JP7140935B1 - リアルタイムアプリケーションのための決定的メモリ割り当て - Google Patents

Abstract

【課題】リアルタイムで安全性が重要なアプリケーション（例えば、車両およびロボットの自律移動）における決定的メモリ割り当てを提供する。【解決手段】方法は、ビットコードをスキャンして、メモリ割り当て関数によるダミー関数への呼び出しを検出する。各呼び出しは、メモリプールの識別子と該メモリプールに格納するデータ型のサイズとを含むパラメータを使用する。検出された各呼び出しに対して、パラメータを含む割り当てレコードが生成される。そして、割り当てレコードに基づいてヘッダファイルが生成される。ヘッダファイルは、バケットの定義と、メモリプールの定義とを含むことができる。メモリプールの各定義は、少なくとも１つのバケットを特定することができる。【選択図】図２７

Description

本明細書で説明する実施形態は、一般に、リアルタイムアプリケーションに向けられ、より詳細には、リアルタイムで安全性が重要なアプリケーション（例えば、車両およびロボットの自律移動）における決定的メモリ割り当てに向けられる。

リアルタイムで安全性が重要な環境におけるメモリ割り当ては、安全で証明可能であるべきである。例えば、プログラミング言語Ｃ＋＋の場合、メモリ割り当ては、道路運送車両の機能安全に関する国際標準化機構（ＩＳＯ）２６２６２規格に由来する要件を満たすＡｕｔｏｓａｒ Ｃ＋＋ １４ コーディングガイドラインに準拠する必要がある。特に、Ａｕｔｏｓａｒ Ｃ＋＋ １４ コーディングガイドラインの２つの主要なルールに準拠する必要がある。

まず、規則Ａ１８－５－５によれば、メモリ管理機能は、最悪シナリオ実行時間での決定的な動作を保証し、メモリ断片化を回避し、メモリ不足を回避し、割り当てと解放との不一致を回避し、カーネルへの非決定的な呼び出しに依存しないことが必要である。ミドルウェアでは、メモリ不足の回避、割り当てと解放との不一致は保証できない。しかし、他の３つの要件はミドルウェアで対応することが可能である。

次に、規則Ａ１８－５－７によれば、動的メモリ管理機能を使用する場合、非実時間プログラムフェーズにおいてのみ、メモリの割り当てと解放とが可能である。言い換えれば、メモリは初期化時に事前割り当てが可能であり、実行時にはできない。

したがって、リアルタイムアプリケーションにおける決定的メモリ割り当てのためのシステム、方法、および非一時的なコンピュータ可読媒体が開示される。一実施形態では、少なくとも１つのハードウェアプロセッサを使用して以下を行わせることを含む方法が開示される。

アプリケーションのコンパイルされたソースコードを表すビットコードをスキャンするステップであって、前記ソースコードは、複数のパラメータを使用するダミー関数を呼び出すメモリを割り当てるための割り当て関数を含み、前記複数のパラメータは、メモリプールの識別子と前記メモリプールに格納するデータ型のサイズとを含む、アプリケーションのコンパイルされたソースコードを表すビットコードをスキャンするステップと、
前記ビットコードをスキャンしながら、前記ビットコード内の前記ダミー関数への各呼び出しを検出するステップと、前記ダミー関数への各呼び出しに対して、前記ダミー関数への前記検出された呼び出しで使用された前記複数のパラメータを抽出し、かつ前記抽出された複数のパラメータから、前記メモリプールの前記識別子と前記データ型の前記サイズとを含む割り当てレコードを生成するステップと、前記生成された割り当てレコードから割り当てレコードリストを生成するステップと、前記割り当てレコードリストに基づいてヘッダファイルを生成するステップであって、前記ヘッダファイルは、１つ以上のバケットの定義と、１つ以上のメモリプールの各定義とを含み、前記１つ以上のメモリプールの各定義は、前記１つ以上のバケットのうちの少なくとも１つを特定する、前記割り当てレコードリストに基づいてヘッダファイルを生成するステップと、を含む。

本方法は、前記少なくとも１つのハードウェアプロセッサを使用して、
前記ビットコードをスキャンするステップ前に、前記ソースコードを前記ビットコードにコンパイルするステップと、
前記ヘッダファイルを生成するステップ後、前記ヘッダファイルで前記ソースコードを再コンパイルするステップと、をさらに含むことができる。

前記１つ以上のバケットの各々の定義は、ブロック数とブロックサイズとを含むことができる。前記ヘッダファイルを生成するステップは、前記割り当てレコードリスト中の各一意なサイズに対して、その一意なサイズに整合するブロックサイズを含むバケットの少なくとも１つの定義を生成することを含むことができる。ヘッダファイルを生成するステップは、前記割り当てレコードリスト中の各一意な識別子に対して、その識別子を有するメモリプールの定義を生成するステップをさらに含んでいてもよい。メモリプールの各定義は、前記割り当てレコードリスト中のそのメモリプールの前記識別子に関連付けられている各一意なサイズに対して、ブロックサイズがそのサイズに整合する前記１つ以上のバケットのうちの１つの定義への参照を含んでいてもよい。そのサイズに整合するブロックサイズを含むバケットの少なくとも１つの定義を生成するステップは、そのサイズに一致するブロックサイズを含むバケットの定義を生成するステップを含んでいてもよい。

前記１つ以上のメモリプールの各々の前記定義は、タプルを含んでもよく、前記タプルは１つ以上の参照を含み、かつ前記１つ以上の参照の各々は前記１つ以上のバケットの１つを特定する。

前記ビットコードにおいて、前記割り当て関数の各インスタンスは、前記割り当て関数が単一のメモリプール以外の任意のメモリプールから割り当てられないように、前記単一のメモリプールにバインドされてもよい。

前記メモリプールが未定義である間、前記アプリケーションが利用可能な上流リソースからメモリを割り当て、前記メモリプールが定義されている間、前記メモリプールからメモリを割り当てるように構成されてもよい。

前記ソースコードは、Ｃ＋＋プログラミング言語で記述されてもよい。前記割り当て関数は、前記Ｃ＋＋プログラミング言語のアロケータモデルに従ったカスタムアロケータであってもよい。

前記方法は、前記少なくとも１つのハードウェアプロセッサを使用して、前記１つ以上の割り当ての各々に対して、前記アプリケーションのエントリポイントから前記割り当て関数への関数呼び出しのパスを表す呼び出しグラフを生成するステップをさらに含むことができる。

前記複数のパラメータは、前記メモリプールに格納する前記データ型の識別子をさらに含んでもよい。

前記方法は、サーバなどのプロセッサベースシステムの実行可能なソフトウェアモジュール、および／または非一時的なコンピュータ可読媒体に格納されている実行可能な命令で実施することができる。

本発明の詳細は、その構造および動作の両方に関して、同種の部品に同種の参照番号を付している添付図面の研究によって部分的に得ることができる。
図１は、一実施形態による、本明細書に記載した処理の１つ以上が実行され得る、処理システム例を示す。 図２は、一実施形態による、アロケータテンプレートのソースコード例を示す。 図３は、一実施形態による、メモリプール内のバケットの実装例のソースコードを示す。 図４は、一実施形態による、バケットのコンストラクタおよびデストラクタ関数の実装例のソースコードを示す。 図５は、一実施形態による、バケット内のブロックを割り当てる割り当て関数の実装例のソースコードを示す。 図６は、一実施形態による、バケット内のブロックを解放する解放関数の実装例のソースコードを示す。 図７は、一実施形態による、メモリプールを定義するテンプレート構造の実装例のためのソースコードを示す。 図８は、一実施形態による、特定のアプリケーション例のためにメモリプールを定義するテンプレート構造を特殊化する実装例のためのソースコードを示す。 図９は、一実施形態による、メモリプールの特性を定義するいくつかの構造の実装例のソースコードを示す。 図１０は、一実施形態による、メモリプールの作成関数の実装例のソースコードを示す。 図１１は、一実施形態による、メモリプール初期化の実装例のソースコードを示す。 図１２は、一実施形態による、ファーストフィット戦略を利用する割り当て関数の実装例のソースコードを示す。 図１３は、一実施形態による、バケットの選択を支援するためのインフォ（「ｉｎｆｏ」）構造の実装例のソースコードを示す。 図１４は、一実施形態による、メモリプール内のバケットを割り当てるための割り当て関数の実装例のソースコードを示す。 図１５は、一実施形態による、メモリプール内のバケットを解放するための解放関数の実装例のソースコードを示す。 図１６は、一実施形態による、ネストされたデータオブジェクトに対して同一メモリプールが使用される使用シナリオ例を示す。 図１７は、一実施形態による、ネストされたデータオブジェクトに対して別々のメモリプールが使用される使用シナリオ例を示す図である。 図１８は、一実施形態による、静的プールアロケータの実装例のソースコードを示す。 図１９は、一実施形態による、静的プールアロケータの割り当て関数の実装例のソースコードを示す。 図２０は、一実施形態による、ダミー関数を定義するインスツルメントネームスペースの実装例のソースコードを示す。 図２１は、一実施形態による、静的プールアロケータの割り当て関数に注入されるインスツルメントコードの注入の実施例のソースコードを示す。 図２２は、一実施形態による、静的プールアロケータの解放関数の実装例のソースコードを示す。 図２３は、一実施形態による、ビットコードを解析するパスの実装例のソースコードを示す。 図２４は、静的プールアロケータの一実施形態を使用する単純なアプリケーションのソースコードを示す。 図２５は、一実施形態による、単純なアプリケーションのパスによって生成される、割り当てのための呼び出しグラフを示す。 図２６は、一実施形態による、ヘッダファイル例を示す図である。 図２７は、一実施形態による、アプリケーションで使用されるメモリプールを最適化するためのプロセス例を示す図である。

一実施形態では、例えば、リアルタイムおよび／または安全性が重要なアプリケーションで使用するための決定的メモリ割り当てのためのシステム、方法、および非一時的コンピュータ可読媒体が開示される。この説明を読んだ後、当業者には、様々な代替の実施形態および代替のアプリケーションにおいて本発明を実施する方法が明らかになるであろう。しかしながら、本発明の様々な実施形態が本明細書で説明されても、これらの実施形態は、例および説明のためにのみ提示され、限定するものでないことが理解されよう。かくして、様々な実施形態についてのこの詳細な説明は、添付の特許請求の範囲が規定する本発明の範囲または広がりを制限するものと解釈されるべきではない。

（１．システムの概要）
図１は、本明細書に説明する様々な実施形態に関連して使用され得る例示的な有線または無線システム１００を示すブロック図である。例えば、システム１００は、本明細書に説明する（例えば、最適化ツールなどの１つ以上のソフトウェアモジュールを格納および／または実行するための）機能、プロセス、または方法の１つ以上として、またはそれらと関連して使用することができる。システム１００は、サーバもしくは任意の従来のパーソナルコンピュータ、または有線もしくは無線データ通信が可能な任意の他のプロセッサ対応装置であり得る。当業者には明らかなように、他のコンピュータシステムおよび／またはアーキテクチャを使用することもできる。

