(57)【特許請求の範囲】
【請求項１】
複数のジョブを構成する複数の原画書類を走査及び処理し、同時に印刷するための電子複製装置であって、
前記複数のジョブ内の少なくとも１つのジョブを構成する一組の原画書類を走査する走査装置手段と、
前記走査済みの書類の画像データを記憶する記憶手段であって、該記憶手段は、現在の処理のための画像データを記憶する主メモリと、後続の処理のための画像データを記憶するディスクメモリとを含み、前記主メモリの記憶容量が前記ディスクメモリの記憶容量よりも小さい、記憶手段と、
前記主メモリ内に記憶された画像データのコピーを印刷する印刷装置手段と、
前記走査装置手段と記憶手段と印刷装置手段の動作を制御し、及び前記主メモリとディスクメモリとの間で画像データを転送するシステムマネージャ手段と、
前記システムマネージャ手段によって作動させられる資源マネージャ手段とから成り、
該資源マネージャ手段は、前記印刷装置手段が前記主メモリに記憶されていないが前記ディスクメモリに記憶されている画像データを要求するときであって前記主メモリの記憶容量が前記要求された画像データを受容するのに不十分であるとき、前記要求された画像データを受容するために、前記主メモリに記憶されている最新に印刷された画像データを前記主メモリから除去するように前記ディスクメモリへ転送する構成であり、
更に、（１）原画書類に対応する画像データを前記印刷装置手段が要求する時間と当該原画書類に対応する画像データを該印刷装置手段が印刷する時間とをスケジューリングする、前記資源マネージャ手段と協働する長期スケジューラと、
（２）前記長期スケジューラから呼出されて、前記スケジューリングに従って前記主メモリから前記最新に印刷された画像データを除去する、前記資源マネージャ手段と協働するメモリスワッパとが設けられ、
前記メモリスワッパは、前記主メモリにある最新に印刷された、１ページに相当する画像データを前記主メモリから除去する
ことを特徴とする電子複製装置。
【請求項２】
複数のジョブを構成する複数の原画書類を走査及び処理し、同時に印刷するための電子複製装置であって、
前記複数のジョブ内の少なくとも１つのジョブを構成する一組の原画書類を走査する走査装置手段と、
前記走査済みの書類の画像データを記憶する記憶手段であって、該記憶手段は、現在の処理のための画像データを記憶する主メモリと、後続の処理のための画像データを記憶するディスクメモリとを含み、前記主メモリの記憶容量が前記ディスクメモリの記憶容量よりも小さい、記憶手段と、
前記主メモリ内に記憶された画像データのコピーを印刷する印刷装置手段と、
前記走査装置手段と記憶手段と印刷装置手段の動作を制御し、及び前記主メモリとディスクメモリとの間で画像データを転送するシステムマネージャ手段と、
前記システムマネージャ手段によって作動させられる資源マネージャ手段とから成り、
該資源マネージャ手段は、前記印刷装置手段が前記主メモリに記憶されていないが前記ディスクメモリに記憶されている画像データを要求するときであって前記主メモリの記憶容量が前記要求された画像データを受容するのに不十分であるとき、前記要求された画像データを受容するために、前記主メモリに記憶されている最新に印刷された画像データを前記主メモリから除去するように前記ディスクメモリへ転送する構成であり、
更に、（１）原画書類に対応する画像データを前記印刷装置手段が要求する時間と当該原画書類に対応する画像データを該印刷装置手段が印刷する時間とをスケジューリングする、前記資源マネージャ手段と協働する長期スケジューラと、
（２）前記長期スケジューラから呼出されて、前記スケジューリングに従って前記主メモリから前記最新に印刷された画像データを除去する、前記資源マネージャ手段と協働するメモリスワッパとが設けられ、
各画像が複数のセグメントで構成され、前記メモリスワッパは、前記主メモリにある最新に印刷された、１つ又はそれ以上のセグメントに相当する画像データを前記主メモリから除去する
ことを特徴とする電子複製装置。
【請求項３】
請求項１又は２に記載の電子複製装置において、前記長期スケジューラは、前記印刷装置手段が１つの原画書類に対応する画像データを要求する時間と前記原画書類に対応する画像データを印刷する時間との間の所定のオフセット時間をスケジューリングする
ことを特徴とする電子複製装置。
【請求項４】
請求項１又は２に記載の電子複製装置において、前記長期スケジューラは、少なくとも１セットの原画書類の印刷の前に、該原画書類に対応する画像データを前記ディスクメモリから検索するのに必要な前記主メモリの記憶容量をスケジューリングする
ことを特徴とする電子複製装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は電子複写装置に関し、特に、電子印字装置及び電子複写装置に用いるための資源管理アルゴリズム及びメモリ管理アルゴリズムに関する。本発明の資源管理アルゴリズムは印字装置のページメモリ及びディスク記憶を最適に管理及び割当てするためのものである。本発明においては３つのスケジューリングアルゴリズム、即ち、オフセットアルゴリズム、アドバンストスケジューリングアルゴリズム、及び連続セットスケジューリングアルゴリズムを用いる。前記オフセットアルゴリズムは、画像要求時と印字時との間に短い時間（ピッチ）を許すものであり、前記アドバンストスケジューリングアルゴリズムは、予め若干数のページをスケジュールすることにより、印字に先立って印字セット内の画像を検索するために必要に応じてディスクをスケジュールするためのものであり、前記連続セットスケジューリングアルゴリズムは、前記アドバンストスケジューリングアルゴリズムの変形であり、セット相互間のスキップ数を減少させるために連続セットに対してメモリ使用及びディスクをスケジュールするものである。本発明は更に一群のメモリ管理スワッピングアルゴリズムに関し、ピッチスキップ数を減少し、及びターンアランドタイムを改善するため、利用可能なメモリ及びディスク帯域幅の資源に依存してこのアルゴリズムから最適戦略を選択することができる。
【０００２】
【従来の技術】
データ管理装置のスループットを改善するためのデータ管理装置及び方法が米国特許第4,241,420 号及び第4,339,503 号に開示されている。米国特許第4,241,420 号には、転送の遅延をさけるため、ディスクメモリとＲＡＭメモリとの間のデータの転送を監視するための制御装置が開示されている。米国特許第4,339,503 号においては、ディスクメモリと高速限定容量ＲＡＭメモリとの間のデータの転送を制御するための制御装置が開示されている。
【０００３】
電子印字装置のためのメモリ管理装置に関する更に他の技術が知られている。即ち、米国特許第4,910,611 号には対話型画像処理のための方法が開示されており、種々の操作が画像に対して実行される。効率を高くするため、各指令を解析し、指令を完了するためには画像のどの部分が必要であるかを決定する。更に、メモリスワッピングを用いることにより、主メモリと補助ディスクメモリとの間のメモリ転送を避ける。米国特許第4,445,195 号には可変長ピクチャ情報の記録装置が開示されており、ピクチャ画像が走査されて装置に入力され、ディスクに記憶される。このピクチャをメモリから検索し、印字することができる。該当する画素の長さが実際のデータと一緒に記憶される。従って、このピクチャの長さを測定するのが簡単である。米国特許第4,511,928 号には、画像を走査及び記憶することのできる高品質画像複写のための装置及び方法が開示されている。記憶印字並行機能を含む複写装置の全ての操作を制御するための２つのプロセッサが設けられている。
【０００４】
米国特許第4,894,646 号には画像処理装置内で画像を操作するための画像処理用装置及び方法が開示されており、この装置内の各画像は複数の下位画像に再分割され、これら下位画像は互いに独立に処理される。この米国特許は大形のディジタル画像の効率的な処理に関するものである。即ち、画像を処理しつつあるプロセッサのメモリの容量が不足であるか、またはプロセッサのアドレス能力が画像データの取扱いに不十分であるか、またはこれら両方であるというような大形画像の処理に関するものである。この装置に記憶されている画像は二次記憶装置に保持され、この画像の一部分だけが、随時、一次記憶装置における操作に用いられる。或る画像の操作は、一次記憶装置と二次記憶装置との間のデータスワップを最小にする変形された最長時間未使用（ＬＲＵ）アルゴリズムによって決定される。
【０００５】
【発明が解決しようとする課題】
本発明の目的は、印字装置のページメモリ及びディスク記憶装置を最適に管理及び割当てする装置を提供することにある。
本発明の他の目的は、オフセットアルゴリズムにより、ページメモリ及びディスク記憶装置を最適に管理及び割当てすることにある。
【０００６】
本発明の更に他の目的は、アドバンストスケジューリングアルゴリズムにより、ページメモリ及びディスク記憶装置を最適に管理及び割当てすることにある。本発明の更に他の目的は、連続セットスケジューリングアルゴリズムにより、ページメモリを最適に管理及び割当てすることにある。
本発明の更に他の目的は、ピッチスキップを減少し及びターンアラウンドタイムを改善するために利用することのできるメモリ及びディスク帯域幅の資源に依存して最適戦略を選択することのできるようにする一群のメモリ管理スワッピングアルゴリズムを提供することにある。
【０００７】
【課題を解決するための手段】
本発明の前記及び他の目的及び利点は、入出力手段をメモリ手段に接続させている電子複写装置のためのものである。前記メモリ手段は走査バッファ手段及び印字バッファ手段を具備し、前記印字バッファ手段は記憶手段に接続される。メモリ／ディスク帯域幅手段が更に設けられ、これは、入出力手段、ユーザインタフェース手段、長期スケジューリングテーブル手段、及び資源データベース手段とインタフェースさせられる。
【０００８】
前記複写装置は走査管理手段を更に具備し、この管理手段は、システムマネージャ、長期スケジューリングテーブル手段、走査短期スケジューリング手段、資源マネージャ手段、及び入力手段とインタフェースさせられる。印字マネージャ手段が更に設けられ、これは、出力手段、システムマネージャ手段、長期スケジューリングテーブル手段、及び資源マネージャ手段とインタフェースさせられる。
【０００９】
前記の資源管理手段は、ディスクマネージャ手段、走査マネージャ手段、印字マネージャ手段、印字短期スケジューリング手段、資源データベース手段、及び印字短期スケジューリング手段とインタフェースさせられる。前記の印字長期スケジューリング手段は、長期スケジューリングテーブル手段、及び印字メモリスワッパ手段とインタフェースさせられる。
【００１０】
３つのスケジューリングアルゴリズムを本発明におけるハードウェアとともに用いる。その内の一つのオフセットアルゴリズムであり、他の一つはアドバンストスケジューリングアルゴリズムであり、第３のものは連続セットスケジューリングアルゴリズムである。電子印字及び／又は複写装置を、前記スケジューリングアルゴリズムの１つ、２つ、または全部を使用するようにプログラムすることができる。
【００１１】
以下、本発明を図面について詳細に説明する。図面において、同様参照番号は同様部材を示す。
【００１２】
【実施例】
Ａ、装置、
図１及び図２について説明すると、図は本発明の教示に従って印字ジョブを処理するためのレーザ式印字装置２を例示するものである。印字装置２を、説明の都合上、走査装置部６、制御装置部７、及び印字装置部８に分割する。本明細書においては格別の印字装置を図示してこれについて説明を行なうが、本発明は、インクジェット式、粒子線写真式、等の他の形式の印字装置に対しても用いることができる。
【００１３】
図２ないし図４について説明すると、走査装置部６は透明プラテン２０を有し、走査すべき書類２２がその上に載せられる。１つまたは複数の線形アレイ２４が、プラテン２０に下で往復走査移動するように支持されている。レンズ２６及びミラー２８、２９、３０が協同し、プラテン２０の線状セグメント及びその上で走査される書類の上にアレイ２４を合焦させる。アレイ２４は、走査された画像を表す画像信号または画素を提供し、この画像信号は、プロセッサ２５による適当な処理の後、制御装置部７へ出力される。
【００１４】
プロセッサ２５はアレイ２４によって出力されたアナログ画像信号をディジタル信号に変換し、この画像信号を要求に従って処理して装置２をイネーブルし、プログラムされたジョブを実行するのに必要な形式で前記画像データを記憶及び操作する。プロセッサ２５はまた、画像信号に対して、フィルタリング、しきい値処理、スクリーニング、クロッピング、縮小／拡大、等のような強調及び変更を加える。ジョブプログラムに何らかの変更及び調整を加えた後には、書類を再走査する。
【００１５】
走査すべき書類２２をプラテン２０に載せ、再循環式書類取扱（ＲＤＨ）モードまたは半自動書類取扱（ＳＡＤＨ）モードで動作可能な自動書類取扱（ＡＤＨ）３５によって走査する。ブック（Book) モードを含む手動モード及びコンピュータフォームズフィーダ（Computer Forms Feeder)（ＣＦＦ）モードも提供され、ＣＦＦモードにおいては書類はコンピュータ用折りたたみ用紙の形式で受け入れられる。ＲＤＨモード動作のため、書類取扱装置３５は書類トレイ３７を有し、このトレイ内に書類２２がスタックまたはバッチとして配置される。トレイ３７内の書類２２は真空式送りベルト４０及び書類送りローラ４１及び書類送りベルト４２によってプラテン２０上に送られ、このプラテンにおいて書類はアレイ２４によって走査される。走査の後、書類はベルト４２によってプラテン２０から取り出され、書類送りローラ４４によってトレイ３７へ戻される。
【００１６】
ＳＡＤＨモードの動作に対しては、書類入り口スロット４６が、トレイ３７とプラテン２０との間にある書類送りベルト４２に対する接近を提供する。即ち、個々の書類が前記スロットに手で差し込まれ、プラテン２０へ運ばれる。スロット４６の後ろにある送りローラ４９はニップを形成し、書類に係合してこれを送りベルト４２へ及びプラテン２０上へ送る。走査の後、書類はプラテン２０から取り出され、キャッチトレイ４８内に排出される。
【００１７】
ＣＦＦモードの動作に対しては、コンピュータ形式の材料をスロット４６を通して送り、送りローラ４９によって書類送りベルト４２へ送る。この書類送りベルトは前記コンピュータ形式の折りたたみ材料の一つのページをプラテン２０上の所定位置へ送る。
図２及び図３について説明すると、印字装置部８はレーザ式印字装置を有す。この印字装置部８を、説明の都合上、ラスタ出力走査装置（ＲＯＳ）部８７、印字モジュール部９５、用紙供給部１０７、及び仕上げ装置１２０に分割する。ＲＯＳ  ８７はレーザ９１を有す。このレーザのビームは２つの画像形成用のビーム９４に分割される。各ビーム９４は、音響光学変調装置９２により、入力される画像信号の内容に従って変調され、二重画像形成用ビーム９４を提供する。ビーム９４は、回転式多角形体１００の鏡面ファセットにより、印字モジュール部９５の移動式感光体９８を横切って走査させられ、各走査で感光体９８上の２つの画像線画を露光し、変調装置９２へ入力される画像信号によって表される静電潜像を作る、感光体９８は、画像形成ビーム９４による露光の準備として、帯電ステーションにおいてコロトロン１０２によって一様に帯電させられる。前記静電潜像は現像装置１０４によって現像され、そして転写ステーション１０６において、用紙供給部１０７によって送り出される印字媒体１０８へ転写される。媒体１０８は、種々のシートサイズ、形式、及び色彩の任意のものであってよい。転写のため、印字媒体は、主用紙トレイ１１０から、または補助用紙トレイ１１２もしくは１１４から、感光体９８上の現像済み画像と時間的に整合して送り出される。印字媒体１０８へ転写された現像済み画像は定着装置１１６によって永久的に固着または定着させられ、その結果できた印字物は出力トレイ１１８へ、または仕上げ装置１２０へ排出される。仕上げ装置１２０は、印字物を互いに縫い綴じまたはステープル綴じして書籍を形成するためのスティッチャ１２２、及び印字物を接着剤で結着して書籍にするための熱式製本装置１２４を有す。前記印字装置は、印字される書類データを記憶するためのメモリ（図示せず）を有している場合もある。
【００１８】
図１、図２、図５、図６及び図７について説明すると、制御装置部７を、説明の都合上、画像入力制御装置５０、ユーザインタフェース（ＵＩ）５２、システム制御装置またはＥＳＳ  ５４、主メモリ５６、画像操作部５８、及び画像出力制御装置６０に分割する。
図５ないし図７について詳細に説明すると、制御装置部７は複数のプリント配線盤（ＰＷＢ）７０（ＰＷＢ  ７０−１ないし７０−１０をまとめて示す）を有す。ＰＷＢ  ７０は、１対のメモリバス７２、７４により、互いに、及びシステムメモリ６１に接続される。メモリ制御装置７６がシステムメモリ６１をバス７２、７４と接続させる。ＰＷＢ  ７０としては、複数のシステムプロセッサ７８を有するシステムプロセッサＰＷＢ−１、及び、ＵＩ  ５２とデータをやりとりするためのＵＩ通信制御装置８０を有する抵速入出力プロセッサＰＷＢ  ７０−２、及び、主メモリ５６のディスク９０−１、９０−２、９０−３とそれぞれデータをやりとりするためのディスク駆動制御装置／プロセッサ８２を有するＰＷＢ  ７０−３、７０−４、７０−５（画像データを圧縮するための画像圧縮装置／プロセッサ５１はＰＷＢ  ７０−３上にある）、及び、画像操作部５８の画像操作プロセッサを有する画像操作ＰＷＢ  ７０−６、及び、印字装置部８によって印字するために画像データを処理するための画像発生プロセッサ８６を有する画像発生プロセッサＰＷＢ  ７０−７、７０−８、及び、印字装置部８とのデータのやりとりを制御するためのディスパッチプロセッサ８８、８９を有するディスパッチプロセッサＰＷＢ  ７０−９、及び、ブート制御調停スケジューラＰＷＢ  ７０−１０がある。
【００１９】
走査装置部６のプロセッサ２５から制御装置部７に入力された走査済み画像データは、ＰＷＢ  ７０−３上の画像入力制御装置５０の画像圧縮装置／プロセッサ５１によって圧縮される。画像データが圧縮装置／プロセッサ５１を通過するにつれ、該画像データはＮ走査線幅のスライスにセグメント化される。各スライスはスライスポインタを有す。圧縮済み画像データは、スライスポインタとともに、及び画像特定情報（画素単位で計った書類の高さ及び幅、使用した圧縮方法、圧縮済みの画像データに対するポインタ、及び画像スライスポインタに対するポインタのような）を提供する関連の全ての画像記述子とともに、画像ファイルに入れられる。相異なる印字ジョブを表すこの画像ファイルは、ランダムアクセスメモリまたはＲＡＭを具備するシステムメモリ６１に一時的に記憶され、主メモリ５６への転送を待つ。この主メモリにおいてデータは使用待ち状態に保持される。
【００２０】
図１に示すように、ＵＩ  ５２は、会話形タッチスクリーン６２、キーボード６４、及びマウス６６から成る組合せ形のオペレータ制御装置／ＣＲＴディスプレイを有す。ＵＩ  ５２はオペレータを印字装置２とインタフェースさせ、オペレータが印字ジョブ及び他の命令をプログラムし、システムオペレーティング情報、命令、プログラミング情報、診断情報、等を得ることのできるようにする。タッチスクリーン６２に表示されるファイル及びアイコンのような項目は、スクリーン６２に表示されている項目に指で触れることにより、またはマウス６６を用いてカーソル６７を選択項目に向けてマウスをキーイングすることにより、作動させられる。
【００２１】
主メモリ５６は、マシンオペレーティングシステムソフトウェア、マシンオペレーティングデータ、及び現在処理中の走査済み画像データを記憶するための複数のハードディスク９０−１、９０−２、９０−３を有す。
主メモリ５６内の圧縮済み画像データが更に処理を要求するとき、またはＵＩ５２のタッチスクリーン６２上の表示を要求されるとき、または印字装置部８によって要求されるとき、前記データは主メモリ５６内でアクセスされる。プロセッサ２５によって提供されのもの以外の更に他の処理が要求される場合には、前記データはＰＷＢ７０−６上の画像操作部５８へ転送され、このＰＷＢにおいて、丁合、準備、分解、等の追加の処理ステップが実行される。処理の後、前記データは主メモリ５２へ戻され、タッチスクリーン６２上の表示のためにＵＩ  ５２へ送られ、または画像出力制御装置６０へ送られる。
【００２２】
画像出力制御装置６０へ出力された画像データは圧縮解除され、ＰＷＢ  ７０−７、７０−８（図５）の画像発生プロセッサ８６による印字のために準備される。その後、データはＰＷＢ  ７０−９上のディスパッチプロセッサ８８、８９によって印字装置部８へ出力される。印字のために印字装置部８へ送られた画像データは、通例、新しい画像データのための場所を作るためにメモリ５６から排除される。
【００２３】
図８について説明すると、システム制御信号は複数のプリント配線盤（ＰＷＢ）を介して分配される。これらＰＷＢとして、ＥＤＮコアＰＷＢ  １３０、マーキングイメージング（ＭＩＮ）コアＰＷＢ  １３２、用紙取扱（ＰＨＮ）コアＰＷＢ  １３４、仕上製本（ＦＢＮ）コアＰＷＢ  １３６、及び種々の入出力（Ｉ／Ｏ）ＰＷＢ  １３８がある。システムバス１４０が、コアＰＷＢ  １３０、１３２、１３４及び１３６を、互いに及び制御装置部７に接続し、ローカルバス１４２が、Ｉ／Ｏ  ＰＷＢ  １３８を、互いに及びその関連のコアＰＷＢに接続する。
【００２４】
マシンパワーアップすると、オペレーティングシステムソフトウェアがメモリ５６からＥＤＮコアＰＷＢ  １３０へ、そしてそこからバス１４０を介して残りのコアＰＷＢ  １３２、１３４及び１３６へロードされる。各コアＰＷＢ  １３０、１３２、１３４、１３６は、ＰＷＢへのオペレーティングシステムソフトウェアのダウンロード、故障検出、等を制御するためのブートＲＯＭ  １４７を有す。ブートＲＯＭ  １４７はまた、バス１４０を介するＰＷＢ  １３０、１３２、１３４、１３６への及びこれからのオペレーティングシステムソフトウェア及び制御データの伝送、ならびにローカルバス１４２を介するＩ／Ｏ  ＰＷＢ  １３８への及びこれからの制御データの伝送を可能にする。追加のＲＯＭ、ＲＡＭ、及びＮＶＭ型のメモリが装置２内の種々の場所に配置されている。
【００２５】
図９について説明すると、ジョブはジョブプログラムモードにプログラムされ、プログラム中のジョブに対するジョブティケット（Job Ticket) １５０及びジョブスコアカード（Job Scorecard)１５２がタッチスクリーン６２上に表示される。ジョブティケット１５０はプログラムされる種々のジョブ選択を表示し、ジョブスコアカード１５２はジョブを印字するための装置に対する基本命令を表示する。
Ｂ、資源管理
以下の説明において、制御装置７を電子工学サブシステム（ＥＳＳ）と呼び、走査装置を画像入力端末装置（ＩＩＴ）と呼び、印字装置を画像出力端末装置（ＩＯＴ）と呼ぶ。
【００２６】
効率的な資源管理、十分な電子工学サブシステム（ＥＳＳ）メモリ、及び十分なディスク帯域幅は、電子複写（ＥＲ）システム及び電子印字システムの性能の最適化に関する３つの重要なシステムパラメータである。システム性能は、ジョブ当たりの平均ターンアラウンドタイムを最小にしてジョブスループットを増加させることにより、及びジョブ当たりの印字ピッチスキップの平均比率を最小にしてマシンの消耗部品を効率的に使用することによって改善される。
【００２７】
ピッチスキップは、システムが全実行モード（感光体の帯電及び放電）になっているが用紙シートに画像形成がなされていないという時間である。印字ピッチスキップの数を最小にすること、及び／又はピッチスキップの数を所定範囲内に保持することが、ターンアラウンドタイムを改善し及びマシンの消耗部品を効率的に使用する際の１つの要点である。
【００２８】
本発明のモデルを作る際に用いられるＥＲシステム構成は図１０に示すシステムの走査／マーク部である。例示の基本ＥＳＳアーキテクチャは、走査装置（６）または入力装置（ＩＩＴ）と接続された限定容量のメモリ、印字装置（８）または出力装置（ＩＯＴ）、及び硬式スプールディスクから成る。入力装置、出力装置、及びディスク駆動装置がそれらの特定機能を実施するためにそれら自体の制御装置を有しているにしても、全数４つの構成部材が資源マネージャによって管理される。例えば、書類の機械的走査に関して資源マネージャが走査装置を制御しないにしても、資源マネージャは、動作を開始するのに十分なメモリを提供しないことにより、走査装置が走査開始することができる時を制限する。
【００２９】
図１０について説明すると、ＥＳＳ  ２００は、スプールディスク２０４に接続された走査／記憶／マークチャネル２０２とインタフェースさせられるＩＩＴ／ＩＯＴインタフェースボード２０１を有す。ＥＳＳ  ２００は更に、ビデオ発生チャネル２０６、ビデオ発生チャネル２０８、及びフォントディスク２１２に接続されたチャネル２１０に接続されている。
【００３０】
本発明を実施する際のＥＳＳの１つの機能は、システムが走査／印字ジョブを受容及び実行することを可能にすることである。走査／印字機能の３つの基本ステップは、（１）原画のセットを走査してメモリに入力すること、（２）各原画を圧縮済みビットマップとしてスプールディスクに記憶させること、及び（３）原画のセットの所望数のコピーを印字することである。この資源管理アルゴリズムは前記３つのステップの各々を同時に実施するために開発されたものである。詳述すると、前記３つのステップの同時性により、このシステムは、画像を走査しながら画像をディスクに記憶させ及び画像を印字することができる。入力装置及び出力装置の速度を等しくすることができるので、原画が走査されてメモリに記憶されると直ちに最初の画像の印字が開始することができる。試験を行なったところ、入力装置は１分間当たり１００画像の速度で機能し、出力装置は１分間当たり１００ページの速度で機能した。しかし、本発明は、印字装置が走査速度よりも早く速度で働くシステムにも適用可能である。
【００３１】
システム内のメモリの量が制限されているので、現在メモリ内に存在していないでスプールディスクに記憶されている画像をメモリに入れることをシステムが要求するが、圧縮済みビットマップ形式の画像を保持するために利用できる十分なメモリがないという時点が来る。そこで、資源マネージャは、到来画像のための場所を作るために、現在メモリ内にあるページのうちのどれをメモリから除去するのが最もよいかを決定することが必要となる。目標は、性能に対する影響がほとんど無いか皆無である画像を除去することである。
【００３２】
また、ＥＳＳは、ディスクの速度と圧縮不十分なページとが組合わさるために印字に所要な画像をＩＯＴに提供することができなくなる可能性がある。圧縮不十分なページを印字に間に合うようにメモリに入れるのに十分なディスク帯域幅がないという可能性がある。従って、各ジョブは或る数の印字ピッチスキップを招く可能性がある。従って、各ジョブは或る数の印字ピッチスキップを招来する可能性がある。
【００３３】
印字ピッチスキップを最少にするため、最小限必要な資源、及びこれら限定資源を管理するための最適戦略を決定することが必要である。前述の説明に従い、メモリの大きさ及びディスク帯域幅の可能範囲を見積もった。６種類のディスク帯域幅、即ち、6.５、7.５、8.５、１２、１３及び１５メガビット／秒を選択した。８種類のメモリ大きさ、即ち、１６、２０、２４、３２、４８、６４、９６及び１２８メガバイトを選択した。このモデルを４８種類のディスク帯域幅／メモリ構成で走行させた。
【００３４】
このモデルは２つの一次ソフトウェアルーチンからできており、これらは、システム資源を操作するために資源マネージャによって呼び出される。これらソフトウェアルーチンを長期スケジューラ（ＬＴＳ）及び短期スケジューラ（ＳＴＳ）と呼ぶ。これについては付録Ａ及びＢを参照されたい。
ＬＴＳによって行なわれる２つの主なタスクとして、（１）各ジョブに対し、ターンアラウンドタイム及び印字スキップの総数を最小にする。これは、１群の画像に対して要求されるディスク帯域幅及びＥＳＳメモリを前もってスケジュールすることによって行なわれる。メモリ状態、帯域幅ユーティライゼーション、各画像ファイルの大きさ、及び原画数を用い、ＬＴＳは印字スキップを最少数に減少することができる。次に、（２）走査及び印字を同時に行なうための十分なメモリが残っているということを確実にする。ところが、ＬＴＳは、いつ次のジョブがＩＩＴを要求しようとするかを知ることができず、また、次のジョブの各画像の大きさを知ることができない。従って、走査バッファに、２：１圧縮率画像ファイルを受容するのに十分な大きさを与える。
【００３５】
ＳＴＳによって行なわれる２つの主なタスクとして、（１）スケジュール済み画像ファイルが、この画像に対して印字が開始する前に、ＥＳＳ印字バッファにロードされたということを確実にする。そうでないと、印字スキップがこのページに対して要求される。次に、（２）次の利用可能ディスク帯域幅をＩＩＴに与えることによって同時的走査／印字を提供しようと試みる。
Ｃ、結果
前記のシステムモデルは、同時的走査／印字機能、片面→片面印字に対する１００原画の自動書類取扱装置（ＡＤＨ）容量、及び現在システム内にある全てのジョブを保持するのに十分な大きさのスプーリングディスクを含んでいた。走査済み画像に対する平均圧縮率は１０：１であり、最低圧縮率は２：１であった。２：１圧縮率とは、原画に比べて半数のビットを用いて画像をメモリに記憶することができるということを意味する。１０：１圧縮率とは、原画に比べて１／１０の数のビットを用いて画像をメモリに記憶することができるということを意味する。（原画は、約２１６×２７９mm（8.５×１１インチ）用紙上に２5.４mm（１インチ）当たり６００×６００スポットを有す。）
下記の結果は、３６０Ｋの月平均コピー量で実行した２５０ジョブ（これはほぼ１週間分のジョブである）に基づくものである。ジョブの到着時刻、ページの圧縮率、ジョブの形式、原画の数、コピーの数、及び他の全てのジョブ数統計情報はモンテカルロ法を用いて発生させた。
【００３６】
ディスク帯域幅／メモリトレードオフモデルは１００ppm 走査装置及び１００ppm 印字装置から成っていた。全ジョブは、片面対片面モードで走行するＡ４判用紙から成っていた。ジョブ当たり原画の平均数は１０であり、ジョブ当たりコピーの平均数は４０であった。ジョブ当たり平均ランレングスは１６６刷りであった。
【００３７】
検討した結果、１２メガビット／秒ディスク帯域幅レベルの平均ジョブターンアラウンドタイム（ＴＡＴ）は、１６メガバイトよりも大きいメモリの全ての量に対して5.７５分である。この構成に対し、ジョブ当たり平均約0.１％の印字ピッチスキップがあった。これは、ジョブ当たり２％であった目標印字ピッチスキップに対して十分に目標内にあった。
【００３８】
図１１から解るように、6.５メガビット／秒のディスク帯域幅に対して、及び２４メガバイトよりも大きいメモリの全ての量に対して、印字ピッチスキップについての１％未満の最低限に近い改善が得られるに過ぎない。
図１２から解るように、１２メガビット／秒のディスク帯域幅に対して、及び１６メガバイトよりも大きいメモリの全ての量に対して、ＴＡＴにおける１％未満の最低限に近い改善が得られるに過ぎない。
【００３９】
１２メガビット／秒未満のディスク帯域幅及び２４メガバイト未満のメモリ大きさに対する図１１及び図１２において、最低の曲線は、システム性能に対するハードウェアの限界を表す基線を形成する。この基線は、長期スケジューリングアルゴリズムを改善することにより、即ち、システム資源をより効率的に使用することにより、更に減少させられる。
【００４０】
予備研究においては長期スケジューリングアルゴリズム（ＬＴＳ）を用い、１セットずつのスケジューリングを行なった。一つのセットの最後の数ページが印字されるにつれ、ディスクは遊休状態となった。
ディスクの使用をより効率的にするため、現在の研究に対しては１セットずつアルゴリズムを高め、連続セットのスケジューリングを含むようにした。これは、５セットを有するジョブに対して、最初のジョブをストリーム印字（後で定義する）し、次いで、第２及び第３のセットに対してメモリ及びディスク帯域幅使用のスケジュールを構築し、第２のセットを印字した後、第３及び第４のセットに対してスケジュールを構築する（以下同様）、ということを意味する。第３及び第４のセットに対するスケジュールは、前のスケジュールによってメモリに既に入っている第３のセットのページを考慮に入れて引き出される。この改訂アルゴリズムにより、ＴＡＴにおいて3.６６％の低下、ジョブ当たりピッチスキップにおいて１7.０９％の低下が得られた。
【００４１】
図１３は、ディスク帯域幅／メモリトレードオフモデルのための目的ハードウェア構成のブロック線図である。このモデルは、４つの一次ハードウェアサブシステム、即ち、画像入力端末装置（ＩＩＴ）２１４、ＥＳＳメモリ２２０の走査バッファ２１８、ＥＳＳメモリ２２０の印字バッファ２２２、スプーリングディスク２２４、及び画像出力端末装置（ＩＯＴ）２１６から成る一般的電子複写装置である。
【００４２】
これら構成部材の各々の機能及び顕著なパラメータを次に説明する。
画像入力端末装置（ＩＩＴ）：ＩＩＴは、原画書類からの画像を、ＥＳＳによる後続の処理のため、ビットマップにディジタル化する。
電子工学サブシステム（ＥＳＳ）：ＥＳＳは制御電子工学装置及び制御システムソフトウェアから成り、これらは、ＥＲ及びＥＰシステム内のデータ送信装置（ＩＩＴ／ネットワークインタフェース）とデータ受信装置（ＩＯＴ）との間の画像データ流れを準備及び管理する。
【００４３】
ＥＳＳはまた、現在走査及び印字中の書類に対するＥＲシステムの主メモリを有す。このモデルにおいて、ＥＳＳメモリは２つの部分、即ち、走査バッファ及び印字バッファに動的に分割される。比較のため、ＥＳＳメモリの大きさを１６メガバイトから１２８メガバイトまで変化させながらこのモデルを走行させた。書類が走査中である場合には、約２メガバイトの専用バッファを「最低状態」画像を取り扱うために割当てた。残りのＥＳＳメモリは印字バッファとして用いられる。
【００４４】
スプーリングディスク：スプーリングディスクは、走査及び圧縮された画像及びビットマップのためのデータ記憶装置を提供する。
このモデルにおいては、スプーリングディスクの大きさに対する制限はない。研究のため、ＥＳＳメモリとスプーリングディスクとの間のディスク帯域幅を１秒当たり6.５メガビットから１５メガビットまで変化させた。
【００４５】
画像出力端末装置（ＩＯＴ）：ＩＯＴは印字の機能を行なう。ＩＯＴは自足式電子印字装置を構成しない。ＩＯＴは、ＥＳＳによって準備されたビデオビットストリームを入力として受け入れる。
このモデルは、印字すべき次の画像が印字バッファ内にある場合には、１枚の用紙を送り出すか、さもなくば、この画像がバッファに入るまで１つまたは複数のピッチをスキップする、という仮定の下で働く。
【００４６】
図１４に示すメモリ／ディスク帯域幅トレードオフモデル２２６は、例示したシステムの走査／マーク部分を抜き出したものである。図１４について説明すると、ＵＩ  ５２はジョブパラメータ情報２３２をメモリ／ディスク帯域幅トレードオフモデル２２６へ送る能力を有す。ＩＩＴ  ２１４は、モデル２２６からＩＩＴ指令信号２５０を受信しながらＩＩＴ状態情報２５４及び画像パラメータ情報２５２をモデル２２６へ送る能力を有す。ＬＴＳテーブル２３０は、ＬＴＳテーブルを引用する線路２４８を介して情報をトレードオフモデル２２６へ送る能力を有す。トレードオフモデル２２６は、ＬＴＳテーブルを設定する線路２４６を介して情報を、及びＬＴＳテーブルを初期設定する線路２４４を介して情報を送る能力を有す。資源データベースは、基準資源状態を与える線路２４２を介して情報をトレードオフモデル２２６へ送る能力を有す。トレードオフモデル２２６は割当て資源情報２４０及び資源状態情報２３８を資源データベース２２８へ送る能力を有す。ＩＯＴ  ２１６は、トレードオフモデル２２６から印字指令信号２３６を受信しながらＩＯＴ状態信号２３４をトレードオフモデル２２６へ送る能力を有す。
【００４７】
モデル内の４つの一次モジュールとして、システムマネージャ、走査マネージャ、印字マネージャ、及び資源マネージャがある。これらモジュールは一緒に働いて長期スケジューラ（ＬＴＳ）テーブルを設定し、システム資源をモニタし、及びユーザインタフェース（ＵＩ）を介してシステムへ与えられるジョブに対するＩＩＴ／ＩＯＴアクティビティを制御する。各モジュールはシステム内の独立プロセスであり、そして各モジュールは若干のインタフェース及び同期機能を含む。
【００４８】
ＬＴＳは、資源マネージャによって構築及び実行される重要な内部データ構造である。ＬＴＳはセットの各スケジュール済み画像に対する将来の印字アクティビティを包含しており、これにはメモリユーティライゼーション及びディスク使用アクティビティが含まれている。
構造的には、前記モデルは２つの部分、即ち、一組のＳＬＡＭネットワークステートメント、及び一組のフォートランサブルーチンに分割される。ＳＬＡＭネットワーク部（付録Ｃ）は、ジョブをシステムへ与えることから仕上がりジョブを出力領域からアンロードすることまでのＥＲシステムの全プロセスを記述するのに用いられる。フォートランサブルーチンは、システム資源を扱う事象の詳細を記述するのに用いられる。モデル内には１０個の重要な事象、即ち、ＰＩＣＫ ＯＲＩＧＩＮＡＬ、ＳＣＡＮ ＰＡＧＥ、ＥＮＤ Ｓ ＰＡＧＥ、ＩＭＡＧＥ ＪＯＢ、ＩＭＡＧＥ ＳＥＴ、ＩＭＡＧＥ ＰＡＧＥ、ＭＡＲＡＫ ＰＡＧＥ、ＥＮＤ  ＭＡＲＫ ＰＡＧＥ、ＲＥＳＯＵＲＣＥ ＭＡＮ、及びＤＩＳＫ ＭＡＮがある。最初の３つの事（付録Ｄ）は、走査アクティビティ、及びＩＩＴとシステム資源との間のインタフェースを制御するのに用いられる。次の５つの事象（付録Ｅ）は、印字アクティビティ、及びＩＯＴとシステム資源との間のインタフェースを制御するのに用いられる。最後の２つの事象（付録Ｆ及びＧ）は、ＥＳＳメモリを保持し、及びディスク読出／書込アクティビティを制御するのに用いられる。
【００４９】
図１５に示すシステムマネージャ２５６は、ＵＩからジョブパラメータを獲得し、ＩＩＴ及びＩＯＴの状態をモニタし、及び資源データベースを保持する。
システムマネージャはＩＩＴ／ＩＯＴ状態をモニタし、現在ジョブをストリーム印字すべきか、ジョブ印字すべきか、またはハイブリッド印字すべきかを決定する。システムがどの状態にあるかを知ることは重要である。即ち、最初のセットのページをスケジュールするため、次に示す３つの方法があるからである。
【００５０】
１、ストリーム印字モード：ストリーム印字は、ジョブがシステムに到着し、そしてＩＩＴ及びＩＯＴが遊休状態になっているときに生ずる。このジョブは、原画の走査が開始した後に印字を開始する。
原画数が前以て解っていないので、長期スケジューリングは行なわれない。
２、ジョブ印字モード：ジョブ印字は、ＩＯＴが使用可能となる前にジョブの全ての原画が既にディスクに退避させられているときに生ずる。
【００５１】
最初のセットの全部は前スケジュールされる。
３、ハイブリッド印字モード：ハイブリッド印字は、ＩＯＴが使用可能となる前にディスクに退避させられている原画が１００％未満であるときに生ずる。既に走査されている原画はジョブ印字され、従って前スケジュールされる。走査されていない原画はストリーム印字され、従って前スケジューリングはない。
【００５２】
資源データベースは、（１）走査装置、感光体、またはＲＤＨが使用中であるか遊休状態であるか、（２）使用中のＥＳＳメモリの量、（３）走査バッファが割当てられているかどうか、及び（４）スプーリングディスクの状態、に関する状態情報を包含する。
走査マネージャ２３１（図１５）は、走査ジョブ要求を取り扱うという役、及び動的に割当てられた走査バッファを保持するという役をなす。
【００５３】
走査マネージャ２３１はＩＩＴ指令信号２７０をＩＩＴ  ２１４へ送る能力を有し、ＩＩＴ  ２１４は画像パラメータ信号２７２を走査マネージャ２３１へ送る能力を有す。システムマネージャ２５６は走査ジョブ要求信号２７４を走査マネージャ２３１へ送る能力を有し、マネージャ２３１は、ストリーム印字のためのＬＴＳテーブル初期設定信号をＬＳＴテーブル２３０へ送る他の能力を有す。走査マネージャ２３１は走査バッファ初期設定信号２７８及びワーキングバッファ要求信号２８０を走査短期スケジューラ２５８へ送る能力を有し、スケジューラ２５８はワーキングバッファ状態信号２８２を走査マネージャへ送る能力を有す。走査マネージャ２３１は、走査バッファ要求信号２６２、ディスク書込要求信号２６４、及び復帰走査バッファ信号２６６を資源マネージャ２６０へ送る能力を有し、資源マネージャ２６０は割当て走査バッファ信号２６８を走査マネージャへ送る能力を有す。
【００５４】
走査ジョブ要求が受信されると、走査マネージャは、走査すべき次ぎの画像に対するバッファとして、２：１の比率に圧縮された画像（最低状態圧縮比率は２：１であると仮定）を保持するのに十分な場所を確保することを走査短期スケジューラに要求する。走査バッファを割当てるのに利用できるメモリが不十分である場合には、走査スキップが生ずる。きもない場合には、１走査ピッチ後に、圧縮済み画像がワーキングバッファ内でディスクへの転送を待つ。
【００５５】
ジョブがストリーム印字モードになっている場合には、走査マネージャはこの原画に対する画像パラメータ及び他の情報をＬＴＳテーブルにコピーする。
印字マネージャ２５７（図１６）はＩＯＴと資源マネージャとの間のインタフェースである。システムマネージャから印字ジョブ要求が受信されると、印字マネージャは、ジョブのためのＬＴＳテーブルをジョブ印字モードに、またはハイブリッド印字モードに初期設定する。
【００５６】
図１６について説明すると、システムマネージャ２５６は印字ジョブ要求信号２８６を印字マネージャ２５７へ送る能力を有す。印字マネージャはジョブ印字用ＬＴＳテーブル初期設定信号２９０をＬＴＳテーブル２３０へ送る能力を有す。    〜    〜    印字マネージャ２５７は、ＬＴＳ要求信号２９２を資源マネージャ２６０へ、及び印字指令信号２３６をＩＯＴ  ２１６へ送る他の能力を有す。ＩＯＴ  ２１６は画像要求信号２８４を印字マネージャへ送る能力を有し、資源マネージャ２６０は画像状態信号２９４を印字マネージャへ送る能力を有す。
【００５７】
各セットの印字に先立ち、印字マネージャは、この印字マネージャのための印字アクティビティをスケジュールするため、資源マネージャの下で適切な印字スケジューラを呼び出す。
印字マネージャはまた、ＩＯＴマーキングのタイミング、１印字ピッチずつの割りのＩＯＴ関連アクティビティ、及び、ジョブの最後のページである場合のＥＳＳメモリ及びスプーリングディスクからの画像の排除、を制御する。
【００５８】
資源マネージャ（ＲＭ）２６０（図１７）はシステム資源とそのクライアントとの間のインタフェースとして働く。ＲＭのクライアントは走査マネージャ及び印字マネージャである。図１７は走査マネージャ、印字マネージャ及び資源マネージャ相互間の対話を示すものであり、これについては前述した。
図１７は、資源マネージャ２６０は画像状態信号２９４を印字マネージャ２５７へ送る能力を有し、印字マネージャ２５７はＬＴＳ要求信号２９２を資源マネージャ２６０へ送る能力を有しているということを示す更に示すものである。資源マネージャ２６０は印字要求信号３２８を印字短期スケジューラ２９８へ送る能力を有し、印字短期スケジューラ２９８は画像状態ディスク書込スケジュール信号３２６を資源マネージャ２６０へ送る能力を有す。資源マネージャ２６０は割当て資源信号２４０は資源データベース２２８へ送る能力を有し、資源データベース２２８は基準資源データ信号２４２を資源マネージャへ送る能力を有す。資源データベースは基準資源状態信号２４２を印字長期スケジューラ３００へ送る更に他の能力を有し、印字長期スケジューラ３００は印字スケジュール信号３０８を資源マネージャ２６０へ送る能力を有す。資源マネージャ２６０はＬＴＳ要求信号３１０を印字長期スケジューラ３００へ送る能力を有す。印字長期スケジューラ３００はセットＬＴＳテーブル信号３１８をＬＴＳテーブル２３０へ送る能力を有し、ＬＴＳテーブル２３０は基準ＬＴＳテーブル３２０を印字長期スケジューラ３００へ送る能力を有す。印字メモリスワッパ３０２はメモリ状態／スケジュール信号３２４を印字長期スケジューラ３００へ送る能力を有し、印字長期スケジューラ３００はメモリ要求信号３２２を印字メモリスワッパ３０２へ送る能力を有す。資源マネージャ２６０はディスクＲ／Ｗ要求信号３０６をディスクマネージャ２９６へ送る更に他の能力を有し、ディスクマネージャ２９６はディスク状態信号３０４を資源マネージャ２６０へ送る能力を有す。
【００５９】
印字長期スケジューラ（ＬＴＳ）ルーチンは、各画像ファイルに対する所要のディスク帯域幅及びＥＳＳメモリを現在メモリ状態、ディスク帯域幅ユーティライゼーション、及び初期設定済みＬＴＳテーブルに従って前もって確保することにより、印字すべき次のセットに対するスケジュールを設定する。その結果、利用可能メモリはジョブの前部分によって確保され、ジョブの後部分に対しては場所がなくなる。この時点で、印字ＬＴＳは印字メモリスワッパルーチンを呼び出し、メモリに入れるべき次の画像ファイルのための場所を作るためにＥＳＳメモリから或る画像ファイルを削除する。更に、印字ＬＴＳは適当するディスク帯域幅を走査クライアントに割当て、走査／印字同時性を保持する。
【００６０】
印字短期スケジューラ（ＳＴＳ）はＬＴＳテーブルに指定されているアクティビティのスケジュールを実行する。
ディスクマネージャは、印字ＳＴＳ及び印字ＬＴＳによってなされるディスク読出及び書込要求を処理する。
Ｄ、長期スケジューラ
ワーキングモデルを設計する主目的の一つは異なる長期スケジューリングの相対的性能を調べるためであった。効率的ＬＴＳアルゴリズムの開発に関する主な論点は下記のとおりである。即ち、
−−  何ページを前もってスケジュールすべきか？  前もってスケジュールするページ数があまりに少ないと、例えば１ページずつスケジュールすると、ディスク帯域幅を浪費することになる。一つのジョブの全セットの全てのページをスケジュールすることは最適スケジュールとなるが、２つの主な欠点がある。即ち、（１）これはリアルタイムモードにおいて実際的でないという可能性がある。及び（２）或る程度の走査／印字同時性が失われるという可能性がある。
【００６１】
−−  ジョブが印字中であり、そしてメモリの容量が一杯になったとき、どのページを削除すべきか？  試験されたメモリ管理アルゴリズムのうち、最良の方法は、「最新印字退避画像フィルを先」（ＲＰＳＦ）方式でスワップアウトすることであった。
ＲＰＳＦ方式は下記の仕方で行なわれる（付録Ｉ及びＪ参照）。即ち、ジョブの新しいセットを印字開始する前に、ＬＴＳは、各画像ファイルに所要のディスク帯域幅及びＥＳＳメモリを、各画像ファイルに対するメモリ状態、帯域幅ユーティライゼーション、及び大きさに基づいてスケジュールする。次の画像をスケジュールするのに十分なメモリが残っていない場合には、前にロード及び退避された若干の画像ファイルを、これらを印字した後、印字バッファから削除する。画像を削除する順序は、そのデータが優先権を与えられた状態でどれくらい以前に印字されたか、に基づいて定められる。
【００６２】
（ａ）原理長期スケジューリングアルゴリズム
電子複写（ＥＲ）及び電子印字（ＥＰ）のシステムにおいて、メモリ及び帯域幅のような資源の割当ては資源マネージャによって行なわれる。ＥＲ／ＥＰシステムにおけるこれら限定資源の管理及び割当てに用いられるアルゴリズムは、ターンアラウンドタイム（ＴＡＴ）及びジョブ当たりピッチスキップ比率について、システム性能に対して重大な影響を与える。
【００６３】
この問題をよりよく理解するため、下記の場合を考えてみる。即ち、
１、ジョブ当たり原画数（ＯＰＪ）が比較的小さく、従ってジョブの全ての原画が一度にメモリ内に存在し得る場合には、ディスク速度及び資源割当ては重要でない。これは、全てのページがメモリ内にある場合には、個々のページまたはページの部分（セグメントと呼ぶ）をディスク上へ及びその外へ転送する必要がないからである。
【００６４】
２、原画当り印字数（ＰＰＯ）が１に等しい場合には、メモリの大きさ及び資源割当ては比較的重要でない。その理由は、原画を走査すると同じ速度でページを印字するシステムにおいては、各ページを印字するにつれてこれを放棄することができ、このようにしてメモリをからにすることができるからである。本来、メモリは一度に若干数のページを保持することができるものであり、この数は、画像形成システム及びその用紙通路の長さによって定まる。
【００６５】
３、ＰＰＯが１よりも大きく、そして全てのページからのセグメントが一時にメモリ内に存在することができない場合には、資源割当て、即ち、メモリの大きさ、及びディスクの速度の各々がシステムの性能において重要な役をなす。
本発明において用いるスケジューリングアルゴリズムの進展について次ぎに説明する。即ち、
オセセット法  −−  オフセットアルゴリズムの考え方は、或る画像に対する画像要求時刻と画像印字時刻との間の短い時間（オフセット時間）を考慮するものである。オフセット時間は若干数の印字ピッチで表される（図１８参照）。オフセット方式の考え方は、一つのページに対する要求時刻と印字時刻との間の遅れ時間を考慮するものである。オフセット時間は若干数の印字ピッチで表され、この場合においては２である。
【００６６】
単一セット先行スケジューリング法  −−  このアルゴリズム（付録Ａの長期スケジューラアルゴリズムに対応する）は、オフセット法によって生じた無駄なディスク帯域幅を利用するものである。これは、セットの印字に先立って印字セット内の各画像を検索するのに必要な所要ディスク帯域幅をスケジュールすることによって達成される（図１９参照）。
【００６７】
連続セットスケジューリング法  −−  このアルゴリズム（付録Ｈ）は、単一セット先行スケジューリング法によって生ずるスキップ数（セット相互間の）を減少させようとするものである。この方法（図２０）は、セット１及びｎ＋１に対するメモリ使用及びディスク帯域幅をスケジュールし、そして、セット１を印字した後、このスケジュールを資源マネージャに与えて実行するものである。セットｎに対するスケジュールは、セットｎ−１の印字が完了したときにメモリ内になお存在している画像を考慮する。この方法は、セットｎの印字最中の全ての未使用帯域幅をセットｎ＋１の画像検索のために使用することを可能にする。
【００６８】
図１８はオフセット法を示すものであり、ｎ原画のセットｉ及びｉ＋１の部分要求、ページ転写、及び印字を示している。また、図１８において、Ｔはｉ／ｈピッチ時間、Ｒｉはページｉに対する要求、Ｐｉはページｉである。右向き三角形信号は指定ページを表し、横長矩形信号はこのページに対するディスク読出時間を表し、斜め十字信号はディスク帯域幅制限による印字スキップを表す。二方向矢印は、ディスクが印字クライアントのために使用中であるということを示す。使用したオフセット値は２ピッチである。この例においては、ページに対する要求とこのページの印字との間に２ピッチの要求がある。２に等しいオフセットに対し、これは、そのページの要求と印字完了との間に３ピッチの差異があることになる。
【００６９】
オフセットアルゴリズムの要件は、ページに対する要求がピッチ境界でのみ生ずることができるということである。この要件の結果、無駄な帯域幅が生ずる。例えば、オフセット＝２に対して、要求と印字時刻との間に２ピッチの差がある。１ピッチの３／４をページに入れることを要求される場合、次のページ要求は次のピッチ境界までは生じないので、１／４ピッチの無駄な帯域幅があることになる。
【００７０】
例えば図１８において、ページＰｎ−２が時刻Ｔｘにおいて（Ｒｎ−２）を要求されるが、Ｔｘ＋２とＴｘ＋３との間の時間内に延びているページＰｎ−２を読み取るのにかかる時間のために時刻Ｔｘ＋３までは印字されない。ページＰｎ−２に対してスキップピッチが生ずる。
この問題を軽減するため、単一セットＬＴＳアルゴリズムが予め或る数のページに対するシステム資源をスケジュールする。即ち、ジョブが印字を開始する前に、ＥＲシステム内の各ジョブに対する印字要件、原画数、セット数、及び画像の複雑性が解っているからである。
【００７１】
ジョブがｍセットを有していたとすると、ジョブ印字モードにおいて、長期スケジューリング（ＬＴＳ）アルゴリズムを単一セットインプリメンテーションがセット１．．．ｍを１セットずつスケジュールした。ストリーム印字モードにおいて、セット２．．．ｍが１セットずつスケジュールされる。例えば、ストリーミング印字モードにおいて、メモリ／ディスク帯域幅スケジュールがセット２に対して構築され、資源マネージャ（ＲＭ）に与えられて実行された。次いで、セット３に対するスケジュールが構築され、ＲＭによって実行された。次いで、セット４に対するスケジュールがＬＴＳによって構築され、ＲＭによって実行された。以下同様に行なわれる。この方法を用いてセットをスケジュールする結果、連続セット相互間に若干の未使用帯域幅があることになり、不必要なピッチスキップが生ずる。これは図１９に示す。
【００７２】
印字ジョブがｎ原画及びｍセットを有するものとすると、図１９は、セットｉの最後の３ページ、及びセットｉ＋１の最初の３ページについてのユーティライゼーションを示すものである。ページＰｎ−１に対する印字スキップは、ページＰｎ−１をメモリへ転送するための時間がかかるため、不可避であった。しかし、下記のように連続セットスケジューリングを用いた場合、Ｔｘ＋７まではセットｉ＋１のページをスケジュールしないことによって生じたＴｘ＋５及びＴｘ＋６中の未使用帯域幅が利用可能であった。
【００７３】
単一セットＬＴＳアルゴリズムを連続セットのスケジューリングを行なうように変形した（図２０）。このアップグレイドしたＬＴＳがセット２及び３に対してメモリ及びディスク帯域幅をスケジュールし、このスケジュールをＲＭに与えて実行する。セット３が印字完了した後、ＬＴＳは、セット３のページがメモリに入れられたことを考慮しながらセット３及び４をスケジュールする。以下同様に行なう。この方法により、Ｔｘ＋５及びＴｘ＋６の帯域幅が使用可能となり、セットｉ＋１のＰ１及びＰ２によって生じた印字スキップが除去される。連続セットスケジューリングの効果を図２０に示す。
【００７４】
（ｂ）解析
前記３つのスケジューリングアルゴリズムを解析するために用いたシステムモデルをＳＬＡＭ  ＩＩシミュレーション言語及びフォートランの組合せを用いて構築した。このモデルは、同時的走査／印字機能、片面から片面への印字のための１００原画の自動書類取扱装置（ＡＤＨ）容量、及び全てのジョブを同時にシステム内に保持するのに十分な大きさのスプーリングディスクを有す。走査済み画像に対する平均圧縮率は１０：１であり、最低の場合の圧縮率は２：１であった。
【００７５】
下記の結果は、月平均３６０Ｋのコピー量で実行した２５０ジョブに基づいたのであり、これは約１週間分のジョブである。ジョブの到着時刻、ページの圧縮率、ジョブの型、原画の数、コピーの数、及び他の全てのジョブ数統計情報は、モンテカルロ法を用いて発生させた。
モデルは、１分当り１００ページ（１００ppm ）走査装置、及び１００ppm 印字装置から成るものであった。全てのジョブは、片面対片面モードで走行するＡ４判用紙から成っていた。ジョブ当り平均原画数は１０、ジョブ当り平均コピー数は４０であった。ジョブ当り平均ランレングスは１６６刷りであった。
【００７６】
結果は、単一セットスケジューリングがオフセットアルゴリズムに勝っているということを示した。
連続セットスケジューリングアルゴリズムを単一セットスケジューリングアルゴリズムに対する改善として提案及び実行した。図２１は、連続セットスケジューリングアルゴリズムを単一セットスケジューリングアルゴリズムと比較して用いたときのターンアラウンドタイム及びピッチスキップの改善（改善百分率）を示す表である。
Ｅ、メモリ管理
次の説明は、メモリの量が、印字ジョブ内の画像の各々に対する圧縮データを包含するのに不十分であるときのメモリからの画像のスワッピングに関するものである。画像置き換えの問題は、既にスプールディスク上に存在している画像がメモリに入ることを要求され、そして、圧縮されたビットマップ形式の画像を保持するために利用できる十分なメモリがない、というときに生ずる。資源マネージャは、メモリ内に現在存在しているページから、次ぎに必要な画像を検索するためにどれをメモリから除去するのが最も良いかを決定することが必要となる。画像スワッピング法は全部の画像または部分的画像をスワップすることを基礎とする。
【００７７】
固定セットの資源、即ち、メモリ及びディスク帯域幅を有する電子複写システムが与えられると、システム性能は、種々のメモリ管理スワッピングアルゴリズムのインプリメンテーションを通じて影響される。このアルゴリズムは、ページスワッピング法（下記のアルゴリズム１ないし３）またはセグメント（部分画像）スワッピング法（下記のアルゴリズム４及び５）を適用可能である。開発及び解析されたこれらアルゴリズムについて次ぎに詳細に説明する。即ち、
１、最新使用画像スワッピングアルゴリズム（付録Ｉ）：最新使用画像スワッピングアルゴリズム（ＲＰＳＦに対応）は、次の画像をメモリに入れることを要求されるとき、メモリに存在している画像のセットから最新に使用された（印字及び退避させられた）ものをスワップアウトすることを選択する。
【００７８】
２、最大最近使用画像スワッピングアルゴリズム：最大最近使用画像スワッピングアルゴリズムは、次の画像をメモリに入れることを要求されるとき、メモリに存在している画像のセットから、最大の画像を、これが印字及び退避済みであるべきであったならば、スワップアウトすることを選択する。
３、最小最近使用画像スワッピングアルゴリズム：最小最近使用画像スワッピングアルゴリズムは、次の画像をメモリに入れることを要求されるとき、メモリに存在している画像のセットから、最小の画像を、これが印字及び退避済みであるべきであったならば、スワップアウトすることを選択する。
【００７９】
４、最新使用セグメントスワッピングアルゴリズム（付録Ｊ）：最新使用セグメントスワッピングアルゴリズムは、最新に印字されてメモリになお存在している画像から、最長時間未印字であってメモリになお存在している画像まで、画像の順序付けに必要なメモリの量に応じて部分的または全部の画像をスワップすることを選択する。このアルゴリズムにおいては、各画像は一グループのセグメントから成ると定義される。一つのセグメントの大きさは、一定であってその実際の大きさは特定のスプールディスクの特性に応じて定まる、と定義される。画像をメモリ内にスワップすることが必要となったとき、スケジューラは、メモリ内への新しい画像の検索を考慮してスワップアウトすべきメモリのセグメントの正確な数を計算する。次いで、スケジューラは、所望の時にメモリから除去することのできる全ての画像を検査し、最新に印字された画像からそれだけの数だけのセグメントをスワップアウトする。このアルゴリズムは前述の仮定の下で最適のアルゴリズムである。即ち、このアルゴリズムは、これが発生する被スワップセグメントの量が最も少なく、そして、セグメントは定義によって互いに等しい大きさであり、このアルゴリズムはディスク読出の量を最小量に減少するからである。
【００８０】
実験によれば、この最新使用セグメントスワッピングアルゴリズムは好ましい方法である。図２８の棒グラフにおいて、最新使用セグメントスワッピングアルゴリズムを他のアルゴリズムと比較して示す（印字ピッチスキップ比較）。
５、順次限定セグメントスワッピングアルゴリズム（付録Ｋ）：このアルゴリズムも、部分画像をメモリ内に及びこれから外へスワップすることができるという主仮定を基礎としている。ここで、スケジューラが若干数のセグメントをメモリからスワップすることが必要になると、画像の最新に使用された配列で、或る限定数のセグメントが、現在メモリ内で利用可能であってスワップアウトされ得る画像から除去される。この除去されるセグメントの数は、１ピッチタイムフレーム内でディスクから検索することのできるセグメントの数に基づく。それで、順次限定セグメントスワッピングアルゴリズムという名で呼ぶのである。このアルゴリズムは最新使用セグメントスワッピングアルゴリズムよりも良いということはないが、これにより、ディスクは、全印字セットにわたってディスクが使用中であるという時間を広げる。これは、必然的に発生するシーク数及び回転待ち時間についてのより大きなディスクオーバヘッドを招くという悪影響を受けることが少ない。
【００８１】
図２７は順次限定セグメントスワッピングアルゴリズム及び最新使用ページスワッピングアルゴリズムに対する種々のメモリメガビット容量におけるピッチスキップの百分率を比較した表である。
これらの画像及び部分画像スワッピングアルゴリズムは、或るジョブの画像印字セットをスケジュールする間に実施すると、電子複写装置及び電子印字装置の性能を向上させることができる。これは、メモリの量がジョブの印字部分内の画像の各々に対する圧縮データを包含するのに不十分であるときに、部分画像または全画像のどちらをメモリからスワップするかを選択的に選ぶことによって行なわれる。従って、性能のこの向上は電子工学式印字装置及び複写装置に対する性能／費用比率を向上させる。
【００８２】
画像置き換えアルゴリズムの研究が、簡単な電子工学サブシステムアーキテクチャ構成の性能を評価するために開発された個別式シミュレーションの分野に生じた。この構成内に種々のアルゴリズムが導入されて解析され、その後、結果が比較された。
使用されたシステムモデルは、画像入力端末装置、電子工学サブシステム、スプーリングディスク、及び画像出力端末装置から成るものであった。ユーザインタフェース及びネットワークインタフェースのような他のサブシステムは、走査／印字チャネル上のスプーリングディスク及びメモリはこれらサブシステムによって影響されることがないので、このモデルに含まれなかった。このシステムモデルは、オペレータによって走査されるように自動書類取扱装置内に入れられておって無作為に到着するジョブに対する同時走査／印字機能のシミュレーションを行なった。スプールディスクは、所定の時にシステム内にある全てのジョブからの画像を保持するのに十分な場所を有しているものと仮定した。平均圧縮率は１０：１、最低圧縮率は２：１であると仮定した。
【００８３】
前記スワッピングアルゴリズムの各々に対するシステムの性能を評価するために計算した結果は、約３５０Ｋの月平均コピー量で２５０ジョブを実行したことに基づいたものである。ジョブの到着時刻、ページの圧縮率、原画数、コピー数、及び他の全てのジョブ数統計的データは、モンテカルロ法を用いて発生させた。
【００８４】
平均ターンアラウンドタイム（ＴＡＴ）及び印字ピッチスキップの百分率を資源管理アルゴリズムの性能を測定する基準として用いた。平均ＴＡＴは、１セットのジョブの走査／印字を完了するのに要する平均持続時間と定義され、これには、ジョブのプログラム、ロード、走査、印字、及びシステムからのアンロード、ならびに、システムまたはオペレータが使用中または作業中であったために生ずる待ち時間が含まれる。単一ジョブに対するターンアラウンドタイムは、或るジョブが作業のためにオペレータに到着した時から、このジョブがオペレータによってシステムから除去されるまでの持続時間として特定的に測定される。
【００８５】
第２の性能測定は、システムによって発生する印字ピッチスキップの比率である。単一印字ピッチスキップは、ジョブの印字最中に、ＥＳＳが所要の印字画像を、この画像に対する指定の印字時刻にＩＯＴに提供することができないときに生ずる。発生する各ピッチスキップは、ＩＯＴエンジンが、運転中ではあるが、ハードコピー出力を何も作っていないときの時間を表す。印字ピッチスキップの比率は、印字ピッチスキップ総数を、製作済み刷り総数と印字ピッチスキップ総数との和で除して計算される。
【００８６】
性能は、硬式ディスクに接続された１６、２０、２４、３２、４８、及び６４メガバイトのメモリを有しているシステムに対して評価された。前記ディスクの転送速度（平均回転待時間も、平均シーク持続時間も含まず）は１秒当り6.５、7.５、8.５、または１２メガビットである。平均回転待時間及び平均シーク持続時間を明らかにするため、各ディスクトランザクションに対し、追加の平均オーバヘッド費用を有効転送速度に含ませた。この結果、２４の個別ＥＲシステム構成の組合せとなる。この２４の構成を各メモリ管理アルゴリズムに対してモデルとして作る。１月当り約３５０Ｋ印字の量で表される。
【００８７】
図２２及び２３は、最新使用セグメントスワッピングアルゴリズムを最新使用退避ページスワッピングアルゴリズムと比較する表である。
Ｆ、資源及びメモリ管理の調整
概念的には、ＩＯＴを、印字ピッチ毎に画像ファイルを要求する消費者と考え、ＥＳＳを、要求された画像をＩＯＴに対して提供する生産者と考えることができる。ＥＳＳが、要求された画像を、ＩＯＴがこれを印字する準備ができる前に提供することができない場合、ＩＯＴは待ち、このようにして印字スキップを生ずる。換言すれば、印字スキップは、要求された画像を十分に速く提供することができないＥＳＳによるものである。
【００８８】
主な問題は、ＩＯＴ消費速度を手元の限定された資源とどのようにして整合させるかである。本発明に対するモデルを準備するに際して、ＡＤＨ容量は片面／片面印字に対して１００原画であり、スプーリングディスク容量は装置に到来するであろうジョブを保持するのに十分な大きさである、と仮定した。平均圧縮率は１０：１、最低圧縮率は２：１であった。更に、限定資源環境の下で、ＥＳＳは所要の画像を十分に速く提供することはできないものと仮定した。従って、各ジョブは若干数の印字スキップをもつ可能性がある。
【００８９】
印字ピッチスキップを最少にするため、必要最小資源、及びこの限定資源を管理するための最適戦略を決定した。メモリ大きさ及びディスク帯域幅の可能範囲を推定した。選定した６つのディスク帯域幅は6.５、7.５、8.５、１２、１３及び１５メガビット／秒であった。選定した８つの帯域幅は１６、２０、２４、３２、４８、６４、９６、及び１２８メガバイトであった。このモデルを４８種類のディスク帯域幅／メモリ構成に対して走行させた。
【００９０】
このモデルの内部に２つの重要なソフトウェアがあり、これらソフトウェアは資源マネージャによって呼び出されて限定資源を操作する。これらソフトウェアモジュールは長期スケジューラ（ＬＴＳ）及び短期スケジューラ（ＳＴＳ）である。ＬＴＳは応答し、或るタイムフレーム中、資源をスケジュールする。ＳＴＳは応答し、ＬＴＳによって提供されるスケジュールのシミュレーションを行なう。
【００９１】
ＬＴＳによって行なわれる２つの主なタスクとして、（１）各ジョブに対する印字スキップの総数を規定限界内に保持しながらターンアラウンドタイムを最小にする。これは、一グループの画像に対する所要のディスク帯域幅及びＥＳＳメモリを前もってスケジュールすることによって行なわれる。換言すれば、ジョブが走査されてシステムに入力された後、ＬＴＳは、その限定資源の使用を、メモリ状態、帯域幅ユーティライゼーション、各画像ファイルの大きさ、及び原画数に基づいて注意深く計画することにより、印字スキップを減少させることができる。次のタスクとして（２）同時的走査及び印字を行なうためにＩＩＴに対して十分なメモリが残っているということを保証する（ＳＴＳはＩＩＴに対する必要な帯域幅を支持する）。ところが、ＬＴＳは将来を予言することはできない。いつ次のジョブがＩＩＴを要求しようとするかを知ることができず、また次のジョブの各画像の大きさも知ることができない。走査バッファの割当ては或るアドホック方式において行なうことが必要である。２：１画像ファイル（最低の場合）を保持するのに十分な走査バッファが常に確保されていた。
【００９２】
ＳＴＳによって行なわれる２つの主なタスクとして（１）スケジュール済み画像ファイルが、この画像ファイルに対する印字が開始する前に、ＥＳＳ印字バッファにロードされているということを保証する。さもないと、印字スキップがこのページに対して要求される。次ぎに（２）利用可能な次のディスク帯域幅をＩＴＴに与えることにより、同時的走査／印字を提供することを試みる。
１、メモリ管理アルゴリズム
印字スキップを最小にするため、ＬＴＳは各画像ファイルに対する所要のディスク帯域幅及びＥＳＳメモリをスケジュールすることが必要である。ＥＳＳメモリがジョブの全ての画像ファイルを保持するのに十分な大きさである場合には、印字スキップはジョブ印字ジョブの最初の印字セット最中に生ずるのみであり、ストリーム印字ジョブに対しては印字スキップは生じない。従って、ＬＴＳのタスクは極めて容易である。この場合、ジョブ印字ジョブの印字スキップ数はディスク帯域幅のみによって定まる。
【００９３】
この研究における下端のメモリ大きさは１６メガバイトであり、８つの２：１画像ファイル、または４０の１０：１画像ファイルを保持することができた。結局、この限定されたメモリスペースは大きなジョブの前部分によって占められ、このジョブの後部分に対してはスペースが残らない。この時点で、ＬＴＳはスワッパを呼び出し、次の画像ファイルをメモリに入れるための場所を作るため、ＥＳＳメモリから或る画像ファイルを削除する。
２、定義の一般的仮定及び再考
−  ディスク帯域幅：選択されるデータ転送速度は論理ディスクの純スループットである。最大シーク時間は３５ミリ秒、最小シーク時間は８ミリ秒であると仮定する。また、システムは画像ファイルにアクセスするために２つの最大シークを必要とするものと仮定する。選択された６つのディスク帯域幅は走査及び印字の機能のためにのみ用いられる。
【００９４】
−  ジョブマトリックス：ＲＧＢ  ２００Ｋマトリックスを基礎とするこの研究のため、変形３６０Ｋジョブマトリックスを用いた。全てのジョブに対してＡ４判用紙及び片面対片面印字を仮定する。
−  ジョブ印字及びハイブリッド印字：現在ジョブがシステムに到着したときにＩＯＴが前のジョブに使用中である場合に生ずる印字モード。ジョブ印字モードは、新しく到着したジョブの全ての画像ファイルが、ＩＯＴが使用可能となる前に、スプーリングディスクに退避させられていたときに生ずる。ハイブリッド印字は、原画の１００％未満のものが、ＩＯＴが使用可能となる前に、退避させられていたときに生ずる。
【００９５】
−  長期スケジューラ（ＬＴＳ）：資源マネージャの主モジュール。このスケジューラは、システム及びその現在ジョブについてのその知識に基づいてその限定資源の使用を注意深く計画することにより、ＴＡＴ及び印字スキップを最少にしようとする。
−  短期スケジューラ（ＳＴＳ）：資源マネージャの他の主モジュール。ＳＴＳは、印字時においてＬＴＳによって設定されるスケジュールを実行し、理想的ディスク帯域幅をＩＩＴに割当てて走査／印字同時性を支持する。
【００９６】
−  ストリーム印字：現在ジョブがシステムに到着したときにＩＩＴ及びＩＯＴの両方が遊休状態であるときに生ずる印字モード。
３、基本的仮定
ページシーケンス：ＩＩＴ及びＩＯＴの両方が１：Ｎモードで動作した。
0003732235.tif 000002
オペレータ時間：
ジョブ命令読出し及び書類取扱装置ロード                        8.４秒
システムプログラム                                            8.０秒
書類取扱装置アンロード                                        5.０秒
ジョブアンロード及び作業命令完了                              2.０秒
ワーキングジョブマトリックスにおけるジョブパラメータ：
ＡＭＣＶ                              ３６０ｋ（１１００ジョブ／月）
披シミュレーションジョブ                            ２５０ジョブ実行
ジョブ当り平均原画数（ＯＰＪ）                                9.９０
披シミュレーションＯＰＪ                                    １0.３０
原画当り平均印字数（ＰＰＯ）                                ３8.６５
披シミュレーションＰＰＯ                                    ４0.３４
ジョブ当り平均量                                          １８2.６０
ジョブ当り披シミュレーション平均量                        １６6.１０
指数ジョブ間到着時間                                      ２６5.４９秒
（他のＡＭＣＶはＩ．Ａ．Ｔ．を変化することによってシミュレーションすることができる）
ＩＩＴパラメータ
印字装置速度                                        １００ページ／秒
ＩＩＴピッチ時間                                              0.６秒
解像度                    ６００走査／２5.４mm（６００走査／インチ）
走査幅                                      約２７９mm（１１インチ）
長縁送りＡ４用紙
ＩＯＴパラメータ
走査速度                                            １００ページ／秒
ＩＯＴピッチ時間                                              0.６秒
解像度                    ６００走査／２5.４mm（６００走査／インチ）
走査幅                                      約２７９mm（１１インチ）
長縁送りＡ４用紙
スプーリングディスクパラメータ
ディスク帯域幅                              6.５〜１５メガビット／秒
最大シーク時間                                            ３５ミリ秒
最小シーク時間                                              ８ミリ秒
シリンダ大きさ                  ９６キロバイト（または１セグメント）
ＥＳＳメモリ
メモリ大きさ                          ８メガバイト〜１２８メガバイト
メモリ単位                          １セグメント（＝９６キロバイト）
メモリ管理／スワッピングアルゴリズムの役目は、システムの限定された資源をよりよく利用することにより、与えられたシステム性能を向上させることである。メモリ管理／スワッピングアルゴリズムの性能を測定するのに用いる基準として、平均ターンアラウンドタイム及び印字ピッチスキップ百分率がある。これら性能測定の正確な定義については前述してある。種々のメモリ管理／スワッピング手法間の比較の外に、結果も用い、ある性能レベルに到達するのに必要なメモリ量とディスク帯域幅との間のトレードオフ曲線を描く。
【００９７】
この一組の実験においてモデルとして作った基本的ＥＳＳアーキテクチャは、入力装置に接続されたメモリの限定スプール、出力装置、及びスプールディスクから成っている。全数４つの構成部材は資源マネージャによって管理される。但し、入力装置、出力装置、及びディスク駆動装置は、それらの特有の機能を行なうため、それら自体の制御装置を持っている。例えば、資源マネージャは、書類の機械的走査については走査装置を制御しないが、走査装置に動作を開始するのに十分なメモリを提供しないことにより、いつ走査装置が走査を開始することができるかを抑制する。
【００９８】
この一組の実験におけるＥＳＳの主な機能は、システムに走査／印字ジョブを受容して実行することを許すということである。走査／印字機能の３つの基本的ステップは、（１）原画のセットを走査してメモリに入力する、（２）各原画を圧縮ビットマップとしてスプールディスクに記憶させる、及び（３）原画のセットの所望数のコピーを印字する、ことである。このメモリ管理アルゴリズムは、前記３つのステップを同時に実行し、画像を走査しながら画像の記憶及び印字を行なうことができるようにするために開発されたものである。入力装置及び出力装置の速度は等しいから、最初の画像の印字は、その原画が走査されてメモリに入れられると直ちに開始することができる。この現在の組の実験に対し、入力装置及び出力装置は、１分当り１００画像の最大速度で機能した。
【００９９】
ＥＲシステム内のメモリの量が限定されているので、システムが、現在メモリ内に存在していないでスプールディスクに記憶されている画像をメモリに入れることを要求するが、圧縮ビットマップ形式のこの画像を保持するのに利用できる十分なメモリがない、という時点がやってくる。そこで、資源マネージャは、到来する画像のための場所を作るために、現在メモリ内にあるページのうちのどれをメモリから除去するのが最も良いかを決定することが必要になる。このときの目標は、性能に影響を与えることがほとんどないか又はまったくない画像を除去することである。
【０１００】
最新使用セグメントスワッピングアルゴリズムは、最新に使用されたセグメントをスワップアウトすることを選択するので、最良である。即ち、これは、ＥＲシステムに対し、最も遠い将来まで必要とならないセグメントをスワップアウトするのと同等であるからである。付録Ｉ及び付録Ｊは参照されたい。
結果（図２２及び２３）は、最新使用セグメントスワッピングアルゴリズムが、前に説明した最新使用ページスワッピングアルゴリズムと呼ばれるスワッピングアルゴリズムよりもはるかに良いということを示している。
【０１０１】
前記結果は、最新使用セグメントスワッピングアルゴリズムは、最新使用ページスワッピングアルゴリズムと比較すると、ジョブ当り印字ピッチスキップの比率を約６％減少させ（１2.２％から6.３０％へ）、また、１６メガバイトのメモリ及び平均転送速度が6.５メガビット／秒のディスクを有するＥＲシステムに対し、平均ターンアラウンドタイムを1.８％減少させる（6.８０３分から6.６７７分へ）、ということを示している。ＥＳＳメモリの量が増加するにつれ、最新使用セグメントスワッピングアルゴリズムと最新使用ページスワッピングアルゴリズムとの間の性能の差は減少する。また、ディスク帯域幅が増大するにつれ、最新使用セグメントスワッピングアルゴリズムと最新使用ページスワッピングアルゴリズムとの間の性能の差は減少する。最後に、メモリ及び／又はディスク帯域幅が増大するにつれ、平均ターンアラウンドタイム及び印字ピッチスキップの両方は、いずれのメモリ管理アルゴリズムに対しても減少する。
【０１０２】
前記結果は、ＴＡＴについて測定したＥＲシステムの性能及び印字ピッチスキップは、固定セットの資源を与えられると、使用したメモリ管理手法によって影響を受ける可能性があるということを示している。部分画像をスワップする能力は、限定資源を有するＥＲシステムの性能を向上させることができる。
メモリ管理アルゴリズムは包括的資源割当てアルゴリズムのうちの小部分である。詳述すると、メモリ管理アルゴリズムは、到来画像のための場所を作るために、メモリ内に存在しているページのうちのどれをスワップするかを特殊な場合中に決定するルーチンである。実際のジョブスケジューリング及び資源確保は資源割当てアルゴリズムによって行なわれる。
【０１０３】
いま問題としている電子複写（ＥＲ）装置は、画像を圧縮ビットマップ形式で記録的に及び一時的に記憶するために硬式ディスクを使用する一つの電子工学サブシステムである。本来、ＥＳＳは、画像を一時的に記憶するために用いることのできる或る量の固定メモリ、及び画像をディスクから検索し又はこれに記憶させる際に用いる効果的なディスク帯域幅を有している。モデルの全ての与えられた走行に対してＥＳＳは固定した量のメモリ及びディスク帯域幅を有しているが、これらはいずれも可変及び調整可能である。これら２つの変数が調整可能であるので、アーキテクチャについての類似しているが別々のインプリメンテーションに対してシステム性能の比較を行なうことができる。これらのサンプル点を用いてディスク帯域幅／メモリトレードオフ曲線を描くことができる。図２４ないし２６を参照されたい。
【０１０４】
このような評価に対する動機は、或るセットの固定資源を与えられると、即ち、この場合はメモリの大きさ及びディスク帯域幅を与えられると、或るメモリ管理方式が他のメモリ管理手法よりも性能がすぐれていることがあるからである。システム性能に本来的に影響を与える重要なシステムパラメータは、メモリの大きさ、ディスク帯域幅、資源管理、及びメモリスワッピングルーチンである。
【０１０５】
平均ターンアラウンドタイム（ＴＡＴ）及び印字ピッチスキップの比率はいずれも資源管理アルゴリズムの性能を測定する基準として用いられる。平均ＴＡＴは一つのセットのジョブの走査／印字を完了するのにかかる平均期間と定義され、これには、プログラム、ロード、走査、印字、及びシステムからのジョブのアンロードに要する時間、ならびに、システムまたはオペレータが使用中又は作業中であったために生じた全ての待ち時間が含まれる。単一ジョブに対するターンアラウンドタイムは、或るジョブが作業のためにオペレータに到着したときからこのジョブがオペレータによってシステムから除去されるまでの時間として詳細に測定される。
【０１０６】
第２の性能測定はシステムによって発生させられる印字ピッチスキップの比率である。単一印字ピッチスキップは、ジョブの印字最中に、ＥＳＳが所要の印字画像を該画像に対する指定印字時にＩＯＴに提供することができないときに生ずる。発生する各ピッチスキップは、ＩＯＴエンジンが、運転してはいるが、ハードコピー出力を何も作っていないときの時間を表す。印字ピッチスキップの比率は、印字ピッチスキップの総数を、作られる刷りの総数に印字ピッチスキップの総数を加えたもので除して計算される。
【０１０７】
現在の研究に対しては、硬式ディスクに接続された１６、２０、２４、３２、４８、及び６４メガバイトのメモリを有するシステムに対して性能を評価する。このディスクの転送速度（平均回転待時間も平均シーク時間も含まない）は１秒当り6.５、7.５、8.５、または１２メガビットである。各ディスクトランザクションに対し、平均回転待ち時間及び平均シーク時間を考慮して、追加の平均オーバヘッドコストを有効転送速度に含ませた。この結果、２４の別々のＥＲシステム構成を組み合わせたものが得られる。前記２４の構成は各メモリ管理アルゴリズムのモデルとして作ったものである。ジョブは、４ｘ７  ＲＢＧ  ２００Ｋの計算マトリックスから発生され、１月当り約３５０Ｋ印字の量を表すようにシミュレーションが行なわれる。
【０１０８】
【発明の効果】
メモリ管理ルーチンは或る状態において性能を表す。しかし、或る状態の下では、これらのパラメータすらも、システム性能決定の際に行なう役目は小さい。原画数が小さいときには、資源割当て計画は取るに足りないものとなる。この場合には、全ての原画はメモリ内に同時に存在することができ、従って、印字エンジンは印字ピッチスキップを発生させることなしに最高速度で運転することができる。
【０１０９】
資源割当てが取るに足りず、そしてディスク帯域幅があまり重要でないという他の場合は、原画当り印字数が１に等しいときである。この場合には、原画を走査してメモリに入れ、その画像を一時的に記憶するための要求をディスクへ送る。原画当り１つの印字しか必要でないのであるが、システム内の誤りのために１つまたは複数の画像を再印字することが必要となった場合、各画像は、走査されると、これにつづいてディスクに記憶される。一つのページが成功的にディスクに退避させられて印字された後にのみ、利用可能メモリを増大させるためにメモリから削除される。ページの走査は、この機能に利用可能な十分なメモリがあるときに、行なわれる。走査動作に利用可能なメモリの十分な供給があるまで、走査スキップが引き起こされる。資源割当ては取るに足りないものであるが、ディスク帯域幅が画像の走査及び印字と整合することができないと、発生する。
【０１１０】
原画当り印字数が１よりも大きく、そしてジョブの全てのセグメントがメモリ内に同時に存在することのできないときに、メモリ割当て及びディスク帯域幅はシステム性能の決定において命令的役割をなす。メモリ管理及びディスク帯域幅割当ての役割は、固定資源のレベルならびに現在のジョブ及びシステム状態に関係する情報が既知である場合には、印字ピッチスキップの数及びＴＡＴを減少させるように、ディスク及びメモリの使用をスケジュールしようとすることである。これは、指定グループの画像に必要なディスク帯域幅及びＥＳＳメモリを前もってスケジュールすることによって行なわれる。
【０１１１】
スプールディスクの目的は、圧縮ビットマップ形式の走査済み画像のための一時的記憶媒体として働くことである。従って、原画は１回走査するだけでよい。本質的には、ディスクは、主メモリの延長として使用され、メモリマネージャによって必要と考えられるときに画像を記憶及び検索する。そこで、メモリマネージャは、出力装置によって望まれるときに画像が主メモリ内にあることを保証するように利用可能なディスク帯域幅を使用することができる。メモリマネージャは、高い優先順位の画像に対して道をあけるため、或る時間中は必要でない画像を除去するということができる。
【０１１２】
図２２及び２３に、最新使用セグメントスワッピングアルゴリズムの結果を、最新使用ページスワッピングアルゴリズムとの比較とともに詳細に示す。最も限定構成したシステム（メモリ＝１６メガバイト、ディスク帯域幅＝6.５メガビット／秒）に対し、最新使用セグメントスワッピングアルゴリズムは印字ピッチスキップを１2.２７％から6.３０％へ約２分の１に減少させ、平均ＴＡＴを6.８０３分から6.６７７分へ1.８％減少させる。スキップ及びＴＡＴの減少は、総主メモリが増大するにつれて少なくなる。図２４及び２５を参照されたい。この結果また、ディスク帯域幅が増大するにつれて最新使用セグメントスワッピングアルゴリズムの影響が減るということを示している。図２５及び２６を参照されたい。
【０１１３】
図２２及び２３の表は、順次限定セグメントスワッピングアルゴリズムの結果、及びこのアルゴリズムと最新使用ページスワッピングアルゴリズムとの比較を示すものである。順次限定セグメントスワッピングアルゴリズムをモデルとして限定構成したシステム（メモリ＝１６メガバイト、ディスク帯域幅＝6.５メガビット／秒）は印字ピッチスキップの比率を１2.２７％から6.２２％へ約２分の１に減少させる。ＴＡＴは6.８０３分から6.６７７分へ1.８％減少させられる。この結果はまた、順次限定セグメントスワッピングアルゴリズムと最新使用ページスワッピングアルゴリズムとの間の印字ピッチスキップの差は、ディスク帯域幅が6.５メガビット／秒から１２メガビット／秒へ増大するにつれて減少するということを示している。
【０１１４】
以上、本発明をその実施例について説明したが、当業者には明らかなように種々の代替、変形及び変更が可能である。即ち、特許請求の範囲に記載のごとき本発明の精神及び範囲を逸脱することなしに種々の代替、変形及び変更を行なうこが可能である。
【図面の簡単な説明】
【図１】本発明にかかる電子式印字装置を示す斜視図である。
【図２】図１に示す印字装置の主要部材を示すブロック線図である。
【図３】図１に示す印字装置の主要な機械的構成部材を示す立面図である。
【図４】図１に示す印字装置のための書類走査装置の構造の細部を示す側面図である。
【図５】図１に示す印字装置のための制御装置部の主な部品を示すブロック線図である。
【図６】図１に示す印字装置のための制御装置部の主な部品を示すブロック線図である。
【図７】図１に示す印字装置のための制御装置部の主な部品を示すブロック線図である。
【図８】図１に示す印字装置のためのプリント配線盤及び共用線接続部を具備するオペレーティングシステムのブロック線図である。
【図９】図１に示す印字装置のユーザインタフェース（ＵＩ）タッチスクリーン上に表示されるジョブプログラミングティケット及びジョブスコアカードの例を示す平面図である
【図１０】本発明に対する一つのモデルとして用いられたシステムのブロック線図である。
【図１１】種々のディスク帯域幅に対し、メモリのメガバイト値に従う印字スキップの比率を示すグラフである。
【図１２】種々のディスク帯域幅に対し、メモリの種々のメガバイト値におけるターンアラウンドタイムを示すグラフである。
【図１３】本発明のモデルとして用いたハードウェア構成のブロック線図である。
【図１４】本発明の種々の構成部材とインタフェースされる本発明のメモリ／ディスク帯域幅トレードオフ手段を示す流れ図である。
【図１５】本発明の種々の構成部材とインタフェースされる本発明の走査マネージャを示す流れ図である。
【図１６】本発明の複数の他の構成部材とインタフェースされる本発明の印字マネージャを示す流れ図である。
【図１７】印字長期スケジューラを含む本発明の他の種々の構成部材とインタフェースされる本発明の資源マネージャの流れ図である。
【図１８】本発明のオフセット法を示す説明図である。
【図１９】本発明の単一セットアドバンススケジューリング法を示す説明図である。
【図２０】本発明の連続セットスケジューリング法を示す説明図である。
【図２１】ディスク帯域幅をターンアラウンドタイム百分率差及び百分率ピッチスキップ百分率差と比較する表である。
【図２２】最新使用セグメントスワッピングアルゴリズムと最新使用退避ページスワッピングアルゴリズムとの比較を示す表である。
【図２３】図２２の表に示すディスク転送速度とは異なるディスク転送速度における最新使用セグメントスワッピングアルゴリズムと最新使用退避ページスワッピングアルゴリズムとの比較を示す表である。
【図２４】種々のディスク帯域幅に対し、メモリのメガバイト値に従う分単位のターンアラウンドタイムを比較するグラフである。
【図２５】種々のディスク帯域幅に対し、メモリのメガバイト値に従う印字ピッチスキップの百分率を比較するグラフである。
【図２６】メモリの種々の大きさに対し、分単位のターンアラウンドタイムをディスク帯域幅及び秒当りメガバイト値と比較するグラフである。
【図２７】種々のメモリメガバイトレベルにおいて、順次限定セグメントスワッピングアルゴリズム及び最新使用ページスワッピングアルゴリズムに対する印字ピッチスキップ百分率を比較する表である。
【図２８】本発明における種々のスワッピングアルゴリズムを比較する棒グラフである。
【符号の説明】
６  走査装置部
７  制御装置部
８  印字装置部
５６  主メモリ
２０４  スプールディスク
２２０  ＥＳＳメモリ
２２４  スプーリングディスク
２５６  システムマネージャ
２６０  資源マネージャ
【図１】
0003732235.tif 000003
【図２】
0003732235.tif 000004
【図３】
0003732235.tif 000005
【図４】
0003732235.tif 000006
【図５】
0003732235.tif 000007
【図６】
0003732235.tif 000008
【図７】
0003732235.tif 000009
【図８】
0003732235.tif 000010
【図９】
0003732235.tif 000011
【図１０】
0003732235.tif 000012
【図１１】
0003732235.tif 000013
【図１２】
0003732235.tif 000014
【図１３】
0003732235.tif 000015
【図１４】
0003732235.tif 000016
【図１５】
0003732235.tif 000017
【図１６】
0003732235.tif 000018
【図１７】
0003732235.tif 000019
【図１８】
0003732235.tif 000020
【図１９】
0003732235.tif 000021
【図２０】
0003732235.tif 000022
【図２１】
0003732235.tif 000023
【図２２】
0003732235.tif 000024
【図２３】
0003732235.tif 000025
【図２４】
0003732235.tif 000026
【図２５】
0003732235.tif 000027
【図２６】
0003732235.tif 000028
【図２７】
0003732235.tif 000029
【図２８】
0003732235.tif 000030