Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming.threads > #4258 > unrolled thread
| Started by | Sky89 <Sky89@sky68.com> |
|---|---|
| First post | 2018-05-09 18:01 -0400 |
| Last post | 2018-05-09 18:01 -0400 |
| Articles | 1 — 1 participant |
Back to article view | Back to comp.programming.threads
About Deadlock-freedom and Starvation-freedom.. Sky89 <Sky89@sky68.com> - 2018-05-09 18:01 -0400
| From | Sky89 <Sky89@sky68.com> |
|---|---|
| Date | 2018-05-09 18:01 -0400 |
| Subject | About Deadlock-freedom and Starvation-freedom.. |
| Message-ID | <pcvd1m$apt$3@dont-email.me> |
Hello.. 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 A critical section object and the Spinlock are starvation-free. Thank you, Amine Moulay Ramdane.
Back to top | Article view | comp.programming.threads
csiph-web