第4章-互斥同步与通信解析优秀PPT.ppt

《第4章-互斥同步与通信解析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第4章-互斥同步与通信解析优秀PPT.ppt（116页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机操作系统教程（第计算机操作系统教程（第2版）版）第四章第四章 互斥、同步与通讯互斥、同步与通讯并发进程(concurrent processes)进程互斥(mutual exclusion)进程同步(synchronization)进程高级通讯(communication)1计算机操作系统教程（第计算机操作系统教程（第2版）版）4.1 并发进程4.1.1 依次程序及其特性依次程序及其特性程序的依次性程序的依次性-内部依次性：内部依次性：P1:a1,a2,a3;P2:b1,b2,b3-外部依次性：情形外部依次性：情形1：a1,a2,a3,b1,b2,b3;情形情形2：b1,b2,b3,a1

2、,a2,a3依次程序设计的特性：依次程序设计的特性：-依次性：处理机严格按指令依次执行；依次性：处理机严格按指令依次执行；-封闭型：执行过程独占资源；封闭型：执行过程独占资源；-可再现性：程序执行的结果与执行速度无关。可再现性：程序执行的结果与执行速度无关。多个进程依次执行多个进程依次执行进程内全部指令按依次执行进程内全部指令按依次执行2计算机操作系统教程（第计算机操作系统教程（第2版）版）4.1 并发进程4.1.2 并发程序及其特性并发程序及其特性程序的并发性程序的并发性内部并发性：内部并发性：P2:b1,b2,b3;P2:b1,b3,b2外部并发性：情形外部并发性：情形1：a1,b1,b2

3、,a2,a3,b3;情形情形2：b1,b2,a1,b3,a2,a3并发程序的特性（带来好处也引发问题）：并发程序的特性（带来好处也引发问题）：-交叉性：不同的交叉可能导致不同的结果；交叉性：不同的交叉可能导致不同的结果；-非封闭性：进程的运行环境可被其他进程所变更；非封闭性：进程的运行环境可被其他进程所变更；-不行再现性：不行再现上次运行的结果。不行再现性：不行再现上次运行的结果。指令可以按依次也可以不按依次执行指令可以按依次也可以不按依次执行进程交叉执行进程交叉执行并发特性将引发一系列问题如互斥、死锁、饿死等并发特性将引发一系列问题如互斥、死锁、饿死等3计算机操作系统教程（第计算机操作系统教

4、程（第2版）版）4.1.2 与时间有关的错误与时间有关的错误例：图书借阅系统例：图书借阅系统 （x:某种某种书册数，设当前书册数，设当前x=1.）终端终端1（进程p1）：终端终端2（进程p2）：do do 等待借书者等待借书者；等待借书者等待借书者；IF(x=1)IF(x=1)x=x-1;x=x-1;借书借书 借书借书 Else 无书无书 Else 无书无书 while(1)while(1)12344计算机操作系统教程（第计算机操作系统教程（第2版）版）4.1.2 与时间有关的错误与时间有关的错误(Cont.)错误缘由之错误缘由之1：进程执行交叉进程执行交叉(进程推动速度不同进程推动速度不同)

5、;错误缘由之错误缘由之2：涉及公共变量涉及公共变量(x)。Remarks:某些交叉导致结果不正确某些交叉导致结果不正确;必需去掉导致不正确结果的交叉。必需去掉导致不正确结果的交叉。5计算机操作系统教程（第计算机操作系统教程（第2版）版）4.2 进程互斥进程互斥(mutual exclusion)进程间发生的一种间接性相互作用。进程间发生的一种间接性相互作用。4.2.1 共享变量与临界区共享变量与临界区4.2.2 临界区域与进程互斥临界区域与进程互斥4.2.3 进程互斥的实现进程互斥的实现4.2.4 多处理机环境下的互斥多处理机环境下的互斥6计算机操作系统教程（第计算机操作系统教程（第2版）版）

