JPH06289838A - フォントキャッシュ制御装置およびその適用方法 - Google Patents

Abstract

(57)【要約】 【目的】ある所要の文字を印字処理して表示するために
用いられる装置において、限られた容量のフォントキャ
ッシュを有効に活用するとともに、当該フォントキャッ
シュにおけるＬＲＵ処理の負荷を軽減させ、その印字処
理を高速に実行することが可能にされたフォントキャッ
シュ制御装置およびその適用方法を提供すること。 【構成】キャッシュバッファおよびキャッシュバッファ
管理データメモリ（４Ｂ）を備えており、キャッシュヒ
ットに対応させてキャッシュバッファ管理データを書き
換えることにより、該キャッシュバッファがフルである
ときの空き領域作成処理に備える処理を行うことが可能
にされたフォントキャッシュ制御装置において、キャッ
シュヒット処理遅延バッファ（４Ｅ），キャッシュヒッ
ト時にキャッシュヒット処理遅延バッファに登録を行う
手段（４Ｃ），および、一括してキャッシュヒット処理
を行う手段（４Ｄ）を含んでなることを特徴とするフォ
ントキャッシュ制御装置およびその適用方法。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明はフォントキャッシュ制
御装置およびその適用方法に関するものであり、特に、
ある所要の文字を印字処理して表示するために用いられ
る装置において、限られた容量のフォントキャッシュを
有効に活用するとともに、当該フォントキャッシュにお
けるＬＲＵ処理の負荷を軽減させ、その印字処理を高速
に実行することが可能にされたフォントキャッシュ制御
装置およびその適用方法に関するものである。

【０００２】

【従来の技術】この種のフォントキャッシュ制御は従来
から次のような手法をもって実施されていた。即ち、 第１処理ステップ：印字すべき文字コードを受け入れ
て、これに対応する文字パターンデータが関連のフォン
トキャッシュに存在するか否かをチェックする。 第２処理ステップ：所要の文字パターンデータが関連の
フォントキャッシュに存在するときには、該文字パター
ンデータが対応の印字処理のために用いられる。 第３処理ステップ：所要の文字パターンデータが関連の
フォントキャッシュに存在しないときには、これに対応
する文字パターンデータの展開を改めて実行する。な
お、このときに、関連のフォントキャッシュに空きがあ
ると、この空きに前記の展開された文字パターンデータ
を格納する。 第４処理ステップ：前記第３処理ステップにおいて関連
のフォントキャッシュに空きがなかった（即ち、当該フ
ォントキャッシュがフルの状態にあった）ときには、該
フォントキャッシュに格納されている文字パターンデー
タの中で最後の参照の時期が最も古いものを消去し、こ
れによって空きにされた領域に前記第３処理ステップに
おいて展開された文字パターンデータを格納する。

【０００３】一般的にいえば、前述の第４処理ステップ
においてはＬＲＵアルゴリズム（対象のフォントキャッ
シュに格納されている文字パターンデータの中で、最後
の参照の時期が最も古いものから消去していく手法）が
適用される。ところで、このようなＬＲＵ処理を厳密に
実行するときには、当該処理の対象になるフォントキャ
ッシュはいわゆる双方向のリスト構造をもって管理され
ることから、最近に参照された文字コードに対応する文
字パターンデータは、前記フォントキャッシュの先頭位
置に移動して格納されることになり、この結果として、
その消去が最も困難なものにされる。そして、このよう
なＬＲＵ処理について認められることは、参照の可能性
が高いものをフォントキャッシュに格納し続けるために
は有効な手法であるということである。しかしながら、
ある所定の１文字を描画する毎に前記のＬＲＵ処理が実
行されるために、例えば比較的短期間に同じ文字が続け
て描画されるような場合等においては、消去される可能
性が全くないＬＲＵ順位にある文字であってもその順位
が順次更新されることになり、その結果として本来の印
字処理の高速化という目標に合わなくなってしまう。

【０００４】例えば、特開平３−４８２８５号公報［文
字処理系におけるフォントキャッシュ制御方式］には、
文字パターンデータを格納すべき領域がなくなった場合
に、それまでに格納されたデータを全て消去する（即
ち、それまでのデータを全て初期化する）ことが従来技
術として記述されており、このような従来技術における
欠点を解消するために、文字パターンデータが格納され
るデータ領域を分割管理して、無駄に消去されるデータ
を少なくすることが提案されている。また、これとは別
の特開平３−４８２８６号公報［文字処理系におけるフ
ォントキャッシュ制御方式］においては、前述された特
開平３−４８２８５号公報におけると同じ従来技術の欠
点を解消するため、文字パターンデータが格納されるべ
きデータ領域がなくなったときに、その格納用の領域の
先頭から消去することが提案されている。ところが、上
記されたいずれのやり方にしても、頻繁に用いられてい
ることが明かな文字パターンデータでも関連のフォント
キャッシュから消去されてしまうことになり、後からの
使用が必要になったときには、消去された文字と同じも
のを改めて展開することが必要になる可能性がある。こ
のために、従来から一般的に用いられているＬＲＵ処理
の手法に比べて、そのヒット率が低下してしまう恐れが
ある。なお、前記されたこの種の技術に関連して、前述
された２件の文献以外に、次のものを参考文献として挙
げることができる。即ち、特開平２−４７０７８号公報
［印刷装置］；特開平２−６３７５９号公報［出力装
置］；特開平３−１１１８９０号公報［出力装置］；お
よび特開平３−１４９６１５号公報［印刷装置］を参考
文献として挙げることができる。これらの文献によれ
ば、フォントキャッシュに格納すべき文字の範囲をホス
ト側から指定する手法がとられている。これらの文献に
開示された技術によれば、出力すべき対象としての文書
に適合した態様で制御をすることが可能であるけれど
も、ホスト側においては、出力すべき文書に合わせて、
格納すべき文字の範囲を頻繁に更新することが必要であ
り、これを怠ると必要な文字がフォントキャッシュに格
納されないという事態が生じる恐れがある。ところで、
別の参考文献である特開平２−２０２４６３号公報［印
刷装置］において提案されている技術的事項は、文字デ
ータを所定の単位（例えば、ページ）をもって受信し、
この所定の単位に含まれている文字毎の出現頻度に基づ
いて、フォントキャッシュに格納すべき文字を定めるこ
とである。しかるに、このようなやり方によるときに
は、文字毎の出現頻度を求めるために施される処理が、
対象とする文字の個数の増加に応じて増大することとな
り、ある所定の単位としてのページに含まれた文字の出
力に続けて、後続のページに含まれた文字の出力までの
無用の待ち時間が生じる可能性がある。更に、この参考
文献においては、格納すべき文字数や種類に対してフォ
ントキャッシュの容量が少ない場合や、出現してくる文
字の順番に関する対応策について、さしたる考慮がなさ
れていない。

【０００５】

【発明が解決しようとする課題】上記された従来のこの
種の技術には次のような問題点があった。即ち、対象の
フォントキャッシュに文字パターンデータの格納のため
の空きスペースがないときに一般的に適用されているＬ
ＲＵアルゴリズムによれば、参照の可能性が高いものを
該フォントキャッシュに継続して格納しておくことは有
効であるけれども、ある所定の１文字を描画する毎に前
記のＬＲＵアルゴリズムに基づく処理が実行されるため
に、消去される可能性が全くないＬＲＵ順位にある文字
であってもその順位が順次更新される場合があり、その
結果として本来の印字処理の高速化という目標に合わな
くなるという問題点があった。また、別に提案された事
項として、［１］文字パターンデータを格納すべき領域
がなくなった場合に、文字パターンデータが格納される
データ領域を分割管理することにより、無駄に消去され
るデータを少なくすること；および、［２］同じく文字
パターンデータを格納すべき領域がなくなった場合に、
その格納用の領域の先頭から消去すること；があるが、
このいずれのやり方にしても、頻繁に用いられているこ
とが明かな文字パターンデータでも関連のフォントキャ
ッシュから消去されてしまうことになり、後からの使用
が必要になったときに、消去された文字と同じものを改
めて展開することが必要になる可能性があることから、
前記従来より一般的に用いられているＬＲＵ処理の手法
に比べてヒット率が低下する恐れがあるという問題点が
あった。

【０００６】この発明は上記された問題点を解決するた
めになされたものであって、ＬＲＵ遅延処理用のバッフ
ァを設けておくことにより、フォントキャッシュにヒッ
トしたときには対応のＬＲＵ処理を遅延させることが可
能にされ、また、当該バッファがフルになったり、フォ
ントキャッシュにミスヒットしたりして、該フォントキ
ャッシュから消去すべき候補の選択のために必要が生じ
たときにＬＲＵ処理を実行するようにされ、ＬＲＵ遅延
処理中に複数回ヒットした文字コードに対するＬＲＵ処
理を１回で行うことができるようにされて、無駄なＬＲ
Ｕ処理の実行回数を減少させるとともに、その印字性能
を大幅に向上させることを目的とするものである。ま
た、同様にＬＲＵ遅延処理用のバッファを設けておくこ
とにより、フォントキャッシュにミスヒットしたときに
該フォントキャッシュから消去すべき候補の選択とその
消去のための処理とを遅延させて、当該バッファがフル
になるまで処理を進めることが可能になり、ヒットしな
かった文字の文字パターンを格納するための領域確保の
ために、近い将来において再使用される可能性のある文
字パターンが消去されてしまうことを防止することによ
り、その印字性能を大幅に向上させることをも目的とす
るものである。

