进程并发与互斥教学教材

3.5进程并发与互斥3.5.1互斥算法3.5.2信号量(semaphore)3.5.3同步算法3.5.4经典的进程互斥同步问题13.5.1互斥算法3.5.1.1临界资源3.5.1.2临界区的访问过程3.5.1.3同步机制应遵循的准则23.5.1.1临界资源进程间资源访问冲突共享变量的修改冲突（空间）操作顺序冲突（时间）在多道程序环境下——各进程之间存在资源共享，进程的运行时间和空间将会受影响进程间的制约关系间接制约：进行竞争——独占分配到的部分或全部共享资源，“互斥”直接制约：进行协作——等待来自其他进程的信息，“同步”3共享变量的修改冲突4有6种可能的操作顺序，只有一种结果是正确的。6互斥：指多个进程不能同时使用同一个资源为保证系统正常工作，多个并发进程在对共享的硬件或软件（如外设、共享代码段、共享数据结构）进行访问时（关键是进行写入或修改），必须互斥地进行。——有些共享资源可以同时访问，如只读数据。系统资源中每次只允许一个进程使用，而不能由多个进程同时共享的资源称为临界资源。73.5.1.2临界区的访问过程临界区临界资源（CriticalResources）：一种一次只能为一个进程服务的资源。临界区（CriticalSection）：进程中访问临界资源的程序。每个使用该资源的进程都要包含一个临界区。8临界区(criticalsection)：进程中访问临界资源的一段代码。进入区(entrysection)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志退出区(exitsection)：用于将“正在访问临界区”标志清除。剩余区(remaindersection)：代码中的其余部分。9。两个进程不能同时进入访问同一临界资源的临界区，这称为进程互斥。103.5.1.3互斥机制应遵循的准则空闲则进：当没有进程在临界区时，任何需要进入临界区的进程都允许立即进入。

忙则等待：在共享同一对象的所有进程中，一次只能有一个进程进入临界区。其它要求进入临界区的进程只能等待。

有限等待：任何一个进程经有限时间等待后都能进入临界区，不允许出现进程“死等”的情况。让权等待：当一个进程不能进入临界区时要立即阻塞自己，释放处理机让其它进程使用，避免“忙等”。111、进程互斥的软件方法算法:加锁法设立一个公用整型变量key［Ｓ］：描述允许进入临界区的标志进程在进入区循环检查是否允许进入临界区：key［Ｓ］为1时，进程P可进入（否则是无限等待）；加锁（置key［Ｓ］为0)，进入临界区；进程P退出临界区时解锁，在退出区修改允许进入标识key［Ｓ］为1；缺点：多个进程可能同时进入临界区。12算法如下：ProcessP(1) ProcessP(2)Begin begin…… ……While(key［Ｓ］=0)doskip;While(key［Ｓ］=0)doskip;key［Ｓ］=0; key［Ｓ］=0;Criticalsection; Criticalsection;key［Ｓ］=1; key［Ｓ］=1;…… ……end. end.132、进程互斥的硬件方法为保证第一步和第二步执行不可分离。有些机器在硬件中设置了“测试与设置”指令，Test-and-Set指令（TS指令）该指令读出标志后设置为TRUEbooleanTS(boolean*lock){booleanold;old=*lock;*lock=TRUE;returnold;}lock表示资源的两种状态：TRUE表示正被占用，FALSE表示空闲14互斥算法（TS指令）利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE在进入区利用TS进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过；15Swap指令（或Exchange指令）交换两个字（字节）的内容voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}16互斥算法（Swap指令）利用Swap实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE。每个进程设置一个私有布尔变量keykey=TRUE;do{SWAP(&lock,&key);}while(key)doskip;lock=FALSE;criticalsectionremaindersection17优点适用于任意数目的进程，在单处理器或多处理器上更显其优越简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量缺点等待要耗费CPU时间，即“忙等”，不能实现“让权等待”可能产生“饿死”现象：有的进程可能永远执行不了18试考虑以下进程PA和PB反复使用临界区的情况： PA A：lock(key［Ｓ］) 〈Ｓ〉unlock(key［Ｓ］) GotoA PB B：lock(key［Ｓ］) ＜Ｓ＞ unlock(key［Ｓ］) GotoB193.5.2信号量(semaphore)3.5.2.1信号量和P、V原语3.5.2.2利用信号量实现互斥多数互斥算法缺乏公平性，只有获得处理机的进程才可进行进入临界区的测试，且测试结果具有偶然性。需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。信号量代表可用资源实体的数量。203.5.2.1信号量和P、V原语为了实现进程的互斥和同步，操作系统中引进了信号量(Semaphore)的概念。信号量具有以下特性：(1)信号量是一个整形变量。

