操作系统原理第七章进程同步与进程通信

操作系统原理第七章进程同步与进程通信进程的顺序性进程的顺序性是指进程在顺序处理器上的执行是严格按序的，即按照程序规定的操作顺序，只有在前一个操作结束后才能开始后继操作。当一个进程独占处理器时，它具有两个特性：可再现性进程的并发性每一个进程具有顺序性，但是在多道程序设计系统中，多个进程要竞争，轮流占用处理器。有两个进程A和B，它们各自顺序执行时的操作序列如下：进程A：a1，a2，a3，…，am进程B：b1，b2，b3，…，bm在多道程序设计系统中，处理器可能执行的操作序列a1，b1，a2，b2，a3，b3…a1，a2，b1，a3，b2，b3…进程的并发性在一个进程的工作没有完成之前，另一个进程就可以开始工作，这些进程就称为可同时执行的。或者称它们具有并发性，并且把可同时执行的进程称为并发进程。进程的并发性如果一个进程的执行不影响另一个进程的执行结果，也不依赖一个进程的进展情况，即它们是各自独立的，则称这些进程相互之间是无关的。如果一个进程的执行要依赖其他进程的进展状况，或者可能会影响其他进程的执行结果，则说这些进程是有交互的。与时间有关的错误对于有交互的并发进程来说，并发会破坏“封闭性”和“可再现性”例1：车辆自动计数系统processObserverbeginL1:observealorry;count:=count+1;gotoL1;end;processReporterbeginprintcount;count:=0;end;系统功能：统计每小时的卡车流量观察者进程(Observer)：观察到一辆卡车，计数器+1报告者进程(Reporter)：每隔1小时，将计数值输出，计数器清零例2：航班售票系统processPi(i=1,2,…)beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ak代表某天某次航班的剩余票数；Pi代表售票处理进程；Ri是每个售票进程的私有变量；各个售票处进程的工作如左边代码所示：processP2beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP3beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ri=5假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP2beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP3beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ri=5假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP3beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP2beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ri=5假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP2beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP3beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ri=5假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP3beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP2beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ri=4假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP2beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP3beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ak=4假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP2beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP3beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ri=4假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP3beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP2beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;Ak=4假设某时刻Ak为5，A、B两个人同时在2号3号窗口买票processP3beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;processP2beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;假设某时刻Ak为1，两个窗口同时卖票，可能出现什么情况？与时间有关的错误由于进程交替修改了共享变量造成结果可能不正确。造成不正确的因素与进程占据处理器的时间、执行速度以及外界的影响（卡车），这些因素都与时间有关，所以称为与时间有关的错误。临界区有交互的并发进程执行时出现与时间有关的错误，其根本原因是对共享资源（变量）的使用不受限，为了使并发进程能正确地执行，必须对共享变量的使用加以限制。processObserverbeginL1:observealorry;count:=count+1;gotoL1;end;临界区processReporterbeginprintcount;count:=0;end;把并发进程中与共享变量有关的程序段称为临界区。涉及相同共享变量的临界区称为相关临界区。临界区processPi(i=1,2…)beginRi:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=Ri输出一张票；end;else输出”票已售完“end;如果能保证一个进程在临界区执行时，不让另一个进程进入相关的临界区执行，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。临界区当无进程在临界区时，若有进程要进入，则允许一个进程进入临界区当有进程在临界区执行时，其他试图进入临界区的进程必须等待当有一个进程离开临界区，若有等待进入临界区的进程，则允许一个进程进入它的临界区信号量机制（Semaphores）1965年，荷兰的E.W.Dijkstra(狄克斯特拉)提出了信号量同步机制。用于进程同步广泛应用于存在临界资源和临界区控制的场合信号量的概念信号量S是一个整数S≥0可供并发进程使用的资源实体数<0绝对值表示等待使用资源的进程数PV操作对信号量的操作只能由P、V操作来进行，即：信号量数值的改变只能由P、V操作完成PV操作由P操作和V操作组成，也称P操作原语和V操作原语。P操作P(S):将信号量S减1，若结果小于0，则把调用P(S)的进程设置成等待信号量S的状态ProcedureP(VarS:Semaphore);beginS:=S-1;ifS<0thenW(s)end;{P}W(s)表示把调用P(S)的进程设置成等待信号量S的状态V(S):将信号量S加1，若不大于0(小于等于0)，则释放一个等待信号量S的进程。ProcedureV(VarS:Semaphore);beginS:=S+1;ifS<=0thenR(s)end;{V}V操作R(s)表示释放一个等待信号量S的进程进程的互斥进程的互斥是指有若干进程都要使用某一共享资源时，任何时刻最多只允许一个进程去使用该资源，其他要使用的进程必须等待，直到该资源的占用者释放了该资源。beginS:semaphore;S:=1;cobegin:processPi（i=1,2,3…）beginP(S);{临界区Ci（访问共享资源的代码）}V(S);end;coend:end;假设有n个进程P1，P2，P3..Pn共享某一资源,任意时刻只允许一个进程访问该资源，它们各自的临界区分别为C1，C2…Cn。begincount:integer;count:=0;S:semaphore;S:=1;cobegin:processObserverbeginL1:observealorry;P(S);count:=count+1;V(S);gotoL1;end;processReporterbeginP(S);printcount;count:=0;V(S);end;coend:end;beginS:semaphore;S:=1;cobegin:processPi(i=1,2,3…)beginP(S);Ri:=Ak;ifRi>=1thenbeginRi:=Ri-1;Ak=RiV(S);输出一张票；end;elsebeginV(S);输出”票已售完“end;coend:end;读者/写者问题计算机中，把可供多个进程使用的文件称为共享文件。想读文件的进程称为读进程，写文件的进程称为写进程。不允许多个进程同时使用共享文件beginS:semaphore;S:=1;cobeginprocessReaderi(i=1,2,3…)beginP(S);readfileF;V(S);end;processWriterj(j=1,2,3…)beginP(S);writefileF;V(S);end;coend:end;P22612有4个并发执行的进程A，B，C，D,它们在执行时都要读共享文件F。限定：不允许进程A和进程B同时读文件F，不允许进程C和进程D同时读文件F。写出用PV操作管理时四个进程的程序。beginS1,S2:semaphore;S1:=1;S2:=1;cobeginprocessAbeginP(S1);readfileF;V(S1);end;processBbeginP(S1);readfileF;V(S1);end;coend:end;processDbeginP(S2);readfileF;V(S2);end;

