サンタクロース問題を Squeak Smalltalk で

Squeak Smalltalk


Squeak Smalltalk のスレッドは、処理を記述したブロック [...] に fork を送信することで、手軽に作ってフォークさせられます。ただ、よほどのことがない限り、他へは制御を渡さないので(^_^;)、今回の求められているように、複数のスレッドを同時並行的に走らせたいときは適当なタイミングで Processor yield し、明示的に切り替える必要があります。なお、Samlltalk ではスレッドのことをプロセス（a Process）と呼称し、クラス名も同じです。きっと、暫定ダイナブックの OS であったころの名残りでしょう。

セマフォ（a Semaphore）は wait すると別のスレッドで signal されるまでアクティブスレッドを待ち合わせします。new ではなく、forMutualExclusion で作ったセマフォ（あらかじめシグナル済みのセマフォ）は、critical: [...] で排他的処理を記述するのに使えます。

共有キュー（a SharedQueue）は、スレッドセーフな待ち行列です。中身が空（から）のとき、要素を取り出そうとするとそのスレッドを停止して、他のスレッドで追加されるまで待たせる機能も持っています。



これらの機能を用いて、与えられた問題を記述してみます。



サンタは、９頭いるトナカイ全員が戻ってくるか、こびとが３人がやってきて起こしてくれるまで待っています（サンタを起こす wait）。

９頭組のトナカイに起こされたら、ハーネスをつけて（ソリの準備 signal）ソリを引かせてオモチャを配りに行きます。配りおわったらトナカイたちのハーネスを外して解放し、彼らが出かけるのを見届けて（トナカイの解散 wait）また寝ます。

３人組のこびとさんたちに起こされたら、会議をひらいて次期のオモチャをどうするかをこびとさんたちに伝授します（問題解決 signal）。会議が終わると、こびとさんたちが仕事に戻るのを見届けて（こびとの退出 wait）から、また寝ます。

| 休暇中のトナカイたち 仕事中のこびとたち 戻ってきているトナカイたち 列んでいるこびとたち
  サンタを起こす ソリの準備 問題解決 こびとの退出 こびと排他 サンタの日常 トナカイの解散
  こびとたちの来訪 こびとたちの順番待ち 出力排他 シミュレーション終了 出力 |

休暇中のトナカイたち := #(
   ダッシャー  ダンサー  プランサー
   ヴィクセン  ドンダー  ブリッツェン 
   キューピッド  コメット  ルドルフ) asOrderedCollection.
仕事中のこびとたち := (($A to: $J) collect: [:chr | 'こびと「{1}」' format: {chr}]) asOrderedCollection.
出力 := String new writeStream.

戻ってきているトナカイたち := SharedQueue new.
列んでいるこびとたち := SharedQueue new.

サンタを起こす := Semaphore new.
ソリの準備 := Semaphore new.
トナカイの解散 := Semaphore new.
問題解決 := Semaphore new.
こびとの退出 := Semaphore new.
シミュレーション終了 := Semaphore new.
こびと排他 := Semaphore forMutualExclusion.
出力排他 := Semaphore forMutualExclusion.

World findATranscript: nil.
Transcript clear.


サンタの日常 := [
   [  サンタを起こす wait.
      出力排他 critical: [出力 cr; nextPutAll: '●サンタ、起こされる'].
      戻ってきているトナカイたち size = 9
         ifTrue: [ソリの準備 signal. トナカイの解散 wait]
         ifFalse: [問題解決 signal. こびとの退出 wait].
      出力排他 critical: [出力 cr; nextPutAll: '●サンタ、寝る'].
      Processor yield.
   ] repeat
] fork.


