Language : Japanese English

iwk - 2008/07/20 12:58:44

具体例を出すと、
(define acc (make-account-and-serializer 100))

として
((acc 'deposit) 100)
とするのは当然問題なくbalanceは200となります。
しかしながら、
(define the-balance-serializer (acc 'serializer))
(define new-deposit (the-balance-serializer (acc 'deposit)))
とすると無限ループに陥ります。

iwk - 2008/07/20 13:05:02

ちょっと動作を追えていないのですが多分(mutex 'release)していない団塊で(mutex 'acquire)を呼び出している部分が出てくるせいだと思います。
段階○
団塊×
うーん。なんだか後味が悪い・・・。
それで、回避策として私が述べた、新しいserializerをもう一つ作ればよいというのは、nagaさんのおっしゃるとおりあんまり良くないですね。
なぜかというと、例えば、具体的にmake-account-and-serializerプロシージャの内部定義において
(let ((serializer1 (make-serializer))
(serializer2 (make-serializer)))
(define (dispatch m)
(cond ((eq? m 'withdraw) (serializer1 withdraw))
((eq? m 'deposit) (serializer2 deposit))
...以下略)
という風に定義してしまうとwithdrawとdepositは一連化されているにもかかわらず互いに独立しており、互いに介入可能になってしまうからです。
理由としては、変数cellを共有していない為です。
にしても、3.45は確かにImplementing serializerを読まないと回答不能ですね。

iwk - 2008/07/20 13:32:01

Exercise3.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
テキストに示されているように、実装よりの操作を作ったりせずに、普通の手続きを使ってtest-and-set!を実装せよ。

iwk - 2008/07/20 13:39:15

同時に2つのプロセスが同一(the mutexなので)のmutexを呼び出すことを許すことでどうしてmutexの実行が失敗する可能性があるのか証明するために図3.29における一例のようなタイミングダイアグラムを描け。
-----
図書くのは苦手なんですけどExcel使ったらなんとかなるかなぁ。

iwk - 2008/07/20 13:53:27

投稿画像
こんな感じ?

iwk - 2008/07/20 13:57:10

投稿画像
少しそれっぽくしてみた。
ふー。というわけでやっと今週やるべきところの範囲に到達できました。アホだ。
Exercise3.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 conccurently.
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.

iwk - 2008/07/20 14:04:58

semaphoreが訳せない。

iwk - 2008/07/20 14:25:23

(サイズnの)semaphoreはmutexの一般化である。

iwk - 2008/07/20 14:29:10

mutexのようにsemaphoreはacquireとreleaseの演算をサポートするが、n個のプロセスを並列的に補足するという点においてより一般的である。
付加的な、semaphoreを補足することを試みるプロセスは、releaseオペレーションが呼ばれるまで待たなければならない。
semaphoreの実装を与えよ。
a. mutexの見地から
b. 実装よりのtest-and-set!オペレーションの見地から。
難しいのでパス。

naga - 2008/07/20 18:43:27

atomicallyは、これ以上分割できないというような意味で、それを使った部分は「test-and-set!は2つ以上のプロセスが同時に実行できないように計算機システムで用意されている仕組みを使って実装されなければならない。」みたいな意味だと思います。

iwk - 2008/07/20 23:50:16

なるほど。その観点からちょっと読み直してみます。

iwk - 2008/07/21 00:29:02

脚注の46を読んで納得できました。確かにその通りですね。testとsetの間に何らかの介入が起きてしまったら一連化システム自体が破綻してしまうわけですね。
というわけで、厳密に言えばSICPにおけるtest-and-set!の実装はよろしく無い。介入が発生する余地があります。
gaucheのmutexはきっとここらへんをうまく介入が起きないように実装しているのですね。一度gaucheのmutexを読んでみるのもいいかもしれないです。
すみません。日本語が変ですね。

iwk - 2008/07/21 01:13:04

Exercise3.47~3.49わからない。orz
とりあえず、今週の分の宣言だけやっときます。今週はExercise3.52まで。

Lingrアカウントをお持ちの方は、ページ右上のメニューからログインして下さい。

ニックネーム:

 

投稿ショートカット: / /

計算機プログラムの構造と解釈読書会

アイコン
閲覧者---
最終更新2008/07/25 18:28:36
地域Japan
入退出の挨拶はいりません。ただただ自分の能力を上げることを第一に考えてください。
スローガンは「誰かの為にじゃなくて自分のために」。

【SICP】計算機プログラムの構造と解釈【Scheme】
http://pc11.2ch.net/test/read.cgi/tech/1107345738/

で企画された計算機プログラムの構造と解釈の輪読会用ルームです。

目的:SICPを読むことでの個々の能力の向上
意義:
1.自分ひとり読んでいたのでは思いつかないアイデアに触れられる
2.分からないことを人に聞ける
3.一人で読んでいたらめんどくさがってパスしまうようなハードルもまじめに超えてやろうと思える。
4.本を読み進めるにあたってのペースメーカーになる
5.近場で勉強会、読書会が開催されない(できない)地方の人が参加できる。
LingrのルームページURLを入力すると、対応するLingrBBSページを表示します。


運営サイト一覧

AnyWare+ PODCAST-BP PHP Rampart