【０００７】

【課題を解決するための手段】この発明は上記の目的を
果たすためになされたものであり、この発明に係るフォ
ントキャッシュ制御装置は、キャッシュバッファおよび
キャッシュバッファ管理データメモリ（４Ｂ）を備えて
おり、キャッシュヒットに対応させてキャッシュバッフ
ァ管理データを書き換えることにより、該キャッシュバ
ッファがフルであるときの空き領域作成処理に備える処
理を行うことが可能にされたフォントキャッシュ制御装
置において、キャッシュヒット処理遅延バッファ（４
Ｅ）と、キャッシュヒット時にＬＲＵ処理遅延バッファ
に登録を行う手段（４Ｃ）と、一括してキャッシュヒッ
ト処理を行う手段（４Ｄ）とを含んでなることを特徴と
するものである。この発明に係る別のフォントキャッシ
ュ制御装置は、キャッシュバッファ管理データには予約
フラグが含まれており、キャッシュヒット処理遅延バッ
ファに登録を行う手段（４Ｃ）は同時に予約フラグをセ
ットするものであり、一括してキャッシュヒット処理を
行う手段（４Ｄ）はその処理に対応させて予約フラグを
リセットし、キャッシュバッファがフルであるときの空
き領域作成処理は、予約フラグのセットされていないデ
ータエントリのみを消去の対象とすることを特徴とする
ものである。この発明に係る更に別のフォントキャッシ
ュ制御装置は、キャッシュバッファ、キャッシュバッフ
ァ管理データメモリ（４Ｂ）および出力バッファを備え
ており、要求されたデータ識別子別に対応するデータを
出力バッファに書き込むようにされた、フォントキャッ
シュ制御の機能が随伴されるデータ出力装置のためのフ
ォントキャッシュ制御装置であって、データのキャッシ
ングを行う際にキャッシュバッファ管理データを参照し
て必要なデータの有無を判断する手段（４Ａ）と、キャ
ッシュヒット時にはキャッシュにあるデータを出力バッ
ファに書き込む手段（４Ｄ）と、キャッシュミスヒット
処理遅延バッファ（４Ｈ）と、キャッシュミスヒット時
にはキャッシュミスヒット処理遅延バッファに登録する
手段（４Ｃ）と、一括してキャッシュミスヒット処理
（データの入力、展開や出力バッファへの書き込み）を
行う手段（４Ｇ）とが含まれてなることを特徴とするも
のである。

【０００８】

【作用】この発明に係るフォントキャッシュ制御装置
は、付属のキャッシュバッファがフルであるときの空き
領域を効率的に作成できるようにされており、キャッシ
ュヒットが生じたときに対応する処理を遅延させるため
の手段であるキャッシュヒット処理遅延バッファと、前
記キャッシュヒットが生じたときにその旨を登録してお
くための手段である（ＬＲＵ）処理遅延バッファ登録部
と、前記のように登録されたものを一括してキャッシュ
ヒット処理を行うための手段とを含んでなることを特徴
とするものである。このような特徴をもって構成された
この発明に係るフォントキャッシュ制御装置によれば、
キャッシュバッファに空き領域を生成させるべき時点の
例えば直前において、必要なキャッシュヒット処理を一
括して行うことが可能となり、それだけ当該装置の使用
効率が向上するという利点がもたらされる。また、この
発明に係る別のフォントキャッシュ制御装置において
は、キャッシュバッファ管理データに含まれる予約フラ
グのセットは、キャッシュヒット処理遅延バッファに登
録を行う手段によって実行されること、一括して行われ
るキャッシュヒット処理に対応して前記予約フラグのリ
セットが実行されること、および、キャッシュバッファ
がフルであるときの空き領域作成処理は、該予約フラグ
がセットされていないデータエントリだけを消去の対象
として選択・実行されることを特徴とするものである。
このような特徴をもって構成されたこの発明に係る別の
フォントキャッシュ制御装置によれば、例えば通常のＬ
ＲＵ処理では消去の候補にされてしまうものであって
も、前記の予約フラグが立てられたものは当該消去の候
補から外されることになり、将来に必要となりそうなも
のが無駄に消去されてしまうという危険性が軽減される
という利点がある。そして、この発明に係る更に別のフ
ォントキャッシュ制御装置は、フォントキャッシュ制御
の機能が随伴されるデータ出力装置のためのフォントキ
ャッシュ制御装置であって、データのキャッシングを行
う際にキャッシュバッファ管理データを参照して必要な
データの有無を判断すること、キャッシュヒットが生じ
た時にはキャッシュに存在するデータを出力バッファに
書き込むこと、キャッシュミスヒットが生じた時にはそ
の旨をキャッシュミスヒット処理遅延バッファに登録す
ること、および、前記のように生じたキャッシュミスヒ
ットについて、一括して該当のキャッシュミスヒット処
理（データの入力、展開や出力バッファへの書き込み）
を実行することが含まれてなることを特徴とするもので
ある。このような特徴をもって構成されたこの発明に係
る更に別のフォントキャッシュ制御装置によれば、キャ
ッシュミスヒットが生じる度に対象とするフォントに必
要な展開処理等を施すことがなくなり、必要なキャッシ
ュミスヒット処理を一括して行うことが可能となり、そ
れだけ当該装置の使用効率が向上するという利点がもた
らされる。

【０００９】

【実施例】図１は、この発明の実施例であるフォントキ
ャッシュ制御装置を中心とする概略的な構成を例示する
ブロック図である。この図１において、文字コード入力
受付装置１は、例えば外部適所に設けられたホスト装置
（図示されない）から伝送される所要の文字コード入力
を受け付けるためのものである。展開用文字データ記憶
装置２は、例えば大容量低速動作型の記憶装置であって
もよく、展開のために用いられる文字データ（情報）が
格納されている。文字パターン展開装置３は、前記展開
用文字データ記憶装置２から取り出された文字データ
（情報）について、対応の文字パターンに展開するため
のものである。フォントキャッシュ制御装置４はこの発
明の中心的な装置であり、これについては、図２を参照
しながら後述する。フォントキャッシュ５は、小容量高
速動作型の記憶装置あればよく、過去において展開され
た文字コードに対応する文字パターンデータが、その容
量分だけ記憶されるものである。文字出力用ページバッ
ファ６は、文字パターン展開装置３またはフォントキャ
ッシュ５からの文字パターンデータに基づく出力イメー
ジが、フォントキャッシュ制御装置４の制御下で出力す
るためにページ単位で一時的に格納されるものである。
そして、文字出力装置７は、前記文字出力用ページバッ
ファ６において所要の処理・格納がなされているページ
単位の出力イメージが、可視的に出力・表示されるもの
である。

【００１０】図２は、前記図１における中心的な装置で
あるフォントキャッシュ制御装置４の構成例示図であ
る。この図２において、キャッシュバッファ管理部４Ａ
は、フォントキャッシュ５（図１）における文字パター
ンデータについて、作成・登録・格納・削除等の種々の
管理業務を負担するものである。キャッシュバッファ管
理データメモリ４Ｂは、前記フォントキャッシュ５の管
理業務を遂行するために必要な各種のデータを格納して
いるものであり、例えば、後述されるような予約フラグ
等がここに含まれている。処理遅延バッファ登録部４Ｃ
は、ヒットやミスヒットが生じたキャッシュについて、
対応の処理を遅延させるべきものが登録されるものであ
る。データ入出力部４Ｄは、フォントキャッシュ５と文
字出力用ページバッファ６（図１）とを仲介するもので
あり、前者であるフォントキャッシュ５において選択さ
れたある所定の文字パターンデータを受け入れて、後者
である文字出力用ページバッファ６に向けて出力させる
ものである。キャッシュヒット一括処理部４Ｅは、ヒッ
トが生じたキャッシュにおける複数の同じ文字パターン
データについて、必要な処理を一括して施すものであ
る。キャッシュヒット処理遅延バッファ４Ｆは、ヒット
が生じたキャッシュにおける複数の同じ文字パターンデ
ータについて、後での一括処理のために一時的に格納し
ておくものである。キャッシュミス一括処理部４Ｇは、
ミスヒットが生じたキャッシュにおける複数の同じ文字
パターンデータについて、必要な処理を一括して施すも
のである。そして、キャッシュミス処理遅延バッファ４
Ｈは、ミスヒットが生じたキャッシュにおける複数の同
じ文字パターンデータについて、後での一括処理のため
に一時的に格納しておくものである。

【００１１】図３は、上記実施例において用いられるＬ
ＲＵ遅延処理バッファ２０の構成例示図である。この図
３において、ＬＲＵ遅延処理バッファ２０には複数個の
ポインタ格納部２１が設けられており、それぞれのポイ
ンタ格納部２１に格納されたポインタは、ＬＲＵ遅延処
理が実行されている文字パターンデータが格納されたフ
ォントキャッシュ５（図１）に対するものである。この
ＬＲＵ遅延処理バッファ２０において管理することがで
きる文字数は、通常は上記実施例において用いられるメ
モリ資源の大きさ等を考慮して定まるものであるが、前
記フォントキャッシュ５のエントリ数と同じであるか、
または、これよりも少数であるようにすることが好適で
ある。