6、4.2.1 共享变量与临界区域共享变量与临界区域共享变量（共享变量（shared variable）多个进程都须要访问的变量。多个进程都须要访问的变量。临界区（临界区（critical region）访问共享变量的程序段。访问共享变量的程序段。一组共享变量一组共享变量CR1CR2CRn.程序段1程序段2程序段n7计算机操作系统教程（第计算机操作系统教程（第2版）版）共享变量与临界区表示共享变量与临界区表示共享变量共享变量:shared 临界区域临界区域:region do 语句语句例子：例子：shared x1,x2;shared y1,y2;region x1,x2 do region y1

7、,y2 do 临界区可以嵌套临界区可以嵌套8计算机操作系统教程（第计算机操作系统教程（第2版）版）4.2.2 临界区域与进程互斥临界区域与进程互斥定义：两个或两个以上进程不能同时进入关于同一组共定义：两个或两个以上进程不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，享变量的临界区域，否则可能发生与时间有关的错误，这种现象称为进程互斥。这种现象称为进程互斥。二层涵义：二层涵义：（1）不容很多个进程同时进入关于同一组共享变）不容很多个进程同时进入关于同一组共享变量的相同的临界区域；量的相同的临界区域；（2）不容很多个进程同时进入关于同一组共享变）不容很多个进程同时进入关于同

8、一组共享变量的不同的临界区域。量的不同的临界区域。Remarks:互斥是相对于公共变量而言的。互斥是相对于公共变量而言的。9计算机操作系统教程（第计算机操作系统教程（第2版）版）嵌套临界区域嵌套临界区域 shared x;shared y;region x do region y do .region y do region x do .临界区可以嵌套：临界区可以嵌套：已进入临界区域已进入临界区域可能引发死锁！可能引发死锁！10计算机操作系统教程（第计算机操作系统教程（第2版）版）4.2.3 进程互斥的实现进程互斥的实现FrameworkRepeat critical section rema

9、inder sectionUntil falseentry sectionexit section11计算机操作系统教程（第计算机操作系统教程（第2版）版）4.2.3 进程互斥的实现进程互斥的实现实现临界区管理的三个原则：实现临界区管理的三个原则：正确性原则：正确性原则：随意时刻至多只能有一个进程处于同一组共享变量的临随意时刻至多只能有一个进程处于同一组共享变量的临界区域中；界区域中；公允性原则：公允性原则：一个恳求进入临界区的进程应当在有限等待时间内获得一个恳求进入临界区的进程应当在有限等待时间内获得进入临界区的机会；进入临界区的机会；进展性原则：进展性原则：当临界区空闲时，竞争进入临界区的

10、多个进程在有限的当临界区空闲时，竞争进入临界区的多个进程在有限的时间内确定下一个进入临界区的进程。时间内确定下一个进入临界区的进程。临界区调度原则：临界区调度原则：！临界区空闲，想进入的应能进入；！临界区空闲，想进入的应能进入；！临界区不空闲，进程应等待；！临界区不空闲，进程应等待；！进程离开临界区时，应能唤醒等待进入的进程。！进程离开临界区时，应能唤醒等待进入的进程。12计算机操作系统教程（第计算机操作系统教程（第2版）版）4.2.3.1 进程互斥的软件实现进程互斥的软件实现完全用程序实现，不需特殊硬件指令支持。可用于单CPU和多CPU环境中。有忙式等待问题。Busy waiting“运行运

11、行”或或“就绪就绪”13计算机操作系统教程（第计算机操作系统教程（第2版）版）Lamport面包店算法面包店算法算法思想：设置一个发号者，按算法思想：设置一个发号者，按0,1,2,发号。想进入临发号。想进入临界区的进程抓号，抓到号之后按由小到大的次序依次进入。界区的进程抓号，抓到号之后按由小到大的次序依次进入。Problem:两个进程可能抓到相同的号。两个进程可能抓到相同的号。Why?为保证抓到不同的号，须要互斥机制。为保证抓到不同的号，须要互斥机制。Resolution:若抓到相同的号，按进程编号依次进入。若抓到相同的号，按进程编号依次进入。Definition:(a,b)(c,d)if(a

12、c)or(a=c and bd)14计算机操作系统教程（第计算机操作系统教程（第2版）版）Lamport面包店算法面包店算法int choosing n;表示进程是否在抓号表示进程是否在抓号int number n;记录进程所抓到的号码记录进程所抓到的号码Pi 进入进入：do choosingi=1;numberi=maxnumber0,numbern-1+1;choosingi=0;for(j=0;jn;j+)While(choosingj)skip;While(numberj0)&(numberj,j)(numberi,i)skip;正在抓号正在抓号抓到号码抓到号码抓号完毕抓号完毕比较号码

