进程管理四经典进程同步问题

复习1记录型信号量及其wait、Signal操作意义；生产者--消费者问题：信号量意义、初值生产者进程中，两个wait操作顺序能否颠倒，为什么？什么情况下会产生死锁现象？And型信号量机制及其Swait、Ssignal操作意义

2经典进程同步问题生产者－消费者问题有界缓冲区问题的建模哲学家进餐问题多进程同步问题的建模读者－写者问题数据库互斥访问问题的建模理发师睡觉问题CS模式进程同步问题的建模进程通信34用信号量实现进程的同步---

生产者－消费者问题我们把前面面的例子扩充，假定缓冲区buffer是一个有界缓冲区，可存放n个数据，同时假定有n个CP进程不断地产生数据，并送buffer；有m个IOP进程从缓冲区中取数据打印。在我们生活中有很多这样的例子。44用信号量实现进程的同步---

生产者－消费者问题互斥关系分析任何时刻，只能有一个进程在缓冲区中操作引入互斥信号量（mutex）信号量初值为1.如果变为0，表明已有进程进入临界区；同步关系分析对于“生产者”而言，缓冲区满则应等待引入同步信号量“empty”，初值为n。为0表示缓冲区全满对于“消费者”而言，缓冲区空则应等待引入同步信号量“full”，初值为0表示缓冲区全空54用信号量实现进程的同步---

生产者－消费者问题64用信号量实现进程的同步---

生产者－消费者问题7我们可利用一个数组来表示上述的具有n个(0，1，…，n-1)缓冲区的缓冲池。用输入指针in来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1；用一个输出指针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1。由于这里的缓冲池是组织成循环缓冲的，故应把输入指针加1表示成in:=(in+1)modn；输出指针加1表示成out:=(out+1)modn。8在生产者进程中使用一局部变量nextp，用于暂时存放每次刚生产出来的产品；而在消费者进程中，则使用一个局部变量nextc，用于存放每次要消费的产品。9Varmutex，empty，full:semaphore:=1,n,0；

buffer:array[0，…，n-1]ofitem；

in，out:integer:=0，0；

begin

parbegin

proceducer:begin

repeatproduceranitemnextp；wait(empty)；wait(mutex)；

buffer(in):=nextp；

in:=(in+1)modn；

signal(mutex)；

signal(full)；

untilfalse；

end

consumer:begin

repeat

wait(full)；

wait(mutex)；

nextc:=buffer(out)；out:=(out+1)modn；

signal(mutex)；signal(empty)；consumertheiteminnextc；untilfalse；end

parend

end104用信号量实现进程的同步---

生产者－消费者问题总结思考1：mutex和empty两个信号量之间有什么区别吗？思考2：多信号量的操作顺序有要求吗？互斥信号量mutex：防止多个进程同时进入临界区同步信号量empty和full：保证事件发生的顺序缓冲区满时，Producer停止运行缓冲区空时，Consumer停止运行概念差别——互斥与同步（并发的两个要素）互斥：保护临界区，防止多个进程同时进入同步：保证进程运行的顺序合理思考生产者进程中，两个wait操作的顺序能否互换？生产者进程先执行wait(mutex),再执行wait(empty),何时会出错？消费者进程中，先wait(mutex)，再wait(full)何时会出错？11如果某种原因使得生产者进程执行了多次，而消费者进程一次也没执行，从而全部缓冲区都存满新数据时，再执行一次生产者进程就会死锁。如果某种原因使得消费者进程执行了多次，而生产者进程一次也没执行，从而全部缓冲区都为空时，再执行一次消费者进程就会死锁。12同步/互斥信号量的使用方法互斥信号量必定成对出现：进入临界区——临界区——退出临界区同步信号量未必成对出现，依赖于同步关系的性质同步信号量和互斥信号量的操作顺序基本原则：互斥信号量永远紧邻临界区:同步在前，互斥在后。132.4.2信号量集问题：一段处理代码需要同时获取两个或多个临界资源――可能死锁：各进程分别获得部分临界资源，然后等待其余的临界资源，"各不相让"解决方法：在一个wait原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配。称为Swait(SimultaneousWait)。在Swait时，各个信号量的次序并不重要，虽然会影响进程归入哪个阻塞队列。由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁。信号量集用于同时需要多个资源时的信号量操作；1.AND型信号量集AND型信号量集用于同时需要多种资源且每种占用一个时的信号量操作；14

