Module 2 Lecture 6 hrs.

Clock-Driven Scheduling: Static, Time-Driven scheduler, General structure of Cyclic

Schedules, Cyclic Executives, Improving the Average Response Time Of Aperiodic
Jobs, Scheduling Sporadic Jobs.

Clock- Driven Scheduling:

The clock-driven schedulers are those in which the scheduling points are determined by the
interrupts received from a clock. In the event-driven ones, the scheduling points are defined
by certain events which precludes clock interrupts. Clock driven scheduling has an ability to
consider complex dependencies, communication delays, and resource contention among jobs
when constructing the static schedule, guaranteeing absence of deadlocks and unpredictable
delays. Entire schedule is captured in a static table. Different operating modes can be
represented by different tables. No concurrency control or synchronization required. If
completion time jitter requirements exist, it can be captured in the schedule. In this unit, we
will discuss the concept of clock driven system.

In CDS, we use the foloowing notation and assumptions-

Clock-driven approach is appropriate only when the system is deterministic, excluding a few
aperiodic and sporadic jobs. The restricted assumptions are:

a. There are n periodic tasks in the system; n is fixed in an operation mode.

b. The parameters of all periodic tasks are known a priori. Variations in the inter release times
of job in any periodic task are negligibly small i.e. each job in Ti is released pi units of time
after the previous job in Ti.
c. Each job Ji,k is ready for execution at its release time ri,k .
d. We refer to a periodic task Ti with phase Öi, period pi, execution time ei and relative
deadline Di by the 4-tuple (Öi, pi, ei, Di)
e. (1,10,3,6) means the first job in the task is released and ready at time 1 and must be
completed by time 7; second job is ready at 11 and must be completed by 17 and so on.
f. Each job executes for 3 units of time.
g. Default deadline of each job is its period and phase is 0.

There are aperiodic jobs released at unexpected time instants and there are no sporadic jobs .

Advantages and Disadvantages of Clock-Driven Scheduling

The advantages of clock-driven scheduling are discussed below:

a. Conceptual simplicity

a1. complex dependencies, communication delays, resource contentions can be

considered when developing the schedule
a2. no need for any synchronization mechanisms
a3. schedule can be represented as tables that is used by the scheduler at run time

b. Relatively easy to validate

b1. Because times when jobs execute are deterministic, the system will not exhibit anomalies
b2. Can prove scheduling feasibility by exhaustive simulation and testing
Disadvantages of clock-driven scheduling are discussed below:
a. Inflexible, since schedule is computed off-line, small changes mean that new tables
have to be generated.
b. Release times of jobs must be fixed
c. Priority-driven does not require this
d. A lot information about jobs has to be known beforehand, so that the schedule can be
precomputed.
e. Difficult to get acceptable response times for aperiodic (soft real-time) jobs.

Static, Time-Driven scheduler

Whenever the parameters of jobs with hard deadlines are known before the system begins tI
execute, a straightforward way to ensure that they meet their deadlines is to construct a static
schedule of the jobs off-line. This schedule specifies exactly when each job executes. In this
schedule, the amount of processor time allocated to every job is equal to its maximum
execution time, and every job completes by its deadline. Among all the feasible schedules,
we may want to choose one that is good according to some criteria (processor idles
periodically to accommodate aperiodic jobs).

Consider a system that contains four independent periodic tasks. They are T1 = (4,1), T2 =
(5,1.8), T3=(20,1) and T4 = (20,2). The utilizations are .25, .36, .05 and .01 , totalling .76 ,
We need to create a schedule for only first hyper period which is 20. A schedule is shown in
the figure given below.

Some intervals, such as (3.8, 4), (5, 6) and (10.8, 12) are not used by periodic tasks. We can
use these for executing aperiodic jobs.

A straight forward way to implement the scheduler is to store the precomputed schedule as a
table. Each entry (tk, T(tk)) in this table gives a decision time tk, which is an instant when a
scheduling decision has been made and T(tk) is the name of the task whose job starts at tk or
I. The scheduler timer is used. Immediately after all the tasks have been created and
initialized and then at every scheduling decision time, the scheduler, sets the timer so the
timer will expire and request an interrupt at the next decision time. Upon receiving a timer
interrupt at tk, the scheduler sets the timer to expire at tk+1 and prepares the task T(tk) for
execution. The scheduler then suspends itself, letting the task have processor and execute,
when the timer expires again the scheduler repeats its operation.

