基于负载特性和服务时间评估改进的AS调度算法

陈金忠，姚念民，蔡绍滨，孙美玲

(哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150000)

1 引言

随着CPU与内存速度的不断提高，存储系统成为计算机性能的瓶颈。I/O调度层已经成为存储系统不可或缺的一部分[1,2]。I/O调度算法大致分为3大类。

第1类是实时任务I/O调度算法，这类算法主要是在保证任务实时性的条件下，最大化任务的吞吐量。SCAN-EDF[3]将相同截止时间的请求划分到同一组，然后在每一组内应用SCAN算法进行扫描。SCAN-EDF只对相同截止时间的任务按磁头移动方向调度，其性能取决于具有相同截止时间任务的数目。为了对更多任务进行优化，DM-SCAN(deadline-modification-SCAN)[4]将任务的截止时间修改为最短任务的截止时间dmin，将任务的完成时间不超过截止时间dmin的所有任务划分到同一组，然后在组内应用SCAN算法调度提高任务的吞吐量。RG-SCAN[5](reschedulable-group-SCAN)引用了RG-group的概念。它首先寻找包含最多任务数的集合，集合中所有任务的完成时间不超过任务的截止时间，此集合称为RG-group，然后对RG-group应用SCAN算法来提高任务的吞吐量。RG-SCAN不需要修改任务的截止时间。SCAN-EDF、DM-SCAN和RG-SCAN都是在组内进行任务调度，属于局部调度算法。GSR(global seek-optimizing real-time)[6]根据磁头移动方向将任务分组，然后在保证实时性的前提下，在组与组之间调度任务，以达到吞吐量的最大化。GSR是全局调度算法。

第2类是预定带宽或时延的I/O调度算法，这类算法用于满足用户的预定带宽或者预定时延，如DVT(differential virtual time)[7]、Hybrid[8]、Argon[9]、pClock[10]、adaptive DRR(deficit round-robin)[11]、MBAC(measurement-based admission control)[12]和BFQ(budget fair queuing)[13]等算法。这些算法在满足预定带宽或时延的条件下，提高任务的吞吐量。

第3类调度算法是为了提高吞吐量而设计的算法，主要有SCAN、LOOK、SSTF(shortest seek time first)、NOOP(no operation)、Deadline、AS(anticipatory scheduling)和 CFQ(completed fairness queuing)等调度算法[14～17]。这些算法旨在减少磁头移动的距离。NOOP、CFQ、Deadline和AS是当前Linux I/O调度层常用的调度算法。NOOP实现了最简单的FIFO队列，所有的请求除了合并之外，采用先来先服务的策略。CFQ为每个进程分配一个队列，按照I/O请求的扇区地址进行排序，每个进程的I/O请求以循环的方式服务。CFQ对于每个进程都是完全公平的。相对于NOOP来说，先到来的请求不一定先服务，CFQ可能出现I/O请求饿死的现象。Deadline在CFQ的基础上，为每个I/O请求分配了截止时间，解决了饿死的问题。CFQ和Deadline考虑的焦点在于满足零散I/O请求上，对于连续的I/O请求，比如顺序读，并没有做优化。并且这些调度算法都是持续性工作的[18]，一旦服务完I/O请求，立即调度当前队列I/O请求。为了满足随机I/O和顺序I/O混合的场景。预期调度算法(AS)在请求提交完之后并不立即处理当前队列中的I/O请求，而是等待一段空闲时间，以等待下一个邻近的请求被提交，等待周期为6 ms。这样给应用程序提供了提交相邻磁道位置的I/O请求的机会，从而减少磁头寻道的距离。但AS存在两点不足。第一，不同负载特性的I/O请求对AS的性能产生很大影响。对于I/O密集型的应用程序，2个I/O请求到达时间间隔可能很小(<6 ms)，使用6 ms的预期周期，显然浪费了时间。对于I/O请求时间间隔较大的应用程序(>6 ms)，使用6 ms的预期周期，必然会增加预期失败的次数。第二，AS只根据当前队列中I/O请求的磁道位置而没有根据I/O请求的服务时间来决定是否预期下一个请求，这就导致预期不准确。