Swait(S1,S2,…,Sn) //同时的P原语；

{

if(S1>=1&&S2>=1&&…&&Sn>=1){ //满足资源要求时的处理；

for(i=1;i<=n;++i)--Si; //注：与wait的处理不同，这里是在确信可满足

//资源要求时，才进行减1操作；

}else{ //某些资源不够时的处理；调用进程进入第一个小于1信号量的等待队列Sj.queue;

阻塞调用进程;将调用进程的PC置为swait操作开头

}}15

Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //释放占用的资源；

for(eachprocessPwaitinginSi.queue)//检查每种资源的等待队列的所有进程；

{

从等待队列Si.queue中取出进程P;

进程P进入就绪队列;}}

}需要注意：原先处于阻塞状态的进程，被唤醒后，从何处开始执行？与记录型信号量机制有何不同？16生产者－消费者问题

－AND型信号量机制若不愿意考虑wait操作的先后顺序，也可用AND型信号量来实现。生产者进程中：用Swait(empty,mutex)代替wait(empty)和wait(mutex),用Ssignal(mutex,full)代替signal(mutex)和signal(full)消费者进程中用Swait(full,mutex)代替wait(full)和wait(mutex),用Ssignal(mutex,empty)代替signal(mutex)和signal(empty)17producer:beginrepeatproduceaniteminnextp；Swait(empty，mutex)；buffer(in):=nextp；in:=(in+1)modn；Ssignal(mutex，full)；untilfalse；endconsumer:beginrepeatSwait(full，mutex)；Nextc:=buffer(out)；Out:=(out+1)modn；Ssignal(mutex，empty)；consumertheiteminnextc；untilfalse；end182.一般“信号量集”问题：一次需要N个某类临界资源时，就要进行N次wait操作－－低效又可能死锁方法：在AND型信号量集的基础上进行扩充：进程对信号量Si的测试值为ti（用于信号量的判断，即当Si>=ti时，表示可用资源数量大于ti，才分配资源，否则便不予分配），占用值为di（用于信号量的增减，即分配资源时Si=Si–di释放资源时Si=Si+di）Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);一般信号量集用于同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理；19

Swait(S1,S2,…,Sn) //P原语；

{while(TRUE){if(S1>=1&&S2>=1&&…&&Sn>=1){ //满足资源要求时的处理；

for(i=1;i<=n;++i)--Si; //注：与wait的处理不同，这里是在确信可满足

//资源要求时，才进行减1操作；

break;}else{ //某些资源不够时的处理；调用进程进入第一个小于1信号量的等待队列Sj.L;

阻塞调用进程;将调用进程的PC置为swait操作开头}}}20

Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //释放占用的资源；

for(eachprocessPwaitinginSi.L)//检查每种资源的等待队列的所有进程；

