Consider a sharable resource with the following characteristics: 

(1) As long as there are fewer than three processes using the resource, new processes can start using it right away. 

(2) Once there are three processes using the resource, all three must leave before any new processes can begin using it. We realize that counters are needed to keep track of how many processes are waiting and active, and that these counters are themselves shared resources that must be protected with mutual exclusion. So we might create the following solution:

The solution appears to do everything right: All accesses to the shared variables are protected by mutual exclusion, processes do not block themselves while in the mutual exclusion, new processes are prevented from using the resource if there are (or were) three active users, and the last process to depart unblocks up to three waiting processes.

a. The program is nevertheless incorrect. Explain why.

b. Suppose we change the if in line 6 to a while. Does this solve any problem in the program? Do any difficulties remain?

Transcribed Image Text:

semaphore mutex = 1, block = 0; int active = 0, waiting 1 /* share variables: semaphores, */ /* counters, and * / /* state information */ 2 = 0; 3 boolean must wait = false; 4 semwait (mutex); if (must_wait) { /* Enter the mutual exclusion */ 6 /* If there are (or were) 3, then */ ++waiting; /* we must wait, but we must leave */ semsignal (mutex); /* the mutual exclusion first */ 8. 9. semwait (block) ; /* Wait for all current users to depart */ 10 Semwait (mutex) ; /* Reenter the mutual exclusion */ 11 --waiting; /* and update the waiting count * / 12 } 13 ++active; /* Update active count, and remember */ 14 must_wait = active == 3; /* if the count reached 3 */ 15 semsignal (mutex); /* Leave the mutual exclusion */ 16 17 /* critical section */ 18 19 semWait (mutex) ; /* Enter mutual exclusion */ 20 --active; /* and update the active count */ 21 if (active == 0) { /* Last one to leave? */ 22 int n; if (waiting < 3) n = waiting; 23 24 else n = 3; /* If so, unblock up to 3 */ while ( n >0 ) { /* waiting processes */ 25 26 semsignal (block) ; 27 --n; } must wait - false; 28 29 /* All active processes have left */ 30 31 semsignal (mutex) ; /* Leave the mutual exclusion */