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 22 Nov 2007 09:13 The structure we're discussing has a separate 16-bit depth count and 9 bit sequence count. Sequence count increases monotonically. "Chris Thomasson" <cristom(a)comcast.net> wrote in message news:98OdnXUQ0LWfvtjanZ2dnUVZ_jmdnZ2d(a)comcast.com... >>> >>> >>> 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.
From: Chris Thomasson on 22 Nov 2007 18:35 "Alexander Grigoriev" <alegr(a)earthlink.net> wrote in message news:%23HpYWHRLIHA.3848(a)TK2MSFTNGP05.phx.gbl... > The structure we're discussing has a separate 16-bit depth count and 9 bit > sequence count. Sequence count increases monotonically. Right. So effectively its only a 9-bit ABA counter. The aba problem can trip up the 16-bit depth count by popping and pushing the same item. depth of 1, changed to depth of 0, and back to 1 again; ABA...
From: Alexander Grigoriev on 22 Nov 2007 22:17 This is what sequence number is for. "Chris Thomasson" <cristom(a)comcast.net> wrote in message news:F-ydnQxWxLBYjdvanZ2dnUVZ_qiinZ2d(a)comcast.com... > "Alexander Grigoriev" <alegr(a)earthlink.net> wrote in message > news:%23HpYWHRLIHA.3848(a)TK2MSFTNGP05.phx.gbl... >> The structure we're discussing has a separate 16-bit depth count and 9 >> bit sequence count. Sequence count increases monotonically. > > Right. So effectively its only a 9-bit ABA counter. The aba problem can > trip up the 16-bit depth count by popping and pushing the same item. depth > of 1, changed to depth of 0, and back to 1 again; ABA...
From: Chris Thomasson on 22 Nov 2007 22:50
"Alexander Grigoriev" <alegr(a)earthlink.net> wrote in message news:OGWKX%23XLIHA.4272(a)TK2MSFTNGP05.phx.gbl... > This is what sequence number is for. [...] 9 bit sequence number is small. Back when IBM did things the processors were not as fast as they are now... |