操作系统-第2章(2)(第四版)

1、第二章进 程 管 理 2.3 2.3 进程的同步进程的同步进程同步问题的提出进程同步问题的提出 进程异步推进可能造成混乱进程异步推进可能造成混乱 混乱可能导致不可再现混乱可能导致不可再现进程同步目标进程同步目标第二章进 程 管 理 一、进程同步的基本概念一、进程同步的基本概念1 1进程间两种主要关系进程间两种主要关系 1) 1) 直接作用直接作用-相互合作引起相互合作引起-进程同步：进程同步：( (如：输入、计算、打印如：输入、计算、打印) ) 进程间的相互联系是进程间的相互联系是有意识的安排有意识的安排的，直接作用只发生在相交进程间。的，直接作用只发生在相交进程间。 2) 2) 间接作用间接

2、作用-资源共享引起资源共享引起-进程互斥：进程互斥：( (如如: :打印机资源打印机资源) ) 进程间要通过某种中介发生联系，是进程间要通过某种中介发生联系，是无意识安排无意识安排的，可发生在相交进的，可发生在相交进程之间，也可发生在无关进程之间。程之间，也可发生在无关进程之间。第二章进 程 管 理 进程间的同步关系（一）进程间的同步关系（一）第二章进 程 管 理 进程间的同步关系（二）进程间的同步关系（二）第二章进 程 管 理 进程间的同步关系（三）进程间的同步关系（三）第二章进 程 管 理 进程间的同步关系进程间的同步关系第二章进 程 管 理 相互感知程度相互感知程度 交互关系交互关系 一

3、个进程对其他进程一个进程对其他进程的影响的影响 相互不感知相互不感知( (完全不完全不了解其它进程的存在了解其它进程的存在) ) 竞争竞争(competition) (competition) 一个进程的操作对其一个进程的操作对其他进程的结果无影响他进程的结果无影响 间接感知间接感知( (双方都与双方都与第三方交互，如共享第三方交互，如共享资源资源) ) 通过共享进行协作通过共享进行协作 一个进程的结果依赖一个进程的结果依赖于从其他进程获得的于从其他进程获得的信息信息 直接感知直接感知( (双方直接双方直接交互，如通信交互，如通信) ) 通过通信进行协作通过通信进行协作 一个进程的结果依赖一个

4、进程的结果依赖于从其他进程获得的于从其他进程获得的信息信息 进程之间关系及感知程度进程之间关系及感知程度第二章进 程 管 理 2. 2. 进程的同步（直接作用）进程的同步（直接作用） 指系统中多个进程中发生的事件存在某种时序关系，需要指系统中多个进程中发生的事件存在某种时序关系，需要相互合作相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待（阻塞）状态，获得为它提供消息，在未获得消息之前，该进程处于等待（阻塞）状态，获得消息后被唤醒进入就绪状态。消息后被唤醒进入

5、就绪状态。多个相关进程在执行次序上的协调。多个相关进程在执行次序上的协调。 如：司机如：司机 售票员售票员 停车停车- 开车门开车门 开车开车- - 关车门关车门 3. 3. 进程的互斥（间接作用）进程的互斥（间接作用） 由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争竞争使用这些资源，进程的这种关系为进程的互斥。使用这些资源，进程的这种关系为进程的互斥。 如：多个打印者竞争打印机；如：多个打印者竞争打印机；第二章进 程 管 理 系统中某些资源一次只允许一个进程使用，称这样的资源为临界系统中某些资源一次只允许一个进程使

6、用，称这样的资源为临界资源或互斥资源。资源或互斥资源。 1) 1) 生产者生产者-消费者消费者(producer-consumer)著名的进程同步问题。著名的进程同步问题。 问题描述：问题描述：有一群生产者进程在生产产品，并将这些产品提供给消有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有间设置了一个具有n n个缓冲区的缓冲池（循环缓冲），个缓冲区的缓冲池（循环缓冲），生产者生产者进程将它进程将它所生产的产品所生产的产品放入放入一个缓冲区中；一个缓冲区中；

