计算机操作系统第四版第三章调度算法ppt课件.ppt

调度算法 进程调度算法类型 算法类型 简单的调度算法 先来先服务算法 短作业 进程 优先 最高响应比优先 优先权法 抢占式优先权 非抢占式优先权 静态优先权 动态优先权 多级反馈队列算法 时间片轮转法 1 先来先服务First Come First Served FCFS 作业 进程 调度算法FCFS是一种最简单的调度算法 可用于作业或进程调度 此算法的原则是按照作业到达后备作业队列 或进程进入就绪队列 的先后次序来选择作业 或进程 FCFS算法属于非抢占方式 一旦一个进程占有处理机 它就一直运行下去 直到该进程完成或者因等待某事件而不能继续运行时才释放处理机 FCFS算法易于实现 表面上很公平 CPU 就绪队列 1 2 3 后备队列 内存 例题 在单道环境下 某批处理有四道作业 已知他们的进入系统的时刻 估计运算时间如下 作业 进入时刻 h 运行时间 h 1 2 3 4 8 00 8 50 9 00 9 50 2 00 0 50 0 10 0 20 用FCFS算法计算作业的运行情况 平均周转时间和平均带权周转时间 8 00 10 00 10 50 10 60 10 00 10 50 10 60 10 80 2 00 2 00 1 60 1 30 1 00 4 00 16 00 6 50 平均周转时间T 平均带权周转时间T 用FCFS算法 计算作业的运行情况 平均周转时间和平均带权周转时间 完成时间 开始时间 运行时间 周转时间 完成时间 进入时间 带权周转时间 周转时间 运行时间 6 875 h 1 725 h FCFS算法调度例2 作业名进入时间运行时间 分 需内存量KBA8 064215B8 183060C8 302450D8 362410E8 421220有用户空间100KB 并规定作业相应程序装入内存连续区域 并不能被移动 作业与进程均采用FCFS算法 有用户空间100KB 并规定作业相应程序装入内存连续区域 并不能被移动 作业与进程均采用FCFS算法作业名进入时间运行时间 分 需内存量KBA8 064215B8 183060C8 302450D8 362410E8 421220 FCFS总结 FCFS根据进程到达就绪队列的时间来分配中央处理机 一旦一个进程获得了中央处理机 就一直运行到结束 先来先服务是非剥夺调度 这种调度从形式上讲是公平的 但它使短作业要等待长作业的完成 重要的作业要等待不重要作业的完成 从这个意义上讲又是不公平的 先进先出调度使响应时间的变化较小 因此它比其它大多数调度都可预测 由于这种调度方法不能保证良好的响应时间 在处理交互式用户时很少用这种方法 在当今系统中 先进先出很少作为调度模式 而是常常嵌套在其它的调度模式中 例如 许多调度模式根据优先级将处理机分配给进程 但具有相同优先级的进程却按先进先出进行分配 2 短作业 进程优先 SJF ShortestProcessNext 调度算法这种调度算法主要用于作业调度 它从作业后备队列中挑选所需运行时间 估计值 最短的作业进入主存运行 这一算法有利于短作业 对长作业不利 采用SJF有利于系统减少平均周转时间和平均带权周转时间 例题 用SJF算法计算作业的运行情况 平均周转时间和平均带权周转时间 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 0028 500 5039 000 1049 500 20 平均周转时间T 平均带权周转时间T 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0028 500 5039 000 1049 500 20 平均周转时间T 平均带权周转时间T 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 0028 500 5039 000 1049 500 20 平均周转时间T 平均带权周转时间T 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 0028 500 5039 000 1010 0049 500 20 平均周转时间T 平均带权周转时间T 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 0028 500 5039 000 1010 0010 1049 500 20 平均周转时间T 平均带权周转时间T 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 0028 500 5039 000 1010 0010 1049 500 2010 10 平均周转时间T 平均带权周转时间T 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 0028 500 5039 000 1010 0010 1049 500 2010 1010 30 平均周转时间T 平均带权周转时间T 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 0028 500 5010 3039 000 1010 0010 1049 500 2010 1010 30 平均周转时间T 平均带权周转时间T 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 0028 500 5010 3010 8039 000 1010 0010 1049 500 2010 1010 30 平均周转时间T 平均带权周转时间T 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 0028 500 5010 3010 8039 000 1010 0010 1049 500 2010 1010 30 平均周转时间T 平均带权周转时间T 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 002 0028 500 5010 3010 802 3039 000 1010 0010 101 1049 500 2010 1010 300 80 平均周转时间T 平均带权周转时间T 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 002 001 0028 500 5010 3010 802 304 6039 000 1010 0010 101 1011 0049 500 2010 1010 300 804 00 平均周转时间T 平均带权周转时间T 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 002 001 0028 500 5010 3010 802 304 6039 000 1010 0010 101 1011 0049 500 2010 1010 300 804 00 平均周转时间T 1 55h平均带权周转时间T 5 15h 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 002 001 0028 500 5010 3010 802 304 6039 000 1010 0010 101 1011 0049 500 2010 1010 300 804 00 平均周转时间T 1 55h平均带权周转时间T 5 15h 最短作业优先法 SJF 运行顺序 1 3 4 2 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 002 001 0028 500 5010 3010 802 304 6039 000 1010 0010 101 1011 0049 500 2010 1010 300 804 00 缺点 1有利于短作业 不利于长作业 2未考虑作业紧迫程度 图3 4FCFS和SJF调度算法的性能 SJF算法例 作业名进入时间运行时间 分 需内存量KBA8 064215B8 183060C8 302450D8 362410E8 421220有用户空间100KB 并规定作业相应程序装入内存连续区域 并不能被移动 作业与进程均采用SJf算法 作业名进入时间运行时间 分 需内存量KBA8 064215B8 183060C8 302450D8 362410E8 421220 例 A请求系统服务时间5s B请求系统服务时间为100s 设第0到第5秒前 CPU运行C进程 第1秒时B进入系统内存 第2秒时A进入内存当CPU空闲 需要调度进程时根据不同的算法选择A或B问 分别计算FCFS算法下和SJF算法下 A和B的周转时间 带权周转时间和系统平均周转时间 B A 调度算法比较例题 FCFS算法 先来先服务B 周转时间为4 100 104s带权周转时间为104 100 1 04A 周转时间为3 100 5 108s带权周转时间为108 5 21 6平均带权周转时间为 21 6 1 04 2 11 32SJF算法 短进程优先A 周转时间为3 5 8s带权周转时间为8 5 1 6B 周转时间为4 5 100 109s带权周转时间为109 100 1 09平均带权周转时间为 1 6 1 09 2 1 345 调度算法比较例 先调度B后调度A 先调度A后调度B 调度顺序 调度顺序 短作业 进程 优先算法SJ P F 不一定能真正做到短作业优先调度未考虑作业的紧迫程度 因而不能保证紧迫性作业被及时处理不利于长作业 当不断有短进程到达时 不保证长进程响应的及时性 甚至可能得不到调度 3 高响应比优先HighestResponseRatioNext HRRN 作业 调度算法按照高响应比优先的原则 在每次选择作业投入运行时 先计算此时后备作业队列中每个作业的响应比RP 然后选择其值最大的作业投入运行 RP值定义为 RP 已等待时间 要求运行时间 要求运行时间 1 已等待时间 要求运行时间HRN算法实际上是FCFS算法和SJF算法的折衷 响应比R不仅是要求运行时间的函数 而且还是等待时间的函数 由于R与要求运行时间成反比 故对短作业是有利的 另一方面 因R与等待时间成正比 故长作业随着其等待时间的增长 也可获的较高的响应比 这就克服了短作业优先的缺点 既照顾了先来者 又优待了短作业 是上述两种算法的一种较好的折中 3 最高响应比作业优先算法 HRN 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 0028 500 5039 000 1049 500 20平均周转时间 带权周转时间 8 00 10 00 2 00 1 00 10 10 10 60 2 10 4 20 10 00 10 10 1 10 11 00 10 60 10 80 1 30 6 50 1 625h 5 675h 4 时间片轮转Round Robin RR 调度算法 进程调度程序总是选择就绪队列中第一个进程 允许其占有处理机一个时间片的时间 当执行的时间片用完时 调度程序便停止该进程的执行 并将它送就绪队列的末尾 等待分配下一时间片再执行 然后把处理机分配给就绪队列中新的队首进程 同时也让它执行一个时间片 这样就可以保证就绪队列中的所有进程 在一给定的时间内 均能获得一时间片处理机执行时间 在RR算法中 时间片的大小对系统性能有很大的影响 时间片轮转策略特别适合于分时系统中使用 当多个进程驻留在主存中时 在进程间转接处理机的开销一般是不大的 在轮转法中 时间片长度的选取非常重要 时间片长度的选择会直接影响系统开销和响应时间 如果时间片长度过短 则调度程序剥夺处理机的次数增多 这将使进程上下文交换次数也大大增加 加重了系统开销 如果时间片长度选择过长 大 大到一个进程足以完成其全部运行工作所需的时间 那么时间片轮转法就退化为先来先服务策略了 最佳的时间片量值应能使分时用户得到好的响应时间 时间片S RT NmaxRT 响应时间Nmax 最大进程数每当一轮调度开始时 系统便根据就绪队列中已有进程数目计算一次值 作为新一轮调度的时间片 这种方法得到的时间片是随就绪队列中的进程数变化的 例 假定在一个处理机上执行以下五个作业 作业号ABCDE到达时间01234运行时间43524分别采用FCFS SJF RR 时间片 1 和HRN 响应比高者优先 四种调度算法时 试做 1 画出调度图 2 计算每个作业的周转时间和带权周转时间 3 计算平均周转时间和平均带权周转时间 调度图 T0123456789101112131415161718FCFSAAAABBBCCCCCDDEEEESJFAAAADDBBBEEEECCCCCRRABCDEABCDEABCEACECHRNAAAABBBDDCCCCCEEEE 例解 例解 1 例解 2 高响应比优先 HRRN 作业 调度算法计算 T 0 只有作业A已到达 调度作业A运行 T 4 作业A完成 作业B C D E已到达 计算作业B C D E响应比RP分别为 1 3 3 1 2 5 1 1 2 1 0 4 作业B响应比最大调度运行 T 7 作业B完成 作业C D E已到达 计算作业C D E响应比RP分别为 1 5 5 1 4 2 1 3 4 作业D响应比最大调度运行 T 9 作业D完成 作业C E已到达 计算作业C E响应比RP分别为 1 7 5 1 5 4 作业C响应比最大调度运行 T 14 作业C完成 只有作业E未完成 调度作业E运行 按照进程的优先权大小来调度 使高优先权进程得到优先处理的调度策略称为优先权调度算法 进程的优先权的设置可以是静态的 也可以是动态的 5 高优先权 Priority 优先调度算法 静态优先权 在进程创建时确定 且在整个生命期中保持不变 确定进程优先权的依据有 进程类型 通常系统进程 例如对换进程 的优先权高于一般用户态进程的优先权 进程对资源的需求 如进程执行时间及内存需要的进程应赋予较高的优先权 根据用户要求 由用户的紧迫程度及用户所付费用的多少来确定进程的优先权 动态优先权 是指在创建进程时所赋予的优先权 可以随进程的推进而改变 以便获得更好的调度性能 改变优先权的因数 随系统不同而不同 最常考虑的因素的进程的等待时间 已使用处理机的时间 或者资源使用情况等 在UNIX系统中处于核心态和用户态的优先权不同 进程处于核心态的优先权高 处于核心态的进程优先权又分二类 一类是因等待磁盘I O 等待缓冲器等不可中断优先权最高 而另一类因等待TTY输入输出等可中断优先权其次 处于用户态的优先权相对较低 用户态优先权又分为n 1级优先权 优先数为0级的优先权最高 优先数为n级的优先权最低 用户态优先权是可变的 它随着占用CPU时间的增加而降低 核心每隔1秒钟便按下述公式对各进程重新计算其用户优先数 优先数与优先权成反比关系 优先数 最近使用CPU的时间 2 基本用户优先数 例题 假定要在处理机上执行如下作业 作业的执行顺序为 6 多级队列调度算法 多队列调度是根据作业的性质和类型的不同 将就绪队列再分为若干个子队列 所有的作业 或进程 按其性质排入相应的队列中 而不同的就绪队列采用不同的调度算法 例如前后台系统可以建立两个就绪队列 批处理作业所建立进程进入后台就绪队列 交互型作业所建立的进程进入前台就绪队列 前台采用时间片轮转算法 进程按FCFS等策略排序 后台采用高优先权的调度算法或者短作业优先的调度算法 对多级就绪队列调度策略有两种 一种是各就绪队列按进程性质赋予不同的优先权 优先权高的就绪队列的进程优先被调度 例如上例中前台就绪队列的优先权比后台就绪队列的优先权高 所以前台队列中的进程优先被调度 而只有当优先权高的就绪队列空时 方才调度优先权其次的就绪队列进程 在上例中只有前台队列空时 才调度后台就绪队列 这样 只有较高优先权的就绪队列都空时才调度最低优先权就绪队列的进程 另一种调度就绪队列的方式是为每个队列分配一定的占用CPU时间的比例 如在上例中为前台队列分配80 的CPU时间 给后台队列分配20 的CPU时间 1 优先级逐渐降低2 优先级高的时间片短3 新进程进入内存后 首先将它放入第一队列的末尾 按FCFS原则排队等待调度 6 多级反馈队列调度算法 4 在第n队列中便采取按时间片轮转的方式运行 5 仅当第一队列空闲时 调度程序才调度第二队列中的进程运行 如果处理机正在第i队列中为某进程服务时 又有新进程进入优先权较高的队列 第1 i 1 中的任何一个队列 则此时新进程将抢占正在运行进程的处理机 即由调度程序把正在运行的进程放回到第i队列的末尾 把处理机分配给新到的高优先权进程 WindowsNT采用可抢占动态优先级多级就绪队列调度算法 NT执行体支持32级优先级 并将它们分成两类 实时优先级 16 31 和可变优先级 1 15 0级为系统保留 每个优先级一个就绪队列 高序号队列为高优先级 调度程序从高优先级的队列开始往下找 如高优先级队列为空时才再往下找 直至找