Every periodic task that requires resource on more than one processor can be treated as an end to end periodic task. Each job of task contains a chain of component jobs which execute in sequence on different processors. Suppose, task Ti has n(i) subtasks Ti,k for k = 1, 2, …., n(i). These subtasks execute in turn in different processors to its visit sequence Vi = (vi, 1, vi, 2, …… vi, n(i) ) where Vi,k = Pj which means the kth subtask executes on processor Pj. The two essential components to the end to end scheduling schemes are 1) protocols for synchronizing the execution of sibling subtasks on different processor. So that precedence constraint among subtasks is maintained. 2) Algorithms for scheduling subtasks on each processor.
Inter-process Synchronization Protocol:
Greedy Synchronization Protocol
It is most commonly used in non-real time systems like in wide communication. Transmission of each newly compressed frame is made ready as soon as compression of frame is completed.
Greedy Synchronization protocol states that when jth job of Ti,k completes on Vi,k , the scheduler of Vi,k sends a synchronization signal to the scheduler of Vi,k+1 on which the successor subtask Ti,k+1 executes. Upon receiving the synchronization signal, the scheduler of Vi,k+1 releases the corresponding job of task Ti,k+1.
Example: T1 (6, 3) T3 (6, 9, 4) T2, 1 (9, 3) and T2, 2 (9, 3)
These tasks run on two processors P1 and P2 where T1 and T2, 1 run on P1, T2, 2 and T3 on P2. T1 has highest priority on P1 and T2, 2 has highest priority in P2.
Figure: Illustration of Greedy Synchronization Protocol
Greedy synchronization protocol decreases the response time of end to end periodic task in comparison to non-greedy method. In the example above, the inter-release time of task T2 is 6 while its period is 9 due to which T3 misses its deadline.