华科电信系操作系统.ppt

1、第五章 并行性：互斥和同步,为了充分利用计算机各部分的能力，使之并行运行以提高计算机系统的效率和性能，计算机界一直在坚持不懈地、不遗余力地发展并行技术。近几十年来，随着多道程序设计、多处理器系统、分布式处理系统技术的发展，操作系统的并行技术不断完善。,掌握 程序顺序执行和并行执行的含义和特点 并行执行的表示方法 临界段的定义、目的、设计原则 同步和互斥的含义、实现方式 信号量机制：信号量定义、物理意义、信号量的使用（互斥、同步、生产者/消费者， 阅读者/写入者等）。 进程通信,多道程序设计基础并行程序设计,并行程序设计 进程间的同步和互斥 同步和互斥的执行工具 同步机构在实际程序设计中的应用

2、进程通信 *管程 *Windows NT中的同步和互斥机制,1、程序的顺序执行,处理机逐条的一次只执行一条指令 主存储块一次只访问一个字或字节 外设一次只能传送一个数据块 传统程序设计方法：顺序程序执行,程序的顺序执行,概念: 一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。 例如：,程序顺序执行的特点,顺序性 处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。 封闭性 程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。 可再现性 程序执行的结

3、果与初始条件有关，而与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。,多道程序环境程序设计思想：并行程序设计,例：在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi (i=1,2,3,.,n)。 这些作业系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。,例如: I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2,I3与P1是可以同时执行的。,程序并行执行 （定义） 若干个程序段同时在系统中运行，这些程序的执行在时间

4、上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并行执行的。,程序并行性的表示之一：有向图,程序并行性的表示之二：并行语言,并行语言：并行PASCAL，CSP/K语言，MODULA语言，扩充的Ada等. 并行语句记号: cobegin S1;S2;S3;.;SN coend; Si(i=1,2,3,.,n)表示n个语句（程序段），这n个语句用cobegin和coend括起来表示这n个语句是可以并发执行的。co是concurrent的头两个字符。 有的书用parbegin和parend表示。 Si: 简单语句，复合语句，并行语句。 编译程

5、序为每个并行语句Si设置一个进程。,程序并行性表示举例,假设有一个程序由 S0Sn+1个语句， 其中 S1Sn语句是并发执行的。 程序如下： S0; cobegin S1;S2;S3;.;SN coend; Sn+1;,程序并行性表示举例,+,*,*,/,-,-,BEGIN COBEGIN t1=a-b t2=c-d t3=e/f COEND COBEGIN t4=t1*t2 t5=t3*2 COEND t6=t4+t5 END,算数表达式求值: (a-b)*(c-d)+(e/f)*2,a b c d e f,2,并行程序设计的特点,并行、异步的在系统内运行 共享各类资源，彼此相互制约 只有在

