04第四章 互斥同步与通讯2VIP

4.3.6会合(Rendezvous),背景80年代,Ada,InitiatedbyDOD;Ada95,(Object-oriented),AugustaAdaLovlace18151852世界上第一位程序设计师原名:AugustaAdaByronLordGeorgeGordenByron的女儿17881824,(Rendezvous),会合：两个并发执行流汇集到一处并发执行流调用接受均发生，握手，同步。,P1:,会合引入背景分布系统,共享变量（被动）Semaphores;,P(S)CR2V(S),P2:,共享变量与访问进程在同一存储区，不适合分布环境。,PV操作问题:,P(S)CR1V(S),P1:,会合引入背景分布系统,共享变量（被动）Semaphores;,P(S)CR2V(S),P2:,共享变量与访问进程在同一存储区，不适合分布环境。,PV操作问题:,P(S)CR1V(S),站点1,站点2,会合引入背景分布系统,管程（被动）,管程与调用进程在同一存储区，不适合分布环境。,管程问题:,会合引入背景分布系统,管程（被动）,管程与调用进程在同一存储区，不适合分布环境。,管程问题:,站点1,站点2,会合图示,被调用者代调用者执行调用代码,会合图示,被调用任务,入口1：accept,入口2：accept,select,.,.,.,PCB,PCB,.,.,.,调用语句,调用语句,调用任务,入口FIFO队列,Ada同步语句,1.调用语句.2.接受语句acceptdoend,Accept语句,有调用者,等待,选取第一个,会合开始调用者等待,有in参数,取in参数,有语句序列,执行之,有out参数,送out参数,会合结束调用者继续,会合期,例子-单一资源管理,tasksingle_resourceisentryacquire;entryreturn;endsingle_resource;,taskbodysingle_resourceisbeginloopacceptacquire;acceptreturn;endloopendsingle_resource;,single_resource.acquire;使用single_resource.return;,Ada同步语句（cont.）,3.选择语句selectwhen=orwhen=elseendselect,4.3.6.1会合的描述(Cont.),F,任取一开放且被调用的,select语句流程,F,T,取in参数,T,执行语句序列,T,送out参数,T,计算所有布尔表达式为真者对应标记开放,有开放的,有else部分,有被调用的开放的,有else部分,等待,F,会合开始，调用者等待,有in参数,有语句序列,F,有out参数,F,执行else部分,T,建立异常条件,F,执行else部分,T,F,会合结束，调用者继续,T,选择语句后有,执行,T,F,4.3.6.2会合例子-客栈问题,.,explorers,bakery,hunter,活动：(1)接受猎物(2)接受面包(3)做三明治(4)给探险家,限制：一份猎物一份面包一份三明治一位客人,master,客栈,客栈问题,explorer：loop探险进客栈取三明治出客栈吃三明治endloop,hunter：loop狩猎进客栈送猎物出客栈endloop,bakery：loop做面包进客栈送面包出客栈endloop,入口,入口,入口,客栈问题,procedureAdalodgeistasktypeexplorer;taskhunter;taskbakery;taskmasterisentrydeliverbread;/面包师送面包entrydelivermeat;/狩猎者送猎物entrylodge;/探险家取三明治endmaster;,客栈问题,taskbodyexplorerisvictuals:food;beginloopexplore;master.lodge(victuals);/入客栈取三明治eat(victuals)endloopendexplorer;,客栈问题,taskbodyhunteriswalrus:food;beginloophunt(walrus);master.delivermeat(walrus)endloopendhunter;,taskbodybakeryisrolls:food;beginloopbake(rolls);master.deliverbread(rolls)endloopendbakery;,客栈问题,客栈问题,taskbodymasterisbread,meat,sandwich:food;proceduremakesandwichisbegincook(meat);sandwich:=bread+meat;bread:=0;meat:=0;endmakesandwich;,客栈问题,beginbread:=0;meat:=0;sandwich:=0;loopselectwhenbread=0=acceptdeliverbread(br:infood)dobread:=br;enddeliverbread;orwhenmeat=0=acceptdelivermeat(mt:infood)domeat:=mt;enddelivermeat;,客栈问题,orwhen(sandwich0)or(bread0andmeat0)=acceptlodge(snack:outfood)do/入店取三明治ifsandwich=0thenmakesandwichendif;snack:=sandwich;endlodge;sandwich:=0/会合期之外elseif(bread0)and(meat0)and(sandwich=0)thenmakesandwichendif/栈主人活动endselectendloopendmaster,客栈问题,explorers:array(1.numberofexploers)ofexplorer;beginnull;endAdalodge;,Boundedbufferproblem,taskboundedbufferisentryputin;entrygetout;endboundedbuffer;taskbodyboundedbufferisb:array(0.k-1)ofinteger;ip,op:0.k-1;count:integer;beginip:=0;op:=0;count:=0;,Boundedbufferproblem,loopselectwhen(countacceptputin(item:ininteger)dob(ip):=itemendputin;ip:=(ip+1)modk;count:=count+1;,Boundedbufferproblem,orwhen(count0)=acceptgetout(item:outinteger)doitem:=b(op);endgetout;op:=(op+1)modk;count:=count-1;endselectendloopendboundedbuffer;,作业#4,1.用Ada语言中的会合解决读者/写者问题，要求写者优先。即编写一个任务，其中有如下四个入口：start_read;finish_read,start_write,finish_write.提示：可以使用嵌套的accept语句。,读者-写者问题,Taskreaders_writersisentrystart_read;entryfinish_read;entrystart_write;entryfinish_write;Endreaders_writes;Taskbodyreaders_writersis;Varread_count,write_count:integer;beginread_count:=0;write_count:=0;,读者-写者问题,Loopselectwhenwrite_count=0=acceptstart_readdoread_count:=read_count+1;endstart_readorwhenread_count0=acceptfinish_readdoread_count:=read_count-1;endfinish_read;or,读者-写者问题,whenwrite_count=0=acceptstart_writedowhileread_count0doacceptfinish_readdoread_count:=read_count-1;endfinish_readendwhileendstart_write;write_count:=write_count+1;orwhenwrite_count0=acceptfinish_writedowrite_count:=write_count-1;endfinish_write;endselectEndloop;Endreaders_writers,读者-写者问题,读者活动:Readers_writers.start_read;读操作Readers_writers.finish_read;写者活动:Readers_writers.start_write;写操作Readers_writers.finish_write;,4.4进程高级通讯,进程通讯：进程之间的相互作用。低级通讯（简单信号）进程互斥进程同步高级通讯（大宗信息）高级通讯memorysharingvs.messagepassingdirectvs.indirectsymmetricvs.non-symmetricbufferingvs.non-buffering,4.4.1进程通讯概念,4.4.2进程通讯模式,1.共享内存模式(sharedmemory)：,2.消息传递模式(messagepassing)：,OS提供：（1）公共内存（2）互斥同步机制,P1,P2,M,send,receive,直接：进程-进程间接：进程-信箱-进程,P1,P2,公共内存,4.4.3直接方式,对称形式(senderandreceivernameeachother)send(R,message)receive(S,message),S:,R:,4.4.3直接方式,receive(pid,N).,send(R,M1).,send(R,M2).,非对称形式(onlysendernamesreceiver)send(R,message)receive(pid,message),C/Smodel,R:,S1:,S2:,4.4.3.1有缓冲途径(消息传递模式,直接方式,非对称形式),PCB,send(R,M)sizetext,PCB,receive(pid,N),M:,N:,msg,msg,msg,.,发送者S:,接收者R:,Messagepassing,direct,non-symmetric,buffering,Sizetextsenderlink,载有消息的缓冲：,进程消息队列管理：VarSm:semaphore;(0)收取消息前：P（Sm）;消息入队后：V（Sm);消息队列互斥：Varm_mutex:semaphore;(1)P(m_mutex);入列(出列)动作;V(m_mutex);,Bufferpoolmanagement,VarSb,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(b_mutex);取一空buf;V(b_mutex);size,text,sender=bufP(m_mutex);消息入链尾；V(m_mutex);V(Sm);,Receive(pid,N)P(Sm);P(m_mutex);头消息出链;V(m_mutex);size,text=Nsender=pidP(b_mutex);空buf入链；V(b_mutex);V(Sb);,Remarks：,Send/receive为高级通讯原语，可用低级原语实现；Send/receive不是真正意义的原语，可以被中断。,4.4.3.2无缓冲途径(消息传递模式,直接方式,非对称形式),发送-接收都发生,信息由发送者复制到接收者.PCB中两个信号灯,S_m,S_w,初值0.S_m:接收进程等待S_w:发送进程等待发送过程:send(R,M)根据R找到消息接收者发送消息进程增1,如接收进程等待将其唤醒,即执行V(S_m)等待消息传送完毕,即执行P(S_w),4.4.3.2无缓冲途径,接收过程:receive(pid,N)等待消息到达,即执行P(S_m)消息由发送进程空间复制到接收进程空间;唤醒发送消息进程,即执行V(S_w),4.4.3.2无缓冲途径,Send(R,M),Receive(pid,N),M:,N:,reg,send,receive,S_mS_w,PCB,硬件,OS,4.4.3.2无缓冲途径,优点:节省空间(不需要buffer)缺点:并发性差:发送进程需要等待接收进程执行receive把信息复制到接收进程空间后才能继续.,4.4.4间接方式,Mailbox,Send_mb(mb,m),Receive_mb(mb,n),multi-sender-multi-receiver;multi-sender-onereceiver,4.4.4.1信箱属于操作系统空间,Typemailbox=recordin,out:0.k;s1,s2:semaphore;(k,0)mutex:semaphore;(1)letter:array0.k-1ofmessage;end;Varmb:mailbox;create_mb(mb);系统调用delete_mb(mb);系统调用,信箱通讯,Proceduresend_mb(varmb:mailbox;m:massage);beginwithmbdobeginP(s1);/申请空位P(mutex);letterin:=m;in:=(in+1)modk;V(mutex);V(s2)/消息增加一个end;end;,信箱通讯,Procedurereceive_mb(varmb:mailbox;varn:massage);beginwithmbdobeginP(s2);/申请消息P(mutex);n:=letterout;out:=(out+1)modk;V(mutex);V(s1)/空位增加一个end;end;,属于操作系统空间的信箱,Varmb:mailbox,create_MB,delete_MB,send_MB,receive_MB,create_MB(mb)receive_MB(mb,N)delete_MB(mb)N:,send_MB(mb,M)M:,UNIX进程高级通讯机制,UNIX进程高级通讯机制,速度：pipe作为文件，需要两次IO，但一般不会真正执行IO操作:缓冲与延迟写(delayedwrite),写到内存缓冲区,只要内存资源不紧张,缓冲区不另作它用,不会写到外存,读时可在内存缓冲区中得到.Pipe文件大小的限制(Eg.2k),循环使用,避免缓冲资源紧张.特点：基于文件系统实现，与文件统一的界面。,UNIX信号通讯机制,structproccharp_sig;procNPROCstructuserintu_signalNSIG;,系统调用signal(sig,func)预置信号处理程序u_signalsig=func;Func=0时接收信号进程终止自己;Func=奇数时忽略;Func=偶数时为处理程序入口.进程初创时继承其父进程信号处理程序.信号发送与接收任何时候都可接收,记录在p_sig中.处理被调度选中即将由核心态转到目态.,(用户处理的中断),Windows2000/xp的管道,1.无名管道：BOOLCreatePipe(PHANDLEhReadPipe,PHANDLEhWritepipe,LPSECURITY_ATTRIBUTESlpPipeAt,DWORDnSize)2.命名管道：服务器端：.pipePipeName;客户端：serverNamepipePipeNameCreateNamedPipe:在服务器端建立管道；ConnectNamedPipe:在服务器端等待客户连接请求；CallNamedPipe:客户进程建立与服务器管道连接；ReadFile,WriteFile:管道读写。,Windows2000/xp的mailslot,服务器端：.mailslotpathname客户进程：rangemailslotpathnamerange:本地或服务器CreatMailslot:服务器端创建邮件槽；GetMailslotInfo:服务器查询邮件槽信息；ReadFile:服务器读邮件槽；WriteFile:客户端发送消息。,Linux共享内存通讯,进程P的逻辑空间,进程Q的逻辑空间,内存空间,A,A,B,B,限制：只能用于同一站点通讯；注意：互斥问题需要用户自己控制。,Linux共享内存通讯,描述共享存储区的数据结构,structshmid_dsstructipc_permshm_perm;/operationpermsintshm_segsz;/sizeofsegment(bytes)_kernel_time_tshm_atime;/lastattachtime_kernel_time_tshm_dtime;/lastdetachtime_kernel_time_tshm_ctime;/lastchangetime_kernel_ipc_pid_tshm_cpid;/pidofcreator_kernel_ipc_pid_tshm_lpid;/pidoflastoperatorunsignedshortshm_nattch;/no.ofcurrentattachesunsignedshortshm_unused;/compatibilityvoid*shm_unused2;/ditto-usedbyDIPCvoid*shm_unused3;/unused,Linux共享内存通讯,相关系统调用shmget(key,size,permflg)/共享存储区的获取或创建；shmat(shmid,shmaddr,shmflg)/共享存储区的附接；shmdt(virtaddr)/共享存储区的剥离；shmctrl(shmid,cmd,buf)/共享存储区的控制。,Linux共享内存通讯,共享存储区的获取或创建调用原型：intshmid=intshmget(key_tkey,intsize,intshmflag)；参数：Key:标识共享内存的键值：(1)任意进程通讯，取一名字，注意冲突，可用ftok()产生；(2)父子进程通讯，IPC_PRIVATE:子进程继承。size:共享存储区的大小(以字节为单位，页面大小的整数倍)shmflg:(1)权限，一般取0666;(2)标志(a)IPC_CREATE不存在创建，存在返回标识,(b)IPC_CREATE|IPC_EXCL不存在创建，存在报错。返回值：shmid:共享内存内部标识,错误返回-1。,Linux共享内存通讯,共享内存的附接调用原型*virtaddr=shmat(intshmid,char*shmaddr,intshmflag)参数：shmid：共享内存的ID；shmaddr：共享内存的起始地址；0由系统分配；intshmflag：操作模式，SHM_RDONLY只读模式，其它(0)读写模式；返回值：成功时，虚拟空间起始地址，失败时返回-1。,Linux共享内存通讯,脱离附接调用原型intshmdt(char*virtaddr)参数：virtaddr：共享内存的虚拟地址。返回值：成功时返回0。失败时返回-1。,Linux共享内存通讯,共享内存控制调用原型intshmctl(intshmid,intcmd,structshmid_ds*buf);参数shmid：共享内存的ID。cmd：是控制命令(IPC_STAT取状态；IPC_SET设状态；IPC_RMID删除)buf:shmid_ds结构体指针。返回值：成功：0,失败：-1,Linux共享内存通讯(例子),发送进程sndshm.c#include#include#include#include#include#includemain()intshmid;char*viraddr;charbufferBUFSIZ;shmid=shmget(12