计算机操作系统辅导第三章

1、2020/7/6,1,计算机操作系统,第三章 处理机调度与死锁,2020/7/6,2,2009年2个选择（调度、死锁各占1个）2010年1个选择（调度）2011年2个选择（调度、银行家算法）2012年3个选择（调度、银行家算法）2013年2个选择(调度、银行家算法),处理机调度部分是操作系统对CPU的管理，这部分要求考生理解作业和进程的关系，掌握作业调度和进程调度的策略和算法，重点要掌握几种典型的调度算法的基本思想、适用的范围和特点，要能指出各种调度算法的调度顺序并能计算它们的周转时间。 调度算法的难点在于计算不同调度算法下调度的效率，建议使用时间轴（甘特图Gantt）的方法解决相关的调度时间

2、计算问题。 银行家算法是系统进行资源分配的时候防止发生死锁的一种方法，该算法的难点在于搞清楚各种不同表格的含义，能够看懂并且会做出相关的表格，由表格推出结果。,2020/7/6,3,本章目录,3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度(略) 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 基础要点 练习题 常见知识分析 实战练习,2020/7/6,4,第三章 处理机调度与死锁,3.1 处理机调度的层次 1、高级调度：作业调度、长程调度、接纳调度。目标是把外存上在于后备队列中的那些作业调入内存。调度对象是作业。

3、 1)作业和作业步 (1)作业：包括程序、数据和作业说明书。批处理系统中以作业为单位，从外存调入内存。 (2)作业步：每个作业必须经过若干个相对独立、又相互关联的加工步骤才能得到结果。每个加工步骤称为一个作业步，各作业步是相互联系的。 典型的作业分三步走：编译、链接装配和运行。 (3)作业流：作业后备队列。,2020/7/6,5,2)作业控制块JCB：系统为每个作业设置一个JCB，是作业在系统中存在的标志：作业标识、用户名称、用户帐号、作业类型、作业状态、调度信息、资源需求、资源使用等。作业到达系统，由作业注册程序为作业建立JCB，根据作业类型放到相应的后备队列中 3)作业调度：由作业调度程序

4、根据JCB中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法调度它们。创建进程、分配必要的资源。接纳调度。,2020/7/6,6,4）作业运行的三个阶段和三种状态 三个阶段：收容、运行和完成 收容：提交作业、输入到硬盘上，建立JCB，放入后备队列。为后备状态。 运行：被调度进入内存，建立进程，每一次放入就绪队列，直到运行结束。动行状态。 完成：任务完成或异常结束，由终止作业程序回收JCB和资源，将结果信息形成输出文件输出。完成状态。,2020/7/6,7,5）作业调度的主要任务 (1)决定接纳多少作业：单道、多道 (2)决定接纳哪些作业：作业调度算法 一般系统总是优先选择I/O型

5、和计算型作业均衡个作业投入运行。 2、低级调度：进程调度或短程调度，频率最高。由短期调度程序或CPU调度程序执行。Scheduler 功能： (1)保存处理机的现场信息：程序计数器、通用寄存器的内容。 (2)按某种算法选取进程，将其改为运行状态。 (3)由分派程序Dispatcher把处理器分配给进程。恢复现场，从断点处继续运行。 进程切换一定发生在核心态而非用户态,2020/7/6,8,三个基本机制： (1)排队器。形成就绪队列。就绪队列可实现为：FIFO队列，优先队列，树或简单的无序链表。 (2)分派器。选择就绪进程，切换上下文，分配处理机，切换到用户模式，跳转到用户程序的合适位置，以重新

6、启动程序，停止一个进程而启动另一个进程的时间称为分派延迟（dispatch latency）。 (3)上下文切换机制：两对切换。当前进程和分派程序，分派程序和新进程。,2020/7/6,9,进程上下文切换步骤： 保存被中断程序的处理器现场信息 修改被中断进程的PCB有关信息，如状态 把被中断进程的PCB加入相应队列 选择占用处理器运行的另一个进程 修改被选中进程的PCB信息，就绪。 设置被选中进程的地址空间，恢复存储管理信息 根据被选中进程的上下文信息恢复处理器现场,2020/7/6,10,处理器模式切换步骤 保存被中断进程的处理器现场信息 处理器从用户态切换到核心态，以便执行系统服务程序或中

7、断处理程序的地址。 如果处理中断，可根据所规定的中断级别设置中断屏蔽位。 根据系统调用号或中断号，从系统调用表中或入口地址表中找到系统服务程序或中断处理程序的地址。 模式切换不同于进程切换，它不一定引起进程状态的切换，也不一定引起进程切换。,2020/7/6,11,CPU调度决策可以如下4种环境下发生 （1）当一个进程从运行状态切换到等待状态（如：I/O请求，或调用P等待一个子进程的终止） （2）当一个进程从运行状态切换到就绪状态（如：当出现中断时） （3）当一个进程从等待状态切换到就绪状态（如：I/O完成，抢占式调度） （4）当一个进程终止时 对于1和4,没有选择而只有调度。当调度只能发生在

