典问题进程同步习题全

公用信箱：密码：os2007设有n个进程共享一个程序段，对如下两种情况：（1)如果每次只允许一个进程进入该程序段；(2)如果每次最多允许m个进程(M＜＝n)同时进入该程序段。试问：所采用的信号量初值是否相同?信号量值的变化范围如何?所采用信号量的初值不相同。在情况(1)中，信号量的初值为1，信号量值的变化范围是l，0，-1…-(n-1)。在情况(2)中，信号量的初值为M，信号量值的变化范围是M，m-1，m-2…(m-n)。进程同步习题进程同步习题一条小河上有一座独木桥，规定每次只允许一人过桥。如果把每个过桥这看作一个进程，为保证安全，请用信号量操作实现正确管理。进程同步习题begins:semaphore;s：=1;cobeginbeginwait(s);

过桥；

signal(s)；

end Coend end 练习a,b两点间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当ab间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车时，到达a（或b）的车辆可以进入ab段，但不能从a，b点同时驶入；当某方向在ab段行驶的车辆使出了ab段且无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用wait,signal工具对ab段实现正确管理。答案：Semaphores,mutexab,mutexbaPab：Wait(mutexab)Countab++Ifcountab=1thenwait(s);Signal(mutexab)

…..wait(mutexab)countab--;ifcountab=0thensignal(s)signal(mutexab);答案：Pba:wait(mutexba)countba=countba+1;Ifcountba=1thenwait(s)signal(mutexba)enter;

……wait(mutexba)countba--;ifcountba=0thensignal(s) signal(mutexba);南京大学2000年试题桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，两个儿子专等吃盘子中的橘子，两个女儿专等吃盘子中的苹果。请用信号量操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。ParbeginFather:beginL1:p(empty);p(mutex);

放苹果；

v(mutex);v(apple);gotol1;end;Mather:beginL2:p(empty)；

p(mutex);

放橘子；

v(mutex);v(orange);gotol2;end;Daughter:beginL3:p(apple);p(mutex);

取苹果；

v(mutex);v(empty);gotol3;end;L4:p(orange);p(mutex);

取橘子；

v(mutex);v(empty);Gotol4;end;桌上有一个空的水果盘，盘中一次只能放一个水果，服务员、男顾客和女顾客共用这个盘子。服务员向盘中放草莓和香蕉，男顾客专等吃盘中的草莓，女顾客专等吃盘中的香蕉。规定每次当盘子空时只能放一个水果供顾客食用。请用信号量机制实现服务员、男顾客和女顾客三个进程的同步。题解：盘子是三个人的公有信号量，设为mutex,初值为1，服务员的私有信号量设为empty初值为1，男顾客的私有信号量为ba，初值为0，女顾客的私有信号量为cm，初值为0。waiter:beginL1:p(empty);p(mutex);

放香蕉或草莓；

v(mutex);

如果放香蕉则v(ba);

否则v(cm);gotoL1;end;Woman:beginL3:p(cm);p(mutex);

取草莓；

v(mutex);v(empty);gotoL2;end；Man:beginL2:p(ba);p(mutex);

取香蕉；

v(mutex);v(empty);gotoL2;end;汽车司机与售票员之间必须协同工作，一方面只有售票员把车门关好了司机才能开车，因此，售票员关好车门应通知司机开车。另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应通知售票员，汽车当前正在始发站停车上客，试设必要的信号灯及赋初值，写出他们的同步过程。解答：可以用两个信号量s1、s2，分别表示可以开门和可以开车，其初始值都为0，用PV操作实现为：司机：售票员：

L0:正常行车L1:售票到站停车P(S1)V(S1)开车门

P(S2)关车门启动开车V(S2)gotoL0gotoL1和尚挑水问题：寺庙里有多个小、老和尚，一水缸。小和尚取水，老和尚饮水。水缸容积10桶水，水取自同一水井，水井每次只容一个桶取水，桶总数3个，每次入、取水缸水仅为一桶。试用P、V操作描述和尚取水、饮水的互斥与同步过程。mutex1=mutex2=1;分别代表水井和水缸empty=10;水缸的入水量full=0;水缸的取水量count=3;水桶个数打水：begin p(empty) p(count) p(mutex1)

从水井打水；

v(mutex1)p(mutex2)

往缸中放水

v(mutex2) v(full) v(count) end取水：begin p(full) p(count) p(mutex2)

从水缸取水

v(mutex2) v(count) v(empty)end

哲学家进餐问题设有5个哲学家，共享一张放有五把椅子的桌子，每人分得一把椅子。但是，桌子上总共只有5支筷子，在每人两边分开各放一支。哲学家们在肚子饥饿时才试图分两次从两边拾起筷子就餐。条件：(1)只有拿到两支筷子时，哲学家才能吃饭。(2)如果筷子已在他人手上，则该哲学家必须等待到他人吃完之后才能拿到筷子。(3)任一哲学家在自己未拿到两支筷子吃饭之前，决不放下自己手中的筷子。试:(1)描述一个保证不会出现两个邻座同时要求吃饭的通信算法。(2)描述一个既没有两邻座同时吃饭，又没有人饿死（永远拿不到筷子）的算法。(3)在什么情况下，5个哲学家全部吃不上饭？1.begin2.begin3.begin4.begin5.beginP(s1)；p(s2)；p(s3)；p(s4)；p(s5)；P(s2)；p(s3)；p(s4)；p(s5)；p(s1)；吃饭；吃饭；吃饭；吃饭；吃饭；V(s1)；v(s2)；v(s3)；v(s4)；v(s1)；V(s2)；v(s3)；v(s4)；v(s5)；v(s5)；EndendendendendPi:RepeatThinkforwhilep(mutex);p(s[i]);p(s[(i+1)mod5]);v(mutex);eatforwhile;v(s[i])v(s[(i+1)mod5]);untilfalse利用AND型信号量机制实现:semaphorechopstick[5]={1，1，1，1，1};

while(true)

{

think();

Swait(chopstick[(I+1)]%5,chopstick[I]);

eat();

Ssignal(chopstick[(I+1)]%5,chopstick[I]);

}

限制人数

semaphorechopstick[5]={1，1，1，1，1};

semaphoremutex=4;

{

Repeatthink();

wait(mutex);//请求进餐

wait(chopstick[i]);//请求左手边的筷子

wait(chopstick[(i+1)%5]);//请求右手边的筷子

eat();

signal(chopstick[(i+1)%5]);//释放右手边的筷子

signal(chopstick[i]);//释放左手边的筷子

signal(mutex);//释放信号量mutexuntilfalse}

原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。

semaphorechopstick[5]={1，1，1，1，1};

voidphilosopher(inti)

{

while(true)

{

think();

if(i%2==0)//偶数哲学家，先右后左。

{

wait(chopstick[i+1]mod5);

wait(chopstick[i]);

eat();

signal(chopstick[i+1]mod5);

signal(chopstick[i]);

}

Else//奇数