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 15 Nov 2007 12:23 "Pops" <dude(a)nospamnospamnospam.com> wrote in message news:eUNbMM4JIHA.4272(a)TK2MSFTNGP05.phx.gbl... > Joe Seigh wrote: [...] > That said, this Interlocked Singly List API seems to be useful but it > still seems to require a lock-sync when using its FLUSH function, not for > to be confused a PURGE consideration. To me, a FLUSH is a purge if the > data is not available or saved during the flush. The reason you don't need an explicit mutual exclusion lock is because you are using instructions that atomically modify the entire list anchor in one single atomic operation. > > In this case, it provides a pointer to a list. To me, in order to be > thread safe, the function has to be make a COPY of the data and provide a > new pointer list, then it can safely purge the internal list it is > maintaining. [...] You do not need COW semantics' wrt flushing the contents of a lock-free LIFO. You simply SWAP the head of the list with NULL, and that's it.
From: m on 15 Nov 2007 13:31 Yes I am extending the discussion to include all kinds of data structures besides queues; and yes there are various ways to protect them. No I don�t really want to discuss them in detail, I just wanted to put something out there to see if I could tweak someone�s interest ;) Thread pre-emption is important on all pre-emptive multi-tasking operating systems regardless of how many CPUs are present in the system. The importance of this consideration lies in the fact that between any two instructions executed by thread A, thread B may have executed a large number of instructions (either on this CPU or on another one) or none at all. The reason this is, implicitly, important is that, even though one could use a lock-free algorithm for nearly anything, they are specifically designed for HPC scenarios with multiple produces & multiple consumers (or more generally, multiple modifiers). Lock-free is not a forward progress guarantee. Lock-free, a misnomer, is an idiom in which software locks are replaced with hardware locks because they are, presumably, more efficient. This efficiently is achieved, if by nothing else, by being smaller (one instruction vs. hundreds) and by avoiding interaction with the OS scheduler. Lock-free algorithms must provide a forward progress guarantee, otherwise they would cease to function under contention, but that guarantee, in and of itself, does not make an algorithm lock-free and hence does not define the idiom. "Joe Seigh" <jseigh_01(a)xemaps.com> wrote in message news:JUV_i.7973$WM.837(a)trndny05... >m wrote: >> 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. >> >> > Lock-free is a forward progress guarantee. It has no effect on semantics. > You shouldn't be able to tell the difference between lock-free and locked > queues. The observed order of dequeues will be the same order of any > corresponding enqueues that were observed. This is for queues which is > what are inferred when you use the term producer/consumer. If you're > talking > about performing arbitrary functions on an arbitrary collection, e.g. > ordered list, then they're really just the same as an arbitrary data > structure where the operations on them consist of multiple accesses on > the data. You need some form of synchronization to coordinate those > accesses. This could be lock based, MCAS, or STM. > > Thread preemption was only a significant distinction when stuff ran on > single processor systems and only one thread could run at a time. That's > no longer true on multi-cores. > > > > -- > Joe Seigh > > When you get lemons, you make lemonade. > When you get hardware, you make software.
From: Chris Thomasson on 15 Nov 2007 14:37 "m" <m(a)b.c> wrote in message news:uCb9BX7JIHA.3916(a)TK2MSFTNGP02.phx.gbl... [...] > > > Lock-free is not a forward progress guarantee. Lock-free, a misnomer, is > an idiom in which software locks are replaced with hardware locks because > they are, presumably, more efficient. This efficiently is achieved, if by > nothing else, by being smaller (one instruction vs. hundreds) and by > avoiding interaction with the OS scheduler. Lock-free algorithms must > provide a forward progress guarantee, otherwise they would cease to > function under contention, but that guarantee, in and of itself, does not > make an algorithm lock-free and hence does not define the idiom. [...] I think you should look at the differences between wait-free and lock-free. Wait-free means that the operation will complete within a finite number of steps, in other words, there are no loops. Lock-free implies conditional looping. You can get into live-lock under certain scenarios. For instance, a live-lock can ensue if the reservation make by a load-linked is constantly invalided before the store-conditional get to execute. A PowerPC manual mentions some of this wrt false-sharing messing with the reservation. That's why STM is so prove to live-lock... STM is like LL/SC with huge reservation granules.
From: Chris Thomasson on 15 Nov 2007 15:14 One could theoretically open themselves up to live-lock conditions if they did not take this into consideration when implementing certain lock-free algorithms on PPC. For instance, if the anchor of a lock-free LIFO was not the size of a cache-line, and was not aligned on a cache-line boundary you could get "false-sharing" on the anchor. I don't have much experience with PPC, but it seems that false-sharing could break reservations on the anchor and adversely affect forward progress, and might cause live-lock like conditions...
From: m on 15 Nov 2007 15:40
Lock-free & wait-free are independent idioms which, in certain algorithms, can overlap. Except that lock-free doesn�t imply conditional looping, this is an attribute of many algorithms that are lock-free not a defining property of the idiom, your definitions are reasonable; so what am I missing? The fact that on certain architectures, false-sharing can adversely affect performance is a consideration in implementation and algorithm choice. Specifically, don�t choose an algorithm that is hard to implement or performs badly on your target architecture ;) "Chris Thomasson" <cristom(a)comcast.net> wrote in message news:f7OdndviL--1OqHanZ2dnUVZ_qmlnZ2d(a)comcast.com... > One could theoretically open themselves up to live-lock conditions if they > did not take this into consideration when implementing certain lock-free > algorithms on PPC. For instance, if the anchor of a lock-free LIFO was not > the size of a cache-line, and was not aligned on a cache-line boundary you > could get "false-sharing" on the anchor. I don't have much experience with > PPC, but it seems that false-sharing could break reservations on the > anchor > and adversely affect forward progress, and might cause live-lock like > conditions... |