Concurrency control Flashcards
What is the bounded-buffer/producer-consumer problem?
Process produces data, process consumes data.
Production and consumption rates may vary - shared buffer absorbs variations
What is the dining philosophers?
Share a round table, need two chopsticks to eat. Pick up closest chopstick one at a time, no-one eats = deadlock.
What is the Reader and writers problem?
DB shared between processes, in which one PS reads and the other writes. Reader may read partially written data.
What is a critical section?
Part of a program that accesses shared data.
Must ensure that only one process can be executing in a critical section at a given time.
How do we avoid race conditions?
Design a protocol for process cooperation.
lock
critical section
unlock
How can we avoid race conditions?
- Atomic instructions
- Interrupts
- Kernel scheduler
- Concurrency control mechanisms
How do Atomic Instructions help to avoid race conditions?
HW support for implementing lock, acquire lock on entry and release lock on exit
How do we prevent concurrency?
Single processor: Disable interrupts during wait and signal operations
Multiple processors: Secondary mutual exclusion algorithm, involves busy waiting.
Basically, spin when there’s nothing to do
What is a semaphore?
Used to implement different synchronisation mechanisms.
Can avoid busy-waiting
How do binary semaphores work?
Integer restricted to 0 or 1.
Known as a mutex
How do counting semaphores work?
Starts with amount of resources and decrements/increments when they are removed/readded
What are the atomic operations
Wait: Delays the calling process integer > 0, then decrements it
Signal: Increment integer
What is special about a mutex?
It is shared between all cooperating processes.
How are bounded-buffers used concurrently?
Mutual exclusion on the buffer pool, can’t be read & written simultaneously. Synchronised when buffer is empty or full.
How do we get R/W concurrency
Mutual exclusion for writers, as many readers as wanted.
What is a monitor?
Implements concurrency control at the language level.
Compiler generates concurrency control code
How do condition variables work with monitors?
Condition variables allow for tailor-mode synchronisation schemes based on condition X
What operations work on monitors?
Wait: x.wait() means calling process is suspended
Signal: x.signal() runs waiting process
Process Q has called wait on condition x. Process P signals condition X. What are the possible outcomes?
Signal and wait : P waits for Q to leave the monitor
Signal and continue: Q waits for P to leave the monitor
P leaves the monitor immediately.
Why do we need kernel pre-emption?
Kernels have to handle concurrency; interrupts, system calls and multiple CPU’s.
All can leave the kernel in an inconsistent state
