408 操作系统 知识点记忆（2）进程与线程

前言

本文基于王道考研《操作系统考研复习指导》与汤小丹《计算机操作系统》（第4版）教材内容，结合 408 考研大纲，系统梳理进程与线程的核心知识记忆点和框架，既为个人复习沉淀思考，亦希望能与同行者互助共进。

本章是全课程的核心与难点，围绕“并发”二字展开，主线是：用进程与线程描述程序的执行，用调度决定谁上 CPU，用同步与互斥保证正确性，用死锁处理解决资源竞争的失控。

核心知识记忆点+理解性说明

第二章 进程与线程

1. 进程与线程

A. 进程与线程的基本概念

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

进程的特征：动态性+并发性+独立性+异步性+结构性

进程：更好地使多道程序并发执行，提高资源利用率和系统吞吐量
线程：减少程序在并发执行时所付出的时空开销，提高操作系统的并发性能 轻量级线程基本CPU执行单元 程序执行流最小单元
线程ID，程序计数器，寄存器集合，堆栈
进程的一个实体，系统独立调度、分派的基本单位
就绪（已具备各种执行条件、只需再获得CPU）、阻塞（因某事受阻处于暂停状态）、运行状态线程状态与转换 +图

线程属性：

1. 线程是一个轻型实体，它不拥有系统资源，但每个线程都应有一个唯一的标识符和一个线程控制块，线程控制块记录线程执行的寄存器和栈等现场状态。
2. 不同的线程可以执行相同的程序，即同一个服务程序被不同的用户调用时，操作系统将它们创建成不同的线程。
3. 同一进程中的各个线程共享该进程所拥有的资源。
4. 线程是CPU的独立调度单位，多个线程是可以并发执行的。在单CPU的计算机系统中，各线程可交替地占用CPU;在多CPU的计算机系统中，各线程可同时占用不同的CPU，若各个CPU同时为一个进程内的各线程服务，则可缩短进程的处理时间。
5. 一个线程被创建后，便开始了它的生命周期，直至终止。线程在生命周期内会经历阻塞态、就绪态和运行态等各种状态变化。

进程和线程比较

1. 调度。在传统的操作系统中，拥有资源和独立调度的基本单位都是进程，每次调度都要进行上下文切换，开销较大。在引入线程的操作系统中，线程是独立调度的基本单位，而线程切换的代价远低于进程。在同一进程中，线程的切换不会引起进程切换。但从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
2. 并发性。在引入线程的操作系统中，不仅进程之间可以并发执行，一个进程中的多个线程之间也可并发执行，甚至不同进程中的线程也能并发执行，从而使操作系统具有更好的并发性，提高了系统资源的利用率和系统的吞吐量。
3. 拥有资源。进程是系统中拥有资源的基本单位，而线程不拥有系统资源（仅有一点必不可少、能保证独立运行的资源），但线程可以访问其隶属进程的系统资源，这主要表现在属于同一进程的所有线程都具有相同的地址空间。要知道，若线程也是拥有资源的单位，则切换线程就需要较大的时空开销，线程这个概念的提出就没有意义。
4. 独立性。每个进程都拥有独立的地址空间和资源，除了共享全局变量，不允许其他进程访问。某个进 程中的线程对其他进程不可见。同一进程中的不同线程是为了提高并发性及进行相互之间的合作而创建的，它们共享进程的地址空间和资源。5)系统开销。在创建或撤销进程时，系统都要为之分配或回收进程控制块(PCB)及其他资源，如内存空间、I/O设备等。操作系统为此所付出的开销，明显大于创建或撤销线程时的开销。类似地，在进程切换时涉及进程上下文的切换，而线程切换时只需保存和设置少量寄存器内容，开销很小。此外，同一进程内的多个线程共享进程的地址空间，因此这些线程之间的同步与通信非常容易实现，甚至无须操作系统的干预。
5. 支持多处理器系统。对于传统单线程进程，不管有多少个CPU，进程只能运行在一个CPU上。对于多线程进程，可将进程中的多个线程分配到多个CPU上执行。

