1) What is Safe State? Define Deadlock. Explain Banker’s Algorithm to avoid deadlock.
Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
Consider an example when two trains are coming toward each other on same track and there is only one track, none of the trains can move once they are in front of each other. Similar situation occurs in operating systems when there are two or more processes hold some resources and wait for resources held by other(s). For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is waiting for resource 1.
1.
2.
3.
4.
Consider an example when two trains are coming toward each other on same track and there is only one track, none of the trains can move once they are in front of each other. Similar situation occurs in operating systems when there are two or more processes hold some resources and wait for resources held by other(s). For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is waiting for resource 1.
Safe State:-
If the system can allocate resources to the process in such a way that it can avoid deadlock. Then the system is in a safe state.
Banker's Algorithm:-
Banker's algorithm is a deadlock avoidance algorithm. It is named so because this algorithm is used in banking systems to determine whether a loan can be granted or not.
Consider there are
n account holders in a bank and the sum of the money in all of their accounts is S. Everytime a loan has to be granted by the bank, it subtracts the loan amount from the total money the bank has. Then it checks if that difference is greater than S. It is done because, only then, the bank would have enough money even if all the n account holders draw all their money at once.
Banker's algorithm works in a similar way in computers.
Whenever a new process is created, it must specify the maximum instances of each resource type that it needs, exactly.
Let us assume that there are
n processes and m resource types. Some data structures that are used to implement the banker's algorithm are:
1. Available
It is an array of length
m. It represents the number of available resources of each type. If Available[j] = k, then there are kinstances available, of resource type R(j).
2. Max
It is an
n x m matrix which represents the maximum number of instances of each resource that a process can request. If Max[i][j] = k, then the process P(i) can request atmost kinstances of resource type R(j).
3. Allocation
It is an
n x m matrix which represents the number of resources of each type currently allocated to each process. If Allocation[i][j] = k, then process P(i) is currently allocated k instances of resource type R(j).
4. Need
It is an
n x m matrix which indicates the remaining resource needs of each process. If Need[i][j] = k, then process P(i)may need k more instances of resource type R(j) to complete its task.Need[i][j] = Max[i][j] - Allocation [i][j]