{"id":28296,"date":"2017-12-24T16:08:04","date_gmt":"2017-12-24T10:38:04","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=28296"},"modified":"2017-12-24T16:08:04","modified_gmt":"2017-12-24T10:38:04","slug":"bankers-algorithm","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/bankers-algorithm\/","title":{"rendered":"Banker\u2019s Algorithm"},"content":{"rendered":"<p>The banker\u2019s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an \u201cs-state\u201d check to test for possible activities, before deciding whether allocation should be allowed to continue.<\/p>\n<p>Following <strong>Data structures<\/strong> are used to implement the Banker\u2019s Algorithm:<\/p>\n<p>Let <strong>\u2018n\u2019 <\/strong>be the number of processes in the system and\u00a0<strong>\u2018m\u2019 <\/strong>be the number of resources types.<\/p>\n<p><strong>Available :\u00a0<\/strong><\/p>\n<ul>\n<li>It is a 1-d array of size <strong>\u2018m\u2019<\/strong> indicating the number of available resources of each type.<\/li>\n<li>Available[ j ] = k means there are <strong>\u2018k\u2019<\/strong> instances of resource type <strong>R<sub>j<\/sub><\/strong><\/li>\n<\/ul>\n<p><strong>Max :<\/strong><\/p>\n<ul>\n<li>It is a 2-d array of size \u2018<strong>n*m\u2019 <\/strong>that defines the maximum demand of each process in a system.<\/li>\n<li>Max[ i, j ] = k means process <strong>P<sub>i<\/sub><\/strong> may request at most <strong>\u2018k\u2019<\/strong> instances of resource type <strong>R<sub>j.<\/sub><\/strong><\/li>\n<\/ul>\n<p><strong>Allocation :<\/strong><\/p>\n<ul>\n<li>It is a 2-d array of size<strong> \u2018n*m\u2019 <\/strong>that defines the number of resources of each type currently allocated to each process.<\/li>\n<li>Allocation[ i, j ] = k means process <strong>P<sub>i<\/sub><\/strong> is currently allocated <strong>\u2018k\u2019<\/strong> instances of resource type <strong>R<sub>j<\/sub><\/strong><\/li>\n<\/ul>\n<p><strong>Need :<\/strong><\/p>\n<ul>\n<li>\u00a0It is a 2-d array of size <strong>\u2018n*m\u2019<\/strong> that indicates the remaining resource need of each process.<\/li>\n<li>Need [ i,\u00a0 j ] = k means process <strong>P<sub>i<\/sub><\/strong> currently allocated <strong>\u2018k\u2019<\/strong> instances of resource type <strong>R<sub>j<\/sub><\/strong><\/li>\n<li>Need [ i,\u00a0 j ] = Max [ i,\u00a0 j ] \u2013 Allocation [ i,\u00a0 j ]<\/li>\n<\/ul>\n<p>Allocation<sub>i<\/sub> specifies the resources currently allocated to process P<sub>i<\/sub> and Need<sub>i<\/sub> specifies the additional resources that process P<sub>i<\/sub> may still request to complete its task.<\/p>\n<p>Banker\u2019s algorithm consist of Safety algorithm and Resource request algorithm<\/p>\n<p><b>Safety Algorithm<\/b><\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-28304\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/safety-algorithm.png\" alt=\"Banker\u2019s Algorithm\" width=\"672\" height=\"419\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/safety-algorithm.png 672w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/safety-algorithm-300x187.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/safety-algorithm-320x200.png 320w\" sizes=\"(max-width: 672px) 100vw, 672px\" \/><\/p>\n<p><strong>Resource-Request Algorithm<\/strong><\/p>\n<p>Let Request<sub>i<\/sub> be the request array for process P<sub>i<\/sub>. Request<sub>i <\/sub>[j] = k means process P<sub>i<\/sub> wants k instances of resource type R<sub>j<\/sub>. When a request for resources is made by process P<sub>i<\/sub>, the following actions are taken:<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-28306\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/resource-allocation-algorithm.png\" alt=\"Resource-Request Algorithm Let Requesti be the request array for process Pi. Requesti [j] = k means process Pi wants k instances of resource type Rj. When a request for resources is made by process Pi, the following actions are taken:\" width=\"753\" height=\"288\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/resource-allocation-algorithm.png 753w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/resource-allocation-algorithm-300x115.png 300w\" sizes=\"(max-width: 753px) 100vw, 753px\" \/><\/p>\n<p><strong>Example:<\/strong><\/p>\n<p><strong>Considering a system with five processes P<sub>0<\/sub> through P<sub>4<\/sub> and three resources types A, B, C. Resource type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time t<sub>0<\/sub> following snapshot of the system has been taken:<\/strong><\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-28314\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/safety-1.png\" alt=\"Banker\u2019s Algorithm\" width=\"472\" height=\"220\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/safety-1.png 472w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/safety-1-300x140.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/safety-1-470x220.png 470w\" sizes=\"(max-width: 472px) 100vw, 472px\" \/><\/p>\n<p><strong>Question1.\u00a0What will be the content of the Need matrix?<\/strong><\/p>\n<p>Need [i, j] = Max [i, j] \u2013 Allocation [i, j]\n<p>So, the content of Need Matrix is:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-28324\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/unnamed.png\" alt=\" Banker\u2019s Algorithm\" width=\"228\" height=\"211\" \/><\/p>\n<p><strong>Question2.\u00a0 Is the system in safe state? If Yes, then what is the safe sequence?<\/strong><\/p>\n<p>Applying the Safety algorithm on the given system,<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-28329\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/questionsolved-1024x632.png\" alt=\"Banker\u2019s Algorithm\" width=\"1024\" height=\"632\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/questionsolved-1024x632.png 1024w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/questionsolved-1024x632-300x185.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/questionsolved-1024x632-768x474.png 768w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/questionsolved-1024x632-990x611.png 990w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/p>\n<p><strong>Question3. What will happen if process\u00a0P<sub>1\u00a0<\/sub>requests one additional instance of resource type A and two instances of resource type C?<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-28336\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Allocation.png\" alt=\"Banker\u2019s Algorithm\" width=\"770\" height=\"394\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Allocation.png 770w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Allocation-300x154.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Allocation-768x393.png 768w\" sizes=\"(max-width: 770px) 100vw, 770px\" \/><\/p>\n<p>We must determine whether this new system state is safe. To do so, we again execute Safety algorithm on the above data structures.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-28339\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Q31-1024x636.png\" alt=\"Banker\u2019s Algorithm\" width=\"1024\" height=\"636\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Q31-1024x636.png 1024w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Q31-1024x636-300x186.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Q31-1024x636-768x477.png 768w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Q31-1024x636-320x200.png 320w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Q31-1024x636-990x615.png 990w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/p>\n<p>Hence the new system state is safe, so we can immediately grant the request for process\u00a0<strong>\u00a0P<sub>1 .<\/sub><\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Banker\u2019s Algorithm- Operating System &#8211; The banker\u2019s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,71771,82275],"tags":[82787,82785,82788,82786,82790,82791,82789],"class_list":["post-28296","post","type-post","status-publish","format-standard","hentry","category-coding","category-cs-subjects","category-operating-systems","tag-banker-algorithm-in-operating-system-with-example-ppt","tag-bankers-algorithm-explanation","tag-bankers-algorithm-program-in-c","tag-bankers-algorithm-questions-and-answers","tag-bankers-algorithm-tutorial-point","tag-resource-request-algorithm","tag-safety-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28296","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=28296"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28296\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=28296"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=28296"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=28296"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}