Algorithm for lock-free fifo queue management

This page presents an algorithm for lock-free fifo queue management.

Wait-free implementation of share data objects is an alternative approach for the problem of inter-task communication and synchronization. Wait-free mechanisms allow multiple tasks to access a shared object at the same time, but without enforcing mutual exclusion to accomplish this.

A wait-free implementation of a shared data objects guarantees that every process accessing the object always completes its operation in a bounded number of its own steps, regardless of interleaving (process halts, failures, scheduler behavior).

Wait-free inter-task communication does not allow one task to block another task and thus gives significant advantages over lock-based schemes.