王道操作系统笔记第二章-进程管理（非常完整！包学包会！融入笔者自己的思考！）

本笔记为笔者观看网课王道计算机考研 操作系统 所记录。

文章目录 2.1.1、进程的概念、组成、特征2.1.2、进程的状态与转换、进程的组织2.1.3、进程控制2.1.4、进程通信2.1.5、线程的概念2.1.6、线程的实现方式和多线程模型2.1.7、线程的状态与转换2.2.1、进程调度的概念、层次2.2.2、进程调度的时机、切换与过程、方式2.2.3、调度器和闲逛进程2.2.4、调度算法的评价指标2.2.5、调度算法（1）2.2.6、调度算法（2）2.2.7、调度算法（3）2.3.1、进程同步、进程互斥2.3.2、进程互斥的软件实现方式2.3.3、进程互斥的硬件实现方式2.3.4、互斥锁2.3.5、信号量机制2.3.6、用信号量实现进程互斥、同步、前驱关系2.3.7、生产者-消费者问题2.3.8、多生产者-多消费者问题2.3.9、吸烟者问题2.3.10、读者写者问题2.3.11、哲学家进餐问题2.3.12、管程2.4.1、死锁的概念2.4.2、死锁的处理策略-预防死锁2.4.3、死锁的处理策略-避免死锁2.4.4、死锁的处理策略-检测和解除

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

进程定义：进程是允许并发执行的程序在某个数据集合上的执行过程，是程序的一次执行。

下面是linux的内核源码中定义的PCB数据结构

引入了线程之后，进程就不再是接受调度的基本单位了，但是进程依然是获得资源的基本单位。

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

就绪状态：进程一但获得CPU就可以投入运行的状态。

执行状态：进程获得CPU正在运行的状态。

阻塞状态: 进程由于等待资源或某个事件的发生而暂停执行的状态。

比如

大多数操作系统都是使用的链接方式来组织的PCB

2.1.3、进程控制

如果这两个特权指令允许用户程序使用的话，那么用户可以在程序开头设置关中断指令，在程序结尾设置开中断指令，这样程序就永远都不会被中断。所以这两个特权指令只能让内核程序使用而不能让用户使用。

但是呢，这些寄存器不是单个进程所独属的，它们也会被其他进程所使用。那么会发生什么情况呢。

另一个进程的数据会覆盖掉指令寄存器中的值

上面和下面的过程为恢复的过程

总结得精辟

2.1.4、进程通信

基于数据结构的共享可以理解为是一个“特殊的全局变量”可以被各个进程所共享。为什么说是特殊的呢？因为我们平时写代码时定义的全局变量时局部于一个进程的，而这个“特殊的全局变量”可以被各个进程所共享。

进程P要先通过系统调用申请“信箱”，然后准备好自己的msg，

进程需要先申请“管道”。“管道”内数据的读写是先进先出的。

既然这样的话，那管道通信合共享内存通信有什么区别呢？区别就在于FIFO“先进先出”。“管道”可以理解成一个循环队列。

考试的时候就回答“一个管道允许多个写进程，一个读进程”即可。

经查阅资料及linux上实验验证

2.1.5、线程的概念

进程的定义：进程是程序的一次执行。

进程再将这些资源分配给线程。

2.1.6、线程的实现方式和多线程模型

2.1.7、线程的状态与转换

与进程的状态与转换基本一致，不过我们只关注就绪、阻塞、运行这三种状态。

TCB的组织有多种方式。 比如说每个进程设置一个线程表；系统中所有线程组织成一个线程表；也可以根据线程的状态不同组织成不同的线程表。

所谓线程的组织，无非就是把各个TCB有规律地分门别类地组织起来。

2.2.1、进程调度的概念、层次

只有高频的进程调度，才能让进程快速轮流地上cpu运行，这样才可以让用户在宏观上看起来各个进程在同时运行。

在用手机时有可能出现这样的体验，有时候切换程序进程会发现切换得很快，有的时候切换得又很慢（说明要切换得那个程序进程现在正处于外存中）。

系统负载比较高，内存空间不够用时，那么就会把一些处于就绪态的进程调入外存中，变成就绪挂起的状态。一直到内存空间空闲，或者说进程需要继续执行，那么就绪挂起的进程就会被激活成就绪态（挪回内存空间）。

处于阻塞态的进程也会被挂起和激活。

有些操作系统有可能 当处于阻塞挂起状态的进程等待的事件出现时，将此进程转为就绪挂起的状态。而后当他重新被调入内存的时候，就会变为就绪态而不是阻塞态。

