Slide 1
Operating Systems
Hubertus Franke
.edu
CSCI-GA.2250-001
Concurrency
&&
Deadlocks
For illustration
purpose only
Potential Deadlock
I need quad
A and B
I need quad
B and C
I need quad
C and D
I need quad
D and A
Actual Deadlock
HALT until B
is free
HALT until C
is free
HALT until D
is free
HALT until A
is free
Inter Process Communication (IPC)
• Processes often need to work
together or at the very least share
resources.
Issues:
• Send information
• Mitigate contentions over resources
• Synchronize dependencies
Inter-Process Communication
Race Conditions:
result depends on exact order of processes running
Two processes want to access shared memory at same time:
Read is typically not an issue but write or conditional execution IS
Process will first inquire
about free slot (read), then
write to the free slot and
finally increment the free
slot index.
Intra Process Communication
• Threads often need to work together and
access resources (e.g. memory) in the
common address space.
Same Issues:
• Send information
• Mitigate contentions over resources
• Synchronize dependencies
Example: Multi-threaded Webserver
• Dispatcher thread deposits work into
queue of requests to be processed
• Worker threads will pick work from the
queue
• Read-Modify-Write cycles are typically an issue
• For instance, you read a variable , make a decision and
modify the variable.
• Examples:
• These will have problems if the same code is executed by
two threads concurrently.
• Consider the race and preemption case with 2 threads
Expectation is that code has “consistent view” at data
Read-Modify-Write Cycles
If ( var == 0 ) {
/*do something */
var = 1;
}
ldw r3, @var
cmpwi r3, 0
bne L1
stwi @var, 1
/* some code */
L1:
If ( var == 0 ) {
var = 1;
/*do something */
}
read modify-write race or preemption
Critical Regions
Four conditions to prevent errors:
1. No two processes simultaneously in critical region
2. No assumptions made about speeds or numbers of CPUs
3. No process running outside its critical region may block
another process
4. No process must wait forever to enter its critical region
Mutual Exclusion: Only one process (thread)
at a time can access any shared variables,
memory, or resources.
Critical Regions
Mutual exclusion using critical regions
Mutual Exclusion with Busy Waiting
Simplest solution?
• How about disabling interrupt?
• User program has too much privilege.
• Won’t work in SMP (multi-core systems)
Lock variable?
• If the value of the lock variable is 0 then
process sets it to “1” and enters. Other
processes have to wait.
• What’s the problem here?
–> READ-MODIFY-WRITE cycle
• Using a simple Lock Variable
• Both Threads assume now they hold the lock
Read-Modify-Write Cycles
During Locks
L1: ldw r3, @var
cmpwi r3, 0
bnz L1
stwi @var, 1
/* lock acquired */
var=0
var=1
L1: ldw r3, @var
cmpwi r3, 0
bnz L1
stwi @var, 1
/* some code */
L1:
r3 still sees “0”
Thread-1 Thread-2
Context-switch
Mutual Exclusion with Busy Waiting
Process 0 Process 1
Proposed solution to critical region problem
But that’s just a toy and in reality not useful
Peterson’s solution for achieving mutual exclusion
Mutual Exclusion with Busy Waiting
Figure 2-25. Entering and leaving a critical region
using the TSL instruction.
The TSL (Test and Set Lock) Instruction
• With a “little help” from Hardware
Figure 2-26. Entering and leaving a critical region
using the XCHG instruction.
The XCHG Instruction
(other arch have cmp_and_swap)
Load/Store Conditional
• Modern processors resolve cmp_and_swap through the
cache coherency and instructions
• Reservation (ldwx) remembers ONE address on a CPU
and verifies on (stwx) whether still held otherwise
store will fail
• Reservation is lost on interrupts or if another CPU
steals cacheline holding
first lecture on cache coherency) or if another lwdx is
issued.
L1: ldwx r3, @lockvar // load r3 and set reservation register on CPU with &lockvar
add r3,r3,1 // r3 = r3+1
stwx r3, @lockvar // store conditionally r3 back to lockvar if reservation is still held
bcond L1 // if store conditionally failed try again
l
Solutions so far
• Both TSL (xchg/cmpswp) and
Peterson’s solutions are correct, but
they
– rely on busy-waiting during “contention”
– waste CPU cycles
– Priority Inversion problem
Priority Inversion Problem
• Higher priority process can be
prevented from entering a critical
section (CS) because the lock variable is
dependent on a lower priority process.
– Priority P1 < Priority P2
– P1 is in its CS but P1 is never scheduled.
Since P2 is busy in busy-waiting using the
CPU cycles
Lock Contention
• Lock Contention arises when a process/thread attempts to
acquire a lock and the lock is not available.
• This is a function of
– frequency of attempts to acquire the lock
– Lock hold time (time between acquisition and release)
– Number of threads/processes acquiring a lock
• Lock contention is a function of lock hold time and lock
acquisition frequency.
• If lock contention is low, TSL is an OK solution.
• The linux kernel uses it extensively for many locking
scenarios.
• Alternative approaches will be discussed next.
Concurrency
• Reminder
– Concurrency is having multiple contexts of
execution not necessarily running at the
exact same time.
– Parallelism is having multiple contexts of
execution running at the exact same time.
Producer-Consumer problem
Buffer with N slots
• Producer: (1 .. j)
– How do I know a slot is free ?
– How do I know a slot became free ?
• Consumer: (1 .. k)
– How do I know nothing is available?
– How do I know something became available ?
P1
PJ
:
C1
CK
:buffer
How can mutual exclusion solutions be used in
every day OSs?
• Example:
– UNIX: ls –ls | grep “yooh” | awk ‘{ print $1 }’
/usr/bin/ls -ls /usr/bin/grep “yooh” /usr/bin/awk ‘print $1’
Process-1 Process-2 Process-3
Pipe #1 Pipe #2
Kernel
Kernel-Obj Kernel-Obj
Terminal Output
• Responsibility of a Pipe
– Provide Buffer to store data from stdout of Producer and release it to stdin of Consumer
– Block Producer when the buffer is full (because consumer has not consumed data)
– Block Consumer if no data in buffer when the consumer wants to read(stdin)
– Unblock Producer when buffer space becomes free
– Unblock Consumer when buffer data becomes available
Pipes
• Pipes not just for stdin and stdout
• Pipes can be created by applications
• All kind of usages for pipes.
• PipeBuffer typically has
16 write slots
• 4KB guaranteed to be atomic
• ➔ 64KB
Not sure why the book put a while loop here,
we just assume that these function
produce/consume one elem
Pre-emption!!!
Count == 0
Called after pre-emption
but before sleep in the
consumer
Fatal Race Condition
1. Let count = 1
2. Consumer begins loop, decrements count == 0
3. Consumer returns to loop beginning and executes:
if(count == 0), then
pre-emption happens.
4. Producer gets to run, executes
count = count + 1;
if(count == 1) and calls wakeup(consumer)
5.Pre-emption Consumer calls sleep(consumer)
Requirements
• Need a mechanism that allows
synchronization between
processes/threads on the base of
shared resource.
• Synchronization implies interaction with
scheduling sub-system.
• Led to the innovation of semaphores.
Semaphore Data Structure
class Semaphore
{
int value; // counter
Queue
// waiting on this sema
void Init(int v); // initialization
void P(); // down(), wait()
void V(); // up(), signal ()
}
Initially developed as a “construct” to ease programming.
Dijkstra 1965
This version is based on multi-threaded capable OS or thread library
Older version used Process as the object , same principle
Semaphore implementations
void Semaphore::Init(int v)
{
value = v;
Queue
}
Semaphore implementations
void Semaphore::P() // or wait() or down()
{
value = value – 1;
if (value < 0)
{
waiting.add(current_thread);
current_thread.status = blocked;
schedule(); // forces wait, thread blocked
}
}
AKA “acquiring or grabbing the semaphore”
think of it as obtaining access rights
Semaphore implementations
void Semaphore::V() // or signal() or up()
{
value = value + 1;
if (value <= 0)
{
Thread *thd = waiting.getNextThread();
scheduler->add(thd); // make it scheduable
}
}
AKA “releasing the semaphore”
Semaphore Solution
How do P() and V() avoid the race condition?
P() and V() must be atomic.
e.g.
• First line of P() & V() can disable interrupts.
• Last line of P() & V() re-enables interrupts.
However: disabling interrupts only works on single CPU systems
Atomic lock variable an option on entry and exit,
but must release the lock as part of call to schedule() in P()
or must reacquire the lock as part of call to schedule() in V()
Semaphore Data Structure
(with atomicity)
class Semaphore
{
int lockvar; // to guarantee atomicity
int value; // counter
Queue
// waiting on this sema
void Init(int v); // initialization
void P(); // down(), wait()
void V(); // up(), signal ()
}
Semaphore implementations
void Semaphore::P() // or wait() or down()
{
lock(&lockvar);
value = value – 1;
if (value < 0)
{
waiting.add(current_thread);
current_thread.status = blocked;
unlock(&lockvar);
schedule(); // forces wait, thread blocked
lock(&lockvar);
}
}
Semaphore implementations
void Semaphore::V() // or signal() or up()
{
lock(&lockvar);
value = value + 1;
if (value <= 0)
{
Thread *thd = waiting.getNextThread();
scheduler->add(thd); // make it scheduable
}
unlock(&lockvar);
}
Two kinds of semaphores
• Mutex semaphores
(or binary semaphores or LOCK):
for mutual exclusion problems:
value initialized to 1
• Counting semaphores:
for synchronization problems.
Value initialized to any value 0..N
Value shows available tokens to enter
or number or processes waiting when
negative.
Semaphore Solution To the Producer
Consumer Problem
Producer(T item)
{
P(&empty);
P(&mutex); // Lock
buffer[widx] = item;
widx = (widx + 1 ) % N;
V(&mutex); // Unlock
V(&full);
}
Consumer(T &item)
{
P(&full);
P(&mutex); // Lock
item = buffer[ridx];
ridx = (ridx + 1 ) % N;
V(&mutex); // Unlock
V(&empty);
}
#define N
Semaphore empty = N;
Semaphore full = 0; 3 Semaphores required
Semaphore mutex = 1;
T buffer[N];
int widx = 0, ridx = 0;
LOCK
signaling
Semaphore Solution To the Producer
Consumer Problem
Producer(T item)
{
P(&empty);
P(&mutex_w); // Lock
buffer[widx] = item;
widx = (widx + 1 ) % N;
V(&mutex_w); // Unlock
V(&full);
}
Consumer(T &item)
{
P(&full);
P(&mutex_r); // Lock
item = buffer[ridx];
ridx = (ridx + 1 ) % N;
V(&mutex_r); // Unlock
V(&empty);
}
#define N
Semaphore empty = N;
Semaphore full = 0; 4 Semaphores for lower
Semaphore mutex_w = 1; lock contention
Semaphore mutex_r = 1;
T buffer[N];
int widx = 0, ridx = 0;
LOCK
signaling
Semaphore Solution To the Producer
Consumer Problem
Producer(T item)
{
P(&empty);
P(&mutex_w); // Lock
int wi = wdix;
widx = (widx + 1 ) % N;
V(&mutex_w); // Unlock
buffer[wi] = item;
V(&full);
}
Consumer(T &item)
{
P(&full);
P(&mutex_r); // Lock
int ri = rdix;
ridx = (ridx + 1 ) % N;
V(&mutex_r); // Unlock
item = buffer[ri];
V(&empty);
}
#define N
Semaphore empty = N;
Semaphore full = 0; 4 Semaphores for lower
Semaphore mutex_w = 1; lock contention
Semaphore mutex_r = 1;
T buffer[N];
int widx = 0, ridx = 0;
LOCK
signaling
Shorter lock hold times by only protecting the indices not the buffer themselves
Nasty condition on wi
This example doesn’t work; too aggressive !!!!!
Figure 2-29. Implementation of mutex lock and mutex unlock.
Mutex Implementation
Figure 2-30. Some of the Pthreads calls relating to mutexes.
Mutexes in Pthreads
Figure 2-31. Some of the Pthreads calls relating
to condition variables.
Mutexes in Pthreads
Using threads to solve
the producer-consumer
problem.
Mutexes in Pthreads
Problems with semaphore?
– It can be difficult to write semaphore code
(arguably)
– One has to be careful in code construction
– If a thread dies and it holds a semaphore,
the implicit token is lost
Deadlock-free code Code with potential deadlock
Some Advice for locks
• Always acquire multiple locks in the same
order
• Preferably release in reverse order as
acquired: not required but good hygiene
lots of discussion on this, there are scenarios where
that is not desired but highly optimized
implementation
• Example: SMP CPU scheduler
where load balancing is required.
Example
doit()
{
s1.P();
{
s2.P();
“do something awesome”
s2.V();
}
s1.V();
}
doit()
{
s1.P();
s2.P();
“do something awesome”
s1.V();
s2.V();
}
doit()
{
s1.P();
s2.P();
“do something awesome”
s2.V();
s1.V();
}
OK Better Making nesting clearer
Example
doit()
{
s1.P();
do {
s2.P();
do {
“do something awesome”
break;
“do something else awesome”
} while(0);
s2.V();
} while (0);
s1.V();
} Making nesting clearer
Example: SMP Scheduler
• Each cpu_i has ( runQ[i] and rqLock[i] )
• cpu0 ( i=0, j=1 ) ; cpu1 ( i=1, j=0 )
• Can lead to deadlocks → must use same order
CPU-0
runQ[0]
rqLock[0]
CPU-1
runQ[1]
rqLock[1]
Schedule(int i)
{
lock(rqlock[i]);
:
{ // load balance with j
lock(rqlock[j]);
; // pull some threads
unlock(rqlock[j]);
}
:
unlock(rqlock[i]);
}
Example SMP Scheduler
• So how do we get correct order?
• We force it !!
if necessary release owned lock first and reaquire.
• We just need some order ( could be “<“ or based on addresses, it doesn’t matter ) Schedule(int i) { lock(rqlock[i]); : { // load balance with j add_lock(i,j); ; // pull some threads unlock(rqlock[j]); } : unlock(rqlock[i]); } add_lock(int hlv, int alv) { if ( hlv > alv ) {
// first unlock hlv
unlock(rqlock[hlv]);
lock(rqlock[alv];
lock(rqlock[hlv];
} else {
lock(rqlock[alv]);
}
}
So which lock should I use
• Busy Lock vs. Semaphores ?
• If lock hold time is short and/or code is
uninterruptible, lock variables and busy
waiting are OK ( linux kernel uses it all
the time )
• Else use semaphores
Other Unix/Linux Mechanisms
• File based:
flock()
• System V semaphores
heavy weight as each call is a system call going into the kernel
semget(), semop() [ P and V ]
• Futexes
Lighter weight as uncontested cases are resolved done using cmpxchg
in userspace and if race condition is recognized it goes to kernel
futex()
• Message queues
mq_open(),mq_close(),mq_send(), mq_receive()
Monitors
⚫ Hoare and Brinch Hansen proposed a higher-level synchronization
primitive: monitor
⚫ Only ONE thread allowed inside the Monitor
⚫ Compiler achieves Mutual Exclusion
⚫ Monitor is a programming language construct like a
class or a for-loop.
⚫ We still need a way to synchronize on events!
⚫ Condition variables: wait & signal
⚫ Not counters: signaling with no one waiting → event lost
⚫ Waiting on signal releases the monitor and wakeup reacquires it.
Figure 2-33. A monitor.
Monitor Example
Monitors
• What to do when a thread A in a
monitor signals a thread B sleeping on a
condition variable?
– Ensure that signal is the last command in the
monitor?
– Block A while B runs?
– Let A finish then run B?
Figure 2-34. An outline of the producer-consumer problem with
monitors.
Monitors
Figure 2-36. The producer-consumer problem with N messages.
Producer-Consumer Problem
with Message Passing
. . .
Figure 2-36. The producer-consumer problem with N messages.
Producer-Consumer Problem
with Message Passing
Message Passing
▪ No shared memory on distributed
systems…
▪Instead we can send LAN messages.
send(destination, &message);
receive(destination, &message);
Message Passing Issues
• Guard against lost messages (acknowledgement)
• Authentication (guard against imposters)
• Addressing :
• To processes
• Via Mailbox (place to buffer messages)
• Send to a full mailbox means block
• Receive from an empty mailbox means block
Message Passing Issues
• What about buffer-less messages?
• Send and Receive wait (block) for each
other to be ready to talk: rendezvous
Figure 2-37. Use of a barrier. (a) Processes approaching a barrier. (b) All
processes but one blocked at the barrier. (c) When the last process
arrives at the barrier, all of them are let through.
Barriers
Deadlock vs Starvation
• Deadlock – Process(es) waiting on events
(resources) that will never happen:
• Can be system wide or just one process
[ will define this more precisely later ]
• Starvation – Process(es) waiting for its
turn but never comes:
• Process could move forward, the resource or
event might be come available but this process
does not get access.
• Printing policy prints smallest file available. 1
process shows up with HUGE file, will not get to
run if steady stream of files.
Deadlocks
Occur among processes who need to
acquire resources in order to progress
Resources
• Anything that must be acquired, used, and
released over the course of time.
• Hardware or software resources
• Preemptable and Nonpreemptable resources:
– Preemptable: can be taken away from the
process with no ill-effect
– Nonpreemptable: cannot be taken away from the
process without causing the computation to fail
Reusable
• can be safely used by only one process
at a time and is not depleted by that
use
• processors, I/O channels, main and
secondary memory, devices, and
data structures such as files,
databases, and semaphores
Consumable
• one that can be created
produced) and destroyed
(consumed)
• interrupts, signals,
messages, and information
• in I/O buffers
Resource Categories
So …
• 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.
• Assumptions
– If a process is denied a resource, it is put to sleep
– Only single-threaded processes
– No interrupts possible to wake up a blocked process
Conditions for Resource Deadlocks
1. Each resource is either currently assigned to
exactly one process or is available.
2. Processes currently holding resources that were
granted earlier can request new resources.
3. Resources previously granted cannot be forcibly
taken away from a process. They must be explicitly
released by the process holding them.
4. 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.
Resource Allocation Graph
Process
Resource
Process A is holding resource R
Resource Allocation Graph
Process B is requesting resource S
Resource Allocation Graph
Deadlock!
How to Deal with Deadlocks
1. Just ignore the problem !
2. Let deadlocks occur, detect them, and
take action
3. Dynamic avoidance by careful resource
allocation
4. Prevention, by structurally negating
one of the four required conditions.
The Ostrich Algorithm
However: remember Murphy’s law !!!
What can go wrong, will ……
Deadlock Detection and Recovery
• The system does not attempt to prevent
deadlocks.
• It tries to detect it when it happens.
• Then it takes some actions to recover
• Several issues here:
– Deadlock detection with one resource of each
type
– Deadlock detection with multiple resources of
each type
– Recovery from deadlock
Deadlock Detection:
One Resource of Each Type
• Construct a resource graph
• If it contains one or more cycles, a
deadlock exists
Formal Algorithm to Detect
Cycles in the Allocation Graph
For Each node N in the graph do:
1. Initialize L to empty list and designate all arcs as
unmarked
2. Add the current node to end of L. If the node appears
in L twice then we have a cycle and the algorithm
terminates
3. From the given node pick any unmarked outgoing arc.
If none is available go to 5.
4. Pick an outgoing arc at random and mark it. Then
follow it to the new current node and go to 2.
5. If the node is the initial node then no cycles and the
algorithm terminates. Otherwise, we are in dead end.
Remove that node and go back to the previous one. Go
to 2.
When to Check for Deadlocks?
• Check every time a resource request is made
• Check every k minutes
• When CPU utilization has dropped below a
threshold
Recovery from Deadlock
• We have detected a deadlock … What next?
• We have some options:
– Recovery through preemption
– Recovery through rollback
– Recovery through killing processes
Recovery from Deadlock:
Through Preemption
• Temporary take a resource away from its
owner and give it to another process
• Manual intervention may be required (e.g. in
case of printer)
• Highly dependent on the nature of the
resource.
• Recovering this way is frequently impossible.
Recovery from Deadlock:
Through Rollback
• Have processes checkpointed periodically
• Checkpoint of a process: its state is
written to a file so that it can be
restarted later
• In case of deadlock, a process that owns
a needed resource is rolled back to the
point before it acquired that resource
Recovery from Deadlock:
Through Killing Processes
• Kill a process in the cycle.
• Can be repeated (i.e. kill other
processes) till deadlock is resolved
• The victim can also be a process NOT in
the cycle
Deadlock Avoidance
• In most systems, resources are
requested one at a time.
• Resource is granted only if it is safe to
do so
Safe and Unsafe States
• A state is said to be safe if there is one
scheduling order in which every process
can run to completion even if all of them
suddenly request their maximum number
of resources immediately
• An unsafe state is NOT a deadlock state
Safe and Unsafe States
Maximum the process will need (e.g. A will need 6 more).
Assume a total of 10 instances of the resources available
This state is safe because there exists a sequence of allocations that allows
all processes to complete.
Safe and Unsafe States
How about this state?
The difference between a safe and unsafe state is that from a safe state the system can
guarantee that all processes will finish; from an unsafe state, no such guarantee can be given.
The Banker’s Algorithm
• Dijkstra 1965
• Checks if granting the request leads to
an unsafe state
• If it does, the request is denied.
The Banker’s Algorithm:
The Main Idea
• The algorithm checks to see if it has enough
resources to satisfy some customers
• If so, the process closest to the limit is
assumed to be done and resources are back,
and so on.
• If all loans (resources) can eventually be
repaid, the state is safe.
The Banker’s Algorithm:
Example (single resource type)
Safe UnsafeSafe
The Banker’s Algorithm:
Example (multiple resources)
The Banker’s Algorithm
• Very nice theoretically
• Practically useless!
– Processes rarely know in advance what
their maximum resource needs will be.
– The number of processes is not fixed.
– Resources can suddenly vanish.
Deadlock Prevention
• Deadlock avoidance is essentially
impossible.
• If we can ensure that at least one of
the four conditions of the deadlock is
never satisfied, then deadlocks will be
structurally impossible.
Deadlock Prevention:
Attacking the Mutual Exclusion
• Can be done for some resources (e.g the
printer) but not all.
• Spooling
• Words of wisdom:
– Avoid assigning a resource when that is not
absolutely necessary.
– Try to make sure that as few processes as
possible may actually claim the resource
Deadlock Prevention:
Attacking the Hold and Wait Condition
• Prevent processes holding resources from
waiting for more resources
• This requires all processes to request all
their resources before starting execution
• A different strategy: require a process
requesting a resource to first temporarily
release all the resources it currently holds.
Then tries to get everything it needs all at
once
Deadlock Prevention:
Attacking No Preemption Condition
• Virtualizing some resources can be a
good strategy (e.g. virtualizing a
printer)
• Not all resources can be virtualized (e.g.
records in a database)
Deadlock Prevention:
The circular Wait Condition
• Method 1: Have a rule saying that a
process is entitled only to a single
resource at a moment.
• Method 2:
– Provide a global numbering of all resources.
– A process can request resources whenever
they want to, but all requests must be done
in numerical order
– With this rule, resource allocation graph
can never have cycles.
Deadlock Prevention:
Summary
Conclusions
• Deadlocks can occur on
hardware/software resources
• OS needs to be able to:
– Try to avoid them if possible
– Detect deadlocks
– Deal with them when detected