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

1、4.3.6 会会 合合 (Rendezvous)n P/V操作、管程等同步机制操作、管程等同步机制 适合于单机系统及具有公共内存的多适合于单机系统及具有公共内存的多CPU系统系统;n 会合适合于不具有公共内存的分布式系统会合适合于不具有公共内存的分布式系统;n 80年代年代, Ada, Initiated by DOD; Ada 95, (Object-oriented)n 会会 合合: 两个并发执行流汇集到一处两个并发执行流汇集到一处。l并发执行流并发执行流：调用调用；接受接受l均发生均发生, 握手握手, 同步。同步。l 共享变量与访问进程在同一存储区，共享变量与访问进程在同一存储区， 不适

2、合分布环境。不适合分布环境。4.3.6 会会 合合(Cont.)共享变量共享变量( 被动被动 )CR1P1:CR2P2:l 管程与调用进程在同一存储区，管程与调用进程在同一存储区， 不适合分布环境。不适合分布环境。P1:共享变量共享变量CR2管程管程(被动被动):CR1P2:分布系统中的同步机制分布系统中的同步机制应避开被动成分应避开被动成分4.3.6 会会 合合(Cont.)n 会合图示会合图示l 被调用者被调用者代代调用者调用者执行调用代码。执行调用代码。4.3.6.1 会合的描述会合的描述调用语句调用语句调用语句调用语句接受语句接受语句选择语句选择语句任任 务务task任任 务务task

3、任任 务务task不同主机中主动成分不同主机中主动成分进程直接相互作用：进程直接相互作用：会合同步机制。会合同步机制。 会合描述：会合描述：n 一个任务可有多个入口，每个入口对应一段程序；一个任务可有多个入口，每个入口对应一段程序；n 一个任务一个任务调用调用另一个任务的入口，另一个任务的入口， 被调任务被调任务接受接受该调用，会合发生；该调用，会合发生；n 调用者发出调用请求，被调者未接受该调用，调用者等待；调用者发出调用请求，被调者未接受该调用，调用者等待；n 被调者要接受调用，而当前尚无调用者时，被调用者等待；被调者要接受调用，而当前尚无调用者时，被调用者等待；n 当多个任务调用某任务的

4、同一个入口时，当多个任务调用某任务的同一个入口时， 被调用者按先来先服务被调用者按先来先服务(FCFS)的次序接受调用；的次序接受调用；n 入口处可以携带调用参数，还可以有返回参数，入口处可以携带调用参数，还可以有返回参数， 以实现信息的交换；以实现信息的交换；n 被调用者可以被调用者可以选择选择会合的入口。会合的入口。 先到达会合处者先到达会合处者等待后到达者。等待后到达者。4.3.6.1 会合的描述会合的描述(Cont.)会合描述的图示：会合描述的图示：调用语句调用语句PCBPCB入口入口 调用语句调用语句PCBPCB入口入口 select调用任务调用任务被调用任务被调用任务入口队列入口队

5、列(FIFO)4.3.6.1 会合的描述会合的描述(Cont.)Ada实现会合的核心语句实现会合的核心语句:1. 调用语句调用语句 . ;2. 接受语句接受语句 accept do end l 形参表形参表中可有入参数和出参数，分别用保留字中可有入参数和出参数，分别用保留字 in 和和 out 来区分。来区分。l 由于分布系统中没有公共内存，故形参全为值参，且不可为指针。由于分布系统中没有公共内存，故形参全为值参，且不可为指针。 4.3.6.1 会合的描述会合的描述(Cont.)accept 语句的语义：语句的语义：n 若若无调用者无调用者，则等待；，则等待；n 选取第一个调用者；选取第一个调

6、用者；n 会合开始，会合开始，调用者等待调用者等待；n 若有若有 in 参数，则参数，则取取 in 参数；参数；n 若若有有，则，则执行之；执行之；n 若有若有 out 参数，则参数，则送送 out 参数；参数；n 会合结束，会合结束，调用者继续调用者继续。会合期会合期4.3.6.1 会合的描述会合的描述(Cont.)accept 语句流程语句流程有调用者有调用者选取队列中第一个调用者选取队列中第一个调用者会合开始，调用者等待会合开始，调用者等待有有 in 参数参数取取 in 参数参数等等 待待有语句序列有语句序列执行语句序列执行语句序列有有 out 参数参数送送 out 参数参数会合结束，会

