Do critical section and atomicity imply each other?

Question

Is it correct that

• In concurrent programming, a critical section is a sequence of statements which can't be executed by more than one processes/threads at the same time.

• Atomicity (as "A" in ACID for transactions in database systems) means a sequence of statements must be either executed completely or not at all. If all operations in a transaction are completed, the memory transaction is committed. Otherwise, the operations must be aborted and rolled back.

Is it correct that

• critical section isn't necessary atomic

• atomic section isn't necessary critical?

Thanks.

Answer 1

Atomicity should be understood to mean that the thing it refers to (a transaction, an operation, etc.) is all-or-nothing. There is no defined mechanism to observe partial results.

For a database transaction, atomicity means that all changes to the database are either made visible to others all at once at the same time (commit) or they are all discarded (rollback).

For processor instructions, atomicity means that nothing short of a complete power failure can interrupt that operation once the processor has started on it.

---

A critical section is a sequence of statements where the application's logic can get really screwed up if multiple thread of execution execute that sequence at the same time.

Thus, the defining factor of a critical section is not that it physically cannot be executed by multiple threads, but that it must not be executed by multiple threads to ensure the integrity of the application's logic.

---

critical section isn't necessary atomic

That is correct. The code in a critical section can both be interrupted to execute other code and it can make changes that are observable before the execution of the critical section has completed.

It is only parts of the mutex operations themselves, which provide the protection for the critical section, that must be atomic in order to ensure only a single thread can execute the critical section at a time.

atomic section isn't necessary critical?

If atomicity is ensured by the section being non-interruptible, then it can be argued that it is also a critical section, but I would hardly call a single instruction a "sequence of statements".

If atomicity is created with commit/rollback semantics like in a database transaction, then to some degree multiple transactions can operate on the same database or even the same table. However, a certain amount of exclusion is also needed to ensure the changes made in one transaction are not overwritten by another, concurrent, transaction. However, such exclusive access to (part of) a database is not referred to as a critical section. The most common term used for such exclusive access is that the transaction holds an exclusive lock or a write lock.

Answer 2

Do critical section and atomicity imply each other?

No, that is not a correct interpretation.

• Atomicity is in essence a package deal for one actor: "If you get a pedicure, you must also have a manicure".
• A critical section is in essence a limit on the amount of actors: "Only one customer can be in the parlor at the same time".

These two concepts can be combined, but they are not inherently related to each other.

• You could enforce manicures with pedicures, but allow multiple customers in your parlor at the same time.
• You could allow only one customer in your parlor at the same time, but allow them to have a manicure and/or a pedicure.

Answer 3

How I hate ACID.

Atomicity in ACID has nothing to do with concurrency. It means that all changes in a transaction are applied or non are applied. So even if you just have a single transaction at at time that transfers money from account A to account B, in case of e.g a power failure you want account A, B both to be modified or none to be modified.

Isolation in ACID is about concurrency. This is where you will find things like SERIALIZABLE; the system behaves as if the transactions were executed one after another.