操作系统——（2）进程与线程

1 进程的概念、组成、特征

1.1 进程的概念

程序：是静态得到，就是存放在磁盘里的可执行文件，就是一系列的指令集合

进程：是动态的，是程序（同一个程序执行会对应多个进程）的一次执行过程

1.2 进程的组成——PCB

当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的“身份证号”——PID

操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中

PCB信息：

进程标识符

处理机状态

进程调度信息

进程控制信息

PCB的组织方式：

线性方式

链接方式

索引方式

PCB是给操作系统用的；程序段、数据段是给进程自已用的

与进程自身的运行逻辑有关

一个进程实体（进程映像）由PCB、程序段、数据段组成。进程是动态的，进程实体（进程映像）是静态的

进程实体反应了进程在某一时刻的状态

注意：PCB是进程存在的唯一标志

1.3 进程的特征

操作系统的目标：

程序顺序执行：一个较大的程序通常由若干个程序段组成

程序在执行时，必须按照某种先后顺序逐个执行，仅当前一操作执行完后，才能执行后继操作

前趋图：有向无循环图，用于描述进程之间执行的先后顺序；结点表示进程或程序段，有向边表示前驱关系

程序并发执行：采用多道程序技术，将多个程序同时装入内存，使之并发运行

2 进程的状态与转换、进程的组织

2.1 进程的状态

2.1.1 创建态、就绪态

进程正在被创建时，它的状态是“创建态”，在这个阶段操作系统会为进程分配资源、初始化PCB

当进程创建完成后，便进入“就绪态”，处于就绪态的进程已经具备运行条件，但由于没有空闲CPU，就暂时不能运行

2.1.2 运行态

当CPU空闲时，操作系统就会选择一个就绪进程，让它上处理机运行。如果一个进程此时在CPU上运行，那么这个进程处于“运行态”CPU会执行该进程对应的程序（执行指令序列）

2.1.3 阻塞态

在进程运行的过程中，可能会请求等待某个事件的发生（如等待某种系统资源的分配，或者等待其他进程的响应）

在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入“阻塞态”

当CPU空闲时，又会选择另一个“就绪态”进程上CPU运行

2.1.4 终止态

一个进程可以执行exit系统调用，请求操作系统终止该进程。此时该进程会进入“终止态”，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB

当终止进程的工作完成之后，这个进程就彻底消失了

2.2 进程状态的转换

2.3 进程的组织

2.3.1 链式方式

2.3.2 索引方式

3 进程控制

3.1 什么是进程控制？（实现进程状态转换）

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能

3.2 如何实现进程控制？（用“原语”实现）

原语是一种特殊的程序，它的执行具有原子性（可以用“关中断指令”和”开中断指令“这两个特权指令实现原子性）。也就是说，这段程序的运行必须是一气呵成，不可中断

如果不“一气呵成”，就有可能导致操作系统中的某些关键数据结构信息不统一的情况，这会影响操作系统进行别的管理工作

正常情况：CPU每执行完一条指令都会例行检查是否有中断信号需要处理，如果有，则暂停运行当前这段程序，转而执行相应的中断处理程序

CPU执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。这样，关中断、开中断之间的这些指令序列就是不可被中断的，这就实现了“原子性”

3.3 进程控制相关的原语

CPU中会设置很多“寄存器”，用来存放程序运行过程中所需的某些数据

​ PSW：程序状态寄存器

​ PC：程序计数器，存放下一条指令的地址

​ IR：指令寄存器，存放当前正在执行的指令

​ 通用寄存器：其他一些必要信息

4 进程通信

4.1 什么是进程通信？

是指两个进程之间产生数据交互

4.2 为什么进程通信需要操作系统支持?

进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立

为了保证安全，一个进程不能直接访问另一个进程的地址空间

4,3 共享存储

为避免出错，各个进程对共享空间的访问应该是互斥的。各个进程可使用操作系统内核提供的同步互斥工具（例如P、V操作）

4.4 消息传递

进程间的数据交换以格式化的消息为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换

4.4.1 直接通信方式（点名道姓的通信方式）

4.4.2 间接通信方式（以“信箱”作为中间实体进行消息传递）

4.5 管道通信

“管道”是一种特殊的共享文件，又名pipe文件。其实就是在内存中开辟一个大小固定的内存缓冲区

