More Web Proxy on the site http://driver.im/

Article

Free access

Studies in Markov models of computer systems

Authors:

William BulgrenAuthors Info & Claims

ACM '75: Proceedings of the 1975 annual conference

Pages 102 - 107

https://doi.org/10.1145/800181.810294

Published: 01 January 1975 Publication History

Abstract

A new general model of I/O - CPU interation is described.

The model is a discrete Markov process, and takes into account mean CPU time between physical I/O requests, mean I/O service times for each device, single or double buffering, and CPU queue discipline. A simple method of finding the steady state probability vector is shown. The utilization results are calculated and compared to, for three CPU queue disciplines, and for various service times, the results of earlier analytical models, with some interesting outcomes. The new model is limited presently to small systems (i.e., five or less tasks, and six or less I/O queues) due to the number of states necessary to model a large system.

References

[1]

Abate, J., Dubner, H., and Weinberg, S.B., Queuing Analysis of the IBM 2314 Disk Storage Facility, Journal of the ACM, 15, Oct. 1968,577-589.

Digital Library

[2]

Abate, J., and Dubner, H., Optimizing the Performance of a Drum-like Storage, IEEE Trans. on Computers, c-18:11, Nov. 1969.

[3]

Anderson, H.A. Jr., and Sargent, R.G., A Statistical Evaluation of the Scheduler of an Experimental Interactive Computing System, Statistical Computer Performance Evaluation, Academic Press, Nov. 1971, 73-98.

[4]

Anderson, H.A., Jr., Approximating Pre-Emptive Priority Dispatching in a Multiprogramming Model, IBM J. of Research and Development, 17, Nov. 1973, 533-539.

Digital Library

[5]

Arora, S.R., and Gallo, A., The Optimal Organization of Multiprogrammed Multi-level Memory, ACM (SIGOPS) Workshop on System Performance Evaluation, Harvard Univ., April 1971, 104-141.

Digital Library

[6]

Bard, Y., and Suryanarayana, K.V., On the Structure of CP-67 Overhead, Statistical Computer Performance Evaluation, Academic Press, 1971, 329-346.

[7]

Buzen, J., Analysis of System Bottlenecks Using a Queueing Network Model, ACM (SIGOPS) Workshop on System Performance Evaluation, Harvard Univ., 1971, 82-103.

Digital Library

[8]

Chang, W., Queues with Feedback for Time Sharing Computer System Analysis, Operations Research, 16:3, May-June 1968, 613-627.

Digital Library

[9]

Chang, W., Peternot, Y.J., and Ray, J.A., Throughput Analysis of Computer Systems—Multiprogramming Versus Multiprocessing, ACM (SIGOPS) Workshop on System Performance Evaluation, Harvard Univ., 1971, 59-81.

Digital Library

[10]

Chang, W., Computer Interference Analysis, IBM J. of Research and Development, Jan, 1973, 13-26.

[11]

Coffman, E.G., and Kleinrock, L., Feedback Queuing Models for Time Sharing Systems, J. of ACM, 15:4, 1968, 549-576.

Digital Library

[12]

Coffman, E.G., Analysis of a Drum I/O Queue under Scheduled Operation in a Paged Computer System, J. of ACM, 16:1, Jan. 1969, 73-90. Correction in J. of ACM, 16:4, 646.

Digital Library

[13]

Coffman, E.G., Muntz, R.R., and Trotter, T., Waiting Time Distribution for Processor Sharing Systems, J. of ACM, 17:1, Jan. 1970, 123-130.

Digital Library

[14]

Denning, P.J., A Statistical Model for Console Behavior in Multi-user Computers, Comm. of ACM, 11:9, Sept. 1968, 605-612.

Digital Library

[15]

Estrin, G., and Kleinrock, L., Measures, Models and Measurements for Time Shared Computer Utilities, Proc. 1967 ACM Natl Conf., 85-96.

Digital Library

[16]

Feeley, J.M, A Computer Performance Monitor and Markov Analysis for Multiprocessor System Evaluation, Statistical Computer Performance Evaluation, Academic Press, 1971, 165-226.

[17]

Feller, W., An Introduction to Probability Theory and its Applications, Vol. 2, Wiley, New York, 1966.

[18]

Fenichel, R.R., and Grossman, A.J., An Analytic Model of Multi-programmed Computering, AFIPS Spring Joint Computer Conf., Vol. 34, 1969, 717-721.

[19]

Foley, J.D., A Markovian Model of the University of Michigan Executive System, Comm. of ACM, 10:9, Sept. 1967, 584-588.

Digital Library

[20]

Frank, H., Analysis and Optimization of Disk Storage Devices for Time Sharing System, J. of ACM, 16:4, Oct. 1969, 602-620.

