JPH05314120A - キャッシュメモリ - Google Patents

Abstract

(57)【要約】 【目的】 ＬＲＵアルゴリズムでフォントを削除する際
に、複数個のフォントを格納しているフォントデータブ
ロックが、不当に優遇されないようにすること。 【構成】 格納したいとしている最大サイズのフォント
を基にキャッシュメモリを分割したフォントデータブロ
ックを、更に幾つかのフォントデータサブブロックに分
割する。そして、フォントをキャッシュメモリに格納す
るに当たっては、フォントのサイズを考慮して、所要数
のフォントデータサブブロックを使用して格納する。そ
して、ＬＲＵアルゴリズムにおけるキャッシュメモリ内
残留優先度決定方法として、ヒットしたフォントが格納
されているフォントデータブロックのヒット前のキャッ
シュメモリ内残留優先度をＰ，該ヒットしたフォントが
格納されているフォントデータブロックに格納されてい
る全フォント数をＮとした時、ヒット後のキャッシュメ
モリ内残留優先度を Ｐ（１−１／Ｎ） （但し、少数点以下切捨て） とする方法を採用する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、文字フォント等のビッ
トマップデータを一時的に格納しておくキャッシュメモ
リに関するものである。

【０００２】

【従来の技術】ホストコンピュータから文字信号を受
け、その文字をビットマップデータの形でページバッフ
ァに展開し、それを表示装置に表示したり、印字装置で
プリントアウトする装置がある。そのような装置におい
ては、使用頻度の高いフォントのビットマップデータ
を、一時的に格納しておくキャッシュメモリを具えたも
のがある。

【０００３】図５は、前記のような装置の一例としての
プリンタの構成を示す図である。図５において、１０は
プリンタ制御部、１１はアウトラインフォントデータ格
納部、１２は解釈部、１３はキャッシュメモリ制御部、
１４はキャッシュメモリ、１５は中間バッファ、１６は
描画部、１７はページバッファ、１８はコントロールパ
ネル、１９は画像記録部である。画像記録部１９は、こ
の場合プリンタである。

【０００４】印字しようとする文字の信号が、ホストコ
ンピュータ等から解釈部１２へ送られて来る。文字の信
号とは、例えばどういう文字かを表す文字コードとか、
文字の大きさ（文字の高さ，幅）等に関する信号であ
る。解釈部１２は、その信号を解釈して、まず、その文
字がキャッシュメモリ１４に有るか探し、有ればそこか
ら取り出して、ページバッファ１７に送る。

【０００５】もし無ければ、アウトラインフォントデー
タ格納部１１から、その文字のアウトラインフォントデ
ータを取り出し、描画部１６でビットマップデータのフ
ォントに描画し、それをページバッファ１７に送る。同
時に、キャッシュメモリ１４にも送って格納し、次に使
用する時のために備える。

【０００６】ページバッファ１７に１ページ分の文字が
展開されれば、そのページ分のデータが画像記録部１９
へ送られ、印刷される。なお、中間バッファ１５は、解
釈部１２からの信号を、タイミング調整等のために一時
的に格納するためのものである。また、コントロールパ
ネル１８は、操作者が種々の指令をするためのものであ
る。

【０００７】ところで、キャッシュメモリ１４は、フォ
ントのビットマップデータを格納するわけであるが、１
つのフォントを格納するための区画（これを、「フォン
トデータブロック」という）の大きさは、予め定めてお
く。フォントデータブロックの大きさは、キャッシュメ
モリ１４にキャッシュしようと思っている最大サイズの
文字を、コントロールパネル１８から指定しておくこと
によって定められる。

【０００８】例えば、最大１２ポイントまでの文字をキ
ャッシュしたいというのであれば、コントロールパネル
１８より、「１２ポイント」と入力する。文字ポイント
数が指定されれば、フォントデータブロック１の大き
さ、つまりデータ量は、次のようにして決定される。 フォントデータブロック１のデータ量＝（Ｄ＋７）÷８
×Ｄ 但し、Ｄはドット数であり、指定されたポイント数Ｍと
表示時（または印刷時）の解像度Ｋとより Ｄ＝（Ｍ・Ｋ／７２） で求められる。

【０００９】図３は、従来のフォントデータ格納方式を
説明する図である。１はフォントデータブロック、１−
１はデータ格納方向を示す線、１−２は所要メモリ容量
を示す線である（１−１，１−２の線は、従来の問題点
を説明するためのものであるので、ここでは格別注意す
る必要はない）。

