JPH05261983A

JPH05261983A - 文字データ管理装置

Info

Publication number: JPH05261983A
Application number: JP4062395A
Authority: JP
Inventors: Fumio Nagasaka; 文夫長坂
Original assignee: Seiko Epson Corp
Current assignee: Seiko Epson Corp
Priority date: 1992-03-18
Filing date: 1992-03-18
Publication date: 1993-10-12

Abstract

(57)【要約】【目的】共有メモリ型密結合マルチマイクロプロセッ
サシステムで、各プロセッサが持つフォントキャッシュ
の内容を同一とし、各プロセッサ間に著しい処理速度の
違いを生じさせない文字データ管理装置を提供するこ
と。【構成】フォントキャッシュを、複数個のマイクロプ
ロセッサ1についてそれぞれ局所的なメモリ2に配置し、
共有ＲＡＭ4には共有フォントキャッシュ315を配置す
る。文字データの取得要求が発生した場合は、まず局所
フォントキャッシュ2からの読み出しを試み、これが不
可の時、次に共有フォントキャッシュ315からの読み込
みを試み、さらにこれも不可であれば、アウトラインフ
ォント元データからの文字発生をし、生成された文字形
状のイメージデータは共有フォントキャッシュ315だけ
に書き込む。局所フォントキャッシュ2の更新は、プロ
セスのスイッチが行なわれる時点で行なう。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、複数のプロセッサによ
り並列処理を行い印字データを出力する文字データ管理
装置に関する。

【０００２】

【従来の技術】ワークステーション等の周辺機器として
用いられる印刷装置では、最近、出力装置の解像度に依
存するビットマップ形のフォントから、出力装置の解像
度に依存しない文字輪郭を曲線情報として記述したアウ
トラインフォントが使われてきている。しかし、最終的
には各出力装置で解像度にあった画素データに変換する
処理を行う為、その変換に時間がかかってしまう。特
に、漢字の様な複雑な輪郭を持つフォントに対してはな
おさらである。

【０００３】そこで、プロセッサにより既に画素データ
に処理された変換済みの文字に関しては、その画素デー
タをバスを介してプロセッサに接続されているフォント
キャッシュと呼ばれるメモリに一時的に蓄え、その文字
の出力要求が再び発生した際にその画素データを使用す
る方法が採られている。それにより、印刷の際の処理時
間が短縮可能であるが、フォントキャッシュとして持て
る容量には限界があることから、特定の使用頻度の高い
文字だけをいかに保持しておくかが重要となってくる。
このフォントキャッシュの管理方法として、特開昭６４
−８８６６０号及び特開平２−２３３２６９号が開示さ
れている。前者はフォントキャシュに登録された文字デ
ータが再び呼び出された時、登録順位の再設定を行ない
登録時期の古いデータとして削除される不都合を防ぐも
のであり、後者は予め使用フォントに削除優先情報を持
たせるものである。

【０００４】しかし、フォントキャッシュを最大に効率
良く利用しても、単一プロセッサでの装置では高速化に
やはり限界が生じてしまう。

【０００５】そこで、複数のプロセッサをバス接続し、
複数のプロセッサによる並列処理により、単一プロセッ
サで実現不可能な高速処理を行なわせようとする発想が
生まれてくる。すでにコンピュータシステムでは、複数
のプロセッサにより並列処理を行うものが有り、各々の
プロセッサは割り当てられたプロセスの実行に当り、現
在処理中の実行単位の一部をキャッシュメモリに転送す
ることで命令アクセス、データアクセスの高速化を実現
している。

【０００６】

【発明が解決しようとする課題】それに対し、印刷装置
では、前述のようにアウトラインフォントから文字デー
タに変換する処理を必要とし、前者のコンピュータシス
テムのような只単に実行プロセスのプログラムをキャッ
シュメモリに転送をすればよいと云うわけにはいかず、
フォントキャッシュへの書き込みに費やされる時間は遥
かに大きくなる。従って、印刷装置では、なるべくアウ
トラインフォントから文字データへの変換処理を行わ
ず、しかもフォントキャッシュの内容を使用頻度の高い
データで満たしておくことが必要となる。

【０００７】また、個々のプロセッサが各々独自にフォ
ントキャッシュ管理を行うと、あるプロセッサで既に文
字画素データに変換された文字であっても別のプロセッ
サのフォントキャッシュに該文字が登録されていなけれ
ば、再度文字画素データへの変換を行う重複処理が行わ
れ効率的でない。特に、それまで使用頻度の低かったプ
ロセッサに、急に使用文字種の多い実行プロセスが割り
当てられた場合においては、フォントキャッシュの利用
率が著しく低下し処理上のボトルネックとなってしま
う。

【０００８】本発明はこの様な問題に鑑みてなされたも
のであって、その目的とするところは、各プロセッサの
持つフォントキャッシュの内容を同一となし、フォント
キャッシュの利用効率を高め高速文書処理を行う文字デ
ータ管理装置を提供することにある。

【０００９】

【課題を解決するための手段】本発明の文字データ管理
装置は、複数のプロセッサと、該プロセッサから共通に
アクセス可能な共有フォントキャッシュと、前記プロセ
ッサから共通にアクセス可能なアウトラインフォント供
給部と、前記プロセッサ個々にアクセス可能な局所フォ
ントキャッシュとを有し、プロセス実行時の文字の取得
要求に対し、まず局所的フォントキャッシュからの読み
取りを試み、あればこれを読み取り、なければ共有フォ
ントキャッシュからの読み取りを試み、更にない時は、
アウトラインフォント供給部から元データを読み込み文
字画素データを生成し、共有フォントキャッシュに登録
する。

【００１０】実行時のプロセス終了あるいは休止時に
は、共有フォントキャッシュの内容を局所的フォントキ
ャッシュに転送し、個々のフォントキャッシュの内容を
更新することを特徴とする。

【００１１】

【作用】本発明によれば、新たな文字画素データの書き
込みは共有キャッシュに対し行われる。プロセス終了あ
るは休止時に共有キャッシュから個々の局部キャッシュ
へデータが転送されるから、局部キャッシュの同一性が
保証できる。

【００１２】

【実施例】図１はこの発明の一実施例として挙げた電子
写真方式の印刷装置のブロック構成図である。

