计算机操作系统 第三版 2.3进程同步

1、1 2.3进程同步进程同步 n引入并发后，进程的执行结果受到进程间相对执行速引入并发后，进程的执行结果受到进程间相对执行速 度的影响。度的影响。 n如何实现进程的执行结果与相对执行速度无关。如何实现进程的执行结果与相对执行速度无关。 n2.3.1 进程同步的基本概念进程同步的基本概念 n2.3.2 信号量机制信号量机制 n2.3.3 信号量的应用信号量的应用 2 2.3.1进程同步的基本概念进程同步的基本概念 n并发执行的进程，由于并发执行的进程，由于资源共享资源共享和和进程合作进程合作，相互间存在，相互间存在 着制约关系。着制约关系。 如何控制和协调并发进程异步执行的时序？如何控制和协调并发

2、进程异步执行的时序？ 进程的互斥进程的互斥/同步机制同步机制 进程之间如何互相联系，传递信息？进程之间如何互相联系，传递信息？ 进程的通信进程的通信 n进程同步的主要任务：是使并发执行的诸进程间能有效地进程同步的主要任务：是使并发执行的诸进程间能有效地 共享资源和相互合作，从而使程序的执行具有可再现性。共享资源和相互合作，从而使程序的执行具有可再现性。 n用于实现同步的机制用于实现同步的机制同步机制同步机制 3 A A进程进程 进程间的两种制约关系进程间的两种制约关系间接制约间接制约 B B n彼此本无关，但是由于竞争使用同一共享资源而产生相彼此本无关，但是由于竞争使用同一共享资源而产生相 互

3、制约的关系。互制约的关系。 n因因共享互斥性资源，一个进程在执行期间应具有排斥其共享互斥性资源，一个进程在执行期间应具有排斥其 他进程的能力。这种行为称为他进程的能力。这种行为称为互斥互斥( (Mutual Exclusion) ) A进程进程B进程进程 n进程进程资源资源进程进程 n间接制约源于间接制约源于资源共享资源共享。 4 进程间的两种制约关系进程间的两种制约关系直接制约直接制约 进程之间由于相互合作，使得执行时要有确定的次序进程之间由于相互合作，使得执行时要有确定的次序 相互清楚对方的存在及其作用相互清楚对方的存在及其作用 往往是几个进程往往是几个进程共同完成一个任务共同完成一个任务

4、 进程进程进程进程 这种因进程合作而产生的制约关系称为这种因进程合作而产生的制约关系称为进程的同步进程的同步 缓冲区缓冲区 输入进程输入进程 计算进程计算进程 n直接制约源于直接制约源于进程合作进程合作。 5 总结总结 n受到制约的这些进程，受到制约的这些进程，不管是受到直接制约还是受到不管是受到直接制约还是受到 间接制约，执行时都要依次执行。间接制约，执行时都要依次执行。 n或者说并发执行的同时在受到制约的语句部分要顺序或者说并发执行的同时在受到制约的语句部分要顺序 执行。执行。 n所不同的是，受到直接制约的要求有明确的执行次序。所不同的是，受到直接制约的要求有明确的执行次序。 同步同步 S

5、ynchronization n受到间接制约的进程，谁先执行都可以，但一旦一个受到间接制约的进程，谁先执行都可以，但一旦一个 先执行，其余需要等待。先执行，其余需要等待。互斥互斥 Mutual Exclusion n从某种意义上说，互斥的实质就是同步，或者说，互从某种意义上说，互斥的实质就是同步，或者说，互 斥是同步的一种特殊形式。斥是同步的一种特殊形式。 6 2. 临界资源临界资源 n指在一段时间内只允许一个进程访问的资源。指在一段时间内只允许一个进程访问的资源。 n临界资源具有临界资源具有一次只允许一个进程一次只允许一个进程使用的属性。使用的属性。 计算机的许多计算机的许多硬件资源硬件资源

6、都被处理成临界资源，如都被处理成临界资源，如 打印机、磁带机等。打印机、磁带机等。 系统中还有系统中还有许多软资源许多软资源，如共享变量、表格、队，如共享变量、表格、队 列、栈等也被处理成临界资源。列、栈等也被处理成临界资源。 A:A: B: B: N=N+1 N=N+1； PRINT NPRINT N； N=0 N=0； 7 p1 p2 p3 使用使用 打印机打印机 使用使用 打印机打印机 共享共享 变量变量 临界区临界区 n每个进程中，每个进程中，访问临界资源的那段代码称为临界区访问临界资源的那段代码称为临界区。 不允许多个并发进程交叉执行的一段程序不允许多个并发进程交叉执行的一段程序。

7、临临 界界 区区 这些程序段分散在不同的进程。这些程序段分散在不同的进程。 n临界区可按不同的共享资源划分成不同的集合。临界区可按不同的共享资源划分成不同的集合。如：如： p1,p2 同属一个集合中的临界区不允许并发执行，必须互斥。同属一个集合中的临界区不允许并发执行，必须互斥。 8 临界区：访问临界资源临界区：访问临界资源 临界区的代码构成临界区的代码构成 void P1 while(true) /preceding code /critical section /following code entercritical 进入区进入区: :申请进入临界区申请进入临界区 进入前，先测试临界资源

