目录

调度的概念

调度目标

所有系统

批处理系统

交互式系统

实时系统

调度算法

非抢占式调度算法

先来先服务

最短作业优先

非抢占式优先级调度

抢占式调度算法

最短剩余时间优先

轮转调度

抢占式优先级调度

多级反馈队列

彩票调度

公平分享调度


调度的概念

  • 进程是资源分配的基本单位;
  • 线程是CPU调度的基本单位。

一个单核CPU在某一时刻只能允许一个线程执行,但是现在的计算机总是有一大堆进/线程等待执行。这就需要某种规则来决定处理这些进/线程的顺序,这就是调度要研究的问题。

进程状态:

运行态:当前正在占有CPU的进/线程;

就绪态:具备运行条件,等待系统分配CPU的进/线程;

阻塞态:不具备运行条件,正在等待某外部事件发生的进/线程。

所谓进程调度,就是指在处于就绪态的一堆进/线程里,按照一定的调度算法,选出一个进/线程并给它分配CPU时间让它运行,从而实现多进程/多线程的并发执行。

进程切换的基本流程:

  1. 首先用户态必须切换到内核态;
  2. 保存当前进程的状态,包括在其PCB中保存CPU各寄存器值,以便日后重新执行;
  3. 调度算法选定一个新进程;
  4. 新进程的内存地址空间重新装入MMU(内存管理单元);
  5. 新进程开始执行。

调度目标

所有系统

对于所有系统,都应该有以下调度目标:

  • 公平——给每个进程公平的CPU份额;
  • 策略强制执行——保证规定的调度策略被执行;
  • 平衡——保证系统的所有部分都在忙碌。

批处理系统

批处理系统更适合非抢占式调度算法,应有以下调度目标:

  • 吞吐量——每小时最大作业数;
  • 周转时间——从提交到终止的最短时间;
  • CPU利用率——保持CPU始终忙碌。

交互式系统

交互式系统更适合抢占式调度算法,应有以下调度目标:

  • 响应时间——快速响应请求;
  • 均衡性——满足用户的期望。

实时系统

对于实时系统,应有以下调度目标:

  • 满足截止时间——避免丢失数据;
  • 可预测性——如多媒体系统中避免品质降低。

调度算法

进程调度的核心自然是调度规则,即各种调度算法。

计算机都有一个硬件时钟,也叫RTC或CMOS,它独立于操作系统,由主板上一块电池供电的芯片,所以即使计算机断电,RTC也可以维持时间。这个硬件时钟会周期性的发出时钟中断。

根据如何处理时钟中断,可以把调度算法分为两类:

  • 非抢占式调度算法:发生时钟中断时不调度;
  • 抢占式调度算法:通过时钟中断使CPU控制权返回给调度程序,进而调度其它进程。

非抢占式调度算法:正在运行的进程只有在该进程执行完成或发生阻塞(如I/O请求)的情况下才会释放CPU;

抢占式调度算法:分给进程的时间片耗尽之后,无论当前进程有没有执行完成,调度程序均选择其他进程执行。

非抢占式调度算法

先来先服务

先来先服务算法(FCFS):按照进程请求CPU的顺序调度它们。

意思就是,所有的就绪状态的进程在一个队列中,申请使用CPU的进程按照先来后到的顺序排在队列尾部,每执行完一个进程,系统就从该队列的头部取出第一个进程来执行。

优点:

  • 易于理解且算法实现简单;

缺点:

  • 对短进程不利。排在长进程后面的短进程需要等待很长时间,短进程的响应时间可能会很长。

最短作业优先

最短作业优先算法(SJF):每次调度时选择当前已到达的、且运行时间最短的作业。

优点:

  • 对比FCFS,平均等待时间、平均周转时间、平均带权周转时间均有提高;

缺点:

  • 需提前掌握各作业的运行时间;
  • 对长作业不利。因为如果一直有短作业到来,那么长作业永远得不到调度,长作业有可能会饿死,处于一直等待短作业执行完毕的状态。

周转时间:从进程请求CPU到进程执行完毕为止的统计平均时间。

