Why is this atomic? Or on the opposite, who do we implement it differently so that it is not atomic?

The code for atomicCAS on this slide is just a logical description. AtomicCAS is not a function in C, I'm just using C on the slide to define what the operation does. Think about it as an intrinsic.

The implementation of atomic_min, however, is just C code that successfully executes an atomic min operation given only the atomicCAS intrinsic.

Quick check: can you provide an implementation of atomicCAS in x86 using atomic cmpxcng?

We talked about in class how if the return value of atomicCAS was equal to compare then the CAS succeeded. This is because you can see in the C impl of CAS, we set *addr = val only if old (the retval of atomicCAS) is equal to compare.

I think atomic_inc can be implemented almost identically to min, except wherever you see a min(old, x), replace it with a old + x.

I think lock can be implemented like so: lock(int * addr){ while(!atomicCAS(addr, 0, 1)) ; } This works (assuming addr represents the lock, 0 is free, 1 is locked) in a very similar way to the test and set lock. Since we set compare to be equal to 0, the atomicCAS sets addr to be equal to 1 if it was previously 0. Otherwise, if addr were to be 1, it sets addr to be 1. We do this in a while loop until atomicCAS returns 0 (i.e. atomicCAS() == compare) so that we block until the lock is acquired.

I'm curious as to whether this suffers from the same cache issues as the test-and-set lock and if a similar modification to the test-and-test-and-set lock would be useful here. I tentatively think not because it seems like the CAS instruction doesn't perform a write if old != compare?

"can you provide an implementation of atomicCAS in x86 using atomic cmpxcng?" Not sure if I'm doing it right:

load EAX, a // load value of a into EAX register lock cmpxchg x, b // compare a with what's stored in x, if they're the same, put b into memory //ZF stores the return value

Is the atomic_min function really correct here? It doesn't have a return statement. So doesn't always return 0?

@blipblop It doesn't return anything but it puts the min value into memory.

put it is true that the return value of atomic_min() on this slide should be void.

Or, it is common for atomicXXX() operations to return old. For example, an example you've probably used in Assignment 2.

atomic<int> myCounter;
int nextTask = myCounter++;

Implementing atomic fetch-and-op is actually very similar (although more limited in scope) to transactional memory. The philosophy in both is that you go ahead and do whatever you need to do as if you had not a worry in the world, and only when it comes time to write your result back to memory, you check to see if there were any conflicts with other threads. If there were, then you brush yourself off and start over.