05进程管理三互斥和同步二范例.ppt

* wait(rmutex); If readcount==0 then wait(wmutex); Readcount=readcount+1; signal(rmutex); ……执行读取操作 wait(rmutex); Readcount:=readcount-1 if readcount==0 then signal(wmutex); signal(rmutex); 读者-写者问题 读者部分 第一个读者要阻塞所有后来的写者 最后一个读者要唤醒所有阻塞的写者 * wait(wmutex); ……执行写操作 signal(wmutex); 写者部分 * 增加限制条件，即同时读取的读者数不能超过RN L,mx:=RN,1 信号量集： Swait(S,d,t); Ssignal(S,d) S为信号量，d为需求量，t为下限值 写者： Swait(mx,1,1;L,RN,0); ……执行写操作 Ssignal(mx,1); 读者-写者问题一般信号量集机制 读者： Swait(L,1,1); Swait(mx,1,0); ……执行读取操作 Ssignal(L,1); If（L=1）L=L-1; If（mx=1）mx=mx; If（mx=1 L=RN) { mx=mx-1;L=L; } * 3. 哲学家进餐问题(the dining philosophers problem) 问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子； * * 1.利用记录型信号量机制解决 2.利用AND型信号量机制解决 2.4.2哲学家就餐问题 * 哲学家就餐问题 问题分析： 筷子是临界资源：每根有多于一个哲学家要用，而且同时只能有一个哲学家使用 5根筷子可以用5个信号量表示。形成信号量数组： Semaphore chopstick[5]={1,1,1,1,1} ； 所有信号量初值为1，表示未被使用。 * 哲学家就餐问题—解决方法 第i位哲学家的活动描述为： do { wait(chopstick[i]); wait(chopstick[(i+1)mod 5]); eat; signal(chopstick[i]); signal(chopstick[(i+1)mod 5]); think; }while [TRUE]; parbegin philosopher (0)； philosopher (1)； philosopher (2)； philosopher (3)； philosopher (4)； parend * 不足之处及改进方法 可能产生死锁： 五位哲学家同时饥饿，各自拿起左边的筷子时，会使得所有信号量的值为0，再试图拿起右边的筷子时，都将拿不到筷子。 解决死锁的方法： 至多允许四个哲学家同时进餐。 仅当哲学家的左右两支筷子均可用时，才进餐。（用AND信号量机制解决哲学家进餐问题。） 奇数号哲学家先拿左边的筷子，偶数号哲学家先拿右边的筷子。 * AND型信号量机制解决哲学家就餐问题 要求哲学家同时获得两根筷子，否则一根也不拿。 Semaphore chopstick [5]=(1,1,1,1,1); //第i位哲学家进程： do { think; Sswait(chopstick[(I+1)mod 5]),chopstick[I]); Eats; Ssignal(chopstick[(I+1)mod 5]),chopstick[I]); }while[TRUE]; * 思考： 用其余两种思路，怎样解决哲学家就餐问题？ * 10. 有一阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记信号，阅览室中共有100个座位，请问： (1) 为描述读者的动作，应编写几个程序？设置几个进程？进程与程序间的对应关系如何？ (2) 用类Pascal语言和Wait, Signal操作写出这些进程间的同步算法。 * 答：(1) 应编写1个程序；设置2个进程；进程与程序间的对应关系是：多对1。 (2) begin  S1:=100 (有100个座位) S2:=0 (没有阅读者)  mutex: =1 cobegin P1: repeat P(S1); P(mutex); 登记信息; V