Understanding Deadlocks in Operating Systems

 
D
e
a
d
l
o
c
k
s
 
 
W
h
a
t
 
i
s
 
D
e
a
d
l
o
c
k
?
 
Imagine processes P1 and P2.
Imagine resources  R1 and R2.
 
Both processes need both recourses. Process P1 lock resource R1 and
process P2 lock recourse R2. After both finish their job with their
resources, instead of releasing it, they will hold it and look for other
resource.
They will stay in this state and never get out. This state call deadlock.
 
Ali Akbar Mohammadi
 
2
 
R
e
s
o
u
r
c
e
s
 
A resource can be a hardware device (e.g., a tape drive) or a piece of
information (e.g., a locked record in a database).
 
Ali Akbar Mohammadi
 
3
 
F
u
n
g
i
b
l
e
 
R
e
s
o
u
r
c
e
s
 
For some resources, several identical instances may be available, such
as three tape drives. When interchangeable copies of a resource are
available, called 
fungible resources, 
any one of them can be used to
satisfy any request for the resource.
 
Ali Akbar Mohammadi
 
4
 
T
y
p
e
s
 
o
f
 
R
e
s
o
u
r
c
e
s
 
Preemptable resource: 
A preemptable resource is one that can be
taken away from the process owning it with no ill effects.
Nonpreemptable resource: 
Is one that cannot be taken away from its
current owner without causing the computation to fail.
 
In general, deadlocks involve nonpreemptable resources.
 
Ali Akbar Mohammadi
 
5
 
T
h
e
 
S
e
q
u
e
n
c
e
 
o
f
 
E
v
e
n
t
s
 
R
e
q
u
i
r
e
d
 
t
o
 
U
s
e
 
a
 
R
e
s
o
u
r
c
e
 
1. 
Request the resource.
2. 
Use the resource.
3. 
Release the resource.
 
Ali Akbar Mohammadi
 
6
 
P
r
i
n
c
i
p
l
e
s
 
o
f
 
D
e
a
d
l
o
c
k
 
Deadlock can be defined formally as follows:
A set of processes is deadlocked if each process in the set is waiting
for an event that only another process in the set can cause.
 
Ali Akbar Mohammadi
 
7
 
C
o
n
d
i
t
i
o
n
s
 
f
o
r
 
D
e
a
d
l
o
c
k
 
1. 
Mutual exclusion condition. Each resource is either currently
assigned to exactly one process or is available.
2. 
Hold and wait condition. Processes currently holding resources that
were granted earlier can request new resources.
3. 
No preemption condition. Resources previously granted cannot be
forcibly taken away from a process. They must be explicitly released
by the process holding them.
4. 
Circular wait condition. There must be a circular chain of two or
more processes, each of which is waiting for a resource held by the
next member of the chain.
 
Ali Akbar Mohammadi
 
8
 
D
e
a
d
l
o
c
k
 
M
o
d
e
l
i
n
g
 
Ali Akbar Mohammadi
 
9
 
A
n
 
E
x
a
m
p
l
e
o
f
 
h
o
w
D
e
a
d
l
o
c
k
O
c
c
u
r
s
 
Ali Akbar Mohammadi
 
10
 
H
o
w
D
e
a
d
l
o
c
k
C
a
n
 
b
e
A
v
o
i
d
e
d
 
Ali Akbar Mohammadi
 
11
 
S
t
r
a
t
e
g
i
e
s
 
a
r
e
 
U
s
e
d
 
f
o
r
 
D
e
a
l
i
n
g
 
w
i
t
h
 
D
e
a
d
l
o
c
k
s
 
1. 
Just ignore the problem altogether. Maybe if you ignore it, it will
ignore you.
2. 
Detection and recovery. Let deadlocks occur, detect them, and take
action.
3. 
Dynamic avoidance by careful resource allocation.
4. 
Prevention, by structurally negating one of the four conditions
necessary to cause a deadlock.
 
Ali Akbar Mohammadi
 
12
 
T
h
e
 
