A Multiprocessor System with Non-Preemptive Earliest-Deadline-First Scheduling Policy: A Performability Study

Document Type : Research Paper


1 Department of Electrical and Computer Engineering, University of Tehran,Tehran, Iran

2 Department of Computer Engineering, Sharif University of Technology, Tehran,Iran


This paper introduces an analytical method for approximating the performability of a firm realtime system modeled by a multi-server queue. The service discipline in the queue is earliestdeadline- first (EDF), which is an optimal scheduling algorithm. Real-time jobs with exponentially distributed relative deadlines arrive according to a Poisson process. All jobs have deadlines until the end of service and are served non-preemptively. An important performance measure to calculate is the loss probability. The performance of the system is approximated by a Markovian model in the long run. A key parameter, namely, the loss rate when there are n jobs in the system is used in the model, which is estimated by partitioning the system into two subsystems. The resulting model can then be solved analytically using standard Markovian solution techniques. The number of servers in the system may change due to failure or repair. The performability of the system is evaluated in the presence of such structural changes. The latter measure is approximated by a Markov reward model, considering the loss probability as the reward rate. Comparing numerical and simulation results, we find that the existing errors are relatively small.


Main Subjects

[1] AlEnavy T.A., Aydin H. (2005), Energy-constrained scheduling for weakly-hard real-time systems;
Proceedings of the 26th IEEE Real-Time Systems Symposium (RTSS’05); 376-385.
[2] Baccelli F., Boyer P., Hebuterne G. (1984),Single-server queues with impatient customers; Advanced
Applied Probability 16; 887-905.
[3] Barrer D.Y. (1957), Queueing with impatient customers and ordered service; Operational Research
5; 650- 656.
[4] Bernat G., Burns A., Llamosi A. (2001), Weakly hard real-time systems; IEEE Transactions on
Computers 50 (4); 308-321.
[5] Brandt A., Brandt M. (1999), On the M(n)/M(n)/s queue with impatient calls; Performance
Evaluation 35; 1-18.
[6] Brandt A., Brandt M. (2002), Asymptotic results and a Markovian approximation for the
M(n)/M(n)/s+GI system; Queueing Systems 41; 73-94.
[7] Cohen J.W. (1968), Single server queue with uniformly bounded virtual waiting time; Journal of
Applied Probability 5; 93-122.
[8] Daley D.J. (1965), General customer impatience in queue GI/G/1; Journal of Applied Probability 2;
[9] Deavours D.D., Clark G., Courtney T., Daly D., Derisavi S., Doyle J.M., Sanders W.H., Webster
P.G. (2002), The Mobius framework and its implementation; IEEE Transactions on Software
Engineering 28(10); 956-969.
[10] Dolev S., Keizelman A. (1999), Non-preemptive real-time scheduling of multimedia tasks; Real-
Time Systems 17(1); 23–39.
[11] Doytchinov B., Lehoczky J., Shreve S. (2001), Real-time queues in heavy traffic with earliestdeadline-
first queue discipline; Annals of Applied Probability 11; 332-379.
[12] EN 50170 (1996), General purpose field communication system; CENELEC, In European Standard.
[13] George L., Muhlethaler P., Rivierre N. (1995), Optimality and non-preemptive real-time scheduling
revisited; Rapport de Recherche RR-2516, INRIA, Le Chesnay Cedex, France.
[14] George L., Rivierre N., Spuri M. (1996), Preemptive and non-preemptive real-time uni-processor
scheduling; Rapport de Recherche RR-2966, INRIA, Le Chesnay Cedex, France.
[15] Hong J., Tan X., Towsley D. (1989), A performance analysis of minimum laxity and earliest
deadline scheduling in a real-time system; IEEE Transactions on Computers 38(12); 1736-1744.
[16] Hsueh M.C., Iyer R. K., Trivedi K.S. (1988), Performability modeling based on real data: A case
study; IEEE Transactions on Computers 37(4); 478-484.
[17] Kargahi M., Movaghar A. (2005), Non-preemptive earliest-deadline-first scheduling policy: A
performance study; Proceedings of IEEE International Symposium on Modeling, Analysis, and
Simulation of Computer and Telecommunication Systems (MASCOTS’05); 201-210
[18] Kargahi M., Movaghar A. (2006), A method for performance analysis of earliest-deadline-first
scheduling policy; Journal of Supercomputing 37(2); 197-222.
[19] Kruk L., Lehoczky J., Shreve S., Yeung S.N. (2004), Earliest-deadline-first service in heavy-traffic
acyclic networks; Annals of Applied Probability 14(3); 1306-1352.
[20] Lehoczky J.P. (1996), Real-time queueing theory; Proceedings of IEEE Real-Time Systems
Symposium; 186-195.
[21] Lehoczky J.P. (1997), Using real-time queueing theory to control lateness in real-time systems;
Performance Evaluation Review 25(1); 158-168.
[22] Liu C.L., Layland J.W. (1973). Scheduling algorithms for multiprogramming in a hard real-time
environment; Journal of Associative Computational Machinery 20; 46-61.
[23] Livani M.A., Kaiser J. (1998), EDF consensus on CAN bus access for dynamic real-time
applications; Proceedings of IEEE Workshop on Parallel and Distributed Computing Systems in
conjunction with 12th International Parallel Processing Symposium / 9th Symposium on Parallel and
Distributed Processing (IPPS/SPDP'98); 1088-1097.
[24] Meyer J.F. (1982), Closed-form solutions of performability; IEEE Transactions on Computers C-
31(7); 648-657.
[25] Meyer J.F. (1992), Performability: A retrospective and some pointers to the future; Performance
Evaluation 14(3-4); 139-156.
[26] Movaghar A. (1998), On queueing with customer impatience until the beginning of service;
Queueing Systems 29; 337-350.
[27] Movaghar A. (2006), On queueing with customer impatience until the end of service; Stochastic
Models 22; 149-173.
[28] Palm C. (1953), Methods for judging the annoyance caused by congestion; Tele 2; 1-20.
[29] Panwar S.S., Towsley D., Wolf J.K. (1988), Optimal scheduling policies for a class of queues with
customer deadlines to the beginning of service; Journal of Associative Computational Machinery
35(4); 832-844.
[30] Qiu Q., Wu Q., Pedram M. (2001), Dynamic power management in a mobile multimedia system
with guaranteed quality-of-service; Proceedings of the 38th Conference on Design Automation
(DAC’01); 834-839.
[31] Raghunathan V., Schurgers C., Park S., Srivastava M. B. (2002), Energy aware wireless microsensor
networks; IEEE Signal Processing Magazine 19 (2); 40-50.
[32] Reibman A.R., Trivedi K.S. (1988), Numerical transient analysis of Markov dependability models;
Computers and Operations Research 15; 19-36.
[33] Smith R.M., Trivedi K.S., Ramesh A.V. (1988), Performability analysis: Measures, an algorithm,
and a case study; IEEE Transactions on Computers 37(4); 406-417.
[34] Takacs L. (1974), A single-server queue with limited virtual waiting time; Journal of Applied
Probability 11; 612-617.
[35] Towsley D., Panwar S.S. (1990), On the optimality of minimum laxity and earliest deadline
scheduling for real-time multiprocessors; Proceedings of IEEE EUROMICRO-90 Workshop on Real-
Time; 17-24.
[36] Towsley D., Panwar S.S. (1992), Optimality of the stochastic earliest deadline policy for the G/M/c
queue serving customers with deadlines; Second ORSA Telecommunications Conference.
[37] Trivedi K.S., Muppala J.K., Woolet S.P., Haverkort B.R. (1992), Composite performance and
dependability modeling; Performance Evaluation 14; 197-215.
[38] Zhao W., Stankovic J.A. (1989), Performance analysis of FCFS and improved FCFS scheduling
algorithms for dynamic real-time computer systems; Proceedings of IEEE Real-Time Systems
Symposium; 156-165.
[39] CAN-CIA, ″CAN specification 2.0 Part B″,
http://www.cancia.org/downloads/ciaspecificatios, 1992.
[40] Sanders W.H., ″Mobius user manual″, http://www.mobius.uiuc.edu, 2005