操作系统 | Homeward

操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。

一、概述#

1.1 基础特性#

批处理系统有着高资源利用率和系统吞吐量；分时系统能获得及时响应；实时系统具有实时特征。除此之外，操作系统还具有并发、共享、虚拟和异步四个基本特性。

1. 并发

并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。

并行是物理意义上的，需要硬件支持，如多流水线、多核处理器或者分布式计算系统，而并发是逻辑意义上的。

操作系统通过引入进程和线程，使得程序能够并发运行。

2. 共享

共享又称资源复用，是指系统中的资源可以被多个并发进程共同使用。

有两种共享方式：互斥共享和同时共享。

互斥共享的资源称为临界资源，例如打印机等，在同一时刻只允许一个进程访问，需要用同步机制来实现互斥访问。

3. 虚拟

虚拟技术把一个物理实体转换为多个逻辑实体。

主要有两种虚拟技术：时分复用技术和空分复用技术。

多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。

虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。

4. 异步

异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。

1.2 主要功能#

1. 进程管理

处理机的分配和运行都是以进程为基本单位。

进程控制：创建进程和终止已结束进程；
进程同步：进程互斥方式（如加锁）和进程同步方式（如信号量机制）；
进程通信：直接通信方式（如源进程发送命令把消息挂到目标进程的消息队列上）；
调度：作业调度和进程调度；
死锁处理。

2. 内存管理

为多道程序的运行提供良好的环境，提高存储器的利用率。

内存分配：静态分配方式和动态分配方式；
地址映射；
内存保护与共享；
虚拟内存等。

3. 文件管理

为用户进程分配 I/O 设备，提高 CPU 和 I/O 设备的利用率。

文件存储空间的管理；
目录管理；
文件读写管理和保护。

4. 设备管理

完成用户的 I/O 请求，方便用户使用各种设备，并提高设备的利用率。

缓冲管理；
设备分配；
设备处理；
虛拟设备。

1.3 系统调用#

如果一个进程在用户态需要使用内核态的功能，就进行系统调用从而陷入内核，由操作系统代为完成。

1. 指令划分

特权指令：只能由操作系统使用。

如启动 I/O、内存清零、修改程序状态字、设置时钟、允许/禁止终端、停机。
非特权指令：用户程序可以使用的指令。

如控制转移、算数运算、取数指令、访管指令（使用户程序从用户态陷入内核态）。

2. 内核态和用户态

内核态（Kernel Mode）：运行操作系统程序、
用户态（User Mode）：运行用户程序

运行在用户态下的程序不能直接访问操作系统内核数据结构和程序。当我们在系统中执行一个程序时，大部分时间是运行在用户态下的，在其需要操作系统帮助完成某些它没有权力和能力完成的工作时就会切换到内核态。这两种状态的主要差别是：

处于用户态执行时，进程所能访问的内存空间和对象受到限制，其所占有的处理机是可被抢占的；
处于核心态执行中的进程，则能访问所有的内存空间和对象，且所占有的处理机是不允许被抢占的。

3. CPU 状态的切换

用户态 -> 内核态：唯一途径是通过中断、异常、陷入机制（访管指令）；
内核态 -> 用户态：设置程序状态字 PSW。

CPU 上下文切换：

保存 CPU 寄存器里原来用户态的指令位；
为了执行内核态代码，CPU 寄存器需要更新为内核态指令的新位置；
跳转到内核态运行内核任务；
当系统调用结束后，CPU 寄存器需要恢复原来保存的用户态，然后再切换到用户空间，继续运行进程。

以下三种情况会导致用户态到内核态的切换：

系统调用：用户态进程主动要求切换到内核态的一种方式，用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作。比如 fork() 实际上就是执行了一个创建新进程的系统调用。而系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现。
异常：当CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。
外围设备的中断：当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。

4. 大内核和微内核

（1）大内核

大内核是将操作系统功能作为一个紧密结合的整体放到内核，由于各模块共享信息，因此有很高的性能。

（2）微内核

由于操作系统不断复杂，因此将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。

在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。

因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失。

二、进程管理#

2.1 进程与线程#

1. 进程

进程是资源分配的基本单位。

进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作，PCB 是进程存在的唯一标志。

2. 线程

线程是独立调度的基本单位。

一个进程中可以有多个线程，它们共享进程资源。一个进程创建时，操作系统会创建一个线程，这就是主线程，而其他的从线程，需要主线程的代码来创建，也就是由程序员来创建。

3. 区别

（1）拥有资源

进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

（2）调度

线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。不存在没有线程的进程，因为这样的进程将得不到调度。

（3）系统开销

由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

（4）通信方面

线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

2.2 进程的状态#

运行状态：CPU 就绪；其他所需资源就绪；
就绪状态：CPU 未就绪；其他所需资源就绪；
阻塞状态：CPU 未就绪；其他所需资源未就绪；
创建状态：操作系统为新进程分配资源、创建 PCB；
终止状态：操作系统回收进程的资源、撤销 PCB。

只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。

阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

2.3 进程同步#

同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系；
互斥：多个进程在同一时刻只有一个进程能进入临界区。

临界区：对临界资源进行访问的那段代码称为临界区。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。

// 临界区伪代码
entry section        
     critical section 
exit section

1. 硬件同步机制

（1）关中断

禁用中断之后，进程（线程）就不会被切换出去，从而保证代码段能执行结束。但坏处也很明显，由于中断被禁用，如果临界区代码一直执行，其他进程就没机会执行。

（2）原子操作指令

比较常见的原子操作指令包括 test and set 、compare and swap 。

2. 信号量机制

semaphore 由一个整型变量（S）和两个原子操作组成。S 表示资源的数量，而两个原子操作一般被成为 P 操作和 V 操作（有时也被成为wait、signal）。

