Policies on Scheduling the CPU

这是 《Operating System: Three Easy Pieces》 的第 2 篇读书笔记。

接上篇笔记《Mechanisms on Virtualizing the CPU》,上篇文章介绍了操作系统在虚拟化CPU方面需要的基础机制/设施(Mechanisms),主要是与硬件协作共同提供给上层应用一个安全实用的抽象,本篇主要记录操作系统在调度CPU方面的策略(Policies)。

Scheduling: Introduction

how should we develop a basic framework for thinking about scheduling policies?

  • What are the key assumptions?
  • What metrics are important?
  • What basic approaches have been used in the earlist of computer systems?

Workload Assumptions

Determining the workload is a critical part of building policies, and the more you know about workload, the more fine-tuned your policy can be.

作者对任务使用CPU的方式先做了一些限定,后面会逐渐放开限制,徐徐展开各种策略。

  1. Each job runs for the same amount of time.
  2. All jobs arrive at the same time.
  3. Once started, each job runs to completion.
  4. All jobs only use the CPU (i.e., the perform no I/O)
  5. The run-time of each job is know.

Scheduling Metrics

For now, let us simplify our life by simply having a simple metric: Turnaround Time.

T(turnaround) = T(completetion) - T(arrival)

First In, First Out (FITO)

FIFO的调度方式很简单
举个例子,上面5个假设全都成立的时候:

上图Turnaround Time的为:(10 + 20 + 30) / 3 = 20.
但是FIFO的调度方式会出现如下例子想说明的问题,当*假设1*不成立的时候:


上图的Turnaround Time为:(100 + 110 + 120) / 3 = 110,先到达的任务会一直执行到之前其完成让出CPU.

这样的结果肯定不能另用户满意,CPU的大部分时间都被长时间的任务A所占据了,任务B、C得到CPU的时间被大大推迟。

Shortest Job First (SJF)

顾名思义,时间较短的任务会优先得到运行机会。
上面的例子,如果使用SJF的调度方式,那么Turnaround Time为:(10 + 20 + 120) / 3 = 50.

上图举例的情况是任务A、B、C同时到达的情况,那么如果B、C比A后到达呢?这种情况SJF调度器是没有规定B/C可以抢占A的CPU的(因为我们还没有放开*假设3*的限制),也就是说当*假设2*不成立的时候,SJF调度策略也不好使了,其结果如下图:

Shortest Time-to-Completion First (STCF)

运行时间较短的任务先得到运行机会(我们在这里其实是放开*假设3*的限制了),因此SJF的不适情况,使用STCF之后的运行结果如下:

其Turnaround Time为:((120-0) + (20-10) + (30-10)) / 3 = 50

A New Metric:Response Time

我们考虑另一个维度,响应时间 Response Time,其计算公式为:T(response) = T(firstrun) - T(arrival)
它看重的是任务何时得到运行机会,这对多用户/多任务时的体验非常友好。

Round Robin

也被叫做轮询策略,The basic idea is simple:

RR runs a job for a time slice (sometimes called a scheduling quantum) and then switches to next job in the run queue.
It repeatedly does so until the jobs are finished.

轮询的执行方式见上图(Figure 7.7)。

可以看到,轮询的一大好处是任务能够得到尽快的响应,这点对用户体验非常友好。
谁也不想要一个敲入运行命令后等待好一会儿才响应的“慢东西”。

Incorporating I/O

放开*假设4*的限制,如果CPU Scheduler执行的是轮询策略,任务会发出I/O操作怎么办?
我们知道当一个任务在执行I/O操作的时候它其实是处于*blocked*的状态的,CPU执行进程的I/O指令,并等待I/O设备返回结果,而I/O设备又通常比CPU慢很多个数量级,如果这个时候进程A不让出CPU的话,那么CPU这个时候就处于空转状态,这是一个资源浪费,调度情况如下图所示:

如果这个时候可以切换任务的话,那么CPU的使用情况会如下图所示:

这种情况下,CPU的使用率会好些,任务的平均响应时间也比较低。

No More Oracle

其实上面所讨论的策略其实都基于最后一个假设成立的情况——*提前知道了任务的运行时间*,但是一个任务怎么能提前知道自己的运行时间呢?

答案是——并不能知道——因为没有这样的先验能力存在。

那么,有没有策略可以兼容上面这些策略的所长又能适度中和这些策略的所短呢?

Multi-Level Feedback Queue

MLFQ的基本思想是:

  • 维护一些不同的队列去装载任务,每个队列按优先级排序;
  • 在一个给定的时间内,一个任务只能出现在一个队列中;
  • 在高优先级队列里的任务得到优先运行机会;
  • 同优先级队列里的任务按照Round Robin(轮询)方式得到运行机会
  • OS根据任务的“运行特点”(是否使用I/O?大量的CPU运算?等等)指定相应的策略,在任务运行时动态调整任务的优先级(可以调高可以调低);
  • 为了避免某些任务”玩弄“调度器,使得其他任务长时间处于低优先级队列(也就是说被“饿死”了)而得不到运行机会,引入 “Priority Boost” 机制,定期提升低优先级队列里的任务的权限;

这上面说的其实还比较笼统,但是可以根据实际情况具体展开,可以有很多的调优策略。
实际情况中:Solaris操作系统的CPU调度器FreeBSD操作系统(version 4.3)的调度器 是MLFQ的经典实现。

MLFQ的优点既综合了前述的几种策略的优点

  1. 一定程度保证了SJF/STCF对于短时间任务的优势
  2. 对于运行时间较长的任务也有 Round Robin(轮询)策略保证一定的公平性
  3. 也考虑到了I/O的情况
  4. 同时又能根据运行时的情况动态调整,*不必“未卜先知”地知道每个人物的运行时间*

使得它在业界得到了比较广泛的实现。

引用
Operating System: Three Pieces of Way - Scheduling: Introduction
Operating System: Three Pieces of Way - Scheduling: The Multi-Level Feedback Queue

Comments
Write a Comment