{"id":173,"date":"2018-07-19T11:07:42","date_gmt":"2018-07-19T11:07:42","guid":{"rendered":"http:\/\/csp3.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=173"},"modified":"2018-08-07T10:22:02","modified_gmt":"2018-08-07T10:22:02","slug":"deadlocks-avoidance","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/chapter\/deadlocks-avoidance\/","title":{"rendered":"Deadlocks \u2013 Avoidance"},"content":{"raw":"
\r\n\r\n \r\n

18.1 Introduction<\/strong><\/p>\r\n \r\n

In a <\/span>multi-programming\u00a0environment, 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. In the previous module, we learnt different ways to prevent deadlocks. In this module, we shall see how deadlocks are avoided.<\/span><\/span><\/p>\r\n \r\n

In the previous module, we learnt that a system with resources can be depicted using a resource-allocation graph. In a resource-allocation graph, processes are denoted using circles and resource types are denoted using rectangles. The different instances of each resource type are shown as dots within the rectangles. Processes and resource types are the nodes of the resource-allocation graph. The edges show the dependency between the processes and the resources. If there is an edge from a process to a resource, it means that the process is requesting for an instance of the resource (request edge). If there is an edge from a resource to a process, it means that an instance of the resource is assigned to the process (assignment edge).<\/span><\/p>\r\n \r\n

18.2. Resource-Allocation Graph Algorithm for Deadlock Avoidance\u00a0<\/strong><\/p>\r\n\r\n<\/div>\r\n

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

Fig. 18.1 Resource-Allocation Graph for Deadlock Avoidance (Source: [1])<\/strong><\/p>\r\n \r\n

A variant of the resource-allocation graph is used to avoid deadlocks when the\u00a0system has only one instance of a resource type. In this graph, a new type of edge is added called the claim edge. A claim edge is represented by a dashed line as shown in Figure 18.1. A claim edge <\/span>P<\/em>i \u00ae <\/span>R<\/em>j indicates that process <\/span>P<\/em>j will request resource <\/span>R<\/em>j. All claim edges must appear in the graph, initially. Resources must be claimed <\/span>a priori <\/em>in the system. That is, at the beginning, the system should know the future requests of all the processes. These requests that would be made in future are depicted using claim edges.<\/span><\/p>\r\n \r\n

A claim edge <\/span>P<\/em>i \u00ae \u00a0<\/span>R<\/em>j is converted to a request edge when process <\/span>P<\/em>i actually requests for resource <\/span>R<\/em>j. When resource <\/span>R<\/em>j is released by process <\/span>P<\/em>i, the assignment edge <\/span>R<\/em>i \u00ae <\/span>P<\/em>i reconverts to a claim edge <\/span>P<\/em>i <\/em>\u00ae <\/span>R<\/em>j<\/em>.<\/span><\/p>\r\n \r\n

We will now learn how deadlocks can be avoided using this type of resource-allocation graphs. Suppose <\/span>P<\/em>i requests <\/span>R<\/em>j. The resource-allocation graph would have had a claim edge from <\/span>P<\/em>i to <\/span>R<\/em>j. The claim edge is now converted to a request edge <\/span>P<\/em>i \u00ae <\/span>R<\/em>j. The request edge <\/span>P<\/em>i \u00ae <\/span>R<\/em>j is converted to an assignment edge <\/span>R<\/em>j \u00ae <\/span>P<\/em>i. The resource-allocation graph now depicts how the state of the system would have been after the resource <\/span>R<\/em>j is allocated to <\/span>P<\/em>i. The resource-allocation graph is now checked for cycles using the cycle-detection algorithm. If there is no cycle, the system is in a safe state and the resource can be allocated to <\/span>P<\/em>i. If there is a cycle, process <\/span>P<\/em>i has\u00a0to wait. <\/span>P<\/em>i is not allocated the resource <\/span>R<\/em>j immediately.<\/span><\/p>\r\n \r\n

Thus, the resource-allocation graph alone is modified and the system is checked for safe state. The actual allocation of resource is not done immediately. Only if the allocation would result in a safe state, the actual allocation of resources is done.<\/span><\/p>\r\n\r\n<\/div>\r\n

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

Fig. 18.2 Unsafe State In Resource-Allocation Graph (Source: [1])<\/p>\r\n \r\n

Consider the resource-allocation graph in Figure 18.2. P<\/em>2 requests for resource R<\/em>2 as shown using the claim edge from P<\/em>2 to R<\/em>2 in Figure 18.1. This is converted to an assignment edge in the resource-allocation graph as shown in Figure 18.2. The graph is now checked for cycles. Since there is a cycle, the system understands that allocating\u00a0R<\/em>2 to <\/span>P<\/em>2 will lead to a deadlock. The only instance of <\/span>R<\/em>1 is assigned to <\/span>P<\/em>1 and the only instance of <\/span>R<\/em>2 is assigned to <\/span>P<\/em>2. <\/span>P<\/em>2 has requested for <\/span>R<\/em>1. It is known from the claim edge that process <\/span>P<\/em>1 may request for <\/span>R<\/em>2. If <\/span>P<\/em>1 requests for <\/span>R<\/em>2 (before releasing <\/span>R<\/em>1, then both the processes <\/span>P<\/em>1 and <\/span>P<\/em>2 will wait for a resource held by the other process. The system will go to a deadlocked state. Therefore, <\/span>R<\/em>2 is not allocated to <\/span>P<\/em>2. Thus, deadlocks are avoided.<\/span><\/p>\r\n \r\n

This method can be used to avoid deadlocks only if there is a single instance of each resource type. If there are more instances of each resource type, Banker\u2019s algorithm is used for deadlock avoidance.<\/span><\/p>\r\n\r\n<\/div>\r\n

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

18.3\u00a0 Banker\u2019s Algorithm<\/strong><\/p>\r\n \r\n

In the Banker\u2019s algorithm, each process must a priori declare its maximum use. This should be done for any deadlock avoidance algorithm. The maximum resource need of each process must not exceed the total number of resources in the system. When a user requests for resources, the system checks whether the allocation of the request will result in a safe state. If, after the allocation, the system will be in a safe state, resources are allocated. Else, the process waits. When a process gets all its resources it must return them in a finite amount of time.<\/p>\r\n \r\n\r\n18.3.1\u00a0 Data Structures for the Banker\u2019s Algorithm\u00a0<\/strong>\r\n\r\n \r\n\r\nLet n <\/em>denote the number of processes and m <\/em>denote the number of resource types.\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0Available: <\/em>Vector of length m<\/em>. If Available[j<\/em>] = k<\/em>, there are k \u00a0<\/em>instances \u00a0of resource type R<\/em>j <\/em>available.\r\n

A B C<\/em><\/p>\r\n

3 3 2<\/p>\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 3, 3 and 2 respectively.<\/p>\r\n \r\n

\u2022\u00a0Max: n x m <\/em>matrix. The n <\/em>rows correspond to n <\/em>processes and the m <\/em>columns correspond to the m <\/em>resource types. If Max[i, j<\/em>] = k<\/em>, then process P<\/em>i <\/em>may request at most k <\/em>instances of resource type R<\/em>j<\/em><\/p>\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\n<\/tr>\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 maximum need of process P<\/em>0 can\u00a0 be 7 instances of resource type A, 5 instances of resource type B and 3 instances of\u00a0resource type C. Similarly, the maximum need of the other processes <\/span>P<\/em>1, <\/span>P<\/em>2 and\u00a0<\/span>P<\/em>3 are also shown.<\/span><\/p>\r\n\r\n<\/div>\r\n

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

\u2022\u00a0\u00a0Allocation: n <\/em>x m <\/em>matrix. The n <\/em>rows correspond to n <\/em>processes and the m <\/em>columns correspond to the m <\/em>resource types. If Allocation[i,j<\/em>] = k <\/em>then process P<\/em>i <\/em>is currently allocated k <\/em>instances of R<\/em>j.<\/em><\/p>\r\n\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 and P<\/em>3. The number of instances of resource type currently allocated to each process is shown. Process 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 P<\/em>1, P<\/em>2 and P<\/em>3 are also shown.<\/p>\r\n \r\n

\u2022\u00a0\u00a0Need: n <\/em>x m <\/em>matrix. The n <\/em>rows correspond to n <\/em>processes and the m <\/em>columns correspond to the m <\/em>resource types. This matrix shows the future need of each process. If Need<\/em>[i, j<\/em>] = k<\/em>, then P<\/em>i <\/em>may need k <\/em>more instances of R<\/em>j <\/em>to complete its task.<\/p>\r\n \r\n

Need <\/em>[i, j] <\/em>= Max<\/em>[i, j<\/em>] \u2013 Allocation <\/em>[i, j<\/em>]<\/p>\r\n \r\n\r\nThat is, future need is a process\u2019s maximum need minus the resources currently allocated.\r\n\r\n \r\n\r\n18.3.2\u00a0 Notations Used:\u00a0<\/strong>\r\n\r\n \r\n\r\nIf X <\/em>and Y <\/em>are vectors of length n<\/em>\r\n

    \r\n \t
  • X <\/em>\u2264 Y <\/em>iff X<\/em>[i<\/em>] \u2264 Y<\/em>[i<\/em>] for all i <\/em>= 1,2,\u2026,n<\/em><\/li>\r\n<\/ul>\r\n

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

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

      \r\n \t
    • If X <\/em>= (1,7,3,2), Y <\/em>= (0,3,2,1)<\/li>\r\n<\/ul>\r\n \r\n

      In the above Y <\/em>\u2264 <\/span>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 the first element of X and so on.<\/span><\/p>\r\n \r\n\r\nY <\u00a0\u00a0\u00a0 X, <\/em>if Y <\/em>\u2264 X <\/em>and Y<\/em>\u2260 X<\/em>\r\n\r\n \r\n

      Each row in the matrices Allocation and Need is treated as a vector. For example, the i<\/em>th\u00a0 row of matrix Allocation and Need are\u00a0 referred to as Allocationi\u00a0 <\/em>and Needi <\/em>respectively.<\/p>\r\n\r\n<\/div>\r\n \r\n

      The Banker\u2019s algorithm comprises a safety algorithm and a resource-allocation algorithm. For a given state of the system, the safety algorithm checks if the system is in a safe state. The safety algorithm is given below:<\/span><\/p>\r\n\r\n

      \r\n\r\n \r\n\r\n18.3.3\u00a0 Safety Algorithm\u00a0<\/strong>\r\n\r\n \r\n\r\n1.\u00a0 Let Work <\/em>and Finish <\/em>be vectors of length m <\/em>and n <\/em>respectively.\u00a0\u00a0 Initialize:\r\n

      Work <\/em>= Available<\/em><\/p>\r\n

      Finish <\/em>[i<\/em>] = false <\/em>for i <\/em>= 1,2, \u2026, n<\/em><\/p>\r\n2.\u00a0 Find an i <\/em>such that both:\r\n

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

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

      If no such i <\/em>exists, go to step 4.<\/p>\r\n3.\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\n4.\u00a0 If Finish <\/em>[i<\/em>] == true for all i<\/em>, then the system is in a safe state.\r\n\r\n \r\n

      Whenever a request for resources comes from a process, the system runs the resource-request algorithm and modifies the state of the system in the simulation as if the resource is allocated. The actual state of the system is not modified; the data structures in the algorithm alone are modified. The safety algorithm is run to check if the system still remains in a safe state. The resource-request algorithm for process P<\/em>i is given below:<\/p>\r\n \r\n\r\n18.3.4\u00a0 Resource-Request Algorithm for Process P<\/em>i<\/em>\u00a0<\/strong>\r\n\r\n \r\n\r\nRequest<\/em>i <\/em>= request vector for process P<\/em>i<\/em>. If Request<\/em>i <\/em>[j<\/em>] = k <\/em>then process P<\/em>i <\/em>wants k\u00a0<\/em>instances of resource type R<\/em>j<\/em>.\r\n\r\n \r\n\r\n1. If Request<\/em>i <\/em>\u00a3 Need<\/em>i <\/em>go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim.\r\n\r\n2. If Request<\/em>i <\/em>\u00a3 Available<\/em>, go to step 3. Otherwise P<\/em>i\u00a0\u00a0\u00a0\u00a0 <\/em>must wait, since resources are not available.\r\n\r\n3. Pretend to allocate requested resources to P<\/em>i <\/em>by modifying the state as follows:\r\n\r\n \r\n\r\nAvailable <\/em>= Request<\/em>i<\/em>;<\/em>\r\n\r\nAllocation<\/em>i <\/em>= Allocation<\/em>i <\/em>+ Request<\/em>i<\/em>;\r\n\r\nNeed<\/em>i <\/em>= Need<\/em>i <\/em>\u2013 Request<\/em>i;;<\/em>\r\n\r\n \r\n\r\nThe safety algorithm is now run to check if the system is in a safe state with this modified state.\r\n\r\n \r\n\r\nIf safe <\/em>\u00de the resources are allocated to P<\/em>i<\/em>.<\/em>\r\n\r\nIf unsafe <\/em>\u00de P<\/em>i m<\/em>ust wait, and the old resource-allocation state is restored<\/em>\r\n\r\n \r\n\r\nWe will understand how the algorithm works by an example as given below.<\/span>\r\n\r\n<\/div>\r\n

      \r\n\r\n \r\n\r\n18.3.5\u00a0 Example of Banker\u2019s Algorithm<\/strong>\r\n\r\n \r\n\r\nConsider 5 processes P<\/em>0 \u00a0through P<\/em>4; 3 resource types A<\/em>, B <\/em>and C<\/em>. There are 10 instances of A<\/em>, 5 instances of B <\/em>and 7 instances of C<\/em>.\r\n\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\r\n
      <\/td>\r\nAllocation<\/em><\/strong><\/td>\r\nM<\/em><\/strong>ax<\/em><\/strong><\/td>\r\nAvailable<\/em><\/strong><\/td>\r\n<\/tr>\r\n
      <\/td>\r\nA B C<\/em><\/strong><\/td>\r\nA B C<\/em><\/strong><\/td>\r\nA B C<\/em><\/strong><\/td>\r\n<\/tr>\r\n
      P<\/em><\/strong>0<\/strong><\/td>\r\n0 1 0<\/strong><\/td>\r\n7 5 3<\/strong><\/td>\r\n3 3 2<\/strong><\/td>\r\n<\/tr>\r\n
      P<\/em><\/strong>1<\/strong><\/td>\r\n2 0 0<\/strong><\/td>\r\n3 2 2<\/strong><\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/em><\/strong>2<\/strong><\/td>\r\n3 0 2<\/strong><\/td>\r\n9 0 2<\/strong><\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/em><\/strong>3<\/strong><\/td>\r\n2 1 1<\/strong><\/td>\r\n2 2 2<\/strong><\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/em><\/strong>4<\/strong><\/td>\r\n0 0 2<\/strong><\/td>\r\n4 3 3<\/strong><\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nThe content of the matrix Need is defined to be Max \u2013 Allocation. Matrix Need is given below:\r\n

      Need <\/em>\u00a0A B C<\/em><\/p>\r\n

      P<\/em>0\u00a0\u00a0\u00a0\u00a0\u00a0 7 4 3<\/p>\r\n

      P<\/em>1\u00a0 \u00a0 \u00a0 \u00a01 2 2<\/p>\r\n

      P<\/em>2\u00a0\u00a0\u00a0\u00a0\u00a0 6 0 0<\/p>\r\n

      P<\/em>3\u00a0\u00a0\u00a0\u00a0\u00a0 0 1 1<\/p>\r\n

      P<\/em>4\u00a0\u00a0\u00a0\u00a0\u00a0 4 3 1<\/p>\r\n \r\n\r\nWe will first check if the system is in a safe state in the current situation. For this, the safety algorithm is run.\r\n

      Allocation<\/em>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Need\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\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\n7 4 3<\/td>\r\n3 3 2<\/td>\r\n<\/tr>\r\n
      P<\/em>1<\/td>\r\n2 0 0<\/td>\r\n1 2 2<\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/em>2<\/td>\r\n3 0 2<\/td>\r\n6 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n0 1 1<\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n4 3 1<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nVector Work is initialized to Available Therefore, Work = Available = (3,3,2)\r\n\r\n \r\n\r\nFinish[i] = false for i = 0,1,2,3,4 Let i = 0<\/span>\r\n\r\nIs Need0 \u2264 Work?\u00a0\u00a0\u00a0 No, (7,4,3) is not less than or equal to (3,3,2)<\/span>\r\n\r\n<\/div>\r\n
      \r\n\r\nLet i = 1\r\n\r\nIs Need1 \u2264 Work?\u00a0\u00a0\u00a0 Yes, (1,2,2) is less than or equal to (3,3,2)\r\n\r\nTherefore, set Finish[1] = true. P<\/em>1 added to the safe sequence < P<\/em>1>\r\n\r\nIs Need2 \u2264 Work?\u00a0\u00a0\u00a0 No, (6,0,0) is not less than or equal to (5,3,2)<\/span>\r\n\r\nWork = Work + Allocation1 = (3,3,2) + (2,0,0) = (5,3,2) Let i = 2\r\n\r\n \r\n\r\nLet i = 3\r\n\r\nIs Need3 \u2264 Work?\u00a0\u00a0\u00a0 Yes, (0,1,1) is less than or equal to (5,3,2)\r\n\r\nTherefore, set Finish[3] = true , P<\/em>3 added to safe sequence < P<\/em>1, P<\/em>3>\r\n\r\nWork = Work + Allocation3 =(5,3,2) + (2,1,1) = (7,4,3)\r\n\r\n \r\n\r\nWork = (7,4,4)\r\n\r\nLet i = 4\r\n\r\nIs Need4 \u2264 Work? Yes, (4,3,1) is less than or equal to (7,4,3)\r\n\r\nSet Finish[4] = true , P<\/em>4 is added to safe sequence < P<\/em>1 ,P<\/em>3, P<\/em>4 >\r\n\r\nWork = Work + Allocation4 = (7,4,3) + (0,0,2) = (7,4,5)\r\n\r\n \r\n\r\nWork = (7,4,5)\r\n\r\nNow, check again the processes that were not added to the safe sequence. P<\/em>0\r\n\r\nand P<\/em>2 are remaining.\r\n\r\n \r\n\r\nSo, let i = 0\r\n\r\nIs Need0 \u2264 Work?\u00a0\u00a0\u00a0 Yes\r\n\r\nSet Finish[0] = true, P<\/em>0 is added to safe sequence < P<\/em>1 ,P<\/em>3, P<\/em>4 , P<\/em>0>\r\n\r\nWork = Work + Allocation0 =(7,4,5) + (0,1, 0) = (7,5,5)\r\n\r\n \r\n\r\nWork = (7,5,5)\r\n\r\nLet i = 2\r\n\r\nIs Need2 \u2264 Work?\u00a0\u00a0\u00a0 Yes\r\n\r\nFinish[0] = true , P<\/em>2 is added to safe sequence <P<\/em>1 ,P<\/em>3, P<\/em>4 , P<\/em>0 , P<\/em>2 >\r\n\r\nWork = Work + Allocation2 =(7,5,5) + (3,0,2) = (10,5,7)\r\n\r\n \r\n\r\nThe system is in a safe state since the sequence < P<\/em>1<\/sub>, P<\/em>3<\/sub>, P<\/em>4<\/sub>, P<\/em>2<\/sub>, P<\/em>0<\/sub>> satisfies the safety requirement\r\n\r\n \r\n\r\nNow, let P<\/em>1\u00a0<\/sub>Request (1,0,2)\r\n\r\n<\/div>\r\n \r\n

      First, check if Request1 \u00a3 Available (that is, (1,0,2) \u00a3 (3,3,2)) \u00de <\/span>true.<\/em><\/p>\r\n \r\n

      Also, check if Request1 \u00a3 Need1 (that is (1,0,2) \u00a3 (1,2,2)) \u00de <\/span>true.<\/em><\/p>\r\n\r\n

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

      Now, the data structures are changed as if the request of P<\/em>1 is granted. The future Need of P<\/em>1 is changed from (1,2,2) to (0,2,0). The Allocation of P<\/em>1 is changed from (2,0,0) to (3,0,2) and the resources available are changed to (2,3,0)<\/p>\r\n\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\nNeed<\/em> A B C<\/em><\/td>\r\nAvailable<\/em> A B C<\/em><\/td>\r\n<\/tr>\r\n
      P<\/em>0<\/td>\r\n0 1 0<\/td>\r\n7 4 3<\/td>\r\n2 3 0<\/td>\r\n<\/tr>\r\n
      P<\/em>1<\/td>\r\n3 0 2<\/td>\r\n0 2 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/em>2<\/td>\r\n3 0 1<\/td>\r\n6 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n0 1 1<\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n4 3 1<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

      The system is\u00a0 now checked for a safety sequence. Executing safety algorithm shows that the sequence <P<\/em>1, P<\/em>3, P<\/em>4, P<\/em>0, P<\/em>2> satisfies the safety requirement. Therefore, the request of P<\/em>1 can be granted.<\/p>\r\n \r\n

      After P<\/em>1\u2019s request is granted, can request for (3,3,0) by P<\/em>4 be granted?<\/strong><\/p>\r\n \r\n

      No, resources are not available. Only (2,3,0) is available. P<\/em>4 needs 3 instances of A, but only 2 instances of A are available.<\/p>\r\n \r\n\r\nCan request for (0,2,0) by P<\/em>0 be granted?<\/strong>\r\n\r\n \r\n\r\nP<\/em><\/strong>0 <\/strong>Request (0,2,0)<\/strong>\r\n\r\n \r\n\r\nCheck if Request0 \u00a3 Available\r\n

      (0,2,0) \u00a3 (2,3,0) \u00de true.<\/em><\/p>\r\n \r\n\r\nAlso, check if Request0 \u00a3 Need0 (that is (0,2,0) \u00a3 (7,4,3)) \u00de true.<\/em>\r\n

      Now, \u00a0change \u00a0the \u00a0data \u00a0structures \u00a0as \u00a0if \u00a0the \u00a0request \u00a0is \u00a0granted \u00a0and \u00a0run \u00a0the \u00a0safety algorithm to check for a safe sequence. The future Need of P<\/em>0 is changed from (7,4,3) to (7,2,3). \u00a0The \u00a0Allocation \u00a0of \u00a0P<\/em>1 \u00a0is \u00a0changed \u00a0from \u00a0(0,1,0) \u00a0to \u00a0(0,3,0) \u00a0and \u00a0the \u00a0resources available are changed from (2,3,0) to (2,1,0).<\/p>\r\n\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\nNeed<\/em> A B C<\/em><\/td>\r\nAvailable<\/em> A B C<\/em><\/td>\r\n<\/tr>\r\n
      P<\/em>0<\/td>\r\n0 3 0<\/td>\r\n7 2 3<\/td>\r\n2 1 0<\/td>\r\n<\/tr>\r\n
      P<\/em>1<\/td>\r\n3 0 2<\/td>\r\n0 2 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/em>2<\/td>\r\n3 0 1<\/td>\r\n6 0 0<\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/em>3<\/td>\r\n2 1 1<\/td>\r\n0 1 1<\/td>\r\n<\/td>\r\n<\/tr>\r\n
      P<\/em>4<\/td>\r\n0 0 2<\/td>\r\n4 3 1<\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nThe future need of any of the processes cannot be satisfied with the resources available. Therefore, there is no safe sequence. Therefore, it is understood that the request of P<\/em>0 should not be granted.\r\n\r\n<\/div>\r\n \r\n

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

      This module discussed what is meant by a safe sequence. We learnt how deadlocks can be avoided when there is a single instance for all resource types. We also learnt how deadlocks can be avoided when there are multiple instances of resources using the Banker\u2019s algorithm.<\/p>\r\n \r\n\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

        18.1 Introduction<\/strong><\/p>\n

         <\/p>\n

        In a <\/span>multi-programming\u00a0environment, 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. In the previous module, we learnt different ways to prevent deadlocks. In this module, we shall see how deadlocks are avoided.<\/span><\/span><\/p>\n

         <\/p>\n

        In the previous module, we learnt that a system with resources can be depicted using a resource-allocation graph. In a resource-allocation graph, processes are denoted using circles and resource types are denoted using rectangles. The different instances of each resource type are shown as dots within the rectangles. Processes and resource types are the nodes of the resource-allocation graph. The edges show the dependency between the processes and the resources. If there is an edge from a process to a resource, it means that the process is requesting for an instance of the resource (request edge). If there is an edge from a resource to a process, it means that an instance of the resource is assigned to the process (assignment edge).<\/span><\/p>\n

         <\/p>\n

        18.2. Resource-Allocation Graph Algorithm for Deadlock Avoidance\u00a0<\/strong><\/p>\n<\/div>\n

        \n

        \"\"<\/p>\n

        Fig. 18.1 Resource-Allocation Graph for Deadlock Avoidance (Source: [1])<\/strong><\/p>\n

         <\/p>\n

        A variant of the resource-allocation graph is used to avoid deadlocks when the\u00a0system has only one instance of a resource type. In this graph, a new type of edge is added called the claim edge. A claim edge is represented by a dashed line as shown in Figure 18.1. A claim edge <\/span>P<\/em>i \u00ae <\/span>R<\/em>j indicates that process <\/span>P<\/em>j will request resource <\/span>R<\/em>j. All claim edges must appear in the graph, initially. Resources must be claimed <\/span>a priori <\/em>in the system. That is, at the beginning, the system should know the future requests of all the processes. These requests that would be made in future are depicted using claim edges.<\/span><\/p>\n

         <\/p>\n

        A claim edge <\/span>P<\/em>i \u00ae \u00a0<\/span>R<\/em>j is converted to a request edge when process <\/span>P<\/em>i actually requests for resource <\/span>R<\/em>j. When resource <\/span>R<\/em>j is released by process <\/span>P<\/em>i, the assignment edge <\/span>R<\/em>i \u00ae <\/span>P<\/em>i reconverts to a claim edge <\/span>P<\/em>i <\/em>\u00ae <\/span>R<\/em>j<\/em>.<\/span><\/p>\n

         <\/p>\n

        We will now learn how deadlocks can be avoided using this type of resource-allocation graphs. Suppose <\/span>P<\/em>i requests <\/span>R<\/em>j. The resource-allocation graph would have had a claim edge from <\/span>P<\/em>i to <\/span>R<\/em>j. The claim edge is now converted to a request edge <\/span>P<\/em>i \u00ae <\/span>R<\/em>j. The request edge <\/span>P<\/em>i \u00ae <\/span>R<\/em>j is converted to an assignment edge <\/span>R<\/em>j \u00ae <\/span>P<\/em>i. The resource-allocation graph now depicts how the state of the system would have been after the resource <\/span>R<\/em>j is allocated to <\/span>P<\/em>i. The resource-allocation graph is now checked for cycles using the cycle-detection algorithm. If there is no cycle, the system is in a safe state and the resource can be allocated to <\/span>P<\/em>i. If there is a cycle, process <\/span>P<\/em>i has\u00a0to wait. <\/span>P<\/em>i is not allocated the resource <\/span>R<\/em>j immediately.<\/span><\/p>\n

         <\/p>\n

        Thus, the resource-allocation graph alone is modified and the system is checked for safe state. The actual allocation of resource is not done immediately. Only if the allocation would result in a safe state, the actual allocation of resources is done.<\/span><\/p>\n<\/div>\n

        \n

        \"\"<\/p>\n

        Fig. 18.2 Unsafe State In Resource-Allocation Graph (Source: [1])<\/p>\n

         <\/p>\n

        Consider the resource-allocation graph in Figure 18.2. P<\/em>2 requests for resource R<\/em>2 as shown using the claim edge from P<\/em>2 to R<\/em>2 in Figure 18.1. This is converted to an assignment edge in the resource-allocation graph as shown in Figure 18.2. The graph is now checked for cycles. Since there is a cycle, the system understands that allocating\u00a0R<\/em>2 to <\/span>P<\/em>2 will lead to a deadlock. The only instance of <\/span>R<\/em>1 is assigned to <\/span>P<\/em>1 and the only instance of <\/span>R<\/em>2 is assigned to <\/span>P<\/em>2. <\/span>P<\/em>2 has requested for <\/span>R<\/em>1. It is known from the claim edge that process <\/span>P<\/em>1 may request for <\/span>R<\/em>2. If <\/span>P<\/em>1 requests for <\/span>R<\/em>2 (before releasing <\/span>R<\/em>1, then both the processes <\/span>P<\/em>1 and <\/span>P<\/em>2 will wait for a resource held by the other process. The system will go to a deadlocked state. Therefore, <\/span>R<\/em>2 is not allocated to <\/span>P<\/em>2. Thus, deadlocks are avoided.<\/span><\/p>\n

         <\/p>\n

        This method can be used to avoid deadlocks only if there is a single instance of each resource type. If there are more instances of each resource type, Banker\u2019s algorithm is used for deadlock avoidance.<\/span><\/p>\n<\/div>\n

        \n

         <\/p>\n

        18.3\u00a0 Banker\u2019s Algorithm<\/strong><\/p>\n

         <\/p>\n

        In the Banker\u2019s algorithm, each process must a priori declare its maximum use. This should be done for any deadlock avoidance algorithm. The maximum resource need of each process must not exceed the total number of resources in the system. When a user requests for resources, the system checks whether the allocation of the request will result in a safe state. If, after the allocation, the system will be in a safe state, resources are allocated. Else, the process waits. When a process gets all its resources it must return them in a finite amount of time.<\/p>\n

         <\/p>\n

        18.3.1\u00a0 Data Structures for the Banker\u2019s Algorithm\u00a0<\/strong><\/p>\n

         <\/p>\n

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

         <\/p>\n

        \u2022\u00a0\u00a0Available: <\/em>Vector of length m<\/em>. If Available[j<\/em>] = k<\/em>, there are k \u00a0<\/em>instances \u00a0of resource type R<\/em>j <\/em>available.<\/p>\n

        A B C<\/em><\/p>\n

        3 3 2<\/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 3, 3 and 2 respectively.<\/p>\n

         <\/p>\n

        \u2022\u00a0Max: n x m <\/em>matrix. The n <\/em>rows correspond to n <\/em>processes and the m <\/em>columns correspond to the m <\/em>resource types. If Max[i, j<\/em>] = k<\/em>, then process P<\/em>i <\/em>may request at most k <\/em>instances of resource type R<\/em>j<\/em><\/p>\n\n\n\n\n\n\n\n
        <\/td>\nA B C<\/em><\/td>\n<\/tr>\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 maximum need of process P<\/em>0 can\u00a0 be 7 instances of resource type A, 5 instances of resource type B and 3 instances of\u00a0resource type C. Similarly, the maximum need of the other processes <\/span>P<\/em>1, <\/span>P<\/em>2 and\u00a0<\/span>P<\/em>3 are also shown.<\/span><\/p>\n<\/div>\n

        \n

         <\/p>\n

        \u2022\u00a0\u00a0Allocation: n <\/em>x m <\/em>matrix. The n <\/em>rows correspond to n <\/em>processes and the m <\/em>columns correspond to the m <\/em>resource types. If Allocation[i,j<\/em>] = k <\/em>then process P<\/em>i <\/em>is currently allocated k <\/em>instances of R<\/em>j.<\/em><\/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 and P<\/em>3. The number of instances of resource type currently allocated to each process is shown. Process 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 P<\/em>1, P<\/em>2 and P<\/em>3 are also shown.<\/p>\n

         <\/p>\n

        \u2022\u00a0\u00a0Need: n <\/em>x m <\/em>matrix. The n <\/em>rows correspond to n <\/em>processes and the m <\/em>columns correspond to the m <\/em>resource types. This matrix shows the future need of each process. If Need<\/em>[i, j<\/em>] = k<\/em>, then P<\/em>i <\/em>may need k <\/em>more instances of R<\/em>j <\/em>to complete its task.<\/p>\n

         <\/p>\n

        Need <\/em>[i, j] <\/em>= Max<\/em>[i, j<\/em>] \u2013 Allocation <\/em>[i, j<\/em>]<\/p>\n

         <\/p>\n

        That is, future need is a process\u2019s maximum need minus the resources currently allocated.<\/p>\n

         <\/p>\n

        18.3.2\u00a0 Notations Used:\u00a0<\/strong><\/p>\n

         <\/p>\n

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

          \n
        • X <\/em>\u2264 Y <\/em>iff X<\/em>[i<\/em>] \u2264 Y<\/em>[i<\/em>] for all i <\/em>= 1,2,\u2026,n<\/em><\/li>\n<\/ul>\n

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

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

            \n
          • If X <\/em>= (1,7,3,2), Y <\/em>= (0,3,2,1)<\/li>\n<\/ul>\n

             <\/p>\n

            In the above Y <\/em>\u2264 <\/span>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 the first element of X and so on.<\/span><\/p>\n

             <\/p>\n

            Y <\u00a0\u00a0\u00a0 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 Need is treated as a vector. For example, the i<\/em>th\u00a0 row of matrix Allocation and Need are\u00a0 referred to as Allocationi\u00a0 <\/em>and Needi <\/em>respectively.<\/p>\n<\/div>\n

             <\/p>\n

            The Banker\u2019s algorithm comprises a safety algorithm and a resource-allocation algorithm. For a given state of the system, the safety algorithm checks if the system is in a safe state. The safety algorithm is given below:<\/span><\/p>\n

            \n

             <\/p>\n

            18.3.3\u00a0 Safety Algorithm\u00a0<\/strong><\/p>\n

             <\/p>\n

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

            Work <\/em>= Available<\/em><\/p>\n

            Finish <\/em>[i<\/em>] = false <\/em>for i <\/em>= 1,2, \u2026, n<\/em><\/p>\n

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

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

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

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

            3.\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

            4.\u00a0 If Finish <\/em>[i<\/em>] == true for all i<\/em>, then the system is in a safe state.<\/p>\n

             <\/p>\n

            Whenever a request for resources comes from a process, the system runs the resource-request algorithm and modifies the state of the system in the simulation as if the resource is allocated. The actual state of the system is not modified; the data structures in the algorithm alone are modified. The safety algorithm is run to check if the system still remains in a safe state. The resource-request algorithm for process P<\/em>i is given below:<\/p>\n

             <\/p>\n

            18.3.4\u00a0 Resource-Request Algorithm for Process P<\/em>i<\/em>\u00a0<\/strong><\/p>\n

             <\/p>\n

            Request<\/em>i <\/em>= request vector for process P<\/em>i<\/em>. If Request<\/em>i <\/em>[j<\/em>] = k <\/em>then process P<\/em>i <\/em>wants k\u00a0<\/em>instances of resource type R<\/em>j<\/em>.<\/p>\n

             <\/p>\n

            1. If Request<\/em>i <\/em>\u00a3 Need<\/em>i <\/em>go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim.<\/p>\n

            2. If Request<\/em>i <\/em>\u00a3 Available<\/em>, go to step 3. Otherwise P<\/em>i\u00a0\u00a0\u00a0\u00a0 <\/em>must wait, since resources are not available.<\/p>\n

            3. Pretend to allocate requested resources to P<\/em>i <\/em>by modifying the state as follows:<\/p>\n

             <\/p>\n

            Available <\/em>= Request<\/em>i<\/em>;<\/em><\/p>\n

            Allocation<\/em>i <\/em>= Allocation<\/em>i <\/em>+ Request<\/em>i<\/em>;<\/p>\n

            Need<\/em>i <\/em>= Need<\/em>i <\/em>\u2013 Request<\/em>i;;<\/em><\/p>\n

             <\/p>\n

            The safety algorithm is now run to check if the system is in a safe state with this modified state.<\/p>\n

             <\/p>\n

            If safe <\/em>\u00de the resources are allocated to P<\/em>i<\/em>.<\/em><\/p>\n

            If unsafe <\/em>\u00de P<\/em>i m<\/em>ust wait, and the old resource-allocation state is restored<\/em><\/p>\n

             <\/p>\n

            We will understand how the algorithm works by an example as given below.<\/span><\/p>\n<\/div>\n

            \n

             <\/p>\n

            18.3.5\u00a0 Example of Banker\u2019s Algorithm<\/strong><\/p>\n

             <\/p>\n

            Consider 5 processes P<\/em>0 \u00a0through P<\/em>4; 3 resource types A<\/em>, B <\/em>and C<\/em>. There are 10 instances of A<\/em>, 5 instances of B <\/em>and 7 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\n
            <\/td>\nAllocation<\/em><\/strong><\/td>\nM<\/em><\/strong>ax<\/em><\/strong><\/td>\nAvailable<\/em><\/strong><\/td>\n<\/tr>\n
            <\/td>\nA B C<\/em><\/strong><\/td>\nA B C<\/em><\/strong><\/td>\nA B C<\/em><\/strong><\/td>\n<\/tr>\n
            P<\/em><\/strong>0<\/strong><\/td>\n0 1 0<\/strong><\/td>\n7 5 3<\/strong><\/td>\n3 3 2<\/strong><\/td>\n<\/tr>\n
            P<\/em><\/strong>1<\/strong><\/td>\n2 0 0<\/strong><\/td>\n3 2 2<\/strong><\/td>\n<\/td>\n<\/tr>\n
            P<\/em><\/strong>2<\/strong><\/td>\n3 0 2<\/strong><\/td>\n9 0 2<\/strong><\/td>\n<\/td>\n<\/tr>\n
            P<\/em><\/strong>3<\/strong><\/td>\n2 1 1<\/strong><\/td>\n2 2 2<\/strong><\/td>\n<\/td>\n<\/tr>\n
            P<\/em><\/strong>4<\/strong><\/td>\n0 0 2<\/strong><\/td>\n4 3 3<\/strong><\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

             <\/p>\n

            The content of the matrix Need is defined to be Max \u2013 Allocation. Matrix Need is given below:<\/p>\n

            Need <\/em>\u00a0A B C<\/em><\/p>\n

            P<\/em>0\u00a0\u00a0\u00a0\u00a0\u00a0 7 4 3<\/p>\n

            P<\/em>1\u00a0 \u00a0 \u00a0 \u00a01 2 2<\/p>\n

            P<\/em>2\u00a0\u00a0\u00a0\u00a0\u00a0 6 0 0<\/p>\n

            P<\/em>3\u00a0\u00a0\u00a0\u00a0\u00a0 0 1 1<\/p>\n

            P<\/em>4\u00a0\u00a0\u00a0\u00a0\u00a0 4 3 1<\/p>\n

             <\/p>\n

            We will first check if the system is in a safe state in the current situation. For this, the safety algorithm is run.<\/p>\n

            Allocation<\/em>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Need\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\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>\n7 4 3<\/td>\n3 3 2<\/td>\n<\/tr>\n
            P<\/em>1<\/td>\n2 0 0<\/td>\n1 2 2<\/td>\n<\/td>\n<\/tr>\n
            P<\/em>2<\/td>\n3 0 2<\/td>\n6 0 0<\/td>\n<\/td>\n<\/tr>\n
            P<\/em>3<\/td>\n2 1 1<\/td>\n0 1 1<\/td>\n<\/td>\n<\/tr>\n
            P<\/em>4<\/td>\n0 0 2<\/td>\n4 3 1<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

             <\/p>\n

            Vector Work is initialized to Available Therefore, Work = Available = (3,3,2)<\/p>\n

             <\/p>\n

            Finish[i] = false for i = 0,1,2,3,4 Let i = 0<\/span><\/p>\n

            Is Need0 \u2264 Work?\u00a0\u00a0\u00a0 No, (7,4,3) is not less than or equal to (3,3,2)<\/span><\/p>\n<\/div>\n

            \n

            Let i = 1<\/p>\n

            Is Need1 \u2264 Work?\u00a0\u00a0\u00a0 Yes, (1,2,2) is less than or equal to (3,3,2)<\/p>\n

            Therefore, set Finish[1] = true. P<\/em>1 added to the safe sequence < P<\/em>1><\/p>\n

            Is Need2 \u2264 Work?\u00a0\u00a0\u00a0 No, (6,0,0) is not less than or equal to (5,3,2)<\/span><\/p>\n

            Work = Work + Allocation1 = (3,3,2) + (2,0,0) = (5,3,2) Let i = 2<\/p>\n

             <\/p>\n

            Let i = 3<\/p>\n

            Is Need3 \u2264 Work?\u00a0\u00a0\u00a0 Yes, (0,1,1) is less than or equal to (5,3,2)<\/p>\n

            Therefore, set Finish[3] = true , P<\/em>3 added to safe sequence < P<\/em>1, P<\/em>3><\/p>\n

            Work = Work + Allocation3 =(5,3,2) + (2,1,1) = (7,4,3)<\/p>\n

             <\/p>\n

            Work = (7,4,4)<\/p>\n

            Let i = 4<\/p>\n

            Is Need4 \u2264 Work? Yes, (4,3,1) is less than or equal to (7,4,3)<\/p>\n

            Set Finish[4] = true , P<\/em>4 is added to safe sequence < P<\/em>1 ,P<\/em>3, P<\/em>4 ><\/p>\n

            Work = Work + Allocation4 = (7,4,3) + (0,0,2) = (7,4,5)<\/p>\n

             <\/p>\n

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

            Now, check again the processes that were not added to the safe sequence. P<\/em>0<\/p>\n

            and P<\/em>2 are remaining.<\/p>\n

             <\/p>\n

            So, let i = 0<\/p>\n

            Is Need0 \u2264 Work?\u00a0\u00a0\u00a0 Yes<\/p>\n

            Set Finish[0] = true, P<\/em>0 is added to safe sequence < P<\/em>1 ,P<\/em>3, P<\/em>4 , P<\/em>0><\/p>\n

            Work = Work + Allocation0 =(7,4,5) + (0,1, 0) = (7,5,5)<\/p>\n

             <\/p>\n

            Work = (7,5,5)<\/p>\n

            Let i = 2<\/p>\n

            Is Need2 \u2264 Work?\u00a0\u00a0\u00a0 Yes<\/p>\n

            Finish[0] = true , P<\/em>2 is added to safe sequence <P<\/em>1 ,P<\/em>3, P<\/em>4 , P<\/em>0 , P<\/em>2 ><\/p>\n

            Work = Work + Allocation2 =(7,5,5) + (3,0,2) = (10,5,7)<\/p>\n

             <\/p>\n

            The system is in a safe state since the sequence < P<\/em>1<\/sub>, P<\/em>3<\/sub>, P<\/em>4<\/sub>, P<\/em>2<\/sub>, P<\/em>0<\/sub>> satisfies the safety requirement<\/p>\n

             <\/p>\n

            Now, let P<\/em>1\u00a0<\/sub>Request (1,0,2)<\/p>\n<\/div>\n

             <\/p>\n

            First, check if Request1 \u00a3 Available (that is, (1,0,2) \u00a3 (3,3,2)) \u00de <\/span>true.<\/em><\/p>\n

             <\/p>\n

            Also, check if Request1 \u00a3 Need1 (that is (1,0,2) \u00a3 (1,2,2)) \u00de <\/span>true.<\/em><\/p>\n

            \n

             <\/p>\n

            Now, the data structures are changed as if the request of P<\/em>1 is granted. The future Need of P<\/em>1 is changed from (1,2,2) to (0,2,0). The Allocation of P<\/em>1 is changed from (2,0,0) to (3,0,2) and the resources available are changed to (2,3,0)<\/p>\n\n\n\n\n\n\n\n\n
            <\/td>\nAllocation<\/em> A B C<\/em><\/td>\nNeed<\/em> A B C<\/em><\/td>\nAvailable<\/em> A B C<\/em><\/td>\n<\/tr>\n
            P<\/em>0<\/td>\n0 1 0<\/td>\n7 4 3<\/td>\n2 3 0<\/td>\n<\/tr>\n
            P<\/em>1<\/td>\n3 0 2<\/td>\n0 2 0<\/td>\n<\/td>\n<\/tr>\n
            P<\/em>2<\/td>\n3 0 1<\/td>\n6 0 0<\/td>\n<\/td>\n<\/tr>\n
            P<\/em>3<\/td>\n2 1 1<\/td>\n0 1 1<\/td>\n<\/td>\n<\/tr>\n
            P<\/em>4<\/td>\n0 0 2<\/td>\n4 3 1<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

             <\/p>\n

            The system is\u00a0 now checked for a safety sequence. Executing safety algorithm shows that the sequence <P<\/em>1, P<\/em>3, P<\/em>4, P<\/em>0, P<\/em>2> satisfies the safety requirement. Therefore, the request of P<\/em>1 can be granted.<\/p>\n

             <\/p>\n

            After P<\/em>1\u2019s request is granted, can request for (3,3,0) by P<\/em>4 be granted?<\/strong><\/p>\n

             <\/p>\n

            No, resources are not available. Only (2,3,0) is available. P<\/em>4 needs 3 instances of A, but only 2 instances of A are available.<\/p>\n

             <\/p>\n

            Can request for (0,2,0) by P<\/em>0 be granted?<\/strong><\/p>\n

             <\/p>\n

            P<\/em><\/strong>0 <\/strong>Request (0,2,0)<\/strong><\/p>\n

             <\/p>\n

            Check if Request0 \u00a3 Available<\/p>\n

            (0,2,0) \u00a3 (2,3,0) \u00de true.<\/em><\/p>\n

             <\/p>\n

            Also, check if Request0 \u00a3 Need0 (that is (0,2,0) \u00a3 (7,4,3)) \u00de true.<\/em><\/p>\n

            Now, \u00a0change \u00a0the \u00a0data \u00a0structures \u00a0as \u00a0if \u00a0the \u00a0request \u00a0is \u00a0granted \u00a0and \u00a0run \u00a0the \u00a0safety algorithm to check for a safe sequence. The future Need of P<\/em>0 is changed from (7,4,3) to (7,2,3). \u00a0The \u00a0Allocation \u00a0of \u00a0P<\/em>1 \u00a0is \u00a0changed \u00a0from \u00a0(0,1,0) \u00a0to \u00a0(0,3,0) \u00a0and \u00a0the \u00a0resources available are changed from (2,3,0) to (2,1,0).<\/p>\n\n\n\n\n\n\n\n\n
            <\/td>\nAllocation<\/em> A B C<\/em><\/td>\nNeed<\/em> A B C<\/em><\/td>\nAvailable<\/em> A B C<\/em><\/td>\n<\/tr>\n
            P<\/em>0<\/td>\n0 3 0<\/td>\n7 2 3<\/td>\n2 1 0<\/td>\n<\/tr>\n
            P<\/em>1<\/td>\n3 0 2<\/td>\n0 2 0<\/td>\n<\/td>\n<\/tr>\n
            P<\/em>2<\/td>\n3 0 1<\/td>\n6 0 0<\/td>\n<\/td>\n<\/tr>\n
            P<\/em>3<\/td>\n2 1 1<\/td>\n0 1 1<\/td>\n<\/td>\n<\/tr>\n
            P<\/em>4<\/td>\n0 0 2<\/td>\n4 3 1<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

             <\/p>\n

            The future need of any of the processes cannot be satisfied with the resources available. Therefore, there is no safe sequence. Therefore, it is understood that the request of P<\/em>0 should not be granted.<\/p>\n<\/div>\n

             <\/p>\n

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

             <\/p>\n

            This module discussed what is meant by a safe sequence. We learnt how deadlocks can be avoided when there is a single instance for all resource types. We also learnt how deadlocks can be avoided when there are multiple instances of resources using the Banker\u2019s algorithm.<\/p>\n

             <\/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":15,"template":"","meta":{"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-173","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\/173","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\/173\/revisions"}],"predecessor-version":[{"id":420,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/173\/revisions\/420"}],"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\/173\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/media?parent=173"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapter-type?post=173"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/contributor?post=173"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/license?post=173"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}