{"id":154,"date":"2018-07-19T10:20:37","date_gmt":"2018-07-19T10:20:37","guid":{"rendered":"http:\/\/csp3.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=154"},"modified":"2018-08-07T10:17:28","modified_gmt":"2018-08-07T10:17:28","slug":"deadlocks-introduction","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/chapter\/deadlocks-introduction\/","title":{"rendered":"Deadlocks \u2013 Introduction"},"content":{"raw":"
\r\n\r\n \r\n\r\n16.1\u00a0 Introduction<\/strong>\r\n\r\n \r\n

Any system has many processes and a number of different resources. In such a system, processes request for resources, use them and then release them. If a process requests for resources and the resources are not available, the process waits. If the requested resources are held by other waiting processes, the requesting process continues to wait forever. This situation is called a deadlock.<\/span><\/p>\r\n \r\n

This module explains what is meant by a deadlock, the methods for handling deadlocks, what a resource-allocation graph is and how a resource-allocation graph can be used to handle deadlocks.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n16.2\u00a0 ridge Crossing Example\u00a0<\/strong>\r\n\r\n\"\"\r\n

Fig. 16.1 Bridge crossing - deadlock<\/strong><\/p>\r\n \r\n

Consider vehicles crossing a bridge as shown in Figure 16.1. Vehicles can cross the bridge only in one direction at a particular time. If two vehicles that are moving in opposite directions try to cross the bridge at the same time, both get into a deadlocked situation. The deadlock can be resolved only if one vehicle backs up. To back up one vehicle, several other vehicles may also have to be backed up if a deadlock occurs.<\/p>\r\n \r\n\r\n16.3 Deadlock Problem in a System<\/strong>\r\n\r\n \r\n

A situation similar to that of crossing a bridge can happen in a system as well. Suppose there is a set of blocked processes, each holding a resource and waiting to acquire a resource held by another process in the set. All the processes will be waiting for each other to release resources. Then, the system will be in a deadlocked state.<\/p>\r\n \r\n

Consider the following example: A system has 2 tape drives. There are two processes P<\/em>1 and P<\/em>2. Each process holds one tape drive and needs another one. Since there are only two tape drives in the system, each of the two processes is waiting for the tape drive held by the other waiting process. Now, both the processes are unable to proceed and are deadlocked.<\/p>\r\n\r\n<\/div>\r\n \r\n

Let us see another example. Though this example was explained in an earlier module, it is given here for better clarity. There are two semaphores, <\/span>A <\/em>and <\/span>B<\/em>, initialized to 1. Since the initial value is 1, each of the semaphores <\/span>A <\/em>and <\/span>B <\/em>is guarding resources that can be accessed only by one process at a time. Let <\/span>P<\/em>0 and <\/span>P<\/em>1 be two processes that are executing the following sequence of statements respectively.<\/span><\/p>\r\n\r\n

\r\n\r\n\u00a0 \u00a0 P<\/em>0<\/sub>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0P<\/em>1<\/sub>\r\n\r\n \r\n\r\nwait (A);\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 wait(B);<\/em>\r\n\r\nwait (B);\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 wait(A);<\/em>\r\n\r\n \r\n

Suppose P<\/em>0 executes wait(A<\/em>) first. This operation decrements the value of semaphore A <\/em>from 1 to 0. Suppose there is a context switch and P<\/em>1 executes wait(B<\/em>). This will decrement the value of semaphore B <\/em>from 1 to 0. Next, P<\/em>1 continues to execute wait(A<\/em>). Since the value of semaphore A <\/em>is 0, process P<\/em>1 waits. There is a context switch now and process P<\/em>0 executes wait(B<\/em>). Since the value of semaphore B <\/em>is 0, process P<\/em>0 waits. Here, we see that process P<\/em>0 is waiting for semaphore B <\/em>held by process P<\/em>1 and process P<\/em>1 is waiting for semaphore A <\/em>held by process P<\/em>0. Thus, both the processes are in a deadlocked state.<\/p>\r\n \r\n\r\n16.4 System Model<\/strong>\r\n\r\n \r\n

Any system has a finite number of resources, distributed among a number of competing processes. The resources are categorized into several resource types R<\/em>1, R<\/em>2, ..., R<\/em>m . The resource types in a system may be CPU cycles, memory space, I\/O devices and so on. Each resource type R<\/em>i has W<\/em>i instances. For example, if there are 5 printers, then there are 5 instances of the resource type printer.<\/p>\r\n \r\n

Each process utilizes resources as follows: Each process requests for resources, uses the resources and releases the resources after using the resources. A process may request as many resources as it requires to carry out its designated task. The number of resources requested by the process cannot exceed the total number of resources available in the system. That is, if there are five printers, the process cannot request for six.<\/p>\r\n \r\n

There are system calls available for the request and release of resources like the request <\/em>and release device<\/em>, open <\/em>and close file<\/em>, allocate <\/em>and free memory<\/em>. Request and release of resources can be accomplished through the wait and the signal operations on semaphores.<\/p>\r\n \r\n

A table is maintained in the system that records whether each resource is free or allocated. If a resource is allocated, information is maintained as to which process the resource is allocated. If a process requests a resource currently allocated to another process, the process is added to a queue of processes waiting for that resource.<\/p>\r\n \r\n\r\n16.5 Deadlock Characterization<\/strong>\r\n\r\n \r\n

In a deadlocked system, processes never finish executing and system resources are tied up, preventing other jobs from starting. We shall now understand the features that characterize deadlocks.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n16.5.1 Necessary conditions<\/strong>\r\n\r\n \r\n\r\nDeadlocks can arise if the following four conditions hold simultaneously in a system:\r\n
    \r\n \t
  • Mutual exclusion: If there is a non-shareable resource, only one process can use a resource at a time.<\/li>\r\n \t
  • Hold and\u00a0 wait:\u00a0 A process holding at least one resource is waiting to acquire additional resources held by other waiting processes.<\/li>\r\n \t
  • No preemption: A resource can be released only voluntarily by the process that is holding it after the process has completed its task. It is not possible to preempt a resource forcibly from a process.<\/li>\r\n \t
  • Circular wait: If there exists a set {P<\/em>0, P<\/em>1, \u2026, P<\/em>0} of waiting processes such that P<\/em>0 is waiting for a resource that is held by P<\/em>1, P<\/em>1 is waiting for a resource that is held by P<\/em>2, \u2026, P<\/em>n<\/em>\u20131 is waiting for a resource that is held by P<\/em>n, and P<\/em>n is waiting for a resource that is held by P<\/em>0.<\/li>\r\n<\/ul>\r\n \r\n\r\n16.5.2 Resource-Allocation Graph<\/strong>\r\n\r\n \r\n

    Any system can be described by means of a directed graph called a system resource-allocation graph. The graph consists of a set of vertices V <\/em>and a set of edges\u00a0E<\/em>. The set of vertices V is partitioned into two types, P <\/em>= {P<\/em>1, P<\/em>2, \u2026, P<\/em>n<\/em>}, the set consisting of all the processes in the system and R <\/em>= {R<\/em>1, R<\/em>2, \u2026, R<\/em>m<\/em>}, the set consisting of all the resource types in the system. A directed edge from P<\/em>i to R<\/em>j is denoted as P<\/em>i \u00ae\u00a0R<\/em>j and is called a request edge. A directed edge from R<\/em>j to P<\/em>i is denoted as R<\/em>j <\/em>\u00ae P<\/em>i <\/em>and is called an assignment edge.<\/p>\r\n \r\n

    Pictorially, a process is denoted using a circle as shown below:<\/p>\r\n

    \"\"<\/p>\r\nA resource type is denoted using a square. The instances of a resource type are shown using dots inside the square. A resource type with 4 instances is denoted pictorially as shown below:\r\n

    \"\"<\/p>\r\nWhen P<\/em>i requests an instance of R<\/em>j, it is denoted as an edge from P<\/em>i to R<\/em>j in the resource-allocation graph.\r\n

    \"\"<\/p>\r\nWhen <\/span>P<\/em>i is holding an instance of <\/span>R<\/em>j, it is shown as an edge from a dot in <\/span>R<\/em>j to <\/span>P<\/em>i\u00a0<\/span>in the resource-allocation graph.<\/span>\r\n\r\n<\/div>\r\n

    \r\n

    \"\"<\/p>\r\n

    Figure 16.2 shows an example of a resource-allocation graph. P<\/em>1, P<\/em>2 and P<\/em>3 are the three processes in the system. There are four resource types, R<\/em>1, R<\/em>2, R<\/em>3 and R<\/em>4. There is one instance of R<\/em>1, two instances of R<\/em>2, one instance of R<\/em>3 and three instances of R<\/em>4. P<\/em>1 is holding one instance of R<\/em>2 and is requesting for one instance of R<\/em>1. P<\/em>2 is holding one instance of R<\/em>1 and one instance of R<\/em>2 and is requesting for one instance of R<\/em>3. P<\/em>3 is holding one instance of R<\/em>3.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

    \r\n

    Fig. 16.2 Resource-allocation graph (Source: [1])<\/p>\r\n \r\n

    Deadlocks can be detected from a resource-allocation graph. If the resource-allocation graph contains no cycles, no process is deadlocked. If the resource-allocation graph contains cycles, deadlocks may exist. If there is only one instance of each resource type and there is a cycle in the graph, there is a deadlock in the system.<\/p>\r\n \r\n

    16.5.3\u00a0 Resource-Allocation Graph With a Deadlock<\/strong><\/p>\r\n \r\n

    Figure 16.3 shows a resource-allocation graph with a deadlock. In this figure, process P<\/em>1 is waiting for an instance of resource type R<\/em>1. There is only one instance of R<\/em>1 which is held by process P<\/em>2. P<\/em>2 is waiting for an instance of resource R<\/em>3. There is only one instance of R<\/em>3, which is held by process P<\/em>3. Process P<\/em>3 is waiting for an instance of R<\/em>2. There are two instances of R<\/em>2, each of which is held by P<\/em>1 \u00a0and P<\/em>2 respectively. Thus, P<\/em>1, P<\/em>2 and P<\/em>3 are waiting for resources held by other waiting processes.<\/p>\r\n \r\n

    It is seen that there is a cycle <\/span>P<\/em>1 \u00ae <\/span>R<\/em>1 \u00ae <\/span>P<\/em>2 \u00ae <\/span>R<\/em>3 \u00ae <\/span>P<\/em>3 \u00ae <\/span>R<\/em>2 \u00ae <\/span>P<\/em>1. All the processes that are part of the cycle are waiting and there is no free instance \u00a0of resource. Therefore, all the processes in the cycle are deadlocked. None of the processes is able to proceed further.<\/span><\/p>\r\n\r\n<\/div>\r\n

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

    Fig. 16.3 Resource-allocation graph with a deadlock (Source: [1])<\/p>\r\n \r\n\r\n16.5.4\u00a0 <\/strong>Resource Allocation Graph With A Cycle But No Deadlock<\/strong>\r\n\r\n\"\"\r\n

    Fig. 16.4 Resource allocation graph with a cycle but no deadlock (Source: [1])<\/p>\r\n \r\n

    It is always not necessary to have a deadlock if there is a cycle. We now look at\u00a0an example scenario where there is a cycle in the resource-allocation graph, but there is no deadlock. Figure 16.4 shows a resource-allocation graph with a cycle <\/span>P<\/em>1 \u00ae <\/span>R<\/em>1 \u00ae <\/span>P<\/em>3\u00a0<\/span>\u00ae <\/span>R<\/em>2 \u00ae <\/span>P<\/em>1. But, in this scenario, an instance of <\/span>R<\/em>1 is held by process <\/span>P<\/em>2, which is not a waiting process. Once <\/span>P<\/em>2 finishes using the resource, it will release the resource. <\/span>R<\/em>1 will now be available for process <\/span>P<\/em>3. Similarly, an instance of <\/span>R<\/em>2 is held by process <\/span>P<\/em>4 and\u00a0<\/span>P<\/em>4 is not waiting for any other resource. Therefore, <\/span>P<\/em>4 releases the resource <\/span>R<\/em>2 after using the resource. Now, <\/span>R<\/em>2 is available for process <\/span>P<\/em>1.<\/span><\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n\r\nThus, from the examples given above, it is seen that\r\n\r\n \r\n\r\n\u2013 If a resource-allocation graph contains no cycles \u00de no deadlock.\r\n\r\n\u2013 If there are several instances per resource type and there is a cycle in the resource-allocation graph, there is a possibility of deadlock.<\/span>\r\n\r\n- If a resource-allocation graph contains a cycle \u00de \u00a0if there is only one instance per resource type, then there is deadlock.\r\n\r\n \r\n\r\n16.6 Methods for Handling Deadlocks\u00a0<\/strong>\r\n\r\n \r\n\r\nWe can deal with the deadlock problem in one of three ways:\r\n\r\n \r\n\r\n1. We can use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state.\r\n\r\n2. We can allow the system to enter a deadlock state, detect it, and recover.\r\n\r\n3. We can ignore the problem altogether, and pretend that deadlocks never occur in the system.\r\n\r\n \r\n

    To ensure that deadlocks never occur in a system, deadlock prevention or deadlock avoidance scheme can be used. Deadlock prevention is a set of methods for ensuring that at least one of the necessary conditions (Mutual exclusion, Hold and wait, No preemption, Circular wait) does not hold. These methods prevent deadlocks by constraining how requests for resources can be made.<\/p>\r\n \r\n

    Deadlock avoidance requires that the operating system should be given additional information about which resources a process will request and use during its life time. With this information, whenever a request for a resource comes from a process, the system can decide whether the request can be granted immediately or not. The system simulates and finds out if the system will go to a deadlocked state if the request is granted. Based on that, the system decides if the request can be granted or not.<\/p>\r\n \r\n

    If there is no mechanism employed in the system for deadlock prevention and avoidance, then deadlocks can occur. In this case, the system must employ algorithms for deadlock detection and recovery.<\/p>\r\n \r\n

    If the system does not employ algorithms even for deadlock detection and recovery, that is, if the problem is ignored altogether, then the system may be in a deadlock state and may not recognize what has happened. In this case, the system performance deteriorates and the system should be restarted manually. Although this method does not seem to be a viable approach, it is used in some operating systems.<\/p>\r\n \r\n\r\n16.7\u00a0 Summary<\/strong>\r\n\r\n \r\n

    Deadlocks may occur in a system that has shared resources. A system in which processes use resources can be depicted using a resource-allocation graph. A cycle in a resource-allocation graph may or may not indicate a deadlock.<\/span><\/p>\r\n\r\n<\/div>\r\n \r\n\r\nReferences<\/strong>\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

      16.1\u00a0 Introduction<\/strong><\/p>\n

       <\/p>\n

      Any system has many processes and a number of different resources. In such a system, processes request for resources, use them and then release them. If a process requests for resources and the resources are not available, the process waits. If the requested resources are held by other waiting processes, the requesting process continues to wait forever. This situation is called a deadlock.<\/span><\/p>\n

       <\/p>\n

      This module explains what is meant by a deadlock, the methods for handling deadlocks, what a resource-allocation graph is and how a resource-allocation graph can be used to handle deadlocks.<\/span><\/p>\n<\/div>\n

      \n

       <\/p>\n

      16.2\u00a0 ridge Crossing Example\u00a0<\/strong><\/p>\n

      \"\"<\/p>\n

      Fig. 16.1 Bridge crossing – deadlock<\/strong><\/p>\n

       <\/p>\n

      Consider vehicles crossing a bridge as shown in Figure 16.1. Vehicles can cross the bridge only in one direction at a particular time. If two vehicles that are moving in opposite directions try to cross the bridge at the same time, both get into a deadlocked situation. The deadlock can be resolved only if one vehicle backs up. To back up one vehicle, several other vehicles may also have to be backed up if a deadlock occurs.<\/p>\n

       <\/p>\n

      16.3 Deadlock Problem in a System<\/strong><\/p>\n

       <\/p>\n

      A situation similar to that of crossing a bridge can happen in a system as well. Suppose there is a set of blocked processes, each holding a resource and waiting to acquire a resource held by another process in the set. All the processes will be waiting for each other to release resources. Then, the system will be in a deadlocked state.<\/p>\n

       <\/p>\n

      Consider the following example: A system has 2 tape drives. There are two processes P<\/em>1 and P<\/em>2. Each process holds one tape drive and needs another one. Since there are only two tape drives in the system, each of the two processes is waiting for the tape drive held by the other waiting process. Now, both the processes are unable to proceed and are deadlocked.<\/p>\n<\/div>\n

       <\/p>\n

      Let us see another example. Though this example was explained in an earlier module, it is given here for better clarity. There are two semaphores, <\/span>A <\/em>and <\/span>B<\/em>, initialized to 1. Since the initial value is 1, each of the semaphores <\/span>A <\/em>and <\/span>B <\/em>is guarding resources that can be accessed only by one process at a time. Let <\/span>P<\/em>0 and <\/span>P<\/em>1 be two processes that are executing the following sequence of statements respectively.<\/span><\/p>\n

      \n

      \u00a0 \u00a0 P<\/em>0<\/sub>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0P<\/em>1<\/sub><\/p>\n

       <\/p>\n

      wait (A);\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 wait(B);<\/em><\/p>\n

      wait (B);\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 wait(A);<\/em><\/p>\n

       <\/p>\n

      Suppose P<\/em>0 executes wait(A<\/em>) first. This operation decrements the value of semaphore A <\/em>from 1 to 0. Suppose there is a context switch and P<\/em>1 executes wait(B<\/em>). This will decrement the value of semaphore B <\/em>from 1 to 0. Next, P<\/em>1 continues to execute wait(A<\/em>). Since the value of semaphore A <\/em>is 0, process P<\/em>1 waits. There is a context switch now and process P<\/em>0 executes wait(B<\/em>). Since the value of semaphore B <\/em>is 0, process P<\/em>0 waits. Here, we see that process P<\/em>0 is waiting for semaphore B <\/em>held by process P<\/em>1 and process P<\/em>1 is waiting for semaphore A <\/em>held by process P<\/em>0. Thus, both the processes are in a deadlocked state.<\/p>\n

       <\/p>\n

      16.4 System Model<\/strong><\/p>\n

       <\/p>\n

      Any system has a finite number of resources, distributed among a number of competing processes. The resources are categorized into several resource types R<\/em>1, R<\/em>2, …, R<\/em>m . The resource types in a system may be CPU cycles, memory space, I\/O devices and so on. Each resource type R<\/em>i has W<\/em>i instances. For example, if there are 5 printers, then there are 5 instances of the resource type printer.<\/p>\n

       <\/p>\n

      Each process utilizes resources as follows: Each process requests for resources, uses the resources and releases the resources after using the resources. A process may request as many resources as it requires to carry out its designated task. The number of resources requested by the process cannot exceed the total number of resources available in the system. That is, if there are five printers, the process cannot request for six.<\/p>\n

       <\/p>\n

      There are system calls available for the request and release of resources like the request <\/em>and release device<\/em>, open <\/em>and close file<\/em>, allocate <\/em>and free memory<\/em>. Request and release of resources can be accomplished through the wait and the signal operations on semaphores.<\/p>\n

       <\/p>\n

      A table is maintained in the system that records whether each resource is free or allocated. If a resource is allocated, information is maintained as to which process the resource is allocated. If a process requests a resource currently allocated to another process, the process is added to a queue of processes waiting for that resource.<\/p>\n

       <\/p>\n

      16.5 Deadlock Characterization<\/strong><\/p>\n

       <\/p>\n

      In a deadlocked system, processes never finish executing and system resources are tied up, preventing other jobs from starting. We shall now understand the features that characterize deadlocks.<\/p>\n<\/div>\n

      \n

       <\/p>\n

      16.5.1 Necessary conditions<\/strong><\/p>\n

       <\/p>\n

      Deadlocks can arise if the following four conditions hold simultaneously in a system:<\/p>\n

        \n
      • Mutual exclusion: If there is a non-shareable resource, only one process can use a resource at a time.<\/li>\n
      • Hold and\u00a0 wait:\u00a0 A process holding at least one resource is waiting to acquire additional resources held by other waiting processes.<\/li>\n
      • No preemption: A resource can be released only voluntarily by the process that is holding it after the process has completed its task. It is not possible to preempt a resource forcibly from a process.<\/li>\n
      • Circular wait: If there exists a set {P<\/em>0, P<\/em>1, \u2026, P<\/em>0} of waiting processes such that P<\/em>0 is waiting for a resource that is held by P<\/em>1, P<\/em>1 is waiting for a resource that is held by P<\/em>2, \u2026, P<\/em>n<\/em>\u20131 is waiting for a resource that is held by P<\/em>n, and P<\/em>n is waiting for a resource that is held by P<\/em>0.<\/li>\n<\/ul>\n

         <\/p>\n

        16.5.2 Resource-Allocation Graph<\/strong><\/p>\n

         <\/p>\n

        Any system can be described by means of a directed graph called a system resource-allocation graph. The graph consists of a set of vertices V <\/em>and a set of edges\u00a0E<\/em>. The set of vertices V is partitioned into two types, P <\/em>= {P<\/em>1, P<\/em>2, \u2026, P<\/em>n<\/em>}, the set consisting of all the processes in the system and R <\/em>= {R<\/em>1, R<\/em>2, \u2026, R<\/em>m<\/em>}, the set consisting of all the resource types in the system. A directed edge from P<\/em>i to R<\/em>j is denoted as P<\/em>i \u00ae\u00a0R<\/em>j and is called a request edge. A directed edge from R<\/em>j to P<\/em>i is denoted as R<\/em>j <\/em>\u00ae P<\/em>i <\/em>and is called an assignment edge.<\/p>\n

         <\/p>\n

        Pictorially, a process is denoted using a circle as shown below:<\/p>\n

        \"\"<\/p>\n

        A resource type is denoted using a square. The instances of a resource type are shown using dots inside the square. A resource type with 4 instances is denoted pictorially as shown below:<\/p>\n

        \"\"<\/p>\n

        When P<\/em>i requests an instance of R<\/em>j, it is denoted as an edge from P<\/em>i to R<\/em>j in the resource-allocation graph.<\/p>\n

        \"\"<\/p>\n

        When <\/span>P<\/em>i is holding an instance of <\/span>R<\/em>j, it is shown as an edge from a dot in <\/span>R<\/em>j to <\/span>P<\/em>i\u00a0<\/span>in the resource-allocation graph.<\/span><\/p>\n<\/div>\n

        \n

        \"\"<\/p>\n

        Figure 16.2 shows an example of a resource-allocation graph. P<\/em>1, P<\/em>2 and P<\/em>3 are the three processes in the system. There are four resource types, R<\/em>1, R<\/em>2, R<\/em>3 and R<\/em>4. There is one instance of R<\/em>1, two instances of R<\/em>2, one instance of R<\/em>3 and three instances of R<\/em>4. P<\/em>1 is holding one instance of R<\/em>2 and is requesting for one instance of R<\/em>1. P<\/em>2 is holding one instance of R<\/em>1 and one instance of R<\/em>2 and is requesting for one instance of R<\/em>3. P<\/em>3 is holding one instance of R<\/em>3.<\/p>\n<\/div>\n

        \"\"<\/p>\n

        \n

        Fig. 16.2 Resource-allocation graph (Source: [1])<\/p>\n

         <\/p>\n

        Deadlocks can be detected from a resource-allocation graph. If the resource-allocation graph contains no cycles, no process is deadlocked. If the resource-allocation graph contains cycles, deadlocks may exist. If there is only one instance of each resource type and there is a cycle in the graph, there is a deadlock in the system.<\/p>\n

         <\/p>\n

        16.5.3\u00a0 Resource-Allocation Graph With a Deadlock<\/strong><\/p>\n

         <\/p>\n

        Figure 16.3 shows a resource-allocation graph with a deadlock. In this figure, process P<\/em>1 is waiting for an instance of resource type R<\/em>1. There is only one instance of R<\/em>1 which is held by process P<\/em>2. P<\/em>2 is waiting for an instance of resource R<\/em>3. There is only one instance of R<\/em>3, which is held by process P<\/em>3. Process P<\/em>3 is waiting for an instance of R<\/em>2. There are two instances of R<\/em>2, each of which is held by P<\/em>1 \u00a0and P<\/em>2 respectively. Thus, P<\/em>1, P<\/em>2 and P<\/em>3 are waiting for resources held by other waiting processes.<\/p>\n

         <\/p>\n

        It is seen that there is a cycle <\/span>P<\/em>1 \u00ae <\/span>R<\/em>1 \u00ae <\/span>P<\/em>2 \u00ae <\/span>R<\/em>3 \u00ae <\/span>P<\/em>3 \u00ae <\/span>R<\/em>2 \u00ae <\/span>P<\/em>1. All the processes that are part of the cycle are waiting and there is no free instance \u00a0of resource. Therefore, all the processes in the cycle are deadlocked. None of the processes is able to proceed further.<\/span><\/p>\n<\/div>\n

        \n

        \"\"<\/p>\n

        Fig. 16.3 Resource-allocation graph with a deadlock (Source: [1])<\/p>\n

         <\/p>\n

        16.5.4\u00a0 <\/strong>Resource Allocation Graph With A Cycle But No Deadlock<\/strong><\/p>\n

        \"\"<\/p>\n

        Fig. 16.4 Resource allocation graph with a cycle but no deadlock (Source: [1])<\/p>\n

         <\/p>\n

        It is always not necessary to have a deadlock if there is a cycle. We now look at\u00a0an example scenario where there is a cycle in the resource-allocation graph, but there is no deadlock. Figure 16.4 shows a resource-allocation graph with a cycle <\/span>P<\/em>1 \u00ae <\/span>R<\/em>1 \u00ae <\/span>P<\/em>3\u00a0<\/span>\u00ae <\/span>R<\/em>2 \u00ae <\/span>P<\/em>1. But, in this scenario, an instance of <\/span>R<\/em>1 is held by process <\/span>P<\/em>2, which is not a waiting process. Once <\/span>P<\/em>2 finishes using the resource, it will release the resource. <\/span>R<\/em>1 will now be available for process <\/span>P<\/em>3. Similarly, an instance of <\/span>R<\/em>2 is held by process <\/span>P<\/em>4 and\u00a0<\/span>P<\/em>4 is not waiting for any other resource. Therefore, <\/span>P<\/em>4 releases the resource <\/span>R<\/em>2 after using the resource. Now, <\/span>R<\/em>2 is available for process <\/span>P<\/em>1.<\/span><\/p>\n<\/div>\n

        \n

         <\/p>\n

        Thus, from the examples given above, it is seen that<\/p>\n

         <\/p>\n

        \u2013 If a resource-allocation graph contains no cycles \u00de no deadlock.<\/p>\n

        \u2013 If there are several instances per resource type and there is a cycle in the resource-allocation graph, there is a possibility of deadlock.<\/span><\/p>\n

        – If a resource-allocation graph contains a cycle \u00de \u00a0if there is only one instance per resource type, then there is deadlock.<\/p>\n

         <\/p>\n

        16.6 Methods for Handling Deadlocks\u00a0<\/strong><\/p>\n

         <\/p>\n

        We can deal with the deadlock problem in one of three ways:<\/p>\n

         <\/p>\n

        1. We can use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state.<\/p>\n

        2. We can allow the system to enter a deadlock state, detect it, and recover.<\/p>\n

        3. We can ignore the problem altogether, and pretend that deadlocks never occur in the system.<\/p>\n

         <\/p>\n

        To ensure that deadlocks never occur in a system, deadlock prevention or deadlock avoidance scheme can be used. Deadlock prevention is a set of methods for ensuring that at least one of the necessary conditions (Mutual exclusion, Hold and wait, No preemption, Circular wait) does not hold. These methods prevent deadlocks by constraining how requests for resources can be made.<\/p>\n

         <\/p>\n

        Deadlock avoidance requires that the operating system should be given additional information about which resources a process will request and use during its life time. With this information, whenever a request for a resource comes from a process, the system can decide whether the request can be granted immediately or not. The system simulates and finds out if the system will go to a deadlocked state if the request is granted. Based on that, the system decides if the request can be granted or not.<\/p>\n

         <\/p>\n

        If there is no mechanism employed in the system for deadlock prevention and avoidance, then deadlocks can occur. In this case, the system must employ algorithms for deadlock detection and recovery.<\/p>\n

         <\/p>\n

        If the system does not employ algorithms even for deadlock detection and recovery, that is, if the problem is ignored altogether, then the system may be in a deadlock state and may not recognize what has happened. In this case, the system performance deteriorates and the system should be restarted manually. Although this method does not seem to be a viable approach, it is used in some operating systems.<\/p>\n

         <\/p>\n

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

         <\/p>\n

        Deadlocks may occur in a system that has shared resources. A system in which processes use resources can be depicted using a resource-allocation graph. A cycle in a resource-allocation graph may or may not indicate a deadlock.<\/span><\/p>\n<\/div>\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":13,"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-154","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\/154","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":4,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/154\/revisions"}],"predecessor-version":[{"id":418,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapters\/154\/revisions\/418"}],"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\/154\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/media?parent=154"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/pressbooks\/v2\/chapter-type?post=154"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/contributor?post=154"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp3\/wp-json\/wp\/v2\/license?post=154"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}