13、比较号码确定谁进入确定谁进入忙等待忙等待15计算机操作系统教程（第计算机操作系统教程（第2版）版）Lamport面包店算法面包店算法(Cont.)临界区临界区(CS)其余部分其余部分while(1);变量变量choosing的作用：的作用：P1：抓到：抓到1;P2：抓到：抓到1;正确次序：正确次序：P1，P2，P3P3：抓到：抓到2;可能按可能按P2,P3,P1次序进入次序进入！numberi=0；进入临界区进入临界区出临界区，号码清零出临界区，号码清零16计算机操作系统教程（第计算机操作系统教程（第2版）版）Eisenberg/Mcguire算法（令牌法）算法（令牌法）enum flag n

14、;(取值：取值：idle,want_in,in_cs);int turn;（取值：（取值：0.n-1，初始随意）初始随意）0 i turnn-1先于先于i先于先于iflagi=idle:进程进程Pi不想进入临界区不想进入临界区flagi=want_in:进程进程Pi想进入临界区想进入临界区flagi=in_cs:进程进程Pi想进入或已进入临界想进入或已进入临界区区17计算机操作系统教程（第计算机操作系统教程（第2版）版）Eisenberg/Mcguire算法算法Pi进入进入:Do do flagi=want_in;我要进入我要进入 j=turn;取令牌取令牌 While(j!=i)令牌是我的？

