Browse Prior Art Database

Proportional Rate Scheduling Mechanism

IP.com Disclosure Number: IPCOM000088102D
Original Publication Date: 1977-Apr-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 4 page(s) / 52K

Publishing Venue

IBM

Related People

Brown, DT: AUTHOR [+2]

Abstract

Introduction. The scheduling mechanism described below provides a means of scheduling the execution of tasks on a computer system in such a way that the tasks receive processing at rates equal to or proportional to the rates that have been requested for the tasks. The requested rates are set externally, as by users of the system or by a system manager, possibly in conjunction with a supervisory program that monitors past system performance. The mechanism provides for scheduling adjustments when processing for a task is delayed due to contention for system resources or due to storage access delays (e.g., page faults in a system having virtual storage). These adjustments are designed to compensate for the delays and provide the correct average rate.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 37% of the total text.

Page 1 of 4

Proportional Rate Scheduling Mechanism

Introduction. The scheduling mechanism described below provides a means of scheduling the execution of tasks on a computer system in such a way that the tasks receive processing at rates equal to or proportional to the rates that have been requested for the tasks. The requested rates are set externally, as by users of the system or by a system manager, possibly in conjunction with a supervisory program that monitors past system performance. The mechanism provides for scheduling adjustments when processing for a task is delayed due to contention for system resources or due to storage access delays (e.g., page faults in a system having virtual storage). These adjustments are designed to compensate for the delays and provide the correct average rate.

An important aspect of the mechanism is that it controls scheduling adjustments so that compensation for delay occurs in a gradual manner: processing of other tasks is not unduly disrupted when one task is receiving extra processing to compensate for delay.

Processing is the execution of instructions by a processing unit (PU) of a computer system, and a task is the performance of some function through the execution of a sequence of instructions. For a given PU, processing is proportional to time spent executing instructions on the PU. A collection of tasks using a computer system may have different requirements for the rate at which they receive processing. Because they share (take turns using) the PU or PUs, the processing rate received by each task will, in general, be less than that delivered by a PU.

By scheduling the tasks on the PU or PUs, the rates given to the tasks can be controlled, subject to the limit of the total rate the PU or PUs can deliver. The scheduling mechanism attempts to deliver the requested rate for each task. If not enough rate is available, or if additional rate is available, rate is delivered to each task in proportion to its requested rate. Relationship to Dispatcher.

The scheduling mechanism described here is assumed to be part of a larger mechanism that supervises the execution of tasks. The scheduling mechanism provides proportional rate distribution among tasks by selecting tasks to compete for processing under control of a dispatching mechanism or dispatcher.

The scheduling mechanism selects a task to receive a fixed quantity of processing (P) and then gives control of the task to the dispatcher. After processing is complete, control returns to the scheduling mechanism. In general, the dispatcher will have control of several tasks at any time and will share the PU or PUs among them in a way that maximizes the total processing that is done. This may be accomplished through various priority mechanisms and through time-slicing or through preemption of the PU by higher priority tasks. Tasks that are delayed while waiting for resources remain under control of the dispatcher.

Thus, it can be seen that there are two levels...