计算机操作系统第3章.ppt

第第3 3章章 进程管理进程管理3.1 3.1 进程的概念进程的概念3.2 3.2 进程的描述进程的描述3.3 3.3 进程状态及其转换进程状态及其转换3.4 3.4 进程控制进程控制3.5 3.5 进程互斥进程互斥3.6 3.6 进程同步进程同步3.7 3.7 进程通信进程通信3.8 3.8 死锁问题死锁问题3.9 3.9 线程线程 丑饲宪涸病芜交诌舱疾睡奎纂旦遥窝猜浇畸信肾鲁尼痈根鸿坞橱勉六貌摔计算机操作系统第3章计算机操作系统第3章3.1 进程的概念进程的概念 现代操作系统的重要特点：现代操作系统的重要特点：程序的并发执行、资源共享、用户随机地使用程序的并发执行、资源共享、用户随机地使用1.程序的顺序执行程序的顺序执行程序的顺序执行程序的顺序执行：程序独占处理机直至最终结束的过：程序独占处理机直至最终结束的过程程序的顺序执行具有如下特点：程序的顺序执行具有如下特点：(1) 顺序性顺序性程序顺序执行时，其执行过程可看作一系列严格按程程序顺序执行时，其执行过程可看作一系列严格按程序规定的状态转移过程序规定的状态转移过程2) 封闭性封闭性程序执行得到的最终结果由给定的初始条件决定，不程序执行得到的最终结果由给定的初始条件决定，不受外界因素的影响。

受外界因素的影响蔼品共甫强沮尊包芬脚一邓封湘缝剃全循威钵征饼擂嘿兼骄掳扮脂灿客谊计算机操作系统第3章计算机操作系统第3章(3) 可再现性可再现性只要输入的初始条件相同，则无论何时重复执行该程只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果序都会得到相同的结果2. 多道程序系统中程序执行环境的变化多道程序系统中程序执行环境的变化多道程序执行的系统环境具有下述三个特点：多道程序执行的系统环境具有下述三个特点：(1) 独立性独立性每道程序都是逻辑上独立的，它们之间不存在逻辑上每道程序都是逻辑上独立的，它们之间不存在逻辑上的制约关系的制约关系2) 随机性随机性在多道程序环境下，特别是在多用户环境下，程序和在多道程序环境下，特别是在多用户环境下，程序和数据的输入与执行开始时间都是随机的数据的输入与执行开始时间都是随机的3) 资源共享资源共享资源共享将导致对进程执行速度的制约资源共享将导致对进程执行速度的制约戎罪掺共赂龙汞币敛浪虑际畅囤昭送补筐赡派漠汛抬捻秤炒睬汲赫宵疼胡计算机操作系统第3章计算机操作系统第3章3. 程序的并发执行程序的并发执行(1) 什么是程序的并发执行什么是程序的并发执行 并发执行并发执行：即一道程序的执行尚未结束；另一道程：即一道程序的执行尚未结束；另一道程序的执行已经开始的执行方式。

是为了增强计算机序的执行已经开始的执行方式是为了增强计算机系统的处理能力和提高资源利用率所采取的一种同系统的处理能力和提高资源利用率所采取的一种同时操作技术程序的并发执行可进一步分为两种：时操作技术程序的并发执行可进一步分为两种：第一种第一种第一种第一种是多道程序系统的程序执行环境变化所引起是多道程序系统的程序执行环境变化所引起的多道程序的并发执行微观上仍是顺序执行，尽的多道程序的并发执行微观上仍是顺序执行，尽管多道程序的并发执行在宏观上是同时进行的管多道程序的并发执行在宏观上是同时进行的第第第第二种二种二种二种并发执行是在某道程序的几个程序段中（例如并发执行是在某道程序的几个程序段中（例如几个程序），包含着一部分可以同时执行或顺序颠几个程序），包含着一部分可以同时执行或顺序颠倒执行的代码例如语句：倒执行的代码例如语句：驱育尾缨升挚偏廷锹钠劳擂粘签侵腆郁涉费馋剩僻慢券殃柯瘩弄品敝请莽计算机操作系统第3章计算机操作系统第3章read (a) ；；read (b) ；；它们既可以同时执行，也可颠倒次序执行对于这样它们既可以同时执行，也可颠倒次序执行对于这样的语句，同时执行不会改变顺序程序所具有的逻辑的语句，同时执行不会改变顺序程序所具有的逻辑性质。

因此，可以采用并发执行来充分利用系统资性质因此，可以采用并发执行来充分利用系统资源以提高计算机的处理能力源以提高计算机的处理能力程序的并发执行可总结为：一组在逻辑上互相独立的程序的并发执行可总结为：一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上程序或程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序段的执行尚未结束，另一个互相重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的这种执行方式程序段的执行已经开始的这种执行方式程序的并发执行不同于程序的并行执行程序的并行程序的并发执行不同于程序的并行执行程序的并行执行是指一组程序按独立的、异步的速度执行并执行是指一组程序按独立的、异步的速度执行并行执行不等于时间上的重叠可以将并发执行过程行执行不等于时间上的重叠可以将并发执行过程描述为：描述为：骇玲谬薛稼团粤伏剖弘仿希揭幅梦简畔信霹署湛参串返抱庄赔遇磺晋恤穷计算机操作系统第3章计算机操作系统第3章S0CobeginP1；；P2；；... PnCoendSn这里，这里，S0，，Sn分别表示并发程序段分别表示并发程序段P1，，P2，，…，，Pn开始执行前和并发执行结束后的语句。

开始执行前和并发执行结束后的语句P1，，2，，…，，Pn也可以由同一程序段中的不同语句组成也可以由同一程序段中的不同语句组成1966年年Bernstein 提出了提出了两相邻语句两相邻语句S1，，S2可以并发执可以并发执行的条件：行的条件：将程序中任一语句将程序中任一语句Si划分为两个变量的集合划分为两个变量的集合R(Si)和和W(Si)其中R(Si)={a1 a2 … am}，，aj(j=1，，…，，m)是语句是语句Si在执行期间必须对其进行读操作的变量；在执行期间必须对其进行读操作的变量；剪胰澎淋稳羊技猿禁尤茂斤弱超蠕宝投范魂史擅开遥取卯瑞桩蒋牛休探饱计算机操作系统第3章计算机操作系统第3章W(Si)={b1 b2 … bn}，，bj(j=1，，…，，n)是语句是语句Si在执行期间必须对其进行写操作的变量；在执行期间必须对其进行写操作的变量；如果对于如果对于两相邻语句两相邻语句S1和和S2，有，有①① R(S1)∩ W(S2)={∮∮}，，②② W(S1)∩ R(S2)={∮∮}，，③③ W(S1)∩ W(S2)={∮∮} 同时成立，则语句同时成立，则语句S1和和S2是可以并发执行的。

是可以并发执行的筷揣粹栽贿犀味自哗商巢藏樱斯郑目搅抬杂与龚瓶镜烤狈聚手沾桃法拜呛计算机操作系统第3章计算机操作系统第3章多道执行与单道执行有何优点:例：例：例：例：有三个程序有三个程序A、、B、、C；每个程序都由输入、计算、；每个程序都由输入、计算、输出三部分代码组成；记为输出三部分代码组成；记为Ai、、Ac、、Ao，，Bi、、Bc、、Bo，，Ci、、Cc、、Co；假设各部分代码在相应的设备上；假设各部分代码在相应的设备上执行的时间都为执行的时间都为t；在单道环境下：总的运行时间；在单道环境下：总的运行时间9t，，输入设备占用输入设备占用3t，输出设备占用，输出设备占用3t C P U 利用率＝利用率＝3t／／9t＝＝3／／9＝＝33.3％％ 输入设备利用率＝输入设备利用率＝3t／／9t＝＝3／／9＝＝ 33.3 ％％ 输出设备利用率＝输出设备利用率＝3t／／9t＝＝3／／9＝＝ 33.3 ％％AiAiAoAoAcAcBiBiBoBoBcBcCiCiCcCcCoCoAiAiAoAoAcAcBiBiBoBoBcBcCiCiCcCcCoCott时时间间ttttttt倚烤灼蚤善活世娃足卷凡危恍最遭骤疡陷预因这朱扼戌沟设蕴班兔蓖沥寅计算机操作系统第3章计算机操作系统第3章多道环境下多道环境下多道环境下多道环境下：总的运行时间：总的运行时间5t，输入设备占用，输入设备占用3t，输出设备占，输出设备占用用3t。

C P U 利用率＝利用率＝3t／／5t＝＝3／／5＝＝60％％ 输入设备利用率＝输入设备利用率＝3t／／5t＝＝3／／5＝＝60％％ 输出设备利用率＝输出设备利用率＝3t／／5t＝＝3／／5＝＝60％％CPUCPU时间片时间片时间片时间片进进进进 程程程程 A A进进进进 程程程程 B B进进进进 程程程程 C CtAiAiAcAcAoAoBiBiBcBcBoBoCiCiCcCcCoCotttt输入设备输入设备输入设备输入设备输出设备输出设备输出设备输出设备CPUCPU烈组譬晰酉椅耕亚朔舍泊涯血杂酌瘤选枯誉矾箩胰怯陵能铣辣拥僳咨返招计算机操作系统第3章计算机操作系统第3章(2) 程序的并发执行所带来的影响程序的并发执行所带来的影响程序的并发执行充分地利用了系统资源，从而提高了程序的并发执行充分地利用了系统资源，从而提高了系统的处理能力，这是并发执行好的一方面但是，系统的处理能力，这是并发执行好的一方面但是，正如前面所提到的那样，由于系统资源有限，程序正如前面所提到的那样，由于系统资源有限，程序的并发执行必然导致资源共享和资源竞争，从而改的并发执行必然导致资源共享和资源竞争，从而改变程序的执行速度。

如果并发执行的各程序段中语变程序的执行速度如果并发执行的各程序段中语句或指令满足上述句或指令满足上述Bernstein 的三个条件，则认为的三个条件，则认为并发执行不会对执行结果的封闭性和可再现性产生并发执行不会对执行结果的封闭性和可再现性产生影响但在一般情况下，系统要判定并发执行的各影响但在一般情况下，系统要判定并发执行的各程序段是否满足程序段是否满足Bernstein 条件是相当困难的从条件是相当困难的从而，如果并发执行的程序段不按照特定的规则和方而，如果并发执行的程序段不按照特定的规则和方法进行资源共享和竞争，则其执行结果将不可避免法进行资源共享和竞争，则其执行结果将不可避免地失去封闭性和可再现性下面的例子说明了这一地失去封闭性和可再现性下面的例子说明了这一点堤锨啮淑革梗社灌擅稿术书啃九眷呜眉孵咙檄欺溜谨躯恍赁鲤雀小阿苹科计算机操作系统第3章计算机操作系统第3章堆栈的取数和存数过程图堆栈的取数和存数过程图草爬瓶惯譬顶骂镣耘绸精遁所成珠萍梗吾扛利魂晨苏淆圃窗费柄敏售闺屉计算机操作系统第3章计算机操作系统第3章例：设有堆栈例：设有堆栈S，栈指针，栈指针top，栈中存放内存中相应数，栈中存放内存中相应数据块地址（如图据块地址（如图3.1(a)）设有两个程序段）设有两个程序段getaddr(top)和和reladdr(blk)，其中，其中getaddr(top)从给从给定的定的top所指栈中取出相应的内存数据块地址，而所指栈中取出相应的内存数据块地址，而reladdr(blk)则将内存数据块地址则将内存数据块地址blk放入堆栈放入堆栈S中。

中getaddr(top)和和reladdr(blk)可分别描述为：可分别描述为：procedure getaddr(top)beginlocal rr ←(top)top ← top-1return(r)endprocedure reladdr(blk)蜡昨馒逗柿菜联函潦叙铣挚懊反章构悦叹爸滁链有窖毗猎矽注盏粪冤望浇计算机操作系统第3章计算机操作系统第3章•例：利用堆栈管理一块内存区中各数据块的使用情况用例：利用堆栈管理一块内存区中各数据块的使用情况用getaddr(top) 从栈顶取出相应的内存块的地址用从栈顶取出相应的内存块的地址用reladdr(blk)将数据块的地址（以将数据块的地址（以bkl为地址）放入堆栈中为地址）放入堆栈中proc getaddr(top) Begin local r; 1.1 r  s[top]; 1.2 top  top-1; 1.3 return (r);end;Proc reladdr(blk) Begin 2.1 top  top+1; 2.2 s[top]  blk; End;分析分析getaddr(top) 与与reladdr(blk)的并发执行的并发执行012345t… …abtop2.1 top  top+11.1 r  s[top]1.2 top  top-11.3 return (r)2.2 s[top]  blktoptop blk抚绎蜘怔艳抿稽逆泣铱斟拄掷寝瘦宵谬专央纪鲍曹都撅获纶杆涛滁盂幕怀计算机操作系统第3章计算机操作系统第3章上例中的程序段并发执行出现错误结果是由于两程序上例中的程序段并发执行出现错误结果是由于两程序段共享资源堆栈段共享资源堆栈S，从而使得执行结果受执行速度，从而使得执行结果受执行速度影响。

一般情况下，并发执行的各程序段如果共享影响一般情况下，并发执行的各程序段如果共享软、硬件资源，都会造成其执行结果受执行速度影软、硬件资源，都会造成其执行结果受执行速度影响的局面显然，这是程序设计人员不希望看到的响的局面显然，这是程序设计人员不希望看到的为了使得在并发执行时不出现错误结果，必须采取为了使得在并发执行时不出现错误结果，必须采取某些措施来制约、控制各并发程序段的执行速度某些措施来制约、控制各并发程序段的执行速度这在操作系统程序设计中尤其重要，因为操作系统这在操作系统程序设计中尤其重要，因为操作系统用户随机性与各道程序逻辑独立的特点将使得每个用户随机性与各道程序逻辑独立的特点将使得每个用户程序所使用的软、硬件资源都受到其他并发程用户程序所使用的软、硬件资源都受到其他并发程序的共享和竞争，从而得到非预料的或不正确的结序的共享和竞争，从而得到非预料的或不正确的结果为了控制和协调各程序段执行过程中的软、硬果为了控制和协调各程序段执行过程中的软、硬件资源的共享和竞争，显然，必须应该有一个描述件资源的共享和竞争，显然，必须应该有一个描述各程序段执行过程和共享资源的基本单位各程序段执行过程和共享资源的基本单位。

膨惺茬尺赚秦憋脂东胰势翠邦秆顷臀臣蓄卫疹律伐帐暂沼颅栈船惟炼胖炒计算机操作系统第3章计算机操作系统第3章从上述讨论可以看出，由于程序的顺序性、静态性以从上述讨论可以看出，由于程序的顺序性、静态性以及孤立性，用程序段作为描述其执行过程和共享资及孤立性，用程序段作为描述其执行过程和共享资源的基本单位既增加操作系统设计和实现的复杂性，源的基本单位既增加操作系统设计和实现的复杂性，也无法反映操作系统所应该具有的程序段执行的并也无法反映操作系统所应该具有的程序段执行的并发性、用户随机性，以及资源共享等特征也就是发性、用户随机性，以及资源共享等特征也就是说，用程序作为描述其执行过程以及共享资源的基说，用程序作为描述其执行过程以及共享资源的基本单位是不合适的需要有一个能描述程序的执行本单位是不合适的需要有一个能描述程序的执行过程且能用来共享资源的基本单位这个基本单位过程且能用来共享资源的基本单位这个基本单位被称为进程（或任务）被称为进程（或任务）廓腻杯绢钉址弗险哉钎假烹多策糟乎军深粘褥份瞩紧糟俭浸祝禹其坡斥蕴计算机操作系统第3章计算机操作系统第3章3.1.2 进程的定义进程的定义进程的概念是进程的概念是60年代初期，首先在年代初期，首先在MIT 的的 Multics系系统和统和IBM 的的 TSS/360系统中引用的。

系统中引用的进程的定义进程的定义：一个具有独立功能的程序对某个数据集：一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位在处理机上的执行过程和分配资源的基本单位进程和程序是两个既有联系又有区别的概念，它们的进程和程序是两个既有联系又有区别的概念，它们的区别和关系可简述如下：区别和关系可简述如下：违臃历茹贞余赊禄瘟荆亢岳筹旱晒涛拖椿班悸痕泊荡饿夯清紧诚翟抵饲赤计算机操作系统第3章计算机操作系统第3章(1) 进程是一个动态概念，而程序则是一个静态概念进程是一个动态概念，而程序则是一个静态概念程序是指令的有序集合，没有任何执行的含义而程序是指令的有序集合，没有任何执行的含义而进程则强调执行过程，它动态地被创建，并被调度进程则强调执行过程，它动态地被创建，并被调度执行后消亡执行后消亡2) 进程具有并行特征，而程序没有由进程的定义进程具有并行特征，而程序没有由进程的定义可知，进程具有并行特征的两个方面，即独立性和可知，进程具有并行特征的两个方面，即独立性和异步性也就是说，在不考虑资源共享的情况下，异步性也就是说，在不考虑资源共享的情况下，各进程的执行是独立的，执行速度是异步的。

显然，各进程的执行是独立的，执行速度是异步的显然，由于程序不反映执行过程，所以不具有并行特征由于程序不反映执行过程，所以不具有并行特征3) 进程是竞争计算机系统资源的基本单位，从而其进程是竞争计算机系统资源的基本单位，从而其并行性受到系统自己的制约这里，制约就是对进并行性受到系统自己的制约这里，制约就是对进程独立性和异步性的限制程独立性和异步性的限制4) 不同的进程可以包含同一程序，只要该程序所对不同的进程可以包含同一程序，只要该程序所对应的数据集不同应的数据集不同财债虐憨薄翔糕敷事致漱叼儡堤沛署拍剁海开跋丝纯皇竞钥落哀邯王绊平计算机操作系统第3章计算机操作系统第3章3.1.3 作业和进程的关系作业和进程的关系作业是用户需要计算机完成某项任务时要求计算机所作业是用户需要计算机完成某项任务时要求计算机所作工作的集合进程是已提交完毕程序的执行过程作工作的集合进程是已提交完毕程序的执行过程的描述，是资源分配的基本单位区别与关系：的描述，是资源分配的基本单位区别与关系：(1) 作业是用户向计算机提交任务的任务实体在用作业是用户向计算机提交任务的任务实体在用户向计算机提交作业之后，系统将它放入外存中的户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行。

而进程则是完成用户任作业等待队列中等待执行而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位务的执行实体，是向系统申请分配资源的基本单位任一进程，只要它被创建，总有相应的部分存在于任一进程，只要它被创建，总有相应的部分存在于内存中2) 一个作业可由多个进程组成且必须至少由一个一个作业可由多个进程组成且必须至少由一个进程组成，但反过来不成立进程组成，但反过来不成立3) 作业的概念主要用在批处理系统中而进程的概作业的概念主要用在批处理系统中而进程的概念则用在几乎所有的多道系统中念则用在几乎所有的多道系统中进葛派容醉奖豁桐俱彻蚜款京茂晃渤张装成御使劫匡问据啪叹隆牌锰仗鞠计算机操作系统第3章计算机操作系统第3章3.2 进程的描述进程的描述从处理机的活动角度来看，又如何识别描述程序执行从处理机的活动角度来看，又如何识别描述程序执行活动的进程呢？显然，系统中需要有描述进程存在活动的进程呢？显然，系统中需要有描述进程存在和能够反映其变化的物理实体，即进程的静态描述和能够反映其变化的物理实体，即进程的静态描述进程的静态描述由三部分组成：进程控制块进程的静态描述由三部分组成：进程控制块PCB，，有关程序段和该程序段对其进行操作的数据结构集。

有关程序段和该程序段对其进行操作的数据结构集进程控制块包含了有关进程的描述信息、控制信息进程控制块包含了有关进程的描述信息、控制信息以及资源信息，是进程动态特征的集中反映系统以及资源信息，是进程动态特征的集中反映系统根据根据PCB感知进程的存在和通过感知进程的存在和通过PCB中所包含的各中所包含的各项变量的变化，掌握进程所处的状态以达到控制进项变量的变化，掌握进程所处的状态以达到控制进程活动的目的由于进程的程活动的目的由于进程的PCB 是系统感知进程的是系统感知进程的唯一实体，因此，在几乎所有的多道操作系统中，唯一实体，因此，在几乎所有的多道操作系统中，一个进程的一个进程的PCB结构都是全部或部分常驻内存的结构都是全部或部分常驻内存的席滚颜昨携茸诅烈鸡限甄蜜札赦稚俺择卸邱软邵恼条扮助刁蒜疲售嘴约帜计算机操作系统第3章计算机操作系统第3章进程的程序部分描述进程所要完成的功能而数据结进程的程序部分描述进程所要完成的功能而数据结构集是程序在执行时必不可少的工作区和操作对象构集是程序在执行时必不可少的工作区和操作对象这两部分是进程完成所需功能的物质基础由于进这两部分是进程完成所需功能的物质基础。

