JPH10116230A - メモリ管理装置及びコンピュータ読み取り可能な記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】 書き換え回数制限型メモリの長寿命化を図り
ながら、処理時間の短いガーベジコレクションの実現を
可能にする。 【解決手段】 安定度設定部１２は、新規オブジェクト
の安定度を０に、所定回数のガーベジコレクション処理
の間に回収や書き込みが行われない安定度Ｎのオブジェ
クトの安定度を（Ｎ＋１）に設定する。オブジェクト割
付部１４は、安定度０，１のオブジェクトをＲＡＭ８に
割り付け、安定度２，３のオブジェクトをフラッシュメ
モリ７に割り付ける。未使用領域が無い場合には、ガー
ベジコレクション実行部１３によって、ＲＡＭ８の安定
度０の領域から順次高い安定度の領域を加えてガーベジ
コレクション処理を繰り返す。こうして、ガーベジコレ
クション処理の回数と時間とを短縮し、ガーベジコレク
ションに伴う書き換えをフラッシュメモリ７に対して少
ない回数で行って書き換え回数制限型メモリの長寿命化
を図る。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、書き換え回数に
制限のあるメモリの長寿命化を図りながら、メモリの利
用効率が高くて中断時間の短いガーベジコレクションの
実現を可能にするメモリ管理装置及びコンピュータ読み
取り可能な記録媒体に関する。

【０００２】

【従来の技術】近年、ＰＤＡ（Ｐｅｒｓｏｎａｌ Ｄｉ
ｇｉｔａｌ Ａｓｓｉｓｔａｎｔ）等のバッテリで動作
する携帯型の情報処理端末機器が実現化されている。上
記ＰＤＡのような端末は、少ないメモリ容量で動作する
ことや、低消費電力であることが強く要求される。上記
ＰＤＡでは、未使用時にシステムの状態を保存するため
に、バッテリでバックアップされたＲＡＭ（ランダム・
アクセス・メモリ）を搭載することが多い。そして更
に、低消費電力化を図るために、上記ＲＡＭのかなりの
部分を低消費電力のフラッシュメモリに置き換えるよう
になっている。

【０００３】一方、メモリの利用効率を高めて、アプリ
ケーションプログラムの構築を容易にするメモリ管理手
法として、ガーベジコレクションが知られている。例え
ば、ニュートン（アップル社製）のオペレーティングシ
ステムは、上記ガーベジコレクションを主要なメモリ管
理手法として採用している。但し、上記ニュートンにお
いては、ガーベジコレクションの対象となるのはＲＡＭ
領域のみである。

【０００４】

【発明が解決しようとする課題】しかしながら、上記従
来のガーベジコレクションには、上記ＰＤＡのような端
末システムのメモリ管理手法として用いた場合には以下
のような問題がある。

【０００５】（１）実行の中断 上記ガーベジコレクションの実行中には、アプリケーシ
ョンを含む他のシステムの実行が中断させられる。その
ために、ある量以上のメモリに対するガーベジコレクシ
ョンの実行は、対話的な利用を前提とするＰＤＡでは、
利用者に対する応答を悪化させることになる。

【０００６】（２）メモリの頻繁な書き換え 上記ガーベジコレクションは、通常ＲＡＭ上のメモリ管
理を前提としているため、例外なく、管理の対象となる
メモリ空間を頻繁に走査して書き換えるようにしてい
る。そのために、上記ガーベジコレクションを、フラッ
シュメモリのように書き換え回数に制限のあるメモリに
対してそのまま適用すると、メモリの寿命を著しく縮め
てしまう。

【０００７】すなわち、上記ＰＤＡのように、フラッシ
ュメモリのごとく書き換え回数に制限のあるメモリを搭
載している計算機システムでガーベジコレクションを実
現するためには、ガーベジコレクション実行による他の
システムの実行の中断時間を短縮することと同時に、書
き換え回数制限型メモリの寿命を延ばすための対策を講
ずる必要がある。

【０００８】ガーベジコレクションの処理時間を短縮す
る手法は「実時間ガーベジコレクション」と呼ばれてお
り、多数提案されている。しかしながら、フラッシュメ
モリのような書き換え回数制限型メモリを搭載するシス
テムに対して、書き換え回数制限型メモリを含むメモリ
領域への適用を想定した実時間ガーベジコレクション
は、これまで知られていない。

【０００９】そこで、この発明の目的は、書き換え回数
に制限のあるメモリの長寿命化を図りながら、メモリの
利用効率が高くて処理時間の短いガーべジコレクション
の実現を可能にするメモリ管理装置を堤供することにあ
る。

【００１０】

【課題を解決するための手段】上記目的を達成するた
め、請求項１に係る発明は、書き換え回数制限型メモリ
とＲＡＭと上記両メモリの論理アドレスを物理アドレス
に変換するアドレス変換部を有するシステムのメモリ管
理装置であって、上記書き換え回数制限型メモリあるい
はＲＡＭの未使用領域が所定の大きさより小さい場合
に、この未使用領域が小さいメモリに対してガーベジコ
レクション処理を行うガーベジコレクション実行部と、
上記各メモリに対するデータの割り付け単位を表す情報
であるオブジェクトに対して、上記各メモリに対する新
規オブジェクトの割り付け時、あるいは、上記ガーベジ
コレクション処理実行時に、上記ガーベジコレクション
処理によって回収されず且つ当該ガーベジコレクション
処理時まで書き込みが行われなかった場合に増加する安
定度を設定する安定度設定部と、上記各メモリに対する
新規オブジェクトの割り付け時、あるいは、上記ガーベ
ジコレクション処理実行時に、上記安定度設定部によっ
て設定された安定度が所定値以下のオブジェクトを上記
ＲＡＭに割り付ける一方、上記安定度が上記所定値より
高いオブジェクトを上記書き換え回数制限型メモリに割
り付けるオブジェクト割付部を備えたことを特徴として
いる。

【００１１】上記構成において、書き換え回数制限型メ
モリあるいはＲＡＭに対する新規オブジェクトの割り付
けが要求されると、安定度設定部によって新規オブジェ
クトの安定度が設定される。そして、オプジェクト割付
部によって、上記設定された安定度が所定値以下である
場合には、上記新規オブジェクトはＲＡＭに割り付けら
れる。一方、上記安定度が上記所定値より高い場合に
は、上記新規オブジェクトが上記書き換え回数制限型メ
モリに割り付けられる。さらに、上記新規オブジェクト
を割り付ける際に、割り付け対象となる上記書き換え回
数制限型メモリあるいはＲＡＭの未使用領域が所定の大
きさより小さい場合には、ガーベジコレクション実行部
によってガーベジコレクション処理が行われる。そし
て、上記安定度設定部によって、当該ガーべジコレクシ
ョン処理によって回収されず且つ当該ガーベジコレクシ
ョン処理時まで書き込みが行われなかったオブジェクト
の安定度が増加される。そして、上記設定された安定度
が上記所定値より高くなると、上記オブジェクト割付部
によって、当該オブジェクトは上記ＲＡＭから上記書き
換え回数制限型メモリに割り付け直される。

【００１２】こうして、常に、上記安定度が所定値以下
のオブジェクトを上記ＲＡＭに割り付ける一方、上記安
定度が上記所定値より高いオブジェクトを上記書き換え
回数制限型メモリに割り付けることによって、上記ガー
ベジコレクション処理によって回収されにくく且つ書き
込みが起こりにくいオブジェクト群が上記書き換え回数
制限型メモリに割り付けられる。その結果、上記書き換
え回数制限型メモリに対する書き換えや書き込みが押さ
えられて、上記書き換え回数制限型メモリの長寿命化が
図られる。

【００１３】また、請求項２に係る発明は、請求項１に
かかる発明のメモリ管理装置において、上記ガーベジコ
レクション実行部は、上記未使用領域が所定の大きさよ
り小さいメモリに関して、上記安定度の高いオブジェク
トが割り付けられている領域よりも、上記安定度の低い
オブジェクトが割り付けられている領域に対して、高い
頻度で上記ガーベジコレクション処理を行うようになっ
ていることを特徴としている。

【００１４】上記構成によれば、上記安定度の低いオブ
ジェクトが割り付けられている領域に対して高い頻度で
上記ガーベジコレクション処理が行われる。したがっ
て、上記ガーベジコレクション処理に付随する書き換え
は、上記安定度の低いオブジェクトが割り付けられてい
る上記ＲＡＭに対して頻繁に行われることになり、上記
書き換え回数制限型メモリの更なる長寿命化が図られ
る。さらに、上記安定度の低いオブジェクトが割り付け
られている領域に対して高い頻度で上記ガーベジコレク
ション処理が行われることによって、該当するメモリの
全領域に対して一様に上記ガーベジコレクション処理を
行う場合よりも上記ガーべジコレクション処理の時間が
短縮されて、他の処理の中断時間が短縮される。

