A Residual Time Based Scheduling: Performance Modeling in M/G/C Queueing Applications

ABSTRACT

It is well known, in queueing theory, that the system performance is greatly influenced by scheduling policy. No universal optimum scheduling strategy exists in systems where individual customer service demands are not known a priori. However, if the distribution of job times is known, then the residual time (expected time remaining for a job), based on the service it has already received, can be calculated. Our particular research contribution is in exploring the use of this function to enhance system performance by increasing the probability that a job will meet its deadline. In a detailed discrete event simulation, we have tested many different distributions with a wide range of C2 and shapes, as well as for single and dual processor system. Results of four distributions are reported here. We compare with RR and FCFS, and find that in all distributions studied our algorithm performs best. In the study of the use of two slow servers versus one fast server, we have discovered that they provide comparable performance, and in a few cases the double server system does better.

It is well known, in queueing theory, that the system performance is greatly influenced by scheduling policy. No universal optimum scheduling strategy exists in systems where individual customer service demands are not known a priori. However, if the distribution of job times is known, then the residual time (expected time remaining for a job), based on the service it has already received, can be calculated. Our particular research contribution is in exploring the use of this function to enhance system performance by increasing the probability that a job will meet its deadline. In a detailed discrete event simulation, we have tested many different distributions with a wide range of C2 and shapes, as well as for single and dual processor system. Results of four distributions are reported here. We compare with RR and FCFS, and find that in all distributions studied our algorithm performs best. In the study of the use of two slow servers versus one fast server, we have discovered that they provide comparable performance, and in a few cases the double server system does better.

KEYWORDS

Simulation, Residual Time Scheduling, Coefficient of Variation, M/G/C Queue, Processor Sharing

Simulation, Residual Time Scheduling, Coefficient of Variation, M/G/C Queue, Processor Sharing

Cite this paper

nullTasneem, S. , Lipsky, L. , Ammar, R. and Sholl, H. (2010) A Residual Time Based Scheduling: Performance Modeling in M/G/C Queueing Applications.*Journal of Software Engineering and Applications*, **3**, 746-755. doi: 10.4236/jsea.2010.38086.

nullTasneem, S. , Lipsky, L. , Ammar, R. and Sholl, H. (2010) A Residual Time Based Scheduling: Performance Modeling in M/G/C Queueing Applications.

References

[1] D. G. Feitelson and B. Nitzberg, “Job Characteristics of a Production Parallel Scientific Workload on the NASA Ames iPSC/860,” In: D. G. Feitelson and L. Rudolph, Eds., Job Scheduling Strategies for Parallel Processing, IPPS’95 Workshop, Santa Barbara, Lecture Notes in Computer Science, Springer, Vol. 949, 1995, pp. 337- 360.

[2] S.-H. Chiang, R. K. Mansharamani and M. K. Vernon, “Use of Application Characteristics and Limited Preemption for Run-To-Completion Parallel Processor Scheduling Policies,” Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, Nashville, 1994, pp. 33-44.

[3] R. A. Idris, U.-K. Guillaume and W. E. Biersack, “Analysis of LAS Scheduling for Job Size Distributions with High Variance,” Proceedings of ACM SIGMETRICS, San Diego, 10-12 June 2003, pp. 218-228.

[4] F. Baskett, K. M. Chandy, R. Muntz and F. G. Palacious, “Open, Close and Mixed Networks of Queues with Different Classes of Customers,” Journal of the ACM, Vol. 22, No. 2, 1975, pp. 248-260.

[5] L. Lipsky, “Queueing Theory: A linear Algebraic Approach (LAQT),” 2nd Edition, Springer Verlag, New York, 2008.

[6] T. L. Casavant and J. G. Kuhl, “A Taxonomy of Scheduling in General Purpose Distributed Computing Systems”, IEEE Transactions on Software Engineering, Vol. 14, No. 2, February 1988, pp. 141-145.

[7] K. G. Shin and P. Ramanathan, “Real Time Computing: A New Discipline of Computer Science and Engineering,” Proceedings of the IEEE, Vol. 82, No. 1, 1994, pp. 6-24.

[8] H. Topcuoglu, S. Hariri and M.-Y. Wu, “Performance Effective Low Complexity Task Scheduling for Heterogeneous Computing,” IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 3, March 2002, pp. 260-274.

[9] Y. Kwok and I. Ahmed, “Static Scheduling Algorithm for Allocating Directed Task Graphs to Multiprocessors,” ACM Computing Surveys, Vol. 31, No. 4, 1999, pp. 406- 471.

[10] T. Yang and A. Gerasoulis, “DSC: Scheduling Parallel Task on an Unbounded Number of Processor,” IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 9, 1994, pp. 951-967.

[11] I. Ahmed and Y. Kwok, “A New Approach to Scheduling Parallel Programs Using Task Duplication,” Proceedings of the International Conference on Parallel Processing (ICPP), St. Charles, Vol. 3, August 1994, pp. (II)47-51.

[12] E. S. H. Hou, N. Ansari and H. Ren, “A Genetic Algorithm for Multiprocessor Scheduling,” IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 2, 1994, pp. 113-120.

[13] T. L. Adam, K. M. Chandy and J. R. Dickson, “A Comparison of List Schedules for Parallel Processing Systems,” Communications of ACM, Vol. 17, No. 12, 1974, pp. 685-690.

[14] K. Ramamritham and J. Stankovic, “Scheduling Algorithms and Operating Systems Support for Real Time Systems,” Proceedings of the IEEE, Vol. 82, No. 1, 1994, pp. 55-67.

