JPH07334411A - 記憶領域管理方式 - Google Patents

Abstract

(57)【要約】 【目的】簡単な処理で領域の無駄が少ない記憶領域管理
方式およびそれを用いたデータバッファを提供すること
を目的とする。 【構成】複数のデータを記憶するデータバッファに、複
数の相異なる単位長を記憶する単位長記憶手段、データ
記憶手段に記憶されている複数のデータ各々に対応する
単位長を記憶するデータ長記憶手段を設ける。 【効果】本発明により、処理が簡単で領域の無駄の少な
い記憶領域管理が実現できる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、半導体メモリ等の記憶
装置内のデータ格納領域管理方式に係わり、特に通信装
置におけるパケットバッファの管理方式に関する。

【０００２】

【従来の技術】従来、ネットワークに接続される通信装
置等のバッファ管理においてデータを格納する領域の管
理の方法として２通りの方式が知られている。第１の方
式は、格納されるデータの長さに関わらずデータ長のと
りうる最大値に相当する領域を各データに割り当てる方
式であり、第２の方式は、比較的小さな固定長の領域を
ポインタでリンクし、データ格納に必要な量の領域をデ
ータごとに割り当てる方式である。（例えば、″Intern
etworking with TCP/IP volume2″,P32-33，1991, P
rentice hall）。

【０００３】

【発明が解決しようとする課題】上述した従来の管理方
式のうち、第１の方式ではデータの最大長に比べて極端
に短いデータ、例えば最大長４キロバイトに対して６４
バイトのデータ、を格納する場合に大部分の記憶領域が
無駄になるという問題があった。第２の方式においては
領域の長さを小さく（例えば１２８バイトに）すれば、
領域の無駄は少なくなるが、データごとの領域の使用個
数の記録や、バッファ管理用ポインタの更新でポインタ
更新量を計算するなどの処理が必要になるという欠点が
あった。

【０００４】本発明の目的は、記憶領域管理のための処
理を少なくし、かつ領域の無駄が少ない記憶領域管理方
式を提供することにある。

【０００５】

【課題を解決するための手段】記憶領域管理のために、
確率の大きいデータ長を単位長として設定し、データ記
憶手段に格納される各データに対し複数の単位長のなか
でデータを格納し得る最も短い単位長の領域を割当て、
各データに割り当てられた領域がどの単位長であるかを
記録する。

【０００６】

【作用】本発明によれば、あらかじめ設定した複数の単
位長のうちのいずれかと近い長さを持つデータの格納に
おいては領域の無駄が小さくなるので、データ長の確率
分布に基づいて単位長を設定すれば無駄の生じる確率を
小さくできる。

【０００７】またポインタの更新も、データ格納に使用
した領域が複数の単位長のどれであるかをデータ長記憶
手段から判別しその単位長をポインタに加算するだけ
で、更新量を毎回計算する必要はないため処理が容易で
ある。

【０００８】

【実施例】次に本発明の各実施例について説明する。図
２に示すネットワーク間接続装置２００は受信処理部１
００の受信パケットバッファで本発明による記憶領域管
理方式を用いている。

【０００９】図１に示した受信処理部１００は、パケッ
トに対して処理を行うプロセッサ１１０、半導体メモリ
で実現されたデータ記憶手段７００、ネットワークイン
ターフェース２２０から受信したパケットをデータ記憶
手段７００に書き込むデータ書き込み手段３００、デー
タ記憶手段７００内の処理済みパケットをプロセッサ１
１０の指示で送信処理部２１０に転送するデータ読みだ
し手段５００とからなる。

【００１０】受信処理部１００ではデータ記憶手段７０
０内のデータ格納領域７１０を循環バッファとして管理
している。ネットワークインターフェース２２０から受
信したパケットはデータ書き込み手段３００によりデー
タ格納領域７００に格納され、プロセッサ１１０により
処理が行われた後データ読みだし手段５００により送信
処理部２１０に転送される。転送が終わり不用になった
パケットの格納されている領域は、再び受信パケットを
格納するために使うので、パケットの転送終了時にデー
タ読みだし手段５００からデータ書き込み手段３００に
対して領域の解放を通知する。

【００１１】次にデータ書き込み手段３００およびデー
タ読みだし手段５００の詳細について以下で説明する。

【００１２】まず、データ書き込み手段３００の詳細を
図３に従って説明する。データ書き込み手段３００は、
パケット長を計数するカウンタ３１０、２つの異なる単
位長を記憶する単位長記憶手段３３０、カウンタ３１０
の値に基づいて２つの単位長から１つを選択する選択回
路Ａ３４１、データ書き込みアドレス生成部３８０、お
よびそれらを制御する制御回路３９０などで構成されて
いる。

