Resources may represents

  • Hardware devices such as sensor and actuators
  • Disk or memory capacity and buffer space
  • Software resources such as locks or queues

Resource Access Control Protocols work to reduce the undesirable effect of resource contention. Resource contention affects the execution behavior and schedulability of jobs. It is focused on the Priority Driven Systems. Clock Driven Systems can avoid resource contention among jobs by scheduling them according to cyclic schedule that keeps jobs‟ resource access serialized.

Assumptions on Resources and their Usage

  • The system consists of only one processor
  • The system also contains p types of serially reusable resources named R1, R2 Rp
  • There are v i indistinguishable units of resources of type Ri for 1 ≤ i ≤ p
  • Serially reusable resources are granted to jobs on a non-preemptive basis and used in a mutually exclusive manner
  • When a unit of a resources Ri is granted to a job, this unit is no longer available to other jobs until the job frees the unit. For example mutexes, reader/writer locks, connection sockets, printers.
  • A binary semaphore is a resource that has only one unit while a counting semaphore has many units. For example a system containing five printers has five units of the printer resource
  • There is only one unit of an exclusive write lock.
  • Some resources can be used by more than one job at the same time 
  • This type of resource has many units each used in a mutually exclusive manner e.g. a file that can be read by at most „v‟ users at the same time

Mutual Exclusion and Critical Sections

  • A lock based concurrency control mechanism is used to enforce mutually exclusive accesses of jobs to resources.
  • When a job wants to use ni units of resource R i, it executes a lock to request them This lock request is denoted by L(R i, n i) .
  • If a lock request fails, the requesting job is blocked and loses the processor.
  • When the requested resource becomes available, it is unblocked.
  • The job holding a lock cannot be preempted by a higher priority job needing that lock.
  • The job continues to execute when it is granted the requested resource.
  • When the job no longer needs the resource, it releases the resource by executing an unlock denoted by U(R i, n i)
  • A job that begins at a lock and ends at a matching unlock is called a critical section Resources are released in the last-in-first-out-order.
  • The expression [R, n, e] is used to represent the critical section regarding n units of resources with the critical section requiring e units of execution time.
  • The critical section may nest if a job needs the multiple simultaneous resources. For example lock R1 then Lock R2 then lock R3 and unlock R3, R2 and R1 is represented as [R1, n1, e1, [R2, n2, e2, [R3, n3, e3]]]
  • The critical section that is not included in other critical section is called outer most critical section.

For example:

Resource Conflicts and Blocking

  • Two jobs conflict with one another or have a resource conflict if some of the resources they require are of the same type.
  • Jobs contend for a resource when one job requests a resource that other jobs already The scheduler always denies a request if there are not enough free units of the resource to satisfy the request or to avoid some undesirable execution behavior.
  • When the scheduler does not grant n i units of resource R i to the job requesting them, the lock request L(R i, η i) of the job fails.
  • When the lock request fails, the job is blocked and loses the processor then blocked job is removed from the ready job queue. It stays blocked until the scheduler grants it n i units of R i for which the job is waiting.
  • When the job becomes unblocked it is moved back to the ready queue and executes when it is scheduled.

For example: Consider a system with

  • Three jobs J 1, J2, J3, with feasible interval (6, 14], ( 2, 17], (0 ,18].
  • The jobs are scheduled on the processor on the EDF basis.
  • J1 has the highest and J3 has the lowest priority.
  • All three jobs require the resource R which has only one unit. Then the critical sections in these jobs are [R; 2], [R; 4], [R; 4] such that

  • At time 0 only J3 is ready so it executes
  • At time 1, J3 is granted the resource R when it executes L(R)
  • J2 is released at time 2, preempts J3 and begins to execute
  • 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
  • At time 6, J1 becomes ready preempts J3 and begins to execute
  • J1 executes until time 8 when it executes a L(R) to request R. J3 still has the resource so J1 becomes blocked. Only J3 is ready for execution and it again has the processor and executes.
  • The critical section of J3 completes at time 9. The resource R becomes free when J3 executes U(R) both J1 and J3 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.
  • J1 releases the resource R at time J2 is unblocked. Since J1 has the highest priority it continues to execute.
  • 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 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.