由于进程的这两部分内容与控制进程的执行及完成进程功程的这两部分内容与控制进程的执行及完成进程功能直接有关，因而，在大部分多道操作系统中，这能直接有关，因而，在大部分多道操作系统中，这两部分内容放在外存中，直到该进程执行时再调入两部分内容放在外存中，直到该进程执行时再调入内存下面分别介绍进程的内存下面分别介绍进程的PCB结构、程序与数据结构、程序与数据结构集等虱值胀蔓熬瑚裕煮汀辑拇缄泣诣勇尸阑贵湘斑楞朔翔厅鹰弃尝铀巡竖肉计算机操作系统第3章计算机操作系统第3章3.2.1 进程控制块进程控制块PCB PCB包含一个进程的描述信息、控制信息及资源信包含一个进程的描述信息、控制信息及资源信息，有些系统中还有进程调度等待所使用的现场保息，有些系统中还有进程调度等待所使用的现场保护区PCB 集中反映一个进程的动态特征在创建集中反映一个进程的动态特征在创建一个进程时，应首先创建其一个进程时，应首先创建其 PCB，然后才能根据，然后才能根据PCB 中信息对进程实施有效的管理和控制当一个中信息对进程实施有效的管理和控制当一个进程完成其功能之后，系统则释放进程完成其功能之后，系统则释放PCB，进程也随，进程也随之消亡。

之消亡根据操作系统的要求不同，根据操作系统的要求不同，PCB的内容会有所不同的内容会有所不同下面所示基本内容是必需的：下面所示基本内容是必需的：(1) 描述信息描述信息 进程名或进程标识号、进程名或进程标识号、 用户名或用户标识号、用户名或用户标识号、 家族家族关系2) 控制信息控制信息厕尸能溪场踪天魔办呼羽秀逼块必厂插嗓寝骇烽赵质缉砧夫虽卸淫唱耿残计算机操作系统第3章计算机操作系统第3章①① 进程当前状态进程当前状态进程在活动期间可分为就绪态、执行态和等待状态进程在活动期间可分为就绪态、执行态和等待状态②② 进程优先级进程优先级进程优先级是选取进程占有处理机的重要依据进程优先级是选取进程占有处理机的重要依据③③ 程序开始地址程序开始地址④④ 各种计时信息各种计时信息⑤⑤ 通信信息通信信息(3) 资源管理信息资源管理信息PCB 中包含最多的是资源管理信息，包括有关存储器中包含最多的是资源管理信息，包括有关存储器的信息、使用输入输出设备的信息、有关文件系统的信息、使用输入输出设备的信息、有关文件系统的信息等这些信息有：的信息等这些信息有：①① 占用内存大小及其管理用数据结构指针，例如后述占用内存大小及其管理用数据结构指针，例如后述内存管理中所用到的进程页表指针等。

内存管理中所用到的进程页表指针等征驱段寐糯酞怨唾臣鸭来苛郧奋漂携淌去铱运猴纪般假肝苞疯充亩宠捡吓计算机操作系统第3章计算机操作系统第3章②② 对换或覆盖用的有关信息，如对换程序段长度，对换或覆盖用的有关信息，如对换程序段长度，对换外存地址等这些信息在进程申请、释放内存对换外存地址等这些信息在进程申请、释放内存中使用③③ 共享程序段大小及起始地址共享程序段大小及起始地址④④ 输入输出设备的设备号，所要传送的数据长度、输入输出设备的设备号，所要传送的数据长度、缓冲区地址、缓冲区长度及所用设备的有关数据结缓冲区地址、缓冲区长度及所用设备的有关数据结构指针等这些信息在进程申请释放设备进行数据构指针等这些信息在进程申请释放设备进行数据传输中使用传输中使用⑤⑤ 指向文件系统的指针及有关标识等进程可使用指向文件系统的指针及有关标识等进程可使用这些信息对文件系统进行操作这些信息对文件系统进行操作空刻舍烷九白喻匠匙哩刁蛀锦跑汞等缠乘津盅畏请鸵奄芋隋棱剐侨寸丢诺计算机操作系统第3章计算机操作系统第3章(4) CPU 现场保护结构现场保护结构当前进程因等待某个事件而进入等待状态或因某种事当前进程因等待某个事件而进入等待状态或因某种事件发生被中止在处理机上的执行时，为了以后该进件发生被中止在处理机上的执行时，为了以后该进程能在被打断处恢复执行，需要保护当前进程的程能在被打断处恢复执行，需要保护当前进程的 CPU现场（或称进程上下文）。

现场（或称进程上下文）PCB 中设有专门中设有专门的的 CPU现场保护结构，以存储退出执行时的进程现场保护结构，以存储退出执行时的进程现场数据现场数据总之，进程控制块总之，进程控制块PCB 是系统感知进程存在的唯一是系统感知进程存在的唯一实体通过对实体通过对PCB 的操作，给进程分配资源、调度的操作，给进程分配资源、调度进程执行、释放进程所占有的各种资源；而完成进进程执行、释放进程所占有的各种资源；而完成进程所要求功能的程序段的有关地址，以及程序段在程所要求功能的程序段的有关地址，以及程序段在进程过程中因某种原因被停止执行后的现场信息也进程过程中因某种原因被停止执行后的现场信息也都在都在PCB 中官柠阳业肾仅槐疙缠兔萌桌俗阴痛巨搪飘最牺疤逞纠钙附说警惋缺焊包氯计算机操作系统第3章计算机操作系统第3章由于由于PCB 中包含有较多的信息，因此，一个中包含有较多的信息，因此，一个PCB表表往往要占据较大的存储空间（一般占几百到几千个往往要占据较大的存储空间（一般占几百到几千个字节）在有的系统中，为了减少字节）在有的系统中，为了减少 PCB对内存的占对内存的占用量，只允许用量，只允许PCB中最常用的部分，如中最常用的部分，如CPU现场保现场保护、进程描述信息、控制信息等常驻内存。

护、进程描述信息、控制信息等常驻内存PCB 结结构中的其他部分则存放于外存之中，待该进程将要构中的其他部分则存放于外存之中，待该进程将要执行时与其他数据一起装入内存执行时与其他数据一起装入内存近年来，面向对象技术已被用于操作系统设计在面近年来，面向对象技术已被用于操作系统设计在面向对象的操作系统中，进程的描述将采用其他方式向对象的操作系统中，进程的描述将采用其他方式培幅骚谐舵荆嘉桌客耸女徽蠕蓬茄祝纵轴岛苇梦糙箱默拂艺唬悠枯荐琵绒计算机操作系统第3章计算机操作系统第3章3.2.2 进程上下文进程上下文本节介绍包括程序段和数据集在内的上下文的概念本节介绍包括程序段和数据集在内的上下文的概念进程上下文实际上是进程执行活动全过程的静态描述进程上下文实际上是进程执行活动全过程的静态描述具体地说，进程上下文包括计算机系统中与执行该具体地说，进程上下文包括计算机系统中与执行该进程有关的各种寄存器的值、程序段在经过编译之进程有关的各种寄存器的值、程序段在经过编译之后形成的机器指令代码集（或称正文段）、数据集后形成的机器指令代码集（或称正文段）、数据集及各种堆栈值和及各种堆栈值和PCB结构结构(图图3.2)。

这里，有关寄存这里，有关寄存器和栈区的内容是重要的例如，没有程序计数器器和栈区的内容是重要的例如，没有程序计数器PC和程序状态寄存器和程序状态寄存器PS，，CPU将无法知道下条待将无法知道下条待执行指令的地址和控制有关操作从执行指令的地址和控制有关操作从CPU是活动的是活动的观点来静态地看一个进程时，必须把有关寄存器和观点来静态地看一个进程时，必须把有关寄存器和栈区的内容也包括在其中无论在何种系统中，进栈区的内容也包括在其中无论在何种系统中，进程上下文的各部分都必须按一定的规则有机地组合程上下文的各部分都必须按一定的规则有机地组合起来以便于执行起来以便于执行卫避慕釜苏芝翅析盖舌扇晰现夹烛窍悠烟鼠润涕义拆尖悠谁谨傲迁淫走殿计算机操作系统第3章计算机操作系统第3章图图3.2 进程上下文结构进程上下文结构痔垛呀箍翔煮疲峪黑烧锻尔啃迂编印趣钨僳抑睹阶汁险拂四池饰即祭凛滑计算机操作系统第3章计算机操作系统第3章进程上下文可按一定的执行层次组合，例如用户级上进程上下文可按一定的执行层次组合，例如用户级上下文、系统级上下文等显然，一个进程的执行是下文、系统级上下文等显然，一个进程的执行是在该进程的上下文中执行，而当系统调度新进程占在该进程的上下文中执行，而当系统调度新进程占有处理机时，新老进程的上下文发生转换。

有处理机时，新老进程的上下文发生转换在在UNIX System Ⅴ中，进程上下文由用户级上下文、中，进程上下文由用户级上下文、寄存器上下文以及系统级上下文组成用户级上下寄存器上下文以及系统级上下文组成用户级上下文由进程的用户程序段部分编译而成的用户正文段、文由进程的用户程序段部分编译而成的用户正文段、用户数据、用户栈等组成而寄存器上下文则由程用户数据、用户栈等组成而寄存器上下文则由程序寄存器序寄存器PC、处理机状态字寄存器、处理机状态字寄存器PS、栈指针和、栈指针和通用寄存器的值组成其中通用寄存器的值组成其中PC给出给出CPU 将要执行将要执行的下条指令的虚地址；的下条指令的虚地址；PS给出机器与该进程相关联给出机器与该进程相关联时的硬件状态，例如当前执行模式、能否执行特权时的硬件状态，例如当前执行模式、能否执行特权指令等；栈指针指向下一项的当前地址，而通用寄指令等；栈指针指向下一项的当前地址，而通用寄存器则用于不同执行模式之间的参数传递等存器则用于不同执行模式之间的参数传递等饮阂杭馆桅侩抵案炭阔孜眨净晃家狄泊烃痈货胜龋蛤炬甫泉共德钡饵拌椒计算机操作系统第3章计算机操作系统第3章进程的系统级上下文又分为静态部分与动态部分。

这进程的系统级上下文又分为静态部分与动态部分这里的动态部分不是指程序的执行，而是指在进入和里的动态部分不是指程序的执行，而是指在进入和退出不同的上下文层次时，系统为各层上下文中相退出不同的上下文层次时，系统为各层上下文中相关联的寄存器值所保存和恢复的记录关联的寄存器值所保存和恢复的记录系统级上下文的静态部分包括系统级上下文的静态部分包括PCB 结构（结构（UNIX系统系统中的中的 PCB结构被分为结构被分为proc结构和结构和user结构两部分）、结构两部分）、将进程虚地址空间映射到物理空间用的有关表格和将进程虚地址空间映射到物理空间用的有关表格和核心栈这里，核心栈主要用来装载进程中所使用核心栈这里，核心栈主要用来装载进程中所使用系统调用的调用序列系统调用的调用序列系统级上下文的动态部分是与寄存器上下文相关联的系统级上下文的动态部分是与寄存器上下文相关联的进程上下文的层次概念也主要体现在动态部分中，进程上下文的层次概念也主要体现在动态部分中，即系统级上下文的动态部分可看成是一些数量变化即系统级上下文的动态部分可看成是一些数量变化的层次组成其变化规则满足先进后出的堆栈方式，的层次组成其变化规则满足先进后出的堆栈方式，每个上下文层次在栈中各占一项。

每个上下文层次在栈中各占一项UNIX System Ⅴ的进程上下文组成如图的进程上下文组成如图3.3则跳摇咎毕龙吁研赵还豫霍擦诌晨遇膛蠢等页水茬筒颅哭彼莽捡秋乙扁俱计算机操作系统第3章计算机操作系统第3章图图3.3 UNIX System Ⅴ进程上下文组成进程上下文组成扔剐舷狙栓畦仔刁宇核皇垒补徒屏谍厦荡助锦灰掀恼应她傻流蜡促烈围绽计算机操作系统第3章计算机操作系统第3章3.2.3 进程空间进程空间任一进程，都有一个自己的地址空间，把该空间称为任一进程，都有一个自己的地址空间，把该空间称为进程空间或虚空间进程空间的大小只与处理机的进程空间或虚空间进程空间的大小只与处理机的位数有关在位数有关在UNIX以及以及Linux等操作系统中，进程等操作系统中，进程空间还被划分为用户空间和系统空间两大部分空间还被划分为用户空间和系统空间两大部分在进程空间被划分为两大部分后，用户程序在用户空在进程空间被划分为两大部分后，用户程序在用户空间内执行，而操作系统内核程序则在进程的系统空间内执行，而操作系统内核程序则在进程的系统空间内执行间内执行为防止用户程序访问系统空间，造成访问出错，系统为防止用户程序访问系统空间，造成访问出错，系统通过程序状态寄存器等设置不同的执行模式，即用通过程序状态寄存器等设置不同的执行模式，即用户模式和系统模式来进行保护。

户模式和系统模式来进行保护 兆字岿征媚惰盛敌酷蓉跳岂铸陈念档撬瞒腔疏蹭挺无锚满掸侣伞艾势阎擂计算机操作系统第3章计算机操作系统第3章3.3 进程状态及其转换进程状态及其转换3.3.1 进程状态进程状态一个进程的生命期可以划分为一组状态，这些状态刻一个进程的生命期可以划分为一组状态，这些状态刻划了整个进程系统根据划了整个进程系统根据PCB 结构中的状态值控制结构中的状态值控制进程在进程的生命期内，一个进程至少具有三种进程在进程的生命期内，一个进程至少具有三种基本状态，它们是：执行状态、等待状态和就绪状基本状态，它们是：执行状态、等待状态和就绪状态处于就绪状态的进程已经得到除处于就绪状态的进程已经得到除 CPU之外的其他资之外的其他资源，只要由调度得到处理机，便可立即投入执行源，只要由调度得到处理机，便可立即投入执行国返糯元梆琵沸唇谬诱栓蔚刑运珊酝缉秧没聘挨糙演蜒甭则笋织符咯纪骆计算机操作系统第3章计算机操作系统第3章在有些系统中，为了有效地利用内存，就绪状态又可在有些系统中，为了有效地利用内存，就绪状态又可进一步分为内存就绪状态和外存就绪状态。

在这样进一步分为内存就绪状态和外存就绪状态在这样的系统中，只有处于内存就绪状态的进程在得到处的系统中，只有处于内存就绪状态的进程在得到处理机后才能立即投入执行而处于外存就绪状态的理机后才能立即投入执行而处于外存就绪状态的进程只有先成为内存就绪状态后，才可能被调度执进程只有先成为内存就绪状态后，才可能被调度执行这种方式明显地提高了内存的利用效率，但反行这种方式明显地提高了内存的利用效率，但反过来也增加了系统开销和系统复杂性过来也增加了系统开销和系统复杂性在单在单CPU系统中，任一时刻处于执行状态的进程只能系统中，任一时刻处于执行状态的进程只能有一个只有处于就绪状态的进程经调度选中之后有一个只有处于就绪状态的进程经调度选中之后才可进入执行状态才可进入执行状态咋施始械淋泡隘勘膳篮茎纤掂妊犹赵凭书租彦裴隶伎丹贫瞒背旷旱帧式禁计算机操作系统第3章计算机操作系统第3章在某些操作系统中，一个进程在其生命期内的执行过在某些操作系统中，一个进程在其生命期内的执行过程中，总要涉及到用户程序和操作系统内核程序两程中，总要涉及到用户程序和操作系统内核程序两部分因此，进程的执行状态又可进一步划分为用部分因此，进程的执行状态又可进一步划分为用户执行状态和系统执行状态。

划分用户态和系统态户执行状态和系统执行状态划分用户态和系统态最主要的原因是要把用户程序和系统程序区分开来，最主要的原因是要把用户程序和系统程序区分开来，以利于程序的共享和保护显然，这也是以增加系以利于程序的共享和保护显然，这也是以增加系统复杂度和系统开销为代价的统复杂度和系统开销为代价的进程因等待某个事件发生而放弃处理机进入等待状态进程因等待某个事件发生而放弃处理机进入等待状态显然，等待状态可根据等待事件的种类而进一步划显然，等待状态可根据等待事件的种类而进一步划分为不同的子状态，例如内存等待、设备等待、文分为不同的子状态，例如内存等待、设备等待、文件等待和数据等待等这样做的好处是系统控制简件等待和数据等待等这样做的好处是系统控制简单，发现和唤醒相应的进程较为容易但系统中设单，发现和唤醒相应的进程较为容易但系统中设置过多的状态又会造成系统参数和状态转换过程的置过多的状态又会造成系统参数和状态转换过程的增加她炽蜜孵裴袜如淀咆洲阿拿贞蔫橡捕就纠谷迄闭柯裸恍钞篓洁粥勉镶词粹计算机操作系统第3章计算机操作系统第3章3.3.2 进程状态转换进程状态转换进程的状态反映进程执行过程的变化这些状态随着进程的状态反映进程执行过程的变化。

这些状态随着进程的执行和外界条件发生变化和转换那么，是进程的执行和外界条件发生变化和转换那么，是什么样的条件使得进程各状态发生转换呢？示图给什么样的条件使得进程各状态发生转换呢？示图给出了三个基本状态，即就绪状态、执行状态与等待出了三个基本状态，即就绪状态、执行状态与等待状态之间的转换关系状态之间的转换关系事实上，进程的状态转换是一个非常复杂的过程从事实上，进程的状态转换是一个非常复杂的过程从一个状态到另一个状态的转换除了要使用不同的控一个状态到另一个状态的转换除了要使用不同的控制过程（将在下节中讲述），有时还要借助于硬件制过程（将在下节中讲述），有时还要借助于硬件触发器才能完成例如，在触发器才能完成例如，在 UNIX 系统中，从系统系统中，从系统态到用户态的转换要借助硬件触发器完成态到用户态的转换要借助硬件触发器完成裳辑快偏雹墒僧远谩受魁余泥乙神沿玲往刊椿橇怖毖崩险斧挝驾奢蠕栅卤计算机操作系统第3章计算机操作系统第3章 进程状态转换图进程状态转换图筏柞傈牙优堡照绳裳桐叔宣京兼牌接殷丁末枕舔概粱抬佰成寂乃袱强施邢计算机操作系统第3章计算机操作系统第3章3.4 进进 程程 控控 制制进程和处理机管理的一个重要任务是进程控制。

所谓进程和处理机管理的一个重要任务是进程控制所谓进程控制，就是系统使用一些具有特定功能的程序进程控制，就是系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源从而达到多进程高效率并发执行和协调、实现资源共享的目的一般地，把系统态下执行的某些具有共享的目的一般地，把系统态下执行的某些具有特定功能的程序段称为原语原语可分为两类：一特定功能的程序段称为原语原语可分为两类：一类是机器指令级的，其特点是执行期间不允许中断类是机器指令级的，其特点是执行期间不允许中断另一类是功能级的，其特点是作为原语的程序段不另一类是功能级的，其特点是作为原语的程序段不允许并发执行这两类原语都在系统态下执行，且允许并发执行这两类原语都在系统态下执行，且都是为了完成某个系统管理所需要的功能和被高层都是为了完成某个系统管理所需要的功能和被高层软件所调用软件所调用毙顶儡迷趋娟纳抹糠亡荐刮锯衔内帝插进崔誓涤涯版贞南丈觉翻亨算瑶秉计算机操作系统第3章计算机操作系统第3章显然，系统在创建、撤消一个进程以及要改变进程的显然，系统在创建、撤消一个进程以及要改变进程的状态时，都要调用相应的程序段来完成这些功能。

