Condition Variables, Semaphores & Deadlocks Flashcards
Condition variable signals
- wait: assumes the lock is held when wait() is called, puts caller to sleep + releases the lock (atomically), when awoken, reacquires lock before returning
- signal: wake a single waiting thread
- broadcast: wake all waiting threads
Rules of thumb for condition variables
- keep state in addition to CV’s
- always do wait/signal with lock held
- whenever thread wakes from waiting, recheck state (use “while”)
enumerate types of synchronization objectives
- spinlocks
- (counting) semaphore
- Mutex (lock)
- condition variable
summarize spinlocks’ respective
operations’ semantics
lock/unlock
uses busy waiting and atomic instructions (such as test-and-set) to ensure mutual exclusion. Wates CPU time, thus only recommended for short critical sections. Preemption is problematic, so pure spinlocks are most common in kernel code with interrupts disabled. Doesn’t make sense on single-processor systems
summarize semaphores’ respective
operations’ semantics
wait(sem)/signal(sem)
Each call to wait decrements the counter of the semaphore. If the counter falls below 0, the thread/process executing wait os blocked and appended to the semaphore’s queue. A call to signal increments the counter of the semaphore. If it is still less or equal to zero, a thread/process is removed from the queue and unblocked. The counter isn’t directly accessible for users of a semaphore.
summarize mutexes’ respective
operations’ semantics
lock(m), unlock(m)
A counting semaphore whose counter can only take values 0 or 1. Calls to signal to wake up a thread from sem’s queue
summarize condition variables’ respective
operations’ semantics
wait(cond, mutex), signal(cond)
Always used with a mutex. Allows a thread to acquire a lock, check for a certain condition, and go to sleep if the condition isn’t met. The lock is automatically released when the thread is blocked and reacquired when the thread is unblocked.
Condition variables vs semaphores
-CV have no state
-Semaphores have state: track integer value
which synchronization primitives can be built from others
locks from semaphores
CV from semaphores
Semaphores from locks + CV
Deadlock conditions
- Mutual exclusion: limited access to resource/ resources can’t be shared between processes
- Hold and Wait: Wait for next resource while already holding at least one
- No preemption: Once the resource is granted, it can’t be taken away but only handed back voluntarily
- Circular wait: Possibility of circularity in graph of requests
Deadlock countermeasures
- Prevention: pro-active, make deadlocks impossible to occur
- Avoidance: decide on allowed action based on knowledge
- Detection: react after deadlock happened (recovery)
What is the definition of a deadlock?
It is a situation in which several activities can’t make any progress, because each activity is waiting for a resource that is assigned to another activity, and no activity releases any of its resources.
For each condition necessary for deadlocks, give an example of how they can be prevented by breaking the condition.
Mutual Exclusion: Spooling; to avoid multiple processes from directly accessing a non-sharable resource
Hold And wait: allocate all resources atomically; once a process holds any resources, it must not allocate additional resources
No preemption: allowing resources to be revoked
Circular wait: ordering resources numerically and only allow multiple resources to be allocated in a specified order
Why is disabling interrupts a privileged instruction?
Preemptive scheduling is realized by using the timer interrupt to involuntarily enter the kernel while a user space process is executing.
If a process in user space could disable interrupts, it could gain infinite CPU time, thereby taking over the system.