【００１２】図４は、上記実施例におけるフォントキャ
ッシュ５を管理するために用いられるＬＲＵ管理用エン
トリ３０のデータ構造の例示図である。この図４におい
て、前記ＬＲＵ管理用エントリ３０は、フォントキャッ
シュ５に格納される文字パターンに対応する文字情報
（例えば、文字コード）格納部３１；ＬＲＵ管理用の前
方ポインタ格納部３２；ＬＲＵ管理用の後方ポインタ格
納部３３；該当の文字パターンデータに対するポインタ
格納部３４；および、ＬＲＵ処理識別子格納部３５；か
ら構成されている。ここに、ＬＲＵ処理識別子とはＬＲ
Ｕ更新処理中にＬＲＵリストの順位を更新したエントリ
にセットする値であり、ある所定の１サイクルのＬＲＵ
更新処理を行うのに先だって更新されるものである。こ
れは、あるサイクルのＬＲＵ更新処理で更新されたエン
トリと別のサイクルで更新されたエントリを識別する排
他的な値である。このようなＬＲＵ処理識別子として
は、例えば、十分に大きい範囲の整数を１ずつ増加させ
るものを採用することもできる。

【００１３】図５は、上記実施例において、ハッシュテ
ーブル４１で管理されるＬＲＵ管理用エントリ（３０Ａ
〜３０Ｃ）と対応の文字パターンデータ（４３Ａ〜４３
Ｃ）およびＬＲＵ遅延処理バッファ２０の間の関係に関
する例示図である。なお、ここでのハッシュテーブルと
は、例えばある所定の文字コード等をキーとして、当該
キーと格納されている可能性のあるエントリとを対応付
けるためのテーブルであって、それらの対応付けは、通
常ハッシュ関数と呼ばれる所定の計算式によってなされ
る。例えば、文字［Ａ］が文字コード４０に相当してい
るとして、対応するエントリは該テーブルの４０番目に
あるというように、実際に４０番目に文字［Ａ］が登録
されていれば［ヒット］，これが登録されていなければ
［ミスヒット］等の判定をするようにされる。そして、
ここでのハッシュテーブルは、キャッシュのヒット／ミ
スヒットを判定するための補助的なデータ構造をとるよ
うにされており、同様な機能を果たすものが提供可能で
あれば、このハッシュテーブルに限られるものではない
が、一般的には、上記のような目的のために、この種の
ハッシュテーブルが多用されている。そして、ここでの
ハッシュテーブル自体は、対応付けがなされたキャッシ
ュエントリを指し示すポインタの集合されたものであ
る。この図５において、フォントキャッシュエントリ
（ＬＲＵリスト）に相当するＬＲＵ管理用エントリ（３
０Ａ〜３０Ｃ）は、キャッシュミスの際の消去候補エン
トリを双方向のリスト構造をもって管理している。消去
候補エントリのリストはＬＲＵアルゴリズムで管理され
ており、フォントキャッシュに格納されている文字パタ
ーンが参照されたものが、その参照時期の新→古の順序
で連結されている。即ち、最近参照された文字（文字パ
ターンデータ４３Ａに対応するもの）は、ＬＲＵ管理先
頭エントリへのポインタ３２Ａによってリストの先頭に
されており、また、参照の時期が最も古いもの（文字パ
ターンデータ４３Ｃに対応するもの）は、ＬＲＵ管理最
終エントリへのポインタ３３Ａによって消去候補に指定
されている。この図５においては、ＬＲＵ遅延処理バッ
ファ２０に登録された上下２個のキャッシュエントリが
単一のキャッシュエントリを指定するようにされてい
る。即ち、ある同一の文字を指定するようにされてい
る。また、この図５で示されている文字パターンデータ
格納領域４３は、機能的には前記図１におけるフォント
キャッシュ５に対応するものである。

【００１４】図６は、上記実施例における動作の説明に
用いられる出力文書５０の例示図である。そして、この
図６における出力文書５０には次のような文章が記載さ
れている。［近年における電子技術の進歩は、既存通信
メディアの普及・発展に大きな役割を果たすとともに、
社会・経済活動などの周辺環境の進展に伴う多種多様な
新しい通信に対する需要に応じ、多様な発展を遂げてき
た。これは、］

【００１５】図７は、上記実施例における動作の説明に
用いられる例示図である。この図７は、前記図５を簡略
化して示したものであって、ハッシュテーブル４１は省
略されており、ある所定の桁数（ここでは１０桁である
が、実際にはこれよりも多くされる）のＬＲＵ遅延処理
バッファ２０とある一定数のキャッシュエントリ（ＬＲ
Ｕリスト）６１とから構成されている。ここでのキャッ
シュエントリ６１は、前記図５においてリスト構造にさ
れているＬＲＵ管理用エントリ（３０Ａ〜３０Ｃ）に対
応するものである。そして、この図６で示された状態に
おいては、前記図１のフォントキャッシュ５に対応する
文字パターンデータ格納領域４３は既にフルの状態にあ
り、「［な］［ど］［周］・・・［の］［進］［展］」
のような文字に対応する文字パターンデータがフルに格
納されている。

【００１６】図８は、上記実施例における動作の説明に
用いられる別の例示図である。この図８においては、
［な］［ど］［の］［周］［辺］［環］［境］［の］
［進］［展］の都合１０文字分がＬＲＵ遅延処理バッフ
ァ２０を満たすように格納されている。そして、ここで
の１０文字分の文字パターンはキャッシュにヒットして
おり、特に、［の］に対応する文字パターンは連続して
ヒットしていることが示されている。

【００１７】図９は、上記実施例における動作の説明に
用いられる別の例示図である。この図９においては、前
記図８に示された状態から後でヒットしない文字パター
ンが出現して、所要のＬＲＵ処理を施すようにされてい
る。ここでは、３文字分のＬＲＵリスト６１が更新され
て、それぞれのキャッシュエントリのＬＲＵ処理識別子
も更新されたことが示されている。なお、このことは、
図９におけるＬＲＵリスト６１の右側からみて３個にシ
ェードを施すことによって示されている。

【００１８】図１０は、上記実施例における動作の説明
に用いられる別の例示図である。この図１０において
は、先頭から７文字分についてのＬＲＵ処理が完了した
ときの、ＬＲＵ遅延処理バッファ２０に登録・格納され
た８番目の文字［の］に関する処理の態様が示されてい
る。ここでは、登録・格納されたエントリ（ＬＲＵリス
ト６１に含まれているもの）のＬＲＵ処理識別子が現在
のサイクルのものと一致していることから、ＬＲＵリス
ト６１の更新は実行されない。ここで、［ＬＲＵ処理識
別子が現在のサイクルのものと一致している］とは、一
連のＬＲＵ遅延処理バッファの後処理で、そのキャッシ
ュエントリが既にＬＲＵリスト上でＬＲＵ処理がなされ
ていることを示すものである。ここでの例においては、
文字［の］は２回ＬＲＵ処理が施される可能性があるけ
れども、その２回目の処理は必要とされない。このよう
なことを判定するために、その１回目の処理の際にＬＲ
Ｕ識別子を更新して、必要な処理が既に施されたことを
示すようにされる。ここでのＬＲＵ識別子は、一通りの
ＬＲＵ遅延処理バッファの後処理が終了し、また、ＬＲ
Ｕ遅延処理が行われて後処理が再度開始された時点では
別の値をとるものであり、このために上記のような処理
が可能になる。

【００１９】図１１は、上記実施例における動作の説明
に用いられる別の例示図である。この図１１には、ある
所定の１サイクルのＬＲＵ処理が完了した（即ち、ＬＲ
Ｕ遅延処理バッファ２０がクリアされた）ときの状態が
示されている。即ち、対応のＬＲＵリスト６１が更新さ
れ、キャッシュミスが生じた文字のための消去候補エン
トリ順番が確定された状態が示されている。このように
順番が確定してからキャッシュのミスヒットが連続して
生起したときには、該リストにおいて確定された順番に
よって消去候補エントリが消去されていくことになる。