[15] K. Ramamritham, I. Stankovic, et al., “Efficient Scheduling algorithms for Real time Multiprocessor Systems,” IEEE Transactions on Parallel and Distributed Systems, Vol. 1, No. 2 April 1990, pp. 184-194.

[16] K. Ramaritham, “Allocating and Scheduling of Precedence-Related Periodic Tasks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 6. No. 4, April 1995, pp. 412-420.

[17] H. Chetto and M. Chetto, “Some results of the Earliest Deadline Scheduling Algorithm,” IEEE Transactions on Software Engineering, Vol. 15, No. 10, October 1989, pp. 1261-1269.

[18] C. L. Liu and J. W. Layland, “Scheduling Algorithm for Multiprogramming in a Hard Real Time Environment,” Journal of the ACM, Vol. 20, No. 1, 1973, pp. 46-61.

[19] K. Mok and M. L. Dertouzos, “Multiprocessor Scheduling in a Hard Real Time Environments,” Proceedings of the 7th Texas Conference on Computing Systems, Houston, 1978, pp. 5-12.

[20] S. K. Trivedi, “Probability and Statistics with Reliability, Queuing, and Computer Science Applications,” Prentice Hall, Englewood Cliffs, 1982.

[1] D. G. Feitelson and B. Nitzberg, “Job Characteristics of a Production Parallel Scientific Workload on the NASA Ames iPSC/860,” In: D. G. Feitelson and L. Rudolph, Eds., Job Scheduling Strategies for Parallel Processing, IPPS’95 Workshop, Santa Barbara, Lecture Notes in Computer Science, Springer, Vol. 949, 1995, pp. 337- 360.

[2] S.-H. Chiang, R. K. Mansharamani and M. K. Vernon, “Use of Application Characteristics and Limited Preemption for Run-To-Completion Parallel Processor Scheduling Policies,” Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, Nashville, 1994, pp. 33-44.

[3] R. A. Idris, U.-K. Guillaume and W. E. Biersack, “Analysis of LAS Scheduling for Job Size Distributions with High Variance,” Proceedings of ACM SIGMETRICS, San Diego, 10-12 June 2003, pp. 218-228.

[4] F. Baskett, K. M. Chandy, R. Muntz and F. G. Palacious, “Open, Close and Mixed Networks of Queues with Different Classes of Customers,” Journal of the ACM, Vol. 22, No. 2, 1975, pp. 248-260.

[5] L. Lipsky, “Queueing Theory: A linear Algebraic Approach (LAQT),” 2nd Edition, Springer Verlag, New York, 2008.

[6] T. L. Casavant and J. G. Kuhl, “A Taxonomy of Scheduling in General Purpose Distributed Computing Systems”, IEEE Transactions on Software Engineering, Vol. 14, No. 2, February 1988, pp. 141-145.

[7] K. G. Shin and P. Ramanathan, “Real Time Computing: A New Discipline of Computer Science and Engineering,” Proceedings of the IEEE, Vol. 82, No. 1, 1994, pp. 6-24.

[8] H. Topcuoglu, S. Hariri and M.-Y. Wu, “Performance Effective Low Complexity Task Scheduling for Heterogeneous Computing,” IEEE Transactions on Parallel and Distributed Systems, Vol. 13, No. 3, March 2002, pp. 260-274.

[9] Y. Kwok and I. Ahmed, “Static Scheduling Algorithm for Allocating Directed Task Graphs to Multiprocessors,” ACM Computing Surveys, Vol. 31, No. 4, 1999, pp. 406- 471.

[10] T. Yang and A. Gerasoulis, “DSC: Scheduling Parallel Task on an Unbounded Number of Processor,” IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 9, 1994, pp. 951-967.

[11] I. Ahmed and Y. Kwok, “A New Approach to Scheduling Parallel Programs Using Task Duplication,” Proceedings of the International Conference on Parallel Processing (ICPP), St. Charles, Vol. 3, August 1994, pp. (II)47-51.

[12] E. S. H. Hou, N. Ansari and H. Ren, “A Genetic Algorithm for Multiprocessor Scheduling,” IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 2, 1994, pp. 113-120.

[13] T. L. Adam, K. M. Chandy and J. R. Dickson, “A Comparison of List Schedules for Parallel Processing Systems,” Communications of ACM, Vol. 17, No. 12, 1974, pp. 685-690.

[14] K. Ramamritham and J. Stankovic, “Scheduling Algorithms and Operating Systems Support for Real Time Systems,” Proceedings of the IEEE, Vol. 82, No. 1, 1994, pp. 55-67.

[15] K. Ramamritham, I. Stankovic, et al., “Efficient Scheduling algorithms for Real time Multiprocessor Systems,” IEEE Transactions on Parallel and Distributed Systems, Vol. 1, No. 2 April 1990, pp. 184-194.

[16] K. Ramaritham, “Allocating and Scheduling of Precedence-Related Periodic Tasks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 6. No. 4, April 1995, pp. 412-420.

[17] H. Chetto and M. Chetto, “Some results of the Earliest Deadline Scheduling Algorithm,” IEEE Transactions on Software Engineering, Vol. 15, No. 10, October 1989, pp. 1261-1269.

[18] C. L. Liu and J. W. Layland, “Scheduling Algorithm for Multiprogramming in a Hard Real Time Environment,” Journal of the ACM, Vol. 20, No. 1, 1973, pp. 46-61.

[19] K. Mok and M. L. Dertouzos, “Multiprocessor Scheduling in a Hard Real Time Environments,” Proceedings of the 7th Texas Conference on Computing Systems, Houston, 1978, pp. 5-12.

[20] S. K. Trivedi, “Probability and Statistics with Reliability, Queuing, and Computer Science Applications,” Prentice Hall, Englewood Cliffs, 1982.