The arbitrary driven cyclic schedules are flexible but they are inefficient. They depends on accurate time interrupt based on execution time of task and they also have high scheduling overloads. Hence the clock driven scheduling are implemented by using structural approach rather than tabular approach.

Fig: General Structure of a cyclic schedule

The total scheduling time are divided into number of time intervals called frames. Every frame has length f called frame size. Scheduling decision are made only at the beginning of frame and there is no preemption with in each frame. The phase of the each periodic task is a positive integer multiple of frame size. The first job of every task is released at beginning of frame and φ = k⋅f. This approach provides two major benefits:

  • Scheduler can easily check for overruns and missed deadlines at the end of each
  • Can use a periodic clock interrupt, rather than programmable timer?

Frame Size Constraints:

This constraint explains how to choose frame length in cyclic scheduling. To avoid preemption, want jobs to start and complete execution within a single frame:

f ≥ max(e1, e2, …, en)            ………………                                    (Eq.1)

To minimize the number of entries in the cyclic schedule, the hyper-period should be an integer multiple of the frame size (⇒ f divides evenly into the period of at least one task)

∃ i : mod(pi, f ) = 0.............................................................................. (Eq.2)

To allow scheduler to check that jobs complete by their deadline, should be at least one frame boundary between release time of a job and its deadline:

2*f – gcd(pi, f ) ≤ Di for i = 1, 2, …, n…......................................................... (Eq.3)

All 3 constraints should be satisfied.

Frame Size Constraints – Example: 

Given tasks are T1 = (4, 1.0), T2 = (5, 1.8) T3 = (20, 1.0), T4 = (20, 2.0).

Hyper-period H = lcm (4, 5, 20, 20) = 20

Constraints: Eq.1 ⇒ f ≥ max (1, 1.8, 1, 2) ≥ 2

Eq.2 ⇒ f ∈ { 2, 4, 5, 10, 20 }

Eq.3 ⇒ 2f - gcd( 4, f ) ≤ 4      (T1)

2f - gcd( 5, f ) ≤ 5                   (T2)

2f - gcd(20, f ) ≤ 20                (T3, T4)

These all constraints are satisfied by f = 2 only so required frame size = 2.

Job Slices:

Sometimes, a system cannot meet all three frame size constraints simultaneously. At this situation we can often solve by partitioning a job with large execution time into slices (sub-jobs) with shorter execution times/deadlines then these slices are called job slices.

Consider a system with three independent task

T1 = (4, 1), T2 = (5, 2, 7), T3 = (20, 5)

Condition 1 è f ≥ 5

Condition 2 è 2, 4, 5, 10, 20

Condition 3 è 2f – gcd(Pi, f) ≤4,  ≤7 ,≤ 20

From condition 1 we must have f≥ 5 but to satisfy condition 3 we must have f ≤ 4.

In above example, we can divide each job in (20, 5) into a chain of three slices with execution time 1, 3 and 1 respectively as (20, 1), (20, 3), (20, 1). The time schedule be generated as,

Sometimes need to partition jobs more slices than required by frame size constraints to yield a feasible schedule. To construct a cyclic schedule, we need to make 3 kinds of design constraints:

  • Chose a frame size based on constraints
  • Partition jobs into jobs
  • Places slices in frames

Slack Stealing:

A natural way to improve the response times of aperiodic jobs is by executing the aperiodic jobs ahead of the periodic jobs whenever possible. This approach, called slack stealing. Every periodic jobs slice must be scheduled in a frame that ends no later than its deadline. When aperiodic job executes ahead of slice of periodic task then it consumes the slack in the frame. It reduce the response time of aperiodic jobs but requires accurate timer.

For example:

Consider a system with

  • Three periodic tasks T1 (4, 1), T2 (5, 2), and T3 (8, 10, 1)
  • Three aperiodic tasks A1 (4, 5), A2 (9.5, 0.5), and A3 (10.5, 2)

Now major cycle in the cyclic schedule of the periodic tasks is:

This shows that the slack time be available at 3 to 4, 10 to 12, 15 to 16 and 18 to 20 where aperiodic task can be executed. The aperiodic task for execution shown as below:

When the aperiodic jobs execute by use of the cyclic executive such that

  • Job A1 can executed in idle period starting at 7 and preempted at Similarly resumed at 10 and executed at 10.5.
  • At time 10.5 A2 starts its execution and finished at Similarly A3 starts its execution at time 11 and preempted at 12.
  • Job A3 is resumed on slack starts at 15 and executed at 16.

Now the schedule be constructed as:

Here,

Response time of A1 = 6.5 Response time for A2 = 1.5 Response time for A3 = 5.5 Average response time = 4.5

If the cyclic executive does slack stealing such that,

  • At time between 4 and 8 there is the slack of 1 such that A1 can be executed at time 4 and preempted at 5.
  • At time between 8 to 12 there exists the slack of 2 such that A1 can resumed up to 5 and A2 can execute between 9.5 to 10. Similarly A3 can execute between 11 to12 and preempted.
  • At time between 12 and 16 there exists the slack of 1 and task A3 can resumed on 12and executed at 13.

Now the schedule can be generated as:

Here,

Response time of A1 = 4.5 Response time for A2 = 0.5

Response time for A3 = 2.5 Average response time = 2.5

This shows that the average response time is improved if slack stealing approach is used.