第二章进程管理

1、第二章 进程管理(1),计算机,操 作 系 统,第二章 进程管理 2.1 前驱图和程序执行,为了更好地描述程序的顺序执行和并发执行情况，引入前驱图的概念。,前趋图是一个有向无循环图，用于描述进程间执行的先后关系。图中的每个结点可以表示一条语句、一个程序段或进程，结点间的有向边或前趋关系(Precedence_Relation)“”。 (|在Pj开始前Pi必须完成如果，可写成PiPj，Pi是Pj的直接前趋，Pj是Pi的直接后继。前趋图中必须不存在循环。,2.1.1 前驱图,P1P2，P1P3，P1P4，P2P5，P3P5，P4P6，P4P7，P5P8，P6P8，P7P9，P8P9,P=P1, P

2、2, P3, P4, P5, P6, P7, P8, P9 =, , , , , , , , , , ,2.1.2 程序的顺序执行及特征,1.程序的顺序执行（只适用于单道程序） 程序段之间的顺序执行 例如：进行计算。I:输入操作 C:计算操作 P:打印操作。 程序语句的顺序执行,S1：a:=x+y； S2：b:=a-5； S3：c:=b+1；,2.程序的顺序执行时的特征,顺序性：一个程序的各个部分的执行，严格地按照某种先后次序执行； 封闭性：程序在封闭的环境下运行，即程序运行时独占全部系统资源； 可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是

3、“停停走走”地执行，都将获得相同的结果。,2.1.3 程序并发执行及特征,1.并发环境 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的,2. 程序的并发执行,在对一批程序进行处理时，可以并发执行。 例如：输入、计算、打印三个程序对一个作业进行处理时执行顺序为：Ii Ci Pi.对一批作业进行处理时，存在以下的前趋关系： IiCi，IiIi+1，CiPi，CiCi+1，PiPi+1,例如：下述四条语句的程序段，其前趋关系图如下： S1: a=x+2 S2: b=y+4 S3: c=a+b S4: d=c+b,3.程序的并发执行的特征,间断性:由

4、于它们共享资源或程序之间相互合作完成一项共同任务，因而使程序之间相互制约。 失去封闭性：程序并发执行时共享资源相互间有影响。 不可再现性：由于程序的并发执行，打破了由另一程序独占系统资源的封闭性，因而破坏了可再现性。(例P35),例子一,进程A、B共享变量 N，初始值为5; 进程A N=N+1; 进程B Print(N) N=0;,按照 执行 N的值 n n+1 0 按照 执行 N的值 n 0 1 按照 执行 N的值 n n+1 0,例子二,进程A . r=N; r=r-1; N=r; .,进程B . r=N; r=r-1; N=r; .,售票进程A、B共享余票数变量N，N的初始值为20;,2

5、.2 进程的描述,2.2.1.进程的定义和特征 1.定义 为了能使程序并发执行，并且可以对并发执行的程序加以描述和控制，人们引入了“进程”的概念。 为了使参与并发的每一个程序都能独立运行，为之配置了一个专门的数据结构进程控制块（Process Control Block,PCB),进程实体：PCB、程序段、数据段 对于进程的定义，从不同的角度可以有不同的定义，其中较典型的定义有： (1) 进程是程序的一次执行。 (2) 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 (3) 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。,2.进程的特征

6、,结构特征：为了控制和管理进程，系统为每个进程设立一个进程控制块PCB。 动态性：进程的实质是程序的一次执行过程， 并发性：任何进程都可以同其他进程一起向前推进 独立性：进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位； 异步性：由于进程间的相互制约，使进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进,3. 进程与程序的区别,程序是静态的，进程是动态的; 进程更能真实地描述并发,而程序不能; 一个程序可对应多个进程，即同一程序段可在不同数据集合上运行，可构成不同的进程。反之亦然，即一个进程可以涉及到一个或几个程序的执行。 进程有生命周期，有诞生有消亡，是短暂

