More analysis of Lock-free algorithms..

Hello,

Read this:


More analysis of Lock-free algorithms..

I have just looked at the following invention of a Lock-free bounded 
queue by the following PhDs:

Peter Pirkelbauer that is a PhD in computer science

Here he is:

http://pirkelbauer.com/cv_peter_pirkelbauer.html

and by Reed Milewicz Postdoctoral Appointee, Sandia National Laboratories

Here he is:

https://scholar.google.com/citations?user=PzG-VUAAAAAJ&hl=en

Here is there paper of there Portable Lock-free Bounded Queue invention:

https://rmmilewi.github.io/files/lockfreequeue16.pdf


I think that there Lock-free Bounded Queue invention has a disadvantage 
, it is that it is too "complex", so it is not good , this is
why i have just invented my following Lock-free Bounbed Queue and a 
Lock-free Bounded Stack that are simple to reason about and are much 
less complex than the above invention:

About software fault tolerance and reliability, read again..

Read the following interesting document about Fault-tolerant computing:

http://web.cs.ucla.edu/~rennels/article98.pdf

I will soon provide you with my following new inventions that are my
new Lock-free algorithms that support software fault tolerance and 
reliability in a form of Thread-killing Immunity, that means any thread 
forcefully killed in the system won't delay other threads, and in a form 
of Signal Immunity and in a form of Pre-emption tolerance and 
convoy-avoidance and in a form of Priority Inversion Immunity etc.

Read my following thoughts to notice it:

About my new inventions of Lock-free algorithms..

I am a white arab, and i think i am smart since i have invented
many scalable algorithms and there implementations, and today
i will talk more about Lock-free algorithms..

I have previously invented a fully Lock-free bounded LIFO stack 
algorithm, but i have just invented a fully Lock-free bounded FIFO queue 
algorithm and a fully Lock-free bounded limited priority queue, but can 
we ask the question of: Do we have to be really smart to be able to 
invent those Lock-free algorithms ?

I think that we have to be smart to be able to invent them, because when 
you are inventing them you have to be able from the many characteristics 
of the Lock-free algorithm and the restrictive compare-and-swap (CAS) 
and/or double-length CAS (DCAS) to be able to invent them, so you are 
too restricted or too constrained and it makes the job of inventing 
those Lock-free algorithms difficult, this is why you have to be smart, 
and as you have noticed i have first invented a Lock-free bounded LIFO 
stack algorithm that is based on an almost(very nearly) Lock-free 
bounded FIFO queue, and this almost Lock-free bounded FIFO queue of mine 
has the following advantages(and notice that it only doesn't support 
Thread-killing Immunity, that means 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 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.

You can read about them and download them from my website here:

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


But i will show you soon my inventions of a fully Lock-free bounded LIFO 
stack algorithm and of a fully Lock-free bounded FIFO queue algorithm 
and of a fully Lock-free bounded limited priority queue algorithm.


Thank you,
Amine Moulay Ramdane.