0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ The term "atomic" is used in (several) different ways in different context. Sometimes in very similar but still different ways. It is often used informally as well. Your question starts with a definition that seems to be based off of database theory, but then talks about programs. Your definition talks about "transactions" but there are no transactions in your program. It's likely that you are inadvertently using the wrong definition of "atomic". (Your definition of atomicity also doesn't really match the meaning of it a la ACID.) $\endgroup$ – Derek Elkins May 12 at 2:46
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As a note, this is what Isolation means in ACID, not what Atomicity means. It's not clear if your definition is intended to coincide/cover the ACID notion of atomicity (which isn't terribly relevant to arbitrary code). $\endgroup$ – Derek Elkins May 12 at 18:19
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.