C|进程调度|单核CPU调度

CPU调度，决定了CPU执行进程的策略，好的调度policy需要兼顾进程首次被调度的等待时间和进程结束执行的等待时间，因此在算法设计上极其精妙。本章完全Copy自OSTEP，介绍了基础的调度算法。

初始条件：

我们先简化条件，从理想情况开始，再逐步去除限制

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., they perform no I/O)
5. The run-time of each job is known.

Metric I

进程结束所等待的时间

[公式]

条件一

假设条件1取消，进程ABC用时分别为100/10/10

FIFO

总用时100/110/120

SJF

因此我们将队列变为优先队列，Shortest Job First，总用时10/20/120

条件二

假设条件2取消，进程BC延迟10秒到达，总用时100/110/120

由于不能Switch，因此A执行后必须执行到底，无法优化

条件三

假设条件3取消，可以进行Process Switch

Shortest Time-to-Completion First （STCF）

每次新job进入，重新进行调度，按照剩余时间进行调度（可以看作把job分割）

Metric II

首次被调度等待的时间

[公式]

Round Robin

时间切片，每次切片都轮换所有进程。这样避免了长时间进程过长等待，但是会带来更多Switching Cost(Context,flush TLB & pipeline)

条件四

假设条件4取消，可以进行I/O

当进程A进行I/O时，由于I/O速度比CPU更慢，因此CPU需要等待I/O完成，此时CPU处于闲置，因此可以Switch给其他进程。

按耗时占比可以分为I/O-intensive 和 CPU-intensive

条件五

假设条件5取消，在开始进程前进程时间未知

Multi-Level Feedback Queue（MLFQ）

最小化

[公式]

,尽可能优化

[公式]

以历史预测未来（这个思想在很多算法中都有使用，隔壁线性分配的内存再分配算法里也用了

，此外还有cache，hardware branch)。但是假如历史并不能很好预测未来或者预测了相反的未来，那么反而引起误导。

Basic Rules

划分优先级，每个优先级都有独立的队列

Rule 1：

同优先级，Round Robin

Rule 2：

不同优先级，执行高优先级的进程（减少切换开销）

Rule 3：

新进程优先级最高（这样减少了response time）

Rule 4a：

单次执行一次完整time slice，优先级减少一级（这样运行时间长的自然就低优先级了）

Rule 4b：

如果执行了I/O，优先级不变（I-O intensive，可以高优先级处理，反正大部分时间都是空闲的）

问题：

1.starvation

大量I/O-intensive 挤占高优先级，导致CPU-intensive无法执行。

2.Gaming scheduler attack

故意进行短I/O，不降级（CPU-intensive 伪装成I/O-intensive欺诈）

3. 程序行为改变

前期主要使用CPU，后期主使用I/O，然而优先级无法逆转

Extra Rules

Rule 5：

定期将所有进程全部移动至最高优先级（处理程序行为改变）

change Rule 4：

累积执行一定时间限额后降级（处理attack和starvation）

问题：

如何确定参数，如优先级，time slice长度，多久重置一次优先级。

考虑typical workload 下的最佳参数（黑盒炼丹

一般而言，训练的结果是：

高优先级给的slice短

低优先级给的slice长

但是这种训练方法肯定没办法处理所有情况，因此可以用一个配置文件，让管理员作为调参侠，手动调节。

疑惑

首次被调度等待的时间

[公式]

Round Robin

时间切片，每次都轮换所有进程。这样避免了长时间进程过长等待，但是会带来更多Switching Cost(Context,flush TLB & pipeline)

？讲道理，如果metric只是first turn的话，那我直接每次新进来进程做个round robin，让新进程first turn很短，然后切回正常的优先队列就好了。

我认为这里的Metric应该是

[公式]

也就是不能让一个进程被闲置太久，而不是只看第一次response的时间。

由于现代PC都是多核处理器，因此等我之后有时间再发多核版本。可见

Reference:OSTEP