1.解题思路
1.确定函数的个数：梳理题目中有几个进程，一个进程对应一个函数（根据动作是否一致区分是否为统一进程）
2.确定函数的动作：
①动作是什么：在函数内部，用中文描述动作（允许用中文的伪代码形式答题）
②动作的次数：只做一次（不加while）还是重复进行（while循环）
3.确定函数是否在每个动作之前需要进行P操作：如果需要进行P操作，则一定有与之对应的V操作；需要思考这个V操作应该被放在哪进行
①消耗资源型的P操作：题目一般会显性给出，例如每次动作需要消耗一个缓冲区空间（P操作减少缓冲区空间，V操作增加缓冲区空间，缓冲区无空间时无法进行动作）
②互斥型的P操作：需要注意隐含的互斥关系，例如缓冲区的互斥访问
4.确定信号量的个数：所有PV操作定义完成后，再确定信号量的个数
5.检查是否发生死锁：连续进行多个P操作的地方是否会发生死锁（只有一个P操作不会发生死锁）
①某信号量的PV连续出现（中间没有夹杂别的P操作），则不会发生死锁：不发生请求和保持
//不夹杂其余P操作 P(mutex); 动作; V(mutex); //夹杂其余P操作 P(mutex); P(full); 动作; V(empty); V(mutex;
②连续多个P导致的死锁可尝试调整P顺序解决
2.生产者 - 消费者
1.确定函数的个数（3）：生产车间A和生产车间B虽然都是生产车间，但是它们俩执行的动作不一致，故不是同一个进程，即生产车间A和生产车间B需要对应不同的函数；进程 = 生产车间A（P1） + 生产车间B（P2） + 装配车间（C）
2.确定函数的动作：
①动作是什么：
P1和P2分别生产A、B两种零件，并将分别把它们送到货架F1、F2上
C从货架上分别取出A、B后，组装成A + B
②动作的次数：P1、P2和C都是不断重复 → while
3.确定函数是否在每个动作之前需要进行P操作：
①P1生产A零件之前不需要消耗资源
P1将A放到F1前需要消耗1个F1货架（A缓冲区）的剩余容量 → C从F1上取A后会释放1个F1货架的剩余容量
②P2生产B零件之前不需要消耗资源
P2将B放到F2前需要消耗1个F2货架（B缓冲区）的剩余容量 → C从F2上取B后会释放1个F2货架的剩余容量
③C从F1取A前需要消耗1个F1货架上的A产品 → P1把A放到F1后释放1个F1货架上的A产品
C从F2取B前需要消耗1个F2货架上的B产品 → P2把B放到F2后释放1个F2货架上的B产品
C组装成A+B前不需要消耗资源
④P1和C对F1的访问是互斥的（mutex1）；P2和C对F2的访问是互斥的（mutex2）
4.确定信号量的个数：F1 = F2 = 10，full1 = full2 = 0，mutex1 = mutex2 = 1
5.检查是否发生死锁：先P同步信号量（F1、F2、full1、full2），再P互斥信号量(mutex1、mutex2）
1.确定函数的个数（2）：老和尚喝水，小和尚取水
2.确定函数的动作：
①动作是什么：
老和尚从缸中打水、喝水
小和尚从井中打水、放水
②动作的次数：不断进行 → while
3.确定函数是否在每个动作之前需要进行P操作：
①老和尚打水前消耗1个桶 → 老和尚喝水后增加1个桶
老和尚喝水前消耗1个水缸里的水 → 小和尚打水后增加1个水缸里的水
②小和尚打水前消耗1个桶 → 小和尚放水后增加1个桶
小和尚打水前消耗1个水缸的剩余容量 → 老和尚喝水后增加1个水缸的剩余容量
③小和尚之间对井的访问是互斥的（mutex1）；老和尚间和小和尚间、老和尚和小和尚对水缸的访问是互斥的（mutex2）
4.确定信号量的个数：互斥访问信号量为1，其余为资源数量
5.检查是否发生死锁：
①如果老和尚和小和尚都是先对tong进行P操作（先进行取水桶操作），则可能发生：三个老和尚同时取水，并取得水桶（此时完成了三个P(tong)，则tong = 0），但是水缸中没有水（full = 0），即老和尚进程被阻塞在P（full）；而若干个小和尚想去打水，水桶却被取光（tong = 0），即小和尚进城被阻塞在P(tong)，这样就形成了死锁
②同理，也可能发生三个小和尚分别拿着桶，而水缸中水满（empty = 0），被阻塞在P（empty）；而老和尚苦于没有水桶，被阻塞在P（tong）
解决方法：调整老和尚进程和小和尚进程的取桶顺序
老和尚先判断水缸中有没有水，水缸有水的情况下才去取桶喝水，即先P（full）再P（tong）
小和尚先判断水缸中有没有剩余容量，水缸中有剩余容量的情况下才去取桶打水，即先（empty）再P（tong）
1.确定函数的个数（2）：所有生产者动作一致，故所有生产者视为一类进程；所有消费者动作一致，故所有消费者视为一类进程
2.确定函数的动作：
①动作是什么：
P生产产品，并将产品放入缓冲区
C从缓冲区取10个产品
②动作的次数：P和C都是不断重复 → while
3.确定函数是否在每个动作之前需要进行P操作：
①P生产产品前不需要消耗资源
P将产品放入缓冲区前需要消耗1个缓冲区剩余容量 → C从缓冲区取10个产品后增加10个缓冲区剩余容量（每取出1个产品，增加1个缓冲区容量，通过for循环实现）
②C从缓冲区取10个产品前需要消耗10个缓冲区产品数量（for循环实现） → P将产品放入缓冲区后增加1个缓冲区产品数量
③P和C对缓冲区的访问是互斥的（mutex）
④多个C之间P操作是互斥的：如果只是简单的使用for循环设置在取10个产品前，则可能发生多个C轮流的取产品
4.确定信号量的个数
5.检查是否发生死锁：否
3.理发师
1.服务与被服务的关系
2.区别：需要额外设置变量记录当前等待的顾客有多少个，且该变量的访问是要互斥进行的，即需要夹在PV操作中
3.理发师问题实际上是生产者 - 消费者问题的变式：
①生产者 - 消费者问题：生产者生产资源，消费者消费资源；缓冲区限制资源上限
②理发师问题：将顾客和服务员分别视为一种资源
顾客：每个顾客到店时，生产一个顾客资源；在被服务前，消耗一个服务员资源
服务员：提供服务前，消耗一个顾客资源；确定有顾客时，生产一个服务员资源；再提供服务
特点：1.顾客无上限 2.服务员在没有顾客的时候可以休息，通过P(customer)实现
int waiting = 0; //表示当前有多少顾客正在等待 semaphore mutex = 1; //实现对waiting变量的互斥访问 //顾客资源，初始无顾客到店 //顾客资源不够时，服务员资源需要阻塞等待 semaphore customer = 0; //服务眼资源，初始无服务员上岗 //服务员资源不够时，顾客需要阻塞等待 semaphore server = 0; server_i(){ //消耗顾客资源，生产服务员资源 while(1) { // P(customer); //在提供服务前，需要消耗顾客资源 //如果当前没有顾客，则会被阻塞在P(customer) //当有一个顾客到店时，顾客就会生产一个顾客资源 //此时被阻塞在P(customer)的服务员就会被唤醒，并提供服务 //此时再对waiting变量进行--操作 P(mutex); //访问waiting变量时需上锁 waiting--; //顾客数 - 1，相当于“叫号”操作 V(server); //服务员生产服务员资源 V(mutex); //解锁 提供服务; } } //顾客只需要被服务一次，故无需while循环 costumer(){ //生产顾客资源，消耗服务员资源 P(mutex); //访问waiting变量时需上锁 waiting++; //顾客数 + 1，相当于"取号"操作 V(customer); //生产顾客资源 V(mutex); //解锁 //当前没有空闲服务员时，则会被阻塞在P(server) //当某个服务员完成服务时，该服务员进程执行下一轮循环 //即服务员进程执行V(server)后，顾客进程被唤醒 P(server); //消耗服务员资源 被服务; }
特点：顾客到店时，会检查waiting变量是否小于m，即等待数量有上限
int waiting = 0; semaphore mutex = 1; semaphore server = 0; semaphore customer = 0; //服务员进程和第一种情况一致 Server_i(){ while(1) { P(customer); P(mutex); waiting--; V(server); V(mutex); 提供服务; } } //需要对waiting变量进行判断是否小于m //小于m则进行和第一种情况一样的后续操作 //大于等于m则解锁后直接离开 Customer(){ P(mutex); //互斥访问变量waiting，上锁 if (waiting < m) { //当前等待顾客的个数 < m waiting++; //顾客等待数 + 1 V(customer); //生产顾客资源 V(mutex); //解锁 P(server); //消耗服务员资源 被服务; } else { //当前等待顾客的个数 >= m V(mutex); //解锁 离开; } }
特点：①在没有顾客时，服务员不能休息，必须忙等，即不断的轮询（while）检查waiting变量，判断当前是否有正在等待的顾客
②此情况下无需申明customer变量，即服务员无需阻塞
③用waiting变量判断服务员当前是否需要为顾客提供服务
int waiting = 0; //表示当前正在等待的顾客数 semaphore mutex = 1; semaphore server = 0; Server_i() { while (1) { P(mutex); //上锁 if (waiting > 0) { //当前有顾客 waiting--; //"叫号" V(server); //生产服务员资源 V(mutex); //解锁 } else { V(mutex); //解锁 continue; //进行下一轮循环，实现忙等 } 提供服务; } } Customer(){ P(mutex); //上锁 waiting++; //"取号" V(mutex); //解锁 P(server); //消耗服务员资源 被服务; }