针对AS算法存在以上2个方面的不足，提出了一种改进的基于负载特性和服务时间评估的AS调度算法(WPCAS)，主要分为进程归类模块(PC)和服务时间评估模块(STE)。PC模块通过分析负载的访问特性，为不同类型的负载设置不同的预期周期。STE模块根据I/O请求的服务时间决定是否预期下一个I/O请求。相比于AS，WPCAS不仅适应了负载的动态变化，而且使预期更加准确。因此，本文提出的WPCAS调度算法在吞吐量和伪空闲周期等方面的性能都优于传统的AS调度算法。

2 相关工作

Linux I/O子系统主要包括虚拟文件系统、页面高速缓存、通用块设备层和I/O调度层。Linux内核的调度算法集中于I/O调度层，主要有以下4种调度算法：NOOP、Deadline、CFQ 和AS。

2.1 I/O请求服务时间模型

其中，旋转时延与磁盘转速相关，传输时延等于I/O请求除以数据传输率。结合式(1)和式(2)，可计算I/O请求的服务时间。

2.2 AS预期策略

2.2.1 AS预期原理

AS执行完成当前读请求，并不立即执行队列的下一个请求，而是预留6 ms的时间窗口去等待下一个即将到来的请求。如果下一个到来的请求与当前已完成请求的磁道位置是邻近的，那么将会极大提高I/O的性能。为了预期下一个请求，AS算法维护每类进程历史I/O请求的平均到达时间间隔和磁道位置信息[20]。

AS预期原理：AS根据I/O请求的磁道位置判断从当前队列挑选的请求是不是“最优”请求。如果挑选出I/O请求的磁道位置与当前磁头位置的距离小于进程历史相邻I/O请求磁道位置之差的平均值，就认为此请求是“最优”请求，从而立即服务该请求。否则，启动定时器，预期下一个请求[20]。

2.2.2 AS预期机制状态转换

图1显示了AS的预期机制状态转换图。当上一个I/O请求完成时，处于FINISHED状态，I/O调度层根据上一节提到的预期原理判断是否预期下一个请求。如果预期下一个I/O请求，那么启动定时器，并将定时器的超时时间设置为6 ms，进入了WAITING状态。否则，直接调度当前队列中的I/O请求，进入SCHEDULING状态。当定时器超时，表示预期失败，那么从当前队列选取I/O请求进行服务，进入SCHEDULING状态。当预期成功时，服务预期到的I/O请求，也进入SCHEDULING状态。此后，将I/O请求分发到通用块设备层中进行调度，进入RUNNING状态。当执行完I/O请求时，又回到了FINISHED状态。

图1 预期机制状态转换

2.3 AS执行流程

Linux I/O调度层的AS算法 具有以下几个特征。

1)近似单向电梯算法,可以向后寻道的最大磁道距离为1 024×1 024个扇区。

2)为读写操作指定不同的超时时间，读超时时间为125 ms，写超时时间为250 ms。

3)读写操作采用批处理的策略。为读batch与写batch分配不同的超时时间，读batch超时时间为500 ms，写batch超时时间为125 ms。

4)预期周期：AS为I/O请求指定6 ms的预期周期，期望下一个请求邻近于当前请求。

图2描述了AS算法的执行流程。AS维护FIFO队列和SORT队列。FIFO队列是按照I/O请求到达时间进行排序的队列，SORT队列是按照I/O请求的磁道位置与当前磁头位置的距离远近进行排序的。首先，如果FIFO队列中有超过截止时间的请求，就马上服务这个请求，并从FIFO队列和SORT队列删除该请求。否则，根据预期原理决定是否预期下一个I/O请求。然后,AS调度算法将当前队列中的I/O请求或者是预期到的I/O请求分发到通用块设备层的调度队列中去。最后，由磁盘驱动器来完成数据的实际传输。

图2 预期调度算法的处理流程

3 WPCAS调度策略

