《计算机操作系统》课件

湘潭大学第3章

进程的同步与通信湘潭大学第3章

进程的同步与通信进程的异步性导致程序执行的不可再现性，给系统造成混乱。进程同步的主要任务，是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。进程的异步性导致程序执行的不可再现性，给系统造成混乱。进程同3.1进程同步的基本概念进程间的相互制约关系在多道程序环境下，系统中可能有着许多进程，这些进程之间可能存在以下两种关系。间接相互制约关的系：多个进程之间彼此无关，并不知道其他进程的存在，但这些进程既然同处于一个系统中，也就必然存在资源共享的关系，如共享CPU、I/O设备等。此时进程同步的主要任务是保证诸进程能互斥地访问临界资源。这样，系统中的资源应由系统统一管理，不允许用户进程直接使用。直接相互制约的关系：在某些进程间还存在相互合作关系，此时进程同步的主要任务是保证诸进程在执行次序上的协调，不会出现与时间有关的差错。3.1进程同步的基本概念进程间的相互制约关系临界资源临界资源，也称独占资源，是在一段时间内只允许一个进程访问的资源。对临界资源，进程间应采取互斥方式共享。例子：Producer-Consumer问题描述了一个生产者进程（PP）生产消息，并提供给一个消费者（CP）进程消费。为使PP和CP能并发执行，设置一个有n个缓冲区的缓冲池，PP将其生产的消息放入一缓冲区中，CP可从一缓冲区取得消息。尽管所有PP和CP都以异步方式运行，但它们之间必须保持同步，即不允许CP到一空缓冲区取消息，也不允许PP向一满的缓冲区投放消息。临界资源012354n-2n-1inoutcounter计数器输入指针输出指针012354n-2n-1inoutcounter计数器输入指PP和CP共享的变量：Varn,integer;Typeitem=…;Varbuffer:array[0,1…n-1]ofitem;in,out:0,1…n-1;counter:0,1…n;PP和CP共享的变量：PP:repeat……produceaniteminnextp;……whilecounter=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;untilfalse;CP:repeatwhilecounter=0dono-opnextc:=buffer[out];out:=(out+1)modn;counter:=counter-1;consumetheiteminnextcuntilfalse;PP:repeatCP:repeat

以上的生产者程序和消费者程序，二者在顺序执行时结果是正确的。但若并发执行就会出错，原因是这二个进程共享变量counter,生产者对它加1，消费者对它减1，这两个操作用机器语言实现时的形式可为：设counter的当前值是5若按下述方式运行register1:=counter;（register1:=5）register1:=registe1+1（register1:=6)register2:=counter;(register2:=5)register2:=registe2-1;(register2:=4)counter:=register1(counter=6)counter:=register2;(counter=4)Producer:register1:=counter;register1:=registe1+1;counter:=register1;Consumer:register2:=counter;register2:=registe2-1;counter:=register2;(counter=5)counter正确的答案应是5，而现在是4故应将counter作为临界资源处理以上的生产者程序和消费者程序，二者在顺序执行时结果是正确的临界区临界区的定义定义：在每个进程中访问临界资源的那段代码称为临界区（criticalsection).若能保证诸进程互斥地进入自己的临界区，便可实现它们对临界资源的互斥访问。为此，进程在进入临界区之前应检查欲访问的临界资源，若临界资源未被访问，便可进入临界区，否则不能进入。因此须在临界区前设置一段称为进入区(entrysection)的代码段；同样在其后加上一段称为退出区的代码段(exitsection)。进程中除进入区、临界区、及退出区之外的其他代码段称为剩余区。一个访问临界资源的循环进程描述如下：

