\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{10}

% title command
\newcommand{\mytitle}[1]{\begin{center} {\Large Computation Structures -- 
6.004 Problem Set \psnum \\ Juliet Bourne -- #1} \\ \vspace{-.1in} 
\rule{6in}{.5mm} \end{center}}
% problem command
\newcommand{\prob}[1]{\vspace{.15in}\noindent{\fbox{\large\bf Problem #1}}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}
% newpage setup command 
\newcommand{\mynewpage}{\newpage\noindent
\begin{center}
{\Large 6.004 Problem Set \psnum -- Juliet Bourne -- {\bf Page \thepg}}
\rule{6in}{.5mm}
\end{center}
\addtocounter{pg}{1}}
% see-page command
\newcommand{\seepage}{\noindent See page \rule{.2in}{.1mm} for the
computer output.}

\begin{document}

\mytitle{12/5/90}

\prob{1: {\em Operating System Services}}

\subprob{A} Antarctica.

\subprob{B} 

\begin{verbatim}
TypeSt(p)
 struct MState *p;
 { int num, addr;
   char *st;

   addr = POPPS4(p);
   num = FetchByte(addr);
   st = addr + 1;
   for (i = 0; i <= num; i++)
     TTYWrite(ProcList[CurProc].TTYNumber, st[i]);
}
\end{verbatim}

\subprob{C}

\begin{verbatim}
TypeSt(p)
 struct MState *p;
 { int num, addr;
   char *st;

   if (TTYWriteOK(ProcList[CurProc].TTYNumber)
     { addr = POPPS4(p);
       num = FetchByte(addr);
       st = addr + 1;
       for (i = 0; i <= num; i++)
         TTYWrite(ProcList[CurProc].TTYNumber, st[i]);
     }
   else
       { p->PC = p->PC -2;
         Scheduler(p);
       }
 }
\end{verbatim}

\prob{2: {\em Sychronized Processes}}

\subprob{A} S3 = 1  S1 = 0  S2 = 0

\subprob{B} S1 = 1  S2 = 0  S3 = 0

\subprob{C} No, because the process which prints the ``I'' won't get a
positive semaphore until the process which prints the ``B'' prints a
``B''.

\mynewpage

\prob{3: {\em Producer-Consumer Process Paradigm}}

\subprob{A} \verb+ Chars = 100  Holes = 0  InPtr = 0  OutPtr = 0+. After
a \verb+read()+ there are 99 \verb+Chars+, 0 \verb+Holes+, \verb+InPtr =
0+, and \verb+OutPtr = 1+.  If the next event is a \verb+write(c)+
instead of \verb+read()+, it will wait until a \verb+read()+ is called
because there are no \verb+Holes+ to write into.

\subprob{B} Consider the scenario, with a 1-character FIFO buffer:

\begin{verbatim}
Chars = 0   Holes = 1
Proc 0 writes 'a'; gets swapped out
Chars = 1   Holes = 0
Proc 1 wants to write 'b'; has to wait; gets swapped out
'a' is read
Chars = 0   Holes = 1
Proc 2 writes 'c'; gets swapped out
Chars = 1   Holes = 0
'c' is read
Chars = 0   Holes = 1
Proc 1 writes 'b'; gets swapped out
Chars = 1   Holes = 0
'b' is read 
Chars = 0   Holes = 1
...
\end{verbatim}

\noindent This behavior happens because of the round robin process
swapping. There is no guarantee that control will be handled back over
to the first process waiting to write once a hole is created.

\subprob{C} Use a semaphore to control who is allowed to write; only one
process can write at a time. The first one to request a write will be
the first to write once the process writing is done.

\begin{verbatim}
semaphore mutex = 1;

write(c)
 char c;
 {           wait(mutex);                /* Need to be owner of mutex */
             wait(Holes);                /* Need a hole */
             buf[InPtr] = c;             /* Insert character */
             InPtr = (InPtr+1) % 100;    /* Circular increment */
             signal(Chars);              /* We've added a char */
             signal(mutex);              /* Give up mutex */
 }
\end{verbatim}

\mynewpage

\noindent Now the scenario is something like this:

\begin{verbatim}
Chars = 0   Holes = 1   mutex = 1
Proc 0 writes 'a'; gets swapped out
Chars = 1   Holes = 0   mutex = 1
Proc 1 wants to write 'b'; has to wait on Holes; gets swapped out
Chars = 1   Holes = 0   mutex = 0
'a' is read
Chars = 0   Holes = 1   mutex = 0
Proc 2 want to write 'c'; has to wait to get mutex; gets swapped out
Proc 0 wants to write 'd'; has to wait to get mutex; gets swapped out
Proc 1 writes 'b'; gets swapped out
Chars = 1   Holes = 0   mutex = 1
'b' is read
Chars = 0   Holes = 0   mutex = 1
...
\end{verbatim}

\prob{4: {\em Implementation of Wait Semaphores}}

\subprob{A} \verb+p->PC = p->PC - 2+ backs up the program counter to
right before the supervisor call. In this way, the supervisor call will
not seem to be executed twice when the call is reexecuted. 

\subprob{B} For a single-processor system, it suffices for
\verb+WaitSVC+ to disable interrupts while in \verb+WaitSVC+. Thus,
\verb+WaitSVC+ must be atomic.

\subprob{C} For a multiprocessor system, a test-and-set instruction is
needed to arbitrate between processors wanting the same resource. Thus,
the instruction which both tests a semaphore and sets it has to be
atomic.

\subprob{D} If the call to \verb+Scheduler+ were replaced with
\verb+goto again+, \verb+WaitSVC+, for which interrupts are disabled,
would loop forever, because \verb+Sem[s]+ would never change.

\subprob{E} Adding a call to \verb+Scheduler+ at the end of
\verb+WaitSVC+ wouldn't change the behavior of it very much. After
decrementing \verb+Sem[s]+, another process would be explicitly
scheduled.

\subprob{F} Putting the semaphore storage into user virtual memory would
be a bad idea since the user would have access to it and it could be
swapped out of the virtual memory. 

\end{document}