8、是否被占用进入前，先测试临界资源是否被占用; ; 未占用，则进入，同时设被占用标志。未占用，则进入，同时设被占用标志。 已占用，则不能进入。已占用，则不能进入。 exitcritical 退出区退出区: :释放临界资源。释放临界资源。 修改资源标志为未占用修改资源标志为未占用 9 互斥机制应遵循的规则互斥机制应遵循的规则 用来实现互斥的同步机制应遵循下述四条规则：用来实现互斥的同步机制应遵循下述四条规则： n空闲让进：空闲让进：无进程处于临界区内时，可让一个申请进无进程处于临界区内时，可让一个申请进 入该临界区的进程进入。入该临界区的进程进入。 n忙则等待：忙则等待：临界区内有进程时，申请进入

9、临界区的进临界区内有进程时，申请进入临界区的进 程必须等待。程必须等待。 n有限等待：有限等待：进程进入临界区的请求，必须在有限的时进程进入临界区的请求，必须在有限的时 间内满足。间内满足。 n让权等待：让权等待：等待进入临界区的进程，必须立即释放等待进入临界区的进程，必须立即释放 CPU。 10 n并发进程间的相互制约关系从本质上说是由于争夺和共并发进程间的相互制约关系从本质上说是由于争夺和共 享资源产生的。享资源产生的。 n信号量：管理资源用的系统变量信号量：管理资源用的系统变量，在信号量基础上在信号量基础上定义定义 两个操作原语：两个操作原语： Wait(P操作操作)、Signal(V操

10、作操作)，是一种是一种 广泛应用的互斥同步机制广泛应用的互斥同步机制。 2.3.2 信号量机制信号量机制 Edsgar Wybe Edsgar Wybe DijkstraDijkstra（埃德斯加埃德斯加狄克斯特拉）狄克斯特拉） 19721972年年ACMACM图灵奖（图灵奖（ACM Turing AwardACM Turing Award）获得者获得者 “一个程序的易读性和易理解性同其中所包含的一个程序的易读性和易理解性同其中所包含的 无条件转移控制的个数成反比关系。无条件转移控制的个数成反比关系。” 提出结构化程序设计思想提出结构化程序设计思想 11 12 n信号量定义：信号量定义：1个数

11、据结构个数据结构+2个基本操作个基本操作 struct semaphore int value; /表示某种资源的数量表示某种资源的数量 PCB *queue;/等待在该信号量上的进程等待在该信号量上的进程 P(semaphore s); /消费唤醒操作消费唤醒操作 S(semaphore s); /产生唤醒操作产生唤醒操作 13 信号量信号量的的P操作操作 P(semaphore s) s.value-; if(s.value 0) 该进程状态置为等待状态该进程状态置为等待状态 将该进程插入等待队列末尾将该进程插入等待队列末尾s.queue;s.queue; nP P的名称来源于荷兰语的的名

12、称来源于荷兰语的proberenproberen，即，即testtest n当当s. values. value0 0时，进程立即把自己的时，进程立即把自己的PCBPCB链接到等待队列将自己链接到等待队列将自己 阻塞，做到了阻塞，做到了“让权等待让权等待”。 申请一个资源申请一个资源, ,得到继续得到继续, ,得不到阻塞得不到阻塞 14 信号量信号量的的V操作操作 V(semaphore s) s.value+; if(s.value =0 本进程进入等待队列 转进程调度程序 否 是 返回 V原语操作原语操作 入口 S=S+1 S0S0表示有表示有S S个资源可用个资源可用 nS=0S=0表示

13、无资源可用表示无资源可用 nS0S0则则| S | S |表示表示S S等待队列中的进程个数等待队列中的进程个数 nP(S)P(S)：表示申请一个资源：表示申请一个资源 nV(S)V(S)：表示释放一个资源。：表示释放一个资源。 n解决互斥问题时，一个进程中，解决互斥问题时，一个进程中， P(S)P(S)和和V(S)V(S)必须成对出现。必须成对出现。 n没有没有P(S) P(S) ，就不能保证对临界资源的互斥访问。，就不能保证对临界资源的互斥访问。 n没有没有V(S) V(S) ，临界资源就永远不会被释放，从而等待该资源，临界资源就永远不会被释放，从而等待该资源 的进程就不能被唤醒。的进程就

14、不能被唤醒。 信号量的初值应该大于等于信号量的初值应该大于等于0 0 信号量及信号量及P、V操作讨论操作讨论 18 2.利用信号量同步利用信号量同步 n受到直接制约的进程并发执行时需要同步，即在受到直接制约的进程并发执行时需要同步，即在需要需要 同步的地方必须有明确的先后执行顺序。同步的地方必须有明确的先后执行顺序。 n例：实现打印进程与计算进程的同步问题例：实现打印进程与计算进程的同步问题 缓冲区缓冲区计算进程计算进程打印进程打印进程 n缓冲区初始状态为空。缓冲区初始状态为空。 n同步体现在：同步体现在： 打印进程只有当缓冲区有结果时，才能从缓冲区取数打印。打印进程只有当缓冲区有结果时，才能

15、从缓冲区取数打印。 计算计算 放数入缓冲区放数入缓冲区 取数，清缓冲区取数，清缓冲区 打印打印 19 缓冲区缓冲区计算进程计算进程打印进程打印进程 缓冲区为满缓冲区为满 n同步体现在：同步体现在： 打印进程只有当缓冲区有结果时，才能从缓冲区取数打印。打印进程只有当缓冲区有结果时，才能从缓冲区取数打印。 n打印进程的执行有打印进程的执行有执行条件。执行条件。 计算计算 放数入缓冲区放数入缓冲区 取数，清缓冲区取数，清缓冲区 打印打印 Wait(full) n信号量信号量full表示缓冲区为满，初值为表示缓冲区为满，初值为0。 Signal(full) 20 void Pc( ) 计算计算 放数放

16、数 缓冲区缓冲区计算进程计算进程打印进程打印进程 void main() parbegin( Pc,Pp ); semaphore full=0; void Pp( ) 取数取数 打印打印 Wait(full) Signal(full) 0-1= -1 -1+1= 0 21 缓冲区缓冲区计算进程计算进程打印进程打印进程 计算计算 放数入缓冲区放数入缓冲区 取数，清缓冲区取数，清缓冲区 打印打印 缓冲区为满缓冲区为满 缓冲区为空缓冲区为空 n同步体现在：同步体现在： 1)1)缓冲区为空：先放数缓冲区为空：先放数( (计算进程计算进程) )再取数再取数( (打印进程打印进程) ) 。 2)2)缓冲

