The resource-allocation-graph algorithm for deadlock avoidance is not applicable to a resource-allocation system with multiple instances of each resource type. Banker’s algorithm is applicable to such a system but is less efficient than the resource-allocation graph scheme. When a new process enters the system, it must declare the maximum number of instances of each resource type that it many need. This number may not exceed the total number of resources in the system. When a user requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state. If it will, the resources are allocated; otherwise, the process must wait until some other process releases enough resources.
$Safe \,\,state → no \,\, deadlock$
A state is said to be safe, if it has a process sequence ${P1, P2,…, Pn}$, such that for each $Pi$, the resources that $Pi$ can still request can be satisfied by the currently available resources plus the resources held by all $Pj$, where $j < i$.
State is safe because OS can definitely avoid deadlock (by blocking any new requests until safe order is executed)
This avoids circular wait condition as Process waits until safe state is guaranteed.
Deadlock Avoidance Algorithms :
1. Resource-Allocation Graph Algorithm : Works only if each resource type has one instance.
Since each resource has only One instance, Things become easy, Hence we do not need to apply banker's algo (Time cop = $O(m \times n^2)$) to determine whether System is in safe state or not, for Deadlock Avoidance. Instead we can apply Resource-Allocation Graph Algorithm which takes just $O(mn)$ time.
Algorithm:
1. Add a claim edge, $Pi → Rj$, if $Pi$ can request $Rj$ in the future, Represented by a dashed line in graph.
2. A request $Pi → Rj$ can be granted only if Adding an assignment edge $Rj → Pi$ does not introduce cycles – (since cycles imply unsafe state)
In Resource Allocation Graphs,
1. If graph contains no cycles $\rightarrow$ no deadlock
2. If graph contains a cycle then
- if only one instance per resource type, then deadlock
- if several instances per resource type, possibility of deadlock
So, In Resource-Allocation Graphs, When each resource has single instance, then Just by checking Cycle, We can decide whether System is in Safe state or not. Hence, Time comp = $O(mn)$
An algorithm for detecting a cycle in this graph requires an order of $n^2$ operations, where $n$ is the number of processes in the system.
2. Banker's Algorithm : Banker's algo can be applied even when Resource-system have multiple instances of each resource type. It can also be applied when Resource-system have single instance of each resource type But in that case, It would be less efficient than Resource-Allocation Graph Algorithm which we discussed above.
Algorithm : Let's keep it Simple and not go too much formal. Explaining the Algorithm just the way we solve any Question in Banker's algo to keep it simple and easy to understand. There might be other more efficient ways (Not asymptotically though) using Data Structures like Hash table etc... But I'll use the simplest data structures like Array and matrix(2-D Array) to elaborate my point.
Deadlock Avoidance, assuming that we are in a safe state and we are requested certain resources, simulates the allocation of those resources and determines if the resultant state is safe. If it is safe then request is satisfied, otherwise it is delayed until it becomes safe.
The Banker's Algorithm is used to determine if a request can be satisfied. It uses the following variables :
1. AVAILABLE = it specifies for each resource how many copies of it are available. Let's take an array data structure to represent it. Hence We'll have Avail$[1...m]$ of integers to represent AVAILABLE array where I assume that Each resource is named $1 \,\,to \,\,m$, Hence, Each Array index corresponds to one specific resource with same name as array index.
2. ALLOCATION = Array $ALLOC[1..n, 1..m]$ of integer; -- $ALLOC[i,j]$ specifies the number of copies of resource $j$ that are allocated to process $i$. So, Rows represent Processes numbered from $1\,\,to\,\,n$ and columns represent Resources numbered from $1 \,\, to \,\,m$
3. MAX : Array MAX$[1..n, 1..m]$ of integer; -- $MAXIM[i,j]$ specifies the maximum number of copies of resource $j$ that process $i$ will use.
4. NEED; array $NEED[1..n, 1..m]$ of integer; -- $NEED[i,j]$ specifies the number of copies of resource $j$ that process $i$ still requires. It is equal to $MAX[i,j]-ALLOC[i,j]$
Now let's analyze the time comp just like we apply Banker's algo to any problem. (It would help if you keep some example/data with you)
So, First We Try to find that Process whose Need we can satisfy with the Available resources. Hence, We need to scan through All the Rows to NEED matrix to find such process which in worst case might take $O(mn)$ time as we, in worst case, might have to scan all the $n$ rows of NEED matrix with the AVAIL Array and in each row scan we have to compare $m$ elements (of NEED of process $P_i$ and AVAIL array)..Hence $O(mn)$
After this, If we find such Row i.e. Process $P_i$ whose need we can satisfy then we allocate it its needed resources and let it complete. Which when completed, leaves all its resources it was previously holding(ALLOC matrix $P_i$ row) and these resources are added into the AVAIL array. This takes $O(m)$ time as there are $m$ resources. So, So far, For this First Process $P_i$ we have spent $O(mn) + O(m)$ time. And Now it is out of our concern and so out of further consideration.
Then We move on to find next process $P_j$ whose request we can satisfy. And Same Procedure which we applied for Process $P_i$, is applied for it as well. i.e. We scan through each Row of NEED array and try to find such process $P_j$ whose NEED we can satisfy by comparing its NEED with the AVAIL array... Hence, In worst case, We might have to scan through all the (n-1) Rows of NEED array and for each Row, $m$ comparisons with AVAIL array. Hence, Time taken $O(m(n-1))$
And After finding such process, we allocate it its needed resources and let it complete. Which when completed, leaves all its resources it was previously holding(ALLOC matrix $P_j$ row) and these resources are added into the AVAIL array. This takes $O(m)$ time as there are $m$ resources. So, So far, For this Second Process $P_j$ we have spent $O(m(n-1)) + O(m)$ time. And Now it is out of our concern and so out of further consideration.
Repeat this same procedure until All are completed or We can't find a safe sequence in between.
So, Time comp in worst case = $O(mn) + O(m(n-1)) + O(m(n-2)) + ..... + O(m) = O(m.n^2)$
