操作系统：04第四章 互斥同步与通讯（2）

《操作系统：04第四章 互斥同步与通讯（2）》由会员分享，可在线阅读，更多相关《操作系统：04第四章 互斥同步与通讯（2）（51页珍藏版）》请在金锄头文库上搜索。

1、4.3.6 会合会合( (Rendezvous) )n背景背景n80年代年代, Ada, Initiated by DOD;nAda 95, (Object-oriented)n会合：两个并发执行流汇集到一处会合：两个并发执行流汇集到一处n并发执行流并发执行流n调用调用n接受接受n均发生，握手，同步。均发生，握手，同步。CR1P1:会合引入背景会合引入背景分布系统分布系统 共享变量共享变量（被动）（被动）CR2P2:共享变量与访问进程在同一存储区，不适合分布环境。共享变量与访问进程在同一存储区，不适合分布环境。PVPV操作问题操作问题操作问题操作问题: :会合引入背景会合引入背景分布系统分布系

2、统共享变量共享变量CR1CR2管程（被动）管程（被动）P1：.P2：.管程与调用进程在同一存储区，不适合分布环境。管程与调用进程在同一存储区，不适合分布环境。管程问题管程问题管程问题管程问题: :会合图示会合图示任务任务task任务任务task任务任务task调用语句调用语句调用语句调用语句接受语句接受语句选择语句选择语句被调用者被调用者代代调用者调用者执行调用代码执行调用代码会合图示会合图示被调用任务被调用任务入口入口1：accept入口入口2：acceptselect.PCBPCB.PCBPCB.调用语句调用语句调用语句调用语句调用任务调用任务入口入口FIFO队列队列Ada同步语句同步语句

3、1. 调用语句调用语句 . 2. 接受语句接受语句 accept doendAccept语句语句If 无调用者无调用者 Then 等待；等待；选取第一个调用者选取第一个调用者会合开始，调用者等待；会合开始，调用者等待；If 有有in参数参数 Then 取取in参数；参数；If 有有 Then 执行之；执行之； If 有有out参数参数 Then 送送out参数；参数；会合结束，调用者继续。会合结束，调用者继续。会合期会合期例子例子-单一资源管理单一资源管理task single_resource is entry acquire; entry return;end single_resourc

4、e;task body single_resource is begin loop accept acquire; accept return; end loop end single_resource;single_resource.acquire; 使用使用single_resource.return;Ada同步语句（同步语句（cont.）3. 选择语句选择语句 select when = or when = else end selectSelect语句语义语句语义计算所有布尔表达式，为真者对应入口标记开放；计算所有布尔表达式，为真者对应入口标记开放；If 无开放的无开放的 Then I

5、f 有有ELSE部分部分 Then 执行之执行之 Else 异常异常; break;If 无被调用的开放的无被调用的开放的 Then If 有有ELSE部分部分 Then 执行之执行之; break; Else 等待等待;任取一开放的被调用的接受语句任取一开放的被调用的接受语句会合开始，调用者等待；会合开始，调用者等待；If 有有in参数参数 Then 取取in参数；参数；If 有有 Then 执行之；执行之； 会会合合期期If 有有out参数参数 Then 送送out参数；参数；会合结束，调用者继续；会合结束，调用者继续；If select语句有语句序列语句有语句序列 Then 执行之。执行

6、之。4.3.6.2 会合例子会合例子-客栈问题客栈问题.explorersbakeryhunter活动：活动：(1)接受猎物接受猎物(2)接受面包接受面包(3)做三明治做三明治(4)给探险家给探险家限制：限制：一份猎物一份猎物一份面包一份面包一份三明治一份三明治一位客人一位客人master客栈客栈问题客栈问题explorer：loop 探探 险险 进客栈进客栈 取三明治取三明治 出客栈出客栈 吃三明治吃三明治end loophunter：loop 狩狩 猎猎 进客栈进客栈 送猎物送猎物 出客栈出客栈end loopbakery：loop 做面包做面包 进客栈进客栈 送面包送面包 出客栈出客栈e

