chapter3_调度与死锁概要

《chapter3_调度与死锁概要》由会员分享，可在线阅读，更多相关《chapter3_调度与死锁概要（159页珍藏版）》请在金锄头文库上搜索。

1、计算机操作系统,济宁医学院信息工程学院,课程主要内容,操作系统引论（1章） 进程管理（2-3章） 存储管理（4章） 设备管理（5章） 文件管理（6章） 操作系统接口（7章）,第2章 进程管理,进程的基本概念与控制 进程的基本概念 进程控制 线程的基本概念 进程同步与通信 进程同步 经典进程的同步问题 管程机制 进程通信,第3章 处理机调度与死锁,在多道程序环境下，一个作业从提交到执行，通常都要经历多级调度，如高级调度、低级调度、中级调度等。而系统的运行性能在很大程序上取决于调度，因此调度便成为多道程序的关键。 在多道程序环境下，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能

2、力，然而，多个进程的并发执行也带来了新的问题-死锁。,3.1处理机调度的层次和调度算法的目标 3.2作业与作业调度 3.3进程调度 3.4实时调度,3.5产生死锁的原因和必要条件 3.6死锁预防和避免的方法 3.7死锁的检测与解除 本章作业,第3章 处理机调度与死锁,3.1 处理机调度的基本概念,一、调度的层次 二、处理机调度算法的目标,返回目录,目标： 1、理解处理机调度的三级调度各自的含义，会区分这三种调度； 2、理解抢占式调度和非抢占式调度这两种调度方式的概念，知道时间片轮转等调度算法是抢占式的还是非抢占式的； 3、了解调度算法的准则。 重点/难点：三级调度之间的比较和含义（可命制单项选

3、择题）,掌握常见的几种调度算法，做到能根据系统中各个进程的属性和到达情况按常见的调度算法调度多个进程执行的顺序； 2、理解等待时间、周转时间和加权周转时间的含义，做到会计算它们； 3、了解实时调度。 重点/难点： 1、常见调度算法的比较(可命制单选题) 2、用常见调度算法调度当前系统，并计算平均周转时间、平均加权周转时间、平均等待时间(可命制综合应用题),提交,输入管理系统,作业调度,SPOOLING 输出,后备,退出,完成,就绪,阻塞,中级调度,进程调度,一、调度的层次,一、调度的层次,1、高级调度（长程/作业/宏观调度） （1）从外存后备队列中选择作业进入就绪队列或挂起就绪. （2）在批处

4、理系统中,大多配有作业调度,但在分时系统及实时系统中,一般不配置. （3）作业调度执行频率很低,通常为几分钟一次,甚至更久。,一、调度的层次,2、低级调度（进程/短程调度） （1）决定哪个进程应获得处理机 （2）由分派程序将处理机分配给选中的进程。 （3）进程调度执行频率很高,通常为10100ms。,一、调度的层次,3、中级调度（中程/交换调度） 在内存和外存对换区之间按照给定的原则和策略选择进程对换，以解决内存紧张问题，从而提高内存的利用率和系统吞吐量，常用于分时系统或具有虚拟存储器的系统中。,二、处理机调度算法的目标,1、处理机调度算法的共同目标 （1）资源利用率。 （2）公平性。不会发生

5、饥饿现象。 （3）平衡性。 （4）策略强制执行。,二、处理机调度算法的目标和准则,2、批处理系统、分时系统、实时系统的目标和准则,面向用户的准则 周转时间短 响应时间快 截止时间的保证 优先权准则 面向系统的准则 系统吞吐量 处理机利用率好 各类资源平衡利用,最优准则 最大的CPU利用率 最大的吞吐量 最短的周转时间 最短的等待时间 最短的响应时间,二、处理机调度算法的目标和准则,周转时间（常用于批处理系统） 定义：作业从提交 完成的时间 时间组成： （1）驻外等待调度时间 （2）驻内等待调度时间 （3）执行时间 （4）阻塞时间,周转时间不具有区分实际运行时间长短的性质。,二、处理机调度算法的

