Transcript Chapter6

Announcements
• The fixing the bug part of Lab 4’s
assignment 2 is now considered extra
credit.
• Comments for the code should be on the
parts you wrote for the assignment.
1
Concurrency: Deadlock and
Starvation
Chapter 6
2
3
Deadlock
• Permanent blocking of a set of processes
that either compete for system resources
or communicate with each other
• No efficient solution
• Involve conflicting needs for resources
by two or more processes
4
Deadlock Example
P1
.
Get A
.
Get B
.
Release A
Release B
P2
.
Get B
.
Get A
.
Release B
Release A
5
6
Deadlock Example
P1
.
Get A
.
Release A
.
Get B
Release B
P2
.
Get B
.
Get A
.
Release B
Release A
7
8
Deadlock Environment
• Mutual exclusion
– Only one process may use a resource at a
time
• Hold-and-wait
– A process may hold allocated resources
while awaiting assignment of others
• No preemption
– No resource can be forcibly removed form a
process holding it
9
Condition for Deadlock
• Circular wait
– A closed chain of processes exists, such that each
process holds at least one resource needed by the
next process in the chain
10
Deadlock Prevention
• Mutual Exclusion
– Must be supported by the operating system
• Hold and Wait
– Require a process request all of its required
resources at one time
11
Deadlock Prevention
• No Preemption
– Process must release resource and request
again
– Operating system may preempt a process to
require it releases its resources
• Circular Wait
– Define a linear ordering of resource types
12
Deadlock Avoidance
• A decision is made dynamically whether
the current resource allocation request
will, if granted, potentially lead to a
deadlock
• Requires knowledge of future process
request
13
Two Approaches to
Deadlock Avoidance
• Do not start a process if its demands
might lead to deadlock
• Do not grant an incremental resource
request to a process if this allocation
might lead to deadlock
14
Determination of a Safe State
Initial State
15
Determination of a Safe State
P2 Runs to Completion
16
Determination of a Safe State
P1 Runs to Completion
17
Determination of a Safe State
P3 Runs to Completion
18
Resource Allocation Denial
• Referred to as the banker’s algorithm
• State of the system is the current
allocation of resources to process
• Safe state is where there is at least one
sequence that does not result in deadlock
• Unsafe state is a state that will lead to
deadlock if no resources released and
rest requested.
19
Reusable Resources
• Used by only one process at a time and not
depleted by that use
• Processes obtain resources that they later
release for reuse by other processes
• Processors, I/O channels, main and secondary
memory, devices, and data structures such as
files, databases, and semaphores
• Deadlock occurs if each process holds one
resource and requests the other
20
Consumable Resources
• Created (produced) and destroyed
(consumed)
• Interrupts, signals, messages, and
information in I/O buffers
• Deadlock may occur if a Receive
message is blocking
• May take a rare combination of events to
cause deadlock
21
Example of Reusable
Deadlock
• Deadlock occurs if receive is blocking
P1
...
P2
...
Receive(P2);
...
Receive(P1);
...
Send(P2, M1);
Send(P1, M2);
22
Deadlock Avoidance
Summary
• Maximum resource requirement must be
stated in advance
• Processes under consideration must be
independent; no synchronization
requirements
• There must be a fixed number of
resources to allocate
• No process may exit while holding
resources
23
Sites on Deadlock
• http://access1.sun.com/techarticles/CAT/deadlock.html
• http://www.javaspecialists.co.za/archive/Issue093.html
• http://news.zdnet.com/2100-9595_22-982905.html
24
Deadlock Detection
25
Strategies once Deadlock
Detected
• Abort all deadlocked processes
• Back up each deadlocked process to
some previously defined checkpoint, and
restart all process
– Original deadlock may occur
• Successively abort deadlocked processes
until deadlock no longer exists
• Successively preempt resources until
deadlock no longer exists
26
Selection Criteria Deadlocked
Processes
• Least amount of processor time
consumed so far
• Least number of lines of output
produced so far
• Most estimated time remaining
• Least total resources allocated so far
• Lowest priority
27
Strengths and Weaknesses of the
Strategies
28
Real World Solutions
• Integrated Deadlock Strategy
– Group resources into different classes and
enforce a linear ordering strategy.
• Prevention (avoiding circular waits)
• Within classes can still have multiple access.
29
Example Classes
• Swappable space : Virtual Memory
– Must make all requests at the same time.
(Avoiding the Hold-and-Wait problem)
• Process Resources : Assignable devices
(ex: tape drives and files)
– Know ahead of time (avoidance)
– Linear ordering (circular wait nullified)
• Main Memory :
– Preemption -> swap out to virtual memory
30
Example Classes
• Internal Resources : I/O channels
– Resource ordering.
31
Dining Philosophers Problem
32
Dining Philosophers Problem
33
Dining Philosophers Problem
34
Dining Philosophers Problem
35
Dining Philosophers Problem
36
Deadlock in OS
• Most Operating Systems assume deadlock
won’t occur.
– Within the kernel processes.
• Make all kernel level resource allocations
deadlock free.
– Get all.
– Preemption.
– Linear ordering.
• Side Note: Interrupts can play havok in OS
design.
• How does the kernel determine what is a
resource to be concerned about?
37
UNIX Concurrency
Mechanisms
• Shared memory
– Block of memory that both processes have access
to. Similar to a pipe, with fewer built in controls.
• Pipes
– Sending messages but a fixed byte size to store the
message.
• Messages (msgsnd and msgrcv)
– Able to store messages in a queue.
– Blocks on send when queue full and on a read
when queue empty.
38
UNIX Concurrency
Mechanisms
• Semaphores (semWait and semSignal)
– Can be managed in sets
• semctl : Used to initialize all semaphores in the set to the
same value at the same time.
• sem_op : Pass in a set of individual operations to be
performed in order.
• Signals
– Very similar to an interrupt, but all signals have the
same priority level.
– Type determines what happens when received.
• SIGKILL : Kill the process
• SIGCHLD : Inform process on the death of a child
39
Linux Kernel Concurrency
Mechanisms
• Has a set of atomic operations. (atomic_t)
– Operations execute without interruption and
without interference.
– atomic_dec_and_test : Subtract a 1 from the
variable and return 1 if equals 0.
– atomic_int_and_test : Add a 1 to the variable and
return 1 if equals 0.
– atomic_read : Gets the value of the atomic
variable.
– atomic_set : Sets the value of the atomic variable to
the specified value.
40
Linux Kernel Concurrency
Mechanisms
• Spinlocks
– Very similar to semaphores but designed for shorts
waits.
– Doesn’t put the thread to sleep while waiting for
the spinlock to release.
– Can be done with interrupts enabled or disabled.
• Semaphores
– Puts the thread to sleep if semaphore unavailable.
– Can be done with interrupts enabled or disable.
41
Linux Kernel Concurrency
Mechanisms
Used when code is reordered to optimize processor
efficiency.
a = 1;
b = 1;
42
Solaris Thread
Synchronization Primitives
• Mutual exclusion (mutex) locks
– Basically a binary semaphore.
• Semaphores
– Basic counting semaphore.
• Condition variables
– Allows a thread to wait until a specific
condition occurs.
– Used with a mutex lock.
43
Condition Example
mutex_enter(&m)
while (some_condition) {
cv_wait(&cv,&m);
}
mutex_exit(&m)
44
45
Extra Slides
46
Example of Deadlock
47
Another Example of Deadlock
• Space is available for allocation of
200Kbytes, and the following sequence
of events occur
P1
P2
...
...
Request 80 Kbytes;
Request 70 Kbytes;
Request 60 Kbytes;
Request 80 Kbytes;
...
...
• Deadlock occurs if both processes
progress to their second request
48
49
Possibility of Deadlock
• Mutual Exclusion
• No preemption
• Hold and wait
50
Existence of Deadlock
•
•
•
•
Mutual Exclusion
No preemption
Hold and wait
Circular wait
51
Determination of an
Unsafe State
52
Determination of an
Unsafe State
53
Resource Allocation Graphs
• Directed graph that depicts a state of the
system of resources and processes
54
Resource Allocation Graphs
55
Banker’s Algorithm
56
Banker’s Algorithm
57
58
Linux Atomic Operations
59
Linux Atomic Operations
60
Linux Kernel Concurrency
Mechanisms
• Spinlocks
– Used for protecting a critical section
61
62
63