processCbeginP(S2);readfileF;V(S2);end;某系统允许最多10个进程同时读文件F，当同时读文件F的进程不满10个时，欲读该文件的其他进程可立即读，当已有10个进程在读文件F时其他欲读文件F的进程必须等待，直至有进程读完后退出方可去读,写出进程并发执行时的程序。beginS：semaphore;S:=10;cobeginprocessReaderi(i=1,2,3…)beginP(S);readfileF;V(s);end;coend:end;允许多个进程同时使用共享文件要求：(1)多个进程可以同时读文件F(2)任何一个进程在对文件F进行写时，不允许其他进程读或写(3)有进程在读文件F时，不允许任何进程去写PV操作的实现思路：processWriteri(i=1,2,3)beginP(S);writefileF;V(S);end;

processReaderi(i=1,2,3..)beginif是第一个读进程thenP(S);readfileF;if是最后一个完成的读进程thenV(S);end;

beginS:semaphore;S=1;rc:integer;rc=0;cobegin:processReaderi(i=1,2,3…)beginrc:=rc+1;ifrc=1thenP(S);readfileF;rc:=rc-1;ifrc=0thenV(S)end;coend:end;

processwriterj(j=1,2…)beginP(S);writefileF;V(S);end;beginS，mutex:semaphore;S:=1;mutex:=1;rc:integer;rc:=0;cobegin:processReaderi(i=1,2,3…)beginP(mutex);rc:=rc+1;ifrc=1thenP(S);V(mutex);readfileF;P(mutex);rc:=rc-1;ifrc=0thenV(S)V(mutex);end;coend:End;processwriterj(j=1,2,3…)beginP(S);writefileF;V(S);end;进程的同步记录进程B进程A缓冲区存取加工假设缓冲区容量为1一个生产者进程，将数据存在缓冲区中；一个消费者进程，从缓冲区中取数据，要求两者同步（即缓冲区空才可以存，缓冲区满才可以取）用PV操作实现进程的同步beginSP，SG:semaphore;SP:=1;SG:=0;Buffer：integer;cobegin:

processproducerbeginL1:produceaproductP(SP);buffer:=product;V(SG);gotoL1;end;coend:End;processconsumerbeginL2:P(SG);takeaproduct;V(SP);Consume;gotoL2;end;桌上只有一个盘子，一个盘子一次只能放一个苹果，爸爸向盘子里放苹果，儿子从盘子里拿苹果，用PV操作实现同步。beginS1，S2:semaphore;S1:=1;S2:=0;cobegin:process爸爸beginL1:P(S1);放苹果V(S2);gotoL1;end;process儿子beginL2:P(S2);拿苹果V(S1);gotoL2;end;coend:end;用PV操作实现售票员和司机的同步,假设初始状态为车在始发站，要求售票员进程先开始执行process售票员开车门关车门售票process司机启动车辆

正常行车

