I. Progress
1. Progress Conditions
- Deadlock-free: some thread trying to acquire the lock eventually succeeds.
- Starvation-free: every thread trying to acquire the lock eventually succeeds.
- Lock-free: some thread calling a method eventually returns.
- Wait-free: every thread calling a method eventually returns.
DF and SF both need to be considered under fair executions,
which is not required for LF and WF.
|
Non-Blocking |
Blocking |
| Everyone makes progress |
Wait-free |
Starvation-free |
| Someone makes progress |
Lock-free |
Deadlock-free |
II. Synchronization
Overview
- Adding threads should not lower throughput
- Contention effects
- Mostly fixed by Queue locks
- CAS can invalidate cache. Hence using too many CAS’s may greatly slow down the program.
- Should increase throughput
- Not possible if inherently sequential
- Surprising things are parallelizable
Coarse-Grained Synchronization
Each method locks the object
- Avoid contention using queue locks
- Easy to reason about
- Standard Java model