8.CPU调度算法

(1) 算法背景
(2) 调度原则
(3) 调度算法/实时调度/多处理器调度
(4) 优先级反转

8-1 算法背景

简述上下文切换与CPU调度(Schedule)关系：

• 切换CPU当前任务,从一个进程/线程到另一个
• 保存当前进程/线程在PCB/TCB的执行上下文(CPU状态)
• 读取下一个进程/线程的上下文

Q:什么是CPU调度？
答：按照调度算法程序从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个线程/进程。

Q:什么是调度算法程序?
答：挑选进程/线程的内核函数（通过一切调度策略）使得效率最高,满足用户需求;

Q:在进程/线程的生命周期中的什么时候进行调度？
答：在五种进程状态（Start/Ready/Runing/Waiting/Done）切换的时候进行调度,即从一个状态变为另一个状态,特别是和运行（running）相关的状态。

内核运行调度程序的条件(满足一条即可):

• 进程从Runing 到 Wait 状态
• 进程Done(终结)
  不可抢占调度：调度必须等待事件/进程结束,早期OS。
  可以抢占调度：OS决定在何时打断进程,调度程序在中断被响应后执行,当前进程从运行切换到就绪(或者一个进程从等待W切换到就绪R),当前运行的进程可以被换出,现代OS。

针对是用户态的进程:

• 进程在内核中通过系统调用执行,因为系统调用返回时,是到发起这个调用的进程继续执行,所以内核中不会切换/抢占。
• 只要进程在系统调用时不存在从运行态到阻塞态的变化,OS可以确保返回正常。

如果在内核中也允许这种抢占,系统调用返回时不是原来的进程而是另一个优先级更高的进程,就是内核中的抢占。
OS发展：不可抢占 -> 只支持用户态进程抢占 -> 用户态和内核态进程都可抢占

8-2 调度原则

执行模型：程序在CPU突发和I/O中交替;

• 每一个调度决定都是关于下一个CPU突发时将哪个工作交给CPU;
• 在时间分片机制下,线程可能在结束当前CPU突发请被迫放弃CPU;

CPU的占用率是波状,CPU大量运算是高峰,而读写I/O时是平稳的低值;

• CPU使用率：CPU处于忙状态所占用时间的百分比;
• 吞吐量：在单位时间内完成进程数量;
• 周转时间：一个进程从初始化到结束,包括所有等待时间所花费的时间;
• 等待时间：进程在就绪队列中总时间;
• 响应时间：从一个请求被提交到产生第一次应所花费的总时间;

Q:通常选择更快的服务,但什么是更快?

• 高吞吐量（高带宽）
• 低响应时间（低延迟）
• 补充：但两者很难兼顾

用量化的方法来看调度算法：

1. 减少响应时间-即使处理用户的输入并将输出结果提供给用户;
2. 减少平均响应时间的波动 - 在交互系统中,可预测性比高差异低平均更重要;
3. 减少等待时间-每个进程为单位
4. 增加吞吐量(两个方面)

• 减少开销（操作系统开销,上下文切换）
• 系统资源的高效利用（CPU,I/O设备）

桌面系统要求交互 - 低延迟调度增加了交互式表现,
数据中心的服务器更强调吞吐量 - OS需要保证吞吐量不受影响;

Q:调度公平的意义？
每个进程都公平地得到CPU的支持,比如占用相同的CPU时间或等待相同时间;但是公平通常会增加平均响应时间。

8-3 调度算法

调度算法的三大种类：

• 一般性的调度算法
• 针对嵌入式系统的特殊调度算法
• 多CPU多内核的调度算法

(1) 基本调度算法

• 先来先服务(FCFS,First Come First Served) | 不公平,平等等待时间较差;
• 短进程优先(SPN,Shortest Process Next) == 短作业优先(SJF,Shortest Job First ) | 不公平,但是平均等待时间最小,需要精确预测计算时间;
• 短剩余时间优先(SRT,Shortest Remaining Time)
• 最高响应比优先(HRRN,Highest Response Ratio Next) | 基于SPN调度改进,不可抢占
• 轮循(Round Robin) – 公平 但是平均等待时间较差
• 多级反馈队列(Multilevel Feedback Queues) | 和 SPN 类型类似
• 公平共享调度(Fair Share Scheduling) | 公平是第一要素

8.3.1 FCFS
fifo队列规定：如果在进程在执行中阻塞,队列的下一个会得到CPU;

比如下面：进程运行时间短的放在起始位置则周转时间变短;

WeiyiGeek.FCFS案例

优点：简单方便理解
缺点：

• 平均等待时间波动大
• 花费时间少的可能反而排在时间长的进程后面
• 可能导致CPU 和 I/O之间的重叠处理(CPU密集的进程导致I/O闲置时,I/O密集型进程也在等)
• 没考虑进程抢占

8.3.2/.3 SPN / SRT
按照预测的完成时间来将任务入就绪队列之中,既可以是抢占的也可以是不可抢占的;

• 不可抢占(SJF SPN)
• 可抢占(SRT - 短剩余时间优先)

WeiyiGeek.SPN案例

SRT 优点：最小的平均等待时间和周转时间
SRT 缺点：

• 连续的短任务可能导致长任务饥饿,短任务可用时被长任务占用则会增加平均等待时间,不能保证公平；
• 需要预知未来下一个进程的突发时间,比如询问用户,如果用户欺骗就杀死进程。

8.3.4 HRRN
在SPN调度的基础上改进,不可抢占,关注进程等待多长时间,防止无限期推迟;

R最高者优先进程：Wait 等待 / Service 服务/执行
R=(waiting time + service time) / service time,

SPN与HRRN对比：前者只考虑了执行时间,而后者还考虑了等待时间;
优点：防止无限期延迟即进程饥饿(不可抢占);交互性,响应性更好;
缺点：对抢占性的支持不够,也需要预知执行时间;

