1

ADII~I, IGAL. A time-sharing queue with preemptive resume pmonty discipline. Oper. Res. Stat. and ~con. Mlmeo Ser. No. 7. Dep. of Indust and Mgt. Eng., Techmon, Israel Institute of Technology, Halfa, Israel, Dec. 1967 This paper deals with a TS system with Polsson arrivals and exponential service operating under a preemptive resume-priomt~ disciphne as a special case of a station operating on an RR basis and subject to breakdowns2

2

Computer time-sharing with pnorltms. Oper. Res. Stat. and Econ. Mlmeo Set. No. 13, Dep. of Indust. and Mgt. Eng., Technion, Israel Institute of Technology, Halfa, Israel, May 1968. For a TS system with Poisson arrivals and exponential service, the following priority disciplines are discussed: (a) head-of-thehne, (b) preemptive repeat, and (c) mixed preemptive strategy.S

3

B. Krishnamoorthi , Roger C. Wood, Time-Shared Computer Operations With Both Interarrival and Service Times Exponential, Journal of the ACM (JACM), v.13 n.3, p.317-338, July 1966  [doi>10.1145/321341.321342]

4

CHANG, W. A queuemg model for a simple case of time-sharing. IBM Syst. J 5 (1966), 115-125. An infinite source RR system having the quantum size a random variable is studied. Derived are the expected number m queue, expected response time, average busy period length, and mare memory size requirements.

5

Queues with feedback for time-sharing computer system analysis. Oper Res. 16 (1968), 613-627. A preemptive, externally assigned priority class model is formulated with Poisson input from each class and zero overhead and swap~ ping time. Generating functions for queue size and Laplace transforms of the response time for each class are found.

6

COFFMAN, E. G. Stochastic models of multiple and time-shared computer operations. No. 66- 38, UCLA Eng. Rep, UCLA, Los Angeles, Calif., June 1966. RR and FB models under running-time priority discJphnes and a vamety of assumptions are given a most comprehensive study. One chapter contains one of the few available analyses of a multiprocessor system. Thin paper 2s available from Reports Group, Dept. of Eng.. Boelter Hall, Room 7526, U of California, Los Angeles, Calif. 90024.

7

Studying multiprogrammmg systems with the queuemg theory. Datamation 18, 6 (June 1967), 47-54. This paper reviews the formal queuemg models (RR and FB) which can assist in the analysis of priority rules m multlprogrammmg computer systems. Results from eight papers are presented.

8

An analysis of computer operations under running-time priority disciplines..Proc. ACM Symp. on Interactive Systems for Expemmental and Applied Mathemahcs, Academic Press, New York, 1968. Some of the results in {6} are presented

9

E. G. Coffman, Jr., Analysis of Two Time-Sharing Algorithms Designed for Limited Swapping, Journal of the ACM (JACM), v.15 n.3, p.341-353, July 1968  [doi>10.1145/321466.321467]

10

AND KRISHNAMOORTHI, B. Preliminary anal~'ses of time-shared computer operation. Doc. SP-1719, System Development Corp.. Santa Momca, Calif., Aug. 1964. In this paper a model of the time-sharing system developed by SDC is given and erapineal measurements provided. Then analyhc results for a fimte source, RR system with constant swap time and geometric service times are derived using Markov chains. Tilts paper is available from System Development Corp., 2500 Colorado Ave.. Santa Monica. Cahf

11

Edward G. Coffman , Leonard Kleinrock, Feedback Queueing Models for Time-Shared Systems, Journal of the ACM (JACM), v.15 n.4, p.549-576, Oct. 1968  [doi>10.1145/321479.321483]

12

AND Computer scheduling methods and their countermeasures. Proc. AFIPS 1968 Spring Joint Comput. Conf, Vol. 32, Thompson Book Co.. Washington, D. C., pp. 11-21. A survey of the important scheduling algorithms together with countermeasures a user might employ to improve service to himself

13

CORBATS, F. J., et al. An experimental timesharing system. Proc. AFIPS 1962 Spring Joint Comput. Conf.. Vol. 21, Spartan Books. New York, pp. 335-344. This classic reference discusses the need for time-sharing, some of the implementation T)roblems, and presents the Corbato scheduling algorithm, which is essentially an FBN system with logarithmic queue structure.

14

Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968  [doi>10.1145/363095.363141]

15

