Synchronization Notes

Concurrency

  • Processes execute interleaved in time, creating the illusion of simultaneous execution.

  • Benefits include increased processing efficiency.

  • Issues include allocation of processor time, communication, synchronization, and resource sharing.

Difficulties of Concurrency

  • Competition: Interleaved operations cause race conditions.

  • Sub-optimal Allocation: Resources may remain unused, leading to deadlocks.

  • Non-deterministic behavior: Debugging is difficult due to unpredictable scheduling.

Resource Competition

  • Lack of coordination may lead to inconsistencies.

  • Shared data state depends on the last update.

  • Need for synchronization: Requires careful ordering and sequencing of actions.

Synchronization of Processes

  • Mutual Exclusion: Avoid simultaneous resource access.

  • Condition synchronization: Enforce a strict sequence of actions.

Example

  • Demonstrates how context switches can lead to incorrect results when process2's result is overwritten by process1.

Race Condition

  • Occurs when multiple processes read and write shared data.

  • Final result depends on execution order.

  • Scheduling: Context switches at arbitrary times.

  • Outdated copies of data: Processes operate with stale memory values.

Critical Section

  • Code that accesses a shared resource.

Critical Section Protocol

  • Entry section: Request permission to enter.

  • Exit section: Communicate leaving the critical section.

Critical Section Problem

  • Avoid race conditions.

  • Enforce mutual exclusion.

  • Avoid deadlock and starvation.

Achieve Mutual Exclusion

  • Ensure one process finishes its critical section, even if pre-empted.

  • Other processes must wait.

Implementing Mutual Exclusion

  • Shared lock variables: Use shared locks with busy waiting.

  • Higher operating system constructs: Semaphores, Monitors, message passing.

Implementing Mutual Exclusion (Details)

  • Busy waiting: Process continuously checks for lock availability, consuming CPU cycles.

Deadlock and Starvation

  • Deadlocks: Processes wait forever for resources.

  • Starvation: A process waits forever to enter its critical section.