8.3.5 RR
用时间切片和抢占来轮流执行,提高公平; 在量子切片/时间切片的离散单元中分配处理器,时间片结束时切换到下一个准备好的进程;
线程执行时间单元： (n-1)q

WeiyiGeek.RR线程执行案例

案例：进程所需时间
P1 : 53 , P2 : 8 , P3 : 68 , P4 : 24

P1 P2 P3 P4 P1 P3 P4  P1   P3  P3 
0  20 28 48 68 88 108 112  125 145 153

#等待时间
P1 = (68 -20) + (112 - 88) = 72
P2 = (20 - 0) = 20
P3 = (28 - 0) + (88 - 48) + (125 - 108) = 85
p4 = (48 - 0) + (108 -68) = 88

#平均等待时间
(p1 + p2 + p3 + p4) / 4 = 66

优点:公平相对稳定;
缺点：

• 平均等待时间较长(与时间片有关)
• 按时间片轮流执行增加了上下文切换开销

时间片大小的重要性?

• 时间(量子)片过大：等待时间变长,极限的情况下退化成为FCFS
• 时间(量子)片过小：反应迅速(每个队列中的进程都将被执行),但是上下文切换开销太大

目标：选择一个合适的时间量子,维持上下文切换开销处于 < 1%;

案例：在FCFS和RR中,不同时间片对平均等待时间的影响,进程Pn所需时间与上面案例一致;

WeiyiGeek.时间片对平均等待时间的影响

8.3.6 Multilevel Feedback Queues (多级队列)
就绪队列分为相对独立的队列：前台交互,后台批处理;
每个队列拥有自己的调度策略：前台RR,后台FCFS
调度必须在队列间进行:

• 固定优先级：先处理前台,然后处理后台;可能导致饥饿;
• 时间切片：每一个队列的到一个确定能够调度其进程的CPU/总时间;如80%给前台,20%给后台;

一个进程可以在不同的队列中移动,例如：n级优先级-优先级在所有级别中RR在每个级别中;

1. 时间量子大小随优先级级别的增加而增加;
2. 如果当前时间量子中没有完成,则自动降到下一个优先级;

WeiyiGeek.时间片对平均等待时间的影响

队列的特点：
W等待时间越长,优先级会越来越高;(即前台交互任务,保证公平性)
E执行时间越长,优先级会越来越低;(即后台运算任务,提高效率)

优点：

• CPU密集型任务的优先级下降很快,就随着不断消耗时间量子就下降到低的优先级,I/O密集型任务停留在高优先级;
• 能动态地根据进程的特征来调整队列优先级和调度CPU;

8.3.7 Fair Share Scheduling
公平共享调度,用户层面的公平,适用于多用户共享服务器的场景;
FFS控制用户对系统资源的访问：

• 一些用户组比其他的用户组更重要;
• 保证不重要的组无法垄断资源;
• 未使用的资源按照每个组分配的资源的比例来分配;
• 没有达到资源使用率目标的组合获取更高优先级;

WeiyiGeek.FFS控制

评价调度方法：

• 确定性建模：对确定的工作量计算每个算法的表现
• 队列模型：用来处理随机工作负载的数学方法
• 实现/模拟：建立一个允许算法运行实际数据的系统,最灵活/一般性

总结：

• 上面的都是一些通用计算机调度算法,与实际计算机调度有所差异;（在真实机器上跑一遍因为和硬件也有关系）
• 需要交互性强的进程,我们希望它的优先级较高;
• 公平每个进程占用同等的CPU时间,但会牺牲效率

(2) 实时调度(real-time)

定义：正确性依赖于其时间和功能两方面的一种OS,比如调度火车/工厂,需要确保任务在规定时间内完成的

性能指标：强调时间约束的及时性（deadlines|期限）,速度和平均性能相对不重要。
主要特征：重点是时间约束的可预测性,实时调度算法主要用于嵌入式;

类别：

• 硬件/强实时系统：重要任务在规定时间必须完成;
• 软件/弱实时系统：重要任务优先级更高,尽量完成并非必须完成;

任务/工作单元job：一次计算,一次文件读取,一次信息传递等等
属性：取得进展所需要的资源和定时参数;

案例：

release time 进程处于就绪态的时间
relative deadline  任务是间隔时间段完成,每个任务有个特定的时间,要在特定的时间段内完成
absolute deadline 最终的结束时间

WeiyiGeek.相对于绝对期限

一些列相识任务周期任务,即有规律的重复

• 周期 P= inter - realease time = relative deadline (0 < p)
• 执行时间e = 最大执行时间 (0 < e < p)
• 使用率 / 利用率 U = e / p

(硬时限)Hard real-time—hard deadline：保证确定性

• 错过了最后期限,肯能会发生灾难性或非常严重的后果;

(软时限)Soft real-time—-soft deadline：

• 理想情况下,时限没有被满足,那么就相应的降低要求;

设计算法满足deadline要求,决定实时任务执行的顺序;

1. 静态优先级调度（事先确定）
   描述：在这个任务执行之前,已经把优先级确定下来,然后根据优先级进行调度任务;
2. 动态优先级调度（优先级会动态变化）
   描述：任务的优先级,随着任务的运行而变化,不同时间和不同优先级,有可能导致任务被延迟;

RM(Rate Monotonic,速率单调调度) : 最佳静态优先级调度,通过周期安排优先级,周期越短优先级越高;
EDF(Earliest Deadline First,最早期限调度) : 最佳动态优先级调度,deadline越早优先级越高,执行Deadline最早的任务;

(3) 多处理器调度
多处理器调度算法（多核）,追求负载平衡（load balance）(优点是负载共享)
多处理器的CPU调度更加复杂,多个相同的单处理器组成一个多处理器;

对称多处理器(SMP):