【００２０】図１２は、上記実施例の動作を説明するた
めのフローチャートであって、前記図７の状態から前記
図６に例示された文書を出力させることを説明するため
のものである。この図１２において、 Ｓ１：印字すべき文字コードの取り出し；まず、ＬＲＵ
遅延処理バッファ２０がフルの状態にあるか否かのチェ
ックがなされる。そして、このＬＲＵ遅延処理バッファ
２０がフルの状態にはないとされたときには、印字対象
としての文字コードを取り出して、キャッシュヒット／
キャッシュミスのいずれであるかの判定処理がなされ
る。ここで、［１］キャッシュヒットであると判定され
たときには、Ｓ２，Ｓ３の処理がなされる。これに対し
て、［２］キャッシュミスであると判定されたときに
は、［２Ａ］ＬＲＵ遅延処理バッファ２０に登録された
エントリが存在するときにはＳ４以降の処理がなされ、
また、［２Ｂ］ＬＲＵ遅延処理バッファ２０に登録され
たエントリが存在しないときにはＳ１０以降の処理がな
されることになる。 Ｓ２：前記Ｓ１においてキャッシュヒットが生じたと
き；フォントキャッシュ５（文字パターンデータ格納領
域４３）においてヒットが生じたキャッシュエントリ
（ＬＲＵ管理用エントリ３０Ａ〜３０Ｃにおいて対応す
るもの）がＬＲＵ遅延処理バッファ２０に登録される。 Ｓ３：エントリから文字パターンを得て、ページバッフ
ァ側にコピーする；関連のキャッシュエントリから対応
する文字パターンを得て、これをページバッファ（文字
出力用ページバッファ６：図１を参照）側にコピーす
る。ここで、更に処理すべき文字があるか否かのチェッ
クを行い、ＬＲＵ遅延処理バッファ２０がフルの状態に
なるか、または、フルの状態になるのに先だってキャッ
シュミスが生じたときには、フォントキャッシュ内の文
字に対してＬＲＵ更新処理を施すために、Ｓ４以降また
はＳ１０以降の処理がなされる。 Ｓ４：前記Ｓ１においてキャッシュミスが生じ、また
は、出力すべき文字がなくなって、ＬＲＵ遅延処理バッ
ファに登録されたエントリがある場合、もしくは、ＬＲ
Ｕ遅延処理バッファがフルの状態になった場合には、Ｌ
ＲＵ識別子について所定の更新がなされる。 Ｓ５：ＬＲＵ遅延処理バッファに最後に登録されたエン
トリが選択される；ここで認められるように、該ＬＲＵ
遅延処理バッファ２０に登録された順番とは逆の順番で
該当のエントリに対するＬＲＵ処理が施されることにな
る。 Ｓ６：バッファに登録されたキャッシュエントリが選択
される；ＬＲＵ遅延処理バッファ２０に登録されたキャ
ッシュエントリにおける所定のものが選択される。ここ
では、該キャッシュエントリのＬＲＵ処理識別子につい
て、前記Ｓ４において更新されたものと一致するか否か
のチェックがなされる。そして、一致しているとされた
ときには、該エントリは対応のＬＲＵ処理サイクルで既
に所要のＬＲＵ処理が行われており、このＬＲＵ処理を
再度実行することは不要である。これに対して、一致し
ていないとされたときには、所要のＬＲＵ処理を施すた
めに以下のＳ７およびＳ８に移行するようにされる。 Ｓ７：現在のエントリをＬＲＵリスト６１の先頭に移動
させる。 Ｓ８：該エントリのＬＲＵ処理識別子を前記Ｓ４におい
て変更されたものに書き換える。 Ｓ９：前記Ｓ８の処理に続けて、ＬＲＵ遅延処理バッフ
ァ２０における次続のエントリを選択するようにされ
る。これ以降は、前記ＬＲＵ遅延処理バッファ２０に登
録されたエントリが存在するときには、先のＳ６からの
作業が繰り返される。これに対して、前記登録されたエ
ントリが存在せず、キャッシュミスをトリガとするＬＲ
Ｕリスト６１の更新をしているときには、キャッシュミ
スが生じた文字に関する展開処理をするために前記Ｓ１
０以降の処理を実行する。これ以外のときには、ＬＲＵ
遅延処理バッファ２０のＬＲＵ処理が完了したとしてＳ
１５における処理の実行がなされる。 Ｓ１０：ＬＲＵリスト６１における消去候補としてのエ
ントリが選択される。 Ｓ１１：前記Ｓ１０で選択されたエントリに登録されて
いる文字パターンが消去される。 Ｓ１２：前記文字パターンが消去されたエントリに対応
する領域を用いて、必要とする文字に対応するパターン
の展開処理が実行される。 Ｓ１３：前記展開された文字パターンを管理しているエ
ントリが、ＬＲＵリスト６１の先頭に移動される。 Ｓ１４：前記展開された文字パターンを得て、これをペ
ージバッファ側にコピーする。ここで、Ｓ１０からＳ１
４までの処理は、通常のフォントキャッシュミスが生じ
たときに施されるものである。キャッシュヒットに失敗
した文字を対応の文字パターンに展開するためには、当
該文字パターンの展開をするための領域が必要であり、
この領域を確保するためにＬＲＵリスト６１における消
去候補エントリが選択されることになる。 Ｓ１５：必要な処理が完了したＬＲＵ遅延処理バッファ
２０に関する管理情報（例えば、該バッファに格納され
ている文字数に関する情報）がクリアされる。

【００２１】ここで、上記実施例において用いられた１
００文字の文章例（図６の［近年における電子技術の進
歩は、既存通信メディアの普及・発展に大きな役割を果
たすとともに、社会・経済活動などの周辺環境の進展に
伴う多種多様な新しい通信に対する需要に応じ、多様な
発展を遂げてきた。これは、］）について、文字毎の出
現回数を［に：６回］，［の：４回］，［進：２回］，
［は：２回］，・・・のようにカウントしていくと、こ
の１００文字の文章例における１７種の文字が複数回出
現しており、その総数は４５文字分に相当することが認
められる。そして、残りの５５文字分は１回だけ出現し
ている。ここで、前記複数回出現している４５文字中の
１７文字分は、その１回目の出現において展開処理を受
けることが必要であり、残りの（４５−１７＝２８）２
８文字分はキャッシュヒットの際の利点を受ける可能性
がある。即ち、上記の例文において、句読点を含む１０
０文字の中で同じ文字が出現する回数は２８回であり、
それらについては、前述されたような利点を受ける可能
性があることになる。いま、キャッシュのヒット率が例
えば９５％であるとすると、キャッシュミスの発生は平
均的には２０文字に対して１回であることになるが、前
記の文章例では、２０文字以内で同じ文字が出現する
（前記の文章例において、例えば、最初の［の］に続け
て１３文字目に同じ［の］が出現している）回数は１０
回あることが認められる。従って、このような文章例に
ついてこの発明の実施例を適用するときには、従来のこ
の種の技術に比べて、ＬＲＵリストの更新処理の回数を
ほぼ１０％削減することができる。なお、数字やアルフ
ァベットが多用される文章についてみれば、例えば、社
員名簿の中には数字が多用されるものがあり［例：氏
名：富士ＸＸＸ 社員 Ｎｏ． １１０２３ １９６１年
１０月２０生］、この例では［１］や［０］が多用され
ることや、英文において［ｅ］なる英文字が頻繁に用い
られることのために、前記の削減率を更に向上させるこ
とが可能になることがある。ここで、［Ｔｈｅ ｍａｎ
ｉｓ ｖｅｒｙ ｋｉｎｄ．］なる英文を例にとる
と、ここでの同じ文字の出現について、［ｅ：２回（７
文字目に出現）］，［ｎ：２回（９文字目に出現）］，
［ｉ：２回（７文字目に出現）］，であることが認めら
れる（ただし、スペースは無視）。

【００２２】図１３は、この発明の（予約フラグが適用
される）別の実施例において用いられるＬＲＵ遅延処理
バッファ２０の構成例示図である。この図１３におい
て、ＬＲＵ遅延処理バッファ２０には、複数個の文字描
画情報格納部１２Ａと、これらに個々に対応するポイン
タ格納部１２Ｂとが含まれており、前者である文字描画
情報格納部１２Ａに含まれている情報は、所要の遅延処
理が行われている文字を描画するために必要な情報（例
えば、ある所定のページバッファ上への書き込み位置に
関する情報）であり、また、それぞれのポインタ格納部
１２Ｂに格納されたポインタは、対応のフォントキャッ
シュ内のエントリに対するものである。このＬＲＵ遅延
処理バッファ２０において管理することができる文字数
は、通常は上記別の実施例におけるメモリ資源の大きさ
等を考慮して定められるが、前記フォントキャッシュの
エントリ数と同じであるか、または、これよりも少数で
あるようにされる。

【００２３】図１４は、上記別の実施例におけるフォン
トキャッシュ５を管理するために用いられるＬＲＵ管理
用エントリ３００のデータ構造の例示図である。この図
１４において、前記ＬＲＵ管理用エントリ３００は、フ
ォントキャッシュ５に格納される文字パターンに対応す
る文字情報（例えば、文字コード）格納部３１；ＬＲＵ
管理用の前方ポインタ格納部３２；ＬＲＵ管理用の後方
ポインタ格納部３３；該当の文字パターンデータに対す
るポインタ格納部３４；および、予約フラグ格納部３５
Ａ；から構成されている。ここに、予約フラグとは、近
い将来に用いる可能性がある文字パターンデータについ
て、その使用の予約をするためのものである。

【００２４】図１５は、上記別の実施例において、ハッ
シュテーブル４１で管理されるＬＲＵ管理用エントリ
（３００Ａ〜３００Ｃ）と対応の文字パターンデータ
（４３Ａ〜４３Ｃ）および（ＬＲＵ）遅延処理バッファ
２０の間の関係に関する例示図である。なお、ＬＲＵ管
理用エントリ３００Ａ，３００Ｂにおいてシェードが付
された部位は、予約フラグがセットされた状態にあるこ
とを示している。この図１５において、フォントキャッ
シュエントリ（ＬＲＵリスト）に相当するＬＲＵ管理用
エントリ（３００Ａ〜３００Ｃ）は、キャッシュミスの
際の消去候補エントリを、双方向のリスト構造をもって
管理している。消去候補エントリのリストはＬＲＵアル
ゴリズムで管理されており、フォントキャッシュに格納
されている文字パターンが参照されたものが、その参照
時期の新→古の順序で連結されている。即ち、最近参照
された文字（文字パターンデータ４３Ａに対応するも
の）は、ＬＲＵ管理先頭エントリへのポインタ３２Ａに
よってリストの先頭にされており、また、参照の時期が
最も古いもの（文字パターンデータ４３Ｃに対応するも
の）は、ＬＲＵ管理最終エントリへのポインタ３３Ａに
よって消去候補に指定されている。なお、この図１５で
示されている文字パターンデータ格納領域４３も、機能
的には前記図１におけるフォントキャッシュ５に対応す
るものである。

