第二章 进程管理

第二章 进程管理

2.1 进程和线程

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

概念

进程（Process）：是动态的，是程序的一次执行过程

同一个程序多次执行会对应多个进程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wvYZBmbc-1641113805176)(E:/txy/大三上/操作系统/img/image-20210806100929301.png)]

组成

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aZLqpHdq-1641113805178)(E:/txy/大三上/操作系统/img/image-20210806102114288.png)]

PCB是进程存在的唯一标志

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

这些信息都被保存在一个数据结构PCB（Process Control Block）中，即进程控制块操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jCeFPnM4-1641113805178)(E:/txy/大三上/操作系统/img/image-20210806102043843.png)]

特征

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7htOEJZ9-1641113805179)(E:/txy/大三上/操作系统/img/image-20210806102222621.png)]

动态性：动态性是进程最基本特征，进程有着创建、活动、暂停、终止等过程，具有生命周期

并发性：多个进程实体同时存在内存中，引入进程的目的就是为了程序与其他程序并发执行

独立性：进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。没有建立PCB的程序，都不能作为一个独立单位参与运行

异步性：进程相互制约，进程以不可预知的速度向前推进。所以操作系统中一定要配置响应的进程同步机制程序段

结构性：每个进程都配置一个PCB对其进行描述（数据段、进程实体、进程控制段）

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

进程的状态

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7IpXvLA0-1641113805180)(E:/txy/大三上/操作系统/img/image-20210806104014419.png)]

• 创建态
• 就绪态
• 运行态
• 阻塞态
• 终止态

进程的转换

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GvNxv1Ot-1641113805181)(E:/txy/大三上/操作系统/img/image-20210806104039442.png)]

进程的组织

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PoJC8rgN-1641113805182)(E:/txy/大三上/操作系统/img/image-20210806103324789.png)]

2.1.3 进程控制

进程控制就是要实现进程状态转换

• 如何实现进程控制/p>

  用“原语”实现

  原语的执行具有“原子性”，一气呵成

• 如何实现原语的“原子性”/p>

  原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断。可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性

进程的创建

允许一个进程创建另一个进程，此时创建者称为父进程，被创建的进程称为子进程。子进程可以继承父进程所拥有的资源。当子进程被撤销时，应将其从父进程那里获得的资源归还给父进程。在撤销父进程时，必须同时撤销其所有的子进程。

用户登录，作业调度，提供服务，应用请求

进程的终止

正常结束、异常结束、外界干预

进程的阻塞

阻塞态是暂时停止运行，比如等待IO操作，等待其他进程配合

进程的唤醒

等待的事件发生

进程的切换

当前进程时间片到

有更高优先级的进程到达

当前进程主动阻塞

当前进程终止

以上进程控制的原语与以下基本类似：

（1）更新PCB中信息

（2）将PCB插入合适队列

（3）分配/回收资源

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GszP3Fjl-1641113805183)(E:/txy/大三上/操作系统/img/image-20210806105151274.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lCHHOC3f-1641113805184)(E:/txy/大三上/操作系统/img/image-20210806105215214.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-e9yWkaLo-1641113805184)(E:/txy/大三上/操作系统/img/image-20210806105230188.png)]

阻塞态是暂时停止运行，比如等待IO操作

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AnhR30SP-1641113805185)(E:/txy/大三上/操作系统/img/image-20210806105240169.png)]

2.1.4 进程通信

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RKs9BnkV-1641113805186)(E:/txy/大三上/操作系统/img/image-20210809091958835.png)]

什么是进程通信/h4>

进程通信就是指进程之间的信息交换。
进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。

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

共享存储

基于数据结构的共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式
基于存储区的共享：在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。

管道通信

数据以字符流的形式写入管道，当管道写满时，写进程的write（）系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read（）系统调用将被阻塞。

如果没写满，就不允许读。如果没读空，就不允许写。

数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。

消息传递

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

间接通信：消息要先发送到中间实体（信箱）中，因此也称“信箱通信方式”。

2.1.5 线程的概念和特点

什么是线程，为什么要引入线程/h4>

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Tb1C4Vxl-1641113805186)(E:/txy/大三上/操作系统/img/image-20210809092454436.png)]

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

可以把线程理解为“轻量级进程”。
线程是一个基本的CPU执行单元，也是程序执行流的最小单位。

引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件）

引入线程后，进程只作为除CPU之外的==系统资源的分配单元==（如打印机、内存地址空间等都是分配给进程的）。线程则作为==处理机的分配单元==。