puter systems Rep. MAC-TR-50, MIT Project MAC. Cambridge, Mass., May 1968. The dynamic allocation of limited processor and main memory resources among the users is investigated in four phases: (1) a model for program behavior is constructed, (2) the properties of system demand are defined and studied, (3) system balance policies are formulated as mathematical programming problems whose solutions are found dynamically by the scheduler, (4) these ideas are applied to the design and administration of multiprocess computer systems. Available from the Clearinghouse for Federal Scientific and Techmcal information (CFSTI), Sills Bldg, 5285 Port Royal Rd., Springfield, VA 22151

16

G. Estrin , L. Kleinrock, Measures, models and measurements for time-shared computer utilities, Proceedings of the 1967 22nd national conference, p.85-96, January 1967, Washington, D.C., United States  [doi>10.1145/800196.805978]

17

GREENBERGER, M. The priority problem and computer time-sharing. Ma~ Sci. 15(1966), 888- 906. eginning with a rather philosophic discussion of priority and cost assignments, this paper then applies these considerations to RR system w~th constant swap-time. The pptimal quantum size Is investigated via this costing model.

18

JACKSON, J.R. Jobshop-like queueing systems. Man. Sci 10 (1963), 131-142. The equilibrium joint probability distribution of queue length's Is obtained for a broad class of jobshop-like networks of waiting lines. The generation of routings is modeled as a random walk.

19

KLEINROCK, L. Analysis of a time-shared processor. Nay. Res. Log. Quart. 11 (1964), 59-73. This paper analyzes a queueing structure for a RR time-shared system with Bernoulli mput and geometric service times. The expected response time conditioned on service time is found and compared with the FCFS discipline.

20

Leonard Kleinrock, Sequential Processing Machines (S.P.M) Analyzed With a Queuing Theory Model, Journal of the ACM (JACM), v.13 n.2, p.179-193, April 1966  [doi>10.1145/321328.321329]

21

Communication Nets; Stochastic Message Flow and Delay. McGraw-Hill, New York, 1964. This monograph considers the stochastic flow of message traffic in connected networks of communication centers.

22

A conservation law for a wide class ot queuemg disciplines. Nay. Res Log. Quart. 12 (1965), 181-192 It is shown for queueing systems with Poisson input, no defections, and no work losses that a particular weighted sum of the waitmg times is a constant independent of the queue discipline. Time-shared systems: a theoretical treat-

23

ment. J. ACM 13, 2 (Apr. 1967), 242-261. "Ideal" (i.e. zero overhead and swapping time) RR and externally assigned priority class systems with Poisson arnvals and geometric or exponential service times are studied. Expected response times are derived both m the fimte Q case and the processorshared (i.e. Q --) 0) case.

24

~. Certain analytic results for time-shared processors. Proc. 1968 IFIP Cong. (in press). In the context of a fimte source model with exponential "think times" and servme times, system saturation is defined and studied. The degradation in performance caused by splitting a system into smaller systems is also investigated. -- Optimum bribing for queue position.

25

Oper. Res. 15 (1967), 304-318. A non-time-sharing model is presented in which relative position in tile queue is determined by the size of the customer's bribe. A cost function encompassing the bribe and the cost of waiting is defined and the conditions for an optimal bribing function are then found.

26

-, ANt) COFF~, E. G. Distribution of attained service in time-shared systems. 3. Cornput. Syst. Sci. 1 (1967), 287-298. The attained service for an incompletely serviced customer is the number of seconds that he has so far spent in the service facility. In this paper the distribution of attained servwe is found in terms of the average response time.

27

KaISHNAMOOaTHI, B. The stationary behavior of a time-sharing system under poisson assumptions. Doc. SP 2090, System Development Corp., Santa Monica, Cahf., Sept. 1965. Using renewal-theoretic arguments, the limiting dlstrlbutmn of the number of active channels at time t is found for a time-sharing system with both lnteramval and service times exponential and a finite number of users. This paper is available from System Development Corporation, 2500 Colorado Ave., Santa Momca, Calif.

28

B. Krishnamoorthi , Roger C. Wood, Time-Shared Computer Operations With Both Interarrival and Service Times Exponential, Journal of the ACM (JACM), v.13 n.3, p.317-338, July 1966  [doi>10.1145/321341.321342]

29

LITTLe, J. D. C. A proof of the queueing formula L -- kW. Oper. Res. 9 (1961), 383-387. The first published proof of the often used queueing formula that the average queue length is given by the product of the average arrival rate and the average system waiting time.

30

PATEL,'N. R. A mathematical analysis of computer time-sharing systems. Int. Tech. Rep. No. 20 ARO(D), Grant no. DA-ARO(D)-31-124- G158, Oper. Res Center, MIT, Cambridge. Mass., 1964. Both a RR and a FBN system (the latter closely akin to the Corbato algorithm {13}) are analyzed for the expected waits of requests. Available from Clearinghouse for Federal Scientific Technical Information (CFSTI), Sills Bldg., 5285 Port Royal Rd., Springfield, VA 22151.

