When you are faced with a concurrent system that you want to model, the very first question you should ask is ``What are its atomic operations?'' To answer this question, therefore, you must be absolutely clear about the level of abstraction at which you are modeling your system. Why? Because at one level what is atomic may not at all be atomic at a lower level.
Bank Account Example
Consider your Mellon bank account. At one level of abstraction, the operations of withdrawing, depositing, and determining your balance may each be considered atomic. However, the operation of transferring money from one account to another might not; it might require two atomic steps: a withdrawal from one account followed by a deposit into the other.
At a lower level of abstraction your bank account might be represented as a file in Mellon Bank's central database. Performing an operation, e.g., a withdrawal, at the higher level might actually involve various access and update operations to the file. At this lower level of abstraction, we can assume that accessing and updating a file are each atomic; thus, we might effect the atomicity of the higher-level withdrawal as a sequence of lower-level atomic accesses and updates to a file.
At an even lower level, we could imagine that the file actually lives on a physical disk. At this level, reading and writing to disk are each atomic.
Even lower, we could imagine that the file is physically spread across multiple pages on the disk; reading and writing to disk is made up of atomic reads and writes to individual disk pages.
Below this, we have atomic reads and writes to the bits under the disk head. Below that we have physics (magnets, electrons, you get the idea ...).
End of Example
At any given level of abstraction, what determines whether an operation is atomic is whether you consider the execution of that operation to be indivisible. If it is indivisible you can't divide it any further.
If an operation is atomic you cannot observe any intermediate
states when it executes.
If an operation is non-atomic then you can
observe possible intermediate states when it executes. For example, in the
transfer operation above, if it's non-atomic then I can observe the
intermediate state in which the sum of my two bank accounts is less
than the sum of their original (and similarly, final) values. If I
choose to model the transfer operation as atomic
, then I cannot
observe this intermediate state.
When you model a concurrent system, you certainly need to specify each of your atomic operations. Sometimes you will need to specify non-atomic operations too (e.g., the transfer operation), perhaps as a sequence of atomic operations. Remember that because there are other processes executing concurrently with the process executing the non-atomic operation, you have weaker guarantees. For example, suppose I specify f to be the non-atomic operation that is made up of the sequence of atomic g and h:
where I am using double angle brackets around g and h to emphasize that they each execute atomically. Then, in between the execution of g and h, some other process can do something (interleave one of its operations), therefore changing the state of the system from what g just left it in. That is, g's post-condition may not hold anymore; in particular it may not hold by the time h starts executing.