On Saturday, August 25, 2018 at 8:18:53 AM UTC-7, Peter Veentjer wrote: > > Hi Gil, > > thanks for your answer. > > However it still feels a bit like 'it works because it does' (or my skull > is just too thick). > > So what prevents a cpu from perpetually being denied to execute the LOCK > XADD? So imagine there are 2 cpu's, both executing a LOCK XADD in a loop, > what prevents that one of the cpu's isn't perpetually being starved from > its resource. >
What prevents it is the fact that if this was possible, you've just described a trivial way for you to crash any server and any laptop on earth from user-mode code. One of the jobs of the hardware designers is to make it impossible for you to do that, and they've usually done that job to an ok enough level on the systems we run on (assuming we haven't read anything in the news about "how to bring all of AWS down from a laptop"). > And even if it isn't perpetual, what guarantees that the CPU completes in > a bounded number of steps? > > > > On Saturday, August 25, 2018 at 9:39:13 AM UTC+3, Gil Tene wrote: >> >> Wait-free, Lock-free, and Obstruction-free are well defined things. They >> are all non-blocking, such that suspended threads cannot indefinitely >> prevent all others from making progress, but they differ in the forward >> progress expectations of individual threads. The "Non-blocking >> algorithm" wikipedia entry >> <https://en.wikipedia.org/wiki/Non-blocking_algorithm#cite_note-wf-queue-16> >> does a fair job of explaining what each means. It is forward progress in a >> bounded number of steps, rather than "fairness", that is key. You can be >> extremely unfair (as in making forward progress at 1,000,000,000:1 ratios) >> and wait-free at the same time. >> >> There is a difference between the wait-free/lock-free classification of >> an operation/instruction and the classification of a mechanism/algorithm >> using that operation/instruction... >> >> Both the LOCK XADD operation and LOCK CAS operations are wait free. There >> is nothing any other processor can do to prevent your processor from making >> forward progress and eventually (in a bound number of steps) executing >> either instruction. In fact, [at the very least] all user-mode x86 CPU >> instructions are trivially wait free, otherwise very bad things could be >> done by user-mode code... >> >> The key difference between a LOCK XADD and a LOCK CAS is that the LOCK >> XADD will actually and unconditionally force a visible change to the shared >> memory state in a way that no other processor can prevent, while the shared >> memory effect of a LOCK CAS operation is a conditional, and will only occur >> if the compare shows that the expected value and the memory value are the >> same. Simple (but by no means all) uses of CAS often perform retry loops in >> lock-free, but not wait-free, mechanisms. >> >> It is easy to see how one can use LOCK XADD operations to build wait-free >> mechanisms. E.g. implementing a wait-free atomic counter using XADD is >> trivial. It is similarly useful in more complicated synchronization >> primitives, like e.g. my WriterReaderPhaser >> <http://stuff-gil-says.blogspot.com/2014/11/writerreaderphaser-story-about-new.html>, >> >> which is wait free on architectures that support atomic increment >> operations, but (in my current implementation) is only lock free on >> architectures that force us to resort to a CAS.. It is somewhat harder to >> construct wait-free mechanisms using LOCK CAS, but it is by no means not >> impossible, and usually just means some extra complexity and spending some >> more memory per concurrent thread or cpu. e.g. see "Wait-Free Queues >> With Multiple Enqueuers and Dequeuers" >> <http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf>, where >> wait free queues are implemented using CAS constructs. >> >> On Friday, August 24, 2018 at 10:00:22 PM UTC-7, Peter Veentjer wrote: >>> >>> I'm polishing up my lock free knowledge and one question keeps on >>> bugging me. >>> >>> The question is about the LOCK XADD and why it is considered to be wait >>> free. >>> >>> AFAIK for wait freedom there needs to be some fairness. >>> >>> So image a concurrent counter using a spin on a cas to increment a >>> counter, then at least 1 thread wins and makes progress. Therefor this >>> implementation is lock free. It isn't wait free because some thread could >>> be spinning without bound. The problem here is that there is no fairness. >>> >>> Now imagine this counter would be implemented using a LOCK XADD and >>> therefor there is no need for a loop. What is guaranteeing that every >>> thread is going to make progress in a bound number of steps? E.g. could it >>> happen that one thread is continuously denied exclusive access to the >>> memory and therefor it won't complete in a bound number of steps? Or do the >>> request get stored in some kind of list and the requests are processed in >>> this order? This order would provide fairness and then it will be wait free. >>> >>> I have been looking at the Intel documentation of LOCK XADD; but it >>> remains unclear. >>> >> -- You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group. To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
