Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/800194.805879acmconferencesArticle/Chapter ViewAbstractPublication Pagesacm-national-conferenceConference Proceedingsconference-collections
Article
Free access

Simulation of dispatching algorithms in a multiprogramming environment

Published: 01 August 1972 Publication History

Abstract

CPU scheduling or dispatching in computer systems is surveyed. In order to study and evaluate a dispatching algorithm, a simulation model of a dispatching algorithm for multiprogramming operating system has been devised and programmed. Essential elements which have been included are the job environment, the computer system environment, and the user environment. The model is patterned basically after GECOS III, on the H-600 line computer. Some results of the investigation are presented, such as lengths of various queues, I/O time, processor utilization, expected time in various queues, throughput and flexibility.

References

[1]
"Analysis of Some Queueing Models in Real-Time Systems," IBM Corporation, IBM-GF20-0007-1.
[2]
"GE's New Monitor," Datamation, Vol. 13, 11 (November, 1967), 77-78.
[3]
"GE-600 Line GECOS III: Dispatcher and Peripheral Allocation," General Electric Information Systems Division, CPB-1491B.
[4]
"GE-625/635 Comprehensive Operating Supervisor (GECOS) Reference Manual," General Electric Information Systems Division, CPB-1195.
[5]
Abell, V.A., Rosen, S., and Wagner, R.E. "Scheduling in a General Purpose Operating System," Proceedings of the AFIPS Fall Joint Computer Conference, Vol. 37 (1970), 89-96.
[6]
Adiri, I. "Time-Sharing Queues with Priorities," Journal of the Association for Computing Machinery, 16, 4 (October, 1969), 631-645.
[7]
Adiri, I., and Avi-Itzhak, B. "A Time-Sharing Queue with a Finite Number of Customers," Journal of the Association for Computing Machinery, 16, 2 (April, 1969), 315- 323.
[8]
Baskett, F., Browne, J.C., and Raike, W. M. "The Management of a Multi-Level Non-Paged Memory System," Proceedings of the AFIPS Spring Joint Computer Conference, Vol. 36 (1970), 459-465.
[9]
Bernstein, A.J., and Sharp, J.C. "A Policy- Driven Scheduler for a Time-Sharing System," Communications of the Association for Computing Machinery, 14, 2 (February, 1971), 74-78.
[10]
Campbell, D.J., Cook, W., and Heffner, W.J. "General Comprehensive Operating Supervisor - GECOS III," Software Age, Vol. 2, 1 (January, 1968), 8-16.
[11]
Campbell, D.J., and Heffner, W.J. "Measurement and Analysis of Large Operating Systems During System Development," Proceedings of the AFIPS Fall Joint Computer Conference, Vol. 33 (1968), 903-914.
[12]
Cantrell, H.N., and Ellison, A.L. "Multiprogramming System Performance Measurement and Analysis," Proceedings of the AFIPS Spring Joint Computer Conference, Vol. 32 (1968), 213-221.
[13]
Cheng, P.S. "Trace-driven System Modeling," IBM Systems Journal, 4 (1969), 280- 289.
[14]
Coffman, E.G. "Analysis of Two Time-Sharing Algorithms," Journal of the Association for Computing Machinery, 15, 3 (July, 1968), 341-353.
[15]
Coffman, E.G. "Studying Multiprogramming Systems with the Queueing Theory," Datamation, 13, 6 (June, 1967), 47-54.
[16]
Coffman, E.G., and Kleinrock, L. "Computer Scheduling Methods and Their Countermeasures," Proceedings of the AFIPS Spring Joint Computer Conference, Vol. 32 (1968), 11-21.
[17]
Coffman, E.G., Muntz, R.R., and Trotter, D. "Waiting Time Distributions for Processor-Sharing Systems," Journal of the Association for Computing Machinery, Vol. 17, 1 (January, 1970), 123-130.
[18]
Corbató, F.J. "An Experimental Time-Sharing System," Programming Systems and Language. New York: McGraw-Hill Book Co., 1967, 683-698.
[19]
Curry, G.L., and Schuermann, A.C. "Scheduling in a Multiprogramming Environment," Software Age, Vol. 2, 1 (January, 1968), 32-35.
[20]
Delbrouck, L.E.N. "A Feedback Queueing System with Batch Arrivals, Bulk Service, and Queue-Dependent Service Time," Journal of the Association for Computing Machinery, Vol. 17, 2 (April, 1970),314-323.
[21]
Doherty, W.J. "Scheduling TSS-360 for Responsiveness," Proceedings of the AFIPS Fall Joint Computer Conference, Vol. 37 (1970), 97-111.
[22]
Drummond, Jr., M.E. "A Perspective on System Performance Evaluation," IBM Systems Journal, 4 (1969), 252-263.
[23]
Estrin, G., and Kleinrock, L. "Measures, Models, and Measurements for Time-Shared Computer Utilities," Proceedings of the 22nd ACM National Conference, (1967), Thompson Book Company, Washington, D.C., 85-96.
[24]
Feller, W. An Introduction to Probability Theory and Its Applications. Vol. 1, Third Edition. New York: John Wiley & Sons, Inc., 1968.
[25]
Fine, G.H., and McIsaac, P.V. "Simulation of a Time-Sharing System," Management Science, Vol. 12, 6 (February, 1966), 180-194.
[26]
Gaver, Jr., D.P. "Probability Models for Multiprogramming Computer Systems," Journal of the Association for Computing Machinery, Vol. 14, 3 (July, 1967), 423-438.
[27]
Gordon, G. System Simulation. New York: Prentice-Hall, Inc., 1969.
[28]
Greenberger, M. "The Priority Problem and Computer Time-Sharing," Management Science, Vol. 12, 11 (1966), 888-906.
[29]
Havender, J.W. "Avoiding Deadlock in Multitasking Systems," IBM Systems Journal, Vol. 7, 2 (1968), 74-84.
[30]
Hellerman, H. "Time-Sharing Scheduler Strategies," IBM Systems Journal, Vol. 8, 2 (1969), 94-117.
[31]
Huesmann, L.R., and Goldberg, R.P. "Evaluating Computer Systems through Simulation," Computer Journal, Vol. 10, 2 (August, 1967), 150-156.
[32]
Jackson, J.R. "Jobshop-like Queuing Systems," Management Science Vol. 10 (1963), 131-142.
[33]
Karush, A.D. 3 "Two Approaches for Measuring the Performance of Time-Sharing Systems," Software Age, (March, 1970), 10-13. (April, 1970), 26-27, 40. (May, 1970), 13-14.
[34]
Kleinrock, L. "A Delay Dependent Queue Discipline," Naval Research Logistics Quarterly, Vol.11, 4 (December, 1964), 329-342.
[35]
Kleinrock, L. "Analysis of a Time-Shared Processor," Naval Research Logistics Quarterly, Vol.11, I (March, 1964), 59-74.
[36]
Kleinrock, L. "Sequential Processing Machines Analyzed with a Queuing Theory Model," Journal of the Association for Computing Machinery, Vol. 13, 2 (April, 1966), 179-193.
[37]
Kleinrock, L. "Time-Shared Systems: A Theoretical Treatment," Journal of the Association for Computing Machinery, Vol. 14, 2 (April, 1967), 242-261.
[38]
Kleinrock, L. "A Continuum of Time-Sharing Scheduling Algorithms," Proceedings of the AFIPS Spring Joint Computer Conference, Vol. 36 (1970), 453-458.
[39]
Lasser, D.J. "Productivity of Multiprogrammed Computers - Progress in Developing an Analytic Prediction Method," Communications of the Association for Computing Machinery, Vol. 12, 12 (December, 1969), 678-684.
[40]
Marshall, B.S. "Dynamic Calculation of Dispatching Priorities Under OS/360," Datamation, Vol. 15, 8 (August, 1969), 93-97.
[41]
McKinney, J.M. "A Survey of Analytical Time-Sharing Models," Computing Surveys, Vol. 1, 2 (June, 1969), 105-106.
[42]
Muntz, R.R., and Coffman, E.G. "Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems," Journal of the Association for Computing Machinery, Vol. 17, 2 (April, 1970), 324-338.
[43]
Nielson, N.R. "The Simulation of Time-Sharing Systems," Communications of the Association for Computing Machinery, Vol. 10, 7 (July, 1967), 397-412.
[44]
Nielson, N.R. "An Analysis of Some Time-Sharing Techniques," Communications of the Association for Computing Machinery, Vol. 14, 2 (February, 1971), 79-90.
[45]
Norland, K.E., and Bulgren, W.G. "A Simulation Model of GECOS III," Proceedings of 1971 Annual Conference of the Association for Computing Machinery, 596- 612.
[46]
Penny, J.P. "An Analysis, Both Theoretical and by Simulation of a Time-Shared Computer System," Computer Journal, Vol. 9 (May, 1966), 53-59.
[47]
Phillips, K. "A Survey of Core Allocation Schemes with a Simulation and Analysis of the H-635 Scheme," Personal Communication (to be published).
[48]
Rasch, P.J. "A Queuing Theory Study of Round Robin Scheduling of Time-Shared Computer Systems," Journal of the Association for Computing Machinery, Vol. 17, 1 (January, 1970), 131-146.
[49]
Rehmann, S.L., and Gangwere, S.G. "A Simulation Study of Resource Management in a Time-Sharing System," Proceedings of the AFIPS Fall Joint Computer Conference, Vol. 32 (1968), 1411-1430.
[50]
Rothkopf, M. "Scheduling with Random Service Times," Management Science, Vol. 12, 9 (May, 1966), 707-713.
[51]
Saaty, T. "Seven More Years of Queues," Naval Research Logistics Quarterly, Vol. 13, 4 (December, 1966), 447-476.
[52]
Saltzer, J.H., and Gintell, J.W. "The Instrumentation of Multics," Communications of the Association for Computing Machinery, Vol. 13, 8 (August, 1970), 495-500.
[53]
Seaman, P.H., and Soucy, R.C. "Simulating Operating Systems," IBM Systems Journal, 4 (1969), 264-279.
[54]
Scherr, A.L. "An Analysis of Time-Shared Computer Systems," Research Monograph No. 36, The MIT Press (1967).
[55]
Scherr, A.L. "Time-Sharing Measurement," Datamation, Vol. 12, 4 (April, 1966), 22-26.
[56]
Scherr, A.L., and Larkin, D.C. "Time-Sharing for OS," Proceedings of the AFIPS Fall Joint Computer Conference, Vol. 37, (1970), 113-117.
[57]
Sedgewick, R., Stone, R., and McDonald, J.W. "SPY - A Program to Monitor OS/360," Proceedings of the AFIPS Fall Joint Computer Conference, (1970), 119-128.
[58]
Shemer, J.E. "Some Mathematical Considerations of Time-Sharing Scheduling Algorithms," Journal of the Association for Computing Machinery, Vol. 14, 2 (April, 1967), 262-272.
[59]
Stanley, W.I., and Hertel, H.F. "Statistics Gathering and Simulation for Apollo Real-Time Operating System," IBM Systems Journal, Vol. 7, 2 (1968), 85-102.
[60]
Stimler, S. "Some Criteria for Time-Sharing System Performance," Communications of the Association for Computing Machinery, Vol. 12, 1 (January,1969), 47-53.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
ACM '72: Proceedings of the ACM annual conference - Volume 2
August 1972
530 pages
ISBN:9781450374927
DOI:10.1145/800194
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1972

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. CPU scheduling
  2. Computer system analysis
  3. Multiprogramming
  4. Simulation

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 310
    Total Downloads
  • Downloads (Last 12 months)20
  • Downloads (Last 6 weeks)5
Reflects downloads up to 11 Dec 2024

Other Metrics

Citations

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media