7、消费者消费者进程可从一个缓冲区中进程可从一个缓冲区中取走取走产产品去消费。品去消费。第二章进 程 管 理 数据定义：数据定义： 1 1）itemitem buffernbuffern 用一个数组表示具有用一个数组表示具有n n个个(0(0，1 1，n-1)n-1)缓冲区的缓冲池。缓冲区的缓冲池。2 2）输入指针）输入指针 in: in: 下一个可投放产品的缓冲区。下一个可投放产品的缓冲区。 in:= (in+1) % nin:= (in+1) % n；3 3）输出指针）输出指针 outout： 下一个可从中获取产品的缓冲区。下一个可从中获取产品的缓冲区。 out:= (out+1) % nou

8、t:= (out+1) % n。4 4）整型变量）整型变量 countercounter：生产者和消费者两进程共享。生产者和消费者两进程共享。 初始值为初始值为0;0; 生产者进程向缓冲池中投放一个产品后，使生产者进程向缓冲池中投放一个产品后，使countercounter加加1 1； 消费者进程从中取走一个产品时，使消费者进程从中取走一个产品时，使countercounter减减1 1；5 5）局部变量）局部变量 nextpnextp： 存放每次刚生产出来的产品；存放每次刚生产出来的产品；6 6）局部变量）局部变量 nextcnextc： 存放每次要消费的产品。存放每次要消费的产品。 第二章

9、进 程 管 理 Producer：生产者进程：生产者进程 while (1) produce an item in nextp； while (counter=n) ； bufferin:=nextp； in:=(in+1) % n； counter+； ； Consumer: 消费者进程消费者进程 while (1) while (counter=0) ；nextc:=bufferout；out:=(out+1) % n；counter-；consumer the item in nextc； 初始初始counter=0；思考：思考： 1、生产者程序和消费者程序顺序执行时其结果是否正确？、生

10、产者程序和消费者程序顺序执行时其结果是否正确？ 2、生产者程序和消费者程序并发执行时其结果是否正确？、生产者程序和消费者程序并发执行时其结果是否正确？ 3、原因何在？、原因何在？有何有何 作用？作用？第二章进 程 管 理 问题问题: 共享变量共享变量counter。生产者、消费者对其操作，这两个操作在用生产者、消费者对其操作，这两个操作在用机器语言实现时，用下面的形式描述：机器语言实现时，用下面的形式描述： 假设：假设： counter:=5 register1:=counter； register2:=counter；生产者：生产者：register1:=register1+1； 消费者：消

11、费者：register2:=register2-1； counter:=register1； counter:=register2； 执行顺序：执行顺序：1、生产者先执行左列的三条语句，消费者再执行右列三条语句。、生产者先执行左列的三条语句，消费者再执行右列三条语句。 count:= 52、消费者先执行右列的三条语句，生产者再执行左列三条语句。、消费者先执行右列的三条语句，生产者再执行左列三条语句。 count:= 53、register1:=counter； (register1=5) register1:=register1+1； (register1=6) register2:=coun

12、ter； (register2=5) register2:=register2-1； (register2=4) counter:=register1； (counter=6) counter:=register2； (counter=4)结论：共享变量结论：共享变量counter是临界是临界资源，需互斥访资源，需互斥访问。问。结果不可再现结果不可再现第二章进 程 管 理 例题：例题：1. 有两个并发执行的进程有两个并发执行的进程P1和和P2，共享初值为，共享初值为1的变量的变量x。P1对对x加加1，P2对对x减减1。加。加1和减和减1操作的指令序列分别如下所示。操作的指令序列分别如下所示。

13、/ 加加1操作操作 / 减减1操作操作 load R1，x / 取取x到寄存器到寄存器R1中中 load R2，x inc R1 dec R2 store x，R1 / 将将R1的内容存入的内容存入x store x，R2 两个操作各执行一次结束后，两个操作各执行一次结束后，x的值的值( )。A可能为可能为-1或或3 B只能为只能为1 C可能为可能为0、1或或2 D可能为可能为-1、0、1或或2第二章进 程 管 理 5. 5. 临界区临界区每个进程用于访问每个进程用于访问临界资源临界资源的那段程序。的那段程序。若能保证诸进程若能保证诸进程互斥地互斥地进入自己的临界区，便可实现诸进程对临进入自己