【００１３】印刷装置は、３つの主要な部分から構成さ
れる。すなわち、プリントエンジン11、エンジン制御装
置10および制御回路である。印刷装置の動作は、次の通
りである。制御回路が外部のパーソナルコンピュータ等
の機器に接続されたインターフェース13から、印刷制御
コードを受信する。マイクロプロセッサユニット1によ
り実行される制御処理プログラムがこれを解釈して印刷
画素を生成し、イメージメモリ9に書き込む。エンジン
制御装置10は、この画素データをプリントエンジン11の
動作に同期してエンジン側に転送し印刷処理を行う。

【００１４】この実施例は、上記の一連の処理の内、制
御回路の文字データ管理方式に関して、本発明の手段を
取り入れたものである。

【００１５】制御回路の構成は次の通りである。複数
（図１では４個）のマイクロプロセッサユニット1が、
バス調停回路15によりグローバルバス3に接続される。
バス調停回路15は、バス調停制御回路12の制御信号に従
い、グローバルバス3に対するマイクロプロセッサユニ
ット1の競合を調停する。グローバルバス3には共有ＲＯ
Ｍ5、及び共有ＲＡＭ4が接続される。共有ＲＯＭ5に
は、本実施例の印刷装置の制御プログラムが書き込まれ
ている。また共有ＲＡＭ4は、上記制御プログラムの作
業用メモリと、後述するグローバルフォントキャッシュ
および受信データバッファに使用される。

【００１６】本実施例の印刷装置において、制御コード
の指定によってビットマップ印刷、文字印刷、簡単な図
形印刷が可能である。しかし本実施例の説明の中では簡
単のため、文字印刷の場合についてのみ説明する。

【００１７】本実施例の印刷装置は、アウトラインフォ
ントを使用し文字印刷を行なう。使用するアウトライン
フォントの元データは、ハードディスク装置8に予め記
録されている。ハードディスク装置8は、ディスク制御
装置7を介しＩ／Ｏプロセッサ6に制御される。また、外
部コンピュータ都のインターフェース13もＩ／Ｏプロセ
ッサ6により制御される。Ｉ／Ｏプロセッサ6はグローバ
ルバス3から通信ポートによりアクセスされるため、個
々のマイクロプロセッサユニット1は、独自にＩ／Ｏプ
ロセッサ6にアクセス可能である。

【００１８】各マイクロプロセッサユニット1が生成す
る印刷画素は、イメージメモリ9に記録される。イメー
ジメモリ9はデュアルポートメモリによって構成され、
エンジン制御回路10はグローバルバス3の調停とは別の
タイミングで、画素データを読み出し、プリントエンジ
ン11に転送する。

【００１９】一方、各マイクロプロセッサユニット1に
は、それぞれ局所的なフォントキャッシュ2が接続され
る。このフォントキャッシュ2はローカルバス接続され
ており、グローバルバス3を介してアクセスされるメモ
リに比較し、バス調停を必要としないため高速なアクセ
スができる。

【００２０】次に図２を用いて、本実施例で用いるフォ
ントキャッシュ管理方法の動作を説明する。各マイクロ
プロセッサユニット1に局所的に接続されたフォントキ
ャッシュ2には、フォント管理テーブル206及びフォント
データ部201が配置されている。また、共有ＲＡＭ4の上
に置かれるグローバルフォントキャッシュ領域315に
は、フォント管理テーブル206、フォントデータ部201及
びあふれ領域205が配置される。本実施例においては、
フォント管理テーブル206が６ｋバイト、フォントデー
タ部201が１２８ｋバイト、あふれ領域205が２ｋバイト
である。

【００２１】これら各メモリ上のデータ構造は、局所的
なフォントキャッシュ2においても、共有ＲＡＭ4上のフ
ォントキャッシュ315においても同様である。図２で
は、簡単のためこれらデータ構造をアドレスバス215、
データバス216によってアクセスする説明図とした。実
際のこれらバスアクセスでは、局所的なメモリアクセス
はマイクロプロセッサユニット1のローカルバスにより
行なわれ、大域的なアクセスはグローバルバス3により
行なわれる。

【００２２】以下これらのデータ構造を個々に説明す
る。

【００２３】フォント管理テーブル206は、６バイトの
登録フラグ207、１２バイトの文字指定レコード208及び
２バイトのキー209によって構成される構造体の、３０
０個からなる一次元配列である。この構造体を図６に示
した。ここで、文字指定レコードは以下の要素からなる
データ構造である。

【００２４】但し、書体は、ある文字について、複数の文字デザイン
が行われた場合、文字形状の差を特定する上で使用され
る呼称である。上記データ構造では、この呼称に数値を
割り当てて使用する。また、文字修飾指定は、文字書体
によらず、対象の文字の形状を、斜体文字、白抜き文字
などの操作対象とする指定であり、書体と同様に、上記
データ構造で使用する場合の内部表現は数値化されてい
る。

【００２５】フォントデータ部201は有限長の連続なア
ドレス配置を持つメモリである。内部は１２８バイトの
大きさの管理単位メモリ202の集合である。管理単位メ
モリ202は、大きさ１２６バイトのデータ部204と、大き
さ２バイトの指標部203からなる。指標部203の内容は、
次に続くべき管理単位メモリへの指標である。管理単位
メモリ202は大きさ固定であるため、指標の値から、実
アドレスの値は簡単な演算により求めることができる。
すなわち指標の値をixとしたとき、次に続くべき管理単
位メモリ202の先頭番地は、次式の値addrとして得られ
る。

【００２６】 addr = ix × 128 ＋メモリ201先頭番地言うまでも無く、値128は管理単位メモリの大きさから
くるもので、この演算は実アドレスへの変換の一例に過
ぎない。管理単位メモリ202の指標部203は、いわゆる連
結ポインタの変形の一つである。

【００２７】実際の文字のイメージデータは、管理単位
メモリ202のデータ部204を副数個使用し格納される。格
納されるデータの内容は、最初の２バイトが使用する管
理単位メモリ202の個数であり、これに続くデータがイ
メージデータである。また全てのイメージデータはラン
レングス圧縮されたデータ列からなる。

