TIM Labs

SICP読書会(Exercise 3.46 - Exercise 3.47)

| コメント(0) | トラックバック(0)

今回のあらすじ

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 までバリバリ読み進めます。

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/455

コメントする

このブログ記事について

このページは、kanaが2015年2月28日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「SICP読書会(Exercise 3.43 - Exercise 3.45)」です。

次のブログ記事は「JavaScript でオセロを実装する(ネット対戦編)」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。