General structure of Cyclic Schedules

Cyclic schedules involve repeating a sequence of activities indefinitely, often used in

manufacturing, embedded systems, or compilers for scheduling loop operations. They are
 characterized by a periodic timer and a major cycle that divides time into frames, with each
task scheduled to execute within a frame.

Cyclic scheduling is used in various domains, including manufacturing, time-sharing of

processors in embedded systems, and compilers for scheduling loop operations for parallel
or pipelined architectures.
Some basic terminologies used in cyclic schedules are as follows-
 Periodic Timer:
Unlike table-driven schedulers, cyclic schedulers use a periodic timer that needs to be set only
once.
 Major Cycle:
The scheduling decision is made periodically, choosing which job to execute and performing
monitoring and enforcement operations.
 Frames:
Time is divided into equal-sized frames, and each job must be scheduled to execute entirely
within one frame.
 Frame Size:
The frame size (f) must be greater than or equal to the worst-case execution time of any task
(C).
 Hyperperiod (H):
The hyperperiod is the least common multiple of the periods of all tasks in the system.
 Scheduling Decisions:
The scheduler determines which task to execute within each frame, ensuring that all tasks meet
their deadlines.
 Cyclic Executive:
A cyclic executive is an alternative to a real-time operating system, using a form of cooperative
multitasking with a single task realized as an infinite loop.
 Aperiodic Jobs:
Aperiodic jobs, which are not part of the periodic schedule, are typically scheduled in the
background and their execution may be delayed.
Figure below shows a good structure of cyclic schedules.

A constraint enforced by this structure is that scheduling decisions are made periodically,
rather than at arbitrary times. The scheduling decision times partition the timeline into
intervals called frames. Each frame has length f which is the frame size. Scheduling decisions
are made only at the beginning of every frame so there is no preemption in a frame. Phase is
always a multiple of frame size. Scheduler also carries out monitoring and enforcement
actions at the beginning of each frame to check whether every job scheduled in the frame has
indeed been released and ready for execution.

Frame Size constraints:

 The frames should be sufficiently longs so that every job can start and complete its
execution within a frame (no preemption).
 Possible If we make the frame size f larger than the execution time of every task Ti
(Constraint 1).
 The frame size would be chosen so that it divides H. This condition is met if f divides the
period pi of at least one task Ti.
 (pi /f ) – pi/f = 0 for at least one i (Constraint 2). Thus there are an integer number of
frames in each hyperperiod.
 F is the number of frames in a hyperperiod.
 A hyperperiod that begins at the beginning of (kF+1)st frame, for any k =0,1… is called a
major cycle.
 To make it possible for the scheduler to determine whether every job completes by its
deadline, we want the frame size to be sufficiently small so that between the release time and
deadline of every job, there is at least one frame (Constraint 3).
 The figure below illustrates the suitable range of f for a task.
 When f is in this range, there is at least one frame between the release time and deadline
of every job in the task.
 Now, the figure given below constraints the frame size to be no less than 2. As hyper
period is 20; 2, 4, 5, 10 are possible frame sized.
 However only 2 satisfies (pi /f ) – pi/f = 0.
 If we have (15, 1, 14), (20, 2, 26), and (22, 3) we must have only 3, 4, 5.

The another term which is important here is Job Slices

At times the constraints cannot be met, for example, (4,1), (5,2,7), (20,5). For constraint 1 we
must have f>= 5 but for constraint 3 we must have f<=4. Now we are forced to partition each
job in a task that has a large execution time into slices (sub jobs) with smaller execution times
(IN message transmission, divide message into several segments, when job is computational
divide into non-preemptive procedures). Now the lower bound by constraint 1 has been
reduced.

Now we can divide each job in (20,5) into a chain of three slices with execution time 1,3,1.
So (20,5) now in fact is (20,1), (20,3), (20,1). Now we have 5 tasks and we can choose frame
size 4.
We have not chosen to decompose (20,5) into (20,3) and (20,2) as it would not be possible to
fit these tasks together with T1 and T2 in five frames of size 4. T1 must be scheduled in each
frame.

T2 must be scheduled in 4 out of 5 frames. This leaves one frame with 3 units of time for T3.
The other frames only have one unit of time left for T3.

We can schedule two subtasks each with 1 unit of execution time in these frames, but there is
not time in any frame for a subtask with execution time 2.

Cyclic Executives

