操作系统
前言
就看408真题的考频，可以说，这一节有很大概率考大题。而互斥与同步本就是操作系统这门课相对而言的难点。本文参考22版王道操作系统，先回顾进程同步中的基本概念，后重点分析了几种经典同步问题，最后详细回答了王道的课后习题。本人尚在学习过程中，文章难免有纰漏，尤其是几处感觉王道书有问题的地方，也不敢确定自己的想法是否正确，希望大家辩证地看待。
进程同步
一、基本概念
1. 临界资源
多个进程可以共享系统中的各种资源，许多资源一次只能为一个进程所用，将一次仅允许一个进程所用的资源称为临界资源
物理设备：打印机
许多变量、数据等
临界资源的访问过程分成4个部分：
进入区：为了进入临界区使用临界资源，在进入区要检查可否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区
临界区：进程中访问临界资源的那段代码，又称临界段
退出区：将正在访问临界区的标志清除
剩余区：代码中的其余部分
2. 临界区
每个进程中访问临界资源的那段代码
3. 同步
这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。执行的前驱关系实质就是同步
4. 互斥
互斥也称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许访问此临界资源
同步机制应遵循准则：
空闲等待
忙则等待
有限等待
让权等待
二、互斥的基本方法
软件实现算法
1.单标志法
turn 指示被允许进入临界区的进程编号
P 0 进程：
while (turn != 0); critical section; turn = 1; remainder section;
P 1 进程：
while (turn != 1); critical section; turn = 0; remainder section;
缺陷：必须交替进入临界区，若一个进程不再进入临界区，则另一个进程也无法进入临界区
违背空闲让进
举例：p 0 p0p0 进入临界区并离开，此时临界区空闲，但 p 1 p1p1 始终不进入临界区，此时 t u r n = 1 turn=1turn=1 导致 p 0 p0p0 无法进入临界区
2.双标志法先检查
先查看临界资源是否正在被访问，若正在被访问，则等待
否则，进入临界区
P i 进程：
while (flag[j]); //（1） flag[i] = True; //（3） critical section; flag[i] = False; remainder section;
P j 进程：
while (flag[i]); //（2） flag[j] = True; //（4） critical section; flag[j] = False; remainder section;
优点：
不用交替进入，可以连续使用
缺点：
P i 和 P j 可能同时进入临界区，当按照 ( 1 ) ( 2 ) ( 3 ) ( 4 ) 的顺序执行时，二者标志位起初均为 F a l s e ，导致都进入了临界区
违背忙则等待
这里的问题在于检查和修改操作不能一次性完成
3.双标志法后检查
可以看出，与双标志法前检查区别在于检查在修改的后面
P i 进程：
flag[i] = True; while (flag[j]); critical section; flag[i] = False; remainder section;
P j 进程：
flag[j] = True; while (flag[i]); critical section; flag[j] = False; remainder section;
缺点：
按照之前的思路，两个进程几乎同时要进入临界区，都将自己的标志位记为 T r u e ，然后同时检测对方状态，发现对方也要进入临界区，导致互相谦让，结果谁都进不了
导致饥饿现象
4.Peterson’s Algorithm
先看代码：设置了 f l a g标志位 和 t u r n 标志，可以发现是单标志法和双标志法后检查的结合
P i 进程：
flag[i] = True; turn = j; while (flag[j] && turn == j); critical section; flag[i] = False; remainder section;
P j 进程：
flag[j] = True; turn = i; while (flag[i] && turn == i); critical section; flag[i] = False; remainder section;
举个生活中的例子，两个人同时要进门，都特别谦让，在双标志法后检查中，谁都进不去。而本算法指定了一个 t u r n 标志，即主人指定谁先进来，这样其实就是二者先礼貌的客气一番，然后就按照主人的指定顺序入门了。很符合生活中的实际情况。
利用 f l a g 解决临界资源的互斥访问
利用 t u r n 解决饥饿问题
硬件实现算法
计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或对两个字的内容进行交换
通过硬件支持实现临界段问题的方法称为低级方法，或称为元方法
1.中断屏蔽方法
禁止一切中断发生，或称为屏蔽中断、关中断。保证不会发生进程切换，这样当前进程能顺利执行临界区代码，保证互斥
关中断 临界区 开中断
缺点：
限制了处理机交替执行程序的能力，效率低下
权力交给用户不太明智
2.硬件指令方法
T e s t A n d S e t 指令
原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设成真
boolean TestAndSet (boolean *lock) { boolean old; old = *lock; *lock = true; return old; }
为每个临界资源设置一个共享布尔变量 l o c k
表示资源两种状态：
T r u e 表示被占用
F a l s e 表示未被占用， l o c k 初值为 F a l s e
利用 T e s t A n d S e t 检查和修改标志 l o c k若有进程在临界区，则重复检查，直到进程退出。
用该指令实现进程互斥算法如下：
while TestAndSet(&lock); 进程的临界区代码段; lock=false; 进程的其他代码;
S w a p 指 令
功能：交换两个字（字节）的内容
功能描述如下：
Swap(boolean *a, boolean *b) { boolean temp; temp = *a; *a = *b; *b = temp; }
注意：以上指令描述仅仅是功能实现，而并非软件实现的定义，事实上，是由 硬件逻辑 直接实现的，不会被中断
应该为每个临界资源设置一个 共享 布尔类型变量 lock ，初值为 flase ；在 每个进程中再设置一个 局部 布尔变量 key ，用于与 lock 交换信息。在进入临界区前，先利用 S w a p SwapSwap 指令交换 lock 与 key 的内容，然后检查 key 的状态；有进程在临界区时，重复交换和检查过程，直到进程退出。
key = true; while(key !- false) { Swap(&lock, &key); } 进程的临界区代码段; lock=false; 进程的其他代码;
硬件方法的优点：适用于任意数目的进程，而不管是单处理机还是多处理机。可支持进程中有多个临界区，只需为每个临界区设立一个布尔变量
硬件方法的缺点：进程等待进入临界区要耗费处理机时间，不能实现 让权等待。从等待进程中随机选择一个进入临界区，有的进程可能选不上，导致 饥饿
三、信号量
信号量用来解决互斥和同步问题，它只能被两个标准的 原语 w a i t ( S )和 s i g n a l ( S ) 访问，也可以记为 P操作 和 V操作
原语 指完成某种功能且不被分割、不被中断执行的操作序列，通常可由硬件来实现。
1.整型信号量
整型信号量被定义为一个用于表示资源数目的整型量 S
wait(S) { while(S<=0); S = S-1; } signal(S) { S=S+1; }
信号量 S ≤ 0 ，就会不断地测试，因此并未遵循 让权等待 的原则
2.记录型信号量
不存在 忙等 现象。除了一个用于代表资源数目的整型变量 v a l u e 外，再增加一个进程链表 L LL，用于链接所有等待该资源的进程。
记录型信号量描述：
typedef struct { int value; struct process *L; } semaphore;
相应的 w a i t ( S )和 s i g n a l ( S ) 操作如下：
void wait(semaphore S) { S.value--; if (S.value < 0) { add this process to S.L; block(S.L); } }
关键就是在发现资源已分配完后进行自我阻塞，放弃处理机，进入等待队列，遵循 让权等待 准则
void signal(semaphore S) { S.value++; if (S.value <= 0) { remove a process P from S.L; wakeup(P); } }
进程释放一个资源，如果还有等待进程，应该唤醒第一个。
3.利用信号量实现同步
设 S 为实现进程 P 1 , P 2 同步的公共信号量，初值为零。
semaphore S = 0; P1() { ... x; V(S); ... } P2() { ... P(S); y; ... }
同步是有先后顺序的，在这里 P 2
进程中的y语句要用到进程 P 1
中语句x的运行结果，即现有x才能有y
所以信号量初值设为零，如果 P 2
先执行，就会被阻塞，保证了正确的 先后顺序
4.利用信号量实现进程互斥
设 S 为实现进程 P 1 , P 2
互斥的信号量，初值为一。（每次只允许一个进程进入临界区，也就是资源数为一）。
semaphore S = 1; P1() { ... P(S); //上锁 进程P1的临界区; V(S); //解锁 ... } P2() { ... P(S); //上锁 进程P2的临界区; V(S); //解锁 ... }
5.利用信号量实现前驱关系
上图是一个前驱图，信号量初始值均设为零。为了保证 S 1 → S 2 , S 1 → S 3
的前驱关系，设置信号量 a 1 , a 2，以此类推
semaphore a1=a2=b1=b2=c=d=e=0; S1() { ... V(a1); V(a2); } S2() { P(a1); ... V(b1); V(b2); } S3() { P(a2); ... V(c); } S4() { P(b1); ... V(d); } S5() { P(b2); ... V(e); } S6() { P(c); P(d); P(e); ... }
因该很容易看出来，其实这就是多层的同步问题，并不复杂，主要是抓住一个要点：你依赖谁？谁依赖你？对于你依赖的进程，你要 P PP ，其实就是问问它搞好了没有，好了就把数据发你，你就可以开始工作了。如果你去问他，他没好，那么你就在那等，它好了再叫你。同理，谁依赖你，它也就在那等你，所以你数据处理后就 V VV 发给它。搞明白先后顺序，问题就迎刃而解了。
四、管程
1.管程的定义
信号量操作的缺点？
程序员写程序时必须特别注意顺序问题。编写程序困难，易出错
什么是管程？
利用共享数据结构抽象地表示系统中的共享资源，而把对该数据结构实施的操作定义为一组过程。进程对共享资源的申请，释放等操作，都由这组过程来实现。这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就能统一管理对共享资源的所有访问，实现进程互斥。
管程由4部分组成：
管程的名称
局部于管程内部的共享数据结构说明
对该数据结构进行操作的一组过程
对局部于管程内部的共享数据设置初始化的语句
2.条件变量
设置条件变量以及等待/唤醒操作以解决同步问题。
每个条件变量保存一个等待队列，用于记录因为该条件变量而阻塞的所有进程，对条件变量只能进行两种操作，即 w a i t waitwait 和 s i g n a l signalsignal
条件变量和信号量的比较：
相似点：条件变量的 w a i t / s i g n a l wait/signalwait/signal 操作类似于信号量的 P / V P/VP/V 操作，可以实现进程的阻塞/唤醒
不同点：条件变量没有值，仅实现排队等待功能；而信号量有值，反映剩余资源数
3.用管程解决生产者消费者问题
王道伪代码如下：
右边是生产者消费者进程代码，可见管程封装程度之高。
