Exhaustive Lock Dependency Emulator その３ 修正とチェック

略して ELDE。マルチプロセスの最も簡単な lock/unlock 機構において、そのロックの依存を総当たり的に調べるプログラムを書いた。その１で「虚実行」も数え上げていたのを修正し、「実実行」のみを対象とするようにした。

前回は、意図しない「虚実行」を含めていたため、他の人がやらないような実装になり、その意味では個性があったかもしれないが、今回こそ、特に工夫のない「車輪の再発明」になっていると思う。ただ、前回の怪我の功名で、違う考え方で作った二つの実装が同じ結果を出すのを確かめることで、エミュレータの正しさを多少ともチェックしているのは優位点かもしれない。「証明」がないのは相変わらずではあるが、いくつかの例で、チェックはできた。

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

今回のアイデアのキモは、グローバルな単一ロックのみを扱うため、ロックは重ならず、プロセスをまたいでそれぞれのロックをシーケンシャルに整列して捉えることができるという点にある。その列をロック仕様として総当りで数え上げ、それに基づくよう実行していく。処理の重なりのうち、簡単なものは省いて効率化する。

なお、「プログラム」をコンテクストに関し「関数的(functional)」でなければならない…という条件を課すのは今回も同様である。すなわち、コンテクストが同じように(同じ lock/unlock 順序で)与えられれば、常に同じ「出力」をしなければならない。

続きを読む "Exhaustive Lock Dependency Emulator その３ 修正とチェック"

組み合わせと順列の数え上げのアルゴリズム

Perl で組み合わせの数え上げが欲しかったのだが、CPAN からのインストールには C が必要なようなので、できれば避けたい。これぐらいなら、Perl 自体で書けるだろうと、参考となるサイトを探すと…意外にない。

そして見つけたいくつかの日本語のサイトでは、nCr = nCr=(n-1)Cr + (n-1)C(r-1) の式を使って示していた。いや、もっと効率の良い方法があったはず…と海外のサイトを調べると、最近、私が勉強している Python でアルゴリズムを示しているサイトがあったので、それを Perl に書き換えてみた。

なお、「数え上げ」という言葉を使ったが、数を求めるのと区別するために、組み合わせや順列の「生成」と言ったり「列挙」と言ったりもするようだ。

続きを読む "組み合わせと順列の数え上げのアルゴリズム"