【００１０】図３（イ）は、Ａという文字（フォント）
のビットマップデータを表している。このＡは、フォン
トデータブロック１全体をフルに使ったサイズの文字で
ある。図３（ロ），（ハ）のＫ，Ｈは、その半分程度の
サイズの文字である。従来は、文字のサイズにかかわら
ず、１つの文字は、１つのフォントデータブロック１に
格納されていた。

【００１１】

【発明が解決しようとする課題】

（問題点）しかしながら、前記した従来のキャッシュメ
モリへのフォントデータ格納方式では、格納するフォン
トのサイズにかかわらず、１つのフォントに対しては１
つのフォントデータブロックを使って格納するので、メ
モリを無駄に消費するという問題点があった。

【００１２】（問題点の説明）図３において、フォント
データブロック１にフォントデータを格納する場合、デ
ータ格納方向を示す線１−１の方向に、１ドットづつの
データが順次格納される。その結果、ＡとかＫとかＨ等
のフォントが格納されることになる。

【００１３】図３（イ）の場合は、Ａという文字のサイ
ズが大きく、フォントデータブロック１をフルに使わな
ければ格納できない。しかし、図３（ロ）や（ハ）のよ
うに、フォントデータブロック１のサイズに比べて小さ
なサイズのフォント（Ｋ，Ｈ）を格納する場合、フォン
トデータブロック１をフルに使わなくとも、格納でき
る。即ち、ＫなりＨなりの全容を構成するドットが格納
された後の位置を表す線１−２までのメモリで、Ｋなり
Ｈなりのフォントデータは、格納できてしまう。つま
り、線１−２は、このサイズのＫなりＨなりを格納する
際の、所要メモリ容量を表す線ということになる。

【００１４】従って、所要メモリ容量を示す線１−２よ
り下方にある部分のメモリは、実質的には使われずじま
いになっており、結局、この部分は無駄に消費されてい
ることになる。本発明は、以上のような問題点を解決す
ることを課題とするものである。

【００１５】

【課題を解決するための手段】前記課題を解決するた
め、本発明のキャッシュメモリでは、指定された最大文
字サイズにより定まるデータサイズのフォントデータブ
ロックを更に複数個に分割したフォントデータサブブロ
ックを、フォントを格納する単位として具え、ヒットし
たフォントが格納されているフォントデータブロックの
ヒット前のキャッシュメモリ内残留優先度をＰ，該ヒッ
トしたフォントが格納されているフォントデータブロッ
クに格納されている全フォント数をＮとした時、ヒット
後のキャッシュメモリ内残留優先度を Ｐ（１−１／Ｎ） （但し、少数点以下切捨て） とすることとした。

【００１６】

【作 用】格納したいとしている最大サイズのフォン
トを基にキャッシュメモリを分割したフォントデータブ
ロックを、更に幾つかのフォントデータサブブロックに
分割する。そして、フォントをキャッシュメモリに格納
するに当たっては、そのフォントのサイズを考慮して、
フォントデータサブブロックを所要数使用して格納す
る。更に、ヒットされた時のキャッシュメモリ内残留優
先度を、 Ｐ（１−１／Ｎ） （但し、小数点以下切捨て） とすることにより、ＬＲＵアルゴリズム（ＬＲＵ：Leas
t Recently Used １番昔に使ったものから削除するとい
う方式）により残留させるか否かが決められているキャ
ッシュメモリにおいて、複数個のフォントがキャッシュ
されているフォントデータブロックが、不当に優遇され
ることのないようにする。

【００１７】

【実施例】以下、本発明の実施例を図面に基づいて詳細
に説明する。図２は、本発明のキャッシュメモリでのフ
ォントデータ格納方式を説明する図である。符号は、図
３のものに対応し、２はフォントデータサブブロックで
ある。

【００１８】本発明では、キャッシュメモリにキャッシ
ュしようとしている最大サイズの文字ポイント数より定
めたフォントデータブロック１を、更に幾つかに分割し
て、フォントデータサブブロック２とする。そして、フ
ォントを格納するに際しては、フォントデータサブブロ
ック２を単位として格納する。

【００１９】即ち、１つのフォントデータサブブロック
２で格納し得るサイズのフォントの場合は、１つのフォ
ントデータサブブロック２を使用して格納する。フォン
トのサイズが大きく、１つのフォントデータサブブロッ
ク２では格納し得ない場合には、必要な数のフォントデ
ータサブブロック２を使用して格納する。

【００２０】図２では、フォントデータブロック１を２
分割したものを、フォントデータサブブロック２とした
例を示している。もっと細かく分割することも可能であ
る（例えば、４分割，８分割等）。図２（イ）のＡは、
サイズが大きくて１つのフォントデータサブブロック２
では格納できないので、連続する２つのフォントデータ
サブブロック２を使用して格納されている。

