Stop learning alone!

Learn faster and stay on-track by joining this free class with other self-learners.

Structure and Interpretation of Computer Programs

Class length: 13 weeks. Start anytime.

Creator: kday

Status: Established

Join this class!

Do all problems in section 3.4 of SICP. Total of 11 problems.

Homework Submissions

1 total

bhrgunatha (Self-grade: Pretty good)
Submitted 1 year ago | Permalink

Exercise 3.38

a

If no interleaving is possible the resulting values can be:

45: Peter +10; Paul -20; Mary /2
35: Peter +10; Mary /2; Paul -20
45: Paul -20; Peter +10; Mary /2
50: Paul -20; Mary /2; Peter +10
40: Mary /2; Peter +10; Paul -20
40: Mary /2; Paul -20; Peter +10

b

A couple of timing diagrams showing other values possible when interleaving is allowed

$50
$110

Exercise 3.39

There are three possible outcomes remaining now:

101: P1 sets x to 100 and then P2 increments x to 101.
100: P1 accesses x (twice), then P2 sets x to 11, then P1 sets x.
121: P2 increments x to 11 and then P1 sets x to x times x.

Exercise 3.40

There are 5 possible values of interleaving the 2 processes:

100 : P1 reads x twice, P2 reads x 3 times , P2 sets x to 1,000, P1 sets x to 100
1,000 : P1 reads x twice, P2 reads x 3 times, P1 sets x to 100, P2 sets x to 1,000
10,000 (1) : P1 reads x once (10), P2 sets x to 1,000, P1 reads x again (1,000) and sets x to 10,000
10,000 (2) : P2 reads x twice (10), P1 sets x to 100, P2 reads x again (100) and sets x to 10,000
100,000 : P2 reads x once (10), P1 sets x to 100, P2 reads twice again (100) and sets x to 100,000
1,000,000 (1) : P1 reads x twice, xx, sets x to 100, P2 reads x 3 times, calculates xx*x, sets x to 1,000,000
1,000,000 (2) : P2 reads x 3 times. xxx, sets x to 1,000, P2 reads x twice, x*x, sets x to 1,000,000

When the 2 processes are serialised there is only value 1,000,000

Exercise 3.41

Ben’s change doesn’t add anything in this simple example since mutations are serialised.

Exercise 3.42

It’s a safe change to make, since everything is ultimately handled by the same serialiser. Instead of having a new feed to pass procedure calls into the serialiser every time the mutating procedures is called, two separate feeds are created, one for deposits and one for withdrawals.

Exercise 3.43

Timing diagram showing a 3 account exchange

Since withdraw and deposit are both serialised once the difference, d1 has been calculated on accounts a1 and a2, d1 is added to a2 and subtracted from a1. Suppose that another concurrent exchange occurs between account a3 and a2, with difference d2, but that the concurrency mechanism, while allowing serialised access to a single account, doesn’t apply correctly to two accounts and we see unexpected results. Total before exchanges: a1 + a2 + a3 step 1: P1: a1 = a1 – d1 step 2: P2: a2 = a2 – d2 step 3: P1: a2 = a2 + d1 = a2 – d2 + d1 step 4: P2: a3 = a3 + d2 Total after exchanges: a1-d1 + a2-d2+d1 + a3+d2 = a1 + a2 + a3

I’m not drawing the other diagram. It’s clear that two processes each accessing two resources and mutating both (even when serialising access to each one) has exactly the same problem as two processes accessing a single resource and mutating them.

Exercise 3.44

Louis is wrong in this simple scenario. In exercise 3.43 we showed the total is preserved and so it is safe to write transfer in this way - assuming that the procedure doesn't crash in between the two mutations. The key difference between transfer and exchange is that transfer is a 3 step procedure (calculate difference, withdraw, deposit). Mathematically exchange seems to be 3 steps as well, but it should considered 4 steps (calculate difference, withdraw, calculate difference, deposit).

Exercise 3.45

If s1 is account1?s serialiser and s2 is account2?s serialiser, then exchange is called from an environment protected by both s1 and s2. Within that environment a call to ((account1 'withdraw) difference) is made which will use s1 to call (withdraw difference), but s1 is already protecting the call to exchange and so withdraw can’t be evaluated until exchange has completed which it obviously can't do.

Exercise 3.46

This is basically the same problem as two procedures mutating a single account without serialising operations. The timing diagram is identical to the one in the book.

Timing diagram of non-serilaised test-and-set!

Exercise 3.47

a. See below b. See below

Exercise 3.48

See below. I think my approach is right, but I can't say for sure whether the arguments of account1 and account2 are correct in both branches of the if statement.

Exercise 3.49

The question hints that this mechanism can fail when we only realise what other resources we need access to once we’ve acquired a lock – the most obvious example of this is database mutations. Earlier in the book though we saw joint accounts and I guess this would also need a different deadlock resolution.

;; Exercise 3.47a
(define (make-sempahore n)
  (let ((count n)
        (the-mutex (make-mutex)))
    (define (the-sempahore m)
      (cond ((eq? m 'acquire)
             (the-mutex 'acquire)
             (if (zero? count)
                 (begin
                   (the-mutex 'release)
                   (the-semaphore 'acquire))
                 (begin
                   (set! count (- count 1))
                   (the-mutex 'release))))
            ((eq? m 'release)
             (the-mutex 'acquire)
             (if (= count n)
                 (the-mutex 'release)
                 (begin
                   (set! count (+ count 1))
                   (the-mutex 'release))))))
    the-sempahore))

;; Exercise 3.47b
(define (make-sempahore n)
  (let ((count n)
        (cell (list false)))
    (define (the-sempahore m)
      (cond ((eq? m 'acquire)
             (if (test-and-set! cell)
                 (the-semaphore 'acquire)
                 (if (zero? count)
                     (clear! cell)
                     (begin
                       (set! count (- count 1))
                       (clear! cell)))))
            ((eq? m 'release)
             (if (test-and-set! cell)
                 (the-semaphore 'release)
                 (if (= count n)
                     (clear! cell)
                     (begin
                       (set! count (+ count 1))
                       (clear! cell)))))))
    the-sempahore))

;;Exercise 3.48
(define (make-account balance acct-num)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (let ((balance-serializer (make-serializer)))
    (define (dispatch m)
      (cond ((eq? m 'withdraw) withdraw)
            ((eq? m 'deposit) deposit)
            ((eq? m 'balance) balance)
            ((eq? m 'serializer) balance-serializer)
            ((eq? m 'acct-num) acct-num)
            (else (error "Unknown request -- MAKE-ACCOUNT"
                         m))))
    dispatch))

(define (exchange account1 account2)
  (let ((difference (- (account1 'balance)
                       (account2 'balance))))
    ((account1 'withdraw) difference)
    ((account2 'deposit) difference)))

(define (serialized-exchange account1 account2)
  (let ((serializer1 (account1 'serializer))
        (serializer2 (account2 'serializer))
        (id1 (account1 'acct-num))
        (id2 (account2 'acct-num)))
    (if (< id1 id2)
        ((serializer2 (serializer1 exchange))
         account1
         account2)
        ((serializer1 (serializer2 exchange))
         account1
         account2))))

No comments. Sign up or log in to comment