{"id":2277,"date":"2021-01-27T14:53:55","date_gmt":"2021-01-27T09:23:55","guid":{"rendered":"https:\/\/binaryterms.com\/?p=2277"},"modified":"2021-01-28T15:40:21","modified_gmt":"2021-01-28T10:10:21","slug":"deadlock-characterization","status":"publish","type":"post","link":"https:\/\/binaryterms.com\/deadlock-characterization.html","title":{"rendered":"Deadlock Characterization"},"content":{"rendered":"

Deadlock characterization<\/strong> describes the distinctive features that are the cause of deadlock occurrence. Deadlock is a condition in the multiprogramming environment where the executing processes get stuck in the middle of execution waiting for the resources that have been held by the other waiting processes thereby preventing the execution of the processes.<\/p>\n

In this content, we will discuss the characteristics that are essential for the occurrence of deadlock. The four conditions that must sustain at the same time to eventuate a deadlock are: mutual experience, hold and wait, no preemption, circular wait.<\/p>\n

Deadlock Characterization<\/h2>\n
    \n
  1. Deadlock Prerequisites<\/li>\n
  2. Systems Resource Allocation Graph<\/li>\n<\/ol>\n

    Deadlock Prerequisites<\/h3>\n

    i) Mutual Exclusion<\/strong><\/p>\n

    In a multiprogramming environment, there may be several processes requesting the same resource at a time. The mutual exclusion condition, allow only a single process to access the resource at a time. While the other processes requesting the same resource must wait and delay their execution until it has been released. The mutual exclusion condition prevents two or more processes to access the same resource at a time.<\/p>\n

    ii) Hold and wait<\/strong><\/p>\n

    The hold and wait condition simply means that the process must be holding access to one resource and must be waiting to get hold of other resources that have been acquired by the other processes.<\/p>\n

    iii) No Preemption<\/strong><\/p>\n

    A process acquiring a resource, cannot be preempted in between, to release the acquired resource. Instead, the process must voluntarily release the resource it has acquired when the task of the process has been completed.<\/p>\n

    iv) Circular Wait<\/strong><\/p>\n

    The processes must be waiting in a circular pattern to acquire the resource. This is similar to hold and waits the only difference is that the processes are waiting in a circular pattern.<\/p>\n

    Let us discuss this with an example there are five processes i.e. P0<\/sub>, P1, <\/sub>P2, <\/sub>P3, <\/sub>P4<\/sub>. Now the process P0<\/sub> is waiting to acquire the process held by the P1<\/sub>, further the process P1<\/sub> is waiting to acquire the resource held by P2<\/sub>, \u2026., process P4<\/sub> is waiting to acquire the resource held by P0.<\/sub><\/p>\n

    System Resource Allocation Graph<\/h3>\n

    The system reallocation graph is a directed graph that briefs you about the deadlock more precisely. Like every graph, it also has a set of vertices<\/strong> and a set of edges.<\/strong> Further, the set of vertices can be classified into two types of nodes P and R. Where P is the set of vertices indicating the set of active processes<\/em> and R is the set of vertices indicating all types of resources<\/em> in the system.<\/p>\n

    When a process requests for a resource it denoted by the request edge<\/strong> in the resource-allocation graph. The request edge is a directed edge from the requesting process Pi<\/sub> to requested resource Rj <\/sub>i.e. Pi<\/sub> -> Rj<\/sub>.<\/p>\n

    Well, when a resource is allotted to some process then it is denoted by the assignment edge<\/strong>. The assignment edge is the directed edge from the instance of resource R\u00adj<\/sub> to the process P\u00adi<\/sub> i.e. Rj<\/sub> -> Pi<\/sub>.<\/p>\n

    In the graph, resources are denoted by the rectangles<\/strong> and the processes are denoted by the circles.<\/strong> If a resource has multiple instances then it is denoted by the dots<\/strong> inside the rectangle.<\/p>\n

    When a process request for an instance of the resource it directs a request edge to the resource. If the resource is able to allocate the resource instance to the requesting process then immediately the request edge is converted to assignment edge.<\/p>\n

    The request edge always points to the resource rectangle in the graph, not to dots (instance) inside the rectangle. Although the assignment edge nominates the dot (instance) to a process.<\/p>\n

    To understand deadlock we let us take an example. Consider we have following set of nodes and edges.<\/p>\n

      \n
    1. There are three active processes P = {P1<\/sub>, P2<\/sub>, P3<\/sub>}<\/li>\n
    2. There are four resources R = { R1, <\/sub>R2<\/sub>, R3<\/sub>, R4<\/sub>}<\/li>\n
    3. The set of request edge and assignment edges we have
      \nE = { P1 -> R1<\/sub>, P2<\/sub> -> R3<\/sub>, R1<\/sub> -> P2<\/sub>, R2<\/sub> -> P2<\/sub>, R2 <\/sub>-> P1<\/sub>, R3<\/sub> -> P3<\/sub>}<\/li>\n<\/ol>\n

      Observe the figure above that the resource R\u00ad1<\/sub> has only one instance, resource R2<\/sub> has two instances, resource R3<\/sub>\u00a0has one instance, and resource R4<\/sub> has three instances. Let us check the status of the processes.<\/p>\n

      The figure below shows that the process P1 <\/sub>has requested for the instance of resource R1<\/sub> is already holding the instance of resource R2<\/sub>. The process P2<\/sub>\u00a0has requested for the instance of resource R3<\/sub> and is already holding the instances of resource R1 <\/sub>and R3<\/sub>. The process P3 <\/sub>has not requested for any resource instance but is holding the instance for resource R3<\/sub>.<\/p>\n

      \"Resource<\/p>\n

      Remember if the resource allocation graph has a cycle and every resource has a single instance then it implies that a deadlock has occurred. In case, the resources have multiple instances then a cycle in the graph need not be indicating the occurrence of deadlock.<\/p>\n

      Consider that the process P3<\/sub> is requesting for the instance of resource R2<\/sub> which is already held by the process P1<\/sub> and P2<\/sub>. In this case, you will observe that there are two cycles in the resource allocation graph:<\/p>\n

        \n
      • P1<\/sub> -> R 1<\/sub> -> P2<\/sub> -> R3<\/sub> -> P3<\/sub> -> R2<\/sub> -> P1<\/sub><\/li>\n
      • P2<\/sub> -> R3<\/sub> -> P3<\/sub> -> R2<\/sub> -> P2<\/sub><\/li>\n<\/ul>\n

        \"Dead<\/p>\n

        Process P1<\/sub>, P2<\/sub> and P3<\/sub> are now in deadlock as each process in the cycle is waiting for the resource held by another process. But every cycle in the resource allocation graph does not indicate the deadlock, you have to observe the cycle carefully while dealing with deadlock problem.\u00a0So, this is how you can characterize the deadlock in the system.<\/p>\n","protected":false},"excerpt":{"rendered":"

        Deadlock characterization describes the distinctive features that are the cause of deadlock occurrence. Deadlock is a condition in the multiprogramming environment where the executing processes get stuck in the middle of execution waiting for the resources that have been held by the other waiting processes thereby preventing the execution of the processes. In this content, […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_genesis_hide_title":false,"_genesis_hide_breadcrumbs":false,"_genesis_hide_singular_image":false,"_genesis_hide_footer_widgets":false,"_genesis_custom_body_class":"","_genesis_custom_post_class":"","_genesis_layout":"","footnotes":""},"categories":[2],"tags":[],"class_list":{"0":"post-2277","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-operating-system","7":"entry"},"yoast_head":"\nWhat is Deadlock Characterization? - Binary Terms<\/title>\n<meta name=\"description\" content=\"Deadlock characterization describes the distinctive features that are manadatory and essential for the occurence of deadlock.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/binaryterms.com\/deadlock-characterization.html\" \/>\n<meta property=\"og:locale\" content=\"en_GB\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"What is Deadlock Characterization? - Binary Terms\" \/>\n<meta property=\"og:description\" content=\"Deadlock characterization describes the distinctive features that are manadatory and essential for the occurence of deadlock.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/binaryterms.com\/deadlock-characterization.html\" \/>\n<meta property=\"og:site_name\" content=\"Binary Terms\" \/>\n<meta property=\"article:published_time\" content=\"2021-01-27T09:23:55+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2021-01-28T10:10:21+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/01\/Resource-allocation-dead-lock-characterization.jpg\" \/>\n<meta name=\"author\" content=\"Neha T\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Neha T\" \/>\n\t<meta name=\"twitter:label2\" content=\"Estimated reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/binaryterms.com\/deadlock-characterization.html#article\",\"isPartOf\":{\"@id\":\"https:\/\/binaryterms.com\/deadlock-characterization.html\"},\"author\":{\"name\":\"Neha T\",\"@id\":\"https:\/\/binaryterms.com\/#\/schema\/person\/e495f1d57f5c0a4c521cc3dba95661fe\"},\"headline\":\"Deadlock Characterization\",\"datePublished\":\"2021-01-27T09:23:55+00:00\",\"dateModified\":\"2021-01-28T10:10:21+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/binaryterms.com\/deadlock-characterization.html\"},\"wordCount\":957,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/binaryterms.com\/#organization\"},\"image\":{\"@id\":\"https:\/\/binaryterms.com\/deadlock-characterization.html#primaryimage\"},\"thumbnailUrl\":\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/01\/Resource-allocation-dead-lock-characterization.jpg\",\"articleSection\":[\"Operating System\"],\"inLanguage\":\"en-GB\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/binaryterms.com\/deadlock-characterization.html#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/binaryterms.com\/deadlock-characterization.html\",\"url\":\"https:\/\/binaryterms.com\/deadlock-characterization.html\",\"name\":\"What is Deadlock Characterization? - Binary Terms\",\"isPartOf\":{\"@id\":\"https:\/\/binaryterms.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/binaryterms.com\/deadlock-characterization.html#primaryimage\"},\"image\":{\"@id\":\"https:\/\/binaryterms.com\/deadlock-characterization.html#primaryimage\"},\"thumbnailUrl\":\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/01\/Resource-allocation-dead-lock-characterization.jpg\",\"datePublished\":\"2021-01-27T09:23:55+00:00\",\"dateModified\":\"2021-01-28T10:10:21+00:00\",\"description\":\"Deadlock characterization describes the distinctive features that are manadatory and essential for the occurence of deadlock.\",\"breadcrumb\":{\"@id\":\"https:\/\/binaryterms.com\/deadlock-characterization.html#breadcrumb\"},\"inLanguage\":\"en-GB\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/binaryterms.com\/deadlock-characterization.html\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-GB\",\"@id\":\"https:\/\/binaryterms.com\/deadlock-characterization.html#primaryimage\",\"url\":\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/01\/Resource-allocation-dead-lock-characterization.jpg\",\"contentUrl\":\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/01\/Resource-allocation-dead-lock-characterization.jpg\",\"width\":448,\"height\":384,\"caption\":\"Resource allocation dead lock characterization\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/binaryterms.com\/deadlock-characterization.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/binaryterms.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Deadlock Characterization\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/binaryterms.com\/#website\",\"url\":\"https:\/\/binaryterms.com\/\",\"name\":\"Binary Terms\",\"description\":\"The Computer Science & IT Guide\",\"publisher\":{\"@id\":\"https:\/\/binaryterms.com\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/binaryterms.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-GB\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/binaryterms.com\/#organization\",\"name\":\"Binary Terms\",\"url\":\"https:\/\/binaryterms.com\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-GB\",\"@id\":\"https:\/\/binaryterms.com\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/binaryterms.com\/wp-content\/uploads\/2020\/05\/binary-terms-logo1.png\",\"contentUrl\":\"https:\/\/binaryterms.com\/wp-content\/uploads\/2020\/05\/binary-terms-logo1.png\",\"width\":400,\"height\":63,\"caption\":\"Binary Terms\"},\"image\":{\"@id\":\"https:\/\/binaryterms.com\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/binaryterms.com\/#\/schema\/person\/e495f1d57f5c0a4c521cc3dba95661fe\",\"name\":\"Neha T\",\"url\":\"https:\/\/binaryterms.com\/author\/author\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"What is Deadlock Characterization? - Binary Terms","description":"Deadlock characterization describes the distinctive features that are manadatory and essential for the occurence of deadlock.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/binaryterms.com\/deadlock-characterization.html","og_locale":"en_GB","og_type":"article","og_title":"What is Deadlock Characterization? - Binary Terms","og_description":"Deadlock characterization describes the distinctive features that are manadatory and essential for the occurence of deadlock.","og_url":"https:\/\/binaryterms.com\/deadlock-characterization.html","og_site_name":"Binary Terms","article_published_time":"2021-01-27T09:23:55+00:00","article_modified_time":"2021-01-28T10:10:21+00:00","og_image":[{"url":"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/01\/Resource-allocation-dead-lock-characterization.jpg","type":"","width":"","height":""}],"author":"Neha T","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Neha T","Estimated reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/binaryterms.com\/deadlock-characterization.html#article","isPartOf":{"@id":"https:\/\/binaryterms.com\/deadlock-characterization.html"},"author":{"name":"Neha T","@id":"https:\/\/binaryterms.com\/#\/schema\/person\/e495f1d57f5c0a4c521cc3dba95661fe"},"headline":"Deadlock Characterization","datePublished":"2021-01-27T09:23:55+00:00","dateModified":"2021-01-28T10:10:21+00:00","mainEntityOfPage":{"@id":"https:\/\/binaryterms.com\/deadlock-characterization.html"},"wordCount":957,"commentCount":0,"publisher":{"@id":"https:\/\/binaryterms.com\/#organization"},"image":{"@id":"https:\/\/binaryterms.com\/deadlock-characterization.html#primaryimage"},"thumbnailUrl":"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/01\/Resource-allocation-dead-lock-characterization.jpg","articleSection":["Operating System"],"inLanguage":"en-GB","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/binaryterms.com\/deadlock-characterization.html#respond"]}]},{"@type":"WebPage","@id":"https:\/\/binaryterms.com\/deadlock-characterization.html","url":"https:\/\/binaryterms.com\/deadlock-characterization.html","name":"What is Deadlock Characterization? - Binary Terms","isPartOf":{"@id":"https:\/\/binaryterms.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/binaryterms.com\/deadlock-characterization.html#primaryimage"},"image":{"@id":"https:\/\/binaryterms.com\/deadlock-characterization.html#primaryimage"},"thumbnailUrl":"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/01\/Resource-allocation-dead-lock-characterization.jpg","datePublished":"2021-01-27T09:23:55+00:00","dateModified":"2021-01-28T10:10:21+00:00","description":"Deadlock characterization describes the distinctive features that are manadatory and essential for the occurence of deadlock.","breadcrumb":{"@id":"https:\/\/binaryterms.com\/deadlock-characterization.html#breadcrumb"},"inLanguage":"en-GB","potentialAction":[{"@type":"ReadAction","target":["https:\/\/binaryterms.com\/deadlock-characterization.html"]}]},{"@type":"ImageObject","inLanguage":"en-GB","@id":"https:\/\/binaryterms.com\/deadlock-characterization.html#primaryimage","url":"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/01\/Resource-allocation-dead-lock-characterization.jpg","contentUrl":"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/01\/Resource-allocation-dead-lock-characterization.jpg","width":448,"height":384,"caption":"Resource allocation dead lock characterization"},{"@type":"BreadcrumbList","@id":"https:\/\/binaryterms.com\/deadlock-characterization.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/binaryterms.com\/"},{"@type":"ListItem","position":2,"name":"Deadlock Characterization"}]},{"@type":"WebSite","@id":"https:\/\/binaryterms.com\/#website","url":"https:\/\/binaryterms.com\/","name":"Binary Terms","description":"The Computer Science & IT Guide","publisher":{"@id":"https:\/\/binaryterms.com\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/binaryterms.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-GB"},{"@type":"Organization","@id":"https:\/\/binaryterms.com\/#organization","name":"Binary Terms","url":"https:\/\/binaryterms.com\/","logo":{"@type":"ImageObject","inLanguage":"en-GB","@id":"https:\/\/binaryterms.com\/#\/schema\/logo\/image\/","url":"https:\/\/binaryterms.com\/wp-content\/uploads\/2020\/05\/binary-terms-logo1.png","contentUrl":"https:\/\/binaryterms.com\/wp-content\/uploads\/2020\/05\/binary-terms-logo1.png","width":400,"height":63,"caption":"Binary Terms"},"image":{"@id":"https:\/\/binaryterms.com\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/binaryterms.com\/#\/schema\/person\/e495f1d57f5c0a4c521cc3dba95661fe","name":"Neha T","url":"https:\/\/binaryterms.com\/author\/author"}]}},"_links":{"self":[{"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/posts\/2277","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/comments?post=2277"}],"version-history":[{"count":8,"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/posts\/2277\/revisions"}],"predecessor-version":[{"id":2287,"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/posts\/2277\/revisions\/2287"}],"wp:attachment":[{"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/media?parent=2277"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/categories?post=2277"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/binaryterms.com\/wp-json\/wp\/v2\/tags?post=2277"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}