7、合结束，唤醒调用者唤醒调用者TFFFFTTT4.3.6.1 会合的描述会合的描述(Cont.)例例4-10 (分布系统会合例分布系统会合例)：单一资源管理单一资源管理task single_resource is entry require ; entry release ;end single_resource;task body single_resource is begin loop accept require; accept release; end loop end single_resource;single_resource.require; 使用使用single_resou

8、rce.release;single_resource.require; 使用使用single_resource.release;HOST1HOST24.3.6.1 会合的描述会合的描述(Cont.)3. 选择语句选择语句: 同一时刻多个入口均有调用者时同一时刻多个入口均有调用者时, 可通过可通过select 语句选择一个入口的调用者与被调者会合。语句选择一个入口的调用者与被调者会合。4.3.6.1 会合的描述会合的描述(Cont.)select when = ； or when = ； else end select ;如果如果select语句中的语句中的某接受语句某接受语句 A 之前的之前

9、的when条件为真条件为真, 或或 A 前面无前面无when语句，语句，则称则称A为为开放的接受开放的接受语句语句。4.3.6.1 会合的描述会合的描述(Cont.)select 语句的语义：语句的语义：n 计算所有布尔表达式，为计算所有布尔表达式，为真真者对应者对应标记标记开放开放；n 无开放的无开放的： 如果有如果有ELSE部分则部分则执行执行Selse ，否则，否则异常异常; break;n 无被调用的开放的无被调用的开放的 (此时有开放的此时有开放的accept)： 如果有如果有ELSE部分，则部分，则执行执行Selse，break; 否则被调用者否则被调用者等待等待;n 任取一开放的

10、任取一开放的且且被调用的被调用的：l 会合开始，会合开始，调用者等待；调用者等待；l 若有若有 in 参数，则参数，则取取 in 参数；参数；l 若若有有，则，则执行之；执行之；l 若有若有 out 参数，则参数，则送送 out 参数；参数；l 会合结束，会合结束，调用者继续调用者继续。会合期会合期4.3.6.1 会合的描述会合的描述(Cont.)select 语句流程语句流程计算所有布尔表达式计算所有布尔表达式为为真真者对应者对应标记开放标记开放有开放的有开放的有有else部分部分F有被调用的开放的有被调用的开放的T有有else部分部分F等等 待待F会合开始，调用者等待会合开始，调用者等待有

11、有 in 参数参数有语句序列有语句序列F取取 in 参数参数T执行语句序列执行语句序列T有有 out 参数参数F送送 out 参数参数Telse部分部分T建立异常条件建立异常条件Felse部分部分TF会合结束，调用者继续会合结束，调用者继续任取一开放且被调用的任取一开放且被调用的T客客 栈栈Master 主人主人4.3.6.2 会合的例子会合的例子 例例4-11 客栈问题客栈问题 客栈问题描述客栈问题描述 客栈限制：客栈限制：一份猎物一份猎物 一份面包一份面包一份三明治一份三明治一位客人一位客人主人活动：主人活动： 接受猎物接受猎物 接受面包接受面包 做三明治做三明治 给探险者给探险者.Exp

12、lorers探险者探险者Baker面包师面包师Hunter狩猎者狩猎者到客栈取一个到客栈取一个三明治在外吃三明治在外吃猎物交给猎物交给客栈主人客栈主人面包交给面包交给客栈主人客栈主人explorers：loop 探探 险险 进客栈进客栈 取三明治取三明治 出客栈出客栈 吃三明治吃三明治end loophunter：loop 狩狩 猎猎 进客栈进客栈 送猎物送猎物 出客栈出客栈end loopbaker：loop 做面包做面包 进客栈进客栈 送面包送面包 出客栈出客栈end loop入入口口进程定义进程定义 入入口口入入口口4.3.6.2 会合的例子会合的例子(Cont.) 例例4-11 客栈问