综上所述，AS有2个特点。第一，预期周期为固定的6 ms。第二，根据当前队列中I/O请求的磁道位置与当前磁头位置的距离是否小于进程历史相邻I/O请求磁道位置之差的平均值，决定是否预期下一个I/O请求。AS有2点不足。首先，不同负载特性的I/O请求会对AS的性能产生很大影响。对于I/O密集型的应用程序，2个I/O请求的到达时间间隔可能很小(<6 ms)，使用6 ms的预期周期，显然浪费了时间。对于I/O请求时间间隔较大的应用程序(>6 ms)，使用6 ms的预期周期，必然会增加预期失败的次数。其次，根据I/O请求的磁道位置来判断是否预期，不够准确。为了更好地适应负载变化和更准确的预期I/O请求，提出了一种改进的基于负载特性和服务时间评估的AS调度算法(WPCAS)，它包括进程归类模块(PC)和服务时间评估模块(STE)。PC模块主要功能是根据I/O请求的负载特性，将进程归类并设置为不同的预期周期。STE模块的主要功能是根据I/O请求的服务时间来判断是否预期下一个I/O请求。

3.1 进程归类模块(PC)

AS对所有的负载都使用固定的预期周期(6ms)，不能适应负载的动态变化。本文提出了进程归类的方法，其基本思想是根据负载特性决定预期周期的大小，将不同类别的进程映射为不同的预期周期。进程归类模块首先找出I/O请求到达时间间隔最密集的区域，然后将这个区域对应的到达时间间隔作为预期周期。下面给出一些定义。

定义1Tthink：I/O请求的到达时间间隔。

定义2概率密度函数f(Tthink)表示Tthink的概率密度。

定义3分布函数F(Tthink)表示Tthink的分布。

定义4Map(i)表示进程i映射的预期周期。

假设I/O请求的到达时间间隔在0到20 ms之间。由定义可知

其中，Tas表示预期成功的平均等待时间，定义为预期成功所花费的总时延除以预期成功的I/O请求数。γ是pa,b的门限值。当pa,b≥γ，那么选择整数j∈[a,b]，作为进程的预期周期。当pa,b＜γ，选择Tas作为预期周期。因此，进程归类模块根据Map函数动态调整预期周期的长度，适应了负载的动态变化。

3.2 服务时间评估模块(STE)

针对AS根据I/O请求的磁道位置来判断是否预期下一个I/O请求，提出了更精确的基于服务时间的预期策略。其基本思想是比较当前队列I/O请求的服务时间和预期情况下I/O请求服务时间的大小，决定是否预期。

定义5Si表示刚服务完的第i个I/O请求的磁道位置，表示从当前队列挑选的I/O请求的磁道位置，此请求是离当前磁头位置最近的。表示预期成功的I/O请求的磁道位置。

定义6一个I/O请求的三元组指I/O请求i的寻道延迟，Tr指I/O请求的旋转延迟，取决于磁盘转速。Tt指I/O请求的传输延迟，取决于数据传输率。

定义7进程历史相邻I/O请求的磁道位置之差的平均值aseek_dist定义如下：

其中，Ts表示预期成功的服务时间，Tf表示预期失败的服务时间。假设Tas表示预期成功平均等待时间。Taf表示预期失败的平均等待时间，预期周期为Pms，则Taf等于预期周期P。显然，预期成功的服务时间Ts等于预期到I/O请求的寻道时延，旋转时延，传输时延和预期成功的平均等待时延之和，如式(9)所示

根据式(9)和式(10)，式(11)表示为

3.3 WPCAS算法设计与复杂性分析

3.3.1 WPCAS算法设计

WPCAS算法主要包括2个部分，分别是进程归类模块和服务时间评估模块。进程归类模块为不同类型的负载设置不同的预期周期，并输出预期周期大小。服务时间评估模块比较SORT队列当前I/O请求的服务时间和预期情况下I/O请求的服务时间，决定是否预期下一个I/O请求。如果预期下一个I/O请求，设置预期标志(anticipated_flag=1)，否则，设置预期标志(anticipated_flag=0)。WPCAS算法的形式化描述如下。

算法1WPCAS调度算法

输入：I/O请求状态信息

输出：预期周期大小

step1统计进程I/O请求的历史状态信息，包括磁道位置和到达时间间隔、预期失败的请求数、预期失败所花费的总时延、预期成功的请求数和预期成功所花费的总时延。

