# Two Scheduling Methods

## Two Scheduling Methods

### 0x00 引言

MLFQ应该OS课程都会将到的一个Scheduling算法吧。因为某些原因需要复习一下几年前学过的内容。

The Multi-level Feedback Queue (MLFQ) scheduler was first described by Corbato et al. in 1962 in a system known as the Compatible Time-Sharing System (CTSS), and this work, along with later work on Multics, led the ACM to award Corbato its highest honor, the Turing Award. The scheduler has subsequently been refined throughout the years to the implementations you will encounter in some modern systems.


### 0x01 How To Change Priority

How can we design a scheduler that both minimizes response time for interactive jobs while also minimizing turnaround time without a priori knowledge of job length?


Scheduler 一般都存在一些基本的规则，先来看看这里的两个基本的规则:

• Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t).

• Rule 2: If Priority(A) = Priority(B), A & B run in RR.


• Rule 3: When a job enters the system, it is placed at the highest priority (the topmost queue).

• Rule 4a: If a job uses up an entire time slice while running, its pri- ority is reduced (i.e., it moves down one queue).

• Rule 4b: If a job gives up the CPU before the time slice is up, it stays at the same priority level.

##### 存在的问题
1. 饥饿，交互式的任务一多，其它类型的任务就很难得到运行的机会；
2. 不安全，应用可以hack这个sheduler，通过在这个时间片的末尾发出IO请求，它就能一直保持住它的优先级；
3. 任务的行为不是一成不变的，一个任务已开始可能是IO密集型的，之后会变成CPU密集型的，反之亦然。然而在这里一旦开始被认为是CPU密集型的，它就没机会变为IO密集型的了(sheduler的看法)

### The Priority Boost

• Rule 5: After some time period S, move all the jobs in the system to the topmost queue.


### Better Accounting

​ 上面提到的第2个问题还是没有解决。之所以存在这个问题，是因为上面的rule 4a,4b。那就将rule修改一下:

Rule 4: Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced (i.e., it moves down one queue).


### Summary

MLFQ is interesting for the following reason: instead of demanding a priori knowledge of the nature of a job, it observes the execution of a job and prioritizes it accordingly. In this way, it manages to achieve the best of both worlds: it can deliver excellent overall performance (similar to SJF/STCF) for short-running interactive jobs, and is fair and makes progress for long-running CPU-intensive workloads. For this reason, many systems, including BSD UNIX derivatives, Solaris, and Windows NT and subsequent Windows operating systems use a form of MLFQ as their base scheduler.


• Rule 1: 如果A的优先级 > B的优先级, A运行.

• Rule 2: 如果A的优先级 == B的优先级, A B以RR的方式运行.

• Rule 3: 任务最开始加入的时候，都将它运行在最高的优先级.

• Rule 4: 在一个队列上面运行完时间片之后，将削减优先级，降低到更加低的队列.

• Rule 5: 周期性地将所有任务提升到最后优先级.


### 0x02 Proportional Share

How can we design a scheduler to share the CPU in a proportional manner? What are the key mechanisms for doing so? How effective are they?


#### 最基本的思路

lottery scheduling使用的一个最基本的概念就是：tickets，凭证。使用tickets来代表了使用分享到的资源，tickets的比例代表了分享到的资源的比例。它使用一种概率性的方法来决定下一个运行的进程，比如下面这个例子，系统必须知道这里一共有多少个tickets(这里就是100)，然后挑选一个随机的ticket，数字是0-99。如果是0-74则运行A，74-99则运行B。

Let’s look at an example. Imagine two processes, A and B, and further that A has 75 tickets while B has only 25. Thus, what we would like is for A to receive 75% of the CPU and B the remaining 25%.


#### Ticket机制

lottery scheduling也提供了一些方式来操作tickets。一个概念就是ticket currency，currency使得用户可以决定以怎么样的比例来运行自己的jobs，系统会自动将这个currency转化为全局的tickets。比如用户A给自己的两个jobs每个500tickets，B用户给自己的一个job 10tickets，则对应到全局的rickets就是A1 50，A2 50，B1 100。这个有点类似于Linux里面的组调度。

Rather, *inflation* can be applied in an environment where a group of processes trust one another; in such a case, if any one process knows it needs more CPU time, it can boost its ticket value as a way to reflect that need to the system, all without communicating with any other processes.


## 参考

1. “Operating Systems: Three Easy Pieces“ (Chapter: The Multi-Level Feedback Queue) by Remzi Arpaci-Dusseau and Andrea Arpaci-Dusseau. Arpaci-Dusseau Books, 2014.
2. “Operating Systems: Three Easy Pieces“ (Chapter: Scheduling: Proportional Share) by Remzi Arpaci-Dusseau and Andrea Arpaci-Dusseau. Arpaci-Dusseau Books, 2014.