【００２８】周知の様に、メモリ管理手法としては、可
変長のデータ列を、連続したメモリ上に動的に配置する
方法が有る。この方法を使用すると、キャッシュへの登
録・削除を繰り返した後に、不要となったデータ列によ
る、複数個の、大きさの一定でない空き領域が生じる。
このような不要となった断片化したメモリ資源を再配置
し、大きな連続した空き領域を再度作り出すためには、
メモリのブロック移動を含む実行時間のかかる処理を行
う必要が有る。これに対し、本実施例の採用した、固定
長の管理単位メモリを複数利用する手段は、最終端の管
理単位メモリに未使用部分が生じ、メモリ利用率の点で
動的メモリ管理に劣るものである。しかし、管理が単純
であることから、容易にハードウェア化できる他、ソフ
トウェアで管理プログラムを実行しても高速処理ができ
る点で優れている。

【００２９】あふれ領域205は、連続した２ｋバイトの
大きさの一次元配列である。

【００３０】以上の様なフォントデータ部201、フォン
ト管理テーブル206及びあふれ領域205は、いずれもキャ
ッシュ割り当て処理217と呼ぶ一連の処理群によって管
理される。これら処理群には読み出し処理210、書き込
み処理211及び連結解消処理212が含まれる。

【００３１】次に、キャッシュ割り当て処理217につい
て説明する。

【００３２】キャッシュに登録された文字については、
そのイメージデータは、フォントデータ部201内のどれ
かの管理単位メモリ202を先頭に複数個の管理単位メモ
リ202に分割され格納される。このとき先頭となる管理
単位メモリ202については、フォントデータ部201の先頭
から連続して３００個の管理単位メモリ202をそれぞれ
使用する。一文字分のデータを複数の管理単位メモリ20
2に記録する場合の最初の管理単位メモリ202指標は、フ
ォント管理テーブル206の構造体の中のキー209によって
指定する。先に述べた様にフォントデータ部201は約１
２８ｋバイトの大きさを持つが、これは管理単位メモリ
202の１０２４個の集合である。この様な配列の大きさ
の制限があるため本実施例では、１文字あたりのイメー
ジデータは平均４３０バイト程度である。

【００３３】次に図５を用いて、文字データ取得の処理
の流れを説明する。

【００３４】あるプロセス内で、文字データを取得する
要求が発生した場合、文字データ取得処理501が呼び出
される。ここで要求は、前述したような文字指定レコー
ドによって行なわれる。言うまでもなく、同一文字コー
ドであっても、大きさ、文字種、文字修飾が異なる文字
指定を扱う必要があるためである。

【００３５】文字データ取得処理501の処理手順は、図
８の流れ図の通りである。処理を実行中のマイクロプロ
セッサユニット1はまず局所的なフォント管理テーブル2
06を検索する(S801)。ここで与えられた文字指定レコー
ドと同一の文字指定レコードがフォント管理テーブル20
6に存在すれば、文字データ（文字形状のイメージデー
タ）は局所的なフォントキャッシュに存在する。従っ
て、局所的なフォントキャッシュからの読み出しが実行
される(S802)。

【００３６】しかし、局所的なフォント管理テーブル20
6の検索で該当する文字のデータを検出できなかった場
合は、続いて大域的なフォント管理テーブル206を検索
する(S803)。文字指定レコードと同一の文字指定レコー
ドがフォント管理テーブル206に存在した場合は、大域
的な共有変数であるアクセスカウンタ508の値を＋１す
る(S804)。アクセスカウンタ508は４８ビット長のカウ
ンタで、システム立ち上げ時にクリアされる。以降クリ
アされず、フォント管理テーブル206で検索対象が検出
された場合文字データ取得処理501によって、またフォ
ント管理テーブル206に新たに登録された要素が有った
場合文字データ登録処理502によって、それぞれ＋１さ
れる。本実施例の使用状態では、オーバーフローは発生
しない。アクセスカウンタ508の値は、共有のフォント
管理テーブル206の、検出された要素に対応した登録フ
ラグ207に記録される(S805)。アクセスカウンタ508の値
は、登録、読み出しが行なわれた回数をカウントするた
め、この数が大きい程、最近アクセスされた要素である
と判断できる。

【００３７】続いてフォント管理テーブル206の該当す
る要素のキー209が取り出され(S806),大域的なフォント
キャッシュからの文字データ読み出しが行なわれる(S80
7)。大域的なフォント管理テーブル206で、文字指定レ
コードの一致する要素が検出できなかった場合は、カー
ネルに対し、文字データのハードディスク装置8からの
読み込みを要求する(S808)。

【００３８】これは、Ｉ／Ｏ処理を伴う。本実施例で
は、Ｉ／Ｏ処理の間、各マイクロプロセッサユニット1
は、処理結果を待たず現在実行中のプロセスを休止する
(S809)。この時、図３で示す更新処理304が実行され
る。更新処理304は、まず共有ＲＡＭ4のフォントキャッ
シュ領域への他のマイクロプロセッサユニット1のアク
セスを排他的にロックする。次に大域的なフォント管理
テーブル206と、フォントデータ部201の内容を全て、局
所的なフォント管理テーブル206とフォントデータ部201
に転送する。本実施例においてこの処理時間は約４０ｍ
秒である。この処理終了後、共有ＲＡＭ4上のフォント
キャッシュ領域に対するアクセスの排他制御を解除す
る。

【００３９】一方、ハードディスク装置8からのアウト
ラインフォントデータの読み込みが終了すると、Ｉ／Ｏ
プロセッサ6によるＩ／Ｏ終了処理が行なわれる。ま
ず、共有メモリ上のカーネルプログラム動作を示すフラ
グがチェックされ、カーネルプログラムを実行中のマイ
クロプロセッサユニットがあるか検出が行なわれる。

【００４０】カーネルプログラムを実行中のマイクロプ
ロセッサユニット1が存在する場合、Ｉ／Ｏプロセッサ6
は、共有メモリ上のＩ／Ｏ終了フラグを真にし、Ｉ／Ｏ
処理を完了する。カーネルプログラムを実行中のマイク
ロプロセッサユニット1が存在しない場合は、Ｉ／Ｏプ
ロセッサ6は、共有メモリ上のＩ／Ｏ終了フラグを真に
したの後、割り込み制御回路14を用いて、待機中のマイ
クロプロセッサユニット1に割り込み信号を送る。ここ
で、割り込み制御回路14は、待機中のマイクロプロセッ
サユニット1が無い場合、処理を保留しどれかのプロセ
スの実行が休止されるのを待つ。

