Browse Prior Art Database

Time Map Scheduling

IP.com Disclosure Number: IPCOM000079298D
Original Publication Date: 1973-Jun-01
Included in the Prior Art Database: 2005-Feb-26

Publishing Venue

IBM

Related People

Kelley, WJ: AUTHOR

Abstract

In computer systems which initiate and coordinate many activities, the need is evident for processing resources to be scheduled in a more efficiency manner than simply allowing one activity to preempt another. There will still exist a need to respond to unplanned interrupts; however, for those types of events which can be preplanned, greater processor utilization can be realized. Activities to be scheduled are classified as: (1) Time dependent cyclic. (2) Time dependent noncyclic, and, (3) Nontime dependent.

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 24% of the total text.

Page 1 of 10

Time Map Scheduling

In computer systems which initiate and coordinate many activities, the need is evident for processing resources to be scheduled in a more efficiency manner than simply allowing one activity to preempt another. There will still exist a need to respond to unplanned interrupts; however, for those types of events which can be preplanned, greater processor utilization can be realized. Activities to be scheduled are classified as: (1) Time dependent cyclic. (2) Time dependent noncyclic, and, (3) Nontime dependent.

Such scheduling requirements as polling of teleprocessing lines, transferring data over an I/O (input/output) interface in blocks, or allowing a program to execute according to a desired rate, are all examples of cyclic activities whose use of a processor can be preplanned. The scheduling of an activity to start at some specific time in the future or the delay of an activity for a specified period, are time dependent but noncyclic. Nontime dependent activities are the normal class of tasks which are run whenever processor time is available.

A scheduling/dispatching technique is being presented which will satisfy all time-dependent requirements, equally, not just those having highest priority. The basic mechanism is a sequence of steps executed by a hardware (or microcoded) Timer Routine running asynchronously with one or more main processors (CPUs) and I/O processors. The primary function of this Timer Routine is to step through a sequence of commands, a Time Map, and respond to Whatever action has been scheduled. This action may range from doing nothing, except setting the timer to go to the next command dt units from now, initiating a trivial I/O "program" without interrupting the main processor, or actually interrupting a processor by performing a task switch. The logic of the Timer Routine is described in Fig. 1. The routine is entered every dt units of time; however, it does not interrupt a main processor unless it must initiate a new activity. The activity the main processor is currently executing is kept in a hardware register called CURRENT ID. Whenever a state change is made, the ID in this register is used to index into a Scheduling Requirements Table SRT (Fig. 2). The current ID register, as well as the Time Map and SRT, are protected by the hardware system and cannot be accessed by a program running on the main processor, except through special instructions or restricted programs.

The Time Map is an array of time slots. Each slot contains a 2-byte action field for each processor. Each action field has an action code (C=2 bits) and an index field (ID=14 bits). See Fig. 2. The action code is interpreted as follows: 00 - set time and increment index only 01 - reset index or initiate I/O "program" 10 - task switch required (change activity).

ID is a unique identifier that distinguishes the various activities being dispatched. The activity associated with the ID is to be invoked whenever a slot cont...