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

Groups > comp.programming.threads > #4259 > unrolled thread

Read again, i correct a typo

Back to article view | Back to comp.programming.threads

Contents

  Read again, i correct a typo Sky89 <Sky89@sky68.com> - 2018-05-09 18:03 -0400

#4259 — Read again, i correct a typo

Hello..


Read again, i correct a typo

About Deadlock-freedom and Starvation-freedom..

"Starvation-freedom can be defined as: Whatever the process p, each 
invocation of acquire_mutex() issused by p eventually terminates. OR Any 
process trying to enter critical section, will eventually enter critical 
section.

Deadlock-freedom: Whatever the time T , if before T one or several 
processes have invoked the operation acquire_mutex() and none of them 
has terminated its invocation at time T , then there is a time T' > T at 
which a process that has invoked acquire_mutex() terminates its 
invocation.[Raynal, Concurrent Programming: Algorithms, Principles, and 
Foundations] OR If process is trying to enter critical section, then 
some process, not necessary same one, eventually will enter critical 
section. OR At least one, always wins.

Notice, that deadlock-freedom is saying that there are some processes 
will make progresses, but others might be stuck(starving), trying to get 
into critical section. It sound weird at first, but it is so: not all 
threads are stuck, so there is no deadlock, i.e. deadlock-freedom.

On other hand, starvation-freedom is saying that every process trying to 
get into critical section, will eventually do so. There will be no 
processes that will ever starve.

This makes starvation-freedom much stronger property than deadlock-freedom."


Also read the following paper:

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


It says that:


"Recently, Herlihy and Shavit [12] suggested that perhaps the answer 
lies in a surprising property of lock-free algorithms: in practice, they 
often behave as if they were wait-free (and similarly, deadlock-free
algorithms behave as if they were starvation-free)."


So deadlock-free algorithms are starvation-free.


So the Windows critical section object and the Spinlock are starvation-free.


Thank you,
Amine Moulay Ramdane.

[toc] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web