Process Synchronization

Chapter 6: Process Synchronization

Process Synchronization Overview

• A cooperating process is defined as one that can affect or be affected by other processes running in the system.

• Issues with concurrent access to shared data can lead to data inconsistency.

• In this chapter, various mechanisms are introduced to ensure:

  • Orderly execution of cooperating processes sharing a logical address space to maintain data consistency.

  • Methods for processes to share data either:

  • Directly, through a logical address space (both code and data).

  • Indirectly, through files or messages.

Example: Producer-Consumer Problem

• In a shared memory system, a producer process generates information that a consumer process uses.

  • Example scenario: A web server produces web pages that are consumed by clients through a browser.

• Solution framework for producer-consumer problem involves:

  • Utilizing a buffer of items fillable by the producer and emptyable by the consumer.

  • The buffer must be stored in a memory region shared by both the producer and consumer processes.

• The processes operate concurrently:

  • A producer can produce while a consumer consumes.

  • Synchronization is crucial to prevent the consumer from trying to consume data that hasn’t been produced.

Buffers in Producer-Consumer Problem

• Two types of buffers exist:

  • Unbounded-buffer:

  • There is no practical limit on the size.

  • The producer can always produce without waiting; however, the consumer may have to wait for new items.

  • Bounded-buffer:

  • There is a fixed size buffer.

  • The consumer must wait if the buffer is empty, while the producer must wait if the buffer is full.

Critical Variables in Synchronization

• Counter variable is used to manage the number of items in the buffer:

  • Initialized at 0.

  • Incremented by counter++ when a new item is added: ( ext{counter}++ )

  • Decremented by counter-- when an item is removed: ( ext{counter}-- )

  • Example scenario: When the variable counter starts at 5, if producer and consumer execute their respective operations concurrently, potential outcomes could be 4, 5, or 6. Only the result of 5 is valid when operations are executed in isolation.

Race Condition

• A race condition occurs when two processes access and manipulate shared data concurrently, and the execution outcome is affected by the sequence of access.

• For instance, operations can be broken down into equivalent machine language instructions, creating a scenario where the initial counter value was 5:

  1. Producer reads counter to register, registering 5.

  2. Producer increments register to 6.

  3. Consumer reads counter to register, still reflecting 5.

  4. Consumer decrements register to 4.

  5. Producer writes back 6 to counter.

  6. Consumer writes back 4 to counter.

• Resulting incorrect state occurs due to lack of synchronization, which highlights the need for synchronized processes where overlaps do not interfere.

Defining Critical Sections

• A critical section is a segment of code where a process accesses shared resources.

  • Defined in contexts where common variables are altered, tables updated, or files written.

• It is fundamental that when one process executes in its critical section, no other process is executing in theirs;

• Critical section problem entails designing a protocol for processes to cooperate, guided by specific rules:

  1. Each process must request permission before entering its critical section.

  2. The segment of code governing this request is referred to as the entry section.

  3. After execution, the critical section can be followed by an exit section.

  4. The subsequent code after is termed the remainder section.

Requirements for Solutions to Critical-Section Problem

• Any solution must meet the following three requirements:

  1. Mutual Exclusion: When one process is executing in its critical section, no other process can be executing in theirs.

  2. Progress: If no process is executing its critical section, and others want to enter, only those not in the remainder section can participate in deciding who will enter next.

  3. Bounded Waiting: Limit on the number of times other processes may enter their critical sections after a process has requested to enter before that request is granted.

Peterson’s Solution

• Peterson’s Solution is a classic software solution for the critical-section problem demonstrating the complexities of achieving mutual exclusion, progress, and bounded waiting.

• It is applicable specifically to two processes, denoted as Pi and Pj.

• Requires two shared variables:

  1. int turn: indicates whose turn it is to enter their critical section.

  2. boolean flag[2]: indicates if a process is prepared to enter its critical section.

Algorithm Structure of Peterson’s Solution

• For processes Pi and Pj, the following structure is observed:

  • For process Pi:
    do { flag[i] = true; turn = j; while (flag[j] && turn == j); // critical section flag[i] = false; // remainder section } while (true);

  • For process Pj:
    do { flag[j] = true; turn = i; while (flag[i] && turn == i); // critical section flag[j] = false; // remainder section } while (true);

Semaphore

• A semaphore is a more sophisticated synchronization tool compared to mutex locks, allowing processes to synchronize their activities effectively.

• A semaphore is an integer variable acting as a signaling mechanism for process interaction.

• It is accessed through two atomic operations:

  1. wait() (originally P()):
     wait(S) { while (S <= 0); // busy wait for S to be greater than 0 S--; }

  2. signal() (originally V()):
     signal(S) { S++; // Signal others that the critical section is empty }