生产者-消费者问题
- 该图指有两组进程共享一个环形的缓冲池。一组进程被称为生产者，另一组进程被称为消费者。
- 缓冲池是由若干个大小相等的缓冲区组成的，每个缓冲区可以容纳一个产品。
- 生产者进程不断地将生产的产品放入缓冲池，消费者进程不断地将产品从缓冲池中取出。
问题分析
①生产者—消费者之间的同步关系表现为：一旦缓冲池中所有缓冲区均装满产品时，生产者必须等待消费者提供空缓冲区；一旦缓冲池中所有缓冲区全为空时，消费者必须等待生产者提供满缓冲区。
②生产者—消费者之间还有互斥关系：由于缓冲池是临界资源，所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行。
生产者－消费者问题是相互合作进程关系的一种抽象
问题解答
①所用信号量设置如下：
Ⅰ）同步信号量empty，初值为n，表示消费者已把缓冲池中全部产品取走，有n个空缓冲区可用。
Ⅱ）同步信号量full，初值为0，表示生产者尚未把产品放入缓冲池，有0个满缓冲区可用。
Ⅲ）互斥信号量mutex，初值为1，以保证同时只有一个进程能够进入临界区，访问缓冲池。
用信号量机制解决生产者—消费者问题
- 生产者—消费者问题是相互合作的进程关系的一种抽象，例如， 在输入时，输入进程是生产者，计算进程是消费者；而在输出时，则计算进程是生产者，而打印进程是消费者， 因此，该问题有很大的代表性及实用价值
在生产者—消费者问题中要注意以下几点
- 在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对地出现；
- 对资源信号量empty和full的P和V操作，同样需要成对地出现，但它们分别处于不同的进程中。例如，P(empty)在生产进程中，而V(empty)则在消费进程中，生产进程若因执行P(empty)而阻塞， 则以后将由消费进程将它唤醒；
- 在每个程序中的多个P操作顺序不能颠倒。应先执行对资源信号量的P操作，然后再执行对互斥信号量的P操作，否则可能引起进程死锁
item B[n]; //数组B用来模拟n个缓冲区Semaphore mutex,empty,full;mutex.value=1,empty.value=n,full.value=0;int in=0; //in指针指向一个空缓冲区int out=0; //out指针指向一个满缓冲区item product; //product代表一个产品cobegin
process Producer_i() //i=1,2,3,…,m
{
while(1)
{
product=produce(); //生产一个产品
P(empty); //请求空缓冲区
P(mutex); //请求独占缓冲池
B[in]=product; //产品放到空缓冲区
in=(in+1)%n; //in移至下一个空缓冲区
V(mutex); //释放缓冲池的使用权
V(full); //满缓冲区个数增一,若有阻塞的消费者进程则唤醒之
}
}
process Consumer_j() //j=1,2,3,…,k
{
while(1){
P(full); //请求消费满缓冲区中的产品
P(mutex); //请求独占缓冲池使用权
product=B[out]; //从满缓冲区中取出产品
out=(out+1)%n; //out移至下一个满缓冲区
V(mutex); //释放对缓冲池的使用权
V(empty); //空缓冲区个数增一
//若有阻塞的生产者进程则唤醒之
consume(); //进行产品消费
}
} coend
哲学家进餐问题
问题描述:5个哲学家同坐在
一张圆桌旁，每个人的面前摆 放着一碗面条，碗的两旁各摆 放着一只筷子。假设哲学家的 生活除了吃饭就是思考问题（这是一种抽象， 即对该问题而言其他活动都无关紧要），而吃饭的时候需要左手拿一只筷子 右手拿一只筷子，然后开始进餐。 吃完后又将筷子放回原处，继续思考问题。
一个哲学家的活动进程可表示为
（1）思考问题；
（2）饿了停止思考，左手拿一只筷子（如果左侧哲学家已持有它，则需要等待）；
（3）右手拿一只筷子（如果右侧哲学家已持有它，则需要等待）；
（4）进餐；
（5）放右手筷子；
（6）放左手筷子；
（7）重新回到思考问题状态（1）
如何协调5个哲学家的活动进程
- 按哲学家的活动进程，当所有的哲学家都同时拿起左手筷子时，则所有的哲学家都将拿不到右手的筷子，并处于等待状态，那么哲学家都将无法进餐，最终饿死。
- 将哲学家的活动进程修改一下，变为当右手的筷子拿不到时，就放下左手的筷子，这种情况不一定没有问题，因为可能在一个瞬间，所有的哲学家都同时拿起左手的筷子，则自然拿不到右手的筷子，于是都同时放下左手的筷子；等一会，又同时拿起左手的筷子，如此这样永远重复下去，则所有的哲学家都将无法进餐。
利用信号量解决哲学家进餐问题
- 经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。
- 为每支筷子设置一个互斥信号量，其初值均为1。每个哲学家在进餐之前，必须借助互斥信号量的P原语进行以下两个操作：取左边的筷子和取右边的筷子。进餐完毕后，必须借助互斥信号量的V原语放下手上的两支筷子。
- 为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。
可采取以下几种解决方法
- 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐
//可预防死锁Semaphore mutex, chopstick[5];mutex.value=4;for(int i=0;i<5;i++) chopstick[i].value=1;cobegin
process Philosopher_i( ) // i=0, 1, 2, 3, 4
{ while(1)
{
think(); //思考
P(mutex); //最多允许4个哲学家申请筷子
P(chopstick[i]); //拿起左手的筷子
P(chopstick[(i+1)%5]); //拿起右手的筷子
V(mutex); //已拿到两个筷子，解除申请
eat( ); //进餐
V(chopstick[i]); //放回左手的筷子
V(chopstick[(i+1)%5]); //放回右手的筷子
}
}coend
- 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐
Semaphore chopstick[5];for(int i=0;i<5;i++) chopstick[i].value=1;cobegin
process Philosopher_i() // i=0, 1, 2, 3, 4
{
while(1)
{
think(); //思考
SP(chopstick[i],chopstick[(i+1)%5]);
//同时拿起左、右手的两只筷子
eat(); //进餐
SV(chopstick[i],chopstick[(i+1)%5]);
//同时放回左、右手的两只筷子
}
} coend
- 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、 2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐
//可预防死锁Semaphore chopstick[5];for(int i=0;i<5;i++) chopstick[i].value=1;cobegin
process Philosopher_i() // i=0, 1, 2, 3, 4
{
while(1)
{
think();//思考
if(i%2==1){//如果是奇数号哲学家
P(chopstick[i]); //拿起左手的筷子
P(chopstick[(i+1)%5]); //拿起右手的筷子
} else{ //如果是非奇数号哲学家
(chopstick[(i+1)%5]); //拿起右手的筷子
P(chopstick[i]); //拿起左手的筷子
}
eat( ); //进餐
V(chopstick[i]); //放回左手的筷子
V(chopstick[(i+1)%5]); //放回右手的筷子
}
} coend
读者—写者问题
- 一个数据文件或记录可被多个进程共享，我们把只要求读该文件的进程称为“Reader进程”，其他进程称为“Writer进程”
- 允许多个进程同时读一个共享对象，因为读不会使数据文件混乱
- 不允许一个Writer进程和其他Reader进程或Writer进程同时访问一个对象
- 读者—写者问题(Reader-Writer Problem)是指保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题
- 读者—写者问题常被用来测试新同步原语
读者-写者问题中的进程之间存在3种制约关系
- 一是读者之间允许同时读；
- 二是读者与写者之间需要互斥；
- 三是写者与写者之间也需要互斥。
解决
- 为解决读者进程、写者进程之间的同步，需要设置如下的信号量：
（1）读互斥信号量rmutex。用于使读者进程互斥地访问公用变量（共享变量）count，且rmutex.vaule的初值为1。
（2）写互斥信号量wmutex。用于实现写者进程与读者进程的互斥以及写者进程与写者进程的互斥，且wmutex.value的初值为1。
（3）公用变量count。用于记录当前正在读文件的读者进程个数，且count.value的初值为0，仅在count.value的值为0时才允许写者进程访问文件。
睡眠理发师问题
问题描述：有一个理发师、一把理发椅和n把供等侯理发顾客坐的椅子。 如果没有顾客则理发师就在理发椅子上睡觉。 当一个顾客到来时则必须唤醒理发师进行理发。 若理发师正在理发时又有顾客到来， 如果有空椅子可坐则该顾客就坐下来等侯， 如果没有空椅子可坐就离开理发厅。
解决
- 可以将睡眠理发师问题看做是n个生产者（顾客）和一个消费者（理发师）问题。
- 顾客作为生产者，每到来一个就使公用变量rc加1（记录需要理发顾客的人数），以便让理发师理发（消费）至最后一个顾客（产品）。
- 第一个到来的顾客应负责唤醒理发师，如果不是第一个到达的顾客，则在有空椅子的情况下坐下等待，否则离开理发厅（该信息可由公用变量rc获得）。
- 而理发师进程则在被唤醒后给顾客理发，理完一个顾客后若仍有顾客等待（rc不为0），则唤醒等待的顾客继续理发，如果没有顾客等待，则理发师继续睡眠直到下次到来的顾客唤醒他。
Semaphore wakeup,wait,mutex;wakeup.value=0,wait.value=0,mutex.value=1;int rc=0;cobegin
process Customer_i() //i=1, 2, 3, …, m
{
P(mutex);
rc++; //等待理发顾客人数加1
if(rc==1)
{
坐在理发椅上;
V(wakeup); //第一个顾客到来唤醒理发师
V(mutex);
P(wait); //阻塞自己等待理发师唤醒
}
else if(rc>n+1) //顾客已无椅子可坐
{
rc--; //该顾客需离开理发厅
V(mutex);
}
else //顾客不是第一个到达但有空椅子可坐
{
坐在空椅子上;
V(mutex);
P(wait); //阻塞自己等待理发师唤醒
}
离开理发厅;
}
process Barber()
{
P(wakeup); //无理发的顾客则理发师睡眠
while(1)
{
P(mutex);
if(rc!=0) //有等待理发的顾客
{
V(wait); //唤醒wait队列上第一个顾客
让被唤醒的顾客坐在理发椅上理发;
rc--; //等待理发顾客人数减1
V(mutex);
}
else
{
V(mutex);
P(wakeup); //无理发顾客则理发师睡眠
}
}
}coend
缓冲区数据传送问题
设有进程A、B和C，分别调用函数get、copy和put 对缓冲区S和T进行操作。 其中，get负责把数据块输入到缓冲区S中，copy负责从 缓冲区S中取出数据块并复制到缓冲区T中， put负责从缓冲区T中取出数据输出打印， 试描述进程A、B和C的实现算法。
Semaphore empty1,empty2,full1,full2;empty1.value=1,empty2.value=1;full1.value=0,full2.value=0;cobegin
process A()
{
while(1)
{
P(empty1); //测试缓冲区S是否非空
//非空则阻塞进程A
get(); //将数据块输入到缓冲区S
V(full1); //通知进程B可取出S中数据块
//若进程B阻塞则唤醒它
}
}
process B()
{
while(1)
{
P(full1); //S是否有数据，无则阻塞进程B
P(empty2); //测试缓冲区T是否非空
//非空则阻塞进程B
copy(); //从S中取出数据复制到缓冲区T
V(empty1); //通知进程A缓冲区S为空
//若进程A阻塞则唤醒它
V(full2); //通知C可取出缓冲区T中数据打印
//若进程C阻塞则唤醒它
}
}
process C()
{
while(1)
{
P(full2); //T是否有数据，无则阻塞进程C
put(); //取出缓冲区T中数据打印
V(empty2); //通知进程B缓冲区T为空
//如进程B阻塞则唤醒它
}
}coend
汽车过桥问题
问题描述：桥上不允许两车交会，但允许同方向多辆车依次通行 （即桥上可以有多个同方向的车）。 用P、V操作实现交通管理以防止桥上堵车。
解决方法：
- （1）如果某一方向的车先到，则让
该方向的车过桥。但可能会出现该方向
的车源源不断的到达、过桥，使得另一
方向的车处于“饥饿”状态。 - （2）参考读者-写者问题中的写者优
先算法，即桥上允许同一方向的多辆车依次过桥，如果此时对方有车提出过桥，则阻塞本方还未上桥的后续车辆，待桥上本方的车辆过完后，对方的车辆开始过桥。
Semaphore mutex1,mutex2,wait;mutex1.value=1,mutex2.value=1,wait.value=1;int count1=0,count2=0;cobegin
process N_i() //i=1,2,3,…,m
{
P(wait); //对方车辆过桥时阻止本方车辆上桥
P(mutex1); //申请对count1的访问权
//如果对方车辆已上桥则阻塞自己
if(count1==0) P(mutex2); //己方第一个上桥车辆则阻塞对方车辆上桥
count1++; //己方过桥车辆加1
V(mutex1); //释放对count1的访问权
V(wait); //允许后续车辆申请过桥;
P(mutex1); //申请对count1的访问权
count1--; //己方过桥车辆减1
if(count1==0) V(mutex2);
//己方最后一个车辆过桥后允许对方车辆上桥
//如有被阻塞的对方车辆则唤醒其过桥
V(mutex1); //释放对count1的访问权
}
process S_j() //j=1,2,3,…,n
{
P(wait); //对方车辆申请过桥时阻止本方车辆上桥
P(mutex2); //申请对count2的访问权
//如果对方车辆已上桥则阻塞自己
if(count2==0) P(mutex1);
//己方第一个上桥车辆则阻塞对方车辆上桥
count2++; //己方过桥车辆加1
V(mutex2); //释放对count2的访问权
V(wait); //允许后续到达的车辆请求过桥;
P(mutex2); //申请对count2的访问权
count2--; //己方过桥车辆减1
if(count2==0) V(mutex1);
//己方最后一个车辆过桥后允许对方车辆上桥
//如有被阻塞的对方车辆则唤醒其过桥
V(mutex2); //释放对count2的访问权
}coend
实例总结
实现进程的同步互斥实际就是给进程的并发执行增加一定的限制，以保证被访问的共享数据的完整性和进程执行结果的可再现性。