《第二章_进程管理下.ppt》由会员分享，可在线阅读，更多相关《第二章_进程管理下.ppt（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 操作系统 第二章 进程管理2.5 进程互斥一、互斥的概念1资源共享引起的制约间接制约 在在多多道道程程序序系系统统中中，各各进进程程并并发发执执行行，并并以以各各自自独独立立的的速速度度向向前前推推进进。当当并并发发进进程程竞竞争争使使用用同同一一资资源源（如如处处理理机机、主主存存空空间间、I/OI/O设设备备以以及及文文件件等等一一类类资资源源）时时，它它们们之之间间会会发发生生冲冲突突，竞竞争争资资源源的的进进程程之之间间没没有有任任何何信信息息交交换换，但但是是，一一个个进进程程的的执执行行可可能能会会影影响响到到竞竞争争进进程程的的行行为为。例例如如，两两个个进进程程都都期期望望访
2、访问问同同一一个个资资源源，操操作作系系统统把把这这个个资资源源分分配配给给其其中中一一个个进进程程，另另一一个个就就必必须须等等待待。这这种种由由竞竞争争共共享享资资源源带带来来的进程之间的相互制约的关系称为的进程之间的相互制约的关系称为间接制约关系间接制约关系。1 操作系统 第二章 进程管理2临界资源与临界区 如如若若两两个个或或更更多多的的进进程程需需要要访访问问打打印印机机，在在并并发发执执行行的的过过程程当当中中，若若让让它它们们任任意意使使用用，则则可可能能发发生生的的情情况况是是多多个个进进程程交交替替使使用用打打印印机机，输输出出结结果果交交织织在在一一起起，很很难难区区分分。
3、解解决决的的方方法法是是任任何何一一个个进进程程在在使使用用打打印印机机打打印印整整个个文文件件时时，都独占打印机的控制权，直到打印完成释放打印机为止。都独占打印机的控制权，直到打印完成释放打印机为止。临界资源：临界资源：一次仅允许一个进程使用的资源。一次仅允许一个进程使用的资源。许多物理设备都属于临界资源，例如：输入机、打印许多物理设备都属于临界资源，例如：输入机、打印机、绘图机等；此外，还有许多软件资源，例如：共享的机、绘图机等；此外，还有许多软件资源，例如：共享的变量、数据、表格、队列等也属于临界资源。它们虽然可变量、数据、表格、队列等也属于临界资源。它们虽然可被若干进程所共享，但一次只
4、能为一个进程所利用。被若干进程所共享，但一次只能为一个进程所利用。2 操作系统 第二章 进程管理 设某时刻游艺场的在设某时刻游艺场的在场人数场人数countcount为为n n，这时有这时有一个人进场，同时有一个一个人进场，同时有一个人退场。由于进场和退场是随机的，因此进程人退场。由于进场和退场是随机的，因此进程PINPIN和和POUTPOUT的的执行是并发的。执行是并发的。例如例如:某游艺场设置了一个自动计数系统，用一个计数器某游艺场设置了一个自动计数系统，用一个计数器countcount指示在场的人数。指示在场的人数。当有一个人进场时，当有一个人进场时，由进程由进程PINPIN实现计数加实
5、现计数加1 1；当有一个人退场时，由进当有一个人退场时，由进程程POUTPOUT实现计数减实现计数减1 1。countR1countR1 R1+1R1 R1+1R1R1countR1countcountR2 countR2 R2R21R21R2R2countR2count进程进程PINPIN 进程进程POUT POUT 如如果果这这两两个个进进程程按按下下述述不不同同顺顺序序执执行行时时，执执行行的的结结果果分分别如下：别如下：3 操作系统 第二章 进程管理1 1）进程）进程PINPIN和和POUTPOUT各自顺序执行：各自顺序执行：假假若若进进程程PINPIN先先执执行行，结结束束之之后后进
6、进程程POUTPOUT再再执执行行，两两个个进进程程分分别别完完成成了了对对countcount的的计计数数加加1 1和和计计数数减减1 1的的工工作作，countcount的计数值保持为的计数值保持为n n，显然，这个结果是正确的。显然，这个结果是正确的。2 2）进程）进程PINPIN和和POUTPOUT交替执行各个操作：交替执行各个操作：假若：假若：PIN R1PIN R1：=count=count；POUT R2POUT R2：=count=count；PIN R1PIN R1：=R1+1=R1+1；countcount：=R1=R1；POUT R2POUT R2：=R2=R21 1；c
7、ountcount：=R2=R2；执行完毕时，执行完毕时，count count 的的计数值为计数值为n-1n-1。假若：假若：PIN R1PIN R1：=count=count；POUT R2POUT R2：=count=count；R2R2：=R2=R21 1；countcount：=R2=R2；PIN R1PIN R1：=R1+1=R1+1；countcount：=R1=R1；执行完毕时，执行完毕时，count count 的的计数值为计数值为n+1n+1。上述两种结果和实际的情况不一致，即发生上述两种结果和实际的情况不一致，即发生与时间有关的错误与时间有关的错误。4 操作系统 第二章
8、进程管理 问题的关键在于共享变量问题的关键在于共享变量countcount，两个进程访问这个共两个进程访问这个共享变量，如果一个进程修改了享变量，如果一个进程修改了countcount，完成了对完成了对countcount的一的一部分操作，然后被中断，另一个进程在第一个进程使用完部分操作，然后被中断，另一个进程在第一个进程使用完countcount的值之前又修改了的值之前又修改了countcount，从而造成了从而造成了countcount计数值的计数值的错误；错误；如果一次只允许一个进程对共享变量如果一次只允许一个进程对共享变量countcount进行访问，进行访问，就能解决这个问题，共享变
9、量就能解决这个问题，共享变量countcount属于临界资源。属于临界资源。要防止临界资源使用过程中发生要防止临界资源使用过程中发生“与时间有关的错误与时间有关的错误”，惟一的办法是，惟一的办法是控制访问临界资源的各进程的执行控制访问临界资源的各进程的执行,实现对实现对临界资源的互斥访问。临界资源的互斥访问。临界区临界区：每个进程中访问临界资源的那一部分程序每个进程中访问临界资源的那一部分程序。注意：临界区是对某一资源而言的，对于不同资源的临界注意：临界区是对某一资源而言的，对于不同资源的临界 区，它们之间是无关的，所以不必互斥地执行。区，它们之间是无关的，所以不必互斥地执行。5 操作系统 第
10、二章 进程管理3.互斥 在操作系统中，当一个进程进入临界区访问临界资源在操作系统中，当一个进程进入临界区访问临界资源时，另一个欲进入相关临界区的进程必须等待，直到占用时，另一个欲进入相关临界区的进程必须等待，直到占用临界资源的进程退出临界区后，另一个进程才可以进入临临界资源的进程退出临界区后，另一个进程才可以进入临界区，进程之间这种相互制约的关系称为界区，进程之间这种相互制约的关系称为互斥互斥。即进程的即进程的互斥互斥就是两个或两个以上的进程不能同时进就是两个或两个以上的进程不能同时进入共享同一临界资源的入共享同一临界资源的(相关相关)临界区。临界区。6 操作系统 第二章 进程管理1 1）若若
11、有有多多个个进进程程同同时时要要求求进进入入它它们们的的临临界界区区时时，应应在在有有限限的的时时间间内内让让其其中中之之一一进进入入临临界界区区，而而不不应应相相互互阻阻塞塞，以以致于各进程都不能进入临界区；致于各进程都不能进入临界区；2 2）每次至多只允许一个进程处于临界区；每次至多只允许一个进程处于临界区；3 3）进程在临界区内仅停留有限的时间。进程在临界区内仅停留有限的时间。实实现现进进程程互互斥斥，也也就就是是实实现现对对于于临临界界区区的的管管理理。为为了了保保证证共共享享临临界界资资源源的的各各进进程程在在临临界界区区互互斥斥地地执执行行，提提出出了了对临界区管理的原则：对临界区
12、管理的原则：4.对临界区管理的原则 7 操作系统 第二章 进程管理 根根据据上上述述对对临临界界区区的的管管理理原原则则，可可以以得得出出临临界界区区的的调调度原则：度原则：1 1）空空闲闲让让进进:当当无无进进程程处处于于临临界界区区内内时时，允允许许一一个个进进程程进进入入临界区；临界区；2 2）忙忙则则等等待待:当当某某一一个个进进程程已已进进入入临临界界区区时时，其其它它欲欲进进入入临临界区的进程必须等待；界区的进程必须等待；3 3）有有限限等等待待:当当某某一一个个进进程程离离开开临临界界区区时时，若若有有进进程程等等待待进进入临界区，则允许其中一个进程进入临界区入临界区，则允许其中
13、一个进程进入临界区;4 4）让让权权等等待待:当当进进程程不不能能进进入入自自己己的的临临界界区区时时，应应立立即即释释放放处理机处理机。8 操作系统 第二章 进程管理 实现进程互斥的同步机构：实现进程互斥的同步机构：锁机制、信号量和锁机制、信号量和PVPV操作机操作机制制、管程机制。、管程机制。二、锁机制 1.1.锁：锁：使用一个标志或一个变量来代表临界资源的状态。使用一个标志或一个变量来代表临界资源的状态。W=1W=1为锁被关闭，表示该资源已占用；为锁被关闭，表示该资源已占用；W=0W=0为锁已打开，表示该资源空闲，未被占用。为锁已打开，表示该资源空闲，未被占用。系统提供一对在锁位系统提供
14、一对在锁位W W上进行操作的上锁原语上进行操作的上锁原语LockLock（W W）和开锁原语和开锁原语UnLockUnLock（W W）。）。进程互斥的实现可以采用软件的方法，也可以通过系统提进程互斥的实现可以采用软件的方法，也可以通过系统提供的同步机构来协调进程间的关系。供的同步机构来协调进程间的关系。9 操作系统 第二章 进程管理2.上锁原语Lock（W）：测试测试W W的值，若的值，若W=1W=1，表示资源正在使用，继续反复测试；表示资源正在使用，继续反复测试；若若W=0W=0，则设置则设置W=1W=1（上锁）。上锁）。上锁原语算法上锁原语算法:locklock(w(w）begin be
15、gin test:if(w=1 test:if(w=1）gotogoto test test else w=1 else w=1；endend W=1 W=1？1W1W 入口入口 返回返回是是否否10 操作系统 第二章 进程管理3.开锁原语UnLock（W）：设置设置W=0W=0（开锁）。开锁）。0W0W 入口入口 返回返回开锁原语算法开锁原语算法:UnlockUnlock(w(w）begin begin w=0;w=0;end end 在测试锁位在测试锁位W W的值和设置锁位的值和设置锁位W W的值为的值为1 1的这两步之间，的这两步之间，锁位锁位W W的值不得被其它进程所改变，这是应该绝对
16、保证的，的值不得被其它进程所改变，这是应该绝对保证的，因此采用了在锁位因此采用了在锁位W W上的原语操作。上的原语操作。有些系统中，机器在硬件中提供了专门的硬件指令有些系统中，机器在硬件中提供了专门的硬件指令Test Test and Setand Set（简称简称TSTS）来完成上述的上锁和开锁操作。例如，来完成上述的上锁和开锁操作。例如，在在IBM/370IBM/370中就有一条称为中就有一条称为“测试并置位测试并置位”的的TSTS指令。指令。11 操作系统 第二章 进程管理4.用上锁原语和开锁原语实现进程互斥 利利用用上上锁锁原原语语和和开开锁锁原原语语可可以以解解决决并并发发进进程程对
17、对临临界界区区访问的互斥问题。访问的互斥问题。任任何何申申请请进进入入临临界界区区的的进进程程，必必须须先先执执行行上上锁锁原原语语。若若上上锁锁原原语语顺顺利利通通过过，则则进进程程可可以以进进入入临临界界区区，这这时时临临界界区区已已被被上上锁锁原原语语锁锁住住，其其它它申申请请进进入入临临界界区区的的进进程程只只能能等等到到临临界界区区开开锁锁之之后后才才有有可可能能进进入入临临界界区区；当当进进程程完完成成对对临临界界资资源源的的访访问问退退出出临临界界区区时时再再执执行行开开锁锁原原语语，以以释释放放该该临临界资源。界资源。12 操作系统 第二章 进程管理上锁原语上锁原语 临界区临界
18、区CSCSA A开锁原语开锁原语上锁原语上锁原语 临界区临界区CSCSA A开锁原语开锁原语进程进程A A进程进程B B13 操作系统 第二章 进程管理进程使用临界资源的操作流程进程使用临界资源的操作流程 R1+1R1 R1count countR2countR2 R2+2R2 R1count 上锁原语上锁原语Lock(W)Lock(W)开锁原语开锁原语UnLock(WUnLock(W)countR1 上锁原语上锁原语Lock(WLock(W)开锁原语开锁原语UnLock(WUnLock(W)进程进程PINPIN 进程进程POUTPOUT 临界区临界区 临界区临界区14 操作系统 第二章 进程
19、管理2.6 信号量和PV操作一、信号量的概念 在在操操作作系系统统中中，信信号号量量是是表表示示资资源源的的实实体体，是是一一个个特特殊殊的的变变量量，其其值值仅仅能能由由PVPV操操作作来来改改变变。操操作作系系统统利利用用信信号号量量的的状态对进程和资源进行管理状态对进程和资源进行管理。信信号号量量是是一一个个确确定定的的二二元元组组(s(s，q)q)，s s是是一一个个具具有有非非负负初初值值的的整整型型变变量量，q q是是一一个个初初始始状状态态为为空空的的进进程程PCBPCB队队列列的的首首指指针针。因因此此，一一个个信信号号量量w w包包括括两两个个部部分分：即即整整数数值值部部分
20、分w.sw.s和指针部分和指针部分w.qw.q。w.sw.sw.qw.q信号量信号量w w 15 操作系统 第二章 进程管理信号量的物理含义：信号量的物理含义：从从资资源源观观点点来来看看，s s的的值值表表示示系系统统中中某某类类可可用用资资源源的的数数目目。其其大于等于零大于等于零时，表示系统中当前时，表示系统中当前可用资源的数目可用资源的数目；其其小小于于零零时时，其其绝绝对对值值表表示示系系统统中中还还欠欠缺缺的的资资源源数数目目，(即正在即正在等待使用临界资源的进程数等待使用临界资源的进程数)。w.sw.sw.qw.q PCBPCB队列队列 建建立立一一个个信信号号量量必必须须说说明
21、明该该信信号号量量所所代代表表的的意意义义，并并赋初值，而信号量的值仅能由赋初值，而信号量的值仅能由PVPV操作原语来改变。操作原语来改变。16 操作系统 第二章 进程管理二、P、V操作 PVPV操作是操作是P P操作原语操作原语P P（s s）和）和V V操作原语操作原语V V（s s）的简称，的简称，是定义在信号量上的两个操作原语，在执行期间不可分割。是定义在信号量上的两个操作原语，在执行期间不可分割。P P操作原语操作原语P P（s s）的过程：的过程：(P(P（s s）-wait(swait(s)1 1）s s的值减的值减1 1；2 2）若若相相减减的的结结果果大大于于或或等等于于零零
22、，则则调调用用P P（s s）的的进进程程继继续续执行；执行；3 3）若若相相减减的的结结果果小小于于零零，则则调调用用P P（s s）的的进进程程被被阻阻塞塞，并并插入到该信号量的等待队列中，然后转进程调度程序。插入到该信号量的等待队列中，然后转进程调度程序。17 操作系统 第二章 进程管理 P(S)P(S)操作操作算法算法p p begin begin s=s s=s 1 1；if s0if s0 保护调用进程的保护调用进程的CPUCPU现场；现场；将该进程入将该进程入s s的等待队列；的等待队列；置该进程为置该进程为“等待等待”状态；状态；转进程调度；转进程调度；end end s-1s
23、 s-1s s0?s0?调用进程入等待队列调用进程入等待队列 转进程调度转进程调度 入口入口 继续继续是是否否18 操作系统 第二章 进程管理V V操作原语操作原语V V（s s）的过程：的过程：(V V（s s）-signal(ssignal(s)（1 1）s s的值加的值加1 1；（2 2）若相加的若相加的结果大于零，则进程继续执行；结果大于零，则进程继续执行；（3 3）若若相相加加的的结结果果小小于于或或等等于于零零，则则从从该该信信号号量量的的等等待待队队列列中中唤唤醒醒一一等等待待进进程程，然然后后返返回回原原进进程程继继续续执执行行或或转转进进程程调调度程序。度程序。从从PVPV操
24、操作作原原语语的的定定义义中中可可以以看看出出，当当进进程程调调用用P P操操作作，判判断断s s的的值值小小于于零零时时，调调用用P P（s s）的的进进程程被被阻阻塞塞后后，该该进进程程并并没没有有象象锁锁机机制制中中那那样样陷陷入入“忙忙等等待待”，而而是是“让让权权等等待待”，放放弃弃占占用用处处理理机机而而进进入入等等待待队队列列，然然后后转转进进程程调调度度程程序序重重新新选选择择一一个个进进程程占占用用处处理理机机。从从而而避避免免了了处处理理机机的的空空耗耗，提提高了处理机的效率。高了处理机的效率。19 操作系统 第二章 进程管理V(S)V(S)操作操作算法算法V V begi
25、n begin s=s+1 s=s+1；if sif s0 0 移出移出s s等待队列首元素；等待队列首元素；将该进程入就绪队列；将该进程入就绪队列；置该进程为置该进程为“就绪就绪”状态；状态；end end唤醒等待队列中的一个进程唤醒等待队列中的一个进程返回或转进程调度返回或转进程调度 s+1s s+1s入口入口 继续继续 s0?s0?是是否否20 操作系统 第二章 进程管理三、用信号量实现进程互斥 利用信号量能方便地解决临界区问题。利用信号量能方便地解决临界区问题。设设有有n n个个进进程程，用用数数组组P(i)P(i)表表示示，设设与与n n个个进进程程共共享享的的临临界界资资源源对对应
26、应的的互互斥斥信信号号量量为为s s。信信号号量量初初始始化化为为1 1，表表示示初初始始状状态态时时共共享享资资源源是是空空闲闲的的。只只需需把把各各个个进进程程临临界界区区的的程程序序段段置于置于P P（s s）和）和V V（s s）之间即可实现之间即可实现n n个进程的互斥。个进程的互斥。P P（s s）V V（s s）临界区临界区1 1 P P（s s）P P（s s）临界区临界区i i 临界区临界区n n V V（s s）V V（s s）进程进程P P（1 1）进程进程P P（i i）进程进程P P（n n）21 操作系统 第二章 进程管理2 2）进进程程每每执执行行一一次次V V操
27、操作作，信信号号量量的的数数值值加加1 1，意意味味着着进进程程释放一个单位的资源释放一个单位的资源。当当s s0 0，说说明明系系统统中中没没有有进进程程在在等等待待此此类类资资源源，则则释释放放资源的进程继续执行；资源的进程继续执行；当当s0s0，说说明明此此信信号号量量的的等等待待队队列列中中有有等等待待进进程程，那那么么应应唤唤醒醒等等待待队队列列中中的的一一个个进进程程，将将释释放放的的资资源源分分配配给给它它，使使其能获取所需资源，然后释放资源的进程可继续执行下去。其能获取所需资源，然后释放资源的进程可继续执行下去。当当s s0 0，表表示示系系统统已已无无资资源源可可用用，所所有
28、有的的此此类类资资源源均均已已被被占占用用，则则应应将将该该进进程程阻阻塞塞，并并插插入入等等待待队队列列。此此时时，s s的的绝对值表示信号量绝对值表示信号量s s的等待队列中的进程数。的等待队列中的进程数。注意：注意：信号量和信号量和PVPV操作的物理含义操作的物理含义1 1）进进程程每每执执行行一一次次P P操操作作，信信号号量量的的数数值值减减1 1，意意味味着着进进程程申请分配一个单位的资源申请分配一个单位的资源。当当s0s0，表示了某类可用资源的数量表示了某类可用资源的数量;22 操作系统 第二章 进程管理分析信号量分析信号量s s的取值范围的取值范围 例如：设一民航售票系统有例如
29、：设一民航售票系统有n n个售票处。每个售票处通个售票处。每个售票处通过终端访问系统中的公用数据区，假定公共数据区中的一过终端访问系统中的公用数据区，假定公共数据区中的一些单元些单元xkxk（k=1k=1，2 2，m m）分别存放分别存放月月日日次次航班的现存票数。设航班的现存票数。设P1 P1，P2P2，PnPn表示各售票处的表示各售票处的处理程序，处理程序，R1R1，R2R2，RnRn表示各进程执行时所用的工表示各进程执行时所用的工作单元。作单元。23 操作系统 第二章 进程管理用信号量实现各进程间的互斥用信号量实现各进程间的互斥beginbegin cobegin cobegin pro
30、cess Pi process Pi（i=1i=1，2 2，n n）beginbegin 按旅客订票要求找到按旅客订票要求找到xkxk（k=1k=1，2 2，m m）；RiRi=xkxk；if Ri1 then if Ri1 then begin begin RiRi=Ri-1=Ri-1；xkxk=RiRi；输出一张票；输出一张票；endend else else 输出输出“票已售完票已售完”；endend；coendcoend；endend；sksk：semaphoresemaphore；sksk=1=1；P P（sksk）；）；V V（sksk）；V V（sksk）；）；beginbegi
31、nendend；信号量信号量SkSk的取值范围是：的取值范围是：1 1到到 -（n n 1 1）之间的整之间的整数数24 操作系统 第二章 进程管理2.7 进程同步一、同步的概念 异步环境中的各进程并发执行，并以各自独立的速度向异步环境中的各进程并发执行，并以各自独立的速度向前推进，并发执行的进程之间可能由于前推进，并发执行的进程之间可能由于合作完成同一任务合作完成同一任务而而相互支持和依赖，从而引发出进程间的相互支持和依赖，从而引发出进程间的直接制约关系直接制约关系。异步环境：异步环境：主要指各并发进程的执行起始时间的随机性和执主要指各并发进程的执行起始时间的随机性和执行速度的独立性。行速度
32、的独立性。直接制约关系带来进程的同步。亦即，一组相互合作的直接制约关系带来进程的同步。亦即，一组相互合作的并发进程，为了协调其推进速度，在一些关键点上可能需要并发进程，为了协调其推进速度，在一些关键点上可能需要相互等待或互通消息，进程之间这种相互制约的关系称作相互等待或互通消息，进程之间这种相互制约的关系称作进进程同步程同步。具有同步关系的一组并发进程称为。具有同步关系的一组并发进程称为合作进程合作进程（或（或相相关进程关进程）。）。25 操作系统 第二章 进程管理（一）按规定次序执行的合作进程的同步（一）按规定次序执行的合作进程的同步一般同步问题可以分为两类：一般同步问题可以分为两类：1 1
33、）保证一组合作进程按逻辑需要所确定的执行次序；）保证一组合作进程按逻辑需要所确定的执行次序；2 2）保证共享缓冲区）保证共享缓冲区(或共享数据或共享数据)的合作进程的同步。的合作进程的同步。二、同步的例子26 操作系统 第二章 进程管理例如：例如：A A，B B两个进程通过一个缓冲区合作完成一项任务，两个进程通过一个缓冲区合作完成一项任务，A A进进程将将从卡片机读入的数据送入缓冲区，程将将从卡片机读入的数据送入缓冲区，B B进程从缓冲区中取进程从缓冲区中取走数据进行处理。当缓冲区空时，走数据进行处理。当缓冲区空时，B B进程因得不到数据而阻塞，进程因得不到数据而阻塞，只有当只有当A A进程将
34、数据送入缓冲区时才将进程将数据送入缓冲区时才将B B进程唤醒。反之，当进程唤醒。反之，当缓冲区已满，缓冲区已满，A A进程不能继续送数据而阻塞，只有当进程不能继续送数据而阻塞，只有当B B进程取进程取走数据时才唤醒走数据时才唤醒A A进程。进程。缓存区缓存区 P P A A P PB B 从读卡机读入数据从读卡机读入数据从缓存区中取数据从缓存区中取数据 将数据送入缓存区将数据送入缓存区 加工处理数据加工处理数据 P P A A P PB B（二）共享缓冲区的合作进程的同步（二）共享缓冲区的合作进程的同步27 操作系统 第二章 进程管理例例1:P1:PA A,P,PB B,P,PC C为一组合作
35、进程，其进程流图如下所示，试用为一组合作进程，其进程流图如下所示，试用信号量实现这三个进程的同步。信号量实现这三个进程的同步。设两个同步信号量设两个同步信号量S SB B，S SC C：S SB B表示表示P PA A发给发给P PB B的能开始执行的能开始执行的消息，其初值为的消息，其初值为0 0；S SC C表示表示P PA A发给发给P PC C的能开始执行的能开始执行消息消息，其初值为，其初值为0 0。三、用信号量机制实现进程同步 要实现进程的同步就必须提供一种同步机制，该机制能要实现进程的同步就必须提供一种同步机制，该机制能把其它进程需要的消息发送出去，也能测试自己等待的消息把其它进
36、程需要的消息发送出去，也能测试自己等待的消息是否到达。是否到达。28 操作系统 第二章 进程管理算法描述：算法描述：begin begin int S int SB B=0=0；intint S SC C=0;=0;cobegin cobegin process Pprocess PA A beginbegin V(SV(SB B););V(SV(SC C););endend processprocessP PB B beginbegin P(SP(SB B););endend processprocess P PC C beginbegin P(SP(SC C););endend coend
37、coendendend29 操作系统 第二章 进程管理（二）（二）共享缓冲区的合作进程的同步共享缓冲区的合作进程的同步例如：设某计算进程例如：设某计算进程cpcp和打印进程和打印进程iopiop共用一个单缓冲，如下共用一个单缓冲，如下图所示。其中，图所示。其中，cpcp进程负责不断地计算数据并送入缓冲区进程负责不断地计算数据并送入缓冲区bufbuf中，中，iopiop进程负责从缓冲区进程负责从缓冲区bufbuf中取出数据去打印。中取出数据去打印。缓冲区缓冲区bufbuf cpcp进程和进程和iopiop进程必须遵进程必须遵循以下同步规则：循以下同步规则：(1)(1)当当cpcp进程进程把计算结
38、果送入把计算结果送入bufbuf时，时，iopiop进程才能从进程才能从bufbuf中中取出结果去打印，否则必须取出结果去打印，否则必须等待。等待。(2)(2)当当iopiop进程把进程把bufbuf中的数据取出打印后，中的数据取出打印后，cpcp进程才能把下一进程才能把下一个计算结果送入个计算结果送入bufbuf中，即只有当中，即只有当bufbuf为空时，为空时，cpcp进程才能动进程才能动作，否则必须等待。作，否则必须等待。30 操作系统 第二章 进程管理beginbegin int int fullfull=0=0；intint emptyempty=1;=1;cobegin cobeg
39、in processprocess cpcp beginbegin LcLc:得到一个进程结果；得到一个进程结果；P(P(emptyempty););将数送到缓冲区中；将数送到缓冲区中；V(V(fullfull););gotogoto LcLc;end end process process iopiop begin begin Lo:Lo:P(fullP(full););从缓冲区中取一数；从缓冲区中取一数；V(emptyV(empty););从打印机上输出；从打印机上输出；gotogoto Lo;Lo;end end coendcoendendend 设置两个信号量设置两个信号量fullfu
40、ll和和emptyempty。fullfull用来表示缓冲区中是用来表示缓冲区中是否有可供打印的计算结果，初值为否有可供打印的计算结果，初值为0 0。emptyempty用以表示缓冲区用以表示缓冲区有无空位置存放新的信息，初值为有无空位置存放新的信息，初值为1 1。算法描述如下：算法描述如下：表示表示bufbuf中有无信息中有无信息表示表示bufbuf中有无空位置中有无空位置31 操作系统 第二章 进程管理四、四、生产者生产者消费者问题消费者问题 生产者生产者消费者问题是一个典型的同步例子。消费者问题是一个典型的同步例子。它描述了一组生产者向一组消费者提供产品（数据），它描述了一组生产者向一组
41、消费者提供产品（数据），它们共享一个有界缓冲区，生产者向其中投放产品，消费者它们共享一个有界缓冲区，生产者向其中投放产品，消费者从中取出产品消费。这样的一个问题是许多相互合作进程存从中取出产品消费。这样的一个问题是许多相互合作进程存在的内在关系的一种抽象。在的内在关系的一种抽象。一组生产者一组生产者P1P1、P2P2、PmPm一组消费者一组消费者C1C1、C2C2、CkCk有界缓冲区有界缓冲区长度为长度为n n（n n 0 0）32 操作系统 第二章 进程管理 只要缓冲区未满，生产者就可把产品送入缓冲区；只要只要缓冲区未满，生产者就可把产品送入缓冲区；只要缓冲区未空，消费者便可从缓冲区取走产品
42、并消耗它。缓冲区未空，消费者便可从缓冲区取走产品并消耗它。仅当缓冲区满时，生产者被阻塞，类似地，缓冲区空时，仅当缓冲区满时，生产者被阻塞，类似地，缓冲区空时，消费者被阻塞。消费者被阻塞。生产者和消费者的同步关系将禁止生产者向满的缓冲区生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品，也禁止消费者从空的缓冲区中提取物品。输送产品，也禁止消费者从空的缓冲区中提取物品。P1P1P2P2P3P3Pm-1Pm-1PmPm C1C1C2C2C3C3Ck-1Ck-1CkCk缓冲区缓冲区33 操作系统 第二章 进程管理信号量的功能：信号量的功能：消费者在信号量上做消费者在信号量上做P P操作来表示消耗
43、一个资源，生产操作来表示消耗一个资源，生产者通过在同一信号量上做者通过在同一信号量上做v v操作表示生产一个资源。计数器操作表示生产一个资源。计数器在每次在每次P P操作后减操作后减1 1，而在每次，而在每次V V操作中增操作中增1 1。这一计数器的初。这一计数器的初始值是可利用的资源数目。当资源是不可利用时，将申请资始值是可利用的资源数目。当资源是不可利用时，将申请资源的进程放置到等待队列中，如果有一个资源释放，在等待源的进程放置到等待队列中，如果有一个资源释放，在等待队列中的第一个进程被唤醒并得到资源的控制权。队列中的第一个进程被唤醒并得到资源的控制权。为解决这一类生产者为解决这一类生产者
44、消费者问题，应设置两个同步信号量：消费者问题，应设置两个同步信号量：1 1）avail:avail:表示空缓冲单元的数目表示空缓冲单元的数目，初值为缓冲区的大小初值为缓冲区的大小n;n;2 2）full:full:表示满缓冲单元表示满缓冲单元(即产品）的数目，初值为即产品）的数目，初值为0 0；由于有界缓冲区是一个临界资源，必须互斥使用，所以，另由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量：外还需要设置一个互斥信号量：3 3）mutexmutex:互斥信号量，初值为互斥信号量，初值为l l。34 操作系统 第二章 进程管理生产者生产者消费者问题消费者问题 生产
45、者进程生产者进程Pi(i=1,2,Pi(i=1,2,m),m)消费者进程消费者进程Cj(j=1,2,Cj(j=1,2,k),k)产品送入缓冲区产品送入缓冲区 P(avail)P(avail)P(mutex)P(mutex)V(mutex)V(mutex)V(full)V(full)生产一个产品生产一个产品 从缓冲区取一个产品从缓冲区取一个产品 P(mutex)P(mutex)V(avail)V(avail)V(mutex)V(mutex)消耗该产品消耗该产品 P(full)P(full)35 操作系统 第二章 进程管理生产者生产者消费者问题算法描述消费者问题算法描述 beginbegin in
46、t full=0 int full=0；int avail=n;int avail=n;int mutex=1;int mutex=1;int int ti,tjti,tj=0;=0;cobegin cobegin process produceri process produceri begin begin Lp:Lp:生产一个产品；生产一个产品；P(avail);P(avail);P(mutex);P(mutex);送一个产品到送一个产品到titi缓冲区；缓冲区；titi=(ti+1)mod n;=(ti+1)mod n;V(mutex);V(mutex);V(full);V(full);
47、goto goto LpLp end end process process consumerjconsumerj begin begin LcLc:P(full);P(full);P(mutex);P(mutex);从缓冲区从缓冲区tjtj中中取产品取产品；tjtj=(tj+1)mod n;=(tj+1)mod n;V(mutex);V(mutex);V(avail);V(avail);消费一个产品；消费一个产品；gotogoto LcLc end end coend coend end end36 操作系统 第二章 进程管理分析信号量分析信号量s s的取值范围的取值范围 例如：设一民航售票
48、系统有例如：设一民航售票系统有n n个售票处。每个售票处通个售票处。每个售票处通过终端访问系统中的公用数据区，假定公共数据区中的一过终端访问系统中的公用数据区，假定公共数据区中的一些单元些单元xkxk（k=1k=1，2 2，m m）分别存放分别存放月月日日次次航班的现存票数。设航班的现存票数。设P1 P1，P2P2，PnPn表示各售票处的表示各售票处的处理程序，处理程序，R1R1，R2R2，RnRn表示各进程执行时所用的工表示各进程执行时所用的工作单元。作单元。37 操作系统 第二章 进程管理用信号量实现各进程间的互斥用信号量实现各进程间的互斥beginbegin cobegin cobegi
49、n process Pi process Pi（i=1i=1，2 2，n n）beginbegin 按旅客订票要求找到按旅客订票要求找到xkxk（k=1k=1，2 2，m m）；RiRi=xkxk；if Ri1 then if Ri1 then begin begin RiRi=Ri-1=Ri-1；xkxk=RiRi；输出一张票；输出一张票；endend else else 输出输出“票已售完票已售完”；endend；coendcoend；endend；sksk：semaphoresemaphore；sksk=1=1；P P（sksk）；）；V V（sksk）；V V（sksk）；）；begi
50、nbeginendend；信号量信号量SkSk的取值范围是：的取值范围是：1 1到到 -（n n 1 1）之间的整之间的整数数38 操作系统 第二章 进程管理例例 ：用信号量实现司机和售票员间的同步。：用信号量实现司机和售票员间的同步。司机司机 售票员售票员 正常行车正常行车 到站停车到站停车 售售 票票 开车门开车门 关车门关车门 离站开车离站开车设：设：S1S1和和S2S2分别为司机和售票员的私用信号量，其初值均为分别为司机和售票员的私用信号量，其初值均为0 0，信号量信号量S1S1表示售票员通知司机表示售票员通知司机“可以开车可以开车”的消息（信号），的消息（信号），信号量信号量S2S2