System Resources

A system consists of a finite number of resources to be distributed among a number of competing processes. Each type of resource can have several finite instances. Some example include:

• CPU cycles / cores
• I/O devices
• Access to files or memory locations (guarded by locks or semaphores, etc)

A process must request a resource before using it and must release the resource after using it. A process may request as many resources as it requires to carry out its designated task. Obviously, the number of resources requested should not exceed the total number of resources available in the system.

In other words, a process cannot request three printers if the system has only two.

Under the normal mode of operation, a process may utilize a resource in only the following sequence:

• Request: The process requests the resource. If the request cannot be granted immediately (for example, if the resource is being used by another process), then the requesting process must wait until it can acquire the resource.

• Use: The process can operate on the resource (for example, if the resource is a printer, the process can print on the printer).

• Release: The process releases the resource.

The request and release of resources may require system calls, depending on who manages the resources.

Kernel Managed Resources

For each use of a kernel-managed resource, the operating system checks to make sure processes who requested these resources has been granted allocation of these resources. Examples are the request() and release() device, open() and close() file, and allocate() and free() memory system calls.

Some implementation detail: A typical OS manages some kind of system table (data structure) that records whether each resource is free or allocated. For each resource that is allocated, the table also records the process to which it is allocated. If a process requests a resource that is currently allocated to another process, it can be added to a queue of processes waiting for this resource.

Developers who simply write programs utilising these resources simply make the system calls and need not care about how Kernel manages these resources (abstracted).

User Managed Resources

For each use of user-managed resources, we can guard them using semaphores or mutexes. The request and release of semaphores can be accomplished through the wait() and signal() operations on semaphores, or through acquire() and release() of a mutex lock.

Writing these series of wait() and signal() are defined by developers, and they have to be very careful in writing them else it might result in a deadlock situation.

The Deadlock Problem

Deadlock is a situation whereby a set of blocked processes (none can make progress) each holding a resource and waiting to acquire a resource held by another process in the set.

The locking tools we learned in the previous chapter prevents race condition, but if not implemented properly it can cause deadlock.

Example

For example, consider two mutex locks being initialized:

pthread_mutex_t first_mutex;
Pthread_mutex_t second_mutex;
pthread_mutex_init(&first_mutex,NULL);
pthread_mutex_init(&second_mutex,NULL);

And two threads doing these work concurrently potentially results in deadlock:

Can you identify the order of execution that causes deadlock?

// Thread 1 Instructions
pthread_mutex_lock(&first_mutex);
pthread_mutex_lock(&second_mutex);
/**
* Do some work
*/
pthread_mutex_unlock(&second_mutex);
pthread_mutex_unlock(&first_mutex);
pthread_exit(0);
/************************************/


// Thread 2 Instructions
pthread_mutex_lock(&second_mutex);
pthread_mutex_lock(&first_mutex); /**
/**
* Do some work
*/
pthread_mutex_unlock(&first_mutex);
pthread_mutex_unlock(&second_mutex);
pthread_exit(0);
/************************************/

Consider the scenario where Thread 1 acquires first_mutex and then suspended, then Thread 2 acquires second_mutex.

• Neither thread will give up their currently held mutex,
• However they need each other’s mutex lock to continue: hence neither made progress and they are in a deadlock situation.

Deadlock Necessary Conditions

A deadlock situation may arise if the following four conditions hold simultaneously in a system. These are necessary but not sufficient conditions:

Read: simultaneously, means ALL of them must happen to even have a probability of deadlock

1. Mutual exclusion

   • At least one resource must be held in a non-sharable mode.
   • If another process requests that resource that’s currently been held by others, the requesting process must be delayed until the resource has been released.

2. Hold and Wait

   • A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.

3. No preemption¹

   • Resources can only be released only after that process has completed its task, voluntarily by the process holding it.

4. Circular Wait

   • There exists a cycle in the resource allocation graph (see next section)

These conditions are necessary but not sufficient, meaning that if all four are present, it is not 100% guaranteed that there is currently a deadlock.

Think! Since these conditions are necessary for deadlock to happen, removing just one of them prevents deadlock from happening at all.

Resource Allocation Graph

Deadlocks can be described more precisely in terms of a directed graph called a system resource-allocation graph.

The graph description:

• A set of vertices V that is partitioned into two different types of nodes:
  • Active processes (circle node) and
  • All resource types (square node) in the system
• Directed edges from:
  • Process to resource nodes: process requesting a resource (request edge)
  • Resource to process nodes: assignment / allocation of that resource to the process (assignment edge)
• Resource instances within each resource type node (dots)

Example 1

Suppose a system has the following state:

The resource allocation graph illustrating those states is as follows:

Analysing the Graph

If the graph has no cycle: deadlock will never happen.

If there’s at least 1 cycle:

• If all resources has exactly one instance, then deadlock (deadlock necessary and sufficient condition)
• If cycle involves only a set of resource types with single instance, then deadlock (deadlock necessary and sufficient condition)
• Else if cycle involves a set of resource types with multiple instances, then maybe deadlock (we can’t say for sure, this is just a necessary but not sufficient condition)

In Example 1 diagram above, the three processes are deadlocked (process and resource is shortened as P and R respectively):

• P1 needs R1, which is currently held by P2
• P2 needs R4, which is currently held by P3
• P3 needs R2, which is currently held by either P1 or P2

  Neither process can give up their currently held resources to allow the continuation of the others resulting in a deadlock.

Example 2

Now consider the another system state below. Although there are cycles, this is not a deadlocked state because P1 might eventually release R2 after its done, and P3 may acquire it and complete. Finally, P2 may resume to completion after P3 is done.