Week 10: Semaphores Flashcards
What is a race condition?
A situation where the outcome depends on the sequence or timing of processes accessing shared resources.
How can race conditions be prevented?
By ensuring only one process accesses a shared resource at a time (mutual exclusion).
What is a critical section?
A part of a process that accesses shared resources
Why does using a critical_region flag fail?
A process may be interrupted between checking and setting the flag, allowing another process to enter the critical section.
Why does disabling interrupts fail as a solution?
It:
- Cannot work in multi-processor
- Risks forgetting to re-enable
- May be abused by selfish users.
What does strict alternation enforce?
Processes take turns entering their critical sections based on a shared turn variable.
What are the drawbacks of strict alternation?
It forces processes to wait unnecessarily and prevents a process from entering its critical section twice in a row.
What is Peterson’s solution?
A mutual exclusion algorithm with the following variables:
Each process has an integer id number
Two shared variables are needed:
- turn: Indicates whose turn it is.
- interested[]: Flags whether a process wants to enter its critical section.
Each process must know the other’s process id
Why is Peterson’s solution effective?
It combines lock variables with turn-taking, ensuring fairness and preventing simultaneous access.
What is busy waiting?
A process repeatedly checks a condition in a loop, wasting CPU time.
Why is busy waiting problematic?
It wastes resources and may prevent lower-priority processes from running in priority scheduling systems.
What is the purpose of the sleep and wakeup system calls?
To prevent busy waiting by blocking a process (sleep) until it is explicitly awakened (wakeup) by another process.
What is the difficulty with using sleep and wakeup?
A wakeup call can be lost if it occurs before the sleeping process actually starts sleeping, leading to deadlocks.
What is the producer-consumer problem?
A synchronization problem where a producer adds data to a shared buffer, and a consumer removes it, requiring coordination to avoid overflows and underflows.
How do sleep and wakeup address the producer-consumer problem?
The producer sleeps if the buffer is full, and the consumer wakes it up when space is available, and vice versa.
What is a semaphore?
A primitive introduced by E.W. Dijkstra, used for synchronization and mutual exclusion, with two atomic operations: down and up.
How does down work?
It decrements the semaphore value if it’s greater than zero; otherwise, the process blocks.
How does up work?
It increments the semaphore value and wakes up a waiting process if any are blocked.
How are semaphores used in the producer-consumer solution?
- (binary) semaphore mutex: Ensures mutual exclusion for buffer access.
- semaphore empty: Tracks empty slots in the buffer.
- semaphore full: Tracks filled slots in the buffer.
Why is atomicity important for semaphores?
To ensure that no process can interrupt another during a semaphore operation, preventing race conditions.
How can semaphores be implemented?
By disabling interrupts or using hardware instructions like test-and-set-lock (TSL).
What is the TSL instruction?
A hardware instruction that atomically tests and sets a memory value, ensuring mutual exclusion during semaphore operations.
How does TSL work?
It reads a memory value and sets it simultaneously, preventing other processes from accessing it until the operation is complete.
