大题12
题目
答案
信号量设置
同步信号量 e m p t y ，初值为 10 ，表示空座位的数量，先有空座位，顾客才能取号
互斥信号量 m u t e x ，初值为 1 ，互斥使用取号机
同步信号量 f u l l ，初值为 1 ，表示座位上有顾客的数量（已占座位人数）。先座位上有顾客，营业员才能叫号
同步信号量 s e r v i c e ，初值为0，顾客获得空座位后，要等待叫号后才能被服务
semaphore empty = 10; semaphore mutex = 1; semaphore full = 0; semaphore service = 0; cobegin { process 顾客i { P(empty); P(mutex); 从取号机获取一个号码; V(mutex); V(full); P(service); 接受服务; } Process 营业员 { while (True) { P(full); V(empty); V(service); 为顾客服务; } } } coend
这是王道的代码，我下面说一下自己的理解。
我解决同步问题一直的思路就是看临界状态，即什么时候被阻塞，可以写成在…的数量为零时被阻塞就算解决。但在解释 s e r v i c e serviceservice 时却很难说通。等待营业员叫号的人数？营业员叫号的人数？这些都说不通。最后找了一个较为合理的解释：营业员可以服务的人数。那么在 V ( s e r v i c e ) V(service)V(service) 后，值为一，表示营业员可以服务的人数为一，这时一位顾客 P ( s e r v i c e ) P(service)P(service) 就可以正常接受服务，而剩下的顾客实际上就是在这个信号量下排队。
e m p t y emptyempty 我个人认为也可以理解为互斥信号量，表示座位需要互斥使用，这时 V ( e m p t y ) V(empty)V(empty) 就要写在顾客进程里。
大题13
题目
答案
可以联想到读者写者问题，那题读者用了计数器，这里我们类比一下
信号量设置
互斥信号量 m u t e x N t o S ，由北向南的车辆互斥的访问用来统计由北向南车辆的数量的计数器
互斥信号量 m u t e x S t o N ，由南向北的车辆互斥的访问用来统计由南向北车辆的数量的计数器
互斥信号量 m u t e x ，两方向的车流互斥访问桥
semaphore mutexNtoS = 1; semaphore mutexStoN = 1; semaphore mutex = 1; int numNtoS = 0; int numStoN = 0; NtoS() { P(mutexNtoS); if (numNtoS == 0) { P(mutex); } numNtoS++; V(mutexNtoS); 通过桥; P(mutexNtoS); numNtoS--; if (numNtoS == 0) { V(mutex); } V(mutexNtoS); } StoN() { P(mutexStoN); if (numStoN == 0) { P(mutex); } numStoN++; V(mutexStoN); 通过桥; P(mutexStoN); numStoN--; if (numStoN == 0) { V(mutex); } V(mutexStoN); }
显然，这种写法容易造成饥饿！
大题14
题目
答案
不能成功，有可能2个线程都在临界区。因为没有保证进入函数的原子性。
会出现死锁。flag[0]为真后切换到线程1执行，flag[1]为真。这是二者执行下一条语句时都会被阻塞，产生死锁。
大题15
题目
答案
信号量设置
互斥信号量 m u t e x ，初值为一，保证互斥访问箱子
同步信号量 f u l l 1，初值为零，表示箱子里车架的数量
同步信号量 f u l l 2 ，初值为零，表示箱子里车轮的数量
同步信号量 e m p t y ，初值为 N ，表示空闲的位置数
同步信号量 l e f t 1，初值为 N − 2 ，表示最多还可以放多少车架
同步信号量 l e f t 2 ，初值为 N − 1 ，表示留给车轮的空位置数量
semaphore mutex = 1; semaphore full1 = 0; semaphore full2 = 0; semaphore empty = N; semaphore left1 = N - 2; semaphore left2 = N - 1; 工人1活动: do { 加工一个车架; P(left1); P(empty); P(mutex); 车架放入箱子中; V(mutex); V(full1); }while(1) 工人2活动: do { 加工一个车轮; P(left2); P(empty); P(mutex); 车轮放入箱子中; V(mutex); V(full2); }while(1) 工人3活动: do { P(full1); P(mutex); 箱中取出一个车架; V(mutex); V(empty); V(left1); P(full2); P(full2); P(mutex); 箱中取出两个车轮; V(empty); V(empty); V(left2); V(left2); 组装为一台车; }while(1)
最开始写的时候没有设置信号量 l e f t 1 left1left1 和 l e f t 2 left2left2，主要是没有考虑到死锁的情况，如果工人1干活特别麻利，在工人2最多生产出来一个前，就已经把箱子填满了，那么工人二生产后也无法放入箱中，工人三也无法组装，产生死锁。
⛔️ 注意！
王道没有写互斥信号量，绝对是错误的！大家可以理一下逻辑，没有互斥，工人1和工人2是完全有可能同时进入临界区的，违背了基本原则。
我看的是22版的王道，到我看了下最新出的23版也没有修正这个错误，我觉得是很不应该的。说实话，王道错误真的是挺多的。
大题16
题目
答案
信号量设置
同步信号量 f u l l，初值为零，表示缓冲区有物品的数量
同步信号量 e m p t y ，初值为一，表示缓冲区为空的数量
互斥信号量 m u t e x ，初值为一
semaphore full = 0; semaphore empty = 1; semaphore mutex = 1; P() { while (true) { 生产物品; P(empty); P(mutex); 将产品放入缓冲区; V(mutex); V(full); } } Q() { while (true) { P(full); P(mutex); 取走产品; V(mutex); V(empty); } } R() { if (empty == 1) { 生产物品; P(empty); P(mutex); 将产品放入缓冲区; V(mutex); V(full); } if (full == 1) { P(full); P(mutex); 取走产品; V(mutex); V(empty); } }
大题17
题目
答案
信号量设置
互斥信号量，初值为一，确保互斥访问 w a i t i n g变量
同步信号量 f u l l ，初值为 0，表示已经坐人的椅子数量
同步信号量 s e r v i c e，初值为零，用来实现顾客等待理发师的同步关系
错误示范
semaphore empty = n; semaphore full = 0; semaphore service = 0; 顾客 { P(empty); V(full); P(service); } 理发师 { while (true) { P(full); V(empty); V(service); 理发; } }
这题和之前那道真题比较类似，但做的时候就发现题目中的无椅子可做就离开无法实现，按我的代码逻辑，是要阻塞在 e m p t y emptyempty 排队等待的
正确答案
semaphore mutex = 1; semaphore full = 0; semaphore service = 0; int waiting = 0; 顾客 { P(mutex); if (waiting < n) { waiting++; V(mutex); V(full); P(service); 被理发; } else { V(mutex); 无座离开; } } 理发师 { while (true) { P(full); P(mutex); waiting--; V(mutex); V(service); 理发; } }
注意这里的 V ( m u t e x )在if和else里都有，强调逻辑的严谨，避免死锁
大题18
题目
答案
明显又是读者写者问题的演变
信号量设置
互斥信号量 m u t e x ，初值为一，3类观众互斥访问录像厅
互斥信号量 m u t e x 1 ，初值为一，看第一部电影的观众互斥访问变量 c o u n t 1
互斥信号量 m u t e x 2 ，初值为一，看第二部电影的观众互斥访问变量 c o u n t 2
互斥信号量 m u t e x 3 ，初值为一，看第三部电影的观众互斥访问变量 c o u n t 3
semaphore mutex = 1; semaphore mutex1 = 1; semaphore mutex2 = 1; semaphore mutex3 = 1; int count1 = 0; int count2 = 0; int count3 = 0; P1() { P(mutex1); if (count1 == 0) { P(mutex); } count1++; V(mutex1); 看电影; P(mutex1); count1--; if (count1 == 0) { V(mutex); } V(mutex1); } P2() { P(mutex2); if (count2 == 0) { P(mutex); } count2++; V(mutex2); 看电影; P(mutex2); count2--; if (count2 == 0) { V(mutex); } V(mutex2); } P1() { P(mutex3); if (count3 == 0) { P(mutex); } count3++; V(mutex3); 看电影; P(mutex3); count3--; if (count3 == 0) { V(mutex); } V(mutex3); }
大题19
题目
答案
理论上说每次只能一辆自行车通过，所以整条路应该互斥访问，但由于 M MM 的存在，可以使左右双方向最多各有一辆车然后在这里错车
信号量设置
互斥信号量 T 2 N ，初值为1，从T到N方向只允许一辆车进入
互斥信号量 N 2 T，初值为1，从N到T方向只允许一辆车进入
互斥信号量 L ，初值为1，L这段路只允许一辆车进入，是为了保证如果从t到n方向的车骑得快的话，也必须在安全岛等待，而不能到L与另一方向的车阻塞在L。
互斥信号量 K ，初值为1
semaphore T2N = 1; semaphore N2T = 1; semaphore L = 1; semaphore K = 1; T到N方向 { P(T2N); P(L); 从T进入L; 进入M; V(L); P(K); 从K到N; V(K); V(T2N); } N到T方向 { P(N2T); P(K); 从N进入K; 进入M; V(K); P(L); 从L到T; V(L); V(N2T); }
大题20
题目
答案
信号量设置
同步信号量 f u l l，初始值 0，缓冲区的产品数
同步信号量 e m p t y ，初始值 1000 ，缓冲区剩余可以放的产品数
互斥信号量 m u t e x ，互斥访问缓冲区
互斥信号量 m u t e x _ c o n s u m e r，保证一个消费者连续取10件产品，其他消费者才能取产品
semaphore full = 0; semaphore empty = 1000; semaphore mutex = 1; semaphore mutex_consumer = 1; Producer_i() { while (true) { P(empty); P(mutex); 放产品到缓冲区; V(mutex); V(full); } } Consumer_j() { while (true) { P(mutex_consumer); for (int i = 0; i < 10; i++) { P(full); P(mutex); 从缓冲区取走一件产品; V(mutex); V(empty); } V(mutex_consumer); } }
大题21
题目
答案
信号量设置
同步信号量 c l o s e ，初值为零，先关车门再启动车辆
同步信号量 o p e n ，初值为零，先停车再开车门
semaphore open = 0; semaphore close = 0; 驾驶员 { P(close); 启动车辆; 正常行车; 到站停车; V(open); } 售票员 { 关车门 V(close); 售票; P(open); 开车门; }
大题22
题目
答案
信号量设置
同步信号量 f u l l A ，初值为 x ，表示A的信箱中邮件数量
同步信号量 f u l l B，初值为 y ，表示B的信箱中邮件数量
同步信号量 e m p t y A ，初值为 M − x ，表示信箱最多还可以放多少邮件
同步信号量 e m p t y B ，初值为 N − y ，表示信箱最多还可以放多少邮件
互斥信号量 m u t e x A ，互斥访问信箱A
互斥信号量 m u t e x B ，互斥访问信箱B
semaphore fullA = x; semaphore fullB = y; semaphore emptyA = M - x; semaphore emptyB = N - y; semaphore mutexA = 1; semaphore mutexB = 1; A { while (true) { P(fullA); P(mutexA); 从A的信箱中取出一个邮件; V(mutexA); V(emptyA); 回答问题并提出一个新问题; P(emptyB); P(mutexB); 将新邮件放入B的信箱; V(mutexB); V(fullB); } } B { while (true) { P(fullB); P(mutexB); 从B的信箱中取出一个邮件; V(mutexB); V(emptyB); 回答问题并提出一个新问题; P(emptyA); P(mutexA); 将新邮件放入A的信箱; V(mutexA); V(fullA); } }
大题23
题目
答案
信号量设置
互斥信号量 m u t e x Y 1 ，初值为一，保证线程1和3互斥访问y
互斥信号量 m u t e x Y 2 ，初值为一，保证线程2和3互斥访问y
互斥信号量 m u t e x Z ，初值为一，保证线程2和3互斥访问z
问：这里为什么不能只用一个信号量来使三个线程互斥访问变量 y？
答：实际上我们可以看出线程1和2是读者，为了最大限度地并发执行，这两个线程应该可以同时访问临界资源。而线程3既要读又要写，必须互斥
semaphore mutexY1 = 1; semaphore mutexY2 = 1; semaphore mutexZ = 1; thread1 { cnum w; P(mutexY1); w = add(x, y); V(mutexY1); } thread2 { cnum w; P(mutexY2); P(mutexZ); w = add(y, z); V(mutexZ); V(mutexY2); } thread3 { cnum w; w.a = 1; w.b = 1; P(mutexZ); z = add(z, w); V(mutexZ); P(mutexY1); P(mutexY2); y = add(y, w); V(mutexY1); V(mutexY2); }
大题24
题目
答案
在哲学家问题中，有一种解决死锁的方法就是限制最多有 n − 1 位哲学家同时进餐，而这里的碗实际上就可以起到这种效果。
如果 m < n ，那毫无疑问，可以达到限制效果
如果 m ≥ n ，我们可以形式上没收一些碗，使得信号量初值为 n − 1
信号量设置
互斥信号量 b o w l ，初值为 m i n ( n − 1 , m ) ，用于协调哲学家对碗的使用
互斥信号量 c h o p s t i c k s [ n ] 初值均设为 1 ，用于协调哲学家对筷子的使用
semaphore bowl; semaphore chopsticks[n]; for (int i = 0; i < n; i++) { chopsticks[i] = 1; } bowl = min(n - 1, m); CoBegin while (true) { 思考; P(bowl); P(chopsticks[i]); P(chopsticks[(i + 1) % n]); 就餐; V(chopsticks[i]); V(chopsticks[(i + 1) % n]); V(bowl); } CoEnd
大题25
题目
答案
这题就是简单的前驱问题，我想直接偷懒就写2个信号量，然后P两次即可。我觉得这样应该也没有错，但不敢保证，稳妥起见还是用王道的写法
信号量设置
信号量 S A C
，初值为零，控制A和C的执行顺序
以此类推
semaphore Sac = 0; semaphore Sbc = 0; semaphore Sce = 0; semaphore Sde = 0; A() { V(Sac); } B() { V(Sbc); } C() { P(Sac); P(Sbc); 完成动作C; V(Sce); } D() { V(Sde); } E() { P(Sce); P(Sde); 完成动作E; }
七、天道酬勤
王道书上出现了多次的一句话：考研复习的关键在于反复多次和全面，“偷工减料”是要吃亏的。