17、区为满：先取数缓冲区为满：先取数( (打印进程打印进程) )再放数再放数( (计算进程计算进程) ) 。 n每个进程在每次循环时都有执行需要满足的条件。每个进程在每次循环时都有执行需要满足的条件。 Wait(empty) Signal(full) Wait(full) Signal(empty) n设信号量设信号量empty表示缓冲区为空，初值为表示缓冲区为空，初值为1。 信号量信号量full表示缓冲区为满，初值为表示缓冲区为满，初值为0。 n每个进程互给对方进程发送执行条件已满足的信号。每个进程互给对方进程发送执行条件已满足的信号。 22 void Pc( ) while(true) 计算计

18、算 放数放数 缓冲区缓冲区计算进程计算进程打印进程打印进程 void main() parbegin( Pc,Pp ); semaphore empty=1,full=0; void Pp( ) while(true) 取数取数 打印打印 Wait(empty) Signal(full) Wait(full) Signal(empty) 0-1= -1 1-1= 0 -1+1= 0 0-1=-1 -1+1=0 23 n和互斥一样，在同步实现中，和互斥一样，在同步实现中，PV操作也必须成对出现，所操作也必须成对出现，所 不同的是，对不同的是，对同一信号量同一信号量的的PV操作是出现在操作是出现在

19、不同不同的进程。的进程。 24 2.4经典进程同步问题经典进程同步问题 n2.4.1 生产者生产者-消费者问题消费者问题 n2.4.2 哲学家就餐问题哲学家就餐问题 n2.4.3 读者读者-写者问题写者问题 25 n一个生产者，一个消费者，一个缓冲区，生产者生产消一个生产者，一个消费者，一个缓冲区，生产者生产消 息，并将此消息提供给消费者进程去消费。息，并将此消息提供给消费者进程去消费。 2.4.1. 生产者生产者-消费者问题消费者问题 信号量信号量emptyempty，fullfull 单一资源 缓冲区缓冲区计算进程计算进程打印进程打印进程 26 生产者进程：生产者进程： 生产一个产品生产一

20、个产品 ； P（empty）；）； 将产品将产品 放入缓冲区；放入缓冲区； V（ full）；）； 消费者进程：消费者进程： P（full）；）； 从缓冲区取产品从缓冲区取产品 ； V（ empty）；）； 消费产品；消费产品； empty的初值为的初值为1，full的初值为的初值为0 27 一个生产者，一个消费者，一个生产者，一个消费者，n个缓冲区。个缓冲区。 生产者进程：生产者进程： in=0； 生产一个产品生产一个产品 ； P（empty）；）； 往往bufferin 放产品；放产品； in=（in+1）% n； V（ full）；）； 有限资源 消费者进程：消费者进程： out=0；

