Exhaustive Lock Dependency Emulator その１ 並列処理の総当り

※最後に追記するようにこの記事には大きなミスが見つかった。以下は参考のために残しておく議論である。※

マルチスレッドまたはマルチプロセスの最も簡易な lock/unlock 機構において、その依存を総当たり的に調べるプログラムを(Perlで)書いた。

総当たり的なので、特に工夫があるといえるわけではなく、おそらく他の方が特に言及することなく為していることについて、たまたま私もプログラムする順番が回ってきたぐらいのことになると思う。「車輪の再発明」だが、調べるよりは自分で作ったほうが早い部類の話で、記号論理をやった人間にとって示唆に富む部分があるという印象を受けたので、ブログに書いておくことにした…といったところ。

これはマルチプロセス環境を Perl 上でエミュレートするという話ではまったくない。プログラム自体は、シングルプロセスで終了する形をとる。

アイデアのキモは、シングルプロセス環境ではあるがプロセスを順に何度も起動し、unlock があったときに環境をすべて保存し、lock があったときに以前 unlock された環境に切り換わると考えることにより、lock/unlock のシミュレーションができたと考える点にある。

■

理屈と例

例えば、次の二つの「プログラム」を考える。二つのプログラムがそれぞれ別の「プロセス」で動くとする。まず、$context->set や$context->get が $context->lock と $context->unlock の間になければエラーを出すとすれば、排他制御としてはもっとも簡易な形が実現できているとできるだろう。

sub prog1 {
   my ($context) = @_;

   $context->lock();
   $context->set("a", 1);
   $context->unlock();

   $context->lock();
   $context->set("a", 2);
   $context->unlock();
}

sub prog2 {
  my  ($context) = @_;

  $context->lock();
  my $a = $context->get("a");
  print "$a\n" if defined $a;
  print "undef\n" if ! defined $a;
  $context->unlock();
}

当然、$prog1 と $prog2 がどちらが先に実行されるかは不明だし、$prog1 の unlock のあとに $prog2 の lock があれば 1 か 2 が表示されるだろうが、1 と 2 のどちらになるかは不明である。$prog1 の unlock がなく $prog2 が終了していれば、undef が表示されるだろう。

これを「すべての場合」について総当たり的に見てみたい。

ところで、ここでいう「すべての場合」とは何か？

$context のデータが置き換わるのは、lock と unlock に挟まれた部分だけであり、その間では他のプロセスはデータを変えない。逆にいうと他のプロセスがデータを変える可能性があるのは、unlock と lockの間で、その間は自分は get もできないのだから、つきつめれば、lock のときにのみ他のプロセスがデータを変えたかどうか調べればよいとなる。そしてデータが変わるのは他のプロセスが unlock をしたときだけである。

また、「排他制御」という定義である以上、同時に lock は起きないので、あるプロセスの unlock が影響を与える lock は一つと考えてよく、ただ、その lock が unlock されるときは当然、次のプロセスに影響を与えることがあるとすればいい。

ここで、あるプロセス p において n 番目の unlock があったとき、その環境 ($context)が別のプロセス q における m 番目の lock の環境になることをπpυn→πqλm と書くとしよう(Perl での実装ではP${p}U${n}->P${q}L${m} のように書いている)。

実行の一つの「場合」とはすなわち、πpυn→πqλm の列で表すことができる。 (特殊な場合として、空列は、まったく環境の置換が起きない場合と考える。) 今後、一つの「場合」、π(p_0)υ(n_0)→π(q_0)λ(m_0),...,π(p_k)υ(n_k)→π(q_k)λ(m_k) を lock 仕様(lock specification)と呼ぼう。

一つのプロセス内での lock の順序は守られるので、任意の j < k について、

p_k = p_j ならば n_k > n_j、 かつ p_k = q_j ならば n_k >= m_j、 かつ q_k = q_j ならば m_k > m_j、 かつ q_k = p_j ならば m_k > n_j。

大ざっぱに言えば、前の部分で p_k がすでに現れていれば、その n, m よりも n_k は大きい数字でなければならないし、q_k, m_k についても同様のことがいえるということ。

上の例で lock 仕様と実行結果をすべて書き出すと、次のようになる。

空列 undef が表示。 π0υ0→π1λ0 1 が表示。 π0υ0→π1λ0,π1υ0→π0λ1 1 が表示。 π0υ1→π1λ0 2 が表示。 π1υ0→π0λ0 undef が表示。 π1υ0→π0λ1 undef が表示。

