from rafael@comp.nus.edu.sg  Sat Feb  3 12:46:51 2001
Return-Path: <rafael@comp.nus.edu.sg>
Received: from localhost (rafael@localhost)
	by sunA.comp.nus.edu.sg (8.8.5/8.8.5) with ESMTP id MAA22171;
	Sat, 3 Feb 2001 12:46:51 +0800 (GMT-8)
Date: Sat, 3 Feb 2001 12:46:51 +0800 (GMT-8)
From: Rafael Ramirez <rafael@comp.nus.edu.sg>
To: Colin Tan Keng Yan <ctank@comp.nus.edu.sg>
cc: Wu Hui <wuh@comp.nus.edu.sg>, Rafael Ramirez <rafael@comp.nus.edu.sg>
Subject: Sketched Tut 3 answers
Message-ID: <Pine.GSO.4.21.0102031236380.20856-100000@sunA.comp.nus.edu.sg>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Status: ORr

1. See text book.

2. (a) For instance, in the $wait$ operation, if the testing of the
value of the semaphore $s$
and the statement $s:=s-1$ are not executed atomicly, then mutual
exclusion can be violated:
suppose $s=1$ initially and two processes $P1$ and $P2$ execute $wait(s)$
before entering their
critical sections then both could check the value of $s$, both will get
the answer $s=1$ and then
they will both decrement $s$ and enter their critical sections.
                                                                
(b) Busy waiting is not desirable because it may waste cpu time. It can be
avoided by for instance
a blocked-queue semaphore in which suspended processes are kept on a FIFO
queue.

3. The role of lines 2, 4, 5 and 7 is to guarantee mutual exclusion when
accessing the buffer.

4. Semaphore wait: test the value $s$ of the semaphore to decide whether
or n
ot the calling
process suspends, decrements the value of $s$, it is part of the process
code.

Monitor x.wait: no value associated with this operation, suspends the
calling pr
ocess regardless
of any value, it is part of the monitor code.

Semaphore signal: increments the value of $s$, it is part of the process
code.

Monitor x.signal: no value associated with this operation, resumes
execution of
a suspended
process on condition variable x (if any), if no such suspended process the
opera
tion has no effect,
it is part of the monitor code. 

5.

type prod_cons = monitor
   var b : array[0..N-1] of integer;
   var in, out, count : integer;
   var not_full, not_empty : condition;

procedure entry append(I);
begin
   if count=N then begin not_full.wait; end;
   b[in] := I;
   in:=(in+1) mod N;
   count:=count+1;
   not_empty.signal;
end

procedure entry take(I);
begin
   if count=0 then begin not_empty.wait; end;
   I:=b[out];
   out:=(out+1) mod N;
   count:=count-1;
   not_full.signal;
end
         
begin
   in, out, count := 0;
end;