ラベル 謎 の投稿を表示しています。 すべての投稿を表示
ラベル 謎 の投稿を表示しています。 すべての投稿を表示

2010/07/18

Wot, no chickens?

Javaにはリアルタイム性が無いと言うと、ガベージコレクタの話題かと思うが、それだけではない。以下の二つも問題である。

  1. Javaには待ち行列が二つある。Synchronizedによる待ち行列とwait/notifyによる待ち行列である。この二つの待ち行列のせいでライブロックが発生する。これはJava仕様の問題だろう。
  2. それからもう一つ、待ち行列がFIFOではなくLIFOになっていることである。どこまでがJava仕様でどこからがVM実装依存なのか分からないが、現在ダウンロードできるJavaの実行環境はLIFOになっている。LIFOだと後から来たスレッドが先に処理されるので、オーバーロード時には最初に来たスレッドは永遠に待たされる。優先度付き待ち行列のポリシーはVM実装時に変更できないとどこかで読んだ気がするが、この記憶が正しければJava仕様の問題だろう。

これだけJavaが使われていて誰も問題にしないのは謎である。しかし、Androidがカーナビなどでも利用されるようになってくると問題になるのだろうと思う。

この問題を最初に指摘したのはKent大学のPete Welchで「wot, no chickens?」で検索すると今でも関連するページを見ることができる。サンプルコードも掲載されているので実験することができる。インタフェース誌にも小山尾 登氏の解説記事[1][2]が掲載されている。小山尾氏の実験によって現状のJavaVMの待ち行列がLIFOであることが分かった。IBMのサイト[3]でも説明されている。
Javaの問題点を指摘するためにBristol大学のAlan ChalmersがIEEE宛に1997年にレターを以下のメンバーと連名で送ったが無視されたらしい。レターの本文はしばらくWeb上にあったが今はアクセスできなくなっている。

Alastair Allen (University of Aberdeen, UK)
Andre Bakkers (University of Twente, Netherlands)
Richard Beton (Roke Manor Research Limited, UK)
Alan Burke (Aurigor Telecom Systems, Canada)
Alan Chalmers (University of Bristol, UK)
Barry Cook (University of Keele, UK)
Michael Goldsmith (Formal Systems (Europe) Ltd, UK)
Gerald Hilderink (University of Twente, Netherlands)
Ruth Ivimey-Cook (Advanced RISC Machines Ltd, UK)
Adrian Lawrence (University of Oxford, UK)
Jeremy Martin (University of Oxford, UK)
Nan Schaller (Rochester Institute of Technology, USA)
Dyke Stiles (Utah State University, USA)
Oyvind Teig (Autronica, Norway)
Paul Walker (4 Links, UK)
Peter Welch (University of Kent, UK)

それで、この問題を放置するわけにも行かないのでWelch達はCSPを使ってJavaの通信用ライブラリJCSP[4]を作成して公開している。使い方は、中原氏のホームページ[5]に解説がある。今後、組込でJavaを使うのであればJCSPを使った方が良いのではないかと思う。


[1] 並列プロセッサXMOSの検証環境PAT2
[2] UPPAALによる時間仕様検証
[3] JavaプログラマーのためのCSP 第1回
[4] Communicating Sequential Processes for JavaTM (JCSP)
[5] CSPモデルプログラミング

2010/02/20

原因結果グラフ-2 MASK

結果グラフで A masks B とした場合の扱いは

1) A⇒¬B
2) Aが真ならBは未定義(三値論理の利用)
3) Aの真偽による場合分け

の三通りが考えられる。

1)の場合REQ制約の否定として表現できる。CEGTestの場合は、問い合わせ中だが、REQの否定を柔軟に利用できればMASKは要らなくなってしまう。 赤い四角で囲った部分を表現することが出来るので1)の意味でのMASKは特に必要ない。
青丸で囲んだところはちょっと怪しい。と言うか括弧で括るような、否定を取る優先順位を決めなければならない。そう言うことを考えなくても良いようにREQとMASKが定義してあると言うのは合理的かも知れない。ただし、最近FXの秋山氏の指摘で新たな謎が生まれた。MASKは結果側に付ける[1]と言うものである。もしそうなら原因結果グラフは結構簡単で使いやすいものになる気がする。この謎の裏にどんな合理性があるのか調べてみたい。


2)調べてみると三値論理には何種類もある[2]。マスクされた側をどう解釈するか(a.真か偽か決まらない状態、b.真でも偽でもない第三の状態、c.無意味)によって使用する論理系が変わる。VDMはaによって未定義を扱える。ただし、実装上の都合で一部変更して利用している[3]。用途によって結構自由に使って良い見たいな感じである。原因結果グラフを命題論理の範囲で扱うことを考えているので、各ノードは命題でなければならず、単に真偽が決まっていない状態とするのが話が難しくならなくて良いと思う。VDMの様な手直しをするかどうかはまた別の問題として考えれば良いだろう。三値論理を使うと、結果側に不定が現れる。結果側に現れる不定が妥当かどうか、ちゃんと解釈できるかどうかで使用する論理系を決めれば良いと思う。それで、幾つかやってみたが三値論理を使わなかった場合すなわち、1)の方法で真にも偽にもなり得るという結果に落ち着く。aの場合の真理表は以下のようになる。*が真偽が決まらない状態。赤いところをVDMでは*として扱う。


A B A∧B A∨B A⇒B ¬A
T T T T T F
T F F T F
T * * T *
F T F T T T
F F F F T
F * F * T
* T * T T *
* F F * *
* * * * *


3)“A masks B”をAが真の時はBを考慮しなくて良いというそのままの意味に解釈して。Aが真の時はBを含まない原因結果グラフを作ってしまう。これは、原因結果グラフ全体を表す論理式の真偽がどのような意味を持つのかに関わる問題と関係する。


参考文献
[1] http://en.wikipedia.org/wiki/Cause-effect_graph
[2]http://ja.wikipedia.org/wiki/3値論理