2)每一个信号量表示一种系统资源的状况，其值表示该资源当前可用的数量，初值为非零。(3)每一个信号量都对应一个空或非空的等待队列。该队列就是信号量所代表的资源的等待队列。

4)对信号量只能实施P、V操作，只有P、V操作原语才能改变其值。21信号量只能通过初始化和两个标准的原语来访问——作为OS核心代码执行，不受进程调度的打断初始化资源信号量为指定一个非负整数值，表示空闲资源总数——若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数221．P操作原语procedureP(vars:semaphore)begins:=s-1;ifs<0thenW(s);end23w(s)表示将调用P操作原语的进程置成等待信号量s的状态。进程执行P操作时，首先将信号量s减1，其结果若s≥o，则该进程继续运行；若结果s<o则阻塞该进程，并把它插入到信号量s的等待队列中。242．V操作原语ProcedureV(vars:semaphore)begins:=s+1;ifs≤0thenR(s);end25R(s)表示从信号量s的等待队列中释放一个进程。进程执行V操作时，首先将信号量s加1，如果s>o，则该进程继续执行。如果s≤0则释放s信号量等待队列中队首的进程，解除其阻塞状态。调用V操作的当前进程继续执行。26P、V操作的物理意义：执行P操作：s:=s-1意味着把s对应的一个资源分配给调用P操作的进程，资源的数量减少一个。若s减一后其值为0，表示此类资源已全部分配给各个进程了。27在此之后若又有进程请求该资源，在该进程调用P操作时，s减1后成为负值，则执行W(s)，该进程将转换为阻塞态并进入信号量s对应的等待队列中。当信号量s为负值时，它的绝对值表示在该信号量等待队列中的进程数目。28执行V操作时：s:=s+1意味着调用V操作的进程释放了一个信号量s对应的资源。s加一后，若s为负值，表明s对应的等待队列中仍有等待该资源的阻塞进程，则调用R(s)释放等待队列中的一个进程。29被释放的进程是在执行P操作时因资源不足而进入阻塞态的，由于V操作释放了它所需的资源，它就转换为就绪态可以继续执行。30记录型信号量每个信号量s除一个整数值s.count（计数）外，还有一个进程等待队列s.queue，其中是阻塞在该信号量的各个进程的标识311.P原语wait(s)--s.count; //表示申请一个资源;if(s.count<0) //表示没有空闲资源;{调用进程进入等待队列s.queue;阻塞调用进程;}322.V原语signal(s)++s.count; //表示释放一个资源；if(s.count<=0) //表示有进程处于阻塞状态；{从等待队列s.queue中取出一个进程P;进程P进入就绪队列;}V原语通常唤醒进程等待队列中的头一个进程333.5.2.2利用信号量实现互斥在实现进程互斥时，信号量的初值设为1，表示中只允许一个进程进入临界区。在进程执行过程中，当进入临界区时执行P操作，在离开临界区时执行V操作，使临界区位于对同一个信号量的P操作和V操作之间。34mutex为互斥信号量，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏35在进程互斥中使用的信号量，每个进程都可以对它实施P操作，这样的信号量又称为公用信号量。36s:semaphore;s:=1;进程A进程B．．．．．．

．．．．．．

P(s);P(s);临界区CRA;临界区CRB;V(s);V(s);．．．．．．．．．．．．用信号量实现两并发进程的互斥37s=10-101进程s:=s-1CRAs:=s+1R(s)AP(s)V(s)进程s:=s-1W(s)[阻塞等待]CRBs:=s+1BP(s)V(s)--------t1----------t2---------------t3----------------t4---->383.5.3进程同步