The clock driven scheduler must be modified to accommodate the restriction that scheduling
decisions are made only at frame boundaries. The term cyclic executives refer to a scheduler
that deterministically interleaves and sequentializes the execution of periodic tasks on a CUP
according to a given cyclic schedule. It also makes scheduling decision only at the beginning
of each frame and deterministically interleaves the execution of periodic tasks.

However it allows aperiodic and sporadic jobs to use the time not used by periodic tasks. The
cyclic executives take over the processor and executes at each of the clock interrupts, which
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 period task server
(Not needed where periodic tasks never overrun, executive just executes the job slices) , and
lets the server execute the job slices in the current block. Upon the completion of the periodic
task server, the cyclic executive wakes ups the aperiodic jobs in the aperiodic job queue in
turn and allows them to use the remaining time in the frame.

The supposition here is that whenever the server or a job completes, the cyclic executives
wake up and executes. The system may also have an aperiodic task server, which when
awaked executes aperiodic jobs in the aperiodic job queue. In addition to scheduling, the
cyclic executive also checks for overruns at the beginning of each frame. If the last job
executed in the previous frame is not complete at that time, the cyclic executive preempts the
execution of the job if the last job is an aperiodic job. The job remains in the aperiodic job
queue and will be resumed whenever there is time again for aperiodic jobs.

If the cyclic executive finds the periodic task server still executing at the time of a clock
interrupt, a frame overrun occurs. After checking for overruns, the cyclic executive makes
sure that all the job slices scheduled in the current block are ready for execution and then
wakes up the periodic task server to execute them. If there is still time after all the slices in
the current block are completed and the aperiodic job queues is nonempty, it lets the job at
the head of the aperiodic job queue execute.

Improving the Average Response Time of Aperiodic Jobs

There is no advantage to complete a job before its hard deadline. So far the jobs are
scheduled in the background after all the jobs slices with hard deadlines scheduled in each
frame are completed. Strategy of delaying aperiodic jobs is not a good one if hard deadlines
are competing early. The sooner the aperiodic jobs complete, the more responsive the system
is.

One way is to execute aperiodic jobs ahead of the periodic jobs whenever possible. This
approach is called slack stealing. For this scheme to work, every periodic job slice must be
scheduled in a frame that ends no later than its deadline.

Let the total amount of time allocated to all the slices scheduled in the frame k be xk. The
slack time available in the frame is equal to f – xk at the beginning of the frame. If the
aperiodic job queue is nonempty at this time, the cycle 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-xk –
y. The cyclic executive can let aperiodic jobs execute in frame k as long as there is slack.

When the cyclic executive finds the aperiodic job queue empty, it lest the periodic task server
execute the next slice in the current block. The amount of slack remains the same during this
execution.

Example of slack stealing is discussed below:

a. T1= (3, 1); T2= (10, 4): RM scheduled; + aperiodic job A:r = 0.1 , e = 2.1
b. The initial amount of sack in each frame can be pre-computed along with the cyclic
schedule
and stored in the table defining the schedule.
c. It is necessary for the cyclic executive to keep track of the amount of available slack
and update this amount as it consumes the slack.
d. This can be done using an interval timer.
e. At the beginning of each frame, the cyclic executive sets the timer to the value of the
initial slack in the frame.
f. The timer counts down whenever an aperiodic job executes ahead of any slice in the
current block.
g. When the timer expires, indicating that there is no more slack, the cyclic executive
preempts the executing aperiodic job and lets the execution of the next job slice in the current
block begin.
h. Most operating systems do not offer interval timers of sub-millisecond granularity and
accuracy.
i. This scheme is practical only when the temporal parameters of periodic tasks are in
orders of hundreds of milliseconds or seconds.
Scheduling Sporadic Jobs

Sporadic jobs have hard deadlines. Their minimum release times and maximum execution
times are unknown. It is impossible to guarantee a priori that all sporadic jobs can complete
in time.

Acceptance Test:
S1: A common way to deal with this situation is to have the scheduler perform an acceptance test
when each sporadic job is released.
S2: During an 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.
S3: A job in the system, we mean either a periodic job, for which time has already been
allocated in the precomputed cyclic schedule, or a sporadic job which has been scheduled but
not yet completed.
S4: According to the existing schedule, If there is a sufficient amount of time in the frames
before its deadline to complete the newly released sporadic job without causing any job in the
system to complete too late, the scheduler accepts and schedules the job. Otherwise, the scheduler
rejects the new sporadic job.
S5: By rejecting a sporadic job that cannot be scheduled to complete in time immediately after
the job is released, the scheduler gives the application system as much time as there is to take any
necessary recovery action.
Example: A quality control system.
o A sporadic job that activates a robotic arm is released when a defective part is detected.
o The arm, when activated, removes the part from the conveyor belt. This job must complete
before the part moves beyond the reach of the arm.
o When the job cannot be scheduled to complete in time, it is better for the system to have this
information as soon as possible.

