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
Give all possible values of x that can result from executing the following:
(define x 10)
(parallel-execute (lambda () (
x (* 
)))
(lambda () (
x (* 
))))
; Possible Values: HiddenAnswer 
EndOfAnswer
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: HiddenAnswer 
EndOfAnswer
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) HiddenAnswer (let ((s (acct 'serializer)) (d (acct 'deposit))) ((s d) amount)) EndOfAnswer)
Do we need to redefine get-balance in the same way? Why or why
not?
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?
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))) HiddenAnswer (tag-proc EndOfAnswer (lambda (p) (define (serialized-p . args) ... )
serialized-p))))