15、令牌是我的？If(flagj!=idle)j=turn;不是，有令牌的要进？不是，有令牌的要进？Else j=(j+1)%n;有令牌的不进，看下一个有令牌的不进，看下一个 flagi=in_cs;j=i令牌轮到我，设置标记表示要进令牌轮到我，设置标记表示要进 j=0;While(jvalue-;if(s-valuequeue);asleep(s-queue):(1)执行此操作进程的执行此操作进程的PCB入入s-queue尾（状态改为等待）；尾（状态改为等待）；(2)转处理机调度程序。转处理机调度程序。原语：一段不行间断执行的程序34计算机操作系统教程（第计算机操作系统教程（第2版）版）V操作原

16、语操作原语V操作原语：操作原语：void V(semaphore*s)s-value+;if(s-valuequeue);wakeup(s-queue)S-queue链头链头PCB出等待队列，进入就绪队列（状态改出等待队列，进入就绪队列（状态改为就绪）。为就绪）。35计算机操作系统教程（第计算机操作系统教程（第2版）版）规定和结论规定和结论对于信号灯变量的规定：对于信号灯变量的规定：必需置一次初值，只能置一次初值，初值必需置一次初值，只能置一次初值，初值=0;只能执行只能执行P操作和操作和V操作，全部其它操作非法。操作，全部其它操作非法。几个有用的结论：几个有用的结论：当当s-value=0时

17、，时，s-queue为空；为空；当当s-valuevalue|为队列为队列s-queue的长度；的长度；当当s-value初初=1时，可以实现进程互斥；时，可以实现进程互斥；当当s-value初初=0时，可以实现进程同步；时，可以实现进程同步；当当s-value初初=正整数，可以用来管理同类资源。正整数，可以用来管理同类资源。36计算机操作系统教程（第计算机操作系统教程（第2版）版）用信号灯实现进程同步用信号灯实现进程同步一般形式一般形式一般形式一般形式:Semaphore s;(initial value 0)Semaphore s;(initial value 0)P(S)后动作后动作先动

18、作先动作 V(S)P1:P2:37计算机操作系统教程（第计算机操作系统教程（第2版）版）用信号灯实现进程同步用信号灯实现进程同步例子：司机例子：司机-售票员问题：售票员问题：semaphore s1,s2;(initial value 0)司机活动：司机活动：售票员活动：售票员活动：Repeat Repeat P(S1)关车门关车门 启动车辆启动车辆 V(S1)正常行驶正常行驶 售售 票票 到站停车到站停车 P(S2)V(S2)开车门开车门 Until false Until false38计算机操作系统教程（第计算机操作系统教程（第2版）版）例例1.生产者生产者/消费者问题消费者问题 0 1

19、 k-1箱子，容量箱子，容量k，缓冲区缓冲区 B:Array0.k-1Of item生产者生产者消费者消费者生产物品生产物品放入放入B中中B中取物品中取物品消费之消费之39计算机操作系统教程（第计算机操作系统教程（第2版）版）环形缓冲区环形缓冲区10K-1in(in+1)%kout(out+1)%k40计算机操作系统教程（第计算机操作系统教程（第2版）版）问题分析问题分析生产者活动生产者活动：消费者活动消费者活动：do do 加工一件物品；加工一件物品；箱中取一物品；箱中取一物品；物品放入箱中；物品放入箱中；消耗这件物品；消耗这件物品；while(1)；while(1)；资源：资源：箱子（同种

20、组合）箱子（同种组合）资源：资源：物品（同种组合）物品（同种组合）Semaphore S1;semaphore S2;S1.value=k;S2.value=0;放前：放前：P（S1）取前：取前：P（S2）放后：放后：V（S2）取后：取后：V（S1）41计算机操作系统教程（第计算机操作系统教程（第2版）版）同步同步生产者活动生产者活动：消费者活动消费者活动：Repeat Repeat 加工一件物品加工一件物品 P(S2)P(S1)箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(S1)V(S2)消耗这件物品消耗这件物品 Until false Until false对对B（缓冲区）和和i

21、n,out（指针）的互斥的互斥：semaphore mutex;(mutex.value=1)42计算机操作系统教程（第计算机操作系统教程（第2版）版）互斥互斥生产者活动：生产者活动：消费者活动：消费者活动：Repeat Repeat 加工一件物品加工一件物品 P(S2)P(S1)P(mutex)P(mutex)箱中取一物品箱中取一物品 物品放入箱中物品放入箱中 V(mutex)V(mutex)V(S1)V(S2)消耗这件物品消耗这件物品 Until false Until false43计算机操作系统教程（第计算机操作系统教程（第2版）版）程序清单程序清单Program producers_

22、consumers;itemType bufferk;semaphore S1=k;semaphore S2=0;int in=0;int out=0;semaphore mutex=1;void producer()while(1)produceItem(&item);P(S1);P(mutex);Bufferin=item;in=(in+1)%k;V(mutex);V(S2)void consumer()itemType temp;while(1)P(s2);P(mutex);temp=bufferout;out=(out+1)%k;V(mutex);V(S1);44计算机操作系统教程（第

23、计算机操作系统教程（第2版）版）程序（续前）程序（续前）Fork(producer,0);fork(producer,m-1);Fork(consumer,0);fork(consumer,n-1);45计算机操作系统教程（第计算机操作系统教程（第2版）版）例例2.读者读者/写者问题写者问题P.T.Courtois 1971Communication of the ACM,Vol.14,667-669.ACM:Association for Computing Machinery解法1：写者可能饿死（允许写者饿死）解法2：写者优先（写者优先于读者）生产者生产者/消费者问题：消费者问题：多个进程

24、协作，各有各的箱子；多个进程协作，各有各的箱子；读者读者/写者问题：写者问题：多个进程协作，共享同一箱子。多个进程协作，共享同一箱子。46计算机操作系统教程（第计算机操作系统教程（第2版）版）例例2.读者读者/写者问题写者问题问题描述:一组公共数据DB R1 Rm W1.Wn要求：（1）R-R可以同时 （2）R-W不行同时 （3）W-W不行同时accessing47计算机操作系统教程（第计算机操作系统教程（第2版）版）正确解法（可能产生写者饥饿）正确解法（可能产生写者饥饿）Int readCount=0;semaphore r_w_w=1;semaphore mutex=1;Reader()w

25、hile(1)P(&mutex);read_count=read_count+1;If(read_count=1)P(&r_w_w);V(&mutex);P(&mutex);read_count=read_count-1;If(read_count=0)V(&r_w_w);V(&mutex);读者加计数，互斥读者加计数，互斥有写者，读者等待于此信号灯有写者，读者等待于此信号灯多个读者不互斥多个读者不互斥读者减计数，互斥读者减计数，互斥若无读者，唤醒等待的写者若无读者，唤醒等待的写者只有一个读者进入计数只有一个读者进入计数其他要进入的读者等待其他要进入的读者等待48计算机操作系统教程（第计算机操

26、作系统教程（第2版）版）程序续前程序续前Writer()While(1)P(&r_w_w);V(&r_w_w);Fork(reader,0);fork(reader,m-1);Fork(writer,0);fork(writer,n-1);写者操作临界区域写者操作临界区域如有读者，写者等待于此信号灯如有读者，写者等待于此信号灯如已有写者，其他写者等待于此如已有写者，其他写者等待于此写结束，唤醒其他写者或读者写结束，唤醒其他写者或读者49计算机操作系统教程（第计算机操作系统教程（第2版）版）分析：分析：问题问题：读者源源不断，读者源源不断，read_count不归不归0，写者，写者会被饿死。会被

27、饿死。策略策略：一旦有写者等待，新到达读者等待，正在一旦有写者等待，新到达读者等待，正在读的读者都结束后，写者进入。读的读者都结束后，写者进入。50计算机操作系统教程（第计算机操作系统教程（第2版）版）4.3.4 条件临界区条件临界区Conditional Critical Region背景背景PV操作低级，简洁用错操作低级，简洁用错条件临界区形式条件临界区形式region r when b do sR：共享变量；：共享变量；b：布尔表达式；：布尔表达式；s：语句：语句进入条件临界区执行进入条件临界区执行S的条件的条件没有其它进程处于与没有其它进程处于与r相关的条件临界区中相关的条件临界区中进

28、入进入s时时b为真（为真（true）遗忘遗忘P不能实现互斥不能实现互斥遗忘遗忘V可能导致死锁可能导致死锁51计算机操作系统教程（第计算机操作系统教程（第2版）版）条件临界区条件临界区实现互斥实现互斥region v when true do sCCR与与PV操作的等价性操作的等价性(证明从略）证明从略）用CCR可以实现PV操作用PV操作可以实现CCR缺点：缺点：效率低可能产生忙等待52计算机操作系统教程（第计算机操作系统教程（第2版）版）4.3.5 管程（管程（Monitor）PV操作：操作：分散式同步机制：共享分散式同步机制：共享变量操作，变量操作，PV操作，分操作，分散在整个系统中或各个散

29、在整个系统中或各个进程中。进程中。缺点：缺点：可读性差；可读性差；正确性不易保证；正确性不易保证；不易修改。不易修改。优点：优点：高效，敏捷。高效，敏捷。管程：管程：集中式同步工具：共享变集中式同步工具：共享变量及其全部相关操作集中量及其全部相关操作集中在一个摸块中。在一个摸块中。优点：优点：可读性好；可读性好；正确性易于保证；正确性易于保证；易于修改。易于修改。缺点：缺点：不甚敏捷，效率略低。不甚敏捷，效率略低。53计算机操作系统教程（第计算机操作系统教程（第2版）版）4.3.5.1 管程的提出管程的提出70年头初年头初,ByE.W.Dijkstra,C.A.R.Hoare,P.B.Hans

30、en.背景背景:结构化程序设计（结构化程序设计（Structured programming）基于管程作为同步机制的高级语言基于管程作为同步机制的高级语言Concurrent Pascal(Hansen)Modula(With)MesaMod*Concurrent EuclidXCY54计算机操作系统教程（第计算机操作系统教程（第2版）版）管程的提出管程的提出(Cont.)构造操作系统的构造操作系统的PCM方法方法P：processC：classM：monitorExample systemsolo55计算机操作系统教程（第计算机操作系统教程（第2版）版）4.3.5.2 管程形式（管程形式（p

31、ascal语言描述）语言描述）Type monitor_name=MONITOR 共享变量说明 define 本管程内定义，本管程外可调用的过程（函数）名表；use 本管程外定义，本管程内可调用的过程（函数）名表；Procedure 过程名（形参表）；过程局部变量说明 Begin 语句序列 End;56计算机操作系统教程（第计算机操作系统教程（第2版）版）管程形式管程形式(Cont.)Function 函数名（形参表）:值类型；函数局部变量说明 Begin 语句序列；End;.Begin 共享变量初始化语句序列；End;语言特点语言特点：(1)模块化（modularized）;(2)抽象数据类

32、型（abstract data type）;(3)信息掩蔽（information hiding）.57计算机操作系统教程（第计算机操作系统教程（第2版）版）4.3.5.3 管程语义管程语义管程的共享变量在管程外部不行见，外部只能通过调用管管程的共享变量在管程外部不行见，外部只能通过调用管程中的外部过程（函数）间接的访问共享变量；程中的外部过程（函数）间接的访问共享变量；为保证对共享变量操作的数据完整性，规定管程互斥进入；为保证对共享变量操作的数据完整性，规定管程互斥进入；管程中有等待管程中有等待/唤醒机制，等待时释放管程的互斥权，唤唤醒机制，等待时释放管程的互斥权，唤醒时（醒时（P唤醒唤醒Q

33、），有如下三种可能的解决方法：），有如下三种可能的解决方法：P等待，等待，Q接着，直到接着，直到Q退出或等待；退出或等待；(Hoare)Q等待，等待，P接着，直到接着，直到P退出或等待；退出或等待；(Java)唤醒是管程中可执行的最终一个操作。（唤醒是管程中可执行的最终一个操作。（Hansen)58计算机操作系统教程（第计算机操作系统教程（第2版）版）Hoare管程设施管程设施三个等待队列三个等待队列入口等待队列：入口等待队列：每个管程变量一个，用于排队进入；每个管程变量一个，用于排队进入；紧急等待队列：紧急等待队列：每个管程变量一个，用于唤醒等待；每个管程变量一个，用于唤醒等待；内部等待队列

34、：内部等待队列：var c:condition;可依据须要定义多个，用于设可依据须要定义多个，用于设置等待条件。置等待条件。59计算机操作系统教程（第计算机操作系统教程（第2版）版）管程队列管程队列PCBPCBxPCBPCByPCBPCBPCBPCB入口队列紧急队列初始化代码条条件件队队列列操作操作 操作操作操作操作共享变量共享变量互斥进入管程互斥进入管程离开管程时唤醒离开管程时唤醒60计算机操作系统教程（第计算机操作系统教程（第2版）版）进入与离开进入与离开进入管程：进入管程：申请管程互斥权。离开管程：离开管程：如紧急等待队列非空，唤醒第一个等待者；否则开放管程。61计算机操作系统教程（第计

35、算机操作系统教程（第2版）版）条件变量操作条件变量操作Var c:condition;wait(c):如紧急队列非空，唤醒第一个等待者，否则释放管程互斥权;执行此操作的进程（线程）进入c链尾。signal(c):如c链空，相当空操作。否则唤醒第一个，执行此操作的进程（线程）进入紧急队列。62计算机操作系统教程（第计算机操作系统教程（第2版）版）4.3.5.4 管程的运用管程的运用读者读者/写者问题（写优先）写者问题（写优先）哲学家就餐问题（哲学家就餐问题（another approach)Sleepy barbers problemDisk head scheduler Single reso

