A system of independent preemptive task whose relative deadline are equal to or greater than their respective periods is schedulable if and only if the total utilization of the task is greater than 1. Similarly, some tasks may have relative deadlines shorter than their periods but there is no existence of feasible schedule due to frame size constraints. Therefore an algorithms is used to find the feasible schedule in cyclic scheduling is called iterative network flow (INF) algorithms.
The INF algorithms assumes that the task can be preempted at any time and are independent. In order to apply INF, find all possible frame size for given system. For example, consider three independent tasks T1(4, 1), T2(5, 2, 7) and T3 (20, 5). For this valid frame can be 4 or 2 but it cannot satisfy the constraints of frame size so there is impossible to construct the feasible schedule without using INF.The INF iteratively finds the feasible schedule for the possible frame size starting from the largest frame. The feasible schedule found in the way is to decompose the task into subtasks.
The major component of INF is network flow graph. The constraints on when the jobs can be scheduled are represented by the network-flow graph of the system. This graph contains the following vertices and edges; the capacity of an edge is a nonnegative number associated with the edge.
The graph contains following vertices and edges.
- There is a job vertex Ji representing each job Ji, for i = 1, 2, . . . , N.
- There is a frame vertex named j representing each frame j in the major cycle, for j = 1, .
. F. There are two special vertices named source and sink.
- There is a directed edge (Ji , j ) from a job vertex Ji to a frame vertex j if the job Ji can be scheduled in the frame j , and the capacity of the edge is the frame size f .
- There is a directed edge from the source vertex to every job vertex Ji , and the capacity of this edge is the execution time ei of the
- There is a directed edge from every frame vertex to the sink, and the capacity of this edge is
A flows of an edge is a non-negative number satisfying following conditions.
- It is no greater than the capacity of edges.
- The sum of flows of all edges into every vertex is equal to sum of all edges out of