21、P（full）；）； 从从bufferout取产品取产品 ； out=（out+1） % n； V（ empty）；）； 消费产品；消费产品； empty初值初值n，full初值初值0 n n个缓冲区个缓冲区 outin bnb3b2b1 n同步体现在：同步体现在：缓冲区全满或全空时缓冲区全满或全空时 28 void producer() while(true) 生产一个产品生产一个产品 将产品放入将产品放入in指向的缓冲区；指向的缓冲区； in=(in+1)%n; void main() parbegin( producer,consumer ); const int n= /*buffer

22、 size*/ semaphore empty=n; semaphore full=0; Wait(empty); Signal(full); void consumer() while(true) 从从out指向缓冲区取产品；指向缓冲区取产品； out=(out+1)%n; 消费该产品；消费该产品； 思考：思考： 两个生产者交替执行，可不可以？两个生产者交替执行，可不可以？ （不可以，缓冲区是临界资源）（不可以，缓冲区是临界资源） Wait(full); Signal(empty); 29 n该问题不仅需要同步，还需要互斥。该问题不仅需要同步，还需要互斥。 n互斥：互斥： 缓冲区是缓冲区是临

23、界资源临界资源，每个进程要互斥的使用缓冲，每个进程要互斥的使用缓冲 区区 定义公共互斥信号量定义公共互斥信号量mutex，初值为初值为1。 30 while(true) while(true) void producer() 生产一个产品生产一个产品 将产品放入将产品放入in指向的缓冲区；指向的缓冲区； in=(in+1)%n; void main() parbegin( producer,consumer ); const int n= /*buffer size*/ semaphore empty=n; semaphore full=0; Wait(empty); Signal(full)

24、; Wait(full); Signal(empty); semaphore mutex=1； Wait(mutex); Signal(mutex); Wait(mutex); Signal(mutex); 能够交换两个能够交换两个P操作操作? 能够交换两个能够交换两个V交换交换?为什么？为什么？ void consumer() 从从out指向的缓冲区取产品指向的缓冲区取产品 out=(out+1)%n; 消费该产品；消费该产品； 31 while(true) while(true) void producer() 生产一个产品生产一个产品 将产品放入将产品放入in指向的缓冲区；指向的缓冲区；

25、 in=(in+1)%n; void consumer() 从从out指向缓冲区取产品；指向缓冲区取产品； out=(out+1)%n; 消费该产品；消费该产品； void main() parbegin( producer,consumer ); const int n= /*buffer size*/ semaphore empty=n; semaphore full=0; Wait(empty); Signal(full); Wait(full); Signal(empty); semaphore mutex=1； Wait(mutex); Signal(mutex); Wait(mut

26、ex); Signal(mutex); 1-1=0 0-1=-1 0-1=-1 产生死锁产生死锁 32 n进程中若有多个进程中若有多个Wait，要求，要求同步信号量的同步信号量的Wait操作在操作在 前，互斥信号量的前，互斥信号量的Wait操作在后操作在后，以免引起死锁。，以免引起死锁。 n进程中若有多个进程中若有多个Signal，其操作顺序无所谓。，其操作顺序无所谓。 33 补充：同步与互斥的解题思路补充：同步与互斥的解题思路 n分清哪些是互斥问题，哪些是同步问题分清哪些是互斥问题，哪些是同步问题. . 互斥：访问临界资源的；互斥：访问临界资源的； 同步：具有前后执行顺序要求同步：具有前后执

27、行顺序要求 n对对互斥互斥问题问题 要设置互斥信号量，不管有互斥关系的进程有几个或几类，要设置互斥信号量，不管有互斥关系的进程有几个或几类， 通常为通常为每个临界资源只设置一个互斥信号量，且初值为每个临界资源只设置一个互斥信号量，且初值为1 1， 代表一次只允许一个进程对临界资源访问。代表一次只允许一个进程对临界资源访问。 n对对同步同步问题问题 要设置同步信号量，要设置同步信号量，通常同步信号量的个数与参与同步的通常同步信号量的个数与参与同步的 进程种类有关，进程种类有关，即同步关系涉及几类进程，就有几个同步即同步关系涉及几类进程，就有几个同步 信号量。同步信号量表示该进程是否可以开始或该进

28、程是信号量。同步信号量表示该进程是否可以开始或该进程是 否已经结束。否已经结束。 34 例题例题 n桌上有一只盘子桌上有一只盘子,每次只能放入一个水果每次只能放入一个水果.爸爸专向盘中放爸爸专向盘中放 苹果苹果,妈妈专向盘中放桔子妈妈专向盘中放桔子,女儿专等吃盘中的苹果女儿专等吃盘中的苹果,儿子专儿子专 等吃盘中的桔子等吃盘中的桔子.试用试用PV操作写出他们能同步的程序操作写出他们能同步的程序. n思路：思路： 本题中有本题中有爸爸、妈妈、女儿、儿子四个进程爸爸、妈妈、女儿、儿子四个进程，需要为，需要为 每个进程写一个程序。每个进程写一个程序。 题目中有题目中有3类资源类资源，分别是，分别是空

29、碗空碗、已放入碗中的、已放入碗中的苹果苹果、 已放入碗中的已放入碗中的桔子桔子，可分别为它们设置信号量，可分别为它们设置信号量empty （初值为（初值为1）、）、apple（初值为（初值为0）、）、orange（初值为（初值为 0）。）。 35 father: P(empty) 专向盘中放苹果专向盘中放苹果 V(apple) mother: P(empty) 专向盘中放桔子专向盘中放桔子 V(orange) daughter: P(apple) 从盘中取苹果从盘中取苹果 V(empty) son: P(orange) 从盘中取苹果从盘中取苹果 V(empty) semaphor empty=