RepeatEntrysectionCriticalsection;ExitsectionRemaindersectionUntilfalse临界区一个访问临界资源的同步机制应遵循的准则空闲让进：当无进程处于临界区时，表明临界资源处于空闲状态。可允许一请求进入临界区的进程立即进入自己的临界区。忙则等待：当已有进程进入到临界区时，表明临界资源正被访问，故其他试图进入临界区的进程必须等待。有限等待：对要求访问临界资源的进程，应保证该进程能在有效时间内进入自己的临界区，以免陷入“死等状态”。让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。同步机制应遵循的准则硬件同步机制目前许多计算机已提供了一些特殊的硬件指令，允许对一个字中的内容进行检测和修正，或是对两个字中的内容进行交换等，可利用这些特殊的指令来解决临界区问题。实际上，在对临界区进行管理时，可以将标志看作一个锁，“锁开”进入，“锁关”等待，初始时锁是打开的。每个要进入临界区的进程，必须先对锁进行测试，当锁未开时，则必须等待，直至锁被打开。反之，当锁是打开的时，则应立即将其锁上，以阻止其他进程进入临界区。显然，为防止多个进程同时测试到锁开的情况，测试和关键操作必须是连续的，不允许分开进行。硬件同步机制关中断关中断是实现互斥的最简单方法之一。在进入锁测试之前，关闭中断，直到完成锁测试并上锁之后才能打开中断。这样，进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度，也就不会发生进程或线程切换。关中断的缺点：[1]滥用关中断权力可能导致严重后果；[2]关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；[3]不适用于多处理器系统。关中断利用test-and-set指令实现互斥这是借助“测试并建立”硬件指令TS来实现互斥的方法，该指令的一般性描述为：FunctionTS(varlock:boolean):booleanBeginTS:=lock;Lock:=true;EndTS指令可看作一个函数过程，其执行过程是不可分的，即是一条原语。其中，lock有两种状态：当lock=false时，表示该资源空闲；当lock=true时，表示该资源正在被使用。利用test-and-set指令实现互斥用TS指令管理临界区时，为每个临界资源设置一个布尔变量lock，用lock代表该资源的状态，可以看成一把锁，初值为false,表示该临界资源空闲，进程进入临界区之前，首先用TS指令测试lock，如果其值为false，则表示没有进程在临界区内，可以进入，并将lock赋值为true,这等效于关闭了临界资源，使任何进程都不能进入临界区，否则必须循环测试，直到TS(s)为false。利用TS指令实现互斥的循环进程结构可描述为：用TS指令管理临界区时，为每个临界资源设置一个布尔变量locReapt…WhileTS(lock)doskip;Criticalsection;Lock:=false;Remaindersection;UntilfalseReapt利用Swap指令实现进程互斥Swap称为对换指令，用于交换两个字的内容，其处理过程描述为：ProcedureSwap(a,b:boolean)Vartemp:boolean;Begintemp:=a;a:=b;b:=tempend利用Swap指令实现进程互斥利用Swap实现互斥的方法是为每个临界资源设置一个全局布尔变量lock，其初值为false，在每个进程中在利用一个局部布尔变量key，利用Swap指令实现进程互斥的循环进程可描述为：Repeatkey:=true;repeatSwap(lock,key);untilkey=false;临界区操作；Lock:=false;…Untilfalse;利用Swap实现互斥的方法是为每个临界资源设置一个全局布尔变利用硬件指令能有效地实现进程互斥，但当临界资源忙碌时，其他访问进程必须不断地进行测试，处于一种“忙等”状态，不符合“让权等待”的原则，造成处理机时间浪费，同时也很难将它们用于复杂的进程同步问题。利用硬件指令能有效地实现进程互斥，但当临界资源忙碌时，其他访3.2信号量机制信号量机制是一种有效的进程同步工具。只能用于对一个临界资源实现互斥访问的信号量机制：整型信号量记录型信号量能同时对多个临界资源实现互斥访问的信号量机制：“AND”信号量信号量集3.2信号量机制信号量机制是一种有效的进程同步工具。3.2.1整型信号量和记录型信号量整型信号量整型信号量定义为一个用于表示资源数目的整型量S，除初始化外，仅能通过两个标准的原子操作wait(s)和signal(s)来访问，这两个操作分别称为P、V操作，可描述为：

wait(s):whiles≦0dono-ops:=s-1;signal(s):s:=s+1;wait(s)和signal(s)是原子操作的含义：一是当一个进程在修改某信号量时，没有其他进程可同时对该信息量进行修改；二是wait操作中，对s值的测试和做s:=s-1操作时，都不可中断。3.2.1整型信号量和记录型信号量整型信号量记录型信号量

注意到整型信号量机制的操作：

wait(s):whiles≦0dono-ops:=s-1并未遵循“让权等待”的准则。但记录型信号量机制则不存在“忙等”问题,但采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况，为此在信号量机制中采用记录型数据结构来构造记录型信号量，可描述为：

typesemaphore=recordvalue:integer;//资源数目

L:listofprocess;//链接所有等待进程的

end进程链表记录型信号量22相应地，wait(s)和signal(s)操作可描述为：Procedurewait(S)varS:semaphore;beginS.value:=S.value-1;ifS.value<0thenblock(S.L);endProceduresignal(S)varS:semaphorebeginS.value:=S.value+1;ifS.value≦0thenwakeup(S.L);end记录型信号量初值表示系统中某类资源的数目,减1操作表示进程请求一个单位的资源.若小于0，表示资源已分配完毕,该进程调用阻塞原语,进行自我阻塞，放弃处理机，并插入到信号链表S.L中。此时S.value的绝对值表示在该信号链表中已阻塞的进程的数目。表示执行的进程释放一个单位的资源。若不大于0。表示在该信号链表中，仍有等待该资源的进程，故应调用唤醒原语，将S.L链表中的第一个等待进程唤醒。22相应地，wait(s)和signal(s)操作可描述为：3.2.2AND型信号量和信号量集AND型信号量集整型和记录型信号量机制是针对进程间共享一个临界资源而言的。多个进程共享多个临界资源时则要采取另外的信号量机制。设A和B为进程，都要求访问共享数据D和E，这时D和E为临界资源。为D、E设置用于互斥的信号量Dmutex、Emutex，令初值为1，这时A和B有操作：

