Browse Prior Art Database

Method of Scheduling of Processing and Response Time

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

Publishing Venue

IBM

Related People

Brown, DT: AUTHOR [+3]

Abstract

A task is the performance of some function through execution of a sequence of instructions. Execution of instructions is called processing (P). The units of P are normalized instructions. A normalized instruction represents some amount of CPU time. It is said that P is given to a task in order to perform the task.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 27% of the total text.

Page 1 of 4

Method of Scheduling of Processing and Response Time

A task is the performance of some function through execution of a sequence of instructions. Execution of instructions is called processing (P). The units of P are normalized instructions. A normalized instruction represents some amount of CPU time. It is said that P is given to a task in order to perform the task.

A task is said to be created when the need to perform the task is first recognized by a supervisory program. The time from when a task is created until when the task is complete is called the response time (RT) of the task. The units of RT are seconds.

Described is a method by which 1) the P and RT requirements of a task can be described in a natural way to the supervisory program, and 2) the supervisory program can cause P to be given to many concurrently existing tasks so as to satisfy P and RT requirements in a predictable and equitable manner.

P is given to a task at a rate called processing rate (V). The units of V are normalized instructions per second.

P is given to a task when the task is in the dispatched state and it is not given when the task is in the nondispatched state. Thus, the instantaneous V distributed to a task has either a nonzero value or a zero value. The P given to a task during a period of time is the instantaneous V distributed to the task, integrated over that period of time.

Two parameters are input to the supervisory program to describe the requirements of a task. These are: Requested V (Vr), which is the average V that should be distributed to the task. Requested granularity period (Gr), which is the amount of time during which an amount of P, Pr, should be given to the task, where Pr = VrGr.

The sum of the Vr's for all concurrently existing tasks may be less than, equal to, or greater than the available V (Vavail) of the computer (or computers, in a multiprocessing system). Thus: Sum of Vr's for all tasks = kVavail. where k is a numeric factor less than, equal to, or greater than one.

The supervisory program causes the computer to distribute to each task a distributed V (Vd) during a distributed granularity period (d). The Vd and Gd for a task are defined in terms of the Vr and Gr for the task, as follows: Vd = Vr/k; Gd = kGr Therefore, for the task: VdGd = VrGr = Pr

Distribution of V to tasks in accordance with the parameters Vd and Gd is called proportional distribution. (Note that if Gd were defined to be equal to Gr instead of kGr, the supervisory program would, under conditions of ever- increasing load and ever-decreasing Vd's, cause ever-decreasing amounts of P to be given to tasks during their Gd's. This would result in spending an ever- increasing part of Vavail on dispatching overhead.)

1

Page 2 of 4

The Gd for a task is the minimum period of time for which the supervisory program will attempt to ensure that P is given to the task at the rate Vd. During a period of time shorter than Gd, zero P may be given to the task.

The nonzer...