OS - semaphores Flashcards
what’s wrong with busy waiting?
- wasting CPU time - but efficient if waiting-time is short because context switch takes time.
- May cause dead lock
How can busy waiting cause deadlock?
Process A’s priority is higher than process B’s
Process B enters the CS
Process A needs to enter the CS, busy-waits for B to exit the CS.
Process B cannot execute as long as the higher-priority process A is executing/ready.
What is a semaphore?
Semaphore is an object used to solve the mutual exclusion problem, which holds two atomic operations:
down(S) - if S=0, the process is blocked. else: S–;
up(S) - if there are blocked processes, wake-up one of them. else: S++
Is the following algorithm enough to provide mutex,deadlock- freedom and starvation-freedom?
down(S)
CS
up(S)
mutex - yes. Because the functions are atomic
deadlock - yes. Because the functions are atomic
starvation - depends.. we can play with it as in the attached image:
what is interesting about negative-valued semaphores? how is it implemented?
If S is negative, then there are -S blocked processes.
implementation attached.
How is a spinlock implemented using TSL(test-set-lock).
recall: spinlock does not use busy waiting.
what is the problem with the following implementation of Negative Sempahore with TSL?
In down(), resetting flag and sleeping should be atomic:
if sleep occurs first - no other process can enter test-and-set to wake up the process. If setting the flag occurs first, then we might have context switch right before we sleep. In that time some process might pass test-and-set to execute wakeup(p). then the former process would return to run to execute sleep without having someone to wake him up.
This code does not work. Why?
No counting of the waiting threads.
If 3 processes are waiting between line L1 and L2 while 3 other processes execute UP(S) completely, UP(S2) will be called three times, but since it is a binary operation - S2 = 1 by the end of the 3 calls.
When the 3 processes execute L2: Down(S2), only one should pass while the rest will be waiting even though they should have been sent free.
Can you recall the smallest change we did in the implementation of the counting sempahore with binary semaphores?
up(S): we added “else”.
down(S): we removed “else”
This changes assures up(S2) must be followed by down(S2) that must be followed by up(S2) and so on..
What is the “bounded buffer algorithm”?
clue: producer and consumer
The implementation of the counting semaphore using binary semaphores such that it alternates between up(S2) and down(S2) is problematic. with the bounded buffer, we don’t want to have producer->consumer->producer->consumer.. we want to enable a few producers/consumer to enter CS consecutively.
How this problem is fixed, remember?
Using the “wake” variable, we “remember” the number of times up(S2) has occured. this way, even if up(S2) occured a couple of times before down(S2) occured, we release all the processes sleeping on S2 according to the “wake” variable. Note that the increament and decreament of “wake” is done within the S1 semaphore, thus it is atomic like.
What is wrong about the Kearns algorithm that tries to fix the alternation problem?
Assume 8 processes execute down(S). that is, 7 sleep on down(S2). now assume another 4 processes execute up(S) making wake equal 4. now, 4 sleeping processes are released from S2, assume the first process calls up(S2) before the next one to wake up execute wake –. that is, another process has awaken if though we should have released only 4 in total.
How Hemmendinger fixed the “wake” issue?
Instead of waking all of the sleeping threads in up(S), he wakes up only one of them, but keeps the count.
Then, in down(S), the one released in responsible to free all the rest =]
In the following(working and simpler) algorithm, can we switch the order of downs in down(S)?
Of course we can’t! if down(S1) comes before down(S2), once some process is waiting on S2, we also wait on S1!
this way we can’t execute up(S2) and we’re stuck.
Does this simpler,working counting semaphore prevent starvation?
Absolutely no! there is no order for the waiting processes. process might enter down(S2) and call up(S2) and then enter again while some other process is waiting long for his turn