システム１００は、好ましくは、プロセッサ１１０などの１つ以上のプロセッサを含む。入力／出力を管理する補助プロセッサ、浮動小数点数学演算を実行する補助プロセッサ、信号処理アルゴリズムの高速実行に適したアーキテクチャを有する特殊用途マイクロプロセッサ（例えば、デジタル信号プロセッサ）、主処理システムに従属するスレーブプロセッサ（例えば、バックエンドプロセッサ）、デュアルもしくはマルチプロセッサシステム用の追加マイクロプロセッサもしくはコントローラ、および／またはコプロセッサなど、追加のプロセッサが提供されてもよい。そのような補助プロセッサは、別個のプロセッサであってもよいし、プロセッサ１１０と統合されてもよい。システム１００と共に使用され得るプロセッサの例は、限定されないが、「Ｐｅｎｔｉｕｍ（登録商標）」プロセッサ、「Ｃｏｒｅ ｉ７」プロセッサ、および「Ｘｅｏｎ（登録商標）」プロセッサを含み、これらはすべて、カリフォルニア州サンタクララのインテル社から入手可能である。

プロセッサ１１０は、好ましくは、通信バス１０５に接続される。通信バス１０５は、システム１００の記憶装置と他の周辺部品との間の情報転送を容易にするためのデータチャネルを含んでもよい。さらに、通信バス１０５は、データバス、アドレスバス、および／または制御バス（図示せず）を含む、プロセッサ１１０との通信に使用される信号のセットを提供してもよい。通信バス１０５は、例えば、業界標準アーキテクチャ（ＩＳＡ）、拡張業界標準アーキテクチャ（ＥＩＳＡ）、マイクロチャネルアーキテクチャ（ＭＣＡ）、周辺部品相互接続（ＰＣＩ）ローカルバス、「ＩＥＥＥ４８８」汎用インタフェースバス（ＧＰＩＢ）、「ＩＥＥＥ６９６／Ｓ－１００」、および／または同種のものを含む米国電気電子学会（ＩＥＥＥ）によって広められた標準などの任意の標準または非標準バスアーキテクチャから構成されてもよい。

システム１００は、好ましくは、主メモリ１１５を含み、また、二次メモリ１２０を含んでもよい。主メモリ１１５は、本明細書で論ずる機能および／またはモジュールのうちの１つ以上など、プロセッサ１１０上で実行されるプログラムのための命令およびデータの記憶装置を提供する。メモリに記憶され、プロセッサ１１０によって実行されるプログラムは、限定されないが、「Ｃ／Ｃ＋＋」、「Ｊａｖａ」、「ＪａｖａＳｃｒｉｐｔ」、「Ｐｅｒｌ」、「Ｖｉｓｕａｌ Ｂａｓｉｃ」、「．ＮＥＴ」などを含む任意の適切な言語に従って記述および／またはコンパイルすることができるのを理解するべきである。主メモリ１１５は、典型的には、動的ランダムアクセスメモリ（ＤＲＡＭ）および／または静的ランダムアクセスメモリ（ＳＲＡＭ）のような半導体ベースのメモリである。他の半導体ベースのメモリ種としては、例えば、「ＳＤＲＡＭ（ｓｙｎｃｈｒｏｎｏｕｓ ｄｙｎａｍｉｃ ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ）」、「ＲＤＲＡＭ（Ｒａｍｂｕｓ ｄｙｎａｍｉｃ ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ）」、「ＦＲＡＭ（ｆｅｒｒｏｅｌｅｃｔｒｉｃ ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ）」などがあり、「ＲＯＭ（ｒｅａｄ ｏｎｌｙ ｍｅｍｏｒｙ）」が含まれる。

二次メモリ１２０は、任意に、内部媒体１２５および／または取り外し可能媒体１３０を含んでもよい。取り外し可能媒体１３０は、任意の周知の方法で読み取られ、かつ／または書き込まれる。取り外し可能記憶媒体１３０は、例えば、磁気テープドライブ、コンパクトディスク（ＣＤ）ドライブ、デジタル多用途ディスク（ＤＶＤ）ドライブ、他の光学ドライブ、フラッシュメモリドライブ、および／または同種のものであってもよい。

二次メモリ１２０は、そこに格納されているコンピュータ実行可能コード（例えば、開示されたソフトウェアモジュール）および／または他のデータを有する非一時的コンピュータ読取可能媒体である。二次メモリ１２０に格納されたコンピュータソフトウェアまたはデータは、プロセッサ１１０による実行のために主メモリ１１５に読み込まれる。

別の実施形態では、二次メモリ１２０は、コンピュータプログラムまたは他のデータもしくは命令をシステム１００にロードすることを可能にするための他の同様の手段を含んでもよい。そのような手段は、例えば、ソフトウェアおよびデータを外部記憶媒体１４５からシステム１００に転送することを可能にする通信インタフェース１４０を含んでもよい。外部記憶媒体１４５の例は、外部ハードディスクドライブ、外部光学ドライブ、外部光磁気ドライブ、および／または同種のものを含んでもよい。二次メモリ１２０の他の例は、「ＰＲＯＭ（ｐｒｏｇｒａｍｍａｂｌｅ ｒｅａｄ－ｏｎｌｙ ｍｅｍｏｒｙ）」、「ＥＰＲＯＭ（ｅｒａｓａｂｌｅ ｐｒｏｇｒａｍｍａｂｌｅ ｒｅａｄ－ｏｎｌｙ ｍｅｍｏｒｙ）」、「ＥＥＰＲＯＭ（ｅｌｅｃｔｒｉｃａｌｌｙ ｅｒａｓａｂｌｅ ｒｅａｄ－ｏｎｌｙ ｍｅｍｏｒｙ）」、およびフラッシュメモリ（ＥＥＰＲＯＭと同様のブロック指向メモリ）などの半導体ベースのメモリであり得る。

上述したように、システム１００は、通信インタフェース１４０を含んでもよい。通信インタフェース１４０は、システム１００と外部装置（例えば、プリンタ）、ネットワーク、または他の情報源との間でソフトウェアおよびデータを転送することを可能にする。例えば、コンピュータソフトウェアまたは実行可能コードは、通信インタフェース１４０を介してネットワークサーバ（例えば、プラットフォーム１１０）からシステム１００に転送されてもよい。通信インタフェース１４０の例としては、内蔵ネットワークアダプタ、ネットワークインタフェースカード（ＮＩＣ）、パーソナルコンピュータメモリカード国際協会（ＰＣＭＣＩＡ）ネットワークカード、カードバスネットワークアダプタ、無線ネットワークアダプタ、ユニバーサルシリアルバス（ＵＳＢ）ネットワークアダプタ、モデム、無線データカード、通信ポート、赤外線インタフェース、「ＩＥＥＥ１３９４」ファイアワイヤ、システム１００とネットワークまたは別のコンピュータ装置とをインタフェース可能なその他の任意の装置が挙げられる。通信インタフェース１４０は、好ましくは、イーサネット「ＩＥＥＥ８０２」規格、ファイバチャネル、デジタル加入者線（ＤＳＬ）、非同期デジタル加入者線（ＡＤＳＬ）、フレームリレー、非同期転送モード（ＡＴＭ）、統合デジタルサービスネットワーク（ＩＳＤＮ）、個人通信サービス（ＰＣＳ）、伝送制御プロトコル／インターネットプロトコル（ＴＣＰ／ＩＰ）、シリアルラインインターネットプロトコル／ポイントプロトコル（ＳＬＩＰ／ＰＰＰ）など業界周知のプロトコル基準を実装するが、カスタム化された、または標準外のインタフェースプロトコルを実装してもよい。

通信インタフェース１４０を介して転送されるソフトウェアおよびデータは、一般に、電気通信信号１５５の形態である。これらの信号１５５は、通信チャネル１５０を介して通信インタフェース１４０に提供されてもよい。実施形態において、通信チャネル１５０は、有線もしくは無線ネットワーク、または任意の様々な他の通信リンクであってもよい。通信チャネル１５０は、信号１５５を搬送し、いくつか例を挙げるとワイヤもしくはケーブル、光ファイバ、従来の電話回線、セルラー電話リンク、無線データ通信リンク、無線周波数（「ＲＦ」）リンク、もしくは赤外線リンクを含む、様々な有線または無線通信手段を使用して実装することができる。

コンピュータ実行可能コード（例えば、１つ以上のソフトウェアモジュールからなるコンピュータプログラム）は、主メモリ１１５および／または二次メモリ１２０に格納される。コンピュータ実行可能コードは、通信インタフェース１４０を介して受信され、主メモリ１１５および／または二次メモリ１２０に格納することも可能である。このようなコンピュータ実行可能コードが実行されると、システム１００は、本明細書の他の箇所で説明したような開示された実施形態の様々な機能を実行することができる。

本明細書では、「コンピュータ可読媒体」という用語は、コンピュータ実行可能コードおよび／または他のデータをシステム１００またはシステム１００内に提供するために使用される任意の非一時的なコンピュータ可読記憶媒体を指すために使用される。そのような媒体の例としては、主メモリ１１５、二次メモリ１２０（内部メモリ１２５、取り外し可能媒体１３０、および外部記憶媒体１４５を含む）、および通信インタフェース１４０と通信可能に結合されている任意の周辺装置（ネットワーク情報サーバまたは他のネットワーク装置を含む）が挙げられる。これらの非一時的なコンピュータ可読媒体は、実行可能なコード、プログラミング命令、ソフトウェア、および／または他のデータをシステム１００に提供するための手段である。

ソフトウェアを用いて実装される実施形態では、ソフトウェアは、コンピュータ可読媒体に格納され、取り外し可能媒体１３０、入力／出力（Ｉ／Ｏ）インタフェース１３５、または通信インタフェース１４０によってシステム１００にロードすることができる。このような実施形態では、ソフトウェアは、電気通信信号１５５の形態でシステム１００にロードされる。ソフトウェアは、プロセッサ１１０によって実行されるとき、好ましくは、プロセッサ１１０に、本明細書の他の場所で説明されるプロセスおよび機能のうちの１つ以上を実行させる。

実施形態において、入力／出力インタフェース１３５は、システム１００の１つ以上の部品と１つ以上の入力および／または出力装置との間のインタフェースを提供する。入力装置の例は、限定されないが、センサ、キーボード、タッチスクリーンもしくは他のタッチセンシティブ装置、生体感知装置、コンピュータマウス、トラックボール、ペン系のポインティング装置、および／または同種のものを含む。出力装置の例としては、限定されないが、他の処理装置、陰極線管（ＣＲＴ）、プラズマディスプレイ、発光ダイオード（ＬＥＤ）ディスプレイ、液晶ディスプレイ（ＬＣＤ）、プリンタ、真空蛍光ディスプレイ（ＶＦＤ）、表面伝導電子エミッタディスプレイ（ＳＥＤ）、電界放出ディスプレイ（ＦＥＤ）、および／または同種のものが挙げられる。場合によっては、タッチパネルディスプレイ（例えば、スマートフォン、タブレット、または他のモバイル装置）の場合など、入力装置と出力装置とが組み合わされることがある。

