Due Date: April 29, 1999
These can be answered in a sentence or two, and are intended to reinforce
- (3 points) What is a race condition? (Tanenbaum, problem 2.5)
- (4 points) What are the Bernstein conditions?
- (4 points) What conditions must a solution to the critical section
- (4 points) Suppose someone devised a new synchronization primitive
she claimed were as powerful as semaphores. How would she prove this claim?
These questions require some thought and longer answers than the short-answer
questions. They are intended to have you use the concepts discussed in class,
to be sure you understand them and can work with them.
- (15 points) A binary semaphore is most commonly defined as a
semaphore whose integer value can range only between 0 and 1. (This is
slightly different than Tanenbaum's definition on p. 68, but is more common.)
Implement counting semaphores using binary semaphores. (variation of Tanenbaum,
- (20 points) Instead of test-and-set, some computers provide an atomic
instruction that sets the new value to 1 greater than its old value, as shown
function testandinc(var lock: integer): integer;
testandinc := lock;
lock := lock + 1;
end (* testandinc *)
Show how to use this instruction to implement locks. (Hint: you must
be wary of integer overflow.)
- (25 points) On page 77 of the text, Tanenbaum claims that the program
in Fig. 2-18 solves the Dining Philosophers' problem. Either prove or disprove
this claim. If the claim is false, fix the program (that is, implement a
solution to the dining philosophers' problem using semaphores).
- (25 points) Synchronization within monitors uses condition variables
and two special operations, wait and signal. A more general form
of synchronization would be to have a single primitive, waituntil, that
had an arbitrary Boolean predicate as parameter. Thus, one could say, for
waituntil x < 0 or y + z < n
The signal primitive would be no longer needed. This looks
more general than that of Hoare or Brinch Hansen, but is not used.
- Show that waituntil is as general as Hoare's scheme (that is, any
monitor using Hoare's wait and signal primitives can be written
using it.) Is it in fact more general? Justify.
- Why is this form not used in practise? (Hint: think about the
implementation.) (Tanenbaum, problem 2.13)
- (5 points) When a message is sent to a sleeping process in MINIX, the
procedure ready is called to put that process in the proper scheduling queue.
This procedure starts out by disabling interrupts. Explain. (Tanenbaum,
- (5 points) The MINIX procedure mini_rec contains a loop. Explain
what it is for. (Tanenbaum, problem 2.31)
- (5 points) Can the precedence graph below be implemented using
parbegin and parend?
Send email to
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562
Page last modified on 4/16/99