进程与线程比较

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wg4sJ6CK-1641113805187)(E:/txy/大三上/操作系统/img/image-20210809092912836.png)]

线程属性

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jVgA7C5l-1641113805188)(E:/txy/大三上/操作系统/img/image-20210809092934133.png)]

2.1.6 线程的实现方法和多线程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ejnND2cf-1641113805189)(E:/txy/大三上/操作系统/img/image-20210809093107295.png)]

while 循环就是一个最弱智的“线程库”，线程库完成了对线程的管理工作（如调度）。

2.2 调度

2.2.1 调度的概念、层次

基本概念

合理的对进程进行处理及分配

调度的层次

高级调度（作业调度）

按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。

中级调度（内存调度）

按照某种策略决定将哪个处于挂起状态的进程重新调入内存。
一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

低级调度（进程调度/处理机调度）

按照某种策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
进程调度的频率很高，一般几十毫秒一次。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-64y7Hoe4-1641113805190)(E:/txy/大三上/操作系统/img/image-20210809095221730.png)]

补充知识：七种状态

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4UiS4g9I-1641113805191)(E:/txy/大三上/操作系统/img/image-20210809095100142.png)]

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

切换时机

不能切换的情况

1. 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
2. 进程在操作系统内核程序临界区中。
3. 在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列）

可以切换的情况

当前运行的进程主动放弃处理机

• 进程正常终止
• 运行过程中发生异常而终止
• 进程主动请求阻塞（如等待I/O）

当前运行的进程被动放弃处理机

• 分给进程的时间片用完
• 有更紧急的事需要处理（如I/O中断）
• 有更高优先级的进程进入就绪队列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5IK6KRPg-1641113805191)(E:/txy/大三上/操作系统/img/image-20210809095522536.png)]

调度方式

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

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

进程的切换与过程

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

狭义的进程调度指的是从就绪队列中选中一个要运行的进程。

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

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

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

2.2.3 调度算法的评价指标

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tfxXe10D-1641113805192)(E:/txy/大三上/操作系统/img/image-20210809100430643.png)]

2.2.4 调度算法1

先来先服务（FCFS）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fzQVjE8o-1641113805192)(E:/txy/大三上/操作系统/img/image-20210809100556385.png)]

最短作业优先（SJF）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sG5Gq2iI-1641113805193)(E:/txy/大三上/操作系统/img/image-20210809103954401.png)]

最高响应比优先（HRRN）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cX0ESJD2-1641113805193)(E:/txy/大三上/操作系统/img/image-20210809104030359.png)]

2.2.5 调度算法2

时间片轮转（RR）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Vd53Uv6C-1641113805194)(E:/txy/大三上/操作系统/img/image-20210809104546611.png)]

优先级调度

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aJ0phrwP-1641113805194)(E:/txy/大三上/操作系统/img/image-20210809104608636.png)]

多级反馈队列

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-avuZpMUm-1641113805195)(E:/txy/大三上/操作系统/img/image-20210809104623466.png)]

对各类型进程相对公平（FCFS的优点）；

每个新到达的进程都可以很快就得到响应（RR的优点）；

短进程只用较少的时间就可完成（SPF的优点）；

不必实现估计进程的运行时间（避免用户作假）；

可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程（拓展：可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级）

一般不说它有缺点，不过可能导致饥饿

2.3 互斥同步

2.3.1 进程同步、进程互斥

进程同步

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

进程间的直接制约关系就是源于它们之间的相互合作。

解决异步问题

进程互斥

间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待

临界区资源的互斥访问

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

进入区：负责检查是否可进入临界区

退出区：负责解除正在访问临界资源的标志

剩余区：做其他处理

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

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

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

原则

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

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

单标志法

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

主要问题：违背“空闲让进”原则，必须“轮流访问”

双标志先检查法

每个进程访问临界资源前，先检查临界资源是否被访问，如果空闲才能进

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

主要问题：违反“忙则等待”原则。

原因在于，进入区的==“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换==。

双标志后检查法

先设置标志，表示自己想进入，检查对方标志，如果对方也要进入，那么就等待否则就进入

优点：不会两个进程都进入临界区

缺点：双方会互相谦让，导致饥饿

Peterson 算法

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

增加标志位

优点：不会饥饿

缺点：复杂

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

中断屏蔽法

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

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

TestAndSet指令（TSL）

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

相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。

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

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

Swap指令（XCHG）

逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 old 变 量上），再将上锁标记 lock 设置为 true，最后检查 old，如果 old 为 false 则说明之前没有别的进程 对临界区上锁，则可跳出循环，进入临界区。

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

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

2.3.4 信号量机制

实现进程互斥、同步的方法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8h4bhrAF-1641113805195)(E:/txy/大三上/操作系统/img/image-20210810101206955.png)]

信号量其实就是一个变量，可以用一个信号量来表示系统中某种资源的数量

wait、signal 原语常简称为P、V操作（来自荷兰语proberen 和verhogen）。因此，做题的时候常把wait（S）、signal（S） 两个操作分别写为P（S）、V（S）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AXg8xyG4-1641113805196)(E:/txy/大三上/操作系统/img/image-20210811085502606.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Vcsx0fvv-1641113805197)(E:/txy/大三上/操作系统/img/image-20210811085204493.png)]

P上锁

V解锁

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

实现进程互斥

上锁——解锁

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jYzp5jCP-1641113805197)(E:/txy/大三上/操作系统/img/image-20210811085609021.png)]

实现进程同步、前驱关系

解锁——上锁

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dXHZJZh9-1641113805198)(E:/txy/大三上/操作系统/img/image-20210811085723623.png)]

实现前驱关系

画图非常有用

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-h6bfUBVy-1641113805199)(E:/txy/大三上/操作系统/img/image-20210811085837013.png)]

2.3.6 生产者消费者问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aPDsxoT4-1641113805200)(E:/txy/大三上/操作系统/img/image-20210811090040687.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vv0LQicH-1641113805200)(E:/txy/大三上/操作系统/img/image-20210811090123901.png)]

思考：能否改变相邻P、V操作的顺序/h4>

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BKSTZq7w-1641113805201)(E:/txy/大三上/操作系统/img/image-20210811090143116.png)]

会导致：我要放东西通过了，但满了放不进去，去到消费者，但通道被生产者占住了，形成死锁
同步：查看缓存区容量和非空区
互斥：消费者和生产者不能同时使用缓存区

2.3.7 多生产者-多消费者

画图非常有用

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Lx29dg4M-1641113805201)(E:/txy/大三上/操作系统/img/image-20210811090407803.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lIzwZte9-1641113805202)(E:/txy/大三上/操作系统/img/image-20210811090607292-1628643969247.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hQcRoE4S-1641113805202)(E:/txy/大三上/操作系统/img/image-20210811090642491.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2IWMsrrg-1641113805203)(E:/txy/大三上/操作系统/img/image-20210811090704381.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zNkdToRK-1641113805204)(E:/txy/大三上/操作系统/img/image-20210811090742847.png)]

2.3.8 吸烟者问题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Bur6PNjJ-1641113805204)(E:/txy/大三上/操作系统/img/image-20210811090820316.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-S70zp0eT-1641113805205)(E:/txy/大三上/操作系统/img/image-20210811090833274.png)]

2.3.9 读者-写者问题

写和读，写和写不能同时访问

但读和读可以同时访问

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eQKa8wcW-1641113805206)(E:/txy/大三上/操作系统/img/image-20210811090952188.png)]

• “读优先”

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tLo3jKE6-1641113805207)(E:/txy/大三上/操作系统/img/image-20210811091051596.png)]

第一个读者先加两把锁，都关上，再打开互斥锁，让其他读者进行访问

• ”写优先“相对公平

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bJy7FwnE-1641113805207)(E:/txy/大三上/操作系统/img/image-20210811091122875.png)]

第一个读者先加三把锁，都关上，再打开互斥锁和写优先锁，且先打开写优先锁，使只要读者读完就给写

2.3.10 哲学家进餐问题

没什么意思

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-b5VGn3Xw-1641113805208)(E:/txy/大三上/操作系统/img/image-20210811091319770.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-d6oTfOpb-1641113805208)(E:/txy/大三上/操作系统/img/image-20210811091329002.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FHjq64Mm-1641113805209)(E:/txy/大三上/操作系统/img/image-20210811091341243.png)]

2.3.11 管程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9l5C8TgC-1641113805209)(E:/txy/大三上/操作系统/img/image-20210811091411446.png)]

---

为什么要引入管程

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

管程的定义

1. 局部于管程的共享数据结构说明；
2. 对该数据结构进行操作的一组过程；
3. 对局部于管程的共享数据设置初始值的语句；
4. 管程有一个名字。

基本特征

1. 局部于管程的数据只能被局部于管程的过程所访问；
2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
3. 每次仅允许一个进程在管程内执行某个内部过程。