ProcessA:processB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若A和B按下述次序执行wait操作:(Dmutex,Emutex初值为1）processA:wait(Dmutex);//Dmutex=0processB:wait(Emutex);//Emutex=0processA:wait(Emutex);//Emutex=-1,A阻塞processB:wait(Dmutex);//Dmutex=-1,B阻塞

此时A，B进入死锁状态。显然，进程要求的共享资源越多，死锁的可能性越大。3.2.2AND型信号量和信号量集AND型信号量集若A和AND同步机制的基本思想是，将进程在整个运行过程中所需要的所有临界资源，一次性地全部分配给进程，待该进程用完后再一起释放，即对若干个临界资源的分配，采取原子操作方式要么全部分配到进程，要么一个也不分配，这样可避免死锁的情况发生。为此，在wait操作中增加一个“AND”条件，故称为AND同步，或称为同时wait操作，即SWait（SimultaneousWait），其定义为：AND同步机制的基本思想是，将进程在整个运行过程中所需要的所Swait(S1,S2,…,Sn)ifS1≥1and…andSn≥1thenfori:=1tondoSi:=Si-1;endforelse……endifSsignal(S1,S2,…Sn)fori:=1tondoSi:=Si+1;…;endfor;Swait(S1,S2,…,Sn)信号量集机制在记录型信号量机制中，wait(s)或signal(s)操作仅能对信号量施以增1或减1操作，既每次只能获得或释放一个单位的临界资源。当一次需N个某类临界资源时，便需要做N次wait操作，这是低效的。另外有时当资源数量低于某一下限值时，便不分配资源给请求进程。因此，在每次分配之前，都必须测试该资源的数量是否大于测试值t。基于这二点可对AND信号量机制进行扩充，形成一般化的“信号量集”机制。SWait操作可描述为：信号量集机制Swait(S1,t1,d1,…,Sn,tn,dn)

ifS1≧t1and…andSn≧tnthen

fori:=1tondoSi:=Si-di;endfor

elsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi<tiandsetitsprogramcountertothebeginningoftheSwaitoperation.endifSsignal(S1,t1,d1,…,Sn,tn,dn)fori:=1tondoSi:=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.endfor关于一般“信号量集”的几种特殊情况：（1）Swait（S，d，d）。此时在信号量集中只有一个信号量，但允许每次申请d个资源，当现有资源数少于d时不予分配。（2）Swait（S，1，1）。此时的信号量集已蜕化为一般记录型信号量（S>1）或互斥信号量（S=1）。（3）Swait（S，1，0）。当S≧1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。是一种很特殊且很有用的信号量。

Si:某类资源数量,ti:下限测试值,di:申请的资源数.Swait(S1,t1,d1,…,Sn,tn,dn)关于一般利用信号量实现进程互斥利用信号量实现进程互斥3.2.3信号量的应用利用信号量实现进程互斥：varmutex:semaghore:=1;beginparbeginprocess1:beginrepeat

wait(mutex);

criticalsection

signal(mutex);

remaindersection

untilfalse;endprocess2:beginrepeat

wait(mutex);

criticalsectionsignal(mutex);

remaintersectionuntilfalseendparendwait(mutex):whilemutex≦0dono-opmutex:=mutex-1;signal(mutex):mutex:=mutex+1;wait(mutex):whilemutex≦0dono-opmutex:=mutex-1;signal(mutex):mutex:=mutex+1;为使多个进程能互斥地访问某临界资源，而为该资源设置的一个互斥信号量。3.2.3信号量的应用利用信号量实现进程互斥：proces利用信号量实现前趋关系vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);end;beginwait(c);S4;signal(f);end;beginwait(d);S5;signal(g);end;beginwait(e);wait(f);wait(g);S6;end;parendendS1S2S3S5S4S6abcdefg利用信号量实现前趋关系S1S2S3S5S4S6abcdefg3.3管程机制管程的引入引入信号量机制的目的是为了消除与时间有关的错误，在信号量机制中每个要访问临界资源的进程都必须自备同步操作wait(s),signal(s)，就使大量的同步操作分散在各个进程中，故容易因同步操作的使用不当而同样会造成与时间有关的错误。例如：错误1：颠倒wait(s)和signal(s)使用顺序。错误2：程序中的signal(s)被误写为wait(s)。错误3：程序中遗漏wait(s)或signal(s)。基于上述情况，70年代提出了管程的概念。3.3管程机制管程的引入3.3.1管程的定义系统中的各种软硬件资源，均可用数据结构加以抽象描述，即用少量信息和对该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。当共享资源用共享数据结构来表示时，资源管理程序可用对该数据结构进行操作的一组过程来表示。把这样一组相关的数据结构和过程一并称为管程。3.3.1管程的定义系统中的各种软硬件资源，均可用数据结构定义（Hansan）：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。从定义知管程由四部分组成:(1)管程的名称(2)局部于管程的共享数据结构说明；(3)对该数据结构进行操作的一组过程；(4)对局部于管程的共享数据设置初始值的语句。管程有一个重要的特性，即任一时刻管程中只能有一个活跃进程，从而能有效地完成互斥。管程的语法为：定义（Hansan）：一个管程定义了一个数据结构和能为并发进进入队列初始化代码一组操作过程条件队列管程示意图进入队列初始化代码一组操作过程条件队列管程示意图typemonitor-name=monitorvariabledeclarations

procedureentryP1(…);begin…end;…procedureentryPn(…);begin…end;begininitializationcodeend管程命名共享变量说明一组过程初始化变量管程命名共享变量说明一组过程初始化变量3.3.2条件变量利用管程实现进程同步时须设置两个同步操作原语wait和signal。进程通过管程请求临界资源未果时，管程调用wait原语使该进程等待，并将其排在等待队列，仅当另一进程访问完并释放之后，管程又调用signal原语，唤醒等待队列中的队首进程。为区别等待的原因，引入条件变量，且管程予以说明，其形式为：varx，y：condition。变量置于wait和signal之前，即x.wait和x.signal。x.signal的作用是重新启动一个被阻塞进程，若无进程被阻塞，则x.signal不产生任何后果，与信号量机制中的signal操作不同。因为后者总是要执行s:=s+1，总会改变信号量的状态。3.3.2条件变量利用管程实现进程同步时须设置两个同步操作3.3.3利用管程解决生产者—消费者问题解决该问题首先是为它们建立一个管程，命名为PC。其中包含两个过程：（1）put(item)过程：生产者利用该过程将生产的消息投放到缓冲池，用整型变量count表示缓冲池中已有的消息数，当count≧n时，表示缓冲池已满，生产者需等待。（2）get(item)过程：消费者利用该过程从缓冲池中取得一个消息，当count≦0时，表示缓冲池已无可用消息，消费者应等待。PC管程描述如下：3.3.3利用管程解决生产者—消费者问题解决该问题首先是为TypePC=monitorvarin,out,count:integer;buffer:array[0,.,n-1]ofitem;notfull,notempty:condition;procedureentryput(x)beginifcount≧nthennotfull.wait;buffer(in):=x;in:=(in+1)modn;count:=count+1;ifnotempty.queuethennotempty.signal;end