【００１５】また、請求項３に係る発明は、請求項２に
かかる発明のメモリ管理装置において、上記ガーベジコ
レクション実行部は、上記未使用領域が所定の大きさよ
り小さいメモリに関して、上記所定の大きさの未使用領
域が得られるまで，最も低い安定度のオブジェクト群が
割り付けられている領域に順次高い安定度のオブジェク
ト群が割り付けられている領域を加えて上記ガーベジコ
レクション処理を行うようになっていることを特徴とし
ている。

【００１６】上記構成によれば、上記安定度が低いオブ
ジェクト群が割り付けられている領域程上記ガーベジコ
レクション処理の回数が多くなり、上記安定度の高いオ
ブジェクトが割り付けられている上記書き換え回数制限
型メモリに対する上記ガーベジコレクション処理に付随
する書き換えが少なくなる。こうして、上記書き換え回
数制限型メモリの更なる長寿命化が図られる。さらに、
上記未使用領域が所定の大きさより小さいメモリの全領
域に対して一様にガーベジコレクション処理を行う場合
よりも処理時間が短縮されて、他の処理の中断時間が短
縮される。

【００１７】また、請求項４に係る発明は、請求項１に
係る発明のメモリ管理装置において、上記安定度設定部
は、上記新規オブジェクトの割り付け時には，新規オブ
ジェクトの安定度を最小値に設定し、上記ガーベジコレ
クション処理実行時には，当該ガーベジコレクション処
理によって，処理対象領域に在る同一安定度のオブジェ
クトに対するガーベジコレクション処理回数が上記安定
度になってから所定回数になった場合に，上記処理対象
領域に在るオブジェクトであって上記所定回数のガーベ
ジコレクション処理が行われる間に書き込みが行われな
かったオブジェクトの安定度を所定値だけ増加するよう
になっていることを特徴としている。

【００１８】上記構成によれば、新規オブジェクトの安
定度が最小値に設定されるので、殆どが短期間のうちに
他のオブジェクトとの参照関係が成立しないゴミと化す
新規オブジェクトが上記ガーベジコレクション処理回数
の多い上記ＲＡＭに割り付けられる。こうして、メモリ
の利用効率が高められる。さらに、書き込みが行われに
くいオブジェクトの安定度が増加されるので、上記書き
換え回数制限型メモリには書き込みが行われないと予測
されるオブジェクトが割り付けられることになる。こう
して、上記書き換え回数制限型メモリの更なる長寿命化
が図られる。

【００１９】また、請求項５に係る発明は、請求項１に
係る発明のメモリ管理装置において、上記アドレス変換
部は、上記書き換え回数制限型メモリ上におけるアドレ
ス変換の単位領域としてのぺージであって書き込み禁止
であるページに対して書き込みが要求されて発生するア
クセス例外を検知するアクセス例外検知手段を備えて、
上記アクセス例外検知手段によってアクセス例外が検知
された場合には、書き込みが要求された論理アドレス空
間上の論理ページが写像された上記書き換え回数制限型
メモリの物理アドレス空間上の物理ページの内容を上記
ＲＡＭの物理アドレス空間上の未使用の物理ページにコ
ピーし、このコピーされた上記ＲＡＭの物理ページを上
記書き込みが要求された論理ページに対応付けるように
なっていることを特徴としている。

【００２０】上記構成によれば、上記書き換え回数制限
型メモリ上における書き込み禁止ぺージに対して書き込
みが要求されるアクセス例外が発生した場合には、書き
込みが要求された論理アドレス空間上の論理ページが上
記ＲＡＭの物理アドレス空間上の物理ページに写像され
るので、以後上記書き換え回数制限型メモリ上における
書き込み禁止ぺージに対する書き込みが可能となる。さ
らに、上記書き換え回数制限型メモリ上における論理ペ
ージに発生した書き込みが上記ＲＡＭに対して行われる
ことなり、結果として上記書き換え回数制限型メモリの
更なる長寿命化が図られる。

【００２１】また、請求項６に係る発明は、請求項１乃
至請求項５の何れか一つに係る発明のメモリ管理装置に
おいて、上記書き換え回数制限型メモリは、フラッシュ
メモリであることを特徴としている。

【００２２】また、請求項７に係る発明は、書き換え回
数制限型メモリとランダム・アクセス・メモリと上記両
メモリの論理アドレスを物理アドレスに変換するアドレ
ス変換部を有するシステムのメモリ管理装置として機能
させるためのプログラムを記録したコンピュータ読み取
り可能な記録媒体であって、上記書き換え回数制限型メ
モリあるいはランダム・アクセス・メモリの未使用領域
が所定の大きさより小さい場合に、この未使用領域が小
さいメモリに対してガーベジコレクション処理を行うガ
ーベジコレクション実行部と、上記各メモリに対するデ
ータの割り付け単位を表す情報であるオブジェクトに対
して、上記各メモリに対する新規オブジェクトの割り付
け時、あるいは、上記ガーベジコレクション処理実行時
に、上記ガーベジコレクション処理によって回収されず
且つ当該ガーベジコレクション処理時まで書き込みが行
われなかった場合に増加する安定度を設定する安定度設
定部と、上記各メモリに対する新規オブジェクトの割り
付け時、あるいは、上記ガーベジコレクション処理実行
時に、上記安定度設定部によって設定された安定度が所
定値以下のオブジェクトを上記ランダム・アクセス・メ
モリに割り付ける一方、上記安定度が上記所定値より高
いオブジェクトを上記書き換え回数制限型メモリに割り
付けるオブジェクト割付部として機能させるためのプロ
グラムを記録したことを特徴としている。

【００２３】

【発明の実施の形態】以下、この発明を図示の実施の形
態により詳細に説明する。図１は本実施の形態のメモリ
管理装置が搭載された計算機システムにおけるブロック
図である。尚、本実施の形態においては、書き換え回数
に制限のあるＥＥＰＲＯＭとしてフラッシュメモリが使
用されているものとする。

【００２４】図１に示す計算機システム１は、本実施の
形態の特徴であるメモリ管理装置２と、データ用メモリ
が登載されたメモリ部５と、メモリ管理装置２における
管理情報に従ってプログラムやデータ上のメモリアドレ
ス（論理アドレス）をハードウェア上のメモリアドレス
（物理アドレス）に変換するメモリ管理ユニット（以
下、ＭＭＵと略称する）４と、メモリ管理装置２，ＭＭ
Ｕ４およびメモリ部５を制御して上記アドレス変換やガ
ーベジコレクション等を行うＣＰＵ（中央演算処理装
置）３で概略構成される。

【００２５】上記メモリ部５に登載されたデータ用メモ
リは、書き換え回数制限型メモリであるフラッシュメモ
リ７と読み書き可能なＲＡＭ８から構成されている。上
記メモリ管理装置２は、アドレス変換表格納部９，物理
アドレス空間管理部１０，論理アドレス空間管理部ｌ
ｌ，安定度設定部１２，ガーベジコレクション実行部１
３およびオブジェクト割付部１４から構成されている。

【００２６】上記アドレス変換表格納部９はＲＡＭで構
成されて、上記論理アドレスと物理アドレスとの対応を
示すアドレス変換表が格納されている。このアドレス変
換表は、ＭＭＵ４が上記アドレス変換を行う際に参照さ
れる。上記物理アドレス空間管理部１０は、物理アドレ
ス空間上の使用領域と未使用領域を管理する。上記論理
アドレス空間管理部ｌｌは、論理アドレス空間上の使用
領域と未使用領域を管理する。

【００２７】上記安定度設定部１２は、アプリケーショ
ンプログラムが要求するデータの割り付け単位を表す情
報（オブジェクト）に対して、「ガーベジコレクション
による回収されにくさ」と「書き込みの起こりにくさ」
とを合わせた指標（数値）である「安定度」を設定す
る。ここで、上記「回収」とは、後に詳述するように、
ガーベジコレクションを実行する際に、あるオブジェク
トがゴミとなって引き上げられることである。

【００２８】上記「安定度」の設定は、以下のように行
われる。 ・新規に割り付けられたオブジェクトの安定度を最小
（本実施の形態では「０」）にする。 ・ある安定度を有するオブジェクト群については、上記
安定度になってから、上記安定度に対して定められてい
る所定回数だけガーベジコレクションが施された後に、
上記安定度を（本実施の形態では「ｌ」だけ）増加す
る。但し、その所定回数のガーベジコレクションの間に
書き込みが行われたオブジェクトに関しては、上記安定
度の増加を抑制する。

【００２９】上記ガーベジコレクション実行部１３は、
上記データ用メモリの未使用領域が減少したときにガー
ベジコレクションを実行する。また、オブジェクト割付
部１４は、新規オブジェクトを論理アドレス空間に割り
付けたり、ガーべジコレクション処理の際に安定度が変
化したオブジェクトを新たな安定度の領域に割り付け直
したりする。