【００４１】カーネルプログラムが実行され、Ｉ／Ｏプ
ロセッサ6の処理の終了が検出された場合、カーネルプ
ログラムは、待機中のマイクロプロセッサユニット1に
対し、割り込みによってプロセス起動を促し、先に休止
したプロセスの再開処理を行なう(S810)。但し、再開さ
れたプロセスが、休止以前と同じマイクロプロセッサユ
ニット1により実行されるとは限らない。

【００４２】再開されたプロセスは、カーネルサービス
によりアウトラインフォントの文字データを取得し(S81
1)、文字の形状を現すイメージデータの発生処理を行な
う(S812)。この処理は文字形状の複雑さによるが、本実
施例では４０×４０画素の大きさの漢字で、平均１００
ｍ秒から２００ｍ秒程度の処理時間を要する。この後、
プロセスを実行中のマイクロプロセッサユニット1は、
生成された文字のイメージを、文字データ登録処理502
の呼び出しにより、大域的なフォントキャッシュにだけ
登録する(S813)。

【００４３】以上の様に本実施例においては、局所的な
フォントキャッシュ2は、更新処理304以外で書き込みを
行なわない。局所的なフォントキャッシュ2は、常に読
み出しの対象となるだけである。

【００４４】図９は、文字データ登録処理502の処理の
流れ図である。

【００４５】文字データ登録処理502は、文字データ取
得処理501から文字のイメージデータと、文字指定レコ
ード208を引数として呼び出され使用される。登録処理5
02は、テーブル検索処理213を呼び出し(S901)、フォン
ト管理テーブル206の登録フラグ207を検索し、値の最も
小さい要素を取り出す(S902)。このとき、登録フラグ20
7の値が０であれば、その要素は、今までフォント登録
の対象とならなかったか、あるいは削除されたばかりの
要素であると判断する。そこで、登録フラグ207の内容
を１６進数のFFFFFFFFFFFFに書き換える。これは現在使
用中であることを示す一時的フラグである。続いて、こ
の要素に対応するキー209の内容を取り出し、キーと文
字のイメージデータを引数に書き込み処理211を実行す
る(S903)。処理結果の戻り値として、あふれ領域エラー
が戻された場合は、何も行なわず、登録処理を終了す
る。この場合、登録処理終了時には、登録フラグ207の
値を、処理前の値に復元する。

【００４６】書き込み処理211の戻り値として、書き込
みエラーが戻された場合は、登録処理502は削除処理503
を呼び出す(S904)。この処理の結果、フォントキャッシ
ュシステムのフォントデータ部201には空き領域が生じ
るため、登録処理502は再び、キーとイメージデータを
引数として、書き込み処理211を呼び出す。更に、処理
結果の戻り値として、書き込みエラーが戻された場合
は、同様の処理を繰り返し、登録が完了する。この場合
は、登録処理終了時にアクセスカウンタ508の内容に＋
１を行ない(S905)、この値を共有のフォント管理テーブ
ル206の登録フラグ207に書き込む(S906)。

【００４７】フォント管理テーブル206の登録フラグ207
を検索し、値の最も小さい要素を取り出したとき(S90
2)、この値が０でなければ、削除処理503を呼び出し(S9
07)、空き領域を確保し、S902以降の処理を行なう。

【００４８】図１０は、文字データ削除処理503の処理
の流れ図である。

【００４９】文字データ削除処理503は、テーブル検索
処理213を呼び出し(S1001)、共有のフォント管理テーブ
ル206の登録フラグ207について、０でない最小の要素を
取り出し(S1002)、この要素に対応したキー209の値を得
る(S1003)。次にこのキーの値を引数として、連結解消
処理212を呼び出し(S1004)処理を終了する。図５で示し
たように、文字データ取得処理501、文字データ登録処
理502および文字データ削除処理503から呼び出されるの
は、キャッシュ割り当て処理217の処理群である。

【００５０】次に、キャッシュ割り当て処理217の内、
読み出し処理210、書き込み処理211及び連結解消処理21
2についてそれぞれ説明する。

【００５１】読み出し処理210の処理を図１１の流れ図
を用いて説明する。

【００５２】読み出し処理210は引数として受け取った
キーを取り出し(S1101)アドレス演算部214を呼び出し(S
1102)、フォントデータ部201の管理単位メモリ202への
ポインタを取得する(S1103)。続いてこのポインタに従
い、文字のイメージデータ格納の先頭となる管理単位メ
モリ202へアクセスする(S1104)。以下連結した管理単位
メモリ202への指標に従い文字のイメージデータを次々
に読み出す(S1105)。既に述べた様に、格納されるデー
タの内容は、最初の２バイトが使用する管理単位メモリ
202の個数であるため、必要な個数の管理単位メモリ202
を連結することができる。また、一連の連結の最終に位
置する管理単位メモリ202の指標部203の内容は−１（１
６進数でFFFF）である。

【００５３】書き込み処理211の処理を図１２の流れ図
を用いて説明する。

【００５４】書き込み処理211は、受け取った引数から
キーの値を取り出し(S1201)、この値を引数にアドレス
変換処理214を呼び出す(S1202)。この処理結果として、
イメージデータ書き込みに使用可能な最初の管理単位メ
モリ202の先頭アドレスへのポインタを取得する(S120
3)。次に、書き込み処理211は、この管理単位メモリ202
にアクセスし(S1204)、イメージデータの全データサイ
ズを”管理単位メモリのサイズ−２”で割った整数値
（２バイト）の内容を書き込む。これはデータ格納に必
要な管理単位メモリ202の総数に一致する。次に、この
２バイトのデータに連続して、データ部204の大きさに
至るまでのイメージデータを書き込む(S1205)。もし更
に、イメージデータの残りバイト数があれば、書き込み
処理はこのデータをまずあふれ領域205に書き込み(S120
6)、キャッシュメモリのフォントデータ部201内部で、
未使用の管理単位メモリ202を捜す(S1207)。未使用の管
理単位メモリ202が発見できた場合は、先にアクセスし
た管理単位メモリ202の指標部203に、現在の管理単位メ
モリ202への指標を書き込み、新たな結合を生成する(S1
208)。続いてあふれ領域205から、１２６バイト（これ
は、管理単位メモリ202のデータ部204のサイズである）
のデータを取り出し、データ部204に書き込む(S1205)。
これを、あふれ領域205の内容が空になるか、未使用の
管理単位メモリ202が無くなるまで繰り返す。あふれ領
域205の残りデータが無くなった場合、書き込み処理は
正常終了する。この場合、最後に使用した管理単位メモ
リ202の指標部203の内容を、結合終了を示す値FFFFに書
き換え、結合の終端を生成する(S1209)。