7、的；而程序是相对长久的; 程序可作为软件资源长期保存，进程只是一次执行过程，是暂时的； 进程是系统分配调度的独立单位，能与其他进程并发执行; 从结构上看每个进程实体都含有程序段和相应的数据段两部分，这一特征与程序的含义相近。 进程具有创建其他进程的功能，而程序没有。,2.2.2 进程的基本状态及转换,1. 进程的三种基本状态 就绪状态：进程已获得除CPU以外的所有必要资源。 执行状态：进程正在CPU上运行。 阻塞状态：正在执行的进程因某种事件而暂时无法继续执行。,2.三种基本状态的转换,运行,就绪,阻塞,时间片用完/高优先级抢占,进程调度,等待I/O或其它事件,I/O或其它事件完成,创建状态

8、已为进程分配了PCB，但所需的资源尚不能得到满足，比如系统尚无足够的内存使进程无法装入其中，此时创建工作尚未完成，进程不能被调度运行，于是把此时进程所处的状态称为创建状态。 终止状态 进程结束（自然结束或异常结束）时要进入终止状态。不可调用执行，但在操作系统中保留一份记录。,3.创建状态和终止状态,进程五态模型及其转换,2.2.3. 挂起操作和进程状态的转换,进程挂起的原因： 1终端用户的请求 2父进程的请求 3负荷调节的需要 4操作系统的需要,具有挂起操作的进程状态转换图,图25 具有挂起状态的进程状态演变图,具有创建、终止、挂起的进程状态图,2.2.4.进程管理中的数据结构,进程控制块（P

9、CB）,1、进程控制块的作用 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。 进程与PCB是一一对应的。,进程控制块的作用（续）,(1) 作为独立运行基本单位的标志。 (2) 能实现间断性运行方式。 (3) 提供进程管理所需要的信息。 (4) 提供进程调度所需要的信息。 (5) 实现与其它进程的同步与通信。,2、进程控制块中的信息,1进程标识符 内部标识 外部标识 2处理机状态 通用寄存器 指令计数器 程序状态字 用户堆栈 3进程调度信息,进程控制块中的信息（续）,进程的状态 进程优先级 调度算法 调度事件 4进程控制信息 程序和数据地址 进程同步和通信 资源清单 连

10、接指针 （加）5家族联系：用于说明本进程与其它家族成员间的关系。,3、进程控制块的组织方式,线性方式、链接方式组织PCB (队列)、索引方式。 1）线性方式,2）链接方式组织PCB,3）索引方式,2.3 进程控制,2.3.1 操作系统内核 进程控制是对系统中所有进程从产生、存在到消亡的全过程实行有效的管理和控制。进程控制一般是由操作系统的内核来实现，内核在执行操作时，往往是通过执行各种原语操作来实现的。,内核与原语,原语 是由若干条机器指令构成的完成某种特定功能的一段程序，具有不可分割性。即原语的执行必须是连续的，在执行过程中不允许被中断. 内核的基本功能 支撑功能：中断处理、时钟管理、原语操

11、作 资源管理功能：进程管理、存储器管理、设备管理,进程控制,创建、撤消以及完成进程各状态之间的转换。由具有特定功能的原语完成。 进程创建原语：create 进程撤消原语:exit/terminate 阻塞原语:block 唤醒原语:wakeup 挂起原语:suspend 激活原语:active,2.3.2进程的创建,1、进程的层次结构 在OS中，允许一个进程创建另一个进程，通常把创建进程的进程称为父进程，而把被创建的进程称为子进程。 2、进程图 进程图是一棵有向树(如下图)，用于描述进程间的关系，结点代表进程。一棵树表示一个家族，根结点为该家族的祖先(Ancestor)。,进程图,3、引起创建

12、进程的事件,1用户登录 2作业调度 3请求服务 4应用请求,4、进程创建,使用进程创建原语创建一个具有指定标识符的进程，主要是创建进程控制块PCB。步骤如下： 申请空白PCB，并赋予一个统一进程标识符 分配资源：为进程映象分配空间 初始化进程控制块：初始化标识信息、CPU状态信息、进程状态信息等。 将进程插入就绪队列：设置相应的链接，把新进程加到就绪队列的链表中。,创建原语的实现过程,2.3.3 进程的终止,当一个进程需要结束时，用进程终止原语撤消一个指定的进程，收回进程所占有的资源，撤消该进程的PCB。入口信息是被撤消的进程名。,1、引起进程终止的事件（原因）,1正常结束 2异常结束（越界错

13、、保护错、非法指令、特权指令错、运行超时、等待超时、算术错、I/O故障等） 3外界干预（操作员或操作系统干预、父进程请求、父进程终止）,2、进程的终止过程,1找到要终止进程的PCB，读取进程的状态 2立即终止 3终止其所有子进程 4释放资源 5将PCB移出队列、等待其他进程来搜集信息。,2.3.4 进程阻塞与唤醒,处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态。,1、引起进程阻塞和唤醒的事件,(1) 向系统请求共享资源失败。 (2) 等待某种操作的完成。 (

14、3) 新数据尚未到达。 (4) 等待新任务的到达。,2、进程阻塞过程,1进程停止执行、保存CPU现场 2改变状态 3插入相应阻塞队列 4调度进程重新调度,进程的阻塞原语,阻塞原语的实现过程,3、进程唤醒过程,1从阻塞队列中移出该进程 2改变状态 3插入到就绪队列,2.3.5 进程的挂起与激活,1、进程的挂起 挂起原语的功能 可将自身挂起、或挂起具有指定标识符的进程、或将其全部或部分“子孙”挂起。 进程挂起的过程 1查进程当前状态 2修改状态 3对换进程映像的非常驻部分到外存，将其PCB复制到指定内存区域。,4若被挂起的进程正在执行，则调度程序重新调度,2、进程的激活 激活原语功能 激活指定进程

15、或子进程，使处于静止状态的进程变为活动。 进程激活的过程,1 将进程映像非常驻部分调入内存，并检查进程当前状态 2修改状态 3插入相应的队列 4若采用抢占调度策略，要检查是否需要重新调度。,2.4 进程的同步,问题的引入 在多道程序系统中，由于资源共享或进程合作，使进程间形成间接相互制约和直接相互制约关系，这需要用进程互斥与同步机制来协调两种制约关系。 进程同步的主要任务 是使并发执行的进程间有效的共享资源和相互合作。,2.4.1 进程同步的基本概念,1. 进程间的制约关系 1）间接相互制约关系 2）直接相互制约关系 2.临界资源：在一段时间内只允许一个进程访问的资源（如：打印机、磁带机；共享

16、变量、数据结构和缓冲区） 3.临界区：访问临界资源的那段代码,临界区1,临界区2,临界区n,售票系统（数据库中的票数x,另x=5） r=x r=r-1 x=r 如果不加以控制，会导致错误。 对临界资源的访问要互斥 各进程互斥进入临界区访问临界资源,4.同步机制应遵循的规则（使用临界区的原则）,1)空闲让进 2)忙则等待 3)有限等待 4)让权等待,2.4.2 硬件同步机制 用特殊的硬件指令来实现对临界区的管理，将临界区的标志看做一个锁，初始锁是开的，进入临界区时，测试锁的状态，如果锁未开，则等待直到锁开；否则，如果锁开，立即将其立即锁上，防止其他进程进入临界区 1. 关中断 在进入锁测试之前关

