3 ms·

> Code that is proven to work correctly without using synchronisation primitives, ie across the possible interleavings, is generally called "lock free" Informa

> Code that is proven to work correctly without using synchronisation primitives, ie across the possible interleavings, is generally called "lock free" Informally, some people use it for that. But lock-free code is not that. You may have lock-free code with locks, or lock-free code without data races, or lock-free code that can be shown to be incorrect (by your definition) yet work for the designed purpose...

pjc50 6y ago
> You may have lock-free code with locks That doesn't sound very lock-free?
chrisseaton 6y ago
> You may have lock-free code with locks I don't see how you can have that. If one process holding a lock halts then it will prevent system-wide progress, which is not allowed in the definition of 'lock-free'.
- erichocean 6y ago
  > If one process holding a lock halts then it will prevent system-wide progress As others have mentioned already, if you had code that did that, that code would not be "lock-free". Lock-free requires progress in all circumstances even in the presence of ordering primitives (what we colloquially call "locks").
  - chrisseaton 6y ago
    > if you had code that did that, that code would not be "lock-free" Are you replying to the right person? That's what I just explained to the person I was replying to. You've quoted part of my comment but left out the "...which is not allowed in the definition of 'lock-free'".
    - erichocean 6y ago
      Did I? Ha ha, looks like I was preaching to the choir…
MaxBarraclough 6y ago
> You may have lock-free code with locks That doesn't sound right. I suppose you could have locks in the trivial sense, where it never actually blocks, but I don't imagine that's what you meant. https://concurrencyfreaks.blogspot.com/2013/05/lock-free-and-wait-free-definition-and.html https://concurrencyfreaks.blogspot.com/2013/05/lock-free-and... https://www.cs.yale.edu/homes/aspnes/pinewiki/ObstructionFreedom.html https://www.cs.yale.edu/homes/aspnes/pinewiki/ObstructionFre...
- frant-hartm 6y ago
  Your first link confirms you can have locks in a multithreaded lock free algorithm - "The Lock-Free property guarantees that at least some thread is doing progress on its work" - I always thought this property should have been called deadlock free.
  - MaxBarraclough 6y ago
    That's a good point, it does seem consistent with that definition. This other blog post [0] seems to use a stricter definition of lock-free which precludes any way to schedule threads which would cause progress to cease indefinitely. That seems to be what the ConcurrencyFreaks blog refers to as Wait-free. Any experts in lock-free programming able to clarify things? [0] https://preshing.com/20120612/an-introduction-to-lock-free-programming/ https://preshing.com/20120612/an-introduction-to-lock-free-p...

pjc50 6y ago

> You may have lock-free code with locks That doesn't sound very lock-free?

chrisseaton 6y ago

> You may have lock-free code with locks I don't see how you can have that. If one process holding a lock halts then it will prevent system-wide progress, which is not allowed in the definition of 'lock-free'.

erichocean 6y ago
> If one process holding a lock halts then it will prevent system-wide progress As others have mentioned already, if you had code that did that, that code would not be "lock-free". Lock-free requires progress in all circumstances even in the presence of ordering primitives (what we colloquially call "locks").
- chrisseaton 6y ago
  > if you had code that did that, that code would not be "lock-free" Are you replying to the right person? That's what I just explained to the person I was replying to. You've quoted part of my comment but left out the "...which is not allowed in the definition of 'lock-free'".
  - erichocean 6y ago
    Did I? Ha ha, looks like I was preaching to the choir…

MaxBarraclough 6y ago

> You may have lock-free code with locks That doesn't sound right. I suppose you could have locks in the trivial sense, where it never actually blocks, but I don't imagine that's what you meant. https://concurrencyfreaks.blogspot.com/2013/05/lock-free-and-wait-free-definition-and.html https://concurrencyfreaks.blogspot.com/2013/05/lock-free-and... https://www.cs.yale.edu/homes/aspnes/pinewiki/ObstructionFreedom.html https://www.cs.yale.edu/homes/aspnes/pinewiki/ObstructionFre...

frant-hartm 6y ago
Your first link confirms you can have locks in a multithreaded lock free algorithm - "The Lock-Free property guarantees that at least some thread is doing progress on its work" - I always thought this property should have been called deadlock free.
- MaxBarraclough 6y ago
  That's a good point, it does seem consistent with that definition. This other blog post [0] seems to use a stricter definition of lock-free which precludes any way to schedule threads which would cause progress to cease indefinitely. That seems to be what the ConcurrencyFreaks blog refers to as Wait-free. Any experts in lock-free programming able to clarify things? [0] https://preshing.com/20120612/an-introduction-to-lock-free-programming/ https://preshing.com/20120612/an-introduction-to-lock-free-p...