Skip to content

JonChesterfield/Waitfree

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Wait free and lock free data structures

At present, a single such data structure is implemented. This is a single producer, single consumer queue.

The central algorithm is derived from "Correct and Efficient Bounded FIFO Queues", N. Le, A. Guatto, A. Cohen and A. Pop which is derived from the work of L. Lamport in "Proving the correctness of multiprocess programs".

The algorithm for push or pop is essentially:

Get a pointer to my end of the queue Get a pointer to the other end of the queue Use these to determine if we can continue Swap an element with my end of the queue Increment my pointer

The API is not an especially friendly one, in particular whether the element passed to pop or push remainins in a valid state depends on the integer return code from the function calls. This implementation is intended as an implementation detail of a number of easier to use structures.

About

Wait free and lock free data structures

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages