Deadlocks
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Deadlocks as PDF for free.
More details
- Words: 1,143
- Pages: 21
DEADLOCKS
Lecture Series By : Website ::
Er. Kanwalvir Singh Dhindsa www.dhindsa.info
http://groups.google.com/group/os-2007 1
O.S. by Er. K.S.Dhindsa © 2007
DEADLOCK DETECTION & RECOVERY Detection with One Resource of Each Type (1) IF graph contains one or more cycles {any process part of cycle},a deadlock exists IF no cycle exists,system is not deadlocked Algorithm takes each node,as the root like of a tree and does DFS on it If it ever comes back to a node it has already encountered, it has found a cycle If it exhausts all the arcs from any given node,it backtracks to the previous node {then does not contain cycle} If this property holds for all nodes, entire graph is cycle free & hence system not deadlocked
2
O.S. by Er. K.S.Dhindsa © 2007
DEADLOCK DETECTION & RECOVERY Detection with One Resource of Each Type (1) • Process A holds R and wants S • Process B holds nothing but wants T • Process C holds nothing but wants S • Process D holds U and wants S &T • Process E holds T & wants V • Process F holds W and wants S • Process G holds V and wants U
D,E and G are deadlocked
L={R,A,S} L={B,T,E,V,G,U,D,T} 3
O.S. by Er. K.S.Dhindsa © 2007
Detection with Multiple Resource of Each Type (2)
Data structures needed by deadlock detection algorithm 4
O.S. by Er. K.S.Dhindsa © 2007
Detection with Multiple Resource of Each Type (2)
An example for the deadlock detection algorithm 5
O.S. by Er. K.S.Dhindsa © 2007
Deadlock Avoidance Safe and Unsafe States (1) A STATE IS said to be safe if it is not deadlocked and there is some scheduling order in which every process can run to completion even if all of them suddenly request their maximum no. of resources immediately (a)
(b)
(c)
(d)
Demonstration that the state in (a) is safe
(e)
6
O.S. by Er. K.S.Dhindsa © 2007
Safe and Unsafe States (2)
(a)
(b)
(c)
(d)
Demonstration that the state in b is not safe 7
O.S. by Er. K.S.Dhindsa © 2007
Basic Facts • If a system is in safe state ⇒ no deadlocks • If a system is in unsafe state ⇒ possibility of deadlock • Avoidance ⇒ ensure that a system will never enter an unsafe state 8
O.S. by Er. K.S.Dhindsa © 2007
Safe, Unsafe , Deadlock State
9
O.S. by Er. K.S.Dhindsa © 2007
Deadlock Avoidance I. The Dijkstra(1965) Banker's Algorithm for a Single Resource
(a)
(b)
(c)
• Three resource allocation states – safe – safe – unsafe 10
O.S. by Er. K.S.Dhindsa © 2007
The Banker's Algorithm for a Single Resource Modeled on the way a small-town banker might deal with a group of customers to whom he has granted lines of credit Checks to see if granting the request leads to an unsafe state If it does,request is denied If granting the request leads to a safe state,it is carried out Diagram shows four customers( A,B,C,D) each of them granted a no. of credit units Customers – processes, Units -- tape drives & Banker – Operating system 11
O.S. by Er. K.S.Dhindsa © 2007
II. Banker's Algorithm for Multiple Resources
Example of banker's algorithm with multiple resources 12
O.S. by Er. K.S.Dhindsa © 2007
Deadlock Prevention Restrain the ways request can be made
• Mutual Exclusion – not required for sharable resources; must hold for nonsharable resources • Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources. – Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none. – Low resource utilization; starvation possible. 13
O.S. by Er. K.S.Dhindsa © 2007
Deadlock Prevention (Cont.) • No Preemption – – If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released. – Preempted resources are added to the list of resources for which the process is waiting. – Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting. • Circular Wait – impose a total ordering of all resource types, and require that each process requests resources 14 in an increasing order of enumeration. O.S. by Er. K.S.Dhindsa © 2007
Recovery from Deadlock I.
PROCESS TERMINATION
• Abort all deadlocked processes • Abort one process at a time until the deadlock cycle is eliminated In which order should we choose to abort? – Priority of the process – How long process has computed, and how much longer to completion – Resources the process has used – Resources process needs to complete – How many processes will need to be terminated 15 – Is process interactive or batch?
O.S. by Er. K.S.Dhindsa © 2007
Recovery from Deadlock (contd) II. Resource Preemption • Selecting a victim – minimize cost {Which resources & which processes are to be preempted?} • Rollback – return to some safe state, restart process for that state {Total Rollback also can be done } • Starvation – same process may always be picked as victim {process could be picked as victim only for a finite no. of times} 16
O.S. by Er. K.S.Dhindsa © 2007
Thrashing • If a process does not have “enough” pages, the page-fault rate is very high • Leading to: – low CPU utilization – operating system thinks that it needs to increase the degree of multiprogramming – another process added to the system • Thrashing ≡ a process is busy swapping pages in and out (If it is spending more time paging than executing) 17
O.S. by Er. K.S.Dhindsa © 2007
Thrashing (Cont.)
18
O.S. by Er. K.S.Dhindsa © 2007
Working-Set Model • Works on the assumption of locality ∀ ∆ ≡ working-set window ≡ a fixed number of page references Example: 10,000 instruction • WSSi (working set of Process Pi) = total number of pages referenced in the most recent ∆ (varies in time) – if ∆ too small will not encompass entire locality – if ∆ too large will encompass several localities – if ∆ = ∞ ⇒ will encompass entire program • D = Σ WSSi ≡ total demand frames • • • •
If D > m (no. of available frames) ⇒ Thrashing Policy if D > m, then suspend one of the processes Prevents thrashing while keeping degree of multiprogramming as high as possible Optimizes CPU Utilization
19
O.S. by Er. K.S.Dhindsa © 2007
Working-set model
20
O.S. by Er. K.S.Dhindsa © 2007
DEADLOCKS
Lecture Series By : Website ::
Er. Kanwalvir Singh Dhindsa www.dhindsa.info
http://groups.google.com/group/os-2007 21
O.S. by Er. K.S.Dhindsa © 2007
Lecture Series By : Website ::
Er. Kanwalvir Singh Dhindsa www.dhindsa.info
http://groups.google.com/group/os-2007 1
O.S. by Er. K.S.Dhindsa © 2007
DEADLOCK DETECTION & RECOVERY Detection with One Resource of Each Type (1) IF graph contains one or more cycles {any process part of cycle},a deadlock exists IF no cycle exists,system is not deadlocked Algorithm takes each node,as the root like of a tree and does DFS on it If it ever comes back to a node it has already encountered, it has found a cycle If it exhausts all the arcs from any given node,it backtracks to the previous node {then does not contain cycle} If this property holds for all nodes, entire graph is cycle free & hence system not deadlocked
2
O.S. by Er. K.S.Dhindsa © 2007
DEADLOCK DETECTION & RECOVERY Detection with One Resource of Each Type (1) • Process A holds R and wants S • Process B holds nothing but wants T • Process C holds nothing but wants S • Process D holds U and wants S &T • Process E holds T & wants V • Process F holds W and wants S • Process G holds V and wants U
D,E and G are deadlocked
L={R,A,S} L={B,T,E,V,G,U,D,T} 3
O.S. by Er. K.S.Dhindsa © 2007
Detection with Multiple Resource of Each Type (2)
Data structures needed by deadlock detection algorithm 4
O.S. by Er. K.S.Dhindsa © 2007
Detection with Multiple Resource of Each Type (2)
An example for the deadlock detection algorithm 5
O.S. by Er. K.S.Dhindsa © 2007
Deadlock Avoidance Safe and Unsafe States (1) A STATE IS said to be safe if it is not deadlocked and there is some scheduling order in which every process can run to completion even if all of them suddenly request their maximum no. of resources immediately (a)
(b)
(c)
(d)
Demonstration that the state in (a) is safe
(e)
6
O.S. by Er. K.S.Dhindsa © 2007
Safe and Unsafe States (2)
(a)
(b)
(c)
(d)
Demonstration that the state in b is not safe 7
O.S. by Er. K.S.Dhindsa © 2007
Basic Facts • If a system is in safe state ⇒ no deadlocks • If a system is in unsafe state ⇒ possibility of deadlock • Avoidance ⇒ ensure that a system will never enter an unsafe state 8
O.S. by Er. K.S.Dhindsa © 2007
Safe, Unsafe , Deadlock State
9
O.S. by Er. K.S.Dhindsa © 2007
Deadlock Avoidance I. The Dijkstra(1965) Banker's Algorithm for a Single Resource
(a)
(b)
(c)
• Three resource allocation states – safe – safe – unsafe 10
O.S. by Er. K.S.Dhindsa © 2007
The Banker's Algorithm for a Single Resource Modeled on the way a small-town banker might deal with a group of customers to whom he has granted lines of credit Checks to see if granting the request leads to an unsafe state If it does,request is denied If granting the request leads to a safe state,it is carried out Diagram shows four customers( A,B,C,D) each of them granted a no. of credit units Customers – processes, Units -- tape drives & Banker – Operating system 11
O.S. by Er. K.S.Dhindsa © 2007
II. Banker's Algorithm for Multiple Resources
Example of banker's algorithm with multiple resources 12
O.S. by Er. K.S.Dhindsa © 2007
Deadlock Prevention Restrain the ways request can be made
• Mutual Exclusion – not required for sharable resources; must hold for nonsharable resources • Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources. – Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none. – Low resource utilization; starvation possible. 13
O.S. by Er. K.S.Dhindsa © 2007
Deadlock Prevention (Cont.) • No Preemption – – If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released. – Preempted resources are added to the list of resources for which the process is waiting. – Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting. • Circular Wait – impose a total ordering of all resource types, and require that each process requests resources 14 in an increasing order of enumeration. O.S. by Er. K.S.Dhindsa © 2007
Recovery from Deadlock I.
PROCESS TERMINATION
• Abort all deadlocked processes • Abort one process at a time until the deadlock cycle is eliminated In which order should we choose to abort? – Priority of the process – How long process has computed, and how much longer to completion – Resources the process has used – Resources process needs to complete – How many processes will need to be terminated 15 – Is process interactive or batch?
O.S. by Er. K.S.Dhindsa © 2007
Recovery from Deadlock (contd) II. Resource Preemption • Selecting a victim – minimize cost {Which resources & which processes are to be preempted?} • Rollback – return to some safe state, restart process for that state {Total Rollback also can be done } • Starvation – same process may always be picked as victim {process could be picked as victim only for a finite no. of times} 16
O.S. by Er. K.S.Dhindsa © 2007
Thrashing • If a process does not have “enough” pages, the page-fault rate is very high • Leading to: – low CPU utilization – operating system thinks that it needs to increase the degree of multiprogramming – another process added to the system • Thrashing ≡ a process is busy swapping pages in and out (If it is spending more time paging than executing) 17
O.S. by Er. K.S.Dhindsa © 2007
Thrashing (Cont.)
18
O.S. by Er. K.S.Dhindsa © 2007
Working-Set Model • Works on the assumption of locality ∀ ∆ ≡ working-set window ≡ a fixed number of page references Example: 10,000 instruction • WSSi (working set of Process Pi) = total number of pages referenced in the most recent ∆ (varies in time) – if ∆ too small will not encompass entire locality – if ∆ too large will encompass several localities – if ∆ = ∞ ⇒ will encompass entire program • D = Σ WSSi ≡ total demand frames • • • •
If D > m (no. of available frames) ⇒ Thrashing Policy if D > m, then suspend one of the processes Prevents thrashing while keeping degree of multiprogramming as high as possible Optimizes CPU Utilization
19
O.S. by Er. K.S.Dhindsa © 2007
Working-set model
20
O.S. by Er. K.S.Dhindsa © 2007
DEADLOCKS
Lecture Series By : Website ::
Er. Kanwalvir Singh Dhindsa www.dhindsa.info
http://groups.google.com/group/os-2007 21
O.S. by Er. K.S.Dhindsa © 2007
Related Documents
Deadlocks
November 2019 6
Deadlocks
June 2020 1
Deadlocks
June 2020 1
16 Deadlocks
November 2019 3
Cap09 Deadlocks
June 2020 2