2.4 死锁

2.4.1 死锁的概念

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

必要条件

互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。
不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

2.4.2 预防死锁

破坏互斥条件

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

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

缺点：并不是所有的资源都可以改造成可共享使用的资源。

破坏不剥夺条件

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

破坏不剥夺条件：
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。

方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）

缺点：

1. 实现起来比较复杂。
2. 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

破坏请求和保持条件

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

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

缺点：
有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。

另外，该策略也有可能导致某些进程饥饿。

破坏循环等待条件

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

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

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

该策略的缺点：

1. 不方便增加新的设备，因为可能需要重新分配所有的编号；
2. 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费；
3. 必须按规定次序申请资源，用户编程麻烦。

2.4.3 避免死锁

什么是安全序列

安全性算法步骤：

检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列， 并把该进程持有的资源全部回收。 不断重复上述过程，看最是否能让所有进程都加入安全序列。

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AErArk6n-1641113805210)(E:/txy/大三上/操作系统/img/image-20210811144651890.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tsNRhyx5-1641113805211)(E:/txy/大三上/操作系统/img/image-20210811144753103.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7Vunol0z-1641113805211)(E:/txy/大三上/操作系统/img/image-20210811095700097.png)]

2.4.4 检测和解除

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pqwIj5vi-1641113805212)(E:/txy/大三上/操作系统/img/image-20210811095750367.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-samEouZV-1641113805212)(E:/txy/大三上/操作系统/img/image-20210811145530489.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AKRKolCy-1641113805213)(E:/txy/大三上/操作系统/img/image-20210811145650810.png)]

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

死锁的解除

一旦检测出死锁的发生，就应该立即解除死锁。
补充：并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程解除死锁的主要方法有：

1. 资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
2. 撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

PPT小题整理（进程调度）

前趋图

偏序，直接前趋，直接后继

初始节点，终止结点

顺序执行：

顺序性，封闭性，可再现性

并发执行：

间断性、失去封闭性、不可再现性

引入进程目的：

是为了使多个程序并发执行，以改善资源利用率及提高系统的吞吐量

进程的特征：

结构特征：PCB，程序段，数据段

动态性、并发性、独立性、异步性

进程的定义：

进程是程序的一次执行

进程是一个程序及其数据在处理机上顺序执行时发生的活动

进程是一个可拥有资源的独立实体，同时又是一个可以独立调度的基本单位

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

进程与程序的关系

每个进程实体中包含了PCB、程序段和数据段这三个部分，因此进程与程序是紧密相关的

程序是指令的有序集合，能永久的保存在某种介质上，没有任何执行的含义，是一个静态概念。而进程是程序的一次执行过程，是一个动态概念，强调执行过程，它动态地被创建、调度执行、撤消

进程具有并发性，而程序没有

进程是一个能够独立运行、独立分配资源和独立接受调度的基本单位。而程序不具有PCB，所以它是不可能在多道程序环境下独立运行

进程与程序的对应。同一个程序的多次运行，将形成多个不同的进程；同一个程序的一次执行也可以产生多个进程（通过fork调用）；而一个进程也可以执行多个程序（通过exec调用）

PCB

PCB 中记录了OS所需的、用于描述进程的当前状态及控制进程的全部信息

进程描述信息

进程调度信息

处理机状态

进程控制信息

组织方式

链接方式、索引方式、线性方式

进程状态的转换

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2MG2nthb-1641113805214)(…/img/01.png)]

需要加上挂起状态、激活状态

活动就绪、静止就绪、活动阻塞、静止阻塞

进程控制

原语

系统态：高特权、执行一切指令访问所有寄存区，OS内核运行在系统态下

用户态：低特权，只能执行规定指令

进程的创建：

子进程继承父进程所有资源，撤销时，归还

父进程撤销，子进程撤销

事件：用户登录、作业调度、提供服务、应用请求

进程的撤销

正常结束、异常结束、外界干预

阻塞、唤醒原语

向系统请求共享资源失败

等待某种操作完成

新数据尚未到达

无新工作可做

进程挂起原语

终端用户的请求

父进程请求

负荷调节的需要

操作系统的需要

激活原语

终端用户请求激活，内存足够

父进程请求激活，且内存空间足够

进程同步

一组并发进程因直接制约而进行相互合作，相互等待，使得各进程按一定速度执行的过程称为进程间的同步

直接制约关系：合作关系，协同工作的一种等待关系

间接制约关系：对临界资源的竞争关系

