华科电信系操作系统.ppt

《华科电信系操作系统.ppt》由会员分享，可在线阅读，更多相关《华科电信系操作系统.ppt（99页珍藏版）》请在三一办公上搜索。

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:简单语句，复合语句，并行语句。编译程序为每个并行语句Si设置一个进程。,程序并行性表示举例,假

5、设有一个程序由S0Sn+1个语句，其中 S1Sn语句是并发执行的。程序如下：S0;cobegin S1;S2;S3;.;SN coend;Sn+1;,程序并行性表示举例,+,*,*,/,-,-,BEGINCOBEGINt1=a-bt2=c-dt3=e/fCOENDCOBEGINt4=t1*t2t5=t3*2COENDt6=t4+t5END,算数表达式求值:(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;/*从标准输入设备读入一个数据*/write_buf;/*将读入的数据送到bufferf*/End g:Begin while(

7、buffer不为空）/*输出程序段*/read_buf;/*从bufferf中取数据*/output;/*送打印机输出*/End coend,并发执行实例：誊抄,这两个程序段并发执行时可能出现如下情况：1、输出程序运行的速度比输入程序快时，有些输出会重复；如输入送入了一个字符“A”，输出取出打印“A”，当输入还未送入新的数据，输出程序已执行，又取出“A”打印，这样“A”的输出就重复了，出错。2、输入程序执行的速度比输出程序快时，有些数据会丢失；如输入程序送入一个字符“B”，紧接着（当输出程序还未取走字符“B”）又送入字符“N”，这时输出程序取走的是“N”，“B”就丢失了。,并发执行实例：誊抄,

8、三个并发执行程序的誊抄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)f=(R1,R2,.,Rn)s=(R1),t=(R1),g=(R1),然后，copy,put,get三个程序段并发执行，就有六种组合：1、copy;put;get 导致结果：g=(R1,R1)2、copy;get

9、;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个数、有无硬件指令支持等）。,互斥的实现方法,临界段就是为了解决互斥资源的访问问题软件实现用软件解决方法来解决进程间的同步和互斥有着很大的局限性，并不是很理想。硬件方法中断屏蔽方法硬件指令方法,软件方法,解法1：双标志、先检查,后表态。标志表示是否已在临界段。问题：两个进程可能同时进入临界段，违背互斥性原则。P1 P2 p1 p2:while flagj do skip:flagi:=t

13、rue,软件方法,解法2：用一个指针表示哪个应进入临界段，问题：强制两个进程轮流进入临界段，违背前进性原则。P1让出后，P2使用前，p1不可能在进入解法3：双标志，先表态，后查看。问题：可能两个进程都进入不了临界段，违背有空让进。P1 p2 p1 p2:flagi:=true:while flagj do skip,中断屏蔽法,禁止一切中断发生。单CPU中，引起进程切换的唯一原因是中断，故单CPU下可行。缺点：代价高，影响并发性不安全，将禁止一切中断权利给了普通用户。局限性：不适合多CPU，一个进程只能禁止本CPU的中断。,硬件指令方法,思路：一条指令完成读写两个操作手段：执行硬件指令的CPU

14、封锁内存总线，以禁止其他CPU在该指令完成前访问内存。两种指令：TS指令和Swap指令,硬件指令方法（续）,TS：test-and-set指令，读出指定标志后把该标志设置为True。该指令由PASCAL语言描述如下：Function Test-and-Set(var flag:boolean):boolean begin Test-and-Set:=flag;flag:=true end,TS指令的使用：repeatwhile TS(lock)do skip;临界段代码；lock：false；其他代码；forever,硬件指令方法（续）,Swap指令：该指令的功能是交换两个字的内容。PASCA

15、L语言描述如下：Proceduce Swap(var a,b:boolean)var temp:boolean;begin temp:=a;a:=b;b:=temp;end,swap使用：repeatkey=true;repeatswap(lock,key);until keyfalse；临界段代码；lock:false;其他代码；forever,存在的缺点,忙等待：上述硬件指令虽然可以有效的保证进程间互斥，但是进程在临界段中执行时，其他想进入临界段的进程必须不断地检测布尔变量lock的值，这就造成了处理机时的浪费，通常称这种情况为“忙等待”。饥饿：由于采用随机从等待队列中选取进程，会出现有的

16、进程一直处于等待。需CPU支持,硬件指令方法的优点,不但适用于单处理器情况，而且适用于共享主存的SMP多处理器情况（即对称多处理器）；方法简单，行而有效；可以被使用于多重临界段情况，每个临界段可以定义自己的共享变量。,4、信号量,用软件和硬件的方法来解决互斥的问题，都存在一定的缺点，荷兰著名的计算机科学家Dijkstra，于1965年提出了一个同步机构，称之为信号量。其基本原则是在多个相互合作的进程之间使用相同的信号来同步，一个进程强制的被停止在一个特定的地方直到收到一个专门的信号，这个信号也就是信号量。,信号量定义,除初始化外，仅能由两个同步原语对其进行操作的整型变量。两个同步原语分别成为w

17、ait和signal（也称为P和V）。类型：二元信号量：信号量的值仅允许取0或1，主要用于互斥变量。一般信号量：信号量取值允许为非负整数，主要用于进程间的一般同步。在实际操作系统中，一般情况下是由机器硬件提供Wait、signal操作的指令，当然是原子操作，若机器不提供wait、signal操作的指令，则操作系统提供Wait、Signal操作原语。,同步原语,作为OS核心代码的一部分，其执行不受进程调度和执行的打断。进程的等待方式可以分为阻塞等待方式和忙等待方式在不同的等待方式下，Wait和signal操作实现的方式略有不同。,Wait操作,阻塞等待方式S:=S-1若S=0 则进程继续执行其他

18、代码若S0 则 S:=S-1,signal操作,阻塞等待方式S:=S+1若S0 则进程继续执行其他代码若S=0 则从该信号量等待队列中移出第一个进程，使其变为就绪状态，然后返回原进程继续执行其他代码忙等待方式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;/开锁,信号量的数据结构,整型：忙等待方式记录型结构：阻塞等待方

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

20、)=S=m,P4,P1,P2,P3,就绪队列,运行,等待队列,例：4个进程共享2台打印机,S：21P1: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；parendend,Pi：BeginRepeat 临界段;剩余段；foreverend,var mutex:Semaphore；,mutex:=1；,wai

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

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

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

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

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