B. 进程/线程的状态与转换

进程创建 父进程创建子进程

终端用户登录、作业调度、系统提供服务、用户程序应用请求创建进程

1. 为新进程分配一个唯一的进程标识号，并申请一个空白PCB（PCB是有限的）。若PCB申请失败，则创建失败。
2. 为进程分配其运行所需的资源，如内存、文件、I/O设备和CPU时间等（在PCB中体现）。这些资源或从操作系统获得，或仅从其父进程获得。若资源不足（如内存），则并不是创建失败，而是处于创建态，等待内存资源。
3. 初始化PCB，主要包括初始化标志信息、初始化CPU状态信息和初始化CPU控制信息，以及设置进程的优先级等。4)若进程就绪队列能够接纳新进程，则将新进程插入就绪队列，等待被调度运行。

进程终止 正常结束；异常结束；外界干预

1. 根据被终止进程的标识符，检索出该进程的PCB，从中读出该进程的状态。2)若被终止进程处于运行状态，立即终止该进程的执行，将CPU资源分配给其他进程。3)若该进程还有子孙进程，则通常需将其所有子孙进程终止（有些系统无此要求）。4)将该进程所拥有的全部资源，或归还给其父进程，或归还给操作系统。
2. 将该PCB从所在队列（链表）中删除。
   级联终止：一个进程终止，其所有子进程都终止

运行态
就绪态：仅缺少CPU，可剥夺更高优先级，运行态——>就绪态
阻塞态/等待态：需要其他资源（除了CPU）/等待某一事件（eg：I/O操作）
创建态
终止态

进程阻塞与唤醒 该对原语成对使用
阻塞原语 运行态 主动

1. 找到将要被阻塞进程的标识号(PID)对应的PCB。
2. 若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行。3)将该PCB插入相应事件的等待队列，将CPU资源调度给其他就绪进程。唤醒原语
3. 在该事件的等待队列中找到相应进程的PCB。
4. 将其从等待队列中移出，并置其状态为就绪态。
5. 将该PCB插入就绪队列，等待调度程序调度。

进程创建时，操作系统为它新建一个PCB，该结构之后常驻内存，进程存在的唯一标志
包括：
进程描述信息：进程标识符PID，用户标识符UID
进程控制和管理信息：进程当前状态、进程优先级、代码运行入口地址、程序外存地址、进入内存时间、CPU占用时间、信号量使用资源分配清单：代码段指针，数据段指针，堆栈段指针，文件描述符，键盘，鼠标
处理器相关信息：通用寄存器值、地址寄存器值、控制寄存器值、标志寄存器值
程序段 能被进程调度程序调度到CPU执行的程序代码段
数据段 进程对应的程序加工处理的原始数据，程序执行时产生的中间或者最终结果

C. 线程的实现：内核支持的线程，线程库支持的线程

线程控制块TCB：线程标识符；一组寄存器；线程运行状态；优先级；专有存储区；堆栈指针

线程的实现方式
用户级线程ULT 线程管理在用户态完成，无需操作系统干预 调度以进程为单位划分时间片
内核级线程KLT 同一进程中线程切换：用户态——>核心态 开销大
组合方式

线程库
1在用户空间中提供了一个没有内核支持的库 本地函数调用2实现由操作系统直接支持的内核级的一个库 系统调用

多线程类型
1 多对一模型2 一对一模型3 多对多模型 $n\ge m$

D. 进程与线程的组织与控制

E. 进程间通信：共享内存，消息传递，管道，信号

