Two-stage scheduling algorithm based on priority table for clusters with inaccurate system parameters

Abstract

A new two-stage soft real-time scheduling algorithm based on priority table was proposed for task dispatch and selection in cluster systems with inaccurate parameters. The inaccurate characteristics of the system were modeled through probability analysis. By taking into account the multiple important system parameters, including task deadline, priority, session integrity and memory access locality, the algorithm is expected to achieve high quality of service. Lots of simulation results collected under different load conditions demonstrate that the algorithm can not only effectively overcome the inaccuracy of the system state, but also optimize the task rejected ratio, value realized ratio, differentiated service guaranteed ratio, and session integrity ensured ratio with the average improvement of 3.5%, 5.8%, 7.6% and 5.5%, respectively. Compared with many existing schemes that cannot deal with the inaccurate parameters of the system, the proposed scheme can achieve the best system performance by carefully adjusting scheduling probability. The algorithm is expected to be promising in systems with soft real-time scheduling requirement such as E-commerce applications.

Keywords

task scheduling / priority table / inaccurate information / quality of service(QoS)

References

[1] CardelliniV, ColajanniM, YuP S. The state of the art in locally distributed web-server systems[J]. ACM Computing Surveys, 2002, 34(2): 1-49

[2] KatzE, ButlerM, McGrathR. A scalable web server: the NCSA prototype[J]. Computer Networks and ISDN Systems, 1994, 27: 155-164

[3] ShangZhi-guang, LinChuang, XiaoRen-yi, et al.. Web quality of service: a survey[J]. Chinese Journal of Computers, 2004, 27(2): 145-156(in Chinese)

[4] Di-shuo, Zhengwei-min, WangDing-xing, et al.. Research on request dispatching algorithm for web server clusters[J]. Journal of Software, 1999, 10(7): 713-718(in Chinese)

[5] ZhuH, SmithB, YangT. Scheduling optimization for resource-intensive web requests on server clusters [C]. ACM Symposium on Parallel Algorithms and Architectures, 1999, Saint-Malo, ACM Press: 13-22

[6] HuanJin-gui, ChenJian-er, ChenSong-qiao. Parallel-job scheduling on cluster computing systems [J]. Chinese Journal of Computers, 2004, 27(6): 765-771(in Chinese)

[7] CherkasovaL, PhaalP. Session based admission control: a mechanism for peak load management of commercial web sites[J]. IEEE Journal Transactions on Computers, 2002, 51(6): 721-728

[8] JensenE D, LockeC D, TodudaH. A time-driven scheduling model for real-time operating systems[C]. Proceeding of the 6th IEEE Real-time Systems Symp, 1985, San Diego, IEEE Computer Society Press: 112-122

[9] WangYong-yan, WangQiang, WangHong-an, et al.. A real-time scheduling algorithm based on priority table and its implementation[J]. Journal of Software, 2004, 15(3): 360-370(in Chinese)

[10] CrovellaL, BestavrosA. Self-similarity in world wide web traffic: evidence and possible causes[J]. IEEE/ACM Transactions on Networking, 1997, 5(6): 835-846

[11] ButtazzoG, SpuriM, SensiniF. Deadline scheduling in overload conditions[C]. Proc of the 19th IEEE Real-time System Symp, 1995, Pisa, IEEE Computer Society Press: 90-99