(57)【特許請求の範囲】
【請求項１】
ＮＡＮＤフラッシュメモリおよびメモリコントローラを組み込んだメモリシステムにおける方法であって、
前記メモリコントローラにより実行されるべきファームウェアを前記ＮＡＮＤフラッシュメモリに格納するステップと、
前記ファームウェアを、ファームウェアの実行に専用されるオーバーレイＲＡＭメモリの最大量より小さい様々なサイズのオーバーレイに論理的に順序付けるステップと、
選択されたオーバーレイに格納されている関数を呼び出すステップと、
前記オーバーレイＲＡＭメモリに前記選択されたオーバーレイを初めにロードするステップと、
前記選択されたオーバーレイがデータのために前記オーバーレイＲＡＭメモリ内のスペースの割当てを必要とするというインジケーションを保存するステップと、
前記選択されたオーバーレイのためのデータ割当て領域の外側の前記オーバーレイＲＡＭメモリの位置に前記選択されたオーバーレイをロードすることにより、前記オーバーレイＲＡＭメモリからの前記選択されたオーバーレイの自己エビクションを回避するために前記インジケーションを継続して利用するステップと、
を含む方法。
【請求項２】
請求項１記載の方法において、
前記インジケーションは、実行時に保存される方法。
【請求項３】
請求項１〜２のいずれか記載の方法において、
前記インジケーションは、オーバーレイオフセットテーブルに保存される方法。
【請求項４】
請求項１〜３のいずれか記載の方法において、
前記インジケーションは、前記ＮＡＮＤフラッシュメモリに保存される方法。
【請求項５】
請求項１〜４のいずれか記載の方法において、
前記インジケーションを継続して利用するステップは、前記選択されたオーバーレイが前記選択されたオーバーレイを初めにロードするステップの後に呼び出される各々の場合に、保存されたデータ割当ての必要性のインジケーションを参照することを含む方法。
【請求項６】
請求項１〜５のいずれか記載の方法において、
前記オーバーレイＲＡＭメモリ内で必要とされるスペースの割当てのサイズのインジケーションを保存するステップをさらに含む方法。
【請求項７】
請求項１〜６のいずれか記載の方法において、
前記インジケーションを継続して利用するステップは、前記選択されたオーバーレイが前記選択されたオーバーレイを初めにロードするステップの後に呼び出される各々の場合に、保存されたデータ割当ての必要性のインジケーションと、必要とされるスペースの割当てのサイズのインジケーションとを参照することを含む方法。
【請求項８】
請求項１〜７のいずれか記載の方法において、
前記インジケーションを継続して利用するステップは、前記オーバーレイＲＡＭメモリのデータ割当て領域を確保することと、前記選択されたオーバーレイを前記データ割当て領域より下にロードすることをさらに含む方法。
【請求項９】
請求項１〜８のいずれか記載の方法において、
前記データ割当て領域は、前記オーバーレイＲＡＭメモリの上側境界にある方法。
【請求項１０】
請求項１〜９のいずれか記載の方法において、
前記データ割当て領域は、前記ファームウェアの任意の関数のための最大必要データ割当てと等しいかまたはそれより大きい方法。
【請求項１１】
請求項１〜１０のいずれか記載の方法において、
前記必要とされるスペースの割当てのサイズのインジケーションは、オーバーレイオフセットテーブルに保存される方法。
【請求項１２】
請求項１〜１１のいずれか記載の方法において、
前記必要とされるスペースの割当てのサイズのインジケーションは、前記ＮＡＮＤフラッシュメモリに保存される方法。
【請求項１３】
請求項１記載の方法において、
前記選択されたオーバーレイを１回目に前記オーバーレイＲＡＭメモリにロードし、前記選択されたオーバーレイがその１回目にロードされるときには前記オーバーレイＲＡＭメモリの上側境界にロードされ、
前記方法は、前記オーバーレイＲＡＭメモリにおけるメモリ割当てを必要とする関数を前記選択されたオーバーレイが呼び出すか否かを判定するステップをさらに含み、
前記インジケーションを継続して利用するステップは、１回目の後の各回において前記オーバーレイＲＡＭメモリの上側境界以外の領域に前記選択されたオーバーレイをロードすることを含む方法。
【請求項１４】
請求項１３記載の方法において、
前記オーバーレイＲＡＭメモリにおけるメモリ割当てを必要とする関数を前記選択されたオーバーレイが呼び出すか否かを判定するステップは、書き込まれるべきデータのために割当てが必要とされるか否かを判定することを含む方法。
【請求項１５】
フラッシュメモリ記憶システムであって、
ＮＡＮＤフラッシュメモリと、
メモリコントローラと、
前記メモリコントローラにより実行されるべきファームウェアであって、前記ＮＡＮＤフラッシュメモリに格納され、様々なサイズのオーバーレイに分解されるファームウェアと、
前記ファームウェアを実行するための前記メモリコントローラ内のＲＡＭメモリと、を備え、
前記システムは、
選択されたオーバーレイに格納されている関数を呼び出し、
前記メモリコントローラ内のＲＡＭメモリに前記選択されたオーバーレイを初めにロードし、
前記選択されたオーバーレイがデータのために前記ＲＡＭメモリ内のスペースの割当てを必要とするというインジケーションを保存し、かつ
前記選択されたオーバーレイのためのデータ割当て領域の外側の前記ＲＡＭメモリの位置に前記選択されたオーバーレイをロードすることにより、前記選択されたオーバーレイの自己エビクションを回避するために前記インジケーションを継続して利用するように構成されるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フラッシュメモリに関し、特にフラッシュメモリ記憶装置のファームウェアの管理に関する。
【背景技術】
【０００２】
関連出願との相互参照
本願は、その全体が本願明細書において参照により援用されている、２００８年７月２２日に出願された「Avoidance of Self Eviction Caused by Dynamic Memory Allocation in a Flash Memory Storage Device 」という米国特許出願第１２／１７７，８６３号（特許文献１）の優先権を主張する。
【０００３】
フラッシュメモリ大容量記憶装置、すなわち、主として大量のユーザファイルを格納するために使用されるものは、ＮＯＲや他のＸＩＰ（eXecute In Place）メモリではなくてＮＡＮＤフラッシュメモリを主記憶ユニットとしてよく利用する。そのような記憶装置は、写真および音楽等の大規模なライブラリを格納するために使用されるデジタルメモリカードおよびＵＳＢドライブ等を含み、最近は或るラップトップコンピュータにおいて一次記憶装置としても利用されている。ＮＡＮＤでは大量の記憶域を利用できるので、ファームウェアを格納するには、たとえそれをＮＡＮＤから実行できないとしても、ＮＡＮＤを用いることが望ましい。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許出願第１２／１７７，８６３号
【特許文献２】米国特許出願第１２／０３１，３８４号
【非特許文献】
【０００５】
【非特許文献１】MetaWareTM Development Toolkit - Automated Overlay Management Specification Rev 1.5 of ARCTM International, available at www.arc.com
【発明の概要】
【０００６】
携帯用のフラッシュメモリ記憶装置のオペレーティングファームウェアは、実行可能ではない割合に大きなファイル記憶メモリに格納される。それは、実行可能なメモリに収まるオーバーレイに論理的に分解される。デッドスペースと、頻繁にアクセスされるオーバーレイの１つまたはグループの中にあるべき関数の不必要な分離とを最小にすると同時に関数呼び出しを効率的に編成するために、オーバーレイのサイズは様々であってよい。データ割当てを必要とする関数を有するオーバーレイについて、データ割当てはエビクションを引き起こすことがある。この自己エビクションは、完全にあるいは初期実行後に回避される。
【０００７】
本発明の１つの態様は、メモリコントローラにより実行されるべきファームウェアをメモリシステムのＮＡＮＤフラッシュメモリに格納することを含む方法に関する。この方法は、そのファームウェアを様々なサイズのオーバーレイに論理的に順序付けすることと、要求されたオーバーレイをＲＡＭメモリにロードすることと、そのオーバーレイが初めにロードされる時にオーバーレイ内の関数のＲＡＭメモリ内でのデータスペース要件に基づいてロードされたオーバーレイをエビクションするけれども、オーバーレイが初めにロードされた時の後にはデータスペース要件のためにＲＡＭ内のスペースを確保し、これによってオーバーレイをエビクションする必要をなくすこととをも含む。
【０００８】
本発明の他の１つの態様は、ＮＡＮＤフラッシュメモリおよびメモリコントローラを組み込んだメモリシステムにおける方法に関する。この方法は、メモリコントローラにより実行されるべきファームウェアをＮＡＮＤフラッシュメモリに格納することと、ファームウェアを、ファームウェアの実行に専用されるオーバーレイＲＡＭメモリの最大量より小さい様々なサイズのオーバーレイに論理的に順序付けることと、オーバーレイに格納されている関数を呼び出すことと、オーバーレイをメモリコントローラの専用ＲＡＭメモリにロードすることと、選択されたオーバーレイがデータのためにオーバーレイＲＡＭ内のスペースの割当てを必要とするというインジケーションを保存することと、その後、選択されたオーバーレイの自己エビクションを回避するためにインジケーションを利用することとを含む。
【０００９】
本発明の別の１つの態様は、ＮＡＮＤフラッシュメモリおよびメモリコントローラを組み込んだメモリシステムにおける方法に関する。この方法は、メモリコントローラにより実行されるべきファームウェアをＮＡＮＤフラッシュメモリに格納することと、ファームウェアを、ファームウェアの実行に専用されるオーバーレイＲＡＭメモリの最大量より小さい様々なサイズのオーバーレイに論理的に順序付けることと、オーバーレイに格納されている関数を呼び出すことと、オーバーレイをメモリコントローラの専用ＲＡＭメモリにロードすることと、選択されたオーバーレイがデータのためにオーバーレイＲＡＭ内のスペースの割当てを必要とするというインジケーションを保存することと、その後、選択されたオーバーレイの自己エビクションを回避するためにインジケーションを利用することとを含む。
【図面の簡単な説明】
【００１０】
【図１Ａ】フラッシュメモリ記憶装置１００を示すブロック図である。
【図１Ｂ】フラッシュメモリ記憶装置１００のＲＡＭおよびフラッシュメモリスペースの一部分を示すブロック図である。
【図１Ｃ】オーバーレイ管理を説明するフローチャートである。
【図２Ａ】最初のオーバーレイのローディングのプロセスを示すフローチャートである。
【図２Ｂ】その後のオーバーレイのローディングのプロセスを示すフローチャートである。
【発明を実施するための形態】
【００１１】
ソフトウェアプログラムは電子装置で実行可能なメモリにロードされて実行される。ソフトウェアプログラムがその装置の実行可能なメモリ容量より大きければ、ソフトウェアオーバーレイまたは仮想メモリが使用される。
仮想メモリは、ハードウェアで実現されるメモリ管理ユニットを通例使用するオペレーティングシステムを介して物理メモリにマッピングされるアドレス空間である。これは、パーソナルコンピュータおよびその他の無制約型のコンピュータ装置では普通のことである。仮想メモリシステムでは、大きなプログラムは、「ページ」と称される小さなセグメントに分解される。ページは、必要に応じて補助記憶装置から、そのプログラムのために確保されているマシンのメモリのセクションにロードされる。
メモリカードおよび他のフラッシュメモリ記憶装置では仮想メモリは実際的ではなくて、通例実装されない。従って、ソフトウェアオーバーレイが利用される。フラッシュメモリ記憶装置のオペレーティングソフトウェアは通例ファームウェアと称される。ファームウェアオーバーレイは、オーバーレイマネージャによって必要とされたときにメモリに呼び込まれたプログラムセグメントである。呼び込まれた各オーバーレイは、メモリ内に存在するオーバーレイをオーバーライトすることがある。オーバーレイのためのメモリの動的割当ては慎重に管理されなければならない。
【００１２】
図１Ａは、フラッシュメモリ記憶装置（「ＦＭＳＤ」）１００を示す。ＦＭＳＤは、フラッシュメモリアレイ１０８と、メモリコントローラ１０４と、ホストインターフェイス１０２とを含む。フラッシュメモリアレイ１０８は、非ＸＩＰ型のフラッシュメモリであり、好ましくはＮＡＮＤアーキテクチャの非ＸＩＰ型のフラッシュメモリであり、通例ＥＥＰＲＯＭの形をとる。フラッシュメモリアレイ１０８は、大量のユーザファイルを格納するために使用され、装置１００の主データ記憶リポジトリである。それゆえ、アレイ１０８に伴う大きな容量を利用してファームウェア、すなわちＦＭＳＤ１００のための動作命令を格納するのが望ましい。メモリコントローラ１０４自体は、プロセッサと、実行可能なランダムアクセスメモリ（「ＲＡＭ」）（図示せず）とを含む。ＦＭＳＤ１００は、メモリコントローラの外側の１つ以上のＲＡＭメモリを含むこともできる。ホストインターフェイス１０２は、セキュアデジタルまたは他のメモリカード規格等のメモリカードの接点であるように構成されるか、ユニバーサルシリアルバス（「ＵＳＢ」）コネクタまたはＩＥＥＥ１３９４「ファイアワイヤ」コネクタ等であるか、あるいは、ＦＭＳＤ１００が埋め込まれる場合には、特定装置向けインターフェイスであってもよい。フラッシュメモリアレイ１０８は、制御線およびデータ線１０６を介してメモリコントローラ１０４に結合される。
【００１３】
メモリ記憶装置を動作させるファームウェアは実行されるべくＲＡＭに収まる適切なサイズのオーバーレイに分解される。オーバーレイを不必要にＲＡＭに入れたり出したりして循環させることに起因する待ち時間を最小にして、ファームウェアのタスクが効率良く実行されるように、どんな関数呼び出しが種々のオーバーレイに最適に入るべきかを判定するのに無数の時間が費やされる。例えば、第１のオーバーレイの中の関数が第２のオーバーレイの中の他の関数を呼び出したりその逆が行われたりする場合、システムはその２つのオーバーレイの間を「スラッシング」するために多くの時間を費やすことになる。２つのオーバーレイに関するこの例は簡単すぎるけれども、ポイントは、オーバーレイ管理が適切に管理されなければ、ファームウェアの全体の関数を実行するよりもむしろオーバーレイ間で単にスイッチングするのに多くの時間を費やすことになり得るということである。
【００１４】
ハードドライブまたは他のデータ記憶メカニズムの記憶装置アクセス時間よりも処理速度のほうが通例著しく速くて大量のＲＡＭを利用し得るパーソナルコンピュータ等の大きなプロセッサ制御されるシステムでは、これはあまり問題ではない。利用し得るＲＡＭの量が割合に多いことは、ＰＣ等で利用し得る仮想メモリ管理手法とともに、制約付きシステム環境に特有のものではない。
【００１５】
ＮＡＮＤメモリを組み込んだ制約付きシステム環境では、ＮＡＮＤアーキテクチャの記憶動作を管理するためにファームウェアが非常に大きくて複雑であるので、特に問題である。ＮＡＮＤメモリは、しばしば、複数のメモリダイの中、あるいはメモリダイ間の他の領域とは品質が異なる領域を有する。コストを節約するために、メモリカード等のシステムは、そのような品質のばらついた領域を伴う未検査ＮＡＮＤを使用する。これは、低品質領域を利用しないかあるいは存在しないという意味での試験済みの良好なＮＡＮＤだけを使用し得るシステムとは対照的である。最低のコストで提供されなければならない大容量装置では、そのような贅沢は利用し得ないし実際的でもない。そのような装置では、信頼性のない領域が必要に応じて精密にマッピングされてユーザファイルおよびデータが犠牲にされたり失われたりしないように、ファームウェアは、種々の領域の性能を絶えず監視して読み出し／書き込みパラメータおよびデータの物理的／論理的マッピングを改変するためにＮＡＮＤの使用法を積極的に管理しなければならない。その結果、（試験済みの良好なＮＡＮＤを伴う場合よりも）もっと大きくてより複雑なファームウェアとなり、オーバーレイ管理およびＲＡＭ使用法がそれゆえに重要となるということを意味する。
【００１６】
オーバーレイに格納されている（ファームウェア）関数は、いつでも呼び出され得る。その関数が呼び出されるときにその関数を含むオーバーレイがＲＡＭの中にあるという保証はない。ファームウェアの自動オーバーレイマネージャ（「ＡＯＭ」）は、関数が呼び出されるけれどもＲＡＭ内に存在していないという「フォルト（fault ）」の場合を管理するために各呼び出しを処理する。フォルトの場合、ＡＯＭはその関数を配置してそれを呼び出す前に、適切なオーバーレイをロードする。
【００１７】
図１Ｂは、ＦＭＳＤ１００のＲＡＭおよびフラッシュメモリ空間の一部分を示す。ＲＡＭのメインコード領域１２０は、記述子／エントリ１２４ａ〜１２４ｘを有するオーバーレイマッピングテーブル（「ＯＭＴ」）１２４を含む。ＯＭＴは、オーバーレイＲＡＭ（「ＯＲＡＭ」）に現在ロードされているオーバーレイを記述するテーブルである。ＯＭＴ１２４の各エントリ１２４ａ〜１２４ｘは、オーバーレイ領域１３０とも称される、ＯＲＡＭ１３０内の特定の領域を記述する。１２４ＯＭＴは、ＲＡＭ内のオーバーレイへのマップであって常に変化している。それは、どれだけの量のＲＡＭがどのオーバーレイに割り当てられていてＲＡＭのどの部分（１つまたは複数）が空いているのかを定義する。
【００１８】
ＯＲＡＭ１３０はオーバーレイオフセットテーブル（「ＯＯＴ」）１３１を含み、これはさらにＯＲＡＭアドレス１３２ａ〜１３２ｘを含む。ＯＯＴ１３１は、フラッシュメモリ内のオーバーレイへのマップである。各ＯＲＡＭアドレス１３２ａ〜１３２ｘは、フラッシュメモリ内の特定のオーバーレイの対応するオフセット１３４ａ〜１３４ｘを示す。ＯＯＴ１３１は、要求に応じてあるポイントでロードされるべき候補であるフラッシュ内に置かれた全てのオーバーレイ１４０ａ〜１４０ｘを記述するテーブルである。ＯＯＴ１４２自体は、オーバーレイとともにＯＲＡＭにロードされる。オーバーレイ１３６ａ〜１３６ｘまたは１４０ａ〜１４０ｘの各々は、オーバーレイ１４０ａおよび１４０ｂに表されているように少なくとも１つの関数を含む。
【００１９】
図１Ｂに見られるように、種々のオーバーレイ１３６ａ〜１３６ｘ（１３６ａおよび１３６ｂだけが示されている）がＯＲＡＭ１３０内に存在する。オーバーレイの数は、個々のオーバーレイおよびＯＲＡＭ１３０全体のサイズに依存する。ＯＲＡＭ１３０は、１つの離散的ＲＡＭであるかあるいはオーバーレイに割り当てられた大きなＲＡＭの中の１つの領域であり得る。データ１３８および空きスペース１３９もＯＲＡＭ１３０内に存在する。データ１３８は、書き換え可能であるかあるいは不変であり得る。書き換え可能なデータはスペースの割当てであって、割当てをする呼び出し元は「何か」をそこに置き、それは呼び出し元がそれを解放するまでロックされたままである。データは、コード（オーバーレイ）がされ得るのと同じ仕方ではエビクションされ得ない。不変のデータは少し違って、再び呼び出しが使用したい「何か」ではあるけれども、フラッシュからロードされ、その後は好ましくは読み出し専用として扱われるが、必ずしも読み出し専用でなくてもよい。不変なデータに関して、ＡＯＭは、その不変なデータに対してそれがＲＡＭ内にある間に生じたいかなる変更もライトバックしない。
【００２０】
オーバーレイのローディングは、ＦＭＳＤファームウェアにおけるロジックの主要なフローの中でいつどこにロードするかを明示することを必要とせずに処理されるので、ＡＯＭは「自動的」であると考えられる。それらをいつロードするかの決定はＡＯＭに任されている。すなわち、ＡＯＭの機能性を、任意の数のＦＤＳＭ製品あるいは機器構成にも組み込むことができて、特定のハードウェアの実現形態のために特別に構成されなくてもよい。
各オーバーレイ関数について、コンパイラは、その関数が属するオーバーレイへのトークンリファレンスと、オーバーレイにおける関数のオフセットとを生成する。オーバーレイ関数の各呼び出しのために、コンパイラは、特別なレジスタにおいて関数トークンを提供するＡＯＭハンドラを呼び出すために特別な命令のセットを生成する。
【００２１】
ターゲット関数を呼び出す前に、ＡＯＭは、その関数を含んでいるオーバーレイがＯＲＡＭにロードされていることを確認する。ＯＲＡＭにおけるオーバーレイアドレスに関する情報はＯＯＴに置かれる。ＯＯＴにおけるオーバーレイのインデックスを、オーバーレイトークンから抽出することができる。各ＯＯＴエントリは、オーバーレイＯＲＡＭアドレスフィールドを含む。これは、ショートカットとして役立ち、一定の実施形態においてＯＭＴを検索する必要がなくなる。オーバーレイがＯＲＡＭにロードされていなければ、フィールド値は−１（無効アドレス）に等しい。それは、オーバーレイがフラッシュからＯＲＡＭにロードされるべきことを意味する。ＡＯＭは、これを、他のＯＯＴエントリフィールド−オフセットを用いて行う。オフセットは、フラッシュにおけるオーバーレイアドレスを示す。ターゲット関数が既にＯＲＡＭ内にあるのだとしても、あるいはＡＯＭによってロードされたのだとしても、それを差し支えなく呼び出すことができる。ＯＭＴは、メモリ配置に関する情報を含む。それは記述子を含み、各記述子はスタートアドレス、サイズ、フラグおよびトークン（オーバーレイＩＤ）を含む。フラグフィールドは、エントリが空きメモリを指すのか、オーバーレイで占められているメモリまたはデータバッファを指すのかを示す。これ以上の情報については、その全体が本願明細書において参照により援用されている、ｗｗｗ．ａｒｃ．ｃｏｍで入手し得るＡＲＣ（登録商標）インターナショナルのメタウェア（登録商標）開発ツールキット−自動化オーバーレイ管理仕様１．５版 (MetaWareTM Development Toolkit - Automated Overlay Management Specification Rev 1.5 of ARCTM International, available at www.arc.com) （非特許文献１）を参照されたい。
【００２２】
オーバーレイをロードするためには、ＲＡＭにおいて充分な空きスペースが利用できなくてはならない。スペースは一般に、エビクションプロセスを通して利用可能にされる。
エビクションとは、既にＲＡＭ内にあるオーバーレイを選択して、ロードされるべき新しいオーバーレイのためにスペースを利用し得るようにするためにそれを破棄するプロセスを指す。オーバーレイがエビクションのためにどのように選択されるかはさまざまである。「ロードされてから最も長い時間が経った（「ＬＲＬ」：least recently loaded ）アプローチが、その全体が本願明細書において参照により援用されている、２００８年２月１４日に出願された「Overlay Management in a Flash Memory Storage Device 」という米国特許出願第１２／０３１，３８４号（特許文献２）に開示されている。ＬＲＬアプローチは概して好ましいけれども、自己エビクションを回避するために次のプロセスにより改変／実現／補足された、「使われてから最も長い時間が経った（「ＬＲＵ」：least recently used ）アプローチ等の任意の一般化したエビクション方法を利用することができる。
【００２３】
図１Ｃは、高レベルのオーバーレイ管理の実施形態を記述するフローチャートである。ステップ２００で、システムは、呼び出される関数を伴うオーバーレイがＯＲＡＭ内にあるか否かを調べるためにＯＭＴをチェックする。ＯＲＡＭ内にあるならば、その関数は、ステップ２２０に見られるように、ＯＲＡＭから実行される。しかし、ＯＲＡＭ内にないならば、ステップ２０４で、システムは、オーバーレイオフセットにより決定される、フラッシュ内にオーバーレイを配置するためにＯＯＴへ進む。ステップ２０８で、システムは、他の１つまたは複数の必要とされるオーバーレイのためのスペースを作るために、必要に応じて１つ以上のオーバーレイをエビクションする。ステップ２１２で、オーバーレイがロードされ、ステップ２１６で、ＯＭＴはオーバーレイのローディングを反映するように更新される。関数と関連するオーバーレイとがメモリ内にある状態で、関数はステップ２２０でＯＲＡＭから実行される。
オーバーレイの中の関数が、呼び出されたとき、その関数を含むオーバーレイのエビクションという結果をもたらす事態を回避することが望ましい。
【００２４】
図２Ａは、オーバーレイの初めてのローディングを含むプロセスを示す。
ステップ２５２で、システム（ファームウェア）は、オーバーレイに格納されている関数を呼び出す。ステップ２５６で、その呼び出される関数を含む、これらの代表的な図においてオーバーレイ０１と称されるオーバーレイがステップ２５６でＯＲＡＭにロードされる。それが初めてロードされるときには、好ましくはＯＲＡＭの最上部にロードされるけれども、ＯＲＡＭ内のどこにロードされてもよい。ステップ２６０で、関数はデータのためにメモリスペースを割り当てる。一実施形態では、これはメモリ割当てルーチン（「ＭＡＬＬＯＣ」：memory allocation routine ）を呼び出すＡＯＭを必要とする。その後、ステップ２６４で、ＡＯＭ  ＭＡＬＬＯＣは、データのためにメモリスペースが割り当てられるときに、オーバーレイ０１のエビクションを引き起こす。これが起こるのは、一定の関数は、オーバーレイがロードされたＯＲＡＭスペースを使用する必要性を生じさせるという結果をもたらす割合に大きなデータ割当てを必要とするからである。ステップ２７０で、オーバーレイ０１がデータ割当てを必要とするということを示すようにＯＯＴが更新される。ＯＯＴは、好ましくは、必要とされる割当てのサイズを示すようにも更新される。ステップ２７４で、システム（のＡＯＭ  ＭＡＬＬＯＣ）は、関数がもはやＯＲＡＭ内に常駐していないためにフォルトを引き起こすオーバーレイ０１の呼び出された関数に戻る。ステップ２７８でオーバーレイ０１は再ロードされ、ステップ２８２でシステムは呼び出された関数の実行に戻る。
【００２５】
図２Ｂは、２回目以後にオーバーレイをロードすることを含むプロセスを示す。
ステップ３０２で、オーバーレイ０１に格納されている関数が呼び出される。その後、ステップ３０６で、システムは、オーバーレイ０１の１つ以上の関数により必要とされるデータ割当て領域より下のＯＲＡＭ内の位置にオーバーレイ０１がロードされることを確認する。一実施形態では、これを、前にステップ２７０でＯＯＴに格納された１つまたは複数のインジケーションをチェックすることにより実行する。データ割当てのサイズがＯＯＴに格納される実施形態では、データ割当ては、その格納されたサイズのものである。オーバーレイの中の異なる関数が異なるサイズのデータ割当てを必要とすることがあるので、好ましい実施形態では、データ割当ての格納されるサイズは、オーバーレイの中の任意の関数の最大データ割当てである。他の１つの実施形態では、オーバーレイの中の各関数のために必要とされるデータ割当てのサイズをＯＯＴに保存することができる。必要とされるデータ割当てのサイズが格納されない他の実施形態では、データ割当ては、全てのオーバーレイおよびその中の関数についての最大予想サイズのものであり得る。その後、ステップ３１０で、システムはオーバーレイ０１をデータ割当て領域より下にロードし、ステップ３１４で、呼び出された関数はＡＯＭ  ＭＡＬＬＯＣを呼び出す。好ましい実施形態では、データのためのスペースはＯＲＡＭの最上部に確保され、オーバーレイはその確保されたスペースより下にロードされるけれども、他の実施形態では、このスペースはＯＲＡＭの中のどの位置に確保されてもよくてオーバーレイはその確保されたスペースより上あるいは下にロードされることができるということに留意するべきである。ステップ３１８で、ＡＯＭ  ＭＡＬＬＯＣは、オーバーレイ０１のエビクションなしで関数に戻る。
【００２６】
従って、自己エビクションは、そのような挙動をしがちなオーバーレイが初めて生じたときにだけ発生する。メモリシステムは、本質的に、実行時にオーバーレイの自己エビクションする傾向に関して「学習」し、それに応じて順応する。その代わりに、各オーバーレイについてのＯＯＴエントリは、そのオーバーレイの中の関数がデータ割当てを必要とするか否かという１つまたは複数のインジケーションと、そのデータ割当ての関連サイズとともに事前ロードされる。
【図１Ａ】
0005422652.tif 000002
【図１Ｂ】
0005422652.tif 000003
【図１Ｃ】
0005422652.tif 000004
【図２Ａ】
0005422652.tif 000005
【図２Ｂ】
0005422652.tif 000006