CSE 305 - Tutorial 8a - Lock-free data structures

In the lock-free SetList marks were used for deleting nodes (see the third section of the lecture). In this exercise, you are asked to implement a class MonotonicLockFreeSet which implements a lock-free set based on a list with only add and contains methods.

Hint: instead of AtomicMarkedReference from the lecture, you can use just atomic pointer. Note that, unlike an atomic pointer, atomic shared pointer will likely be not lock-free.

In the provided td8.cpp, you are given a class BST implementing binary search trees with only three operations: search, insert, and size (no remove). In this binary search tree all keys are distinct, and insert returns false if the key is already present. Complete the implementation of LockFreeBST making the BST class thread-safe using the lock-free approach.

Implement the AtomicMarkableReference class from the lecture using a combination of std::atomic instantiated at the user-defined structure RefAndMark (provided in td08.cpp). You are not allowed to use locks.

Remark The size of the structure RefAndMark on your computer will very likely exceed 64 bites, so the std::atomic of it will very likely be not lock-free itself (you can check this with is_lock_free method). This might be a bit annoying because any lock-free data structure based on such a class will not be honestly lock-free, but we will ignore this for now. For a method to make it likely lock-free, see the discussion here.

Remark If you are checking your implementation with valrgind (and I encourage you to do so), you might get puzzling Conditional jump or move depends on uninitialised value. It is likely not to be an error, this is to be expected when using compare_exchange_weak with custom structures (see discussion).