17、闭中断，直到完成锁测试并上锁之后才能打开中断。保证了对锁的测试和关锁操作的连续性和完整性，有效地保证了互斥。,2. 利用Test-and-Set指令实现互斥 这是一种借助一条硬件指令“测试并建立”指令TS(Test-and-Set)以实现互斥的方法。 Boolean TS(Boolean * lock) do . while TS( while(true) ,3. 利用Swap指令实现进程互斥 该指令称为对换指令，在Intel 80 x86中又称为XCHG指令，用于交换两个字的内容。 void Swap(Boolean * a, Boolean *b) key=true; Boolean te

18、mp; do temp=*a; Swap(,2.4.3信号量机制,1. 整型信号量 最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。 wait和signal操作可描述为： wait(S) while (S=1 Remove all the process waiting in the queue associated with Si into the ready queue.,4. 信号量集,对于每类临界资源，每次可以申请或释放多个定义如

19、下：（其中s为信号量，d为需求值，t为下限值） Swait(S1, t1, d1; Sn, tn, dn) if (S=t1 Remove all the process waiting in the queue associated with Si into the ready queue,一般“信号量集”可以用于各种情况的资源分配和释放，有以下几种特殊情况： (1) Swait(S, d, d)。 此时在信号量集中只有一个信号量S，表示每次申请d个资源，当少于d个时，便不分配。 (2) Swait(S, 1, 1)。 此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时

20、)。 (3) Swait(S, 1, 0)。是一种很特殊且很有用的信号量操作。可作为一个可控开关，当S1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区。,2.4.4 信号量的应用,1. 利用信号量实现进程互斥 Semaphore mutex=1; PA() PA() while(1) while(1) wait(mutex); wait(mutex); 临界区； 临界区； signal(mutex); signal(mutex); 剩余区； 剩余区； ,2. 利用信号量实现前趋关系,进程Pi中有语句Ti，进程Pj中有语句Tj，若希望TiTj，则可设一个初值为0的公用信号量S，并

21、将signal(s)操作放在Ti后，而将wait(s)操作放在Tj前，以保证Ti在Tj开始执行之前完成。,Pi Pj Ti wait(s) Signal(s) Tj,思考:,a,b,c,d,e,f,g,p1( )S1; signal(a); signal(b); p2( )wait(a); S2; signal(c); signal(d); p3( ) wait(b); S3; signal(e); p4( ) wait(c); S4; signal(f); p5( ) wait(d); S5; signal(g); p6( ) wait(e); wait(f); wait(g); S6; m

22、ain( ) semaphore a,b,c,d,e,f,g; a.value=0,b.value=0,c.value=0, d.value=0,e.value=0,f.value=0,g.value=0; cobegin p1( );p2( );p3( );p4( );p5( );p6( ); coend ,2.4.5 管程机制 1管程的定义 系统中的各种硬件资源和软件资源均可用数据结构抽象地描述其资源特性。 代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的管理程序共同构成一个操作系统的资源管理模块，称之为管程。,管程由四部分组成： 管程的名称； 局部于管程的共享数据结

23、构说明； 对该数据结构进行操作的一组过程； 对局部于管程的共享数据设置初始值的语句。,2. 条件变量 在利用管程实现进程同步时，必须设置同步工具，如两个同步操作原语wait和signal。 在管程中，因某种原因被阻塞或挂起时，如果不释放管程，则其他进程无法进入管程，被迫长时间等待。因此，需要引入条件变量（condition x)，同时提供x.wait和x.signal,管程的语法如下（P51）： type monitor-name=monitor variable declarations procedure entry P1(); begin end; procedure entry P2(

24、); begin end; procedure entry Pn(); begin end; begin initialization code; end,如果有进程Q处于阻塞状态， 当进程P执行了X.signal操作后，怎样决定由哪个进行执行，哪个等待，可采用下述两种方式之一进行处理： (1) P等待，直至Q离开管程或等待另一条件。 (2) Q等待，直至P离开管程或等待另一条件。 采用哪种处理方式， 当然是各执一词。 但是Hansan却采用了第一种处理方式。,2.5 经典进程的同步问题,2.5.1 生产者消费者问题 生产者消费者问题是相互合作的进程关系的一种抽象，例如， 在输入时，输入进程是

25、生产者，计算进程是消费者；而在输出时，则计算进程是生产者，而打印进程是消费者， 因此，该问题有很大的代表性及实用价值。,1. 利用记录型信号量解决生产者消费者问题,mutex:互斥信号量，初始值为1,full:同步信号量，初始值为0 empty:同步信号量，初始值为n,生产者-消费者问题,P(mutex) P(empty),P(mutex) P(full),semaphore mutex=1, empty=n, full=0; item buffern; int in=0, out=0; void proceducer() do producer an item nextp; wait(emp

26、ty); wait(mutex); buffer(in)=nextp; in=(in+1) % n; signal(mutex); signal(full); while(true); ,void consumer do wait(full); wait(mutex); nextc=buffer(out); out =(out+1) % n; signal(mutex); signal(empty); consumer the item in nextc; while(true); ,2. 利用AND信号量解决生产者消费者问题,semaphore mutex=1, empty=n, full=

27、0;, out=0; void proceducer() do producer an item nextp; wait(empty); wait(mutex); buffer(in)=nextp; in=(in+1) % n; signal(mutex); signal(full); while(true); ,void consumer do wait(full); wait(mutex); nextc=buffer(out); out =(out+1) % n; signal(mutex); signal(empty); consumer the item in nextc; while

28、(true); ,se item buffern; int in=0maphore mutex=1, empty=n, full=0; item buffern; int in=0, out=0; void proceducer() do producer an item nextp; Swait(empty,mutex); buffer(in)=nextp; in=(in+1) % n; Ssignal(mutex,full); while(true); ,void consumer do Swait(full,mutex); nextc=buffer(out); out =(out+1)

29、% n; Ssignal(mutex,empty); consumer the item in nextc; while(true); ,2.5.2 哲学家进餐问题,1. 利用记录型信号量解决哲学家进餐问题 临界资源桌子上的筷子，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下： Semaphore chopstick5=1,1,1,1,1;,第i位哲学家的活动可描述为： do wait(chopsticki); wait(chopstick(i+1) % 5); eat; signal(chopsticki);

30、 signal(chopstick(i+1) % 5); think; while(1),若五位哲学家同时饥饿而各自拿起其左边的筷子，当他们再试图去拿右边的筷子时，都因无筷子拿而阻塞，出现死锁！,为防止死锁发生可采取以下几种解决方法： (1) 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐。 (2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。(AND信号量机制)（） (3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。,2. 利用AND信号量机制解决哲学家进餐问题 在哲学家进餐问题中，要求每个哲学家先获得两个临界资

31、源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。 do Swait(chopsticki, chopstick(i+1) % 5); eat; Ssignal(chopsticki,chopstick(i+1) % 5); think; while(1),2.5.3 读者-写者问题,条件： 1）多个读者可以同时进行读 2）写者必须互斥（只允许一个写者写，也不能让读者与写者同时进行，任一写者执行写操作前应让已有的写者或读者全部退出。） 3）读者优先于写者（一旦有读者，则后续读者都将被允许访问文件。）,1. 利用记录型信号量解决读者-写者问题

32、 1）为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex，初值为1。 2）设置一个整型变量Readcount表示读者的数目，初值为0. 仅当Readcount=0, 表示无读者在读时，读者才需要执行Wait(Wmutex)操作。若wait(Wmutex)操作成功，读者便可去读，相应地，做Readcount+1操作。同理，仅当读者进程在执行了Readcount减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让Writer进程写。 3）因为Readcount是一个可被多个读者进程访问的临界资源，因此，应该为它设置一个互斥信号量rmutex，

33、初值为1.,读者-写者问题可描述如下： Semaphore rmutex=1, wmutex=1; void reader() do wait(rmutex); if (readcount=0)wait(wmutex); Readcount+; signal(rmutex); perform read operation; wait(rmutex); readcount-; if (readcount=0) signal(wmutex); signal(rmutex); while(true),void writer() do wait(wmutex); perform write opera

34、tion; signal(wmutex); while(true); ,2. 利用信号量集机制解决读者-写者问题 (P66),main( ) int RN; Semaphore L=RN, mx=1; Cobegin reader() while(1) Swait(L,1,1); Swait(mx,1,0); perform read operation; Ssignal(L,1); ,writer() while(1) Swait(mx,1,1; L,RN,0); perform write operation; Ssignal(mx,1); ,读者-写者问题：写者优先 条件： 1）多个读者

35、可以同时进行读。 2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）。 3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）。,写者优先,main() Semaphore s =1,sn=n; Cobegin readeri()(i=1,2,.,n) while(1) wait(s); wait(sn); signal(s); . 读文件； signal(sn) ,Writerj()(j=1,2,k) while(1) wait(s); for( i=1;i=n;i+) wait(sn); . 写文件； . for( i=1;i=n;i+) signal(sn);

36、 signal(s) Coend ,同步问题示例一,有4个进程A,B,C,D共享一个缓冲区，进程A负责循环地从文件读一个整数放入缓冲区，进程B从缓冲区取出MOD 3为0的整数并累计求和；进程C从缓冲区取出MOD 3为1的整数并累计求和；进程D从缓冲区取出MOD 3为2的整数并累计求和.请用PV操作写出能够正确执行的程序。,解：semaphore mutex.value=1,S0.value=0, S1.value=0,S2.value=0; int buffer=0,sumA=0,sumB=0,sumC=0,y=0,进程A While（true） 从文件读入一个整数x; Wait(mutex)

37、 Buffer=x; Signal(mutex) If buffer mod 3=0 signal(S0) Else if buffer mod 3 =1) signal(S1) Else signal(S2) ,进程B While（true） Wait(S0); Wait(mutex); y=buffer; Signal(mutex) sumB=sumB+y; ,进程C While（true） Wait(S1); Wait(mutex); y=buffer; Signal(mutex) sumC=sumC+y; ,进程D While（true） Wait(S2); Wait(mutex);

38、y=buffer; Signal(mutex) sumD=sumD+y; ,同步问题示例二,桌子上有一个空盘子，允许存放一只水果，爸爸可以向盘中放苹果，妈妈向盘子中放橘子，女儿专门吃盘子中的苹果，儿子专门吃盘子中的橘子。规定当盘子空的时候一次只能放一只水果，请用信号量实现他们之间的同步与互斥。,解：设置三个信号量S,So,Sa分别表示可否向盘中放水果，可否取桔子，可否取苹果。 初值分别为1，0，0。,Father() while(1) p(S); 将苹果放入盘中; v(Sa); ,Mother() while(1) p(S); 将橘子放入盘中; v(So); ,Son() while(1) p

39、(So) 取桔子 v(S); 吃桔子; ,Daughter() while(1) p(Sa) 取苹果 v(S); 吃苹果; ,练习,1、司机进程正常行车，到站时停车，停车后司机通知售票员，然后售票员打开车门，让乘客下车/上车，完后售票员关车门并通知司机，然后司机正常行车同时售票员售票。 2、桌上有一只盘子，最多可容纳两个水果，每次仅能放入或取出一个水果。爸爸向盘子中放苹果，妈妈向盘子中放桔子。两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。试用信号量和P、V操作来实现爸爸、妈妈、儿子和女儿间的同步与互斥关系。,while(1) 启动车辆 正常驾驶 到站停车 售票员进程： while(1

40、) 关门 售票 开门 ,2.6 进 程 通 信,2.6.1 进程通信的类型,1. 共享存储器系统(Shared-Memory System),基于共享数据结构的通信方式。 (2) 基于共享存储区的通信方式。,2. 管道(Pipe)通信系统 所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。 写进程向管道(共享文件)提供输入的发送进程，信息以字符流的方式写入管道。 读进程接受管道输出的接收进程 首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中。,为了协调双方的通信，管道机制必须提供以下三方面的协调能力： 互斥，即当

41、一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。 同步，指当写(输入)进程把一定数量(如4 KB)的数据写入pipe，便去睡眠等待， 直到读(输出)进程取走数据后，再把他唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。 确定对方是否存在，只有确定了对方已存在时，才能进行通信。,3. 客户机-服务器系统(Client-Server system) 当前主流的通信实现机制 主要实现方法 套接字 远程过程调用 远程方法调用,1) 套接字(Socket),起源于20世纪70年代加州大学伯克利分校版本的UNIX(即BSD Unix) 是UNIX 操

42、作系统下的网络通信接口。 最初用在同一台主机上多个应用程序之间的通信(即进程间的通信)，主要是为了解决多对进程同时通信时端口和物理线路的多路复用问题。 现在，套接字已成为最流行的网络通信程序接口之一。,2) 远程过程调用和远程方法调用 远程过程(函数)调用RPC(Remote Procedure Call)，是一个通信协议，用于通过网络连接的系统。该协议允许运行于一台主机(本地)系统上的进程调用另一台主机(远程)系统上的进程，而对程序员表现为常规的过程调用，无需额外地为此编程。如果涉及的软件采用面向对象编程，那么远程过程调用亦可称做远程方法调用。,实际上，远程过程调用的主要步骤是： (1) 本

43、地过程调用者以一般方式调用远程过程在本地关联的客户存根，传递相应的参数，然后将控制权转移给客户存根； (2) 客户存根执行，完成包括过程名和调用参数等信息的消息建立，将控制权转移给本地客户进程； (3) 本地客户进程完成与服务器的消息传递，将消息发送到远程服务器进程； (4) 远程服务器进程接收消息后转入执行，并根据其中的远程过程名找到对应的服务器存根，将消息转给该存根；,(5) 该服务器存根接到消息后，开始执行，拆开消息从中取出过程调用的参数，然后以一般方式调用服务器上关联的过程； (6) 在服务器端的远程过程运行完毕后，将结果返回给与之关联的服务器存根； (7) 该服务器存根获得控制权运行

44、，将结果打包为消息，并将控制权转移给远程服务器进程； (8) 远程服务器进程将消息发送回客户端； (9) 本地客户进程接收到消息后，根据其中的过程名将消息存入关联的客户存根，再将控制权转移给客户存根； (10) 客户存根从消息中取出结果，返回给本地调用者进程，并完成控制权的转移。,4. 消息传递系统(Message passing system) 应用最广泛的通信方式 进程间的数据交换，是以格式化的消息(message)为单位的； 网络中，又把message称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。 实现方式的不同而进一步分成直接通信方式和间接通信方式两种。,2.6.2

45、消息传递通信的实现方法,1. 直接消息传递系统 1)直接通信原语 (1)对称寻址方式 Send(Receiver, message); 发送一个消息给接收进程； Receive(Sender, message); 接收Sender发来的消息； 例如，原语Send(P2, m1)表示将消息m1发送给接收进程P2; 而原语Receive(P1，m1)则表示接收由P1发来的消息m1。 (2)非对称寻址方式 Send(P, message); 发送一个消息给接收进程； Receive(id, message); 接收任何进程发来的消息；,(2)消息的格式,在单机系统中，消息是采用比较短的定长消息格式，

