GitHub - MultiArrayQueue/WaitFreeMultiArrayQueue: Wait-Free Multi-Array Queue program codes · GitHub

/" data-turbo-transient="true" />

Skip to content

Search or jump to...

Search code, repositories, users, issues, pull requests...

-->

Search

Clear

Search syntax tips

Provide feedback

--><br>We read every piece of feedback, and take your input very seriously.

Include my email address so I can be contacted

Cancel

Submit feedback

Saved searches

Use saved searches to filter your results more quickly

-->

Name

Query

To see all available qualifiers, see our documentation.

Cancel

Create saved search

Sign in

/;ref_cta:Sign up;ref_loc:header logged out"}"<br>Sign up

Appearance settings

Resetting focus

You signed in with another tab or window. Reload to refresh your session.<br>You signed out in another tab or window. Reload to refresh your session.<br>You switched accounts on another tab or window. Reload to refresh your session.

Dismiss alert

{{ message }}

MultiArrayQueue

WaitFreeMultiArrayQueue

Public

Notifications<br>You must be signed in to change notification settings

Fork

Star

main

BranchesTags

Go to file

CodeOpen more actions menu

Folders and files<br>NameNameLast commit message<br>Last commit date<br>Latest commit

History<br>3 Commits<br>3 Commits

models_for_Spin

models_for_Spin

LICENSE

LICENSE

README.md

README.md

View all files

Repository files navigation

Wait-Free Multi-Array Queue

This is the "latest evolution" of the Multi-Array Queues (after the Java Queues<br>and the Lock-Free Queue):<br>A Queue that is linearizable, lock-free, and in the steady state (i.e. no Queue extensions (anymore)) also wait-free and garbage-free.

The garbage-freedom in the steady state makes this Queue wait-free unconditionally, as no memory allocator<br>(that would disturb the wait-freedom) is involved in there.

This work has been inspired by the Kogan & Petrank Queue<br>in the sense that the linearization operations themselves can be helped by other threads if the helpee has a phase number<br>lower than (or equal to) the phase number of the helper. Other actions (that do not constitute linearization points)<br>can be helped by other threads too. Metaphorically, the algorithms can be seen as a "big carousel" of linearization helping<br>and helping to finish already linearized operations.

To illustrate the principle by an extreme (but possible) execution path: A thread begins its operation by drawing a new phase number<br>and registering the operation in the state array. Immediately after that it goes asleep. In the meantime<br>other threads help linearize and finish the registered operations. When the bespoke thread wakes up,<br>it "goes round" the state array and finds that all operations with phase numbers up to (and including) its phase number<br>are already done, some eventually already replaced by new operations (with higher phase numbers).<br>So without having done any "real work", the thread can successfully return.

The bound on the number of execution steps depends on the number of active threads (this is inherited from the Kogan & Petrank Queue).<br>The program codes of this Wait-Free Queue are more complex than those of the Lock-Free Queue,<br>and there are also more CASes on the path, so that a lower throughput is expected - even in the uncontended case.

New Interactive Simulator of the Wait-Free Queue

Get acquainted here

Implementation

In short: There are currently two implementations aligned with each other: a Spin model and the JavaScript Simulator.<br>No real (i.e. non-model) implementation exists (yet).

In long: The algorithms have first been designed and verified as a model for the Spin model checker<br>(for computer-aided simulations and exhaustive verifications). The Spin model file is the primary source of information<br>and comments on the algorithms as such.

After that, the JavaScript Simulator<br>has been developed (for teaching and visual/manual simulations and verifications).

For a future "real" implementation, similar choices exist as for the<br>Lock-Free Queue,<br>with x86-64 assembly combined with C++ presumably being the most attractive option.

More details

The Wait-Free Multi-Array Queue is a linearizable multiple-writer multiple-reader lock-free FIFO Queue<br>that is in the steady state (i.e. no Queue extensions (anymore)) also wait-free and garbage-free.

The extension operations, however, involve the memory allocator which (most probably) is not wait-free.<br>Further, more than one thread can consider extending the Queue.<br>Each of these competing threads then prepares (allocates) memory for the new ring and tries to CAS it into the rings array.<br>The memory of the winning thread goes into use, but the losing threads have to free the allocated memory again.<br>In other words: A strict garbage-freedom has to be sacrificed in this case (in the sense that superfluous calloc-free pairs may occur).

The Wait-Free Queue builds on top of the Lock-Free Queue<br>with this main difference:

One array element consists of two halves, each 128-bit...