1、同步概念直接制约一组并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程消息(事件）进程互相给对方进程发送执行条件已经具备的信号同步一组并发进程，因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步39PC （计算进程） : A: 计算 得到计算结果 Buf←计算结果 Goto APP

（打印进程） : B: 打印Buf中的数据 清除Buf中的数据 Goto B40一般来说，可以把各进程之间发送的消息作为信号量看待。与进程互斥时不同的是，这里的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关。因此，称该信号量为私用信号量（PrivateSemaphvre）。412、同步的实现方法

利用信号量来描述前趋关系前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；为每个前趋关系设置一个信号量S12，其初值为042s1,s2:semaphore;s1=1,s2=0;cobegin repeatT1; repeatT2;coend;设定两个信号量s1和s2，s1的初值为1，s2的初值为0。如上例，有两个进程T1和T2，要求T1和T2同步运行，则43procedureT1:procedureT2:begin begin．．． ．．． P(s1); P(s2); m1; m2;

V(s2); V(s1);．．． ．．．end; end;44只能由一个进程对其实施P操作的信号量称为该进程的私有信号量。s1是T1的私有信号量，s2是T2的私有信号量。在两个进程相互推进的运行过程中，哪个进程的私有信号量为1，就表示它可以向前推进。453.5.4经典互斥同步问题生产者－消费者问题(theproducer-consumerproblem)问题描述：若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。46生产者进程不断生产产品并把它们放入缓冲区内，消费者进程不断从缓冲区中取走产品进行消费。当缓冲区中产品已经放满时，表示生产速度高于消费而出现了供过于求。这时，生产者进程不能再生产而必须等待产品被消费。当缓冲区取空时，表示消费速度高于生产而出现了供不应求。这时，消费者进程不能再消费而必须等待产品的生产。生产和消费的进程必须达到同步运行，才能使供需平衡。47缓冲区是一个临界资源，两个进程访问缓冲区必须互斥地执行。设一个公用信号量mutex，其初值为1。设生产者进程的私有信号量为empty，表示缓冲区中空闲位置的数目，即可以容纳产品的数目，初值为n。设消费者进程的私有信号量为full，表示缓冲区内已有产品的数目，其初值为0。48mutex,empty,full:semaphore;mutex:=1;empty:=n;full=0;cobeginproducer:begin L1: produceaproduct; P(empty); P(mutex); Addtobuffer; V(full); V(mutex); gotoL1; end;49 consumer:begin L2: P(full); P(mutex); takeonefrombuffer; V(empty); V(mutex); consumeproduct; gotoL2; end;coend;50采用信号量机制：full是“满”数目，初值为0，empty是“空”数目，初值为N。实际上，full和empty是同一个作用，始终有full+empty=Nmutex用于访问缓冲区时的互斥，初值是1每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥——否则可能死锁(为什么？)51无论是生产者进程还是消费者进程，其中V操作的次序是无关紧要的，但P操作的次序不能颠倒。52读者－写者问题(thereaders-writersproblem)问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个“读－写”互斥，“写－写”互斥，“读－读”允许53采用信号量机制：mutex互斥信号量:实现读者与写者、写者与写者之间的互斥，初值是1。Rcount读者共享的变量:表示“正在读”的进程数，初值是0；Rmutex表示对Rcount的互斥操作，初值是1。P(Rmutex);if(Rcount==0)thenP(mutex);++Rcount;V(Rmutex);read;P(Rmutex);--Rcount;if(Rcount==0)thenV(mutex);V(Rmutex);ReaderP(mutex);write;V(mutex);Writer54哲学家用餐问题

在该问题中设想有5位哲学家，他们共同坐在一张餐桌前用餐，用餐过后开始思考问题。他们的生活方式可描述为一个单调的循环：思考-饥饿-用餐-再思考­。已知餐桌上摆的是面条，每个人必须左右手各拿到一把叉子才可以开始进餐。而餐桌上只有5把叉子，任两个哲学家之间有一把，见图所示。55第i位哲学家的行为过程可描述为下面的形式。ProcessPhilosopher(i)BeginWhile(true)BeginThinking();P(mutex[i]); //请求左叉子P(mutex[i+1]mod5); //请求右叉子Eating(); //用餐过程V(mutex[i]); //释放左叉子V(mutex[i+1]mod5); //释放右叉子End;End;56附：信号量集一段处理代码需要同时获取两个或多个临界资源——可能死锁：各进程分别获得部分临界资源，然后等待其余的临界资源，“各不相让”基本思想：在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配。称为Swait(SimultaneousWait)。在Swait时，各个信号量的次序并不重要，虽然会影响进程归入哪个阻塞队列，但是由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁。信号量集用于同时需要多个资源时的信号量操作1.AND型信号量集AND型信号量集用于同时需要多种资源且每种占用一个时的信号量操作；57

Swait(S1,S2,…,Sn)

//P原语；{while(TRUE){if(S1>=1&&S2>=1&&…&&Sn>=1){ //满足资源要求时的处理；for(i=1;i<=n;++i)--Si; //注：与wait的处理不同，这里是在确信可满足//资源要求时，才进行减1操作；break;}else{ //某些资源不够时的处理；调用进程进入第一个小于1信号量的等待队列Sj.queue;阻塞调用进程;}}}58

Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //释放占用的资源；for(eachprocessPwaitinginSi.queue)//检查每种资源的等待队列的所有进程；{从等待队列Si.queue中取出进程P;if(判断进程P是否通过Swait中的测试)//注：与signal不同，这里要进行重新判断；{ //通过检查（资源够用）时的处理； 进程P进入就绪队列;}else{ //未通过检查（资源不够用）时的处理； 进程P进入某等待队列；}}}}592.一般“信号量集”一次需要N个某类临界资源时，就要进行N次wait操作－－低效又可能死锁基本思想：在AND型信号量集的基础上进行扩充：进程对信号量Si的测试值为ti（用于信号量的判断，即Si<ti，表示资源数量低于ti时，便不予分配），占用值为di（用于信号量的增减，即Si=Si-di和Si=Si+di）Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);一般信号量集用于同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理60一般“信号量集”的几种特定情况：Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配；Swait(S,1,1)表示互斥信号量；Swait(S,1,0)作为一个可控开关当S>=1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区；一般“信号量集”未必成对使用Swait和Ssignal如：一起申请，但不一起释放；61独木桥问题:某一条河上有一座独木桥，有人从北向南过桥，有人自南向北过桥，由于独木桥一次只能承载一人，所以请用信号量设计一种算法，让南北双方都能合理通行。公共汽车问题：在公共汽车上，售票员和司机需要合理配合才能保证运行。设售票员必须等汽车停止才能开门、上客、关门、售票；而司机必须等门关好了才能开车、行驶、到站、停车。现在请你用PV原语操作来同步司机和售票员的工作。思考题62假定一个阅览室最多可同时容纳100个人阅读，读者进入和离开阅览室时，都必须在阅览室门口的一个登记表上登记。假定每次只允许一个人登记和去掉登记，设阅览室内有100个座位。请用P,V原语编写读者进程的同步算法。63附：管程(monitor)用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程是管理进程间同步的机制，它保证进程互斥地访问共享资源，并方便地阻塞和唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好控制。64信号量同步的缺点同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；65管程的引入

这是一种具有面向对象程序设计思想的同步机制。它提供了与信号量机制相同的功能。管程（Monitor）概念是著名学者Hore于1974年提出的，并在很多系统中得到实现，诸如Pascal、Java、Modula-3等。管程是由局部数据结构、多个处理过程和一套初始化代码组成的模块。管程的特征为：

（1）管程内的数据结构只能被管程内的过程访问，任何外部访问都是不允许的；（2）进程可通过调用管程的一个过程进入管程；（3）任何时间只允许一个进程进入管程，其他要求进入管程的进程统统被阻塞到等待管程的队列上。66下图是管程的一个结构模型67l

P（c）：当遇到同步约束，就将进程阻塞在条件变量c关联的等待队列上。l

V（c）：从条件变量c关联的等待队列上唤醒一个进程，让它恢复运行。若队列上没有进程在等待，就什么也不做。管程的语言结构可描述为下属形式：Type管程名=MonitorBegin数据结构定义；局部变量定义；条件变量定义；

Porcedure

过程名（形式参数）

Begin

……… //过程体

End;

………

End;68模块化：一个管程是一个基本程序单位，可以单独编译复合数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码信息封装：管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的管程的主要特性69管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量为了保证管程共享变量的数据完整性，规定管程互斥进入管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作管程的实现要素70TypePC=MonitorBeginVarChar:buffer[N];VarInteger:counter,in,out;VarCondition:notfull,notempty;

PorcedurePUT（varchar:item）Begin ifcount=NthenP(notfull); Buffer[in]:=item; in:=(in+1)modN; Count:=count+1; V(notempty);End;PorcedureGET（char:item）Begin ifcount=0thenP(notempty); item:=Buffer[out]; out:=(out+1)modN; Count:=count-1; V(notfull);End;Begincount,in,out=0,0,0;End;End;利用管程PC解决生产者-消费者问题71ProcedureConsumer()BeginVarchar:x;While(true)BeginGET(x);Consume_the_item_in_x();EndEnd;应用程序算法如下。ProcedureProducer()BeginVarchar:x;While(true)BeginProduce_an_item_in_x();PUT(x);End;End;72管程的优点管程可增强模块的独立性：系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性引入管程可提高代码的可读性，便于修改和维护，正确性易于保证：采用集中式同步机制。一个操作系统或并发程序由若干个这样的模块所构成，一个模块通常较短，模块之间关系清晰。733.6进程间通信

(IPC,INTER-PROCESSCOMMUNICATION)3.6.1进程间通信的类型3.6.2共享存储器系统3.6.3管道(pipe)3.6.4消息传递741.低级通信和高级通信低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量。优点：速度快。缺点：传送信息量小。效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。主要用于控制进程执行速度的作用。用户直接实现通信的细节，编程复杂，容易出错。高级通信：能够传送任意数量的数据，目的主要是用于交换信息。

3.6.1进程间通信的类型752.进程的通信方式共享存储区方式不要求数据移动，可以任意读写和使用任意数据结构，需要进程互斥和同步的辅助来确保数据一致性管道方式消息或邮箱机制消息的发送不需要接收方准备好，随时可发送763.6.2共享存储器系统

这种通信需要在内存中开辟一个共享的存储空间，供进程之间进行数据传递。比如计算进程将所得的结果送入内存共享区的缓冲区环中，打印进程从中将结果取出来，就是一个利用共享存储器进行通信的例子。这种通信方式在UNIX、Linux、Windows及OS/2等系统中都有具体的实现。共享存储器系统中，共享的空间一般应当是需要互斥访问的临界资源。诸多进程为了避免丢失数据或重复取数，需要执行特定的同步协议。

在利用共享存储器进行通信之前，信息的发送者和接收者都要将共享空间纳入到自己的虚地址空间中，让它们都能访问该区域。存储器管理模块将共享空间映射成实际的内存空间。77（1）创建或删除共享存储区（2）共享存储区的附接与断接（3）共享存储区状态查询（4）共享存储区管理

共享存储器系统的特点：

利用共享存储器系统进行通信的效率特别高，适用于通信速度要求特别高的场合。

这种同步与互斥机制的实现一般要由程序员来承担，系统仅仅提供一个共享内存空间的管理机制。

78Linux的共享存储区创建或打开共享存储区(shmget)：依据用户给出的整数值key，创建新区或打开现有区，返回一个共享存储区ID。连接共享存储区(shmat)：连接共享存储区到本进程的地址空间，可以指定虚拟地址或由系统分配，返回共享存储区首地址。父进程已连接的共享存储区可被fork创建的子进程继承。拆除共享存储区连接(shmdt)：拆除共享存储区与本进程地址空间的连接。共享存储区控制(shmctl)：对共享存储区进行控制。如：共享存储区的删除需要显式调用shmctl(shmid,IPC_RMID,0)；793.6.3管道通信

管道（Pipe）是可供进程共享的一种外存文件，主要用于连接一个写入进程和一个读出进程，以实现它们之间的数据通信。写入进程按字符流的形式将数据写入管道文件中，让读出进程从中获得数据。由于管道机制特别适用于大容量数据的通信，因此在许多操作系统中被采用。管道通信机制分为无名管道和有名管道80进程通信实例——管道(pipe)

UNIX最早的消息传递机制是管道，管道是一条在进程间以字节流方式传送的通信通道。管道逻辑是被看作是管道文件，物理上则是由文件系统的高级缓冲区（通常几十KB）来实现，是单向的。在使用管道前要建立相应的管道，然后才可使用。利用UNIX提供的系统调用pipe，可建立一条同步通信管道。其格式为： pipe(fd) intfd［2］；这里，fd［1］为写入端，fd［0］为读出端。81示例例：用C语言编写一个程序，建立一个pipe，同时父进程生成一个子进程，子进程向pipe中写入一字符串，父进程从pipe中读出该字符串。解：程序如下： #include〈stdio.h〉 main() { intx，fd［2］； charbuf［30］，s［30］； pipe(fd)；/*创建管道*/ while((x=fork())==-1)；/*创建子进程失败时，循环*/ if(x==0)82 { sprintf(buf，″Thisisanexample＼n″)； write(fd［1］，buf，30)；/*把buf中字符写入管道*/ exit(0)； } else/*父进程返回*/ { wait(0)； read(fd［0］，s，30)；/*父进程读管道中字符*/ printf(″%s″，s)； } }831.Linux管道通过pipe系统调用创建无名管道，得到两个文件描述符，分别用于写和读。intpipe(intfildes[2]);文件描述符fildes[0]为读端，fildes[1]为写端；通过系统调用write和read进行管道的写和读；进程间双向通信，通常需要两个管道；只适用于父子进程之间或父进程安排的各个子进程之间；Linux中的命名管道，可通过mknod系统调用建立：指定mode为S_IFIFOintmknod(constchar*path,mode_tmode,dev_tdev);842.WindowsNT管道无名管道：类似于Linux管道，CreatePipe可创建无名管道，得到两个读写句柄；利用ReadFile和WriteFile可进行无名管道的读写；BOOLCreatePipe(PHANDLEhReadPipe, //addressofvariableforreadhandle PHANDLEhWritePipe, //addressofvariableforwritehandle LPSECURITY_ATTRIBUTESlpPipeAttributes, //pointertosecurityattributes DWORDnSize //numberofbytesreservedforpipe);85

系统中的进程在交互传送数据时，涉及到对数据结构的互斥使用问题。为实施互斥，进程之间需要同步。提供这些功能的一个好方法是消息传递。还有一个优点是，消息传递可较容易地在单处理机系统、分布式系统、共享存储器的多处理机系统中实现。

消息传递中的管理机制由操作系统提供，主要体现为以下两个原语。发送原语：send(destination,message)，其中，destination为消息的目的地（接收进程名）。该原语表示发送消息到进程destination。接收原语：receive(source,message)，其中，source是消息发出地（发送进程名）。该原语表示从进程source接收消息。3.6.4消息传递86

在这种方式中要解决的关键问题仍然是同步问题：仅当一条消息从某个进程发送后，其他进程才可能接收到消息。那么，消息发送者通过send原语发出一条消息后，应当如何处理呢？有两种选择：要么将发送进程阻塞起来，直到消息被接收为止，再把它唤醒；要么不阻塞发送进程。同样地，消息接收者通过receive原语要接收一条消息时，如果能立即收到，可继续运行。如果消息尚未发出的话，也有两种选择：要么阻塞进程等待消息；要么不阻塞进程，放弃接收。

这样一来，系统可选择的处理有以下几种：

会合（renezvous）方式

宽松同步方式

不阻塞发送者，只阻塞接收者方式一、实现同步的方法

87

在消息传递中，发送者需要明确消息发往哪里，接收者需要指明消息的来源。通常，按send和receive原语的实现方式可分为直接寻址和间接寻址两类。1.直接寻址（DirectAddressing）

实现直接寻址的一个较为简单的方案是，让send原语明确指出接收者的进程号，receive原语明确指出发送者的进程号，系统根据这两个原语实现直接通信。这种一对一的通信，用来处理并发进程之间的合作是相当有效的。2.间接寻址（IndirectAddressing）

在间接寻址方式中，消息并不直接从发送进程传到接收进程，而是要经过一个中间介质——临时保存消息的队列，通常称为“信箱”。因此，两个通信进程的操作是，一个进程将消息发到信箱中，另一个从信箱中取消息。二、直接通信和间接通信

883.7线程(THREAD)3.7.1线程的引入3.7.2进程和线程的比较3.7.3线程的执行3.7.4线程的分类

引入线程的目的是以小的系统开销来提高进程内的并发程度。893.7.1线程的引入为提高进程内各个功能模块的并发性传统os：为进程创建一些子孙进程进程：资源分配单位（存储器、文件）和CPU调度（分派）单位，由PCB和进程间上下文确定。

由于进程是资源的拥有者，故其在创建、撤销及状态转换时，系统要付出较大的时间和空间开销，从而使得系统中的进程不宜过多，切换频率不宜太高，因此限制了并发程度的提高。为了减少程序并发所付出的时间和空间开销，使os具有更好的并发性，把进程的两个基本属性分开。90现代os：一个进程可以创建多个线程线程：“轻量级进程（LightweightProcess）”，是进程的一个实体，使被独立调度和分派的基本单位，表示进程中的一个控制点（执行体），执行一系列指令。91进程只作为其他资源分配单位线程作为CPU调度单位只拥有必不可少的资源，如：线程状态、寄存器上下文和栈同样具有就绪、阻塞和执行三种