页数：79页文件大小：288.8 KB来源： 计算机操作系统ppt课件
本课件承接同步与通信主题，讲解适合分布式环境的会合机制及其与信号灯、管程的转换关系，并通过大量例题演示同步原语的正确性分析、死锁风险与常见编程陷阱，适合已掌握基本同步原语后的进阶练习。
会合描述的图示：……调用语句……PCBPCB………入口<accept>……调用语句……PCBPCB…入口<accept>……select调用任务被调用任务入口队列(FIFO)
accept语句流程有调用者选取队列中第一个调用者会合开始，调用者等待有in参数取in参数等待有语句序列执行语句序列有out参数送out参数会合结束，唤醒调用者TFFFFTTT
例4-10(分布系统会合例)：单一资源管理tasksingle_resourceisentryrequire ;entryrelease ;endsingle_resource;taskbodysingle_resourceisbeginloopacceptrequire;acceptrelease;end loopendsingle_resource;single_resource.require;使用single_resource.release;single_resource.require;使用single_resource.release;HOST1HOST
3.选择语句:同一时刻多个入口均有调用者时,可通过select语句选择一个入口的调用者与被调者会合。4.3.6.1会合的描述select[ when <布尔表达式>=> ]<接受语句>；[<语句序列>]{ or [ when <布尔表达式>=> ]<接受语句>；[ <语句序列>]}[ else <语句序列Selse> ]end select ;如果select语句中的某接受语句A之前的when条件为真,或A前面无when语句，则称A为开放的接受语句。
4.3.6.1会合的描述select语句流程计算所有布尔表达式为’真’者对应<accept>标记开放有开放的<accept>有else部分F有被调用的开放的<accept>T有else部分F等待F会合开始，调用者等待有in参数有语句序列F取in参数T执行语句序列T有out参数F送out参数Telse部分T建立异常条件Felse部分TF会合结束，调用者继续任取一开放且被调用的<accept>T
客栈Master主人4.3.6.2会合的例子例4-11客栈问题客栈问题描述客栈限制：一份猎物一份面包一份三明治一位客人主人活动：⑴接受猎物⑵接受面包⑶做三明治⑷给探险者...Explorers探险者Baker面包师Hunter狩猎者到客栈取一个三明治在外吃猎物交给客栈主人面包交给客栈主人
explorers：loop探险进客栈取三明治出客栈吃三明治end loophunter：loop狩猎进客栈送猎物出客栈end loopbaker：loop做面包进客栈送面包出客栈end loop入口进程定义入口入口4.3.6.2会合的例子例4-
任务及入口定义：procedureAdalodgeistask typeexplorer;taskhunter;taskbaker;taskmasterisentrydelivermeat;//狩猎者送猎物entrydeliverbread;//面包师送面包entrylodge;//探险家取三明治endmaster;4.3.6.2会合的例子例4-
task bodyexplorerisvictuals : food ;beginloopexplore ;master.lodge (victuals);//入客栈取三明治eat ( victuals ) ;end loopend explorer ;探险者任务：4.3.6.2会合的例子例4-
task bodyhunteriswalrus : food ;beginloophunt ( walrus ) ;master.delivermeat (walrus)end loopend hunter ;狩猎者任务：4.3.6.2会合的例子例4-
task bodybakerisrolls : food ;beginloopbake ( rolls ) ;master.deliverbread ( rolls )end loopend baker ;面包师任务：4.3.6.2会合的例子例4-
task bodymasterisbread, meat, sandwich : food ;proceduremakesandwichisbegincook (meat ) ;sandwich := bread + meat ;bread := 0 ;meat := 0 ;endmakesandwich;客栈主人任务：4.3.6.2会合的例子例4-
begin//master开始bread := 0 ; meat := 0; sandwich := 0 ;loopselectwhen bread=0 =>acceptdeliverbread ( br: in food)dobread := br;enddeliverbread;orwhen meat=0 =>acceptdelivermeat(mt: in food)domeat := mt ;enddelivermeat ;or客栈主人任务：4.3.6.2会合的例子例4-
when (sandwich<>0)or(bread<>0 and meat<>0) =>acceptlodge (snack: out food )//入店取三明治doif sandwich=0thenmakesandwichend if ;snack := sandwich ;endlodge ;sandwich := 0//会合期之外。该语句里外都行客栈主人任务：4.3.6.2会合的例子例4-
explorers: array [1 .. Numberofexploers] of explorer;begin null; end Adalodge ;elseif ( bread <> 0 ) and ( meat <> 0 )and ( sandwich = 0 )thenmakesandwichend if//栈主人活动end selectend loopend master客栈主人任务：4.3.6.2会合的例子例4-
用Ada语言中的会合解决读者/写者问题，要求写者优先。即编写一个任务，其中有如下四个入口：start_read;finish_read;start_write;finish_write.提示：可以使用嵌套的accept语句。
taskreaders_writersisentrystart_read; entryfinish_read;entrystart_write; entryfinish_write;endreaders_writes;task body readers_writers isvarread_count , write_count: integer;begin read_count := 0; write_count := 0 ;loopselect
when write_count = 0=>acceptstart_readdoread_count++;endstart_read;orwhen read_count > 0=>acceptfinish_readdoread_count--;endfinish_read;orwhen (write_count > 0)=>acceptfinish_writedowrite_count--;endfinish_write ;or
when write_count = 0 =>acceptstart_writedowhileread_count > 0doacceptfinish_readdoread_count--;endfinish_read ;end whilewrite_count++;endstart_write;end selectend loop;end readers_writers;
taskboundedbufferisentryputin;entrygetout;endboundedbuffer ;taskbodyboundedbufferisb :array[ 0 .. k-1 ]ofinteger ;ip , op :0 .. k-1 ;count :integer ;beginip:=0; op:=0; count:=0;loop4.3.6.2会合的例子Bounded buffer problem
selectwhen(count < k ) =>acceptputin ( item :ininteger )dob [ ip ] := item ;ip := ( ip + 1 ) mod k ;count := count + 1 ;endputin ;orwhen(count > 0 ) =>acceptgetout ( item :outinteger )doitem := b [ op ] ;op := ( op + 1 ) mod k ;count := count–1 ;endgetout ;endselectendloopendboundedbuffer ;4.3.6.2会合的例子Bounded buffer problem
生产者活动do {加工一件物品item ;boundedbuffer.putin(item);//物品放入箱中} while ( 1 )消费者活动：do {boundedbuffer.getout(item);//箱中取一物品;消耗物品item ;} while ( 1 )4.3.6.2会合的例子Bounded buffer problem
1.共享内存模式(shared memory)OS提供：⑴公共内存；⑵互斥同步机制。P1P2公共内存通信实现：进程之间运用OS提供的互斥同步机制实现对公共内存信息读/写。
：PCB…send(R,M)……M:发送者SsizetextPCB…receive(pid,N)……N:sizetext接收者Rmsg2msgn...msg1缓冲消息链是互斥区
sizetextsenderlink载有消息的缓冲：消息队列互斥：var m_mutex : semaphore; (1)P ( m_mutex ) ;入/出队列动作;V ( m_mutex ) ;4.4.3.1有缓冲途径消息队列同步：var S_msg : semaphore; (0)收取消息前：P ( S_msg ) ;消息入队后：V ( S_msg ) ;消息队列有入队列(发送)、出队列(接收)操作,需要互斥和同步管理。msgi:
Buffer pool managementvar S_buf, b_mutex : semaphore ; (k,1)申请：P ( S_buf ) ;P ( b_mutex ) ;头缓冲区出链;V ( b_mutex ) ;释放：P ( b_mutex ) ;缓冲区入链头;V ( b_mutex ) ;V ( S_buf ) ;bufbufbufHead4.4.3.1有缓冲途径发送/接收消息时，要对系统提供的缓冲池进行申请和释放操作，该缓冲池需要互斥和同步管理。假定系统在缓冲池提供k个消息缓冲区。
发送/接收原语send ( R , M )根据R找接收者；P ( S_buf ) ;P ( b_mutex ) ;从缓冲池取一空buf ;V ( b_mutex ) ;size,M,sender => bufP ( m_mutex ) ;消息buf入R消息队列链尾;V ( m_mutex ) ;V ( S_msg ) ;receive ( pid , N )P ( S_msg ) ;P ( m_mutex ) ;消息队列头消息msg1出链;V (m_mutex ) ;(msg1.size,msg1.text)=>Nmsg1.sender =>pidP ( b_mutex ) ;msg1入缓冲池链；V ( b_mutex ) ;V ( S_buf ) ;
4.4.3.2无缓冲途径发送/接收示图OSHALregister……………send(R,M);……………M:……S_mS_W……发送进程S……………received(pid,N);……………N:……S_m’S_W'……接收进程R
Mailbox(FIFO)发送send_MB (MB,M):将消息M发送到信箱MB.接收receive_MB (MB,N):从信箱MB接收消息到N.特点:multi-sender⇒multi-receiver;multi-sender⇒one receiver4.4.4间接方式间接方式:通信进程之间在通信时不指定对方名字,而是指定一个中间媒体—信箱。又称作信箱方式。…msg3msg2msg1
typedefmailboxstruct {int in, out; semaphore s1, s2 ; ( k , 0 )semaphore mutex ; ( 1 )message letter[k] ;} ;mailboxmb;//编译时并不分配空间create_MB ( mb ) ;//系统调用,为mb分配空间delete_MB ( mb ) ;//系统调用,释放mb空间4.4.4间接方式通信实现:信箱即可以在操作系统空间,也可以在用户空间。考虑信箱在操作系统空间的通信实现。
send_MB (mailbox mb; message M){ P ( mb.s1 ) ;//信箱有空位？P ( mb.mutex ) ;mb.letter [mb.in ] = M ;mb.in = ( mb.in + 1 ) % k ;V ( mb.mutex ) ;V ( mb.s2 )//消息增加一个}
receive_MB(mailbox mb; message *N){ P ( mb.s2 ) ;//申请消息P ( mb.mutex ) ;*N= mb.letter [ mb.out ] ;mb.out = ( mb.out + 1 ) % k ;V ( mb.mutex ) ;V ( mb.s1 ) ;//空位增加一个}
creat_MB(mb);………….receive_MB(mb,N);…………delete_MB(mb);…………N:………….send_MB(mb,M);……………………M:OSCreat_MBDelete_MBSend_MBReceive_MB…msg3msg2msg1mailbox mb;通信实现示图(信箱在系统空间):…msg3msg2msg1创建信箱的进程为信箱拥有者,可以调用receive_MB.
4.5.1 Java中的管程entry setandwait setObjectLockownerentry setwait setAcquire locknotify(), notifyAll()wait()
例：生产/消费问题public classBounded Buffer{ public BoundedBuffer ( ){ count=0; in=0; out=0;buffer = new Object [ BUFFER_SIZE ] ;}private static finalintBUFFER_SIZE=5;privateintcount, in, out;privateObject[]buffer;4.5.1 Java中的管程
4.5.1 Java中的管程例：生产/消费问题publicsynchronizedvoid enter(Object item){ while ( count == BUFFER_SIZE )try{ wait();//被唤醒后重新检测等待条件}catch (InterruptedException e){ }count++;buffer [ in ] = item ;in = ( in+1 ) % BUFFER_SIZE ;notify ( ) ;}
4.5.1 Java中的管程例：生产/消费问题publicsynchronizedObject remove( ){ while ( count == 0 ){try{ wait();}catch (InterruptedException e){ }}count--;item = buffer [ out ] ;out = ( out + 1 ) % BUFFER_SIZE ;notify ( ) ;return ( item );}}
4.5.1 Java中的管程例：生产/消费问题生产者活动：do {加工一件物品item;pc.enter( item );} while ( 1 )消费者活动：do { item=pc.remove;消耗物品item;} while ( 1 )Bounded Bufferpc;
4.5.1 Java中的管程例：读者/写者问题public classDatabase{public Database ( ){ readcount = 0 ;dbReading = false ; dbWriting = false ;}private intreadercount;private booleandbReading;private booleandbWriting;
4.5.1 Java中的管程例：读者/写者问题publicsynchronizedvoid startRead( ){ while ( dbWriting == true )try{ wait ( ) ;}catch(InterruptedException e){}readcount ++ ;if ( readcount == 1 ) dbReading = true ;}publicsynchronizedvoid endRead(){ readcount--;if ( readcount == 0 ) dbReading = false ;notifyAll () ;}
4.5.1 Java中的管程例：读者/写者问题publicsynchronizedvoid startWrite( ){ while(dbReading==true||dbWriting==true)try{ wait();}catch (InterruptedException e) { }dbWriting=true;}publicsynchronizedvoid endWrite( ){dbWriting=false;notifyAll();}}
4.5.2 Linux进程通信4.5.2.1共享内存textdata栈共享存储区进程P的逻辑空间textdata栈进程Q的逻辑空间内存空间共享内存通信其它pagetableshmaddrsizekey…………………………共享存储区表AA’BB’
(2)共享存储区的附接char *shmat(shmid, shmaddr, shmflg)int shmid, shmflg; char *shmaddr;shmid: shmget返回的共享存储区描述符；shmaddr:共享存储区对应的进程虚拟空间的起始地址；shmflg:读写标志。等于SHM_RDONLY表示只读；等于0表示可读写；函数返回值：共享存储区对应进程空间的虚拟地址。
(3)共享存储区的分离int shmdt( shmaddr )char *shmaddr;shmaddr:要分离的虚拟地址，即shmat返回的虚拟地址。
4.5.2.2 signal、pipe与持久对象pipe是用于进程间传递消息。持久对象(persistent object)可以被进程创建和撤销，也可能被移到后备存储器中。
4.5.3 Windows 2000/XP的并发控制功能描述Win32应用程序接口同步对象创建一个信号量变量，由参数给出初值。CreateSemaphore信号量打开已经存在的信号量对象，返回句柄。OpenSemaphore释放对信号量对象的引用。ReleaseSemaphore创建一个新互斥锁对象。CreateMutex互斥锁打开已经存在的互斥锁对象，返回句柄。OpenMutex释放对互斥对象的占有。ReleaseMutex创建一个事件对象。CreateEvent事件打开事件对象，返回句柄。OpenEvent设置事件对象为有信号状态。SetEvent重置事件对象。ResetEvent探测事件对象。PulseEvent初始化一个临界区对象。InitializeCriticalSection临界区等待进入临界区，得到使用权时返回。EnterCriticalSection以非等待方式申请临界区互斥权，申请失败则返回0。TryEnterCriticalSection释放一个临界区的使用权。LeaveCriticalSection撤销临界区对象。DeleteCriticalSection
UNIX进程高级通讯机制Pipe:an unnamed file with two fds , one for write, andthe other for read. The size of pipe file is limited to 4blocks(one block is 512 bytes).int fd [ 2 ] ;pipe ( fd ) :功能：创建一个pipe文件返回：fd [0]:读描述符；fd [1]:写描述符。pipe可以被子进程继承.管道读/写:write(fd[1],buf1,count1);//将buf1中count1个字节写入管道；read(fd[0],buf2,count2);//把管道中count2个字节读到buf2.无名管道
Windows2000/xp的mailslot服务器端：\\.\mailslot\[path]name客户进程：\\range\mailslot\[path]namerange:本地或服务器CreatMailslot:服务器端创建邮件槽；GetMailslotInfo:服务器查询邮件槽信息；ReadFile:服务器读邮件槽；WriteFile:客户端发送消息。
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}