MASSACHVSETTS INSTITVTE OF TECHNOLOGY
Department of Electrical Engineering and Computer Science
6.001---Structure and Interpretation of Computer Programs
Spring Semester, 1999

Recitation -- Wednesday, April 7

1. Concurrency

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

 
(define x 10)
(parallel-execute (lambda () ( x (*  )))
                  (lambda () ( x (*   ))))

; Possible Values: 

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

 
(define x 10)
(define s (make-serializer))
(parallel-execute (s (lambda () ( x (*  )))
                  (s (lambda () ( x (*   ))))

; Possible Values: 

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 get-balance and a simple deposit procedure.

Notice that this deposit procedure is not safe because we do not use the serializer. For example,
(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?

 
(define (deposit acct amount)
)

Do we need to redefine get-balance in the same way? Why or why not?

3. Exchanging Accounts

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

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

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

Does this fix everything? Not quite. This could make things worse! Now we have the concept of 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?

4. Unique Ids

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

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

 
(define (make-serializer)

  (let ((mutex (make-mutex)))

     (lambda (p)    
       (define (serialized-p . args) 
        ...
       )

       serialized-p))))

• About this document ...