5 线程的概念

5.1 什么是线程，为什么要引入线程？

还没有引入进程之前，系统中各个程序只能串行执行

有的进程可能需要“同时”做很多事，二传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度

传统的进程是程序执行流的最小单位

引入线程后，线程成为了程序需执行流的最小单位

可以把线程理解为“轻量级进程”

线程是一个基本的CPU执行单元，也是程序执行流的最小单位。

引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务；进程只是作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）

5.2 引入线程机制后，有什么变化？

5.3 线程的属性

6 线程的实现方式和多线程模型

6.1 线程的实现方式

6.1.1 用户级线程

历史背景：早期的操作系统只支持进程，不支持线程。当时的“线程”是由线程库实现的。

很多编程语言提供了强大的线程库，可以实现线程的创建、销毁、调度等功能

1.线程的管理工作是由应用程序通过线程库来完成，所有的线程管理工作都由应用程序负责

2.线程切换不需要操作系统干涉，线程切换可以在用户态下即可完成

3.操作系统不能意识到用户级线程的存在，“用户级线程”就是“从用户视角看能看到的线程”

4.优缺点

优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的开销小，效率高

缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行

6.1.2 内核级线程（由操作系统支持的线程）

1.内核级线程的管理工作由操作系统内核完成。
2.线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
3.操作系统会为每个内核级线程建立相应的TCB (Thread Control Block，线程控制块），通过TCB对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”
4.优缺点
优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

6.2多线程模型

在支持内核级线程的系统中，根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型

内核级进程中可以运行任意一个有映射关心的用户级线程代码，只有两个内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞。

7 线程的状态与转换

7.1 线程的组织与控制

8 调度的概念、层次

8.1 高级调度

8.2 中级调度

内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存

暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列

中级调度（内存调度）—— 按照某种策略决定将哪个处于挂起状态的进程重新调入内存

8.3 低级调度

低级调度（进程调度/处理机调度）——按照某种策略从就绪队列中选取一个进程，将处理机分配给它

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度

进程调度的频率很高，一般几十毫秒一次

8.4 进程的挂起态与七状态模型

暂时调到外存等待的进程状态为挂起状态

挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态

五状态模型->七状态模型

9 进程调度的时机、切换与过程调度方式

9.1 进程调度的时机

进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机

临界资源：一个时间段只允许一个进程使用的资源。各进程需要互斥地访问临界资源

临界区：访问临界资源的那段代码

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的PCB组成）

9.2 进程调度的方式

1. 非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态

   实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统

2. 剥夺调度方式，又称抢占方式。当一个进程正在进程处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程

   可以优先处理更紧急的进程，也可实现让各进程时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统

9.3 进程的切换与过程

“狭义的进程调度”与“进程切换”的区别：

狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换的过程主要完成了：

1. 对原来运行进程各种数据的保存

2. 对新的进程各种数据的恢复（如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）

注意：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在进程切换上，而真正用于执行进程的时间减少

10 调度器和闲逛进程

10.1 调度器/调度程序

10.2 闲逛进程

调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程

特性：

1）优先级最低

2）可以是0地址指令，站一个完整的指令周期（指令周期末尾例行检查中断）

3）能耗低

11 调度算法的评价指标

11.1 CPU利用率

由于早期的CPU造价及其昂贵，因此人们会希望让CPU尽可能多迪工作

CPU利用率：指CPU“忙碌”的时间占总时间的比例

通常会考察多道程序并发执行的情况，可以用“甘特图”来辅助计算

11.2 系统吞吐量

单位时间内完成作业的数量

11.3 周转时间

是指从作业被提交给系统开始，到作业完成为止的这段时间间隔

它包括四个部分：

1. 作业在外存后备队列上等待作业调度（高级调度）的时间

2. 进程在就绪队列上等待进程调度（低级调度）的时间

3. 进程在CPU上执行的时间

4. 进程等待I/O操作完成的时间

后三项在一个作业的整个处理过程中，可能发生多次

有的作业运行时间短，有的作业运行时间长，因此在周转时间相同的情况下，运行时间不同的作业，给用户的感觉肯定是不一样的

对于周转时间相同的两个作业，实际运行时间长的作业相同时间内被服务的时间更多，带权周转时间更小，用户满意度更带权周转时间与周转时间都是越小越好

11.4 等待时间

指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低

作业在后备队里等待被服务（调度）。作业调入内存后，建立对应的进程。这个进程会被CPU服务

会被I/O设备服务，当然也会有等待被服务的时候

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间

对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间

11.4 响应时间

指从用户提交请求到首次产生响应所用的时间

12 调度算法

12.1 先来先服务（FCFS）

优点：公平、算法实现简单

缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即FCFS算法对长作业有利，对短作业不利

不会导致饥饿

12.2 短作业优先（SJF）

使用短进程优先调度算法

每次调度当前已经到达且运行时间最短的作业/进程

对比FCFS算法的结果，显然SPF算法的平均等待/周转/带权周转时间都要更低

​ “最短剩余时间优先算法”

每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度

注意几个小细节：

1.如果题目中未特别说明，所提到的默认是非抢占式

2.在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少

或者在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少

12.2.1 对FCFS和SJF两种算法的思考

12.3 高响应比优先算法

12.4 时间片轮转（RR）

通过就绪队列，时间一到就插到队尾

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间，因此时间片不能太大

12.5 优先级调度算法

补充：就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以吧优先级高的进程排在更靠近队头的位置

根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。

静态优先级：创建进程时确定，之后一直不变

动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级

通常：

系统进程优先级高于用户进程

前台进程优先级高于后台进程

操作系统更偏好I/O进程（或称I/O繁忙型进程）

注：与I/O型进程相对的是计算型进程（或称CPU繁忙型进程）

可以从追求公平、提升资源利用率等角度考虑

如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级

如果某进程占用处理机运行了很长时间则可适当降低其优先级

如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级

12.6 多级反馈队列调度算法

会导致饥饿

12.7 多级队列调度算法

13 进程同步、进程互斥

13.1 什么是进程同步

进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知得到速度向前推进

读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据->读数据”的顺序来执行

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作

13.2 什么是进程互斥

进程的“并发：需要”共享“的支持。各个并发执行的进程不可避免的需要共享一些系统资源（比如内存、又比如打印机、摄像头这样的I/O设备）

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源

对临界资源得到访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源

对临界资源的互斥访问，可以在逻辑上分为如下四个部分：

进入区：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志（可理解为“上锁”），以阻止其他进程同时进入临界区

临界区：访问临界资源的那段代码

退出区：负责解除正在访问临界资源的标志（可理解为：解锁“）

剩余区：做其他处理

注意：

临界区是进程中访问临界资源的代码段

进入区和退出区是负责实现互斥的代码段

临界区也可称为“临界段”

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循一下原则：

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区

2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待

3. 有限等待。对请求访问的进程，应保证在有限时间内进入临界区（保证不会饥饿）

4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

14 进程互斥的软件实现方法

14.1 单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

14.2 双标志先检查法

算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0]=true”意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区

