ch6_Synchronization-2022

Chapter 6: Synchronization Tools

Overview of Synchronization Tools in Operating Systems

  • Synchronization is essential for managing the execution of processes that communicate and share resources within an operating system.

Key Topics Covered

  • Background on synchronization

  • Race conditions and the critical-section problem

  • Solutions for synchronization:

    • Interrupt-based solutions

    • Peterson’s solution

    • Hardware support

      • Memory barriers

      • Atomic variables and hardware instructions

    • Mutex locks and semaphores

Background

  • Processes Types:

    • Independent Process: Operating independently, affecting no other processes.

    • Cooperating Process: Their execution impinges upon other processes.

  • Concurrency: Leads to shared data inconsistencies as processes may execute simultaneously on single or multi-core processors.

  • Synchronization Mechanisms: Ensures orderly execution to maintain data consistency.

Race Conditions

  • Definition: An undesirable situation when two or more processes access and manipulate shared data concurrently, and the result depends on the sequence of execution.

  • Example Scenario:

    • Initial variable: X = 4

    • Concurrent processes: P1 and P2 alter X simultaneously, leading to unpredictable values due to race conditions.

Example Breakdown:

  1. Load X

  2. X = X + 2 (by P1)

  3. Load X again during simultaneous execution (by P2) might give different final results depending on how they interleave.

  4. Final values can be inconsistent post-execution—demonstrating the race condition.

Critical-Section Problem

  • Critical Section: Code segment where shared data is accessed. Only one process should execute in this section at a time.

  • Requirements for Solutions:

    • Mutual Exclusion: Only one process can be in the critical section.

    • Progress: No process should block others from entering.

    • Bounded Waiting: Limit the number of times other processes can enter the critical section after a request has been made.

Solutions to the Critical-Section Problem

  1. Interrupt-based solutions:

    • Disable interrupts temporarily; this is ineffective in multi-CPU systems.

  2. Peterson’s Solution:

    • A software solution for two processes, ensuring mutual exclusion, progress, and bounded waiting.

    • Relies on shared variables turn and flag.

  3. Hardware Support:

    • Memory barriers ensure that memory operations occur in the correct order.

    • Special atomic operations like Test-and-Set and Compare-and-Swap to manage synchronization efficiently without busy waiting.

Mutex Locks

  • Mutex: A simpler tool that provides a locking mechanism for critical sections.

    • Acquisition and Release: A process must first acquire the lock before entering the critical section and releases it when done.

    • Implemented using atomic operations to ensure no race conditions occur.

Semaphores

  • A synchronization primitive that allows processes to be coordinated not just via mutual exclusion but also through signaling.

  • Semaphore operations:

    • wait(S): Decreases the semaphore's value; if the value is 0, the process waits.

    • signal(S): Increases the semaphore's value, waking up waiting processes.

  • Types of Semaphores:

    • Counting Semaphore: Controls access to a resource pool.

    • Binary Semaphore: Works similarly to a mutex, with values only between 0 and 1.

Issues with Semaphores

  • Busy Waiting: Can lead to inefficient resource usage.

  • Deadlock: Occurs when processes are waiting indefinitely for resources held by each other.

  • Starvation: A process waiting indefinitely without acquiring the lock due to sequential blocking.

Summary of Tools and Problems

  1. Software Solutions: Like Peterson, with limitations on the number of processes.

  2. Mutex: Better than Peterson, but still can lead to busy waiting.

  3. Test_and_Set vs. Compare_and_Swap: Better for hardware scenarios but have their constraints.

  4. Semaphore Issues: Versatile but susceptible to deadlocks and starvation issues.

Final Thoughts on Critical-Section Solutions

  • Balance between effectiveness and efficiency in synchronization continues to be a major focus in concurrent programming.