バッファ管理方法及びデータ処理装置

トップ :: G 物理学 :: G06 計算;計数

【発明の名称】	バッファ管理方法及びデータ処理装置
【発明者】	【氏名】須藤日出夫
【要約】	【課題】連続する未使用のブロックの検出を必要とするたび毎に、未使用のブロックの個数を計数することから、未使用の連続ブロックの検出に多大な時間を要する。【解決手段】少なくとも１つのブロックが使用されている使用状態から未使用状態に変化することにより生じた、連続する未使用のブロックのうちの少なくとも一つのブロックに対応する情報領域に、連続する当該ブロックの個数を示す個数情報を書き込み、バッファにデータを書き込むために複数のブロックが必要であると判断されたときに、管理テーブルの情報領域の個数情報に基づいて、書き込むべき連続する未使用のブロックを指定する。

【特許請求の範囲】
【請求項１】データを処理するためのデータ処理装置であって外部からのデータを内部処理のために一時的に格納するためのメモリー領域が複数のブロックに区画されたバッファと、それぞれが対応する各前記ブロックがデータの格納のために使用されているか否かを表す使用情報が書き換え可能に書き込まれる複数の情報領域から成る管理テーブルとを備えるデータ処理装置において前記バッファを管理する方法であって、少なくとも１つの前記ブロックが使用されている使用状態から未使用状態に変化することにより生じた、連続する未使用のブロックのうちの少なくとも一つのブロックに対応する前記情報領域に、連続する当該ブロックの個数を示す個数情報を書き込む書込ステップと、前記バッファにデータを書き込むために複数のブロックが必要であると判断されたときに、前記管理テーブルの前記情報領域の個数情報に基づいて、書き込むべき連続する未使用のブロックを指定する指定ステップとを含むことを特徴とするバッファ管理方法。
【請求項２】前記指定ステップは、前記した連続する未使用のブロックの先頭ブロックを特定するための先頭ブロック情報および連続する未使用の該ブロックの個数を示すブロック数情報を予め格納する管理レジスタが提供する前記先頭ブロック情報および前記ブロック数情報を参照して、前記データを書き込むべき連続する未使用のブロックを指定することを特徴とする請求項１記載のバッファ管理方法。
【請求項３】前記書込ステップは、連続する未使用のブロックに隣り合う他の未使用なブロックを包含することにより、新たな連続する未使用のブロックを生成し、該ブロックの先頭ブロックの前記個数情報を書き換えることを備えることを特徴とする請求項１記載のバッファ管理方法。
【請求項４】前記した未使用のブロックの包含による新たな連続する未使用なブロックの生成は、データを格納すべく指定された連続する未使用のブロックの個数の履歴に応じて実行されることを特徴とする請求項３記載のバッファ管理方法。
【請求項５】前記した未使用なブロックの包含による新たな連続する未使用なブロックの生成は、未使用の複数のブロックの分布に応じて実行されることを特徴とする請求項３記載のバッファ管理方法。
【請求項６】前記指定ステップは、連続する未使用のブロックのうち、その先頭または後尾に単独の未使用のブロックの生成を回避して、必要な個数のブロックを指定することを特徴とする請求項１記載のバッファ管理方法。
【請求項７】データを処理すべく、外部からのデータを内部処理のために一時的に格納するためのメモリー領域が複数のブロックに区画されたバッファと、それぞれが対応する各前記ブロックがデータの格納のために使用されているか否かを表す使用情報が書き換え可能に書き込まれる複数の情報領域から成る管理テーブルとを備えるデータ処理装置であって、それぞれが前記バッファ及び前記管理テーブルのために用いられる複数の記憶部を含み、各記憶部の前記バッファに用いられる領域および前記管理テーブルに用いられる領域の配置は、各記憶部でそれぞれ互いに同一であることを特徴とするデータ処理装置。
【請求項８】前記各記憶部における前記バッファに用いられる領域および前記管理テーブルに用いられる領域におけるそれぞれの前記ブロックおよび情報領域の配置は、各記憶部でそれぞれ互いに同一であることを特徴とする請求項７記載のデータ処理装置。
【請求項９】前記情報領域は、連続するブロックが使用されている使用状態から未使用状態に変化したときに、連続する未使用のブロックのうちの少なくとも一つのブロックに対応する前記情報領域に連続する当該ブロックの個数を示す個数情報を書き込まれることを特徴とする請求項７記載のデータ処理装置。
【請求項１０】さらに、連続するブロックが格納された使用状態から未使用状態に変化したときに、連続する当該ブロックのうちの少なくとも一つのブロックに対応する前記情報領域に連続する未使用の前記ブロックの個数を示す個数情報を書き込み、かつ前記バッファにデータを書き込むために複数のブロックが必要であると判断されたときに、前記管理テーブルの前記情報領域の個数情報に基づいて、書き込むべき連続する未使用のブロックを指定する制御部を含むことを特徴とする請求項７記載のデータ処理装置。

