操作系统学习笔记-第二章-进程与线程

基于王道计算机考研操作系统。

笔记目录

第一章-计算机系统概述
 第二章-进程与线程
 第三章-内存管理
 第四章-文件系统
 第五章-输入/输出管理

第二章进程与线程

2.1 进程与线程

2.1.1 进程的概念和特征

进程的概念

在多道程序环境下，允许多个程序并发执行。进程的概念是为了更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性。

为了进程都能独立地运行，必须配置一个专门的数据结构，称为进程控制块(PCB)。

系统利用PCB来描述进程的基本情况和运行状态。由程序段、相关数据段和PCB三部分组成了进程实体（又称为进程映像）。创建进程就是创建进程的PCB，撤销进程就是撤销进程的PCB。

对进程比较典型的定义有：

进程是一个正在执行程序的实例。
进程是一个程序及其数据从磁盘加载到内存后，在CPU上的执行过程。
进程是一个具有独立功能的程序在一个数据集合上运行的过程。

我们可将操作系统中的进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程的特征（理解）

进程是由多道程序的并发执行引出的，和程序是两个截然不同的概念。程序是静态的，进程是动态的。进程的基本特征是对比单个程序的顺序执行提出的。

动态性。进程是程序的一次执行，有一定的生命周期，是动态地产生、变化和消亡的。动态性是进程最基本的特征。
并发性。多个进程同存于内存中，且能在一段时间内同时运行。并发性是进程的重要特征，也是操作系统的重要特征。
独立性。进程是一个能独立运行、独立获得资源和独立接受调度的单位。未建立PCB的程序都不能作为一个独立的单位参与运行。
异步性。进程相互制约，按各自独立的、不可预知的速度向前推进。异步性导致执行结果的不可再现性，为此操作系统必须配置相应的进程同步机制。
结构性。每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB组成。

2.1.2 进程的组成

进程是一个独立的运行单位，也是操作系统进行资源分配和调度的基本单位。它由以下三部分组成，PCB是最核心的部分。

进程控制块

进程创建时，操作系统为它新建一个PCB，常驻内存，任意时刻都可以存取，并在进程结束时删除。PCB是进程实体的一部分，是进程存在的唯一标志。

进程执行时，系统通过PCB了解进程现状，以便进行控制管理；进程结束时，系统回收PCB，系统随之消亡。

OS希望调度某个进程运行时，要从PCB查出现行状态和优先级；调度到某个进程后，要根据PCB所保存的CPU状态信息恢复现场，并根据PCB中的程序和数据的内存始址，找到其程序和数据。进程在运行过程中，需要与合作的进程实现同步、通信时，也需要访问PCB。系统总是通过PCB对进程进行控制的，系统也只能通过PCB才能感知到进程的存在。

PCB主要包括进程描述信息、进程控制和管理信息、资源分配清单、处理机相关信息。

进程描述信息
进程标识符(PID)：每个进程的唯一标识号。
用户标识符(UID)：进程所归属的用户。
进程控制和管理信息
进程当前状态：描述进程的状态信息，作为CPU分配调度的依据。
进程优先级：描述进程抢占CPU的优先级，优先级高的进程可优先获得CPU。
资源分配清单
用于说明有关内存地址空间和虚拟地址空间的状况。
处理机相关信息（CPU上下文）
CPU中各寄存器的值，便于进程断点继续执行。

系统中的PCB有的处于就绪态，有的处于阻塞态。为了方便管理和调度，常见的组织方式有链接方式和索引方式。

链接方式将同一状态的PCB连接成一个队列，不同状态对应不同的队列，也可以根据不同阻塞原因分成多个队列。

索引方式将同一状态的PCB组织在一个索引表中，表项指向相应的PCB，不同状态对应不同表，如就绪索引表和阻塞索引表。

程序段

程序段就是能被进程调度到CPU执行的程序代码段，程序可被多个进程共享。

数据段

一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间结果或最终结果。

2.1.3 进程的状态与转换

进程通常有5种状态，前3种是进程的基本状态。PCB中有一个字段记录进程的状态。

运行态。每个时刻只有一个进程处于运行态。
就绪态。进程获得除了CPU以外的一切所需资源，可能有多个就绪态进程，通常排成一个就绪队列。
阻塞态，又叫等待态。进程等待某一事件而暂停运行，即使CPU空闲也不能运行，通常也排成一个队列，根据阻塞原因的不同设置多个阻塞队列。
创建态。进程正在被创建且还未转到就绪态。创建进程需要多个步骤：申请一个空白PCB，向PCB填写控制和管理进程的信息，分配所需资源，将进程转入就绪态并插入就绪队列。
终止态。进程正在从系统中消失。进程需要结束运行时先置为终止态，然后进一步处理资源释放和回收工作。

区别就绪态和阻塞态：就绪态是只缺少CPU，一旦获得CPU就立即执行；阻塞态是需要除CPU的其他资源或等待某一事件。就绪态和阻塞态是进程生命周期中两个完全不一样的状态。

一个进程从运行态变为阻塞态是主动的行为（一般通过系统调用），从阻塞态变为就绪态是被动的行为，需要其他相关进程的协助。

2.1.4 进程控制

进程控制的主要功能是创建新进程、撤销已有进程、实现进程状态转换等功能。一般将进程控制用的程序段称为原语，进程控制用原语实现，原语的特点是原子性，执行期间不允许中断，是一个不可分割的基本单位。原语的原子性通过关中断和开中断两个特权指令实现。

进程的创建

允许一个父进程创建一个子进程，子进程可以继承父进程所拥有的资源，子进程被撤销时将资源归还给父进程，撤销父进程时通常连同撤销所有子进程。

操作系统中，终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等都会引起进程的创建，操作系统创建一个进程的过程如下：

为新进程分配唯一标识号(PID)，并申请一个空白PCB。PCB申请失败则创建失败。
为进程分配其运行所需的资源。如果资源不足不会创建失败，而是处于创建态，等待内存资源。
初始化PCB。初始化标志信息、CPU状态、控制信息、进程优先级等等。
插入进程就绪队列。

进程的终止

引起进程终止的事件主要有：

正常结束。
异常结束，出现某种异常事件导致无法继续运行。
外界干预，应外界请求而终止运行。

终止进程的过程如下：

根据终止进程PID找到PCB，读取状态。
若处于运行状态，立即终止运行，将CPU资源分配给其他进程。
若还有子孙进程，通常也要终止。
将进程拥有的所有资源归还父进程或OS。
将PCB从所在队列删除。

进程的阻塞和唤醒

正在进行的进程由于期待的事件未发生，调用阻塞原语将自己变为阻塞态。阻塞是进程自身的一种主动行为，也只有处于运行态的进程（拥有CPU），才能成将其转换为阻塞态。

阻塞原语的执行过程如下：

找到阻塞进程PID的PCB。
若为运行态，则保护现场，转变为阻塞态，停止运行。
将PCB插入等待队列，将CPU资源调度给其他就绪进程。

当阻塞期待的事件出现时，进程调用唤醒原语，将等待该事件的进程唤醒。

唤醒原语的执行过程如下：

在该事件的等待队列中找到相应进程的PCB。
从等待队列中移出，设置状态为就绪态。
将PCB插入就绪队列等待调度。

Block原语和Wakeup原语是一对作用刚好相反的原语，必须成对使用，否则阻塞进程将永远不能唤醒而永久处于阻塞态。

2.1.5 进程的通信（IPC）

进程通信是指进程之间的信息交换。PV操作是低级通信方式，高级通信方式是指以较高的效率传输大量数据的通信方式。高级通信方式主要有3类。