• 每个处理器运行自己的调度程序
• 需要在调度程序中同步

System Bus上连接了两个Physical CPU 然后它再连接Logical CPU;

8-4 优先级反转

原理：低优先级任务占用了某共享资源,高优先级任务不能及时执行(即高优先级任务要等待低优先级任务时发生)

优先级反转的持续时间取决于其他不相关任务的不可预测的行为;
案例：比如火星探路者(进程优先级文问题)

WeiyiGeek.优先级反转问题

原因解析：T3先执行,到t2时访问共享资源,t3时T1抢占,开始执行T1,某时刻需要访问已经被T3占用的共享资源,但T3还没有释放,所以不能继续T1就开始等待,t5时T2又抢占执行,此时T1受制于T2的执行时间,因为T1必须要等T3,导致T1的时间延长了,引起不稳定状态,最后频繁的重启系统;

解决优先级反转方法： 低优先级任务 继承 高优先级任务的 优先级依赖他们共享的资源;(优先级继承 与 高优先级任务共享资源的低优先级任务,其优先级被提升)
优先级天花板: 资源的优先级 和 所有可以锁定该资源的任务中最高优先级的任务 优先级相同;(任务的优先级取决于所占用资源的优先级)

注意点：

1. 除非优先级高于系统中所有被锁定的资源的优先级上限,否则任务尝试执行临界区的时候会被阻塞;
2. 持有最高优先级上限信号量锁的任务,会被继承被该锁所阻塞的任务的优先级;

---

9.同步与互斥

(1) 背景以及概念介绍
(2) 临界区及管理方法

9.1 背景概念介绍

背景：多道程序设计(Multi-Programming)是现代OS中的一个重要特性,需要以下来基础来支撑下

• 并行与并发的概念的引入来支持,
• 进程/线程操作系统抽象出来用于支持多道程序设计;
• CPU调度与调度算法(不同测试)

面试必问Q:什么是并行和并发?
答：并发和并行最开始都是操作系统中的概念,表示的是CPU执行多个任务的方式。这两个概念极容易混淆。

并发 Concurrent： 在操作系统中,是指一个时间段中有几个程序都处于已启动运行到运行完毕之间,且这几个程序都是在同一个处理机上运行;

比如:现在使用的windows操作系统,可以”同时”做很多件事儿(一边看电影/一边聊QQ/一边听歌),这所谓的”同时”,在操作系统底层可能并不是真正的意义上的”同时”;

• 实际上对于单CPU的计算机来说,在CPU中同一时间是只能干一件事儿的,但同一个时间段内可以完成多个事件,不同的事通过时间片分时调度;
• 操作系统是把CPU的时间划分成长短基本相同的时间区间即”时间片”,通过操作系统的管理,把这些时间片依次轮流地分配给各个应用使用
• 给用户的感觉是他在同时的进行听歌和打游戏,实际上在操作系统中,CPU是在游戏进程和音乐播放器进程之间来回切换执行的。
• 操作系统时间片的使用规则：某个作业在时间片结束之前没有完成整个任务,这时该作业将被暂停(等待状态),等待下一次CPU调度执行

并发 Concurrent： 当系统多个CPU(多核处理器)时,当一个CPU执行一个进程时,另一个CPU可以执行另一个进程,两个进程互不抢占CPU资源可以同时进行执行;

比如：两个人吃午饭过程中,你吃了米饭、蔬菜、牛肉;我也吃了米饭、蔬菜和牛肉,这时我们两个人之间的吃饭就是并行的。
两个人之间可以在同一时间点一起吃牛肉,或者一个吃牛肉,一个吃蔬菜,我们之间是互不影响的(但是会影响资源-后面要说到)

• 有多个CPU的情况下,才会出现真正意义上的『同时进行』
• 多个人同时做多件事儿

WeiyiGeek.并发并行

并发并行之间的区别：

• 并发:指的是多个事情,在同一时间段内同时发生了,多个任务之间是互相抢占资源的
• 并行:指的是多个事情,在同一时间点上同时发生了,多个任务之间是不互相抢占资源的

  

  WeiyiGeek.对比图

1.主要讲解协同多道程序设计和并发问题
独立线程：(1)不和其他线程共享资源或状态 (2)缺点性(输入状态决定结果) (3)可重现(能够重现起始条件I/O) (4)调度顺序不重要
合作线程：(1)在多个线程中共享状态 (2)不确定性 (3)不可重现 [2/3一维着bug可能时间接性的发生的]

在实际运行中进程或者线程,计算机/设备需要进行合作;
Q:为什么需要合作?

• 共享资源（嵌入式系统）
• 并行提高效率（I/O操作和计算可以重叠,拆分小任务,流水,并行,多处理器）
• 模块化（大程序分解成小程序,使系统易于扩展）

案例1：程序可以调用函数fork()来创建一个新的进程(拥有相同的代码段),OS需要分配一个新的并且唯一的进程ID;

new_pid = next_pid++  //此时在内核中系统调用执行(共享全局变量),当前系统最高的PID值

//机器指令
LOAD next_pid Reg1  // 将next_pid的值放入到reg1
STORE Reg1 new_pid
INC Reg1           // next_pid++
STORE Reg1 next_pid

假设两个进程并发执行,如果next-pid等于100,其中一个进程PID是101,而next_Pid应该增加到102;

WeiyiGeek.实际情况

我们的希望是无论多个线程的指令序列怎么交替,程序都必须正常工作;不确定性要求并行程序的正确性,一定更要预先思考。

竞态条件(Race condition ):

• 系统缺陷：结果依赖于并发执行的时间点 顺序/时间(不确定性/不可重现)

Q：如何避免竞争？
答：让指令不被打断;

问题1：多个进程会交互对共享资源的访问,如果处理不当就会导致饥饿与死锁。

概念介绍：

