王道考研 操作系统 第二章 进程管理第二章 进程管理前言2.1.1进程的定义、组成、组织方式2.1.2进程的状态与转换2.1.3进程控制2.1.4进程通信2.1.5线程概念和多线程模型2.2.1处理机调度的概念、层次2.2.2进程调度的时机、切换与过程2.2.3调度算法的评价指标2.2.4FCFS、SJF、HRRN调度算法2.2.5时间轮转法、优先级、多级反馈队列2.3.1进程同步、进程互斥2.3.2进程互斥的软件实现方法2.3.3进程互斥的硬件实现方法2.3.4信号量机制2.3.5用信号量实现

第二章 进程管理

前言

• 参考书籍《计算机操作系统》 汤小丹、《2022年 操作系统考研复习资料》 王道。(个人认为王道的书整体顺序安排更合理，更好用)
• B站王道计算机考研 操作系统视频课
• 原本是小张期末考试整理的王道笔记，后来复习过程中使用笔记可以快速的根据目录或者文字检索去查找某个概念、知识点。所以分享给大家，需要文本文件的可以留言评论。
• 思维导图和文字内容是手敲的，所以可能有一些错别字，评论我会修改。
• 如果只是为了期末考试可以看我的这篇操作系统期末考试总结_鬼才小张同学的博客-CSDN博客

2.1.1进程的定义、组成、组织方式

思维导图

本节内容

进程的概念

进程的组成

进程(进程实体)由程序段、数据段、PCB三部分组成。

进程的组织

在一个系统中，通常有数十、数百乃至数千个PCB。为了能对他们加以有效的管理，应当用适当的方式把这些PCB组织起来。
注：进程的组成讨论的是一个进程内部由哪些部分构成的问题，而进程组织讨论的是多个进程之间的组织方式问题。

链接方式

索引方式

进程的特征

进程和程序是两个截然不同的概念，相比于程序，进程拥有以下特征：

1. 动态性(最基本特征)：进程是程序的一次执行过程，是动态地产生、变化和消亡地。
2. 并发性：内存中有多个进程实体，各进程可并发执行。
3. 独立性：进程是能独立运行、独立获得资源、独立接受调度地基本单位
4. 异步性：各进程按各自独立的、不可预知地速度向前推进，操作系统要提供“进程同步机制”来解决异步问题,可能导致运行结果地不确定性。
5. 结构性：每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB组成。

2.1.2进程的状态与转换

思维导图

本节内容

进程是程序的一次执行。在这个执行过程中，有时进程正在被CPU处理，有时需要等待CPU服务，可见，进程的状态是会有各种变化。为了方便对各个进程的管理，操作系统需要将进程合理地划分为几种状态。

三种基本状态

运行态：占有CPU，并在CPU上运行
就绪态：已经具备运行条件，但由于没有空闲CPU，而暂时不能运行。
阻塞态：因等待某一事件而暂时不能运行。
注意单核处理机环境下，每一时刻最多只有一个进程处于运行态。双核环境下可以同时有两个进程处于运行态。

另外另种状态

创建态：进程正在被创建，操作系统为进程分配资源、初始化PCB。

终止态：进程正在从系统中撤销，操作系统回收进程拥有的资源、撤销PCB。

进程的状态转换

2.1.3进程控制

思维导图

本节内容

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

如何实现进程控制
动画讲解1:13-5:00

用原语实现进程控制。原语的特点是执行期间不允许中断，只能一气呵成。
这种不可被中断的操作即原子操作。原语采用“关中断”和开中断指令实现。

关/开中断指令的权限非常大，必然是只允许在核心态下执行的特权指令。

进程控制相关的原语

各原语可以实现怎样状态转换，各原语大概做了哪些事(理解了在选择题分析出答案即可，不用背)

2.1.4进程通信

思维导图

本节内容

什么是进程通信
进程通信就是指进程之间的信息交换。进程是分配系统资源的单位(包括内存地址空间)，因此各进程拥有的内存地址空间相互独立。
为了保证安全，一个进程不能直接访问另一个进程的地址空间。但是进程之间的信息交换又是必须实现的。为了保证进程间的安全通信，操作系统提供了一些方法。

共享存储

管道通信

消息传递

进程间的数据交换以格式化的消息为单位。进程通过操作系统提供的“发送消息/接受消息”两个原语进行数据交换。动画讲解9:00-11:00

2.1.5线程概念和多线程模型

思维导图

本节内容

什么是线程？为什么要引入线程？
还没引入进程之前，系统中各程序只能串行执行。

可以把线程理解为"轻量级进程"。线程是一个基本的CPU执行单元，也是程序执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务(如QQ视频、文字聊天、传文件)。

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

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

线程的属性

线程的实现方式

用户级线程

内核级线程

二者组合

多线程模型

在同时支持用户级线程和内核级线程的系统中，由几个用户级线程映射到几个内核级线程的问题引出了“多线程模型”问题。

多对一

一对一模型

多对多，集二者之所长

2.2.1处理机调度的概念、层次

思维导图