进程通信：进程之间信息交换
高级通信 较高速率传输大量数据
共享存储：通信进程之间存在一块可直接访问的共享空间
低级方式：基于数据结构
高级方式：基于存储区
消息传递：格式化消息为单位 发送消息和接收消息 两原语
直接通信方式 进程 和进程
间接通信方式 发送进程将消息发送到某个中间实体（信箱） 可以多个进程位于同一信箱send/receive消息P—（从右往左取数据）— <—（从右往左取数据）— Q
管道通信 管道（pipe文件） 在内存中开辟一个大小固定的内存缓冲池
+图 生产者消费者方式通信
互斥、同步确认对方存在
管道：限制管道大小，读进程可能工作得比写进程快，只能由创建进程访问
信号：用于通知进程发生了某个事件的机制 内核给某个进程发送信号 一个进程给另一个进程发送信号信号的处理方式：执行默认的信号处理程序
执行进程定义的信号处理程序

2. CPU调度与上下文切换

A. 调度的基本概念

CPU三级调度
高级调度（作业调度） 外存上处于后备队列作业中挑选
外存与辅存之间的调度
中级调度（内存调度）暂时不能运行的进程调至外存等待，挂起态决定将外存中挂起进程重新调入内存存储器管理的对换功能
低级调度（进程调度）
从就绪队列中选取一个进程，将CPU分配给它
联系

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

调度程序（调度器）：调度和分派CPU的组建
排队器+分派器+上下文切换器

1. 排队器。将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便于调度程序选择。每当有一个进程转变为就绪态时，排队器便将它插入相应的就绪队列。
2. 分派器。依据调度程序所选的进程，将其从就绪队列中取出，将CPU分配给新进程。
3. 上下文切换器。在对CPU进行切换时，会发生两对上下文的切换操作：第一对，将当前进程的上下文保存到其PCB中，再装入分派程序的上下文，以便分派程序运行；第二对，移出分派程序的上下文，将新选进程的CPU现场信息装入CPU的各个相应寄存器。在上下文切换时，需要执行大量load和store指令，以保存寄存器的内容，因此会花费较多时间。现在已有硬件实现的方法来减少上下文切换时间。通常采用两组寄存器，其中一组供内核使用，一组供用户使用。这样，上下文切换时，只需改变指针，让其指向当前寄存器组即可。

现代操作系统中，应该进行进程调度与切换的情况如下：

1. 创建新进程后，父进程和子进程都处于就绪态，因此需要决定是运行父进程还是运行子进程，调度程序可以合法地决定其中一个进程先运行。
2. 进程正常结束或异常终止后，必须从就绪队列中选择某个进程运行。若没有就绪进程，则通常运行一个系统提供的闲逛进程。3)当进程因I/O请求、信号量操作或其他原因此被阻塞时，必须调度其他进程运行。
3. 当I/O设备准备就绪后，发出I/O中断，原先等待I/O的进程从阻塞态变为就绪态，此时需要决定是让新的就绪进程投入运行，还是让中断发生时运行的进程继续执行。

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

1. 在处理中断的过程中。中断处理过程复杂，在实现上很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺CPU资源。
2. 需要完全屏蔽中断的原子操作过程中。如加锁、解锁、中断现场保护、恢复等原子操作。在原子过程中，连中断都要屏蔽，更不应该进行进程调度与切换。

B. 调度的目标

调度评价标准
CPU利用率 CPU有效工作时间/工作+空闲时间系统吞吐量
周转时间 作业完成时间-作业提交时间
平均周转时间 作业周转时间/总个数
带权周转时间 作业周转时间/作业实际运行时间平均带权周转时间 带权周转时间/总个数
等待时间
响应时间 从用户提交请求到系统首次产生响应所用时间

C. 调度的实现：调度器/调度程序(scheduler)，调度的时机与调度方式（抢占式/非抢占式），闲逛进程，内核级线程与

用户级线程调度

进程调度方式：非抢占调度方式（非剥夺方式）早期批处理，不用于分时、实时系统 抢占方式（剥夺方式）

用户级线程调度 线程切换在同一进程进行，仅需少量机器指令内核级线程调度 需要完整上下文切换，修改内存映像，使高速缓存失效

D. CPU调度算法