13、题客栈问题任务及入口定义：任务及入口定义：procedure Adalodge is task type explorer ; task hunter ; task baker ; task master is entry delivermeat ; /狩猎狩猎者送猎物者送猎物 entry deliverbread ; /面包师送面包面包师送面包 entry lodge ; /探险家取三明治探险家取三明治 end master ;4.3.6.2 会合的例子会合的例子(Cont.) 例例4-11 客栈问题客栈问题task body explorer is victuals : food ; be

14、gin loop explore ; master.lodge (victuals) ; /入客栈取三明治入客栈取三明治 eat ( victuals ) ; end loop end explorer ;探险者任务：探险者任务：4.3.6.2 会合的例子会合的例子(Cont.) 例例4-11 客栈问题客栈问题task body hunter is walrus : food ; begin loop hunt ( walrus ) ; master.delivermeat (walrus) end loop end hunter ;狩猎者任务：狩猎者任务：4.3.6.2 会合的例子会合的例子

15、(Cont.) 例例4-11 客栈问题客栈问题task body baker is rolls : food ; begin loop bake ( rolls ) ; master.deliverbread ( rolls ) end loop end baker ;面包师任务：面包师任务：4.3.6.2 会合的例子会合的例子(Cont.) 例例4-11 客栈问题客栈问题task body master is bread, meat, sandwich : food ; procedure makesandwich is begin cook (meat ) ; sandwich := br

16、ead + meat ; bread := 0 ; meat := 0 ; end makesandwich ;客栈主人任务：客栈主人任务：4.3.6.2 会合的例子会合的例子(Cont.) 例例4-11 客栈问题客栈问题begin /master开始开始 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 = accept delivermeat

17、(mt: in food) do meat := mt ; end delivermeat ; or客栈主人任务：客栈主人任务：4.3.6.2 会合的例子会合的例子(Cont.) 例例4-11 客栈问题客栈问题 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 /会合期之外。该语句里外都行会合期之

18、外。该语句里外都行客栈主人任务：客栈主人任务：4.3.6.2 会合的例子会合的例子(Cont.) 例例4-11 客栈问题客栈问题explorers: array 1 . Numberofexploers of explorer;begin null; end Adalodge ; else if ( bread 0 ) and ( meat 0 ) and ( sandwich = 0 ) then makesandwich end if /栈主人活动栈主人活动 end select end loopend master客栈主人任务：客栈主人任务：4.3.6.2 会合的例子会合的例子(Cont

19、.) 例例4-11 客栈问题客栈问题用用 Ada 语言中的会合解决读者语言中的会合解决读者/写者问题，要求写者优先。写者问题，要求写者优先。即编写一个任务，其中有如下四个入口：即编写一个任务，其中有如下四个入口： start_read; finish_read; start_write; finish_write. 提示：提示：可以使用嵌套的可以使用嵌套的 accept 语句。语句。4.3.6.2 会合的例子会合的例子(Cont.) 例例4-12 读者读者-写者问题写者问题task readers_writers is entry start_read ; entry finish_read

20、; entry 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 select4.3.6.2 会合的例子会合的例子(Cont.) 例例4-12 读者读者-写者问题写者问题when write_count = 0 = accept start_read do read_count+; end start_read

21、; orwhen read_count 0 = accept finish_read do read_count-; end finish_read; or when (write_count 0) = accept finish_write do write_count-; end finish_write ; or 4.3.6.2 会合的例子会合的例子(Cont.) 例例4-12 读者读者-写者问题写者问题 when write_count = 0 = accept start_write do while read_count 0 do accept finish_read do rea

22、d_count- ; end finish_read ; end while write_count+; end start_write;end selectend loop;end readers_writers;4.3.6.2 会合的例子会合的例子(Cont.) 例例4-12 读者读者-写者问题写者问题n 读者活动读者活动:readers_writes . start_read ;读操作；读操作；Readers_writers . finish_read ;n 写者活动写者活动:readers_writers . start_write ;写操作；写操作；readers_writers .