31

SCHERR, A. L. An Analyszs o} T~me-Shared Computer Systems. MIT Press, Cambridge, Mass., 1967. This classic presents analytic and simulation models of the Project MAC time-sharing system together with measurements of that system and valuable discussions of the resuits.

32

SCHRAGE, L. E., AND MILLER, L.W. The queue M/G/1 with the shortest remaimng processing time discipline. Oper Res. 13, 4 (July-Aug. 1966), 670-684. A priority queueing model in which the service tames of jobs are known and preemption without loss occurs is studmd. The priority rule used is an extensmn of the shortest-jobfirst discipline.

33

~ The queue M/G/1 with feedback to lower priority queues. Man. Sci. 13(1967), 466- 474. The queue M/G/1 with a FB~ discipline is considered. Laplace transforms and expressions for the moments of response time are found.

34

Jack E. Shemer, Some Mathematical Considerations of Time-Sharing Scheduling Algorithms, Journal of the ACM (JACM), v.14 n.2, p.262-272, April 1967  [doi>10.1145/321386.321389]

35

TAKACS, L. Introduction to the Theory o} Queues Oxford U Press, New York, 1962 A useful reference containing many of the results of priority queueing systems needed for time-sharing analyses.

Peter J. Denning, Third Generation Computer Systems, ACM Computing Surveys (CSUR), v.3 n.4, p.175-216, Dec. 1971

R. G. Hamlet, Efficient multiprogramming resource allocation and accounting, Communications of the ACM, v.16 n.6, p.337-343, June 1973

N. S. Losapio , William G. Bulgren, Simulation of dispatching algorithms in a multiprogramming environment, Proceedings of the ACM annual conference, p.903-913, August 01-01, 1972, Boston, Massachusetts, United States

Greg Henderson , Juan Rodriguez-Rosell, The optimal choice of window sizes for working set dispatching, ACM SIGMETRICS Performance Evaluation Review, v.3 n.4, p.10-33, December 1974

Forest Baskett, The dependence of computer system queues upon processing time distribution and central processor scheduling, Proceedings of the third ACM symposium on Operating systems principles, p.109-113, October 18-20, 1971, Palo Alto, California, United States

John Peterson , William Bulgren, Studies in Markov models of computer systems, Proceedings of the 1975 annual conference, p.102-107, January 1975

Kenneth E. Norland , William C. Bulgren, A simulation model of GECOS III, Proceedings of the 1971 26th annual conference, p.596-612, January 1971

L. Kleinrock , R. R. Muntz, Processor Sharing Queueing Models of Mixed Scheduling Disciplines for Time Shared System, Journal of the ACM (JACM), v.19 n.3, p.464-482, July 1972

C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973

Jair M. Babad, A Generalized Multi-Entrance Time-Sharing Priority Queue, Journal of the ACM (JACM), v.22 n.2, p.231-247, April 1975

S. D. Conte , M. H. Halstead, The technology of computer center management: a proposed course for graduate professional programs in computer science or in information systems, Communications of the ACM, v.19 n.7, p.369-370, July 1976

Dileep P. Bhandarkar , Samuel H. Fuller, Markov chain models for analyzing memory interference in multiprocessor computer systems, ACM SIGARCH Computer Architecture News, v.2 n.4, p.1-6, december 1973

Manfred Ruschitzka , R. S. Fabry, A unifying approach to scheduling, Communications of the ACM, v.20 n.7, p.469-477, July 1977

Stephen R. Kimbleton , G. Michael Schneider, Computer Communication Networks: Approaches, Objectives, and Performance Considerations, ACM Computing Surveys (CSUR), v.7 n.3, p.129-173, Sept. 1975

Mark Franklin , David Looney, Simulation of a computer system with single and dual density discs, Proceedings of the 1st symposium on Simulation of computer systems, p.258-267, June 19-20, 1973, Gaithersburg, Maryland, United States

C. L. Liu , James W. Layland, Scheduling algorithms for multiprogramming in a hard-real-time environment, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001

John W. McCredie, Jr., A tandem queueing model of a time-sharing computing system, Proceedings of the ACM annual conference, p.991-1000, August 01-01, 1972, Boston, Massachusetts, United States

W. C. Lynch, Operating system performance, Communications of the ACM, v.15 n.7, p.579-585, July 1972

William S. Dorn, Editor's Preview…, ACM Computing Surveys (CSUR), v.2 n.2, p.83-87, June 1970