本节内容

调度的基本概念

调度的三个层次-高级调度

中级调度

补充知识：进程的挂起状态与七状态模型

暂时调到外存等待的进程状态为挂起状态(挂起态)。
挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。

低级调度

三层调度的联系、对比

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

思维导图

本节内容

进程调度的时机

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

进程调度的方式

进程与进程切换过程

2.2.3调度算法的评价指标

思维导图

本节内容

CPU利用率

CPU“忙碌”的时间占总时间的比例
利用率=$\frac{忙碌时间}{总时间}$

系统吞吐量

对于计算机来说，希望能用尽可能少的时间处理完尽可能多的作业。
单位时间内完成作业的数量

系统吞吐量=$\frac{总共完成了多少道作业}{总共花了多少时间}$

eg：某计算机系统处理完10道作业，共花费100s，则系统吞吐量为？

10/100=0.1 道/s

周转时间

对于计算机的用户来说，他很关心自己作业从提交到完成花了多少时间。
周转时间指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

它包括四部分：作业在外存后备队列上等待作业调度(高级调度)时间、进程在就绪队列上等待进程调度(低级调度)的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业的整个处理过程中，可能多次发生。

(作业)周转时间=作业完成时间-作业提交时间

平均周转时间=$\frac{各作业周转时间之和}{作业数}$

带权周转时间=$\frac{作业周转时间}{作业实际运行时间}$=$\frac{作业完成时间-作业提交时间}{作业实际运行时间}$

平均带权周转时间=$\frac{各作业带权周转时间之和}{作业数}$

等待时间

计算机的用户希望自己的作业尽可能少的等待处理机。
等待时间指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

响应时间

对于计算机用户来说，会希望自己的提交请求(比如通过键盘输入了一个调试命令)尽早地开始被系统服务、回应。
响应时间指从用户提出请求到首次产生响应所用的时间。

2.2.4FCFS、SJF、HRRN调度算法

思维导图

本节内容

各种调度算法的学习思路

1. 算法思想
2. 算法规则
3. 这种调度算法是用于作业调度还是进程调度
4. 抢占式？非抢占式
5. 优点和缺点
6. 是否会导致饥饿

先来先服务

按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。

eg：

进程	到达时间	运行时间	完成时间	等待时间	平均等待时间	周转时间	平均周转时间	带权周转时间	平均带权周转时间
P1	0	7	7	0	4.75	7	8.75	1	3.25
P2	2	4	11	5		9		2.25
P3	4	1	12	7		8		8
P4	5	4	16	7		11		2.75

注意I/O操作

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

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

不会造成饥饿

短作业优先

最短的作业/进程优先得到服务(所谓“最短”，是指要求服务时间最短)。

eg：非抢占式的短作业优先算法 P1→P3→P2→P4

进程	到达时间	运行时间	完成时间	等待时间	平均等待时间	周转时间	平均周转时间	带权周转时间	平均带权周转时间
P1	0	7	7	0	4	7	8	1	2.5625
P2	2	4	12	6		10		2.5
P3	4	1	8	3		4		4
P4	5	4	16	7		11		2.75

抢占式的短作业优先算法 P1(5)→P2(2)→P3(0)→P2(0)→P4(0)→P1(0)

注意

1. 如果题目中未特别说明，所提到的"短作业/进程优先算法"默认是非抢占式
2. 很多书上都会说“SJF 调度算法的平均等待时间、平均周转时间最少”。严格来说，这个表述是错误的，不严谨的。之前的例子表明，最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少。应该加上一个条件==“在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少”，或者说“在所有进程都几乎同时到达==时，采用SJF调度算法的平均等待时间、平均周转时间最少”。如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先,SRNT算法）的平均等待时间、平均周转时间最少”
3. 虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法(如FCFS) ,SJF依然可以获得较少的平均等待间、平均周转时间。
4. 如果选择题中遇到“SJF算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项。

优点："最短的"平均等待时间、平均周转时间

缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。

会导致饥饿。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生==“饥饿"现象。如果一直得不到服务，则成为"饿死”==。

最高相应比优先

在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。

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

eg：

综合考虑了等待时间和运行时间(要求服务时间)
等待时间同时时，要求服务时间短的优先(SJF的优点)
要求服务时间相同时，等待时间长的优先(FCFS的优点)
对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
不会导致饥饿

总结

2.2.5时间轮转法、优先级、多级反馈队列

思维导图

本节内容

时间轮转法

按照各个进程到达就绪队列地顺序，轮流让各个进程执行一个时间片(eg：100ms)。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放入就绪队列队尾重新排队。

eg：时间片大小为2

时间片大小为5

时间片太大或太小有什么影响？

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间，因此时间片不能太大。
另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

eg：

优先级

每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程。

eg：非抢占式

​ 抢占式

补充知识

优点：用于优先级区分紧急程度、重要程度，适用于实时 操作系统。可灵活的调整对各种作业/进程的偏好程度。
缺点：若源源不断地有高优先级进程到来，则可能导致饥饿。

会导致饥饿。

