Elements of Scheduling Algorithms for End to End Periodic Tasks

Elements of Scheduling Algorithms for End-to-End Periodic Tasks

End to end scheduling has two essential components:

1. Protocols for synchronizing the execution of siblings subtasks on different processors so that precedence constraints among subtask are maintained.
2. Algorithms for scheduling subtasks on each processor.

According to the end to end scheduling approach, the fact that no subtasks in the system ever requires remote resource makes it possible for the scheduler on each processor to use any on uniprocessor scheduling algorithms and resource access protocols to schedule subtasks on the processor and control their accesses to resources. It is even possible for the system to use a mixture of more than one scheduling strategy. For example, using dynamic priority schemes on some processors while using fixed priority schemes on the others, or make some processors priority driven and others clock driven.

Most of the real life systems use mixed scheduling strategies on different processors. For example, an end to end task whose subtasks compress video images periodically on a computer transmits video stream across a network whereas decompresses and displays the video on other computer. The computers at the two ends schedules the compression and decompression subtask differently from the way the network schedules the transmission of the video.

Interprocessor Synchronization Protocols

The jobs of the first sub-task T_i,1 of every end to end periodic task Ti are released no less than pi units of time apart. In a multiprocessor system, how jobs in sibling subtasks are released critically affects the schedulability, completion time jitter and average response time of end to end to tasks. So, a protocol that governs when the schedulers on different processors release the jobs the sibling subtasks is called an execution synchronization protocol. It is simply called a synchronization protocol because there is no ambiguity.

A synchronization protocol is correct if it,

1. Never releases jobs in any first subtask before the end to end release times of the jobs, and
2. Never allows the violation of any precedence constraint among sibling subtasks.

There are two types of synchronization protocols:

1. Greedy Synchronization Protocol (work-conserving)
2. Non-Greedy Synchronization Protocol (nonwork-conserving)

Greedy Synchronization Protocol

It is a commonly used synchronization protocol, especially in real time system. It can be implemented in many different ways. It can be implemented as follows: when the j^th job of T_i,k completes on V_i,k, the scheduler of V_i,k sends a synchronization signal to the scheduler of V_i,k+1 on which the successor subtask Ti,k+1 is executed. After receiving the synchronization signal, the scheduler of V_i,k+1 releases the corresponding job J_i,k+1;j immediately. Since, the multiprocessor system model used here takes into account interprocessor communication costs, the delay in synchronization signal delivery id let to be 0.

The greedy synchronization protocol is a simple protocol. It does not require any global clock synchronization. The only global information it requires is the identities of the immediate upstream processor and the next downstream processor in the visit sequence of each task which is executed on the processor. The greedy synchronization protocol yields the shortest average end to end response time of all tasks compared with non-greedy protocols. But the inter-release intervals of consecutive jobs in a later subtask can be shorter than the period of the subtask. This can by illustrated by the following example.

Consider a system with two processor and three tasks: T₁ = (6, 3), T₃ = (6, 10, 4) do not have subtasks, and they are executed on P₁ and P₂. T₂ has Subtasks: T_2,1 = (9,3) executes on P₁ and T_2,2 = (9, 3) executes on P₂. The relative end to end deadlines of the tasks are equal to their respective periods. The tasks are given fixed priorities on both the processors. T₁ has higher priority on P₁ and T_2,2 has a higher priority on P₂. Figure (a) shows the schedule of the tasks when they are synchronized on the basis of greedy protocol. The dashed vertical arrows at times 6 and 12 represents synchronization signal between processors. Since, the inter-release times of jobs in T_2,2 can be as short as 6, T₃ cannot meet its deadlines. Figure (b) shows that if the jobs in T_2,2 are released periodically. T₃ always meets its deadlines.(Liu, 2003, pp. 374-376)

End-to-End Tasks in Heterogeneous Systems

When the processor time demand of every subtask T_i,k on a processor meets the design constraint of the scheduling algorithm used by the processor, an upper bound W_i,k to the subtask’s response time is obtained on the processor without considering tasks that execute on other processors. Without loss of generality, it is assumed that the scheduler on every processor uses a real-time scheduling algorithm.

