A two-class parallel queue with pure space sharing among rigid jobs and general service times

ABSTRACT

We analyze a parallel system model with one queue, two servers and rigid jobs. Each job arriving to the queue may require either one or two servers. Jobs that require one server (type-1 jobs) have exponentially distributed service requirements while jobs requiring two servers (type-2 jobs) have general service time distribution. The FCFS scheduling discipline is assumed and all jobs are served according to pure space sharing. By applying the supplementary variable method we derive closed-form expressions, exact as well as approximate, for the steady-state mean queue length and utilization of the servers. In addition, we investigate the utilization as well as the throughput of the system as the load reaches its maximal value inside the stability region. Numerical results are presented that give insight into the impact of each parameter on system performance.

REFERENCES

• 1: Kento Aida , Hironori Kasahara , Seinosuke Narita, Job Scheduling Scheme for Pure Space Sharing Among Rigid Jobs, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.98-121, March 30, 1998
• 2: D. Auckly. Solving the quartic with a pencil, 2003, http://arxiv.org/pdf/math.HO/0310449 (last visited 31/07/2006).
• 3: Gunter Bolch , Stefan Greiner , Hermann de Meer , Kishor S. Trivedi, Queueing networks and Markov chains: modeling and performance evaluation with computer science applications, Wiley-Interscience, New York, NY, 1998
• 4: O. Boxma, G. Koole, and Z. Liu. Queueing-theoretic solution methods for models of parallel and distributed systems. In O. Boxma and G. Koole, editors, Performance Evaluation of Parallel and Distributed Systems, number 105 and 106 in CWI Tracts, pages 1--21. CWI, Amsterdam, 1994. Proceedings of the Torino Workshop.
• 5: R. M. Bryant, Maximum Processing Rates of Memory Bound Systems, Journal of the ACM (JACM), v.29 n.2, p.461-477, April 1982 [doi>10.1145/322307.322319]
• 6: D. Filippopoulos and H. Karatza. A dynamic programming model of two heterogeneous clusters with co-allocation of jobs. Int. J. Simulation: Systems, Science & Technology, 6:4--14, 2005.
• 7: S. Neumark. Solution of cubic & quartic equations. Pergamon Press, Oxford, 1965.
• 8: Vittoria de Nitto Personé , Vincenzo Grassi, An analytical model for a parallel fault-tolerant computing system, Performance Evaluation, v.38 n.3-4, p.201-218, Dec. 1999 [doi>10.1016/S0166-5316(99)00047-4]
• 9: S. Ross. Stochastic processes. John Wiley & Sons, New York, 1996.
• 10: Mark S. Squillante , Fang Wang , Marios Papaefthymiou, Stochastic analysis of gang scheduling in parallel and distributed systems, Performance Evaluation, 27-28, p.273-296, Oct. 1996 [doi>10.1016/0166-5316(96)00042-9]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Performance, Theory

Keywords:
discriminant, monotonicity, parallel system, partial derivative, real roots, stability, supplementary variable