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.