26、ry Semaphore;Procedure producer begin repeat wait(E);wait(mutex);“分配空缓冲区并调整指针P的临界段”；Signal(mutex);“向缓冲区中装入数据”；Signal(F);forever end,生产者、消费者问题,Procedure Consumersbegin repeat wait(F);wait(mutex);“分配满缓冲区并调整指针C的临界段”；signal(mutex);“从缓冲区中取出数据”；signal(E);forever end,生产者、消费者问题,Main（）beginF:=0;E:=n;mutex:=1

27、;cobeginProducer 1;Producer 2;Producer n;Consumer1;Consumer2;Consumer m;coendend,生产者、消费者问题,特点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(mutex)-P:wait(E)生产者和消费者的缓冲指针P、C不能同时移动。即缓冲分配不能同时进行。可改进：将两个互斥信号量来分别控制对指针P、C的操作。,阅读者、写入者问题,定义：指多个进

28、程对一个共享资源进行读写操作的问题。阅读者：对共享资源进行读操作的进程。写入者：对共享资源进行写操作的进程原则：任何时候写入者最多只允许1个，阅读者可有多个；对共享资源的读写操作限制关系包括:“读”“写”：互斥“写”“写”：互斥“读”“读”：允许当无写入者正在访问共享数据集时，阅读者可以进行访问，否则必须等待。当无阅读者正在访问共享数据集时，写入者可以进行访问，否则必须等待。,阅读者、写入者问题,信号量的考虑：两个共享资源：Readcount:记录正在读的阅读者人数。共享数据集Readcount的访问：对阅读者是互斥的，用mutex作访问的互斥信号量。共享数据集的访问：对写操作互斥，读写操作互

