Scheme - 並列性の制御機構(相互排除器の一般化(セマフォ(semaphore)))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の3(標準部品化力, オブジェクトおよび状態)、3.4(並列性)、3.4.2(並列性の制御機構)、直列変換器の実装、問題 3.46、問題 3.47を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題3.46

プロセス1がセルを真に設定したのに、プロセス2がセルをテストする前にセルの内容が実際に真に設定されていない。よって、二つのプロセスが同時に相互排除器を獲得するのを許すと、相互排除の実装が破綻してしまう。

問題 3.47

a. 相互排除器を使って実装した場合。

コード(BBEdit)

sample.scm

(define (make-semaphore n)
  (let ((counter 0)
        (mutex (make-mutex)))
    (define (the-semaphore m)
      (cond ((eq? m 'acquire)
             (mutex 'acquire)
             (if (<= counter n)
                 (begin (set! counter (+ counter 1))
                        (mutex 'release))
                 (begin (mutex 'release)
                        (the-semaphore 'acquire))))
            ((eq? m 'release)
             (mutex 'acquire)
             (if (> n 0) (set! counter (- counter 1)))
             (mutex 'release))))
    the-semaphore))

b. test-and-set!を使って実装した場合。

コード(BBEdit)

sample.scm

(define (make-semaphore n)
  (let ((counter 0)
        (cell (list false)))
    (define (the-semaphore m)
      (cond ((eq? m 'acquire)
             (if (or (test-and-set! cell)
                     (> counter n))
                 (the-semphore m'acquire)  ; retry
                 (begin (set! counter (+ counter 1))
                        (clear! cell))))
            ((eq? m 'release)
             (if (> counter 0) (set! counter (- counter 1)))
             (clear! cell))))
    the-smaphore))