【００２５】図１６は、上記別の実施例における動作の
説明に用いられる例示図である。この図１６は、前記図
１５を簡略化して示したものであって、ハッシュテーブ
ル４１は省略されており、ある所定の桁数（ここでは３
桁にされている）の（ＬＲＵ）遅延処理バッファ２０と
ある一定数のキャッシュエントリ（ＬＲＵリスト）６１
とから構成されている。ここでのキャッシュエントリ６
１は、前記図１５においてリスト構造にされているＬＲ
Ｕ管理用エントリ（３００Ａ〜３００Ｃ）に対応するも
のである。そして、この図１６で示された状態におい
て、前記図１のフォントキャッシュ５に対応する文字パ
ターンデータ格納領域４３には、「［序］［に］［年］
［ ］・・・［ ］」のような文字に対応する文字パタ
ーンデータが格納されている。

【００２６】図１７は、上記別の実施例における動作の
説明に用いられる別の例示図である。この図１７におい
ては、［近］なる１文字がＬＲＵ遅延処理バッファ２０
に格納されている。そして、この場合における［近］の
文字パターンはキャッシュにヒットしておらず、対応の
文字情報だけがＬＲＵ遅延処理バッファ２０に登録され
ることになる。

【００２７】図１８は、上記別の実施例における動作の
説明に用いられる別の例示図である。この図１８におい
ては、前記図１７に示された状態に続けて、文字［年］
について所要のＬＲＵ処理を施すようにされている。こ
の場合における［年］の文字パターンはキャッシュにヒ
ットしており、このために、対応の文字情報およびキャ
ッシュエントリがＬＲＵ遅延処理バッファ２０に登録さ
れるとともに、対応のエントリに対する予約フラグのセ
ットがなされることになる。なお、この予約フラグのセ
ットについては、図１８におけるＬＲＵリスト６１の左
側からみて４番目にシェードを施すことによって示され
ている。

【００２８】図１９は、上記別の実施例における動作の
説明に用いられる別の例示図である。この図１９におい
ては、前記図１８に示された状態に続けて、文字［に］
について所要のＬＲＵ処理を施すようにされており、ま
た、この状態においてＬＲＵ遅延処理バッファ２０がフ
ルにされている。この場合における［に］の文字パター
ンもキャッシュにヒットしているため、前記の文字
［年］の場合と同様に、対応の文字情報およびキャッシ
ュエントリがＬＲＵ遅延処理バッファ２０に登録される
のに加えて、対応のエントリに対する予約フラグがセッ
トされる。なお、この予約フラグのセットについては、
図１９におけるＬＲＵリスト６１の左端（ここは、本来
ならば消去候補エントリに対応している）にシェードを
施すことによって示されている。

【００２９】図２０は、上記別の実施例における動作の
説明に用いられる別の例示図である。この図２０におい
ては、前記図１９に示された状態に続けて、文字［近］
を格納する領域を確保するため、図１のフォントキャッ
シュ５に相当する文字パターンデータ格納領域４３から
不用の文字パターンデータ（ここでは、文字［序］に対
応するもの）を消去することができる消去候補エントリ
を選択することが例示されている。この図２０において
は、ＬＲＵリスト６１の左端（前述されたように、本来
の消去候補エントリに対応するもの）には文字［に］に
対する予約フラグがセットされているために、この左端
のエントリに続く［序］のためのエントリが消去対象の
エントリに指定されることになる。このような場合にお
いては、従来の手法では近い将来に参照されるにも係わ
らず、［に］に対する文字パターンが消去候補として選
択されており、この点においてこの発明の有効性を認め
ることができる。

【００３０】図２１は、上記別の実施例における動作の
説明に用いられる別の例示図である。この図２１におい
ては、前記図２０に示された状態に続けて、選択された
消去対象のエントリに対する文字パターンデータ（ここ
では、文字［序］に対応するもの）を消去し、文字
［近］に対応する文字パターンデータの展開を実行して
から、ＬＲＵリスト６１について所要の更新をするよう
にされる。

【００３１】図２２は、上記別の実施例における動作の
説明に用いられる別の例示図である。この図２２におい
ては、前記図２１に示された状態に続けて、ＬＲＵ遅延
処理バッファ２０に登録されていた文字に関する所定の
後処理が施され、クリアにされて、所要の作業が全て終
了した後の、フォントキャッシュ５（図１）に相当する
文字パターンデータ格納領域４３におけるデータ構造が
示されている。

【００３２】図２３は、上記別の実施例の動作を説明す
るためのフローチャートであって、前記図１６の状態か
ら前記図６に例示された文書を出力させることを説明す
るためのものである。この図２３において、 Ｓ１：印字すべき文字コードの取り出し；まず、印字す
べき文字コードの取り出しがなされ、ＬＲＵ遅延処理バ
ッファ２０がフルの状態にあるか否かのチェックがなさ
れる。そして、このＬＲＵ遅延処理バッファ２０がフル
の状態にはないとされたときには、印字対象としての文
字コードについて、キャッシュヒット／キャッシュミス
のいずれであるかの判定処理がなされる。ここで、
［１］キャッシュヒットであると判定されたときには、
Ｓ２，Ｓ３の処理がなされる。これに対して、［２］キ
ャッシュミスであると判定されたときには、前記のステ
ップＳ２，Ｓ３をスキップして、Ｓ４以降の処理がなさ
れる。ここで、前記の図１６を再び参照すると、［近］
なる文字が処理を施された状態が示されている。この場
合には、前記の文字［近］はヒットしておらず、対応の
文字情報だけがＬＲＵ遅延処理バッファ２０に登録され
ることになる。 Ｓ２：ＬＲＵ遅延処理バッファ２０に空きがあり、対象
の文字についてキャッシュヒットが生じたとき；フォン
トキャッシュ５（文字パターンデータ格納領域４３）か
ら、ヒットが生じた文字パターンデータを管理するキャ
ッシュエントリ（ＬＲＵ管理用エントリ３０Ａ〜３０Ｃ
において対応するもの）を取り出して、その予約フラグ
をセットするようにされる。 Ｓ３：ヒットが生じたキャッシュエントリのポインタ
を、ＬＲＵ遅延処理バッファ２０に登録するようにされ
る。 Ｓ４：文字の出力情報をＬＲＵ遅延処理バッファ２０に
登録するようにされる。実際の描画処理において必要と
される情報、即ち、前記実際の描画処理において文字パ
ターンを文字出力用ページバッファ６にコピーするため
に必要な（例えば、該当の文字の位置を指定するための
ような）情報を、前記ＬＲＵ遅延処理バッファ２０に登
録するようにされる。これ以降は、処理すべき文字が存
在する限りは先のステップＳ１に戻って、必要な処理の
繰り返しがなされる。そして、ＬＲＵ遅延処理バッファ
２０がフルになるのに先だって処理すべき文字がなくな
ったときには、ＬＲＵ遅延処理バッファ２０内の文字の
出力のために、ステップＳ５以降の処理を実行するよう
にされる。ここで、前記の図１８を再び参照すると、
［年］なる文字が処理を施された状態が示されている。
この場合には、前記の文字［年］はヒットしており、対
応の文字情報とキャッシュエントリとがＬＲＵ遅延処理
バッファ２０に登録され、これに加えて、対応するエン
トリの予約フラグがセットされる。 Ｓ５：ＬＲＵ遅延処理バッファ２０がフルであるとき
の、その遅延処理後の後処理をすること；前記ＬＲＵ遅
延処理バッファ２０がフルであるときは、バッファに登
録されている文字についての実際の描画処理を施すよう
にされる。このステップＳ５においては、ＬＲＵ遅延処
理バッファ２０の先頭から選択するようにされる。そし
て、このバッファの先頭からキャッシュエントリが登録
されているか否かのチェックがなされる。ここで、
［１］キャッシュエントリが登録されているとき、即
ち、フォントキャッシュ５に所要の文字パターンが登録
されているときには、ステップＳ６以降の作業を実行す
るようにされる。これに対して、［２］キャッシュエン
トリが登録されていないとき、即ち、キャッシュヒット
が生じなかったときには、ステップＳ１１以降の作業を
実行するようにされる。ここで、前記の図１９を再び参
照すると、［に］なる文字が処理を施された状態が示さ
れるとともに、ＬＲＵ遅延処理バッファ２０がフルであ
る状態が示されている。この場合には、文字［に］もヒ
ットしており、前記図１８における文字［年］と同様な
処理が施されたことになる。 Ｓ６：エントリの予約フラグをクリアする（キャッシュ
ヒットが生じたときの描画処理）；ＬＲＵ遅延処理バッ
ファ２０に登録されたキャッシュエントリにおける所定
のものの予約フラグがクリアされる。ここでの予約フラ
グは、ステップＳ１１以降でフォントキャッシュ５から
消去される候補として選択されることを防止するための
ものであるが、直後のステップＳ６においてＬＲＵリス
ト６１の先頭におかれるものであることから、この時点
でクリアされたとしても、消去候補にされることはな
い。 Ｓ７：ＬＲＵ遅延処理バッファ２０に登録されているキ
ャッシュエントリをＬＲＵリスト６１の先頭に移動させ
る。 Ｓ８：該ＬＲＵ遅延処理バッファ２０に登録されている
キャッシュエントリから所要の文字パターンを得て、こ
れを文字出力用ページバッファ６にコピーする。即ち、
ＬＲＵ遅延処理バッファ２０に登録されている所定の文
字描画情報に基づいて、文字出力用ページバッファ６の
対応の位置にコピーする。 Ｓ９：ＬＲＵ遅延処理バッファ２０について、所定の処
理が終了したものを一つだけクリアする。 Ｓ１０：次に続くバッファの選択をする。即ち、前記の
ステップＳ９に続けて、次のバッファが存在するか否か
のチェックがなされ、バッファが存在することが判明し
たときに、このステップＳ１０における作業がなされ
る。これ以降は、前記ＬＲＵ遅延処理バッファ２０に登
録された文字情報がまだ存在するときには、その選択を
してから、ステップＳ６またはＳ１１以降の処理が施さ
れる。また、該ＬＲＵ遅延処理バッファ２０における描
画処理が完了したときに、処理すべき文字がまだ存在す
れば、ステップＳ１に戻ってＬＲＵ遅延処理バッファ２
０における遅延処理が再開される。これに対して、処理
すべき文字が存在しなければ、印字ための処理が終了す
るようにされる。 Ｓ１１：ＬＲＵリスト６１における消去候補としてのエ
ントリが選択される。キャッシュヒットが生じなかった
文字の描画のためには、対応の文字パターンを展開する
ための領域が必要であり、このような領域の確保のため
に、ＬＲＵリスト６１における消去候補としてのエント
リが選択される。ここで、ある所定のチェックの結果と
して、該当のエントリに予約フラグがセットされている
とすると、次のステップＳ１２に移行して、次の消去候
補としてのエントリを選択し、予約フラグがセットされ
ていないエントリが発見されるまで、ステップＳ１１に
おける処理とＳ１２における処理とを反復するようにさ
れる。なお、予約フラグがセットされていなかったとき
には、ステップＳ１３以降の作業が実行されることにな
る。ここで、前記の図２０を再び参照すると、ＬＲＵ遅
延処理バッファ２０に登録された文字［近］に対する消
去候補エントリが選択される状態が示されている。ここ
では、ＬＲＵリスト６１の消去候補エントリの中の文字
［に］に対して予約フラグがセットされていることか
ら、次の文字［序］に対するエントリを消去候補エント
リとして選択するようにされている。 Ｓ１２：ＬＲＵリスト６１における次続の消去候補とし
てのエントリが選択される。 Ｓ１３：エントリに登録されている文字パターン領域の
開放； Ｓ１４：文字パターンの展開処理；ここでは、ステップ
Ｓ１１で選択されたエントリに登録されている文字パタ
ーンの消去がなされて、使用可能な領域として選択され
（Ｓ１３），該当の領域を用いて、ＬＲＵ遅延処理バッ
ファ２０に登録されている描画すべき文字に対する展開
処理がなされる（Ｓ１４）。そして、これに対応する文
字パターンがフォントキャッシュ５に登録される。これ
以降の処理については、ステップＳ５においてヒットし
たエントリと同様な処理を実行するために、ステップＳ
７以降の処理を継続するようにされる。ここで、前記の
図２１を再び参照すると、図２０において選択されたエ
ントリの（文字［序］に対する）文字パターンデータを
消去し、文字［近］に対する文字パターンデータを展開
して、関連のＬＲＵリスト６１を更新した状態が示され
ている。なお、この図２１に続く図２２においては、Ｌ
ＲＵ遅延処理バッファ２０に登録された文字に対する所
要の後処理が施されてからの、フォントキャッシュ５
（文字パターンデータ格納領域４３）におけるデータ構
造の状態が示されている。