8、1和4时，调度方案是非抢占的。Windowx 3.x是非抢占的，Windows 95开始是抢占的。Mac OS X是抢占的。,2020/7/6,12,进程调度方式 1)非抢占式 2)抢占式 基于的原则 (1)优先权原则 (2)短作业优先 (3)时间片原则。,2020/7/6,13,3、中级调度：中程调度 目的：提高内存利用率和系统吞吐量。实际是存储器管理中的对换功能。 作业1：处理机的三级调度分别在什么情况下发生？各级调度分别完成什么工作？（西北大学2000年研究生试题） 解：（1）高级调度主要用在批处理系统中，并在需要从外存的后备队列向内存调入作业运行时发生；中级调度在内存紧张而无法满足运行

9、作业的要求时发生；低级调度是在执行进程运行完毕、执行进程转入阻塞状态、执行进程的时间片用完、有比现行进程更紧迫的进程到达并允许它抢占CPU等情况下发生的。,2020/7/6,14,（2）高级调度的主要工作是根据调度算法决定把外存后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程插入到就绪队列上等待执行。中级调度的工作是在内存紧张时，将内存中暂时不能运行的进程调出至外存，并在内存空闲时再将外存中具备运行条件的就绪进程调入内存。低级调度的主要工作是根据一定的调度算法，决定就绪进程中的哪一个进程将获得CPU，并将CPU分派给它。,2020/7/6,15,例：引起进

10、程调度的原因有哪些？ 解： （1）进程正常终止或异常终止 （2）正在执行的进程因某种原因而阻塞 a. 提出I/O请求后被阻塞 b. 在调用P操作时因资源不足而阻塞 c. 因其他原因执行block原语而阻塞等。 （3）在引入时间片的系统中，时间片用完 （4）在抢占调度方式中，就绪队列中某进程的优先权变得比当前正在执行的进程高，或者有优先权更高的进程进入就绪队列。,2020/7/6,16,注意： 当系统中只有一个进程且它具备执行条件时，或者系统中只有一个进程具备执行条件而其他的进程均处于阻塞状态时，系统中便会出现只存在运行进程却没有就绪进程的现象。 如果系统中的所有进程均处于阻塞状态，则系统中便会

11、出现既没有运行进程也没有就绪进程的现象。 系统中不会出现只有就绪进程，却没有运行进程的现象。,2020/7/6,17,3.2 调度队列模型和调度准则 1、仅有进程调度的调度队列模型 进程的运行情况： (1)在规定的时间内完成 (2)时间片用完 (3)提出了I/O请求。,2020/7/6,18,2、具有高级和低级调度的调度队列模型 (1)就绪队列的形式：最高优先级优先调度算法。 (2)设置多个阻塞队列。 3、同时具有三级调度的调度队列模型 4、选择调度方式和调度算法的若干准则 (1)面向用户的准则：周转时间T和带权周转时间W。 周转时间T后备作业队列+就绪队列+阻塞队列+CPU运行时间 等待时间

12、和运行时间 完成时间-到达时间 带权周转时间W周转时间/服务时间 1+等待时间/服务时间,2020/7/6,19,(2)面向系统的准则：系统吞吐量，处理机利用率，各类资源的平衡利用。 整体准则：使CPU使用率和吞吐量最大化，使周转时间、等待时间和响应时间最小化，需要优化平均值，有些情况需要优化最小值或最大值。,2020/7/6,20,批处理作业的调度： 先来先服务算法： 计算时间短的作业优先算法： 响应比高者优先算法:仅适用于作业调度 优先数调度算法,2020/7/6,21,3.3 调度算法：根据系统的资源分配策略所规定的资源分配算法。 1、先来先服务和短作业(进程)优先调度算法。 1)FCF

13、S：先形成FIFO队列，作业调度和进程调度。甘特图Gantt 特点：非抢占，有利于长作业，不利于短作业，有利于CPU繁忙型作业，不利于I/O繁忙型作业。或CPU区间时间变化大，其平均等待时间变化就很大。所有进程等待一个大进程释放CPU，称为护航效果convoy effect，不适于分时系统。允许一个进程保持CPU时间过长是个严重错误。,0,24,27,30,2020/7/6,22,甘特图，也称为横道图(Bar chart)。是在1917年由亨利甘特开发的，其内在思想简单，基本是一条线条图，横轴表示时间，纵轴表示活动(项目)，线条表示在整个期间上计划和实际的活动完成情况。它直观地表明任务计划在什

14、么时候进行，及实际进展与计划要求的对比。,2020/7/6,23,2)SJF或SPF： 特点：抢占（最短剩余时间优先）或非抢占对长作业不利，未考虑作业的紧迫程序，作业的长短只能估计。 SJF算法可证明在长期调度中为最佳的（前提条件是所有作业同时到达或所有作业都到达后才进行调度），通过将短进程移到长进程之前，短进程等待时间的减少大于长进程等待时间的增加，因而，平均等待时间减少了。 问题：如何知道下一个CPU区间的长度。在短期调度中不容易实现。,0,3,9,16,24,2020/7/6,24,2020/7/6,25,调 度 算 法,作 业 情 况,2.1,2.25,1.5,3.2,2.67,1,带

15、权周转时间,8,9,3,16,8,4,周转时间,13,6,18,9,4,完成时间,2.8,3.5,5.5,2,2,1,带权周转时间,9,14,11,10,6,4,周转时间,18,14,12,7,4,完成时间,4,2,5,3,4,服务时间,4,3,2,1,0,到达时间,平均,E,D,C,B,A,进程名,FCFS(a),SJF(b),2020/7/6,26,作业2：若在后备作业队列中等待运行的同时有三个作业1、2、3，已知它们各自的运行时间为a,b,c，且满足关系abc，试证明采用短作业优先算法能获得最小平均周转时间。,2020/7/6,27,例：试证明，短作业优先的作业调试算法可以得到最短的平均