【００５５】一方、未使用の管理単位メモリ202が必要
な数だけ検出できず、あふれ領域205にイメージデータ
が残っている場合は、書き込み処理211は、呼び出し側
の処理に書き込みエラーを返し(S1210)処理を中止す
る。この場合、不要な文字のデータをフォントキャッシ
ュメモリのフォントデータ部201から取り除き、空き領
域を広げ、再度書き込み処理211を呼び出す必要がある
が、この処理は、上位処理である呼び出し側（文字デー
タ登録処理502）において判断、実行される。

【００５６】あふれ領域205は、１文字のデータには充
分大きな容量を持つ連続したアドレスのメモリ領域であ
るが、もしあふれ領域205に入りきらない大きさの文字
のイメージデータが渡された場合は、書き込み処理211
はあふれ領域エラーを返し(S1211)処理を中止する。こ
の場合、この文字のイメージデータはフォントキャッシ
ュに登録されない。なぜなら、特に大きなイメージデー
タを持つ文字は、発生頻度が極めて低いため、キャッシ
ュに登録しても、システムの処理速度改善に寄与しない
ためである。

【００５７】連結解消処理212の処理を図１３の流れ図
を用いて説明する。

【００５８】データの削除された管理単位メモリ202、
あるいはデータの空白な管理単位メモリ202は、指標部2
03の値が０であることによって他の管理単位メモリ202
から区別される。連結解消処理212は、引数から管理単
位メモリ202への指標の値であるキーを取得し、さらに
アドレス変換処理214の呼び出しを行なう(S1301)。アド
レス変換処理214は、キー値を演算により実アドレスに
変換し、削除対象となる文字データの記録されている最
初の管理単位メモリ202を指し示すポインタを発生する
(S1302)。以下、連結解消処理212は、このポインタが示
す管理単位メモリ202の指標部203から次の管理単位メモ
リ202の先頭番地の実アドレスを計算し、後に続く指標
部203の内容を次々に0000で置き換える(S1304)。この操
作を管理単位メモリ202の連結が続く限り、指標部203の
内容が（１６進数で）FFFFである管理単位メモリ202に
至るまで繰り返す。このあと、連結の最終の管理単位メ
モリ202の指標部203の内容を、（１６進数で）FFFFから
0000に書き換える(S1305)。

【００５９】以上で、本実施例が使用したフォントキャ
ッシュ内のデータへのアクセス手段の説明を終わる。

【００６０】フォント管理機構が使用するフォントキャ
ッシュメモリ管理方法として、いくつか公知の方法が存
在する。基本的にフォントキャッシュメモリは、有限長
のメモリ割り当てであり、新たに文字のイメージデータ
を登録しようとし、メモリの空きスペースが確保できな
い場合は、現在の登録を更新する。すなわち、キャッシ
ュ領域から、不要なデータ（ここではどれかの文字のイ
メージデータ）を削除し、新規のデータを登録する。管
理方法として重要なのは、必要なデータを残し、不要な
データを削除することである。しかし、将来どのような
文字データに対する要求が発生するかを予測する理想的
な方法が無いため、何らかの基準に従い不要なデータを
決めることになる。この決定が適切であれば、要求文字
のデータが、キャッシュ領域に存在する確率（ヒット
率）が向上し、処理速度の向上につながる。不要なデー
タを決める代表的な管理方法は以下の４つである。

【００６１】方法１：現在のデータ群の中で、最も初期
に登録されたデータが不要と判断される。いわゆるFirs
t In First Out(FIFO)の方法。

【００６２】方法２：現在のデータ群の中で、最も長い
期間使用されなかったデータが不要と判断される。いわ
ゆるLeast Recently Used(LRU)の方法。

【００６３】方法３：現在のデータ群の中で、最も長い
期間使用されなかったデータはむしろ次に使用され、最
近使用されたデータが不要と判断される方法。

【００６４】方法４：現在のデータ群の中で、最も使用
頻度の低いデータが不要と判断される。いわゆるLeast
Frequently Used(LFU)の方法。

【００６５】従来方法の内、例えば特開昭６４−８８６
６０”フォントキャッシュ制御方式”は方法１に対し方
法３の改善を行った方法を用いている。また特開平２−
２０２４６４”印刷装置”は方法１を用いている。

【００６６】これら管理方式は、単一のフォント管理機
構に対し、単一のフォントキャッシュメモリを使用する
構成に対し発明された方法である。本発明の様な（バス
共有による）密結合のマルチマイクロプロセッサ方式で
は、各フォントキャッシュのデータ一致を確立するた
め、ローカルなフォントキャッシュと、共有されたフォ
ントキャッシュの管理が個々に行なわれる必要がある。

【００６７】本実施例は、キャッシュの局所的な管理に
おいてはLeast Recently Used(LRU)の方法を用いた。

【００６８】各マイクロプロセッサユニット1の並列実
行は、割り込み制御回路14の発生する割り込み信号によ
って制御される。以下図３の説明図と図４の状態遷移図
を用いて、これを説明する。

【００６９】本実施例の印刷装置制御回路において実行
されるプログラムは、複数のマイクロプロセッサユニッ
ト1により並列実行される。この時、個々のプロセッサ
の実行単位をプロセスと呼ぶ。プロセスは、プロセスヘ
ッダ、プログラムオブジェクト、作業領域から構成され
る。プロセスヘッダには、プロセスが（中断後の再開を
含め）開始される場合のプログラムカウンタの値、スタ
ックポインタの値、プロセッサの各レジスタの値、メモ
リサイズ、メモリ管理情報及びプロセス固有の管理情報
が含まれる。プロセスのオブジェクト部分は実行可能な
プログラムコードが含まれる。また、プロセスの作業領
域は、プロセス内の変数、スタック等に割り当てられ
る。実行時にはプロセスの実体は主記憶領域に配置され
る。本実施例では、共有ＲＡＭ4に図３に示す様なメモ
リ空間300をとり、ここにプロセス303、308、309等を配
置する。プロセスはプログラム実行中にカーネルに対す
るプロセス生成要求で生成され、終了により消失するの
で、実行時のプロセスの個数は不定である。