14.3 双标志后检查法

算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到了先“上锁“后”检查“的方法，来避免上述问题

如果按照1526的顺序执行，P0和P1都无法进入临界区

14.4 Peterson算法

算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）

15 进程互斥的硬件实现方法

15.1 中断屏蔽方法

利用“开/ 关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）

优点：简单、高效

缺点：不适用于多处理机：只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）

15.2 TestAndSet指令

简称TS指令，也有地方称为TestAndLock指令，或TSL指令

TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑

优点：实现简单，无需像软件实现方法那样严格检查是否会出现逻辑漏洞；适用于多处理机环境

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”

15.3 Swap指令

有的地方也叫EXchange指令，或简称XCHG指令

Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境

缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”

16 互斥锁

16.1 进程互斥：锁

互斥锁

解决临界区最简单的工具就是互斥锁。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数acquire()获得锁，而函数release()释放锁

每个互斥锁有一个布尔变量available，表示锁是否可用。如果锁是可用的，调用acquire()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放

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

互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程进入临界区时必须连续循环调用acquire。当多个进程共享同一个CPU时，就浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行

需要连续循环忙等的互斥锁，都可以称为自旋锁，如TSL指令、swap指令、单标志法

特性：

需忙等，进程时间片用完才下处理机，违反“让权等待”

优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低

