Ex-3.47

A mutex is an object that supports two operations - aquire and release. Once a mutex is aquired, no other process can aquire it unless it has been released. mutex is implemented using an *atomic* operation test-and-set! that tests value in a cell, returns true if cell value is already set to true or else sets the cell value to true and returns false.

A semaphore (of size n) is a generalization of a mutex. Like a mutex, a semaphore supports acquire and release operations, but it is more general in that up to n processes can acquire it concurrently. Additional processes that attempt to acquire the semaphore must wait for release operations.

(a) - semaphore implementation using mutex

(define (make-semaphore n)
(let ((m (make-mutex))
   (count 0)
   (result false))
(define (aquire)
 (m 'aquire)
 (if (> count 0)
     (set! count (- count 1)))
 (m 'release))
(define (dispatch msg)
 (cond
  ((eq? msg 'aquire) (aquire))
  ((eq? msg 'release) (release))
  (else "Unknown msg to SEMAPHORE: " msg)))
dispatch))

(b) - semaphore implementation using test-and-set

(define (clear! cell)
(set-car! cell false))

(define (make-semaphore n)
;makes a list of n cells
(define (make-cells n)
  (define (iter n a)
    (if (= n 0) a
        (iter (- n 1) (cons (list false) a))))
  (iter n '()))

(let ((cells (make-cells n)))
  (define (aquire)
    (define (iter cells)
      (cond
       ((null? cells) (aquire))
       ((not (test-and-set! (car cells)))
        true)
       (else (iter (cdr cells)))))
    (iter cells))
  (define (release)
    (define (iter cells)
      (cond
       ((null? cells)
        ;all the cells are already in released state
        ;nothing to do
        'ok)
       ((caar cells)
        (clear! (car cells)) 'ok)
       (else (iter (cdr cells)))))
    (iter cells))
  (define (dispatch msg)
    (cond
     ((eq? msg 'aquire) (aquire))
     ((eq? msg 'release) (release))
     (else "Unknown msg to SEMAPHORE: " msg)))
  dispatch))

Ex-3.46

Let say 2 processes try to aquire the mutex simultaneously when its in released state

(define (test-and-set! cell)
  (if (car cell)
      true
      (begin (set-car! cell true)
             false)))

Let P1 denote the event of first process calling (car cell) and P2 denote the event of first process calling (set-car! cell true). Similarly let Q1 denote the event of second process calling (car cell) and Q2 denote the event of second process calling (set-car! cell true).

Since test-and-set! is not atomic, so following interleaved execution sequence is possible...

P1 Q1 P2 Q2

With this sequence both the processes will aquire the mutex and mutex symantics that only one can aquire it at one time is broken.

Serializer Implementation..

Serializer is implemented in terms of another primitive called "mutex", that has two operations to "aquire" and "release" it. At one time only one process can aquire the mutex, other processes trying to aquire it at that time will block untill the mutex is released by the process that has the mutex aquired.
BTW, if multiple processes were waiting for the mutex to be released.. which of those processes get to aquire the mutex depends upon a component called scheduler.

Ex-3.45

There will be a deadlock. Here is why...

(serialized-exchange account1 account2)
...
...
(serializer1 (serializer2 exchange) account1 account2)
...
Notice, call to exchange is serialized in both the
serializers, so they won't let any other serialized
procedure run unless this call completes.

exchange makes following call..
(- (account1 'balance) (account2 'balance))
...
(account1 'balance)
This is a serialized call with the given code in the 
problem and will be blocked because serializer1 is still 
waiting for exchange call to complete.

Ex-3.44

No, given implementation of transfer is fine. Its different from exchange because in exchange, difference between the balance of two accounts is calculated without any serialization constraints and transfer doesn't have it.

Ex-3.42

It is safe and there is no difference.

Ex-3.41

No, checking the balance is a read-only operation and doesn't result in any anomalous behavior even when unserialized. Serializing it will just hamper the performance for no good.

Ex-3.40

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

Let P, Q represent both procedures and Pk/Qk denotes accessing value of x the kth time then following possibilities are possible..

x = 1000000: P1, P2, P sets x, Q1, Q2, Q3, Q sets x
x = 1000000: Q1, Q2, Q3, Q sets x, P1, P2, P sets x
x = 10000: P1, Q1, Q2, Q3, Q sets x, P2, P sets x
x = 100: P1, P2, Q1, Q2, Q3, Q sets x, P sets x
x = 100000: Q1, P1, P2 ,P sets x, Q2, Q3, Q sets x
x = 10000: Q1, Q2, P1, P2, P sets x, Q3, Q sets x
x = 1000: Q1, Q2, Q3, P1, P2, P sets X, Q sets x

.... There are other execution sequences possible also, but all the possible values that x can take after the execution are {100, 1000, 10000, 100000, 1000000}

In the next case when P, Q are serialized. After the execution, x can only be 1000000.

In general, This phenomenon when multiple threads/processes are modifying the same resource and final value of the resource could be different depending upon the interleaving is called "Race Condition"

Ex-3.39

Following 3 possibilities remain..

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

Ex-3.38

;Ex-3.38 a
Without interleaving there are 6(Fact(3) ways in which they can do their transactions) cases possible.

1. Peter, Paul, Mary .. balance: $45
2. Paul, Peter, Mary .. balance: $45
3. Peter, Mary, Paul .. balance: $35
4. Paul, Mary, Peter .. balance: $50
5. Mary, Peter, Paul .. balance: $40
6. Mary, Paul, Peter .. balance: $40

;Ex-3.38b
deposit/withdraw of Peter/Paul can be divided in 2 steps
(set! balance (+/ balance amt))
1. Access the current balance
2. Calculating (+/- balance amt) and setting balance to the calculated value.

Let us denote these 2 steps for both person's transactions as Peter-1, Peter-2, and Paul-1, Paul-2.

withdraw of Mary can be divided in 3 steps
(set! balance (- balance (/ balance 2)))
Mary-1: Access the balance for calculating (/ balance 2)
Mary-2: Access the balance for calculating (- balance (/..
Mary-3: Setting balance to value calculated in step Mary-2


One of the possible execution sequence could be....

Peter-1 Paul-1 Mary-1 Peter-2 Paul-2 Mary-2 Mary-3

..with this sequence the final balance would be... $30

Ex-3.35

code from book for constraint network.

(define (squarer a b)
  (define (process-new-value)
    (if (has-value? b)
        (if (< (get-value b) 0)
            (error "square less than 0 -- SQUARER" (get-value b))
            (set-value! a (sqrt (get-value b)) me))
        (if (has-value? a)
            (set-value! b (square (get-value a)) me))))
  (define (process-forget-value)
    (forget-value! a me)
    (forget-value! b me)
    (process-new-value))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request -- SQUARER" request))))
  (connect a me)
  (connect b me)
  me)

;;tests
(define A (make-connector))
(define B (make-connector))
(probe "A" A)
(probe "B" B)

(squarer A B)

(set-value! A 3 'user)
;Probe: B = 9
;Probe: A = 3
;Value: done

(forget-value! A 'user)
;Probe: B = ?
;Probe: A = ?
;Value: done

(set-value! B 25 'user)
;Probe: A = 5
;Probe: B = 25
;Value: done 

Ex-3.34

code from book for constraint network.

;;Lets Experiment
(define (squarer a b)
 (multiplier a a b))
(define A (make-connector))
(define B (make-connector))
(Probe "A" A)
(Probe "B" B)
(squarer a b)

(set-value! A 5 'user)
;Probe: A = 5
;Probe: B = 25
;Value: done

(forget-value! A 'user)
;Probe: A = ?
;Probe: B = ?
;Value: done

(set-value! B 16 'user)
;Probe: B = 16
;Value: done 

Case-I: Setting value in A ,B doesn't have a value yet.
It works - No issue.

Case-II: Setting value in B, A doesn't have a value yet.
It does *NOT* work.
Reason:
On setting the value in B, when multiplier will be informed about value.. no cond clause are applicable because two of the three connectors does not have any value(as two connectors are same) and the call is simply ignored.

Ex-3.33

code from book for constraint network.

(define (averager a1 a2 av)
(define (process-new-value)
  (cond ((and (has-value? a1) (has-value? a2))
         (set-value! av
                     (/
                      (+ (get-value a1) (get-value a2))
                      2) me))
        ((and (has-value? a1) (has-value? av))
         (set-value! a2
                     (- (* 2 (get-value av)) (get-value a1))
                     me))
        ((and (has-value? a2) (has-value? av))
         (set-value! a1
                     (- (* 2 (get-value av)) (get-value a2))
                     me))))
(define (process-forget-value)
  (forget-value! av me)
  (forget-value! a1 me)
  (forget-value! a2 me)
  (process-new-value))
(define (me request)
  (cond ((eq? request 'I-have-a-value)
         (process-new-value))
        ((eq? request 'I-lost-my-value)
         (process-forget-value))
        (else
         (error "Unknown request -- AVERAGER" request))))
(connect a1 me)
(connect a2 me)
(connect av me)
me)

;;Test
(define A (make-connector))
(define B (make-connector))
(define C (make-connector))
(probe "A" A)
(probe "B" B)
(probe "C" C)
(averager A B C)

(set-value! A 2 'user)
;Probe: A = 2
;Value: done
(set-value! B 4 'user)
;Probe: C = 3
;Probe: B = 4
;Value: done
(forget-value! A 'user)
;Probe: C = ?
;Probe: A = ?
;Value: done
(set-value! C 8 'user)
;Probe: A = 12
;Probe: C = 8
;Value: done
(forget-value! B 'user)
;Probe: A = ?
;Probe: B = ?
;Value: done
(forget-value! C 'user)
;Probe: C = ?
;Value: done
(set-value! A 4 'user)
;Probe: A = 4
;Value: done
(ser-value! C 10 'user)
;Probe: B = 16
;Probe: C = 10
;Value: done

section-3.3.5 Propagation of Constraint code

Just pasting the code for Constraint Networks from book here to run and interact with it...

;;========CONNECTOR============
;;connector implementation
(define (make-connector)
  (let ((value false) (informant false) (constraints '()))
    (define (set-my-value newval setter)
      (cond ((not (has-value? me))
             (set! value newval)
             (set! informant setter)
             (for-each-except setter
                              inform-about-value
                              constraints))
            ((not (= value newval))
             (error "Contradiction" (list value newval)))
            (else 'ignored)))
    (define (forget-my-value retractor)
      (if (eq? retractor informant)
          (begin (set! informant false)
                 (for-each-except retractor
                                  inform-about-no-value
                                  constraints))
          'ignored))
    (define (connect new-constraint)
      (if (not (memq new-constraint constraints))
          (set! constraints
                (cons new-constraint constraints)))
      (if (has-value? me)
          (inform-about-value new-constraint))
      'done)
    (define (me request)
      (cond ((eq? request 'has-value?)
             (if informant true false))
            ((eq? request 'value) value)
            ((eq? request 'set-value!) set-my-value)
            ((eq? request 'forget) forget-my-value)
            ((eq? request 'connect) connect)
            (else (error "Unknown operation -- CONNECTOR"
                         request))))
    me))
(define (for-each-except exception procedure list)
  (define (loop items)
    (cond ((null? items) 'done)
          ((eq? (car items) exception) (loop (cdr items)))
          (else (procedure (car items))
                (loop (cdr items)))))
  (loop list))

;;connector interface
(define (has-value? connector)
  (connector 'has-value?))
(define (get-value connector)
  (connector 'value))
(define (set-value! connector new-value informant)
  ((connector 'set-value!) new-value informant))
(define (forget-value! connector retractor)
  ((connector 'forget) retractor))
(define (connect connector new-constraint)
  ((connector 'connect) new-constraint))

;;==========CONSTRAINTS================

;;generic constraint interface
(define (inform-about-value constraint)
  (constraint 'I-have-a-value))
(define (inform-about-no-value constraint)
  (constraint 'I-lost-my-value))

;;adder constraint implementation
(define (adder a1 a2 sum)
  (define (process-new-value)
    (cond ((and (has-value? a1) (has-value? a2))
           (set-value! sum
                       (+ (get-value a1) (get-value a2))
                       me))
          ((and (has-value? a1) (has-value? sum))
           (set-value! a2
                       (- (get-value sum) (get-value a1))
                       me))
          ((and (has-value? a2) (has-value? sum))
           (set-value! a1
                       (- (get-value sum) (get-value a2))
                       me))))
  (define (process-forget-value)
    (forget-value! sum me)
    (forget-value! a1 me)
    (forget-value! a2 me)
    (process-new-value))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request -- ADDER" request))))
  (connect a1 me)
  (connect a2 me)
  (connect sum me)
  me)

;;multiplier constraint implementation
(define (multiplier m1 m2 product)
  (define (process-new-value)
    (cond ((or (and (has-value? m1) (= (get-value m1) 0))
               (and (has-value? m2) (= (get-value m2) 0)))
           (set-value! product 0 me))
          ((and (has-value? m1) (has-value? m2))
           (set-value! product
                       (* (get-value m1) (get-value m2))
                       me))
          ((and (has-value? product) (has-value? m1))
           (set-value! m2
                       (/ (get-value product) (get-value m1))
                       me))
          ((and (has-value? product) (has-value? m2))
           (set-value! m1
                       (/ (get-value product) (get-value m2))
                       me))))
  (define (process-forget-value)
    (forget-value! product me)
    (forget-value! m1 me)
    (forget-value! m2 me)
    (process-new-value))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request -- MULTIPLIER" request))))
  (connect m1 me)
  (connect m2 me)
  (connect product me)
  me)

;;constant constraint implementation
(define (constant value connector)
  (define (me request)
    (error "Unknown request -- CONSTANT" request))
  (connect connector me)
  (set-value! connector value me)
  me)



;; Probe
(define (probe name connector)
  (define (print-probe value)
    (newline)
    (display "Probe: ")
    (display name)
    (display " = ")
    (display value))
  (define (process-new-value)
    (print-probe (get-value connector)))
  (define (process-forget-value)
    (print-probe "?"))
  (define (me request)
    (cond ((eq? request 'I-have-a-value)
           (process-new-value))
          ((eq? request 'I-lost-my-value)
           (process-forget-value))
          (else
           (error "Unknown request -- PROBE" request))))
  (connect connector me)
  me)

;;====== 9C = 5(F - 32) Relation Simulation ========
(define (celsius-fahrenheit-converter c f)
  (let ((u (make-connector))
        (v (make-connector))
        (w (make-connector))
        (x (make-connector))
        (y (make-connector)))
    (multiplier c w u)
    (multiplier v x u)
    (adder v y f)
    (constant 9 w)
    (constant 5 x)
    (constant 32 y)
    'ok))

(define C (make-connector))
(define F (make-connector))
(probe "Celsius temp" C)
(probe "Fahrenheit temp" F)

(celsius-fahrenheit-converter C F)
(set-value! C 25 'user)
;Probe: Celsius temp = 25
;Probe: Fahrenheit temp = 77
;done

(set-value! F 212 'user)
;Error! Contradiction (77 212)

(forget-value! C 'user)
;Probe: Celsius temp = ?
;Probe: Fahrenheit temp = ?
;done

(set-value! F 212 'user)
;Probe: Fahrenheit temp = 212
;Probe: Celsius temp = 100
;done

event-driven simulation

In section 3.3.4, SICP presents a digital circuit simulator that implements it using a design called event-driven programming. In such designs basically actions("events") triggers further events that happen at a later time and those in turn trigger further events and so on.
To be particular about the example given in the book, Wire is the main object where we can set signal and can add any number of events(no-arg procedures). Whenever a signal changes(event of signal change happens), it triggers all the events added to it and those events when happen change signal on other wires which in turn trigger more events and so on... that is how the signal propagates.

I also wrote a port of this example in scala here.