第六章第六章 处理机调度处理机调度o6.1 处理机的多级调度处理机的多级调度o6.2 作业调度作业调度o6.3 进程调度进程调度o6.4 UNIX系统的进程调度系统的进程调度操作系统原理处理机调度6.1 处理机的多级调度处理机的多级调度o1. 批处理OS中的处理机调度n对处理机的分配分两级：o作业调度（宏观调度）：分配资源、建立进程o进程调度（微观调度）：分配处理机、时间片o2.多任务操作系统中的处理机调度 n分时或个人计算机 OS中的处理机调度支持多任务并发。o对处理机的分配：进程调度（并分配处理机时间）o调度对象：就绪进程o3. 多线程OS中的处理机调度n对处理机的分配：线程调度n调度对象：就绪线程操作系统原理处理机调度6.2 作业调度作业调度o一一. 作业的状态作业的状态 作业在整个活动期间一共有四种状态， n提交状态：用户将自己的程序和数据提交给系统，等待输入。n后备状态：作业已存放在磁盘上，等待调度。运行就绪完成等待后备提交作业调度作业调度作业录入执行n执行状态：作业进入主存开始运行。 n完成状态：作业计算完成开始，退出系统。 3操作系统原理处理机调度o二二. 作业调度的功能作业调度的功能 n1. 确定数据结构确定数据结构o建立作业控制块jcb (job control block)。n作业控制块记录了每个作业类型、状态、资源请求及分配情况。 n2. 确定调度策略与调度算法确定调度策略与调度算法o按一定的调度策略从磁盘中存放的大量作业中挑选一个或几个作业投入运行。n3. 分配资源分配资源o为选中的作业分配所需要的系统资源（主存、外设等）。 n4. 善后处理善后处理o收回该作业所占用的全部资源，撤消作业控制块以及与该作业有关的全部进程。6.2 作业调度作业调度4操作系统原理处理机调度o三三. .作业控制块作业控制块n每个作业进入系统时，有系统为其建立jcb。作业控制块jcb存在于系统的整个过程中，jcb是一个作业存在的标志。njcb的主要内容如下： 作作 业业 名名 资资 源源 要要 求求 资资 源源 使使 用用 情况情况 估计执行时间 进入系统时间 最迟完成时间 开始执行时间 要求的主存量 已执行时间 要求外设的类型及台数 主存地址 要求文件量和输出量 外设台号 类类 型型 优优 先先 级级 控制方式 作业作业 状态状态 作业类型6.2 作业调度作业调度5操作系统原理处理机调度o四四. 作业调度算法性能的衡量作业调度算法性能的衡量n采用平均周转时间和平均带权周转时间来衡量作业调度算法性能的好坏。n1. 周转时间周转时间o一个作业提交给计算机系统到该作业的结果返回给用户所需要的时间。o(1) 定义定义 ti = tci - tsi ti作业i的周转时间 tsi作业i的提交时间（磁盘后备队列） tci作业i的完成时间。o(2) 意义意义 说明作业I在系统中停留时间的长短。o(3)平均周转时间平均周转时间 t = （n为作业个数）6.2 作业调度作业调度6操作系统原理处理机调度6.2 作业调度作业调度o2. 平均带权周转时间平均带权周转时间wn(1) 定义定义 o一个作业的周转时间与其运行时间的比值。 wi = ntri为作业i的实际执行时间，ti进入磁盘后备队列的时间n(2) 意义意义 o说明作业i在系统中相对等待时间。n(3) 平均周转时间平均周转时间 t = 操作系统原理处理机调度6.2 作业调度作业调度o五五. 作业调度算法作业调度算法n1.先来先服务调度算法o(1)策略：按作业来到的先后次序进行调度。o(2)特点：简单，易实现。 o(3)讨论在先来先服调度算法下周转时间与带权周转时间 作业提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.0010.502.00439.000.1010.5010.601.601649.500.2010.6010.801.306.5平均周转时间 t=1.725平均带权周转时间 w=6.875这种算法对短作业不利，执行时间短，等待时间较长，带权周转时间很高。操作系统原理处理机调度6.2 作业调度作业调度o2. 短作业优先调度算法短作业优先调度算法n(1)策略：按作业请求运行的时间长短进行调度。n(2)特点：易实现，系统吞吐量高。 只照顾短作业，而没有考虑长作业的利益。n(3)讨论在短作业优先调度算法下的周转时间与带权周转时间 作业 提交时间 执行时间 开始时间完成时间周转时间 带权周转时间18.002.008.0010.002.00128.500.5010.3010.802.304.639.000.1010.0010.101.101149.500.2010.1010.300.804平均周转时间 t=1.55平均带权周转时间 w=5.15易于实现，效率较高；主要弱点不考虑长作业的利益。操作系统原理处理机调度6.2 作业调度作业调度o3.响应比高者优先调度算法响应比高者优先调度算法n计算后备作业表中的每个作业的响应比，挑选响应比最高者运行。o响应比响应时间/执行时间o响应比1作业等待时间/执行时间作业提交时间执行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.3010.602.104.239.000.1010.0010.101.101149.500.2010.6010.801.306.5平均周转时间 t=1.625平均带权周转时间 w=5.675是先来先服务和短作业优先算法之间的折中算法。操作系统原理处理机调度6.2 作业调度作业调度o4.优先调度算法优先调度算法n据系统设计目标分析各作业的优先数，调度时选取优先数高的作业先执行。n优先数的计算保证使输出量最少、要求执行时间短的作业以及等了很久的作业得到优待。n优先数（等待时间）2要求执行时间16输出量o等待时间：作业在磁盘中等候时间（分）o要求执行时间：据Jcb中记录的相应值推算出（秒）o输出量：据Jcb中记录的相应值推算出（行）n它企图十分迅速的执行各种短作业，但偶尔也要执行一个在磁盘中等候很久的作业，此时“等待时间”这一项的值已远远超过其他两项之和。操作系统原理处理机调度6.3 进程调度进程调度o一一. 调度调度/分派结构分派结构n任何进程都必须通过调度/分派模块来使用处理机。进程调度的功能可细分为调度和分派两部分。n1. 调度调度o依照完全确定的策略将一批进程进行排序，形成就绪队列。o调度程序的功能：负责将一个进程插入到就绪队列并按一定原则保持队列结构；n2. 分派分派o当处理机空闲时，是移出就绪队列中第一个进程，并赋予它使用处理机的权利。o分派程序的功能：是将进程从就绪队列中移出并建立该进程执行的及其状态。12操作系统原理处理机调度o3. 调度调度分派结构图分派结构图 6.3 进程调度进程调度调度程序等待唤醒接受pcb1pcb2pcb3pcb4pcb5Ready_q分派程序cpu13操作系统原理处理机调度o二二. 进程调度的功能和调度准则进程调度的功能和调度准则n进程调度的功能o1. 记录进程的有关情况和状态特征（ pcb ）o2. 决定分配策略n由就绪队列的排序原则体现的。n优先调度原则进程就绪队列按进程优先级高低排序n先来先服务原则进程就绪队列按进程来到的先后次序排序o3. 实施处理机的分配和回收nCPU现场信息的切换6.3 进程调度进程调度14操作系统原理处理机调度6.3 进程调度进程调度n进程调度的时机o进程完成其任务时；o在一次管理程序调用之后，该调用使现行程序暂时不能继续运行时；o在一次出错陷入之后，该陷入使现行进程在出错处理时被挂起时；o在分时系统中，完成的规定时间片时；o在采用可剥夺调度方式的系统中，高掠夺低进程时。操作系统原理处理机调度6.3 进程调度进程调度n进程调度的准则ocpu使用率：尽可能忙o吞吐量：指一个时间单元内所完成的进程数量。o周转时间：是所有时间段之和，包括等待进入主存、在就绪队列中等待、在cpu上执行和I/O执行时间。o响应时间：指联机用户向计算机发出一个命令到计算机执行完该命令，并将相应的执行结果返回给用户所需的时间。o等待时间：是进程在就绪队列中等待所花费时间之和。操作系统原理处理机调度o三三. 进程调度方式进程调度方式n1. 什么是调度方式什么是调度方式o当一进程正在处理机上执行时，若有某个更为“重要而紧迫”的进程需要进行运行，系统如何分配处理机。n2. 非剥夺方式非剥夺方式o一种是让正在执行的进程继续执行，直到该进程完成或发生某事件而进入“完成”或“阻塞”状态时，才把处理机分配给“重要而紧迫”的进程。n3. 剥夺方式剥夺方式o当“重要而紧迫”的进程一到，便暂停正在执行的进程，立即把处理机分配给优先级更高的进程。n4. 选择可抢占策略：选择可抢占策略：o该策略是两种极端的抢占和不可抢占策略之间的折衷方案。 o进程被指派一个优先数，并有一对标志（U、V）6.3 进程调度进程调度17操作系统原理处理机调度o四四. 进程调度算法进程调度算法n1. 进程优先数调度算法进程优先数调度算法o(1) 什么是进程优先数调度算法n预先确定各进程的优先数，系统把处理机的使用权赋予就绪队列中具备最高优先权(优先数和一定的优先级相对应)的就绪进程。o(2) 优先数的分类及确定n静态优先数在进程被创建时确定，且一经确定后在整个进程运行期间不再改变。n 静态优先数的确定优先数根据进程所需使用的资源来计算优先数基于程序运行时间的估计优先数基于进程的类型 6.3 进程调度进程调度18操作系统原理处理机调度n动态优先数进程优先数在进程运行期间可以改变。n动态优先数的确定：o进程使用CPU超过一定数值时，降低优先数；o进程进行I/O操作后，增加优先数o进程等待时间超过一定数值时，提高优先数6.3 进程调度进程调度19操作系统原理处理机调度o2. 循环轮转调度算法循环轮转调度算法n先进先出可能存在的问题是，当一个进程在放弃对处理机的控制权之前可能执行很长时间，而其他进程的推进受到严重的影响。那么就可使用一个时间片，这一时间片方法称为循环轮转规则。 n(1) 简单循环轮转调度简单循环轮转调度o定义：当CPU空闲时，选取就绪队列首元素，赋予一个时间片，当时间片用完时，释放cpu控制权，该进程转为就绪态并进入就绪队列末端o特点：n就绪队列中的所有进程以等速度向前进展 时间片q = t/nnt 为响应时间，n为进入系统的进程数目。n时间片选择:时间片应该比进程切换时间要长，常为100ms6.3 进程调度进程调度20操作系统原理处理机调度6.3 进程调度进程调度n(2)可变时间片轮转调度可变时间片轮转调度o每当一轮开始，系统根据就绪队列中已有的进程数目计算一次q值，然后进行轮转。在此期间所到达的进程都暂不进入就绪队列，要等此次轮转完毕后再一并进入。o在采用可变时间片算法中n每当一轮开始时，系统便根据就绪队列中已有的进程数计算q值，然后进行轮转。n在此期间所到达的进程都占不进入就绪队列，而要等到此次轮转完后再一起进入。n此时，系统根据就绪队列中的进程数重新计算q值，然后开始下一轮循环。操作系统原理处理机调度o五五. 调度用的进程调度变迁图调度用的进程调度变迁图 n可采用进程状态变迁图阐述进程调度算法。n如有进程调度算法：o（1）当CPU空闲时，首先从高优先级就绪队列中选择一个进程运行，给定时间片为100ms。o（2）如高优先级就绪队列为空，则从低优先级就绪队列中选择一个进程运行，给定时间片500ms。o进入低优先就绪队列的进程一般是计算量比较大的的，称为受cpu限制的进程；而阻塞变为高优先就绪进程一般是输入/输出量比较大的进程，称受I/O限制的进程。6.3 进程调度进程调度22操作系统原理处理机调度6.3 进程调度进程调度o这种调度策略优先照顾I/O量大的进程。适当照顾了计算量大的进程。运行低优先级就绪高优先级就绪因I/O而等待请求I/OI/O完成首先选择100ms其次选择500ms超时间片操作系统原理处理机调度6.3 进程调度进程调度o较为复杂的进程状态变迁图运行低优先级就绪高优先级就绪因盘或带I/O而阻塞请求盘或带I/OI/O完成进程调度100ms500ms进程调度超时间片中优先级就绪因终端I/O而阻塞因页面I/O而阻塞I/O完成I/O完成缺页中断请求终端I/O操作系统原理处理机调度6.4 UNIX系统的进程调度系统的进程调度o处理机的分配主要包括三方面工作：n首先，将现行进程的CPU现场保护到该进程的pcb结构中；n其次，依调度原则在就绪队列中选择一个进程；n最后，恢复选中进程的运行现场。nUNIX系统中，完成这三项工作的程序称为进程切换调度。操作系统原理处理机调度6.4 UNIX系统的进程调度系统的进程调度o一、一、UNIX系统的进程调度算法系统的进程调度算法nUNIX系统的进程调度算法是优先数算法。o一个进程优先权的高低取决于其优先数，优先数越小，优先权越高。在进程调度时机来到时，总是选取优先权最高的进程去运行。nUNIX系统确定进程优先数的方法有设置和计算两种。o设置方式用于高、低优先级睡眠状态进程。o优先数的计算是当进程处在用户态时，每秒由时钟处理程序计算和设置，或者在发生俘获后，返回到用户态之前由俘获处理程序计算和设置。操作系统原理处理机调度6.4 UNIX系统的进程调度系统的进程调度o（1）优先数的）优先数的设置设置 n当进程需睡眠时，设置其优先数。由不同的睡眠原因决定其大小。o等待紧迫的事件，该进程的优先数设置为负值o等待慢速设备I/O、进程间同步，该进程的优先数设置为正值。o（2）优先数的计算）优先数的计算n1) 当进程从核心态返回用户态时，或自陷返回时，系统计算该进程的优先数。 p_pri = min127，p_cpu/16-p_nice+PUSERnp_cpu（反映使用cpu的程度）和p_nice（是程序可以设置的进程优先数偏置值）都是proc的分量， PUSER是固定的偏置常数，定位100操作系统原理处理机调度6.4 UNIX系统的进程调度系统的进程调度o(2) 在时钟中断处理程序中在时钟中断处理程序中n每隔20ms，将正在运行的进程的p_cpu 加 1，直到255。这使当前进程p_cpu增大，pri也增大，于是优先级降低。n每隔1s ，时钟中断处理程序对所有的就绪进程计算 p_cpu 减10，直到小于10时置为0。这使所有未占用cpu的进程p_cpu增大，pri也增大，于是优先级提高。n所以，占用cpu时间越长的进程，下次被调用的可能性越小，而未占用cpu的进程等待时间越长，下次被调用的可能性就越大。操作系统原理处理机调度6.4 UNIX系统的进程调度系统的进程调度o p_cpu这样的改变方式使进程使用cpu的时间与它被调用的机会称为负反馈过程。 p_cpu p_pri 进程优先权 被调度的机会 被调度的机会 进程优先权 p_pri p_cpuo这样的负反馈过程使系统中在用户态下运行的各个进程都能比较均衡的享用处理机。操作系统原理处理机调度6.4 UNIX系统的进程调度系统的进程调度o二、进程优切换调度程序进程优切换调度程序swtch算法 swtch 输入：无 输出：无 保留现行进程的现场到其系统栈中； for (就绪队列中的每一个进程) 取在主存、就绪态、优先权最高的进程； if (没有找到满足条件的进程) 机器空闲等待； /* 下次中断使机器脱离空闲等待状态 */ 将选取的进程从就绪队列中移出； 切换到被选中进程的映像，恢复其运行； 操作系统原理处理机调度6.4 UNIX系统的进程调度系统的进程调度oswtch程序的主要任务如下：n1）将调用swtch的当前进程的现场信息保留在其系统栈中。n2）将扫描proc表，找出满足如下条件的进程去运行。o在主存（p_flag的SLOAD=1）;o就绪状态（p_stat=SRUN）;o优先数（p_pri）最小。n3）找到了所要求的进程后，把该进程的p_addr装入存储管理地址映射的寄存器中，并设置好相应的地址映射机构，再恢复该进程的现场。操作系统原理处理机调度一. 处理机的两级调度 二. 作业调度 1. 作业的四种状态 2. 作业控制块 3. 周转时间、带权周转时间：定义 物理意义 4. 常用的作业调度算法 先来先服务 短作业优先 对一批作业，若采用两中不同的调度算法，能分析、计算调度性能的好坏。 第六章第六章 小结小结操作系统原理处理机调度三. 进程调度 1. 调度方式 非剥夺方式 剥夺方式 2. 常用的进程调度算法 优先数调度 循环轮转调度 3. 调度用的进程状态变迁图o通过调度用的进程状态变迁图，能分析系统采用的调度策略，调度性能的好坏。o能分析因果变迁及条件。 第六章第六章 小结小结操作系统原理处理机调度