进程同步与通信xiuga.ppt

第3章进程同步与通信,进程同步与互斥,经典进程同步问题,管程,AND信号量,进程通信,取空闲块的进程Getspace:Begin局部变量gg=stacktoptop=top1返回值为gEnd,释放数据块ad的进程Release(ad):Begintop=top1stacktop=adEnd,设t0时刻，top=3。假设执行顺序为：先执行Release(ad)的第一条：top=top1=31=4再执行Getspace：g=stack4，top=top1=3再执行Release(ad)的第二条：stack3=ad,3.1进程的同步与互斥,3.1进程的同步与互斥,OS引入进程后，由于进程的异步性，可能会导致程序执行结果的不确定性，使程序执行时出现不可再现性。进程互斥与同步的主要任务是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。,程序的制约方式有如下两种：（1）间接制约方式。互斥这是由于竞争相同资源而引起的，得到资源的程序段可以投入运行，而得不到资源的程序段就是暂时等待，直至获得可用资源时再继续运行。（2）直接制约方式。同步这通常是在那些逻辑上相关的程序段之间发生的。一般是由于各种程序段要求共享信息引起的。,进程同步的基本概念,同步：指多个进程中发生的事件存在着某种时序关系，它们必须按规定时序执行，以共同完成一项任务。互斥：多个进程不能同时使用同一资源。临界资源：某段时间内仅允许一个进程使用的资源。临界区：每个进程中访问临界资源的那段代码。,例：P1，P2两进程共享变量COUNT（COUNT的初值为5）P1:R1=COUNT;R1=R1+1;COUNT=R1;P2:R2=COUNT;R2=R2+1;COUNT=R2;,分析：1执行顺序P2P1执行结果P1：COUNT为7，P2：COUNT为6。2执行顺序P1：R1=COUNTP2：R2=COUNTP1：R1=R1+1；COUNT=R1P2：R2=R2=1；COUNT=R2执行结果P1：COUNT为6，P2：COUNT为6。,临界资源实例,？,例：P1，P2两线程共享变量COUNT（COUNT的初值为5）P1:R1=COUNT;R1=R1+1;COUNT=R1;P2:R2=COUNT;R2=R2+1;COUNT=R2;,用Bernstein条件考察R（P1）=R1，COUNTW（P1）=R1，COUNTR（P2）=R2，COUNTW（P2）=R2，COUNTR（P1）W（P2）,临界资源实例,！,P1、P2不符合Bernstein条件必须对程序的执行顺序施加某种限制,While(1),空闲让进当无进程处于临界区时，临界资源处于空闲状态。此时允许进程进入临界区。忙则等待当已有进程进入临界区时，临界资源正在被访问，其他想进入临界区的进程必须等待。有限等待对于要求访问临界资源的进程，应保证在有效的时间内进入，以免进入“死等”状态。让权等待当进程不能进入临界区时，应立即释放处理机，以免进程进入“忙等”。,进入区,临界区,退出区,剩余区,同步机制应遵循的准则,访问临界资源的进程描述为,互斥实现的硬件方法,禁止中断专用机器指令TS（TestandSet）指令Swap指令,/TS指令：booleanTS(lock);booleanlock;booleantemp;temp=lock;lock=true;returntemp;,Lock有两种状态：当lock=false时，表示资源空闲;当lock=true时，表示资源正在被使用。为了实现互斥，设布尔变量lock，其初值为false,表示资源空闲。利用TS指令实现互斥。缺点：没有做到：“让权等待”。,/TS指令的使用while(TS(lock)/*什么也不做*/;临界区;lock=false;剩余区;,TS（TestandSet）指令,互斥实现的软件方法,/进程0while(turn!=0)/什么都不做;临界区;turn=1;剩余区;/进程1while(turn!=1)do/什么都不做;临界区;turn=0;剩余区;,设置公共整型变量turn，用于指示进入临界区的进程编号i(i=0,1)。使P0、P1轮流访问临界资源。缺点：强制性轮流进入临界区，不能保证“空闲让进”。,单标志算法,！,/进程0while(flag1)/什么都不做;flag0=true;临界区;flag0=false;剩余区;/进程1while(flag0)/什么都不做;flag1=true;临界区;flag1=false;剩余区;,设置数组flag，初始时设每个元素为false,表示所有进程都未进入临界区。若flagi=true,表示进程进入临界区执行。在每个进程进入临界区时，先查看临界资源是否被使用，若正在使用，该进程等待，否则才可进入。解决了“空闲让进”问题。缺点：可能同时进入临界区，不能保证“忙则等待”。,用软件方法解决互斥问题,双标志、先检查算法,！,/进程0flag0=true;while(flag1)/什么也不做;临界区;flag0=false;剩余区;,两进程先后同时作flagi=true;缺点：保证了不同时进入临界区，但又可能都进不去。不能保证“有空让进”。,/进程1flag1=true;while(flag0)/什么也不做;临界区;flag1=false;剩余区;,双标志、先修改后检查算法,用软件方法解决互斥问题,！,/进程0flag0=true;turn=1;while(flag1),保证了“有空让进”和“忙则等待”。,/进程1flag1=true;turn=0;while(flag0),先修改、后检查、后修改算法,用软件方法解决互斥问题,！,信号量和PV操作,1965年，荷兰学者Dijkstra提出了信号灯机制，卓有成效地解决了进程同步问题。记录型信号灯的定义structsemaphoreintvalue;structPCB*queue;,信号灯的PV操作,voidwait(semaphores)s.value=s.value-1;if(s.value0)block(s.queue);/*将进程阻塞，并将其投入等待队列s.queue*/voidsignal(semaphores)s.value=s.value+1;if(s.value=0)wackup(s.queue);/*唤醒阻塞进程，将其从等待队列s.queue取出，投入就绪队列*/,从资源的观点看信号灯的意义:s.value的初值表示系统中某种资源数目。wait(s)表示要申请一个资源。signal(s)表示要释放一个资源。s.value0时，|s.value|表示等待队列的进程数。,信号灯的物理意义,信号量和P，V原语,信号量sem：整数。大于等于0时，表示当前可用的资源个数；小于0时，表示正在等待该资源的进程数。,sem=sem1,调用它的进程入等待队列,转进程调度,sem0,是,sem0,是,sem0,返回,P原语,V原语,sem为互斥信号量，取值（1，0，-1）。sem=1表示有一个空闲资源。即，进程PA和PB都没进临界区。sem=0表示有0个空闲资源。即，某进程已经进入临界区sem=-1表示差一个空闲资源。即，某进程已经进入临界区，但另有一进程已经做了P原语，正在等待。,Pb:P(sem)V(sem);,可具体化,用信号灯解决互斥问题,用信号灯解决互斥问题,semaphoremutex=1;P1:while(1)P(mutex);临界区;V(mutex);剩余区;,P2:while(1)P(mutex);临界区V(mutex);剩余区;,A：测试，直到buf为空计算计算结果bufgotoA,计算进程Pc,打印进程Pp,B：测试，直到buf满打印buf中的数据清除buf中的数据gotoB,这里假定已经对公有缓冲区buf进行了互斥措施。缺点：用“测试”来实现同步，消耗大量CPU时间。,用“测试”来实现同步,A：wait(Bufempty)计算计算结果bufBufempty=falsesignal(Buffull=true)gotoA,计算进程Pc,打印进程Pp,B：wait(Buffull)打印buf中的数据清除buf中的数据Buffull=falsesignal(Bufempty=true)gotoB,1、设消息名Bufempty表示buf空，消息名Buffull表示buf满。2、初始化Bufempty=true，Buffull=false。,用wait和signal实现同步,私用信号量,公有信号量：用于互斥。表示公有资源是否可用。私用信号量：用于同步。例如，Bufempty是计算进程的私用信号量，Buffull是打印进程的私用信号量。,用P，V原语实现同步,1、设Bufempty为进程Pa的私用信号量，Buffull为Pb的私用信号量2、初始化：Bufempty=n；Buffull=0。,Pa：deposit(data)局部变量xP(Bufempty)选择一个空区Buf(x)Buf(x)dataBuf(x)置满标记V(Buffull),发送进程Pa,接收进程Pb,B：remove(data)局部变量xP(Buffull)选择一个空区Buf(x)dataBuf(x)Buf(x)置空标记V(Bufempty),问题：需要考虑互斥吗？,用信号灯解决同步问题,semaphorea,b=0,0;s1;V(a);V(b)P(a);s2P(b);s3,生产者消费者问题读者写者问题哲学家进餐问题打磕睡的理发师问题,3.2经典进程同步问题,生产者-消费者问题,指有两组进程共享一个环形的缓冲池。一组进程被称为生产者，另一组进程被称为消费者。缓冲池是由若干个大小相等的缓冲区组成的，每个缓冲区可以容纳一个产品。生产者进程不断地将生产的产品放入缓冲池，消费者进程不断地将产品从缓冲池中取出。,用信号量解决“生产者-消费者”问题,voidconsumer()/消费者进程while(true)P(full);P(mutex);data_c=bufferj;j=(j+1)%n;V(mutex);V(empty);consumetheitemindata_c;,semaphoremutex=1;semaphoreempty=n;semaphorefull=0;,inti,j;ITEMbuffern;ITEMdata_p,data_c;,voidproducer()/生产者进程while(true)produceanitemindata_p;P(empty);P(mutex);bufferi=data_p;i=(i+1)%n;V(mutex);V(full);,读者-写者问题,一个数据对象若被多个并发进程所共享，且其中一些进程只要求读该数据对象的内容，而另一些进程则要求写操作，对此，我们把只想读的进程称为“读者”，而把要求写的进程称为“写者”。问题描述：读者可同时读；读者读时，写者不可写；写者写时，其他的读者、写者均不可进入。,读者进程：while(true)有人要读P(Wmutex);读;无人读了V(Wmutex);,写者进程：while(true)P(Wmutex);写;V(Wmutex);,semaphoreWmutex=1;,用信号量解决读者-写者问题,voidreader()/*读者进程*/while(true)P(Rmutex);if(Rcount=0)P(Wmutex);Rcount=Rcount+1;V(Rmutex);read;/*执行读操作*/P(Rmutex);Rcount=Rcount-1;if(Rcount=0)V(Wmutex);V(Rmutex);,SemaphoreWmutex,Rmutex=1,1;intRcount;,用信号量解决读者-写者问题,voidwriter()/*写者进程*/while(true)P(Wmutex);write;/*执行写操作*/V(Wmutex);,哲学家进餐问题,五个哲学家，他们的生活方式是交替地思考和进餐。哲学家们共用一张圆桌，围绕着圆桌而坐，在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时拿起其左、右的两支筷子，试图进餐，进餐完毕又进行思考。这里的问题是哲学家只有拿到靠近他的两支筷子才能进餐，而拿到两支筷子的条件是他的左、右邻居此时都没有进餐。,semaphorechopstick5=1,1,1,1,1;voidphilosopher(inti)/*哲学家进程*/while(true)P(chopsticki);P(chopstick(i+1)%5);eating;/*进餐*/V(chopsticki);V(chopstick(i+1)%5);thinking;/*思考*/,用信号量解决哲学家进餐问题,哲学家能顺利地吃到饭吗,？,打磕睡的理发师问题,理发店有一名理发师，一把理发椅，还有N把供等候理发的顾客坐的普通椅子。如果没有顾客到来，理发师就坐在理发椅上打磕睡。当顾客到来时，就唤醒理发师。如果顾客到来时理发师正在理发，顾客就坐下来等待。如果N把椅子都坐满了，顾客就离开该理发店去别处理发。,用信号量解决打磕睡的理发师问题,voidcustomer()/顾客进程P(mutex);if(waiting=1,AND信号量定义,AND信号量定义,Ssignal(s1,s2,sn)for(i=1;i=n;i=i+1)si=si+1;for(等待队列si.queue中的每个进程P)if(进程P通过Swait中的测试)/*通过检查，即资源够用*/wackup(p);/唤醒进程P；else/*未通过检查，即资源不够用*/进程P继续等待；,用AND信号量解决哲学家进餐问题,semaphorechopstick5=1,1,1,1,1;voidphilosopher(inti)/*哲学家进程*/while(true)Swait(chopsticki,chopstick(i+1)%5);eat();/*进餐*/Ssignal(chopsticki,chopstick(i+1)%5);think();/*思考*/,管程机制,引入的原因：信号灯机制虽然既方便又有效地解决了进程同步问题，但要求访问临界资源的进程自备同步操作wait(s)、signal(s)，使得大量的同步操作分散在各个进程中，给进程的管理带来不便，并会因同步操作使用不当导致死锁。Hoare和Hanson提出了管程的概念把分散在各个进程中的与同一共享资源有关的同步处理从各进程中抽出并集中起来。,一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。管程=数据结构+操作+对数据结构中变量的初始化,3.4管程的定义,管程的结构,条件变量用管程实现进程同步，设置两个同步操作原语wait,signal为了区别等待的原因，引入条件变量condition其形式为varx,y:condition条件变量置于wait和signal之前，表示为x.wait和x.signal例如：由于共享数据被占用而使调用进程等待，该条件变量的形式为notbusy;wait原语应改为notbusy.wait,monitor_name=monitorvariabledeclarationsprocedureP1();procedureP2();procedurePn();initcode,管程的语法,利用管程解决生产者-消费者问题,monitormonitor_PC;charbuffern;intnextin,nextout;intcount;conditionnotfull,notempty;voidput(charx);/*过程*/if(count=n)cwait(notfull);buffernextin=x;nextin=(nextin+1)%n;count=count+1;csignal(notempty);,voidget(charx);/*过程*/if(count=0)cwait(notempty);x=buffernextout;nextout=(nextout+1)%n;count=count-1;csignal(notfull);/*管程体*/nextin=0;nextout=0;count=0;/*变量初始化*/,voidproducer()/*生产者进程*/charx;while(true)produceancharinx;monitor_PC.put(x);,voidconsumer()/*消费者进程*/charx;while(true)monitor_PC.get(x);consumeanx;,利用管程解决生产者-消费者问题,3.5进程通信,信号灯作为进程同步和互斥工具是卓有成效的。但作为通信工具就不够理想。其原因为：效率低一次只传一条消息。通信对用户不透明。因此必须引入高级通信工具，解决进程之间大量的信息传递问题,进程通信的类型,共享存储器系统消息传递系统直接通信方式间接通信方式管道通信,进程通信中的几个问题,通信链路的建立方式显示建立链路隐式建立链路通信方向通信链路连接方式通信链路的容量数据格式同步方式阻塞方式不阻塞方式,消息缓冲,申请消息缓冲区,接收区,接收进程A的消息队列,发送进程1,接收进程A,接收进程B的消息队列,接收区,接收进程B,互斥的原因：对于缓冲区（发送区、接收区）和消息队列，系统内所有进程是共享的。系统内有多个发送进程，也有多个接收进程。例如，多个发送进程并发执行，会引起消息队列的混乱。半同步的原因：消息队列的长度，并不是固定的。多个队列的长度也不尽相同,接收进程A的消息队列,发送进程1,发送进程2,2个发送进程并发执行，可能引起混乱,头指针,尾指针,1SEND(A)（发送消息）原语,发送消息原语被进程用于把消息发送到存放消息的缓冲区。A是原语的参数，表示发送区的地址。其工作原理是：首先调用“寻找目标进程的PCB”的程序查找接收进程的PCB，如果接收进程存在，申请一个存放消息的缓冲区，消息缓冲区为空时，接收此消息的进程因等待此消息的到来而处于阻塞状态，则唤醒此进程，并把消息的内容、发送原语的进程名和消息等，复制到预先申请的存放消息的缓冲区，且将存放消息的缓冲区连接到接收进程的PCB上；如果接收进程不存在，则由系统给出一个“哑”回答；最后控制返回到发送消息的进程继续执行，或转入进程调度程序重新分配处理机。如果消息缓冲区已满，则返回到非同步错误处理程序入口进行特殊处理。如图所示。,有接收进程吗,缓冲区有空吗,申请缓冲区,接收进程在就绪态,唤醒接收进程,发送区内容缓冲区,返回,非同步错误处理,给出哑回答,有,有,否,无,无,是,发送消息过程流图,2READ（A）（读取消息）原语,READ(A)原语用来读取消息。接收进程读取消息之前，在自己的空间中确定一个接收区A。然后使用READ(A)原语。A是接收进程提供的接收区开始地址。如图所示。,图示读取消息,返回本节目录,消息缓冲队列-示意图,消息缓冲队列-数据结构定义,/消息缓冲区定义structmessage_buffercharsender30;/*发送进程标识符*/intsize;/*消息长度*/chartext200;/*消息正文*/structmessage_buffer*next;/指向下一个消息缓冲区的指针/PCB中有关通信的数据项structprocess_controlstructmessage_buffer*mq;/*消息队列队首指针*/semaphoremutex=1;/*消息队列互斥信号量，初值为1*/semaphoresm=0;/*消息队列同步信号量，记录消息的个数.初值为0*/,/发送原语charreceiver30;structmessage_buffera;voidsend(receiver,a)structmessage_bufferi;structprocess_controlj;getbuf(a.size,i);/*发送区a消息的长度申请一缓冲区i*/i.sender=a.sender;i.size=a.size;i.text=a.text;i.next=NULL;getid(PCB_set,receiver,j);/*获得接收进程的进程标识符j*/P(j.mutex);Insert(j.mq,i);/*将消息缓冲区i挂到的消息队列j.mq上*/V(j.mutex);V(j.sm);,消息缓冲队列-发送原语,消息缓冲队列-接收原语,structmessage_bufferb;voidreceive(b)structmessage_bufferi;structprocess_controlj;j=internal_name();/*接收进程的内部标识符*/P(j.sm);P(j.mutex);remove(j.mq,i);/*从消息队列中摘下第一个消息缓冲区*/V(j.mutex);b.sender=i.sender;b.size=i.size;b.text=i.text;,发送进程Send(m)begin申请一个新消息缓冲区P(mutex)消息m新消息缓冲区新消息缓冲区队列V(mutex)V(SM)end,接收进程Receive(n)beginP(SM)P(mutex)从队列中摘下消息n将消息n拷贝到接收区释放内容已取走的缓冲区Vmutex)end,设公用信号量mutex为互斥信号量，初值为1；SM为接收进程的私用信号量，表示等待接收的消息个数，初值为0。,邮箱通信机制,1、设Bufempty为进程Pa的私用信号量，Buffull为Pb的私用信号量2、初始化：Bufempty=n；Buffull=0。,申请消息缓冲区,接收区,大小固定的邮箱,发送进程,接收进程,不用考虑互斥的原因：邮箱是发送进程和接收进程私有的，系统内其它进程不能访问。同步的原因：发送时，要有空格；接收时，要有满格。,Pa：deposit(data)局部变量xP(Bufempty)选择一个空区Buf(x)dataBuf(x)Buf(x)置满标记V(Buffull),发送进程Pa,接收进程Pb,B：remove(data)局部变量xP(Buffull)选择一个空区Buf(x)dataBuf(x)Buf(x)置空标记V(Bufempty),返回本节目录,客户服务器系统通信,常用的通信方式：命名管道套接字远程过程调用,利用UNIX提供的系统调用pipe，可建立一条同步通信管道。其格式为：pipe(fd)intfd2；这里，fd1为写入端，fd0为读出端。,2.示例例1：用C语言编写一个程序，建立一个pipe，同时父进程生成一个子进程，子进程向pipe中写入一字符串，父进程从pipe中读出该字符串。解：程序如下：#includestdio.hmain()intx，fd2；charbuf30，s30；pipe(fd)；/*创建管道*/while