Assumptions On Resources And Their Usage

The example in Figure 8–2 illustrates the effect of resource contentions. In this example, there are three jobs, J1, J2, and J3, whose feasible intervals are (6, 14], (2, 17] and (0, 18], respectively. The release time and deadline of each job are marked by the vertical bar on each of the time lines. The jobs are scheduled on the processor on the earliest-deadline-first basis. Hence, J1 has the highest priority and J3 the lowest. All three jobs require the resource R, which has only 1 unit. In particular, the critical sections in these jobs are [R; 2], [R; 4], and [R; 4], respectively. Below is a description of this schedule segment. The black boxes in Figure 8–2 show when the jobs are in their critical sections.

1. At time 0, only J3 is ready. It executes.
2. At time 1, J3 is granted the resource R when it executes L(R).
3. J2 is released at time 2, preempts J3, and begins to execute.
4. At time 4, J2 tries to lock R. Because R is in use by J3, this lock request fails. J2 becomes blocked, and J3 regains the processor and begins to execute.
5. At time 6, J1 becomes ready, preempts J3 and begins to execute.
6. J1 executes until time 8 when it executes a L(R) to request R. J3 still has the resource. Consequently, J1 becomes blocked. Only J3 is ready for execution, and it again has the processor and executes.
7. The critical section of J3 completes at time 9. The resource R becomes free when J3 executes U(R). Both J1 and J2 are waiting for it. The priority of the former is higher. Therefore, the resource and the processor are allocated to J1, allowing it to resume execution.
8. J1 releases the resource R at time 11. J2 is unblocked. Since J1 has the highest priority, it continues to execute.
9. J1 completes at time 12. Since J2 is no longer blocked and has a higher priority than J3, it has the processor, holds the resource, and begins to execute. When it completes at time 17, J3 resumes and executes until completion at 18.

This example illustrates how resource contention can delay the completion of higher-priority jobs. It is easy to see that if J1 and J2 do not require the resource, they can complete by times 11 and 14, respectively.