第七章并发程序设计语言

第七章并发程序设计语言内容摘要：

tion Critical Region简称 CCR)将共享变量显式地置于叫做资源的区域内 每个进程在自己的进程体内指明要访问的条件临界区，而同一临界区可出现在不同进程之中 (谁进谁用 ) 首先在资源中声明共享变量 : resource r(共享变量声明 )，例： resource sema( s:int :=n ) 使用共享变量： region r when B do S end region sema when s0 do s:= s1 end // P操作 region sema do s:= s+1 end // V操作 例 : 用 CCR实现的生产者与消费者 pragram PRODUCER_CONSUMER_CCR var buf:TYPE。 var empty:sema,full:sema。 resource sema:(empty := 1,full := 0)。 process PRODUCER [i:1..M]:: loop PRODUCER[i] 产生一条消息 m。 deposit: region sema when empty0 do empty := empty 1 end； buf := m。 region sema do full := full + 1 end。 end loop。 end。 process CONSUMER [j:1..N]:: loop fetch: region sema when full0 do full:= full 1 end。 m=buf； region sema do empty := empty + 1 end。 CONSUMER[j] 消费者取出的这条消息 m。 end loop。 end。 end PRODUCER_CONSUMER_CCR. 条件临界区评价 条件临界区最主要的优点是概念清晰。 此外 : • 无需辅助标志和变量即可描述共享变量的任何进程交互 • 程序编译时即可保证互斥 • 一个进程创建一个条件不需顾及其它条件是否与此条件有关 • 易于程序正确性证明 • 体现了共享数据传递的方便 它的致命缺点是低效 (和信号灯相比 )。 此外： • 进程和共享变量耦合太紧 • 临界区利写不利读，一多了就太散，因而也难修改 四、监控器 Dijkstra建议是把分散在整个程序中的 region语句进一步集中成为一个模块叫做监控器 (monitor)。 program monitor monitor Mname:: 共享数据声明并初始化。 proc op1 (形参表 1) is op1 体 end。 ... proc opn (形参表 n) is opn体 end。 end。 process Pname [i:1..N]:: 局部数据声明并初始化 begin : call (实参表 )。 : end begin 初始化，激活进程 end monitor. 例 : 有界缓冲区的监控器实现算法 monitor BOUNDED_BUFFER:: var buf[1..q]： TYPE。 var frout :=1， rear :=1， count := 0。 var not_full:cond； //当 count q示信为真 var not_empty:cond。 //当 count0 示信为真 proc deposit (data :TYPE) is while count = q do wait (not_full) end。 buf [rear] := data。 rear := (rear mod q) +1。 count := count+1。 signal (not_empty)。 end。 proc fetch (var result :TYPE) is while count=0 do wait (not_empty) end。 result := buf [front]。 front := (front mod q) +1。 count := count 1。 signal (not_full)。 end。 end BOUNDED_BUFFER. 以监控器实现条件同步的技术 (1) 复盖条件变量 (2) 传递条件 (3) 有无占先对竞争的并发进程影响是很大的 ,由于不占先在被唤醒进程执行之前 ,监控器不能拒绝另一进程进入它 .(见下例 *) (4) 为了防止条件信号被偷，发信号的进程直接将条件传入被唤醒的进程。 (见下例 **) (5) 会合同步 进程交互是客户 /服务器 (C/S)关系时 ,为此两交互进程必须会合 (rendezvou)才能得到服务。 如不能到达会合的同步点则要相互等待。 （ 见下例 ***） 例 * 以监控器作信号灯 monitor SEMAPHORE:: var s:= 0。 var pos:cond。 //当 s0， pos示信为真 proc P( ) is while s=0 do wait (pos) end。 s:= s1。 end。 proc V( ) is s := s+1； signal (pos)。 end。 end SEMAPHORE. 例 **： 以监控器实现的 FIFO信号灯 monitor SEMAPHORE:: var s=0。 var pos :cond； //当 V中 pos队列非空示真 proc P( ) is if s0 then s:= s1 endif。  if s=0 then wait(pos) endif。 end。 proc V( ) is if empty(pos) then s:= s+1 endif。  if not empty(pos) then signal(pos) endif。 end。 end SEMAPHORE. 注 :本例中 “ ” 号表示和前一个语句并行执行的语句 ,以下同 . 例 *** 贪睡的理发师的模拟解 monitor BARBER_SHOP:: var barber := 0,chair :=0,open =0。 var barber_available :cond //当 barber0 示真 var chair_occupied :cond //当 chair0示真 var door_open:cond //当 open=0示真 proc get_haircut( ) is //顾客调用 while barber=0 do wait (barber_available) end。 barber := barber1。 chair := chair+1； signal (chair_occupied)。 while open=0 do wait (door_open) end。 open := open1； signal (customer_left)。 end。 proc get_next_customer( ) is proc finished_cut ( ) is end BARBER_SHOP. 见下一页 proc get_next_customer( ) is //理发师调用 barber := barber+1； signal (barber_available)。 while chair=0 do wait (chair_occupied) end。 chair := chair1。 end。 proc finished_cut ( ) is //理发师调用 open := open+1； signal (door_open)。 while open0 do wait (customer_left) end。 end。 各种语言实现监控器时的原语语义差异 监控器有三个特征：第一，监控器封装了共享变量，共享变量仅能由监控器内的过程访问。 第二，监控器内的过程都是互斥地执行的。 因而共享变量不能并发访问。 第三，条件同步由wait和 signal操作实现 程序设计语言 Mesa包括以上三个特征。 UNIX采用上述条件同步。 监控器有时不一定必须互斥。 也可以采用其它办法实现条件同步。 (1) 实现条件同步的各种信号机制 • 自动信号 AS:只要 wait加上条件就可以不用 signal原语了 .即省去检查 signal是否执行的开销 ,程序员也不必操心是否用错。 • 信号和继续 SC:当无占先时发信号的进程继续执行 .直至它进入等待或返回之前 ,其它进程是不许进入监控器的。 modula3即采用此种机制。 • 信号和出口 SX:既然被占了先 ,发信号的进程也就不等了 .立即从监控器出口或从过程返回。 并发 Pascal即采用此种机制。 • 信号和等待 SW:发信号的进程被人占先之后处于监控器内等待，直到它能再次获得互斥访问，恢复执行。 Modula和并发 Euclid采用这种机制。 • 信号和急等 SU:发信号进程被人占先之后也要等待，但保证在监控器有新的进程进入之前先使它得到恢复。 Pascal_plus即采用这样的机制。 各种语言实现监控器时的原语语义差异 以上五种信号机制语义略有不同，但可从理论上证明它们是等价的。 即以一种机制可模拟另一 种机制。 实现费用不同，对某些类型问题表达的方便性不同。 也正是不同语言各自钟爱它们的原因。 (2) 嵌套监控器中的互斥 在磁盘调度器之类的应用中，一个进程首先要争取进入磁盘去寻址，找到地址后读 /写，这样就要设计两个监控器 一个管理粗的磁盘资源，进程进入或释放。 另一个管理读 /写区，进程互斥地读写。 这两个监控器是嵌套的 每一时刻只有一个进程进入监控器，调用某个过程，我们称它是闭式调用 .在嵌套监控器之中，这种方式容易引起死锁。 开式调用是若有嵌套调用发生时上层互斥自动解开，待调用返回后上层监控器又重新闭合 (获得 )互斥 •路径表达式 1974年 Campbell和 Habermann提出以路径表达式直接控制进程顺序的建议 监控器中派生出来的一个重要分枝。 路径表达式是就每一资源在其开始声明时 ,就在其上定义操作的约束。 path deposit,fetch end //deposit和 fetch并发执行 path deposit。 fetch end //deposit必须先于 fetch执行 path1:（ deposit； fetch) end //只能有一条路径 (但可多次执行此路径 ),两操作交替互斥执行 . path N:(1:(deposit)； 1:(fetch)) end //deposit和 fetch是一一对应地互斥激活 ,先执行 deposit,完成的 deposit个数不超过 N次 ,且可多于 fetch完成的个数 .由路径表达式指明的同步约束 ,编译时即可保证 . 优点是程序员可直接控制过程的执行 ,正文清晰。 但当同步化依赖过程参数或监控器的状态时，表达能力差。 消息是信息传递的单元 ,按 shannon的模型 ,信息源借助信道 (channel)向信息目标发送消息 .信道成了并发进程共享的资源 .信道是通信网的抽象 , 泛指进程间通信的路径 .信道由两个原语访问 : send, 程向信道发送一消息 ,通信就开始了 .需要该消息的进程 , 从信道上接受 (获取 )这条消息 .数据流也随发送者传递到接受者 . 基于消息传递的通讯机制 基于消息传递的通讯机制 由于信道本身不能存储 , 变量只能存放在各个进程中 , 因而不能共享地访问 ,所以也用不着互斥机制 .由于只有所在进程能考察变量情况 , 条件同步编程与基于共享变量的大不相同 .程序也不一定非要在一个处理器上执行 ,可以分布在多个处理器上 , 分布式程序因而得名 .反过来 , 分布式程序却可在单主机或多路处理器的 (分时 )系统上执行 .此时把信道改成共享存储就可以了 . 两类通信模式 基于消息传递的进程 , 通信虽然不靠共享存储间接实现， 然而通信时也有同步异步之分 • 同步消息传。