Skip to content

Optimistic Set is a linked-list based unique collection. It traverses the list twice per operation, only locking the nodes to be updated.

License

Notifications You must be signed in to change notification settings

javaf/optimistic-set

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Fine Set is a collection of unique elements maintained as a linked list. The list of nodes are arranged in ascending order by their key, which is obtained using hashCode(). This facilitates the search of a item within the list. When the list is empty, it contains two sentinel nodes head and tail with minimum and maximum key values respectively. These sentinel nodes are not part of the set.

Each node has an associated lock (fine-grained) that enables locking specific nodes, instead of locking down the whole list for all method calls. Traversing the list (find) is done in a hand-holding manner, as children do with an overhead ladder. Initially two nodes are locked. While moving to the next node, we unlock the first node, and lock the third node, and so on. This prevents any thread from adding or removing threads in between, allowing them to execute in pipelined fashion.

As this set uses fine-grained locks (per node), it performs well when contention is medium. Due to acquiring of locks in hand-holding fashion, threads traversing the list concurrently will be stacked behind each other. This forced pipelining occurs even if they want to modify completely different parts of the list.

Course: Concurrent Data Structures, Monsoon 2020
Taught by: Prof. Govindarajulu Regeti

add():
1. Create new node beforehand.
2. Find node after which to insert.
3. Add node, only if key is unique.
4. Increment size if node was added.
5. Unlock node pairs locked by find.
remove():
1. Find node after which to remove.
2. Remove node, only if key matches.
3. Decrement size if node was removed.
4. Unlock node pairs locked by find.
contains():
1. Find node previous to search key.
2. Check if next node matches search key.
3. Unlock node pairs locked by find.

See FineSet.java for code, Main.java for test, and repl.it for output.

references

About

Optimistic Set is a linked-list based unique collection. It traverses the list twice per operation, only locking the nodes to be updated.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages