Deadlock and Banking Algorithm

Get a piece of basic knowledge about deadlock and what it is. What are the measures., conditions, and more. Also, know about Banker's algorithm and how does the calculation work.

1. Deadlock & Banker’s Algorithm Operating System(Cse-323)

2. What is 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. In a multiprogramming system, numerous processes get competed for a finite number of resources. Any process requests resources, and as the resources aren't available at that time, the process goes into a waiting state. At times, a waiting process is not at all able again to change its state as other waiting processes detain the resources it has requested. So in this condition, a deadlock is appeared. In the operating system, multiple resources are used by process in three different ways, such as – Requests for resource Use this resource Free this resource after completing task.

3. What is Deadlock!!?? In the diagram above, the process 1 has resource 1 and needs to acquire resource 2. Similarly process 2 has resource 2 and needs to acquire resource 1. Process 1 and process 2 are in deadlock as each of them needs the other’s resource to complete their execution but neither of them is willing to relinquish their resources.

4. Deadlock characterization A deadlock state can occur when the following four circumstances hold simultaneously within a system: Mutual exclusion: At least there should be one resource that has to be held in a non-sharable manner. Only a single process at a time can utilize the resource. If other process demands that resource, the requesting process must be postponed until the resource gets released. Hold and wait: A job must be holding at least one single resource and waiting to obtain supplementary resources which are currently being held by several other processes.

5. Deadlock characterization A deadlock state can occur when the following four circumstances hold simultaneously within a system: No preemption: In which one process cannot take the resources of other processes by force. A resource cannot be taken from a process unless the process releases the resource Circular wait: The circular wait situation implies the hold-and-wait state or condition, and hence all the four conditions are not completely independent. They are interconnected among each other.

6. There is some basic facts regarding a system’s deadlock issue. Those are, If all the 4 characterization occurs simultaneously then there will be deadlock present in the system. As a result, if the graph contains no cycle then there will be no deadlock present in the system. But when a graph contains a cycle, then there can be two conditions present at the system, If there is only one instance present per resources then the deadlock will be present. But if there are more than one instance per resources then there will be not deadlock. The state of the system informs that if resources are allocated to different processes then the system undergoes deadlock or not. 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. If the system can’t allocate resources to the process safely, then the system is in an unsafe state. Unsafe state system may lead to deadlock but not always.

7. Handling deadlocks Deadlock Prevention: Preventing deadlocks by constraining how requests for resources can be made in the system and how they are handled (system design). The goal is to ensure that at least one of the necessary conditions(Mutual exclusion, Hold and wait, No preemption, Circular wait) for deadlock can never hold. Deadlock Avoidance: The system dynamically considers every request and decides whether it is safe to grant it at this point. The system requires additional apriori information regarding the overall potential use of each resource for each process.. Allows more concurrency. Deadlock Detection: Always grant resource request when possible. Periodically check for deadlocks. If a deadlock exists, recover from it. Ignore the problem...

8. Avoidance algorithms Single instance of a resource type Multiple instance of a resource type

9. Banker’s algorithm It is a banker algorithm used to avoid deadlock and allocate resources safely to each process in the computer system. The 'S-State’ or the safe state examines all possible tests or activities before deciding whether the allocation should be allowed to each process. It also helps the operating system to successfully share the resources between all the processes. The banker's algorithm is named because it checks whether a person should be sanctioned a loan amount or not to help the bank system safely simulate allocation resources.

10. Terms In order to implement this algorithm, we need to know about three things. How much each process can request for each resource in the system. How much each process is currently holding each resource in a system. The number of each resource currently available in the system.