原子操作(Atomic Operation)：指一次不存在任何中断或者失败的执行,要么完整执行要么不执行,不会发生部分执行;但实际操作往往不是原子的,甚至单个机器指令都不一定是原子的。 

临界区(Critical Section)： 进程中访问共享资源的代码区域,且当另一个进程处于相应代码区域时便不会执行。
互斥(Mutual Exclusion)：保证只有一个进程处于临界区,不允许多个进程访问同一共享资源.(一个厕所同时只能一个人使用)
死锁(Dead Lock)： 多个进程相互等待完成特定任务,而最终没法继续自身任务
饥饿(Starvation)： 一个可执行的进程长期等待执行,被调度器持续忽略。
锁(Lock) ：获得锁,获得控制权,
解锁(Unlock):释放锁,失去控制权
忙等待(Busy-waiting) ：进程在等待进入临界区时,循环执行无意义操作,浪费系统资源
Progress：希望进入临界区的进程总是能够进入临界区

案例2：操作系统中问题与现实生活中问题类比;

• 存在的问题：两人都去买了面包,却不知道对方也买了面包;
• 1.利用便签(lock)还是会多购买面包;(先判断有无面包,再判断有没有标签(lock)[此时如果发生上下文切换就会导致异常])
• 2.如果将留便签放在第一位可能还是不会去买bread;(先贴上锁,再判断有无面包,再判断有无便签[如果在此之前发生了切换B线程也贴上了标签],所以A不会去买且B到判断时候也不会去买)
• 3.为便签增加标签,进行增加访问过的记录,判断A和B有无访问过;可能导致没有线程去买面包(错误时间的上下文切换可能导致每个进程都认为宁一个进程去买面包了),这就是我们的饥饿问题;

  

  WeiyiGeek.案例2

解决方法：

WeiyiGeek.解决方法

解决方法总结:

• 它是有效的但是不够完美,太复杂了
• A和B的代码不同,每个线程的代码也会略有不同
• A在等待的时候,其实是在消耗CPU的时间,这样的情况叫做忙等待(BUS-WAITING)

案例3:假设我们有一些锁的实现
都是原子操作-如果两个线程都在等待同一个锁,并且同时发现锁备释放了,那么只有一个能够获得锁;

//解决上面的面包问题
BreadLock.Acquire() - 在锁释放前一直等待,然后获得锁
if(nobread)
{
  buy bread
}
BreadLock.Release() - 解锁并唤醒任何等待中的进程

9.2 临界区及管理方法

临界区(Critical Section)的一些主要概念：

• 互斥：同一时刻只有一个线程在临界区里面
• 有限等待:如果一个线程i处于入口区,那么在i的请求被接收之前,其他线程进入临界区的时间是有限制的;
• 无忙等待：[可选]如果一个进程在等待进入临界区,那么在它可以进入之前会被挂起;

