os_ch2-2进程同步

1,2.4进程同步,2.4.1进程同步的基本概念2.4.2硬件同步机制2.4.3信号量机制（重点掌握）2.4.4信号量的应用（掌握）2.3.5管程机制（了解）,2,2.4.1进程同步的基本概念,引例1银行的联网储蓄业务允许储户同时用储蓄卡和存折对同一帐户进行存取款操作，如果某帐户同时办理（在ATM机和营业柜台）两笔存款业务（假设分别是1000和2000元）从系统角度看，有两个进程同时对储户余额等数据进行修改。如果两个进程同时读出原余额（假设为5000），两个进程分别将最新余额修改为6000（5000+1000）和7000（5000+2000）,3,引例1分析,余额为6000或7000都不正确原因：两个进程同时修改同一数据，没有进行有效控制正确方法：如果有多个进程同时修改某一数据，操作系统必须控制，一次只允许一个进程完成读数据修改数据。,4,2.4.1进程同步的基本概念,引例2编写一个复制n个记录的程序，它把文件F中的每个记录依次读到输入缓冲区R，再从R拷贝到输出缓冲区T，最后写到文件G中。假定R和T正好存放一个记录。GET：从文件F按照顺序读出一个记录，然后送入输入缓冲区R；COPY：把输入缓冲区R里的记录拷贝到输出缓冲区T里；PUT：从输出缓冲区T里读出一个记录，然后依照顺序写入文件G。,5,引例2分析,6,引例2分析,若不管GET、COPY、PUT的执行关系，有六种执行可能：1）COPYPUTGET；2）COPYGETPUT；3）PUTCOPYGET4）PUTGETCOPY；5）GETCOPYPUT；6）GETPUTCOPY,7,引例2分析,8,1.两种形式的制约关系引例1间接制约：进程的互斥(mutualexclusion)由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥进程资源进程,2.4.1进程同步的基本概念,9,引例2直接制约：进程的同步（synchronization）系统中一些进程需要相互合作，共同完成一项任务。一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态进程进程,10,例题1,【例1】进程之间存在哪几种相互制约关系？下列活动分别属于哪种制约关系？（1）若干同学都要借同一本书；（2）两队举行篮球比赛，两队员争抢球时；（3）流水线生产的各道工序；（4）商品生产和社会消费。,11,2.临界资源(criticalresource)系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量,2.4.1进程同步的基本概念,12,3.临界区（互斥区）：criticalsection一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作在进程中涉及到临界资源的程序段叫临界区演示,2.4.1进程同步的基本概念,13,例题2,【例2】一个正在访问临界资源的进程，由于申请等待I/O操作而被中断时，_。A可以允许其他进程进入与该进程相关的临界区。B不允许其他进程进入任何临界区。C可以允许其他就绪进程抢占处理器，继续运行。D不允许任何进程抢占处理器。,14,4.同步机制应遵循的准则,空闲则入：其他进程均不处于临界区,则允许进入临界区；忙则等待：已有进程处于其临界区则等待；有限等待：等待进入临界区的进程不能死等；让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）,2.4.1进程同步的基本概念,15,5.同步和互斥的解决方法软件方法：由进程自己，通过执行相应的程序指令，实现与别的进程的同步和互斥。硬件方法：通过屏蔽中断或采用专门的机器指令控制同步和互斥。操作系统或专门的程序设计语言提供支持：如信号量，管程，消息传递方法。,16,turn:0P0进入临界区1P1进入临界区.P0:dowhile(turn!=0);criticalsectionturn:=1;remaindersectionwhile(1);,补充：软件方法(1)：Dekker算法,17,软件方法(1)：Dekker算法,P1:dowhile(turn!=1);criticalsectionturn:=0;remaindersectionwhile(1);演示,18,flag:array0.1ofboolean;P0:doflag0:=true;whileflag1;criticalsectionflag0:=false;remaindersectionwhile(1);,软件方法(2)：Perterson算法,19,软件解法(2)：Perterson算法,P1:doflag1:=true;whileflag0;criticalsectionflag1:=false;remaindersectionwhile(1);演示,20,例题3,【例3】进行PO和P1的共享变量定义及其初值为:booleanflag2;intturn=0;flag0=false;flag1=false;若进行P0和P1访问临界资源的类C代码实现如下:voidp0()/进程p0voidp1()/进程p1while(TRUE)while(TRUE)flag0=TRUE;turn=1;flag1=TRUE;turn=0;While(flag1则并发执行进程PO和P1时产生的情况是(A)不能保证进程互斥进入临界区,会出现”饥饿”现象(B)不能保证进程互斥进入临界区,不会出现”饥饿”现象(C)能保证进程互斥进入临界区,会出现”饥饿”现象(D)能保证进程互斥进入临界区,不会出现”饥饿”现象,21,软件解法的缺点：1.忙等待2.实现过于复杂，需要高的编程技巧,22,2.4.2硬件解法,1.关中断repeat“屏蔽中断”指令“开中断”指令untilfalse,23,2.“测试并设置”指令,booleanTS（boolean*lock）booleanold;old=*lock;*lock=TRUE;returnold;,24,2.“测试与设置”指令,每个临界资源设置一个lock布尔变量do.whileTS(,25,3.“交换”指令,voidSwap(boolean*a,boolean*b)booleantemp;temp:=*a;*a:=*b;*b:=temp,26,每个临界资源定义一个全局变量lock每个进程定义一个局部变量keyP:dokey:=true;doswap(lock,key);while(key!=false);lock:=false;.while(TRUE);,27,2.4.3信号量机制,1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），一种卓有成效的进程同步机制。,28,信号量只能通过初始化和两个标准的原语：P操作和V操作来访问作为OS核心代码执行，不受进程调度的打断初始化指定一个非负整数值，表示空闲资源总数（又称为“资源信号量”）,29,P，V操作的实现,1.整型信号量intS;wait(S):whileS=0doskip;S:=S-1;signal(S):S:=S+1;,30,P，V操作的实现,2.记录型信号量：semaphore是一个数据结构structsemaphoreintvalue;pointer_PCBqueue;信号量说明：semaphores;,31,wait操作wait(s)s.value=s.value-;if(s.value0)该进程状态置为等待状态将该进程的PCB插入相应的等待队列s.queue末尾;,32,signal操作,signal(s)s.value=s.value+;if(s.value=1,37,Ssignal(S1,S2,Sn)for(i=1;i0时，信号量值表示该类资源的可用资源数S0时，每执行一次P操作，意味着请求分配一个单位的该类资源给执行P操作的进程，即S:=S-1；S=0时，每执行一次V操作，意味着进程释放一个单位的该类可用资源，即S:=S+1.而此时若S等待队列中有因该资源而被封锁的进程（blockeda），则把队列中的一个进程唤醒，转入就绪队列（readya）。演示,46,2利用信号量实现同步/前趋,47,2利用信号量实现同步/前趋,用P.V操作解决GET与COPY的问题,48,GET与COPY同步,从文件F取出一个记录送至输入缓冲区R,向COPY发送“可以拷贝”的消息,等待COPY发来的“拷贝结束”的消息,等待GET发来“可以拷贝”的消息,将输入缓冲区R里的记录拷贝到输出缓冲区T里,向GET发送“拷贝结束”的消息,GET,COPY,1.,1.,2.,2.,3.,3.,V(s1),P(s1),P(s2),V(s2),49,司机进程：售票员进程：REPEATREPEAT正常驾驶;售票；到站停车;P(S1)；V(S1);开车门；P(S2);关车门；离站开车;V(S2);UNTILUNTIL,1,2(S1=-1),3,4,5(S1=0),6(S2=-1),7,8,9(S2=0),10,50,2.4.5管程（monitor）机制,1、管程的提出采用PV同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中,51,管程：一种同步机制2、管程定义:指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作,52,3、管程基本思想集中式同步机制，基本思想是将共享变量以及对共享变量能够进行的所有操作集中在一个模块中，一个操作系统或并发程序由若干个这样的模块所构成，由于一个模块通常较短，模块之间关系清晰，提高了可读性，便于修改和维护，正确性易于保证。,53,4、管程的四个组成部分：管程名称局部变量和数据结构说明对该数据结构进行操作的一组过程/函数初始化代码,54,图管程的示意图,55,条件变量说明形式：Varx,y:condition。使用形式：X.wait和X.signalX.Wait作用：调用管程的进程因x条件被阻塞，进入x条件阻塞队列，释放管程X.signal作用，是重新启动一个被阻塞的进程，但如果没有被阻塞的进程，则X.signal操作不产生任何后果。,56,管程伪代码示例,Monitormointor_name/管程名sharevariabledeclarations;/局部变量conddeclarations;/条件变量public:voidP1();/过程定义voidP2();/过程定义/初始化代码,57,2.5经典进程同步问题,2.5.1生产者消费者问题问题描述：若干进程通过有限的共享缓冲区交换数据。其中，生产者进程不断写入，而消费者进程不断读出；,缓冲区,58,1、一个生产者，一个消费者，一个缓冲区,生产者While(true)生产一件产品；放入一件产品；,消费者While(true)取出一件产品；消费产品；,wait(S1),wait(S2),signal(S1),signal(S2),Question:S1,S2初值？,semaphoreS1,S2;S1=1,S2=0;,59,2、多个生产者，多个消费者，n个缓冲区,12345678910,Question:两个生产者进程同时向缓冲区中放产品？,out,in,60,voidproducer()While(true)生产一件产品；放入一件产品；,voidconsumer()While(true)取出一件产品；消费产品；,wait(empty),wait(full),signal(empty),signal(full),semaphoreS1,S2;S1=n,S2=0;,wait(mutex),signal(mutex),wait(mutex),signal(mutex),Question：wait(S1),wait(mutex)互换？,Question：signal(mutex)和signal(S2)互换？,semaphoremutex;mutex=1;,61,利用AND信号量解决生产者消费者问题,intin=0,out=0;itembuffern;semaphoremutex=1,empty=n,full=0;voidproducer()doproduceaniteminnextp;Swait(empty,mutex);buffer(in)=nextp;in=in+1)modn;Ssignal(mutex,full);while(TRUE);,62,voidconsumer()doSwait(full,mutex);nextc=buffer(out);out=(out+1)modn;Ssignal(mutex,empty);consumertheiteminnextc;while(TRUE);,63,3.利用管程解决,put(item)过程生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当countn时，表示缓冲池已满，生产者须等待。get(item)过程消费者利用该过程从缓冲池中取出一个产品，当count0时，表示缓冲池中已无可取用的产品，消费者应等待。,64,monitorproducer-consumerintin,out,count;itembuffern;conditionnotfull,notempty;intcount;public:voidput(itemx)if(countn)cwait(notfull);bufferin=x;in=(in+1)modn;count+;csignal(notempty);,65,voidget(itemx)if(count0)thencwait(notempty);x=bufferout;out=(out+1)modn;count-;csignal(notfull);in=0;out=0;count=0;PC;,66,在利用管程解决生产者-消费者问题时，其中的生产者和消费者可描述为：,voidproducer()itemx;while(TRUE).produceaniteminnextp;PC.put(x);voidconsumer()itemx;whlie(TRUE)PC.get(x);consumetheiteminnextc;.,67,2.5.2读者写者问题,问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个“读写”互斥，“写写”互斥，“读读”允许,68,采用信号量机制：write读写互斥信号量，初值是1。readnum对读者计数，初值是0；mutex表示对readnum的互斥操作，初值是1。,69,Question:,当有读者在读时，若同时有读者和写者访问共享资源?读者优先读，写者等待写者“饥饿”写者优先算法,70,2.5.3哲学家进餐问题(thediningphilosophersproblem),有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子每个哲学家的行为是思考，感到饥饿，然后吃通心粉为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子,71,第i个哲学家Varchopstick:array0.4ofsemaphore:=1,1,1,1,1;Repeat思考；饥饿；wait(chopsticki)；wait(chopstick(i+1)mod5）；进食；signal(chopsticki)；signal(chopstick(i+1)mod5)；Untilfalse;,72,问题：,若每个哲学家同时拿起各自左边的筷子？,73,为防止死锁发生可采取的措施：仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子Swait,Ssignal最多允许4个哲学家同时坐在桌子周围给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之,74,补充苹果桔子问题,桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果,75,信号量解决苹果桔子问题,sp:semaphore；/*盘子里可以放几个水果*/sg1:semaphore;/*盘子里有桔子*/sg2:semaphore;/*盘子里有苹果*/sp=1;/*盘子里允许放一个水果*/sg1=0;/*盘子里没有桔子*/sg2=0;/*盘子里没有苹果*/,76,cobeginprocessfatherbeginL1:削一个苹果；wait(sp);放苹果；signal(sg2);gotoL1;end;processdaughterbeginL4:wait(sg2);取苹果；signal(sp);吃苹果；gotoL4;end;,77,processmotherbeginL2:剥一个桔子；wait(sp);放入桔子；signal(sg1);gotoL2;end;proce