多级反馈队列

1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾。
3. 只有第K级队列为空时，才会为K+1级队头的进程分配时间片。

eg：动画讲解30:00-35:00

优缺点：对各类型进程相对公平(FCFS优点)；每个新到达的进程都可以很快就得到响应(RR的优点)；短进程只用较少的时间就可完成(SPF的优点)；不必实现估计进程的运行时间(避免用户作假)；可灵活地调整对各类进程地偏好程度，比如CPU密集型进程、I/O密集型进程(扩展：可以将因I/O而阻塞地进程重新放回到原队列，这样I/O型进程就可以保持较高优先级)。

总结

2.3.1进程同步、进程互斥

思维导图

本节内容

什么是进程同步？

并发性带来了异步性，有时需要通过进程同步解决这种异步问题。有的进程之间需要相互配合完成工作，各进程的工作推进需要遵守一定的先后顺序。

什么是进程互斥？

对临界资源的访问，需要互斥的进行。即同一时间段内只能允许一个进程访问该资源。

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

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

1. 空闲让进。临界区空闲时，应允许一个进程访问。
2. 忙则等待。临界区正在被访问时，其他试图访问的进程需要等待。
3. 有限等待。要在有限时间内进入临界区，保证不会饥饿。
4. 让权等待。进不了临界区的进程，要释放处理机，防止忙等。

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

思维导图

本节内容

单标志法

双标志先检查法

如果在②发生进程切换，P1进程也满足访问临界区条件，所以违反忙则等待原则

双标志后检查法

Peterson算法

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

思维导图

本节内容

中断屏蔽方法

TestAndSet指令

Swap指令

2.3.4信号量机制

思维导图

本节内容

信号量机制

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

整型信号量

记录型信号量

eg：动画17:00-23:00

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

思维导图

本节内容

信号量机制实现进程互斥

P操作是对资源的申请，V操作是对资源的释放。P、V操作必须成对出现

信号量机制实现进程同步

信号量机制实现前驱关系

2.3.6生产者-消费者问题

本节内容

问题描述

实现

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

总结

2.3.7多生产者-多消费者

本节内容

问题分析

如果不设置互斥信号量

总结

2.3.8吸烟者问题

本节内容

问题描述

问题分析

总结

2.3.9读者-写者问题

本节内容

问题描述

问题分析

如何实现

总结

2.3.10哲学家进餐问题

本节内容

问题描述

问题分析

如何实现

三种方案

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

总结

2.3.11 管程

思维导图

本节内容

为什么引入管程？

解决信号量机制编程麻烦、易出错的问题。

管程的定义和基本特征

扩展

扩展

2.4.1死锁的概念

思维导图

本节内容

什么是死锁？

在并发环境下，各进程相互等待对方手里的资源，导致各进程都阻塞，无法向前推进。

eg：

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

死锁：在并发环境下，各进程相互等待对方手里的资源，导致各进程都阻塞，无法向前推进。

饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先(SPF)算法中，若有源源不断地短进程到来，则长进程将一直得不到处理机，从而发生长进程"饥饿"。

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

死锁产生的必要条件

什么时候会发生死锁

死锁的处理策略

1. 预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
2. 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁(银行家算法)。
3. 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。

2.4.2死锁的处理策略-预防死锁

思维导图

本节内容

破坏互斥条件

破坏不剥夺条件

破坏请求和保持条件

破坏循环等待条件

2.4.3死锁的处理策略-避免死锁

思维导图

本节内容

什么是安全序列

银行家算法

实际做题

代码实现银行家算法

总结

2.4.4死锁的处理策略-检测和解除

思维导图

本节内容

死锁的检测

死锁解除

最后

以上就是热心戒指为你收集整理的王道考研 操作系统 第二章 进程管理第二章 进程管理前言2.1.1进程的定义、组成、组织方式2.1.2进程的状态与转换2.1.3进程控制2.1.4进程通信2.1.5线程概念和多线程模型2.2.1处理机调度的概念、层次2.2.2进程调度的时机、切换与过程2.2.3调度算法的评价指标2.2.4FCFS、SJF、HRRN调度算法2.2.5时间轮转法、优先级、多级反馈队列2.3.1进程同步、进程互斥2.3.2进程互斥的软件实现方法2.3.3进程互斥的硬件实现方法2.3.4信号量机制2.3.5用信号量实现的全部内容，希望文章能够帮你解决王道考研 操作系统 第二章 进程管理第二章 进程管理前言2.1.1进程的定义、组成、组织方式2.1.2进程的状态与转换2.1.3进程控制2.1.4进程通信2.1.5线程概念和多线程模型2.2.1处理机调度的概念、层次2.2.2进程调度的时机、切换与过程2.2.3调度算法的评价指标2.2.4FCFS、SJF、HRRN调度算法2.2.5时间轮转法、优先级、多级反馈队列2.3.1进程同步、进程互斥2.3.2进程互斥的软件实现方法2.3.3进程互斥的硬件实现方法2.3.4信号量机制2.3.5用信号量实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。