(57)【要約】本発明は、ロックレス・バッファリソース管理方式に関する。提案の方式においては、バッファプールは、割り当てリストおよび割り当て解除リストを有するように構成されている。割り当てリストは、前のバッファオブジェクトの中のネクストポインタによって次のバッファオブジェクトにリンクされた１つ以上のバッファオブジェクトと、割り当てリストの先頭のバッファオブジェクトを指し示すヘッドポインタとを有する。割り当て解除リストは、前のバッファオブジェクトの中の次のポインタによって次のバッファオブジェクトにリンクされた１つ以上のバッファオブジェクトと、割り当て解除リストの先頭のバッファオブジェクトを指し示すヘッドポインタと、割り当て解除リストの最後のバッファオブジェクトの次のポインタを指し示すテールポインタとを有し、このテールポインタは、ポインタのポインタである。
2015506027.tif 000002
【特許請求の範囲】
【請求項１】
バッファリソースの管理方法であって、割り当てリストと割り当て解除リストとを有するようにバッファプールが構成されており、
前記割り当てリストは、前のバッファオブジェクトにおいてネクストポインタによって次のバッファオブジェクトへとリンクされる１つ以上のバッファオブジェクトと、前記割り当てリストにおける先頭のバッファオブジェクトの次のバッファオブジェクトを指し示しているヘッドポインタとを有し、
前記割り当て解除リストは、前のバッファオブジェクトにおいてネクストポインタによって次のバッファオブジェクトへとリンクされる１つ以上のバッファオブジェクトと、前記割り当てリストにおける先頭のバッファオブジェクトの次のバッファオブジェクトを指し示しているヘッドポインタと、前記割り当てリストの最後に位置するバッファオブジェクトのネクストポインタを指し示しているテールポインタとを有し、前記テールポインタはポインタのポインタであり、
初期化の際に、前記割り当て解除リストの前記ヘッドポインタが空にされ、前記割り当て解除リストの前記テールポインタが前記割り当て解除リストの前記ヘッドポインタを指し示すようにされ、
前記バッファリソースの管理方法は、引き継ぎアクションとして、
前記割り当て解除リストの前記ヘッドポインタを前記割り当てリストの前記ヘッドポインタに割り当てるステップと、
前記割り当て解除リストの前記ヘッドポインタをクリーニングして空にするステップと、
前記割り当て解除リストの前記テールポインタを当該割り当て解除リストの前記ヘッドポインタを指し示すようにするステップと
を有することを特徴とするバッファリソースの管理方法。
【請求項２】
前記割り当てリストが空かどうかを判定するステップと、
前記割り当てリストが空である場合、前記割り当て解除リストが空であるかどうかを判定するステップと、
前記割り当て解除リストが空でない場合、前記引き継ぎアクションを実行するステップと
をさらに有することを特徴とする請求項１に記載のバッファリソースの管理方法。
【請求項３】
前記割り当てリストが空でない場合、前記割り当てリストにおける前記先頭のバッファオブジェクトをリンク解除するステップをさらに有することを特徴とする請求項２に記載のバッファリソースの管理方法。
【請求項４】
前記割り当て解除リストが空である場合、ヒープから複数のバッファオブジェクトを割り当て、当該複数のバッファオブジェクトを前記割り当てリストにリンクするステップをさらに有することを特徴とする請求項２に記載のバッファリソースの管理方法。
【請求項５】
リクラメーションアクションとして、
前記割り当て解除リストにおける前記最後に位置する前記バッファオブジェクトの前記ネクストポインタを、新しく解放されたバッファオブジェクトを指し示すようにするステップであって、前記割り当て解除リストの最後の前記ネクストポインタは前記割り当て解除リストの前記テールポインタによってアドレス指定されている、前記ステップと、
前記割り当て解除リストの前記テールポインタを前記新しく解放されたバッファオブジェクトのネクストポインタに移動させるステップと
をさらに有することを特徴とする請求項１ないし４のいずれか１項に記載のバッファリソースの管理方法。
【請求項６】
事後調整アクションとして、
前記新しく解放されたバッファオブジェクトが前記割り当て解除リスト内にリンクされた後で、前記割り当て解除リストの前記ヘッドポインタが空かどうかを判定するステップと、
前記割り当て解除リストの前記ヘッドポインタが空である場合、前記割り当て解除リストの前記テールポインタを前記割り当て解除リストの前記ヘッドポインタを指し示すようにするステップと
をさらに有することを特徴とする請求項５に記載のバッファリソースの管理方法。
【請求項７】
再リクラメーションアクションとして、
前記事後調整アクションの後で、前記割り当てリストの前記ヘッドポインタが空で、かつ、前記新しく解放されたバッファオブジェクトがまだ解放状態であるかどうかを判定するステップと、
前記割り当てリストの前記ヘッドポインタが空で、かつ、前記新しく解放されたバッファオブジェクトがまだ解放状態である場合、前記リクラメーションアクションを再度実行するステップと
をさらに有することを特徴とする請求項６に記載のバッファリソースの管理方法。
【請求項８】
前記引き継ぎアクションと前記リクラメーションアクションとはどの位置においても交互に配置可能であることを特徴とする請求項５ないし７のいずれか１項に記載のバッファリソースの管理方法。
【請求項９】
バッファリソースの管理方法であって、バッファプールが割り当てリストと割り当て解除リストとを有すように構成されており、
前記割り当てリストは、前のバッファオブジェクトにおいてネクストポインタによって次のバッファオブジェクトへとリンクされる１つ以上のバッファオブジェクトと、前記割り当てリストにおける先頭のバッファオブジェクトの次のバッファオブジェクトを指し示しているヘッドポインタとを有し、
前記割り当て解除リストは、前のバッファオブジェクトにおいてネクストポインタによって次のバッファオブジェクトへとリンクされる１つ以上のバッファオブジェクトと、前記割り当てリストにおける先頭のバッファオブジェクトの次のバッファオブジェクトを指し示しているヘッドポインタと、前記割り当てリストの最後に位置するバッファオブジェクトのネクストポインタを指し示しているテールポインタとを有し、前記テールポインタはポインタのポインタであり、
初期化の際に、前記割り当て解除リストの前記ヘッドポインタが空にされ、前記割り当て解除リストの前記テールポインタが前記割り当て解除リストの前記ヘッドポインタを指し示すようにされ、
前記バッファリソースの管理方法は、リクラメーションアクションとして、
前記割り当て解除リストにおける前記最後に位置する前記バッファオブジェクトの前記ネクストポインタを、新しく解放されたバッファオブジェクトを指し示すようにするステップであって、前記割り当て解除リストの最後の前記ネクストポインタは前記割り当て解除リストの前記テールポインタによってアドレス指定されている、前記ステップと、
前記割り当て解除リストの前記テールポインタを前記新しく解放されたバッファオブジェクトのネクストポインタに移動させるステップと
を有することを特徴とするバッファリソースの管理方法。
【請求項１０】
事後調整アクションとして、
前記新しく解放されたバッファオブジェクトが前記割り当て解除リスト内にリンクされた後で、前記割り当て解除リストの前記ヘッドポインタが空かどうかを判定するステップと、
前記割り当て解除リストの前記ヘッドポインタが空である場合、前記割り当て解除リストのテールポインタを前記割り当て解除リストのヘッドポインタを指し示すようにするステップと
をさらに有する
ことを特徴とする請求項９に記載のバッファリソースの管理方法。
【請求項１１】
再リクラメーションアクションとして、
前記事後調整アクションの後で、前記割り当てリストの前記ヘッドポインタが空で、かつ、前記新しく解放されたバッファオブジェクトがまだ解放状態であるかどうかを判定するステップと、
前記割り当てリストの前記ヘッドポインタが空で、かつ、前記新しく解放されたバッファオブジェクトがまだ解放状態である場合、前記リクラメーションアクションを再度実行するステップと
ことを特徴とする請求項１０に記載のバッファリソースの管理方法。
【請求項１２】
通信機器においてバッファリソース管理を実行させるコンピュータ可読命令であって、コンピューティングデバイスによって実行可能であり、請求項１ないし１１のいずれか１項に記載された前記バッファリソースの管理方法を実行させるコンピュータ可読命令を備えたコンピュータ可読記憶媒体。
【請求項１３】
割り当て解除リストを有するように構成されたバッファプールを備えた通信機器であって、
前記割り当て解除リストは、
前のバッファオブジェクト内のネクストポインタによって次のバッファオブジェクトへとリンクされた１つ以上のバッファオブジェクトと、
前記割り当て解除リストの先頭に位置するバッファオブジェクトを指し示すヘッドポインタと、
ポインタのポインタであるテールポインタであって、前記割り当て解除リストの最後に位置するバッファオブジェクトのネクストポインタを指し示すテールポインタと
を有することを特徴とする通信機器。
【請求項１４】
初期化の際に、前記割り当て解除リストの前記ヘッドポインタが空にされ、前記割り当て解除リストの前記テールポインタが前記割り当て解除リストの前記ヘッドポインタを指し示すようにされることを特徴とする請求項１３に記載の通信機器。
【請求項１５】
前記バッファプールはさらに割り当てリストを有するように構成されており、
前記割り当てリストは、
前のバッファオブジェクト内のネクストポインタによって次のバッファオブジェクトへとリンクされた１つ以上のバッファオブジェクトと、
前記割り当てリストの先頭に位置するバッファオブジェクトを指し示すヘッドポインタと
を有することを特徴とする請求項１３または１４に記載の通信機器。
【請求項１６】
引き継ぎアクションとして、
前記割り当て解除リストの前記ヘッドポインタを前記割り当てリストの前記ヘッドポインタに割り当てるステップと、
前記割り当て解除リストの前記ヘッドポインタをクリーニングして空にするステップと、
前記割り当て解除リストの前記テールポインタを当該割り当て解除リストの前記ヘッドポインタを指し示すようにするステップと
を実行するように構成されたプロセッサをさらに有することを特徴とする請求項１３ないし１５のいずれか１項に記載の通信機器。
【請求項１７】
前記プロセッサは、さらに、
前記割り当てリストが空かどうかを判定するステップと、
前記割り当てリストが空である場合、前記割り当て解除リストが空であるかどうかを判定するステップと、
前記割り当て解除リストが空でない場合、前記引き継ぎアクションを実行するステップとを実行するように構成されていることを特徴とする請求項１６に記載の通信機器。
【請求項１８】
前記プロセッサは、さらに、前記割り当てリストが空でない場合、前記割り当てリストにおける前記先頭のバッファオブジェクトをリンク解除するステップを実行するように構成されていることを特徴とする請求項１７に記載の通信機器。
【請求項１９】
前記プロセッサは、さらに、前記割り当て解除リストが空である場合、ヒープから複数のバッファオブジェクトを割り当て、当該複数のバッファオブジェクトを前記割り当てリストにリンクするステップを実行するように構成されていることを特徴とする請求項１７に記載の通信機器。
【請求項２０】
リクラメーションアクションとして、
前記割り当て解除リストの前記最後に位置する前記バッファオブジェクトの前記ネクストポインタを、新しく解放されたバッファオブジェクトを指し示すようにするステップであって、前記割り当て解除リストの最後の前記ネクストポインタは前記割り当て解除リストの前記テールポインタによってアドレス指定されている、前記ステップと、
前記割り当て解除リストの前記テールポインタを前記新しく解放されたバッファオブジェクトのネクストポインタに移動させるステップと
を実行するように構成されたプロセッサをさらに有することを特徴とする請求項１３ないし１５のいずれか１項に記載の通信機器。
【請求項２１】
前記プロセッサは、さらに、
事後調整アクションとして、
前記新しく解放されたバッファオブジェクトが前記割り当て解除リスト内にリンクされた後で、前記割り当て解除リストの前記ヘッドポインタが空かどうかを判定するステップと、
前記割り当て解除リストの前記ヘッドポインタが空である場合、前記割り当て解除リストの前記テールポインタを前記割り当て解除リストの前記ヘッドポインタを指し示すようにするステップとを実行するように構成されていることを特徴とする請求項２０に記載の通信機器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リソース管理のロックレス解決策に関し、特に、ロックレス・バッファリソース管理方式および同方式を使用する通信機器に関する。
【背景技術】
【０００２】
ＢＳ（基地局）および／またはスイッチなどの通信機器においては、常にそのバッファリソースを管理するニーズがある。例えば、ＬＴＥ（ロングタームエボリューション）のｅＮＢ（進化型ノードＢ）のＳ１インタフェースにおける着信／発信パケットは、エアインタフェースの着信／発信パケットとは対照的に、並列かつ非同期の手順である。たいてい２つの個別のタスクがあり、一方は、Ｓ１インタフェースのソケットを通じて送信または受信して、無線ＵＰ（ユーザプレーン）（ＰＤＣＰ／ＲＬＣ／ＭＡＣ）スタックにパケットを配信し、他方は、ＵＰスタックのパケットからスケジューリング情報に従ってＭＡＣ（媒体アクセス制御）ＰＤＵ（パケットデータユニット）を作成して、エアインタフェースで送信する。
【０００３】
図１は、ＬＴＥのｅＮＢにおける一例であるプロデューサおよびコンシューマモデルを示す。（Ｓ１インタフェースの）ソケットのタスクは、コンシューマであり、プールの中らバッファオブジェクトをＳ１インタフェースからの保持パケットに割り当てて、それをＵＰスタックに転送する。（エアインタフェースの）他方のタスクは、プロデューサであり、エアインタフェースを通じてＰＤＵを送信した後、バッファオブジェクトをリリース（解放）してプールに戻す。バッファオブジェクトは、２つのタスクの間を流れるパケットのコンテナであり、それ故、再利用のためにバッファプールでリサイクルされる。この場合、そのようなマルチスレッド実行環境において、バッファプールのデータの完全性をどのように保証するかというよくある課題が生じる。
【０００４】
プロデューサ−コンシューマモデルにおいてデータの完全性を保証するよくある方法は、ＬＯＣＫ（ロック）である。このロックは、複数のスレッドにバッファプールへの順次アクセスを強要して、データの完全性を確保する。
【０００５】
ロックメカニズムは、たいていＯＳ（オペレーティングシステム）によって提供され、ミューテックスやセマフォのように原子性を確実にすることができる。アロケーション（割り当て）であれデアロケーション（割り当て解除）であれ、任意のタスクがバッファプールにアクセスしたいときはいつも、まずロックを取得する必要が常にある。他のタスクがロックを所有している場合、現在のタスクは、その所有者がロックを解放するまで、その実行を保留しなければならない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ロックメカニズムは、不可避的に余分のタスクスイッチ（切り替え）を持ち込んでしまう。通常の場合は、全体の性能に大きな影響を与えない。しかし、際どいリアルタイム環境においては、タスク切り替えのオーバヘッドを無視することはできない。例えばＬＴＥのｅＮＢにおいては、ＴＴＩのスケジューリングは１ｍｓに過ぎないのに対して、１回のタスク切り替えには、約２０μｓかかり、タスクの中断から再開までの１巡には、少なくとも２回のタスク切り替え手順、すなわち４０μｓが必要であり、これは、特にトラヒック量が多い場合には、ＬＴＥのスケジューリング性能に顕著な影響を与える。
【０００７】
たいてい、ベースバンドのアプリケーションは、マルチコア・ハードウェア・プラットフォームで実行され、このプラットフォームは、複数のタスクの並列同時実行を促進して、高い性能を達成する。しかし、ロックメカニズムは、そのような並列モデルを妨害してしまう。ロックの本質は、データの完全性を確保するために、まさに順次実行を強要することにあるからである。ロックを所有する間隔が非常に短いとしても、順次実行は、マルチコア・プラットフォームで実行されているアプリケーションに大きな影響を与え、潜在的な性能のボトルネックになることがある。
【課題を解決するための手段】
【０００８】
上記の問題の少なくとも１つを解決するために、本発明においては、ロックレス・バッファリソース管理方式および同方式を使用する通信機器を提案する。
【０００９】
本発明の第１の態様によれば、バッファプールが割り当てリストおよび割り当て解除リストを有するように構成されているバッファリソース管理方法を提供する。割り当てリストは、前のバッファオブジェクトの中のネクスト（次の）ポインタによって次のバッファオブジェクトにリンクされた１つ以上のバッファオブジェクトと、割り当てリストの先頭のバッファオブジェクトを指し示すヘッド（先頭）ポインタとを有する。割り当て解除リストは、前のバッファオブジェクトの中の次のポインタによって次のバッファオブジェクトにリンクされた１つ以上のバッファオブジェクトと、割り当て解除リストの先頭のバッファオブジェクトを指し示す先頭ポインタと、割り当て解除リストの最後のバッファオブジェクトの次のポインタを指し示すテール（末尾）ポインタとを有し、この末尾ポインタは、ポインタのポインタである。初期化においては、割り当て解除リストの先頭ポインタはエンプティ（空）であり、割り当て解除リストの末尾ポインタは、割り当て解除リストの先頭ポインタ自体を指し示す。バッファリソース管理方法は、割り当てリストの先頭ポインタに割り当て解除リストの先頭ポインタの役割を割り当てる工程と、割り当て解除リストの先頭ポインタを空にクリアする工程と、割り当て解除リストの末尾ポインタに割り当て解除リストの先頭ポインタ自体を指示させる工程とである、テイクオーバーアクション（引き継ぎ行動）の工程を有していてもよい。
【００１０】
一実施形態においては、バッファリソース管理方法は、割り当てリストが空であるか否かを判定する工程と、割り当てリストが空である場合に、割り当て解除リストが空であるか否かを判定する工程と、割り当て解除リストが空でない場合に、引き継ぎ行動の工程を行う工程とをさらに有していてもよい。バッファリソース管理方法は、割り当てリストが空でない場合に、割り当てリストの先頭のバッファオブジェクトをリンク解除（切り離す）工程をさらに有していてもよい。バッファリソース管理方法は、割り当て解除リストが空である場合に、ヒープ（の中から複数のバッファオブジェクトを取り出す工程と、その複数のバッファオブジェクトを割り当てリストとリンクさせる工程とをさらに有していてもよい。
【００１１】
別の実施形態においては、バッファリソース管理方法は、割り当て解除リストの末尾ポインタによってアドレス指定される、割り当て解除リストの最後のバッファオブジェクトの次のポインタに、新しく解放されるバッファオブジェクトを指示させる工程と、割り当て解除リストの末尾ポインタを新しく解放されるバッファオブジェクトの次のポインタに移動させる工程とである、リクラメーションアクション（再利用行動）の工程をさらに有していてもよい。バッファリソース管理方法は、新しく解放されるバッファオブジェクトが割り当て解除リストの中にリンクされた後、割り当て解除リストの先頭ポインタが空であるか否かを判定する工程と、割り当て解除リストの先頭ポインタが空である場合に、割り当て解除リストの末尾ポインタに割り当て解除リストの先頭ポインタ自体を指示させる工程とである、ポスト・アジャストメント・アクション（事後調整行動）の工程をさらに有していてもよい。バッファリソース管理方法は、事後調整行動の後、割り当てリストの先頭ポインタが空であるか否か、および新しく解放されたバッファオブジェクトが依然として解放状態にあるか否かを判定する工程と、割り当てリストの先頭ポインタが空であり、かつ新しく解放されたバッファオブジェクトが依然として解放状態にある場合に、再利用行動の工程を再度行う工程とである、再リクラメーションアクション（再々利用行動）の工程をさらに有していてもよい。
【００１２】
一例として、引き継ぎ行動の工程と再利用行動の工程は、どの位置においても交互に配置することができる。
【００１３】
本発明の第２の態様によれば、バッファプールが割り当てリストおよび割り当て解除リストを有するように構成されているバッファリソース管理方法を提供する。割り当てリストは、前のバッファオブジェクトの中の次のポインタによって次のバッファオブジェクトにリンクされた１つ以上のバッファオブジェクトと、割り当てリストの先頭のバッファオブジェクトを指し示す先頭ポインタとを有する。割り当て解除リストは、前のバッファオブジェクトの中の次のポインタによって次のバッファオブジェクトにリンクされた１つ以上のバッファオブジェクトと、割り当て解除リストの先頭のバッファオブジェクトを指し示す先頭ポインタと、割り当て解除リストの最後のバッファオブジェクトの次のポインタを指し示す末尾ポインタとを有し、この末尾ポインタは、ポインタのポインタである。初期化においては、割り当て解除リストの先頭ポインタは空であり、割り当て解除リストの末尾ポインタは、割り当て解除リストの先頭ポインタ自体を指し示す。バッファリソース管理方法は、割り当て解除リストの末尾ポインタによってアドレス指定される、割り当て解除リストの最後のバッファオブジェクトの次のポインタに、新しく解放されるバッファオブジェクトを指示させる工程と、割り当て解除リストの末尾ポインタを新しく解放されるバッファオブジェクトの次のポインタに移動させる工程とである、再利用行動の工程を有していてもよい。
【００１４】
一実施形態においては、バッファリソース管理方法は、新しく解放されるバッファオブジェクトが割り当て解除リストの中にリンクされた後、割り当て解除リストの先頭ポインタが空であるか否かを判定する工程と、割り当て解除リストの先頭ポインタが空である場合に、割り当て解除リストの末尾ポインタに割り当て解除リストの先頭ポインタ自体を指示させる工程とである、事後調整行動の工程をさらに有していてもよい。バッファリソース管理方法は、事後調整行動の後、割り当てリストの先頭ポインタが空であるか否か、および新しく解放されたバッファオブジェクトが依然として解放状態にあるか否かを判定する工程と、割り当てリストの先頭ポインタが空であり、かつ新しく解放されたバッファオブジェクトが依然として解放状態にある場合に、再利用行動の工程を再度行う工程とである、再々利用行動の工程をさらに有していてもよい。
【００１５】
本発明の第３の態様によれば、本発明の第１および第２の態様のうちのいずれか１つによる方法を実行するために、コンピューティングデバイスで実行可能であり、通信機器におけるバッファリソース管理を促進する、コンピュータで読み取り可能な命令を有する、コンピュータで読み取り可能な記憶媒体を提供する。
【００１６】
本発明の第４の態様によれば、割り当て解除リストを有するように構成されているバッファプールを有する、通信機器を提供する。割り当て解除リストは、前のバッファオブジェクトの中の次のポインタによって次のバッファオブジェクトにリンクされた１つ以上のバッファオブジェクトと、割り当て解除リストの先頭のバッファオブジェクトを指し示す先頭ポインタと、割り当て解除リストの最後のバッファオブジェクトの次のポインタを指し示す末尾ポインタとを有し、この末尾ポインタは、ポインタのポインタである。
【００１７】
一実施形態の初期化においては、割り当て解除リストの先頭ポインタは空であり、割り当て解除リストの末尾ポインタは、割り当て解除リストの先頭ポインタ自体を指し示す。
【００１８】
別の実施形態においては、バッファプールは、割り当てリストを有するようにさらに構成されており、割り当てリストは、前のバッファオブジェクトの中の次のポインタによって次のバッファオブジェクトにリンクされた１つ以上のバッファオブジェクトと、割り当てリストの先頭のバッファオブジェクトを指し示す先頭ポインタとを有する。
【００１９】
さらに別の実施形態においては、通信機器は、割り当てリストの先頭ポインタに割り当て解除リストの先頭ポインタの役割を割り当てる工程と、割り当て解除リストの先頭ポインタを空にクリアする工程と、割り当て解除リストの末尾ポインタに割り当て解除リストの先頭ポインタ自体を指示させる工程とである、引き継ぎ行動の工程を実行するように構成されたプロセッサをさらに有していてもよい。
【００２０】
また別の実施形態においては、プロセッサは、割り当てリストが空であるか否かを判定する工程と、割り当てリストが空である場合に、割り当て解除リストが空であるか否かを判定する工程と、割り当て解除リストが空でない場合に、引き継ぎ行動の工程を行う工程とを実行するようにさらに構成されていてもよい。プロセッサは、割り当てリストが空でない場合に、割り当てリストの先頭のバッファオブジェクトを切り離す工程を実行するようにさらに構成されていてもよい。プロセッサは、割り当て解除リストが空である場合に、ヒープの中から複数のバッファオブジェクトを取り出す工程と、その複数のバッファオブジェクトを割り当てリストとリンクさせる工程とを実行するようにさらに構成されていてもよい。
【００２１】
もう１つの実施形態においては、プロセッサは、割り当て解除リストの末尾ポインタによってアドレス指定される、割り当て解除リストの最後のバッファオブジェクトの次のポインタに、新しく解放されるバッファオブジェクトを指示させる工程と、割り当て解除リストの末尾ポインタを新しく解放されるバッファオブジェクトの次のポインタに移動させる工程とである、再利用行動の工程を実行するようにさらに構成されていてもよい。
【００２２】
あるいは代わりに、通信機器は、割り当て解除リストの末尾ポインタによってアドレス指定される、割り当て解除リストの最後のバッファオブジェクトの次のポインタに、新しく解放されるバッファオブジェクトを指示させる工程と、割り当て解除リストの末尾ポインタを新しく解放されるバッファオブジェクトの次のポインタに移動させる工程とである、再利用行動の工程を実行するように構成されたプロセッサをさらに有していてもよい。
【００２３】
さらに、プロセッサは、新しく解放されるバッファオブジェクトが割り当て解除リストの中にリンクされた後、割り当て解除リストの先頭ポインタが空であるか否かを判定する工程と、割り当て解除リストの先頭ポインタが空である場合に、割り当て解除リストの末尾ポインタに割り当て解除リストの先頭ポインタ自体を指示させる工程とである、事後調整行動の工程を実行するようにさらに構成されていてもよい。プロセッサは、事後調整行動の後、割り当てリストの先頭ポインタが空であるか否か、および新しく解放されたバッファオブジェクトが依然として解放状態にあるか否かを判定する工程と、割り当てリストの先頭ポインタが空であり、かつ新しく解放されたバッファオブジェクトが依然として解放状態にある場合に、再利用行動の工程を再度行う工程とである、再々利用行動の工程を実行するようにさらに構成されていてもよい。
【００２４】
一例として、引き継ぎ行動の工程と再利用行動の工程は、どの位置においても交互に配置することができる。
【００２５】
別の例として、通信機器は、基地局（ＢＳ）、スイッチ、または進化型ノードＢ（ｅＮＢ）であってもよい。
【００２６】
本発明の上記および他の目的、特徴および利点は、添付の図面とともに、本発明の非限定の実施形態についての以下の詳細説明を読むことにより明らかになる。
【図面の簡単な説明】
【００２７】
【図１】１つのプロデューサかつ１つのコンシューマのモデルの概略図である。
【図２】それぞれのバッファオブジェクト、ヘッダ、およびテールを有する、一例である割り当てリストおよび一例である割り当て解除リスト（「フリーリスト」とも呼ばれる）を示す図である。
【図３】バッファオブジェクトを示す概略図である。
【図４】一例であるコンシューマタスクのフロー図である。
【図５】一例であるプロデューサタスクのフロー図である。
【図６】バッファ紛失検出を有する一例であるプロデューサタスクのフロー図である。
【発明を実施するための形態】
【００２８】
以下、本発明の実施形態について、図面に沿って説明する。以下の説明においては、幾つかの特定の実施形態を説明のためだけに使用している。それらの実施形態は、本発明に対する何らかの限定と理解されるものではなく、その例と理解されるものである。本発明の理解をあいまいにする恐れはあるが、従来の構造および構成については省略する。
【００２９】
従来技術によるロックメカニズムは、タスク切り替えの余分のオーバヘッドを持ち込み、並列実行を妨げるので、本発明の１つの目的は、要するに、ロックを除いても、依然としてデータの完全性を確保することにある。
【００３０】
最新のＯＳ理論は、ロックメカニズムがマルチタスク環境におけるリソースコンフリクトを解決する唯一の可能な方法であることを証明している。しかし、その理論は、まさに一般事例を対象としたものであるのに対して、特別な事例においては、ロックはもはや必要ないことがある。図１に示すプロデューサおよびコンシューマが関係する事例は、まさにそのような事例の１つであり、この事例は次の特徴を有する。
●２つの同時タスクのみ利用可能
２つを超えるタスクを有する一般事例とは対照的に、このプロデューサおよびコンシューマの事例は、ちょうど２つのタスクを有する。
●一方は読み出し、他方は書き込む
どのタスクも読み出しも書き込みもできる一般事例とは対照的に、このプロデューサはバッファプールに主に書き込み、一方コンシューマはバッファプールから主に読み出す。
【００３１】
タスクが２つだけあり、それぞれのタスクがバッファプールに対して異なる操作を行う場合、データ構造および処理手順を注意深く設計することによって、ロックを使用することなく、２つのタスクにバッファプールの異なる部分にアクセスさせることが可能である。
【００３２】
上記の目的を達成するためには、以下の設計原理の少なくとも１つに従ってもよい。
１．クリティカルデータ構造を異なるタスクに分離する。
【００３３】
ロックは使用しないが、データ構造を分離する方法は依然として使用してもよく、そうすることにより、データの完全性を広範囲にわたって確保することができる。
【００３４】
例えば、あるリンクリスト構造においては、リストの先頭は、２つのタスクが同時にアクセスするクリティカル変数になり、従ってその完全性を保証することは不可能である。しかし、個別のタスクに対して２つの個々のリストを採用する場合、コンフリクトの可能性は大幅に減少する。
【００３５】
しかし、時には、同時にアクセスがあることは依然として避けられない。従って、依然としてまた別の技術を導入する必要がある。
２．できるだけ少ない数の命令を用いて、それらのクリティカルデータ構造にアクセスする。
【００３６】
クリティカルデータ構造にアクセスするとき、ｉｆ−ｔｈｅｎ−ｅｌｓｅ方式がたいてい採用される。すなわち、最初に状態を確認し、その結果に応じてデータ構造を操作する。しかし、この方式は、より多くのＣＰＵ命令を占有して、データの完全性を確保することをさらに難しくする。コード命令が少なければ少ないほど、コンフリクトの可能性は小さくなる。そういうことから、データ構造および処理手順を注意深く設計することによって、クリティカルデータ構造の状態を確認することなく、同じ処理ロジックを採用するように最善を尽くした方がよい。
３．クリティカルデータ構造の１つへの同時アクセスが避けられないとき、異なるタスクからの操作が互いに矛盾しないようにしておく方がよい。
【００３７】
データ構造を注意深くどのように設計しようと、２つのタスクが同じデータ構造を操作することは常に生じる。ロック同期メカニズムがないと、データ構造に対する２つのタスクの実行シーケンスはランダムであり、その結果は、予測できなくなる。従って、異なるタスクからのコンフリクトする操作を避ける方がよい。ここで、一例の「矛盾しない(compatibility)」の意味は、読み出し−および−書き込み、または書き込み−および−書き込みが同じ結果を有することを意味しており、２つのタスクが同時にデータ構造にアクセスする場合でさえ、決定性の常に同じ結果を生じることができるということである。
４．状態確認を使用する必要があるとき、いったん真と確認されたら、状態が変わらないようにする方がよい。
【００３８】
一般的には、状態確認は、処理手順を注意深くどのように設計しようとも避けられない。状態確認は不可分操作ではないので、予期しないタスク切り替えが確認と対応する操作との間に起こることがある。タスクがその実行を再開後に、状態が変わっていることがあり、データを損なうことになる。そういうことから、ロックを使用しない場合、タスク切り替えが確認とそれに続く操作との間に実際に行われる場合でさえ、状態がいったん真または偽と確認されたら、状態自体を確実に変わらないようにした方がよい。
【００３９】
本発明の一実施形態においては、ロックレス・リソース・コンフリクト解決方法を提供する。この方法においては、バッファプールは、割り当てリストおよび割り当て解除リストを有するように構成されている。割り当てリストは、前のバッファオブジェクトの中のネクスト（次の）ポインタによって次のバッファオブジェクトにリンクされた１つ以上のバッファオブジェクトと、割り当てリストの先頭のバッファオブジェクトを指し示すヘッド（先頭）ポインタとを有する。割り当て解除リストは、前のバッファオブジェクトの中の次のポインタによって次のバッファオブジェクトにリンクされた１つ以上のバッファオブジェクトと、割り当て解除リストの先頭のバッファオブジェクトを指し示す先頭ポインタと、割り当て解除リストの最後のバッファオブジェクトの次のポインタを指し示すテール（末尾）ポインタとを有し、この末尾ポインタはポインタのポインタである。初期化においては、割り当て解除リストの先頭ポインタは空であり、割り当て解除リストの末尾ポインタは、割り当て解除リストの先頭ポインタ自体を指し示す。バッファリソース管理方法は、割り当てリストの先頭ポインタに割り当て解除リストの先頭ポインタの役割を割り当てる工程と、割り当て解除リストの先頭ポインタを空にクリアする工程と、割り当て解除リストの末尾ポインタに割り当て解除リストの先頭ポインタ自体を指示させる工程とである、テイクオーバアクション（引き継ぎ行動）の工程を有していてもよい。引き継ぎ行動の工程を実行する前に、バッファリソース管理方法は、割り当てリストが空でない場合に、割り当てリストの先頭でバッファオブジェクトを切り離して、コンシューマタスクに戻る工程と、あるいは、割り当て解除リストが空でない場合に、引き継ぎ行動の工程を実行することによって、割り当てリストが割り当て解除リストを引き継ぐ工程とを有していてもよい。割り当て解除リストが空である場合、複数のバッファオブジェクトがヒープの中から割り当てられ、割り当てリストにリンクされ、その後コンシューマタスクに戻る。バッファリソース管理方法は、（割り当て解除リストの末尾ポインタによってアドレス指定される）割り当て解除リストの最後のバッファオブジェクトの次のポインタに、新しく解放されるバッファオブジェクトを指示させる工程と、割り当て解除リストの末尾ポインタを新しく解放されるバッファオブジェクトの次のポインタに移動させる工程とである、リクラメーションアクションを（再利用行動）の工程をさらに有していてもよい。バッファリソース管理方法は、解放されるバッファオブジェクトが割り当て解除リストの最後にリンクされた後、割り当て解除リストの先頭ポインタが空になっている（引き継ぎが行われている）場合に、結果を引き継ぎと一致させ続けるために、割り当て解除リストの末尾ポインタに割り当て解除リストの先頭ポインタ自体を指示させる工程である、上記再利用に続くポスト・アジャストメント・アクション（事後調整行動）の工程をさらに有していてもよい。バッファリソース管理方法は、事後調整以降、割り当てリストの先頭ポインタが空になり（バッファオブジェクトがコンシューマに既に割り当てられた）、かつ新しく解放されたバッファオブジェクトが依然として解放状態にある場合に、バッファ紛失を避けるために、上記再利用行動の工程を再び行う工程である、上記事後調整に続く再リクラメーションアクション（再々利用行動）の工程をさらに有していてもよい。
【００４０】
上記の設計原理１に基づいて、バッファプールは、それぞれ割り当ておよび割り当て解除用の、２つの個別リストを有するように設計されている。詳細には、図２は、それぞれのバッファオブジェクト、ヘッダおよびテールを有する、これら２つの個別リスト（割り当てリスト、割り当て解除リスト（「フリーリスト」とも呼ばれる））を示す。
【００４１】
図２は、それぞれのバッファオブジェクト、ヘッダおよびテールを有する、一例である割り当てリストおよび一例である割り当て解除リスト（「フリーリスト」とも呼ばれる）を示す。図２を参照すると、グローバルポインタは、次のように記述される。
●ａｌｌｏｃ＿ｈｅａｄ：
割り当てリストを指し示す（バッファ＊）先頭ポインタ
○ポインタはＮＵＬＬに初期化される。
【００４２】
○ヒープ内の大容量メモリに言及している。
【００４３】
○引き継ぎ後は、割り当て解除リストの最初のバッファオブジェクトを指し示す。
●ｆｒｅｅ＿ｈｅａｄ：
割り当て解除リストを指し示す（バッファ＊）先頭ポインタ
○ポインタはＮＵＬＬに初期化される。
【００４４】
○割り当て解除リストの最初のバッファオブジェクトを指し示す。
【００４５】
○引き継ぎ後、ポインタは再びＮＵＬＬに再設定される。
●ｆｒｅｅ＿ｔａｉｌ：
割り当て解除リストの最後のバッファオブジェクトの次のポインタを指し示す（バッファ＊＊）末尾ポインタ
○ポインタは初期化においてｆｒｅｅ＿ｈｅａｄを指し示す。
【００４６】
○バッファオブジェクトが解放されるたびに、そのバッファオブジェクトは、ｆｒｅｅ＿ｔａｉｌによって指示されて割り当て解除リストの最後にリンクされ、ｆｒｅｅ＿ｔａｉｌは、解放されたバッファオブジェクトの次のポインタを指し示すように移動される。
【００４７】
○引き継ぎ後、ｆｒｅｅ＿ｔａｉｌは再びｆｒｅｅ＿ｈｅａｄを指し示すように再設定される。
【００４８】
本発明の幾つかの実施形態は、図２に示す割り当て解除リストおよび割り当てリストの少なくとも１つを有するように構成されていてもよいバッファプールを有する、通信機器を提供する。この通信機器は、基地局（ＢＳ）、スイッチまたは進化型ノードＢ（ｅＮＢ）であってもよい。詳細には、割り当て解除リストは、前のバッファオブジェクトの中の次のポインタによって次のバッファオブジェクトにリンクされた１つ以上のバッファオブジェクトと、割り当て解除リストの先頭のバッファオブジェクトを指し示す先頭ポインタ（ｆｒｅｅ＿ｈｅａｄ）と、割り当て解除リストの最後のバッファオブジェクトの次のポインタを指し示す末尾ポインタ（ｆｒｅｅ＿ｔａｉｌ）とを有し、この末尾ポインタは、ポインタのポインタである。割り当てリストは、前のバッファオブジェクトの中の次のポインタによって次のバッファオブジェクトにリンクされた１つ以上のバッファオブジェクトと、割り当てリストの先頭のバッファオブジェクトを指し示す先頭ポインタ（ａｌｌｏｃ＿ｈｅａｄ）とを有する。
【００４９】
図３は、バッファオブジェクトを示す概略図である。
【００５０】
図３を参照すると、１つのバッファオブジェクトは、以下のフィールドを有する。
●ｉｎＦｒｅｅＬｉｓｔ：バッファオブジェクトがプールの中にあるか否かを示すブール代数（真（TRUE）：空、偽（FALSE）：使用）
このフィールドは、次のルールに従って設定される。
【００５１】
○初期化において、フィールドは真に設定される。
【００５２】
○コンシューマタスクがプールの中からバッファを割り当てるとき、割り当てリストからリンク解除する（切り離す）前にフィールドを偽に設定した方がよい。
【００５３】
○プロデューサタスクがバッファをプールに解放するとき、割り当て解除リストに付加する前にフィールドを真に設定した方がよい。
【００５４】
○コンシューマタスクがバッファをプールに戻すとき、フィールドを真に設定する前にまずバッファを割り当てリストの最初に挿入した方がよい。
●コンテンツ［］：ｃｈａｒ型［］
例えば最大２，５００バイトの着信パケットを保持する。
●長さ
実際のバッファコンテンツの長さ。
●オフセット
アレイ内のコンテンツの開始オフセットであり、前置されるプロトコルヘッダ（ＰＤＣＰ）を保持する。
●次
続くバッファオブジェクトを指し示す次のポインタ。
●魔法数（マジックナンバー）
バッファの所有者を示す任意の隠しフィールドである。
【００５５】
このフィールドは、初期化によってプロデューサになっている。バッファオブジェクトは、通常プロデューサタスクによって解放されるからである。しかし、異なる処理を可能にするために、コンシューマタスクが未使用のバッファを解放してプールに戻すとき、コンシューマに修正されてもよい。
【００５６】
上記の設計原理２に基づいて、通常のｉｆ−ｔｈｅｎ−ｅｌｓｅコードモデルの代わりに、各タスクは、クリティカルリソースの先取りと片付け作業を遂行するための２つの命令のみを有する同じコードモデルをまさに使用する。こうすることにより、命令数を少なくしている。その結果、可能な命令シーケンスの組み合わせのセットを大幅に減少させ、全ての場合を列挙することを可能にして、アルゴリズムの正しさを保証している。
【００５７】
コンフリクトは、２つのタスクの交互実行によって生じるので、アルゴリズムは、可能なコードシーケンスの組み合わせを全て考慮する必要があり、全ての可能性を確実に列挙する必要がある。
【００５８】
１つのタスクがＭ−１個の命令を有して、可能な命令の交互配置位置がＭ個あり、他のタスクがその位置で交互配置されるＮ個の命令を有すると想定すると、全ての可能なコードシーケンスの組み合わせ数は次の通りである。
【００５９】
Ｓ（Ｎ，Ｍ）＝Ｓ（Ｎ−１，Ｍ）＋Ｓ（Ｎ−１，Ｍ−１）＋Ｓ（Ｎ−１，Ｍ−２）＋...＋Ｓ（Ｎ−１，１）
Ｎを１、２、３...から列挙すると、
Ｓ（１，Ｍ）＝Ｍ＝Ｏ（Ｍ）
Ｓ（２，Ｍ）＝Ｓ（１，Ｍ）＋Ｓ（１，Ｍ−１）＋Ｓ（１，Ｍ−２）＋...＋Ｓ（１，１）
＝Ｍ＋Ｍ−１＋Ｍ−２＋...＋１＝（Ｍ＋１）×Ｍ／２
＝Ｏ（Ｍ２）
Ｓ（３，Ｍ）＝Ｓ（２，Ｍ）＋Ｓ（２，Ｍ−１）＋Ｓ（２，Ｍ−２）＋...＋Ｓ（２，１）
＝（Ｍ＋１）×Ｍ／２＋（Ｍ）×（Ｍ−１）／２＋（Ｍ−１）×（Ｍ−２）／２＋...＋１
＝Ｏ（Ｍ３）
Ｓ（Ｎ，Ｍ）＝Ｏ（ＭＮ）
上式から、ＭおよびＮが大きい値である場合、コード組み合わせセットの数は膨大な値に達して、全ての可能性を網羅することは極端に難しくなる。まさにこの理由から、クリティカルコードシーケンスは、少ない命令数に限定されている。
【００６０】
この点に関しては後で詳述するように、クリティカルコードシーケンスを少ない命令数に減少させた場合でさえ、コンフリクトを生じる操作が、引き継ぎ手順中に依然として起こることがある。ここで、コンシューマタスクは、｛ｆｒｅｅ＿ｈｅａｄ＝ＮＵＬＬ；ｆｒｅｅ＿ｔａｉｌ＝＆ｆｒｅｅ＿ｈｅａｄ｝である２つのクリティカル命令のみを有するように設計されていて、３つの可能な交互配置位置があり、プロデューサタスクは、｛＊ｆｒｅｅ＿ｔａｉｌ＝ｐＮｏｄｅＤｅｌ；ｆｒｅｅ＿ｔａｉｌ＝＆（ｐＮｏｄｅＤｅｌ−＞ｎｅｘｔ）｝である２つのクリティカル命令のみを有するように設計されている。実際の状況においては、コンシューマタスクおよびプロデューサタスクのこれらの命令は、どの位置においても交互配置可能である。そういうことから、交互配置コード組み合わせセットの合計数は、Ｓ（Ｎ＝２，Ｍ＝３）＝Ｓ（１，３）＋Ｓ（１，２）＋Ｓ（１，１）＝３＋２＋１＝６である。
【００６１】
実際の実行においては、どのシナリオに相当するかは明確には誰にもわからないので（確認することができないからである。確認するとなると、余分の交互配置コード組み合わせセットを持ち込むことになる）、最終のコードシーケンスは、どのシナリオが起こるかにかかわらず、結果が常に正しいことを保証できる方がよい。上記の設計原理３に基づいて、上記の全てのシナリオにおいて矛盾しないように、行動を注意深く選択した方がよい。例えば、いったん引き継ぎが検出されると、事後調整中に、割り当て解除リストの末尾ポインタは、戻されて、割り当て解除リストの先頭ポインタを指し示す。末尾ポインタの上記の調整は、引き継ぎ手順と事後調整手順の間でだけ矛盾しないからであり、引き継ぎ行動と再利用行動がどのように互いに交互配置されるかにかかわらず常に正しい。
【００６２】
新しい手順がコンフリクトの可能性をより小さい範囲に減少させるように特別な設計を採用している場合でさえ、２つのタスクの交互実行によって引き起こされる副作用は、依然として避けられない。幸いにも、他のタスクのフットプリントを注意深くチェックすることによって、その副作用を完全に取り除くことができる。他のタスクがデータ構造に作用していることを見つけると、副作用を取り除くために、データ構造に特別な調整を行う必要がある。設計原理４に基づくと、他のタスクが作用しても、データ構造の確認状態は安泰である。割り当て解除リストの先頭ポインタがいったん空になると、コンシューマタスクはもはやそれに作用せず、プロデューサタスクが意図的にそれを変更するまで、常にいつまでも空のままになっているからである。プロデューサタスクが意図的にそれを変更するのは、もちろんプロデューサタスク自体とコンフリクトすることはない。その結果、事後調整の正しさを保証する。
【００６３】
上記の設計原理１〜４に基づいて、コンシューマタスクおよびプロデューサタスク用の動作記述および対応する疑似コードについて、次に示す。
割り当て
スレッドが、多重定義された新しい演算子を通じて、プールからバッファを割り当てるように要求すると、スレッドの役割に応じて別々の処理が行われる。
−コンシューマ
通常のシナリオである。リンクが空でない場合、割り当てリストの先頭からバッファオブジェクトを切り離すように常に試みる。リンクが空である場合は、割り当て解除リストが空でない場合に、プロデューサのスレッドから割り当て解除リストを引き継ぐように試み、割り当て解除リストが空である場合に、バッファプールを作成するためにヒープの中から大容量メモリを割り当てるように、独自の新しい機能を呼び出す。
−プロデューサ
それ自体のプロデューサプールの中からバッファを割り当てる（後で詳述する）。
コンシューマタスク
ｉｆ（割り当てリストが空である）
｛
ｉｆ（割り当て解除リストが空である）
｛
／／ヒープの中から取得
ヒープの中から１組のバッファを割り当て、それらを割り当てリストにリンクする
｝
ｅｌｓｅ
｛
／／引き継ぎ行動
ａｌｌｏｃ＿ｈｅａｄ＝ｆｒｅｅ＿ｈｅａｄ；
ｆｒｅｅ＿ｈｅａｄ＝ＮＵＬＬ；
ｆｒｅｅ＿ｔａｉｌ＝＆ｆｒｅｅ＿ｈｅａｄ；
｝
｝
／／バッファオブジェクトの割り当て
割り当てリストの先頭からバッファオブジェクトを切り離す
割り当て解除
割り当て手順と同様に、割り当て解除においても、次の２つのシナリオを区別する必要がある。
−プロデューサ
ｆｒｅｅ＿ｔａｉｌポインタによってのみ割り当て解除リストに作用する。２つのＣＰＵ命令で十分である。すなわち、バッファオブジェクトをｆｒｅｅ＿ｔａｉｌが指示する割り当て解除リストの最後にリンクさせる命令と、ｆｒｅｅ＿ｔａｉｌをこのバッファオブジェクトに移動させる命令とで十分である。割り当て解除シナリオが割り当てシナリオの引き継ぎ動作と同時に行われることがあるので、その後、データの完全性を保証するために特別な事後調整が依然として必要である（後で詳述する）。
−コンシューマ
プロデューサとの衝突を避けるために、コンシューマタスクからの割り当て解除手順は、割り当てリストの最初にバッファを挿入することで、割り当てリストに作用するだけである。
プロデューサタスク
ｉｆ｛（ｆｒｅｅ＿ｔａｉｌ＝＝＆ｆｒｅｅ＿ｈｅａｄ）
｛
／／引き継ぎとのコンフリクトを解決する
／／ｆｒｅｅ＿ｔａｉｌをフリーリストの最後に移動させる
ｗｈｉｌｅ（＊ｆｒｅｅ＿ｔａｉｌ  ！＝ＮＵＬＬ）
｛
ｆｒｅｅ＿ｔａｉｌ＝＆（＊ｆｒｅｅ＿ｔａｉｌ）−＞ｎｅｘｔ
｝
｝
／／バッファオブジェクトをフリーリストの最後にリンクする
＊ｆｒｅｅ＿ｔａｉｌ＝ｐＮｏｄｅＤｅｌ；
ｆｒｅｅ＿ｔａｉｌ＝＆（ｐＮｏｄｅＤｅｌ−＞ｎｅｘｔ）；
／／事後調整
ｉｆ（ｆｒｅｅ＿ｈｅａｄが空である場合）
｛
ｆｒｅｅ＿ｔａｉｌ＝＆ｆｒｅｅ＿ｈｅａｄ；
｝
これらに対応するものとして、図４は、一例であるコンシューマタスクのフロー図を示し、図５は、一例であるプロデューサタスクのフロー図を示す。
【００６４】
本発明の幾つかの実施形態においては、図２に示すバッファプールを有する通信機器は、上記のコンシューマタスクの１つ以上の工程および／または上記の手順タスクの１つ以上の工程を行うように構成されたプロセッサをさらに有していてもよい。
【００６５】
上述のように、割り当て解除は、引き継ぎ動作と同時に起こることがある。コード命令交互配置効果のせいで、ｆｒｅｅ＿ｔａｉｌが今解放されるバッファに移動されたときに、コンシューマタスクに引き継がれていることがあり、この場合、ｆｒｅｅ＿ｔａｉｌ点は正しくなくなり、末尾ポインタの正しさを維持するために、余分の調整が必要になることがある。
【００６６】
データの完全性を維持するために、事後調整が、ｆｒｅｅ＿ｈｅａｄを確認する割り当て解除手順に続いて常に行われる。ｆｒｅｅ＿ｈｅａｄが空である場合は、引き継ぎが本当に行われたことを意味しており（現在の割り当て解除は、ｆｒｅｅ＿ｈｅａｄを空にしたまま終わってはいけない）、ｆｒｅｅ＿ｔａｉｌをｆｒｅｅ＿ｈｅａｄに再設定する。これは、引き継ぎ行動と全く同じであるが、矛盾のない結果を生じる（設計原理３を参照）。
【００６７】
ｆｒｅｅ＿ｈｅａｄは、引き継ぎ行動によっていったん空に設定されると、もはや変わらない。それ故、上記の確認は信頼でき、事後調整において使用することができる。しかし、非空のｆｒｅｅ＿ｈｅａｄの確認は、非空のｆｒｅｅ＿ｈｅａｄが引き継ぎ行動によって空に再設定されうるので信頼できず、従って、事後調整においては使用されない。
【００６８】
事後調整は、引き継ぎと再利用との間のコンフリクトを解決することができるが、バッファ紛失の問題は依然として存在することがあり、次のように生じる。
●割り当てリストにバッファがなく、割り当て解除リストに１つだけバッファが残されている。
●割り当て解除において、割り当て解除リストの最後のオブジェクト（唯一のバッファオブジェクト）をｆｒｅｅ＿ｔａｉｌによって指示してもらい、その次のポインタへリンクしようと試みるまさにその前に、タスク切り替えが起こり、割り当て解除リストから唯一のバッファオブジェクトを引き継いでコンシューマタスクに割り当て、次いでａｌｌｏｃ＿ｈｅａｄは再びＮＵＬＬに設定される。
●プロデューサタスクは、何事も起こらなかったかのように、その実行を再開して続行する。この場合、プロデューサタスクは、依然として前のバッファオブジェクト（割り当てられている）を使用して、解放されるバッファをリンクする。解放されたバッファは、もはやどの既知のポインタからも参照されないので漏れる。
【００６９】
上記のバッファ紛失問題を解決するために、バッファ紛失検出手順が導入されてもよい。このために、割り当てリストがヒープの中から割り当てられた新しいバッファオブジェクトを有するか、それとも割り当て解除リストから引き継がれた再利用のバッファオブジェクトを有するかを示すために、追加のグローバル変数であるＮｅｗｆｒｏｍＨｅａｐ（ブール代数）も、本実施形態において定義される。
●ＮｅｗｆｒｏｍＨｅａｐ：
割り当てリストがヒープの中から割り当てられた新しいバッファオブジェクトを有するか、それとも割り当て解除リストから引き継がれた再利用のバッファオブジェクトを有するかを示す（ブール代数）。
【００７０】
○変数は、初期化において偽に設定される。
【００７１】
○ヒープの中から大容量メモリが割り当てられて、ａｌｌｏｃ＿ｈｅａｄによって参照されるたびに、変数は真に設定される。
【００７２】
○引き継ぎ後、変数は偽に再設定される。
【００７３】
以下の条件を確認することによって、上記のバッファ紛失状態の事例に狙いを定める。
●ｆｒｅｅ＿ｈｅａｄ＝＝ＮＵＬＬ
バッファ紛失の前提条件である引き継ぎが本当に起こっていることを意味している。
●ｉｎＦｒｅｅＬｉｓｔ＝＝ＴＲＵＥ（真）
バッファが割り当てられていないことを意味しており、紛失する可能性がある。
●（ａｌｌｏｃ＿ｈｅａｄ＝＝ＮＵＬＬ）｜｜（ＮｅｗｆｒｏｍＨｅａｐ）
割り当て解除リストから引き継がれた唯一のバッファオブジェクトが割り当てられており、バッファ紛失が生じていることを意味する。
【００７４】
上記の条件が満足される場合、バッファ紛失が生じ、再び再利用される必要がある。２回目の再利用は、割り当て解除リストが空になっているので、成功するであろう。引き継ぎ行動は再び起こることはなく、安全に割り当て解除リストにリンクされうる。
【００７５】
この関連で、プロデューサタスクの疑似コードは、次のように修正されてもよい。
プロデューサタスク
for(ｉｎｔ  ｉ＝０；  ｉ＜２；ｉ＋＋)
｛
ｉｆ（ｆｒｅｅ＿ｔａｉｌ＝＝＆ｆｒｅｅ＿ｈｅａｄ）
｛
／／引き継ぎとのコンフリクトを解決する
／／ｆｒｅｅ＿ｔａｉｌをフリーリストの最後に移動させる
ｗｈｉｌｅ（＊ｆｒｅｅ＿ｔａｉｌ  ！＝ＮＵＬＬ）
｛
ｆｒｅｅ＿ｔａｉｌ＝＆（＊ｆｒｅｅ＿ｔａｉｌ）−＞ｎｅｘｔ
｝
｝
／／バッファオブジェクトをフリーリストの最後にリンクする
＊ｆｒｅｅ＿ｔａｉｌ＝ｐＮｏｄｅＤｅｌ；
ｆｒｅｅ＿ｔａｉｌ＝＆（ｐＮｏｄｅＤｅｌ−＞ｎｅｘｔ）；
／／事後調整
ｉｆ（ｆｒｅｅ＿ｈｅａｄが空である）
｛
ｆｒｅｅ＿ｔａｉｌ＝＆ｆｒｅｅ＿ｈｅａｄ；
／／バッファ紛失検出
ｉｆ（（ｐＮｏｄｅＤｅｌ−＞ｉｎＦｒｅｅＬｉｓｔ＝＝ＴＲＵＥ）＆＆
（ａｌｌｏｃ＿ｈｅａｄ＝＝ＮＵＬＬ｜｜ＮｅｗｆｒｏｍＨｅａｐ））
｛
ｃｏｎｔｉｎｕｅ；
｝
｝
ｂｒｅａｋ；
｝
図６は、一例であるバッファ紛失検出を有するプロデューサタスクのフロー図を示す。
【００７６】
本発明の幾つかの実施形態における図２に示すバッファプールを有する通信機器は、バッファ紛失検出を有する上記のプロデューサタスクの１つ以上の工程を実行するように構成されたプロセッサをさらに有していてもよい。
【００７７】
提案のロックレス・バッファリソース管理方式は、リソースを解放するだけの１つのプロデューサと、リソースを割り当てるだけの１つのコンシューマとのシナリオに、たいてい適用される。場合によっては、プロデューサも、リソースを割り当てる必要があることもある。他方では、コンシューマタスクも、未使用のリソースを解放してバッファプールに戻す必要があることもある。
【００７８】
この状況において、プロデューサは、コンシューマとの衝突を避けるために、もう１つ個別のプール（他のタスクはこのプールにアクセスしないので、リンクされるリストは１つだけで十分である）からリソースを割り当ててもよい。プロデューサタスクのリソース割り当ての可能性はコンシューマタスクのようには高くないので、別のプールを管理するためのオーバヘッドは依然として受け入れ可能である。
【００７９】
コンシューマ側に関しては、コンシューマは、未使用のバッファオブジェクトを割り当てリストの最初に挿入することによって未使用リソースを解放してもよい。割り当てリストは、コンシューマタスク自体だけが作用するので、割り当てリストに衝突は少しももたらさない。
【００８０】
提案のロックレス・バッファリソース管理方式は、１ｍｓ期間当たり少なくとも６０μｓのタスク切り替えのオーバヘッドを減少することと、フルレート（ダウンリンク帯域幅８０Ｍｂｐｓおよびエアインタフェース帯域幅２０Ｍｂｐｓ）のユーザデータ量で、約１０％の性能の向上を達成することが証明されている。
【００８１】
本発明の他のアレンジメントには、方法実施形態の工程および動作を実行するソフトウェアプログラムを含む。これについては、まず概要を述べ、それから詳細に説明する。より具体的には、コンピュータプログラムプロダクトは、コンピュータプログラムロジックがその上に符号化されたコンピュータで読み取り可能な媒体を備えるような実施形態である。コンピュータプログラムロジックは、コンピュータデバイスで実行されるとき、上述のロックレス・バッファリソース管理方式を提供するための対応する動作を提供する。コンピュータプログラムロジックは、コンピュータシステムの少なくとも１つのプロセッサで実行されるとき、その少なくとも１つのプロセッサが、本発明の実施形態の動作（方法）を実行することを可能にする。本発明のそのようなアレンジメントは、光媒体（例えば、ＣＤ−ＲＯＭ）、ソフトディスクまたはハードディスクなどのコンピュータで読み取り可能な媒体上で提供されるか、またはそれらに符号化されたソフトウェア、コードおよび／または他のデータ構造；１つ以上のＲＯＭまたはＲＡＭまたはＰＲＯＭのチップ上のファームウェアまたはマイクロコードなどの他の手段；あるいは特定用途向け集積回路（ＡＳＩＣ）；あるいは１つ以上のモジュールの中のダウンロード可能なソフトウェアイメージおよび共有データベース等として典型的に提供される。ソフトウェア、ハードウェア、またはそのようなアレンジメントは、コンピュータデバイスの１つ以上のプロセッサが本発明の実施形態によって述べられる技術を行うことができるように、コンピュータデバイスに搭載されてもよい。例えば他のエンティティのデータ通信デバイスまたはコンピュータデバイスのグループなどと一緒に動作しているソフトウェアプロセスも、本発明のノードおよびホストを提供してもよい。本発明によるノードおよびホストも、複数のデータ通信デバイス上の複数のソフトウェアプロセス、または小さい特定のコンピュータのグループ上で実行される全てのソフトウェアプロセス、または単一のコンピュータ上で実行される全てのソフトウェアプロセスの間で分散されてもよい。
【００８２】
システムの態様のハードウェア実施とソフトウェア実施との間には、差異はほとんど残されていない。ハードウェアまたはソフトウェアの使用は、一般に（しかし、ある状況においては、ハードウェアにするかソフトウェアにするかの選択は重要なことがあるので、常にではない）、費用対効率のトレードオフを意味する設計の選択である。本明細書に記載のプロセスおよび／またはシステムおよび／または他の技術に影響を及ぼすことがある種々の媒介物があり（例えば、ハードウェア、ソフトウェアおよび／またはファームウェア）、好ましい媒介物は、プロセスおよび／またはシステムおよび／または他の技術が配備される状況とともに変わる。例えば、開発者が速度と精度が最重要であると判断する場合、開発者は、主にハードウェアおよび／またはファームウェア媒介物を選択してもよい。柔軟性が最重要である場合、開発者は、主にソフトウェア実施を選択してもよい。また別の代替として、開発者は、ハードウェア、ソフトウェアおよび／またはファームウェアの組み合わせを選択してもよい。
【００８３】
これまでの説明は、本発明の実施形態のみを挙げており、本発明を少しも限定する意図はない。従って、本発明の精神および原理内で行われる修正、置換、改善などのいずれも、本発明の範囲に包含されるものである。
＜略語集＞
ＢＳ  基地局(Base Station)
ｅＮＢ  進化型ノードＢ(evolved Node B)
ＬＴＥ  ロングタームエボリューション(Long Term Evolution)
ＭＡＣ  媒体アクセス制御(Media Access Control)
ＯＳ  オペレーティングシステム(Operating System)
ＰＤＣＰ  パケットデータ収束プロトコル(Packet Data Convergence Protocol)
ＰＤＵ  パケットデータユニット(Packet Data Unit)
ＲＬＣ  無線リンク制御(Radio Link Control)
ＴＴＩ  送信時間間隔(Transmission Time Interval)
ＵＰ  ユーザプレーン(User Plane)
【図４】
2015506027.tif 000003
【図５】
2015506027.tif 000004
【図６】
2015506027.tif 000005
【図１】
2015506027.tif 000006
【図２】
2015506027.tif 000007
【図３】
2015506027.tif 000008
【手続補正書】
【提出日】平成26年12月9日(2014.12.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
バッファリソースの管理方法であって、割り当てリストと割り当て解除リストとを有するようにバッファプールが構成されており、
前記割り当てリストは、前のバッファオブジェクトにおいてネクストポインタによって次のバッファオブジェクトへとリンクされる１つ以上のバッファオブジェクトと、前記割り当てリストにおける先頭のバッファオブジェクトを指し示しているヘッドポインタとを有し、
前記割り当て解除リストは、前のバッファオブジェクトにおいてネクストポインタによって次のバッファオブジェクトへとリンクされる１つ以上のバッファオブジェクトと、前記割り当て解除リストにおける先頭のバッファオブジェクトを指し示しているヘッドポインタと、前記割り当てリストの最後に位置するバッファオブジェクトのネクストポインタを指し示しているテールポインタとを有し、前記テールポインタはポインタのポインタであり、
初期化の際に、前記割り当て解除リストの前記ヘッドポインタが空にされ、前記割り当て解除リストの前記テールポインタが前記割り当て解除リストの前記ヘッドポインタを指し示すようにされ、
前記バッファリソースの管理方法は、引き継ぎアクションとして、
前記割り当て解除リストの前記ヘッドポインタを前記割り当てリストの前記ヘッドポインタに割り当てるステップと、
前記割り当て解除リストの前記ヘッドポインタをクリーニングして空にするステップと、
前記割り当て解除リストの前記テールポインタを当該割り当て解除リストの前記ヘッドポインタを指し示すようにするステップと
を有することを特徴とするバッファリソースの管理方法。
【請求項２】
前記割り当てリストが空かどうかを判定するステップと、
前記割り当てリストが空である場合、前記割り当て解除リストが空であるかどうかを判定するステップと、
前記割り当て解除リストが空でない場合、前記引き継ぎアクションを実行するステップと
をさらに有することを特徴とする請求項１に記載のバッファリソースの管理方法。
【請求項３】
前記割り当てリストが空でない場合、前記割り当てリストにおける前記先頭のバッファオブジェクトをリンク解除するステップをさらに有することを特徴とする請求項２に記載のバッファリソースの管理方法。
【請求項４】
前記割り当て解除リストが空である場合、ヒープから複数のバッファオブジェクトを割り当て、当該複数のバッファオブジェクトを前記割り当てリストにリンクするステップをさらに有することを特徴とする請求項２に記載のバッファリソースの管理方法。
【請求項５】
リクラメーションアクションとして、
前記割り当て解除リストにおける前記最後に位置する前記バッファオブジェクトの前記ネクストポインタを、新しく解放されたバッファオブジェクトを指し示すようにするステップであって、前記割り当て解除リストの最後の前記ネクストポインタは前記割り当て解除リストの前記テールポインタによってアドレス指定されている、前記ステップと、
前記割り当て解除リストの前記テールポインタを前記新しく解放されたバッファオブジェクトのネクストポインタに移動させるステップと
をさらに有することを特徴とする請求項１ないし４のいずれか１項に記載のバッファリソースの管理方法。
【請求項６】
事後調整アクションとして、
前記新しく解放されたバッファオブジェクトが前記割り当て解除リスト内にリンクされた後で、前記割り当て解除リストの前記ヘッドポインタが空かどうかを判定するステップと、
前記割り当て解除リストの前記ヘッドポインタが空である場合、前記割り当て解除リストの前記テールポインタを前記割り当て解除リストの前記ヘッドポインタを指し示すようにするステップと
をさらに有することを特徴とする請求項５に記載のバッファリソースの管理方法。
【請求項７】
再リクラメーションアクションとして、
前記事後調整アクションの後で、前記割り当てリストの前記ヘッドポインタが空で、かつ、前記新しく解放されたバッファオブジェクトがまだ解放状態であるかどうかを判定するステップと、
前記割り当てリストの前記ヘッドポインタが空で、かつ、前記新しく解放されたバッファオブジェクトがまだ解放状態である場合、前記リクラメーションアクションを再度実行するステップと
をさらに有することを特徴とする請求項６に記載のバッファリソースの管理方法。
【請求項８】
前記引き継ぎアクションと前記リクラメーションアクションとはどの位置においても交互に配置可能であることを特徴とする請求項５ないし７のいずれか１項に記載のバッファリソースの管理方法。
【請求項９】
バッファリソースの管理方法であって、バッファプールが割り当てリストと割り当て解除リストとを有すように構成されており、
前記割り当てリストは、前のバッファオブジェクトにおいてネクストポインタによって次のバッファオブジェクトへとリンクされる１つ以上のバッファオブジェクトと、前記割り当てリストにおける先頭のバッファオブジェクトを指し示しているヘッドポインタとを有し、
前記割り当て解除リストは、前のバッファオブジェクトにおいてネクストポインタによって次のバッファオブジェクトへとリンクされる１つ以上のバッファオブジェクトと、前記割り当て解除リストにおける先頭のバッファオブジェクトを指し示しているヘッドポインタと、前記割り当てリストの最後に位置するバッファオブジェクトのネクストポインタを指し示しているテールポインタとを有し、前記テールポインタはポインタのポインタであり、
初期化の際に、前記割り当て解除リストの前記ヘッドポインタが空にされ、前記割り当て解除リストの前記テールポインタが前記割り当て解除リストの前記ヘッドポインタを指し示すようにされ、
前記バッファリソースの管理方法は、リクラメーションアクションとして、
前記割り当て解除リストにおける前記最後に位置する前記バッファオブジェクトの前記ネクストポインタを、新しく解放されたバッファオブジェクトを指し示すようにするステップであって、前記割り当て解除リストの最後の前記ネクストポインタは前記割り当て解除リストの前記テールポインタによってアドレス指定されている、前記ステップと、
前記割り当て解除リストの前記テールポインタを前記新しく解放されたバッファオブジェクトのネクストポインタに移動させるステップと
を有することを特徴とするバッファリソースの管理方法。
【請求項１０】
事後調整アクションとして、
前記新しく解放されたバッファオブジェクトが前記割り当て解除リスト内にリンクされた後で、前記割り当て解除リストの前記ヘッドポインタが空かどうかを判定するステップと、
前記割り当て解除リストの前記ヘッドポインタが空である場合、前記割り当て解除リストのテールポインタを前記割り当て解除リストのヘッドポインタを指し示すようにするステップと
をさらに有する
ことを特徴とする請求項９に記載のバッファリソースの管理方法。
【請求項１１】
再リクラメーションアクションとして、
前記事後調整アクションの後で、前記割り当てリストの前記ヘッドポインタが空で、かつ、前記新しく解放されたバッファオブジェクトがまだ解放状態であるかどうかを判定するステップと、
前記割り当てリストの前記ヘッドポインタが空で、かつ、前記新しく解放されたバッファオブジェクトがまだ解放状態である場合、前記リクラメーションアクションを再度実行するステップと
ことを特徴とする請求項１０に記載のバッファリソースの管理方法。
【請求項１２】
通信機器においてバッファリソース管理を実行させるコンピュータ可読命令であって、コンピューティングデバイスによって実行可能であり、請求項１ないし１１のいずれか１項に記載された前記バッファリソースの管理方法を実行させるコンピュータ可読命令を備えたコンピュータ可読記憶媒体。
【請求項１３】
割り当て解除リストを有するように構成されたバッファプールを備えた通信機器であって、
前記割り当て解除リストは、
前のバッファオブジェクト内のネクストポインタによって次のバッファオブジェクトへとリンクされた１つ以上のバッファオブジェクトと、
前記割り当て解除リストの先頭に位置するバッファオブジェクトを指し示すヘッドポインタと、
ポインタのポインタであるテールポインタであって、前記割り当て解除リストの最後に位置するバッファオブジェクトのネクストポインタを指し示すテールポインタと
を有することを特徴とする通信機器。
【請求項１４】
初期化の際に、前記割り当て解除リストの前記ヘッドポインタが空にされ、前記割り当て解除リストの前記テールポインタが前記割り当て解除リストの前記ヘッドポインタを指し示すようにされることを特徴とする請求項１３に記載の通信機器。
【請求項１５】
前記バッファプールはさらに割り当てリストを有するように構成されており、
前記割り当てリストは、
前のバッファオブジェクト内のネクストポインタによって次のバッファオブジェクトへとリンクされた１つ以上のバッファオブジェクトと、
前記割り当てリストの先頭に位置するバッファオブジェクトを指し示すヘッドポインタと
を有することを特徴とする請求項１３または１４に記載の通信機器。
【請求項１６】
引き継ぎアクションとして、
前記割り当て解除リストの前記ヘッドポインタを前記割り当てリストの前記ヘッドポインタに割り当てるステップと、
前記割り当て解除リストの前記ヘッドポインタをクリーニングして空にするステップと、
前記割り当て解除リストの前記テールポインタを当該割り当て解除リストの前記ヘッドポインタを指し示すようにするステップと
を実行するように構成されたプロセッサをさらに有することを特徴とする請求項１３ないし１５のいずれか１項に記載の通信機器。
【請求項１７】
前記プロセッサは、さらに、
前記割り当てリストが空かどうかを判定するステップと、
前記割り当てリストが空である場合、前記割り当て解除リストが空であるかどうかを判定するステップと、
前記割り当て解除リストが空でない場合、前記引き継ぎアクションを実行するステップとを実行するように構成されていることを特徴とする請求項１６に記載の通信機器。
【請求項１８】
前記プロセッサは、さらに、前記割り当てリストが空でない場合、前記割り当てリストにおける前記先頭のバッファオブジェクトをリンク解除するステップを実行するように構成されていることを特徴とする請求項１７に記載の通信機器。
【請求項１９】
前記プロセッサは、さらに、前記割り当て解除リストが空である場合、ヒープから複数のバッファオブジェクトを割り当て、当該複数のバッファオブジェクトを前記割り当てリストにリンクするステップを実行するように構成されていることを特徴とする請求項１７に記載の通信機器。
【請求項２０】
リクラメーションアクションとして、
前記割り当て解除リストの前記最後に位置する前記バッファオブジェクトの前記ネクストポインタを、新しく解放されたバッファオブジェクトを指し示すようにするステップであって、前記割り当て解除リストの最後の前記ネクストポインタは前記割り当て解除リストの前記テールポインタによってアドレス指定されている、前記ステップと、
前記割り当て解除リストの前記テールポインタを前記新しく解放されたバッファオブジェクトのネクストポインタに移動させるステップと
を実行するように構成されたプロセッサをさらに有することを特徴とする請求項１３ないし１５のいずれか１項に記載の通信機器。
【請求項２１】
前記プロセッサは、さらに、
事後調整アクションとして、
前記新しく解放されたバッファオブジェクトが前記割り当て解除リスト内にリンクされた後で、前記割り当て解除リストの前記ヘッドポインタが空かどうかを判定するステップと、
前記割り当て解除リストの前記ヘッドポインタが空である場合、前記割り当て解除リストの前記テールポインタを前記割り当て解除リストの前記ヘッドポインタを指し示すようにするステップとを実行するように構成されていることを特徴とする請求項２０に記載の通信機器。
【国際調査報告】
2015506027.tif 000009
2015506027.tif 000010
2015506027.tif 000011