著者

小池 龍信 岩井 輝男 中西 正和

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.40, no.7, pp.1-8, 1999-08-15

参考文献数

8

被引用文献数

1

---

ごみ集め処理(GC)を必要とする言語がいくつか存在し Lisp言語などのような関数型言語処理系にはGCが不可欠である.これらの処理系は 実時間性に向いてないとされてきた.理由としては GCを行っている時に処理が一時中断することがあげられる.この中断時間をできるだけ減らすための研究がなされている.このようなGCを実時間GCと呼び その中の一つにTreadmill GCがある.Treadmill GCは複写式GCを改良したものである.このGCでは全てのオブジェクトを双方向環状リストで連結し GCは複写によるオブジェクトの移動ではなく 双方向ポインタのつけかえ(relink)で実現する.これにより複写式GCの利点を保持し さらにオブジェクトの移動を行わないため複写式GCで問題となるreadバリアが解消されている.Treadmill GCの時間的コストは生きているオブジェクトの数に比例する.よって生きているオブジェクトが多い場合には実時間性が乏しい.この問題点の解決方法として世代別GCの考えを取り入れた.世代別GCの考え方は ある程度生き続けたオブジェクトは半永久に生き残り また生成して間もないオブジェクトの殆どは寿命が短いというものである.本稿では 世代別GCの考えを取り入れたTreadmill GC(Opportunistic Treadmill GC)の提案及びその実現方法 さらにいくつかのベンチマークアプリケーションを実行し その実験結果から1回のGC時間 総実行時間を削減したことについて報告を行う.Real-time Garbage Collection is a study that makes pause time of GC as short as possible. Treadmill GC, one of the real-time GC algorithms, is improved Copying GC. In this scheme all objects are linked by cyclic doubly-linked lists (treadmill). Objects are not removed by copying, and objects' pointer of treadmill are relinked. This means that advantages of Copying GC are preserved, solving read barrier problem at the same time. We propose the "Opportunistic Treadmill GC", which is a Garbage Collection technique that the collector traces only short-life objects, setting long-life objects out of collector's view. There is a strong evidence that the overwhelming majority of objects die very young, although a small proportion may live for a long time. In Treadmill GC, pause time of GC is mostly the time for relinking alive objects. Especially in the original Treadmill GC, collector has to relink all alive object. However in Opportunistic Treadmill GC, collector only has to relink short-life objects of all alive objects. Hence we can make a pause time of GC shorter and improve effective real-time GC. Then we implemented the original Treadmill GC and Opportunistic Treadmill GC on an incremental garbage collector of the Lisp1.5 based system, and showed how efficient it is by a few experiments, in comparison with the original Treadmill GC, we could decrease average time of one GC execution as well as total execution time. We refined incremental GC so that the real-time systems with our Opportunistic Treadmill GC will be more useful.

著者

高橋 聡子 岩井 輝男 田中 良夫 前田 敦司 中西 正和

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.38, no.5, pp.1050-1057, 1997-05-15

参考文献数

14

---

リスト処理プロセスとGCプロセスを同時に複数動作させることによって,リスト処理を並列化することによる処理時間の短縮が可能になった.しかし,セルの消費のペースはアプリケーションによって異なり,CPUの数も計算機によって異なるので,リスト処理プロセスの最適な数はアプリケーション,計算機によって異なると考えられる.本稿では,セルの消費速度やフリーセルの残量によってリスト処理プロセスとGCプロセスのCPU割当てを動的に決定する機能により,Lispの代表的なアプリケーションに対し,処理速度と実時間性とのバランスのとれた処理を行うことを可能とする並列Lispシステムの報告を行う.本システムの実装にあたっては,できるだけリスト処理の中断が生じることがなく,リスト処理に最大数のCPUが割り当てられるようCPU割当てのパラメータを設定し,CPU割当てを動的に決定した.その結果,リスト処理の中断がなくなり実行時間が短縮された.Parallel lisp system with parallel garbage collection(GC)can produce improvements in throughput by executing list processing in parallel.But,the optimal number of list processes and GC processes depends on machines and applications because the number of processors on a machine and cells which are consumed by various applications is different.In this paper,we report parallel lisp system which makes it possible to balance throughput and real time performance by dynamic allocation of CPU depending on speed of consuming cells and the number of remaining free cells.We dynamically changed CPU allocation according to the parameter which was set to avoid a disruption of list processing and allocateas many CPU as possible to list processing.Consequently,our system yielded improvements in throughput without any disruption of list processing.

著者

萩原 知章 岩井 輝男 中西 正和

雑誌

全国大会講演論文集

巻号頁・発行日

vol.第52回, no.ソフトウェア, pp.19-20, 1996-03-06

---

世界的に行われているLisp言語の標準化の活動の1つとして、国際標準機構ISOによるものがあり、ISLispと呼ばれている。ISLispの特徴は、Common Lispの仕様から使用頻度の低い機能を取り除いたものである。このため、Common Lispに比べ処理系の作成が容易である。また、オブジェクト指向機能も兼ね備えている。本研究では、ISLispに準拠したLispの実装をバイトコードインタプリタにより行なった。この実装は2段階に分けられる。第1段階(本システム):コンパイラがLispのプログラムを後置記法に直し、中間コードに変換する。そして、このコードに最適化を施し、バイトコードで書かれたファイルに変換する(これ以降この作業をコンパイルという)。第2段階:バイトコードインタプリタがバイトコードに変換されたプログラムを読み込み、解読し、スタック機械により実行する。本稿では、第1段階のコンパイラの実装および、中間コードに最適化を施した際の実行効率について述べる。

著者

岩井 輝男 中西 正和

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. 記号処理研究会報告

巻号頁・発行日

vol.93, no.52, pp.9-16, 1993-06-18

---

Lisp ServerはMach OS 3.0 と似ていて,単純な機能とLispインタプリタを備えたOSである.この基本となる考えはシンプルで,拡張性のあるカーネルの通信を持っている.この目的はすべてのOSの処理がカーネルを通してユーザプログラム(スレッド)間の通信で可能になるまで,OSの機能をカーネルの外に出すことである.極端に言えば,カーネルはユーザプログラム間の通信をサポートするだけとなる.このような思想のもとに設計したLisp ServerはMulti-User Multi-Threadであり,すべてのLispのセルを共有した,環境をユーザに与えるOSである.

著者

萩原 知章 岩井 輝男 中西 正和

雑誌

全国大会講演論文集

巻号頁・発行日

vol.52, pp.19-20, 1996-03-06

---

世界的に行われているLisp言語の標準化の活動の1つとして、国際標準機構ISOによるものがあり、ISLispと呼ばれている。ISLispの特徴は、Common Lispの仕様から使用頻度の低い機能を取り除いたものである。このため、Common Lispに比べ処理系の作成が容易である。また、オブジェクト指向機能も兼ね備えている。本研究では、ISLispに準拠したLispの実装をバイトコードインタプリタにより行なった。この実装は2段階に分けられる。第1段階(本システム):コンパイラがLispのプログラムを後置記法に直し、中間コードに変換する。そして、このコードに最適化を施し、バイトコードで書かれたファイルに変換する(これ以降この作業をコンパイルという)。第2段階:バイトコードインタプリタがバイトコードに変換されたプログラムを読み込み、解読し、スタック機械により実行する。本稿では、第1段階のコンパイラの実装および、中間コードに最適化を施した際の実行効率について述べる。