16、响应时间。（北京大学1990年研究生试题） 证明：假设有n个作业J1，J2,，Jn，它们各自的运行时间分别为T1,T2,，Tn，当作业的调度次序为Ji1,Ji2,.,Jin时，则平均响应时间T为： TTi1+(Ti1+Ti2)+(Ti1+Ti2+Ti3)+(Ti1+Ti2+Tin)/n=nTi1+(n-1) Ti2+1Tin/n。由于nn-1n-2.1，因此，当Ti1=Ti2=.=Tin时，平均响应时间T最短。故短作业优先的作业调度算法可以得到最短的平均响应时间。,2020/7/6,28,2、高优先权优先调度算法HPF SJF属于简单优先级算法，其优先级为下一个CPU区间的倒数。实质上FCFS

17、也属于简单优先级算法，其优先级为等待时间。 1)优先权调度算法的类型 (1)非抢占式 (2)抢占式,2020/7/6,29,优先级可通过内部或外部方式定义： 内部定义优先级使用一些测量数据以计算进程优先级。如：时间极限、内存要求、打开文件的数量和平均I/O区间与平均CPU区间之比等。 外部定义优先级通过操作系统之外的准则来定义，如：进程的重要性，用于支付的费用类型和数量、赞助工作的单位、其他（政治）等因素。,2020/7/6,30,问题：无穷阻塞或饥饿。1973年关闭MIT的IBM 7094时，发现有一个低优先级进程是1967年提交但是一直还未运行。低优先级进程无穷等待问题的解决之一是老化ag

18、ing，逐渐增加等待很长时间的进程的优先级。,2020/7/6,31,2)优先权的类型 (1)静态优先权:优先数，小数表示大权，或反之。 确定进程优先权的依据：进程类型、进程对资源的需求，用户要求。 (2)动态优先权:随着进程的推进而改变。防止一个低优先权的进程处于饥饿状态或防止一个长进程长期霸占CPU。,2020/7/6,32,3)高响应比优先调度算法HRN。 优先权=(等待时间+服务时间)/服务时间 兼顾了短作业和先来先服务的优点。既考虑了等待时间又考虑了运行时间。,2020/7/6,33,2009年,2、下列进程调度算法中，综合考虑进程等待时间和执行时间的是(D ) A 时间片轮转调度算

19、法 B 短进程优先调度算法 C 先来先服务调度算法 D 高响应比优先调度算法,2020/7/6,34,作业3、（北京大学95年试题）有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。,2020/7/6,35,要求： （1）列出所有作业进入内存时间及结束时间 （2）计算平均周转时间(以分钟计算),2020/7/6,36,作业4、假设有四个作业，它们的提交、执行时间如下表所示。若采用响应比高者优先调度算法，试问平均周转时间和平均带权周转时间为多少？,2020/7/6,3

20、7,3、基于时间片的轮转调度算法。专为分时系统设计，类似于FCFS，增加了抢占 1)时间片轮转法RR (1)基本原理:怎么轮转？ (2)时间片大小的确定：time quantum,or time slice,一般为10100ms,过大会成为FCFS，过小该算法称为处理器共享。 经验：80%的CPU区间应该小于时间片。,时 间 片,作 业 情 况,2.5,3.33,5,2.25,2,1,带权周转时间,8.4,13,10,9,6,4,周转时间,17,13,11,7,4,完成时间,3.46,3.33,3,3.5,3.67,3.75,带权周转时间,11.8,13,6,14,11,15,周转时间,17,

21、9,16,12,15,完成时间,4,2,4,3,4,服务时间,4,3,2,1,0,到达时间,平均,E,D,C,B,A,进程名,RR q=1,RR q=4,2020/7/6,39,作业5： 一、进程调度算法计算题（华师大2002年试题） 假定有进程，它们的提交时间、运行时间如下： 作业号到达时间运行时间开始时间结束时间 103 224 342 464 要求： 1、采用先来先服务算法，分别计算这批进程的平均轮转时间、平均带权轮转时间 2、采用时间片轮转算法（时间片Q=2），分别计算这批进程的平均轮转时间、平均带权轮转时间。,2020/7/6,40,作业6、有5个批任务几乎同时到达，其预计的运行时间

22、A,B,C,D,E分别为6，10，2，8，4分，计算其在时间片轮转算法下的平均进程周转时间。（进程切换开销可以忽略）,2020/7/6,41,2)多级队列调度算法：将就绪队列分成多个独立队列。按照进程的属性、进程优先级、进程类型，一个进程被永久分配到一个队列。每个队列有自己的调度算法。如：前台（交互）进程和后台（批处理）进程处于不同的队列。前台采用RR算法，后台采用FCFS算法。队列间采用固定优先级抢占调度算法。前台比后台具有绝对的优先级。 如： （1）系统进程 （2）交互进程 （3）交互编辑进程 （4）批处理进程 （5）学生进程 特点：进程不能在队列之间移动，调度开销低。缺点：不够灵活,3)

