# Scheduling and Synchronization of Synergetic Tasks Processors And Or Manipulators or I/O Devices

Original Publication Date: 1974-Dec-01

Included in the Prior Art Database: 2005-Feb-28

## Publishing Venue

IBM

## Related People

## Abstract

This is a system for scheduling of tasks and synchronization of synergetic tasks. Here, task connotes an undertaking to be performed by a processor, and/or a manipulator or an I/O device. Scheduling Algorithm

**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 7__**Scheduling and Synchronization of Synergetic Tasks Processors And Or
Manipulators or I/O Devices **

This is a system for scheduling of tasks and synchronization of synergetic tasks. Here, task connotes an undertaking to be performed by a processor, and/or a manipulator or an I/O device. Scheduling Algorithm

Let S denote a scheduling system composed of a processor P and a scheduler S. Let the integer alpha epsilonA formally denote a task (viz. alpha = 2 denotes task 2, etc.). Let the integer sigma denote the system's status. Let a denote a string of tasks; that is, let a denote a vector a = (a(1), a(2),..., a(i),...) such that a(i)epsilonA biepsilonI. (a(i) is a task that belongs to set A; i is an integer). Suppose: (1) That there exists, at some time tau an iepsilonI for which alpha = a(i) holds. (2) That the execution of a task alpha updates sigma. Then, the scheduling of a new task alpha can be defined as follows: (1) Using the ordered doublet (i,sigma) the system extracts from schedule S (a matrix) a new value for i; that is, the system sets i equal to S(isigma) : i <-- S(isigma). (2) Using the new value i, the system sets alpha equal to a(i): alpha <-- a(i); and, hence, defines the new task to be task alpha.

The scheduler is schematically described in Fig. 1. The construction of a schedule (matrix S) and of its associated string of tasks (vector a) is illustrated by an example in Fig. 2.

Fig. 1a is a schematic description of the scheduler. Note that the scheduling operation consists of only two instructions. Fig. 1b is also a schematic description of a scheduler (cf. Fig. 2).

Fig. 2 is an illustration of how to construct the schedule (matrix S) and the task string (vector a) that correspond to a flow diagram (cf. Fig. 1b). Note 1: The scheduler is initiated by setting the doublet (i,sigma) equal to (1,1). Note 2: Suppose, for example, that the execution of task 3 (i = 3; alpha = a(3) = 3) yields sigma = 2, then, the scheduling of the next task is done as follows:

(Image Omitted)

Hence, the next scheduled task is task 4. (cf. flow diagram and tables a and S
above). Note 3: The symbol X formally denotes EXIT FROM SCHEDULER. X
may be chosen to be a positive integer equal to the dimension f vector a plus 1; a

(X)may be defined as a task that disconnects (logically or physically) the
scheduler from the comparator. Synchronization Algorithm

Let S and S' denote two scheduling systems each composed of a processor (P and P') and a scheduler (S and S'). Let A and A' denote two sets of tasks. Let alpha epsilon A and alpha'epsilonA'. Suppose, also, that task alpha executes on system S and that task alpha' executes on system S'. Let integers sigma and sigma' denote the statuses of systems S and S', respectively. Let a and a' denote strings of tasks; more specifically, let a = (a(1), a(2),..., a(i),...) and a' = (a'(1), a'(2),..., a'(i),...) satisfy the conditions:

(Image Omitted)

1

__Page 2 of 7__Furthermore, let t and t' denote two "synchroniza...