到站停车beginS1，S2:semaphore;//S1能否开门，S2能否开车S1:=1;S2:=0;cobegin:process司机beginL1:P(S2);启动车辆正常行驶到站停车V(S1);gotoL1;end;coend:End;process售票员beginL2:P(S1);开门关门V(S2);售票gotoL2;end;P2257有三个并发进程R、M、P，它们共享一个只能存放一个记录的缓冲区。R负责从输入设备读信息，每次读一个记录，存在缓冲区中。M对缓冲区中的记录加工，P把加工后的记录打印输出。记录经加工并输出后，缓冲区才能存放下一个记录。写出它们并发执行时的程序。假设有三个进程R，W1，W2共享一个缓冲区B，又设B中每次只能放一个数。要求：缓冲区中无数时，R可以从设备读数存到缓冲若存到缓冲中的数是奇数，允许W1将其取出打印若存到缓冲中的数是偶数，允许W2将其取出打印R必须等缓冲区空才能放，W1，W2不能从空缓冲区中取数。beginSP，SG1,SG2:semaphore;SP:=1;SG1:=0;SG2:=0;Buffer：integer;cobegin:

processRbeginL1:读入一个数numberP(SP);buffer:=number;ifbuffermod2<>0thenV(SG1)elsethenV(SG2)gotoL1;end;coend:end;processW1beginL2:P(SG1);y:=buffer;V(SP);printy;gotoL2;end;processW2beginL3:P(SG2);z:=buffer;V(SP);printz;gotoL3;end;多缓冲区的进程同步记录BA缓冲区进程存进程取加工假设缓冲区容量为n，或者假设有n个缓冲区。一个生产者进程，一个消费者进程，要求消费者进程的处理顺序与生产者进程的输入的完全一样beginbuffer:array[0,n-1]ofintegerk,t:integer;k:=0;t:=0;SP，SG:semaphore;SP:=n;SG:=0;cobegin:

processproducerbeginL1:produceaproductP(SP);buffer[k]:=product;k=(k+1)modn;V(SG);gotoL1;end;coend:end;processconsumerbeginL2:P(SG);takeaproductfrombuffer[t];t:=(t+1)modn;V(SP);Consume;gotoL2;end;同步与互斥的混合问题某工厂有一个可以存放设备的仓库，总共可以存放8台设备。生产部门生产的每一台设备都必须入库。销售部门可以从仓库中提出设备供应客户。设备出/入库需要借助运输工具，现只有一套运输工具，每次只能运一台设备请设计一套能够协调工作的自动调度系统。beginS，SP,SG:semaphore;S:=1;SP:=8;SG:=0

cobegin:

process生产beginL1:生产一台设备P(SP);P(S);运送到仓库；V(S)V(SG);gotoL1;end;coend:end;process销售beginL1:P(SG);P(S);从仓库运出；V(S)V(SP);gotoL1;end;m个生产者和r个消费者怎样共享容量为n的缓冲区，每个生产者都要把生产的物品存入缓冲区，每个消费者要从缓冲区中取物品beginbuffer:array[0,n-1]ofintegerk,t:integer;k:=0;t:=0;SP，SG,mutex1，mutex2:semaphore;SP:=n;SG:=0;mutex1:=1，mutex2:=1；cobegin:

