3 3调度算法 进程调度算法类型 算法类型 简单的调度算法 先来先服务算法 短作业 进程 优先 最高响应比优先 优先权法 抢占式优先权 非抢占式优先权 静态优先权 动态优先权 多级反馈队列算法 时间片轮转法 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 调度算法 进程调度程序总是选择就绪队列中第一个进程 允许其占有处理机一个时间片的时间 当执行的时间片用完时 调度程序便停止该进程的执行 并将它送就绪队列的末尾 等待分配下一时间片再执行 然后把处理机分配给就绪队列中新。