教育コース生　花井亮

	１．はじめに

戦略ソフトウェアプログラムではGCを、一から設計して実用的なソフトウェアとして作りあげることを目標として活動している。本プログラムで設計・実装す るのは、アプリケーションプログラムの停止時間をかなり小さく抑える実時間GCである。停止時間の目安としては100μ秒とする。また、実装した実時間 GCを実際にヒューマノイドの制御に利用して評価することを考えている。

	２．ヒューマノイドソフトウェア環境と実時間GC

複雑化するヒューマノイドソフトウェアの開発効率を上げるため、開発にLispを利用するというアプローチがある。しかし、開発にLispを用いた場合に も、従来はGCによるアプリケーションプ ログラムの停止の問題を回避するため、反射系など実時間性を必要とする処理の記述はCやC++といった言語を用いて行い、別プロセスとして実行するという 形にならざるを得なかった。本研究で開発する実時間GCを利用すると、知識表現の上位の記述からから実時間性の必要な反射系の記述までを統一的に Lispで記述し、それぞれをマルチスレッド対応Lisp処理系の上でスレッドとして実行することができる。これにより、従来ソケットなどを用いて通信す る必要があった処理を、単にLispの変数に値を読み書きするだけで行うことができるし、動的な機能の追加もLispのloadで可能になる。また、 Lispの対話的環境を制御ソフトウェアの開発に利用できるということは、初期段階では特に有用である。

	３．戦略ソフトウェアの設計

	３．１　想定するアプリケーション（の振る舞い）

GCの方式自体は、必ずしもロボット制御に依存したものではない。ただし、アプリケーションはヒューマノイドソフトウェアのように、複数の非同期処理が存 在 し、また、実時間性を必要とする処理や、必ずしも実時間性を必要としない処理が混在するものとしている。これは、多くの実時間アプリケーションに共通した 特徴でもある。

	３．２　実時間GC実現

実時間GCを実現するには、

• 予測不可能な停止時間につながる処理の排除
• ヒープの空き領域が不足し、アプリケーション のメモリ要求に応えられない状態（飢餓状態）の回避

が必要となる。

３．２．１　基本方式

本ソフトウェアでは、100μ秒のように、小さな停止時間を実現するために、「スナップショット＋リターンバリア方式」を採用した。この方式は、基本的に はマーク＆スイープ方式であり、多くのインクリメンタルGCにおいて問題となるスタックのスキャンを分割して行うことで、アプリケーションの停止要因を排 除する方式である。

３．２．２　リターンバリア

スナップショット方式を実現するためには、あるタイミングでルート集合のスナップショットをとる必要があるが、スタックのようにアクセスされる場所が限ら れている場所はそこだけスキャンしておいて、残りの部分のスキャンは遅らせることができる。リターンバリアの着眼点はまさにそこである。スタックはその性 質上、アクセスが現在実行している関数のフレームに限られる。そこで、はじめに実行中の関数のフレーム（カレントフレーム）をスキャン済みにしておけば、 後は必要になるまで遅らせても良い。こうすることで、時間的緊急度の高い処理が再開するために必要なルートのスナップショットを優先的にとり、必要なス ナップショットがとれたスレッドから再開することができる。リターンバリア方式の具体的手順は、以下のようになる。

1. コレクターは、GC開始時には カレントフレームだけスキャンして、その下にバリアを設定する。
2. その後、
　　・ コレクターはスタックを上からスキャンしながらバリアを下げていく。
　　・ アプリケーションプログラムはリターンする時、下のフレームがまだスキャンされていなければ自分でスキャンしてバリアを下げてからリターンする。

	４．現状

• 上記のGCの基本的な部分を実装した
• 対象： EusLisp
  ロボット制御を目的として開発されたLisp処理系
• 試験的な性能評価
  実装の改良により変化するが、とりあえず現状の評価
  まずまず結果（実行時間、停止時間）
• 実時間Linuxの１つであるART-Linuxに基づいた評価環境の整備

	4．1　性能評価

• 環境：　Pentium M 1.60 GHz
  メモリ1GB
  Debian Linux 2.4.18
• アプリケーション
  大きな２分探索木を作成後、ランダムにノードの挿入・削除を繰り返す
• 測定対象：　アプリケーションの実行時間
• EusLispが持っている一括GCを用いた場合と比較
• 結果：　およそ10%から15%程度のオーバヘッドがある
  GCとアプリケーションの処理を細かく切り替えるほどキャッシュミスが増えると予測されるから、この程度のオーバヘッドは妥当といえる（このあた りの詳細については今後、詳しく調査していく予定）。

	５．今後の課題

現在、GCは別スレッドとして実装してある。これは、多くの非同期処理を行う環境では、比較的CPUの空き時間が存在するため、その間にGCを行ってしま うことが理想的だからである。しかし、この方法では必ずしも飢餓状態を回避することはできない。そこで、アプリケーションのメモリ要求率に応じてGC処理 の速さを変えることができるインクリメンタル方式を組み合わせることを考えている。これを、どのように組み合わせるかが今後の課題である。
また、
・ 整備したART-Linux上で、より実用的なアプリケーションを用いてテストをする。
・ 実際にロボット制御に使ってみる。
といったことも今後の課題である。