Page 103 - DCAP608_REAL TIME SYSTEMS

Real Time Systems

Notes 10.2 Scheduling Sporadic Jobs

Like jobs in periodic tasks, sporadic jobs have hard deadlines. Their minimum release times and
maximum execution times are unknown a priori. It is impossible to guarantee a priori that all
sporadic jobs can complete in time. A common way to deal with this situation is to have the
scheduler perform an acceptance test when each sporadic job is released. During and acceptance
test, the scheduler checks whether the newly released sporadic job can be feasibly scheduled
with all the jobs in the system at the time. Here by a job we mean either a periodic job, for which
time has already been allocated or sporadic job, which has been scheduled but not yet completed.
If according to schedule, there is a sufficient amount of time in that frame s before its deadline to
complete the newly released sporadic job without causing any job in the systems to complete
too late, the scheduler accepts and schedules the job. Otherwise the sporadic job is rejected and
thus scheduler gives the application systems as much time as there is to take any necessary
recovery action. Consider a quality control system.
A sporadic job that activates robotic arm is released when a defective part is detected. The arm,
when activated, removes the part from the conveyor belt. Thus job must complete before the
part moves beyond the reach of the arm. When the job cannot be completed in time, it is better
for the system to have this information as soon as possible. The system can slow down the belt,
stop the belt, or alert an operator to manually remove the part. If it was late, its lateness could
only be detected at its deadline, if the recovery action is taken there, the defective item may
already have been packed. We assume that the maximum execution time of each sporadic job
becomes known upon its release. It is impossible for the scheduler to determine which sporadic
jobs to admit and which to reject unless this information is available.
So the scheduler must maintain information on the maximum execution times of all types of
sporadic jobs that the system may execute in response to the events it is required to handle.
Suppose at the beginning of frame t, an acceptance test is done on a sporadic job S(d,e). Suppose
that the deadline d of S is in frame l+1 (l ends before d and l+1 after d) and l>=t.

The job must be scheduled in the lth or earlier frames. The job can complete in time only if the
current amount of slack time in frames t,t+1,….,l is equal to or greater than its execution time e.
Therefore the scheduler should reject S if e > amount of slack.
The scheduler also has to check whether accepting a new job may cause some sporadic jobs in the
system to complete late.
The scheduler accepts the new job only if no sporadic jobs in system are adversely affected. As
there can be more than one sporadic job, a good way to order them is on the earliest Deadline
First (EDF) basis. The scheduler maintains a queue of accepted sporadic jobs in non-decreasing
order of their deadlines and inserts each newly accepted sporadic job into this queue in this
order. Whenever all slices of periodic tasks scheduled in each frame are completed, the cyclic
executive lets the jobs in the sporadic job queue execute in the order they appear in the queue.
The cyclic executive assumes that each newly released sporadic job is placed in a waiting queue
without the intervention of the scheduler. The scheduler allows aperiodic jobs to execute only
when the accepted sporadic job queue is empty. Whenever a server or job completes the cyclic
executive wakes up to execute. In the figure given on p. 99, the frame size used is 4.

The shaded boxes show where periodic tasks are scheduled. Suppose at time 3, a sporadic job S1
(17,4.5) is released. Acceptance test is done at time 4, when frame 2 begins. S1 must be scheduled
in frames 2, 3, 4 where total slack time is 4 thus S1 is rejected. At time 5, S2 (29,4) is released and
frame 3 to 7 end before its deadline. Acceptance test is done at time 8, as the total slack time is 5.5
so S2 is accepted. At time 11, S3 (22, 1.5) is released. The scheduler finds 2 units of slack time in
frames 4, 5. There is still enough slack to complete S2 event though S3 executes ahead of S2. So
scheduler accepts and executes this job in frame 4. At time 14, S4 (44, 5) is released.

98 LOVELY PROFESSIONAL UNIVERSITY