chap3-1 进程通讯

1,第三章进程通讯,3.1临界区和临界资源3.2进程互斥3.3信号灯和P、V操作3.4进程同步3.5经典的同步/互斥问题3.6结构化的同步/互斥机构管程,2,考研大纲：1、进程同步的基本概念2、实现临界区互斥的基本方法软件实现方法；硬件实现方法3、信号量4、管程5、经典同步问题生产者-消费者问题；读者-写者问题；哲学家进餐问题。,3,先来分析并发进程带来的一种现象假设一个飞机定票系统有两个终端，分别运行各自的订票管理软件：进程P1和P2，由于P1和P2是两个可同时运行的并发进程。系统会出现何种情况.,3.1临界区和临界资源,4,变量x表示系统中剩余的票数。main()intx;CobeginP1(x);P2(x)；Coend其中Cobegin和Coend表示在它们之间的程序是并发执行的，交叉调用。,5,voidP1(x)read(x);if(x=1)thenx=x-1;出票；write(x)；,临界区,6,voidP2(x)read(x);if(x=1)thenx=x-1;出票；write(x)；,临界区,7,这两个进程按各自的速率交叉执行，假设系统还剩最后一张票。,第一种情况：,结果：系统运行正常,8,第二种情况：,结果：两个不同售票点售出了两张相同的票出现了与时间有关的错误,write(x),如果保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。,9,10,什么叫临界资源？（criticalresource）一次仅允许一个进程使用的资源称为临界资源。什么叫临界区？（criticalsection）,包含对临界资源的访问操作，不允许多个并发进程交叉执行的那段程序,什么叫互斥？一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的顺序执行。即不允许两个以上的共享该资源的并发进程同时进入临界区,称为互斥。例如：进程p1，p2共享使用打印机,11,临界区的管理计算机专家Dijkstra1965年提出临界区设计原则，即一组并发进程互斥执行时必须满足：每次至多有一个进程处于临界区。如果已有进程在临界区中，其他欲进入的进程应等待：进程仅在临界区内逗留有限的时间。,12,3.2进程互斥的实现1.锁和上锁、开锁操作,当进程使用临界资源之前必须完成下列操作：考察锁位的值；若原来的值是为“0”，将锁位置为“1”,即上锁；然后可以使用该临界资源；若原来值是为“1”，说明该资源已被别人占用，则转到第步查询并等待。当进程使用完资源后，将锁位置为“0”，即开锁。,13,14,2.用上锁原语和开锁原语实现互斥,假设有两个进程共享打印机，两个进程中使用打印机的程序段为临界区。为保证打印的正确，设置打印机的锁位print，其初值为“0”，表示打印机可打印。,15,如何通过锁操作来解决前述订票系统问题？,实现临界区管理的硬件设施,关中断测试并建立指令对换指令,关中断,实现互斥的最简单方法之一关中断方法的缺点：不适合多处理器系统关中断时间过长影响系统性能。,测试并建立指令(1),TS指令的处理过程TS(x):若x=1，则x:=0；return(1)；否则return(0)；TS指令管理临界区时，可把一个临界区与一个布尔变量s相连，由于变量s代表了临界资源的状态，可把它看成一把锁。,测试并建立指令(2),chars=1;Pi(charpi)/*i=1,2,n*/dopi=TS(s)while(pi=1);临界区;s=1；,对换指令(1),对换（swap）指令的功能是交换两个字的内容：swap(a,b)temp=a;a=b;b=temp;,对换指令(2),lock:boolean;lock:=false;（开锁状态）processPi/*i=1,2,n*/pi:boolean;beginpi:=true;repeatswap(lock,pi)untilpi=false；临界区;lock:=false；end;,22,3.3信号量和P、V操作1.信号量(semaphore)的概念,信号量是一个被保护的变量，只有P操作、V操作和一种称为信号量初始化操作才能访问和改变它的值。,23,信号灯的定义：信号灯是一个结构型数据结构，包括两个分量：s,q，s：一个有非负初值的整型变量，代表资源的实体。在实际应用中应准确地说明s的意义和初值，q：每个信号灯都有一个队列，q是队列指针，其初始状态为空。,24,2.P、V操作,信号灯的值仅能由P、V操作来改变。对信号灯的P操作记为：P(S)，P操作是一个原子操作。对信号灯的V操作记为：V(S),V操作是一个原子操作。在实际操作系统中，一般情况下是由机器硬件提供P、V操作的指令，当然是原子操作，若机器不提供P、V操作的指令，则操作系统提供P、V操作原语。,25,（1）s值减1；（2）若相减结果大于等于0，则进程继续执行；（3）若结果小于0，则该进程阻塞。注：阻塞该进程包括：保存进程CPU现场；置“等待”状态；入等待队列；转进程调度；,P操作,26,（1）s值加1；（2）若相加结果大于0，进程继续执行；（3）否则，唤醒一个等待该信号灯的进程，然后本进程继续执行。,V操作,27,3.用信号灯实现进程互斥,用两个进程共享打印机的例子。设信号灯print表示打印机，初值为1，表示打印机可用(也可理解为有1台打印机)。,28,29,用P、V操作解决进程间互斥问题,P(mutex),V(mutex),P1,P2,P3,互斥区,P(mutex),P(mutex),V(mutex),V(mutex),比喻：每个人都有一把进门的钥匙，但只能容纳一个人,30,3.4进程同步（synchronism）,先看一个例子,31,到站停车,开车,开车门,关车门,售票,正常行车,。,售票员,司机,。,32,同步的概念,同步：所谓同步就是并发进程在一些关键点上可能需要相互等待与互通消息，这样的相互制约关系称为进程同步。在操作系统中，同步有各种各样，但归纳起来有两类诸进程合作完成某工作的逻辑顺序；对系统资源的共享。如两个进程共享一个缓冲区;,33,3.5经典的同步/互斥问题一生产者消费者问题,假定缓冲区buffer是一个有界缓冲区，可存放n个数据，同时假定有K个CP进程不断地产生数据，并送buffer；有m个IOP进程从缓冲区中取数据打印。,34,对于生产者进程：产生一个数据，当要送入缓冲区时，要检查缓冲区是否已满，若未满，则可将数据送入缓冲区，并通知消费者进程；否则，等待；对于消费者进程：当它去取数据时，要看缓冲区中是否有数据可取，若有则取走一个数据，并通知生产者进程，否则，等待。这种相互等待，并互通信息就是典型的进程同步。同时，缓冲区是个临界资源，因此，诸进程对缓冲区的操作程序是一个共享临界区，应互斥访问。,35,生产者消费者问题程序,36,37,分析下面的生产者消费者问题,38,二读者和写者问题,有十个读者和两个编辑同时处理一篇文章，对于读操作是可以同时进行的，若有读者正在读这篇文章，编辑就不能工作，若编辑正在处理这篇文章，读者就不能作读操作，编辑与编辑的工作也是互斥的，试用信号灯及P、V操作写出读者与编辑之间协同工作的程序描述。,39,解：mutex:用于读者与编辑、编辑与编辑的互斥信号灯，初值为1；mutex1:用于对couter操作的互斥的信号灯，初值为1。,哲学家吃面问题(1),有五个哲学家围坐在一圆桌旁，桌中央有一盘面，每人面前有一只空盘子，每两人之间放一支筷子。每个哲学家思考、饥饿、然后吃面。为了吃面，每个哲学家必须获得两支筷子，且每人只能直接从自己左边或右边去取筷子,哲学家吃面问题(2),哲学家吃面问题(3),semaphorefork5=1,1,1,1,1;CobeginPi()/i=0,1,2,3,4,while(1)思考；P(forki)；P(forki+1)；吃面；V(forki)；V(forki+1)；coend;,有若干种办法可避免这类死锁,上述解法可能出现永远等待，有若干种办法可避免死锁：至多允许四个哲学家同时吃；奇数号先取左手边的筷子，偶数号先取右手边的筷子；每个哲学家取到手边的一双筷子才吃，否则一支筷子也不取。,3.6什么是管程?为什么要引入管程,把分散在各进程中的临界区集中起来进行管理；防止进程有意或无意的违法同步操作，便于用高级语言来书写程序，也便于程序的正确性验证。,45,管程的定义,定义：将共享资源和与共享资源有关的操作集中在一个模块中，可单独编译。即管程对共享资源进行了封装，将信号量及其操作原语封装在一个对象内部。进程只能互斥进入管程，在一个管程中，不能同时有两个活动的进程。,管程的基本形式,TYPE=MONITOR;define;use；procedure();begin；end;procedure();begin；end;begin；end;,管程的结构,管程的示例,TYPESSU=MONITORintbusy;conditionnobusy;definerequire,return;usewait,signal；busy=0；/*管程变量初始化*/require()if(busy=1)wait(nobusy);/*调用进程加入等待队列*/busy=1；return()busy=0；signal(nobusy);/*从等待队列中释放进程*/,管程的条件变量(1),条件变量：当调用管程过程的进程无法继续运行时，用于阻塞进程的一种变量同步原语wait：当一个管程过程发现无法继续时，它在某些条件变量condition上执行wait，就把调用进程阻塞在该条件变量相应的队列中。,管程的条件变量(2),signal原语：对condition做此操作，将唤醒该条件变量等待队列中的一个进程。,管程的问题讨论(1),使用signal释放等待进程时，可能出现两个进程同时停留在管程内。解决方法：执行signal的进程等待，直到被释放进程退出管程或等待另一个条件(Hoare方法)。被释放进程等待，直到执行signal的进程退出管程或等待另一个条件。,管程实现：Hoare方法,霍尔方法使用P和V操作原语来实现对管程中过程的互斥调用，及实现对共享资源互斥使用的管理。不要求signal操作是过程体的最后一个操作，且wait和signal操作可被设计成可以中断的过程。,Hoare管程数据结构(1),1.mutex为保证管程中的过程互斥的被调用，定义互斥信号量mutex（初值为1）。进程调用过程前，执行P(mutex)；进程退出管程时执行V(mutex)开放管程。为了使进程在等待资源期间，其他进程能进入管程，故在wait操作中也必须执行V(mutex)，否则会妨碍其他进程进入管程，导致无法释放资源。,Hoare管程数据结构(2),2.next和next-count对每个管程，引入条件信号量next（初值为0），凡发出signal操作的进程应该用P(next)挂起自己。进程在退出管程的过程前，须检查是否有别的进程在信号量next上等待，若有，则用V(next)唤醒它。定义变量next-count（初值为0），用来记录在next上等待的进程个数，以供查询。,Hoare管程数据结构(3),3.x-sem和x-count引入信号量x-sem（初值为0），申请资源得不到满足时，执行P(x-sem)挂起。进程释放资源时，需要查询是否有别的进程在等待资源，用计数器x-count（初值为0）记录等待资源的进程数。执行signal操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用V(x-sem)来实现。,Hoare管程数据结构,每个管程定义如下数据结构：TYPEinterf=RECORDsemaphoremutex;/*进程调用管程过程前使用的互斥信号量*/semaphorenext;/*发出signal的进程挂起自己的信号量*/intnext_count;/*在next上等待的进程数*/,Hoare的wait操作,wait(semaphore,Hoare的signal操作,signal(semaphore,Hoare的外部过程形式,任何一个调用管程中过程的外部进程应组织成下列形式，确保互斥地进入管程P(IM.mutex);ifIM.next_count0thenV(IM.next);elseV(IM.mutex);,霍尔方法实现哲学家吃面问题,TYPEdining-philosophers=MONITORenumthinking,hungry,eatingstate5;semaphores5;ints-count5;InterfIM;definepickup,putdown;usewait,signal；,霍尔方法实现哲学家吃面问题,test(intk)If(state(k-1)%5!=eating)/唤醒第k个哲学家进程,霍尔方法实现五个哲学家吃面问题(3),pickup(inti)statei=hungry;test(i);if(statei!=eating)/不能吃就等待wait(si,s-counti,IM)；,putdown(inti)statei=thinking;test(i-1)%5);test(i+1)%5);,霍尔方法实现五个哲学家吃面问题(5),哲学家想吃面时调用过程pickup，吃完后调用过程putdown。,霍尔方法实现哲学家吃面问题,Cobeginphilosopher-_i()/i=0，1，4while(1)P(IM.mutex);dining-philosopher.pickup(i);if(IM.next-count0)V(IM.next);elseV(IM.mutex);吃通心面；P(IM.mutex);dining-philosopher.putdown(i);if(IM.next-count0)V(IM.next);elseV(IM.mutex);coend;,管程与进程作比较(1),管程定义的是公用数据结构，而进程定义的是私有数据结构；管程把共享变量上的同步操作集中起来，而临界区却分散在每个进程中；管程是为管理共享资源而建立的，进程主要是为占有系统资源和实现系统并发性而引入的；,管程与进程作比较(2),管程是被欲使用共享资源的进程所调用的，管程和调用它的进程不能并行工作，而进程之间能并行工作，并发性是其固有特性；管程是语言或操作系统的成分，不必创建或撤销，而进程有生命周期，由创建而产生至撤销便消亡。,68,3.7进程间高级通信,3.7.1进程通信的方式3.7.2消息缓冲机制3.7.3邮箱通信3.7.4进程通信的例子管道,69,3.7.1进程通信的方式,低级通信：只能传递状态和整数值（控制信息），包括信号量和管程机制。优点是速度快。缺点是：传送信息量小：效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。编程复杂：用户直接实现通信的细节，编程复杂，容易出错。高级通信：能够传送任意数量的数据，包括三类：共享存储区、消息或信箱、管道。,70,共享内存：相互通信的进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换。消息或信箱传递：系统为进程提供了两个高级通讯原语send和receive。当要进行消息传递时执行send。当接收者要接收消息时执行receive。共享文件模式：管道通信,71,消息的一般形式消息缓冲通信技术基本思想是：根据“生产者消费者关系”原理，利用公用消息缓冲区实现进程间的信息交换。发送进程先申请一个消息缓冲区，写入消息后把该消息缓冲区送入接收进程的消息队列中，通知接收进程。接收进程从消息队列中摘下一消息缓冲区，取出所需要的信息。,3.7.2消息缓冲机制,72,消息缓冲通信机构包含下列内容：1消息缓冲区是一个数据结构sender：消息发送者名size：消息长度Text：消息正文Next：下一个消息缓冲区的链指针,73,PCB,.Send(R,M).发送进程名：S消息长度:SIZE消息正文：TEXT,.Receive(S,N).发送进程名：S消息长度:SIZE消息正文:TEXT,M:,N:,发送进程S,消息1,消息n,消息2,.,send,Receive,74,2.发送原语和接收原语发送原语：send(,)发送一个消息给进程；发送进程存放的消息内存区的首址在中。接收原语：Receive(,)接收来自进程的消息。,75,例子：Send(,)向系统申请一个消息缓冲区；P(mutex)；将发送区消息m送入新申请的消息缓冲区；把消息缓冲区挂入接收进程的消息队列；V(mutex)；V(SM)；注：SM为私用信号量，初值为0,76,Receive(，)P(SM)；P(mutex）；摘下消息队列中的消息n；将消息n从缓冲区复制到接收区；释放缓冲区；V(metex)；,77,1信（邮）箱信箱是一种数据结构，逻辑上它分成两部分：信箱头和由若干格子组成的信箱体。信箱中每个格子存放一封信，信箱中格子的数目和每格的大小在创建信箱时确定。进程间的通信要满足如下条件：a.发送进程发送消息时，邮箱中至少要有一个空格存放该消息。b.接收进程接收消息时，邮箱中至少要有一个消息存在。,3.7.3邮箱通信-间接消息传递,78,发送进程A,邮箱体,邮箱头,接收进程B,Deposite(m),Remove(m),邮箱通信结构,79,2.发送原语和接收原语该发送进程调用过程deposit(m)将消息发送到邮箱，接收进程调用过程remove(m),将消息m从邮箱中取出。Fromnum发送进程的私用信号量。记录信箱空格，初值为nMesnum接收进程的私用信号量。记录信箱有消息的个数。,80,Deposit(m);INT；P(fromnum)；找到一个空格x；将消息m放入空格x中；置格x的标志为满；V(mesnum)；/消息个数1,81,Remove(m)INTx;P(mesnum);找到一个满格x;把满格x中的消息取出放m中;置格x标志为空;V(fromnum);,82,3.7.4进程通信的例子管道管道通信由unix首创，作为unix的一大特色立即引起了人们的兴趣。由于其有效性，一些系统继unix之后相继引入了管道技术，如PC-DOS，管道通信将成为进程通信的一种重要方式。管道是以文件系统为基础。消息缓冲通信机构是以内存缓冲区为基础。