【００３０】上記構成の計算機システム１は、以下のよ
うに動作する。ここで、上記メモリ部５のフラッシュメ
モリ７には低安定度（安定度０と安定度１）のオブジェ
クトが設定される一方、ＲＡＭ８には高い安定度（安定
度２と安定度３）のオブジェクトが設定されている。先
ず、上記ＣＰＵ３によって新規オブジェクトの割り付け
要求がなされると、安定度設定部１２によって新規オブ
ジェクトの安定度が最低安定度「０」に設定され、オブ
ジェクト割付部１４によって論理アドレス空間管理部ｌ
ｌの管理情報が参照されてＲＡＭ８用の論理アドレス空
間上の未使用領域に割り付けられる。その際に、上記Ｒ
ＡＭ８用の論理アドレス空間上に新規オブジェクトを割
り付け可能な程度の未使用領域が無い場合には、ガーベ
ジコレクション実行部１３によって論理アドレス空間上
における安定度「０」のオブジェクト群が連続して設定
されている領域に対してガーベジコレクション処理を実
行して十分な未使用領域を得る。尚、十分な未使用領域
が得られない場合には、十分な未使用領域が得られるま
でより高い安定度の領域を順次加えながらガーベジコレ
クション処理を行う。こうして、常時論理アドレス空間
の総ての領域に対して一様にガーベジコレクション処理
を実行するよりも少ないガーベジコレクション回数で処
理時間の短縮を図り、早い時期にゴミとなってしまう低
安定度のオブジェクトに対するガーベジコレクション処
理の頻度を高くしてオブジェクトの回収率を高める。

【００３１】上記安定度設定部１２は、ガーベジコレク
ション実行部１３によって論理アドレス空間の安定度Ｎ
の領域に所定回数Ｘ_Nだけガーベジコレクション処理が
行われた際に、他のオブジェクトとの参照関係が成立す
るためにゴミとなって回収されることがなく、且つ、そ
れまでに書き込みが行われなかったオブジェクトの安定
度を（Ｎ＋１）に増加させる。そして、安定度が「ｌ」
から「２」に増加されるオブジェクトは、オブジェクト
割付部１４によって、上記Ｘ_N回目のガーベジコレクシ
ョン処理の際にＲＡＭ８側からフラッシュメモリ７側に
割り付け直される。こうして、書き込みが行われないと
予測される安定したオブジェクトのみをガーベジコレク
ション処理に伴う書き換えの頻度が少ないフラッシュメ
モリ７側に集めることによって、フラッシュメモリ７の
長寿命化を図るのである。

【００３２】以下、上記ＭＭＵ４，安定度設定部１２，
ガーベジコレクション実行部１３およびオブジェクト割
付部１４の動作についてより詳細に説明する。図２は、
上記オブジェクトの構成を示す概念図である。上記オブ
ジェクトは、一つの連続した論理アドレス空間上に低位
番地から高位番地に向かって順次配列されている。そし
て、一つのオブジェクトの構成は、ガーベジコレクショ
ン実行部１３によってガーベジコレクション処理を実行
するために、以下のような特徴を有している。 （Ａ）上記オブジェクトは、先頭を表すヘッダ２１，参
照するオブジェクトの数２２および参照するオブジェク
トのポインタ２３，２３，…の情報格納領域から成り、
各情報格納領域は夫々１ワードの大きさを持つ。そし
て、ヘッダ２１の先頭には１ビットの書き込みフラグ２
４が設定され、次の１ビットにはマークフラグ２５が設
定されている。これらのフラグは何れも負論理であっ
て、初期値は「１」である。上記書き込みフラグ２４に
は、当該オブジェクトに書き込みが行われた場合に
「０」が書き込まれる（以下、このことを「セットす
る」と言う）。そして、当該オブジェクトにガーベジコ
レクション処理が実行される際に「１」にクリアされ
る。したがって、書き込みフラグ２４を監視すること
で、安定度を増加するのに必要な上記所定回数のガーベ
ジコレクションの間に、当該オブジェクトに書き込みが
行われたが否かを知ることができるのである。上記マー
クフラグ２５には、当該オブジェクトが他のオブジェク
トから参照されている場合に、ガーベジコレクションの
際に「０」が書き込まれる（以下、このことを「セット
する」と言う）。上記フラッシュメモリ７は、各ブロッ
クのデータを消去した後には全ワードの各ビットに
「１」が書き込まれており、各ビットの「１」を「０」
に書き換えることは可能（逆は不可）である。そこで、
フラッシュメモリ７上に設定された論理アドレス空間に
配置されたオブジェクトの場合にも、書き込みフラグ２
４やマークフラグ２５を実現できるのである。本実施の
形態においては、フラッシュメモリ上のオブジェクトに
関しては、マークフラグ２５のみを設定する。

【００３３】（Ｂ）上記ポインタ２３には、参照される
他のオブジェクトの先頭（ヘッダ２１）の論理アドレス
が書き込まれる。 （Ｃ）オブジェクトの途中のワードを指す論理アドレス
から当該オブジェクトの先頭の論理アドレスを知ること
ができる。これは、ヘッダ２１に、参照するオブジェク
トの数２２に書き込まれる「数」の情報あるいはオブジ
ェクトのポインタ２３に書き込まれる「ポインタ」の情
報と識別可能なパターンを呈する情報を付加し、オブジ
ェクトの途中のワードを指す論理アドレスから低位番地
の方に上記パターンを呈する情報を検索することによっ
て可能となる。

【００３４】本実施の形態においては、図２に示すよう
に、同じ安定度を有するオブジェクトを同一論理アドレ
ス空間上に連続して配置する。そして、論理アドレス空
間管理部ｌｌで、各論理アドレス空間に配置されたオブ
ジェクト群の安定度と、その安定度を持つオブジェクト
群が配置されている領域の論理アドレス上の範囲を管理
しておく。こうすることによって、安定度設定部１２
は、論理アドレス空間管理部ｌｌにオブジェクト群の先
頭アドレスを問い合わせることによって、各オブジェク
トに付与された安定度を知ることができるのである。

【００３５】図３は、上記ＣＰＵ３によって書き込みが
要求された際に、ＭＭＵ４によって行われるアドレス変
換の一例の様子を示す概念図である。図３に示すよう
に、論理アドレス空間には、フラッシュメモリ７用に設
定された連続空間と、ＲＡＭ８用に設定された連続空間
とがある。尚、他にＲＯＭ６用の連続空間もあるが、本
実施の形態においては省略する。同様に、物理アドレス
空間にも、フラッシュメモリ７上に設定された連続空間
と、ＲＡＭ８上に設定された連続空間とがある。

【００３６】通常、上記ＭＭＵ４によるアドレス変換
は、バックアップ用の２次記憶装置を用いて、大きな論
理アドレス空間を小さな物理アドレス空間に写像する
「仮想記憶」のために用いられることが多い。しかしな
がら、本実施の形態においては、説明の都合上、ディス
ク等の２次記憶装置を持たず、ＲＡＭ８に関しては設定
された物理アドレス空間よりも論理アドレス空間の方が
小さいものとする。

【００３７】図３において、オブジェクトａはフラッシ
ュメモリ７側に在って、アドレス変換の単位領域（以
下、ページと言う）Ｐより小さい領域を有している。オ
ブジェクトｂはフラッシュメモリ７側に在って、ページ
Ｐより大きい領域を有している。オブジェクトｃはＲＡ
Ｍ８側に在って、べージＰより小さい領域を有してい
る。オブジェクトｄはＲＡＭ８側に在って、べージＰよ
り大きい領域を有している。

【００３８】上記ＭＭＵ４は、主にフラッシュメモリ７
に写像されるフラッシュメモリ７側の論理アドレス空間
上のぺージであって、アドレス変換表格納部９に格納さ
れたアドレス変換表において「書き込み禁止」がエント
リされているページに対して、書き込みを行おうとする
「アクセス例外」を検知するアクセス例外検知手段１５
を有している。そして、上記ＭＭＵ４は、アクセス例外
検知手段１５によって上記アクセス例外が検知された場
合には、この書き込み禁止のぺージが写像されたフラッ
シュメモリ７上の物理アドレス空間におけるぺージ（以
下、物理ページと略称する）の内容をＲＡＭ８上の物理
アドレス空間における未使用ページにコピーし、このコ
ピーされたＲＡＭ８上の物理ページを写像元のフラッシ
ュメモリ７側の論理アドレス空間におけるぺージ（以
下、論理ぺージと略称する）に対応付け直すのである。
こうすることによって、以後、書き込み禁止であった論
理ぺージに対して書き込みが可能になる。すなわち、上
記書き込み禁止が指定されるようなフラッシュメモリ７
をデータ用メモリとしても使用可能になるのである。

【００３９】図４は、上記アクセス例外発生時に行われ
るアドレス変換の様子を示す概念図である。図４におい
ては、フラッシュメモリ７用に設定された論理アドレス
空間上に在る上記オブジェクトｂの最初の論理ぺージに
書き込み禁止が指定されており、この論理ページに対し
てＣＰＵ３によって書き込みが要求された場合に、ＭＭ
Ｕ４によって行われるオブジェクトｂのアドレス変換の
様子を示している。

