8. Locks
Deadlock: Lifelock: all threads try to acquire, drop, acquire, … locks (state of system changes w/o progress)
Semaphores: variable used to control access to a common resource by multiple threads
Possibility to prevent deadlocks: global ordering
volatile: Each thread may cache variables locally. Without volatile, one thread might not see updates made by another thread.
Reader-Writer Lock
3 States:
- not held
- held for writing by one thread
- held for reading by one/multiple threads
Not fair b/c readers are prioritized
RW Lock
A fairer lock
- writers
- readers
- writersWaiting
- readersWaiting
- writersWait
Granular Lock
Hand-Over-Hand Locking
Ex. Sorted Linked List. Always lock the current and next node (otherwise: we add a new element, but another thread removes it’s predecessor. Then the new node is not included)
Disadvantage: lot’s of unnecessary locking and unlocking (Overhead!)
Optimistic Lock
- Find nodes w/o locking
- If found, lock both nodes and check that nothing was changed
- If changed between finding and locking: release lock and start over
Disadvantage: might start over
Lazy Synchronization
- Mark if not reachable anymore using AtomicBoolean
- Synchronize pred and curr and remove
Like optimistic but prevent starting over b/c all other threads know if a node is about to be removed