状态时，都要调用相应的程序段来完成这些功能那么，这些程序段是不是原语呢？如果它们不是原那么，这些程序段是不是原语呢？如果它们不是原语，则由上述原语的定义可知，这些程序段是允许语，则由上述原语的定义可知，这些程序段是允许并发执行的然而，如果不加控制和管理地让这些并发执行的然而，如果不加控制和管理地让这些控制进程状态转换及创建和撤消进程的程序段并发控制进程状态转换及创建和撤消进程的程序段并发执行，则会使得其执行结果失去封闭性和可再现性，执行，则会使得其执行结果失去封闭性和可再现性，从而达不到进程控制的目的反过来，如果对这些从而达不到进程控制的目的反过来，如果对这些程序段采用下面章节中所述的控制方法使其在并发程序段采用下面章节中所述的控制方法使其在并发执行过程中也能完成进程控制任务的话，将会大大执行过程中也能完成进程控制任务的话，将会大大增加系统的开销和复杂度因此，在操作系统中，增加系统的开销和复杂度因此，在操作系统中，通常把进程控制用程序段做成原语用于进程控制通常把进程控制用程序段做成原语用于进程控制的原语有：创建原语、撤消原语、阻塞原语、唤醒的原语有：创建原语、撤消原语、阻塞原语、唤醒原语等。

原语等午剃池咒坡侮柴论牺症输罕糯适蛀虐尿群卑索诺隐灯睬抚竹埃讥糜刽昭乌计算机操作系统第3章计算机操作系统第3章3.4.1 进程创建与撤消进程创建与撤消1. 进程创建进程创建(1) 由系统程序模块统一创建，例如在批处理系统中，由系统程序模块统一创建，例如在批处理系统中，由操作系统的作业调度程序为用户作业创建相应的由操作系统的作业调度程序为用户作业创建相应的进程以完成用户作业所要求的功能进程以完成用户作业所要求的功能2) 由父进程创建，例如在层次结构的系统中，父进由父进程创建，例如在层次结构的系统中，父进程创建子进程以完成并行工作程创建子进程以完成并行工作由系统统一创建的进程之间的关系是平等的，它们之由系统统一创建的进程之间的关系是平等的，它们之间一般不存在资源继承关系而在父进程创建的进间一般不存在资源继承关系而在父进程创建的进程之间则存在隶属关系，且互相构成树型结构的家程之间则存在隶属关系，且互相构成树型结构的家族关系属于某个家族的一个进程可以继承其父进族关系属于某个家族的一个进程可以继承其父进程所拥有的资源另外，无论是哪一种方式创建进程所拥有的资源另外，无论是哪一种方式创建进程，在系统生成时，都必须由操作系统创建一部分程，在系统生成时，都必须由操作系统创建一部分承担系统资源分配和管理工作的系统进程。

承担系统资源分配和管理工作的系统进程奄怀钩秦讥滤夜碑蹈辊班滴普舷针祝赂队刁盯妹劈岂范末梧或券码舍廓市计算机操作系统第3章计算机操作系统第3章无论是系统创建方式还是父进程创建方式，都必须调无论是系统创建方式还是父进程创建方式，都必须调用创建原语来实现用创建原语来实现2. 进程撤消进程撤消以下几种情况导致进程被撤消：以下几种情况导致进程被撤消：(1) 该进程已完成所要求的功能而正常终止该进程已完成所要求的功能而正常终止2) 由于某种错误导致非正常终止由于某种错误导致非正常终止3) 祖先进程要求撤消某个子进程祖先进程要求撤消某个子进程采鬃承案炒垒窗这菊纂本钨伞忱雇饶踏袁邑叠惭千聋奔银简错面伺蜘泪鬃计算机操作系统第3章计算机操作系统第3章无论哪一种情况导致进程被撤消，进程都必须释放它无论哪一种情况导致进程被撤消，进程都必须释放它所占用的各种资源和所占用的各种资源和PCB 结构本身，以利于资源的结构本身，以利于资源的有效利用另外，当一个祖先进程撤消某个子进程有效利用另外，当一个祖先进程撤消某个子进程时，还需审查该子进程是否还有自己的子孙进程，时，还需审查该子进程是否还有自己的子孙进程，若有的话，还需撤消其子孙进程的若有的话，还需撤消其子孙进程的 PCB结构和释放结构和释放它们所占有的资源。

它们所占有的资源撤消原语首先检查撤消原语首先检查 PCB进程链或进程家族，寻找所进程链或进程家族，寻找所要撤消的进程是否存在如果找到了所要撤消的进要撤消的进程是否存在如果找到了所要撤消的进程的程的 PCB结构，则撤消原语释放该进程所占有的资结构，则撤消原语释放该进程所占有的资源之后，把对应的源之后，把对应的 PCB结构从进程链或进程家族中结构从进程链或进程家族中摘下并返回给摘下并返回给 PCB空队列如果被撤消的进程有自空队列如果被撤消的进程有自己的子进程，则撤消原语先撤消其子进程的己的子进程，则撤消原语先撤消其子进程的 PCB结结构并释放子进程所占用的资源之后，再撤消当前进构并释放子进程所占用的资源之后，再撤消当前进程的程的 PCB结构和释放其资源结构和释放其资源趣炸喉殃窿窝歪夺蛛戮舵呼票廖嗓婆凝虑苞宝从连丙剥购窜膏麦违抹纠杜计算机操作系统第3章计算机操作系统第3章3.4.2 进程的阻塞与唤醒进程的阻塞与唤醒进程的创建原语和撤消原语完成了进程从无到有，从进程的创建原语和撤消原语完成了进程从无到有，从存在到消亡的变化被创建后的进程最初处于就绪存在到消亡的变化被创建后的进程最初处于就绪状态，然后经调度程序选中后进入执行状态。

这里状态，然后经调度程序选中后进入执行状态这里主要介绍实现进程的执行状态到等待状态，又由等主要介绍实现进程的执行状态到等待状态，又由等待状态到就绪状态转换的两种原语，即阻塞原语与待状态到就绪状态转换的两种原语，即阻塞原语与唤醒原语唤醒原语阻塞原语在一个进程期待某一事件发生，但发生条件阻塞原语在一个进程期待某一事件发生，但发生条件尚不具备时，被该进程自己调用来阻塞自己阻塞尚不具备时，被该进程自己调用来阻塞自己阻塞原语在阻塞一个进程时，由于该进程正处于执行状原语在阻塞一个进程时，由于该进程正处于执行状态，故应先中断处理机和保存该进程的态，故应先中断处理机和保存该进程的CPU现场然后将被阻塞进程置然后将被阻塞进程置“阻塞阻塞”状态后插入等待队列状态后插入等待队列中，再转进程调度程序选择新的就绪进程投入运行中，再转进程调度程序选择新的就绪进程投入运行阻塞原语的实现过程如图阻塞原语的实现过程如图滥足规盛吻港籍奄妒郝赠讹抛牲龙髓骏踢止蜗泉禹嘛栖各曾畴挛赴篙瘁庆计算机操作系统第3章计算机操作系统第3章这里，转进程调度程序是很重要的，否则，处理机将这里，转进程调度程序是很重要的，否则，处理机将会出现空转而浪费资源。

会出现空转而浪费资源阻塞原语图阻塞原语图趟垢帘甚疏雾猜锯啊涎辩素嵌蚂杯况抹尝瓤罚虎嚎鞭礼弦瑟驭吸屋蚀甜矣计算机操作系统第3章计算机操作系统第3章当等待队列中的进程所等待的事件发生时，等待该事当等待队列中的进程所等待的事件发生时，等待该事件的所有进程都将被唤醒唤醒一个进程有两种方件的所有进程都将被唤醒唤醒一个进程有两种方法：一种是由系统进程唤醒另一种是由事件发生法：一种是由系统进程唤醒另一种是由事件发生进程唤醒当由系统进程唤醒等待进程时，系统进进程唤醒当由系统进程唤醒等待进程时，系统进程统一控制事件的发生并将程统一控制事件的发生并将“事件发生事件发生”这一消息这一消息通知等待进程从而使得该进程因等待事件已发生通知等待进程从而使得该进程因等待事件已发生而进入就绪队列由事件发生进程唤醒时，事件发而进入就绪队列由事件发生进程唤醒时，事件发生进程和被唤醒进程之间是合作关系因此，唤醒生进程和被唤醒进程之间是合作关系因此，唤醒原语既可被系统进程调用，也可被事件发生进程调原语既可被系统进程调用，也可被事件发生进程调用称调用唤醒原语的进程为唤醒进程唤醒原语用称调用唤醒原语的进程为唤醒进程唤醒原语首先将被唤醒进程从相应的等待队列中摘下，将被首先将被唤醒进程从相应的等待队列中摘下，将被唤醒进程置为就绪状态之后，送入就绪队列。

在把唤醒进程置为就绪状态之后，送入就绪队列在把被唤醒进程送入就绪队列之后，唤醒原语既可以返被唤醒进程送入就绪队列之后，唤醒原语既可以返回原调用程序，也可以转向进程调度，以便让调度回原调用程序，也可以转向进程调度，以便让调度程序有机会选择一个合适的进程执行如图：程序有机会选择一个合适的进程执行如图：攫稽毫斥戌梗寐砒胸把眉疤棘蝴漱忌跺殖臼仁六话墟们虫拉牙报扬虱超表计算机操作系统第3章计算机操作系统第3章唤醒原语图唤醒原语图领溢懒泼滓舱纂勺绅姻潜穷蓑疽贤骄游獭渔版筏岛何场阀酶涵负袱灿驻茄计算机操作系统第3章计算机操作系统第3章3.5 进进 程程 互互 斥斥3.5.1 资源共享所引起的制约资源共享所引起的制约进程的并发执行不仅仅是用户程序的执行开始时间的进程的并发执行不仅仅是用户程序的执行开始时间的随机性和提高资源利用率的结果，也是资源有限性随机性和提高资源利用率的结果，也是资源有限性导致资源的竞争与共享对进程的执行过程进行制约导致资源的竞争与共享对进程的执行过程进行制约所造成的所造成的1. 临界区临界区在描述一个程序或算法时，总是认为存在一个伪处理在描述一个程序或算法时，总是认为存在一个伪处理机，可以按程序或算法所规定的步骤来执行该程序机，可以按程序或算法所规定的步骤来执行该程序或算法的。

但是，事实上，在实际的系统中则往往或算法的但是，事实上，在实际的系统中则往往不是这样一般说来，即使在程序中所描述的一条不是这样一般说来，即使在程序中所描述的一条语句，也是由多条执行指令构成的例如，各种程语句，也是由多条执行指令构成的例如，各种程序中经常出现的赋值语句：序中经常出现的赋值语句：X=X+1；；歌市窜条熏驼笨拼下姐砖查菏叙释苇论残凶诱矩拉窟刽埋诬舔努条灌疡姑计算机操作系统第3章计算机操作系统第3章在用汇编语言书写时，就变成：在用汇编语言书写时，就变成：LOADA，，XADDIA，，1STOREA，，X等三条语句，这里等三条语句，这里 A代表累加器根据系统的设计代表累加器根据系统的设计和要求，在这三条语句的执行期间，也有可能发生和要求，在这三条语句的执行期间，也有可能发生中断或调度，从而使得与当前进程无关的程序得以中断或调度，从而使得与当前进程无关的程序得以执行为了保证程序执行最终结果的正确性，必须执行为了保证程序执行最终结果的正确性，必须对并发执行的各进程进行制约，以控制它们的执行对并发执行的各进程进行制约，以控制它们的执行速度和对资源的竞争在进程的概念一节中已经介速度和对资源的竞争。

在进程的概念一节中已经介绍了进程中两相邻语句可并发执行的三个条件是绍了进程中两相邻语句可并发执行的三个条件是否有一种更为简单的办法来检查出需要对程序的哪否有一种更为简单的办法来检查出需要对程序的哪些部分进行制约才能保证其执行结果的正确性呢？些部分进行制约才能保证其执行结果的正确性呢？这里来看下面的例子这里来看下面的例子矩称害砍麻脚索举拂卷太霖躇绪酱托兢戊起惹略而寞陵跑闽们矢断伎禾夜计算机操作系统第3章计算机操作系统第3章设有两个计算进程Ｐ设有两个计算进程ＰA，Ｐ，ＰB共享内存Ｍ共享内存ＭS其中 ＭＭS分为三个领域，即系统区、进程工作区和数据区分为三个领域，即系统区、进程工作区和数据区这里数据区被划分大小相等的块，每个块中既可能这里数据区被划分大小相等的块，每个块中既可能放有数据，也有可能未放有数据系统区主要是堆放有数据，也有可能未放有数据系统区主要是堆栈Ｓ，其中存放那些空数据块的地址栈Ｓ，其中存放那些空数据块的地址多进程共享内存栈区示例图多进程共享内存栈区示例图憋拜吨绷畸桨招缠茫裤添苞啃骚偶丁琐俞奠塞钱纫蚕嫁僚逊帛哦效恨渣小计算机操作系统第3章计算机操作系统第3章当进程Ｐ当进程ＰA或Ｐ或ＰB要求空数据块时，从堆栈最顶部要求空数据块时，从堆栈最顶部（（top指针所指的位置）取出所需数据块。

当进程指针所指的位置）取出所需数据块当进程ＰＰA或Ｐ或ＰB释放数据块时，则把所释放数据块的地释放数据块时，则把所释放数据块的地址放入堆栈顶部令址放入堆栈顶部令getspace 为取空数据块过程，为取空数据块过程，release(ad)为释放数据块过程这里，为释放数据块过程这里，ad为待释放为待释放数据块的地址如果堆栈Ｓ非空的话，进程Ｐ数据块的地址如果堆栈Ｓ非空的话，进程ＰA或或ＰＰB是可以用任意的顺序释放和获取数据块的执是可以用任意的顺序释放和获取数据块的执行行getspace就是获取一个空数据块，而执行就是获取一个空数据块，而执行release(ad)就是释放一个地址为就是释放一个地址为ad的数据块然而，的数据块然而，由下面的描述可以看到，在进程并发执行时，由下面的描述可以看到，在进程并发执行时，getspace或或 release(ad)将有可能完不成所要求的功将有可能完不成所要求的功能getspace和和 release(ad)可进一步描述为：可进一步描述为：欣陇膳镶朗簇废郁服僧瞒沼哭应披臂桔体昂哎黔眼柄本访馒洁鹏岿庶腻凳计算机操作系统第3章计算机操作系统第3章getspace:begin local gg←stack ［［ top ］］top←top-1endrelease(ad):begin top ← top+1stack ［［ top ］］←adend设时刻设时刻t0时，时，top=h0，则，则getspace和和 release(ad)可能可能按以下顺序执行：按以下顺序执行：首先首先 release(ad)的第一句执行，的第一句执行，t0：：top ← top+1 →top=h0+1；；接着接着getspace 执行，得：执行，得：肯鹤席吟仲趴晨蒙戎也墨晦筹建丧朋酌冈怂钮糜皱荡惜恋均饮栈汾鸣须击计算机操作系统第3章计算机操作系统第3章t1：：g ← stack ［［top］］ → g=stack ［［ h0+1］；］；t2：：top ← top-1 → top=h0；；再是再是 release(ad)的第二句执行，得：的第二句执行，得：t3：：stack ［［top］］← ad → stack ［［ h0 ］］ ← ad；；其结果是调用其结果是调用getspace的进程取到的是的进程取到的是h0+1中的一个中的一个未定义值，而调用未定义值，而调用release(ad)的进程把所释放的空的进程把所释放的空块地址块地址ad重复放入了重复放入了h0中。

中怎样保证上述执行结果的正确性呢？怎样保证上述执行结果的正确性呢？ 一个较为明显一个较为明显的答案是，如果把的答案是，如果把getspace和和release(ad)抽象为两个抽象为两个各以一个动作完成的顺序执行单位，那么执行结果各以一个动作完成的顺序执行单位，那么执行结果的正确性是可以保证的的正确性是可以保证的策姐锄桶鳖它吨尿惫汕速阿六鲸仲光工侍药滋虏预狐弟耻诱遏固士函沁干计算机操作系统第3章计算机操作系统第3章把不允许多个并发进程交叉执行的一段程序称为临界把不允许多个并发进程交叉执行的一段程序称为临界部分（部分（critical section ）或临界区（）或临界区（critical region）临界区是由属于不同并发进程的程序段共享公用数据临界区是由属于不同并发进程的程序段共享公用数据或公用数据变量而引起的，例如上例中就是因为过或公用数据变量而引起的，例如上例中就是因为过程程 getspace 和和 release(ad)共同访问栈Ｓ中的数据而共同访问栈Ｓ中的数据而引起的临界区不可能用增加硬件的方法来解决临界区不可能用增加硬件的方法来解决因此，临界区也可以被称为访问公用数据的那段程因此，临界区也可以被称为访问公用数据的那段程序。

序渠同应苞划招它屯绣拙诉帕写性秧屿治粱埂停鳃弧咒相顷掘属网聊坚禾刺计算机操作系统第3章计算机操作系统第3章2. 间接制约间接制约一般来说，可以把那些不允许交叉执行的临界区按不一般来说，可以把那些不允许交叉执行的临界区按不同的公用数据划分为不同的集合上例中，以公用同的公用数据划分为不同的集合上例中，以公用数据栈Ｓ划分的临界区集合是数据栈Ｓ划分的临界区集合是{getspace,release}把这些集合称为类（把这些集合称为类（class）显然，对类给定一个）显然，对类给定一个唯一的标识名，系统就会容易地区分它们在程序唯一的标识名，系统就会容易地区分它们在程序的描述中，可用下列标准形式来描述临界区：的描述中，可用下列标准形式来描述临界区：when〈类名〉〈类名〉do〈临界区〉〈临界区〉od设类设类 {getspace，，release} 的类名为的类名为sp，则，则getspace和和release(ad)可重新描述为：可重新描述为：getspace: when sp do getspce←stack ［［ top ］］top←top-1 odrelease(ad): when sp do top← top+1stack ［［ top ］］ ← ad od弓糯盘轨作嚏吭咯镰芝陇旦涡疡衰伟秧雾纷但旁毅俘捧椎含忙状八拢赡代计算机操作系统第3章计算机操作系统第3章把这种由于共享某一公有资源而引起的在临界区内不把这种由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称为由共享公有资允许并发进程交叉执行的现象，称为由共享公有资源而造成的对并发进程执行速度的间接制约，简称源而造成的对并发进程执行速度的间接制约，简称间接制约。

这里，间接制约这里，“间接间接”二字主要是指各并发进二字主要是指各并发进程的速度受公有资源制约，而不是进程间直接制约程的速度受公有资源制约，而不是进程间直接制约的意思这里，受间接制约的类中各程序段在执行顺序上是任这里，受间接制约的类中各程序段在执行顺序上是任意的显然，对于每一类，系统应有相应的分配和释放相应显然，对于每一类，系统应有相应的分配和释放相应公有资源的管理办法，以制约并发进程这就是互公有资源的管理办法，以制约并发进程这就是互斥酚宰献择嘴镊度蚤著姨陷书杏绣传冒柳妮阐雌计递僻沧裴测霓对耶胃媳汪计算机操作系统第3章计算机操作系统第3章3. 什么是互斥什么是互斥可以把互斥定义为：一组并发进程中的一个或多个程可以把互斥定义为：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行也就是说，不允许两不允许交叉执行的单位执行也就是说，不允许两个以上的共享该资源的并发进程同时进入临界区称个以上的共享该资源的并发进程同时进入临界区称为互斥这里，考虑类中只有一个元素，也就是只有一个程序这里，考虑类中只有一个元素，也就是只有一个程序段的情况是很有意思的。

这时程序段本身为公有资段的情况是很有意思的这时程序段本身为公有资源被并发进程共享一般情况下，作为程序段的一源被并发进程共享一般情况下，作为程序段的一个过程不允许多个进程共同访问它但如果该过程个过程不允许多个进程共同访问它但如果该过程是纯过程，则各并发进程可以同时访问它纯过程是纯过程，则各并发进程可以同时访问它纯过程是指在执行过程中不改变过程自身代码的一类过程是指在执行过程中不改变过程自身代码的一类过程纠枚怨恕型的模哥枚肥标书嘻硒格拳矢旱穷驶抓窑年别浴握谆沿算满瞄消计算机操作系统第3章计算机操作系统第3章通常，在计算机系统中，有许多过程是被多个并发进通常，在计算机系统中，有许多过程是被多个并发进程同时访问共享，例如编辑程序、编译程序等把程同时访问共享，例如编辑程序、编译程序等把一个过程作成纯过程可便于多个进程共享，但由于一个过程作成纯过程可便于多个进程共享，但由于编制纯过程必须对有关变量和工作区作相应的处理，编制纯过程必须对有关变量和工作区作相应的处理，从而其执行效率往往会受到一定的影响从而其执行效率往往会受到一定的影响一组并发进程互斥执行时必须满足如下准则：一组并发进程互斥执行时必须满足如下准则：(1) 不能假设各并发进程的相对执行速度。