23、 finish_write ;4.3.6.2 会合的例子会合的例子(Cont.) 例例4-12 读者读者-写者问题写者问题task 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 : integer ; begin ip:=0; op:=0; count:=0; loop4.3.6.2 会合的例子会合的例子(Cont.) Bounded buffer

24、 problem select when (count accept putin ( item : in integer ) do b ip := item ; ip := ( ip + 1 ) mod k ; count := count + 1 ; end putin ; or when (count 0 ) = accept getout ( item : out integer ) do item := b op ; op := ( op + 1 ) mod k ; count := count 1 ; end getout ; end select end loopend bound

25、edbuffer ; 4.3.6.2 会合的例子会合的例子(Cont.) Bounded buffer problem生产者活动生产者活动 do 加工一件物品加工一件物品 item ; boundedbuffer.putin(item) ; /物品放入箱中物品放入箱中 while ( 1 )消费者活动：消费者活动：do boundedbuffer.getout(item) ; /箱中取一物品箱中取一物品; 消耗物品消耗物品 item ; while ( 1 )4.3.6.2 会合的例子会合的例子(Cont.) Bounded buffer problem4.4 进程高级通信进程高级通信n 低级

26、通信低级通信 (简单信号简单信号)l 进程互斥：相关或不相关进程之间；进程互斥：相关或不相关进程之间；l 进程同步：相关进程之间。进程同步：相关进程之间。n 高级通信高级通信 (大宗信息的交换大宗信息的交换)l memory sharingl message passingu direct vs. indirectu symmetric vs. non-symmetricu buffering vs. non-buffering4.4.1 进程通信的概念进程通信的概念进程通信：进程通信：进程之间的互斥、同步及信息交换统称为进进程之间的互斥、同步及信息交换统称为进程通信程通信(Inter-Pro

27、cess Communication : IPC)。4.4.2 进程通信的模式进程通信的模式1. 共享内存模式共享内存模式(shared memory)OS 提供：提供： 公共内存；公共内存； 互斥同步机制。互斥同步机制。P1P2公共公共内存内存通信实现：通信实现：进程之间运用进程之间运用OS提供的互斥同步机制提供的互斥同步机制 实现对公共内存信息读实现对公共内存信息读/写。写。直接直接: 进程进程-进程进程间接间接: 进程进程-信箱信箱-进程进程4.4.2 进程通信的模式进程通信的模式(Cont.)2. 消息传递模式消息传递模式(message passing)P1sendP2receive

28、Mn 进程之间无公共内存进程之间无公共内存;n OS 提供系统调用命令提供系统调用命令:l 发送命令发送命令sendl 接收命令接收命令receiven 消息传递过程由消息传递过程由 OS 完成完成, 对用户透明。对用户透明。4.4.3 直接方式直接方式n 对称形式对称形式 (symmetric)： sender and receiver name each otherl send ( R , message ) ;l receive ( S , message ) ;send (R,M)R:直接方式直接方式: 相互通信进程在通信时，直接指定接收者相互通信进程在通信时，直接指定接收者 或发送者

29、的名字。或发送者的名字。receive (S,N)S:一对一通信一对一通信4.4.3 直接方式直接方式(Cont.)n 非对称形式非对称形式 (asymmetric)：多对一：多对一 only sender names receiverl send ( R , message ) ;l receive ( pid , message ) ;send (R,M1)S1:send (R,M2)S2:receive (pid,N)R:传送途径传送途径: 缓冲途径、非缓冲途径缓冲途径、非缓冲途径C/S model4.4.3.1 有缓冲途径有缓冲途径适用于消息传递模式、直接方式适用于消息传递模式、直接方

30、式( (非对称形式非对称形式) )。发送过程发送过程:n 发送进程执行发送进程执行send;n OS为发送进程分配缓冲区为发送进程分配缓冲区;n 将将send消息拷贝到缓冲区消息拷贝到缓冲区;n 将缓冲区链接到接收进程的消息链中。将缓冲区链接到接收进程的消息链中。接收过程：接收过程：n 接收进程执行接收进程执行receive;n OS在接收进程的消息链中取出消息缓冲区在接收进程的消息链中取出消息缓冲区, 并将其内容拷贝到接收进程空间并将其内容拷贝到接收进程空间;n 释放缓冲区。释放缓冲区。4.4.3.1 有缓冲途径有缓冲途径(Cont.)缓冲消息通信示图：缓冲消息通信示图：SPCBsend(R

31、,M)M:发送者发送者SsizetextRPCBreceive(pid,N)N:sizetext接收者接收者Rmsg2msgn.msg1缓冲消息链是互斥区缓冲消息链是互斥区sizetextsenderlink载有消息的缓冲：载有消息的缓冲：消息队列互斥：消息队列互斥： var m_mutex : semaphore; (1) P ( m_mutex ) ; 入入/出队列动作出队列动作 ; V ( m_mutex ) ;4.4.3.1 有缓冲途径有缓冲途径(Cont.)消息队列同步：消息队列同步： var S_msg : semaphore; (0) 收取消息前：收取消息前：P ( S_msg

32、) ; 消息入队后：消息入队后：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

33、.1 有缓冲途径有缓冲途径(Cont.)发送发送/接收消息时，要对系统提供的缓冲池进行申请和释放操作，该缓冲接收消息时，要对系统提供的缓冲池进行申请和释放操作，该缓冲池需要互斥和同步管理。假定系统在缓冲池提供池需要互斥和同步管理。假定系统在缓冲池提供 k 个消息缓冲区。个消息缓冲区。发送发送/接收原语接收原语send ( R , M ) 根据根据 R 找接收者；找接收者； P ( S_buf ) ; P ( b_mutex ) ; 从缓冲池链头取一空从缓冲池链头取一空 buf ; V ( b_mutex ) ; size,M,sender = buf P ( m_mutex ) ; 消息消息

34、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)= N msg1.sender = pid P ( b_mutex ) ; msg1入入缓冲池缓冲池链链头头； V ( b_mutex ) ; V ( S_buf ) ;4.4.3.1 有缓冲途径有缓冲途径(Cont.)Remarks：n send/receive 为高级通

