新城＠筑波大学情報です。こんにちは。

In article <bhrr6s$bgv@utogw.gssm.otsuka.tsukuba.ac.jp>
        kuno@gssm.otsuka.tsukuba.ac.jp writes:
> > 同じ CFD にして同時に投票にかけられるは、私には読めませんでし
> > た。
>   まあその書き方は直すとして、そのようなもの(同じCFDで同時に投票
> に掛けられる)であれば、新城さんとしては受け入れ可能かどうか、そ
> こを伺わせてください。

ネットワーク・ニュースの議論なので、新城個人に聞かれても困り
ます。他の人の意見も聞いて下さい。

私の意見は、そういうスケジューリングが「可能」で、かつ、別の
スケジューリングも可能であるような柔軟性があるものならＯＫです。
「必ず同時」は、不可です。

> > 議案群とCFDの関係で、CFXで CFD期間が終ってしまうので。
>   これも、同時に投票して同時に決着させる結果終る、というのは受け
> 入れられないですか?

これも、必ず同時は、不可です。同時も可能、別の順番でも可能と
いう柔軟性があるものならＯＫです。

>   飯嶋さんもかかれていますがMakefileが例になるようなものはちょっ
> となあと思います。またundoという概念が必要なのも。

undo ではなくて、「仮成立」でもいいです。v4 は、そうでした。
成功するか失敗するかわからないけれど、とにかく先に進めてそれ
なりの結論を出してみるというのが、楽観的／投機的なスケジュー
リングです。

> P.S. 1つのCFDに含まれる複数の議案の間で依存と対立の関係に矛盾が
>      生じることはありますよね。AとBが依存、AとCが対立、BとCが依
>      存とか(複数の提案者が勝手に出すと当然起こり得ます)。その場
>      合はどうするのでしょう?

はい。矛盾がおきないような結果を１つ選ぶために、どれかの議案
を不成立にします。v4 なら、投票にかけて、投票の yes 得票の多
いものを優先させて成立させます。そして、それに矛盾するものは、
不成立にして矛盾を防ぎます。

たとえば、A が yes 100 票 no 90 票、B が yes 50 票 no 40票、
C が yes 10 票、no 9 票だとします。全部の案が yes > no になっ
ています。この中では、A の得票が多いので、まず ず A を成立さ
せます。C は、A と対立していたので、不成立にします。B ですが、
B が C に依存していたら、これも不成立にします。逆に C が B 
に依存していたら、B は成立させます。

簡単ですよね。

トランザクション処理なら、最終的に「逐次化可能(serializable)」
という厳しい制約のもので、複数の処理を並行して実施します。逐
次化可能は厳しすぎるので、ngMP ではそれは要求しなくてもいい
でしょう。

Makefile の例は、別に分かりやすい人もいるだろうということで
出したのであって、今の案は別に Makefile に依存しているわけで
もなんでもありません。Makefile が分からない人は、別の層の概
念で理解してもらえばいいので、大丈夫です。

make の例をもう少しすると、もともと make には、逐次的にやる
という意味はすくなくて、複数の処理を並列にやってもいい所もあ
ります。これを本当に並列にやるものが並列make。Sequent
Balance に入っていたのが最初だと思いますが、今は、GNU にもそ
の機能はあります。-j オプションのあるものです。

並列 make の次に出てきたものが、楽観的makeと投機的make。make 
と言われる前に、別の世界で先に処理を進めて、make と言われた
ときには、即座にその結果を出すというものです。先に進めた処理
は、ユーザがファイルを修正したりした無駄になります。だけど成
功した時には速いし、そもそもＣＰＵが遊んでいたら無駄にはなり
ません。

投機的makeについては、次の論文を見てください。

根路銘, 當城, 新城, 溝淵, 喜屋武, 翁長: "世界のDAG を利用し
た投機的make の実現", 情報処理学会研究会報告95-OS-70-4,
Vol.95, No.70, pp.25-32 (1995年8月).

http://www.ipsj.or.jp/members/SIGNotes/Jpn/07/1995/070/article004.html

＼＼　新城　靖　（しんじょう　やすし）　＼＼
＼＼　筑波大学　電子・情報　　　　　　　＼＼