Process Synchronization

Chapter 6: Process Synchronization

Introduction to Process Synchronization

• Cooperating Process:

  • A process that can affect or be affected by other processes executing in the system.

  • Key issue: Concurrent access to shared data may result in data inconsistency.

  • Discussion in this chapter focuses on:

  • The orderly execution of cooperating processes that share a logical address space, ensuring data consistency.

  • Types of data sharing:

  • Direct Sharing:

    • Processes share both code and data directly in a logical address space.

  • Indirect Sharing:

    • Data is shared only through files or messages.

Synchronization Example: Producer-Consumer Problem

• Concept:

  • In a shared memory system, a producer process produces information consumed by a consumer process.

• Example Context:

  • A web server (producer) generates web pages, which are consumed by clients through browsers.

• Buffer Mechanism:

  • To enable concurrent execution of producer and consumer, a buffer of items is required:

  • Shared Memory Buffer:

    • A region of memory shared between producer and consumer processes.

  • Synchronization Requirement:

    • Ensuring the consumer does not consume an item that has not yet been produced.

Producers and Consumers Code Mechanics

• Counter Variable Initialization:

  • Initial value of the counter is set to 5.

• Producer Execution Steps:

  • register1 = counter

  • register1 = register1 + 1 (this increments the counter)

  • counter = register1

• Consumer Execution Steps:

  • register2 = counter

  • register2 = register2 - 1 (this decrements the counter)

  • counter = register2

• Example Execution:

  • Execution Timestamps:

  • T0: producer executes register1 = counter (register1 = 5)

  • T1: producer executes register1 = register1 + 1 (register1 = 6)

  • T2: consumer executes register2 = counter (register2 = 5)

  • T3: consumer executes register2 = register2 - 1 (register2 = 4)

  • T4: producer executes counter = register1 (counter = 6)

  • T5: consumer executes counter = register2 (counter = 4)

• Outcome: No synchronization leads to incorrect counter values.

Buffer Types

• Two kinds of buffers:

  • Unbounded Buffer:

  • No practical limit on size; producer can always produce items.

  • Consumer might need to wait for new items.

  • Bounded Buffer:

  • Fixed size; consumer must wait if the buffer is empty, and producer must wait if the buffer is full.

Race Condition

• Definition:

  • A situation where multiple processes access and manipulate shared data concurrently, with the outcome depending on the order of execution.

• Example of Race Condition Execution:

  • Consider a scenario where the counter can be manipulated concurrently:

  • counter++ and counter-- executed concurrently can lead to various results (4, 5, 6), but the only correct state should be counter = 5.

• Concurrency Mechanism:

  • We require process synchronization to prevent race conditions.

Critical Section Problem

• Definition:

  • In a system of n processes:

  • Each process has a critical section of code that changes common variables or resources.

  • Key Rule:

  • No two processes can execute their critical sections simultaneously.

• Requirements for a Solution:

  1. Mutual Exclusion:

  • If one process is in its critical section, no other process can be in theirs.

  1. Progress:

  • If no process is in its critical section and some want to enter, only those outside the critical section can decide who will enter.

  1. Bounded Waiting:

  • There is a limit to how many times other processes can enter their critical sections after requesting to enter.

Solutions to the Critical-Section Problem

• General Structure of Each Process:

  • Each process must:

  1. Request permission to enter its critical section (entry section).

  2. Execute its critical section (e.g., accessing shared resources).

  3. Execute its exit section after critical execution.

  4. The rest of the code after that is the remainder section.

Peterson’s Solution for Two Processes

• Overview:

  • A software-based solution for the critical-section problem.

  • Not guaranteed to function correctly on modern architectures but illustrates the complexities in designing mutual exclusion solutions.

• Process Requirements:

  • Only applicable for two processes (Pi and Pj).

  • Needs two shared data items:

  • int turn; (indicates whose turn to enter the critical section).

  • boolean flag[2]; (indicates if a process is ready to enter its critical section).

• Algorithm:

  • 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);

Semaphores

• Definition:

  • A synchronization tool that provides advanced ways for processes to synchronize their activities.

• Components:

  • Semaphore S: An integer variable shared between processes.

• Operations:

  • Access to semaphore S via two atomic operations:

  1. wait(S):
     wait(S) { while (S <= 0) // busy wait ; // wait until S is positive S--; // decrement to signal entry into the critical section }

  2. signal(S):
     signal(S) { S++; // Signals that the critical section is now empty }