Chapter 6: Synchronization Study Notes

Chapter 6: Synchronization

6.1 Tools

  • Discusses synchronization tools within operating systems, focusing on synchronization problems among concurrent processes.
  • Reference: Operating System Concepts - 10th Edition by Silberschatz, Galvin, and Gagne ©2018.

6.2 Outline

  • Background: Overview of concurrency and synchronization.
  • The Critical-Section Problem: Explanation and implications of critical sections in concurrent programming.
  • Peterson’s Solution: Introduction of a software-based solution to the critical-section problem.
  • Hardware Support for Synchronization: Discusses hardware solutions that assist in synchronization tasks.
  • Mutex Locks: Definition and usage of mutex locks as a synchronization mechanism.
  • Semaphores: Explanation of semaphores as a signaling mechanism for synchronization.
  • Monitors: Description of monitors as high-level synchronization constructs.
  • Liveness: Concepts of liveness and its importance in synchronization.
  • Evaluation: Assessment of different solutions for synchronization issues.

6.3 Objectives

  • Understand and describe the critical-section problem, including race conditions.
  • Illustrate hardware solutions to the critical-section problem, including:
    • Memory barriers
    • Compare-and-swap operations
    • Atomic variables
  • Demonstrate synchronization methods using mutex locks, semaphores, monitors, and condition variables.
  • Evaluate synchronization tools in various contention scenarios (low, moderate, high).

6.4 Background

  • Processes can execute concurrently, meaning they can be interrupted and partially complete execution at any time.
  • Concurrent access to shared data can cause data inconsistency.
  • To maintain data consistency, mechanisms to ensure orderly execution among cooperating processes are necessary.
  • Illustrated with the Bounded Buffer problem from Chapter 4, where a counter shared by a producer and a consumer can lead to race conditions.

6.5 Race Condition

  • Example involving processes P0 and P1 using the fork() system call.
  • Race condition arises when both processes access the shared kernel variable next_available_pid simultaneously, potentially leading to assigning the same PID to two different processes if not properly synchronized.

6.6 Critical Section Problem

  • In a system of n processes {p0, p1, …, pn-1}:
    • Each process has a critical section segment of code that may modify shared data (e.g., common variables, tables, files).
    • Mutual Exclusion: If one process is executing in its critical section, others cannot be in theirs.
    • Entry Section: Processes must request permission to enter the critical section.
    • Exit Section: Follows the critical section, allowing processes to continue execution after exiting.

6.7 Critical Section Structure

  • General structure for process Pi is as follows:
    • Entry section
    • Critical section
    • Exit section
    • Remainder section

6.8 Critical-Section Requirements

  1. Mutual Exclusion: Only one process can execute in the critical section at a time.
  2. Progress: If no process is in the critical section and other processes want to enter, one must be selected without indefinite postponement.
  3. Bounded Waiting: There should be a limit on how often other processes enter the critical section after a request is made.
    • Assumes processes run at non-zero speed and there is no assumption of their relative speeds.

6.9 Interrupt-based Solution

  • Approach using interrupts entails:
    • Entry Section: Disable interrupts to prevent context-switching during the critical section.
    • Exit Section: Re-enable interrupts after exiting.
  • Concerns addressed:
    • Long execution times for critical sections can lead to starvation.
    • In multiprocessor systems, this method is less effective because processes may run on different CPUs.

6.10 Software Solution 1

  • Focus on a two-process solution where load and store operations are atomic.
  • Using one variable int turn to indicate whose turn it is to enter the critical section, initially set to a specific process's ID.

6.11 Algorithm for Process Pi

  • Sample pseudo-code provided:
  while (true) {
      while (turn == j);  // Wait for turn
      // Critical section
      turn = j;           // Remainder section
  }

6.12 Correctness of the Software Solution

  • Mutual Exclusion is maintained since P1 enters critical section only if turn = i.
  • Consideration of Progress Requirement and Bounded-Waiting Requirement: Ensure no process starves.

6.13 Peterson’s Solution

  • Two-process solution involving variables:
    • int turn: indicates whose turn to enter the critical section.
    • boolean flag[2]: flags for each process indicating readiness to enter.
  • Initial Value: turn starts with one process ID.

