When the parameter of job with hard deadline are known before the system begins the execution then the static schedules of jobs can be developed at offline and processor time allocated to a jobs is equal to its maximum execution time.
The scheduler dispatches the jobs according to the static schedule and repeats the jobs in each hyper periods. The static schedule guarantees that each job completes by its deadline and no job overrun can occur.
Example:
Four independent periodic tasks: T1 = (4, 1), T2 = (5, 1.8), T3 = (20, 1), T4 = (20, 2) Utilization = 1/4 + 1.8/5 + 1/20 + 2/20 = 0.76
Hyperperiod = LCM (4, 5, 20, 20) = 20
According to this specification, schedules be generated as:
|
Time |
Release Job |
Running Job |
|
0 |
J11, J21, J31, J41 |
J11(T1) |
|
1 |
J21, J31,J41 |
J21(T2) |
|
2.8 |
J31, J41 |
J31(T3) |
|
3.8 |
J41 |
-------------- |
|
4 |
J12, J41 |
J12(T1) |
|
5 |
J13, J41 |
J22(T2) |
|
6.8 |
J41 |
------------------ |
|
8 |
J23, J41 |
J13(T1) |
|
9 |
J41 |
--------------------- |
|
10 |
J23,J41 |
J23(T2) |
|
11.8 |
J41 |
-------------------- |
|
12 |
J14, J41 |
J14(T1) |
|
13 |
J41 |
J41(T4) |
|
15 |
J24 |
----------------- |
|
16 |
J15,J24 |
J15(T1) |
|
17 |
J24 |
J24(T2) |
Corresponding static schedule be constructed as:
In this schedule T1 starts its execution at 0 time and repeats after each periods. Some intervals are not used by periodic task called as slack time. This adds the advantage since other a periodic jobs can be executed here.
Types of Clock Driven Schedules:
There are two types of clock driven schedules.
- Table Driven Scheduling
- Cyclic Schedule
1. Table Driven Scheduling:
Table driven schedulers usually pre-compute which task would run when and store this schedule in a table at the time the system is designed. Rather than automatic computation of schedule by the scheduler, the application programmer can be given the freedom to select his own schedule for the set of tasks in the application and store the schedule in a table (called schedule table) to be used by the scheduler at the run time.
An example of a schedule table is shown as following fig. There is difficult to implement the scheduling since the table becomes very large in case of large and complex system.
|
Tasks |
Start time in millisecond |
|
T1 |
0 |
|
T2 |
3 |
|
T3 |
10 |
|
T4 |
12 |
|
T5 |
17 |
Fig: Time Driven Scheduling
2. Cyclic Schedule:
Cyclic schedules are very popular and extensively used in industry. Cyclic schedules are simple, efficient and are easy to program. An example application where cyclic schedule is used, is a temperature controller. A temperature controller periodically samples the temperature of a room and maintains it at a preset value. Such temperature controllers are embedded in typical computer- controlled air conditioners.
|
Tasks |
Frame Number |
|
T3 |
F1 |
|
T1 |
F2 |
|
T3 |
F3 |
|
T4 |
F2 |
Fig. Example schedule table for cyclic scheduler
A cyclic scheduler repeats a pre-computed schedule. The pre-computed schedule needs to be stored only for one major cycle.