【００３３】図２４は、この発明の（ヒット時遅延処理
のための）更に別の実施例において用いられるＬＲＵ遅
延処理バッファ２０の構成例示図である。この図２４に
おいて、ＬＲＵ遅延処理バッファ２０には、複数個の文
字描画情報格納部１２Ａと、これらに個々に対応する遅
延ヒットフラグ格納部１２Ｃとが含まれており、前者で
ある文字描画情報格納部１２Ａに含まれている情報は、
所要の遅延処理が行われている文字を描画するために必
要な情報（例えば、ある所定のページバッファ上への書
き込み位置に関する情報）であり、また、それぞれのフ
ラグ格納部１２Ｃに格納された遅延ヒットフラグは、遅
延処理でミスした文字が再び出現した場合にセットされ
るものである。このＬＲＵ遅延処理バッファ２０におい
て管理することができる文字数は、通常は上記更に別の
実施例におけるメモリ資源の大きさ等を考慮して定めら
れるが、前記フォントキャッシュのエントリ数と同じで
あるか、または、これよりも少数であるようにされる。

【００３４】図２５は、上記更に別の実施例における、
遅延処理バッファ２０と遅延処理用ハッシュテーブル４
１Ａとの関連の例示図である。この図２５において、遅
延処理用ハッシュテーブル４１Ａは、フォントキャッシ
ュ５（図１）においてミスがあった文字が再び現れるこ
とをチェックするためのものであり、遅延処理の結果と
して登録される文字が該テーブル４１Ａに登録されてい
るか否かのチェックを行い、その結果が遅延処理バッフ
ァ２０における遅延ヒットフラグ１２Ｃに反映される。
この図２５においては、遅延処理バッファ２０の第３列
（３）における遅延ヒットフラグ１２Ｃがセットされ
て、ここに格納された文字は当該遅延処理バッファ２０
の他のいずれかの場所に格納された文字と同じであるこ
とが示されている。

【００３５】図２６は、上記更に別の実施例におけるフ
ォントキャッシュ５を管理するために用いられるＬＲＵ
管理用エントリ４００のデータ構造の例示図である。こ
の図２６において、前記ＬＲＵ管理用エントリ４００
は、フォントキャッシュ５に格納される文字パターンに
対応する文字情報（例えば、文字コード）格納部３１；
ＬＲＵ管理用の前方ポインタ格納部３２；ＬＲＵ管理用
の後方ポインタ格納部３３；および、該当の文字パター
ンデータに対するポインタ格納部３４；から構成されて
いる。

【００３６】図２７は、上記更に別の実施例において、
フォントキャッシュ用のハッシュテーブル４１Ｂで管理
されるＬＲＵ管理用エントリ（４００Ａ〜４００Ｃ）と
対応の文字パターンデータ（４３Ａ〜４３Ｃ）との間の
関係に関する例示図である。この図２７において、フォ
ントキャッシュエントリ（ＬＲＵリスト）に相当するＬ
ＲＵ管理用エントリ（４００Ａ〜４００Ｃ）は、キャッ
シュミスの際の消去候補エントリを、双方向のリスト構
造をもって管理している。消去候補エントリのリストは
ＬＲＵアルゴリズムで管理されており、フォントキャッ
シュに格納されている文字パターンが参照されたもの
が、その参照時期の新→古の順序で連結されている。即
ち、最近参照された文字（文字パターンデータ４３Ａに
対応するもの）は、ＬＲＵ管理先頭エントリへのポイン
タ３２Ａによってリストの先頭にされており、また、参
照の時期が最も古いもの（文字パターンデータ４３Ｃに
対応するもの）は、ＬＲＵ管理最終エントリへのポイン
タ３３Ａによって消去候補に指定されている。なお、こ
の図２７で示されている文字パターンデータ格納領域４
３も、機能的には前記図１におけるフォントキャッシュ
５に対応するものである。

【００３７】図２８は、上記更に別の実施例における動
作の説明に用いられる例示図である。この図２８は、前
記図２５および図２７の関連事項を簡略化して示したも
のであって、ハッシュテーブル４１Ｂは省略されてお
り、ある所定の桁数（ここでは３桁にされている）のＬ
ＲＵ遅延処理バッファ２０とある一定数のキャッシュエ
ントリ（ＬＲＵリスト）６１とから構成されている。こ
こでのキャッシュエントリ６１は、前記図２７において
リスト構造にされているＬＲＵ管理用エントリ（４００
Ａ〜４００Ｃ）に対応するものである。そして、この図
２８で示された状態において、前記図１のフォントキャ
ッシュ５に対応する文字パターンデータ格納領域４３に
は、「［お］［に］［年］［ ］・・・［ ］」のよう
な文字に対応する文字パターンデータが格納されてい
る。なお、この図２８における領域６Ａは、文字出力用
ページバッファ６（図１）のイメージ格納領域に相当す
るものである。

【００３８】図２９は、上記更に別の実施例における動
作の説明に用いられる別の例示図である。この図２９に
おいては、［近］なる１文字がＬＲＵ遅延処理バッファ
２０に格納されている。そして、この場合における
［近］の文字パターンはキャッシュにヒットしておら
ず、対応の文字情報だけがＬＲＵ遅延処理バッファ２０
に登録されることになる。そして、前記文字出力用ペー
ジバッファ６におけるイメージ格納用領域６Ａはブラン
クの状態に留まっている。

【００３９】図３０は、上記更に別の実施例における動
作の説明に用いられる別の例示図である。この図３０に
おいては、前記図２９に示された状態に続けて、文字
［年］について所要のＬＲＵ処理を施すようにされてい
る。この場合における［年］の文字パターンはキャッシ
ュにヒットしており、このために、関連のエントリがＬ
ＲＵリスト６１の先頭に移動される。そして、文字パタ
ーンデータ格納領域４３（図１のフォントキャッシュ
５）から対応の文字パターンを取り出して、これを前記
文字出力用ページバッファ６におけるイメージ格納用領
域６Ａの所定箇所に転記するようにされる。

