At the lowest level, the primitives we have to build our synchronization on are usually some hardware instruction such as test-and-set, and disabling interrupts. Building up from test-and-set implies that there will be some amount of busy-waiting on the lock variable. Building up on interrupts means that we'll miss some of the clock ticks and the system will get behind. Neither one is very pleasant. The usual answer is to use busy waiting, but only in very limited doses, as in the implementations of P() and V() that were discussed in section on 1/28. If the wait is thought to be short, busy waiting is an acceptable technique.
2. We need to show that, if Pi is in its critical section and Pk (k != i) has already chosen its number[k] != 0, then (number[i], i) < (number[k], k).
Suppose the assumptions above are true but that (number[i], i) >= (number[k], k). But Pi made it past the statement that said "while number[j] != 0 and (number[j],j) < (number[i], i) do no-op." When that statement was evaluated at j = k, Pi should have done no-ops until Pk had entered and exited the critical section. However, we know that Pi entered first while Pk waited. Therefore (number[i], i) < (number[k], k).
3. First, let's restate Dekker's algorithm. It goes like this: if Pi wants to get into the critical section, first it sets the "I want in" bit (flag[i]). Then it checks to see if Pj also wants to get in, by looking at flag[j]. As long as flag[j] is set, if it's j's turn, Pi cancels its request, waits until it's not j's turn any more, and then resubmits its request. When j's flag is finally unset, then i can proceed into the critical section. When it has finished, it sets the turn back to j and unsets its flag. Now, the three requirements for the critical section problem are:
5. The system clock is often implemented by incrementing some counter every time the clock interrupt fires. If interrupts are disabled, then the clock interrupt won't fire, and the clock won't be updated. It will begin to lose time. One way to avoid this is to "cheat" on the interrupt disabling implementation, and just cause the section of code which couldn't be interrupted to roll back if it is in fact interrupted.
6. Wait consists of the following operations: 1) decrement the counter; 2) test the counter; 3) if it's negative, then 3a) add yourself to the queue and 3b) block. Suppose wait were not executed atomically. Let t1 and t2 be two threads trying to enter the critical section.
counter is 1; t1 and t2 have started wait()
t1 loads counter
t2 loads counter
t1 decrements and stores it; counter is 0
t2 decrements and stores it; counter is still 0
t1 and t2 are both in the critical section at the same time
Signal consists of the following operations: 1) increment the
counter; 2) test the counter; 3) if it's negative or zero, then 3a)
remove a thread from the queue and 3b) wake it up. Suppose
signal were not executed atomically. Let t1 and t2 be threads
that want to get into the critical section and let t3 be a thread in
the critical section.
t3 is in the critical section; counter is 0
t3 loads the value of the counter
t1 waits; counter is -1
t3 increments and stores the counter; counter is 1
t3 wakes up t1; t1 enters
t2 waits; counter is 0
t1 and t2 are both in the critical section at the same time
9. Monitors, conditional critical regions, and semaphores are all equivalent.
Semaphores are at least as powerful as conditional critical regions because we can implement CCRs using semaphores. The code to implement "region x when B do S" is listed in the book on page 181, in figure 6.18.
Conditional critical regions are at least as powerful as monitors because we can implement monitors using CCRs. To implement a monitor, we need one way for threads to block on entry, and another place to block for each condition variable. Suppose we have a monitor which looks like this:
type MonitoredModule = monitor
var x: condition;
procedure entry P1(...);
begin P1stuff; end;
procedure entry P2(...);
begin P2stuff; end;
procedure entry Pn(...);
begin Pnstuff; end;
Then write your CCR'd code like this:
var modulevar, condx, boolx;
procedure P1(...);
begin
region modulevar when true do P1stuff;
end;
procedure P2(...);
begin
region modulevar when true do P2stuff;
end;
procedure Pn(...);
begin
region modulevar when true do Pnstuff;
end
And any time you would have used x.wait(), do this instead:
region condx when boolx do XWaitstuff;Similarly, any time you would have used x.signal(), do this instead:
boolx = true;Finally, monitors are at least as powerful as semaphores because we can implement semaphores using monitors. A semaphore needs a counter and a queue for waiters. Here's the monitor to do it:
type SemaphoreModule = monitor
var counter: int;
var queue: condition;
procedure entry P(self);
begin
if(counter == 0)
queue.wait;
counter--;
end
procedure entry V();
begin
counter++;
queue.signal;
end
Since each of these three synchronization constructs is at least as
powerful as the next, we have proven that they all have equivalent
power. The implication is that, given any one of these three, you can
implement either of the others.13. We want a monitor to allocate line printers to prioritized processes. Assume no resource preemption.
type LinePrinterAllocator = monitor
var counter: int;
var prioritywait: array [0..n] of condition;
var state: array [0..n] of (printing, waitingtoprint, neither);
procedure init;
begin
counter := 3;
for(i=0 to n) state[i] := neither;
end
procedure entry grabprinter(i);
begin
if(counter == 0)
state[i] := waitingtoprint;
prioritywait[i].wait;
counter--;
state[i] := printing;
end
procedure entry releaseprinter(i);
begin
counter++;
state[i] := neither;
for(i=0 to n)
if(state[i] == waitingtoprint)
prioritywait[i].signal;
break;
end