なお、「プログラム」は $context に関し「関数的(functional)」であることが条件になる。すなわち、$context が同じように(同じ lock/unlock 順序で) 与えられれば、常に同じ「出力」をしなければならない。

■

実装

実装には私が使い慣れた Perl を用いている。エミュレータを書く最初なので、拡張性は念頭に置きつつも、できるだけシンプルに書くことをこころがけた。

アルゴリズム的には、まずありえる lock 仕様をすべて書き出してしまい。枝刈りしながらも、lock 仕様を一つずつ実行するという形をとっている。

当然、プログラムにはループがありうる。しかし、今回の方法だと「すべての場合」を書き出すと、無限に続くかもしれないループは、無限のメモリ空間を要することになるので、lock 数の上限を先に lock_limit として与えることにしている。

プログラムの「メイン」部分はだいたい次のようになっている。

MAIN:
{
    my $emu = Main::_Emulator->new();
    $emu->new_process(sub {
                        my ($context) = @_;
                        $context->lock();
                        $context->set("a", 1);
                        $context->unlock();

                        $context->lock();
                        $context->set("a", 2);
                        $context->unlock();
                      },
                      lock_limit => 3,
                     );
    $emu->new_process(sub {
                        my ($context) = @_;
                        $context->lock();
                        my $a = $context->get("a");
                        print $a . "\n" if defined $a;
                        print "undef\n" if ! defined $a;
                        $context->unlock();
                      },
                      lock_limit => 2,
                     );
    print "\n\nPlan:\n";
    $emu->dump_tree();
    print "\n\nResult:\n";
    $emu->run();
    print "\n\nResult Tree:\n";
    $emu->dump_tree();
}

$emu->new_process で、上の例の $prog1 と $prog2 を登録している。 lock_limit は、それがどう機能するかを見るために、一つずつ多めにとってある。

最初の $emu->dump_tree() はとりあえず書き出した lock 仕様をすべて表示する。$emu->run() が lock 仕様にもとづいてすべての場合について実行を行っている。最後の $emu->dump_tree() は、枝刈りされ、意味のあるとわかった lock 仕様だけをすべて表示することになる。

今回は「デバッグ」中の起動ということにして、run の途中で print するようにしている。Perl の特徴により、実行順序がばらばらでみにくいかもしれない。"cut!" と表示されるところは、実行はしてみたが、lock 仕様を満たしようがないと判断された部分を示している。

実行すると、最後のほうが次のような表示になった。

(...続き...)
run_by_lock_spec: P0U2->P1L1
cut!
run_by_lock_spec: P1U0->P0L1
undef
run_by_lock_spec: P1U0->P0L1,P0U2->P1L1
cut!
run_by_lock_spec: P1U0->P0L1,P0U1->P1L1
undef
cut!
run_by_lock_spec: P1U0->P0L1,P1U1->P0L2
cut!
run_by_lock_spec: P1U1->P0L2
cut!


Result Tree:

P0U0->P1L0
P0U0->P1L0,P1U0->P0L1
P0U1->P1L0
P1U0->P0L0
P1U0->P0L1

上にある部分では "cut!" されなかったのが "P1U0->P0L1" だけということで、もう少し枝刈りを改良する余地がありそうだ。Result Tree に関しては、上の例のところで挙げたものと一致している。

■

今後の課題

「πpυn→πqλm」という表記は、process の p をギリシャ文字の π に unlock の u を υ に lock の l を λ に変えて、カッコつけてるというのもあるが、計算論の pi-calculus (π計算)や lambda-calculus (λ計算)を少し意識している。

もちろん、それらとはまったく別物で、pi-calculus ではどれがどれを待つというのが重要になってるのに、私のエミュレーションでは、プロセスにとって大事な入力待ちの状態さえまったく出て来ない。

しかし、それは言ってみれば lock をかけようとしてからずっと待ってる状態に入力待ちを対応させることもできるのではないかという感触があり、それは特殊な枝刈りの仕方で、そこではまるでラムダ抽象のように lock が機能する…といったように議論を持っていっていくことができるのではないかとか夢想している。

今後いつか、そういった部分を理論的に詰めてみたい。

上の実装では lock_limit を最初に指定して lock 仕様の場合の数の最大値を制限したが、プログラムした感触では、順次、lock 仕様の木を伸ばしていくということも不可能ではなさそうだ。枝刈りをもっと効率的にし、メモリ使用量を少なくする工夫をさらに取り入れながら、lock_limit がいらない実装もしてみたい。