36、urce management 63计算机操作系统教程（第计算机操作系统教程（第2版）版）例例1.读者读者/写者问题写者问题写者优先（偏向写者的解法）写者优先（偏向写者的解法）TYPE reaers_and_writers=MONITOR;Var rq,wq:condition;reading_count,write_count:integer;Define start_read,finish_read,start_write,finish_write;64计算机操作系统教程（第计算机操作系统教程（第2版）版）例例1.读者读者/写者问题写者问题Procedure start_read;Begi

37、n If write_count0 Then wait(rq);reading_count+;signal(rq);End;Procedure finish_read;Begin reading_count-;If reading_count=0 Then signal(wq)End;65计算机操作系统教程（第计算机操作系统教程（第2版）版）例例1.读者读者/写者问题写者问题Procedure start_write Begin write_count+;If(write_count1)or (reading_count0)Then wait(wq)End;Procedure finish_w

38、rite;Begin write_count-;If write_count0 Then signal(wq)Else signal(rq)End;66计算机操作系统教程（第计算机操作系统教程（第2版）版）例例1.读者读者/写者问题写者问题Begin reading_count:=0;write_count:=0;End;读者：读者：Readers_and_writers.start_read;读操作；Readers_and_writers.finish_read;写者：写者：Reader_and_writers.start_write;写操作；Reader_and_writers.finis