【００４０】上記アクセス例外時におけるアドレス変換
処理は以下のようにして行われる。図５は、上記ＭＭＵ
４によって行われるアクセス例外アドレス変換処理動作
のフローチャートである。以下、図５に従って、上記ア
クセス例外時におけるアドレス変換処理について詳細に
説明する。

【００４１】上記ＭＭＵ４のアクセス例外検知手段１５
によって上記アクセス例外が検知されると、アクセス例
外アドレス変換処理動作がスタートする。ステップＳ１
で、上記物理アドレス空間管理部１０の管理情報に基づ
いて、ＲＡＭ８上の物理アドレス空間からの未使用物理
ページの取得が行われる。ステップＳ２で、上記ステッ
プＳ１において未使用の物理ページが取得できたか否か
が判別される。その結果、取得できた場合にはステップ
Ｓ３に進み、取得できなかった場合にはステップＳ７に
進む。

【００４２】ステップＳ３で、上記ステップＳ２におい
て取得されたＲＡＭ８上の未使用物理ページに、アクセ
ス例外を起こしたフラッシュメモリ７上の物理ページ
（図３におけるフラッシュメモリ７上の物理ページ３
１）の内容がコピーされる。ステップＳ４で、上記物理
アドレス空間管理部１０に対して、アクセス例外を起こ
したフラッシュメモリ７上の物理ページ３１が未使用に
なったことが通知される。

【００４３】ステップＳ５で、上記ステップＳ３におい
てコピーされたＲＡＭ８上の物理ページ３２にアクセス
例外を起こしたフラッシュメモリ７上の物理ページの元
の論理アドレスが対応付けられて書き込み可能になるよ
うに、上記アドレス変換表のエントリが書き換えられ
る。ステップＳ６で、上記アクセス例外を起こしたフラ
ッシュメモリ７側の論理ページ３１が属するオブジェク
トｂのへッダ２１の書き込みフラグ２４が「０」にセッ
トされる。そうした後、アクセス例外アドレス変換処理
動作を終了する。

【００４４】ここで、上述のように、上記ＲＡＭ８に関
しては設定された物理アドレス空間よりも論理アドレス
空間の方が小さいので、物理アドレス空間には余分な領
域３３（図４参照）が生ずる。そこで、上記ステップＳ
ｌにおいては、この余分な領域３３から未使用物理ペー
ジの取得が行われて、論理アドレスと物理アドレスとの
割り付けの変更が行われるのである。そして、やがて余
分な領域３３に未使用物理ページがなくなると、上記ス
テップＳ２において未使用物理ページが取得できないと
判別されて、ステップＳ７に進む。

【００４５】ステップＳ７で、例えば、「ＣＰＵのキャ
ッシュ」や「仮想記憶」の分野で公知の「ＬＲＵアルゴ
リズム(Ｌeast Ｒecent Ｕsed Ａlgorithm)」を用い
て、過去に上記ステップＳ１において取得されて使用さ
れている（つまり、フラッシュメモリ７用の論理アドレ
ス空間に割り付けられている）ＲＡＭ８上の物理ぺージ
の中で、現時点から最も長い問アクセスされていない物
理ぺージが選出される。ステップＳ８で、上記物理アド
レス空間管理部１０の管理情報に基づいて、フラッシュ
メモリ７上の物理アドレス空間から未使用の物理ぺージ
が選出される。ステップＳ９で、上記ステップＳ８にお
いて選出されたフラッシュメモリ７上の未使用物理ペー
ジのブロックデータが消去される。そうした後、この消
去された物理ぺージに、上記ステップＳ７において選出
されたＲＡＭ８上の最も長い問アクセスされていない物
理ぺージの内容がコピーされる。こうして、上記フラッ
シュメモリ７上の未使用の物理ページを再利用すること
によって、上記ステップＳ４において物理アドレス空間
管理部１０に対して未使用の登録がなされたアクセス例
外を起こしたフラッシュメモリ７側の物理ぺージ３１も
再使用されることになる。

【００４６】ステップＳ１０で、上記ステップＳ９にお
いてコピーされたフラッシュメモリ７上の物理ぺージに
上記ステップＳ７において選出されたＲＡＭ８上の物理
ぺージの元の論理アドレスが対応付けられるように、上
記アドレス変換表のエントリが書き換えられる。ステッ
プＳ１１で、上記物理アドレス空間管理部１０に対し
て、上記ステップＳ７において選出されたＲＡＭ８上の
物理ページが未使用になったことが通知される。そうし
た後、上記ステップＳｌに戻り、上記ステップＳ１にお
いて未使用が登録されたＲＡＭ８上の物理ぺージが取得
され、上記ステップＳ３においてアクセス例外を起こし
たフラッシュメモリ７上の物理ページの内容がコピーさ
れ、上記ステップＳ５において上記アドレス変換表のエ
ントリが書き換えられ、上記ステップＳ６において書き
込みフラグ２４がセットされると、アクセス例外アドレ
ス変換処理動作を終了する。

【００４７】以上のようにして、アクセス例外アクセス
変換処理動作が終了した後は、図４に示すように、フラ
ッシュメモリ７側の論理アドレス空間上のオブジェクト
ｂにおけるアクセス例外を起こした論理ページの物理ペ
ージがＲＡＭ８上に割り付けられている。したがって、
書き込み禁止であったオブジェクトｂの最初の論理ペー
ジに対して書き込み処理を継続できるのである。

【００４８】ここで、厳密には、上記フラッシュメモリ
７のブロックサイズと物理ページのサイズが異なる場合
がある。すなわち、昨今の典型的な両サイズは１Ｋバイ
ト〜４Ｋバイト程度で同じであるが、一般的なフラッシ
ュメモリと３２ビットＣＰＵ用ＭＭＵとに関しては、ブ
ロックサイズ≧ページサイズである。もし、ブロックサ
イズ＞ページサイズである場合には、本来はブロックサ
イズ／ページサイズ分の物理ページをＲＡＭ８上に取得
することになるが、本実施の形態においては、簡単のた
めにブロックサイズ＝ページサイズであるとする。

【００４９】次に、上記ガーベジコレクション実行部１
３によって行われるガーベジコレクションについて説明
する。図６は、上記論理アドレス空間上に新規のオブジ
ェクトが割り付けられる際の論理アドレス空間の様子を
示す。ここで、本実施の形態においては、上記ＲＡＭ８
用の論理アドレス空間に設定されたオブジェクトの安定
度は、フラッシュメモリ７用の論理アドレス空間に設定
されたオブジェクトの安定度よりも低く定めてある。以
下、ＲＡＭ８用の論理アドレス空間に配置されるオブジ
ェクトの安定度は「安定度０」と「安定度１」とであ
り、フラッシュメモリ７用の論理アドレス空間に配置さ
れるオブジェクトの安定度は「安定度２」と「安定度
３」とであるとする。

【００５０】図６において、上記ＣＰＵ３によってメモ
リ管理装置２に対して、新規のオブジェクトに対する論
理アドレスの割り付けが要求されると、オブジェクト割
付部１４によって、ＲＡＭ８用の論理アドレス空間上の
安定度０の領域における未使用領域３５の先頭（使用領
域３６の最後尾の次ぎ）のアドレスからの新規オブジェ
クトのメモリ領域が割り付けられる。図７は、上記オブ
ジェクト割付部１４によって行われる論理アドレス空間
上における安定度Ｎの領域に対するメモリ領域割り付け
処理動作のフローチャートである。ステップＳ２１で、
上記論理アドレス空間上における安定度Ｎの未使用領域
に新規オブジェクトのメモリ領域が割り付け可能であ
り、且つ、新規オブジェクトのメモリ領域が割り付けら
れた後の未使用領域に所定の大きさ以上の領域が残るが
否かが判別される。その結果、割り付け可能で、且つ、
所定の大きさ以上の未使用領域が残る場合にはステップ
Ｓ２３に進む。一方、そうでない場合（すなわち、割り
付け不可能である場合か、割り付け後に上記所定の大き
さ以上の領域が残らない場合）にはステップＳ２２に進
む。ステップＳ２２で、上記ガーベジコレクション実行
部１３が起動されて、後に詳述するようにしてガーベジ
コレクション処理が実行される。そうした後、上記ステ
ップＳ２１に戻り、割り付け可能であり、且つ、割り付
け後に上記所定の大きさ以上の領域が残ると判別される
とステップＳ２３に進む。ステップＳ２３で、上記論理
アドレス空間上における安定度Ｎの未使用領域の先頭か
ら新規オブジェクトのメモリ領域が割り付けられる。そ
うした後、メモリ領域割り付け処理動作を終了する。

