Concurrency
Concurrency & Deadlocks
Inter-Process Communication (IPC)
Processes often need to work together or at the very least share resources.
Issues
Send information
Mitigate contentions(disagreements) over resources
Synchronize dependencies
Race Condition
Race condition is a condition where the behavior(result) of the system depends on exact order of processes running.
E.g. Two processes want to access shared memory at the same time: Read is typically not an issue but write or conditional execution IS.
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(disagreements) 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
Read-Modify-Write cycles are typically an issue. For instance, you read a variable, make a decision and modify the variable.
Examples:
These examples will have problems if the same code is executed by two threads concurrently. Consider the race and preemption case with 2 threads.
So, expectation is that code has "consistent view" at data.
Critical Region / Section
Critical section / region is a protected section that accesses a shared resource, which can only executed by at most one process at a time.
Mutual Exclusion: Only one process (thread) at a time can access any shared variables, memory or resources.
Four conditions to prevent errors
No two processes simultaneously in critical region
No assumptions made about speeds or numbers of CPUs
No process running outside its critical region may block another process
No process must wait forever to enter its critical region
Mutual Exclusion with Busy Waiting
Simple solution: Disable interrupt
Problems:
Disabling interrupt for user program would be too much privilege
Won't work in SMP (multi-core systems)
Solution: Use lock variable
If the value of the lock variable is 0, then process sets it to 1 and enters. Other processes have to wait.
Problem: Read-Modify-Write cycles
Peterson's Solution
Mathematically correct but not practical, cannot be efficiently implemented.
The TSL Instruction (Test and Set Lock)
With a "little help" from hardware: the test and set instruction is used to write(set) 1 to a memory location and return its old value as a single atomic (non-interruptible) operation.
This is implemented by locking the bus.
The XCHG Instruction (cmp_and_swap)
This is also implemented by locking the bus.
Load / Store Conditional
Modern processors resolve cmp_and_swap through the cache coherency mechanism.
Reservation (ldwx
) remembers ONE address on a CPU and verifies on (stwx
) whether still held otherwise store will fail.
Reservation is lost on:
interrupts
if another CPU steals cacheline holding
lockvar
if another
lwdx
is issued.
Comparisons
Both TSL (xchg/cmpswp) and Peterson's solution are correct, but they:
rely on busy-waiting during "contention"
waste CPU cycles (one way to circumvent this is by calling thread_yield to voluntarily give up the CPU and upon rescheduling it will attempt again)
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.
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 (is related to):
frequency of attempts to acquire the lock
lock hold time (time between acquisition and release)
number of threads/processes acquiring a lock
If lock contention is low, TSL is an OK solution. The linux kernel uses it extensively for many locking scenarios.
Concurrency vs Parallelism
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
Example: Piping
ls -ls | grep "yooh" | awk '{print $1}'
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 are not just for stdin and stdout. They can be created by applications used for all kinds of things.
PipeBuffer typically has 16 write slots. 4KB guaranteed to be atomic.
Race Condition
Fatal race condition in this example:
Let count = 1
Consumer begins loop, decrements count == 0
COnsumer returns to loop beginning and executes:
if (count == 0)
, then preemption happensProducer gets to run, executes
count = count + 1; if (count == 1)
and callswakeup(consumer)
Preemption Consumer calls
sleep(consumer)
Requirements
Need a mechanism that allows synchronization between processes/threads on the base of shared resources.
Synchronization implies interaction with scheduling subsystem.
Let to the innovation of semaphores.
Semaphore
Semaphore Data Structure
Implementation:
How do P and V avoid race condition?
P()
and V()
must be atomic.
Solution: By disabling interruptions
First line of P()
and V()
can disable interrupts. Last line of P()
and V()
re-enables interrupts.
However, disabling interrupts only works on single CPU systems.
Solution: Use atomic lock variable
New implementation:
Two kinds of semaphores: Mutex and Counting
Mutex semaphores or binary semaphores or simply LOCK is for mutual exclusion problems: value initialized to 1.
Counting semaphores is for synchronization problems: value initialized to any value 0..N. Value shows available tokens to enter or number of processes waiting when negative.
They are of same implementation, just different initial values.
Semaphore Solution to the Producer-Consumer Problem
3 semaphores (minimal) example:
4 semaphores for lower lock contention:
Using two mutexes for read and write makes it possible for producer and consumer to be more concurrent (they should not be competing), thus less lock contention.
Mutexes in Pthreads
Some of the Pthreads calls relating to mutexes are:
Thread call | Description |
---|---|
Pthread_mutex_init | Create a mutex |
Pthread_mutex_destroy | Destroy an existing mutex |
Pthread_mutex_lock | Acquire a lock or block |
Pthread_mutex_trylock | Acquire a lock or fail |
Pthread_mutex_unlock | Release a lock |
Some of the Pthreads calls relating to condition variables are:
Thread call | Description |
---|---|
Pthread_cond_init | Create a condition variable |
Pthread_cond_destroy | Destroy a condition variable |
Pthread_cond_wait | Block waiting for a signal |
Pthread_cond_signal | Signal another thread and wake it up |
Pthread_cond_broadcast | Signal multiple threads and wake all of them |
P: wait, V: signal
Using threads to solve the producer-consumer problem
Problems with Semaphores
It can be difficult to write semaphores code (arguably)
One has to be careful with the code construction
If a thread dies and it holds a semaphore, the implicit token is lost
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: SMP Scheduler
Deadlock example
Consider situation: cpu0 (i=0, j=1)
and cpu1 (i=1, j=0)
, this can lead to deadlocks -> must use same order instead
Force order solution
We force the correct order. If necessary, we release owned lock first and re-acquire.
Busy Lock vs Semaphore
If lock hold time is short and/or code is uninterruptible, then lock variables and busy waiting is OK (linux kernel uses it all the time).
Otherwise, 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 into 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
Monitor Example
Producer-Consumer Problem with Monitor
Message Passing
When there's no shared memory (e.g. on distributed systems), we can send LAN messages instead.
send(destination, &message);
send(destination, &message);
Producer-Consumer Problem with Message Passing
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
What about buffer-less messages?
Send and Receive wait (block) for each other to be ready to talk: rendezvous (meet at an agreed time and place)
Barriers
A barrier for a group of threads or processes means any thread/process must stop at this point and cannot proceed until all other threads/processes reach this barrier.
Three possible states:
Processes approaching a barrier
All processes but one blocked at the barrier
When the last process arrives at the barrier, all of them are let through
Deadlocks
A deadlock is a state in which each member of a group waits for another member, including itself, to take action. It occurs among processes/threads who need to acquire resources in order to progress.
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
Deadlock vs Starvation
Deadlock: Process(es) waiting on events (resources) that will never happen. Can be system wide or just one process.
Starvation: Process(es) waiting for its turn but never comes.
Process could move forward, the resource or event might become available but this process may not be able to get access to it.
Such starvation is usually caused by certain policy. For example, a printing policy may always choose to print the smallest file available. Then now one process shows up with HUGE file. This process will not likely get to run if there's steady stream of smaller file jobs coming in.
Resources
Resources are anything that must be acquired, used and released over the course of time. Could be hardware or software resources.
Preemptable and non-preemptable resources
Preemptable: can be taken away from the process with no ill-effect
Non-preemptable: cannot be taken away from the process without causing the computation to fail
Reusable and Consumable resources
Reusable: can be safely used by only one process at a time and is not depleted by that use. e.g. processors, I/O devices, main and secondary memory, devices, and data structures such as files, databases and semaphores.
Consumable: one that can be created (produced) and destroyed (consumed). e.g. interrupts, signals, messages and information in I/O buffers.
Conditions for Resource Deadlocks
Each resource is either currently assigned to exactly one process or is available
Processes currently holding resources that were granted earlier can request new resources
Resources previously granted cannot be forcibly taken away from a process. They must be explicitly released by the process holding them.
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
How to Deal with Deadlocks
Just ignore the problem.
Let deadlocks occur, detect them, and take action.
Dynamic avoidance by careful resource allocation.
Prevention, by structurally negating one of the four required conditions.
The Ostrich Algorithm
The ostrich algorithm is a strategy of ignoring potential problems on the basis that they may be exceedingly rare. It is used when it is more cost-effective to allow the problem to occur than to attempt its prevention.
Deadlock Detection
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 ore more cycles, a deadlock exists.
Formal Algorithm to Detect Cycles in the Allocation Graph
For each node N in the graph do:
Initialize L to empty list and designate all arcs as unmarked
Add the current node to end of L. If the node appears in L twice then we have a cycle and the algorithm terminates
From the given node, pick any unmarked outgoing arc. If none is available, go to 5.
Pick an outgoing arc at random and mark it. Then follow it to the new current node and go to 2.
If the node is the initial node, then no cycles found 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 and recovery through killing process.
Recovery 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 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 Through Killing Process
Kill a process in the cycle.
Can be repeated (i.e. kill other processes) until 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 theme suddenly request their maximum number of resources immediately.
An unsafe state is NOT a deadlock state.
For example, assume a total of 10 instances of the resources available:
The Banker's Algorithm
The algorithm checks if granting the request leads to an unsafe state. If it does, the request is denied.
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.
Example
Problems
Very nice theoretically, but 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.
E.g. For printer, use spooling (Spooling is a process in which data is temporarily held to be used and executed by a device, program or the system.).
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. virtualize a printer).
Not all resources can be virtualized. (e.g. records in a database)
Deadlock Prevention: Attacking 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.
Summary
Condition | Approach |
---|---|
Mutual exclusion | Spool everything |
Hold and wait | Request all resources initially |
No preemption | Take resources away / virtualize them |
Circular wait | Order resources numerically |
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
Last updated