Optimization Problems Arising in Time-Shared Systems

摘要

A comprehensive survey of the analytic time-sharing models to date is presented. Most of these models neglect swapping time which is known to be one of the greatest impediments to efficient time-sharing operations. Assuming a constant swapping time, results are developed here for the following models: infinite source round-robin, finite source round-robin, and infinite source foreground-background. From cost function considerations (based on response time), optimal values of those parameters under the direct control of the systems designer (i.e., the quantum size (s), number of users, and, in the foreground-background case, the number of queues) are characterized and procedures for finding these optimal values outlined. Complementing the fixed quantum models described above is an adaptive quantum, finite source round-robin model. The quantum allocated is a function of the number in the system. An algorithm based on Jewell's Markov-renewal programming techniques is developed which may be used to choose optimally the quantum size for each state. Comparisons with corresponding fixed quantum models are made. An annotated bibliography is provided. (Author)