共享存储（最快）

在通信的进程之间存在一块可直接访问的共享空间（可以是虚拟空间），通过这块空间进行信息交换。在对共享空间进行读写操作时，需要使用同步互斥工具进行控制。

共享存储又分为两种：低级方式的共享是基于数据结构的共享；高级方式的共享是基于存储区的共享。操作系统指为进程提供共享空间和互斥工具，具体的数据交换由用户自己安排读写指令完成。

进程空间一般是独立的，想让两个进程共享空间，必须通过特殊的系统调用实现，而进程内的线程是自然共享进程空间的。

消息传递

如果不存在可直接访问的共享空间，则必须利用操作系统提供的消息传递方法实现进程通信。在消息传递系统中，进程之间的数据交换以格式化的消息为单位。进程通过操作系统提供的发送消息和接收消息两个原语进行数据交换。

这种方式隐藏了通信实现细节，使通信过程对用户透明，是当前应用最广泛的进程间通信机制。在微内核操作系统中，微内核和服务器之间的通信就采用了消息传递机制。这个机制还能很好地支持多CPU系统、分布式系统和计算机网络。

直接通信方式。发送进程直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上。
间接通信方式。发送进程将消息发送到某个中间实体，接收进程从中间实体取得信息。这个中间实体一般称为信箱。该通信方式广泛应用于计算机网络中。

管道通信

管道是一个特殊的共享文件，又称pipe文件，数据在管道中先进先出。管道通信允许两个进程按生产者-消费者方式进行通信。只要管道不满，就能一直写入数据；只要管道不空，就能一直读取数据。

管道机制必须提供三方面的协调能力：

互斥，一个进程对管道读/写的时候，其他进程必须等待。
同步，写入一定量数据后，写进程阻塞，直到读进程取走数据后再唤醒。
确定对方的存在。

在Linux中，管道是一种使用非常频繁的通信机制。管道本质上也是一种文件，但又和一般的文件不同。管道可以克服使用文件通信的两个问题：

限制管道的大小。管道文件是一个固定大小的缓冲区，在Linux中大小为4KB，这样使得它的大小不会像普通文件一样不加检验地增长。使用单个固定缓冲区也会带来问题，比如写管道时可能变满，这种情况发生时，随后对管道写的调用会默认阻塞，等待某些数据被读取，以便腾出足够的空间供写使用。
读进程也可能工作的比写进程快，管道被读空，这种情况读调用将会被阻塞，等待某些数据的写入。

管道只能被创建进程访问，父进程创建一个管道后，子进程会继承父进程的管道，并可用它来与父进程通信。

管道中的数据一旦被读出就彻底消失，多个进程读同一个管道时可能会错乱。通常有两种解决方案：

一个管道允许多个写进程，一个读进程。
允许有多个写进程，多个读进程，但是系统会让哥哥读进程轮流从管道中读数据。

从管道读数据是一次性操作，数据一旦被读取，就释放空间。普通管道只允许单向通信（半双工通信），想要双向同时通信（全双工）需要定义两个管道。

2.1.6 线程和多线程模型

线程的基本概念

引入进程的目的是为了更好地使多道程序并发执行，提高资源利用率和系统吞吐量；引入线程的目的是减小程序在并发执行时付出的时空开销，提高操作系统的并发性能。

线程最直接的理解是轻量级进程，它是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。

线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只用有一点在运行中必不可少的资源，但它可与同属一个进程的其他线程共享所拥有的全部资源。一个线程可以创建或撤销另一个线程，同进程的多个线程可以并发执行。线程在运行中呈现出间断性。线程也有就绪、阻塞、运行三种基本状态。

进程只作为除CPU外的系统资源的分配单元，而线程作为CPU的分配单元。由于一个进程内部有多个线程，线程的切换如果发生在进程内部，则只需要很少的进程开销。

线程与进程的比较

调度。线程是独立调度的基本单位，线程切换的代价远低于进程。在同一进程中，线程的切换不会引起进程切换。
并发性。一个进程中的多个线程之间也能并发执行，不同进程中的线程也能并发执行。
拥有资源。进程是系统中拥有资源的基本单位，线程不拥有资源，但是可以访问其隶属进程的系统资源，主要表现在属于同一进程的所有线程都具有相同的地址空间。
独立性。每个进程都有独立的地址空间和资源，除了共享全局变量，不允许其他进程访问。某个进程的线程对其他进程不可见。
系统开销。创建和撤销进程时要分配和回收PCB以及其他资源，开销较大。线程切换只需保存和设置少量寄存器内容，开销很小。同一进程内的线程共享进程的地址空间，线程之间的同步和通信非常容易实现。
支持多处理器系统。单线程进程只能运行在一个CPU上。对于多线程进程，可以将进程的多个线程分配到多个CPU上执行。

线程的属性

多线程操作系统的进程已经不再是一个基本的执行实体，所谓进程处于执行状态，实际上是该进程的线程正在执行。

线程的主要属性如下：

线程是一个轻型实体，不拥有系统资源，但每个线程都有一个唯一标识符和一个线程控制块，线程控制块记录线程执行的寄存器和栈等现场状态。
不同的线程可以执行相同的程序，同一个服务被不同用户调用，操作系统将他们创建成不同的线程。
同一进程中的各个线程共享该进程拥有的资源。
线程是CPU的独立调度单位，多个线程可以并发执行。单CPU计算机中各线程交替使用CPU；多CPU计算机中各线程同时占用不同的CPU。
一个线程被创建后，就开始了它的生命周期，直到终止。

线程的状态与转换

线程在运行时也有间断性。线程有下面三种基本状态：

执行态。
就绪态。
阻塞态。

线程切换时，需要保存PC、其他寄存器、堆栈指针的值到TCB中，以便恢复断点。

线程的组织与控制

线程控制块

线程控制块(TCB)与PCB类似，用于记录控制和管理线程的信息，通常包括：线程标识符；一组寄存器；线程运行状态；优先级；线程专有存储区，用于保存现场；堆栈指针，用于过程调用保存局部变量和返回地址等。

各个线程都可以读、写甚至清除另一个线程的堆栈。

线程的创建

线程由创建而产生，由调度而执行，由终止而消亡。

用户程序启动时，通常仅由一个初始化线程的线程正在执行，主要功能是创建新线程。创建新线程时，需要利用一个线程创建函数，并提供相应参数，比如入口指针、堆栈大小、优先级等。线程创建函数执行完会返回线程标识符。

线程的终止

线程完成自己的任务或出现异常强制终止后，由终止线程调用相应函数执行终止操作。

有些线程比如系统线程一旦被建立，便一直运行不会被终止。线程被终止后不会立即释放它占有的资源，只有进程中的其他线程执行了分离函数后，被终止线程才与资源分离，这些资源才能被其他线程利用。

被终止但未释放资源的线程仍可被其他线程调用，以便被终止线程重新恢复运行。

线程的实现方式

线程的实现可以分为用户级线程和内核级线程。

用户级线程（ULT）

用户级线程中，有关线程管理（创建、撤销、切换等）的所有工作都由应用程序在用户态完成，无需操作系统干预。应用程序通常从单线程开始，在该线程中开始运行，通过调用线程库中的派生例程创建一个相同进程中运行的新线程。

设置了用户级线程的系统，其调度仍然以进程为单位进行，各个程轮流进行一个时间片。这种实现方式的优点如下：

线程切换不用转换到内核态，节省开销。
调度算法可以是进程专用的，不同进程可以根据自己的需要，对自己的进程选择不同的调度算法。
用户级线程的实现和操作系统平台无关，对线程管理的代码是属于用户程序的一部分。

缺点如下：

系统调用的阻塞问题，线程执行一个系统调用时，不仅该线程被阻塞，进程内的所有线程都被阻塞。
不能发挥多CPU的优势，内核每次仅分配一个CPU给进程，只有一个线程能执行。

内核级线程（KLT）

内核级线程是在内核的支持下运行的，线程管理的所有工作在内核态实现。内核根据TCB感知线程的存在，并加以控制。

优点如下：

能发挥多CPU的优势，内核能同时调度同一进程的多个线程。
如果进程打一个线程被阻塞，内核可以调度其他线程占用CPU，也可以运行其他进程的线程。
内核支持线程有很小的数据结构和堆栈，线程切换比较快。
内核本身也可采用多线程技术，提高系统的执行速度和效率。

组合方式

有些系统使用组合方式的多线程实现。组合实现方式中，内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程。一些内核级线程对应多个用户级线程，这是用户级线程通过时分多路复用内核级线程来实现的。

同一个进程中的多个线程可以同时在多CPU上并行执行，且在阻塞一个线程时不需要将整个进程阻塞，组合方式结合了KLT和ULT的优点，并克服各自的不足。

线程库

线程库是为程序员提供创建和管理线程的API。实现线程库的方法有：

在用户空间中提供一个没有内核支持的库。这种库的所有代码和数据结构都位于用户空间中。调用库内的一个函数只导致用户空间的一个本地函数的调用。
实现由操作系统直接支持的内核级的一个库。库内的所有代码和数据结构都位于内核空间。调用库中的一个API函数通常会导致对内核的系统调用。

多线程模型

多对一模型。将多个用户级线程映射到一个内核级线程，每个进程只被分配一个内核级线程，线程的调度和管理在用户空间完成。仅当用户线程需要访问内核时，才将其映射到一个内核级线程上，但每次只允许一个线程进行映射。
优点：线程管理是在用户空间进行的，无需切换到核心态，效率比较高。
缺点：如果一个线程在访问内核时发生阻塞，整个进程都会被阻塞；同一时间只有一个线程能访问内核，多个线程不能同时在CPU上运行。
一对一模型。将每个用户级线程映射到一个内核级线程。每个进程有与用户线程数量相同的内核级线程，线程切换由内核完成，需要切换到核心态。
优点：一个线程被阻塞后，允许调度另一个线程运行，并发能力较强。
缺点：每创建一个用户线程就要创建一个对应的内核线程，开销较大。
多对多模型。将n个用户级线程映射到m个内核级线程上，$n>=m$。
特点：既克服了多对一模型并发度不高的缺点，又客服了一对一模型开销大的缺点，还拥有他们各自的优点。

2.1.7 信号

信号机制主要用于实现进程之间的通信，用于通知进程某个特定事件已经发生。进程收到一个信号后，对该信号进行处理。

通常用宏定义常量表示信号名，不同操作系统对信号类型的定义也不一样。

信号的发送与保存

PCB中包含pending（待处理）和blocked（被阻塞，也可称为信号掩码）两个位向量。用n比特的位向量表示n种信号。

用户进程之间可以发送信号，内核进程也可以给用户进程发送信号，但是用户进程之间允许发送的信号类型是有限制的，内核没有什么限制。

常用的发送信号的函数kill函数：

int kill(pid_t pid,int sig)
    //pid代表发给谁，sig代表发什么信号

收到kill函数后，pending中的对应位向量置1，不过它无法分辨是哪个进程发过来的。

信号的处理

每次进程从内核态转为用户态时，例行检查是否有待处理信号，如果有，就处理信号。

检查的过程：

blocked位向量全部按位取反。
取反后的blocked和pending逐位进行与运算。
根据运算的结果，为1对应的信号就是需要处理的信号。

怎么处理信号：

执行操作系统会为这个信号设置的缺省处理程序（默认）。
执行进程为此类信号设置的用户自定义信号处理程序。
有些信号既不能被用户自定义处理，也不能被阻塞，例如Linux的SIGKILL、SIGSTOP信号。

一些补充信息：
信号处理程序运行结束后，通常会返回进程的下一条指令运行，除非信号处理程序将进程阻塞或终止。
一旦处理了某个信号，就将pending重置为0。
重复收到的同类信号，将被简单的丢弃。
同时收到多个不同信号时，通常先处理序号更小的序号。
每个进程自定义的信号处理程序是只针对自身的，不同进程对相同的信号可能会有不同的信号处理程序。

信号和异常的关系

信号可以作为异常的配套机制，让进程对操作系统的异常处理进行补充。

有些异常（如缺页）可以由内核完成全部处理，此时就不用使用信号机制。
有些异常可能还需要用户进程配合，可以用信号和异常相互配合。

2.2 CPU调度

2.2.1 调度的概念

调度的基本概念

在多道程序系统中，进程的数量往往多于CPU的个数，因此进程争用CPU的情况在所难免。CPU的调度是对CPU进行分配，从就绪队列中按照一定的算法选择一个进程分配CPU，实现进程并发执行。

CPU调度是多道程序操作系统的基础，是操作系统设计的核心问题。

调度的层次

一个作业从提交开始直到完成，往往要经历以下三级调度。

高级调度（作业调度）
按照某种规则从外存上处于后备队列的作业中挑选一个或多个，分配必要的资源，并建立相应的进程，使他们获得竞争CPU的权利。作业调度就是内存与辅存之间的调度，每个作业只调入、调出一次。
多道批处理系统中大多配有作业调度，其他系统中通常不需要配置作业调度。
中级调度（内存调度）
引入中级调度的目的是提高内存利用率和系统吞吐量。那些暂时不能运行的进程调整至外存等待，此时进程的状态称为挂起态。当他们具备运行条件且内存稍有空闲时，由中级调度来决定将那些具备条件的挂起进程重新调入内存，并修改为就绪态，插入就绪队列。中级调度实际上是存储器管理中的对换功能。
低级调度（进程调度）
按照某种算法从就绪队列选区一个进程分配CPU。进程调度是最基本的一种调度，各种操作系统都必须配置这级调度。进程调度的频率很高，一般几十毫秒一次。

三级调度的联系

作业调度从外存的后备队列选择一批作业进入内存，为他们建立进程，送入就绪队列。进程调度从就绪队列中选出一个进程，改为运行态，分配CPU。中级调度为了提高内存的利用率，挂起那些暂时不能运行的进程。

作业调度为进程的活动做准备，进程调度使进程正常活动起来。
中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间。
作业调度次数少，中级调度次数略多，进程调度频率最高。
进程调度是最基本的，不可或缺。

2.2.2 调度的实现

调度程序（调度器）

用于调度和分派CPU的组件称为调度程序，通常由三部分组成。

排队器。系统中所有就绪进程按照一定的策略排成一个或多个队列，以便调度程序选择。每当有一个进程转变为就绪态，排队器就将它插入就绪队列。
分派器。依据调度程序所选的进程，将其从就绪队列中取出，分配CPU。
上下文切换器。在对CPU进行切换时，会发生两对上下文切换操作：第一对，将当前进程上下文存入PCB，再装入分派程序的上下文。第二队，移出分派程序的上下文，将新选程序的CPU现场信息装入CPU的各个相应寄存器。

在上下文切换时需要执行大量load和store指令，会消耗较多时间。现在有硬件实现的方法来减少上下文切换时间：通常采用两组寄存器，一组给内核，一组给用户。上下文切换时，只需要改变指针指向当前寄存器组即可。