有的时候一个处于运行态的进程，运行结束后，可能这个进程下处理机的时候就会被直接放到外存中进入就绪挂起的状态。

有的时候一个处于创建态的进程，创建结束（创建完PCB）后，有可能内存不够，那这时处于创建态的进程会先进入到就绪挂起的状态。

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

当一个进程此时处于内核程序临界区并且这个临界区是要访问就绪队列的话，那么在访问之前它会把这个就绪队列上锁。

如果进程此时处于普通程序临界区并且这个临界区是要访问普通的临界资源比如打印机的话，那也会在访问之前上锁。

根据当前运行的进程是否可以被强行剥夺处理机资源这个问题我们又可以引出如下知识点。

“这个进程可以是刚刚被暂停执行的进程,也可能是另一个进程，后一种情况就需要进程切换”这句话我看不明白。

2.2.3、调度器和闲逛进程

解释：

创建新进程会触发“调度程序”是因为创建新进程时就绪队列会发生改变，就绪队列一变就有可能让新进程抢占当前运行进程的cpu。所以创建新进程时“调度程序”要出来工作一下。

进程退出时处理机会空闲，所以“调度程序”要出来工作一下看看选谁上处理机。

运行进程阻塞时“调度程序”也要出来看一下。

I/O中断发生时可能使得某些阻塞进程回到就绪态，所以“调度程序”需要出来看一下

如果一个系统支持的不仅是进程，还支持线程，那么“调度程序”它支持的对象就变成了线程。

闲逛进程就跟你没事干的时候抖腿一样。

0地址指令就意味着不需要访存，甚至不需要访问cpu中的任何一个寄存器，因此这种指令使得cpu能耗比较低。

“闲逛进程”（Idle Process）在操作系统中是一个用于填充CPU空闲时间的特殊进程，当没有其他进程需要运行时，操作系统会将CPU资源分配给闲逛进程。闲逛进程的主要目的是确保CPU不会处于完全空闲的状态，而是处于一种可用状态等待工作。因此，它是计算机操作系统在“无事可做”时保持正常运行的基本组件。

闲逛进程的作用：

填充CPU空闲时间 闲逛进程用于在没有其他进程需要执行时占用CPU资源，避免CPU完全空闲。CPU的设计通常是为了解决多任务并发处理的需求，而闲逛进程帮助CPU在没有工作负载的情况下依旧保持“忙碌”，以便随时可以响应新的任务。保持系统稳定性 有了闲逛进程后，CPU调度器始终有一个“备胎”进程可以分配资源，这样即使没有其他用户进程或者系统进程，CPU也不会停顿或出错，这确保了系统稳定性。低优先级 闲逛进程的优先级是最低的，任何其他进程一旦准备好运行，闲逛进程都会立即被挂起，让出CPU资源。它的存在不会干扰正常的系统任务或用户任务。能耗优化 一些现代CPU在执行闲逛进程时会进入低功耗状态，从而减少能源消耗。这对笔记本电脑、手机等设备特别重要，因为它可以有效延长电池寿命。周期性检查中断 在某些系统架构中，闲逛进程会执行一个简单的“空指令”循环，例如0地址指令，确保CPU在等待的过程中周期性地检查中断信号。一旦有硬件或软件中断发生，CPU可以立刻响应。

举例：

比如在Windows系统中，闲逛进程表现为“System Idle Process”，通常显示在任务管理器中。当其他进程在等待资源时，CPU利用空闲时间执行这个进程，并根据系统需求快速转入其他任务。

2.2.4、调度算法的评价指标

甘特图后面会讲。

如果你上厕所需要一分钟，排队等了十分钟，那你肯定感觉很糟糕。而如果你上厕所需要一个小时，排队等了十分钟，那你感受就还挺好的。

因此又提出了一个带权周转时间的概念。

进程等待I/O完成的期间其实是在被I/O设备服务的，这种时间是不能算到等待时间里的。？？？合理吗。就算I/O准备好了，进程不也得再放到就绪队列里等着被调度被服务吗？？？

等待I/O完成有可能是I/O正在做进程的作业。

2.2.5、调度算法（1）

对于p3这个进程来说，他的体验会特别糟糕。

“事实上就是等待时间越久的越优先得到服务”这句话需要理解一下

可以尝试用数学证明一下SRNT的平均等待时间、平均周转时间最少。

用户作假的情况即它本来是长进程，却故意把自己的运行时间说得很短。

注意看这个公式，我觉得分子上放个“被要求服务时间”的作用就是保证响应比大于等于1，仅此而已。