6、严格遵循并行程序设计的原则下，程序运行的结果才是确定的，否则，可能产生意料不到的情况,并发执行实例：誊抄,一个循环程序顺序执行的誊抄 算法1： 输入：f 输出：g while (f 不为空） input ; output ; 由这个程序完成誊抄工作是不会出错的。,并发执行实例：誊抄,两个程序并发执行完成誊抄 设有一台标准输入设备（键盘），和一台标准输出设备（显示器或打印机），输入程序负责从标准设备中读取一个字符，送缓冲区中。输出程序从缓冲区中取数据，送标准设备输出。,并发执行实例：誊抄,算法：2 cobegin f: Begin while (不为结束符）/* 输入程序段 */ input;

7、/* 从标准输入设备读入一个数据 */ write_buf; /* 将读入的数据送到bufferf */ End g: Begin while(buffer不为空） /* 输出程序段 */ read_buf; /* 从bufferf中取数据 */ output; /* 送打印机输出 */ End coend ,并发执行实例：誊抄,这两个程序段并发执行时可能出现如下情况： 1、输出程序运行的速度比输入程序快时，有些输出会重复； 如输入送入了一个字符“A”，输出取出打印“A”，当输入还未送入新的数据，输出程序已执行，又取出“A”打印，这样“A”的输出就重复了，出错。 2、输入程序执行的速度比输出程

8、序快时，有些数据会丢失； 如输入程序送入一个字符“B”，紧接着（当输出程序还未取走字符“B”）又送入字符“N”，这时输出程序取走的是“N”，“B”就丢失了。,并发执行实例：誊抄,三个并发执行程序的誊抄 get程序负责从输入序列f中读取字符并送到缓冲区s中； copy程序把缓冲区s中的数据复制到缓冲区t中去; put程序从缓冲区t中取出数据打印。,若程序错写成： while(誊抄未完成） cobegin copy; put; get; coend ,初始状态： f=(R1,R2,.,Rn) s=() t=() g=() 首先顺序执行了一次 get(s,f), copy(t,s) put(g,t)

9、 f=(R1,R2,.,Rn) s=(R1),t=(R1),g=(R1),然后，copy,put,get三个程序段并发执行，就有六种组合： 1、copy;put;get 导致结果：g=(R1,R1) 2、copy;get;put 导致结果：g=(R1,R1) 3、put;copy;get 导致结果：g=(R1,R1) 4、put;get;copy 导致结果：g=(R1,R1) 5、get;copy;put 导致结果：g=(R1,R2) 6、get;put;copy 导致结果：g=(R1,R1) 这就是与时间有关的错误。,程序并发执行的特点,失去了程序的封闭性 如果程序执行的结果是一个与时间无关

10、的函数，即具有封闭性。 若一个程序的执行可改变另一个程序的变量，象二个并发程序完成誊抄的例子，程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度，在这种情况下就失去了程序的封闭性。,程序并发执行的特点,程序并发执行的相互制约 在多道程序设计的环境下，程序是并发执行的。即系统中有多道程序在“同时”执行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的，也有间接。,3、进程间的同步与互斥,同步：指多个进程因协同合作而发生的一种直接制约关系。进程相互配合，共同完成一个任务。 互斥：指多个进程因竞争共享资源

11、而发生的一种间接制约关系。有许多资源在使用上具有排他性，或者说只能互斥作用，进程间需要互相竞争，才有可能使用这些资源，如打印机等。 互斥也是一种同步。一种特殊的同步。 互斥的概念来自于诸进程对独占使用资源（设备）的竞争，是进程之间的间接制约关系。 同步来源于多个进程的合作，是进程之间的直接制约关系。,临界段的提出,多道程序环境进程之间存在资源共享； 硬件：外设 软件：共享代码段、共享数据结构等； 进程访问共享资源时有约束： 共享资源不支持多进程同时进行读写操作； 共享资源不支持多进程同时访问。 进程间资源访问冲突 共享变量的修改冲突 操作顺序冲突,临界资源：每次只允许一个进程访问的共享资源。

12、临界段：进程中访问临界资源（共享变量）的代码段。 访问同一临界资源的各临界段分散在各有关进程的程序中。,临界段设计原则,互斥性：每次允许一个进程停留在临界段。 有限逗留：进程只能 在临界段内逗留有限时间。 有限等待：进程不能无限期等待在临界段之外。 前进性：临界段外进程不可以阻止其他进程进入临界段。 有空让进：若有多个进程同时要求进入临界段，应在有限的时间内让其中一个进入临界段，不应相互阻塞。 通用性：不能预期和假定进程进展的相对速度以及可用的处理器的数目。（如进程的速度、cpu个数、有无硬件指令支持等）。,互斥的实现方法,临界段就是为了解决互斥资源的访问问题 软件实现 用软件解决方法来解决进

13、程间的同步和互斥有着很大的局限性，并不是很理想。 硬件方法 中断屏蔽方法 硬件指令方法,软件方法,解法1：双标志、先检查,后表态。 标志表示是否已在临界段。 问题：两个进程可能同时进入临界段，违背互斥性原则。 P1 P2 p1 p2 : while flagj do skip : flagi := true,软件方法,解法2：用一个指针表示哪个应进入临界段， 问题：强制两个进程轮流进入临界段，违背前进性原则。 P1让出后，P2使用前， p1不可能在进入 解法3：双标志，先表态，后查看。 问题：可能两个进程都进入不了临界段，违背有空让进。 P1 p2 p1 p2 : flagi := true

14、: while flagj do skip,中断屏蔽法,禁止一切中断发生。 单CPU中，引起进程切换的唯一原因是中断，故单CPU下可行。 缺点： 代价高，影响并发性 不安全，将禁止一切中断权利给了普通用户。 局限性：不适合多CPU，一个进程只能禁止本CPU的中断。,硬件指令方法,思路：一条指令完成读写两个操作 手段：执行硬件指令的CPU封锁内存总线，以禁止其他CPU在该指令完成前访问内存。 两种指令： TS指令和Swap指令,硬件指令方法（续）,TS：test-and-set指令，读出指定标志后把该标志设置为True。 该指令由PASCAL语言描述如下： Function Test-and-S

15、et(var flag:boolean):boolean begin Test-and-Set:=flag; flag : =true end,TS指令的使用： repeat while TS(lock) do skip; 临界段代码； lock： false； 其他代码； forever,硬件指令方法（续）,Swap指令：该指令的功能是交换两个字的内容。 PASCAL语言描述如下： Proceduce Swap(var a,b:boolean) var temp : boolean; begin temp : =a; a:=b; b:=temp; end,swap使用： repeat key

16、 = true; repeat swap(lock,key); until keyfalse； 临界段代码； lock : false; 其他代码； forever,存在的缺点,忙等待：上述硬件指令虽然可以有效的保证进程间互斥，但是进程在临界段中执行时，其他想进入临界段的进程必须不断地检测布尔变量lock的值，这就造成了处理机时的浪费，通常称这种情况为“忙等待”。 饥饿：由于采用随机从等待队列中选取进程，会出现有的进程一直处于等待。 需CPU支持,硬件指令方法的优点,不但适用于单处理器情况，而且适用于共享主存的SMP多处理器情况（即对称多处理器）； 方法简单，行而有效； 可以被使用于多重临界段

17、情况，每个临界段可以定义自己的共享变量。,4、信号量,用软件和硬件的方法来解决互斥的问题，都存在一定的缺点，荷兰著名的计算机科学家Dijkstra，于1965年提出了一个同步机构，称之为信号量。其基本原则是在多个相互合作的进程之间使用相同的信号来同步，一个进程强制的被停止在一个特定的地方直到收到一个专门的信号，这个信号也就是信号量。,信号量定义,除初始化外，仅能由两个同步原语对其进行操作的整型变量。 两个同步原语分别成为wait和signal（也称为P和V）。 类型： 二元信号量：信号量的值仅允许取0或1，主要用于互斥变量。 一般信号量：信号量取值允许为非负整数，主要用于进程间的一般同步。 在

18、实际操作系统中，一般情况下是由机器硬件提供Wait、signal操作的指令，当然是原子操作，若机器不提供wait、signal操作的指令，则操作系统提供Wait、Signal操作原语。,同步原语,作为OS核心代码的一部分，其执行不受进程调度和执行的打断。 进程的等待方式可以分为 阻塞等待方式和忙等待方式 在不同的等待方式下，Wait和signal操作实现的方式略有不同。,Wait操作,阻塞等待方式 S:=S-1 若S=0 则进程继续执行其他代码 若S0 则 S:=S-1,signal操作,阻塞等待方式 S:=S+1 若S0 则进程继续执行其他代码 若S=0 则从该信号量等待队列中移出第一个进程

19、，使其变为就绪状态，然后返回原进程继续执行其他代码 忙等待方式 S:=S1,硬件指令实现互斥的同步原语,Wait(S): While TS(lock) do skip /上锁 While S=0 do skip; /同步原语代码 S: =S-1; lock : =false; /开锁 Signals(S): While TS(lock) do skip /上锁 S: =S+1; /同步原语代码 lock : =false; /开锁,信号量的数据结构,整型：忙等待方式 记录型结构：阻塞等待方式 type SemaphoreRecord value:integer L: point to PCB

20、end,两种比较方式的比较,阻塞等待： 信号量采用记录型数据结构 实现复杂，须操作就绪队列和阻塞队列 进程间开销大 忙等待： 信号量采用整型 实现简单 可减少进程间开关开销 CPU资源浪费,信号量的物理意义,信号量S的初值表示可用资源数 当S0时，S的值表示还剩可用资源数 当S0，意味着有资源可以申请，操作后，S=S-1意味着资源减少 Signal操作：释放资源，执行Signal操作之后，S=S+1,意味着资源数增加,信号量的物理意义,信号量的变化范围： 设可用资源数为m，进程数为n 忙等待：0=S =m 阻塞等待: -(n-m)=S =m,P4,P1,P2,P3,就绪队列,运行,等待队列,例

21、：4个进程共享2台打印机,S：2 1P1:wait(s) 0 p2:wait(s) -1 p3:wait(s) -2 p4:wait(s) -1p1:signal(s) 0 p2:signal(s) p3:signal(s) p4:signal(s),利用信号量实现互斥,描述：多个进程共享临界资源，并且对资源的访问是互斥的，资源可用单位数为1。,Begin parbegin P1； Pi； Pn； parend end,Pi： Begin Repeat 临界段; 剩余段； forever end,var mutex:Semaphore；,mutex:=1；,wait(mutex);,signa

22、l(mutex);,利用信号量实现互斥,为临界资源设置一个互斥信号量mutex，其初值为1；在每个进程中将临界区代码置于wait(mutex)和signal(mutex)原语之间. 必须成对使用wait和signal原语：遗漏wait原语则不能保证互斥访问，遗漏signal原语则不能在使用临界资源之后将其释放（给其他等待的进程）；wait、signal原语不能次序错误、重复或遗漏.,利用信号量来实现同步,用信号量及wait、signal操作来描述左图 1、说明进程的同步关系 进程P1、P2可并行执行，P3的执行必须等待P1、P2都完成后才能开始执行。 2、设置信号灯，说明含义、初值。 s13

23、= 0 表示进程P1尚未执行完成； s23 = 0 表示进程P2尚未执行完成；,利用信号量来实现同步,程序描述 main() int s13=0;s23=0; parbegin p1; p2; p3; parend; ,P1() signal(s13); P2() . signal(s23); ,P3() wait(s13); wait(s23); . ,共享缓冲区的合作进程的同步,设有一个缓冲区buffer，大小为一个字节， CP进程不断产生字符，送buffer， IOP进程从buffer中取出字符打印。 如不加控制，会有多种打印结果，这取决于这两个进程运行的相对速度。在这众多的打印结果中，

24、只有CP、IOP进程的运行刚好匹配的一种是对的，其它均为错误，并且不能重现。,要保证打印结果的正确，CP、IOP必须遵循以下同步规则: 当CP把结果送入buffer后，IOP才能从buffer中取，否则IOP必须等待； 当IOP从buffer中取走数据后，CP才能将新产生数据送buffer，否则也必须等待。,解决这个问题的步骤： 分析问题，弄清楚同步关系，如上分析； 设置信号量，说明含义、初值； 写出程序描述。,Main() int sb=1;sa=0; cobegin CP(); IOP(); coend ,Sb 表示buffer是否有空位存放数据，初值为1表示可以存放一个数据。 Sa表示是

25、否有数据打印，初值为0，表示没有数据供打印。,CP() while(计算未完） 获得一个计算结果； wait(sb); 将数据放入buffer； signal(sa); ,IOP() while(打印未完） wait(sa); 从buffer中取数据； signal(sb); 打印； ,生产者、消费者问题,定义：指若干进程通过有限的共享缓冲区交换数据时，对缓冲区资源的使用问题。 生产者：向共享缓冲区写入数据的进程。 消费者：从共享缓冲区读取数据的进程。,生产者、消费者问题,描述： 若共享区为n个，可将这n个缓冲区视为共享资源。 任何时刻，一个缓存区只允许一个进程对其操作。 缓冲区空时，生产者可

26、写入数据（不许写重），否则等待。消费者读取数据后的缓存成为生产者的可用资源。 缓冲区中有数据时，消费者读取数据（不许取重），否则等待。生产者写入数据的缓存成为消费者的可用资源。 生产者和消费者都以异步方式运行，但必须保持同步，即各自只能操作各自的可用资源。,生产者、消费者问题,缓冲池：N个缓冲区 P：一组生产者共用的指向空缓冲区头的指针； C：一组消费者共用的指向满缓冲区头的指针。 互斥操作： 分配空缓冲区和移动指针P; 释放满缓冲区和移动指针C;,满 C P 空,生产者、消费者问题,信号量设置 3个信号量 E：表示空的缓冲区数，初值为n； F：表示满的缓冲区数，初值为0； Mutex：分配缓

27、冲区的互斥信号量，初值为1。,生产者、消费者问题,var E,F: Semaphore； muntex: binary Semaphore; Procedure producer begin repeat wait(E); wait(mutex); “分配空缓冲区并调整指针P的临界段”； Signal(mutex); “向缓冲区中装入数据”； Signal(F); forever end,生产者、消费者问题,Procedure Consumers begin repeat wait(F); wait(mutex); “分配满缓冲区并调整指针C的临界段”； signal(mutex); “从缓冲

28、区中取出数据”； signal(E); forever end,生产者、消费者问题,Main（） begin F:=0; E:=n; mutex:= 1; cobegin Producer 1; Producer 2; Producer n; Consumer1; Consumer2; Consumer m; coend end,生产者、消费者问题,特点 Wait次序不能颠倒，否则会出现死锁 当E0，Fn时， P：wait（mutex）-p:wait(E)- S:wait(mutex)-S:wait(F) 当En，F0时， S：wait（mutex）-S:wait(F)- P:wait(mut

29、ex)-P:wait(E) 生产者和消费者的缓冲指针P、C不能同时移动。即缓冲分配不能同时进行。 可改进：将两个互斥信号量来分别控制对指针P、C的操作。,阅读者、写入者问题,定义：指多个进程对一个共享资源进行读写操作的问题。 阅读者：对共享资源进行读操作的进程。 写入者：对共享资源进行写操作的进程 原则： 任何时候写入者最多只允许1个，阅读者可有多个； 对共享资源的读写操作限制关系包括: “读”“写” ：互斥 “写”“写”：互斥 “读”“读”：允许 当无写入者正在访问共享数据集时，阅读者可以进行访问，否则必须等待。 当无阅读者正在访问共享数据集时，写入者可以进行访问，否则必须等待。,阅读者、写

30、入者问题,信号量的考虑： 两个共享资源： Readcount:记录正在读的阅读者人数。 共享数据集 Readcount的访问：对阅读者是互斥的，用mutex作访问的互斥信号量。 共享数据集的访问：对写操作互斥，读写操作互斥，用wrt作访问的互斥信号量。,阅读者、写入者问题,var mutex,wrt:Semaphore; readcount:integer; mutex:=wrt:=1;readcount:=0; parbegin Readeri: beginwait(mutex); readcount:=readcount+1; if readcount=1 then wait(wrt);s

31、ignal(mutex); 读数据集；wait(mutex);readcount:=readcount-1; if readcount=0 then signal(wrt); signal(mutex); end,Writeri: begin wait(wrt);写数据集； signal(wrt); end; parend,阅读者、写入者问题,特点： 某种程度上，阅读者优先，写入者总在所有阅读者完成后才进行。 各阅读者可并发运行。 练习： 读者优先= 写入者优先 两种情形： 1、写入者封锁后来的阅读者； 2、第一个写入者封锁后来的阅读者，并且后来的写入者可以优先于阅读者；,写入优先,Var v

32、,w,r,mutwx,k:semaphore;RC,WC:integer; begin w:=r:=v:=k:=1;RC:=WC:=0; parbegin READER: begin wait(r);wait(v); if RC=0 then wait(w); RC:=RC+1; signal(v);signal(r); 阅读； wait(v); RC:=RC-1; if RC=0 then signal(w); signal(v); end,WRITER: begin wait(k);if WC=0 then wait(r); WC:=WC+1;signal(k); wait(w); 写入；

33、signal(w);wait(k);WC:=WC-1; if WC=0 then signal(r);signal(k); end parend end,哲学家用餐问题,一个典型的进程同步问题。 问题的描述：有五个哲学家，他们的生活是交替地进行思考和就餐。哲学家们共一张圆桌，周围放有五张椅子，每人坐一张。在圆桌上有五个碗和五只筷子，当一个哲学家思考时，他不与同事交谈，饥饿时便试图取左、右最靠近他的筷子，但他可能一支都拿不到。只有在他拿到两支筷子时方能就餐。餐毕，放下筷子继续思考。,一个简单的解法是，用一个信号量表示一支筷子 这五个信号量构成信号量数组，其描述为： var chopstick:

34、array0.4 of semaphore; 所有信号量被初始化为1 ，第i个哲学家的活动可描述为： repeat wait (chopsticki); wait(chopstick (i+1) mod 5 ); . eat; . signal (chopsticki); signal (chopstick(i+1) mod 5); . think; . forever;,上述解法可保证不会有两个相邻的哲学家同时就餐; 但可能引起死锁。假如五个哲学家同时饥饿而拿起各自左边的筷子，使五个信号量chopstick均为0；当他们再试图去拿右边的筷子时，他们都无限期地等待。 死锁问题可采取以下解决方法

35、： 至多只允许四个哲学家同时就餐，以保证至少有一个哲学家可以就餐，最终总会释放出他所用过的筷子，从而可使更多的哲学家就餐； 仅当哲学家的左、右两支筷子均可用时，才允许他拿起筷子就餐； 规定奇数号哲学家先拿起其左边筷子，然后再去拿右边筷子；而偶数号哲学家则相反。 按此规定，1、2号哲学家竞争1号筷子，3、4号哲学家竞争3号筷子，即五个哲学家都先竞争奇数号筷子，获得后，再去竞争偶号筷子，最后总会有某一个哲学家能获得两支筷子而就餐。,睡着的理发师问题,问题描述：在理发馆中，有一个理发师，一张理发椅和n个为等待顾客所设的椅子。如果没有顾客来，理发师就会坐在理发椅上睡觉，当一个顾客来到时，他必须唤醒睡着

36、了的理发师。如果在理发师理发时，又有别的顾客到达，他们要么坐下(如果有空的椅子)，要么离开(如果所有的椅子都被坐满)。用信号量和wait、signal操作写出理发师和顾客行为的程序描述。,5、进程间的通信,进程通信：指进程之间的信息交换。 作业若干个可并行执行的进程协同完成一个工作（同步）进程通信（在进程之间交换一定数量的信息）。 进程通信方式： 低级通信原语：交换信息量较少。如互斥，同步机构。 高级通信原语：交换信息量较多。如直接通信，间接通信。 高级通信原语： 直接通信：一个进程直接发送消息给接受者进程；Send( P, Msg ); Receive( P, Msg ); 间接通信：进程通

37、过一个“信箱”来传递消息。Send( A, Msg ); Receive( A, Msg );,直接通信,要求发送进程和接收进程都以显示的方式提供对方的标识符。通常系统提供两条通信原语。 原语send（P，消息）：把一个消息发送给进程P 原语receive（Q，消息）：从进程Q接收一个消息,消息队列,通常一个进程可以与多个进程通信，即可以向多个进程发送消息，也可以接收来自多个进程的消息。为了便于进程接收和处理这些消息，一般采用消息队列通信机制，将消息组织成消息队列，用链指针链接起来，头指针放在进程的PCB中。,有关数据结构,消息队列 type Msg record MsgSend； MsgSi

38、ze； MsgText； MsgNext； end,PCB中部分数据 type PCB record Msgmq； 首指针 MsgMutex；互斥信号量 MsgSm； 资源信号量 end,发送和接收过程,发送进程在自己地址空间设置一发送区，将发送的消息正文，发送者进程标示符，消息长度填入其中，然后调用发送原语。 发送原语根据发送区的消息长度，申请一缓冲区，将发送区的消息复制到缓冲区中。并获得接收进程的内部标识符，然后将缓冲区挂在接收进程的消息队列上。 接收进程调用接收原语，从自己的消息队列中摘下消息队列中的消息，并将其中的数据复制到指定的消息接收区。,发送区:a,进程A,消息缓冲区,PCB:

39、B,Msgmq,接收区:b,进程B,Receive(A,b),Sender:A,Size:5,Text:Hello,同步机制,信号量： 互斥信号量（mutex）：对消息对列指针的操作 等待信号量（swait）：消息资源数,发送时： wait(mutex); 将消息链入队列； signal（mutex）； signal（swait）；,接收时： wait（swait）； wait(mutex); 从队列中摘取消息； signal（mutex）；,间接通信,进程间发送或接收消息通过一个信箱来进行，消息可以被理解成信件 原语send（A，信件）：把一封信件（消息）传送到信箱A 原语receive（A

40、，信件）：从信箱A接收一封信件（消息）,间接通信的实现,信箱是存放信件的存储区域，每个信箱可以分成信箱特征和信箱体两部分。信箱特征指出信箱容量、信件格式、指针等；信箱体用来存放信件 发送信件：如果指定的信箱未满，则将信件送入信箱中由指针所指示的位置，并释放等待该信箱中信件的等待者；否则发送信件者被置成等待信箱状态 接收信件：如果指定信箱中有信，则取出一封信件，并释放等待信箱的等待者，否则接收信件者被置成等待信箱中信件的状态,6、管道,管道（pipeline）源自“贝尔实验室”开发的Unix,是Unix最具特色的进程通信方式； 也称共享文件方式，基于文件系统，利用一个打开的共享文件实现进程间的相

41、互通信，文件作为缓冲传输介质。 管道是进程间以字节流方式传送的通信通道，通过通常的 IO 接口来存取。创建管道后，通过使用操作系统的任何读或写 IO 系统调用来读或者写它。 管道通常是单向的；常用于命令行所指定的输入输出重定向和管道命令。在使用管道前要建立相应的管道，然后才可使用。 Windows 管道与 Linux 管道的区别： Windows 使用单一句柄（类似于 Linux 文件描述符）支持双向 IO。 Linux 管道返回两个文件描述符来实现双向 IO。,管道具有如下三个突出的特点 发送进程能以比较简单的方式，源源不断地把产生的消息以自然流的方式写入管道，而不需要考虑对每次传送的信息长

42、度的限制。 接收进程能在适当的时机从管道按需提取信息，同样也不必以固定的消息长度为单位进行。 发送和接收进程都能以一定的方式了解对方进程是否存在，并且可以通过管道的现存消息情况（管道空、管道有信息、管道满）等相互协调动作。,7、套接字,套接字（socket）起源于Unix BSD版本，目前已经被Unix和Windows操作系统广泛采用，并支持TCP/IP协议，即支持本机的进程间通信，也支持网络级的进程间通信 双向的，数据格式为字节流（一对一）或报文（多对一，一对多）；主要用于网络通信； 支持client-server模式和peer-to-peer模式，本机或网络中的两个或多个进程进行交互。提供

43、TCP/IP协议支持 UNIX套接字(基于TCP/IP)：send, sendto, recv, recvfrom; 在Windows NT中的规范称为Winsock(与协议独立，或支持多种协议)：WSASend, WSASendto, WSARecv, WSARecvfrom;,8、Windows NT中的同步和互斥机制,NT是多机操作系统,支持对称多处理模式, 同步和互斥由多种机制实现. 内核中的同步和互斥机制：实现多处理器之间的同步. 提高临界段代码执行的中断优先级：实现同一处理机中的互斥； 转锁机制（spin-lock）：用T-S指令实现多处理机间的互斥。,Windows NT中的同步

44、和互斥机制,“等待和信号设置”机制：实现线程之间的同步(即一个线程主动停止执行并等待其他现成执行一些操作)。 进程通信机制: 客户进程与服务器进程间的通信采用交换信息的方式. 小消息通信方法: 少于256bytes(将消息传给与服务器相连的端口对象)； 大消息通信方法: 多于256bytes (将消息指针传给与服务器相连的端口对象,并把消息存放在共享的主存区域中)； 多通信端口机制: 当子系统有多个通信端口时用。,Windows NT同步对象,Mutex对象：互斥对象，相当于互斥信号量，在一个时刻只能被一个线程使用。有关的API： CreateMutex创建一个互斥对象，返回对象句柄； Ope

45、nMutex返回一个已存在的互斥对象的句柄，用于后续访问； ReleaseMutex释放对互斥对象的占用，使之成为可用；,（1） NT支持的三种同步对象,对象名称是由用户给出的字符串。不同进程中用同样的名称来创建或打开对象，从而获得该对象在本进程的句柄。,Semaphore对象：相当于资源信号量，取值在0到指定最大值之间，用于限制并发访问的线程数。有关的API： CreateSemaphore创建一个信号量对象，指定最大值和初值，返回对象句柄； OpenSemaphore返回一个已存在的信号量对象的句柄，用于后续访问； ReleaseSemaphore释放对信号量对象的占用；,Event对象：

46、事件对象，相当于触发器，可通知一个或多个线程某事件的出现。有关的API： CreateEvent创建一个事件对象，返回对象句柄； OpenEvent返回一个已存在的事件对象的句柄，用于后续访问； SetEvent和PulseEvent设置指定事件对象为可用状态； ResetEvent设置指定事件对象为不可用状态（nonsignaled）；手工复位，并唤醒所有等待线程；,（2）同步对象等待,(1) WaitForSingleObject在指定的时间内等待指定对象为可用状态(signaled state)； DWORD WaitForSingleObject( HANDLE hHandle, / handle of object to wait for DWORD dwMilliseconds/ time-out interval in milliseconds ); (2) WaitForMultipleObjects在指定的时间内等待多个对象为可用状态； DWORD WaitForMultipleObjects( DWORD nCount, /对象句柄数组中的句柄数； CONST HANDLE *lpHandles, / 指向对象句