调度的时机、切换与过程

调度程序是操作系统内核程序。请求调度的事件发生后才能运行调度程序，调度新的就绪程序之后才会进行进程切换。理论上应该顺序执行这几件事，但是实际如果某时刻发生了引起进程调度的因素，不一定能马上进行调度与切换。

应该进行进程调度与切换的情况如下：

创建新进程后，父进程和子进程都处于就绪态，因此要决定运行哪个进程，调度程序可以决定其中一个先运行。
进程正常结束或异常终止后，必须从就绪队列选择一个进程运行。若没有就绪进程，则通常运行系统提供的闲逛进程。
进程因某种原因被阻塞时，必须调度其他进程运行。
进程由阻塞态变为就绪态，需要决定让新的就绪程序投入运行还是让这个程序继续进行。

此外，有更紧急的任务或当前的时间片用完时，也被强行剥夺CPU。

进程切换往往在调度完成后立刻发生，要求保存原进程断点的现场信息，恢复被调度进程的现场信息。现场切换时，操作系统内核将现场信息推入进程的内核堆栈保存他们，更新栈指针。内核完成更新新进程现场后开始新的进程。

不能进行进程调度与切换的情况如下：

在处理中断的过程中。中断的处理过程很复杂，实现上很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应该剥夺CPU资源。
需要完全屏蔽中断的原子操作过程。
进程在操作系统内核程序临界区中。

如果在上述过程发生了引起调度的条件，不能马上进行调度和切换，应该置系统的请求调度标志，等到上述过程结束后才可以调度与切换。

进程调度的方式

非抢占调度方式，又称为非剥夺方式。一个进程在CPU上执行时，即使有某个更重要的进程进入就绪队列，也要等待该进程完成或阻塞才将CPU分配给其他进程。
非抢占的优点是实现简单、系统开销小，适用于早期的批处理系统，但是不能用于分时系统和大多数实时系统。
抢占式调度方式，又称为剥夺方式。如果有更重要的进程进入就绪队列，允许调度程序根据某种原则暂停正在执行的进程，将CPU分配给紧急进程。
抢占调度对提高系统吞吐率和响应效率都有明显的好处。但是抢占必须遵循一定的原则，例如优先权、短进程优先、时间片原则等。

闲逛进程

进程切换时如果没有就绪进程，就会调度闲逛进程运行，PID为0。如果没有其他进程就绪，该进程就会一直运行，并在指令周期后测试中断。闲逛进程的优先级最低，只有有进程就绪就会立即让出CPU。

闲逛进程不需要CPU以外的资源，不会被阻塞，能耗低。

两种线程的调度

用户级线程调度。内核并不知道线程的存在，它只选择一个进程，给予时间控制，由进程的调度程序决定哪个线程运行。
内核级线程调度。内核选择特定线程运行，赋予时间片，通常不考虑属于哪个进程。

用户级线程切换在同一进程内运行，仅需少量的机器指令。内核级的线程切换需要完整的上下文切换、修改内存映像、使高速缓存失效，这就导致了若干数量级的延迟。

2.2.3 调度的目标（评价指标）

CPU利用率。$CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}$
系统吞吐量。表示单位时间内CPU完成作业的数量。长作业会降低吞吐量，短作业能提高吞吐量。调度算法和方式的不同也会影响吞吐量。
周转时间。指作业提交到作业完成经历的时间。是作业等待、就绪队列排队、CPU上运行、I/O操作花费时间的总和。$周转时间=作业完成时间-作业提交时间$。$带权周转时间=\frac{周转时间}{作业实际运行的时间}$。
平均周转时间是多个作业周转时间的平均值。带权周转时间是多个作业带权周转时间的平均值。他们越小越好。
等待时间。进程等待CPU的时间之和。衡量一个调度算法的优劣，常常只需简单地考查等待时间。
响应时间。从用户提交请求到系统首次产生响应的时间。交互式系统中，周转时间不是最好的评价准则，通常采用响应时间作为衡量调度算法的重要准则之一。

2.2.4 进程切换

进程切换是在内核的支持下实现的，任何进程都是在操作系统内核的支持下运行的。

上下文切换

切换CPU到另一个进程要保存当前进程状态并恢复上一个进程的状态，称为上下文切换。进程上下文采用PCB表示，包括CPU寄存器的值、进程状态和内存管理信息等。

切换流程如下：

挂起一个进程，将上下文保存到PCB，包括PC值和其他寄存器。
将进程的PCB移到相应的队列。
选择另一个进程执行，并更新PCB。
恢复新进程的CPU上下文。
跳转到新进程PCB的PC指向的位置执行。

上下文切换的消耗

上下文切换通常是计算密集型的，需要可观的CPU时间，每秒上百次切换，每次切换需要纳秒量级时间，对于系统意味着消耗大量CPU时间。

有些CPU提供多个寄存器组，这样上下文切换只需要简单地改变当前寄存器组的指针。

上下文切换与模式切换

模式切换与上下文切换不同，模式切换时，CPU可能还在执行同一进程。用户态和内核态的切换称为模式切换，没有改变当前的进程。

上下文切换只能发生在内核态，它是多任务操作系统的一个必需特性。

调度和切换的区别：调度指决定资源分配的行为，是一种决策行为；切换是实际分配的行为，是执行行为。一般来说，先有资源的调度，然后才有进程的切换。

2.2.5 典型的调度算法

先来先服务（FCFS）

在作业调度中，FCFS每次从后备队列选择最先进入队列的一个或几个作业，调入内存，分配资源，创建进程并放入就绪队列。

进程调度中，FCFS每次从就绪队列选择最先进入该队列的进程，直到运行完成或阻塞才释放CPU。

FCFS属于不可剥夺算法。因此容易被长作业占据大量时间，不能作为分时系统和实时系统的主要调度策略。但是它常被结合其他调度策略使用，例如优先级调度。

FCFS的特点是算法简单，但效率低；对长作业有利，对短作业不利；有利于CPU繁忙型作业，不利于I/O繁忙型作业。

短作业/进程优先（SJF/SPF）

SJF对短作业（进程）优先调度，从后备队列选择一个或几个估计运行时间最短的作业（进程）。在所有进程几乎同时到达时，采用SJF的平均等待时间和平均周转时间最少。

SJF算法的缺点：

对长作业不利，周转时间增加，长作业可能长期不调度，产生饥饿现象。
未考虑作业的紧迫程度。
作业的长短是用户提供的估计时间，不一定真正能做到短作业优先。

SPF也可以是抢占式的。当新进程到达就绪队列，如果预估比当前进程还短，则立即停止当前进程，将CPU分配给新进程，因此抢占式SPF又叫最短剩余时间优先算法。

高响应比优先（HRRN）

高响应比优先主要用于作业调度，是对FCFS和SJF的综合平衡。每次调度先计算作业响应比，选响应比最高的投入运行。高响应比优先是非抢占式的。

$响应比R_p=\frac{等待时间+要求服务时间}{要求服务时间}$

作业的等待时间相同，要求服务时间越短，响应比越高，有利于短作业，类似SJF。
要求服务时间相同，作业的响应比由等待时间决定，等待时间越长越高，类似FCFS。
对于长作业的响应比随着时间提高，等待时间足够长也能获得CPU，克服饥饿现象。

优先级

优先级可用于作业和进程调度，优先级用来描述作业的紧迫程度，每次从后备队列挑选优先级最高的一个或几个。

