磁盘的IO重排序与调度策略

万芝堂是百年老字号了，主营中草药，并兼老中医出诊。虽然万芝堂有近百年的历史，但活动范围仅限北京城，即使在北京城也仅有2个分号。最近万芝堂换了新掌柜的。新掌柜新官上任三把火，不仅在北京增加了分号数量，在保定府也开了好几家分号。

图1 总号与分号

保定府本身也比较大，分号开了5家，具体的在各大街区基本都有，繁华街区开了3家。这样也符合供求关系的规则，毕竟繁华街区人多，需要草药的人也会多一些。

图2 保定府分号

分号多了，管理的难度就上来了。首先要考虑的是草药质量的问题。如果各个分号各自负责采购，药品质量很难保证质量。况且还有很多是秘方药，不可能在分号生产。思来想去，只能在总号生产，然后通过镖局分发到各个分号。由于实际情况不同，各个分号需要补充的草药类型可能是不同的。具体方法是分号提供草药的类型和数量，总号统一分发。

策略确定好了，生意也就这么运行了。万芝堂就找了本地一家比较有名的镖局---会友镖局。比较草药这东西事关人命，不能不重视，找一个好点的镖局还能放心一些，免得有些小镖局掉包。

很快，保定府的分号1通过飞鸽传书要求发一批保命丸。总号收到消息马上与会友镖局联系，安排发货。镖局的人刚把货送到保定分号1，还没喘口气，又来新单子了。万芝堂又要向保定府分号2发一批狗皮膏药。会友镖局的人马不停蹄的将药运到了保定府分号2。回来不久，饭还没顾上吃一口，万芝堂又要发送一箱麻沸散到保定府分号3。

图3 傻干活

IO的蓄流和泄流

大当家的感觉心力交瘁，浑身乏力啊。虽然钱是给够了，这么天天溜也不是个事啊。于是大当家叫上二当家和三当家一块商量一下对策。

三当家若有所思的说：“既然万芝堂生意这么火，那我们何不把草药先放到镖局。在镖局压两三天，如果有新的货物要送，我们就一起送过去，要是没有，那我们再送也不迟。”(注：这就是磁盘驱动中的蓄流/泄流，也就是IO不会马上发送给驱动，而是攒一批再发送)

其他当家的觉得此计甚好，于是大家一拍即合。

没过两天，万芝堂又要给保定府的分号1送一批大力丸。镖局将大力丸收下，但并没有安排马上送货。果然，第二天万芝堂有送过来一批狗皮膏药，要送到分号5。又等了2天，不见万芝堂来送货，于是会友镖局就押镖送货，将大力丸和狗皮膏药一起送到了保定府，并依次送到了分号1和分号5。

图4 赞起来一起

IO重排序

万芝堂的生意确实是好，会友镖局押镖的刚回来，万芝堂又给送过来一批货，而且这次货物非常多。上面有个清单，万芝堂交代依照清单送货就行。清单是这么写的：

• 分号1 -> 狗皮膏药一箱
• 分号4 -> 大力丸一箱
• 分号2 -> 健骨粉两箱
• 分号5 -> 保命丸一箱
• 分号3 -> 保命丸一箱

会友镖局马不停蹄的将货物送到了保定府。由于长途跋涉，大家实在太累了。于是大当家的先让大家找个客栈休息，明天再挨家送货。

在休息的时候大当家的想：“虽然这几家都在保定府内，但保定府这么大，我要想想怎么送省力一些。”

大当家的继续想：“既然都已经到保定了，也不差这一时半会儿了。那我就不安清单的顺序送货，我按整个路程送货，怎么方便我就怎么来。”于是大当家的将本来应该由图5左侧的送货路径安排成了图5右侧的送货顺序。这样，整个送货的路径减少了一大半。(注：这就是磁盘IO的重排序，尽量保证路径最优，避免磁臂来回摆动的耗时)

图5 规划路径

随着生意越做越多，会友镖局的名声也打出来了。除了万芝堂，其它XX堂也都让会友镖局送货。会友镖局还是故技重施，所有货物攒到一定量之后再发。

Deadline调度策略

有一天万芝堂的掌柜的过来了，说：“大当家的啊，你们这不靠谱啊。我这前几天发的货，怎么还没送到啊。保定府那边都发了两个飞鸽传书了。”

大当家的赔笑道：“不好意思啊，佟掌柜，最近货物实在太多，我也是没办法啊。”

经过两人的协商，最后万芝堂的货物送来后都要确定一个送到的时间，然后会友镖局必须在规定时间内送到。这样，分号再也不会出现过了半个月还没收到货的情况。(注： 这就是磁盘的Deadline调度策略，保证IO能在规定时间内完成)

CFQ调度策略

虽然其它XX堂也让会友镖局送货，但他们的分号本来就少，而且有些并不在保定府。比如医仁堂的分号在保定有一家，在太原有一家，而万友堂的分号则在石家庄。以医仁堂为例，他的货物每次总是放好几天，什么时候万芝堂送货的时候，会友镖局才捎带着将货物一起送过去。因为单独送医仁堂的那点货物实在是不划算。

由于现在货物多，押镖的人有少，实在忙不过来。会友镖局大部分货物是送往保定的，太原等其它地方的货物比较少。因此，镖局大部分时间往返北京保定之间，太原的货物总是很慢才能送到。这导致医仁堂非常不满意，于是医仁堂的掌柜的去找大当家的理论：“我们付的钱又不少，凭啥我们的货物发送的总是这么慢.....”

虽然吵了一架，但大当家还是一个比较好的CEO，他反思到：“顾客就是上帝，确实不应该这样。我们应该保证每一个客户的满意，不能只顾大客户啊!”

于是大当家的制定了一个策略，要求大家发货的时候尽量保证每个客户的货物都能尽量公平的发送出去。即使是小客户货物少，也不能不发。(注： 这就是磁盘的CFQ调度策略，它保证各个进程尽量公平)

各种制度不断完善，镖局的生意也越来越好了。