Offline scheduling is taking a scheduling decision at the compile time. In offline scheduling, decisions are made prior to the running of the system. A table is generated that contains the necessary scheduling decisions for use during the run time. Clock-driven scheduling is a type of off-line scheduling which is described in brief with the example below.

I. Clock-Driven: cyclic Scheduling (Static Scheduling)

The Clock-driven scheduling also called as static or offline scheduling. In this type of scheduling, decisions are taken previously at chosen time instance. The schedule is pre-computed off-line and store for use at run time. Clock-driven schedulers make their scheduling decisions regarding which task to run next only at the clock interrupt points.

The Clock-driven schedulers are those for which the scheduling points are determined by timer interrupts. The Clock-driven schedulers are also called off-line schedulers because these schedulers fix the schedule before the system starts to run. That is, the scheduler pre-determines which task will run when. Therefore, these schedulers incur very little run time overhead. However, a prominent shortcoming of this class of schedulers is that they cannot satisfactorily handle aperiodic and sporadic tasks since the exact time of occurrence of these tasks cannot be predicted. For this reason, this type of schedulers is also called the static scheduler.

Clock-driven scheduling are categorized into two types,

i. Table-driven

ii. Cyclic

Cyclic schedulers are very popular and are being extensively used in the industry. A large majority of all small embedded applications being manufactured presently are based on cyclic schedulers.

Cyclic schedulers are simple, efficient, and are easy to program. An example application where a cyclic scheduler is normally 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.

A cyclic scheduler repeats a pre-computed schedule. The pre-computed schedule needs to be stored only for one major cycle. Each task in the task set to be scheduled repeats identically in every major cycle. The major cycle is divided into one or more minor cycles (see Fig. above). Each minor cycle is also sometimes called a frame. In the example shown in the above figure, the major cycle has been divided into four minor cycles (frames). The scheduling points of a cyclic scheduler occur at frame boundaries. This means that a task can start executing only at the beginning of a frame.

The frame boundaries are defined through the interrupts generated by a periodic timer. Each task is assigned to run in one or more frames. The assignment of tasks to frames is stored in a schedule table. An example schedule table is shown in Figure below.

The size of the frame to be used by the scheduler is an important design parameter and needs to be chosen very carefully. The selected frame size should satisfy the following three constraints.

1. Minimum Context Switching:

This constraint is imposed to minimize the number of context switches occurring during task execution. The simplest interpretation of this constraint is that a task instance must complete running within its assigned frame. Unless a task completes within its allocated frame, the task might have to be suspended and restarted in a later frame. This would require a context switch involving some processing overhead.

To avoid unnecessary context switches, the selected frame size should be larger than the execution time of each task, so that when a task starts at a frame boundary it should be able to complete within the same frame. Formally, we can state this constraint as: max({ei}) < F where ei is the execution times of the of task Ti, and F is the frame size. Note that this constraint imposes a lower-bound on frame size, i.e., frame size F must not be smaller than max({ei}).

2. Minimization of Table Size:

This constraint requires that the number of entries in the schedule table should be minimum, in order to minimize the storage requirement of the schedule table. Remember that cyclic schedulers are used in small embedded applications with a very small storage capacity. So, this constraint is important to the commercial success of a product. The number of entries to be stored in the schedule table can be minimized when the minor cycle squarely divides the major cycle.

When the minor cycle squarely divides the major cycle, the major cycle contains an integral number of minor cycles (no fractional minor cycles). Unless the minor cycle squarely divides the major cycle, storing the schedule for one major cycle would not be sufficient, as the schedules in the major cycle would not repeat and this would make the size of the schedule table large.

We can formulate this constraint as ⎣M/F⎦ = M/F……(1)

In other words, if the floor of M/F equals M/F, then the major cycle would contain an integral number of frames.

3. The satisfaction of Task Deadline:

This third constraint on frame size is necessary to meet the task deadlines. This constraint imposes that between the arrival of a task and its deadline, there must exist at least one full frame. This constraint is necessary since a task should not miss its deadline, because by the time it could be taken up for scheduling, the deadline was imminent. Consider this: a task can only be taken up for scheduling at the start of a frame. If between the arrival and completion of a task, not even one frame exists, a situation as shown in Fig. above might arise. In this case, the task arrives sometimes after the kth frame has started.

Obviously, it cannot be taken up for scheduling in the kth frame and can only be taken up in the k+1th frame. But, then it may be too late to meet its deadline since the execution time of a task can be up to the size of a full frame. This might result in the task missing its deadline since the task might complete only at the end of (k+1)th frame much after the deadline d has passed. We, therefore, need a full frame to exist between the arrival of a task and its deadline as shown in Fig. below, so those task deadlines could be met.

More formally, this constraint can be formulated as follows: Suppose a task arises after Δt time units have passed since the last frame. Then, assuming that a single frame is sufficient to complete the task, the task can complete before its deadline iff (2F − Δt) ≤ di, or 2F ≤ (di + Δt). …(2)

Remember that the value of Δt might vary from one instance of the task to another. The worst case scenario (where the task is likely to miss its deadline) occurs for the task instance having the minimum value of Δt, such that Δt > 0. This is the worst case scenario since under this the task would have to wait for the longest before its execution can start.

