哈工大李治军老师操作系统笔记【15】：信号量临界区保护（Learning OS Concepts By Coding Them !）

0 回顾

用信号量可以实现同步，都看信号量来决定走走停停从而实现同步，但是上一课的信号量没有这节课的保护，还是不能工作的，完整的就是靠临界区来保证信号量，靠信号量来实现进程之间的同步

• 两个主题

1. 为什么要保护信号量？为什么会引出临界区的概念？
2. 在实际中是采用什么方法来保护信号量的？

1 为什么要保护信号量？

---

---

• 信号量是一个整型变量

• 通过对整型变量的访问修改，让多个进程有序推进

• 最基础的其实是原子操作，都是在这个基础上这些锁才能实现

• 提出问题

• 信号量的值在多进程共同修改的情况下会有问题

• 如果信号量本身实现的有问题，那又怎么能保证进程间同步的正确性呢？

• 通过本小节的学习，可以使用临界区的保护方法，来保证信号量语义的正确性，那么就可以使用信号量来正确的实现进程间同步

---

---

1.1 竞争条件

---

• 问：既然这样操作会产生语义错误，那么为什么不直接使用empty--？
• 就是说，想让empty--，就得先存寄存器操作一下，然后，再存回去，但是可能还没存回去，时间片就切出去了，所以还是不行
• 并且register那个是寄存器，只不过用c语言的形式表达而已，empty--最后还是会落实到寄存器操作的

---

• 右边的代码就是正确，但是也要考虑时间片用完的问题
• 竞争条件这不是一种编程错误，而是共享数据没有保护带来的语义错误
• 竞争条件是和调度有关的共享数据语义错误
• 所以必须要引出保护机制

1.2 直观想法

• 解决竞争条件的直观想法
• 给信号量的值上锁

---

---

• 生产者P1要修改共享变量了，首先就上锁，就是对其他变量说，我要开始修改了，你们谁也别动了
• 生产者P2来看，发现empty的锁（标记）还在呢，就阻塞，不能往前执行，空转，时间片切出去，还让生产者P1继续执行
• P1执行完，开锁，这时候P2就可以切进来
• 所以一定是empty载入进来，修改完了载出去，也就是empty一定是改完了
• 综上，要不是empty改完了，或者要不是一句都改不了
• 所以对于这种共享变量，要不全部改完，不要竞争；要不我一旦获得可以改的机会，我一定把他全部做完，不能执行中间这个被其他进程抢走了，这样就会发生语义错误
• 所以一段 代码一次只允许一个进程进入
• 原子操作，临界区
• 进程1在执行这个代码的时候，进程2不能进入这个进程1的这段代码，只能一个进程进去，这个代码就叫临界区
• 修改信号量，要想保证大家共享，修改这个全局变量，就必须用临界区保护

1.3 临界区

• 信号量要想表达同步，必须语义正确
• 而语义正确的时候，信号量必须要保护
• 怎么保护？
• 保护信号量那段代码的必须是临界区
• 综上，读写信号量的代码一定是临界区

---

---

• 进程1进去修改他的信号量的时候，进程2绝不能进去执行对应的修改信号量代码

1.4 保护原则

• 基本原则：互斥进入
• 附加原则
• “有空让进”：临界区空闲的时候，应尽快选择出一个进程进入临界区（不能所有人卡着门口，结果一个人都进不去）
• “有限等待”：进程发出请求进入临界区的等待时间必须是有限的，不能出现饥饿问题（不能总是让别人进，我也要尽快进去）

---

---

1.5 轮换法

---

---

• 没轮到当前进程就是空转，一旦轮到你了就进行，完事儿了就出来
• turn是全局变量
• 因为turn在两边只能分别等于0与1，所以说满足了互斥要求
• 但是，P0完成后不能再进入临界区，尽管进程P1不在临界区，不满足有空让进
• 轮换法满足基本的互斥要求，简单的赋值操作可以认为是原子的，不会被打断而出错
• 轮换法不满足“有空让进”，P0完成一次临界区操作后，将turn值修改为1，那么接下来只有当P0也完成一次临界区操作后，才会轮到P0
• 假设P0剩余区的代码很快执行完了，P0再次请求进入临界区
• 而P1剩余区的代码执行非常耗时，假设P1此时在剩余区还要接着运行很长一段时间，那么这段时间，P0就一直在等待，而实际上临界区并没有被占用，不满足“有空让进”
• 轮换法也不一定满足“有限等待”，如果P0完成一次临界区操作后，P1在剩余区死循环，那么P0就永远进不去临界区了，产生了饥饿
• 引出标记法