CPU调度算法
FCFS 先来先服务
SJF 短作业优先
高响应比优先调度 等待时间+要求服务时间/要求服务时间
优先级调度 非抢占式 抢占式
操作系统更偏向I/O型进程 静态优先级 动态优先级 系统>用户 交互>非交互 I/O>计算CPU 计算型
RR时间片轮转 就绪队列按照FCFS排列
一个时间片尚未用完而当前进程已完成，调度程序立即激活
一个时间片用完，产生一个时钟中断，时钟中断处理程序激活调度程序

多级队列调度算法 unix

1. 设置多个就绪队列，并为每个队列赋予不同的优先级。第1级队列的优先级最高，第2级队列的优先级次之，其余队列的优先级逐个降低。
2. 赋予各个队列的进程运行时间片的大小各不相同。在优先级越高的队列中，每个进程的时间片就越小。例如，第i+1级队列的时间片要比第i级队列的时间片长1倍。
3. 每个队列都采用FCFS算法。新进程进入内存后，首先将它放入第1级队列的末尾，按FCFS原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。若它在一个时间片结束时尚未完成，调度程序将其转入第2级队列的末尾等待调度；若它在第2级队列中运行一个时间片后仍未完成，再将它放入第3级队列，以此类推。当进程最后被降到第n级队列后，在第n级队列中便采用时间片轮转方式运行。
4. 按队列优先级调度。仅当第1级队列为空时，才调度第2级队列中的进程运行；仅当第1~i-1级队列均为空时，才会调度第i级队列中的进程运行。若CPU正在执行第i级队列中的某个进程时，又有新进程进入任何一个优先级较高的队列，此时须立即将正在运行的进程放回到第i级队列的末尾，而将CPU分配给新到的高优先级进程。

E. 多处理机调度

非对称多处理机(Asymmetric MultiProcessing,AMP)大多采用主从式操作系统，内核驻留在主机上，而从机上只运行用户程序，进程调度由主机负责。当从机空闲时，便向主机发送一个索求进程的信号，在主机中有一个就绪队列，只要队列不为空，主机便从队首摘下一个进程分配给索求进程的从机。这种分配方式实现简单，缺点是主机太忙，容易成为系统瓶颈。
对称多处理机(Symmetric MultiProcessing,SMP)的所有处理机都是相同的，因此由调度程序将任何一个进程分配给任何一个CPU。

亲和性 系统应尽量避免将进程从一个CPU移到另一个CPU，而应试图让一个进程运行在同一个CPU上负载均衡 对于SMP系统，应尽量保证所有CPU的负载平衡（也称负载均衡），以便充分利用多处理机的优点

多处理机调度方案
公共就绪队列 所有CPU共享同一个就绪队列
软亲和是指由调度程序尽量保持一个进程到某个CPU上，但这个进程也可以迁移到其他CPU上
硬亲和是指由用户进程通过系统调用，主动请求系统分配到固定的CPU上
私有就绪队列 系统为每个CPU设置一个私有就绪队列 必须进行负载均衡
对于推迁移，一个特定的系统程序周期性检查每个CPU的负载，若发现不平衡，则从超载CPU的就绪队列中“推”一些进程到空闲CPU的就绪队列，从而平均分配负载。若一个CPU负载很低，则从超载CPU的就绪队列中“拉”一些进程到自己的就绪队列，发生拉迁移。在系统中，推迁移和拉迁移常被并行实现。

F. 上下文及其切换机制

切换CPU到另一个进程需要保存当前进程状态并恢复另一个进程的状态，这个任务称为上下文切换。进程上下文采用进程PCB表示，包括CPU寄存器的值、进程状态和内存管理信息等。当进行上下文切换时，内核将旧进程状态保存在其PCB中，然后加载经调度而要执行的新进程的上下文。在切换过程中，进程的运行环境产生实质性的变化。上下文切换的流程如下：

1. 挂起一个进程，将CPU上下文保存到PCB，包括程序计数器和其他寄存器。
2. 将进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列。
3. 选择另一个进程执行，并更新其PCB。
4. 恢复新进程的CPU上下文。
5. 跳转到新进程PCB中的程序计数器所指向的位置执行。

