(57)【要約】【課題】  データ記憶にかかる処理遅延をもたらすことなく，メモリ空間の利用効率を上げ，少ないメモリ容量でも多くのデータを蓄積することが可能となる。【解決手段】  本発明の，メモリ１１０へのデータの記憶または読み出しを管理するメモリ管理装置１００は，メモリに記憶されるデータのセル長を計数するセル長計数部１２２と，メモリの各セルに対応付けられセルの記憶状態を示す空き情報に基づいて，セル長以上連続して空いており，かつ，隣接するセルが占有されている空きセル群を検出する空きセル群検出部１２４と，検出された空きセル群にデータを記憶するデータ記憶部１２６と，データが記憶された各セルの空き情報を更新する空き情報更新部１２８とを備えることを特徴とする。【選択図】    図１
2007241465.tif 000002
【特許請求の範囲】
【請求項１】
固定長の記憶領域からなるセル単位で，メモリへのデータの記憶または読み出しを管理するメモリ管理装置であって：
前記メモリに記憶されるデータのセル長を計数するセル長計数部と；
前記メモリの各セルに対応付けられセルの記憶状態を示す空き情報に基づいて，前記セル長以上連続して空いており，かつ，隣接するセルが占有されている空きセル群を検出する空きセル群検出部と；
前記検出された空きセル群に前記データを記憶するデータ記憶部と；
前記データが記憶された各セルの空き情報を更新する空き情報更新部と；
を備えることを特徴とする，メモリ管理装置。
【請求項２】
前記空きセル群検出部は，隣接するセル同士の空き情報の排他的論理和をとり，その値と各空き情報との論理積をとった結果に基づいて前記空きセル群を検出することを特徴とする，請求項１に記載のメモリ管理装置。
【請求項３】
前記データの記憶または読み出しは，前記セル単位に加えて，複数のセルによって定義されるユニット単位でも行われることを特徴とする，請求項１に記載のメモリ管理装置。
【請求項４】
前記ユニットは，２のべき乗個のセルから構成され，
前記空きセル群検出部は，前記セルまたはユニットのいずれかの単位で空きセル群を検出することを特徴とする，請求項３に記載のメモリ管理装置。
【請求項５】
前記空きセル群検出部は，ユニットに含まれる全てのセルの空き情報の論理積をとり，隣接するユニット同士の該論理積値の排他的論理和をとり，その値と各空き情報との論理積をとった結果に基づいて空きセル群を検出することを特徴とする，請求項４に記載のメモリ管理装置。
【請求項６】
前記ユニットに含まれる全てのセルの空き情報の論理積は，隣接するセル同士の論理積にさらに順次論理積をとり，各出力をカスケード接続して形成されることを特徴とする，請求項５に記載のメモリ管理装置。
【請求項７】
前記ユニットは，さらに各２のべき乗×１．５個のセルから構成されることを特徴とする，請求項４に記載のメモリ管理装置。
【請求項８】
前記２のべき乗×１．５個のセルから構成されるユニットに含まれる全てのセルの空き情報の論理積は，隣接するセル同士の論理積にさらに順次論理積をとり，段数が異なる任意の論理積の出力同士の論理積から形成されることを特徴とする，請求項７に記載のメモリ管理装置。
【請求項９】
任意のセル群からデータを削除するデータ削除部をさらに備え，
前記空き情報更新部は，データが削除されたセルの空き情報も更新することを特徴とする，請求項１に記載のメモリ管理装置。
【請求項１０】
固定長の記憶領域からなるセル単位で，メモリへのデータの記憶または読み出しを管理するメモリ管理方法であって：
前記メモリに記憶されるデータのセル長を計数するセル長計数ステップと；
前記メモリの各セルに対応付けられセルの記憶状態を示す空き情報に基づいて，前記セル長以上連続して空いており，かつ，隣接するセルが占有されている空きセル群を検出する空きセル群検出ステップと；
前記検出された空きセル群に前記データを記憶するデータ記憶ステップと；
前記データが記憶された各セルの空き情報を更新する空き情報更新ステップと；
を含むことを特徴とする，メモリ管理方法。
【請求項１１】
前記セル群検出ステップは，セル，および２のべき乗個もしくは２のべき乗×１．５個のセルから構成されるユニットのいずれかの単位で空きセル群を検出することを特徴とする，請求項１０に記載のメモリ管理方法。
【請求項１２】
前記セル群検出ステップは，該当する空きセル群が検出されなかった場合，検出した単位よりセル長が長いユニット単位で再度検出し直すことを特徴とする，請求項１１に記載のメモリ管理方法。
【請求項１３】
メモリに対して，送受信されるデータを固定長の記憶領域からなるセル単位で記憶または読み出しする通信装置であって：
前記メモリに記憶されるデータのセル長を計数するセル長計数部と；
前記メモリの各セルに対応付けられセルの記憶状態を示す空き情報に基づいて，前記セル長以上連続して空いており，かつ，隣接するセルが占有されている空きセル群を検出する空きセル群検出部と；
前記検出された空きセル群に前記データを記憶するデータ記憶部と；
前記データが記憶された各セルの空き情報を更新する空き情報更新部と；
を備えることを特徴とする，通信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，メモリへのデータの記憶または読み出しを行うメモリ管理装置，メモリ管理方法，通信装置に関する。
【背景技術】
【０００２】
従来からある蓄積交換型の通信システムにおいては，データをパケット等の伝送単位にアセンブルし，そのパケットによって通信装置（通信局）間のデータの交換が行われていた。このようなデータのアクセス制御において，アクセス制御部は，上位レイヤから送信すべきデータを受け取ると，一旦，アクセス制御部内のメモリ（バッファ）にデータを蓄積し，伝送メディアの状況に応じてこのメモリからデータを取り出し，送信パケットを生成，送信していた。
【０００３】
このように送信されたパケットは受信側の通信装置で正しく複合されるとは限らない。従って，アクセス制御部は，受信側の通信装置から受信確認の応答があるまで，上記メモリ内のデータを消去することなく保持し，必要に応じて再送するなどの処理を行っていた。
【０００４】
このようなデータの蓄積交換処理を行うために，アクセス制御部は，メモリのどの部分にデータが記憶されているかといったメモリ空間の管理を行わなければならない。メモリ空間の管理を行うシステムとしては，コンピュータにおけるファイルシステムが考えられる。このファイルシステムとしては，例えば，ＦＡＴ（Ｆｉｌｅ  Ａｌｌｏｃａｔｉｏｎ  Ｔａｂｌｅ）型ファイルシステムが挙げられる。かかるＦＡＴ型ファイルシステムでは，クラスタと呼ばれる固定長単位でメモリ空間の管理が行われ，通常は，一つのデータを一つのクラスタに記憶（格納）する。
【０００５】
また，複数のデータを束ねて１つのファイルに記憶し，新たなデータを書き込む際には，データで埋まっているファイルではなく空き領域を有するファイルを検出し，そこにデータを記憶する技術が知られている（例えば，特許文献１）。
【０００６】
また，メモリ空間の他の管理方法として，記憶領域をリングバッファ状に形成し，データの入出力をＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）で行う方法も知られている。かかるＦＩＦＯによる処理では，データの入出力の度に記憶ポインタもしくは読み出しポインタを更新し，メモリの使用領域および未使用領域を容易に把握することができる。
【０００７】
【特許文献１】特開２００３−０８５０１０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら，上記蓄積交換型の通信システムにおいて交換されるデータは，様々なアプリケーションにより生成されるので，送信されるパケットは，数十バイト程度の小さなものから数千バイト程度の大きなものまで様々な大きさで形成される。従って，上記ＦＡＴ型ファイルシステムのように数千バイトを許容するクラスタに数十バイトの小さなデータのみが記憶されると，メモリ空間に無駄な記憶領域ができてしまい，そのような記憶領域は利用されないままデッドスペースとなっていた。
【０００９】
また，空き領域を有するファイルにデータを記憶する技術においても，上記クラスタに対応するエントリー領域のみでメモリ空間が管理されているので，上記同様，記憶すべきデータ長が短い場合に無駄な記憶領域ができてしまう。
【００１０】
また，蓄積交換型の通信システムにおいては，即時性が求められるパケットと，あまり即時性が求められないパケットとが混在し，アクセス制御部は，即時性の求められるパケットを検出すると優先的に送信しなければならない。従って，上述したリングバッファによるＦＩＦＯでは，任意アドレスのデータを抽出するパケット処理に対応できない。
【００１１】
また，データの蓄積という観点から，アクセス制御部において大容量のメモリが必要とされる。しかし，単にメモリの容量を大きくするだけでは，ハードウェアの大型化，高コスト化，高消費電力化を招くこととなる。従って，小容量のメモリで如何にして要求に見合ったメモリ管理を行うかが注目される。また，このような処理を実行できたとしても，それに伴って多くの処理遅延が生じると，情報の転送に時間がかかったり，処理中にデータがオーバーフローしたりするなどの新たな問題が発生する。従って，このメモリ管理処理は短期間で行う必要がある。
【００１２】
本発明は，従来のメモリの管理方法が有する上記問題点に鑑みてなされたものであり，本発明の目的は，データ記憶にかかる処理遅延をもたらすことなく，メモリ空間の利用効率を上げ，少ないメモリ容量でも多くのデータを蓄積することが可能な，新規かつ改良されたメモリ管理装置，メモリ管理方法，通信装置を提供することである。
【課題を解決するための手段】
【００１３】
上記課題を解決するために，本発明のある観点によれば，固定長の記憶領域からなるセル単位で，メモリへのデータの記憶または読み出しを管理するメモリ管理装置であって：上記メモリに記憶されるデータのセル長を計数するセル長計数部と；上記メモリの各セルに対応付けられセルの記憶状態を示す空き情報に基づいて，上記セル長以上連続して空いており，かつ，隣接するセルが占有されている空きセル群を検出する空きセル群検出部と；上記検出された空きセル群に上記データを記憶するデータ記憶部と；上記データが記憶された各セルの空き情報を更新する空き情報更新部と；を備えることを特徴とする，メモリ管理装置が提供される。
【００１４】
本発明では，メモリへのデータの記憶時において，特定のセル長以上連続して空いており，かつ，隣接するセルが占有されている空きセル群を検出する。即ち，空きセル群検出部は，隣接するセルにデータが記憶されている空きセル群を敢えて選択し，記憶すべきデータが辛うじて入るそのような断片化された空間にデータを記憶する。こうして，メモリ空間上における記憶領域の連続性を高めることができ，充填率，利用効率を上げることが可能となる。
【００１５】
上記空きセル群検出部は，隣接するセル同士の空き情報の排他的論理和をとり，その値と各空き情報との論理積をとった結果に基づいて上記空きセル群を検出するとしてもよい。
【００１６】
空きセル群検出部は，かかる簡単な論理計算の結果により，隣接する２つのセルの少なくとも一方が，自己のセルは空いているが，隣接しているセルは占有されているセルであることを容易に把握することができる。従って，データの記憶にかかる処理遅延をもたらすことなく，メモリ空間の利用効率を上げることが可能となる。
【００１７】
上記データの記憶または読み出しは，上記セル単位に加えて，複数のセルによって定義されるユニット単位でも行われるとしてもよい。
【００１８】
複数のセルからなるユニットを定義することにより，メモリ管理装置は，記憶すべきデータの長さに応じてセルもしくはユニットを選択し，その単位でメモリ空間を管理することができる。このように各記憶すべきデータには，データの大きさに応じた適切な記憶領域と配置が割り当てられるので，メモリ空間の利用効率をさらに上げることが可能となる。
【００１９】
上記ユニットは，２のべき乗個のセルから構成され，上記空きセル群検出部は，上記セルまたはユニットのいずれかの単位で空きセル群を検出するとしてもよい。ユニットの構成を２のべき乗個に制限することで，メモリ空間の管理処理を容易にすることができる。
【００２０】
上記空きセル群検出部は，ユニットに含まれる全てのセルの空き情報の論理積をとり，隣接するユニット同士の該論理積値の排他的論理和をとり，その値と各空き情報との論理積をとった結果に基づいて空きセル群を検出するとしてもよい。
【００２１】
ここでは上述したセルの論理計算をユニットにも適用している。かかる論理計算によると，２つの隣接するユニットのうち少なくとも一方が，自己のユニットは空いているが隣接しているユニットは占有されているユニットであることを容易に把握することができる。
【００２２】
上記ユニットに含まれる全てのセルの空き情報の論理積は，隣接するセル同士の論理積にさらに順次論理積をとり，各出力をカスケード接続して形成されるとしてもよい。
【００２３】
ユニットが２のべき乗個のセルから構成されるとき，隣接するセル同士の論理積は，この２つのセルをユニットとした場合のユニットの空き情報となる。従って，順次論理積をとることにより，２，４，８，…といったセルからなるユニットの空き情報を生成することができる。
【００２４】
上記ユニットは，さらに各２のべき乗×１．５個のセルから構成されるとしてもよい。２のべき乗のほぼ中間にあたる２のべき乗×１．５個のセルでもユニットを構成すると，２のべき乗のみのユニットと比較してより高い分解能でメモリ空間を管理することができ，より効率的なメモリ空間を築くことが可能となる。
【００２５】
上記２のべき乗×１．５個のセルから構成されるユニットに含まれる全てのセルの空き情報の論理積は，隣接するセル同士の論理積にさらに順次論理積をとり，段数が異なる任意の論理積の出力同士の論理積から形成されるとしてもよい。
【００２６】
当該２のべき乗×１．５個のセルから構成されるユニットの空き情報は，その構成されるセル群を２対１に分けたセル群の論理積によって表すことができる。従って，隣接するセル同士の論理積にさらに順次論理積をとり，段数が異なる任意の論理積の出力同士の論理積で表すことが可能となる。
【００２７】
任意のセル群からデータを削除するデータ削除部をさらに備え，上記空き情報更新部は，データが削除されたセルの空き情報も更新するとしてもよい。かかる構成により，データが削除されたことによって空きセルとなったセルを容易に把握することが可能となる。
【００２８】
また，当該メモリ管理装置が記憶対象となるメモリ自体を含んで構成されるとしてもよい。
【００２９】
上記課題を解決するために，本発明の別の観点によれば，固定長の記憶領域からなるセル単位で，メモリへのデータの記憶または読み出しを管理するメモリ管理方法であって：上記メモリに記憶されるデータのセル長を計数するセル長計数ステップと；上記メモリの各セルに対応付けられセルの記憶状態を示す空き情報に基づいて，上記セル長以上連続して空いており，かつ，隣接するセルが占有されている空きセル群を検出する空きセル群検出ステップと；上記検出された空きセル群に上記データを記憶するデータ記憶ステップと；上記データが記憶された各セルの空き情報を更新する空き情報更新ステップと；を含むことを特徴とする，メモリ管理方法が提供される。
【００３０】
上述したように，本発明では，隣接するセルにデータが記憶されている空きセル群を敢えて選択し，記憶すべきデータが辛うじて入るそのような断片化された空間にデータを記憶する。こうして，メモリ空間上における記憶領域の連続性を高めることができ，充填率，利用効率を上げることが可能となる。
【００３１】
上記セル群検出ステップは，セル，および２のべき乗個もしくは２のべき乗×１．５個のセルから構成されるユニットのいずれかの単位で空きセル群を検出するとしてもよい。
【００３２】
記憶単位としてセルおよびユニットを用いることにより，体系化したメモリの管理を行うことができ，また，２のべき乗個もしくは２のべき乗×１．５個のセルの段階を設けることにより，メモリ空間を高い分解能で管理することができる。従って，より効率的なメモリ空間を築くことが可能となる。
【００３３】
上記セル群検出ステップは，該当する空きセル群が検出されなかった場合，検出した単位よりセル長が長いユニット単位で再度検出し直すとしてもよい。
【００３４】
このように，セル数の少ないセルもしくはユニットから順に空きセル群を探すことによって，記憶すべきデータに応じた領域に無駄なくデータを記憶することができ，より効率的なメモリ空間を築くことが可能となる。
【００３５】
また，上述したメモリ管理装置における従属項に対応する構成要素やその説明は，当該メモリ管理方法にも適用可能である。
【００３６】
上記課題を解決するために，本発明の別の観点によれば，メモリに対して，送受信されるデータを固定長の記憶領域からなるセル単位で記憶または読み出しする通信装置であって：上記メモリに記憶されるデータのセル長を計数するセル長計数部と；上記メモリの各セルに対応付けられセルの記憶状態を示す空き情報に基づいて，上記セル長以上連続して空いており，かつ，隣接するセルが占有されている空きセル群を検出する空きセル群検出部と；上記検出された空きセル群に上記データを記憶するデータ記憶部と；上記データが記憶された各セルの空き情報を更新する空き情報更新部と；を備えることを特徴とする，通信装置が提供される。
【００３７】
上述しているメモリは，通信装置における送受信データのバッファとしての利用価値が高い。従って，メモリの容量を無制限に大きくすることができない通信装置においても，メモリ空間上における記憶領域の連続性を高めることができ，充填率，利用効率を上げることが可能となる。
【００３８】
上述したメモリ管理装置における従属項に対応する構成要素やその説明は，当該通信装置にも適用可能である。
【発明の効果】
【００３９】
以上説明したように本発明によれば，隣接するセルにデータが記憶されている空きセル群を簡単な論理計算によって容易に把握することができるため，データ記憶にかかる処理遅延をもたらすことなく，メモリ空間の利用効率を上げ，少ないメモリ容量でも多くのデータを蓄積することが可能である。
【発明を実施するための最良の形態】
【００４０】
以下に添付図面を参照しながら，本発明の好適な実施の形態について詳細に説明する。なお，本明細書及び図面において，実質的に同一の機能構成を有する構成要素については，同一の符号を付することにより重複説明を省略する。
【００４１】
蓄積交換型の通信システムにおいては，通信装置間でデータを伝送する際に，送受信すべきデータをパケット等の伝送単位にアセンブルしている。
【００４２】
図１１は，一般的な蓄積交換型の通信システムにおける通信装置１０の概略的な機能を示したブロック図である。図中通信装置１０のアクセス制御部１２は，上位レイヤ１４から送信すべきデータを受け取ると，アクセス制御部１２内にあるバッファとしてのメモリ１６に一旦データを蓄積し，伝送メディアの状況に応じてバッファからデータを取り出し，送信パケットを生成，モデム１８を介して他の通信装置３０に送信する。蓄積されたデータは，メモリ管理装置２０によって管理され，送信データのアドレスに関しては送信アドレスカウンタ２２，受信データのアドレスは受信アドレスカウンタ２４が用いられる。
【００４３】
このように送信されたパケットは受信側の通信装置３０で正しく複合されるとは限らない。従って，アクセス制御部１２は，受信側の通信装置３０から受信確認の応答があるまで，上記メモリ１６内のデータを消去することなく保持し，必要に応じて再送するなどの処理を行っている。
【００４４】
このようなメモリ空間の管理を行うシステムとして，例えば，ＦＡＴ型ファイルシステムが利用されている。
【００４５】
図１２は，ＦＡＴ型ファイルシステムのメモリの取り扱いを説明するための説明図である。当該ＦＡＴ型ファイルシステムは，例えば，０ｘ００００〜０ｘＦＦＦＦバイトの記憶領域５０において，クラスタ５２と呼ばれる固定長単位，ここでは，０ｘ１００バイト単位でメモリ空間の管理を行い，通常，一つのデータを一つのクラスタに格納している。
【００４６】
しかしながら，データ通信の際交換されるデータは様々なアプリケーションにより生成されるので，送信されるパケットは，数十バイト程度の小さなものから数千バイト程度の大きなものまで様々な大きさで形成される。従って，０ｘ８０バイトのデータ５４を記憶する場合でも，０ｘ１０バイトのデータ５６を記憶する場合でも，同様に１つのクラスタが割り当てられ，例えば，０ｘ１０バイトのデータ５６が記憶されたクラスタの他の領域は利用することができなくなる。これは，メモリ空間の有効利用という観点からは好ましいことではない。
【００４７】
また，メモリ空間の他の管理方法として，記憶領域をリングバッファ状に形成し，データをＦＩＦＯで入出力する方法も挙げられる。かかるＦＩＦＯの処理では，データの入出力の度に格納ポインタもしくは取り出しポインタが更新され，メモリのどの領域が現在利用されていないかを容易に把握することができる。
【００４８】
しかし，蓄積交換型の通信システムにおいては，即時性が求められるパケットと，あまり即時性が求められないパケットとが混在し，アクセス制御部１２は，即時性の求められるパケットを検出すると優先的に送信しなければならない。従って，上述したリングバッファによるＦＩＦＯでは，任意アドレスのデータを抽出するパケット処理に対応できない。
【００４９】
このようなデータの蓄積という観点から，アクセス制御部１２において大容量のメモリを設ける必要がある。しかし，単にメモリの容量を大きくするだけでは，ハードウェアの大型化，高コスト化，高消費電力化を招くこととなる。従って，小容量のメモリで如何にして要求に見合ったメモリ管理を行うかが注目される。また，このような処理を実行できたとしても，それに伴って多くの処理遅延が生じると，情報の転送に時間がかかったり，処理中にデータがオーバーフローしたりするなどの新たな問題が発生する。従って，このメモリ管理処理は短期間で行う必要がある。
【００５０】
このような問題に鑑みて，本発明の実施形態においては，（１）メモリへのデータの記憶時において，隣接するセルには既にデータが記憶されている空きセル群を敢えて選択し，記憶すべきデータが辛うじて入るそのような断片化された空間にデータを記憶する。こうして，メモリ空間上における記憶領域の連続性を高めることができ，充填率，利用効率を上げることが可能となる。
【００５１】
また，（２）従来のクラスタ単位ではなく，固定長の記憶領域からなるセルおよび複数のセルによって定義されるユニット単位を定義し，記憶すべきデータの長さに応じて，セルもしくはユニットを選択し，その単位でメモリ空間を管理することによって，データの大きさに応じた適切な記憶領域と配置が割り当てられ，メモリ空間の利用効率をさらに上げることが可能となる。
【００５２】
上記（１），（２）によって，データ記憶にかかる処理遅延をもたらすことなく，メモリ空間の利用効率を上げ，少ないメモリ容量でも多くのデータを保持することが可能となる。以下，このような本実施形態に関する具体的な機能を詳述する。
【００５３】
（第１の実施形態：メモリ管理装置）
図１は，第１の実施形態によるメモリ管理装置１００の概略的な構成を示した機能ブロック図である。かかるメモリ管理装置１００は，中央制御部１２０と，セル長計数部１２２と，空きセル群検出部１２４と，データ記憶部１２６と，空き情報更新部１２８と，データ削除部１３０とを含んで構成され，固定長の記憶領域からなるセル単位で，メモリ１１０へのデータの記憶または読み出しを管理している。ここでは，理解を容易にするため固定長が１バイトのセルを想定しているが，セルの長さは任意に設定することができる。
【００５４】
また，当該メモリ管理装置１００は，メモリ１１０自体を含んで構成することもできる。また，かかるメモリ１１０は，ＲＡＭ，Ｅ２ＰＲＯＭ，不揮発性ＲＡＭ，フラッシュメモリ，カードメモリ，ＵＳＢメモリ，ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）等の記憶媒体から構成されてもよい。
【００５５】
上記中央制御部１２０は，中央処理装置（ＣＰＵ）を含む半導体集積回路により，上位レイヤの指令に応じてメモリ管理装置１００全体を管理および制御する。
【００５６】
上記セル長計数部１２２は，上位レイヤ１４０から送信すべきデータを，もしくはモデム１４２から受信したデータを受け取ると，その送信もしくは受信データのセル長（セルの長さ）を計数する。例えば，データが３バイトから構成されている場合，セルを１バイトとした本実施形態において，セル長は３となる。かかるセル長は，後述の空きセル群検出部１２４が記憶可能な領域を検出するために利用される。
【００５７】
このようなデータを記憶するメモリ１１０は，上述したようにセル単位で管理され，各セルにはそのセルに既にデータが記憶されているかどうかを示す空き情報が対応づけられている。本実施形態においては，空き情報を１ビットで表し，空いている状態を「１」，既にデータで占有されている状態を「０」で表す。
【００５８】
上記空きセル群検出部１２４は，メモリ１１０の各セルに対応付けられセルの記憶状態を示す空き情報に基づいて，セル長計数部１２２で求められた送信もしくは受信データのセル長以上連続して空いており，かつ，隣接するセルが占有されている空きセル群を検出する。即ち，自己のセルが空き状態「１」であり，隣接するセルが占有状態「０」となるセルが空きセル群（１つのセルの場合は空きセル）である。
【００５９】
メモリ１１０への記憶および削除を繰り返す際に，次に記憶するであろうデータを考慮せず，空いているセルを自由に利用すると，所謂「虫食い」の状態になり，大きなデータを記憶することが困難になってオーバーフローを起こしかねない。上記空きセル群検出部１２４によって，このような問題を回避できる。
【００６０】
図２は，上記空きセル群を説明するためメモリ空間の一部を抽出した説明図である。かかるメモリ空間では，０ｘ００００〜０ｘ０００７までのセルがあり，０ｘ００００，０ｘ０００２および０ｘ０００７のセルには既にデータが書き込まれている。かかるデータが書き込まれているセルの空き情報は占有状態を示す「０」となっている。
【００６１】
例えば，１セルからなるデータを記憶する場合，このメモリ空間を参照すると，０ｘ０００１，０ｘ０００３〜０ｘ０００６の６セルが記憶可能，即ち空きセルである。ここで，空きセル群検出部１２４は，隣接するセルが既にデータに占有されている空きセル，即ち０ｘ０００１，０ｘ０００３，および０ｘ０００６を敢えて選択する。
【００６２】
このように記憶すべきデータが辛うじて入るそのような断片化された空間にデータを記憶することによって，メモリ空間上における記憶領域の連続性を高めることができる。図２において，隣接するセルも空いている０ｘ０００４，０ｘ０００５に新たにデータを記憶した場合，最早連続した空き領域は２セル分しかとることができない。上記０ｘ０００４や０ｘ０００５ではなく，例えば，０ｘ０００１にデータを記憶した場合，連続した空き領域として４セルを確保でき，次に大きなデータが来ても対応可能となる。
【００６３】
上記データ記憶部１２６は，空きセル群検出部１２４によって検出された空きセル群，例えば図２における０ｘ０００１，０ｘ０００３，０ｘ０００６に記憶すべきデータを記憶する。
【００６４】
上記空き情報更新部１２８は，データが記憶された各セルの空き情報を更新する。例えば，図２において０ｘ０００１にデータが記憶された場合，０ｘ０００１のセルの空き情報は「１」から「０」に更新される。
【００６５】
上記データ削除部１３０は，上位レイヤ１４０もしくはモデム１４２からのデータ削除指令を受けて，任意のセル群からデータを削除する。このとき，空き情報更新部１２８は，データが削除されたセルの空き情報も更新するとしてもよい。例えば，図２において０ｘ０００２のデータを削除した場合，０ｘ０００２のセルの空き情報は「０」から「１」に更新される。かかる構成により，データが削除され，再度データを書き込むことが可能となったセルを容易に把握することができる。
【００６６】
かかるメモリ管理装置１００では，上述したように，メモリ１１０へのデータの記憶時において，特定のセル長以上連続して空いており，かつ，隣接するセルが占有されている空きセル群を検出して，記憶すべきデータが辛うじて入るそのような断片化された空間にデータを記憶する。こうして，メモリ空間上における記憶領域の連続性を高めることができ，充填率，利用効率を上げることが可能となる。
【００６７】
（空きセル群検出部１２４）
上述したような構成により，同容量のメモリ１１０を効率的に利用できるので，ハードウェアの大型化，高コスト化，高消費電力化を招くことなく，小容量のメモリ１１０で目的を達成することが可能となる。しかし，このような処理を実行するために多くの処理遅延が伴うと，情報の転送に時間がかかったり，処理中にデータがオーバーフローしたりするので，メモリ管理に関する処理は短時間で行う必要がある。以下では，空きセル群検出部１２４による空きセル群の具体的な検出回路を詳述する。
【００６８】
図３は，空きセル群検出部１２４の具体的な回路構成を説明した回路図である。かかる回路図では，左側にメモリ１１０の各セルが縦に並置され，その各セルにはそれぞれ空き情報が対応付けられている。従って，上記で新たにデータが記憶された０ｘ０００１のセルの空き情報は「０」となっており，まだ，データが記憶されていない０ｘ０００３〜０ｘ０００６のセルの空き情報は「１」となっている。
【００６９】
空きセル群検出部１２４では，まず，空きセル検出ブロック１４８において，隣接するセル同士，例えば，セル０ｘ００００と０ｘ０００１，セル０ｘ０００２と０ｘ０００３の空き情報の排他的論理和（ＥＸＯＲ）をとり，さらに，その排他的論理和の結果と各空き情報との論理積（ＡＮＤ）をとる。こうして，図中空きセル群のフラグ１５０に示すような結果を得ることができる。
【００７０】
かかる論理計算によると，２つのセルにおいて，自己のセルは空いているが，隣接しているセルは占有されているということを，値が「１」となっていることで容易に把握することができる。ここでは，０ｘ０００３および０ｘ０００６のセルがそれに当たる。従って，データ記憶にかかる処理遅延をもたらすことなく，メモリ空間の利用効率を上げることが可能となる。
【００７１】
（ユニット単位）
また，データの記憶または読み出しは，上述したセル単位に加えて，複数のセルによって定義されるユニット単位でも行われるとしてもよい。また，このようなユニットは，２のべき乗個のセルから構成されるとしてもよく，空きセル群検出部１２４は，セルまたはユニットのいずれかの単位で空きセル群を検出するとしてもよい。
【００７２】
図４は，本実施形態におけるメモリの取り扱いを説明するための説明図である。図４では，固定長の記憶領域からなるセル単位に加えて，そのセルを複数連ねたユニット単位も形成する。例えば，０ｘ００００〜０ｘＦＦＦＦバイトの記憶領域２００上で，３２バイトからなるセル２０２が定義され，セルを２つ連ねたユニット２０４，さらにセルを４つ連ねたユニット２０６，セルを８つ連ねたユニット２０８も定義される。このように従来のクラスタのような一次元のメモリ管理ではなく，二次元の分け方でメモリを管理する。
【００７３】
このように複数のセルからなるユニットを定義することによって，当該メモリ管理装置１００は，記憶すべきデータの長さに応じて，セルもしくはユニットを選択し，その単位でメモリ空間を管理することができる。従って，各記憶すべきデータは，データの大きさに応じた適切な記憶領域と配置が割り当てられ，メモリ空間の利用効率をさらに上げることが可能となる。また，ユニットを２のべき乗個に制限することで，メモリ空間の管理処理を容易にすることができる。
【００７４】
また，ユニットのセル数を大きく定義すると，送受信されるデータもしくはパケットの長さに拘わらず１つのユニット内にデータを納めることもでき，１つのユニットに複数のデータを入れることも可能となる。このようにユニットのセル数を調整して，１つのデータもしくはパケットが複数のユニットに跨るのを防ぐことも可能である。
【００７５】
（ユニット単位での空きセル群検出部１２４）
セルおよびユニット単位でメモリを管理した場合における，空きセル群の具体的な検出回路を以下に詳述する。
【００７６】
図５は，空きセル群検出部１２４の具体的な回路構成を説明した回路図である。かかる回路図では，左側にメモリ１１０の各セルが縦に並置され，その各セルにはそれぞれ，図３同様の空き情報が対応付けられている。ここでは，２セルからなるユニットに関して空きセル群を検出する処理を想定する。
【００７７】
空きセル群検出部１２４では，まず，隣接するセル同士，例えば，０ｘ００００と０ｘ０００１，０ｘ０００２と０ｘ０００３の空き情報の論理積をとり，それを２セルからなるユニットの空き情報と定義する。従って，定義された２セルが全て空いている場合に限り，論理積の結果が空きを示す「１」となる。
【００７８】
続いて，空きセル検出ブロック１４８を用い，隣接するユニット同士，即ち，上記２セルの論理積（ユニットの空き情報）の結果同士の排他的論理和をとり，さらに，その排他的論理和の結果と各ユニットの空き情報との論理積をとる。こうして，図中空きセル群のフラグ２５０に示すような結果を得ることができる。
【００７９】
かかる論理計算によると，２つのユニットにおいて，自己のユニットは完全に空いているが，隣接しているユニットは少なくとも１つのセルがデータに占有されているということを，値が「１」となっていることで容易に把握することができる。ここでは，０ｘ０００４と０ｘ０００５とのユニットがそれに当たる。かかる構成により，ユニット単位においてもセル単位同様に利用効率の高いメモリ管理が可能となる。
【００８０】
また，さらに大きなユニット単位でメモリを管理する場合でも，上述したセルおよび２セルからなるユニットの関係に従って，空きセル群検出部１２４を構成することができる。例えば，取り扱うべきユニットに含まれる全てのセルの空き情報の論理積を，隣接するセル同士の論理積にさらに順次論理積をとり各出力をカスケード接続して形成することにより，簡単に構成することができる。
【００８１】
図６は，空きセル群検出部１２４の具体的な回路構成を説明した回路図である。かかる回路図では，セル，２セルからなるユニット，４セルからなるユニット，および，８セルからなるユニットに関して空きセル群を探している。
【００８２】
空きセル群検出部１２４では，まず，隣接するセル同士，例えば，０ｘ００００と０ｘ０００１，０ｘ０００２と０ｘ０００３の空き情報の論理積をとり，それを２セルからなるユニットの空き情報と定義する。さらにその隣接する２セルからなるユニット同士の空き情報の論理積をとり，それを４セルからなるユニットの空き情報とする。８セルからなるユニットも同様に構成される。
【００８３】
続いて，上述したように，隣接するセルもしくはユニット同士，即ち，論理積の結果同士の排他的論理和をとり，さらに，その排他的論理和の結果と各空き情報との論理積をとる。こうして，図中空きセル群のフラグ１５０，２５０，２６０，２７０に示すような結果を得ることができる。
【００８４】
このフラグ１５０，２５０，２６０，２７０を参照すると，自己のユニットが空きセルのみで構成され，かつ，隣接するユニットが少なくとも１つのセルにおいてデータに占有されている空きセル群は，１セルの０ｘ０００３，０ｘ０００６および２セルからなるユニットの０ｘ０００４と０ｘ０００５のみということが理解される。このようにして各ユニットにおける空きセル群を容易に抽出することが可能となる。
【００８５】
また，ユニットは，さらに各２のべき乗×１．５個のセルから構成されるとしてもよい。２のべき乗のほぼ中間にあたる２のべき乗×１．５個のセルからなるユニットを加えることにより，２のべき乗のみのユニットと比較してより高い分解能でメモリ空間を管理することができ，より効率的なメモリ空間を築くことが可能となる。
【００８６】
上記２のべき乗×１．５個のセルから構成されるユニットに含まれる全てのセルの空き情報の論理積は，隣接するセル同士の論理積にさらに順次論理積をとり，段数が異なる任意の論理積の出力同士の論理積から形成されるとしてもよい。
【００８７】
図７は，空きセル群検出部１２４の具体的な回路構成を説明した回路図である。かかる回路図では，２つのセル（ユニット）と１つのセルをカスケード接続して，３セルからなるユニットの空き情報を生成し，また，さらにその出力をカスケード接続して６セルからなるユニットの空き情報も生成している。
【００８８】
図７に示したように，当該２のべき乗×１．５個のセルから構成されるユニットの空き情報は，その構成されるセル群を２対１に分けたセル群の論理積によって表すことができる。従って，このようなユニットの空き情報は，隣接するセル同士の論理積にさらに順次論理積をとり，段数が異なる任意の論理積の出力同士の論理積で表すことが可能となる。こうして，図中空きセル群のフラグ２８０，２９０に示すような結果を得ることができる。
【００８９】
図８は，空きセル群検出部１２４の変形例を説明した回路図である。かかる回路図では，３セルからなるユニットが空いており，隣接する１セルがデータに占有されていることを容易に把握することができる。図中空きセル群のフラグ３００を参照すると，０ｘ０００３〜０ｘ０００５および０ｘ０００４〜０ｘ０００６の２つのユニットが空きセル群となる。
【００９０】
図９は，空きセル群検出部１２４のさらなる変形例を説明した回路図である。かかる回路図では，６セルからなるユニットが空いており，隣接する２セルからなるユニットのいずれか１セルがデータに占有されていることを容易に把握することができる。図中空きセル群のフラグ３１０を参照すると，６セル分の空きセル群は無いことが理解できる。
【００９１】
このようなセルとユニットの空きセル群の検出回路は，上述した実施形態に限られず，当業者であれば当然にして組むことができる回路の範囲も当該実施形態に含まれる。
【００９２】
また，上記メモリ管理装置１００を備え，他の通信装置に送受信するデータを，メモリ１１０に対して，セルもしくはユニット単位で記憶または読み出しを行う通信装置も提供される。
【００９３】
また，上述した実施形態においては，理解を容易にするため１セルを１バイトや３２バイトとし，１ユニットは８セル以内で構成しているが，かかる場合に限らず，状況に応じて任意の値を設定することができる。例えば，ＴＣＰ／ＩＰを上位レイヤとする通信システムにおいて，バルク情報転送時に１５００バイトのパケットが多量に発生する場合等を考慮し，セル単位を１２８バイトや２５６バイトあるいは５１２バイトに設定し，１ユニットを６４，３２，もしくは１６セルで構成することもできる。かかる実質的な設定により，より効率よくメモリを利用することができる。
【００９４】
（第２の実施形態：メモリ管理方法）
次に，セルもしくはユニット単位の効率的なメモリ管理方法について詳述する。かかるメモリ管理方法は，基本的に，記憶すべきデータを入れることができるセルもしくはユニットを探し，記憶と同時に空き情報を更新している。また，このとき検出される空きセル群は，隣接するセルが既にデータに占有されていることを特徴とする。
【００９５】
図１０は，メモリ管理方法における処理の流れを表したフローチャートである。まず，メモリ管理装置１００のセル長計数部１２２は，上位レイヤ１４０から送信すべきデータを，もしくはモデム１４２から受信したデータを受け取ると，その送信もしくは受信データのセル長を計数する（Ｓ４００）。
【００９６】
そして，その結果に基づいて，検出すべき空きセル群の長さを求める（Ｓ４０２）。その長さの単位は，セル，２のべき乗個もしくは２のべき乗×１．５個のセルから構成されるユニットのいずれかの単位，即ち，１セルおよび２，３，４，６，８セルからなるユニットが準備されている。２のべき乗個もしくは２のべき乗×１．５個のセルの段階を設けることで，より高い分解能でメモリ空間を管理することができ，より効率的なメモリ空間を築くことが可能となる。従って，検出すべき空きセル群の長さを５セルとした場合（１セル５１２バイトで２５００バイトのパケットを取り扱う場合），５以上で一番近いユニット，即ち６セルからなるユニットが検出対象となる。
【００９７】
検出対象となるユニットが求められると，そのユニットに関する処理に移行する（Ｓ４０４）。空きセル群検出部１２４は，検出対象となるユニットの空き情報に基づいて，そのユニットが完全に空いており，かつ，隣接するユニットが占有されている空きセル群を検出する（Ｓ４０６，Ｓ０８，Ｓ４１０，Ｓ４１２，Ｓ４１４，Ｓ４１６）。具体的には，各ユニットに対する空きセル群のフラグ１５０，２５０，２８０，２６０，２９０，２７０の中で，「１」となるフラグがあるかどうか検出される。
【００９８】
ここで，「１」となるフラグが存在すると（Ｓ４３０，Ｓ４３２，Ｓ４３４，Ｓ４３６，Ｓ４３８，Ｓ４４０），データ記憶部１２６は，検出された空きセル群にデータを記憶し（Ｓ４５０），さらに，空き情報更新部１２８は，データが記憶された各セルの空き情報を更新する（Ｓ４５２）。
【００９９】
「１」となるフラグが存在しない場合，そのユニットでは適した空きセル群が存在しないということになるので，ユニットのセル数を一段上げて，即ち，２なら３に，３なら４に，４なら６にして再度空きセル群の検出を行う。そして，最終的なユニットでも適した空きセル群が検出できない場合，記憶失敗としてデータの格納を止めるか，もしくは，隣接するセルも空いているセル群を対象に検出し直すこととなる（Ｓ４５６）。
【０１００】
このように，本実施形態でも，第１の実施形態同様，隣接するセルにデータが記憶されている空きセル群を敢えて選択し，記憶すべきデータが辛うじて入るそのような断片化された空間にデータを記憶する。こうして，メモリ空間上における記憶領域の連続性を高めることができ，充填率，利用効率を上げることが可能となる。
【０１０１】
また，セル数の少ないセルもしくはユニットから空きセル群を順に探すことによって，記憶すべきデータに応じた無駄のない領域にデータを記憶することができ，より効率的なメモリ空間を築くことが可能となる。
【０１０２】
上述の実施形態では，通信装置を中心にメモリの管理方法を述べているが，当然，かかるメモリ管理を様々な電子機器のメモリ管理に適応することが可能である。
【０１０３】
以上，添付図面を参照しながら本発明の好適な実施形態について説明したが，本発明は係る例に限定されないことは言うまでもない。当業者であれば，特許請求の範囲に記載された範疇内において，各種の変更例または修正例に想到し得ることは明らかであり，それらについても当然に本発明の技術的範囲に属するものと了解される。
【０１０４】
また，上記の実施形態で用いられた具体的な数値はあくまで説明の便宜上引用した値であり，本実施形態の効果はこれら数値に限定されるものではない。また，ユニット数を拡張した場合であっても，その拡張回路構成は，図で示された回路の出力信号を多段にカスケード接続すれば提供可能であることは言うまでもない。
【０１０５】
また，上記の実施形態において，隣接するセルもしくはユニットにデータが占有されているかどうかは，隣接する一方しか参照していないが，当業者なら当然にして両方を参照する回路構成を考慮することは可能であり，コスト的な制限がなければ，そのようにすることでより一層メモリを効率的に扱えるのは容易に考えつく事項である。
【０１０６】
また，上述の実施形態では，セル毎に空き情報を対応付けているが，さらに，連続してデータに占有されているという連続占有情報も対応付けるとしてもよい。例えば，３セルからなるデータの１，２番目のセルには次のセルも同じデータであることを示す「１」が，３番目のセルには次のセルは他のデータであることを示す「０」が付加される。かかる情報により，格納した情報が複数のセルに跨っていることを把握することができる。また，空き情報更新部は，かかる連続占有情報も空き情報と共に更新するとしてもよい。
【０１０７】
なお，本明細書のメモリ管理方法における各工程は，必ずしもフローチャートとして記載された順序に沿って時系列に処理する必要はなく，並列的あるいは個別に実行される処理（例えば，並列処理あるいはオブジェクトによる処理）も含むとしても良い。
【図面の簡単な説明】
【０１０８】
【図１】第１の実施形態によるメモリ管理装置の概略的な構成を示した機能ブロック図である。
【図２】空きセル群を説明するためメモリ空間の一部を抽出した説明図である。
【図３】空きセル群検出部の具体的な回路構成を説明した回路図である。
【図４】第１の実施形態におけるメモリの取り扱いを説明するための説明図である。
【図５】空きセル群検出部の具体的な回路構成を説明した回路図である。
【図６】空きセル群検出部の具体的な回路構成を説明した回路図である。
【図７】空きセル群検出部の具体的な回路構成を説明した回路図である。
【図８】空きセル群検出部の変形例を説明した回路図である。
【図９】空きセル群検出部の変形例を説明した回路図である。
【図１０】メモリ管理方法における処理の流れを表したフローチャートである。
【図１１】一般的な蓄積交換型の通信システムにおける通信装置の概略的な機能を示したブロック図である。
【図１２】ＦＡＴ型ファイルシステムのメモリの取り扱いを説明するための説明図である。
【符号の説明】
【０１０９】
１００  メモリ管理装置
１１０  メモリ
１２２  セル長計数部
１２４  空きセル群検出部
１２６  データ記憶部
１２８  空き情報更新部
１３０  データ削除部
【図１】
2007241465.tif 000003
【図２】
2007241465.tif 000004
【図３】
2007241465.tif 000005
【図４】
2007241465.tif 000006
【図５】
2007241465.tif 000007
【図６】
2007241465.tif 000008
【図７】
2007241465.tif 000009
【図８】
2007241465.tif 000010
【図９】
2007241465.tif 000011
【図１０】
2007241465.tif 000012
【図１１】
2007241465.tif 000013
【図１２】
2007241465.tif 000014