常用于多处理机系统，一个核忙等，其他核照常工作，并快速释放临界区

不太适用于单处理机系统，忙等的过程不可能解锁

17 信号量机制

1. 在双标志先检查法中，进入区的：检查“、”上锁“操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题

2. 所有的解决方案都无法实现“让权等待”

17.1 信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步

信号量其实就是一个变量（可以是一个整数、也可以是更复杂的记录型变量），可以用一个信号量来表示系统某种资源的数量，比如系统中只有一台打印机，就可以设置一个初值为1的信号量

原语是一种特殊的程序段，其执行只能一气呵成、不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题

整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量

与普整数变量的区别：对信号量的操作只有三种，即初始化、P操作、V操作

17.2 记录型信号量

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量

如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把挂到信号量S的等待队列（即阻塞队列）中

释放资源后，若还有别的进程在等待这种资源，则使用wakeup 原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态

18 用信号量实现进程互斥、同步、前驱关系

18.1 信号量机制实现进程互斥

注意：对不同临界资源需要设置不同的互斥信号量

P、V操作必须成对出现。缺少P就不能保证临界资源的互斥访问。缺少V会导致资源永不被释放，等待进程永不被唤醒。

18.2 信号量机制实现进程同步

进程同步：要让各并发进程按要求有序地推进

1.分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）

2.设置同步信号量S，初始为0

3.在“前操作”之后执行V(S)

4.在“后操作”之前执行P(S)

​ 保证了代码4 一定是在代码2 之后执行

18.3 信号量机制实现前驱关系

其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作）

1. 要为每一对前驱关系各设置一个同步信号量

2. 在“前操作”之后对相应的同步信号量执行V操作

3. 在“后操作”之后对相应的同步信号量执行P操作

19 生产者-消费者问题

只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待

只有缓冲区不空时，消费者才能从中取出产品，否则必须等待

缓冲区是临界资源，各进程必须互斥访问

19.1 PV操作题目分析步骤

1.关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系

2.整理思路。根据各进程的操作流程确定P、V操作的大致顺序

3.设置信号量。根据题目条件确定信号量初值（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

19.2 能否改变相邻P、V操作的顺序？

这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待着生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”

因此，实现互斥的P操作一定要在实现同步的P操作之后

V操作不会导致进程阻塞，因此两个V操作顺序可以交换

20 吸烟者问题

这个题也属于“生产者-消费者”问题，更详细的说应该是“可生产多种产品的单生产者-多消费者”。

桌子可以抽象为容量为1的缓冲区，要互斥访问

缓冲区大小为1，同一时刻，四个同步信号量中至多有一个的值为1

provider(){
    while(true){
        if(i==0){
            P(finish);
            P(mutex);
            制作组合一;
            V(mutex);
            V(offer1)
        }else if(i==1){
            P(finish);
            P(mutex);
            制作组合二;
            V(mutex);
            V(offer2)
        }else if(i==2){
            P(finish);
            P(mutex);
            制作组合二;
            V(mutex);
            V(offer3)
        }
        i += i % 3;
    }
}

若一个生产者要生产多种产品（或者说会引发多种前驱事件），那么各个V操作应该放在各自对应的“事件”发生之后的位置

21 读者写者问题

21.1 问题描述

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程或其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：

1）允许多个读者可以同时对文件执行读操作

​ 读者进程在读数据后并不会将数据清空，并不会改变数据。因此多个读者可同时访问共享数据

2）只允许一个写者往文件中写信息

3）任一写者在完成写操作之前不允许其他读者或写者工作

4）写者执行写操作前，应让已有的读者和写者全部退出

​ 读进程与写进程同时共享数据，可能导致读出的数据不一致的问题

​ 两个写进程同时共享数据，可能导致数据错误覆盖的问题

21.2 如何实现

潜在的问题：只要有读进程还在读，写进程就要一直阻塞等待，可能“饿死”。因此，这种算法中，读进程是优先的

结论：在这种算法中，连续进入读者可以同时读文件，写者和其他进程不能同时访问文件；写者不会饥饿，但也并不是真正的“写优先”，而是相对公平的先来先服务

22 哲学家进餐问题

如果5个哲学家并发地拿起了自己左手边的筷子，每位哲学家循环等待右边的人放下筷子（阻塞），发生了“死锁”