29、斥，用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);signal(mutex);读数据集；wait(mutex);readcount:=readcount-1;if readcount=0 then signal(wrt);signal(mutex);end,Writeri:begin

30、 wait(wrt);写数据集；signal(wrt);end;parend,阅读者、写入者问题,特点：某种程度上，阅读者优先，写入者总在所有阅读者完成后才进行。各阅读者可并发运行。练习：读者优先=写入者优先两种情形：1、写入者封锁后来的阅读者；2、第一个写入者封锁后来的阅读者，并且后来的写入者可以优先于阅读者；,写入优先,Var v,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

31、+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);写入；signal(w);wait(k);WC:=WC-1;if WC=0 then signal(r);signal(k);endparendend,哲学家用餐问题,一个典型的进程同步问题。问题的描述：有五个哲学家，他们的生活是交替地进行思考和就餐。哲学家们共一张圆桌，周围放有五张椅子，每人坐一张。

32、在圆桌上有五个碗和五只筷子，当一个哲学家思考时，他不与同事交谈，饥饿时便试图取左、右最靠近他的筷子，但他可能一支都拿不到。只有在他拿到两支筷子时方能就餐。餐毕，放下筷子继续思考。,一个简单的解法是，用一个信号量表示一支筷子 这五个信号量构成信号量数组，其描述为：var chopstick:array0.4 of semaphore;所有信号量被初始化为1，第i个哲学家的活动可描述为：repeatwait(chopsticki);wait(chopstick(i+1)mod 5);.eat;.signal(chopsticki);signal(chopstick(i+1)mod 5);.thin

33、k;.forever;,上述解法可保证不会有两个相邻的哲学家同时就餐;但可能引起死锁。假如五个哲学家同时饥饿而拿起各自左边的筷子，使五个信号量chopstick均为0；当他们再试图去拿右边的筷子时，他们都无限期地等待。死锁问题可采取以下解决方法：至多只允许四个哲学家同时就餐，以保证至少有一个哲学家可以就餐，最终总会释放出他所用过的筷子，从而可使更多的哲学家就餐；仅当哲学家的左、右两支筷子均可用时，才允许他拿起筷子就餐；规定奇数号哲学家先拿起其左边筷子，然后再去拿右边筷子；而偶数号哲学家则相反。按此规定，1、2号哲学家竞争1号筷子，3、4号哲学家竞争3号筷子，即五个哲学家都先竞争奇数号筷子，获得

34、后，再去竞争偶号筷子，最后总会有某一个哲学家能获得两支筷子而就餐。,睡着的理发师问题,问题描述：在理发馆中，有一个理发师，一张理发椅和n个为等待顾客所设的椅子。如果没有顾客来，理发师就会坐在理发椅上睡觉，当一个顾客来到时，他必须唤醒睡着了的理发师。如果在理发师理发时，又有别的顾客到达，他们要么坐下(如果有空的椅子)，要么离开(如果所有的椅子都被坐满)。用信号量和wait、signal操作写出理发师和顾客行为的程序描述。,5、进程间的通信,进程通信：指进程之间的信息交换。作业若干个可并行执行的进程协同完成一个工作（同步）进程通信（在进程之间交换一定数量的信息）。进程通信方式：低级通信原语：交换信

35、息量较少。如互斥，同步机构。高级通信原语：交换信息量较多。如直接通信，间接通信。高级通信原语：直接通信：一个进程直接发送消息给接受者进程；Send(P,Msg);Receive(P,Msg);间接通信：进程通过一个“信箱”来传递消息。Send(A,Msg);Receive(A,Msg);,直接通信,要求发送进程和接收进程都以显示的方式提供对方的标识符。通常系统提供两条通信原语。原语send（P，消息）：把一个消息发送给进程P原语receive（Q，消息）：从进程Q接收一个消息,消息队列,通常一个进程可以与多个进程通信，即可以向多个进程发送消息，也可以接收来自多个进程的消息。为了便于进程接收和处