保护临界区进程三种方法(互斥实现方式)：禁用硬件中断，基于软件(Peterson算法,更高级的抽象;

• 进入与离开临界区代码ENTER/EXIT_CRITICAL_SECTION
• 比较不同的机制,性能并发级别

(1)硬件中断方法
描述：没有中断，就没有上下文切换,没有并发,减少不确定性。

• 进入临界区时禁用中断
• 退出临界区时开启中断
• 如果两个CPU并行的话一个CPU只能屏蔽自身,另一个仍可能产生中断

禁用中断产生问题：

• 不能进行响应外部硬件设备请求
• 线程无法被停止,整个系统都会停下来,可能导致其他线程可能会饥饿/影响效率;

Q:临界区要是太长咋整？
答：无法限制响应中断所需的时间，可能有硬件影响。一般都用于短的临界区时间。

(2)基于软件的解决方法
两个线程T0和T1,多进程Ti的通常结构,线程可能共享一些共有的变量来同步他们的行为;

#//常规结构
do {
  enter critical_section #//进入区域
  Critical_Section #//临界区
  exite critical_section  #//离开区域
  Reminder_Section  #//提醒区域 
}while(1);


#//1.共享变量初始化(满足互斥但是有时候不满足Progresss)
#//Ti在退出临界区后做其他的事情去了,Tj想继续运行,但必须等待Ti处理临界区

int turn=0; #//初始是Ti进入临界区 
#//对Thread Ti，有： 
do{ 
  while(turn != i); #//busy waiting  (忙等待)   turn == i;//表示进入临界区否则忙等待
      ....
  critical section 
  turn = j;     #//after exit turn=j  
  reminder section 
}while (1);


#//2.改进方法用数组(flag),必须是一种交替循环(如果先flag[i]=1再while循环，满足互斥但可能死锁)
flag[i]==1  #//进程i想进入临界区执行 

int flag[2];flag[0]=flag[1]=0;   #//初始化共享变量
do{ 
  while(flag[j] == 1); # //初始flag都是0，没有满足互斥 
  flag[i] == 1;  #//先请求 想进入临界区执行 
  critical section 
  flag[i]=0; 
  remainder section
}while (1);

上面的方法为下面的实现奠定了基础：
满足进程Pi 和 Pj之间互斥的正解基于软件的解决方法(1981年)：

//use two shared data items
int  turn;       // who ‘s turn to enter the critical section(谁准备好进入临界区)
boolean flag[];  //whether the process is ready to enter(知识进程是否准备好进入临界区)

//PETERSON算法
do{
flag[i] = TURE;  //为真确定做好准备
turn = j;
while(flag[j] && turn==j);  //同时满足进入临界区
    CRITICAL SECTION
    flag[i]=FLASE;   //重新设置为做好准备
REMAINDER SECTION  //提醒临界区
} while(TURE);

Dekker算法(改进)：

WeiyiGeek.Dekker

Eisenberg and Mcguire’s algorirhm：(多进程互斥)对N个进程, 进程i之前的先进入了i再进入，i之后的等i先进入

Bakert算法(排队取号，同号比ID)：类似于银行取号的原理(如果有两个取票机,假如会取到相同的票号,这时再按照顾客的身份证进行排序出不相同的票号),所以当多个进程按照其顺序取票号时候,有可能还要按照进程本身的PID进行排序;
假如N个进程的临界区：

• 进入临界区之前,进程接收一个数字;
• 得到的数字最小的进入临界区;
• 如果进程Pi和Pj收到相同的数字,那么如果i < j,Pi先进入临界区否则Pj先进入
• 编号方案总是按照枚举的增加顺序生成数字;

总结：

• 对于算法的设计最好是满足互斥,前进,有序等待对于临界区的管理;
• Dekker算法(1965)：第一个针对于双线程例子的正确解决方案;
• Bakery算法(1979): 针对于n线程的临界区问题解决方案;
• 产生的问题：
  • 复杂,需要共享数据项
  • 耗资源,需要忙等待,浪费CPU时间
  • 没有硬件保证的情况下无真正的软件解决方法,load store必须要是原子操作;

(3)更高级的抽象方法-主流方式
硬件提供原子操作指令，通过特殊的内存访问电路实现,大多数现代体系结构都这样;
操作系统提供更高级的编程抽象来简化并行编程：例如锁,信号量(硬件源语中构建)实现进入与退出临界区;

锁是一个抽象的数据结构,一个二进制状态(锁定/解锁)：

// Lock::Acquire - 锁释放前一直等待,然后得到锁
// Lock::Acquire - 释放锁,唤醒任何等待的进程
lock_next_pid -> Acquire(); //进入临界区
new_pid = nex_pid++;
lock_next_pid -> Release();  //退出临界区
``` 

大多数现代体系结构都提供特殊的原子操作指令：
- 通过特殊的内存访问电路
- 针对单处理器和多处理器

Test-and-Set 指测试和置位 : 从内存读取值返回该值,测试该值是否为1(返回boolean类型)，并将该内存值设为1;
Exchange 交换指令 : 交换内存中两个值,然后返回;
![WeiyiGeek.语义和执行过程](https://cdn.jsdelivr.net/gh/WeiyiGeek/blogimage/2019/20190420112708.png)


锁的实现：
```bash
#下面是导致忙等版本，适用于临界区较小的情况, 可以支持N个进程的操作且是一样的，都很简洁 
#如果临界区较大，则加入阻塞和唤醒语句，会产生上下文切换开销
#线程在等待的时间消耗CPU周期;
class Lock {
  int lock = 0;
}

Lock::Acquire() {
  """
  1.如果锁被释放,那么testandset读取0并将值设置为1,锁被设置为忙并且需要等待完成
  2.如果锁处于忙状态,那么test-and-set读取1并将值设置为1,不改变锁的状态并且需要循环(自旋pin)
  """
  // test-and-set
  while (test-and-set(lock));
  // exchange
  key = 1;
  while (key == 1) exchange(lock, key);
}

Lock::Release() {
  lock = 0;
}


#无忙等待(采用睡眠的形式)，当它等待其他事件时，可以睡眠/阻塞
class lock{ int value = 0; waitqueue q;}
lock::acquire(){
  while (test-and-set(value)){
  //add this TCB to wait queen q;
  schedule();
  }
}
lock::release(){
  value=0;
  //remove one thread t from q;
  wakeup(t);  //需要进行唤醒
}

利用Exchange来完成进入与退出临界区”

int lock=0;   //初始化 
//to process Ti that want to enter the critical section 
int key;
do{
  key=1; 
  while(key==1) exchange(lock,key); //when key!=1 swap out of (k = 0)时候while退出执行临界区
  critical section     //at that time key=0 lock=1
  lock=0; 
  remainder section 
}while(true)

基于原子操作的机器指令方式优点：

• 适用于单处理器或共享主存的多处理器中任意数量的进程
• 实现简单并且容易证明
• 易扩展到多临界区，开销小，广泛使用

基于原子操作的机器指令方式缺点:

• 还是有忙等浪费CPU时间;
• 抢LOCK随机可能某个一直抢不到，当进程离开临界区，且多个进程在等待时可能导致饥饿；
• 死锁: 一个低优先级的进程拥有临界区，一个高优先级的进程也需求，那么高优先级进程忙等占用cpu,低优先级的不能释放Lock, 要通过优先级反转来解决。

总结：

WeiyiGeek.临界区

• 如果临界区很短的情况下,还是建议选择忙等待状态,因为他们不需要完成上下文切换,否则要引入WAITING和wakeup;
• 用锁来解决互斥问题，锁是高层编程抽象，需要一定硬件支持;
• 常用三种：禁用中断（仅可单处理器），软件方法（复杂），原子操作指令（单处理器或多处理器都可以）
• 可选的实现内容：有忙等待，无忙等待（进程睡眠）

---

10.信号量与同步

(1) 背景以及信号量
(2) 信号量的使用与实现
(3) 临界区与管程区别
(4) 同步问题与实现

10.1 背景以及信号量(Semaphore)

信号量 Semaphore 是由Dijkstra在20世纪60年代提出的,在早期的操作系统是主要的同步原语,由于产生信号量是由于多程序并发存在大的问题,即出现并发问题(竞争条件);

同步需要多线程共享公共数据的协调执行,包括互斥与条件同步;

• 互斥：在同一时间只有一个线程可以执行临界区;

Q：如何确保同步正确执行？

• 从底层硬件支持编译,需要高层次的编程抽象如锁lock;
• 锁只解决了互斥为了有时候要让多个进程进入临界区（比如只在临界区进行读操作，不必要求互斥），需要解决同步
• 信号量和管程是比锁更高级的抽象,也是同步互斥的解决方式

抽象数据类型： 用一个整形（sem）表示，提供两个原子操作 P() 和 V()

V ：verhoog(荷兰语增加) / P ：Prolaag(荷兰语减少)
P()，表示有线程需要进入临界区，sem–; if (sem < 0) wait; else progress(继续);
V()，表示有线程离开临界区，sem++; if (sem <= 0) wakeup a thread in waiting list #sem <= 0意味着有线程在等待进入临界区，唤醒常用FIFO方式
sem初值设为1就相当于锁了；初值设为更大的值，可以实现条件同步

信号量类似于铁路中信号灯,比如下面初始化两个资源控制信号灯:

WeiyiGeek.信号量类似

信号量的特征：

• Semaphore是有符号的整数:一般初始是>0的数，一旦小于0就不能继续，要挂在信号量上，其他进程做V操作才能唤醒，具体唤醒哪个取决于具体的算法，如常用FIFO先来先服务较为公平
• Semaphore是被保护的变量:但操作必须是原子即初始化完成后只能通过P() 于V() 这两个原子操作改变值;
• P 操作会阻塞 , V 操作不会阻塞

10.2 信号量的使用与实现

信号量的两种类型：

• 二进制信号量 ：0 或者 1
• 一般 / 计数信号量 ：可取任何非负值

信号量的使用场景：

• 互斥
• 条件同步(调度约束—一个线程等待另一个线程的事情发生)

(1)用二进制信号量实现互斥于调度约束

#实现互斥
mutex = new semaphore(0);
mutex->P();
Critical section;
mutex->V();

#实现调度约束
#调度约束sem初值设为0，Thread A某处P() / Thread B某处V()，确保Thread A在P()之后的语句一定在Thread B的V()执行之后才会开始执行
condition=new semaphore(0);
for thread A  condition->P();  #开始等待
for thread B  condition->V();  #发出信号唤醒 A / B 在V()操作之前的语句执行完后才能执行A的 P()之后的语句-同步

一个线程等待另外一个线程处理事情的时候,光有互斥(锁机制)是不够的;

例如：有界缓冲区的生产者-消费者问题;

• 一个或者多个生产者产生数据将数据放在一个缓冲区里,单个消费者每次从缓冲区取出数据;
• 在任何一个时间只有一个生产者或消费者可以访问该缓冲区;

Producer (生产者)	Buffer	Consumer (消费者)
用于存放产品	缓冲区

正确性要求：可以多个生产者访问Buffer写数据，但写的时候消费者不能有操作（互斥）, 缓冲区空消费者必须等待生产者,缓冲区满生产者必须等待消费者（调度/同步约束）。

每个约束用一个单独的信号量表示：

• 二进制信号量互斥(1/0)
• 一般信号量 full buffers
• 一般信号量 empty buffer

#初始化信号量
Class BoundedBuffer{
  Mutex = new semaphore(1);
  fullBuffers = new semaphore(0);
  emptyBuffers = new semaphore(n); #当前生产者可以往里面放多少个数据
}
#如果Buffer不空，则full/empty设别的值
#缓冲区界限 -> 生产存放
BoundedBuffer::Deposit(c){
  emptyBuffer->P(); #个生产者都可以进入直到empty<0被阻塞，不能先锁再emptybuffer--, 不然会在Buffers满的时候死锁 
  mutex->P(); 
  Add c to the buffer; 
  mutex->V(); 
  fullBuffers->V(); #初始是0，只有先V()不然消费者不能取
} 
  
# 消费移除
BoundedBuffer::Remove(c){ 
    fullBuffers->P();  #初始是0时会被挂起 
    mutex->P();  #线程进入临界区
    Remove c from buffer; 
    mutex->V();  #线程执行完成退出临界区
    emptyBuffers->V(); 
}

Q：问题上面的P&V可以换顺序吗？
答：可以。

(2)信号量实现
信号量的用用途：

• 互斥和条件同步
• 但等待条件是独立的互斥

使用两种方式硬件原语：

• 禁用中断
• 原子指令(test and set)

例如:使用禁用中断：

class Semaphore{ 
  int sem; 
  Waitqueue q;
} 

//有了数据结构,sem信号量自减，如果小于0则放入等待序列中,同时自身睡眠
Semaphore::P(){
   sem--; 
   if(sem<0){
     Add this thread t to q; 
     block(p); 
    } 
} 

//信号量自加,判断是否有线程在睡眠等待队列(<=0),将从等待队列中取出FIFO算法存在时间最久的进程进行执行（唤醒）
Semaphore::V(){ 
  Sem++; 
  If(sem<=0){ 
   Remove a thread t from q; 
   wakeup(t);
  } 
}

信号量和LOCK有区别：LOCK是通过忙等/等待队列实现sleep，信号量是等待队列。

上面这种方式存在的问题：

• 读/开发代码比较困难(程序员必须非常精通才行)，开发容易犯错（忘记释放信号量,使用的信号量已经被另外一个线程占用）
• 不能够处理死锁问题

10.3 管程的使用与实现

描述：比信号量抽象程度更高的机制,目的分离互斥(mutex)和条件同步的关注;作为编程语言的特性而诞生，用来简化并发编程，而非为OS设计;

什么是管程?
描述：管程(monitor)包含了一系列的共享变量，以及针对这些变量的操作的函数的组合/模块

• 一个Lock(指定临界区)
• 0 或者多个条件变量(等待/通知信号量用于管理并发访问共享数据)

一般方法：

• 收集在对象/模块中的相关共享数据
• 定义方法来访问共享数据

进入管程的队列是互斥的,然后执行wait等待睡眠/signal唤醒操作;

#Lock 锁机制
Lock::Acquire() - 等待直到锁可用,然后抢占锁;
Lock::Release() - 释放锁,唤醒等待者如果有

#条件(Condition)变量
- 允许等待状态进入临界区（允许处于等待[睡眠]的线程进入临界区,某个时刻原子释放锁进入睡眠)
- wait() : 释放锁/睡眠重新获得锁返回
- signal() : 唤醒等待者,(或者使用所有等待则)在如果有的前提下