システム１００は、音声ネットワークおよび／またはデータネットワークを介した無線通信を容易にする任意の無線通信部品を含むこともできる。無線通信部品は、アンテナシステム１７０と、無線システム１６５と、ベースバンドシステム１６０とを含む。システム１００において、無線周波数（ＲＦ）信号は、無線システム１６５の管理の下、アンテナシステム１７０によって空中で送受信される。

一実施形態において、アンテナシステム１７０は、１つ以上のアンテナと、アンテナシステム１７０に送信および受信信号経路を提供するために切り換え機能を実行する１つ以上のマルチプレクサ（図示せず）とを含み得る。受信経路において、受信ＲＦ信号は、マルチプレクサから、受信ＲＦ信号を増幅し増幅された信号を無線システム１６５に送信する低雑音増幅器（図示せず）に結合され得る。

別の実施形態では、無線システム１６５は、様々な周波数で通信するように構成されている１つ以上の無線機を含むことができる。一実施形態において、無線システム１６５は、復調器（図示せず）と変調器（図示せず）とを１つの集積回路（ＩＣ）に組み合わせることができる。また、復調器と変調器とは、別個の部品であってもよい。受信経路において、復調器は、ベースバンド受信オーディオ信号を残してＲＦ搬送波信号を剥ぎ取り、これは、無線システム１６５からベースバンドシステム１６０に送信される。

受信信号に音声情報が含まれている場合、ベースバンドシステム１６０は、その信号を復号化し、アナログ信号に変換する。そして、信号を増幅し、スピーカーに送る。また、ベースバンドシステム１６０は、マイクロフォンからアナログオーディオ信号を受信する。これらのアナログオーディオ信号は、ベースバンドシステム１６０によってデジタル信号に変換され、符号化される。ベースバンドシステム１６０はまた、送信のためにデジタル信号を符号化し、無線システム１６５の変調器部分に経路化されるベースバンド送信オーディオ信号を生成する。変調器は、ベースバンド送信オーディオ信号をＲＦ搬送波信号と混合し、アンテナシステム１７０に経路化され、電力増幅器（図示せず）を通過することができるＲＦ送信信号を生成する。電力増幅器は、ＲＦ送信信号を増幅し、それをアンテナシステム１７０に経路化し、そこで信号は送信のためにアンテナポートへ切り換えられる。

ベースバンドシステム１６０はまた、中央処理装置（ＣＰＵ）であってもよいプロセッサ１１０と通信可能に結合される。プロセッサ１１０は、データ記憶領域である１１５および１２０にアクセスすることができる。プロセッサ１１０は、好ましくは、主メモリ１１５または二次メモリ１２０に格納することができる命令（すなわち、開示されたソフトウェアなどのコンピュータプログラム）を実行するように構成されている。コンピュータプログラムは、ベースバンドプロセッサ１６０から受信されて、主メモリ１１０もしくは二次メモリ１２０に格納されるか、または受信時に実行されることも可能である。このようなコンピュータプログラムが実行されると、システム１００は、開示された実施形態の様々な機能を実行することができる。

（２．プロセスの概要）
ここから、決定的メモリ割り当てのためのプロセスの実施形態について詳細に説明する。説明するプロセスは、例えば、コンピュータプログラムまたはソフトウェアパッケージとして、１つ以上のハードウェアプロセッサ（例えば、プロセッサ１１０）によって実行される１つ以上のソフトウェアモジュールにおいて具現化することができることを理解するべきである。説明するプロセスは、ソースコード、オブジェクトコード、および／またはマシンコードで表される命令として実装することもできる。これらの命令は、ハードウェアプロセッサ１１０によって直接実行してもよいし、あるいは、オブジェクトコードとハードウェアプロセッサ１１０との間で動作する仮想マシンによって実行することもできる。

あるいは、説明するプロセスは、ハードウェア部品（例えば、汎用プロセッサ、集積回路（ＩＣ）、特定用途向け集積回路（ＡＳＩＣ）、デジタル信号プロセッサ（ＤＳＰ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）もしくは他のプログラマブル論理装置、個別ゲートもしくはトランジスタ論理など）、ハードウェア部品の組み合わせ、またはハードウェアおよびソフトウェア部品の組み合わせとして実装することができる。ハードウェアとソフトウェアとの交換可能性を明確に示すために、様々な例示的な構成要素、ブロック、モジュール、回路、およびステップを、その機能性の観点から一般的に本明細書で説明する。このような機能をハードウェアとして実装するか、ソフトウェアとして実装するかは、システム全体に課される特定の用途および設計上の制約に依存する。当業者であれば、特定のアプリケーションごとに様々な方法で説明した機能を実装することができるが、そのような実装の決定は、本発明の範囲から逸脱する原因となると解釈すべきではない。さらに、部品、ブロック、モジュール、回路、またはステップ内の機能のグループ化は、説明を容易にするためのものである。特定の機能またはステップは、本発明から逸脱することなく、１つの部品、ブロック、モジュール、回路、またはステップから別のものに移動させることができる。

さらに、本明細書で説明するプロセスは、サブプロセスの特定の配置および順序で例示されるが、各プロセスは、より少ない、より多い、または異なるサブプロセスと、サブプロセスの異なる配置および／または順序とで実施され得る。さらに、サブプロセスを特定の順序で説明または図示している場合でも、他のサブプロセスの完了に依存しない任意のサブプロセスは、その他の独立したサブプロセスの前、後、またはそれと並行して実行してもよいことを理解するべきである。

（２．１．メモリプール入門）
固定サイズのブロック割り当てでは、メモリ管理にはメモリプールが使用される。メモリプールは、同一ブロックサイズを持つ複数のメモリブロックをバケットにあらかじめ割り当てることで、動的なメモリ割り当てを可能にする。つまり、バケットはブロック数およびブロックサイズによって定義される。バケットのサイズは、ブロック数とブロックサイズとの積である。

メモリプールは、１つのバケットまたは複数のバケットを含むことができる。メモリプールが複数のバケットを含む場合、所与のバケットは、１つ以上の他のバケットと異なるサイズのメモリブロックを有してよく、かつ／または、１つ以上の他のバケットと異なる数のメモリブロックを有してよい。言い換えれば、メモリプールは、複数のバケットを含むことができ、各バケットのブロック数およびブロックサイズは、独立して構成することができる。メモリプール内の各バケットは、他のすべてのバケットと同一の、固定サイズを有してもよい。しかし、各バケットは、異なる数のブロックに分割することができる。簡単な例として、メモリプールは、それぞれ６５，５３６バイト（すなわち、６４キロバイト（ｋｂ））の大きさの４つのバケットを有することができる。バケットのうちの第１のものは、サイズがすべて８バイトの８，１９６ブロックを有することができ、バケットのうちの第２のものは、サイズがすべて６４バイトの１，０２４ブロックを有することができ、バケットのうちの第３のものは、サイズがすべて１，０２４バイト（１ｋｂ）の６４ブロックを有することができ、バケットのうちの第４のものは、サイズがすべて４，０９６バイト（４ｋｂ）の１６ブロックを有することができる。あるいは、メモリプール内の２つ以上のバケットは、異なるサイズを有してもよい。本明細書では、メモリプールを主に複数のバケットの集合体として説明するが、開示される実施形態は、単一のバケットからなるメモリプールに、何らの変更もなく適用することができることを理解されたい。

メモリプールのサイズはコンパイル時（すなわち、アプリケーションがコンパイルされる時）に固定される一方、アプリケーションは実行時（例えば、リアルタイムプログラム時）にメモリプールの所与のバケット内のメモリブロックを割り当て、アクセスし、解放することが可能である。重要なことは、メモリプールは、メモリの事前に割り当てられたバッファにおける動的な割り当てと解放とを提供し、それらをすべて一定時間内に実行できることである。かくして、メモリプールは決定的であり、したがって、いかなる割り当てまたは解放操作のための最悪の場合の時間を一定時間で保証するので、リアルタイムで、安全が重要なアプリケーションに適している。

通常、メモリプール内のバケットの寸法（すなわち、ブロックサイズおよびブロック数）は、コンパイル時に予め知っておく必要がある。しかし、アプリケーションが必要とするブロック数は、実行時（例えば、コンパイル時には分からない入力）に依存する場合があり、したがって、コンパイル時には分からない場合がある。したがって、リアルタイムアプリケーションや組み込みアプリケーションでは、ブロック数の上限がアプリケーションにハードコーディングされる。一方、離散的なデータ型を持つプログラミング言語では、アプリケーションが必要とするブロックサイズは、コンパイル時に分かっているはずである。

（２．２．アロケータの導入）
Ｃ＋＋などのプログラミング言語は、割り当ての実サイズを隠す高水準の抽象化機能を利用している。例えば、Ｃ＋＋標準ライブラリ（ｓｔｄ）は、マップ（ｓｔｄ：：ｍａｐ）、リスト（ｓｔｄ：：ｌｉｓｔ）、セット（ｓｔｄ：：ｓｅｔ）、プロミス（ｓｔｄ：：ｐｒｏｍｉｓｅ）、共有ポインタ（ｓｔｄ：：ｓｈａｒｅｄ＿ｐｔｒ）などのコンテナを提供している。これらのコンテナは、メモリの確保と解放とのためにアロケータを利用する。つまり、アロケータは、所与のコンテナに対するメモリの割り当てと解放とのすべての要求を処理する。

標準ライブラリはデフォルトで使用される汎用アロケータを提供する一方、コンテナは開発者が実装したカスタムアロケータをパラメータとして受け取り、使用することができる。しかし、アロケータによる実際の割り当てと解放とは、標準ライブラリの実装の内部で行われる。したがって、カスタムアロケータの呼び出しは、通常、ソフトウェアコードには現れない。つまり、カスタムアロケータが使用するバケットのブロックサイズは、通常、コンパイル時にソフトウェアコードから導出することができない。

アロケータのテンプレートは、コンテナが内部で使用する別のデータ型を有する新しいアロケータをインスタンス化するリバインド構造を含む。図２は、一実施形態による、リバインド構造を持つアロケータテンプレートのソースコードの例を示す。図示のように、リバインド構造は、コンテナが内部で必要とする第２のデータ型（例えば、図２の「ｔｙｐｅｎａｍｅ Ｕ」）について、第１のデータ型（例えば、図２の「ｔｙｐｅｎａｍｅ Ｔ」）について使用するカスタムアロケータであり得る同一アロケータの新しいインスタンス化を作成する。例えば、「ｓｔｄ：：ｌｉｓｔ」コンテナは、所与のデータ型のためのカスタムアロケータを取得し得るが、所与のデータ型だけでなく、ノードのためのメモリも割り当てる必要がある。このため、リバインド構造は「ｓｔｄ：：ｌｉｓｔ」コンテナで使用する内部「ｌｉｓｔ＿ｎｏｄｅ」データ型にカスタムアロケータをリバインドする。このように、カスタムアロケータに必要なデータサイズが導出できるはずのソフトウェアコードの場所は、リバインド構造に隠されている。