即各并发不能假设各并发进程的相对执行速度即各并发进程享有平等的、独立的竞争共有资源的权利，且进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任一指令在不采取任何措施的条件下，在临界区内任一指令结束时，其他并发进程可以进入临界区结束时，其他并发进程可以进入临界区2) 并发进程中的某个进程不在临界区时，它不阻止并发进程中的某个进程不在临界区时，它不阻止其他进程进入临界区其他进程进入临界区3) 并发进程中的若干个进程申请进入临界区时，只并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入能允许一个进程进入选毯巍掇砌漫咱糊狰按厂的泪朋句系滚费茶橱勋专扬圣挛罢呜谊依舀录硷计算机操作系统第3章计算机操作系统第3章(4) 并发进程中的某个进程申请进入临界区时开始，并发进程中的某个进程申请进入临界区时开始，应在有限时间内得以进入临界区应在有限时间内得以进入临界区这里，准则这里，准则(1)，，(2)，，(3)是保证各并发进程享有平是保证各并发进程享有平等的、独立的竞争和使用公有资源的权利，且保证等的、独立的竞争和使用公有资源的权利，且保证每一时刻至多只有一个进程在临界区。

而准则每一时刻至多只有一个进程在临界区而准则(4)则是并发进程不发生死锁（将在后面讲述）的重要则是并发进程不发生死锁（将在后面讲述）的重要保证否则，由于某个并发进程长期占有临界区，保证否则，由于某个并发进程长期占有临界区，其他进程则因为不能进入临界区而进入互相等待状其他进程则因为不能进入临界区而进入互相等待状态在一组并发执行进程中，除了因为竞争公有资源而引在一组并发执行进程中，除了因为竞争公有资源而引起的间接制约带来进程之间互斥之外，还存在有因起的间接制约带来进程之间互斥之外，还存在有因为并发进程互相共享对方的私有资源所引起的直接为并发进程互相共享对方的私有资源所引起的直接制约直接制约将使得各并发进程同步执行下面，制约直接制约将使得各并发进程同步执行下面，将讨论互斥的实现方法将讨论互斥的实现方法捶汀伶员雪君拨胖拔莉硕罗鼻舒印略邪仲尺茹丘锑刽屉霞颤沂掉烯郑潮伙计算机操作系统第3章计算机操作系统第3章3.5.2 互斥的加锁实现互斥的加锁实现上节中，给出了临界区的描述方法和并发进程互斥执上节中，给出了临界区的描述方法和并发进程互斥执行时所必要遵守的准则但是，并没有给出怎样实行时所必要遵守的准则。

但是，并没有给出怎样实现并发进程的互斥人们可能认为只需把临界区中现并发进程的互斥人们可能认为只需把临界区中的各个过程按不同的时间排列调用就行了但事实的各个过程按不同的时间排列调用就行了但事实上这是不可能的因为这要求该组并发进程中的每上这是不可能的因为这要求该组并发进程中的每个进程事先知道其他并发进程与系统的动作，由用个进程事先知道其他并发进程与系统的动作，由用户程序执行开始的随机性可知，这是不可能的户程序执行开始的随机性可知，这是不可能的一种可能的办法是对临界区加锁以实现互斥当某个一种可能的办法是对临界区加锁以实现互斥当某个进程进入临界区之后，它将锁上临界区，直到它退进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止并发进程在申请进入临界区时，出临界区时为止并发进程在申请进入临界区时，首先测试该临界区是否是上锁的如果该临界区已首先测试该临界区是否是上锁的如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可被锁住，则该进程要等到该临界区开锁之后才有可能获得临界区能获得临界区身扶躇昧愉获年廉恬召瘴嗣皑玄俗绕企鼻屉恬袖钞都俊曙蕉贯赢错英滴始计算机操作系统第3章计算机操作系统第3章设临界区的类名为Ｓ。

为了保证每一次临界区中只能设临界区的类名为Ｓ为了保证每一次临界区中只能有一个程序段被执行，又设锁定位有一个程序段被执行，又设锁定位 key［Ｓ］［Ｓ］ key［Ｓ］表示该锁定位属于类名为Ｓ的临界区［Ｓ］表示该锁定位属于类名为Ｓ的临界区加锁后的临界区程序描述如下：加锁后的临界区程序描述如下：lock(key ［Ｓ］［Ｓ］)〈临〈临 界界 区〉区〉unlock(key ［Ｓ］［Ｓ］)设设key ［Ｓ］［Ｓ］=1时表示类名为Ｓ的临界区可用，时表示类名为Ｓ的临界区可用，key ［Ｓ］［Ｓ］=0时表示类名为Ｓ的临界区不可用则，时表示类名为Ｓ的临界区不可用则，unlock(key ［Ｓ］［Ｓ］)只用一条语句即可实现即：只用一条语句即可实现即：key ［Ｓ］［Ｓ］←1不过，由于不过，由于lock(key ［Ｓ］［Ｓ］)必须满足必须满足key ［Ｓ］［Ｓ］=0时，不允许任何进程进入临界区，而时，不允许任何进程进入临界区，而key ［Ｓ］［Ｓ］=1时仅允许一个进程进入临界区的准则，因而实现起时仅允许一个进程进入临界区的准则，因而实现起来较为困难来较为困难臭卉廷瘤定戏坑稿遂今号扼尊货葬屠察惫租狠咳帛赞巫劝伎奠便颓绅陀巴计算机操作系统第3章计算机操作系统第3章一种简便的实现方法是：一种简便的实现方法是：lock (x)=begin local vrepeatv←xuntilv=1x←0end这种实现方法是不能保证并发进程互斥执行所要求的这种实现方法是不能保证并发进程互斥执行所要求的准则准则(3)的。

因为当同时有几个进程调用的因为当同时有几个进程调用lock(key ［Ｓ］［Ｓ］)时，在时，在x←0语句执行之前，可能已有两个语句执行之前，可能已有两个以上的多个进程由于以上的多个进程由于key ［Ｓ］［Ｓ］=1而进入临界区而进入临界区为解决这个问题有些机器在硬件中设置了为解决这个问题有些机器在硬件中设置了“测试与测试与设置指令，保证第一步和第二步执行不可分离设置指令，保证第一步和第二步执行不可分离注意：在系统实现时锁定位注意：在系统实现时锁定位key ［Ｓ］总是设置在公［Ｓ］总是设置在公有资源所对应的数据结构中的有资源所对应的数据结构中的舅坟铭望赔吗肌掷点绘厩饭瘟抛成则蕾纤帽侈谅纤匠垮辆蹋购锄瑚挟廉要计算机操作系统第3章计算机操作系统第3章3.5.3 信号量和Ｐ，Ｖ原语信号量和Ｐ，Ｖ原语1. 信号量（信号量（semaphore））尽管用加锁的方法可以实现进程之间的互斥，但这种尽管用加锁的方法可以实现进程之间的互斥，但这种方法仍然存在一些影响系统可靠性和执行效率的问方法仍然存在一些影响系统可靠性和执行效率的问题例如，循环测试锁定位将损耗较多的题例如，循环测试锁定位将损耗较多的 CPU计计算时间。

如果一组并发进程的进程数较多，且由于算时间如果一组并发进程的进程数较多，且由于每个进程在申请进入临界区时都得对锁定位进行测每个进程在申请进入临界区时都得对锁定位进行测试，这种开销是很大的试，这种开销是很大的另外，使用加锁法实现进程间互斥时，还将导致在某另外，使用加锁法实现进程间互斥时，还将导致在某些情况下出现不公平现象试考虑以下进程些情况下出现不公平现象试考虑以下进程PA和和PB反复使用临界区的情况：反复使用临界区的情况：PAA：：lock(key［Ｓ］［Ｓ］)〈Ｓ〉〈Ｓ〉县龄秆饮容肌孺灾蛛店腕僧鸟吩均讣绵淑芜坯骆镭蜘揭案奋癌亏只嘎浇揉计算机操作系统第3章计算机操作系统第3章unlock(key［Ｓ］［Ｓ］)Goto APBB：：lock(key ［Ｓ］［Ｓ］)＜Ｓ＞＜Ｓ＞unlock(key ［Ｓ］［Ｓ］)Goto B设进程Ｐ设进程ＰA已通过已通过lock(key ［Ｓ］［Ｓ］)过程而进入临界过程而进入临界区显然，在进程区显然，在进程PA执行执行unlock(key ［Ｓ］［Ｓ］)过程过程之前，之前，key ［Ｓ］［Ｓ］=0且进程且进程PB没有进入临界区的机没有进入临界区的机会然而，当进程会。

然而，当进程PA执行完执行完unlock(key ［Ｓ］［Ｓ］)过过程之后，由于紧接着是一转向语句，进程程之后，由于紧接着是一转向语句，进程PA将又将又立即去执行立即去执行lock(key ［Ｓ］［Ｓ］)过程愧涅潮屑旱烬陇非呸弄呜磺煎衔卤钱垫幅婆溜卖娟纹馒挫燕窝灶瞳闪烤雪计算机操作系统第3章计算机操作系统第3章此时，由于此时，由于unlock(key［Ｓ］［Ｓ］)过程已将过程已将key［Ｓ］的［Ｓ］的值置为值置为1，也就是开锁状态，从而进程，也就是开锁状态，从而进程PA又可进入又可进入临界区Ｓ只有在进程临界区Ｓ只有在进程PA执行完执行完unlock(key［Ｓ］［Ｓ］)过程之后、执行过程之后、执行Goto A语句之前的瞬间发生进程语句之前的瞬间发生进程调度，使进程调度，使进程PA把处理机转让给进程把处理机转让给进程PB，进程，进程PB才有可能得到执行然而遗憾的是，这种可能性是才有可能得到执行然而遗憾的是，这种可能性是非常小的因此，进程非常小的因此，进程PB将处于永久饥饿状态将处于永久饥饿状态（（starvation）解决上述问题首先必须找到产生问题的原因显然，解决上述问题首先必须找到产生问题的原因。

显然，在用加锁法解决进程互斥的问题时，一个进程能否在用加锁法解决进程互斥的问题时，一个进程能否进入临界区是依靠进程自己调用进入临界区是依靠进程自己调用lock过程去测试相过程去测试相应的锁定位每个进程能否进入临界区是依靠自己应的锁定位每个进程能否进入临界区是依靠自己的测试判断这样没有获得执行机会的进程当然无的测试判断这样没有获得执行机会的进程当然无法判断，从而出现不公平现象而获得了测试机会法判断，从而出现不公平现象而获得了测试机会的进程又因需要测试而损失一定的的进程又因需要测试而损失一定的CPU 时间刹唁曳旬镐沈感术吼哭决扣辛柑酮镰被底沛豺轴楼谣榷骆苍粘湾隙有澳阔计算机操作系统第3章计算机操作系统第3章这正如某个学生想使用某个人人都可借用、且不规定这正如某个学生想使用某个人人都可借用、且不规定使用时间的教室时一样，他必须首先申请获得使用使用时间的教室时一样，他必须首先申请获得使用该教室的权利，然后再到教室看看该教室是不是被该教室的权利，然后再到教室看看该教室是不是被锁上了如果该教室被锁上了，他只好下次再来观锁上了如果该教室被锁上了，他只好下次再来观察，看该教室的门是否已被打开这种反复将持续察，看该教室的门是否已被打开。

这种反复将持续到他进门后为止从这个例子中，可以得到解决加到他进门后为止从这个例子中，可以得到解决加锁法所带来的问题的方法一种最直观的办法是，锁法所带来的问题的方法一种最直观的办法是，设置一个教室管理员从而，如果有学生申请使用设置一个教室管理员从而，如果有学生申请使用教室而未能如愿时，教室管理员记下他的名字，并教室而未能如愿时，教室管理员记下他的名字，并等到教室门一打开则通知该学生进入这样，既减等到教室门一打开则通知该学生进入这样，既减少了学生多次来去教室检查门是否被打开的时间，少了学生多次来去教室检查门是否被打开的时间，又减少了因为学生自发地检查造成的不公平现象又减少了因为学生自发地检查造成的不公平现象在操作系统中，这个管理员就是信号量信号量管在操作系统中，这个管理员就是信号量信号量管理相应临界区的公有资源，它代表可用资源实体理相应临界区的公有资源，它代表可用资源实体谎轩鲸疽窝诉晾伍妄啊棒格湃峡阎炎宦瘟罐遗吭锨魔凰卢韦酒撑见岿唬舜计算机操作系统第3章计算机操作系统第3章信号量的概念和下面所述的Ｐ、Ｖ原语是荷兰科学家信号量的概念和下面所述的Ｐ、Ｖ原语是荷兰科学家E.W.Dijkstra提出来的。

信号是铁路交通管理中的提出来的信号是铁路交通管理中的一种常用设备，交通管理人员利用信号颜色的变化一种常用设备，交通管理人员利用信号颜色的变化来实现交通管理在操作系统中，信号量来实现交通管理在操作系统中，信号量sem是一是一整数在sem大于等于零时代表可供并发进程使用大于等于零时代表可供并发进程使用的资源实体数，但的资源实体数，但sem小于零时则表示正在等待使小于零时则表示正在等待使用临界区的进程数显然，用于互斥的信号量用临界区的进程数显然，用于互斥的信号量sem的初值应该大于零，而建立一个信号量必须经过说的初值应该大于零，而建立一个信号量必须经过说明所建信号量所代表的意义，和赋初值以及建立相明所建信号量所代表的意义，和赋初值以及建立相应的数据结构以便指向那些等待使用该临界区的进应的数据结构以便指向那些等待使用该临界区的进程双卡魄农篡任措疚悼义响阁耗焙壶陈抑团顺应青甄腺阂洒悬氟荔有胁亢胁计算机操作系统第3章计算机操作系统第3章2. Ｐ，Ｖ原语Ｐ，Ｖ原语信号量的数值仅能由Ｐ，Ｖ原语操作改变信号量的数值仅能由Ｐ，Ｖ原语操作改变(Ｐ和Ｖ分Ｐ和Ｖ分别是荷兰语别是荷兰语 Passeren 和和Verhoog 的头一个字母，相的头一个字母，相当于英文的当于英文的pass和和increment的意思的意思)。

采用Ｐ，Ｖ采用Ｐ，Ｖ原语，可以把类名为Ｓ的临界区描述为原语，可以把类名为Ｓ的临界区描述为When ＳＳ do ＰＰ(sem)临界区Ｖ临界区Ｖ(sem)od这里，这里，sem是与临界区内所使用的公用资源有关的信是与临界区内所使用的公用资源有关的信号量一次Ｐ原语操作使得信号量号量一次Ｐ原语操作使得信号量sem减减1，而一次，而一次Ｖ原语操作将使得信号量Ｖ原语操作将使得信号量sem加加1必须强调的一点必须强调的一点是，当某个进程正在临界区内执行时，其他进程如是，当某个进程正在临界区内执行时，其他进程如果执行了Ｐ原语操作，则该进程并不像调用果执行了Ｐ原语操作，则该进程并不像调用lock时时那样因进不了临界区而返回到那样因进不了临界区而返回到lock的起点，等以后的起点，等以后重新执行测试，而是在等待队列中等待有其他进程重新执行测试，而是在等待队列中等待有其他进程做Ｖ原语操作释放资源后，进入临界区，这时，Ｐ做Ｖ原语操作释放资源后，进入临界区，这时，Ｐ原语的执行才算真正结束原语的执行才算真正结束殴仍阐续领惮油尺葱柿传扶恶谋库司益敢揍罗大拍屑叭喇瞅韧踩炽看论沛计算机操作系统第3章计算机操作系统第3章另外，当有好几个进程执行Ｐ原语未通过而进入等待另外，当有好几个进程执行Ｐ原语未通过而进入等待状态之后，如有某进程作了Ｖ原语操作，则等待进状态之后，如有某进程作了Ｖ原语操作，则等待进程中的一个可以进入临界区，但其他进程必须等待。

程中的一个可以进入临界区，但其他进程必须等待Ｐ原语操作的主要动作是：Ｐ原语操作的主要动作是：(1) sem减减 1；；(2) 若若sem减减1后仍大于或等于零，则进程继续执行；后仍大于或等于零，则进程继续执行；(3) 若若sem减减1后小于零，则该进程被阻塞后与该信后小于零，则该进程被阻塞后与该信号相对应的队列中，然后转进程调度号相对应的队列中，然后转进程调度Ｐ原语操作的功能框图如图Ｐ原语操作的功能框图如图3.11搭涵褐伺薄狗庆瞅穴胃软四孰禄焦肺诫糊膀娥骡汹诡押妊灸壹到掉绿雌标计算机操作系统第3章计算机操作系统第3章图图3.11 Ｐ原语操作功能Ｐ原语操作功能图图 3.12Ｖ原语操作功能Ｖ原语操作功能戌与弄妖憎削专叼直暑皂嗓竖耶棱艇圣邢榨托誓蛮拇鸡哇镍偷隐瘩簇恒频计算机操作系统第3章计算机操作系统第3章Ｖ原语的操作主要动作是：Ｖ原语的操作主要动作是：(1) sem加加1；；(2) 若相加结果大于零，进程继续执行；若相加结果大于零，进程继续执行；(3) 若相加结果小于或等于零，则从该信号的等待队若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。

或转进程调度Ｖ原语操作的功能框图如图Ｖ原语操作的功能框图如图3.12有了加锁法的基础，大家应该明白为什么Ｐ，Ｖ过程有了加锁法的基础，大家应该明白为什么Ｐ，Ｖ过程要以原语实现的原因否则，如果多个进程同时调要以原语实现的原因否则，如果多个进程同时调用Ｐ操作或Ｖ操作的话，则有可能在Ｐ操作刚把用Ｐ操作或Ｖ操作的话，则有可能在Ｐ操作刚把sem-1而未把对应进程送入等待队列时，Ｖ操作开而未把对应进程送入等待队列时，Ｖ操作开始执行从而，Ｖ操作将无法发现等待进程而返回从而，Ｖ操作将无法发现等待进程而返回因此，Ｐ，Ｖ操作都必须以原语实现，且在Ｐ，Ｖ因此，Ｐ，Ｖ操作都必须以原语实现，且在Ｐ，Ｖ原语执行期间不允许中断发生原语执行期间不允许中断发生蜂葫狠怎炉兑踞潘呻侩冯绞俄咖窄蝴蟹挽漳溪腾米怖缮竭炙缄迸匡翁吼志计算机操作系统第3章计算机操作系统第3章关于Ｐ，Ｖ原语的实现，有许多方法这里介绍一种关于Ｐ，Ｖ原语的实现，有许多方法这里介绍一种使用加锁法的软件实现方法，实现过程描述如下：使用加锁法的软件实现方法，实现过程描述如下：Ｐ（Ｐ（sem）：）：begin封锁中断；封锁中断；lock(lockbit)val［［sem］］=val［［sem］］-1if val［［sem］］<0保护当前进程保护当前进程CPU现场现场当前进程状态置为当前进程状态置为″等待等待″将当前进程插入信号将当前进程插入信号sem等待队列等待队列转进程调度转进程调度fiunlock(lockbit)；开放中断；开放中断end哟同斟墓敖持肩匡氟凸鹅散仿阔瓤羊砂损刃泌躲立掏驰柳痪充氮沏肇记舍计算机操作系统第3章计算机操作系统第3章Ｖ（Ｖ（sem）：）：begin封锁中断；封锁中断；lock(lockbit)va［［sem］］=val［［sem］］+1if val［［sem］］≤0localk从从sem等待队列中选取一等待进程，将其等待队列中选取一等待进程，将其指针置入指针置入k中中将将k插入就绪队列插入就绪队列进程状态置进程状态置“就绪就绪”fiunlock(lockbit)；开放中断；开放中断end碌辕惨膏颅刺拒间浑枢毖硒白祸囚肩茬盼气器藤邀柔枉看夹忘生漫滴咕匙计算机操作系统第3章计算机操作系统第3章3.5.4 用Ｐ，Ｖ原语实现进程互斥用Ｐ，Ｖ原语实现进程互斥利用Ｐ，Ｖ原语和信号量，可以方便地解决并发进程利用Ｐ，Ｖ原语和信号量，可以方便地解决并发进程的互斥问题，而且不会产生使用加锁法解决互斥问的互斥问题，而且不会产生使用加锁法解决互斥问题时所出现的问题。