模式切换与上下文切换是不同的，模式切换时，CPU逻辑上可能还在执行同一进程。用户进程最开始都运行在用户态，若进程因中断或异常进入内核态运行，执行完后又回到用户态刚被中断的进程运行。用户态和内核态之间的切换称为模式切换，而不是上下文切换，因为没有改变当前的进程。上下文切换只能发生在内核态，它是多任务操作系统中的一个必需的特性。

3. 同步与互斥

A. 同步与互斥的基本概念

临界资源：一次只允许一个进程使用的资源 互斥访问临界资源的访问过程：
进入区 “上锁”
临界区/临界段 访问临界资源的代码
退出区 “解锁”
剩余区 其余部分

为禁止两个进程同时进入临界区，同步机制应遵循以下准则：

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

同步：直接制约关系 互斥：间接制约关系

B. 基本的实现方法：软件方法；硬件方法

软件实现方法
单标志检查法 turn 表示允许进入临界区的进程编号，但两进程必须交替进入临界区，违背空闲让进双标志先检查法 flag[2] $flag[i]=true$ $P_i$ 想进入临界区 先检查对方，再设置自己，可能同时进入，违背忙则等待双标志后检查法 先设置自己，再检查对方，可能同时进入不了，违背空闲让进，有限等待
Peterson算法 设置flag和turn 未遵循让权等待

硬件实现方法
中断屏蔽方法 不适合多处理机，只适合操作系统内核进程，不适合于用户进程
硬件指令方法 TestAndSet指令 读出指定标志后将标志设置为真
boolean TestAndSet (boolean lock) {
boolean old;
old = lock;
*lock=true;
return old;
}
进程在进入临界区之前，先用TS指令检查lock值：
1 若为false,则表示没有进程在临界区，可以进入，并将lock置为true,这意味着关闭了临界资源（加锁），使任何进程都不能进入临界区；2 若为true,则表示有进程在临界区，进入循环等待，直到当前访问临界区的进程退出时解锁（将lock置为false）。
利用TS指令实现互斥的过程描述如下：
while TestAndSet (&lock);
进程的临界区代码段；
lock=false;
进程的其他代码；
硬件指令方法 Swap指令 交换两个字（字节）的内容
Swap (boolean *a, boolean b) {
boolean temp = a;

• a =* b;
• b=temp;
  }
  过程描述如下：
  boolean key=true;
  while (key != false)
  Swap (&lock, &key) ;
  进程的临界区代码段；
  lock=false;
  进程的其他代码；
  适合多处理机
  1 等待进入临界区的进程会占用CPU执行while循环，不能实现“让权等待”；
  2 从等待进程中随机选择一个进程进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

C. 锁；信号量；条件变量

互斥锁 一个进程在进入临界区时调用acquire()函数，以获得锁；在退出临界区时调用 release()函数，以释放锁。每个互斥锁有一个布尔变量available,表示锁是否可用。若锁是可用的，则调用 acquire()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。
上面描述的互斥锁也称自旋锁，其主要缺点是忙等待，当有一个进程在临界区时，任何其他进程在进入临界区前必须连续循环调用acquire()。类似的还有前面介绍的单标志法、TS指令和Swap指令。当多个进程共享同一CPU时，这种连续循环显然浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上旋转，而不影响其他线程的执行。

原语：完成某种功能且不被分割，不被中断执行操作序列，通常可由硬件实现

信号量 wait（） P（） P操作
signal（） V（） V操作
整型信号量：初始化 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 § ;
}
}

使多个进程能互斥访问某个临界资源，需要为该资源设置一个互斥信号量S，初值为1（可用资源数为1）
S的取值范围为(-1,0,1)。
当 $S=1$ 时，表示两个进程都未进入临界区；
当 $S=0$ 时，表示有一个进程已进入临界区；
当 $S=-1$ 时，表示有一个进程正在临界区，另一个进程因等待而阻塞在阻塞队列中，需要被当前已在临界区运行的进程退出时唤醒。同步 同步信号量S初值为0

