CPU调度

• 什么是CPU调度?为什么要进行CPU调度?如何进行CPU调度?

  • 对于多道程序来说(单片系统)CPU只有一个,如何调度CPU使得在CPU空闲的时候(如进行IO操作时)使得内粗哪种的其他进程来使用CPU,保证CPU的最大利用率,这就要用到 "处理器调度"了
  • 对于操作系统来说,如何使资源利用率得到最大化无疑是其永恒的主题之一,cpu作为资源,肯定也需要这样的最大化
  • CPU的调度,必须要依赖进程的 CPU-I/O周期,意思是指CPU从cpu区间(CPU BURST)开始执行,之后是IO区间,如此循环直到最后一个CPU区间结束循环,而从前面的知识我们知道,下一个CPU区间的执行依赖于IO区间的完成,但在IO区间进行时,是否可也使得其他进程的CPU区间使用CPU呢?答案是肯定的,而为了完成这种转换就是CPU调度了
  • 当然进程的区间长度也是根据进程的特性决定的,有的进程更多的依赖于计算(CPU-bound)那么就可以安排更长的CPU区间,反之,如果是传输数据为主的进程(I/O-bound)则给予更长的IO区间

• CPU调度室由谁来调度?什么时候发生调度?具体是怎么实现的?

  • CPU的调度要靠short-term scheduler 短期CPU调度程序(or CPU scheduler)
  • CPU scheduler每当CPU空闲时(如正在执行的进程至于IO区间),则从就绪队列中选取一个进程得到CPU使用权
  • 如第三章提到的,CPU进程由很多状态,而调度也发生在这些调度转换中:
    • 运行到等待(IO请求)
    • 运行到就绪(中断)
    • 等待到就绪(IO完成)
    • 进程终止
      但是不是所有的操作系统在上面4中情况都发生调度的,操作系统在什么时候调度称为操作系统的调度策略,如果调度只能发生在1.4情况下,则称这种调度策略为非抢占式的(Non-Preemptive)否知就是抢占式的.非抢占式的...也就是说,要不把他设为等待,否知这个进程将一直进行下去直到结束.也就WIN3.X系列采用这样的设计,从WIN95之后一直采用抢占式的调度策略
  • 说明抢占式调度与非抢占式调度的区别。对于计算中心，上述两种调度方式哪一种比较适合？
  • 短期调度程序选择了进程之后,要将cpu的使用权传递给被选择的进程,这一过程是由分派程序(dispatcher)来进行的
    • 切换上下文
    • 切换到用户模式
    • 跳转到用户程序合适的位置,以重新启动程序
      当然完成上述工作也是需要时间的,这时间称为分派延迟
  • 结合短期CPU调度程序和分派程序基本就可以完成CPU调度了

调度准则

• 什么是调度准备?他有什么作用?
  短期CPU调度程序选择进程的时候肯定也需要一定的方式,而这样选择进程的算法被称为调度算法,而调准则就是评价调度算法好与坏,适合不适合的基准

• 调度准则有哪些?

  1. CPU使用率
  2. 吞吐量:单位时间完成进程数
  3. 周转时间:从进程提交到完成进程所用的时间
  4. 等待时间:进程在就绪队列中花费的时间
  5. 响应时间:从提交请求道返回响应所花的时间

调度算法

这个可以算是本节课的核心了,上面的调度准则也是为了调度算法服务的

• 我们从5个准则出发来评价算法:
  1. CPU使用率没得说,只要就绪队列里有进程,CPU将一直忙绿
  2. 吞吐量,这个不好说,看具体情况
  3. 周转时间:这个也要看情况
  4. 等待时间:这个很关键,下面我们将主要从这一点来分析算法
  5. 响应时间:具体分析吧

先到先服务调度(FCFS) Scheduling

• 从等待时间来看这种算法...变化太大
• 易产生护航效果(convoy effect)
• 这是一种典型的非抢占式的算法,CPU效率一般比较低

最短作业优先调度(Shortest-Job-First (SJF))

• 短期CPU调度器从就绪队列中找到下一个CPU区间最短的进程进行执行
• 这可以被证明,SJF在平均等待时间是最优的
• 但在短期调度上很难实现,因为我们不知道下一个CPU区间的长度
• sjf可以使抢占式的也可以是非抢占式的
  • 非抢占式:once CPU given to the process it cannot be preempted until completes its CPU burst
  • 抢占式的:if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. This scheme is know as the Shortest-Remaining-Time-First
• SJF虽然在平均等待时间是最佳的,但它也容易造成问题:
  • 前述的无法获知下一个CPU区间长度是一个
  • 需要很长时间来执行的进程则会被无限推迟,这种效应称为饥饿

优先级调度

• 每一个继承都与一个优先级关联

• 调度选择进程时选择优先级高的来进行

• 优先级调度也可以分为抢占式的和非抢占式的

  • 非抢占式的:高优先级的来了也不会给其让CPU,而是先执行自己
  • 抢占式的....不说了,一下就懂了

• 从某种意义上来说,SJF是一种优先级调度,只不过进程关联的优先级是其CPU区间长度

• 这种算法容易产生饥饿(starvation)
  结局饥饿也是有一定方法的:比如老化(Aging)
  也就是随着进程的等待,其优先级会被缓慢提升

轮转法调度(RR)

专门为分时系统设计

• 核心思想:RR调度让就绪队列的第一个进程使用CPU(时间片)的时长内没有完成,则放到队列尾巴
• RR调度的核心问题在于时间片大小的选取,如果时间片过大,那不就是FCFS了吗,如果太小呢?那不就成了CPU共享了吗,而且别忘了还有CPU上下文切换所消耗的时间啊,切换的过于频繁这部分的消耗也将是惊人的,一般来说,要使得进程80%的CPU区间小于时间片

多级队列调度

• 这种调度方式是将进程按照不同的属性(进程大小,优先级,进程类型)分成不同的队列,而每个队列都有自己的调度算法,进程被永久分配到某一个队列中
• 队列之间同样要有调度,通常采用固定优先级抢占式调度

多级反馈队列调度

• 类似多级调度队列,只不过进程可以在进程间转移,占用过多CPU时间的进程将被降低优先级,放到低优先级队列,而长时间等待的进程会被放到优先级高的队列来
• 要定义一个多级反馈队列调度:
  1. 队列数量
  2. 每个队列的调度算法
  3. 用以确定何时升级到高优先级队列的方法
  4. 用以确定何时降级到低优先级队列的方法
  5. 用以确定进程在需要服务时进入那个队列的方法

多CPU调度

好了,上面提到了很多方法,但都是对于单CPU的方法,对于多CPU系统
这个PDF缺页了......
CPU scheduling more complex when multiple CPUs are available.
Homogeneous processors within a multiprocessor.
Load Balancing — keep the workload evenly distributed across all processors.
Push migration
Pull migration