【００２１】図２（ロ）では、Ｋ，Ｈのサイズが小さ
く、それぞれ１つのフォントデータサブブロック２で格
納し得るサイズなので、１つのフォントデータサブブロ
ック２に格納されている。従って、図２と同じＡ，Ｋ，
Ｈのフォントを格納する場合、本発明では、フォントデ
ータブロックが２つで済み、従来３つ必要としていたの
に比べて、１個節約できる。即ち、無駄に消費されるメ
モリが少なくなる。

【００２２】フォントをキャッシュメモリに格納する手
順を簡単に説明すると、次の通りである。まず、ホスト
コンピュータから、図５の解釈部１２に送られて来る文
字の信号より、その文字サイズがどのようなサイズ（高
さ，幅）なのかを求める。これにより、この文字を格納
するのには、メモリ容量にして何バイト必要なのか（デ
ータ量）が分かる。

【００２３】次に、そのデータ量をまかなうには、フォ
ントデータサブブロック２を幾つ使用すれば格納できる
かを算出する。図２の例は、フォントデータサブブロッ
ク２は、フォントデータブロック１を２分割したもので
あるから、この例における算出結果は、１個か、それと
も２個である。

【００２４】図２（ロ）のように、１つのフォントデー
タサブブロック２で収容できる文字を格納する場合は、
どの空きフォントデータサブブロック２を使用しても差
支えない。しかし、図２（イ）のように、２個のフォン
トデータサブブロック２を用いなければ収容できない文
字を格納する場合は、連続した空きフォントデータサブ
ブロック２が必要である。つまり、格納に適する条件
（ここでは「連続している」という条件）で、所要数の
空きフォントデータサブブロック２があるかどうかを探
す必要がある。

【００２５】空きブロックが無かった場合には、どれか
のブロックの内容を削除して、そこへ格納せざるを得な
い。そのために、まず削除するブロックを、一定のやり
方に則って探す。このようなことは、キャッシュメモリ
を管理する上での処理の１つである「あふれ処理」と言
われるものに属する処理である。

【００２６】内容を削除するブロックの決め方には、種
々のものがある。その内の１つに、参照された（前回ヒ
ットした）のが最も古いものから順に削除するというや
り方（ＬＲＵアルゴリズム）がある。削除されてできた
空きブロックに、今回の新たなフォントが格納される。

【００２７】ところで、フォントデータブロックを複数
個のフォントデータサブブロックに分割して、１つのフ
ォントを格納したり、複数個のフォントを格納したりす
ると、従来のＬＲＵアルゴリズムでは、複数個のフォン
トを格納しているフォントデータブロックが、不当に優
遇されるという不都合が生じることが判明した。

【００２８】図４は、ＬＲＵアルゴリズムでの従来の優
先度決定方法を説明する図である。符号は図２のものに
対応している。「優先度」は、キャッシュメモリ内残留
優先度（あふれ処理の時、キャッシュメモリから削除さ
れないという点での優先度）を表し、数値が小さいほど
優先度が高い（０が最高）。また、「フォント」は、１
つのフォントデータブロックに格納されている、単一ま
たは複数個のフォントを表している。

【００２９】今、仮にＫとＨとが格納されているフォン
トデータブロックのＫがヒットしたとする。図４（イ）
は、それがヒットする前の、各フォントデータブロック
の優先度を表している。従来の優先度決定方法は、ヒッ
トしたフォントデータブロックを最高の優先度にすると
いう方法であった。従って、ヒット後の優先度を表して
いる図４（ロ）では、ＫとＨが格納されているフォント
データブロックは、最高の優先度「０」に位置づけられ
ている。それに伴い、他のフォントデータブロックの優
先度は、１つづつ繰り下げられる（優先度の数値として
は、＋１される）。

【００３０】すると、Ｋ，Ｈの２個のフォントを格納し
ているフォントデータブロックがヒットされる確率は、
１個のフォントしか格納していない他のフォントデータ
ブロックに比べて、２倍となる。フォントデータブロッ
クをＮ分割してフォントデータサブブロックとすると、
Ｎ個のフォントを格納するものが出て来るが、これは、
ヒット確率がＮ倍となる。

【００３１】これでは、複数個のフォントを格納してい
るフォントデータブロックは、常に高い優先度を維持す
ることになり、不当に優遇されることになる。不当に優
遇される結果、比較的よく使用するフォントであるにも
かかわらず、１つのフォントデータブロックをフルに使
って格納されているため、徐々に優先度が低くなり、キ
ャッシュメモリから削除されてしまうものが出て来る。