非抢占式优先级调度算法。某个优先级更高的进程进入队列，正在运行的进程继续运行，直到完成或等待事件，然后才是新进程。
抢占式优先级调度算法。某个优先级更高的进程进入就绪队列，立即暂停当前进程，将CPU分给新进程。

优先级可分为：

静态优先级。优先级在进程创建时确定，且整个运行期间不变。确定的依据有进程类型、资源要求、用户要求。
优点时简单易行，系统开销小；
缺点是不够精确，优先级低的进程可能长期得不到满足。
动态优先级。创建时先赋予一个优先级，优先级随着进程的推进或等待时间的增加而改变。例如规定随着时间增加提高，这样优先级初值较低的进程在等待够长后也能获得CPU。

一般来说可以参照以下原则：

系统进程>用户进程。
交互型进程（前台）>非交互型进程（后台）。
I/O型进程（I/O密集）>计算型进程（CPU密集）。

时间片轮转（RR）

时间片轮转适用于分时系统。将所有就绪进程按FCFS排成一个就绪队列，每隔一定时间产生一次时钟中断，激活调度程序调度，给队首进程分配一个时间片。

若时间片未用完而进程执行完成，则调度程序会立即激活；时间片用完，则产生时钟中断，由时间中断处理程序来激活调度程序。

在RR算法中，时间片的大小对性能影响很大，时间片足够大则退化成FCFS算法，增大进程响应时间；时间片太小则切换频繁，加大CPU开销。时间片的长短通常由系统的响应时间、就绪队列中的进程数目和系统的处理能力决定。

多级队列

前面的算法只设置一个就绪队列，算法是固定且单一的，无法满足不同用户对调度策略的不同要求。多CPU系统中这种缺点更加突出，多级队列调度算法可以一定程度上弥补。

该算法在系统中设置多个就绪队列，不同类型或性质的进程固定分配到不同的就绪队列，每隔队列可以实施不同的调度算法。同一队列/不同队列的进程可以设置不同的优先级。

在多CPU系统中，多级队列可以很方便的为每个CPU设置一个单独的就绪队列，每个CPU各自实施不同的调度策略，这样可以根据用户需求将多个线程分配到一个或多个CPU运行。

多级反馈队列

多级反馈队列结合了时间片轮转和优先级算法，动态调整优先级和时间片大小，比如为了提高系统吞吐量和缩短平均周转时间而照顾短进程；为了获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。同时也不用事先预估进程的执行时间。

设置多个就绪队列，为每个队列赋予不同的优先级。
赋予各个队列的进程运行时间片的大小各不同，优先级越高的队列时间片越小。
每个队列都采用FCFS。若时间片内未完成则进入下一级队列，降到n级队列以后变为时间片轮转。
按队列优先级调度。当第1级为空时才会执行第2级，当1到i-1级队列都为空时，才会执行第i级队列。如果正在执行第i级进程，此时有新进程优先级更高，则立即将当前进程放回i级队列队尾，CPU分配给高优先级进程。

多级反馈的优势有以下几点：

终端型作业用户：短作业优先。
短批处理作业用户：周转时间较短。
长批处理作业用户：前面几个队列得到部分执行，不会一直不处理。

2.2.6 多处理机调度

单处理机调度：只需决定让哪个就绪进程优先上处理机即可。

多处理机调度：还需要决定被调度的进程上哪个处理机。还需要考虑负载均衡和处理机亲和性。

负载均衡：尽可能让每个CPU都同等忙碌。

处理机亲和性：尽量让一个进程调度到同一个CPU上运行，发挥CPU缓存（Cache）的作用。

公共就绪队列

系统内的所有就绪进程都放在统一的就绪队列中（位于内核区），由所有CPU共享。每个CPU时运行调度程序，从公共就绪队列选择一个进程运行。

所以为了保证访问队列的操作互斥，CPU访问公共就绪队列时需要上锁。

优点：可以天然实现负载均衡。

缺点：各个进程频繁切换CPU运行，亲和性不好。

提升亲和性的方法：
软亲和：由进程调度程序尽量保证亲和性。
硬亲和：由用户进程通过系统调用，主动要求操作系统分配固定的CPU。

私有就绪队列

每个CPU都有一个私有的就绪队列，CPU空闲时运行调度程序，从私有队列中选择一个进程运行。

实现均衡负载的方法：

推迁移。一个特定的系统程序周期性检查每个处理器的负载，如果负载不平衡，就从忙碌的CPU的就绪队列中推一些就绪进程到空闲的CPU的就绪队列。
拉迁移。每个CPU运行调度程序时，周期性检查自身负载与其他CPU负载。如果一个CPU负载很低，就从其他高负载的CPU的就绪队列拉一些就绪进程到自己的就绪队列。

私有就绪队列天然实现了亲和性，当不希望进程切换CPU运行时，程序员可以通过系统调用的方式保证硬亲和。

2.3 同步与互斥

2.3.1 同步与互斥的基本概念

临界资源

一次仅允许一个进程使用的资源称为临界资源。许多物理设备属于临界资源，还有许多变量、数据都可以被若干进程共享，也属于临界资源。在每个进程中，访问临界资源的那段代码称为临界区。

可将临界资源的访问过程分为4个部分：

进入区。在进入区要检查是否可进入临界区，若能，则应设置正在访问临界区的标志，防止其他进程同时进入。
临界区。访问临界资源的代码段，又称为临界段。
退出区。将访问标志去除。
剩余区。代码的剩余部分。

同步

同步也称为直接制约关系，指为了完成任务而建立的两个或多个进程，需要协调运行次序、传递信息而产生的制约关系。同步关系源于进程之间的相互合作。

互斥

互斥也称间接制约关系。一个进程进入临界区使用临界资源，另一个进程必须等待。

同步机制应该遵循：

空闲让进。临界区空闲时，可以允许一个请求进程立即进入临界区。
忙则等待。已有进程进入临界区时，其他进程必须等待。
有限等待。对请求进入的进程，应该保证能在有限时间内进入临界区，防止无限等待。
让权等待（原则上遵循，但非必须）。进程不能进入临界区时，应立即释放处理器。

2.3.2 实现临界区互斥的基本方法

软件实现方法

在进入区设置并检查一些标志来表明是否有进程在临界区中。

单标志法

设置一个公用整型变量turn，表示允许进入临界区的进程编号。当turn = i时，表示允许$P_i$进入临界区。进程退出临界区将使用权给另一个进程，将turn置为j。

该算法可以实现每次仅允许一个进程进入临界区，但两个进程必须交替进入临界区，若某个进程不再进入临界区，另一个进程也将无法进入（违背空闲让进），很容易造成资源利用不充分。

双标志先检查法

设置一个bool型数组flag[2]，标记各个进程想进入临界区的意愿。flag[i] = true表示$P_i$想进入临界区。$P_i$进入临界区前，先检查对方是否想进入临界区，若想，则等待；否则将flag[i] = true，再进入临界区，退出时置为false。

优点：不用交替进入，可连续使用。

缺点：两个进程可能同时进入临界区，由于检查和设置操作不是一气呵成的，可能会导致正好双方都检查通过（违背忙则等待）。

双标志后检查法

在上面算法的基础上，先设置自己的标志，再检查对方的标志，若对方的标志为true，则等待；否则进入临界区。

两个进程依次设置自己的标志，并依次检查对方的标志，可能会出现发现对方也想进入临界区，导致谁也进不了（违背空闲让进），发生饥饿现象（违背有限等待）。

Peterson算法

Peterson算法结合了算法一和三的思想，利用flag[]解决互斥访问问题，利用turn解决饥饿问题。如果双方争着进临界区，则可让进程将进入临界区的机会谦让给对方。

