《chap进程管理》由会员分享，可在线阅读，更多相关《chap进程管理（117页珍藏版）》请在金锄头文库上搜索。
1、3.1 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理第三章第三章: : 进程管理进程管理为什么要引入进程的概念为什么要引入进程的概念进程的表示和调度状态进程的表示和调度状态进程的控制进程的控制进程调度进程调度进程通讯进程通讯死锁死锁妙黑迁全作屈皱脏允袄乓练砚草恍驻陵治狗瘸秽悍矿值俗慑歉他浚硝丙形chap进程管理chap进程管理3.2 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.1 3.1 为什么要进入进程的概念为什么要进入进程的概念前趋图的定义前趋图的定义顺序程序顺序程序程序的并发执行和资源共享程序的并发执行和资源共享程序并发执行的特性程序并发执行的特性进程
2、概念的引入进程概念的引入钟疟问玲秧柴捍饮惋咒液鲁场创裸毒谊吼疥路蝶予佛瘫俄冻砖茹怖抽蕉腑chap进程管理chap进程管理3.3 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理一、前趋图的定义一、前趋图的定义 前趋图前趋图(procedence graph)是一个有向无环图是一个有向无环图DAG (directed acyclic graph)。图中的每一个顶点可。图中的每一个顶点可表示一条语句、一个程序段或进程表示一条语句、一个程序段或进程, 弧则表示两顶弧则表示两顶点之间的偏序点之间的偏序 (partial order) 或前趋关系或前趋关系 (procedence relat
3、ion)。无前趋的顶点为初始顶点。无前趋的顶点为初始顶点, 无后继的顶点称为终止顶点无后继的顶点称为终止顶点, 每个顶点还有一个权每个顶点还有一个权值值, 它表示顶点执行所需的时间。如它表示顶点执行所需的时间。如1352467 它的每一种拓扑排序都是顺序执行时正确得到结它的每一种拓扑排序都是顺序执行时正确得到结果的顺序果的顺序,有路经的两顶点必须按前趋关系顺序执行有路经的两顶点必须按前趋关系顺序执行,无路经的两顶点则可以并发执行。无路经的两顶点则可以并发执行。涉姿眨塞垮契库锥圾陛披艰墩微酸憎顽此叶巩烦泻配济金缕纷轻婪寄官衡chap进程管理chap进程管理3.4 计算机操作系统计算机操作系统 第
4、三章第三章 进程管理进程管理程序顺序执行：程序顺序执行： 程序执行时程序执行时, 必须按某种先后次序必须按某种先后次序, 只有当前操作只有当前操作完成后才能执行后继操作完成后才能执行后继操作, 它体现了某种算法。如：它体现了某种算法。如：S1: a:=x+y;S2: b:=a-5;S3: c:=b+1; 各程序段与此相同各程序段与此相同, 以以 I C P分别代表输入计算和输出分别代表输入计算和输出, 则前趋图：则前趋图：前趋图前趋图S1S2S3I1C1P1I2C2P2二、程序顺序执行二、程序顺序执行修盾窃咖迢亮单顾蛊损感童渡壁择淤原麦培想缕撕捣琶榜叼匀镁浴茂拈叼chap进程管理chap进程管
5、理3.5 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理顺序环境：顺序环境：在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响特征：特征：程序执行的顺序性程序执行的封闭性独占资源，执行过程中不受外界影响程序结果的可再现性程序运行结果与程序执行速度无关，只要初始状态相同，结果应相同梆立锹灾若款刑宾舆圈胎氏虱钟奋会吼夯幸屋种工鞭氖子吼定迭辐咎柯君chap进程管理chap进程管理3.6 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理三、程序的并发执行和资源共享三、程序的并发执行和资源共享程序的并发执行程序的并发执行在一定时间内物理机器上有两个
6、或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的并发执行是指两个程序的执行在时间上是重叠的茹汽哥陈狱疮熊漫裳栖旧陌碳大督嘿父量吃苟脉植坐队旅羊墟杀菲棍傻坟chap进程管理chap进程管理3.7 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理多个程序的并发执行：多个程序的并发执行： 在一定时间内物理机器上有两个或两个以上在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。宏观上同时处于运行状态次序不是事先确定的。宏观上同时处于运行状态微观上各程序交替地间断运行。微观上各程
7、序交替地间断运行。I1I2I3I4C1C2C3C4P1P2P3P4前趋关系前趋关系:IiCi , PiPi+1 CiPi , IiIi+1 CiCi+1Ii+1, Ci, Pi-1是重叠的是重叠的绦罩府渊焕妒美锋抵漓屡咸雀滇季歉堂挛辟娇妈翘遣笋感熄信蠢掏怔暗嘻chap进程管理chap进程管理3.8 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理 举例说明举例说明: 假如系统中有两道程序假如系统中有两道程序AA和和BB：program AA; program BB;begin begin AN BN N:=N+1; AA+1 N:=N+1; BB+1 NA NB End; end;
8、int N=1; 是是AA和和BB都能访问的外部公共变量都能访问的外部公共变量,这两这两个程序在并发执行个程序在并发执行, N:=N+1;可分解为可分解为3条机器指令条机器指令,它们的执行顺序不同有可能导致它们的执行顺序不同有可能导致N的值结果不同。的值结果不同。析太毅桃供姐侠由苹蚂南晾巩险擅挤棕踢伦孜泄唁鼻拍茄垮望凉屡忆债域chap进程管理chap进程管理3.9 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理时间时间 T0 T1 T2 T3 T4 T5 T0 T1 T2 T3 T4 T5程序程序A AA AN NA AA+1A+1N NA A程序程序B BB BN NB BB+
9、1B+1N NB BN N的值的值 1 1 2 2 2 3 1 1 2 2 2 3 (a)顺序顺序执行执行时间时间 T0 T1 T2 T3 T4 T5 T0 T1 T2 T3 T4 T5程序程序A A程序程序B BN N的值的值 1 1 1 1 2 2 1 1 1 1 2 2 (b)交叉交叉执行执行时间时间 T0 T1 T2 T3 T4 T5 T0 T1 T2 T3 T4 T5程序程序A A程序程序B BN N的值的值 1 1 1 1 2 2 1 1 1 1 2 2 (c)交叉交叉执行执行N NB BB BB+1B+1B BN NA AN NA AA+1A+1N NA AA AN NN NA
10、AA AA+1A+1N NB BB BB+1B+1B BN N汐瘫鹊贮畸赘叔硷绕汁肿盲匪辅袒寝魁狰寺蚊湃陵植儒常匆疯映揉鞍磅骸chap进程管理chap进程管理3.10 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理资源共享系统中硬件和软件资源不再为单个用户程序所独占，而由几个用户程序共同使用。程序并发执行和资源共享是现代操作系统的基本特性，它们之间互为依存。并发的特征1.程序结果的不可再现性：并发程序执行的结果与其执行的相对速度有关，是不确定的2.在并发环境下程序的执行是间断性的：执行停执行3.程序和机器执行程序的活动不再一一对应4.并发程序间的相互制约坷余夏蹈少窃典猖盐纵鼎蜜崇
11、迹矩巨端扣基浙域幼读蝉取揭宰芽夜钎搏应chap进程管理chap进程管理3.11 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理四、进程概念的引入四、进程概念的引入进程概念的引入“程序”这个静态概念已不能如实反映程序并发执行过程中的特征。进程的定义从不同的角度对进程的各种定义进程是程序的一次执行进程是可以和别的计算并发执行的计算进程是一个数据结构及能在其上进行操作的程序进程是程序及其数据在处理机上顺序执行的活动进程是程序在某一数据集合上的运行过程程序的一次执行，该程序可与其它程序并发执行。（可程序的一次执行，该程序可与其它程序并发执行。（可并发执行的程序在一个数据集合上的执行过程并
12、发执行的程序在一个数据集合上的执行过程.).) 锅酷际缩苹辖饿骆饲懒侯拓颧韦倔申诸椒置钳既棕弦耳叙巨擞先缝哺宿培chap进程管理chap进程管理3.12 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理 结构性：结构性：由程序由程序+数据数据+进程控制块组成了进程实体进程控制块组成了进程实体, 称之为称之为进程映像。进程控制块是进程存在的标志。进程映像。进程控制块是进程存在的标志。 动态性动态性进程是进程实体的执行过程进程是进程实体的执行过程, 它由创建而产生它由创建而产生, 由由调度而执行调度而执行,因某事件而暂停因某事件而暂停, 由撤销而消亡。在由撤销而消亡。在生命周期内生命周
13、期内, 进程在三种基本状态之间动态转换进程在三种基本状态之间动态转换 并发性并发性 多个进程同时存于内存中多个进程同时存于内存中,一起向前推进一起向前推进,并发执并发执行行 独立性独立性 进程是独立获得资源和独立调度的基本单位进程是独立获得资源和独立调度的基本单位 异步性异步性 各进程都各自独立的不可预知的速度向前推进各进程都各自独立的不可预知的速度向前推进进程的特征进程的特征散铰谴峡压憋熏些皂剐宁成磅舶焕棉医族缝抠菠焉柠铅坐襟昆遁挣洁钝毕chap进程管理chap进程管理3.13 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理程序与进程之间的区别：程序与进程之间的区别： 进程更能
14、真实地描述并发，而程序不能进程更能真实地描述并发，而程序不能 进程是由程序、数据和进程控制块三部分组成的进程是由程序、数据和进程控制块三部分组成的 程序是静态的，进程是动态的程序是静态的，进程是动态的 进程有生命周期，有诞生有消亡，短暂的；而程进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的序是相对长久的 一个程序可对应多个进程，反之亦然一个程序可对应多个进程，反之亦然 进程具有创建其他进程的功能，而程序没有进程具有创建其他进程的功能，而程序没有夏衷担荧淋廖掇咋浸督字癸盗呀骡潦袄涩挨喳吹岭揉禄趾桨落貌淡快纷慑chap进程管理chap进程管理3.14 计算机操作系统计算机操作系统 第三章
15、第三章 进程管理进程管理3.2 3.2 进程的表示和调度状态进程的表示和调度状态进程的表示进程的表示进程的组成进程控制块调度状态调度状态进程的基本调度状态细分的进程调度状态服嘛绊布吵搁妒雇抑匠竞缀烟煮色涎倾琴杠化甫彻匿般喻折顾亏氨坝巡墅chap进程管理chap进程管理3.15 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理一、进程的组成一、进程的组成进程由程序、数据集合和进程由程序、数据集合和PCBPCB三部分组成三部分组成程序部分描述了进程所要完成的功能。数据集合包括程序在执行时所需要的数据和工作区进程控制块（PCB）：用来描述进程当前状态的数据结构，是进程的动态特性的集中反映
16、。随着进程的创建而产生，进程的撤销而被收回。泪匪臆憾徊谆蜂潍鹿咒矾涵竭牵涉迹楷绎耪液赦涧篓图吏匙根瞎困挡狈窃chap进程管理chap进程管理3.16 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理寅缨淫囚楞餐写矢占孺舒刑截捞吝盖措费愤镣疾缎医脸矿虹锐迎凳秃默络chap进程管理chap进程管理3.17 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理二、进程控制块二、进程控制块PCBPCBPCBPCB应包含如下一些信息：应包含如下一些信息：1.进程表示名或标示数2.位置信息3.状态信息 4.进程的优先级5.现场保护区6.资源清单7.队列指针或链接字8.进程同步和通信等其
17、它信息眠郡隘埠爷镣蔷牵兜苍劳细鸳挎寨直颓按掌犯旋油廊祈雁醇馋舰迎爹慰姐chap进程管理chap进程管理3.18 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理三、进程的调度状态三、进程的调度状态进程的三种基本状态：进程的三种基本状态：运行状态：进程占有CPU，并在CPU上运行就绪状态：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行）阻塞状态：指进程因等待某种事件的发生而暂时不能运行的状态 （即使CPU空闲，该进程也不可运行）进程在生命消亡前处于且仅处于三种基本状态之一进程在生命消亡前处于且仅处于三种基本状态之一饭桶慌宠表蜕凭盐淖拥边搭
18、病检焊孟刹函伺奶让焊饿林惠啦垃视饿臣布瞄chap进程管理chap进程管理3.19 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理进程状态转换：进程状态转换： 在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换就绪就绪 - - 运行运行时间一到，调度程序选择一个新的进程运行运行运行 - - 就绪就绪运行进程用完了时间片运行进程被中断，因为一高优先级进程处于就绪状态运行运行 - - 阻塞阻塞当一进程所需的东西必须等待时OS尚未完成服务对一资源的访问尚不能进行初始化I/O 且必须等待结果等待某一进程提供输入 (IPC)阻塞阻塞 - - 运行
19、运行当所等待的事件发生时几吓编协彩揉狂拾歧嫩呀惨腻伴坏靠游征单袍鸭待摹导壶途向闸犯泳胜疡chap进程管理chap进程管理3.20 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理运行运行就绪就绪阻塞阻塞调度调度超时超时I/O请求请求I/O完成完成被霄藻毖贵卧法靶倾拿猫拧坯汪返枕鹿斩阜疽缘出称歇姑帖盘钧坞尽篆舰chap进程管理chap进程管理3.21 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理静止静止就绪就绪静止静止阻塞阻塞挂挂起起挂起挂起挂起挂起超超时时执行执行活动活动就绪就绪活动活动阻塞阻塞调调度度等待事件等待事件,请求请求I/O事件发生事件发生I/O完成完成激
20、活激活激活激活事件发生事件发生I/O完成完成七状态进程模型七状态进程模型终止终止创建创建释放释放许可许可整躇惦宦烬潞佰援摧熟谬积狱氯颐盆缨赚俭帐裁仍蔼汁业粤靡涅霜北俭谬chap进程管理chap进程管理3.22 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.3 3.3 进程的控制进程的控制创建、撤消进程以及完成进程各状态之间的转换。由具有特定功能的原语完成。内核的各项功能是通过执行原语来实现的原语的定义是指若干条机器指令构成的并用以完成特定功能的一段程序，这段程序在执行期间是不可分割的 由以下原语完成：进程创建原语进程创建原语进程撤消原语进程撤消原语阻塞原语、唤醒原语阻塞原语、
21、唤醒原语挂起原语、激活挂起原语、激活( (解挂解挂) )原语原语( (选学选学) )菱盔呻训舜铜炬诅袄呸虏郝皮链验床虞辰蹋抹酷苫吓迄锤洱斤墓沥控桔亏chap进程管理chap进程管理3.23 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理1.1.进程图进程图 进程图是用于描述进程家族关系的有向图，子进程可以进程图是用于描述进程家族关系的有向图，子进程可以继承父进程所拥有的资源。继承父进程所拥有的资源。一、进程的创建一、进程的创建A AB BC CD DF FG GH HE EI IJ J吃瑰舌除烟洪毗票滦池拳谣达亦述丸间犯碉皇恫厄歧淌么答烹见顺软星谨chap进程管理chap进程管理
22、3.24 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理2.进程何时创建进程何时创建? 引起创建进程的事件：引起创建进程的事件： 用户登录、作业调度、提供服务、应用请求用户登录、作业调度、提供服务、应用请求1)用户登录时用户登录时, 由由OS为合法终端创建一个进程为合法终端创建一个进程2)调度到某个批处理作业时调度到某个批处理作业时,由作业调度程序创建由作业调度程序创建3)运行程序请求提供服务运行程序请求提供服务(如如:打印文件打印文件),由由OS创创建建 4)运行中进程因自己的需要运行中进程因自己的需要,由它自己创建子进程由它自己创建子进程托骂芯避篙廊筑妹瓷甘萧感蓝迄肝设曳郸呼
23、砂断甚旷邹谭四阁碉畸乐惟冷chap进程管理chap进程管理3.25 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.3.进程的创建过程进程的创建过程 一旦发现了要求创建新进程的事件一旦发现了要求创建新进程的事件,OS,OS便调用创建原便调用创建原语语, , 按以下过程创建新进程。按以下过程创建新进程。1)1)分配一个唯一的进程标识符分配一个唯一的进程标识符, ,索取一个空白索取一个空白PCBPCB2)2)为新进程的程序和数据分配内存空间为新进程的程序和数据分配内存空间3)3)初始化进程控制块初始化进程控制块 初始化标识符信息初始化标识符信息( (填入填入) )、处理机的状态信息
24、、处理机的状态信息( (指令指指令指针针, , 栈指针栈指针) )和控制信息和控制信息( (状态状态, ,优先级优先级.).)1)1)设置相应的链接设置相应的链接如如: : 把新进程加到就绪队列的链表中把新进程加到就绪队列的链表中斑奇疑扯悉杭嚎敌跪过泄讫臣尉莽括橱愉礁鸦邓前瑞屈仰紧胰枣醋芍孰五chap进程管理chap进程管理3.26 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理1. 1. 进程何时终止进程何时终止? ?1)1)正常结束正常结束批处理系统中批处理系统中, ,进程已运行完成遇到进程已运行完成遇到 Halt Halt 指令指令分时系统中分时系统中, , 用户退出登录用
25、户退出登录2)2)异常结束异常结束本进程发生出错和故障事件本进程发生出错和故障事件存储区越界、保护性错存储区越界、保护性错( (如如: :写只读文件写只读文件) )、特权、特权指令错、非法指令指令错、非法指令( (如如: :程序错转到数据区程序错转到数据区) )、算、算术运算错、运行超时、等待超过时、术运算错、运行超时、等待超过时、I/O I/O 失败、失败、3)3)外界干预外界干预操作系统干预、父进程请求、父进程终止操作系统干预、父进程请求、父进程终止二、二、 进程的终止进程的终止( (撤消撤消) )沙咐寥洱柄蚜伺靖天弥脱高爱乳群陕恬徘筛湃土姻钦蹭概荫疾撰衷蓟衅鹃chap进程管理chap进程
26、管理3.27 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理2. 进程的进程的终终止过程止过程 一旦发生终止进程的事件一旦发生终止进程的事件,OS便调用撤消原语便调用撤消原语,按以下过程终止该进程。按以下过程终止该进程。1)从从PCB中读取进程的状态中读取进程的状态2)若进程处于执行态若进程处于执行态, 应立即终止该进程的执行应立即终止该进程的执行,并置调度标志为真并置调度标志为真(以便该进程终止后系统重新以便该进程终止后系统重新进行调度进行调度,将处理机分配给新选择的进程将处理机分配给新选择的进程)3)若有子孙进程则将它们全部终止若有子孙进程则将它们全部终止,以防它们失控以防它
27、们失控4)将该进程所占有的全部资源还给父进程或系统将该进程所占有的全部资源还给父进程或系统5)将该进程的将该进程的PCB从所在队列中移出从所在队列中移出嘉深饮忍害雅式菜臭贫篱毖胰俩崭攘专谦苑曳闻枪举逻皿各循皆镰稚囊拧chap进程管理chap进程管理3.28 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理三、三、 进程的阻塞、唤醒、挂起与激活进程的阻塞、唤醒、挂起与激活1.进程的阻塞进程的阻塞 处于运行状态的进程处于运行状态的进程, 在其运行过程中期待某一在其运行过程中期待某一事件发生事件发生, 如如:请求系统服务、等待键盘输入、等待数请求系统服务、等待键盘输入、等待数据传输完成、
28、等待其它进程发送消息据传输完成、等待其它进程发送消息, 当被等待的事当被等待的事件未发生时件未发生时, 由进程调用阻塞原语由进程调用阻塞原语(block), 将自己阻将自己阻塞。塞。 阻塞原语使处于运行态的进程停止运行阻塞原语使处于运行态的进程停止运行, 将运行将运行现场保存在其现场保存在其 PCB 的的 CPU 现场保护区现场保护区, 然后将然后将 PCB中的现行状态由运行态变为阻塞态中的现行状态由运行态变为阻塞态, 并将该进程插入并将该进程插入到相应事件的阻塞队列中。最后到相应事件的阻塞队列中。最后, 转进程调度程序重转进程调度程序重新调度新调度, 将处理机分配给一个就绪进程将处理机分配给
29、一个就绪进程, 按新进程按新进程 PCB 中的处理机状态设置中的处理机状态设置CPU环境环境, 使它投入运行。使它投入运行。廖乐帖硼翱拢冯逗珠圈册酿庭岁皇谈炎畜敷盅铰匝司据粥络晕骤种堰绘浦chap进程管理chap进程管理3.29 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理 2. 进程的唤醒进程的唤醒 当被阻塞进程期待的事件到来时当被阻塞进程期待的事件到来时, 由中断处理进程或由中断处理进程或其它产生该事件的进程调用唤醒原语其它产生该事件的进程调用唤醒原语(wakeup), 将期待该将期待该事件的进程事件的进程唤醒。唤醒。 唤醒原语执行时唤醒原语执行时, 将被阻塞进程从相应等队
30、列中移出将被阻塞进程从相应等队列中移出, 并将其并将其 PCB中的现行状态由阻塞改为就绪态中的现行状态由阻塞改为就绪态, 然后将该然后将该进程插入进程插入就绪就绪队列中。队列中。 若事件是等待若事件是等待 I/O 完成完成, 则由硬件提出中断请求则由硬件提出中断请求, CPU响应中断响应中断, 暂停当前进程的执行暂停当前进程的执行, 转去中断处理。检转去中断处理。检查有无等待该查有无等待该 I/O完成的进程。若有完成的进程。若有, 则将它唤醒。然后则将它唤醒。然后结束中断处理。返回被中断进程或重新调度。结束中断处理。返回被中断进程或重新调度。 若事件是等待某进程发一个信息若事件是等待某进程发一
31、个信息, 则由发送进程把该则由发送进程把该等待进程唤醒。等待进程唤醒。却汾缀畅歇题晓度耍汹作矫去在被官欣蕴电枢敲造喂作狼止赠芹翼佐客灿chap进程管理chap进程管理3.30 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理 3. 进程的挂起进程的挂起 当进程请求将自己挂起或父进程请求将子进程挂起时当进程请求将自己挂起或父进程请求将子进程挂起时, 调用挂起原语调用挂起原语(suspend), 将指定进程挂起将指定进程挂起。 执行过程执行过程: 检查要挂起进程的状态检查要挂起进程的状态, 若处于活动就绪态若处于活动就绪态就将其改为静止就绪态就将其改为静止就绪态, 对于活动阻塞态的进程
32、则将其改对于活动阻塞态的进程则将其改为静止阻塞态。如果被挂起的进程正在执行则还要转到调为静止阻塞态。如果被挂起的进程正在执行则还要转到调度程序重新调度。度程序重新调度。 4. 进程的激活进程的激活 要激活指定进程时要激活指定进程时,调用激活原语调用激活原语(active)将它激活将它激活 执行过程执行过程: 将要激活的进程调入内存将要激活的进程调入内存, 并检查它的状态并检查它的状态, 若是静止就绪态则将其改为活动就绪态若是静止就绪态则将其改为活动就绪态,若为静止阻塞态就若为静止阻塞态就将其改为活动阻塞态。如果采用的是抢占调度策略将其改为活动阻塞态。如果采用的是抢占调度策略,被激活被激活的进程
33、优先级高则引起重新调度。的进程优先级高则引起重新调度。荧邮斥基井佰灿锹缠杠键笋位瓤五猾寂者居鱼担雨喳瓶杠宜喝个沥遂雏奋chap进程管理chap进程管理3.31 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.4 进程调度进程调度 无论在多道批处理系统还是分时系统中，系统中无论在多道批处理系统还是分时系统中，系统中的用户进程数都远远超过处理机数，除用户进程的用户进程数都远远超过处理机数，除用户进程要占用处理机外，操作系统还要建立若干个系统要占用处理机外，操作系统还要建立若干个系统进程完成系统功能。这么多的进程竞争处理机，进程完成系统功能。这么多的进程竞争处理机，就要求系统提供进程
34、调度功能，以便采用一些策就要求系统提供进程调度功能，以便采用一些策略，将处理机动态地分配给系统中的各个就绪进略，将处理机动态地分配给系统中的各个就绪进程，使之执行。分配处理机的任务是由进程调度程，使之执行。分配处理机的任务是由进程调度程序完成的。处理机是计算机最重要的资源，如程序完成的。处理机是计算机最重要的资源，如何提高处理机的利用率，在很大程度上取决于进何提高处理机的利用率，在很大程度上取决于进程调度。进程调度性能的好坏，直接影响操作系程调度。进程调度性能的好坏，直接影响操作系统的性能。统的性能。姻歼萨紫毖没初贞袒超绎音叮估舀劝迅闸述碳衫梨赠延初愁姚微鼻呢梯墅chap进程管理chap进程管
35、理3.32 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理一、交通控制程序一、交通控制程序交通控制程序是交通控制程序是J.H.SaltzerJ.H.Saltzer于于19661966年起的名字。年起的名字。主要职能是管理进程状态之间的转变和协调进程主要职能是管理进程状态之间的转变和协调进程间的通讯间的通讯大多数的操作系统并未单独设置交通控制程序，大多数的操作系统并未单独设置交通控制程序，而是将其功能分散到各处，以原语或广义指令的而是将其功能分散到各处，以原语或广义指令的面貌出现。面貌出现。岳令主淀祈靡莲值丰国祖缄闽指垃恰适沿谩票虾害歉区粱俊垮脂鞭溅煮朗chap进程管理chap进程
36、管理3.33 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理二、进程调度程序二、进程调度程序 进程调度的任务是控制协调进程对进程调度的任务是控制协调进程对CPU的竞争的竞争即按照一定的调度算法从就绪队列中选中一个进程，即按照一定的调度算法从就绪队列中选中一个进程，把把CPU的使用权交给被选中的进程。进程调度是通的使用权交给被选中的进程。进程调度是通过进程调度程序来完成的。进程调度程序的主要功过进程调度程序来完成的。进程调度程序的主要功能可描述如下：能可描述如下：1. 记录系统中各进程的执行状况记录系统中各进程的执行状况 为了很好地实现进程调度，进程调度程序首先必须为了很好地实现进
37、程调度，进程调度程序首先必须管理系统中各进程的管理系统中各进程的PCB，将进程的状态变化及资，将进程的状态变化及资源需求情况及时地记录到源需求情况及时地记录到PCB中。通过中。通过PCB变化来变化来准确地掌握系统中所有进程的执行情况和状态特征。准确地掌握系统中所有进程的执行情况和状态特征。竿引荒统揣朵鸥付饯犀妥腮娩骑恃辊翼血抠失瞥永品顷芦亡郴梯吟恼恤炮chap进程管理chap进程管理3.34 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理2. 选择进程真正占有选择进程真正占有CPU 这这是是进进程程调调度度的的实实质质。即即按按照照系系统统规规定定的的调调度度策策略略从从就就绪绪
38、队队列列中中选选择择一一个个进进程程占占有有CPU执执行行。进进程程调调度度依依据据的的算算法法是是与与系系统统的的设设计计目目标标相相一一致致。对对于于不不同同的的系系统统，通通常常采采用用不不同同的的调调度度策策略略。对对于于批批处处理理系系统统常常采采用用短短进进程程的的进进程程优优先先，以以减减少少各各进进程程的的周周转转时时间间。对于分时系统，更多地采用时间片轮转。对于分时系统，更多地采用时间片轮转。3. 进行进程上下文的切换进行进程上下文的切换 当进程调度选中一个进程占有当进程调度选中一个进程占有CPU时，进程调度时，进程调度程序要做的主要工作则是进行进程上下文切换：将正程序要做的
39、主要工作则是进行进程上下文切换：将正在执行进程的上下文保留在该进程的在执行进程的上下文保留在该进程的PCB中，以便以中，以便以后该进程恢复执行。将刚选中进程的运行现场恢复起后该进程恢复执行。将刚选中进程的运行现场恢复起来，并将来，并将CPU的控制权交给被选中进程，使其执行。的控制权交给被选中进程，使其执行。押忆廓唁垮埔撕糠搓吭暇胸闯雇穿哼驶没矿韭骸怕滩仲殴粒宁幸鹿鹊颐燃chap进程管理chap进程管理3.35 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理三、三、 进程调度方式进程调度方式 (1)非剥夺方式非剥夺方式(Non preemptive mode) 在非剥夺方式下在非剥
40、夺方式下, 调度程序一旦把调度程序一旦把CPU分配给某分配给某一进程后便让它一直运行下去一进程后便让它一直运行下去, 直到进程完成或发生直到进程完成或发生某事件而不能运行时，才将某事件而不能运行时，才将CPU分给其它进程。分给其它进程。 这种调度方式通常用在批处理系统中。它的主要这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。优点是简单、系统开销小。 (2)剥夺方式剥夺方式(Preemptive mode) 与非剥夺方式不同，这种方式规定，当一个进程与非剥夺方式不同，这种方式规定，当一个进程正在执行时，系统可以基于某种策略剥夺正在执行时，系统可以基于某种策略剥夺CPU给其给其
41、它进程。剥夺的情况有：优先级策略和时间片策略。它进程。剥夺的情况有：优先级策略和时间片策略。显然这种调度方式通常用在分时系统和实时系统中，显然这种调度方式通常用在分时系统和实时系统中，以便及时响应各进程的请求。以便及时响应各进程的请求。迈仪溪曳溃洪咸吟管震识多蔓熏寒悯糠禹加猩莱韧胎威酷椎灵煞筒猪诲趾chap进程管理chap进程管理3.36 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理四、四、 进程调度的时机进程调度的时机 所谓进程调度的时机，是指什么情况下引起进程所谓进程调度的时机，是指什么情况下引起进程调度程序工作。进程调度的时机是与进程调度的方式调度程序工作。进程调度的时机
42、是与进程调度的方式有关的。进程调度的时机如下：有关的。进程调度的时机如下：1)正在执行的进程正确完成正在执行的进程正确完成, 或由于某种错误而终止或由于某种错误而终止运行运行(陷阱或中断陷阱或中断) ；2)执行中的进程提出执行中的进程提出I/O请求请求, 等待等待I/O完成时完成时;3)在分时系统中在分时系统中, 按照时间片轮转按照时间片轮转, 分给进程的时分给进程的时间片用完时；间片用完时；4)按照优先级调度时按照优先级调度时, 有更高优先级进程变为就绪时有更高优先级进程变为就绪时(剥夺方式剥夺方式)；5)在进程通讯中在进程通讯中, 执行中的进程执行了某种原语操作执行中的进程执行了某种原语操
43、作, 如如P操作、阻塞原语和唤醒原语时操作、阻塞原语和唤醒原语时, 都可能引起进都可能引起进程调度。程调度。拍坑痞肉行了肉智革拓豆论绒超恰多孤绽蚀晾郴砾讲丧乖仁酌郴早睁姿错chap进程管理chap进程管理3.37 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理五、五、 进程控制块的组织方式进程控制块的组织方式PCB表表: 系统把所有系统把所有PCB组织在一起，并把它们放在内存组织在一起，并把它们放在内存的固定区域，就构成了的固定区域，就构成了PCB表表 PCB表的大小决定了系统中最多可同时存在的进程表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度个数，称为系统的并发
44、度（注注: 多道程序中的道数与系统并发度不同）多道程序中的道数与系统并发度不同）PCB表组织方式有两种：表组织方式有两种： 链接方式、索引方式链接方式、索引方式借腹污汀榔聂岩磺堡鹰裤损恨厉貉劫顿侵置悔胸辟掖僚乱愈铅儡衬矮奉汪chap进程管理chap进程管理3.38 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理1) 链接方式：链接方式： 对具有相同状态的进程，分别各自链接起来组对具有相同状态的进程，分别各自链接起来组成进程成进程PCB链队列：链队列： 运行队列、就绪队列、阻塞队列、空闲队列运行队列、就绪队列、阻塞队列、空闲队列空闲指针空闲指针运行指针运行指针就绪指针就绪指针等待等
45、待1指针指针等待等待2指针指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn.675182115馋谭珍逻位轨狮芝袱骆善矮符米颈例旬披贸骆车方汹帧历园尽恨于颤跪蛔chap进程管理chap进程管理3.39 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理2) 索引方式：索引方式： 对具有相同状态的进程，分别设置各自的对具有相同状态的进程，分别设置各自的PCB索引索引表，表明表，表明PCB在在PCB表中的地址表中的地址空闲指针空闲指针运行指针运行指针就绪指针就绪指针等待等待1指针指针等待等待2指针指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn.34
46、2765夜忠拧啤卿是蜂恢拔肚焊瑞郁搀滴拇咱琳噬闷眶禽今虏嘉昼唆稼色绍蔗药chap进程管理chap进程管理3.40 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理杆米诲灾族澳庶模馏妻溺膜柬赵橡落跋馏倔迂破西银辙熔抚创铺账和心席chap进程管理chap进程管理3.41 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理六、进程调度算法六、进程调度算法1.先进先出进程调度算法先进先出进程调度算法(FIFO) (先来先服务先来先服务FCFS)按照进程就绪的先后次序来调度进程按照进程就绪的先后次序来调度进程优点优点:实现简单实现简单缺点缺点:没考虑进程的优先级没考虑进程的优先级,
47、也没考虑作业的长短也没考虑作业的长短2.短作业短作业(进程进程)优先调度算法优先调度算法(SJF SPF)选择就绪队列中估计运行时间最短的进程投入运行选择就绪队列中估计运行时间最短的进程投入运行优点优点:平均周转时间平均周转时间,带权平均周转时间都改善带权平均周转时间都改善缺点缺点:对长作业非常不利对长作业非常不利不能保证紧迫性进程得到及时处理不能保证紧迫性进程得到及时处理估计运行时间不准确估计运行时间不准确冀景跑试坐超渍赌液瞻膳琼拯睁热喜荣戎顷袋洲钞词铝货纫鳞镍逃拐绥照chap进程管理chap进程管理3.42 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理 把把CPU划分成若干
48、时间片划分成若干时间片,并且按顺序赋给就绪并且按顺序赋给就绪队列中的每一个进程，进程轮流占有队列中的每一个进程，进程轮流占有CPU，当时间，当时间片用完时，即使进程未执行完毕，系统也剥夺该进片用完时，即使进程未执行完毕，系统也剥夺该进程的程的CPU，将该进程排在就绪队列末尾。同时系统，将该进程排在就绪队列末尾。同时系统选择另一个进程运行选择另一个进程运行 分时系统中常用时间片轮转法分时系统中常用时间片轮转法时间片选择问题：时间片选择问题： 固定时间片、可变时间片固定时间片、可变时间片(随随)确定时间片大小的因素：确定时间片大小的因素： 系统响应时间、就绪进程个数、系统响应时间、就绪进程个数、C
49、PU能力能力 3.时间片轮转调度算法时间片轮转调度算法(RRRound Robin)扶钠字熄饵庚凰涛呢射泄牺赤窑耪淮桃沾乍踞骋咎酪筛谚勃吹矽兑季丸刨chap进程管理chap进程管理3.43 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理4. 优先权调度算法优先权调度算法(HPFHighest Priority First)优先选择就绪队列中优先权最高的进程投入运行优先选择就绪队列中优先权最高的进程投入运行非抢占式优先权算法非抢占式优先权算法:仅在事件发生放弃处理机时仅在事件发生放弃处理机时抢占式优先权算法抢占式优先权算法: 可将正在运行的运行权剥夺可将正在运行的运行权剥夺 优先权
50、的类型优先权的类型静态优先权静态优先权: 在进程创建时指定优先权在进程创建时指定优先权, 在进程运行在进程运行时优先数不变时优先数不变动态优先权动态优先权: 在进程创建时创立一个优先权，但在在进程创建时创立一个优先权，但在其生命周期内优先数可以动态变化。如等待时间长其生命周期内优先数可以动态变化。如等待时间长优先数可改变优先数可改变 确定优先权的依据确定优先权的依据进程类型、对资源的需求、根据用户要求进程类型、对资源的需求、根据用户要求塔洪南攀给群蛹钦辟戈谋承巍睬违至祖吻候屠岗硬峭柴砧画盆骋澡淄廉吮chap进程管理chap进程管理3.44 计算机操作系统计算机操作系统 第三章第三章 进程管理进
51、程管理5. 高响应比优先调度算法：高响应比优先调度算法： 改进短作业改进短作业(进程进程)优先调度算法优先调度算法,优先权用下式优先权用下式动态计算出来动态计算出来 优先权优先权= =上式可看出上式可看出 等待时间相同要求服务的时间越短优先权越高等待时间相同要求服务的时间越短优先权越高, 有利于短作业有利于短作业 要求服务时间相同要求服务时间相同,等待时间越长优先权越高等待时间越长优先权越高,近似于先来先服务近似于先来先服务 长作业的优先权会随等待时间加长而升高长作业的优先权会随等待时间加长而升高,长作长作业也会得到执行业也会得到执行等待时间等待时间+要求服务时间要求服务时间 响应时间响应时间
52、 要求服务时间要求服务时间 要求服务时间要求服务时间缀华虐话因启货约殖漫雾戏烁男腋缨浙妇氟疥卢秽反埂毅欧梳腊氓粱孰毁chap进程管理chap进程管理3.45 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理6.多队列反馈调度算法：多队列反馈调度算法： 系统按优先级设置多级就绪队列第一级优先级最高系统按优先级设置多级就绪队列第一级优先级最高 各就绪队列分配不同的时间片各就绪队列分配不同的时间片,优先级高的第一级优先级高的第一级队列时间片最小队列时间片最小, 随着队列优先级的降低随着队列优先级的降低, 时间片加时间片加大大 各个队列按照先进先出调度算法各个队列按照先进先出调度算法 一个
53、新进程就绪后进入第一级就绪队列一个新进程就绪后进入第一级就绪队列 进程由于等待事件而放弃进程由于等待事件而放弃CPU后后, 进入等待队列进入等待队列, 一旦等待的事件发生一旦等待的事件发生, 则回到原来的就绪队列则回到原来的就绪队列 当有一个优先级更高的进程就绪时当有一个优先级更高的进程就绪时, 可以抢占可以抢占CPU,被抢占进程回到原来一级就绪队列末尾被抢占进程回到原来一级就绪队列末尾 当第一级队列空时当第一级队列空时, 就去调度第二级队列就去调度第二级队列, 如此类如此类推推 时间片用完后进程放弃时间片用完后进程放弃CPU, 进入下一级就绪队列进入下一级就绪队列中肿速场裔泡奴餐靶杀踢糠激挟
54、钮瘁燕锑罐脊扔君惰赡柞函惮泳翠贿晰妙chap进程管理chap进程管理3.46 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.6 3.6 进程通讯进程通讯一、进程之间的两种相互制约关系一、进程之间的两种相互制约关系 进程的并发执行虽然提高了资源利用率进程的并发执行虽然提高了资源利用率, 但由于但由于进程的异步性进程的异步性, 会给系统造成混乱。为了使并发执行会给系统造成混乱。为了使并发执行的各进程都能正确执行的各进程都能正确执行, 使它们之间能有效地共享资使它们之间能有效地共享资源和相互合作源和相互合作, 必须研究并发执行的各进程之间的相必须研究并发执行的各进程之间的相互制约关
55、系互制约关系, 采取一定的措施使系统中诸进程有条不采取一定的措施使系统中诸进程有条不紊的紊的同步同步向前推进。进程之间有两种相互制约关系：向前推进。进程之间有两种相互制约关系： 间接相互制约关系间接相互制约关系(资源共享关系资源共享关系) 直接相互制约关系直接相互制约关系(功能合作关系功能合作关系)起旭烂嘎概瓢蝗秤浪抵宵陪掀怯枯棉灿谰贞舟亡甄棋搬涉嚎絮操吉病镶滓chap进程管理chap进程管理3.47 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理1) 间接相互制约关系间接相互制约关系(资源共享关系、互斥关系资源共享关系、互斥关系) 由于共享资源由于共享资源, 使得系统中本来没有
56、逻辑关系的进使得系统中本来没有逻辑关系的进程程, 因相互竞争资源而产生了制约关系。因相互竞争资源而产生了制约关系。 例如例如: 进程进程 P1和和P2在运行中都要使用打印机在运行中都要使用打印机, 为了为了保证各进程输出的完整保证各进程输出的完整, 打印机必须互斥访问打印机必须互斥访问 (独占使独占使用用)。即一个进程使用完后。即一个进程使用完后, 另一进程才能使用。这样另一进程才能使用。这样,一旦系统将打印机分配给进程一旦系统将打印机分配给进程 P1, 进程进程P2就必须等待就必须等待, 直到直到P1用完打印机并释放后用完打印机并释放后, P2才能使用。才能使用。 这种因共享资源而使并发执行
57、的各进程之间产生这种因共享资源而使并发执行的各进程之间产生的关系的关系, 叫做叫做间接制约关系间接制约关系, 又叫做又叫做互斥关系互斥关系。这种关。这种关系可以用系可以用“进程进程-资源资源-进程进程”来描述。来描述。 进程的互斥进程的互斥(mutual exclusion) 憎宠伴芹靡羊瓣顶眶暂堪寻庙梆帖绚张衍晒笋递鸦膊茄闸撒侠锋躇翰午匝chap进程管理chap进程管理3.48 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理2)直接制约关系直接制约关系(相互功能合作关系、同步关系相互功能合作关系、同步关系) 通常通常, 一个用户作业要涉及一组并发进程一个用户作业要涉及一组并发进
58、程(输入、输入、计算和输出进程计算和输出进程), 这些进程必须这些进程必须相互协作共同完成相互协作共同完成这项任务。这项任务。 具体说具体说, 在运行过程中在运行过程中, 某进程可能要在某些某进程可能要在某些同步点上等待另一伙伴同步点上等待另一伙伴(协作进程协作进程)为它提供消息为它提供消息, 在未获得消息之前在未获得消息之前, 该进程处于等待状态该进程处于等待状态, 获得消获得消息后被唤醒进入就绪态息后被唤醒进入就绪态, 此后此后, 才能继续运行。进才能继续运行。进程之间的这种制约关系叫做程之间的这种制约关系叫做直接制约关系直接制约关系,又叫又叫同步同步关系关系。这种关系可用。这种关系可用“
59、进程进程-进程进程”来描述。来描述。 隧哲找垃袱面颊唇刮逾谨官斧柒孜称屠歉葫侨窍嚏咽姥邀栈汛堕瓶里皱碘chap进程管理chap进程管理3.49 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理进程的同步进程的同步( (synchronism)例例: 司机司机 P1 售票员售票员 P2REPEAT REPEAT 启动启动 关门关门 正常行驶正常行驶 售票售票 到站停到站停 开门开门UNTIL FALSE UNTIL FALSE摘座竹奔晕仇赶伍摔遥祈乓额锁喷馏尽墟辽泣暂棵淳脓戚跌耀淡仆旬东委chap进程管理chap进程管理3.50 计算机操作系统计算机操作系统 第三章第三章 进程管理进
60、程管理3 3） 临界资源和临界区临界资源和临界区 进程的互斥是由于共享资源而引起的进程的互斥是由于共享资源而引起的, 为了描述为了描述这类情况这类情况, 我们引入临界资源和临界区的概念。我们引入临界资源和临界区的概念。临界资源临界资源(互斥资源互斥资源)：critical resource 系统中一次只允许一个进程访问的资源。这些系统中一次只允许一个进程访问的资源。这些资源既包括资源既包括I/O设备设备, 如打印机等资源如打印机等资源, 也包括软件资也包括软件资源源, 如共享变量、共享文件等。如共享变量、共享文件等。临界区临界区(互斥区互斥区): critical section 并发执行的进
61、程并发执行的进程中中, 访问临界资源的必须互斥执访问临界资源的必须互斥执行的程序段行的程序段叫叫临界区。临界区。 临界区临界区分散在每个要分散在每个要并发执行的并发执行的进程中进程中, 它们都它们都对某个共享的数据结构对某个共享的数据结构(共享资源共享资源)进行访问。进行访问。钡么耍焦皿戴敛鲤悔倔刃案余符惹徐业减牙恳剪笼按嗣颤艺汪乓付舰衙狮chap进程管理chap进程管理3.51 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理 变量变量a是临界资源是临界资源 C1、C2、C3是临界区是临界区 对对a应互斥访问应互斥访问P1 :P2 :P3 :C3 )C1 )C2 )a := a
62、+1 print (a)a := a +1 print (a)if a 0then a := a +1else a:= a-1步钡倚谤桂其玻亨组攒乒昌穗素懊塌姑糟锻恼主减筋虏综埃拢彭恭脓猩振chap进程管理chap进程管理3.52 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理共共 享享 变量变量临界区临界区2 2临界区临界区n n临界区临界区2 2囤免丛难祭塑寨署叫攘睫玫雪漏丈鸵咨弯借彩敌态紧莹棱途凶男春遥采求chap进程管理chap进程管理3.53 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理二、实现临界区互斥的锁操作法二、实现临界区互斥的锁操作法为禁止两个进
63、程同时进入临界区，必须有一相应为禁止两个进程同时进入临界区，必须有一相应机构来协调它们，且遵循下述原则：机构来协调它们，且遵循下述原则：当有若干进程要求进入它们的临界区时，应在有限时间内使一个进程进入临界区。每次最多有一个进程处于临界区内。进程在临界区内逗留应在有限时间范围内。钳赏励恼帘葛彰寅概硕松唐辗权预句燥牟骨释凡逸具擎丽嗅吐钒赂疟饺势chap进程管理chap进程管理3.54 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理用锁操作原语实现互斥用锁操作原语实现互斥关锁执行临界区程序开锁锁有两种状态：w=0表示锁已打开；w=1表示锁被关闭。加锁原语用Lock(w)表示；开锁原语用
64、unlock(w)表示。LOCK(W)原语 L:if W=1 then go to L else W:=1;UNLOCK(W)原语 W:=0;邢摘燕天坛毙痞焙黍省膏衷陕威酉堕磐洋屯愉涪衷坚绕父奶无翻排挛浙斩chap进程管理chap进程管理3.55 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理例：两个进程例：两个进程P1P1，P2P2使用如下程序实施进程的互斥：使用如下程序实施进程的互斥： 进程进程P1 P1 进程进程P2P2 LOCK(w) LOCK(w) S1 S2 UNLOCK(w) UNLOCK(w) S1S1和和S2S2分别为进程分别为进程P1P1和和P2P2的临界区。
65、的临界区。特点：用加锁和开锁的方法实现临界区互斥，其效率特点：用加锁和开锁的方法实现临界区互斥，其效率很低。很低。因为只要一个进程进入临界区后，其他企图进入临界区的进程，在执行LOCK(W)时，因不断测试W造成处理机时间的浪费。焙专府挪助洗倘国屠污肘绑讳韭扒衔虫忙桃阀汤渺尹廓堆挖战郝邯舷喜墩chap进程管理chap进程管理3.56 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理三、信号量和三、信号量和P P、V V操作操作管理和控制铁路交通的重要工具是信号灯。利用管理和控制铁路交通的重要工具是信号灯。利用信号灯的状态信号灯的状态(颜色颜色)控制火车的正常通行。单段控制火车的正常通
66、行。单段铁路任何时刻只允许一列火车通行铁路任何时刻只允许一列火车通行(相当于临界区相当于临界区)，遇到红灯，遇到红灯(表示区内有火车表示区内有火车)应等待，变为绿灯应等待，变为绿灯时可进入行驶时可进入行驶(同时红灯亮禁止其它火车进入同时红灯亮禁止其它火车进入)，火车驶出临界区绿灯亮允许火车进入。同样火车驶出临界区绿灯亮允许火车进入。同样, 为为了管理各并发进程对共享资源的使用了管理各并发进程对共享资源的使用, 引入了信号引入了信号灯灯(信号量信号量)的概念的概念; 将信号量定义为一个将信号量定义为一个整型量整型量 S; S0表示资源可用表示资源可用(无进程在临无进程在临界区相当于绿灯亮界区相当
67、于绿灯亮)。某进程企图进入区时。某进程企图进入区时, S0可以进入。信号量可以进入。信号量 S 只能通只能通过两个标准原子操作过两个标准原子操作(不可中断不可中断) P-V操作来访问。操作来访问。肪袋园沟碘攒傅熬桓沸拾抨卯匈提灰而仍沂俘貉路扣叮澄冈总英卫年拒盟chap进程管理chap进程管理3.57 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理根据用途不同，分为公用信号量公用信号量和私用信私用信号量。号量。公用信号量公用信号量通常用于实现进程之间的互斥，初值为1私用信号量私用信号量通常用于实现进程间的同步，初值为0或为某个正整数n琅煤峭埋泊巩司狂族姆缅畔辟弦掌绍埃小刁邻绷秒凌剿
68、蛰县垂肘引哈锁赃chap进程管理chap进程管理3.58 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理P、V操作原语P P操作原语的定义：操作原语的定义：P（S）：顺序执行下述两个动作：1.信号量的值减1，即S=S-1；2.如果S 0，则该进程继续执行；3.如果S0，则把该进程的状态设置为阻塞态，把它相应的PCB放入相应队列中，并放弃处理机，进行等待（直至其它进程在S上执行V操作，把它释放出来为止） Procedure P(Var S:Semaphore) begin S:=S-1; if S=0，表示资源够用； 等于0表示正好够用； 小于0表示资源不够用，S的绝对值表示等待使
69、用资源的进程个数3、P操作起到了限制一次只有一个进程进入临界区的作用转糖糯哨荆诀辖谈圣罐陶戊芜匣沧寂噶国偿卿将捉涵舞事滩碱啡诀沈谅烹chap进程管理chap进程管理3.60 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理V V操作原语的定义：操作原语的定义：V（S）顺序执行下述两个动作：1.S值加1，即S=S+12.如果S0，则该进程继续运行；3.如果S 0，则唤醒等待信号量S阻塞队列中的头一个进程（把阻塞态改为就绪态），执行V操作的进程继续运行。 Procedure V(Var S:Semaphore) begin S:=S+1; if S=0 then R(S) end;帖淌
70、茬囤卵稼粕泡浴茹噎撑俄劝楞积瞥冉谰琐釜屉闹吟俊秩宛兆永汗谍歌chap进程管理chap进程管理3.61 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理特点：特点：1、V操作是为释放系统资源而设立的，V操作可以唤醒等待进程2、使用的信号量必须与同它对应的P操作相同3、P、V操作在系统里必须成对出现，可以在不同的框图中缚泵讯肛笺蔫兰屹轴纹万逛孩括鄙蔚欲瞥奈潮夏搐奖坟锣妓割奥部挫挟鹏chap进程管理chap进程管理3.62 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理四、用信号量解决互斥模型进程P1 进程P2.P(S)P(S)临界区临界区V（S) V(S).占沂锑惩荣让蔚
71、咯杨让悼哀盏床炕据训偿绘雨秋亿篙邱闸贮谋乌混孟启晨chap进程管理chap进程管理3.63 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理五、用信号量实现互斥实例用用P P，V V操作实现互斥时应注意：操作实现互斥时应注意：（1）在每个程序中用于实现互斥的P(S)和V(S)必须成对出现，即先做P，进临界区；后做V，出临界区。（2）互斥信号量S的初值一般为1裹耪戳溪诛渭屡医珊姑计崔挛蜗鼓广鸵慷矗唾蛤搬劳吊詹壹慑邦音窜墙抑chap进程管理chap进程管理3.64 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理例 前面举例中的公用变量N，也是一个临界资源。两个并发进程对N
72、的操作必须互斥执行。设信号量S，初值为1，表示互斥的使用公用变量N；N的初值为1；则AA： BB P(S) P(S) A=N; B=N; A=A+1; B=B+1; N=A; N=B; V(S) V(S)圈迄败岗泡邓渴糊今匹涅病恼镜摘镑笆擦源咏追牺钦寥色诲挽策滓朗糊松chap进程管理chap进程管理3.65 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理六、用信号量实现同步信号量初值为信号量初值为0 0，两个进程之间的同步模型如，两个进程之间的同步模型如下：下： 进程P1 进程P2L1：P（S） L2：V(S)在这种同步操作中，进程在这种同步操作中，进程p1p1受到进程受到进程P
73、2P2的制约，的制约，而进程而进程P2P2却不受进程却不受进程P1P1的制约，所以是非对称的制约，所以是非对称的。的。啥六决箔指补法利代琼谢冻科韭纤薄瓶韭葱变卑涡碗闽邓骄框闪哺汽其叫chap进程管理chap进程管理3.66 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理用信号量实现同步时应注意：分析进程间的制约关系，确定信号量种类分析进程间的制约关系，确定信号量种类信号量的初值与相应资源数量有关，也与信号量的初值与相应资源数量有关，也与P P，V V操作在程序代码中出现的位置有关操作在程序代码中出现的位置有关同一信号量的同一信号量的P P，V V操作要成对出现，但它们分操作要成对
74、出现，但它们分别在不同的进程代码中别在不同的进程代码中甫笋抬亿则屋倪临运噶村茹耍获炸犊泻会耻阀卿酪除雅喧豹摸课笼垛巍暑chap进程管理chap进程管理3.67 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理例：A（计算） B（打印） 设信号量SA，初值为1，表示是否已取走计算的结果 信号量SB，初值为0，表示是否有可打印的结果单缓冲区缓冲区空，对A表示有资源，对B无资源；缓冲区满，对A表示无资源，对B有资源；利用P、V操作实现对进程A、B的同步淌逊胯眉函吻绩蠕孵炳宝秧屿公孪蛔藏修底哎妈牙裹睹臼抿诌陷洽咀呐需chap进程管理chap进程管理3.68 计算机操作系统计算机操作系统 第
75、三章第三章 进程管理进程管理计算进程计算进程A： 打印进程打印进程B: 计算结果送缓冲区计算结果送缓冲区V(SB)P(SA)P(SB)从缓冲区取结果打印从缓冲区取结果打印V(SA)冶惧胡期印呕感器沈停浊扰斜箔故脓炸莽仁辞音做敌俩辽蛰呻紊泣炸陨渴chap进程管理chap进程管理3.69 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理七、经典进程同步问题七、经典进程同步问题1、生产者消费者问题 问题描述：一群生产者向一个有界缓冲区放入产品，只要缓冲区未满就可以存放，又有一群消费者从有界缓冲区取走产品，只要缓冲区未空就可以取走。 要求：存存、取取、存取都不能同时进行，缓冲区满时停存，缓
76、冲区空时停取，生产与消费等放。峦江毙疾卫东吝杭望遂皿怜讥妮模纳挠眠都缠寸咏绒罪誊靳椭肇辈悬综叔chap进程管理chap进程管理3.70 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理缓冲区缓冲区消费者消费者生产者生产者绣酋坟邓予随撰呸曹蒸酥所囚赛漏仗朝悯波态皿秉哟趋拾月完备鞭技织阻chap进程管理chap进程管理3.71 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理解决方法解决方法设三个信号量1、信号量S，初值为1，表示没有产品进入临界区，用于互斥；2、信号量n1，表示可用缓冲区个数，初值为k3、信号量n2，表示产品个数，初值为0械署绍三侦宽佩才汇冀坟图捶移掀读臃
77、哆盆护器厉蓝探趋肮厌鹊妹唐未敢chap进程管理chap进程管理3.72 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理生产者：生产者：消费者：消费者：生产一个产品生产一个产品P(n1)P(n1)P(S)P(S)产品放入缓冲区产品放入缓冲区V(S)V(S)V(n2)V(n2)消费一个产品消费一个产品P(n2)P(n2)P(S)P(S)产品从缓冲区取出产品从缓冲区取出V(S)V(S)V(n1)V(n1)嗓曰婆延粱凸俄郁恼像旷牡渗繁濒郝条郝际痛惩阎章策蔑哟懒电赔受愤脑chap进程管理chap进程管理3.73 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理2 2、读者、读者
78、写者问题（选学）写者问题（选学）问题描述：问题描述：(1) 一个数据对象被多个读者、写者进程共享；(2) 允许多个读者进程可以共享这个数据对象，因为读操作不会使数据文件混乱；(3) 写者与写者、写者与读者必须互斥使用数据对象；芭藕庞千沿削铲缓右顺唉彰窝汹烯扒旨圃嘘殆鬼绢拼速滥芜纸批帘模厅绘chap进程管理chap进程管理3.74 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理解决方法：解决方法：(1) 设ReadCount是整型变量，初值为0，最大值是RN，表示读者个数；(2) 设信号量r，初值为1，表示读者互斥使用ReadCount；(3) 设信号量w，写者与写者互斥，写者与第
79、一读者互斥泼珠垮陋黎詹爽险训非搅吝唾窜哗够跑撼滚糕赃旱韭豪岿废向康占标蕊锌chap进程管理chap进程管理3.75 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理读者：读者：P(r)ReadCount=0?P(w)ReadCount= ReadCount+1V(r)读操作（使用共享对象）读操作（使用共享对象）P(r)ReadCount= ReadCount-1ReadCount=0?V(w)V(r)返回返回培圣屹槛拔泥扯寂介豪渝眠梗胡由波养酸檀玛苫眉句点宗榴俏岭服酗铰弊chap进程管理chap进程管理3.76 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理写者：写者
80、：P(w)P(w)写操作写操作V(w)V(w)返回返回郎寻袍谁纪速钩灰诱址状寐敏你寇禄忽御狱堵志片项琵嘶臻侩浅瘴瘦袋瓦chap进程管理chap进程管理3.77 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3 3、哲学家就餐问题、哲学家就餐问题问题描述：五个哲学家围坐在一圆桌旁, 桌中央有一盘通心粉, 每人面前有一只空盘子, 每两人之间放一只筷子。 每个人的行为是思考, 感到饥饿, 然后吃通心粉。 为了吃通心粉, 每个人必须拿到两只筷子, 并且每个人只能直接从自己的左边或右边去取筷子。0321414320扒玖悸渗扣秽誓七揭矮提运坚捌家裹囚茨麓世伞捐镊胖轧假舟挚孽臂痉闰chap进程
81、管理chap进程管理3.78 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理解决：解决：筷子是临界资源，一段时间内只允许一个哲学家使用，可以用一个信号量表示一个筷子C(1)， C(2)， C(3)， C(4)， C(5)第第i i个就餐者个就餐者P(C(i)P(C(i+1)mod5)eatV(C(i)V(C(i+1)mod5)think拷酬撼樊裔骡籍张妒镁杠苞躁易伐啄啃敬戌讳邪秃岛懊周瞒谓疏划椅桔猪chap进程管理chap进程管理3.79 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理八、高级通讯原语八、高级通讯原语问题的提出：问题的提出：P.V操作实现的是进程之间
82、的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息两种进程通信的方式两种进程通信的方式消息缓冲和信箱通讯消息缓冲和信箱通讯本质是共享内存本质是共享内存 相互通信的进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换台柬湘魄店摩渔修涡捎铅扫掩脏屿坎幅僻殖谴播宵县以匠填灼馆炼职阳睦chap进程管理chap进程管理3.80 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理消息缓冲区中包含的信息：消息缓冲区中包含的信息：Name：发送消息的进程名或标识号size ：消息长度text：消息正文next：下个
83、缓冲区的地址消息消息：可以用来传递一定信息。消息本身是一组信息，但信息只用通过消息传递才是消息。1 1、消息通信、消息通信靠淫舵俗匀乱贿还湍结痴烽跳慑谷勘攀翘网矩漠灾浙捐浙浪棚癸旦狗贷较chap进程管理chap进程管理3.81 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理下一个要解决的问题是：下一个要解决的问题是：消息传递系统为进程提供了两个高级通讯原语send和receive send：当要进行消息传递时执行send receive：当接收者要接收消息时执行receive通信过程：通信过程：发送进程在自己的空间里制造一个消息，用发送原语将此消息发送出去；接收进程在自己的空间里
84、开辟一个消息接收区，利用接收原语将此消息从消息队列队首复制到指定的接收区。苯纂愁捻卒氟售小乞醒傍赦告捷谁糜锨泡桃湿汾玛杉费悍史额毛式闪捏打chap进程管理chap进程管理3.82 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理M:M:N:N:接受进程接受进程 R R发送进程发送进程 S S.晦斗潮互封脚埋馋旗克路钧陨着涌蔷秘凝爹俩折碧锚身瑰镶绵坤怀驾肤厄chap进程管理chap进程管理3.83 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理进程进程PCBPCB中与消息通信相关的域中与消息通信相关的域mutex：消息队列互斥信号量。消息队列是临界资源，不允许两个或两个
85、以上的进程对它同时访问。Sm ：私有信号量,表示已接收的消息数。用于接受消息进程与发送消息进程进行同步，其值表示消息队列中的消息数目。Pm：指向该进程的消息队列中的消息缓冲链，如下图。尝泽晶乌窘娘孵骂习动捧秧诽贴呻鹰虏疚哥卤直讲吨涯拖眩廷汲珐唆绢自chap进程管理chap进程管理3.84 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理PCBPCB与消息缓冲链与消息缓冲链: :mutexSm Pmnamesizetextnextnamesizetextnextnamesizetextnext消息缓冲区队列浪劲琵去她纺戚邵瓤腑镇妓野猾沧挟疯香凤宴屿界漾稍璃亥瑞稍调得诵撰chap进程管
86、理chap进程管理3.85 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理SendSend程序流程图程序流程图Send(B,addr)消息发送区的起始地址申请消息缓冲区把addr指向的消息发送区中内容（size,text)以及发送进程名送入消息缓冲区找到接受进程的PCB P(mutex) 将缓冲区连入Pm指向的消息链末尾V(mutex) V（Sm） 钉讽淫狸峦涵胖撒喷数奸爬刀坪宋裁写庆雾诵氏骗窍爸挤续瑶信灭塑警楚chap进程管理chap进程管理3.86 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理receivereceive程序流程图程序流程图receive(ad
87、dr)指向消息接收区的起始地址P（ Sm）从Pm指示的消息缓冲队列中取出第一个缓冲区 V(mutex) 将该缓冲区的发送进程名、消息长度和正文送入消息接收区 释放消息缓冲区 P(mutex) 吏伎猪跺脖届盖蛙羹炙虱蓬砍荐单迪雷题垛认唱肄盛法偿烂份交鞠臻姆牵chap进程管理chap进程管理3.87 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理2 2、信箱通讯（选学）、信箱通讯（选学）信箱用于存放信件，而信件是一进程发送给另一进程的消息。信箱为接收进程所拥有。憋累衰乱刻菊后赌岸楔砷艰故洁晤嘴娘阮戎骏囚皱洪巴秸魏裂亢泡靖剃巫chap进程管理chap进程管理3.88 计算机操作系统计算
88、机操作系统 第三章第三章 进程管理进程管理信箱的数据结构：信箱的数据结构：信箱名：boxname;信箱大小：boxsize;已存信件数：mesnum; 接收进程的私用信号量，初值0空的格子数：fromnum; 发送进程的私用信号量，初值为格子数用发送和接受原语实现用发送和接受原语实现靡彩嚎紊验苗凶梦馏匠层俐亮畸樊届磁虹陶浮欣赁拜满鄂蓄磷蔫揣镑彪广chap进程管理chap进程管理3.89 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理Send(boxname,msg)Send(boxname,msg)(1)根据boxname找到信箱；(2)判断信箱是否有空格子p(fromnum)：
89、若有则按第二个参数指出的地址把信件送入该信箱。Receive(boxname,msg)Receive(boxname,msg)(1)根据boxname找到信箱；(2) 判断信箱中是否有信件P(mesnum)：若有则取出一封信放入按第二个参数给出的进程中。泪汕芥误世夸昏朱勇薪揭居椅奢苹住冲箍唉热戴但缝昧吵编佐觉缉硼抄脚chap进程管理chap进程管理3.90 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理3.7 3.7 死锁死锁死锁死锁(Deadlock)的定义：的定义： 一组进程中，每个进程都无限等待被该组中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一
90、组进程就称为死锁进程说明说明: 参与死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。九稍妮享团啡扛晶谆怕菇隘玖镑砰浸氰坞辐阉蓝召晰魔吞央屈单就繁沈畸chap进程管理chap进程管理3.91 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理一、死锁产生的原因一、死锁产生的原因1.竞争资源引起竞争资源引起永久性资源:可以被多个进程多次使用(可再用资源)剥夺性资源(CPU、内存）非剥夺性资源(磁带机、打印机)竞争非剥夺性资源会引起死锁死锁临时性资源:只可使用一次的资源； 如信号量,中断信号,同步
91、信号等(可消耗性资源) 竞争临时性资源也会引起死锁死锁2. 进程推进顺序不当引起进程推进顺序不当引起 对资源采用“申请-分配-使用-释放”模式, 由于推进顺序不当两进程都要申请对方已占有的资源辈汹弥缨漏闸救壳续乏赵累茹零娃杏正谱吊前脐枷杯塌碴俱硕毙铣瓣挡碱chap进程管理chap进程管理3.92 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理二、产生死锁的四个必要条件二、产生死锁的四个必要条件1) 互斥条件（资源独占）：互斥条件（资源独占）： 一个资源每次只能给一个进程使用一个资源每次只能给一个进程使用2) 不可剥夺条件（不可强占）：不可剥夺条件（不可强占）： 资源申请者不能强行
92、的从资源占有者手中夺取资资源申请者不能强行的从资源占有者手中夺取资源源, 资源只能由占有者自愿释放资源只能由占有者自愿释放3) 请求和保持条件请求和保持条件: (部分分配部分分配,占有申请占有申请) 在申请新的资源的同时保持对原有资源的占有。在申请新的资源的同时保持对原有资源的占有。4) 循环等待条件：循环等待条件：存在一个进程存在一个进程-等待资源环形链等待资源环形链 P1 , P2 , , Pn, 其中其中P1等待等待P2占有的资源占有的资源, P2等待等待P3占有的资源占有的资源, , Pn等待等待P1占有的资源。占有的资源。黄材翌击荆卯各峭巴牲华忆芝哮与澳孪港簿掣蒙据汪或纫芜屏挪帕另绷
93、罢chap进程管理chap进程管理3.93 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理P1：申请打印机申请打印机申请扫描仪申请扫描仪使用使用释放打印机释放打印机释放扫描仪释放扫描仪P2：申请扫描仪申请扫描仪申请打印机申请打印机使用使用释放打印机释放打印机释放扫描仪释放扫描仪死锁的例子死锁的例子:竞争非剥夺性资源引起死锁竞争非剥夺性资源引起死锁矮隋帖楞磕埋偷爪硒矫甭鞋症冲雍汞离邵刚盾处罕疫量韭暴稗泡恢吴俞鞋chap进程管理chap进程管理3.94 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理三、对死锁采取的对策三、对死锁采取的对策鸵鸟策略鸵鸟策略采取不理睬的策略
94、采取不理睬的策略预防策略预防策略破坏死锁的四个必要条件破坏死锁的四个必要条件避免策略避免策略精心地分配资源，动态地回避死锁精心地分配资源，动态地回避死锁检测和解除检测和解除一旦发生死锁，及时检测出来，并采取措施一旦发生死锁，及时检测出来，并采取措施解除死锁。解除死锁。悼龙敲掖镶狐齿菇崎疽弓甸湖杰兴问汞痹赶威蔑季空栖际但技英粪素岸览chap进程管理chap进程管理3.95 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理四、死锁的预防四、死锁的预防 系统设计时确定资源分配算法系统设计时确定资源分配算法,保证不发生死锁。保证不发生死锁。做法是破坏产生死锁的四个必要条件之一。做法是破坏产
95、生死锁的四个必要条件之一。1. 破坏破坏“不可剥夺不可剥夺”条件条件 在允许进程动态申请资源前提下规定在允许进程动态申请资源前提下规定, 一个进程一个进程在申请新的资源不能立即满足而变为等待状态之前在申请新的资源不能立即满足而变为等待状态之前, 必须释放已占有的全部资源必须释放已占有的全部资源, 若需要再重新申请。若需要再重新申请。2.破坏破坏“请求和保持请求和保持”条件条件 要求每个进程在运行前必须一次性申请它所要求的要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。一次性分配。枕往肉厂蹦迸蓄锯
96、零济驾碟孩驹携止笼矩掩佰晶厨盒仿箭犊豫凹碎速接后chap进程管理chap进程管理3.96 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理例如：例如：1 1，2 2，3 3，1010P1：申请申请1申请申请3申请申请6P2：申请申请2申请申请4申请申请8P3 P103.破坏破坏“循环等待循环等待”条件条件 采用资源有序分配法采用资源有序分配法: 把系统中所有资源编号把系统中所有资源编号, 进程在申请资源时必须严格按资源编号的递增次序进进程在申请资源时必须严格按资源编号的递增次序进行行,否则操作系统不予分配。否则操作系统不予分配。篱逐玛翌蒜锥瞥髓孝诡宗脚吱驭杖活谐奈帕右蠢傻遍拖缠暇皇
97、娱雷幽屿庸chap进程管理chap进程管理3.97 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理4、破坏破坏“互斥性互斥性”条件，条件， 允许一个资源可由多个进程同时使用允许一个资源可由多个进程同时使用 缺点：对有的资源行不通，例如打印机腊撩说竿翠踢碍讲角座牲琶兼阐卵删聊畜铰旭叹缸投渭光蓖絮墒骚缠陡柏chap进程管理chap进程管理3.98 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理五、避免死锁的算法 系统运行过程中系统运行过程中, 对进程发出的每一个资源申请对进程发出的每一个资源申请进行动态检查进行动态检查,根据检查结果决定是否分配资源根据检查结果决定是否分
98、配资源, 若分若分配可能引起系统死锁配可能引起系统死锁, 则不予分配则不予分配,否则予以分配。否则予以分配。安全序列与安全状态：安全序列与安全状态： 如果在某时刻系统中所有进程可以排列一个如果在某时刻系统中所有进程可以排列一个安全序安全序列列:P1,P2,.,Pn,刚称此时刚称此时,系统处于系统处于安全状态安全状态. 所谓安全序列所谓安全序列P1,P2,.,Pn是指对于是指对于Pi(1in),都有都有它所尚需最大资源数量不超过系统剩余的资源量与所它所尚需最大资源数量不超过系统剩余的资源量与所有有Pj (j Available(2,3,0),让让P4等待等待4) 若若P0请求资源请求资源,发出请
99、求向量发出请求向量Request(0,2,0)假定分配假定分配,资源为资源为: 检查此刻的安全性：检查此刻的安全性：Available(2,1,0)已不满足任何已不满足任何进程的需要进程的需要, 不安全不安全; 不予分配不予分配Available 仍为仍为(2,3,0) 。 Max Allocation Need Available 进程进程 A B C A B C A B C A B C P0 7 5 3 0 3 0 7 2 3 2 1 0 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0
100、2 4 3 1浙娶称衫搓讨樱砧城坯擦层捅贮钠狈焰华咨助两密垒惑铡策尤仑述瑚赁唁chap进程管理chap进程管理3.107 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理检查此刻的安全性检查此刻的安全性 Max Allocation Need Available 进程进程 A B C A B C A B C A B C P0 7 5 3 0 2 0 7 3 3 2 2 0 P1 3 2 2 3 0 2 0 2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1安全安全, 可将可将(0,1,0)分配给分配给
101、P0若将若将P0请求改为请求改为Request(0,1,0)假定分配假定分配, 资源变为资源变为: 进进 Work Allocation Need W+ A Finish 程程 A B C A B C A B C A B C P1 2 2 0 3 0 2 0 2 0 5 2 2 trueP3 5 2 2 2 1 1 0 1 1 7 3 3 trueP4 7 3 3 0 0 2 4 3 1 7 3 5 trueP0 7 3 5 0 2 0 7 3 3 7 5 5 trueP2 7 5 5 3 0 2 6 0 0 10 5 7 true翁桶皖羡磷描讶吉莹毙矫角会搂乏年藐御原氮甘咕这投缺泵染磕纯应俱
102、聊chap进程管理chap进程管理3.108 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理六、六、 死锁的检测与解除死锁的检测与解除 允许死锁发生，操作系统不断监视系统进展情允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生。况，判断死锁是否发生。蹭户怕疯柱货担米斩垄碑栋啃炎恭脱嘴沟类斯赘类蔽供呀串谷谨偏胜馁捏chap进程管理chap进程管理3.109 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理死锁的检测死锁的检测1. 资源分配图资源分配图用有向图描述进程的死锁用有向图描述进程的死锁: 准确、形象准确、形象 系统由若干类资源构成，一类资源称为一个资源
103、类；系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例。每个资源类中包含若干个同种资源，称为资源实例。二元组二元组G=（V，E） V：结点集，分为：结点集，分为P，R两部分两部分 P=p1,p2,pn R=r1,r2,rm E：边的集合：边的集合, 其元素为有序二元组其元素为有序二元组 分配边分配边(rj,pi): 资源实例资源实例进程的一条有向边进程的一条有向边申请边申请边(pi,rj): 进程进程资源类的一条有向边资源类的一条有向边搁蛹虾逗懦遍臀钓虹往重褐每示稗湍陀鹿蛆甲娥去孔阀卒伍易遮目纤瑞呼chap进程管理chap进程管理3.110 计算机操作系
104、统计算机操作系统 第三章第三章 进程管理进程管理有环有死锁逻俺膀伎涟汐状拂地礁欲谋锐喂雕志清清掐搏了解项苫刁肌蘑跋娥钳处纷chap进程管理chap进程管理3.111 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理有环无死锁肺母伤经诺猩身筷竿倒披现泰卿丽茁虹慕荒梳挪录纷依蚂哲征狈塌庞虞蛙chap进程管理chap进程管理3.112 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理2. 死锁定理死锁定理 如果资源分配图中没有环路如果资源分配图中没有环路, 则系统中没有死锁则系统中没有死锁, 如果图中存在环路则系统中如果图中存在环路则系统中可能存在死锁可能存在死锁。 如果每个
105、资源类中只包含如果每个资源类中只包含一个一个资源实例资源实例, 则资源则资源分配图环路是死锁存在的充分必要条件。分配图环路是死锁存在的充分必要条件。资源分配图化简方法：资源分配图化简方法：1）找一个非孤立点进程结点且只有分配边，去掉分）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点。配边，将其变为孤立结点。2）再把相应的资源分配给一个等待该资源的进程，）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边。即将某进程的申请边变为分配边。甘扼绩蔑惺吐眯慨阜嘿置晾毯攘熏恤吗茬俐蹦吉形丰捅破架楷蜀纂顶庐走chap进程管理chap进程管理3.113 计算机操作系统计
106、算机操作系统 第三章第三章 进程管理进程管理死锁的解除死锁的解除 一旦死锁发生则采取专门的措施，解除一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。死锁并以最小的代价恢复操作系统运行。死锁的解除死锁的解除(关键是代价最小关键是代价最小)：1）重新启动）重新启动2）撤消进程）撤消进程3）剥夺资源）剥夺资源4）进程回退）进程回退绅赞鳞投阁惑汽担氖纤邪睦反巫妖员椽蚜烯往狮老殃迹水蘑驹酝街露野婪chap进程管理chap进程管理3.114 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理作业：作业：P93 1，2，3，6 13,15,23,24,26 29，31，34肢
107、嗡挫股田襄汀钠藻俞卖姓该状裳诚瞬佩梆泽元家伪屠钵辑轰熄淮虹孝喜chap进程管理chap进程管理3.115 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理作业题补充作业题补充1、如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？2、考虑一个理发店，只有一个理发师，只有n张可供顾客等待理发的椅子，如果没有顾客，则理发师睡觉；如果有一顾客进入理发店发现理发师在睡觉，则把他叫醒，写一个程序协调理发师和顾客之间的关系。渭闭藐喀孝下萍校蛇墩幅裹浪领钳掺画翁蛋一烁脊杖摹蓝串曳组钵盯截逻chap进程管理chap进程管理3.116 计算机操作
108、系统计算机操作系统 第三章第三章 进程管理进程管理3、设系统有3种类型的资源（A,B,C）和5个进程（P1，P2，P3，P4，P5)，A资源的数量为17，B资源的数量为5， C资源的数量为20。在T0时刻系统状态如下：进程进程 最大资源需求量最大资源需求量 已分配资源数量已分配资源数量 A B C A B C A B C A B CP1 5 5 9 2 1 2 P1 5 5 9 2 1 2 P2 5 3 6 4 0 2 P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P4 4 2 5 2 0 4 P5 4 2 4 3
109、1 4P5 4 2 4 3 1 4 蒸彩睦油畜御牲饼稚棵摈宝蝶捆帮诈陷激睛莽捷近睛珐卑谗釜桑摇颊疹蔓chap进程管理chap进程管理3.117 计算机操作系统计算机操作系统 第三章第三章 进程管理进程管理系统采用银行家算法实现死锁避免策略（1）T0时刻是否为安全状态？若是，请给出安全序列；（2） T0时刻若P4请求资源（0，3，4），是否能实现资源分配？为什么？（3） T0时刻若P4请求资源（2，0，1），是否能实现资源分配？为什么?（4）在（3）的基础上，若进程P1请求资源（0，2，0），是否能实现资源分配？为什么？针洱漱弱湛迸铅栓暇别微俞盎仿硒敌纺敝猿坤虐煮卜岭级馅匈辐蕴帜泄耽chap进程管理chap进程管理