WeiyiGeek.管程原理

管程实现:需要维持每个条件队列,线程等待的条件等待signal();

WeiyiGeek.管程的实现

用管程实现生产者-消费者模型

• count表示buffer中产品的数量,唤醒后获得锁
• 条件变量notFull、notEmpty表示是否为满或空的状态，notFull可以理解为okToProduce
• 先在前后加锁因为要保证只有一个线程在临界区 lock 在等待/睡眠的时候通过 notfull.wait(&lock) 释放锁。

Hansen方式，signal()之后继续执行完release()再切换线程，易于实现，实际OS采用此方式
Hoare方式，signal()之后立刻切换线程，直观，但实现困难，教科书一般按此方式

WeiyiGeek.操作系统管程的使用

While和if的区别，前者release后是挂在条件变量上的多个线程抢CPU，抢到谁给谁所以要check again, 后者是直接转交给了下一个线程，始终满足 count < n 的条件，所以直接走IF下面的语句

WeiyiGeek.两种方法的类比

存在的问题：

• 开发/调试并行程序很难,非确定性的交叉指令

两个同步互斥的机制，临界区和monitor，比起LOCK都可以解决更广泛的问题，但也都离不开底层的硬件支持。
同步互斥的不确定性强，调试困难。

WeiyiGeek.临界区和MONITOR比较

