【README】

1.本文内容总结自 B站 《操作系统-哈工大李治军老师》，内容非常棒，墙裂推荐；

2.操作系统使用信号量实现进程同步（合作），走走停停，推进多进程合理有序向前执行；  
3.靠临界区保护信号量，靠信号量实现进程同步；

---

【1】为什么保护信号量

0）信号量

• 定义： 一个整型数字；通过对信号量的访问修改，实现多进程同步（合作），有序执行；

1）问题

• 存在多个进程同时对信号量（如empty）进行访问修改的场景，对信号量的修改存在并发问题；
• 如 进程1，进程2 同时对信号量（empty）进行减1， 则可能出现信号量减1而不是减2的结果；这就会导致消费者只唤醒一个生产者进程而不是两个生产者进程；这是有问题的；

 图解： 并发问题例子，empty = -1，但有2个生产者进程睡眠，这说明empty信号量的值是错误的；

---

【2】竞争条件

1）竞争条件：

• 和调度有关的共享数据语义错误；

 图片解说：

• 第i次，与第j次执行的顺序不同，最后进程p1和p2的信号量empty的值肯定不同；
• 第i次执行得到的信号量empty是错误的，第j次是正确的；

错误和调度顺序有关；

• 不知道什么时候发生时钟中断，时钟中断就会执行进程调度算法 ；

2）解决竞争条件的方法

 上图显示的执行顺序如下：

 其中，以下代码只允许同时只有一个进程P来访问；
【代码段1】

P.register = empty
P.register = P.register – 1;
Empty = P.register

---

【3】临界区

1）临界区定义：

• 同一时间段，一次只允许一个进程进入的代码段，如代码段1；

补充： 临界区中存放操作信号量的代码；

 3）重要工作： 找出进程中的临界区代码 ；
4）读写信号量的代码一定是临界区；
5）进程代码结构

6）如何编写临界区代码

• 实际上是  进入区， 退出区的代码如何编写的问题； 这是我们要解决的核心；

---

【4】临界区代码的保护原则

0）3个原则

1. 互斥进入；
2. 有空让进；
3. 有限等待；

1）基本原则： 互斥进入（或不能同时进入）： 如果一个进程在临界区中执行，则其他进程不允许进入； （原则1）

2）好的临界区保护原则

• 有空让进：（原则2）
• 有限等待；（原则3）

---

【4.1】进入临界区的一个尝试-轮换法

轮换法解说：

• 进程P0：turn不等于0则空转，等于 0就进入临界区；执行完成后，设置turn为1，让出执行资源给P1执行；
• 进程P1：turn 不等于 1则空转，等于1就进入临界区；执行完成后，设置turn为0，让出执行资源给P0执行；

轮换法问题：

• P0执行完剩余区后，无法再次从while(turn!=0) 开始执行，即便资源空闲，这是有问题的（不满足有空让进原则）；

---

【4.2】进入临界区的方法2 -值日（轮转）

 1）轮换法类似于值日；
2）问题：可能丈夫妻子都去买了牛奶，买了两瓶牛奶，不满足需求（我们只买一瓶牛奶）；
3）改进方法： 无论丈夫还是妻子，买牛奶前，在冰箱上留便条以示标记；

---

【4.3】进入临界区的方法3-标记法

 

图片解说： 由左边代码 改进为 右边代码leavenote；

1）标记法的问题（两个进程不同执行顺序造成的死锁问题）；
                                         表1 两个进程不同执行顺序造成的死锁问题

 两个进程都阻塞，则发生了死锁，程序挂起；即 进程p0 p1的进入请求会无限等待（不满足有限等待规则）；
底层原因在于， 进程1，进程2 依据的是不同变量来判断是否应该执行，而不是同一个变量，若是同一个变量就可以解决；

补充：回到买牛奶的场景：根据表1的执行顺序，那丈夫和妻子都会看到对方留了条，都不会去买牛奶，这就造成了死锁；

2）解决方法-非对称标记

 非对称标记执行细节（丈夫比妻子更加忙碌：丈夫看见妻子留条了，还是会继续等待；而妻子看见丈夫留条了，不会等待直接跳过并撤销留条）

 

---

【4.4】进入临界区方法4-Peterson 算法

1）结合了标记和轮转两种思想；

【代码解说】

• 1）加了一个 turn；可以看到进程p0 进程p1 同时把 turn 作为判断条件，因为turn的值要么0，要么1，p0 p1对应到 turn的不同值，则p0 p1 一定是互斥进入；
• 2）peterson算法，是标记轮转算法，其中标记指的是 flag，轮转指的是turn；
• 3）peterson算法的正确性
  • 满足互斥进入；
  • 满足有空让进；
  • 满足有限等待；

 问题： 上述是2个进程同步执行的调度算法；多个进程会怎么办 ？

• peterson算法无法解决多个进程的调度场景，引入面包店算法；

---

【4.5】进入临界区方法5-面包店算法（取号）

1）进程进入临界区之前，取号（非0标记）；

• 进程离开临界区把序号设置为0；调度时，每次让最小的号进入临界区；

2） 面包算法正确性

 
小结： 面包店算法的代码实现有点复杂；

---

