Concurrency Notes

  • Concurrency Introduction

    • Converts a single physical CPU into multiple virtual CPUs.
    • Enables multiple programs to run simultaneously.
    • Creates illusion of large private virtual memory for each process.
    • Each program behaves as if it has its own memory.
    • OS secretly multiplexes address spaces across physical memory and disk.

  • Threads

    • A new abstraction for a single running process.
    • Multi-threaded program has more than one point of execution (multiple PCs being fetched and executed from).
    • Each thread is like a separate process but shares the same address space and can access the same data.
    • Single thread state:
    • Program counter (PC) tracks instruction fetching.
    • Private set of registers for computation.
    • Context switch between threads is similar to process context switch but address space remains the same.
    • Thread context switch saves/restores register state using Thread Control Blocks (TCBs).
    • Each thread has its own stack for local variables, arguments, and return values (thread-local storage).

  • Why Use Threads?

    • Parallelism: Speed up programs on multi-processor systems by using a thread per CPU.
    • Avoid Blocking: Prevent program progress from stalling due to slow I/O by switching to other threads.
    • Enables overlap of I/O with other activities within a single program.
    • Threads share an address space, making data sharing easier compared to multiple processes.

  • Thread Creation Example

    • Program creates two threads, each printing “A” or “B”.
    • Threads may run immediately or be put in a “ready” state.
    • On a multiprocessor, threads could run simultaneously.
    • pthread_join() waits for a particular thread to complete.
    • The OS scheduler determines which thread runs at a given time.
    • Thread creation is like a function call that creates a new thread of execution, running independently of the caller.

  • Shared Data and Race Conditions

    • Threads accessing shared data can lead to race conditions.
    • Example: Two threads incrementing a shared variable.
    • The desired result may not be achieved due to interleaving of instructions.
    • Race condition: Results depend on the timing of code execution.
    • Critical section: Code that accesses shared variables and must not be concurrently executed by more than one thread.
    • Mutual exclusion: Ensures that only one thread executes within the critical section at a time.

  • The Heart Of The Problem: Uncontrolled Scheduling

    • Shows example assembly code for incrementing a counter:
      mov 0x8049a1c, %eax
      add $0x1, %eax
      mov %eax, 0x8049a1c

  • Race Condition Explanation

    • A thread loads counter value to register, gets interrupted, another thread increments counter, first thread resumes and overwrites the incremented value.
    • Critical section requires mutual exclusion to prevent race conditions.
    • Indeterminate program: Output varies across different runs.

  • Wish For Atomicity

    • Atomic operations solve race conditions by executing a series of actions as a single, uninterruptible unit (“all or nothing”).
    • Atomicity ensures either all actions occur or none occur, with no intermediate state visible.

  • Synchronization Primitives

    • Hardware provides instructions to build synchronization primitives.
    • OS and hardware support are used to create multi-threaded code that accesses critical sections in a synchronized manner.

  • Need For Thread Interaction

    • Threads often need to wait for another to complete an action.
    • Mechanisms are needed to support sleeping/waking interactions in multi-threaded programs.

  • Key Concurrency Terms

    • Critical Section: Code accessing a shared resource.
    • Race Condition: Multiple threads enter a critical section simultaneously, leading to unexpected outcomes.
    • Indeterminate Program: Program with race conditions, producing varying output.
    • Mutual Exclusion: Primitives to ensure only one thread enters a critical section, avoiding races.

  • Concurrency in OS

    • The OS was the first concurrent program and many techniques were created for use within the OS.
    • Page tables, process lists, file system structures, and virtually every kernel data structure has to be carefully accessed, with the proper synchronization primitives, to work correctly.

  • Thread API Guidelines

    • Keep it simple.
    • Minimize thread interactions.
    • Initialize locks and condition variables.
    • Check your return codes.
    • Pass arguments and return values carefully.
    • Use condition variables to signal between threads.
    • Use the manual pages.