ch6-SYNCHRONIZATION-new

Chapter 6: Synchronization Tools

Overview

  • This chapter covers synchronization tools in the context of operating systems, emphasizing how processes can cooperate and share data without leading to inconsistencies.

Outline

  • Background

  • The Critical-Section Problem

  • Hardware Support for Synchronization

  • Semaphores

  • Monitors

Objectives

  • Describe the critical-section problem and illustrate a race condition.

  • Illustrate hardware solutions to the critical-section problem.

  • Explain how mutex locks, semaphores, and monitors can resolve critical section issues.

Background

  • **Processes Execution:

    • Processes can execute simultaneously, and interruptions are possible.

    • Concurrent access to shared resources may lead to inconsistent data.

    • Mechanisms are needed to ensure orderly process execution to maintain data integrity.**

Race Condition

  • Definition: A scenario in which multiple processes access and manipulate shared data concurrently, with the outcome dependent on the order of access.

  • Solution: To prevent race conditions, ensure exclusive access to shared data by synchronizing processes. Synchronization and coordination are essential.

Example of Race Condition

  • Processes P0 and P1: Both create child processes using fork(). A race condition arises with the kernel variable next_available_pid, leading to potential assignment of the same PID to different processes if not properly synchronized.

Critical Section Problem

  • Definition: A part of the program where shared variables are accessed and modified. Only one process can be in the critical section at a time.

  • Key Points:

    • Protocols must be designed for processes to synchronize their activities and cooperatively share data.

    • Each process must request access to the critical section through predefined sections: entry, critical, exit, and remainder.

Requirements to Solve Critical Section Problem

  1. Mutual Exclusion: If a process is in its critical section, no other process can enter.

  2. Progress: If no process is in the critical section, and some want to enter, then only processes not in their remainder sections can decide who enters next.

  3. Bounded Waiting: Limits the number of times a process can enter its critical section after requesting entry.

Solutions for Critical Section Problem

Interrupt-Based Solutions

  • Entry section: Disable interrupts

  • Exit section: Enable interrupts

  • Limitations:

    • Not practical for long-running critical sections.

    • Risks starvation of processes.

    • Infeasible for multiprocessor environments.

Peterson's Solution

  • Applicable for Two Processes: Uses two variables: turn (indicating whose turn) and flag[] (indicating readiness to enter).

  • Algorithm Steps:

    • Set flag[i] to true, indicating readiness.

    • Set turn to the other process's index to allow the other process to proceed.

    • The process waits while flag[j] is true and it is turn until entering the critical section.

    • After exiting, it sets flag[i] to false.

Memory Barriers

  • Definition: Instructions to enforce order constraints on memory operations.

  • Types:

    • Strongly Ordered: Modifications are visible immediately to all processors.

    • Weakly Ordered: Modifications may not be visible immediately.

  • Function: Ensure that all loads and stores complete before subsequent operations, maintaining consistency across processes.

Atomic Variables

  • Definition: Special hardware instructions for uninterrupted operations, such as test-and-set and compare-and-swap.

  • Purpose: Ensure mutual exclusion and avoid data races during updates, especially with counters.

  • **Key Characteristics:

    • Operations on atomic variables are indivisible.**

test_and_set Instruction

  • Function: Sets a boolean variable to true atomically while returning the original variable's value.

compare_and_swap Instruction

  • Function: Atomically swaps the value of a variable if it matches an expected value and returns the original value.

Mutex Locks

  • Simplify protecting critical sections to prevent race conditions.

  • Mechanism: Acquire a lock before entering the critical section and release it afterward.

  • Disadvantage: Busy waiting can be inefficient, especially in real-time environments.

Semaphore

  • An advanced synchronization tool using an integer variable accessed via wait() and signal() operations.

  • wait(S): Waits until the semaphore value is positive, then decrements it.

  • signal(S): Increments the semaphore value, indicating resource availability.

  • Types: Counting semaphores (multiple instances) and binary semaphores (0 or 1).

Semaphore Implementation

  • Ensure no two processes execute wait() and signal() simultaneously.

  • Modify wait() to suspend processes instead of busy waiting, placing them in a waiting queue.

Monitors

  • A high-level synchronization abstraction that restricts access to shared variables.

  • Only one process can be executed at a time within a monitor. Functions within the monitor manage internal states and communications.

  • Pseudocode Example:

    monitor monitor-name {
  // shared variable declarations
  procedure P1 (…) { … }
  procedure P2 (…) { … }
  …
}

Conclusion

  • This chapter introduces critical synchronization issues faced in operating systems, articulating concepts such as the critical-section problem, race conditions, and showing solutions involving semaphores and monitors to manage concurrent processing effectively.