Digital Library

[21]

Gaver, D.P., Probability Models for Multiprogramming Computer Systems, J. of ACM, 14:3, July, 1967.

Digital Library

[22]

Gaver, D.P., and Shedler, G.S., Control Variable Methods in the Simulation of a Multiprogrammed Computer System, Naval Research Logistics Quarterly, Vol. 18, No. 4, Dec. 1971, 435-450.

[23]

Gordon, W.J., and Newell, G.F., Closed queueing systems with exponential servers, Operations Research, 15, 1967, 254-265.

Digital Library

[24]

Hanssmann, F., Kistler, W., and Schulz, H., Modeling for Computer Center Planning, IBM Systems J., 10:4, 1971, 305-324.

Digital Library

[25]

Hellerman, H., and Smith, H.J., Throughput Analysis of Some Idealized Input, Output, and Compute Overlap Configurations, Computing Surveys, 2:2, 1970, 111-118.

Digital Library

[26]

Jackson, J.R., Networks of Waiting Lines, Operations Research, 5, 1957, 518-521.

Digital Library

[27]

Jackson, J.R., Jobshop-like queueing systems, Management Science, 10:1, Oct. 1963, 131-142.

Digital Library

[28]

Kimbleton, S.R., and Moore, C.G., A Probabilistic Framework for System Performance Evaluation, ACM (SIGOPS) Workshop on System Performance Evaluation, Harvard Univ., 1971, 337-361.

Digital Library

[29]

Kleinrock, L., Time Shared Systems-A Theoretical Treatment, J. of ACM, 14:2, April 1967, 242-261.

Digital Library

[30]

Kobayaski, H., Application of the Diffusion Approximation to Queuing Networks, Part 1, Proc. of the ACM-SIGME Symposium on Measurement and Evaluation, Feb. 1973, 54-60.

Digital Library

[31]

Kobayashi, H., Application of the Diffusion Approximation to Queueing Networks I: Equilibrium Queue Distributions, J. of ACM, 21, 1974, 316-328.

Digital Library

[32]

Kobayashi, H., Application of the Diffusion Approximation to Queueing Networks II: Nonequilibrium Distribution and Application to Computer Modeling, J. of ACM, 21, 1974, 459-469.

Digital Library

[33]

Krishnamoorthi, B., Time-Shared Computer Operations with Both Interarrival and Service Times Exponential, J. of ACM, 13:3, July 1966, 317-338.

Digital Library

[34]

Lassettre, E.B., and Scherr, A.L., Modelling the Performance of the OS-360 Time Sharing Option (TSO), Statistical Computer Performance Evaluation, Academic Press, 1971, 57-72.

[35]

Little, J., A Proof of the Queueing Formula L&equil;&lgr;W, Operations Research, Vol. 9, No. 3, 383-387.

Digital Library

[36]

McCredie, J.W., Analytic Models as Aids for Multiprocessor Design, Proc. of the 7th Annual Princeton Conference on Information Science and Systems, March 1973.

[37]

McKinney, J.M., A Survey of Analytical Time Sharing Models, Computing Surveys, 1:2, 1969, 105-116.

Digital Library

[38]

Mitrani, I., Nonpriority Multiprogramming Systems under Heavy Demand Conditions, J. of ACM, 19:3, July 1972, 445-452.

Digital Library

[39]

Newell, G.F., Applications of Queueing Theory, London, Chapman and Hall, 1971.

[40]

Parzen, E., Stochastic Processes, Holden-Day, San Francisco, 1962.

Digital Library

[41]

Posner, M., and Bernholtz, B., Two-Stage Closed Queueing Systems with Time Lags, Can. Opnal. Res. Soc. J., 5, 1967, 82-99.

[42]

Posner, M., and Bernholtz, B., Closed Finite Queueing Networks with Time Lags, Operations Research, 16, 1968, 962-976.

Digital Library

[43]

Posner, M., and Bernholtz, B., Queueing Network with Time Lags and Several Classes of Units, Operations Research, 16, 1968, 977-985.

Digital Library

[44]

Racite, M.P., The Use of Pure and Modified Regression Techniques for Developing Systems Performance Algorithms, Statistical Computer Performance Evaluation, Academic Press, 1971, 347-370.

[45]

Rasch, P., A Queuing Theory Study of Time-Shared Computer Systems, J. of ACM, 1970, 131-145.

Digital Library

[46]

Rosenblatt, M., Random Processes, Oxford Press, New York, 1962.

[47]

Scherr, A.L., An Analysis of Time-Shared Computer Systems, MIT Press, Cambridge, Mass., 1967.

[48]

Schrage, L., Analysis and Optimization of a Queuing Model of a Real-Time Computer Control System, IEEE Trans. on Computers, c-18:11, Nov. 1969, 997-1003.