O
s
t
r
i
c
h
 
A
l
g
o
r
i
t
h
m
 
Stick your head in the sand and pretend there is no problem at all.
 
Ali Akbar Mohammadi
 
13
 
D
e
t
e
c
t
i
o
n
 
a
n
d
 
R
e
c
o
v
e
r
y
 
The system does not do anything except monitor the requests and
releases of resources. Every time a resource is requested or released,
the resource graph is updated, and a check is made to see if any
cycles exist. If a cycle exists, one of the processes in the cycle is killed.
If this does not break the deadlock, another process is killed, and so
on until the cycle is broken.
 
Ali Akbar Mohammadi
 
14
 
D
e
a
d
l
o
c
k
 
P
r
e
v
e
n
t
i
o
n
 
1
 
First let us attack the mutual exclusion condition. If no resource were
ever assigned exclusively to a single process, we would never have
deadlocks.
Example:
Printers
 can have spool and all processes requesting printer, write in spool.
The only process the work with printer’s spool is printer Daemon.
Exception:
Not all recourses can be spooled. If the only available memory will be 64 MB
and 2 process ask for that much, and take half of it, the deadlock will accure.
 
Ali Akbar Mohammadi
 
15
 
D
e
a
d
l
o
c
k
 
P
r
e
v
e
n
t
i
o
n
 
2
 
If we can prevent processes that hold resources from waiting for
more resources, we can eliminate deadlocks.
One way to achieve this goal is to require all processes to request all their
resources before starting execution. If everything is available, the process will
be allocated whatever it needs and can run to completion. If one or more
resources are busy, nothing will be allocated and the process would just wait.
The problem arise cause all processes don’t know which resource
they need beforehand.
 
Ali Akbar Mohammadi
 
16
 
D
e
a
d
l
o
c
k
 
P
r
e
v
e
n
t
i
o
n
 
3
 
If a process has been assigned the printer and is in the middle of
printing its output, forcibly taking away the printer because a needed
plotter is not available is tricky at best and impossible at worst.
 
Ali Akbar Mohammadi
 
17
 
D
e
a
d
l
o
c
k
 
P
r
e
v
e
n
t
i
o
n
 
4
 
The circular wait can be eliminated in several ways. One way is simply
to have a rule saying that a process is entitled only to a single
resource at any moment. If it needs a second one, it must release the
first one. For a process that needs to copy a huge file from a tape to a
printer, this restriction is unacceptable.
Another way to avoid the circular wait is to provide a global
numbering of all the resources.
 
Ali Akbar Mohammadi
 
18
 
(
a
)
 
N
u
m
e
r
i
c
a
l
l
y
 
O
r
d
e
r
e
d
 
R
e
s
o
u
r
c
e
s
(
b
)
 
A
 
R
e
s
o
u
r
c
e
 
G
r
a
p
h
 
Ali Akbar Mohammadi
 
19
 
S
u
m
m
a
r
y
 
o
f
 
A
p
p
r
o
a
c
h
e
s
 
t
o
 
D
e
a
d
l
o
c
k
 
P
r
e
v
e
n
t
i
o
n
 
Ali Akbar Mohammadi
 
20
 
D
e
a
d
l
o
c
k
 
A
v
o
i
d
a
n
c
e
 
The Banker's Algorithm for a Single Resource
Resource Trajectories
 
Ali Akbar Mohammadi
 
21
 
T
h
e
 
B
a
n
k
e
r
'
s
 
A
l
g
o
r
i
t
h
m
 
f
o
r
 
a
 
S
i
n
g
l
e
 
R
e
s
o
u
r
c
e
 
It is modeled on the way a small-town banker might deal with a group
of customers to whom he has granted lines of credit. The banker does
not necessarily have enough cash on hand to lend every customer the
full amount of each one's line of credit at the same time.
 
Ali Akbar Mohammadi
 
22
 
T
h
r
e
e
 
R
e
s
o
u
r
c
e
 
A
l
l
o
c
a
t
i
o
n
 
S
t
a
t
e
s
:
(
a
)
 