procedureentryget(x)beginifcount≦0thennotempty.wait;x:=buffer(out);out:=(out+1)modn;count:=count-1;ifnotfull.queuethennotfull.signal;endbeginin:=out:=0;count:=0;end因池中无空缓冲区而等待，此时调用管程中该过程的进程排入等待空缓冲区队列。若等待满缓冲区队列中有进程，则唤醒对首进程。若无则什么都不做。因池中无满缓冲区而等待，此时调用管程中该过程的进程排入等待满缓冲区队列。在利用管程解决生产者—消费者问题时，其中的生产者和消费者可描述为：Producer:beginrepeatproduceaniteminnextp;PC.put(nextp);untilfalse；endConsumer:beginrepeatPC.get(nextc);consumetheiteminnextc;untilfalse;endTypePC=monitorprocedureentr3.4经典进程同步问题3.4.1生产者—消费者问题

TheProceducer-ConsumerProblem是相互合作进程关系的一种抽象，有很大的代表性和实用价值。一、利用记录型信号量解决生产者—消费者问题：设在生产者和消费者之间的共用缓冲池中有n个缓冲区，利用互斥信号量mutex使诸进程实现对缓冲池的互斥使用；利用资源信号量empty和full分别表示池中空缓冲区和满缓冲区数量。此问题可描述如下：3.4经典进程同步问题3.4.1生产者—消费者问题

varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…n-1]ofitem;in,out:integer:=0,0;beginparbeginproducer:beginrepeat…produceaniteminnextp;…

wait(empty);

wait(mutex);buffer(in):=nextp;in:=(in+1)moden;

signal(mutex);

signal(full);untilfalse;end

consumer:beginrepeat

wait(full);

wait(mutex);nextc:=buffer(out);out:=(out+1)modn;

signal(mutex);

signal(empty);consumetheiteminnextc;untilfalse;endparend;end应注意的问题：1、每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对出现。2、对资源信号量empty和full的Wait和signal操作，须成对出现，但分别处于不同的程序中。3、应先执行对资源信号量的Wait操作，然后再执行对互斥信号量的wait操作，顺序不能颠倒。否则可能引起死锁。Procedurewait(s)vars:semaphore;beginS.value:=S.value-1;ifS.value<0thenblock(S.L);endProceduresignal(s)vars:semaphorebeginS.value:=S.value+1;ifS.value≦0thenwakeup(S.L);end

varmutex,empty,full:s3.4.2哲学家进餐问题一、利用记录型信号量解决哲学家进餐问题varchopstick:array[0,…,4]ofsemaphore;

第i个哲学家的活动可描述为：repeatwait(chopstick[i]);wait(chopstick[(i=+1)mod5]);…eat;…signal(chopstick[i]);signal(chopstick[(i=+1)mod5]);

…thinkuntilfalse

该解法可保证不会有两个相邻的哲学家同时进餐，但可能引起死锁。对于死锁的问题有几种解决方法。见P78。04321043213.4.2哲学家进餐问题一、利用记录型信号量解决哲学家进餐利用记录型信号量解决哲学家进餐问题varchopstick:array[0,…,4]ofsemaphore;//初始值为1

第i个哲学家的活动可描述为：repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);…eat;…signal(chopstick[i]);signal(chopstick[(i+1)mod5]);

…thinkuntilfalse该解法可保证不会有两个相邻的哲学家同时进餐，但可能引起死锁。对于死锁的问题有几种解决方法。利用记录型信号量解决哲学家进餐问题…例如：5个哲学家同时饥饿而各自拿起左边的筷子，当他们试图去拿右边的筷子时，因无筷子可拿而无限期地等待。从而死锁。解决死锁的方法有几种：至多只允许4个哲学家同时进餐，以保证有1个哲学家能够进餐。仅当哲学家左右两边的筷子都可用时，才允许拿起筷子进餐。规定奇数号哲学家先拿他左边的筷子，然后再拿右边的筷子；偶数号哲学家先拿他右边的筷子，然后再拿左边的筷子。例如：5个哲学家同时饥饿而各自拿起左边的筷子，当他们试图去拿利用管程解决哲学家进餐问题哲学家可以处于进餐、饥饿和思考这三种状态之一。相应地引入数据结构：

varstate:array[0…4]of(think,hungry,eat)为每一位哲学家设置一个条件变量self(i)，每当哲学家饥饿，但又得不到进餐所需的筷子时，他可以执行self(i).wait操作，来推迟进餐，条件变量可描述为：

