操作系统-第2章-进程的描述与控制(下).

第二章进程的描述与控制前趋图和程序执行进程的描述2进程控制33进程同步44经典进程的同步问题3535142019/12/301进程通信44线程(Threads)的基本概念3576线程的实现4482019/12/3022.5经典进程的同步问题2.5.1生产者—消费者问题1．利用记录型信号量解决生产者—消费者问题假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用。利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产者—消费者问题可描述如下:P602019/12/303intmutex=1，empty=n，full=0；arraybuffer[0，…，n-1]；intin=0，out=0；beginparbeginproceducer:beginrepeat…2019/12/304produceranitemnextp；……wait(empty)；wait(mutex)；buffer[in]=nextp；in=(in+1)%n；signal(mutex)；signal(full)；untilfalse；end2019/12/305consumer:{wait(full)；wait(mutex)；nextc:=buffer(out)；out=(out+1)%n；signal(mutex)；signal(empty)；consumertheiteminnextc；}2019/12/306在生产者—消费者问题中应注意：首先，在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现；其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。例如，wait(empty)在计算进程中，而signal(empty)则在消费进程中，计算进程若因执行wait(empty)而阻塞，则以后将由消费进程将它唤醒；最后，在每个程序中的多个wait操作顺序不能颠倒，应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁。2019/12/3072．利用AND信号量解决生产者—消费者问题对于生产者—消费者问题，也可利用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)。利用AND信号量来解决生产者—消费者问题的算法描述如下：2019/12/308intmutex，empty，full:=1，n，0；buffer:array[0，…，n-1]ofitem；inout:integer:=0，0；beginparbeginproducer:beginrepeatproduceaniteminnextp；Swait(empty，mutex)；buffer(in):=nextp；in:=(in+1)modn；Ssignal(mutex，full)；untilfalse；end……2019/12/309consumer:beginrepeatSwait(full，mutex)；Nextc:=buffer(out)；Out:=(out+1)modn；Ssignal(mutex，empty)；consumertheiteminnextc；untilfalse；endparendend2019/12/30103．利用管程解决生产者—消费者问题在利用管程方法来解决生产者—消费者问题时，首先便是为它们建立一个管程，并命名为ProclucerConsumer，或简称为PC。其中包括两个过程：(1)put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当count≥n时，表示缓冲池已满，生产者须等待。(2)get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count≤0时，表示缓冲池中已无可取用的产品，消费者应等待。2019/12/3011PC管程可描述如下：typeproducer-consumer=monitorVarin,out,count:integer；buffer:array[0,…,n-1]ofitem；notfull，notempty:condition；procedureentryput(item)beginifcount=nthennotfull.wait；buffer(in):=nextp；in:=(in+1)modn；count:=count+1；ifnotempty.queuethennotempty.signal；end2019/12/3012procedureentryget(item)beginifcount=0thennotempty.wait；nextc:=buffer(out)；out:=(out+1)modn；count:=count-1；ifnotfull.queuethennotfull.signal；endbeginin:=out:=0；count:=0end2019/12/30132.4.2哲学家进餐问题1．利用记录型信号量解决哲学家进餐问题经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：Varchopstick:array[0，…，4]ofsemaphore；2019/12/3014所有信号量均被初始化为1，第i位哲学家的活动可描述为：repeatwait(chopstick[i])；//左边wait(chopstick[(i+1)mod5])；//右边eat；signal(chopstick[i])；signal(chopstick[(i+1)mod5])；think；untilfalse；………2019/12/3015在以上描述中，当哲学家饥饿时，总是先去拿他左边的筷子，即执行wait(chopstick[i])；成功后，再去拿他右边的筷子，即执行wait(chopstick[(i+1)mod5])；又成功后便可进餐。进餐完毕，又先放下他左边的筷子，然后再放右边的筷子。虽然，上述解法可保证不会有两个相邻的哲学家同时进餐，但有可能引起死锁。假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0；当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。对于这样的死锁问题，可采取以下几种解决方法：2019/12/3016(1)至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。(2)仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。(3)规定偶数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而奇数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。2019/12/30172．利用AND信号量机制解决哲学家进餐问题在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。描述如下：Varchopsiickarrayofsemaphore:=(1,1,1,1,1)；processirepeatthink；Swait(chopstick[(i+1)mod5]，chopstick[i])；eat；Ssignal(chopstick[(i+1)mod5]，chopstick[i])；untilfalse；2019/12/30182.4.3读者—写者问题1．利用记录型信号量解决读者—写者问题为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。另外，再设置一个整型变量Readcount表示正在读的进程数目。由于只要有一个Reader进程在读，便不允许Writer进程去写。因此，仅当Readcount=0，表示尚无Reader进程在读时，Reader进程才需要执行Wait(Wmutex)操作。若Wait(Wmutex)操作成功，Reader进程便可去读，相应地，做Readcount+1操作。同理，仅当Reader进程在执行了Readcount减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让Writer进程写。又因为Readcount是一个可被多个Reader进程访问的临界资源，因此，也应该为它设置一个互斥信号量rmutex。2019/12/3019读者—写者问题可描述如下:Varrmutex，wmutex:=1,1；Readcount=0；Reader:beginrepeatwait(rmutex)；ifreadcount==0thenwait(wmutex)；Readcount:=Readcount+1；signal(rmutex)；………..performreadoperation；wait(rmutex)；readcount:=readcount-1；ifreadcount==0thensignal(wmutex)；signal(rmutex)；2019/12/3020writer:beginrepeatwait(wmutex)；performwriteoperation；signal(wmutex)；untilfalse；endparendend…2019/12/302121请给出一个写者优先的“读者-写者”问题的算法描述。应用题举例Reader：beginrepeatwait(S);wait(rmutex);ifreadcount==0thenwait(wmutex);readcount=readcount+1;signal(rmutex);signal(S);performreadoperation;wait(rmutex);readcount=readcount-1;ifreadcount==0thensignal(wmutex);signal(rmutex);untilfalse;end;2019/12/302222writer：beginrepeatwait(mutex);ifwritecount==0thenwait(S);writecount=writecount+1;signal(mutex);wait(wmutex);performwriteoperation;signal(wmutex);wait(mutex);writecount=writecount-1;ifwritecount==0thensignal(S);signal(mutex);untilfalse;end;应用题举例2019/12/30232．利用信号量集机制解决读者—写者问题这里的读者—写者问题与前面的略有不同，它增加了一个限制，即最多只允许RN个读者同时读。为此，又引入了一个信号量L，并赋予其初值为RN，通过执行wait(L，1，1)操作，来控制读者的数目。每当有一个读者进入时，就要先执行wait(L，1，1)操作，使L的值减1。当有RN个读者进入读后，L便减为0，第RN+1个读者要进入读时，必然会因wait(L，1