39、h_write;调用管程内的过程调用管程内的过程67计算机操作系统教程（第计算机操作系统教程（第2版）版）例：磁头引臂调度问题例：磁头引臂调度问题0 1 199updown磁头引臂扇区略略68计算机操作系统教程（第计算机操作系统教程（第2版）版）调度算法调度算法FCFS（first come first serve）公允公允效率低效率低SSTF（shortest seek time first）效率高效率高磁道卑视磁道卑视SCAN（elevator algorithm）效率较高，较公允效率较高，较公允略略69计算机操作系统教程（第计算机操作系统教程（第2版）版）Hansen管程实现管程实现SC

40、AN算法算法外部过程：外部过程：申请：申请：require(dest:0.199)释放：释放：release()运用方式：运用方式：require(dest);IO操作操作 -(管程外操作管程外操作)release略略70计算机操作系统教程（第计算机操作系统教程（第2版）版）管程实现管程实现SCAN算法算法TYPE disk_head_shared=MONITOR Var busy:BOOLEAN;headpos:0.199;direction:(up,down);cylinder:ARRAY0.199Of condition;count:ARRAY0.199Of integer;Define

41、 Apply,release;略略71计算机操作系统教程（第计算机操作系统教程（第2版）版）管程实现管程实现SCAN算法算法 PRPCEDURE require(dest:0.199);Begin If busy Then Begin countdest:=countdest+1;wait(cylinderdest)End busy:=true;If destheadpos Then direction:=up;headpos:=dest End;略略72计算机操作系统教程（第计算机操作系统教程（第2版）版）管程实现管程实现SCAN算法算法 Procedure upscan;Var I:0.2

