Rate Analysis at Process Level
Delay analysis on the process graph
- delay of a path, delay of a cycle
A k-critical path for a process p is a path that determines kth invocation time of p.
A k-critical path for p is a maximum delay path with exactly k edges ending at p.
A cycle with maximum mean delay is called a critical cycle.
Theorem 1: A k-critical path for p that includes a vertex of a critical cycle Cj has less than lcm (|C|, |Cj|)/|C| occurrences of any non-critical cycle |C|.
=> bounds the number of non-critical cycles in a k-critical path.
Let x_i(k) be the time at which process p_i starts executing for the k-th time.
x_i(k) = max_{predecessors of p_i} [ x_j(k-1) + A_ij ] => X(k) = A x X(k-1) = A^k x X(0)
where A^l _ij is the length of the longest path from p_j to p_i that goes through exactly (l-1) vertices.