6、目标和准则,返回,平均周转时间 带权周转时间 平均带权周转时间,平均周转时间可以衡量不同调度算法对相同任务流的调度性能。,带权周转时间衡量长短任务的差别，故带权周转时间W越小越好,二、处理机调度算法的目标和准则,返回,响应时间快（对交互性作业）（分时系统） 概念：键盘提交请求到首次响应时间 时间组成 （1）输入传送时间 （2）处理时间 （3）响应传送时间 均衡性 截止时间的保证（特别于实时系统） 可预测性,补充：调度队列模型,在OS中的任何一种调度中，都将涉及到进程队列，由此形成了三种类型的调度队列模型。 1.仅有进程调度的调度队列模型 2.具有高级和低级调度的调度队列模型 3.同时具有三级调

7、度的调度队列模型,返回本节,1、仅有进程调度的调度队列模型,进程调度,时间片完,返回,2、具有高级和低级调度的调度队列模型,时间片完,返回,3、同时具有三级调度的调度队列模型,时间片完,进程调度,CPU,进程完成,等待事件,作业调度,中程调度,返回,回顾:具有三级调度的调度队列模型,时间片完,CPU,进程完成,事 件 出 现,等待事件,进程调度,中级调度,作业调度,3.2 作业与作业调度,一、批处理系统中的作业 作业：不仅包含了通常的程序和数据，还应配有一份作业说明书，系统根据该作业说明书对程序的运行进行控制。 作业步：每个作业都必须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果，我们

8、把其中的每一个加工步骤成为一个作业步。 作业流：若干个作业进入系统后，形成了输入作业流，处理时便形成处理作业流。,作业控制块：保存了系统对作业进行管理和调度所需的全部信息。 包含内容有：作业标识、用户名称、用户帐户、作业类型、作业状态、调度信息、资源需求、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。,二、作业运行的三个阶段和三种状态 收容阶段：把用户提交的作业通过某种输入方式输入到硬盘上，再为该作业建立JCB，放入作业后备队列中。 运行阶段：为被调度的作业分配必要的资源和建立进程，并将其放入就绪队列。 完成阶段：作业运行完成、或发生异常情况而提前结束时，便进入此阶段

9、。,三、高级调度需解决的问题 （1）接纳作业数（内存驻留数） 即多道程序的“道或度” 太多，则可能会影响系统的服务质量（如周转时间太长） 太少，又将导致系统资源利用率和吞吐量的下降 应根据系统的规模和运行速度来确定，同时要求I/O型进程与CPU型进程中和调度 （2）接纳策略（应将哪些作业从外存调入内存） 取决于采用何种调度算法（先来先服务、短作业优先等）,(一)先来先服务（FCFS）调度算法,基本思想:,对于作业调度：从后备作业队列中（按进入的时间顺序排队）选择队首一个或几个作业，调入内存，创建进程，放入就绪队列。 对于进程调度：从就绪队列中选择一个最先进入队列的进程，将CPU分配于它。,例1

10、： 作业名 到达时间 服务时间 A 0 1 B 1 100 C 2 1 D 3 100,(一)先来先服务（FCFS）调度算法,完成时间-到达时间,开始时间+服务时间,上一个进程的完成时间,1 101 100 1,101 102 100 100,102 202 199 1.99,例2：下面三个作业几乎同时到达系统并立即进行FCFS调度： 作业名 所需CPU时间 作业1 28 作业2 9 作业3 3 假设提交顺序为1、2、3，则平均作业周转时间T = 若提交顺序改为作业2、1、3，则T= 若提交顺序改为作业3、2、1，则T= FCFS调度算法的平均作业周转时间与作业提交的顺序有关。,(28+37+

11、40)/3 = 35,29,18,(一)先来先服务（FCFS）调度算法,FCFS调度算法评价,简单，但效率不高。 有利于长作业（进程）不利于短作业（进程）。 有时为了等待长作业的执行，而使短作业的周转时间变得很大，从而平均周转时间也变大。 现在操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系统和实时系统中。但它常被结合在其它调度策略中使用。,返回,(一)先来先服务（FCFS）调度算法,(二)短作业优先调度算法,短作业优先调度算法（SJF） 从后备队列中选择一个或若干个估计运行时间 最短的作业，将它们调入内存运行。,短进程优先调度算法（SPF） 从就绪队列中选出一个估计运行时间最短的进