题时所出现的问题设信号量设信号量sem是用于互斥的信号量，且其初值为是用于互斥的信号量，且其初值为1表表示没有并发进程使用该临界区显然，由上面几节示没有并发进程使用该临界区显然，由上面几节的讨论可知，只要把临界区置于Ｐ的讨论可知，只要把临界区置于Ｐ(sem)和Ｖ和Ｖ(sem)之间，即可实现进程间的互斥当一个进程想要进之间，即可实现进程间的互斥当一个进程想要进入临界区时，它必须先执行Ｐ原语操作以将信号量入临界区时，它必须先执行Ｐ原语操作以将信号量sem减减1在一个进程完成对临界区的操作之后，它在一个进程完成对临界区的操作之后，它必须执行Ｖ原语操作以释放它所占用的临界区由必须执行Ｖ原语操作以释放它所占用的临界区由于信号量初始值为于信号量初始值为 1，所以，任一进程在执行Ｐ原，所以，任一进程在执行Ｐ原语操作之后将语操作之后将sem的值变为的值变为0，表示该进程可以进入，表示该进程可以进入临界区崖抠筹读规质遂伎涯拿庆砖簇闭惜似墓蹈划颜丙骸按恨薯沈绣祝窘孟馅票计算机操作系统第3章计算机操作系统第3章在该进程未执行Ｖ原语操作之前如有另一进程想进入在该进程未执行Ｖ原语操作之前如有另一进程想进入临界区的话，它也应先执行临界区的话，它也应先执行 ＰＰ 原语操作，从而使原语操作，从而使sem 的值变为的值变为-1，因此，第二个进程将被阻塞。

直，因此，第二个进程将被阻塞直到第一个进程执行Ｖ原语操作之后，到第一个进程执行Ｖ原语操作之后，sem 的值变为的值变为0，从而可唤醒第二个进程进入就绪队列，经调度，从而可唤醒第二个进程进入就绪队列，经调度后再进入临界区在第二个进程执行完Ｖ原语操作后再进入临界区在第二个进程执行完Ｖ原语操作之后，如果没有其他进程申请进入临界区的话，则之后，如果没有其他进程申请进入临界区的话，则sem 又恢复到初始值又恢复到初始值用信号量实现两并发进程用信号量实现两并发进程PA，，PB互斥的描述如下：互斥的描述如下：1) 设设 sem为互斥信号量，其取值范围为为互斥信号量，其取值范围为(1,0,-1)其中其中sem=1表示进程表示进程PA和和PB都未进入类名为Ｓ的临都未进入类名为Ｓ的临界区，界区，sem=0表示进程表示进程PA或或PB已进入类名为Ｓ的已进入类名为Ｓ的临界区，临界区，sem=-1表示进程表示进程PA和和PB中，一个进程已中，一个进程已进入临界区，而另一个进程等待进入临界区进入临界区，而另一个进程等待进入临界区仓涨失扁披桔毗初寂育李顷韩育衫稳扩丈厚字矽拣磕妹肛度妥畏桩嫡伐驳计算机操作系统第3章计算机操作系统第3章2) 描述：描述：PA：：ＰＰ(sem)〈Ｓ〉〈Ｓ〉ＶＶ(sem)：：：：：： PB：：ＰＰ(sem)〈Ｓ〉〈Ｓ〉ＶＶ(sem)∷ ∷：：：：铬甘鞭商炕竿溺眶妊违读祟姐卢躺冷营上顶颊咒八净投喂者虎柴概蠢秆忘计算机操作系统第3章计算机操作系统第3章吸晤祸婿楼挎倦皮殃爸叠霸诊如羚越褪绕泼酉冲有新呛民摆烃堕侄犹讥娩计算机操作系统第3章计算机操作系统第3章3.6 进进 程程 同同 步步3.6.1 同步的概念同步的概念除了对公有资源的竞争而引起的间接制约之外，并发除了对公有资源的竞争而引起的间接制约之外，并发进程之间是否还存在着其他制约关系影响执行速度进程之间是否还存在着其他制约关系影响执行速度呢？来看下面的例子。

呢？来看下面的例子计算进程和打印进程共同使用同一缓冲区计算进程和打印进程共同使用同一缓冲区Buf计算进程反复地把每次计算结果放入进程反复地把每次计算结果放入 Buf中，而打印进中，而打印进程则把计算进程每次放入程则把计算进程每次放入 Buf中的数据通过打印机中的数据通过打印机打印输出如果不采取任何制约措施，这两个进程打印输出如果不采取任何制约措施，这两个进程的执行起始时间和执行速度都是彼此独立的，其相的执行起始时间和执行速度都是彼此独立的，其相应的控制段可以描述为：应的控制段可以描述为：蚁瞧呆陶反呈椒楼值剿苗馏标魂正舅芝求死呆排篓遮劈驭君都矛蹭究蛆却计算机操作系统第3章计算机操作系统第3章PAPA：：: :A:A: local Buflocal BufRepeatRepeatBuf← BufBuf← BufUntilUntilBuf=Buf=空空计算计算得到计算结果得到计算结果Buf ← Buf ← 计算结果计算结果GotoGoto A APB:PB:：：: : B: B:local Prilocal PriRepeatRepeat Pri ← Buf Pri ← BufUntilUntilPri ≠ Pri ≠ 空空 打印打印 Buf Buf中的数据中的数据 清除清除 Buf Buf中的数据中的数据GotoGoto B B衍没守据程冤毫丈壕殷让秽铺旋朱毁喂菇蹈祭体鱼科雁硒不虫峭届筒蚊始计算机操作系统第3章计算机操作系统第3章这里，如果假定进程这里，如果假定进程PC和和PP对公用缓冲区对公用缓冲区Buf 已采已采取了互斥措施。

取了互斥措施显然，如果按上面的描述并发执行进程显然，如果按上面的描述并发执行进程PA和和PB的话，的话，则会造成则会造成CPU时间的极大浪费（因为其中包含有二时间的极大浪费（因为其中包含有二处反复测试语句）这是操作系统设计要求不允许处反复测试语句）这是操作系统设计要求不允许的CPU 时间的浪费主要是由于进程时间的浪费主要是由于进程PA和和PB的执的执行互相制约所引起的行互相制约所引起的PA的输出结果是的输出结果是PB的执行的执行条件，反过来，条件，反过来，PB的执行结果也是的执行结果也是PA的执行条件的执行条件这种现象在操作系统和用户进程中大量存在这与这种现象在操作系统和用户进程中大量存在这与上节中讲述的进程互斥是不同的，进程互斥时它们上节中讲述的进程互斥是不同的，进程互斥时它们的执行顺序可以是任意的一组在异步环境下的并的执行顺序可以是任意的一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的而限制各进程的执行速度的过程称为并发进程间的直接制约直接制约毒健摧弧紫遏秘化全袱汀模疏掷沫评藏纽拆乾搔恢柒卒淖妻盾瓢薪铰他抿计算机操作系统第3章计算机操作系统第3章这里异步环境主要指各并发进程的执行起始时间的随这里异步环境主要指各并发进程的执行起始时间的随机性和执行速度的独立性。

正如在上面例子中所看机性和执行速度的独立性正如在上面例子中所看到的那样，如果没有相应的解决方法，进程的直接到的那样，如果没有相应的解决方法，进程的直接制约将会造成大量的制约将会造成大量的CPU时间浪费一种最为简单时间浪费一种最为简单和直观的方法是直接制约的进程互相给对方进程发和直观的方法是直接制约的进程互相给对方进程发送执行条件已经具备的信号这样，被制约进程即送执行条件已经具备的信号这样，被制约进程即可省去对执行条件的测试，只要收到了制约进程发可省去对执行条件的测试，只要收到了制约进程发来的信号便开始执行，而在未收到制约进程发来的来的信号便开始执行，而在未收到制约进程发来的信号时便进入等待状态信号时便进入等待状态诛阳卜酬末苦往曼未养砌啡泵鸿姆拎魄孺要撕秒郸贵榴颐俏嫡激扇裔志汉计算机操作系统第3章计算机操作系统第3章把异步环境下的一组并发进程，因直接制约而互相发把异步环境下的一组并发进程，因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步具有同一定的速度执行的过程称为进程间的同步具有同步关系的一组并发进程称为合作进程，合作进程间步关系的一组并发进程称为合作进程，合作进程间互相发送的信号称为消息或事件。

如果对一个消息互相发送的信号称为消息或事件如果对一个消息或事件赋以唯一的消息名，则可用过程或事件赋以唯一的消息名，则可用过程wait(消息名）消息名）表示进程等待合作进程发来的消息，而用过程表示进程等待合作进程发来的消息，而用过程signal（消息名）（消息名）表示向合作进程发送消息利用过程表示向合作进程发送消息利用过程wait和和signal，，可以简单地描述上面例子中的计算进程可以简单地描述上面例子中的计算进程PA和打印和打印进程进程PB的同步关系如下：的同步关系如下：输淳戒崔恼陵维矾涨援生拧醋呈耿徊尿姥维怒葫自匆阂广沃垃摄帆风蛇老计算机操作系统第3章计算机操作系统第3章(1) 设消息名设消息名Bufempty表示表示Buf空，消息名空，消息名Buffull表表示示Buf中装满了数据中装满了数据2) 初始化初始化Bufempty=true，，Buffull=false 3) 描述：描述：PA：：A:wait(Bufempty)计算计算Buf ← 计算结果计算结果signal(Buffull)Goto A汗乎踢宽雨鱼蛀迂贾赣哄掀广睫蚤呢奈简耗兄践僳锅偷岗搂麦挂埋盛藉营计算机操作系统第3章计算机操作系统第3章PB：：B:wait(Buffull)打印打印Buf中的数据中的数据清除清除Buf中的数据中的数据signal(Bufempty)Goto B过程过程wait的功能是等待到消息名为的功能是等待到消息名为true的进程继续执的进程继续执行，而行，而signal的功能则是向合作进程发送合作进程的功能则是向合作进程发送合作进程所需要的消息名，并将其值置为所需要的消息名，并将其值置为true。

唤肺桑槛诬妇卑毒脂辆忌递弘壳屉关藏谨头瞥灰碱树镁寺贝恢橡酚柜肾更计算机操作系统第3章计算机操作系统第3章3.6.2 私用信号量私用信号量上面用上面用wait（消息名）与（消息名）与signal（消息名）的方式，（消息名）的方式，描述了进程同步的一种实现方法事实上，使用描述了进程同步的一种实现方法事实上，使用 信信号量的方法也可实现进程间的同步号量的方法也可实现进程间的同步一般来说，也可以把各进程之间发送的消息作为信号一般来说，也可以把各进程之间发送的消息作为信号量看待与进程互斥时不同的是，这里的信号量只量看待与进程互斥时不同的是，这里的信号量只与制约进程及被制约进程有关而不是与整组并发进与制约进程及被制约进程有关而不是与整组并发进程有关因此，称该信号量为私用信号量（程有关因此，称该信号量为私用信号量（Private Semaphvre）一个进程）一个进程Pi的私用信号量的私用信号量Semi是从是从制约进程发送来的进程制约进程发送来的进程Pi的执行条件所需要的消息的执行条件所需要的消息与私用信号量相对应，称互斥时使用的信号量为公与私用信号量相对应，称互斥时使用的信号量为公用信号量用信号量。

儡核懈棋品彪到拙花兔停晃邢痛般颇祭溃嗓檬暇师琵舔捧普佛鼓疥衫穆甜计算机操作系统第3章计算机操作系统第3章3.6.3 用Ｐ，Ｖ原语操作实现同步用Ｐ，Ｖ原语操作实现同步有了私用信号量的概念，可以使用Ｐ，Ｖ原语操作实有了私用信号量的概念，可以使用Ｐ，Ｖ原语操作实现进程间的同步利用Ｐ，Ｖ原语实现进程同步的现进程间的同步利用Ｐ，Ｖ原语实现进程同步的方法与利用方法与利用wait和和signal过程时相同，也是分为三过程时相同，也是分为三步首先为各并发进程设置私用信号量，然后为私步首先为各并发进程设置私用信号量，然后为私用信号量赋初值，最后利用Ｐ，Ｖ原语和私用信号用信号量赋初值，最后利用Ｐ，Ｖ原语和私用信号量规定各进程的执行顺序量规定各进程的执行顺序缓冲区队列图缓冲区队列图瘦秒欲斯羌巧径疹误诗耽吠触蓑刊丈琼旷镊渍附拄弘蔼绎栖粟宿痢孙侯疑计算机操作系统第3章计算机操作系统第3章初值初值a=1，表示，表示BUF为空；为空；b=0表示表示BUF为非满PA:L: P(a) 计算；计算； 计算结果计算结果 BUF V(b)Goto L;PB:L: P(b) 计算；计算； BUF 打印打印 V(a)Goto L;阐傻浅你蔽该饺霞尸懊确棉疮止板止兔拒臃房揣跌忠雍砚笑纷宇漫成构叹计算机操作系统第3章计算机操作系统第3章例：设进程例：设进程PA和和PB通过缓冲区队列传递数据（如图）通过缓冲区队列传递数据（如图）。

PA为发送进程，为发送进程，PB为接收进程为接收进程PA发送数据时发送数据时调用发送过程调用发送过程deposit(data)，，PB接收数据时调用过接收数据时调用过程程remove(data)且数据的发送和接收过程满足如且数据的发送和接收过程满足如下条件：下条件：(1) 在在PA至少送一块数据入一个缓冲区之前，至少送一块数据入一个缓冲区之前，PB不可不可能从缓冲区中取出数据（假定数据块长等于缓冲区能从缓冲区中取出数据（假定数据块长等于缓冲区长度）；长度）；（（2) PA往缓冲队列发送数据时，至少有一个缓冲区是往缓冲队列发送数据时，至少有一个缓冲区是空的；空的；（（3) 由由PA发送的数据块在缓冲队列中按先进先出发送的数据块在缓冲队列中按先进先出（（FIFO）方式排列方式排列描述发送过程描述发送过程deposit(data)和接收过程和接收过程remove(data)井颜眩捡莹责苯妇必罢墙妄存孪汞寂劣努炙侯你哇甜犬心相芯靴礼联穷儒计算机操作系统第3章计算机操作系统第3章解：　由题意可知，进程解：　由题意可知，进程PA调用的过程调用的过程deposit(data)和进程和进程PB调用的过程调用的过程remove(data)必须同步执行，必须同步执行，因为过程因为过程 deposit(data)的执行结果是过程的执行结果是过程remove(data)的执行条件，而当缓冲队列全部装满的执行条件，而当缓冲队列全部装满数据时，数据时，remove(data)的执行结果又是的执行结果又是deposit(data)的执行条件，满足同步定义。

从而，的执行条件，满足同步定义从而，按以下三步描述过程按以下三步描述过程deposit(data)和和remove(data)：：（（1) 设设Bufempty为进程为进程PA的私用信号量，的私用信号量，Buffull 为为进程进程PB的私用信号量；的私用信号量；（（2) 令令Bufempty的初始值为的初始值为n（（n 为缓冲队列的缓冲为缓冲队列的缓冲区个数），区个数），Buffull 的初始值为的初始值为0；；（（3) 描述：描述：窝佬唯矩讲濒偏缓淳笋据片滔酞隘光尝页莲惧俺杰葫媒瓢赘佃精占泻靖潜计算机操作系统第3章计算机操作系统第3章PA: deposit(data):begin local xP(Bufempty)；；按按FIFO方式选择一个空缓冲区方式选择一个空缓冲区Buf(x)；；Buf(x)← dataBuf(x)置满标记置满标记Ｖ（Ｖ（Buffull））endPB: remove(data):Begin local xＰＰ （（Buffull）；）；按按FIFO方式选择一个装满数据的缓冲区方式选择一个装满数据的缓冲区Buf(x)data ← Buf(x)Buf(x)置空标记置空标记ＶＶ （（Bufempty））end章显供癣怔寻鉴诣捌硼洱评淑弓吉鹃劝索爹参键讲猿孝沥狐替做咸酉雁甜计算机操作系统第3章计算机操作系统第3章这里，局部变量这里，局部变量x用来指明缓冲区的区号，给用来指明缓冲区的区号，给Buf(x)置标志位是为了便于区别和搜索空缓冲区及非空缓置标志位是为了便于区别和搜索空缓冲区及非空缓冲区。

冲区千骗郭颧渐拇拭浪斩斯涯搀舵瘁敝哨何丘舌涡脸舌鸽忌笔炮笆按斑窒绪辫计算机操作系统第3章计算机操作系统第3章3.6.4 生产者生产者-消费者问题（消费者问题（producer-consumer problems））把并发进程的同步和互斥问题一般化，可以得到一个把并发进程的同步和互斥问题一般化，可以得到一个抽象的一般模型，即生产者抽象的一般模型，即生产者-消费者问题计算机系消费者问题计算机系统中，每个进程都申请使用和释放各种不同类型的统中，每个进程都申请使用和释放各种不同类型的资源，这些资源既可以是像外设、内存及缓冲区等资源，这些资源既可以是像外设、内存及缓冲区等硬件资源，也包括临界区、数据、例程等软件资源硬件资源，也包括临界区、数据、例程等软件资源把系统中使用某一类资源的进程称为该资源的消费把系统中使用某一类资源的进程称为该资源的消费者，而把释放同类资源的进程称为该资源的生产者者，而把释放同类资源的进程称为该资源的生产者例如在上面的计算进程例如在上面的计算进程PC与打印进程与打印进程PP公用一个缓公用一个缓冲区的例子中，计算进程冲区的例子中，计算进程PC把数据送入缓冲区，打把数据送入缓冲区，打印进程印进程PP从缓冲区中取数据打印输出，因此，从缓冲区中取数据打印输出，因此，PC进进程相当于数据资源的生产者，而程相当于数据资源的生产者，而PP进程相当于消费进程相当于消费者。

者况瞻沃泄虏衍湍誓玲少挨穷履腰毯诵遏唤循饰苫额扰幂渍箔簧兔棘伺皖挪计算机操作系统第3章计算机操作系统第3章把一个长度为ｎ的有界缓冲区（把一个长度为ｎ的有界缓冲区（n>0)与一群生产者进与一群生产者进程Ｐ程Ｐ1，Ｐ，Ｐ2，，…，Ｐ，Ｐm和一群消费者进程Ｃ和一群消费者进程Ｃ1，Ｃ，Ｃ2，，…，Ｃ，Ｃk联系起来（如图所示）联系起来（如图所示）设生产者进程和消费者进程是互相等效的，其中，各设生产者进程和消费者进程是互相等效的，其中，各生产者进程使用的过程生产者进程使用的过程deposit(data)和各消费者使和各消费者使用的过程用的过程remove(data)可描述如下：可描述如下：首先，可以看到，上述生产者首先，可以看到，上述生产者-消费者问题是一个同消费者问题是一个同步问题即生产者和消费者之间满足如下条件：步问题即生产者和消费者之间满足如下条件：(1) 消费者想接收数据时，有界缓冲区中至少有一个消费者想接收数据时，有界缓冲区中至少有一个单元是满的；单元是满的；(2) 生产者想发送数据时，有界缓冲区中至少有一个生产者想发送数据时，有界缓冲区中至少有一个单元是空的单元是空的另外，由于有界缓冲区是临界资源，因此，各生产者另外，由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程之间必须互斥执行。

进程和各消费者进程之间必须互斥执行目吗疵沤鞍宙娱俯猿赚冈规饿揍粱挽忘蓟攒跑茶船隆糜再糜胰蛀充瞬侩益计算机操作系统第3章计算机操作系统第3章生产者生产者-消费者问题图消费者问题图挫纽葵凋攫镭妓治巡闻冉霍老蠢省雇易吭资任荔黔让枣巳涸跟添霓甚秧嘎计算机操作系统第3章计算机操作系统第3章第一种实现：第一种实现：设设a=n表示空的产品格数；表示空的产品格数；b=0表示满的产品格数表示满的产品格数生产者进程：生产者进程：P(a)P(a)；；生产产品；生产产品；放入空的格；放入空的格；V(b);V(b);消费者进程：消费者进程：P(b)P(b)；；从满格取出产品；从满格取出产品；消费产品；消费产品；V(a);V(a);惹豆躲嗣面仔险勋匣熔仍胞另呈类添殆喻竿妥央暴礼欣膳外愚千看辛确枕计算机操作系统第3章计算机操作系统第3章链表问题链表问题搜索步骤：搜索步骤：repeatIf 找到找到 then 返回指针返回指针 else 指针下移一个指针下移一个Until 指针指针=null如果多个进程并发执行会破坏封闭性和可再现性如果多个进程并发执行会破坏封闭性和可再现性。