【００３２】従って、優先度の決定方法を改良して、複
数個のフォントを格納しているフォントデータブロック
が、不当に優遇されることのないようにする必要があ
る。そこで、本発明では、次のような、新たな優先度決
定方法を提案する。

【００３３】即ち、Ｎ個のフォントを格納しているフォ
ントデータブロックがヒットした時、そのヒットが優先
度引き上げに貢献する度合いは、単一のフォントが格納
されているものがヒットした場合に比べて、１／Ｎの値
打ちにしか評価してやらないという方法である。なお、
フォントデータブロック内の１つのフォントデータサブ
ブロックのみに格納され、残りのフォントデータサブブ
ロックは空となっている場合には、言うまでもないこと
ではあるが、Ｎ＝１として扱う。

【００３４】従来の優先度決定方法では、ヒット前の優
先度をＰとした場合、ヒットにより優先度０に引き上げ
られていた。即ち、ヒット後の優先度を算出する際に
は、Ｐ−Ｐ＝０という演算が行われていた。ヒットによ
り、ヒット前の優先度Ｐだけ引上げ（−Ｐ）ていたので
ある。

【００３５】新しい優先度決定方法では、Ｎ個のフォン
トを格納しているフォントデータブロックがヒットした
時には、優先度引上げに貢献する度合いを１／Ｎしか認
めないから、Ｐ×（１／Ｎ）だけしか引き上げない。従
って、新しい優先度は、この分だけ数値を小さくして、
Ｐ−Ｐ×（１／Ｎ）となる。書き換えると Ｐ（１−１／Ｎ） …… と表せる。なお、優先度は整数で表すから、小数点以下
は切り捨てることにする。

【００３６】図１は、ＬＲＵアルゴリズムでの新たな優
先度決定方法を説明する図である。符号等は、図４のも
のに対応している。図１（イ）はヒット前の各フォント
の優先度を示している。今、フォントＫがヒットしたと
する。Ｋが格納されているフォントデータブロックの優
先度は３である（Ｐ＝３）。ヒット後の優先度は、前記
式に、Ｎ＝２，Ｐ＝３を代入して、３（１−１／２）
＝１．５を得るから、小数点以下切り捨てて、１が求め
られる。それゆえ、図１（ロ）に示すように、ヒット後
は優先度１として位置づけられる。従来なら最高の優先
度にされていたが（図４（ロ））、新しい方法では、そ
こまでは優遇しない。

【００３７】

【発明の効果】以上述べた如く、本発明のキャッシュメ
モリによれば、格納したいとしている最大サイズのフォ
ントを基にキャッシュメモリを分割したフォントデータ
ブロックを、更に幾つかのフォントデータサブブロック
に分割し、それを単位としてフォントを格納するので、
メモリが無駄に消費されることがなくなる。

【００３８】また、ＬＲＵアルゴリズムにおけるキャッ
シュメモリ内残留優先度決定方法として、新しい方法を
提案したので、複数個のフォントを格納しているフォン
トデータブロックが、優先度の面で不当に優遇されるこ
とがなくなる。

【図面の簡単な説明】

【図１】 ＬＲＵアルゴリズムでの新たな優先度決定方
法を説明する図

【図２】 改良したフォントデータ格納方式を説明する
図

【図３】 従来のフォントデータ格納方式を説明する図

【図４】 ＬＲＵアルゴリズムでの従来の優先度決定方
法を説明する図

【図５】 キャッシュメモリを具えたプリンタの構成を
示す図

【符号の説明】

１…フォントデータブロック、２…フォントデータサブ
ブロック、１−１…データ格納方向を示す線、１−２…
所要メモリ容量を示す線、１０…プリンタ制御部、１１
…アウトラインフォントデータ格納部、１２…解釈部、
１３…キャッシュメモリ制御部、１４…キャッシュメモ
リ、１５…中間バッファ、１６…描画部、１７…ページ
バッファ、１８…コントロールパネル、１９…画像記録
部

Claims (1)

【特許請求の範囲】
1. 【請求項１】 指定された最大文字サイズにより定まる
   データサイズのフォントデータブロックを更に複数個に
   分割したフォントデータサブブロックを、フォントを格
   納する単位として具え、ヒットしたフォントが格納され
   ているフォントデータブロックのヒット前のキャッシュ
   メモリ内残留優先度をＰ，該ヒットしたフォントが格納
   されているフォントデータブロックに格納されている全
   フォント数をＮとした時、ヒット後のキャッシュメモリ
   内残留優先度を Ｐ（１−１／Ｎ） （但し、少数点以下切捨て） とすることを特徴とするキャッシュメモリ。