From Wisdom91@21:1/5 to All on Thu Jul 30 20:49:27 2020
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
- Pre-emption tolerant and they are good at convoy-avoidance.
- 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:
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.