Process Synchronisation Flashcards
What is the critical section problem?
When multiple processes/threads access shared data simultaneously, leading to race conditions (unpredictable results)
Solution Requirements for the Critical Section Problem
- Mutual Exclusion: Only one process in CS at a time
- Progress: No process outside CS should block others
- Bounded Waiting: No process waits forever
How does Peterson’s algorithm work?
Uses turn and flag[2] variables to ensure mutual exclusion for two processes
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
flag[i] = false;
What is a mutex lock?
A binary lock [acquire()/release()] that ensures only one process enters critical section
acquire() {
while (!available);
available = false;
}
release() {
available = true;
}
What is a semaphore and how does it differ from a mutex?
An integer variable with atomic “wait()” (P) and “signal()” (V) operations:
- Counting Semaphore: Tracks multiple resources
- Binary Semaphore: Acts like a mutex (0 or 1)
How does a semaphore avoid busy waiting?
Uses blocking/wakeup:
wait(S) {
S–;
if (S < 0) { block(); }
}
signal(S) {
S++;
if (S <= 0) { wakeup(P); }
}
How do semaphores solve the producer-consumer problem?
Use three semaphores:
1. mutex (1 for CS access)
2. empty (n for empty slots)
3. full (0 for filled slots)
Solution for Dining Philosophers
Allow only 4 philosophers to eat or make one pick right-first
What causes deadlock in the dining philosophers problem?
All philosophers simultaneously pick up their left chopstick, waiting indefinitely for the right one.
Deadlock vs Starvation
- Deadlock: Two+ processes wait forever for each other’s resources
- Starvation: A process is indefinitely denied resources
What is a monitor in synchronisation?
A high-level construct where methods auto-synchronise (only 1 thread executes at a time)
monitor Account {
int balance;
method deposit() {…}
}
What’s a monitor?
A class-like structure ensuring only one thread executes its methods at a time
+ No manual lock management
- Less flexible than semaphores
