第2章_进程管理讲述.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 前提条件之二：需要事先估计作业的运行时间 如何知道作业的运行时间？ 该时间只可能是一个估计值； 让提交该作业的用户来提供。不太实用； 使用前面的CPU运行时间来预测后面的CPU运 行时间，通过过去的行为来预测将来的行为。 如果一个作业已经运行很长时间了，那它可能 还会运行更长的时间； 使用指数平均值函数来预测下一段CPU时间; 2.5.3 交互式系统中的调度算法 1. 时间片轮转法 在时间片轮转算法（Round-Robin，RR）中，将所有的就绪进程按照FCFS原则，排成一个队列； 每次调度时将处理器分派给队首进程，让其执行一小段CPU时间（时间片）； 在一个时间片结束时，如果进程还没有执行完的话，在时钟中断中，进程调度程序将暂停当前进程的执行，并将其送到就绪队列的末尾，然后执行当前的队首进程； 如果一个进程在它的时间片用完之前就已结束或被阻塞，那么立即让出CPU。 开始时，进程B位于队列之首，因此被调度执行。当它的时间片用完后，就把它送到就绪队列的末尾。同时，进程F成为队首进程，被调度运行。 （本图摘自Andrew S. Tanenbaum： “Modern Operating Systems” ） 优点： 公平性：各个就绪进程平均地分配CPU的使用 时间。假设有n个就绪进程， 那么每个进程将 得到1/n的CPU时间； 活动性：若时间片大小为q，每个进程最多等 待(n-1)q时间就能够再次得到CPU去运行； 一般来说，平均周转时间较SJF算法为长，但 能够得到较短的平均响应时间； 缺点：q的大小难以确定（一般在20－50ms）。 q太大：退化为FCFS算法，进程在一个时间片 内执行完或被阻塞，响应时间长。如q=100ms； q太小：每个进程需要更多时间片才能处理完， 进程切换次数增加(1ms)，增大系统开销。如q=4ms 时间片轮转法的特点 进程 CPU时间 P1 53 P2 17 P3 68 P4 24 一个例子：时间片长度q＝20 P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 平均周转时间： (134 + 37 + 162 + 121) / 4＝113.5 SJF的平均周转时间： (94 + 17 + 162 + 41) / 4＝78.5 2. 优先级算法 轮转法有一个缺省的前提，即各进程同等重要； “人人生而平等”？ 恐怕不太现实！同样，并 不是每个进程都同等重要， 怎么办？分等级！ QQ vs. Outlook 优先级算法（Priority Scheduling）：给每个进 程设置一个优先级，然后在所有就绪进程中选择 优先级最高的那个进程去运行； SJF就是一个优先级算法，每个进程的优先级是 它的CPU运行时间（时间越短，优先级越高）； 分为可抢占和不可抢占两种方式； 各进程优先级的确定方式可分为静态和动态两种。 静态优先级方式 确定优先级的依据： 进程类型（系统进程优先级高于用户进程，交互式进程高于批处理进程）； 对系统资源的需求（对CPU和内存需求较少的进程，优先级较高）； 用户要求（用户级别和付费情况，如军用电脑、商用电脑）。 静态方式的缺点： 静态优先级方式是指在创建进程时确定进程优先级，并保持不变到进程结束。 高优先级的进程一直占用CPU，低优先级的进程“饥饿”。 动态优先级方式 为防“饥饿”, 根据运行时间和等待时间调整优先级 进程每执行一个时间片就降低其优先级。当一个进程持续执行时，其优先级降低到让出CPU； 在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行。 动态优先级方式是指在创建进程时赋予给进程的优先级，在进程运行过程中可以动态改变，以便获得更好的调度性能。 在一个实际的操作系统中，如何实现优先级