The Art of Multiprocessor Programming
The Art of Multiprocessor Programming, 2011. Maurice Herlihy, Nir Shavit. Morgan Kaufmann. Also available online in the ETH network.
Proposed Exercise Solutions
The synchronisation state of a lock-based program can be described as a directed graph, in which each node represents a thread. An edge between two nodes A and B represents that thread A waits for a lock held by thread B. A deadlock occurs if the graph is not cycle-free. Fine-grained locking is free of deadlocks because the locks are ordered by their position in the list and a thread can only acquire a lock if he holds all locks that were earlier in the list. A cycle in the graph can only occur if a thread is holding a lock and requests a lock that is coming before the lock it is currently holding.
No, the implementation is not correct anymore. The order in which the pred and curr entries of the remove() method are locked would also have to be changed. Otherwise a deadlock would occur when remove() holds the pred-lock and requires the curr-lock and add() holds the curr-lock and requires the pre-lock.
We consider all three possibilities in which threads could overlap with the add() method:
- add() - add(): Two threads want to add a value at the same time into the list. If they both want to add something after the same element, then one waits because they both want to lock the same predecessor. If the list contains a, b and c in this order and thread A wants to add something between a and b and thread B wants to add something between b and c this is also no problem because thread A does not modify b, but only sets a pointer to it.
- add() - remove(): Thread A wants to add something and thread B wants to remove something from a list a, b and c. If thread A wanted to add something between a and b, and had already acquired the lock for pred, then b can’t delete neither a nor b because either the lock pred or curr would belong to thread A.
- add() - contains(): Same argument as with add() - remove().
No matter whether the method returns true or false, the node contains has checked must have been accessible from the head at some point. This point can then be chosen for the linearisation.