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

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

Abstract

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.

Key words: storage system, I/O schedule layer, AS, WPCAS, service time

Jin-zhong CHEN,Nian-min YAO,Shao-bin CAI,Mei-ling SUN. Improved anticipatory scheduling algorithm based on workload characteristic and service time evaluation[J]. Journal on Communications, 2015, 36(1): 159-166.

Figures/Tables 9

References 21

[1]	WORTHINGTON B , GANGER G , PATT Y . Scheduling algorithms for modern disk drives[A]. In ACM 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-groups for multimedia real-time disk 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 , 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.
[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]. New York(2010), 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.The 28th 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]	[EB/OL]. 2010.
[15]	LOVE R . Linux Kernel Development[M]. Developers Library Sams Publishing/Novel, 2005.
[16]	STOUPA K , VAKALI A . 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 . An introduction to disk drive modeling[J]. IEEE Comput, 1994,27(3): 16-28.
[20]	IOzone file system benchmark[EB/OL]. .
[21]	KATCHER J . Postmark:a New File System Benchmark[R]. Technical Report TR 3022,Network Appliance, 1997.

Metrics

Recommended 0

No Suggested Reading articles found!

调度算法	95%-Heuristic	AS	WPCAS
总预期数	384630	371464	361268
预期成功数	362706	364590	356694
预期失败数	21924	6874	4574
成功时延	335140 ms	214014 ms	140768 ms
失败时延	86536 ms	41244 ms	16250 ms
伪空闲周期长度	0.238 ms	0.113 ms	0.047 ms
吞吐量	27415 kbit/s	34231 kbit/s	45238 kbit/s

Improved anticipatory scheduling algorithm based on workload characteristic and service time evaluation

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 21

Related Articles 15

Metrics

Recommended 0

[1]	Li WANG, Aiguo FEI, Ping ZHANG, Lianming XU. Research on new frameworks and key technologies for intelligent emergency command communication networks [J]. Journal on Communications, 2023, 44(6): 1-11.
[2]	Hui JIANG, Tianliu HE, Min LIU, Sheng SUN, Yuwei WANG. High-performance federated continual learning algorithm for heterogeneous streaming data [J]. Journal on Communications, 2023, 44(5): 123-136.
[3]	Zhen ZHENG, Yingjian YAN, Juesong CAI, Yanjiang LIU. Non-specific TVLA method based on two-sample KS test [J]. Journal on Communications, 2023, 44(5): 137-147.
[4]	Rui GUO, Yang LIU. Simplified sequence repetition nodes-based fast successive cancellation decoding algorithm for polar code [J]. Journal on Communications, 2023, 44(5): 158-168.
[5]	Xiaoyu CHEN, Chengrui WANG, Fan LIU. New construction method of periodic quasi-complementary sequence set [J]. Journal on Communications, 2023, 44(5): 206-212.
[6]	Tao FENG, Liqiu CHEN, Junli FANG, Jianming SHI. Blockchain data sharing scheme based on localized difference privacy and attribute-based searchable encryption [J]. Journal on Communications, 2023, 44(5): 224-233.
[7]	Weifeng LU, Ning LI, Jia XU, Lijie XU, Jian XU. Joint scheduling algorithm for correlative tasks in multi-access edge computing [J]. Journal on Communications, 2023, 44(4): 87-98.
[8]	Jinyin CHEN, Haiyang XIONG, Haonan MA, Yayu ZHENG. CLB-Defense: based on contrastive learning defense for graph neural network against backdoor attack [J]. Journal on Communications, 2023, 44(4): 154-166.
[9]	Yifeng WANG, Yuanbo GUO, Qingli CHEN, Chen FANG, Renhao LIN, Yongliang ZHOU, Jiali MA. Method based on contrastive incremental learning for fine-grained malicious traffic classification [J]. Journal on Communications, 2023, 44(3): 1-11.
[10]	Yun LIN, Huaitao XU, Sen WANG, Sicheng ZHANG, Long ZHUANG. Objective assessment of communication speech interference effect based on feature fusion [J]. Journal on Communications, 2023, 44(3): 105-116.
[11]	Junfeng TIAN, Qianyu YANG, Xiao Jitian. Distributed audit causal consistency model based on biased stability [J]. Journal on Communications, 2023, 44(3): 164-177.
[12]	Xuejiao LIU, Tiancong CAO, Yingjie XIA. Research on efficient and secure cross-domain data sharing of IoV under blockchain architecture [J]. Journal on Communications, 2023, 44(3): 186-197.
[13]	Wei FAN, Cheng PENG, Dali ZHU, Yuqing WANG. Research on intrusion response strategy based on static Bayesian game in mobile edge computing network [J]. Journal on Communications, 2023, 44(2): 70-81.
[14]	Weigang HUO, Rui LIANG, Yonghua LI. Anomaly detection model for multivariate time series based on stochastic Transformer [J]. Journal on Communications, 2023, 44(2): 94-103.
[15]	Guojun LI, Xu HOU, Changrong YE, Yiping LUO. Wide area cooperative resource allocation algorithm for shortwave communication access network [J]. Journal on Communications, 2023, 44(2): 112-121.