【００１３】ネットワークインターフェース２２０はパ
ケットの受信に先立ってパケット受信開始を制御回路３
９０に通知する。制御回路３９０はカウンタ３１０のリ
セットを行い、パケット長の計数を開始させる。ネット
ワークインターフェース２２０からパケットが送られて
くると、データ書き込みアドレス生成部３８０がパケッ
トを格納するアドレスをデータ記憶手段７００に対して
出力し、パケットを図４に示すように、パケットに割り
当てられた領域の先頭１ワードをあけて格納する。あけ
た１ワードはデータ長記憶領域４１０として使用され
る。

【００１４】データ書き込みアドレス生成部３８０の出
力するアドレスは常に書き込み領域末尾アドレスタ３７
０と比較回路３８５により比較され、データ記憶領域７
００内の他のデータを破壊しないよう制御回路３９０に
より監視されている。パケットの格納の途中で未使用領
域が不足した場合、そのパケットは廃棄される。パケッ
トの廃棄に関しては、予め未使用領域長を計算しパケッ
トの最大長よりも大きい場合にのみパケットの受信を許
可するようにしても良い。

【００１５】１パケットの受信が終了するとネットワー
クインターフェース２２０は制御回路３９０にパケット
受信終了を通知する。その時点でのカウンタ３１０の値
に基づいて選択回路Ａ３４１は単位長記憶手段３３０の
単位長を選択する。選択された単位長はそのパケットの
格納に割当てる領域の長さになる。パケットの占める領
域の長さが単位長Ａ８１０であるか単位長Ｂ８２０であ
るかはデータ長記憶領域４１０に記録される。データ長
記憶領域４１０には、パケットの占める領域の長さが単
位長Ａ８１０であること示す単位長Ａ記録符号５６１ま
たは単位長Ｂ８２０であることを示す単位長Ｂ記録符号
５６２のいずれかの値が記録される。単位長記録符号Ａ
５６１および単位長Ｂ記録符号Ｂ５６２はあらかじめデ
ータ長記録手段３２０に登録されており、カウンタ３１
０の値に基づいて適当な記録符号が選択され、データ長
記憶領域４１０に記録される。

【００１６】１パケットの格納が終わりデータ長記憶領
域４１０に単位長Ａ記録符号５６１または単位長Ｂ記録
符号５６２が記録された後、選択回路Ａ３４１により選
択された単位長を加算回路３５１により書き込み領域先
頭アドレス３６０に加算しパケットに適当な単位長の領
域を割当てる。

【００１７】また割当てた領域の解放は、データ読みだ
し手段５００から領域解放通知信号５１０を受けた制御
回路３９０が選択回路Ｂ３４２に指示を与えることによ
り、選択された単位長が書き込み領域末尾アドレス３７
０に加算されることで行われる。

【００１８】次にデータ読みだし手段の詳細について図
４に沿って説明する。データ読みだし手段５００はプロ
セッサ１１０の転送起動信号１２０により転送を開始す
る。まず、データ長記憶領域４１０の値が比較回路５５
０に送られ、単位長Ａ記録符号５６１と単位長Ｂ記録符
号５６２のいずれであるかを判別する。その結果にもと
づいて制御回路５４５は転送を制御する。転送終了後、
データ読みだし領域先頭アドレス５３５に単位長Ａ８１
０または単位長Ｂ８２０が加えられる。

【００１９】１パケットの転送終了時にデータ読みだし
手段５００はデータ書き込み手段３００に対して、単位
長Ａ８１０、単位長Ｂ８２０どちらの長さの領域を解放
するかを領域解放通知信号５１０で伝える。

【００２０】次に、この実施例における記憶領域管理に
ついて具体例を示して説明する。仮に、本実施例のネッ
トワーク間接続装置の扱うパケットが最大１５００バイ
ト、最小４８バイトであるとする。パケット長の分布を
６４バイト以下のパケットが２５％、１５００バイトの
パケットが６５％、その他の長さのパケットが１０％と
した場合、単位長Ａ８１０を６４バイト、単位長Ｂ８２
０を１５００バイトに設定すると、メモリの無駄が大き
くなるのは全パケットの約１０％の場合に抑えられる。

【００２１】これに対して、短い固定長、例えば６４バ
イト、の固定長領域を必要なだけ割当てる方式では、記
憶領域の無駄は少なくなるが、パケットに対して割当て
る領域の大きさの計算や、ポインタ更新の計算のための
論理回路が必要になる。また６４バイト単位の割当てで
は１から２４の領域を１パケットに対して割当てるの
で、領域長の記録のための資源が多く必要であるが、本
実施例では、例えば単位長Ａ記録符号５６１を０、単位
長Ｂ記録符号５６２を１と割当てれば１ビットで記録可
能であり、領域の大きさの記録のための資源が少なくて
すむ。

【００２２】以上のように本発明を用いた記憶領域管理
ではデータ長の分布を反映した記憶領域の割当てを行う
ことで、単純な処理で領域の無駄の少ない管理が行え
る。

