Transcript OperatingSystems-Lecture15

Operating System Concepts and Techniques
Lecture 15
Deadlock and starvation-1
M. Naghibzadeh
Reference
M. Naghibzadeh, Operating System Concepts and Techniques, First ed., iUniverse Inc., 2011.
To order: www.iUniverse.com, www.barnesandnoble.com, or www.amazon.com
Deadlock and Starvation
Deadlock is an standstill situation in which two or more
processes are unable to proceed because of each
process is waiting for something from another process
and a closed wait-for cycle is formed
For example, if two people one has a pencil and the
other one a sheet of paper and each one needs the
other’s resource which will never receive a deadlock
occurs
2
Deadlock conditions
There are three necessary conditions for deadlock to
occur
1.
2.
3.
Mutual exclusion: there are resources in the system for which
mutual exclusion is enforced to prevent race condition
Hold and wait (or partial allocation): A situation in which a
process is holding one or more resources and is also waiting
for one or more other resources that are not available for the
time being
Non-preemptable resources: A resource that cannot be
forcibly taken away from the holder process without imposing
any intolerable harm to the process
One sufficient condition for deadlock
1.
The existence of a wait-for closed cycle, when this happens it
means the three necessary conditions also hold
3
Deadlock modeling
To
graphically
show
deadlock opposite symbols
are used
The following closed waitfor graph shows a deadlock
A process
A resource
A process waiting for a resource
A
CD
drive
scanner
A resource is taken by a process
B
4
Solutions for deadlock problem
There are four policies to attack deadlock
 Ignoring Deadlock
 Deadlock Prevention
 Deadlock Avoidance
 Deadlock Detection and Recovery
Ignoring deadlock (or ostrich algorithm): we are not
actually suggesting a solution, but rather erasing a
problem statement

It does not mean deadlock will not occur
The side effects of such an action could be very harmful

It is not wise to ignore deadlock in sensitive environments

5
Deadlock Prevention
For deadlock prevention, we can arrange that at least
one of the conditions is not satisfied



By not enforcing mutual exclusion, we allow race conditions
to occur; this is not acceptable
Removing the hold-and-wait is possible; do not allow a
process to wait for a new resource while holding other
resources (preemptable resources are exempted)
 Assign all the needed resource of a process at start or not
accept this process
Disadvantages:
 Inefficient use of resources
 Must declare all its needed resources at the start
6
Deadlock Prevention…
Removing the non-preemptability

Not possible, some resources are naturally non-preemptable
Removing the circular-wait

One method is to use resource ordering
 All (non-preemptable) resources are clustered into n ordered
classes
 If a process is given a resource from class i, it can only request
resources from classes of a higher order
 Resources possessed by a process must be returned in a
descending order

Disadvantages:
 Inefficient use of resources but much better than removing hold
and wait
 Must declare all its needed resources at the start
7
Deadlock Prevention…
Semi-Proof of deadlock freeness by showing a two-process case
Example: a Process will need resources 5, 18, 13, 20, 22, 28, 32,
45, during its execution
1- Resource number 13 is requested // OS will allocate resources 5, 8,
and 13
2- Resource number 22 is requested // OS will allocate resources 20
and 22
3- Resource number 22 is released // OS will take back this resource
4- Resource number 45 is requested // OS will allocate resources 22,
28, 32, and 45
5- Resource number 28 is released // OS will not take back this
resource because the process still possesses resources 32 and 45
6- Resources number 32 and 45 are released // OS will take back
resource numbers 45, 32, and 28
7- Resource number 22 is released // OS will take back this resource
8
Deadlock Avoidance
Deadlock avoidance ensures that deadlock will not
occur
Deadline avoidance is based on careful analysis of
every request by examining what will happen in the
future if the requested resource is allocated

The resource is allocated if the system will be safe and will
not be allocated otherwise. If not allocated, the requesting
process withdraws its request and resubmits it at a later time
One of the most respected deadline avoidance
methods is the banker’s algorithm formalized by
Dijkstra
9
Deadlock Avoidance - Banker’s algorithm
Think of a bank branch that has certain amount of
cash capital (resources) and an intelligent manager
Its capital will not increase
The banker grants credit to customers who need a
loan
The total sum of all credits is greater than the bank’s
capital, otherwise the system is safe anyways
Customers may claim all their credit at once or in a
number of installments
The banker is not allowed to forcibly collect the
money from a customer (non-preemptable)
10
Deadlock Avoidance - Banker’s algorithm…
The banker carefully checks every request to make
sure by lending the amount he will not encounter
deadlock
A deadlock will occur when lending a requested
amount leads to a situation in which there is no way
to complete total needs of all customers, no matter
what the future ordering of the requests would be
A safe request is one which will not cause deadlock
An unsafe request will not be granted
11
Banker’s algorithm
1. If the number of requested resources is greater than the
number of available resources the request is not valid;
return from this algorithm; otherwise continue with the next
step
2. Suppose that the required resources are given to the
process (it is not actually given)
3. See if there is a process that can complete its job with the
available resources; if there is one, mark it as completed;
suppose that all of its resources are taken back and are
added to available resources; repeat this step for unmarked
processes until there are no more unmarked processes or
there is no process left that can complete its job with the
available resources
4. If all processes are marked, it is safe to allocate the
requested resources to the process; otherwise declare that
the allocation is unsafe and return
12
Banker’s algorithm
Example:




Suppose the number of simultaneously opened
files is restricted to 128
four processes in the system that need to
simultaneously open, in the worst case, 55, 95, 10,
and 80 files, respectively
Total need is 55+95+10+80=240
Next slide is a scenario of requests
13
Banker’s algorithm-example
1. Process p1 needs to open 20 files
2. Process p3 needs to open 2 files
3. Process p1 needs to open 15 files
4. Process p4 needs to open 25 files
5. Process p3 needs to open 3 files
6. Process p2 needs to open 47 files
7. Process p4 needs to open 7 files
8. Process p3 needs to open 5 files
9. Process p2 needs to open 33 files
10. Process p1 needs to open 20 files
11. Process p4 needs to open 30 files
12. Process p4 needs to open 18 files
13 Process p2 needs to open 15 files
14
Banker’s algorithm-example…
Step no.
Process
Request
Given,
so far
Will need
in the future
0
Available,
overall
Safety
128
Safe
1
P1
20
0
35
128
Safe
2
p3
2
0
8
108
Safe
3
p1
15
20
20
106
Safe
4
p4
25
0
55
91
Safe
5
p3
3
2
5
66
Safe
6
p2
47
0
48
63
Safe
7
p4
7
25
48
16
Unsafe
15
Summary
Controlled
usage of
shared
resources,
by
guaranteeing mutual exclusion to prevent race
condition, causes an important undesirable side
effects called deadlock
There are four different policies for attacking
deadlocks: ignoring deadlock, deadlock prevention,
deadlock avoidance, and deadlock detection and
recovery
The first policy erases the problem statement
altogether
The second and third policy forestall deadlock from
happening, even though the system usually pays a
high price for this
16
Find out
The
exact
difference
between
deadlock
prevention and deadlock avoidance
As many non-preemptable resources as you can
As many preemptable resources as you can
Whether there could be a closed circular wait
which includes main memory when memory
management is virtual memory
There cannot be a deadlock with only one
process
Other policies for preventing deadlock, like waitwound
17
Any questions?
18