23、多级反馈队列调度算法FB：满足各类用户的需求。 例三、利用甘特图分析右面例子,2020/7/6,44,例1、假设有一个系统中有5个进程，它们的到达时间和服务时间如表所示，忽略I/O以及其他开销时间，若分别按高响应比优先、非抢占及抢占的短进程优先调度算法进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间,2020/7/6,45,2020/7/6,46,例2、设有四道作业，它们的提交时间及执行时间如下：,2020/7/6,47,试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法进的平均周转时间和平均带权周转时间，并指出它们的调度顺序。（

24、时间单位：小时，以十进制进行计算）,2020/7/6,48,解：采用先来先服务调度算法，则其调度顺序为1、2、3、4。,2020/7/6,49,平均周转时间：T=(2.0+2.8+3.1+3.3)/4=2.8 平均带权周转时间：W=(1+2.8+6.2+11)/4=5.25 采用短作业优先调度算法自己练习T=2.45,W=3.85。,2020/7/6,50,例3、下表给出作业1、2、3的到达时间和运行时间。采用短作业优先调度算法和先来先服务调度算法，试问平均周转时间各为多少？是否还有更好的调度策略存在？（时间单位：小时，以十进制进行计算）。,2020/7/6,51,2020/7/6,52,采用

25、先来先服务调度算法：平均周转时间T=10.53 采用短作业优先调度策略，顺序：1、3、2平均周转时间T=9.53 存在缩短平均周转时间的策略，即还有两个短作业，等所有作业都到达后，再按短作业优先调度算法调度，顺序：3、2、1，平均周转时间T=6.87,2020/7/6,53,作业6、在一个两道的批处理操作系统中，有6个作业到达系统，它们的到达时刻、估计运行时间和优先级如下表所示. 作业号 到达时刻 进入内存时刻 估计运行时间 优先级 JOB1 8：00 90分钟 5 JOB2 8：10 30分钟 6 JOB3 8：30 20分钟 3 JOB4 8：50 15分钟 8 JOB5 9：20 10分

26、钟 2 JOB6 9：40 5分钟 4 系统采用短作业优先作业调度算法，作业一旦被调度运行就不再退出.但当有新的作业投入运行时，可以按照优先级进行进程调度(数越小优先级越大). 试给出每个作业的运行时间(段)序列.（例如：JOB1：8：00-8：30，9：10-9：20，） 试计算出作业的平均周转时间,2020/7/6,54,2012年,29、一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达，它的计算和I/O操作顺序如下： P1：计算60ms，I/O80ms，计算20ms P2:计算120ms，I/O40ms，计算40ms 若不考虑调度和切换时间，则完成两个作业需要的时间最少

27、是（） A 240ms B 260ms C 340ms D 360ms,2020/7/6,55,30、若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中错误的是（） A 在进程结束时能进行处理机调度 B 创建新进程后能进行处理机调度 C 在进程处于临界区时不能进行处理机调度 D 在系统调用完成并返回用户态时能进行处理机调度,2020/7/6,56,线性优先级调度策略(SRR)selfish round robin,新创建的进程按FCFS排成就绪队列A，而其他已得到过时间片服务的进程也按FCFS排成另一个就绪队列或称享受服务队列B。 对两个不同队列中的进程，设置不同的优先级P

28、。 A中的优先级以a的速率增加： Pa*t (a0) B中的优先级以b的速率增加： Pb*t (ab0),2020/7/6,57,所以，某一进程在t1被创建，在t时刻 ,该进程的优先级为 P(t)=a*(t-t1) 若该进程在t2时刻转入B队列中，则在时刻t，该进程的优先级为 P(t)=a*(t2-t1)+b*(t-t2),2020/7/6,58,当A队列中的第一个进程优先级和B队列中最后一个进程的优先级相等时，A中的第一个进程可以转入B队列。或当B队列为空时，A中的第一个进程可转入B队列。,2020/7/6,59,显然，ab0的条件是必要的。 若ba0时，两个队列中优先级永远不会相等，B中永

29、远只有一个进程，转化成了FCFS算法。 若ab=0时，则转化为RR法。,2020/7/6,60,基于公平原则的调度算法,1、保证调度算法：明确的性能保证。 2、公平分享调度算法：分配给每个进程相同的处理机时间。,2020/7/6,61,3.4 实时调度(略),1、实现实时调度的基本条件 1)提供必要的信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级 2)系统处理能力强 3)采用抢占式调度机制 4)具有快速切换机制：对外部中断的快速响应能力、快速的任务分派能力。,2020/7/6,62,2、实时调度算法的分类 1)非抢占式调度算法：轮转调度算法和优先级调度算法。小型实时系统

30、或要求不太严格的实时控制系统中。 2)抢占式调度算法：要求较严格的实时系统中。 (1)基于时钟中断的抢占式优先权调度算法 (2)立即抢占的优先权调度算法,2020/7/6,63,3、常用的几种实时调度算法 1)最早截止时间优先EDF算法:根据任务的开始截止时间来确定任务的优先级，开始截止时间越早，优先级越高。系统保持一个实时任务就绪队列，按截止时间的早晚排序。抢占式或非抢占式。 2)最低松弛优先LLF算法：根据实时任务的松驰度（松驰度任务必须完成的时间任务本身的运行时间当前时间）来确定任务的优先权，松驰度越低，优先权越高。系统中保持一个按松驰度排序的实时任务就绪队列，主要用抢占式。,2020/

