06进程管理三互斥和同步二.ppt

* 读者－写者问题的信号量解法 互斥关系分析 读者和写者不能同时进入共享数据区 多个写者不能同时进入共享数据区 多个读者可以同时进入共享数据区 同步关系分析 读者进入缓冲区，写者必须等待 写者进入缓冲区，读者必须等待 三种类型： 读者优先：一旦有读者进入，则后续读者均可进入 合理顺序：读者在先来的写者之后 写者优先：只要有写者等待，则后续读者必须等待 写--写互斥 读--写互斥 * 当读者进程到来时，三种情况： 1）无读者、写者：新读者可以读 2）有写者等待，但有其它读者正在读：新读者也可以读 3）有写者写：新读者等 当写者进程到来时，三种情况： 1）无读者、其他写者：新写者可以写 2）有读者：新写者等待 3）有其它写者：新写者等待 读--写互斥 读--写互斥 写--写互斥 读--写互斥 读--写互斥 写—写互斥： 互斥信号量Wmutex 怎样判断有没有读者在读？ * 增加一个公共变量Readcount，表示当前有几个读者进程在读。 新来一个读者进程，Readcount加1； 撤销一个读者进程，Readcount减1； 第一个读者：阻塞所有写者进程；允许其他读者进程执行。 最后一个读者：唤醒可能的写者进程。 Readcount成为临界资源，必须互斥访问： 增加互斥信号量Rmutex * 采用信号量机制： 两种进程： Reader、Writer 两个信号量 Wmutex表示读者和写者之间互斥，初值是1。 公共变量Readcount表示“正在读”的进程数，初值是0； Rmutex表示读者对Readcount的互斥操作，初值是1。 Readcount＝0时允许写 分析小结 * 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个信号量表示。形成信号量数组： var chopstick:array[0,…4]of semaphore； 所有信号量初值为1，表示未被使用。 * 哲学家就餐问题—解决方法 第i位哲学家的活动描述为： Repeat wait(chopstick[i]); wait(chopstick[(i+1)mod 5]); eat; signal(chopstick[i]); signal(chopstick[(i+1)mod 5]); think; Until false; parbegin philosopher (0)； philosopher (1)； philosopher (2)； philosopher (3)； philosopher (4)； parend * 不足之处及改进方法 可能产生死锁： 五位哲学家同时饥饿，各自拿起左边的筷子时，会使得所有信号量的值为0，再