资源描述
计算机操作系统,杨为民m0304abc,汤子瀛哲凤屏汤小丹编著,2,2.3.2信号量机制,1.整型信号量最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作(AtomicOperation)wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。wait和signal操作可描述为：wait(S):whileS0dono-opS=S-1;signal(S):S=S+1;,3,2.3.2信号量机制,2.记录型信号量在整型信号量机制中的wait操作，只要是信号量S0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：,4,2.3.2信号量机制,typesemaphore=recordvalue:integer;L:listofprocess;end相应地，wait(S)和signal(S)操作可描述为：procedurewait(S)varS:semaphore;beginS.value=S.value-1;ifS.value0thenblock(S,L)endproceduresignal(S)varS:semaphore;beginS.value=S.value+1;ifS.value0thenwakeup(S,L);end,5,2.3.2信号量机制,在记录型信号量机制中，S.value的初值表示系统中某类资源的数目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.value=S.value-1；当S.value0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则。此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value=S.value+1操作表示资源数目加1。若加1后仍是S.value0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。信号量S是一个整数，S大于等于零时代表可供并发进程使用的资源实体数，但S小于零时则表示正在等待使用临界区的进程数。,6,2.3.2信号量机制,3.AND型信号量在两个进程中都要包含两个对Dmutex和Emutex的操作，即processA:processB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若进程A和B按下述次序交替执行wait操作：processA:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex=0processA:wait(Emutex);于是Emutex=-1A阻塞processB:wait(Dmutex);于是Dmutex=-1B阻塞,7,2.3.2信号量机制,AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait(Simultaneouswait)定义如下：,8,2.3.2信号量机制,Swait(S1,S2,Sn)ifSi1andandSn1thenfori=1tondoSi=Si-1;endforelseplacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal(S1,S2,Sn)fori=1tondoSi=Si+1;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.endfor;,9,2.3.2信号量机制,4.信号量集Swait(S1,t1,d1,Sn,tn,dn)ifSit1andandSntnthenfori=1tondoSi=Si-di;endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSitiandsetitsprogramcountertothebeginningoftheSwaitOperation.endifSsignal(S1,d1,Sn,dn)fori=1tondoSi=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueueendfor;,10,2.4经典进程的同步问题,2.4.1生产者消费者问题2.4.2哲学家进餐问题2.4.3读者-写者问题,11,2.4.1生产者消费者问题,前面我们已经对生产者消费者问题(Theproceducer-consumerproblem)做了一些描述，但未考虑进程的互斥与同步问题，因而造成了数据Counter的不定性。生产者消费者问题是相互合作的进程关系的一种抽象。在输入时，输入进程是生产者，计算进程是消费者；而在输出时，则计算进程是生产者，而打印进程是消费者，因此，该问题有很大的代表性及实用价值。,12,2.4.1生产者消费者问题,1.利用记录型信号量解决生产者消费者问题假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产者消费者问题可描述如下：,13,2.4.1生产者消费者问题,Varmutex,empty,full:semaphore=1,n,0;buffer:array0,n-1ofitem;in,out:integer=0,0;beginparbeginproceducer:beginrepeatproduceranitemnextp;wait(empty);wait(mutex);buffer(in)=nextp;in=(in+1)modn;signal(mutex);signal(full);untilfalse;end,14,2.4.1生产者消费者问题,consumer:beginrepeatwait(full);wait(mutex);nextc=buffer(out);out=(out+1)modn;signal(mutex);signal(empty);consumertheiteminnextc;untilfalse;endparendend,15,2.4.1生产者消费者问题,在生产者消费者问题中应注意：首先，在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现；其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。例如，wait(empty)在计算进程中，而signal(empty)则在打印进程中，计算进程若因执行wait(empty)而阻塞，则以后将由打印进程将它唤醒；最后，在每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁。,16,2.4.1生产者消费者问题,2.利用AND信号量解决生产者消费者问题Varmutex,empty,full:semaphore=1,n,0;buffer:array0,n-1ofitem;inout:integer=0,0;beginparbeginproducer:beginrepeatproduceaniteminnextp;Swait(empty,mutex);buffer(in)=nextp;in=(in+1)modn;Ssignal(mutex,full);untilfalse;end,17,2.4.1生产者消费者问题,consumer:beginrepeatSwait(full,mutex);nextc=buffer(out);out=(out+1)modn;Ssignal(mutex,empty);consumertheiteminnextc;untilfalse;endparendend,18,2.4.2哲学家进餐问题,1.利用记录型信号量解决哲学家进餐问题经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：Varchopstick:array0,4ofsemaphore;,19,2.4.2哲学家进餐问题,所有信号量均被初始化为1，第i位哲学家的活动可描述为：repeatwait(chopsticki);wait(chopstick(i+1)mod5);eat;signal(chopsticki);signal(chopstick(i+1)mod5);think;untilfalse;,20,2.4.2哲学家进餐问题,可采取以下几种解决方法：(1)至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。(2)仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。(3)规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。,21,2.4.2哲学家进餐问题,2.利用AND信号量机制解决哲学家进餐问题在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。Varchopsiickarray0,4ofsemaphore=(1,1,1,1,1);processirepeatthink;Sswait(chopstick(i+1)mod5,chopsticki);eat;Ssignat(chopstick(i+1)mod5,chopsticki);untilfalse;,22,2.4.3读者-写者问题,1.利用记录型信号量解决读者-写者问题为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。另外，再设置一个整型变量Readcount表示正在读的进程数目。由于只要有一个Reader进程在读，便不允许Writer进程去写。因此，仅当Readcount=0,表示尚无Reader进程在读时，Reader进程才需要执行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader进程便可去读，相应地，做Readcount+1操作。同理，仅当Reader进程在执行了Readcount减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让Writer进程写。又因为Readcount是一个可被多个Reader进程访问的临界资源，因此，应该为它设置一个互斥信号量rmutex。,23,2.4.3读者-写者问题,读者-写者问题可描述如下：Varrmutex,wmutex:semaphore=1,1;Readcount:integer=0;beginparbeginReader:beginrepeatwait(rmutex);ifreadcount=0thenwait(wmutex);Readcount=Readcount+1;signal(rmutex);performreadoperation;,24,wait(rmutex);readcount=readcount-1;ifreadcount=0thensignal(wmutex);signal(rmutex);untilfalse;endwriter:beginrepeatwait(wmutex);performwriteoperation;signal(wmutex);untilfalse;endparendend,2.4.3读者-写者问题,25,2.4.3读者-写者问题,2.利用信号量集机制解决读者-写者问题VarRNinteger;L,mx:semaphore=RN,1;beginparbeginreader:beginrepeatSwait(L,1,1);Swait(mx,1,0);performreadoperation;,26,2.4.3读者-写者问题,Ssignal(L,1);untilfalse;endwriter:beginrepeatSwait(mx,1,1;L,RN,0);performwriteoperation;Ssignal(mx,1);untilfalse;endparendend,27,1对于生产者一消费者问题，假设缓冲区是无界的，试用信号灯与PV操作给出解法。答：由于是无界缓冲区，所以生产者不会因为得不到缓冲区而被阻塞，不需要对空缓冲区进行管理，可以舍去在有界缓冲区中用来管理空缓冲区的信号量及其PV操作。semaphoremutex_in=1；semaphoremutex_out=1；semaphreproduct=0；intin=0，out=0；生产者活动：消费者活动：while（1）while（1）producenextpreduct；P（product）P（mutex_in）；P（mutex_out）；addtheproducttobufferin；taketheproductfrombufferout；in+；out+；V（mutex_in）；V（mutex_out）；V（product）；,28,14设有一个可以装A、B两种物品的仓库，其容量无限大，但要求仓库中A、B两种物品的数量满足下述不等式：-M=A物品数量-B物品数量=N其中，M和N为正整数。试用信号灯和PV操作描述A、B两种物品的入库过程。答：已知条件-M=A物品数量-B物品数量=N可以拆分成两个不等式，即A物品数量-B物品数量=NB物品数量-A物品数量=M这两个不等式的含义是：仓库中A物品可以比B物品多，但不能超过N个；B物品可以比A物品多，但不能超过M个。semaphorea=n；semaphoreb=m；voidmain（）createprocess（A，）；createprocess（B，）；A物品入库：B物品入库：void（A）void（B）；while（1）while（1）P（a）；P（b）；A物品入库；B物品入库；V（b）；V（a）；,29,18、一座小桥（最多只能承重两个人）横跨南北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。试用信号灯和PV操作写出南、北两岸过桥的同步算法。解：需要三个信号量。load用来控制桥上人数，初值为2，表示桥上最多有2个人；north用来控制北段桥的互斥使用，初值为1；south用来控制南段桥的互斥使用，初值为1。semaphoreload2；semaphorenorth1；semaphresouthl；tosouth（）tonorth（）P（load）；P（load）；P（north）；P（south）；过北段桥；过南段桥；到桥中间；到桥中间；V（north）；V（south）；P（south）；P（north）；过南段桥；过北段桥；到达南岸；到达北岸；V（south）；V（north）；V（load）；V（load）；,30,31,32,33,34,35,11何谓并行？何谓并发？在单处理机系统中下述并行和并发现象哪些可能发生？哪些不会发生？（1）进程与进程之间的并行；（2）进程与进程之间的并发；（3）处理机与设备之间的并行；（4）处理机与通道之间的并行；（5）通道与通道之间的并行；（6）设备与设备之间的并行。,36,答：所谓并行是指同一时刻同时进行，进程并行需要多处理器的支持；所谓并发，是指在一段时间内，多个进程都在向前推进，而在同一时刻，可能只有一个进程在执行，多个过程轮流使用处理器。在单处理机系统中，可能发生的并行和并发现象如下：（1）进程与进程之间的并发。例如，在Windows操作系统中，MP3播放进程和Word字处理进程可以并发执行，这样用户就可以边听音乐边写文章了。（2）处理机与设备之间的并行。例如，当处理机进行科学运算时，打印机可以打印文档。（3）处理机与通道之间的并行，通道程序的执行可与处理机的操作并行。（4）通道与通道之间的并行。通常一个系统中有多个通道，这些通道可以并行地执行相应的通道程序。（5）设备与设备之间的并行。例如，打印机打印文档时，磁带机在输入数据。,37,2什么是进程？进程具有哪些主要特性？比较进程与程序之间的相同点与不同点。答：进程是具有一定独立功能的程序关于一个数据集合的一次运行活动。进程具有以下主要特性：（1）并发性：可以与其他进程一起在宏观上同时向前推进。（2）动态性：进程是执行中的程序。此外，进程的动态性还体现在如下两个方面。首先，进程是动态产生、动态消亡的；其次，在进程的生存期内，其状态处于经常性的动态变化之中。（3）独立性：进程是调度的基本单位，它可以获得处理机并参与并发执行。（4）交往性：进程在运行过程中可能会与其他进程发生直接或间接的相互作用。（5）异步性：每个进程都以其相对独立、不可预知的速度向前推进。（6）结构性：每个进程有一个控制块PCB。,38,进程和程序的相同点：程序是构成进程的组成部分之一，一个进程存在的目的就是执行其所对应的程序，如果没有程序，进程就失去了其存在的意义。进程与程序的不同点：（1）程序是静态的，而进程是动态的。（2）程序可以写在纸上或在某一存储介质上长期保存，而进程具有生存期，创建后存在，撤销后消亡。（3）一个程序可以对应多个进程，但一个进程只能对应一个程序。例如，一组学生在一个分时系统中做C语言实习，他们都需要使用C语言的编译程序对其源程序进行编译，为此每个学生都需要有一个进程，这些进程都运行C语言的编译程序。另外，一个程序的多次执行也分别对应不同的进程。,39,6有几种类型进程队列？每类各应设置几个队列？答：通常，系统中的进程队列分为如下三类：（1）就绪队列：整个系统一个。所有处于就绪状态的进程按照某种组织方式排在这一队列中，进程入队列和出队列的次序与处理机调度算法有关。在某些系统中，就绪队列可能有多个，用以对就绪进程分类，以方便某种调度策略的实施。（2）等待队列：每个等待事件一个。当进程等待某一事件时，进入与该事件相关的等待队列中；当某事件发生时，与该事件相关的一个或多个进程离开相应的等待队列，进入就结队列。（3）运行队列：在单CPU系统中只有一个，在多CPU系统中每个CPU各有一个。每个队列中只有一个进程，指向运行队列头部的指针被称作运行指示字。,40,12设S1和S2为两个信号灯变量，下列八组P、V操作哪些可以同时进行？哪些不能同时进行？为什么？（1）P（S1），P（S2）；（2）P（S1），V（S2）；（3）V（S1），P（S2）；（4）V（S1），V（S2）；（5）P（S1），P（S1）；（6）P（S2），V（S2）；（7）V（S1），P（S1）；（8）V（S2），V（S2）。答：能同时进行的包括：（1）、（2）、（3）、（4）。这些操作涉及不同的信号灯变量，属于关于不同组共享变量的临界区。不能同时进行的包括：（5）、（6）、（7）、（8）。这些操作涉及相同的信号灯变量，属于关于同一组共享变量的临界区。,41,2.5进程通信,2.6.1进程通信的类型2.6.2消息传递通信的实现方法2.6.3消息传递系统实现中的若干问题2.6.4消息缓冲队列通信机制,42,2.5进程通信,通信（communication）意味着在进程间传送数据。操作系统可以被看作是各种进程组成的。这些进程都具有各自的独立功能，且大多数被外部需要而启动执行。一般来说，进程间的通信根据通信内容可以划分为二种：控制信息的传送与大批量数据传送。有时，也把进程间控制信息的交换称为低级通信，低级通信一般只传送一个或几个字节的信息，以达到控制进程执行速度的作用。把进程间大批量数据的交换称为高级通信。高级通信要传送大量数据。高级通信的目的不是为了控制进程的执行速度，而是为了交换信息。,43,2.5.1进程通信的类型,共享存储器系统(Shared-MemorySystem)消息传递系统(Messagepassingsystem)管道(Pipe)通信,44,2.5.1进程通信的类型,1.共享存储器系统(Shared-MemorySystem)(1)基于共享数据结构的通信方式：诸进程公用数据结构以实现进程间的信息交换；(2)基于共享存储区的通信方式：诸进程通过对共享存储区中数据的读或写实现通信。,45,2.5.1进程通信的类型,2.消息传递系统(Messagepassingsystem)不论是单机系统、多机系统，还是计算机网络，消息传递机制都是用得最广泛的一种进程间通信的机制。在消息传递系统中，进程间的数据交换，是以格式化的消息(message)为单位的；在计算机网络中，又把message称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。操作系统隐藏了通信的实现细节，大大减化了通信程序编制的复杂性，而获得广泛的应用。消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成直接通信方式和间接通信方式两种。,46,2.5.1进程通信的类型,3.管道(Pipe)通信所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)，以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。由于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中。,47,2.5.1进程通信的类型,为了协调双方的通信，管道机制必须提供以下三方面的协调能力：互斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。同步，指当写(输入)进程把一定数量(如4KB)的数据写入pipe，便去睡眠等待，直到读(输出)进程取走数据后，再把他唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。确定对方是否存在，只有确定了对方已存在时，才能进行通信。,48,2.5.2消息传递通信的实现方法,1.直接通信方式这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。通常，系统提供下述两条通信命令(原语)：Send(Receiver,message);发送一个消息给接收进程；Receive(Sender,message);接收Sender发来的消息；例如，原语Send(P2,m1)表示将消息m1发送给接收进程P2;而原语Receive(P1，m1)则表示接收由P1发来的消息m1。,49,2.5.2消息传递通信的实现方法,在某些情况下，接收进程可与多个发送进程通信，因此，它不可能事先指定发送进程。例如，用于提供打印服务的进程，它可以接收来自任何一个进程的“打印请求”消息。对于这样的应用，在接收进程接收消息的原语中的源进程参数，是完成通信后的返回值，接收原语可表示为：Receive(id,message);,50,2.5.2消息传递通信的实现方法,我们还可以利用直接通信原语，来解决生产者-消费者问题。当生产者生产出一个产品(消息)后，便用Send原语将消息发送给消费者进程；而消费者进程则利用Receive原语来得到一个消息。如果消息尚未生产出来，消费者必须等待，直至生产者进程将消息发送过来。生产者-消费者的通信过程可分别描述如下：repeatproduceaniteminnextp;send(consumer,nextp);untilfalse;repeatreceive(producer,nextc);consumetheiteminnextc;untilfalse;,51,2.5.2消息传递通信的实现方法,2.间接通信方式(1)信箱的创建和撤消。进程可利用信箱创建原语来建立一个新信箱。创建者进程应给出信箱名字、信箱属性(公用、私用或共享)；对于共享信箱，还应给出共享者的名字。当进程不再需要读信箱时，可用信箱撤消原语将之撤消。(2)消息的发送和接收。当进程之间要利用信箱进行通信时，必须使用共享信箱，并利用系统提供的下述通信原语进行通信。Send(mailbox,message);将一个消息发送到指定信箱Receive(mailbox,message);从指定信箱中接收一个消息,52,2.5.2消息传递通信的实现方法,信箱可由操作系统创建，也可由用户进程创建，创建者是信箱的拥有者。据此，可把信箱分为以下三类。1)私用信箱用户进程可为自己建立一个新信箱，并作为该进程的一部分。信箱的拥有者有权从信箱中读取消息，其他用户则只能将自己构成的消息发送到该信箱中。这种私用信箱可采用单向通信链路的信箱来实现。当拥有该信箱的进程结束时，信箱也随之消失。,53,2.5.2消息传递通信的实现方法,2)公用信箱它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息。显然，公用信箱应采用双向通信链路的信箱来实现。通常，公用信箱在系统运行期间始终存在。3)共享信箱它由某进程创建，在创建时或创建后，指明它是可共享的，同时须指出共享进程(用户)的名字。信箱的拥有者和共享者，都有权从信箱中取走发送给自己的消息。,54,2.5.2消息传递通信的实现方法,在利用信箱通信时，在发送进程和接收进程之间，存在以下四种关系：(1)一对一关系。这时可为发送进程和接收进程建立一条两者专用的通信链路，使两者之间的交互不受其他进程的干扰。(2)多对一关系。允许提供服务的进程与多个用户进程之间进行交互，也称为客户/服务器交互(client/serverinteraction)。(3)一对多关系。允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方式，向接收者(多个)发送消息。(4)多对多关系。允许建立一个公用信箱，让多个进程都能向信箱中投递消息；也可从信箱中取走属于自己的消息。,55,2.5.3消息传递系统实现中的若干问题,1.通信链路(communicationlink)为使在发送进程和接收进程之间能进行通信，必须在两者之间建立一条通信链路。有两种方式建立通信链路。由发送进程在通信之前，用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路；在链路使用完后，也用显式方式拆除链路。这种方式主要用于计算机网络中。发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令(原语)，系统会自动地为之建立一条链路。这种方式主要用于单机系统中。,56,2.5.3消息传递系统实现中的若干问题,根据通信链路的连接方法，又可把通信链路分为两类：点点连接通信链路，这时的一条链路只连接两个结点(进程)；多点连接链路，指用一条链路连接多个(n2)结点(进程)。而根据通信方式的不同，则又可把链路分成两种：单向通信链路，只允许发送进程向接收进程发送消息；双向链路，既允许由进程A向进程B发送消息，也允许进程B同时向进程A发送消息。,57,2.5.3消息传递系统实现中的若干问题,2.消息的格式在某些OS中，消息是采用比较短的定长消息格式，这减少了对消息的处理和存储开销。这种方式可用于办公自动化系统中，为用户提供快速的便笺式通信；但这对要发送较长消息的用户是不方便的。在有的OS中，采用另一种变长的消息格式，即进程所发送消息的长度是可变的。系统在处理和存储变长消息时，须付出更多的开销，但方便了用户。这两种消息格式各有其优缺点，故在很多系统(包括计算机网络)中，是同时都用的。,58,2.5.3消息传递系统实现中的若干问题,3.进程同步方式(1)发送进程阻塞、接收进程阻塞。(2)发送进程不阻塞、接收进程阻塞。(3)发送进程和接收进程均不阻塞。,59,2.5.4消息缓冲队列通信机制,1.消息缓冲队列通信机制中的数据结构(1)消息缓冲区。在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区。它可描述如下：typemessagebuffer=recordsender;发送者进程标识符size;消息长度text;消息正文next;指向下一个消息缓冲区的指针end,60,2.5.4消息缓冲队列通信机制,(2)PCB中有关通信的数据项。在利用消息缓冲队列通信机制时，在设置消息缓冲队列的同时，还应增加用于对消息队列进行操作和实现同步的信号量，并将它们置入进程的PCB中。在PCB中应增加的数据项可描述如下：typeprocesscontrolblock=recordmq;消息队列队首指针mutex;消息队列互斥信号量sm;消息队列资源信号量end,61,2.5.4消息缓冲队列通信机制,2.发送原语发送进程在利用发送原语发送消息之前，应先在自己的内存空间，设置一发送区a，把待发送的消息正文、发送进程标识符、消息长度等信息填入其中，然后调用发送原语，把消息发送给目标(接收)进程。发送原语首先根据发送区a中所设置的消息长度a.size来申请一缓冲区i，接着，把发送区a中的信息复制到缓冲区i中。为了能将i挂在接收进程的消息队列mq上，应先获得接收进程的内部标识符j，然后将i挂在j.mq上。由于该队列属于临界资源，故在执行insert操作的前后，都要执行wait和signal操作。,62,图2-12消息缓冲通信,2.5.4消息缓冲队列通信机制,63,proceduresend(receiver,a)begingetbuf(a.size,i);根据a.size申请缓冲区；i.sender=a.sender;将发送区a中的信息复制到消息缓冲区之中；i.size=a.size;i.text=a.text;i.next=0;getid(PCBset,receiver.j);获得接收进程内部标识符；wait(j.mutex);insert(j.mq,i);将消息缓冲区插入消息队列；signal(j.mutex);signal(j.sm);end,2.5.4消息缓冲队列通信机制,64,2.5.4消息缓冲队列通信机制,3.接收原语接收原语描述如下：procedurereceive(b)beginj=internalname;j为接收进程内部的标识符；wait(j.sm);wait(j.mutex);remove(j.mq,i);将消息队列中第一个消息移出；signal(j.mutex);b.sender=i.sender;将消息缓冲区i中的信息复制到接收区b;b.size=i.size;b.text=i.text;end,
展开阅读全文