Process Synchronization Basics

Operating Systems - Process Synchronization

• Process synchronization is the task of coordinating the execution of processes to prevent race conditions and ensure consistent access to shared data and resources.
• Processes can be classified as independent or cooperative, depending on whether one process's execution affects another.
• Concurrent access to shared data can lead to data inconsistency.
• Data consistency requires orderly execution mechanisms for cooperating processes.

Objectives

• Introduce the critical-section problem and its software and hardware solutions to ensure the consistency of shared data.
• Examine classical process synchronization problems.
• Explore tools used to solve process synchronization problems.

Background

• Processes can run concurrently or in parallel.
• CPU schedulers switch between processes allowing concurrent execution. Multi-core processors allow parallel execution.
• Concurrent access to shared data may result in data inconsistency.
• Mechanisms ensure the orderly execution of cooperating processes.

Background - Process Synchronization

• Process synchronization is the coordination of process execution to prevent race conditions. Race conditions occur when the outcome of a program depends on the unpredictable order in which processes access and manipulate shared data.
• Processes "race" to access or modify shared data.

Producer-Consumer Problem

• A classic multi-process synchronization problem.
• Producers generate data, put it into a buffer, and continuously generate more data.
• Consumers consume data from the buffer.
• Producers and consumers share the same memory buffer with a fixed size (bounded).

Producer-Consumer Problem - Solutions

• Introduce a counter to keep track of full buffers.
• The counter is initialized to 0. Producers increment the counter after producing a new buffer. Consumers decrement the counter after consuming a buffer.
• Code examples for producer and consumer processes are provided, demonstrating the expected outcome when incrementing and decrementing the counter.

Race Condition

• A race condition arises when multiple processes try to access and modify shared resources concurrently.
• The outcome of the program depends on the specific order in which processes execute.
• This can lead to incorrect shared data values.

Critical Section

• A critical section is a part of a program where a process accesses shared resources.
• Only one process can be inside its critical section at a time per resource.

Critical Section Problem - Solution

• Mutual Exclusion: Only one process can be in its critical section at any given time.
• Progress: If no process is in its critical section and other processes wish to enter, the selection of the next process must not be postponed indefinitely.
• Bounded Waiting: A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request, and before that request is granted.

Peterson's Solution

• A software-based solution to the critical-section problem limited to two processes.
• Uses shared Boolean flags and a turn variable to give each process a fair chance to enter the critical section.

Synchronization Hardware

• Uniprocessors can disable interrupts to prevent preemption, but this can be inefficient on multiprocessors.
• Modern machines use atomic instructions—instructions that are non-interruptible—like test_and_set and compare_and_swap to provide locks for critical sections.

Mutex Locks

• A simple synchronization mechanism to address the critical section problem using a shared boolean variable representing the lock status.
• The acquire() operation ensures exclusive access to shared data, while the release() operation returns the lock.
• Typically implemented with hardware-supported atomic operations.

Semaphore

• An integer variable that can be modified by atomic wait() and signal() operations.
• Wait() decrements the semaphore value and blocks the process if the value is negative.
• Signal() increments the semaphore value.
• Can solve various synchronization problems.

Semaphore Implementation

• Issues with busy waiting in implementations (consuming CPU cycles while waiting for resource availability).
• Implementing a waiting queue to allow blocked processes to be swapped out of the CPU, reducing the need for busy-waiting.

Semaphore - Problems

• Deadlock: Two or more processes are waiting indefinitely for an event.
• Starvation: A process may never be selected for service.
• Priority inversion: Scheduling problem where a lower-priority process holds a lock needed by a higher-priority process.

Classical Problems of Synchronization

• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining Philosophers Problem

Bounded-Buffer Problem

• A problem with n buffers, each holding one item.
• Semaphores mutex (initialized to 1), full (initialized to 0), and empty (initialized to n) coordinate producers and consumers.
• Producer threads wait() on empty and add to the buffer, then signal() full.
• Consumer threads wait() on full and remove from the buffer, then signal() empty.

Readers-Writers Problem

• Data is shared among multiple readers and writers.
• Multiple readers can read concurrently, but only one writer can write at a time.
• Several variations exist prioritizing reads or writes.

Dining Philosophers Problem

• Five philosophers seat around a table with chopsticks.
• Each philosopher needs two chopsticks to eat.
• An algorithm ensures that no philosopher is starved from accessing the resources.