tag:blogger.com,1999:blog-8231772264325864647.post7520744292207940889..comments2024-03-22T19:05:00.088+01:00Comments on Concurrency Freaks: Lock-Free and Wait-Free, definition and examplesPedro Ramalhetehttp://www.blogger.com/profile/01340437958052998917noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-8231772264325864647.post-21113824141516852312015-11-19T22:55:54.804+01:002015-11-19T22:55:54.804+01:00Hi Jaksa,
The definition of wait-free doesn't ...Hi Jaksa,<br />The definition of wait-free doesn't explicitly require lock-free, but it does so implicitly:<br />If we provide the guarantee that N threads are making progress (wait-free) then this implies also that at least one thread is making progress (lock-free).<br /><br />An obstruction-free method will complete in a finite number of steps if it is running in isolation (i.e. no other threads are attempting to access the same object/lock/whatever). The same is true for lock-free.<br />If it is _not_ running in isolation, then obstruction-free does _not_ give you the guarantee to complete in a finite number of steps, and lock-free gives you the guarantee that at least _one_ thread will complete in a finite number of steps (but maybe none of the other N-1 threads will ever complete). <br />Wait-free gives you the guarantee that _all_ threads will always complete in a finite number of steps.<br /><br />Hope this answers your question.Pedro Ramalhetehttps://www.blogger.com/profile/01340437958052998917noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-28983955507199389162015-11-19T16:23:03.386+01:002015-11-19T16:23:03.386+01:00I might be wrong, but shouldn't the definition...I might be wrong, but shouldn't the definition of wait-free explicitly require being lock-free. Because an obstruction-free operation that uses a lock which is exclusive only to that operation will finish in a bounded number of steps (depending on the population), right?Jaksahttps://www.blogger.com/profile/11943153007608087685noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-85619261959352274462015-04-19T16:39:35.195+02:002015-04-19T16:39:35.195+02:00Thank you!Thank you!Roccohttps://www.blogger.com/profile/05515022753876218473noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-51871493584079414292013-07-01T22:05:59.815+02:002013-07-01T22:05:59.815+02:00Hi Roman. You are right, Andreia had already point...Hi Roman. You are right, Andreia had already pointed it out before and I forgot to change it. I was thinking in terms of "stronger guarantees" but that would not be a proper usage of a Venn diagram.<br />I've replaced it with a new diagram where the order is reversed as you suggested.<br />Thanks for pointing it out!Pedro Ramalhetehttps://www.blogger.com/profile/01340437958052998917noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-55532387378968255012013-06-27T09:02:15.920+02:002013-06-27T09:02:15.920+02:00Hi. Thanks for the article. I think I'm missin...Hi. Thanks for the article. I think I'm missing something since it looks like the vien digram is backwards. You write that 'Something else that is a common cause of confusion is that "Wait-Free implies Lock-Free" (but not the other way around). This means that a function that is said to be Wait-Free gives that same (and more) progress guarantees than a function that is Lock-Free.' I read this as that the set of all Wait-Free functions is a subset of all Lock-Free functions (since the conditions for Wait-Free are stronger than for Lock-Free). In your diagram it's other way around: set of Wait-Free functions contains the set of Lock-Free.../https://www.blogger.com/profile/14812986518443172899noreply@blogger.com