35、信原语为高级通信原语, 可用低级原语实现可用低级原语实现;n send/receive不是真正意义的原语，不是真正意义的原语， 可以被中断。可以被中断。n 每个进程的每个进程的PCB中都要定义中都要定义 S_msg 和和 m_mutex .n S_buf和和b_mutex是操作系统定义的公共信号量。是操作系统定义的公共信号量。4.4.3.1 有缓冲途径有缓冲途径(Cont.)适用于消息传递模式，直接方式，非对称形式。适用于消息传递模式，直接方式，非对称形式。发送发送/接收过程：接收过程：n 发送进程执行发送进程执行 send， 若接收进程未执行到若接收进程未执行到 receive，则发送者等待

36、；，则发送者等待；n 接收进程执行接收进程执行 receive， 若发送进程未执行到若发送进程未执行到 send，则接收者等待；，则接收者等待；n 发送发送 / 接收都发生，信息由发送者接收都发生，信息由发送者复制复制到接收者。到接收者。4.4.3.2 无缓冲途径无缓冲途径发送发送/接收的同步：接收的同步：每个进程的每个进程的PCB中两个信号量。中两个信号量。semaphore S_m ; / 初值为初值为 0, 用于接收者等待。用于接收者等待。semaphore S_w ; / 初值为初值为 0, 用于发送者等待。用于发送者等待。通过通用寄存器通过通用寄存器4.4.3.2 无缓冲途径无缓冲途

37、径(Cont.) send(R, M):n 根据根据 R 找到消息接收者找到消息接收者;n 发送消息进程个数增发送消息进程个数增1, 执行执行V(R.S_m), 通知进程通知进程 R 要发消息要发消息 (如等待将其唤醒如等待将其唤醒)；n 等待等待 R 执行到执行到 receive, 即执行即执行 P ( S.S_w ) 。receive(pid, N):n 等待消息到达等待消息到达, 即执行即执行 P (R.S_m ) ;n 消息由发送进程空间消息由发送进程空间 M 复制到接收进程空间复制到接收进程空间 N ;n 唤醒发送消息进程唤醒发送消息进程, 即执行即执行 V (S.S_w ) 。发送