【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、プリンタのようなデータ処理装置に処理すべきデータを一時的に格納するために組み込まれるバッファを管理するバッファ管理方法および該管理方法を使用するデータ処理装置に関する。
【０００２】
【従来の技術】プリンタは、コンピュータから受信する印刷用、制御用、監視用等の様々な種類のデータを円滑に処理すべく、複数のアプリケーション・プログラムを有する。受信されたデータは、その種類に応じたアプリケーション・プログラムによって処理される。しかしながら、アプリケーション・プログラムがデータを処理するタイミングは互いに異なることから、先に受信されたデータが後に受信されたデータよりも先に処理されるとは限らない。そこで、このようなタイミングの相違を補完すべく、バッファが用いられている。
【０００３】バッファは、複数のブロックから構成される。プリンタが受信したデータは、バッファの未使用のブロックに次々に格納され、また、ブロックに格納された受信データがアプリケーション・プログラムによって処理のために読み出されると、そのブロックは、未使用状態に戻る。しかしながら、データの読み出し時の相違に起因して、使用中のブロックと未使用のブロックとが入り交じって存在する虫食い状態が生じ、未使用状態のブロックの連続性は損なわれやすい。
【０００４】データの高速処理には、データを連続するブロックに格納することが望ましい。そこで、従来、データの書込みに複数のブロックを要する場合、各ブロックが使用中か否かを個々にチェックすることにより、未使用のブロックを見つけ出し、さらに、見つけ出された未使用のブロックのうち連続する未使用のブロックの個数を計数することにより、必要な個数の連続する未使用のブロックを検出する。
【０００５】
【発明が解決しようとする課題】しかしながら、このような従来の方法では、連続する未使用のブロックの検出を必要とするたび毎に、連続する未使用のブロックの個数を計数する必要があり、そのために未使用の連続ブロックの検出に多大な時間を要するという問題があった。
【０００６】
【課題を解決するための手段】上記の問題を解決するために、本発明に係るバッファ管理方法は、データを処理するためのデータ処理装置であって外部からのデータを内部処理のために一時的に格納するためのメモリー領域が複数のブロックに区画されたバッファと、それぞれが対応する各ブロックがデータの格納のために使用されているか否かを表す使用情報が書き換え可能に書き込まれる複数の情報領域から成る管理テーブルとを備えるデータ処理装置において、少なくとも１つのブロックが使用されている使用状態から未使用状態に変化することにより生じた、連続する未使用のブロックのうちの少なくとも一つのブロックに対応する情報領域に、連続するブロックの個数を示す個数情報を書き込む書込ステップと、バッファにデータを書き込むために複数のブロックが必要であると判断されたときに、管理テーブルの情報領域の個数情報に基づいて、書き込むべき連続する未使用のブロックを指定する指定ステップとを含むことを特徴とする。
【０００７】指定ステップでは、連続する未使用のブロックの先頭ブロックを特定するための先頭ブロック情報および連続する未使用のブロックの個数を示すブロック数情報を予め格納する管理レジスタが提供する先頭ブロック情報およびブロック数情報を参照して、データを書き込むべき連続する未使用のブロックを指定することが望ましい。
【０００８】書込ステップは、連続する未使用のブロックに隣り合う他の未使用なブロックを包含することにより、新たな連続する未使用のブロックを生成し、ブロックの先頭ブロックの個数情報を書き換えることを備えることが望ましい。未使用のブロックの包含による新たな連続する未使用なブロックの生成は、データを格納すべく指定された連続する未使用のブロックの個数の履歴に応じて実行されること、及び未使用の複数のブロックの分布に応じて実行されることがさらに望ましい。
【０００９】指定ステップでは、連続する未使用のブロックのうち、その先頭または後尾に単独の未使用のブロックの生成を回避して、必要な個数のブロックを指定することが望ましい。
【００１０】また、本発明に係るデータ処理装置は、データを処理すべく、外部からのデータを内部処理のために一時的に格納するためのメモリー領域が複数のブロックに区画されたバッファと、それぞれが対応する各ブロックがデータの格納のために使用されているか否かを表す使用情報が書き換え可能に書き込まれる複数の情報領域から成る管理テーブルとを備えるデータ処理装置であって、それぞれがバッファ及び管理テーブルのために用いられる複数の記憶部を含み、各記憶部のバッファに用いられる領域および管理テーブルに用いられる領域の配置は、各記憶部でそれぞれ互いに同一であることを特徴とする。
【００１１】各記憶部におけるバッファに用いられる領域および管理テーブルに用いられる領域におけるそれぞれのブロックおよび情報領域の配置は、各記憶部でそれぞれ互いに同一であることが望ましい。
【００１２】情報領域は、連続するブロックが使用されている使用状態から未使用状態に変化したときに、連続する未使用のブロックのうちの少なくとも一つのブロックに対応する情報領域に連続するブロックの個数を示す個数情報を書き込まれることが望ましい。
【００１３】さらに、連続するブロックが格納された使用状態から未使用状態に変化したときに、連続するブロックのうちの少なくとも一つのブロックに対応する情報領域に連続する未使用のブロックの個数を示す個数情報を書き込み、かつバッファにデータを書き込むために複数のブロックが必要であると判断されたときに、管理テーブルの情報領域の個数情報に基づいて、書き込むべき連続する未使用のブロックを指定する制御部を含むことが望ましい。
【００１４】
【発明の実施の形態】本発明のバッファ管理方法を使用したデータ処理装置として、具体例のプリンタについて説明する。図１は、具体例のプリンタの構成を示す。プリンタ１は、図１に示されているように、記憶ユニット２、制御ユニット３及びプリンタ機能ユニット４を含む。記憶ユニット２は、プリンタ１に接続されたコンピュータやワークステーション（図示せず）から受信するデータを一時的に格納する。制御ユニット３は、記憶ユニット２およびプリンタ機能ユニット４を制御する。プリンタ機能ユニット４は、印刷に必要な種々の処理を行う。
【００１５】記憶ユニット２は、記憶部２Ａ～２Ｃを有する。記憶部２Ａ～２Ｃは、互いに同一な構成を有することから、説明を簡略にすべく、以下、記憶部２Ａのみを詳述する。記憶部２Ａは、バッファ２０、管理テーブル２１、先頭ブロック管理レジスタ２２及び記憶部管理レジスタ２３を有する。
【００１６】図２は、バッファの構成を示す。バッファ２０は、プリンタ１が受信したデータを格納するために用いられ、図２に示されているように、区画された複数のブロックＢ０～Ｂ３１から構成されている。受信したデータは、１または２以上の、データが格納されていないすなわち未使用のブロックに格納される。データの格納に２以上のブロックを必要とするときには、離散する複数のブロックにデータを分割して格納してもよく、また、連続するブロックに一括して格納してもよい。データの高速処理の観点からは、後者が望ましい。
【００１７】図３は、管理テーブルの構成を示す。管理テーブル２１は、該管理テーブルに対応するバッファ２０の使用状況を管理するために設けられている。管理テーブル２１は、図３に示されているように、バッファ２０のブロックＢ０～Ｂ３１に対応する複数の情報領域ｉ０～ｉ３１から構成されている。
【００１８】図４は、情報領域の構成を示す。各情報領域ｉには、該情報領域に対応するブロックの使用および未使用に拘わらず、当該ブロックについての情報が書き込まれる。すなわち、情報領域ｉには、図４に示されているように、リンク・ポインタＬＰ、ブロック個数ＢＮ、使用／未使用フラグＦＬ、ブロック・アドレスＢＡ、データ・サイズＤＳ及びデータ・ポインタＤＰの各情報が格納されている。
【００１９】リンク・ポインタＬＰは、従来から知られているように、使用中および未使用のそれぞれのブロック同士を関連付けるために用いられる。具体的には、リンク・ポインタＬＰは、相互に離れた位置にある使用中のブロックの検索を容易とすべく、これらのブロックを関連付け、また相互に離れた位置にある未使用のブロックの検索を容易とすべく、これらのブロックを関連付ける。
【００２０】ブロック個数ＢＮは、連続する使用中のブロックの個数または連続する未使用のブロックの個数を示す。連続するブロックの場合、当該ブロックの個数は、少なくとも、その先頭に位置する先頭ブロックに対応する情報領域中のブロック個数ＢＮによって示される。なお、連続しないブロック、すなわち、単独のブロックの場合、ブロック個数ＢＮは、「１」を示す。
【００２１】使用／未使用フラグＦＬ、ブロック・アドレスＢＡおよびデータ・サイズＤＳは、従来知られている機能を果たすべく用いられる。すなわち、使用／未使用フラグＦＬは、当該情報領域に対応するブロックが使用されているか否かを示す。使用されているときには、「使用中」を示し、使用されていないときには、「未使用」を示す。ブロック・アドレスＢＡは、当該情報領域に対応するブロックのアドレスを示す。より具体的には、例えば、当該ブロックの領域が有する複数のアドレスのうち先頭のアドレスを示す。データ・サイズＤＳは、当該情報領域に対応するブロックに格納されているデータの大きさを示す。したがって、プリンタ１が受信したデータが１ブロックより大きいか否かに拘わらず、データ・サイズＤＳは、ブロックの大きさ以下である。
【００２２】データ・ポインタＤＰは、受信データが複数のブロックにまたがって記憶されているときに該ブロックを示す。制御ユニット３は、受信データの先頭部分が記憶されたブロックについての読み出しを行った後、該ブロックのデータ・ポインタＤＰを参照することにより受信データの次の部分が記憶されたブロックについて読み出しを行うというように、データ・ポインタＤＰに従ってブロックからの読み出しを次々に行うことにより、ブロック・サイズより大きい受信データの読み出しを行うことができる。
【００２３】図５は、バッファの使用状態の例を示す。図５において、斜線が施されたブロックは使用中であることを示す。例えば、ブロックＢ８、Ｂ９、Ｂ１３は使用中であり、ブロックＢ０～Ｂ７、Ｂ１０～Ｂ１２、Ｂ１４は未使用であることを示す。
【００２４】図６は、使用中のブロック同士および未使用のブロック同士のそれぞれの関係を示す。先頭ブロック管理レジスタ２２は、該管理レジスタに対応するバッファ２０における使用中のブロックのうち先頭に位置する使用中のブロックおよび未使用のブロックのうち先頭に位置する未使用のブロックを管理するために用いられる。先頭ブロック管理レジスタ２２は、使用中ブロック・ポインタ２２Ａにより、先頭位置にある使用中のブロックを示し、また、未使用ブロック・ポインタ２２Ｂにより先頭位置にある未使用のブロックを示す。
【００２５】図５に示されるバッファ２０の使用状態について、図６に示されているように、使用中ブロック・ポインタ２２Ａは、バッファ２０内の先頭に位置する使用中のブロックである「ブロックＢ８」を示し、ブロックＢ８に対応する情報領域ｉ８中のリンク・ポインタＬＰは、後に続く離れた位置にある使用中のブロックである「ブロックＢ１３」を示し、ブロックＢ１３に対応する情報領域ｉ１３中のリンク・ポインタＬＰは、後に続く離れた位置にある使用中のブロックである「ブロックＢ１５」を示し、ブロックＢ１５に対応する情報領域ｉ１５中のリンク・ポインタＬＰは、後に続く離れた位置にある使用中のブロックである「ブロックＢ２１」を示す。
【００２６】また、ブロックＢ８に対応する情報領域ｉ８中のブロック個数ＢＮは、使用中の２個のブロックＢ８、Ｂ９の存在を表すべく「２」であり、ブロックＢ１３に対応する情報領域ｉ１３中のブロック個数ＢＮは、使用中の１個のブロックＢ１３の存在を表すべく「１」であり、ブロックＢ１５に対応する情報領域ｉ１５中のブロック個数ＢＮは、使用中の２個のブロックＢ１５、Ｂ１６の存在を表すべく「２」である。
【００２７】他方、未使用ブロック・ポインタ２２Ｂは、バッファ２０内の先頭に位置する未使用のブロックである「ブロックＢ０」を示し、ブロックＢ０に対応する情報領域ｉ０中のリンク・ポインタＬＰは、後に続く離れた位置にある未使用のブロックである「ブロックＢ１０」を示し、ブロックＢ１０に対応する情報領域ｉ１０中のリンク・ポインタＬＰは、後に続く離れた位置にある未使用のブロックである「ブロックＢ１４」を示し、ブロックＢ１４に対応する情報領域ｉ１４中のリンク・ポインタＬＰは、後に続く離れた位置にある未使用のブロックＢ１７を示す。
【００２８】また、ブロックＢ０に対応する情報領域ｉ０中のブロック個数ＢＮは、未使用の８個のブロックＢ０～Ｂ７の存在を表すべく「８」であり、ブロックＢ１０に対応する情報領域ｉ１０中のブロック個数ＢＮは、未使用の３個のブロックＢ１０～Ｂ１２の存在を表すべく「３」であり、ブロックＢ１４に対応する情報領域ｉ１４中のブロック個数ＢＮは、未使用の１個のブロックＢ１４の存在を表すべく「１」である。
【００２９】このような使用中ブロック・ポインタ２２Ａ、未使用ブロック・ポインタ２２Ｂおよびリンク・ポインタＬＰにより、使用中または未使用のブロックを容易に検索することができる。また、このようなブロック個数ＢＮにより、ブロックの個数を容易に認識することが可能になる。
【００３０】図７は、記憶部管理レジスタを示す。記憶部管理レジスタ２３は、記憶部２Ａ自身及び記憶部２Ａと記憶部２Ｂとの関係を示すべく、図７に示されているように、未使用ブロック数２３Ａ、使用ブロック数２３Ｂ及び後続記憶部ポインタ２３Ｃを有する。未使用ブロック数２３Ａ及び使用ブロック数２３Ｂは、記憶部２Ａのバッファ２０内のブロックＢ０～Ｂ３１のうち使用中のブロックの個数、及び未使用のブロックの個数をそれぞれ示す。後続記憶部ポインタ２３Ｃは、記憶部２Ａに続く記憶部２Ｂの位置を示す。より具体的には、記憶部２Ｂの領域の先頭のアドレス、すなわち、記憶部２Ｂのバッファ２０のブロックＢ０の先頭のアドレスを示す。
【００３１】記憶部２Ａ～２Ｃが、バッファ２０及び管理テーブル２１の領域をそれぞれ同様に割り当てられ、かつ図７に示される記憶部管理レジスタ２３を備えることから、制御ユニット３は、これらの記憶部２Ａ～２Ｃを何ら管理手順を異にすることなく、単一の管理手順により管理することが可能になる。さらに、例えば、記憶部２Ｃの後段に記憶部２Ａ～２Ｃと同様なバッファ２０、管理テーブル２１、記憶部管理レジスタ２３が割り当てられた記憶部を増設したときには、その記憶部を記憶部２Ａ～２Ｃを管理する手順と同様な手順で管理することが可能になる。
【００３２】図８は、具体例のプリンタのバッファの指定手順を示す。以下、図５のバッファの使用状態の例を前提に、図８に沿って動作を説明する。説明及び理解を容易とすべく、受信したデータを格納するために５個の連続する未使用のブロックが必要である場合を想定する。
【００３３】ステップＳ１００：データの書き込みに必要な個数の未使用ブロックを確保すべく、制御ユニット３は、未使用のブロックを検索する。この未使用ブロックの検索のために、制御ユニット３は、先頭ブロック管理レジスタ２２中の未使用ブロック・ポインタ２２Ｂを参照する。図６に示されるように未使用ブロック・ポインタ２２ＢがブロックＢ０を示すことから、制御ユニット３は、ブロックＢ０がバッファ２０内の最も若いアドレスを有する未使用のブロックであると認識する。
【００３４】制御ユニット３は、次に、管理テーブル２１の対応する情報領域ｉのブロック個数ＢＮを参照する。ブロックＢ０のブロック個数ＢＮが８を示すことから、制御ユニット３は、ブロックＢ０を連続するブロック中の先頭ブロックとする当該連続するブロックの個数が８個であることを認識する。言い換えれば、ブロックＢ０～Ｂ７が未使用であることを知る。
【００３５】ステップＳ１１０：制御ユニット３は、ステップＳ１００で認識したブロックの個数が、データを格納するために必要な個数以上であるか否かを判断する。制御ユニット３は、連続する未使用のブロックＢ０～Ｂ７の個数が８個であり、また、データを格納するために必要なブロックの個数が５個であることから、連続する未使用のブロックＢ０～Ｂ７の個数が、データを格納するために必要なブロックの個数以上であると判断する。
【００３６】ステップＳ１２０：制御ユニット３は、ステップＳ１１０で、連続する未使用のブロックの個数が、データを格納するために必要な個数以上であると判断したとき、その連続する未使用のブロックをデータの格納のためのブロックとして指定する。ここで、制御ユニット３は、連続する８個の未使用のブロックＢ０～Ｂ７のうち、例えば、連続する５個の未使用のブロックＢ０～Ｂ４をデータを格納するためのブロックとして指定し、また、残りの３個のブロックＢ５～Ｂ７を未使用のままに維持する。すなわち、前者のブロック列の先頭ブロックであるブロックＢ０及び後尾のブロックであるブロックＢ４のブロック個数ＢＮを「５」に書き換え、また、後者のブロック列の先頭ブロックであるブロックＢ５及び後尾のブロックであるブロックＢ７のブロック個数ＢＮを「３」に書き換える。
【００３７】ステップＳ１３０：制御ユニット３は、ステップＳ１１０で、連続する未使用のブロックの個数が、データを格納するために必要な個数未満であると判断したとき、例えば、当該連続する未使用のブロックよりも後方に位置する他の連続する未使用のブロックを検索する。すなわち、制御ユニット３は、データを格納するために必要なブロックの個数未満であると判断された連続する未使用のブロックの先頭ブロックのリンク・ポインタＬＰを参照して、当該連続するブロックの後に離れて位置する未使用のブロックを認識し、認識したブロックのブロック個数ＢＮを参照することによりブロックの個数を認識する。
【００３８】データを格納するために必要なブロックの個数以上であると判断したときには、その連続する未使用のブロックをデータの格納のためのブロックとして指定する。他方、データを格納するために必要なブロックの個数未満であると判断したときには、上記と同様に、当該ブロックのリンク・ポインタＬＰを参照することにより、当該ブロックの後に離れて位置するブロックを検索する。
【００３９】このような検索の繰り返しによっても、必要とするブロックの個数以上の未使用のブロックを指定できないときには、制御ユニット３は、必要なブロックの個数未満の個数の連続する未使用のブロックを指定し、かつ不足分に相当する個数の他の未使用のブロックを指定する。
【００４０】なお、データを格納するために必要なブロックの個数以上の連続する未使用のブロックを繰り返し検索することなく、直ちに、必要なブロックの個数未満の未使用のブロック及び不足分の個数の未使用のブロックを検索し、それらのブロックを指定してもよい。
【００４１】ステップＳ１４０：制御ユニット３は、ステップＳ１２０の処理に続いて、ブロックＢ０～Ｂ４の先頭ブロックＢ０及び後尾ブロックＢ４の使用／未使用フラグＦＬをそれぞれ「使用中」に書き換える。また、ブロックＢ５～Ｂ７の先頭ブロックＢ５の使用／未使用フラグＦＬを「未使用」に書き換える。
【００４２】ステップＳ１５０：制御ユニット３は、ステップＳ１４０の処理に続き、受信データを、ブロックＢ０を先頭とするブロックＢ０～Ｂ５に格納することから、使用中ブロック・ポインタ２２Ａを「ブロックＢ０」に書き換え、また、ブロックＢ０のリンク・ポインタＬＰを「ブロックＢ８」に書き換える。さらに、未使用ブロック・ポインタ２２Ｂを「ブロックＢ５」に書き換え、ブロックＢ５のリンク・ポインタＬＰを「ブロックＢ１０」に書き換える。これにより、先頭ブロック管理レジスタ２２及び情報領域ｉは、図１０の状態から図１１の状態へ移行する。
【００４３】図９は、具体例のプリンタのバッファの指定の解除手順を示す。以下、図５に示すバッファの使用状態の例を前提に、図９に沿って動作を説明する。説明及び理解を容易とすべく、図５に示されているように、連続する２個の使用中のブロックＢ８、Ｂ９に格納されたデータが読み出され、それらのブロックＢ８、Ｂ９の指定を解除する必要が生じたことを想定する。
【００４４】ステップＳ２００：制御ユニット３は、指定を解除すべきブロックに続くブロックが使用中か否かを判断する。すなわち、制御ユニット３は、ブロックＢ９の後に続くブロックＢ１０の使用／未使用フラグＦＬを参照して、ブロックＢ１０が使用中か否かを判断する。
【００４５】ステップＳ２１０：指定を解除すべきブロックの後に続くブロックが「未使用」であるときには、制御ユニット３は、当該後に続くブロックのブロック個数ＢＮを参照して、指定を解除すべきブロックと当該後に続くブロックとを連結する。すなわち、制御ユニット３は、ブロックＢ１０のブロック個数ＢＮを参照して、ブロックＢ１０を先頭ブロックとする３個の連続する未使用のブロックＢ１０～Ｂ１２が存在することを認識し、ブロックＢ８、Ｂ９及びブロックＢ１０～Ｂ１２を連結し、これにより、新たに５個の連続する未使用のブロックＢ８～Ｂ１２を生成する。
【００４６】ステップＳ２２０：制御ユニット３は、連結後の新たに生成された連続するブロックの先頭ブロックのブロック個数ＢＮを書き換える。すなわち、制御ユニット３は、先頭ブロックであるブロックＢ８のブロック個数ＢＮを「２」から「５」に書き換え、また、後尾ブロックであるブロックＢ１２のブロック個数ＢＮを「３」から「５」に書き換える。
【００４７】ステップＳ２３０：制御ユニット３は、指定を解除したブロックの使用／未使用フラグＦＬを「未使用」に書き換える。すなわち、制御ユニット３は、ブロックＢ８、Ｂ９の使用／未使用フラグＦＬを「使用中」から「未使用」に書き換える。
【００４８】ステップＳ２４０：制御ユニット３は、連結後の新たに生成された連続するブロックについて、リンク・ポインタＬＰを書き換える。すなわち、制御ユニット３は、「ブロックＢ１０」を示しているブロックＢ０のリンク・ポインタＬＰを「ブロックＢ８」に書き換え、また、ブロックＢ８のリンク・ポインタＬＰの「ブロックＢ１３」を「ブロックＢ１４」に書き換える。この結果、未使用のブロックまたは連続する未使用のブロックの先頭ブロックが、ブロックＢ０、ブロックＢ８、ブロックＢ１４のように関連付けられる。
【００４９】また、制御ユニット３は、使用中ブロック・ポインタ２２Ａを「ブロックＢ１３」に書き換える。この結果、使用中のブロックまたは連続する使用中のブロックの先頭ブロックが、ブロックＢ１３、Ｂ１５、ブロックＢ２１のように関連付けられる。これにより、先頭ブロック管理レジスタ２２及び情報領域ｉは、図１０の状態から図１２の状態に移行する。
【００５０】ステップＳ２５０：制御ユニット３は、ステップＳ２００での判断の結果、後に続くブロックが「使用中」であるときには、制御ユニット３は、ステップＳ２１０の連結やステップＳ２２０のブロックの個数の書き換えを行うことなく、指定を解除すべきブロックの使用／未使用フラグＦＬを「使用中」から「未使用」に書き換える。この結果、ブロックＢ８、Ｂ９の先頭ブロックであるブロックＢ８のブロック個数ＢＮは、「２」に維持される。
【００５１】ステップＳ２６０：制御ユニット３は、ステップＳ２５０で使用／未使用フラグＦＬを書き換えた後、指定を解除すべきブロックについて、リンク・ポインタＬＰを書き換える。すなわち、制御ユニット３は、「ブロックＢ８」を示している使用中ブロック・ポインタ２２Ａを「ブロックＢ８」から「ブロックＢ１３」に書き換え、ブロックＢ８、Ｂ９の前に位置する連続する未使用のブロックＢ０～Ｂ７の先頭ブロックであるブロックＢ０のリンク・ポインタＬＰを「ブロックＢ１０」から「ブロックＢ８」に書き換える。
【００５２】この結果、未使用のブロックまたは連続する未使用のブロックの先頭ブロックが、ブロックＢ０、ブロックＢ８、ブロックＢ１４のように関連付けられる。また、使用中のブロックまたは使用中の連続するブロックの先頭ブロックが、ブロックＢ１０、ブロックＢ１３、ブロックＢ１５のように関連付けられる。これにより、先頭ブロック管理レジスタ２２及び情報領域ｉは、図１３の状態から図１４の状態へ移行する。
【００５３】上述したように、具体例のプリンタでのバッファ管理方法によれば、データを格納するために使用していたブロックＢ８、Ｂ９の指定を解除するときに、連結後の未使用のブロックＢ８～Ｂ１２の個数「５」を、先頭ブロックであるブロックＢ８のブロック個数ＢＮとして書き換え、または、未使用になった連結されないブロックＢ８、Ｂ９の個数「２」を先頭ブロックであるブロックＢ８のブロック個数ＢＮとして維持する。このように、新たに他のデータを格納する必要が生じる前に、連続する未使用のブロックの個数を予め計数し、その個数を記憶しておき、データ格納時に、予め計数されかつ記憶された未使用ブロックの個数を参照することにより、データの格納の必要が生じた後にブロックの個数を計数していた従来のバッファ管理方法に比較して迅速に行うことが可能になる。
【００５４】上述した具体例のバッファ管理方法では、制御ユニット３は、未使用になったブロックＢ８、Ｂ９に連結する未使用のブロックを、前記した後方のブロックＢ１０～Ｂ１２に限らず、その前方のブロックとすることができる。例えば、図５に示す例では、制御ユニット３は、ブロックＢ８、Ｂ９の前に隣接する未使用のブロックＢ０～Ｂ７と連結することが望ましい。制御ユニット３は、この連結により、連続する未使用のブロックＢ０～Ｂ１２を生成する。
【００５５】具体的には、制御ユニット３は、指定を解除すべきブロック列の先頭ブロックの前に位置するブロックの使用／未使用フラグＦＬに基づき、該ブロックが使用中であるか未使用であるかを判断する。さらに、該ブロックのブロック個数ＢＮすなわち、該ブロックを含むブロック列の長さに基づき、該ブロック列の先頭ブロックの位置を得る。制御ユニット３は、さらに、未使用ブロック・ポインタ２２Ｂ及びリンク・ポインタＬＰについて必要な書き換えを行う。
【００５６】すなわち、上記の例では、制御ユニット３は、ブロックＢ７の使用／未使用フラグＦＬを参照することによりブロックＢ７が未使用であることを認識し、次に、ブロックＢ７のブロック個数ＢＮを参照することによりブロックＢ７を後尾ブロックとする８個のブロック、すなわちブロックＢ０～Ｂ７から構成されるブロック列を認識する。制御ユニット３は、さらに、未使用ブロック・ポインタ２２Ｂが示すブロックＢ０と該ブロック列の先頭ブロックＢ０とを比較する。両者が一致することから、ブロックＢ０のリンク・ポインタＬＰを該ブロックＢ０を含むブロック列の後に離れて位置する未使用のブロックであるブロックＢ１４を示すべく「ブロックＢ１４」に書き換え、また、先頭ブロックであるブロックＢ０のブロック個数ＢＮ及び後尾ブロックであるブロックＢ１２のブロック個数ＢＮを「１３」に書き換える。このようにして、先頭ブロック管理レジスタ及び情報領域ｉは、図１２の状態から図１５の状態に移行する。
【００５７】図１６は、先頭ブロック管理レジスタの他の例を示す。図６に示した具体例のバッファ管理方法では、先頭ブロック管理レジスタ２２は、図６に示される使用中ブロック・ポインタ２２Ａおよび未使用ブロック・ポインタ２２Ｂを用いている。図１６に示す例では、使用中ブロック・ポインタ２２Ａを用いることなく、しかも未使用ブロック・ポインタとして、引き続く未使用ブロック個数情報を含む未使用ブロックポインタすなわち連続ポインタが用いられている。図１６に示される連続ポインタは、８個のポインタ、すなわち、８連続ポインタ２２－８～１連続ポインタ２２－１の例を示す。８連続ポインタ２２－８～１連続ポインタ２２－１は、バッファ２０内における連続する未使用ブロック個数毎で、各連続ブロックの先頭ブロックのアドレスが最も若い、８個～１個のそれぞれの連続する未使用のブロックの先頭ブロックを示す。例えば、３連続ポインタ２２－３は、バッファ２０における３個の連続の未使用ブロック群のうち最先に位置する未使用ブロックＢ１０～Ｂ１２の先頭ブロックである「ブロックＢ１０」を示し、さらに、ブロックＢ１０に対応する情報領域ｉ１０中のリンク・ポインタＬＰは、ブロックＢ１０の後の離れた位置にある連続する３個の未使用のブロックＢ２８～Ｂ３０の先頭ブロックである「ブロックＢ２９」を示す。また、１連続ポインタとは、単独のブロックを意味する。また、図１６の管理レジスタで「ＮＵＬＬ」は、連続ポインタのブロック数に該当する未使用ブロックが存在しないことを意味する。
【００５８】制御ユニット３は、例えば、データを格納するために３個の連続する未使用のブロックを必要とするときに、図８のステップＳ１００で、３連続ポインタ２２－３を参照することにより、ブロック列Ｂ１０～Ｂ１２を見つけ出す。このように、図６に示した例におけるような未使用ブロック・ポインタ２２Ｂの参照及びブロック個数ＢＮの参照という２回の参照を行うことなく、３連続ポインタ２２－３の参照という１回の参照を行うだけで、３個の連続する未使用のブロックＢ１０～Ｂ１２を見つけ出すことが可能になることから、ブロックの指定をより迅速に行うことができる。
【００５９】３連続ポインタ２２－３が、３個の連続する未使用のブロックが存在しないことを示す「ＮＵＬＬ」であるときには、制御ユニット３は、順次、４連続ポインタ２２－４および５～８個の連続する未使用のブロックを次々に検索する。
【００６０】このような検索によっても、所望の３～８個の連続する未使用のブロックを見つけ出すことができないときには、制御ユニット３は、さらに、２～１連続ポインタ２２－２～２２－１を順番に参照することにより、所望の総個数の未使用ブロックを確保するために、２～１個の連続する未使用のブロックを検索することが望ましい。
【００６１】ところで、データを孤立する複数の未使用のブロックに分割することは、データの高速処理に好ましくない。特に、未使用のブロックが単独で存在することを回避することが望ましい。そこで、データの格納のためのブロックの指定により他のブロックが孤立するという事態を回避すべく、例えば３個のブロックを確保する必要がある場合、３個の連続する未使用のブロックが存在しないときには、単独の１つの未使用ブロックを生成しないために、４個の連続する未使用のブロックを検索することなく、所望個数よりも２以上大きい個数の連続する未使用のブロック、例えば、５個の連続する未使用のブロックを検索することが望ましい。さらに、５個の連続する未使用のブロックを見つけたときには、当該ブロックの先頭ブロックまたは後尾ブロックから起算して所望の３個のブロックを指定することにより、連続未使用ブロックの両端のそれぞれに単独の未使用ブロックを生成させないために、指定されない２個の未使用のブロックが連続するようにすることが望ましい。
【００６２】図１に沿って説明した具体例のバッファ管理方法では、制御ユニット３は、指定を解除すべきブロックＢ８、Ｂ９に隣接するブロックＢ１０～Ｂ１２が未使用であるときには、それらのブロック同士を連結する。しかし、連結により新たな連続するブロックＢ８～Ｂ１２を生成することがバッファの管理上必ずしも望ましいとは限らない。そこで、制御ユニット３は、例えば、過去に何個の連続する未使用のブロックを指定したかという履歴、または何個のブロックがどのように使用中であるかという現在の使用分布に従って連結すべき否かを判断することが望ましい。以下、これらの履歴及び使用分布について説明する。
【００６３】図１７は、履歴に基づく連結の判断に用いる判断テーブルを示す。判断テーブル３０は、制御ユニット３に設けられており、指定を解除すべきブロックについて連結を行うべきか否か判断するために用いられる。判断テーブル３０は、図１７に示されているように、平均指定ブロック数、残ブロック数及び処理から構成されている。平均指定ブロック数は、データの格納のために過去に指定された所望ブロックの個数の平均を示す。平均指定ブロック数は、具体的には、所定時間内に指定されたブロックの個数の総計をその指定の回数で除算することにより算出される。残ブロック数は、各バッファ２０内の総ブロックＢ０～Ｂ３１の個数に対する、単独および連続の未使用のブロックの個数の割合を示す。処理は、制御ユニット３が、指定を解除されたブロック及び隣接するブロックを連結するか否かであり、これは、指定を解除すべきブロックの個数に左右されない。
【００６４】制御ユニット３は、図９のステップＳ２１０で、連結を直ちに行うことなく、図１７の判断テーブル３０を参照することにより、連結の要否を判断する。ここで、例えば、平均指定ブロック数が「２」であり、残ブロック数が「２９％」であるときには、制御ユニット３は、指定を解除すべきブロックと隣接するブロックとを連結しない。また、平均指定ブロック数が「７」であり、残ブロック数が「５０％」であるときには、制御ユニット３は、指定を解除すべきブロックと隣接するブロックとを連結する。このように、制御ユニット３は、図１７の判断テーブル３０に基づき、指定を解除すべきブロックと隣接するブロックとを連結すべきか否かを判断し、その判断の結果に従って両ブロックを連結しまたは連結しない。したがって、過去に指定されたブロックの個数から判断して必要とする連続個数の蓋然性が高まるほど、その要求を満たすべく連結処理が行われることから、ブロックの指定の解除をより迅速に行うことができる。
【００６５】図１８は、ブロックの使用分布を示す。使用分布３１として、管理テーブル２１の情報領域ｉのブロック個数ＢＮを用いることができる。図５に示すバッファ２０の使用状況下での使用分布が図１８に示されており、ブロックＢ０～Ｂ３１に対応する情報領域ｉ０～ｉ３１中のブロック個数ＢＮは、連続する使用中または未使用のブロックの個数を示す。連続しない、すなわち単独のブロックについては、そのブロック個数は、「１」である。また、ブロック個数ＢＮは、「未使用」を「＋」で表し、「使用中」を「－」で表す。
【００６６】例えば、図５に示されるように、８個のブロックＢ０～Ｂ７が未使用であることから、ブロックＢ０～Ｂ７に対応する情報領域ｉ０～ｉ７中のブロック個数ＢＮは、それぞれ、＋８、＋８、＋８、＋８、＋８、＋８、＋８、＋８を示す。また、２個のブロックＢ８、Ｂ９が使用中であることから、ブロックＢ８、Ｂ９に対応する情報領域ｉ８、ｉ９中のブロック個数ＢＮは、それぞれ、－２、－２を示す。これらのブロック個数ＢＮを用いて、バッファ２０の使用分布を数値で示す分散値を算出する。分散値は、連続するブロックのブロック個数ＢＮの数値とブロックの個数との積を合計することにより得られる。
【００６７】例えば、連続するブロックの最大個数を８個に制限するという条件の下で、ブロックＢ０～Ｂ３１の全てが未使用であるときの分散値は、（８×８）×４＝２５６である。また、図５の使用状態であるバッファ２０の分散値は、図１８に示される数値を用いて、｛（８×８）＋（３×３）＋（１×１）＋（４×４）＋（６×６）＋（３×３）｝－｛（２×２）＋（１×１）＋（２×２）＋（１×１）＋（１×１）｝＝１２３と求めることができる。バッファ２０については、上記のような条件の下に、使用中のブロックと未使用のブロックのばらつき程度が同様であるとき、すなわち、分散値が１００～１５０の範囲にあるときには、連結を行うことが望ましい。
【００６８】制御ユニット３は、図９のステップＳ２１０で、図１８の使用分布３１として機能する管理テーブル２１のブロック個数ＢＮを用いて分散値を算出し、その得られた分散値が１００～１５０の範囲であるか否かに基づき、連結の要否を判断する。このように、ブロックＢ０～Ｂ３１の使用状況を数値で示す分散値を用いて連結の要否を判断することにより不要な連結を回避することが可能になることから、ブロックの指定の解除をより迅速に行うことができる。
【００６９】
【発明の効果】本発明のバッファ管理方法では、前記したように、連続する未使用のブロックが生じたときに、このブロックの個数を示す個数情報を先頭に位置する先頭ブロックに対応する情報領域に書き込み、データを書き込むための連続する複数の未使用のブロックが必要であるときには、予め先頭ブロックに書き込まれた前記個数情報に基づいて、データを書き込むべき連続する未使用のブロックを指定する。したがって、本発明に係る前記管理方法によれば、前記個数情報に基づき未使用ブロックを指定できることから、連続する未使用のブロックの検出を必要とするたび毎に従来のような計数を行う必要はなく、従来に比して、連続する未使用のブロックの指定を迅速に行うことが可能になる。
【００７０】本発明のデータ処理装置によれば、データを一時的に格納するためのバッファのための領域およびバッファの使用状況を示す管理テーブルのための領域が、各記憶部でそれぞれ互いに同一に配置されることから、記憶部の数や位置に左右されることなく、バッファ及び管理テーブルを容易に使用することが可能になる。

【出願人】	【識別番号】５９１０４４１６４【氏名又は名称】株式会社沖データ
【出願日】	平成１２年１０月３日（２０００．１０．３）
【代理人】	【識別番号】１０００８２０５０【弁理士】【氏名又は名称】佐藤幸男
【公開番号】	特開２００２－１０８６９７（Ｐ２００２－１０８６９７Ａ）
【公開日】	平成１４年４月１２日（２００２．４．１２）
【出願番号】	特願２０００－３０３２９６（Ｐ２０００－３０３２９６）