Synchronization Notes

Synchronization Overview

  • Importance of synchronizing processes and threads in sharing data.
  • Example scenario involving producer and consumer threads illustrating the need for data integrity.

Need for Process/Thread Synchronization

  • Shared Data: Processes/threads depend on the integrity of shared data.
    • Example: Producer and consumer share a buffer and count.
    • Issues: Concurrent access leads to data corruption and undefined behavior without synchronization mechanisms.

Producer-Consumer Example

  • Producer Function:
    • Continuously produces items and places them in a buffer until the buffer is full.
    • Checks if buffer is full: while (count == BUFFER_SIZE) { }.
  • Consumer Function:
    • Continuously consumes items from the buffer until it is empty.
    • Checks if buffer is empty: while (count == 0) { }.
  • Buffer Management: Variables in, out, and count manage the buffer and the number of items.

Critical Section Concept

  • Critical Section: Code section where shared resources are accessed.
    • Entry and Exit Management: Requires extra code to handle access to critical sections, ensuring only one thread or process can execute at a time.
  • Properties of a Good Protocol for Critical Sections:
    1. Mutual Exclusion: Only one process in critical section.
    2. Progress: No indefinite postponement for processes wanting to enter the critical section.
    3. Bounded Waiting: No process should wait forever to enter; a limit on the number of entries for other processes.

Race Conditions

  • Occurs when multiple processes manipulate shared data elements and the outcome depends on execution order.
  • Need for synchronization to prevent such conditions.

Peterson's Algorithm

  • Description: A software-level solution to the critical section problem.
  • Data Structures used:
    • Boolean flags to indicate interest in entering the critical section.
    • A turn variable to indicate whose turn it is to enter.
  • Mechanism: Processes must check their flags and turn before entering the critical section, ensuring mutual exclusion.

Problems with Traditional Software Solutions

  • Modern Processors Issues: Out-of-order execution and speculative execution can undermine synchronization.
  • Hardware Solutions: Utilize atomic operations, such as Test-and-Set and Compare-and-Swap to avoid race conditions.

Spinlocks and Busy Waiting

  • Definition of Spinlock: Threads enter busy wait if they cannot acquire the critical section.
  • Drawbacks: High CPU consumption during waits.
  • Alternative: Use mutex locks that put threads to sleep when access to critical sections is denied.

Semaphores

  • Definition: Counters controlling access to shared resources.
  • Types:
    • Binary Semaphores: Value of 0 or 1 for mutual exclusion.
    • Counting Semaphores: Allows counting permits/resources.
  • Mechanism: Uses queues to manage waiting processes when no permits are available.

Producer-Consumer Synchronization with Semaphores

  • Three Synchronization Types Needed:
    1. Binary Semaphore for mutual exclusion.
    2. Counting Semaphore for producer waits in full buffers.
    3. Counting Semaphore for consumer waits in empty buffers.

Issues with Semaphores

  • Complexity: Ordering errors can lead to deadlocks or starvation scenarios in multi-threading environments.

Monitors

  • Definition: Synchronization construct that abstracts semaphore complexities.
  • Features of a Monitor:
    1. Shared data management.
    2. Operations requiring safe access.
    3. Automatic locking mechanisms ensuring singular access to shared data.
    4. Conditional variables for waiting threads.