(57)【要約】【課題】ガーベッジコレクションにはコンテキストスイッチが伴っていたので、オーバーヘッドによるパフォーマンス低下が見られていた。【解決手段】デジタルテレビジョン受像器１０のＪａｖａ仮想機械３６内において、インタプリタ処理部２６がＪａｖａプログラムをスレッド単位で実行し、各スレッドが１対１でタスクと対応づけられ、カーネル２０によりスケジューリングの対象となる。生成処理部２８がスレッド内でオブジェクトを生成し、メモリ管理部３０が各オブジェクトにヒープ領域を割り当てる。実時間管理部３２は、スレッドごとの実時間度を管理し、その実時間度に基づく中断期間にＧＣ処理部３４がＧＣ処理を実行する。【選択図】        図２
2004234546.tif 000002
【特許請求の範囲】
【請求項１】
プログラムの実行において不要となったオブジェクトに割り当てられた領域を解放するガーベッジコレクションの処理を、実行中のスレッドに設定された実時間度に応じてそのスレッドの処理を中断する間に、そのスレッド内で実行することを特徴とするプログラム実行方法。
【請求項２】
前記ガーベッジコレクションの処理を実行中に他のスレッドの割り込みがあったとき、前記他のスレッドの実時間度に応じたタイミングで前記ガーベッジコレクションの処理を停止してその未実行分の処理を次回以降へ繰り越すことを特徴とする請求項１に記載のプログラム実行方法。
【請求項３】
プログラムをスレッド単位で実行するインタプリタ処理部と、
前記スレッド内でオブジェクトを生成する生成処理部と、
前記オブジェクトにメモリ領域の一部を割り当てるメモリ管理部と、
前記スレッドに設定された実時間度を管理する実時間管理部と、
前記メモリ領域のうちどのオブジェクトにも割り当てられていない空き領域が所定値を下回ったときに、実行中のスレッドの実時間度に応じた期間、そのスレッドの処理を中断し、前記プログラムの実行において不要となったオブジェクトに割り当てられた領域を解放するガーベッジコレクションの処理を前記中断する期間にそのスレッド内で実行するＧＣ処理部と、を有することを特徴とするプログラム実行装置。
【請求項４】
前記ＧＣ処理部は、前記ガーベッジコレクションの処理を実行中に他のスレッドの割り込みがあったとき、前記他のスレッドの実時間度に応じたタイミングで前記ガーベッジコレクションの処理を停止してその未実行分の処理を次回以降へ繰り越すことを特徴とする請求項３に記載のプログラム実行装置。
【請求項５】
プログラムをスレッド単位で実行する機能と、
前記スレッド内でオブジェクトを生成する機能と、
前記オブジェクトにメモリ領域の一部を割り当てる機能と、
前記スレッドに設定された実時間度を管理する機能と、
前記メモリ領域のうちどのオブジェクトにも割り当てられていない空き領域が所定値を下回ったときに、実行中のスレッドの実時間度に応じた期間、そのスレッドの処理を中断する機能と、
前記プログラムの実行において不要となったオブジェクトに割り当てられた領域を解放するガーベッジコレクションの処理を前記中断する期間にそのスレッド内で実行する機能と、をコンピュータに発揮させることを特徴とするコンピュータプログラム。
【請求項６】
前記実行する機能は、前記ガーベッジコレクションの処理を実行中に他のスレッドの割り込みがあったとき、前記他のスレッドの実時間度に応じたタイミングで前記ガーベッジコレクションの処理を停止してその未実行分の処理を次回以降へ繰り越すことを特徴とする請求項５に記載のコンピュータプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、プログラム実行方法および装置に関する。本発明は特に、Ｊａｖａプログラムを実行する仮想機械の技術に関する。
【０００２】
【従来の技術】
Ｊａｖａ（登録商標）プログラムを実行する環境であるＪａｖａ仮想機械（Ｊａｖａ  Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ）がもつ特徴の一つとして、ガーベッジコレクション（以下、単にＧＣという。）がある。これは、実行中のプログラムによって利用されなくなったオブジェクトに割り当てられているメモリ領域を回収して再利用可能な状態に遷移させる機能であり、メモリ解放の命令をあらかじめプログラムに明示しなくともＪａｖａ仮想機械側が自動的に処理するので、プログラマからメモリ管理の手間を省きの負担を軽減できる機能である。このＧＣにはいくつかの方式が知られている（例えば、特許文献１および非特許文献１参照。）。
【０００３】
【特許文献１】
特開２０００−９９３５１号公報  （全文）
【非特許文献１】
湯浅太一、「実時間ごみ集め」、情報処理１９９４年１１月、Ｖｏｌ．３５
Ｎｏ．１１
【０００４】
【発明が解決しようとする課題】
上記従来技術においては、ＧＣを処理するためのスレッドをあらかじめ起動しておき、そのスレッドの実行優先度を周期的に切り替えながらＧＣ以外のスレッドと交互に実行させている。また、実時間性の高い他のスレッドの割り込みがあったときは、その割り込みのあったスレッドへ即座に処理を移譲させていた。
【０００５】
しかしながら、実行するスレッドを切り替えるにはコンテキストスイッチが伴うためオーバーヘッドが大きくなり、全体的なパフォーマンス低下を招きやすい。また、実時間性の高いスレッドの割り込みがあったときに無条件にＧＣスレッドから割り込みスレッドへ処理を移譲してしまうと、結果的に空きヒープ領域が枯渇してしまうおそれがある。
【０００６】
本発明はこうした状況に鑑みなされたものであり、その目的はスレッドの実時間性を最大限に担保しつつ適切なメモリ管理を実現する点にある。別の目的は、コンテキストスイッチを伴わないＧＣを実現する点にある。さらに別の目的は、最低限必要なＧＣ処理進行を確保してヒープ領域の枯渇を防止する点にある。
【０００７】
【課題を解決するための手段】
本発明のある態様はプログラム実行方法である。この方法は、プログラムの実行において不要となったオブジェクトに割り当てられた領域を解放するガーベッジコレクションの処理を、実行中のスレッドに設定された実時間度に応じてそのスレッドの処理を中断する間に、そのスレッド内で実行する。ガーベッジコレクションの処理を実行中に他のスレッドの割り込みがあったとき、他のスレッドの実時間度に応じたタイミングでガーベッジコレクションの処理を停止してその未実行分の処理を次回以降へ繰り越してもよい。
【０００８】
ここでは、ＧＣの処理をそのスレッド内で実行しており、別個の独立したスレッドでＧＣを実行する構成ではないので、コンテキストスイッチを伴わずにＧＣを実行できる。
【０００９】
「実時間度」は、そのスレッドをリアルタイムに実行すべき必要性の度合いを示し、あらかじめスレッドごとまたはオブジェクトごとにその度合いを設定しておく。例えば即時実行の必要性が高いスレッドほど実時間度を高く設定しておく。スレッドの実時間度は、その処理の中断期間を決定するときと、割り込み時の実行開始タイミングを決定するときに参照される。複数のスレッドが並列処理されるときは、それぞれの実時間度の高低をもとにＧＣの実行時間を判定してもよい。このように、スレッドを即時実行する必要性とＧＣを実行する必要性との調停を図り、最適なＧＣ実行時間を確保する。これにより、スレッドの実時間性を担保しつつ、最低限必要なＧＣを実行してヒープ領域の枯渇を防止できる。
【００１０】
本発明の別の態様はプログラム実行装置である。この装置は、プログラムをスレッド単位で実行するインタプリタ処理部と、スレッド内でオブジェクトを生成する生成処理部と、オブジェクトにメモリ領域の一部を割り当てるメモリ管理部と、スレッドに設定された実時間度を管理する実時間管理部と、メモリ領域のうちどのオブジェクトにも割り当てられていない空き領域が所定値を下回ったときに、実行中のスレッドの実時間度に応じた期間、そのスレッドの処理を中断し、プログラムの実行において不要となったオブジェクトに割り当てられた領域を解放するガーベッジコレクションの処理を前記中断する期間にそのスレッド内で実行するＧＣ処理部と、を有する。
【００１１】
ＧＣ処理部は、ガーベッジコレクションの処理を実行中に他のスレッドの割り込みがあったとき、他のスレッドの実時間度に応じたタイミングでガーベッジコレクションの処理を停止してその未実行分の処理を次回以降へ繰り越してもよい。
【００１２】
本態様においても、スレッドを即時実行する必要性とＧＣを実行する必要性との調停を図り、最適なＧＣ実行時間を確保する。これにより、スレッドの実時間性を担保しつつ、最低限必要なＧＣを実行してヒープ領域の枯渇を防止できる。
【００１３】
なお、以上の構成要素の任意の組合せや、本発明の構成要素や表現を方法、装置、システム、コンピュータプログラム、プログラムを格納した記録媒体、データ構造などの間で相互に置換したものもまた、本発明の態様として有効である。
【００１４】
【発明の実施の形態】
（第１実施形態）
本実施形態においては、本発明のプログラム実行装置をデジタルテレビジョン受像器として実現した例を説明する。デジタルテレビジョン受像器は、デジタル衛星放送やデジタル地上波放送の放送波をデコードして画面に表示するとともに、放送信号に付随して受信するデータ放送を用いて番組以外の情報を画面に表示する点に特徴がある。画面の表示制御にＪａｖａプログラムが用いられ、その実行環境としてのプログラム実行装置をＪａｖａ仮想機械の形で実現する。
【００１５】
図１は、デジタルテレビジョン受像器１０の基本構成図である。デジタルテレビジョン受像器１０は、デジタル放送の放送信号を受信する受信部１２と、放送信号を復号して映像信号に変換するデコード部１４と、放送番組およびデータ放送を画面に表示させる表示処理部１６と、デジタルテレビジョン受像器１０の動作を制御する制御部１８と、を有する。制御部１８は、受信部１２、デコード部１４、表示処理部１６に対して動作を指示する。例えば、リモートコントローラからの信号を受けて、放送信号の受信、放送信号の復号、画面への表示処理などを指示する。制御部１８を中心とした各構成の制御には、それぞれ即時実行の必要性に応じてあらかじめ実時間度が設定されている。
【００１６】
制御部１８を中心としたデジタルテレビジョン受像器１０の各構成の制御は、ハードウェア的には、ＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウェア的にはメモリにロードされた表示処理機能や制御機能のあるプログラムなどによって実現される。図２では特にソフトウェアに着目して機能ブロックを描いているが、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組合せと連携によっていろいろな形で実現できることは、当業者には理解されるところである。
【００１７】
図２は、デジタルテレビジョン受像器１０において実行されるソフトウェアのモジュール構成図である。デジタルテレビジョン受像器１０を制御するＯＳは、リアルタイムマルチタスクカーネル（以下、単にカーネルという）２０を中心として動作し、各プログラムの複数のタスクを並列的に処理する。実行するプログラムは、このＯＳ向けに機械語へコンパイルされたアプリケーションプログラム２２と、Ｊａｖａ仮想機械３６向けに中間コードへコンパイルされたＪａｖａプログラム２４とがある。
【００１８】
Ｊａｖａ仮想機械３６は、Ｊａｖａプログラム２４をスレッド単位で実行するインタプリタ処理部２６と、スレッド内でオブジェクトを生成する生成処理部２８と、各オブジェクトにメモリ領域の一部をヒープ領域として割り当てるメモリ管理部３０と、各スレッドに設定された実時間度を管理する実時間管理部３２と、ＧＣを実行するＧＣ処理部３４と、を含む。Ｊａｖａ仮想機械３６において実行されるスレッドに１対１でタスクが対応づけられることを前提とする。
【００１９】
ＧＣ処理部３４は、実行中のスレッドの実時間度を実時間管理部３２から取得し、その実時間度に応じてＧＣ処理による中断時間を決定する。ＧＣ処理部３４は、ＧＣ処理中に他のスレッドの割り込みがあったとき、そのスレッドの実時間度に応じてＧＣ処理の停止または続行を決定する。ＧＣ処理の詳細は後述する。
【００２０】
図３は、複写式ＧＣの過程を模式的に示す。まず、メモリ領域のうち各オブジェクトに割り当て可能な領域を二つに分割する。そのうちいずれか一方の領域をヒープ領域としての割り当てに使用する。図のように左側のメモリ領域４０を使用する場合に、順次複数のオブジェクト５０にヒープ領域を割り当てていき、左側のメモリ領域４０から使用中のヒープ領域４２を引いた空きヒープ領域４４が所定値（以下、「ＧＣ起動閾値」という。）を下回るまで続ける。ルート領域４６には、各オブジェクト５０へのポインタが格納されている。
【００２１】
空きヒープ領域４４がＧＣ起動閾値を下回ったとき、ルート領域４６を走査し、ポインタをもとに辿ることのできるオブジェクト５０を順次右側のメモリ領域５２へ複写する。複写したオブジェクトのポインタは新たなアドレスに更新する。ルート領域４６の走査とオブジェクトの複写が完了した後、左側のメモリ領域４０をすべて消去する。これにより、プログラムの実行に必要なオブジェクトがすべて右側のメモリ領域５２へ移動する反面、不要なオブジェクトは右側のメモリ領域５２へ移動しないので、右側の使用中のヒープ領域５４は左側の使用中のヒープ領域４２よりも容量が小さくなる。こうして左側のメモリ領域４０と右側のメモリ領域５２とをＧＣ処理しながら交互に使用する。
【００２２】
図４は、Ｊａｖａ仮想機械３６を起動してから終了するまでの全体的な過程を示すフローチャートである。まずヒープ領域の初期化として、メモリ領域内にヒープ領域を確保し（Ｓ１０）、空きヒープ領域４４の値を初期化し（Ｓ１２）、ＧＣ起動閾値を設定する（Ｓ１４）。ＧＣ処理のスケジューリングに用いるパラメータとして、まず保証される基準中断時間に相当する基準仕事量を決定する（Ｓ１６）。この保証される基準中断期間は、ＧＣ処理中に他のスレッドの割り込みがあったときの反応時間に基づいて定まる。すなわち、他のスレッドの割り込み有無にかかわらず、この基準中断期間が最低限のＧＣ処理期間として保証される基準値となる。そして、各スレッドの実時間度に応じたこの基準中断期間の倍数の期間、ＧＣ処理が実行される。基準仕事量は、基準中断期間だけＧＣ処理を実行した場合にその処理によって走査されるオブジェクトの総データサイズである。
【００２３】
次に、スレッドの実時間度に応じて実行すべきＧＣ処理量を示す目標仕事量を決定し（Ｓ１８）、ＧＣ処理の実行中であることを示すＧＣ処理中フラグを初期化する（Ｓ２０）。以上の各初期化作業が終わったところでプログラムを実行する（Ｓ２２）。そのプログラムの終了とともにＪａｖａ仮想機械３６も終了する。
【００２４】
図５は、図４において実時間度ごとの目標仕事量を決定するＳ１８の詳細を示すフローチャートである。ここでは、実時間度のレベルの数だけ目標仕事量の決定を繰り返す。繰り返し変数ｉに最大実時間度を代入し（Ｓ３０）、基準仕事量に基づいて目標仕事量を決定する（Ｓ３２）。目標仕事量は、最大実時間度をＭＡＸＲとすると次式で示される。
目標仕事量＝基準仕事量×（ＭＡＸＲ＋１−ｉ）
目標仕事量を決定後、繰り返し変数ｉをデクリメントし（Ｓ３４）、繰り返し変数ｉが最小実時間度になるまでＳ３２およびＳ３４の処理を繰り返す（Ｓ３６Ｎ）。繰り返し変数ｉが最小実時間度になると（Ｓ３６Ｙ）、図４のＳ２０へ続く。これにより、実時間度ごとの目標仕事量が得られる。例えば、実時間度が高いほど目標仕事量は小さく、実時間度が低いほど目標仕事量は大きい。
【００２５】
図６は、オブジェクト生成からＧＣ処理までの過程を示すフローチャートである。まずオブジェクト生成にあたり、ヒープ確保のためにメモリ領域のロックをカーネル２０から獲得し（Ｓ４０）、ＧＣ処理中フラグがオンになっている場合は（Ｓ４２Ｙ）、後述するＳ５０までスキップする。ＧＣ処理中フラグがオンになっておらずＧＣ処理中でない場合（Ｓ４２Ｎ）、空きヒープ領域４４から実行するオブジェクトのサイズを引いた値がＧＣ起動閾値を下回るならば（Ｓ４４Ｙ）、ＧＣ処理中フラグをオンにして（Ｓ４６）、繰越仕事量の値を初期化する（Ｓ４８）。Ｓ４４においてＧＣ起動閾値を下回らない場合は（Ｓ４４Ｎ）、Ｓ５４までスキップする。
【００２６】
Ｓ４８で繰越仕事量の値を初期化した後、単位仕事係数を設定し（Ｓ５０）、ＧＣ処理を実行する（Ｓ５２）。単位仕事係数は、例えばオブジェクトサイズ１ＭＢあたりの走査量であり、ヒープ領域の大きさに依存する。その後、オブジェクトにメモリ領域の一部を割当て（Ｓ５４）、空きヒープ領域４４の値を更新する（Ｓ５６）。最後にヒープ領域確保のためのロックを解除してオブジェクトの生成を終了する（Ｓ５８）。
【００２７】
図７は、図６のＳ５２におけるＧＣ処理の詳細な過程を示すフローチャートである。まず処理済仕事量の値を初期化し（Ｓ６０）、繰越仕事量が０であれば（Ｓ６２Ｎ）、Ｓ６８までスキップし、繰越仕事量が０より大きければ（Ｓ６２Ｙ）、目標仕事量を元の目標仕事量の整数Ｎ倍とし（Ｓ６４）、その増分を繰越仕事量から差し引く（Ｓ６６）。なお、目標仕事量の整数Ｎ倍は、例えば２倍程度に設定するなど、Ｓ６６において増分差し引き後の繰越仕事量が０未満にならないような範囲とする。その後、走査処理を実行し（Ｓ６８）、終了処理を実行する（Ｓ７０）。このように繰越仕事量が減少する方向でＧＣ処理を余分に実行することにより、ヒープ領域の枯渇を防止する。
【００２８】
図８は、図７のＳ６８における走査処理の詳細な過程を示すフローチャートである。まずＧＣを実行するスレッドの実時間度に対応する目標仕事量を基準仕事量で割った値を変数Ｌに代入し（Ｓ８０）、繰り返し変数ｉをリセットし（Ｓ８２）、実時間度に応じた基準仕事量のＧＣ処理を実行し（Ｓ８４）、その実行した分の仕事量を処理済仕事量に加える（Ｓ８６）。ここで、他のスレッドによってヒープ領域確保のためのロック獲得が試行されていなければ（Ｓ８８Ｙ）、変数ｉをインクリメントし（Ｓ９０）、変数Ｌが変数ｉより小さくなければ（Ｓ９２Ｎ）、Ｓ８４へ戻る。Ｓ８８においてロック獲得が試行されていたときは（Ｓ８８Ｎ）、本図の走査処理を終了する。Ｓ９２において変数Ｌが変数ｉより小さいときもまた、本図の走査処理を終了する（Ｓ９２Ｙ）。
【００２９】
図９は、図７のＳ７０における終了処理の詳細な過程を示すフローチャートである。すでに全オブジェクトを走査してある場合（Ｓ７２Ｙ）、ＧＣ処理中のフラグをオフにしてＧＣ処理を終了する（Ｓ７４）。全オブジェクトの走査が終わっていない場合（Ｓ７２Ｎ）、繰越仕事量は次式で示される。
繰越仕事量＝現時点での繰越仕事量＋オブジェクトサイズ×単位仕事係数−処理済仕事量
この式によって繰越仕事量を求め（Ｓ７６）、この繰越仕事量を次回以降のＧＣ処理に繰り越す。
【００３０】
（第２実施形態）
第１実施形態においては、ＧＣ処理中に他のスレッドの割り込みがあったとき、ＧＣ処理を停止してそのまま他のスレッドへ処理を移譲する構成とした。本実施形態には、割り込みのあった他のスレッドの実時間度に応じてＧＣ処理の続行または停止する点で異なる。すなわち、図８のＳ８８においては、他のスレッドがヒープ領域のロック獲得を試行したか否かだけでなく、他のスレッドの実時間度に応じてＧＣ処理を停止すべきか否かを同時に判断する。他のスレッドの実時間度が最大の場合はただちにＧＣ処理を停止して図８の処理を終了する。他のスレッドの実時間度が最大ではない場合、その実時間度に応じた数を変数ｉに加えてＳ８４からＳ９２までのループ回数を調整し、他のスレッド実行までの遅延時間を反映させる。また、実行中のスレッドの実時間度よりも割り込みスレッドの実時間度が高い場合にＧＣ処理を停止してもよい。
【００３１】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、その各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００３２】
実施の形態においては、基準仕事量を単位としてその倍数で目標仕事量を設定していた。これは目標仕事量を固定的に定めて正確な実時間性を確保するハードリアルタイム式である。一方、変形例においては、実時間度に応じて目標仕事量を定めるとともに、オブジェクトごとに実時間性の猶予度も別途設定しておき、その猶予度に基づいて目標仕事量に幅をもたせるソフトリアルタイム式であってもよい。例えば、ＧＣ処理中に実時間度の高い他のスレッドの割り込みがあっても、その割り込みスレッドの猶予度に応じてＧＣ処理の停止タイミングおよび割り込みスレッドへの移行タイミングを変えてもよい。これにより、各スレッドが許容する限り少しでも長い期間ＧＣ処理を実行してヒープの枯渇を防止できる。
また、オブジェクトごとの実時間度および猶予度をあらかじめテーブルの形で設定しておいてもよい。
【００３３】
実施の形態においては、デジタルテレビジョン受像器にＪａｖａ仮想機械３６を組み込んだ例で説明した。変形例においては、本発明のＪａｖａ仮想機械３６を他の装置に組み込んだ構成としてもよいし、コンピュータ上で実行させる構成としてもよい。
【００３４】
実施の形態においては、図３のように複写式ＧＣを採用したが、変形例においては、ＧＣのスケジューリングが可能である限り複写式ＧＣ以外の方式を採用してもよい。
【００３５】
【発明の効果】
本発明によれば、プログラムのリアルタイム性を確保しつつ、ガーベッジコレクションの処理時間も確保することができる。
【図面の簡単な説明】
【図１】デジタルテレビジョン受像器の基本構成図である。
【図２】デジタルテレビジョン受像器において実行されるソフトウェアのモジュール構成図である。
【図３】複写式ＧＣの過程を模式的に示す図である。
【図４】Ｊａｖａ仮想機械を起動してから終了するまでの全体的な過程を示すフローチャートである。
【図５】図４において実時間度ごとの目標仕事量を決定するＳ１８の詳細を示すフローチャートである。
【図６】オブジェクト生成からＧＣ処理までの過程を示すフローチャートである。
【図７】図６のＳ５２におけるＧＣ処理の詳細な過程を示すフローチャートである。
【図８】図７のＳ６８における走査処理の詳細な過程を示すフローチャートである。
【図９】図７のＳ７０における終了処理の詳細な過程を示すフローチャートである。
【符号の説明】
２０  カーネル、  ２６  インタプリタ処理部、  ２８  生成処理部、  ３０メモリ管理部、  ３２  実時間管理部、  ３４  ＧＣ処理部、  ３６  Ｊａｖａ仮想機械、  ４０  メモリ領域。
【図１】
2004234546.tif 000003
【図２】
2004234546.tif 000004
【図３】
2004234546.tif 000005
【図４】
2004234546.tif 000006
【図５】
2004234546.tif 000007
【図６】
2004234546.tif 000008
【図７】
2004234546.tif 000009
【図８】
2004234546.tif 000010
【図９】
2004234546.tif 000011