SICP問題3.46

直列変換器の実装(教科書で定義)

(define (make-serializer)
  (let ((mutex (make-mutex)))
    (lambda (p)
      (define (serialized-p . args)
        (mutex 'acquire)
        (let ((val (apply p args)))
          (mutex 'release)
          val))
      seralized-p)))

相互排除器(mutex)の実装(教科書で定義)
引数は獲得(acquire)と解放(release)

(define (make-mutex)
  (let ((cell (list #f)))
    (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 #f))
(define (test-and-set! cell)
  (if (car cell)
      #f
      (begin (set-car! cell #t)
             #f)))

上記のtest-and-set!の場合、二つのプロセスが同時に相互排除器を獲得すると、相互排除器の実装が破綻することを示す

        P1                  cell                P2
(mutex 'acquire)            #f          (mutex 'acquire)
        ↓                  ↓                  ↓
(test-and-set! cell)        #f          (test-and-set! cell)
        ↓                  ↓                  ↓
(if (car cell)) ───→    #f                  ↓
        ↓                  ↓                  ↓
        ↓                  #f ←─── (if (car cell))
        ↓                  ↓                  ↓
(set-car! cell #t)          #t                  ↓
        ↓                  ↓                  ↓
        ↓                  #t          (set-car! cell #t)

この時点で両方のプロセスでが相互排除器の獲得が出来てしまう。