46、不利于较长消息的用户。 另一种变长的消息格式，即进程所发送消息的长度是可变的。 方便了用户，这两种消息格式各有其优缺点，故在很多系统(包括计算机网络)中，是同时都用的。,（3）进程同步方式,进程间进行通信时，不论是发送进程还是接收进程，在完成消息的发送或接收后，都存在两种可能性，即或者继续发送（接收），或者阻塞。由此可得以下三种情况 (1) 发送进程阻塞、 接收进程阻塞。 (2) 发送进程不阻塞、 接收进程阻塞。 (3) 发送进程和接收进程均不阻塞。,（4）通信链路(communication link) 为使在发送进程和接收进程之间能进行通信，必须在两者之间建立一条通信链路。 两种方式建立通

47、信链路： （1）由发送进程在通信之前，用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路；在链路使用完后，也用显式方式拆除链路。这种方式主要用于计算机网络中。 （2）发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令(原语)，系统会自动地为之建立一条链路。这种方式主要用于单机系统中。,根据通信链路的连接方法，又可把通信链路分为两类： 点点连接通信链路，这时的一条链路只连接两个结点(进程)； 多点连接链路，指用一条链路连接多个(n2)结点(进程)。 而根据通信方式的不同，则又可把链路分成两种： 单向通信链路，只允许发送进程向接收进程发送消息； 双向链路，既允许由进程A向进程