varself:array[0…4]ofcondition利用管程解决哲学家进餐问题在管程中还设置三个过程：（1）pickup(i:0…4)过程。在哲学家进程中，可利用该过程去进餐。某哲学家饥饿时，且其左、右两边的哲学家都未进餐，则他可以进餐。但只要其左右两位有一位在进餐，他便不能进餐，此时执行self(i).wait操作来推迟自己的进餐。在管程中还设置三个过程：（2）putdown(i:0…4)过程。哲学家进餐毕，他去看其左右两边的哲学家，若他们都饥饿且他左右两边的哲学家都未用餐时，便可让他们进餐。（3）test(i:0…4)。该过程为测试过程，用它去测试哲学家是否已具备用餐条件，即state[k+4mod5]≠eatandstate[k]=hungryandstate[k+1mod5]≠eat条件是否为真。若为真，方允许哲学家进餐。该过程被pickup和putdown两过程所调用。（2）putdown(i:0…4)过程。哲学家进餐毕，他去看TypeDP=monitorvarstate:array[0…4]of(think,hungry,eat);varself:array[0…4]ofcondition;procedureentrypickup(i:0…4);beginstate[i]:=hungry;test(i);ifstate[i]≠eatthenself[i].wait;end;procedureentryputdown(i:0…4);beginstate[i]:=think;test(i+4mod5);test(i+1mod5);endproceduretest(k:0…4)beginifstate[k+4mod5]≠eatandstate[k]=hungryandstate[k+1mod5]≠eatthenbeginstate[k]:=eat;self[k].signal;end;end

