实现临界段的硬件方法概要PPT课件

-,第八讲信号量,4.2.3实现临界段的硬件方法4.2.4信号量信号量的使用（互斥与同步）信号量的具体实现4.2.5进程同步与互斥举例有限缓冲区问题哲学家就餐问题,-,4.2.3实现临界段的硬件方法,利用处理机提供的特殊指令实现临界区加锁常见硬件指令有:,一、“Test_and_Set”指令二、“Swap”指令三、“Dec_and_Test”指令,-,一、“Test_and_Set”指令其功能描述为：FunctionTest_and_Set(Vartarget：boolean):boolean；beginTest_and_Set=target；target=true；end；,-,设lock为全局布尔变量，利用Test_and_Set指令，即可实现对临界区的加锁与解锁：,RepeatwhileTest_and_Set(lock)doskipcriticalsectionlock=false;non-criticalsectionUntilfalse;,-,“Test_and_Set”读后置1指令实例：TrepeatSwap(lock,key);untilkey=false;criticalsectionlock=false;non-criticalsectionUntilfalse;,-,设s为全局整形变量（初值为1)，利用下面的指令序列，可实现对临界区的加锁与解锁吗？,Repeatwhiles=0)；end；,-,设s为全局整形变量（初值为1)，利用Dec_and_Test指令，也可实现对临界区的加锁与解锁：,-,4.2.4信号量,信号量机制：“信号量”、“P、V操作”。信号量s为一整型变量，它只能通过P、V操作访问：,P(s):while!Dec_and_Test(s)dos+;V(s):s+；,-,一.原子操作原子操作：指完成某种功能且不被分割、不被中断执行的操作序列。或称此类操作序列为原子的。在单机环境下：一条硬件指令就是一个原子操作，也可以通过中断屏蔽实现由一组指令序列构成的原子操作。在多机环境下：一些硬件指令是原子的，如Test_and_Set、Swap、Dec_and_Test等。,-,一.信号量的使用(互斥与同步)互斥：用于n个进程的临界段互斥，n进程共享一个信号量mutex,初值为1，任一进程Pi的结构为：,P(mutex),V(mutex),临界段,非临界段,repeat,untilfalse,-,同步：有P1、P2两进程，必须在P1执行完S1语句后，P2才能执行S2。需同步的两进程共享信号量synch，初值为0。,Parbegin,P2:begin,P1:begin,S1;,V(synch);,end;,P(synch);,S2;,end;,Parend;,-,操作系统实现信号量时与进程调度相结合，消除忙等待现象。原则是：在P操作循环等待的地方加入放弃处理机/挂入等待队列动作，在V操作时，从等待队列中摘取进程变为就绪态。,二.信号量的具体实现,-,1、信号量定义typeSemaphore=recordvalue:integer;一个数型变量L:Listofprocess;一个PCB队列end;2、P操作P(S):S.Value-;ifS.value0then保存现场将本进程挂入S.L队列，重新调度3、V操作V(S):S.value+ifS.value0then从S.L队列取一进程挂入就绪队列,-,4.2.5进程同步与互斥举例一、有限缓冲区问题问题描述：设有n个缓冲区，一组生产者进程往缓冲区写数据，一组消费者进程从缓冲区取数据，写取以一个缓冲区为单位。说明：将缓冲池看作是共享数据，对缓冲区的操作必须是互斥操作如果缓冲区全满，生产者进程必须等待如果缓冲区全空，消费者进程必须等待,-,有限缓冲区的生产者/消费者问题（生产者和消费者共享一个产品缓冲池）,共享N个缓冲区,P1P2PmC1C2Cn,生产者,消费者,缓冲池,-,解：设置以下信号量mutex,初值为1，控制互斥访问缓冲池full,初值为0，表示当前缓冲池中满缓冲区数empty,初值为n，表示当前缓冲池中空缓冲区数有限缓冲区生产者/消费者进程描述如下：typeitem=;varbuffer=;full,empty,mutex:semaphor;nextp,nextc:item;beginfull:=0;empty:=n;mutex:=1;,-,P(empty);P(mutex);addnextptobuffer;V(full);V(mutex);untilfalse;end;,ParbeginProducer:beginrepeatproduceaniteminnextp;.,-,consumetheiteminnextc;untilfalse;end;Parend;,consumer:beginrepeatP(full);P(mutex);removeanitemfrombuffertonextc释放缓冲区V(empty);V(mutex);,-,二、哲学家就餐问题问题描述：五个哲学家五只筷子，哲学家循环做着思考和吃饭的动作，吃饭程序是：先取左边筷子，再取右边筷子，再吃饭，再放筷子。,-,实现：为每个筷子设一把锁（信号量，初值为1）varchopstick:array0,4ofsemaphore;第i个进程描述为(i=0,4):repeatP(chopsticki);取左筷子P(chopstick(i+1)mod5)；取右筷子吃V(c