Classic Synchronization Problems Flashcards
What are the 3 classic synchronization problems?
- Producer-Consumer AKA bounded-buffers
- Readers-Writers
- Dining-Philosophers
The classic synchronization problems are ________ that can be used to model money ______ ________ problems
abstractions, resource, sharing
The classic synchronization problems can be used to _______ newly proposed synchronization problems
test
In the bounded-buffer problem, what do producers and consumers do, and where?
producers insert into a buffer, and consumers remove from buffer
In the bounded-buffer problem, it is possible to have _________ producers and consumers
multiple
In the bounded-buffer problem, what are 3 issues?
- Violation of buffer structure
- Producing when full
- Consuming when empty
In the bounded-buffer problem, the solution uses ______ semaphores
three
In the bounded-buffer problem, what are the 3 semaphores used in the solution called, and what are they initialized to?
- mutex: 1
- full: 0
- empty: N
In the bounded-buffer problem, the producer ________ full and _________ empty
increments, decrements
In the bounded-buffer problem, there is a _______ between producers and consumers
symmetry
In the readers-writers problem, _____ is shared among multiple processes
data
In the readers-writers problem, readers only _____ and do not perform any ________
read, updates
In the readers-writers problem, writers can _____ and ________
read, write
In the readers-writers problem, what are the 2 requirements for a solution?
- Allow multiple concurrent readers and no writer
- Allow one writer and no reader
In the readers-writers problem, a solution as provided by the OS and runtime libraries called __________ in Pthread
pthread_rw_lock*
In the readers-writers problem, a process can ask for ______________ lock either in read or write mode
readers-writes
In the readers-writers problem, when should you use reader-writer locks? (2 reasons)
- When it’s easy to identify readers and writers
- When there are more readers than writers
reader-writer locks are more ________ to implement than mutex
complex
reader-writer locks have more _________ because of coordination between readers and writers
overhead
Why do reader-writer locks have high concurrency?
They allow multiple readers
In the reader-writer lock struct, what 3 values are there, and what are they initialized to?
- read_count: 0
- rw_mutex: 1
- mutex: 1
In the reader-writer lock struct, what does read_count do?
tracks the number of reader holding the lock
In the reader-writer lock struct, the rw_mutex allows either many _______ or one _______
readers, writer
In the reader-writer lock struct, the mutex protects __________
read_count
The dining philosophers problem models ________ processes sharing __________ resources
multiple, multiple
What is the goal of the dining philosophers problem?
To coordinate forks utilization among all philosophers
In the dining philosophers problem, a broken solution is to use one ________ per fork. This causes a _________ when all philosophers grab their left forks at the same time
semaphore, deadlock
In the dining philosophers problem, what are 3 working solutions?
- require at least one philosopher acquire forks in a different order
- timeout + retry
- make sure no neighbours are eating (using condition variables)
What are 2 functions condition_variable x has?
x. wait()
x. signal()
condition_variable x.wait() ______ the calling thread
suspends
condition_variable x.signal() ______ the one of ANY process that invoked wait
resumes
A _______ is an abstract data type for synchronization
monitor
A monitor __________ mutual exclusion operations
encapsulates
A monitor only has one active ______ within it
process
A monitor is implemented using ________ internally
semaphores
A ________ priority process must wait if the resource it requires is being used by a __________ priority process
higher, lower
Imagine a scenario with processes PL, PM, and PH and PL has a resource desired by PH. PL is running first. What happens when PM becomes runnable? What is this event called?
PM preempts PL, affecting the waiting time for PH. This is called a Priority inversion
Imagine a scenario with processes PL, PM, and PH and PL has a resource desired by PH. PL is running first. How do we prevent PM from affecting PH’s waiting time? What is this called?
PL inherits H since PH is waiting on resource held by PL so PM cannot preempt. This is called priority inheritance.
