进程并发与互斥.ppt

《进程并发与互斥.ppt》由会员分享，可在线阅读，更多相关《进程并发与互斥.ppt（107页珍藏版）》请在三一办公上搜索。

1、1,3.5 进程并发与互斥,3.5.1 互斥算法3.5.2 信号量(semaphore)3.5.3 同步算法3.5.4 经典的进程互斥同步问题,2,3.5.1 互斥算法,临界资源临界区的访问过程同步机制应遵循的准则,3,3.5.1.1 临界资源,进程间资源访问冲突共享变量的修改冲突（空间）操作顺序冲突（时间）,在多道程序环境下各进程之间存在资源共享，进程的运行时间和空间将会受影响,进程间的制约关系 间接制约：进行竞争独占分配到的部分或全部共享资源，“互斥”直接制约：进行协作等待来自其他进程的信息，“同步”,4,共享变量的修改冲突,5,操作顺序冲突,有3个进程：get,copy和put，它们对4

2、个存储区域f、s、t和g进行操作。,6,有6种可能的操作顺序，只有一种结果是正确的。,7,互斥：指多个进程不能同时使用同一个资源,为保证系统正常工作，多个并发进程在对共享的硬件或软件（如外设、共享代码段、共享数据结构）进行访问时（关键是进行写入或修改），必须互斥地进行。有些共享资源可以同时访问，如只读数据。,系统资源中每次只允许一个进程使用，而不能由多个进程同时共享的资源称为临界资源。,8,3.5.1.2 临界区的访问过程,临界区,临界资源（Critical Resources）：一种一次只能为一个进程服务的资源。临界区（Critical Section）：进程中访问临界资源的程序。每个使用该

3、资源的进程都要包含一个临界区。,9,临界区(critical section)：进程中访问临界资源的一段代码。进入区(entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应“正在访问临界区”标志退出区(exit section)：用于将“正在访问临界区”标志清除。剩余区(remainder section)：代码中的其余部分。,10,。两个进程不能同时进入访问同一临界资源的临界区，这称为进程互斥。,11,3.5.1.3 互斥机制应遵循的准则,空闲则进：当没有进程在临界区时，任何需要进入临界区的进程都允许立即进入。忙则等待：在共享同一对象的

4、所有进程中，一次只能有一个进程进入临界区。其它要求进入临界区的进程只能等待。有限等待：任何一个进程经有限时间等待后都能进入临界区，不允许出现进程“死等”的情况。让权等待：当一个进程不能进入临界区时要立即阻塞自己，释放处理机让其它进程使用，避免“忙等”。,12,1、进程互斥的软件方法,算法:加锁法,设立一个公用整型变量 key：描述允许进入临界区的标志进程在进入区循环检查是否允许进入临界区：key为1时，进程P可进入（否则是无限等待）；加锁（置key为0)，进入临界区；进程P退出临界区时解锁，在退出区修改允许进入标识key为1；,缺点：多个进程可能同时进入临界区。,13,算法如下：Process

5、 P(1)Process P(2)Begin begin While(key=0)do skip;While(key=0)do skip;key=0;key=0;Critical section;Critical section;key=1;key=1;end.end.,14,2、进程互斥的硬件方法,为保证第一步和第二步执行不可分离。有些机器在硬件中设置了“测试与设置”指令，,Test-and-Set指令（TS指令）,该指令读出标志后设置为TRUEboolean TS(boolean*lock)boolean old;old=*lock;*lock=TRUE;return old;lock表示

6、资源的两种状态：TRUE表示正被占用，FALSE表示空闲,15,互斥算法（TS指令）,利用TS实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE在进入区利用TS进行检查：有进程在临界区时，重复检查；直到其它进程退出时，检查通过；,16,Swap指令（或Exchange指令）,交换两个字（字节）的内容void SWAP(int*a,int*b)int temp;temp=*a;*a=*b;*b=temp;,17,互斥算法（Swap指令）,利用Swap实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为FALSE。每个进程设置一个私有布尔变量key,18,优点适用于