14、的临界区，便可实现诸进程对临界资源的互斥访问。界资源的互斥访问。第二章进 程 管 理 6. 进程同步应遵循的原则进程同步应遵循的原则1）空闲让进）空闲让进当资源空闲时，应当允许访问资源的进程进入临界区。当资源空闲时，应当允许访问资源的进程进入临界区。2）忙则等待）忙则等待 当资源被占用时，应使申请访问该资源的进程等待，等待使用者归当资源被占用时，应使申请访问该资源的进程等待，等待使用者归还资源。还资源。第二章进 程 管 理 第二章进 程 管 理 第二章进 程 管 理 补充：二、补充：二、 临界资源锁机制临界资源锁机制-解决进程互斥解决进程互斥 例：商场的试衣间例：商场的试衣间 是互斥资源是互斥

15、资源 是临界资源是临界资源 是共享资源是共享资源 每个顾客必须遵循以下过程使用试衣间：每个顾客必须遵循以下过程使用试衣间：观察锁状态观察锁状态关锁关锁使用试衣间使用试衣间开锁开锁第二章进 程 管 理 临界资源锁机制临界资源锁机制关锁关锁访问访问开锁开锁第二章进 程 管 理 一种简单的锁操作实现一种简单的锁操作实现资源正在使用，继续反复测试资源正在使用，继续反复测试上锁上锁开锁开锁 L=1 L=1？ 1L 1L 入口入口 返回返回是是否否 0L 0L 入口入口 返回返回上锁上锁开锁开锁第二章进 程 管 理 锁操作模拟过程锁操作模拟过程第二章进 程 管 理 锁操作的一般模型锁操作的一般模型第二章进

16、 程 管 理 出了问题的锁出了问题的锁第二章进 程 管 理 利用上锁原语和开锁原语实现进程互斥利用上锁原语和开锁原语实现进程互斥 利用上锁原语和开锁原语可以解决并发进程对临界区访问的互利用上锁原语和开锁原语可以解决并发进程对临界区访问的互斥问题。斥问题。上锁原语上锁原语 临界区临界区CSCSA A开锁原语开锁原语上锁原语上锁原语 临界区临界区CSCSA A开锁原语开锁原语进程进程A A进程进程B B第二章进 程 管 理 锁操作的特点：锁操作的特点： 实现了进程互斥访问临界资源。实现了进程互斥访问临界资源。 不遵循让权等待原则。不遵循让权等待原则。忙等忙等资源正在使用，继续反复测试；资源正在使用

17、，继续反复测试；忙等；忙等；上锁上锁Lock(L)、UnLock(L)原子操作，不许中断。原子操作，不许中断。第二章进 程 管 理 硬件同步机制硬件同步机制 目前许多计算机已提供了一些特殊的硬件指令，允许对目前许多计算机已提供了一些特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。可利用这些特殊的指令来解决临界区问题。行交换等。可利用这些特殊的指令来解决临界区问题。 第二章进 程 管 理 实现互斥的最简单的方法之一。实现互斥的最简单的方法之一。 在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才在进入锁测试

18、之前关闭中断，直到完成锁测试并上锁之后才能打开中断。能打开中断。 关中断的方法存在许多缺点关中断的方法存在许多缺点 滥用关中断权力可能导致严重后果；滥用关中断权力可能导致严重后果； 关中断时间过长，会影响系统效率，限制了处理器交关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；叉执行程序的能力； 关中断方法也不适用于多关中断方法也不适用于多CPU 系统，因为在一个处理系统，因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的器上关中断并不能防止进程在其它处理器上执行相同的临界段代码；临界段代码；1. 关中断关中断第二章进 程 管 理 （1）TS指令定义：指令定义：Boo

19、lean TS(Boolean *lock) /lock 初始值初始值FALSE:表示没有进程进入临界区表示没有进程进入临界区 Booean old; old =*lock; *lock=TRUE; /锁住锁住 return old ;（2）对临界区的访问：）对临界区的访问： do . while TS(&lock) ; /lock为为True, 不能进入；否则锁住临界区，进入；不能进入；否则锁住临界区，进入； critical section; /访问临界区访问临界区 lock=FALSE; /解锁解锁 . while (TRUE);2.利用利用Test-and-Set指令实现互斥指