【００７０】本実施例の使用する各マイクロプロセッサ
ユニット1は、幾つかの”例外処理ベクタ”と呼ばれる
特定アドレスへのジャンプ機構を持っている。これら
は、例えば”割り込み処理が行なわれた場合ジャンプす
べきベクタ”、あるいは”リセット後にジャンプすべき
ベクタ”などである。電源投入直後全てのマイクロプロ
セッサユニット1は、リセット後のベクタで指定された
特定のアドレスの命令語を実行する。本実施例の場合、
この命令語は無限ループを生成し、各マイクロプロセッ
サユニットの処理は待機状態となる。図３の説明図上の
メモリ空間300に配置された領域301は、この無限ループ
が含まれる領域である。以下これを待機ルーチン301と
呼ぶ。

【００７１】次に、割り込み制御回路１４が、どれか一
つのマイクロプロセッサユニット1を選び、割り込み信
号を発生する。割り込みは、割り込み時のジャンプ先ア
ドレスを指定し行なわれる。この割り込みによってマイ
クロプロセッサユニット1のプログラムカウンタは、無
限ループの外の値に書き換えられる。ここではまず割り
込みディスパッチテーブルのカーネル領域へのジャンプ
命令を含むアドレスが指定され、ディスパッチルーチン
302へのジャンプが発生する。この結果、４個有るマイ
クロプロセッサユニット1の内のどれか一つは、カーネ
ルの処理306を開始する。

【００７２】カーネル処理306の動作は、図７の流れ図
に示される。カーネル処理306は、割り込みによってそ
の処理が開始されると直ちに、割り込みの発生時の要求
がＩ／Ｏ終了処理であるか判断する(S701)。この判断が
真であれば、Ｉ／Ｏ終了処理(S702)が実施される。S701
の判断が真でない場合およびS702の処理が終了した場合
は、待ち行列に処理要求があるか調べS703、処理要求が
有れば、要求内容を処理する(S704)。次にＩ／Ｏプロセ
ッサの処理状態を取得し(S705)、完了したＩ／Ｏ処理が
あれば、S701以降を繰り返す。待ち行列内の全ての処理
要求を処理したときは、判断S703が偽となり、処理を終
了し待機ルーチン301に戻る。

【００７３】カーネル処理を実行するマイクロプロセッ
サユニット1は、起動後最初の１回は、印刷処理プログ
ラムの開始プロセスの実行を割り当てる。具体的には、
プロセスの開始アドレスの値をディスパッチテーブルに
書き込み、割り込み制御回路14を使用し他のマイクロプ
ロセッサユニット1に割り込みを発生する。割り込み制
御回路14には、マイクロプロセッサユニット1の動作状
態を示すフラグ16が有り、待機ルーチン301にあるマイ
クロプロセッサユニット1についてはこのフラグの対応
するビットの値が１である。従って割り込み制御回路14
はこのフラグの値の監視により、待機中のマイクロプロ
セッサユニット1を特定し、これに割り込み信号を送
る。既にカーネルで動作中の他のマイクロプロセッサユ
ニット1によって、ディスパッチテーブルにジャンプ先
アドレスが書き込まれているため、ここで割り込み信号
が入力されたマイクロプロセッサユニット1のプログラ
ムカウンタは、指定アドレスに変更される。

【００７４】この結果、最初の印刷処理プログラムの起
動が行なわれると、後はこの印刷処理プログラムの処理
の流れに従い、全ての動作が行なわれる。印刷処理プロ
グラムは、インターフェース13を介し外部コンピュータ
から印刷制御コードを受信するプロセスを生成し、印刷
制御コードを受け取り印刷処理を行なう。この途中で、
文字形状発生、印刷画素の並べ換え、エンジン制御装置
10へのデータ完了信号の転送などが行なわれる。

【００７５】本実施例の制御回路が、マルチマイクロプ
ロセッサ構成であることから、ここに述べた様な個々の
処理にはそれぞれ独立の実行単位であるプロセスが割り
当てられる。特に、文字発生に関しては、改行コードの
入力が有る毎にプロセスの生成を行なう。一方で、この
文字発生のプロセスは、改行コードまでの、一連の文字
発生を全て行なうと、処理終了となり、プロセス終了要
求をカーネルの要求待ち行列にエンキュウする（待ち行
列に要素を追加する場合をエンキュウ、要素が除かれる
場合をデキュウと書く）。カーネルはこの要求があると
対象のプロセスをメモリ空間300から取り除き廃棄する
ので、プロセスの数は高々数十個である。図３の説明
図では、ある時間のメモリ空間とプログラム実行の状態
の例を挙げている。メモリ空間300には、この場合３つ
のプロセス303、308、309と、ディスパッチルーチン30
2、カーネルへの要求発生処理305、カーネル処理306、
Ｉ／Ｏ処理307及び更新処理304が存在する。メモリ空間
にはこの他に、大域的な（共有の）フォントキャッシュ
の領域315、インターフェースからの受信データを保存
するバッファ316が配置される。また、図３において右
向きの矢印は実行時間の推移を示し、下向きの矢印はメ
モリ配置上の上位アドレス方向を示す。さらに折れ線31
1、312、313はそれぞれマイクロプロセッサユニット1の
実行時のプログラムカウンタの値の変化を示す。

【００７６】この実施例において本発明の主な動作を実
現するのは更新処理304である。以下例を挙げこれを説
明する。既に実行中のプロセス303を処理しているマイ
クロプロセッサユニット1が、新たなプロセスを生成し
ようとする場合、プロセス生成要求をカーネルに対し行
なう。この要求は要求発生処理305を呼び出して行なわ
れる。折れ線312は、このためプログラムカウンタが一
時的に要求処理305の位置に書き変わることを示してい
る。矢印Ａの位置でプロセス生成要求を行なう。この要
求は、カーネルに対する要求待ち行列にエンキュウされ
る。カーネル処理306は別のマイクロプロセッサユニッ
ト1により実行されている。カーネル処理306（折れ線31
3で示す）はこの要求を取り出し、新たにプロセス308を
生成し、その実行開始番地をディスパッチルーチン302
内にあるディスパッチテーブルに書き込む。

