What exactly does the term "atomicity" mean in the context of computer systems in general and multithreaded programming in particular?

Atomicity comes from atom, which derives from the Greek word atomos, which means uncuttable, but is more commonly translated as "indivisible." You may recall from your physics classes that physicists used to believe that atoms represented the smallest, indivisible particles that make up all matter (before particle physicists discovered even smaller particles).

In Computer Science, we mean the idea of being "indivisible," and here specifically we mean "all or nothing," or "entirely or not at all" with respect to what we can observe. To give a simple example that's closer to CS3214: suppose you have this code sequence in one thread:

items_in_container++;
insert_item_into(&container, item);

which involves two operations: (a) incrementing the variable items_in_container and (b) adding the item into the container.

We would say that these operations are done atomically if no other thread would be able to observe operation (a) without also observing operation (b). In other words, no thread should ever see items_in_container incremented without also seeing the item in the container.

This is nice, because then other threads can code:

if (items_in_container > 0)
   item = get_item(&container)

without risking a scenario where items_in_container is greater than zero but no item is in the container.

As given, however, these 2 operations would not be atomic with each other. A lock is needed, so we'd have to write:

lock(&container_lock);
items_in_container++;
insert_item_into(&container, item);
unlock(&container_lock);

Now, every thread will see either:

• items_in_container to be zero and no item in the container
• or items_in_container to be positive and at least one item in the container

But that works only if the thread itself acquires and releasing the lock:

lock(&container_lock);
if (items_in_container > 0)
   item = get_item(&container)
unlock(&container_lock);

Note that if 2 threads try to perform these operations about the same time, it's not guaranteed which of these 2 outcomes occurs: if you must be certain that the second thread sees items added to the container, you must use condition variables or semaphores - but now at least no thread will see items_in_container in a state that's inconsistent with the actual number of items in the container.

My example of atomicity involved 2 things: a counter variable and the container itself. However, remember that in C, not even operations such as items_in_container++ are atomic, but they actually consist of 2 individual operations:

int tmp = items_in_container;
items_in_container = tmp + 1;

that are already not atomic! If 2 threads both perform these operations on the value 0, the final value may be 1 or 2 (and worse, C11 says this is undefined behavior).

Another way of thinking about atomic is that if all individual operations are atomic, then the overall outcome represents some sequence order of these operations - we don't know which, but there is one.

Our common method to achieve atomicity is to wrap the operations we need to be atomic into critical sections protected with locks.

However, with C11 atomics, certain simple operations can be made atomic without locks. For instance, if items_in_container were declared as atomic_int, items_in_container++ would be atomic. (But note: items_in_container would be atomic only individually with respect to observing items_in_container - it still wouldn't be atomic with respect to what's in the container.) See the lecture for more details.