Race conditions
It’s very easy to introduce subtle programing errors into concurrent programs
Unidentified or incorrectly-protected critical sections leading to race conditions
Why subtle?
- In a sequential program, given identical input, things happen deterministically (i.e. in the same order)
- This is not the case in a concurrent program (sometimes work)
- This has led to the design of special concurrent programming languages that try to aid correctness (e.g., Eiffel, CSP)
Deadlock Scenario
Deadlock
- Mutual exclusion of resources
– Processes need exclusive access to the resources they are attempting to obtain - Hold and wait
– Processes are allowed to hold a resource while waiting for another resource - Non-preemption of resources
– Resources may not be forcibly taken away from a process - Circular wait
– Possibility of getting into a cycle of processes where each process waits for a resource held by the ‘next’ process
Deadlock in Threads
Very typical with incorrect lock ordering
Dealing with Deadlock
- Program design so circular wait never occurs
– Impose total ordering on resources and requiring all processes request resources in that same order - Prove formally a program is deadlock free before running
– Very difficult, except for small and simple programs
– Satellites, mission critical systems use this… - Detect deadlock at runtime, and try recover automatically
– Selectively abort processes
– Roll back to an earlier state - Manual corrective action
– Ctrl + C
– Reboot!
– Kick the machine?
Deadlocks and Locking Order
Livelock Intuition
Two cars coming from opposite directions have to cross a single-lane bridge.
Cars get on the bridge, see each other. Each back offs so the other can pass.
Ad infinitum
Livelock
- Process can’t make progress for a reason other than deadlock (typically the process is still actively changing)
- Unlike deadlock, livelock may eventually resolve spontaneously
- However, often drops into an indefinite livelock ‘groove’, hence livelock is often as undesirable as deadlock
- Can occur if deadlock detection repeatedly triggered
Starvation
Some process is unable to obtain access to shared resources
- May happen because other processes repeatedly beat the other process in obtaining access
- Deadlock implies starvation but not vice versa
Dining Philoshopher
Solution? Each picks up an available fork, then waits for the other fork to become available
Deadlock!
Dining Philoshopher
Each picks up an available fork, then checks for the other fork.
If unavailable, put downs the held fork. Retries. Solution?
Livelock!
Dining Philoshopher
Each picks lower-numbered fork first and then highernumbered fork
Prevents deadlock
But not starvation: C eats, then thinks, but
before P can pick up 2, picks it up again…ad
infinitum
Need fair scheduling to guarantee that P
eventually eats
Paranoid Programming
If you are dealing with concurrent design patterns,
Approach the problem methodically
- Its very unlikely you can ‘code your way’ out of the problem
- (Especially with 500,000 lines of code..)
- Checks before, during, and after concurrency ‘hotspots’
- Pen and paper does wonders