step2计算预期成功率(ps)、预期失败率(pf)和预期成功的平均等待时间(Tas)。

step3根据式(3)和式(4)，计算最佳的预期周期范围，再由式(6)，得到每类进程的最佳预期周期大小。然后，设置并输出每类进程的预期周期大小。

step4计算调度SORT队列当前I/O请求的服务时间和预期情况下I/O请求的服务时间并进行比较。如果，设置预期标志(anticipated_flag=1)，表示预期下一个I/O请求。否则，设置预期标志(anticipated_flag=0)，表示调度SORT队列的当前I/O请求。

step5若FIFO队列有超过截止时间的I/O请求，则将该请求分发到通用块设备层的调度队列，进行处理。否则，转入step6。

step6如果anticipated_flag=0，则将SORT队列的当前I/O请求插入通用块设备层的调度队列，等待磁盘驱动器完成数据传输。否则，根据step3得到预期周期的长度,设置定时器的超时时间，等待下一个I/O请求到达。如果定时器超时，预期失败请求数加1，服务SORT队列的当前I/O请求。否则，预期成功请求数加1，服务预期到的I/O请求。

3.3.2 WPCAS算法复杂性分析

假设进程类别为m，每类进程历史I/O请求数为n,那么WPCAS需要记录mn个I/O请求，即空间复杂度为O(mn)。PC模块的时间复杂度为O(m)，STE模块的时间复杂度为O(mn)。所以WPCAS算法的时间复杂度为O(m+mn)。因此，WPCAS算法是可行的。

4 性能测试

在Linux 2.6.20内核对AS算法进行修改，增加了PC和STE 2个模块。分别对吞吐量，预期成功的平均时延和伪空闲周期[18]进行了测试。为了测量真实的磁盘性能，绕过了Linux页面高速缓存，使用直接I/O测试。主要包含以下几种负载。

1)IOzone生成的顺序负载。

2)IOzone生成的随机负载。

3)Postmark生成的Web服务器负载。

通过测试对比了NOOP、CFQ、Deadline、AS、WPCAS和95%-Heuristic[18]等调度算法的性能。

4.1 测试工具

采用IOzone和Postmark作为负载测试工具。IOzone[20]是一个文件系统的benchmark工具，可以测试不同的操作系统中文件系统和磁盘的读写性能。 Postmark[21]主要用于测试文件系统在邮件系统或电子商务系统中的性能，其特点是：频繁、大量地存取小文件，可生成Web服务器负载、数据库负载和Email负载等。

4.2 性能指标

实验性能评价参数主要有：

1)吞吐量；

2)预期成功的平均等待时延；

3)伪空闲周期的长度。

伪空闲周期长度定义为预期失败的总时延除以总的预期请求数。显然，这个值越小，平均响应时间越小。

4.3 实现方法

实验测试中，在Linux 2.6.20内核block/blkdev.h头文件的io_context结构体加入了链表inv_d。在block/as-iosched.c文件的as_update_iohist记录最近n个请求的到达时间间隔，并存入链表inv_d。在as_antic_update_rq加入了2个计数器as_scount和as_stime，记录预期成功的请求数和预期成功所花费的总时延。在as_antic_timout函数中加入了2个计数器as_fcount和as_ftime，记录预期失败的请求数和预期失败所花费的总时延。然后添加函数as_antic_dertermined和as_class_proccess。as_class_proccess根据进程归类模块为不同负载指定的预期周期。as_antic_determined根据服务时间评估模块决定是否预期下一个请求。

4.4 顺序负载和随机负载测试

使用IOzone生成512 KB大小的文件，测试NOOP、Deadline、CFQ、AS和WPCAS在10、40、80类进程下的吞吐量。以进程类别数等于40为例，顺序负载配置为:#root/iozone–i0–i1–r4096–t40–s100–I–Rresult.xls。其中，–i0表示顺序写、–i1表示顺序读、–r表示测试块大小、–t表示进程类别数、–s表示测试文件大小、–I表示绕过文件系统缓存，直接对磁盘进行读写。–R表示产生excel的输出日志。随机负载配置为：#root/iozone–i2–r4096–t40–I–Rresult.xls。其中，–i2表示随机读写负载。实验中分别对10、40、80类进程下的顺序负载和随机负载测试了50次，对3种情况下的测试结果分别求平均值并进行比较。

4.4.1 顺序读写512 KB文件的吞吐量

图3～图5显示了I/O调度算法在顺序负载下的吞吐量。图3和图4表明，当进程类别较少时，NOOP和Deadline在顺序负载下的吞吐量比其他I/O调度算法都高。图5表明，当进程类别数较多时，由于不同进程的I/O请求持续交错的到达，I/O请求的连续性遭到破坏，所以NOOP和Deadline的吞吐量比其他I/O调度算法低。对于顺序负载，WPCAS的吞吐量比AS提高了10.9%左右。AS算法为每类进程分配固定的预期周期（6 ms），对于顺序请求的负载，AS虽然能够预测到下一个到达的连续请求，但也造成了某些密集I/O(到达时间间隔小于6 ms)长时间的等待。而WPCAS算法不但能够准确的预测下一个连续的请求，而且根据进程特性为每类进程分配不同的预期周期，能够适应负载的动态变化。因此，WPCAS算法的吞吐量比AS高。

图3 进程类别数为10，顺序负载下各种I/O调度算法的吞吐量

图4 进程类别数为40，顺序负载下各种I/O调度算法的吞吐量

图5 进程类别数为80，顺序负载下各种I/O调度算法的吞吐量

4.4.2 随机读写512 KB大小文件的吞吐量

图6～图8显示了I/O调度算法在随机负载下的吞吐量。可以看出，CFQ算法对于随机读写吞吐量高于其他调度算法。这是由于CFQ为每个进程维护一个I/O队列，各个进程发出的I/O请求以轮循的方式处理。因此，CFQ非常适合于随机、零散的I/O请求。由于NOOP算法按照先来先服务进行调度，对于随机负载，会造成磁头的频繁移动，增加寻道时延。因此，NOOP的随机读写性低于AS和WPCAS。在随机负载下，WPCAS比AS吞吐量提高了5%左右。这是由于在随机负载下，每类进程的I/O请求的到达时间间隔差别很大，使采用固态预期周期长度的AS预期失败或等待时间过长。而WPCAS根据负载特性动态改变预期周期的长度，使预期更加准确和高效。

图6 进程类别数为10，随机负载下各种I/O调度算法的吞吐量

图7 进程类别数为40，随机负载下各种I/O调度算法的吞吐量

图8 进程类别数为80，随机负载下各种I/O调度算法的吞吐量

4.5 Postmark生成的Web服务器负载

为了进一步评估WPCAS算法的性能，使用Postmark模拟真实的Web服务器负载，比较了95%-Heuristic、AS和WPCAS的性能。如表1所示，A-T、A-S和A-F分别表示总的预期请求数、预期成功的请求数和预期失败的请求数。A-ST和A-FT分别表示预期成功所花费的总时延和预期失败所花费的总时延。95%-Heuristic、AS和WPCAS的伪空闲周期长度分别为0.238 ms、0.113 ms和0.047 ms。WPCAS的吞吐量比AS和95%-Heuristic分别提高了24%和40%。这是由于访问Web服务器的负载类型是动态变化的。例如，Web服务器上的某一“热点”新闻，可能引起短时间内大量的I/O请求到达，I/O非常密集。在一段时间之后，这些“热点”的新闻逐渐成为“冷门”，可能很长时间才会有I/O请求到达。AS算法对所有的负载采用固态的预期周期(6 ms)，增加了预期失败的次数和预期成功的所花费的总时延。WPCAS针对不同类型的负载动态的调度预期周期的长度，适应了负载的动态变化。因此，WPCAS非常适用于Web服务器负载、网站访问负载等。

表1 Postmark生成的Web服务器负载

5 结束语

针对传统AS调度算法的不足，提出了一种基于负载特性和服务时间评估改进的AS算法(WPCAS)。WPCAS分为进程归类模块(PC)和服务时间评估模块(STE)两部分。PC根据负载特性，动态调整预期周期的长度，从而适应负载动态变化。STE根据I/O请求的服务时间决定是否预期下一个I/O请求，使得预期更加的准确。通过对比实验证明了在吞吐量、预期成功的平均时延和伪空闲周期长度等方面，WPCAS算法优越于95%-Heuristic和AS算法。特别地，WPCAS算法非常适用于Web网络服务器负载。

