1/25
questions 34-41
Semaphores
A unified, low level but efficient signaling mechanism for mutual exclusion and condition synschronization
Semaphore operations
P, take the lock (Decrease value)
V to release the lock (Increase value)
What should the initial semaphore value be?
Non-negative
The semaphore P operation suspends the calling process if there is at least one process waiting on the semaphore
True
The V operation on a semaphore suspends the calling thread if there are no threads waiting on the semaphore
False
Binary Semaphore
Takes the value 1 or 0
Used as mutex lock and signaling flags
General (counting) semaphore
Takes any nonnegative interger value
Serves as a resource counter
Signaling Semaphores
A binary semaphore that is used as a flag for signaling events or conditions
The technique of passing between processes the right to execute with mutual exclusion
Passing the baton
Passing-the-Baton Technique
A signaling proc (s) passes ownership of the mutex semaphore to the waithing proc (W) by using the signaling semaphore

Will the program terminate always, sometimes or never?
Sometimes

If the program terminates, what are the possible final values of Z?
If the program terminates, Z == { 1, 2, 3 }
Split Binary Semaphores
A set of binary semaphores where at most one semaphore is 1 at a time
Solutions for Dining philosophers problem
Odd numbered philosopher get their right then left forks, and even-numbered get their left then right forks
Limit the number of eating philosophers to n-1 at a time
Livelock is the busy-waiting analog of deadlock
True
What is the role of semaphores in process synchronization?
Semaphores are used to control access to shared resources and coordinate process execution order.
What can cause a race condition in a semaphore-based synchronization implementation?
A race condition can occur if multiple processes modify shared variables or signals in an unpredictable order, leading to unintended behavior.

Based on the provided implementations in the image, why is Implementation B correct while Implementation A is incorrect?
Implementation A has a race condition due to improperly ordered semaphore signals. Implementation B correctly orders the signals, ensuring proper synchronization using a "passing the baton" approach.

How can the await statement be executed atomically in this implementation?
By ensuring that all critical sections in processes accessing variables in B or S are protected with the entry semaphore e, using P(e); critical section; V(e);.

What happens to the delay counter nd when all signalled processes exit their instances of the await statement?
nd is 0, but the delay semaphore d may have an arbitrary positive value
What is weakly fair scheduling in the context of process synchronization?
Weakly fair scheduling ensures that if a process keeps requesting access to a resource infinitely often, it will eventually get access.
What can cause a semaphore-based wait loop to never terminate?
If the condition being waited on is never met or if scheduling is unfair, a process may remain indefinitely blocked.
What is the difference between a binary semaphore and a counting semaphore?
A binary semaphore (mutex) can only take values 0 or 1, while a counting semaphore can have values greater than 1 to allow multiple processes to proceed.
Unconditional fair scheduling policy
If every unconditional atomic action that is eligible is executeted eventually
Strongly fair scheduling policy
If it is unconditionally fair and if each eligible condtional atomic action is executed eventually, assuming that the condition is infinitely often true
Load Balancing
The act of assigning even work load to every process in a concurrent program