同步结构：锁(互斥),条件变量(有条件的同步),其他原语(信号量)

怎么有效的使用这些结构?
答：制定并遵循严格的程序设计风格/策略;

10.4 同步问题与实现

(1) 经典同步问题 - 读者优先
主要讨论读者(reader)和写者问题(Writer);

• 动机：共享数据的访问
• 两种类型使用者的定义：
  • 读者：不需要修改数据(只读)
  • 写者：读取和修改数据(读取和修改)
• 主要的问题约束：
  • 同一时间有多个读者,但是在任何时候只有一个写者;
  • 但没有写者时,读者才能访问数据;(读写不能同时进行)
  • 当没有读者和写者时,写者才能访问数据;(写者不能同时进行)
  • 在任何时间只有一个线程可以操作共享变量;(即对于同一个文件读写只能由一个进程进行)

多个并发进程的数据集共享：

• 读者 - 只读数据集,他们不执行任何更新
• 写者 - 可以读取和写入

共享数据：

• 数据集
• 信号量 CountMutex 初始化为1,用于对count修改的互斥;
• 信号量 WriteMutex 初始化为1,用于读者和写者、写者之间的互斥;
• 整数 Rcount 初始化为 0 ,表示读者个数;

实际案例：读者优先以信号量实现

writemutex ： 操作保证了写的互斥，和当前没有读者时，读者进入的互斥。
Rcount ：保证了可以有多个读者，由于自身是共享变量（对多个读者而言），所以在++ /– /判断操作的前后要用到CountMutex

sem_wait() 为 P() 等待
sem_post() 为 V() 释放

##### Writer #####
sem_wait(WriteMutex);
  write;
sem_post(WriteMutex);


##### Reader #####
sem_wait(CountMutex);
 if(Rcount == 0){
  sem_wait(WriteMutex);
 }
  ++Rcount

sem_post(CountMutex);

read;

sem_wait(CountMutex);
  --Rcount;  #表示读者全部完成了读
  if(Rcount == 0){
    sem_post(WriteMutex);
  }
sem_post(CountMutex);

读者优先和写者优先比较

• 读者优先策略：只要有一个读者处于活动状态,后来的读者都会被接纳.如果读者源源不断的出现的话,那么写者就始终处于阻塞状态;(避免了按照时间顺序谁先来谁执行)
• 写者优先策略：一旦写者就绪那么写者尽可能快地执行写操作,如果写者源源不断的出现的话,那么读者就始终处于阻塞阻塞转状态;

(2) 经典同步问题 - 写者优先
存在两类写者：一种是正在写的,一种是在写的等待队列里；而读者只有在上面者两类写者完成后才能进行读操作;
关键点：

• signal() 只唤醒一个线程
• broadcast() 唤醒所有线程

实际案例：写者优先-使用管程实现

Database::Read(){
    //Wait until no writers;  #等待没有写者
    Start Read();
    read database;
    //check out - wake up waiting writers;  #读完成了再检测是否有等待的写者
    DoneRead();
}

#基础结构：两种方法
Database::Write(){
  //Wait until no readers/writes;
  StartWrite();
  write database;
  //check out - wake up waiting readers/writers; //检测并且唤醒等待队列里面的读者或者写者
   DoneWrite();
}

//#----------------------------------------------------------------#
#管程状态变量 （管程需要任何操作都处于互斥的，确保一个程序进入管程(临时于临界区)去执行）
AR = 0;  #正在读的个数
AW = 0;  #正在写的个数
WR = 0;   #等待的读者个数
WW = 0;   #等待的写者个数
CONDITION oktoRead;  #可以读了
CONDITION oktoWrite; #可以写了
Lock lock;

//准备进行读操作(写者优先)
Private Database::StratRead()
{
  lock.Acquire(); //保护互斥
  //再读操作之之前,先判断是否存在写者
  while((AW+WW) > 0){  
    WR++;
    okToRead.wait(&lock);
    WR--;
  }
  lock.Release();
}

//唤醒处于等待状态的Writer;
Private Database::DoneRead()
{
  lock.Acquire();
  AR--;
  //注意下面要保证其他的正在读的读者也为0
  if(AR == 0 && WW > 0)
  {
    okToWrite.signal();
  }
  lock.Release();
}

//准备进行写操作(读者优先)
Private Database::StratWrite()
{
  lock.Acquire();
  //再读操作之之前,先判断是否存在写者
  while((AR+WR) > 0){  
    WW++;
    okToWrite.wait(&lock); //写等待
    WW--;
  }
  AW++;
  lock.Release();
}