In a system of end to end periodic tasks, one of the way to keep the worst case end to end response time of every periodic task small and end to end schedulability analysis simple is to use a non-greedy interprocessor synchronization protocol that reshapes the release time pattern of every subtask to make the subtask periodic. The modified phase protocol (MPM) and release guard (RG) protocol are examples of such protocols. They do not require priority driven scheduling to be used on individual processors.(Liu, 2003, pp. 398-399)

Corollary

In a system where a real time algorithm is used to schedule sub-tasks on every processor, an upper bound W_i to the end to end response time of any periodic task T_i synchronized to the MPM protocol or the RG protocol is given by

Where n(i) is the number of subtasks in T_i and the upper bound W_i,k to the response time of every subtask T_i,k is obtained by considering only subtasks on the same processor as T_i,k and by treating every subtask T_j,l as a periodic task whose period is equal to the period P_j of the parent task T_j.

Predictability and Validation of Dynamic Multiprocessor Systems

Predictable execution of a set J of jobs is defined in terms of 3 possible schedules of J according to the given scheduling algorithm: the maximum, minimal and actual schedules. If every job in J were to execute for as long as its maximum execution time (or short as its minimum execution time), the resultant schedule of J would be the maximal (or minimal) schedule. These schedules can be easily be constructed as long as the range of execution time of every hard real time job is known. The actual execution times of jobs are unknown, and therefore, the actual schedule of J is unknown.

The figure below illustrates that in a dynamic system, the actual start time s(J_i) of a job J_i according to the actual schedule of J can be later or earlier than its start time s⁺(J_i) or s-(J_i) according to the maximal schedule or minimal schedule. The start time of J_i is said to be unpredictable if this condition occurs. Similarly, the actual completion time f(J_i) according to the actual schedule of J can be later than its completion time f⁺(J_i) of J_i according to the maximum schedule. The completion time of J_i is unpredictable if this is true. On the other hand, if s^-(J_i) ≤ s(j_i) ≤ s⁺(J_i) then J_i is start time predictable and if f^-(J_i) ≤ f(j_i) ≤ f⁺(J_i), then J_i is completion time predictable. The execution of J_i is predictable if J_i is both start time and completion time predictable. The execution behavior of the entire set J is predictable if every job in J is predictable.

The above example shows that the execution of jobs in dynamic, priority driven multiprocessor is unpredictable in general, but this system can have predictable execution under several conditions. According to the maximal and minimal schedules, when one of these conditions are satisfied, the response time of each job gives the upper and lower bounds of the response time.(Liu, 2003, pp. 400-401)

Validation of Preemptable/Migratable system

A dynamic system in which jobs are scheduled on a priority driven manner on ‘m’ processors is called as a preemptable/migratable system. Every job that can be dispatched to execute on any processor can be preempted at any time and when preempted, they can be resumed on any processor. That is, jobs can be migrated among processors. A condition for predictability of a preemptable or migratable system is: the jobs have no precedence constraints and do not contend for resources.

Theorem

The execution of a system of preemptable/migratable jobs is predictable if all the jobs have fixed release times, are independent, and do not contend for resources.

Other conditions for Predictability

The system shown in above figure is a preemptable or migratable system. In such system, jobs are scheduled in priority driven manner and every job can be dispatched to execute on any processor. However, once a job starts on a processor, it is constrained to execute on that processor. Job migration is too costly in most multiprocessor and distributed systems so, this scheduling strategy is commonly used. Under the theorem stated below, the execution of preemptable or migratable, independent jobs is predictable.

Theorem 1

If in a system of preemptable/nonmigratable, independent jobs, preemption can never occur, then the execution of the jobs is predictable.

Theorem 2

If according to the maximal schedule of a system of preemptable/nonmigratable independent jobs, no job is preemptable and the jobs start in the same sequence according to the maximal and minimal schedules, then their execution is predictable.

References

Liu, J. W. (2003). Real Time System. Pearson Education, Inc. and Doring Kindersley Publishing Inc.