1

According to Examples/Illustration of Wait-free And Lock-free Algorithms: all wait-free programs are lock-free, this is obvisous by the definition of lock-free and wait-free. But I can't think of an algorihtm that is lock-free but not wait-free, are there any examples to illustrate it?

konchy
  • 573
  • 5
  • 16
  • 2
    Many things involving CAS retry loops are good examples. When one thread makes progress, the others have a CAS failure if they were trying to modify the same object. Of course, counting time or cycles vs. instructions means that software retry loops vs. hardware waiting for MESI ownership of a cache line to run a "wait free" `lock inc` instruction to increment a shared variable isn't necessarily a big difference. (see [Are X86 atomic RMW instructions wait free](https://stackoverflow.com/q/61744469)) – Peter Cordes Aug 08 '22 at 07:18
  • [Anything in std::atomic is wait-free?](https://stackoverflow.com/q/61849972) has some further discussion of why C++ only guarantees lock-freedom, not wait-freedom. e.g. because of machine that need LL/SC retry loops to implement atomic primitives like CAS or fetch_add. – Peter Cordes Aug 08 '22 at 07:22
  • Related: [What is an example of obstruction-free algorithm that is not lock-free?](https://stackoverflow.com/q/46489805) is a different distinction. – Peter Cordes Aug 08 '22 at 07:24

0 Answers0