咸鱼今年压了读者写者问题，前几年没考过。
死锁的四个条件是：
- 禁止抢占（no preemption）：系统资源不能被强制从一个线程中退出。
- 持有和等待（hold and wait）：一个线程在等待时持有并发资源。持有并发资源并还等待其它资源，也就是吃着碗里的望着锅里的。
- 互斥（mutual exclusion）：资源只能同时分配给一个线程，无法多个线程共享。
- 循环等待（circular waiting）：一系列线程互相持有其他进程所需要的资源。必须有一个循环依赖的关系。
死锁只有在四个条件同时满足时发生，预防死锁必须至少破坏其中一项。
生产者-消费者问题
特点：进程与进程之间是“ 生产资源一消耗资源的关系
六步做题
- 有几类进程？——每类进程对应一个函数
- 在每个函数内部，用自己的语言描述进程动作（只做一次-不加
while或者 不断重复-加while(1)） - 分析每一动作之前，是否需要
P()操作
有P()必有V()，每写一个P()，就安排一个V() - 所有 PV 写完后，才去定义信号量，定义完再确认每个信号量的初值是多少
- 注意连续出现多个P操作是否会导致死锁
- 检查题意
例题：
graph TD
A[生产者A] --> F1[工厂F1]
B[生产者B] --> F2[工厂F2]
F1 --> C[组装工人]
F2 --> C
分析：
-
几类进程？—— 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 的互斥}
}
