Concurrent hashing and natural parallelism
Prev: Counting, sorting, and distributed coordination Next: Skiplists and balanced search
Exercises
Exercise 13.1. Modify the StripedHashSet to allow resizing of the
range lock array using read-write locks.
Exercise 13.2. For the LockFreeHashSet, show an example of the
problem that arises when deleting an entry pointed to by a bucket
reference, if we do not add a sentinel entry, which is never deleted,
to the start of each bucket.
Exercise 13.3. For the LockFreeHashSet, when an uninitialized bucket
is accessed in a table of size , it might be necessary to
recursively initialize, that is, split, as many as of its
parent buckets to allow the insertion of a new bucket. Show an example
of such a scenario. Explain why the expected length of any such
recursive sequence of splits is constant.
Exercise 13.4. For the LockFreeHashSet, design a lock-free data
structure to replace the fixed-size bucket array. Your data structure
should allow an arbitrary number of buckets.
Exercise 13.5. For the LockFreeHashSet, design a lock-free data
structure to replace the fixed-size bucket array. Your data structure
should allow for unbounded doubling of the number of buckets in order
to keep the average bucket length below THRESHOLD. Describe how you
would implement the methods in Fig. 13.35 and how your implementation
preserves lock-freedom, correctness, and expected or amortized
work.
Exercise 13.6. Outline correctness arguments for LockFreeHashSet’s
add(), remove(), and contains() methods.
Hint: You may assume the LockFreeList algorithm’s methods are
correct.
Prev: Counting, sorting, and distributed coordination Next: Skiplists and balanced search