48、B发送消息，也允许进程B同时向进程A发送消息。,2. 信箱通信间接通信,系统为信箱通信提供了若干条原语： (1) 信箱的创建和撤消。进程可利用信箱创建原语来建立一个新信箱。创建者进程应给出信箱名字、信箱属性(公用、私用或共享)；对于共享信箱， 还应给出共享者的名字。当进程不再需要读信箱时，可用信箱撤消原语将之撤消。 (2) 消息的发送和接收。当进程之间要利用信箱进行通信时，必须使用共享信箱，并利用系统提供的下述通信原语进行通信。 Send(mailbox, message); 将一个消息发送到指定信箱； Receive(mailbox, message); 从指定信箱中接收一个消息；,信箱可由

49、操作系统创建，也可由用户进程创建，创建者是信箱的拥有者。据此，可把信箱分为以下三类： 1) 私用信箱 用户进程可为自己建立一个新信箱，并作为该进程的一部分。信箱的拥有者有权从信箱中读取消息，其他用户则只能将自己构成的消息发送到该信箱中。这种私用信箱可采用单向通信链路的信箱来实现。 当拥有该信箱的进程结束时，信箱也随之消失。,2) 公用信箱 它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息。显然，公用信箱应采用双向通信链路的信箱来实现。通常，公用信箱在系统运行期间始终存在。 3) 共享信箱 它由某进程创建，在创建时或创建后，指

