semaphore U = 3; semaphore V = 0; [Process 1] [Process 2] [Process 3] L1:wait(U) L2:wait(V) L3:wait(V) type("C") type("A") type("D") signal(V) type("B") goto L3 goto L1 signal(V) goto L2Within each process the statements are executed sequentially, but statements from different processes can be interleaved in any order that's consistent with the constraints imposed by the semaphores. When answering the questions below assume that once execution begins, the processes will be allowed to run until all 3 processes are stuck in a wait() statement, at which point execution is halted.
start: U=3 V=0 type C: U=2 V=1 type A: U=2 V=0 type B: U=2 V=1 type A: U=2 V=0 type B: U=2 V=1 type D: U=2 V=0 type D: oops, impossible since V=0
start: U=3 V=0 type C: U=2 V=1 type A: U=2 V=0 type B: U=2 V=1 type A: U=2 V=0 type C: U=1 V=1 type D: U=1 V=0 type B: U=1 V=1 type C: U=0 V=2 type A: U=0 V=1 type B: U=0 V=2 type D: U=0 V=1 type D: U=0 V=0
Process A Process B int Y; int Z; A1: Y = X*2; B1: Z = X+1; A2: X = Y; B2: X = Z;X is set to 5 before either process begins execution. As usual, statements within a process are executed sequentially, but statements in process A may execute in any order with respect to statements in process B.
A1 A2 B1 B2: X = 11 A1 B1 A2 B2: X = 6 A1 B1 B2 A2: X = 10 B1 A1 B2 A2: X = 10 B1 A1 A2 B2: X = 6 B1 B2 A1 A2: X = 12
Process A Process B int Y; int Z; wait(S); wait(S); A1: Y = X*2; B1: Z = X+1; A2: X = Y; B2: X = Z; signal(S); signal(S);S is set to 1 before either process begins execution and, as before, X is set to 5. Now, how many different values of X are possible after both processes finish executing?
A1 A2 B1 B2: X = 11 B1 B2 A1 A2: X = 12
Process A Process B int Y; int Z; A1: Y = X*2; B1: wait(T); A2: X = Y; B2: Z = X+1; signal(T); X = Z;T is set to 0 before either process begins execution and, as before, X is set to 5. Now, how many different values of X are possible after both processes finish executing?
A1 A2 B1 B2: X = 11
Process A Process B ... ... A1: tempA = counter + 1; B1: tempB = counter + 2; A2: counter = tempA; B2: counter = tempB; ... ...The variable "counter" initially has the value 10 before either process begins to execute.
A1 A2 B1 B2: X = 13 A1 B1 A2 B2: X = 12 A1 B1 B2 A2: X = 11 B1 A1 B2 A2: X = 11 B1 A1 A2 B2: X = 12 B1 B2 A1 A2: X = 13
semaphore sync = 1; Process A Process B wait(sync); wait(sync); A1: tempA = counter + 1; B1: tempB = counter + 2; A2: counter = tempA; B2: counter = tempB; signal(sync); signal(sync);
A1 B1 \ / B2 | A2
semaphore s1 = 0; semaphore s2 = 0; Process A Process B A1: tempA = counter + 1; B1: tempB = counter + 2; signal(s1); wait(s1); wait(s2); B2: counter = tempB; A2: counter = tempA; signal(s2);
Process P Process Q N = 5; Sqr = 0; loopP: loopQ: if (N==0) Sqr = Sqr + 2*N + 1; goto endP; N = N - 1; goto loopQ; goto loopP; endP: print(Sqr);
Semaphore P = 1; // P gets first shot at execution Semaphore Q = 0; // Q has to wait for first N value int N, Sqr; Process P Process Q N = 5; Sqr = 0; loopP: loopQ: if (N==0) wait(Q); goto endP; Sqr = Sqr + 2*N + 1; wait(P); signal(P); N = N - 1; goto loopQ; signal(Q); goto loopP; endP: wait(P); // wait for last Q iteration! print(Sqr);Optionally, you could also split Sqr = Sqr + 2*N + 1 into Sqr = Sqr + 1 and Sqr = Sqr + 2*N to slightly improve concurrency.
semaphore S=???; /* Shared semaphore. */ A_Enter() /* Handle gerbil entering tube via A */ { wait(S); } A_Leave() /* Handle gerbil leaving tube via A */ { signal(S); } B_Enter() /* Handle gerbil entering tube via B */ { wait(S); } B_Leave() /* Handle gerbil leaving tube via B */ { signal(S); }
semaphore mutex=1; struct gerbiphore { /* definition of "gerbiphore" structure*/ int dir; /* Direction: 0 means unspecified. */ int count; /* Number of Gerbils in tube */ } A, B, ...; /* one gerbiphore for each tube */ int Fwd=1, Bkwd=2; /* Direction codes for tube travel */ /* genter(g, dir) called with gerbiphore pointer g and direction dir whenever a gerbil wants to enter the tube attached to g in direction dir */ genter(struct gerbiphore *g, int dir) { loop: wait(mutex); if (g->dir == 0) g->dir = dir; /* If g->dir unassigned, grab it! */ if (g->dir == dir) { g->count = 1 + g->count; /* One more gerbil in tube. */ *********; /* MISSING LINE! */ return; } signal(mutex); goto loop; } /* gleave(g, dir) is called whenever a gerbil leaves the tube attached to gerbiphore g in direction dir. */ gleave(struct gerbiphore *g, int dir) { wait(mutex); g->count = g->count - 1; if (g->count == 0) g->dir = 0; signal(mutex); }Unfortunately a blotch of red wine obscures one line of Nickles's code. The team of stain analysts hired to decode the blotch eventually respond with a sizable bill and the report that "it appears to be Ch. Petrus, 1981". Again, your services are needed. What belongs in place of ********* at the line commented "MISSING LINE"?
int Tubes[100]; /* max of 100 tubes */ WTube_handler() { int TubeNumber = User.R0; /* which tube to write */ int Datum = User.R1; /* the data to write */ if (Tubes[TubeNumber] != 0) { /* wait until Tube is empty */ User.XP = User.XP - 4; return; } else { Tubes[TubeNumber] = Datum; /* tube empty, fill it up! */ } } RTube_handler() { int TubeNumber = User.R0; /* which tube to read */ if (Tubes[TubeNumber] == 0) { /* wait until there's data */ User.XP = User.XP - 4; return; } else { User.R1 = Tubes[TubeNumber]; /* read the datum */ Tubes[TubeNumber] = 0; /* mark the tube as empty */ } }The handlers run as part of the Unicks kernel and will not be interrupted, i.e., handling of interrupts is postponed until the current process returns to user mode. Note that the initial values in the Tubes array are zero, and keep in mind that only nonzero data is to be written to (and read from) each tube.
int TubeNumber = 37; /* tube to be used for mutual exclusion */ WTube(TubeNumber,1); /* one-time-only initialization */ while () { /* loop with critical section */ /* LOCK ACCESS */ <critical section> /* UNLOCK ACCESS */ }where the regions marked LOCK ACCESS and UNLOCK ACCESS use the tube TubeNumber to ensure exclusive access to the code marked <critical section>. These two regions may contain the forms datum=RTube(TubeNumber) and Wtube(TubeNumber,datum) as a C interface to the tube SVCs. Fill in the LOCK and UNLOCK code above.