Skip to main content

6. Concurrency

17/10/22

Concurrency​

  • Threads/processes execute concurrently and can share resources. (Multi-program mining improves system utilisation)
  • A thread/process can be interrupted at any point in time. Process state is saved in the process control block
  • Outcome of programs may become unpredictable. Sharing data can lead to inconsistencies, outcome of execution may depend on the order in which instructions are carried out.

Not always in order. Registers can sometimes not sequentially execute code in the correct order.

Race Conditions​

  • A race condition occurs when multiple threads/processes access shared data and the result is dependent on the order in which the instructions are interleaved.
  • Mechanisms to provide controlled/synchronised access to data and avoid race conditions
  • What comes out is dependent on the order they are carried out/interleaved

Concurrency within the OS​

Data Structures​

  • Kernels are preemptive these days. (Multiple processes/threads are running in the kernel. These cannot be interrupted any any point)
  • The kernel maintains data structures
    • Accessed concurrently/in parallel
    • Can be subject to concurrency issues
  • OS must make sure that interactions within the OS do not result in rare conditions

Resources​

  • Processes share resources, including memory, files etc.
  • Operating system must:
    • Provide locking mechanisms to implement/support mutual exclusions and prevent starvation/deadlocks
    • Allocate and de-allocate these resources safely

Critical Sections, Mutual Exclusion​

  • Critical Section: set of instructions in which shared resources between processes/threads are changed. Only 1 thing can access it at once. Manipulating that share across multiple users. This section gets locked whilst something is accessing it.
  • Mutual Exclusion: must be enforced for critical sections.
    • Only one process at a time should be in the critical section
    • Processes have to get "permission" before entering their critical section
  • Any solution to the critical section problem must satisfy the following requirements:\
    • Mutual exclusion: only one process can be in its critical section at any one point in time
    • Progress: any process must be able to enter its critical section at some point in time
    • Fairness/bounded waiting"": fairly distributed waiting times/processes cannot be made to wait indefinitely.
  • Requirements have to be satisfied, independent of the order in which sequences are executed.

Enforcing Mutual Exclusion​

  • Bottom line of the OS is to hide away the complexity of the hardware.
  • Approaches for mutual exclusion can be:
    • Software based: Peterson's solution
    • Hardware based: test_and_set(), swap_and_compare()
    • Based on:
      • Mutexes/Semaphones
    • Monitors (software construct within the programming languages)
  • Deadlocks have to be prevented

Deadlocks​

Set of processes/threads is deadlocked if each process/thread in the set is waiting for an event that only the other process/thread in the set can cause

Working with mutexes cause deadlocks

Four conditions must hold for deadlocks to occur:

  1. Mutual exclusion: a resource can be assigned to at most one process at a time
  2. Hold and wait condition: a resource can be held whilst requesting new resources
  3. No preemption: resources cannot be forcefully taken away from a process
  4. Circular wait: there is a circular chain of two or more processes, waiting for a resource held by the other processes.
  • No deadlocks can occur if one of the conditions is not satisfied.