(57)【要約】【課題】  メモリ管理システムにおいて、メモリのフラグメンテーションを効率的に回避することができない問題点と、高速に連続的なメモリ空間の割当、解放動作を行い、割当てられた連続的なメモリ空間のサイズの増減を行うことができない問題点を解決し、メモリの割当要求時に要求サイズに適合した未使用領域を高速で割当てること。【解決手段】  メモリ管理システムにおいて、物理アドレス空間を小サイズ毎に区切ったマイクロパーテーション単位で扱い、アプリケーション毎に区切った連続的な論理アドレス空間を必要数の前記マイクロパーテーションに割当てる。物理パーテーション中の未使用領域は、フラグメンテーションのため細分化されてゆくが、各未使用領域をサイズ毎にグループ化して、メモリの割当要求時には要求メモリサイズに該当するグループから未使用領域を選択するために、未使用領域を検索するための時間が短縮されて処理速度が向上する。【選択図】図５
2010204762.tif 000002
【特許請求の範囲】
【請求項１】
論理アドレス空間においてアプリケーションが使用する仮想メモリの割当と解放を管理する論理パーテーション管理部と、
物理アドレス空間において実メモリを小サイズ毎の物理パーテーションに切り分けて前記実メモリの割当と解放を管理する物理パーテーション管理部と、
前記論理アドレス空間と前記物理アドレス空間との間のアドレス変換を行う変換部とを有し、
前記物理パーテーション管理部は、前記物理パーテーションの未使用領域をそのサイズ毎に分類しておき、メモリ割当要求の際には当該割当要求のサイズを含む前記分類された未使用領域から検索して選択する
ことを特徴とするメモリ管理システム。
【請求項２】
請求項１のメモリ管理システムであって、
前記変換部は、前記論理アドレス空間と前記物理アドレス空間とを関連付ける変換テーブルを生成又は消去する
ことを特徴とするメモリ管理システム。
【請求項３】
請求項１又は２のメモリ管理システムであって、
前記論理パーテーション管理部は、前記仮想メモリの割当をアプリケーション毎に連続した論理アドレス空間に確保する
ことを特徴とするメモリ管理システム。
【請求項４】
請求項１から３のいずれかのメモリ管理システムを有する
ことを特徴とする電子機器。
【請求項５】
コンピュータに、
論理アドレス空間においてアプリケーションが使用する仮想メモリの割当と解放を管理する論理パーテーション管理機能と、
物理アドレス空間において実メモリを小サイズ毎の物理パーテーションに切り分けて前記実メモリの割当と解放を管理する物理パーテーション管理機能と、
前記論理アドレス空間と前記物理アドレス空間との間のアドレス変換を行う変換機能とを実現させ、
前記物理パーテーション管理機能は、前記物理パーテーションの未使用領域をそのサイズ毎に分類しておき、メモリ割当要求の際には当該割当要求のサイズを含む前記分類された未使用領域から検索して選択する
ことを特徴とするメモリ管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
メモリ管理システム、電子機器及びメモリ管理プログラムにおいて、メモリの割当・解放動作に関して、フラグメンテーションの発生を抑制し効率的なメモリ管理を行う技術に関する。
【背景技術】
【０００２】
半導体メモリや磁気回転ディスクなどの記憶装置を備える電子機器では、メモリの管理を効率的に行う技術的要求がある。メモリは使用時に必要領域を確保（割当）し、その使用が終わった後は解放して再使用に備える。このような、メモリの割当・解放動作を繰り返すと、フラグメンテーションと呼ばれる使用可能なメモリ空間がアドレス空間上に細かく分散して存在する状態になってしまい、メモリの使用率としては少ない状態であっても大きなアドレス空間が取れない状況が発生する。
【０００３】
従来技術として、画像形成装置などのデータ処理装置において、フラグメンテーションの発生を少なくし、メモリの空き待ちやメモリ内のデータ移動等によるスループットの低下を起こさないメモリ管理方法を実現する以下の方法がある。ページ検出処理部がページ開始を検出すると、メモリ資源取得処理部がメモリを確保し、パーティション（パーテーション）分割が行われ、入力データ用および加工データ用のパーティション（パーテーション）にメモリ領域がそれぞれ確保される。データ加工処理部によって加工データが生成され加工データ用メモリ領域に格納されると、メモリ資源解放処理部によって、不要となるメモリ領域の解放が行われる。解放されたメモリ領域は、加工データ用パーティション（パーテーション）の空き領域の一部となる（特許文献１参照）。
【０００４】
また、高い書き込み速度を実現可能なホスト機器を提供するために、管理システムがメモリ領域上で区画された単位領域を書き込みデータが記憶される書き込み領域として順次割り当てる機能を有し、単位領域の自然数倍の大きさからなる管理単位を割り当て位置の決定単位として用い、書き込み関数呼び出しを受けて管理単位ごとの実現可能な書き込み速度順に従って管理単位を前記書き込み領域として割り当てて、コントローラが、管理システムが割り当てた単位領域に書き込みデータを書き込む旨の指示をメモリカードに出す方法があった（特許文献２参照）。
【０００５】
しかし、特許文献１の方法では画像形成装置のページ単位毎の処理を前提としているため、複数ページに跨る処理には対応できない。また、パーテーションの区切りは２つという制限がある。さらに、パーテーションのサイズは、最初の割当時の容量で不足しても、その連続的メモリ空間の増量はできず、ひとつのパーテーションのサイズを減少する方向にしか容量変化に対応できない。
【０００６】
また、特許文献２の方法は、書き込みの際のメモリ割当に関するものであり、メモリが連続的に割当・解放動作を伴う際のフラグメンテーションの抑制には対応できない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００２−３５１７３９号公報
【特許文献２】特開２００６−２８５６６９号公報
【非特許文献】
【０００８】
【非特許文献１】「プログラミング言語Ｃ」第２版（１９８９年）
【発明の概要】
【発明が解決しようとする課題】
【０００９】
解決しようとする問題点は、メモリ管理システム、電子機器及びメモリ管理プログラムにおいて、メモリのフラグメンテーションを効率的に回避することができなかった点と、高速に連続的なメモリ空間の割当・解放動作を行い、割当てられた連続的なメモリ空間のサイズの増減を行うことができなかった点である。さらに、物理パーテーション内の未使用領域の割当を行う際に、割当サイズに適した未使用メモリ領域を高速で検索することができなかった点である。
【課題を解決するための手段】
【００１０】
本発明のメモリ管理システムは、論理アドレス空間においてアプリケーションが使用する仮想メモリの割当と解放を管理する論理パーテーション管理部と、物理アドレス空間において実メモリを小サイズ毎の物理パーテーションに切り分けて前記実メモリの割当と解放を管理する物理パーテーション管理部と、前記論理アドレス空間と前記物理アドレス空間との間のアドレス変換を行う変換部とを有し、前記物理パーテーション管理部は、前記物理パーテーションの未使用領域をそのサイズ毎に分類しておき、メモリ割当要求の際には当該割当要求のサイズを含む前記分類された未使用領域から検索して選択することを特徴とする。
【００１１】
また、本発明のメモリ管理システムの前記変換部は、前記論理アドレス空間と前記物理アドレス空間とを関連付ける、前記変換テーブルを生成又は消去することを特徴としてもよい。
【００１２】
また、本発明のメモリ管理システムの前記論理パーテーション管理部は、前記仮想メモリの割当をアプリケーション毎に連続した論理アドレス空間に確保することを特徴としてもよい。
【００１３】
本発明の電子機器は、前記メモリ管理システムを有することを特徴とする。
【００１４】
本発明のメモリ管理プログラムは、コンピュータに、論理アドレス空間においてアプリケーションが使用する仮想メモリの割当と解放を管理する論理パーテーション管理機能と、物理アドレス空間において実メモリを小サイズ毎の物理パーテーションに切り分けて前記実メモリの割当と解放を管理する物理パーテーション管理機能と、前記論理アドレス空間と前記物理アドレス空間との間のアドレス変換を行う変換機能とを実現させ、前記物理パーテーション管理機能は、前記物理パーテーションの未使用領域をそのサイズ毎に分類しておき、メモリ割当要求の際には当該割当要求のサイズを含む前記分類された未使用領域から検索して選択することを特徴とする。
【発明の効果】
【００１５】
本発明のメモリ管理システムは、論理アドレス空間においてアプリケーションが使用する仮想メモリの割当と解放を管理する論理パーテーション管理部と、物理アドレス空間において実メモリを小サイズ毎の物理パーテーションに切り分けて前記実メモリの割当と解放を管理する物理パーテーション管理部と、前記論理アドレス空間と前記物理アドレス空間との間のアドレス変換を行う変換部とを有し、前記物理パーテーション管理部は、前記物理パーテーションの未使用領域をそのサイズ毎に分類しておき、メモリ割当要求の際には当該割当要求のサイズを含む前記分類された未使用領域から検索して選択することを特徴とする。
【００１６】
このため、論理アドレス空間におけるフラグメンテーションの効率を効率的に回避する。また、高速に連続的な仮想メモリ空間の割当、解放動作が可能となり、割当てられた連続的な仮想メモリ空間のサイズの増減を行うことが可能となる。そして、多数ある未使用領域の中から、その割当要求のサイズに合う未使用領域を検索する際に、あらかじめサイズによって分類化されている複数のグループ中の最適のグループを選択してその中で検索することが可能となるので、未使用領域の選択にかかる時間が大きく短縮される。
【００１７】
また、本発明のメモリ管理システムの前記変換部は、前記論理アドレス空間と前記物理アドレス空間とを関連付ける、前記変換テーブルを生成又は消去することを特徴としてもよい。
【００１８】
このため、アプリケーションが使用する仮想メモリの論理アドレス空間から、実メモリの物理アドレス空間へのアドレス変換が効率よく行うことができる。
【００１９】
また、本発明のメモリ管理システムの前記論理パーテーション管理部は、前記仮想メモリの割当をアプリケーション毎に連続した論理アドレス空間に確保することを特徴としてもよい。
【００２０】
このため、アプリケーション毎に区切られたパーテーションを一度に解放することにより、仮想メモリの解放が高速に行うことが可能となり、かつ、連続した大きな論理アドレス空間を得ることが可能となる。
【００２１】
本発明の電子機器は、前記メモリ管理システムを有することを特徴とする。
【００２２】
このため、論理アドレス空間におけるフラグメンテーションの発生を効率的に回避する。また、高速に連続的な仮想メモリ空間の割当、解放動作が可能となり、割当てられた連続的な仮想メモリ空間のサイズの増減を行うことが可能となる。また、アプリケーション毎に区切られたパーテーションを一度に解放することにより、仮想メモリの解放を高速に行うことが可能となり、かつ、連続した大きな論理アドレス空間を得ることが可能となる。また、ＤＭＡ（Direct Memory Access）等のハードウェア依存アクセスがあっても、当該箇所が他のアプリケーション等に割当てられることがなく動作する。
【００２３】
本発明のメモリ管理プログラムは、コンピュータに、論理アドレス空間においてアプリケーションが使用する仮想メモリの割当と解放を管理する論理パーテーション管理機能と、物理アドレス空間において実メモリを小サイズ毎の物理パーテーションに切り分けて前記実メモリの割当と解放を管理する物理パーテーション管理機能と、前記論理アドレス空間と前記物理アドレス空間との間のアドレス変換を行う変換機能とを実現させ、前記物理パーテーション管理機能は、前記物理パーテーションの未使用領域をそのサイズ毎に分類しておき、メモリ割当要求の際には当該割当要求のサイズを含む前記分類された未使用領域から検索して選択することを特徴とする。
【００２４】
このため、論理アドレス空間におけるフラグメンテーションの効率を効率的に回避する。また、高速に連続的な仮想メモリ空間の割当、解放動作が可能となり、割当てられた連続的な仮想メモリ空間のサイズの増減を行うことが可能となる。そして、多数ある未使用領域の中から、その割当要求のサイズに合う未使用領域を検索する際に、あらかじめサイズによって分類化されている複数のグループ中の最適のグループを選択してその中で検索することが可能となるので、未使用領域の選択にかかる時間が大きく短縮される。
【図面の簡単な説明】
【００２５】
【図１】従来のメモリプール方式（１）のアプリケーションとメモリマップの関係図である。
【図２】従来のメモリプール方式（２）のメモリマップとメモリプールの関係図である。
【図３】従来のメモリマッププール方式（３）のメモリマップと物理パーテーションの関係図である。
【図４】従来のメモリプール方式（２）でのメモリマップとパーテーションの関係図である。
【図５】従来のメモリプール方式（３）でのメモリマップとパーテーションの関係図である。
【図６】アプリケーションを一括解放するメモリ管理方式のメモリマップ図である。
【図７】フラグメンテーションの上限の閾値を設けるメモリ管理方式のメモリマップ図である。
【図８】ＭＣＢによる未使用領域のリンク状態を示すマップメモリである。
【図９】本発明によるパーテーション内でサイズ毎に未使用領域をグループ化した様子を示すマップメモリである。
【図１０】従来例による記憶割当の説明図である。
【図１１】未使用メモリブロックのリスト構造が全てのパーテーションにリンクされている場合を示す図である。
【図１２】未使用メモリブロックのリスト構造を物理パーテーション単位に区切る場合の図である。
【図１３】未使用メモリブロックのリスト構造が全ての物理パーテーションにリンクされている場合の図である。
【図１４】未使用メモリブロックのリスト構造を物理パーテーション単位に区切る場合の図である。
【図１５】未使用メモリブロックのリスト構造を物理パーテーションにリンクされている場合の変換テーブルの例である。
【図１６】未使用メモリブロックのリスト構造を物理パーテーション単位に区切る場合を示す図である。
【図１７】変換テーブルとＭＣＢの関係を示す図である。
【図１８】ＢＳＤ mallocによる割当の例のパーテーション内のメモリマップである。
【図１９】割当サイズに応じて、未使用メモリブロックのリスト構造を別にする例のパーテーション内のメモリマップである。
【図２０】割当サイズに応じて、未使用メモリブロックのリスト構造を別にする例である。
【図２１】割当サイズに応じて、未使用メモリブロックのリスト構造を別にする場合の変換テーブルの例である。
【図２２】割当サイズに応じて未使用メモリブロックのリスト構造を別にする場合の変換テーブルのリンク例である。
【図２３】変換テーブルとＭＣＢとの関係を示す図である。
【図２４】ひとつの未使用メモリブロックのリスト構造によるメモリ解放の説明図である。
【図２５】複数の未使用メモリブロックのリスト構造によるメモリ解放の説明図である。
【図２６】割当後フリー領域が存在する場合のメモリ割当前後のメモリマップである。
【図２７】割当後フリー領域が存在する場合のメモリ割当のフローチャートである。
【図２８】割当後フリー領域が存在しない場合のメモリ割当前後のメモリマップである。
【図２９】割当後フリー領域が存在しない場合のメモリ割当処理のフローチャートである。
【図３０】メモリ解放前後のメモリマップである（左隣接メモリブロックが未使用、右隣接メモリブロックが使用中の場合）。
【図３１】メモリ解放処理のフローチャートである（左隣接メモリブロックが未使用、右隣接メモリブロックが使用中の場合）。
【図３２】メモリ解放前後のメモリマップである（左隣接メモリブロックが使用中、右隣接メモリブロックが未使用の場合）。
【図３３】メモリ解放処理のフローチャートである（左隣接メモリブロックが使用中、右隣接メモリブロックが未使用の場合）。
【図３４】メモリ解放前後のメモリマップである（左右隣接メモリブロックが未使用の場合）。
【図３５】メモリ解放処理のフローチャートである（左右隣接メモリブロックが未使用の場合）。
【図３６】メモリ解放前後のメモリマップである（左右隣接メモリブロックが使用中の場合）。
【図３７】メモリ解放処理のフローチャートである（左右隣接メモリブロックが使用中の場合）。
【図３８】ソフトウェアの構成図である。
【発明を実施するための形態】
【００２６】
メモリ管理システム、電子機器及びメモリ管理プログラムにおいて、メモリのフラグメンテーションを効率的に回避することができない問題点と、高速に連続的な仮想メモリ空間の割当、解放動作を行い、割当てられた連続的なメモリ空間のサイズの増減を行うことができない問題点を物理アドレス空間を小サイズ毎に区切ったマイクロパーテーション単位で扱い、アプリケーション等毎に区切った連続的な論理アドレス空間を必要数の前記マイクロパーテーションに割当てる。マイクロパーテーションの集合で形成する論理パーテーションに対応する物理パーテーション中の未使用領域は、フラグメンテーションのため細分化されてゆくが、各未使用領域をサイズ毎にグループ化して、メモリの割当要求時には要求メモリサイズに該当するグループから未使用領域を選択する方法により、未使用領域を検索するための時間が短縮されて処理速度が向上する。
【実施例】
【００２７】
［従来のメモリプール方式との比較］
図１に示すように従来のメモリプール方式では、メモリ空間中からアプリケーションが必要時にメモリ領域を取得（割当）して、メモリの使用が終わると同領域を解放する。この動作により、フラグメンテーションと呼ばれるメモリが細分化された状態となり連続した大容量のメモリ領域を取ることが困難となる問題がある。
【００２８】
図２に従来方式での改良されたメモリプール方式では、アプリケーションの各々が起動時にサイズを定めたメモリ領域を確保する。メモリマネージャーはアプリケーションからのメモリ割当要求時には、それぞれのアプリケーションに予め確保されたメモリ領域内からメモリを取得する。本方法では、図１で説明した方法に比較して、アプリケーションの終了時には、あらかじめ確保されていたメモリ領域が一括して解放されるため、大容量の連続したメモリ領域を確保できるメリットがある。
【００２９】
しかし、何れの方法でも、画像形成装置などアプリケーションによっては大きな画像データを扱う装置では個々のアプリケーションが使用する最大メモリサイズが大きく異なる。そのため、図２で示した各アプリケーションのメモリプールの領域を固定する方法では、メモリの使用が非効率となる問題がある。
【００３０】
［マイクロパーテーションによる物理アドレス空間と論理アドレス空間の変換］
そこで、物理メモリ空間を小サイズの領域（以降マイクロパーテーションと呼ぶ）に切り分けて、論理アドレス空間をこのマイクロパーテーションの実メモリの物理アドレス空間に変換する方法によって、前記した不具合を解消する。
【００３１】
この方法によれば、実メモリの物理アドレス空間が実際に連続していなくとも、連続した論理アドレス空間に割当てることにより、連続した大容量のメモリ空間を確保することができる。
【００３２】
例えば、図２で示したアプリケーション毎にメモリプールを行う方式において、以下の表１に示すパーテーションサイズでメモリ領域を確保しておいて、後にデータのサイズに示すメモリ領域が必要となった時に、データのサイズがパーテーションサイズを超えている場合にはメモリ領域を確保できない。図４にこの場合のメモリマップを示す。
【００３３】
【表１】
2010204762.tif 000003
【００３４】
しかし、前記したマイクロパーテーションを用いて物理アドレス空間と論理アドレス空間の変換を行う場合には、表２に示すように必要に応じてパーテーションサイズを変更可能（マイクロパーテーションを論理アドレス空間に割当てるないしは解放することにより可能）であるので上記したようなメモリの不足の問題は起こらない。図５にこの場合のメモリマップを示す。
【００３５】
【表２】
2010204762.tif 000004
【００３６】
［パーテーション内の未使用領域］
このようなマイクロパーテーションを用いた、論理アドレス空間と物理アドレス空間との間での変換を行う方法において、アプリケーションによって使用されるメモリ空間と未使用のメモリ空間により分けられるが、未使用のメモリ領域は、図８に示すようなリンクリスト構造により結合されている。
【００３７】
これは、アプリケーションからのメモリ領域の割当要求時にその割当要求に適したサイズ（割当要求のサイズより大きくかつなるべく小さい容量のものを選択することにより、メモリの利用効率を高めてフラグメンテーションの発生を抑制可能である）のものを探し出すために、まず、ポインタが示すメモリ領域のサイズを要求サイズと比較して、適合すれば当該領域を確保し、適合しなければ当該領域のポインタが指し示す次の領域に飛ぶというメモリ確保のための領域の検索動作を取るためである。この場合にこのリンクリスト構造は、未使用のメモリ領域のサイズには関係なく、アドレス空間の順番に機械的に並んでいるだけであり、最適なサイズの未使用領域を探し出す（検索する）のに非常に時間がかかる問題がある。
【００３８】
そこで、本発明実施例のメモリ管理方式では、未使用領域（未使用ブロック）のリンクリスト構造を物理パーテーション単位で閉じてさらに、未使用領域のサイズの幅（レンジ）をもたせて、そのサイズのレンジ内でのリンクリスト構造とすることとした。
【００３９】
図９に示す例では、メモリの未使用領域を
（１）メモリレンジ１をメモリサイズが0x0001から0x00FF
（２）メモリレンジ２をメモリサイズが0x0100から0x0FFF
（３）メモリレンジ３をメモリサイズが0x1000以上
とする３つのレンジに分けて、それぞれのレンジ毎に連結したリンクリスト構造にしてある。
【００４０】
［構成］
図３８に本発明実施例のメモリ管理システムの機能ブロック図を示す。
【００４１】
メモリ管理システムは、メモリマネージメント初期化部２００、変換テーブル管理部２０１、アドレス変換部２２１、メモリ統計情報管理部２４１、ＭＣＢ管理部２６１の各機能部を有する。以下に各機能部について説明する。
【００４２】
メモリマネージメント初期化部２００は、メモリマネージメントの初期化に必要な動作を行う。初期化時にメモリマネージメントを行うメモリ領域や、物理アドレス空間、論理アドレス空間、固定アドレス空間の設定等を行う。
【００４３】
変換テーブル管理部２０１（論理パーテーション管理部、物理パーテーション管理部）は、物理アドレス空間において実メモリを小サイズに切り分けたマイクロパーテーションに対するメモリの割当と解放の管理を行う。また、論理アドレス空間においてアプリケーションが使用する仮想メモリの割当と解放の管理を行う。変換テーブル管理部２０１は、さらに個々の機能部に分かれており、パーテーション管理部２１１、パーテーションサイズの管理部２１３、アドレス（物理、論理）管理部２１５、ＩＤ管理部２１７、フラグ（待機、停止）管理部２１９とを有する。
【００４４】
パーテーション管理部２１１は、前記した物理アドレス空間をマイクロパーテーションに切り分けてその割当解放の管理を行う。
【００４５】
パーテーションサイズの管理部２１３は、パーテーションのサイズの管理を行う。
【００４６】
アドレス（物理、論理）管理部２１５は、論理アドレスでのメモリの割当及び解放と、それに呼応する物理アドレスの管理を行う。
【００４７】
ＩＤ管理部２１７は、アプリケーション毎に持つＩＤを管理し、変換テーブル中に各メモリブロックがどのアプリケーションから使われているかのＩＤを記載して管理する。
【００４８】
フラグ（待機、停止）管理部２１９は、各メモリブロックの状態（待機、停止）を管理する。
【００４９】
次にアドレス変換部２２１（変換部）は、前記論理アドレス空間と物理アドレス空間との間のアドレス変換を行う。物理アドレスから論理アドレスへの変換部２３１と論理アドレスから物理アドレスへの変換部２３３との二つの機能部を有する。
【００５０】
メモリ統計情報管理部２４１（物理パーテーション管理部）は、物理パーテーション管理部の一部の機能を担う。物理パーテーション内の未使用領域をそのサイズによりグループに分けてリンクリスト構造を形成し、メモリの割当要求の際には、最適なサイズのグループの中のリンクリストから未使用領域を検索する。
【００５１】
メモリ使用ブロック数の管理部２３１は、メモリ使用ブロック数を管理する。
【００５２】
メモリ使用バイト数の管理部２５３は、メモリ使用バイト数を管理する。
【００５３】
パーテーションの閾値チェック部２５５は、パーテーションのフラグメンテーション率をチェックし、そのフラグメンテーション率が上限の閾値を超えた場合には、当該パーテーションからのメモリの再割当を禁止する。一旦再割当を禁止されたパーテーションのフラグメンテーション率が下限の閾値を下回った場合には、メモリの再割当の禁止を解除する。これらの上限閾値と下限閾値は例えば、典型的には上限閾値を７０％、下限閾値を３０％としてもよい。また、上限閾値は最大値に近い例えば９９％といった値であってもよい。
【００５４】
ここで、フラグメンテーション率は次式から算出される。
【００５５】
フラグメンテーション率（％）＝｛［フラグメント数］／（［マイクロパーテーション数］−１）｝×１００
閾値種別管理２５７は、メモリの未使用領域のサイズに従って、物理パーテーション内でサイズ毎にグループ分けを行う。
【００５６】
ＭＣＢ管理部２６１は、メモリコントロールブロック（ＭＣＢ）の管理を行う。ＭＣＢは、実メモリのメモリブロックの先頭部にあるポインターやサイズ情報等を納めた部分であり、その管理を行う。ＭＣＢの動作の詳細については後述する。
【００５７】
［詳細な動作の説明］
本方式のさらに詳細な構造について、従来例（非特許文献１参照）との比較を示して以下に説明する。
【００５８】
図９は、メモリマップの未使用領域と使用領域でのさらに詳細な構造を示した図である。各メモリ領域には、先頭に次の同種のメモリ領域を示すポインタ（ptr）と領域のサイズ（size）を示すＭＣＢ（メモリコントロールブロック）と呼ばれるヘッダ部分を持ち、その後に使用可能領域を有する。
【００５９】
この場合に、使用中のメモリのポインタは使われること無く、未使用の領域についてのポインタが次の未使用領域を示す。ＭＣＢと使用可能領域を合わせてメモリブロックと呼ぶ。以下の表３にＭＣＢの内容を示す。
【００６０】
【表３】
2010204762.tif 000005
【００６１】
図９に示した非特許文献１によるアルゴリズムでは、未使用メモリブロックのリスト構造が全てのパーテーションにリンクされている（繋がっている）ので、割当処理時間が長くなる場合がある。
【００６２】
また、未使用メモリブロックのリスト構造を物理パーテーション単位に区切った場合と比較して割当処理の平均時間が長いという問題がある。
【００６３】
図１１に、未使用メモリブロックのリスト構造が全てのパーテーションにリンクされている場合を示す。また、図１２に未使用メモリブロックのリスト構造を物理パーテーション単位に区切る場合を示す。
【００６４】
さらに、そのときのリンクリスト構造を示したメモリマップについて、図１３に、未使用メモリブロックのリスト構造が全てのパーテーションにリンクされている場合を、図１４に未使用メモリブロックのリスト構造を物理パーテーション単位に区切る場合を示す。
【００６５】
これらの場合に用いられる変換テーブルの例について、図１５及び図１６に示す。図１５は、未使用メモリブロックのリスト構造が、全ての物理パーテーションにリンクされている場合であり、図１６は、未使用メモリブロックのリスト構造が、物理パーテーション単位に区切る場合である。
【００６６】
両方に共通する項目は、マイクロパーテーション番号、ＩＤ（メモリを利用しているアプリケーションを示す番号）、フラグ（メモリの使用状態）、物理開始アドレス、レングス（長さ、すなわちサイズ）、論理開始アドレス、リンク先ポインタ（次の未使用メモリブロックを示すポインタ）である。
【００６７】
図１６には、図１５に無い「先頭のＭＣＢへのポインタ」という項目がある。次にこの項目について説明する。
【００６８】
図１７に未使用メモリブロックのリスト構造が物理パーテーション単位で区切られている場合のメモリマップ（上段）と変換テーブル（下段）を並べて示し、「先頭のＭＣＢへのポインタ」が、各物理パーテーションの未使用メモリ領域の先頭アドレスを指すことを示している。
【００６９】
この方法により、物理パーテーション単位毎に未使用メモリ領域を探すことが可能となり、未使用メモリの割当の効率が高まる。
【００７０】
図１８に非特許文献１に記載のＢＳＤ malloc によるメモリの割当方法で割当てられた際のメモリマップの例を示す。従来のＢＳＤ malloc によるメモリの割当方法では、予め複数サイズのブロックを用意し、要求されたメモリサイズに該当するブロックを割当てる。本方法によるメモリ割当は高速処理が可能だがメモリ使用効率は悪い。
【００７１】
一方本発明実施例によるメモリ管理方法によるメモリ割当でのメモリマップと各未使用領域のリンクリスト構造を図１９に示す。この場合に、割当サイズに応じて未使用メモリブロックのリスト構造を別にすることにより、未使用メモリブロックの検索回数が減る。
【００７２】
図２０にこの場合のより詳細にメモリマップを示す。未使用メモリ領域は、サイズによってメモリレンジ１とメモリレンジ２の二つに分けられて、それぞれは異なるリンクリスト構造に属している。この場合には、ＭＣＢ部分に以下の表４に示す、prev-flag, self-flagを有する。
【００７３】
【表４】
2010204762.tif 000006
【００７４】
表４にあるとおり、prev-flagは隣接する一つ前のメモリブロックの状態（使用中か未使用）を示す。self-flagは自身のメモリブロックの状態を表す。使用中とは、メモリが割当てられている状態、未使用とはメモリが割当てられていない状態を表す。
【００７５】
ptrは、self-flagが未使用の場合は、次の同じメモリレンジの未使用ブロックの先頭を表し、使用中の場合は、隣接する一つ前の未使用メモリブロックの先頭アドレスを示す。
【００７６】
図２１に割当サイズに応じて未使用メモリブロックのリスト構造をサイズ１から４の４つに分ける場合の変換テーブルを示す。図１６で示した変換テーブルでは、ひとつのＭＣＢへのポインタのみがあったが、図２３で示すようにＭＣＢへのポインタは、未使用領域のサイズ毎に分けられたポインタを有する。図２３に示すように、サイズ１から４の４つのポインタは、メモリマップ上のそれぞれのレンジの未使用領域のリンクリスト構造の先頭のリストを指し示す。
【００７７】
図２２に図２１に示した変換テーブルのリンク例を示す。各テーブルのリンク先ポインタが次のテーブルを指し示しており、最終テーブルのリンク先ポインタはＥＮＤとなっている。
【００７８】
図２３にこの変換テーブルとＭＣＢの関係を示す。前記したサイズ毎の先頭のＭＣＢへのポインタは、そのサイズのレンジ内に該当するサイズの未使用領域を有する未使用領域の先頭アドレスを指し示す。
【００７９】
図２４に非特許文献１に記載のメモリブロックの解放方法を示す。従来方法では、複数の未使用メモリブロックのリスト構造に対応できない。
【００８０】
図２４（Ｐ）の例では、ＡからＥのメモリブロックがＡ：使用、Ｂ：未使用、Ｃ：使用、Ｄ：未使用、Ｅ：使用の状態でＣを解放するとＢ＋Ｃ＋Ｄの未使用の連続領域ができ、前の未使用領域はＢ、次の未使用領域はＤとなる。
【００８１】
図２４（Ｑ）の例では、ＡからＥのメモリブロックがＡ：未使用、Ｂ：使用、Ｃ：使用、Ｄ：未使用、Ｅ：使用の状態でＣを解放するとＣ＋Ｄの未使用の連続領域ができ、前の未使用領域はＡ，次の未使用領域はＤとなる。
【００８２】
図２４（Ｒ）の例では、ＡからＥのメモリブロックがＡ：使用、Ｂ：未使用、Ｃ：使用、Ｄ：使用、Ｅ：未使用の状態でＣを解放するとＢ＋Ｃの未使用の連続領域ができ、前の未使用領域はＢ、次の未使用領域はＥとなる。
【００８３】
図２４（Ｓ）の例では、ＡからＥのメモリブロックがＡ：未使用、Ｂ：使用、Ｃ：使用、Ｄ：使用、Ｅ：未使用の状態でＣを解放すると前の未使用領域はＡ、次の未使用領域はＥとなる。
【００８４】
図２５では、本発明実施例のメモリレンジ毎にリンクリスト構造を有する場合の例について示す。図２５（Ｔ）で、メモリブロックがＡ：未使用、Ｂ：使用、Ｃ：未使用、Ｄ：使用、Ｅ：未使用、Ｆ：使用、Ｇ：未使用の状態で、使用されていたＤを解放すると図２５（Ｕ）のように変化して、Ｄは未使用となり、そのサイズレンジが0x1000以上であるために、同じサイズレンジの未使用領域ＡとＧとの間に挿入される。
【００８５】
図２５において、非特許文献１に記載のアルゴリズムを適用すると、前の未使用領域はＡで
Ａのアドレス＋Ａのレングス＜Ｄのアドレス
次の未使用領域はＧで
Ｄのアドレス＋Ｄのレングス＜Ｇのアドレスとなり、
ＣとＤが連結されない、またＤとＥが連結されない。
【００８６】
そこで、Ｄ解放時にＣとＤとＥとを連結するために以下の方法を用いる。
【００８７】
メモリブロックＤのprev-flagをチェックすることで、隣接するメモリブロックCの状態（「使用中」または「未使用」）を取得する。（注）Ｄのprev-flagが「未使用」の場合、ＤのptrはＣの先頭アドレスを指す。メモリブロックＥのself-flagをチェックすることで、隣接するメモリブロックＥの状態（「使用中」または「未使用」）を取得する。（注）Ｄのsizeから、Ｅの先頭アドレスが求まる。
【００８８】
図２６にメモリ割当後にフリー領域が存在する場合のメモリ割当のメモリマップを示し、図２７にその動作のフローチャートを示す。この処理はメモリブロックＦを割当てる。ここで、メモリブロックＦのサイズは、メモリブロックＢのサイズより小さい。
【００８９】
以下にステップ毎の動作を説明する。
【００９０】
Ｓ１１：Ｅのprev-flagを「使用中」にセットする。
【００９１】
Ｓ１３：Ｅのself-flagを「未使用」にセットする。
【００９２】
Ｓ１５：Ｅのメモリサイズを算出し、sizeにセットする。
【００９３】
Ｓ１７：割当前のＢのメモリレンジに該当する「空きブロックのリスト」から、Ｂのメモリブロックを外す。
【００９４】
Ｓ１９：割当後のＥのメモリレンジに該当する「空きブロックのリスト」に、Ｅのメモリブロックを挿入する。
【００９５】
Ｓ２１：Ｆのprev-flagを「未使用」にセットする。
【００９６】
Ｓ２３：Ｆのself-flagを「使用中」にセットする。
【００９７】
Ｓ２５：Ｆのptrに、Ｅ（未使用）のブロックの先頭アドレスをセットする。
【００９８】
Ｓ２７：Ｆのsizeをセットする。
【００９９】
Ｓ２９：Ｇのprev-flagを「使用中」にセットする。
【０１００】
Ｓ３１：Ｇのptrに、ＮＵＬＬ（Ｆのメモリブロック使用中）をセットする。
【０１０１】
以上の一連の動作で割当後フリー領域が存在する場合のメモリ割当処理が完了する。
【０１０２】
図２８にメモリ割当後にフリー領域が存在しない場合のメモリ割当のメモリマップを示し、図２９にその動作のフローチャートを示す。この処理はメモリブロックＦを割当てる。ここで、メモリブロックＦのサイズは、メモリブロックＢのサイズと同じ。
【０１０３】
以下にステップ毎の動作を説明する。
【０１０４】
Ｓ４１：Ｅのprev-flagを「使用中」にセットする。
【０１０５】
Ｓ４３：Ｅのself-flagを「未使用」にセットする。
【０１０６】
Ｓ４５：Ｅのptrに、ＮＵＬＬ（Ｄのメモリブロック使用中）をセットする。
【０１０７】
Ｓ４７：割当前のＢのメモリレンジに該当する「空きブロックのリスト」から、Ｂのメモリブロックを外す。
【０１０８】
Ｓ４９：Ｆのprev-flagを「使用中」にセットする。
【０１０９】
Ｓ５１：Ｆのptrに、ＮＵＬＬ（Ｅのメモリブロック使用中）をセットする。
【０１１０】
以上の一連の動作で割当後フリー領域が存在しない場合のメモリ割当処理が完了する。
【０１１１】
図３０に下位アドレスに隣接するメモリブロックが未使用、上位アドレスに隣接するメモリブロックが使用中の場合のメモリ解放の動作前後のメモリマップを示し、図３１にその動作のフローチャートを示す。この処理はメモリブロックＢを解放する。Ｂのprev-flagが「未使用」、Ｃのself-flagが「使用中」なので、ＤとＥのメモリブロックを結合して解放する。
【０１１２】
以下にステップ毎の動作を説明する。
【０１１３】
Ｓ６１：ＤとＥの結合後のメモリサイズを算出し、Ｄのsizeにセットする。
【０１１４】
Ｓ６３：解放前のＡのメモリレンジに該当する「空きブロックのリスト」から、Ａのメモリブロックを外す。
【０１１５】
Ｓ６５：解放後のＤとＥを結合したメモリレンジに該当する「空きブロックのリスト」に、ＤとＥを結合したメモリブロックを挿入する。
【０１１６】
Ｓ６７：Ｆのprev-flagを「未使用」にセットする。
【０１１７】
Ｓ６９：Ｆのptrに、Ｄ（未使用）のブロックの先頭アドレスをセットする。
【０１１８】
以上の一連の動作で左隣接メモリブロックが未使用、右隣接メモリブロックが使用中の場合のメモリ解放処理を完了する。
【０１１９】
図３２に下位アドレスに隣接するメモリブロックが使用中、上位アドレスに隣接するメモリブロックが未使用の場合のメモリ解放の動作前後のメモリマップを示し、図３３にその動作のフローチャートを示す。この処理はメモリブロックＢを解放する。Ｂのprev-flagが「使用中」、Ｃのself-flagが「未使用」なので、ＦとＧのメモリブロックを結合して解放する。
【０１２０】
以下にステップ毎の動作を説明する。
【０１２１】
Ｓ７１：ＦとＧの結合後のメモリサイズを算出し、Ｆのsizeにセットする。
【０１２２】
Ｓ７３：Ｆのptrに、次の（同じメモリレンジの）未使用ブロックの先頭アドレスをセットする。
【０１２３】
Ｓ７５：Ｆのself-flagを「未使用」にセットする。
【０１２４】
Ｓ７７：解放前のＣのメモリレンジに該当する「空きブロックのリスト」から、Ｃのメモリブロックを外す。
【０１２５】
Ｓ７９：解放後のＦとＧを結合したメモリレンジに該当する「空きブロックのリスト」に、ＦとＧを結合したメモリブロックを挿入する。
【０１２６】
Ｓ８１：Ｈのptrに、Ｆ（未使用）のブロックの先頭アドレスをセットする。
【０１２７】
以上の一連の動作で左隣接メモリブロックが使用中、右隣接メモリブロックが未使用の場合のメモリ解放処理を完了する。
【０１２８】
図３４に上位アドレス、下位アドレスに隣接するメモリブロックが未使用の場合のメモリ解放の動作前後のメモリマップを示し、図３５にその動作のフローチャートを示す。この処理はメモリブロックＢを解放する。Ｂのprev-flagが「未使用」、Ｃのself-flagが「使用中」なので、ＥとＦとＧのメモリブロックを結合して解放する。
【０１２９】
以下にステップ毎の動作を説明する。
【０１３０】
Ｓ９１：Ｅ、Ｆ、Ｇの結合後のメモリサイズを算出し、Ｅのsizeにセットする。
【０１３１】
Ｓ９３：Ｅのptrに、次の（同じメモリレンジの）未使用ブロックの先頭アドレスをセットする。
【０１３２】
Ｓ９５：解放前のＡのメモリレンジに該当する「空きブロックのリスト」から、Ａのメモリブロックを外す。
【０１３３】
Ｓ９７：解放前のＣのメモリレンジに該当する「空きブロックのリスト」から、Ｃのメモリブロックを外す。
【０１３４】
Ｓ９９：解放後のＥとＦとＧを結合したメモリレンジに該当する「空きブロックのリスト」に、ＥとＦとＧを結合したメモリブロックを挿入する。
【０１３５】
Ｓ１０１：Ｈのptrに、Ｅ（未使用）のブロックの先頭アドレスをセットする。
【０１３６】
以上の一連の動作で上位アドレス、下位アドレスに隣接するメモリブロックが未使用の場合のメモリ解放処理を完了する。
【０１３７】
図３６に上位アドレス、下位アドレスに隣接するメモリブロックが使用中の場合のメモリ解放の動作前後のメモリマップを示し、図３７にその動作のフローチャートを示す。この処理はメモリブロックＢを解放する。Ｂのprev-flagが「使用中」、Ｃのself-flagが「使用中」なので、Ｅのメモリブロックだけを解放する。
【０１３８】
以下にステップ毎の動作を説明する。
【０１３９】
Ｓ１１１：Ｅのself-flagを「未使用」にセットする。
【０１４０】
Ｓ１１３：ＥのメモリサイズをＥのsizeにセットする。
【０１４１】
Ｓ１１５：解放後のＥのメモリレンジに該当する「空きブロックのリスト」に、Ｅのメモリブロックを挿入する。
【０１４２】
Ｓ１１７：Ｆのprev-flagを「未使用」にセットする。
【０１４３】
Ｓ１１９：Ｆのptrに、Ｅ（未使用）のブロックの先頭アドレスをセットする。
【０１４４】
以上の一連の動作で上位アドレス、下位アドレスに隣接するメモリブロックが使用中の場合のメモリ解放処理を完了する。
【０１４５】
［実施例の効果］
本発明実施例のメモリ管理システムにより、以下のことが可能となる。
【０１４６】
フラグメンテーションを効率的に回避することが可能となる。
【０１４７】
フラグメンテーションを回避する為の手段であるパーテーションを複数化することが可能となる。
【０１４８】
フラグメンテーションを回避する為の手段であるパーテーションの区切り位置を動的に変更することが可能となる。
【０１４９】
メモリの解放順序に制限を必要とせず、不要になったメモリから解放可能となる。
【０１５０】
未使用領域をそのサイズのレンジ毎に分類し、メモリの割当要求時に最適なサイズのメモリ領域を検索する際には、割当要求のサイズに適合するサイズレンジの中からのみ未使用領域を検索するため、検索にかかる時間が短くなる。
【符号の説明】
【０１５１】
２００  メモリマネージメント初期化部
２０１  変換テーブル管理部（物理パーテーション管理部、論理パーテーション管理部）
２１１  パーテーション管理部
２１３  パーテーションサイズ管理部
２１５  アドレス（物理・論理）管理部
２１７  ＩＤ管理部
２１９  フラグ（待機・停止）管理部
２２１  アドレス変換部（変換部）
２３１  物理アドレスから論理アドレスへの変換部
２３３  論理アドレスから物理アドレスへの変換部
２４１  メモリ統計情報管理部（物理パーテーション管理部）
２５１  メモリ使用ブロック数の管理部
２５３  メモリ使用バイト数の管理部
２５５  パーテーションの閾値チェック部
２５７  閾値種別管理部
２６１  ＭＣＢ管理部
２７１  malloc()処理部
２７３  free()処理部
【図１】
2010204762.tif 000007
【図２】
2010204762.tif 000008
【図３】
2010204762.tif 000009
【図４】
2010204762.tif 000010
【図５】
2010204762.tif 000011
【図６】
2010204762.tif 000012
【図７】
2010204762.tif 000013
【図８】
2010204762.tif 000014
【図９】
2010204762.tif 000015
【図１０】
2010204762.tif 000016
【図１１】
2010204762.tif 000017
【図１２】
2010204762.tif 000018
【図１３】
2010204762.tif 000019
【図１４】
2010204762.tif 000020
【図１５】
2010204762.tif 000021
【図１６】
2010204762.tif 000022
【図１７】
2010204762.tif 000023
【図１８】
2010204762.tif 000024
【図１９】
2010204762.tif 000025
【図２０】
2010204762.tif 000026
【図２１】
2010204762.tif 000027
【図２２】
2010204762.tif 000028
【図２３】
2010204762.tif 000029
【図２４】
2010204762.tif 000030
【図２５】
2010204762.tif 000031
【図２６】
2010204762.tif 000032
【図２７】
2010204762.tif 000033
【図２８】
2010204762.tif 000034
【図２９】
2010204762.tif 000035
【図３０】
2010204762.tif 000036
【図３１】
2010204762.tif 000037
【図３２】
2010204762.tif 000038
【図３３】
2010204762.tif 000039
【図３４】
2010204762.tif 000040
【図３５】
2010204762.tif 000041
【図３６】
2010204762.tif 000042
【図３７】
2010204762.tif 000043
【図３８】
2010204762.tif 000044