SICP読書会(Exercise 3.46 – Exercise 3.47)


2015年 02月 28日

今回のあらすじ

SICP3.4.2 Mechanisms for Controlling ConcurrencyImplementing serializersをバリバリ読んでExercise 3.47まで解きます。

正常に動かないサンプル実装を眺める図

Implementing serializers

今まで存在を仮定していたserializerを実装する話です。
しかし、

  • serializer を実装する為に mutex の存在を仮定して
  • mutex を実装する為に test-and-set! の存在を仮定して
  • でも test-and-set! は実行システムに依存するのでSchemeレベルでは実装できない

という若干の残念さがある流れです。

Exercise 3.46

Suppose that we implement test-and-set! using an ordinary procedure as
shown in the text, without attempting to make the operation atomic. Draw
a timing diagram like the one in figure 3.29 to demonstrate how the mutex
implementation can fail by allowing two processes to acquire the mutex at the
same time.

この問題は3.4節でこれまで散々やってきた銀行口座の例と同じ形なので簡単ですね。

テキスト中の test-and-set! のイメージ実装は

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

ですが、これは

  • cell のチェック
  • cell の設定

の2ステップが存在するので、以下のような状況で残念な結果になりますね:

 |   Process 1        cell       Process 2
 |                    (#f)
 |        _____________||_____________
 |        |                          |
 |  [acccess cell]                   |
 |        |                    [acccess cell]
 |        |                          |
 |        |                    [modify cell]
 |  [modify cell]       _____________|
 |        |             |
 |        |             v      [return false]
 |        |           (#t)
 |        |_____________
 |                     |
 |  [return false]     v
 |                    (#t)
 v
time

Exercise 3.47

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. Give
implementations of semaphores

a. in terms of mutexes

b. in terms of atomic test-and-set! operations.

a. in terms of mutexes

semaphore は mutex の拡張なので、 make-semaphoremake-mutex と同じ要領で書けば良さそうですね。
一先ず make-mutex を雛型にして概形を書きましょう:

(define (make-semaphore n)
  (let (...)
    (define (acquire)
      ...)
    (define (release)
      ...)
    (define (dispatch m)
      (cond [(eq? m 'acquire) (acquire)]
            [(eq? m 'release) (release)]
            [else (error "Unknown message sent to a semaphore" m)]))
    dispatch))

let で用意する変数ですが、

  • お題は「in terms of mutex」なので mutex が1つ必要
  • nプロセスまで同時利用が可能なので現在の利用プロセス数が必要

になりますね:

(let ([mutex (make-mutex)]
      [c 0])
  ...)

acquire に関しては

  • 空席が残ってれば1つ消費する
  • 空席が残ってなければ席が空くまで待つ

というロジックになるので簡単ですね:

(define (acquire)
  (mutex 'acquire)
  (cond [(< c n)
         (set! c (+ c 1))
         (mutex 'release)]
        [else
          (mutex 'release)
          (acquire)]))

release に関しては

  • 席を1つ空ける

だけなので簡単ですね:

(define (release)
  (mutex 'acquire)
  (set! c (- c 1))
  (mutex 'release))

とはいえ、 acquire の前に release をする等、
うっかりさんが release が余分に行ってしまう可能性があるので、
一応エラーチェックは入れた方が良いでしょう:

(define (release)
  (mutex 'acquire)
  (if (<= 1 c)
    (set! c (- c 1))
    (error "This semaphore is not acquired yet"))
  (mutex 'release))

全体としては以下の実装になりました:

(define (make-semaphore n)
  (let ([mutex (make-mutex)]
        [c 0])
    (define (acquire)
      (mutex 'acquire)
      (cond [(< c n)
             (set! c (+ c 1))
             (mutex 'release)]
            [else
              (mutex 'release)
              (acquire)]))
    (define (release)
      (mutex 'acquire)
      (if (<= 1 c)
        (set! c (- c 1))
        (error "This semaphore is not acquired yet"))
      (mutex 'release))
    (define (dispatch m)
      (cond [(eq? m 'acquire) (acquire)]
            [(eq? m 'release) (release)]
            [else (error "Unknown message sent to a semaphore" m)]))
    dispatch))

b. in terms of atomic test-and-set! operations.

これは先程の mutex 版の実装のうち、
acquirerelease を差し替えるだけですね:

(define (acquire)
  (if (test-and-set! cell)
    (acquire)
    (cond [(< c n)
           (set! c (+ c 1))
           (clear! cell)]
          [else
            (clear! cell)
            (acquire)])))

(define (release)
  (cond [(test-and-set! cell)
         (release)]
        [else
          (if (<= 1 c)
            (set! c (- c 1))
            (error "This semaphore is not acquired yet"))
          (clear! cell)])

make-semaphore の残りの部分は mutex 版と一緒なので省略します。

mutex 版と test-and-set! 版を比較すると、
mutex 版の方がまだ読み易い感じがしますね。

次回予告

3.4.2 Mechanisms for Controlling ConcurrencyDeadlockからラストのConcurrency, time, and communicationまでバリバリ読み進めます。