（２．３．メモリプールの実装）
次に、開示された実施形態で使用することができるメモリプールの実装例について説明する。開示された実施形態の理解に完全な説明は必要ないため、最小限の実装のみを図示している。したがって、読みやすくするためにいくつかのエラーチェックが省略され、説明する実装はスレッドセーフではなく、デフォルトの整合が仮定されている。他の実装では、より堅牢なエラーチェックを含み、スレッドセーフであり、かつ／またはデフォルトの整合を仮定しないこともできる。使用される特定の実装は、メモリプールが使用される特定のアプリケーションに依存し得ることを理解されたい。

一実施形態では、メモリプールの複数のインスタンスは、同一アプリケーション内で定義することができる。安全性が重要なアプリケーションでは、安全のためにメモリプールを分離する必要のあることが多いので、これは重要であり得る。例えば、複数のスレッドを有するアプリケーションにおいて、スレッドが互いにロックするのを防ぐために、各スレッドに対して別々のメモリプールをインスタンス化することができる。

図３は、一実施形態による、メモリプール内のバケットの実装例のソースコードを示す。各バケットは、一定のブロックサイズ（ＢｌｏｃｋＳｉｚｅ）と一定のブロック数（ＢｌｏｃｋＣｏｕｎｔ）とを有し、これらはいずれも、そのバケット（ｂｕｃｋｅｔ）コンストラクタに渡されるパラメータによって定義される。各バケットはまた、バケット内に割り当てられる実際のメモリへのポインタ（ｍ＿ｄａｔａ）と、バケット内の各ブロックに対して１ビットを使用してメモリ割り当てを追跡するビットマップからなる台帳へのポインタ（ｍ＿ｌｅｄｇｅｒ）とを含む。バケット内の各ブロックのインデックスは、該ビットマップの各ビットのインデックスに対応する。ブロックが割り当てられると、そのブロックのインデックスに対応するビットマップ内のビットを「１」に設定することができ、ブロックが割り当て解除されると、そのブロックのインデックスに対応するビットマップ内のビットを「０」に設定することができる。

また、バケットの実装例は、以下の機能を含む。
－公開の「ｂｅｌｏｎｇ（）」関数は、パラメータとして渡されたメモリポインタがバケットに属するかどうかをテストする。
－公開の「ａｌｌｏｃａｔｅ（）関数およびｄｅａｌｌｏｃａｔｅ（）」関数は、バケット内のメモリブロックの割り当ておよび解放をそれぞれする。
－非公開の「ｆｉｎｄ＿ｃｏｎｔｉｇｕｏｕｓ＿ｂｌｏｃｋｓ（）」関数は、パラメータとして数値「ｎ」を受け取り、連続する「ｎ」個のブロックの集合を見つけようとするものである。例えば、この関数は台帳のビットマップをスキャンして、連続した「ｎ」個の空きブロックを表す、ビットマップ内の連続した「０」の列を探す。ｎ個の連続した空きブロックが見つかった場合、その最初のブロックへのインデックスを返す。ｎ個の連続した空きブロックが見つからなかった場合、ブロック数（ＢｌｏｃｋＣｏｕｎｔ）を返す。
－非公開の「ｓｅｔ＿ｂｌｏｃｋｓ＿ｉｎ＿ｕｓｅ（）」関数は、インデックスと数値「ｎ」とを受け取り、インデックスから始まる「ｎ」個のブロックの集合を、割り当て済みまたは「使用中」としてマークする。例えば、この関数は、台帳のビットマップのインデックスから始まる「ｎ」個のビット列を「１」に設定することができる。
－非公開の「ｓｅｔ＿ｂｌｏｃｋｓ＿ｆｒｅｅ（）」関数は、インデックスと数値「ｎ」とを受け取り、インデックスから始まる「ｎ」個のブロックの集合を、割り当て解除または「空き」としてマークする。例えば、この関数は、台帳のビットマップのインデックスから始まる「ｎ」個のビット列を「０」に設定することができる。

図４は、一実施形態による、バケットのためのコンストラクタおよびデストラクタの実装例のソースコードを示す。図示のように、コンストラクタは、「ｓｔｄ：：ｍａｌｌｏｃ」を利用して、バケット内のデータに対してバケットのサイズ（ＢｌｏｃｋＳｉｚｅ＊ＢｌｏｃｋＣｏｕｎｔ）に等しいメモリを割り当て、台帳に対してブロック数（ＢｌｏｃｋＣｏｕｎｔ）に等しいメモリを割り当てる。なお、「ｓｔｄ：：ｍａｌｌｏｃ」の代わりに、Ｃ＋＋プログラミング言語の「ｎｅｗ」演算子を使ってもよい。いずれの場合も、コンストラクタはデータと台帳とに割り当てられたメモリをゼロに初期化する。仮定したデフォルトの整合ではなく、カスタムの整合が必要な場合は、バケットのコンストラクタで実装することができる（例えば、「ｓｔｄ：：ｍａｌｌｏｃ」をカスタムの整合を提供できる関数で置き換えるなど）。

図５は、一実施形態による、バケット内のブロックを割り当てるための「ａｌｌｏｃａｔｅ（）」関数の実装例のソースコードを示す。図示のように、「ａｌｌｏｃａｔｅ（）」関数は、割り当てられるバイト数を入力パラメータとして受け取り、バイト数をブロックサイズで割り、必要であれば切り上げることによって、ブロックの数「ｎ」に変換する。「ａｌｌｏｃａｔｅ（）」関数は、「ｆｉｎｄ＿ｃｏｎｔｉｇｕｏｕｓ＿ｂｌｏｃｋｓ（）」関数を呼び出して、「ｎ」個の連続した空きブロックの集合があるかどうかを判断する。「ｎ」個の連続した空きブロックの集合がない場合、「ａｌｌｏｃａｔｅ（）」関数は０を返す。「ｎ」個の連続した空きブロックがある場合、「ａｌｌｏｃａｔｅ（）関数は「ｓｅｔ＿ｂｌｏｃｋｓ＿ｉｎ＿ｕｓｅ（）」関数を呼び出してブロックを割り当て済みとし、バケット内のこの「ｎ」個の連続した現在割り当てられたブロックの集合の最初のブロックへのポインタを返す。

図６は、一実施形態による、バケット内のブロックを解放するための「ｄｅａｌｌｏｃａｔｅ（）」関数の実装例のソースコードを示す。図示のように、「ｄｅａｌｌｏｃａｔｅ（）」関数は、入力パラメータとしてポインタと、割り当て解除されるバイト数とを受け取る。「ｄｅａｌｌｏｃａｔｅ（）」関数は、バケットのデータの開始点とポインタとの間の距離を計算し、このポインタの距離に基づいて、割り当て解除される最初のブロックのインデックスを計算する。次に、「ｄｅａｌｌｏｃａｔｅ（）」関数は、入力パラメータとして受け取ったバイト数に基づいて、割り当て解除されるブロック数を計算し、「ｓｅｔ＿ｂｌｏｃｋｓ＿ｆｒｅｅ（）」関数を呼び出して、計算した最初のブロックのインデックスから始まるブロック数が割り当て解除されたとマークする。

前述したように、メモリプールは、単に、１つ以上のバケット（多くの場合、複数のバケット）の集合体である。各バケットには、ブロックサイズとブロック数との２つのプロパティがある。１つ以上のバケットに対するこのプロパティの対の集合体は、メモリプールのインスタンスを定義する。図７は、一実施形態による、メモリプールを定義するためのテンプレート構造の実装例のソースコードを示す。「ｉｄ」パラメータは、メモリプールのインスタンスを識別する。識別子は、整数（例えば、メモリプールの第１のインスタンスのための「１」、メモリプールの第２のインスタンスのための「２」、等）または他のデータ型（例えば、文字列）とすることができる。デフォルトの実装では、バケットの無い（つまり、タプルが空の）メモリプールを定義する。

図８は、一実施形態による、メモリプールを定義するためのテンプレート構造を特定のアプリケーション例に特殊化する実装例のソースコードを示す。このソースコードは、アプリケーションをコンパイルするために使用されるヘッダファイルにおいて提供されてもよい。テンプレート構造は、３つの異なる構成を有する３つのバケットからなる、識別子が「１」のメモリプールを定義する。第１のバケットはブロックサイズが１６バイトでブロック数が１００００、第２のバケットはブロックサイズが３２バイトでブロック数が１００００、第３のバケットはブロックサイズが１０２４バイトでブロック数が５００００である。これは一例であり、メモリプール内のバケットの正確な数や構成は、メモリプールを使用するアプリケーションに依存することを理解する必要がある。重要なのは、メモリプールを定義するファイルを生成したり修正したりして、メモリプールを特定のアプリケーションに合わせてカスタマイズできることである。

図９は、一実施形態による、メモリプールの特性を定義するいくつかの構造の実装例のソースコードを示す。バケット数特性（ｂｕｃｋｅｔ＿ｃｏｕｎｔ）は、メモリプール内のタプルのサイズ（すなわち、バケット数）を表す。プールタイプ特性（ｐｏｏｌ＿ｔｙｐｅ）は、バケット数に等しいサイズを有するバケットの配列である。「ｇｅｔ＿ｓｉｚｅ」および「ｇｅｔ＿ｃｏｕｎｔ」関数は、メモリプールの識別子（ｉｄ）とそのメモリプールのタプル内のバケットのインデックス（Ｉｄｘ）とで識別されるバケットのブロックサイズおよびブロック数のプロパティをそれぞれ返す。

図１０は、一実施形態による、メモリプールを作成するための関数の実装例のソースコードを示す。図示のように、「ｇｅｔ＿ｉｎｓｔａｎｃｅ（）」関数は、メモリプールの識別子を用いてインスタンス化され、静的ローカル配列（ｐｏｏｌ＿ｔｙｐｅ）を定義する。「ｇｅｔ＿ｉｎｓｔａｎｃｅ（）」関数は、メモリプールのタプル内のバケットごとに「ｇｅｔ＿ｓｉｚｅ（）」関数および「ｇｅｔ＿ｃｏｕｎｔ（）」関数を呼び出して、実際のバケットで配列をインスタンス化し、それによってメモリプールを作成する。

図１１は、一実施形態による、メモリプール初期化の実装例のソースコードを示す。図示のように、「ｉｓ＿ｄｅｆｉｎｅｄ（）」関数は、指定された識別子を有するメモリプールが少なくとも１つのバケットを含んでいるか（真）またはバケットを有さないか（偽）を示すブール値を返す。「ｉｎｉｔｉａｌｉｚｅ（）」関数は、メモリプールをインスタンス化するためのヘルパー関数である。前述のように、デフォルトのメモリプールはバケットを持たずにインスタンス化されることがあるため、これら２つの関数は有用である。

（２．４．バケットの選択）
割り当てが実行されるとき、アロケータは割り当てが１つのデータオブジェクトに対するものか、複数のデータオブジェクトに対するものかについての情報を持っていない。むしろ、アロケータは格納するデータのバイト数を受け取るだけである。つまり、割り当てレベルでは、格納するデータオブジェクトに関する情報は得られない。したがって、アロケータは、格納するデータオブジェクトの数ではなく、格納するデータのバイト数に基づいて、所与の割り当てに対して適切なバケットを選択しなければならない。この選択は、さまざまな方法で実装することができる。