20、令实现互斥第二章进 程 管 理 三、进程同步的信号量机制（三、进程同步的信号量机制（semaphoresemaphore） 经典信号量、记录型信号量、经典信号量、记录型信号量、AND信号量、信号量集信号量、信号量集1. 信号量机制的基本概念信号量机制的基本概念 信号量信号量 信号量是对信号量是对具体物理资源的抽象具体物理资源的抽象。 不同类的资源用不同类的资源用不同名称不同名称的信号量代表。的信号量代表。 同类资源同类资源的个数用的个数用 0的信号量值表示。的信号量值表示。 信号量值为信号量值为 0 或或 1 的信号量的信号量表示表示临界资源临界资源。信号量是比锁更高级的资源抽象方式信号量是比

21、锁更高级的资源抽象方式第二章进 程 管 理 2. 2. 经典经典( (整型整型) )信号量的信号量的P P，V V操作操作 资源的申请与释放原语资源的申请与释放原语P操作操作 wait(S) while Svalue-； if S-valuelist)；; signal(semaphore *S) /释放资源释放资源 V(S) S-value:+； if S-valuelist)；; 第二章进 程 管 理 纪录型信号量机制特点：纪录型信号量机制特点： 进程对资源访问的过程：进程对资源访问的过程： 原语保证原语保证 p（s），），v（s）操作都是原语；）操作都是原语； 保证不出现保证不出现“锁不

22、住锁不住”资源的现象；资源的现象；第二章进 程 管 理 纪录型信号量机制特点：纪录型信号量机制特点： 主动阻塞与被动唤醒主动阻塞与被动唤醒第二章进 程 管 理 例题：例题：1. 有一个计数信号量有一个计数信号量S；1）假如若干个进程对）假如若干个进程对S进行了进行了28次次P操作和操作和18次次V操作之后，信号量操作之后，信号量S的值为的值为0；2）假如若干个进程对信号量）假如若干个进程对信号量S进行了进行了15次次P操作和操作和2次次V操作。请问此时有多少操作。请问此时有多少个进程等待在信号量个进程等待在信号量S的队列中（）。的队列中（）。 A. 2 B. 3 C. 5 D. 7 设与某资源

23、关联的信号量（设与某资源关联的信号量（K）初值为）初值为3，当前值为，当前值为1。若。若M表示该资源的可表示该资源的可用个数，用个数，N表示等待该资源的进程数，则表示等待该资源的进程数，则M，N分别是（）。分别是（）。 A. 0，1 B. 1，0 C. 1，2 D. 2，0 在在9个生产者、个生产者、6个消费者共享容量为个消费者共享容量为8的缓冲器的生产者的缓冲器的生产者-消费者问题中，互消费者问题中，互斥使用缓冲器的信号量初始值为（）。斥使用缓冲器的信号量初始值为（）。 A. 1 B. 6 C. 8 D. 9 有三个进程共享同一程序段，而每次只允许两个进程进入该程序段，若用有三个进程共享同一

24、程序段，而每次只允许两个进程进入该程序段，若用PV操作同步机制，则信号操作同步机制，则信号S的取值范围是（）。的取值范围是（）。 A. 2，1，0，-1 B. 3，2，1，0 C. 2，1，0，-1，-2 D. 1，0，-1，-2第二章进 程 管 理 4. AND4. AND型信号量型信号量 引入原因引入原因 基本思想基本思想 流程流程第二章进 程 管 理 AND型信号量引入原因型信号量引入原因第二章进 程 管 理 ANDAND型信号量基本思想型信号量基本思想基本思想基本思想 将将多次对多个信号量多次对多个信号量的申请改为一次，用一个原子操作的申请改为一次，用一个原子操作完成。完成。或 进程要

25、么一次获得所有的资源，要么一个也申请不到。进程要么一次获得所有的资源，要么一个也申请不到。 不会存在互相等待的局面不会存在互相等待的局面第二章进 程 管 理 AND型信号量集流程资源申请型信号量集流程资源申请第二章进 程 管 理 AND型信号量集流程资源释放型信号量集流程资源释放第二章进 程 管 理 信号量集流程信号量集流程第二章进 程 管 理 5. 5. 信号量集信号量集 引入原因引入原因 更灵活更灵活 基本思想基本思想 si：各信号量：各信号量; ti：申请下限：申请下限 ti 0时，可进行资源预留；时，可进行资源预留； di：申请个数：申请个数 一次可申请一种资源的多个。一次可申请一种资

