under Free Pascal

Algorithm for lock-free fifo queue management

Dariusz Mazur

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.



Test the presented code, and compare and contrast its performance against a "traditional lock-based" solution for a single-producer/consumer queue. You just may find that lock-free thread-to-thread communication can be stable, simple, and "useful" after all.

>> flqueue.pas
Language: FPC Pascal v2.2.0+ / Delphi 6+
Required switches: none
Author: Dariusz Mazur
Date: 27.01.2008
Version: 0.6


Last update: 26-01-2008. Copyright © 2008 Dariusz Mazur