进入临界区之前，进程先设置自己的flag标志，再设置允许进入turn标志，之后再同时检测对方的标志。

双方如果想同时进入，会各自置自己的flag，然后同时设置turn。但是只有一个结果会被保持，turn的最终值决定了哪个进程被允许先进入临界区。

相比于前三个算法，Peterson算法满足了空闲让进、忙则等待、有限等待，但是依然未遵循让权等待。

硬件实现方法

中断屏蔽方法

一个进程正在执行它的临界区代码时，关中断。等执行完再开中断。

缺点：

限制了CPU交替执行程序的能力，系统效率明显降低。
对内核来说，关中断很方便，但是权限交给用户很不明智，如果不再开中断，系统可能会终止。
不适合多处理器系统，在一个CPU上关中断不能防止其他CPU执行临界区代码。

硬件指令方法（TestAndSet）

TestAndSet指令简称TS指令，这条指令是原子操作，功能是读出指定标志后将标志设置为真。

用TS指令管理临界区时，为每个临界资源都设置一个共享bool变量lock，true表示正被占用，false表示空闲，初始值为false。

进程进入临界区前，先用TS指令检查lock值，若为false则可以进入，并改为true；若为true则等待。

TS指令将加锁和检查操作用硬件方式变成了原子操作。相比于关中断方法，由于锁是共享的，更适用于多处理器系统。缺点是暂时无法进入临界区的进程会占用CPU循环执行TS指令，无法做到让权等待。

硬件指令方法2（Swap指令）

用Swap指令管理临界区时，给每个临界资源设置一个bool型变量lock，初始为false；再在每个进程设置一个局部bool变量key，初值为true，用于和lock交换信息。

Swap指令先记录临界区是否已加锁，再将lock置为true，最后检查key，如果为false，说明之前没有其他进程对临界区加锁，可以进入临界区。

用硬件指令实现互斥的优点：

简单、容易验证其正确性。
适用于任意数目的进程，支持多处理器系统。
支持系统中有多个临界区，只需为每个临界区设立一个bool变量。

缺点：

等待进入临界区的进程会占用CPU执行while循环，不能实现让权等待。
等待进程中随机选择一个进程进入临界区，可能会有进程一直选不上导致饥饿。

TS指令和Swap指令都仅为功能描述，由硬件逻辑实现，不会被中断。

2.3.3 互斥锁

解决临界区最简单的工具就是互斥锁。在进程进入临界区时调用acquire()函数以获得锁；在退出时调用release()以释放锁。每个互斥锁有一个bool变量available，表示锁是否可用。可用的话，调用acquire()会成功，并且锁不可再用。当试图获取不可用的锁时，进程会被阻塞，直到锁被释放。

acquire()或release()的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

上面描述的互斥锁也称自旋锁，主要缺点是忙等待。类似单标志法、TS指令和Swap指令，需要循环忙等，会卡在入口占用CPU。因此互斥锁通常用于多处理器系统，一个线程可以在一个处理器上旋转，而不影响其他线程的执行。

自旋锁的优点是，进程在等待锁期间，没有上下文切换，如果上锁的时间比较短，则等待代价不高。

2.3.4 信号量

信号量机制是一种功能较强的机制，用来解决互斥和同步问题，只能被两种标准的原语wait()和signal()访问，可以简写为P()和V()，即P操作和V操作。

整型信号量

整型信号量被定义为一个用于表示资源数目的整型量S。对于S的操作只有三种：初始化、wait操作和signal操作。

wait(S){            //相当于进入区
    while(S<=0);  //资源数不够就循环等待
    S = S - 1;    //资源数够就占用一个资源
}
signal(S){        //相当于退出区
    S = S + 1;   //使用后释放一个资源
}

该机制实现了检查和上锁一气呵成，避免了并发、异步导致的问题。但是该机制也未实现让权等待，使进程处于忙等。

记录型信号量

记录性信号量是一种不存在忙等现象的进程同步机制。需要一个代表资源数目的整型变量value和一个用于链接所有等待该资源进程的进程链表L。

typedef struct{
    int value;
    struct process *L;
} semaphore;

void wait(semaphore S){  //申请资源
    S.value--;
    if(S.value < 0){
        add this process to S.L;
        block(S.L);
    }
}

void signal(semaphore S){ //释放资源
    S.value++;
    if(S.value <= 0){
        remove a process P from S.L;
        wakeup(P);
    }
}

对于信号量的一次P操作，表示进程请求一个该类资源，当S.value < 0时，说明资源已经分配完毕，应该使用block原语进行自我阻塞，主动放弃CPU，并插入等待队列S.L。

对于信号量的一次V操作，表示进程释放一个该类资源，若S.value++后仍然是S.value <= 0，说明仍有进程在等待该类资源，因此应调用wakeup原语将S.L的第一个进程唤醒。

使用信号量实现进程互斥

为了实现互斥访问临界资源，需要为该资源设置一个信号量S，初值为1，然后将各个进程访问该资源的临界区置于P(S)和V(S)之间。这样每个进程进入临界区之前，都会对S做P操作，如果访问成功则进入，如果失败则阻塞。访问结束后，对S做V操作，释放临界资源。

S的取值范围为(-1,0,1)。当S=1，表示两个进程都未进入临界区；S=0，表示有一个进程进入临界区；S=-1，表示有一个进程正在临界区，另一个进程因等待阻塞在阻塞队列，需要当前进程退出时唤醒。

注意：
对不同打临界资源需要设置不同的互斥信号量。
P操作和V操作必须成对出现。
有多少资源就将信号量设为多少。

使用信号量实现同步

为了实现同步，需要设置一个信号量S，初值为0。

若先执行到V操作，则S++后S=1。之后执行P操作，此时有可用资源，S--。P操作后不执行block原语，而是继续往下执行y。

若先执行到P操作，则S--后S=-1，表示此时没有可用资源，P操作会执行block原语阻塞$P_2$。等到$P_1$的语句x执行完后，执行V操作，S++，执行V操作的wakeup原语，唤醒进程继续执行y。

简单总结：在同步问题中，如果某个行为会提供某种资源，则在这个行为之后V这种资源；如果某个行为要用到这个资源，则在这个行为之前P这种资源。在互斥问题中，PV要夹紧使用临界资源的行为，中间不能有冗余代码。

利用信号量实现前驱关系

信号量也可以描述程序或语句之间的前驱关系。

每一对前驱关系都是一个同步问题，要为每一对关系设置一个同步信号量，初值为0。在前驱操作之后V操作，在后继操作之前P操作。

分析进程同步和互斥问题的方法步骤

关系分析。找出问题的进程数并分析他们的同步和互斥关系。
整理思路。确定P操作和V操作的大致顺序。
设置信号量。

2.3.5 经典同步问题

生产者-消费者问题

一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有当缓冲区不满时，生产者才能将消息放入缓冲区；否则必须阻塞，等待消费者从缓冲区中取出消息后将其唤醒。

只有缓冲区不空时，消费者才能从缓冲区取出消息；否则必须等待，等待生产者将消息放入缓冲区后将其唤醒。缓冲区是临界资源。

生产者和消费者对缓冲区互斥访问是互斥关系，同时也是同步关系，生产者生产后，消费者才能消费。
信号量mutex作为互斥信号量，控制互斥访问缓冲池，初值为1；信号量full用于记录当前缓冲池中满缓冲区数（产品数），初值为0；信号量empty用于记录当前缓冲池中的空缓冲区数（空格数），初值为n。

该类问题要注意缓冲区大小为n的处理，当缓冲区有空时，就可以对empty执行P操作，一旦取走一个产品就要执行V操作以释放空闲区。对empty和full的P操作必须放在对mutex的P操作之前。

不可以生产者先执行P(mutex)，再执行P(empty)，消费者执行P(mutex)，再执行P(full)。假设缓冲区已放满，生产者P(empty)阻塞，希望消费者消费，但是信号量被锁，消费者无法操作信号量，也会阻塞，反之亦然。

不过释放信号量时，先释放哪一个都无所谓。

实现互斥的P操作一定要在实现同步的P操作之后，否则可能出现死锁问题。

多生产者-多消费者问题

关系分析。爸爸和妈妈是互斥关系，爸爸和女儿、妈妈和儿子是同步关系。儿子和女儿之间没有互斥和同步关系，因为他们是条件执行，不可能并发。
整理思路。可以抽象成两个生产者和两个消费者被连接到大小为1的缓冲区上。
信号量设置。plate为互斥信号量，表示是否允许向盘子里放入水果，初值为1。apple代表盘子是否有苹果，初值为0。orange表示盘子是否有橘子，初值为0。

图中，dad()和daughter()，mom()和son()必须连续执行，只有在女儿拿走苹果后或儿子拿走橘子后才能释放盘子，即V(plate)。

读者-写者问题

关系分析。读者和写者是互斥的，写者和写者是互斥的，读者和读者不存在互斥。
整理思路。写者与任何进程互斥，使用PV操作即可解决。读者必须实现与写者的互斥同时实现与其他读者的同步。需要一个计数器来判断是否有读者读文件。有读者时，写者无法写。不同读者对计数器的访问也是互斥的。
信号量设置。设置信号量count为计数器，记录当前读者数量，初始值为0；设置mutex为互斥信号量，保护更新count时的互斥；设置互斥信号量rw，用于保证读者和写者的互斥访问。

上面的算法中，读进程都是优先的，存在读进程时写操作会被延迟，只要有一个读进程活跃，后来的读进程都将被允许访问文件。这样可能会导致写进程长时的等待，存在饿死的问题。

若希望写进程优先，应该在读时有写进程访问，直接禁止后续读进程的请求，等待读完直接让写进程执行，等到无写进程执行的情况下才允许读进程再次运行。为此需要增加一个信号量在writer()和reader()函数，并增加对应的PV操作。

写进程优先是相对而言的，称为读写公平法，即读写进程具有一样的优先级。

读者-写者问题有一个关键的特征，即有一个互斥访问的计数器count。遇到不太好解决的同步互斥问题时，要想一想互斥访问的计数器count是否能解决问题。

哲学家进餐问题

关系分析。5名哲学家与左右邻居对中间筷子的访问是互斥关系。
整理思路。关键是如何让一名哲学家拿到左右两根筷子而不死锁。
信号量设置，定义信号量chopstick[5] = {1,1,1,1,1}，用于5根筷子的互斥访问，哲学家编号0-4，哲学家i左边的筷子编号为i，右边的筷子编号为$(i+1)\%5$。

该算法存在问题：所有哲学家都同时拿起左边的筷子，筷子已拿完，出现死锁。

为了防止死锁发生，可对哲学家进程加一些限制：至多允许4名哲学家同时进餐；当一名哲学家两边筷子都可用时才允许它抓起筷子；要求奇数号的哲学家先拿左边的筷子再拿右边的，偶数号相反。

制定的正确规则如下：假设当一名哲学家两边筷子都可用时，才允许它抓起筷子。

哲学家进餐问题的关键在于解决进程死锁。

2.3.6 管程

管程的定义

管程是一种新的进程同步工具，管程的特性保证了进程互斥，无需程序员自己实现互斥，降低了死锁发生的可能。管程还提供了条件变量，让程序员灵活地实现进程同步。

利用共享数据结构抽象地表示系统中的共享资源，而将对该数据结构试试的操作定义为一组过程。这个代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程。

管程定义了一个数据结构和能为并发进程所执行的一组操作，该组操作能同步进程和改变管程中的数据。管程由四部分组成：

管程的名称。
局部于管程内部的共享数据结构说明。
对该数据结构进行操作的一组过程。
对局部于管程内部的共享数据设置初始值的语句。

管程很像一个类。

管程将对共享资源的操作封装起来，内部的共享数据结构只能被管程内的过程所访问。一个进程只有调用管程内的过程才能进入管程访问共享资源。
每次仅允许一个进程进入管程，从而实现进程互斥。只有某个进程运行完它调用的过程后，下一个进程才能开始运行它调用的过程。

条件变量

当一个进程进入后被阻塞，直至阻塞原因解除前，如果该进程不释放管程，其他进程将无法进入管程。

因此将阻塞原因定义为条件变量。管程中设置了多个条件变量，每个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程。对条件变量只能进行wait和signal操作。

x.wait：当x对应的条件不满足，进程调用x.wait将自己插入x条件的等待队列，并释放管程。

x.signal：x对应的条件发生了变化，唤醒一个因x阻塞的进程。

条件变量和信号量的比较：

条件变量的wait/signal操作类似信号量的P/V操作，可以实现进程的阻塞/唤醒。
条件变量是没有值的，仅实现排队等待功能；信号量是有值的，信号量的值反映了剩余资源数。在管程中，剩余资源数用数据结构记录。

2.4 死锁

2.4.1 死锁的概念

死锁的定义

死锁指多个进程因竞争资源而造成的一种僵局，各个进程都被阻塞。

死锁与饥饿

一组进程处于死锁状态指组内的每个进程都在等待一个事件，而这个事件只可能由组内的另一个进程产生。

饥饿指的是进程在信号量内无穷等待的情况。

产生饥饿的主要原因是：多个进程申请某类资源时，有的分配策略是不公平的，不能保证等待时间上界的存在。即使系统未发生死锁，某些进程也要长时间等待。等待时间给进程的推进带来明显影响时称发生了饥饿。饥饿不代表系统一定死锁，但至少有一个进程的执行被无限期推迟。

死锁和饥饿的共同点是进程都无法顺利向前推进的现象。

主要差别：

发生饥饿的进程可以只有一个；发生死锁的进程必然大于等于两个。
发生饥饿的进程可能处于就绪态（长时间得不到CPU），也可能处于阻塞态；发生死锁的进程必定处于阻塞态。

死锁产生的原因

系统资源的竞争。系统中拥有的不可剥夺资源数量不满足多个进程运行的需要，由于争夺资源陷入僵局。对可剥夺资源的竞争（CPU和主存）是不会引起死锁的。
进程推进顺序非法。请求和释放资源顺序不当也会导致死锁。
信号量使用不当也会造成死锁。进程间彼此等待对方发来的消息也会导致进程无法推进。

死锁产生的必要条件

互斥条件。进程要求对资源进行排他性使用，一段时间内资源只能为一个进程拥有，其他请求进程必须等待。
不可剥夺条件。进程获得的资源释放之前，不能被其他进程强行夺走。
请求并保持条件。进程已经保持了至少一个资源，又提出了新的资源请求，而这个资源在别的进程手上，请求进程被阻塞，但又对自己获得的资源保持不放。
循环等待条件。存在一种进程资源的循环等待链。

产生死锁必须同时满足以上四个条件，任一条件不成立，死锁就不会发生。

死锁的等待环要求$P_i$等待的资源必须由$P_{i+1}$来满足，而循环等待条件无此限制，因此循环等待只是死锁的必要条件。

死锁的处理策略

死锁预防。破坏死锁4个必要条件中的一个或几个。
避免死锁。在资源的动态分配过程中，用某种方法防止系统进入不安全状态。
死锁的检测与解除。允许发生死锁，通过死锁的检测机构检测死锁的发生，然后采取某种措施解除死锁。

预防死锁和避免死锁都属于实现预防策略。预防死锁的限制条件比较严格，实现较为简单，但往往系统的效率低，资源利用率低；避免死锁的限制条件比较宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来比较复杂。

2.4.2 死锁预防

破坏互斥条件

大部分资源本来就无法同时访问，破坏互斥条件而预防死锁的办法不太可行。

可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备，在各进程看来，自己对独占资源的使用请求立即被接收处理了，不需要再阻塞等待。

破坏不可剥夺条件

当一个已经保持了不可剥夺资源的进程，请求新的资源得不到满足，它必须释放已经保持的所有资源，待以后需要时再重新申请，从而破坏不可剥夺条件。

该策略实现起来比较复杂，释放资源可能使前一阶段的工作失效，这种方法主要常用于状态易于保存和回复的资源，比如CPU寄存器和内存资源，一般不能用于打印机之类的资源。反复地申请和释放资源既影响进程推进速度，又增加系统开销，从而降低系统吞吐量。

破坏请求并保持条件

要求进程在请求资源时不能持有不可剥夺资源。可通过两种方法实现：

采用预先静态分配方法，进程在运行前一次申请完它所需要的全部资源。在它的资源未满足前，不让他投入运行。在运行的期间，进程不会再提出资源请求，从而破坏请求条件。在等待期间，进程不占有任何资源，从而破坏等待条件。
允许进程只获得初期所需的资源后，便可开始运行。进程在运行过程中再逐步释放已分配给自己且已使用完毕的全部资源后，才能请求新的资源。

方法1的实现简单，但是系统资源被严重浪费，有些资源可能仅在运行初期或快结束使用，而且容易导致饥饿。方法2改进了这些缺点。

破坏循环等待条件

可以采用顺序资源分配法。首先给系统中的各类资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。

一个进程在已经占有小编号的资源时，才有资格申请更大编号的资源。已持有大编号资源的进程不可能逆向申请小编号的资源，不会产生循环等待条件。

缺点：

编号必须相对稳定，不便于增加新类型设备。
进程实际使用资源的顺序可能还是和编号的次序不一致，造成资源的浪费。
必须按规定次序申请资源，为用户编程带来麻烦。

2.4.3 死锁避免

避免死锁同样属于事先预防策略，在每次分配资源的过程中，分析此次分配是否会带来死锁风险。只有不产生死锁的情况下才会分配资源。这种方法施加的限制条件较弱，可以获得较好的系统性能。

系统安全状态

系统进行资源分配之前，计算此次分配的安全性。如果此次分配导致系统进入不安全状态，则不允许分配，让进程等待。

安全状态指系统能按某种推进顺序为每个进程分配所需的资源，直到满足每个进程对资源的最大需求。此时称这个推进顺序为安全序列（可能有多个）。如果找不到安全序列，就称处于不安全状态。

如果系统处于安全状态，则一定不会发生死锁；如果处于不安全状态，则有可能发生死锁。

银行家算法

银行家算法是最著名的死锁避免算法。

进程运行之前先声明对各类资源的最大需求量，其数目应该不超过系统的资源总量。进程在运行中申请资源时，系统必须确定是否有足够长的资源分配给该进程。若有，再进一步试探，将这些资源分配给进程后是否会使系统处于不安全状态，如果不会，才将资源分配给它。

数据结构描述

假设系统中有n个进程，m类资源。

可利用资源向量Available：含有m个元素的数组，每个元素代表一类可用的资源数目。Available[j] = K代表系统中有K个$R_j$类资源可用。
最大需求矩阵Max：$n\times m$矩阵，定义系统中n个进程中的每个进程对m类资源的最大需求。Max[i,j] = K代表进程$P_i$需要$R_j$类资源的最大数目为K。
分配矩阵Allocation：$n\times m$矩阵，定义系统中每类资源当前已经分配给每个进程的资源数。Allocation[i,j] = K表示进程$P_i$当前已经分得$R_j$类资源的数目为K。
需求矩阵Need：$n\times m$矩阵，表示每个进程接下来还需要多少资源。Need[i,j] = K表示进程$P_i$还需要$R_j$类资源的数目为K。

由此可知：
$$
Need = Max – Allocation
$$
通常Max矩阵和Allocation矩阵是已知条件，求出Need矩阵是解题第一步。

算法描述

设$Request_i$是进程$P_i$的请求向量，$Request_i[j] = K$表示进程$P_i$需要j类资源K个。当$P_i$发出资源请求后，系统进行检查：

如果$Request_i[j] <= Need[i,j]$，则转向步骤2；否则认为出错。
如果$Request_i[j] <= Available[i,j]$，则转向步骤3；否则表示尚无足够资源，必须等待。
系统试探将资源分配给$P_i$，并修改：
$$
\begin{aligned}
Available &= Available-Request_i; \
Allocation[i,j] &= Allocation[i,j]+Request_i[j]; \
Need[i,j] &= Need[i,j] – Request_i[j]
\end{aligned}
$$
系统执行安全性算法，检查执行本次分配后，系统是否处于安全状态。若安全才分配；否则本次试探作废，恢复原来的分配状态，让$P_i$等待。

安全性算法

设置工作向量Work，表示系统中的剩余可用资源数目，它有m个元素，在执行算法之前，令Work = Available。

初始时安全序列为空。
从Need矩阵找到符合条件的行：该行不在安全序列中，且该行小于或等于Work向量，找到后，将对应的进程加入安全队列；若找不到，则执行步骤4。
进程$P_i$进入安全序列后，可顺利执行，直至完成，并释放给它的资源，Work = Work + Allocation[i]，返回步骤2。
此时安全序列中已有所有进程，则处于安全状态，否则处于不安全状态。

安全性算法举例

银行家算法举例

2.4.4 死锁检测和解除

如果系统在为进程分配资源的时候不采取任何预防或避免措施，应该提供死锁检测和解除的手段。

死锁检测

死锁避免需要知道进程从开始到结束的所有资源请求。死锁检测检测某个时候是否发生死锁，只需要知道对应时刻的资源请求。

可以用资源分配图来检测系统所处的状态是否为死锁状态。用圆圈表示一个进程，用框表示一类资源。由于一种类型的资源可能有多个，因此用一个框中的一个圆表示一类资源中的一个资源。

从进程到资源有向边称为请求边，表示该进程申请一个单位的该类资源；从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程。

简化资源分配图可以检测系统状态S是否为死锁状态。

找出既不阻塞又不孤立的进程$P_i$。消去它的所有请求边和分配边，使之称为孤立的节点。
进程$P_i$释放资源后，可能可以唤醒某些等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程，如果能消去图中所有的边，则称该图是可完全简化的。

S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的，该条件称为死锁定理。

用死锁定理简化后，还有边相连的进程就是死锁进程。

死锁解除

资源剥夺法。挂起某些死锁进程，并抢占它的资源，分配给其他死锁的进程。但是要防止被挂起的进程长时间得不到资源而处于匮乏状态。
撤销进程法。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销的代价高低进行。这种方法实现比较简单，但是代价可能很高。
进程回退法。让一个或多个进程回退到足以回避死锁的地步，回退时，进程自愿释放而非被剥夺。要求系统保持进程的历史信息，设置还原点。