信号量相关问题典型案例
此为博主从个人csdn博客搬运来的第三篇,内容关于操作系统中信号量的经典题目。
题干
类读者写者问题
有P1、P2、P3三类进程共享同一表格F,其中P1对F只读不写,P2对F只写不读,P3对F先读后写。不同进程可同时读F,但如果有进程写时,其余进程不能读或写。请用信号量以及P、V操作给出解决方案,并做一定分析。
理发师问题
理发店中有一位理发师,一把理发椅,N个候坐用的凳子。若无顾客,则理发师睡觉,且第一个顾客到来时叫醒理发师;若理发师正理发时有顾客到店,有空凳子就坐下,没有就离开。请用信号量以及P、V操作给出解决方案。
解法
类读者写者问题
简要分析:这是典型的读者写者问题,P1相当于读者,P2为写者,P3则是先读者后写者的角色。(本解答只是其中两种较简单的解法)
作答:
解法一
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| semaphore w = 1; semaphore mutex = 1; int count = 0;
P1(){ while(1) { P(mutex); if (count == 0) P(w); count++; V(mutex); reading... P(mutex); count--; if (count == 0) V(w); V(mutex); } }
P2(){ while(1) { P(w); writing... V(w); } }
P3(){ while(1) { P(mutex); if (count == 0) P(w); count++; V(mutex); reading... P(mutex); count--; if (count == 0) V(w); V(mutex); P(w); writing... V(w); } }
|
简要分析:此解法满足读者优先的策略,因为一旦有读者进程进入便可抢占插入到写者进程之前。
解法二
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
| semaphore rw = 1; semaphore w = 1; semaphore mutex = 1; int count = 0;
P1(){ while(1) { P(w); P(mutex); if (count == 0) P(rw); count++; V(mutex); V(w); reading... P(mutex); count--; if (count == 0) V(rw); V(mutex); } }
P2(){ while(1) { P(w); P(rw); writing... V(rw); V(w); } }
P3(){ while(1) { P(mutex); if (count == 0) P(w); count++; V(mutex); reading... P(mutex); if (count == 0) V(w); count--; V(mutex); P(w); P(rw); writing... V(rw); V(w); } }
|
简要分析:此解法可实现较为公平的读写,因为此解法遵循先来先服务的原则。
理发师问题
对于理发师问题,可设置三个信号量加以解决
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| semaphore mutex = 1; semaphore barber = 0; semaphore customer = 0; int count = 0;
Barber(){ while(1) { P(customer); P(mutex); count--; V(barber); V(mutex); 理发…… } }
Customer(){ P(mutex); if (count < N) { count++; V(customer); V(mutex); P(barber); 理发…… } else { V(mutex); } }
|