Interlocked operations don't solve everything

re: Inerlocked operations don't solve everything

Chris — Wed, 15 Sep 2004 14:11:00 GMT

Shouldn't that while condition be "!= lOriginal"? I thought InterlockedCompareExchange returned the initial value of the destination, and we want to keep looping if the result wasn't what we expected.

re: Inerlocked operations don't solve everything

Raymond Chen — Wed, 15 Sep 2004 14:35:00 GMT

D'oh! You're right.

re: Inerlocked operations don't solve everything

anon — Wed, 15 Sep 2004 14:42:00 GMT

Spelled Interlocked wrong in title:
>Inerlocked< operations don't solve everything

re: Interlocked operations don't solve everything

jeffdav — Wed, 15 Sep 2004 17:23:00 GMT

I came across someone who really did not understand InterlockedIncrement() once. I had to remove the following:

/* Synchronization */
#define InterlockedIncrement(plong) (++(*(plong)))
#define InterlockedDecrement(plong) (--(*(plong)))

I was sad.

re: Interlocked operations don't solve everything

Seth McCarus — Wed, 15 Sep 2004 17:32:00 GMT

Okay, two simple and probably stupid questions:

Why is there not InterlockedAssign function? (I guess InterlockedExchange could be used there, but still...)

How can one iterate a list created with InitializeSListHead?

re: Interlocked operations don't solve everything

Raymond Chen — Wed, 15 Sep 2004 17:45:00 GMT

1. Please read the linked page that opens the article.
2. You can't walk a linked list atomically.

re: Interlocked operations don't solve everything

Seth McCarus — Wed, 15 Sep 2004 18:04:00 GMT

What about on a multiprocessor system? If two CPUs try to write to the same memory location "simultaneously," would there not be problems?

Maybe synchronization is performed on a hardware level??

re: Interlocked operations don't solve everything

Johan — Wed, 15 Sep 2004 18:06:00 GMT

It's not clear to me what the intended memory access/ordering semantics of the plain (non-*Acquire/*Release) Interlocked* operations are. The documentation says nothing about it, but there's an IA64-specific note indicating an associated *full* memory barrier. Is that the intended semantics? Or was that fence just added to avoid breaking all the existing code which assumes an x86-like memory model?

re: Interlocked operations don't solve everything

Jordan Russell — Wed, 15 Sep 2004 18:09:00 GMT

An "InterlockedAssign" function would be handy because while writes to aligned 32-bit variables are always atomic, they're not always _ordered_ on non-x86 platforms as explained at <http://msdn.microsoft.com/library/en-us/dllproc/base/synchronization_and_multiprocessor_issues.asp>. That article suggests using InterlockedExchange instead of a direct assignment, but that seems like overkill on platforms where writes are always ordered, e.g. x86.

re: Interlocked operations don't solve everything

Pavel Lebedinsky — Wed, 15 Sep 2004 21:03:00 GMT

The MSDN article that Jordan referred to is not quite correct, by the way:

http://groups.google.com/groups?selm=3f79e7ee%241%40news.microsoft.com&output=gplain

Win32 should have provided a memory barrier macro/intrinsic that is guaranteed to be respected by both the compiler and hardware. As far as I know, there's still no such thing (there are various bits and pieces like the MemoryBarrier macro but nothing that prevents both CPU and compiler reordering).

re: Interlocked operations don't solve everything

foxyshadis — Wed, 15 Sep 2004 21:11:00 GMT

Interestingly, one of the best explanations of ABA google came up with was in this blog.

http://weblogs.asp.net/oldnewthing/archive/2004/08/17/215682.aspx#217600

re: Interlocked operations don't solve everything

lowercase josh — Thu, 16 Sep 2004 10:12:00 GMT

If I'm not mistaken, what you have to lock for the critical section to work is the data, not the code. If all access to that data goes through the same critical section, that first InterlockedMultiply would work correctly. To me, "critical section" seems to imply a "section" of code, but you nearly always want to lock the data. :/

re: Interlocked operations don't solve everything

Mike — Thu, 16 Sep 2004 13:00:00 GMT

Why are they called the interlocked functions rather than the atomic functions? ie AtomicIncrement etc. That would be a slightly more intuitive name (albiet, doesn't sound as cool :)

Seth: yes the sync is done with hardware.

InterlockedCompareExchange() is some assembly like this:

lock cmpxchg a, b

The lock prefix causes the CPU to perform a "bus assert" which basically locks the bus. It prevents other processors from accessing memory while the bus is held. At least this is my understanding.

After a bus assert I suppose the CPU clears the dcache but now I'm just guessing :)

re: Interlocked operations don't solve everything

MikeF — Thu, 16 Sep 2004 13:38:00 GMT

Possibly silly question: What is the "critical section bottleneck", and why is looping over a cmpxchg better?

My understanding is that a pure critical section approach (a) lets the OS sleep the blocked thread, and (b) wastes less time than the cmpxchg loop anyway.

I'm almost certainly missing something here but I can't see what. Is the overhead on critical sections particularly big?

re: Interlocked operations don't solve everything

Seth McCarus — Thu, 16 Sep 2004 14:11:00 GMT

Thanks for your answers, Raymond and Mike.

re: Interlocked operations don't solve everything

Ben Hutchings — Thu, 16 Sep 2004 15:10:00 GMT

Mike wrote: "After a bus assert I suppose the CPU clears the dcache but now I'm just guessing :)"

That would take far too long. Actually processors in SMP systems obey a cache coherency protocol which ensures that memory that's been modified in cache but not yet written back is forwarded from processor to processor (possibly by writing it back to memory first) and memory that's about to be modified by one processor is invalidated in the caches of the others.

The problems of memory coherence are not due to caching but to reordering of instructions in the processor core and of memory operations issued by the processor core to its cache(s).

re: Interlocked operations don't solve everything

Trent Glascock — Thu, 16 Sep 2004 19:35:00 GMT

MikeF: Waiting on a critical section is an expensive operation. So expensive that on multi-processor systems you can elect to "spin" before waiting on the critical section. The code in the original post could loop through a hundred iterations and still come out ahead of waiting on a busy critical section.

See InitializeCriticalSectionAndSpinCount

http://msdn.microsoft.com/library/en-us/dllproc/base/initializecriticalsectionandspincount.asp