Atomic Instruction

Question

What do you mean by Atomic instructions?

How does the following become Atomic?

TestAndSet

int TestAndSet(int *x){
   register int temp = *x;
   *x = 1;
   return temp;
}

From a software perspective, if one does not want to use non-blocking synchronization primitives, how can one ensure Atomicity of instruction? is it possible only at Hardware or some assembly level directive optimization can be used?

Answer 1

Atomicity can only be guaranteed by the OS. The OS uses the underlying processor features to achieve this.

So creating your own testandset function is impossible. (Although I'm not sure if one could use an inline asm snippet, and use the testandset mnemonic directly (Could be that this statement can only be done with OS priviliges))

EDIT: According to the comments below this post, making your own 'bittestandset' function using an ASM directive directly is possible (on intel x86). However, if these tricks also work on other processors is not clear.

I stand by my point: if You want to do atmoic things, use the OS functions and don't do it yourself

Answer 2

Some machine instructions are intrinsically atomic - for example, reading and writing properly aligned values of the native processor word size is atomic on many architectures.

This means that hardware interrupts, other processors and hyper-threads cannot interrupt the read or store and read or write a partial value to the same location.

More complicated things such as reading and writing together atomically can be achieved by explicit atomic machine instructions e.g. LOCK CMPXCHG on x86.

Locking and other high-level constructs are built on these atomic primitives, which typically only guard a single processor word.

Some clever concurrent algorithms can be built using just the reading and writing of pointers e.g. in linked lists shared between a single reader and writer, or with effort, multiple readers and writers.

Answer 3

Atomicity is a key concept when you have any form of parallel processing (including different applications cooperating or sharing data) that includes shared resources.

The problem is well illustrated with an example. Let's say you have two programs that want to create a file but only if the file doesn't already exists. Any of the two program can create the file at any point in time.

If you do (I'll use C since it's what's in your example):

 ...
 f = fopen ("SYNCFILE","r");
 if (f == NULL) {
   f = fopen ("SYNCFILE","w");
 }
 ...

you can't be sure that the other program hasn't created the file between your open for read and your open for write.

There's no way you can do this on your own, you need help from the operating system, that usually provide syncronization primitives for this purpose, or another mechanism that is guaranteed to be atomic (for example a relational database where the lock operation is atomic, or a lower level mechanism like processors "test and set" instructions).

Answer 4

Atomic comes from the Greek ἄτομος (atomos) which means "indivisible". (Caveat: I don't speak Greek, so maybe it's really something else, but most English speakers citing etymologies interpret it this way. :-)

In computing, this means that the operation, well, happens. There isn't any intermediate state that's visible before it completes. So if your CPU gets interrupted to service hardware (IRQ), or if another CPU is reading the same memory, it doesn't affect the result, and these other operations will observe it as either completed or not started.

As an example... let's say you wanted to set a variable to something, but only if it has not been set before. You might be inclined to do this:

if (foo == 0)
{
   foo = some_function();
}

But what if this is run in parallel? It could be that the program will fetch foo, see it as zero, meanwhile thread 2 comes along and does the same thing and sets the value to something. Back in the original thread, the code still thinks foo is zero, and the variable gets assigned twice.

For cases like this, the CPU provides some instructions that can do the comparison and the conditional assignment as an atomic entity. Hence, test-and-set, compare-and-swap, and load-linked/store-conditional. You can use these to implement locks (your OS and your C library has done this.) Or you can write one-off algorithms that rely on the primitives to do something. (There's cool stuff to be done here, but most mere mortals avoid this for fear of getting it wrong.)