% -*- Mode: Tex -*-

\def\AnswerSheet{1}

\input 6001mac.tex

\begin{document}

\psetheader{Spring Semester, 1999}{Recitation -- Wednesday, April 7}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\Large\bf 1. Concurrency}

Give all possible values of x that can result from executing the
following:

\beginlisp
(define x 10)
(parallel-execute (lambda () ($\overbrace{\rm{}set!}^C$ x (* $\overbrace{\rm{}x}^A$ $\overbrace{\rm{}x}^B$)))
                  (lambda () ($\underbrace{\rm{}set!}_G$ x (* $\underbrace{\rm{}x}_D$ $\underbrace{\rm{}x}_E$ $\underbrace{\rm{}x}_F$))))
\null
; Possible Values: \ANSWER{$10^2, 10^3, 10^4, 10^5, 10^6$}
\endlisp

Which of these possibilities remain if we instead use serialized procedures:

\beginlisp
(define x 10)
(define s (make-serializer))
(parallel-execute (s (lambda () ($\overbrace{\rm{}set!}^C$ x (* $\overbrace{\rm{}x}^A$ $\overbrace{\rm{}x}^B$)))
                  (s (lambda () ($\underbrace{\rm{}set!}_G$ x (* $\underbrace{\rm{}x}_D$ $\underbrace{\rm{}x}_E$ $\underbrace{\rm{}x}_F$))))
\null 
; Possible Values: \ANSWER{$10^6$}
\endlisp

\vskip 0.1in
{\Large\bf 2. More Concurrency: Bank Accounts}

In class yesterday, we saw how we can use serializers to make account
balances more safe for deposits and withdrawals.  Consider the
following procedure for making an account.  We can define the
procedure {\tt get-balance} and a simple {\tt deposit} procedure.

\begin{tabular}{p{3.5in}p{2.5in}}
\beginlisp
(define (make-account balance)
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((serializer (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'deposit) deposit)
            ((eq? m 'balance) balance)
            ((eq? m 'serializer) serializer)))
    dispatch))
\endlisp
&
\beginlisp
(define (get-balance acct)
  (acct 'balance))
\null
(define (deposit acct amount)
  (let ((d (acct 'deposit)))
    (d amount)))
\null
(set a (make-account 100))
\endlisp
\end{tabular}

\vspace{0.05in}

Notice that this {\tt deposit} procedure is not safe because we do not
use the serializer.  For example, \\ {\tt (parallel-execute (lambda ()
(deposit a 20)) (lambda () (deposit a 30)))} \\ could fail.  How can
we redefine the deposit procedure to make it safe if multiple deposits
happen concurrently?

\beginlisp
(define (deposit acct amount)
\ANSWER{
  (let ((s (acct 'serializer))
        (d (acct 'deposit)))
    ((s d) amount))
})
\endlisp

\vspace{0.05in}

Do we need to redefine {\tt get-balance} in the same way?  Why or why
not? \\ 
\RA \ANSWER{No, because balance is always a reasonable value.}

\newpage
{\Large\bf 3. Exchanging Accounts}

Now, consider the process of exchanging the amount of money in two
accounts.  For example,

\beginlisp
(define a (make-account 100))
(define b (make-account 50))
(exchange a b)
(get-balance a)  ==>  50
(get-balance b)  ==> 100
\endlisp

Below is an {\tt exchange} procedure that does not serialize.  Using
{\tt exchange}, we can now write a serialized exchange that applies
the serializers from both accounts before making the exchange:

\begin{tabular}{p{3in}p{3in}}
\beginlisp
(define (exchange a1 a2)
  (let ((diff (- (a1 'balance)
                       (a2 'balance))))
    ((a1 'deposit) (- diff))
    ((a2 'deposit) diff)))
\endlisp
&
\beginlisp
(define (serialized-exchange a1 a2)
  (let ((s1 (a1 'serializer))
        (s2 (a2 'serializer)))
\ANSWER{
    ((s1 (s2 exchange)) a1 a2)
}  ))
\endlisp
\end{tabular}

Does this fix everything?  Not quite. This could make things worse!
Now we have the concept of {\bf deadlock}.  One way of fixing deadlock
is to give each serializer a unique id and insist every process
acquire serializers in order of the unique ids.

Imagine that we've changed make-serializer so that it makes a
serializer with a unique id, as show below, left.  How could we change
serialized-exchange to prevent deadlock?

\begin{tabular}{p{3in}p{3in}}
\beginlisp
(define s (make-serializer))
(define t (make-serializer))
(s proc) ==>  <serialized proc>
(s 'id)  ==>  1
(t 'id)  ==>  2
\endlisp
&
\beginlisp
(define (serialized-exchange a1 a2)
  (let ((s1 (a1 'serializer))
        (s2 (a2 'serializer)))
\ANSWER{
    ((if (< (s1 'id) (s2 'id))
         (s1 (s2 exchange))
         (s2 (s1 exchange)))
      a1 a2)
} ))
\endlisp
\end{tabular}

\vspace{-0.1in}
{\Large\bf 4. Unique Ids}

Let's try to add unique ids to our serializers.  First, let's write a
function called {\tt tag-proc} that takes a procedure and returns a
procedure that is tagged with a {\bf unique} id.  See the examples on
the right.

\begin{tabular}{p{3.5in}p{2.5in}}
\beginlisp
(define tag-proc
\ANSWER{
  (let ((count 0))
    (lambda (f)
       (set! count (+ count 1))
       (let ((id count))
         (lambda (x)
           (if (eq? x 'id)
               id
               (f x))))))
})
\endlisp
&
\beginlisp
(define f (tag-proc sqrt))
(define g (tag-proc sqrt))
(define h (tag-proc cube))
(f 'id) \RA 1    (unique id is 1)
(g 'id) \RA 2    (unique id is 2)
(h 'id) \RA 3    (unique id is 3)
(f 25)  \RA 5
(g 81)  \RA 9
(h 3)   \RA 27
\endlisp
\end{tabular}

\vspace{0.05in}

How can we change our {\tt make-serializer} procedure so that each
serializer that is generated has a unique id?   (Where do we put the
call to {\tt tag-proc}?)

\beginlisp
(define (make-serializer)
\null
  (let ((mutex (make-mutex)))
\ANSWER{
    (tag-proc 
}
     (lambda (p)    
       (define (serialized-p . args) 
        ...
       )
\null
       serialized-p))))
\endlisp

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{document}
