(57)【特許請求の範囲】
【請求項１】
デマンドページング技法を適用したシステムでページ置換実行時間を短縮させる方法で、
（ａ）ページフォールトの発生を知らせる信号を受信するステップと、
（ｂ）前記ページフォールトが生じたページを不揮発性メモリから読み取るステップと、
（ｃ）前記フォールトが生じたページを格納する空間をメモリから検索して確保するステップとを含み、
前記（ｃ）ステップは予め計算された限界時間以内に行われ、前記システムのメモリにロードされるデータの一部は前記不揮発性メモリに格納されているデマンドページング技法を適用する、デマンドページングにおけるページ置換方法。
【請求項２】
前記限界時間は、前記（ｂ）ステップを行うのに必要とする時間以下である請求項１に記載のデマンドページングにおけるページ置換方法。
【請求項３】
前記（ｃ）ステップは、前記（ｂ）ステップを行うために前記システムが待機している時間に行われる請求項１に記載のデマンドページングにおけるページ置換方法。
【請求項４】
前記（ｂ）ステップは、
フォールトが生じたページの情報を前記不揮発性メモリに送信するステップと、
前記ページのデータを前記不揮発性メモリから受信するステップとを含み、
前記システムが待機している時間は、前記送信するステップと前記受信するステップとの間に存在する時間である請求項３に記載のデマンドページングにおけるページ置換方法。
【請求項５】
前記（ｃ）ステップは、
置換対象になる複数のページを管理するポインタを移動させるステップと、
前記移動したポインタが指示するページを、前記フォールトが生じたページを格納する空間として確保するステップとを含み、
前記移動させるステップは、前記限界時間以下で行われる請求項１に記載のデマンドページングにおけるページ置換方法。
【請求項６】
前記限界時間は、前記（ｂ）ステップを行うのに必要とする時間以下である請求項５に記載のデマンドページングにおけるページ置換方法。
【請求項７】
前記システムは、前記メモリを管理するにあたって、メモリ内のページを２つのグループに分けて管理し、第１グループは現在参照されたページのリストで、第２グループは今後置換されるページのリストであり、
前記（ｃ）ステップは、前記第２グループで格納する空間を確保するステップを含み、
前記第１グループと前記第２グループとの間で置換または整理されるページのグループ移動は前記限界時間以下で行われる請求項１に記載のデマンドページングにおけるページ置換方法。
【請求項８】
前記限界時間は、前記（ｂ）ステップを行うのに必要とする時間以下である請求項７に記載のデマンドページングにおけるページ置換方法。
【請求項９】
電源の供給なしで格納されたデータ保持をする不揮発性格納装置と、
前記不揮発性格納装置からデータを受信して格納し、データ格納時に電源の供給を必要とし、デマンドページングを介してデータを管理するメモリと、
前記メモリでページフォールトが発生することを知らせる信号を送信するメモリ管理部と、
前記ページフォールトが生じたページの情報を抽出して、前記ページを格納する前記メモリの空間を検索して確保するページフォールトハンドラと、
前記不揮発性格納装置にフォールトが発生したページの情報を送信し、前記不揮発性格納装置からデータを受信するデバイスドライバとを含み、
前記ページフォールトハンドラによる処理は予め計算された限界時間以内に行われる、デマンドページングにおけるページ置換装置。
【請求項１０】
前記限界時間は、前記デバイスドライバが前記不揮発性格納装置にフォールトが発生したページの情報を送信した時点から、前記不揮発性格納装置からデータを受信する時点まで必要とする時間以下である請求項９に記載のデマンドページングにおけるページ置換装置。
【請求項１１】
前記ページフォールトハンドラは、前記メモリの空間を検索して確保する作業を前記デバイスドライバが不揮発性格納装置からデータを受信するために待機している時間に行う請求項９に記載のデマンドページングにおけるページ置換装置。
【請求項１２】
前記ページフォールトハンドラは、
置換対象になる複数のページを管理するポインタを移動させ、
前記移動したポインタが指示するページを、前記フォールトが生じたページを格納する空間として確保し、
前記移動させる作業は前記限界時間以内に行う請求項９に記載のデマンドページングにおけるページ置換装置。
【請求項１３】
前記限界時間は、前記デバイスドライバが前記不揮発性格納装置にフォールトが発生したページの情報を送信した時点から、前記不揮発性格納装置からデータを受信する時点まで必要とする時間以下である請求項１２に記載のデマンドページングにおけるページ置換装置。
【請求項１４】
前記ページフォールトハンドラは、前記メモリを管理するにあたって、メモリ内のページを２つのグループに分けて管理し、第１グループは現在参照されたページのリストであり、第２グループは今後置換されるページのリストであり、
前記メモリの空間を検索して確保する作業は、前記第２グループで格納する空間を確保する作業を含み、
前記第１グループと前記第２グループとの間で置換または整理されるページのグループ移動は前記限界時間以下で行われる請求項９に記載のデマンドページングにおけるページ置換装置。
【請求項１５】
前記限界時間は、前記デバイスドライバが前記不揮発性格納装置にフォールトが発生したページの情報を送信した時点から、前記不揮発性格納装置からデータを受信する時点まで必要とする時間以下である請求項１４に記載のデマンドページングにおけるページ置換装置。
【請求項１６】
前記不揮発性格納装置は、フラッシュメモリと前記フラッシュメモリのデータを前記不揮発性格納装置外との間で伝送するバッファまたはレジスタを含む請求項９に記載のデマンドページングにおけるページ置換装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デマンドページング技法に関し、より詳しくは、デマンドページング技法を適用したシステムでページ置換実行時間を短縮させる方法および装置に関するものである。
【背景技術】
【０００２】
デマンドページング（Ｄｅｍａｎｄ  Ｐａｇｉｎｇ）技法とは、仮想メモリシステムを用いるハードディスクのような補助格納装置に仮想メモリを割り当てて、ユーザの要求により物理メモリをマッピングして制限されたメインメモリをより効率的に用いることができるようにする技法である。フラッシュメモリは、ハードディスクのように不揮発性と速いアクセス速度を有するが、電力を少なく消費するため埋め込みシステム（ｅｍｂｅｄｄｅｄ  ｓｙｓｔｅｍ）や移動デバイス（ｍｏｂｉｌｅ  ｄｅｖｉｃｅ）などの応用で多く用いられている。
【０００３】
デマンドページングを行う順序、ページフォールトが発生した時、先ずフォールトハンドラはフォールトが発生したページをする物理メモリ空間を確保する。使用可能な物理メモリ空間がない場合、既に割り当てられたページと置換させて確保する。フォールトハンドラは物理メモリ空間を確保してから、フォールトが発生したページが格納された不揮発性格納装置のアドレスを検出した後、不揮発性装置から該当ページを読み取ってメモリマッピングテーブルを更新する。
【０００４】
図１は、デマンドページング処理過程を時間の流れにソフトウェア処理過程とデバイスＩ／Ｏとの関係を示す図面である。
【０００５】
デバイスでデータを読み取る場合はページフォールトが発生した場合である。ページフォールトハンドラ１０は、先ずデバイスからデータを読み取って格納するメモリの空間を確保する。そして、ページフォールトが生じたページのアドレスを検出して、該当ページのデータを読み取るようにデバイスにＲＥＡＤ＿ＣＭＤという命令語を生成する。この命令語がデバイスに伝えられれば、デバイスは一定時間のビジー時間を経た後、データを伝送するが、ここでビジー時間は該当ページに格納されたデータを読み取るための先行作業を行う時間である。例えば、フラッシュメモリからデータを読み取る場合、該当ページが格納された領域にコラム信号とロー（ｒｏｗ）信号を送ってデータを読み取ることができる。このような過程を行うために一定時間が所要される。この時間以後にフラッシュメモリから該当ページのデータを伝送することができる。デバイスからデータを伝送すれば、ページフォールトハンドラはマッピングテーブルを更新して、受信したデータを格納する。
【０００６】
図１に示したページ置換作業は、デバイスからデータを読み取ってページフォールト結果を整理するなどの様々な作業をしなければならないため、ページ置換を減らすことがシステムの性能に多くの影響を及ぼすことができる。
【０００７】
ページ置換アルゴリズムのうち最も最適化されたアルゴリズムとしてＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）アルゴリズム。これは最近用いた回数が最も少ないページを置換対象とする方式である。ところで、ＬＲＵページ置換政策をページングに適用するためにはハードウェアの支援が必要であるが、大部分のシステムでは真の意味のＬＲＵページ置換政策のためのハードウェア支援がない。したがって、通常的にクロックアルゴリズム、Ｍａｃｈ２．５アルゴリズムなどＬＲＵに類似したアルゴリズムを適用している。
【０００８】
ところで、従来のページング技術は、ハードディスクなどの不揮発性格納装置に基づいてページングを処理して、フラッシュメモリのような不揮発性格納装置の特性を考慮していない。ハードディスクからデータを読み取る方式とフラッシュメモリからデータを読み取る方式には差があるが、ページング技術にこのような差を考慮していない。
【０００９】
ハードディスクの場合、物理メモリアドレスと不揮発性格納装置のアドレスを介して、不揮発性格納装置から物理メモリにデータを読み取ることができるが、フラッシュメモリのようにデバイス内にバッファ（またはレジスタ）がある不揮発性格納装置の場合には物理メモリ（ＲＡＭ）にデータを読み取る前に不揮発性格納装置内のバッファ（またはレジスタ）までデータをロードした後、そのバッファまたはレジスタから物理メモリにデータをロードする。フラッシュメモリに不揮発性格納装置のアドレスと共に読み取り命令を発生させれば、読み取り命令語が生じた後バッファ（またはレジスタ）にデータがロードされるが、ロードされる間デバイスはビジー状態となる。この時間はフラッシュメモリによって異なるが、通常２３μｓ〜３５μｓの時間が所要される。
【００１０】
上記の場合以外にも、ページング技術を適用時に不要な反復的な演算が続く場合がある。したがって、ページングでページを置換時に必要とする実行時間を縮小させる方法と装置が必要である。特許文献１は中央処理装置でフラッシュメモリのデータを検査し、ページを要請する段階と、要請された該当ページをフラッシュメモリからＲＡＭに保存する段階と、該当ページ内に保存された関連ページ番号を検査して関連ページをＲＡＭに保存する段階を含むゲーム用携帯端末機のデマンドページング方法を開示しているが、ハードディスクとフラッシュメモリの読み込み方法の差異によるページング技術の差異を考慮しておらず、要求ページングでページを交替時に所要される遂行時間を減縮させる方案は提案されていない。
【特許文献１】韓国特許公開第２００５−００７５５３３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、前記問題点を改善するために案出されたもので、フラッシュメモリのような不揮発性格納装置の特性を考慮して、ページング技法を適用することに目的がある。
【００１２】
また、本発明は、不揮発性格納装置からデータを読み取る時間の間に他の作業を行うようにしてシステムの性能を向上させることに目的がある。
【００１３】
本発明の目的は、以上で言及した目的に制限されず、言及していないまた他の目的は下記記載によって当業者が明確に理解できるものである。
【課題を解決するための手段】
【００１４】
本発明の一態様に係るページング技法を適用したシステムでページ置換実行時間を短縮させる方法は、（ａ）ページフォールトの発生を知らせる信号を受信するステップと、（ｂ）前記ページフォールトが生じたページを不揮発性メモリから読み取るステップと、（ｃ）前記フォールトが生じたページを格納する空間をメモリから検索して確保するステップとを含み、前記（ｃ）ステップは予め計算された限界時間以内に行われ、前記システムのメモリにロードされるデータの一部は前記不揮発性メモリに格納されているページング技法を適用する。
【００１５】
本発明の他の態様に係るページング技法を適用したシステムでページ置換実行時間を短縮させる装置は、電源の供給なしで格納されたデータをする不揮発性格納装置と、前記不揮発性格納装置からデータを受信して格納し、データ格納時に電源の供給を必要とし、ページングを介してデータを管理するメモリと、前記メモリでページフォールトが発生することを知らせる信号を送信するメモリ管理部と、前記ページフォールトが生じたページの情報を抽出して、前記ページを格納する前記メモリの空間を検索して確保するページフォールトハンドラと、前記不揮発性格納装置にフォールトが発生したページの情報を送信し、前記不揮発性格納装置からデータを受信するデバイスドライバとを含み、前記ページフォールトハンドラは予め計算された限界時間以内に行われる。
【発明の効果】
【００１６】
本発明を具現することによって、フラッシュメモリのような不揮発性格納装置の特性を考慮してページング技法を適用することができる。
【００１７】
本発明を具現することによって、不揮発性格納装置からデータを読み取る時間の間に他の作業を行うことができる。
【発明を実施するための最良の形態】
【００１８】
その他、実施形態の具体的な事項は、詳細な説明および図面に含まれている。
【００１９】
本発明の利点および特徴、そしてそれらを達成する方法は、添付する図面と共に詳細に後述する実施形態を参照すれば明確になる。しかし、本発明は以下にて開示する実施形態に限定されず、互いに異なる多様な形態によって実施され、単に本実施形態は本発明の開示が完全なものとなるようにし、本発明が属する技術分野で通常の知識を有する者に発明の範疇を完全に知らせるために提供されるものであって、本発明は請求項の範疇によってのみ定義されるものである。明細書の全体に亘り、同一参照符号は同一構成要素を示す。
【００２０】
以下、本発明の実施形態によって、デマンドページング技法を適用したシステムでページ置換実行時間を短縮させる方法および装置を説明するためのブロック図または処理フローチャートに対する図面を参考にして本発明について説明する。この時、処理フローチャートの各ブロックとフローチャートの組合せは、コンピュータプログラムインストラクションによって行われることが理解できる。これらコンピュータプログラムインストラクションは、汎用コンピュータ、特殊用コンピュータ、またはその他のプログラム可能なデータプロセシング装備のプロセッサに搭載することができるため、コンピュータまたはその他のプログラム可能なデータプロセシング装備のプロセッサを介して行われるそのインストラクションがフローチャートブロックで説明する機能を行う手段を生成するようになる。これらコンピュータプログラムインストラクションは、特定方式で機能を具現するために、コンピュータまたはその他のプログラム可能なデータプロセシング装備が備えられるコンピュータによって利用可能または読み取り可能なメモリに格納されることも可能であるため、そのコンピュータによって利用可能または読み取り可能なメモリに格納されたインストラクションは、フローチャートブロックで説明する機能を行うインストラクション手段を含む製造品目の生産に用いることも可能である。コンピュータプログラムインストラクションは、コンピュータまたはその他のプログラム可能なデータプロセシング装備上に搭載することも可能であるため、コンピュータまたはその他のプログラム可能なデータプロセシング装備上で一連の動作ステップが行われ、コンピュータで実行されるプロセスを生成して、コンピュータまたはその他のプログラム可能なデータプロセシング装備の機能を行うインストラクションはフローチャートブロックで説明する各ステップの機能を実行することも可能である。
【００２１】
また、各ブロックは、特定された論理的機能を実行するための１つ以上の実行可能なインストラクションを含むモジュール、セグメント、またはコードの一部を示すことができる。また、複数の代替実行例ではブロックで言及された機能が順序から外れて行われることも可能であることに注目しなければならない。例えば、連続して図示されている２つのブロックは、実質的に同時に行われることも可能で、またはそのブロックが時には該当機能により逆順に行われることも可能である。
【００２２】
フラッシュメモリのような不揮発性格納装置の場合には格納装置内からバッファあるいはレジスタまでデータをロードする過程と、そのバッファあるいはレジスタからロードされたデータを物理メモリ（ＲＡＭ）に伝送する過程とが区分されるため、セルからバッファ（またはレジスタ）までデータをロードする時間の間に置換ページ選定作業などの作業をすることによってデマンドページング処理時間を短縮することが可能である。勿論、置換ページ選定以外にデマンドページング作業のための過程でありながら、デバイスがビジー時間の間に実行が可能なメモリマッピングテーブルのアップデート、ＴＬＢとキャッシュ無効化などの作業を行うことも可能である。
【００２３】
上述したように、フラッシュメモリが装着されたデバイスからデータを読み取るためには読み取り命令とアドレスを発生させて、一定時間を待った後データをデバイスからホストに伝送する過程を有する。一定時間を待つことはフラッシュメモリの構造上、データが格納された不揮発性格納装置のセルから揮発性格納装置のバッファまたはレジスタにデータを持ってくる時間が必要とされるためである。
【００２４】
フラッシュメモリのセルに格納されたデータをバッファに持ってくるのに必要とする時間を効率的に活用すれば、フラッシュメモリでのデータロード時間を減らせる。
【００２５】
図２は、本発明の一実施形態に係る前記データロード時間を減らしながらページングを処理する過程を示す時間フローチャートである。図１と比較して物理メモリの空間を確保して、マッピングテーブルを更新する作業を「Ｂｕｓｙ」の場合に行う。ページフォールトハンドラが「ＲＥＡＤ  ＣＭＤ」を生成すれば、フラッシュメモリのセルからバッファまたはレジスタにデータを移動させる。この時、ページフォールトハンドラは、「Ｂｕｓｙ」の時間（Ｔ）の間に独自の作業を行うことができる。図２では、物理メモリの空間を確保してマッピングテーブルを更新する作業を併行するようにして時間を減らせる。
【００２６】
図３は、本発明の一実施形態に係るページ置換時間を減らす過程を適用するクロックアルゴリズムの動作を示す図面である。
【００２７】
クロックアルゴリズムは、一種のＦＩＦＯ置換アルゴリズム（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ  ｒｅｐｌａｃｅｍｅｎｔ  ａｌｇｏｒｉｔｈｍ）である。バックアームは、ポインタであって、ＦＩＦＯから最初にキューに入ってきたページを示している。置換されるページ（置換ページ）を選定する時はバックアームが示しているページの参照ビットを確認して、そのページの参照ビットが参照しないことを示す「ＵＲ」（ｕｎｒｅｆｅｒｅｎｃｅｄ）であれば置換ページと選定し、参照することを示す「Ｒ」（ｒｅｆｅｒｅｎｃｅｄ）であれば、そのページには一回の機会をさらに与えて、バックアームを１コマ移動させてバックアームが示すページの参照ビットを確認する。バックアームを移動する時、ポインタのフロントアームも共に移動しながら、フロントアームが示していたページの参照ビットを「ＵＲ」に変更させる。このような方式でバックアームとフロントアームを移動させながら、バックアームが「ＵＲ」を示しているページを発見すれば、該当ページは置換ページと選定される。
【００２８】
図３は、クロックアルゴリズムで置換ページを選定する過程を示す図面である。「５１」でバックアームが示しているページの参照ビットは‘Ｒ’であるため、バックアームが「ＵＲ」ページを示すまでバックアームとフロントアームを移動する。その結果「５２」のように３回移動して、ページ１３を置換ページとして選定した。また、バックアームを３回移動しながら、フロントアームも同様に３回移動し、フロントアームが移動しながら、ページ２、１１、そして７の参照ビットを「ＵＲ」に設定した。このように置換ページを選定した後、「５３」のように新しいページ４を割当させて、バックアームとフロントアームを各々１回移動させる。「５４」は、「５３」で参照ビットが「ＵＲ」のページ７が再び参照された場合の例である。クロックアルゴリズムで「ＵＲ」のページが再び参照されれば、参照ビットを「ＵＲ」から「Ｒ」に変更する。その結果「５５」のようにページ７の参照ビットが「Ｒ」に変更される。
【００２９】
図４は、本発明の一実施形態に係る図３のクロックアルゴリズムにページ置換時間を減らす過程を示す図面である。図３に示すように、バックアームは「ＵＲ」ページを参照するまでポインタが移動、フロントアームはバックアームの移動によりポインタを移動させながら、参照ビットを「Ｒ」から「ＵＲ」に変更する。ところで、バックアームとフロントアームとの間に全てのページの参照ビットが「Ｒ」の場合には、結局バックアームとフロントアームの差だけポインタを移動させる探索過程を経た後にフロントアームが「ＵＲ」に変更したページをバックアームが置換するようになる。図４の「６２」でバックアームとフロントアームとの間に存在するページが全て「Ｒ」である場合、バックアームはページ２５まで移動しなければならず、フロントアームはページ２５からずっと参照ビットを「ＵＲ」に変える作業をしなければならないため、これは時間的な浪費になり得る。したがって、図４では一定時間Ｔ以内にだけ「ＵＲ」のページをバックアームが検索し、バックアームが「ＵＲ」のページを発見できない場合でも、一定時間Ｔが過ぎれば「Ｒ」のページを置換ページにする。
【００３０】
図４の「６３」でバックアームは一定時間Ｔの間「ＵＲ」であるページを検索するが、「ＵＲ」であるページを探せなくなった。そして、バックアームが移動する間フロントアームも一定時間Ｔ移動しながら、ページの参照ビットを「ＵＲ」に変更する。
【００３１】
Ｔ時間が過ぎればバックアームはページ２を示し、フロントアームはページ２６を示し、両方とも「Ｒ」である。２つのアームが示すページが「Ｒ」であっても、これらを置換ページにすることができる。「６４」ではフロントアームが示すページ２６を置換ページにした。勿論、バックアームが示すページ２を置換ページにすることができる。
【００３２】
前記一定時間Ｔは、システムに応じて別に設定される。この時、図２でフラッシュのような不揮発性格納装置からデータを読み取る期間（ビジー）中に前記のバックアームとフロントアームを移動しながらページを検索することができる。ビジー期間中にはシステムが不揮発性格納装置からデータを読み取れない期間であるため、この時、ページフォールトを処理する作業を行えば必要とする時間を減らすことができる。
【００３３】
図４でページ置換のために、バックアームとフロントアームを移動させる時間を減らすための限界時間Ｔを設け、一実施形態として限界時間Ｔを不揮発性格納装置からデータを読み取る時間と重複するようにした。
【００３４】
図５は、Ｍａｃｈ２．５アルゴリズムで置換ページを選定する過程を示す図面である。
【００３５】
Ｍａｃｈ２．５アルゴリズムはスタック方式でページを管理する。最近参照されたページはスタックの最上に置かれ、最初に参照されたページはスタックの最下に置かれて、ページ置換時にはスタックの最下にあるページを選定することによって最初に参照されたページが置換ページとなる。
【００３６】
Ｍａｃｈ２．５アルゴリズムは、ページを有効リストと置換リスト(無効リスト)とで区分して管理する。有効リストのページは、ページフォールトが発生しないため参照するか否かを知ることができないリストであり、置換リストのページは実際にページが物理メモリには積載されているが、ページを参照するか否かを知るために偽物のページフォールトが発生することができるようにページを無効化させる。したがって、有効リストには常に最近参照されたページがスタックされて、有効リストに新しいページが挿入されるごとに最初に有効リストに追加されたページが置換リストとしてスタックされる。置換リストにあるページが参照されれば、該当ページは有効リストの最前に置かれて常に最近参照されたページとして管理される。
【００３７】
図５のＭａｃｈ２．５アルゴリズムの実施では、置換ページ選定と新しく参照されたページをリストに追加する例である。Ｍａｃｈ２．５アルゴリズムの置換ページは常に置換リストの最後のページとなる。そして、新しく追加するページは有効リストの最前に追加させ、この時有効リストの最後のページを置換ページに移す作業が追加される。
【００３８】
（ａ）で「７０」は有効リストであり、「８０」は置換リストである。最近参照されたページは４であり、置換リストで最も置換されるページは２０である。ページ５を参照するために、置換リスト８０のページ２０が置換ページとなる。（ｂ）は置換された結果で、置換リスト８２にはページ２０が存在せず、ページ２０のメモリ領域がページ５に割り当てられてページ５は有効リスト７１に存在する。
【００３９】
置換リスト８２には有効リスト７２の最後のページのページ２を置換ページに移す。したがって、（ｃ）のようにページ２が有効リスト７４から置換リスト８４に移動した。
【００４０】
（ｃ）の置換リスト８４に存在するページ７を参照する場合、ページ７は有効リストに移動する。その結果（ｄ）のようにページ７は置換リスト８６から除去され、有効リスト７６の最前に追加される。そして、有効リスト７６のページ９は置換リスト８６に移動する作業が必要である。（ｅ）はページ９が置換リスト８８に移動したことを示す。
【００４１】
図５のＭａｃｈ２．５アルゴリズムの動作は、ページが置換されるごとに有効リストのページを置換リストに移動させる作業を行う。すなわち、置換リストにあるページが参照された場合、該当ページを有効リストの最前に挿入して、有効リストの１つのページを置換リストに移す作業からなる。Ｍａｃｈ２．５のアルゴリズムはページが参照された時に行うリスト管理オーバーヘッドが発生する。
【００４２】
このような作業を毎度行うことは時間が必要であるため、システムが特定作業を行わない時間に置換リストを移動させて全体作業時間を減らすことができる。
【００４３】
図６は、本発明の一実施形態に係る図５のＭａｃｈ２．５アルゴリズムで置換リストの移動時点を行う過程を示す図面である。
【００４４】
図６では、置換するページを選定する時間はデバイスがデータを読み取るために待機する時間のようにオペレーションを行わない時間に実行可能で、この時間内に置換ページ選定と置換リスト、有効リストの更新がなされない場合には一部の作業を追ってデバイスが待機する時間に作業するようにして、ページング処理性能を向上させられる。
【００４５】
（ａ）で置換リスト１００に存在するページ７を参照する。その結果、（ｂ）のようにページ７は置換リスト１０２から除去して、有効リスト９２の最前に挿入する。図５では有効リストの最後のページを置換リストに移動させるが、図６ではこのような移動作業を行わない。これは追って作業する。
【００４６】
（ｃ）は（ｂ）の状態で新しいページのページ６を参照して、その結果、新しいページを割り当てるために置換リスト１０４から置換ページを有効リスト９４に追加してページ６に割り当てる。一方、前述した過程のように、有効リスト９４のページを置換ページ１０４に移動させない。
【００４７】
（ｄ）は新しいページ２２を参照して、その結果、有効リスト９６に新しいページ２２が追加され、置換リスト１０６からページが除去される。同様に有効リスト９６から置換リスト１０６にページを移動させる過程は省略される。
【００４８】
前記ページング過程が行われる間、デバイスが図２で例として挙げた「Ｂｕｓｙ」期間の場合、デバイスは有効リスト９８のページを置換リスト１０８に移動させる。
【００４９】
すなわち、初期有効リストの数に比べて増えたページの数だけを有効リストの最後の部分から抽出して置換リストに移す。この時、置換リストに移動させなければならないページの数が多い場合、デバイスの「Ｂｕｓｙ」時間を考慮して、特定時間内に移動させることができなかったページは次の新しいページ参照時に処理することができるようにする。したがって、一回のページング処理時間が特定時間以上に増加することを防止することができる。
【００５０】
図７は、本発明の一実施形態に係る読み取り命令を送信してページングのためのメモリ作業を行うフローチャートである。図２で物理メモリ空間を確保してマッピングテーブルを更新する時点Ｔ内に図４または図６で示したページング処理作業を行う場合のフローチャートである。
【００５１】
ページフォールトが発生すれば該当ページを読み取らなければならない。したがって、該当ページが格納された不揮発性格納装置のアドレスを抽出する（Ｓ１２０）。マッピングテーブルにこのような情報が記録される。このアドレスを不揮発性格納装置に読み取り命令を送信する（Ｓ１２２）。読み取り命令を不揮発性格納装置に送信して、再びデータを受信するまでは図２で示したように一定時間が必要である。この時間の間、読み取ったページを格納する物理メモリの空間確保のために置換ページを選定する（Ｓ１２４）。そして、メモリマッピングテーブルを更新する（Ｓ１２６）。また、不揮発性格納装置からページを読み取って物理メモリに格納する（Ｓ１２８）。
【００５２】
図４のクロックアルゴリズムで限界時間Ｔだけバックアームとフロントアームを移動させること、または図６のＭａｃｈ２．５アルゴリズムで限界時間内に有効リストと置換リストを管理して、完了しない部分は次の限界時間の間実行することがＳ１０４とＳ１０６の過程に含まれる。
【００５３】
一方、本明細書では図４と図６の限界時間は必ず図２の限界時間Ｔと一致することを要求するのではない。図４と図６で置換ページ選定と置換リスト管理に必要な作業はシステムが休止状態（アイドル）の場合にいつでも行えることであり、休止状態の一例として、不揮発性メモリからデータを読み取るためにシステムが待機する時間を休止状態にすることができる。
【００５４】
図８は、本発明の一実施形態に係るページングの実行時間を短縮させる過程を示すフローチャートである。ページングでは一部のページだけメモリにロードまたは格納するため、アプリケーションでメモリの特定ページを要請する場合、ページフォールトが発生することができる。ページフォールトの発生を知らせる信号を受信すれば（Ｓ２００）、ページフォールトが発生したページに関する情報、例えば、論理的または物理的アドレスを含む情報を不揮発性メモリに送信する（Ｓ２１０）。図８の動作はフラッシュメモリのように、データを読み取るためにバッファまたはレジスタを経てシステムにデータを伝送する不揮発性メモリに適用可能である。Ｓ２１０で不揮発性メモリにページに関する情報、例えばアドレスに関する情報を送信して、該当アドレスのデータを読み取るまで時間が必要であるため、その間にＳ２３０、Ｓ２４０過程を行う。追って不揮発性メモリから読み取るようになるページを格納することができるように、メモリで置換ページを選定する（Ｓ２３０）。そして、ページングのためのリストを管理する（Ｓ２４０）。
【００５５】
さらに、ページのデータを不揮発性メモリから受信する（Ｓ２５０）。受信したデータをメモリに格納して、アプリケーションの動作を進行する（Ｓ２６０）。この時、Ｓ２１０とＳ２５０の間の時間にＳ２３０とＳ２４０作業を行うようになる。
【００５６】
前述したクロックアルゴリズムを説明すれば、置換対象になる複数のページを管理するポインタ（バックアーム、フロントアーム）を移動させ、移動したポインタが指示するページを、前記フォールトが生じたページを格納する空間として確保するステップがＳ２３０とＳ２４０になり得る。勿論、前記のＳ２３０とＳ２４０は必ずしもＳ２１０とＳ２５０の間に生じなければならないことではない。システムが休止時間に行うことができる。
【００５７】
同様に、Ｍａｃｈ２．５アルゴリズムを用いる場合、メモリ内のページを有効リストと置換リストとで分け、有効リストは現在参照されたページのリストで、置換リストは今後置換されるページのリストを含むようにして、これらリスト間にページを移動させる過程が必要である。このようなリスト間のページ置換などの作業がＳ２３０とＳ２４０で行われ、システムが休止時間に行うことができる。前記システムの休止期間はＳ２１０とＳ２５０の間の時間になり得る。
【００５８】
図９は、本発明の一実施形態に係るシステムの構成図である。本実施形態で用いられる「〜部」という用語、すなわち「モジュール」または「〜テーブル」などは、ソフトウェアまたはＦＰＧＡまたはＡＳＩＣのようなハードウェア構成要素を意味し、モジュールはある役割を行う。ところが、モジュールは、ソフトウェアまたはハードウェアに限定される意味ではない。モジュールは、アドレッシングできる格納媒体にあるように構成することもでき、１つまたはそれ以上のプロセッサを再生させるように構成することもできる。したがって、一例としてモジュールはソフトウェア構成要素、オブジェクト指向ソフトウェア構成要素、クラス構成要素およびタスク構成要素のような構成要素と、プロセス、関数、属性、プロシージャ、サブルーチン、プログラムコードのセグメント、ドライバ、ファームウェア、マイクロコード、回路、データ、データベース、データ構造、テーブル、アレイ、および変数を含む。構成要素とモジュールの中で提供されている機能は、さらに小さい数の構成要素およびモジュールに結合したり、追加的な構成要素とモジュールにさらに分離したりすることができる。だけでなく、構成要素およびモジュールはデバイス内の１つまたはそれ以上のＣＰＵを再生させるように具現することもできる。
【００５９】
システムまたは装置３００は、携帯電話、ＭＰ３プレーヤ、ＰＭＰ、ＰＤＡ、ノート型パソコンなど不揮発性格納装置を有する機器を含む。不揮発性格納装置４００は、上述したようにフラッシュメモリのような格納媒体を用いることができる。不揮発性格納装置４００、すなわち不揮発性メモリは、電源の供給なしで格納されたデータをする。不揮発性格納装置４００は、カードのような形態で着脱することができ、装置内に埋め込むことができる。
【００６０】
メモリ３５０は、不揮発性格納装置４００からデータを受信して格納し、データ格納時に電源の供給を必要とする。メモリは、ページングを介して、本来格納可能な容量よりさらに多い容量のデータを管理することができる。これを可能にするようにメモリ管理部３２０、ページフォールトハンドラ３１０が存在する。メモリ管理部３２０は、ページフォールトの発生を知らせる信号をページフォールトハンドラ３１０に送信する。ページフォールトハンドラ３１０は、ページフォールトが生じたページの情報を抽出して、前記ページを格納するメモリ３５０の空間を検索して確保する。ページフォールトハンドラ３１０は、メモリ３５０の空間を検索して確保するための方案として、前述したクロックアルゴリズム、Ｍａｃｈ２．５アルゴリズムなどを適用することができる。
【００６１】
デバイスドライバ３４０は、不揮発性格納装置４００にフォールトが発生したページの情報を送信し、前記不揮発性メモリからデータを受信する。この時間の間隔が装置３００の側面から休止期間になり得る。ページフォールトハンドラ３１０は、前記休止期間または予め計算された限界時間以内にメモリ３５０にページを格納するための空間を検索して確保する作業を行う。
【００６２】
ページキャッシュ管理者３３０は、ページのアドレスとメモリでの位置または不揮発性格納装置での情報を一部キャッシュして管理する。
【００６３】
本発明が属する技術分野で通常の知識を有する者であれば、本発明がその技術的思想や必須の特徴を変更せず、他の具体的な形態によって実施することができるということを理解できる。したがって、以上で記述した実施形態はすべての面で例示的なものであり、限定的なものではないことを理解しなければならない。本発明の範囲は前記詳細な説明より後述する特許請求の範囲によって具現され、特許請求の範囲の意味および範囲、そしてその均等概念から導き出される全ての変更または変形された形態が本発明の範囲に含まれると解釈しなければならない。
【図面の簡単な説明】
【００６４】
【図１】ページング処理過程を時間の流れにソフトウェア処理過程とデバイスＩ／Ｏとの関係を示す図である。
【図２】本発明の一実施形態に係る前記データロード時間を減らしながらページングを処理する過程を示す時間フローチャートである。
【図３】本発明の一実施形態に係るページ置換時間を減らす過程を適用するクロックアルゴリズムの動作を示す図である。
【図４】本発明の一実施形態に係る図３のクロックアルゴリズムにページ置換時間を減らす過程を示す図である。
【図５】Ｍａｃｈ２．５アルゴリズムで置換ページを選定する過程を示す図である。
【図６】本発明の一実施形態に係る図５のＭａｃｈ２．５アルゴリズムで置換リストの移動時点を見直して行う過程を示す図である。
【図７】本発明の一実施形態に係る読み取り命令を送信してページングのためのメモリ作業を行うフローチャートである。
【図８】本発明の一実施形態に係るページングの実行時間を短縮させる過程を示すフローチャートである。
【図９】本発明の一実施形態に係るシステムの構成図である。
【符号の説明】
【００６５】
３００      システム
３１０      ページフォールトハンドラ
３２０      メモリ管理部
３３０      ページキャッシュ管理者
３４０      デバイスドライバ
３５０      メモリ
４００      不揮発性格納装置
【図１】
0004481999.tif 000002
【図２】
0004481999.tif 000003
【図３】
0004481999.tif 000004
【図４】
0004481999.tif 000005
【図５】
0004481999.tif 000006
【図６】
0004481999.tif 000007
【図７】
0004481999.tif 000008
【図８】
0004481999.tif 000009
【図９】
0004481999.tif 000010