(57)【要約】  【課題】  メモリ領域の断片化の発生を抑制すると共に、高速な割り付け処理を行うことができるメモリ管理システムを提供する。  【解決手段】  割り付けを要求されたデータに対して、当該メモリ領域の空き領域を選択して可変長の領域のメモリの割り付けを行うメモリ管理システムにおいて、前記空き領域の探査方向をメモリアドレスの昇順とするか又は降順とするかを決するために用いる基準サイズを記憶する基準サイズ記憶手段を備え、前記データのサイズが、前記基準サイズ以上の場合は探査方向を降順（Ｓ３）、前記基準サイズ未満の場合は探査方向を昇順（Ｓ４）としつつ、前記データのサイズ以上のサイズを有するものとして最初に探査された空き領域を選択して前記データに対するメモリの割り付けを行う（Ｓ５、Ｓ６）。【選択図】      図２
2005157714.tif 000002
【特許請求の範囲】
【請求項１】
割り付けを要求されたデータに対して、当該メモリ領域の空き領域を選択して可変長の領域のメモリの割り付けを行うメモリ管理システムにおいて、
前記空き領域の探査方向を決するために用いる基準サイズを記憶する基準サイズ記憶手段を備え、
前記データのサイズが前記基準サイズより大きい場合と小さい場合とで、前記探査方向をメモリアドレスの昇順とするかと降順とするかとを互いに逆にしつつ、前記データのサイズ以上のサイズを有するものとして最初に探査された空き領域を選択して前記データに対するメモリの割り付けを行うことを特徴とするメモリ管理システム。
【請求項２】
前記データのサイズ以上のサイズを有する空き領域がない場合に、
前記基準サイズを前記データのサイズで書き換えて記憶することを特徴とする請求項１に記載のメモリ管理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置や画像処理装置などのメモリを使用する装置に適用可能なメモリ管理システムに関する。
【背景技術】
【０００２】
従来より、メモリ領域に対して割り付け要求がなされた際に、散在する空き領域中のいずれかを選択し、可変長の領域のメモリを割り付ける（動的にメモリを割り付ける）場合の代表的なアルゴリズムとして、最初適合（ｆｉｒｓｔ−ｆｉｔ）法と最良適合（ｂｅｓｔ−ｆｉｔ）法の２種類が一般的に知られている。
【０００３】
最初適合法とは、割り付けを要求されたデータが格納され得る空き領域を、空き領域のサイズの大きさに関係なくメモリアドレスの昇順に探査し、最初に探査された空き領域を選択して割り付けを行う方法である。
【０００４】
また、最良適合法とは、メモリ中に散在している全ての空き領域を探査し、割り付け要求のあったデータのサイズとの差が最小となるようなサイズの空き領域を選択して割り付けを行う方法である。
【０００５】
また、他の従来技術として、過去の割り付け要求がされたデータのサイズの統計をとって、その大きさに準じてクラス分けをし、割り付け要求の回数が多いクラス順に、割り付け要求サイズに適合する空き領域を選択するものがある（例えば、特許文献１参照）。
【特許文献１】特開平０９−０１６４６３号公報
【０００６】
＜＜背景技術の動作の説明：具体例１＞＞
最初適合法のアルゴリズムを適用した従来のメモリ管理システムの動作を、図７に示される具体例を用いて説明する。図７は、最初適合法のアルゴリズムを適用した従来のメモリ管理システムにおけるメモリ１０５の使用状況の第１例を示す図である。
【０００７】
図７（ａ）は、メモリ１０５に対して、全領域が未使用（空き）の状態から、サイズが１キロバイトと３２キロバイトのデータの割り付けを、交互にそれぞれ４回づつ行った後のメモリ１０５の使用状況を表している。図７（ｂ）は、図７（ａ）の状態から、サイズが１キロバイトのデータを割り付けられた４つの領域を削除（開放）した後のメモリ１０５の使用状況を表している。
【０００８】
メモリ１０５は複数の情報（データ）を記憶することができ、また、各情報を記憶する場所を特定するための番号がメモリ１０５には付されている。この番号をアドレス（番地）、またはメモリアドレスといい、例えば１６進数表示で０ｘ００００〜０ｘ８０００までの連番がアドレスとして付される。この場合の「０ｘ００００」、「０ｘ８０００」のアドレスをそれぞれ最上位アドレス、最下位アドレスという。また、２つのアドレスを比較した際、番号（数字）が小さい方を上位アドレス、番号が大きい方を下位アドレスという。
【０００９】
図７（ａ）及び図７（ｂ）の図中において、上方側がメモリ１０５の上位アドレス側、下方側が下位アドレス側を表しており、メモリ１０５の上端はそれぞれの最上位アドレス、下端はそれぞれの最下位アドレスに対応している。
【００１０】
図７（ａ）に示されるように、最初適合法においては、割り付けを要求されたデータが格納され得る空き領域を、空き領域のサイズの大きさに関係なくメモリアドレスの昇順に探査し、最初に探査された空き領域を選択して割り付けを行うため、サイズが１キロバイトと３２キロバイトのデータの割り付けが、メモリ１０５の最上位アドレスより交互に、且つ連続してなされている。尚、データの割り付けがなされた領域は、図中「使用中」と表されており、サイズが１キロバイトと３２キロバイトのデータの割り付けがなされていない領域は、空き領域（図中「空き」と表示）となっている。
【００１１】
そして、サイズが１キロバイトのデータを割り付けられた使用中の領域（計４つ）が削除されると、図７（ｂ）に示されるように、サイズが３２キロバイトのデータを割り付けられた使用中の領域と隣接して、サイズが１キロバイトの空き領域が４つ生成され、メモリ領域の断片化が生じることとなる。
【００１２】
尚、最初適合法のアルゴリズムを適用した従来のメモリ管理システムに関し、図７（ａ）、図７（ｂ）を用いて上述の説明をしたが、最初適合法のアルゴリズムに代えて最良適合法のアルゴリズムを適用した場合であっても、最初適合法のアルゴリズムを適用した従来のメモリ管理システムと同様に、メモリ領域の断片化は生じることとなる。
【００１３】
＜＜背景技術の動作の説明：具体例２＞＞
更に、図８に示される別の具体例を用いて、最初適合法のアルゴリズムを適用した従来のメモリ管理システムの動作を説明する。図８は、最初適合法のアルゴリズムを適用した従来のメモリ管理システムにおけるメモリ１０５の使用状況の第２例を示す図である。
【００１４】
図８（ａ）は、当初、サイズが４キロバイト、２０キロバイト、８キロバイト、３２キロバイトの４つのデータ、及びその他のデータをメモリ１０５に割り付け、その後それら４つのデータ、即ちサイズが４キロバイト、２０キロバイト、８キロバイト、３２キロバイトのデータの割り付けを削除（開放）した場合のメモリ１０５の使用状況を表している。メモリ１０５に対する前記「４つのデータ」それぞれの割り付け前後にも、「他のデータ」の割り付けがなされており、それら「他のデータ」の割り付けは削除されていないものとする。それら「他のデータ」が割り付けられた領域は、図８（ａ）中、「使用中」と記載された部分に相当している。
【００１５】
図８（ｂ）は、図８（ａ）の状態から、サイズが６キロバイトと３２キロバイトのデータの割り付けを更に行った後のメモリ１０５の使用状況を表している。尚、図８（ａ）中、実線の矢印及び破線の矢印は、それぞれ更に割り付けを要求されたサイズが６キロバイト、３２キロバイトのデータが格納されるべき空き領域を探査する順序を示している。
【００１６】
図８（ａ）及び図８（ｂ）の図中において、上方側がメモリ１０５の上位アドレス側、下方側が下位アドレス側を表しており、メモリ１０５の上端はそれぞれの最上位アドレス、下端はそれぞれの最下位アドレスに対応している。また、メモリ１０５において、当初割り付けられた「サイズが４キロバイト、２０キロバイト、８キロバイト、３２キロバイトの４つのデータ」は、サイズが４キロバイト、２０キロバイト、８キロバイト、３２キロバイトのデータの順に割り付けられたものとし、それぞれの割り付けが開放された後の空き領域を、以下、それぞれ空きＡ、空きＢ，空きＣ，空きＤと言う。
【００１７】
最初適合法においては、割り付けを要求されたデータが格納され得る空き領域を、空き領域のサイズの大きさに関係なくメモリアドレスの昇順に探査し、最初に探査された空き領域を選択して割り付けを行うため、当初割り付けられた「サイズが４キロバイト、２０キロバイト、８キロバイト、３２キロバイトの４つのデータ」は、メモリ１０５の上位アドレス側からこの順番で割り付けられ、それら４つのデータに係る割り付けが開放された後は、図８（ａ）に示されるようなメモリの使用状況となる。即ち、メモリ１０５の上位アドレス側から、空きＡ、空きＢ、空きＣ、空きＤの順番に空き領域が発生する。
【００１８】
そして、図８（ａ）の状態から更にサイズが６キロバイトのデータの割り付けを行う際、以下のように、上位アドレス側から空き領域が探査される（図８（ａ）中の実線の矢印を参照）。
（ステップ１）：空きＡのサイズ（４キロバイト）と、６キロバイトが比較されるが、割り付けできないので、次の空き領域を検索する。
（ステップ２）：空きＢのサイズ（２０キロバイト）に、６キロバイトのサイズのメモリ領域を確保することができるため、空きＢを選択して割り付ける。
【００１９】
このように、サイズが６キロバイトのデータの割り付けにとっては、より空き領域のサイズとの差が小さい空きＣ（サイズが８キロバイト）を選択するのが最適であるのに関わらず、最初適合法のアルゴリズムを適用した場合は、空きＢを選択してしまう。従って、図８（ｂ）に示すように、空きＢにサイズが６キロバイトのデータを割り付けることで残存した新たな空き領域（空きＢ’）のサイズは、２０キロバイトから６キロバイトを差し引いた１４キロバイトになり、次回、サイズが２０キロバイトのデータについて割り付け要求が発生した時、そのデータを空きＢ’に格納できなくなる（つまり、メモリ不足となる）。
【００２０】
また、図８（ａ）の状態から更にサイズが３２キロバイトのデータの割り付けを行う際、以下のように、上位アドレス側から空き領域が探査される（図８（ａ）中の破線の矢印を参照）。
（ステップ１）：空きＡのサイズ（４キロバイト）と、３２キロバイトが比較されるが、割り付けできないので、次の空き領域を検索する。
（ステップ２）：空きＢのサイズ（２０キロバイト）と、３２キロバイトが比較されるが、割り付けできないので、次の空き領域を検索する。
（ステップ３）：空きＣのサイズ（８キロバイト）と、３２キロバイトが比較されるが、割り付けできないので、次の空き領域を検索する。
（ステップ４）：空きＤのサイズ（３２キロバイト）に、３２キロバイトのサイズのメモリ領域を確保することができるため、空きＤを選択して割り付ける。
【００２１】
このように、最初適合法のアルゴリズムを適用した場合は、サイズが３２キロバイトのデータが格納され得る空きＤを選択するまでに、空きＤの位置するアドレスより上位にある全ての空き領域（空きＡ、空きＢ、空きＣ）についても選択できるか否かの判断を行うことになり、無駄が生じ、割り付け処理に多大な時間を費やしてしまう。
【００２２】
＜＜背景技術の動作の説明：具体例３＞＞
更に、図９に示される別の具体例を用いて、最初適合法のアルゴリズムを適用した従来のメモリ管理システムの動作を説明する。図９は、最初適合法のアルゴリズムを適用した従来のメモリ管理システムにおけるメモリ１０５の使用状況の第３例を示す図である。
【００２３】
図９（ａ）はメモリ１０５に対して、全領域が未使用（空き）の状態から複数のデータの割り付けを行った後のメモリ１０５の使用状況を表したものである。但し、その割り付け後も、メモリ１０５には空き領域が残存しているものとする。
【００２４】
図９（ａ）及び図９（ｂ）の図中において、上方側がメモリ１０５の上位アドレス側、下方側が下位アドレス側を表しており、メモリ１０５の上端はそれぞれの最上位アドレス、下端はそれぞれの最下位アドレスに対応している。
【００２５】
最初適合法においては、割り付けを要求されたデータが格納され得る空き領域を、空き領域のサイズの大きさに関係なくメモリアドレスの昇順に探査し、最初に探査された空き領域を選択して割り付けを行うため、図９（ａ）に示すように、メモリ１０５の上位アドレス側にまとまってデータが割り付けられて「使用中」となっており、下位アドレス側は空き領域（図中、「空き」と表示）となっている。
【００２６】
図９（ｂ）は、図９（ａ）の状態から、新たにサイズがそれぞれ８キロバイト、２０キロバイト、３２キロバイトのデータＳ、データＴ、データＵに対する割り付けを、この順番で行った場合のメモリ１０５の使用状況を表したものである。最初適合法においては、割り付けを要求されたデータが格納され得る空き領域を、空き領域のサイズの大きさに関係なくメモリアドレスの昇順に探査し、最初に探査された空き領域を選択して割り付けを行うため、図９（ｂ）に示すように、図９（ａ）で「使用中」であった領域に連続した下位アドレス側の領域に、データＳ、データＴ、データＵに対する割り付けがこの順番で行われる。
【００２７】
次に、図９（ｂ）の状態から、データＳ、データＴ、データＵのいずれか１つを削除（開放）した場合のメモリ領域の断片化の発生の有無について検討する。
【００２８】
まず、図９（ｂ）に示す状態にあるメモリ１０５からデータＵの割り付けのみを削除（開放）しても、データＵの割り付けられた領域は既に存在している空き領域と隣接しているため、メモリ領域の断片化は生じない。
【００２９】
しかし、図９（ｂ）に示す状態にあるメモリ１０５からデータＴの割り付けのみを削除（開放）すると、データＴの割り付けられた領域は、データＳとデータＵの割り付けられた領域の間にあるため、メモリ領域の断片化が生じる。
【００３０】
更に、図９（ｂ）に示す状態にあるメモリ１０５からデータＳの割り付けのみを削除（開放）した場合でも、データＳの割り付けられた領域は既に存在している空き領域に隣接していないため、メモリ領域の断片化が生じてしまう。従って、（後述するように本発明と比較にした場合に明らかとなるが）最初適合法のアルゴリズムを採用した場合はメモリ領域の断片化が生じやすいと言える。
【発明の開示】
【発明が解決しようとする課題】
【００３１】
上述のとおり、最初適合法を採用した場合、常にメモリ領域の先頭から空き領域が探査され、割り付けを要求されたデータを格納し得る空き領域が見つかり次第割り付けがなされるため、必然的にメモリ領域の先頭付近の利用頻度が他の部分に比べて高くなる。従って、メモリ領域の先頭付近にメモリ領域の断片化（フラグメンテーション）が頻繁に発生し、メモリ不足が発生しやすくなるという問題があった。また、割り付けを要求されたデータを格納し得る空き領域がメモリアドレスの下位アドレス側にしかない場合であっても、その空き領域より上位アドレス側にある全ての空き領域に対し選択できるか否かの判断を行うため、無駄が生じ、割り付け処理に多大な時間を費やしてしまうという問題があった。
【００３２】
また、最良適合法を採用した場合、メモリ領域中に散在している空き領域の全てを探査する必要があるため、割り付け処理に費やす時間が大きくなるという問題があった。
【００３３】
また、特許文献１に記載の従来構成例は、空き領域の無駄な検索処理を軽減することを目的としているが、割り付け要求がされた回数が少ないクラスに属するサイズの割り付け要求がされた場合は、結局最後に探査されるため、かえって割り付け処理に多大な時間を費やしてしまう。従って、選択される全てのサイズについて統計的に見ると、割り付け処理の迅速性に問題があった。
【００３４】
本発明は、上記の点に鑑み、メモリ領域の断片化の発生を抑制すると共に、高速な割り付け処理を行うことができるメモリ管理システムを提供することを目的とする。
【課題を解決するための手段】
【００３５】
上記目的を達成するために本発明は、割り付けを要求されたデータに対して、当該メモリ領域の空き領域を選択して可変長の領域のメモリの割り付けを行うメモリ管理システムにおいて、前記空き領域の探査方向を決するために用いる基準サイズを記憶する基準サイズ記憶手段を備え、前記データのサイズが前記基準サイズより大きい場合と小さい場合とで、前記探査方向をメモリアドレスの昇順とするかと降順とするかとを互いに逆にしつつ、前記データのサイズ以上のサイズを有するものとして最初に探査された空き領域を選択して前記データに対するメモリの割り付けを行うようにしている。
【００３６】
これにより、メモリ領域の断片化の発生を抑制すると共に、高速な割り付け処理を行うことができる。
【００３７】
また、前記データのサイズ以上のサイズを有する空き領域がない場合に、前記基準サイズを前記データのサイズで書き換えて記憶するようにしても良い。
【００３８】
これにより、前記基準サイズは、割り付け要求元であるプログラム等にとって適切な（統計的に最適な）値に自動的に更新される。
【発明の効果】
【００３９】
上述した通り、本発明に係るメモリ管理システムによれば、メモリ領域の断片化の発生を抑制すると共に、高速な割り付け処理を行うことができる。
【発明を実施するための最良の形態】
【００４０】
以下、本発明について図面を参照しながら詳細に説明する。図１は、本発明の実施の形態に係るメモリ管理システム１０の構成図であり、中央演算処理装置（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１（以下「ＣＰＵ１」という）によって制御が行われるオペレーティングシステム２（以下「ＯＳ２」という）上で、プログラム３が稼動している例である。
【００４１】
プログラム３やＯＳ２がメモリを必要とする処理を行う際、そのメモリの要求はＣＰＵ１に送られて、ＣＰＵ１からメモリ管理手段４にメモリ要求として送出される。メモリ管理手段４は、このメモリ要求を受けてメモリ５内に要求されたサイズのメモリ領域を割り付けて確保する。その場合、メモリ管理手段４は割り付けを行う前処理として、管理領域６で記憶されているメモリ５に関する管理情報を参照して、メモリ５内における空き領域を探査する。
【００４２】
本実施形態に係るメモリ管理システム１０は、メモリ５の管理を可変長メモリ管理方式、即ちメモリ５に対して割り付け要求がなされた際に、散在する空き領域中のいずれかを選択し、可変長の領域のメモリを割り付ける（動的にメモリを割り付ける）方式を採用している。
【００４３】
メモリ５は複数の情報（データ）を記憶することができ、また、各情報を記憶する場所を特定するための番号がメモリ５には付されている。この番号をアドレス（番地）、またはメモリアドレスといい、例えば１６進数表示で０ｘ００００〜０ｘ８０００までの連番がアドレスとして付される。この場合の「０ｘ００００」、「０ｘ８０００」のアドレスをそれぞれ最上位アドレス、最下位アドレスという。また、２つのアドレスを比較した際、番号（数字）が小さい方を上位アドレス、番号が大きい方を下位アドレスという。尚、説明の便宜上、図１においてメモリ５と管理領域６は分離して記載しているが、管理領域６は、メモリ５の内部に設けても構わない。
【００４４】
以下、本実施形態に係るメモリ管理システム１０のメモリ領域の割り付け動作について、図２を参照しながら説明する。図２は、図１におけるメモリ管理システム１０の動作を説明するためのフローチャートである。
【００４５】
まず、ステップＳ１において、データのサイズがαの割り付け要求が発生したとする。ステップＳ１を経て移行するステップＳ２では、サイズαが、管理領域６に記憶されている「基準サイズ」と比較される。ここで、この「基準サイズ」は、後述するように空き領域の探査方向をメモリアドレスの昇順とするか降順とするかを決定するために用いられるものであり、後述するように、初期値は駆動するプログラム３やＯＳ２に応じて適宜決定される。
【００４６】
サイズαが「基準サイズ」以上である場合は（ステップＳ２のＹ）、空き領域の探査方向を降順と決定する（ステップＳ３）。即ち、メモリ５内の最下位アドレスより上位アドレス側に向かって空き領域を探査する（例えば、メモリアドレス０ｘ８０００より０ｘ００００に向かって探査する）よう探査方向を決定する。一方、サイズαが「基準サイズ」より小さい場合は（ステップＳ２のＮ）、空き領域の探査方向を昇順と決定する（ステップＳ４）。即ち、メモリ５内の最上位アドレスより下位アドレス側に向かって空き領域を探査する（例えば、メモリアドレス０ｘ００００より０ｘ８０００に向かって探査する）よう探査方向を決定する。
【００４７】
尚、新たな割り付け要求が発生する度に（ステップＳ１が実行される度に）、ステップＳ２の判定はなされる為、その都度、空き領域の探査方向は変わりうる。
【００４８】
ステップＳ３又はステップＳ４で空き領域の探査方向が決定されると、その決定された探査方向で空き領域を探し、見つかった空き領域のサイズがサイズα以上であるか否かがチェックされる（ステップＳ５）。そして、その見つかった空き領域のサイズがサイズα以上である場合は（ステップＳ５のＹ）、その空き領域を選択して割り付けを要求されたデータの割り付けを行う（ステップＳ６）。
【００４９】
一方、探査された空き領域のサイズがサイズαより小さい場合は、ステップＳ７に移行し、メモリ５の全領域にわたって空き領域の探査が行われたか否かを判定する。
【００５０】
未だ、メモリ５の全領域にわたって空き領域の探査が行われていない場合は（ステップＳ７のＮ）、上述のステップＳ５に戻り、引き続き空き領域の探査を行うが、既にメモリ５の全領域にわたって空き領域の探査を行っている場合は（ステップＳ７のＹ）、空き領域が不足しているため割り付けできないとして、ステップＳ８に移行する。
【００５１】
ステップＳ８では、メモリ管理手段４がＣＰＵ１に対して「割り付け不可能」の信号を伝達する等の割り付け不可能に係わるエラー処理を行うとともに、「基準サイズ」の値をサイズαの値で書き換える。この「基準サイズ」の値をサイズαの値で書き換えることの意義については後述する。
【００５２】
上述したように、メモリ管理システム１０では、割り付けを要求されたデータのサイズαが「基準サイズ」以上の場合と「基準サイズ」未満の場合とで、空き領域の探査方向をメモリアドレスの昇順とするかと降順とするかとを互いに逆にしつつ（メモリアドレスの昇順とするかと降順とするかとを異にしつつ）、サイズα以上のサイズを有するものとして最初に探査された空き領域を選択して割り付けを要求されたデータの割り付けを行う。
【００５３】
＜＜動作の説明：具体例１＞＞
次に、背景技術の欄で説明した最初適合法のアルゴリズムを適用した従来のメモリ管理システムと比較しながら、本実施形態に係るメモリ管理システム１０の動作を、図３に示される具体例を用いて説明する。図３は、図１における管理領域６に記憶される内容の一部及びメモリ５の使用状況の第１例を示す図であり、背景技術の欄で図７を用いて説明したメモリ領域の割り付け処理と同様の割り付け処理をメモリ管理システム１０において実行させた場合のメモリの使用状況を示したものである。
【００５４】
図３（ａ）は、図７（ａ）と同様、メモリ５に対して全領域が未使用（空き）の状態から、サイズが１キロバイトと３２キロバイトのデータの割り付けを交互にそれぞれ４回づつ行った後のメモリ５の使用状況を表している。図３（ｂ）は、図７（ｂ）と同様、図３（ａ）の状態から、サイズが１キロバイトのデータを割り付けられた４つの領域を開放した後のメモリ５の使用状況を表している。また、図３（ａ）及び図３（ｂ）における管理領域６に記憶されている「基準サイズ」は、ともに１６キロバイトとなっている。
【００５５】
図３（ａ）及び図３（ｂ）の図中において、上方側がメモリ５の上位アドレス側、下方側が下位アドレス側を表しており、メモリ５の上端はそれぞれの最上位アドレス、下端はそれぞれの最下位アドレスに対応している。
【００５６】
割り付けを要求されたデータのサイズである１キロバイトは「基準サイズ」（１６キロバイト未満）であるため、上述したように空き領域の探査方向は昇順となり（図２のステップＳ４参照）、３２キロバイトは「基準サイズ」（１６キロバイト）以上であるため、上述したように空き領域の探査方向は降順となる（図２のステップＳ３参照）。
【００５７】
従って、図３（ａ）に示されるように、メモリ５の最上位アドレスから下位アドレス側に向かってサイズが１キロバイトのデータが４つ連続して割り付けられ、最下位アドレスから上位アドレス側に向かってサイズが３２キロバイトのデータが４つ連続して割り付けられる。また、データの割り付けのなされていないメモリ空間の中央付近には、１つの空き領域が残存する。
【００５８】
そうすると、サイズが１キロバイトのデータを割り付けられた領域（計４つ）が削除されても、図３（ｂ）に示されるように、サイズが１キロバイトの４つの空き領域は、サイズが３２キロバイトのデータを割り付けられた領域と隣接していない上位アドレス側にまとまって発生するため、メモリ領域の断片化は生じず、図３（ａ）の状態から既に存在していた空き領域と削除された領域とを併合した１つの連続した空き領域が生成されることとなる。
【００５９】
背景技術の欄で図７を用いて説明した最初適合法のアルゴリズムを適用した従来のメモリ管理システムにおいて同様の処理を行うと、図７（ｂ）に示されるようにメモリ１０５にはメモリ領域の断片化が生じてしまうが、上述したようにメモリ５にはメモリ領域の断片化が生じない。従って、本実施形態に係るメモリ管理システム１０においては、メモリ領域の断片化が生じにくく、メモリ領域の断片化に起因するメモリ不足の発生を抑制することができる。
【００６０】
また、特に情報処理装置や入出力装置、或いは画像処理装置などでデータ処理が行われる場合、ある特定の固定データサイズのデータが頻繁に処理される。例えば、固定データサイズの入出力バッファを介して転送され、処理されるデータは１キロバイトなどのように固定サイズであり、画像処理の場合に、画像の１ラインごとに処理されるデータも固定サイズである。
【００６１】
そして、固定サイズでありながら互いにサイズの異なるデータについての割り付け要求が交互に（または交互ではなくても入り交じって）発生することにより、図３（ａ）や図７（ａ）に示されるような状態になることは、通常且つ頻繁に起こりうる。また、例えば、一連の画像処理が終了すれば全ラインのデータが不要となる場合等、ある固定サイズを有する複数のデータの割り付けが一斉に削除（解放）されることにより、図３（ｂ）や図７（ｂ）に示されるような状態になることも、通常且つ頻繁に起こりうる。従って、上述の情報処理装置等に本実施形態に係るメモリ管理システム１０を適用すれば、メモリの断片化に起因するメモリ不足の発生を抑制することができるため、特に有用であるといえる。
【００６２】
＜＜動作の説明：具体例２＞＞
更に、図４に示される別の具体例を用いて、最初適合法のアルゴリズムを適用した従来のメモリ管理システムと比較しながら、本実施形態に係るメモリ管理システム１０の動作を説明する。図４は、図１における管理領域６に記憶される内容の一部及びメモリ５の使用状況の第２例を示す図であり、背景技術の欄で図８を用いて説明したメモリ領域の割り付け処理と同様の割り付け処理をメモリ管理システム１０において実行させた場合のメモリの使用状況を示したものである。
【００６３】
図４（ａ）は、図８（ａ）と同様、当初、サイズが４キロバイト、２０キロバイト、８キロバイト、３２キロバイトの４つのデータ、及びその他のデータが本実施形態に係るメモリ管理システム１０に備えれらるメモリ５に割り付け、その後それら４つのデータ、即ちサイズが４キロバイト、２０キロバイト、８キロバイト、３２キロバイトのデータの割り付けを削除（開放）した場合のメモリ５の使用状況を表している。図８（ａ）を用いて説明したメモリ１０５に対するものと同様、メモリ５に対する前記「４つのデータ」それぞれの割り付け前後にも、「他のデータ」の割り付けがなされており、それら「他のデータ」の割り付けは削除されていないものとする。それら「他のデータ」が割り付けられた領域は、図４（ａ）中、「使用中」と記載された部分に相当している。
【００６４】
図４（ｂ）は、図８（ｂ）と同様、図４（ａ）の状態から、サイズが６キロバイトと３２キロバイトのデータの割り付けを更に行った後のメモリ５の使用状況を表している。また、図４（ａ）及び図４（ｂ）における管理領域６に記憶されている「基準サイズ」は１６キロバイトとなっている。尚、図４（ａ）中、実線の矢印及び破線の矢印は、それぞれ更に割り付けを要求されたサイズが６キロバイト、３２キロバイトのデータが格納されるべき空き領域を探査する順序を示している。
【００６５】
図４（ａ）及び図４（ｂ）の図中において、上方側がメモリ５の上位アドレス側、下方側が下位アドレス側を表しており、メモリ５の上端はそれぞれの最上位アドレス、下端はそれぞれの最下位アドレスに対応している。また、メモリ５において、当初割り付けられた「サイズが４キロバイト、２０キロバイト、８キロバイト、３２キロバイトの４つのデータ」は、サイズが４キロバイト、２０キロバイト、８キロバイト、３２キロバイトのデータの順に割り付けられたものとし、それぞれの割り付けが開放された後の空き領域を、メモリ１０５におけるものと同様（図８参照）、それぞれ空きＡ、空きＢ，空きＣ，空きＤと言う。
【００６６】
メモリ５に対して、当初割り付けられた「サイズが４キロバイト、２０キロバイト、８キロバイト、３２キロバイトの４つのデータ」のうち、サイズが４キロバイト及び８キロバイトのデータは、サイズが「基準サイズ」（１６キロバイト）未満であるため、上述したように空き領域の探査方向は昇順となり（図２のステップＳ４参照）、上位アドレス側から下位アドレス側に向かってサイズが４キロバイトのデータ、サイズが８キロバイトのデータが、この順番で割り付けられる。
【００６７】
当初割り付けられた「サイズが４キロバイト、２０キロバイト、８キロバイト、３２キロバイトの４つのデータ」のうち、サイズが２０キロバイト及び３２キロバイトのデータは、サイズが「基準サイズ」（１６キロバイト）以上であるため、上述したように空き領域の探査方向は降順となり（図２のステップＳ３参照）、下位アドレス側から上位アドレス側に向かってサイズが２０キロバイトのデータ、サイズが３２キロバイトのデータが、この順番で割り付けられる。
【００６８】
そして、それらの当初割り付けられた「４つのデータ」に係る割り付けが開放された後は、図４（ａ）に示されるようなメモリの使用状況となる。即ち、上位アドレス側から、空きＡ、空きＣ、空きＤ、空きＢの順番に空き領域が発生する。
【００６９】
図４（ａ）の状態から更にサイズが６キロバイトのデータの割り付けを行う際は、そのサイズが「基準サイズ」（１６キロバイト）未満であるため、上述したように空き領域の探査方向は昇順となり（図２のステップＳ４参照）、以下のように、上位アドレス側から空き領域が探査される（図４（ａ）中の実線の矢印を参照）。
（ステップ１）：空きＡのサイズ（４キロバイト）と、６キロバイトが比較されるが、割り付けできないので、次の空き領域を検索する。
（ステップ２）：空きＣのサイズ（８キロバイト）に、６キロバイトのサイズのメモリ領域を確保することができるため、空きＣを選択して割り付ける。
【００７０】
このように、サイズが６キロバイトのデータを更に割り付けるに際して、最初適合法のアルゴリズムを適用したメモリ管理システムにおいては、上述したように（図８（ｂ）参照）、サイズが２０キロバイトの空きＢを選択したのに対し、本実施形態に係るメモリ管理システム１０においては、割り付けを要求されたデータのサイズ（６キロバイト）と空き領域のサイズとの差がより小さい空きＣを選択することとなる。
【００７１】
これは、「基準サイズ」（１６キロバイト）未満のサイズを有するデータの割り付けは最上位アドレスから降順に、「基準サイズ」以上のサイズを有するデータの割り付けは最下位アドレスから昇順に、空き領域を探査することにより、上位アドレス側には「基準サイズ」未満のサイズを有する比較的小さな空き領域が、下位アドレス側には「基準サイズ」以上のサイズを有する比較的大きな空き領域が集まりやすくなっていることに起因している。
【００７２】
そして、図４（ｂ）に示すように、空きＣにサイズが６キロバイトのデータを割り付けることで残存した新たな空き領域（空きＣ’）のサイズは、８キロバイトから６キロバイトを差し引いた２キロバイトとなるが、空きＢは、図８（ｂ）の空きＢ’（サイズが１４キロバイト）と異なり２０キロバイトのサイズを維持しているため、次回、サイズが２０キロバイトのデータについての割り付け要求が発生しても、空きＢにそのデータを格納することができる。従って、本実施形態に係るメモリ管理システム１０は、メモリ不足が発生しにくく、メモリの使用効率が良いといえる。
【００７３】
また、図４（ａ）の状態から更にサイズが３２キロバイトのデータの割り付けを行う際は、そのサイズが「基準サイズ」（１６キロバイト）以上であるため、上述したように空き領域の探査方向は降順となり（図２のステップＳ３参照）、以下のように、下位アドレス側から空き領域が探査される（図中、破線の矢印参照）。
（ステップ１）：空きＢのサイズ（２０キロバイト）と、３２キロバイトが比較されるが、割り付けできないので、次の空き領域を検索する。
（ステップ２）：空きＤのサイズ（３２キロバイト）に、３２キロバイトのサイズのメモリ領域を確保することができるため、空きＤを選択して割り付ける。
【００７４】
このように、サイズが３２キロバイトのデータを更に割り付けるに際して、背景技術の欄で図８を用いて説明した最初適合法のアルゴリズムを適用した従来のメモリ管理システムにおいては、４つの空き領域全てを検索する必要があったが、メモリ管理システム１０においては、２つの空き領域（空きＢ、空きＤ）を検索するだけで割る付けるべき空き領域の探査が完了している。
【００７５】
これも、「基準サイズ」（１６キロバイト）未満のサイズを有するデータの割り付けは最上位アドレスから降順に、「基準サイズ」以上のサイズを有するデータの割り付けは最下位アドレスから昇順に、空き領域を探査することにより、上位アドレス側には「基準サイズ」未満のサイズを有する比較的小さな空き領域が、下位アドレス側には「基準サイズ」以上のサイズを有する比較的大きな空き領域が集まりやすくなっていることに起因している。
【００７６】
つまり、「基準サイズ」以上のサイズのデータを新たに割り付ける場合は、「基準サイズ」以上のサイズを有する比較的大きな空き領域が集まっている上位アドレス側を優先的に探査することとなるため、「基準サイズ」未満のサイズの空き領域が集まりやすい上位アドレス側の空き領域を無駄に探査することが抑制されて、より高速に割り付けるべき空き領域の探査が完了するわけである。
【００７７】
従って、本実施形態に係るメモリ管理システム１０は、メモリ領域の断片化の発生を抑制すると共に、高速な割り付け処理を行うことができると言える。
【００７８】
また、最初適合法のアルゴリズムを採用した場合は、上述したようにメモリ領域の上位アドレス側（先頭付近）の利用頻度が他の部分（下位アドレス側等）に比べて高くなるため、メモリ領域の先頭付近にメモリ領域の断片化が頻繁に発生することとなるが、本実施形態に係るメモリ管理システム１０においては、メモリ領域の上位アドレス側と下位アドレス側の利用頻度の偏りが軽減されているため、メモリ領域の断片化の発生が抑制されるといえる。
【００７９】
＜＜動作の説明：具体例３＞＞
更に、図５に示される別の具体例を用いて、最初適合法のアルゴリズムを適用した従来のメモリ管理システムと比較しながら、本実施形態に係るメモリ管理システム１０の動作を説明する。図５は、図１における管理領域６に記憶される内容の一部及びメモリ５の使用状況の第３例を示す図であり、背景技術の欄で図９を用いて説明したメモリ領域の割り付け処理と同様の割り付け処理をメモリ管理システム１０において実行させた場合のメモリの使用状況を示したものである。
【００８０】
図５（ａ）は、メモリ５に対して全領域が未使用（空き）の状態から、複数のデータの割り付けを行った後のメモリ５の使用状況を表したものである。この複数のデータは、図９（ａ）を用い背景技術の欄にて説明した「メモリ１０５に対して全領域が未使用の状態から割り付けた複数のデータ」と全く同じものとし（図９（ａ）参照）、その割り付けられた複数のデータの中には、図５（ａ）及び図５（ｂ）に示す管理領域６に記憶されている「基準サイズ」（１６キロバイト）以上のサイズを有するデータと、「基準サイズ」未満のサイズを有するデータが含まれているものとする。また、その割り付け後もメモリ５には空き領域が残存しているものとする。
【００８１】
図５（ａ）及び図５（ｂ）の図中において、上方側がメモリ５の上位アドレス側、下方側が下位アドレス側を表しており、メモリ５の上端はそれぞれの最上位アドレス、下端はそれぞれの最下位アドレスに対応している。
【００８２】
本実施形態に係るメモリ管理システム１０においては、上述したように、割り付けられるデータのサイズが「基準サイズ」未満であれば空き領域を最上位アドレスから昇順に（図２のステップＳ４参照）、「基準サイズ」以上であれば空き領域を最下位アドレスから降順に（図２のステップＳ３参照）探査方向を変えるため、図５（ａ）に示すように、メモリ５の上位アドレス側と下位アドレス側の２つに分離してデータが割り付けられて「使用中」となっており、その分離した使用中の領域の間が空き領域（図中、「空き」と表示）となっている。
【００８３】
図５（ｂ）は、図９（ｂ）と同様、図５（ａ）の状態から、新たにサイズがそれぞれ８キロバイト、２０キロバイト、３２キロバイトのデータＳ、データＴ、データＵに対する割り付けを、この順番で行った場合のメモリ５の使用状況を表したものである。図５（ｂ）に示すように、データＳのサイズ（８キロバイト）は「基準サイズ」（１６キロバイト）未満であるため、データＳはメモリ５の上位アドレス側にある「使用中」の領域の下位アドレス側に連続して割り付けられ、データＴのサイズ（２０キロバイト）及びデータＵのサイズ（３０キロバイト）は共に「基準サイズ」（１６キロバイト）以上であるため、メモリ５の下位アドレス側にある「使用中」の領域の上位アドレス側に連続し、且つメモリアドレスの降順にデータＴ、データＵが割り付けられる。
【００８４】
次に、図５（ｂ）の状態から、データＳ、データＴ、データＵのいずれか１つを削除（開放）した場合のメモリ領域の断片化の発生の有無を、最初適合法のアルゴリズムを適用した従来のメモリ管理システムと比較しながら（図９（ｂ）参照）、検討する。
【００８５】
まず、図９（ｂ）に示す状態にあるメモリ１０５からデータＵの割り付けのみを削除（開放）しても、データＵの割り付けられた領域は既に存在している空き領域と隣接しているため、メモリ領域の断片化は生じない。図５（ｂ）に示す状態にあるメモリ５からデータＵの割り付けのみを削除（開放）しても、同様のことが言える。
【００８６】
また、図９（ｂ）に示す状態にあるメモリ１０５からデータＴの割り付けのみを削除（開放）すると、データＴの割り付けられた領域は、データＳとデータＵの割り付けられた領域の間にあるため、メモリ領域の断片化が生じ、図５（ｂ）に示す状態にあるメモリ５からデータＴの割り付けのみを削除（開放）した場合も、データＴの割り付けられた領域は、データＵの割り付けられた領域と既にメモリ５の下位アドレス側にある使用中の領域の間にあるため、メモリ領域の断片化が生じる。
【００８７】
ところが、図９（ｂ）に示す状態にあるメモリ１０５からデータＳの割り付けのみを削除（開放）すると、データＳの割り付けられた領域は既に存在している空き領域に隣接していないため、メモリ領域の断片化が生じるのに対し、図５（ｂ）に示す状態にあるメモリ５からデータＳの割り付けのみを削除（開放）しても、データＳが割り付けられた領域は既に存在している空き領域に隣接しているため、削除されるデータＳが割り付けられていた領域は既にある空き領域と併合されることとなって、メモリ領域の断片化が生じない。
【００８８】
このように、メモリ１０５及びメモリ５に対して、同様のメモリ領域の割り付け、削除を行っても、メモリ５がメモリ１０５に比べてメモリ領域の断片化が生じにくい。これは、本実施形態に係るメモリ管理システム１０においては、割り付けられるデータのサイズに応じて空き領域の探査方向の昇順、降順が切り換えられるため、空き領域が中央に集まりやすくなるためである。
【００８９】
＜＜メモリ不足となった時の処理（ステップＳ８）＞＞
次に、管理領域６に記憶される「基準サイズ」が、割り付け要求元であるプログラム３やＯＳ２にとって最適な値に自動的に更新される様子を、図６を用いて説明する。図６は、管理領域６に記憶される「基準サイズ」が変更されて、メモリ５の使用状況が変化していく様子を表した図である。
【００９０】
図６（ａ）、図６（ｂ）、図６（ｃ）、図６（ｄ）、図６（ｅ）、図６（ｆ）の全ての図中において、上方側がメモリ１０５またはメモリ５の上位アドレス側、下方側が下位アドレス側を表しており、メモリ１０５、メモリ５の上端はそれぞれの最上位アドレス、下端はそれぞれの最下位アドレスに対応している。また、図６（ａ）〜（ｆ）の全ての図中のメモリ５は、データの記憶内容こそ異なれど同一のメモリであって、その全記憶容量は３２キロバイトである。
【００９１】
図６（ａ）は、メモリ５に対して、全領域が未使用（空き）の状態から、サイズがそれぞれ２キロバイト、１４キロバイト、４キロバイト、１０キロバイトのデータＬ、データＭ、データＮ、データＯの割り付けを、この順番に行った後のメモリ５の使用状況を表した図である。また、これらのデータの割り付けを行う際、「基準サイズ」は、１６キロバイトとなっていたものとする。そうすると、データＬ、データＭ、データＮ、データＯの全てのサイズは「基準サイズ」未満であるので、上述したように空き領域の探査方向は全て昇順となり（図２のステップＳ４参照）、図６（ａ）に示すように、最上位アドレスからデータＬ、データＭ、データＮ、データＯの順番に連続してメモリ領域が割り付けられる。また、データＯが割り付けられた領域の下位アドレス側には、メモリ５の全記憶容量（３２キロバイト）から、データＬ、データＭ、データＮ、データＯを割り付けた分を差し引いた６キロバイトのサイズの空き領域が新たに生成される。
【００９２】
この図６（ａ）に示すような「基準サイズ」（１６キロバイト）は、メモリ５の使用効率上、適切な値になっているとはいえない。なぜなら、割り付けられた全てのデータのサイズが「基準サイズ」未満であるため、常に割り付け領域の探査方向が昇順となってしまい、最初適合法のアルゴリズムを用いた場合と同じメモリ領域の割り付けを行ってしまうためである。
【００９３】
図６（ｂ）は、メモリ５及び管理領域６が図６（ａ）の状態にある場合に、新たにデータＰ（サイズが８キロバイト）の割り付け要求が発生した時のメモリ５の使用状況及び「基準サイズ」の値を表した図である。上述したように、メモリ５にはサイズが６キロバイトの空き領域が１つ存在しているだけなので、サイズが８キロバイトのデータＰを割り付けることができない。この新たな割り付け要求に対して、空き領域不足のため割り付けができない状態、換言すれば、新たな割り付けを要求されたデータのサイズ以上のサイズを有する空き領域がない状態を、以下「メモリオーバー」という。
【００９４】
この状態は、上述のステップＳ７（図２）の判定結果が肯定である状態であるので、メモリ管理システム１０は、上述のステップＳ８（図２）の処理を行うこととなる。即ち、メモリ管理手段４がＣＰＵ１に対して「割り付け不可能」の信号を伝達する等の割り付け不可能に係わるエラー処理を行うとともに、「基準サイズ」の値を新たな割り付けを要求されたデータＰのサイズ（８キロバイト）の値で書き換える。従って、図６（ｂ）に示すように、「基準サイズ」が８キロバイトに変更される。
【００９５】
ところで、割り付け要求元であるプログラム３やＯＳ２は、１種類や２種類でなく、時には数十種類に及ぶような様々なサイズの領域について、メモリの割り付けを要求するのが通常であるため、この変更された「基準サイズ」（８キロバイト）は、今後発生するであろう割り付け要求に係るデータのサイズの最小値または最大値となる可能性は低い。逆に言うと、今後、割り付け要求元であるプログラム３やＯＳ２は、この変更された「基準サイズ」以上のサイズを有するデータの割り付け要求と、このサイズ未満のサイズを有するデータの割り付け要求とを混在して行う可能性が高いと言える。
【００９６】
従って、この「基準サイズ」の変更があった後は、割り付けを要求されたデータのサイズに応じて空き領域の探査方向を切り換えるというメモリ管理システム１０の有する特徴が、十分に発揮されるようになる。
【００９７】
つまり、「メモリオーバー」の契機となった割り付けを要求されたデータのサイズで、「基準サイズ」を書き換えることにより、「基準サイズ」は割り付け要求元のプログラム３やＯＳ２にとって、より適した値に変更されたことになる。
【００９８】
また、ＣＰＵ１が上記「割り付け不可能」の信号を受けると、ＣＰＵ１は割り付け要求元であるプログラム３またはＯＳ２に「割り付け不可能」に関する情報を伝え、割り付け要求元は、既にメモリ５に割り付けられたデータのうち、削除しても良いデータがないかどうかを判断する。ここで、削除しても良いデータが一切ない場合は、データＰを割り付けることができない訳であるが、今、データＯの割り付けを削除（開放）しても良いと判断したとする。
【００９９】
図６（ｃ）は、図６（ｂ）の状態から、データＯの割り付けを削除した時のメモリ５の使用状況及び「基準サイズ」の値を表した図である。図６（ｂ）の状態より存在していたサイズが６キロバイトの空き領域とデータＯの割り付けられていた領域が併合したサイズが１６キロバイトの空き領域が、データＮの割り付けられた領域に連続した下位アドレス側の領域に新たに生成される。このサイズが１６キロバイトの新たな空き領域には、サイズが８キロバイトのデータＰを格納可能である。
【０１００】
そして、メモリ５及び管理領域６が図６（ｃ）の状態にある場合に、データＰを割り付けた時のメモリ５の使用状況及び「基準サイズ」の値を表した図が、図６（ｄ）である。データＰのサイズ（８キロバイト）は、「基準サイズ」（８キロバイト）以上であるため、空き領域は最下位アドレスより降順に探査され、図６（ｄ）に示すように、データＰは図６（ｃ）の状態で存在していた空き領域（サイズが１６キロバイト）中の下位アドレス側から割り付けられる。そして、データＰの割り付けられた領域に連続した上位アドレス側の領域には、サイズが８キロバイトの空き領域が残存する。
【０１０１】
図６（ｅ）は、図６（ｄ）の状態から、更にデータＭ及びデータＮの割り付けを削除した時のメモリ５の使用状況及び「基準サイズ」の値を表した図である。このデータＭ及びデータＮの削除に関する指令もプログラム３またはＯＳ２が行う。これにより、図６（ｄ）の状態で存在していた空き領域（サイズが８キロバイト）と、削除されるデータＭ及びデータＮの割り付けられていた領域が併合することにより、データＬの割り付けられた領域とデータＰの割り付けられた領域の間に、サイズが２６キロバイトの空き領域が新たに生成される。
【０１０２】
図６（ｆ）は、図６（ｅ）の状態から、データＱ（サイズが８キロバイト）及びデータＲ（サイズが４キロバイト）の割り付けを新たに行った時のメモリ５の使用状況及び「基準サイズ」の値を表した図である。データＱは「基準サイズ」（８キロバイト）以上であるため空き領域は降順に探査される。従って、データＱは、データＰの割り付けられた領域に連続した上位アドレス側の領域に割り付けられる。データＲは「基準サイズ」（８キロバイト）未満であるため空き領域は昇順に探査される。従って、データＲは、データＬの割り付けられた領域に連続した下位アドレス側の領域に割り付けられる。そして、データＱとデータＲを割り付けたことにより、データＱが割り付けられた領域とデータＲが割り付けられた領域の間に、サイズが１０キロバイトの空き領域が残存する。
【０１０３】
この図６（ｆ）に示すメモリ５の使用状況は、図３や図４を用いて説明してきたように、「基準サイズ」以上のサイズのデータは下位アドレス側よりに、「基準サイズ」未満のサイズのデータは上位アドレス側よりにまとまって割り付けられた状況になっている。これは、「メモリオーバー」となった時、「基準サイズ」をその新たな割り付けを要求されたデータのサイズで書き換えたことに起因している。
【０１０４】
そして、図６（ｆ）のように、「基準サイズ」以上のサイズのデータを下位アドレス側に、「基準サイズ」未満のサイズのデータを上位アドレス側にまとまって割り付ければ、メモリ領域の断片化の発生を抑制しつつも、高速な割り付け処理が実現できることは、上述してきたとおりである。
【０１０５】
また、「メモリオーバー」を契機として「基準サイズ」が割り付け要求元であるプログラム３等にとって、より適切でない値に変更される場合もありうる。しかし、「メモリオーバー」や、不要な割り付け領域の削除命令、新たな割り付け要求は頻繁に発生するため、この「基準サイズ」が適切でない状態は直ぐに解消される。即ち、「基準サイズ」は、割り付け要求元であるプログラム３等にとって適切な（統計的に最適な）値に自動的に更新されていくといえる。
【０１０６】
＜＜その他＞＞
また、本発明を画像形成装置等にて実施する場合、装置の種類によってメモリの割り付けを要求されたデータのサイズは装置の設計段階で予め決まっているものである。例えば、割り付けを要求されたデータのサイズの最大値（最大のサイズ）が１２８キロバイト、最小値（最小のサイズ）が１キロバイトといった具合である。従って、割り付けを要求されたデータのサイズに応じて空き領域の探査方向を切り換えるという本発明の有する特徴が当初より発揮されるように、「基準サイズ」の初期値を、前記最大値より小さく、且つ前記最小値より大きい値に設定してもよい。
【０１０７】
尚、上述した実施例においては、割り付けを要求されたデータのサイズが「基準サイズ」以上であれば空き領域の探査方向を降順（図２のステップＳ３）、「基準サイズ」未満であれば空き領域の探査方向を昇順（図２のステップＳ４）とする例を挙げたが、勿論、図２におけるステップＳ２の記号「≧」を「＞」、「≦」、「＜」の何れに変えても良い。何れにしても、上述した本発明の有する効果は実現されるからである。
【０１０８】
即ち、割り付けを要求されたデータのサイズが「基準サイズ」よりおおきれば空き領域の探査方向を降順、「基準サイズ」以下であれば空き領域の探査方向を昇順としても良いし（「＞」に相当）、割り付けを要求されたデータのサイズが「基準サイズ」よりおおきれば空き領域の探査方向を昇順、「基準サイズ」以下であれば空き領域の探査方向を降順としても良い（「≦」に相当）。更に、割り付けを要求されたデータのサイズが「基準サイズ」以上であれば空き領域の探査方向を昇順、「基準サイズ」未満であれば空き領域の探査方向を降順としても良い（「＜」に相当）。
【０１０９】
また、これまで、割り付けを要求されたデータのサイズを８キロバイト、メモリ５の記憶容量を３２キロバイト、「基準サイズ」の初期値を１６キロバイト等、具体的な数値を例に挙げて説明したが、本発明はこうした数値に限定されないことはいうまでもない。
【産業上の利用可能性】
【０１１０】
上述した通り、本発明に係るメモリ管理システムによれば、メモリ領域の断片化を抑制しつつも、高速な割り付け処理を行うことができる。
【図面の簡単な説明】
【０１１１】
【図１】本発明の実施の形態に係るメモリ管理システム１０の構成図である。
【図２】図１におけるメモリ管理システム１０の動作を説明するためのフローチャートである。
【図３】図１における管理領域６に記憶される内容の一部及びメモリ５の使用状況の第１例を示す図である。
【図４】図１における管理領域６に記憶される内容の一部及びメモリ５の使用状況の第２例を示す図である。
【図５】図１における管理領域６に記憶される内容の一部及びメモリ５の使用状況の第３例を示す図である。
【図６】図１における管理領域６に記憶される「基準サイズ」が変更されて、メモリ５の使用状況が変化していく様子を表した図である。
【図７】最初適合法のアルゴリズムを適用した従来のメモリ管理システムにおけるメモリの使用状況の第１例を示す図である。
【図８】最初適合法のアルゴリズムを適用した従来のメモリ管理システムにおけるメモリの使用状況の第２例を示す図である。
【図９】最初適合法のアルゴリズムを適用した従来のメモリ管理システムにおけるメモリの使用状況の第３例を示す図である。
【符号の説明】
【０１１２】
１    ＣＰＵ
２    ＯＳ
３    プログラム
４    メモリ管理手段
５、１０５    メモリ
６    管理領域
１０    メモリ管理システム
【図１】
2005157714.tif 000003
【図２】
2005157714.tif 000004
【図３】
2005157714.tif 000005
【図４】
2005157714.tif 000006
【図５】
2005157714.tif 000007
【図６】
2005157714.tif 000008
【図７】
2005157714.tif 000009
【図８】
2005157714.tif 000010
【図９】
2005157714.tif 000011