Process Synchronization
When several threads touch shared data, the result can depend on timing. That is a race condition.
race.py
import threading
counter = 0
def work():
global counter
for _ in range(100_000):
counter += 1 # read-modify-write is NOT atomic
threads = [threading.Thread(target=work) for _ in range(4)]
[t.start() for t in threads]; [t.join() for t in threads]
print(counter) # may be less than 400000
The critical-section problem
A solution must provide:
- Mutual exclusion: only one process in the critical section.
- Progress: a decision about who enters cannot be postponed forever.
- Bounded waiting: no process waits indefinitely.
Tools
| Tool | Description |
|---|---|
| Mutex (lock) | Binary lock; only the owner may release it |
| Semaphore | Integer counter with atomic wait (P) and signal (V); counting or binary |
| Monitor | Language construct bundling data, operations and a lock |
| Condition variable | Wait until a condition becomes true, used with a mutex |
| Atomic instructions | Test-and-set, compare-and-swap |
lock.py
lock = threading.Lock()
def safe_work():
global counter
for _ in range(100_000):
with lock: # mutual exclusion
counter += 1
Classic problems
- Producer-consumer (bounded buffer): semaphores
empty,fulland a mutex. - Readers-writers: many readers or one writer.
- Dining philosophers: shows deadlock and starvation risks.
Producer Consumer
wait(empty) wait(full)
wait(mutex) wait(mutex)
add item to buffer remove item from buffer
signal(mutex) signal(mutex)
signal(full) signal(empty)
Loading Comments...