什么是Scheduling? 为什么我们需要Scheduling？

When two or more processes/threads are simultaneously in the ready state, if only one CPU is available, a choice has to be made which process to run next. 做出这个choice的被称为Scheduler，这个过程叫Scheduling。Scheduler使用的算法叫scheduling algorithm。

随着计算机硬件的飞速发展（摩尔定律），CPU的资源不再是scarce的了，scheduling也就显得没那么重要了，举个简单的例子，如果一个计算机的CPU运算速度无限快，根本就没有必要调度，随便运行哪个程序都可以，因为都是很快就运行完了，还设置复杂的调度算法？何必呢。

但对于networked servers来说，scheduling又显得重要起来，因为servers通常会接收来自不同用户的requests，这时就需要scheduler发挥作用了。

根据使用CPU时间的长短我们可以把process分成两类，一类叫compute-bound,或者叫CPU-bound,另一类叫I/O-bound。如下图所示，CPU-bound的process会经常使用CPU的资源，而I/O-bound的process不经常使用CPU。

随着现在CPU的运算速度越来越快，CPU使用的时间越来越短，很多时候我们都是处于I/O-bound的状态，所以我们更关注IO-bound。

When to Schedule

When a new process is created. 比如Unix系统中使用了fork()指令，child process的状态和parent process完全相同，都处于ready的状态，那么先运行child还是parent呢？
When a process exits。当一个process运行完之后我们必须决定下一个运行的process。
When a process blocks on I/O。当一个process因为I/O阻塞了，我们必须决定下一个运行的process。
When an I/O interrupts occurs。一个程序从waiting for the I/O到可以运行了，这时候需要scheduler决定是否运行这个刚准备就绪的process。

Scheduling Algorithms

Scheduling in Batch Systems

First-Come, First-Served

这个算法的另一个名字叫FIFO，也就是队列。

non-preemptive
not optimal

挺简单的，没什么好说的，注意一下waiting time的计算。

优点是非常简单，易于实现。

缺点是：

Waiting time depends on arrival order.
Potentially long wait for jobs that arrive later.
Convoy effect:Short jobs stuck waiting for long jobs.(reduces utilization of I/O devices)

什么是Convoy effect呢？ Convoy effect有两种表现形式：

All I/O devices idle even when the system contains lots of I/O jobs.
CPU idle when even if system contains CPU bound jobs.

SJF

Shortest Job First algoirithm has two versions. One version is non-preemtive and one is preemtive.

SJF有一个特殊的地方，它是有前提的，它的requirement是：the elapse time needs to know in advance.

如果所有的jobs都是同时到达的，那么SJF是optimal的，

Preemtive SJF is also called Shortest Remaining Time Next(SRTN).

SJF的优点是：

Provably optimal for minimizing average wait time。
Helps keep I/O devices busy.

缺点：

Not pratical:Cannot predict future CPU burst time.
Starvation:Long jobs may never be scheduled.

SJF还有一个特点是它不支持优先级调度，因为它自己规定了优先级(时间短的优先)。

Scheduling in Interactive System

对于Interactive system来说，算法总是preemtive的。

Round-Robin Scheduling

RR其实就是preemtive的FCFS，它假设所有processes有着相同的优先级，并且视processes为一个queue。

这里对于time quantum有一个需要注意的地方：time quantum的长短如何选定？

如果time quantum太大的话，虽然减少了context switch的发生次数，但是会让它变成FCFS，有着糟糕的响应时间。如果太短的话，增加了context switch的发生的次数，并且没有有效利用CPU,花了太多时间在switch上而不是利用CPU。

下面再来整理一下RR的优缺点。优点：

Fair allocation of CPU across jobs,no starvation.
Low average waiting time when job lengths vary.
Shortest jobs finish relatively quickly.
Turnaround time typically larger than SRTF but better response time.

缺点：

Poor average waiting time with similar job lengths.
performance depends on length of time-slice.
Do not consider priority.
High overhead due to frequent context switches.

Priority Scheduling

其实也就是带着优先级的FCFS。

优点：

Static priorities work well for real time systems
Dynamic priorities work well for general workloads.

缺点：

Low priority jobs can starve
May not give the best AWT

Multi-Level Queue

Used in scenarios where the processes can be classified into groups based on property like process type,CPU time,IO access,memory size,etc. Split the Ready Queue in serveral queues, processes assigned to one queue permanently.

把各种不同优先级的processes分成不同的queue,each queue with its own scheduling algorithm.

Multi-Level Feedback Queue

将一份job分成不同的level，这个level没运行完就到下个level。和muti-level queue有所不同。

Lottery Scheduling

基于概率的调度，Give processes lottery tickets. At scheduling time, a lottery ticket is chosen at random, and the process holding that ticket gets that resource.

意思就是拿到更多票的运行的概率会高。

优点是：

simple
highly responsive
can support cooperation between processes
easy to support priority and propotion requirement

Modern Operating Systems chapter 2 notes Scheduling