=========================================================================== セッションD2：研究報告 【会場の広さ】 : 80席 【参加者の数】 : 32人 =========================================================================== ====================================================================== 組込みシステム用ネットワークインタフェースに関する研究 阿部 司（苫小牧工業専門学校情報工学科） ====================================================================== 発表内容： 最近インターネットが非常に普及してきたので組込みシステムでネットに接続 する機会が多い。実際に製品ということで出荷されているメーカーさんもおら れる。プロトコルスタックが必要だが現状の汎用機のプロトコルはあるが汎用 過ぎて組込みには使いづらい。もうひとつは、組込みシステムと限定した場合、 地球規模の大きな伝送遅延を考える必要はあまりないと考えた。 ○組込みシステムの制約 　メモリ容量 　重量 　サイズ 　消費電力 等の厳しいリソース制約がある ○環境 組込みシステムといっても規模の範囲があるのである程度限定した 　ROM 128Kバイト 　RAM 32Kバイト 　レジスタ 32ビット 　1チップCPU ＋ 外部メモリ 実装ターゲットプロセッサはH8/3048F 現状のプロトコルスタックは多機能であり、メモリも大量に使用する。「どの 程度機能を削減しても通信ができるか」という所までやってみた。応用として、 HTTPが通らないと現在のインターネットでは使い物にならないと思っている。 TCP/IPについては、かなりオプションを外したり、分割機能も無しということ で簡略化している。ネットワークインターフェース関係としては単一リンク、 つまり終端というものを対象にしている。 HTTPはインターネットのトラフィックを多く占めるが、ファイアウォールやproxy も通過しやすいということで標準の応用層に使えるのではないかと考えている。 ノードは中継はせず、入ってくるのは一箇所から、出てくのも一箇所からと簡 略化して今回の実装を行った。 実装に用いたリアルタイムOSは豊橋技術科学大学のTOPPERSプロジェクトで開発 されたJSPカーネルを使用している。(μITRON4.0スタンダードプロファイル1.0) TCP/IPプロトコルスタック及びPPPは、FreeBSDバージョン3.4をベースに実装を 行った。これは、mbufと呼ばれる固定的なメモリブロックによるリスト構造で 実装されている。しかし、動的なメモリ操作がこのプロトコルスタック内で行 われる可能性があるので、それをできるだけ防ぐためにネットワークバッファ というものを考えた。まず全部割り当ててしまう。TCP/IP、ネットワーク関係 も全部含めて確保してしまって、後は動的な割り当てはしないということにし ている。これでオーバーヘッドは0.4％となる。 ○インターフェースの単純化 単一リンクなので一本しか出力がない訳で、１つだけ多重にしていればよい。 ネットワークの情報の取得もマクロにより単純化している。TCP/IPの処理は 32bitで行うと効率がよい。 ○PPPの実装 接続方式として 　シリアルインタフェースによる直接接続 　電話回線とモデムによるダイアルアップ接続 ○PPPのオプション ・MRU ・ACCM ・MAGIC ・PCOMP ・ACCOMP ・RAP ○PPP主制御部(点線の部分) ┏━━━━━━━━┓ ┌───┐ ┌───┐ ┃NETタイマタスク ┃ │IP入力│ │IP出力│ ┗━━┯━━━━━┛ └───┘ └─┬─┘ │ ↑ ┌--------↓----------┐ │ │ │ ┌─────┐ │ │ │ │ │ PPP出力　│ │ │ │ │ └──┬──┘ │ │ │ │ ↓ │ ┌------│---------------------------│-----┘ ┌───┐ │ │ │ │ │ DTQ　│ │ │ │ │ └─┬─┘ │ │ ↓ │ ↓ │ │┌─────┐ 　┌───┐ ┏━━┷━━━━━━━━━━┓ │ ││PPPタイマ ├→ │ DTQ　├→┃ PPP制御タスク ┃ │ │└─────┘　 └───┘ ┗━━━━━━━━━━┯━━┛ │ │ ↑ │ │ │ ┌─┴─┐ │ │ │ │ DTQ　│ │ │ │ └───┘ │ │ │ ↑ │ │ │ ┏━━━┷━━━┓ │ │ │ ┃PPP入力タスク ┃ │ │ │ ┗━━━━━━━┛ │ │ └----------------------------------↑---------------↓-----------┘ ┌─┴──┐ 　┌────┐ │HDLC入力│ │HDLC出力│ └────┘　 └─┬──┘ ↑ ↓ ┌─┴─────────┐ │シリアルインタフェース│ └───────────┘ 制御タスク，入力タスク,タイマタスクがある。PPPタイマはNETタイマタスク から500ms毎に起動される。IPからはPPP出力という関数を通って下へ行く。 ○実際にPPPを使用してWWWを実装して簡単な評価を行った。 ネットワークインタフェースはPPP、HTTPはバージョン1.0で、これは要求応答 ごとに接続と切断を行う。実際に表示できるのは2ページで、TOPページとネッ トワークの統計情報を表示する。サーバを構成するタスクはPPP関係が2つ、ネ ットワーク、ログタスク(JSP標準)、WWW、UDPのECHOサーバ、manマシンインタ フェースとしてコンソールタスク。接続した例がトップページにリンクした例。 リンクをたどるとネットワーク情報があり、何オクッテト送受信したかが書い てある。(TCP関係、PPP関係、エラー情報等) ○コンソールでデバッグをやりつつTCPの状態遷移を記録した 　タスク開始 　モデムに着信 　PPP/IPCP起動 　接続 　応答 　データの転送が２回 　データ転送の様子 　切断 　　切断は60秒idleさせてモデムを切断してダウンさせるという機構を組み込 　　んである。 ○評価(メモリがどの程度必要か) 先程必要量としてROMが128K、RAMが32Kと述べたが、十分中に収まっている。 これはWWWサーバ、プロトコルスタック、PPP関係をのみを含めており、これだ けで構成できる。ページの増加がWWWサーバタスク、コンフィギュレーションに 関係している。全体としては5Kbyte程増えているが、規模の制約内である。 ○まとめ 組込みシステムで最低限どれだけの機能があれば通信できるかを検討し、プロ トコルスタックを実装した(APIはITRONのTCP/IPを使用した)。ネットワークイ ンタフェースとしてPPPを実装し、直接又はダイアルアップで通信が可能である ことを確認した。これによりWWWサーバとUDPサーバを実装した。必要性を考慮 した上で、制約条件をクリアした。 ○今後の課題 ・PPPの機能の追加 　パスワードによる認証しかないので、もう少し高級なパスワード認証方式、 　VJ　圧縮機能の導入。しかしVJ圧縮機能についてはメモリが3.6K(PPPの約16 　%)必要であるので、検討が必要である。 ・今回は単一のノードだが、複数ノードと中間ノードを経由せずに直接通信が 　行えるようにする。 ・IPv6への対応 ・これらによるメモリの増加への検討 ○質疑応答 ・net_bufを作っていて，可変長の場合はどうするのですか？ 　>オプションがまったくない場合は固定長をわりあてます。TCPのMSSに関し 　てはバッファ長を制御する用に使えるので、それについてはサポートしてい 　ます。 ・今の実装でFreeBSD3.4と比較してどの程度軽くなったのですか？ 　>ソケットインタフェースと比較して約1/3程度になったはずです。 ・ソフトフェアの環境を教えて下さい。コンパイラ、言語などは？ 　>リアルタイムOSにはJSPカーネル。開発環境はWindows2000上のcygwinでgcc 　コンパイラを用いて開発しています。 ・フルアセンブラですか？ 　>プロトコルスタック，PPPについては全部Cで書いてあります。 ・コンパイラの依存性については？ 　>そちらについては検討していないが、最適化については最大限しています。 ・ほかのプロセッサに移行したときに比較的簡単にいけそうですか？ 　>物理インタフェースについてはシリアルインタフェースですので，JPSにシ 　リアルインタフェースのためのモジュールがあるので、どんなCPUにも可能です。 ・そのソースをARMやV86に移したときに、移した人が苦労しないで済むんですか？ 　>エンディアンの違いの問題はあります。今後の研究で他のCUPへの実装も考えて 　おります。 ・機能を削減したから1/3になったんですよね。FreeBSDのAPIをμITRONのAPIに 　変えられたんですよね？それはどれくらいの変更量になりましたか？ 　>かなり変更しました。ソケットインタフェース自体が大きかったですね。実 　際のコアの、TCP/IPのところは1/3まではいかず、半分いくかいかないかとい 　うところです。 ・組込みシステムの制約ということで、例えば消費電力やコストはどうなってい 　るのですか？ 　>実は一般的な話でこの様な制約があるかなというふうに考えまして、実際は 　消費電力やコスト自体はそれほど考えずにやっています。 ・μITRONのソケットは実はあまり普及してないというのがありまして、これ 　をいきなりみせられても戸惑うのですが、UNIXのソケットを元にしてインタ 　フェースを変えられたということで、TCP/IP上でプログラムを作られたとい 　うことで、その上での使い方はどのようなものでしたか？ 　>ソケットインタフェースを使ったプログラムをしたことがあるが，流れ自 　体は変わらないかなと、 ・逆にそれを公表していただいたりは？ 　>品質等ありますので、これから考えます。 ====================================================================== 計量器組込みソフトウェアの仕様記述および検証事例 新田直也（奈良先端科学大学院大学）○，高橋孝一（産業技術総合研究所） （○：発表者） ====================================================================== ○背景 はかり等の軽量機はその機能をソフトウェアに置き換えることによって、近年 高機能化を果たしている。その反面、機能の大部分をソフトウェアに依存する ことで、信頼性の確保が困難になってきている。今回の事例で対象にしたのは 非自動はかりと呼ばれるタイプの軽量機で、これは計量結果を得るために、計 量過程で操作者の介在を必要とするはかりです。産業技術総合研究所では、こ の非自動はかりが法律で示した基準を満たしているかといったことを実際に検 証することを行っている。この非自動はかりは操作者とのインタラクションと してタッチパネルの入力や、ディスプレイの表示、計量した結果をレシートと してプリンタに出力するといった機能を持っている。一般にソフトウェアの規 模が大きくなると、従来テストと呼ばれる手法がとられる。テストは、人間が 実際に器械を動かして仕様に合っているかを確認しながら進められる。 しかし、人間が操作するという都合上、全ての動作の可能性を網羅することは ほぼ不可能と考えてよい。これとは別に、古くから研究されている分野として 形式的検証と呼ばれる技術がある。これは、数学的に厳密に定義された形式で 書かれた仕様とソースコードのようなものを与えて、そのソースコードが仕様 を満たすかどうかを、コンピュータが全ての可能性を探索することで検証し、 結果を出力するといったものである。 先程のテストとの違いは、全ての可能性をコンピュータが探索するので、理論 上は漏れがないというメリットがある。ただ、形式的検証といっても現実に応 用するのは大変で、一番の問題は計算量が爆発するという問題がある。最悪の 場合、問題によっては計算機をどれだけ動かしても永遠に答えが出ない可能性 があることが理論的に証明されているといったタイプの問題もある。要するに、 計算量を抑えるにはどうすればいいかといった問題がある。 また、数学的に定義された仕様記述法をつかうので、それがそもそも検証した い仕様をうまく表現できているのかといった根本的な問題もある。 今回は、このような形式的手法を計量器の組込みソフトフェアに対してどこま で適用できるかといったことを調べることが目的となっている。 ○アプローチ 形式的手法の根幹的な技術としてはモデル検査法を用いる。これは、有限状態 システムを仮想的に動かして仕様を満たしているかを自動で調べるといった技 術である。ただ、ソフトウェアというのは状態数が無限と考えていいものなの で、このモデル検査法にそのまま適用することはできない。そこで今回、スラ イシングや抽象化技法と呼ばれる技術を組み合わせて、探索空間を有限に圧縮 することでモデル検査法を適用するといったアプローチをとった。また仕様記 述の方法は、線形時相論理式というものを用いた。 ○発表の流れ 　非自動はかり器の概要の説明 　モデル検査を行うツールとしてSPINと呼ばれるものがあるが、その概要の説明 　線形時相論理の説明 　状態空間のスライシングと抽象化の手法の説明 　結果 　まとめ ○非自動はかり器の概要 非自動はかりは2つのボードからなる。それぞれのボードにCPUが乗っているが、 メインボードの方は主にユーザとのインタラクション、タッチパネルからの入 力や出力、テンキーからの入力の受け付け、ディスプレイ、プリンタにレシー トを出力といったことをする。 一方、はかりボードと呼ばれるものは、はかりの台に加重をかけたときにその 信号がアナログではかりボードに入ってきて、AD変換器を通過してデジタルの 信号に直す。その後、はかりボード上の組込みソフトウェアで、そのデジタル に直された計量データをリアルタイムで加工する。その加工した結果をメイン ボードからのリクエストに応じてメインボード側に送り出す。 今回は、全ての組込みソフトウェアを相手にするのは大変なので、はかりボー ド上に乗っている組込みソフトウェアに限定して検証を行った。検証に使った メインのツールはSPINと呼ばれるツール。モデル検査を行うには検査をされる システムと、基準となる使用を与えなければならない。システムはPromelaと呼 ばれる言語を用いて記述して、有限状態の遷移モデルになっている。 また、仕様はLTL、線形時相論式理というもので書かれる。その２つを入力して、 有限状態遷移モデルが仕様を満たしていればYES、満たしていなければNOを出力 する。また、満たしていなかったときは、その使用を満たしていないことを示 す具体的な実行系列を出力するという機能をこのSPINは持っている。このSPIN に使われる使用記述法が線形時相論理と呼ばれるものである。 その基本命題としては、内部変数を用いてC言語の条件文のような形で記述する ことができる。例えばフラグｆがTRUEであるとか、xの値がy以上であるとかい う形で書くことができる。 その基本命題を使って、例えば、いつでも命題Pが成り立つとか、いつかは命題P が成り立つといった形で、これらの記述を組み合わせて仕様を加えていく。一 般に前者を完全性、後者を生存性と呼ぶ。 これらを組み合わせて、例えば、いつでもその先で、いつかはフラグbが真にな るといった内容の仕様を記述することができるようになっている。 ○検証手法の概要 そもそも検証したいものは、計量器組込みソフトウェアのフローチャートが仕 様を満たしているかどうかなので、入力は２つ、フローチャートと仕様である。 最終的にはSPINと呼ばれるツールに渡したいのだが、SPINは有限状態の遷移モ デルを入力として、仕様としてはLTL式を入力とする。従ってSPINに渡すために、 いくつかの変換を行わなければならない。 まず、計量器ソフトウェアのフローチャートからスタートして、そのフローチ ャートの中で検証したい仕様に関連する部分を抜き出す。この関係ない部分を 切り捨てる作業をスライシングという。そうやって抽出されたフローチャート の部分をスライスというが、SPINにかけるにはまだまだ大きすぎるので、さら に抽象化と呼ばれる作業を行って状態空間を圧縮する。その時点でやっとSPIN にプログラムで書ける状態になるので、一方、仕様はLTL式で書いて、SPINに その２つを入力して検証を行うという流れになる。 ○想定した仕様 はかりの主な処理として安定判定処理というのがある。これは、はかりの台の 上に肉とかそういった物を乗せたときに、風が吹いてきてその影響で揺れては 困るので、風などの影響をまず排除したい。ただし、何グラムか足りなくて意 図的に追加した場合は、その荷重の追加による計量値の変化は逆に反映させた い。ある種の、相矛盾するこの種の要求を満たすように作られているのが安定 判定処理である。 その、安定であるかどうかに関係する仕様を検証するのが今回のターゲット。 フローチャート中に安定フラグというのがある。それに着目して、それを使っ て表現できる仕様に今回は限定した。この安定判定フラグに着目して、それに 関係する部分を抜き出す。このスライシングという処理を最初に行った。 スライシングというのは、データ依存性と制御依存性を用いて、ある着目した 変数に関係する部分を抜き出してくる技術である。このスライシングを行った 結果、フローチャートの全719ポイント中、69ポイントに絞り込むことができた。 また、フローチャート中に存在する変数を、整数型12個に絞ることができた。 しかし、これだけ絞ってもSPINにかけるにはまだ大きすぎる。 そこで、次に抽象化という作業を行った。計量データが32ビットの整数で、5個 存在している。5個の中の2つの組み合わせは10組、その中の6組だけが、その2 つの変数の差分の絶対値が特定の値と比較されているという特徴を見つけた。 この5つの変数を取り除いて、その代わりに差分の絶対値を表す6つの変数を導 入して、しかもその定義域はフローチャート上で比較される定数値で、32ビッ トを分割して領域で分割し、その領域自体を値と見ることで圧縮を行った。 具体的に説明すると、今32ビットの変数XとYがあったとする。この差分の絶対値 |X-Y|というのも32ビットである。この|X-Y|が、フローチャート中で、0,a,b,c という4つの値としか比較されないとする。そうすると、全32ビットの値を領域 で分割して、それぞれを5つの値と見て、0から4までの値しかとらない変数と考 えると、その変数は3ビットに収めることができる。こういった圧縮を行うこと で、状態空間を1.13*10^45分の一まで圧縮することにより、SPINで検証できる ようになった。 SPINは、色んな実行系列を仮想的に動かしてみて、仕様が満たされない実行系 列を見つけると、自動的にストップして、その結果を出力する。よって、仕様 が満たされるときが一番時間がかかる。そのときの状態探索数が約30万、検証 時間が16.58秒で一応終了した。これにはPentiumⅢ600MHzを用いた。 ○検証結果 9個の動作仕様を考え、それをLTLの式で形式化して検証してみた。 その9個のうち、生存性に関わるものが4つで、安全性に関わるものが5つ。 ○まとめ ある組込みシステムの一部に対してであれば、いろんな技術を組み合わせるこ とで、この形式的な検証も適用が可能であるという一例を示すことができた。 また、線形時相論理式というものを使用したが、この非自動はかりについて言 えば、比較的上手く仕様を表現できていたのではないかと思っている。 ○今後の課題 ・より一般的な形で，どんな組込みシステムに対しても適用できるような手法 　を確立 ・リアルタイム制の導入 ・より複雑なモジュールに対しても検証がかのうであるように拡張 ・仕様をより直感的にかけるような手法の検討 ○所感 直感的に明らかな仕様であっても、線形時相論理で書くのは以外に大変で自明 ではない。また、書いた仕様自体が誤っている可能性が高い。しかし、何度も 繰り返し検証することでシステムの信頼性を上げることができると思っている。 ○質疑応答 ・タスクが複数になった場合はどうですか？ >今回のSPINと呼ばれるものでも、タスクが複数あってそれらが同期したり 　通信しあうようなものを書けるようにはなっています。 >今回は１つだけのタスクしか使ってなくて、SPINの機能を十分に使ってな 　かったんですが、それは可能です。 >ただ、タスクが増えると指数的に状態も増えていくので、現実的な時間で 　どう検証するかといった課題はあるかと思っています。 ・計量器のはかりでここまでやらなきゃいけない確たる理由は何ですか？ 　どういうレベルまで検証すればいいですか？ >目的が１つではないです。 >１つは先程説明しました安定判定処理と呼ばれるものの記述がですね、各 　メーカさんのコアとなっている技術で外には公開していただけない技術なん 　ですが、そこでほとんどノウハウに近い形で貯められています。 >実際にいろんな環境が変わった場合とか法律が変わったとかで、プログラム 　を変えなければいけない場合があります。 >そのときに１からまた検証しなおすのは心もとないということで、ああいっ 　た処理に限定しただけでも、ある程度動いているということが検証できれば 　嬉しいといった点があります。 >開発者側からの要望というのがあります。 >もう一点はですね、こちらの方が難しいと思うんですが、産総研で法定計量 　というのを行っておりまして、計量器が実際に法律の基準を満たしているか 　どうか検査する必要があるんですが、ソフトの部分がかなり大きくなってい 　るので現実的に物を乗っけただけで、実際にそういう検証だけでいいのかと 　いう問題があってですね、ソフト自体もいろんな組み合わせで検証しないと 　いけないということがあります。 >それに対して、全部は難しいと思うんですが、ある程度のある一部に対し 　ての検証ができればよいかと思います。 ・フォーマルメソッドは応答系が活発ですよね、いわゆる最終状態がない無 　限の状態ですが、この技術を応答系にもっていくには何が問題となると考 　えますか？ >インタラクティブなものですよね。 >例えば時相論理でも使うものが若干違ってくる可能性があります。 >このシステムでも応答系の部分はありますので、そちらに応用したいな 　とは思っているんですが、応答系はいくつかの問題がありまして、例えば 　人間とのインタラクションがあると、直感的に操作できるか？レスポンスを 　返せるかと、重要な使用になってくると思うんですが、そもそも形式化でき 　るかという問題があると思っています。 >それがクリアできたとしても、使う道具が若干変わってきて、こういうよ 　うな制御系だと線形的な使用記述方法が向いてると思うんですが、応答系 　だと、もっと途中の状態がどうなっているかということが重要になってくる 　かと思います。 ====================================================================== ITRON仕様カーネルのレディキュー構造による性能比較 伊藤圭○，渡辺洋輔，石川知雄，宮内新（武蔵工業大学） （○：発表者） ====================================================================== ○背景 わが国において機器組込みリアルタイムOSのスタンダードとなっているITRON 仕様の最新バージョンとしてμITRON4.0が公開されている。また、豊橋技術科 学大学を中心とするTOPPERSプロジェクトにより開発されたμITRON4.0仕様の評 価に加えて、研究及び教育用プラットフォームのカーネルとしてTOPPERS/JSPカ ーネルが提供されている。 ○研究目的 OSの主要な機能の１つとして、次に実行するタスクを決定する処理としてスケ ジューリングの機能がある。ITRON仕様のスケジューリング規則というものは、 優先度順の先頭タスクから実行されることのみを規定しており、実装上ではレ ディキューというもので実現している。簡単に説明すると、タスクの優先順位 を高いほうから順に実行可能タスクが繋がれていき、一番優先順位の高いタス クがCPUに移されて実行されることになる。このタスクの優先順位は、主にタス クが持っている優先度というパラメータによって決定される。この場合、優先 順位と優先度は定義的に異なるものとなっている。レディキューの内部構造と しては、カーネルの作成者側にゆだねられており、実際には具体的な判断基準 が存在しないので、このような設定の指標となるガイドラインがあることが望 ましいと考えた。 そこで、本研究の目的としては、レディキューの構造による性能の差を、定量 的に評価するという目的で異なる２つのレディキュー構造を用意し、実際に TOPPERS/JSPカーネル上に実装してオーバーヘッド等を測定し評価を行った。 ○比較するレディキュー構造 レディキューに新たに挿入されるタスクの位置が異なる。まず、タスクの持つ 優先度に従う。当然優先度が同じタスクというものが存在するわけで、その場 合はFCFS方式で、先に実行可能状態になったタスクが優先ということになる。 ここでTOPPERS/JSPカーネルについてだが、デフォルトのレディキューの構造と して、各優先度ごとにレディキューを備える構造をとっている。本研究では、 簡略化したレディキューを実装して性能比較・検討をしようということで、こ の優先度ごとに対応して一本化したレディキュー構造を作成して評価を行った。 この一本化したレディキューをシングルレディキューと名付た。 ○それぞれの構造 ┌─┐ │●│…Queue Head └─┘ ┌─┐ │ │…Task └─┘ Priority High ┌─┐ │ │●│←──────────┐ │ └─┘ │ │ 　↑ ┌─┐ ┌─┐ │ │ └→│ │←─→│ │←─┘ │ └─┘ └─┘ │ ┌─┐ │ │●│←┐ │ └─┘ │ │ 　↑ │ │ └──┘ │ │ ┌─┐ │ │●│←────┐ │ └─┘ │ │ 　 ↑ ┌─┐ │ │ └→│ │←─┘ │ └─┘ │ ┌─┐ │ │●│←────────────────┐ │ └─┘ │ │ 　↑ ┌─┐ ┌─┐ ┌─┐ │ │ └→│ │←─→│ │←─→│ │←─┘ Low └─┘ └─┘ └─┘ これが、デフォルトの優先度ごとの図。各優先度ごとにキューヘッダが存在し、 それぞれの優先度ごとの実行可能状態タスクが双方向にリンクしている構造を とる。タスクが存在しない優先度というのがあるが、その場合はリンク先がキ ューヘッダ自身を指すようにしてタスクが存在しないということを示している。 これに付随して、タスクが存在するかしないかというレディキューの管理、ビ ットマップというものが用意されており、レディキューアクセスの際にはその ビットマップを利用してアクセスすることになる。 Priority High ┌─┐ │ ┌→│●│ │ │ └─┘ │ │ ↑ ┌─┐ ┌─┐ │ │ └→│ │←─→│ │←─┐ │ │ └─┘ └─┘ │ │ │ ┌────────────┘ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ┌─┐ │ │ └→│ │←─┐ │ │ └─┘ │ │ │ │ │ │ ┌──────┘ │ │ │ │ │ 　│ ┌─┐ ┌─┐ ┌─┐ │ │ └→│ │←─→│ │←─→│ │←─┐ Low │ └─┘ └─┘ └─┘ │ └─────────────────────┘ これが、作成したシングルレディキューの図。先程は各優先度ごとにキューヘ ッダがあったが、キューヘッダが一本化ということで１つになる。異なる優先 度が全て双方向にリンクされる構造をとる。あるタスクにアクセスしたいとい う状態が起こるが、その場合、今回はタスクが持っている優先度情報を順番に キューヘッダの先頭から順探索していくアルゴリズムをとるようにした。その 理由としては、当然キューヘッダに近いほうから優先度が高いということなの で、そちらからやったほうが、当然リアルタイム性を必要とするパスであろう ということで順探索の方法をとった。 ○シングルレディキューの特徴 デフォルトのキュー構造を変えているので、カーネル部分の変更点を簡単に示 す。先程のビットマップは、各優先度ごとに有るのか無いのかを示すので、一 本化したことによって全て優先度が繋がれてしまうので、ビットマップの管理 がそもそも不要になるということで、レディキューの管理のビットマップ及び ビットマップを算出する関数というのを廃止した。逆に、順探索で調べていく のでタスク挿入時の挿入場所の探索関数というのを追加した。これによって、 レディキューの先頭付近、つまり優先度が高いタスクへの操作速度が向上する のではないかと考えた。特に、最高優先度タスクへのアクセスは最速となる。 最速というのは、探索はするが実際にはキューヘッダに繋がれたタスクは実際 には探索不要になるので、その意味で最高優先度タスクへのアクセスは最速と いうことになる。 ○各レディキューの評価手法 カーネルのコンパイル後のオブジェクトサイズを比較した。また、タスク操作 関連のシステムコールのオーバーヘッドを評価指標としている。これはそれぞ れ３つあり、タスクの起動命令、タスクの優先度を変更する命令、レディキュ ーを回転する命令、この３つをソフトウェアの対象とした。 この理由は、これらが特にレディキューを操作するのではないかという見解か ら、３つのシステムコールを選定した。それぞれ、各1000回試行した場合の平 均時間と最悪時間を測定した。測定に使用した実機は日立SolutionEngine、 CPUは133MHzのプロッセッサである。 ○結果 ・オブジェクトサイズ 　24.8KByteから23.0KByteへ約8%の減少が見られた。 ・キャッシュ保護の場合でのタスク起動命令のオーバーヘッドの平均時間 　　キャッシュOFFの場合では先頭付近、優先度１の場合でシングルが同等で、 　他は優先度ごとという結果が出ている。 　　キャッシュONの場合では、タスクの優先順位がおよそ５の場合はほぼ同等、 　６以上になると、優先度ごとの方が性能がよいという結果となった。 　　先程述べた最速ということで、優先順位１の場合はかなりよい結果を示し 　ているのではないかと思う。 　　最悪時間は、キャッシュOFFの場合では優先度ごとの方がよい性能だった。 　　キャッシュONの場合は、優先順位10程度までは同等ではないかというよう 　な結果となった。 　やはり、最高優先度においてはシングルの方がよい性能を示している。 ・優先度変更命令においては優先順位10以下ならばシングル、11以上になると 　デフォルトの方が性能がよいという結果になった。 　　キャッシュがONの場合では、かなりシングルの方もそれなりの所まで有効 　性が見られる。 　　ディスパッチが有る無しに関わらず、優先順位が２５個程度まではシング 　ルの方が優れているという結果となった。 ○まとめ シングルレディキューを実装したことによりタスク操作関連のオブジェクトサ イズの減少が見られた。今回は３種類しか比較してないがその３つを総括する と、システムコールのオーバーヘッドの面から見た場合では、タスク数5個以 下ではシングル、6個以上では優先度ごとがよいのではないかという結論を得た。 ○質疑応答 ・シングルの場合、rootから逆向きにも辿れますよね。ならば後ろから廻して 　に入れることができるならば，アルゴリズム的に平均を半分にできるのでは 　ないですか？ >アルゴリズム的にはそうなんですが、後ろの方から探索するのも確かに考 　えました。 ・しかし後ろの方からいったときに、優先度を見たりしなきゃいけない気がす 　るんですよ。 >で、後ろの方はあまりリアルタイム性が必要でないのではないかという気 　がしたので、しょうがないというか切り捨てではないですけど、後ろの方も 　やりたければ、あくまでガイドラインを示そうとしているので。 ・しかし、タスクの切り替えは神様の時間、OSの時間ですよね。 　だから、優先順位も何も無いんですよ。 　これを平均値でもいいから半分に減らせたら、システムを使った人はハッピ 　ーなんですよ。だから、そういう努力をすると大分、1/2は大きいですよ。 　だからいい結果になると思います。　前から入れる後ろから入れるというの 　もラフにやるんじゃなくて、例えば、優先度ごとの表を作っておくんですよ。 　それを参考にしてね、後ろから前からとやれば、いろいろと工夫する点はあ 　ると思いますよ。 >はい。 ・シングルの方が部が悪いという結果が出てる気がしますが、元々のデータ構 　造の方が操作時間が固定なわけですね。ライナー性という点において不利な 　わけですよ。そこらへについての見解をお願いします。 　>そもそも目的がガイドラインなので ・ガイドラインはいいんですけど、最終的にここっていうのが無いわけですよ。 　かなり小規模だったらいいよって話になりますよね。 　>この場合、そうなってしまいますよね。 ・5個だとそもそもレディキューに繋がっていなくていいかもしれないのでは？ 　>それは少し違っていて、最大レディになっているタスクの数が5個という話 　なので ・仕様の方で、タスクの数ｎを考えなければならないんですよ。 　>確かに固定時間より遅いという点は考えなければならないですね。 ====================================================================== 最小命令セットRISCへのGCCコンパイラ移植の試み 早坂晴康○,清水尚彦（東海大学） （○：発表者） ====================================================================== ○目標 ハードウェア、ソフトウェアの知識を研究室全体として得ようということで、 ハードウェアシステムを自分たちで構築し、その上でLinuxを動作させること を目標とした。ハードウェアシステムとしては、USB、PCIやVGAを自分達で作 って、内部的にはメモリシステム、キャッシュ、コントローラ、I/Oシステム、 を自分達で作って、本当にLinuxを動作させようという試み。今回、どのよう な命令があれば本当にGCCが動くのかという最低限のレベルを示そうとした。 ○環境 実際のプロセッサ、これはSNKというが、32bitのRISC型プロセッサで、命令数 はたった17個。レジスタは、汎用レジスタ8個と、PC、irで、最小構成となっ ている。 ○GCCの移植に必要なもの ・マシンディスクリプション 　　GCCではテスト用としてローカルというのが定義されているので、ローカル 　MDというふうに記述した。 　　この中には、命令パターンを記述する。 　　命令パターンの中に、スタンダードネーム、これはGCCが欲しがっているも 　のを満たすように記述した。 ・ターゲットマクロ 　SNK固有の情報を記述した。 ○命令パターン C言語のプログラムと、マッチング、これはコンパイラ中間表現ということで GCCが欲しがっているスタンダードネーム。 これでマッチングさせて、これをSNKの命令に変換する。MDの中にどんなふう に書くかということで、各命令パターンを定義した。 ○define_expand コンパイラで標準で要求されている命令パーターン名があり、それを define_insnで定義したインストラクションで出力するために使用する。 ○ターゲットマクロ 今回、方針としてリトルエンディアンを採用した。全ての変数をメモリ渡しに するように書いた。関数の入り口と出口のところに、レジスタの退避領域、局 所変数領域の確保を行うように書いた。 ○レジスタの定義 汎用レジスタとして8本、r0〜r7まで定義した。r0はi形式の場合、ソースレジ スタで使用するときは遷移0とした。固定的な使い方をするレジスタとしては 順番にr1,r0〜r7となっている。r4はリターンアドレスとして使用する。r5は 返り値のメモリのアドレスを定義するときに使用する。r6はフレームポインタ レジュームr7はスタックポインタ ○関数の入口と出口 ターゲットマクロのなかに記述してある。関数の入り口ではスタック領域の確 保が必要となる。関数の出口では、レジスタの領域と、スタックの領域を戻す ようにしている。 ○スタックの実際 呼び出す前に引数を書くためにスタックポインタが下げられて、次に出力引数 が確保される。これはGCCが勝手にやってくれる。次に関数の呼び出しの入り 口でスタックポインタを下げ、レジスタを退避させる。次にフレームポインタ をスタックと一緒に下げ、ローカル変数領域を使うようにする。その際、出力 引数を取るめに、FIRST_PARM_OFFSETというもので定義してやる。 ○デモ これが書いたもの。こんなような簡単なC言語を変換をさせる。 そうするとtest.Sができて、アセンブラが実際にこのように出てくる。 ○まとめ 今課題として乗算命令の対応があり、乗算命令自体がないので、他のシフトと かをあわせてライブラリコールとして実装することを検討している。また、 binutilsの移植でCGENを用いて移植を行っていくことを検討している。 ○質疑応答 ・レジスタのアドレスをサブルーチンのターゲットとしてリンク＆ジャンプ 　する命令、balrがないと関数のテーブルの読みがうまくいかないような気 　がしますが、mdで要求されませんでしたか？ 　関数を例とすると，配列かなんかでもってて，i番目の関数に割り当てるよ 　うなことを書くと、ここでbalrがないと厳しいのでは？ 　>bal命令がインデックスタイプとなっていますので、インデックスのイミデ 　ィエイトを0にすることでbalrと等価で動くはずです。 ・そのコンパイラが正しく動いているということはどうやって検証される予定 　ですか？ 　>一応、カーネルをコンパイルして動かしてみようというのが最初の目的だ 　ったので、どうやって検証するかというのはちょっと考えていません。 ====================================================================== 【記録者自身の感想】 一定の基礎知識がないと、説明や質疑応答の内容も理解しづらいと感じた。 質疑応用の議論が収束しないままの発表や、結果に対する評価が十分に行わ れていない発表もあったような印象を受けた。 組込みシステム内の様々な分野の発表を聞くことができたので、非常に有意義 であった。