\documentclass[twoside]{article}
\usepackage{graphics}
\usepackage{fancyheadings}

\newcommand{\coursenumber}{131}
\newcommand{\coursetitle}{Principles of Programming Languages}

\topmargin  18pt        % 27pt
\headheight 12pt        % 12pt
\headsep    35pt        % 45pt
\textheight 8.0in
\textwidth  6.2in

\oddsidemargin   22pt      % Left margin on odd-numbered pages.
\evensidemargin  22pt      % Left margin on even-numbered pages.
\marginparwidth  72pt       % Width of marginal notes.
\marginparsep    11pt      % Horizontal space between outer margin and 
                           % marginal note

\pagestyle{fancy}
\lhead{CSCI \coursenumber}
\chead{}
\rhead{\semester}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\setlength{\headrulewidth}{0pt}
\setlength{\footrulewidth}{0pt}

\newcommand{\semester}[0]{
     \ifnum\month>7{Fall}\fi
     \ifnum\month<8{Spring}\fi\  \number\year
}

\newcommand{\points}[1]{(#1 points)}
\newcommand{\phead}[2]{\points {#1} \textbf{#2}}

\def\rightarrowfill{\mathsurround=0pt  \mathord- \mkern-6mu
  \cleaders\hbox{$\mkern-2mu \mathord- \mkern-2mu$}\hfill
  \mkern-6mu \mathord-\!\!\!\!\longrightarrow}
\newcommand{\step}[1]{~~\stackrel{\texttt{\scriptsize #1}}{\rightarrowfill}~~}


\begin{document}

\begin{center}
    \Large Homework 11\\ \vspace{1 ex} Due Tuesday, 12/6/2011
\end{center}

\vspace{2 ex} 

Please turn in your homework solutions online at  
\texttt{http://www.dci.pomona.edu/tools-bin/cs131upload.php}
by midnight on the due date. 


\vspace{2 ex}


\begin{enumerate}
    
    \item \phead{10}{Atomicity \& Race Conditions}

    The \texttt{DoubleCounter} class defined below has methods
    \texttt{incrementBoth} and \texttt{getDifference}.  Assume that
    \texttt{DoubleCounter} will be used in multi-threaded applications.

    \begin{verbatim}
    class DoubleCounter { 
       protected int x = 0, y = 0; 
       
       public int getDifference() { 
          return x - y; 
       } 

       public void incrementBoth() { 
          x++; 
          y++; 
       } 
    } 
    \end{verbatim}
    There is a potential data race between \texttt{incrementBoth} and
    \texttt{getDifference} if \texttt{getDifference} is called between the
    increment of x and the increment of y.  For the following 
    questions, assume that the ``++'' operators are atomic (in 
    reality they are not) and that each thread calls incrementBoth 
    exactly once.
    
    \begin{enumerate}
        \item What are the possible return values of
        \texttt{getDifference} if there are 2 threads?

        \item What are the possible return values of
        \texttt{getDifference} if there are n threads?

        \item Data races can be prevented by inserting synchronization
        primitives.  One option is to declare

        \begin{verbatim}
        public synchronized int getDifference() {...} 
        public void incrementBoth() {...} 
        \end{verbatim}
        This will prevent two threads from executing method \texttt{getDifference}
        at the same time.  Is this enough to ensure that \texttt{getDifference}
        always returns 0?  Explain briefly.
     
        \item Is the following declaration 
        \begin{verbatim}
        public int getDifference() {...} 
        public synchronized int incrementBoth() {...} 
        \end{verbatim}
        sufficient to ensure that \texttt{getDifference} always returns 0?  Explain
        briefly.

        \item What are the possible values of \texttt{getDifference} if
        the following declarations are used?
        \begin{verbatim}
        public synchronized int getDifference() {...} 
        public synchronized int incrementBoth() {...} 
        \end{verbatim} 

    \end{enumerate}
    
    \item \phead{10}{Concurrent Access to Objects}
    
    Please do problem 14.6 from Mitchell, page 471.    
    
    \item \phead{10}{Java synchronized objects}

    Please do problem 14.7, parts a,b,and c from Mitchell, page 472. 

    \item \phead{20}{Using Bounded Buffer}
   
    The Haskell function, \texttt{primesto n}, given below, can be used to
    calculate the list of all primes less than or equal to n by using
    a variant of the classic "Sieve of Eratosthenes".
    
    \begin{verbatim}
{- Sieve of Eratosthenes: Remove all multiples of first element from list,
   then repeat sieving with the tail of the list.  If start with list [2..n]
   then will find all primes from 2 up to and including n. -}
sieve :: (Integral a) => [a] -> [a]
sieve [] = []
sieve (fst:rest) = let
        nurest = filter (\n -> (n `mod` fst) /= 0) rest
     in
        fst:(sieve nurest)

-- return list of primes from 2 to n
primesto :: (Integral t) => t -> [t] 
primesto n = sieve [2..n];

    \end{verbatim}

    Notice that each time through the sieve we first filter all of the
    multiples of the first element from the tail of the list, and then
    perform the sieve on the reduced tail.  In an eager language, one
    must wait until the entire tail has been filtered before you can
    start the sieve on the resulting list.  In Haskell, it will 
    perform the calculation on demand and only calculate as much as 
    is needed.  For example if we displayed only the first element of 
    the result of primesto 100, then only that element would be 
    calculated.  If we have spare processors, one could use
    parallelism to have one process start sieving the result before
    the entire tail had been completely filtered by the original
    process.

    Here is a good way to think of this concurrent algorithm that will
    use the Java \texttt{BoundedBuffer} class defined in the previous
    problem.  The main program should begin by creating a
    \texttt{BoundedBuffer} object (say with 5 slots) and then should
    successively insert the numbers from 2 to n (for some fixed n)
    into the \texttt{BoundedBuffer} using the \texttt{put} method,
    and finally put in -1 to signal that it is the last element.
    After the creation of the \texttt{BoundedBuffer} object, but
    before starting to put the numbers into the
    \texttt{BoundedBuffer}, the program should create a \texttt{Sieve}
    object (using the \texttt{Sieve} class described below) and pass
    it the \texttt{BoundedBuffer} object (as a parameter to
    \texttt{Sieve}'s constructor).  The \texttt{Sieve} object should
    then begin running in a separate thread while the main program
    inserts the numbers in the buffer.

    After the \texttt{Sieve} object has been constructed and the
    \texttt{BoundedBuffer} object stored in an instance variable,
    \texttt{in}, its \texttt{run} method should get the first item
    from \texttt{in} using the \texttt{get} method.  If that number
    is negative then the \texttt{run} method should terminate.
    Otherwise it should print out the number (System.out.println is
    fine) and then create a new \texttt{BoundedBuffer} object,
    \texttt{out}.  A new Sieve should be created with
    \texttt{BoundedBuffer} \texttt{out} and started running in a new
    thread.  Meanwhile the current Sieve object should start filtering
    the elements from the \texttt{in} buffer.  That is, the
    \texttt{run} method should successively grab numbers from the
    \texttt{in} buffer, checking to see if each is divisible by the
    first number that was obtained from \texttt{in}.  If a number is
    divisible, then it is discarded, otherwise it is put on buffer
    \texttt{out}.  This reading and filtering continues until a
    negative number is read.  When the negative number is read then it
    is put into the \texttt{out} buffer and then the \texttt{run}
    method terminates.
    
    If all of this works successfully then the program will eventually have 
    created a total of p + 1 objects of class \texttt{Sieve} (all running 
    in separate threads), where p is the number of primes between 2 and n.  
    The instances of \texttt{Sieve} will be working in a pipeline, using 
    the buffers to pass numbers from one \texttt{Sieve} object to the next.

    Please write this program in Java using the \texttt{BoundedBuffer}
    class from the previous problem.  Each of the buffers used should
    be able to hold at most 5 items.
    
    \item \phead{15}{Sieve with Actors}
    
    Rewrite the Sieve of Eratosthenes program from above in Scala
    using Actors (and no \texttt{BoundedBuffer}).  In the Java 
    program you wrote, you created a new Thread for every prime 
    number you discovered.  This time, you will create a new 
    \texttt{Sieve} actor for each prime \texttt{Int}.
    
    \textbf{Hints}: Your \texttt{Sieve} actor should keep track of the prime it
    was created with, and it should have a slot that can hold another
    ``follower'' \texttt{Sieve} actor that will handle the next prime
    found.  (The mailbox of this other Actor will play the role of the
    \texttt{BoundedBuffer} from the previous problem in that it will
    hold the numbers being passed along from one actor to the next.)
    Each \texttt{Sieve} actor should be able to handle messages of the form
    \texttt{Number(n)} and \texttt{Stop}.
    
    The operation of each \texttt{Sieve} actor, once started, is
    similar to the previous problem.  If it receives a message of the
    form \texttt{Number(n)} then it checks if it is divisible by its
    prime.  If so, it is discarded.  If not, then if the follower
    Actor has not yet been created, create it with the number.  If
    not, then send the number to the follower \texttt{Sieve} actor.
    When the Stop \texttt{message} is sent, pass it on to the follower
    (if any), and exit.
    
    This program works best with a \texttt{receive} and a
    \texttt{while} loop (like in the Auction example) rather than
    \texttt{react} and \texttt{loop} (as in the \texttt{PingPong} and
    \texttt{BoundedBuffer} actor examples from class).
    
    Your program should print (in order) all of the primes less than 
    100.  You can print each prime as it is discovered (e.g., when 
    you create the corresponding \texttt{Sieve} actor), but it would 
    be even better to return a list of all of the primes, and then 
    print those out.  To do this, you can send the message Stop 
    synchronously with ``!?'' and get back the list of all primes.  
    The ``!?'' operator returns an object of type \texttt{Any} 
    (equivalent to Java's \texttt{Object}), so you'll have to use 
    \texttt{match} to decode it as a list of \texttt{Int}.
    
\end{enumerate}

\end{document}