Whats exact definition of 'atomicity' in programming?

Question

the definition of 'atomicity' says that a transaction should be able to be terminated without being touched or manipulated by possibly concurrent running actions during its process. But does that also mean that a program should not run concurrent when it is supposed to be atomic?

let's say we have 2 program as an example:

example_program1:

counts int i = 1 to 100 every second

every number is printed in new line

example_program2:

just prints "hi"

and a parent program that includes both of these program and run them once receiving a signal to start a specific program (e.g via sigaction in linux) with 2 version:

version 1:

runs the program (even concurrent) anytime once receiving the signal

which means program2 can print "hi" while program1 is still printing out the numbers

version 2:

only run one program at a time

signal for other program is blocked until program in progress has terminated

in this example, can only version 2 be considered atomic or both? Would this program be non-atomic only if e.g program2 would increment i by 1 during its process?

Answer 1

If an operation X is atomic, that means that anyone observing the operation will see it either as not yet started, or as completed, and not in any state that is partially completed. That's it.

Obviously if you write code to perform an operation X, and other code can see it half performed, or interfere with it, then your implementation of the operation X is not atomic.

In some contexts, an”atomic” operation can succeed or fail; if such an atomic operation fails then the effect must be exactly the same as if the operation had never been started.

Answer 2

I'm not sure I know of a simple, formal, abstract definition of "atomic" for a programming language. I know of many different ones at various levels of abstraction and with regards to various topics. I also know some that seem fairly abstract but have fairly sophisticated prerequisites (e.g. presheaf models of concurrency). Part of the problem is that there are a lot of different ways of saying two programs "behave" "equivalently" and some definitions may respect different notions of "equivalent".

A sketch (that I'm making up right now) of one approach with respect to an interleaving model of concurrency is: Given an operational semantics, a sequence of statements is executed atomically if all transitions (of the operational semantics) involving those statements happen in sequence. A sequence of statements is atomic if all possible sequences of transitions executes the sequence of statements atomically. We could loosen this to an "as if they were executed atomically" which we might start to formalize by saying that all possible sequences of transitions are equivalent (presumably observationally equivalent) to a sequence of transitions that executes the statements atomically.

Basically, executed atomically means that once we start executing some sequence of statements, we don't interleave the execution any other statement into the execution of the sequence. Implementation-wise, this might mean that we only execute one thread at a time as in a time-slicing implementation of threads, and a sequence of statements executed atomically means there were no context switches during their execution. The above definition has an issue in that it doesn't really handle coordination between threads well. It wouldn't really make sense to say that communication along a channel between two threads, for example, was ever atomic. (Often we talk about operations on a data structure as being atomic, and that would probably be more appropriate for this example. The definition would be specific to the data structure.)

For your example program and assuming an operational semantics where a print statement could be handled in a single transition, then Program 2 would always be executed atomically and is (fairly trivially) atomic. Your second execution describes a scenario where Program 1 is executed atomically while your first does not. If there was some mechanism that guaranteed your second execution always happened, then you could say Program 1 (with that mechanism) was atomic, but otherwise it presumably would not be atomic on its own.

As mentioned in my comment, "atomic" is often used in an informal and/or implementation-oriented sense. Therefore what exactly is intended is often unclear, though the spirit of what is intended is usually reasonable clear.

Answer 3

The deep dark ancient origin of the word Atomic in programming refers to an assembly language instruction ATOMIC. In the same way that a group of individual particles (proton, neutron, electron) form a single unbreakable unit called an atom, in programming ATOMIC refers to a group of assembly instructions that form a single uninterruptable unit instruction. The first assembly instruction is ATOMIC which suspends all interrupts until interrupts are re-initiated with something like UNATOMIC.

Since then the word ATOMIC has been grossly misused by marketing. Calling a single instruction ATOMIC is just silly.

ATOMIC was originally an acronym, I think it might have been "A seT? Of Multiple Instruction Clusters" - sorry, not sure about the T, it's been many years.

Answer 4

In case of memory models it means that loads and stores of the atomic operation can't be interleaved with any other load and store (even not to a different addres). If you have for example a compare-and-swap, you need a load and a store. Then on the memory order, this load and store need to be adjacent.

A Primer on Memory Consistency and Cache Coherence 2e page 28.

You can download the book for free on the Morgan Claypool website.