6.14 Algorithm for Process Pi in Peterson's Solution

  • Pseudo-code for process Pi:
  while (true) {
      flag[i] = true;    // Indicate readiness
      turn = j;          // Set turn for other process
      while (flag[j] && turn == j); // Wait if required
      // Critical Section
      flag[i] = false;  // Exit Remainder Section
  }

6.15 Correctness of Peterson’s Solution

  • Three requirements verified:
    • Mutual Exclusion: P1 enters whenever either flag[j] == false or turn == i.
    • Progress: Satisfied as no process is left waiting indefinitely.
    • Bounded-Waiting: Met through controlled access to the critical section.

6.16 Peterson’s Solution and Modern Architecture

  • Despite its educational value, the solution does not always function effectively on modern architectures due to instruction reordering by processors or compilers, which may lead to unexpected results especially in multithreaded contexts.

6.17 Modern Architecture Example

  • Example with two threads sharing:
    • boolean flag = false;
    • int x = 0;
    • Execution sequence leading to unexpected outputs if instructions are improperly ordered, where the expected output could be 100 but might result in 0 due to reordering of the operations.

6.18 Modern Architecture Example (Cont.)

  • Demonstrates how reordering can result from the independence of variables, leading to potential data inconsistency.

6.19 Peterson’s Solution Revisited

  • Emphasizes the effect of instruction reordering in Peterson’s Solution, which can allow both processes to enter critical sections simultaneously.
  • Memory barriers are required to ensure the proper functioning of synchronization in modern systems.

6.20 Memory Barrier

  • Defines memory models (strongly ordered vs. weakly ordered).
    • Strongly Ordered: Immediate visibility of memory modifications across processors.
    • Weakly Ordered: Delayed visibility; may not be immediately apparent to other processors.
  • Memory Barrier: Instruction that ensures memory updates are visible across all processors before proceeding with subsequent operations.

6.21 Memory Barrier Instructions

  • Memory barrier instructions ensure completion of all loads and stores before any subsequent load/store operation.

6.22 Memory Barrier Example

  • Example provided ensuring correct order of operations between Threads 1 and 2 with inserted memory barriers to ensure thread safety and correctness of output.

6.23 Synchronization Hardware

  • Discusses hardware support for critical section code implementation.
  • Importance of not using interrupt disabling on multiprocessor systems due to inefficiency.
  • Three forms of hardware support identified:
    1. Hardware instructions
    2. Atomic variables

6.24 Hardware Instructions

  • Special hardware instructions that afford unsusceptible execution for certain operations, such as testing and modifying data or swapping contents atomically.

6.25 The test_and_set Instruction

  • Definition: boolean test_and_set(boolean *target)
  • Properties:
    • Executed atomically
    • Returns the original value before setting the new value to true.

6.26 Solution Using test_and_set()

  • Shared boolean variable lock initialized to false demonstrating the synchronization mechanism using test_and_set.

6.27 The compare_and_swap Instruction

  • Definition: int compare_and_swap(int *value, int expected, int new_value)
  • Properties:
    • Executed atomically
    • Conditional update of value based on matching expected value.

6.28 Solution using compare_and_swap

  • Implementation using compare_and_swap to manage access to a critical section within shared integer variable lock.

6.29 Bounded-waiting with compare-and-swap

  • Example demonstrating bounded waiting through a waiting mechanism and the use of compare-and-swap to manage the lock state effectively.

6.30 Atomic Variables

  • Explanation of atomic variables enabling atomic operations amongst basic data types, providing uninterruptible updates.

6.31 Atomic Variables (Cont.)

  • Example provided illustrating how to implement an increment operation on an atomic variable.

6.32 Mutex Locks

  • Mutex locks offer simplified solutions for critical section problems.
  • Defined as boolean variables indicating lock availability, where:
    • Acquire() the lock before the critical section
    • Release() after exiting the critical section.
  • Typically implemented using atomic operations.

6.33 Solution to CS Problem Using Mutex Locks

  • General structure demonstrates continuous attempts to acquire locks around critical sections and their proper release afterward.

6.34 Semaphore

  • Defined as an integer variable controlled through atomic operations, serving more complex synchronization needs than mutex locks.
  • Operations: wait() and signal() elaborated.

6.35 Semaphore (Cont.)

  • Differentiation between counting and binary semaphores:
    • Counting Semaphore: Values range unrestricted.
    • Binary Semaphore: Values constrained between 0 and 1 (akin to mutex locks).

6.36 Semaphore Usage Example

  • Example scenarios relating processes P1 and P2 to govern execution order using semaphores effectively.

6.37 Semaphore Implementation

  • Discusses safeguarding semaphore operations to prevent simultaneous modifications leading to critical sections conflicts.
  • Acknowledges a possible rise in busy waiting due to frequent semaphore accesses.

6.38 Semaphore Implementation with no Busy Waiting

  • Describes an advanced semaphore structure with a waiting queue to maintain processes awaiting semaphore availability, reducing busy waiting.

6.39 Implementation with no Busy Waiting (Cont.)

  • Definition of the semaphore's structure to manage value and associated processes within the waiting queue.

6.40 Implementation with no Busy Waiting (Cont.)

  • Detailed wait() and signal() functions laying the groundwork for semaphore management without busy waiting.

6.41 Problems with Semaphores

  • Highlights common mistakes in semaphore usage leading to synchronization failures and deadlocks, emphasizing careful implementation.

6.42 Monitors

  • Describes the concept of monitors as high-level abstractions for synchronization, only allowing one active process at a time.
  • Pseudocode structure laid out for monitor declarations and internal procedure definitions.

6.43 Schematic view of a Monitor

  • Visual representation of a monitor's components and their organization (shared data, operations, and entry queue).

6.44 Monitor Implementation Using Semaphores

  • Monitors can integrate semaphore locks for mutual exclusion during procedure execution.

6.45 Condition Variables

  • Describes condition variables and associated operations (wait() and signal()).

6.46 Monitor with Condition Variables

  • Schematic representation showing interactions of condition variables within a monitor structure.

6.47 Usage of Condition Variable Example

  • Provides an example for using condition variables to manage execution order between P1 and P2 based on a completion signal.

6.48 Monitor Implementation Using Semaphores (Cont.)

  • Advanced monitor structures introduced with semaphore management for observing conditions among waiting processes.

6.49 Implementation – Condition Variables

  • Functional definitions for x.wait() and x.signal(), detailing their respective workflows during execution.

6.50 Implementation (Cont.)

  • Continuation of condition variable signaling mechanisms emphasizing the structured execution flow for handling multiple processes in a wait state.

6.51 Resuming Processes within a Monitor

  • Considerations for determining which waiting process to resume upon signal execution, introducing conditional-wait constructs with prioritized handling.

6.52 Single Resource Allocation

  • Strategy for allocating a single resource among competing processes based on their planned usage times, preventing bottlenecks.

6.53 Single Resource Monitor

  • Structured as a monitor handling the allocation of resources securely, ensuring mutual exclusion during critical access periods.

6.54 Single Resource Monitor (Cont.)

  • Operational notes and incorrect monitor usage examples designed to illustrate common pitfalls to avoid.

6.55 Incorrect use of monitor operations

  • Common mistakes that can lead to synchronization errors when using monitors, underscoring the importance of correct operation sequence.

6.56 Liveness

  • Defines liveness as properties ensuring processes' progress without indefinite waiting, reiterating its criticality in synchronization contexts.
  • Indefinite Waiting is discussed as a liveness failure, emphasizing real-time implications on concurrent execution.

6.57 Liveness (Cont.)

  • Delves deeper into types of liveness failures, including deadlock situations where processes eternally wait for each other's resources without resolution.
  • Example: Deadlock scenario illustrated through semaphore interactions between two processes, P0 and P1.

6.58 Other forms of deadlock

  • Discusses alternative forms like starvation (indefinite blocking without removal from the wait queue) and priority inversion in resource management.

6.59 End of Chapter 6

  • Concludes the chapter summarizing synchronization methodologies and common challenges encountered in concurrent programming.