Page 94 - DCAP608_REAL TIME SYSTEMS

Unit 9: Concept of Clock-driven Scheduling

 Each job J is ready for execution at its release time r . Notes
i,k i,k
 We refer to a periodic task T with phase Ö , period p , execution time e and relative
i i i i
deadline D by the 4-tuple (Ö , p , e , D )
i i i i i
 (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.

 Each job executes for 3 units of time.
 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.

9.2 Static, Timer-Driven Schedules

Whenever the parameters of jobs with hard deadlines are known before the system begins t
i
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.

Figure 9.1: Scheduler

Source: ansari.szabist-isb.edu.pk/RTS/RTS0508.ppt
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 (t , T(t )) in this table gives a decision time t , which is an instant when a
k k k
scheduling decision has been made and T(t ) is the name of the task whose job starts at t or I. The
k k
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 t , the scheduler
k
sets the timer to expire at t and prepares the task T(t ) for execution. The scheduler then
k+1 k
suspends itself, letting the task have processor and execute, when the timer expires again the
scheduler repeats its operation.
Input: Stored schedule (t , T(t )) for k = 0,1,…N-1
k k
Task SCHEDULER:
See the next decision point i and table entry k to 0;
set the timer to expire at t
k
do forever

LOVELY PROFESSIONAL UNIVERSITY 89