A resource access control protocol is a set of rules that govern

  • When and under what conditions each request for resource is granted
  • How jobs requiring resources are scheduled.

One of the major objective of resources access control is to minimize the undesirable effects of resource allocation.

The undesirable effects of resource contention are

  1. Priority Inversion
  2. Timing anomalies
  3. Deadlock

Priority Inversion


Priority inversion can occur when execution of some jobs or portions of jobs is non-preemptable. As resources are allocated to jobs on a non-preemptive 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 this example, there are three jobs, J1, J2, and J3, whose feasible intervals are (6, 14], (2, 17] and (0, 18], respectively. Here the lowest priority job J3 first blocks J2 and then blocks J1 while it holds the resource R such that Priority Inversion occurs in intervals (4,6] and (8,9] .

Let us take another example

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.

Timing anomalies


When priority inversion occurs, timing anomalies invariably follow i.e. there may be the chance of miss the deadline. This condition is called timing anomalies. Suppose the critical section J3 is [R; 2.5] in the above example then J1 misses its deadline as it does not complete until 14.5.

Deadlock


If two jobs need resource Rx and Ry and if one acquires the lock in the order Rx then Ry and the other job acquires them in opposite order Ry then Rx then deadlock occurs.

Here the deadlocks occurs when J1 needs Rx locked by J2 and J2 needs Ry locked by J1.