Operating System Concepts ——chapter 6——CPU Scheduling

调度算法目标：
通过多道程序设计来获得尽可能大的CPU利用率。

基本算法：

FCFS

first come, first server
看起来很公平，但是并不一定合理。
容易导致短作业进程等待时间过长。

SJF

shortest job first
选择执行时间最短的优先执行

非抢占式

如果一个作业已经在执行了，即使有执行时间更短的作业到达，依然保持已经在执行的作业，不进行抢占。

抢占式

如果一个作业已经在执行了，如果有执行时间更短的作业到达，则执行时间更短的作业被执行。

等待时间=结束时刻-执行时间-到达时刻

怎么知道作业下次执行时间是多少？
指数平均法：

priority scheduling

每个进程都被赋予一个优先级。优先级越高越先执行。
SJF是优先级调度的一种

缺点：
infinite blocking(饥饿)
解决办法：
aging.
动态优先级，等待时间越长，优先级越高。

Round-Robin scheduling

时间片轮转。一般每个时间片为10-100ms。

相比SJF，RR算法时间片会小一些，但是有更好的实时响应。

multilevel queue

ready queue is partitioned int separate queues:
forground(interactive)
background(batch)
Each queue has its own scheduling algorithm:
foreground – RR
background – FCFS

multilevel feedback queue

a process can move between the various queues.
比如随着CPU的使用变化可以在I/O-bound 队列和CPU-bound中切换。
例如：
3 queues:
Q0– RR with time quantum 8 milliseconds
Q1– RR time quantum 16 milliseconds
Q2– FCFS
Scheduling：
Lower-priority processes cannot be executed only higher-priority queue is empty
A new job enters queue Q0which is servedFCFS
When it gains CPU, job receives 8 milliseconds
If not finish in 8 milliseconds, moved to queue Q1.
At Q1 job is again served FCFS and receives 16 additional milliseconds
If it still does not complete, it is preempted and moved to queue Q2.