(57)【要約】      （修正有）【課題】１つのヒープ領域におけるデフラグメンテーションを簡単な構成で効率よくより高速に行う。【解決手段】第１段階として、２領域ＳＺ１及びＳＺ２中サイズが小さい方の領域内に存在する使用中領域を先に再配置する（Ｓ２２、Ｓ２３、Ｓ３３）。第２段階の処理（Ｓ２４〜Ｓ２７、Ｓ３４〜Ｓ３７）により、２領域ＳＺ１及びＳＺ２中サイズが小さい方の領域内にさらに、サイズが大きい方の領域内の使用中領域を再配置する。第３段階で、可能であれば（Ｓ２８、Ｓ３８）最大サイズＳＺumの使用中領域Ｅを２領域ＳＺ１及びＳＺ２中サイズが小さい方の領域内に再配置する。【選択図】図２
2010277268.tif 000002
【特許請求の範囲】
【請求項１】
物理メモリ上のヒープ領域を管理するメモリ管理装置において、
該ヒープ領域における複数の使用中領域のうち最大サイズのものの両端のそれぞれから該ヒープ領域の同一側端までの２領域中サイズが小さい方の領域内に、該最大サイズの使用中領域以外の使用中領域の全部又は一部を、所定順に再配置してデフラグメンテーションを行う管理手段、
を有することを特徴とするメモリ管理装置。
【請求項２】
該管理手段は、第１段階として、該２領域中サイズが小さい方の領域内に存在する使用中領域を先に、該最大サイズの使用中領域にアドレス上近い方から順に再配置する、
ことを特徴とする請求項１に記載のメモリ管理装置。
【請求項３】
該管理手段はさらに、該第１段階の再配置完了後に第２段階として、該２領域中サイズが大きい方の領域内の使用中領域を所定順に、該２領域中サイズが小さい方の領域内の未使用中領域に再配置し、再配置できないものは、該２領域中サイズが大きい方の領域内に、該最大サイズの使用中領域にアドレス上近い方から順に再配置する、
ことを特徴とする請求項２に記載のメモリ管理装置。
【請求項４】
該管理手段はさらに、該第２段階の再配置完了後に、該２領域中サイズが小さい方の領域内の未使用中領域のサイズが、該最大サイズの使用中領域のそれ以上であれば、該最大サイズの使用中領域をこの未使用中領域内に再配置する、
ことを特徴とする請求項３に記載のメモリ管理装置。
【請求項５】
請求項１乃至４のいずれか１つに記載のメモリ管理装置を備えたことを特徴とするワンチップマイクロコンピュータ。
【請求項６】
請求項５に記載のワンチップマイクロコンピュータと、
該ワンチップマイクロコンピュータにより制御される制御対象と、
を備えたことを特徴とする組込システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリデフラグメンテーションを行うメモリ管理装置及びこれを備えたワンチップマイクロコンピュータ並びに組込システムに関する。
【背景技術】
【０００２】
組込システムでは、ワンチップマイクロコンピュータを用いてリアルタイム処理を行っている。
【０００３】
一方、メモリを効率良く使用するために、ヒープ領域にメモリを動的に確保し、不要になったら解放することが行われている。
【０００４】
このため、メモリのフラグメンテーションが生じ、特に補助記憶装置を用いない組込システムでは、メモリデフラグメンテーションを高速に行って、リアルタイム性を確保する必要がある。
【０００５】
下記特許文献１では、この要求を満たすために、複数のメモリプールを用いている。
【特許文献１】特開２００２−３２２３４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、複数のメモリプールを使用すると、それぞれの空き領域を連続させて使用することができないので、メモリ使用効率が低下する。特にワンチップマイクロコンピュータでは、メモリの記憶容量が比較的少ないので、メモリ使用効率を高める必要がある。
【０００７】
本発明の目的は、このような問題点に鑑み、１つのヒープ領域におけるデフラグメンテーションを簡単な構成で効率よくより高速に行うことが可能なメモリ管理装置及びこれを備えたワンチップマイクロコンピュータ並びに組込システムを提供することにある。
【課題を解決するための手段】
【０００８】
本発明の第１態様では、物理メモリ上のヒープ領域を管理するメモリ管理装置において、
該ヒープ領域における複数の使用中領域のうち最大サイズのものの両端のそれぞれから該ヒープ領域の同一側端までの２領域中サイズが小さい方の領域内に、該最大サイズの使用中領域以外の使用中領域の全部又は一部を、所定順に再配置してデフラグメンテーションを行う管理手段を有する。
【０００９】
本発明によるメモリ管理装置の第２態様では、第１態様において、該管理手段は、第１段階として、該２領域中サイズが小さい方の領域内に存在する使用中領域を先に、該最大サイズの使用中領域にアドレス上近い方から順に再配置する。
【００１０】
本発明によるメモリ管理装置の第３態様では、第２態様において、該管理手段はさらに、該第１段階の再配置完了後に第２段階として、該２領域中サイズが大きい方の領域内の使用中領域を所定順に、該２領域中サイズが小さい方の領域内の未使用中領域に再配置し、再配置できないものは、該２領域中サイズが大きい方の領域内に、該最大サイズの使用中領域にアドレス上近い方から順に再配置する。
【００１１】
本発明によるメモリ管理装置の第４態様では、第３態様において、該管理手段はさらに、該第２段階の再配置完了後に、該２領域中サイズが小さい方の領域内の未使用中領域のサイズが、該最大サイズの使用中領域のそれ以上であれば、該最大サイズの使用中領域をこの未使用中領域内に再配置する。
【発明の効果】
【００１２】
上記第１態様の構成によれば、最大サイズの使用領域を再配置しなくてもよく、しかも、２領域中サイズが小さい方の領域内にこれ以外の使用中領域の全部又は一部を再配置するので、簡単な処理で比較的大きな空き領域を効率よく短時間で得ることができ、リアルタイム処理を確保可能となるという効果を奏する。換言すれば、よりパフォーマンスの低い安価なプロセッサを用いることが可能となるという効果を奏する。
【００１３】
上記第２態様の構成によれば、第１段階として、該２領域中サイズが小さい方の領域内に存在する使用中領域を先に再配置するので、再配置可能か否かを判断することなく確実に再配置でき、処理効率が高いという効果を奏する。
【００１４】
上記第３態様の構成によれば、該第１段階の再配置完了後の第２段階の処理により、該２領域中サイズが小さい方の領域内にさらに該２領域中サイズが大きい方の領域内の使用中領域が再配置されるので、より大きな空き領域を得ることができるという効果を奏する。
【００１５】
上記第４態様の構成によれば、該第２段階の再配置完了後に、可能であれば該最大サイズの使用中領域が該２領域中サイズが小さい方の領域内に再配置されるので、さらに大きな空き領域を効率よく簡単に得ることができるという効果を奏する。
【００１６】
本発明の他の目的、構成及び効果は以下の説明から明らかになる。
【実施例１】
【００１７】
図６は、本発明が適用される組込システム１の概略ブロック図である。
【００１８】
この組込システム１は、制御対象２をワンチップマイクロコンピュータ１０でリアルタイム制御している。
【００１９】
ワンチップマイクロコンピュータ１０では、ＭＰＵ１１がバス１２を介してＲＯＭ１３、ＲＡＭ１４、周辺回路１５及びＩ/Ｏインタフェース１６と結合されている。
【００２０】
ＲＯＭ１３は、例えばフラッシュメモリであり、ＯＳ（オペレーティングシステム）及びアプリケーションが格納されている。ＲＡＭ１４は、ワークエリアとして用いられる。高速処理のため、起動時にＲＯＭ１３内のプログラムの一部又は全部を、ＲＡＭ１４上にコピーして、ＲＡＭ１４内からアプリケーションを起動してもよい。周辺回路１５は、ＡＤＣ（アナログ／デジタルコンバータ）、ＤＡＣ（デジタル／アナログコンバータ）及びＤＭＡＣ（ダイレクトメモリアクセスコントローラ）などを備えている。Ｉ/Ｏインタフェース１６は、制御対象２に結合されている。
【００２１】
図５は、メモリデフラグメンテーションに関係した部分の機能ブロック図である。
【００２２】
ＲＯＭ１３内のアプリケーションは、その一部がメインスレッド２０として機能し、ＲＡＭ１４内に子スレッド２１〜２３を動的に生成し、これらで２内の複数部を並列にリアルタイム制御する。スレッド２０〜２３はそれぞれ、ＯＳのメモリ管理部３０を介して、ヒープ領域３１内にメモリ（記憶領域）を動的に確保したり解放したりする。
【００２３】
メモリ管理部３０は、このメモリを確保する際に、メモリ管理リスト３２の未使用リスト３２１を参照して使用中領域を決定し、その先頭アドレスとサイズとを記入した要素を、使用中リスト３２２に連結する。メモリを解放する際には、使用中リスト３２２中の対応する要素を抜き出して未使用リスト３２１に連結する。これらリストは当業者に周知のものであり、その詳細説明を省略する。また、アドレスが連続する未使用領域のリスト要素を、１つの要素に纏める。メモリデフラグメンテーション部３０３は、メモリ割当部３０１で用いられる。
【００２４】
図１は、メモリ割当部３０１による処理を示す概略フローチャートである。以下、括弧内は図中のステップ識別符号である。
【００２５】
（Ｓ０）未使用リスト３２１を参照して、要求されるサイズ以上の未使用領域を検出する。
【００２６】
（Ｓ１）ステップＳ０で検出できればステップＳ４へ進み、そうでなければステップＳ２へ進む。
【００２７】
（Ｓ２）ヒープ領域３１を拡大可能であればこれを拡大する。また、以下で使用するフラグＦに０を代入する。
【００２８】
（Ｓ３）サイズＳＺ２での拡大により、要求されたサイズのメモリを確保可能であればステップＳ４へ進み、そうでなければステップＳ５へ進む。
【００２９】
（Ｓ４）未使用リスト３２１及び使用中リスト３２２に対し上述の処理を行って、要求されたメモリを確保する。
【００３０】
（Ｓ５）Ｆ＝０であればステップＳ６へ進み、そうでなければステップＳ８へ進む。
【００３１】
（Ｓ６）メモリデフラグメンテーション部３０３を介して、ヒープ領域３１に対し、後述のデフラグメンテーションを行う。
【００３２】
（Ｓ７）フラグＦに１を代入し、ステップＳ３へ戻る。
【００３３】
（Ｓ８）要求されたサイズのメモリを確保できなかったことを要求元に知らせるために、関数の戻り値としてＮＵＬＬを返す。
【００３４】
図２は、ステップＳ６の詳細フローチャートである。
【００３５】
（Ｓ２０）使用中リスト３２２を参照して、使用中領域の最大サイズＳＺumを検出する。
【００３６】
例えば図５のヒープ領域３１の場合、使用中領域Ｅのサイズが最大サイズＳＺumとして検出される。
【００３７】
（Ｓ２１）図５に示すように、この最大サイズＳＺumの領域の両端のそれぞれと、ヒープ領域３１の同一端側との間の２領域のそれぞれのサイズＳＺ１及びＳＺ２を求める。
【００３８】
（Ｓ２２）ＳＺ１＞ＳＺ２であればステップＳ２３へ進み、そうでなければステップＳ３３へ進む。
【００３９】
（Ｓ２３）第１段階のデフラグメンテーションとして、サイズＳＺ２側の各使用中領域を、最大サイズＳＺumの領域に近いほうから順に詰めて再配置する。これにより、図５の場合、図３（Ａ）に示す如くなる。
【００４０】
（Ｓ２４）サイズＳＺ１側に使用中領域が存在すればステップＳ２５へ進み、そうでなければステップＳ２８へ進む。
【００４１】
（Ｓ２５）サイズＳＺ１側の最大サイズＳＺumに最も近い使用中領域がサイズＳＺ２側の現在の未使用領域のサイズ以下であればステップＳ２６へ進み、そうでなければステップＳ２７へ進む。
【００４２】
（Ｓ２６）この使用中領域を、サイズＳＺ２側の現在の未使用領域に、最大サイズＳＺum側へ詰めて再配置する。次にステップＳ２４へ戻る。ステップＳ２４〜Ｓ２６の処理の繰り返しにより、図３（Ｂ）に示す状態となる。
【００４３】
（Ｓ２７）この使用中領域を、サイズＳＺ１側の現在の未使用領域に、最大サイズＳＺum側へ詰めて再配置する。次にステップＳ２４へ戻る。ステップＳ２４、Ｓ２５及びＳ２７の処理の繰り返しにより、図３(Ｃ)に示す状態となる。
【００４４】
（Ｓ２８）サイズＳＺ２側の余白が最大サイズＳＺum以上であればステップＳ２９へ進み、そうでなければデフラグメンテーション処理を終了する。
【００４５】
図３(Ｃ)の場合にはステップＳ２８で否定判定され、図４(Ａ)の場合にはステップＳ２８で肯定判定される。
【００４６】
（Ｓ２９）最大サイズＳＺumの領域を、サイズＳＺ２側の現在の未使用領域に、最大サイズＳＺumの領域側へ詰めて再配置する。これにより、図４（Ｂ）に示す如くなる。
【００４７】
ステップＳ３３〜Ｓ３９の処理はそれぞれ、ステップＳ２３〜Ｓ２９の処理においてサイズＳＺ１とＳＺ２とを入れ替えた処理と同一であり、その説明を省略する。
【００４８】
本実施例１によれば、最大サイズＳＺumの使用領域Ｅを再配置しなくてもよく、しかも、２領域ＳＺ１及びＳＺ２中サイズが小さい方の領域内にこれ以外の使用中領域の全部又は一部を簡単なアルゴリズムで再配置するので、比較的大きな空き領域を短時間で得ることができ、リアルタイム処理を確保可能となるという効果を奏する。換言すれば、よりパフォーマンスの低い安価なワンチップマイクロコンピュータ１０を用いることが可能となるという効果を奏する。
【００４９】
また、第１段階として、２領域ＳＺ１及びＳＺ２中サイズが小さい方の領域内に存在する使用中領域を先に再配置するので（Ｓ２２、Ｓ２３、Ｓ３３）、再配置可能か否かを判断することなく確実に再配置でき、処理効率が高いという効果を奏する。
【００５０】
さらに、この第１段階の再配置完了後の第２段階の処理（Ｓ２４〜Ｓ２７、Ｓ３４〜Ｓ３７）により、２領域ＳＺ１及びＳＺ２中サイズが小さい方の領域内にさらに、サイズが大きい方の領域内の使用中領域が再配置されるので、より大きな空き領域を得ることができるという効果を奏する。
【００５１】
また、この第２段階の再配置完了後に、可能であれば（Ｓ２８、Ｓ３８）最大サイズＳＺumの使用中領域Ｅが２領域ＳＺ１及びＳＺ２中サイズが小さい方の領域内に再配置されるので（図４）、さらに大きな空き領域を効率よく得ることができるという効果を奏する。
【００５２】
本発明の好適な実施例を説明したが、本発明には他にも種々の変形例が含まれ、上記複数の実施例で述べた構成要素の他の組み合わせ、各構成要素の機能を実現する他の構成を用いたもの、当業者であればこれらの構成又は機能から想到するであろう他の構成も、本発明に含まれる。
【００５３】
例えば、上記実施例ではリアルタイム性の高い処理として複数スレッドのそれぞれでヒープ領域３１内にメモリを確保する場合を説明したが、複数プロセスのそれぞれでヒープ領域３１内にメモリを確保したり、単一プロセスでヒープ領域３１内にメモリを確保する場合にも本発明を適用できる。
【図面の簡単な説明】
【００５４】
【図１】メモリ管理部のメモリ割当部による処理を示す概略フローチャートである。
【図２】図１中のステップＳ６の詳細フローチャートである。
【図３】（Ａ）〜（Ｃ）はそれぞれ図２のステップＳ２３、Ｓ２４〜Ｓ２６並びにＳ２４、Ｓ２５及びＳ２７の処理説明図である。
【図４】（Ａ）及び（Ｂ）は図２のステップ２８及びＳ２９の処理説明図である。
【図５】メモリデフラグメンテーションに関係した部分の機能ブロック図である。
【図６】本発明が適用される組込システムの概略ブロック図である。
【符号の説明】
【００５５】
１０  ワンチップマイクロコンピュータ
１１  ＭＰＵ
１２  バス
１３  ＲＯＭ
１４  ＲＡＭ
１５  周辺回路
１６  Ｉ/Ｏインタフェース
２０  メインスレッド
２１〜２３  スレッド
３０  メモリ管理部
３０１  メモリ割当部
３０２  メモリ解放部
３０３  メモリデフラグメンテーション部
３１  ヒープ領域
３２  メモリ管理リスト
３２１  未使用リスト
３２２  使用中リスト
Ａ〜Ｇ  使用中領域
ＳＺum  最大サイズ
ＳＺ１、ＳＺ２  サイズ
Ｆ  フラグ
【図１】
2010277268.tif 000003
【図２】
2010277268.tif 000004
【図３】
2010277268.tif 000005
【図４】
2010277268.tif 000006
【図５】
2010277268.tif 000007
【図６】
2010277268.tif 000008