【００７７】カーネル処理306を実行中のマイクロプロ
セッサユニット1は次に割り込み制御回路１４を用い、
現在待機中の別のマイクロプロセッサユニット1を特定
し、割り込み信号を送る。折れ線311はこの結果プロセ
ス308を実行するマイクロプロセッサユニット1のプログ
ラムカウンタの軌跡を示している。このマイクロプロセ
ッサユニット1は、割り込みを受けまずディスパッチル
ーチン302へジャンプし、プロセス308の実行開始アドレ
スにジャンプする。

【００７８】上記処理において待機中のマイクロプロセ
ッサユニット1が無い場合、カーネル処理は、待機状態
になるマイクロプロセッサユニット1が発生した時点
で、割り込み発生しプロセス実行を割り当てる。

【００７９】一方、先に折れ線312で示される処理を実
行しているマイクロプロセッサユニット1は、この例で
は次にＩ／Ｏ処理要求を発生する。既に図８の流れ図に
おいて説明したように、文字データをハードディスク装
置8から読み込む場合等が、この処理を伴う。このため
プログラムカウンタの軌跡である折れ線312は、再び要
求発生処理305に一時的に書き換えられる。

【００８０】本実施例において、全てのプロセスはＩ／
Ｏ処理に入るとプロセスの処理の継続を一旦中止し、待
機状態に戻る。これによってカーネルは、待機状態に入
ったマイクロプロセッサユニット1を、別のプロセスの
実行に割り当てることができる。なぜなら、Ｉ／Ｏ処理
は多くの場合数ミリ秒程度の待ちを生じるため、この
間、あるプロセッサがプロセス内で処理を継続するよ
り、他のプロセスに実行を移す方がプロセッサ資源の効
率的な使用にとり有利だからである。

【００８１】全てのプロセスは、上記の様にプロセスを
中断する場合、及びプロセスが終了した場合に、更新処
理304を実行する。更新処理304の処理内容は、プロセス
中断の場合は、プロセスの現在の状態を記録し、マイク
ロプロセッサユニット1の局所的なフォントキャッシュ2
の内容を更新することである。これは既に述べたよう
に、共有メモリ上のフォントキャッシュ315から、フォ
ント管理テーブル206とフォントデータ部201の内容を読
み出し、局所的なフォントキャッシュ2へ転送すること
で実現される。

【００８２】また、プロセス終了の場合は、更新処理30
4の処理内容は、プロセスの使用したメモリを開放し、
以下は同様にマイクロプロセッサユニット1の局所的な
フォントキャッシュ2の内容を更新することである。

【００８３】プログラムカウンタの軌跡である折れ線31
2は、矢印Ｂの位置で更新処理304を実行している様子を
示す。このマイクロプロセッサユニット1は、その後プ
ロセスを休止し待機ルーチン301の実行に戻る（図８のS
809を見よ）。この時、割り込み制御回路14のフラグ16
のこのマイクロプロセッサユニットに該当するビットの
値を１とし、待機状態に入ることを記録する。

【００８４】一方、Ｉ／Ｏプロセッサ6によりＩ／Ｏ処
理が終了すると、割り込み制御回路14によって待機中の
マイクロプロセッサユニット1に割り込み信号が送られ
る。この結果、折れ線312でプログラムカウンタの軌跡
が現されるマイクロプロセッサユニット1がカーネル処
理306の実行に入る。図７の流れ図で既に説明したよう
に、この場合まずＩ／Ｏ終了処理が行なわれる。従って
折れ線312は一時的にＩ／Ｏ処理307の領域に入る。ここ
でＩ／Ｏプロセッサ6の処理結果を取り出したカーネル
処理は、先ほど休止したプロセス303を再開する。ここ
では折れ線313で軌跡を示したマイクロプロセッサユニ
ット1が待機状態にあるため、カーネル処理306は割り込
み制御回路14によってこのマイクロプロセッサユニット
１に割り込み処理を行なう。この割り込み処理によっ
て、指定されたマイクロプロセッサユニット1はディス
パッチルーチン302を通り、プロセス303の前回休止した
番地から処理を再開する（図８のS810を見よ）。これは
矢印Ｃで示される位置である。

【００８５】以上が本実施例における並列実行及び更新
処理304の動作の流れである。

【００８６】次に、更新処理304について、別の実施例
をあげる。

【００８７】前述の実施例において、更新処理304は、
共有メモリ上のフォントキャッシュ315から、フォント
管理テーブル206の全てと、フォントデータ部201の全て
を局所的なフォントキャッシュ2のフォント管理テーブ
ル206およびフォントデータ部201に転送するものであっ
た。これは、フォント読み込み、登録の各処理におい
て、共有変数であるアクセスカウンタ508をインクリメ
ントした後、フォント管理テーブル206の登録フラグ207
を更新する際に、大域的な（共有の）フォント管理テー
ブル206に対してだけ操作を行なうためである。

【００８８】しかし、共有メモリ上のフォントデータ部
201の内容全部を、局所メモリに転送する処理は、処理
速度の点から見て、あるサイズ以上のフォントキャッシ
ュの使用を困難とする。極めて大きなサイズ（１Ｍバイ
ト以上）のフォントキャッシュを実装したい場合、より
効果的な転送を行なうべきである。これを実現するため
に、別の実施例として次の部分を変更することが考えら
れる。

【００８９】まず図８の文字データ取得処理501の流れ
図の中で、登録フラグ更新(S805)を、共有メモリ4上の
フォント管理テーブル206及び局所フォントキャッシュ2
上のフォント管理テーブル206の双方に対して行なう様
に変更する。また、図９の文字データ登録処理502の流
れ図の中で、登録フラグ更新(S906)を、共有メモリ4上
のフォント管理テーブル206及び局所フォントキャッシ
ュ2上のフォント管理テーブル206の双方に対して行なう
様に変更する。