12、程，将处理机分配给它。 可采用抢占或者非抢占调度方式。,执行顺序：,SJF/SPF_非抢占式举例,A,0,3,3,1,0,3,A,B,C,D,E,2,4,6,8,6,4,5,2,B,3,9,7,1.17,9,11,3,1.5,11,15,11,2.75,15,20,14,2.8,E,C,D,7.6,1.84,FCFS：ABCDE,FCFS和的SJF比较,SJF: ADBEC,二、短作业优先调度算法,优点： 1）能有效降低作业/进程的平均等待时间； 2）提高吞吐量； 3）能有效缩短作业/进程的周转时间； 缺点： 1）对长作业/进程不利； 2）不考虑作业/进程的紧迫程度； 3）作业执行时间仅为估计

13、；,课堂练习,练习：有如下四个进程，它们的到达时间和服务时间如下所示，请分别计算在采用FCFS、SPF非抢占两种调度算法时的平均周转时间和平均等待时间。 进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4,进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4 FCFS,平均周转时间= (7-0)+(11-2)+(12-4)+(16-5)/4=8.75 平均等待时间 = (0+(7-2)+(11-4)+(12-5)/4 =4.75,课堂练习,课堂练习,进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4 SPF

14、,平均周转时间= (7-0)+(12-2)+(8-4)+(16-5)/4=8 平均等待时间= (0-0)+(8-2)+(7-4)+(12-5)/4 = 4,SPF与FCFS的比较,返回,HPF(Highest-Priority-First) 需为每个进程设置一个由数字表示的优先数。 进程优先数的大小应与进程所对应事件的紧迫程度相对应。 当需要进行处理机分配时，系统在可运行的进程中选择优先数最高者使其投入运行。 进程的优先数反映了进程运行的优先级别，故又将其称作优先级算法。,(三)优先权调度算法（HPF）,思考：优先数如何存放？,PCB,（1）静态优先级 优先权在创建进程时确定，且在进程的整个运

15、行期间保持不变。一般用整数表示，小表示优先级高。 确定原则： 进程类型（系统进程用户进程） 进程对资源的需求（进程估计执行时间及内存需要量） 用户要求（紧急程度和付费情况） 优点： 缺点：,优先权的类型,简单、开销较少,公平性差（对低优先数进程）,优先权的类型,（2）动态优先权 动态优先级在进程的存在过程中不断发生变化。 动态优先级的变化取决于： 进程的等待时间 进程的运行时间 进程使用资源的类型等 此优先数确定方法资源利用率高，公平性好，但开销较大，实现较为复杂。 最高响应比优先算法采用动态优先级。,(四)高响应比优先权调度算法HRP,优先权的变化为,为响应比。,如等待时间相同,则要求服务时

16、间愈短,其优先权愈高-SPF. 如要求服务时间相同,优先权决定于等待时间-FCFS。 对长作业,若等待时间足够长，优先权也高，也能获得CPU。,算法HRP示例,算法HRP示例,HRP 的调度性能,=2.14,0,3,9,15,13,3,9,13,20,15,TA=3,TB=7,TC=9,TD=14,TE=7,=8.00,8,3,6,4,5,2,2,0,4,6,A,B,C,D,E,WE=3.50,WA=1,WB=1.17,WC=2.25,WD=2.80,E,C,D,A,B,周转时间T=结束时间Tc-到达时间Tin=3-0=3,周转时间 T,带权周转时间W=周转时间T/服务时间Tr=3/3=1,带权周转时 间W,平均,=(9-4)+4/4=2.