管程：代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序保证进程互斥，程序员无法自己实施，降低死锁可能性
高级同步机制，类似类

1. 管程的名称；
2. 局部于管程内部的共享数据结构说明；
3. 对该数据结构进行操作的一组过程（或函数）；
4. 对局部于管程内部的共享数据设置初始值的语句。
   monitor Demo{
   共享数据结构S；
   init_code（）{
   S=S；
   }
   take_away(){
   S–;
   ……
   }
   give_back(){
   S++;
   ……
   }
   }
   管程将对共享资源的操作封装起来，每次仅允许一个进程进入管理，从而实现进程互斥
   管程的基本特征：
5. 局部于管程的数据只能被局部于管程的过程所访问
6. 一个进程只有通过管程内的过程才能进入管程访问共享数据
7. 每次仅允许一个进程在管程内执行某个内部过程，编译器负责实现各进程互斥进入管程中的过程
   eg：Java 中的Synchronized 每次只能有一个线程进入函数
   x.wait:当x对应的条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程。此时其他进程可以使用该管程。
   x.signal:x对应的条件发生了变化，则调用x.signal,唤醒一个因x条件而阻塞的进程。
   下面给出条件变量的定义和使用：
   monitor Demo {
   共享数据结构 S;
   condition x;
   init code () {}
   take away () {
   if (S <= 0) x.wait();
   资源足够，分配资源，做一系列相应处理；
   give back () {
   归还资源，做一系列相应处理；
   if（有进程在等待）x.signal();//唤醒一个阻塞进程
   }
   相似点：条件变量的wait/signal操作类似于信号量的P/V操作，可以实现进程的阻塞/唤醒。
   不同点：条件变量是“没有值”的，仅实现了“排队等待”功能；而信号量是“有值”的,
   信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。

D. 经典同步问题：生产者-消费者问题，读者-写者问题；哲学家进餐问题

生产者-消费者问题
生产者、消费者共享初值为空，大小为n的缓冲区缓冲区没满——>生产者生产
缓冲区没空——消费者消费
缓冲区满——>生产者必须等待
缓冲区空——>消费者必须等待
semaphore mutex=1;
semaphore empty=n;
semaphore full=0;
producer () {
while (1) {
生产一个产品
P (empty) ;
P (mutex) ;
将产品放入缓冲区
V (mutex) ;
V(full);
}
}
consumer () {
while (1) {
P(full);
P (mutex) ;
从缓冲区中取出一个产品
V (mutex) ;
V (empty) ;
消费产品
}
}

互斥：缓冲区（盘子）访问
同步：苹果——>女儿取
橘子——>儿子取
盘子空——>放水果
plate盘子可以放的水果数量
mutex 互斥访问盘子（这里 $plate=1$ 不设置，也可正常实现）缓冲区数量大于1，设置访问互斥量semaphore $plate=1,apple=0,orange=0$;
dad () {
while (1) {
准备一个苹果
P (plate);
把苹果放入盘子
V(apple) ;
}
}
mom () {
while (1) {
准备一个橘子
P (plate);
把橘子放入盘子
V (orange) ;
}
}
son () {
while (1) {
P (orange);
从盘子中取出橘子
V (plate);
吃掉橘子
}
}
daughter () {
while (1) {
P (apple);
从盘子中取出苹果
V (plate) ;
吃掉苹果
}
}

读者、写者问题
允许多个读者同时读
只允许一个写者写
任意写者完成操作之前不允许读者读写者写操作之前，读者和写者全部退出互斥：写进程和写进程
写进程和读进程
读进程和读进程不存在互斥访问int $count=0$;
semaphore mutex=1;
semaphore rw=1;
★★★semaphore w=1; //写进程优先writer () {
while (1) {
★★★P(w);
P(rw) ;
写文件
V(rw) ;
★★★V(w);
}
}
reader () {
while (1) {
★★★P(w);
P (mutex) ;
if (count == 0)
P (rw) ;
count++;
V (mutex) ;
★★★V(w);
读文件
P (mutex) ;
count --;
if (count == 0)
V(rw) ;
V (mutex) ;
}
}

吸烟者问题
可生产多种产品的单生产者 多消费者烟草、纸、胶水
组合1 纸+胶水——>抽烟者1
2 烟草＋胶水—— 2
3 烟草+纸—— 3
桌子可抽象为容量1的缓冲区 互斥访问provider（）{
while(1){
if i==0
将组合1放在桌子上
V（offer1）；
}
i=(i+1)%3;
P(finish);
}
Smoker1(){
while(1){
P(offer1);
从桌上拿走组合；
V(finish);
}
}

哲学家就餐问题
semaphore chopstick [5]={1,1,1,1,1};semaphore mutex=1;
Pi () {
do {
P (mutex) ;
P(chopstick [i]);
P(chopstick[ (i+1) %5]);V (mutex) ;
进餐
V (chopstick [i]) ;
V(chopstick[ (i+1) %5]);思考
}while (1);
}

4. 死锁

A. 死锁的基本概念

死锁：多个进程因竞争资源而造成的一种僵局（互相等待对方手里的资源），使得各个进程都被阻塞，若无外力干涉，这些进程都无法向前推进。

死锁和饥饿的主要差别：

1. 发生饥饿的进程可以只有一个；而死锁是因循环等待对方手里的资源而导致的，因此，若有死锁现象，则发生死锁的进程必然大于或等于两个。
2. 发生饥饿的进程可能处于就绪态（长期得不到CPU，如SJF算法的问题），也可能处于阻塞态（如长期得不到所需的I/O设备）；而发生死锁的进程必定处于阻塞态。

死锁产生的原因 系统资源的竞争 进程推进顺序不合理
产生的必要条件： 互斥条件 不可剥夺条件 请求并保持和 循环等待（发生死锁必定有）

B. 死锁预防

死锁预防
破坏互斥条件 只能互斥使用的资源改造为允许共享使用
不可剥夺 用于状态易于保存、恢复的资源 eg CPU寄存器、内存资源
请求并保持条件 请求资源时，不能持有不可剥夺的资源

1. 采用预先静态分配方法
2. 允许进程只获得初期所需资源，可开始运行进程在运行过程中逐步释放已分配给自己且已使用完毕的全部资源后，才能请求新的资
   源
   循环等待条件 顺序资源分配法 给系统各类资源编号，规定每个进程必须按编号递增顺序请求资源

C. 死锁避免

D. 死锁检测和解除

死锁检测 资源分配图 请求边 分配边
死锁解除 资源剥夺法 撤销进程法 进程回退法 挂起（暂时放在外存） 终止进程法

总结（本章速记）

本章知识骨架：

• 1. 进程与线程
  • A. 进程与线程的基本概念
  • B. 进程/线程的状态与转换
  • C. 线程的实现：内核支持的线程，线程库支持的线程
  • D. 进程与线程的组织与控制
  • E. 进程间通信：共享内存，消息传递，管道，信号
• 2. CPU调度与上下文切换
  • A. 调度的基本概念
  • B. 调度的目标
  • C. 调度的实现：调度器/调度程序(scheduler)，调度的时机与调度方式（抢占式/非抢占式），闲逛进程，内核级线程与
    用户级线程调度
  • D. CPU调度算法
  • E. 多处理机调度
  • F. 上下文及其切换机制
• 3. 同步与互斥
  • A. 同步与互斥的基本概念
  • B. 基本的实现方法：软件方法；硬件方法
  • C. 锁；信号量；条件变量
  • D. 经典同步问题：生产者-消费者问题，读者-写者问题；哲学家进餐问题
• 4. 死锁
  • A. 死锁的基本概念
  • B. 死锁预防
  • C. 死锁避免
  • D. 死锁检测和解除

关键速记清单：

• 进程是一个正在执行程序的实例。
• 进程的特征：动态性+并发性+独立性+异步性+结构性
• 进程：更好地使多道程序并发执行，提高资源利用率和系统吞吐量
• 线程ID，程序计数器，寄存器集合，堆栈
• 进程的一个实体，系统独立调度、分派的基本单位
• 线程属性：
• 同一进程中的各个线程共享该进程所拥有的资源。
• 进程和线程比较
• 进程创建 父进程创建子进程
• 终端用户登录、作业调度、系统提供服务、用户程序应用请求创建进程
• 进程终止 正常结束；异常结束；外界干预
• 将该PCB从所在队列（链表）中删除。
• 级联终止：一个进程终止，其所有子进程都终止
• 就绪态：仅缺少CPU，可剥夺更高优先级，运行态——>就绪态
• 进程阻塞与唤醒 该对原语成对使用
• 阻塞原语 运行态 主动
• 找到将要被阻塞进程的标识号(PID)对应的PCB。
• 在该事件的等待队列中找到相应进程的PCB。
• 将其从等待队列中移出，并置其状态为就绪态。
• 将该PCB插入就绪队列，等待调度程序调度。
• 进程描述信息：进程标识符PID，用户标识符UID
• 程序段 能被进程调度程序调度到CPU执行的程序代码段
• 线程的实现方式
• 内核级线程KLT 同一进程中线程切换：用户态——>核心态 开销大
• 组合方式
• 多线程类型
• 1 多对一模型2 一对一模型3 多对多模型 $n\ge m$
• 进程通信：进程之间信息交换
• 高级通信 较高速率传输大量数据
• 共享存储：通信进程之间存在一块可直接访问的共享空间
• 低级方式：基于数据结构
• 高级方式：基于存储区
• 消息传递：格式化消息为单位 发送消息和接收消息 两原语
• 直接通信方式 进程 和进程
• 管道通信 管道（pipe文件） 在内存中开辟一个大小固定的内存缓冲池
• +图 生产者消费者方式通信
• 互斥、同步确认对方存在
• 管道：限制管道大小，读进程可能工作得比写进程快，只能由创建进程访问
• 执行进程定义的信号处理程序
• CPU三级调度
• 高级调度（作业调度） 外存上处于后备队列作业中挑选
• 外存与辅存之间的调度
• 低级调度（进程调度）
• 从就绪队列中选取一个进程，将CPU分配给它
• 作业调度为进程活动做准备，进程调度使进程正常活动起来。
• 作业调度次数少，中级调度次数略多，进程调度频率最高。
• 进程调度是最基本的，不可或缺。
• 调度程序（调度器）：调度和分派CPU的组建
• 排队器+分派器+上下文切换器
• 现代操作系统中，应该进行进程调度与切换的情况如下：
• 不能进行进程的调度与切换的情况如下：
• 调度评价标准
• CPU利用率 CPU有效工作时间/工作+空闲时间系统吞吐量
• 周转时间 作业完成时间-作业提交时间
• 平均周转时间 作业周转时间/总个数
• 等待时间
• 响应时间 从用户提交请求到系统首次产生响应所用时间
• CPU调度算法
• FCFS 先来先服务
• SJF 短作业优先

结语

并发是操作系统最迷人也最危险的部分。进程的引入让程序可以“同时”运行，线程的引入让并发粒度更细、切换更轻；调度算法决定谁能占用 CPU，同步机制决定大家同时用时会不会出错，而死锁理论刻画的则是“谁都动不了”的极端困局。复习这一章，建议抓住三条主线：调度关注效率（周转时间、响应时间、吞吐量），同步关注正确性（互斥、临界区、让权等待），死锁关注资源分配的安全性（预防、避免、检测与解除）。信号量与 PV 操作是把这三条主线串起来的通用语言——把生产者-消费者、读者-写者、哲学家进餐三道经典问题各动手写一遍，你会发现它们的差别只在“资源有几个、谁需要几个”。

参考资料

1. 王道考研《操作系统考研复习指导》
2. 汤小丹．计算机操作系统（第4版）．西安：西安电子科技大学出版社
3. Abraham Silberschatz．操作系统概念（Operating System Concepts）．北京：机械工业出版社