S
a
f
e
.
 
(
b
)
 
S
a
f
e
.
 
(
c
)
 
U
n
s
a
f
e
.
 
Ali Akbar Mohammadi
 
23
 
T
h
e
 
B
a
n
k
e
r
'
s
 
A
l
g
o
r
i
t
h
m
 
f
o
r
 
a
 
S
i
n
g
l
e
 
R
e
s
o
u
r
c
e
 
The banker's algorithm considers each request as it occurs, and sees if
granting it leads to a safe state. If it does, the request is granted;
otherwise, it is postponed until later.
To see if a state is safe, the banker checks to see if he has enough
resources to satisfy some customer. If so, those loans are assumed to
be repaid, and the customer now closest to the limit is checked, and
so on. If all loans can eventually be repaid, the state is safe and the
initial request can be granted.
 
Ali Akbar Mohammadi
 
24
 
R
e
s
o
u
r
c
e
 
T
r
a
j
e
c
t
o
r
i
e
s
 
Ali Akbar Mohammadi
 
25
Slide Note
Embed
Share

Deadlocks in operating systems occur when processes hold resources and wait for others, leading to a state where none can progress. Processes may hold resources while requesting more, resulting in a standstill known as a deadlock. This deadlock arises from conditions like mutual exclusion, hold and wait, and no preemption. Understanding the types of resources, sequence of events, and principles of deadlock is essential in managing and preventing such situations.


