(57)【特許請求の範囲】
【請求項１】
メモリがデータを記憶する工程と、
制御部が、前記メモリに記憶されたデータの削除順序を管理し、前記メモリの空き領域の断片化解消処理を行うときに当該メモリに記憶されたデータを当該データの削除順序に基づいて並べ替える工程と、を有し、
前記制御部は、前記データを並べ替えるとき、最初に削除されるデータを前記メモリの空き領域と連続する記憶領域に配置することを特徴とする画像処理装置のメモリ管理方法。
【請求項２】
メモリがデータを記憶する工程と、
制御部が、前記メモリに記憶されたデータの削除順序を管理し、新たなデータが前記メモリに記憶されるたびに当該メモリに記憶されたデータを当該データの削除順序に基づいて並べ替える工程と、を有し、
前記制御部は、前記データを並べ替えるとき、最初に削除されるデータを前記メモリの空き領域と連続する記憶領域に配置することを特徴とする画像処理装置のメモリ管理方法。
【請求項３】
前記制御部は、前記データを並べ替えるとき、前記データを当該データの削除順序に従って連続した記憶領域に配置することを特徴とする請求項１又は２に記載の画像処理装置のメモリ管理方法。
【請求項４】
前記制御部は、前記データの種類に応じて個別にデータの削除順序を管理し、前記データを並べ替えるとき、個別に管理されたデータの削除順序に基づいて前記データの種類ごとに前記データを並べ替えることを特徴とする請求項１から３のいずれか一項に記載の画像処理装置のメモリ管理方法。
【請求項５】
前記データは、固定長のブロック単位で管理されるデータを含むことを特徴とする請求項１から４のいずれか一項に記載の画像処理装置のメモリ管理方法。
【請求項６】
前記データは、可変長のブロック単位で管理されるデータを含むことを特徴とする請求項１から５のいずれか一項に記載の画像処理装置のメモリ管理方法。
【請求項７】
コンピュータを、
前記コンピュータのメモリにデータを記憶する手段、
前記メモリに記憶されたデータの削除順序を管理し、前記メモリの空き領域の断片化解消処理を行うときに当該メモリに記憶されたデータを当該データの削除順序に基づいて並べ替え、当該データを並べ替えるとき、最初に削除されるデータを前記メモリの空き領域と連続する記憶領域に配置する手段、
として機能させることを特徴とするプログラム。
【請求項８】
コンピュータを、
前記コンピュータのメモリにデータを記憶する手段、
前記メモリに記憶されたデータの削除順序を管理し、新たなデータが前記メモリに記憶されるたびに当該メモリに記憶されたデータを当該データの削除順序に基づいて並べ替え、当該データを並べ替えるとき、最初に削除されるデータを前記メモリの空き領域と連続する記憶領域に配置する手段、
として機能させることを特徴とするプログラム。
【請求項９】
前記データを並べ替えるとき、前記データを当該データの削除順序に従って連続した記憶領域に配置することを特徴とする請求項７又は８に記載のプログラム。
【請求項１０】
前記データの種類に応じて個別にデータの削除順序を管理し、前記データを並べ替えるとき、個別に管理されたデータの削除順序に基づいて前記データの種類ごとに前記データを並べ替えることを特徴とする請求項７から９のいずれか一項に記載のプログラム。
【請求項１１】
前記データは、固定長のブロック単位で管理されるデータを含むことを特徴とする請求項７から１０のいずれか一項に記載のプログラム。
【請求項１２】
前記データは、可変長のブロック単位で管理されるデータを含むことを特徴とする請求項７から１１のいずれか一項に記載のプログラム。
【請求項１３】
データを記憶するメモリと、
前記メモリに記憶されたデータの削除順序を管理し、前記メモリの空き領域の断片化解消処理を行うときに当該メモリに記憶されたデータを当該データの削除順序に基づいて並べ替える制御部と、を備え、
前記制御部は、前記データを並べ替えるとき、最初に削除されるデータを前記メモリの空き領域と連続する記憶領域に配置することを特徴とする画像処理装置。
【請求項１４】
データを記憶するメモリと、
前記メモリに記憶されたデータの削除順序を管理し、新たなデータが前記メモリに記憶されるたびに当該メモリに記憶されたデータを当該データの削除順序に基づいて並べ替える制御部と、を備え、
前記制御部は、前記データを並べ替えるとき、最初に削除されるデータを前記メモリの空き領域と連続する記憶領域に配置することを特徴とする画像処理装置。
【請求項１５】
前記制御部は、前記データを並べ替えるとき、前記データを当該データの削除順序に従って連続した記憶領域に配置することを特徴とする請求項１３又は１４に記載の画像処理装置。
【請求項１６】
前記制御部は、前記データの種類に応じて個別にデータの削除順序を管理し、前記データを並べ替えるとき、個別に管理されたデータの削除順序に基づいて前記データの種類ごとに前記データを並べ替えることを特徴とする請求項１３から１５のいずれか一項に記載の画像処理装置。
【請求項１７】
前記データは、固定長のブロック単位で管理されるデータを含むことを特徴とする請求項１３から１６のいずれか一項に記載の画像処理装置。
【請求項１８】
前記データは、可変長のブロック単位で管理されるデータを含むことを特徴とする請求項１３から１７のいずれか一項に記載の画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置のメモリ管理方法、プログラム及び画像処理装置に関する。
【背景技術】
【０００２】
データの入力に基づいて画像形成（印刷）を行う画像形成装置は、解析処理やラスタライズ処理等、入力されたデータからビットマップ画像データを生成するインタプリタ処理を行う。インタプリタ処理では、処理前後のデータをメモリに展開する。
【０００３】
画像形成装置に入力可能なデータは、画像データに限らず、ＰＳ（PostScript）によって記述されたデータファイルや、ＰＤＦ（Portable Document Format）、ＸＰＳ（XML Paper Specification）等の各種の電子文書データを用いることができる。
近年、前述のＸＰＳをはじめとする新フォーマットの追加や、ＰＳ、ＰＤＦのバージョンアップ等がさかんに行われており、これに伴い画像形成装置に入力されるデータの容量は増加している。このため、画像形成装置のインタプリタ処理に必要なメモリ容量も増加している。
【０００４】
画像形成装置のメモリ容量を増加させる方法として、メモリの増設がある。しかし、メモリの増設は、画像形成装置のコストを上げてしまう。その一方、画像形成装置の市場における価格競争の激化により、画像形成装置はコストダウンを求められている。そのため、メモリを効率的に活用する技術が求められている。
【０００５】
メモリを効率的に活用する技術として、メモリの空き領域の断片化解消処理（以下、単に断片化解消処理と記載）がある（例えば特許文献１、特許文献２等）。断片化解消処理は、メモリに記憶された複数のデータの各データ間に生じた空き領域（断片化された空き領域）を統合して大きな空き領域とし、当該大きな空き領域に新たなデータを記憶可能とする処理である。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平１１−２１３１０７号公報
【特許文献２】特開２００２−１１６７４８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１、特許文献２等の、従来技術による断片化解消処理では、空き領域の統合後、すぐにメモリの空き領域が断片化されてしまう。
図２５（Ａ）、（Ｂ）に、従来技術による断片化解消処理後に生じる空き領域の断片化の一例を示す。図２５（Ａ）は、断片化解消処理直後のメモリの状態の一例を示し、図２５（Ｂ）は、断片化解消処理後に生じたメモリの空き領域の断片化の一例を示す。
図２５（Ａ）に示すように、断片化解消処理によって統合された空き領域Ｅ１を有するメモリの記憶領域には、複数のデータを記憶されたメモリの記憶領域（例えば図２５（Ａ）の記憶領域Ｄ１、Ｄ２）がある。その後、使用済みとなったデータは削除されるため、図２５（Ｂ）に示すように、記憶領域Ｄ１、Ｄ２内に空き領域Ｅ２、Ｅ３が生じる。
また、図示しないが、空き領域Ｅ２、Ｅ３には、その後に生じる新たなデータが記憶されるが、その新たなデータの容量は、空き領域Ｅ２、Ｅ３の空き容量に必ずしも合致しない。このため、空き領域Ｅ２、Ｅ３の一部が断片化された空き領域として残ることがある。
このように、断片化処理解消後、メモリの空き領域の断片化はたちまち再び生じる。
【０００８】
本発明は、メモリの空き領域の断片化を抑止することを目的とする。
【課題を解決するための手段】
【０００９】
請求項１に記載の発明による画像処理装置のメモリ管理方法は、メモリがデータを記憶する工程と、制御部が、前記メモリに記憶されたデータの削除順序を管理し、前記メモリの空き領域の断片化解消処理を行うときに当該メモリに記憶されたデータを当該データの削除順序に基づいて並べ替える工程と、を有し、前記制御部は、前記データを並べ替えるとき、最初に削除されるデータを前記メモリの空き領域と連続する記憶領域に配置することを特徴とする。
【００１０】
請求項２に記載の発明による画像処理装置のメモリ管理方法は、メモリがデータを記憶する工程と、制御部が、前記メモリに記憶されたデータの削除順序を管理し、新たなデータが前記メモリに記憶されるたびに当該メモリに記憶されたデータを当該データの削除順序に基づいて並べ替える工程と、を有し、前記制御部は、前記データを並べ替えるとき、最初に削除されるデータを前記メモリの空き領域と連続する記憶領域に配置することを特徴とする。
【００１１】
請求項３に記載の発明は、請求項１又は２に記載の画像処理装置のメモリ管理方法であって、前記制御部は、前記データを並べ替えるとき、前記データを当該データの削除順序に従って連続した記憶領域に配置することを特徴とする。
【００１２】
請求項４に記載の発明は、請求項１から３のいずれか一項に記載の画像処理装置のメモリ管理方法であって、前記制御部は、前記データの種類に応じて個別にデータの削除順序を管理し、前記データを並べ替えるとき、個別に管理されたデータの削除順序に基づいて前記データの種類ごとに前記データを並べ替えることを特徴とする。
【００１３】
請求項５に記載の発明は、請求項１から４のいずれか一項に記載の画像処理装置のメモリ管理方法であって、前記データは、固定長のブロック単位で管理されるデータを含むことを特徴とする。
【００１４】
請求項６に記載の発明は、請求項１から５のいずれか一項に記載の画像処理装置のメモリ管理方法であって、前記データは、可変長のブロック単位で管理されるデータを含むことを特徴とする。
【００１６】
請求項７に記載の発明によるプログラムは、コンピュータを、前記コンピュータのメモリにデータを記憶する手段、前記メモリに記憶されたデータの削除順序を管理し、前記メモリの空き領域の断片化解消処理を行うときに当該メモリに記憶されたデータを当該データの削除順序に基づいて並べ替え、当該データを並べ替えるとき、最初に削除されるデータを前記メモリの空き領域と連続する記憶領域に配置する手段、として機能させることを特徴とする。
【００１７】
請求項８に記載の発明によるプログラムは、コンピュータを、前記コンピュータのメモリにデータを記憶する手段、前記メモリに記憶されたデータの削除順序を管理し、新たなデータが前記メモリに記憶されるたびに当該メモリに記憶されたデータを当該データの削除順序に基づいて並べ替え、当該データを並べ替えるとき、最初に削除されるデータを前記メモリの空き領域と連続する記憶領域に配置する手段、として機能させることを特徴とする。
【００１８】
請求項９に記載の発明は、請求項７又は８に記載のプログラムであって、前記データを並べ替えるとき、前記データを当該データの削除順序に従って連続した記憶領域に配置することを特徴とする。
【００１９】
請求項１０に記載の発明は、請求項７から９のいずれか一項に記載のプログラムであって、前記データの種類に応じて個別にデータの削除順序を管理し、前記データを並べ替えるとき、個別に管理されたデータの削除順序に基づいて前記データの種類ごとに前記データを並べ替えることを特徴とする。
【００２０】
請求項１１に記載の発明は、請求項７から１０のいずれか一項に記載のプログラムであって、前記データは、固定長のブロック単位で管理されるデータを含むことを特徴とする。
【００２１】
請求項１２に記載の発明は、請求項７から１１のいずれか一項に記載のプログラムであって、前記データは、可変長のブロック単位で管理されるデータを含むことを特徴とする。
【００２３】
請求項１３に記載の発明による画像処理装置は、データを記憶するメモリと、前記メモリに記憶されたデータの削除順序を管理し、前記メモリの空き領域の断片化解消処理を行うときに当該メモリに記憶されたデータを当該データの削除順序に基づいて並べ替える制御部と、を備え、前記制御部は、前記データを並べ替えるとき、最初に削除されるデータを前記メモリの空き領域と連続する記憶領域に配置することを特徴とする。
請求項１４に記載の発明による画像処理装置は、データを記憶するメモリと、前記メモリに記憶されたデータの削除順序を管理し、新たなデータが前記メモリに記憶されるたびに当該メモリに記憶されたデータを当該データの削除順序に基づいて並べ替える制御部と、を備え、前記制御部は、前記データを並べ替えるとき、最初に削除されるデータを前記メモリの空き領域と連続する記憶領域に配置することを特徴とする。
請求項１５に記載の発明は、請求項１３又は１４に記載の画像処理装置であって、前記制御部は、前記データを並べ替えるとき、前記データを当該データの削除順序に従って連続した記憶領域に配置することを特徴とする。
請求項１６に記載の発明は、請求項１３から１５のいずれか一項に記載の画像処理装置であって、前記制御部は、前記データの種類に応じて個別にデータの削除順序を管理し、前記データを並べ替えるとき、個別に管理されたデータの削除順序に基づいて前記データの種類ごとに前記データを並べ替えることを特徴とする。
請求項１７に記載の発明は、請求項１３から１６のいずれか一項に記載の画像処理装置であって、前記データは、固定長のブロック単位で管理されるデータを含むことを特徴とする。
請求項１８に記載の発明は、請求項１３から１７のいずれか一項に記載の画像処理装置であって、前記データは、可変長のブロック単位で管理されるデータを含むことを特徴とする。
【発明の効果】
【００２４】
本発明によれば、メモリの空き領域の断片化を抑止することができる。
【図面の簡単な説明】
【００２５】
【図１】画像形成装置１のブロック図である。
【図２】画像形成装置１で行われる画像処理の概要を示す図である。
【図３】ＲＡＭ１２の記憶内容の一例を示すイメージ図である。
【図４】メモリ管理テーブルによるデータ管理の流れを説明する図である。図４（Ａ）は、固定長ブロックに分割可能なデータの一例を示す図である。図４（Ｂ）は、分割前のデータを示すラベル、当該データの保持期間、当該データの構成要素、構成要素の保存位置、データ保存範囲及び走査完了位置の対応付けの一例を示す図である。図４（Ｃ）は、対応付けられた登録データがメモリ管理テーブルに登録される一例を示す図である。
【図５】メモリ管理テーブルによるデータ管理の流れを説明する図である。図５（Ａ）は、「保持期間がＦＢである」データが既にメモリ管理テーブル上に登録されている「保持期間がＤＬである」データよりも上側に登録される一例を示す図である。図５（Ｂ）は、「保持期間がＤＬである」データの上側に二つの「保持期間がＦＢである」データが登録されると、その「保持期間がＤＬである」データの上側にさらに「保持期間がＦＢである」データを追加することがないことを示す図である。図５（Ｃ）は、登録データがメモリ管理テーブル上から削除される一例を示す図である。
【図６】ＤＬ／ＦＢ記憶領域に対する断片化解消処理の概略を示す。
【図７】断片化解消処理におけるＲＡＭ１２の記憶領域を示したイメージ図である。図７（Ａ）は、断片化解消処理前のＲＡＭ１２の記憶領域を示す図である。図７（Ｂ）は、記憶範囲算出処理の結果の一例を示す図である。図７（Ｃ）は、メモリブロックのセットの一例を示す図である。
【図８】断片化解消処理におけるＲＡＭ１２の記憶領域を示したイメージ図である。図８（Ａ）は、分割データＮ１を入替対象データとして扱う処理を示す図である。図８（Ｂ）は、入替対象データＢＩの分割データのデータ保存範囲を示す図である。図８（Ｃ）は、図７（Ｃ）に示すメモリブロックとは別のメモリブロックのセットの一例を示す図である。
【図９】断片化解消処理におけるＲＡＭ１２の記憶領域を示したイメージ図である。図９（Ａ）は、分割データＮ２を入替対象データＮ１と差し替える処理を示す図である。図９（Ｂ）は、繰り返し処理後のＤＬ／ＦＢ記憶領域に記憶されているＤＬ、ＦＢのうち、最初に削除されるデータより前のアドレスに存在するＤＬ、ＦＢの分割データの削除を示す図である。
【図１０】断片化解消処理におけるＲＡＭ１２の記憶領域を示したイメージ図である。図１０（Ａ）は、圧縮データのシフトに伴う圧縮データ及び空き領域の位置変更イメージを示す図である。図１０（Ｂ）は、圧縮データのシフト完了状態を示す図である。図１０（Ｃ）は、最後に削除される圧縮データの再配置に伴う圧縮データの位置変更イメージを示す図である。図１０（Ｄ）は、最後に削除される圧縮データの再配置完了状態を示す図である。
【図１１】断片化解消処理におけるＲＡＭ１２の記憶領域を示したイメージ図である。図１１（Ａ）は、最後に削除される圧縮データの再配置完了後の圧縮データのシフトに伴う圧縮データ及び空き領域の位置変更イメージを示す図である。図１１（Ｂ）は、最後に削除される圧縮データの再配置完了後の圧縮データのシフト完了状態を示す図である。図１１（Ｃ）は、最後から２番目に削除される圧縮データの再配置に伴う圧縮データの位置変更イメージを示す図である。図１０（Ｄ）は、最後から２番目に削除される圧縮データの再配置完了状態を示す図である。
【図１２】断片化解消処理完了後のＲＡＭ１２の記憶領域を示す図である。
【図１３】断片化解消処理後のＲＡＭ１２におけるデータ削除の一例を示す図である。
【図１４】データの受信から印刷を行うに至る処理の概略を示すフローチャートである。
【図１５】図１４のステップＳ２に示す解析処理の流れを示すフローチャートである。
【図１６】図１４のステップＳ３に示すラスタライズ処理の流れを示すフローチャートである。
【図１７】図１４のステップＳ４に示す圧縮処理の流れを示すフローチャートである。
【図１８】図１６のステップＳ２２及び図１７のステップＳ３４に示すＲＡＭ開放処理の流れを示すフローチャートである。
【図１９】図１７のステップＳ３３に示す断片化解消処理の流れを示すフローチャートである。
【図２０】図１９のステップＳ５１に示すＤＬ／ＦＢ記憶領域断片化解消処理の流れを示すフローチャートである。
【図２１】図１９のステップＳ５２に示す圧縮データ記憶領域断片化解消処理の流れを示すフローチャートである。
【図２２】図２０のステップＳ６１及び図２１のステップＳ７１に示す記憶範囲算出処理の流れを示すフローチャートである。
【図２３】図２０のステップＳ６２に示すＤＬ／ＦＢ位置並べ替え処理の流れを示すフローチャートである。
【図２４】図２１のステップＳ７２に示す圧縮データ位置並べ替え処理の流れを示すフローチャートである。
【図２５】従来技術による断片化解消処理後に生じる空き領域の断片化の一例を示す説明図である。図２５（Ａ）は、断片化解消処理直後のメモリの状態の一例を示す図である。図２５（Ｂ）は、断片化解消処理後に生じたメモリの空き領域の断片化の一例を示す図である。
【発明を実施するための形態】
【００２６】
以下、図を参照して本発明の実施の形態の例を詳細に説明する。
本発明に係る画像処理装置としては、例えばプリンタ、複写機、ファクシミリ装置又はこれらの複合機等の画像形成装置に搭載される画像処理装置が挙げられるが、これに限定されるものではない。
【００２７】
図１に、画像形成装置１のブロック図を示す。
画像形成装置１は、ＣＰＵ１１、ＲＡＭ１２、ＲＯＭ１３、記憶部１４、インタフェース１５、画像形成部１６及びＡＳＩＣ（Application Specific Integrated Circuit）１７を有し、これらの各構成はバス１８によって接続される。
【００２８】
ＣＰＵ１１は、ＲＯＭ１３内に記憶されたプログラムと協働し、ＲＡＭ１２に展開されたプログラムやデータ等に従って画像形成装置１の動作制御を行う。
ＲＡＭ１２は、ＣＰＵ１１の処理によって展開されたデータや、当該処理によって一時的に生じたデータ等を格納する。
ＲＯＭ１３は、ＣＰＵ１１によって読み出されるプログラムやデータ等を記憶する。
【００２９】
記憶部１４は、ＣＰＵ１１によって読み出されるプログラムやデータ等を記憶する。記憶部１４は、プログラムやデータ等を書き換え可能な記憶装置である。記憶部１４は、例えばフラッシュメモリやハードディスクドライブ、その他の書き換え可能な記憶装置又はそれらの記憶装置の組合せ等によって構成される。
【００３０】
インタフェース１５は、外部の機器を接続し、当該外部の機器との間でデータ伝送を可能とする。インタフェース１５を介した外部の機器の接続及びデータ伝送は、有線／無線を問わず、またそのプロトコルやその他の接続形式に関する条件（例えば規格等）を問わない。本実施形態では、インタフェース１５は、ネットワークインターフェースカード（Network Interface Card、ＮＩＣ）等の通信装置を有し、回線２を通じて外部入力装置３からデータを受信する。
【００３１】
画像形成部１６は、インタフェース１５を介して入力されたデータに基づいた画像形成（印刷）を行う。
画像形成部１６に採用可能な印刷方式として、例えば電子写真方式やインクジェット方式、熱転写方式、オフセット等が挙げられる。本実施形態では、画像形成部１６は、電子写真方式による画像形成を行うための構成を有する。
ＡＳＩＣ１７は、後述する圧縮処理を行うための回路である。
【００３２】
図２に、画像形成装置１で行われる画像処理の概要を示す。
インタフェース１５が受信するデータには、ページ記述言語（以下、ＰＤＬ：Page Description Language）が含まれる。
ＣＰＵ１１は、ＲＯＭ１３内に記憶されたプログラムとの協働により、解析部２１やラスタライズ部２２として機能し、ＡＳＩＣ１７と協働して画像処理を行う。
【００３３】
解析部２１は、ＰＤＬに対して解析処理を施し、中間言語データであるディスプレイリスト（以下、ＤＬ：Display List）を生成する。ＤＬは、ページ単位で生成される。ＤＬは、ＲＡＭ１２に記憶される。
【００３４】
ラスタライズ部２２は、ＤＬに対してラスタライズ処理を施し、ビットマップデータを生成する。ビットマップデータは、１ページを複数のバンドに分割したバンド単位で生成される。バンド単位のビットマップデータは、フレームバッファ（以下、ＦＢ：Frame Buffer）としてＲＡＭ１２に記憶される。
【００３５】
ＡＳＩＣ１７は、ＦＢに対して圧縮処理を施し、圧縮データを生成する。圧縮データは、ＲＡＭ１２に記憶される。
１ページ分のビットマップデータに対応する圧縮データの生成完了後、画像形成部１６は、圧縮データを読み出して印刷を行う。
【００３６】
図３に、ＲＡＭ１２の記憶内容の一例を示す。
図３に示すように、ＲＡＭ１２は、ＤＬ、ＦＢ及び圧縮データを記憶することができる。本実施形態では、ＲＡＭ１２が記憶する各データのうち、ＤＬ及びＦＢは、一のデータを複数の固定長のブロック単位に分割して管理することができる。図３では、例示として、ＤＬ１の一部についてのみ固定長のブロック単位に分割された分割データを図示している。圧縮データは、固定長ブロックに分割可能なデータとしては取り扱われず、一のデータが連続した記憶領域に記憶される。
また、本実施形態では、圧縮データがＲＡＭ１２の記憶領域の先頭アドレス側寄りに記憶され、ＤＬ及びＦＢがＲＡＭ１２の記憶領域の末尾アドレス側寄りに記憶される。以下、圧縮データが記憶される側のＲＡＭ１２の記憶領域を圧縮データ記憶領域と記載し、ＤＬ及びＦＢが記憶されるＲＡＭ１２の記憶領域をＤＬ／ＦＢ記憶領域と記載する。
【００３７】
ＣＰＵ１１は、ＲＯＭ１３内に記憶されたプログラムとの協働により、ＲＡＭ１２に記憶された各種データの管理を行う。
ＣＰＵ１１は、メモリ管理テーブルを生成してＲＡＭ１２に記憶されたＤＬ、ＦＢ及び圧縮データを管理する。
以下、図４（Ａ）〜（Ｃ）及び図５（Ａ）〜（Ｃ）を用いて、メモリ管理テーブルによるデータ管理の流れを説明する。
【００３８】
図４（Ａ）に示すように、ＣＰＵ１１は、固定長ブロックに分割可能なデータを分割し、分割データを生成する。
図４（Ｂ）、（Ｃ）に示すように、ＣＰＵ１１は、分割前のデータを示すラベル、当該データの保持期間、当該データの構成要素、構成要素の保存位置、データ保存範囲及び走査完了位置を対応付けてメモリ管理テーブルに登録する。
【００３９】
分割前のデータを示すラベルは、分割データの分割前のデータを示す情報である。例示として、図４（Ｂ）、（Ｃ）及び図５（Ａ）〜（Ｃ）では、「Ａ」、「Ｂ」、「Ｃ」のように１文字ののアルファベットで示している。
データの保持期間は、分割前のデータを示すラベルに対応するデータをＲＡＭ１２上で保持する期間を示す情報である。本実施形態では、ＤＬ、ＦＢ及び圧縮データはそれぞれ個別に保持期間を予め定められており、データの種類で保持期間を区別することができる。例示として、図４（Ｂ）、（Ｃ）及び図５（Ａ）〜（Ｃ）では、「ＤＬ」、「ＦＢ」のようにファイルの種類で保持期間を示している。
データの構成要素は、分割前のデータを示すラベルに対応するデータを構成する分割データを示す情報である。図４（Ａ）の例示では、「Ａ」のラベルを有するＦＢは、「Ａ１」、「Ａ２」、「Ａ３」の固定長ブロックに分割された分割データによって構成されるので、図４（Ｂ）に示すように、「Ａ」のラベルを有するＦＢの構成要素として「Ａ１，Ａ２，Ａ３」が登録されている。
構成要素の保存位置は、各分割データが記憶されているＲＡＭ１２上のメモリアドレスを示す情報である。
【００４０】
データ保存範囲は、各分割データが記憶されているメモリアドレスの範囲を示す情報である。走査完了位置は、データ保存範囲のうちメモリアドレス上で最後に位置するデータ保存範囲の末尾アドレスを示す。
【００４１】
図４（Ｃ）、図５（Ａ）〜（Ｃ）に例示するメモリ管理テーブルでは、上側に登録されているデータほど先に保持期間の終了を迎え、登録されたデータに対応するデータがＲＡＭ１２から削除される。
図５（Ａ）に示すように、本実施形態では、メモリ管理テーブル上において、「保持期間がＦＢである」データは、既にメモリ管理テーブル上に登録されている「保持期間がＤＬである」データよりも上側に登録される。ただし、図５（Ｂ）に示すように、本実施形態では、メモリ管理テーブルにおいて「保持期間がＤＬである」データの上側に二つの「保持期間がＦＢである」データが登録されると、その「保持期間がＤＬである」データの上側にさらに「保持期間がＦＢである」データを追加することはない。
図５（Ａ）、（Ｂ）に示すＤＬ、ＦＢの登録順ルールは本実施形態で用いる一例であり、他のルールを用いてもよい。
【００４２】
ＲＡＭ１２に記憶されたデータ（例えばＤＬ／ＦＢ等）であって、メモリ管理テーブルによって管理される各データは、それぞれの保持期間の終了を迎えるとＲＡＭ１２上から削除される。ＣＰＵ１１は、メモリ管理テーブルに登録された各データの保持期間に基づいて、ＲＡＭ１２に記憶されたデータのうち、保持期間の終了を迎えたデータを削除する。ＲＡＭ１２から削除されたデータに対応するメモリ管理テーブル上の登録データは、図５（Ｃ）に示すようにメモリ管理テーブル上から削除される。
【００４３】
図４（Ａ）〜（Ｃ）、図５（Ａ）〜（Ｃ）及びその説明では、ＤＬ及びＦＢのメモリ管理テーブルについて説明しているが、圧縮データについても同様に管理される。ＤＬ及びＦＢのメモリ管理テーブルと圧縮データのメモリ管理テーブルは個別に生成、管理される。圧縮データについては、図５（Ａ）、（Ｂ）及びその説明で示すような登録順の並び替えルールはない。
【００４４】
次に、本実施形態におけるＲＡＭ１２の断片化解消処理について説明する。
ＣＰＵ１１は、空き容量が断片化されたＲＡＭ１２のＤＬ、ＦＢ及び圧縮データを並び替えて、ＲＡＭ１２の空き領域を連続した一の記憶領域に統合する。
図６に、ＤＬ／ＦＢ記憶領域に対する断片化解消処理の概略を示す。
前述のように、ＲＡＭ１２に記憶されているＤＬ／ＦＢはＲＡＭ１２の記憶領域の末尾アドレス側寄りに記憶されるが、場合によっては空き領域（例えば図６に示す空き領域Ｅ）が各データ間に生じることがある。
【００４５】
断片化解消処理に先立ち、ＣＰＵ１１は記憶範囲算出処理を行う。記憶範囲算出処理は、メモリ管理テーブルによって管理される各データを連続した記憶領域に記憶させた場合に必要なＲＡＭ１２の記憶領域の範囲（記憶範囲）を算出する処理である。例えば、図６に示す空き領域Ｅを含むＤＬ／ＦＢ記憶領域Ｍ１について記憶範囲算出処理を行った場合、空き領域Ｅを含まず、ＲＡＭ１２の記憶領域の末尾アドレス側から連続した記憶範囲Ｍ２が算出される。
同様に、圧縮データ記憶領域について記憶範囲算出処理を行った場合、空き領域を含まず、ＲＡＭ１２の記憶領域の先頭アドレス側から連続した記憶範囲が算出される。
【００４６】
そして、ＣＰＵ１１は、位置並べ替え処理を行う。位置並べ替え処理は、メモリ管理テーブルによって管理される各データをデータの削除順序に基づいて並べ替える処理である。本実施形態では、ＣＰＵ１１は、それぞれのメモリ管理テーブルによって管理される各データをデータの削除順に従って連続した記憶領域に配置する。
例えば、図６に示すＤＬ／ＦＢ記憶領域Ｍ１に記憶されたＤＬ、ＦＢを並べ替えた場合、並べ替え後の記憶領域Ｍ３に示すように、各ＤＬ、ＦＢがそれぞれ連続した記憶領域に記憶される。図６に示す例の場合、ＤＬ及びＦＢのメモリ管理テーブル（以下、「ＤＬ／ＦＢメモリ管理テーブル」と記載）ではＦＢ１、ＤＬ１、ＤＬ２の順にデータの保持期間が終了する登録がなされている。よって、並べ替え後の記憶領域Ｍ３に記憶されたデータは、ＦＢ１、ＤＬ１、ＤＬ２の順に並ぶ。
【００４７】
ＣＰＵ１１は、位置並べ替え処理を行うにあたり、最初に削除されるデータを断片化解消処理完了後のＲＡＭ１２の空き領域と連続する記憶領域に配置する。例えば、図６に示す例の場合、ＦＢ１が最初に削除されるデータである。ＦＢ１は位置並べ替え処理完了後のＲＡＭ１２の空き領域Ｆと連続する記憶領域に配置される。
図６では、ＤＬ／ＦＢ記憶領域Ｍ１について例示しているが、圧縮データ記憶領域についても同様のルールに基づいて位置並べ替え処理が行われる。
【００４８】
図７及至図１２を用いて、断片化解消処理の詳細な流れを示す。図７及至図１２は、ＲＡＭ１２の記憶領域を時系列に沿って示したイメージ図である。図７及至図１３では、ＤＬ、ＦＢ及び圧縮データをマスキングして示し、空き領域を白抜きして示す。また、圧縮データは、ＤＬ、ＦＢに比して濃いマスキングによって示す。
図７（Ａ）に示すＲＡＭ１２に対して断片化解消処理が行われる場合、まず、ＣＰＵ１１は、図７（Ｂ）に示すように、記憶範囲算出処理を行う。ＣＰＵ１１は、各メモリ管理テーブルによって管理された各データの記憶容量を算出し、算出したデータの記憶容量をメモリ管理テーブル別に積算する。ここでは、ＤＬ／ＦＢメモリ管理テーブルに基づいて算出された積算結果をＤＬ／ＦＢ記憶範囲算出結果とし、圧縮データのメモリ管理テーブル（以下、「圧縮データメモリ管理テーブル」と記載）に基づいて算出された積算結果を圧縮データ記憶範囲算出結果とする。
図７（Ｂ）ではＤＬ／ＦＢ記憶領域及び圧縮データ記憶領域のそれぞれについて算出された記憶範囲を一つの図で説明しているが、必ずしも同時に算出する必要はない。例えば、ＤＬ／ＦＢ記憶領域の記憶範囲算出処理を完了した後に圧縮データ記憶領域の記憶範囲算出処理を行ってもよいし、その逆でもよい。ＤＬ／ＦＢ記憶領域及び圧縮データ記憶領域の記憶範囲算出処理を同時に行ってもよい。
【００４９】
次に、ＣＰＵ１１は、ＤＬ／ＦＢ位置並べ替え処理を行う。ＤＬ／ＦＢ位置並べ替え処理は、ＤＬ／ＦＢ記憶領域に記憶された各データに対する位置並べ替え処理である。
ＤＬ／ＦＢ位置並べ替え処理において、ＣＰＵ１１は、図７（Ｃ）に示すように、ＤＬ／ＦＢメモリ管理テーブルに登録されたデータのデータ保存範囲に含まれる記憶領域であって、所定のブロック長を有するＲＡＭ１２の記憶領域（メモリブロック）を処理対象としてセットする。
次に、ＣＰＵ１１は、セットされたメモリブロック内に位置並べ替えの必要がある分割データが含まれていないか判定する走査処理を行う。位置並べ替えの必要がある分割データとは、ＤＬ／ＦＢメモリ管理テーブルに登録されたＤＬ／ＦＢの削除順に基づいてＤＬ／ＦＢを各データの削除順に並べ替えた場合にその位置に記憶されていてはならない分割データである。
【００５０】
図８（Ａ）において「Ｎ１」で示すように、セットされたメモリブロック内に位置並べ替えの必要がある分割データが含まれていた場合、ＣＰＵ１１は、当該分割データを入替対象データとして扱う処理を行う。入替対象データに指定されたデータは、所定のワークバッファに記憶される。ワークバッファには、ＲＡＭ１２の空き領域や記憶部１４の記憶領域、その他専用の記憶装置を用いることができる。
図８（Ｂ）に示すように、ＣＰＵ１１は、入替対象データとされた分割データのデータ保存範囲をＤＬ／ＦＢメモリ管理テーブルから取得する。そして、図８（Ｃ）に示すように、ＣＰＵ１１は、取得されたデータ保存範囲に基づいて、ＤＬ／ＦＢメモリ管理テーブルに登録されたＤＬ／ＦＢの削除順に基づいてＤＬ／ＦＢを各データの削除順に並べ替えた場合に入替対象データを記憶することができるＲＡＭ１２の記憶領域を決定し、別のメモリブロックとしてセットする。
図９（Ａ）に示すように、ＣＰＵ１１は、走査処理を行って当該別のメモリブロック内に位置並べ替えの必要がある分割データ（図９（Ａ）に示す「Ｎ２」）を抽出し、ワークバッファに記憶された入替対象データと差し替える処理を行う。そして、ＣＰＵ１１は、抽出された分割データを新たな入替対象データとする。
【００５１】
ＣＰＵ１１は、新たな入替対象データに対して前述のメモリブロックのセット、走査処理、再配置、再配置によって生じる入替対象データの指定の処理を繰り返す。これらの処理を繰り返していくと、最終的に別のメモリブロックとしてセットされたメモリブロック内に位置並べ替えの必要がある分割データが存在しなくなる。
この繰り返し処理に伴い、ＣＰＵ１１は、走査完了位置を設定、更新して管理する。走査完了位置は、走査処理によって、どのメモリブロックまで「メモリブロック内に位置並べ替えの必要がある分割データが存在しない」ことが確認されたかを管理するためのデータである。位置並べ替えの必要がある分割データが存在しなくなったとき、走査完了位置はＤＬ／ＦＢ記憶範囲内の全領域について「メモリブロック内に位置並べ替えの必要がある分割データが存在しない」ことを示す状態（全記憶領域走査完了）となる。全記憶領域走査完了となったとき、ＣＰＵ１１は繰り返し処理を抜ける。
繰り返し処理を抜けた後、図９（Ｂ）に示すように、ＣＰＵ１１は、繰り返し処理後のＤＬ／ＦＢ記憶領域に記憶されているＤＬ、ＦＢのうち、最初に削除されるデータより前のアドレスに存在するＤＬ、ＦＢの分割データの残滓を削除してＲＡＭ１２の空き領域を確保する。以上でＤＬ／ＦＢ位置並べ替え処理が完了する。
【００５２】
ＤＬ／ＦＢ位置並べ替え処理完了後、ＣＰＵ１１は、圧縮データ位置並べ替え処理を行う。
図１０（Ａ）、（Ｂ）に示すように、ＣＰＵ１１は、圧縮データをＤＬ、ＦＢと連続した記憶領域にシフトさせ、ＲＡＭ１２の空き領域を記憶領域の先頭アドレス寄りに統合する。
次に、図１０（Ｃ）、図１０（Ｄ）に示すように、ＣＰＵ１１は、圧縮データメモリ管理テーブルによって管理される圧縮データの削除順序に基づいて、最後に削除される圧縮データをＲＡＭ１２の空き領域の先頭アドレスから連続する記憶領域に再配置する。
その後、図１１（Ａ）、（Ｂ）に示すように、再配置が完了した圧縮データ以外の圧縮データであって、再配置されたデータによって生じた空き領域より先頭アドレス寄りに位置する圧縮データを、再配置されたデータによって生じた空き領域を埋めるようにシフトさせる。これによって、再配置されたデータによって生じた空き領域は、他の空き領域と統合される。
【００５３】
次に、図１１（Ｃ）、（Ｄ）に示すように、ＣＰＵ１１は、圧縮データメモリ管理テーブルによって管理される圧縮データの削除順序に基づいて、最後から２番目に削除される圧縮データ（図１１（Ｃ）、（Ｄ）に示す「最後から２番目」）を、最後に削除される圧縮データが記憶された記憶領域と連続する記憶領域に再配置する。その後、ＣＰＵ１１は、前述の図１１（Ａ）、（Ｂ）及びその説明で示す処理と同様に、空き領域を統合する。以後、最初に削除される圧縮データの再配置が完了するまで、ＣＰＵ１１は、再配置と空き領域の統合を繰り返す。図１２に示すように、最初に削除される圧縮データの再配置が完了し、最初に削除される圧縮データが断片化解消処理完了後のＲＡＭ１２の空き領域と連続する記憶領域に配置されると、圧縮データ位置並べ替え処理が完了する。記憶範囲算出処理、ＤＬ／ＦＢ位置並べ替え処理及び圧縮データ位置並べ替え処理の完了を以って、ＣＰＵ１１は断片化解消処理を終了する。
【００５４】
図１３に、断片化解消処理後のＲＡＭ１２におけるデータ削除の一例を示す。
図１３に示すように、断片化解消処理後のＲＡＭ１２から、最初に削除されるＤＬ又はＦＢや、最初に削除される圧縮データが削除されると、圧縮データ記憶領域とＤＬ／ＦＢ記憶領域との間に介在する空き領域と連続する記憶領域が開放されることにより、断片化されない一の空き領域が形成される。
さらに、その後削除されるＤＬ又はＦＢは、その直前に削除されたＤＬ又はＦＢによって生じた空き領域と連続する記憶領域に位置する。同様に、削除される圧縮データは、その直前に削除された圧縮データによって生じた空き領域と連続する記憶領域に位置する。このように、位置並べ替え処理を受けた各データが削除されることによって生じる空き領域は断片化を生じさせず、連続した空き領域を形成する。
【００５５】
以下、図１４及至図２４を用いて、画像形成装置１の処理の流れを示す。
図１４に、データの受信から印刷を行うに至る処理の概略を示す。
画像形成装置１は、データを受信すると（ステップＳ１）、解析処理（ステップＳ２）、ラスタライズ処理（ステップＳ３）、圧縮処理（ステップＳ４）を経て印刷を行う（ステップＳ５）。
ステップＳ５の処理後、ＣＰＵ１１は、全てのページの印刷を完了したか否かの判定を行う（ステップＳ６）。全てのページの印刷を完了していない場合（ステップＳ６：ＮＯ）、画像形成装置１は、ステップＳ２〜Ｓ５の処理を再度行う。全てのページの印刷を完了した場合（ステップＳ６：ＹＥＳ）、画像形成装置１は、処理を終了する。
【００５６】
図１５に、図１４のステップＳ２に示す解析処理の流れを示す。
解析部２１は、ＰＤＬを解析してＤＬを生成する（ステップＳ１１）。また、解析部２１は、全てのＰＤＬに対して解析処理を完了したか否かを判定する（ステップＳ１２）。全てのＰＤＬに対して解析処理を完了していない場合（ステップＳ１２：ＮＯ）、ステップＳ１１の処理に戻る。全てのＰＤＬに対して解析処理を完了した場合（ステップＳ１２：ＹＥＳ）、処理を抜ける。
【００５７】
図１６に、図１４のステップＳ３に示すラスタライズ処理の流れを示す。
ラスタライズ部２２は、ＤＬに対してラスタライズ処理を施してＦＢを生成する（ステップＳ２１）。また、ラスタライズ部２２は、ＲＡＭ開放処理を行う（ステップＳ２２）。
ステップＳ２１、Ｓ２２の処理後、ラスタライズ部２２は、全てのＤＬに対してラスタライズ処理を完了したか否かを判定する（ステップＳ２３）。全てのＤＬに対してラスタライズ処理を完了していない場合（ステップＳ２３：ＮＯ）、ステップＳ２１の処理に戻る。全てのＤＬに対してラスタライズ処理を完了した場合（ステップＳ２３：ＹＥＳ）、処理を抜ける。
【００５８】
図１７に、図１４のステップＳ４に示す圧縮処理の流れを示す。
ＡＳＩＣ１７は、ＦＢを圧縮して圧縮データを生成する（ステップＳ３１）。また、ＣＰＵ１１は、ステップＳ３１で生成したＦＢをＲＡＭ１２に記憶させるに伴い、ＲＡＭ１２の記憶容量の不足（メモリ不足）が発生したか否かを判定する（ステップＳ３２）。メモリ不足を生じた場合（ステップＳ３２：ＹＥＳ）、ＣＰＵ１１は断片化解消処理を行う（ステップＳ３３）。
ステップＳ３３の処理後又はステップＳ３２においてメモリ不足を生じていない場合（ステップＳ３２：ＮＯ）、ＣＰＵ１１は、ＲＡＭ開放処理を行う（ステップＳ３４）。
ステップＳ３３又はステップＳ３４の処理後、ＣＰＵ１１は、全てのＦＢに対して圧縮処理を完了したか否かを判定する（ステップＳ３５）。全てのＦＢに対して圧縮処理を完了していない場合（ステップＳ３５：ＮＯ）、ステップＳ３１の処理に戻る。全てのＦＢに対して圧縮処理を完了した場合（ステップＳ３５：ＹＥＳ）、処理を抜ける。
【００５９】
図１５及至図１７のフロー及びその説明では、全てのＰＤＬ、ＤＬ、ＦＢに対する処理を完了した場合に各処理を抜ける記載としているが、解析処理、ラスタライズ処理及び圧縮処理は並行して行うことができる。即ち、ラスタライズ部２２は、生成されたＤＬから順次ＦＢを生成することができる。また、ＡＳＩＣ１７は、生成されたＦＢから順次圧縮データを生成することができる。そして、画像形成部１６は、１ページ分の圧縮データが揃い次第、そのページの印刷を行うことができる。
【００６０】
図１８に、図１６のステップＳ２２及び図１７のステップＳ３４に示すＲＡＭ開放処理の流れを示す。
ＣＰＵ１１は、メモリ管理テーブル上で保持期間の終了したデータがあるか否か判定し（ステップＳ４１）、メモリ管理テーブル上で保持期間の終了したデータがある場合（ステップＳ４１：ＹＥＳ）、保持期間の終了したデータを削除する（ステップＳ４２）。ステップＳ４２の処理後又はステップＳ４１においてメモリ管理テーブル上で保持期間の終了したデータがない場合（ステップＳ４１：ＮＯ）、処理を抜ける。
【００６１】
図１６のステップＳ２２に示すＲＡＭ開放処理と図１７のステップＳ３４に示すＲＡＭ開放処理とでは、データ削除の対象となる記憶領域が異なる。図１６のステップＳ２２に示すＲＡＭ開放処理ではＤＬ／ＦＢ記憶領域のデータ削除が行われ、図１７のステップＳ３４に示すＲＡＭ開放処理では圧縮データ記憶領域のデータ削除が行われる。
【００６２】
図１９に、図１７のステップＳ３３に示す断片化解消処理の流れを示す。
ＣＰＵ１１は、ＤＬ／ＦＢ記憶領域断片化解消処理（ステップＳ５１）、圧縮データ記憶領域断片化解消処理（ステップＳ５２）を順次行う。
【００６３】
図２０に、図１９のステップＳ５１に示すＤＬ／ＦＢ記憶領域断片化解消処理の流れを示す。
ＣＰＵ１１は、記憶範囲算出処理（ステップＳ６１）、ＤＬ／ＦＢ位置並べ替え処理（ステップＳ６２）を順次行う。
図２１に、図１９のステップＳ５２に示す圧縮データ記憶領域断片化解消処理の流れを示す。
ＣＰＵ１１は、記憶範囲算出処理（ステップＳ７１）、圧縮データ位置並べ替え処理（ステップＳ７２）を順次行う。
【００６４】
図２２に、図２０のステップＳ６１及び図２１のステップＳ７１に示す記憶範囲算出処理の流れを示す。
ＣＰＵ１１は、メモリ管理テーブルに登録されたデータの記憶容量を算出する（ステップＳ８１）。ＣＰＵ１１は、メモリ管理テーブルに登録された全てのデータの記憶容量を算出するまでステップＳ８１の処理を繰り返す（ステップＳ８２：ＮＯ）。メモリ管理テーブルに登録された全てのデータの記憶容量を算出すると（ステップＳ８２：ＹＥＳ）、算出された記憶容量を積算して記憶範囲を算出する（ステップＳ８３）。
図２０のステップＳ６１に示す記憶範囲算出処理では、ＤＬ／ＦＢメモリ管理テーブルに基づいて記憶範囲算出処理が行われる。図２１のステップＳ７１に示す記憶範囲算出処理では、圧縮データメモリ管理テーブルに基づいて記憶範囲算出処理が行われる。
【００６５】
図２３に、図２０のステップＳ６２に示すＤＬ／ＦＢ位置並べ替え処理の流れを示す。
ＣＰＵ１１は、ＤＬ／ＦＢメモリ管理テーブルに登録されたデータのデータ保存範囲に含まれる記憶領域であって、所定のブロック長を有するメモリブロックを処理対象としてセットする。（ステップＳ９１）。次に、ＣＰＵ１１は、走査処理を行い、セットされたメモリブロック内に位置並べ替えの必要がある分割データが含まれているか判定する（ステップＳ９２）。セットされたメモリブロック内に位置並べ替えの必要がある分割データが含まれていない場合（ステップＳ９２：ＮＯ）、ＣＰＵ１１は、ステップＳ９２の判定によって位置並べ替えの必要がある分割データが含まれていないことが判明したメモリブロックに応じて走査完了位置を更新する（ステップＳ９３）。
【００６６】
セットされたメモリブロック内に位置並べ替えの必要がある分割データが含まれていた場合（ステップＳ９２：ＹＥＳ）、ＣＰＵ１１は、ワークバッファに既に入替対象データがあるか否か判定する（ステップＳ９４）。ワークバッファに入替対象データがない場合（ステップＳ９４：ＮＯ）、ステップＳ９２に位置並べ替えの必要があると判定された分割データを入替対象データとして指定する（ステップＳ９５）。そして、ＣＰＵ１１は、入替対象データとされた分割データのデータ保存範囲に基づいて、ＤＬ／ＦＢを各データの削除順に並べ替えた場合に入替対象データを記憶することができるＲＡＭ１２の記憶領域を、別のメモリブロックとしてセットする（ステップＳ９６）。
【００６７】
ステップＳ９６の処理後、ＣＰＵ１１は、セットされたメモリブロックについて、セット後に走査処理を完了したか否かを判定する（ステップＳ９７）。走査処理を完了していない場合（ステップＳ９７：ＮＯ）、ステップＳ９２の処理に戻る。
【００６８】
ステップＳ９４の判定において、ワークバッファに既に入替対象データがある場合（ステップＳ９４：ＹＥＳ）、ＣＰＵ１１は、入替対象データを、ステップＳ９２において位置並べ替えの必要がある分割データとして判定された分割データと差し替える（ステップＳ９８）。その後、ＣＰＵ１１は、ステップＳ９６の処理を行う。
【００６９】
ＣＰＵ１１は、ステップＳ９３の処理後も、ステップＳ９７の判定を行う。ステップＳ９７の判定において、セットされたメモリブロックの走査処理を完了していた場合（ステップＳ９７：ＹＥＳ）、ＣＰＵ１１は、走査完了位置が全記憶領域走査完了を示すか否か判定する（ステップＳ９９）。走査完了位置が全記憶領域走査完了を示さない場合（ステップＳ９９：ＮＯ）、ＣＰＵ１１は走査完了位置に基づいて、走査処理を完了していない別のメモリブロックをセットし（ステップＳ１００）、ステップＳ９２の処理を行う。走査完了位置が全記憶領域走査完了を示す場合（ステップＳ９９：ＹＥＳ）、ＣＰＵ１１は、繰り返し処理後のＤＬ／ＦＢ記憶領域に記憶されているＤＬ、ＦＢのうち、最初に削除されるデータより前のアドレスに存在するＤＬ、ＦＢの分割データを削除し（ステップＳ１０１）、処理を終了する。
【００７０】
図２４に、図２１のステップＳ７２に示す圧縮データ位置並べ替え処理の流れを示す。
ＣＰＵ１１は、再配置の完了していない圧縮データをＤＬ、ＦＢと連続した記憶領域にシフトさせ（ステップＳ１１１）、ＲＡＭ１２の空き領域を記憶領域の先頭アドレス寄りに統合する。
次に、ＣＰＵ１１は、圧縮データメモリ管理テーブルによって管理される圧縮データの削除順序に基づいて、再配置を完了していない圧縮データのうち最後に削除される圧縮データをＲＡＭ１２の空き領域のうち最も先頭アドレス寄りの記憶領域に再配置する（ステップＳ１１２）。
その後、ＣＰＵ１１は、全ての圧縮データの再配置を完了したか否かを判定する（ステップＳ１１３）。全ての圧縮データの再配置を完了していない場合（ステップＳ１１３：ＮＯ）、ステップＳ１１１の処理に戻る。全ての圧縮データの再配置を完了した場合（ステップＳ１１３：ＹＥＳ）、処理を終了する。
【００７１】
以上、本実施形態によれば、ＣＰＵ１１が、メモリ管理テーブルによってＲＡＭ１２に記憶されたＤＬ、ＦＢ、圧縮データの削除順序を管理する。そして、ＣＰＵ１１は、ＲＡＭ１２の空き領域の断片化解消処理を行うときにＲＡＭ１２に記憶されたＤＬ、ＦＢ、圧縮データを各データの削除順序に基づいて並べ替える。
例えば、メモリ管理テーブルによって管理される各データをデータの削除順に従って連続した記憶領域に配置するよう並べ替えることで、データの削除に伴って伴って生じる空き領域は自動的に統合された空き領域となる。また、最初に削除されるＤＬ又はＦＢ及び圧縮データをＲＡＭ１２の空き領域と連続する記憶領域に配置することで、ＲＡＭ１２における既存の空き領域と、最初に削除されるデータの削除によって生じる空き領域とを統合して連続する記憶領域とすることができる。このように、位置並べ替え処理後に各データの削除によって生じるＲＡＭ１２の空き領域の断片化を抑止し、ＲＡＭ１２の空き領域を有効活用することができる。
【００７２】
さらに、ＣＰＵ１１は、ＤＬ、ＦＢ、圧縮データを並べ替えるとき、最初に削除されるＤＬ又はＦＢ及び圧縮データをＲＡＭ１２の空き領域と連続する記憶領域に配置する。これによって、ＲＡＭ１２における既存の空き領域と、最初に削除されるＤＬ、ＦＢ、圧縮データの削除によって生じる空き領域とを統合して連続する記憶領域とすることができる。よって、断片化されない連続する空き領域を形成することができ、位置並べ替え処理後に各データの削除によって生じるＲＡＭ１２の空き領域の断片化を抑止し、ＲＡＭ１２の空き領域を有効活用することができる。
【００７３】
さらに、ＣＰＵ１１は、メモリ管理テーブルによって管理される各データをデータの削除順に従って連続した記憶領域に配置する。
これによって、ＤＬ及びＦＢは、削除順に連続した記憶領域に記憶される。このため、ＤＬ及びＦＢが削除されるに伴って生じる空き領域は自動的に統合された空き領域となる。また、圧縮データは、削除順に連続した記憶領域に記憶され、圧縮データが削除されるに伴って生じる空き領域は自動的に統合された空き領域となる。このように、位置並べ替え処理後に各データの削除によって生じるＲＡＭ１２の空き領域の断片化を抑止し、ＲＡＭ１２の空き領域を有効活用することができる。
【００７４】
さらに、ＣＰＵ１１は、ＤＬ／ＦＢメモリ管理テーブルと、圧縮データメモリ管理テーブルとを個別に管理し、位置並べ替え処理において、それぞれのメモリ管理テーブルに基づいてＤＬ／ＦＢ位置並べ替え処理と圧縮データ位置並べ替え処理とを行う。
これによって、ブロック単位での管理の有無やデータの削除タイミング等の取り扱いが異なるデータをそれぞれ削除順に並び替えることができ、それぞれのデータの削除によって生じる空き領域を容易に管理することができる。
【００７５】
さらに、ＤＬ、ＦＢは固定長のブロック単位に分割される。
固定長の分割データを用いることで、位置並べ替え処理において入替対象データを固定長の分割データ単位とすることができる。このため、データの再配置で差し替えられるデータの容量を固定長の分割データ単位で管理することができる。つまり、入替対象データのデータサイズの変動がないので、管理が容易となる。さらに、ワークバッファの記憶容量を固定長の分割データ単位とすることができ、管理が容易である上、差し替えられるデータのデータサイズの変動を考慮した余剰バッファを必要としないので、位置並べ替え処理に要するワークバッファを最小限にすることができる。
【００７６】
なお、本発明の実施の形態は、今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【００７７】
以下、本発明の実施形態の変形例を例示する。
例えば、ＤＬ又はＦＢあるいはその両方を可変長ブロックで分割してもよい。
この場合、固定長ブロックに比してブロック長を柔軟に変更できることにより、固定長ブロックに比して少ない数の分割データでＤＬやＦＢを扱うことができる。分割データの数が少なくなることによって、メモリ管理テーブル上でラベルに対する構成要素の管理を行う処理（マッピング）の処理量が低減される。これによって、メモリ管理テーブルによる各データの管理をより高速に行うことができる。
固定長のブロック単位で管理するデータと、可変長のブロック単位で管理するデータの双方を取り扱ってもよい。
【００７８】
位置並べ替え処理の対象とするデータを限定してもよい。例えば、ＤＬ、ＦＢのうち最初に削除されるデータを、統合された空き領域と連続する記憶領域に配置するための並べ替えを行うのみとしてもよい。
この場合、全てのデータを並べ替える場合に比して、並べ替え処理の処理量が低減するので、並べ替え処理を高速に完了させることができる。また、最初に削除されるＤＬ又はＦＢが削除された時点では空き領域が連続するので、ＲＡＭ１２の空き領域の断片化を抑止することができ、ＲＡＭ１２の空き領域を有効活用することができる。
同様に、圧縮データのうち最初に削除されるデータを、統合された空き領域と連続する記憶領域に配置するための並べ替えを行うのみとしてもよい。また、ＤＬ、ＦＢのうち最初に削除されるデータ及び最初に削除されるデータを、統合された空き領域と連続する記憶領域に配置するための並べ替えを行うのみとしてもよい。
また、並べ替えを行うデータの限定対象は、最初に削除されるデータに限らない。例えば、最初及び最初から２番目までとすることもできるし、３番目以降についても並べ替えを行うデータの限定対象とするか否かをを任意に設定することができる。
【００７９】
ＲＡＭ１２に新たなデータが記憶されるたびに、各データの位置並べ替え処理を行ってもよい。
この場合、断片化解消処理に伴う再配置によって、削除されるデータは常に空き領域と連続する記憶領域に記憶されるので、ＲＡＭ１２の空き領域は常に統合された空き領域となる。これによって、ＲＡＭ１２の空き領域の断片化を生じさせずにＲＡＭ１２の空き領域を有効活用することができる。
【００８０】
位置並べ替え処理において、最初に削除されるデータを既存のＲＡＭ１２の空き領域と連続させなくともよい。
この場合でも、データは削除順に連続した記憶領域に記憶されるので、データが削除されるに伴って生じる空き領域は自動的に統合された空き領域となる。これによって、位置並べ替え処理後に生じるＲＡＭ１２の空き領域の断片化を生じさせずにＲＡＭ１２の空き領域を有効活用することができる。
【００８１】
上述した本発明の実施形態及びその変形例を組み合わせて用いてもよい。
ＤＬ／ＦＢ記憶領域と圧縮データ記憶領域の位置は入れ替えることができる。また、ＤＬ、ＦＢ、圧縮データ等の各データや、メモリ管理テーブルで取り扱うパラメータ等はあくまで一例であり、他のデータの管理に本発明を適用することもできる。
【００８２】
以上の説明では、本発明に係るプログラムのコンピュータ読み取り可能な媒体としてＲＯＭを使用した例を開示したが、この例に限定されない。その他のコンピュータ読み取り可能な媒体として、フラッシュメモリ等の不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬型記録媒体を適用することが可能である。
また、本発明に係るプログラムのデータを通信回線を介して提供する媒体として、キャリアウエーブ(搬送波)も本発明に適用される。
【符号の説明】
【００８３】
１     画像形成装置
２     回線
３     外部入力装置
１１   ＣＰＵ
１２   ＲＡＭ
１３   ＲＯＭ
１４   記憶部
１５   インタフェース
１６   画像形成部
１７   ＡＳＩＣ
１８   バス
【図１】
0005454342.tif 000002
【図２】
0005454342.tif 000003
【図３】
0005454342.tif 000004
【図４】
0005454342.tif 000005
【図５】
0005454342.tif 000006
【図６】
0005454342.tif 000007
【図７】
0005454342.tif 000008
【図８】
0005454342.tif 000009
【図９】
0005454342.tif 000010
【図１０】
0005454342.tif 000011
【図１１】
0005454342.tif 000012
【図１２】
0005454342.tif 000013
【図１３】
0005454342.tif 000014
【図１４】
0005454342.tif 000015
【図１５】
0005454342.tif 000016
【図１６】
0005454342.tif 000017
【図１７】
0005454342.tif 000018
【図１８】
0005454342.tif 000019
【図１９】
0005454342.tif 000020
【図２０】
0005454342.tif 000021
【図２１】
0005454342.tif 000022
【図２２】
0005454342.tif 000023
【図２３】
0005454342.tif 000024
【図２４】
0005454342.tif 000025
【図２５】
0005454342.tif 000026