进程通信与控制课件

第三讲进程同步与通信,目的与要求：了解并发程序的高级语言表示与操作系统支持下的实现；同步与互斥问题。重点与难点：并发程序中的同步与互斥,1,PPT学习交流,并发与并行的区别,并发是指多个任务在单处理机下分时运行，从宏观上看它们同时都在向前推进，但从微观上来看，它们正在分时地轮流使用处理机。并行是指多个任务在多个处理机上正在同时运行，从微观上看这些任务分别是在各自的物理处理机上分别运行。,2,PPT学习交流,3.1并发原理1、并发带来的问题,一个简单的例子（ECHO（回显）是一个共享程序）Voidecho()charout,in;cinin;Out=in;coutin;Out=in;Coutin;Out=in;Coutin;Out=in;Cout=1)X2X2-1：AjX2；输出一张票else输出“票售完”,10,PPT学习交流,考虑以下的执行次序:(a)和(b),按(a)的序列执行时，结果是正确的。按(b)的序列执行情况，则两个旅客可能各自都买到一张同天同次航班的机票，可是，Aj的值实际上只减去了1,造成余票数的不正确。,设Aj=50则x1=50,此时x2=50,此时x1=49,此时x2=49,此时Aj=49,此时Aj=49,11,PPT学习交流,特别是，当某次航班只有一张余票时，就可能把这一张票同时售给了两位旅客，显然这是不能允许的。,设Aj=1则x1=1,此时x2=1,此时x1=0,此时x2=0,此时Aj=0,此时Aj=0,12,PPT学习交流,出错原因是什么？余票额是共享变量！没有建立对共享变量的使用与保护机制。,由以上的例子说明什么？要想实现多道程序并发执行，必须设法对共享变量（资源）加入一定的管理机制和一定的保护措施，保证共享资源的协调使用，以避免出现与时间有关的错误，以保持并发程序的可再现性。,13,PPT学习交流,思考：对共享变量（资源）如何加上这种规则（机制）呢？这是现代操作系统必须解决的核心问题！同步机制：信号传递？互斥机制：加锁？,14,PPT学习交流,同步关系（亦称直接制约关系）:指完成同一任务的伙伴进程间，因需要在某些位置上协调它们的工作而相互等待、相互交换信息所产生的制约关系。如：接力跑比赛中，运动员之间要配合默契。一棒一棒接着跑。,3.2进程的互斥与同步,15,PPT学习交流,例：在计算机系统中对同一缓冲区的数据的输入与输出操作。缓冲区满才能输出，缓冲区空才能输入。,16,PPT学习交流,互斥关系（亦称间接制约关系）:即进程间因相互竞争使用独占型资源（互斥资源）所产生的制约关系。例（1）：上例中ECHO程序中的变量OUT和IN，例（2）：飞机订票系统中的余票额Aj必须互斥使用。例（3）：多个用户进程同用一台打印机时。,17,PPT学习交流,既同步又要互斥的例子：1、客车上的司机和售票员各司其职为完成同一个运送乘客的任务相互配合。互斥：司机开车时售票员不要开门，售票员开门时司机不要开车；同步：司机停车时售票员才能开门，售票员关门时司机才能开车）。,18,PPT学习交流,司机进程,售票员进程,19,PPT学习交流,互斥与同步的例子：2、有限缓冲区问题。互斥：存时不要取，取时不要存。同步：有数据才能取，有空区才能存。,20,PPT学习交流,互斥与同步的例子：3、读者与写者问题。（Readers/Writers问题）4、哲学家就餐问题。（就餐和思考需同步与互斥）,21,PPT学习交流,一、两个基本概念：临界资源（criticalresource）：一次仅允许一个进程使用的资源。如：上例ECHO程序中的共享变量IN，OUT,飞机订票系统的余票额Aj等。,3.3临界资源和临界区,22,PPT学习交流,临界段（区）（criticalsection)：各进程必须互斥执行的程序段。如：飞机余票额Aj的操作的程序段。,23,PPT学习交流,二、临界资源须互斥使用,例1打印机：P1,P2两进程使用同一打印机。如果不互斥使用会交叉输出。例2共享变量：共享变量是临界资源。,24,PPT学习交流,CobeginvoidA()N=count;N=N+100;count=N;voidB()M=count;M=M+200;count=M;Coend;,如下例对共享变量count的互斥访问。,例:若count为300,如互斥执行结果count为600,临界区,临界区,25,PPT学习交流,CobeginvoidA()N=count;N=N+100;count=N;voidB()M=count;M=M+200;count=M;Coend;,若不互斥,可能结果为500.（设count初值为300）,不互斥执行,26,PPT学习交流,三、进程互斥进入临界区的一般结构进入临界段之前要申请，获得批准方可进入；退出临界段之后要声明，以便其他进程进入。,While(1)进入区临界区退出区剩余区（其余代码）;,27,PPT学习交流,CobeginvoidA()N=count;N=N+100;count=N;voidB()M=count;M=M+200;count=M;Coend;,例如上例对共享变量count的互斥访问。,临界区,临界区,Entrycode(请求独占),exitcode(释放),Entrycode(请求独占),exitcode(释放),28,PPT学习交流,例如：对打印机（临界资源）的互斥使用,临界资源,29,PPT学习交流,四、临界区进入准则（同步机制）准则1：空闲让进。若无进程进入空闲的临界区，一次仅允许一个进程进入。准则2：忙则等待。任何时候，处于临界区内的进程不可多于一个，如果已有进程进入自己的临界区，则其他进程必须等待。,30,PPT学习交流,准则3：有限等待。进入临界区的进程要在有限时间内退出，以便其他进程及时进入自己的临界区。准则4：让权等待。如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。,31,PPT学习交流,3.4互斥实现方法,一、利用硬件方法解决进程互斥问题1、禁止中断临界段不能被中断，以保证互斥。while(1);缺点：（1）代价较高，执行效率低；（2）不能用于多处理机系统。,32,PPT学习交流,2、专用机器指令,（1）“TestandSet”指令该指令功能描述为：intts(staticintlock)intts=lock;lock=1;return(ts);这里：ts函数作为一个原语执行（即不存在中断）。lock有两种状态：当lock=0时，表示该资源空闲；当lock=1时，表示该资源正在被使用。,33,PPT学习交流,例1：利用testset指令实现互斥的循环进程描述：P(i):While(1)while(ts(lock)No-op;lock=0;,Main()lock=0;cobeginp(1);P(2);P(n);coend.,假设进程P2欲进程临界区，调用过程P（2），执行ts(lock)后返回ts为假，并置lock=1,故P2进入临界区，若此时有进程P1欲进入临界区，调用P(1),执行测试ts(lock),因lock为1，故ts返回真，故P1被拒绝进入临界区。,34,PPT学习交流,（2）Swap指令实现进程该指令功能描述为：voidsinta,b）；inttemp；temp=a；a=b；b=temp；这里，SWAP指令也是原语。在利用Swap实现进程互斥时，可为临界资源设置一个全局变量lock，其初值为0，在每个进程中再利用一个局部变量key。然后通过swap指令实现互斥。,35,PPT学习交流,例2：利用swap指令实现互斥的描述,36,PPT学习交流,P(I)：/*I为进程号，如为P（2）为进程P2调用While(1)Keyi=1;Dos);while(keyi);lock=0;,Main()lock=0;cobeginp(1);P(2);P(n);coend,例：P2先调用P过程，则此时lock=1,Key2=0,P2进入临界区。当P2正在临界区时，若有另一进程又想进入临界区，执行P（1），此时key1=1,lock=1,两者交换还是1，故P1只能循环等待。直至P2退出临界区，交换使lock=0为止。,37,PPT学习交流,3、使用特殊机器指令实现互斥的优缺点优点：（1）可用于：含有任意数量进程的单处理机或共享主存的多处理机；（2）比较简单，易于验证；（3）可支持多个临界段，每个临界段用各自的变量加以定义。如lock变量的改变。,38,PPT学习交流,缺点：（1）由于采用忙碌-等待(死等，一直循环判断等待，等到可以进入临界区为止)，所以在进程等待进入临界段时，将耗费处理机时间。（2）有可能产生饥饿。（3）有可能产生死锁。如：P1在执行TS或SWAP指令时，拥有更高优先级的进程P2中断P1，并且P2又要使用P1所占用的资源。,39,PPT学习交流,二、利用软件方法解决进程互斥问题假如有2个进程P1和P2，它们共享一个临界资源R，则P1与P2并发执行，P1与P2互斥使用R。并发执行的程序段如下：main（）cobeginp1；p2；,40,PPT学习交流,互斥执行的程序段用软件实现。算法1（单标志算法）我们设置一个公用整型变量turn，用于指示被允许进入临界区的进程的编号，即若turn=1，表示允许进程P1进入临界区。算法1对P1、P2进程的描述如下：,41,PPT学习交流,P1：while（1）while（turn！1）no-op；criticalsectionturn2；,P2：while（1）while（turn！2）no-op；criticalsectionturn1；,测试自己能否进入临界区,把临界区使用权交给P2,42,PPT学习交流,对算法一的评价：该算法可确保每次只允许一个进程进入临界区。2个进程是轮流地进入临界区。不能保证实现“空闲让进”的准则。如当进程P2暂时并未要求访问该临界资源，而P1又想再次访问该资源，但它却无法进入临界区。,43,PPT学习交流,算法2（双标志、先检查算法）基本思想：在每一个进程访问临界资源之前，先去查看一下临界资源是否正被访问。若正被访问，该进程需等待；否则进入自己的临界区。为此，设置一个数组，使其中每个元素的初值为0，表示所有进程都未进入临界区。若flag0=1时，表示进程P1正在临界区内执行；若且flag1=1时，表示进程P2正在临界区内执行。算法2的描述如下：,44,PPT学习交流,Intflag2=0，0；P1：while（1）while（flag1）no-op；flag0=1；criticalsectionflag0=0；,P2：while（1）while（flag0）no-op；flag1=1；criticalsectionflag1=0；,测试对方是否在临界区，如果在，在此循环等待,如果对方不在临界区，自己进入临界区,45,PPT学习交流,对算法2的评价：算法2解决了有空让进的问题。违背了“忙则等待”的准则。即当P1和P2都未进入临界区时，它们各自的访问标志都为0.如果P1和P2几乎是在同时都要求进入临界区，因而都发现对方的访问标志flag为0。于是2个进程都先后进入临界区，显然，这时又违背了“忙则等待”的准则。,46,PPT学习交流,算法3（双标志、先修改后检查算法）算法3中仍然使用了数组flag，但flag0=1表示进程P1希望进入临界区，然后再去查看P2的标志。若此时flag1=1，则P1等待；否则，P1进入临界区；对于进程P2亦然。,47,PPT学习交流,Intflag2=0，0；P1：while（1）Flag0=1；while（flag1）no-op；criticalsectionflag0=0；,P2：while（1）Flag1=1；while（flag0）no-op；criticalsectionflag1=0；,测试对方是否在临界区,48,PPT学习交流,对算法3的评价：算法3又会造成最终谁都不能进入临界区的后果。因而它既违背了“有空让进”的准则1，又违背了“有限等待”的准则3。例如，当P1和P2几乎在同时要进入临界区，双方都在“谦让”，结果谁也进不了临界区。,49,PPT学习交流,算法4（先修改、后检查、后修改者等待算法）,Intflag2=0，0；P1:while（1）Flag0=1；turn=2；While(flag1/信号量的值域structPCB*queue;/*queue为等待进程链表指针S;,信号量变量S的值只能通过P、V操作来改变它。,54,PPT学习交流,二、P和V操作原语的伪代码形式如下：,P操作(或wait操作)描述：VoidP(semaphoreS)S.value-;if(s.value0)Block(S.queue);,V操作(或singal操作)描述：VoidV(semaphoreS)s.value+;if(s.value=0)wakeup(S.queue);,通过对信号量做P、V操作来实现互斥访问临界区。,55,PPT学习交流,三、N个进程利用信号量、PV操作互斥使用临界段的一般结构：设互斥信号量S的初值为1,临界资源如打印机,S.value-;if(S.value0说明等待队列queue中无等待的进程）如果s.value=0,则释放信号量队列L上的第一个PCB所对应的进程（把阻塞态改为就绪态），执行V操作的进程继续执行。,60,PPT学习交流,五、信号量机制物理含义1、信号量初值S.value表示系统中某种资源的数目，又称资源信息量。2、执行一次P操作意味着请求分配一个单位资源，因此S.value的值减1；当S.value0时,表示等待队列无等待该信号量的进程,其值表示还可用的资源数目.做P操作的进程继续执行.,61,PPT学习交流,3、执行一次V操作意味着释放一个单位资源，因此S.value的值加1；若s.value0时,表示等待队列无等待该信号量的进程,其值表示还可用的资源数目.做V操作的进程继续执行。,62,PPT学习交流,六、信号量的一般应用1、用信号量实现进程互斥要使N个进程互斥使用某临界资源（如打印机），只要在每个进程的使用临界资源的临界区（即程序段）前加P操作，退出临界区前加V操作，并且n个进程共享一个互斥信号量S,初值为1（即只允许一个进程进入临界区）。,63,PPT学习交流,例1：进程Pa（分配进程）和Pb（释放进程）对某一打印机分配表的互斥使用情况，可用信号量实现。设互斥信号量mutex，其初值为1。则Pa和Pb的临界区代码可按下述方式组织：,Pa:P(mutex)分配打印机（读写分配表）V(mutex),Pb:P(mutex)释放打印机（读写分配表）V(mutex),mutex.value-;if(mutex.value0)Block(mutex.L);,mutex.value+;if(mutex.value=1)Ri:=Ri-1;Aj:=Ri;,V(S);输出一张票；elseV(S);输出“票已售完”；;/*过程结束cobeginP(1),P(2),P(n),65,PPT学习交流,2、用信号量实现进程同步根据信号量的初值，在某个进程的程序段前加P操作，在另一个的程序段后加V操作,66,PPT学习交流,例2、有P1,P2两进程，必须在P1执行完S1语句后，P2才能执行S2。请用PV操作实现同步（需同步的两进程共享信号量s，初值为0。）,P2:,P1:,S1;,V(s);,;,P(s);,S2;,;,67,PPT学习交流,例2、有P1,P2两进程，必须在P1执行完S1语句后，P2才能执行S2。请用PV操作实现同步（需同步的两进程共享信号量s，初值为0。）,P2:,P1:,S1;,V(s);,;,P(s);,S2;,;,信号量初值为0，则P2不可能先执行，因为执行P（s）操作时，S=-1=n)notfull.wait;Bufferin=nextp;In=(in+1)modn;Count+;Ifnotempty.queuenotempty.signal;,Entypget(item)if(count=0)notempty.wait;nextc=bufferout;out=(out+1)modn;count-;Ifnotfull.queuenotfull.signal;csignal(notfull);in=out=0;count=0;,共享变量说明,放产品过程,取产品过程,局部变量置初值,如果缓冲池已满，放产品过程入等待队列,如果等待取的队列中有进程，则唤醒,如无产品可取，则该进程进入等待队列,如果等待放的队列中有进程，则唤醒,108,PPT学习交流,Voidproducer()while(1)produceaniteminnextp;producer-consumer.put(item);Voidconsumer()while(1)producer-consumer.get(item);Consumetheiteminnextc;,Main()Cobeginproducer();consumer();.,109,PPT学习交流,三、管程与进程的异同(1)二者都定义了数据结构。进程定义的是私有数据结构PCB,管程定义的是公共数据结构，如消息队列。(2)二者都在各自的数据结构上进行有意义的操作。进程是由顺序程序执行有关操作，管程主要是进行同步操作和初启操作。(3)二者设置的目的不同。进程是为了更好地实现系统的并发性而设置的，管程是为了解决进程的公共变量，为了解决共享资源的互斥使用问题而设置的。,110,PPT学习交流,（4）进程通过调用管程中的过程对共享变量实行操作。此时，该过程就如通常的子程序一样被调用而处于被动工作方式，因此，称管程为被动成分。与此相对应的进程则处于主动工作方式而被称为主动成分。（5）由于进程是主动成分，故进程之间能被并发执行，然而管程是被动成分，管程和调用它的进程不能并发执行。（6）进程可由“创建”而诞生，由“撤消”而消亡，有生命期，管程是操作系统中的固有成分，无需进程创建，也不能为进程所撤消，只能被进程调用。,111,PPT学习交流,3.5进程通信一、进程通信的概念与类型1、概念进程通信指进程之间的信息交换。2、类型。依据交换信息量的多少。（1）低级通信。如进程的同步与互斥的信号量机制。特点：一是效率低二是通信对用户不透明。,112,PPT学习交流,（2）高级通信。指用户可直接通过操作系统提供的一组通信命令高效地传送大量数据的一种通信方式。特点：一是效率高。二是通信对用户透明。,113,PPT学习交流,二、高级通信机制的类型1、共享存储器系统通信的进程共享某些数据结构或共享存储区，进程之间能够通过它们进行通信。（1）基于共享数据结构的通信方式进程间同步处理由程序员解决。（2）基于共享存储区的通信方式,114,PPT学习交流,2、消息传递系统在消息传递中，进程间的数据交换以消息为单位。程序员直接利用系统提供的通信命令（原语）来实现。（1）直接通信方式。发送进程直接将消息发送给接收进程并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列取得消息。,115,PPT学习交流,（2）间接通信方式。发送进程将消息发送到某种中间实体中，接收进程从中取得消息。这种中间实体一般为信箱，故也称之为信箱通信方式。,116,PPT学习交流,3、管道通信方式管道是指用于连接一个读进程和一个写进程以实现它们之间通信的共享文件，又称为pipe文件。管道通信须提供3方面的协调能力：（1）互斥（2）同步（3）对方是否存在,117,PPT学习交流,三、直接通信和间接通信1.直接通信方式指发送进程利用操作系统提供的发送和接收命令（原语）进行通信。发送消息时直接指明接收者或发送者进程ID。发送原语：send（receiver,message）;接收原语：receiver(sender,message);,118,PPT学习交流,举例：（UNIX中两进程利用信号通信）。ProcessAsend(1040,SIGUSR1);#向1040号进程发送一个SIGUSR1信号。ProcessBreceive(SIGUSR1,func);#当收到SIGUSR1信号时，就执行func(),如果SIGUSR1信号未到，则系统登记func函数，待其信号到时再调用执行。,119,PPT学习交流,2.间接通信方式基本思想：系统为每个信箱设一个消息队列，消息发送和接收都指向该消息队列，（每个进程可以对消息队列发送并接收/只发送/只接收)缺点：必须有一个通信双方共享的一个逻辑消息队列（UNIX的PIPE，FIFO及IPC消息传递机制都属于这种形式），使用时消息发送者约定写方式打开信箱,消息接收者约定读方式打开信箱或同时读写打开。优点：很容易建立双向通信链(只要对信箱说明为读写打开)。,120,PPT学习交流,四、用消息传递实现互斥,121,PPT学习交流,ProgrammulualexclusionConstn=;(*进程个数*)ProcedureP(I:integer);Varmsg:message;Beginrepeatreceive(mutex,msg);send(mutex,msg);foreverEnd;,Begin(*mainprogram*)Create-mailbox(mutex);Send(mutex,null);ParbeginP(1);P(2);P(n);ParendEnd.,122,PPT学习交流,又例：用消息传递解决有限缓冲区的生产者/消费者问题使用两个邮箱（两个缓冲区）。生产者将生产出的数据作为消息送到邮箱mayconsume,只要邮箱中有消息，消费者就可以消费。最初，邮箱mayproduce充满了与缓冲区容量相同数量的空消息，mayproduce中的消息随生产者的生产而减少，随消费者的消费而增加。,123,PPT学习交流,ProgramproducerconsumerConstcapacity=.;null=;VarI:integer;Procedureproducer;varpmsg:message;Beginwhiletruedobeginreceive(mayproduce,psmg);pmsg:=produce;send(maysonsume,pmsg)endEnd;Procdureconsumer;Varcmsg:message;Begin,Whiletruedobeginreceive(mayconsume,cmsg);consume(cmsg);send(mayprocedure,null)endEnd;Begin父进程Createmailbox(mayproduce);Createmailbox(mayconsume);ForI=1tocapacitydosend(mayproduce,null);Parbeginproducer;consumerParendEnd.,124,PPT学习交流,逻辑通信链容量：在通信发送者和接收者之间存在一条逻辑通信链，设链的容量是指该链暂存消息的能力。1.容量为0。表示通信链不能暂存任何消息，链中无缓冲(不计链头的发送缓冲和链尾的接收缓冲)，这要求接收方必须在发送方之前发接收请求，否则发送失败。2.有限容量。队列的长度为n,至多可存放n条消息。表示链中有有限缓冲区、发送者不必等接收者发出接收请求，不必等接收者准备好接收缓冲区，即可将消息存于通信链