Process Synchronization Notes & Formulas

1. Definition

Mechanisms to control the order of execution when processes share resources, to prevent race conditions and ensure data consistency.

2. Race Condition

When outcome depends on the order of execution of concurrent processes.
Example: counter++ is NOT atomic - it is read, increment, write (3 steps). Concurrent access corrupts value.

3. Critical Section Problem

Requirements (must ALL hold):

1. Mutual Exclusion: At most one process in CS at a time
2. Progress: If CS is empty, a process wanting to enter must be allowed in finite time
3. Bounded Waiting: Every process must eventually enter CS - no starvation

4. Software Solutions

Peterson's Solution (2 processes - Very Important):
// Process i (j = 1-i)
flag[i] = true;
turn = j;
while (flag[j] && turn == j); // busy wait
// critical section
flag[i] = false;
Satisfies all 3 conditions for 2 processes. Requires busy waiting. Assumes atomic load/store.

5. Hardware Solutions

• Test-and-Set: Atomically read and set a lock variable
• Compare-and-Swap (CAS): Atomically compare memory value and swap if matches
• Mutex lock: Uses hardware atomic instruction internally. acquire()/release()

6. Semaphores (Very Important)

Integer variable S with two atomic operations:

• wait(S) / P(S): S--; if S < 0, block process
• signal(S) / V(S): S++; if S ≤ 0, wake one blocked process

Binary semaphore (mutex): S ∈ {0,1} - mutual exclusion
Counting semaphore: S = number of available resources - resource management

Semaphore for ordering (process B after process A):

• Initialize S = 0
• Process A: do work; signal(S)
• Process B: wait(S); do work

7. Classic Synchronization Problems (Very Important)

Producer-Consumer (Bounded Buffer):

• Semaphores: mutex=1, empty=N, full=0
• Producer: wait(empty) → wait(mutex) → add → signal(mutex) → signal(full)
• Consumer: wait(full) → wait(mutex) → remove → signal(mutex) → signal(empty)

Readers-Writers:

• Multiple readers can read simultaneously; writers need exclusive access
• First readers-writers problem: readers preferred (writers may starve)

Dining Philosophers:

• 5 philosophers, 5 forks - each needs 2 forks to eat
• Deadlock if all pick up left fork simultaneously
• Solutions: allow only 4 philosophers at table, or pick both forks atomically, or asymmetric solution (odd picks left first, even picks right first)

8. Monitors

High-level synchronization construct - only one process active inside monitor at a time.

• Condition variables: wait() and signal() operations - used for ordering within monitor
• Java synchronized methods implement monitor-like behavior

9. GATE Trick

Semaphore signal/wait order in producer-consumer: mutex must be INSIDE empty/full wait - reversing causes deadlock. Peterson's solution: memorize the flag and turn logic. Dining philosophers deadlock: all pick up one fork simultaneously - classic circular wait. Binary semaphore ≠ mutex in all implementations - binary semaphore can be signaled by any process, mutex must be released by acquirer.