**临界区：**每个进程中，访问临界资源的那段代码

**互斥：**一组并发进程中的一个或多个程序段，因为共享一共有资源而导致他们必须一个不允许交叉执行的单位执行

同步机制应遵循的规则：

空闲让进、忙则等待、有限等待、让权等待

信号量机制

整型信号量

没有遵循“让权等待”

记录型信号量（★★★★★）

表示

value（初值表示系统中某类资源的数目）

next（访问该资源的进程等待队列）

Wait

（1）S.value=S.value-1

（2）如果s.value≥0，则表示有资源，该进程继续执行；如果s.value

Signal

（1） s.value:=s.value+1

（2）如果s.value>0，则该进程继续执行；如果s.value≤0，则表示在S信号量队列中，仍有等待该资源的进程被阻塞，故调用唤醒原语将S信号量队列中的第一个等待进程唤醒

AND型信号量

将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配，这样就可避免死锁情况的发生。为此，在wait操作中，增加了一个个“AND”条件，故称为AND同步，

信号量集

前面几种信号量机制中，wait(S)和signal(S)操作仅能对信号量进行加1或减1的操作。而当我们一次需要N个某类资源时，并要进行N次wait(S)，非常不方便。而且，当资源数量低于某一下限时，便不分配资源。因此，引入了信号量集

Swait(S1, t1, d1, …, Sn, tn, dn) 其中Si信号量，d为需求量，t为下限值

实现互斥

为了使多个进程能互斥的访问某临界资源，只须为该资源设置一互斥信号量，并设其初始值为1，然后将各进程访问该资源的临界区置于wait(mutex)和signal(mutex)操作之间即可

实现前驱关系

设有两个并发执行的进程P1和P2，P1中有语句s1；P2中有语句S2，并有S1-》S2

P1：S1；signal(S)；

P2：wait(S)；S2；

生产者消费者

读者写者

哲学家进餐

进程通信

低级通信：只能传递状态和整数值

优点：速度快

缺点：传送信息量小，编程复杂

高级通信：利用原语，传送大量数据

进程间的数据交换以格式化的消息为单位

直接通信方式

直接把消息发送给目标进程

间接通信方式

进程间通过某种中间实体（信箱）通信，发送进程将消息投入信箱，接收进程则从信箱中取得消息

通过消息缓冲队列通信机制

私用信箱、公用信箱、共享信箱

共享存储区

消息队列、共享内存、管道的区别

消息队列自身有同步机制；但不支持广播机制； 当传输大量数据时，花费较高

共享内存必须自己考虑同步问题，但支持广播机制；当传输大量数据时，系统开销小

管道能传递大量数据，但只支持半双工，只能用于有血缘关系的进程之间

PPT小题整理（处理机调度）

调度的实质

调度的实质是一种资源分配，处理机调度是对处理机资源进行分配

处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。

处理机调度的层次

高级调度（作业调度）

用于决定把外存上处于后备队列中的哪些作业调入内存，为它们分配必要的资源，并创建进程。

在批处理中，大多配有作业调度，但在分时和实时系统中，通常不配置作业调度。

作业调度的运行频率较低，一般为几分钟一次

中极调度（内存调度）

它按一定的算法将外存中处于静止就绪状态或静止阻塞状态的进程换入内存，而将内存中处于活动就绪状态或活动阻塞状态的某些进程换出至外存。

交换调度的目的是为了解决内存紧张问题，它常用在分时系统及具有虚拟存储器的系统中

低级调度（进程调度）

主要任务是按照一定的策略选取就绪队列中的一个进程获得处理机。

进程调度是最基本的调度，在os中必须配置它。它的运行频率很高，

非抢占方式

抢占方式

处理机调度算法的目标

资源利用率

CPU利用率=CPU有效工作时间 / （CPU有效工作时间+CPU空闲等待时间）

公平性

指应使各个进程都获得合理的CPU 时间，不会发生进程饥饿现象。

平衡性

使系统中的CPU和各种外部设备都能经常处于忙碌状态

策略强制执行

对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，

批处理系统的目标

周转时间

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

平均周转时间

$T=\frac{1}{n}\sum _{i=1}^n{T}_i$

带权周转时间

即作业的周转时间T与系统为它提供服务的时间Ts之比，即W?=?T/Ts

平均带权周转时间

T = 1 n ∑ i = 1 n T i T s T = frac{1}{n}sumlimits_{i=1}^nfrac{T_i}{T_s} T=n来源：weixin_45360119