50、明它是可共享的，同时须指出共享进程(用户)的名字。信箱的拥有者和共享者，都有权从信箱中取走发送给自己的消息。,在利用信箱通信时，在发送进程和接收进程之间，存在以下四种关系： (1) 一对一关系。这时可为发送进程和接收进程建立一条两者专用的通信链路，使两者之间的交互不受其他进程的干扰。 (2) 多对一关系。允许提供服务的进程与多个用户进程之间进行交互，也称为客户/服务器交互(client/server interaction)。 (3) 一对多关系。允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方式，向接收者(多个)发送消息。 (4) 多对多关系。允许建立一个公用信箱，让多个进程都能

51、向信箱中投递消息；也可从信箱中取走属于自己的消息。,2.6.4 消息缓冲队列通信机制,1. 消息缓冲队列通信机制中的数据结构 (1) 消息缓冲区。在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区。它可描述如下： Typedef struct message buffer sender; 发送者进程标识符 size; 消息长度 text; 消息正文 next; 指向下一个消息缓冲区的指针 ,(2) PCB中有关通信的数据项。在利用消息缓冲队列通信机制时，在设置消息缓冲队列的同时，还应增加用于对进程的消息队列进行操作和实现同步的信号量，并将它们置入进程的PCB中。在PCB中应增加的数据项可描述如下： typedef struct process_control_ block mq; 消息队列队首指针 mutex; 消息队列互斥信号量 sm; 消息队列资源信号量（消息个数） ,图 2 - 12 消息缓冲通信,(2)发送原语 procedure s