31、7/6,64,多处理机调度（略）,1、对称多处理器系统SMPS：各处理器在功能和结构上都是相同的。 非对称多处理器系统，采用主从式结构，OS的核心程序在某个特定的（主）处理器，其他（从）处理器执行用户程序，进程调度由主处理器执行。 2、进程分配方式 静态分配方式：一个进程从开始执行到完成，被固定分配到一个处理器上执行。每个处理器维护一个专用就绪队列。 动态分配方式：系统设置一个公用的就绪队列，被随机调度到任一空闲的处理器上执行。,2020/7/6,65,3、进程调度方式 （1）自调度方式：系统中设置一个公用的进程队列，所有的处理器在空闲时，都可自己到该队列中取一进程（或线程）来执行。 （2）成

32、组调度方式：将一组相互合作的进程或隶属于同一个进程的一组线程分配到一组处理器上去同时执行。 （3）专用处理器分配方式。在一个应用程序的执行期间，专门为该应用程序分配一组处理器，每一个线程一个处理器，这组处理器仅供该应用程序专用，直到该程序完成。,2020/7/6,66,死锁的一种规范定义,如果一个进程集合中的每个进程都在等待只能由该组进程中的其他进程才能引发的事件，那么，该组进程是死锁的。DeadLock。事件是资源获取和释放。 资源包括物理资源（打印机、磁带驱动器、内存空间和CPU周期）或逻辑资源（文件、信号量和管程）,2020/7/6,67,所谓死锁，是指多个进程因竞争资源而造成的一种僵局

33、，若无外力作用，这些进程永远不能再向前推进。 进程使用资源的顺序 （1）申请：relquest(设备)、open(文件)、allocate(内存) （2）使用 （3）释放： release(设备)、close(文件)、free(内存),2020/7/6,68,3.5 产生死锁的原因和必要条件,资源的分类：可重用资源和消耗性资源、可抢占资源和不可抢占资源。 1、产生死锁的原因：竞争资源和进程间推进顺序非法。 2、产生死锁的必要条件：互斥条件、请求和保持条件、不剥夺条件和环路等待条件。 3、处理死锁的基本方法：,2020/7/6,69,(1)预防死锁：deadlock-prevention,三种。

34、 互斥：一般不能被破坏 占有并等待：一种协议是一次性资源分配法，二种协议是一个进程申请其他资源前，必须释放其已分配的所有资源。 非抢占：一个进程占有资源并申请另一个不能立即分配的资源，那么其已有的资源都可被抢占。一个进程要重新执行，必须分配到其所申请的资源，并恢复其等待时被抢占的资源。仅适用于CPU寄存器和内存，不适于其他资源 循环等待：有序资源分配法 以上方法的副作用是低设备使用率和系统吞吐量。,2020/7/6,70,(2)避免死锁：deadlock-avoidance, 银行家算法:安全性算法，资源请求算法,2020/7/6,71,(3)检测死锁：死锁定理(资源分配图和进程化简)， 必须

35、：保存有关资源的请求和分配信息；提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。 每个资源类中只有一个资源的死锁检测。必须采用两个表：进程占用（资源）表和等待（资源）表。前者记录哪些进程占用了什么资源，后者记录处于等待资源状态的进程正在等待什么资源。 死锁检测程序反复检测这两张表，列出所有等待占用关系，若其中有一组进程循环等待资源，则系统出现了死锁。 (4)解除死锁：剥夺资源和撤消进程 (5)鸵鸟算法：UNIX和Windows,2020/7/6,72,例1、产生死锁的必要条件是什么？解决死锁问题常用哪几种措施？（中科院计算所1997年研究生试题） 例2、要使一个系统不发生死锁，一般可

36、采用哪些方法？简述它们的实现原理（中国科技大学1998年研究生试题）,2020/7/6,73,例3、什么是饥饿？死锁与饥饿的主要差别是什么？ 解：饥饿并不表示系统一定会发生死锁，但至少有一个进程的执行被无阻期地推迟。饥饿与死锁的主要差别有： （1）进入饥饿状态的进程可以只有一个，而由于循环等待条件，进入死锁状态的进程却必须大于或等于两个； （2）处于饥饿状态的进程可以是一个就绪进程，如静态优先权调度算法时的低优先权就绪进程，而处于死锁状态的进程则必定是阻塞进程。,2020/7/6,74,2009年,3、某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生

37、死锁的K的最小值是( C ) A 2 B 3 C 4 D 5,2020/7/6,75,发生死锁的现象就是占有并等待，并且等待的资源不会释放。可假设死锁已发生，进而讨论进程个数。肯定发生死锁的最小进程数是这样得到的：假设K个进程，每个进程需要M个资源，而每个进程已占有M-1个，都在等待最后一个资源，于是死锁发生；此时，只要再多一个资源，死锁便可解除，K便是所求值。根据题目条件，M3，K（M-1）=8，得K4。,2020/7/6,76,4、银行家算法 (1)安全状态 (2)银行家算法的数据结构 (3)银行家算法的步骤 (4)安全性算法。,2020/7/6,77,2012年,27、假设5个进程P0、

