Stochastic Modeling of Processor Scheduling with Application to Data Base Management Systems
by S. S. Lavenberg, G. S. Shedler
This paper is concerned with the stochastic modeling of processor scheduling and of queuing due to contention for resources in data base management systems. The processing services rendered in searching the data base and retrieving and processing information are modeled explicitly, as is the algorithm used to schedule these services on the processor. The scheduling of the processor is based on a total priority ordering of a set of queues for processing service. A queuing model incorporating the processor scheduling algorithm for IMS (Information Management System) is formulated in order to illustrate the modeling ideas. The model is analyzed under rather general distributional assumptions, based on the observation that certain stochastic processes in the model are cumulative processes defined over the same embedded semi-Markov process. The model is not used in a performance study of IMS, nor is it proposed that the model developed here is one upon which a performance study of IMS should be undertaken. The model should be viewed as illustrative of stochastic models which can be constructed to incorporate algorithms for processor scheduling.