Common Problems in Concurrent Programs

Question 1

Race conditions

Answer 1

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)

Question 2

Deadlock Scenario

Question 3

Deadlock

Answer 3

1. Mutual exclusion of resources
   – Processes need exclusive access to the resources they are attempting to obtain
2. Hold and wait
   – Processes are allowed to hold a resource while waiting for another resource
3. Non-preemption of resources
   – Resources may not be forcibly taken away from a process
4. Circular wait
   – Possibility of getting into a cycle of processes where each process waits for a resource held by the ‘next’ process

Question 4

Deadlock in Threads

Answer 4

Very typical with incorrect lock ordering

Question 5

Dealing with Deadlock

Answer 5

1. Program design so circular wait never occurs
   – Impose total ordering on resources and requiring all processes request resources in that same order
2. Prove formally a program is deadlock free before running
   – Very difficult, except for small and simple programs
   – Satellites, mission critical systems use this…
3. Detect deadlock at runtime, and try recover automatically
   – Selectively abort processes
   – Roll back to an earlier state
4. Manual corrective action
   – Ctrl + C
   – Reboot!
   – Kick the machine?

Question 6

Deadlocks and Locking Order

Answer 6

Question 7

Livelock Intuition

Answer 7

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

Question 8

Livelock

Answer 8

• 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

Question 9

Starvation

Answer 9

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

Question 10

Dining Philoshopher

Solution? Each picks up an available fork, then waits for the other fork to become available

Answer 10

Deadlock!

Question 11

Dining Philoshopher

Each picks up an available fork, then checks for the other fork.
If unavailable, put downs the held fork. Retries. Solution?

Answer 11

Livelock!

Question 12

Dining Philoshopher

Each picks lower-numbered fork first and then highernumbered fork

Answer 12

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

Question 13

Paranoid Programming

Answer 13

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