38、P1、P2、P3、P4共享三类资源R1、R2、R3，这些资源总数分别为18、6、22。T0时刻的资源分配情况如下表所示，此时存在的一个安全序列是,2020/7/6,78,A P0,P2,P4,P1,P3 B P1,P0,P3,P4,P2 C P2 D P3,P4,P2,P1,P0,2020/7/6,79,2013年,31、某系统正在执行三个进程P1、P2和P3，各进程的计算(CPU)时间和I/O时间比例如下表所示 为提高系统资源利用率，合理的进程优先级设置应为 A P1P2P3 B P3P2P1 C P2P1=P3 D P1P2=P3,2020/7/6,80,2013年,32、下列关于银行家算

39、法的叙述中，正确的是 A 银行家算法可以预防死锁 B 当系统处于安全状态时，系统中一定无死锁进程 C 当系统处于不安全状态时，系统中一定会出现死锁进程 D 银行家算法破坏了死锁必要条件的中“请求和保持”条件,2020/7/6,81,作业7：设系统中有3种类型的资源（A，B，C）和5个进程P1,P2,P3，P4,P5,A资源的数量为17,B资源的数量为5,C资源的数量为20。在T0时刻系统状态如表所示。系统采用银行家算法实现死锁避免策略。（北京大学1997年研究生试题）,2020/7/6,82,2020/7/6,83,(1)T0时刻是否为安全状态？若是，请给出安全序列。 (2)在T0时刻若进程P

40、2请求资源(0，3,4),是否能实施资源分配，为什么？不能 (3)在(2)的基础上，若进程P4请求资源(2,0,1),是否能实施资源分配？为什么？能 (4)在(3)的基础上，若进程P1请求资源(0,2,0)，是否能实施资源分配？为什么？不能,2020/7/6,84,例1：Dijstra 1965年提出的银行家算法其主要思想是什么？它能够用来解决实际中的死锁问题吗？为什么？（中科院1996年研究生试题、浙江大学1997年研究生试题） 解：银行家算法的主要思想是避免系统进入不安全状态。在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，如果有，则先试行分配，并对分配后的新状态进行安全性检

41、查。如果新状态安全，则正式分配上述资源，否则就拒绝分配上述资源。这样，它保证系统始终处于安全状态，从而避免死锁现象的发生。,2020/7/6,85,在银行家算法中，是根据每个进程对资源的最大需求来进行安全性检查的；另外，在整个过程中，进程的数目固定不变。由于实际应用中，在每次进程运行之前，系统难以了解其对资源的最大需求；而在整个过程中，可能不断地有进程终止、或有新进程被创建，所以进程的数目是动态变化的。因此，用银行家算法来解决实际中的死锁问题存在一定的困难,2020/7/6,86,作业8、在银行家算法中，若出现下述资源分配情况：,2020/7/6,87,试问： (1)该状态是否安全？P0，P3

42、，P4，P1，P2 (2)如果进程P2提出请求Request2(1,2,2,2)后，系统能否将资源分配给它？,2020/7/6,88,例3、考虑由n个进程共享的具有m个同类资源的系统，证明：如果对i=1,2,.,n，有need0而且所有最大需求量之和小于m+n，那么该系统是死锁无关的。（西北工业大学2000年研究生试题） 证明：对n个进程中的任何k个进程，它们的最大需求之和等于n个进程的最大需求量之和与其余n-k个进程的最大需求量之和两者之差。由于每个进程的最大需求必定大于等于1,故其余n-k个进程的最大需求量之和必定大于等于n-k。当n个进程的最大需求量之和小于m+n时，上述k个进程的最大需

43、求量之和必定小于(m+n)-(n-k)，即m+k。也就是说，当n个进程的最大需求量之和小于m+n时，其中任何k个进程，它们的最大需求量之和都将小于m+k。 对n个进程中的任何k个进程，假设它们分别为Pj1,Pjk，如果它们因竞争上述m个资源而发生死锁，则必有： Allocation=m即系统已无空闲的资源，以及Needi0,因此可得到： Needi=k,从而进一步可得到：Maxi=Needi+Allocationi=k+m 这个结论是与“任何k个进程，它们的最大需求量之和都将小于m+k”相矛盾。因此，当系统的资源已全部分配出去时，k个进程中必定存在一个进程，其Needi=0,也就是说，它已获得

44、了全部所需资源，能够顺利完成，故系统中不可能发生k个进程的死锁现象。由于，1k=n，因此，系统中的n个进程不可能因为竞争m个同类资源而发生任何死锁现象。,2020/7/6,89,判断题,1、程序的并发执行失去程序的封闭性和再现性，程序和机器执行程序活动一一对应。（陕西省1997年自考），不再一一对应。 2、进程由进程控制块和数据集以及对该数据集进行操作的程序段组成。（清华大学1998年研究生试题） 3、进程具有并发性，它能与其他进程并发执行。（陕西省1997年自考） 4、进程是一个独立的运行单位，也是系统进行资源分配和调度的基本单位。（西安电子科技大学2000年研究生试题），未引入线程的系统中

45、。 5、进程是程序执行的动态过程，而程序是进程运行的静态文本。（陕西省1997年自考）,2020/7/6,90,6、在单处理机上的进程就绪队列和阻塞队列最多只能有一个。（陕西省1995年自考） 7、进程从运行态转变为就绪状态的原因一定是时间片用完。 8、一个进程的状态变化总会引起其他一些进程的状态发生变化。 9、进程申请CPU得不到满足时，其状态变为等待状态。 10、一次仅允许一个进程使用的资源叫临界资源，所以对临界资源是不能实现共享的。 11、临界区是指进程中用于实现进程互斥的那段代码。 12、信号量的初值不能是负的。,2020/7/6,91,13、P、V操作是操作系统中进程低级通信原语。（

