M7: Concurrency Control and Synchronization Flashcards
Test-and-set lock:
a hardware instruction that locks memory locations while they are being accessed by a process.
Race condition
the system attempts to perform two or more operations at the same time, but due to the underlying context switching and scheduling implementations by the OS, the ordering of these operations is not guaranteed. The result of the operations changes as a function of changes in ordering.
Semaphore
a semaphore is a kernel object with an integer value. It supports two operations, P and V, which modify the integer value.
○ P : One of the operations of a semaphore. If the semaphore’s value is greater than zero, decrement. Otherwise, wait until the value is greater than zero and then decrement. Sometimes it is also called wait.
○ V : One of the operations of a semaphore. Increment the value of the semaphore. Sometimes it is also called signal or post.
Binary semaphore
a semaphore that saturates at an integer value of
1 -> Mutex
Counting semaphore:
semaphore that saturates as an integer value
of N, for N greater than or equal to 1.
Waiting queue
processes or threads waiting to enter the critical section are notified, or “woken up”, when the process currently using the critical section exits. This strategy helps eliminate the need for busy waiting in the
semaphore implementation.
Deadlock :
two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes.
Monitors
a high-level abstraction that provides a convenient and effective mechanism for process synchronization. Only one process may be active within the monitor at a time.
Condition variables
a primitive with two functions, wait and signal.
○ Wait : a condition variable function called by a process that waits for a condition to be true
○ Signal : a condition variable function that wakes up a process waiting on the condition to be true
Why is Busy Waiting Bad
1) Consume CPU resources
2) can lead to starvation if waiting process has higher prior in scheduler. Constantly running high prio process that just waits and consumes CPU time
Why does lost wake up problem arise
Race Condition. Going to sleep vs. wakeup signal
The buffer is empty and the consumer has just read count to see if it is 0. At that instant, the scheduler decides to stop running the consumer temporarily and start running the producer. The producer inserts an item in the buffer, increments count, and notices that it is now 1. Reasoning that count was just 0, and thus the consumer must be sleeping, the producer calls wakeup to wake the consumer up.
Unfortunately, the consumer is not yet logically asleep, so the wakeup signal is lost. When the consumer next runs, it will test the value of count it previously read, find it to be 0, and go to sleep. Sooner or later the producer will fill up the buffer and also go to sleep. Both will sleep forever
For what are binary semaphores/mutexes used
manage mutual exclusion, handle access to Critical Section
Potential approach to solve deadlock with semaphores
Impose hierarchy between resources. e.g. always pick resources in alphabetical order.
How is it possible that no context switch happens with semaphores given that involves several steps
operating system briefly disables all interrupts while it is testing the semaphore, updating it, and putting the process to sleep/waking up
How can Semaphores be protected if we are using multiple CPUs
each semaphore should be protected by a lock variable, to make sure that only one CPU at a time examines the semaphore