7、nd loop入入口口入入口口入入口口客栈问题客栈问题procedure Adalodge is task type explorer; task hunter; task bakery; task master is entry deliverbread; /面包师送面包面包师送面包 entry delivermeat; /狩猎狩猎者送猎物者送猎物 entry lodge; /探险家取三明治探险家取三明治 end master;客栈问题客栈问题task body explorer is victuals:food; begin loop explore; master.lodge(victu

8、als); /入客栈取三明治入客栈取三明治 eat(victuals) end loop end explorer;客栈问题客栈问题task body hunter is walrus:food; begin loop hunt(walrus); master.delivermeat(walrus) end loop end hunter;task body bakery is rolls:food; begin loop bake(rolls); master.deliverbread(rolls) end loop end bakery;客栈问题客栈问题客栈问题客栈问题task body

9、master is bread, meat, sandwich: food; procedure makesandwich is begin cook(meat); sandwich:=bread+meat; bread:=0; meat:=0; end makesandwich;客栈问题客栈问题 begin bread:=0; meat:=0; sandwich:=0; loop select when bread=0 = accept deliverbread(br: in food) do bread:=br; end deliverbread; or when meat=0 = acc

10、ept delivermeat(mt: in food) do meat:=mt; end delivermeat;客栈问题 or when (sandwich0)or(bread0 and meat0)= accept lodge(snack: out food) do /入店取三明治入店取三明治 if sandwich=0 then makesandwich end if; snack:=sandwich; end lodge; sandwich:=0 /会合期之外会合期之外 else if (bread0)and(meat0)and(sandwich=0) then makesandwi

11、ch end if /栈主人活动 end select end loop end master客栈问题客栈问题 explorers: array(1.numberofexploers)of explorer; begin null; end Adalodge; Bounded buffer problemtask boundedbuffer is entry putin; entry getout;end boundedbuffer;task body boundedbuffer is b: array(0.k-1)of integer; ip, op: 0.k-1; count: integ

12、er; begin ip:=0; op:=0; count:=0;Bounded buffer problem loop select when (count accept putin(item:in integer) do b(ip):=item end putin; ip:=(ip+1)mod k; count:=count+1; Bounded buffer problem or when (count0) = accept getout(item:out integer) do item:=b(op); end getout; op:=(op+1)mod k; count:=count

13、-1; end select end loopend boundedbuffer; 作业作业 #41. 用用Ada语言中的会合解决读者语言中的会合解决读者/写者问题，要求写写者问题，要求写者优先。即编写一个任务，其中有如下四个入口：者优先。即编写一个任务，其中有如下四个入口： start_read; finish_read, start_write, finish_write. 提示：可以使用嵌套的提示：可以使用嵌套的accept语句。语句。读者读者-写者问题写者问题Task readers_writers is entry start_read; entry finish_read; ent

14、ry start_write; entry finish_write;End readers_writes;Task body readers_writers is; Var read_count, write_count: integer; begin read_count:=0; write_count:=0;读者读者-写者问题写者问题 Loop select when write_count=0 = accept start_read do read_count := read_count+1; end start_read or when read_count0 = accept fi

15、nish_read do read_count := read_count-1; end finish_read; or 读者读者-写者问题写者问题 when write_count=0 = accept start_write do while read_count 0 do accept finish_read do read_count:= read_count -1; end finish_read end while end start_write; write_count:=write_count+1; or when write_count0 = accept finish_wr

16、ite do write_count:=write_count-1; end finish_write; end select End loop;End readers_writers读者读者-写者问题写者问题n读者活动:nReaders_writes.start_read;n读操作nReaders_writers.finish_read;n写者活动:nReaders_writers.start_write;n写操作nReaders_writers.finish_write;4.4 进程高级通讯进程高级通讯n进程通讯：进程之间的相互作用。进程通讯：进程之间的相互作用。n低级通讯（简单信号）低级

17、通讯（简单信号）n进程互斥进程互斥n进程同步进程同步n高级通讯（大宗信息）高级通讯（大宗信息）n高级通讯高级通讯nmemory sharing vs. message passingndirect vs. indirectnsymmetric vs. non-symmetricnbuffering vs. non-buffering4.4.1 进程通讯概念进程通讯概念P1 4.4.2 进程通讯模式1. 共享内存模式共享内存模式(shared memory)：2. 消息传递模式消息传递模式(message passing)： P2OS提供：提供：（1）公共内存）公共内存（2）互斥同步机制）互斥同

18、步机制P1P2Msendreceive直接：进程直接：进程-进程进程间接：进程间接：进程-信箱信箱-进程进程4.4.3 直接方式直接方式n对称形式对称形式(sender and receiver name each other)nsend(R,message)nreceive(S,message)Send(R,M).Receive(S,N).S:R:4.4.3 直接方式直接方式receive(pid,N).send(R,M1).send(R,M2).n非对称形式非对称形式(only sender names receiver)nsend(R,message)nreceive(pid,messa

19、ge)C/S modelR:S1:S2:4.4.3.1 有缓冲途径有缓冲途径(消息传递模式消息传递模式,直接方式直接方式,非对称形式非对称形式)PCBsend(R,M)size text PCBreceive(pid,N) M:N:msgmsgmsg.发送者发送者S:接收者接收者R:Message passing, direct,non-symmetric, bufferingSizetextsenderlink载有消息的缓冲：载有消息的缓冲：进程消息队列管理：进程消息队列管理： Var Sm:semaphore; (0) 收取消息前收取消息前：P（Sm）; 消息入队后：消息入队后：V（Sm)