【4.6】临界区保护的方法6-开关中断（仅作用于单cpu，多cpu会失效）

1）引入软硬件协同设计思想，如为了让一个路由算法执行更加高效，需要对路由器硬件做一些改进；
2）回顾临界区定义：

• 只允许一个进程进入； 进入另一个进程意味着什么？
• 是因为调度，进程切换造成了一个进程进入临界区；

3）被调度：另一个进程只有被调度才能执行，才可能进入临界区；

• 而调度是由 时钟中断 触发 schedule函数实现的；

 如何阻止调度？ 调度是通过时钟中断起作用，关闭时钟中断就阻止了调度；

 通过开关中断在 系统多cpu情况下不起作用；
因为：

• 进程1发出的关中断指令只能作用于当前cpu，不能作用于进程2所在cpu2；
• 所以进程1的关中断，没办法阻止进程2执行；进程2一旦执行，它就可以操作同一个内存地址的信号量如 empty，还是可能造成并发问题；

---

【4.7】临界区保护的硬件原子指令法 （方法7）

写在前面： 硬件原子指令法，是引入软硬件协同设计思想后的产物；
1）背景
为了多进程合作，交替执行，不出错，采用临界区保护信号量使得同时只能允许一个进程进入； 算法设计如下：

• Step1）上锁；
• Step2）执行临界区代码；
• Step3）开锁（解锁）；

上锁，开锁，其实都是对变量进行操作；
如以 mutex作为变量，mutex=1表示有资源，可以进入，即锁是开着的；而mutex=0表示没有资源，不能进入，当前进程阻塞，即上锁状态；

【上锁问题】

• 我们临界区保护信号量一次只允许一个进程进入；
• 那对mutex的修改是不是也需要保护，即一次只能允许一个进程修改mutex；mutex修改完成后才允许其他进程进入；

2）mutex修改代码的问题
2.1）修改mutex伪代码

 

2.2）问题

• 在进程p1执行完步骤2后，调度程序（中断）把cpu切换到进程p2执行，也执行到p2的步骤2；
• 执行p2的步骤2，又再切回到进程p1的步骤3执行，然后再切回到进程p2的步骤3执行；
• 这样的问题是 ， mutex只减了一次1，而不是业务逻辑上的 应该减两次1；

小结：

• 为了保护临界区，引入了mutex变量，结果mutex变量的修改也存在并发问题，那是不是还要引入新的变量来保护mutex………. 这就没完没了了；

3）修改mutex存在并发问题的解决方法

• 使用原子性操作，即 上述mutex伪代码中3个步骤的3条指令，转为1条硬件指令，该指令执行期间，不允许cpu切换（调度） ，这就可以保证mutex修改的正确性；
• （原子性，要么全部成功，要么全部失败，中途cpu不会切换）；

4）硬件原子指令例子-testAndSet（里面的操作要么全部成功，要么全部失败，中途不会切换）

// 原子指令 TestAndSet
boolean TestAndSet(boolean &x) 
{
	boolean rv = x;
	x = true;
	return rv;
}
// 临界区加锁开锁代码 
while(TestAndSet(&lock))
{
	临界区;
	lock = false;
	剩余区; 
}

原子指令代码解说：

• 情况1：当x（或lock锁）等于false，表示没有锁，则 rv赋值为false，x赋值为true，返回rv=false；接着while循环结束，进入临界区；（因为执行原子指令时，lock等于false没有锁，那进程进入把lock设置为true，即上锁，然后进入临界区）
• 情况2：当x（或lock锁）等于true，表示已经被锁了，则 rv赋值为true，x赋值为true，返回rv=true；接着while循环继续，当前进程阻塞直到lock为false（其他进程开锁）

5） 有个问题： 硬件原子指令是否适合多cpu的情况？

• 答案是 肯定适合；
• 因为原子指令是硬件层面设计的，即cpu设计实现的，cpu在设计原子指令时，可以把操作的变量所属内存地址加锁；

---

【总结】用临界区保护信号量，用信号量实现进程同步

1）信号量定义：

• 一个整型数字；通过对信号量的访问修改，实现多进程同步（合作），有序执行；

2）临界区定义：

• 同一时间段，一次只允许一个进程进入的代码段；

3）信号量是一个整型数字，对信号量的修改存在并发问题，所以用临界区保护信号量；
4）使用临界区保护信号量，那临界区也需要保护，临界区保护原则如下：

• 互斥进入；
• 有空让进；
• 有限等待；

5）临界区保护的7种方法

1. 轮换法；
2. 值日；
3. 标记法；
4. Peterson-标记轮转法；
5. 面包店算法；
6. 开关中断；
7. 硬件原子指令法；

6）临界区保护信号量

• 一旦临界区保护住了信号量，信号量在执行过程中就会变成语义就会正确；
• 信号量语义正确后，根据这个语义就可以实现多个进程什么时候执行，什么时候唤醒，什么时候阻塞，就实现了进程在适当时候阻塞，适当时候推进，实现了多个进程合作的合理推进；
• 用临界区保护信号量，用信号量实现进程同步，这是进程合作，进程同步的完整故事；

7）对信号量修改，采用硬件原子指令，要么全部成功，要么全部失败，中途不会切换；