sicp-ex-3.42



<< Previous exercise (3.41) | Index | Next exercise (3.43) >>


xdavidliu

A possible test for whether the change proposed here is safe:

 ; 
 ; 
 (let ((acc (make-account 100))) 
   (parallel-execute 
     (lambda () ((acc 'withdraw) 10)) 
     (lambda () ((acc 'withdraw) 20))) 
   (acc 'balance)) 

The original version in book *certainly* returns 70 here, since each of the two withdrawals results in a *separately* serialized procedure. The modified version on the other hand has both withdrawals using a *single* serialized procedure.

Without further knowledge of how make-serial and parallel-execute actually work, it's hard to tell whether a serialized function can be interleaved *with itself*. If yes, then for the modified version, there may be a data race and the above block of code can incorrectly return 90 or 80. If not, then the modified version in this exercise works perfectly.

A reasonable thing to say would be that since both arguments to parallel-execute were serialized using the same serializer (since they are actually the same *function*), we should expect them to not interleave with each other, and hence the modification *should* work.

it is a safe change to make, for it will get the same final result as the original version. we should differentiate the code copy, which is the code to be run, to runtime copy, which is the process running to be executed. the original version will execute serializer function each time the account receiving a message, which will generate a *separate runtime copy* as a new sub-process from the *withdraw/deposit code*. While the modified version will generate a *mediate code copy* at the time as the account constructed in the main process, from which it will generate a *separate runtime copy* as a new sub-process each time the account receiving a message.


In a nutshell, IMHO here `withdraw` doesn't change so `(protected withdraw)` also won't change. So safe.

To be more detailed, here `(protected withdraw)` is just one procedure instead of applying one procedure to one variant arg list and then getting the different result at each run possibly.

---

See tejomay's comment for Self-interleaving problem.



meteorgan

  
  
 It's safe to do that change. There is nothing different about concurrency in these two version. The only difference is new one serialize the procedures before call the functions, but the original one do it when call withdraw or deposit.   

The original solution and the one proposed by Ben Bitdiddle are essentially the same.

That is not the only difference. Every call to serializer returns a new function that accesses the same serializer. With Ben Bitdiddle's version, only two serialized functions are created - one for withdraw and deposit. With the original solution, a new serialized function is created on each call to withdraw or deposit. As described by xdavidliu, the original is the safer solution, since it's unclear whether a function would interleave with itself. It's entirely possible, since each function call creates a new process which are treated differently.


I agree with it's safe to change, but I don't think there is no difference. In changed version, all accounts created share a same serialized set, which means only one account could execute withdraw or deposit at a same time. Hence there will be no concurrency between different accounts.

Every time make-account is called make-serializer is called. There will be a unique serializer for every account. I don't agree that "only one account could execute withdraw or deposit at the same time."



See the ``make-serializer` and `make-mutex` implementation given at the end of section 3.4.2:

 ; 
 ; 
 (define (make-serializer) 
   (let ((mutex (make-mutex))) 
     (lambda (p) 
       (define (serialized-p . args) 
         (mutex 'acquire) 
         (let ((val (apply p args))) 
           (mutex 'release) 
           val)) 
       serialized-p))) 
 (define (make-mutex) 
   (let ((cell (list false)))             
     (define (the-mutex m) 
       (cond ((eq? m 'acquire) 
              (if (test-and-set! cell) 
                  (the-mutex 'acquire))) ; retry 
             ((eq? m 'release) (clear! cell)))) 
     the-mutex)) 
 (define (clear! cell) 
   (set-car! cell false)) 
 (define (test-and-set! cell) 
   (if (car cell) 
       true 
       (begin (set-car! cell true) 
              false))) 

Self-interleaving is not an issue here.

`Make-serializer` is a simple wrapper that waits to apply its procedure to the supplied arguments until it gets permission from the `mutex`. Each application of the serialized procedure results in a new `'acquire` call to the mutex.

Self-interleaving is not an issue because the mutex is indifferent to as "where" the `'acquire` request comes from: from its perspective, two competing `withdraw` procedure calls are equivalent to one `withdraw` and one `deposit` call.

I think this code is more efficient than the code in 3.41. Here, the procs are serialized once at the start instead being serialized every time they are called.