36、理这些消息，一般采用消息队列通信机制，将消息组织成消息队列，用链指针链接起来，头指针放在进程的PCB中。,有关数据结构,消息队列type Msg record MsgSend；MsgSize；MsgText；MsgNext；end,PCB中部分数据type PCB record Msgmq；首指针 MsgMutex；互斥信号量 MsgSm；资源信号量 end,发送和接收过程,发送进程在自己地址空间设置一发送区，将发送的消息正文，发送者进程标示符，消息长度填入其中，然后调用发送原语。发送原语根据发送区的消息长度，申请一缓冲区，将发送区的消息复制到缓冲区中。并获得接收进程的内部标识符，然后将缓冲区

37、挂在接收进程的消息队列上。接收进程调用接收原语，从自己的消息队列中摘下消息队列中的消息，并将其中的数据复制到指定的消息接收区。,发送区:a,进程A,消息缓冲区,PCB: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）；,间接

38、通信,进程间发送或接收消息通过一个信箱来进行，消息可以被理解成信件原语send（A，信件）：把一封信件（消息）传送到信箱A原语receive（A，信件）：从信箱A接收一封信件（消息）,间接通信的实现,信箱是存放信件的存储区域，每个信箱可以分成信箱特征和信箱体两部分。信箱特征指出信箱容量、信件格式、指针等；信箱体用来存放信件发送信件：如果指定的信箱未满，则将信件送入信箱中由指针所指示的位置，并释放等待该信箱中信件的等待者；否则发送信件者被置成等待信箱状态接收信件：如果指定信箱中有信，则取出一封信件，并释放等待信箱的等待者，否则接收信件者被置成等待信箱中信件的状态,6、管道,管道（pipeline

39、）源自“贝尔实验室”开发的Unix,是Unix最具特色的进程通信方式；也称共享文件方式，基于文件系统，利用一个打开的共享文件实现进程间的相互通信，文件作为缓冲传输介质。管道是进程间以字节流方式传送的通信通道，通过通常的 IO 接口来存取。创建管道后，通过使用操作系统的任何读或写 IO 系统调用来读或者写它。管道通常是单向的；常用于命令行所指定的输入输出重定向和管道命令。在使用管道前要建立相应的管道，然后才可使用。Windows 管道与 Linux 管道的区别：Windows 使用单一句柄（类似于 Linux 文件描述符）支持双向 IO。Linux 管道返回两个文件描述符来实现双向 IO。,管道

40、具有如下三个突出的特点发送进程能以比较简单的方式，源源不断地把产生的消息以自然流的方式写入管道，而不需要考虑对每次传送的信息长度的限制。接收进程能在适当的时机从管道按需提取信息，同样也不必以固定的消息长度为单位进行。发送和接收进程都能以一定的方式了解对方进程是否存在，并且可以通过管道的现存消息情况（管道空、管道有信息、管道满）等相互协调动作。,7、套接字,套接字（socket）起源于Unix BSD版本，目前已经被Unix和Windows操作系统广泛采用，并支持TCP/IP协议，即支持本机的进程间通信，也支持网络级的进程间通信双向的，数据格式为字节流（一对一）或报文（多对一，一对多）；主要用于

41、网络通信；支持client-server模式和peer-to-peer模式，本机或网络中的两个或多个进程进行交互。提供TCP/IP协议支持UNIX套接字(基于TCP/IP)：send,sendto,recv,recvfrom;在Windows NT中的规范称为Winsock(与协议独立，或支持多种协议)：WSASend,WSASendto,WSARecv,WSARecvfrom;,8、Windows NT中的同步和互斥机制,NT是多机操作系统,支持对称多处理模式,同步和互斥由多种机制实现.内核中的同步和互斥机制：实现多处理器之间的同步.提高临界段代码执行的中断优先级：实现同一处理机中的互斥；转

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

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

