Non-blocking Algorithms

Tutorials

In the tutorials we're going to implement a simple concurrent cache.

• Tutorials repository

Homework

Your task is to implement a concurrent add-only hash-set of Strings without using locks.

1. Download the skeleton from git repository
2. See the naive synchronized implementation in SynchronizedStringSet class.
3. Implement the same behavior in NonblockStringSet class without locks by using atomic operations (see java.util.concurrent.atomic package).
   • Which atomic structure is useful for the implementation of bins?
   • If an atomic object (Atomic* classes) is created too many times, use Atomic*FieldUpdater instead to avoid unnecessary memory overhead.
4. Test your implementation with provided tests in the JcstressStringSetTest
5. Upload a zipped NonblockStringSet.java file to BRUTE

The amount of points you'll get is based on how close you are to the reference solution. If you manage to beat the reference solution, you'll receive one bonus point.

Voluntary Exercises

You can also try to implement the two following assignments from previous years.

Linked-List

Some related slides are available in here

1. Start with the implementation of the set using a simple linked list.
2. Download the template from https://gitlab.fel.cvut.cz/esw/nonblock-linkedlist.git
3. Implement the set with AtomicMarkableReference<Type> holding a reference to the next node, and the mark if this node holding the reference is logically deleted
4. Implement a helper method find(int value), which traverses the list until it finds the correct position of the value and deletes the marked nodes during the traversal.
5. Implement the delete(int value) method with marking of the deleted node beforehand (logical deletion) and with other threads helping with the physical deletion if they find any marked node.
6. Implement add(int value) method.
7. Implement wait-free contains(int value) method. The method is read-only.

Skip-List

Generalize the previous algorithm to a skip list. Use the template from https://gitlab.fel.cvut.cz/esw/nonblock-skiplist.git

1. To clarify how the skip list works, we recommend starting with the contains method, which just goes through the list and tries to find the value (without calling find() method). It does not need to change anything in the skip list. This point is not mandatory.
2. Try to generalize the method find(), to look not only for one predecessor and one successor of the searched value but for the predecessors on all the levels.
3. Implement add and delete methods
4. Testing is an important part of implementation of any algorithm; therefore, your task is also to create tests. Unfortunately, testing concurrent structures is difficult.
   • Start with testing of only single-thread behavior (very easy - e.g., classical JUnit).
   • Try to design some tests that check the functionality in a multi-threaded environment.
   • You have to be able to demonstrate that the algorithm is working correctly.