processproduceri(i=1,2..)beginL1:produceaproductP(SP);P(mutex1)buffer[k]:=product;k=(k+1)modn;V(mutex1)V(SG);gotoL1;end;coend:end;processconsumeri（i=1,2..）beginL2:P(SG);P(mutex2);takeaproductfrombuffer[t];t:=(t+1)modn;V(mutex2)V(SP);Consume;gotoL2;end;桌上放一个盘子，每次只能放一个水果，爸爸像盘子里放苹果，妈妈向盘子里放橘子，女儿专吃苹果,儿子专吃橘子。盘子空的时候爸爸或妈妈才能向盘子里面放一个水果，仅当盘子里有自己需要的水果时才可取一个水果。把爸爸、妈妈、儿子、女儿看做四个进程，用PV操作进行管理，使这四个进程能正确地并发执行。beginmutex,SA，SO:semaphore;mutex:=1;SA:=0;SO:=0;cobegin:process爸爸beginL1:P(mutex);放苹果V(SA);gotoL1;end;process妈妈beginL2:P(mutex);放橘子V(SO);gotoL2;end;coend:end;process儿子beginL4:P(SO);拿橘子V(mutex);gotoL4;end;process女儿beginL3:P(SA);拿苹果V(mutex);gotoL3;end;P2258如果盘子的容量改为2，且任何时刻只允许爸爸、妈妈、女儿、儿子中的一个进程去访问盘子（放或者取）。beginmutex1,mutex2,SA，SO:semaphore;mutex1:=2;mutex2:=1;SA:=0;SO:=0;cobegin:process爸爸beginL1:P(mutex1);//盘子P(mutex2);//伸手放苹果V(mutex2);V(SA);gotoL1;end;process妈妈beginL2:P(mutex1);//盘子P(mutex2);//伸手放橘子V(mutex2);V(SO);gotoL2;end;coend:end;process女儿beginL3:P(SA);P(mutex2);//伸手拿苹果V(mutex2)V(mutex1);gotoL3;end;process儿子beginL4:P(SO);P(mutex2);//伸手拿橘子V(mutex2)V(mutex1);gotoL4;end;有三个进程A1、A2、A3，它们共享两个缓冲区B1和B2。缓冲区B1中可以存放n件产品，缓冲区B2中可以存放m件产品。进程A1每次生产一件产品，并把产品存入缓冲区B1。进程A2每次生产一件产品，并把产品存入缓冲区B2。进程A3每次从缓冲区B2中取一件产品区消费。为了防止把产品存入已满的缓冲，或者从空缓冲中取产品，或重复取一产品，用PV操作实现它们的相互制约关系。进程A1缓冲区B1n缓冲区B2m进程A2进程A3消费生产BeginB1，B2:array[0,n-1]ofintegerk1,k2，t1，t2:integer;k1:=0;k1:=0;t1:=0;SP，SG:semaphore;SP=n;SG=0;cobegin:

processproducerbeginL1:produceaproductP(SP);buffer[k]:=product;k=(k+1)modn;V(SG);gotoL1;end;coend:End;进程通信并发进程间可以通过PV操作交换信息实现进程的互斥和同步，因此可以把PV操作看做进程间的一种通信方式，但这种通信只交换了少量的信息。如果进程间要交换大量信息，这种大量信息的传递要有专门的通信机制来实现，通过专门的通信机制实现进程间大量信息的通信方式称为进程通信。通信机制采用高级通信方式时，进程间用信件来交换信息。信件：信件内容包括发送者名、信息(信息存放的地址和长度)、等/不等回信，回信存放地址。通信方式：信件的传递是由通信原语完成的，最基本的原语是两条：发送(send)原语和接收(receive)原语。通信方式直接通信方式这种通信方式总是固定在一对进程之间进行send(B,M)把信件M发送给BABreceive(A,X)接受来自进程A的信件存入X中通信方式间接通信这种通信方式总是信箱为媒体来实现通信的，接受进程设立一个信箱，任何要向该进程发信的进程总是把信件发送到该进程的信箱里AB信箱Nsend(N,M)把信件M送入信箱N中receive(N,X)从信箱N中取出一封信存入X取发间接通信的实现间接通信指的是进程之间利用信箱来交换信息。通信时要遵循的规则：信箱满时，把发送信件的进程置成”等信箱“，直到信箱有空才被释放若信箱无信，则把接收信件的进程置成”等信件“，直到信箱有信件才释放。可存信件数已有信件数可存信件的指针信件1信件2取信件信箱说明信箱的数据结构定义TYPEbox=recordsize:0..n;信箱大小count:0..n;现有信件数letter:array[1..n]ofmessage;信件S1,S2:semaphore;end;send原语过程proceduresend(varB:box;M:message)vari:integer;beginifB.count=B.sizethenW(B.S1)如果信箱满，等信箱elsebegini:=B.count+1;确定可存放信件的位置B.letter[i]=M;信件存放到信箱指定位置B.count:=i;信箱的信件数+1R(B.S2);释放等信件者end;end;{send}receive原语过程procedurereceive(varB:box;M:message)vari:integer;beginifB.count=0thenW(B.S2)如果信箱无信，等信件elsebeginX:=B.letter[1];总是取第一封信B.count:=B.count-1;信件数-1ifB.count<>0thenfori=1toB.countdoB.letter[i]:=B.letter[i+1];所有信件上移R(B.S1);释放一个等信箱的进程end;end;{receive}进程通信示意组织信件Msend(B,M)..receive(A,Y)receive(B,X)处理信件M组织回信Nsend(A,N)信件M信件NB进程信箱A进程信箱A进程B进程磁盘管理欲访问磁盘的进程begin…{组织信件M};send{B,M};…end;磁盘管理进程L1:receive(B,X){按信件要求组织通道程序};{通道程序首址存入CAW};{启动磁盘};{等待磁盘传输结束};{组织回信M};send{name,M};gotoL1；end;用进程通信实现进程同步用直接通信方式解决生产者/消费者问题cobegin:processproducerbeginL1:生产物品组织信件Msend（consumer,M）gotoL1;end;cobegin:proce