42、00;Begin I:=headpos;While(I=199)and(countI=0)Do I:=I+1;If I=0)and(countI=0)Do I:=I-1;If I=0 Then Begin countI:=countI-1;signal(cylinderI)End End;略略74计算机操作系统教程（第计算机操作系统教程（第2版）版）管程实现管程实现SCAN算法算法Procedure release;Begin busy:=false;If direction=up Then Begin upscan;downscan End Else Begin downscan;upsca

43、n End End;略略75计算机操作系统教程（第计算机操作系统教程（第2版）版）管程实现管程实现SCAN算法算法Procedure initialize;Var I:0.199;Begin busy:=false;headpos:=0;direction:=up;For I:=0 To 199 Do countI:=0 EndBegin initialize End;略略76计算机操作系统教程（第计算机操作系统教程（第2版）版）4.3.5.5 管程与管程与PV操作的等价性操作的等价性用PV操作可以构造管程用管程可以构造PV操作Implementing PV operationsusing m

44、onitors is trivial 略略77计算机操作系统教程（第计算机操作系统教程（第2版）版）用管程构造用管程构造PV操作操作TYPE semaphore=MONITOR(init_value)VAR c:condition;count:integer;DEFINE P,V;PROCEDURE P;BEGIN count:=count-1;IF count0 THEN wait(c);END;PROCEDURE V;BEGIN count:=count+1;IF count 0 THEN BEGIN urgent_count:=urgent_count-1;V(urgent)ELSE V

