- About Lockfree algorithms.. - 1 Update
- Read again, i correct a typo - 1 Update
- About Deadlock-freedom and Starvation-freedom.. - 1 Update
| Sky89 <Sky89@sky68.com>: May 09 06:14PM -0400 Hello, About Lockfree algorithms.. Read the following paper: https://arxiv.org/pdf/1311.3200.pdf 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))." So i think Lockfree algorithms are very interesting to work with. Thank you, Amine Moulay Ramdane. |
| Sky89 <Sky89@sky68.com>: May 09 06:03PM -0400 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. |
| Sky89 <Sky89@sky68.com>: May 09 06:01PM -0400 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. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.programming.threads+unsubscribe@googlegroups.com. |
No comments:
Post a Comment