11. Terms If n is the number of processes, and m is the number of each type of resource used in a computer system, Available: It is an array of length 'm' that defines each type of resource available in the system. When Available[j] = K, means that 'K' instances of Resources type R[j] are available in the system. Max: It is a [n x m] matrix that indicates each process P[ i ] can store the maximum number of resources R[j] (each type) in a system. Allocation: It is a matrix of m x n orders that indicates the type of resources currently allocated to each process in the system. When Allocation [ i , j] = K, it means that process P[ i ] is currently allocated K instances of Resources type R[j] in the system. Need: It is an M x N matrix sequence representing the number of remaining resources for each process. When the Need[ i ] [j] = k, then process P[ i ] may require K more instances of resources type Rj to complete the assigned work. Nedd [ i ][j] = Max[ i ][j] - Allocation[ i ][j]. Finish: It is the vector of the order m. It includes a Boolean value (true/false) indicating whether the process has been allocated to the requested resources, and all resources have been released after finishing its task.

12. Example Process Allocation MAX AVAILABLE A B C A B C A B C P1 1 7 5 3 3 3 2 P2 2 3 2 2 P3 3 2 9 2 P4 2 1 1 2 2 2 P5 2 4 3 3 NEED (max-allocation) A B C 7 4 3 1 2 2 6 1 1 4 3 1

13. Example (Cont.) Available Resources of A, B and C are 3, 3, and 2. Now we check if each type of resource request is available for each process. So, among all the processes, process 2 follows the condition. For Process P2: Need <= Available 1, 2, 2 <= 3, 3, 2; condition TRUE So, Available Resources = 3,3,2 – 1,2,2 = 2,1,2 After the process 2 is complete, New available resources: Available + Allocation(With the allocation resources from start) = 2,1,2 + 1,2,2 + 2, 0,0 = 5,3,2 Now, in the same way we will look for other processed which satisfies this condition. For Process P4: Need <= Available 0,1,1<= 5,3,2condition; TRUE So, Available Resources = 5,3,2 – 0,1,1 = 5,2,1 After the process 4 is complete, New available resources: Available + Allocation(With the allocation resources from start) = 5,2,1 + 0,1,1 + 2, 1,1 = 7,4,3 P2 1 2 2 NEED P4 1 1 NEED

14. Example (CONT..) Available Resources of A, B and C are 3, 3, and 2. For Process P5: Need <= Available 4,3,1<= 7, 4, 3; condition TRUE So, Available Resources = 7,4,3 – 4,3,1 = 3,1,2 After the process 5 is complete, New available resources: Available + Allocation(With the allocation resources from start) = 3,1,2 + 4,3,1 + 0,0,2 = 7,4,5 Now, in the same way we will look for other processed which satisfies this condition. For Process P1: Need <= Available 7,4,3<= 7,4,5; condition TRUE So, Available Resources = 7,4,5 – 7,4,3 = 0,0,2 After the process 4 is complete, New available resources: Available + Allocation(With the allocation resources from start) = 0,0,2 + 7,4,3 + 0, 1,0 = 7,5,5 P5 1 2 2 NEED P4 1 1 NEED

15. Example (CONT..) Available Resources of A, B and C are 3, 3, and 2. For Process P3: Need <= Available 6,0,0 <= 7, 5, 5; condition TRUE So, Available Resources = 7,5,5 – 6,0,0 = 1,5,5 After the process 5 is complete, New available resources: Available + Allocation(With the allocation resources from start) = 1,5,5 + 6,0,0 + 3,0,2 = 10,5, 7 P3 6 NEED Hence, we execute the banker's algorithm to find the safe state and the safe sequence like P2, P4, P5, P1 and P3.

16. advantages It contains various resources that meet the requirements of each process. Each process should provide information to the operating system for upcoming resource requests, the number of resources, and how long the resources will be held. It helps the operating system manage and control process requests for each type of resource in the computer system. The algorithm has a Max resource attribute that represents indicates each process can hold the maximum number of resources in a system. Disadvantages It requires a fixed number of processes, and no additional processes can be started in the system while executing the process. The algorithm does no longer allows the processes to exchange its maximum needs while processing its tasks. Each process has to know and state their maximum resource requirement in advance for the system. The number of resource requests can be granted in a finite time, but the time limit for allocating the resources is one year.

17. Thank you MD. Anisur Rahman 192-15-2825(pc-b)