Effect Of Resource Contention And Resource Access Control (Rac)

EFFECTS OF RESOURCE CONTENTION AND RESOURCE ACCESS CONTROL: A resource access-control protocol, or simply an access-control protocol, is a set of rules that govern (1) when and under what conditions each request for resource is granted and (2) how jobs requiring resources are scheduled. Before moving on to describe several well-known resource access-control protocols and their performance, let us examine in more detail the undesirable effects of resource contention. By looking more closely at what can happen when jobs contend for resources, we should see more clearly the specific design objectives of such a protocol.
Priority Inversion, Timing Anomalies, and Deadlock: Resource contentions among jobs can also cause priority inversion. Because resources are allocated to jobs on a nonpreemptive basis, a higher-priority job can be blocked by a lower-priority job if the jobs conflict, even when the execution of both jobs is preemptable. In the example in Figure 8–2, the lowest priority job J3 first blocks J2 and then blocks J1 while it holds the resource R. As a result, priority inversion occurs in intervals (4, 6] and (8, 9].
When priority inversion occurs, timing anomalies invariably follow. Figure 8–3 gives an example. The three jobs are the same as those shown in Figure 8–2, except that the critical section in J3 is [R; 2.5]. In other words, the execution time of the critical section in J3 is shortened by 1.5. If we were not warned earlier in Section 4.8 about timing anomalies, our intuition might tell us that as a consequence of this reduction in J3’s execution time, all jobs

should complete sooner. Indeed, this reduction does allow jobs J2 and J3 to complete sooner. Unfortunately, rather than meeting its deadline at 14, J1 misses its deadline because it does not complete until 14.5.

More seriously, without good resource access control, the duration of a priority inversion can be unbounded. The example in Figure 8–4 illustrates this fact. Here, jobs J1 and J3 have the highest priority and lowest priority, respectively. At time 0, J3 becomes ready and executes. It acquires the resource R shortly afterwards and continues to execute. After R is allocated to J3, J1 becomes ready. It preempts J3 and executes until it requests resource R at time 3. Because the resource is in use, J1 becomes blocked, and a priority inversion begins. While J3 is holding the resource and executes, a job J2 with a priority higher than J3 but lower than J1 is released. Moreover, J2 does not require the resource R. This job preempts J3 and executes to completion. Thus, J2 lengthens the duration of this priority inversion. In this situation, the priority inversion is said to be uncontrolled [ShRL90]. There can be an arbitrary number of jobs with priorities lower than J1 and higher than J3 released in the meantime. They can further lengthen the duration of the priority inversion. Indeed, when priority inversion is uncontrolled, a job can be blocked for an infinitely long time.

Nonpreemptivity of resource allocation can also lead to deadlocks. The classic example is one where there are two jobs that both require resources X and Y. The jobs are in deadlock

when one of them holds X and requests for Y, while the other holds Y and requests for X. The conditions that allow this circular wait of jobs for each other (i.e., a deadlock) to occur are well-known [Crow, SiGa].

From these examples, we see that no resource access-control protocol can eliminate the priority inversion and anomalous behavior caused by resource contention. A more realistic goal of such a protocol is that it keeps the delays thus incurred as short as possible. For this reason, a criterion we use to measure the performance of a resource access-control protocol is the blocking time of each job. A good resource access-control protocol should control priority inversion and prevent deadlock and, thus, keep the blocking time of every job bounded from the above.