It should be clear that if a task arrives just after a frame has started, then the task would have to wait for the full duration of the current frame before it can be taken up for execution. If a task at all misses its deadline, then certainly it would be under such situations. In other words, the worst case scenario for a task to meet its deadline occurs for its instance that has the minimum separation from the start of a frame.

The determination of the minimum separation value (i.e. min(Δt)) for a task among all instances of the task would help in determining feasible frame size. Consequently, this constraint can be written as:

for every Ti, 2F – gcd(F, pi) ≤ di …(3)

Note that this constraint defines an upper-bound on frame size for a task Ti, i.e., if the frame size is any larger than the defined upper-bound, then tasks might miss their deadlines. Expr. 3 defined the frame size, from the consideration of one task only. Now considering all tasks, the frame size must be smaller than max(gcd(F, pi)+di)/2.

Example 1:

A cyclic scheduler is to be used to run the following set of periodic tasks on a uniprocessor: T1 = (e1=1, p1=4), T2 = (e2=, p2=5), T3 = (e3=1, p3=20), T4 = (e4=2, p4=20). Select an appropriate frame size.

Solution: For the given task set, appropriate frame size is the one that satisfies all the three required constraints. In the following, we determine a suitable frame size F which satisfies all the three required constraints.

Constraint 1: Let F be an appropriate frame size, then max {ei, F}. From this constraint, we get F ≥ 1.5.

Constraint 2: The major cycle M for the given task set is given by M = LCM(4,5,20) = 20. M should be an integral multiple of the frame size F, i.e., M mod F = 0. This consideration implies that F can take on the values 2, 4, 5, 10, 20. The frame size of 1 has been ruled out since it would violate the constraint 1.

Constraint 3: To satisfy this constraint, we need to check whether a selected frame size F satisfies the inequality: 2F − gcd(F, pi) < di for each pi.

Let us first try frame size 2. 
For F = 2 and task T1: 

2 ∗ 2 − gcd(2, 4) ≤ 4 ≡ 4 − 2 ≤ 4 
Therefore, for p1 the inequality is satisfied. 
Let us try for F = 2 and task T2: 
2 ∗ 2 − gcd(2, 5) ≤ 5 ≡ 4 − 1 ≤ 5 
Therefore, for p2 the inequality is satisfied. 
Let us try for F = 2 and task T3: 

2 ∗ 2 − gcd(2, 20) ≤ 20 ≡ 4 − 2 ≤ 20 
Therefore, for p3 the inequality is satisfied. 
For F = 2 and task T4: 
2 ∗ 2 − gcd(2, 20) ≤ 20 ≡ 4 − 2 ≤ 20 
For p4 the inequality is satisfied.

Thus, constraint 3 is satisfied by all tasks for frame size 2. So, frame size 2 satisfies all the three constraints. Hence, 2 is feasible frame size.

Let us try frame size 4. 
For F = 4 and task T1: 
2 ∗ 4 − gcd(4, 4) ≤ 4 ≡ 8 − 4 ≤ 4 
Therefore, for p1 the inequality is satisfied. 
Let us try for F = 4 and task T2: 
2 ∗ 4 − gcd(4, 5) ≤ 5 ≡ 8 − 1 ≤ 5

For p2 the inequality is not satisfied. Therefore, we need not look any further. Clearly, F = 4 is not suitable frame size.

Let us now try frame size 5, to check if that is also feasible.

For F = 5 and task T1, we have 2 ∗ 5 − gcd(5, 4) ≤ 4 ≡ 10 − 1 ≤ 4 The inequality is not satisfied with T1. We need not look any further. Clearly, F = 5 is not suitable frame size.

Let us now try frame size 10. For F = 10 and task T1, we have 2 ∗ 10 − gcd(10, 4) ≤ 4 ≡ 20 − 2 ≤ 4 The inequality is not satisfied with T1. We need not look any further. Clearly, F=10 is not suitable frame size.

Let us try if 20 is feasible frame size. For F = 20 and task T1, we have 2 ∗ 20 − gcd(20, 4) ≤ 4 ≡ 40 − 4 ≤ 4 Therefore, F = 20 is also not suitable. So, only the frame size 2 is suitable for scheduling.

Even though for Example 1 we could successfully find a suitable frame size that satisfies all the three constraints, it is quite probable that a suitable frame size may not exist for many problems. In such cases, to find a feasible frame size we might have to split the task (or a few tasks) that is (are) causing violation of the constraints into smaller sub-tasks that can be scheduled in different frames.

Advantages of clock driven scheduling

1. Decisions on what jobs to execute at what time are made at specific time instants.
2. Jobs can schedule according to direct static schedule in different modes just need to change the static schedule table.
3. Context switching and communication overheads are low.
4. Easy to validate, test and certify.
5. Possible to determine whether the systems indeed meets all of its timing requirements.

Disadvantages of clock driven scheduling

1. The system based on this approach is relatively difficult to modify and maintain.
2. Suited for systems which are rarely modified.
3. Release time of all jobs must be fixed.
4. Not suitable for systems that contain all hard and soft real-time applications.