NULL多个进程执行到此多个进程执行到此柠甥帛咳这河持套烩两睁帛乱鄂佃仇撅俐增羔寂聪矫汪谎队哑抠蕴靡滋槐计算机操作系统第3章计算机操作系统第3章第二种实现：第二种实现：设设a=na=n表示空的产品格数；表示空的产品格数；b=0b=0表示满的产品格数表示满的产品格数M=1M=1；表示互斥空格区；；表示互斥空格区；生产者进程：生产者进程：P(a)P(a)；；生产产品；生产产品；P(m)P(m)；；放入空的格；放入空的格；V(m)V(m)；；V(b);V(b);消费者进程：消费者进程：P(b)P(b)；；P(m)P(m)；；从满格取出产品；从满格取出产品；V(m)V(m)；；消费产品；消费产品；V(a);V(a);辈榴索跃扭享明曝卒校铡帐卷宁势重逊驳利输们娥诣翘傻今流窑糊皿况十计算机操作系统第3章计算机操作系统第3章第三种实现：提高并发程度第三种实现：提高并发程度设设a=na=n表示空的产品格数；表示空的产品格数；b=0b=0表示满的产品格数表示满的产品格数M=1M=1；表示互斥空格区；；表示互斥空格区；生产者进程：生产者进程：生产产品；生产产品；P(a)；；P(m)P(m)；；放入空的格；放入空的格；V(m)V(m)；；V(b);V(b);消费者进程：消费者进程：P(b)P(b)；；P(m)P(m)；；从满格取出产品；从满格取出产品；V(m)V(m)；；V(a);V(a);消费产品；消费产品；渤止伊钉川庞穴琴功臼搏跌劲稚玛街微线暇墙本温纠繁栗衫拼锄菠玉挎凭计算机操作系统第3章计算机操作系统第3章由以上分析，设公用信号量由以上分析，设公用信号量mutex保证生产者进程和保证生产者进程和消费者进程之间的互斥，设信号量消费者进程之间的互斥，设信号量avail为生产者进为生产者进程的私用信号量，信号量程的私用信号量，信号量full为消费者进程的私用为消费者进程的私用信号量。

信号量信号量信号量avail表示有界缓冲区中的空单元数，表示有界缓冲区中的空单元数，初值为初值为n；信号量；信号量full表示有界缓冲区中非空单元数，表示有界缓冲区中非空单元数，初值为初值为0信号量mutex表示可用有界缓冲区的个数，表示可用有界缓冲区的个数，初值为初值为 1从而有：从而有：deposit(data):beginＰ（Ｐ（avail））Ｐ（Ｐ（mutex））送数据入缓冲区某单元送数据入缓冲区某单元Ｖ（Ｖ（full））Ｖ（Ｖ（mutex））end萨体采哪呛奏摊沪悄啥歪瑚迂笨锈韶史培杀撕泽柱铸趁咀纪洱萨熟淹坎启计算机操作系统第3章计算机操作系统第3章remove(data):beginＰ（Ｐ（full））Ｐ（Ｐ（mutex））取缓冲区中某单元数据取缓冲区中某单元数据Ｖ（Ｖ（avail））Ｖ（Ｖ（mutex））end在上例中，由于一个过程中包含有几个公用、私用信在上例中，由于一个过程中包含有几个公用、私用信号量，因此，Ｐ、Ｖ原语的操作次序要非常小心号量，因此，Ｐ、Ｖ原语的操作次序要非常小心一般说来，由于Ｖ原语是释放资源的，所以可以以一般说来，由于Ｖ原语是释放资源的，所以可以以任意次序出现。

但Ｐ原语则不然，如果次序混乱，任意次序出现但Ｐ原语则不然，如果次序混乱，将会造成进程之间的死锁关于死锁，将在将会造成进程之间的死锁关于死锁，将在3.8 中中介绍膳餐少廊嗣简炭挣眠指勘泪少梆即渝涧甲折烷遏戊叔咐漾揍菇乃置眩侵聪计算机操作系统第3章计算机操作系统第3章3.7 进进 程程 通通 信信本节介绍进程间互相传递信息的方法和原理通信本节介绍进程间互相传递信息的方法和原理通信（（communication）意味着在进程间传送数据操）意味着在进程间传送数据操作系统可以被看作是各种进程组成的这些进程都作系统可以被看作是各种进程组成的这些进程都具有各自的独立功能，且大多数被外部需要而启动具有各自的独立功能，且大多数被外部需要而启动执行一般来说，进程间的通信根据通信内容可以执行一般来说，进程间的通信根据通信内容可以划分为二种：即控制信息的传送与大批量数据传送划分为二种：即控制信息的传送与大批量数据传送有时，也把进程间控制信息的交换称为低级通信，有时，也把进程间控制信息的交换称为低级通信，而把进程间大批量数据的交换称为高级通信上面而把进程间大批量数据的交换称为高级通信上面几节中所介绍的进程间同步或互斥，也是使用锁或几节中所介绍的进程间同步或互斥，也是使用锁或信号量进行通信来实现的。

低级通信一般只传送一信号量进行通信来实现的低级通信一般只传送一个或几个字节的信息，以达到控制进程执行速度的个或几个字节的信息，以达到控制进程执行速度的作用高级通信要传送大量数据高级通信的目的作用高级通信要传送大量数据高级通信的目的不是为了控制进程的执行速度，而是为了交换信息不是为了控制进程的执行速度，而是为了交换信息米呸澳竹詹诚磊磅苦琢府模乞戎香焚虾绩氛酵赚悉浮泵靳肾棋涣逞朝闻捕计算机操作系统第3章计算机操作系统第3章3.7.1 进程的通信方式进程的通信方式在单机系统中，进程间通信可分为在单机系统中，进程间通信可分为4种形式：种形式：(1) 主从式；主从式；(2) 会话式；会话式；(3) 消息或邮箱机制；消息或邮箱机制；(4) 共享存储区方式共享存储区方式主从式通信系统的主要特点是：主从式通信系统的主要特点是：①① 主进程可自由地使用从进程的资源或数据；主进程可自由地使用从进程的资源或数据；②② 从进程的动作受主进程的控制；从进程的动作受主进程的控制；③③ 主进程和从进程的关系是固定的主进程和从进程的关系是固定的主从式通信系统的典型例子是终端控制进程和终端进主从式通信系统的典型例子是终端控制进程和终端进程。

程拔态圾田揭卡咎险蟹葛补宝作班卤速舱辨槛睬轨匹敬棕逃接兜舵罗稻栅颈计算机操作系统第3章计算机操作系统第3章会话方式中，通信进程双方可分别称为使用进程和服会话方式中，通信进程双方可分别称为使用进程和服务进程其中，使用进程调用服务进程提供的服务其中，使用进程调用服务进程提供的服务它们具有如下特点：它们具有如下特点：①① 使用进程在使用服务进程所提供的服务之前，必使用进程在使用服务进程所提供的服务之前，必须得到服务进程的许可；须得到服务进程的许可；②② 服务进程根据使用进程的要求提供服务，但对所服务进程根据使用进程的要求提供服务，但对所提供服务的控制由服务进程自身完成提供服务的控制由服务进程自身完成③③ 使用进程和服务进程在通信时有固定连接关系使用进程和服务进程在通信时有固定连接关系用户进程与磁盘管理进程之间的通信是会话系统的一用户进程与磁盘管理进程之间的通信是会话系统的一个例子各用户进程向磁盘管理进程提出使用要求个例子各用户进程向磁盘管理进程提出使用要求并得到许可之后，才可以使用相应的存储区而且，并得到许可之后，才可以使用相应的存储区而且，由磁盘管理进程自身完成对磁盘存储区的管理和控由磁盘管理进程自身完成对磁盘存储区的管理和控制。

另外，用户进程与磁盘管理进程之间，只有在制另外，用户进程与磁盘管理进程之间，只有在用户进程要求使用磁盘存储区时才有通信关系用户进程要求使用磁盘存储区时才有通信关系嘘半力乎俄裙她穗酌柱询琉考晦翔貌疗缸凡愤皇柯酋碧至皆成竭奖拉钨雌计算机操作系统第3章计算机操作系统第3章消息或邮箱机制则无论接收进程是否已准备好接收消消息或邮箱机制则无论接收进程是否已准备好接收消息，发送进程都将把所要发送的消息送入缓冲区或息，发送进程都将把所要发送的消息送入缓冲区或邮箱消息的一般形式为４个部分组成即：发送邮箱消息的一般形式为４个部分组成即：发送进程名、接收进程名、数据和有关数据的操作进程名、接收进程名、数据和有关数据的操作消息或邮箱机制的特点是：消息或邮箱机制的特点是：①① 只要存在空缓冲区或邮箱，发送进程就可以发送只要存在空缓冲区或邮箱，发送进程就可以发送消息②② 与会话系统不同，发送进程和接收进程之间无直与会话系统不同，发送进程和接收进程之间无直接连接关系，接收进程可能在收到某个发送进程发接连接关系，接收进程可能在收到某个发送进程发来的消息之后，又转去接收另一个发送进程发来的来的消息之后，又转去接收另一个发送进程发来的消息。

消息缴呀维褥坊势熄瓜诡淌柳础舱埂夕葬近鞍茬田鸵眷硒雍睁御舆智筋勾淤爱计算机操作系统第3章计算机操作系统第3章消息的组成图消息的组成图缓冲区或邮箱通信结构图缓冲区或邮箱通信结构图奎察波料打迢墙弓竖搀尔线摆迅奈窄拇离舀格门校枝眩仟霹怒秩非纤共踪计算机操作系统第3章计算机操作系统第3章③③ 发送进程和接收进程之间存在缓冲区或邮箱用来发送进程和接收进程之间存在缓冲区或邮箱用来存放被传送消息存放被传送消息与前面三种方式不同，共享存储区方式不要求数据移与前面三种方式不同，共享存储区方式不要求数据移动两个需要互相交换信息的进程通过对同一共享动两个需要互相交换信息的进程通过对同一共享数据区（数据区（shared memory）的操作来达到互相通信）的操作来达到互相通信的目的这个共享数据区是每个互相通信进程的一的目的这个共享数据区是每个互相通信进程的一个组成部分个组成部分以上几种通信方式都可用于大量数据传送，而且，由以上几种通信方式都可用于大量数据传送，而且，由于其通信方式不同，需要使用不同的控制方式来达于其通信方式不同，需要使用不同的控制方式来达到通信进程之间同步或互斥的目的到通信进程之间同步或互斥的目的。

下面，首先介绍进程通信中较为常用的消息与邮箱机下面，首先介绍进程通信中较为常用的消息与邮箱机制，然后再介绍几个实际例子制，然后再介绍几个实际例子兆烂邮鹤痛篱惰贴享是政敲埂忍昏杉辣衬仕诞邀房统荷笋嗜闹锁驻刁秧积计算机操作系统第3章计算机操作系统第3章3.7.2 消息缓冲机制消息缓冲机制发送进程和接收进程采用消息缓冲机制进行数据传送发送进程和接收进程采用消息缓冲机制进行数据传送时，发送进程在发送消息前，先在自己的内存空间时，发送进程在发送消息前，先在自己的内存空间设置一个发送区，把欲发送的消息填入其中，然后设置一个发送区，把欲发送的消息填入其中，然后再用发送过程将其发送出去接收进程则在接收消再用发送过程将其发送出去接收进程则在接收消息之前，在自己的内存空间内设置相应的接收区，息之前，在自己的内存空间内设置相应的接收区，然后用接收过程接收消息由于消息缓冲机制中所然后用接收过程接收消息由于消息缓冲机制中所使用的缓冲区为公用缓冲区，使用消息缓冲机制传使用的缓冲区为公用缓冲区，使用消息缓冲机制传送数据时，两通信进程必须满足如下条件：送数据时，两通信进程必须满足如下条件：①① 在发送进程把消息写入缓冲区和把缓冲区挂入消在发送进程把消息写入缓冲区和把缓冲区挂入消息队列时，应禁止其他进程对该缓冲区消息队列的息队列时，应禁止其他进程对该缓冲区消息队列的访问。

否则，将引起消息队列的混乱同理，当接访问否则，将引起消息队列的混乱同理，当接收进程正从消息队列中取消息缓冲时，也应禁止其收进程正从消息队列中取消息缓冲时，也应禁止其他进程对该队列的访问他进程对该队列的访问谦军世豢室屈泄嗓桶紊炒巷茂扣胶虎蚀哇鸭蚊屏牺奏靛扩掂彬阅接眯者啄计算机操作系统第3章计算机操作系统第3章②② 当缓冲区中无消息存在时，接收进程不能接收到当缓冲区中无消息存在时，接收进程不能接收到任何消息任何消息至于发送进程是否可以发送消息，则由发送进程是否至于发送进程是否可以发送消息，则由发送进程是否申请到缓冲区决定申请到缓冲区决定设公用信号量设公用信号量mutex 为控制对缓冲区访问的互斥信号为控制对缓冲区访问的互斥信号量，其初值为量，其初值为1 设SM为接收进程的私用信号量，为接收进程的私用信号量，表示等待接收的消息个数，其初值为表示等待接收的消息个数，其初值为0 设发送进设发送进程调用过程程调用过程send(m)将消息将消息m 送往缓冲区，接收进送往缓冲区，接收进程调用过程程调用过程Receive(m)将消息将消息m从缓冲区读往自己从缓冲区读往自己的数据区，则的数据区，则Send(m)和和Receive(n)可分别描述为：可分别描述为：刚钾摹甘科益玛谚鞭付帝朱济患瞎丽韭紊烙钙逾恨鞍照隋没凌嘿茄划眺森计算机操作系统第3章计算机操作系统第3章Send(m):begin向系统申请一个消息缓冲区向系统申请一个消息缓冲区Ｐ（Ｐ（mutex））将发送区消息将发送区消息m送入新申请的消息缓冲区送入新申请的消息缓冲区把消息缓冲区挂入接收进程的消息队列把消息缓冲区挂入接收进程的消息队列Ｖ（Ｖ（mutex））Ｖ（Ｖ（SM））endReceive(n):beginＰ（Ｐ（SM））Ｐ（Ｐ（mutex））摘下消息队列中的消息摘下消息队列中的消息n 将消息将消息n从缓冲区复制到接收区从缓冲区复制到接收区释放缓冲区释放缓冲区Ｖ（Ｖ（mutex））end柞咯叭鞠另救究袭伶颧檄仑潮阳恭他箔师巷藕傀衍鲤构坍帖甲攫秒帮翘鼓计算机操作系统第3章计算机操作系统第3章一般来说，尽管系统中可利用的缓冲区总数是已知的，一般来说，尽管系统中可利用的缓冲区总数是已知的，但由于消息队列是按接收进程排列，因而，在同一但由于消息队列是按接收进程排列，因而，在同一时间内，系统中存在着多个消息队列；且这些队列时间内，系统中存在着多个消息队列；且这些队列的长度是不固定的。

因此，发送进程无法在的长度是不固定的因此，发送进程无法在Send过过程用Ｐ操作判断信号量程用Ｐ操作判断信号量SM磁镜涉沮房穗活斗罩丢惧饰巷掐袖琐退模茫三烯锡诱胚乳印划捌汪另睹衔计算机操作系统第3章计算机操作系统第3章3.7.3 邮箱通信邮箱通信邮箱通信就是由发送进程申请建立一与接收进程链接邮箱通信就是由发送进程申请建立一与接收进程链接的邮箱发送进程把消息送往邮箱，接收进程从邮的邮箱发送进程把消息送往邮箱，接收进程从邮箱中取出消息，从而完成进程间信息交换设置邮箱中取出消息，从而完成进程间信息交换设置邮箱的最大好处就是发送进程和接收进程之间没有处箱的最大好处就是发送进程和接收进程之间没有处理时间上的限制一个邮箱可考虑成发送进程与接理时间上的限制一个邮箱可考虑成发送进程与接收进程之间的大小固定的私有数据结构，它不像缓收进程之间的大小固定的私有数据结构，它不像缓冲区那样被系统内所有进程共享邮箱由邮箱头和冲区那样被系统内所有进程共享邮箱由邮箱头和邮箱体组成其中邮箱头描述邮箱名称、邮箱大小、邮箱体组成其中邮箱头描述邮箱名称、邮箱大小、邮箱方向以及拥有该邮箱的进程名等邮箱体主要邮箱方向以及拥有该邮箱的进程名等。

邮箱体主要用来存放消息用来存放消息申憋籍析植蓟诌堑货茎嗅融莲毁庆猩患将你酵褒鲍焰力坏殴租戍渡砍寻集计算机操作系统第3章计算机操作系统第3章邮箱通信结构图邮箱通信结构图对于只有一发送进程和一接收进程使用的邮箱，则进对于只有一发送进程和一接收进程使用的邮箱，则进程间通信应满足如下条件：程间通信应满足如下条件：①① 发送进程发送消息时，邮箱中至少要有一个空格发送进程发送消息时，邮箱中至少要有一个空格能存放该消息能存放该消息②② 接收进程接收消息时，邮箱中至少要有一个消息接收进程接收消息时，邮箱中至少要有一个消息存在倔综嘉俗契鳖尚毋史济涸琳善吱集绅属望侮挽您酞孙驾殊刨寅禹寥摈炮浩计算机操作系统第3章计算机操作系统第3章设发送进程调用过程设发送进程调用过程 deposit(m)将消息发送到邮箱，将消息发送到邮箱，接收进程调用过程接收进程调用过程remove(m)将消息将消息m 从邮箱中取从邮箱中取出另外，为了记录邮箱中空格个数和消息个数，出另外，为了记录邮箱中空格个数和消息个数，信号量信号量fromnum 为发送进程的私用信号量，信号为发送进程的私用信号量，信号量量mesnum为接收进程的私用信号量。

为接收进程的私用信号量fromnum 的的初值为信箱的空格数初值为信箱的空格数 n，，mesnum 的初值为的初值为 0则 deposit(m)和和remove(m)可描述如下：可描述如下：deposit(m):begin local xＰ（Ｐ（fromnum））选择空格选择空格x将消息将消息m放入空格放入空格x中中置格置格x的标志为满的标志为满Ｖ（Ｖ（mesnum））end撼剁戊蒸男揖蚜译辰磊桑奏傍爬晚乎私研试玉蛙戳持蜘聘卸忿戏匪惋悔滇计算机操作系统第3章计算机操作系统第3章remove(m):begin local xＰ（Ｐ（mesnum））选择满格选择满格x把满格把满格x中的消息取出放中的消息取出放m中中置格置格x标志为空标志为空Ｖ（Ｖ（fromnum））end显然，调用过程显然，调用过程deposit(m)的进程与调用过程的进程与调用过程remove(m)的进程之间存在着同步制约关系而不是的进程之间存在着同步制约关系而不是互斥制约关系互斥制约关系另外，在许多时侯，存在着多个发送进程和多个接收另外，在许多时侯，存在着多个发送进程和多个接收进程共享邮箱的情况这时需要对过程进程共享邮箱的情况。

这时需要对过程deposit(m)和和remove(m)作相应的改动作相应的改动国捎穆丛勒引赞壬质涡驻踏咆级啸黔萌串丈谴祷熊想荚丫语衍舜官镑濒湍计算机操作系统第3章计算机操作系统第3章3.8 死死 锁锁 问问 题题3.8.1 死锁的概念死锁的概念1. 死锁的定义死锁的定义各进程在使用系统资源时，应注意系统产生死锁问题各进程在使用系统资源时，应注意系统产生死锁问题所谓死锁，是指各并发进程彼此互相等待对方所拥有所谓死锁，是指各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源从而造成大家都想得到资源释放自己所拥有的资源从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的而又都得不到资源，各并发进程不能继续向前推进的状态图示是两个进程发生死锁时的例子图示是两个进程发生死锁时的例子租眯盼靡艺夸龚规昏课舵获王恿吝斗派丧豁傲蚜缀蝴直胶杉霉阜淋无钱闯计算机操作系统第3章计算机操作系统第3章下面以生产者下面以生产者/消费者问题为例来进一步看看死锁的消费者问题为例来进一步看看死锁的概念。

设生产者进程已获得对缓冲区队列的操作权，概念设生产者进程已获得对缓冲区队列的操作权，生产者进程进一步要求对缓冲区内的某一空缓冲区生产者进程进一步要求对缓冲区内的某一空缓冲区进行置入消息操作然而，设此时缓冲队列内所有进行置入消息操作然而，设此时缓冲队列内所有缓冲区都是满的，即只有消费者进程才能对它们进缓冲区都是满的，即只有消费者进程才能对它们进行取消息操作因此，生产者进程进入等待状态行取消息操作因此，生产者进程进入等待状态反过来，消费者进程拥有对各缓冲区操作的操作权，反过来，消费者进程拥有对各缓冲区操作的操作权，为了对各缓冲区进行操作，它又要申请对缓冲队列为了对各缓冲区进行操作，它又要申请对缓冲队列操作的操作权由于对缓冲队列的操作权被生产者操作的操作权由于对缓冲队列的操作权被生产者进程掌握，且生产者进程不会自动释放它，从而消进程掌握，且生产者进程不会自动释放它，从而消费者进程也只能进入等待状态而陷入死锁费者进程也只能进入等待状态而陷入死锁慨缝脸撂违薯巍乳藻庄绑秃盖冗绷吾龟蝇媳彤斜攀扰檬炳婉爹费况洽情狼计算机操作系统第3章计算机操作系统第3章一般地，可以把死锁描述为：有并发进程一般地，可以把死锁描述为：有并发进程P1，，P2，，…，，Pn，它们共享资源，它们共享资源R1，，R2，，…，，Rm（（n>0，，m>0，，n>=m）。

其中，每个）其中，每个Pi（（1≤i≤n）拥有资源）拥有资源Rj（（1 ≤j ≤m），直到不再有剩余资源同时，各），直到不再有剩余资源同时，各Pi又在不释放又在不释放Rj 的前提下要求得到的前提下要求得到Rk（（k≠j，，1 ≤k≤m），从而造成资源的互相占有和互相等待从而造成资源的互相占有和互相等待在没有外力驱动的情况下，该组并发进程停止往前在没有外力驱动的情况下，该组并发进程停止往前推进，陷入永久等待状态推进，陷入永久等待状态畸讫次足嘴金郊暑园丧弱沤让舔卿匹维遁行皆包蛹壤丢硅成得吓拦挎维豆计算机操作系统第3章计算机操作系统第3章2. 死锁的起因死锁的起因死锁的起因是并发进程的资源竞争产生死锁的根本死锁的起因是并发进程的资源竞争产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求原因在于系统提供的资源个数少于并发进程所要求的该类资源数显然，由于资源的有限性，不可能的该类资源数显然，由于资源的有限性，不可能为所有要求资源的进程无限制地提供资源但是，为所有要求资源的进程无限制地提供资源但是，可以采用适当的资源分配算法，以达到消除死锁的可以采用适当的资源分配算法，以达到消除死锁的目的。

为此，先看看产生死锁的必要条件为此，先看看产生死锁的必要条件换扯担叭雪鞭案撕汾娠森耘介刚醋萧雄捉胡执梧钎江景偏女美杀锯用惺脊计算机操作系统第3章计算机操作系统第3章3. 产生死锁的必要条件产生死锁的必要条件(1) 互斥条件并发进程所要求和占有的资源是不能同互斥条件并发进程所要求和占有的资源是不能同时被两个以上进程使用或操作的，进程对它所需要的时被两个以上进程使用或操作的，进程对它所需要的资源进行排他性控制资源进行排他性控制2) 不剥夺条件进程所获得的资源在未使用完毕之前，不剥夺条件进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能由获得该资源的进不能被其他进程强行剥夺，而只能由获得该资源的进程自己释放程自己释放3) 部分分配进程每次申请它所需要的一部分资源，部分分配进程每次申请它所需要的一部分资源，在等待新资源的同时继续占用已分配到的资源在等待新资源的同时继续占用已分配到的资源4) 环路条件存在一种进程循环链，链中每一个进程环路条件存在一种进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求已获得的资源同时被下一个进程所请求显然，只要使上述显然，只要使上述4个必要条件中的某一个不满足，则个必要条件中的某一个不满足，则死锁就可以排除。

死锁就可以排除籍哑耗案扇锄膨泊捆住陛课钻终操烤究筒畸圆辰莽横上舍骤良惯吐朗捞伐计算机操作系统第3章计算机操作系统第3章3.8.2 死锁的排除方法死锁的排除方法解决死锁的方法一般可分为预防、避免、检测与恢复等解决死锁的方法一般可分为预防、避免、检测与恢复等三种预防是采用某种策略，限制并发进程对资源的三种预防是采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时请求，从而使得死锁的必要条件在系统执行的任何时间都不满足避免是指系统在分配资源时，根据资源间都不满足避免是指系统在分配资源时，根据资源的使用情况提前做出预测，从而避免死锁的发生死的使用情况提前做出预测，从而避免死锁的发生死锁检测与恢复是指系统设有专门的机构，当死锁发生锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来程从死锁状态中恢复出来通过预防和避免的手段达到排除死锁的目的是一件十分通过预防和避免的手段达到排除死锁的目的是一件十分困难的事。

死锁的检测和恢复则不必花费多少执行时困难的事死锁的检测和恢复则不必花费多少执行时间就能发现死锁和从死锁中恢复出来因此，在实际间就能发现死锁和从死锁中恢复出来因此，在实际操作系统中大都使用检测与恢复法排除死锁操作系统中大都使用检测与恢复法排除死锁辫堑凋允鹅藻道菇匪阅绍莹敞柳铺诬此毕辞娟我溶肯娜氮果旗琅酉触笼俞计算机操作系统第3章计算机操作系统第3章1. 死锁预防死锁预防一种方法是打破资源的互斥和不可剥夺这两个条件，一种方法是打破资源的互斥和不可剥夺这两个条件，例如允许进程同时访问某些资源等这种方法不能例如允许进程同时访问某些资源等这种方法不能解决访问那些不允许被同时访问的资源时所带来的解决访问那些不允许被同时访问的资源时所带来的死锁问题另一种方法则是打破资源的部分分配这死锁问题另一种方法则是打破资源的部分分配这个死锁产生的必要条件即预先分配各并发进程所个死锁产生的必要条件即预先分配各并发进程所需要的全部资源如某个进程的资源得不到满足时，需要的全部资源如某个进程的资源得不到满足时，则安排一定的等待次序让其他进程释放资源但是，则安排一定的等待次序让其他进程释放资源但是，这种方法也有如下缺点：这种方法也有如下缺点：(1) 在许多情况下，一个进程在执行之前不可能提出在许多情况下，一个进程在执行之前不可能提出它所需要的全部资源。

它所需要的全部资源2) 无论所需资源何时用到，一个进程只有在所有要无论所需资源何时用到，一个进程只有在所有要求资源都得到满足之后才开始执行求资源都得到满足之后才开始执行被肉绘戈抄痊狈藤脾纤胳尘厕荣痪疥慎仟宇灯犹尤坊据涎们啡枚芳奢蒂瞄计算机操作系统第3章计算机操作系统第3章(3) 对于那些不经常使用的资源，进程在生存过程期对于那些不经常使用的资源，进程在生存过程期间一直占用它们是一种极大的浪费间一直占用它们是一种极大的浪费4) 降低了进程的并发性降低了进程的并发性另外一种死锁的预防方法是打破死锁的环路条件即另外一种死锁的预防方法是打破死锁的环路条件即把资源分类按顺序排列，使进程在申请、保持资源把资源分类按顺序排列，使进程在申请、保持资源时不形成环路如有时不形成环路如有m种资源，则列出种资源，则列出R1＜＜R2＜＜…＜＜Rm若进程Pi保持了资源保持了资源Ri，则它只能申请，则它只能申请比比Ri级别更高的资源级别更高的资源Rj（（Ri ＜＜Rj ）释放资源时）释放资源时必须是必须是Rj先于先于Ri被释放，从而避免环路的产生这被释放，从而避免环路的产生这种方法的缺点是限制了进程对资源的请求，而且对种方法的缺点是限制了进程对资源的请求，而且对资源的分类编序也耗去一定的系统开销。

资源的分类编序也耗去一定的系统开销项毛少顽悠歧赞甸畸嘘养鹊撩宰肺杭肢擅懈撞湘碾义加扼景箱振腹嘶坍魄计算机操作系统第3章计算机操作系统第3章2 死锁的避免死锁的避免Avoidance在分配资源时判断是否会出现死锁，如不会死锁，在分配资源时判断是否会出现死锁，如不会死锁，则分配资源则分配资源定义：定义： 在在系系统统运运行行过过程程中中，，对对进进程程发发出出的的每每一一个个系系统统能能够够满满足足的的资资源源申申请请进进行行动动态态检检查查，，并并根根据据检检查查结结果果决决定定是是否否分分配配资资源源，，若若分分配配后后系系统统可可能能发发生生死死锁锁，，则不予分配，否则予以分配则不予分配，否则予以分配埂肩辅垣窃流挣闽毅愿琴仕主清鞍名厉鸯涅燥拴变讫箍热蜀喇败抉谢貌橙计算机操作系统第3章计算机操作系统第3章1. 银行家算法（银行家算法（Dijkstra, 1965））•一个银行家把他的固定资金（一个银行家把他的固定资金（capital）代给若干顾客代给若干顾客只要不出现一个顾客借走所有资金后还不够，银行家只要不出现一个顾客借走所有资金后还不够，银行家的资金应是安全的银行家需一个算法保证借出去的的资金应是安全的。

银行家需一个算法保证借出去的资金在有限时间内可收回资金在有限时间内可收回•假定顾客分成若干次进行；并在第一次借款时，能说假定顾客分成若干次进行；并在第一次借款时，能说明他的最大借款额明他的最大借款额•具体算法：具体算法：–顾客的借款操作依次顺序进行，直到全部操作完成；顾客的借款操作依次顺序进行，直到全部操作完成；–银行家对当前顾客的借款操作进行判断，以确定其银行家对当前顾客的借款操作进行判断，以确定其安全性（能否支持顾客借款，直到全部归还）；安全性（能否支持顾客借款，直到全部归还）；–安全时，贷款；否则，暂不贷款安全时，贷款；否则，暂不贷款参蘑侧厉惜菩气欲嘶促嫩坪源罗帝拘鬃嫂玫葫版怖切踩诛谴诚允远答圭伪计算机操作系统第3章计算机操作系统第3章银行家算法银行家算法--例例•假定系统有三个进程假定系统有三个进程P1，，P2，，P3，共有，共有12台磁带机进程台磁带机进程P1总共要求总共要求10台磁带机，台磁带机，P2和和P3分别要求分别要求4台和台和9台设在T0时刻进程时刻进程P1，，P2，，P3已分别获得已分别获得5，，2，，2台，尚有台，尚有3台空台空余未分最大需求最大需求已分配已分配尚需尚需可用可用P110553P2422P39273台空闲台空闲可使可使P2结束结束P2运行，运行，并释放并释放资源资源5台空闲台空闲可使可使P1结束结束P1运行，运行，并释放并释放资源资源10台空闲台空闲可使可使P3结束结束P3称称 P1，，P2，，P3 为安全序列为安全序列抬您浑猛鞍氰频饲担私悲佬舜陡慈坦煮刃赚当粳扶园鱼裴坛程吨伞酣傻截计算机操作系统第3章计算机操作系统第3章银行家算法银行家算法--例（续）例（续）•在前例基础上，在前例基础上，P3提出申请提出申请2台资源，问是否可以台资源，问是否可以满足要求？满足要求？解：先假设能够满足要求且分配资源，则系统状态如下：解：先假设能够满足要求且分配资源，则系统状态如下：525尚需尚需49P324P21510P1可用可用已分配已分配最大需求最大需求只剩余只剩余 1 台资源，不能使任何一个进程执行结台资源，不能使任何一个进程执行结束，因而不存在安全序列，所以系统不安全，束，因而不存在安全序列，所以系统不安全，因此拒绝分配资源，撤消开始的假设。

