咸鱼今年压了读者写者问题，前几年没考过。
死锁的四个条件是：
- 禁止抢占（no preemption）：系统资源不能被强制从一个线程中退出。
- 持有和等待（hold and wait）：一个线程在等待时持有并发资源。持有并发资源并还等待其它资源，也就是吃着碗里的望着锅里的。
- 互斥（mutual exclusion）：资源只能同时分配给一个线程，无法多个线程共享。
- 循环等待（circular waiting）：一系列线程互相持有其他进程所需要的资源。必须有一个循环依赖的关系。
死锁只有在四个条件同时满足时发生，预防死锁必须至少破坏其中一项。
生产者-消费者问题
特点：进程与进程之间是“ 生产资源一消耗资源的关系
六步做题
- 有几类进程？——每类进程对应一个函数
- 在每个函数内部，用自己的语言描述进程动作（只做一次-不加
while或者 不断重复-加while(1)） - 分析每一动作之前，是否需要
P()操作
有P()必有V()，每写一个P()，就安排一个V() - 所有 PV 写完后，才去定义信号量，定义完再确认每个信号量的初值是多少
- 注意连续出现多个P操作是否会导致死锁
- 检查题意
例题：
分析：
-
几类进程？—— 2类：生产车间和装配车间
-
描述每类动作
见下图绿蓝紫的框架部分。 -
安排PV操作
分析每一动作之前，是否需要P()一个东西。
以车间1为例：
- 生产A零件之前不需要等待任何资源，所以生产A零件之前不需要P()；
- 把A零件放入F1之前需要确保F1有空位，因此需要P(empty_F1)
- 什么地方会V(empty_F1)？——装配工人从F1取走
- F2同理
- 从F1取A，A可能不够，所以在此之前需要P(A)，V(A)在把A放入F1之后
- 从F2取B，同理
- 组装不需要PV操作
- 定义信号量
Semaphore mutex1=1; //互斥访问货架F1
Semaphore mutex2=1; //互斥访问货架F2
Semaphore empty1=10; //货架F1上有几个空位
Semaphore full1=0; //货架F1上有几个A零件
Semaphore empty2=10; //货架F2上有几个空位
Semaphore full2=0; //货架F2上有几个B零件
- 注意连续出现多个P操作是否会发生死锁
- 检查题意
单纯的同步问题——前驱后继问题
可以按照生产者消费者问题的六步做题法来做。
哲学家进餐问题
一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子己在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
特点: 只有一类进程，但需要占用多个资源才能运行
三种思路：
- 限制申请资源的顺序。如：规定单号哲学家先取左筷子，双号先取右筷子。（不建议使用）
- 限制并发进程数。如：规定同一时间只能有一个哲学家就餐（禁止并行）。（也不建议使用）
- 让进程一口气取得所有资源，再开始运行。如：哲学家只有能够取得两个筷子的时候才会就餐。
// 代码来自https://www.cnblogs.com/lordtianqiyi/p/17677155.html
semaphore mutex = 1; // 互斥拿筷子
semaphore chopstick[5] = {1,1,1,1,1};
void philosopher(int i){
while(true)
{
/*当哲学家饥饿时，总是先拿左边的筷子，再拿右边的筷子*/
P(mutex)
P(chopstick[i]);
P(chopstick[(i+1)%5]);
V(mutex)
// 吃饭
/*当哲学家进餐完成后，总是先放下左边的筷子，再放下右边的筷子*/
V(chopstick[i]);
V(chopstick[(i+1)%5]);
}
}
为防止同时拿到左筷子而死锁的情况，这里在拿筷子时加了一个互斥信号量mutex。拿筷子时互斥，这样就不会出现同时拿到左筷子的情况。但是效率较低。
更好的做法是把筷子变成int型变量：
// 万能模板
semaphore mutex = 1; // 互斥拿筷子
int chopstick[5] = {1,1,1,1,1};
void philosopher(int i){
while(true)
// 当哲学家左右筷子不全在时，跳转回while，循环
{
P(lock);
if (chopstick[i] && chopstick[(i+1)%5] ){
// 条件是所有资源都足够
-- chopstick[i];
-- chopstick[(i+1)%5];
// 所有资源int值--
V(mutex);
break;
}else{
V(mutex); // 跳回while
}
// 吃饭
P(lock); // 一口气归还所有资源
++ chopstick[i];
++ chopstick[(i+1)%5];
V(lock);
}
}
例题：2019真题
分析：
- 姑且认为只有一类进程——哲学家
philosopher(){
while(1){
get left chopstick;
get right chopstick;
get bowl;
eat;
}
}
理发师问题
是服务-被服务的关系
分析：
- 有几类进程？—— 2类：理发师和顾客
- 没有顾客时理发师可不可以睡觉？可以的话则阻塞；不可以(2011.45)则循环忙等
- 座位是否有限？座位不够顾客跑路，座位够顾客等待
- 如何用代码表示取号和叫号
int waiting = 0; // 已取号但还没被服务的人数
semaphore mutex_wait = 1; // 互斥访问waiting
semaphore Service = 0; // 服务信号量
semaphore customer = 0; // 顾客信号量，用于理发师睡觉
// 顾客
customer_i(){
while(1){
get number;
P(mutex_wait);
waiting++;
V(mutex_wait);
// 被叫号之后才能被服务
// V(customer); // 叫醒理发师
等待被叫号;
P(Service); // 被叫号对应一次服务
// cut hair;
}
}
// 理发师
server_j(){
while(1){ // 如果不睡觉，理发师需要循环工作
P(mutex_wait);
if(waiting>0){ // 有人在等待
call number;
waiting--;
V(mutex_wait);
V(Service);
// cut hair;
}else{
V(mutex_wait);
// P(customer) //睡觉
}
}
}
读者写者问题
读者和写着两组并发进程共享一个文件，要求：多个读者可以同时读文件；只允许一个写者写文件；任一写者在完成写操作之前不允许其他人工作；写者写之前，应该让已有的读写者都退出。
分析：本质就是连续多个同类进程访问同一个临界资源的问题
2类进程：读者和写者。
其中有互斥关系的是：写者之间、写者与读者之间。
代码参考https://www.cnblogs.com/Mount256/p/16804609.html
这位老哥写得挺好的，我就没必要再改了，就加了点注释。
读优先
int count = 0; // 读者数量
semaphore busy = 1; // “读文件”和“写文件”的互斥锁
semaphore mutex = 1; // 变量 count 的互斥锁
Reader(){ // 读者进程
while(1){
P(mutex); // 给count上锁
count++;
if (count == 1){ // 有人读时加锁，后面人继续读不用再加锁了
P(busy); // 有读者时因互斥关系不能写
}
V(mutex);
// 读文件;
P(mutex);
count--;
if (count == 0){ // 没有读者时去锁
V(busy);
}
V(mutex);
}
}
Writer(){ // 写者进程
while(1){
P(busy);
// 写文件;
V(busy);
}
}
读优先缺点是读进程会抢占资源到站写者饥饿。
读写公平
int count = 0;
semaphore queue = 1; // 实现“读写公平”的互斥锁，可以视为一个队列
semaphore busy = 1; // “读文件”和“写文件”的互斥锁
semaphore mutex = 1; // 变量 count 的互斥锁
Reader(){ // 读者进程
while(1){
P(queue); // 在无写进程请求时不需要进入队列
P(mutex); // 该互斥量实际上是多余的，上面语句已经兼有互斥功能
count++;
if (count == 1){
P(busy);
}
V(mutex); // 该互斥量实际上是多余的，下面语句已经兼有互斥功能
V(queue); // 恢复对共享文件的访问，不然其他读者没法读了
// 读文件;
P(mutex);
count--;
if (count == 0){
V(busy);
}
V(mutex);
}
}
Writer(){ // 写者进程
while(1){
P(queue); // 在无其他写进程请求时不需要进入队列
P(busy);
// 写文件;
V(busy);
V(queue); // 恢复对共享文件的访问
}
}
这样子有一个写者排入队列就会把后面的读者堵住，后面的读者形成不了抢占。
顺序为：之前的读者-写者-后来的读者
写优先
int ReaderCount = 0; // 读者数量
int WriterCount = 0; // 写者数量
semaphore Read = 1; // “读文件”的互斥锁
semaphore Write = 1; // “写文件”的互斥锁
semaphore ReaderMutex = 1; // 变量 ReaderCount 的互斥锁
semaphore WriterMutex = 1; // 变量 WriterCount 的互斥锁
Reader(){ // 读者进程
while(1){
P(Read); // 每个读进程都需要对 Read 加锁
P(ReaderMutex); // 对 ReadCount 的互斥，实际上，上条语句已经兼有此功能，可以去掉
ReaderCount++;
if (ReaderCount == 1){ // 如果是第一个读进程
P(Write); // 则对写者上锁
}
V(ReaderMutex); // 对 ReadCount 的互斥，实际上，下条语句已经兼有此功能，可以去掉
V(Read); // Read 解锁
读文件;
P(ReaderMutex); // 对 ReadCount 的互斥
ReaderCount--;
if (ReaderCount == 0){ // 如果是最后一个读进程
V(Write); // 则对写者解锁
}
V(ReaderMutex); // 对 ReadCount 的互斥
}
}
Writer(){ // 写者进程
while(1){
P(WriterMutex); // 对 WriterCount 的互斥
WriterCount++;
if (WriterCount == 1){ // 如果是第一个写进程
P(Read); // 则对读者上锁
}
V(WriterMutex); // 对 WriterCount 的互斥
P(Write); // Write 加锁
写文件;
V(Write); // Write 解锁
P(WriterMutex); // 对 WriterCount 的互斥
WriterCount--;
if (WriterCount == 0){ // 如果是最后一个写进程
V(Read); // 则对读者解锁
}
V(WriterMutex); // 对 WriterCount 的互斥
}
}