• Lockfree bounded LIFO stack and FIFO queue version 1.01

    From Wisdom91@21:1/5 to All on Thu Jul 9 20:50:39 2020

    Lockfree bounded LIFO stack and FIFO queue version 1.01

    Author: Amine Moulay Ramdane is the inventor of the
    Lockfree LIFO stack and he has corrected and
    enhanced the Lockfree FIFO queue


    A fast Lockfree FIFO queue and a fast lockfree LIFO Stacks, they are
    bounded, the Lockfree FIFO queue was corrected and enhanced by Amine
    Moulay Ramdane and it doesn't have false sharing, also Amine Moulay
    Ramdane has invented a lockfree LIFO stack that doesn't need ABA
    prevention and it doesn't need Hazard pointers and it is not complicated
    and it doesn't have false sharing, please look at its source code inside LockfreeStackBounded.pas.

    Wait-free and lock-free algorithms enjoy more advantages derived from
    their definitions:

    Thread-killing Immunity: Any thread forcefully killed in the system
    won't delay other threads.
    Signal Immunity: The C and C++Standards prohibit signals or asynchronous interrupts from calling many system routines such as malloc. If the
    interrupt calls malloc at the same time with an interrupted thread, that
    could cause deadlock. With lock-free routines, there's no such problem
    anymore: Threads can freely interleave execution.
    Priority Inversion Immunity: Priority inversion occurs when a
    low-priority thread holds a lock to a mutex needed by a high-priority
    thread. Such tricky conflicts must be resolved by the OS kernel.
    Wait-free and lock-free algorithms are immune to such problems.

    An unbounded queue can hold infinite number of messages, while bounded -
    up to some predefined limit. If the limit is reached further enqueue
    operations fail. Note that array-based queue are always bounded. On
    first sight unbounded queues are more attractive (because they allow you
    to not care). But they are not. They are dangerous. What will happen if
    your queue will grow up to 10^6 messages? 10^7? 10^8? 10^9? What? It
    should not happen? So why you put an unbounded queue in the first place?
    In 95% of cases you need a bounded queue, because it will enforce what
    you think should happen, and will save you from bad things,
    it is the same for Stacks.

    Read the following paper:


    This paper suggests a simple solution to this problem. We show that, for
    a large class of lock- free algorithms, under scheduling conditions
    which approximate those found in commercial hardware architectures,
    lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free
    progress. It says on the Analysis of the Class SCU(q, s):

    "Given an algorithm in SCU(q, s) on k correct processes under a uniform stochastic scheduler, the system latency is O(q + s*sqrt(k), and the
    individual latency is O(k(q + s*sqrt(k))."

    So i think lockfree algorithms are very interesting to work with.

    The size of the queue and the stack must be passed to the constructor
    and it must be the power of 2.

    You can download them from my website here:


    Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freepascal.org/

    Operating Systems: Windows, Mac OSX , Linux on (x86)...

    Required FPC switches: -O3 -Sd

    -Sd for delphi mode....

    Required Delphi switches: -$H+

    {$DEFINE CPU32} and {$DEFINE Windows32} for 32 bit systems

    {$DEFINE CPU64} and {$DEFINE Windows64} for 64 bit systems

    Thank you,
    Amine Moulay Ramdane.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)