Simulation Study of Task Scheduling and Resequencing in a Multiprocessing System

Abstract

The performance of parallel programs such as fork-join jobs is significantly affected by the choice of policy used to schedule tasks.

In this paper we present the results of a simulation study comparing three basic policies that schedule independent tasks in conjunction with resequencing of jobs. A closed queuing network model is considered; the CPU consists of homogeneous and independent processors, each serving its own queue.

The simulation results reveal that the performance of the three policies is affected by the resequencing delay. It is shown that over a wide range of system parameters the first-come-first-served policy exhibits better performance than the policy that gives priority to tasks of a job having the smallest number of tasks. It is also shown that the policy that gives priority to the smallest task performs best when there are large variations in the task service times.

Keywords

Discrete simulation systems modeling performance scheduling queuing

Get full access to this article

View all access options for this article.

References

Iliadis, I. and Lien, Y.C. 1988. "Resequencing delay distribution for a queuing system with two heterogeneous servers under threshold scheduling." Data Communication Systems and Their Performance. Amsterdam: Elsevier Science Publishers B.V., IFIP, pp. 359-373.

Takine, F. and Hasegawa, T. 1990. "Resequencing delay in preemptive priority M/M/2 queues." Performance '90. Amsterdam: Elsevier Science Publishers B.V., pp. 109-121.

Karatza, H.D. 1995. "Simulation study of multitasking and resequencing in a homogeneous distributed system." Proceedings of the Eurosim Congress '95. Vienna, Austria, September, Amsterdam: Elsevier Publishers P.V., 541-546

Dandamudi, S. 1991. "A comparison of task scheduling strategies for multiprocessor systems." Proceedings of the IEEE Symposium on Parallel and Distributed Processing. Dallas, TX, December, pp. 423-426.

Dandamudi, S. 1994."Performance implications of task routing and task scheduling strategies for multiprocessor systems ." Proceedings of the IEEE-Euromicro Conference on Massively Parallel Computing Systems. Ischia, Italy, May, pp. 348-353.

Towsley, D. , Romel, C.G. , and Stankovic , J.A. 1990. " Analysis of fork-join program response times on multiprocessors." IEEE Trans. Parallel and Distributed Systems vol. 1, no. 3, July, pp. 286-303.

Kumar, A. and Shorey, R. 1993. "Performance analysis and scheduling of stochastic fork-join jobs in a multicomputer system." IEEE Trans. Parallel and Distributed Systems vol. 4, no. 10, pp. 1147-1162.

Majumdar, S. , Eager D. , and Bunt, R.B. 1988. "Scheduling in multiprogrammed parallel systems." Proceedings of the 1988 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems. May, pp. 104-113.

Leutenegger, S.T. and Vernon, M.K. 1990. "The performance of multiprogrammed multiprocessor scheduling policies." Proceedings of the 1990 ACM Sigmetrics Conference. May, Performance Evaluation Review 18, pp. 226-236.

10.

Sevcik, K. 1994. "Application scheduling and processor allocation in multiprogrammed parallel processing systems." Performance Evaluation vol. 19, pp. 107-140.

11.

Law, A. and Kelton, D. 1991. Simulation Modeling and Analysis. New York: McGraw-Hill.