46、陕西省1998年自考） 14、进程在要求使用某一临界资源时，如果资源正被另一进程所使用，则该进程必须等待，当另一个进程使用完并释放后方可使用，这种情况即所谓进程间同步。（陕西省1995年自考）。这叫互斥 15、死锁是一种与时间有关的错误，它与进程推进的速度无关。（陕西省1996自考） 16、采用资源的静态分配算法可以预防死锁的产生。（西安电子科技大学2000年研究生试题） 17、某系统由相同类型的4个资源组成，若资源可被3个进程申请使用，每个进程最多可申请2个资源，则该系统不会发生死锁。 18、在死锁的避免方法中，仅当系统处于安全状态时，才实施分配。 19、在剥夺式进程管理方式下，现运行进程的

47、优先级不低于系统中所有进程的优先级。（陕西省1997年自考） ，仅高于就绪进程，可低于阻塞进程。 20、某一进程被中断，转去执行中断处理程序，中断处理程序结束后， 一定返回到被中断的程序。 （陕西省1998年自考）,2020/7/6,92,单项选择题,1、多道程序设计是指（）（西安电子科技大学2002年研究生试题） A 在实时系统中并发运行多个程序 B 在分布式系统中同一时刻运行多个程序 C 在一台处理机上同一时刻运行多个程序 D 在一台处理机上并发运行多个程序 2、一个进程是（）。（清华大学1996年研究生试题） A 由协处理机执行的一个程序 B 一个独立的程序+数据集 C PCB结构与程序

48、和数据的集合D 一个独立的程序,2020/7/6,93,3、下列几种关于进程的叙述，（）最不符合操作系统对进程的理解。（浙江大学1998年研究生试题） A 进程是在多程序环境中的完整的程序 B 进程可以由程序、数据和进程控制块描述 C 线程是一种特殊的进程 D 进程是程序在一个数据集合上的运行过程，它是系统进行资源分配和调度的一个独立单元。 4、现代操作系统中申请资源的基本单位（A），在CPU得到执行的基本单位（B），（A）是由（C）组成的，它与（B）的区别之一是（D）。（东南大学2000年研究生试题） A、B：（1）模块；（2）作业；（3）线程；（4）管程；（5）进程；（6）类程；（7）例程

49、 C： （1）入口，过程，出口；（2）正文，数据，堆栈；（3）正文段，数据段，PCB；（4）正文，数据，JCB。 D： （1）A的并发粒度比B的大；（2）A的并发粒度比B的小；（3）A是动态的，而B是静态的；（4）A有后备状态，而B没有。,2020/7/6,94,5、支持多道程序设计的操作系统在运行过程中，不断地选择新进程运行来实现CPU的共享，但其中（）不是引起操作系统选择新进程的直接原因。（复旦大学1999年研究生试题） A 运行进程的时间片用完 B 运行进程出错 C 运行进程要等待某一时间发生 D 有新进程进入就绪状态。 6、在非剥夺调度方式下，当（）时，不会引起一进程从就绪态变为运行态

50、。 A 一个进程被创建后进入就绪态 B 一个进程从运行态变成等待态 C 运行的进程执行结束 D 一个进程从运行态变成就绪态,2020/7/6,95,7、系统中有n(n2)个进程，并且当前没有执行进程调度程序，则（）不可能发生。 A 有一个运行进程，没有就绪进程，剩下的n-1个进程处于等待状态。 B 有一个运行进程和n-1个就绪进程，但没有进程处于等待状态。 C 有一个运行进程和1个就绪进程，剩下的n-2个进程处于等待状态。 D 没有运行进程但有2个就绪进程，剩下的n-2个进程处于等待状态。 8、在多进程的系统中，为了保证公共变量的完整性，各进程应互斥进入临界区，所谓临界区是指（）。（清华大学1

51、996年研究生试题） A 一个缓冲区 B 一段数据区 C 同步机制 D 一段程序 9、在操作系统中，P、V操作是一种（）。（西安交通大学1999年研究生试题） A机器指令 B系统调用命令 C作业控制命令 D低级进程通信原语,2020/7/6,96,10、若有3个进程共享一个互斥段，每次最多允许2个进程进入互斥段，则信号量的变化范围是（）。（陕西省1998年自考） A 2,1,0,-1 B 3,2,1,0 C 2,1,0,-1,-2 D 1,0,-1,-2 11、设有4个作业同时到达，每个作业的执行时间均为2个小时，它们在一台处理机上按单道方式运行，则平均周转时间为（）。 A 1小时 B 5小时

52、 C 2.5小时 D 8小时,2020/7/6,97,12、现有3个同时到达的作业J1,J2,J3,它们的执行时间分别是T1,T2,T3,且T1T2T3。系统按单道方式运行且采用短作业优先算法，则平均周转时间是（）。（西安电子科技大学2002年研究生试题） A T1+T2+T3 C (3T1+2T2+T3)/3 B (T1+T2+T3)/3 D (T1+2T2+3T3)/3 13、哪一个说法对剥夺式系统来讲结论正确（）。（北京理工大学1999年研究生试题） A若系统采用轮转法调度进程，则系统采用的是剥夺式调度 若现行进程要等待某一事件时引起调度，则该系统是剥夺式调度 实时系统通常采用剥夺式调度

