RELEASE TIMES, DEADLINES, AND TIMING CONSTRAINTS
The release time of a job is the instant of time at which the job becomes available for execution. The job can be scheduled and executed at any time at or after its release time whenever its data and control dependency conditions are met. As an example, we consider a system which monitors and controls several furnaces. After it is initialized and starts execution (say at time 0), the system samples and reads each temperature sensor every 100 msec and places the sampled readings in memory. It also computes the control law of each furnaceevery 100 msec in order to process the temperature readings and determine flow rates of fuel, air, and coolant. Suppose that the system begins the first control-law computation at time 20 msec. The fact that the control law is computed periodically can be stated in terms of release times of the control-law computation jobs J0, J1, . . . , Jk, . . . . The release time of the job Jk in this job stream is 20 k × 100 msec, for k = 0, 1, . . . . We say that jobs have no release time if all the jobs are released when the system begins execution.
The deadline of a job is the instant of time by which its execution is required to be completed. Suppose that in the previous example, each control-law computation job must complete by the release time of the subsequent job. Then, their deadlines are 120 msec, 220 msec, and so on, respectively. Alternatively, if the control-law computation jobs must complete sooner, their deadlines may be 70 msec, 170 msec, and so on. We say that a job has no deadline if its deadline is at infinity.
In this example, as in many others, it is more natural to state the timing requirement of a job in terms of its response time, that is, the length of time from the release time of the job to the instant when it completes. We call the maximum allowable response time of a job its relative deadline. Hence the relative deadline of every control-law computation job mentioned above is 100 or 50 msec. The deadline of a job, sometimes called its absolute deadline, is equal to its release time plus its relative deadline.
In general, we call a constraint imposed on the timing behavior of a job a timing constraint. In its simplest form, a timing constraint of a job can be specified in terms of its release time and relative or absolute deadlines, as illustrated by the above example. Some complex timing constraints cannot be specified conveniently in terms of release times and deadlines. We will discuss the parameters needed to specify those constraints when they arise, but in most of this book, we are concerned primarily with this simple form.