【００２３】次に本発明の他の実施例を図６に示す。こ
の実施例ではデータバッファ６００に記憶領域管理用プ
ロセッサ６３０を用意し、ソフトウェアで記憶領域の管
理を行っている。データ長記録手段はプログラムとして
実現され、単位長はプログラム上の定数、あるいはプロ
グラムメモリ６４０上のデータとして記憶されており、
外部から変更することが可能である。データ記憶手段６
０５内の領域の割当て方は図１の実施例と同様であるも
のとする。

【００２４】このデータバッファ６００に外部からデー
タが入力されると、書き込みＤＭＡコントローラ６１０
はカウンタ６１１でデータ長の計数を始める。記憶領域
管理用プロセッサ６３０はカウンタ値６１１とソフトウ
ェア内に記述された複数の相異なる単位長とを比較して
適当な単位長を選択し、データ記憶手段６０５のデータ
長記憶領域に単位長記録符号６１５を記録する。同時に
ソフトウェアで管理している書き込み領域先頭アドレス
６１４に選択した単位長を加算して、それを書き込みＤ
ＭＡコントローラ６１０のアドレス発生回路６１２に通
知する。外部から次に入力されるデータはこのアドレス
から格納される。

【００２５】データバッファ装置６００に対して転送起
動信号６２３が送られると、記憶領域管理用プロセッサ
６３０はデータ長記憶領域の単位長記録符号６１５を調
べ転送するデータ長を計算し、読みだしＤＭＡコントロ
ーラ６２０のアドレス発生回路６２１に転送長６２２と
して通知する。読みだしＤＭＡコントローラ６２０は指
定された転送長の転送を終了すると、転送終了通知信号
６２１で記憶領域管理用プロセッサ６３０に対し転送終
了を通知する。記憶領域管理用プロセッサ６３０はソフ
トウェアで管理している書き込み領域末尾アドレスを更
新する。

【００２６】図６の実施例では図１の実施例においてハ
ードウェアで実現していた機能をソフトウェアで実現し
ており、ハードウェア部の単純化と単位長の外部からの
変更が可能だという特徴がある。

【００２７】以上、本発明を実施例に沿って説明した
が、本発明のデータバッファ装置は通信装置に限らず広
範囲に適用可能である。

【００２８】

【発明の効果】以上説明したように本発明によれば複雑
な処理無しに記憶領域の無駄の少ない記憶領域管理を実
現できる。

【図面の簡単な説明】

【図１】本発明によるデータバッファの第１実施例を示
すブロック図である。

【図２】図１の実施例を用いた通信装置を示すブロック
図である。

【図３】図１の実施例のデータ書き込み手段の詳細なブ
ロック図である。

【図４】図１の実施例におけるパケットの格納の説明図
である。

【図５】図１の実施例のデータ読みだし手段の詳細なブ
ロック図である。

【図６】本発明の第２実施例を示すブロック図である。

【符号の説明】

１００…受信処理部、 ２００…ネットワーク間接続装置、 ３００…データ書き込み手段、 ３２０…データ長記録手段、 ３３０，５２０…単位長記憶手段、 ４１０，７２１，７２２，７２３…データ長記憶領域、 ５００…データ読みだし手段、 ５６１…単位長Ａ記録符号、 ５６２…単位長Ｂ記録符号、 ６０５，７００…データ記憶手段、 ７１９…データ格納領域、 ８１０…単位長Ａ、 ８２０…単位長Ｂ。

Claims (7)

【特許請求の範囲】
1. 【請求項１】複数のデータを記憶するデータ記憶手段に
   おいて、複数の相異なる単位長を記憶する単位長記憶手
   段と、該データ記憶手段に記憶されている複数のデータ
   各々に対応する単位長を記憶するデータ長記憶手段と、
   各データに対応する単位長を該データ長記憶手段に記録
   するデータ長記録手段を設け、各データに対して割当て
   る領域の長さが該単位長記憶手段に記憶された複数の単
   位長の中でそのデータ長以上の値である単位長のうちで
   最も短い単位長と等しく、該データ長記録手段はその単
   位長を該データ長記憶手段に記録することを特徴とする
   記憶領域管理方式。
2. 【請求項２】請求項１の記憶領域管理方式を用いること
   を特徴とするデータバッファ。
3. 【請求項３】請求項２のデータバッファにおいて、前記
   データ長記憶手段を前記データ記憶手段内の領域として
   実現することを特徴とするデータバッファ。
4. 【請求項４】請求項１の記憶領域管理方式において、前
   記単位長記憶手段に記憶された複数の単位長が外部から
   変更可能であることを特徴とする記憶領域管理方式。
5. 【請求項５】請求項１の記憶領域管理方式において、格
   納するデータの長さの確率分布において確率の大きなデ
   ータ長を単位長として設定することを特徴とする記憶領
   域管理方式。
6. 【請求項６】請求項２または請求項３記載のデータバッ
   ファをパケットバッファとして用いることを特徴とする
   通信装置。
7. 【請求項７】請求項１の記憶領域管理方式において、前
   記データ記憶手段に格納するデータの最大長を単位長の
   一つとして設定することを特徴とする記憶領域管理方
   式。