例えば、アプリケーションは、格納するデータに十分な大きさのバケットに到達するまで、メモリプール内のバケットを単純にスキャンすることができる。この場合、バケットはそのブロックサイズによってソートされるべきである。図１２は、一実施形態による、このファーストフィット戦略を利用する「ａｌｌｏｃａｔｅ（）」関数の実装例のソースコードを示す。図示のように、「ａｌｌｏｃａｔｅ（）」関数は、格納するデータのサイズを表す入力パラメータ（ｂｙｔｅｓ）以上のブロックサイズを有するバケットを見つけるまで、バケットを繰り返し処理する。そのようなバケットが見つかり次第、「ａｌｌｏｃａｔｅ（）」関数はそのバケットにデータを割り当て、そのバケットへのポインタを返す。そうでない場合は、「ａｌｌｏｃａｔｅ（）」関数は割り当てに失敗したことを示す例外を投げる。このファーストフィット戦略は、「ｓｔｄ：：ｍａｐ」や「ｓｔｄ：：ｌｉｓｔ」のような、データオブジェクトのために一つずつメモリを確保するコンテナに適している。しかし、複数のデータオブジェクトに対して同時にメモリを確保する他のコンテナ（例えば、ハッシュノードとハッシュノードへのポインタとの両方に対してメモリを確保する「ｓｔｄ：：ｕｎｏｒｄｅｒｅｄ＿ｍａｐ」など）には、このファーストフィット法は適さない可能性がある。

より高度な戦略として、アプリケーションのソフトウェアコードに対してコンパイル時の解析を行うことができる。その分析結果を利用して、特定のバケットを特定のデータ型に（例えば「ｔｙｐｅｎａｍｅ」に基づいて）バインドすることができる。言い換えれば、特定のバケットを特定のデータ型に合わせるように構成することができる。

すべての型のコンテナ（例えば、「ｓｔｄ：：ｍａｐ」、「ｓｔｄ：：ｌｉｓｔ」、「ｓｔｄ：：ｕｎｏｒｄｅｒｅｄ＿ｍａｐ」など）に適するであろう実行時の別の手段として、「ａｌｌｏｃａｔｅ（）」関数は、最も少ない浪費メモリおよび／または最小数の割り当てブロックをもたらすバケットを選択することができる。図１３は、一実施形態による、バケットの選択を支援するためのインフォ（「ｉｎｆｏ」）構造の実装例のソースコードを示す。図示のように、インフォ構造は、割り当てのためのそれぞれの浪費量と、割り当てに必要とされるであろうブロックの数とに基づいて、２つのバケットを比較する演算子を定義する。この場合、浪費量は、格納するデータのサイズと、データを格納するために必要とされるであろうブロックの合計サイズとの間のバイトの差として定義される。演算子は、２つのバケットの浪費量が等しくない場合は、浪費量が最少となるバケットを優先し、２つのバケットの浪費量が等しい場合は、最小のブロック数を必要とするバケットを優先することにより、浪費量の最少化を図るように設計されている。このように、演算子は、バケットの集合をそれぞれの浪費量で順序付けし、浪費量が最も少なくなるバケットを選択するのに使用することができる。

図１４は、一実施形態による、図１３からのインフォ構造を利用する、メモリプール内のバケットを割り当てるための「ａｌｌｏｃａｔｅ（）」関数の実装例のソースコードを示す。図示のように、「ａｌｌｏｃａｔｅ（）」関数は、メモリプール内の各バケットの浪費量と必要なブロック数とを計算し、これらの値をインフォ構造の配列に格納する。配列の各エントリは、バケットのうちの１つに正確に対応する。次に、「ａｌｌｏｃａｔｅ（）」関数は、インフォ構造に定義された演算子に基づいて、浪費量が最も少ないバケットから最も多いバケットへと配列を並べ替える。そして、「ａｌｌｏｃａｔｅ（）」関数は、この並べ替えのされた配列から、浪費量が最も少ないバケットを選択することができる。

アロケータは連続したブロックの集合を割り当てる必要があるため、メモリプールのバケット内でメモリが断片化し得る。しかし、アプリケーションの開発者は、開発中に、割り当てと解放とのパターンに注意し、別々のメモリプールを利用することで、メモリの断片化を緩和することができる。

図１５は、一実施形態による、メモリプール内のバケットを解放するための「ｄｅａｌｌｏｃａｔｅ（）」関数の実装例のソースコードを示す。図示のように、「ｄｅａｌｌｏｃａｔｅ（）」関数は、入力パラメータとしてポインタとバイト数とを受け取る。「ｄｅａｌｌｏｃａｔｅ（）」関数は、ポインタがバケットに属するかどうかをチェックし、属していれば、バケット内のブロックを解放するための「ｄｅａｌｌｏｃａｔｅ（）」関数を呼び出す。

（２．５．アロケータの実装）
開示された実施形態で使用されるアロケータは、「ｓｔｄ：：ａｌｌｏｃａｔｏｒ＿ｔｒａｉｔｓ」と互換性があるＣ＋＋アロケータモデルを実装してもよい。Ｃ＋＋の多くの構成要素は、あるアロケータから別のアロケータへ静かに移行することができる。これにより、異なるコンテナ間でデータを移動するときに、アロケータが１つのメモリプールから別のメモリプールにデータを移動する可能性が生じ、非決定的メモリ割り当てを生じる可能性がある。したがって、一実施形態において、各アロケータは、アロケータがメモリプール間でデータを移動できないことを保証するために、コンパイル時にメモリプールの単一の特定のインスタンスにバインドされる。

一実施形態では、各アロケータは、それがバインドされるメモリプールが定義されるまで、別のリソースから割り当てをするように実装されている。上述したように、メモリプールは、バケットが無い（すなわち、未定義）状態でインスタンス化される場合がある。したがって、アロケータは、そのメモリプールが未定義である場合であっても、適切に機能できるほうがよい。したがって、アロケータは、バインドされるメモリプールが定義されるまで、メモリヒープなどのデフォルトのリソースから割り当てをするように構成されてもよい。そして、メモリプールが定義されると、アロケータは自動的にメモリプールからの割り当てを開始する。

図１６は、一実施形態による、同一メモリプールがネストされたデータオブジェクトに使用される使用シナリオの例を示す。図示のように、静的プールアロケータ（ｓｔａｔｉｃ＿ｐｏｏｌ＿ａｌｌｏｃａｔｏｒ）は、データ型およびメモリプールの識別子を含む、２つのテンプレート引数を有する。このシナリオでは、リストオブジェクトおよびリストオブジェクトのベクトルは、同一メモリプール（すなわち、「ＡｌｌｏｃＩｄ＝１」によって識別されるメモリプール）から割り当てられる。ベクトルに値が入力されると、リスト用のデータとベクトル用のデータとが同一メモリプールに格納される。

図１７は、一実施形態による、ネストされたデータオブジェクトのために別々のメモリプールが使用される別の使用シナリオを示す図である。図示のように、リスト（すなわち、「ｌｉｓｔ＿ａｌｌｏｃａｔｏｒ」）およびベクトル（すなわち、「ｖｅｃｔｏｒ＿ａｌｌｏｃａｔｏｒ」）に対して２つの異なるアロケータがテンプレート「ｓｔａｔｉｃ＿ｐｏｏｌ＿ａｌｌｏｃａｔｏｒ」から作成される。それぞれのアロケータは、異なるメモリプールにバインドされる。例えば、リストアロケータは、第１の識別子（すなわち、「ＡｌｌｏｃＩｄ＝１」）を持つメモリプールにバインドされ、ベクトルアロケータは、第２の識別子（すなわち、「ＡｌｌｏｃＩｄ＝２」）を持つメモリプールにバインドされている。その結果、ベクトルに値が入力されると、リスト用のデータはベクトル用のデータとは別のメモリプールに格納される。

図１８は、一実施形態による、静的プールアロケータ（ｓｔａｔｉｃ＿ｐｏｏｌ＿ａｌｌｏｃａｔｏｒ）の実装例のソースコードを示す。注目すべきは、実装例は、割り当ての理解に最も関連するコードのみを含み、一方、割り当ての理解に無関係なコードを省略していることである。省略されたコードの多くは、「ｓｔｄ：：ｐｍｒ：：ｐｏｌｙｍｏｒｐｈｉｃ＿ａｌｌｏｃａｔｏｒ」のコードと同一である。

図示のように、リバインド構造は、静的プールアロケータを同一メモリプールにのみリバインドする。具体的には、リバインド構造は、静的プールアロケータを再インスタンス化するときに、メモリプールの同一識別子を使用する。同様に、コピーコンストラクタおよび代入演算子も同一メモリプールの識別子を使用し、静的プールアロケータが単一のメモリプールにバインドされ、異なるメモリプール間でデータを移動することが禁止されることを保証する。

さらに、静的プールアロケータは上流リソース（ｍ＿ｕｐｓｔｒｅａｍ＿ｒｅｓｏｕｒｃｅ）を定義し、これはデフォルトリソースとして（「ｐｍｒ：：ｇｅｔ＿ｄｅｆａｕｌｔ＿ｒｅｓｏｕｒｃｅ（）」関数を呼び出すことで）初期化される。したがって、メモリプールの識別子が未定義であっても、静的プールアロケータはメモリを確保することができる。特に、メモリプールが未定義である場合、静的プールアロケータはデフォルトリソース（例えば、上位アプリケーションで利用可能なメモリヒープ）からメモリを割り当てる。

図１９は、一実施形態による、静的プールアロケータの「ａｌｌｏｃａｔｅ（）」関数の実装例のソースコードである。図示のように、メモリプールが定義されている場合、この関数は、アロケータにバインドされているメモリプールからメモリを割り当てる。そうでなければ、メモリプールが定義されていない場合、この関数は、上流リソースからメモリを割り当てる。メモリプールが定義されている間の実行時の部分は、リアルタイムで安全性が重要な環境に適しかつ保証される、保証可能なモードと考えることができる。一方、メモリプールが定義されていない実行時は、リアルタイムで安全性が重要な環境には適さず保証もされない、保証不能なモードと考えることができる。

（２．６．データ型サイズの集合体）
注目すべきは、図１９に示すように、静的プールアロケータ（ｓｔａｔｉｃ＿ｐｏｏｌ＿ａｌｌｏｃａｔｏｒ：：ａｌｌｏｃａｔｅ）の「ａｌｌｏｃａｔｅ（）」関数において、割り当てが実行されているデータ型（Ｔ）が既知であることである。したがって、実行時にこの「ａｌｌｏｃａｔｅ（）」関数でデータ型のサイズを出力し、メモリ割り当てが行われているデータ型のサイズを実行時のログに記録することが可能である。しかし、これでは、すべてのデータ型に対する完全なカバレッジが保証されないため、理想的とは言えない。例えば、割り当てがまれなデータ型は、所与の有限の実行時間中に記録されずに終わるかもしれない。さらに、一部のアプリケーションで割り当ての完全なカバレッジが保証されたとしても、すべての実世界のアプリケーションでは不可能か非現実的である。さらに、開発者は一般に呼び出しグラフに関する情報（たとえば、実行時にどのように、そしてなぜ「ａｌｌｏｃａｔｅ（）」関数に到達したのか）を持っていない。したがって、すべての可能なデータ型が考慮されていることを証明することは困難である。