如何防止死锁的发生呢？

1）可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的

2）要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号刚好相反。用这种方式可以保证如果相邻的两个奇偶号哲学家都想吃放，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况

3）仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子

更准确的说法应该是：各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子

23 管程

23.1 为什么要引入管程

信号量机制存在的问题：编写程序困难、易出错

如果写错了P操作的顺序，就可能会发生死锁

能不能设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松？

23.2 管程的定义和基本特征

管程是一种特殊的软件模块，有这些部分组成：

1）局部于管程的共享数据结构说明

2）对该数据结构进行操作的一组过程

3）对局部于管程的共享数据设置初始值的语句

4）管程有一个名字

23.2.1 管程的基本特征：

1. 局部于管程的数据只能被局部于管程的过程所访问

2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据

3. 每次仅允许一个进程在管程内执行某个内部过程

23.1 拓展1：用管程解决生产者消费者问题

伪代码：

管程中设置条件变量和等待/唤醒操作，以解决同步问题

引入管程的目的无非就是要更方便地实现进程互斥和同步

1. 需要在管程中定义共享数据（如生产者消费者问题的缓冲区）

2. 需要在管程中那个定义用于访问这些共享数据的“入口”——其实就是一些函数（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品）

3. 只有通过这些特定的“入口”才能访问共享数据

4. 管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入（如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多一个进程在访问缓冲区。注意：这种互斥特性是由编译器负责实现的，程序员并不关心）

5. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”）：可以通过唤醒操作将等待在条件变量上的进程或线程唤醒

23.1 拓展2：java中类似于管程的机制

java中，如果用关键字synchronized来描述一个函数，那么这个函数同一时间段只能被一个线程调用

24 死锁的概念

24.1 什么是死锁

哲学家进餐问题，每位哲学家都在等待自己右边的人放下筷子，这些哲学家进程都因等待筷子资源而被阻塞。即发生“死锁”

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都被阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉，这些进程都将无法向前推进

24.2 死锁、饥饿、死循环的区别

死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象

饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先算法

死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的

24.3 死锁产生的必要条件

产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生

1. 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）

2. 不剥夺条件：进程所获得的的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放

3. 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放

4. 循环等待的条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源被下一个进程所请求

注意！发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待时死锁的必要不充分条件）

24.4 什么时候会发生死锁

总之，对不可剥夺资源的不合理分配，可能导致死锁

24.5 死锁的处理策略

1. 预防死锁。破坏死锁产生的四个必要条件中的一个或几个

2. 避免死锁。用某种方法防止进入不安全状态，从而避免死锁（银行家算法）

3. 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁

24.5.1 预防死锁

24.5.1.1 破坏互斥条件

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁

如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如：SPOOLing技术

这个策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件

24.5.1.2 破坏不剥夺条件

24.5.1.3 破坏请求和保持条件

可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源

24.5.1.4 破坏循环等待条件

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

原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象

24.5.2 避免死锁（银行家算法）

24.5.2.1 什么是安全序列

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个

如果分配资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求，这也是“银行家算法”的核心思想

24.5.2.1 银行家算法

核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待

系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁

24.5.3 死锁的检测和解除

如果系统中不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供两个算法：

1）死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁

2）死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来

24.5.3.1 死锁的检测

为了能对系统是否已发生了死锁进行检测，必须：

1）用某种数据结构来保存资源的请求和分配信息

2）提供一种算法，利用上述信息来检测系统是否已进入死锁状态

1. 如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去

2. 如果这个进程执行结束了就把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去

3. 相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程

如果按照上述过程，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于一个安全序列）

4. 如果最终不能消除所有边，那么此时就是发生了死锁。最终还连着边的那些进程就是处于死锁状态的进程

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

24.5.3.1 死锁的解除

一旦检测出死锁的发生就应该立即解除死锁

补充：并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程

解除死锁的主要方法有：

1. 资源剥夺法。挂起（暂时放在外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应该防止被挂起的进程长时间得不到资源而饥饿

2. 撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来

3. 进程回退法。让一个或多个进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点

如何决定“对谁动手”

1. 进程优先级

2. 已执行多长时间

3. 还要多久能完成

4. 进程已经使用了多少资源

5. 进程时交互式的还是批处理式的