【００９０】これによって更新処理304は図１４の流れ
図の様に行なうことができる。すなわち、共有メモリ上
のフォント管理テーブル206と、フォントキャッシュ2上
のフォント管理テーブル206の内容を個々に比較する(S1
401)。共有メモリ上のフォント管理テーブル206の登録
フラグ207が、フォントキャッシュ2上のフォント管理テ
ーブル206の同位置の登録フラグより新しい（値が大き
い）場合は、共有メモリのフォント管理テーブル206の
この要素（207,208,209全て）を、フォントキャッシュ2
上のフォント管理テーブル206の同位置に転送する(S140
2)。次にこの位置のキーを取り出し、フォントデータ部
201でのフォントデータの開始位置の管理単位メモリ202
の最初のアドレスを計算する(S1403)。さらに、共有メ
モリ4上のフォントデータ部201から、管理単位メモリ20
2の内容を、一文字のデータ全てについて連結リストに
従い順次読み出し、フォントキャッシュ2上のフォント
データ部201の同位置にオーバーライトする(S1404)。こ
の時、削除処理は不要である。続いてフォント管理テー
ブル206の終了かどうかを判断し(S1405)、（Ｓ１４０
１）以降の処理をテーブル終了まで繰り返す。この処理
では、フォントキャッシュの内容が安定し新たな文字の
登録の頻度が下がるにつれ、更新処理３０４の処理時間
が短縮される。

【００９１】以上に述べた様な更新処理304を伴うプロ
セス管理によって、本実施例の印刷装置においては、複
数個のマイクロプロセッサユニット1の局所的なフォン
トキャッシュ2の内容を、それぞれ一致させることがで
きる。この一方で、プロセス実行中はフォントキャッシ
ュ2からのデータ読み込みは、共有メモリ空間へのアク
セスを発生しないことによって高速に行なうことができ
る。

【００９２】すなわち本実施例が示したのは、書き込み
動作を伴うフォント登録は共有メモリに行ない、読み込
みは局所メモリだけから行なうフォント管理方法であ
る。フォントをフォントキャッシュに登録する際、局所
メモリへの書き込みも行なわないため、メモリアドレス
管理は簡単であり、局所メモリ、共有メモリの配置上の
制約が少なく柔軟である。

【００９３】また、上記実施例での構成において、図１
のエンジン制御装置10及びプリントエンジン11の部分
を、グラフィックコントローラおよびＣＲＴ装置等にそ
れぞれ置き換えることによって、そのまま表示装置、ワ
ークステーション等の機器に適用できることは言うまで
もない。

【００９４】

【発明の効果】以上の実施例において明らかなように、
マルチプロセッサ構成の処理装置において、個々のマイ
クロプロセッサに局所的なフォントキャッシュを配置し
た場合、本発明の文字データ管理手段によって、キャッ
シュ内のデータ一致性を保つのは容易である。加えて本
発明は、付加的なハードウェア無しに、フォントキャッ
シュの一致を図る解決手段であり、装置コスト面で効果
が大きい。

【００９５】個々の局所的なフォントキャッシュの内容
がほぼ一致しているので、どの様なプロセスの割り当て
が行なわれても、ある水準以上のキャッシュのヒット率
を確保できるという効果がある。

【００９６】また、局所的なフォントキャッシュに該当
する文字データが無い場合であっても、まず大域的なフ
ォントキャッシュの管理テーブルの参照が行なわれれる
ため、他のプロセスが既に作成し登録した文字データが
有れば使用可能である。これは、同一文字のアウトライ
ンフォント元データを複数のプロセスがハードディスク
装置から読み取ろうとする処理の重複を防ぐ効果があ
り、結果的に、Ｉ／Ｏ処理がボトルネックとなることを
解消する効果がある。

【図面の簡単な説明】

【図１】本発明の実施例のブロック図。

【図２】フォントキャッシュシステムの説明図。

【図３】マルチプロセッサ処理の説明図。

【図４】マルチプロセッサ処理の状態遷移図。

【図５】文字データ取得処理の概略構成図。

【図６】フォント管理テーブル内の一要素のデータ構造
説明図。

【図７】カーネル処理の流れ図。

【図８】文字データ取得処理の流れ図。

【図９】文字データ登録処理の流れ図。

【図１０】文字データ削除処理の流れ図。

【図１１】読み出し処理の流れ図。

【図１２】書き込み処理の流れ図。

【図１３】連結解消処理の流れ図。

【図１４】更新処理304の別実施例の流れ図。

【符号の説明】

１…マイクロプロセッサユニット２…フォントキャッシュ３…グローバルバス４…共有ＲＡＭ５…共有ＲＯＭ６…Ｉ／Ｏプロセッサ７…ディスク制御装置８…ハードディスク装置９…イメージメモリ１０…エンジン制御装置１１…プリントエンジン１２…バス調停制御回路１３…インターフェース１４…割り込み制御回路１５…バス調停回路１６…マイクロプロセッサユニット1の動作状態を示す
フラグ２０１…フォントデータ部２０２…管理単位メモリ２０３…指標部２０４…データ部２０５…あふれ領域２０６…フォント管理テーブル２０７…登録フラグ２０８…文字指定レコード２０９…キーの値（指標）２１０…読み出し処理２１１…書き込み処理２１２…削除処理３００…メモリ空間３０１…待機ルーチン３０２…ディスパッチルーチン３０３、３０８、３０９…プロセス３０４…更新処理３０５…要求発生処理３０６…カーネル処理３０７…Ｉ／Ｏ処理３１５…共有フォントキャッシュ領域５０１…文字データ取得処理５０２…文字データ登録処理５０３…連結解消処理

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁵ 識別記号庁内整理番号ＦＩ技術表示箇所Ｇ０９Ｇ 5/22 9061−5Ｇ

Claims

【特許請求の範囲】

【請求項１】複数のプロセッサと、該プロセッサから
共通にアクセス可能な共有フォントキャッシュと、前記
プロセッサから共通にアクセス可能なアウトラインフォ
ント供給部と、前記プロセッサ個々にアクセス可能な局
所フォントキャッシュとを有し、プロセス実行時の文字の取得要求に対し、まず局所的フ
ォントキャッシュからの読み取りを試み、あればこれを
読み取り、なければ共有フォントキャッシュからの読み
取りを試み、更にない時は、アウトラインフォント供給
部から元データを読み込み文字画素データを生成し、共
有フォントキャッシュに登録する。実行時のプロセス終
了あるいは休止時には、共有フォントキャッシュの内容
を局所的フォントキャッシュに転送し、個々のフォント
キャッシュの内容を更新することを特徴とする文字デー
タ管理装置。