26、源的多个。第二章进 程 管 理 “信号量集信号量集”的几种特殊情况的几种特殊情况： (1) Swait(S，d，d)。此时在信号量集中只有一个信号量此时在信号量集中只有一个信号量S，但允许它，但允许它每次申请每次申请d个资源，当现有资源数少于个资源，当现有资源数少于d时，不予分配。时，不予分配。(2) Swait(S，1，1)。此时的信号量集已蜕化为一般的记录型信号量此时的信号量集已蜕化为一般的记录型信号量(S1时时)或互斥信号量或互斥信号量(S=1时时)。(3) Swait(S，1，0)。这是一种很特殊且很有用的信号量操作。当这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特

27、定区；当时，允许多个进程进入某特定区；当S变为变为0后，将阻止任何进程进入后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。特定区。换言之，它相当于一个可控开关。 S=1，S值不变，可以进入临界区；值不变，可以进入临界区； S1，阻塞进程；，阻塞进程；第二章进 程 管 理 小结四种信号量特点：小结四种信号量特点：1 1、整型信号量、整型信号量 wait(s)wait(s)，signal(s)signal(s)对一类资源申请和释放对一类资源申请和释放 wait(s)wait(s)：如果：如果s=0, s=0, 忙等；否则申请忙等；否则申请一个一个资源；资源； signal(s)sign

28、al(s)：释放：释放一个一个资源；资源；2 2、记录型信号量、记录型信号量-对一类资源申请和释放对一类资源申请和释放 解决了忙等；解决了忙等； wait(s)wait(s)： 如如s s减一后，减一后，s0s0，则阻塞，排到阻塞队列。，则阻塞，排到阻塞队列。 signal(s)signal(s)：如：如s s加一后，加一后，s=0s=0，则唤醒一个进程；，则唤醒一个进程； 如如s=-2s=-2，说明有两个进程排在等待该类资源的阻塞队列。，说明有两个进程排在等待该类资源的阻塞队列。3 3、AndAnd型信号量型信号量 解决了解决了多类资源多类资源同步和互斥管理。策略：一次性全获得和释放；同步和

29、互斥管理。策略：一次性全获得和释放； 但一次只能申请和释放一个资源。但一次只能申请和释放一个资源。4 4、信号量集、信号量集 对对多类资源，每次可申请和释放多个，并且有一个下限多类资源，每次可申请和释放多个，并且有一个下限。策略：如满足策略：如满足条件，一次性全获得和释放。条件，一次性全获得和释放。PV操操作作第二章进 程 管 理 6 . 6 . 信号量的应用信号量的应用利用信号量实现进程互斥利用信号量实现进程互斥资源竞争时的进程同步。资源竞争时的进程同步。 对竞争资源的互斥访问互斥信号量对竞争资源的互斥访问互斥信号量mutex=1mutex=1。互斥信号量初值一。互斥信号量初值一般为般为1

30、1。第二章进 程 管 理 6. 6. 信号量的应用信号量的应用-利用信号量实现进程同步利用信号量实现进程同步-相互合作时的进程同步相互合作时的进程同步 保证进程间的前驱、后继关系保证进程间的前驱、后继关系第二章进 程 管 理 6 . 6 . 信号量的应用信号量的应用-利用信号量实现前趋关系利用信号量实现前趋关系 条件：条件：设有两个并发执行的进程设有两个并发执行的进程P1和和P2。P1中有语句中有语句S1；P2中有语句中有语句S2。 目标：目标：S1S2 前驱关系前驱关系 实现：实现： P1和和P2共享一个公用信号量，初值共享一个公用信号量，初值S=0; P1：S1；signal(S)； P2

31、：wait(S)；S2； 第二章进 程 管 理 Var a,b,c,d,e,f,g：semaphore: =0,0,0,0,0,0,0；beginparbeginbegin S1； signal(a)； signal(b)； end；begin wait(a)； S2； signal(c)； signal(d)； end；begin wait(b)； S3； signal(e)； end；begin wait(c)； S4； signal(f)； end；begin wait(d)； S5； signal(g)； end；begin wait(e)； wait(f)； wait(g)； S6；