7、任意数目的进程，在单处理器或多处理器上更显其优越简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量缺点等待要耗费CPU时间，即“忙等”，不能实现“让权等待”可能产生“饿死”现象：有的进程可能永远执行不了,19,试考虑以下进程PA和PB反复使用临界区的情况：PAA：lock(key)unlock(key)Goto APBB：lock(key)unlock(key)Goto B,20,3.5.2 信号量(semaphore),3.5.2.1 信号量和P、V原语3.5.2.2 利用信号量实现互斥,多数互斥算法缺乏公平性，只有获得处理机的进程才可进行进入临界区的测试，

8、且测试结果具有偶然性。需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。信号量代表可用资源实体的数量。,21,3.5.2.1 信号量和P、V原语,为了实现进程的互斥和同步，操作系统中引进了信号量(Semaphore)的概念。信号量具有以下特性：(1)信号量是一个整形变量。2)每一个信号量表示一种系统资源的状况，其值表示该资源当前可用的数量，初值为非零。(3)每一个信号量都对应一个空或非空的等待队列。该队列就是信号量所代表的资源的等待队列。4)对信号量只能实施P、V操作，只有P、V操作原语才能改变其值。,2

9、2,信号量只能通过初始化和两个标准的原语来访问作为OS核心代码执行，不受进程调度的打断初始化资源信号量为指定一个非负整数值，表示空闲资源总数若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数,23,1P操作原语 procedure P(var s:semaphore)begin s:=s-1;if s0 then W(s);end,24,w(s)表示将调用P操作原语的进程置成等待信号量s的状态。进程执行P操作时，首先将信号量s减1，其结果若so，则该进程继续运行；若结果so则阻塞该进程，并把它插入到信号量s的等待队列中。,25,2V操作原语Procedure V(var

10、 s:semaphore)begin s:=s+1;if s0 then R(s);end,26,R(s)表示从信号量s的等待队列中释放一个进程。进程执行V操作时，首先将信号量s加1，如果so，则该进程继续执行。如果s0则释放s信号量等待队列中队首的进程，解除其阻塞状态。调用V操作的当前进程继续执行。,27,P、V操作的物理意义：执行P操作：,s:=s-1意味着把s对应的一个资源分配给调用P操作的进程，资源的数量减少一个。若s减一后其值为0，表示此类资源已全部分配给各个进程了。,28,在此之后若又有进程请求该资源，在该进程调用P操作时，s减1后成为负值，则执行W(s)，该进程将转换为阻塞态并进

11、入信号量s对应的等待队列中。当信号量s为负值时，它的绝对值表示在该信号量等待队列中的进程数目。,29,执行V操作时：s:=s+1意味着调用V操作的进程释放了一个信号量s对应的资源。s加一后，若s为负值，表明s对应的等待队列中仍有等待该资源的阻塞进程，则调用R(s)释放等待队列中的一个进程。,30,被释放的进程是在执行P操作时因资源不足而进入阻塞态的，由于V操作释放了它所需的资源，它就转换为就绪态可以继续执行。,31,记录型信号量,每个信号量 s 除一个整数值s.count（计数）外，还有一个进程等待队列s.queue，其中是阻塞在该信号量的各个进程的标识,32,1.P 原语wait(s),-s

12、.count;/表示申请一个资源;if(s.count 0)/表示没有空闲资源;调用进程进入等待队列 s.queue;阻塞调用进程;,33,2.V 原语signal(s),+s.count;/表示释放一个资源；if(s.count=0)/表示有进程处于阻塞状态；从等待队列s.queue中取出一个进程P;进程P进入就绪队列;,V原语通常唤醒进程等待队列中的头一个进程,34,3.5.2.2 利用信号量实现互斥,在实现进程互斥时，信号量的初值设为1，表示中只允许一个进程进入临界区。在进程执行过程中，当进入临界区时执行P操作，在离开临界区时执行V操作，使临界区位于对同一个信号量的P操作和V操作之间。,

13、35,mutex为互斥信号量，其初值为1；在每个进程中将临界区代码置于P(mutex)和V(mutex)原语之间必须成对使用P和V原语：遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放（给其他等待的进程）；P、V原语不能次序错误、重复或遗漏,36,在进程互斥中使用的信号量，每个进程都可以对它实施P操作，这样的信号量又称为公用信号量。,37,s:semaphore;s:=1;进程A 进程B P(s);P(s);临界区CRA;临界区CRB;V(s);V(s);,用信号量实现两并发进程的互斥,38,s=1 0-1 0 1进程 s:=s-1 CRA s:=s+1 R(s)A P