[49]

Shedler, G.S., A Queuing Model of a Multiprogrammed Computer with a Two Level Storage System, Comm. of ACM, 16:1, Jan. 1973, 3-10.

Digital Library

[50]

Shemer, J.E., Some Mathematical Considerations of Time Sharing Scheduling Algorithms, J. of ACM, 14:2, April 1967, 262-270.

Digital Library

[51]

Smith, J.L., An Analysis of Time Sharing Computer Systems Using Markov Models, AFIPS Spring Joint Computer Conf., 34, 1969, 87-95.

[52]

Strauss, J.C., An Analytic Model of the Hasp Execution Task Monitor, Proc. of ACM-SIGME Symp. on Measurement and Evaluation, Feb. 1973.

Digital Library

[53]

Waldbaum, G., Evaluating Computing System Changes by Means of Regression Models, Proc. of ACM-SIGME Symp. on Measurement and Evaluation, Feb. 1973.

Digital Library

[54]

Wallace, V.L., and Rosenberg, R.S., Markov Models for Numerical Analysis of Computer System Behavior, Proc. AFIPS 1966 Joint Comp. Conf., 141-148.

[55]

Yeh, A.C., An Application of Statistical Methodology in the Study of Computer System Performance, Statistical Computer Performance Evaluation, Academic Press, 1971, 287-328.

Cited By

Madnick SWang Y(1986)Modeling multiprocessor computer systems with unbalanced flowsACM SIGMETRICS Performance Evaluation Review10.1145/317531.31753614:1(28-34)Online publication date: 1-May-1986
https://dl.acm.org/doi/10.1145/317531.317536
Madnick SWang YPerros HStewart WTrivedi K(1986)Modeling multiprocessor computer systems with unbalanced flowsProceedings of the 1986 ACM SIGMETRICS joint international conference on Computer performance modelling, measurement and evaluation10.1145/317499.317536(28-34)Online publication date: 1-May-1986
https://dl.acm.org/doi/10.1145/317499.317536
Heidelberger PTrivedi K(1983)Analytic Queueing Models for Programs with Internal ConcurrencyIEEE Transactions on Computers10.1109/TC.1983.167612532:1(73-82)Online publication date: 1-Jan-1983
https://dl.acm.org/doi/10.1109/TC.1983.1676125
Show More Cited By

Index Terms

Studies in Markov models of computer systems

Recommendations

Markov-modulated finite-source queueing models in evaluation of computer and communication systems

The present paper deals with a first-come, first-served (FCFS) queueing model to analyze the behaviour of a heterogeneous finite-source system with a single server. The sources and the server are assumed to operate in independent Markovian environments, ...
Queueing systems with vacations and priorities with applications in production and computer systems modeling
Multiserver Queueing Models of Multiprocessing Systems

Conventional time sharing and multiprogramming systems have been extensively modeled as single-server queues. In contrast, multiprocessing systems must be modeled as multiserver queueing systems. This paper investigates the effect of the scheduling ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ACM '75: Proceedings of the 1975 annual conference

January 1975

371 pages

ISBN:9781450374811

DOI:10.1145/800181

Copyright © 1975 ACM.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1975

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
395
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)3

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Madnick SWang Y(1986)Modeling multiprocessor computer systems with unbalanced flowsACM SIGMETRICS Performance Evaluation Review10.1145/317531.31753614:1(28-34)Online publication date: 1-May-1986
https://dl.acm.org/doi/10.1145/317531.317536
Madnick SWang YPerros HStewart WTrivedi K(1986)Modeling multiprocessor computer systems with unbalanced flowsProceedings of the 1986 ACM SIGMETRICS joint international conference on Computer performance modelling, measurement and evaluation10.1145/317499.317536(28-34)Online publication date: 1-May-1986
https://dl.acm.org/doi/10.1145/317499.317536
Heidelberger PTrivedi K(1983)Analytic Queueing Models for Programs with Internal ConcurrencyIEEE Transactions on Computers10.1109/TC.1983.167612532:1(73-82)Online publication date: 1-Jan-1983
https://dl.acm.org/doi/10.1109/TC.1983.1676125
Towsley DChandy KBrowne J(1978)Models for parallel processing within programsCommunications of the ACM10.1145/359619.35962221:10(821-831)Online publication date: 1-Oct-1978
https://dl.acm.org/doi/10.1145/359619.359622
Jiřina MSargent RSchmidt J(1977)Simulation of multiprocessor computer with local memoriesProceedings of the 9th conference on Winter simulation - Volume 210.5555/800289.811276(684-692)Online publication date: 1-Jan-1977
https://dl.acm.org/doi/10.5555/800289.811276

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents