Chapter 6: Process Synchronization

Overview

Process synchronization ensures that multiple processes or threads can cooperate safely when accessing shared resources. It prevents race conditions and maintains data consistency in concurrent systems.

The Critical-Section Problem

  • Definition: A critical section is a part of the program where shared resources are accessed.

  • Goal: Ensure only one process executes its critical section at a time.

  • Requirements: 1. Mutual Exclusion: Only one process in the critical section. 2. Progress: A process outside its critical section cannot block others indefinitely. 3. Bounded Waiting: Limit on how long a process waits to enter its critical section.

Semaphores and Mutexes

  • Semaphore:

    • An integer variable used for signaling between processes.

    • Operations: - wait() (P): Decrement; block if value < 0. - signal() (V): Increment; wake a waiting process.

    • Types: - Counting Semaphore: Range over unrestricted domain. - Binary Semaphore: 0 or 1 (acts like a mutex).

  • Mutex (Mutual Exclusion Lock):

    • Simplified synchronization mechanism allowing only one thread access to a resource.

    • Operations: lock() and unlock().

    • Used for short critical sections.

Monitors

  • Definition: A high-level synchronization construct that encapsulates shared data and operations.

  • Features: - Automatic mutual exclusion for procedure calls. - Uses condition variables (wait, signal) to control execution flow.

  • Advantages: Easier to reason about than low-level semaphores.

Classic Problems of Synchronization

Producer-Consumer Problem

  • Scenario: Producers generate data and put it in a buffer; consumers remove it.

  • Goal: Prevent buffer overflow (producers) and underflow (consumers).

  • Solution: Use semaphores: - empty (count of empty slots) - full (count of filled slots) - mutex (protect buffer access)

Dining Philosophers Problem

  • Scenario: Five philosophers sit at a table, alternating between thinking and eating, with one fork between each pair.

  • Goal: Prevent deadlock and starvation while ensuring mutual exclusion.

  • Common Solutions: - Limit number of philosophers who can eat simultaneously. - Use asymmetric resource allocation (e.g., one philosopher picks up forks in reverse order). - Apply monitors or semaphores with careful ordering.

—