【手続補正書】
【提出日】平成18年10月4日(2006.10.4)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】発明の名称
【補正方法】変更
【補正の内容】
【発明の名称】メモリアロケーション方法及びメモリアロケーション装置並びに記憶媒体
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピュータシステムにおけるメモリブロックを動的に割り当てるためのメモリアロケーション方法であって、
空きのメモリブロックが、サイズに基づいて記録された第１のメモリアロケーションリストを生成する工程と、
空きのメモリブロックが、メモリブロックのアドレスに基づいて記録された第２のメモリアロケーションリストを生成する工程と、
前記コンピュータシステムによってメモリブロックが要求された場合に、前記第１のメモリアロケーションリストを検索して、適切なサイズの空きのメモリブロックから要求されたメモリブロックを割り当てる工程と、
その割り当てに基づいて前記第１及び第２のメモリアロケーションリストを更新する工程と、
前記コンピュータシステムによってメモリブロックが解放された場合に、前記第２のメモリアロケーションリストを参照して、解放されたメモリブロックに隣接する空きのメモリブロックが存在するか否かを判定する工程と、
解放されたメモリブロックに隣接する１またはそれ以上の空きのメモリブロックが存在する場合に、前記解放されたメモリブロックと当該空きのメモリブロックとを結合して、一の空きのメモリブロックを形成する工程と、
前記解放されたメモリブロックと結合して形成された空きのブロックとに基づいて、前記第１及び第２のメモリアロケーションリストを更新する工程と、
を含むことを特徴とするメモリアロケーション方法。
【請求項２】
前記第１及び第２のメモリアロケーションリストが、複数のポインタによって一部が定義され、相互にリンクしたリストデータ構造であることを特徴とする請求項１に記載のメモリアロケーション方法。
【請求項３】
前記第１及び第２のメモリアロケーションリストからのポインターが、相互に結合されたデータ構造を形成するようにメッシュ化されていることを特徴とする請求項２に記載のメモリアロケーション方法。
【請求項４】
前記第１及び第２のメモリアロケーションリストが、スキップリスト形式であることを特徴とする請求項２又は３に記載のメモリアロケーション方法。
【請求項５】
前記スキップリストは、複数のノードを定義し、該ノードの少なくともいくつかは、異なるレベルを有する複数の要素を定義し、各々のノードは、所定サイズの空きのメモリブロックに対応したベースメモリアドレスと関連し、各々の要素は、複数の第１及び第２のポインタ対を含み、各々のポインタ対において第１のポインタは、アドレスに基づいて同じレベル上の第１の要素を指し、各々のポインタ対において第２のポインタは、ブロックサイズに基づいて同じレベル上の第２の要素を指すことを特徴とする請求項４に記載のメモリアロケーション方法。
【請求項６】
コンピュータシステムにおけるメモリブロックを動的に割り当てるためのメモリアロケーション装置であって、
空きメモリブロックが、サイズに基づいて記録された第１のメモリアロケーションリストと、空きメモリブロックが、メモリブロックのアドレスに基づいて記録された第２のメモリアロケーションリストとを生成するためのアロケーションリスト生成手段と、
メモリブロックが前記コンピュータシステムによって要求された場合に、前記第１のメモリアロケーションリストを検索して、適切なサイズの空きメモリブロックから要求されたメモリブロックを割り当てるための割り当て手段と、
メモリブロックがコンピュータシステムによって解放された場合に、前記第２のメモリアロケーションリストを参照して、解放されたメモリブロックに隣接する空きのメモリブロックが存在するか否かを判定する判定手段と、
解放されたメモリブロックに隣接する１またはそれ以上の空きのメモリブロックが存在する場合に、前記解放されたメモリブロックと当該空きのメモリブロックとを結合して、一の空きのメモリブロックを形成する結合手段と、
前記割り当てと、前記解放されたメモリブロックと、結合して形成された空きのメモリブロックとに基づいて、前記第１及び第２のメモリアロケーションリストを更新する手段と、
を備えたことを特徴とするメモリアロケーション装置。
【請求項７】
前記第１及び第２のメモリアロケーションリストが、複数のポインタによって一部が定義され、相互にリンクしたリストデータ構造であることを特徴とする請求項６に記載のメモリアロケーション装置。
【請求項８】
前記第１及び第２のメモリアロケーションリストからのポインターが、相互に結合されたデータ構造を形成するようにメッシュ化されていることを特徴とする請求項７に記載のメモリアロケーション装置。
【請求項９】
前記第１及び第２のメモリアロケーションリストが、スキップリスト形式であることを特徴とする請求項７又は８に記載のメモリアロケーション装置。
【請求項１０】
前記スキップリストは、複数のノードを定義し、該ノードの少なくともいくつかは、異なるレベルを有する複数の要素を定義し、各々のノードは、所定サイズの空きのメモリブロックに対応したベースメモリアドレスと関連し、各々の要素は、複数の第１及び第２のポインタ対を含み、各々のポインタ対において第１のポインタは、アドレスに基づいて同じレベル上の第１の要素を指し、各々のポインタ対において第２のポインタは、ブロックサイズに基づいて同じレベル上の第２の要素を指すことを特徴とする請求項９に記載のメモリアロケーション装置。
【請求項１１】
データを処理する装置のためのプログラムを記録したコンピュータ読取り可能な記憶媒体であって、
前記処理は、コンピュータシステムにおけるメモリブロックを動的にアロケートするための処理を含み、前記プログラムが、
空きのメモリブロックが、サイズに基づいて記録された第１のメモリアロケーションリストを生成する工程のコードと、
空きのメモリブロックが、メモリブロックのアドレスに基づいて記録された第２のメモリアロケーションリストを生成する工程のコードと、
前記コンピュータシステムによってメモリブロックが要求された場合に、前記第１のメモリアロケーションリストを検索して、適切なサイズの空きのメモリブロックから要求されたメモリブロックを割り当てる工程のコードと、
その割り当てに基づいて前記第１及び第２のメモリアロケーションリストを更新する工程のコードと、
前記コンピュータシステムによってメモリブロックが解放された場合に、前記第２のメモリアロケーションリストを参照して、解放されたメモリブロックに隣接する空きのメモリブロックが存在するか否かを判定する工程のコードと、
解放されたメモリブロックに隣接する１またはそれ以上の空きのメモリブロックが存在する場合に、前記解放されたメモリブロックと当該空きのメモリブロックとを結合して、一の空きのメモリブロックを形成する工程のコードと、
前記解放されたメモリブロックと結合して形成された空きのブロックとに基づいて、前記第１及び第２のメモリアロケーションリストを更新する工程のコードと、
を含むことを特徴とする記憶媒体。
【請求項１２】
前記第１及び第２のメモリアロケーションリストが、複数のポインタによって一部が定義され、相互にリンクしたリストデータ構造であることを特徴とする請求項１１に記載の記憶媒体。
【請求項１３】
前記第１及び第２のメモリアロケーションリストからのポインターが、相互に結合されたデータ構造を形成するようにメッシュ化されていることを特徴とする請求項１２に記載の記憶媒体。
【請求項１４】
前記第１及び第２のメモリアロケーションリストが、スキップリスト形式であることを特徴とする請求項１２又は１３に記載の記憶媒体。
【請求項１５】
前記スキップリストは、複数のノードを定義し、該ノードの少なくともいくつかは、異なるレベルを有する複数の要素を定義し、各々のノードは、所定サイズの空きのメモリブロックに対応したベースメモリアドレスと関連し、各々の要素は、複数の第１及び第２のポインタ対を含み、各々のポインタ対において第１のポインタは、アドレスに基づいて同じレベル上の第１の要素を指し、各々のポインタ対において第２のポインタは、ブロックサイズに基づいて同じレベル上の第２の要素を指すことを特徴とする請求項１４に記載の記憶媒体。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
【発明が解決しようとする課題】
本発明は、上記問題点に鑑みてなされたものであり、その目的は、メモリのフラグメンテーションを低減し得る、メモリアロケーション方法及びメモリアロケーション装置並びに記憶媒体を提供することにある。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２７
【補正方法】変更
【補正の内容】
【００２７】
【課題を解決するための手段】
本発明によれば、コンピュータシステムにおけるメモリブロックを動的に割り当てるためのメモリアロケーション方法であって、
空きのメモリブロックが、サイズに基づいて記録された第１のメモリアロケーションリストを生成する工程と、
空きのメモリブロックが、メモリブロックのアドレスに基づいて記録された第２のメモリアロケーションリストを生成する工程と、
前記コンピュータシステムによってメモリブロックが要求された場合に、前記第１のメモリアロケーションリストを検索して、適切なサイズの空きのメモリブロックから要求されたメモリブロックを割り当てる工程と、
その割り当てに基づいて前記第１及び第２のメモリアロケーションリストを更新する工程と、
前記コンピュータシステムによってメモリブロックが解放された場合に、前記第２のメモリアロケーションリストを参照して、解放されたメモリブロックに隣接する空きのメモリブロックが存在するか否かを判定する工程と、
解放されたメモリブロックに隣接する１またはそれ以上の空きのメモリブロックが存在する場合に、前記解放されたメモリブロックと当該空きのメモリブロックとを結合して、一の空きのメモリブロックを形成する工程と、
前記解放されたメモリブロックと結合して形成された空きのブロックとに基づいて、前記第１及び第２のメモリアロケーションリストを更新する工程と、
を含むことを特徴とするメモリアロケーション方法が提供される。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２８
【補正方法】変更
【補正の内容】
【００２８】
本発明においては、前記第１及び第２のメモリアロケーションリストが、リンクされたリストデータ構造であることが好ましい。また、前記第１及び第２のメモリアロケーションリストが結合されていることが好ましい。更に、前記第１及び第２のメモリアロケーションリストが、結合されたスキップリスト形式であることが好ましい。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００２９
【補正方法】変更
【補正の内容】
【００２９】
また、本発明によれば、コンピュータシステムにおけるメモリブロックを動的に割り当てるためのメモリアロケーション装置であって、
空きメモリブロックが、サイズに基づいて記録された第１のメモリアロケーションリストと、空きメモリブロックが、メモリブロックのアドレスに基づいて記録された第２のメモリアロケーションリストとを生成するためのアロケーションリスト生成手段と、
メモリブロックが前記コンピュータシステムによって要求された場合に、前記第１のメモリアロケーションリストを検索して、適切なサイズの空きメモリブロックから要求されたメモリブロックを割り当てるための割り当て手段と、
メモリブロックがコンピュータシステムによって解放された場合に、前記第２のメモリアロケーションリストを参照して、解放されたメモリブロックに隣接する空きのメモリブロックが存在するか否かを判定する判定手段と、
解放されたメモリブロックに隣接する１またはそれ以上の空きのメモリブロックが存在する場合に、前記解放されたメモリブロックと当該空きのメモリブロックとを結合して、一の空きのメモリブロックを形成する結合手段と、
前記割り当てと、前記解放されたメモリブロックと、結合して形成された空きのメモリブロックとに基づいて、前記第１及び第２のメモリアロケーションリストを更新する手段と、
を備えたことを特徴とするメモリアロケーション装置が提供される。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
また、本発明によれば、データを処理する装置のためのプログラムを記録したコンピュータ読取り可能な記憶媒体であって、
前記処理は、コンピュータシステムにおけるメモリブロックを動的にアロケートするための処理を含み、前記プログラムが、
空きのメモリブロックが、サイズに基づいて記録された第１のメモリアロケーションリストを生成する工程のコードと、
空きのメモリブロックが、メモリブロックのアドレスに基づいて記録された第２のメモリアロケーションリストを生成する工程のコードと、
前記コンピュータシステムによってメモリブロックが要求された場合に、前記第１のメモリアロケーションリストを検索して、適切なサイズの空きのメモリブロックから要求されたメモリブロックを割り当てる工程のコードと、
その割り当てに基づいて前記第１及び第２のメモリアロケーションリストを更新する工程のコードと、
前記コンピュータシステムによってメモリブロックが解放された場合に、前記第２のメモリアロケーションリストを参照して、解放されたメモリブロックに隣接する空きのメモリブロックが存在するか否かを判定する工程のコードと、
解放されたメモリブロックに隣接する１またはそれ以上の空きのメモリブロックが存在する場合に、前記解放されたメモリブロックと当該空きのメモリブロックとを結合して、一の空きのメモリブロックを形成する工程のコードと、
前記解放されたメモリブロックと結合して形成された空きのブロックとに基づいて、前記第１及び第２のメモリアロケーションリストを更新する工程のコードと、
を含むことを特徴とする記憶媒体が提供される。