{"id":180,"date":"2018-07-19T11:42:53","date_gmt":"2018-07-19T11:42:53","guid":{"rendered":"http:\/\/csp3.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=180"},"modified":"2018-08-07T10:30:40","modified_gmt":"2018-08-07T10:30:40","slug":"deadlocks-detection-and-recovery","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/chapter\/deadlocks-detection-and-recovery\/","title":{"rendered":"Deadlocks \u2013 Detection and Recovery"},"content":{"raw":"
\r\n\r\n \r\n

19<\/strong>.1 Introduction<\/strong><\/p>\r\n \r\n

In a multi-programming environment, many processes compete for a finite number of resources. If the resources requested by a process are not available, the process waits. If the resources requested by this process are held by other waiting processes, the situation may lead to a deadlock. The different ways to handle deadlocks are deadlock prevention, deadlock avoidance, deadlock detection and recovery.<\/p>\r\n \r\n

In this module we will learn how to detect deadlocks. We will also learn how to recover from deadlocks, when deadlocks occur.<\/p>\r\n \r\n

19.2. Deadlock Detection\u00a0<\/strong><\/p>\r\n \r\n

If there is no deadlock prevention or deadlock avoidance algorithm running in the system, deadlock situation may occur. In this case, it is necessary to detect deadlocks and recover from them. Two methods are explained in this section to detect deadlocks. The first method detects deadlocks when there is only one instance of each resource type. This method uses a variant of the resource-allocation graph. The second method detects deadlocks even when there are multiple instances of each resource type. The second method uses a variant of the banker\u2019s algorithm.<\/p>\r\n \r\n

19.2.1\u00a0 Deadlock Detection \u2013 Single Instance of Each Resource Type\u00a0<\/strong><\/p>\r\n \r\n

The system maintains a wait-for <\/em>graph for detecting deadlocks. The wait-for graph is a variant of the resource-allocation graph. In the wait-for graph, the nodes are processes. If there is an edge P<\/em>i <\/em>\u00ae P<\/em>j<\/em>, then it means that process P<\/em>i <\/em>is waiting for process P<\/em>j<\/em>. The corresponding resource-allocation graph would have had edges P<\/em>i <\/em>\u00ae R<\/em>q <\/em>and R<\/em>q <\/em>\u00ae P<\/em>j <\/em>which means that P<\/em>i is waiting for resource R<\/em>q and R<\/em>q is held by resource P<\/em>j. In the wait-for graph, the resource node is removed and there is an edge from P<\/em>i <\/em>\u00ae P<\/em>j<\/em>. Figure 19.1 shows a resource-allocation graph and the corresponding wait-for graph.<\/p>\r\n \r\n

To detect deadlocks from the wait-for graph, it is required to periodically invoke an algorithm that searches for a cycle in the wait-for graph. If there is a cycle in the wait-for graph, then it means that there is a deadlock in the system. If there are no cycles, then it means that there is no deadlock in the system. In the wait-for graph shown in Figure 19.1, there is a cycle P<\/em>1\u00aeP<\/em>2\u00aeP<\/em>3\u00aeP<\/em>4\u00aeP<\/em>1. Hence, the system is in a deadlocked state. An algorithm to detect a cycle in a graph requires an order of n<\/em>2 operations, where n <\/em>is the number of vertices in the graph.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Fig. 19.1 Resource-Allocation Graph and Corresponding wait-for graph<\/p>\r\n \r\n\r\nThe disadvantage of this method is that it is not suitable for a resource-allocation system with multiple instances of each resource type.\r\n\r\n \r\n\r\n19.2.2\u00a0 Deadlock Detection \u2013 Several Instances of a Resource Type<\/strong>\r\n\r\n \r\n\r\nIn \u00a0this \u00a0subsection \u00a0we \u00a0learn \u00a0a \u00a0deadlock \u00a0detection \u00a0algorithm \u00a0that \u00a0will \u00a0detect deadlocks when there are multiple instances of each resource type.\r\n\r\n \r\n\r\nLet n <\/em>denote the number of processes and m <\/em>denote the number of resource types present in the system.\r\n\r\n \r\n\r\nData Structures Used in the Algorithm:\u00a0<\/strong>\r\n\r\n<\/div>\r\n

\r\n
    \r\n \t
  • Available:\u00a0<\/em><\/strong>A vector of length\u00a0m\u00a0<\/em>indicates the number of available resources of each type<\/strong><\/li>\r\n<\/ul>\r\n\r\n\r\n\r\n\r\n
    A<\/strong><\/td>\r\nB<\/strong><\/td>\r\nC<\/strong><\/td>\r\n<\/tr>\r\n
    2<\/td>\r\n3<\/td>\r\n0<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

    In the example shown above, there are three resource types A, B and C. The number of available instances of resource types A, B and C are 2, 3 and 0 respectively.<\/p>\r\n \r\n\r\n\u2022\u00a0 \u00a0Allocation: <\/em><\/strong>An n <\/em>x m <\/em>matrix defines the number of resources of each type currently allocated to each process. <\/strong>The n <\/em>rows correspond to n <\/em>processes and the m <\/em>columns correspond to the m <\/em>resource types.\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    <\/td>\r\nA B C<\/em><\/strong><\/td>\r\n<\/tr>\r\n
    P<\/em>0<\/td>\r\n0 1 0<\/td>\r\n<\/tr>\r\n
    P<\/em>1<\/td>\r\n2 0 0<\/td>\r\n<\/tr>\r\n
    P<\/em>2<\/td>\r\n3 0 2<\/td>\r\n<\/tr>\r\n
    P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

    In the example shown above, there are three resource types A, B and C and four processes P<\/em>0, P<\/em>1, P<\/em>2 \u00a0and P<\/em>3. The number of instances of each resource type\u00a0currently allocated to each process is shown. Process <\/span>P<\/em>0 is currently allocated 0 instances of resource type A, 1 instance of resource type B and 0 instances of resource type C. Similarly, the current allocation of the other processes <\/span>P<\/em>1, <\/span>P<\/em>2 and <\/span>P<\/em>3 are also shown.<\/span><\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n\r\n\u2022\u00a0 \u00a0\u00a0Request:\u00a0<\/em>An n <\/em>x m <\/em>matrix indicates the current request of each process<\/strong>. If Request <\/em>[i,j] = k<\/em>, then process P<\/em>i <\/em>is requesting k <\/em>more instances of resource type R<\/em>j<\/em>\r\n

    A B C<\/em><\/strong><\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    P<\/em>0<\/td>\r\n7 5 3<\/td>\r\n<\/tr>\r\n
    P<\/em>1<\/td>\r\n3 2 2<\/td>\r\n<\/tr>\r\n
    P<\/em>2<\/td>\r\n9 0 2<\/td>\r\n<\/tr>\r\n
    P<\/em>3<\/td>\r\n2 2 2<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

    In the example shown above, there are three resource types A, B and C and four processes P<\/em>0, P<\/em>1, P<\/em>2 and P<\/em>3. The number of instances of each resource type requested by each process is shown. Process P<\/em>0 is requesting 7 instances of resource type A, 5 instances of resource type B and 3 instances of resource type\u00a0C. Similarly, the request of the other processes P<\/em>1, P<\/em>2 and P<\/em>3 are also shown.<\/p>\r\n \r\n\r\nNotations Used<\/strong>\r\n\r\n \r\n\r\nIf X <\/em>and Y <\/em>are vectors of length n<\/em>,\r\n

    \u2013\u00a0\u00a0\u00a0 X <\/em>\u2264 Y <\/em>iff X<\/em>[i<\/em>] \u2264 Y<\/em>[i<\/em>] for all i <\/em>= 1,2,\u2026,n<\/em><\/p>\r\nThat is, the i<\/em>th element of vector X is less than or equal to the i<\/em>th element of vector Y, for all i<\/em>.\r\n\r\n \r\n\r\nConsider the following vectors X and Y\r\n

    X <\/em>= (1,7,3,2), Y <\/em>= (0,3,2,1)<\/p>\r\n \r\n

    In the above example, Y <\/em>\u2264 X <\/em>because each element of vector Y is less than or equal to the corresponding element of vector X. That is, the first element of Y is less than or equal to the first element of X and so on. Also, note that, Y < X, <\/em>if Y <\/em>\u2264 X <\/em>and Y<\/em>\u2260 X<\/em><\/p>\r\n \r\n\r\nEach row in the matrices Allocation and Request are treated as vectors and referred to as Allocationi <\/em>and Requesti <\/em>respectively.\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n\r\nThe deadlock algorithm which is a variant of the Banker\u2019s algorithm is given\u00a0below:\r\n\r\n \r\n\r\nDetection Algorithm\u00a0<\/strong>\r\n\r\n<\/div>\r\n
    \r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0 Let Work <\/em>and Finish <\/em>be vectors of length m <\/em>and n<\/em>, respectively. Initialize:\r\n

    (a)\u00a0 Work <\/em>= Available<\/em><\/p>\r\n

    (b)\u00a0 For i <\/em>= 1,2, \u2026, n<\/em>, if Allocation<\/em>i \u00a0<\/em>\u00b9 0, then Finish<\/em>[i] = false; otherwise,<\/p>\r\n

    Finish<\/em>[i] = <\/span>true<\/em>.<\/span><\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n\r\n2.\u00a0\u00a0\u00a0 Find an index i <\/em>such that both:\r\n

    (a)\u00a0\u00a0Finish<\/em>[i<\/em>] = false<\/em><\/p>\r\n

    (b)\u00a0\u00a0Request<\/em>i <\/em>\u00a3 Work<\/em><\/p>\r\n

    If no such i <\/em>exists, go to step 4.<\/p>\r\n \r\n\r\n3.\u00a0\u00a0\u00a0 Work <\/em>= Work <\/em>+ Allocation<\/em>i <\/em>\r\n

    Finish<\/em>[i<\/em>] = true<\/em><\/p>\r\n

    go to step 2.<\/p>\r\n \r\n\r\n4.\u00a0\u00a0\u00a0 If Finish<\/em>[i<\/em>] == false, for some i<\/em>, 1 \u00a3 i <\/em>\u00a3\u00a0\u00a0\u00a0\u00a0 n<\/em>, then the system is in deadlock state.\r\n\r\n \r\n\r\nMoreover, if Finish<\/em>[i<\/em>] == false<\/em>, then P<\/em>i <\/em>is deadlocked.\r\n\r\n \r\n

    This algorithm requires an order of O(m <\/em>x n<\/em>2) operations to detect whether the system is in deadlocked state. The working of this algorithm can be understood by an example.<\/p>\r\n \r\n

    Example of Detection Algorithm<\/strong><\/p>\r\n \r\n

    Consider 5 processes P<\/em>0 through P<\/em>4; 3 resource types A<\/em>, B <\/em>and C<\/em>. There are 7 instances of A<\/em>, 2 instances of B <\/em>and 6 instances of C<\/em>.<\/p>\r\n \r\n\r\nThe snapshot at time T<\/em>0 is given below:\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    <\/td>\r\nAllocation<\/em> A B C<\/em><\/td>\r\nRequest<\/em> A B C<\/em><\/td>\r\nAvailable <\/em>\u00a0A B C<\/em><\/td>\r\n<\/tr>\r\n
    P<\/em>0<\/td>\r\n0 1 0<\/td>\r\n0 0 0<\/td>\r\n0 0 0<\/td>\r\n<\/tr>\r\n
    P<\/em>1<\/td>\r\n2 0 0<\/td>\r\n2 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>2<\/td>\r\n3 0 3<\/td>\r\n0 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n1 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n0 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nWe now simulate the algorithm for the above example.\r\n\r\nInitially, Available = (0,0,0); Finish[i] = false for i =\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0,1,2,3,4\r\n\r\ni = 0\r\n\r\nWe check if Request0 \u2264 Available?\u00a0 Yes\r\n\r\nTherefore, Work = Work + Allocation0 =(0,0,0) + (0,1,0) = (0,1,0)\r\n\r\nFinish[0] = true , P<\/em>0 added to safe sequence < P<\/em>0>\r\n

    Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Available<\/em><\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    \u00a0<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\n<\/tr>\r\n
    P<\/em>0<\/td>\r\n0 1 0<\/td>\r\n0 0 0<\/td>\r\n0 0 0<\/td>\r\n<\/tr>\r\n
    P<\/em>1<\/td>\r\n2 0 0<\/td>\r\n2 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>2<\/td>\r\n3 0 3<\/td>\r\n0 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n1 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n0 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n
    \r\n\r\n \r\n\r\nWork = (0,1,0);\r\n\r\nIs Request1 \u2264 Available?\u00a0\u00a0 No\r\n\r\nSince Request1 is not less than Available, check the next process.\r\n

    Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Available<\/em><\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    \u00a0<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\n<\/tr>\r\n
    P<\/em>0<\/td>\r\n0 1 0<\/td>\r\n0 0 0<\/td>\r\n0 0 0<\/td>\r\n<\/tr>\r\n
    P<\/em>1<\/td>\r\n2 0 0<\/td>\r\n2 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>2<\/td>\r\n3 0 3<\/td>\r\n0 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n1 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n0 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nWork = (0,1,0);\r\n\r\nIs Request2 \u2264 Available?\u00a0\u00a0 Yes\r\n\r\nWork = Work + Allocation2 =(0,1,0) + (3,0,3) = (3,1,3) Finish[2] = true , P<\/em>2 added to safe sequence < P<\/em>0, P<\/em>2>\r\n

    \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Available<\/em><\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    \u00a0<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\n<\/tr>\r\n
    P<\/em>0<\/td>\r\n0 1 0<\/td>\r\n0 0 0<\/td>\r\n0 0 0<\/td>\r\n<\/tr>\r\n
    P<\/em>1<\/td>\r\n2 0 0<\/td>\r\n2 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>2<\/td>\r\n3 0 3<\/td>\r\n0 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n1 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n0 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nWork = (3,1,3);\r\n\r\nIs Request3 \u2264 Available?\u00a0\u00a0 Yes\r\n\r\nWork = Work + Allocation3 =(3,1,3) + (2,1,1) = (5,2,4) Finish[3] = true,\r\n\r\nP<\/em>3 added to safe sequence and the safe sequence is now < P<\/em>0, P<\/em>2, P<\/em>3 <\/em>>\r\n

    Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Available<\/em><\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    \u00a0<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\n<\/tr>\r\n
    P<\/em>0<\/td>\r\n0 1 0<\/td>\r\n0 0 0<\/td>\r\n0 0 0<\/td>\r\n<\/tr>\r\n
    P<\/em>1<\/td>\r\n2 0 0<\/td>\r\n2 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>2<\/td>\r\n3 0 3<\/td>\r\n0 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n1 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n0 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nWork = (5,2,4);\r\n\r\nIs Request4 \u2264 Available?\u00a0\u00a0 Yes\r\n\r\nWork = Work + Allocation4 =(5,2,4) + (0,0,2) = (5,2,6) Finish[4] = true,\r\n\r\nP<\/em>4 added to safe sequence and the safe sequence is < P<\/em>0, P<\/em>2, P<\/em>3<\/em>, P<\/em>4 <\/em>>\r\n\r\n<\/div>\r\n \r\n

    Now, we check again from the beginning all the other processes that were not added to the safe sequence.<\/span><\/p>\r\n\r\n

    \r\n

    Allocation\u00a0 \u00a0 \u00a0 \u00a0 Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Available<\/em><\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    \u00a0<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\n<\/tr>\r\n
    P<\/em>0<\/td>\r\n0 1 0<\/td>\r\n0 0 0<\/td>\r\n0 0 0<\/td>\r\n<\/tr>\r\n
    P<\/em>1<\/td>\r\n2 0 0<\/td>\r\n2 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>2<\/td>\r\n3 0 3<\/td>\r\n0 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n1 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n0 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nWork = (5,2,6);\r\n\r\nIs Request1 \u2264 Available?\u00a0\u00a0 Yes\r\n\r\nWork = Work + Allocation1 =(5,2,6) + (2,0,0) = (7,2,6) Finish[1] = true,\r\n\r\nP<\/em>1 added to safe sequence and the safe sequence now is < P<\/em>0, P<\/em>2, P<\/em>3<\/em>, P<\/em>4<\/em>, P<\/em>1 <\/em>>\r\n

    Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Available<\/em><\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    \u00a0<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\n<\/tr>\r\n
    P<\/em>0<\/td>\r\n0 1 0<\/td>\r\n0 0 0<\/td>\r\n0 0 0<\/td>\r\n<\/tr>\r\n
    P<\/em>1<\/td>\r\n2 0 0<\/td>\r\n2 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>2<\/td>\r\n3 0 3<\/td>\r\n0 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n1 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n0 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nSequence <P<\/em>0, P<\/em>2, P<\/em>3, P<\/em>4, P<\/em>1> now results in Finish<\/em>[i<\/em>] = true for all i<\/em>.\r\n\r\n \r\n

    There can be more than one safe sequence, that is there can be correct safe sequences other than <P<\/em>0, P<\/em>2, P<\/em>3, P<\/em>1, P<\/em>4>. We have found one safe sequence. Since there is at least one safe sequence, the system is in a safe state. There is no deadlock in the system.<\/p>\r\n \r\n

    Let process P<\/em>2 now make an additional request for an instance of resource type C. The Request matrix is changed as shown below, after including the request of an instance of resource type C by process P<\/em>2.<\/p>\r\n

    Request<\/em> A B C<\/em><\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    P<\/em>0<\/td>\r\n0 0 0<\/td>\r\n<\/tr>\r\n
    P<\/em>1<\/td>\r\n2 0 2<\/td>\r\n<\/tr>\r\n
    P<\/em>2<\/td>\r\n0 0 1<\/td>\r\n<\/tr>\r\n
    P<\/em>3<\/td>\r\n1 0 0<\/td>\r\n<\/tr>\r\n
    P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<\/div>\r\n \r\n

    Now, let us check if the system will be in a safe state. The deadlock detection algorithm is run again.<\/span><\/p>\r\n\r\n

    \r\n

    Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Available<\/em><\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    \u00a0<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\n<\/tr>\r\n
    P<\/em>0<\/td>\r\n0 1 0<\/td>\r\n0 0 0<\/td>\r\n0 0 0<\/td>\r\n<\/tr>\r\n
    P<\/em>1<\/td>\r\n2 0 0<\/td>\r\n2 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>2<\/td>\r\n3 0 3<\/td>\r\n0 0 1<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n1 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n0 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nInitially, Work = Available = (0,0,0); Finish[i] = false for i =\u00a0\u00a0 0,1,2,3,4 When i = 0,\r\n\r\nCheck if Request0 \u2264 Available?\u00a0 Yes\r\n\r\nWork = Work + Allocation0 =(0,0,0) + (0,1,0) = (0,1,0) Finish[0] = true, P<\/em>0 is added to safe sequence < P<\/em>0>\r\n

    Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Available<\/em><\/p>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    <\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\nA B C<\/em><\/td>\r\n<\/tr>\r\n
    P<\/em>0<\/td>\r\n0 1 0<\/td>\r\n0 0 0<\/td>\r\n0 0 0<\/td>\r\n<\/tr>\r\n
    P<\/em>1<\/td>\r\n2 0 0<\/td>\r\n2 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>2<\/td>\r\n3 0 3<\/td>\r\n0 0 1<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n1 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
    P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n0 0 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nWork is now (0,1,0);\r\n\r\nIs Request1 \u2264 Available? No\r\n\r\nIs Request2 \u2264 Available? No\r\n\r\nIs Request3 \u2264 Available? No\r\n\r\nIs Request4 \u2264 Available? No\r\n\r\n \r\n

    Since the request of all the processes cannot be allocated, the system is not in a safe state. Though it possible to reclaim the resources held by process P<\/em>0, there are insufficient resources to fulfill other processes\u2019 requests. Thus, a deadlock exists, consisting of processes P<\/em>1, P<\/em>2, P<\/em>3, and P<\/em>4.<\/p>\r\n \r\n\r\nDeadlock Detection Algorithm Usage<\/strong>\r\n\r\n \r\n\r\nWhen should we invoke the detection algorithm?\r\n\r\n \r\n\r\nThis depends on the answers to the following questions.\r\n\r\n\u2013 How often is a deadlock likely to occur?\r\n\r\n\u2013 How many processes will be affected by the deadlock when it happens?\r\n\r\n \r\n

    If deadlocks occur frequently, then it is necessary to invoke the detection algorithm frequently. If detection is not done, the resources allocated to deadlocked processes will be idle. The number of processes involved in the deadlock cycle may\u00a0also grow.<\/span><\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n

    Deadlocks occur when a process makes a request that cannot be granted immediately. Therefore, the detection algorithm can be invoked every time a request for allocation cannot be granted immediately. During the detection process, not only the set of processes that are deadlocked are identified, but also the specific process that caused the deadlock is identified. If the cycle is completed by the most recent request, the process that requested the most recent request is identified as responsible for the deadlock. But invoking the deadlock detection algorithm each and every time a request is made results in considerable overhead in computation time.<\/p>\r\n \r\n

    Therefore, the other possibility is to invoke the detection algorithm at less frequent intervals. The detection algorithm may be invoked once per hour or when the CPU utilization falls below 40 percent. In this case there may be many cycles in the graph and it may not be possible to tell which process caused the deadlock.<\/p>\r\n \r\n

    19.3\u00a0\u00a0 Recovery from Deadlocks<\/strong><\/p>\r\n \r\n

    Once deadlocks are detected, it is necessary to recover from deadlocks. There are different ways in which the system can recover from deadlocks. One method is to inform the operator that a deadlock has occurred. The operator deals with the deadlock manually. The second method is to let the system recover from the deadlock automatically. The third method is to break the deadlock. To break the deadlock, there are two ways. One is to abort one or more processes to break the circular wait (process termination). The second is to preempt some resources from one or more of the deadlocked processes (resource preemption).<\/p>\r\n \r\n

    19.3.1\u00a0 Recovery from Deadlock: Process Termination<\/strong><\/p>\r\n \r\n

    Termination of processes can be done in two ways. One is to abort all the deadlocked processes. This method will break the deadlock, but the results of all partial computations done by the aborted processes must be discarded and recomputed later. The second way is to abort one process at a time until the deadlock cycle is eliminated. This method involves a lot of overhead, because, after each process is aborted, deadlock-detection algorithm must be invoked to check if the deadlock still exists.<\/p>\r\n \r\n

    When there are many processes involved in the deadlock, it is necessary to choose a process to terminate first. In which order should we choose a process to abort? There are many factors based on which the process to be aborted can be chosen:<\/p>\r\n \r\n\r\n\u2013\u00a0 Priority of the process (process with the least priority is chosen)\r\n\r\n\u2013\u00a0 How long process has computed, and how much longer to completion (the process that has done the least computations is chosen)\r\n\r\n\u2013\u00a0 Resources the process has used (the process that has used less number of resources is chosen)\r\n\r\n\u2013\u00a0 Resources \u00a0process needs\u00a0 to \u00a0complete \u00a0(the\u00a0 process\u00a0 that \u00a0needs\u00a0 many resources is chosen)\r\n\r\n\u2013\u00a0 How many processes will need to be terminated\r\n\r\n\u2013\u00a0 Is \u00a0process \u00a0interactive \u00a0or \u00a0batch? \u00a0(batch \u00a0processes \u00a0are \u00a0chosen \u00a0to \u00a0be terminated earlier than interactive processes)\r\n\r\n<\/div>\r\n \r\n

    19.3.2\u00a0 Recovery from Deadlock: Resource Preemption<\/strong><\/p>\r\n \r\n

    To recover from deadlocks, resources can be preempted from the deadlocked processes. When resources are preempted, it is necessary to consider certain issues. The issues are discussed below:<\/p>\r\n\r\n

      \r\n \t
    • Selecting a victim<\/li>\r\n<\/ul>\r\n \r\n

      It is necessary to select the victim process from which the resources are to be preempted. The victim process has to be selected such that the cost is minimized. Cost factors may include the number of resources a deadlock process is holding and the amount of time a deadlocked process has thus far consumed during its execution.<\/p>\r\n\r\n

        \r\n \t
      • Rollback<\/li>\r\n<\/ul>\r\n \r\n

        If a resource is preempted from a process, what to do with the process? The process cannot continue, because it is missing some needed resource. Therefore, the process must be rolled back to some safe state and the process must be restarted from that state. But, the problem is that it is difficult to determine a safe state. Therefore a total rollback might have to be done or the process must be aborted and restarted again.<\/p>\r\n\r\n

          \r\n \t
        • Starvation<\/li>\r\n<\/ul>\r\n \r\n

          While selecting a process for preempting resources, the same process may always be picked as victim. In that case, that process may be starved of resources and may not be able to complete its work. To reduce starvation, the number of rollbacks may also be included in the cost factor.<\/p>\r\n \r\n

          19.4\u00a0 Summary<\/strong><\/p>\r\n \r\n

          This module discussed deadlock detection algorithms when there is a single instance for each resource type (wait-for graph) and when there are multiple instances of resources (Banker\u2019s algorithm). This module also discussed how the system can recover from deadlocks.<\/p>\r\n \r\n\r\n \r\n

          References<\/strong><\/p>\r\n\r\n

            \r\n \t
          1. Abraham Silberschatz, \u00a0Peter \u00a0B. \u00a0Galvin, \u00a0Greg \u00a0Gagne, \u00a0\u201cOperating \u00a0System Concepts\u201d, Ninth Edition, John Wiley & Sons Inc., 2012.<\/li>\r\n<\/ol>","rendered":"
            \n

             <\/p>\n

            19<\/strong>.1 Introduction<\/strong><\/p>\n

             <\/p>\n

            In a multi-programming environment, many processes compete for a finite number of resources. If the resources requested by a process are not available, the process waits. If the resources requested by this process are held by other waiting processes, the situation may lead to a deadlock. The different ways to handle deadlocks are deadlock prevention, deadlock avoidance, deadlock detection and recovery.<\/p>\n

             <\/p>\n

            In this module we will learn how to detect deadlocks. We will also learn how to recover from deadlocks, when deadlocks occur.<\/p>\n

             <\/p>\n

            19.2. Deadlock Detection\u00a0<\/strong><\/p>\n

             <\/p>\n

            If there is no deadlock prevention or deadlock avoidance algorithm running in the system, deadlock situation may occur. In this case, it is necessary to detect deadlocks and recover from them. Two methods are explained in this section to detect deadlocks. The first method detects deadlocks when there is only one instance of each resource type. This method uses a variant of the resource-allocation graph. The second method detects deadlocks even when there are multiple instances of each resource type. The second method uses a variant of the banker\u2019s algorithm.<\/p>\n

             <\/p>\n

            19.2.1\u00a0 Deadlock Detection \u2013 Single Instance of Each Resource Type\u00a0<\/strong><\/p>\n

             <\/p>\n

            The system maintains a wait-for <\/em>graph for detecting deadlocks. The wait-for graph is a variant of the resource-allocation graph. In the wait-for graph, the nodes are processes. If there is an edge P<\/em>i <\/em>\u00ae P<\/em>j<\/em>, then it means that process P<\/em>i <\/em>is waiting for process P<\/em>j<\/em>. The corresponding resource-allocation graph would have had edges P<\/em>i <\/em>\u00ae R<\/em>q <\/em>and R<\/em>q <\/em>\u00ae P<\/em>j <\/em>which means that P<\/em>i is waiting for resource R<\/em>q and R<\/em>q is held by resource P<\/em>j. In the wait-for graph, the resource node is removed and there is an edge from P<\/em>i <\/em>\u00ae P<\/em>j<\/em>. Figure 19.1 shows a resource-allocation graph and the corresponding wait-for graph.<\/p>\n

             <\/p>\n

            To detect deadlocks from the wait-for graph, it is required to periodically invoke an algorithm that searches for a cycle in the wait-for graph. If there is a cycle in the wait-for graph, then it means that there is a deadlock in the system. If there are no cycles, then it means that there is no deadlock in the system. In the wait-for graph shown in Figure 19.1, there is a cycle P<\/em>1\u00aeP<\/em>2\u00aeP<\/em>3\u00aeP<\/em>4\u00aeP<\/em>1. Hence, the system is in a deadlocked state. An algorithm to detect a cycle in a graph requires an order of n<\/em>2 operations, where n <\/em>is the number of vertices in the graph.<\/p>\n<\/div>\n

            \n

            \"\"<\/p>\n

            Fig. 19.1 Resource-Allocation Graph and Corresponding wait-for graph<\/p>\n

             <\/p>\n

            The disadvantage of this method is that it is not suitable for a resource-allocation system with multiple instances of each resource type.<\/p>\n

             <\/p>\n

            19.2.2\u00a0 Deadlock Detection \u2013 Several Instances of a Resource Type<\/strong><\/p>\n

             <\/p>\n

            In \u00a0this \u00a0subsection \u00a0we \u00a0learn \u00a0a \u00a0deadlock \u00a0detection \u00a0algorithm \u00a0that \u00a0will \u00a0detect deadlocks when there are multiple instances of each resource type.<\/p>\n

             <\/p>\n

            Let n <\/em>denote the number of processes and m <\/em>denote the number of resource types present in the system.<\/p>\n

             <\/p>\n

            Data Structures Used in the Algorithm:\u00a0<\/strong><\/p>\n<\/div>\n

            \n
              \n
            • Available:\u00a0<\/em><\/strong>A vector of length\u00a0m\u00a0<\/em>indicates the number of available resources of each type<\/strong><\/li>\n<\/ul>\n\n\n\n\n
              A<\/strong><\/td>\nB<\/strong><\/td>\nC<\/strong><\/td>\n<\/tr>\n
              2<\/td>\n3<\/td>\n0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

               <\/p>\n

              In the example shown above, there are three resource types A, B and C. The number of available instances of resource types A, B and C are 2, 3 and 0 respectively.<\/p>\n

               <\/p>\n

              \u2022\u00a0 \u00a0Allocation: <\/em><\/strong>An n <\/em>x m <\/em>matrix defines the number of resources of each type currently allocated to each process. <\/strong>The n <\/em>rows correspond to n <\/em>processes and the m <\/em>columns correspond to the m <\/em>resource types.<\/p>\n\n\n\n\n\n\n\n
              <\/td>\nA B C<\/em><\/strong><\/td>\n<\/tr>\n
              P<\/em>0<\/td>\n0 1 0<\/td>\n<\/tr>\n
              P<\/em>1<\/td>\n2 0 0<\/td>\n<\/tr>\n
              P<\/em>2<\/td>\n3 0 2<\/td>\n<\/tr>\n
              P<\/em>3<\/td>\n2 1 1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

               <\/p>\n

              In the example shown above, there are three resource types A, B and C and four processes P<\/em>0, P<\/em>1, P<\/em>2 \u00a0and P<\/em>3. The number of instances of each resource type\u00a0currently allocated to each process is shown. Process <\/span>P<\/em>0 is currently allocated 0 instances of resource type A, 1 instance of resource type B and 0 instances of resource type C. Similarly, the current allocation of the other processes <\/span>P<\/em>1, <\/span>P<\/em>2 and <\/span>P<\/em>3 are also shown.<\/span><\/p>\n<\/div>\n

              \n

               <\/p>\n

              \u2022\u00a0 \u00a0\u00a0Request:\u00a0<\/em>An n <\/em>x m <\/em>matrix indicates the current request of each process<\/strong>. If Request <\/em>[i,j] = k<\/em>, then process P<\/em>i <\/em>is requesting k <\/em>more instances of resource type R<\/em>j<\/em><\/p>\n

              A B C<\/em><\/strong><\/p>\n\n\n\n\n\n\n
              P<\/em>0<\/td>\n7 5 3<\/td>\n<\/tr>\n
              P<\/em>1<\/td>\n3 2 2<\/td>\n<\/tr>\n
              P<\/em>2<\/td>\n9 0 2<\/td>\n<\/tr>\n
              P<\/em>3<\/td>\n2 2 2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

               <\/p>\n

              In the example shown above, there are three resource types A, B and C and four processes P<\/em>0, P<\/em>1, P<\/em>2 and P<\/em>3. The number of instances of each resource type requested by each process is shown. Process P<\/em>0 is requesting 7 instances of resource type A, 5 instances of resource type B and 3 instances of resource type\u00a0C. Similarly, the request of the other processes P<\/em>1, P<\/em>2 and P<\/em>3 are also shown.<\/p>\n

               <\/p>\n

              Notations Used<\/strong><\/p>\n

               <\/p>\n

              If X <\/em>and Y <\/em>are vectors of length n<\/em>,<\/p>\n

              \u2013\u00a0\u00a0\u00a0 X <\/em>\u2264 Y <\/em>iff X<\/em>[i<\/em>] \u2264 Y<\/em>[i<\/em>] for all i <\/em>= 1,2,\u2026,n<\/em><\/p>\n

              That is, the i<\/em>th element of vector X is less than or equal to the i<\/em>th element of vector Y, for all i<\/em>.<\/p>\n

               <\/p>\n

              Consider the following vectors X and Y<\/p>\n

              X <\/em>= (1,7,3,2), Y <\/em>= (0,3,2,1)<\/p>\n

               <\/p>\n

              In the above example, Y <\/em>\u2264 X <\/em>because each element of vector Y is less than or equal to the corresponding element of vector X. That is, the first element of Y is less than or equal to the first element of X and so on. Also, note that, Y < X, <\/em>if Y <\/em>\u2264 X <\/em>and Y<\/em>\u2260 X<\/em><\/p>\n

               <\/p>\n

              Each row in the matrices Allocation and Request are treated as vectors and referred to as Allocationi <\/em>and Requesti <\/em>respectively.<\/p>\n<\/div>\n

              \n

               <\/p>\n

              The deadlock algorithm which is a variant of the Banker\u2019s algorithm is given\u00a0below:<\/p>\n

               <\/p>\n

              Detection Algorithm\u00a0<\/strong><\/p>\n<\/div>\n

              \n

               <\/p>\n

              1.\u00a0\u00a0\u00a0 Let Work <\/em>and Finish <\/em>be vectors of length m <\/em>and n<\/em>, respectively. Initialize:<\/p>\n

              (a)\u00a0 Work <\/em>= Available<\/em><\/p>\n

              (b)\u00a0 For i <\/em>= 1,2, \u2026, n<\/em>, if Allocation<\/em>i \u00a0<\/em>\u00b9 0, then Finish<\/em>[i] = false; otherwise,<\/p>\n

              Finish<\/em>[i] = <\/span>true<\/em>.<\/span><\/p>\n<\/div>\n

              \n

               <\/p>\n

              2.\u00a0\u00a0\u00a0 Find an index i <\/em>such that both:<\/p>\n

              (a)\u00a0\u00a0Finish<\/em>[i<\/em>] = false<\/em><\/p>\n

              (b)\u00a0\u00a0Request<\/em>i <\/em>\u00a3 Work<\/em><\/p>\n

              If no such i <\/em>exists, go to step 4.<\/p>\n

               <\/p>\n

              3.\u00a0\u00a0\u00a0 Work <\/em>= Work <\/em>+ Allocation<\/em>i <\/em><\/p>\n

              Finish<\/em>[i<\/em>] = true<\/em><\/p>\n

              go to step 2.<\/p>\n

               <\/p>\n

              4.\u00a0\u00a0\u00a0 If Finish<\/em>[i<\/em>] == false, for some i<\/em>, 1 \u00a3 i <\/em>\u00a3\u00a0\u00a0\u00a0\u00a0 n<\/em>, then the system is in deadlock state.<\/p>\n

               <\/p>\n

              Moreover, if Finish<\/em>[i<\/em>] == false<\/em>, then P<\/em>i <\/em>is deadlocked.<\/p>\n

               <\/p>\n

              This algorithm requires an order of O(m <\/em>x n<\/em>2) operations to detect whether the system is in deadlocked state. The working of this algorithm can be understood by an example.<\/p>\n

               <\/p>\n

              Example of Detection Algorithm<\/strong><\/p>\n

               <\/p>\n

              Consider 5 processes P<\/em>0 through P<\/em>4; 3 resource types A<\/em>, B <\/em>and C<\/em>. There are 7 instances of A<\/em>, 2 instances of B <\/em>and 6 instances of C<\/em>.<\/p>\n

               <\/p>\n

              The snapshot at time T<\/em>0 is given below:<\/p>\n\n\n\n\n\n\n\n\n
              <\/td>\nAllocation<\/em> A B C<\/em><\/td>\nRequest<\/em> A B C<\/em><\/td>\nAvailable <\/em>\u00a0A B C<\/em><\/td>\n<\/tr>\n
              P<\/em>0<\/td>\n0 1 0<\/td>\n0 0 0<\/td>\n0 0 0<\/td>\n<\/tr>\n
              P<\/em>1<\/td>\n2 0 0<\/td>\n2 0 2<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>2<\/td>\n3 0 3<\/td>\n0 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>3<\/td>\n2 1 1<\/td>\n1 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>4<\/td>\n0 0 2<\/td>\n0 0 2<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

               <\/p>\n

              We now simulate the algorithm for the above example.<\/p>\n

              Initially, Available = (0,0,0); Finish[i] = false for i =\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 0,1,2,3,4<\/p>\n

              i = 0<\/p>\n

              We check if Request0 \u2264 Available?\u00a0 Yes<\/p>\n

              Therefore, Work = Work + Allocation0 =(0,0,0) + (0,1,0) = (0,1,0)<\/p>\n

              Finish[0] = true , P<\/em>0 added to safe sequence < P<\/em>0><\/p>\n

              Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Available<\/em><\/p>\n\n\n\n\n\n\n\n\n
              \u00a0<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\n<\/tr>\n
              P<\/em>0<\/td>\n0 1 0<\/td>\n0 0 0<\/td>\n0 0 0<\/td>\n<\/tr>\n
              P<\/em>1<\/td>\n2 0 0<\/td>\n2 0 2<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>2<\/td>\n3 0 3<\/td>\n0 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>3<\/td>\n2 1 1<\/td>\n1 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>4<\/td>\n0 0 2<\/td>\n0 0 2<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
              \n

               <\/p>\n

              Work = (0,1,0);<\/p>\n

              Is Request1 \u2264 Available?\u00a0\u00a0 No<\/p>\n

              Since Request1 is not less than Available, check the next process.<\/p>\n

              Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Available<\/em><\/p>\n\n\n\n\n\n\n\n\n
              \u00a0<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\n<\/tr>\n
              P<\/em>0<\/td>\n0 1 0<\/td>\n0 0 0<\/td>\n0 0 0<\/td>\n<\/tr>\n
              P<\/em>1<\/td>\n2 0 0<\/td>\n2 0 2<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>2<\/td>\n3 0 3<\/td>\n0 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>3<\/td>\n2 1 1<\/td>\n1 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>4<\/td>\n0 0 2<\/td>\n0 0 2<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

               <\/p>\n

              Work = (0,1,0);<\/p>\n

              Is Request2 \u2264 Available?\u00a0\u00a0 Yes<\/p>\n

              Work = Work + Allocation2 =(0,1,0) + (3,0,3) = (3,1,3) Finish[2] = true , P<\/em>2 added to safe sequence < P<\/em>0, P<\/em>2><\/p>\n

              \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0\u00a0Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Available<\/em><\/p>\n\n\n\n\n\n\n\n\n
              \u00a0<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\n<\/tr>\n
              P<\/em>0<\/td>\n0 1 0<\/td>\n0 0 0<\/td>\n0 0 0<\/td>\n<\/tr>\n
              P<\/em>1<\/td>\n2 0 0<\/td>\n2 0 2<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>2<\/td>\n3 0 3<\/td>\n0 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>3<\/td>\n2 1 1<\/td>\n1 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>4<\/td>\n0 0 2<\/td>\n0 0 2<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

               <\/p>\n

              Work = (3,1,3);<\/p>\n

              Is Request3 \u2264 Available?\u00a0\u00a0 Yes<\/p>\n

              Work = Work + Allocation3 =(3,1,3) + (2,1,1) = (5,2,4) Finish[3] = true,<\/p>\n

              P<\/em>3 added to safe sequence and the safe sequence is now < P<\/em>0, P<\/em>2, P<\/em>3 <\/em>><\/p>\n

              Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Available<\/em><\/p>\n\n\n\n\n\n\n\n\n
              \u00a0<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\n<\/tr>\n
              P<\/em>0<\/td>\n0 1 0<\/td>\n0 0 0<\/td>\n0 0 0<\/td>\n<\/tr>\n
              P<\/em>1<\/td>\n2 0 0<\/td>\n2 0 2<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>2<\/td>\n3 0 3<\/td>\n0 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>3<\/td>\n2 1 1<\/td>\n1 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>4<\/td>\n0 0 2<\/td>\n0 0 2<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

               <\/p>\n

              Work = (5,2,4);<\/p>\n

              Is Request4 \u2264 Available?\u00a0\u00a0 Yes<\/p>\n

              Work = Work + Allocation4 =(5,2,4) + (0,0,2) = (5,2,6) Finish[4] = true,<\/p>\n

              P<\/em>4 added to safe sequence and the safe sequence is < P<\/em>0, P<\/em>2, P<\/em>3<\/em>, P<\/em>4 <\/em>><\/p>\n<\/div>\n

               <\/p>\n

              Now, we check again from the beginning all the other processes that were not added to the safe sequence.<\/span><\/p>\n

              \n

              Allocation\u00a0 \u00a0 \u00a0 \u00a0 Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Available<\/em><\/p>\n\n\n\n\n\n\n\n\n
              \u00a0<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\n<\/tr>\n
              P<\/em>0<\/td>\n0 1 0<\/td>\n0 0 0<\/td>\n0 0 0<\/td>\n<\/tr>\n
              P<\/em>1<\/td>\n2 0 0<\/td>\n2 0 2<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>2<\/td>\n3 0 3<\/td>\n0 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>3<\/td>\n2 1 1<\/td>\n1 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>4<\/td>\n0 0 2<\/td>\n0 0 2<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

               <\/p>\n

              Work = (5,2,6);<\/p>\n

              Is Request1 \u2264 Available?\u00a0\u00a0 Yes<\/p>\n

              Work = Work + Allocation1 =(5,2,6) + (2,0,0) = (7,2,6) Finish[1] = true,<\/p>\n

              P<\/em>1 added to safe sequence and the safe sequence now is < P<\/em>0, P<\/em>2, P<\/em>3<\/em>, P<\/em>4<\/em>, P<\/em>1 <\/em>><\/p>\n

              Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Available<\/em><\/p>\n\n\n\n\n\n\n\n\n
              \u00a0<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\n<\/tr>\n
              P<\/em>0<\/td>\n0 1 0<\/td>\n0 0 0<\/td>\n0 0 0<\/td>\n<\/tr>\n
              P<\/em>1<\/td>\n2 0 0<\/td>\n2 0 2<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>2<\/td>\n3 0 3<\/td>\n0 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>3<\/td>\n2 1 1<\/td>\n1 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>4<\/td>\n0 0 2<\/td>\n0 0 2<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

               <\/p>\n

              Sequence <P<\/em>0, P<\/em>2, P<\/em>3, P<\/em>4, P<\/em>1> now results in Finish<\/em>[i<\/em>] = true for all i<\/em>.<\/p>\n

               <\/p>\n

              There can be more than one safe sequence, that is there can be correct safe sequences other than <P<\/em>0, P<\/em>2, P<\/em>3, P<\/em>1, P<\/em>4>. We have found one safe sequence. Since there is at least one safe sequence, the system is in a safe state. There is no deadlock in the system.<\/p>\n

               <\/p>\n

              Let process P<\/em>2 now make an additional request for an instance of resource type C. The Request matrix is changed as shown below, after including the request of an instance of resource type C by process P<\/em>2.<\/p>\n

              Request<\/em> A B C<\/em><\/p>\n\n\n\n\n\n\n\n
              P<\/em>0<\/td>\n0 0 0<\/td>\n<\/tr>\n
              P<\/em>1<\/td>\n2 0 2<\/td>\n<\/tr>\n
              P<\/em>2<\/td>\n0 0 1<\/td>\n<\/tr>\n
              P<\/em>3<\/td>\n1 0 0<\/td>\n<\/tr>\n
              P<\/em>4<\/td>\n0 0 2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n

               <\/p>\n

              Now, let us check if the system will be in a safe state. The deadlock detection algorithm is run again.<\/span><\/p>\n

              \n

              Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Available<\/em><\/p>\n\n\n\n\n\n\n\n\n
              \u00a0<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\n<\/tr>\n
              P<\/em>0<\/td>\n0 1 0<\/td>\n0 0 0<\/td>\n0 0 0<\/td>\n<\/tr>\n
              P<\/em>1<\/td>\n2 0 0<\/td>\n2 0 2<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>2<\/td>\n3 0 3<\/td>\n0 0 1<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>3<\/td>\n2 1 1<\/td>\n1 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>4<\/td>\n0 0 2<\/td>\n0 0 2<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

               <\/p>\n

              Initially, Work = Available = (0,0,0); Finish[i] = false for i =\u00a0\u00a0 0,1,2,3,4 When i = 0,<\/p>\n

              Check if Request0 \u2264 Available?\u00a0 Yes<\/p>\n

              Work = Work + Allocation0 =(0,0,0) + (0,1,0) = (0,1,0) Finish[0] = true, P<\/em>0 is added to safe sequence < P<\/em>0><\/p>\n

              Allocation\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Request\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0Available<\/em><\/p>\n\n\n\n\n\n\n\n\n
              <\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\nA B C<\/em><\/td>\n<\/tr>\n
              P<\/em>0<\/td>\n0 1 0<\/td>\n0 0 0<\/td>\n0 0 0<\/td>\n<\/tr>\n
              P<\/em>1<\/td>\n2 0 0<\/td>\n2 0 2<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>2<\/td>\n3 0 3<\/td>\n0 0 1<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>3<\/td>\n2 1 1<\/td>\n1 0 0<\/td>\n<\/td>\n<\/tr>\n
              P<\/em>4<\/td>\n0 0 2<\/td>\n0 0 2<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

               <\/p>\n

              Work is now (0,1,0);<\/p>\n

              Is Request1 \u2264 Available? No<\/p>\n

              Is Request2 \u2264 Available? No<\/p>\n

              Is Request3 \u2264 Available? No<\/p>\n

              Is Request4 \u2264 Available? No<\/p>\n

               <\/p>\n

              Since the request of all the processes cannot be allocated, the system is not in a safe state. Though it possible to reclaim the resources held by process P<\/em>0, there are insufficient resources to fulfill other processes\u2019 requests. Thus, a deadlock exists, consisting of processes P<\/em>1, P<\/em>2, P<\/em>3, and P<\/em>4.<\/p>\n

               <\/p>\n

              Deadlock Detection Algorithm Usage<\/strong><\/p>\n

               <\/p>\n

              When should we invoke the detection algorithm?<\/p>\n

               <\/p>\n

              This depends on the answers to the following questions.<\/p>\n

              \u2013 How often is a deadlock likely to occur?<\/p>\n

              \u2013 How many processes will be affected by the deadlock when it happens?<\/p>\n

               <\/p>\n

              If deadlocks occur frequently, then it is necessary to invoke the detection algorithm frequently. If detection is not done, the resources allocated to deadlocked processes will be idle. The number of processes involved in the deadlock cycle may\u00a0also grow.<\/span><\/p>\n<\/div>\n

              \n

               <\/p>\n

              Deadlocks occur when a process makes a request that cannot be granted immediately. Therefore, the detection algorithm can be invoked every time a request for allocation cannot be granted immediately. During the detection process, not only the set of processes that are deadlocked are identified, but also the specific process that caused the deadlock is identified. If the cycle is completed by the most recent request, the process that requested the most recent request is identified as responsible for the deadlock. But invoking the deadlock detection algorithm each and every time a request is made results in considerable overhead in computation time.<\/p>\n

               <\/p>\n

              Therefore, the other possibility is to invoke the detection algorithm at less frequent intervals. The detection algorithm may be invoked once per hour or when the CPU utilization falls below 40 percent. In this case there may be many cycles in the graph and it may not be possible to tell which process caused the deadlock.<\/p>\n

               <\/p>\n

              19.3\u00a0\u00a0 Recovery from Deadlocks<\/strong><\/p>\n

               <\/p>\n

              Once deadlocks are detected, it is necessary to recover from deadlocks. There are different ways in which the system can recover from deadlocks. One method is to inform the operator that a deadlock has occurred. The operator deals with the deadlock manually. The second method is to let the system recover from the deadlock automatically. The third method is to break the deadlock. To break the deadlock, there are two ways. One is to abort one or more processes to break the circular wait (process termination). The second is to preempt some resources from one or more of the deadlocked processes (resource preemption).<\/p>\n

               <\/p>\n

              19.3.1\u00a0 Recovery from Deadlock: Process Termination<\/strong><\/p>\n

               <\/p>\n

              Termination of processes can be done in two ways. One is to abort all the deadlocked processes. This method will break the deadlock, but the results of all partial computations done by the aborted processes must be discarded and recomputed later. The second way is to abort one process at a time until the deadlock cycle is eliminated. This method involves a lot of overhead, because, after each process is aborted, deadlock-detection algorithm must be invoked to check if the deadlock still exists.<\/p>\n

               <\/p>\n

              When there are many processes involved in the deadlock, it is necessary to choose a process to terminate first. In which order should we choose a process to abort? There are many factors based on which the process to be aborted can be chosen:<\/p>\n

               <\/p>\n

              \u2013\u00a0 Priority of the process (process with the least priority is chosen)<\/p>\n

              \u2013\u00a0 How long process has computed, and how much longer to completion (the process that has done the least computations is chosen)<\/p>\n

              \u2013\u00a0 Resources the process has used (the process that has used less number of resources is chosen)<\/p>\n

              \u2013\u00a0 Resources \u00a0process needs\u00a0 to \u00a0complete \u00a0(the\u00a0 process\u00a0 that \u00a0needs\u00a0 many resources is chosen)<\/p>\n

              \u2013\u00a0 How many processes will need to be terminated<\/p>\n

              \u2013\u00a0 Is \u00a0process \u00a0interactive \u00a0or \u00a0batch? \u00a0(batch \u00a0processes \u00a0are \u00a0chosen \u00a0to \u00a0be terminated earlier than interactive processes)<\/p>\n<\/div>\n

               <\/p>\n

              19.3.2\u00a0 Recovery from Deadlock: Resource Preemption<\/strong><\/p>\n

               <\/p>\n

              To recover from deadlocks, resources can be preempted from the deadlocked processes. When resources are preempted, it is necessary to consider certain issues. The issues are discussed below:<\/p>\n

                \n
              • Selecting a victim<\/li>\n<\/ul>\n

                 <\/p>\n

                It is necessary to select the victim process from which the resources are to be preempted. The victim process has to be selected such that the cost is minimized. Cost factors may include the number of resources a deadlock process is holding and the amount of time a deadlocked process has thus far consumed during its execution.<\/p>\n

                  \n
                • Rollback<\/li>\n<\/ul>\n

                   <\/p>\n

                  If a resource is preempted from a process, what to do with the process? The process cannot continue, because it is missing some needed resource. Therefore, the process must be rolled back to some safe state and the process must be restarted from that state. But, the problem is that it is difficult to determine a safe state. Therefore a total rollback might have to be done or the process must be aborted and restarted again.<\/p>\n

                    \n
                  • Starvation<\/li>\n<\/ul>\n

                     <\/p>\n

                    While selecting a process for preempting resources, the same process may always be picked as victim. In that case, that process may be starved of resources and may not be able to complete its work. To reduce starvation, the number of rollbacks may also be included in the cost factor.<\/p>\n

                     <\/p>\n

                    19.4\u00a0 Summary<\/strong><\/p>\n

                     <\/p>\n

                    This module discussed deadlock detection algorithms when there is a single instance for each resource type (wait-for graph) and when there are multiple instances of resources (Banker\u2019s algorithm). This module also discussed how the system can recover from deadlocks.<\/p>\n

                     <\/p>\n

                     <\/p>\n

                    References<\/strong><\/p>\n

                      \n
                    1. Abraham Silberschatz, \u00a0Peter \u00a0B. \u00a0Galvin, \u00a0Greg \u00a0Gagne, \u00a0\u201cOperating \u00a0System Concepts\u201d, Ninth Edition, John Wiley & Sons Inc., 2012.<\/li>\n<\/ol>\n","protected":false},"author":4,"menu_order":16,"template":"","meta":{"_acf_changed":false,"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-mary-anitha-rajam"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-180","chapter","type-chapter","status-publish","hentry","contributor-dr-mary-anitha-rajam"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/180","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":5,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/180\/revisions"}],"predecessor-version":[{"id":421,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/180\/revisions\/421"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/180\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/media?parent=180"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapter-type?post=180"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/contributor?post=180"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/license?post=180"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}