1 进程同步与互斥
1.1 进程同步
1.1.1 必要性
进程具有异步性的特征，异步性是指各并发执行的进程以各自独立的、不可预知的速度向前推进，可能导致我们的程序不按期望的顺序前进，进而产生错误的结果。由此，操作系统引入了进程同步
1.1.2 什么是进程同步
可以理解为进程之间必须按照一定的先后顺序执行
1.2 进程互斥
1.2.1 必要性
1.2.2 什么是进程互斥
1.2.3 进程互斥的逻辑过程
注意：
1.2.4 实现进程互斥的原则
1.3 总结
2 进程互斥的软件实现方法
2.1 总览
2.2 单标志法
2.2.1 算法思想
背后的逻辑是谦让
2.2.2 实例
对于P0、P1进程，假设有这样一对执行代码
则它们的执行过程为
2.2.3 缺点
2.3 双标志先检查法
2.3.1 算法思想
它背后逻辑是表达意愿
2.3.2 实例
则进程P1、P2在访问临界资源之前，会首先检查其他进程是否在使用（表达自己想使用的意愿），只有没有人在访问的时候才进行访问。
2.3.3 缺点
试想，当P0在执行到②时，P0的时间片被用完，P1执行⑤，发现此时没有进程在访问，于是继续执行。这样，就会造成同时访问临界资源的情况。
2.4 双标志后检查法
2.4.1 算法思想
2.4.2 实例
P0、P1在使用进程时，首先表达自己想使用的意愿（将自己赋为true），即首先进行上锁，接着再检查是否有别的进程希望使用，如果没有那么自己就可以使用了，如果有那么就等待其他进程结束。
2.4.3 缺点
试想，假如按照①⑤②⑥的顺序执行，则P0、P1都想访问资源，造成的结果就是全部都在等对方访问结束，于是发生死锁，谁都访问不了。
2.5 Peterson算法
2.5.1 算法思想
进程在使用资源前，先表达自己想要使用的意思，接着再表示可以优先让其他进程使用
2.5.2 实例
重在理解算法的思想。
根据Turn的值就可以判断出到底是哪个进程最后表达了谦让的意思
2.5.3 缺点
试想，P0始终没有去访问资源，但是在该算法中，P0始终占用着处理机，使处理机处于”忙等待“的状态。
2.6 总结
3 进程互斥的硬件实现方法
3.1 总览
3.2 中断屏蔽方法
3.2.1 算法思想
3.2.2 实例
3.2.3 缺点
事实上，中断屏蔽只可以屏蔽一个处理机，而并不能影响其他处理机，所以如果其他处理机上有进程在访问临界资源就会出错。
3.3 Test and Set指令（TSL）
3.3.1 算法思想
3.3.2 解释
假设P0要进行访问操作。当Lock原来为False时，则说明没有进程在访问，此时P0可以访问。而当Lock为True时，说明此时有其他进程在访问，P0一直执行while代码段，且Lock一直被置为True，直到其他进程访问完毕并将Lock置为False，P0才可以跳出while循环进行访问。
优缺点
3.4 Swap指令（或称为exchange、XCHG）
3.4.1 算法逻辑
3.4.2 解释
基本上与TSL算法的逻辑是一样的
3.4.3 优缺点
与TSL一致。
3.5 总结
4 互斥锁
4.1 解释
4.2 注意
例如我们之前学习的使用一个while循环来实现加锁功能的代码就是自旋锁
4.3 缺点
4.4 特性
5 信号量机制
5.1 总览
5.2 什么是信号量机制
5.2.1 什么是信号量
5.2.2 什么是原语
5.2.3 “一对原语” 指的是什么
5.2.4 什么是信号量机制
既然信号量可以是多种类型，自然而然的我们就想到要去探讨这些不同的类型。
5.3 整型信号量
5.3.1 解释
它与一般的整型变量的区别在于，它只有初始化、P操作、V操作三种操作
5.3.2 实现过程
5.3.3 缺点
假如进程一直得不到资源，那么它就会一直占用处理机。
5.4 记录型信号量
5.4.1 解释
5.4.2 信号量的定义
5.4.3 PV操作的定义
5.4.4 实例
假设有四个进程都想使用打印机，如图。且打印机的数量S为2台
（1）P0最先执行，先执行wait，它会将S-1，并转入使用打印机的代码。接着，P1执行，先执行wait，它也会将S-1，并转入使用打印机的代码
（2）P2执行wait时先将S-1，此时S<0，为-1。故P2执行BLOCK原语，将自己加入阻塞队列。P3的执行过程与P2类似。此时，S=-2，阻塞队列中有2个进程
（3）P0执行打印机完毕，它会执行Signal，将S+1，此时S=-1，执行Wakeup原语唤醒阻塞队列，于是最先进入队列的P2开始使用打印机。接着，P2执行打印机完毕，它会执行Signal，将S+1，此时S=0，执行WakeUp唤醒阻塞队列，于是队列最前的P3开始使用后打印机。
（4）最终，P1使用打印机完毕，它会执行Signal，将S+1，此时S=1，无须执行wakeUp。接着P3使用打印机完毕，执行SIgnal将S+1，此时S=2，无须执行WakeUp。
5.4.5 特征
PV操作上是一种低级的进程通信原语，它是不可以被中断的。
5.5 总结
6 信号量实现进程互斥、同步、前驱关系
6.1 总览
6.2 信号量实现进程互斥
6.2.1 步骤
注意：划分临界区指的是分析哪些资源应该被划分为临界资源（比如打印机的使用、摄像头的使用)
6.2.2 信号量的数据结构
6.2.3 mutex的具体实现过程
6.2.4 实现互斥的逻辑
Mutex相当于一个访问临界资源S的名额。进程在试图访问一个临界资源时，首先执行P操作，将S-1，假如此时S<0，说明此时S没有名额访问，进程将自己加入阻塞队列；假如S>=0，说明S可以访问。进程执行V操作将S+1，假如此时S<=0，说明阻塞队列中有进程在等待访问资源，执行唤醒操作。
6.2.5 注意点
6.3 信号量实现就进程同步
6.3.1 什么是进程同步问题？
6.3.2 实现的步骤
（1）假设P1的②必须在P2的④之前执行。如图
（2）使S的值初始为0
关于S的理解：
（3）描述
6.4 信号量机制实现前驱关系
6.4.1 什么是前驱关系
如图，里面包含了很多前驱关系，比如S1->S2，S1->S3，S2->S4…
6.4.2 解决思路
结合之前实现进程同步的思路，在前面执行的进程必须有该种资源的V操作，在后面执行的进程必须有该种资源的P操作，资源的初始值设为0。
由于不同的前驱关系相互不会造成影响，所以每一种前驱关系都对应一种不同的临界资源，
3. 具体实现
6.5 总结
7 生产者-消费者问题
7.1 PV问题的分析思路
7.2 问题描述
示意图如下：
7.3 问题分析
7.3.1 关系分析（确定有哪些）
题目中一共有3个进程，分别为生产者生产进程，消费者消费进程，访问缓冲区的进程。
他们的同步互斥关系为
（1）只有当缓冲区不满时，生产者才可以生产
（2）只有当缓冲区不空时，消费者才可以消费
（3）同一时间只可以有单独的对象访问缓冲区
7.3.2 整理思路（确定PV操作的大致顺序）
因为有三个同步互斥关系，可以设置三种资源。
（1）缓冲区不满的资源：Empty
（2）缓冲区不空的资源：Full
（3）缓冲区的资源：Mutex
它们的关系如图：
7.3.3 设置信号量
初始时，缓冲空间内没有物品，为空。且缓冲空间没有被访问，为1
Empty，初始为n（同步信号量）
Full，初始为0（同步信号量）
Mutex，初始为1（互斥信号量）
7.4 代码实现
7.4.1 关于生产者
生产者在生产之前需要先申请一个空位置（Empty-1），对应Empty的P操纵。之后需要申请缓冲空间的使用（Mutex-1），对应Mutex的P操作。之后先进行Mutex的V操作，释放缓冲区的资源。可以思考，生产者会不会执行V（Empty）呢？答案是不会，因为生产者肯定不会使资源减少，它在生产之后会使Full+1，对应Full的V操作。
7.4.2 关于消费者
消费者在消费之前需要先申请一个资源（Full-1），对应Full的P操作。之后需要申请缓冲空间的使用（Mutex-1），对应Mutex的P操作。之后先进行Mutex的V操作，是否缓冲区的资源。可以思考，生产者会不会执行V（Full）呢？答案是不会，因为消费者肯定不会使资源增加，它在消费之后会使Empty+1，对应Empty的V操作。
7.4.3 关键代码
While(1)表示生产者会一直不断的生产、消费者会一直不断地消费
7.5 能否改变相邻P、V操作的步骤
1. 改变相邻P操作的顺序
对于生产者，假如它会先申请Mutex，再申请消耗一个空闲区；对于消费者，它会先申请Mutex，再申请消耗一个Full空间。那么，假如此时Empty=0，Full为n，那么生产者会进入睡眠，等待消费者消耗产品并将其唤醒；而消费者发现Mutex没有多余，所以它会等待生产者使用完Mutex将其唤醒。此时二者相互等待对方的唤醒，进入了死锁。
可以看出，不可以改变相邻P操作
2. 改变相邻V操作的顺序
对于生产者，先执行V（Full）再执行V（Mutex）都是起到释放资源的作用，不会造成死锁。对于消费者同理。
3. 将生产者生产资源的过程加到PV操作之间逻辑上并不会造成死锁，但是这样会造成进程访问临界资源的时间过长，不利于系统的稳定。对于消费者同理。
7.6 总结
只可以生产一种产品的单生产者
8 多消费者-多生产者问题
8.1 PV问题的分析思路
8.2 问题描述
解释：多个生产者生产不同类别的产品，多个消费者消费不同类别的产品，存储空间的容量有限
示意图：
8.3 问题分析
8.3.1 关系分析（确定同步互斥关系）
（1）进程
共有四个进程
父亲生产苹果、母亲生产橘子、女儿消费苹果、儿子消费橘子
（2）同步关系
①只有当盘子中有苹果时，女儿才消费苹果
②只有当盘子中有橘子时，儿子才消费橘子
③只有当盘子中没有水果时，父亲、母亲才生产
（3）互斥关系
四个进程对盘子的访问必须是互斥的
8.3.2 整理思路（确定PV操作顺序）
因为有四种同步互斥关系，因此必须设置四个临界资源
（1）苹果资源：Apple
（2）橘子资源：Orange
（3）盘子资源：Mutex
（4）盘子容量资源：Plate
它们的关系如图
8.3.3 设置信号量
初始时Apple、Orange都没有，为0，Plate中没有水果，初值为n，没有进程访问盘子，Mutex初值为1。
8.4 代码
1. 对于生产者1（父亲）
生产者1首先会申请一个盘子的容量，执行P（Plate），将Plate-1，接着会占用存储空间，执行P（Mutex），将Mutex-1。接着将苹果放入盘子，执行V（Apple），使Apple+1，假如此时Apple<=0，说明此时有消费者在排队消费，会执行WakeUp，唤醒消费者（女儿）进行消费。最后会释放占用的存储空间，执行V（Mutex）。
对于生产者2（母亲）也是类似的操作。
2. 对于消费者（女儿）
消费者1首先会申请减少一个Apple的容量，执行P（Apple-1），将Apple-1。接着，消费者1会申请占用存储空间，执行P（Mutex），使Mutex-1。最后女儿从盘子中取出苹果。接着执行V（Plate）操作，将容量+1，假如此时Plate<=0，说明有生产者在等待，执行唤醒语句，唤醒等待队列中第一个生产者。最后会释放存储空间，执行V（Mutex）。
对于消费者2（儿子）也是类似的操作。
3. 关键代码
4. 改进
因为盘子的容量为1，所以同一时刻最多只有一个进程可以进入盘子，达到了互斥访问的目的。因此当Plate=1时，Mutex可以省略不写。
试想，当盘子容量为2且没有互斥信号量Mutex时，父亲与母亲都可以在同一时间访问盘子，可能会造成错误。
8.5 总结
只可以生产一种产品的多生产者
一个重要的注意点：
9 吸烟者问题
9.1 问题描述
9.2 问题分析
9.2.1 关系分析（确定同步、互斥关系）
我们将供应者分别提供的两样东西视为一体，即：组合1（烟草，纸）、组合2（烟草，胶水）、组合3（纸、胶水）。吸烟者分别需要其中的一种组合
（1）进程
共有四个进程：供应者、吸烟者1、2、3
（2）同步关系
吸烟者1只有在供应者供应组合1之后才可以取走东西。吸烟者2、3同理。
（3）互斥关系
三个吸烟者必须轮流的吸烟（或者说：供应者只有在吸烟者吸完之后才可以再次供应原材料）
9.2.2 整理思路（确定PV操作的大致顺序）
每种关系都需要有一个信号量，同步关系的三个关系为offer1、offer2、offer3，互斥关系为finish。
供应者供应了offer1后（V操作），吸烟者才可以拿offer1（P操作）。只有当三个吸烟者之一吸完烟之后（P操作），供应者才可以供应东西（V操作）
9.2.3 设置信号量（确定信号量初值）
初始时桌子上应该是没有东西的，所以Offer1、2、3的初值都是0。初始时也没有人吸烟，所以finish的初值也为0。此外，由于题目说明吸烟者轮流吸烟，所以还需要一个控制变量，我们设置为整型变量（1代表吸烟者1，2代表吸烟者2，3代表吸烟者3）
9.3 代码
9.3.1 吸烟者
以吸烟者1为例：
吸烟者必须先查看桌子上是否有物品1，进行P（offer1），如果没有，则进入睡眠队列，只有当供应者提供了物品1时才苏醒；如果有就拿走吸完，执行V（finish）操作。
其他吸烟者同理
9.3.2 供应者
通过i的变化循环的为每个吸烟者提供材料。以材料1为例，每供应一个材料，就需要将材料的数量+1，执行V（offer1）操作。供应完之后，就应该等待吸烟者吸完，执行P（finish）操作。
9.3.3 改进
事实上，由于缓冲区的大小为1，四个同步信号量中至多只有一个为1，所以finish互斥信号量是不必要的。
9.4 总结
可以生产多种产品的单生产者
10 读者-写者问题
10.1 问题描述
即：读操作可以同时进行，写操作只可以单独进行
10.2 问题分析
10.2.1 关系分析（确定同步、互斥关系）
（1）进程
共有2个进程，即：读进程、写进程
（2）同步关系
读进程-读进程
（3）互斥关系
读进程-写进程
写进程-写进程
10.2.2 整理思路（确定PV操作的大致顺序）
- 实现读写互斥
为了实现读、写的互斥访问，可以设置一个互斥信号量rw，读操作、写操作之前都需要对其进行P操作。但是这样又会造成读进程只可以互斥的访问文件。 - 实现读读同步
可以增加一个表示读进程数量的变量count。
读进程在访问文件前首先检查count是不是为0：
①如果是，代表该进程是第一个读的，所以需要对文件进行加锁，
②如果不是，代表之前已经有读进程对文件加锁，可以直接读取，并使count+1代表自己在读取文件
进程对文件的访问结束之后会使count-1，代表自己访问结束，并检查count是不是为0：
①如果是，代表自己是最后一个停止访问文件的，应该对文件解锁，执行V操作，
②如果不是，代表后面还有读进程在读取文件，对文件的解锁应该由后面的文件进行，自己可以直接退出。
如图：
（读进程）
（写进程）
- 让读不阻塞
试想，当一个读进程甲执行完对count的检查并准备执行P(rw)时，进程被切换到读进程乙，读进程乙执行完P(rw），此时rw=0，后续进程被切换回读进程甲时，它发现rw已经等于0，于是被阻塞在那里。
出现这种情况的原因是因为进程对count的检查并不是连续的。于是可以增加一个互斥信号量mutex用于实现对count的互斥访问。
读进程在读文件前，执行P(mutex)操作，对count进行访问，即：初始查看count是否=0与使count+1时需要加锁，以及最后的对count-1与检查count是否为0时需要加锁。如图
（读进程）
- 让写不饿死
试想，当一直不断有文件读取文件时，写操作就无法完成。因此，还需要设置一个互斥信号量w，读、写进程在执行操作前对需要对这个信号量加锁，在操作完成之后都需要将这个信号量解锁。如图。此时读进程不再是可以源源不断的占用处理机了，写进程也可以与读进程”同台竞争“处理机的使用机会。
（读进程）
（写进程）
- 验证
接下来，我们对不同的情况进行依次分析
①读甲-读乙
读甲首先执行P(w)，对w加锁，接着执行后续操作实现对count的访问，之后将w解锁。此时读乙就可以进入到文件的读取中。实现了读操作的同步
②写甲-写乙
写甲首先执行P(w)，将w加锁。之后在写操作完成之后才解锁，写乙才可以对文件进行写操作。实现了写操作的异步
③写甲-读乙
写甲首先执行P(w)，将w加锁。之后在写操作完成之后才解锁，读乙才可以对文件进行读操作。实现了读写操作的异步
④读乙-写甲-读丙
读乙首先对w加锁，写甲等待w解锁，当读乙解锁后写甲就可以写，即使进程被切换到读丙，读丙也只可以等待写甲队w的解锁。这样，就实现了写操作不被读操作饿死。
⑤写甲-读乙-写丙
与上述分析类似，注意到：w本质上是实现了读写操作的公平性，即：读操作不会打断写操作。
10.2.3 设置信号量
初始时，文件有一个，没有被分给任何一个进程，rw为1；初始时没有进程读文件，则count初值为0；mutex的初始为1；w了实现写、读的公平必须设置为0（w是同步信号量，而同步信号量初值一般都是设置为0）
10.3 总结
11 哲学家进餐问题
11.1 问题描述
11.2 问题分析
可以看出，这个问题中只有互斥事件，即：对于五个筷子的任何一个，拿起其中的任何一个都必须互斥的进行。因此必须设置5个互斥信号量，为chopstick[5] = {1,1,1,1,1}。初值为1代表初始时各筷子的数量都为1
11.2.1 解决办法
仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。
（1）代码
（2）解释
其中的（i+1）%5是为了能让i=5时（第五个哲学家），他可以拿到1号的筷子。
①当1号哲学家尝试拿起筷子，执行P(mutex)，再拿起筷子0，接着拿起筷子1，假设此时发生了进程切换，切换到3号哲学家，此时出现一种情况：即使该哲学家旁边的两个筷子都在，但是他还是没有办法拿筷子吃饭。
②当1号哲学家尝试拿起筷子，执行P(mutex)，再拿起筷子0，接着拿起筷子1，执行了V（Mutex）操作，假设此时发生了进程切换，切换到0号哲学家，他先执行P（mutex)，并拿起筷子4，此时他右边的筷子没有，此时出现了一种情况：并不能保证只有哲学家两边的筷子都可用时，哲学家才拿起筷子。
（3）基于以上两种情况，该方案更加合适的说法是：
但是不管怎么说，这个方案都是可行的
11.2.2 其他解决办法
11.3 总结
12 管程
12.1 总览
为什么引入管程
我们必须注意到：信号量机制虽然可以有效的解决临界资源的访问问题，但是它的实现方式较为复杂且容易出错，这就给程序的编写造成了很大的困难。引入管程是为了让人们在编写代码时无须关注复杂的PV操作，同时还可以让进程可以同步或互斥的访问某些临界资源（管程可以实现同步、互斥）
12.2 管程的定义与特征
1. 定义
2. 特征
3. 可以类比于Java中的class，管程的几个特征都是为了实现对于资源的互斥访问
12.3 使用管程解决生产者消费者问题
12.3.1 主程序
12.3.2 各进程
较为简单不再赘述
12.3.3 总结
12.4 Java类似管程的机制
12.5 总结
13 总结
本文PDF文件下载链接：提取码：ikun
操作系统，如默默守护的守夜者，无声地管理硬件与软件的交流，为计算机创造和谐秩序。
它是无形的引导者，让复杂的任务变得井然有序，为用户提供无忧体验。
操作系统的巧妙设计，让计算机变得更加智能高效，让人与科技之间的交流更加顺畅。
在每一次启动中，它如信任的伙伴，带领我们进入数字世界的奇妙旅程。
渴望挑战操作系统的学习路径和掌握进阶技术？不妨点击下方链接，一同探讨更多操作系统的奇迹吧。我们推出了引领趋势的💻OS专栏：《OS从基础到进阶》 ，旨在深度探索OS的实际应用和创新。🌐🔍
