Lockfree bounded LIFO stack and an almost Lock-free bounded FIFO queue and an almost Lock-free bounded FIFO priority queue version 1.1

Hello,


Lockfree bounded LIFO stack and an almost  Lock-free bounded FIFO queue 
and an almost Lock-free bounded FIFO priority queue version 1.1

Author: Amine Moulay Ramdane is the inventor of the
         Lockfree bounded LIFO stack algorithm and
         the inventor of the almost Lockfree bounded
         FIFO queue algorithm and of the almost Lockfree
         bounded priority FIFO queue algorithm.


Description:

A Lock-free LIFO Stack algorithm and an almost(very nearly) Lock-free 
FIFO queue and an almost(very nearly) Lock-free priority queue, they are 
bounded (and the Lock-free LIFO stack is based on the almost Lock-free 
FIFO queue), and they don't have false sharing, and they retain the 
following advantages of Lock-free and Wait-free algorithms:

- 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 my
   algorithms, 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.
- Pre-emption tolerant and they are good at convoy-avoidance.
- Starvation-free.
- And for k number of threads in the system (of my almost Lock-
   free FIFO queue or my almost Lock-free FIFO priority queue or
   my almost Lock-free LIFO stack), my almost Lock-free FIFO
   queue or my almost Lock-free FIFO priority queue or my almost
   Lock-free LIFO stack have a system latency of O(q + s*sqrt(k)
   and an individual latency of O(k(q + s*sqrt(k)), but my
   algorithms are of the SCU(0,1) Class of Algorithms, so under
   scheduling conditions which approximate those found in
   commercial hardware architectures, there system latency is
   O(sqrt(k)) and there individual latency is O(k*sqrt(k)),
   read more below to understand more.

I have invented this Lock-free LIFO stack algorithm 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.

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.

And read the following paper:

https://arxiv.org/pdf/1311.3200.pdf

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))."

My algorithms of an almost Lock-free FIFO queue and my Lock-free LIFO 
stack algorithm are of the SCU(q, s) Class of Algorithms, so they are 
powerful and they are starvation-free and for k number of threads they 
have a system latency of O(q + s*sqrt(k) and an individual latency of 
O(k(q + s*sqrt(k)).

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:

https://sites.google.com/site/scalable68/lockfree-bounded-lifo-stack-and-fifo-queue

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+

You can configure it as follows from inside defines.inc file:

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

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


Thank you,
Amine Moulay Ramdane.