CS2005: Networks and Operating Systems

CS2005 - Networks and Operating Systems: Process Management

Introduction

• Authors: A. Silberschatz, P. Baer Galvin and G. Gagne ©2003

Session Objectives

• Introduce the critical section problem, ensuring consistency of shared data.

• Present software (not hardware) solutions to the critical section problem.

• Examine several classical process synchronization problems.

• Explore tools used for solving process synchronization issues.

Key Questions

• What can go wrong when multiple processes access the same data?

• What is the general solution to this problem?

• What different approaches can be used to implement this in software?

• Provide two examples of classic synchronization problems.

The Money Problem

• Scenario: Two users sharing a bank account with initial balance £10, both depositing £1 concurrently.

• Timeline events:

  • t0: Balance = £10

  • t1: Both get balance (£10)

  • t2: Both deposit £1 (£10)

  • t3: First deposit updates account (£11)

  • t4: Second gets updated (£11) and deposits (£1)

  • t5: Account updates to (£12)

• Outcome: Ambiguity arises as both processes access the same data leading to inconsistent outputs.

The Problem Overview

• Cooperating processes may share data through accessing files/messages or shared memory.

• Threads can share code and data, especially in concurrent execution.

• Issues arise from interrupted execution, leading to potential data inconsistency.

• Mechanisms are needed to ensure orderly execution of cooperating processes.

Producer-Consumer Problem (Bounded Buffer)

• Definition: A producer generates data consumed by a consumer via a shared buffer of limited size.

• Key concepts:

  • Buffer: Circular list with a maximum size (BUFFER_SIZE).

  • Producer: Adds items when the buffer is not full.

  • Consumer: Removes items when the buffer is not empty.

Producer Algorithm

• Loop to continuously produce items.

• Busy waiting when buffer is full.

• Update buffer and counters appropriately.

Consumer Algorithm

• Loop continuously to consume items.

• Busy waiting when buffer is empty.

• Update buffer and counters appropriately.

Race Condition

• Occurs when multiple processes manipulate a shared variable (e.g., counter) concurrently.

• Results in uncertain outcomes due to the non-deterministic order of execution.

• Therefore, processes must be synchronized to manage shared variable access.

Critical-Section Problem

• Definition: Multiple processes each having a critical section of code that should not be executed concurrently.

• Objective: Ensure that no two processes execute in their critical sections at once.

Critical Section Structure

• Entry Section: Requests permission to enter critical section.

• Critical Section: Protected code segment.

• Exit Section: Notifies exit from the critical section.

• Remainder Code: Non-critical section of the process.

Properties of Critical Section Solutions

• Mutual Exclusion: Only one process in critical section at a time.

• Progress: Allow non-blocking decisions for other processes to enter critical section.

• Bounded Waiting: Limit the number of entries in critical sections before a waiting process gains access.

Peterson’s Solution

• Effective algorithm for two processes sharing data with critical sections.

• Data items shared:

  • int turn: Indicates whose turn to enter critical section.

  • boolean flag[2]: Indicates readiness to enter critical section.

Verification of Requirements

• Mutual Exclusion: Maintained for critical sections.

• Progress: Guaranteed by turn management.

• Bounded Waiting: Max wait of one turn enforced.

Mutex Locks

• Software solutions that protect critical sections.

• Implementation of simple acquire/release mechanism for locks.

• Busy waiting occurs; referred to as spinlocks.

Semaphores

• More sophisticated synchronization tool than mutex locks.

• Semaphore S: An integer variable accessed via atomic operations: wait() and signal().

• Variants include counting semaphores and binary semaphores.

Blocking Mechanism

• Semaphores can block processes when unavailable, avoiding busy waiting.

Handling Deadlocks and Starvation

• Deadlock: Processes waiting indefinitely for one another.

• Starvation: Indefinitely blocking of a process from execution due to scheduling.

• Priority Inversion: Lower-priority process holding a lock requested by a higher-priority process, solvable via priority inheritance.

Synchronization Classics

• Bounded Buffer: Producer and consumer share synchronization primitives and rules for adding/removing items from the buffer.

• Dining Philosophers Problem: Philosophers alternate between thinking and eating, needing two chopsticks to eat, leading to potential deadlock scenarios.

Monitors

• High-level abstraction that restricts access to shared variables by one active process.

• Eases process synchronization but may not cover all synchronization cases effectively.

Reading List

• 5.1 Background

• 5.2 The Critical-Section Problem

• 5.3 Peterson’s Solution

• 5.5 Mutex Locks

• 5.6 Semaphores

• 5.7 Classic Problems of Synchronization

• 5.8 Monitors