1.6 标记法

• 轮换法类似于值日
• 先举一个生活中买牛奶的例子，标记法就是类似于留一个便条

---

---

---

• 想进去就打一个标记
• P0要进临界区，就先标记自己，flag[0] = true，然后判断P1的标记，如果P1已经标记，就等待
• 所以思想就是，进临界区之前先标记自己为true，然后等待别的进程的标记变为false
• 每个进程都需要一个标记变量
• 标记法满足基本的互斥要求，不可能同时进入临界区
• 标记法不满足“有空让进”和“有限等待”，会发生死锁，比时两个flag都等于true，互相卡着不让进

---

---

1.7 非对称标记（Peterson）

---

---

• 什么是非对称标记呢？比如说值日，1,3,5就是你，2,4,6就是我，这样就错开了
• 这样把标记和轮转结合，就有了下面的这个算法

---

---

---

• 满足基本的互斥要求
• 两个flag可能同时等于true，但是turn同一时刻只会有1个值，所以不会死锁，满足“有空让进”
• turn不是决定能否进入的唯一条件，一旦对方的flag置为false，我也可以进入，满足“有限等待”
• 这样P0跑一遍，turn = 0；之后P1跑一遍，turn = 1，之后P0就可以进去了，满足有空让进以及有限等待

1.8 面包店算法

• 每个进程想进来先取一个号，这就有标记的含义，离开的时候把这个号置成0就可以
• 两个进程都想进，号码小的先得到服务（轮转的方法）；号码相同时，名字靠前的先服务

这么解释：就是存在一个进程，它希望进去，并且比我有资格进 那我就不进去 相当于我是否能进去取决于别人的情况而不是我的情况

• 面包店算法，仍然是标记和轮转的结合，但适用于多个进程
• 经过前面的铺垫，面包店算法是第一个保护临界区的，可以正常运转的软件方法（不需要任何硬件支持）
• 每个进程进入临界区前先要取一个非0的号，num[i]=max(num[0], ……, num[n-1])+1
  • 这条语句会有指令交错的问题吧？
  • 取的号是一个非递减序列，而不能说是一个递增序列
• 号码最小的先得到服务；号码相同时，名字靠前的先服务
• 缺点：算法很复杂；号码溢出了怎么办？

---

---

• 因为取号的一定比当前的号要打，类似餐厅排队取号
• 号小的肯定先服务

---

---

• 一个显然的感觉是：太复杂了，有没有简单一些的

---

---

• 进入临界区前关中断，进入临界区后开中断，需要硬件支持
• 单核CPU，进程调度依靠的是中断，关了中断（指令cli()是关中断，sti()是开中断），就不会有别的进程插入了，也就不会有指令交错的问题
• 多核CPU下这种方案不好用，所以这种方案时至今日已经不好用了
• 实验五可以使用这种方案，实验的模拟器模拟出来的计算机是单CPU的

---

1.9 原子指令

---

• 什么叫上锁？什么叫另一个进程来看有没有上锁？
• 锁，就是变量，这个人上锁就是让这个变量是0，还是1；如果是1，表示有资源，进去就没资源，变为0，别的进程来看就发现没资源，就空转，进不去
• 但是修改empty保护要用mutex，但是用mutex又要用其他的信号量，禁止套娃
• 所以这个信号量不应该拿其他的信号量来保护，应该硬件直接保护起来
• 这就是硬件原子指令
• 硬件原子指令
• 这里的语句是对这个机器指令的解释，实际CPU里只会执行一条指令，是制造CPU时就设计好了的
• 疑问：之前学习的Java并发的锁的底层和这个TAS有关系吗？
• 疑问：有没有那种可以原子增减的整型变量？
• 疑问：多CPU好用吗？

2 总结

用临界区保护信号量，信号量的语义就正确，语义正确就实现了进程合理推进，用临界区保护信号量，用信号量实现进程同步。