Uploaded on Jul 22, 2024 | 1 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Deadlocks Deadlocks

  2. What is Deadlock? What is Deadlock? Imagine processes P1 and P2. Imagine resources R1 and R2. Both processes need both recourses. Process P1 lock resource R1 and process P2 lock recourse R2. After both finish their job with their resources, instead of releasing it, they will hold it and look for other resource. They will stay in this state and never get out. This state call deadlock. Ali Akbar Mohammadi 2

  3. Resources Resources A resource can be a hardware device (e.g., a tape drive) or a piece of information (e.g., a locked record in a database). Ali Akbar Mohammadi 3

  4. Fungible Resources Fungible Resources For some resources, several identical instances may be available, such as three tape drives. When interchangeable copies of a resource are available, called fungible resources, any one of them can be used to satisfy any request for the resource. Ali Akbar Mohammadi 4

  5. Types of Resources Types of Resources Preemptable resource: A preemptable resource is one that can be taken away from the process owning it with no ill effects. Nonpreemptable resource: Is one that cannot be taken away from its current owner without causing the computation to fail. In general, deadlocks involve nonpreemptable resources. Ali Akbar Mohammadi 5

  6. The Sequence of Events Required to Use a Resource The Sequence of Events Required to Use a Resource 1. Request the resource. 2. Use the resource. 3. Release the resource. Ali Akbar Mohammadi 6

  7. Principles of Deadlock Principles of Deadlock Deadlock can be defined formally as follows: A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause. Ali Akbar Mohammadi 7

  8. Conditions for Deadlock Conditions for Deadlock 1. Mutual exclusion condition. Each resource is either currently assigned to exactly one process or is available. 2. Hold and wait condition. Processes currently holding resources that were granted earlier can request new resources. 3. No preemption condition. Resources previously granted cannot be forcibly taken away from a process. They must be explicitly released by the process holding them. 4. Circular wait condition. There must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain. Ali Akbar Mohammadi 8

  9. Deadlock Modeling Deadlock Modeling Ali Akbar Mohammadi 9

  10. An Example An Example of how of how Deadlock Deadlock Occurs Occurs Ali Akbar Mohammadi 10

  11. How How Deadlock Deadlock Can be Can be Avoided Avoided Ali Akbar Mohammadi 11

  12. Strategies are Used for Dealing with Deadlocks Strategies are Used for Dealing with Deadlocks 1. Just ignore the problem altogether. Maybe if you ignore it, it will ignore you. 2. Detection and recovery. Let deadlocks occur, detect them, and take action. 3. Dynamic avoidance by careful resource allocation. 4. Prevention, by structurally negating one of the four conditions necessary to cause a deadlock. Ali Akbar Mohammadi 12

  13. The Ostrich Algorithm The Ostrich Algorithm Stick your head in the sand and pretend there is no problem at all. Ali Akbar Mohammadi 13

  14. Detection and Recovery Detection and Recovery The system does not do anything except monitor the requests and releases of resources. Every time a resource is requested or released, the resource graph is updated, and a check is made to see if any cycles exist. If a cycle exists, one of the processes in the cycle is killed. If this does not break the deadlock, another process is killed, and so on until the cycle is broken. Ali Akbar Mohammadi 14

  15. Deadlock Prevention 1 Deadlock Prevention 1 First let us attack the mutual exclusion condition. If no resource were ever assigned exclusively to a single process, we would never have deadlocks. Example: Printers can have spool and all processes requesting printer, write in spool. The only process the work with printer s spool is printer Daemon. Exception: Not all recourses can be spooled. If the only available memory will be 64 MB and 2 process ask for that much, and take half of it, the deadlock will accure. Ali Akbar Mohammadi 15

  16. Deadlock Prevention 2 Deadlock Prevention 2 If we can prevent processes that hold resources from waiting for more resources, we can eliminate deadlocks. One way to achieve this goal is to require all processes to request all their resources before starting execution. If everything is available, the process will be allocated whatever it needs and can run to completion. If one or more resources are busy, nothing will be allocated and the process would just wait. The problem arise cause all processes don t know which resource they need beforehand. Ali Akbar Mohammadi 16

  17. Deadlock Prevention 3 Deadlock Prevention 3 If a process has been assigned the printer and is in the middle of printing its output, forcibly taking away the printer because a needed plotter is not available is tricky at best and impossible at worst. Ali Akbar Mohammadi 17

  18. Deadlock Prevention 4 Deadlock Prevention 4 The circular wait can be eliminated in several ways. One way is simply to have a rule saying that a process is entitled only to a single resource at any moment. If it needs a second one, it must release the first one. For a process that needs to copy a huge file from a tape to a printer, this restriction is unacceptable. Another way to avoid the circular wait is to provide a global numbering of all the resources. Ali Akbar Mohammadi 18

  19. (a) Numerically Ordered Resources (a) Numerically Ordered Resources (b) A Resource Graph (b) A Resource Graph Ali Akbar Mohammadi 19

  20. Summary of Approaches to Deadlock Prevention Summary of Approaches to Deadlock Prevention Condition Mutual exclusion Hold and wait No preemption Circular wait Approach Spool everything Request all resources initially Take resources away Order resources numerically Ali Akbar Mohammadi 20

  21. Deadlock Avoidance Deadlock Avoidance The Banker's Algorithm for a Single Resource Resource Trajectories Ali Akbar Mohammadi 21

  22. The Banker's Algorithm for a Single Resource The Banker's Algorithm for a Single Resource It is modeled on the way a small-town banker might deal with a group of customers to whom he has granted lines of credit. The banker does not necessarily have enough cash on hand to lend every customer the full amount of each one's line of credit at the same time. Ali Akbar Mohammadi 22

  23. Three Resource Allocation States: Three Resource Allocation States: (a) Safe. (b) Safe. (c) Unsafe. (a) Safe. (b) Safe. (c) Unsafe. Ali Akbar Mohammadi 23

  24. The Banker's Algorithm for a Single Resource The Banker's Algorithm for a Single Resource The banker's algorithm considers each request as it occurs, and sees if granting it leads to a safe state. If it does, the request is granted; otherwise, it is postponed until later. To see if a state is safe, the banker checks to see if he has enough resources to satisfy some customer. If so, those loans are assumed to be repaid, and the customer now closest to the limit is checked, and so on. If all loans can eventually be repaid, the state is safe and the initial request can be granted. Ali Akbar Mohammadi 24

  25. Resource Trajectories Resource Trajectories Ali Akbar Mohammadi 25

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#