Igal Adiri, A Dynamic Time-Sharing Priority Queue, Journal of the ACM (JACM), v.18 n.4, p.603-610, Oct. 1971

Igal Adiri, A Note on Some Mathematical Models of Time-Sharing Systems, Journal of the ACM (JACM), v.18 n.4, p.611-615, Oct. 1971

Patricia L. Bennett , Derrell V. Foster, Formulation of a Markovian model of the major processing delays of the VUCC DECsystem-1099, Proceedings of the 17th annual Southeast regional conference, p.2-7, April 09-11, 1979, Orlando, Florida

Allan L. Scherr , David C. Larkin, Time-sharing for OS, Proceedings of the November 17-19, 1970, fall joint computer conference, November 17-19, 1970, Houston, Texas

Peter J. Denning, Principles of computer system organization, ACM SIGCSE Bulletin, v.2 n.3, p.45-55, November 1970

Thomas E. Reeves , Udo W. Pooch, A multiple subsystem simulator of processor scheduling, Proceedings of the 3rd symposium on Simulation of computer systems, p.129-138, August 12-14, 1975, Boulder, Colorado, United States

T. C. Pewitt , S. Y. W. Su, Resource demanded paging and dispatching to optimize resource utilization in an operating system, Proceeding of the 1973 ACM SIGME symposium, p.29-36, January 1973

Forest Baskett, The dependence of computer system queues upon processing time distribution and central processor scheduling, ACM SIGOPS Operating Systems Review, v.6 n.1/2, June 1972

A. L. Dudick , C. D. Pack, Round robin scheduling in a computer communications system with finite swap time and statistically multiplexed arrivals, Proceedings of the ACM second symposium on Problems in the optimizations of data communications systems, p.58-64, January 1971

Peter J. Denning, Principles of computer system organization, Proceedings of the first SIGCSE technical symposium on Education in computer science, p.45-55, January 1970

Don R. Rice, An analytical model for computer system performance evaluation, ACM SIGMETRICS Performance Evaluation Review, v.2 n.2, p.14-30, June 1973

Dileep P. Bhandarkar, A practical application of memory interference models, ACM SIGMETRICS Performance Evaluation Review, v.4 n.2, p.33-39, April 1975

S. F. Yashkov , A. S. Yashkova, Processor sharing: A survey of the mathematical theory, Automation and Remote Control, v.68 n.9, p.1662-1731, September 2007

James W. McGuffee , R. Andrew Cabezas, Starvation-proof priority round-robin queues for time-sharing systems, Journal of Computing Sciences in Colleges, v.21 n.4, p.253-258, April 2006

David Petrou , John W. Milford , Garth A. Gibson, Implementing lottery scheduling: matching the specializations in traditional schedulers, Proceedings of the Annual Technical Conference on 1999 USENIX Annual Technical Conference, p.1-1, June 06-11, 1999, Monterey, California

S. Haldar , D. K. Subramanian, Fairness in processor scheduling in time sharing systems, ACM SIGOPS Operating Systems Review, v.25 n.1, p.4-18, Jan. 1991

M. Naderi, Modelling and performance evaluation of multiprocessors, organizations with multi-memory units, ACM SIGARCH Computer Architecture News, v.16 n.5, p.35-51, Dec. 1988

Misja Nuyens , Adam Wierman, The Foreground-Background queue: A survey, Performance Evaluation, v.65 n.3-4, p.286-307, March, 2008

G. Estrin , R. R. Muntz , R. C. Uzgalis, Modeling, measurement and computer power, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada

Stephen R. Kimbleton, Core complement policies for memory allocation and analysis, Proceedings of the December 5-7, 1972, fall joint computer conference, part II, December 05-07, 1972, Anaheim, California

Leonard Kleinrock, A contiuum of time-sharing scheduling algorithms, Proceedings of the May 5-7, 1970, spring joint computer conference, May 05-07, 1970, Atlantic City, New Jersey

Stephen R. Kimbleton, Performance evaluation: a structured approach, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada

Gisaku Nakamura, A feedback queueing model for an interactive computer system, Proceedings of the May 16-18, 1972, spring joint computer conference, May 16-18, 1972, Atlantic City, New Jersey

M. A. Sencer , C. L. Sheng, An analysis of multiprogrammed time-sharing computer systems, Proceedings of the June 4-8, 1973, national computer conference and exposition, June 04-08, 1973, New York, New York

J. P. Buzen , P. S. Goldberg, Guidelines for the use of infinite source queueing models in the analysis of computer system performance, Proceedings of the May 6-10, 1974, national computer conference and exposition, May 06-10, 1974, Chicago, Illinois