53、 在剥夺式系统中，进程的周转时间较之非剥夺式系统可预见。 14、假设就绪队列中有10个进程，系统将时间片设为200ms,CPU进行进程切换要花费10ms。则系统开销所占的比率约为（） A 1% B 5% C 10% D 20%,2020/7/6,98,15、既考虑作业等待时间又考虑作业执行时间的调度算法是（） A 响应比高者优先 B 短作业优先 C 优先级调度 D 先来先服务 16、调度算法与作业的估计运行时间有关的是（）算法。 A 先来先服务 B 均衡 C 短作业优先 D 时间片轮转 17、设m为同类资源数，n为系统中并发进程数。当n个进程共享m个互斥资源时，每个进程的最大需求是w，则下列情

54、况会出现系统死锁的是（） A m=2,n=1,w=2 B m=2,n=2,w=1 C m=4,n=3,w=2 D m=4,n=2,w=3,2020/7/6,99,18、假设系统由相同类型的9个资源被4个进程共享，试分析每个进程最多可以请求多少个资源数时该系统仍无死锁。（） A 1 B 2 C 3 D 4,2020/7/6,100,填空题,1、在一个单处理机系统中，若有5个用户进程，且假设当前时刻为用户态，则处于就绪状态的用户进程最多有4个，最少有0个。 2、如果系统中有n个进程，则在等待队列中进程的个数最多为n个。（北京大学1997年研究生试题） 3、操作系统中，对信号量S的P原语操作定义中，

55、使进程进入相应等待队列等待的条件是S.value0 4、如果信号量的当前值为-4,则表示系统中在该信号量上有4个等待进程。（北京大学1997年研究生试题）,2020/7/6,101,5、用户与操作系统之间的接口主要分为命令接口和系统调用接口两类。（中国科技大学1998年研究生试题） 6、确定作业调度算法是应注意系统资源的均衡使用，使计算型作业和I/O型作业搭配运行。 7、如果系统中所有作业是同时到达的，则使作业平均周转时间最短的作业调度算法是短作业优先调度算法。（北京大学1997年研究生试题） 8、在先来先服务调度算法中，按照进程进入就绪队列的先后次序来分配处理机。,2020/7/6,102,

56、基础要点,考核要点：各种进程调度算法，死锁的概念，死锁产生的原因和必要条件，处理死锁的方法，银行家算法。 本章基础要点： （1）若要使当前运行进程总是优先级最高的进程，则应该选择可剥夺优先级调度算法。 （2）在分时系统中，进程调度经常采用时间片轮转调度算法。,2020/7/6,103,（3）死锁产生的四个必要条件是：互斥、部分分配、不剥夺和环路等待。 （4）进程运行结束、进入阻塞状态、时间片用完、有更高优先级的进程进入就绪队列等原因均可引起进程调度。 （5）进程调度算法采用等时间片轮转法时，时间片过大，就会使轮转法转化为先来先服务调度算法。,2020/7/6,104,（6）进程的调度方式有两种

57、，一种是可剥夺方式，另一种是不可剥夺方式。 （7）当处理机空闲时，进程调度程序从就绪队列中选取一个进程执行。 （8）最简单的进程调度算法是先来先服务调度算法。,2020/7/6,105,（9）在有m个进程的系统中出现死锁时，死锁进程的个数k应该满足的条件是2=k=m。 （10）一种最常用的进程调度算法是把处理机分配给具有最高优先级的进程。而确定优先级的方法概括起来不外是基于静态特性和动态特性两种方法。前者所得到的是静态优先级，后者所得到的是动态优先级。,2020/7/6,106,（11）不让死锁发生的策略可以分为静态和动态两种，死锁避免属于动态策略。 （12）在为多道程序所提供的可共享系统资源

58、不足时，可能出现死锁。但是，不适当的进程推进顺序也可能产生死锁。 （13）在“进程资源”图中，资源Rj分配给进程Pi应表示为（Rj,Pi）。,2020/7/6,107,（14）采用资源剥夺法可以解除死锁，还可以采用撤消进程方法解除死锁。 （15）静态优先级是在进程创建时确定的，确定之后在整个进程运行期间不再改变。,2020/7/6,108,（16）某系统中有3个并发进程，都需要同类资源4个，该系统不会发生死锁的最少资源个数是10。 （17）发生死锁的必要条件有四个，要防止死锁的发生，可以破坏这四个必要条件，但破坏互斥条件是不太实际的。 （18）资源的按序分配策略可以破坏环路等待条件。,2020/7/6,109,（19）银行家算法中，当一个进程提出的资源请求将导致系统从安全状态进入不安全状态时，系统就拒绝它的资源请求。 （20）预先静态分配法破坏了死锁产生必要条件中的部分分配条件。,2020/7/6,110,练习题及参考答案,1、某系统有同类资源m个，供n个进程共享。如果每个进程最多申请x个资源（其中1=x=m）。请证明：当n(x-1)+1m时，系统不会发生死锁。 2、产生死锁的必要条件是什么？解决死锁问题常用哪几种措施？ 3、某进程被唤醒后立即投入运行，我们就说这个系