非抢占式优先级调度

优先级调度:每个进程被赋予一个优先级,允许优先级最高的可运行进程先运行。

对于非抢占式优先级调度,当一个进程到达就绪队列时,比较它的优先级与当前运行进程的优先级。如果新到达进程的优先级高于当前运行进程的优先级,非抢占优先级调度算法只是将新的进程加到就绪队列的头部,而不会进行进程切换。

缺点:

  • 若有源源不断的高优先级进程到来,低优先级进程会导致饥饿。

抢占式调度算法

最短剩余时间优先

最短剩余时间优先(SRTN):当一个新的进程到达时,把它所需要的整个运行时间与当前进程的剩余运行时间作比较。如果新的进程需要的时间更少,则挂起当前进程,运行新的进程,否则新的进程等待。

优点:

  • 可以使新的短进程得到良好的服务。

缺点:

  • 需提前掌握各进程的运行时间;
  • 对长进程不利。

最短剩余时间优先(SRTN)是最短作业优先的抢占式版本。

轮转调度

轮转调度(RR):每个进程被分配一个时间段,称为时间片,即允许该进程在该时间段内运行。如果在时间片结束时该进程还在运行,则剥夺其CPU并分配给另一个进程;如果该进程在时间片结束前阻塞或结束,则立即进行进程切换。

轮转调度算法对每个进程都一视同仁,就好比大家都排好队,一个一个来,每个人都运行一会儿再接着重新排队等待运行。

优点:

  • 易理解且算法易实现;
  • 可以兼顾长进程和短进程。

缺点:

  • 平均等待时间较长,频繁上下文切换比较费时;
  • 时间片的长度选取困难。

时间片设置的太短会导致过多的进程切换,降低CPU效率;

时间片设置的太长又可能会引起对短的交互请求的响应时间变长。

通常时间片设为20-50ms是一个较合理的折中。

抢占式优先级调度

优先级调度:每个进程被赋予一个优先级,允许优先级最高的可运行进程先运行。

优先级调度的问题在于高优先级进程可能无休止地运行下去,对此有两种解决方案:

  • 调度程序可能在每个时钟中断降低当前进程的优先级。如果调整后该进程的优先级低于次高优先级的进程,则进行进程切换。
  • 给每个进程赋予一个允许运行的最大时间片,时间片耗尽,次高优先级的进程就获得运行机会。

优先级有静态赋予和动态赋予两种方式。

静态赋予即在创建进程时人为确定进程的优先级,并且规定它在进程的整个运行期间保持不变;

动态赋予即在创建进程时赋予该进程一个初始优先级,然后系统根据进程的执行情况的变化而不断改变其优先级,以便获得更好的调度性能。

对于抢占式优先级调度,当一个进程到达就绪队列时,比较它的优先级与当前运行进程的优先级。如果新到达进程的优先级高于当前运行进程的优先级,那么抢占式优先级调度算法就会进行进程切换,让新到的高优先级进程运行。

多级反馈队列

多级反馈队列:在系统中设置多个就绪队列,并为每个队列赋予不同的优先级,从第一个开始逐个降低。不同队列中的进程所赋予的执行时间也不同,优先级越高,时间片越小。

  • 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程,则调度次优先级队列中的进程;
  • 对于同一个队列中的各个进程,按照时间片轮转调度;
  • 当一个进程用完分配的时间片后,它被移到低一级优先级队列。

彩票调度

彩票调度:为进程提供各种系统资源(如CPU时间)的彩票。一旦要做出调度决策时,就随机抽取一张彩票,拥有该彩票的进程则获得该资源。

为了增加重要进程“中彩票”的机率,可以给它们额外的彩票。

公平分享调度

公平分享调度:考虑进程的拥有者是谁,保证每个用户公平的分享CPU。

之前的调度算法都不关注进程所有者是谁。这样做的结果是,如果用户1启动9个进程而用户2启动1个进程,使用轮转或相同优先级调度算法,那么用户1将得到90%的CPU时间,而用户2只得到10%的CPU时间。