操作系统第四章

1 先来先服务 FCFS 调度算法将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列 并按照先来先服务的方式进行调度处理 是一种最普遍和最简单的方法 它优先考虑在系统中等待时间最长的作业 而不管要求运行时间的长短 进程调度算法和作业调度算法 在单道环境下 某批处理显然有四道作业 已知他们的进入系统的时刻 估计运算时间如下 作业 进入时刻 h 运行时间 h 1 2 3 4 8 00 8 50 9 00 9 50 2 00 0 50 0 10 0 20 用FCFS算法计算作业的运行情况 平均周转时间和平均带权周转时间 作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转 1 2 3 4 8 00 8 50 9 00 9 50 2 00 0 50 0 10 0 20 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 1 725 h 平均带权周转时间T 6 875 h FCFS算法调度例2 作业名进入时间运行时间 分 需内存量KBA8 064215B8 183060C8 302450D8 362410E8 421220有用户空间100KB 并规定作业相应程序装入内存连续区域 并不能被移动 作业与进程均采用FCFS算法 有用户空间100KB 并规定作业相应程序装入内存连续区域 并不能被移动 作业与进程均采用FCFS算法作业名进入时间运行时间 分 需内存量KBA8 064215B8 183060C8 302450D8 362410E8 421220 100K 15K 60K 10K 15K 9 189 18 2 最短作业优先法 SJF 该算法总是优先调度要求运行时间最短的作业 运行顺序1342 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 002 001 0028 500 5010 3010 802 304 6039 000 1010 0010 101 1011 0049 500 2010 1010 300 804 50 平均周转时间T 1 55h平均带权周转时间T 5 15h SF算法例2 作业名进入时间运行时间 分 需内存量KBA8 064215B8 183060C8 302450D8 362410E8 421220有用户空间100KB 并规定作业相应程序装入内存连续区域 并不能被移动 作业与进程均采用FCFS算法 作业名进入时间运行时间 分 需内存量KBA8 064215B8 183060C8 302450D8 362410E8 421220 最高响应比作业优先算法是对FCFS方式和SJF方式的一种综合平衡响应比R定义为系统对作业的响应时间与作业要求运行时间的比值R 响应时间 要求运行时间 作业等待时间 需运行时间 需运行时间 1 已等待时间 需运行时间 1 W T 3 最高响应比作业优先算法 HRN 响应比R不仅是要求运行时间的函数 而且还是等待时间的函数 由于R与要求运行时间成反比 故对短作业是有利的 另一方面 因R与等待时间成正比 故长作业随着其等待时间的增长 也可获的较高的相应比 这就克服了短作业优先数法的缺点 既照顾了先来者 又优待了短作业 是上述两种算法的一种较好的折中 3 最高响应比作业优先算法 HRN 作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18 002 008 0010 002 001 0028 500 5010 0010 602 104 2039 000 1010 5010 101 1011 0049 500 2010 6010 801 306 50平均周转时间1 625h带权周转时间5 675h 时间片轮转法主要用于进程调度 采用此算法的系统 其程序就绪队列往往按进程到达的时间来排序 进程调度程序总是选择就绪队列中的第一个进程 也就是说按照先来先服务原则调度 但一旦进程占用处理机则仅使用一个时间片 在使用先一个时间片后 进程还没又完成其运行 它必须释放出处理机给下一个就绪的进程 而被抢占的进程返回到就绪队列的末尾重新排队等待在次运行 4 轮转法 RR 时间片轮转策略特别适合于分时系统中使用 当多个进程驻留在主存中时 在进程间转接处理机的开销一般是不大的 在轮转法中 时间片长度的选取非常重要 时间片长度的选择会直接影响系统开销和响应时间 如果时间片长度过短 则调度程序剥夺处理机的次数增多 这将使进程上下文交换次数也大大增加 加重了系统开销 如果时间片长度选择过长 大 大到一个进程足以完成其全部运行工作所需的时间 那么时间片轮转法就退化为先来先服务策略了 最佳的时间片量值应能使分时用户得到好的响应时间 响应时间S RT NmaxR 响应时间Nmax 最大进程数每当一轮调度开始时 系统便根据就绪队列中已有进程数目计算一次值 作为新一轮调度的时间片 这种方法得到的时间片是随就绪队列中的进程数变化的 进程调度的功能 从就绪队列中挑选一个进程到处理机上运行 作业调度程序在挑选作业进入主存运行时 要为该作业建立相应的进程 在作业完成后要撤销该作业的全部进程 一个进程被建立后 系统为了便于对进程的管理 将系统中的所有进程按其状态将其组织成不同的进程队列 进程调度 进程调度程序 负责进程调度功能的内核程序 作业调度与进程调度程序的区别 前者是挑选作业进主存运行 后者是挑选就绪进程到处理机上运行 进程调度的核心问题就是 采用什么算法把处理机分配给进程 选择调度算法时应考虑的问题 进程调度的算法较多 在设计进程调度算法时应考虑的因素多 比如 尽量提高资源利用率 减少处理机的空闲时间 对于用户作业要较合理的平均响应时间 以及尽可能地增强CPU的处理能力 D C B A CPU 完成 4 4调度算法 1 FCFS 先来先服务调度算法 最简单的调度原则是先进先出就绪队列 根据进程到达就绪队列的时间来分配中央处理机 一旦一个进程获得了中央处理机 就一直运行到结束 先来先服务是非剥夺调度 这种调度从形式上讲是公平的 但它使短作业要等待长作业的完成 重要的作业要等待不重要作业的完成 从这个意义上讲又是不公平的 先进先出调度使响应时间的变化较小 因此它比其它大多数调度都可预测 由于这种调度方法不能保证良好的响应时间 在处理交互式用户时很少用这种方法 在当今系统中 先进先出很少作为调度模式 而是常常嵌套在其它的调度模式中 例如 许多调度模式根据优先级将处理机分配给进程 但具有相同优先级的进程却按先进先出进行分配 2 作业要求的资源 根据作业要求系统提供的处理机时间 内存的大小和I O设备的数量 来确定作业的优先数 如果系统赋予作业的反比于系统的估计执行时间 就形成短作业优先的算法 由于作业需要的执行时间事先难于确定 只是把用户自报的估计时间作为依据 为防止用户少报自己的作业时间以获得优先服务 在采用短作业优先算法时 应采取适当的防备措施 F C B A CPU 完成 A BC 4 时间片轮转算法 当时间片很大时 每个进程得到比完成该进程多的处理机时间 此时轮转调度模式退化为先进先出模式 当时间片非常小时 上下文转换开销就成了决定因素 系统性能降低 大多数时间都消耗在处理机的转换上 只有少许用在用户的计算上 这个最佳的时间片值是多少呢 显然 它将随系统而异 随负载而异 同时也随进程异 时间片的选取是实现各种调度算法的关键之处 而时间片的独额定通常应考虑终端数目 处理机能力 各终端任务的急迫程度 外存传输速度等方面的因素 时间片轮转法亦可应用于批处理系统的处理机调度 5 优先级调度算法 一种常用的进程调度算法是把处理机分配给具有最高优先数的进程 用于实时系统 在这种算法中 首先考虑的问题是如何确定进程的优先数 一种是静态优先数 另一种是动态优先数 1 静态优先数静态优先数是在系统创建时确定的 一经确定之后在整个进程运行期间不再改变 确定静态优先数的有关静特性是 在有的系统中 分配给作业的优先数还取决于它所占用的内存的多少 作业越大 占用内存越多 分配给它的优先数越低 显然 不论是根据作业的执行时间 还是根据作业的大小所确定的优先数 都有利于短作业 2 动态优先数 虽然基于静态优先数的调度算法比较简单 也颇为流利 但毕竟不够精确 因为进程的优先数在它执行前就已算好 且在整个执行期间都保持不变 但随着进程的推进 计算优先数所依赖的特征很多都将随之改变 因此静态优先数并非自始至终都能准确地反映出这些特性 如果能在进程运行中 不断的随着特性的改变而修改其优先数 显然可以实现更多精确的调度 从而获得更好的调度性能 这对分时系统显得格外重要 进程类型 系统中由两类进程 系统进程和用户进程 系统进程的优先数比用户进程的优先数高 特别是某些系统进程 必须赋予它一种特权 当它需要处理机时 应尽快的到满足 例如 设备管理器中的I O进程便是如此 这不仅是为了保证I O设备尽可能忙碌 一提高设备利用率 更主要的是为了避免由于响应不及时 将造成信息的丢失 在