This assignment will be closed on May 27, 2026 (23:59:59).
You must be authenticated to submit your files

CSE 305 - Tutorial 7 - Lazy and Lock-free data structures

In this tutorial, you will be asked to implement classes/functions described below. The exact definitions and automated tests are given to you in the following archive.

  1. Improve the lazy version of SetList (provided in the archive, see the second section of the lecture) to MultisetList, a class implementing a multiset, that is, a set that contains each element with a multiplicity. The add method will increase the multiplicity by one if the element is already in the set. The remove method will descrease the multiplicity if it is positive, and return false only if there was no such element in the set.

    Note that, if you store the multiplicity, you do not need the marked field anymore.

  2. 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.

Upload your file td7.cpp:

Upload form is only available when connected

The following problem is optional.

  1. 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).

Upload your file td7.cpp:

Upload form is only available when connected