Chapter 6+7 Flashcards
(34 cards)
Why can disabling interrupts frequently affect system clock?
Clock updates occur via timer interrupts. Disabling interrupts prevents clock updates causing time drift. Minimize by keeping interrupt-disabled periods very short.
What is busy waiting and what other waiting types exist?
Busy waiting: continuously checking condition in loop wasting CPU. Other types: blocking (process sleeps) interrupt-driven waiting. Can’t avoid entirely but can minimize.
Why are spinlocks inappropriate for single-processor but good for multiprocessor?
Single-processor: spinning process prevents lock holder from running. Multiprocessor: other cores can run lock holder while one core spins.
How can non-atomic wait() and signal() violate mutual exclusion?
Two processes could read semaphore value simultaneously both see 1 both decrement creating race condition allowing both into critical section.
How does binary semaphore implement mutual exclusion among n processes?
Initialize semaphore to 1. Each process calls wait() before critical section signal() after. Only one process can have semaphore at 0.
What race condition exists in banking deposit/withdraw scenario?
Both read same balance concurrently perform calculations write back results. One update lost. Solution: use locks around entire read-modify-write sequence.
What data has race condition in concurrent stack operations?
The ‘top’ variable and stack array elements. Multiple threads can modify top simultaneously corrupting stack state.
How to fix stack race condition?
Move acquire()/release() calls to surround entire operation in push/pop. Fix is_empty() to also use locking or make it atomic.
Are there race conditions in parallel array summing code?
No race conditions. Each iteration synchronizes before next begins. Each element written by only one processor at each level.
Does compare-and-compare-and-swap idiom work for spinlocks?
Yes it works correctly. First check avoids unnecessary compare_and_swap calls when lock unavailable improving performance on bus traffic.
What three requirements must Dekker’s algorithm satisfy?
Mutual exclusion: only one in critical section. Progress: processes not in critical section can’t prevent entry. Bounded waiting: waiting time is limited.
Where are memory barriers needed in Dekker’s algorithm?
Before flag assignments and after turn assignments to ensure proper memory ordering preventing reordering optimizations.
How to implement acquire() with compare_and_swap?
while(compare_and_swap(&mutex->available 0 1) != 0); // spin until successfully change 0 to 1
How to implement release() with compare_and_swap?
mutex->available = 0; // simply set back to available state
When is spinlock better than mutex lock?
Short duration locks: spinlock avoids context switch overhead. Multiprocessor systems where other cores can run while spinning.
When is mutex lock better than spinlock?
Long duration locks: sleeping threads don’t waste CPU cycles. Single processor systems. When thread may sleep while holding lock.
Which is more efficient: mutex or atomic operations for hit counter?
Atomic operations more efficient. Single instruction vs multiple instructions for mutex acquire/release plus no context switch risk.
How can semaphores limit server connections?
Initialize semaphore to N (max connections). Each new connection calls wait() on semaphore. Connection close calls signal(). Blocks when N connections reached.
How is deadlock possible in dining philosophers?
Each philosopher picks up left fork then waits for right fork. If all pick up left simultaneously all wait for right fork creating circular wait deadlock.
Why can’t process hold spinlock while acquiring semaphore in Linux?
Spinlock disables preemption. If semaphore unavailable process would spin forever since it can’t be scheduled out to let semaphore holder run.
What is difference between spinlock and blocking lock?
Spinlock: process actively waits consuming CPU cycles but no context switch. Blocking: process sleeps releases CPU requires context switch.
How does atomic compare_and_swap work?
Atomically compares memory location with expected value. If equal updates with new value returns old value. If not equal returns current value unchanged.
What is critical section problem?
Ensuring only one process executes in critical section at time while allowing progress and preventing indefinite postponement.
What are Peterson’s algorithm requirements?
Mutual exclusion progress and bounded waiting using only shared memory and no special hardware instructions.