20、;消息队列互斥：消息队列互斥： Var m_mutex:semaphore;(1) P(m_mutex); 入列入列(出列出列)动作动作; V(m_mutex);Buffer pool managementbufbufbuf.Var Sb, b_mutex:semaphore; (k,1)申请：申请：P(Sb); P(b_mutex); 头缓冲出链头缓冲出链; V(b_mutex);释放：释放：P(b_mutex); 缓冲入链头缓冲入链头; V(b_mutex); V(Sb);Head：缓冲池缓冲池发送发送-接收原语接收原语Send(R,M) 根据根据R找接收者；找接收者； P(Sb); P(

21、b_mutex); 取一空取一空buf; V(b_mutex); size,text,sender = buf P(m_mutex); 消息入链尾；消息入链尾； V(m_mutex); V(Sm); Receive(pid,N) P(Sm); P(m_mutex); 头消息出链头消息出链; V(m_mutex); size,text= N sender = pid P(b_mutex); 空空buf入链；入链； V(b_mutex); V(Sb);Remarks：nSend/receive 为高级通讯原语，可用为高级通讯原语，可用低级原语实现；低级原语实现；nSend/receive不是真正意

22、义的原语，可不是真正意义的原语，可以被中断。以被中断。4.4.3.2 无缓冲途径无缓冲途径(消息传递模式消息传递模式,直接方式直接方式,非对称形式非对称形式)n发送发送-接收都发生接收都发生,信息由发送者复制到信息由发送者复制到接收者接收者.nPCB中两个信号灯中两个信号灯, S_m, S_w, 初值初值0.n发送过程发送过程:send(R,M)n根据根据R找到消息接收者找到消息接收者n发送消息进程增发送消息进程增1, 如接收进程等待将其唤醒如接收进程等待将其唤醒, 即执行即执行V(S_m)n等待消息传送完毕等待消息传送完毕, 即执行即执行P(S_w)4.4.3.2 无缓冲途径无缓冲途径n接收

23、过程接收过程:receive(pid,N)n等待消息到达等待消息到达, 即执行即执行P(S_m)n消息由发送进程空间复制到接收进程空间消息由发送进程空间复制到接收进程空间;n唤醒发送消息进程唤醒发送消息进程, 即执行即执行V(S_w)4.4.3.2 无缓冲途径无缓冲途径Send(R,M)Receive(pid, N)M:N:regsendreceiveS_mS_wPCB硬件硬件OS4.4.3.2 无缓冲途径无缓冲途径n优点优点:n节省空间节省空间(不需要不需要buffer)n缺点缺点:n并发性差并发性差: 发送进程需要等待接收进程执行发送进程需要等待接收进程执行receive把信息复制到接收进

24、程空间后才能把信息复制到接收进程空间后才能继续继续.4.4.4 间接方式间接方式MailboxSend_mb(mb,m)Receive_mb(mb,n).multi-sender - multi-receiver;multi-sender - one receiver4.4.4.1 信箱属于操作系统空间信箱属于操作系统空间Type mailbox=record in,out:0.k; s1,s2:semaphore; (k,0) mutex:semaphore; (1) letter:array0.k-1of message; end;Var mb:mailbox;create_mb(mb);