14、(s)V(s)进程 s:=s-1 W(s)阻塞等待 CRB s:=s+1 B P(s)V(s)-t1-t2-t3-t4-,39,3.5.3 进程同步1、同步概念,直接制约 一组并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程消息(事件）进程互相给对方进程发送执行条件已经具备的信号同步 一组并发进程，因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步,40,PC（计算进程）:A:计算得到计算结果Buf 计算结果GotoA,PP（打印进程）:B:打印 Buf中的数据清除 Buf中的数据GotoB,41,一般来说，可以把各进程

15、之间发送的消息作为信号量看待。与进程互斥时不同的是，这里的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关。因此，称该信号量为私用信号量（Private Semaphvre）。,42,2、同步的实现方法利用信号量来描述前趋关系,前趋关系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；为每个前趋关系设置一个信号量 S12，其初值为0,43,s1,s2:semaphore;s1=1,s2=0;cobegin repeat T1;repeat T2;coend;,设定两个信号量s1和s2，s1的初值为1，s2的初值为0。,如上例，有两个进程T1和T2，要求T1

16、和T2同步运行，则,44,procedure T1:procedure T2:begin begin P(s1);P(s2);m1;m2;V(s2);V(s1);end;end;,45,只能由一个进程对其实施P操作的信号量称为该进程的私有信号量。s1是T1的私有信号量，s2是T2的私有信号量。在两个进程相互推进的运行过程中，哪个进程的私有信号量为1，就表示它可以向前推进。,46,3.5.4 经典互斥同步问题,生产者消费者问题(the producer-consumer problem),问题描述：若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享

17、缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。,47,生产者进程不断生产产品并把它们放入缓冲区内，消费者进程不断从缓冲区中取走产品进行消费。当缓冲区中产品已经放满时，表示生产速度高于消费而出现了供过于求。这时，生产者进程不能再生产而必须等待产品被消费。,当缓冲区取空时，表示消费速度高于生产而出现了供不应求。这时，消费者进程不能再消费而必须等待产品的生产。生产和消费的进程必须达到同步运行，才能使供需平衡。,48,缓冲区是一个临界资源，两个进程访问缓冲区必须互斥地执行。设一个公用信号量mutex，其初值为1。,设生产者进程的私有信号量为empty，表示缓冲区中空闲位置的数目，即可以

18、容纳产品的数目，初值为n。设消费者进程的私有信号量为full，表示缓冲区内已有产品的数目，其初值为0。,49,mutex,empty,full:semaphore;mutex:=1;empty:=n;full=0;cobegin producer:begin L1:produce a product;P(empty);P(mutex);Add to buffer;V(full);V(mutex);goto L1;end;,50,consumer:begin L2:P(full);P(mutex);take one from buffer;V(empty);V(mutex);consume pr

19、oduct;goto L2;end;coend;,51,采用信号量机制：full是“满”数目，初值为0，empty是“空”数目，初值为N。实际上，full和empty是同一个作用，始终有full+empty=Nmutex用于访问缓冲区时的互斥，初值是1 每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥否则可能死锁(为什么？),52,无论是生产者进程还是消费者进程，其中V操作的次序是无关紧要的，但P操作的次序不能颠倒。,53,读者写者问题(the readers-writers problem),问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多

20、个“读写”互斥，“写写”互斥，“读读”允许,54,采用信号量机制：mutex互斥信号量:实现读者与写者、写者与写者之间的互斥，初值是1。Rcount读者共享的变量:表示“正在读”的进程数，初值是0；Rmutex表示对Rcount的互斥操作，初值是1。,55,哲学家用餐问题,在该问题中设想有5位哲学家，他们共同坐在一张餐桌前用餐，用餐过后开始思考问题。他们的生活方式可描述为一个单调的循环：思考-饥饿-用餐-再思考。已知餐桌上摆的是面条，每个人必须左右手各拿到一把叉子才可以开始进餐。而餐桌上只有5把叉子，任两个哲学家之间有一把，见图所示。,56,第i位哲学家的行为过程可描述为下面的形式。Proce

21、ss Philosopher(i)Begin While(true)Begin Thinking();P(mutexi);/请求左叉子 P(mutexi+1 mod 5);/请求右叉子 Eating();/用餐过程 V(mutexi);/释放左叉子 V(mutexi+1 mod 5);/释放右叉子 End;End;,57,附：信号量集,一段处理代码需要同时获取两个或多个临界资源可能死锁：各进程分别获得部分临界资源，然后等待其余的临界资源，“各不相让”基本思想：在一个原语中，将一段代码同时需要的多个临界资源，要么全部分配给它，要么一个都不分配。称为Swait(Simultaneous Wait)

22、。在Swait时，各个信号量的次序并不重要，虽然会影响进程归入哪个阻塞队列，但是由于是对资源全部分配或不分配，所以总有进程获得全部资源并在推进之后释放资源，因此不会死锁。,信号量集用于同时需要多个资源时的信号量操作,1.AND型信号量集,AND型信号量集用于同时需要多种资源且每种占用一个时的信号量操作；,58,Swait(S1,S2,Sn)/P原语；while(TRUE)if(S1=1,59,Ssignal(S1,S2,Sn)for(i=1;i=n;+i)+Si;/释放占用的资源；for(each process P waiting in Si.queue)/检查每种资源的等待队列的所有进程；

23、从等待队列Si.queue中取出进程P;if(判断进程P是否通过Swait中的测试)/注：与signal不同，这里要进行重新判断；/通过检查（资源够用）时的处理；进程P进入就绪队列;else/未通过检查（资源不够用）时的处理；进程P进入某等待队列；,60,2.一般“信号量集”,一次需要N个某类临界资源时，就要进行N次wait操作低效又可能死锁基本思想：在AND型信号量集的基础上进行扩充：进程对信号量 Si 的测试值为 ti（用于信号量的判断，即 Si ti，表示资源数量低于ti时，便不予分配），占用值为 di（用于信号量的增减，即Si=Si-di和Si=Si+di）Swait(S1,t1,d1

24、;.;Sn,tn,dn);Ssignal(S1,d1;.;Sn,dn);,一般信号量集用于同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理,61,一般“信号量集”的几种特定情况：Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配；Swait(S,1,1)表示互斥信号量；Swait(S,1,0)作为一个可控开关当S=1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区；一般“信号量集”未必成对使用Swait和Ssignal如：一起申请，但不一起释放；,62,独木桥问题:某一条河上有一座独木桥，有人从北向南过桥，有人自南向北过桥，由于独木桥

25、一次只能承载一人，所以请用信号量设计一种算法，让南北双方都能合理通行。公共汽车问题：在公共汽车上，售票员和司机需要合理配合才能保证运行。设售票员必须等汽车停止才能开门、上客、关门、售票；而司机必须等门关好了才能开车、行驶、到站、停车。现在请你用PV原语操作来同步司机和售票员的工作。,思考题,63,假定一个阅览室最多可同时容纳100个人阅读，读者进入和离开阅览室时，都必须在阅览室门口的一个登记表上登记。假定每次只允许一个人登记和去掉登记，设阅览室内有100个座位。请用P,V原语编写读者进程的同步算法。,64,附：管程(monitor),用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序

26、中，其正确性分析很困难。管程是管理进程间同步的机制，它保证进程互斥地访问共享资源，并方便地阻塞和唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好控制。,65,信号量同步的缺点,同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；,66,管程的引入,这是一种具有面向对象程序

27、设计思想的同步机制。它提供了与信号量机制相同的功能。管程（Monitor）概念是著名学者Hore于1974年提出的，并在很多系统中得到实现，诸如Pascal、Java、Modula-3等。管程是由局部数据结构、多个处理过程和一套初始化代码组成的模块。管程的特征为：（1）管程内的数据结构只能被管程内的过程访问，任何外部访问都是不允许的；（2）进程可通过调用管程的一个过程进入管程；（3）任何时间只允许一个进程进入管程，其他要求进入管程的进程统统被阻塞到等待管程的队列上。,67,下图是管程的一个结构模型,68,l P（c）：当遇到同步约束，就将进程阻塞在条件变量c关联的等待队列上。l V（c）：从条

28、件变量c关联的等待队列上唤醒一个进程，让它恢复运行。若队列上没有进程在等待，就什么也不做。管程的语言结构可描述为下属形式：Type 管程名=Monitor Begin 数据结构定义；局部变量定义；条件变量定义；Porcedure 过程名（形式参数）Begin/过程体 End;End;,69,模块化：一个管程是一个基本程序单位，可以单独编译复合数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码信息封装：管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的,管程的主要特性,70,管程中的共享变量在管程外部是不可见的，外部

29、只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量为了保证管程共享变量的数据完整性，规定管程互斥进入管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作,管程的实现要素,71,Type PC=Monitor Begin Var Char:bufferN;Var Integer:counter,in,out;Var Condition:notfull,notempty;Porcedure PUT（var char:item）Beginif count=N then P(notfull);Bufferin:=item;in:=(in+1)mod N

30、;Count:=count+1;V(notempty);End;,Porcedure GET（char:item）Beginif count=0 then P(notempty);item:=Bufferout;out:=(out+1)mod N;Count:=count-1;V(notfull);End;Begin count,in,out=0,0,0;End;End;,利用管程PC解决生产者-消费者问题,72,Procedure Consumer()Begin Var char:x;While(true)Begin GET(x);Consume_the_item_in_x();End En

31、d;,应用程序算法如下。Procedure Producer()Begin Var char:x;While(true)Begin Produce_an_item_in_x();PUT(x);End;End;,73,管程的优点,管程可增强模块的独立性：系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性引入管程可提高代码的可读性，便于修改和维护，正确性易于保证：采用集中式同步机制。一个操作系统或并发程序由若干个这样的模块所构成，一个模块通常较短，模块之间关系清

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

33、区方式不要求数据移动，可以任意读写和使用任意数据结构，需要进程互斥和同步的辅助来确保数据一致性管道方式消息或邮箱机制消息的发送不需要接收方准备好，随时可发送,77,3.6.2 共享存储器系统 这种通信需要在内存中开辟一个共享的存储空间，供进程之间进行数据传递。比如计算进程将所得的结果送入内存共享区的缓冲区环中，打印进程从中将结果取出来，就是一个利用共享存储器进行通信的例子。这种通信方式在UNIX、Linux、Windows及OS/2等系统中都有具体的实现。共享存储器系统中，共享的空间一般应当是需要互斥访问的临界资源。诸多进程为了避免丢失数据或重复取数，需要执行特定的同步协议。在利用共享存储器进

34、行通信之前，信息的发送者和接收者都要将共享空间纳入到自己的虚地址空间中，让它们都能访问该区域。存储器管理模块将共享空间映射成实际的内存空间。,78,（1）创建或删除共享存储区（2）共享存储区的附接与断接（3）共享存储区状态查询（4）共享存储区管理 共享存储器系统的特点：利用共享存储器系统进行通信的效率特别高，适用于通信速度要求特别高的场合。这种同步与互斥机制的实现一般要由程序员来承担，系统仅仅提供一个共享内存空间的管理机制。,79,Linux的共享存储区,创建或打开共享存储区(shmget)：依据用户给出的整数值key，创建新区或打开现有区，返回一个共享存储区ID。连接共享存储区(shmat)

35、：连接共享存储区到本进程的地址空间，可以指定虚拟地址或由系统分配，返回共享存储区首地址。父进程已连接的共享存储区可被fork创建的子进程继承。拆除共享存储区连接(shmdt)：拆除共享存储区与本进程地址空间的连接。共享存储区控制(shmctl)：对共享存储区进行控制。如：共享存储区的删除需要显式调用shmctl(shmid,IPC_RMID,0)；,80,3.6.3 管道通信,管道（Pipe）是可供进程共享的一种外存文件，主要用于连接一个写入进程和一个读出进程，以实现它们之间的数据通信。写入进程按字符流的形式将数据写入管道文件中，让读出进程从中获得数据。由于管道机制特别适用于大容量数据的通信，

36、因此在许多操作系统中被采用。管道通信机制分为无名管道和有名管道,81,进程通信实例管道(pipe),UNIX最早的消息传递机制是管道，管道是一条在进程间以字节流方式传送的通信通道。管道逻辑是被看作是管道文件，物理上则是由文件系统的高级缓冲区（通常几十KB）来实现，是单向的。在使用管道前要建立相应的管道，然后才可使用。,利用UNIX提供的系统调用pipe，可建立一条同步通信管道。其格式为：pipe(fd)intfd2；这里，fd1 为写入端，fd0为读出端。,82,示例例：用C语言编写一个程序，建立一个pipe，同时父进程生成一个子进程，子进程向pipe中写入一字符串，父进程从pipe中读出该字

37、符串。解：程序如下：#include stdio.hmain()intx，fd2；char buf30，s30；pipe(fd)；/*创建管道*/while(x=fork()=-1)；/*创建子进程失败时，循环*/if(x=0),83,sprintf(buf，This is an examplen)；write(fd1，buf，30)；/*把buf中字符写入管道*/exit(0)；else/*父进程返回*/wait(0)；read(fd0，s，30)；/*父进程读管道中字符*/printf(%s，s)；,84,1.Linux 管道,通过pipe系统调用创建无名管道，得到两个文件描述符，分别用于

38、写和读。int pipe(int fildes2);文件描述符fildes0为读端，fildes1为写端；通过系统调用write和read进行管道的写和读；进程间双向通信，通常需要两个管道；只适用于父子进程之间或父进程安排的各个子进程之间；Linux中的命名管道，可通过mknod系统调用建立：指定mode为S_IFIFOint mknod(const char*path,mode_t mode,dev_t dev);,85,2.Windows NT 管道,无名管道：类似于Linux管道，CreatePipe可创建无名管道，得到两个读写句柄；利用ReadFile和WriteFile可进行无名管道

39、的读写；BOOL CreatePipe(PHANDLE hReadPipe,/address of variable for read handle PHANDLE hWritePipe,/address of variable for write handle LPSECURITY_ATTRIBUTES lpPipeAttributes,/pointer to security attributes DWORD nSize/number of bytes reserved for pipe);,86,系统中的进程在交互传送数据时，涉及到对数据结构的互斥使用问题。为实施互斥，进程之间需要同步。

40、提供这些功能的一个好方法是消息传递。还有一个优点是，消息传递可较容易地在单处理机系统、分布式系统、共享存储器的多处理机系统中实现。消息传递中的管理机制由操作系统提供，主要体现为以下两个原语。发送原语：send(destination,message)，其中，destination为消息的目的地（接收进程名）。该原语表示发送消息到进程destination。接收原语：receive(source,message)，其中，source是消息发出地（发送进程名）。该原语表示从进程source接收消息。,3.6.4 消息传递,87,在这种方式中要解决的关键问题仍然是同步问题：仅当一条消息从某个进程发送

41、后，其他进程才可能接收到消息。那么，消息发送者通过send原语发出一条消息后，应当如何处理呢？有两种选择：要么将发送进程阻塞起来，直到消息被接收为止，再把它唤醒；要么不阻塞发送进程。同样地，消息接收者通过receive原语要接收一条消息时，如果能立即收到，可继续运行。如果消息尚未发出的话，也有两种选择：要么阻塞进程等待消息；要么不阻塞进程，放弃接收。这样一来，系统可选择的处理有以下几种：会合（renezvous）方式 宽松同步方式 不阻塞发送者，只阻塞接收者方式,一、实现同步的方法,88,在消息传递中，发送者需要明确消息发往哪里，接收者需要指明消息的来源。通常，按send和receive原语的

42、实现方式可分为直接寻址和间接寻址两类。1.直接寻址（Direct Addressing）实现直接寻址的一个较为简单的方案是，让send原语明确指出接收者的进程号，receive原语明确指出发送者的进程号，系统根据这两个原语实现直接通信。这种一对一的通信，用来处理并发进程之间的合作是相当有效的。2.间接寻址（Indirect Addressing）在间接寻址方式中，消息并不直接从发送进程传到接收进程，而是要经过一个中间介质临时保存消息的队列，通常称为“信箱”。因此，两个通信进程的操作是，一个进程将消息发到信箱中，另一个从信箱中取消息。,二、直接通信和间接通信,89,3.7 线程(THREAD),

43、3.7.1 线程的引入3.7.2 进程和线程的比较3.7.3 线程的执行3.7.4 线程的分类,引入线程的目的是以小的系统开销来提高进程内的并发程度。,90,3.7.1 线程的引入,为提高进程内各个功能模块的并发性传统os：为进程创建一些子孙进程进程：资源分配单位（存储器、文件）和CPU调度（分派）单位，由PCB和进程间上下文确定。由于进程是资源的拥有者，故其在创建、撤销及状态转换时，系统要付出较大的时间和空间开销，从而使得系统中的进程不宜过多，切换频率不宜太高，因此限制了并发程度的提高。为了减少程序并发所付出的时间和空间开销，使os具有更好的并发性，把进程的两个基本属性分开。,91,现代os

44、：一个进程可以创建多个线程线程：“轻量级进程（Lightweight Process）”，是进程的一个实体，使被独立调度和分派的基本单位，表示进程中的一个控制点（执行体），执行一系列指令。,92,进程只作为其他资源分配单位线程作为CPU调度单位只拥有必不可少的资源，如：线程状态、寄存器上下文和栈同样具有就绪、阻塞和执行三种基本状态线程的优点：减小并发执行时的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并发程度。线程的创建时间比进程短线程的终止时间比进程短同进程内的线程切换时间比进程短由于同进程内线程间共享内存和文件资源，可直接进行不通过内核的通信,93,进程与

45、线程的关系,94,线程结构,任一线程有一个独立的栈和一个线程控制块（TCB）。TCB的内容包括：线程标识、优先数，及线程状态、寄存器值、堆栈指针等信息。其中：l 线程状态保存线程的当前状态：运行/阻塞/就绪。l寄存器值保存线程寄存器的上下文。l堆栈指针保存线程的栈指针。,95,下图是多线程环境中的一个进程及其3个线程的模式,96,线程和进程,97,多线程与进程之间的关系,98,线程的使用,字处理程序与用户交互后台排版自动保存数据处理程序输入线程处理线程输出线程,99,3.7.2 进程和线程的比较,地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享调度：线程上下文由于其小而

46、创建、撤销及切换时间比进程上下文切换要快得多并发性：不仅进程之间可并发执行，一个进程中的多个线程之间也可并发执行，从而os具有更好的并发行。切换：同一进程中，线程的切换不会引起进程的切换，只有从一进程中的线程切换到另一进程中的线程时，才会引起进程的切换。,100,3.7.3 线程的执行,线程的状态与操作,线程有 3 个基本状态,即执行、就绪和阻塞。,101,五种基本操作是:(1)派生(spawn):线程在进程内派生出来,它即可由进程派生,也可由线程派生。thread_create(2)阻塞(Block):如果一个线程在执行过程中需要等待某个事件发生,则被阻塞。thread_wait；threa

47、d_yield(3)激活(unblock):如果阻塞线程的事件发生,则该线程被激活并进入就绪队列。(4)调度(schedule):选择一个就绪线程进入执行状态。(5)结束(Finish):如果一个线程执行结束,它的寄存器上下文以及堆栈内容等将被释放。thread_exit,102,3.7.4 线程的分类,OS 对线程的实现方式,103,由内核来维护进程和线程的上下文信息；线程的切换由内核来完成；时间片等额分配给内核线程，所以多内核线程的进程获得更多的CPU时间。,内核线程(kernel-level thread)依赖于OS核心，由内核的内部需求进行创建和撤销，用来执行一个指定的函数。Windo

48、ws NT和OS/2支持内核线程；,好处：一个内核线程发起系统调用而阻塞，不会影响其他线程的运行。,104,用户线程(user-level thread),用户线程的维护由应用进程完成内核不了解用户线程的存在用户线程切换不需要内核特权用户线程调度算法可针对应用优化采用,不依赖于OS核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。调度由应用软件内部进行，通常采用非抢先式和更简单的规则，也无需用户态/核心态切换，所以速度特别快。一个用户线程发起系统调用而阻塞，则其所在的整个进程就在等待。由于时间片等额分配给进程，若进程是多线程则每个线程就慢。,105,采用用户级线程的好

49、处是：管理线程的数据结构都在用户地址空间中，线程的切换不需要内核访问特权。从而减少了在两种模式之间切换的开销。各个应用程序可采用适合自己的专用线程调度算法，比如有的可能采用高优先级调度，而有的可能是简单的循环调度。这些算法仅适应应用程序而不会对内核中的进程调度产生影响。用户级线程可以在各种操作系统中运行，只要装有一个可共享的应用级上的实用程序库线程库就可以了。,106,核心级线程的上下文切换时间要大于用户级线程的上下文切换时间。实现用户级线程不需要操作系统内核的特殊支持，只要有一个能提供线程创建、调度、执行、撤销，以及通信等功能的线程库就行了。,107,作业三(2),什么是线程？试述线程与进程的区别。,