处理机调度与死锁 第三章,回顾： 具有挂起状态的进程状态图,执行,活动 就绪,静止 就绪,活动 阻塞,静止 阻塞,激活,挂起,接纳,新建,终止,分派/调度,时间片用完,激活,挂起,事件发生,完成,事件发生,事件等待,Abstract,1、调度类型 2、调度准则 3、调度算法 4、实时调度 5、死锁与饥饿,Learning objectives of this part,By the end of this lecture you should be able to: 解释什么是响应时间, 周转时间, 截至时间，吞吐量 理解进程调度的目标、类型、原则 理解决策方式: 非抢占 &抢占 分析掌握主要调度算法：FCFS, 时间片轮转，短作业优先，高优先权优先， 高响应比优先，反馈 理解实时系统及类型 实时操作系统的特征 理解掌握：实时调度，截止调度 理解死锁条件、预防死锁 、 避免死锁、 检测死锁、 解除死锁, 银行家算法 (安全状态 vs. 不安全状态 ),调度目标,Response time（响应时间） Throughput（系统吞吐量） Processor efficiency（处理机效率） Fairness(公平性，防止进程饥饿),3.1 调度类型,按调度的层次划分： Long-term scheduling（长程调度） Medium-term scheduling（中程调度） Short-term scheduling（短程调度）,长程调度,又称为高级调度、作业调度，它为被调度作业或用户程序创建进程、分配必要的系统资源，并将新创建的进程插入就绪队列，等待短程调度 作业：比程序更广泛，包含通常的程序和数据，还配有一份作业说明书，系统根据作业说明书对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。 作业步：在作业运行期间，每个作业都必须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果，把其中的每一个加工步骤成为一个作业步。 作业步一般分成：编译、连接装配、运行。,作业控制块（JCB）：作业在系统中的标志，其中保存了系统对作业进行管理和调度所需的全部信息。 每当作业进入系统时，系统便为每个作业建立一个PCB，根据作业类型将它插入相应的后备队列中。作业调度程序依据一定的调度算法来调度它们，被调度到的作业将会装入内存。 在作业运行期间，系统就按照JCB中的信息对作业进行控制。 当一个作业执行结束进入完成状态时，系统负责回收分配给它的资源，撤销它的作业控制块。,高级调度（长程调度）,作业调度功能：根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。 作业进入系统后，先驻留在磁盘上（批处理队列中）。长程调度从该队列中选择作业，为之创建进程。在每次执行作业调度时，都须做出以下两个决定： 1) 接纳多少个作业：太多或太少都不可 2) 接纳哪些作业 ：调度算法,高级调度（长程调度）,短程调度,又称为进程调度、低级调度，调度内存中的就绪进程执行。 功能:决定就绪队列Which进程将获得处理机 1、保存处理机的现场信息， 2、按某种算法选取进程， 3、把处理机分配给进程。 进程调度中的三个基本机制 1、排队器 2、分派器 3、上下文切换机制 进程调度方式 非抢占方式： 简单，实时性差 抢占方式:时间片原则、优先权原则、短作业优先原则。,中程调度,又称为中级调度，它调度换出到磁盘的进程进入内存，准备执行 中程调度配合对换技术使用。 其目的是为了提高内存的利用率和系统吞吐量。 在多道程序度允许的情况下，从外存选择一个挂起状态的进程调度到内存（换入）,短程 调度,中程 调度,新建,就绪,执行,长程 调度,阻塞/ 挂起,阻塞,图3-1 调度与进程状态转换,就绪/ 挂起,总结,外存,内存,占用cpu,3.2.1 调度的队列模型,一、仅有进程调度的队列模型,就绪队列,CPU,阻塞队列,交互用户,时间片完,进程调度,进程完成,等待事件,事件出现,3.2.1 调度的队列模型,二、具有高/低级模型,就绪队列,CPU,阻塞队列,时间片完,进程调度,进程完成,等待事件1,事件1出现,后备队列,阻塞队列,等待事件2,事件2出现,作业调度,3.具有三级调度的调度队列模型,就绪队列,CPU,就绪、挂起队列,时间片完,进程调度,进程完成,后备队列,阻塞、挂起队列,事件出现,作业调度,阻塞队列,等待事件,挂起,事件出现,中级调度,交互型作业,3.2.1 调度队列模型,3.2.2 选择调度方式和算法的若干准则,一、面向用户的准则 1周转时间短（常用于批处理系统） 概念：作业从提交 完成的时间.分为： （1）驻外等待调度时间 （2）驻内等待调度时间 （3）执行时间 （4）阻塞时间,一、面向用户的准则 平均周转时间 平均带权周转时间 可见带权w越小越好,Ts为实际服务时间。,3.2.2 选择调度方式和算法的若干准则,一、面向用户的准则 2响应时间快：（对交互性作业） 概念：键盘提交请求到首次响应时间 （1）输入传送时间 （2）处理时间 （3）响应传送时间 3截止时间的保证：即某任务开始执行的最迟时间或必须完成的最迟时间。（特别于实时系统） 4优先权准则：（即需要抢占调度）,3.2.2 选择调度方式和算法的若干准则,二、面向系统的准则 1吞吐量高（特别于批处理）：单位时间完成作业数 2处理机利用率好：（因CPU贵，特别于大中型多用户系统） 3各类资源的平衡利用。（？折算标准）,3.2.2 选择调度方式和算法的若干准则,3.2.1先来先服务和短作业（进程）优先调度算法 1.FCFS 特点：简单，有利于长作业,即CPU繁忙性作业;不利于短作业。 2.短作业进程优先调度算法：SJ(P)F 提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量） 特点： 对长作业不利，有可能得不到服务（饥饿） 未考虑作业的紧迫程度，不能保证紧急作业被及时处理。 估计执行时间不易确定,3.3 调度算法是一个资源分配问题,例：FCFS算法实例,0,1,1,1,1,101,100,1,101,102,100,100,102,202,199,1.99,图3.4 FCFS和SJF比较,4,7,12,14,18,4,6,10,11,14,9,1,2,2,5.5,3.5,2.8,4,9,18,6,13,4,8,16,3,9,8,1,2.67,3.2,1.5,2.25,2.1,3.2.2 高优先权优先调度算法,1.优先权调度算法类型 非抢占式优先权算法 抢占式优先权算法，实时性更好。 2.优先权类型： 1静态优先权： 进程优先权在整个运行期不变。 确定优先权依据 （1）进程类型 （2）进程对资源的需求； （3）根据用户需求。 特点：简单，但低优先权作业可能长期不被调度。,3.2.2 高优先权优先调度算法(2),2动态优先权： 如：优先权描述为 可见：优先权随执行时间而下降，随等待时间而升高。 响应比,服务时间,（等待时间服务时间）,Rp=,服务时间,（等待时间服务时间）,优先权=,服务时间,响应时间,=,优点：长短兼顾。 主要体现在以下几个方面： （1）如果作业的等待时间相同时，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。 （2）当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。 （3）对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。 缺点：需计算Rp，增加系统开销。,服务时间,（等待时间服务时间）,Rp=,服务时间,响应时间,=,3.3.3 基于时间片的轮转调度算法,1.时间片轮转 时间片大小的确定 太大（每个进程都能在一个时间片内完成）：退化为FCFS； 太小：有利于短作业，频繁地发生中断、进程上下文的切换，系统开销过大 系统对响应时间的要求；T=nq 就绪队列中进程的数目； 系统的处理能力：（应保证一个时间片处理完常用命令） 例题：见书p95,p96,时间片轮转例题（ VISIO截图）,15,12,16,9,17,15,11,14,6,13,11.8,3.75,3.67,3.5,3,3.33,3.46,4,7,11,13,17,4,6,9,10,13,8.4,1,2,2.25,5,3.33,2.5,3.2.3 基于时间片的轮转调度算法,2.多级反馈队列调度 调度实施过程： （1）设置多个就绪队列，并为各个队列赋予不同的优先级。在优先级愈高的队列中，为进程执行的时间片愈小。,就绪队列1,至CPU,S1,就绪队列2,S2,至CPU,就绪队列3,S3,至CPU,就绪队列n,Sn,至CPU,时间片：S1S2S3,图37 多级队列反馈调度算法,（2）当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统，否则进入紧邻的后续队列。 （3）仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1-（i-1）队列均为空时,才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先级较高的队列，则此时新进程将抢占正在运行进程的处理机。 特点：长、短作业兼顾，有较好的响应时间 （1）短作业一次完成； （2）中型作业周转时间不长； （3）大型作业不会长期不处理。,回顾,1、周转时间、带权周转时间 2、FCFS：对短作业不公平 3、短作业：长作业饥饿 4、高优先权：低优先权的可能长期不调度。 5、高响应比：须计算相应比，增加开销。 6、时间片轮转：时间片长短不易确定。太长等同于FCFS，太短频繁中断，增加开销。 7、多级反馈：最好的调度算法。按不同的优先级设在不同的就绪队列。同一队列按FCFS调度。不同队列按优先级高低进行调度。优先级高的时间片设置短些。,3.4.1实现实时调度的基本条件 1提供必要的调度信息 （1）就绪时间； （2）开始/完成截止时间； （3）处理时间； （4）资源要求； （5）优先级； 2系统处理能力强,3.4 实时调度,Ci为处理时间，Pi为周期时间（基于周期性实时任务）,例:如果一个单处理器实时系统中有3个周期性任务，它们的周期分别为80ms、40ms和240ms，需要CPU处理的时间分别为20ms、10ms和40ms，问该实时系统 能否调度这3个周期性任务？,所以，该系统可调度这3个周期性实时任务。 但是，如果这3个周期性实时任务需要处理器处理的时间分别变为30ms、20ms和60ms时，则：,系统不能调度这3个周期性实时任务。,如果将该单处理器系统变为具有两个处理器的系统，则：,则双处理器系统可以调度这3个周期性实时任务。,3.4.1实现实时调度的基本条件 3.采用抢占调度方式 剥夺方式：一般都采用此 非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。 4.具有快速切换机制 具有快速响应外部中断能力。 快速任务分派能力,3.4 实时调度,3.4.2 实时调度算法的分类,1.非抢占式调度算法 时间片轮转 秒级 非抢占优先权（协同） 秒-毫秒级 2.抢占式调度算法 时钟中断抢占优先权 毫秒级 基于抢占点抢占 立即抢占immediate