32、 end；parendend S4S5S3S1S6S2例：例： 有一前驱图，利有一前驱图，利用信号量实现前驱关用信号量实现前驱关系。系。abcdefg第二章进 程 管 理 7. 利用信号量实现同步（利用信号量实现同步（XY）Semaphore s=0; /初始化信号量初始化信号量P1() x; /语句语句x V(s) ; /告诉进程告诉进程P2，语句，语句x已经完成已经完成 P2() P(s) ; /检查语句检查语句x是否运行完成是否运行完成 y; /检查无误，运行语句检查无误，运行语句y 第二章进 程 管 理 7. 利用信号量实现互斥利用信号量实现互斥Semaphore s=1; /初始化信

33、号量初始化信号量P1() P(s)； /准备开始访问临界资源，加锁准备开始访问临界资源，加锁 进程进程P1的临界区；的临界区； V(s) ; /访问结束，解锁访问结束，解锁 P2() P(s)； /准备开始访问临界资源，加锁准备开始访问临界资源，加锁 进程进程P2的临界区；的临界区； V(s) ; /访问结束，解锁访问结束，解锁 第二章进 程 管 理 2.4经典进程的同步问题经典进程的同步问题 一、生产者一、生产者消费者问题消费者问题-典型的同步例子典型的同步例子 它描述了一组生产者向一组消费者提供产品（数据），它们共享一它描述了一组生产者向一组消费者提供产品（数据），它们共享一个有界缓冲区，

34、生产者向其中投放产品，消费者从中取出产品消费。这样个有界缓冲区，生产者向其中投放产品，消费者从中取出产品消费。这样的一个问题是的一个问题是许多相互合作进程许多相互合作进程存在的内在关系的一种抽象。存在的内在关系的一种抽象。 一组生产者一组生产者P1P1、P2P2、PmPm一组消费者一组消费者C1C1、C2C2、CkCk有界缓冲区有界缓冲区长度为长度为n n（n n 0 0）第二章进 程 管 理 只要缓冲区未满，生产者就可把产品送入缓冲区；只要缓冲区未空，只要缓冲区未满，生产者就可把产品送入缓冲区；只要缓冲区未空，消费者便可从缓冲区取走产品并消耗它。消费者便可从缓冲区取走产品并消耗它。 仅当缓冲

35、区满时，生产者被阻塞，类似地，缓冲区空时，消费者被仅当缓冲区满时，生产者被阻塞，类似地，缓冲区空时，消费者被阻塞。阻塞。 生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品，生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品，也禁止消费者从空的缓冲区中提取物品。也禁止消费者从空的缓冲区中提取物品。 P1P1P2P2P3P3Pm-1Pm-1PmPm C1C1C2C2C3C3Ck-1Ck-1CkCk缓冲区缓冲区第二章进 程 管 理 算法分析算法分析两类进程：生产者进程和消费者进程两类进程：生产者进程和消费者进程（1）进程间的关系）进程间的关系（合作：同步信号量合作：同步信号量） 生产者

