《第二章进程管理》由会员分享，可在线阅读，更多相关《第二章进程管理（153页珍藏版）》请在金锄头文库上搜索。
1、第2章 进程管理2.1 2.1 进程的基本概念进程的基本概念 2.2 2.2 进程控制进程控制 2.3 2.3 进程同步进程同步 2.4 2.4 经典进程的同步问题经典进程的同步问题 2.5 2.5 管程机制管程机制 2.6 2.6 进程通信进程通信 2.7 2.7 线程线程 2.1.1 2.1.1 程序顺序执行与特征程序顺序执行与特征v顺序环境是指：顺序环境是指：在计算机系统中只有一个程序在运行，在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响。这个程序独占系统中所有资源，其执行不受外界影响。v一个较大的程序通常都由若干个程序段组成，程序在执一个较大的程序通常
2、都由若干个程序段组成，程序在执行时，各程序段必须按照先后次序逐个执行。程序各程行时，各程序段必须按照先后次序逐个执行。程序各程序段先后执行次序关系可用序段先后执行次序关系可用前趋图前趋图表示。表示。v前趋图前趋图是一个有向无循环图，图由结点和结点间有向边是一个有向无循环图，图由结点和结点间有向边组成，结点代表各程序段操作，而结点间的有向边表示组成，结点代表各程序段操作，而结点间的有向边表示两程序段操作之间存在的前趋关系（两程序段操作之间存在的前趋关系（“”）。两程序。两程序段段PiPi和和PjPj的前趋关系表示成的前趋关系表示成PiPiPjPj，PiPi是是PjPj的的前趋，前趋，PjPj是是
3、PiPi的的后继。后继。P1C C1 1I1I2C2P22.1 2.1 进程的基本概念进程的基本概念注意：注意：前趋图中前趋图中必须不存必须不存在循环。在循环。v 程序顺序执行特征：程序顺序执行特征： 1.1.顺序性顺序性：程序各程序段严格按照规定的顺序执行。：程序各程序段严格按照规定的顺序执行。 2.2.封闭性封闭性：独占资源，执行过程中不受外界影响。：独占资源，执行过程中不受外界影响。 3.3.结果的确定性（结果可再现性）结果的确定性（结果可再现性）：只要程序执行：只要程序执行 环境和初始条件相同，程序多次执行，可获得相环境和初始条件相同，程序多次执行，可获得相 同结果。同结果。2.1.3
4、 2.1.3 程序并发执行与特征程序并发执行与特征v并发环境：两个或两个以上的程序在计算机系统中同并发环境：两个或两个以上的程序在计算机系统中同时处于开始运行但尚未结束的状态。时处于开始运行但尚未结束的状态。v如上述有三个程序段的作业类，虽然每个作业有前趋如上述有三个程序段的作业类，虽然每个作业有前趋关系的各程序段不能在系统关系的各程序段不能在系统CPUCPU和输入输出各部件并和输入输出各部件并行执行，但一个作业没有前趋关系的程序段或不同作行执行，但一个作业没有前趋关系的程序段或不同作业的程序段可以分别在业的程序段可以分别在CPUCPU和各输入输出部件上并行和各输入输出部件上并行执行。执行。
5、四个上述三个程序段类的作业并发执行的前趋图四个上述三个程序段类的作业并发执行的前趋图C3I I1 1I2I3I4C1C2C4P1P2P3P4v程序并发执行特征：程序并发执行特征： 1.1.间断性间断性( (相互制约相互制约) )：程序在并发执行时，由于它们：程序在并发执行时，由于它们 共享资源或为完成同一项任务而相互合作，使在并发共享资源或为完成同一项任务而相互合作，使在并发程序之间形成了相互制约的关系。相互制约将导致并程序之间形成了相互制约的关系。相互制约将导致并发程序具有发程序具有“执行执行- -暂停暂停- -执行执行”这种间断性活动规律。这种间断性活动规律。 2.2.失去封闭性（程序和计
6、算不再一一对应）失去封闭性（程序和计算不再一一对应）：程序在：程序在并发执行时，是多个程序共享系统中的各种资源，因并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的而这些资源的状态将由多个程序来改变，致使程序的运行已失去了封闭性。运行已失去了封闭性。 3.3.结果不可再现性结果不可再现性：程序在并发执行时，由于失去了：程序在并发执行时，由于失去了封闭性，也将导致失去结果的可再现性。即程序经过封闭性，也将导致失去结果的可再现性。即程序经过多次运行，虽然其各次的环境和初始条件相同，但得多次运行，虽然其各次的环境和初始条件相同，但得到的结果却各不相同。到的结
7、果却各不相同。例例：设设有有观观察察者者和和报报告告者者并并行行工工作作。在在一一条条单单向向行行驶驶的的公公路路上上经经常常有有卡卡车车通通过过。观观察察者者不不断断观观察察并并对对通通过过的的卡卡车车计计数数。报报告告者者定定时时地地将将观观察察者者的的计计数数值值打打印印出出来来，然然后后将将计计数器重新清数器重新清“0”。observerbeginL1；observenextcar;count =count+1；gotoL1endreporterbeginL2:printcount;count =0；gotoL2end由由于于观观察察者者和和报报告告者者各各自自独独立立地地并并行行工工
8、作作，因因此此可可能出现以下三种执行序列：能出现以下三种执行序列：(1)count =count+1;printcount;count =0;(2)printcount;count =0;count =count+1;(3)printcount;count =count+1,count =0。假假设设在在开开始始某某个个循循环环之之前前，count的的值值为为n，则则在在完完成成一一个个循循环环后后，对对上上述述三三个个执执行行序序列列打打印印机机打打印印的的count值和执行后的值和执行后的count值如下表所示：值如下表所示：执行序列执行序列(1)(2)(3)打印的值打印的值n+1nn执行
9、后的值执行后的值0102.1.4 2.1.4 进程的特征与状态进程的特征与状态 由于程序在并发执行时，各次执行的结果不由于程序在并发执行时，各次执行的结果不同，所以用同，所以用“程序程序”这个概念已无法描述程序的这个概念已无法描述程序的并发执行，所以必须引入新的概念并发执行，所以必须引入新的概念 - - 进程来描进程来描述程序的并发执行。述程序的并发执行。 1961 1961年，进程的概念首先由美国麻省理工学年，进程的概念首先由美国麻省理工学院在院在MULTICSMULTICS系统中引入，得到人们的普遍重视并系统中引入，得到人们的普遍重视并广为采用。随后，许多人都对进程下过定义。广为采用。随后
10、，许多人都对进程下过定义。v 进程的定义进程的定义如：如：v进程是可以并发执行的程序在一个数据集合上的运行过程。进程是可以并发执行的程序在一个数据集合上的运行过程。v进程是程序的一次执行过程。进程是程序的一次执行过程。v进程是可参与并发执行的程序。进程是可参与并发执行的程序。v进程是一个程序及其数据在处理机上执行时所发生的活动。进程是一个程序及其数据在处理机上执行时所发生的活动。v进程是在给定初始状态和内存区域的条件下，可以并发执进程是在给定初始状态和内存区域的条件下，可以并发执 行的程序的一次执行过程。行的程序的一次执行过程。 根据根据19781978年在庐山召开的全国操作系统会议的讨论，认
11、为年在庐山召开的全国操作系统会议的讨论，认为“进程是一个具有一定独立功能的程序关于某个数据集合的一进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动次运行活动”。1.1.程序与进程之间的区别：程序与进程之间的区别：v 进程的特性进程的特性v进程是程序的执行，属于进程是程序的执行，属于动态动态，程序是静态的，程序是静态的v进程的存在是进程的存在是暂时暂时的，程序的存在是永久的。的，程序的存在是永久的。“一一次运行活动次运行活动”生命周期、诞生生命周期、诞生(建立建立)、死亡、死亡(撤消撤消)v进程实体进程实体程序数据程序数据PCB(进程控制块进程控制块)，即进程即进程是一个程序及其数
12、据在处理机上顺序地执行时所发生是一个程序及其数据在处理机上顺序地执行时所发生的活动。的活动。v一个程序可以对应多个进程一个程序可以对应多个进程v一个进程可以包含多个程序一个进程可以包含多个程序引引入入了了进进程程实实体体的的概概念念后后，我我们们可可以以把把传传统统OS中中的的进进程程定定义义为为：“进进程程是是进进程程实实体体的的运运行行过过程程，是是系系统统进进行行资资源源分分配配和和调调度度的一个独立单位的一个独立单位”。2.2.进程的特性：进程的特性：v动态性：进程是程序的一次执行过程，由创建到消亡是有动态性：进程是程序的一次执行过程，由创建到消亡是有 一定生命周期的，在生命周期内其状
13、态动态变化。一定生命周期的，在生命周期内其状态动态变化。v并发性：在内存中的多个进程能在一段时间内同时运行。并发性：在内存中的多个进程能在一段时间内同时运行。 并发性使得进程执行过程随时会被中断。并发性使得进程执行过程随时会被中断。v独立性：进程是一个能够独立运行的基本单位，即只有进独立性：进程是一个能够独立运行的基本单位，即只有进 程才能被独立调度运行及独立获得资源。程才能被独立调度运行及独立获得资源。v异步性：这是指进程以各自独立的、不可预知的速度向前异步性：这是指进程以各自独立的、不可预知的速度向前 推进。正是这一特征，将导致程序执行的不可再推进。正是这一特征，将导致程序执行的不可再 现
14、性，现性，OSOS需要系统采取必要的措施，以保证各个需要系统采取必要的措施，以保证各个 进程的程序之间能协调运行。进程的程序之间能协调运行。v交往性：多个进程之间可能会发生直接或间接的相互作用。交往性：多个进程之间可能会发生直接或间接的相互作用。3. 3. 进程的状态及其转换进程的状态及其转换1. 1. 进程的三个基本状态进程的三个基本状态n运行状态（运行状态（RunningRunning）：当一个进程在处理机上运行：当一个进程在处理机上运行时，则称该进程处于运行状态。时，则称该进程处于运行状态。n就绪状态（就绪状态（ReadyReady）：一个进程获得了除处理机外的：一个进程获得了除处理机外
15、的一切所需资源，一旦得到处理机即可运行，则称此一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。进程处于就绪状态。n阻塞状态（阻塞状态（WaitingWaiting）：（又称等待状态、封锁状态）：（又称等待状态、封锁状态）：一个进程正在等待某一事件发生（例如请求：一个进程正在等待某一事件发生（例如请求I IO O而等待而等待I IO O完成等）而暂时停止运行，这时即使把完成等）而暂时停止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻处理机分配给进程也无法运行，故称该进程处于阻塞状态。塞状态。进程的状态转换图进程的状态转换图运行运行被抢占被抢占时间片用完时间片用完就绪就
16、绪阻塞阻塞 某等待事件完成某等待事件完成进程调度进程调度某等待事件发生某等待事件发生( (如如I/O请求、请求、P操作等）操作等）( (如如I/O 完成、完成、 V操作等）操作等） 三个基本状态之间可能转换和转换原因如下：三个基本状态之间可能转换和转换原因如下：n就绪态就绪态运行态：进程调度程序按某种算法将处于运行态：进程调度程序按某种算法将处于就绪队列的某个进程选出，把就绪队列的某个进程选出，把CPUCPU分配给它，该进程便分配给它，该进程便由就绪状态转变为运行状态。由就绪状态转变为运行状态。 n运行态运行态就绪态：处于运行状态的进程因时间片用就绪态：处于运行状态的进程因时间片用完而被中断，
17、将该进程的完而被中断，将该进程的PCBPCB表插入就绪队列，该进程表插入就绪队列，该进程便由运行状态转变为就绪状态。如果在采用抢占式调度便由运行状态转变为就绪状态。如果在采用抢占式调度策略的系统中，进入就绪队列的进程的优先级高于正处策略的系统中，进入就绪队列的进程的优先级高于正处在运行状态的进程，可抢占在运行状态的进程，可抢占CPUCPU，将执行状态进程的，将执行状态进程的PCBPCB表插入就绪队列，由运行状态转变为就绪状态。表插入就绪队列，由运行状态转变为就绪状态。 n运行态运行态阻塞态：进程在某等待事件发生（例阻塞态：进程在某等待事件发生（例如如I/OI/O请求、原语请求、原语P P操作等
18、）而无法执行时，会由运操作等）而无法执行时，会由运行状态转变为阻塞状态，在等待该事件的完成过程行状态转变为阻塞状态，在等待该事件的完成过程中将放弃中将放弃CPUCPU的使用权。的使用权。n阻塞态阻塞态就绪态：进程在某等待事件完成，被就绪态：进程在某等待事件完成，被阻塞的原因解除（例如阻塞的原因解除（例如I/OI/O完成、原语完成、原语V V操作等）时，操作等）时，将阻塞状态进程的将阻塞状态进程的PCBPCB表插入就绪队列，由阻塞状态表插入就绪队列，由阻塞状态转变为就绪状态，重新获得被调度的权力。转变为就绪状态，重新获得被调度的权力。 进程运行期间会不断地从一个状态转变为另一进程运行期间会不断地
19、从一个状态转变为另一个状态，它可以多次处于上述三个基本状态中。当个状态，它可以多次处于上述三个基本状态中。当一个进程完成，或者在执行过程中出现意外情况而一个进程完成，或者在执行过程中出现意外情况而异常结束时，进程被撤消，生命期结束。异常结束时，进程被撤消，生命期结束。引入挂起状态的原因：引入挂起状态的原因：（1）终端用户的请求。）终端用户的请求。（2）父进程请求。父进程请求。（3）负荷调节的需要。）负荷调节的需要。（4）操作系统的需要。）操作系统的需要。2.2.进程的挂起（静止）与非挂起（活动）状态进程的挂起（静止）与非挂起（活动）状态 v挂起（挂起（Suspend）：把一个进程从内存转到外存
20、。：把一个进程从内存转到外存。u进程挂起可能有以下几种情况：进程挂起可能有以下几种情况：l阻塞阻塞阻塞挂起：没有进程处于就绪状态或就绪阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时，发生这种转换，以提进程要求更多内存资源时，发生这种转换，以提交新进程或运行就绪进程交新进程或运行就绪进程;l就绪就绪就绪挂起：当有高优先级阻塞（系统认为就绪挂起：当有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程时，系会很快就绪的）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程统会选择挂起低优先级就绪进程;l运行运行就绪挂起：对抢占式系统，当有高优先级就绪挂起：对抢占式系统，当有高
21、优先级阻塞挂起进程因事件出现而进入就绪挂起时，系阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态统可能会把运行进程转到就绪挂起状态u激活（激活（Activate）：）：把一个进程从外存转到内存；把一个进程从外存转到内存；可能有以下几种情况：可能有以下几种情况：l就绪挂起就绪挂起就绪：没有就绪进程或挂起就绪进程就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，发生转换优先级高于就绪进程时，发生转换;l阻塞挂起阻塞挂起阻塞：当一个进程释放足够内存时，阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很系统会把一个高优先级阻塞挂起（系统认为会很快
22、出现所等待的事件）进程激活快出现所等待的事件）进程激活.具有静止状态和活动状态的进程状态变迁图具有静止状态和活动状态的进程状态变迁图活动就绪活动就绪激激活活静止就绪静止就绪挂挂起起解解 封封活动阻塞活动阻塞激激活活静止阻塞静止阻塞挂挂起起解解 封封执行执行被抢占被抢占时钟中断时钟中断某等待事件发生某等待事件发生进程调度进程调度挂起挂起3.3.创建状态和终止状态创建状态和终止状态不少系统增加了两个基本状态：不少系统增加了两个基本状态：1 1. .创建（新）状态创建（新）状态：一个进程刚刚建立（已拥有了自己一个进程刚刚建立（已拥有了自己的的PCBPCB），还未送入主存中就绪队列。），还未送入主存中
23、就绪队列。2.2.终止状态终止状态：一个进程已正常结束或异常结束，以后不一个进程已正常结束或异常结束，以后不能再执行，但在操作系统中依然保留一个记录，其中保能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据，供其它进程收集。存状态码和一些计时统计数据，供其它进程收集。NewReadyRunningExitBlockedAdmitEventOccursDispatchReleaseTime-outEventWait五状态进程模型五状态进程模型活动就绪活动就绪激激活活静止就绪静止就绪挂挂起起解解 封封活动阻塞活动阻塞激激活活静止阻塞静止阻塞挂挂起起解解 封封执行执行被抢占被
24、抢占时钟中断时钟中断某等待事件发生某等待事件发生进程调度进程调度挂起挂起创建创建终止终止许可许可释放释放具有创建、终止和挂起状态的进程状态变迁图具有创建、终止和挂起状态的进程状态变迁图2.1.5 2.1.5 进程控制块（进程控制块（Process Control BlockProcess Control Block）为了描述一个进程和其它进程以及系统资源的为了描述一个进程和其它进程以及系统资源的关系；为了刻画一个进程在各个不同时期所处的状关系；为了刻画一个进程在各个不同时期所处的状态，人们定义了一个与进程相联系的数据结构，称态，人们定义了一个与进程相联系的数据结构，称为为进程控制块（进程控制块
25、（PCB）。PCB：是用以记录进程的有关信息的一块主存，它是用以记录进程的有关信息的一块主存，它是由系统为每个进程分别建立的。是由系统为每个进程分别建立的。当系统创建一个进程时，必须为它设置一个当系统创建一个进程时，必须为它设置一个PCB，然后根据然后根据PCB的信息对进程实施控制管理，的信息对进程实施控制管理，进程任务完成时，系统收回它的进程任务完成时，系统收回它的PCB，进程也随之进程也随之消亡。消亡。1.PCB1.PCB的内容的内容 PCB内容内容可分为调度信息和现场信息两部分，可分为调度信息和现场信息两部分，通常结通常结构如下：构如下：(对不同对不同OS所使用的所使用的PCB结构也不同
26、结构也不同)PCB-ADDRNAMESTATUSNEXTALL-Q-NEXTSTART-ADDRPRIORITYCPUSTATUSCommunication-informationPROCESS-familyOWN-resource对对于于简简单单系系统统，PCB结结构构较较小小；而而在在一一些些较较复复杂杂的的系系统统中中，PCB所所含含的的内内容容就就比比较较多多，比比如如，还还可可能能有有 I/O、 文文 件件传传输输、控控制制信信息。息。PCB结构结构(1)进进程程标标识识符符NAME：每每个个进进程程都都必必须须有有唯唯一一的的标标识识符符，可可以以用用字字符符或或编编号号表表示示。
27、在在创创建建一一个个进进程时，由创建者给出进程的标识符。程时，由创建者给出进程的标识符。(2)进进程程当当前前状状态态status：说说明明本本进进程程目目前前处处于于何何种种状状态态(运运行行、就就绪绪、等等待待)，作作为为进进程程调调度度时时分分配配处处理理机机的的主主要要依依据据。(只只有有当当进进程程处处于于就就绪绪状状态态时，才有可能获得处理机时，才有可能获得处理机)(3)当当前前队队列列指指针针NEXT：该该项项登登记记了了处处于于同同一一状状态态下下的的下下一一个个PCB的的地地址址，以以此此将将处处于于同同一一状状态态的的所所有有进进程程勾勾链链起起来来。而而头头指指针针为为队
28、队列列第第一一元元素素的的地地址址，由由OS掌握。掌握。PCB1PCB2PCBnReady-Q-Start就绪头指针就绪头指针(4)ALL-Q-NEXT总链指针总链指针：所有进程的总链，进程：所有进程的总链，进程PCB中的该项内容是指向总链中的下一个中的该项内容是指向总链中的下一个PCB地址。地址。当建立新进程时，查询是否重名时方便。当建立新进程时，查询是否重名时方便。(5)程序开始地址程序开始地址START-ADDR:该进程的程序将从此地该进程的程序将从此地址开始执行。址开始执行。(6)进程优先级进程优先级PRIORIYT：反映了进程要求：反映了进程要求CPU的紧迫的紧迫程度，它通常由用户预
29、先提出或由系统指定。进程将程度，它通常由用户预先提出或由系统指定。进程将以其优先级的高低去争夺以其优先级的高低去争夺CPU的权利。的权利。(7)CPU现场保护区现场保护区CPUSTATUS：当进程由于某种原因当进程由于某种原因释放处理机后，释放处理机后，CPU现场信息被保存在现场信息被保存在PCB的该区域的该区域中，以便在该进程重新获得处理机后，继续执行，通中，以便在该进程重新获得处理机后，继续执行，通常被保护的信息有：常被保护的信息有：通用通用寄存器，指令计数器寄存器，指令计数器，PSW，用户栈指针。，用户栈指针。(8)通信信息：通信信息：Communication-information:
30、每个进程每个进程在运行过程中与别的进程进行通信时所记录的有关在运行过程中与别的进程进行通信时所记录的有关信息。信息。(9)家庭联系家庭联系PROCESS-FAMILY:有的系统允许一个有的系统允许一个进程创建自己的子进程，这样，会组成一个进程进程创建自己的子进程，这样，会组成一个进程家庭家庭(如它的子进程和父进程的标识符如它的子进程和父进程的标识符)。(10)占有资源清单占有资源清单OWN-resource2.2.进程的组成进程的组成从结构上讲，每个进程都由程序、数据和从结构上讲，每个进程都由程序、数据和一个进程控制块一个进程控制块PCB组成。组成。即即进程程序数据进程程序数据PCB进程的程序
31、部分描述了进程所要完成的功能，进程的程序部分描述了进程所要完成的功能，数据集合是程序在执行时所需要的数据和工作区，数据集合是程序在执行时所需要的数据和工作区，这两部分是进程存在的物质基础，而这两部分是进程存在的物质基础，而PCB是进程是进程存在的唯一标志。存在的唯一标志。 为了便于管理，系统把所有为了便于管理，系统把所有PCBPCB用适当的方式组用适当的方式组织在一起，大致有以下三种组织方式，目前常用后织在一起，大致有以下三种组织方式，目前常用后两种：两种： 3.PCB3.PCB组织方式组织方式（1）线线性性方方式式：把把所所有有不不同同状状态态的的进进程程的的PCB组组织织在在一一个个表表格
32、格中中，这这种种方方法法最最为为简简单单，适适用用于于系系统统中中进进程程数数目目不不多多的的类类型型，其其缺缺点点是是：调调度度进进程程时时，往往往往需需查查找找整个整个PCB表。表。（2）链链接接方方式式：用用PCB表表中中的的队队列列指指针针项项将将具具有有相相同同状状态态的的进进程程的的PCB表表链链接接起起来来，这这样样PCB表表就就形形成成就就绪绪队队列列、空空闲闲队队列列及及阻阻塞塞队队列列等等。其其中中，空空闲闲队队列列是是一一个个，而而就就绪绪队队列列与与阻阻塞塞队队列列可可以以是是多多个个。例例如如，可可以以将将不不同同优优先先级级的的进进程程的的PCB表表排排在在不不同同
33、的的就就绪绪队队列列中中，也也可可以以将将阻阻塞塞原原因因不不同同的的进进程程的的PCB表表排排在在不不同同的的阻阻塞塞队队列列中中。系系统统中中的的某某些些固固定定单单元元分分别别指指向向各各队队列列队队首首地地址址及及执执行行状状态态进进程程的的PCB表表的首地址。的首地址。（3）索索引引方方式式：对对相相同同状状态态的的进进程程，分分别别设设置置各各自自的的PCB索索引引表表，表表目目为为PCB在在PCB表表（线线性性表表）中中的的地地址址。于于是是分分别别有有就就绪绪索索引引表表、等等待待索索引引表表。内内存存中的一些固定单元分别指出各表的起始地址。中的一些固定单元分别指出各表的起始地
34、址。2.2 2.2 进程控制进程控制 进程控制是操作系统内核中的组成部分。在操作系进程控制是操作系统内核中的组成部分。在操作系统中有两类进程：统中有两类进程：系统进程系统进程和和用户进程用户进程。由进程控制对。由进程控制对系统中所有进程实施有效地管理。进程控制主要完成创系统中所有进程实施有效地管理。进程控制主要完成创建进程、撤消进程以及实现进程状态之间的转换等工作。建进程、撤消进程以及实现进程状态之间的转换等工作。 进程控制通过进程控制通过“原语原语”来实现。来实现。 所所谓谓原原语语，是是指指由由若若干干条条机机器器指指令令组组成成的的并并用用以以完完成成特特定定功功能能的的一一个个过过程程
35、，这这段段程程序序在在执执行行期期间间是是不不可可分分割的。它必须在割的。它必须在管态管态下执行，且下执行，且常驻内存常驻内存。 不同的操作系统中，使用的进程控制原语是不完不同的操作系统中，使用的进程控制原语是不完全相同的，下面介绍几种常用的进程控制原语。全相同的，下面介绍几种常用的进程控制原语。1 1进程创建进程创建 创建原语的功能是为一个进程（父进程）创建一创建原语的功能是为一个进程（父进程）创建一个新进程（子进程）。引起创建的事件如下：个新进程（子进程）。引起创建的事件如下：用户登录用户登录：当终端用户登录时，由终端子进程创建用户：当终端用户登录时，由终端子进程创建用户 进程；进程；作业
36、调度作业调度：批处理系统中，作业调度程序为选出的作业：批处理系统中，作业调度程序为选出的作业 创建进程；创建进程；提供服务提供服务：系统为合法用户建立服务进程；：系统为合法用户建立服务进程；应用请求应用请求：进程运行时可以创建子进程来协同完成任务。进程运行时可以创建子进程来协同完成任务。进程家族树进程家族树HIDJKEFGBCAL创建原语实现过程创建原语实现过程在在PCB表区索取一张空表表区索取一张空表申请内存；调入程序和数据；申请内存；调入程序和数据；分配其它必要资源分配其它必要资源初始化初始化 PCB表表将将PCB表插入就绪队列表插入就绪队列返回返回2 2进程终止进程终止进程终止的典型事件
37、如下：进程终止的典型事件如下：进程完成任务，正常结束（进程完成任务，正常结束（Holt,Logs offHolt,Logs off指令）；指令）；进程运行出现故障及错误时，被迫终止运行（越界进程运行出现故障及错误时，被迫终止运行（越界错，保护错，非法指令，特权指令错，运行超时，等错，保护错，非法指令，特权指令错，运行超时，等待超时，算术运算错，待超时，算术运算错，I/OI/O故障等）；故障等）；进程运行时因外界干预而撤消，如系统发生死锁时进程运行时因外界干预而撤消，如系统发生死锁时需要撤消一些进程、父进程撤消子进程等。需要撤消一些进程、父进程撤消子进程等。撤消原语实现过程撤消原语实现过程找出要
38、终止进程的找出要终止进程的PCBPCB撤消该进程的子孙进程撤消该进程的子孙进程释放资源释放资源将将PCB移出所在队列移出所在队列若处运行状态，终止执行，并置调度标志为真若处运行状态，终止执行，并置调度标志为真3 3进程阻塞（进程阻塞（blockblock） 阻塞原语完成进程从执行状态到阻塞状态的转变，阻塞原语完成进程从执行状态到阻塞状态的转变，这时处于执行状态的进程自身被阻塞。阻塞原语能够暂这时处于执行状态的进程自身被阻塞。阻塞原语能够暂时剥夺执行进程使用时剥夺执行进程使用CPUCPU的权力，将其置为阻塞状态并的权力，将其置为阻塞状态并插入阻塞队列。引起阻塞的典型事件如下：插入阻塞队列。引起阻
39、塞的典型事件如下： 进程请求进程请求I/OI/O服务，无论获得服务，无论获得I/OI/O服务与否，通常都要服务与否，通常都要 暂时放弃暂时放弃CPUCPU；某些原语操作，如某些原语操作，如P P操作等可能引起进程阻塞；操作等可能引起进程阻塞；某些系统进程工作时占用某些系统进程工作时占用CPUCPU，无事可做时，则调用阻，无事可做时，则调用阻 塞原语将自己阻塞。塞原语将自己阻塞。阻塞原语实现过程阻塞原语实现过程找出执行进程的找出执行进程的PCB中断中断CPU ，暂停执行，暂停执行, ,保存保存 CPU现场现场将执行进程置为阻塞状态将执行进程置为阻塞状态将将 PCB插入该事件阻塞队列插入该事件阻塞
40、队列4 4进程唤醒进程唤醒(wakeup)(wakeup) 唤醒原语将进程从阻塞状态转变为就绪状态。它将唤醒原语将进程从阻塞状态转变为就绪状态。它将唤醒进程的唤醒进程的PCBPCB从阻塞队列移出，置为就绪状态，插入就从阻塞队列移出，置为就绪状态，插入就绪队列，准备接受进程调度程序的下一次调度。唤醒进绪队列，准备接受进程调度程序的下一次调度。唤醒进程的典型事件如下：程的典型事件如下： 进程请求的进程请求的I/OI/O操作完成；操作完成；某些原语操作，如某些原语操作，如V V操作等可以解封阻塞进程；操作等可以解封阻塞进程；某些系统进程有事可做时，用唤醒原语将其唤醒。某些系统进程有事可做时，用唤醒原
41、语将其唤醒。唤醒原语实现过程唤醒原语实现过程找出唤醒进程的找出唤醒进程的 PCB将将PCB插入就绪队列插入就绪队列将进程将进程PCB中状态置为就绪中状态置为就绪将将PCB从阻塞队列移出从阻塞队列移出5进程挂起（进程挂起（suspend）6进程激活（进程激活（active）1.1.在进程状态转换时，下列（在进程状态转换时，下列（ ）转换是不可能发生的。）转换是不可能发生的。 A.A.就绪态就绪态运行态运行态 B.B.运行态运行态就绪态就绪态 C.C.运行态运行态阻塞态阻塞态 D.D.阻塞态阻塞态运行态运行态2.2.多道程序系统进程从执行状态转换到就绪状态的原因多道程序系统进程从执行状态转换到就绪
42、状态的原因 是是( )( )。 A.A.时间片完时间片完 B.B.等待其它进程的执行结果等待其它进程的执行结果 C.C.等待等待I/O D.I/O D.有更高优先级的进程到有更高优先级的进程到来来3.3.一个进程释放一种资源将有可能导致一个或几个进程一个进程释放一种资源将有可能导致一个或几个进程 （ ）。）。 A.A.由就绪变运行由就绪变运行 B.B.由运行变就绪由运行变就绪 C.C.由阻塞变运行由阻塞变运行 D.D.由阻塞变就绪由阻塞变就绪D DA,DA,DD D5.5.下列各项工作步骤下列各项工作步骤,( ,( ）是创建进程所必须的步骤。）是创建进程所必须的步骤。A.A.建立一个建立一个P
43、CBPCBB.B.由由CPUCPU调度程序为进程调度调度程序为进程调度CPUCPUC.C.为进程分配内存等必要资源为进程分配内存等必要资源D.D.将将PCBPCB接入进程就绪队列接入进程就绪队列 6. 6.关于进程的正确说法是（关于进程的正确说法是（ ）。）。 A.A.进程就是程序，或者说，进程是程序的另一种叫法。进程就是程序，或者说，进程是程序的另一种叫法。 B.B.一个被创建了的进程，在它被消灭之前，大多数时刻一个被创建了的进程，在它被消灭之前，大多数时刻 处于进程的三种基本状态之一。处于进程的三种基本状态之一。 C.C.多个不同的进程可以包含相同的程序。多个不同的进程可以包含相同的程序。
44、 D.D.一个处于等待队列中的进程，即使进入其它状态，仍一个处于等待队列中的进程，即使进入其它状态，仍 然放在等待队列中。然放在等待队列中。 4.4.为使进程由活动就绪变为静止就绪，应利用（为使进程由活动就绪变为静止就绪，应利用（ ） 原语？原语？A.SUSPEND B. ACTIVE C. BLOCK D. WAKEUPA.SUSPEND B. ACTIVE C. BLOCK D. WAKEUPA AACDACD BC BC2.3.1 2.3.1 进程同步的基本概念进程同步的基本概念2.3 2.3 进程同步进程同步 在多道程序环境下，系统中各进程以不可预测的在多道程序环境下，系统中各进程以不
45、可预测的速度向前推进，进程的异步性会造成了结果的不可再速度向前推进，进程的异步性会造成了结果的不可再现性。为防止这种现象，异步的进程间推进受到二种现性。为防止这种现象，异步的进程间推进受到二种限制：限制：q 间接相互制约关系（资源共享关系间接相互制约关系（资源共享关系/ /竞争关系）竞争关系） 多个进程因为使用共享资源而产生竞争关系，在抢多个进程因为使用共享资源而产生竞争关系，在抢占使用资源时可能导致使用失败，都达不到目的，因而占使用资源时可能导致使用失败，都达不到目的，因而要有信息交换以保证各得其所。例如，多个进程共同使要有信息交换以保证各得其所。例如，多个进程共同使用一台打印机，当一个进程
46、打印时，其它进程不能使用，用一台打印机，当一个进程打印时，其它进程不能使用，否则打印内容会混在一起。在这种情况下，就要求当前否则打印内容会混在一起。在这种情况下，就要求当前正在使用打印机的进程与其它要求打印的进程之间交换正在使用打印机的进程与其它要求打印的进程之间交换信息，才能协调对打印机的使用。信息，才能协调对打印机的使用。q直接相互制约关系（直接相互制约关系（相互合作关系）相互合作关系） 一组进程协同完成一个任务，它们之间是合一组进程协同完成一个任务，它们之间是合作关系。这种情况需要对于相互合作的多个进程作关系。这种情况需要对于相互合作的多个进程的执行次序进行协调，这样就必须交换信息，以的
47、执行次序进行协调，这样就必须交换信息，以免出现免出现时间上的差错时间上的差错。例如，一个计算进程和一。例如，一个计算进程和一个打印进程共同完成一个任务。若打印进程要打个打印进程共同完成一个任务。若打印进程要打印时，而计算进程尚未计算出结果，打印进程就印时，而计算进程尚未计算出结果，打印进程就无法打印，但是这种要求会传达给计算进程。当无法打印，但是这种要求会传达给计算进程。当计算进程计算出结果时，通知打印进程，则打印计算进程计算出结果时，通知打印进程，则打印进程就可以工作了。这种进程就可以工作了。这种“传达传达”与与“通知通知”就就是在交换信息。是在交换信息。1.1.进程的同步进程的同步 指系统
48、中多个进程中发生的事件存在某种时序关系，指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。醒进入就绪态。正常行车正常行车开开 车车到站停车到站停车售票售票开车门开车门关车门关车门司机司机售票员售票员司机和售票员的同步司机和售票员的同步2.2.进程的互斥进程的互斥 当某一进程访问某一资源时，不允许别的进
49、程同时访当某一进程访问某一资源时，不允许别的进程同时访问，这种限制称为互斥，即多个进程在访问某些资源（如问，这种限制称为互斥，即多个进程在访问某些资源（如临界资源）时，也要有一种执行次序上的协调，当一个进临界资源）时，也要有一种执行次序上的协调，当一个进程访问完毕，另一个进程才能访问。程访问完毕，另一个进程才能访问。所以就其本质来讲，所以就其本质来讲，互斥仍是一种同步互斥仍是一种同步。进程进程A 请求资源请求资源R 释放资源释放资源R进程进程B 请求资源请求资源R 释放资源释放资源RR使用使用R（阻塞）（阻塞）唤醒唤醒分配分配拒绝拒绝资源互斥使用资源互斥使用n临界资源临界资源 像打印机这类一次
50、只允许一个进程使用的资源称为像打印机这类一次只允许一个进程使用的资源称为临界资源。属于临界资源有硬件打印机等，软件有变量、临界资源。属于临界资源有硬件打印机等，软件有变量、数组、缓冲区等。当然还有一类象磁盘等资源，它允许数组、缓冲区等。当然还有一类象磁盘等资源，它允许进程间共享，即可交替使用，所以它称为共享资源，而进程间共享，即可交替使用，所以它称为共享资源，而临界资源又称临界资源又称独享资源独享资源。n临界区临界区 多个进程共享临界资源时必须互斥使用，例如多个进程共享临界资源时必须互斥使用，例如A A和和B B两个进程都需要使用打印机，它们必须互斥使用。如果两个进程都需要使用打印机，它们必须
51、互斥使用。如果为了保证结果的正确性限制为了保证结果的正确性限制A A、B B二进程推进序列。规定二进程推进序列。规定进程进程A A执行完再执行进程执行完再执行进程B B，这样的限制就显得过于死板，这样的限制就显得过于死板，因为它已不能保证进程因为它已不能保证进程A A、B B能并发执行，所以必须把限能并发执行，所以必须把限制减少到最少，以尽可能支持并发执行。为此把各进程制减少到最少，以尽可能支持并发执行。为此把各进程分解，把分解，把访问临界资源的那段代码访问临界资源的那段代码（称为临界区）与其（称为临界区）与其它段代码分割开来，只对各种进程进入自己的临界区加它段代码分割开来，只对各种进程进入自
52、己的临界区加以限制，即各进程互斥地进入自己的临界区。以限制，即各进程互斥地进入自己的临界区。 observerbeginL1；observenextcar;count =count+1；gotoL1endreporterbeginL2:printcount;count =0；gotoL2end执行速度的不同，导致结果不唯一。执行速度的不同，导致结果不唯一。 进程在并发执行时为了保证结果的可再现性，各进程在并发执行时为了保证结果的可再现性，各进程执行序列必须加以限制以保证互斥地使用临界资进程执行序列必须加以限制以保证互斥地使用临界资源，相互合作完成任务。源，相互合作完成任务。使用临界区的原则使用
53、临界区的原则有空让进：当无进程在临界区时，有空让进：当无进程在临界区时，相应的临界资源处于空相应的临界资源处于空 闲状态，因而允许一个请求进入临界区的进程闲状态，因而允许一个请求进入临界区的进程 立即进入自己的临界区；立即进入自己的临界区；无空等待：无空等待：当已有进程进入自己的临界区时，即相应的临当已有进程进入自己的临界区时，即相应的临 界资源正被访问，因而其它试图进入临界区的进界资源正被访问，因而其它试图进入临界区的进 程必须等待，以保证进程互斥地访问临界资源程必须等待，以保证进程互斥地访问临界资源；有限等待：任一进程进入临界区的要求应在有限的时间内有限等待：任一进程进入临界区的要求应在有
54、限的时间内得到满足；得到满足；让权等待：处于等待状态的进程应放弃占用让权等待：处于等待状态的进程应放弃占用CPU，以使其他，以使其他进程有机会得到进程有机会得到CPU的使用权。的使用权。多中择一：当没有进程在临界区，而同时有多个进程要求多中择一：当没有进程在临界区，而同时有多个进程要求进入自己的临界区，只能让其中之一进入临界进入自己的临界区，只能让其中之一进入临界区，其他进程必须等待；区，其他进程必须等待；3.3.同步机制同步机制 用于保证多个进程在执行次序上的协调关系的相应机用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。制称为进程同步机制。 v一个访问临界资源的进程采用进
55、程同步机制后描述如下：一个访问临界资源的进程采用进程同步机制后描述如下： begin remainder section 1begin remainder section 1； 剩余区剩余区1 1进入区（进入区（entrysection）critical section critical section ； 临界区临界区退出区（退出区（exitsection） remainder section 2 remainder section 2 ； 剩余区剩余区2 2 end end 进程同步机制在临界区前加上进程同步机制在临界区前加上进入区进入区，它负责对欲访，它负责对欲访问的临界资源状态进行检查
56、，以决定是允许该进程进入临问的临界资源状态进行检查，以决定是允许该进程进入临界区还是等待。同时在临界区后加上界区还是等待。同时在临界区后加上退出区退出区，它负责释放，它负责释放临界资源以便其它等待该临界资源的进程使用。临界资源以便其它等待该临界资源的进程使用。v解决进程互斥的同步机制有软件方法、硬件方法、信号量解决进程互斥的同步机制有软件方法、硬件方法、信号量机制和管程等。机制和管程等。（1 1）软件方法解决进程互斥）软件方法解决进程互斥问题：有问题：有二个进程二个进程PiPi和和PjPj互斥共享互斥共享临界资源临界资源R,R,可用下述可用下述 结构作一般性描述：结构作一般性描述： begin
57、begin cobegin cobegin Pi: . Pi: .Pj: .Pj: .coendcoend end end算法算法1n该算法设置了一个公用整型变量该算法设置了一个公用整型变量turn，用于指示被允，用于指示被允许进入临界区的进程编号，既若许进入临界区的进程编号，既若turn=i，表示允许，表示允许Pi进进程进入临界区。该算法可确保每次只允许一个进入临程进入临界区。该算法可确保每次只允许一个进入临界区。但采用强制两个进程轮流进入临界区，很容易界区。但采用强制两个进程轮流进入临界区，很容易造成资源利用不充分，在造成资源利用不充分，在Pi出让临界区之后，出让临界区之后，Pj使用使用临
58、界区之前，临界区之前，Pi不可能再次使用临界区。不可能再次使用临界区。 PiPi进程进程: Pj: Pj进程进程: : repeat repeat repeat repeat while turni do no-op while turnj do no-op while turni do no-op while turnj do no-op critical section critical section critical section critical section turn=j turn=i turn=j turn=i remainder section remainder sect
59、ion remainder section remainder section until false until false until false until false算法算法2n算法基本思想：在每一个进程访问临界区资源之前，先算法基本思想：在每一个进程访问临界区资源之前，先查看一下临界资源是否正被访问，若正被访问，该进程查看一下临界资源是否正被访问，若正被访问，该进程需等待，否则才进入自己的临界区。为此设置了一个数需等待，否则才进入自己的临界区。为此设置了一个数组组flagn，如第，如第i个元素值为个元素值为false表示表示Pi进程未进入临界进程未进入临界区，值为区，值为true表示
60、表示Pi进程进入临界区。进程进入临界区。PiPi进程进程: Pj: Pj进程进程: :repeat repeat repeatrepeat while flagj do no_op; while flagi do while flagj do no_op; while flagi do no_op;no_op; flagi:=true; flagj:=true; flagi:=true; flagj:=true; critical_section; critical_section; critical_section;critical_section; flagi:=false; flagj:
61、=false; flagi:=false; flagj:=false; remainder section; remainder section; remainder section; remainder section;until false until falseuntil false until false算法算法3算法算法2 2是先检测对方进程状态标志后再置自己标志，会造是先检测对方进程状态标志后再置自己标志，会造成二个进程在分别检测后同时进入临界区。为此算法成二个进程在分别检测后同时进入临界区。为此算法3 3采采用先设置自己标志后再检测对方状态标志，它的程序如下，用先设置自己标志后再
62、检测对方状态标志，它的程序如下，但也可能出现二个进程先后同时设置后再分别检测对方状但也可能出现二个进程先后同时设置后再分别检测对方状态标志，造成对方都不能进入临界区，无限期等待。态标志，造成对方都不能进入临界区，无限期等待。 PiPi进程进程: Pj: Pj进程进程: : repeat repeat repeat repeat flagi:=true; flagj:=true; flagi:=true; flagj:=true; while flagj do no_op; while flagi do no_op; while flagj do no_op; while flagi do no
63、_op; critical_section; critical_section; critical_section; critical_section; flagi:=false; flagj:=false; flagi:=false; flagj:=false; remainder section; remainder section; remainder section; remainder section; until false until false until false until false算法算法4(Peterson 1981)4(Peterson 1981)该算法组合了算法
64、该算法组合了算法1 1和算法和算法3 3的关键，当的关键，当flagi=trueflagi=true时时表示表示PiPi要求进入临界区或正在临界区。又设置变量要求进入临界区或正在临界区。又设置变量turnturn，指示允许进入临界区的进程编号。这样可以保证当二，指示允许进入临界区的进程编号。这样可以保证当二个进程同时要求进入临界区时，只允许一个进程进入临个进程同时要求进入临界区时，只允许一个进程进入临界区。界区。 PiPi进程进程: Pj: Pj进程进程: :repeatrepeat flagi:=true;turn:=j; flagi:=true;turn:=j; while(flagjan
65、d turn=j) while(flagjand turn=j) do no_op; do no_op; critical_section; critical_section; flagi:=false; flagi:=false; remainder section; remainder section;until falseuntil false repeatrepeat flagj:=true;turn:=i; flagj:=true;turn:=i; while(flagiand turn=i) while(flagiand turn=i) do no_op; do no_op; cr
66、itical_section; critical_section; flagj:=false; flagj:=false; remainder section; remainder section;until false until false （2 2）硬件方法解决进程互斥）硬件方法解决进程互斥完全利用软件方法，有很大局限性（如完全利用软件方法，有很大局限性（如不适于多进程），现在已很少采用。不适于多进程），现在已很少采用。可以利用某些硬件指令可以利用某些硬件指令机器指令，机器指令，用于保证两个动作的原子性，如在一个取指用于保证两个动作的原子性，如在一个取指令周期中对一个存储器单元的读和写或
67、者读令周期中对一个存储器单元的读和写或者读和测试。由于这些动作在一个指令周期中执和测试。由于这些动作在一个指令周期中执行，他们不会受到其他指令的干扰。行，他们不会受到其他指令的干扰。n利用利用TS实现进程互斥：每个实现进程互斥：每个临界资源设置一个公共布尔临界资源设置一个公共布尔变量变量lock，初值为，初值为FALSEn在进入区利用在进入区利用TS进行检查：进行检查：有进程在临界区时，重复检有进程在临界区时，重复检查；直到其它进程退出时，查；直到其它进程退出时，检查通过；检查通过；Test-and-Set(TS)指令指令boolean TS(boolean lock)boolean TS(b
68、oolean lock) boolean old; boolean old; old = lock; old = lock; lock = TRUE; lock = TRUE; return old; return old; 该指令读出标志后设置为该指令读出标志后设置为TRUETRUElocklock表示资源的两种状态：表示资源的两种状态：TRUETRUE表示正被占用，表示正被占用，FALSEFALSE表示空闲表示空闲互斥算法互斥算法 while TS(lock) do no-op while TS(lock) do no-op； lock = FALSE lock = FALSE； crit
69、ical section critical section； remainder section remainder section； Swap指令（或指令（或Exchange指令）指令）void SWAP(boolean a, boolean b) void SWAP(boolean a, boolean b) boolean temp; boolean temp; temp = a; a = b; b = temp; temp = a; a = b; b = temp; 互斥算法互斥算法n利用利用Swap实现进程互斥：实现进程互斥：每个临界资源设置一个公每个临界资源设置一个公共布尔变量共布
70、尔变量lock，初值为，初值为FALSE。每个进程设置一。每个进程设置一个局部布尔变量个局部布尔变量key，为，为FALSE时进程可进入临界时进程可进入临界区。区。 key = TRUE; key = TRUE; do do SWAP(lock, key); SWAP(lock, key); while (key); while (key);lock = FALSE;lock = FALSE;critical sectioncritical section remainder section remainder section n硬件方法的优点硬件方法的优点适用于任意数目的进程，在单处理器或多
71、处理器上适用于任意数目的进程，在单处理器或多处理器上简单，容易验证其正确性简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量区设立一个布尔变量n硬件方法的缺点硬件方法的缺点当有进程在临界区内时，其他想进入临界区的进程当有进程在临界区内时，其他想进入临界区的进程必须不断地进行测试，处于一种忙等待状态，要耗必须不断地进行测试，处于一种忙等待状态，要耗费费CPU时间，不能实现时间，不能实现“让权等待让权等待”可能可能饥饿饥饿：从等待进程中随机选择一个进入临界：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上区，有
72、的进程可能一直选不上1.1.在下面的叙述中，正确的是（在下面的叙述中，正确的是（ ）。）。A.A.临界资源是非共享资源临界资源是非共享资源 B.B.临界资源是任意共享资源临界资源是任意共享资源C.C.临界资源是互斥共享资源临界资源是互斥共享资源 D.D.临界资源是同时共享资源临界资源是同时共享资源3.3.并发进程之间（并发进程之间（ ）A.A.彼此无关彼此无关 B.B.必须同步必须同步C.C.必须互斥必须互斥 D.D.可能需要同步或互斥可能需要同步或互斥2.2.对进程间互斥地使用临界资源，进程可以（对进程间互斥地使用临界资源，进程可以（ ）A.A.互斥地进入临界区互斥地进入临界区 B.B.互斥
73、地进入各自的临界区互斥地进入各自的临界区C.C.互斥地进入同一临界区互斥地进入同一临界区 D.D.互斥地进入各自的同类资源的临界区互斥地进入各自的同类资源的临界区C CD DD D2.3.2 2.3.2 信号量机制信号量机制信号量是荷兰的计算机科学家信号量是荷兰的计算机科学家Dijkstra在在1965年提出年提出的，也是最早的同步方法。的，也是最早的同步方法。信号量代表可用资源实体的数量。信号量代表可用资源实体的数量。q公用信号量（互斥信号量）公用信号量（互斥信号量）：它为一组需互斥共享临界资：它为一组需互斥共享临界资源的并发进程而设置，代表共享的临界资源，每个进程均源的并发进程而设置，代表
74、共享的临界资源，每个进程均可对它施加可对它施加P P、V V操作，即都可申请和释放该临界资源，其操作，即都可申请和释放该临界资源，其初始值置为初始值置为1 1。q专用信号量（同步信号量）专用信号量（同步信号量）：它为一组需同步协作完成任：它为一组需同步协作完成任务的并发进程而设置，只有拥有该资源的进程才能对它施务的并发进程而设置，只有拥有该资源的进程才能对它施加加P P操作（即可申请资源），而由其合作进程对它施加操作（即可申请资源），而由其合作进程对它施加V V操操作（即释放资源）。作（即释放资源）。在长期广泛的应用中，信号量机制又得到了很大的在长期广泛的应用中，信号量机制又得到了很大的发展，
75、它从发展，它从整型信号量机制整型信号量机制发展到发展到记录型信号量机制记录型信号量机制，进而发展为进而发展为“信号集信号集”机制机制。现在信号量机制已广泛应。现在信号量机制已广泛应用于用于OS中。中。1.1.整型信号量整型信号量 用一个整型变量作为信号量用一个整型变量作为信号量( (如如 S)S)，信号量的初值，信号量的初值表示同类临界资源的个数。设置两种基本操作表示同类临界资源的个数。设置两种基本操作wait(S)/P(S)wait(S)/P(S)和和signal(S)/V(S)signal(S)/V(S) (P和和V分别是荷兰文分别是荷兰文的的“等待等待”和和“发信号发信号”两词的首字母两
76、词的首字母) ，利用对信号，利用对信号量的改变达到互斥与同步的目的。当信号量被初始化后，量的改变达到互斥与同步的目的。当信号量被初始化后，只能为只能为P P、V V操作所改变。操作所改变。P P、V V是一对同步原语，是不可是一对同步原语，是不可中断的原子操作。中断的原子操作。wait(S):while(S=0);S=S-1；sinal(S):S=S+1;当一进程在值不大于当一进程在值不大于0的信号量的信号量S上执行上执行wait操作时，将在循环语操作时，将在循环语句句while上陷入忙等待，直到其他上陷入忙等待，直到其他进程在该信号量进程在该信号量S上执行上执行signal操操作后，解除它的
77、等待。未遵循作后，解除它的等待。未遵循“让权等待让权等待”的准则。的准则。2.2.记录型信号量机制记录型信号量机制把信号量由整型量扩充成为记录形式，可实现把信号量由整型量扩充成为记录形式，可实现“让让权等待权等待”。每个信号量。每个信号量S除一个整数值除一个整数值S.value（计数）（计数）外，还有一个进程等待队列外，还有一个进程等待队列S.L，用于存放所有等待进，用于存放所有等待进程。程。 wait(S):-s.value;s.value;/表示申请一个资源表示申请一个资源; ;if (s.value 0)if (s.value 0)/表示没有空闲资源表示没有空闲资源; ;block(S.
78、L);/ 调用进程进入等待队列调用进程进入等待队列, ,阻塞调用进程阻塞调用进程; ;+S.value;+S.value;/表示释放一个资源；表示释放一个资源；if (S.value = 0) /if (S.value 0表示某类资源的当前可用数。表示某类资源的当前可用数。每执行一次每执行一次wait操作意味着请求分配一个单位的资源，因此描述为操作意味着请求分配一个单位的资源，因此描述为-s.value;qs.value0表示该类资源已不能供分配，因此请求资源的表示该类资源已不能供分配，因此请求资源的进程将被阻塞在等待队列进程将被阻塞在等待队列s.L中，此时中，此时s.value的绝对值等的绝
79、对值等于等待队列于等待队列s.L中的进程数。执行一次中的进程数。执行一次signal操作意味着释操作意味着释放一个单位资源，故描述为放一个单位资源，故描述为+s.value;q若若s.value0，表示在等待队列，表示在等待队列s.L中有因请求该资源不中有因请求该资源不能满足而被阻塞的进程，因此唤醒等待队列能满足而被阻塞的进程，因此唤醒等待队列s.L中的第一中的第一个或优先数最高的进程，允许其使用该资源。个或优先数最高的进程，允许其使用该资源。例：例：S.value=4S.value=0S.value=2P1P2wait(S)：表示请求分配一个资源：表示请求分配一个资源S.value0立即可得
80、立即可得S.value 0要排队要排队signal(S)：表示释放资源表示释放资源3.AND3.AND型信号量型信号量 两个进程两个进程A、B要求访问共享资源要求访问共享资源D、E:processA:processB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若进程若进程A和和B按下述次序交替执行按下述次序交替执行wait操作：操作：processA:wait(Dmutex);于是于是Dmutex=0processB:wait(Emutex);于是于是Emutex=0processA:wait(Emutex);于是于是Emutex=
81、-1A阻塞阻塞processB:wait(Dmutex);于是于是Dmutex=-1B阻塞阻塞将将进进程程在在整整个个运运行行过过程程中中需需要要的的所所有有资资源源，一一次次性性全全部部地地分分配配给给进进程程，待待进进程程使使用用完完后后再再一一起起释释放放。只只要要尚尚有有一一个个资资源源未未能能分分配配给给进进程程，其其它所有可能为之分配的资源，也不分配给他。它所有可能为之分配的资源，也不分配给他。在在wait操操作作中中，增增加加了了一一个个“AND”条条件件，故故称称 为为 AND同同 步步 ， 或或 称称 为为 同同 时时 wait操操 作作 ， 即即Swait(Simultan
82、eouswait)。ANDAND同步机制的基本思想：同步机制的基本思想：Swait(S1,S2,Sn)ifSi1andandSn1thenfori:=1tondoSi =Si-1;endforelseplacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal(S1,S2,Sn)fori =1tondoSi:=Si+1;Removealltheprocesswaiti
83、nginthequeueassociatedwithSiintothereadyqueue.endfor; 4.4.信号量集信号量集 记录型信号量机制存在问题：记录型信号量机制存在问题：q当一次需要当一次需要N个某类资源时，需进行个某类资源时，需进行N次次wait(S)操作，操作，显然低效；显然低效；q某些情况下，当资源数量低于某一下限值时，不予分某些情况下，当资源数量低于某一下限值时，不予分配，因此在每次分配前都必须测试该资源数量。配，因此在每次分配前都必须测试该资源数量。对对AND信信号号量量机机制制加加以以扩扩充充，形形成成一一般般化化的的“信号量集信号量集”机制。机制。Swait(S1
84、,t1,d1,Sn,tn,dn)ifSit1andandSntnthenfori =1tondoSi =Si-di;endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSitiandsetitsprogramcountertothebeginningoftheSwaitOperation.endifS为信号量，为信号量，d为需求值，为需求值，t为下限值为下限值signal(S1,d1,Sn,dn)fori =1tondoSi =Si+di;Removealltheprocesswaitinginthequeuea
85、ssociatedwithSiintothereadyqueueendfor;一般一般“信号量集信号量集”的几种特殊情况：的几种特殊情况：qSwait(S,d,d)：此时在信号量集中只有一个信：此时在信号量集中只有一个信号量号量S，但允许它每次申请但允许它每次申请d个资源，当现有资源个资源，当现有资源数少于数少于d时，不予分配。时，不予分配。qSwait(S,1,1)：此时的信号量集已蜕化为一般：此时的信号量集已蜕化为一般的记录型信号量的记录型信号量(S1时时)或互斥信号量或互斥信号量(S=1时时)qSwait(S,1,0)：这是一种很特殊且很有用的信：这是一种很特殊且很有用的信号量操作。当号
86、量操作。当S1时，允许多个进程进入某特定时，允许多个进程进入某特定区；当区；当S变为变为0后，将阻止任何进程进入特定区。后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。换言之，它相当于一个可控开关。1 1、利用信号量解决进程互斥、利用信号量解决进程互斥n为临界资源设置一个为临界资源设置一个互斥信号量互斥信号量mutex(MULTualExclusion)，其，其初值为初值为1,表明该临界资源未被占用表明该临界资源未被占用；在每；在每个进程中将临界区代码置于个进程中将临界区代码置于P(mutex)和和V(mutex)原语之原语之间间n必须必须成对使用成对使用P和和V原语：遗漏原语：遗
87、漏P原语则不能保证互斥访问，原语则不能保证互斥访问，遗漏遗漏V原语则不能在使用临界资源之后将其释放（给其他原语则不能在使用临界资源之后将其释放（给其他等待的进程）；等待的进程）；P、V原语原语不能次序错误、重复或遗漏。不能次序错误、重复或遗漏。P(mutex)V(mutex)P(mutex)V(mutex)2.3.2 2.3.2 信号量的应用信号量的应用例：夫妻两人的共同存款，保存在例：夫妻两人的共同存款，保存在count(共享资源共享资源)变量变量中。中。semaphoreS=1;intcount;进程进程p1：intR1;P(S);R1 =count;R1 =R1+1;count =R1;
88、V(S)进程进程P2：intR1;P(S);R1 =count;R1 =R1+1;count =R1;V(S)例例:设设一一民民航航航航班班售售票票系系统统有有n个个售售票票处处。每每个个售售票票处处通通过过终终端端访访问问系系统统中中的的公公用用数数据据区区，假假定定公公共共数数据据区区中中一一些些单单元元xk(k=1,2,)分分别别存存放放月月日日次次航航班班的的现现存存票票数数。设设P1，P2，Pn表表示示各各售售票票处处的的处处理理进进程程，R1,R2,Rn表表示示各各进进程程执执行行时时所所用用的的工工作作单单元元。用用信信号号量量实实现现进进程程间间互互斥斥的的程程序序如下：如下：
89、SemaphoreS=1;进程进程Pi(i=1,2,n)按旅客订票要求找到按旅客订票要求找到xk;P(S)Ri=xk;if(Ri=1)Ri=Ri-1;xk=Ri;V(S);输出一张票输出一张票;elseV(S);输出输出“票已售完票已售完”;利用信号量同样可以方便地实现合作进程之间的同利用信号量同样可以方便地实现合作进程之间的同步。方法是为某个事件设置一个信号量步。方法是为某个事件设置一个信号量event,初值为初值为0，表示该事件还未发生，当一进程需要等待表示该事件还未发生，当一进程需要等待event对应的事对应的事件时执行件时执行P(event)，如果此时，如果此时event.count=
90、0，则阻塞该进，则阻塞该进程，将它挂入程，将它挂入event的等待队列；若的等待队列；若event.count=1，则表，则表示事件已发生，该进程可继续执行。当某进程完成了示事件已发生，该进程可继续执行。当某进程完成了event的事件时，立即执行的事件时，立即执行V(event)唤醒唤醒event等待队列中等待队列中的某个进程。的某个进程。我们把信号量我们把信号量event称为称为专用信号量专用信号量，即只有需要，即只有需要等等待待event相应事件发生的进程或说需要其它某个进程给予相应事件发生的进程或说需要其它某个进程给予合作的进程合作的进程在在event上执行上执行P操作操作，而，而完成完
91、成event事件事件的进的进程或说提供合作的进程只程或说提供合作的进程只在在event上执行上执行V操作。操作。2 2、利用信号量解决进程同步、利用信号量解决进程同步 例例：用信号量实现司机和售票员的同步。：用信号量实现司机和售票员的同步。(1)确定同步的规则确定同步的规则根据一般常识，根据一般常识，司机和售票员在车上的操作规则如下：司机和售票员在车上的操作规则如下：1)售票员操作的规则是只有司机停车后，售票员才能开门售票员操作的规则是只有司机停车后，售票员才能开门让乘客上下车；让乘客上下车；2)司机操作的规则是只有售票员关门后，司机才能启动开司机操作的规则是只有售票员关门后，司机才能启动开始
92、行驶汽车。始行驶汽车。（2 2）进程的操作流程）进程的操作流程 售票员进程售票员进程do while do while 关车门；关车门；设立车门已关标志设立车门已关标志; ;售票；售票；是否停车？没停则等待是否停车？没停则等待; ;开车门；开车门；上下乘客；上下乘客；enddo enddo dowhile是否关门？没关则等待是否关门？没关则等待;启动车辆；启动车辆；正常行车；正常行车；到站停车；到站停车；设立车停标志设立车停标志;enddo司机进程司机进程(3)(3)确定信号量的个数和含义确定信号量的个数和含义根据同步规则以及操作流程确定信号量的个数是根据同步规则以及操作流程确定信号量的个数是
93、2 2个个,S1,S1和和S2S2。 S1S1的含义是否关门；的含义是否关门； S2S2的含义是否停车。的含义是否停车。(4)(4)确定信号量的初值确定信号量的初值( (假设正处于停车状态假设正处于停车状态) ) S1=0 S1=0； S2=1S2=1。(5)(5)确定确定P P、V V操作的位置操作的位置1 1）司机操作中，是否关门？没关则等待，这是一个）司机操作中，是否关门？没关则等待，这是一个P P操作，操作， P(S1)P(S1)；2 2）司机操作中，设立停车标志，这是一个）司机操作中，设立停车标志，这是一个V V操作，操作，V(S2)V(S2)；3 3）售票员操作中，是否停车？没停则
94、等待，这是一个）售票员操作中，是否停车？没停则等待，这是一个P P操作操作 ，P(S2)P(S2)；4 4）售票员操作中，设立关门标志，这是一个）售票员操作中，设立关门标志，这是一个V V 操作，操作，V(S1)V(S1)(6)(6)P P、V V操作实现操作实现 int S1=0int S1=0， S2=1;S2=1;main()main() cobegin cobegin driver(); busserver(); driver(); busserver(); coend coend driver()driver() do while T do while T P(S1) P(S1)；
95、启动车辆；启动车辆； 正常行车；正常行车； 到站停车；到站停车； V(S2)V(S2)； busserver()busserver() do while T do while T 关车门；关车门； V(S1)V(S1)； 售票；售票； P(S2)P(S2)； 开车门；开车门； 上下乘客；上下乘客； 例：使用信号量机制，把如下前趋图转换成可并发例：使用信号量机制，把如下前趋图转换成可并发执行的程序。执行的程序。P1P4P2P3P5P6VarS12,S13,S14,S25,S24,S35,S46,S56:Semaphores=0,0,0,0,0,0,0,0;BeginParbeginBeginP1
96、;V(S12);V(S13);V(S14);EndBeginP(S12);P2;V(S25);V(S24);EndBeginP(S13);P3;V(S35);EndBeginP(S14);P4;V(S46);EndBeginP(S25);P(S35);P5;V(S56);EndBeginP(S46);P(S56);P6;EndParendEnd1.1.用用P P、V V操作管理临界区时，信号量的初值一般定义为操作管理临界区时，信号量的初值一般定义为 （ ）。）。A.A.1 B.0 C.1 D.1 B.0 C.1 D.任意值任意值3.3.若信号若信号S S的初值为的初值为2 2，当前值为，当前值
97、为-1-1，则表示有，则表示有( )( ) 个等待进程？个等待进程？A. 0 B. 1 C. 2 D. 3A. 0 B. 1 C. 2 D. 32.2.有有m m个进程共享同一临界资源，若使用信号量机制实个进程共享同一临界资源，若使用信号量机制实 现对一临界资源的互斥访问，则信号量的变化范围现对一临界资源的互斥访问，则信号量的变化范围 是（是（ ）。）。 A. 1A. 1至至 (m-1) B. 1(m-1) B. 1至至m-1 C. 1m-1 C. 1至至m D. 1m D. 1至至m mC CA AB B4.4.当一进程因在记录型信号量当一进程因在记录型信号量S S上执行上执行P(S)P(S
98、)操作而被操作而被 阻塞后，阻塞后，S S的值为（的值为（ ）。）。 A.0 B.0 B.0 B.0 B.0 C.0 D.0B BD DB B例：利用信号量解决如图所示的计算进程例：利用信号量解决如图所示的计算进程C C和打印进程和打印进程P P 通过缓冲区通过缓冲区BufferBuffer传送数据的同步问题。传送数据的同步问题。 BufferCP C C和和P P两进程并发执行，必须在执行序列上遵循以两进程并发执行，必须在执行序列上遵循以下规则，才能避免错误。下规则，才能避免错误。n只有当只有当C C进程把数据送入进程把数据送入BufferBuffer后，后，P P进程才能从进程才能从Buf
99、ferBuffer中取出数据来打印，否则中取出数据来打印，否则P P进程只能等待。进程只能等待。n只有当只有当P P进程从进程从BufferBuffer中取走数据后，中取走数据后，C C进程才能将进程才能将新计算的数据再存入新计算的数据再存入Buffer,Buffer,否则否则C C进程也只能等待。进程也只能等待。如何协调两个进程之间的执行次序呢？作法如下：如何协调两个进程之间的执行次序呢？作法如下： 设置信号量：设置信号量：q 信号量信号量m用以表示缓冲区有无可供打印的结果。用以表示缓冲区有无可供打印的结果。 m的初值为的初值为0 0。q 信号量信号量n用以表示缓冲区中计算结果是否被取走。用
100、以表示缓冲区中计算结果是否被取走。n的初值为的初值为0 0。计算进程计算进程 C C计算结果计算结果缓冲区缓冲区V(m)P(n)打印进程打印进程 P PP(m)V(n)缓冲区缓冲区打印打印设置信号量：设置信号量：q 信号量信号量m用以表示缓冲区有无可供打印的结果。用以表示缓冲区有无可供打印的结果。 m的初值为的初值为0 0。q 信号量信号量n用以表示缓冲器是否为空，用以表示缓冲器是否为空，n的初值为的初值为1 1 。计算进程计算进程 C C计算结果计算结果缓冲区缓冲区V(m)P(n)打印进程打印进程 P PP(m)V(n)缓冲区缓冲区打印打印 例：有三个进程例：有三个进程get,copy,pu
101、t设置设置4 4个信号量并设初值：个信号量并设初值： S1:buffer1S1:buffer1中是否为空，中是否为空， S1=1S1=1； S2:buffer1S2:buffer1中是否有数据，中是否有数据， S2=0S2=0； S3:buffer1S3:buffer1中是否有可供打印数据，中是否有可供打印数据， S3=0S3=0； S4:buffer1S4:buffer1中是否为空，中是否为空， S4=1S4=1。进程进程get向向Buffer1读数据读数据V(S2)P(S1)进程进程copy Buffer1Buffer2V(S1)P(S2)P(S4)V(S3)进程进程put将将Buffer
102、2内容输出内容输出V(S4)P(S3)getcopyputBuffer1Buffer2问问题题演演变变：如如下下图图所所示示，有有多多个个get操操作作同同时时向向Buffer1放数据，有一个放数据，有一个copy操作不断地将操作不断地将Buffer1的数据移到的数据移到Buffer2，有多个，有多个put操作不断地从操作不断地从Buffer2中将数据取走。中将数据取走。Buffer1的容量为的容量为m m，Buffer2的容量是的容量是n,get、copy、put每次操作一个数据，在操作的过程中要保证数据不每次操作一个数据，在操作的过程中要保证数据不丢丢失失。试试用用、原原语语协协调调get
103、、copy、put的的操操作作，并并说明每个信号量的含义和初值。说明每个信号量的含义和初值。putgetBuffer1Buffer2copy2.设设A、B为两个并发进程，它们共享一个临界资源，其为两个并发进程，它们共享一个临界资源，其执行临界区的算法框图如下图所示。试判断该算法是执行临界区的算法框图如下图所示。试判断该算法是否有错？请说明理由。如果有错，请改正。否有错？请说明理由。如果有错，请改正。S1、S2的的初值为初值为0，CSA、CSB为临界区。为临界区。A进程进程CSAV(S1)P(S2)P(S1)CSBV(S2)B进程进程1.一售票厅只能容纳一售票厅只能容纳300人，当少于人，当少于
104、300人时，可以进入；人时，可以进入；否则，需在外等候。若将每一个购票者作为一个进程，否则，需在外等候。若将每一个购票者作为一个进程，请用请用P、V操作编程，并写出信号量的初值。操作编程，并写出信号量的初值。练习：练习：信号量及信号量及P P、V V操作讨论操作讨论lP.VP.V操作必须操作必须成对成对出现，有一个出现，有一个P P操作就一定有一操作就一定有一个个V V操作；操作；l当为当为互斥互斥操作时，它们操作时，它们同处于同一进程同处于同一进程；l当为当为同步同步操作时，则操作时，则不在同一进程中出现不在同一进程中出现；l如果如果P(S1)P(S1)和和P(S2)P(S2)两个操作在一起
105、，那么两个操作在一起，那么P P操作的操作的顺序至关重要顺序至关重要, ,一个同步一个同步P P操作与一个互斥操作与一个互斥P P操作在操作在一起时一起时同步同步P P操作在互斥操作在互斥P P操作前操作前；l两个两个V V操作顺序无关紧要。操作顺序无关紧要。问题：采用问题：采用PVPV同步机制来编写并发程序同步机制来编写并发程序, ,对于共享变对于共享变 量及信号量变量的操作将被分散于各个进程中量及信号量变量的操作将被分散于各个进程中缺点：缺点：n易读性差、不利于修改和维护易读性差、不利于修改和维护n正确性难以保证正确性难以保证解决：解决：nDijkstra(1971)Dijkstra(19
106、71)：“秘书秘书”进程进程nHansenHansen和和Hoare(1973)Hoare(1973)：管程：管程2.3.4 2.3.4 管程机制管程机制管程的提出管程的提出 管程是一种管程是一种同步机制同步机制, ,是关于共享资源的是关于共享资源的数据及在其上操作的一组过程数据及在其上操作的一组过程( (或共享数据结或共享数据结构及其规定的所有操作构及其规定的所有操作) )。 1.1.管程的定义管程的定义2.2.管程的基本思想管程的基本思想 管程作为一种管程作为一种集中的同步机制集中的同步机制, ,是将共享是将共享变量以及对共享变量能够进行的所有操作集中变量以及对共享变量能够进行的所有操作集
107、中在在一个模块中一个模块中，一个操作系统或并发程序由若，一个操作系统或并发程序由若干个这样的模块所构成。一次只能有一个进程干个这样的模块所构成。一次只能有一个进程在管程内活动，保障共享资源的互斥执行。在管程内活动，保障共享资源的互斥执行。n 管程名称管程名称n 局部于管程的共享数据结构说明局部于管程的共享数据结构说明n 对该数据结构进行操作的一组过程对该数据结构进行操作的一组过程/ /函数函数n 对该数据结构初始化语句对该数据结构初始化语句3. 3. 管程的四个组成部分：管程的四个组成部分：3.3.管程的语法描述管程的语法描述TYPEmonitor_name=MONITOR;Defineuse
108、PROCEDURE（）；）；BEGIN.END;.FUNCTION（）：值类型；）：值类型；BEGIN.END;.BEGIN；END;（1 1）模块化，一个管程是一个基本程序单位，）模块化，一个管程是一个基本程序单位，可以单独编译。可以单独编译。（2 2）抽象数据类型，管程是一种特殊的数据类）抽象数据类型，管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作型，其中不仅有数据，而且有对数据进行操作的代码。的代码。（3 3）信息掩蔽，管程是半透明的，管程中的外）信息掩蔽，管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功部过程（函数）实现了某些功能，至于这些功能是怎样实
109、现的，在其外部则是不可见的。能是怎样实现的，在其外部则是不可见的。4.4.管程的三个主要的特性管程的三个主要的特性l由于管程通常是用于管理资源的，因而在管程内由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。因资源被占用等原因不能继续运行时使其等待。l为此在管程内部可以说明和使用一种特殊类型的为此在管程内部可以说明和使用一种特殊类型的变量，称作变量，称作条件变量条件变量, ,只能在管程中访问：只能在管程中访问： var x,y :condition;var x,y :condi
110、tion; l对于条件型变量，可以执行对于条件型变量，可以执行waitwait和和signalsignal操作，操作，每个条件变量保存了一个链表，用以每个条件变量保存了一个链表，用以记录因该条记录因该条件变量而阻塞的所有进程件变量而阻塞的所有进程。5.5.条件变量条件变量lx.wait:x.wait:正在调用管程的进程因正在调用管程的进程因 x x 条件需要被条件需要被阻塞或挂起，则调用阻塞或挂起，则调用x.waitx.wait将自己插入到等待将自己插入到等待队列上，并释放管程，直到队列上，并释放管程，直到 x x 条件变化。条件变化。lx.signal:x.signal:正在调用管程的进程发
111、现正在调用管程的进程发现 x x 条件发条件发生了变化，则调用生了变化，则调用x.signalx.signal，重新启动一个因，重新启动一个因 x x 条件而阻塞或挂起的进程。但如果没有被阻条件而阻塞或挂起的进程。但如果没有被阻塞的进程，则塞的进程，则x.signalx.signal操作不产生任何后果。操作不产生任何后果。这与信号量机制中的这与信号量机制中的signalsignal操作不同。因为，操作不同。因为，后者总是要执行后者总是要执行s =s+1s =s+1操作，因而总会改变操作，因而总会改变信号量的状态。信号量的状态。 多个进程出现在管程中多个进程出现在管程中, ,当一个进入管程的进当
112、一个进入管程的进程执行唤醒操作时（如唤醒），管程中便存程执行唤醒操作时（如唤醒），管程中便存在两个同时处于活动状态的进程。在两个同时处于活动状态的进程。处理方法有三种：处理方法有三种：l等待继续，直到退出或等待等待继续，直到退出或等待（HoareHoare）；）；l等待继续，直到等待或退出；等待继续，直到等待或退出；l规定唤醒为管程中过程最后一个可执行的操作。规定唤醒为管程中过程最后一个可执行的操作。（HansanHansan）问题问题: :l管程中的共享变量在管程外部是不可见的，外管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函部只能通过调用管程中所说明的外部
113、过程（函数）来间接地访问管程中的共享变量。数）来间接地访问管程中的共享变量。l为了保证管程共享变量的数据完整性，规定管为了保证管程共享变量的数据完整性，规定管程程互斥进入。互斥进入。l因为管程是互斥进入的，所以当一个进程试图因为管程是互斥进入的，所以当一个进程试图进入一个已被占用的管程时，应当在管程的入进入一个已被占用的管程时，应当在管程的入口处等待，所以在管程的入口处应当有一个进口处等待，所以在管程的入口处应当有一个进程等待队列，称作程等待队列，称作入口等待队列入口等待队列。6.6.管程的要素管程的要素l如果进程唤醒进程，则等待继续，如如果进程唤醒进程，则等待继续，如果进程在执行时又唤醒进程
114、，则等待果进程在执行时又唤醒进程，则等待继续继续如此，在管程内部，由于执行唤醒操作，如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程，因而还需要有一个可能会出现多个等待进程，因而还需要有一个进程等待队列，这个等待队列被称为进程等待队列，这个等待队列被称为紧急等待紧急等待队列队列。它的优先级应当高于入口等待队列的优。它的优先级应当高于入口等待队列的优先级。先级。管程的示意图管程的示意图（1 1）进程定义的是私有数据结构）进程定义的是私有数据结构PCBPCB，管程定义，管程定义 的是公共数据结构，如消息队列等；的是公共数据结构，如消息队列等；（2 2）进程是由顺序程序执行有关的操作，管程
115、是）进程是由顺序程序执行有关的操作，管程是 进行同步操作和初始化操作；进行同步操作和初始化操作；（3 3）设置目的不同，进程实现系统的并发性，管）设置目的不同，进程实现系统的并发性，管 程解决共享资源的互斥使用；程解决共享资源的互斥使用；（4 4）管程被进程调用；）管程被进程调用；（5 5）进程之间可并发，管程不能与其调用者并发；）进程之间可并发，管程不能与其调用者并发；（6 6）管程是操作系统的固有成分，无创建和撤消。）管程是操作系统的固有成分，无创建和撤消。7. 7. 管程和进程的异同点：管程和进程的异同点：2.4 2.4 经典进程的同步问题经典进程的同步问题消费者进程消费者进程Q生产者进
116、程生产者进程P简单的生产者简单的生产者-消费者问题消费者问题2.4.1 2.4.1 生产者生产者- -消费者问题消费者问题1.1.利用记录型信号量解决生产者利用记录型信号量解决生产者- -消费者问题消费者问题P P进程不能往进程不能往“满满”的缓冲区中放产品，设置信号量的缓冲区中放产品，设置信号量S1S1，表示缓冲区是否为空，初值为，表示缓冲区是否为空，初值为1 1。Q Q进程不能从进程不能从“空空”的缓冲区中取产品，设置信号量的缓冲区中取产品，设置信号量S2S2，表示缓冲区是否有产品，初值为，表示缓冲区是否有产品，初值为0 0。P：Q：while(true)while(true)生产一个产品
117、生产一个产品;P(s2);P(s1);从缓冲区取产品从缓冲区取产品;送产品到缓冲区送产品到缓冲区;V(s1);V(s2);消费产品消费产品;推广：推广：n个生产者个生产者P1，P2Pn，m个消费者个消费者Q1，Q2Qm通过环形有界缓冲区联系，缓冲区存放产品。通过环形有界缓冲区联系，缓冲区存放产品。 n n个缓冲区，每个缓冲区存放一个消息。由于缓冲池是个缓冲区，每个缓冲区存放一个消息。由于缓冲池是临界资源临界资源，它只允许一个生产者投入消息，或者一个消费，它只允许一个生产者投入消息，或者一个消费者从中取出消息。即生产者之间、生产者与消费者之间、者从中取出消息。即生产者之间、生产者与消费者之间、消
118、费者之间都必须互斥使用缓冲池。所以必须设置消费者之间都必须互斥使用缓冲池。所以必须设置互斥信互斥信号量号量mutexmutex，它代表缓冲池资源，它的数值为，它代表缓冲池资源，它的数值为1 1。1234560n-1n-2outin满满空空生产方向生产方向消费方向消费方向l只有在缓冲池中至少有一个缓冲区已存入消息后，消费只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取消息，否则消费者必须等待。者才能从中提取消息，否则消费者必须等待。l只有缓冲池中至少有一个缓冲区是空时，生产者才能把只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区，否则生产者必须等待。消息放入缓冲区，否
119、则生产者必须等待。 l设置一个设置一个同步信号量同步信号量fullfull，它代表的资源是缓冲区满初，它代表的资源是缓冲区满初始值为始值为0 0，值为，值为n n时整个缓冲池满。这个资源是消费者类时整个缓冲池满。这个资源是消费者类进程进程Q Q所拥有，所拥有，Q Q进程可以申请该资源，对它施加进程可以申请该资源，对它施加P P操作，操作，而而C C进程的合作进程生产者进程进程的合作进程生产者进程P P对它施加对它施加V V操作。操作。l设置另一个设置另一个同步信号量同步信号量emptyempty，它代表的资源是缓冲区，它代表的资源是缓冲区空，初始值为空，初始值为n n，表示缓冲池中所有缓冲区空
120、。，表示缓冲池中所有缓冲区空。l整型量整型量inin和和outout：初值均为：初值均为0 0，inin指示首空缓冲块序号，指示首空缓冲块序号，outout指示首满缓冲块序号。指示首满缓冲块序号。同时生产者和消费者之间应满足下列二个同时生产者和消费者之间应满足下列二个同步条件同步条件：设置信号量：设置信号量：in=0; in=0; while (true) while (true) 生产产品生产产品 ； P (empty) P (empty) ； P (mutex) P (mutex) ； 往往BufferinBufferin中放产品中放产品 ； in=(in+1) % n in=(in+1)
121、 % n ； V (mutex) V (mutex) ； V (full) V (full) ； P：Q：out=0; out=0; while (true)while (true) P (full) P (full) ； P (mutex) P (mutex) ； 从从bufferoutbufferout中取产品中取产品 ； out = (out+1) % n out = (out+1) % n ； V (mutex) V (mutex) ； V (empty) V (empty) ； 消费产品消费产品 ； 例：例：桌上有一空盘，只允许存放一个水果。爸爸可向盘桌上有一空盘，只允许存放一个水果
122、。爸爸可向盘中放苹果，也可向盘中放桔子。儿子专等吃盘中的中放苹果，也可向盘中放桔子。儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘中空时一桔子，女儿专等吃盘中的苹果。规定当盘中空时一次只能放一只水果供吃者取用，请用次只能放一只水果供吃者取用，请用P、V原语实现原语实现爸爸、儿子、女儿三个并发进程的同步。爸爸、儿子、女儿三个并发进程的同步。分析分析:在本题中，爸爸、儿子、女儿共用一个盘子，且在本题中，爸爸、儿子、女儿共用一个盘子，且盘中一次只能放一个水果。当盘子为空时，爸爸可盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是苹果，将一个水果放入果盘中。若放入
123、果盘中的是苹果，则允许女儿吃，儿子必须等待；若放入果盘中的是则允许女儿吃，儿子必须等待；若放入果盘中的是桔子，则允许儿子吃，女儿必须等待。本题实际上桔子，则允许儿子吃，女儿必须等待。本题实际上是生产者是生产者-消费者问题的一种变形。这里，生产者消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。消费者只消费其中固定的一类产品。int S=1int S=1，Sa=0Sa=0，So=0;So=0;main( )main( ) cobegin cobegin father(); father();
124、son(); son(); daughter(); daughter(); coend coend 解：解：在本题中，应设置三个信号量在本题中，应设置三个信号量S、So、Sa，信号量，信号量S表示盘子是否为空，其初值为表示盘子是否为空，其初值为1；信号量；信号量So表示盘中是表示盘中是否有桔子，其初值为否有桔子，其初值为0；信号量；信号量Sa表示盘中是否有苹果，表示盘中是否有苹果，其初值为其初值为0。同步描述如下：。同步描述如下：father()father() while(1) while(1) P(S ); P(S ); 将水果放入盘中；将水果放入盘中； ifif（放入的是桔子）（放入的是
125、桔子）V(So);V(So); else V(Sa); else V(Sa); son( )son( ) while(1) while(1) P(So); P(So); 从盘中取出桔子；从盘中取出桔子； V(S);V(S); 吃桔子；吃桔子； daughter( )daughter( ) while(1)while(1) P(Sa); P(Sa); 从盘中取出苹果；从盘中取出苹果； V(S);V(S); 吃苹果；吃苹果； 2.2.利用利用ANDAND型信号量解决生产者型信号量解决生产者- -消费者问题消费者问题Varmutex,empty,full:semaphore:=1,n,0;buffe
126、r:array0,n-1ofitem;inout:integer:=0,0;beginparbeginproducer:beginrepeat produceaniteminnextp; Swait(empty,mutex);buffer(in):=nextp;in:=(in+1)modn;Ssignal(mutex,full);untilfalse;endconsumer:beginrepeatSwait(full,mutex);nextc:=buffer(out);out:=(out+1)modn;Ssignal(mutex,empty);consumertheiteminnextc;un
127、tilfalse;endparendend3. 3. 利用管程解决生产者利用管程解决生产者- -消费者问题消费者问题 n建建 立立 一一 个个 管管 程程 ， 命命 名名 为为 Producer-Consumer（PC）。其中包括两个过程：）。其中包括两个过程：(1)put(item)过过程程。生生产产者者利利用用该该过过程程将将自自己己生生产产的的产产品品投投放放到到缓缓冲冲池池中中，并并用用整整型型变变量量count来来表表示示在在缓缓冲冲池池中中已已有有的的产产品品数数目目，当当countn时时，表表示示缓缓冲冲池池已已满满，生生产产者者须须等等待待。(2)get(item)过过程程。消
128、消费费者者利利用用该该过过程程从从缓缓冲冲池池中中取取出出一一个个产产品品，当当count0时时，表表示示缓缓冲冲池池中中已无可取用的产品，已无可取用的产品，消费者应等待。消费者应等待。typeproducer-consumer=monitorVarin,out,count:integer;buffer:array0,n-1ofitem;notfull,notempty:condition;procedureput(item)beginifcountnthennotfull.wait;buffer(in)：=nextp;in：=(in+1)modn;count：=count+1;ifnotem
129、pty.queuethennotempty.signal;endprocedureget(item)beginifcount0thennotempty.wait;nextc：=buffer(out);out：=(out+1)modn;count：=count-1;ifnotfull.quenethennotfull.signal;endbeginin：=out：=0;count：=0end生产者和消费者可描述为：生产者和消费者可描述为：Producer:beginrepeatproduceaniteminnextp;PC.put(item);untilfalse;endConsumer:beg
130、inrepeatPC.get(item);consumetheiteminnextc;untilfalse;end2.4.2 2.4.2 哲学家就餐问题哲学家就餐问题 五个哲学家围坐一个圆桌，每人面前一碟通心五个哲学家围坐一个圆桌，每人面前一碟通心粉，相邻两碟之间有一根筷子。假定哲学家有两种粉，相邻两碟之间有一根筷子。假定哲学家有两种活动：吃饭与思考。当一个哲学家饥饿时，取左、活动：吃饭与思考。当一个哲学家饥饿时，取左、右最靠近他的两根筷子进餐，餐毕，放下筷子继续右最靠近他的两根筷子进餐，餐毕，放下筷子继续思考。思考。v为每根筷子设置一个为每根筷子设置一个信号量信号量chopstickicho
131、psticki, ,初值为初值为1 1。一个哲学家通过在相应信号量上执行。一个哲学家通过在相应信号量上执行P P操作抓操作抓起一支筷子，执行起一支筷子，执行V V操作放下一支筷子。操作放下一支筷子。philosopher :philosopher : while (true) while (true) P(chopsticki); P(chopsticki); P(chopstick(i+1) % 5) P(chopstick(i+1) % 5)； 用餐；用餐； V(chopsticki);V(chopsticki); V(chopstick(i+1) % 5) V(chopstick(i+1
132、) % 5)； 思考；思考； 1.1.利用记录型信号量解决哲学家就餐问题利用记录型信号量解决哲学家就餐问题 在上述的哲学家就餐过程中，我们将每个哲学家就在上述的哲学家就餐过程中，我们将每个哲学家就餐过程处理为进程，则运行速度是不可预知的，有可能餐过程处理为进程，则运行速度是不可预知的，有可能出现这种情况：五个哲学家同时饥饿，都已拿起了左边出现这种情况：五个哲学家同时饥饿，都已拿起了左边的筷子，这时他们都会因为拿不到右边的筷子而无法就的筷子，这时他们都会因为拿不到右边的筷子而无法就餐，于是谁也不能继续前进，这种情况称为餐，于是谁也不能继续前进，这种情况称为“死锁死锁”。为防止死锁发生可采取的措施
133、：为防止死锁发生可采取的措施：n最多允许最多允许4 4个哲学家同时坐在桌子周围个哲学家同时坐在桌子周围; ;n仅当一个哲学家左右两边的筷子都可用时，才允许他仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子拿筷子; ;n给所有哲学家编号，奇数号的哲学家必须首先拿左边给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之的筷子，偶数号的哲学家则反之; ;2.2.利用利用ANDAND信号量解决哲学家就餐问题信号量解决哲学家就餐问题 在哲学家进餐问题中，要求每个哲学家先获得两个临在哲学家进餐问题中，要求每个哲学家先获得两个临界资源界资源( (筷子筷子) )后方能进餐，这在本质上
134、就是前面所介绍的后方能进餐，这在本质上就是前面所介绍的ANDAND同步问题，故用同步问题，故用ANDAND信号量机制可获得最简洁的解法。信号量机制可获得最简洁的解法。Var chopstick array of semaphoreVar chopstick array of semaphore：=(1,1,1,1,1);=(1,1,1,1,1); professor professor repeat repeat think; think; Swait(chopstickSwait(chopstick(i+1) mod 5(i+1) mod 5,chopstick ,chopstick i i
135、);); eat; eat; Ssignal(chopstickSsignal(chopstick(i+1) mod (i+1) mod 5 5,chopstick,chopsticki i);); until false; until false; 读者读者: : 写者写者: : 第一个读者到时第一个读者到时P P（writewrite） P P（writewrite） Reading WritingReading Writing 最后最后一个读者离开时一个读者离开时V V（writewrite） V V（writewrite） 2.4.3 2.4.3 读者读者- -写者问题写者问题l一个数
136、据集（如文件）如果被几个并行进程所共享，有一个数据集（如文件）如果被几个并行进程所共享，有些进程只要求读数据集内容，它称些进程只要求读数据集内容，它称读者读者，而另一些进程，而另一些进程则要求修改数据集内容，它称则要求修改数据集内容，它称写者写者，几个读者可以同时，几个读者可以同时读些数据集，而不需要互斥，但一个写者不能和其它进读些数据集，而不需要互斥，但一个写者不能和其它进程（不管是写者或读者）同时访问些数据集，它们之间程（不管是写者或读者）同时访问些数据集，它们之间必须互斥。必须互斥。l设置设置互斥信号量互斥信号量writewrite, ,初值为初值为1 1，表示写者间、读者和，表示写者间
137、、读者和写者间互斥，读者和写者写者间互斥，读者和写者主要程序主要程序如下：如下： l用一个用一个变量变量readcountreadcount表示当前正在读的读者个数，初值表示当前正在读的读者个数，初值为为0 0。当进程可以去读或读结束后都要改变。当进程可以去读或读结束后都要改变readcountreadcount的的值，因此值，因此readcountreadcount又成为若干读进程的共享变量，它们又成为若干读进程的共享变量，它们必须互斥地修改必须互斥地修改readcountreadcount。故必须定义另一个用于。故必须定义另一个用于互斥互斥的信号量的信号量mutexmutex，初值也是，初
138、值也是1 1。读者读者- -写者有两个论题写者有两个论题v如果读者来：如果读者来：无读者、写者，新读者可以读；无读者、写者，新读者可以读；有写者等，但有其它读者正在读，则新读者也有写者等，但有其它读者正在读，则新读者也可以读；可以读；有写者写，新读者等。有写者写，新读者等。v如果写者来：如果写者来：无读者，新写者可以写；无读者，新写者可以写；有读者，新写者等待；有读者，新写者等待；有其它写者，新写者等待。有其它写者，新写者等待。第一类读者第一类读者- -写者问题（读者优先）：写者问题（读者优先）：第一类读者第一类读者- -写者问题的解法写者问题的解法读者：读者：while (true) whi
139、le (true) P(mutex);P(mutex); readcount +; readcount +; if(readcount=1) if(readcount=1) P(write);P(write); V(mutex);V(mutex); Reading; Reading; P(mutex);P(mutex); readcount -; readcount -; if(readcount=0) if(readcount=0) V(write);V(write); V(mutex);V(mutex);写者：写者：while (true) while (true) P(write); P
140、(write); Writing; Writing; V(write);V(write);第二类读者第二类读者- -写者问题（写者优先）：写者问题（写者优先）：v写者优先于读者写者优先于读者, ,即如果有一个写者在等待，则新即如果有一个写者在等待，则新到来的读者不允许进行读操作。到来的读者不允许进行读操作。 为了提高写者的优先级，增加一个为了提高写者的优先级，增加一个互斥信号互斥信号量量w w，初值为，初值为1 1，用以在写进程到达时封锁后续的，用以在写进程到达时封锁后续的读者进程。读者进程。第二类读者第二类读者- -写者问题的解法写者问题的解法读者：读者：while (true) while
141、 (true) P(w);P(w); P(mutex);P(mutex); readcount +; readcount +; if(readcount=1) if(readcount=1) P(write);P(write); V(mutex);V(mutex); V(w);V(w); Reading; Reading; P(mutex);P(mutex); readcount -; readcount -; if(readcount=0) if(readcount=0) V(write);V(write); V(mutex);V(mutex);写者：写者：while (true) whil
142、e (true) P(w);P(w); P(write); P(write); Writing; Writing; V(write);V(write); V(w); V(w);2. 2. 利用信号量集机制解决读者利用信号量集机制解决读者- -写者问题写者问题 Var RN integer; Var RN integer; L, mx : semaphoreL, mx : semaphore：= RN , 1;= RN , 1;beginbegin parbegin parbegin readerreader:begin:begin repeat repeat Swait(L,1,1);Swai
143、t(L,1,1); Swait(mx,1,0);Swait(mx,1,0); perform read operation; perform read operation; Ssignal(L,1);untilfalse;end v增加限制：最多允许增加限制：最多允许RNRN个读者同时读。个读者同时读。v引入信号量引入信号量L L，初值为，初值为RNRN。 writer:writer:beginbegin repeat repeat Swait(mx,1,1; L,RN,0);Swait(mx,1,1; L,RN,0); perform write operation; perform wri
144、te operation; Ssignal(mx,1); Ssignal(mx,1); until false; until false; end end parend parend end end 2.5 2.5 进程通信进程通信1.1.共享存储器系统共享存储器系统2.5.1 2.5.1 进程间高级通信的类型进程间高级通信的类型 共享存储器系统、消息传递系统、管道通信系统。共享存储器系统、消息传递系统、管道通信系统。共享存储区共享存储区进程进程A进程进程B 共享存储器的通信模式是在内存中划出共享的存储共享存储器的通信模式是在内存中划出共享的存储区。区。它是可以被多个进程共享的一部分物理内存，
145、进程把它是可以被多个进程共享的一部分物理内存，进程把这些区域链接到自己的虚地址空间上。对这些区域的访问这些区域链接到自己的虚地址空间上。对这些区域的访问与进程对其虚地址空间的其它部分的操作完全相同。当有与进程对其虚地址空间的其它部分的操作完全相同。当有进程向共享内存储区写入数据后，则共享这个内存储区的进程向共享内存储区写入数据后，则共享这个内存储区的所有进程立即可以看见共享区域中的新内容。进程就可以所有进程立即可以看见共享区域中的新内容。进程就可以通过对共享内存储区的数据的读操作与写操作进行通信。通过对共享内存储区的数据的读操作与写操作进行通信。2. 2. 消息传递系统消息传递系统 在消息机制
146、中，进程之间数据交换以格式化的在消息机制中，进程之间数据交换以格式化的消息为单位消息为单位。消息是一组可以传递的信息。通信的。消息是一组可以传递的信息。通信的进程之间不存在共享的内存，而是由发送者执行发进程之间不存在共享的内存，而是由发送者执行发送命令，接收者执行接收命令，即完成了一次消息送命令，接收者执行接收命令，即完成了一次消息的传输。传输过程对用户是透明的，由操作系统完的传输。传输过程对用户是透明的，由操作系统完成。成。3. 3. 管道通信管道通信q 在管道通信过程中，首先要建立一个管道（在管道通信过程中，首先要建立一个管道（pipepipe）文）文 件。管道文件是外存上的一个共享文件。
147、件。管道文件是外存上的一个共享文件。q 写进程向管道尾部写入数据，读进程从管道首端读出数写进程向管道尾部写入数据，读进程从管道首端读出数 据。读进程和写进程之间必须互斥地访问管道。据。读进程和写进程之间必须互斥地访问管道。q 当进程写管道时，管道满，则停写，写进程被阻塞，等当进程写管道时，管道满，则停写，写进程被阻塞，等 到被读进程唤醒后再写；读进程读管道时，管道空，则到被读进程唤醒后再写；读进程读管道时，管道空，则 停读，读进程被阻塞，等到被写进程唤醒后再读，即读停读，读进程被阻塞，等到被写进程唤醒后再读，即读 进程和写进程访问管道时要保持同步关系。进程和写进程访问管道时要保持同步关系。发送
148、进程发送进程接收进程接收进程字符流方式写入读出字符流方式写入读出,先进先出顺序先进先出顺序2.5.2 2.5.2 消息传递通信的实现方法消息传递通信的实现方法 在消息机制中，由于消息传输方式不在消息机制中，由于消息传输方式不同，可以分为同，可以分为直接通信方式直接通信方式( (消息缓冲通消息缓冲通信信) )与与间接通信方式间接通信方式( (信箱通信信箱通信) )。1 1直接通信方式（消息缓冲通信）直接通信方式（消息缓冲通信） 消息缓冲通信过程中，一个进程将一个消息直接发消息缓冲通信过程中，一个进程将一个消息直接发送给接收进程，而接收进程执行时接收这个消息。发送送给接收进程，而接收进程执行时接收
149、这个消息。发送消息与接收消息的传输过程中采用了一个数据结构消息与接收消息的传输过程中采用了一个数据结构消息缓冲区消息缓冲区，而且需要在进程的，而且需要在进程的PCBPCB表中增加一些内容。表中增加一些内容。消息缓冲区内容消息缓冲区内容发送者发送者消息长度消息长度消息正文消息正文消息队列指针消息队列指针消息队列互斥信号量消息队列互斥信号量 mutex消息队列队首指针消息队列队首指针 mq消息队列中消息个数消息队列中消息个数 smPCBPCB表内容表内容消息缓冲通信中的数据结构消息缓冲通信中的数据结构q 发送进程首先在自己地址空间的消息发送区制造一个发送进程首先在自己地址空间的消息发送区制造一个
150、始地址为始地址为a a的消息，然后调用的消息，然后调用send (Bsend (B，a)a)申请分配一申请分配一 个消息缓冲区，将个消息缓冲区，将a a指定的消息复制到缓冲区，然后指定的消息复制到缓冲区，然后 将它挂入接收进程的消息队列。将它挂入接收进程的消息队列。q 接收进程首先在自己的地址空间开辟一个始地址为接收进程首先在自己的地址空间开辟一个始地址为b b的的 消息接收区，然后调用接收命令消息接收区，然后调用接收命令receive (b)receive (b)接收消接收消 息。息。 消息缓冲通信的通信过程如下：消息缓冲通信的通信过程如下：消息缓冲通信过程消息缓冲通信过程进程进程 A发发送
151、送区区send(B,a)进程进程 B B接接收收区区mqmutexsmsender:Asize:5Text:Hellonext:0PCB（B）asender:Asize:5text:Helloreceive(b)sender:Asize:5text:Hellob发送原语发送原语sendsend的实现过程的实现过程发送区发送区(a)内容内容消息缓冲区消息缓冲区申请一个消息缓冲区申请一个消息缓冲区找出接收进程找出接收进程 B的的PCB表表P(mutex)V(mutex)V(sm)根据根据mq，把缓冲区挂到接收，把缓冲区挂到接收进程的消息链链尾进程的消息链链尾proceduresend(receiv
152、er,a)begingetbuf(a.size,i);/根据根据a.size申请缓冲区；申请缓冲区；i.sender =a.sender;i.size =a.size;i.text =a.text;i.next =0;/将发送区将发送区a中的信息复制到消息缓冲区之中；中的信息复制到消息缓冲区之中；getid(PCBset,receiver.j);/获得接收进程内部标识符；获得接收进程内部标识符；wait(j.mutex);insert(j.mq,i);/将消息缓冲区插入消息队列；将消息缓冲区插入消息队列；signal(j.mutex);signal(j.sm);end接收原语接收原语recei
153、vereceive的实现过程的实现过程 用接收进程用接收进程B的的PCB表中的表中的mq, 找出并摘下第一个消息找出并摘下第一个消息V(mutex)将消息缓冲区内容将消息缓冲区内容接收区接收区(b)找出接收进程找出接收进程 B的的PCB 表表P(sm)P(mutex)释放消息缓冲区释放消息缓冲区procedurereceive(b)beginj:=internalname;/j为为接接收收进进程程内内部部的的标标识识符符；wait(j.sm);wait(j.mutex);remove(j.mq,i);/将消息队列中第一个消息移出；将消息队列中第一个消息移出；signal(j.mutex);b.
154、sender =i.sender;b.size =i.size;b.text =i.text;/将消息缓冲区将消息缓冲区i中的信息复制到接收区中的信息复制到接收区b;end消息传递系统实现中的若干问题消息传递系统实现中的若干问题 1.通信链路通信链路(communicationlink)发发送送进进程程和和接接收收进进程程之之间间能能进进行行通通信信，必必然然建建立通信链路。立通信链路。显显式式的的“建建立立连连接接”命命令令(原原语语)请请求求系系统统为为之之建建立立一一条条通通信信链链路路；在在链链路路使使用用完完后后，也也用用显显式式方方式式拆除链路，主要用于拆除链路，主要用于计算机网络
155、计算机网络中。中。发发送送进进程程无无须须明明确确提提出出建建立立链链路路的的请请求求，只只须须利利用用系系统统提提供供的的发发送送命命令令(原原语语)，系系统统会会自自动动地地为为之之建立一条链路。这种方式主要用于建立一条链路。这种方式主要用于单机系统单机系统中。中。2.消息的格式消息的格式定长消息格式定长消息格式变长的消息格式变长的消息格式3.进程同步方式进程同步方式发送进程阻塞、发送进程阻塞、接收进程阻塞。接收进程阻塞。发送进程不阻塞、发送进程不阻塞、接收进程阻塞。接收进程阻塞。发送进程和接收进程均不阻塞。发送进程和接收进程均不阻塞。 通信时指明一个中间媒介，即信箱。在信箱通信中，通信时
156、指明一个中间媒介，即信箱。在信箱通信中，发送者创建一个消息，然后调用发送命令将消息发送到一发送者创建一个消息，然后调用发送命令将消息发送到一个共享的数据结构个共享的数据结构信箱中去，接收者调用接收命令从信箱中去，接收者调用接收命令从信箱中取出消息。信箱中取出消息。 信箱通信过程首先需要信箱通信过程首先需要创建信箱创建信箱，然后，然后发送进程发送进程向信向信箱发送信件，箱发送信件，接收进程接收进程从信箱中取信。当信箱不再需要时，从信箱中取信。当信箱不再需要时，就就撤消该信箱撤消该信箱。信箱可以在系统空间创建，也可以在用户。信箱可以在系统空间创建，也可以在用户空间创建。发送者与接收者之间可以是一对
157、一、一对多、空间创建。发送者与接收者之间可以是一对一、一对多、多对一或者多对多的关系。信箱可以是静态的，也可以是多对一或者多对多的关系。信箱可以是静态的，也可以是动态的，这是一种十分灵活的通信机制。动态的，这是一种十分灵活的通信机制。2. 2. 间接通信（信箱）间接通信（信箱）系统内核系统内核 我们知道没有配置任何软件的计算机称为裸机，我们知道没有配置任何软件的计算机称为裸机，操作系统是在裸机上添加多层软件形成的。通常将与操作系统是在裸机上添加多层软件形成的。通常将与硬件紧密相关的部分，如中断处理程序、设备驱动程硬件紧密相关的部分，如中断处理程序、设备驱动程序及进程从创建到撤消包括进程状态变迁
158、中用到的公序及进程从创建到撤消包括进程状态变迁中用到的公共操作等集中在一起，共操作等集中在一起，常驻内存常驻内存，作为裸机上添加的，作为裸机上添加的第一层软件第一层软件，叫做，叫做内核内核。 内核主要是为进程创造一个适宜的运行环境。内内核主要是为进程创造一个适宜的运行环境。内核完成中断处理、进程控制、进程通信、进程调度等核完成中断处理、进程控制、进程通信、进程调度等操作及内存的分配与回收和设备的驱动等。这些功能操作及内存的分配与回收和设备的驱动等。这些功能通常用原语来实现。通常用原语来实现。2.6 2.6 线程线程2.6.1 2.6.1 线程的基本概念线程的基本概念1.1.线程的引入线程的引入
159、 在引入进程概念的操作系统中，将进程作为一个独立在引入进程概念的操作系统中，将进程作为一个独立运行的基本单位，这包括两层含义：只有进程可以被调度运行的基本单位，这包括两层含义：只有进程可以被调度运行，只有进程才能拥有资源。运行，只有进程才能拥有资源。 当进程被创建时，系统要为它分配当进程被创建时，系统要为它分配PCBPCB表及其它必要表及其它必要的资源，如内存等；当进程被撤消时，系统要收回这些资的资源，如内存等；当进程被撤消时，系统要收回这些资源及源及PCBPCB表等，因此系统必须付出一定的时空开销。当进表等，因此系统必须付出一定的时空开销。当进程运行时，进程的切换现象更会大量存在，由于要保留
160、当程运行时，进程的切换现象更会大量存在，由于要保留当前执行进程的前执行进程的CPUCPU现场和为选中执行的进程重布现场，更现场和为选中执行的进程重布现场，更需较大的时空开销。需较大的时空开销。 为了使进程的程序充分并发执行，同时能尽量减少为了使进程的程序充分并发执行，同时能尽量减少系统的开销，人们提出了新想法，将进程调度运行和拥系统的开销，人们提出了新想法，将进程调度运行和拥有资源这两个基本运行单位的属性分开，让进程拥有资有资源这两个基本运行单位的属性分开，让进程拥有资源，而让一个新的实体作为调度运行的基本单位。基于源，而让一个新的实体作为调度运行的基本单位。基于这种想法，产生了线程的概念。这
161、种想法，产生了线程的概念。 在引入线程的操作系统中，将进程看作在引入线程的操作系统中，将进程看作资源集合资源集合与与线程集合线程集合的复合体。的复合体。 进程拥有资源，属于同一个进程的所有线程可以共进程拥有资源，属于同一个进程的所有线程可以共享这些资源享这些资源。此外，每个线程仅有较少的私用资源，如。此外，每个线程仅有较少的私用资源，如程序计数器、寄存器和栈等。程序计数器、寄存器和栈等。 每一个线程是一个动态对象，它表示进程中的一条每一个线程是一个动态对象，它表示进程中的一条控制线索，执行一系列指令操作，是一个相对独立的、控制线索，执行一系列指令操作，是一个相对独立的、可被调度运行的基本单位。
162、可被调度运行的基本单位。 在进程的地址空间中可以有多个线程，它们可以并在进程的地址空间中可以有多个线程，它们可以并发执行，这就需要一张单独的表来记录线程控制与管理发执行，这就需要一张单独的表来记录线程控制与管理等信息，这张表称为线程控制表。其中，每个线程占一等信息，这张表称为线程控制表。其中，每个线程占一项，以记录线程的程序计数器、寄存器的值及状态等信项，以记录线程的程序计数器、寄存器的值及状态等信息。程序计数器可以使线程像进程一样被暂停执行和恢息。程序计数器可以使线程像进程一样被暂停执行和恢复执行，寄存器的值等可以保存线程暂停执行时的复执行，寄存器的值等可以保存线程暂停执行时的CPUCPU状
163、态。状态。 线程由创建而产生，由撤消而消亡，在生命期间，线程由创建而产生，由撤消而消亡，在生命期间，线程可以处于就绪状态、执行状态和阻塞状态三个基本线程可以处于就绪状态、执行状态和阻塞状态三个基本状态中。这三个基本状态也像进程一样，会发生变迁，状态中。这三个基本状态也像进程一样，会发生变迁，如就绪状态如就绪状态执行状态，执行状态执行状态，执行状态阻塞状态，阻塞状阻塞状态，阻塞状态态就绪状态等。就绪状态等。2. 2. 线程与进程的比较线程与进程的比较 在引入了线程的操作系统中，一个进程除拥有资源在引入了线程的操作系统中，一个进程除拥有资源外，还包括一个或多个线程。下面将进程与线程做一比外，还包括
164、一个或多个线程。下面将进程与线程做一比较。较。 1 1调度调度 在传统的操作系统中，拥有资源的基本单位和独立在传统的操作系统中，拥有资源的基本单位和独立调度运行的基本单位都是进程。在引入线程的操作系统调度运行的基本单位都是进程。在引入线程的操作系统中，则把线程作为调度运行的基本单位，而把进程作为中，则把线程作为调度运行的基本单位，而把进程作为拥有资源的基本单位。在同一个进程中，线程的调度不拥有资源的基本单位。在同一个进程中，线程的调度不会引起进程的调度，只有在由一个进程中的线程调度到会引起进程的调度，只有在由一个进程中的线程调度到另一进程中的线程时，才会引起进程的调度。另一进程中的线程时，才会
165、引起进程的调度。 2 2并发性并发性 在引入线程的操作系统中，不仅进程之间可以并发在引入线程的操作系统中，不仅进程之间可以并发执行，而且属于同一个进程的多个线程之间也可以并发执行，而且属于同一个进程的多个线程之间也可以并发执行，因而使系统具有更好的并发性，可以更有效地使执行，因而使系统具有更好的并发性，可以更有效地使用系统资源和提高系统的吞吐量。用系统资源和提高系统的吞吐量。 3 3拥有资源拥有资源 无论是传统的操作系统，还是引入线程的操作系统，无论是传统的操作系统，还是引入线程的操作系统，进程都是拥有资源的一个独立单位，而线程仅拥有很少进程都是拥有资源的一个独立单位，而线程仅拥有很少的一些私
166、有资源（如程序计数器、寄存器和栈、线程表的一些私有资源（如程序计数器、寄存器和栈、线程表项等），但是它可以访问所属进程的所有资源。项等），但是它可以访问所属进程的所有资源。 4 4系统开销系统开销 由于在进程创建和进程撤消时，系统都要为之分配或由于在进程创建和进程撤消时，系统都要为之分配或回收资源，如回收资源，如PCBPCB表、内存空间，表、内存空间，I/OI/O设备等。因此，系统设备等。因此，系统所付出的开销显然大于创建线程和撤消线程的开销。类似所付出的开销显然大于创建线程和撤消线程的开销。类似地，在进行进程调度时，涉及到当前执行进程地，在进行进程调度时，涉及到当前执行进程CPUCPU环境的环境的保存以及新调度运行进程的保存以及新调度运行进程的CPUCPU环境的重布，而线程调度环境的重布，而线程调度只须保存和重新设置少量寄存器、程序计数器只须保存和重新设置少量寄存器、程序计数器PCPC的内容。的内容。可见，进程切换的开销远远大于线程切换的开销。此外，可见，进程切换的开销远远大于线程切换的开销。此外，由于同一进程的多个线程具有相同的地址空间，使得它们由于同一进程的多个线程具有相同的地址空间，使得它们之间的同步和通信也变得比较容易实现。之间的同步和通信也变得比较容易实现。
