进程之间的制约关系：
直接制约关系(协作关系，需要同步)：合作进程之间产生的制约关系
间接制约关系(竞争关系、需要互斥)：共享资源产生的制约关系
关键词：
- 互斥：即排它。互斥不足以反应访问的顺序
- 例如采用忙等的方式获得锁
- 同步：排它+协作。在等待的事件出现之前，即使获得锁也无法前进
- 睡眠(Sleep)：引起调用进程阻塞的系统调用，直至被另一个进程唤醒
- 唤醒(Wakeup)：唤醒相应的进程
注意：计算机系统的各类问题中，涉及到协作的，要么是等待方主动的去查询，即过一会就去主动的查询一下(忙等)；要么就被动的等待唤醒。忙等的方式有其局限性，因此引入了 睡眠-唤醒 机制
semaphore
定义：信号量由两个成员(s, q)组成，其中s是一个具有非负初值的整形变量，q是一个初始状态为空的队列，又称为 信号灯
s是被保护的整数变量，在初始化完成之后，只能进行P和V操作，不能参与如
if判断等PV原语：不可被中断(由OS保证)
P(Prolaag)：P操作意味着请求一个资源，在一定条件下代表阻塞进程操作
s = s - 1 if s < 0: 设置进程状态为等待 将进程放入q 转调度程序V(Verhoog)：V操作意味着释放一个资源，在一定条件下代表唤醒被阻塞进程的操作
s = s + 1 if s <= 0: 将q中的第一个进程p移出 设置p为就绪状态并插入就绪队列 返回原进程继续执行
信号量的具体实现：由OS保证，可以采用禁用中断(单CPU)、自旋锁(忙等)等方式
分类：
- 二元信号量(互斥量)：仅允许取值为0或者1，主要用于解决互斥问题
- 一般信号量：允许取大于1的整数，主要用于解决同步问题
注意：
- 对于信号量访问和修改只能够通过PV
- PV操作必须成对出现：
- 用于互斥时，位于同一进程之内
- 用于同步时，交错出现在两个合作进程之内
- 多个V操作次序可任意
- 多个P操作次序不能颠倒，否则可能造成死锁：
- 如果将P(互斥量)理解为上锁，P(一般信号量)理解为等待某种资源，则一起出现时，通常是一般信号量在前(上锁意味着排它，不能够既排它又等待其他进程释放资源)
- 很多时候我们需要判断信号量所表示资源数目，通常的做法是设置一个与信号量同步变化的共享变量，用来标记资源数目，由于共享变量在并发进程中均可访问，所以需要在共享变量上增加一个互斥量
信号量的理解
信号量的基本原理是利用信号灯实现进程协作
- 互斥是指同一时刻仅允许一个访问者，具有唯一性和排他性，但互斥无法反应访问顺序
- 同步是指通过有序的访问实现协同
- 在多数情况下同步已经实现了互斥，特别是在有写入资源的情况下必定是互斥的，少数情况是指可以允许访问者同时访问资源，如读者
信号量小结
- 一个信号量可用于 n 个进程的同步互斥，且只能由P、V操作修改
- 用于互斥时，s 初值为 1，取值为 1 ~ -(n-1)
- s = 1：临界区可用
- s = 0：已有一个进程进入临界区
- s < 0：临界区已经被占用，|s| 个进程正等待进入
- 用于同步时，s 初值 >= 0
- s >= 0：可用资源个数
- s < 0：资源的等待队列长度
- 用于互斥时，s 初值为 1，取值为 1 ~ -(n-1)
P、V 操作小结
- P(s)：请求分配一个资源
- V(s)：释放一个资源
- P、V操作必须成对出现
- 用于互斥时，位于同一进程内：(其实也不一定，如吃水果问题)
- 用于同步时，交错出现于两个合作进程内
- 多个 P 操作的次序不可颠倒，一般同步P优先于互斥P
- 多个 V 操作次序可任意
利用信号量解决同步问题的思路
明确同步和互斥进程
- 分析题目，明确要同步和互斥的进程
- 站在进程的角度来思考问题：
- 不要站在操作系统的角度来审视
- 进程是被调度和管理的对象
- 状态的感知与判断
- 进程无法感知其他进程的状态
- 进程对同步、互斥条件的判断，仅依赖信号量或共享变量
理清同步与互斥关系
哪些资源和对象需要互斥访问
哪些资源的访问顺序对进程调度有制约关系
同步信号量要表示出资源的等待条件和数目
P 操作内包含等待；V 操作内包含唤醒
同类资源可设置多个信号量：
- 例如生产者消费者问题中的 empty 和 full
同步P优先于互斥P
信号量的操作只能为P、V，不能取值和赋值：
- 如果需要进行判断，可以通过设置共享变量副本
例题
生产者-消费者问题：
有大小为N的缓冲区，生产者生产产品放到缓冲区，消费者从缓冲区取出产品进行消费。生产者和消费者满足如下关系：
- 互斥关系：对缓冲区的访问需要互斥，包括生产者与消费者之间，生产者与生产者之间，消费者与消费者之间
- 同步关系：当缓冲区满时生产者需要等待，当缓冲区空时消费者需要等待
分析：对缓冲区的访问需要互斥，因此设置互斥信号量mutex，并设初值为1；生产者和消费者分别需要满足各自的同步关系，因此设置同步信号量empty(表示缓冲区剩余的产品数)，并设初值为0；以及同步信号量full(表示将缓冲区装满所需的产品数)，并设初值为n
生产者:
生产产品
P(full) # 这里的两个P不能调换位置，否则可能造成死锁
P(mutex)
将产品送入缓冲区
V(mutex) # 这里的两个V可以调换位置
V(empty) # 同步关系交错出现在两个进程中
消费者:
P(empty)
P(mutex)
从缓冲区取出一个产品
V(mutex)
V(full)
消费一个产品读者-写者问题：
一个数据对象可以被多个并发进程所共享，其中一些进程只要求读数据对象的内容，另一些进程要求修改或写数据对象的内容，允许多个进程同时读数据对象，一个写进程不能同时与其他进程(无论是写或者读)同时访问此数据对象
读者-写着问题根据同步关系的不同可以分为以下几类：
- 读者优先：写者提出请求后需要等待所有的读者读完之后才可以进行修改
- 写着优先：
- 可插队
- 不可插队
- 读写者公平：按照提出请求的顺序先来先服务
读者优先：
分析：写者与读者需要互斥，因此引入互斥量mutex；涉及到对读者数目的判断，因此增加读者的共享变量readcount和互斥变量rmutex
读者：
P(rmutex) # 对共享变量(读者数量)的修改需要互斥
if readcount == 0:
P(mutex)
readcount += 1
V(rmutex)
读操作
P(rmutex)
readcount -= 1
if readcount == 0:
V(mutex)
V(rmutex)
写者：
P(mutex)
写操作
V(mutex)写者优先-不可插队
与读者-写者公平算法的区别在于：只有第一个写者需要排队
分析：写时需要互斥，因此引入互斥量mutex；涉及到对读者数目的判断，因此引入共享变量readcount和互斥量rmutex；涉及到对写者数目的判断，因此引入共享变量writecount和互斥量wmutex；涉及到读写者的排队，因此引入新的互斥信号量queue
读者：
P(queue) # 读者写者均在 queue 上排队
P(rmutex)
if readcount == 0:
P(mutex)
readcount += 1
V(rmutex)
V(queue) # 因为读者可以同时进行读操作，所以到这里释放 queue
读操作
P(rmutex)
readcount -= 1
if readcount == 0:
V(mutex)
V(rmutex)
写者：
P(wmutex)
if writecount == 0:
P(queue) # 只有第一个写者需要排队
writecount += 1
V(wmutex)
P(mutex)
写操作
V(mutex)
P(wmutex)
writecount -= 1
if writecount == 0:
V(queue)
V(wmutex)
写者优先-可插队
分析：读者和写者排不同的队列，因此引入新的互斥信号量 priority
读者：
P(priority) # 读者首先在 priority 上排队，故写者进入时，只需要等待 queue 上的一个
P(queue)
P(rmutex)
if readcount == 0:
P(mutex)
readcount += 1
V(rmutex)
V(queue)
V(priority)
读操作
P(rmutex)
readcount -= 1
if readcount == 0:
V(mutex)
V(rmutex)
写者：
P(wmutex)
if writecount == 0:
P(queue) # 注意这里的操作
writecount += 1
V(wmutex)
P(mutex)
写操作
V(mutex)
P(wmutex)
writecount -= 1
if writecount == 0:
V(queue)
V(wmutex)
一些典型的错误：
- 在读者操作中，误以为queue可以代替rmutex：rmutex的作用是使得修改readcount互斥，如果去除，则某一个读者在下方进行关于
readcount的操作时与上方的readcount操作并不互斥 - 在读者操作中，用rmutex代替priority，误将读者等待再rmutex处。则若读者1读操作完成，持有mutex等待rmutex，写者1持有queue等待mutex，读者2持有rmutex等待queue，会造成死锁
读写者公平
分析：涉及到读者和写者的互斥，引入互斥量mutex；涉及到对读者数目的判断，引入互斥量rmutex和共享变量readcount；引入队列信号量queue
读者：
P(queue)
P(rmutex)
if readcount == 0:
P(mutex)
readcount += 1
V(rmutex)
V(queue)
读操作
P(rmutex)
readcount -= 1
if readcount == 0:
V(mutex)
V(rmutex)
写者：
P(queue)
P(mutex)
V(queue)
写操作
V(mutex)
哲学家进餐问题：
有五个哲学家，他们的生活方式是交替地进行思考和进餐；哲学家们公用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五只筷子；平时哲学家进行思考，饥饿时便试图取左右最靠近他的筷子，只有在同时拿到两只筷子时才能进餐；进餐完毕，放下筷子又继续思考
服务生解法
引入一个餐厅服务生，服务生了解当前筷子的使用情况，哲学家必须经过服务生的允许才可以拿起筷子
破坏环路
？
资源分级
为资源的分配设置一个编号，同时设置资源访问的偏序关系。
例如约定哲学家总是先拿起左右两边编号较低的餐叉，用完餐后，总是先放下编号较高的餐叉。在这种情况下，若有四位哲学家都拿起手边编号较低的餐叉时，第五位哲学家无法拿起任何一个餐叉。注意到，只有一位哲学家能够使用最高编号的餐叉，所以它能够使用两只餐叉用餐。
睡眠的理发师问题
理发店里有一位理发师，一把理发椅和N把供等候理发顾客坐的椅子；如果没有顾客，理发师睡眠，当一个顾客到来时叫醒理发师；若理发师正在理发时又有顾客来，有空椅子就坐下，没有则离开理发店
互斥关系：访问的顾客数量需要互斥
同步关系：没有顾客时，理发师休息；理发师工作时，顾客等待
分析：需要用两个信号量customers和barbers表示同步关系，一个互斥信号量mutex和count表示互斥关系(不用customers代替count的原因是信号量只能通过PV操作访问)
理发师：
while True:
P(customers) # 等待顾客
P(mutex) # 等待中的顾客减1
count -= 1
V(mutex) # mutex 在前可以看作顾客在理发店里面等待，即等在barbers上,若barbers在前则可以看作在理发店外面等待，即等在mutex上
V(barbers) # 理发师已经准备好开始剪头发
cut_hair() # 非临界区
顾客：
P(mutex)
if count < N:
count += 1
V(customers) # 唤醒理发师
V(mutex)
P(barbers) # 等待理发师准备好
cut_hair()
else:
V(mutex) # 椅子满了，顾客离开
吃水果问题
桌子上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，母亲总是放香蕉到盘子中，儿子专心等吃盘中的香蕉，女儿专心等吃盘中的苹果
分析：本题是 生产者-消费者 的一种变形，生产者、消费者以及放入缓冲区的产品都有两类，但每类消费者只能够消费其中固定的一种产品，用 dish 表示盘子是否为空，初值为 1；apple 表示盘中是否有苹果，初值为 0；banana 表示盘中是否有香蕉，初值为 0
father:
while True:
cut_apple()
P(dish)
将苹果放入盘中
V(apple)
mother:
while True:
peal_banana()
P(dish)
将香蕉放入盘中
V(banana)
son:
while True:
P(banana)
从盘中取出香蕉
V(dish)
吃香蕉
girl:
while True:
P(apple)
从盘中取出苹果
V(dish)
吃苹果
独木桥问题
简单版本
独木桥上只允许一个车子通过，当车子到达桥头上，若桥上无车则可上桥，否则等待，直到桥上没有汽车
分析：加锁即可
车:
while True:
P(mutex)
过桥
V(mutex)扩展一
独木桥允许同方向的多个车子同时上桥，即要么左道的多辆车都走，要么右道的多辆车都走
分析：类似于读者优先问题
以左边为例
Semaphore:
lmutex := 1
mutex := 1
Shared variable:
lcount := 0
left_car:
P(lmutex)
lcount += 1
if lcount == 1:
P(mutex)
V(lmutex)
过桥
P(lmutex)
lcount -= 1
if lcount == 0:
V(mutex)
V(lmutex)
扩展二
限定桥上的车辆数最多为 N
分析：只需要加上桥数量的同步变量即可
以左边为例：
Semaphore:
lmutex := 1
mutex := 1
limit := N
Shared variable:
lcount := 0
left_car:
P(lmutex)
lcount += 1
if lcount == 1:
P(mutex)
V(lmutex)
P(limit)
过桥
V(limit)
P(lmutex)
lcount -= 1
if lcount == 0:
V(mutex)
V(lmutex)扩展三
限定桥上数量至多为 N，且后到达的车子按照顺序上桥，即若左边车在桥上，左边后继到达的车子只有在右边没有先到达等待的车子时才能够上桥
分析：类似于读写者公平
Semaphore:
lmutex := 1
mutex := 1
limit := N
Shared variable:
lcount := 0
left_car:
P(limit)
P(lmutex)
lcount += 1
if lcount == 1:
P(mutex)
V(lmutex)
V(limit)
过桥
P(lmutex)
lcount -= 1
if lcount == 0:
V(mutex)
V(lmutex)公园游玩问题
公园有 m 个旅客和 n 辆车，旅客需要乘车逛公园；每辆车仅能乘坐一个旅客；旅客排队乘坐旅行车，当一辆车可用时，载入一个旅客，在绕花园行驶任意长的时间；若 n 辆车都已经被旅客乘坐游玩，则旅客需要等待；如果一辆车已经空闲，但没有游玩的旅客，则车辆需要等待
注：这个题感觉可以有多种理解，过于玄学？
理解一
Semaphore:
emptyBus := n
readyCustomer := 0
顾客:
P(emptyBus) # 检查是否有空车
V(readyCustomer) # 游客上车，等待车辆出发
游玩
车:
P(readyCustomer) # 检查是否有游客上车
游玩
V(emptyBus)理解二
Semaphore:
emptyBus := n
readyCustomer := 0
readyCar := 0
mutex := 1
Shared variable:
count := 0
顾客:
P(mutex)
if count < m: # 假定公园的最大载客量是 m
登记顾客信息
count += 1
V(mutex)
P(emptyBus) # 判断是否有空车
V(readyCustomer) # 顾客等待好，唤醒一辆车
P(readyCar) # 等待车准备好
游玩
else:
V(mutex)
车:
P(readyCustomer) # 等待顾客
登记车信息
V(readCar) # 车准备好
游玩
V(emptyBus) # 释放车理解三(感觉有些奇怪)
Semaphore:
car_available := n
passenger_wait := 0
readyCar := 0
car_busy[n] := { 0 }
mutex := 1
shared variable:
car_number
passenger:
wander_some_time(); // 在公园漫步
V(passenger_wait); // 乘客希望坐车
P(car_available); // 是否有空车
P(readyCar); // 等待车准备好
P(car_busy[car_number]);// 在编号为k的车上行驶
V(mutex); // 释放锁
V(car_available); // 释放车
car:
P(passenger_wait); // 等待乘客
P(mutex); // 加锁
car_number = k; // 设置共享变量为车的编号
V(readyCar); // 车准备好了
travel_random_time(); // 行驶一段时间
V(car_busy[k]); // 到达目的地
红黑客问题(解答太妙了！！)
船每次坐满四个人才能够离开，三个红客+一个黑客或者一个红客+三个黑客不能同船
分析：等待的客人之间先排列组合出可以上船的客人
以红客为例，只有两种情况，即4个红客，或者2个红客+2个或以上的黑客
Semaphore:
mutex := 1 # 用于排列组合的互斥
read_wait := 0 # 被阻塞的红客
black_wait := 0 # 被阻塞的黑客
boat := 1 # 互斥使用船
mutex_wait := 1 # 互斥修改等待上船人数
full := 0 # 船是否满
shared variable:
red_count := 0 # 等待的红客副本
black_count := 0 # 等待的黑客副本
wait_count := 0 # 等待上船的人数
红客:
P(mutex) # 加锁，进行排列组合
red_count += 1
if red_count == 4: # 第一种情况
V(red_wait)
V(red_wait)
V(red_wait) # 释放三个人
red_count = 0 # 等待人数清零
wait_count = 4 # 四个人等待上船
elif red_count == 2 and black_count >= 2:
V(red_wait)
V(black_wait)
V(black_wait)
red_count = 0
black_count -= 2
wait_count = 4
else:
V(mutex)
P(red_wait) # 加入等待队列
P(mutex_wait)
if wait_count == 4:
P(boat) # 船是否回来
wait_count -= 1 # 如果没有符合条件排列，则 wait_count < 0
if wait_count == 0:
V(full) # 船满了
V(mutex) # 如果没有符合条件排列，则不会到这里，nb
V(mutex_wait)
过河
船:
P(full)
过河
V(boat)红黑客问题的变形
n 个学生 m 个网球场 k 个裁判，两个学生组成一组打网球，每组有一个裁判。需要满足：没有学生，裁判休息；没有裁判，学生等待；没有场地，学生等待
Semaphore:
playground := m
referee := k
wait := 0
readyStudeng := 0
mutex := 1
mutex_wait := 1
shared variable:
s_num := 0
wait_num := 0
学生:
P(mutex)
s_num += 1
if s_num == 2:
V(wait)
wait_num = 2
s_num = 0
else:
V(mutex)
P(wait)
P(mutex_wait):
if wait_num == 2:
P(referee) # 等待教练
P(playground) # 等待球场
wait_num -= 1
if wait_num == 0:
V(readyStudent) # 到场了，可以等裁判过来评分
V(mutex)
V(mutex_wait)
裁判:
P(readStudent)
评分
V(referee)
V(playground)
