Concurrency

Overview

Concurrency refers to the general phenomenon of multiple logical control flows whose execution overlaps in time.

Parallelism

Parallelism refers to simultaneous concurrency. Processes can run in parallel if running concurrently on different processor cores or computers.

Read-modify-write

An operation is said to be atomic if it cannot be interrupted.

The read-modify-write (RMW) instructions are a class of atomic instructions that both read a memory location and write a new value into it, either with a new value or some function of the old.

If a thread were to run an atomic operation, other threads are only able to see the state before or after the operation was run. That is, another thread cannot see any intermediate state of an atomic operation.

Test-and-set

The test-and-set (TAS) instruction writes a flag value to a memory location and returns the old value as a single atomic operation. Abstracting away suitable atomicity constructs, the following pseudocode demonstrates how this instruction typically works:

int test_and_set(int *ptr, int new) {
  int old = *ptr;
  *ptr = new;
  return old;
}

Fetch-and-add

The fetch-and-add (FAA) instruction atomically increments a value in a memory location and returns the old value. Abstracting away suitable atomicity constructs, the following pseudocode demonstrates how this instruction typically works:

int fetch_and_add(int *ptr, int add) {
  int old = *ptr;
  *ptr += add;
  return old;
}

Compare-and-swap

The compare-and-swap (CAS) instruction atomically compares a value in memory with an old value, updating it if the values are equal. Abstracting away suitable atomicity constructs, the following pseudocode demonstrates how this instruction typically works:

int compare_and_swap(int *ptr, int old, int new) {
  int prev = *ptr;
  if (prev == old) {
    *ptr = new;
  }
  return prev;
}

Synchronization

Synchronization primitives refer to low-level interfaces, typically provided by the operating system, for coordinating multiple concurrent tasks.

A critical section refers to a section in which only one task is allowed to enter at any given moment. Synchronization primitives are used to define these critical sections.

Semaphores

A semaphore is a locking mechanism typically interacted with using the following two functions:

• wait: Decrements the semaphore. Otherwise blocks until it can do so.
• signal: Increments the semaphore. Notifies blocked tasks.

A binary semaphore restricts its possible values to 0 or 1. A counting semaphore allows an arbitrary nonnegative counter value.

Mutexes

A mutex is a locking mechanism typically interacted with using the following two functions:

• lock(): Acquires the mutex. If a task attempts to lock() an already acquired mutex, it will block.
• unlock(): Releases the mutex. Notifies blocked tasks.

Unlike binary semaphores, a mutex requires that the task that locked it must also be the task that unlocks it. This allows the scheduler to make stricter decisions/guarantees than otherwise possible.