Atomic Operations - aryanjoshi0823/5143-Operating-System GitHub Wiki

What is an Atomic Operation?

An atomic operation is a sequence of instructions that execute as a single, uninterruptible step. During the execution of an atomic operation:

  1. No Interruption: No other thread or process can observe or modify the operation's intermediate states.
  2. All-or-Nothing Execution: The operation is either completed fully or not executed at all.

Characteristics of Atomic Operations

  • Indivisibility: They cannot be interrupted or split into smaller parts.
  • Consistency: Ensure data integrity during concurrent access.
  • Low Overhead: Operate at the hardware or software level with minimal performance impact.

Examples of Atomic Operations

  1. Increment and Decrement: Operations like x++ or x-- are atomic if executed in a single machine instruction (e.g., INC in assembly).
  2. Test-and-Set: A hardware-supported atomic instruction that tests a variable's value and sets it in one step.
  3. Compare-and-Swap (CAS): Compares a variable to an expected value and updates it if the comparison succeeds. Widely used in lock-free algorithms.
  4. Load and Store: Reading and writing a single memory word can be atomic on certain architectures.

Implementation in Operating Systems

Atomicity is achieved using hardware and software mechanisms:

Hardware Support

  • Atomic Instructions: Modern CPUs provide atomic operations such as Test-and-Set, Compare-and-Swap, or Fetch-and-Add.
  • Memory Barriers: Ensure proper ordering of memory operations in multi-core systems.

Software Techniques

  • Spinlocks: Use atomic operations to acquire or release a lock.
  • Mutexes: Implement atomicity by blocking other threads during critical sections.

Use Cases

  1. Semaphore Operations:
    Updating counters atomically to manage resource availability.
  2. Lock-Free Data Structures:
    Designing queues or stacks without explicit locks.
  3. Reference Counting:
    Managing shared resources like memory or file handles.