【００４０】図３１は、上記更に別の実施例における動
作の説明に用いられる別の例示図である。この図３１に
おいては、前記図３０に示された状態に続けて、例え
ば、「における電子技術の進歩は、既存通信メディア
の」なる文字列が処理され、ＬＲＵ遅延処理バッファ２
０がフルにされた（［の］以外はキャッシュにヒットし
た）状態が示されている。ここで、前記文字列の中の最
初の文字［の］がキャッシュにヒットしなかったとする
と、これに対応する文字情報がＬＲＵ遅延処理バッファ
２０に登録される。そして、２番目に出現した文字
［の］については、遅延ヒットフラグがセットされた状
態の文字情報が前記ＬＲＵ遅延処理バッファ２０に登録
されることになる。このような状態においては、文字出
力用ページバッファ６におけるイメージ格納用領域６Ａ
には、文字［近］および文字［の］はいずれもまだ描画
されていない。

【００４１】図３２は、上記更に別の実施例における動
作の説明に用いられる別の例示図である。この図３２に
おいては、前記図３１に示された状態に続けて、文字
［近］を格納する領域を確保するため、図１のフォント
キャッシュ５に相当する文字パターンデータ格納領域４
３から不用の文字パターンデータを消去することができ
る消去候補エントリを選択することが例示されている。
この時点で処理された文字列においてヒットしたもの
は、ヒットしたＬＲＵの先頭位置（即ち、消去候補とは
なり難い位置）に移動されている。従って、ここでの消
去候補エントリの選択に際しては、消去候補エントリと
されているものの中で最左端にあるエントリが選択され
ることになる。なお、ここでの選択の仕方については特
別な手法は採用されていない。選択が必要とされるタイ
ミングをできるだけ遅延させ、それまでにＬＲＵリスト
の順番が最適化するようにされている。

【００４２】図３３は、上記更に別の実施例における動
作の説明に用いられる別の例示図である。この図３３に
おいては、前記図３２に示された状態に続けて、文字
［近］および文字［い］に対応する文字パターンデータ
の展開を実行してから、ＬＲＵリスト６１について所要
の更新をするようにされる。また、遅延ヒットフラグが
セットされたＬＲＵ遅延処理バッファ２０内の２番目の
文字［の］に対する展開処理も行われることになるが、
最初の文字［の］に対する展開が既に文字パターンデー
タ格納領域４３（図１のフォントキャッシュ５）で実行
されているために、前記展開処理を実行することなく、
前記の文字パターンデータ格納領域４３から対応の文字
パターンデータを検索し、この検索の結果に基づいて所
要の描画処理を施すようにされる。そして、この結果と
して、文字出力用ページバッファ６におけるイメージ格
納用領域６Ａには、前述の「における電子技術の進歩
は、既存通信メディアの」なる文字列が描画される。

【００４３】図３４は、上記更に別の実施例の動作を説
明するためのフローチャートであって、前記図２８の状
態から前記図５に例示された文書を出力させることを説
明するためのものである。この図３４において、 Ｓ１：印字すべき文字コードの取り出し；まず、ＬＲＵ
遅延処理バッファ２０がフルの状態にあるか否かのチェ
ックがなされる。そして、このＬＲＵ遅延処理バッファ
２０がフルの状態にはないとされたときには、印字すべ
き文字コードの取り出しがなされる。更に、ここでの印
字対象としての文字コードについて、キャッシュヒット
／キャッシュミスのいずれであるかの判定処理がなされ
る。ここで、［１］キャッシュヒットであると判定され
たときには、Ｓ２，Ｓ３の処理がなされる。これに対し
て、［２］キャッシュミスであると判定されたときに
は、前記のステップＳ２，Ｓ３をスキップして、Ｓ４の
処理がなされることになる。 Ｓ２：Ｓ１で対象の文字についてヒットが生じたとき；
フォントキャッシュ５（文字パターンデータ格納領域４
３）から、ヒットが生じた文字パターンデータを管理す
るキャッシュエントリ（ＬＲＵ管理用エントリ４００Ａ
〜４００Ｃにおいて対応するもの）を取り出して、これ
をＬＲＵリスト６１の先頭に移動させる。 Ｓ３：ヒットが生じたキャッシュエントリに基づいて取
得した文字パターンを、文字出力用ページバッファ６の
適所にコピーさせる。 Ｓ４：Ｓ１で対象の文字についてミスが生じたとき；実
際の描画処理において後から必要とされる情報、即ち、
前記実際の描画処理において文字パターンを文字出力用
ページバッファ６にコピーするために必要な（例えば、
該当の文字の位置を指定するためのような）情報を、前
記ＬＲＵ遅延処理バッファ２０に登録するようにされ
る。このときに、前記ＬＲＵ遅延処理バッファ２０の対
応するエントリが遅延処理用ハッシュテーブル４１Ａに
登録される。なお、これ以降は、処理すべき文字が存在
する限りは先のステップＳ１に戻って、必要な処理の繰
り返しがなされる。そして、ＬＲＵ遅延処理バッファ２
０がフルになるのに先だって処理すべき文字がなくなっ
たときには、ＬＲＵ遅延処理バッファ２０内の文字の出
力のために、ステップＳ５以降の処理を実行するように
される。 Ｓ５：ＬＲＵ遅延処理バッファ２０がフルであるとき
の、その遅延処理後の後処理をすること；前記ＬＲＵ遅
延処理バッファ２０がフルであるときには、または、出
力すべき文字がなくなった時点においてＬＲＵ遅延処理
バッファ２０に登録された文字が存在するときには、バ
ッファに登録されている文字についての実際の描画処理
を施すようにされる。このステップＳ５においては、Ｌ
ＲＵ遅延処理バッファ２０の先頭から選択するようにさ
れる。そして、このバッファの先頭から遅延ヒットフラ
グがセットされているか否かのチェックがなされる。こ
こで、［１］対応の遅延ヒットフラグがセットされてい
るときには、即ち、後述のステップＳ１１〜Ｓ１３にお
ける展開処理に従ってフォントキャッシュ５に所要の文
字パターンが登録されているときには、ステップＳ６以
降の作業を実行するようにされる。これに対して、
［２］対応の遅延ヒットフラグがセットされていないと
きには、即ち、フォントキャッシュ５（文字パターンデ
ータ格納領域４３）に対応の文字パターンが格納されて
いないときには、ステップＳ１１以降の作業である文字
パターンの展開処理を実行するようにされる。 Ｓ６：遅延ヒットフラグがセットされているときの描画
処理；このときには、フォントキャッシュ５（文字パタ
ーンデータ格納領域４３）側から、該当の文字コードに
対応するキャッシュエントリを得るようにされる。 Ｓ７：ＬＲＵ遅延処理バッファ２０に登録されているキ
ャッシュエントリをＬＲＵリスト６１の先頭に移動させ
る。 Ｓ８：該ＬＲＵ遅延処理バッファ２０に登録されている
キャッシュエントリから所要の文字パターンを得て、こ
れを文字出力用ページバッファ６にコピーする（即ち、
所要の描画処理を実行する）。このときには、ＬＲＵ遅
延処理バッファ２０に登録されている所定の文字描画情
報に基づいて、文字出力用ページバッファ６の対応の位
置にコピーする。 Ｓ９：ＬＲＵ遅延処理バッファ２０について、所定の処
理が終了したものを一つだけクリアする。 Ｓ１０：次に続くバッファの選択をする。即ち、前記の
ステップＳ９に続けて、次のバッファが存在するか否か
のチェックがなされ、バッファが存在することが判明し
たときに、このステップＳ１０における作業がなされ
る。これ以降は、前記ＬＲＵ遅延処理バッファ２０に登
録された文字情報がまだ存在するときには、その選択を
してから、ステップＳ６またはＳ１１以降の処理が施さ
れる。また、該ＬＲＵ遅延処理バッファ２０における描
画処理が完了したときに、処理すべき文字がまだ存在す
れば、ステップＳ１に戻ってＬＲＵ遅延処理バッファ２
０における遅延処理が再開される。これに対して、処理
すべき文字が存在しなければ、印字のための処理が終了
するようにされる。 Ｓ１１：ＬＲＵリスト６１における消去候補としてのエ
ントリが選択される。キャッシュヒットが生じなかった
文字の描画のためには、対応の文字パターンを展開する
ための領域が必要であり、このような領域の確保のため
に、ＬＲＵリスト６１における消去候補としてのエント
リが選択される。 Ｓ１２：ステップＳ１１において選択されたエントリに
登録されている文字パターンを消去して、該当の領域を
解放する。 Ｓ１３：所要の文字パターンの展開処理を実行する。こ
こでは、ステップＳ１２で解放された領域を用いて、Ｌ
ＲＵ遅延処理バッファ２０に登録されている描画すべき
文字に対する展開処理がなされる（Ｓ１３）。そして、
これに対応する文字パターンがフォントキャッシュ５に
登録される。これ以降の処理については、ステップＳ５
においてヒットしたエントリと同様な処理を実行するた
めに、ステップＳ７以降の処理を継続するようにされ
る。

【００４４】