[ "トナカイの仕事"
   3 timesRepeat: [
      休暇中のトナカイたち := 休暇中のトナカイたち shuffled.
      9 timesRepeat: [
         | 戻ってきたトナカイ |
         戻ってきたトナカイ := 休暇中のトナカイたち removeFirst.
         出力排他 critical: [出力 cr; nextPutAll: '▼トナカイの「', 戻ってきたトナカイ, '」、戻る'].
         戻ってきているトナカイたち nextPut: 戻ってきたトナカイ.
         Processor yield].
      出力排他 critical: [出力 cr; nextPutAll: '▼トナカイたち、サンタを起こす'].
      サンタを起こす signal.
      ソリの準備 wait.
      出力排他 critical: [出力 cr; nextPutAll: '▼サンタとトナカイたち、出発　→　戻る'].
      9 timesRepeat: [休暇中のトナカイたち add: 戻ってきているトナカイたち next].
      出力排他 critical: [出力 cr; nextPutAll: '▼トナカイたち、ふたたびバケーションへ'].
      トナカイの解散 signal.
      Processor yield].
   シミュレーション終了 signal
] fork.


こびとたちの来訪 := [
   [  こびと排他 critical: [仕事中のこびとたち ifNotEmpty: [
         | こびと |
         こびと := 仕事中のこびとたち remove: 仕事中のこびとたち atRandom.
         出力排他 critical: [出力 cr; nextPutAll: こびと, '、来訪'].
         列んでいるこびとたち nextPut: こびと]].
      Processor yield
   ] repeat
] fork.


こびとたちの順番待ち := [
   [  | 三人組 |
      三人組 := (1 to: 3) collect: [:idx | 列んでいるこびとたち next].
      出力排他 critical: [出力 cr; nextPutAll: 三人組 printString, '、サンタを起こす'].
      サンタを起こす signal.
      問題解決 wait.
      出力排他 critical: [出力 cr; nextPutAll: 三人組 printString, '、サンタと問題を解決'].
      こびと排他 critical: [仕事中のこびとたち addAll: 三人組].
      出力排他 critical: [出力 cr; nextPutAll: 三人組 printString, '、自分の仕事に戻る'].
      こびとの退出 signal.
      Processor yield
   ] repeat
] fork.


シミュレーション終了 wait.
サンタの日常 terminate.
こびとたちの来訪 terminate.
こびとたちの順番待ち terminate.
Transcript show: 出力 contents, '　……'


サンタの日常 terminate とか、ちょっとブラックですね(^_^;)。出力例はこんなかんじ。

