Markov chain analyses of multiprogrammed computer systems

E. G. Coffman

Naval Research Logistics Quarterly, 1969, vol. 16, issue 2, 175-197

Abstract: Most operating systems for large computing facilities involve service disciplines which base, to some extent, the sequencing of object program executions on the amount of running time they require. It is the object of this paper to study mathematical models of such service disciplines applicable to both batch and time‐shared processing systems. In particular, Markov queueing models are defined and analyzed for round‐robin and foreground‐background service disciplines. With the round‐robin discipline, the service facility processes each program or job for a maximum of q seconds; if the program's service is completed during this quantum, it leaves the system, otherwise it returns to the end of the waiting line to await another quantum of service. With the foreground‐background discipline each new arrival joins the end of the foreground queue and awaits a single quantum of service. If it requires more it is subsequently placed at the end of the background queue which is allocated service only when the foreground queue is empty. The analysis focuses on the efficiency of the above systems by assuming a swap or set‐up time (overhead cost) associated with the switching of programs on and off the processor. The analysis leads to generating functions for the equilibrium queue length probabilities, the moments of this latter distribution, and measures of mean waiting times. The paper concludes with a discussion of the results along with several examples.

Date: 1969
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800160203

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:16:y:1969:i:2:p:175-197

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().