理想的には、静的プールアロケータの「ａｌｌｏｃａｔｅ（）」関数へのすべての呼び出しは、実行時のフローにかかわらず（たとえば、その関数が実行時の特定のデータ型に対して実際に呼び出されたかどうかにかかわらず）、コンパイルされたコード内のすべてのデータ型に対してインスタンス化され、登録されるであろう。また、これらの割り当てにつながるすべての呼び出しパスを登録することも有用であろう。一実施形態では、これらの登録を可能にするために、インスツルメントコードをソースコードに注入している。

図２０は、一実施形態による、インスツルメントネームスペースの実装例のソースコードを示す。図示のように、インスツルメントネームスペースは、３つの引数と「ｔｙｐｅ＿ｒｅｇ（）」と呼ばれるダミー関数とを有するテンプレートとして定義されている。テンプレートの３つの引数は、メモリプールの識別子、データ型の名称、およびデータ型のサイズである。「ｔｙｐｅ＿ｒｅｇ（）」関数は、実質的な動作を行わないので、ダミー関数である。むしろ、ダミー関数の唯一の目的は、各割り当ての３つの引数を記録することである。したがって、ダミー関数には任意の名称を付けることができると理解しなければならない。さらに、ダミー関数は空のものとして図示されているが、別の実施形態では、１つ以上の命令を含むことができる。

図２１は、一実施形態による、図１９に例示した静的プールアロケータの「ａｌｌｏｃａｔｅ（）」関数に注入されたインスツルメントコードの一実施例のソースコードを示す。図示のように、「ａｌｌｏｃａｔｅ（）」関数に「ｉｎｓｔｒｕｍｅｎｔ：：ｔｙｐｅ＿ｒｅｇ（）」関数への呼び出しが注入されている。ダミーの「ｔｙｐｅ＿ｒｅｇ（）」関数への呼び出しは、メモリプールの識別子、データ型の名称、およびデータ型のサイズを、空のｔｙｐｅ＿ｒｅｇ（）関数に渡す。

上述したように、「ｔｙｐｅ＿ｒｅｇ（）」関数はダミー関数であり、実際にはアプリケーションの動作に何ら影響を与えない。「ｔｙｐｅ＿ｒｅｇ（）」関数の呼び出しの意義は、アプリケーションのソースコードをコンパイルして生成されるオブジェクトコードから検出できることにある。つまり、アプリケーションをソースコードからオブジェクトコードにコンパイルした後、解析ソフトはコンパイルされたオブジェクトコードをスキャンして「ｔｙｐｅ＿ｒｅｇ（）」関数の呼び出しの各出現箇所を特定することができる。次に、解析ソフトウェアは、識別されたオブジェクトコードの断片から、メモリプールの識別子、データ型の名称、およびデータ型のサイズを抽出し、関連するデータ型およびそれらのデータ型の関連するサイズに各メモリプールを登録することが可能である。そして、解析ソフトは、これらの登録に基づいて、各メモリプールの適切なバケット構成を決定することができる。有利なことに、有限の実行時間中にそのメモリプールからそのデータ型にメモリが割り当てられるかどうかにかかわらず、メモリプールを使用する可能性のあるすべてのデータ型が確実に把握されるようにすることができる。

図２２は、一実施形態による、静的プールアロケータの「ｄｅａｌｌｏｃａｔｅ（）」関数の実装例のソースコードを示す。図示のように、メモリプールが定義されている場合、「ｄｅａｌｌｏｃａｔｅ（）」関数は、メモリプールの「ｄｅａｌｌｏｃａｔｅ（）」関数を用いてメモリプールから割り当て解除を行う。そうでなければ、メモリプールが未定義である場合、「ｄｅａｌｌｏｃａｔｅ（）」関数は、上流リソースからの割り当てを解除する。

（２．７．バケット定義の生成）
一実施形態では、実際の割り当てに応じたバケット定義を収集するために、まず、ソースコードをオブジェクトコードにコンパイルする。例えば、Ｃ＋＋で書かれたソースコードの場合、ソースコードは、「Ｃｌａｎｇ」コンパイラで、解析と操作とが容易な中間ビットコードである「ＬＬＶＭ（旧低レベル仮想マシンの頭文字）」ビットコードにコンパイルすることができる。ソースコードをコンパイルする際に、以下のパラメータをコンパイラに設定すると便利である（「Ｃｌａｎｇ」コンパイラを仮定しているが、他のコンパイラにも翻訳可能である）。
－ｇは、呼び出しグラフを生成するための「ｆｉｌｅ：ｌｉｎｅ」情報を持つようにする。
－Ｏ０を指定して、コンパイラが最適化の際に注入されたダミー関数への呼び出しを削除してしまう可能性があるため、コンパイラに最適化を行わないようにする。
－ｅｍｉｔ－ｌｌｖｍは、ソースコードをネイティブ命令の代わりにビットコードにコンパイルするようにする。
－ＤＮＤＥＢＵＧは、データ構造のリリースバージョンを取得するようにする。

次に、各メモリプールの各インスタンスに割り当てられているすべての一意なデータ型のリストを構成するために、コンパイルされたコード上で１つ以上のパスが実装される。さらに、パスにより、すべての割り当てに対して呼び出しグラフを構築することができ、これはデバッグ目的に有用であるとともにアプリケーションがどのように動作するかについての洞察を提供することもできる。パスは、「Ｃｌａｎｇ」コンパイラによって生成される「ＬＬＶＭ」ビットコード上の「ＬＬＶＭ ｏｐｔ」ツールを使用して実装することができる。「ＬＬＶＭ ｏｐｔ」ツールは、「ＬＬＶＭ」ビットコードファイルに対してカスタムパスを実行することができる。効率化のために、コンパイラが複数のビットコードファイルを生成する場合、複数のビットコードファイルを単一のビットコードファイルに結合して、各パスが単一の合成ビットコードファイルに対してのみ実行されるようにしてもよい。

図２３は、一実施形態による、パスの実装例のソースコードを示す。図示されたパスは、正規表現を使用してダミー「ｔｙｐｅ＿ｒｅｇ（）」関数への関数呼び出しを抽出し解析し、抽出されたデータのリストを生成する関数パスである。特に、リストの各行は、ダミー「ｔｙｐｅ＿ｒｅｇ（）」関数への１つの関数呼び出しを表し、ダミー「ｔｙｐｅ＿ｒｅｇ（）」関数への関数呼び出しにおいてパラメータとして渡される、メモリプールの識別子、そのメモリプールを使用するデータ型のサイズ、およびそのメモリプールを使用するデータ型の名称を含む。リストは、可能的に、単一のメモリプールに関連付けられた複数のデータ型および／または複数のメモリプールに関連付けられた単一のデータ型を含む、１つ以上のデータ型を１つ以上のメモリプールに関連付ける行を含み得ることを理解されたい。

実際には、「ｌｌｖｍ：：ＦｕｎｃｔｉｏｎＰａｓｓ」の代わりに「ｌｌｖｍ：：ＭｏｄｕｌｅＰａｓｓ」を使って、解析対象のソフトウェアモジュール全体から呼び出しグラフを生成することができる。モジュールのエントリポイント（例えば、「ｍａｉｎ（）」関数）から始める深さ優先の検索を実行することができる。「ｔｙｐｅ＿ｒｅｇ（）」関数への呼び出しを発見するたびに、割り当てのデータ型（例えば、サイズおよび／または名称）を登録し（例えば、上記のようにリストに出力または格納する）、割り当ての呼び出しグラフを登録する（例えば、ファイルに出力または格納する）。効率化のために、呼び出しグラフの再帰を検出し、それらの再帰を表す呼び出しグラフの分岐は、割り当てで終わらないので、落とすことができる。このパスの結果は、すべての一意な割り当てのリストである。上述したように、この一意の割り当てのリストは、各割り当てについて、メモリプールの識別子、そのメモリプールから割り当てられたデータ型のサイズおよび／またはそのデータ型の名称を含むことができる。パスの間に、同一割り当て（すなわち、メモリプール識別子、データ型のサイズ、およびデータ型の名称の同一組み合わせ）が複数回検出され得ることを理解されたい。したがって、一意な割り当てのリストを得るために、メモリプール識別子、データ型のサイズ、およびデータ型の名称の一意の組み合わせごとに１つのエントリのみが存在するように、リスト内の割り当てについて、重複を除去してもよい。

第三に、メモリプールの定義とメモリプールが使用するバケットの定義とは、パスによって生成された一意な割り当てのリストから生成される。例えば、一意な割り当てのリストは、リスト内の割り当てに従って特殊化されたメモリプールを定義するヘッダファイルに変換することができる。言い換えれば、各メモリプールは、そのメモリプールの識別子を構成する一意な割り当てのリスト中の割り当てのデータ型に従ってバケットの構成を最適化するバケット記述子を用いてヘッダファイルで定義することができる。

図２４は、本明細書で説明する静的プールアロケータの一実施形態を使用する単純なアプリケーションのソースコードを示す。このアプリケーションは、実世界の例ではなく、開示された実施形態の動作を実証するためにのみ使用されていることを理解されたい。図示のように、アプリケーションは、「ｘ（）」関数を呼び出す「ｆ（）」関数を呼び出す「ｍａｉｎ（）」関数を含んでいる。「ｘ（）」関数は、識別子「３」のメモリプールにバインドされた静的プールアロケータで「ｌｓｔ」という整数リストをインスタンス化し、「ｌｓｔ」に整数「１」を追加する。

図２５は、一実施形態による、図２４に例示した単純なアプリケーションのパスによって検出された割り当てのために生成された呼び出しグラフを示す。特に、図示の呼び出しグラフは、リスト「ｌｓｔ」に整数「１」を追加することによってトリガされたリストノードの割り当てのためのものである。したがって、呼び出しグラフは、メモリプール識別子「３」、データ型のサイズ「２４」（すなわち、リストノードのバイト単位のサイズ）、およびデータ型の名称「ｌｉｓｔ＿ｎｏｄｅ」に関連付けられている。呼び出しグラフから、各割り当ての仕組みと理由とを知ることができる。

注目すべきは、この方法で生成された呼び出しグラフは、仮想呼び出し、関数ポインタを介した呼び出し、およびインラインアセンブリの可能性があるため、不完全である可能性のあることである。しかし、この問題は、呼び出しグラフを一意な割り当てのリストと組み合わせて、すべての割り当てがカバーされていることを証明可能に保証することによって軽減することができる。このアプローチでは、実行中に決して呼び出されることのない到達不可能な割り当てであるオーファン割り当てを検出することができる（例えば、呼び出しグラフには存在しないが、一意な割り当てのリストには存在する）。安全性の観点からは、一般に、割り当てを過少に含むことよりも過大に含むことの方が良い。

「Ｃｌａｎｇ」コンパイラを利用する一実施形態では、解析ソフトウェアは、「ｏｐｔ」コマンドを使用して、コンパイラによって生成されたビットコード上で実行することができる。例えば、図２４に例示したアプリケーションのビットコード上で解析パスを実装した共有オブジェクト（ＳＯ）コンパイルライブラリファイルを実行するには、次のコマンドを使用することができる。

ｏｐｔ －ｌｏａｄ ａｌｌｏｃ－ａｎａｌｙｚｅｒ．ｓｏ －ａｌｌｏｃ－ａｎａｌｙｚｅ －ｇｅｎ－ｈｄｒ ｍｙ＿ｄｅｆｓ．ｈｐｐ －ｅｎｔｒｙ－ｐｏｉｎｔ “ｍａｉｎ”＜ ｈｏｍｅ／ｐｒｏｇｒａｍ．ｂｃ －ｏ ／ｄｅｖ／ｎｕｌｌ

基本的にこのコマンドは、アロケータ解析ツール（ａｌｌｏｃ＿ａｎａｌｙｚｅｒ．ｓｏ）をロードし、ビットコードファイル（ｈｏｍｅ／ｐｒｏｇｒａｍ．ｂｃ）の「ｍａｉｎ（）」関数を起点として、ヘッダファイル（ｍｙ＿ｄｅｆｓ．ｈｐｐ）を生成するものである。

図２６は、一実施形態による、図２４に例示した単純なアプリケーションのビットコードに対する解析ソフトウェアのパスに基づいて生成されるヘッダファイル例（ｍｙ＿ｄｅｆｓ．ｈｐｐ）を示す。図示のように、ヘッダファイルは、識別子「３」を有するメモリプールのためのバケット（ｂｕｃｋｅｔ＿ｃｆｇ２４）およびバケット記述子（ｂｕｃｋｅｔ＿ｄｅｓｃｒｉｐｔｏｒｓ）を含んでいる。注目すべきは、生成されたバケットが、アプリケーション例でリストによって使用されるリストノードに対して最適化されていることである。特に、バケットのブロックサイズは２４バイトであり、ブロックはリストで使用される２４バイトのリストノードと正確に整合するようになっている。言い換えれば、リストの各ノードは、バケットの１ブロックに正確に対応する。より複雑なアプリケーションでは、ヘッダファイルは、複数のメモリプールのための複数のバケットを含むことができることを理解されたい。この場合、バケット記述子は、単一のバケットではなく、複数のバケットを有するタプルを含んでもよく、タプルは、単一のメモリプールではなく、複数のメモリプールに対して定義されてもよい。

上記のようにヘッダファイルが生成されると、アプリケーションは、各メモリプールおよび各メモリプールによって使用される各バケットを最適に定義する、新たに生成されたヘッダファイルで再コンパイルすることが可能である。注目すべきは、これらの定義なしでアプリケーションを実行した場合、アプリケーションは依然として適切に実行されるが、上述の静的プールアロケータの実装により、上流のリソース（例えば、メモリヒープ）を利用することである。この定義を使ってアプリケーションを再コンパイルすると（つまり、ヘッダファイルを使って再コンパイルすると）、上流のリソースではなく、定義されたメモリプールを利用するようになる。言い換えれば、静的プールアロケータの実装の結果、アプリケーションは、デフォルトのメモリリソースからの割り当てとメモリプールからの割り当てとを、アプリケーション自体に何の変更も加えることなく、シームレスに切り替えることができる。

（２．８．実施形態の例）
有利なことに、本明細書で説明する実施形態は、安全性が重要なアプリケーションのための決定的メモリ割り当てを保証する。固定バケットサイズを有するメモリプールの使用は、決定的動作を保証することができるが、これらのメモリプールを適切に構成することは、例えば、Ｃ＋＋アロケータモデルのコンテキストにおいて、複雑である。したがって、実施形態は、カスタムアロケータにインスツルメントコードを注入し、次に、各割り当ての属性を抽出するために、コンパイル時にインスツルメントコードを検出する。これらの属性は、次に、メモリプールを最適に構成するヘッダファイルを生成するために使用することができる。これは、リアルタイムおよび／または安全性が重要なアプリケーションのための、証明可能で決定的メモリ割り当てソリューションを示すものである。

図２７は、一実施形態による、アプリケーションで使用されるメモリプールを最適化するための例示的な全体プロセス２００を示す。プロセス２００のサブプロセスの１つ以上、および可能的に全ては、最適化ツール（例えば、本明細書に説明する解析ソフトウェアを含むか、またはそれらからなる）の１つ以上のソフトウェアモジュールとして実装することができ、これは、コンパイラを含むかまたはそれと連動して動作することができる。最適化ツールは、１つ以上のシステム１００の１つ以上のプロセッサ１１０によって実行され、実行時の間アプリケーションによって使用される１つ以上のメモリプールを最適に定義するヘッダファイルをコンパイル時に生成することができる。

最初に、サブプロセス２１０において、アプリケーションのためのソースコードがビットコードにコンパイルされる。プロセス２００が効果的であるために、ソースコードは、各割り当ての間に、関連する引数を使用して、ダミー関数を呼び出すアロケータまたは他の割り当て関数を利用する必要がある。例えば、本明細書に説明した例である「ｔｙｐｅ＿ｒｅｇ（）」関数などのダミー関数を呼び出す、本明細書に説明した静的プールアロケータを、アロケータとして使用してもよい。ダミー関数への呼び出しで渡される関連引数は、アロケータがバインドされているメモリプールの識別子と、メモリプールからのメモリが割り当てられているデータ型の１つ以上の属性とを含むことができる。実施形態について、主にＣ＋＋のアロケータモデルに関して本明細書で説明してきたが、ダミー関数は、同一結果を達成するために、他のプログラミング言語によって使用される標準の割り当て関数とスキームとに同様に組み込むことができることを理解するべきである。

サブプロセス２２０において、ビットコードを分析する。特に、最適化ツールは、ビットコードをスキャンして、割り当て関数（例えば、カスタムＣ＋＋アロケータ）によるダミー関数への呼び出しを表すビットコードのセグメントを識別することができる。最適化ツールは、ビットコードの終わりに到達する（すなわち、サブプロセス２３０において「Ｙｅｓ」となる）まで、ビットコードをスキャンする。ビットコードの終わりにまだ到達していない（すなわち、サブプロセス２３０において「Ｎｏ」である）限り、最適化ツールは、ビットコードの現在のビューがダミー関数への呼び出しを表しているかどうかを判断する。例えば、最適化ツールは、ビットコードのスライドウィンドウを、ダミー関数への呼び出しを表す既知のビットコード断片と比較するか、または代替のパターンマッチングスキームを使用して、ビットコード内のダミー関数呼び出しの各インスタンスを特定することができる。

最適化ツールは、割り当て機能によるダミー関数への呼び出しを検出する（すなわち、サブプロセス２４０において「Ｙｅｓ」となる）たびに、その呼び出しから割り当て情報を抽出し、登録する。例えば、最適化ツールは、ダミー関数に渡されたパラメータを表すデータを抽出することができる。これらのパラメータは、メモリが割り当て関数によって割り当てられるメモリプールの識別子、メモリが割り当て関数によって割り当てられるデータ型のサイズ、および／またはメモリが割り当て関数によって割り当てられるデータ型の名称を開示することができる。これらのパラメータを、ビットコードから抽出し、ビットコードからソースコードに変換することができる。次に、変換したパラメータを割り当てのリスト内に割り当てとして格納してもよい。一実施形態では、一意な割り当てのみがリストに格納される。この場合、ある割り当てが既にリストに現れている場合、それをリスト内で重複させることなく、廃棄する可能性がある。あるいは、すべての割当てをリストに追加し、その後、重複する割当てを最終的なリストから削除してもよい。本明細書の他の箇所で説明したように、各割り当てについて呼び出しグラフを生成することもできる。ダミー関数への呼び出しがビットコードの現在のビューで検出されない（すなわち、サブプロセス２４０において「Ｎｏ」である）場合、最適化ツールはビットコードのスキャンを継続する。

一旦、ビットコード全体をスキャンし、一意な割り当ての完全なリストの生成（および任意選択として、割り当ての１つ以上（可能的にすべてを含む）の呼び出しグラフの生成）を完了する（すなわち、サブプロセス２３０において「Ｙｅｓ」となる）と、最適化ツールは、自動で（例えば、ユーザの関与なしに）または半自動で（例えば、いくつかのユーザの関与でもって）サブプロセス２６０においてヘッダファイルを生成することができ、それはサブプロセス２７０においてソースコードとともに再コンパイルされる。特に、ヘッダファイルは、サブプロセス２５０の１つ以上の反復において登録した一意な割当てのリストから生成することができる。本明細書の他の場所で論じたように、ヘッダファイルは、１つ以上のバケットの定義（例えば、ブロックサイズおよびブロック数の値）と１つ以上のメモリプールの定義（例えば、バケット定義への１つ以上の参照のタプル）とを含むことができる。

これらの定義は、割り当てのリスト内の特定の割り当てのために最適化することができる。例えば、最適化ツールは、特定のメモリプールのバケットのブロックサイズを、その特定のメモリプールからデータが割り当てられるデータ型のサイズと一致または他の方法で整合するように定義することができる。このようにして、１６バイト、３２バイト、および１０２４バイトという異なるサイズを有する３つの異なるデータ型がすべてメモリプールに関連付けられている場合、最適化ツールは、１６バイト、３２バイト、および１０２４バイトのブロックサイズを有するバケットを定義し、メモリプールがこれら３つのバケットのタプルを含むように定義することができる。あるいは、最適化ツールは、１６バイトと１０２４バイトとのブロックサイズを持つバケットを定義し、メモリプールがこれら２つのバケットを含むように定義することもできる。この場合、３２バイトのサイズを持つデータ型の各インスタンス化は、１６バイトのブロックサイズを持つバケット内の２つのブロックを利用することができる。いずれの場合も、各メモリプールのバケット内のブロックサイズは、そのメモリプールを使用するデータ型のサイズと整合する。

この方法で整合したバケットを作成するための多数の戦略があることを理解されたい。最適化ツールは、登録された割り当てからバケット構成を導出するための任意の１つ以上の戦略を利用するように構成することができる。直截的な戦略では、最適化ツールは、割り当てのリスト内の各一意なデータサイズに対するバケット（すなわち、データサイズに等しいブロックサイズを有するバケット）を生成し、次に、そのメモリプールに関連するデータサイズのすべてに一致するブロックサイズを有するバケットを含む各メモリプールを定義する。いずれの場合も、最適化ツールは、登録された割り当てにおけるデータ型のサイズに基づいてバケット定義を導出することができ、そのメモリプールで使用されるデータ型のサイズに基づいて各メモリプールを定義するバケット定義を選択することができる。二つのメモリプールが同一構成のバケットを利用する場合、最適化ツールは、バケットを一度定義し、その単一のバケット定義を両方のメモリプールの定義に利用できることを理解されたい。言い換えれば、バケット定義は、複数のメモリプールにまたがって再利用することができる。

（３．使用例）
開示された実施形態は、決定的メモリ割り当てが必要なまたは望ましい任意のソフトウェアアプリケーションにおいて決定的メモリ割り当てを提供するために利用することができる。最大の利点は、リアルタイムアプリケーション、特にリアルタイムで安全性が重要なアプリケーションにおいて見ることができる。そのようなアプリケーションには、限定されないが、自律または半自律車両、ロボット、重要なインフラストラクチャ（例えば、発電所、電力網、ネットワークなど）、ロケット、人工衛星、医療機器、および／または同種のものの制御および／または安全システムなどが含まれる。

開示された実施形態の上記説明は、当業者であれば誰でも本発明を製造または使用できるようにするために提供されたものである。これらの実施形態に対する様々な変更は、当業者には容易に明らかであり、本明細書に説明した一般原理は、本発明の精神または範囲から逸脱することなく他の実施形態に適用することが可能である。かくして、本明細書に提示した説明および図面は、本発明の現在好ましい実施形態を表し、それゆえ、本発明によって広く企図される主題の代表であることが理解されるであろう。さらに、本発明の範囲は当業者にとって明白となり得る他の実施形態を完全に包含するとともに、本発明の範囲は限定されないことが理解されよう。

本明細書において、「Ａ、Ｂ、またはＣの少なくとも１つ」、「Ａ、Ｂ、またはＣの１つ以上」、「Ａ、Ｂ、およびＣの少なくとも１つ」、「Ａ、Ｂ、およびＣの１つ以上」、「Ａ、Ｂ、Ｃ、またはそれらの任意の組み合わせ」等の組み合わせは、Ａ、Ｂ、および／またはＣの任意の組み合わせを含み、またＡの倍数、Ｂの倍数、またはＣの倍数のいずれを含んでもよい。具体的には、「Ａ、Ｂ、またはＣの少なくとも１つ」、「Ａ、Ｂ、またはＣの１つ以上」、「Ａ、Ｂ、およびＣの少なくとも１つ」、「Ａ、Ｂ、およびＣの１つ以上」、「Ａ、Ｂ、Ｃ、またはそれらの任意の組み合わせ」等の組み合わせは、Ａのみ、Ｂのみ、Ｃのみ、ＡかつＢ、ＡかつＣ、ＢかつＣ、またはＡかつＢかつＣであってよく、かかる任意の組み合わせにはその構成要素Ａ、Ｂ、および／またはＣの１つ以上が含まれてよい。例えば、ＡとＢとの組み合わせは、１つのＡと複数のＢ、複数のＡと１つのＢ、または複数のＡと複数のＢを含んでよい。

Claims (18)

1. 少なくとも１つのハードウェアプロセッサを使用することを含む方法であって、
   ビットコードにアプリケーションのソースコードをコンパイルするステップであって、前記ソースコードは、複数のパラメータを使用するダミー関数を呼び出すメモリを割り当てるための割り当て関数を含み、かつ前記複数のパラメータは、メモリプールの識別子と前記メモリプールに格納するデータ型のサイズとを含む、ビットコードにアプリケーションのソースコードをコンパイルするステップと、
   前記ビットコードをスキャンするステップと、
   前記ビットコードをスキャンしながら、前記ビットコード内の前記ダミー関数への各呼び出しを検出するステップと、
   前記ダミー関数への各呼び出しに対して、前記ダミー関数への前記検出された呼び出しで使用された前記複数のパラメータを抽出し、かつ前記抽出された複数のパラメータから、前記メモリプールの前記識別子と前記データ型の前記サイズとを含む割り当てレコードを生成するステップと、
   前記生成された割り当てレコードから割り当てレコードリストを生成するステップと、
   前記割り当てレコードリストに基づいてヘッダファイルを生成するステップであって、前記ヘッダファイルは、１つ以上のバケットの定義と、１つ以上のメモリプールの各定義とを含み、前記１つ以上のメモリプールの各定義は、前記１つ以上のバケットのうちの少なくとも１つを特定する、前記割り当てレコードリストに基づいてヘッダファイルを生成するステップと、
   前記ソースコードを前記ヘッダファイルで再コンパイルするステップと、を含む方法。
2. 前記１つ以上のバケットの各々の定義は、ブロック数とブロックサイズとを含む、請求項１に記載の方法。
3. 前記ヘッダファイルを生成するステップは、前記割り当てレコードリスト中の各一意なサイズに対して、その一意なサイズに整合するブロックサイズを含むバケットの少なくとも１つの定義を生成するステップを含む、請求項２に記載の方法。
4. 前記ヘッダファイルを生成するステップは、前記割り当てレコードリスト中の各一意な識別子に対して、その識別子を有するメモリプールの定義を生成するステップをさらに含む、請求項３に記載の方法。
5. メモリプールの各定義は、前記割り当てレコードリスト中のそのメモリプールの前記識別子に関連付けられている各一意なサイズに対して、ブロックサイズがそのサイズに整合する前記１つ以上のバケットのうちの１つの定義への参照を含む、請求項４に記載の方法。
6. そのサイズに整合するブロックサイズを含むバケットの少なくとも１つの定義を生成するステップは、そのサイズに一致するブロックサイズを含むバケットの定義を生成するステップを含む、請求項３に記載の方法。
7. 前記１つ以上のメモリプールの各々の前記定義はタプルを含み、前記タプルは１つ以上の参照を含み、かつ前記１つ以上の参照の各々は前記１つ以上のバケットの１つを特定する、請求項１に記載の方法。
8. 前記ビットコードにおいて、前記割り当て関数の各インスタンスは、前記割り当て関数が単一のメモリプール以外の任意のメモリプールから割り当てられないように、前記単一のメモリプールにバインドされている、請求項１に記載の方法。
9. 前記割り当て関数は、
   前記メモリプールが未定義である間、前記アプリケーションが利用可能な上流リソースからメモリを割り当て、
   前記メモリプールが定義されている間、前記メモリプールからメモリを割り当てるように構成されている、請求項１に記載の方法。
10. 前記ソースコードは、Ｃ＋＋プログラミング言語で記述されている、請求項１に記載の方法。
11. 前記割り当て関数は、前記Ｃ＋＋プログラミング言語のアロケータモデルに従ったカスタムアロケータである、請求項１０に記載の方法。
12. 前記少なくとも１つのハードウェアプロセッサを使用して、前記１つ以上の割り当ての各々に対して、前記アプリケーションのエントリポイントから前記割り当て関数への関数呼び出しのパスを表す呼び出しグラフを生成するステップをさらに含む、請求項１に記載の方法。
13. 前記複数のパラメータは、前記メモリプールに格納する前記データ型の識別子をさらに含む、請求項１に記載の方法。
14. その中に格納された命令を有する非一時的コンピュータ可読媒体であって、前記命令は、プロセッサによって実行されたとき、前記プロセッサに、
    ビットコードにアプリケーションのソースコードをコンパイルするステップであって、前記ソースコードは、複数のパラメータを使用するダミー関数を呼び出すメモリを割り当てるための割り当て関数を含み、かつ前記複数のパラメータは、メモリプールの識別子と前記メモリプールに格納するデータ型のサイズとを含む、ビットコードにアプリケーションのソースコードをコンパイルするステップと、
    前記ビットコードをスキャンするステップと、
    前記ビットコードをスキャンしながら、前記ビットコード内の前記ダミー関数への各呼び出しを検出するステップと、
    前記ダミー関数への各呼び出しに対して、前記ダミー関数への前記検出された呼び出しで使用された前記複数のパラメータを抽出し、かつ前記抽出された複数のパラメータから、前記メモリプールの前記識別子と前記データ型の前記サイズとを含む割り当てレコードを生成するステップと、
    前記生成された割り当てレコードから割り当てレコードリストを生成するステップと、
    前記割り当てレコードリストに基づいてヘッダファイルを生成するステップであって、前記ヘッダファイルは、１つ以上のバケットの定義と、１つ以上のメモリプールの各定義とを含み、前記１つ以上のメモリプールの各定義は、前記１つ以上のバケットのうちの少なくとも１つを特定する、前記割り当てレコードリストに基づいてヘッダファイルを生成するステップと、
    前記ソースコードを前記ヘッダファイルで再コンパイルするステップと、を行わせる、非一時的コンピュータ可読媒体。
15. 前記１つ以上のバケットの各々の前記定義は、ブロック数とブロックサイズとを含む、請求項１４に記載の非一時的コンピュータ可読媒体。
16. 前記ヘッダファイルを生成するステップは、
    前記割り当てレコードリスト中の各一意なサイズに対して、その一意なサイズに整合するブロックサイズを含むバケットの少なくとも１つの定義を生成するステップと、
    前記割り当てレコードリスト中の各一意な識別子に対して、その識別子を有するメモリプールの定義を生成するステップであって、メモリプールの各定義は、前記割り当てレコードリスト中のそのメモリプールの前記識別子に関連付けられている各一意なサイズに対して、ブロックサイズがそのサイズに整合する前記１つ以上のバケットのうちの１つの定義への参照を含む、その識別子を有するメモリプールの定義を生成するステップと、を含む請求項１５に記載の非一時的コンピュータ可読媒体。
17. 前記割り当て関数は、Ｃ＋＋プログラミング言語のアロケータモデルに従ったカスタムアロケータである、請求項１４に記載の非一時的コンピュータ可読媒体。
18. 少なくとも１つのハードウェアプロセッサと、
    １つ以上のソフトウェアモジュールであって、前記少なくとも１つのハードウェアプロセッサによって実行されるとき、
    ビットコードにアプリケーションのソースコードをコンパイルするステップであって、前記ソースコードは、複数のパラメータを使用するダミー関数を呼び出すメモリを割り当てるための割り当て関数を含み、前記複数のパラメータは、メモリプールの識別子と前記メモリプールに格納するデータ型のサイズとを含む、ビットコードにアプリケーションのソースコードをコンパイルするステップと、
    前記ビットコードをスキャンするステップと、
    前記ビットコードをスキャンしながら、前記ビットコード内の前記ダミー関数への各呼び出しを検出するステップと、
    前記ダミー関数への各呼び出しに対して、前記ダミー関数への前記検出された呼び出しで使用された前記複数のパラメータを抽出し、かつ前記抽出された複数のパラメータから、前記メモリプールの前記識別子と前記データ型の前記サイズとを含む割り当てレコードを生成するステップと、
    前記生成された割り当てレコードから割り当てレコードリストを生成するステップと、
    前記割り当てレコードリストに基づいてヘッダファイルを生成するステップであって、前記ヘッダファイルは、１つ以上のバケットの定義と、１つ以上のメモリプールの各定義とを含み、前記１つ以上のメモリプールの各定義は、前記１つ以上のバケットのうちの少なくとも１つを特定する、前記割り当てレコードリストに基づいてヘッダファイルを生成するステップと、
    前記ソースコードを前記ヘッダファイルで再コンパイルするステップと、を行うように構成されている１つ以上のソフトウェアモジュールと、を含むシステム。

Images