36、生产产品后消费者消费。生产者生产产品后消费者消费。设设full:表示表示满缓冲区满缓冲区(即产品）的数目，初值为即产品）的数目，初值为0； 消费者消费后的空缓冲区由生产者生产产品。消费者消费后的空缓冲区由生产者生产产品。设设empty:表示表示空缓冲区空缓冲区的数目，初的数目，初值为缓冲区的大小值为缓冲区的大小n。（2）进程间的关系）进程间的关系（竞争：互斥信号量竞争：互斥信号量） 由于有界缓冲区是一个临界资源，必须互斥使用，所以，还需要设置一个互由于有界缓冲区是一个临界资源，必须互斥使用，所以，还需要设置一个互斥信号量：斥信号量： mutex:互斥信号量，初值为互斥信号量，初值为l。消费者何

37、消费者何时阻塞？时阻塞？生产者何生产者何时阻塞？时阻塞？第二章进 程 管 理 生产者生产者消费者问题流程消费者问题流程 生产者进程生产者进程Pi(i=1,2,Pi(i=1,2, ,m) ,m) 消费者进程消费者进程Cj(j=1,2,Cj(j=1,2, ,k) ,k) 产品送入缓冲区产品送入缓冲区 wait(empty)wait(empty) wait(mutex)wait(mutex)signal(mutex)signal(mutex) signal(full) signal(full) 生产一个产品生产一个产品 从缓冲区取一个产品从缓冲区取一个产品 wait(mutex)(mutex) si

38、gnal(empty)signal(empty) signal(mutex)signal(mutex) 消耗该产品消耗该产品 wait(full)wait(full)唤醒唤醒唤醒唤醒先看先看池满？池满？后看后看使用？使用？empty=0阻塞阻塞full=0阻塞阻塞先看先看池空？池空？第二章进 程 管 理 Semaphore mutex=1, empty=n, full=0；item buffern;int in=0，out=0；void proceducer() doproducer an item nextp；wait(empty)； wait(mutex)；buffer(in)=nextp

39、；in=(in+1) % n；signal(mutex)；signal(full)； while (TRUE);void consumer() do wait(full)； wait(mutex)； nextc=buffer(out)； out=(out+1) % n； signal(mutex)； signal(empty)； consumer the item in nextc； while(TRUE); Swait(empty,mutex)Ssignal(mutex,full)Swait(full,mutex)Ssignal(mutex,empty)记录型记录型信号量信号量And型型信号

40、量信号量第二章进 程 管 理 生产者消费者算法小结：生产者消费者算法小结： 在分析进程同步问题中，逐个分析进程间的关系是关键。在分析进程同步问题中，逐个分析进程间的关系是关键。 不管多复杂的关系，总能归结为两种基本关系（竞争与合作），总是不管多复杂的关系，总能归结为两种基本关系（竞争与合作），总是这两种关系的组合。这两种关系的组合。 不管互斥信号量还是同步信号量，信号量的使用必须成对出现。不管互斥信号量还是同步信号量，信号量的使用必须成对出现。 互斥信号量初值设为互斥信号量初值设为1； P(s1) ，P(s2)两操作在一起，两操作在一起，P的顺序至关重要，同步的顺序至关重要，同步P和互斥和互斥

41、P在一在一起，同步起，同步P操作在前。操作在前。 互斥操作时，互斥操作时，PV处于同一进程；同步操作时，不在同一进程处于同一进程；同步操作时，不在同一进程例题：例题： 设设P、Q、R共享一个缓冲区，共享一个缓冲区，P，Q构成一对生产者构成一对生产者-消费者，消费者，R即为即为生产者又为消费者。使用生产者又为消费者。使用P、V操作实现其同步。请同学们课后完成。操作实现其同步。请同学们课后完成。第二章进 程 管 理 二、哲学家进餐问题二、哲学家进餐问题问题描述问题描述五位哲学家围桌而坐。五位哲学家围桌而坐。哲学家在思考问题时不需要哲学家在思考问题时不需要任何资源，思考完问题后进入任何资源，思考完问

42、题后进入进餐态。进餐态。每人必须获得左右两支筷子每人必须获得左右两支筷子才能进餐。才能进餐。思考思考思考思考思考思考思考思考思考思考准备进餐准备进餐进餐进餐准备进餐准备进餐进餐进餐第二章进 程 管 理 1利用记录型信号量解决哲学家进餐问题利用记录型信号量解决哲学家进餐问题放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。用一个信号量表示一只筷子，由这五个信号量构成信号量数组。用。用一个信号量表示一只筷子，由这五个信号量构成信号量数组。 信号量初始值均为信号量初始值均为1； semaphore chopstick5 =1,1,

43、1,1,1； 活动描述：活动描述：dowait(chopsticki)；/拿起左边筷子拿起左边筷子wait(chopstick(i+1) %5)；/拿起右边筷子拿起右边筷子eat；signal(chopsticki)；/放下左边筷子放下左边筷子signal(chopstick(i+1) % 5)；/放下右边筷子放下右边筷子think；while(TRUE)； 第二章进 程 管 理 哲学家问题分析哲学家问题分析死锁死锁思考思考思考思考思考思考思考思考思考思考准备进餐准备进餐准备进餐准备进餐准备进餐准备进餐准备进餐准备进餐准备进餐准备进餐P（chopsticki）V(chopsticki+1 %5

44、)第二章进 程 管 理 可采取以下几种解决死锁问题方法：可采取以下几种解决死锁问题方法： (1) 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。多的哲学家能够进餐。(2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。(3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶规定奇数号哲学家先拿他左边

45、的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。数号哲学家则相反。15432竞争竞争竞争竞争注：上述几种方法可以解决死锁，注：上述几种方法可以解决死锁，但都施加了一些限制，对系统的效但都施加了一些限制，对系统的效率会产生一定的影响。率会产生一定的影响。第二章进 程 管 理 2利用利用AND信号量机制解决哲学家进餐问题信号量机制解决哲学家进餐问题在哲学家进餐问题中，要求每个哲学家先获得两个临界资源在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子筷子)后方能进餐，后方能进餐，AND信号量机制可获得最简洁的解法。描述如下：信号量机制可获得最简洁的解法。描述如下： Semaphore c

46、hopstick5=1,1,1,1,1；dothink；Swait(chopstick(i+1) % 5，chopsticki)；eat；Ssignal(chopstick(i+1) % 5，chopsticki)；while(TRUE)； 第二章进 程 管 理 三、读者三、读者写者问题写者问题（Reader and Writer ） 问题描述问题描述 一个数据记录一个数据记录(共享数据共享数据)，有多个进程进行读操作，另一些进程进，有多个进程进行读操作，另一些进程进行修改操作。行修改操作。 （Reader） （Writer） 读写策略读写策略 允许多个进程同时进行读操作允许多个进程同时进行读

47、操作读不互斥读不互斥 不允许多于一个进程进行写操作不允许多于一个进程进行写操作写互斥写互斥 不允许读写操作同时进行不允许读写操作同时进行读写互斥读写互斥第二章进 程 管 理 用一个计数器用一个计数器ReadcountReadcount来统计读者的数量，每当有一个读者欲访来统计读者的数量，每当有一个读者欲访问共享数据时，对问共享数据时，对ReadcountReadcount计数加计数加1 1，每当有一个读者结束对共享数，每当有一个读者结束对共享数据的访问时，对据的访问时，对ReadcountReadcount计数减计数减1 1，在第一个读者，在第一个读者到达共享数据区到达共享数据区之之后以及后以

48、及最后一个读者离开最后一个读者离开共享数据区之前，写者共享数据区之前，写者不能访问不能访问共享数据区。共享数据区。 思考：需要几个信号量？是什么类型信号量？思考：需要几个信号量？是什么类型信号量？ 为了解决读者为了解决读者写者问题，我们设置了两个互斥信号量：写者问题，我们设置了两个互斥信号量： 信号量信号量wmutexwmutex，用于写者与写者之间、读者与写者、写者与读者用于写者与写者之间、读者与写者、写者与读者之间对共享数据区操作的互斥，初值为之间对共享数据区操作的互斥，初值为1 1； 信号量信号量rmutexrmutex，用于多个读者对共享计数器用于多个读者对共享计数器Readcount

49、(Readcount(临界资源临界资源) )操作的互斥，初值为操作的互斥，初值为1 1。第二章进 程 管 理 读者读者写者问题可描述如下写者问题可描述如下:Semaphore rmutex=1，wmutex1, readcount=0；读者：读者：void reader() do wait(rmutex)；/*读进程要进入先修改读进程要进入先修改Readcount*/ if (readcount=0) then wait(wmutex)； /*如尚无读进程，读进程需执行如尚无读进程，读进程需执行wait(wmutex) 。 1、 如如wmutex=1(成功成功)，说明无写进程在写，说明无写进程

50、在写， 则则wmutex=0（锁住写进程），读进程可进入读。（锁住写进程），读进程可进入读。 2、 如如wmutex=0（不成功），说明有写进程在写，则读进程阻塞等待。不成功），说明有写进程在写，则读进程阻塞等待。*/ readcount+；/* 如成功进入，读者加一如成功进入，读者加一*/ signal(rmutex)； /*读进程对读进程对readcount访问结束访问结束*/ perform read operation；/*执行读操作执行读操作*/ wait(rmutex)； /*读进程退出要修改读进程退出要修改Readcount*/ readcount-；/* 读者减一读者减一 */ if (readcount