【００５１】上記メモリ領域割り付け処理動作のフロー
チャートにおける上記ステップＳ２２において実行され
るガーベジコレクション処理は、特に限定されるもので
はないが、本実施の形態においては、スライディング・
コンパクション方式によるガーベジコレクション(Ｗegb
reit,Ｂ：「Ａ generalized compactifiying garbagecol
lector」,Ｃomputer Ｊournal，Ｖol.15，Ｎo.3，pp.20
4−208）によって行うものとする。

【００５２】図８は、上記スライディング・コンパクシ
ョン方式によるガーベジコレクション処理による論理ア
ドレス空間の変遷を示す。このガーベジコレクション処
理は以下の手順によって行われる。 （１）マーク付け 図８（ａ）に示すように、参照関係の基準となり、且
つ、ゴミとなって回収されないような特定のオブジェク
ト（以下、ルートと言う）３７から、参照するオブジェ
クトのポインタ２３（図２参照）を走査して、参照され
ているオブジェクトを順次辿りながら、上記参照されて
いるオブジェクトのマークフラグ２５（図２参照）に
「０」をセットする。尚、上記ルート３７の存在領域
は、何れの論理アドレス空間の何れの安定度の領域であ
っても構わない。図８（ａ）の場合には、ルート３７に
よってオブジェクトＡが参照され、オブジェクトＡによ
ってオブジェクトＣとオブジェクトＥとが参照されてい
る。したがって、オブジェクトＡ，Ｃ，Ｅのマークフラ
グ２５がセットされ、オブジェクトＢ，Ｄのマークフラ
グ２５はセットされない。

【００５３】（２）移動量計算 図８（ｂ）に示すように、マークフラグ２５がセットさ
れないオブジェクトＢ，Ｄは使用されずにゴミとなるの
で、このゴミとなるオブジェクトＢ，Ｄのメモリ領域を
ゴミとはならないオブジェクトＣ，Ｅで詰めるために、
オブジェクトＣ，Ｅの移動量（つまり、論理アドレスの
変化量）を計算する。図８（ｂ）の場合には、上記オブ
ジェクトＣをゴミとなるオブジェクトＢの位置に詰める
ための移動量（論理アドレスの変化量ｘ）と、移動後の
オブジェクトＣの直後の位置にオブジェクトＥを詰める
ための移動量（論理アドレスの変化量ｙ）が計算され
る。

【００５４】（３）ポインタ補正 図８（ｃ）に示すように、上記計算値に基づいて上記参
照関係において参照する側のオブジェクトＡのポインタ
２３の内容を参照される側のオブジェクトＣ，Ｅの移動
後の先頭論理アドレスに補正する。図８（ｃ）の場合に
は、上記オブジェクトＡにおけるオブジェクトＥヘのポ
インタ２３の内容が、移動後のオブジェクトＥの先頭の
論理アドレス（論理アドレスβ―変化量ｙ）に補正され
る。同様に、オブジェクトＡにおけるオブジェクトＣへ
のポインタ２３の内容が、移動後のオブジェクトＣの先
頭の論理アドレス（論理アドレスα―変化量ｘ）に補正
される。

【００５５】（４）詰め合わせ 図８（ｄ）に示すように、上記計算値に基づいて、ゴミ
とはならないオブジェクトＣ，Ｅを実際に詰める。図８
（ｄ）の場合には、上記オブジェクトＣがゴミとなるオ
ブジェクトＢの位置に移動され、移動後のオブジェクト
Ｃの直後の位置にオブジェクトＥが移動される。

【００５６】上述のような手順で行われる上記スライデ
ィング・コンパクション方式によるガーベジコレクショ
ン処理では、論理アドレス空間上における処理の対象と
なる同一安定度の領域に対して２回〜３回の走査を要す
るが、ガーベジコレクション処理後に使用領域が詰め合
わせられるために小さな未使用領域を一つにまとめるこ
とができる。

【００５７】ここで、上記論理アドレス空間上における
ガーベジコレクション処理の対象となる領域が安定度Ｎ
の領域であって、安定度Ｍ（Ｍ＞Ｎ）の領域に存在する
オブジェクトによって参照されているオブジェクトが安
定度Ｎの領域に存在する場合には、安定度Ｎの領域に存
在する上記参照されているオブジェクトも、ガーベジコ
レクションの際に上記ルートとして扱う必要がある。こ
のようなルートを、安定度Ｍの領域に存在するオブジェ
クト群を走査せずに認識するために、本実施の形態にお
いては、以下のようにしている。

【００５８】すなわち、図９に示すように、上記論理ア
ドレス空間管理部ｌｌは、管理表として安定度間参照表
１６を有している。そして、ガーベジコレクション処理
のマーク付けにおいて、フラッシュメモリ７側に在る高
い安定度Ｍ（＝２）の参照オブジェクト３８のポインタ
２３にＲＡＭ８側に在る低い安定度Ｎ（＝０）の被参照
オブジェクト３９の先頭の論理アドレスを書き込む際
に、論理アドレス空間管理部ｌｌの安定度間参照表１６
に参照オブジェクト３８の先頭の論理アドレスと当該論
理アドレスが書き込まれたポインタ２３のワード番号と
を書き込むのである。

【００５９】こうすることによって、上記ＲＡＭ８側の
論理アドレス空間における安定度０の領域に対してガー
ベジコレクション処理を実行する場合には、ガーベジコ
レクション実行部１３は、先ず、論理アドレス空間管理
部ｌｌの安定度間参照表１６を検索して、安定度間参照
表１６で指定された論理アドレスにある参照オブジェク
ト３８の指定されたワード番号のポインタ２３を見る。
こうして、処理対象の安定度０よりも高い安定度Ｍ（＝
１，２，３）の領域に存在する参照オブジェクト３８に
よって参照されているオブジェクトであって、安定度０
の領域に存在する被参照オブジェクト３９を検索する。
そして、得られた被参照オブジェクト３９をガーベジコ
レクション実行の際に上記ルートとして扱うのである。

【００６０】尚、上述のような処理対象となる領域の安
定度Ｎより高い安定度Ｍの領域に存在する参照オブジェ
クト３８によって参照されている被参照オブジェクト３
９を上記ルートとして扱う手法は、従来より知られてい
る（Ｕngar Ｄ：Ｇenerationscavenging ： Ａ non-di
sruptive high-performance storage reclamationalgor
ithm，ACM SIGPLAN Ｎotices vol.19,no.5,1987）。

【００６１】上記ガーベジコレクション実行部１３は、
上述のようにしてガーベジコレクション処理を行うので
あるが、例えば安定度０の領域に対してガーベジコレク
ション処理を行った結果、あまり回収が行われず、十分
な未使用領域を回復できなかったと判定した場合には、
一つ上の安定度「１」の領域を加えた安定度０の領域と
安定度１の領域とにガーベジコレクション処理を行うの
である。それでも十分な未使用領域を回復できない場合
には、さらに高い安定度の領域を加えてガーベジコレク
ション処理を行うのである。図１０は、上記ガーベジコ
レクション実行部１３によって行われるより高い安定度
の領域を順次加えて行われるガーベジコレクション処理
動作のフローチャートである。

【００６２】ステップＳ３１で、上記ＲＡＭ８用の論理
アドレス空間における安定度０の領域に対してガーベジ
コレクション・サブルーチンが実行される。ステップＳ
３２で、上記ステップＳ３１の結果、十分な未使用領域
が回復できたか否かが判別される。その結果、十分な未
使用領域が回復できなかった場合にはステップＳ３３に
進み、回復できた場合にはガーベジコレクション処理動
作を終了する。ステップＳ３３で、上記ＲＡＭ８用の論
理アドレス空間における安定度０および安定度１の領域
に対してガーベジコレクション・サブルーチンが実行さ
れる。ステップＳ３４で、上記ステップＳ３３の結果、
十分な未使用領域が回復できたか否かが判別される。そ
の結果、十分な未使用領域が回復できなかった場合には
ステップＳ３５に進み、回復できた場合にはガーベジコ
レクション処理動作を終了する。ステップＳ３５で、上
記ＲＡＭ８用の論理アドレス空間における安定度０およ
び安定度１の領域と、フラッシュメモリ７用の論理アド
レス空間における安定度２の領域とに対して、ガーベジ
コレクション・サブルーチンが実行される。ステップＳ
３６で、上記ステップＳ３５の結果、十分な未使用領域
が回復できたか否かが判別される。その結果、十分な未
使用領域が回復できなかった場合にはステップＳ３７に
進み、回復できた場合にはガーベジコレクション処理動
作を終了する。ステップＳ３７で、上記ＲＡＭ８用の論
理アドレス空間における安定度０および安定度１の領域
と、フラッシュメモリ７用の論理アドレス空間における
安定度２および安定度３の領域とに対して、ガーベジコ
レクション・サブルーチンが実行される。そうした後、
ガーベジコレクション処理動作を終了する。

【００６３】上述のように、本実施の形態においては、
上記ガーベジコレクション実行部１３は、最も安定度の
低い領域からガーベジコレクション処理を行い、十分な
未使用領域が回復できなかった場合には、十分な未使用
領域が回復できるまで順次高い安定度の領域を加えてガ
ーベジコレクション処理を続行するようにしている。し
たがって、常時総ての論理アドレス空間に対して一様に
ガーベジコレクション処理を実行する場合に比して、ガ
ーベジコレクション処理の回数とガーベジコレクション
処理時間とを短縮でき、ガーベジコレクション処理によ
る他のシステムの実行の中断時間を短縮できるのであ
る。また、上述のごとく、安定度０と安定度１との低い
安定度の領域はＲＡＭ８用の論理アドレス空間に配置さ
れる一方、安定度２と安定度３との高い安定度の領域は
フラッシュメモリ７用の論理アドレス空間に配置されて
いる。したがって、ガーベジコレクションに付随して実
行される書き換えは、書き換え回数制限型メモリではな
いＲＡＭ８に対して頻繁に行われ、書き換え回数制限型
メモリであるフラッシュメモリ７に対しては少ない回数
で行われることになる。したがって、フラッシュメモリ
７の長寿命化が図られるのである。また、大部分のオブ
ジェクトが比較的短時間にゴミになる性質があることに
着目して、安定度の低い領域（つまり、安定度の低いオ
ブジェクト群）に対して高い頻度でガーベジコレクショ
ン処理を行うことによって、オブジェクトの回収率を上
げてメモリの利用効串を高めることができるのである。

【００６４】上記安定度設定部１２は、総ての論理アド
レス空間における各安定度Ｎ（Ｎ＝０，１，２）の領域
毎に、ガーベジコレクション実行部１３によって実行さ
れたガーベジコレクション処理回数を管理している。そ
して、安定度Ｎの領域に対するガーベジコレクション処
理回数が安定度Ｎ毎に設定されている所定回数Ｘ_N（Ｎ
＝１，２，３）に達すると、その安定度Ｎの領域に存在
するガーベジコレクション処理に付随する書き換え以外
の書き込みも上記回収も行われなかったオブジェクトの
安定度を（Ｎ＋１）に設定する。ここで、本実施の形態
においては、上述したごとく、同じ安定度を有するオブ
ジェクトは同一論理アドレス空間上に連続して配置する
ようにしている。したがって、上述のように安定度Ｎの
領域中に在って安定度が（Ｎ＋１）となったオブジェク
トは、安定度（Ｎ＋１）の領域に移動させる必要があ
る。そこで、ガーベジコレクション実行部１３によって
行われる実際のガーベジコレクション処理では、図８に
示す手順に加えて、当該ガーベジコレクション処理後に
安定度が（Ｎ＋１）になるオブジェクトを安定度（Ｎ＋
１）の領域に移動させる手順を要する。

【００６５】図ｌｌは、図１０に示すガーベジコレクシ
ョン処理動作のフローチャートにおける上記ステップＳ
３１，Ｓ３３，Ｓ３５，Ｓ３７において実行されるガー
ベジコレクション・サブルーチンのフローチャートであ
る。図１０に示すガーベジコレクション処理動作のフロ
ーチャートにおいて、安定度０の領域に対するガーベジ
コレクション処理が指令されるが、上記ステップＳ３
２，Ｓ３４，Ｓ３６において十分な未使用領域を回復で
きなかったと判別されると、ガーベジコレクション・サ
ブルーチンがスタートする。

【００６６】ステップＳ４１で、上記ルート３７から、
ポインタ２３を走査して参照されているオブジェクトを
順次辿りながら、参照されているオブジェクトのマーク
フラグ２５がセットされる。ステップＳ４２で、ゴミに
なるオブジェクトのメモリ領域をゴミにならないオブジ
ェクトで詰めるためのオブジェクトの移動量が計算され
る。ステップＳ４３で、上記論理アドレス空間管理部ｌ
ｌの管理情報を参照して、安定度が（Ｎ＋１）となるオ
ブジェクトが存在するか否かが判別される。その結果、
存在する場合にはステップＳ４４に進む一方、存在しな
い場合にはステップＳ４７に進む。

【００６７】ステップＳ４４で、上記ステップＳ４３に
おいて安定度が（Ｎ＋１）となると判別された一つのオ
ブジェクトの移動量が、安定度（Ｎ＋１）の領域におけ
る未使用領域の先頭への移動量に更新される。ステップ
Ｓ４５で、上記ステップＳ４３において安定度が（Ｎ＋
１）となると判別された総てのオブジェクトに対する移
動量の更新が柊了したか否かが判別される。その結果、
終了していればステップＳ４７に進み、終了していなけ
ればステップＳ４６に進む。ステップＳ４６で、上記安
定度（Ｎ＋１）の領域に次のオブジェクトを移動可能な
だけの未使用領域が存在するが否かが判別される。その
結果、存在する場合には上記ステップＳ４４に戻って次
のオブジェクトの移動量更新に移行する。一方、存在し
ない場合には、ステップＳ４７に進む。

【００６８】ステップＳ４７で、上記ステップＳ４２に
おいて算出された移動量あるいは上記ステップＳ４４に
おいて更新された移動量に基づいて、参照オブジェクト
のポインタ２３の内容が被参照オブジェクトの移動後の
先頭論理アドレスに補正される。ステップＳ４８で、上
記算出された移動量あるいはその後更新された移動量に
基づいて、ゴミとはならないオブジェクトの詰め合わせ
が行われる。その際に、安定度（Ｎ＋１）の領域に移動
すべきオブジェクトがある場合には、オブジェクト割付
部１４が起動されて、該当するオブジェクトの割り付け
直しが行われる。ステップＳ４９で、上記ステップＳ４
６における判別結果に基づいて、上記ステップＳ４３に
おいて安定度が（Ｎ＋１）となると判別された総てのオ
ブジェクトが安定度（Ｎ＋１）の領域に移動できるか否
かが判別される。その結果、総てのオブジェクトが移動
できればステップＳ５０に進み、そうでなければステッ
プＳ５１に進む。

【００６９】ステップＳ５０で、例えば、（処理後の未
使用領域／処理前の未使用領域）の値と所定確との比較
によって、上記ステップＳ４８の結果、十分な未使用領
域が回復できたか否かが判別される。その結果、十分な
未使用領域が回復できなかった場合にはステップＳ５１
に進み、回復できた場合にはガーべジコレクション・サ
ブルーチンを終了して、図１０に示すガーベジコレクシ
ョン処理動作のフローチャートにリターンする。ステッ
ブＳ５１で、上記ガーベジコレクション実行部１３内に
設定された回復フラグに「１」がセットされて、十分な
未使用領域が回復できなかったことが表示される。そう
した後、ガーベジコレクション・サブルーチンを終了し
て、図１０に示すガーベジコレクション処理動作のフロ
ーチャートにリターンする。

【００７０】上述のように、上記ガーベジコレクション
・サブルーチンにおいては、安定度（Ｎ＋１）の領域に
次のオブジェクトを移動可能なだけの未使用領域が存在
しない場合には、移動量の更新を中止して、そのまま詰
め合わせを行うようにしている。したがって、そのよう
な場合には、安定度Ｎの領域内に安定度（Ｎ＋１）のオ
ブジェクトが混在することなる。しかしながら、そのよ
うな場合には、十分な未使用領域が回復できなかったと
して、上記回復フラグに「１」をセットするので、図１
０に示すガーベジコレクション処理動作のフローチャー
トにリターンした際に、上記ステップＳ３２，Ｓ３４，
Ｓ３６において上記回復フラグが参照されて、十分な未
使用領域が回復できなかったと判別される。その結果、
次のステップで、安定度（Ｎ＋１）のオブジェクトが混
在している安定度Ｎの領域と安定度（Ｎ＋１）の領域と
に対してガーベジコレクション・サブルーチンが実行さ
れて、安定度（Ｎ＋１）の領域に対する未使用領域の回
復が行われるのである。

【００７１】上述のように、本実施の形態においては、
上記オブジェクトに対して「ガーベジコレクションによ
る回収されにくさ」と「書き込みの起こりにくさ」とを
合わせ持つ「安定度」を設定する安定度設定部１２を有
する。また、メモリ部５にデータ用メモリとしてのフラ
ッシュメモリ（書き換え回数制限メモリ）７とＲＡＭ８
とを設け、オブジェクト割付部１４によって、フラッシ
ュメモリ７側の論理アドレス空間上には安定度が「０」
と「１」のオブジェクトを割り付ける一方、ＲＡＭ８側
の論理アドレス空間上には安定度が「２」と「３」のオ
ブジェクトを割り付ける。

【００７２】そして、上記フラッシュメモリ７側の論理
アドレス空間上およびＲＡＭ８側の論理アドレス空間上
に割り付けられたオブジェクトに対して、ＣＰＵ３から
書き込みが要求されると、ＭＭＵ４によって、アドレス
変換表格納部９に格納されたアドレス変換表が参照され
てアドレス変換が行われて、図３に示すように、論理ア
ドレス空間上における当該オブジェクトの論理ページが
物理アドレス空間上に写像されて、この写像された物理
ページに従って書き込みが行われる。

【００７３】また、上記ＭＭＵ４のアクセス例外検知手
段１５によって、ＣＰＵ３から要求された書き込みがア
クセス例外であることが検知されると、ＭＭＵ４は、書
き込み禁止の論理ページが写像されたフラッシュメモリ
７上の物理ページの内容をＲＡＭ８上の物理アドレス空
間における未使用ページにコピーし、このコピーされた
物理ページを写像元のフラッシュメモリ７側の論理ペー
ジに対応付け直す。このようにして、書き込み禁止であ
った論理ページを書き込み可能にすることによって、以
後の当該書き込み禁止のオブジェクトに対する書き込み
はＲＡＭ８上の物理ページに対して行われることとな
る。その結果、書き換え回数制限型のフラッシュメモリ
７に対する書き込み回数が減少されることになる。

【００７４】ここで、上記ＣＰＵ３によって新規のオブ
ジェクトに対する論理アドレスの割り付けが要求される
と、安定度設定部１２によって、上記新規オブジェクト
の安定度が最小値「０」に設定され、オブジェクト割付
部１４によってＲＡＭ８用の論理アドレス空間上の安定
度０の領域の未使用領域の先頭に割り付けられる。その
際に、上記安定度０の領域に新規オブジェクトを割り付
けるだけの未使用領域が存在しない場合には、ガーベジ
コレクション実行部１３によって、最も安定度の低いＲ
ＡＭ８の安定度０の領域に対してガーベジコレクション
が実行される。そして、十分な未使用領域が回復できな
い場合には、十分な未使用領域が回復できるまで順次高
い安定度の領域を加えてガーベジコレクション処理を繰
り返すのである。

【００７５】こうして、大部分のオブジェクトが比較的
短時間にゴミになる性質があることに着目して、ＲＡＭ
８側の安定度の低い領域に対して高い頻度でガーベジコ
レクションを行うことによって、以下のような効果を奏
することができるのである。 ・ガーベジコレクション処理の回数と時間とを短縮で
き、他のシステムの実行の中断時間を短縮できる。 ・ガーベジコレクションに付随する書き換えを書き換え
回数制限型メモリであるフラッシュメモリ７に対して少
ない回数で行って、フラッシュメモリ７の長寿命化を図
ることができる。 ・オブジェクトの回収率を上げてメモリの利用効率を高
めることができる。

【００７６】また、上記安定度設定部１２は、安定度Ｎ
の領域に対するガーベジコレクション処理回数が所定回
数Ｘ_N（Ｎ＝１，２，３）に達すると、その安定度Ｎの
領域に存在する書き込み（ガーベジコレクション処理に
付随する書き換え以外の書き込み）も上記回収も行われ
なかったオブジェクトの安定度を（Ｎ＋１）に設定す
る。そして、ガーベジコレクション実行部１３は、安定
度Ｎの領域に対してガーベジコレクション処理を行う際
に安定度が（Ｎ＋１）に変更されるオブジェクトがあれ
ばそのオブジェクトを安定度（Ｎ＋１）の領域に移動す
る。こうして、上記安定度毎に設定された所定回数のガ
ーベジコレクション処理が行われる間に上記書き込みが
行われない比較的安定したオブジェクトの安定度を増加
することによって、安定度が「２」以上と高いために書
き込み頻度が少ないと予測されるオブジェクトのみがフ
ラッシュメモリ７側に設定でき、フラッシュメモリ７の
更なる長寿命化を図ることができる。

【００７７】また、書き込まれる可能性の高いオブジェ
クトは、被参照オブジェクトが変化することによってゴ
ミを発生する可能性が高い。そこで、上記安定度が
「２」であるオブジェクトは、所定回数Ｘ２にわたるガ
ーベジコレクション処理によって回収されなくとも、そ
の間に書き込みが行われた場合には安定度は「３」には
ならないようにして最もガーベジコレクション処理の頻
度の高い安定度「２」の領域に止め置くのである。つま
り、フラッシュメモリ７側にあるオブジェクトであって
も書き込まれる可能性の高いオブジェクトは最もガーべ
ジコレクション処理の頻度の高い領域に止め置くことに
よって、発生されたゴミがガーべジコレクション処理に
よって回収され易くなって、オブジェクトの回収率を更
に上げることができるのである。

【００７８】なお、上述したメモリ管理装置として機能
させるために、その処理を実行するためのプログラムを
フロッピーディスクやＣＤＲＯＭ等のコンピュータ読み
取り可能な記録媒体に予め記録させておいて、必要に応
じてコンピュータにインストールさせて用いてもよい。

【００７９】

【発明の効果】以上より明らかなように、請求項１に係
る発明のメモリ管理装置または請求項７に係る発明のコ
ンピュータ読み取り可能な記録媒体によれば、書き換え
回数制限型メモリあるいはＲＡＭに対する新規オブジェ
クトの割り付け時、および、ガーベジコレクション実行
部によるガーベジコレクション処理実行時に、安定度設
定部によって、オブジェクトに対して、上記ガーベジコ
レクション処理によって回収されず且つ当該ガーベジコ
レクション処理時まで書き込みが行われなかった場合に
増加する安定度を設定し、オブジェクト割付部によっ
て、上記設定された安定度が所定値以下であるオブジェ
クトをＲＡＭに割り付ける一方、上記安定度が上記所定
値より高いオブジェクトを上記書き換え回数制限型メモ
リに割り付けるので、ガーベジコレクション処理によっ
て回収されにくく、且つ、書き込みが起こりにくいオブ
ジェクト群が上記書き換え回数制限型メモリに割り付け
られる。したがって、この発明によれば、上記書き換え
回数制限型メモリに対する書き換えや書き込みを押さえ
て、上記書き換え回数制限型メモリの長寿命化を図るこ
とができる。

【００８０】また、請求項２に係る発明のメモリ管理装
置におけるガーベジコレクション実行部は、上記安定度
の高いオブジェクトが割り付けられている領域よりも、
上記安定度の低いオブジェクトが割り付けられている領
域に対して、高い頻度で上記ガーベジコレクション処理
を行うので、上記ガーベジコレクション処理に付随する
書き換えは、上記安定度の低いオブジェクトが割り付け
られている上記ＲＡＭに対して頻繁に行われることにな
る。したがって、上記書き換え回数制限型メモリの更な
る長寿命化を図ることができる。また、上記安定度が低
く、ゴミ化しやすいオブジェクト群に対して高い頻度で
上記ガーベジコレクション処理を行うことによって、オ
ブジェクトの回収率を上げてメモリの利用効率を高める
ことができる。さらに、上記安定度の低いオブジェクト
が割り付けられている領域に対して高い頻度で上記ガー
ベジコレクション処理が行われるので、全領域に対して
一様に上記ガーべジコレクション処理を実行する場合よ
りも処理時間を短縮でき、他の処理の中断時間を短縮で
きる。したがって、利用者に対する応答性がよくなる。

【００８１】また、請求項３に係る発明のメモリ管理装
置におけるガーベジコレクション実行部は、所定の大き
さ以上の未使用領域が得られるまで、最も低い安定度の
オブジェクト群が割り付けられている領域に順次高い安
定度のオブジェクト群が割り付けられている領域を加え
て上記ガーベジコレクション処理を行うので、上記安定
度が低い程上記ガーベジコレクション処理の回数が多く
なる。したがって、上記安定度の高いオブジェクトが割
り付けられている上記書き換え回数制限型メモリに対す
る上記ガーベジコレクション処理に付随する書き換えを
少なくして、上記書き換え回数制限型メモリの更なる長
寿命化を図ることができる。また、ゴミ化しやすい低安
定度のオブジェクト群に対する上記ガーベジコレクショ
ン処理の頻度を上げてオブジェクトの回収率を高めるこ
とができる。さらに、上記未使用領域が所定の大きさよ
り少ないメモリの全領域に対して一様にガーベジコレク
ション処理を行う場合よりも処理時間を短縮して、他の
処理の中断時間を短縮できる。

【００８２】また、請求項４に係る発明のメモリ管理装
置における安定度設定部は、上記新規オブジェクトの割
り付け時には、新規オブジェクトの安定度を最小値に設
定するので、殆どが短期間のうちにゴミと化する新規オ
ブジェクトを上記ガーベジコレクション処理回数の多い
上記ＲＡＭに割り付けて上記ガーベジコレクション処理
によって回収することができる。したがって、メモリの
利用効率を高めることができる。さらに、上記ガーベジ
コレクション処理実行時には、ガーベジコレクション処
理回数が所定回数になったオブジェクトであって上記所
定回数のガーベジコレクション処理の間に書き込みが行
われなかったオブジェクトの安定度を所定値だけ増加す
るので、上記書き換え回数制限型メモリには書き込みが
行われないと予測される安定したオブジエクトが割り付
けられることになる。したがって、上記書き換え回数制
限型メモリの更なる長寿命化を図ることができる。

【００８３】また、請求項５に係る発明のメモリ管理装
置におけるアドレス変換部は、アクセス例外検知手段に
よってアクセス例外が検知された場合には、書き込みが
要求された論理アドレス空間上の論理ページが写像され
た上記書き換え回数制限型メモリの物理アドレス空間上
の物理ページの内容をＲＡＭの物理アドレス空間上の未
使用の物理ページにコピーし、このコピーされた上記Ｒ
ＡＭの物理ページを上記書き込みが要求された論理アド
レス空間上の論理ページに対応付けるので、書き込みが
要求された論理アドレス空間上の論理ページを上記ＲＡ
Ｍの物理アドレス空間上の物理ページに対応付け直すこ
とができる。したがって、以後は、上記書き換え回数制
限型メモリ上における書き込み禁止ページに対する書き
込みが可能となる。つまり、上記書き換え回数制限型メ
モリを通常のデータ用メモリとして使用できるのであ
る。

【００８４】さらに、上述の結果、上記書き換え回数制
限型メモリ上における論理ページに発生した書き込みが
上記ＲＡＭに対して行われることなり、結果として上記
書き換え回数制限型メモリの更なる長寿命化を図ること
ができるのである。

【００８５】また、請求項６に係る発明のメモリ管理装
置は、上記書き換え回数制限型メモリとしてフラッシュ
メモリを用いるので、消費電力の低下を図ることができ
る。

【図面の簡単な説明】

【図１】この発明のメモリ管理装置が登載された計算機
システムにおけるブロック図である。

【図２】オブジェクトの構成を示す概念図である。

【図３】図１におけるＭＭＵによって行われるアドレス
変換の一例の様子を示す概念図である。

【図４】アクセス例外時におけるアドレス変換の様子を
示す概念図である。

【図５】図１におけるＭＭＵによって行われるアクセス
例外アドレス変換処理動作のフローチャートである。

【図６】新規のオブジェクトが割り付けられる際の論理
アドレス空間の様子を示す概念図である。

【図７】図１におけるオブジェクト割付部によって行わ
れるメモリ領域割り付け処理動作のフローチャートであ
る。

【図８】スライディング・コンパクション方式によるガ
ーベジコレクション処理による論理アドレス空間の変遷
を示す図である。

【図９】図１における論理アドレス空間管理部の安定度
間参照表の説明図である。

【図１０】図１におけるガーベジコレクション実行部に
よって行われるガーベジコレクション処理動作のフロー
チャートである。

【図ｌｌ】図１０のガーべジコレクション処理動作中に
おいて実行されるガーベジコレクション・サブルーチン
のフローチャートである。

【符号の説明】

１…計算機システム、 ２…メモリ管理装
置、３…ＣＰＵ、 ４…ＭＭＵ、
５…メモリ部、 ７…フラッシュメ
モリ、８…ＲＡＭ、 ９…アクセ
ス変換表格納部、１０…物理アドレス空間管理部、
ｌｌ…論理アドレス空間管理部、１２…安定度設定部、
１３…ガーベジコレクション実行部、１
４…オブジェクト割付部、 １５…アクセス例外
検知手段、１６…安定度間参照表、 ２３…
ポインタ、２４…書き込みフラグ、 ２５…
マークフラグ、３７…ルート。

Claims (7)

【特許請求の範囲】
1. 【請求項１】 書き換え回数制限型メモリとランダム・
   アクセス・メモリと上記両メモリの論理アドレスを物理
   アドレスに変換するアドレス変換部を有するシステムの
   メモリ管理装置であって、 上記書き換え回数制限型メモリあるいはランダム・アク
   セス・メモリの未使用領域が所定の大きさより小さい場
   合に、この未使用領域が小さいメモリに対してガーベジ
   コレクション処理を行うガーベジコレクション実行部
   と、 上記各メモリに対するデータの割り付け単位を表す情報
   であるオブジェクトに対して、上記各メモリに対する新
   規オブジェクトの割り付け時、あるいは、上記ガーベジ
   コレクション処理実行時に、上記ガーベジコレクション
   処理によって回収されず且つ当該ガーベジコレクション
   処理時まで書き込みが行われなかった場合に増加する安
   定度を設定する安定度設定部と、 上記各メモリに対する新規オブジェクトの割り付け時、
   あるいは、上記ガーベジコレクション処理実行時に、上
   記安定度設定部によって設定された安定度が所定値以下
   のオブジェクトを上記ランダム・アクセス・メモリに割
   り付ける一方、上記安定度が上記所定値より高いオブジ
   ェクトを上記書き換え回数制限型メモリに割り付けるオ
   ブジェクト割付部を備えたことを特徴とするメモリ管理
   装置。
2. 【請求項２】 請求項１に記載のメモリ管理装置におい
   て、 上記ガーベジコレクション実行部は、上記未使用領域が
   所定の大きさより小さいメモリに関して、上記安定度の
   高いオブジェクトが割り付けられている領域よりも、上
   記安定度の低いオブジェクトが割り付けられている領域
   に対して、高い頻度で上記ガーベジコレクション処理を
   行うようになっていることを特徴とするメモリ管理装
   置。
3. 【請求項３】 請求項２に記載のメモリ管理装置におい
   て、 上記ガーべジコレクション実行部は、上記未使用領域が
   所定の大きさより小さいメモリに関して、上記所定の大
   きさ以上の未使用領域が得られるまで、最も低い安定度
   のオブジェクト群が割り付けられている領域に順次高い
   安定度のオブジェクト群が割り付けられている領域を加
   えて上記ガーベジコレクション処理を行うようになって
   いることを特徴とするメモリ管理装置。
4. 【請求項４】 請求項１に記載のメモリ管理装置におい
   て、 上記安定度設定部は、 上記新規オブジェクトの割り付け時には、新規オブジェ
   クトの安定度を最小値に設定し、 上記ガーベジコレクション処理実行時には、当該ガーベ
   ジコレクション処理によって、処理対象領域に在る同一
   安定度のオブジェクトに対するガーベジコレクション処
   理回数が上記安定度になってから所定回数になった場合
   に、上記処理対象領域に在るオブジェクトであって上記
   所定回数のガーベジコレクション処理が行われる間に書
   き込みが行われなかったオブジェクトの安定度を所定値
   だけ増加するようになっていることを特徴とするメモリ
   管理装置。
5. 【請求項５】 請求項１に記載のメモリ管理装置におい
   て、 上記アドレス変換部は、 上記書き換え回数制限型メモリ上におけるアドレス変換
   の単位領域としてのべージであって書き込み禁止である
   べージに対して書き込みが要求されて発生するアクセス
   例外を検知するアクセス例外検知手段を備えて、 上記アクセス例外検知手段によって上記アクセス例外が
   検知された場合には、書き込みが要求された論理アドレ
   ス空間上の論理ページが写像された上記書き換え回数制
   限型メモリの物理アドレス空間上の物理ページの内容
   を、上記ランダム・アクセス・メモリの物理アドレス空
   間上の未使用の物理べージにコピーし、このコピーされ
   た上記ランダム・アクセス・メモリの物理べージを上記
   書き込みが要求された論理ページに対応付けるようにな
   っていることを特徴とするメモリ管理装置。
6. 【請求項６】 請求項１乃至請求項５の何れか、一つに
   記載のメモリ管理装置において、 上記書き換え回数制限型メモリは、フラッシュメモリで
   あることを特徴とするメモリ管理装置。
7. 【請求項７】 書き換え回数制限型メモリとランダム・
   アクセス・メモリと上記両メモリの論理アドレスを物理
   アドレスに変換するアドレス変換部を有するシステムの
   メモリ管理装置として機能させるためのプログラムを記
   録したコンピュータ読み取り可能な記録媒体であって、 上記書き換え回数制限型メモリあるいはランダム・アク
   セス・メモリの未使用領域が所定の大きさより小さい場
   合に、この未使用領域が小さいメモリに対してガーベジ
   コレクション処理を行うガーベジコレクション実行部
   と、 上記各メモリに対するデータの割り付け単位を表す情報
   であるオブジェクトに対して、上記各メモリに対する新
   規オブジェクトの割り付け時、あるいは、上記ガーベジ
   コレクション処理実行時に、上記ガーベジコレクション
   処理によって回収されず且つ当該ガーベジコレクション
   処理時まで書き込みが行われなかった場合に増加する安
   定度を設定する安定度設定部と、 上記各メモリに対する新規オブジェクトの割り付け時、
   あるいは、上記ガーベジコレクション処理実行時に、上
   記安定度設定部によって設定された安定度が所定値以下
   のオブジェクトを上記ランダム・アクセス・メモリに割
   り付ける一方、上記安定度が上記所定値より高いオブジ
   ェクトを上記書き換え回数制限型メモリに割り付けるオ
   ブジェクト割付部として機能させるためのプログラムを
   記録したコンピュータ読み取り可能な記録媒体。