{

从等待队列Si.L中取出进程P;

进程P进入就绪队列;}}}}需要注意：原先处于阻塞状态的进程，被唤醒后，从何处开始执行？与记录型信号量机制有何不同？21一般"信号量集"的几种特定情况：Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配；Swait(S,1,1)表示互斥信号量；Swait(S,1,0)作为一个可控开关当S>=1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区；一般"信号量集"未必成对使用Swait和Ssignal：如：一起申请，但不一起释放；222.读者－写者问题(thereaders-writersproblem)问题描述写者向数据区放数据，读者从数据区获取数据多个读者可同时读取数据多个写者不能同时写数据读者和写者的控制策略变化多端23读者－写者问题的信号量解法互斥关系分析读者和写者不能同时进入共享数据区多个写者不能同时进入共享数据区多个读者可以同时进入共享数据区同步关系分析读者进入缓冲区，写者必须等待写者进入缓冲区，读者必须等待三种类型：读者优先：一旦有读者进入，则后续读者均可进入合理顺序：读者在先来的写者之后写者优先：只要有写者等待，则后续读者必须等待写--写互斥读--写互斥24当读者进程到来时，三种情况：1）无读者、写者：新读者可以读2）有写者等待，但有其它读者正在读：新读者也可以读3）有写者写：新读者等当写者进程到来时，三种情况：1）无读者、其他写者：新写者可以写2）有读者：新写者等待3）有其它写者：新写者等待读--写互斥读--写互斥写--写互斥读--写互斥读--写互斥写—写互斥：互斥信号量Wmutex怎样判断有没有读者在读？25增加一个公共变量Readcount，表示当前有几个读者进程在读。新来一个读者进程，Readcount加1；撤销一个读者进程，Readcount减1；第一个读者：阻塞所有写者进程；允许其他读者进程执行。最后一个读者：唤醒可能的写者进程。Readcount成为临界资源，必须互斥访问：增加互斥信号量Rmutex26采用信号量机制：两种进程：Reader、Writer两个信号量Wmutex表示读者和写者之间互斥，初值是1。公共变量Readcount表示“正在读”的进程数，初值是0；Rmutex表示读者对Readcount的互斥操作，初值是1。Readcount＝0时允许写分析小结27wait(rmutex);Ifreadcount=0then wait(wmutex);Readcount:=readcount+1;signal(rmutex);……执行读取操作wait(rmutex);Readcount:=readcount-1ifreadcount=0then signal(wmutex);signal(rmutex);读者-写者问题读者部分第一个读者要阻塞所有后来的写者最后一个读者要唤醒所有阻塞的写者28wait(wmutex);……执行写操作signal(wmutex);写者部分29增加限制条件，即同时读取的读者数不能超过RNL,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;}303.哲学家进餐问题

(thediningphilosophersproblem)问题描述：（由Dijkstra首先提出并解决）5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；31321.利用记录型信号量机制解决2.利用AND型信号量机制解决2.4.2哲学家就餐问题33哲学家就餐问题问题分析：筷子是临界资源：每根有多于一个哲学家要用，而且同时只能有一个哲学家使用5根筷子可以用5个信号量表示。形成信号量数组：varchopstick:array[0,…4]ofsemaphore；所有信号量初值为1，表示未被使用。34哲学家就餐问题—解决方法第i位哲学家的活动描述为：Repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);eat;signal(chopstick[i]);signal(chopstick[(i+1)mod5]);think;Untilfalse;parbeginphilosopher(0)；philosopher(1)；philosopher(2)；philosopher(3)；philosopher(4)；parend35不足之处及改进方法可能产生死锁：五位哲学家同时饥饿，各自拿起左边的筷子时，会使得所有信号量的值为0，再试图拿起右边的筷子时，都将拿不到筷子。解决死锁的方法：至多允许四个哲学家同时进餐。仅当哲学家的左右两支筷子均可用时，才进餐。（用AND信号量机制解决哲学家进餐问题。）奇数号哲学家先拿左边的筷子，偶数号哲学家先拿右边的筷子。36AND型信号量机制解决哲学家就餐问题要求哲学家同时获得两根筷子，否则一根也不拿。varchopstick:array[0,…4]ofsemaphore:=(1,1,1,1,1);//第i位哲学家进程：Repeatthink;Sswait(chopstick[(I+1)mod5]),chopstick[I]);Eats;Ssignal(chopstick[(I+1)mod5]),chopstick[I]);untilfalse;37思考：用其余两种思路，怎样解决哲学家就餐问题？3810.有一阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记信号，阅览室中共有100个座位，请问：(1)为描述读者的动作，应编写几个程序？设置几个进程？进程与程序间的对应关系如何？(2)用类Pascal语言和Wait,Signal操作写出这些进程间的同步算法。39答：(1)应编写1个程序；设置2个