この「エミュレータ」を作る直接のキッカケは、CGI プログラムで(私にとって)複雑な排他制御を行おうとしたとき、本当にそれで意図通り動くかチェックしたいが、どうしたらそういうチェックができるのだろう？…と考えたことにある。

もちろん、そういった「実用的」なプログラムに関してエミュレートできるようになるまでは時間がかかるだろうから、そこを目標とはしないが、それに向けた拡張は行っていきたい。

さしあたり、lock と unlock の間でデータベースにアクセスする(記事の書き換えをする)と宣言したあと、unlock 後にそこにアクセスしても排他的なアクセスにすることはできる…といった機構を導入したい。ここでチェックすべきは、本当にアクセスが排他的になっているかということで、プロセスに与えられた「accessor」が同じ場合か違う場合というのを総当たりで挙動を確かめれば十分という話になろう。

このような理論的実装において、実用的なプログラムでは必ず現れる "sleep" には意味がなくなる。なぜなら、厳密な検証の文脈では、実行のオーバーヘッドはどこにでも起きうると考えるべきだからである。

では、sleep とは何をやっていることになるのだろう？それは、おそらく、エラーに関係する。今回の理屈を延ばしたところにおいて、エラーとはすなわち確率的な事象とせざるを得ない。そして、それに確率的に干渉するのが sleep ということになるのではないか。

サーバー等の実装では、ユーザーが連続して入力するときに、処理をブロックしにくいよう待つために、sleep を使うということであるが、これは、ブロックという「エラー」の確率を減らす操作と考えることができよう。

こういった確率的事象とのからみまで、将来考えられたらうれしい。

■

参考

関連研究等はまだまったく調べていない。上の「今後の課題」をある程度やって、再びブログ記事にするときなどに折を見ながら、落ち着いて調べるといった手順になるかと思う。今は Wikipedia と自分の記事のみ挙げておく。

● 《π-calculus - Wikipedia, the free encyclopedia》。プロセスの代数。本稿とはまったく別(?)のアプローチ。ラムダ計算については適当にググるなりしてください。 ● 《Statuses_Editor_Proxy.CGI》。今回の直接のキッカケとなった CGI。現在、鋭意製作中。 ● 《Perl でオブジェクト指向 C++風》。Perl 実装のオブジェクト指向の使い方は私の独特な書き方。 ● 《セキュアジャパン 2006 の Winny 対策としての VM は釣り？》。この記事に「デバッガの代わりに理論的な極限状況を再現できるものとしてのエミュレータって感じかな。他の方からすれば、エミュレータというよりもインタプリタ + 定理証明システムってことになるのかもしれませんが。」と書いている。そういった関心が本稿の背景にある。 ● 《外作用的簡易経済シミュレーションのアイデアと Perl による実装》。本稿とはまったく関係がないが、今のところシミュレーションの私の関連記事は、ほぼこれだけとなるので載せておく。

■	配布物 ● exhaustive_lock_dependency_emulator_0.pl。バージョン 0.02。
■	「虚実行」またはこの仕組みの大きなミスについて (追記: 2018-04-06)

書いて省みず数年してから、ブラッシュアップしようと見返したときに、この仕組みは失敗していることがわかった。それを説明しよう。

π0υ1→π1λ2 かつ π1υ4→π0λ3 とする。すると、間に π0λ2 とπ1λ3 があるわけで、こららは必ずどちらかが前でどちらかが後になる。π0υ2→π1λ3 か π1υ3→π0λ2 でなければならない。これが仕様に含まれてない実行はニセモノ…「虚実行」というべきものになる。

もっと簡単に、プロセス群の中の一番最初のロック以外のプロセス q の最初のロックは πpυn→πqλ0 なる仕様(p n は任意)を含んでいないと「虚実行」になるし、プロセス群の最後のロックを含むプロセス以外のプロセス q の最後のロック l は πqυl→πpλn なる仕様(p n は任意)を含んでいないと「虚実行」になる。

「虚実行」群の中に「実実行」というべきものがすべて入っているので、「虚実行」群全体でテストに合格したものは「実実行」においてもテストに合格すると言えるが、余計なものまで(大量に)チェックしていることは否めない。

「虚実行」か「実実行」かを判定するプログラムを書こうかと思ったが難しい。ロック仕様から完全に別物にしたほうが早いだろう。今後の課題としたい。

「虚実行」を含めたテスト…という考え方がもしかすると有用かもしれないので、このエントリはこのまま残すことにしたが、注意されたい。

更新：	2011-06-19,2018-04-06
初公開：	2011年06月20日 02:54:27
最新版：	2018年04月06日 01:33:47