beginfori:=0to4dostate[i]:=think;endTypeDP=monitorproceduretest(3.4.3读者——写者问题

一个数据文件或记录(统称数据对象)可被多个进程共享。其中有些进程在读（reader进程）；另一些进程要对数据对象进行写或修改（writer进程）。允许多个reader进程同时读一共享对象，但绝不允许一个writer进程和其他的reader进程或writer进程同时访问共享对象。所谓TheReader-WriterProblem，是指保证一个writer进程必须与其他进程互斥地访问共享对象的同步问题。3.4.3读者——写者问题一个数据文件或记录(统称数据对varrmutex,wmutex:semaphore:=1,1;readcount:intger:=0;beginparbeginreader:beginrepeatwait(rmutex);ifreadcount=0thenwait(wmutex);readcount:=readcount+1;signal(rmutex);…Performreadoperation;…

wait(rmutex);readcount:=readcount-1;ifreadcount=0thensignal(wmutex);signal(rmutex);untilfalse;endwriter:beginrepeatwait(wmutex);performwriteoperation;signal(wmutex);untilfalse;endparendend为实现reader进程与writer进程读或写时的互斥，而设置的互斥信号量。表示正在读的进程数目。因为readcount是一个可被多个reader进程访问的临界资源，故应为它设置一互斥信号量rmutex。由于只要有一个reader进程在读，便不允许writer进程去写。故当readcount=0时，表示尚无reader进程在读，这时reader进程才需要执行wait(wmutex)操作，若操作成功，reader进程便可去读，相应地readcount+1。仅当reader进程在执行了readcount-1操作后其值为0时,才需执行signal(wmutex),以便让writer进程写。varrmutex,wmutex:wait(r502、利用信号量集解决读者—写者问题此处的读者—写者问题与前面的略有不同，增加了一条限制，即最多只允许RN个读者同时读。为此，又引入一个信号量L，其初值为RN，通过执行wait（L，1，1）操作来控制读者的数目，每当有一个读者进入时，都要先执行wait（L，1，1）操作，使L减1。当有RN个读者进入读后，L便减为0，第RN+1个读者要进入读时，必然会因wait（L，1，1）操作失败而阻塞。

502、利用信号量集解决读者—写者问题此处的读者—写者问题与51利用信号量集解决读者—写者问题VarRNinteger;L,mx:semaphore:=Rn,1;beginparbeginreader:beginrepeatSwait(L,1,1)Swait(mx,1,0)…performreadoperation;…Ssignal(L,1);untilfalseendwriter:beginrepeatSwait(mx,1,1;L,RN,0);performwriteopration;Ssignal(mx,1)untilfalse;endparendend51利用信号量集解决读者—写者问题VarRNintege3.5进程通信进程通信是指进程之间的信息交换。进程的互斥和同步可归结为低级通信。在进程互斥中，进程通过修改信号量，向其他进程表明临界资源是否可用。信号量机制作为同步工具是卓有成效的，但作为通信工具则不够理想，主要是效率低和通信对用户不透明。OS系统提供的高级进程通信，是用户可以直接利用操作系统提供的一组通信命令，去大量传送数据的一种通信方式。在这种方式下，通信过程对用户是透明的，从而简化了通信程序编制上的复杂性。3.5进程通信进程通信是指进程之间的信息交换。进程的互斥和3.5.1进程通信的类型共享存储器系统（Shared-MemorySystem）在该系统中，是在存储器中划出一块共享存储区，诸进程可通过对该区中的数据进行读或写来实现通信。进程通信前，向系统申请共享区中的一个分区，并指定该分区的关键字，若系统分配了，则申请者把获得的分区连接到本进程上，可象读写普通存储器一样来读写该公用存储分区。3.5.1进程通信的类型共享存储器系统（Shared-Me消息传递系统（MessagepassingSystem）在该系统中，进程间的数据交换以消息为单位，在计算机网络系统中消息又称为报文。程序员直接利用系统提供的一组通信命令（原语）来实现通信。属高级通信方式。该系统因其实现方式不同，可分为：直接通信方式。发送进程直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上。接受进程从缓冲队列中取得消息。间接通信方式。发送进程将消息发送到称为信箱的中间实体中，接收进程从中取走消息。在计算机网络系统中被称为电子邮件系统。消息传递系统（MessagepassingSystem）管道(Pipe)通信管道是指用于连接一个读进程和一个写进程，以实现他们之间通信的共享文件(pipe)。写进程以字符流形式将数据送入管道，读进程从管道中取得数据。由于通信是利用管道进行的，故称为管道通信。管道通信机制应提供三方面的协调能力：互斥。一个进程正对pipe读/写时，另一个进程必须等待。同步。写进程把一些数据写入pipe后，便去睡眠，直到读进程取走数据后，再唤醒它。读进程读一空pipe时，也应睡眠，直到写进程将数据写入pipe后，才将它唤醒。双方是否存在。只有确定对方已存在，才能进行通信。管道(Pipe)通信3.5.2直接消息传递系统直接通信原语指发送进程利用OS提供的命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。通常系统提供两条通信原语：

Send(Receive,message);//发送原语，将消息message发送给接收者Receive。

Receive(Sender,message);//接收原语，接收发送者Sender发来的消息message。有时，接收进程可与多个发送进程通信，故不可能事先指定发送进程，这时接收原语中的源进程参数是已经进行通信后的返回值：

Receive(id,message);//id为返回值。3.5.2直接消息传递系统直接通信原语利用直接通信原语解决生产者—消费者问题。Repeat…produceaniteminnextp;…send(consumer,nextp);Untilfalse;Reaptreceive(producer,nextc);Untilfalse;利用直接通信原语解决生产者—消费者问题。消息格式消息格式与所处的环境有关。通常可把一个消息分为消息头和消息正文两部分，消息头包括消息传输时所需的控制信息，消息正文是发送进程实际所发送的数据。消息格式有定长格式和变长格式。定长格式开销较小，适合快速的便签式通信，变长格式开销较大，适合于发送较长消息。消息格式进程同步方式进程之间通信，往往需要辅以进程同步来协调通信。当一进程发送一消息后，有两种可能性：一是发送进程阻塞，直到消息被接收进程接收，二是发送进程继续执行。类似地，接收进程接收一消息后也有继续执行或阻塞两种可能。根据发送进程和接收进程都可采取阻塞或继续执行两种方式的情况，可组合出三种同步方式：进程同步方式发送进程阻塞、接收进程阻塞：主要用于进程之间紧密同步、发送进程与接收进程之间无缓冲区时。这两个进程平时都处于阻塞状态，直到有消息传递时。这种同步方式称为汇合。发送进程不阻塞、接收进程阻塞：平时发送进程不阻塞，故可尽快地将若干个消息发给多个目标；接收进程平时处于阻塞态，直到发送进程发来消息时才被唤醒。发送进程和接收进程均不阻塞：平时发送进程和接收进程都忙于自己的事情，仅当发生某事件，使它无法运行时才把自己阻塞起来等待。发送进程阻塞、接收进程阻塞：主要用于进程之间紧密同步、发送进通信链路（communicationlink）为使发送进程和接收进程之间进行通信，必须在它们之间建立一条通信链路。建立通信链路的方式有两种，一种是由发送进程在通信之前，用显式的建立连接命令，请求系统为之建立一条通信链路，在链路使用完后拆除链路。第二种是发送进程无须明确提出建立链路的请求，利用系统提供的发送命令，系统会自动地为之建立一条链路。根据通信方式的不同，链路分为单向链路和双向链路。通信链路（communicationlink）3.5.3信箱通信信箱的结构信箱是一种数据结构，在逻辑上，可以分为两部分：信箱头：用以存放有关信箱的描述信息；信箱体：由若干个可以存放消息（或消息头）的信箱格组成，信箱格的数目，以及每格的大小，是在创建信箱时创建的。3.5.3信箱通信信箱的结构信箱的类型信箱可由OS创建，也可由用户进程创建，创建者是信箱的拥有者。信箱可分为三类，私用信箱。用户进程为自己建立的。公用信箱。由OS创建。共享信箱。由某进程创建并指明共享者，创建者和共享者可使用。在发送进程和接收进程间存在四种关系，即一对一；多对一；一对多；多对多关系。信箱的类型信箱通信原语系统为信箱通信提供了若干条原语：信箱的创建和撤消。消息的发送和接收。Send(mailbox,message);//将一个消息发送到

指定信箱Receive(mailbox,message);//从指定信箱接

收一个消息信箱通信原语3.5.4直接消息传递系统实例消息缓冲队列通信机制广泛用于本地进程之间的通信。在该机制中，发送进程利用Send原语将消息直接发送给接收进程；接受进程则利用Receive原语接收消息。消息缓冲队列通信系统中的数据结构消息缓冲区：是消息缓冲通信方式中主要使用的数据结构，可描述为：

typemessagebuffer=recordsender;size;text;next;endPCB中有关通信的数据项：利用消息缓冲队列通信机制时，PCB中应增加的数据项有mq（消息队列首指针）；mutex（消息队列互斥信号量）sm（消息队列资源信号量）。3.5.4直接消息传递系统实例消息缓冲队列通信机制广泛用于663.5.4消息缓冲队列通信机制（2）发送原语：其描述如下：Proceduresend(receive,a)begingetbuf(a.size,i);getid(PCBset,receiver,j);i.sender:=a.sender;wait(j.mutex);i.size:=a.size;insert(j.mq,i);i.text:=a.text;signal(j.mutex);i.next:=0;signal(j.sm);

endsmProcessASender:ASend(B,a)Size:5Text:hellomutexmqPCB(B)Sender:ASize:5Text:helloNext:0ProcessBReceive(b)Sender:ASize:5Text:helloa发送区ab接收区bi663.5.4消息缓冲队列通信机制（2）发送原语：其描述如673.5.4消息缓冲队列通信机制（3）接收原语：接收进程调用receive(b)，从自己的消息缓冲队列mq中摘下第一个消息缓冲区i，并将其中的数据复制到以b为首址的指定消息接收区内。接收原语描述如下：Procedurereceive(b)

beginj:=internalname;b.sender:=i.sender;wait(j.sm);b.size:=i.size;wait(j.mutex);b.text:=i.text;remove(j.mq,i)endsignal(j.mutex);673.5.4消息缓冲队列通信机制（3）接收原语：接收进程3.5.5线程间的同步和通信互斥锁(mutex)互斥锁用于实现线程对共享资源的互斥访问。互斥锁有两种状态，即开锁(unlock)和关锁(lock)。相应地，可用两条命令对互斥锁进行操作，关锁操作lock将mutex关上，开锁操作unlock打开mutex。为减少线程阻塞的机会，有的系统还提供了用于mutex的操作命令trylock。当一个线程利用trylock去访问mutex时，若mutex处于开锁状态，trylock将返回一个指示成功的状态码；若mutex处于关锁状态，则trylock并不会阻塞该线程，只是返回一个指示操作失败的状态码。3.5.5线程间的同步和通信互斥锁(mutex)条件变量许多情况下，只利用mutex来实现互斥访问，可能会引起死锁，为此引入条件变量。一个条件变量通常与一个互斥锁一起使用，即在创建一个互斥锁时，便联系着一个条件变量。单纯的互斥锁用于短期锁定，主要用来保证对临界区的互斥进入。条件变量则用于线程的长期等待，直至所等待的资源成为可用。以下讨论如何利用互斥锁和条件变量实现对资源R的访问。条件变量对资源R的申请Lockmutex;checkdatastructure;while(Rbusy);wait(conditionvariable);markRasbusy;Unlockmutex释放RLockmutex;markRasfree;unlockmutex;Wakeup(conditionvarialbe);对资源R的申请Lockmutex;释放R信号量机制信号量机制也可用于多线程OS，为提高效率，可为线程和进程分别设置相应的信号量。私用信号量。为同一进程中各线程之间的同步而设置，其数据结构存放在应用程序的地址空间中，私用信号量属于特定进程所有，OS并不知道其存在。如果一旦发生私用信号量的占用者异常或正常结束，但并未释放该信号量所占用空间的情况时时，系统将无法使它恢复为0（空），也不能将它传递给下一个请求它的线程。公用信号量。为实现不同进程间或不同进程中各线程之间的同步而设置。其数据结构存放在受保护的系统存储区中，由OS为它分配空间并进行管理，故也称系统信号量。如果信号量的占有者在结束时未释放该公用信号量，则OS会自动将该信号量空间回收。信号量机制湘潭大学第3章

进程的同步与通信湘潭大学第3章

进程的同步与通信进程的异步性导致程序执行的不可再现性，给系统造成混乱。进程同步的主要任务，是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。进程的异步性导致程序执行的不可再现性，给系统造成混乱。进程同3.1进程同步的基本概念进程间的相互制约关系在多道程序环境下，系统中可能有着许多进程，这些进程之间可能存在以下两种关系。间接相互制约关的系：多个进程之间彼此无关，并不知道其他进程的存在，但这些进程既然同处于一个系统中，也就必然存在资源共享的关系，如共享CPU、I/O设备等。此时进程同步的主要任务是保证诸进程能互斥地访问临界资源。这样，系统中的资源应由系统统一管理，不允许用户进程直接使用。直接相互制约的关系：在某些进程间还存在相互合作关系，此时进程同步的主要任务是保证诸进程在执行次序上的协调，不会出现与时间有关的差错。3.1进程同步的基本概念进程间的相互制约关系临界资源临界资源，也称独占资源，是在一段时间内只允许一个进程访问的资源。对临界资源，进程间应采取互斥方式共享。例子：Producer-Consumer问题描述了一个生产者进程（PP）生产消息，并提供给一个消费者（CP）进程消费。为使PP和CP能并发执行，设置一个有n个缓冲区的缓冲池，PP将其生产的消息放入一缓冲区中，CP可从一缓冲区取得消息。尽管所有PP和CP都以异步方式运行，但它们之间必须保持同步，即不允许CP到一空缓冲区取消息，也不允许PP向一满的缓冲区投放消息。临界资源012354n-2n-1inoutcounter计数器输入指针输出指针012354n-2n-1inoutcounter计数器输入指PP和CP共享的变量：Varn,integer;Typeitem=…;Varbuffer:array[0,1…n-1]ofitem;in,out:0,1…n-1;counter:0,1…n;PP和CP共享的变量：PP:repeat……produceaniteminnextp;……whilecounter=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;untilfalse;CP:repeatwhilecounter=0dono-opnextc:=buffer[out];out:=(out+1)modn;counter:=counter-1;consumetheiteminnextcuntilfalse;PP:repeatCP:repeat

以上的生产者程序和消费者程序，二者在顺序执行时结果是正确的。但若并发执行就会出错，原因是这二个进程共享变量counter,生产者对它加1，消费者对它减1，这两个操作用机器语言实现时的形式可为：设counter的当前值是5若按下述方式运行register1:=counter;（register1:=5）register1:=registe1+1（register1:=6)register2:=counter;(register2:=5)register2:=registe2-1;(register2:=4)counter:=register1(counter=6)counter:=register2;(counter=4)Producer:register1:=counter;register1:=registe1+1;counter:=register1;Consumer:register2:=counter;register2:=registe2-1;counter:=register2;(counter=5)counter正确的答案应是5，而现在是4故应将counter作为临界资源处理以上的生产者程序和消费者程序，二者在顺序执行时结果是正确的临界区临界区的定义定义：在每个进程中访问临界资源的那段代码称为临界区（criticalsection).若能保证诸进程互斥地进入自己的临界区，便可实现它们对临界资源的互斥访问。为此，进程在进入临界区之前应检查欲访问的临界资源，若临界资源未被访问，便可进入临界区，否则不能进入。因此须在临界区前设置一段称为进入区(entrysection)的代码段；同样在其后加上一段称为退出区的代码段(exitsection)。进程中除进入区、临界区、及退出区之外的其他代码段称为剩余区。一个访问临界资源的循环进程描述如下：

RepeatEntrysectionCriticalsection;ExitsectionRemaindersectionUntilfalse临界区一个访问临界资源的同步机制应遵循的准则空闲让进：当无进程处于临界区时，表明临界资源处于空闲状态。可允许一请求进入临界区的进程立即进入自己的临界区。忙则等待：当已有进程进入到临界区时，表明临界资源正被访问，故其他试图进入临界区的进程必须等待。有限等待：对要求访问临界资源的进程，应保证该进程能在有效时间内进入自己的临界区，以免陷入“死等状态”。让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。同步机制应遵循的准则硬件同步机制目前许多计算机已提供了一些特殊的硬件指令，允许对一个字中的内容进行检测和修正，或是对两个字中的内容进行交换等，可利用这些特殊的指令来解决临界区问题。实际上，在对临界区进行管理时，可以将标志看作一个锁，“锁开”进入，“锁关”等待，初始时锁是打开的。每个要进入临界区的进程，必须先对锁进行测试，当锁未开时，则必须等待，直至锁被打开。反之，当锁是打开的时，则应立即将其锁上，以阻止其他进程进入临界区。显然，为防止多个进程同时测试到锁开的情况，测试和关键操作必须是连续的，不允许分开进行。硬件同步机制关中断关中断是实现互斥的最简单方法之一。在进入锁测试之前，关闭中断，直到完成锁测试并上锁之后才能打开中断。这样，进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度，也就不会发生进程或线程切换。关中断的缺点：[1]滥用关中断权力可能导致严重后果；[2]关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；[3]不适用于多处理器系统。关中断利用test-and-set指令实现互斥这是借助“测试并建立”硬件指令TS来实现互斥的方法，该指令的一般性描述为：FunctionTS(varlock:boolean):booleanBeginTS:=lock;Lock:=true;EndTS指令可看作一个函数过程，其执行过程是不可分的，即是一条原语。其中，lock有两种状态：当lock=false时，表示该资源空闲；当lock=true时，表示该资源正在被使用。利用test-and-set指令实现互斥用TS指令管理临界区时，为每个临界资源设置一个布尔变量lock，用lock代表该资源的状态，可以看成一把锁，初值为false,表示该临界资源空闲，进程进入临界区之前，首先用TS指令测试lock，如果其值为false，则表示没有进程在临界区内，可以进入，并将lock赋值为true,这等效于关闭了临界资源，使任何进程都不能进入临界区，否则必须循环测试，直到TS(s)为false。利用TS指令实现互斥的循环进程结构可描述为：用TS指令管理临界区时，为每个临界资源设置一个布尔变量locReapt…WhileTS(lock)doskip;Criticalsection;Lock:=false;Remaindersection;UntilfalseReapt利用Swap指令实现进程互斥Swap称为对换指令，用于交换两个字的内容，其处理过程描述为：ProcedureSwap(a,b:boolean)Vartemp:boolean;Begintemp:=a;a:=b;b:=tempend利用Swap指令实现进程互斥利用Swap实现互斥的方法是为每个临界资源设置一个全局布尔变量lock，其初值为false，在每个进程中在利用一个局部布尔变量key，利用Swap指令实现进程互斥的循环进程可描述为：Repeatkey:=true;repeatSwap(lock,key);untilkey=false;临界区操作；Lock:=false;…Untilfalse;利用Swap实现互斥的方法是为每个临界资源设置一个全局布尔变利用硬件指令能有效地实现进程互斥，但当临界资源忙碌时，其他访问进程必须不断地进行测试，处于一种“忙等”状态，不符合“让权等待”的原则，造成处理机时间浪费，同时也很难将它们用于复杂的进程同步问题。利用硬件指令能有效地实现进程互斥，但当临界资源忙碌时，其他访3.2信号量机制信号量机制是一种有效的进程同步工具。只能用于对一个临界资源实现互斥访问的信号量机制：整型信号量记录型信号量能同时对多个临界资源实现互斥访问的信号量机制：“AND”信号量信号量集3.2信号量机制信号量机制是一种有效的进程同步工具。3.2.1整型信号量和记录型信号量整型信号量整型信号量定义为一个用于表示资源数目的整型量S，除初始化外，仅能通过两个