P 操作表示申请一个资源，P 操作的定义：S = S - 1，若 S >= 0，则执行 P 操作的线程继续执行；若 S < 0，则置该线程为阻塞状态，并将其插入阻塞队列。伪码如下：

Procedure P（Var S：Semaphore）；
　　Begin
　　　　S：=S-1；
　　　　If S<0 then w(S) {执行P操作的线程插入等待队列}
　　End；

V 操作表示释放一个资源，V 操作定义：S = S + 1，若 S > 0 则执行 V 操作的线程继续执行；若 S < 0，则从阻塞状态唤醒一个线程，并将其插入就绪队列。伪代码如下：

Procedure V（Var S：Semaphore）；
　　Begin
　　　　S：=S+1
　　　　If S<=0 then R(s) {从阻塞队列中唤醒一个线程}
　　End；

3. 管程

管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。

管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。

2.4 进程调度算法#

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

1. 批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

（1）先来先服务 first-come first-serverd（FCFS）

非抢占式的调度算法，按照请求的顺序进行调度。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

（2）短作业优先 shortest job first（SJF）

非抢占式的调度算法，按估计运行时间最短的顺序进行调度。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

（3）最短剩余时间优先 shortest remaining time next（SRTN）

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

2. 交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

（1）时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

时间片轮转算法的效率和时间片的大小有很大关系：

因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
而如果时间片过长，那么实时性就不能得到保证。

（2）优先级调度

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

（3）多级反馈队列

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1, 2, 4, 8, …，进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

3. 实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

2.5 上下文切换#

处理器要去执行线程 A 的程序代码时，并不是仅有代码程序就能跑得起来，程序是数据与代码的组合体，代码执行时还必须要有上下文数据的支撑。而这里说的 “上下文”，以程序员的角度来看，是方法调用过程中的各种局部的变量与资源；以线程的角度来看，是方法的调用栈中存储的各类信息；而以操作系统和硬件的角度来看，则是存储在内存、缓存和寄存器中的一个个具体数值。

进程既可以在用户空间运行，又可以在内核空间中运行。进程是由内核来管理和调度的，进程的切换只能发生在内核态。处于用户态的进程的上下文切换大致有以下几个步骤：

中断或系统调用，进入内核态；
保存进程状态到 PCB；
从 PCB 中恢复下一个进程状态；
切换到用户空间，继续运行进程。

线程上下文切换分为两种情况：

前后两个线程属于同一个进程。因为用户态资源是共享的，所以在切换时只需要切换线程的私有数据、寄存器等不共享的数据。
前后两个线程属于不同进程。因为资源不共享，还需要额外切换虚拟内存、全局变量。

2.6 进程通信#

进程同步与进程通信很容易混淆，它们的区别在于：

进程同步：控制多个进程按一定顺序执行；
进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

管道（pipe）及命名管道（named pipe）：管道可用于具有亲缘关系的父子进程间的通信，有名管道除了具有管道所具有的功能外，它还允许无亲缘关系进程间的通信；

信号（signal）：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生；

消息队列：消息队列是消息的链接表，它克服了上两种通信方式中信号量有限的缺点，具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；

共享内存：可以说这是最有用的进程间通信方式。它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等；

信号量：一种计数器，主要作为进程之间及同一种进程的不同线程之间得同步和互斥手段；

套接字：这是一种更为一般得进程间通信机制，它可用于网络中不同机器之间的进程间通信，应用非常广泛。

三、死锁#

互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
占有和等待：已经得到了某个资源的进程可以再请求新的资源。
不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

3.1 死锁处理策略#

1. 死锁预防

（1）破坏互斥条件

例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。

（2）破坏占有和等待条件

一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。

（3）破坏环路等待

给资源统一编号，进程只能按编号顺序来请求资源。

2. 死锁避免

艾兹格·迪杰斯特拉在 1965 年设计的银行家算法，通过记录系统中的资源向量、最大需求矩阵、分配矩阵、需求矩阵，以保证系统只在安全状态下进行资源分配，由此来避免死锁。

3. 死锁检测

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

上图中，有三个进程四个资源，每个数据代表的含义如下：

E 向量：资源总量
A 向量：资源剩余量
C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
R 矩阵：每个进程请求的资源数量

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：

每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
如果没有这样一个进程，算法终止。

4. 死锁恢复

利用抢占恢复
利用回滚恢复
通过杀死进程恢复

四、内存管理#

4.1 虚拟内存#

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。

4.2 分页系统地址映射#

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

下图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为（110 000000000100）。

4.3 页面置换算法#

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

1. OPT

最佳置换算法（OPTimal replacement algorithm，OPT）所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。

最佳置换算法可以用来评价其他算法。

2. FIFO

First In First Out 优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

3. LRU

虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。Least Recently Used 将最近最久未使用的页面换出。

为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

4. NRU

Not Recently Used 将每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R = 1，当页面被修改时设置 M = 1。其中 R 位会定时被清零。可以将页面分成以下四类：

R=0，M=0
R=0，M=1
R=1，M=0
R=1，M=1

当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。

NRU 优先换出已被修改的脏页面（R = 0，M = 1），而非被频繁使用的干净页面（R = 1，M = 0）。

5. Clock

FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：

当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。

第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。

4.4 分段#

内存的分段和分页管理方式和由此衍生的一堆段页式等都属于内存的不连续分配。

1. 分页与分段的比较

对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
地址空间的维度：分页是一维地址空间，分段是二维的。
大小是否可以改变：页的大小不可变，段的大小可以动态改变。
出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

2. 段页式

对于每一个虚拟地址，处理器使用段号检索进程段表来寻找该段的页表；页号用来检索页表并查找到帧号。