【発明の効果】以上説明されたように、この発明に係る
フォントキャッシュ制御装置によれば、ＬＲＵ遅延処理
バッファが設けられており、キャッシュヒットまたはキ
ャッシュミスがあった文字に対するＬＲＵリストの更新
を遅延させることが可能になる。このために、短い期間
内に複数回出現した文字に対するＬＲＵリストの更新を
まとめて実行することが可能にされて、無用なＬＲＵリ
ストの更新を省略することができるという効果が奏せら
れる。また、この発明に係るフォントキャッシュ制御装
置によれば、ＬＲＵ遅延処理バッファが設けられてお
り、所定の予約フラグを用いるようにされていることか
ら、実際の文字パターンの展開やフォントキャッシュの
更新を遅延させることが可能となり、更に、近い将来に
使用される可能性のある文字の消去を防止することも可
能となる。特に、処理中のフォントキャッシュの状態や
印字すべき文字の出現順に応じて、最適の消去候補を該
フォントキャッシュから選択することができるために、
限られた容量のメモリ資源をもって最適のフォントキャ
ッシュ制御をすることができる。これに加えて、ホスト
側からの特別な指示を何も必要としないという利点もあ
る。

【図面の簡単な説明】

【図１】この発明の実施例であるフォントキャッシュ制
御装置を中心とする概略的な構成を例示するブロック図
である。

【図２】上記実施例であるフォントキャッシュ制御装置
の構成例示図である。

【図３】上記実施例において用いられるＬＲＵ遅延処理
バッファ１１の構成例示図である。

【図４】上記実施例におけるフォントキャッシュ５を管
理するために用いられるエントリのデータ構造の例示図
である。

【図５】上記実施例において、ハッシュテーブル４１で
管理されるフォントキャッシュエントリと文字パターン
データおよびＬＲＵ遅延処理バッファの関係の例示図で
ある。

【図６】上記実施例における動作の説明に用いられる出
力文書５１の例示図である。

【図７】上記実施例における動作の説明に用いられる例
示図である。

【図８】上記実施例における動作の説明に用いられる別
の例示図である。

【図９】上記実施例における動作の説明に用いられる別
の例示図である。

【図１０】上記実施例における動作の説明に用いられる
別の例示図である。

【図１１】上記実施例における動作の説明に用いられる
別の例示図である。

【図１２】上記実施例の動作を説明するためのフローチ
ャートである。

【図１３】この発明の（予約フラグが適用される）別の
実施例において用いられるＬＲＵ遅延処理バッファ１１
の構成例示図である。

【図１４】上記別の実施例におけるフォントキャッシュ
５を管理するために用いられるＬＲＵ管理用エントリ３
００のデータ構造の例示図である。

【図１５】上記別の実施例において、ハッシュテーブル
４１で管理されるＬＲＵ管理用エントリ（３００Ａ〜３
００Ｃ）と対応の文字パターンデータ（４３Ａ〜４３
Ｃ）およびＬＲＵ遅延処理バッファ２０の間の関係に関
する例示図である。

【図１６】上記別の実施例における動作の説明に用いら
れる例示図である。

【図１７】上記別の実施例における動作の説明に用いら
れる例示図である。

【図１８】上記別の実施例における動作の説明に用いら
れる別の例示図である。

【図１９】上記別の実施例における動作の説明に用いら
れる別の例示図である。

【図２０】上記別の実施例における動作の説明に用いら
れる別の例示図である。

【図２１】上記別の実施例における動作の説明に用いら
れる別の例示図である。

【図２２】上記別の実施例における動作の説明に用いら
れる別の例示図である。

【図２３】上記別の実施例の動作を説明するためのフロ
ーチャートである。

【図２４】この発明の（ヒット時遅延処理のための）更
に別の実施例において用いられるＬＲＵ遅延処理バッフ
ァ１２の構成例示図である。

【図２５】上記更に別の実施例における、遅延処理バッ
ファ２０と遅延処理用ハッシュテーブル４１Ａとの関連
の例示図である。

【図２６】上記更に別の実施例におけるフォントキャッ
シュ５を管理するために用いられるＬＲＵ管理用エント
リ４００のデータ構造の例示図である。

【図２７】上記更に別の実施例において、フォントキャ
ッシュ用のハッシュテーブル４１Ａで管理されるＬＲＵ
管理用エントリ（４００Ａ〜４００Ｃ）と対応の文字パ
ターンデータ（４３Ａ〜４３Ｃ）との間の関係に関する
例示図である。

【図２８】上記更に別の実施例における動作の説明に用
いられる例示図である。

【図２９】上記更に別の実施例における動作の説明に用
いられる別の例示図である。

【図３０】上記更に別の実施例における動作の説明に用
いられる別の例示図である。

【図３１】上記更に別の実施例における動作の説明に用
いられる別の例示図である。

【図３２】上記更に別の実施例における動作の説明に用
いられる別の例示図である。

【図３３】上記更に別の実施例における動作の説明に用
いられる別の例示図である。

【図３４】上記更に別の実施例の動作を説明するための
フローチャートである。

【符号の説明】 １−−文字コード入力受付装置；２−−展開用文字デー
タ記憶装置；３−−文字パターン展開装置；４−−フォ
ントキャッシュ制御装置；５−−フォントキャッシュ；
６−−文字出力用ページバッファ；７−−文字出力装
置。

Claims (6)

【特許請求の範囲】
1. 【請求項１】キャッシュバッファおよびキャッシュバッ
   ファ管理データメモリを備えており、キャッシュヒット
   に対応させてキャッシュバッファ管理データを書き換え
   ることにより、該キャッシュバッファがフルであるとき
   の空き領域作成処理に備える処理を行うことが可能にさ
   れたフォントキャッシュ制御装置において、 キャッシュヒット処理遅延バッファ、 キャッシュヒット時にキャッシュヒット処理遅延バッフ
   ァに登録を行う手段、および、 一括してキャッシュヒット処理を行う手段、 を含んでなることを特徴とするフォントキャッシュ制御
   装置。
2. 【請求項２】キャッシュバッファ管理データには予約フ
   ラグが含まれており、キャッシュヒット処理遅延バッフ
   ァに登録を行う手段は同時に予約フラグをセットするも
   のであり、一括してキャッシュヒット処理を行う手段は
   その処理に対応させて予約フラグをリセットし、キャッ
   シュバッファがフルであるときの空き領域作成処理は、
   予約フラグのセットされていないデータエントリのみを
   消去の対象とすることを特徴とする、 請求項１に記載のフォントキャッシュ制御装置。
3. 【請求項３】キャッシュバッファ、キャッシュバッファ
   管理データメモリおよび出力バッファを備えており、要
   求されたデータ識別子別に対応するデータを出力バッフ
   ァに書き込むようにされた、フォントキャッシュ制御の
   機能が随伴されるデータ出力装置のためのフォントキャ
   ッシュ制御装置であって、 データのキャッシングを行う装置において、キャッシュ
   バッファ管理データを参照して必要なデータの有無を判
   断する手段、 キャッシュヒット時にはキャッシュにあるデータを出力
   バッファに書き込む手段、 キャッシュミスヒット処理遅延バッファ、 キャッシュミスヒット時にはキャッシュミスヒット処理
   遅延バッファに登録する手段、 一括してキャッシュミスヒット処理（データの入力、展
   開や出力バッファへの書き込み）を行う手段、 が含まれてなることを特徴とする、フォントキャッシュ
   制御の機能が随伴されるデータ出力装置のためのフォン
   トキャッシュ制御装置。
4. 【請求項４】キャッシュバッファとキャッシュバッファ
   管理データメモリとを備えており、キャッシュヒットに
   対応させて該キャッシュバッファ管理データメモリ内の
   キャッシュバッファ管理データを書き換えることによ
   り、キャッシュバッファがフルであるときの空き領域作
   成処理に備える処理を実行するフォントキャッシュ制御
   装置の適用方法であって、 同じ対象に対するキャッシュヒットが複数回生じたとき
   に、該当のキャッシュヒット処理の実行を遅延させるこ
   と、 前記同じ対象に対するキャッシュヒットが複数回生じた
   ときに、ＬＲＵ処理遅延バッファに対してその旨を登録
   すること、および、 キャッシュヒットが複数回生じた前記同じ対象に対し
   て、一括してキャッシュヒット処理を実行すること、 を含んでなることを特徴とする、フォントキャッシュ制
   御装置の適用方法。
5. 【請求項５】キャッシュバッファ管理データに含まれる
   予約フラグのセットは、キャッシュヒット処理遅延バッ
   ファに登録を行う手段によって実行されること、 前記予約フラグのリセットは、一括して行われるキャッ
   シュヒット処理に対応して実行されること、および、 キャッシュバッファがフルであるときの空き領域作成処
   理は、該予約フラグがセットされていないデータエント
   リだけを消去の対象として選択されること、 を特徴とする、請求項４に記載のフォントキャッシュ制
   御装置の適用方法。
6. 【請求項６】キャッシュバッファ、キャッシュバッファ
   管理データメモリおよび出力バッファを備えており、要
   求されたデータ識別子別に対応するデータを出力バッフ
   ァに書き込むようにされた、フォントキャッシュ制御の
   機能が随伴されるデータ出力装置のためのフォントキャ
   ッシュ制御装置の適用方法であって、 データのキャッシングを実行するときに、キャッシュバ
   ッファ管理データを参照して必要なデータの有無を判断
   すること、 キャッシュヒット時においては、キャッシュに存在する
   データを出力バッファに書き込むこと、 キャッシュミスヒット時においては、その旨をキャッシ
   ュミスヒット処理遅延バッファに登録すること、およ
   び、 一括してキャッシュミスヒット処理（データの入力、展
   開や出力バッファへの書き込み）を実行すること、 が含まれてなることを特徴とする、フォントキャッシュ
   制御の機能が随伴されるデータ出力装置のためのフォン
   トキャッシュ制御装置の適用方法。