38、发送/接收原语接收原语R进进程程Send所在进程所在进程4.4.3.2 无缓冲途径无缓冲途径(Cont.)发送发送/接收示图接收示图OSHALregistersend(R,M);M:S_mS_W发送进程发送进程 Sreceived(pid,N);N:S_mS_W接收进程接收进程 Rn 优优 点点:l节省空间节省空间(不需要不需要buffer)n 缺缺 点点:l并发性差并发性差: 发送进程需要等待接收进程执行发送进程需要等待接收进程执行receive 把信息复制到接收进程空间后才能继续。把信息复制到接收进程空间后才能继续。4.4.3.2 无缓冲途径无缓冲途径(Cont.)Mailbox(FIFO

39、)发送发送 send_MB (MB,M): 将消息将消息M发送到信箱发送到信箱MB.接收接收 receive_MB (MB,N): 从信箱从信箱MB接收消息到接收消息到N.特点特点: multi-sender multi-receiver; multi-sender one receiver4.4.4 间接方式间接方式间接方式间接方式: 通信进程之间在通信时不指定对方名字通信进程之间在通信时不指定对方名字, 而是指定一个中间媒体而是指定一个中间媒体信箱信箱。 又称作又称作信箱方式信箱方式。msg1 msg2msg3typedef mailbox struct int in, out; /*初值

40、均为初值均为0; 取值范围取值范围0k-1*/ semaphore s1, s2 ; ( k , 0 ) semaphore mutex ; ( 1 ) message letterk ; ;mailbox mb ; /编译时并不分配空间编译时并不分配空间create_MB ( mb ) ; /系统调用系统调用, 为为mb分配空间分配空间delete_MB ( mb ) ; /系统调用系统调用, 释放释放mb空间空间4.4.4 间接方式间接方式(Cont.)通信实现通信实现: 信箱即可以在操作系统空间信箱即可以在操作系统空间, 也可以在用户空间。也可以在用户空间。 考虑信箱在考虑信箱在操作系统

41、空间的通信实现。操作系统空间的通信实现。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 ) /消息增加一个消息增加一个 4.4.4 间接方式间接方式(Cont.)receive_MB(mailbox mb; message *N) P ( mb.s2 ) ; /申请消息申请消息 P ( mb.mutex ) ; *N= mb.letter

42、 mb.out ; mb.out = ( mb.out + 1 ) % k ; V ( mb.mutex ) ; V ( mb.s1 ) ; /空位增加一个空位增加一个4.4.4 间接方式间接方式(Cont.)4.4.4 间接方式间接方式(Cont.)creat_MB(mb);.receive_MB(mb,N);delete_MB(mb); N:.send_MB(mb,M); M:OS Creat_MB Delete_MB Send_MB Receive_MBmsg1 msg2msg3mailbox mb;通信实现示图通信实现示图(信箱在系统空间信箱在系统空间):msg1 msg2msg3创建

43、信箱的进创建信箱的进程为信箱拥有程为信箱拥有者者, 可以调用可以调用receive_MB.4.5 系统举例系统举例4.5.1 Java中的管程中的管程类似管程的对象类似管程的对象objectn 每个每个object有一个互斥锁有一个互斥锁lock，一般未用；，一般未用；n 说明为说明为synchronized的的method启用互斥锁；启用互斥锁；n 每个每个object内部有一个等待队列；内部有一个等待队列；n wait() : l释放释放lock, 状态改为状态改为blocked, 进入进入wait set.n notify() :l在在wait set中取任意线程，移到中取任意线程，移到

44、entry set, 状态改为状态改为runnable. (Signal and continue)n notifyAlllwait set所有线程移到所有线程移到entry set, 状态改为状态改为runnable.4.5.1 Java中的管程中的管程(Cont.)entry set and wait setObjectLock ownerentry setwait setAcquire locknotify(), notifyAll()wait()4.5.1 Java中的管程中的管程(Cont.)entry set and wait setn 锁的持有者锁的持有者执行执行 wait 操作