25、 系统调用系统调用delete_mb(mb); 系统调用系统调用信箱通讯信箱通讯Procedure send_mb(var mb:mailbox; m:massage); begin with mb do begin P(s1); /申请空位申请空位 P(mutex); letterin:=m; in:=(in+1)mod k; V(mutex); V(s2) /消息增加一个消息增加一个 end; end;信箱通讯信箱通讯Procedure receive_mb(var mb:mailbox; var n:massage); begin with mb do begin P(s2); /申请消

26、息申请消息 P(mutex); n:=letterout; out:=(out+1)mod k; V(mutex); V(s1) /空位增加一个空位增加一个 end; end;属于操作系统空间的信箱属于操作系统空间的信箱Var mb: mailboxcreate_MBdelete_MBsend_MBreceive_MBcreate_MB(mb)receive_MB(mb,N)delete_MB(mb)N: send_MB(mb,M)M: UNIX进程高级通讯机制进程高级通讯机制Pipe: an unnamed file with two fds, one for write, and the

27、other for read. The size of pipe file is limited to 4 blocks(one block is 512 bytes). int fd2; pipe(fd): 功能：创建一个功能：创建一个pipe文件文件返回：返回：fd0: 读描述符；读描述符； fd1: 写写描述符。描述符。pipe可以被子进程继承可以被子进程继承子进程子进程1： write(fd1,buf1,count1);子进程子进程2： read(fd0,buf2,count2)UNIX进程高级通讯机制进程高级通讯机制n速度：速度：npipe作为文件，需要两次作为文件，需要两次IO，但

28、一般不会但一般不会真正执行真正执行IO操作操作:n缓冲与延迟写缓冲与延迟写(delayed write), 写到内存缓冲区写到内存缓冲区, 只要内存资源不紧张只要内存资源不紧张, 缓冲区不另作它用缓冲区不另作它用, 不会不会写到外存写到外存, 读时可在内存缓冲区中得到读时可在内存缓冲区中得到.nPipe文件大小的限制文件大小的限制 (Eg. 2k), 循环使用循环使用, 避免避免缓冲资源紧张缓冲资源紧张.n特点：特点：n基于文件系统实现，与文件统一的界面。基于文件系统实现，与文件统一的界面。UNIX信号通讯机制信号通讯机制struct proc char p_sig; procNPROCstr

29、uct user int u_signalNSIG; n系统调用系统调用signal(sig, func)预置信号处理程序预置信号处理程序nu_signalsig=func;nFunc=0时接收信号进程终时接收信号进程终止自己止自己; nFunc=奇数时忽略奇数时忽略;nFunc=偶数时为处理程序偶数时为处理程序入口入口.n进程初创时继承其父进程信进程初创时继承其父进程信号处理程序号处理程序.n信号发送与接收信号发送与接收n任何时候都可接收任何时候都可接收, 记录在记录在p_sig中中.n处理处理n被调度选中即将由核心态转被调度选中即将由核心态转到目态到目态.(用户处理的中断用户处理的中断)W

30、indows2000/xp的管道的管道1. 无名管道：无名管道：BOOL CreatePipe(PHANDLE hReadPipe, PHANDLE hWritepipe, LPSECURITY_ATTRIBUTES lpPipeAt, DWORD nSize)2. 命名管道：命名管道：服务器端：服务器端：.pipePipeName;客户端：客户端：serverNamepipePipeNameCreateNamedPipe: 在服务器端建立管道；在服务器端建立管道；ConnectNamedPipe: 在服务器端等待客户在服务器端等待客户连接连接请求；请求；CallNamedPipe: 客户进程建立与服务器管道连接；客户进程建立与服务器管道连接；ReadFile, WriteFile: 管道读写。管道读写。Windows2000/xp的的mailslot服务器端：服务器端：.mailslotpathname客户进程：客户进程：rangemailslotpathname range: 本地或服务器本地或服务器CreatMailslot: 服务器端创建邮件槽；服务器端创建邮件槽；GetMailslotInfo: 服务器查询邮件槽信息；服务器查询邮件槽信息；ReadFile: 服务器读邮件槽；服务器读邮件槽；WriteFile: 客户端发送消息。客户端发送消息。