进程切换策略
引言
OSTEP（Operating Systems: Three Easy Pieces）第4章的课后练习提供了一个进程运行模拟器，可以根据不同的参数模拟出不同策略下进程运行结果的具体区别。
本文针对该课后练习的几组对比实验，对进程切换策略的选择结果做出推测和总结。
正文
模拟器用一个单cpu的模型模拟多个进程的运行：每个进程由若干条指令构成，每条指令以一定概率是cpu指令或io指令，io指令发起后进程会阻塞固定时长（默认5个时间片）等待设备完成。输出里每个时刻各进程处于RUN（占用cpu，其中RUN:io是发起io，RUN:io_done是io完成后的收尾）、READY（就绪等待调度）、BLOCKED（等待io完成）、DONE（结束）四种状态之一，带*的时刻表示恰有一次io完成。现实里发起io对应一次系统调用，进程在设备完成工作前无事可做，这正是调度器接管cpu的时机。
纯cpu指令进程运行
在没有io请求发出时，操作系统按顺序执行每个进程，只在上一个进程结束时发生进程切换：
命令介绍：-c（计算并显示运行结果）-p（统计运行数据）-S（进程发起io时是否切换）-I（io完成后切换给谁）-l（进程列表，每个进程写成x:y，x为指令数，y为该条指令是cpu指令的概率）-L（单次io持续时长，默认5）-s（随机种子）
> python ./process-run.py -c -p -S SWITCH_ON_IO -I IO_RUN_IMMEDIATE -l 5:100,5:100
Time PID: 0 PID: 1 CPU IOs
1 RUN:cpu READY 1
2 RUN:cpu READY 1
3 RUN:cpu READY 1
4 RUN:cpu READY 1
5 RUN:cpu READY 1
6 DONE RUN:cpu 1
7 DONE RUN:cpu 1
8 DONE RUN:cpu 1
9 DONE RUN:cpu 1
10 DONE RUN:cpu 1
Stats: Total Time 10
Stats: CPU Busy 10 (100.00%)
Stats: IO Busy 0 (0.00%)
不出意料，此时cpu的运行效率是100%。
cpu和io指令
当加入io读取指令时，情况会变得复杂。在这种情况下，进程的运行顺序对运行效率有很大影响：
> python ./process-run.py -c -p -S SWITCH_ON_IO -I IO_RUN_IMMEDIATE -l 5:100,1:0
Time PID: 0 PID: 1 CPU IOs
1 RUN:cpu READY 1
2 RUN:cpu READY 1
3 RUN:cpu READY 1
4 RUN:cpu READY 1
5 RUN:cpu READY 1
6 DONE RUN:io 1
7 DONE BLOCKED 1
8 DONE BLOCKED 1
9 DONE BLOCKED 1
10 DONE BLOCKED 1
11 DONE BLOCKED 1
12* DONE RUN:io_done 1
Stats: Total Time 12
Stats: CPU Busy 7 (58.33%)
Stats: IO Busy 5 (41.67%)
> python ./process-run.py -c -p -S SWITCH_ON_IO -I IO_RUN_IMMEDIATE -l 1:0,5:100
Time PID: 0 PID: 1 CPU IOs
1 RUN:io READY 1
2 BLOCKED RUN:cpu 1 1
3 BLOCKED RUN:cpu 1 1
4 BLOCKED RUN:cpu 1 1
5 BLOCKED RUN:cpu 1 1
6 BLOCKED RUN:cpu 1 1
7* RUN:io_done DONE 1
Stats: Total Time 7
Stats: CPU Busy 7 (100.00%)
Stats: IO Busy 5 (71.43%)
显而易见，想要最大化cpu利用率，应该先发起io操作，在io进程阻塞的时候运行其他进程的cpu指令。
SWITCH策略
如果将-S选项改为SWITCH_ON_END：进程发起io时不切换到其他就绪进程，cpu在io等待期间一直空等。
> python ./process-run.py -c -p -S SWITCH_ON_END -I IO_RUN_IMMEDIATE -l 1:0,5:100
Time PID: 0 PID: 1 CPU IOs
1 RUN:io READY 1
2 BLOCKED READY 1
3 BLOCKED READY 1
4 BLOCKED READY 1
5 BLOCKED READY 1
6 BLOCKED READY 1
7* RUN:io_done READY 1
8 DONE RUN:cpu 1
9 DONE RUN:cpu 1
10 DONE RUN:cpu 1
11 DONE RUN:cpu 1
12 DONE RUN:cpu 1
Stats: Total Time 12
Stats: CPU Busy 7 (58.33%)
Stats: IO Busy 5 (41.67%)
可以推断出，当操作系统选择在进程阻塞时让cpu空等，进程的运行顺序对整体运行效率就不再起作用，一次io会退化成固定损失5个时间片（-L的默认时长）的串行开销。
进程发起io阻塞时立刻切换到其他就绪进程，是重叠io等待与cpu执行的前提。
IO_RUN策略
另外一个重要策略是io操作完成时，是否要立刻切换回刚完成io的进程。用-I选项进行模拟：
> python ./process-run.py -c -p -S SWITCH_ON_IO -I IO_RUN_IMMEDIATE -l 5:60,7:80
Time PID: 0 PID: 1 CPU IOs
1 RUN:io READY 1
2 BLOCKED RUN:cpu 1 1
3 BLOCKED RUN:cpu 1 1
4 BLOCKED RUN:cpu 1 1
5 BLOCKED RUN:cpu 1 1
6 BLOCKED RUN:cpu 1 1
7* RUN:io_done READY 1
8 RUN:io READY 1
9 BLOCKED RUN:io 1 1
10 BLOCKED BLOCKED 2
11 BLOCKED BLOCKED 2
12 BLOCKED BLOCKED 2
13 BLOCKED BLOCKED 2
14* RUN:io_done BLOCKED 1 1
15* READY RUN:io_done 1
16 READY RUN:cpu 1
17 RUN:cpu DONE 1
18 RUN:cpu DONE 1
19 RUN:cpu DONE 1
Stats: Total Time 19
Stats: CPU Busy 15 (78.95%)
Stats: IO Busy 11 (57.89%)
> python ./process-run.py -c -p -S SWITCH_ON_IO -I IO_RUN_LATER -l 5:60,7:80
Time PID: 0 PID: 1 CPU IOs
1 RUN:io READY 1
2 BLOCKED RUN:cpu 1 1
3 BLOCKED RUN:cpu 1 1
4 BLOCKED RUN:cpu 1 1
5 BLOCKED RUN:cpu 1 1
6 BLOCKED RUN:cpu 1 1
7* READY RUN:io 1
8 RUN:io_done BLOCKED 1 1
9 RUN:io BLOCKED 1 1
10 BLOCKED BLOCKED 2
11 BLOCKED BLOCKED 2
12 BLOCKED BLOCKED 2
13* BLOCKED RUN:io_done 1 1
14 BLOCKED RUN:cpu 1 1
15* RUN:io_done DONE 1
16 RUN:cpu DONE 1
17 RUN:cpu DONE 1
18 RUN:cpu DONE 1
Stats: Total Time 18
Stats: CPU Busy 15 (83.33%)
Stats: IO Busy 12 (66.67%)
结果有点出人意料，居然是io完成后暂不切回（IO_RUN_LATER）的策略运行效率更高。按道理来说，在io操作完成后立刻切换回该进程可以最大化io的利用，从而减少cpu的等待时间。
对比两组输出可知，IO_RUN_LATER那一组里，进程二（PID:1）在进程一（PID:0）阻塞期间多运行了一条cpu指令，总时间因此从19压到18。
这么看来哪种策略更优，非常依赖进程的先后和进程中指令的顺序。
为了探究IO_RUN_LATER的反超是否只是特例，又进行了多组测试。测试结果发现，在少量进程、少量指令的情况下，两种策略的模拟结果非常相近，都有胜出的情况。但是，在进程变多、指令也变多的情况下，io完成后立刻切换回该进程的策略平均表现更优，甚至有几次可以做到100%利用率。
> python ./process-run.py -c -S SWITCH_ON_IO -I IO_RUN_IMMEDIATE -l 5:40,6:60,2:0,20:100 -p
Time PID: 0 PID: 1 PID: 2 PID: 3 CPU IOs
1 RUN:io READY READY READY 1
2 BLOCKED RUN:cpu READY READY 1 1
3 BLOCKED RUN:io READY READY 1 1
4 BLOCKED BLOCKED RUN:io READY 1 2
5 BLOCKED BLOCKED BLOCKED RUN:cpu 1 3
6 BLOCKED BLOCKED BLOCKED RUN:cpu 1 3
7* RUN:io_done BLOCKED BLOCKED READY 1 2
8 RUN:io BLOCKED BLOCKED READY 1 2
9* BLOCKED RUN:io_done BLOCKED READY 1 2
10* BLOCKED READY RUN:io_done READY 1 1
11 BLOCKED READY RUN:io READY 1 1
12 BLOCKED READY BLOCKED RUN:cpu 1 2
13 BLOCKED READY BLOCKED RUN:cpu 1 2
14* RUN:io_done READY BLOCKED READY 1 1
15 RUN:io READY BLOCKED READY 1 1
16 BLOCKED RUN:cpu BLOCKED READY 1 2
17* BLOCKED READY RUN:io_done READY 1 1
18 BLOCKED READY DONE RUN:cpu 1 1
19 BLOCKED READY DONE RUN:cpu 1 1
20 BLOCKED READY DONE RUN:cpu 1 1
21* RUN:io_done READY DONE READY 1 1
22 RUN:cpu READY DONE READY 1
23 RUN:io READY DONE READY 1
24 BLOCKED RUN:cpu DONE RUN:cpu 1 1
25 BLOCKED RUN:cpu DONE RUN:cpu 1 1
26 BLOCKED RUN:io DONE RUN:cpu 1 1
27 BLOCKED BLOCKED DONE RUN:cpu 1 2
28 BLOCKED BLOCKED DONE RUN:cpu 1 2
29* RUN:io_done BLOCKED DONE RUN:cpu 1 1
30 DONE BLOCKED DONE RUN:cpu 1 1
31 DONE BLOCKED DONE RUN:cpu 1 1
32* DONE RUN:io_done DONE READY 1
33 DONE DONE DONE RUN:cpu 1
34 DONE DONE DONE RUN:cpu 1
35 DONE DONE DONE RUN:cpu 1
36 DONE DONE DONE RUN:cpu 1
37 DONE DONE DONE RUN:cpu 1
38 DONE DONE DONE RUN:cpu 1
39 DONE DONE DONE RUN:cpu 1
40 DONE DONE DONE RUN:cpu 1
41 DONE DONE DONE RUN:cpu 1
Stats: Total Time 41
Stats: CPU Busy 41 (100.00%)
Stats: IO Busy 27 (65.85%)
分析结果可以发现，当cpu指令数占多数时，io结束后立刻切回的策略可以最大化填充io阻塞的间隙，提高cpu的利用效率。
对于这种结果，可以这样理解：刚结束io的进程有更大的可能再次发起io，并且现代计算机运行时，cpu指令数通常远多于io指令数，此时采取IO_RUN_IMMEDIATE是更优的选择。
io完成后立刻切换回刚完成io的进程，是平均意义下更优的选择。
小结
进程切换策略的本质是重叠：让一个进程的io等待与其他进程的cpu执行同时进行。SWITCH_ON_IO是重叠的前提，没有它，io就退化成固定损失5个时间片的串行开销，进程顺序也随之失去意义；进程的先后次序决定重叠的机会有多大，先发起io再运行cpu指令能填满阻塞的间隙；io完成后的切换策略影响最小，少量进程时互有胜负，进程和指令变多后IO_RUN_IMMEDIATE平均更优，因为刚结束io的进程大概率还会再次发起io，尽早切回它，下一次重叠就能尽早开始。
一个最优的实践是，SWITCH_ON_IO搭配IO_RUN_IMMEDIATE，并让会发起io的进程先于纯cpu进程投入运行，除非负载只有一两个短进程，此时两种io完成策略的差距可以忽略，不必为此费心。
$ 正在加载评论…