45、操作, 状态改为状态改为blocked, 释放所持有的锁释放所持有的锁 , 进入进入 wait set ; 若若 entry set 非空非空 , 选择其一进入同步方法。选择其一进入同步方法。n 锁的持有者锁的持有者执行执行 notify 操作操作 , 任选任选 wait set 上的一个上的一个线程线程 , 入入 entry set , 状态改为状态改为 runnable . 执行执行notify操作的线程继续。操作的线程继续。n 锁的持有者锁的持有者执行执行 notifyAll 操作操作 , wait set 上的所有线上的所有线程出程出 wait set , 入入 entry set ,

46、 状态改为状态改为 runnable . 执行执行notifyAll操作的线程继续。操作的线程继续。例：生产例：生产/消费问题消费问题public class BoundedBuffer /*类定义开始类定义开始*/public BoundedBuffer ( ) /*缓冲区变量定义缓冲区变量定义*/ count=0; in=0; out=0; buffer = new Object BUFFER_SIZE ; private static final int BUFFER_SIZE=5;private int count, in, out ;private Object buffer ;4.

47、5.1 Java中的管程中的管程(Cont.)4.5.1 Java中的管程中的管程(Cont.)例：生产例：生产/消费问题消费问题(Cont.)public synchronized void 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中的管程中

48、的管程(Cont.)例：生产例：生产/消费问题消费问题(Cont.)public synchronized Object 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中的管程中的管程(Cont.)例：生产例：生产/消费问题消费问题(Cont.)生产者活动：生

49、产者活动：do 加工一件物品加工一件物品item; pc.enter( item ); while ( 1 )消费者活动：消费者活动：do item=pc.remove; 消耗物品消耗物品item; while ( 1 )BoundedBuffer pc; /*定义对象定义对象 pc */4.5.1 Java中的管程中的管程(Cont.)例：读者例：读者/写者问题写者问题public class Database /* 类定义开始类定义开始 */public Database ( ) readcount = 0 ; dbReading = false ; dbWriting = false ;

50、 private int readercount;private boolean dbReading;private boolean dbWriting;4.5.1 Java中的管程中的管程(Cont.)例：读者例：读者/写者问题写者问题(Cont.)public synchronized void startRead ( ) while ( dbWriting = true ) try wait ( ) ; catch(InterruptedException e) readcount + ; if ( readcount = 1 ) dbReading = true ; public sy

51、nchronized void endRead() readcount - ; if ( readcount = 0 ) dbReading = false ; notifyAll () ;4.5.1 Java中的管程中的管程(Cont.)例：读者例：读者/写者问题写者问题(Cont.)public synchronized void startWrite ( ) while(dbReading=true|dbWriting=true) try wait(); catch (InterruptedException e) dbWriting=true;public synchronized v

52、oid endWrite ( ) dbWriting=false; notifyAll(); /*类定义结束类定义结束*/4.5.1 Java中的管程中的管程(Cont.)Java synchronization rulesn A thread that owns the lock for an object can enter another synchronized method (or block) for the same object.n A method can nest synchronized method invocation for different objects. T

53、hus a thread can simultaneously own the lock for several different objects.n If a method is not declared as synchronized, then it can be invoked regardless of lock ownership, even while another synchronized method for the same object is executing. n If the wait set for an object is empty, then a cal

54、l to notify() or notifyAll() has no effect.4.5.2 Linux进程通信进程通信4.5.2.1 共享内存共享内存textdata栈栈共享存储区共享存储区进程进程P的逻辑空间的逻辑空间textdata栈栈进程进程Q的逻辑空间的逻辑空间内存空间内存空间共共享享内内存存通通信信keysizeshmaddrpagetable其它其它shmid:共享存储区表共享存储区表AABB4.5.2.1 共享内存共享内存(Cont.)(1) 共享存储区建立共享存储区建立int shmget(key, size, shmflg)key_t key; int size, sh