[1]WORTHINGTON B,GANGER G,PATT Y.Scheduling algorithms for modern disk drives[A].InACM Sigmetrics[C].1994.241-251.

[2] HUANG L,CHIUEH T.Implementation of a Rotation Latency Sensitive Disk Scheduler[R].Technical Report ECSL-TR81,SUNY,Stony Brook,2000.

[3] REDDY A L N,WYLLIE J.Disk scheduling in a multimedia I/O system[A]. Proc First ACM Int’l Conf Multimedia(MULTIMEDIA’93)[C].1993.225-233.

[4]CHANG R I,SHIH W K,CHANG R C.Deadline-modification-scan with maximum scannable-groupsformultimediareal-timedisk scheduling[A].Proceedings of the 19th IEEE Real-Time Systems Symposium[C].1998.40-49.

[5]CHANG H P,CHANG R I,SHIH W K,etal.Reschedulable-group-SCAN scheme for mixed real-time/non-real-time disk scheduling in a multimedia system[J].J Syst Software,2002,59(2):143-152.

[6]CHANG H P,CHANG R I,SHIH W K,et al.GSR:a global seek-optimizing real-time disk-scheduling algorithm,the journal of transactions in firm real-time database systems[J].Systems and Software,2007,80(2):198-215.

[7]KESAVAN M,GAVRILOVSKA A,SCHWAN K.Differential virtual time(DVT):rethinking I/O service differentiation for virtual machines[A].Proc of the 1st ACM Symposium on Cloud Computing,SoCC’10[C].ACM,New York(2010),2010.27-38.

[8] RIZZO L,VALENTE P.Hybrid:achieving deterministic fairness and high throughput in disk scheduling[A].Proc CCCT’04[C].2004.

[9]WACHS M,ABD-EL-MALEK M,THERESKA E,et al.Argon:performance insulation for shared storage servers[A].Proc of the 5th USENIX Conference on File and Storage Technologies(FAST’07)[C].San Jose,CA,USA,2007.61-76.

[10]GULATI A,MERCHANT A,VARMAN P J.Pclock:an arrival curve based approach for QoS guarantees in shared storage systems[J].SIGMETRICS Performance Evaluation Rev,2007,35(1):13-14.

[11]GULATI A,MERCHANT A,UYSAL M,et al.Efficient and Adaptive Proportional Share I/O Scheduling[R].Hewlett-Packard Pdf,2009.

[12]GANG P,CKER CHIUEH T.Availability and fairness support for storage qos guarantee in distributed computing systems[A]. ICDCS’08.The28th International Conference on 2008[C].2008.589-596.

[13]VALENTE P,CHECCONI F.High throughput disk scheduling with fair bandwidth distribution[J].IEEE Transactions on Computers,2010,59(9):1172-1186.

[14]http://mirror.linux.org.au/pub/linux.conf.au/2007/video/talks/123.pdf[EB/OL].2010.

[15]LOVE R.Linux Kernel Development[M].Developers Library Sams Publishing/Novel,2005.

[16]STOUPA K,VAKALIA.QoS-oriented negotiation in disk subsystems[J].Data and Knowledge Engineering Journal,2006,58(2):107-128.

[17]TANENBAUM A S.Modern Operating Systems[M].Second Ed Prentice Hall,Upper Saddle River,NJ,2001.

[18]LYER S,DRUSCHEL P.Anticipatory scheduling:a disk scheduling framework to overcome deceptive idleness in synchronous I/O[A].Proceedings of the 18th ACM Symposium on Operating Systems Principles[C].New York,NY,2001.

[19]RUEMMLER C,WILKES J.Anintroduction todiskdrive modeling[J].IEEE Comput,1994,27(3):16-28.

[20]IOzone file system benchmark[EB/OL].http://www.iozone.org.

[21]KATCHER J.Postmark:a New File System Benchmark[R].Technical Report TR 3022,NetworkAppliance,1997.