▼トナカイの「プランサー」、戻る
こびと「C」、来訪
▼トナカイの「ブリッツェン」、戻る
こびと「E」、来訪
▼トナカイの「キューピッド」、戻る
こびと「A」、来訪
▼トナカイの「ドンダー」、戻る
#('こびと「C」' 'こびと「E」' 'こびと「A」')、サンタを起こす
こびと「J」、来訪
▼トナカイの「コメット」、戻る
●サンタ、起こされる
こびと「F」、来訪
▼トナカイの「ダンサー」、戻る
#('こびと「C」' 'こびと「E」' 'こびと「A」')、サンタと問題を解決
#('こびと「C」' 'こびと「E」' 'こびと「A」')、自分の仕事に戻る
こびと「B」、来訪
▼トナカイの「ヴィクセン」、戻る
●サンタ、寝る
#('こびと「J」' 'こびと「F」' 'こびと「B」')、サンタを起こす
こびと「H」、来訪
▼トナカイの「ルドルフ」、戻る
●サンタ、起こされる
こびと「E」、来訪
▼トナカイの「ダッシャー」、戻る
#('こびと「J」' 'こびと「F」' 'こびと「B」')、サンタと問題を解決
#('こびと「J」' 'こびと「F」' 'こびと「B」')、自分の仕事に戻る
こびと「B」、来訪
▼トナカイたち、サンタを起こす
●サンタ、寝る
#('こびと「H」' 'こびと「E」' 'こびと「B」')、サンタを起こす
こびと「G」、来訪
●サンタ、起こされる
こびと「A」、来訪
▼サンタとトナカイたち、出発　→　戻る
▼トナカイたち、ふたたびバケーションへ
こびと「C」、来訪
●サンタ、寝る
▼トナカイの「ルドルフ」、戻る
こびと「D」、来訪
●サンタ、起こされる
▼トナカイの「ヴィクセン」、戻る
こびと「F」、来訪
#('こびと「H」' 'こびと「E」' 'こびと「B」')、サンタと問題を解決
#('こびと「H」' 'こびと「E」' 'こびと「B」')、自分の仕事に戻る
▼トナカイの「キューピッド」、戻る
こびと「E」、来訪
●サンタ、寝る
#('こびと「G」' 'こびと「A」' 'こびと「C」')、サンタを起こす
▼トナカイの「ドンダー」、戻る
こびと「I」、来訪
●サンタ、起こされる
▼トナカイの「ダンサー」、戻る
こびと「H」、来訪
#('こびと「G」' 'こびと「A」' 'こびと「C」')、サンタと問題を解決
#('こびと「G」' 'こびと「A」' 'こびと「C」')、自分の仕事に戻る
▼トナカイの「ブリッツェン」、戻る
こびと「G」、来訪
●サンタ、寝る
#('こびと「D」' 'こびと「F」' 'こびと「E」')、サンタを起こす
▼トナカイの「プランサー」、戻る
こびと「C」、来訪
●サンタ、起こされる
▼トナカイの「コメット」、戻る
こびと「J」、来訪
#('こびと「D」' 'こびと「F」' 'こびと「E」')、サンタと問題を解決
#('こびと「D」' 'こびと「F」' 'こびと「E」')、自分の仕事に戻る
▼トナカイの「ダッシャー」、戻る
こびと「D」、来訪
●サンタ、寝る
#('こびと「I」' 'こびと「H」' 'こびと「G」')、サンタを起こす
▼トナカイたち、サンタを起こす
こびと「B」、来訪
●サンタ、起こされる
こびと「E」、来訪
▼サンタとトナカイたち、出発　→　戻る
▼トナカイたち、ふたたびバケーションへ
●サンタ、寝る
▼トナカイの「ダンサー」、戻る
こびと「F」、来訪
●サンタ、起こされる
▼トナカイの「キューピッド」、戻る
こびと「A」、来訪
#('こびと「I」' 'こびと「H」' 'こびと「G」')、サンタと問題を解決
#('こびと「I」' 'こびと「H」' 'こびと「G」')、自分の仕事に戻る
▼トナカイの「プランサー」、戻る
こびと「G」、来訪
●サンタ、寝る
#('こびと「C」' 'こびと「J」' 'こびと「D」')、サンタを起こす
▼トナカイの「ルドルフ」、戻る
こびと「H」、来訪
●サンタ、起こされる
▼トナカイの「ドンダー」、戻る
こびと「I」、来訪
#('こびと「C」' 'こびと「J」' 'こびと「D」')、サンタと問題を解決
#('こびと「C」' 'こびと「J」' 'こびと「D」')、自分の仕事に戻る
▼トナカイの「コメット」、戻る
こびと「C」、来訪
●サンタ、寝る
#('こびと「B」' 'こびと「E」' 'こびと「F」')、サンタを起こす
▼トナカイの「ダッシャー」、戻る
こびと「D」、来訪
●サンタ、起こされる
▼トナカイの「ヴィクセン」、戻る
こびと「J」、来訪
#('こびと「B」' 'こびと「E」' 'こびと「F」')、サンタと問題を解決
#('こびと「B」' 'こびと「E」' 'こびと「F」')、自分の仕事に戻る
▼トナカイの「ブリッツェン」、戻る
こびと「B」、来訪
●サンタ、寝る
#('こびと「A」' 'こびと「G」' 'こびと「H」')、サンタを起こす
▼トナカイたち、サンタを起こす
こびと「E」、来訪
●サンタ、起こされる
こびと「F」、来訪
▼サンタとトナカイたち、出発　→　戻る
▼トナカイたち、ふたたびバケーションへ
●サンタ、寝る
●サンタ、起こされる　……


id:sumim:20070608:p1 へ続く。