45、(mutex);P(s);略略80计算机操作系统教程（第计算机操作系统教程（第2版）版）用用PV操作构造管程操作构造管程管程管程信号灯与信号灯与PV操作操作唤醒操作唤醒操作Signal(c)IF count0 THEN BEGIN count:=count-1;urgent_count:=urgent_count+1;V(s);P(urgent)END进入管程进入管程P(mutex);离开管程离开管程IF urgent_count0 THEN BEGIN urgent_count:=urgent_count-1;V(urgent)ENDELSE V(mutex);略略81计算机操作系统教程（第

46、计算机操作系统教程（第2版）版）Windows2000/XP互斥互斥同步机制同步机制Mutex(OS API)CreateMutex,/创建互斥对象，返回句柄OpenMutex,/打开并返回存在对象句柄ReleaseMutex;/释放对互斥对象的占用semaphore(OS API)CreateSemaphore,/创建信号量OpenSemaphore,/返回已存在信号量句柄ReleaseSemaphore;/释放对信号量的占用82计算机操作系统教程（第计算机操作系统教程（第2版）版）Windows2000/XP互斥同步机制互斥同步机制Event(OS API)CreateEvent,Open

47、Event,SetEvent,ResetEvent,PulseEvent.83计算机操作系统教程（第计算机操作系统教程（第2版）版）Windows2000/XP互斥同步机制互斥同步机制CRITICAL_SECTION类型类型InitializeCriticalSection:初始化EnterCriticalSection:等待进入TryEnterCriticalSection:非等待，失败返回0LeaveCriticalSection:离开DeleteCriticalSection:清除84计算机操作系统教程（第计算机操作系统教程（第2版）版）4.4 进程高级通讯进程高级通讯进程通讯：进程之间

48、的互斥、同步及信息交换。进程通讯：进程之间的互斥、同步及信息交换。低级通讯（简洁信号）低级通讯（简洁信号）进程互斥进程互斥进程同步进程同步高级通讯（大宗信息）高级通讯（大宗信息）高级通讯（一般状况下，进程通讯专指进程间的高级高级通讯（一般状况下，进程通讯专指进程间的高级通讯）通讯）共享内存共享内存 vs.消息传递消息传递干脆通讯干脆通讯 vs.间接通讯间接通讯对称性通讯对称性通讯 vs.非对称性通讯非对称性通讯有缓冲通讯有缓冲通讯 vs.无缓冲通讯无缓冲通讯4.4.1 进程通讯概念进程通讯概念85计算机操作系统教程（第计算机操作系统教程（第2版）版）P1 4.4.2 进程通讯模式进程通讯模式1

49、.共享内存模式共享内存模式(shared memory)：2.消息传递模式消息传递模式(message passing)：P2OS供应：供应：（1）公共内存）公共内存（2）互斥同步机制）互斥同步机制P1P2MsendreceiveOS供应通讯原语供应通讯原语干脆：进程干脆：进程-进程进程间接：进程间接：进程-信箱信箱-进程进程86计算机操作系统教程（第计算机操作系统教程（第2版）版）4.4.3 干脆方式干脆方式干脆方式：通讯进程间彼此直呼其名（指定对方名字）干脆方式：通讯进程间彼此直呼其名（指定对方名字）对称形式对称形式(一对一方式一对一方式)send(R,M)：将消息：将消息M发给进程发给进

50、程Rreceive(S,N)：进程：进程S接收消息至接收消息至NSend(R,M).Receive(S,N).S:R:87计算机操作系统教程（第计算机操作系统教程（第2版）版）干脆方式干脆方式receive(pid,N).send(R,M1).send(R,M2).非对称形式非对称形式(多对一方式多对一方式)send(R,M)：将消息M发给进程Rreceive(pid,N)：接收消息至N，返回pidC/S 模式R:S1:S2:纪录发送进程标识纪录发送进程标识88计算机操作系统教程（第计算机操作系统教程（第2版）版）4.4.3.1 有缓冲途径有缓冲途径PCBsend(R,M)Size：消息长度消