它是不是和带权周转时间有一些相似之处呢。

因为早期的批处理系统计算机价格很昂贵，所以人们更追求系统的整体表现而不是用户体验是情有可原的。

2.2.6、调度算法（2）

RR是伴随着分时操作系统的诞生而诞生的。

说明什么是时间片轮转调度算法？系统设计时如何确定时间片的大小？时间片大小的通常范围值是多少？

答：轮流让就绪队列中的进程依次执行个时间片(每次选择的都是排在就绪队列队头的进程)，被换下来的进程放在队尾。

为调度程序确定时间片的大小时，通常要考虑到以下几个因素：

– 系统对响应时间的要求；

– 就绪队列中进程的数目；

– 系统的处理能力；

时间片是一个较小的时间单元，通常为10ms到100ms。

实现时间片轮转调度算法需要哪些特定硬件和软件的支持？

答：需要的硬件：可编程间隔定时器、可编程中断控制器。

需要的软件：进程控制块、就绪队列、进程调度程序、时钟中断处理程序。

在采用时间片轮转调度算法的系统中，进程在CPU上的剩余执行时间的初始化在什么时候进行？初始值为多少？该值的更新在什么进行？时钟中断由哪个硬部件触发？

答：初始化在进程调度后进行。初始值与时间片长度相同。该值的更新在时钟中断处理程序执行的过程中进行。时钟中断由可编程间隔定时器触发。

因为前台进程是用户能看到运行情况的，所以为保证流畅它们的优先级要比后台进程更重要。

“某进程在就绪队列中等待了很长时间，则可以适当提升其优先级”和高响应比优先算法类似，都是等待时间长了的话就会提高响应比/优先级。所以也可以认为高响应比优先算法也是一种动态优先级调度算法。

这一页ppt待会再看，结合例题一点一点分析。

这个地方要看一下视频里的动画2.2_6_调度算法（2）_哔哩哔哩_bilibili

2.2.7、调度算法（3）

固定优先级用户体验不好，如果一直有系统进程占用，那你打字永远不会被响应。所以时间片划分更合理一些。

2.3.1、进程同步、进程互斥

异步执行的程序速度不可预知。

有的情况下我们需要保证进程间的推进顺序是可预知的。

2.3.2、进程互斥的软件实现方式

while(turn != 0);注意这里的循环，它已经用";"结束了，所以它下面的代码critical section;turn = 1;remainder section;不是循环体。

如果两个程序并发执行，则可能会遇到下面的问题。

如果两个程序并发执行，则可能会遇到下面的问题。

13678不对吧？？

主要看16278

2.3.3、进程互斥的硬件实现方式

注意这段逻辑是用硬件实现的，c语言只是描述一下逻辑。

可以上网查一下为什么TestAndSet适用于多处理及环境，涉及到总线相关的特性。

2.3.4、互斥锁

这也有问题，和整形信号量面临的是同一个问题。？？？

2.3.5、信号量机制

这里有一个问题，既然wait是原语，不可被中断，那么是不是当前正在执行while循环的进程一直不会被切换呢，这个地方可能不太严谨，可以搜一搜看。很多经典的教材中都是这么写得，所以这个地方我们姑且认为它没有问题，不会导致一个进程一直占用处理机的情况吧。搜一下！？？？

此处有动画2.3_5_信号量机制_哔哩哔哩_bilibili

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

2.3.7、生产者-消费者问题

以上图为例，如果两个生产者进程可以并发访问缓冲区，则可能会同时往一块内存区域写，导致混乱。

还有很多其他问题可自行想像。

所以各进程必须互斥地访问缓冲区。

“互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少”这句话是针对这个题（单一缓冲区的生产者消费者问题）来说的。弹幕里看到这么几句话可以帮助理解：“这里同步就是两个资源，空位资源开始为n，由生产者消耗，消费者补充；数据资源开始为0，由生产者补充，消费者消耗”。“互斥信号量初始值一般是资源可用数量，这里是缓冲区所以是1”

再考虑一个问题，生产产品和消费产品能否放到PV操作之间？

从逻辑上看没有问题，但是如果把这两部分的处理放到PV操作之间，那就会导致临界区代码变得更长，也就是说一个进程对临界区上锁的时间会更长，肯定不利于各个进程交替使用临界区，应该让临界区的代码尽可能短，所以，为防止影响系统效能，不应该把生产产品和消费产品放到PV操作之间。

2.3.8、多生产者-多消费者问题

