A Non-Preemptive Two-Class M/M/1 System with Prioritized Real-Time Jobs under Earliest-Deadline-First Policy

Document Type : Research Paper


This paper introduces an analytical method for approximating the performance of a two-class priority M/M/1 system. The system is fully non-preemptive. More specifically, the prioritized class-1 jobs are real-time and served with the non-preemptive earliest-deadline-first (EDF) policy, but despite their priority cannot preempt any non real-time class-2 job. The waiting class-2 jobs can only be served from the time instant that no class-1 job is in the system. The service discipline of the class-2 jobs is FCFS. The required mean service times may depend on the class of the jobs. The real-time jobs have exponentially distributed relative deadlines until the end of service. The system is approximated by a Markovian model in the long run, which can be solved numerically using standard Markovian solution techniques. The performance measures of the system are the loss probability of the class-1 jobs and the mean sojourn (waiting) time of the class-2 jobs. Comparing the numerical and simulation results, we find that the existing errors are relatively small.


Main Subjects

[1] Baccelli F., Boyer P., Hebuterne G. (1984), Single-server queues with impatient customers; Advanced
Applied Probability 16; 887-905.
[2] Barrer D.Y. (1957), Queueing with impatient customers and ordered service; Operational Research5;
[3] Bernat G., Burns A., Llamosi, A. (2001), Weakly hard real-time systems; IEEE Transactions on
Computers 50(4); 308-321.
[4] Boxma O.J., Wall P.R. (1994), Multiserver queues with impatient customers; Proceedings of the 14th
International Teletraffic Congress, 14, Antibes, France, pp 743-756.
[5] Brandt A. Brandt M. (1999a), On the M(n)/M(n)/s Queue with impatient calls; Performance
Evaluation 35; 1-18.
[6] Brandt A. Brandt M. (1999b), On a two-queue priority system with impatience and its application to a
call center; Methodology and Computing in Applied Probability 1; 191-210.
[7] 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.
[8] Brandt A. Brandt M. (2004), On the two-class M/M/1 system under preemptive resume and impatience
of the prioritized customers; Queueing Systems 47(1-2), 147-168.
[9] CAN-CIA, CAN specification 2.0 Part B, http://www.cancia.org/downloads/ ciaspecifications, 1992.
[10] Choi B.D., Kim B., Chung J. (2001), M/M/1 Queue with impatient customers of higher priority;
Queueing Systems 38; 49-66.
[11] Daley D.J. (1965), General customer impatience in queue GI/G/1; Journal of Applied Probability 2;
[12] Dolev S. Keizelman A. (1999), Non-preemptive real-time scheduling of multimedia tasks; Real-Time
Systems 17(1); 23–39.
[13] 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.
[14] EN 50170, General purpose field communication system, In European Standard, CENELEC, 1996.
[15] 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.
[16] 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.
[17] 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.
[18] Jaiswal N. (1968), Priority queues; Academic Press, New York.
[19] Kargahi M., Movaghar A. (2004), A method for performance analysis of earliest-deadline-first
scheduling policy; Proceedings of the 2004 IEEE International Conference on Dependable Systems
and Networks, Florence, Italy, pp 826-834.
[20] 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, Georgia, Atlanta, USA, pp 201-210.
[21] Kargahi M., Movaghar A. (2006), A method for performance analysis of earliest-deadline-first
scheduling policy; Journal of Supercomputing 37(2); 197-222.
[22] Kargahi M., Movaghar A. (2007), A multiprocessor system with non-preemptive earliest deadline first
scheduling policy: A performability study; Journal of Industrial and Systems Engineering 1(1); 37-55.
[23] Kruk L., Lehoczky J., Shreve S., Yeung S.N. (2003), Multiple-input heavy-traffic real-time queues;
Annals of Applied Probability 13(1); 54-99.
[24] Kruk L., Lehoczky J.P., Shreve S., Yeung S.N. (2004), Earliest-deadline-first service in heavy-traffic
acyclic networks; Annals of Applied Probability 14(3); 1306-1352.
[25] Lehoczky J.P. (1996a), Real-time queueing theory; Proceedings of the 17th IEEE Real-Time Systems
Symposium, Washington, D.C., USA, pp 186-195.
[26] Lehoczky J.P. (1996b), Using real-time queueing theory to control lateness in real-time systems;
Performance Evaluation Review 25(1); 158-168.
[27] Leulseged A., Nissanke N. (2004), Probabilistic analysis of multi-processor scheduling of tasks with
uncertain parameters;, Proceedings of the 9th International Conference on Real-Time and Embedded
Computing Systems and Applications, pp 103-122. (LNCS 2968)
[28] Liu C.L., Layland J.W. (1973), Scheduling algorithms for multiprogramming in a hard real-time
environment; Journal of the ACM 20(1); 46-61.
[29] 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, pp 1088-1097.
[30] May M., Bolot J., Jean-Marie A., Diot C. (1999), Simple performance models of differentiated services
schemes for the Internet; Proceedings of the 18th Annual Joint Conference of the IEEE Computer and
Communications Societies, INFOCOM’99, New York, NY, pp 1385-1394 (vol. 3).
[31] Miller R.G. (1960), Priority queues; Annals of Mathematical Statistics 31; 86-103.
[32] Movaghar A. (1998), On queueing with customer impatience until the beginning of service; Queueing
Systems 29; 337-350.
[33] Movaghar A. (2006), On queueing with customer impatience until the end of service; Stochastic
Models 22; 149-173.
[34] Nissanke N., Leulseged A., Chillara S. (2002), Probabilistic performance analysis in multiprocessor
scheduling; Journal of Computing and Control Engineering 13(4); 171-179.
[35] Palm C. (1953), Methods for judging the annoyance caused by congestion; Tele 2; 1-20.
[36] 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, pp 17-
[37] Towsley D., Panwar S.S. (1992), Optimality of the stochastic earliest deadline policy for the G/M/c
queue serving customers with deadlines; Proceedings of the Second ORSA Telecommunications
[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, California, USA, pp 156-165.