% -*- Mode: Tex -*-

%\input /home/welg/6001mac.tex
%\input /homes/welg/6001/6001mac.tex
%\input /zu/scheme/6001ARCHIVE/fall89/6001mac.tex
\input 6001mac.tex

\def\fbox#1{%
  \vtop{\vbox{\hrule%
              \hbox{\vrule\kern3pt%
                    \vtop{\vbox{\kern3pt#1}\kern3pt}%
                    \kern3pt\vrule}}%
        \hrule}}

\def\emptybox#1#2{\fbox{\vbox to #2{\hbox to #1 {\null}}}}

\def\pscenter#1{\hbox to\hsize{\hss\psadobenomag{#1}\hss}}

\setlength{\textheight}{9.2in}

\begin{document}

\psetheader{Spring Semester, 1998}{Recitation -- Friday, April 3}

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

{\Large\bf 1. Student Presentation}

Now that we are using the environment model, it is a little easier to
understand what define does. But define and set! both seem to change
the environment. Explain to the class, using examples, the difference
between what define and set! do.

\vskip .1in

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

{\Large\bf 2. 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: $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: $10^6$
\endlisp

\vskip 0.2in
{\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.

\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))
\null
(set a (make-account 100))
\endlisp

We can now define the procedure {\tt get-balance} as follows:

\beginlisp
(define (get-balance acct)
  (acct 'balance))
\endlisp

\newpage
We can also define a simple {\tt deposit} procedure as follows:

\beginlisp
(define (deposit acct amount)
  (let ((d (acct 'deposit)))
    (d amount)))
\endlisp

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)
  (let ((s (acct 'serializer))
        (d (acct 'deposit)))
    ((s d) amount)))
\endlisp

Hmmm.  Do we need to redefine {\tt get-balance} in the same way?  Why or why
not?

\vskip 0.1in
{\Large\bf 3. Swapping Accounts}

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

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

Let's write the {\tt swap} procedure below, making sure that it
serializes all deposits.

\beginlisp
(define (swap acct1 acct2)
  (let ((s-1 (acct1 'serializer))
        (s-2 (acct2 'serializer))
        (d-1 (acct1 'deposit))
        (d-2 (acct2 'deposit))
        (diff (- (acct1 'balance) (acct2 'balance))))
    ((s-1 d-1) (- diff))
    ((s-2 d-2) diff)))
\endlisp

Is this sufficient?  Will this work in all cases?  What could happen
when \\ {\tt (parallel-execute (lambda () (swap a b)) (lambda () (swap
b a)))} \\ is executed?  

How can we fix this?  Write the new swap below:

\beginlisp
(define (swap acct1 acct2)
  (let ((s-1 (acct1 'serializer))
        (s-2 (acct2 'serializer))
        (d-1 (acct1 'deposit))
        (d-2 (acct2 'deposit))
        (diff (- (acct1 'balance) (acct2 'balance))))
    ((s-1 (s-2 
           (lambda ()
             (d-1 (- diff))
             (d-2 diff)))))))
\endlisp

\vskip 0.06in

Does this fix everything?  Not quite. This could make things worse!
Now we have the concept of {\bf deadlock}.  Deadlock can occur when
two processes are competing for resources.  How can we fix this?  For
more details, see section 3.4.2 in the text.

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

\end{document}
