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

陈金志; 姚念民; 蔡绍滨; 孙美玲

doi:10.11959/j.issn.1000-436x.2015018

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 基于负载特性和服务时间评估改进的AS调度算法
- Improved anticipatory scheduling algorithm based on workload characteristic and service time evaluation
- 通信学报 2015年36卷第1期页码：159-166
- 作者机构：
  
  哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨 150000
- 作者简介：
  
  [ "陈金忠（1986-），男，安徽巢湖人，哈尔滨工程大学博士生，主要研究方向为Linux存储系统、I/O调度算法和固态硬盘。" ]
  [ "姚念民（1974-），男，黑龙江大庆人，博士，哈尔滨工程大学教授、博士生导师，主要研究方向为网络存储、信息安全、无线传感器网络以及高可信计算。" ]
  [ "蔡绍滨（1973-），男，黑龙江哈尔滨人，博士，哈尔滨工程大学教授、博士生导师，主要研究方向为无线传感器网络、水声传感器网络。" ]
  [ "孙美玲（1985-），女，黑龙江五常人，哈尔滨工程大学硕士生，主要研究方向为信号与信息处理、语音识别。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61103209);国家自然科学基金资助项目(61170227);浙江省自然科学基金资助项目(LZ12F02005);浙江省教育厅科学基金资助项目(Y201222977)
- DOI：10.11959/j.issn.1000-436x.2015018
  中图分类号： TP333.35
- 网络出版日期：2015-01，
  
  纸质出版日期：2015-01-25
- 稿件说明：
移动端阅览
陈金志, 姚念民, 蔡绍滨, 等. 基于负载特性和服务时间评估改进的AS调度算法[J]. 通信学报, 2015,36(1):159-166.

Jin-zhong CHEN, Nian-min YAO, Shao-bin CAI, et al. Improved anticipatory scheduling algorithm based on workload characteristic and service time evaluation[J]. Journal on communications, 2015, 36(1): 159-166.
陈金志, 姚念民, 蔡绍滨, 等. 基于负载特性和服务时间评估改进的AS调度算法[J]. 通信学报, 2015,36(1):159-166. DOI： 10.11959/j.issn.1000-436x.2015018.

Jin-zhong CHEN, Nian-min YAO, Shao-bin CAI, et al. Improved anticipatory scheduling algorithm based on workload characteristic and service time evaluation[J]. Journal on communications, 2015, 36(1): 159-166. DOI： 10.11959/j.issn.1000-436x.2015018.

摘要

Linux I/O调度层的预期调度算法AS(anticipatory scheduling)对所有的负载分配相同的预期周期，如果等待的I/O请求没有及时到达，将会带来额外的时延。针对AS算法的不足，提出了一种基于负载特性和服务时间评估改进的AS算法(WPCAS

workload characteristic and service time evluation AS)。WPCAS分为进程归类模块(PC)和服务时间评估模块(STE)两部分。PC模块根据负载特性为每类进程指定不同的预期周期。STE模块根据服务时间决定是否预期下一个请求。通过对比实验表明，WPCAS 在吞吐量、预期成功平均等待时延和伪空闲周期方面都优越于95%-Heuristic和AS算法。

Abstract

Anticipatory scheduling (AS) of Linux I/O schedule layer assigns fixed anticipation period length to each process.It will introduce extra delay if I/O request does not arrive in time.The improved anticipatory scheduling (WPCAS) algorithm is proposed which is based on workload characteristic and service time.WPCAS includes process classifier(PC) module and request service time evaluation (STE) module.PC module assigns different anticipation period lengths in terms of workload characteristic.STE module decides whether to anticipate the coming request according to service time.Experimental results show that WPCAS algorithm is superior to 95%-Heuristic and AS in terms of throughput

average waiting time of anticipation success and deceptive idleness.

关键词

Keywords

references

WORTHINGTON B , GANGER G , PATT Y . Scheduling algorithms for modern disk drives [A ] . In ACM Sigmetrics [C ] . 1994 . 241 - 251 .

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

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 .

CHANG R I , SHIH W K , CHANG R C . Deadline-modification-scan with maximum scannable-groups for multimedia real-time disk scheduling [A ] . Proceedings of the 19th IEEE Real-Time Systems Symposium [C ] . 1998 . 40 - 49 .

CHANG H P , CHANG R I , SHIH W K , et al . 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 .

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 .

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 .

RIZZO L , VALENTE P . Hybrid:achieving deterministic fairness and high throughput in disk scheduling [A ] . Proc CCCT '04 [C ] . New York (2010), 2004 .

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 .

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 .

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

GANG P , CKER CHIUEH T . Availability and fairness support for storage qos guarantee in distributed computing systems [A ] . ICDCS'08.The 28th International Conference on 2008 [C ] . 2008 . 589 - 596 .

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

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

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

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

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

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 .

RUEMMLER C , WILKES J . An introduction to disk drive modeling [J ] . IEEE Comput , 1994 , 27 ( 3 ): 16 - 28 .

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

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

浏览量

678

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据