Interlocked Singly Linked Lists (for Ben or anyone else).
in [Win32 Kernel]
|
Prev: Howto convert IPv6 from WTSClientAddress to string?
Next: Application Error, The memory could not be "read". How to debug?
From: Chris Thomasson on 14 Nov 2007 18:52 "Ben Voigt [C++ MVP]" <rbv(a)nospam.nospam> wrote in message news:O2Xn5DxJIHA.3400(a)TK2MSFTNGP03.phx.gbl... >> This explains the ABA race-condition in detail. After reading that, you >> will >> understand why its important to have some sort of solution to the ABA. >> DWCAS >> is just one way to do it. > > After thinking about it for a bit, I do not think ABA is actually a > problem. > > The only way that InterlockedCompareExchange will succeed is if the old > head pointer is what I have stored in the next-node pointer of the new > head, therefore I have correctly inserted a new node regardless of what > manipulations took place in the meantime. > > Please take a look at my queue implementation and let me know if you see > any problem (I realize it isn't truely lock-free until I replace the > allocator): > [...] Good news! ;^) From what I could gather at the first glance is that you have solved the ABA problem by using the pattern described here: http://groups.google.ca/group/comp.programming.threads/msg/49a5db082507cb87 http://groups.google.ca/group/comp.programming.threads/msg/a359bfb41c68b98b http://groups.google.ca/group/comp.programming.threads/browse_frm/thread/fafe5f528700407 If you stick to that, you will be able to deallocate nodes and not have to worry about it. BTW, when you do it this way, the Get function is not only lock-free... Its wait-free. That's a nice property to strive for sometimes. As long as your method tries to cut down on overheads. Humm... Well, FWIW, if your into low-overhead queuing, I suggest you skim through the following message and follow links: http://groups.google.com/group/comp.arch/msg/a7501814f19731cd What do you think about using distributed message passing algorithms w/ work-stealing scheme for natural auto-balance? I have a library I can license... Actually, never mind that. ;^)
From: m on 14 Nov 2007 20:43 BTW: This form is not a blog - you should really try to consolidate your posts ;) As you say: for LIFO or unordered lists, SCAS is sufficient in the general case. For FIFO or binary data structures, an MCAS is required (DCAS or TCAS). Under certain conditions a control variable can be used with CAS to generate FIFO � the assumption being that fewer than 2^32 (or 2^64) operations are performed on the list between the time that the control variable is checked and when the CAS is executed. Additionally, on windows, FIFO & LIFO are mostly useless for multiple producer / multiple consumer modes because the strict ordering that they imply is lost when thread pre-emption occurs. So other than the vague benefit of LIFO on memory residence (recently used pages are more likely to be in the working set), lock-free ordered lists should be avoided. "Chris Thomasson" <cristom(a)comcast.net> wrote in message news:I5-dnZi55r10FabanZ2dnUVZ_judnZ2d(a)comcast.com... > "Ben Voigt [C++ MVP]" <rbv(a)nospam.nospam> wrote in message > news:O2Xn5DxJIHA.3400(a)TK2MSFTNGP03.phx.gbl... >>> This explains the ABA race-condition in detail. After reading that, you >>> will >>> understand why its important to have some sort of solution to the ABA. >>> DWCAS >>> is just one way to do it. >> >> After thinking about it for a bit, I do not think ABA is actually a >> problem. >> >> The only way that InterlockedCompareExchange will succeed is if the old >> head pointer is what I have stored in the next-node pointer of the new >> head, therefore I have correctly inserted a new node regardless of what >> manipulations took place in the meantime. >> >> Please take a look at my queue implementation and let me know if you see >> any problem (I realize it isn't truely lock-free until I replace the >> allocator): >> > [...] > > Good news! ;^) > > > From what I could gather at the first glance is that you have solved the > ABA problem by using the pattern described here: > > http://groups.google.ca/group/comp.programming.threads/msg/49a5db082507cb87 > > http://groups.google.ca/group/comp.programming.threads/msg/a359bfb41c68b98b > > http://groups.google.ca/group/comp.programming.threads/browse_frm/thread/fafe5f528700407 > > > If you stick to that, you will be able to deallocate nodes and not have to > worry about it. BTW, when you do it this way, the Get function is not only > lock-free... Its wait-free. That's a nice property to strive for > sometimes. As long as your method tries to cut down on overheads. > > Humm... Well, FWIW, if your into low-overhead queuing, I suggest you skim > through the following message and follow links: > > http://groups.google.com/group/comp.arch/msg/a7501814f19731cd > > > What do you think about using distributed message passing algorithms w/ > work-stealing scheme for natural auto-balance? I have a library I can > license... Actually, never mind that. > > ;^)
From: Chris Thomasson on 14 Nov 2007 21:05 "m" <m(a)b.c> wrote in message news:eFgEsjyJIHA.4228(a)TK2MSFTNGP02.phx.gbl... > BTW: This form is not a blog - you should really try to consolidate your > posts ;) > > > > As you say: for LIFO or unordered lists, SCAS is sufficient in the general > case. Single CAS wrt LIFO is only good for the method that Ben uses: http://groups.google.ca/group/comp.programming.threads/msg/49a5db082507cb87 http://groups.google.ca/group/comp.programming.threads/msg/a359bfb41c68b98b http://groups.google.ca/group/comp.programming.threads/browse_frm/thread/fafe5f528700407 > For FIFO or binary data structures, an MCAS is required (DCAS or TCAS). > Under certain conditions a control variable can be used with CAS to > generate FIFO � You can get FIFO with LIFO using the trick described above links. The control variable is what I call the anchor. The anchor structure is opaque and ambiguous. You can have an anchor for a LIFO/FIFO/Whatever... > the assumption being that fewer than 2^32 (or 2^64) operations are > performed on the list between the time that the control variable is > checked and when the CAS is executed. Yup. The montontnic ABA counter can roll... > Additionally, on windows, FIFO & LIFO are mostly useless for multiple > producer / multiple consumer modes because the strict ordering that they > imply is lost when thread pre-emption occurs. Sure. > So other than the vague benefit of LIFO on memory residence (recently used > pages are more likely to be in the working set), lock-free ordered lists > should be avoided. > [...] If your design cannot tolerate an algorithm, don't use it. I agree.
From: Chris Thomasson on 14 Nov 2007 21:09 "Chris Thomasson" <cristom(a)comcast.net> wrote in message news:T7Kdnd74edSNNabanZ2dnUVZ_sqinZ2d(a)comcast.com... > "m" <m(a)b.c> wrote in message news:eFgEsjyJIHA.4228(a)TK2MSFTNGP02.phx.gbl... >> BTW: This form is not a blog - you should really try to consolidate your >> posts ;) >> >> >> >> As you say: for LIFO or unordered lists, SCAS is sufficient in the >> general case. > > Single CAS wrt LIFO is only good for the method that Ben uses: > > http://groups.google.ca/group/comp.programming.threads/msg/49a5db082507cb87 > > http://groups.google.ca/group/comp.programming.threads/msg/a359bfb41c68b98b > > http://groups.google.ca/group/comp.programming.threads/browse_frm/thread/fafe5f528700407 > > > > > >> For FIFO or binary data structures, an MCAS is required (DCAS or TCAS). >> Under certain conditions a control variable can be used with CAS to >> generate FIFO � Humm... Are you stamping the nodes with the sequence number of the monotonic aba counter at time of push and/or pop? Are you sorting them in ascending order or something?
From: Chris Thomasson on 14 Nov 2007 21:22
> Humm... Are you stamping the nodes with the sequence number of the > monotonic aba counter at time of push and/or pop? Are you sorting them in > ascending order or something? I meant to say descending order as ascending would be LIFO. |