Process Synchronization in Operating Systems

Process Synchronization

Background

• Cooperating Processes: These are processes that can affect or be affected by other processes executing in the system. Unlike independent processes, they may share a logical address space and data through files. However, concurrent access to shared data can lead to inconsistencies, necessitating mechanisms to ensure orderly execution.

Producer/Consumer Problem

• Bounded Buffers: This is a classic synchronization problem involving buffers (finite resources). The producer generates data and places it in a buffer, while the consumer retrieves and uses that data.

• Implementation:

  • Shared data is defined with a buffer, pointers for input (in) and output (out), and a counter.

  • The producer process waits when the buffer is full and adds items to the buffer when space is available.

  • The consumer process waits when the buffer is empty and takes items from it when available.

• Atomic Operations: The counter and data manipulations in producer/consumer must be atomic to avoid inconsistent results due to interleaving execution.

Critical Section Problem

• Definition: The critical section problem addresses the need for mutual exclusion when multiple processes access shared data simultaneously.

• Each process needs to execute a critical section of code with access to shared resources without interference from others. The solution must guarantee:

  1. Mutual Exclusion: Only one process can execute in its critical section at a time.

  2. Progress: If no processes are in the critical section, others should be able to proceed without unnecessary delays.

  3. Bounded Waiting: There should be a limit on the number of times other processes can enter the critical section after a request is made.

Race Condition

• A race condition occurs when the outcome of execution depends on the timing of events like process scheduling. Resolving race conditions requires implementing synchronization mechanisms.

Solutions to Critical Section Problem

1. Disabling Interrupts: This solution is not ideal since it can only be executed in kernel mode and may prevent responsiveness in systems.

2. Peterson’s Solution: This software-based solution uses flags and turn indicators, ensuring mutual exclusion while allowing progress.

3. Bakery Algorithm: This algorithm assigns tokens to processes, ensuring that the process with the smallest token accesses the critical section first. It’s useful for managing n-process scenarios.

Semaphores

• A semaphore is an integer variable accessed via two operations:

  • wait(S): Decreases the semaphore and may block the process if the value is less than or equal to zero.

  • signal(S): Increases the semaphore value, potentially unblocking a waiting process.

• Semaphore implementation must be atomic to prevent race conditions. They can be binary or counting semaphores, controlling single or multiple resources.

Deadlock and Starvation

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

• Starvation: A process may starve waiting for resources if not appropriately managed in the semaphore queue.

Priority Inversion

• Priority inversion occurs when a lower-priority process holds resources needed by a higher-priority one, potentially leading to inefficient scheduling and missed deadlines in time-critical applications. Solutions include the priority inheritance protocol, where lower-priority processes temporarily inherit higher priority to proceed.

Readers-Writers Problem

• This synchronization issue arises when multiple readers can access shared data simultaneously, but writers require exclusive access. Solutions vary in prioritization of readers versus writers and must consider potential starvation.

Dining Philosophers Problem

• Conceptualized by Dijkstra, this problem illustrates synchronization using five philosophers sharing five chopsticks. It explores ensuring that each philosopher can eat without causing deadlock while guaranteeing mutual exclusion.

Monitors

• A monitor is a high-level synchronization construct that encapsulates shared data and associated operations. It ensures that only one process can execute within the monitor at a time and uses condition variables to allow processes to wait for certain conditions to be met.

• Condition variables enable processes to suspend execution until another process signals that it can proceed, restricting simultaneous access.

The above notes detail key concepts of process synchronization, highlighting prevalent issues, examples, and established solutions.