//完成写者,检测并唤醒处理等待队列种的读者或写者
Private Database::StratWrite()
{
  lock.Acquire();
  if(ww > 0)
  {
    okToWrite.signal(); //使等待队列的写操作唤醒
  }else if(WR > 0 ){
    okToRead.broadcast(); //提高效率可以让多个读者同时进行读
  }

  lock.Release();
}

(3) 经典同步问题 -哲学家就餐
问题描述：5个哲学家吃饭的时候需要两把叉子,但是圆桌上只有5支叉子，如何保证哲学家动作有序进行?如：不会出现饥渴现象;(由1965年由Dijkstra首先提出并解决)

WeiyiGeek.案例

方法1：

#define N 5   //哲学家个数
void philosopher(int i);    //哲学家编号：0 - 4
while(TRUE)
{
  think();
  take_fork(i);      // 拿起左边叉子
  take_fork((i+1) % N); //拿起右边叉子
  eat();   
  put_fork(i);       // 放下左边叉子
  put_fork((i+1) % N);  // 放下右边叉子
}

//上面的方法,如果是多个人可能导致死锁问题;

方法2：对拿叉子的过程进行了改进(主动释放资源),但是仍然不正确;
如果每一个人都同时拿到叉子,然后又判断右手是否存在叉子,当然此时是不存在的;大家又把叉子放回去了,等待1秒重复执行;

WeiyiGeek.判断右手的叉子是否存在否则放下左手

方法3：在方法2的基础上在else语句下加入 wait_random_time();等待随机长时间;
此种方法等待时间随机变化,可行但是并非万全之策;

方式4: 我们学习了同步和互斥,利用此种方法来实现,但需要考虑问题(是否会出现死锁/还有效率)

#此种方法互斥访问不会出现死锁lock是正确的,但是每次只允许一人进餐(效率比较低)
semaphore mutex;   //互斥信号量初值为1
void philosopher(int i){
   //哲学家编号：0~4
  while(TRUE)
  {
    think();  //哲学家思考
    P(mutex); //进入临界区
      take_fork(i);      // 拿起左边叉子
      take_fork((i+1) % N); //拿起右边叉子
      eat();   
      put_fork(i);       // 放下左边叉子
      put_fork((i+1) % N);  // 放下右边叉子
    V(mutex);   //退出临界区
  }
}

该方案的缺点：它把就餐（而不是叉子）看成是必须互斥的访问的临界资源,因此会造成(叉子)资源的浪费;
从理论上说,如果有五把叉子,但应该允许两个不相邻的哲学家同时就餐;

最终解决：

(1) 从哲学家的角度解决,指导原则：要么不拿,要么就拿两把叉子;
(2) 从计算机程序来解决这个问题,指导原则：不能浪费CPU时间,进程间相互通信;

• S1：思考中…
• S2: 进入饥饿状态
• S3: 如果左邻居或者右邻居正在就餐,进程进入阻塞态否则转S4;
• S4: 拿起两把叉子
• S5: 开始吃饭…
• S6: 放下左边叉子看看左邻居是否可以进餐(饥饿状态,它的左边叉子是存在的),若能则唤醒之;
• S7: 放下右边叉子看看右邻居是否可以进餐(饥饿状态,它的右边叉子是存在的),若能则唤醒之;
• S8：根据判断又回到S1种;

(3) 编写程序的要求;

• 1. 必须有数据结构,来描述每个哲学家的当前状态;
• 2. 该状态是一个临界区资源,每个哲学家对它的访问应该互斥地进行-进程互斥;
• 3. 一个哲学家吃饱后,可能需要唤醒它的左邻右舍,两者之间存在着同步关系-进程同步

//1. 必须有一个数据结构,来描述每个哲学家得当前状态
#define N 5     //哲学家个数
#define LEFT i   //第i个哲学家得左邻居;
#define RIGHT (i+1)%N //第i个哲学家得右邻居;
#define THINKING 0 //思考状态
#define HUNGRY 1 //饥饿状态
#define EATING 2 //进餐状态
int statep[N];    //记录每个人得状态

// 2. 该状态是一个临界资源,对他得访问应该互斥得进行
semaphore mutex;  //互斥信号量,初始值为1

// 3. 一个哲学家吃饱后,可能要唤醒邻居，存在同步关系
semaphore s[N];   //同步信号量初始值为0 

// 4. 主函数philosopher(int i) 
void philosopher()
{
  //封闭式循环
  while(TRUE)
  {
    think(); //S1
    take_forks(i); //S2-S4
    eat(); //S5
    put_forks(i); //S6-S7
  }
}


//函数take_forks功能：要么拿到两把叉子,要么被阻塞起来;
void take_forks(int i)
{
  P(mutex);   //进入临界区
  state[i] = HUNGRY;             //饥饿状态
  test_take_left_right_forks(i); //试图拿两把叉子
  V(mutex);  //退出临界区
  P(s[i]);                       //没有叉子便阻塞
}

//test_take_left_right_forks函数定义（i 即哲学家得序号排列）
void test_take_left_right_forks(int i)
{
  if(state[i] == GUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING)
  {
    state[i] = EATING;  //两把叉子到手
    V(s[i]); //通知第i人可以吃饭了(说白了是自己);(让进程进行唤醒)
  }
}

//函数put_forks定义：把两把叉子放回原处,并且在需要得时候去唤醒左邻右舍
void put_forks(int i){
  P(mutex); //进入临界区
  state[i] = THINKING;  //交出两把叉子
  test_take_left_right_forks(LEFT);  //看左邻居是否可以进餐
  test_take_left_right_forks(RIGHT); //看右邻居是否可以进餐
  V(mutex); //退出临界区
}