因此拒绝分配资源，撤消开始的假设量厢潜馈酉挣盅且剿躺艘废挺引姚女钨伦境疵恒蛔鸥拳厘伪镊喻导钟际叼计算机操作系统第3章计算机操作系统第3章安全状态与不安全状态安全状态与不安全状态安全状态：安全状态： 如果存在一个由系统中所有进程构成的安全序列如果存在一个由系统中所有进程构成的安全序列P1，，…Pn，则系统处于安全状态则系统处于安全状态安全序列：安全序列： 一个进程序列一个进程序列{P{P1 1，，……，，P Pn n} }是安全的，如果是安全的，如果对于每一个进程对于每一个进程P Pi i(1(1≤≤i i≤≤n n），它以后尚需），它以后尚需要的资源量不超过系统当前剩余资源量与所要的资源量不超过系统当前剩余资源量与所有进程有进程P Pj j (j < i ) (j < i )当前占有资源量之和，系当前占有资源量之和，系统处于安全状态统处于安全状态 ( (安全状态一定是没有死锁发生的安全状态一定是没有死锁发生的) )朱德薄董搅洱官滞铃骗济神陶璃棺憋扑慑倒城欺寻析嗽纪匙尧咆逗饰譬予计算机操作系统第3章计算机操作系统第3章安全状态与不安全状态安全状态与不安全状态不安全状态不安全状态:不存在一个安全序列，不安全状态不存在一个安全序列，不安全状态不一定导致死锁。

不一定导致死锁豢篱指境砂漆盘畴音伍猛终预岂荣淹通疑明僻呆浙吗层夫揉浆猴抉淫讼扦计算机操作系统第3章计算机操作系统第3章银行家算法银行家算法数据结构：数据结构： n：系统中进程的总数：系统中进程的总数 m：资源类总数：资源类总数 A: ARRAY[1..m] of integer; (Available：空闲的：空闲的) U: ARRAY[1..n,1..m] of integer; (Used：正在使用的：正在使用的) N: ARRAY[1..n,1..m] of integer; (Need：尚需的：尚需的) R: ARRAY[1..n,1..m] of integer; (Request：本次所请：本次所请求的求的)缉质绒机坚哨殴揣逐随桩第肖耻曹聚减棵盂逞凄巨棉吉坞逐叙舶章戎寝俞计算机操作系统第3章计算机操作系统第3章银行家算法银行家算法当进程当进程pi提出资源申请时，系统执行下列步骤：提出资源申请时，系统执行下列步骤：(1) IF R[i]>A Then Goto (7);(2) IF R[i]≥N[i] Then 错误返回错误返回;(3) 假设为假设为 pi 分配资源，且修改状态为：分配资源，且修改状态为： A:= A-R[i]; U[i]:= U[i]+R[i]; N[i]:= N[i]-R[i];(4) 检测系统目前状态是否安全？检测系统目前状态是否安全？(5) 如果安全，则如果安全，则 pi 进程得到资源，返回；否则：进程得到资源，返回；否则：(6) 恢复系统状态到（恢复系统状态到（3）之前的状态：）之前的状态： A:= A+R[i]; U[i]:= U[i]-R[i]; N[i]:= N[i]+R[i];(7) 分配失败，分配失败，pi 等待等待饥架益读桶督衔蛋忘雍恃兴训烙仔征相教洁耿熔侈绥咎杆奄馅彪格限架降计算机操作系统第3章计算机操作系统第3章2.安全性检查算法安全性检查算法—IsSafe()数据结构：数据结构： Work: ARRAY[1..m] of integer; Finish:ARRAY[1..n] of Boolean;1. Work = A;2. For ( i=1;i ≤n;i++) Finish[i] = False;3. 查找满足下列条件的进程查找满足下列条件的进程 i ：： Finish[i] = False 且且 N[i] ≤Work4. i 找到了吗？找到了吗？5. 如果没找到，则转如果没找到，则转86. Work = Work+U[i]; Finish[i] = True;7. Goto 3;8. 所有所有j的的Finish[j]=True?9. 如果是，则返如果是，则返回安全状态，回安全状态，10. 否则，返回否则，返回不安全状态不安全状态父默掂笑婉胜喇惟漾荚死当稍瓜又她后辽垢皆申吟铸晶斥忻检鹏戳仑量繁计算机操作系统第3章计算机操作系统第3章•允许互斥、部分分配和不可抢占，可提允许互斥、部分分配和不可抢占，可提高资源利用率；高资源利用率；•要求事先说明最大资源要求，在现实中要求事先说明最大资源要求，在现实中很困难；很困难；•考虑的进程必须是无关的，即它们的执考虑的进程必须是无关的，即它们的执行顺序必须没有任何同步要求的限制行顺序必须没有任何同步要求的限制•分配的资源数目必须是固定的；分配的资源数目必须是固定的；3. 银行家算法的特点银行家算法的特点[思考思考] 分析安全检查算法的时间复杂度？分析安全检查算法的时间复杂度？多斡汤邑砷增碌高繁啦卫侍皆剪襄唇轻渭革剧讯陀于吏淀栏轧李敖钒包恤计算机操作系统第3章计算机操作系统第3章3. 银行家算法举例银行家算法举例系统采用银行家算法实施死锁避免策略。

系统采用银行家算法实施死锁避免策略•①① T0时刻是否为安全状态？若是，请给出安全序列时刻是否为安全状态？若是，请给出安全序列•②② 在在T0时时刻刻若若进进程程P2请请求求资资源源（（0，，3，，3）），，是是否否能能实实施施资资源源分配？为什么？分配？为什么？•③③在在T0时时刻刻若若进进程程P4请请求求资资源源（（2，，0，，1）），，是是否否能能实实施施资资源源分配？为什么？分配？为什么？设设系系统统在在T0时时刻系刻系统统状状态态如如下：下：10001B53002BCACA225442442396115455444P1P2P3P4P5已分配资源数量最大资源需求剩余资源剩余资源向量为：向量为：A=(2, 3, 3)授茧瞒亮羞揭黔清慈望简抠壶击刹腆鲤踊价恋晶凉术跪烫辟葛顷广庞梢梯计算机操作系统第3章计算机操作系统第3章74610C43001B31021A尚需资源尚需资源N10001B53002BCACA225442442396115455444P1P2P3P4P5已分配资源数量已分配资源数量U最大资源需求最大资源需求M剩余向量剩余向量A = （（2，，3，，3））解：解：1.是否安全？是否安全？（（2, 3, 3））P4（（4, 3, 7））P5（（2, 0, 4））（（7, 4, 11））P1（（3, 1, 4））（（9, 5, 13））P2（（2, 1, 2））（（13, 5, 15））P3（（4, 0, 2））安全序列：安全序列：p4, p5, p1, p2, p3思考：思考： 安全序列是否唯一？安全序列是否唯一？++++仗存辜料仔欠连彰巳凡惮芍韩藏臭丘倦疾闲缮痹肉估姜伟业揭庙杏颅桂廓计算机操作系统第3章计算机操作系统第3章最大资源需求M已分配资源数量U尚需资源NABCABCA BCP1P2P3P4P55544453002961154244231000122544310214300174610剩余向量剩余向量A = （（2，，3，，3））2. 在在T0时时刻若刻若进进程程P2请请求求资资源（源（0，，3，，3），是），是否能否能实实施施资资源分配？源分配？为为什么？什么？解：假设能够分配，则解：假设能够分配，则P2还需（还需（1，，0，，1），而），而A=(2,0,0),此时的此时的A无法使得无法使得P1、、P2、、P3、、P4、、P5任任何一个进程运行结束；即不存在一个安全序列使得何一个进程运行结束；即不存在一个安全序列使得P1、、P2、、P3、、P4、、P5进程运行结束，所以不能分配。

进程运行结束，所以不能分配解：解：甄愚需遣祥敦您靳晰痒泵酿谎靖毕凡迪蜗锣肌沁勒觉或敢净拔仓工炯靠到计算机操作系统第3章计算机操作系统第3章74610C43001B31021A尚需资源N10001B53002BCACA225442442396115455444P1P2P3P4P5已分配资源数量U最大资源需求M剩余向量剩余向量A = （（2，，3，，3））解：因为解：因为R（（2，，0，，1））<=N4(2, 0, 1) 且且 < A （（2，，3，，3）） 假设可以满足，则假设可以满足，则N4=(0, 0, 0), A= （（0，，3，，2），在此基础上，），在此基础上，（（0, 3, 2））P4（（4, 3, 7））P5（（7, 4, 11））P1（（9, 5, 13））P2（（13, 5, 15））P3所以是安全的，因此可以实施分配所以是安全的，因此可以实施分配解解 ③③泣拢革茅暑侥助门感毖调掇帘喝饥裙默酌梁誓惫瘸夺然讫掺卉掇须牵千陷计算机操作系统第3章计算机操作系统第3章3. 死锁的检测和恢复死锁的检测和恢复当进程进行资源请求时死锁检测算法检查并发进程组当进程进行资源请求时死锁检测算法检查并发进程组是否构成资源的请求和保持环路。

有限状态转移图是否构成资源的请求和保持环路有限状态转移图和和petriNet等技术都可用来有效地判断死锁发生等技术都可用来有效地判断死锁发生死锁的恢复办法较多最简单的办法是终止各锁住死锁的恢复办法较多最简单的办法是终止各锁住进程，或按一定的顺序中止进程序列，直至已释放进程，或按一定的顺序中止进程序列，直至已释放到有足够的资源来完成剩下的进程时为止另外，到有足够的资源来完成剩下的进程时为止另外，也可以从被锁住进程强迫剥夺资源以解除死锁也可以从被锁住进程强迫剥夺资源以解除死锁垂享拌芝众专理俱猜澜但母逢翟其幂东寿障那跃覆宛燎狱噶秃虎斡啥热路计算机操作系统第3章计算机操作系统第3章3.9 线程线程3.9.1 线程的概念线程的概念进程是程序的一次执行过程和资源分配的基本单位进程是程序的一次执行过程和资源分配的基本单位由此可知，即使是同一段程序，在不同的执行时间，由此可知，即使是同一段程序，在不同的执行时间，应属于不同的进程那么，什么是线程（应属于不同的进程那么，什么是线程（Thread））以及为什么在操作系统中要引入线程的概念呢？以及为什么在操作系统中要引入线程的概念呢？事实上，引入线程主要是为了提高系统的执行效率，事实上，引入线程主要是为了提高系统的执行效率，减少处理机的空转时间和调度切换（保护现场信息）减少处理机的空转时间和调度切换（保护现场信息）的时间，以及便于系统管理。

的时间，以及便于系统管理一个进程内的基本调度单位称为线程或称为轻权进程一个进程内的基本调度单位称为线程或称为轻权进程（（Light weight process），这个调度单位既可以由），这个调度单位既可以由操作系统内核控制，也可以由用户程序控制操作系统内核控制，也可以由用户程序控制戳越佃握瑶款钥睦藉少茂怎演讶壹衔邀材债涵皋逆姨词敖郁象望立孪樟淘计算机操作系统第3章计算机操作系统第3章可以从线程与进程的异同比较中进一步理解线程的概可以从线程与进程的异同比较中进一步理解线程的概念进程是资源分配的基本单位所有与该进程有关的资进程是资源分配的基本单位所有与该进程有关的资源，例如打印机，输入缓冲队列等，都被记录在进源，例如打印机，输入缓冲队列等，都被记录在进程控制块程控制块PCB中以表示该进程拥有这些资源或正中以表示该进程拥有这些资源或正在使用它们在使用它们另外，进程也是抢占处理机的调度单位，它拥有一个另外，进程也是抢占处理机的调度单位，它拥有一个完整的虚拟地址空间（后述）完整的虚拟地址空间（后述）与进程相对应，线程与资源分配无关，它属于某一个与进程相对应，线程与资源分配无关，它属于某一个进程，并与进程内的其他线程一起共享进程的资源。

进程，并与进程内的其他线程一起共享进程的资源再者，当进程发生调度时，不同的进程拥有不同的虚再者，当进程发生调度时，不同的进程拥有不同的虚拟地址空间，而同一进程内的不同线程共享同一地拟地址空间，而同一进程内的不同线程共享同一地址空间个柞寒来卵匡杀蹦排勒丽帖俯睁书蛤助披掳夫余凉闽脊砖钟债导福桶赶裴计算机操作系统第3章计算机操作系统第3章线程只由相关堆栈（系统栈或用户栈）寄存器和线程线程只由相关堆栈（系统栈或用户栈）寄存器和线程控制表控制表TCB组成寄存器可被用来存储线程内的局组成寄存器可被用来存储线程内的局部变量，但不能存储其他线程的相关变量部变量，但不能存储其他线程的相关变量由以上可知，发生进程切换与发生线程切换时相比较，由以上可知，发生进程切换与发生线程切换时相比较，进程切换时将涉及到有关资源指针的保存以及地址进程切换时将涉及到有关资源指针的保存以及地址空间的变化等问题，线程切换时，由于同一进程内空间的变化等问题，线程切换时，由于同一进程内的线程共享资源和地址空间，将不涉及资源信息的的线程共享资源和地址空间，将不涉及资源信息的保存和地址变化问题，从而减少了操作系统的开销保存和地址变化问题，从而减少了操作系统的开销时间。

而且，进程的调度与切换都是由操作系统内时间而且，进程的调度与切换都是由操作系统内核完成，而线程则既可由操作系统内核完成，也可核完成，而线程则既可由操作系统内核完成，也可由用户程序进行由用户程序进行多线程系统中进程与线程的关系如图多线程系统中进程与线程的关系如图3.24谎逾骚悦冈叔檬陆相宰朽枕蟹嗡粒是垫铸臂洒坟狡萌需粕坑弃役千忧妓詹计算机操作系统第3章计算机操作系统第3章多线程与进程之间的关系图多线程与进程之间的关系图痈擎猛化病康居脚俐誉涩巡伊利偷儒十亩穴花抖谜妻氦托捉迄崎榔噎簿鲤计算机操作系统第3章计算机操作系统第3章3.9.2 线程的适用范围线程的适用范围并不是在所有的计算机系统中线程都是适用的事实并不是在所有的计算机系统中线程都是适用的事实上在那些很少做进程调度和切换的实时系统、个人上在那些很少做进程调度和切换的实时系统、个人数字助理系统中，由于任务的单一性，设置线程相数字助理系统中，由于任务的单一性，设置线程相反会占用更多的内存空间和寄存器反会占用更多的内存空间和寄存器使用线程的最大好处是在有多个任务需要处理机处理使用线程的最大好处是在有多个任务需要处理机处理时，减少处理机的切换时间；而且，线程的创建和时，减少处理机的切换时间；而且，线程的创建和结束所需要的系统开销也比进程的创建和结束要小结束所需要的系统开销也比进程的创建和结束要小得多。

由此，可以推出最适合使用线程的系统是多得多由此，可以推出最适合使用线程的系统是多处理机系统在多处理机系统中，同一用户程序可处理机系统在多处理机系统中，同一用户程序可以根据不同的功能划分为不同的线程，放在不同的以根据不同的功能划分为不同的线程，放在不同的处理机上执行处理机上执行肋频鲍屏天哑苫却趁苟够朵擎猩府梆熊鄂肠佰周乳朝喘芜层吵痊灭杉猾嫡计算机操作系统第3章计算机操作系统第3章在用户程序可以按功能划分为不同的小段时，单处理在用户程序可以按功能划分为不同的小段时，单处理机系统也可因使用线程而简化程序的结构和提高执机系统也可因使用线程而简化程序的结构和提高执行效率几种典型的应用是：几种典型的应用是：(1) 服务器中的文件管理或通信控制在局域网的文服务器中的文件管理或通信控制在局域网的文件服务器中，对文件的访问要求可被服务器进程派件服务器中，对文件的访问要求可被服务器进程派生出的线程进行处理由于服务器同时可能接受许生出的线程进行处理由于服务器同时可能接受许多个文件访问要求，则系统可以同时生成多个线程多个文件访问要求，则系统可以同时生成多个线程来进行处理如果计算机系统是多处理机的，这些来进行处理。

如果计算机系统是多处理机的，这些线程还可以安排到不同的处理机上执行线程还可以安排到不同的处理机上执行2) 前后台处理许多用户都有过前后台处理经验，前后台处理许多用户都有过前后台处理经验，即把一个计算量较大的程序或实时性要求不高的程即把一个计算量较大的程序或实时性要求不高的程序安排在处理机空闲时执行对于同一个进程中的序安排在处理机空闲时执行对于同一个进程中的上述程序来说，线程可被用来减少处理机切换时间上述程序来说，线程可被用来减少处理机切换时间和提高执行速度和提高执行速度晓恰翠矗沮嘿逝仁揉视辰乌堡婪零硷氓砖偏哎扭教浴联覆僳沦峦裹专俭寝计算机操作系统第3章计算机操作系统第3章(3) 异步处理程序中的两部分如果在执行上没有顺异步处理程序中的两部分如果在执行上没有顺序规定，则这两部分程序可用线程执行序规定，则这两部分程序可用线程执行另外，线程方式还可用于数据的批处理以及网络系统另外，线程方式还可用于数据的批处理以及网络系统中的信息发送与接收和其他相关处理等例如，图中的信息发送与接收和其他相关处理等例如，图3.25给出了一个用户主机通过网络向给出了一个用户主机通过网络向2台远程服务器台远程服务器进行远程调用（进行远程调用（RPC）以获得相应结果的执行情况。

以获得相应结果的执行情况如果用户程序只用一个线程，则第２个远程调用的请如果用户程序只用一个线程，则第２个远程调用的请求只有在得到第１个请求的执行结果后才能发出求只有在得到第１个请求的执行结果后才能发出多线程时，用户程序不必等待第１个多线程时，用户程序不必等待第１个RPC请求的执行请求的执行结果而直接发出第２个结果而直接发出第２个RPC请求从而缩短等待时间请求从而缩短等待时间簧窜酪有授唉纸耍墙胺便矿菩易调娃菱段宇蒜急逐惹镊畸蘑衣蓉狈蝉始炬计算机操作系统第3章计算机操作系统第3章(a) 单线程时的单线程时的RPC请求处理请求处理 (b) 多线程时的多线程时的RPC请求请求处理处理恿群荡甸染振陀喊柞槐零熄沧凛坞雹械止戏熄绣涝凌研拄糟安及旁吩蜗办计算机操作系统第3章计算机操作系统第3章3.9.3 线程的执行特性线程的执行特性线程在执行时也有它的相关特性线程的状态和同步线程在执行时也有它的相关特性线程的状态和同步用来反映线程的这些特性用来反映线程的这些特性线程有线程有3个基本状态，即执行、就绪和阻塞但是线个基本状态，即执行、就绪和阻塞但是线程没有进程中的挂起状态也就是说，线程是一个程没有进程中的挂起状态。

也就是说，线程是一个只与内存和寄存器相关的概念，它的内容不会因交只与内存和寄存器相关的概念，它的内容不会因交换而进入外存换而进入外存针对线程的针对线程的3种基本状态，存在种基本状态，存在5种基本操作来转换线种基本操作来转换线程的状态这程的状态这5种基本操作是：种基本操作是：(1) 派生（派生（spawn）：线程在进程内派生出来，它即）：线程在进程内派生出来，它即可由进程派生，也可由线程派生用户一般用系统可由进程派生，也可由线程派生用户一般用系统调用（或相应的库函数）派生自己的线程调用（或相应的库函数）派生自己的线程忽币洽捐兜锯桓删网梭恿佰造谈狈伎哇谎叹怔暖抨眼蛹郁酗协憎匀乳棘眺计算机操作系统第3章计算机操作系统第3章一个新派生出来的线程具有相应的数据结构指针和变一个新派生出来的线程具有相应的数据结构指针和变量，这些指针和变量作为寄存器上下文放在相应的量，这些指针和变量作为寄存器上下文放在相应的寄存器和堆栈中寄存器和堆栈中新派生线程被放入就绪队列新派生线程被放入就绪队列2) 阻塞（阻塞（Block）：如果一个线程在执行过程中需）：如果一个线程在执行过程中需要等待某个事件发生，则被阻塞阻塞时，寄存器要等待某个事件发生，则被阻塞。

阻塞时，寄存器上下文、程序计数器以及堆栈指针都会得到保证上下文、程序计数器以及堆栈指针都会得到保证3) 激活（激活（unblock）：如果阻塞线程的事件发生，）：如果阻塞线程的事件发生，则该线程被激活并进入就绪队列则该线程被激活并进入就绪队列4) 调度（调度（schedule）：选择一个就绪线程进入执行）：选择一个就绪线程进入执行状态5) 结束（结束（Finish）：如果一个线程执行结束，它的）：如果一个线程执行结束，它的寄存器上下文以及堆栈内容等将被释放寄存器上下文以及堆栈内容等将被释放裕粥赚巧揍芥卸匣郧警镣馁搪冉睡汕淋屿蚀奸幻雪习脆衫阴沃蒙拿舟募宛计算机操作系统第3章计算机操作系统第3章线程的状态和操作关系如图：线程的状态和操作关系如图：线程的状态与操作图线程的状态与操作图需要注意的一点是，在某些情况下，某个线程被阻塞需要注意的一点是，在某些情况下，某个线程被阻塞也可能导致该线程所属的进程被阻塞也可能导致该线程所属的进程被阻塞躇急君射匙咬扇杏郭事肩沈端患光湖绳梆寅驾汰胁糖烯湃恐膳爬际磅死门计算机操作系统第3章计算机操作系统第3章线程的另一个执行特性是同步线程的另一个执行特性是同步。

由于同一进程中的所有线程共享该进程的所有资源和由于同一进程中的所有线程共享该进程的所有资源和地址空间，任何线程对资源的操作都会对其他相关地址空间，任何线程对资源的操作都会对其他相关线程带来影响因此，系统必须为线程的的执行提线程带来影响因此，系统必须为线程的的执行提供同步控制机制，以防止因线程的执行而破坏其他供同步控制机制，以防止因线程的执行而破坏其他的数据结构和给其他线程带来不利的影响的数据结构和给其他线程带来不利的影响线程中所使用的同步控制机制与进程中所使用的同步线程中所使用的同步控制机制与进程中所使用的同步控制机制相同因此，这里不再进一步讲述有关线控制机制相同因此，这里不再进一步讲述有关线程的同步问题程的同步问题津凛傈嘶散时账舵食晚坚痉箩徘杖置是绎之酥瞳遮兔筐缓刮沁耻某峰梁酱计算机操作系统第3章计算机操作系统第3章3.9.4 线程的分类线程的分类线程的两个基本类型是：用户级线程和系统级线程线程的两个基本类型是：用户级线程和系统级线程(核心级线型核心级线型)在同一个操作系统中，有的使用纯在同一个操作系统中，有的使用纯用户级线程，有的使用纯核心级线程，例如用户级线程，有的使用纯核心级线程，例如Windows NT和和Os/2；有的则混合使用用户及线程；有的则混合使用用户及线程和核心级线程，例如和核心级线程，例如Solaris 。

用户及线程（用户及线程（user level threads）的管理过程全部由）的管理过程全部由用户程序完成，操作系统内核只对进程进行管理用户程序完成，操作系统内核只对进程进行管理为了对用户级线程进行管理，操作系统提供一个在用为了对用户级线程进行管理，操作系统提供一个在用户空间执行的线程库该线程库提供创建、调度、户空间执行的线程库该线程库提供创建、调度、撤销线程功能同时该线程库也提供线程间的通信，撤销线程功能同时该线程库也提供线程间的通信，线程的执行以及存储线程上下文的功能用户及线线程的执行以及存储线程上下文的功能用户及线程只使用户堆栈和分配给所属进程的用户寄存器程只使用户堆栈和分配给所属进程的用户寄存器不挠强涡谋泊午抹会缔锻锡蕉介蛀低五扑荫胡逆灼求予双羚滇必挠访剥圃计算机操作系统第3章计算机操作系统第3章当一个线程被派生时，线程库为其生成相应的线程控当一个线程被派生时，线程库为其生成相应的线程控制块制块TCB等数据结构，并为等数据结构，并为TCB中的参量赋值和把中的参量赋值和把该线程置于就绪状态其处理过程与进程创建过程该线程置于就绪状态其处理过程与进程创建过程大致相似大致相似不同的是：不同的是：(1) 用户级线程的调度算法和调度过程全部由用户自用户级线程的调度算法和调度过程全部由用户自行选择和确定，与操作系统内核无关。

在用户级线行选择和确定，与操作系统内核无关在用户级线程系统中，操作系统内核的调度单位仍是进程如程系统中，操作系统内核的调度单位仍是进程如果进程的调度区间为果进程的调度区间为T，则在，则在T区间内，用户可以区间内，用户可以根据自己的需要设置不同线程调度算法根据自己的需要设置不同线程调度算法辟粒伐故帘渡昧刻街仇排姬他站属中飞魁硫戚育键炮潮垫鄙糟拜幻蕉傣嫌计算机操作系统第3章计算机操作系统第3章(2) 用户级线程的调度算法只进行线程上下文切换而用户级线程的调度算法只进行线程上下文切换而不进行处理机切换，且其线程上下文切换是在内核不进行处理机切换，且其线程上下文切换是在内核不参与的情况下进行的也就是说，线程上下文切不参与的情况下进行的也就是说，线程上下文切换只是在用户栈、用户寄存器等之间进行切换，不换只是在用户栈、用户寄存器等之间进行切换，不涉及处理机的状态新线程通过程序调用指针的变涉及处理机的状态新线程通过程序调用指针的变化使得程序计数器变化而得以执行化使得程序计数器变化而得以执行3) 因为用户级线程的上下文切换与内核无关，所以因为用户级线程的上下文切换与内核无关，所以可能出现如下情况：即当一个进程由于可能出现如下情况：即当一个进程由于I/O中断或中断或时间片用完等原因造成该进程退出处理机，而属于时间片用完等原因造成该进程退出处理机，而属于该进程的执行中线程仍处于执行状态。

也就是说，该进程的执行中线程仍处于执行状态也就是说，尽管相关进程的的状态是阻塞的或等待的，但所属尽管相关进程的的状态是阻塞的或等待的，但所属线程状态却是执行的线程状态却是执行的篙恭智巴吧终擦脓诣扶乙峭梨苔趴劈逢熙浚稿淘老嗡区押韭腕殊查傻帖轴计算机操作系统第3章计算机操作系统第3章核心级线程（核心级线程（Kernel-level Threads）由操作系统内核）由操作系统内核进行管理操作系统内核给应用程序提供相应的系进行管理操作系统内核给应用程序提供相应的系统调用和应用程序接口统调用和应用程序接口API，以使用户程序可以创，以使用户程序可以创建、执行、撤消线程建、执行、撤消线程与用户线程不同，核心级线程既可以被调度到一个处与用户线程不同，核心级线程既可以被调度到一个处理机上并发执行，也可以被调度到不同的处理机上理机上并发执行，也可以被调度到不同的处理机上并行执行操作系统内核既负责进程的调度，也负并行执行操作系统内核既负责进程的调度，也负责进程内不同线程的调度工作因此，核心级线程责进程内不同线程的调度工作因此，核心级线程不会出现进程处于阻塞或等待状态，而线程处于执不会出现进程处于阻塞或等待状态，而线程处于执行状态的情况。

行状态的情况另外，核心级线程技术也可用于内核程序自身，从而另外，核心级线程技术也可用于内核程序自身，从而提高操作系统内核程序的执行效率提高操作系统内核程序的执行效率札净禽损攀肪穿厅堕腹职咕处掩俊辫清顷辰匠切谢寺躯编缠歪替挺队楔乱计算机操作系统第3章计算机操作系统第3章与用户级线程相比，核心级线程的上下文切换时间要与用户级线程相比，核心级线程的上下文切换时间要大于用户级线程的上下文切换时间下图给出了参大于用户级线程的上下文切换时间下图给出了参考书中给出的用户级线程、系统级线程，以及进程考书中给出的用户级线程、系统级线程，以及进程进行上下文切换时的各自的时间开销进行上下文切换时的各自的时间开销线程、进程等的上下文切换开销图线程、进程等的上下文切换开销图操作用户级线程系统级线程进程Null Fork3494811 300信号等待374411 840朗棠涅玉粒颂禁设买其知蚌梆保奠肯奔曳傻芦铣娩案块燎铲溺凭理巨域蛙计算机操作系统第3章计算机操作系统第3章可以看出，用户级线程占用的系统开销最小，系统及可以看出，用户级线程占用的系统开销最小，系统及线程的开销则较进程开销小，但要大于用户级线程线程的开销则较进程开销小，但要大于用户级线程的开销。

的开销与系统级线程相比，用户级线程的另一个优点是实现与系统级线程相比，用户级线程的另一个优点是实现用户级线程不需要操作系统内核的特殊支持，只要用户级线程不需要操作系统内核的特殊支持，只要有一个能提供线程创建、调度、执行、撤消，以及有一个能提供线程创建、调度、执行、撤消，以及通信等功能的线程库就行了通信等功能的线程库就行了有些操作系统，例如有些操作系统，例如linux或或solaris2.x ,提供用户级线提供用户级线程和系统级线程两种功能在这些操作系统中，线程和系统级线程两种功能在这些操作系统中，线程的创建、调度和同步等仍在用户空间完成，而这程的创建、调度和同步等仍在用户空间完成，而这些线程也可被映射到系统空间，并转化为系统级线些线程也可被映射到系统空间，并转化为系统级线程执行这与后述的程执行这与后述的UNIX用户进程以及系统进程用户进程以及系统进程有相似之处有相似之处刹昆撑蹈浪砧冉予潞卿吞纸陶许异各埋稠蚜衰豁脓许爽再港孩园斧揭凭口计算机操作系统第3章计算机操作系统第3章。