30、1,apple=0,orange=0; 36 semaphor empty=1,apple=0,orange=0; father( ) while(true) Wait(empty); put an apple; Signal(apple); mother( ) while(true) Wait(empty); put an orange; Signal(orange); main() parbegin(father,mother,son,daughter); daughter( ) while(true) Wait(apple); put an apple; Signal(empty); s

31、on( ) while(true) Wait(orange); put an orange; Signal(empty); 37 经典问题：哲学家就餐问题经典问题：哲学家就餐问题 n问题描述 五个哲学家坐在圆桌前，五个哲学家坐在圆桌前， 每人一份炒饭每人一份炒饭 每个哲学家两侧各有一支每个哲学家两侧各有一支 筷子筷子 哲学家处于吃饭和思考两哲学家处于吃饭和思考两 种状态种状态 进程通信进程通信 38 哲学家就餐问题的信号量解法哲学家就餐问题的信号量解法 n互斥关系分析 筷子：同一时刻只能有一个哲学家拿起筷子筷子：同一时刻只能有一个哲学家拿起筷子 n同步关系分析 就餐：只有获得两个筷子后才能进餐

32、就餐：只有获得两个筷子后才能进餐 n特殊情况考虑 死锁：如果每个哲学家都拿起一只筷子，都饿死死锁：如果每个哲学家都拿起一只筷子，都饿死 并行程度：五只筷子允许两人同时进餐并行程度：五只筷子允许两人同时进餐 进程通信进程通信 39 /*program diningphilosophers*/ semaphore fork5=1,1,1,1,1; int i; void Philosophers (int i) while(true) think( ); eat( ); void main( ) parbegin(Philosophers(0), Philosophers(1), Philosop

33、her(2), Philosopher(3), Philosopher(4); 4 3 2 1 0 4 3 2 1 0 Wait( forki ); Wait( fork(i+1) mod 5 ); Signal( forki ); Signal( fork(i+1) mod 5 ); 同时拿起筷子，出现死锁同时拿起筷子，出现死锁 40 解决办法解决办法 n(1)(1) 规定奇数号哲学家先拿他左边的筷子，然后再去规定奇数号哲学家先拿他左边的筷子，然后再去 拿右边的筷子；而偶数号哲学家则相反。按此规定，拿右边的筷子；而偶数号哲学家则相反。按此规定， 0 0、 1 1号哲学家竞争号哲学家竞争1 1

34、号筷子；号筷子；2 2、3 3号哲学家竞争号哲学家竞争3 3号号 筷子。筷子。 4 3 2 1 0 4 3 2 1 0 41 解决方法一解决方法一 void Philosophers (int i) while(true) think( ); if( i%2=0) Wait( forki ); Wait( fork(i+1) mod 5); else Wait( fork(i+1) mod 5); Wait( forki); eat( ); Signal(forki); Signal(fork(i+1) mod 5); 42 解决办法解决办法 n(2)(2)至多有至多有4 4个哲学家同时拿筷子

35、。个哲学家同时拿筷子。 4 3 2 1 0 4 3 2 1 0 43 /*program diningphilosophers*/ semaphore fork5=1,1,1,1,1; int i; void Philosophers (int i) while(true) think( ); eat( ); void main( ) parbegin(Philosophers(0), Philosophers(1), Philosopher(2), Philosopher(3), Philosopher(4); 4 3 2 1 0 4 3 2 1 0 Wait( forki ); Wait(

36、 fork(i+1) mod 5 ); Signal( forki ); Signal( fork(i+1) mod 5 ); semaphore room=4; Wait( room ); Signal( room ); 解决方法二解决方法二 44 2.4.3 读者读者-写者问题写者问题 nModel 问题模型：问题模型： 多个进程共享一个数据文件或记录。多个进程共享一个数据文件或记录。 读文件的进程读文件的进程读者读者 修改文件的进程修改文件的进程写者写者 n读、写规则如下：读、写规则如下： 多个读者可以同时读文件。多个读者可以同时读文件。 一次只有一个写者往文件中写。一次只有一个写者往文

37、件中写。 如果一个写者在写，则禁止任何读者读。如果一个写者在写，则禁止任何读者读。 n读者与读者、写者与写者、读者与写者间关系读者与读者、写者与写者、读者与写者间关系 n必须保证一个写者与其他进程互斥的访问共享对象。必须保证一个写者与其他进程互斥的访问共享对象。 45 读者优先读者优先/写者优先写者优先 n若写者来若写者来: : 无读者、无写者，新写者可以写。无读者、无写者，新写者可以写。 有读者，新写者等待。有读者，新写者等待。 有写者，新写者等待。有写者，新写者等待。 n若读者来若读者来: : 无读者、无写者，新读者可以读无读者、无写者，新读者可以读 有写者写，新读者等。有写者写，新读者等

38、。 有读者读，写者等，新读者怎么办？有读者读，写者等，新读者怎么办？ 读者优先：优先考虑读者，新读者进入。读者优先：优先考虑读者，新读者进入。 写者优先：优先考虑写者，新读者等，且写者写完后才能进入。写者优先：优先考虑写者，新读者等，且写者写完后才能进入。 46 1. Readers Have Priority 读者优先读者优先 n为共享资源设一个互斥信号量为共享资源设一个互斥信号量wsem，初值为，初值为1。 n如何保证有读者读时，新读者可以读？如何保证有读者读时，新读者可以读？ 设一个整形变量设一个整形变量readcount，用于记录读进程数。，用于记录读进程数。 只有只有readcoun

39、t=1时，新读者使用资源时，才须申时，新读者使用资源时，才须申 请。请。 同样在释放资源时，如果还有读者在读，同样在释放资源时，如果还有读者在读，释放资释放资 源由最后一个在读进程来做。源由最后一个在读进程来做。 47 /*program readandwriter figure5.22 p243 */ int readcount; /初值为初值为0 semaphore wsem=1; void writer( ) while(true) Wait(wsem)； writeunit(); Signal(wsem)； void reader( ) while(true) Wait(wsem)；

40、readunit( ); Signal(wsem)； if(readcount=1) readcount+； if(readcount=0) readcount- -； semaphore x=1; /对对readcount的互斥访问的互斥访问 Wait(x); Signal(x); Wait(x); Signal(x); void main( ) readcount=0; parbegin(reader,writer); 造成写者饥饿造成写者饥饿 48 2. Writer Have Priority 写者优先（自学）写者优先（自学） n为了做到有写者等待时，对新读者屏蔽，设立如下信号为了做到

41、有写者等待时，对新读者屏蔽，设立如下信号 量和变量：量和变量： 信号量信号量rsem：当至少有一个写进程准备访问数据区：当至少有一个写进程准备访问数据区 时，用于禁止所有的读进程。时，用于禁止所有的读进程。 变量变量writecount：控制：控制rsem的设置。的设置。 信号量信号量y：控制：控制writecount的更新。的更新。 n对于读进程，还需要一个额外的信号量对于读进程，还需要一个额外的信号量z。因为在。因为在rsem 上不允许多于一个进程在排队，否则写进程将不能跳过上不允许多于一个进程在排队，否则写进程将不能跳过 这个队列。因此只允许一个读进程在这个队列。因此只允许一个读进程在r

42、sem上排队，而上排队，而 所有其他进程在等待所有其他进程在等待rsem之前，在信号量之前，在信号量z上排队。上排队。 49 /*program readandwriter figure5.22 p243 */ int readcount,writecount; semaphore x=1,y=1,z=1,wsem=1,rsem=1; void writer( ) while(true) Wait(y); writecount+; if(writecount=1) Wait(rsem); Signal(y); Wait(wsem); writeunit(); Signal(wsem); Wai

43、t(y); writecount- -; if(writecount= =0) Signal(rsem); Signal(y); void reader( ) while(true) Wait(z); Wait(rsem); Wait(x); readcount+; if(readcount=1) Wait(wsem)； Signal(x); Wait(rsem); Signal(z); readunit(); Wait(x); readcount- -; if(readcount=0) Signal(wsem)； Signal(x); void main( ) readcount=write

44、count=0; parbegin(reader,writer); 50 作业作业 n1.有三个进程，进程有三个进程，进程get从输入设备上不断读数据，并存从输入设备上不断读数据，并存 入入buffer1;进程进程cut不断将不断将buffer1的内容剪切到缓冲区的内容剪切到缓冲区 buffer2，进程，进程put则不断将则不断将buffer2的内容在打印机上输的内容在打印机上输 出。三个进程并发执行，协调工作。写出该三个进程并出。三个进程并发执行，协调工作。写出该三个进程并 发执行的同步模型。发执行的同步模型。 getcutput buffer1buffer2 51 2.5 管程管程 管程管

45、程 (monitor) (monitor) 是更高级的同步机制，能够进一步是更高级的同步机制，能够进一步 实现复杂的并发性问题。实现复杂的并发性问题。 2.5.1 为什么引入管程为什么引入管程 2.5.2 管程的基本概念管程的基本概念 2.5.3 用管程实现生产者用管程实现生产者-消费者问题消费者问题 52 2.5.1 为什么引入管程为什么引入管程 n利用信号量来处理进程同步问题时，利用信号量来处理进程同步问题时，WaitWait和和SignalSignal操作分散在操作分散在 各个进程中，缺点：各个进程中，缺点： 易读性差易读性差，因为要了解对于一组共享变量及信号量的操作是，因为要了解对于一

46、组共享变量及信号量的操作是 否正确，就必须通读整个系统或者并发程序。否正确，就必须通读整个系统或者并发程序。 不利于修改和维护不利于修改和维护，因为程序的局部性很差，所以任一组变，因为程序的局部性很差，所以任一组变 量或一段代码的修改都可能影响大局。量或一段代码的修改都可能影响大局。 正确性难以保证正确性难以保证，因为操作系统或并发程序通常很大，要保，因为操作系统或并发程序通常很大，要保 证这样一个复杂的系统没有逻辑错误是很难的。证这样一个复杂的系统没有逻辑错误是很难的。 n管程管程 (monitor) (monitor) 是更高级的同步机制，能够进一步实现复杂是更高级的同步机制，能够进一步实

47、现复杂 的并发性问题。的并发性问题。 53 2.5.2 管程的基本概念管程的基本概念 n为每一类共享资源设置一个为每一类共享资源设置一个“管程管程”，统一控制和管，统一控制和管 理各进程对该资源的访问，即任何一个进程要访问共理各进程对该资源的访问，即任何一个进程要访问共 享资源，必须通过管程。享资源，必须通过管程。 系统资源 局部共享 数据结构 实施操作的 若干过程 抽象 建立 管程管程 调用 进程进程 54 n管程管程是一个软件模块，其主要特点如下：是一个软件模块，其主要特点如下： 局部数据变量只能被管程的过程访问局部数据变量只能被管程的过程访问，任何外部过，任何外部过 程都不能访问。程都不

48、能访问。 一个进程通过一个进程通过调用管程的一个过程进入管程调用管程的一个过程进入管程。 在任何时候，在任何时候，只能由一个进程在管程中执行只能由一个进程在管程中执行，调用，调用 管程的任何其他进程都被挂起，以等待管程可用。管程的任何其他进程都被挂起，以等待管程可用。 可以实现互斥可以实现互斥 55 1.管程的组成管程的组成 管程名；管程名； 局部于管程的共享变量说明；局部于管程的共享变量说明； 对该数据结构实施操作的若干过程对该数据结构实施操作的若干过程/函数；函数； 对局部于管程的数据设置初始值的语句。对局部于管程的数据设置初始值的语句。 monitor monitor-name；/定义管

49、程定义管程 variable declarations /局部共享变量声明局部共享变量声明 initialization code; /初始化代码初始化代码 P1(); /一组操作一组操作 P2(); Pn(); 56 n任何一个进程要访问共享资源必须通过任何一个进程要访问共享资源必须通过管程。管程。 n管程每次只允许一个进程进入，管程每次只允许一个进程进入，可以实现进程互斥。可以实现进程互斥。 n那如何实现进程同步呢？那如何实现进程同步呢？ 当执行条件不满足时，应能将管程内执行的进程当执行条件不满足时，应能将管程内执行的进程阻塞阻塞 利用管程实现进程同步，必须使用利用管程实现进程同步，必须使

50、用wait和和signal原语。原语。 当某进程通过管程申请资源而未能满足时，管程就调当某进程通过管程申请资源而未能满足时，管程就调 用用wait原语使该进程阻塞。原语使该进程阻塞。 当另一进程使用完资源释放后，管程调用当另一进程使用完资源释放后，管程调用signal原语唤原语唤 醒阻塞进程。醒阻塞进程。 为了为了区分阻塞的原因区分阻塞的原因，引入了局部于管程的，引入了局部于管程的条件变量条件变量 如，如，cond c; 57 2. 条件变量条件变量 n条件变量条件变量定义格式定义格式 cond x; n对条件变量只能执行两种操作：对条件变量只能执行两种操作： wait操作操作：x.wait

51、用来将执行进程挂到与条件变量用来将执行进程挂到与条件变量x相相 应的等待队列上。应的等待队列上。 signal操作：操作：如如 y.signal 用来唤醒与用来唤醒与x相应的等待队列上相应的等待队列上 的一个进程。若没有等待进程，则的一个进程。若没有等待进程，则 x.signal 不起任何作不起任何作 用。用。 58 管程的结构管程的结构 59 使用管程实现生产者使用管程实现生产者-消费者问题消费者问题 n定义一个管程定义一个管程boundedbuffer，管理有界缓冲区。，管理有界缓冲区。 n管程中有两个条件变量：管程中有两个条件变量： notfull：当缓冲区未全满（至少有增加一个字符的：

52、当缓冲区未全满（至少有增加一个字符的 空间）时，为真；空间）时，为真； notempty：当缓冲区未全空（至少有一个字符）：当缓冲区未全空（至少有一个字符） 时，为真。时，为真。 n为该管程定义两个过程：为该管程定义两个过程： 放产品放产品 put(char x) 取产品取产品 get(char /管程名管程名 char bufferN; int in, out; int count; /局部变量局部变量 cond notfull, notempty; /条件变量条件变量 void put(char x) if(count = =N) notfull.wait; bufferin=x; in=

53、(in+1)%N; count+; if notempty.queue notempty.signal; in=0; out=0; count=0; /局部变量初始化局部变量初始化 void get(char x=bufferout; out=(out+1)%N; count-; if notfull.queue notfull.signal; 61 void producer( ) char x; while(true) produce(x); boundedbuffer.put(x); void consumer( ) char x; while(true) boundedbuffer.g

54、et(x); consume(x); void main( ) parbegin(producer, consumer); 62 管程与信号量的对比管程与信号量的对比 n解决同步互斥问题时，解决同步互斥问题时， 使用信号量，实现同步和互斥都是程序员的责任。使用信号量，实现同步和互斥都是程序员的责任。 使用管程，管程本身的互斥机制使得生产者、消费使用管程，管程本身的互斥机制使得生产者、消费 者不能同时访问缓冲区。但实现同步需要程序员使者不能同时访问缓冲区。但实现同步需要程序员使 用用wait、signal实现。实现。 n与信号量相比，管程的优势在于所有的同步机制都限与信号量相比，管程的优势在于所

55、有的同步机制都限 制在管程内部，因此不仅易于验证同步的正确性，而制在管程内部，因此不仅易于验证同步的正确性，而 且易于检测出错误。且易于检测出错误。 63 2.6 进程通信进程通信 n传送控制信息传送控制信息低级通信低级通信 n目的是为了控制进程的执行速度目的是为了控制进程的执行速度 n如，同步互斥机制中的信号量如，同步互斥机制中的信号量 n特点：交换的信息量少、效率低特点：交换的信息量少、效率低 n低级通信原语：低级通信原语：PV原语原语 n传送大批量数据传送大批量数据高级通信高级通信 n信息交换的目的是为了传送大批量数据信息交换的目的是为了传送大批量数据 n特点：传送的信息量大、效率高特点

56、：传送的信息量大、效率高 n高级通信原语：高级通信原语：Send/Receive原语原语 根据根据 通信通信 内容内容 分为分为 两种两种 64 2.6.1 进程通信的类型进程通信的类型 n高级通信机制高级通信机制可分为三个类型：可分为三个类型： 共享存储器系统共享存储器系统 消息传递系统消息传递系统 共享文件系统共享文件系统 / 管道通信管道通信 n1.共享存储器系统共享存储器系统 基于基于共享数据结构共享数据结构的通信方式的通信方式 n生产者消费者中的缓冲区生产者消费者中的缓冲区,属于属于低级通信低级通信方式方式 基于基于共享存储区共享存储区的通信方式的通信方式 n属于属于高级通信高级通信

57、方式方式 65 2. 消息传递系统消息传递系统 n进程间的数据交换以进程间的数据交换以格式化的消息格式化的消息为单位。为单位。 n因实现方式的不同，分为：因实现方式的不同，分为： 直接通信方式：消息缓冲队列直接通信方式：消息缓冲队列 间接通信方式：信箱通信间接通信方式：信箱通信 66 3. 管道通信管道通信 n所谓所谓“管道管道”，是指用于连接一个读进程和一个写进，是指用于连接一个读进程和一个写进 程以实现他们之间通信的一个共享文件，又名程以实现他们之间通信的一个共享文件，又名pipepipe文文 件。件。 写入端写入端读出端读出端 以比特流方式，单向传输以比特流方式，单向传输 n首先应用于首

58、先应用于UnixUnix操作系统操作系统 67 n消息消息 格式化的数据格式化的数据 2.6.2 消息传递通信消息传递通信 n消息传递通信机制消息传递通信机制 以以格式化的消息格式化的消息作为进程间数据交换单位的进程作为进程间数据交换单位的进程 通信方式。通信方式。 n消息传递系统可以实现：消息传递系统可以实现： 实施互斥实施互斥 交换信息交换信息 n提供一对操作原语：提供一对操作原语： send (destination, message) receive (source, message) 68 1.通信方式通信方式 n消息传递机制有两种实现方式：消息传递机制有两种实现方式： 直接通信方式

59、直接通信方式 间接通信方式间接通信方式 n1. 直接寻址直接寻址/直接通信方式直接通信方式 nSend原语包括目标进程的原语包括目标进程的id号。号。 n发送进程直接将消息发送给目标进程。发送进程直接将消息发送给目标进程。 n2.间接通信方式间接通信方式 消息发送到由队列组成的一个共享数据结构。该消息发送到由队列组成的一个共享数据结构。该 队列称为队列称为信箱信箱。 两个通信进程，一个进程给信箱发送消息，另一两个通信进程，一个进程给信箱发送消息，另一 个从信箱中获取消息。个从信箱中获取消息。 69 3. 同步方式同步方式 n根据发送进程执行根据发送进程执行send原语、接收进程执行原语、接收进

60、程执行receive 原语后是否阻塞，有以下三种组合原语后是否阻塞，有以下三种组合 ： 发送进程阻塞、接收进程阻塞发送进程阻塞、接收进程阻塞 n发送者和接收者都被阻塞，直到完成信息的交付，属发送者和接收者都被阻塞，直到完成信息的交付，属 于进程的紧密同步。于进程的紧密同步。 发送进程不阻塞、接收进程阻塞发送进程不阻塞、接收进程阻塞 n发送者执行完发送者执行完send原语发送完，继续执行；接收者原语发送完，继续执行；接收者 执行完执行完receive即被阻塞，直到等待的消息到达。即被阻塞，直到等待的消息到达。 发送进程和接收进程均不阻塞发送进程和接收进程均不阻塞 n不要求任何一方等待。不要求任何