今回のあらすじ
SICPの3.4.2 Mechanisms for Controlling ConcurrencyのImplementing 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
timeExercise 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 semaphoresa. in terms of mutexes
b. in terms of atomic test-and-set! operations.
a. in terms of mutexes
semaphore は mutex の拡張なので、 make-semaphore は make-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 版の実装のうち、acquire と release を差し替えるだけですね:
(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 ConcurrencyのDeadlockからラストのConcurrency, time, and communicationまでバリバリ読み進めます。
＃人気の記事
＃タグ