System can slow down the belt, stop the belt, or alert an operator to manually remove the part.
o Otherwise, if the sporadic job were scheduled but completed too late, its lateness would not be
detected until its deadline. By the time the system attempts a recovery action, the defective part
may already have been packed for shipment.
 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.
 Therefore, 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.
 We also assume that all sporadic jobs are preemptable. Therefore, each sporadic job can
execute in more than one frame if no frame has a sufficient amount of time to accommodate the
entire job.
 Conceptually, it is quite simple to do an acceptance test.
 Let us suppose that at the beginning of frame t , an acceptance test is done on a sporadic job
S(d, e), with deadline d and (maximum) execution time e.
 Suppose that the deadline d of S is in frame l+1 (i.e., frame l ends before d but frame l+1 ends
after d) and l ≥ t .
 Clearly, the job must be scheduled in the lth or earlier frames.
 The job can complete in time only if the current (total) amount of slack time σc(t, l) in frames
t,t+1, . . . l is equal to or greater than its execution time e. Therefore, the scheduler should reject S
if e > σc(t, l).
 The scheduler accepts the new job S(d, e) only if e ≤ σc(t, l) and no sporadic jobs in system are
adversely affected.
 More than one sporadic job may be waiting to be tested at the same time.
 A good way to order them is on the Earliest-Deadline-First (EDF) basis.
 Newly released sporadic jobs are placed in a waiting queue ordered in non decreasing order of
their deadlines: the earlier the deadline, the earlier in the queue.
 The scheduler always tests the job at the head of the queue and removes the job from the
waiting queue after scheduling it or rejecting it.

EDF Scheduling of the Accepted Jobs: Earliest deadline first (EDF) is dynamic priority
scheduling algorithm for real time systems. Earliest deadline first selects a task according to its
deadline such that a task with earliest deadline has higher priority than others
 The EDF algorithm is a good way to schedule accepted sporadic jobs.
 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 the 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.

An example of EDF is given below for task set of table.

Task Release Execution Deadline (Di) Time

time(ri) Time(Ci) Period(Ti)

T1 0 1 4 4
T2 0 2 6 6
T3 0 3 8 8

U= 1/4 +2/6 +3/8 = 0.25 + 0.333 +0.375 = 0.95 = 95%

As processor utilization is less than 1 or 100% so task set is surely schedulable by EDF.
 Figure-Earliest deadline first scheduling of task set in Table

At t=0 all the tasks are released, but priorities are decided according to their absolute
deadlines so T1 has higher priority as its deadline is 4 earlier than T2 whose deadline is 6 and
T3 whose deadline is 8, that’s why it executes first.

At t=1 again absolute deadlines are compared and T2 has shorter deadline so it executes and
after that T3 starts execution but at t=4 T1 comes in the system and deadlines are compared,
at this instant both T1 and T3 has same deadlines so ties are broken randomly so we continue
to execute T3.

At t=6 T2 is released, now deadline of T1 is earliest than T2 so it starts execution and after
that T2 begins to execute. At t=8 again T1 and T2 have same deadlines i.e. t=16, so ties are
broken randomly an T2 continues its execution and then T1 completes. Now at t=12 T1 and
T2 come in the system simultaneously so by comparing absolute deadlines, T1 and T2 has
same deadlines therefore ties broken randomly and we continue to execute T3.

At t=13 T1 begins it execution and ends at t=14. Now T2 is the only task in the system so it
completes it execution.

At t=16 T1 and T2 are released together, priorities are decided according to absolute
deadlines so T1 execute first as its deadline is t=20 and T3’s deadline is t=[Link] T1
completion T3 starts and reaches at t=17 where T2 comes in the system now by deadline
comparison both have same deadline t=24 so ties broken randomly ant we T continue to
execute T3.

At t=20 both T1 and T2 are in the system and both have same deadline t=24 so again ties
broken randomly and T2 executes. After that T1 completes it execution. In the same way
system continue to run without any problem by following EDF algorithm.

***