Data Abstractions Homework 8

Problem 1. Simple Concurrency with B-Trees
Note: Real databases and file systems use very fancy fine-grained synchronization for B-Trees such as
“hand-over-hand locking” (which we did not discuss), but this problem considers some relatively simpler
approaches.
Suppose we have a B Tree supporting operations insert and lookup. A simple way to synchronize threads
accessing the tree would be to have one lock for the entire tree that both operations acquire/release.
(a) Suppose instead we have one lock per node in the tree. Each operation acquires the locks along
the path to the leaf it needs and then at the end releases all these locks. Explain why this allegedly
more fine-grained approach provides absolutely no benefit.
(b) Now suppose we have one readers/writer lock per node and lookup acquires a read lock for each
node it encounters whereas insert acquires a write lock for each node it encounters. How does
this provide more concurrent access than the approach in part (a)? Is it any better than having one
readers/writer lock for the whole tree (explain)?
(c) Now suppose we modify the approach in part (b) so that insert acquires a write lock only for the
leaf node (and read locks for other nodes it encounters). How would this approach increase
concurrent access? When would this be incorrect? Explain how to fix this approach without
changing the asymptotic complexity of insert by detecting when it is incorrect and in (only) those
cases, starting the insert over using the approach in part (b) for that insert. Why would reverting
to the approach in part (b) be fairly rare?
Problem 2. Minimum Spanning Trees
(a) Weiss, problem 9.15(a). For Prim’s algorithm, start with vertex A, show the resulting table (see
Figure 9.57 of the 3rd edition as an example, which is Figure 9.55 in the 2nd edition), and indicate
the order in which vertices are added. For Kruskal’s algorithm, produce a table, similar to Figure
9.58 in the 3rd edition, which is Figure 9.56 in the 2nd edition. Ties may be broken arbitrarily.
(b) Weiss, problem 9.15(b).