本问题特点：各个生产者生产的东西不一样，各个消费者消费的东西也不一样。

对“多生产者-多消费者问题”的理解，所谓的“多“不是”多个“，而是”多类“。

做题时先写同步信号量，再加互斥信号量。

我们应该把进程同步问题理解为某一个事件一定要求发生在另一个事件之前 而不是某一个进程的行为要发生在另一个进程的行为之前。

2.3.9、吸烟者问题

finish的定义是抽烟者是否完成，所以初值是0（未完成）。

当然你也可以定义 table的信号量来表示桌子是否为空，这样初值就为1（为空）。

你选择定义成finish还是table影响后面代码的写法。

如果选用table那么供应者中的P（table）要放在if之前了。消费者中的V(table)位置不变。

2.3.10、读者写者问题

数据不一致的问题指的是，比如，读者1读走了前三条数据之后，切换为写者，写者把第四条数据更改了，这时又切换为读者1，这时它读的第四条数据就不是自己原来想读的那一条了，这就是数据不一致的问题。

数据错误覆盖问题不再解释。

如果源源不断地读进程进来读，第一个读进程会上锁，最后一个读进程才会解锁，会让写进程”饿死“。怎么解决呢。

有rw的可以进屋子，有w的可以站在门口第一排。

如果是一个写进程站在第一排，那么其他进程就不能站在第一排了，这个时候它只要等屋里的进程开锁之后，就能进屋上锁了（如果屋里没人，直接进屋上锁）。

如果是读进程站在第一排，它如果是第一个要进屋的读进程，那等屋里的写进程解锁以后（或者屋里没人根本没锁），它就得进屋上锁，上锁之后它就会让渡站在第一排的权利。这时如果又有读进程站在第一排，那它就可以直接进屋，不需要等屋里解锁，因为是熟人嘛。而这时如果写进程站在第一排，就需要等屋内解锁，因为不熟。

站在第一排的权利是先来先得的。

可以上网搜一下如何真正实现”写优先“。？？？

2.3.11、哲学家进餐问题

下面看一个代码例子，分析它的问题。

情况一：假设0号在拿起左边的筷子后切换回了2号，则2号会被阻塞，一直到0号拿到右边的筷子开始吃饭后，2号才可以顺利地拿起自己左边和右边的筷子吃饭。 这样其实2号左右两边的筷子都可以用的时候也没被允许抓起筷子。

情况二：假设0号拿起两只筷子开始吃饭后，1号想拿左边筷子时它会阻塞，此时如果发生调度，2号想拿起筷子，但由于1号已经对mutex执行力p操作，所以2号会阻塞。这样其实2号左右两边的筷子都可以用的时候也没被允许抓起筷子。

情况三：假设0号拿起两只筷子开始吃饭后，四号想拿筷子，它在拿右边筷子的时候会阻塞。

？？？

2.3.12、管程

感觉这一节不是很清楚呢 ？？？

full用来存生产者进程的队列，empty用来存消费者进程的队队列。

上面代码是伪代码。并且省去了对缓冲区进行描述的数据结构。

2.4.1、死锁的概念

后面会细讲

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

如果源源不断地有A、B进程进来，则会导致C进程饥饿。

第二个缺点举例：比如P3需要使用5号资源打印机和7号资源扫描仪，但实际使用过程中P3是需要先使用扫描仪再使用打印机的，但由于编号递增申请资源的要求，进程又必须先申请占有它暂时用不到的资源-打印机，之后打印机会空闲很长时间，直到扫描仪使用完了才会回头使用打印机资源。所以这就造成了打印机资源长期空闲，导致系统资源的浪费。

第三个缺点举例：比如P3需要使用5号资源打印机和7号资源扫描仪，用户就需要先编写申请打印机资源的代码再编写申请扫描仪资源的代码。而如果换一个系统，另一个系统打印机和扫描仪的编号刚好相反，打印机7号，扫描仪5号，用户程序就要为此发生改变，需要把申请扫描仪的代码放到申请打印机的代码之前，所以用户编程很麻烦。

此小节介绍的预防死锁的策略或多或少都存在一些缺点。

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

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

上图中P2被阻塞，因为他申请的资源已经被全部分配出去了。P2正常执行。

这种方式相当于找到了一个安全序列P1 P2 ，所以系统处于安全状态的。

上图中P1 P2 就是死锁状态。P3是正常的。

可以上网查一下死锁定理的证明 ？？？

可以自己试着实现一下死锁检测算法。

剩余章节：王道操作系统笔记（非常完整！包学包会！融入笔者自己的思考！）