====== Non-blocking Algorithms ======

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

  - Download the program from git repository: git clone https://gitlab.fel.cvut.cz/esw/nonblock-set
  - See the naive synchronized implementation in ''SynchronizedStringSet'' class.
  - 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.
  - Test your implementation with provided tests and try to implement your own (especially the concurrent ones):
     * Single-thread JUnit tests 
     * Basic test is done also in the ''Main'' class
     * Concurrent tests using two frameworks (basic instructions are in the test implementations, detailed on their websites):
        * [[https://github.com/openjdk/jcstress|jcstress]] - ''JcstressStringSetTest'' in the main source folder
        * [[https://vmlens.com/|vmlens]] - ''VmlensStringSetTest'' in the test source folder  
  - Upload your solution to [[https://cw.felk.cvut.cz/brute/|BRUTE]]
        * Upload only your ''.java'' files you modified (or ''pom.xml'' if you changed it).
        * Do NOT upload any binaries or libraries.
        * There is no automatic evaluation. We will evaluate the code manually. You will present the code to the tutor and explain what key parts of the code do.

===== Concurrent Testing =====
There are several available tools that can be used:
  * [[https://github.com/openjdk/jcstress|jcstress]] - OpenJDK tool with [[https://github.com/openjdk/jcstress/tree/master/jcstress-samples/src/main/java/org/openjdk/jcstress/samples|code samples]] provided
  * [[https://vmlens.com/|vmlens]] - examples provided in the template of the assignment and also on the website of the tool
<note important>vmlens does not fully support JDK 17 - for full functionality, you need to run it on older JDK (I tested it on JDK 11 and 14) </note>
  * [[https://github.com/javapathfinder/jpf-core/wiki|Java Pathfinder]] - Tool developed by NASA for model checking of java bytecode programs.
===== Voluntary Exercises =====
You can also try to implement the two following assignments from previous years. 
==== Linked-List ====


Some related slides are available in {{ :courses:b4m36esw:labs:nonblock.pdf |here}}

     - Start with the implementation of the set using a simple linked list.
     - Download the template from[[https://gitlab.fel.cvut.cz/esw/nonblock-linkedlist.git]]
     - 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
       - 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. 
       - 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.   
       - Implement ''add(int value)'' method.
     - 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]]
    - 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.
    - 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.
    - Implement add and delete methods
    - 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.