第04课进程同步

2.3进程同步与互斥

进程之间两种形式的制约关系直接相互制约关系：进程间的合作。间接相互制约关系：共享系统中的资源。进程同步：是进程之间共同完成一项任务时直接发生相互作用的关系。进程互斥：并发执行的进程因竞争同一资源而导致的相互排斥的关系称为进程间的互斥。1.临界资源临界资源：一次仅允许一个进程使用的资源称为临界资源。

临界资源分为硬件、软件临界资源。硬件临界资源如打印机，软件临界资源如某些变量、表格，也不允许两个进程同时使用。2.3.1临界资源与临界区例：假设一个飞机订票系统有两个终端，执行并发进程：T1（x）T2（x）

beginbeginifx>=1thenx=x-1;ifx>=1thenx=x-1;elseprintf(“None”);

elseprintf(“None”);endendx=x-1语句的机器语言实现：register1:=x;register1:=register1-1;x:=register1;虽然上面的两个终端程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量x。两个终端如果都对x进行减1操作，这两个操作在用机器指令实现时，可用下面的形式描述：

T1(x)T2(x)register1:=x;register2:=x;register1:=register1-1;register2:=register2-1;x:=register1;

x:=register2;假设：x的当前值是5。如果T1进程先执行左列的三条机器语言语句，然后T2进程再执行右列的三条语句，则最后共享变量counter的值为3；反之也正确。但是，如果按下述顺序执行：register1:=x;(register1=5)

register1:=register1-1;(register1=4)

register2:=x;(register2=5)

register2:=register2-1;(register2=4)

x:=register1;(x=4)x:=register2;(x=4)所以，就要把变量x当作临界资源处理，即要互斥地访问x。2.临界区(criticalsection)可把一个访问临界资源的循环进程描述如下：repeat

criticalsection;remaindersection;untilfalse;entrysectionexitsection临界区：一个进程访问临界资源的那段代码称为临界区。同步机制应遵循的规则：空闲让进。(2)忙则等待。(3)有限等待。(4)让权等待。其实,互斥关系也是一种协调关系,从广义上讲它也属于同步关系的范畴。2.3.2信号量及P、V操作

1.信号量及P、V操作信号量：一个具有非负初值的整型变量，并且有一个队列与它关联。因此，定义一个信号量时，要给出它的初值，并给出与它相关的队列指针。信号量的定义如下：typesemaphore=record/*定义信号量*/

value:integer；

L:listofprocess；

endP操作原语P(S){

S.value=S.value-1;if(S.value<0){

该进程状态置为阻塞状态 将该进程的PCB插入相应的阻塞队列末尾S.queue;}入口S=S-1S≥0进程入阻塞队列转进程调度返回是S＜0P操作功能P(S)操作可描述为：procedureP(S)

varS:semaphore;begin

S.value:=S.value-1;ifS.value＜0thenblock(S,L)endV操作原语V(S){

S.value=S.value+1;if(S.value<=0){

唤醒相应阻塞队列S.queue中阻塞的一个进程改变其状态为就绪态，并将其插入就绪队列

}}是入口S=S+1S≤0唤醒阻塞队列中的一个进程返回或转进程调度返回S＞0V

操作功能V(S)操作可描述为：procedureV(S)

varS:semaphore;begin

S.value:=S.value+1;ifS.value≤0thenwakeup(S,L);end关于信号量和P、V操作的说明：信号量的初值一定是一个非负的整数，但是在运行过程中，信号量的值可正可负。P操作和V操作是原语操作。【例2-1】假如有两个并发进程PA和PB，它们共享一个临界资源R。试用信号量及P、V操作实现进程PA和PB对临界资源R的互斥访问。解：设互斥信号量mutex，初值为PA：……P（mutex）；使用临界资源R；V（mutex）；……PB：……P（mutex）；使用临界资源R；V（mutex）；……1表示临界资源的使用情况若mutex＝1表示没有进程进入临界区，临界资源为空闲状态；若mutex＝0表示有一个进程进入临界区，无可以使用的临界资源；若mutex＝－1表示有一个进程进入临界区，另一个进程等待进入。临界资源为占用状态，并有一个进程处于等待该资源的阻塞队列中。互斥信号量mutex的物理意义：【练习2-1】试用P、V操作实现系统中若干个进程关于打印机资源的互斥使用。对于N个并发进程，信号量的取值范围是什么？2.利用信号量实现进程互斥利用信号量实现进程互斥的进程可描述如下：Vars:semaphore:=1;beginparbeginprocess1:begin repeat

P(s);criticalsection

V(s);remaindersection untilfalse;endprocess2:begin repeat

P(s); criticalsection V(s);remaindersection untilfalse;endparendend用信号量实现进程互斥的特点：要找对临界区，范围小了会出错，范围大了会影响进程运行。P、V操作位于临界区前后，在一个进程里成对出现。2个进程对1个临界资源互斥使用时S初值为1，取值范围为-1，0，1。共享缓冲区的进程的同步BUFTCPIOP共享缓冲区【例2-3】共享缓冲区进程同步设有计算进程CP和打印进程IOP，他们的关系如图2-12所示。试用信号量实现这两个进程的同步。解：设有两个信号量empty=1，full=0，empty表示缓冲区中有无数据，即缓冲区是否为空状态，full表示缓冲区中有无空位置，即缓冲区是否为满状态。CP：While(1){计算，并得到一个结果；P（empty）；将数据送入缓冲区中；V（full）；｝IOP：While(1){P（full）；从缓冲区中取出计算结果；V（empty）；将结果在打印机上打印输出；｝【练习2-4】PAPBBuffer1Buffer2PC解：设置四个信号量empty1、empty2、full1和full2。初值设置为empty1=1，full1＝0，empty2=1，full2=0。PA：While(1){P（empty1）；从磁盘中读取记录，并放入到Buffer1中；V（full1）；｝PB：While(1){P（full1）；P（empty2）；从缓冲区Buffer1中读取记录；将记录复制到Buffer2中；V（full2）；V（empty1）；｝PC：While(1){P（full2）；从缓冲区Buffer2中取出记录，并打印出来；V（empty2）；｝3.利用信号量实现进程同步:进程可描述如下：Vars1,s2:semaphore:=0,0;beginparbegin

process1:begin repeat

获得数据；

计算；送至缓冲区; V(s1);P(s2); untilfalse;endprocess2:begin repeat P(s1);

从缓冲区中取数据; 输出;V(s2); untilfalse;endparendend缓冲区P1P2用信号量实现进程同步的特点：配对的P、V操作分别在不同的进程里。初值一般为0，需要设一个以上的信号量。（例如2个进程同步，需要设2个信号量，分别用来传递信息）结论：当n个进程要互斥使用m个同类临界资源时（n>m），用信号量实现互斥时，信号量的初值应为m，即该类可用资源的数目。S的取值范围为-(n-m)~m。当s<0时，|s|为等待该资源的进程的个数；即因该资源而阻塞的阻塞队列中进程个数。当s>0时，s表示还允许进入临界区的进程数（或剩下的临界资源个数）。执行一次P操作，表示请求一个临界资源，s-1后，当s<0时，表示可用资源没有了，阻塞。执行一次V操作，表示释放一个临界资源，s+1后，若s<=0，表示还有进程在阻塞队列中，要去唤醒。2.3.3经典进程同步问题生产者－消费者问题读者－写者问题哲学家进餐问题生产者－消费者问题设有一群生产者P1，P2，…Pm和一群消费者Q1，Q2，…Qn。假定在生产者和消费者之间的