Exhaustive Lock Dependency Emulator その２ wait_and_lock

その１で、このフレームワークにおいて「入力待ち…は…特殊な枝刈りの仕方」ではないかというアイデアを書いた。本稿では、それを実装してみる。

■

理屈

入力待ちは、最も単純にはループして、他のプロセスが $context を変更するのを待てば良い。しかし、それは普通、非効率的で、このエミュレータだと、探索すべき lock 仕様の木の深さを無限に大きくすることになる。

もう少しマシな方法ということであれば、unlock したあと、次に他のプロセスが lock/unlock するのを待ってから lock する「wait_and_lock」と呼ぶべき機構を考えることができる。この方法を先のフレームワークで実現するには、 lock 仕様を見て、間に他の lock がなければ、それを枝刈りするだけで良い。とても簡易で、枝を伸ばすのではなく枝を刈るのだから効率的ですらある。

■

実装

しかし、話としてはそれだけなのだが、実装にはやや大きな改造を必要とする。つまり、他の lock が間にない仕様だと枝刈りするということは、先の実装だと、そこから伸びた枝であるところも実行されなくなるため、単純な枝刈りだと wait_and_lock は決して実行されないとなってしまう。

Perl では、C などで言うところの try {} catch {} と throw は、eval と die で実装できる。先の実装では、lock 仕様が満たせないとわかると die "NORMAL:..." をし、"NORMAL: " という文字列で大域脱出がはかられたので、それは正常終了の一種で枝刈りを要求していると判断していた。

ここからさらに wait_and_lock を実現するためには、die "WAIT:..." という大域脱出を認め、その場合は、枝刈りをしないことにした。また、unlock された$context を配列に保存しているところでは、$context が未定義になったということで配列の最後に undef を残すようにした。もちろん、wait の条件に合いようのない lock 仕様は、die "NORMAL:..." で枝刈りする。

「やや大きな改造」と書いたが、diff を取ってもらえばわかるように、ソースはほぼ数十行の追加のみである。しかし、確実に複雑さを増しており、今後、 lock 仕様を見て枝刈りするという考え方が、この他にも出てくれば、注意を払うだけで論理を実装できるか定かではない。

■

実行例

二つのプロセスがあって、一方が「出力」をしたあと「入力待ち」に入り、もう一方は「入力待ち」をしたあと「出力」するという例を作る。

$emu->new_process(sub {
                    my ($context) = @_;
                    $context->lock();
                    my $a = $context->get("a");
                    print $a . "\n" if defined $a;
                    $context->set("a", 1);
                    $context->unlock();

                    $context->wait_and_lock();
                    my $a2 = $context->get("a");
                    print $a2 . "\n" if defined $a2;
                    $context->set("a", 3);
                    $context->unlock();
                  },
                  lock_limit => 2,
                 );
$emu->new_process(sub {
                    my ($context) = @_;
                    $context->wait_and_lock();
                    my $a = $context->get("a");
                    print $a . "\n" if defined $a;
                    $context->set("a", 2);
                    $context->unlock();
                  },
                  lock_limit => 1,
                 );

実行結果の最後あたりは次のようになる。

(...続き...)
Result:
run_by_lock_spec:
run_by_lock_spec: P0U0->P1L0
1
run_by_lock_spec: P0U0->P1L0,P1U0->P0L1
2
1
run_by_lock_spec: P1U0->P0L0
cut!
run_by_lock_spec: P0U1->P1L0
cut!
run_by_lock_spec: P1U0->P0L1
cut!


Result Tree:

  [ [c000,undef], [undef] ]
P0U0->P1L0
  [ [c000,undef], [c001] ]
P0U0->P1L0,P1U0->P0L1
  [ [c000,c002], [c001] ]

その１にはなかったが、最後に lock 仕様に対する $context の配列の要旨も表示し、wait で終了したものを undef で終る列で表示してわかるようにしてある。

結局、この例だと π0υ0→π1λ0,π1υ0→π0λ1 という lock 仕様のときのみ、正常に終了する。それ以外で Result Tree に表示されているのは、それの前段階で wait 中のプロセスが残るもののみである。

私は他の例も試してみたが、「デッドロック」と判断すべき場合は、ある lock 仕様が wait(undef で終了) を含んでいるが、その lock 仕様の子の仕様において正常終了したものがない場合とでもすれば良いのだろう。もちろん、通常のプログラムにおいて複数のプログラムが入力待ちで終了するのは普通のことであったとしても、このフレームワークだけでは、それと「デッドロック」を区別するのは難しいように思う。

■

今後の課題

その１で挙げた以外で考えたことは、エラーがらみでない確率的なこと。

二つのプロセスがあって、一方では lock 後ある変数に 1 を足し他方では 1 を引くとする。例えば、それをそれぞれ２度繰り返したあと一方が答えを表示する。当然、-2 から 2 までの幅で場合の数というのも考えられようが、「現実」は、lock が一度もブロックされないことが圧倒的に多いとなるだろう。「現実」にはまともな「確率」が存在しない。

しかし、ここにそれぞれ wait_and_lock を挟むとどうなるか。とたんに中間的な値が「現実」味を帯びてくる。wait_and_lock は枝刈りを行うが、その場合の数以上にとても大きな「現実」も枝刈りしたとできるのかもしれない。

以前、乱数の値の重なりついて少し考えたとき、重なりを順序を決める乱数をもう一つ使って解決するのは不自然だと思ったが、同じことが続く chaotic な乱数か特殊な順序決めアルゴリズムなら許せると思った。その感覚が、上の考察につながるような気がする。

ここを理論的に詰めるのは難しいかもしれないが、今後、別のシミュレーションや、多変数乱数計算アルゴリズムに結実させたい。

■	関連 ● 《Exhaustive Lock Dependency Emulator》。その１。 ● 《クリティカルセクション - Wikipedia》。基本用語として。8 bit 機のころの割り込みでもこういう言葉を使ったと思う。あとこのあたりの基本としては、並行プログラミングと並列プログラミングの違いとかがよく話に上った。当然論文はあまたあるはずだが、専門でやってたわけでないので、私の「車輪の再発明」をどう転がしていくといいのかの検討がつかない。
■	配布物 ● exhaustive_lock_dependency_emulator_wl.pl。バージョン 0.01。

更新：	2011-07-01
初公開：	2011年07月01日 22:37:24
最新版：	2011年07月02日 15:22:22