how can I convert non atomic operation to atomic

Question

I am trying to understand atomic and non atomic operations.With respect to Operating System and also with respect to C. As per the wikipedia page here

Consider a simple counter which different processes can increment.
Non-atomic

The naive, non-atomic implementation:
reads the value in the memory location;
adds one to the value;
writes the new value back into the memory location.

Now, imagine two processes are running incrementing a single, shared memory location:
the first process reads the value in memory location;
the first process adds one to the value;
but before it can write the new value back to the memory location it is suspended, and the second process is allowed to run:
the second process reads the value in memory location, the same value that the first process read;
the second process adds one to the value;
the second process writes the new value into the memory location.

How can the above operation be made an atmoic operation. My understanding of atomic operation is that any thing which executes without interruption is atomic. So for example

int b=1000;
  b+=1000;

Should be an atomic operation as per my understanding because both the instructions executed without an interruption,how ever I learned from some one that in C there is nothing known as atomic operation so above both statements are non atomic. So what I want to understand is what is atomicity is different when it comes to programming languages than the Operating Systems?

asm is the answer here, but that is the path to the dark side — Ulterior, Jul 10 '11 at 08:09
@David Heffernan if you want to know and control the execution, you must use asm, otherwise be at compilers mercy. — Ulterior, Jul 10 '11 at 08:52
@user : I assume you didn't intend to downvote the question, so +1 to counteract that. — Sander De Dycker, Jul 10 '11 at 10:08

score 4 · Answer 1 · answered Jul 10 '11 at 10:02

C99 doesn't have any way to make variables atomic with respect to other threads. C99 has no concept of multiple threads of execution. Thus, you need to use compiler-specific extensions, and/or CPU-level instructions to achieve atomicity.

The next C standard, currently known as C1x, will include atomic operations.

Even then, mere atomicity just guarantees that an operation is atomic, it doesn't guarantee when that operation becomes visible to other CPUs. To achieve visibility guarantees, in C99 you would need to study your CPU's memory model, and possibly use a special kind of CPU instructions known as fences or memory barriers. You also need to tell the compiler about it, using some compiler-specific compiler barrier. C1x defines several memory orderings, and when you use an atomic operation you can decide which memory ordering to use.

Some examples:

/* NOT atomic */
b += 1000;

/* GCC-extension, only in newish GCCs 
 *   requirements on b's loads are CPU-specific
 */
__sync_add_and_fetch(&b, 1000);

/* GCC-extension + x86-assembly, 
 *   b should be aligned to its size (natural alignment), 
 *   or loads will not be atomic
 */
__asm__ __volatile__("lock add $1000, %0" : "+r"(b));


/* C1x */
#include <stdatomic.h>
atomic_int b = ATOMIC_INIT(1000);
int r = atomic_fetch_add(&b, 1000) + 1000;

All of this is as complex as it seems, so you should normally stick to mutexes, which makes things easier.

score 3 · Accepted Answer · answered Jul 10 '11 at 07:32

int b = 1000;
b+=1000;

gets turned into multiple statements at the instruction level. At the very least, preparing a register or memory, assigning 1000, then getting the contents of that register/memory, adding 1000 to the contents, and re-assigning the new value (2000) to that register. Without locking, the OS can suspend the process/thread at any point in that operation. In addition, on multiproc systems, a different processor could access that memory (wouldn't be a register in this case) while your operation is in progress.

When you take a lock out (which is how you would make this atomic), you are, in part, informing the OS that it is not ok to suspend this process/thread, and that this memory should not be accessed by other processes.

Now the above code would probably be optimized by the compiler to a simple assignment of 2000 to the memory location for b, but I'm ignoring that for the purposes of this answer.

score 3 · Answer 3 · answered Jul 10 '11 at 07:33

3

b+=1000 is compiled, on all systems that I know, to multiple instructions. Thus it is not atomic.

Even b=1000 can be non atomic although you have to work hard to construct a situation where it is not atomic.

In fact C has no concept of threads and so there is nothing that is atomic in C. You need to rely on implementation specific details of your compiler and tools.

answered Jul 10 '11 at 07:33

David Heffernan

601,492
42
1,072
1,490

so you mean to say that the assembly instruction which would be used to access that particular memory area where the variable is stored that will be atomic. – Registered User Jul 10 '11 at 08:08
so is any one of `int b;` or `b=1000;` atomic? – Registered User Jul 10 '11 at 08:37
int b doesn't generate instructions so question is meaningless. Nothing in C is guaranteed atomic. – David Heffernan Jul 10 '11 at 08:40
@Registered user: Whether `b = 1000` is atomic depends on the CPU, and possibly on b's alignment and size. Even then, you may not have (or have very weak) visibility guarantees. – ninjalj Jul 10 '11 at 10:05

score 0 · Answer 4 · answered Jul 10 '11 at 07:31

The above statements are non atomic because it becomes a move instruction to load b into a register (if it isnt) then add 1000 to it and the store back into memory. Many instruction sets allow for atomicity through atomic increment easiest being x86 with lock addl dest, src; some other instruction sets use cmpxchg to achieve the same result.

score 0 · Answer 5 · edited May 23 '17 at 12:08

So what I want to understand is what is atomicity is different when it comes to programming languages than the Operating Systems?

I'm a bit confused by this question. What do you mean exactly? The atomicity concept is the same both in prog. languages and OS.

Regarding atomicity and language, here is for example a link about atomicity in JAVA, that might give you a different perspective: What operations in Java are considered atomic?

how can I convert non atomic operation to atomic

5 Answers5

Linked