55、mflg; 检查共享存储区表，查找与检查共享存储区表，查找与key相同的表项。相同的表项。 若有，则该区已建立，返回若有，则该区已建立，返回shmid。 若无，且若无，且shmflg=IPC_CREAT、size合法，合法， 则分配页表及相应页面；则分配页表及相应页面； 根据参数根据参数key、size和和shmflg， 在共享存储区表中填写新的表项，返回共享存储区描述符。在共享存储区表中填写新的表项，返回共享存储区描述符。4.5.2.1 共享内存共享内存(Cont.)(2) 共享存储区的附接共享存储区的附接char *shmat(shmid, shmaddr, shmflg)int shmi

56、d, shmflg; char *shmaddr;shmid: shmget返回的共享存储区描述符；返回的共享存储区描述符；shmaddr: 共享存储区对应的共享存储区对应的 进程虚拟空间的起始地址；进程虚拟空间的起始地址；shmflg: 读写标志。读写标志。 等于等于SHM_RDONLY表示只读；表示只读； 等于等于0表示可读写；表示可读写；函数返回值：函数返回值：共享存储区对应进程空间的共享存储区对应进程空间的虚拟地址虚拟地址。共享区首地址？共享区首地址？4.5.2.1 共享内存共享内存(Cont.)(3) 共享存储区的分离共享存储区的分离int shmdt( shmaddr )char

57、*shmaddr;shmaddr: 要分离的虚拟地址，要分离的虚拟地址， 即即shmat返回的虚拟地址。返回的虚拟地址。4.5.2.1 共享内存共享内存(Cont.)(4) 共享存储区使用例：共享存储区使用例：进程进程P： char * A; shmid0=shmget(key0 ,1024, IPC_CREAT); A*shmat(shmid0, A, SHM_RDONLY); ； i=shmdt( A )；进程进程Q： char *B; shmid0=shmget(key0 ,1024, IPC_CREAT); B*shmat(shmid0, B, 0); ； i=shmdt( B )；4

58、.5.2.2 signal、pipe与持久对象与持久对象Signal是一种软件中断是一种软件中断, 通知程序某种事件的发生。通知程序某种事件的发生。Signal产生产生:n 按下按下CTRL+C产生产生SIGINT;n 硬件中断硬件中断, 如除如除0, 非法内存访问非法内存访问(SIGSEV)等等;n Kill 函数可以对进程发送函数可以对进程发送Signal;n Kill命令。实际上是对命令。实际上是对Kill函数的一个包装；函数的一个包装；n 软件中断软件中断: 当当Alarm Clock超时超时(SIGURG)； 当当Reader中止之后又向管道写数据中止之后又向管道写数据 (SIGPI

59、PE).4.5.2.2 signal、pipe与持久对象与持久对象pipe是用于进程间传递消息。是用于进程间传递消息。持久对象持久对象(persistent object)可以被进程创建和撤销，可以被进程创建和撤销，也可能被移到后备存储器中。也可能被移到后备存储器中。4.5.3 Windows 2000/XP 的并发控制的并发控制同步对象同步对象Win32应用程序接口应用程序接口功能描述功能描述信号量信号量CreateSemaphore创建一个信号量变量，由参数给出初值。创建一个信号量变量，由参数给出初值。OpenSemaphore打开已经存在的信号量对象，返回句柄。打开已经存在的信号量对象，

60、返回句柄。ReleaseSemaphore释放对信号量对象的引用。释放对信号量对象的引用。互斥锁互斥锁CreateMutex创建一个新互斥锁对象。创建一个新互斥锁对象。OpenMutex打开已经存在的互斥锁对象，返回句柄。打开已经存在的互斥锁对象，返回句柄。ReleaseMutex释放对互斥对象的占有。释放对互斥对象的占有。事事 件件CreateEvent创建一个事件对象。创建一个事件对象。OpenEvent打开事件对象，返回句柄。打开事件对象，返回句柄。SetEvent设置事件对象为有信号状态。设置事件对象为有信号状态。ResetEvent重置事件对象。重置事件对象。PulseEvent探测