44、eSemaphore释放对信号量对象的占用；,Event对象：事件对象，相当于触发器，可通知一个或多个线程某事件的出现。有关的API：CreateEvent创建一个事件对象，返回对象句柄；OpenEvent返回一个已存在的事件对象的句柄，用于后续访问；SetEvent和PulseEvent设置指定事件对象为可用状态；ResetEvent设置指定事件对象为不可用状态（nonsignaled）；手工复位，并唤醒所有等待线程；,（2）同步对象等待,(1)WaitForSingleObject在指定的时间内等待指定对象为可用状态(signaled state)；DWORD WaitForSingleO

45、bject(HANDLE hHandle,/handle of object to wait for DWORD dwMilliseconds/time-out interval in milliseconds);(2)WaitForMultipleObjects在指定的时间内等待多个对象为可用状态；DWORD WaitForMultipleObjects(DWORD nCount,/对象句柄数组中的句柄数；CONST HANDLE*lpHandles,/指向对象句柄数组的指针，数组中可包括多种对象句柄；BOOL bWaitAll,/等待标志：TRUE表示所有对象同时可用，FALSE表示至少一

46、个对象可用；DWORD dwMilliseconds/等待超时时限；);,（3）子进程对同步对象的继承,对象在创建时指定可否被子进程继承，另外还要把对象的句柄通过命令行参数传递给子进程（才能引用该对象）。DuplicateHandle可以将对象句柄复制给指定的另一个进程；BOOL DuplicateHandle(HANDLE hSourceProcessHandle,/被复制对象句柄所在进程的进程对象句柄；HANDLE hSourceHandle,/被复制对象句柄；HANDLE hTargetProcessHandle,/复制后对象句柄所在进程的进程对象句柄；LPHANDLE lpTarget

47、Handle,/指向复制后对象句柄的指针；DWORD dwDesiredAccess,/复制后对象句柄的访问类型，不同类型对象的访问类型会不同；BOOL bInheritHandle,/复制后对象句柄在子进程中的继承方式；DWORD dwOptions/选项；);,（4）其他同步方法,Critical Section对象：只能在同一进程内使用的临界区，同一进程内各线程对它的访问是互斥进行的。把变量说明为CRITICAL_SECTION类型，就可作为临界区使用。有关的API：InitializeCriticalSection对临界区对象进行初始化；EnterCriticalSection等待占用

48、临界区的使用权，得到使用权时返回；TryEnterCriticalSection非等待方式申请临界区的使用权；申请失败时，返回0；LeaveCriticalSection释放临界区的使用权；DeleteCriticalSection释放与临界区对象相关的所有系统资源；,互锁变量访问：相当于硬件指令，对一个整数（进程内的变量或进程间的共享变量）进行操作。其目的是避免线程间切换的影响。有关的API：InterlockedExchange进行32位数据的先读后写原子操作；InterlockedCompareExchange依据比较结果进行赋值的原子操作；InterlockedExchangeAdd先

49、加后存结果的原子操作；InterlockedDecrement先减1后存结果的原子操作；InterlockedIncrement先加1后存结果的原子操作；,Windows NT的文件映射,采用文件映射(file mapping)机制：可以将整个文件映射为进程虚拟地址空间的一部分来加以访问。在CreateFileMapping和OpenFileMapping时可以指定对象名称。CreateFileMapping为指定文件创建一个文件映射对象，返回对象指针；OpenFileMapping打开一个命名的文件映射对象，返回对象指针；MapViewOfFile把文件映射到本进程的地址空间，返回映射地址空间的首地址；这时可利用首地址进行读写；FlushViewOfFile可把映射地址空间的内容写到物理文件中；UnmapViewOfFile拆除文件映射与本进程地址空间间映射关系；随后，可利用CloseHandle关闭文件映射对象；,小结,掌握程序顺序执行和并行执行的含义和特点并行执行的表示方法临界段的定义、目的、设计原则同步和互斥的含义、实现方式信号量机制：信号量定义、物理意义、信号量的使用（互斥、同步、生产者/消费者，阅读者/写入者等）。进程通信,作业5.85.165.185.19,