Cyclic Executives

CYCLIC EXECUTIVES

Cyclic executive approach is a way of modifying the cock driven scheduler to accommodate the restrictions that the scheduling decisions are made only at frame boundaries.

Cyclic executive is used to mean a table-driven cyclic scheduler for all types of jobs in a multithreaded system. It makes scheduling decisions only at the beginning of each frame and deterministically interleaves the execution of periodic tasks. However, it also allows aperiodic and sporadic jobs to use the time that are not used by periodic tasks.

The cyclic executive executes at each of the clock interrupts after taking over the processor. The clock interrupts occur at the beginning of frames. When it executes, the cyclic executive copies the table entry for the current frame into the current block. It then wakes up a job, called periodic task server, and lets the server execute the job slices in the current block. Upon the completion of the periodic task server, the cyclic executive wakes up the aperiodic jobs in the aperiodic job queue in turn and allows them to use the remaining time in the frame. Here, it is assumed that the cyclic executive wakes up and executes whenever a job/server completes.

The cyclic executives also check for overruns at the beginning of the each frame and takes and appropriate way of handling these frame overruns. The two assumptions for cyclic executive are:

• the existence of timer and,
• each timer interrupt is handled by the cyclic executive within a bounded amount of delay

IMPROVING THE RESPONSE TIME OF APERIODIC JOB.

The sooner an aperiodic job completes, the more responsive the system is. For this reason, minimizing the response time of each aperiodic job or the average response time of all the aperiodic jobs is typically one of the design goals of real-time schedulers.

Slack stealing

Slack stealing was originally proposed for the priority driven systems. Slack stealing approach a way of improving the response time of aperiodic jobs by executing the aperiodic jobs ahead of the periodic jobs whenever possible. Each periodic job slice must be scheduled in a frame that ends no later than its deadline for the slack stealing approach to work.

Let the total amount of time allocated to all the slices scheduled in the frame k be x_k. The slack time available in the frame is equal to f − x_k at the beginning of the frame. If the aperiodic job queue is nonempty at this time, the cyclic executive can let aperiodic jobs execute for this amount of time without causing any job to miss its deadline. When an aperiodic job executes ahead of slices of periodic tasks, it consumes the slack in the frame. After y units of slack time are used by aperiodic jobs, the available slack is reduced to f −x_k −y. The cyclic executive can let aperiodic jobs execute in frame k as long as there is slack, i.e., the available slack f −x_k −y in the frame is larger than 0.

When the cyclic executive ï¬Ânds the aperiodic job queue empty, it lets the periodic task server execute the next slice in the current block. The amount of slack remains the same during this execution. The cyclic executive returns to examine the aperiodic job queue after each slice completes as long as there is slack. (Liu 92-93)

Execution of sporadic jobs (Acceptance Test)

The sporadic jobs have hard deadlines, release time and execution time that are not known a priori. Therefore, a clock driven scheduler cannot guarantee a priori the sporadic jobs complete in time. However, the scheduler can determine whether a sporadic job is schedulable when it arrives using acceptance test. The acceptance test is performed to check whether the newly release sporadic job can be feasibly schedulable in the presence of all the jobs in the system at that time.

If the time is sufficient, slack time in the frames before the deadline of new job, the new sporadic job is accepted, otherwise, it is rejected. If more than one sporadic jobs arrive at once then these should be queued for acceptance in EDF order.

Consider the following example.

EDF algorithm can be used to schedule the accepted sporadic jobs. For this, the scheduler maintains a queue of accepted sporadic job in non-decreasing order of their deadlines and inserts each newly accepted sporadic jobs into this queue in the same order. Whenever all the slices of sporadic task schedule in each frame are completed, the cyclic executive lets the job in sporadic job queue execute in the order. The aperiodic jobs are allowed to accept only when accepted sporadic job queue is empty.

Suppose,

1. At time T = 3, sporadic job S1 with deadline 17 and execution time 4.5 is released. The acceptance test for this job is performed at time T = 4. Therefore, it must be scheduled in the frame 2, 3, and 4 which is less than the execution time of S1. Therefore, the scheduler rejects this jobs.
2. At T = 5, job S2 with D = 29 and E = 4 is released. It can be executed in the frames 3 to 7. The acceptance test is performed at T = 8. The total amount of slack is 5.5 which is greater than the execution time E = 4. Therefore, the scheduler accepts this jobs and the first part of S2 with E = 2 executes in frame 3.
3. At T = 14, job S3 with D = 22 and E = 2.5 releases. The acceptance test at T = 12 finds that 2 unit of slack is available in the frame 4 and 5 where S3 can be schedule because the deadline of S2 is later than S3.
4. At T = 14, S4 with D = 44 and E = 5 is released. At T = 16, the acceptance test is performed. The slack time available is 4.5 before D = 44. This slack time is less than the sporadic job S4 is rejected while the jobs S2 and S3 complete within their deadlines.

References

Liu, Jane W. S. Real Time Systems. Integre Technical Publishing Co., Inc, January 10, 2000. Print.