Race Condition and Critical Section

A race condition occurs when multiple processes access and manipulate shared data concurrently, and the outcome depends on the order of execution. This leads to inconsistent results.

Example: Two processes both read a counter (value=5), both increment it, and both write back. Result: 6 instead of 7.

The critical section is the part of code where shared resources are accessed. The critical section problem requires a solution that satisfies:

• Mutual Exclusion: Only one process can be in its critical section at a time
• Progress: If no process is in its critical section, a process that wants to enter must be allowed to do so
• Bounded Waiting: There must be a limit on how many times other processes can enter their critical sections before a waiting process is allowed in

Peterson's Solution

A software-based solution for two processes. Uses two shared variables: flag[2] (indicates intent to enter) and turn (whose turn it is).

• Satisfies all three requirements for two processes
• Not practical for modern hardware (memory reordering issues)
• Important for understanding the concept

Semaphores

A semaphore is an integer variable accessed only through two atomic operations: wait() (P) and signal() (V).

• wait(S): Decrement S. If S < 0, block the process.
• signal(S): Increment S. If S <= 0, wake up a blocked process.

Binary Semaphore (Mutex): Value is 0 or 1. Used for mutual exclusion. Equivalent to a mutex lock.

Counting Semaphore: Value can be any non-negative integer. Used to control access to a resource with multiple instances.

Mutex

A mutex (mutual exclusion lock) is a binary semaphore used to protect critical sections. A process must acquire the mutex before entering the critical section and release it when done.

• acquire(): Lock the mutex (blocks if already locked)
• release(): Unlock the mutex
• Only the process that acquired the mutex can release it (ownership)

Monitors

A monitor is a high-level synchronization construct that encapsulates shared data and the procedures that operate on it. Only one process can be active inside a monitor at a time.

• Provides mutual exclusion automatically
• Uses condition variables for signaling: wait() and signal()
• Easier to use correctly than semaphores
• Used in Java (synchronized keyword), Python (threading.Condition)

Classic Synchronization Problems

Producer-Consumer (Bounded Buffer): Producer adds items to a buffer; Consumer removes items. Problem: Producer must wait if buffer is full; Consumer must wait if buffer is empty. Solution: Use semaphores (empty, full, mutex).

Readers-Writers: Multiple readers can read simultaneously; writers need exclusive access. Problem: Readers may starve writers or vice versa. Solution: Use semaphores with priority rules.

Dining Philosophers: Five philosophers sit at a table with five forks. Each needs two forks to eat. Problem: All pick up left fork simultaneously -> deadlock. Solutions: Allow only 4 philosophers at a time, use asymmetric solution (odd picks left first, even picks right first), use a monitor.

Hardware Solutions

• TestAndSet: Atomic instruction that reads a variable and sets it to true in one uninterruptible operation. Used to implement mutex locks.
• Compare-And-Swap (CAS): Atomic instruction that compares a memory location with an expected value and, if equal, replaces it with a new value. Foundation of lock-free data structures.
• Disabling Interrupts: Disable interrupts before entering critical section, re-enable after. Simple but dangerous (can't be used in user mode, doesn't work on multiprocessors).

---