Practical Considerations

Practical Considerations

1. Handling overruns:

• Jobs are scheduled based on maximum execution time, but failures might cause overrun
• A robust system will handle this by either: 1) killing the job and starting an error recovery task; or 2) preempting the job and scheduling the remainder as an aperiodic job
• Depends on usefulness of late results, dependencies between jobs, etc.

2. Mode changes:

• A cyclic scheduler needs to know all parameters of real-time jobs a priori
• Switching between modes of operation implies reconfiguring the scheduler and bringing in the code/data for the new jobs
• This can take a long time: schedule the reconfiguration job as an aperiodic or sporadic task to ensure other deadlines met during mode change

3. Multiple processors:

• Can be handled, but off-line scheduling table generation more complex

Algorithm for construction static schedule

A system of independent preemptable periodic task whose relative deadline is equal to or greater than their respective periods is schedulable if and only if the total utilization of the task is not greater than 1.

Some tasks may have relative deadlines shorter than their periods and the cyclic schedule is constrained to have structure and a feasible schedule may not exist event if the conditions are met. Therefore, an algorithm is used to find out a feasible cycle schedule if one exists. This algorithm is called iterative network flow algorithm of 1NF algorithm.

It assumes that the task can be preempted at any time and are independent. In order to apply 1NF algorithm, find all the possible frame sizes of the system. For example, the possible frame sizes of the tasks T₁(4, 1), T₂(5, 2, 7), T₃(20, 5) are 2 and 4. It satisfies the second and third conditions but not the first condition. In such cases, 1NF iterative finds a feasible cyclic schedule for a possible frame size at a time starting from largest frame size to the smallest frame size.

The feasible schedule found in this way tells how to decompose some tasks into sub-tasks if the algorithm fails to find a feasible schedule. In this way, the given tasks do not have feasible cyclic schedule that satisfies all the framesize constraints.

Network Flow Graph

The network flow graph of preemptive scheduling jobs is used by 1NF. To use this algorithm, ignore the tasks to which the jobs belong and names the job to be scheduled in a major cycle of F frames as J1, J2, J3, . . . . . , Jn.

The constraints on which the jobs can be scheduled are represented by the network flow graph of the system. This graph contains the following vertices and edges and the capacity at an edge is a non-negative number associated with the edge.

1. A job vertex Ji represents each job.
2. A frame vertex j represents each frame j in the major cycle.
3. Contains two special vertices called source and sink.
4. A directed edge (J_i, j) from a job vertex J_i to a frame vertex j. if the job Ji can be scheduled in the frame j and capacity of the edge is the frame size f.
5. A directed edge from the source vertex to every jobs and the capacity of this edge is the execution time e_i of the job.
6. A directed edge from every vertex to the sink and the capacity of the edge is ‘f’.

A flow of an edge is a non-negative number satisfying the following condition.

1. No greater than the capacity of the edge.
2. The sum of flows of all the edges into every vertex is equal to the sum of the flows of all the edges out of the vertex except source and sink.

The above conditions can be shown in the following network flow graph.

• J_i can be scheduled in frames x and y.
• J_k can be scheduled in frames y and z.
• (e_k),e_k = “capacity of flow”.

Pros and cons of clock driven scheduling

There are many advantages of Clock driven scheduling. Some of them are listed below.

1. Conceptual Simplicity

• It defines the ability to consider complex dependencies, communication delays, and resource contention among jobs when constructing the static schedule, guaranteeing absence of deadlocks and unpredictable delays
• The entire schedule is captured in a static table
• Different operating modes can be represented by different tables.
• No concurrency control or synchronization is required.
• If completion time jitter requirements exist, can be captured in the schedule

2. When workload is mostly periodic and the schedule is cyclic, timing constraints can be checked and enforced at each frame boundary
3. The choice of frame size can minimize context switching and communication overheads
4. Clock driven scheduling is relatively easy to validate, test and certify.

Despite having its advantages, it has some disadvantages. These are listed below.

1. Inflexible:

• Pre-compilation of knowledge into scheduling tables means that if anything changes materially, have to redo the table generation
• Best suited for systems which are rarely modified once built

2. Other disadvantages:

• Release times of all jobs must be fixed
• All possible combinations of periodic tasks that can execute at the same time must be known a priori, so that the combined schedule can be pre-computed
• The treatment of aperiodic jobs is very primitive
• Unlikely to yield acceptable response times if a significant amount of soft realtime computation exists

References

Liu, Jane W. S. Real Time Systems. Integre Technical Publishing Co., Inc, January 10, 2000. Print.