JPH0638242B2 - 要求ペ−ジ仮想アドレス空間におけるメモリ・ブロツク圧縮方法 - Google Patents
要求ペ−ジ仮想アドレス空間におけるメモリ・ブロツク圧縮方法Info
- Publication number
- JPH0638242B2 JPH0638242B2 JP60184383A JP18438385A JPH0638242B2 JP H0638242 B2 JPH0638242 B2 JP H0638242B2 JP 60184383 A JP60184383 A JP 60184383A JP 18438385 A JP18438385 A JP 18438385A JP H0638242 B2 JPH0638242 B2 JP H0638242B2
- Authority
- JP
- Japan
- Prior art keywords
- page
- block
- memory
- virtual address
- address space
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
- G06F12/023—Free address space management
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/12—Replacement control
- G06F12/121—Replacement control using replacement algorithms
- G06F12/126—Replacement control using replacement algorithms with special data handling, e.g. priority of data or instructions, handling errors or pinning
- G06F12/127—Replacement control using replacement algorithms with special data handling, e.g. priority of data or instructions, handling errors or pinning using additional replacement algorithms
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Memory System Of A Hierarchy Structure (AREA)
- Memory System (AREA)
Description
【発明の詳細な説明】 （発明の技術分野） この発明は、メモリ装置に関し、特にメモリ装置の管理
方法に関し、また特にメモリ応答時間を改善するために
活性及び静止ブロツクを分離する方法に関する。
方法に関し、また特にメモリ応答時間を改善するために
活性及び静止ブロツクを分離する方法に関する。
（発明の背景） メモリ管理装置の開発は関連する多くの研究分野と共に
長い歴史がある。数年に亙りメモリ構造の割付け、割付
け解除に大きな関心が払われて来た。Ｈ．Ｍ．デイテル
による「オペレーテイング・システム」（第７章、１９
８２年、米国マサチユーセツツ州、アデイソン・ウエス
レイ発行）にこの問題に関する多数のメモリ構造が示さ
れている。この他の重要な論文がＤ．クヌスによる「コ
ンピユータ・プログラミング技術、第１巻、「アルゴリ
ズムの基礎」（１９６８年米国マサチユーセツツ州、リ
ーデイング、アデイソン・ウエスレイ発行）に説明され
ている。ここで述べる発明はヒープ管理メモリを有する
コンピユータ装置にまず関連しており、廃物収集機構と
共に、又はこれから独立して用いられるものである。
「ヒープ管理」されたメモリは対象のメモリ装置の時間
順序又は大きさによらず、メモリを（排他的又は非排他
的に）割付け、そして解除するものである。廃物収集メ
モリは利用可能なメモリを自動的に再利用され、またこ
のメモリは必要に応じて時々再編成され、メモリ空間の
利用を効率的にすることができる。廃物収集技術の概説
及び関連の背景部材についてはＪ．コーヘンによる「リ
ンク・データ構造の廃物収集」（コンピユーテイング・
サーベイ、第１３巻、第３号、第３４１頁〜第３６７
頁、１９８１年３月発行）に示されている。Ｐ．ビシヨ
ツプは「非常に大きなアドレス空間」（マサチユーセツ
ツ・インステイテユート・オブ・テクノロジー、研究論
文１１１、１９７５年発行）において非常に大きなアド
レス空間の廃物収集について述べている。
長い歴史がある。数年に亙りメモリ構造の割付け、割付
け解除に大きな関心が払われて来た。Ｈ．Ｍ．デイテル
による「オペレーテイング・システム」（第７章、１９
８２年、米国マサチユーセツツ州、アデイソン・ウエス
レイ発行）にこの問題に関する多数のメモリ構造が示さ
れている。この他の重要な論文がＤ．クヌスによる「コ
ンピユータ・プログラミング技術、第１巻、「アルゴリ
ズムの基礎」（１９６８年米国マサチユーセツツ州、リ
ーデイング、アデイソン・ウエスレイ発行）に説明され
ている。ここで述べる発明はヒープ管理メモリを有する
コンピユータ装置にまず関連しており、廃物収集機構と
共に、又はこれから独立して用いられるものである。
「ヒープ管理」されたメモリは対象のメモリ装置の時間
順序又は大きさによらず、メモリを（排他的又は非排他
的に）割付け、そして解除するものである。廃物収集メ
モリは利用可能なメモリを自動的に再利用され、またこ
のメモリは必要に応じて時々再編成され、メモリ空間の
利用を効率的にすることができる。廃物収集技術の概説
及び関連の背景部材についてはＪ．コーヘンによる「リ
ンク・データ構造の廃物収集」（コンピユーテイング・
サーベイ、第１３巻、第３号、第３４１頁〜第３６７
頁、１９８１年３月発行）に示されている。Ｐ．ビシヨ
ツプは「非常に大きなアドレス空間」（マサチユーセツ
ツ・インステイテユート・オブ・テクノロジー、研究論
文１１１、１９７５年発行）において非常に大きなアド
レス空間の廃物収集について述べている。
更に、廃物収集コストは再利用する廃物量と共に増加す
るのではなく、その空間の大きさに、よつて増加するの
で、仮想メモリの総合的な大きさはしばしば関心の的と
なる。
るのではなく、その空間の大きさに、よつて増加するの
で、仮想メモリの総合的な大きさはしばしば関心の的と
なる。
典型的なメモリ装置及び関連する中央処理装置（ＣＰ
Ｕ）の動作において、ＣＰＵは必要に応じてメモリの割
付けを要求する。メモリの割付けは仮想空間においてよ
く行なわれる。仮想アドレス空間が全部割付けられる
と、前に割付けた仮想アドレス空間において再使用可能
な空間が識別され、再利用されるまでは、付加的な空間
の要求を禁止する必要がある。
Ｕ）の動作において、ＣＰＵは必要に応じてメモリの割
付けを要求する。メモリの割付けは仮想空間においてよ
く行なわれる。仮想アドレス空間が全部割付けられる
と、前に割付けた仮想アドレス空間において再使用可能
な空間が識別され、再利用されるまでは、付加的な空間
の要求を禁止する必要がある。
「物理メモリ」とは、ここで用いているように、主メモ
リ、通常はＲＡＭ半導体素子と、バツクアツプ・メモ
リ、通常はページング・デイスクを含む実物理メモリを
意味する。「仮想アドレス空間」なる用語は、均一、線
形、かつ同質透明なメモリ空間を表わすために用いられ
る。
リ、通常はＲＡＭ半導体素子と、バツクアツプ・メモ
リ、通常はページング・デイスクを含む実物理メモリを
意味する。「仮想アドレス空間」なる用語は、均一、線
形、かつ同質透明なメモリ空間を表わすために用いられ
る。
一般に、本発明に関連する型式のメモリ装置において、
メモリの一部はＣＰＵにより指定された大きさの「複数
のブロツク」に割付けられる。各ブロツクは一つのヘツ
ダを有し、このヘツダには、例えばブロツクの識別、そ
の大きさ及びその他関連のものが含まれ、ブロツクに関
する種々の断片情報が含まれる。また、ブロツクのヘツ
ダには参照カウントを含むフイールドも含まれている。
あるブロツクの参照カウントは他のブロツクからこのブ
ロツク又はそれ自体に対する参照回数を表わすものであ
る。参照カウントの一形式はドイチユ他による「効果
的、増分的な自動廃物収集器」（ＣＡＣＭ、第１９巻、
第９号、第５２２頁〜第５２６頁、１９７６年９月発
行）に示されている。本発明の方法に関連する型式のメ
モリにおいて、あるブロツクが最初に割付けられたとき
は、参照カウントは０である。新しく参照を設定したと
きは、参照カウントを増加させる。ブロツク内の参照を
消去したときは、目標ブロツクの参照カウントを減少さ
せる。あるブロツクを新しく作成したときを除き、ブロ
ツクの参照カウントが０になつたときは、そのブロツク
は廃物であるとみなされ、そのブロツクの空間が再利用
可能となる。
メモリの一部はＣＰＵにより指定された大きさの「複数
のブロツク」に割付けられる。各ブロツクは一つのヘツ
ダを有し、このヘツダには、例えばブロツクの識別、そ
の大きさ及びその他関連のものが含まれ、ブロツクに関
する種々の断片情報が含まれる。また、ブロツクのヘツ
ダには参照カウントを含むフイールドも含まれている。
あるブロツクの参照カウントは他のブロツクからこのブ
ロツク又はそれ自体に対する参照回数を表わすものであ
る。参照カウントの一形式はドイチユ他による「効果
的、増分的な自動廃物収集器」（ＣＡＣＭ、第１９巻、
第９号、第５２２頁〜第５２６頁、１９７６年９月発
行）に示されている。本発明の方法に関連する型式のメ
モリにおいて、あるブロツクが最初に割付けられたとき
は、参照カウントは０である。新しく参照を設定したと
きは、参照カウントを増加させる。ブロツク内の参照を
消去したときは、目標ブロツクの参照カウントを減少さ
せる。あるブロツクを新しく作成したときを除き、ブロ
ツクの参照カウントが０になつたときは、そのブロツク
は廃物であるとみなされ、そのブロツクの空間が再利用
可能となる。
従来のメモリ管理装置においては、ブロツクが割付けら
れ、また割付け解除されるに従い、僅かなブロツクを含
むページをデイスクにページ・アウトしてブロツクの割
付け空間を更に確保することもよくあつた。ページ・ア
ウトしたブロツクをアクセスする必要が生じると、通
常、主メモリ内の付加的なあるページをページ・アウト
し、デイスクから転送するページの空間を作り出す必要
がある。次に、まばらに詰め込まれているページをデイ
スクから主メモリに転送し、必要としたブロツクを用い
た後、直ちにデイスクに書戻しを行なう。このような処
理は急速、かつ頻繁なデイスクのフエツチ及び書込み処
理を含む多数の「スラツシング(thrashing)」を生じ、
かつメモリの動作を非常に低下させるので、好ましくな
いことは明らかである。
れ、また割付け解除されるに従い、僅かなブロツクを含
むページをデイスクにページ・アウトしてブロツクの割
付け空間を更に確保することもよくあつた。ページ・ア
ウトしたブロツクをアクセスする必要が生じると、通
常、主メモリ内の付加的なあるページをページ・アウト
し、デイスクから転送するページの空間を作り出す必要
がある。次に、まばらに詰め込まれているページをデイ
スクから主メモリに転送し、必要としたブロツクを用い
た後、直ちにデイスクに書戻しを行なう。このような処
理は急速、かつ頻繁なデイスクのフエツチ及び書込み処
理を含む多数の「スラツシング(thrashing)」を生じ、
かつメモリの動作を非常に低下させるので、好ましくな
いことは明らかである。
必要なのは、頻繁に必要とするブロツクを収集し、圧縮
して記憶し、デイスクにペイジ・アウトし、かつ頻繁に
用いるブロツクを収集し、主メモリに保持してアクセス
の効率をよくすることにより、ブロツクを効率よく記憶
するメモリ管理方法である。
して記憶し、デイスクにペイジ・アウトし、かつ頻繁に
用いるブロツクを収集し、主メモリに保持してアクセス
の効率をよくすることにより、ブロツクを効率よく記憶
するメモリ管理方法である。
従来提案されたある方法として、バートレイ他により、
「独立した活性及び静止メモリ・ブロツクの仮想メモリ
管理方法」と題する米国同時係属出願、第６３４，３３
４号（１９８４年６月２４日出願、本出願人に譲渡）に
示されたものがある。この出願は複数のアドレス空間を
含む要求ページ仮想アドレス空間にメモリ・ブロツクを
圧縮する方法を開示している。この方法には、活性及び
静止ブロツクを識別し、設定したポインタＮと比較を
し、仮想メモリ空間のアドレスを表示し、そしてポイン
タＮを進め、利用可能な仮想メモリ空間の先頭アドレス
を連続的に表示する複数の処理が含まれいてる。新しい
ブロツクは、割付けられるに従い、歩進するポインタの
位置から開始する仮想アドレス空間に配置される。更
に、ブロツクはユーザにより参照されると、歩進するポ
インタの現在位置に転送されるので、活性ブロツクは活
性ページに収集される。
「独立した活性及び静止メモリ・ブロツクの仮想メモリ
管理方法」と題する米国同時係属出願、第６３４，３３
４号（１９８４年６月２４日出願、本出願人に譲渡）に
示されたものがある。この出願は複数のアドレス空間を
含む要求ページ仮想アドレス空間にメモリ・ブロツクを
圧縮する方法を開示している。この方法には、活性及び
静止ブロツクを識別し、設定したポインタＮと比較を
し、仮想メモリ空間のアドレスを表示し、そしてポイン
タＮを進め、利用可能な仮想メモリ空間の先頭アドレス
を連続的に表示する複数の処理が含まれいてる。新しい
ブロツクは、割付けられるに従い、歩進するポインタの
位置から開始する仮想アドレス空間に配置される。更
に、ブロツクはユーザにより参照されると、歩進するポ
インタの現在位置に転送されるので、活性ブロツクは活
性ページに収集される。
前記バートレイ他の特許出願における発明の特徴の一つ
は、各ページの利用範囲を決定し、ユーザが参照したブ
ロツクを配置しているページの利用範囲が所定レベル内
に含まれるときにのみ、ユーザが参照したブロツクを転
送することである。更に、デイスク・メモリを備え、か
つこれに対して収集した静止ブロツクを含むページの
「ページ・アウト」を周期的に行なう。
は、各ページの利用範囲を決定し、ユーザが参照したブ
ロツクを配置しているページの利用範囲が所定レベル内
に含まれるときにのみ、ユーザが参照したブロツクを転
送することである。更に、デイスク・メモリを備え、か
つこれに対して収集した静止ブロツクを含むページの
「ページ・アウト」を周期的に行なう。
前記バートレイ他の特許出願における更に他の特徴は、
関連ルツクアツプ・テーブルを備え、これに対して最終
的にページ・アウトをする特殊なページに転送されるブ
ロツク位置及びその識別を書込むことである。また、各
テーブル・エントリには識別した各ブロツクの参照カウ
ントが保持されている。関連ルツクアツプ・テーブルは
周期的に走査され、識別したブロツクの参照が更新され
る。
関連ルツクアツプ・テーブルを備え、これに対して最終
的にページ・アウトをする特殊なページに転送されるブ
ロツク位置及びその識別を書込むことである。また、各
テーブル・エントリには識別した各ブロツクの参照カウ
ントが保持されている。関連ルツクアツプ・テーブルは
周期的に走査され、識別したブロツクの参照が更新され
る。
（発明の簡単な説明） 以上の点から、本発明の目的は、デイスクの待ち時間及
び頻繁な廃物収集の再にＣＰＵが遅れる時間を減少させ
ることにより、メモリにおけるデータの総合的なスルー
・プツトを改善するページ要求仮想メモリのメモリ管理
方法を提供することにある。
び頻繁な廃物収集の再にＣＰＵが遅れる時間を減少させ
ることにより、メモリにおけるデータの総合的なスルー
・プツトを改善するページ要求仮想メモリのメモリ管理
方法を提供することにある。
本発明の他の目的は、割付け応答時間を改善する説明し
た型式の方法を提供することにある。
た型式の方法を提供することにある。
本発明の他の目的は、まばらに割付けたページをデイス
クに書出すことなく、バツクアツプ・メモリの効率的な
利用を可能にする説明した型式の方法を提供することに
ある。
クに書出すことなく、バツクアツプ・メモリの効率的な
利用を可能にする説明した型式の方法を提供することに
ある。
この発明の他の目的は、利用率が低いページに順方向に
ブロツクを割付けかつ複写することにより、あるページ
をバツクアツプ・メモリにページ・アウトする必要性を
延期させることにある。
ブロツクを割付けかつ複写することにより、あるページ
をバツクアツプ・メモリにページ・アウトする必要性を
延期させることにある。
これら及び他の目的、特徴並びに効果は、付図及び特許
請求の範囲と関連させて以下の詳細な説明を読むことに
より、当該技術に習熟する者にとり明らかとなるであろ
う。
請求の範囲と関連させて以下の詳細な説明を読むことに
より、当該技術に習熟する者にとり明らかとなるであろ
う。
本発明は、その広範な観点において、固定された複数の
仮想アドレス・ページと、情報のブロツクを書込む固定
数の物理メモリ・ページとを備えた要求ページ仮想アド
レス空間にメモリ・ブロツクを圧縮し、かつメモリから
ページ・アウトしたページを含むバツクアツプ・メモリ
を有する方法を提供する。この方法は、ポインタＮを決
定して前記仮想メモリ空間のページを表示する処理と、
ポインタを進めて割付け用に利用可能な仮想ページを連
続的に表示する処理とからなる。新しいブロツクは、割
付けられると、歩進するポインタにより指示されたペー
ジに利用可能な次の仮想アドレスに配置される。更に、
ブロツクはユーザにより参照されると、ポインタＮの前
記ページ上で利用可能な次の仮想アドレスに転送される
ので、活性ブロツク（以下で説明する）を活性ページに
収集する。ブロツク割付け要求又は前記ページの活性ブ
ロツクを転送するため、ポインタＮの前記ページに適当
な空間がないときは、物理メモリにおける他のページに
位置を見付ける。物理メモリにおける全ページに前記ブ
ロツクに適当な空間がないときは、仮想ページを物理メ
モリからバツクアツプ・メモリに転送した後、解放され
た物理メモリを用いて利用可能な次の仮想アドレス・ペ
ージに進む。
仮想アドレス・ページと、情報のブロツクを書込む固定
数の物理メモリ・ページとを備えた要求ページ仮想アド
レス空間にメモリ・ブロツクを圧縮し、かつメモリから
ページ・アウトしたページを含むバツクアツプ・メモリ
を有する方法を提供する。この方法は、ポインタＮを決
定して前記仮想メモリ空間のページを表示する処理と、
ポインタを進めて割付け用に利用可能な仮想ページを連
続的に表示する処理とからなる。新しいブロツクは、割
付けられると、歩進するポインタにより指示されたペー
ジに利用可能な次の仮想アドレスに配置される。更に、
ブロツクはユーザにより参照されると、ポインタＮの前
記ページ上で利用可能な次の仮想アドレスに転送される
ので、活性ブロツク（以下で説明する）を活性ページに
収集する。ブロツク割付け要求又は前記ページの活性ブ
ロツクを転送するため、ポインタＮの前記ページに適当
な空間がないときは、物理メモリにおける他のページに
位置を見付ける。物理メモリにおける全ページに前記ブ
ロツクに適当な空間がないときは、仮想ページを物理メ
モリからバツクアツプ・メモリに転送した後、解放され
た物理メモリを用いて利用可能な次の仮想アドレス・ペ
ージに進む。
（好ましい実施態様の詳細な説明） オン・ザ・フライ（ＯＴＦ）の圧縮には効率的なメモリ
管理に関する多くの要求が伴う。これには、デイスクの
無駄な待ち時間及び頻繁な廃物収集の際にＣＰＵを遅延
させる時間を減少させることにより、総合的なスループ
ツトを改善させる要求が含まれる。また、まばらに割付
けられたページを書出さずに、割付応答時間を改善する
必要性及びバツクアツプ・メモリを更に効率よく利用す
る必要性も関連してくる。最後に、ダイナミツク及び静
的なワーキング・セツト（以下で説明する）の両方を最
小化する必要性も関連している。
管理に関する多くの要求が伴う。これには、デイスクの
無駄な待ち時間及び頻繁な廃物収集の際にＣＰＵを遅延
させる時間を減少させることにより、総合的なスループ
ツトを改善させる要求が含まれる。また、まばらに割付
けられたページを書出さずに、割付応答時間を改善する
必要性及びバツクアツプ・メモリを更に効率よく利用す
る必要性も関連してくる。最後に、ダイナミツク及び静
的なワーキング・セツト（以下で説明する）の両方を最
小化する必要性も関連している。
この発明は第１図にブロツク化して示されており、メモ
リにおける仮想アドレス空間内の領域Ｘ（前記ビシヨツ
プの意味において）が示されている。この概念の説明を
簡単にするため、ＯＴＦの圧縮を一つのメモリの領域Ｘ
に関連させて説明する。与えられた任意の時点で１以上
の領域が活性であつてもよいが、明確にするため、ここ
では一領域についてのみ説明する。通常、物理メモリ、
バツクアツプ・メモリ等は利用可能な資源からなるこの
ような領域を含んでいる。
リにおける仮想アドレス空間内の領域Ｘ（前記ビシヨツ
プの意味において）が示されている。この概念の説明を
簡単にするため、ＯＴＦの圧縮を一つのメモリの領域Ｘ
に関連させて説明する。与えられた任意の時点で１以上
の領域が活性であつてもよいが、明確にするため、ここ
では一領域についてのみ説明する。通常、物理メモリ、
バツクアツプ・メモリ等は利用可能な資源からなるこの
ような領域を含んでいる。
仮想アドレス空間１０は、先頭点１１から開始し、かつ
領域Ｘの長さを連続する同質のアドレス・セツトにより
表わされる。通常、仮想アドレス空間を視察すると、異
なる型式のブロツクを見出すことができる。これらは、
活性ブロツク、静止ブロツク及び廃物ブロツクである。
活性ブロツクはＣＰＵが能動的に参照を行なうブロツク
である。活性ブロツクは、短寿命であるという意味で
「揮発性」であるといえる。即ち、ＣＰＵは活性ブロツ
クを割付け、短期間これを用いて廃棄をする。静止ブロ
ツクはＣＰＵへアクセス可能であるが、比較的長期間必
要とされない、即ちアクセスされることがないブロツク
である。廃物ブロツクはＣＰＵにこれ以上アクセスでき
ないが、その参照カウントは０になつていないブロツク
である。あるブロツクの参照カウントは、他のブロツク
又はそれ自身により当該ブロツクに対する参照数を表わ
している。最初にあるブロツクが割付けられたときは、
その参照カウントは１であり、新しい参照を確立する度
に、その参照カウントは増加される。あるブロツク内の
参照を破壊したときは、当該ブロツクの参照カウントを
減少させる。参照カウントは廃物収集処理において特に
有用であり、例えば「関連するプロセツサから独立した
並列廃物収集をするコンピユータ・メモリ装置」と題
し、本人出願人に譲渡され、ここで背景技術として参照
される１９８４年６月３１日出願の米国同時係属出願第
６３６，１８７号を参照することができる。
領域Ｘの長さを連続する同質のアドレス・セツトにより
表わされる。通常、仮想アドレス空間を視察すると、異
なる型式のブロツクを見出すことができる。これらは、
活性ブロツク、静止ブロツク及び廃物ブロツクである。
活性ブロツクはＣＰＵが能動的に参照を行なうブロツク
である。活性ブロツクは、短寿命であるという意味で
「揮発性」であるといえる。即ち、ＣＰＵは活性ブロツ
クを割付け、短期間これを用いて廃棄をする。静止ブロ
ツクはＣＰＵへアクセス可能であるが、比較的長期間必
要とされない、即ちアクセスされることがないブロツク
である。廃物ブロツクはＣＰＵにこれ以上アクセスでき
ないが、その参照カウントは０になつていないブロツク
である。あるブロツクの参照カウントは、他のブロツク
又はそれ自身により当該ブロツクに対する参照数を表わ
している。最初にあるブロツクが割付けられたときは、
その参照カウントは１であり、新しい参照を確立する度
に、その参照カウントは増加される。あるブロツク内の
参照を破壊したときは、当該ブロツクの参照カウントを
減少させる。参照カウントは廃物収集処理において特に
有用であり、例えば「関連するプロセツサから独立した
並列廃物収集をするコンピユータ・メモリ装置」と題
し、本人出願人に譲渡され、ここで背景技術として参照
される１９８４年６月３１日出願の米国同時係属出願第
６３６，１８７号を参照することができる。
ＯＴＦ圧縮器の第１の目的は物理メモリに最も活性なブ
ロツクを保持することである。従つて、以下明らかとな
るように、静止ブロツクは物理メモリに空間が得られな
い限り、静止ブロツクは最終的にバツクアツプ・メモリ
に配置される。
ロツクを保持することである。従つて、以下明らかとな
るように、静止ブロツクは物理メモリに空間が得られな
い限り、静止ブロツクは最終的にバツクアツプ・メモリ
に配置される。
仮想メモリには要求ページングを用いるのが望ましいの
で、各ページは同一型式（活性、静止又は廃物）ブロツ
クを保持するのが都合がよい。従つて、ページを選択的
にメモリ（全部活性）に配置、ページ・アウト（全部静
止）、又は再利用（全て廃物）することができる。
で、各ページは同一型式（活性、静止又は廃物）ブロツ
クを保持するのが都合がよい。従つて、ページを選択的
にメモリ（全部活性）に配置、ページ・アウト（全部静
止）、又は再利用（全て廃物）することができる。
与えられた任意時点にいて、「ダイナミツク・ワーキン
グ・セツト」とここで呼ぶ活性ブロツクを含む仮想アド
レス・ページのセツトがその装置の物理メモリより小さ
いときは理想的である。更に、ここで「スタティックワ
ーキング・セツト」と呼ぶ静止及び活性ブロツクを含む
仮想アドレス・ページのセツトが可能な限り小さいとき
も理想的となり、またそのセツトが当該装置のバツクア
ツプ・メモリより小さいということも重要である。
グ・セツト」とここで呼ぶ活性ブロツクを含む仮想アド
レス・ページのセツトがその装置の物理メモリより小さ
いときは理想的である。更に、ここで「スタティックワ
ーキング・セツト」と呼ぶ静止及び活性ブロツクを含む
仮想アドレス・ページのセツトが可能な限り小さいとき
も理想的となり、またそのセツトが当該装置のバツクア
ツプ・メモリより小さいということも重要である。
活性ブロツクを「活性」ページに統合するために、ある
参照にてブロツクは「複写され、又は順方向に転送」さ
れる。従つて、例えばデータをアクセスするために、ブ
ロツクをアクセスするときは、ブロツクを活性ページへ
順方向に転送する。従つて、「古い」ページは静的かつ
廃物ブロツクのみを含む傾向があり、選択的にページ・
アウトすることができる。その結果、活性ブロツクは統
合され、またいくつかの廃物は識別されて再利用され
る。ページ・アウト処理において、全ての廃物ブロツク
が識別されるものでないことに注目すべきである。廃物
収集（ＧＣ）は最終的に要求され、残りの廃物ブロツク
を削除するようにするものでもよい。
参照にてブロツクは「複写され、又は順方向に転送」さ
れる。従つて、例えばデータをアクセスするために、ブ
ロツクをアクセスするときは、ブロツクを活性ページへ
順方向に転送する。従つて、「古い」ページは静的かつ
廃物ブロツクのみを含む傾向があり、選択的にページ・
アウトすることができる。その結果、活性ブロツクは統
合され、またいくつかの廃物は識別されて再利用され
る。ページ・アウト処理において、全ての廃物ブロツク
が識別されるものでないことに注目すべきである。廃物
収集（ＧＣ）は最終的に要求され、残りの廃物ブロツク
を削除するようにするものでもよい。
メモリ管理の通常動作においては、２型式の事象が頻繁
に発生する。これらはＣＰＵが将来利用する新しいブロ
ツクの割付けと、ＣＰＵはこれ以上参照することはない
ということによつて示されるもので、ＣＰＵにとり最早
無用のブロツクの再利用とがある。これらの２事象の頻
度は理想的な場合、等しい。静的なワーキング・セツト
により再利用される全てのブロツクには付加された新し
いブロツクがある。従つて、静的なワーキング・セツト
の大きさは比較的一定となつている。
に発生する。これらはＣＰＵが将来利用する新しいブロ
ツクの割付けと、ＣＰＵはこれ以上参照することはない
ということによつて示されるもので、ＣＰＵにとり最早
無用のブロツクの再利用とがある。これらの２事象の頻
度は理想的な場合、等しい。静的なワーキング・セツト
により再利用される全てのブロツクには付加された新し
いブロツクがある。従つて、静的なワーキング・セツト
の大きさは比較的一定となつている。
廃物収集をしていないときは、参照カウントが廃棄した
ブロツクを再利用する唯一の手段である。あるブロツク
の参照カウントが０となつたためにそのブロツクが再利
用されたときは、そのブロツクが存在する仮想アドレス
・ページの一部は空きであり、従つてこれを再利用可能
なページ断片と考えてよい。いくつかのブロツクを再利
用した後は、いくつかのページ断片がいくつかのページ
に存在し得る。本発明によれば、これらのページ断片の
トラツキングを保持する機構を備えることにより、これ
らのページ断片を位置として用い、新しいブロツク、及
び（以下で説明するように）活性ブロツクと判断された
「順方向複写」ブロツクを割付けることができる。これ
により、アクセス可能なブロツクを参照する場所が全く
分散してしまうという問題が回避される。頻繁に参照さ
れ、かつ互いに密接に関連されるブロツクは、物理メモ
リとして存在するページよりも遥かに多い仮想アドレス
・ページに分散可能とされる。この結果、ひどいスラツ
シユ、即ち頻繁なページ・イン、ページ・アウト又はデ
イスク・アクセスとなる。
ブロツクを再利用する唯一の手段である。あるブロツク
の参照カウントが０となつたためにそのブロツクが再利
用されたときは、そのブロツクが存在する仮想アドレス
・ページの一部は空きであり、従つてこれを再利用可能
なページ断片と考えてよい。いくつかのブロツクを再利
用した後は、いくつかのページ断片がいくつかのページ
に存在し得る。本発明によれば、これらのページ断片の
トラツキングを保持する機構を備えることにより、これ
らのページ断片を位置として用い、新しいブロツク、及
び（以下で説明するように）活性ブロツクと判断された
「順方向複写」ブロツクを割付けることができる。これ
により、アクセス可能なブロツクを参照する場所が全く
分散してしまうという問題が回避される。頻繁に参照さ
れ、かつ互いに密接に関連されるブロツクは、物理メモ
リとして存在するページよりも遥かに多い仮想アドレス
・ページに分散可能とされる。この結果、ひどいスラツ
シユ、即ち頻繁なページ・イン、ページ・アウト又はデ
イスク・アクセスとなる。
本発明のＯＴＦ構造はブロツクの割付け及び除去を管理
するものである。図示のように、ここではＮと呼び、歩
進するポインタにより指示された仮想アドレス・ページ
に新しいブロツクを割付ける。このページにブロツクが
割付けられたときは、そのページの未利用部分のうちの
次に利用可能なアドレスにこのブロツクを配置する。従
つて、第１図に示すように、ポインタＮにより指示され
たページにおいて次に利用可能なアドレスからそれぞれ
開始する仮想アドレス空間に逐次Ｂ１〜Ｂ１３により表
わすブロツクを配置する。更に、本発明によれば、ペー
ジからブロツクを除去したときは、空きになつたポイン
タＮにおけるページ部分を再利用しようとすることはし
ない。
するものである。図示のように、ここではＮと呼び、歩
進するポインタにより指示された仮想アドレス・ページ
に新しいブロツクを割付ける。このページにブロツクが
割付けられたときは、そのページの未利用部分のうちの
次に利用可能なアドレスにこのブロツクを配置する。従
つて、第１図に示すように、ポインタＮにより指示され
たページにおいて次に利用可能なアドレスからそれぞれ
開始する仮想アドレス空間に逐次Ｂ１〜Ｂ１３により表
わすブロツクを配置する。更に、本発明によれば、ペー
ジからブロツクを除去したときは、空きになつたポイン
タＮにおけるページ部分を再利用しようとすることはし
ない。
ポインタＮにより指示されたページがフルとなる度に、
ポインタＮを次に高い又は大きい仮想アドレス・ページ
のポイントへ更新するという意味では、ポインタＮは
「歩進」している。その領域の最大の仮想アドレス・ペ
ージがフルとなると、廃物収集が呼び出される。
ポインタＮを次に高い又は大きい仮想アドレス・ページ
のポイントへ更新するという意味では、ポインタＮは
「歩進」している。その領域の最大の仮想アドレス・ペ
ージがフルとなると、廃物収集が呼び出される。
ブロツクの割付けはＣＰＵの要求に応答して発生する頻
繁な事象のうちの一つのものに過ぎない。また、ブロツ
クの参照カウントが０になると、動的及び静的なワーキ
ング・セツトからなるページによつてもブロツクが再利
用される。従つて、第２図に示すようにブロツクＢ１〜
Ｂ１３を割付けている間にあるブロツクも割付け解除さ
れている。例えば、図示の場合はブロツクＢ８，Ｂ９，
Ｂ１２及びＢ１３を割付け解除し、再利用する。仮想ア
ドレス・ページの一つのブロツクを再利用する度に、そ
の情報は以下において説明するように、利用可能断片リ
ストに示される。更に、そのページの使用が減少する。
どの程度までページを利用しているかは、ページの各制
御構造の一部として正しく保持される重要なパラメータ
である。空の仮想アドレス・ページをまず物理メモリに
転送したときは、そのページの利用率は明らかに０であ
る。ブロツクをページに割付ける度に、ページの利用率
が適当に増大する。同一の理由により、ブロックがペー
ジから回収される度に、そのページの利用率は減少す
る。
繁な事象のうちの一つのものに過ぎない。また、ブロツ
クの参照カウントが０になると、動的及び静的なワーキ
ング・セツトからなるページによつてもブロツクが再利
用される。従つて、第２図に示すようにブロツクＢ１〜
Ｂ１３を割付けている間にあるブロツクも割付け解除さ
れている。例えば、図示の場合はブロツクＢ８，Ｂ９，
Ｂ１２及びＢ１３を割付け解除し、再利用する。仮想ア
ドレス・ページの一つのブロツクを再利用する度に、そ
の情報は以下において説明するように、利用可能断片リ
ストに示される。更に、そのページの使用が減少する。
どの程度までページを利用しているかは、ページの各制
御構造の一部として正しく保持される重要なパラメータ
である。空の仮想アドレス・ページをまず物理メモリに
転送したときは、そのページの利用率は明らかに０であ
る。ブロツクをページに割付ける度に、ページの利用率
が適当に増大する。同一の理由により、ブロックがペー
ジから回収される度に、そのページの利用率は減少す
る。
利用可能な断片２５のリスト（第２図参照）が保持され
るが、なぜこのブロツクの再利用の際に解放される断片
のリストを保持し、次いで解放された断片を利用するこ
とが望ましいのかについては、いくつかの理由がある。
ブロツクの割付けはＮにより指示されたページではな
く、ページにある断片により行なわれる。更に、廃物収
集アルゴリズムにより空きとなつた断片の位置を知る効
果も得られる。
るが、なぜこのブロツクの再利用の際に解放される断片
のリストを保持し、次いで解放された断片を利用するこ
とが望ましいのかについては、いくつかの理由がある。
ブロツクの割付けはＮにより指示されたページではな
く、ページにある断片により行なわれる。更に、廃物収
集アルゴリズムにより空きとなつた断片の位置を知る効
果も得られる。
どのようにしてこのような情報を保持できるかについて
はいくつかの可能性がある。例えば、各領域に対して
「利用可能リスト」（図示なし）を保持してもよい。結
合されたリストの各交点には仮想アドレス及び利用可能
な（空きの）断片の大きさが設定されている。各断片
は、割付けられる度にこれに対応してリストから削除さ
れる。逆に、断片が再利用される度に、適当な情報がリ
ストに登録される。
はいくつかの可能性がある。例えば、各領域に対して
「利用可能リスト」（図示なし）を保持してもよい。結
合されたリストの各交点には仮想アドレス及び利用可能
な（空きの）断片の大きさが設定されている。各断片
は、割付けられる度にこれに対応してリストから削除さ
れる。逆に、断片が再利用される度に、適当な情報がリ
ストに登録される。
空き断片の知識を保持することが可能な他の方法は、全
部空きか、又は全部空きではない各ページに対し、第２
図に示すように利用可能な断片を保持することである。
断片は連続していなければならないということ以外に、
ブロツク割付け（多重領域ブロツクを除く）に課せられ
る条件の一つとして、ブロツクを形成する断片は同一ペ
ージに配置されるということがある。ページ可能断片リ
ストによるページはこの制限を満足させる適当な情報を
保持している。
部空きか、又は全部空きではない各ページに対し、第２
図に示すように利用可能な断片を保持することである。
断片は連続していなければならないということ以外に、
ブロツク割付け（多重領域ブロツクを除く）に課せられ
る条件の一つとして、ブロツクを形成する断片は同一ペ
ージに配置されるということがある。ページ可能断片リ
ストによるページはこの制限を満足させる適当な情報を
保持している。
ブロツクを再利用した後、断片が空きとなつたときは、
この情報はリスト２５に反映されなければならない。存
在する２つの現存ノード間に仮想アドレスが存在してい
る断片は、この現存ノード間の一つのノードに配置され
る。リストの大きさをできる限り小さく、かつ断片を可
能な限り大きくするために、リスト上のノードは可能な
らば何時でも組合される。
この情報はリスト２５に反映されなければならない。存
在する２つの現存ノード間に仮想アドレスが存在してい
る断片は、この現存ノード間の一つのノードに配置され
る。リストの大きさをできる限り小さく、かつ断片を可
能な限り大きくするために、リスト上のノードは可能な
らば何時でも組合される。
空きとなつた断面の知識を保持する同様の他の方法は、
各ページの制御構造情報の一部として一つのビツト・マ
ツプ（図示なし）を備えることである。利用可能な断片
はビツト・マツプにおいて連続する０により表わされ
る。断片が割付けられたときは、ビツト・マツプにおい
てそれらに対応する標識は１に変更される。
各ページの制御構造情報の一部として一つのビツト・マ
ツプ（図示なし）を備えることである。利用可能な断片
はビツト・マツプにおいて連続する０により表わされ
る。断片が割付けられたときは、ビツト・マツプにおい
てそれらに対応する標識は１に変更される。
物理的なページの数が有限であることは、理解できるで
あろう。更に、ポインタＮが歩進するに従い、新しいブ
ロツクを割付けるためには新しいページが必要である。
任意ページをそれに存在するものに関係なく、ページ・
アウトをすることは共通である。しかし、十分に利用さ
れていないページをページ・アウトすること、即ち利用
率が相当に減少したページはデイスク空間を効率よく用
いることにならない。更に、物理メモリに残つている仮
想アドレス・ページに活性ブロツクがうまく配置される
ので、活性ブロツクをデイスクに転送するのは工合が悪
い。
あろう。更に、ポインタＮが歩進するに従い、新しいブ
ロツクを割付けるためには新しいページが必要である。
任意ページをそれに存在するものに関係なく、ページ・
アウトをすることは共通である。しかし、十分に利用さ
れていないページをページ・アウトすること、即ち利用
率が相当に減少したページはデイスク空間を効率よく用
いることにならない。更に、物理メモリに残つている仮
想アドレス・ページに活性ブロツクがうまく配置される
ので、活性ブロツクをデイスクに転送するのは工合が悪
い。
本発明の方法は、デイスク空間を効率よく利用し、かつ
物理メモリに活性ブロツクを保持するため、既に説明し
たように、物理メモリにある仮想ページに既に又は間も
なくページ・アウトされ、まばらに利用されているペー
ジに存在する活性ブロツクを再配置するものである。新
しいブロツクが割当られたポインタＮのページは、物理
メモリに存在するもので、ダイナミツク・ワーキング・
セトの一部である。従つて、このページはある基準を満
足する全ての活性ブロツクを再配置するために理想的な
配置となる。
物理メモリに活性ブロツクを保持するため、既に説明し
たように、物理メモリにある仮想ページに既に又は間も
なくページ・アウトされ、まばらに利用されているペー
ジに存在する活性ブロツクを再配置するものである。新
しいブロツクが割当られたポインタＮのページは、物理
メモリに存在するもので、ダイナミツク・ワーキング・
セトの一部である。従つて、このページはある基準を満
足する全ての活性ブロツクを再配置するために理想的な
配置となる。
ある活性ブロツクを再配置又は順方向に複写をするため
の第１の判断基準は、このブロツクがＣＰＵにより参照
されることである。（あるブロツクを参照することは、
静止ブロツクから活性ブロツクを識別するための唯一の
方法である。）第２の判断基準として、活性ブロツクが
ポイントＮのページに既に配置されていないことであ
る。（この第２の判断基準は何も得られないので、ポイ
ントＮにてページのブロツクは順方向に複写されていな
いことを意味する）。第３の判断基準は、バツクアツプ
・メモリを効率よく用いることに関連するもので、利用
効率があるしきい値以下になつたページに活性ブロツク
が配置されていることである。完全に利用されているペ
ージは、物理メモリにあり、他のページを持つて来るこ
とができるようにページ・アウトされなければならない
ものであつてもそのまゝ残される。そのページがまばら
でないということは、デイスク空間の利用を効率的なも
のにする。残念ながらこの結果、ダイナミツク・ワーキ
ング・セツトから活性ブロツク（同一ページに他の活性
ブロツク７があるかも知れない。）を転送する結果とな
る。
の第１の判断基準は、このブロツクがＣＰＵにより参照
されることである。（あるブロツクを参照することは、
静止ブロツクから活性ブロツクを識別するための唯一の
方法である。）第２の判断基準として、活性ブロツクが
ポイントＮのページに既に配置されていないことであ
る。（この第２の判断基準は何も得られないので、ポイ
ントＮにてページのブロツクは順方向に複写されていな
いことを意味する）。第３の判断基準は、バツクアツプ
・メモリを効率よく用いることに関連するもので、利用
効率があるしきい値以下になつたページに活性ブロツク
が配置されていることである。完全に利用されているペ
ージは、物理メモリにあり、他のページを持つて来るこ
とができるようにページ・アウトされなければならない
ものであつてもそのまゝ残される。そのページがまばら
でないということは、デイスク空間の利用を効率的なも
のにする。残念ながらこの結果、ダイナミツク・ワーキ
ング・セツトから活性ブロツク（同一ページに他の活性
ブロツク７があるかも知れない。）を転送する結果とな
る。
従つて、第４の基準は、有用なことが証明できると思わ
れる。最小のオーバヘツドを有する最終使用（ＬＲＵ）
の実行により決定された、十分に「古」いページに活性
ブロツクを配置したときは、そのページの利用率に関係
なく、この活性ブロツクが複写される。これは、実際上
ダイナミツク・ワーキング・セツトに活性ブロツクを保
持し、またページの利用率の低下を「遮断」することに
なる。
れる。最小のオーバヘツドを有する最終使用（ＬＲＵ）
の実行により決定された、十分に「古」いページに活性
ブロツクを配置したときは、そのページの利用率に関係
なく、この活性ブロツクが複写される。これは、実際上
ダイナミツク・ワーキング・セツトに活性ブロツクを保
持し、またページの利用率の低下を「遮断」することに
なる。
活性ブロツクの再割付けは、ブロツクＢ１をアクセスす
る第２図に示されている。ブロツクＢ１はポインタＮに
より指示されたページに配置されないが、余り利用され
ていないページに配置される。従つて、このページは仮
想アドレス・ページ４に（Ｎが進むに従つて）順方向に
複写される。ブロツクＢ１の古い位置は複写ブロツクに
対するポイントに適宜更新される。ブロツクＢ１を参照
する他のブロツク（図示なし）は、（仮想アドレス・ペ
ージ１に）ブロツクＢ１の古い複写をまだ保持している
ので、ブロツクＢ１の古い位置に順方向のポインタを残
すことが必要となる。第２図に示すように、同様な方法
により、ブロツクＢ４，Ｂ６，Ｂ７及びＢ１０は、ポイ
ンタＮが進むに従つて位置を参照するので、順方向に複
写される。順方向ポインタが残留していることを除き、
ブロツクが順方向に複写されるに従いそれらのアドレス
は利用可能断片リスト２５に登録されることが解る。
る第２図に示されている。ブロツクＢ１はポインタＮに
より指示されたページに配置されないが、余り利用され
ていないページに配置される。従つて、このページは仮
想アドレス・ページ４に（Ｎが進むに従つて）順方向に
複写される。ブロツクＢ１の古い位置は複写ブロツクに
対するポイントに適宜更新される。ブロツクＢ１を参照
する他のブロツク（図示なし）は、（仮想アドレス・ペ
ージ１に）ブロツクＢ１の古い複写をまだ保持している
ので、ブロツクＢ１の古い位置に順方向のポインタを残
すことが必要となる。第２図に示すように、同様な方法
により、ブロツクＢ４，Ｂ６，Ｂ７及びＢ１０は、ポイ
ンタＮが進むに従つて位置を参照するので、順方向に複
写される。順方向ポインタが残留していることを除き、
ブロツクが順方向に複写されるに従いそれらのアドレス
は利用可能断片リスト２５に登録されることが解る。
あるブロツクが前記基準を満足し、順方向に複写される
ものであるときは、このブロツクの参照カウントをまず
調べる。参照カウントの１はＣＰＵがバインデイング・
レジスタを用いた、又は多分用いたブロツク・セル以外
のブロツクを参照していないことを意味する（１９８４
年６月３１日出願の米国同時係属出願第６３６，１８７
号を参照）。従つて、ブロツクを複写し、これを参照し
た対象（セル又はバインデイング・レジスタ）を更新し
た後、ブロツクが新しい位置を指示するので、参照した
ブロツクの原複写を再利用することができる。そのとき
は、ブロツクの原複写を有するページの利用率が減少す
る。
ものであるときは、このブロツクの参照カウントをまず
調べる。参照カウントの１はＣＰＵがバインデイング・
レジスタを用いた、又は多分用いたブロツク・セル以外
のブロツクを参照していないことを意味する（１９８４
年６月３１日出願の米国同時係属出願第６３６，１８７
号を参照）。従つて、ブロツクを複写し、これを参照し
た対象（セル又はバインデイング・レジスタ）を更新し
た後、ブロツクが新しい位置を指示するので、参照した
ブロツクの原複写を再利用することができる。そのとき
は、ブロツクの原複写を有するページの利用率が減少す
る。
順方向に複写されたブロツクの参照カウントが１より大
きいときは、更に、ブロツクを参照する他の対象がブロ
ツクの新しい位置を見付け出すことができるように、ブ
ロツクの原複写の位置に順方向の参照を残す必要があ
る。ブロツクの原位置に順方向の参照を最初に配置した
ときは、ブロツクに対する他の全ての参照がブロツクの
古い位置を知るのみであり、従つて順方向の参照を実際
に参照しているために、原ブロツクから１を減算した参
照カウントに進む。新しい位置に複写されたブロツクに
は、ブロツクを参照した目標に順方向の複写をさせるも
のと、ブロツクに対して順方向参照させるものとの２つ
の参照が与えられる。その後、ある対象が順方向の参照
に遭遇したときは、この対象は新しいブロツク位置のポ
イントに更新され、対象の参照減として順方向の参照カ
ウントを１だけ減少させ、また対象からのポインタとし
て新しい位置のブロツクの参照カウントを１だけ増加さ
せる。順方向参照の参照カウントは、０になつたとき
は、ポイントを１だけ減少させたブロツクの参照カウン
トに従い、再利用することができる。
きいときは、更に、ブロツクを参照する他の対象がブロ
ツクの新しい位置を見付け出すことができるように、ブ
ロツクの原複写の位置に順方向の参照を残す必要があ
る。ブロツクの原位置に順方向の参照を最初に配置した
ときは、ブロツクに対する他の全ての参照がブロツクの
古い位置を知るのみであり、従つて順方向の参照を実際
に参照しているために、原ブロツクから１を減算した参
照カウントに進む。新しい位置に複写されたブロツクに
は、ブロツクを参照した目標に順方向の複写をさせるも
のと、ブロツクに対して順方向参照させるものとの２つ
の参照が与えられる。その後、ある対象が順方向の参照
に遭遇したときは、この対象は新しいブロツク位置のポ
イントに更新され、対象の参照減として順方向の参照カ
ウントを１だけ減少させ、また対象からのポインタとし
て新しい位置のブロツクの参照カウントを１だけ増加さ
せる。順方向参照の参照カウントは、０になつたとき
は、ポイントを１だけ減少させたブロツクの参照カウン
トに従い、再利用することができる。
利用可能な物理メモリの不足によりバツクアツプ・メモ
リを絶対的に必要とするものでない限り、バツクアツプ
・メモリに物理メモリにおけるあるページをページ・ア
ウトすることは避けることが望ましい。従つて、本発明
によれば、ブロツク割付けの要求又は活性ブロツクを順
方向に複写する必要があるとき、またポイントＮのペー
ジがブロツクの加算に適合しないときは、このブロツク
は順方向に複写、又は可能ならば物理メモリにおける他
のページに割付けられる。どのページがブロツクの候補
として適当であるかの選択は、最低の利用率にあるペー
ジの選択と組合せた最新使用（ＭＲＵ）アルゴリズムに
従つてあるページを選択することにより達成可能であ
る。ＭＲＵアルゴリズムは相当な可能性をもつて活性ペ
ージとされるべきページを表示し、一方余り利用してい
ないページは１以上の有力な活性ブロツクを最大の可能
性をもつて適応可能となる。そのときは、そのページの
利用可能断片リストは、第１適合又は最適合を用いてブ
ロツクの配置が可能な位置を表示することになる。前記
アルゴリズムの全ては当該技術において公知であり、こ
こで詳細に説明はしない。
リを絶対的に必要とするものでない限り、バツクアツプ
・メモリに物理メモリにおけるあるページをページ・ア
ウトすることは避けることが望ましい。従つて、本発明
によれば、ブロツク割付けの要求又は活性ブロツクを順
方向に複写する必要があるとき、またポイントＮのペー
ジがブロツクの加算に適合しないときは、このブロツク
は順方向に複写、又は可能ならば物理メモリにおける他
のページに割付けられる。どのページがブロツクの候補
として適当であるかの選択は、最低の利用率にあるペー
ジの選択と組合せた最新使用（ＭＲＵ）アルゴリズムに
従つてあるページを選択することにより達成可能であ
る。ＭＲＵアルゴリズムは相当な可能性をもつて活性ペ
ージとされるべきページを表示し、一方余り利用してい
ないページは１以上の有力な活性ブロツクを最大の可能
性をもつて適応可能となる。そのときは、そのページの
利用可能断片リストは、第１適合又は最適合を用いてブ
ロツクの配置が可能な位置を表示することになる。前記
アルゴリズムの全ては当該技術において公知であり、こ
こで詳細に説明はしない。
別の（ポインタＮではない）ページにブロツクを割付け
て順方向に複写することは、第３図に示されている。例
えば、別のページとしてページ２を選択したものと仮定
する。従つて、ブロツクは、ＣＰＵにより参照されたと
きはその順方向に複写される。図示のように、ブロツク
Ｂ３及びＢ７は順方向に複写される。更に、新しく割付
けられたブロツクＢ１８はページ２に割付けられる。順
方向の複写や割付の処理において、ページ２のブロック
の位置について利用可能断片リスト２５への参照がなさ
れる。
て順方向に複写することは、第３図に示されている。例
えば、別のページとしてページ２を選択したものと仮定
する。従つて、ブロツクは、ＣＰＵにより参照されたと
きはその順方向に複写される。図示のように、ブロツク
Ｂ３及びＢ７は順方向に複写される。更に、新しく割付
けられたブロツクＢ１８はページ２に割付けられる。順
方向の複写や割付の処理において、ページ２のブロック
の位置について利用可能断片リスト２５への参照がなさ
れる。
本発明によれば、ポインタＮにおけるページにおいて利
用可能な空間より大きなブロツクを割付けなければなら
ず、また新しいブロツクと適合するのに十分な大きさの
物理メモリに他のページに利用可能な断片がないとき
は、ブロツクが既に割付けられている複数ページの組か
らページ候補を識別する。例えば第４図に示すように、
ページ１はページ・アウト候補として識別されている。
所望の選択技術により、例えば最適なものとして最高の
利用率を有するページの選択と組合せた最新使用（ＬＲ
Ｕ）アルゴリズムに従つてあるページを選択することに
より、ページ・アウト候補のページの選択をすることが
できる。この選択の組合はよく利用されている静止ペー
ジを表わすものである。次に、空きとなつた物理ページ
は進められたポインタＮにて順方向ブロツクの割付け及
び複写が可能である。
用可能な空間より大きなブロツクを割付けなければなら
ず、また新しいブロツクと適合するのに十分な大きさの
物理メモリに他のページに利用可能な断片がないとき
は、ブロツクが既に割付けられている複数ページの組か
らページ候補を識別する。例えば第４図に示すように、
ページ１はページ・アウト候補として識別されている。
所望の選択技術により、例えば最適なものとして最高の
利用率を有するページの選択と組合せた最新使用（ＬＲ
Ｕ）アルゴリズムに従つてあるページを選択することに
より、ページ・アウト候補のページの選択をすることが
できる。この選択の組合はよく利用されている静止ペー
ジを表わすものである。次に、空きとなつた物理ページ
は進められたポインタＮにて順方向ブロツクの割付け及
び複写が可能である。
可能ならば、いつでも廃物ブロツクを配置し、かつ除去
することが望ましい。残念ながらこのようなブロツクを
発見する機会は限定されている。しかし、２以上のブロ
ツクが循環リストを形成し、全ブロツクが一つのページ
内に収容され、かつ全ブロツクのリストが１の参照カウ
ントを有するときは、このようなブロツクは廃物ブロツ
クであり、ページ・アウトしようとしているページの一
掃中に検出できる。ページの一掃により参照のみをそこ
から開始しているブロツクも配置できる。その結果、十
分な廃物ブロツクを用いて必要な利用可能断片を生成す
るので、バツクアツプ・メモリにページをページ・アウ
トする必要性を事前に処理している。
することが望ましい。残念ながらこのようなブロツクを
発見する機会は限定されている。しかし、２以上のブロ
ツクが循環リストを形成し、全ブロツクが一つのページ
内に収容され、かつ全ブロツクのリストが１の参照カウ
ントを有するときは、このようなブロツクは廃物ブロツ
クであり、ページ・アウトしようとしているページの一
掃中に検出できる。ページの一掃により参照のみをそこ
から開始しているブロツクも配置できる。その結果、十
分な廃物ブロツクを用いて必要な利用可能断片を生成す
るので、バツクアツプ・メモリにページをページ・アウ
トする必要性を事前に処理している。
ここに提供した割付け構造においては、ポインタＮによ
り指示されたものを除くページが頻繁に用いられるの
で、ポインタＮはもつと遅い仮想アドレス空間を介して
進むことになる。その結果、従来構造において進められ
た時間よりかなり長い時間、廃物収集を延期することが
できる。
り指示されたものを除くページが頻繁に用いられるの
で、ポインタＮはもつと遅い仮想アドレス空間を介して
進むことになる。その結果、従来構造において進められ
た時間よりかなり長い時間、廃物収集を延期することが
できる。
本発明をある程度限定して説明し、かつ図示している
が、説明したステツプ及び手順は単なる例であつて、組
合せ及び構成において多数の変更が特許請求の範囲に記
載したように本発明の精神及び範囲を逸脱することな
く、当該技術分野において習熟する者により実行可能な
ことは理解される。
が、説明したステツプ及び手順は単なる例であつて、組
合せ及び構成において多数の変更が特許請求の範囲に記
載したように本発明の精神及び範囲を逸脱することな
く、当該技術分野において習熟する者により実行可能な
ことは理解される。
第１図は本発明によりブロツクを最初に割付けられてい
るときの領域Ｘの仮想アドレス空間の構造を示すブロツ
ク図、 第２図は本発明によりブロツクの割付けを解除し、参照
したブロツクを順方向に複写したときの第１図の領域の
仮想アドレス空間を示し、かつ完全に一杯でも空でもな
いページの利用可能な断片リストの処理を示すブロツク
図、 第３図は本発明に従い、まばらに割付けられた活性ペー
ジの識別を示すと共に、この活性ページに順方向ブロツ
クを割付け、かつ複写をするブロツク図、 第４図は第１図及び第２図の領域Ｘの仮想アドレス空間
を示し、デイスクに対してまばらでなく静止的に割付け
たページの識別及びページ・アウトを示すブロツク図で
ある。 図の種々の符号において、同一の参照符号を用い、同一
又は同様の項目若しくは部分を示す。 １０…仮想アドレス空間、１１…先頭点、Ｂ１〜Ｂ１
８，Ｂ１′〜Ｂ１６′，Ｂ７″…ブロツク。
るときの領域Ｘの仮想アドレス空間の構造を示すブロツ
ク図、 第２図は本発明によりブロツクの割付けを解除し、参照
したブロツクを順方向に複写したときの第１図の領域の
仮想アドレス空間を示し、かつ完全に一杯でも空でもな
いページの利用可能な断片リストの処理を示すブロツク
図、 第３図は本発明に従い、まばらに割付けられた活性ペー
ジの識別を示すと共に、この活性ページに順方向ブロツ
クを割付け、かつ複写をするブロツク図、 第４図は第１図及び第２図の領域Ｘの仮想アドレス空間
を示し、デイスクに対してまばらでなく静止的に割付け
たページの識別及びページ・アウトを示すブロツク図で
ある。 図の種々の符号において、同一の参照符号を用い、同一
又は同様の項目若しくは部分を示す。 １０…仮想アドレス空間、１１…先頭点、Ｂ１〜Ｂ１
８，Ｂ１′〜Ｂ１６′，Ｂ７″…ブロツク。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ドナルド ダブリユ．オツクスリイ アメリカ合衆国テキサス州キヤロルトン, エヌ．サレー ドライブ 2805 (56)参考文献 特開 昭59−211156（ＪＰ，Ａ) 特開 昭61−273647（ＪＰ，Ａ) 特開 昭59−65988（ＪＰ，Ａ) 特開 昭58−37886（ＪＰ，Ａ)
Claims (6)
- 【請求項１】情報のブロックが書き込まれる物理メモリ
に固定数の仮想アドレスページを含む要求ページング仮
想アドレス空間におけるメモリブロック圧縮方法におい
て、 ブロックが書き込まれた仮想アドレスページの利用率を
決定し、 前記仮想アドレスページ内で利用可能なメモリ断片の情
報を含むテーブルに、ブロックの情報が書き込み可能で
ある利用可能なメモリ断片の少なくともアドレスと大き
さを書き込み、 仮想アドレスページが、最新に利用され、最も疎に割り
付けられ、新しい物理ページの割付が必要とされた場合
に、前記テーブルによって指示されたメモリ断片を含む
物理メモリの該仮想アドレスページに前記ブロックを配
置させる、 ことを特徴とする要求ページング仮想アドレス空間にお
けるメモリブロック圧縮方法。 - 【請求項２】特許請求の範囲第１項記載の要求ページ仮
想アドレス空間におけるメモリ・ブロック圧縮方法にお
いて、更にデイスク・メモリを備え、要求したメモリ断
片が物理メモリから得られないときは最新に用いられ、
かつ所定の高利用率を有する所定のページを前記デイス
ク・メモリにページ・アウトする段階を有することを特
徴とする要求ページ仮想アドレス空間におけるメモリ・
ブロック圧縮方法。 - 【請求項３】特許請求の範囲第１項記載の要求ページ仮
想アドレス空間におけるメモリ・ブロック圧縮方法にお
いて、更に参照カウントが零となったブロックの割付け
を解除する段階を有することを特徴とする要求ページ仮
想アドレス空間におけるメモリ・ブロック圧縮方法。 - 【請求項４】特許請求の範囲第１項記載の要求ページ仮
想アドレス空間におけるメモリ・ブロック圧縮方法にお
いて、更にポインタＮを設定して前記仮想メモリ空間の
アドレスを表示する段階と、 前記ポインタＮを進めて次に利用可能な仮想アドレス・
ページの先頭を連続的に表示する段階と、 新しい物理ページを必要とするときに前記メモリ断片リ
スト及び利用の決定により表示された仮想アドレス・ペ
ージにブロックが存在するときは新しく割付けられたブ
ロックを配置する段階と、を有することを特徴とする要
求ページ仮想アドレス空間におけるメモリ・ブロック圧
縮方法。 - 【請求項５】特許請求の範囲第４項記載の要求ページ仮
想アドレス空間におけるメモリ・ブロック圧縮方法にお
いて、更に歩進するポインタの現在位置に対してユーザ
により参照されたブロックを転送することにより、静止
ページに静止ブロックを収集し、かつ活性ページに活性
ブロックを収集する段階を有することを特徴とする要求
ページ仮想アドレス空間におけるメモリ・ブロック圧縮
方法。 - 【請求項６】特許請求の範囲第１項記載の要求ページ仮
想アドレス空間におけるメモリ・ブロック圧縮方法にお
いて、利用可能な断片のテーブルを設ける前記段階は関
連する前記ページ上の利用可能な断片の各ページと関連
されたリストを設ける段階を有することを特徴とする要
求ページ仮想アドレス空間におけるメモリ・ブロック圧
縮方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US644072 | 1984-08-24 | ||
| US06/644,072 US4758944A (en) | 1984-08-24 | 1984-08-24 | Method for managing virtual memory to separate active and stable memory blocks |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS61117638A JPS61117638A (ja) | 1986-06-05 |
| JPH0638242B2 true JPH0638242B2 (ja) | 1994-05-18 |
Family
ID=24583332
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60184383A Expired - Lifetime JPH0638242B2 (ja) | 1984-08-24 | 1985-08-23 | 要求ペ−ジ仮想アドレス空間におけるメモリ・ブロツク圧縮方法 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US4758944A (ja) |
| EP (1) | EP0172707A3 (ja) |
| JP (1) | JPH0638242B2 (ja) |
Families Citing this family (41)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4912629A (en) * | 1986-06-26 | 1990-03-27 | The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration | Real-time garbage collection for list processing using restructured cells for increased reference counter size |
| JPS6336348A (ja) * | 1986-07-30 | 1988-02-17 | Toshiba Corp | バツフアメモリ管理方法 |
| US4989134A (en) * | 1987-03-20 | 1991-01-29 | Hewlett-Packard Company | Method and apparatus for enhancing data storage efficiency |
| US4807120A (en) * | 1987-04-30 | 1989-02-21 | Texas Instruments Incorporated | Temporal garbage collector with indirection cells |
| US5101485B1 (en) * | 1989-06-29 | 1996-12-10 | Frank L Perazzoli Jr | Virtual memory page table paging apparatus and method |
| US5321834A (en) * | 1989-11-28 | 1994-06-14 | Xerox Corporation | Method and system for reclaiming unreferenced computer memory space |
| JPH0792775B2 (ja) * | 1989-12-11 | 1995-10-09 | 株式会社日立製作所 | 外部記憶装置群のスペース管理方法 |
| JPH03266039A (ja) * | 1990-03-16 | 1991-11-27 | Fujitsu Ltd | フリーフォーマットデータリンク処理方式 |
| JPH04230508A (ja) * | 1990-10-29 | 1992-08-19 | Internatl Business Mach Corp <Ibm> | 低電力消費メモリ装置 |
| US5339411A (en) * | 1990-12-21 | 1994-08-16 | Pitney Bowes Inc. | Method for managing allocation of memory space |
| US5257143A (en) * | 1991-01-15 | 1993-10-26 | Zenith Data Systems Corporation | Method and apparatus for positioning head of disk drive using zone-bit-recording |
| JP3386823B2 (ja) * | 1991-03-28 | 2003-03-17 | 株式会社日立製作所 | ファイルの管理方法及び装置 |
| US5386536A (en) * | 1991-03-28 | 1995-01-31 | Courts; Howard R. | Apparatus and method for managing memory allocation |
| US5659744A (en) * | 1991-10-15 | 1997-08-19 | International Computers Limited | Data file store system with means for efficiently managing freeing of data blocks |
| JPH05274152A (ja) * | 1992-03-27 | 1993-10-22 | Hitachi Ltd | オブジェクト管理方式 |
| US5479656A (en) * | 1992-05-13 | 1995-12-26 | Rawlings, Iii; Joseph H. | Method and system for maximizing data files stored in a random access memory of a computer file system and optimization therefor |
| US5535369A (en) * | 1992-10-30 | 1996-07-09 | Intel Corporation | Method for allocating memory in a solid state memory disk |
| US5822781A (en) * | 1992-10-30 | 1998-10-13 | Intel Corporation | Sector-based storage device emulator having variable-sized sector |
| US5802599A (en) * | 1994-02-08 | 1998-09-01 | International Business Machines Corporation | System and method for allocating storage in a fragmented storage space |
| US5568634A (en) * | 1994-04-21 | 1996-10-22 | Gemplus Card International | Method of writing in a non-volatile memory, notably in a memory card employing memory allocation strategies on size and occupancy basis |
| US5493652A (en) * | 1994-04-29 | 1996-02-20 | International Business Machines Corporation | Management system for a buffer memory having buffers of uniform size in which the buffers are divided into a portion of contiguous unused buffers and a portion of contiguous buffers in which at least some are used |
| US5563828A (en) * | 1994-12-27 | 1996-10-08 | Intel Corporation | Method and apparatus for searching for data in multi-bit flash EEPROM memory arrays |
| US5721917A (en) * | 1995-01-30 | 1998-02-24 | Hewlett-Packard Company | System and method for determining a process's actual working set and relating same to high level data structures |
| US5689707A (en) * | 1995-12-04 | 1997-11-18 | Ncr Corporation | Method and apparatus for detecting memory leaks using expiration events and dependent pointers to indicate when a memory allocation should be de-allocated |
| US5829013A (en) | 1995-12-26 | 1998-10-27 | Intel Corporation | Memory manager to allow non-volatile memory to be used to supplement main memory |
| US5937434A (en) * | 1997-02-14 | 1999-08-10 | Intel Corporation | Method of managing a symmetrically blocked nonvolatile memory having a bifurcated storage architecture |
| US6311290B1 (en) | 1997-02-14 | 2001-10-30 | Intel Corporation | Methods of reliably allocating, de-allocating, re-allocating, and reclaiming objects in a symmetrically blocked nonvolatile memory having a bifurcated storage architecture |
| US6182188B1 (en) | 1997-04-06 | 2001-01-30 | Intel Corporation | Method of performing reliable updates in a symmetrically blocked nonvolatile memory having a bifurcated storage architecture |
| US6088759A (en) * | 1997-04-06 | 2000-07-11 | Intel Corporation | Method of performing reliable updates in a symmetrically blocked nonvolatile memory having a bifurcated storage architecture |
| JPH11143779A (ja) * | 1997-11-07 | 1999-05-28 | Nec Corp | 仮想記憶装置におけるページング処理システム |
| US6192444B1 (en) * | 1998-01-05 | 2001-02-20 | International Business Machines Corporation | Method and system for providing additional addressable functional space on a disk for use with a virtual data storage subsystem |
| FR2820849B1 (fr) * | 2001-02-15 | 2003-05-16 | Cit Alcatel | Procede de stockage de donnees informatiques et dispositif de stockage correspondant |
| US6751718B1 (en) * | 2001-03-26 | 2004-06-15 | Networks Associates Technology, Inc. | Method, system and computer program product for using an instantaneous memory deficit metric to detect and reduce excess paging operations in a computer system |
| US20040181373A1 (en) * | 2003-03-12 | 2004-09-16 | Computer Associates Think, Inc. | Visual simulation of dynamic moving bodies |
| EP1870814B1 (en) * | 2006-06-19 | 2014-08-13 | Texas Instruments France | Method and apparatus for secure demand paging for processor devices |
| US8112618B2 (en) | 2004-04-08 | 2012-02-07 | Texas Instruments Incorporated | Less-secure processors, integrated circuits, wireless communications apparatus, methods and processes of making |
| US20070245111A1 (en) * | 2006-04-18 | 2007-10-18 | International Business Machines Corporation | Methods, systems, and computer program products for managing temporary storage |
| EP1870813B1 (en) * | 2006-06-19 | 2013-01-30 | Texas Instruments France | Page processing circuits, devices, methods and systems for secure demand paging and other operations |
| US8424071B2 (en) * | 2009-04-15 | 2013-04-16 | International Business Machines Corporation | Method and apparatus for secure and reliable computing |
| US9942324B2 (en) * | 2015-08-05 | 2018-04-10 | Futurewei Technologies, Inc. | Rebalancing and elastic storage scheme with elastic named distributed circular buffers |
| US12524269B2 (en) * | 2021-03-10 | 2026-01-13 | Texas Instruments Incorporated | Stack memory allocation control based on monitored activities |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CS164932B2 (ja) * | 1971-09-07 | 1975-11-28 | ||
| US3882470A (en) * | 1974-02-04 | 1975-05-06 | Honeywell Inf Systems | Multiple register variably addressable semiconductor mass memory |
| US4189773A (en) * | 1974-07-03 | 1980-02-19 | General Electric Company | On-line memory space allocation |
| GB1548401A (en) * | 1975-10-08 | 1979-07-11 | Plessey Co Ltd | Data processing memory space allocation and deallocation arrangements |
| JPS56140451A (en) * | 1980-03-31 | 1981-11-02 | Hitachi Ltd | Log information holding device |
-
1984
- 1984-08-24 US US06/644,072 patent/US4758944A/en not_active Expired - Lifetime
-
1985
- 1985-08-07 EP EP85305625A patent/EP0172707A3/en not_active Withdrawn
- 1985-08-23 JP JP60184383A patent/JPH0638242B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| US4758944A (en) | 1988-07-19 |
| EP0172707A3 (en) | 1989-08-16 |
| JPS61117638A (ja) | 1986-06-05 |
| EP0172707A2 (en) | 1986-02-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0638242B2 (ja) | 要求ペ−ジ仮想アドレス空間におけるメモリ・ブロツク圧縮方法 | |
| US4660130A (en) | Method for managing virtual memory to separate active and stable memory blocks | |
| EP0574884B1 (en) | A computer method and system for memory management | |
| EP0375188B1 (en) | File system | |
| US4695949A (en) | Method for efficient support for reference counting | |
| US6757794B2 (en) | Buffering data in a hierarchical data storage environment | |
| US6928460B2 (en) | Method and apparatus for performing generational garbage collection in a segmented heap | |
| US7072916B1 (en) | Instant snapshot | |
| US5125086A (en) | Virtual memory paging apparatus with variable size in-page clusters | |
| KR100390616B1 (ko) | 고정적이고 확실한 저장 할당을 위한 시스템 및 방법 | |
| JP3507132B2 (ja) | フラッシュメモリを用いた記憶装置およびその記憶制御方法 | |
| US6105103A (en) | Method for mapping in dynamically addressed storage subsystems | |
| US6308185B1 (en) | Methods and apparatus for generational dynamic management of computer memory | |
| EP1074916B1 (en) | Hardware mechanism for managing cache structures in a data storage system | |
| US6704835B1 (en) | Posted write-through cache for flash memory | |
| JPH0775004B2 (ja) | メモリ制御方法 | |
| US5390315A (en) | Allocation of uniform contiguous blocks of DASD storage by maintaining both a bit and a bit map record of available storage | |
| EP1686483A2 (en) | Method and apparatus to permit adjustable code/data boundary in a nonvolatile memory | |
| JP2003515812A (ja) | 掃除用のガーベッジコレクションの効果を高めるための方法および装置 | |
| US20050027933A1 (en) | Methods and systems for managing persistent storage of small data objects | |
| US6842838B2 (en) | Preemptive memory-block splitting | |
| JPH06214874A (ja) | メモリ管理方式 | |
| US6584475B1 (en) | System for controlling database growth in a read-repeatable environment | |
| JPS6136668B2 (ja) | ||
| Greenberg et al. | The multics multilevel paging hierarchy |