Since the answers below are coded, and everyone codes differently, these are only sample solutions. Any solution that works will get full credit; solutions that don't will get somewhat less credit. All answers are in a C-like pseudocode.
Assume we have 4 semaphores: mutex, have_customers, chair_available, and haircut_finished. We initialize mutex to 1 (unlocked), and the others to 0 (locked). Assume we also have variables num_waiting, initialized to 0, barber_asleep, initialized to false, and chair_occupied, initialized to false. Then:
barber()
while (1)
wait(mutex)
if (!chair_occupied)
if (num_waiting == 0)
// Go to sleep
barber_asleep = true
signal(mutex)
wait(have_customers)
wait(mutex)
barber_asleep = false
else
while(!chair_occupied)
signal(mutex)
wait(mutex)
signal(haircut_finished)
signal(mutex)
customer()
wait(mutex)
if (num_waiting == n)
signal(mutex)
return // .. and go away
if (chair_occupied)
num_waiting++
signal(mutex)
wait(chair_available)
wait(mutex)
num_waiting--
chair_occupied = true
if (barber_asleep)
signal(have_customers)
signal(mutex)
wait(haircut_finished)
wait(mutex)
chair_occupied = false
signal(chair_available)
signal(mutex)
return // ... we're done
Note that all of the variables are "protected" by the mutex semaphore. There might be a shorter solution using a monitor, but this one should work. Note also that unless the chair_available semaphore is implemented as FCFS, customers will not be serviced in the logical order. However, the book made no mention of what order customers should be served in.
Assume we have four semaphores tobacco_paper, tobacco_matches, paper_matches, and cigarette_done, all initialized to 0 (locked). Then:
agent()
while(1)
pick two random items x and y from {tobacco, paper, matches}
signal(x_y)
wait(cigarette_done)
tobacco_process()
while(1)
wait(paper_matches)
signal(cigarette_done)
paper_process() and matches_process are coded similarly by waiting on the appropriate semaphore.
If signal must be the last statement, there is no need for process P to block when it signals Q, since it is already on its way out of the monitor. So we can eliminate all the next_count stuff. P must, however, remember that Q is technically inside the monitor, and preserve the state of mutex appropriately. So, we add a local signalled variable to each procedure, initialized to false, and replace each procedure F with:
wait(mutex);
...
body of F
...
if (!signalled)
signal(mutex);
x.wait becomes:
x_count++; signal(mutex); wait(x_sem); x_count--;
x.signal is:
if (x_count > 0) signalled = true; signal(x_sem);
Note that we do not release mutex when we call signal. This is not wrong. Why? Because we just woke up Q, which should be inside the monitor. Q will release mutex after it exits. If we opened mutex (and of course forced Q to reobtain it), someone else might get it first and change the logical condition we signalled Q for. Note also that this won't work if we can signal multiple conditions. But then the first signal would not be the last statement, violating our condition.
Once a process has obtained the printer, it should keep it (i.e. no preemption). So priority only matters when all printers are in use, and someone is finished. We must be sure to give the free printer to the waiting process with the lowest priority. We could, of course, just use conditional-wait construct. But to see how this would actually be implemented, assume we have the data structure:
typedef struct {
int priority;
condition printer_free;
} Node;
We also have an implementation of a priority queue, namely a queue of the above structure where the dequeue() operation retrieves the element with the smallest (or highest) priority. Then our monitor is:
type printer_allocator = monitor
var the_queue: priority queue
num_free: integer
procedure entry printer_acquire(priority);
if (num_free == 0)
Node newNode = new Node;
newNode.priority = priority;
the_queue.enqueue(newNode);
newNode.printer_free.wait();
... grab a free printer
num_free--;
procedure entry printer_release();
num_free++;
if (the_queue.length() != 0);
Node nextNode = the_queue.dequeue();
signal(nextNode.printer_free);
begin
initialize the_queue;
num_free = 3;
end
OK, from above you know how to implement a conditional-wait construct (using a priority queue with a bunch of semaphores), so we'll use them here. We'll assume for simplicity that no process has an id greater than or equal to n (or we'd just print an error message).
type file = monitor
var space_available: binary condition
total: integer
procedure entry file_open(id)
while (total + id >= n)
space_available.wait(id)
total = total + id;
if (total < n - 1)
space_available.signal();
procedure entry file_close(id)
total = total - id;
space_available.signal();
What happens here? As long as the incoming processes
find adequate space available (i.e. sums less than n),
they will claim that space and open the file. Note
that since we're using a binary condition, we can
signal() at will even if nothing is waiting. If a process
finds inadequate space, it will block. When a process
is done, it wakes up the process with the smallest id
(the most likely to fit in the available space). This
process, upon waking, then signals the next process if space
is still available,
but only after successfully claiming its own space. At some
point (quite possibly with the first process), the space
made available may not be enough for the waking
process, and so a process will be woken up prematurely.
This is what the loop is for; it will immediately block
again.