CPS 110 Midterm Postmortem, Spring 2001 Problem 1: Operators Are Standing By. This problem from the Spring 2001 midterm is similar to the classical "sleeping barber" problem, also known locally as "sleeping professor". This variant has multiple professors or barbers. To solve a problem like this, just write procedures that do the basic synchronization. Don't worry about the outer loop for the operators/professors. I made the mistake of leaving a couple of problem set solutions out there that try to represent the outer loop for the threads. I paid for this: people gave me all kinds of crazy loops that tried to incorporate the whole program for customers and advocates, rather than the basic logic. In grading, I tried to ignore this superfluous code. In this case, the customer() calls a procedure to get an advocate, waking one up if necessary, and waiting if none are available. The advocate() calls a similar procedure to wait for a customer, waking one up if necessary, and waiting if none are available. Since the code is symmetric we can just consider one side, although all the exam answers should and did give me both sides. The basic approach with mx/cv (part A) in broad strokes is going to look something like a basic ping-pong: customer/advocate() { mx.acquire(); peer.signal(); peer.wait(); mx.release(); } Note that we will have a deadlock if the talk() is in here somewhere while the mutex is held. This is because the customer and advocate both need to talk to each other, but they can't hold the mutex at the same time. At best, this approach would kill all parallelism by allowing only one customer/advocate pair to talk at a time. In grading, I tended to just focus on the basic logic, so if you made this deadlock mistake you lost a couple of points at most, and nothing if everything else was OK. There are a couple of other things to note here. First, the customers have to wait for the advocates and vice versa, so we probably want two different condition variables. As always, we can do it one cv using broadcast and looping-before-leaping, but two is cleaner and more elegant. So, for example, the customer might look something like this: customer() { mx.acquire(); advocate.signal(); customer.wait(); mx.release(); } The second thing to note is that it won't work right if they both wait every time like this. This is because whoever gets there last will succeed in waking up a peer, but will then go to sleep, having missed its earlier signal. So we're going to need some logic with some counts. But first a digression to discuss the semaphore solution (part B). The tentative solution above is similar to the basic semaphore solution, which works just fine. For example, the customer: customer() { customer.V(); /* produce a customer */ advocate.P(); /* consume an advocate */ } This works because the semaphore remembers each V() until it is consumed by a P(), so it doesn't matter who gets there first. This is an example of a problem that is handled more elegantly with semaphores. Note, however, that you must initialize both semaphores to zero, since an arriving customer or advocate will take care of incrementing its semaphore. Also, at least one of the Vs must come first, or else all threads will deadlock on the Ps. If you did a whole-program solution, there are acceptable variants that initialize the counts to something other than zero and change the order. For example, it is OK to set the advocate semaphore to the number of advocates, and then postpone the advocate.V until the advocate is done talking. This is less elegant, but it should receive full credit. Some of the offered solutions using semaphores added additional counts without the benefit of a lock, or used a lock which protected the counts at the price of a deadlock because some thread blocks while holding the lock. Since these are fundamental errors stemming from lack of practice with semaphores, these answers were generally worth less than half credit, and sometimes as little as 5 points out of 25. Getting back to the mx/cv solution, we decided that the basic approach could look something like this for each side: customer() { mx.acquire(); if (advocate is waiting) advocate.signal(); else customer.wait(); mx.release(); } The trick is to know if an advocate is waiting. We can use a count of available advocates. Note that the advocate must also know if a customer is waiting, so we need two counts. They must be counts rather than booleans, since multiple advocates and customers may arrive in any order. These are the same counts that are elegantly encapsulated in the semaphore solution. Many people mess up the counts when working this problem under pressure. There are a couple of gotchas. For example, one common attempt is: customer() { mx.acquire(); if (advocates > 0) advocate.signal(); else { customers++; customer.wait(); customers--; } mx.release(); } The problem with this approach is that many customers may pass through before a signalled advocate gets a chance to run, leaving them to think that they have rights to the same advocate. A similar problem can afflict the advocates on the other side. One solution is to have each side consume the count for its peer when it "reserves" that peer with a signal, just as the semaphore solution does implicitly. customer() { mx.acquire(); if (advocates > 0) { advocate.signal(); advocate--; } else { customers++; customer.wait(); } mx.release(); } This is a full-credit solution, but it has one minor weakness in that it assumes that each signal wakes up exactly one waiter. Not every thread implementation guarantees this, as discussed on the problem set. I much prefer the more robust and elegant "loop before you leap" alternative: customer() { mx.acquire(); customers++; advocate.signal(); while (advocates == 0) customer.wait(); advocates--; mx.release(); } Note that it doesn't matter if you do the signal() before or after waiting, since you are holding the mutex and you should not wait if there is a peer available. There is another elegant solution using sequencers/eventcounts, like the "espresso franchise" example on the problem set, but there are several ways to screw that one up too. I also got some contorted solutions using queues and such. I tended to examine these only enough to find something obvious to knock off some points, then gave the benefit of the doubt for the rest of the answer. Here's a summary of how I graded the mx/cv solutions out of 25 points. First, I scan the code looking for correct locking. If there is more than one mutex or if any count is examined or manipulated outside of the mutex, the answer is worth 5-12 points at most. Next I check to be sure that there are two condition variables and that there is a signal (or broadcast) and a wait on each side, naming the correct condition variable. Absent this, the answer is worth 15-19 points at most. Next, I look to be sure that there are two counts, rather than a single count or booleans. Absent this, the answer is worth 20 points at most. Finally, I look to see if the counts are handled correctly. Errors with the counts lose 3-5 points. Various other logic errors cost 1-5 points, including: a broadcast without a corresponding loop-before-leap while loop on the other side, extra synchronization, general goofiness, and talk() with the mutex held. Problem 2: Sellshort This problem was intended to be immediately recognizable to the initiated as a reader/writer lock with writer priority. Most students did recognize it, but there were many incomplete and contorted solutions. Again, many students did not write enter*() and exit*() routines as requested but instead wrote complete loops for customers and employees. Surprisingly few students recognized the need for separate enter() and exit() routines for customers (writers) and employees (readers), and instead encoded all the logic into a single pair of routines with extra if statements. All of this made grading quite difficult and time-consuming for Justin, who graded this problem. He was perhaps more generous with partial credit than I would have been. The solution is similar to those given in Birrell and in class, although you must block readers if a writer is waiting. The extra twist of turning off the lights if you are the last one to leave is trivial. Problem 3: Got Milk This is a direct bounded producer/consumer problem similar to BoundedBuffer in Lab 3. It is easier than BoundedBuffer because there are no ordering requirements for multiple producers and consumers. Thus this version can be solved with a single mutex and condition variable (though it is more obviously correct with two condition variables), or with four lines using dual full/empty semaphores in a cross-wise "peer.V; me.P" configuration, as in problem 1(b). Again, many students tried to write loops for the students rather than simple produce/consume procedures. Many of the solutions tried to handle an argument for produce() representing how many bottles of milk to place in the refrigerator, rather than recognizing that produce() could be called in a loop once for each bottle. These factors led to overly complex and inelegant solutions that complicated grading and did not win any extra points. I graded these solutions by scanning for correct locking (a single mutex encapsulating all logic), looking for a signal() and a wait() on both the produce and consume sides, then checking for proper logic surrounding the signal and wait, typically using a single counter for how many bottles of milk are in the refrigerator, with looping before leaping. For example: produce() { mx.acquire(); while (milk == CAPACITY) spacecv.wait(); milk++; milkcv.signal(); mx.release(); } The consume side is similar: consume() { mx.acquire(); while (milk == 0) milkcv.wait(); milk--; spacecv.signal(); mx.release(); } Problem 4: Mode, space, and context This problem was worth 12 points for parts a-c and 14 points for part d. (a) Read text and initialized data and constants from the executable program file. Zero-fill everything else. (b) Set the PC to the user virtual address of the program's first instruction, as given in the header for the executable file. Set the SP to the base of the user stack for the main thread, as determined by the kernel's policies for laying out address spaces. (c) Trap, fault, interrupt. Give examples of each. The PC is saved and set to the kernel event handler (installed at boot time). The SP is set to the base of the process kernel stack for a trap or fault, and to the top of the interrupt stack for an interrupt. Typically the interrupt stack is global to the kernel. The kernel can return to the faulted context using a special instruction, restoring the PC and SP. It may advance the PC where it is saved in memory before returning, if necessary (e.g., for a system call). (d) Return from trap, fault, or interrupt. Note that a context switch in kernel mode could cause the kernel to return back to user space in a different process. Such a switch could be involuntary (on a timer interrupt) or voluntary (process blocked in a trap or fault). A trap or fault may cause a process to exit, also forcing a context switch and a return back to user space in a different process. An exec trap could create a new process and yield or block to context switch to it, returning back to user space in the context of the child.