Non-blocking Algorithms
Your task is to implement a concurrent add-only hash-set of Strings without using locks.
See the naive synchronized implementation in SynchronizedDictionary
class.
Implement the same behavior in NonblockDictionary class without locks by using atomic operations (see java.util.concurrent.atomic
package).
Which atomic structure is useful as 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):
jcstress -
JcstressDictionaryTest
in the main source folder
vmlens -
VmlensDictionaryTest
in the test source folder
Upload your solution to
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 and the code will be evaluated manually. You will present the code to the tutor and explain what key parts of the code do.
Concurrent Testing
There is several available tools that can be used:
vmlens - examples provided in the template of the assignment and also on the website of the tool
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 the previous year.
Linked-List
Some related slides are available in here
Start with the implementation of the set using simple linked list.
Implement the set with AtomicMarkableReference<Type>
holding 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
-
To clarify how the skip list works, we recommend to start 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. Unfortunatelly, testing of concurrent structures is difficult.
Start with testing of only single-thread behaviour (very easy - e.g. classical JUnit).
Try to desing some tests that checks the functionality in a multi-threaded environment.
You have to be able to demonstrate that the algorithm is working correctly.