Transcript Bart Verzijlenberg

A Java Implementation of a LockFree Concurrent Priority Queue
Bart Verzijlenberg
November 15, 2007
Agenda






Algorithm Review
Implementation
Java Package used
Testing
Conclusion
Questions
November 15, 2007
1
Algorithm Review



Priority Queue
Lock-free
Relies on atomic Compare and Swap
operations
November 15, 2007
2
Algorithm Review

The algorithm uses the Skip-List data structure



Extends the Skip-List for concurrent use
The Skip-List is sorted on the priority of the nodes
The algorithm is lock-free




No blocking
Prevent dead locks
Always progress by at least one operation
Risk of starvation
November 15, 2007
3
Algorithm Review
Skip-List





Multi-layer linked list
Probabilistic alternative to balanced trees
H forward pointer for a node of height h
Each pointer i points to the next node with
a height of at least i
Probabilistic time complexity log(N) for N
nodes
November 15, 2007
4
Inserting in a Skip-List
Inserting 17 in the list
November 15, 2007
5
Implementation

Two classes

Node


Represents an entry in the queue
SkipQueue

Contains the algorithm logic
November 15, 2007
6
Node Class
November 15, 2007
7
SkipQueue Class
November 15, 2007
8
Java Package Used

AtomicMarkableReference


Stores



In Java.util.concurrent.atomic
A reference to an object
A boolean flag
Provides ability to


Atomically set both the flag and reference
Compare and Swap (CAS) the flag and reference
November 15, 2007
9
Testing

Multi-threaded

10 insert threads


Each inserting 100,000 objects with random
integer keys
10 delete threads
Each deleting while the queue is not empty
 If the queue is empty, sleep for a bit and try again

November 15, 2007
10
Testing

Maintain a counter


Stores the number of nodes dequeued
When 1,000,000 nodes removed


Stop the delete threads
Check that
the queue is empty
 removed exactly 1,000,000 nodes

November 15, 2007
11
Testing

10 insert threads


Each inserting 100,000 random integer
numbers
When all numbers have been inserted


Remove them one at a time.
Making sure the nodes come out sorted
November 15, 2007
12
Removing Atomicity

Do atomic references make a difference


Replace each AtomicMarkableReference with a
similar class



i.e. does concurrency come into play, or are we just
lucky
Same functions
But they are not atomic
The queue becomes locked after a small number
of concurrent deletes.
November 15, 2007
13
Conclusion



Further testing is needed to verify the
correctness of the implementation
Tests so far are positive
But cannot be certain there are no
problems
November 15, 2007
14
Questions
November 15, 2007