Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #7292

Here is my other invention of a Lock-free bounded LIFO stack and an almost Lock-free bounded FIFO queue and an almost Lock-free bounded FIFO priority queue..

Show all headers | View raw

Hello,


Here is my other invention of a Lock-free bounded LIFO stack and an almost Lock-free bounded FIFO queue and an almost Lock-free bounded FIFO priority queue..

I am a white arab, and i think i am smart since i have also
invented many scalable algorithms and algorithms.. 


I have invented the following Lock-free bounded LIFO stack and an almost Lock-free bounded FIFO queue and an almost Lock-free bounded FIFO priority 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.


You can download them from below..

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 bounded FIFO queue and of a Lock-free bounded priority FIFO queue and of a Lock-free bounded LIFO stack 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


Thank you,
Amine Moulay Ramdane.

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Here is my other invention of a Lock-free bounded LIFO stack and an almost Lock-free bounded FIFO queue and an almost Lock-free bounded FIFO priority queue.. Amine Moulay Ramdane <aminer68@gmail.com> - 2022-01-10 13:22 -0800
  Re: Here is my other invention of a Lock-free bounded LIFO stack and an almost Lock-free bounded FIFO queue and an almost Lock-free bounded FIFO priority queue.. Flatulata Dentata <flatulata.dentata@gmail.com> - 2022-01-10 20:09 -0800
    Re: Here is my other invention of a Lock-free bounded LIFO stack and an almost Lock-free bounded FIFO queue and an almost Lock-free bounded FIFO priority queue.. Flatulata Dentata <flatulata.dentata@gmail.com> - 2022-01-11 13:07 -0800

csiph-web