Work-Scheduling Algorithms: A Nonprobabilistic Queuing Study (with Possible Application to No. 1 ESS)

In many large computer systems, especially those with real-time use, the central processor handles much of its work through queues, which contain work requests. (The queues may also be called hoppers, buffers, waiting lines, files, and so forth. In this paper we call them hoppers.) The processor examines each hopper in turn, and performs some or all of the work requests if any, which it finds there. Some work requests require processing more urgently than others. One method of providing appropriate response times is to examine more frequently hoppers which contain urgent work, and other hoppers less frequently. For example, the No. 1 ESS (Electronic Switching 2963 2964 T H E BELL SYSTEM TECHNICAL JOURNAL, NOVEMBER 1969 System) has many hoppers which it groups into five different urgency classes.1,2 The five classes are examined (or "visited") in a fixed recurring cycle, of length 30, during which the classes are visited 15, 8, 4, 2, and 1 times, respectively. (During a single visit to a single class, the individual hoppers are visited once each, in a fixed sequence.) This paper contains a practical approximate model for evaluating various alternative cycles. The conceptual basis for the evaluation is the expected time each work request must wait in the hopper before being serviced by the central processor. (Such times depend not only on the cycle, but also on the times required to process requests, and on the rates at which new requests are initiated. These are all assumed given.) The expected waiting times for different hoppers are multiplied by frequencies and also by weights w{ , the "average penalty per second of delay," and added.