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: Alexander Grigoriev on 17 Nov 2007 17:46 "Chris Thomasson" <cristom(a)comcast.net> wrote in message news:BfKdnfd2btBLv6LanZ2dnUVZ_vGinZ2d(a)comcast.com... > "Vladimir Petter [MSFT]" <vladp72(a)hotmail.com> wrote in message > news:u$CatAOKIHA.5400(a)TK2MSFTNGP04.phx.gbl... >> You can find more info on this here http://www.alex-ionescu.com/?p=50 >> Vladimir Petter. [microsoft] > > > Thanks for that. Humm... So, Windows 64-bit running on x86-64 systems that > lack CMPXCHG16B instruction uses only 9-bits for an ABA counter; I think > that may be a bit dangerous. That counter will be rolling over quite > frequently under load... Humm: > > http://groups.google.com/group/comp.programming.threads/browse_frm/thread/133f764f1bc0c9f4 > > > Any thoughts? Counter could roll over, but probability of hitting the same is astronomically low. If there is too much ABA contentions, counter will simply change forward, but not by 512 at once.
From: Chris Thomasson on 17 Nov 2007 23:53 "Chris Thomasson" <cristom(a)comcast.net> wrote in message news:6budnUf11cP9haDanZ2dnUVZ_saknZ2d(a)comcast.com... > "Ben Voigt [C++ MVP]" <rbv(a)nospam.nospam> wrote in message > news:uwEcTw5JIHA.3820(a)TK2MSFTNGP03.phx.gbl... >> >> "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... > [...] >>>> >>>> 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! ;^) > [...] > >> Thanks for the review. I was pretty sure it was correct but it's very >> nice to have concurrence from an expert. > > You welcome. I think your SQueue class is sound wrt the overall concerns > of the ABA problem in general. I also think that the code correctly > address the concerns of deallocating nodes from lock-free data-structures. > You have a performance enhancement on the SQueue<T>::Get() function > because its 100% wait-free as long as the hardware that Windows happens to > be running on supports an atomic swap instruction; Intel does. SPARC used > to support the SWAP instruction; they depreciated it, and delegated its > functionally over to the CAS instruction on 32-bit systems, and CASX on > 64-bit systems. http://groups.google.com/group/comp.arch/msg/04cb5e2ca2a7e19a Damn!
From: Pops on 19 Nov 2007 02:54 Hi Ben, I hope you enjoyed your weekend. :-) See inline comments. Ben Voigt [C++ MVP] wrote: > Did you try a multiple writer scenario, or reduced waits > where you could have some contention? Yes. It was pretty much all the expected issues and results wrt synchronizing and/or controlling queuing and dequeuing rates, including using the proper methods for the design in hand, i.e., pop vs a flush. > Especially don't use Sleep to simulate processing time, > use a loop with a volatile variable to make sure the compiler > doesn't eliminate it. Not sure what you are thinking at the time you wrote this, but it all depends on what you are simulating. I won't attempt to elaborate too deeply but just in case it was misunderstood, I did not intend to imply the parameter READER_PROCESS_DELAY "Simulating Processing Time" to exclusively mean CPU time, if that was you were thinking? To me, the logic to simulate processing time implies doing "things" that emulates as near as possible real world behavior of your data handling design needs which may includes considerations such as HW related interrupts, natural time slicing pre-emptions, as well as CPU time, etc, all to create situations which will help find contention, deadlocks, timing, synchronization, optimization issues, etc. I use various simulation techniques, including combinations of these techniques: sleeps, yields/pokes, software-based timers, math computations, high memory loads, file I/O, RPC calls (which is critically important for us, because this is where most of bottlenecks might occur), for GUI relate issues, posting or sending messages, message handlers with simulator delays, etc. That said, I'm curious. I have various methods for software timers. Can you provide an example of one using volatile? If we referring to the same thing, I wasn't sure if you were thinking HW based timers vs SW based timers. Thanks -- HLS
From: Chris Thomasson on 22 Nov 2007 01:11 "Alexander Grigoriev" <alegr(a)earthlink.net> wrote in message news:%23c$YxuWKIHA.5764(a)TK2MSFTNGP06.phx.gbl... > > "Chris Thomasson" <cristom(a)comcast.net> wrote in message > news:BfKdnfd2btBLv6LanZ2dnUVZ_vGinZ2d(a)comcast.com... >> "Vladimir Petter [MSFT]" <vladp72(a)hotmail.com> wrote in message >> news:u$CatAOKIHA.5400(a)TK2MSFTNGP04.phx.gbl... >>> You can find more info on this here http://www.alex-ionescu.com/?p=50 >>> Vladimir Petter. [microsoft] >> >> >> Thanks for that. Humm... So, Windows 64-bit running on x86-64 systems >> that lack CMPXCHG16B instruction uses only 9-bits for an ABA counter; I >> think that may be a bit dangerous. That counter will be rolling over >> quite frequently under load... Humm: >> >> http://groups.google.com/group/comp.programming.threads/browse_frm/thread/133f764f1bc0c9f4 >> >> >> Any thoughts? > > Counter could roll over, but probability of hitting the same is > astronomically low. If there is too much ABA contentions, counter will > simply change forward, but not by 512 at once. Its good to keep in mind that we are talking about solutions that are analogous to managed race-conditions in their essence. I think that PDR is good method to use wrt addressing the ABA problem in general. The depth of the counter is directly proportional to the "chance" of the race-condition not raising its ugly head right in the middle of a critical operations.
From: Chris Thomasson on 22 Nov 2007 01:41
"Alexander Grigoriev" <alegr(a)earthlink.net> wrote in message news:%23c$YxuWKIHA.5764(a)TK2MSFTNGP06.phx.gbl... > > "Chris Thomasson" <cristom(a)comcast.net> wrote in message > news:BfKdnfd2btBLv6LanZ2dnUVZ_vGinZ2d(a)comcast.com... >> "Vladimir Petter [MSFT]" <vladp72(a)hotmail.com> wrote in message >> news:u$CatAOKIHA.5400(a)TK2MSFTNGP04.phx.gbl... >>> You can find more info on this here http://www.alex-ionescu.com/?p=50 >>> Vladimir Petter. [microsoft] >> >> >> Thanks for that. Humm... So, Windows 64-bit running on x86-64 systems >> that lack CMPXCHG16B instruction uses only 9-bits for an ABA counter; I >> think that may be a bit dangerous. That counter will be rolling over >> quite frequently under load... Humm: >> >> http://groups.google.com/group/comp.programming.threads/browse_frm/thread/133f764f1bc0c9f4 >> >> >> Any thoughts? > > Counter could roll over, but probability of hitting the same is > astronomically low. If there is too much ABA contentions, counter will > simply change forward, but not by 512 at once. The augment the algorithm with a "counter" (e.g., counter inc'd for every push, and dec for every pop). This is not a monotonic counter, therefore its not effective for solving ABA in general. You either need to manage memory and solve ABA externally, or solve it within the state of a specific algorithm. |