JPS61112257A - コンピユ−タ・メモリ・システム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 この発明はメモリ・システムの改良に関し、さらに詳し
く述べれば、共に組み合わされる使用者のプロセッサと
は別個に自動記憶動作を可能にする形のメモリ・システ
ムの改良に関するものである。

記憶管理システムの開発には、多くの関連分岐の研究を
伴う長い歴史がある。多年にわたり、メモリ構造物を割
り当てたり除去するのに多くの注意が払われた。この目
的の多くのメモリ構造物は、マサチューセッツ州、アデ
ィソンーウエスリーのエッチ・エム・ディーチル（Ｄｅ
ｉｔｅｌ、　Ｈ，Ｍ、）が１９８２年に発表した「オペ
レーティング・システム入門」の第７草に示されている
。他の主な問題点はマサチューセッツ州アディンンーウ
ェスリー、リーディングのディー・ニュース（Ｄ、Ｋｎ
ｕｔｈ）が１９６８年に発表した「コンピュータ・プロ
グラミングの技法、第１巻二基礎アルゴリズム」に記載
されている。ここに説明する本発明は主として、ガーベ
ッジ収集することができる大量の管理メモリに関する。

大量の管理メモリとは、考慮中のメモリ・ユニットの一
時的な順序または大きさに関係なくメモリが割り当てら
れたり除去される（顕在的にあるいは暗示的に）ことを
意味する。

ガーベッジ収集されたメモリは使用可能メモリが自動的
に返還要求されるメモリであり、またメモリは必要に応
じてメモリのスペースを有効に利用するためにときどき
組織替えされる。ガーペッゾ収集法の背景研究および関
連背景資料は、１９８１年９月発行のコンピュータ・サ
ーベイス、第１６巻、第６号に記載されたジエー・ニー
ヘン（Ｊ。

Ｃ０Ｍｎ　）の「リング式データ構造物のガーペツゾ収
集」の第６４１頁〜第６６７頁によって示され、ｔｆ′
ｃ１９７５年９月発行のマサチューセッツ仮術協会誌１
１１にピー・ビショップ（Ｐ、　Ｂ１５ｈｏｐ　）によ
って記載された「きわめて大きなアドレス・スペースに
おけるガーベッジ収染」にも示されている。

人工知能の急速な開発につれて、例えば動的組織を要求
するきわめて大量または複雑な情報の記憶装置を含む使
用の場合、いわゆる「知識ベース」すなわち大きなデー
タ・ベースの開発に関心が高まっている。例えば１９８
０年、工ＣＯＴ「第５世代コンピュータ・システムの事
前報告書」にエム・スワ（Ｍ、　Ｓｕｗａ　）らが記載
しｆｃ「知識ベース・メカニズム」を参照のこと。考慮
中または実施済の　　、゛ある大きなデータ・ベースの
例としては、例えば逐語的な判例報告書とか、特定の症
状を表わす診断可能な病気に用いる医学情報とか、要約
、特許請求の範囲、および譲渡情報を含む一定の特許情
報とか、製造業者、小売業者、卸亮業者などの職業別電
話帳とかいった法的情報を包含するデータ・ベースが含
まれる。そのようなデータ・ベースでは、特定な１組の
語および文字のわずかな発生でも発見し、次にその語お
よび文字に関する特定な記録（判例、特許、診断など）
を識別するために、ときには何百万語をも捜す必要がし
ばしばある。

現在、リスプ（Ｌｉ５ｐ　）のような、またそれより少
ない程度まで、パスカル（Ｐａ５ｃａｌ　）およびエイ
ダ（Ａｄａ　）のような特定のコンピュータ言語が、か
かる大量割当てのデータ・ベースの実施に使用されてい
る（リスプはガーペツジ収集されたデータ・ベースをも
支持している）。メモリの割当て、除去、ガーベツジ収
集および圧縮を行うかかる伝統的なアーキテクチャでは
通常、言語実行時間支持および使用されるコンパイラは
ガーペツジ収集および圧縮の責任を負い、また仮想メモ
リ、システムが提供される場合は通常、仮想メモリ・シ
ステムを管理するはハードウェアおよびオペレーティン
グ・システムの責任である。普通、例えばオペレーティ
ング・システムは主メモリと補助メモリとの間をページ
がどう移動するかを決定するある独の要求時ページ転送
Ｌｆ（Ｕを常時使用し、またガーペッジ・コレクタはど
のページが要求されたりどのページがもはや不要である
かを規定する。

前述の通り、今日利用できるシステムでは、メモリはハ
ードウェア・オペレーティング・システム、言語、およ
びデータ・ベースにおいて通常管理される。せいぜい局
部的な最適化を生じるが、多（の場合相互に依存しで働
かない多数の方法が現在使用されている。これらの方法
はしばしば、個人プログラマが理解したり管理するのは
難しい。

プログラマ−がしばしば遭遇する重大な問題として、使
用される特定メモリの速度に直接関連のある個々の語呼
出し速度がある。また、メモリ・ユニットが一定の大き
さのまたは割り当てられた、後入れ先出しくＬＩＦＯ）
方式でない場合には、割当て速度も困難な問題を提供す
る。また、利用できるようになるメモリのブロック間の
時間遅延（どんなプログラムでも解決不能）、および再
割当ての準備をする時間が多く遭遇する問題である。さ
らに、仮想メモリのスペースの全体的な大きさがしばし
ば問題になるのは、ガーベツジ収集の費用が要求される
ガーベツジの量ではなく収集されるスペースの大きさと
共に増大するからである。最後に、保全ま友は安全が重
大な問題であるのは、プログラムまたはメモリの設計に
おいて故意または不注意に、プログラムがメモリ組織の
実際の構造物を常時無視することができ、またデータの
ブロックが容易に書き過ぎされたり完全に消去されるこ
とがあるからである。

サップ（Ｔｈａｔｔｅ　）等による「自動メモリ動作を
可能にするコンピュータ・システム」という件名の同時
係属特許出願（事件要領書第ＴＩ　−１０５９９号）に
も言及されるが、前記出願はこれの譲受人に譲渡されか
つここに参考のために背景として包含される。サップ等
の出願は関連ＣＰＵを持つコンピュータ・システムにつ
いて記載している。そのシステムは一般に自動メモリ動
作を可能にし、本発明は使用者のＣＰＵがメモリ・シス
テムから完全に切り離されて具備される一般システムの
特定な実施例を開示する。

上記から、したがって、本発明の１つの目的は共に組み
合わされる使用者のプロセッサとは別個に自動メモリ動
作全可能にするメモリ・システムを提供することである
。

本発明のもう１つの目的は、使用者のＣＰＵおよびメモ
リ管理二二ツ）　（ＭＭＵ）の責任がメモリ管理責任を
持たないＣＰＵと区別され、■がメモリ内でデータを自
由に移動させる能力を持ち、ＣＰＵおよびＭＭＵがいず
れも別々に、独立して、また同時に作動することができ
、さらにＣＰＵがメモリの完全な組織を維持するのに必
要な構造情報を不注意にまたは故意に破壊しないように
されている。上述の形のメモリ・システムを提供するこ
とである。

本発明０も５１″目的引特定ＯＣＰＵ言語実　　、・、
行およびオペレーティング・システムから自由な上述の
形のメモリ管理システムを提供することである。

本発明のもう１つの目的は、ＣＰＵがメモリをブロック
向きとして見ることができる論理アドレス・スペースを
使用者のＣＰＵに提供する上述の形のメモリ管理システ
ムを提供ｉることである。

本発明のもう１つの目的は、メモリのブロックが上述の
通りＣＰＵとＭＭＵの作動を別々にする情報識別タグを
運ぶとともに、メモリ・システムの完全性に影響を及ぼ
す選択されたタグの組が肩によって厳密に管理される、
上述の形のメモリ管理システムを提供することである。

本発明のもう１つの目的は、ポインタを含むブロックを
越えるメモリ・ブロックを表示するために、メモリのブ
ロックが使用者のＣＰＵには見え難いポインタを含むこ
とがある、上述の形のメモリ・システムを提供すること
である。

本発明のもう１つの目的は、メモリの外部にあって実際
にはどんな形でもよく、かつメモリが適肖に形成された
バインデイング・レジスタを通してのみ使用のプロセッ
サによって呼び出し得るブロック内に無限に割り当てる
ことができる、使用者のＣＰＵと組み合わされる上述の
形のメモリーシステムを提供することである。

上記および他の目的、特徴ならびに利点は、゛付図およ
び特許請求の範囲と共に読むとき下記の詳細な説明から
、尚来者にとって明らかになると思う。

本発明の広い面によるメモリ・システムは、使用者のＣ
ＰＵからの条件、指令または命令に応動して、メモリ・
ブロックを割り当てるとともに割ｇ当てられたメモリ・
ブロックに関する読み、書き、移動、およびＥＱ試験の
諸命令を使用者のＣＰＵに実行させることを特徴とする
メモリ・システムを提供する。メモリ・システムの作動
は、使用者のＣＰＵをメモリにインターフェース接続し
、またメモリをブロック向きメモリとして使用者のＣＰ
Ｕに見えるようにし、さらにメモリ管理ユニットに使用
者のＣＰＵから別個にかつ実際に見え難くメモリのオー
バーヘッド機能を制御させる、バインデイング・レジス
タの使用に基づく。

本発明全付図について説明する。

いろいろな図において、似ていたり同様な部品を表わす
ために同様な参照数字が使用されている。

第１図に示される通り、本発明のメそり・システム１０
は、使用者のＣＰＵ　２０　（使用者のプロセッサと呼
ぶことがある）と組み合わされろ、メモリ管理ユニット
１１および物理的メモリ１２ｔ−含む。明らかＫなると
思うが、これまでのメモリ作動と違って、ここに提起さ
れた使用者のｃｐａ　２　ｇおよびメモリ管理ユニット
（ＭＭＵ　）　１１の責任は別々である。すなわち、Ｏ
ｐＨ７２０はメそす管理責任を負わず、ＭＭＵｌｌはメ
モリ内でデータ全自由に動かすことができる。さらにＣ
ＰＵ　２０は、メ毒りの組織の完全性全維持するのに必
要なメモリの構造情報を不注意［または故意に破壊した
り変えたりすることはできない。明らかになると思うが
、使用者のＣＰＵ　２０は、実際にはメモリ・システム
１０と両立し得るどんな形または種類のものでもよい。

メモリ・システム１０は、使用者のＣＰＵ　２０に対し
てブロック向きと思わせる。いま第２図から、メモリ・
システム１０の実際の構造またはハードウェア構造にか
かわらず、それは参照数字１０およびそれと組み合わさ
れた点線の矢印によって示される通り、使用者のｃｐｔ
ｙ　２０から見て外見上の論理メモリ組織１０を持つ。

論理メモリ組織１０はここでは「論理アドレス・スペー
ス」と呼ばれ、また、明らかになると思うが、以下に説
明されるメモリ管理ユニットから見てメモｌＪ表５！Ａ
または抽象化である「仮想アドレス・スペース」と区別
され、さらにメモリ・システムの実際の物理的メモリ素
子である物理的メモリと区別される。

論理メモリ・システム１０は、論理メモリ・システム１
０の窓または門として役立つ、第６図について詳しく下
記に説明されるバインデイング・レジスタ・ユニット１
５ｔ−持つ。（パインディング会レジスタ・ユニット１
５はメモリ・システム１０の実部分であり、使用者のＯ
ＰＵから見てブロック向きの外観または論理アドレス・
スペース全、メモリ管理が実際に行われる仮想アドレス
・スペースに変える働きをする。）バインデイング・レ
ジスタ・ユニット１５の原理は、どんな瞬間でも使用者
のプロセッサ２０が限定数のブロックのみ金属液アドレ
スし匈ること１．さらに詳しく述べれば、バインデイン
グ・レジスタ・ユニット１５の中の１組のバインデイン
グ・レジスタにポインタが含まわるブロックを使用者の
プロセッサが直接アドレスし得ること、に基づいている
。

使用者のＣＰＵ　２０は普通、バインデイング・レジス
タ・ユニット１５に２つの作動モードで使用する。かく
て、バインデイング・レジスタ１５はメモリ内に特定な
ブロックのアドレス能力を作るために、ブロック識別子
（すなわちブロックに対するポインタ）ｔロードされる
。こねは、アドレス能力が作られているブロックに対す
る特有のバインデイング・レジスタの「パインディング
」と呼ばれる。「パインディング」という語は、ブロッ
クとレジスタの組合せ全強調するのに用いられる。「ポ
インタ」という語は、メモリの特定なブロックのアドレ
ス能力定する値またはデータを示すのに用いられる。明
らかになると思うが、バインデイング・レジスタ内に含
まれるブロック識別子源には一定の制限がある。初期設
定プートストラップ・アドレスを除き、唯一のブロック
・アドレスまたはポインタ源は前に結合されたブロック
または別のバインデイング・レジスタから得られる。

バインデイング・レジスタ・ユニット１５の他の主な作
動モードは、前に結合されたブロック内のある値全参照
する基鋭となる。例えは、規定された相対ブロック位置
にあるデータに関するＣＰＵの要請に応じて、ＭＭＵは
バインデイング・レジスタに含まれるブロック・アドレ
ス・フィールドの内容にインデックス・カウント金加え
ることによってブロック内に発見されたり含まれるべき
特定な値のアドレス全作る。インデックスが特定のブロ
ックにつ〜・て妥当なものであること、例えは、インデ
ックスが２語ブロックの第４語を規定しないこと、全立
証する必要が認められると思う。バインデイング・レジ
スタ・ユニットはこの形のアドレス指定を、ブロックに
現在結合されているレジスタ名に対する相対インデック
スとして支持する。したがってそれは、インデックスが
参照を許する前に安酒であるかどうかを調べる完全検査
を提供する。

さらに詳しく述べれば、バインデイング・レジスタ・ユ
ニット１５は多数のすなわち１組の個々のバインデイン
グ・レジスタ２１．２２．・・・・・・３０を含み、各
レジスタは使用者のＣＰＵ　２０によってアドレス可能
でありかつ操作可能である。使用者のＣＰＵがバインデ
イング・レジスタをアドレスする方法は、例えは、単に
「レジスタ１」、「レジスタ５」などのような特定のバ
インデイング・レジスタを規定するだけで可能である。

バインデイング・レジスタ・ユニット１５は、考慮中の
メモリ管理ユニットの特定な応用に必要なだけ多（のバ
ンディング・レジスタ金持つことができる。

メそり・システム１０の中には、メモリ・ブロックを割
り当てることができる大形物理的メモリ（以下に詳しく
説明する）がある。例えは第２図において、２個のブロ
ック４０および４５は使用者のＣＰＵからの適当な指令
によって作られる（下記）。作られる各ブロックは見出
し部分４０ｈおよび４５１１含み、その少なくとも一部
はバインデイング・レジスタ・ユニット１５のバインデ
イング・レジスタ２０−３０の中の１つに置注される。

そねそれの各ブロックの見出しは、なによりもまずブロ
ック識別データ、ブロック長さデータ、ブロック形式デ
ータ、フラグなどを含む。

さらに各ブロック４０および４５には、データ語４０改
ならひに４５ｄがそれぞれ含まれている。

データ語４０（Ｌおよび４５ｄは、ブロック４０ならび
に４５のそれぞれの見出しからアドレス位置の数だけ移
動される。アドレス位置の数は、使用者のＣＰＵによる
特定アドレスの移動の明細會含む多くの要素に左右され
る。さらに詳しく述べれは、使用者のＣＰＵは例えはバ
インデイング・レジスタ・ユニット１５のレジスタ２１
に含まれる見出し　　１°１からの移動を定めることに
よって、位置４（ｌでブロック４０にデータを書き込む
ことができる〇使用者のＣＰＵが所望のブロック位置を
定める方法は、ブロックが結合される特定のバインデイ
ング・レジスタ（例えは「レジスタ１」）および結合さ
れたブロック内の移動（例えはｒｊＪ　）ｉ定めること
である。次に規定値は使用者のＣＰＨにデータとして直
接戻されたり、（同じまたは異なる）規定されたバイン
デイング・レジスタにおいてバインデイング・レジスタ
・ユニット圧書き込まれたりする。

かくて、例として、また一層間らかになると思うが、使
用者のＣＰＵ　２０はメモリ・システム１０にブロック
、例えば参照数字４０によって表わされるある規定長さ
の説明のためのブロック、を作る指令上山すことができ
る。その銹三に、０ＰＵ２０はレジスタ２１のようなＣ
ＰＵ指示による目標バインデイング・レジスタ内のブロ
ック４０にポインタを置（ようにＭＭＵ顛指示を出す。

その後、ＣＰＵ２０はバインデイング・レジスタ２１の
ポインタによって指向される見出しのアドレスからの移
動ｒｊＪ　ｉ規定することによって、ブロック４０にデ
ータ全書き込む指令を出すことがある。ＣＰＵ２０は、
ブロック４０のアドレスを含まず、ポインタと移動「ｊ
」とを含む特定のバインデイング・レジスタ２１のみを
規定すること全強調しなければならない。

バインデイング・レジスタ・ユニット１５のバインデイ
ング・レジスタおよびブロックをそれに結合する方法は
、第３図についてこれからさらに評しく説明される。各
バインデイング・レジスタは、部分「ａ」と部分「ｂ」
で表わされる２つの部分を備えている。各部分「ａ」と
「ｂ」は、以下に詳しく説明される通り、一定のブロッ
ク識別情報を含む。上述の通り、バインデイング・レジ
スタ・ユニット内のブロックの制定またはパインディン
グの際に１特定のブロック位置またはアドレスは相対イ
ンデックスによって使用者のＣＰＵにより参照される。

第６図に示される通り、この特定の例では、参照される
特定の位置は見出し４５ｈからの移動「１」で前に結合
された参照ブロック４５にあるＰｃによって表わされる
セルである。

このセルＰＣは２個のセグメン）ｔ−有し、第１セグメ
ント６４はＭＭＵタグ用であり、第２セグメント７１は
参照ブロックの見出しに対するポインタ用またはデータ
用である。（いずれの場合も、セグメント７１の内容は
観測者には「データ」として現われろ。）　ＭＭＵタグ
６４は、「データ」が実際にポインタであるか否か會示
す。かくて本例では、セルＰｃのセグメント７１にある
「データ」語は、バインデイング・レジスタ・ユニット
に結合すべき次の後続ブロック（ブロック４０）の見出
し情報４０ｈＫ関するポインタであるかまたはそのポイ
ンタを含んでいる。見出し４０ｈｆ）第１および第２レ
ジスタにある情報は、次忙下記の方法でレジスタの部分
子ａＪおよび部分「ｂ」にコピーされ、それによってパ
インディング工程は完了される。ここでは問題外の情報
も、見出し部分４０ｈＫ含まれることがある。

もう一度、バインデイング・レジスタの部分子ａＪから
、問題の２つの情報、すなわちメモリ管理ユニット・タ
グ６２およびメモリ・サイズ・セグメント６Ｂが与えら
れろ。バインデイング・レジスタの部分「ｂ」も問題の
２つのセグメントを持つ。第１セグメント６３はメモリ
管理ユニット・タグ６３用であり、第２セグメント６９
はあるフラグ用である。バインデイング・レジスタのレ
ジスタ部分子ｔ）Ｊ　（レジスタ部分子０にあるフラグ
はいろいろなフラグを含み、七の例として「ロック」フ
ラグ、「結合」フラグなどがある。ロック・フラグは例
えば、メモリ管理ユニット以外によるブロックのどんな
アドレス指定でも禁止される間のブロックの制定または
移動に使用される。

結合フラグは例えば、ブロックがバインデイング・レジ
スタに結合されていることを表わすのに用いられる。

第２図および第６図の論理メモリ組織を可能にするバイ
ンデイング・レジスタ・ユニツ）ｋ達成するために、第
４図に示されろ方法で配列されたハードウェアが使用さ
れる。本発明によるパインディング・ユニット１５を災
現するハードウェアには、一方では使用者のＣＰＵ　２
０　（第１図）とバインデイング・レジスタ・ユニット
１５と全接続するＣＰＵインターフェース８０、および
他方ではメモリ管理ユニット制御プロセッサ（第５図）
とバインデイング・レジスタ・ユニット１５とを接続す
るプロセッサ・インターフェース８１ｉ−１まれている
。バインデイング・レジスタ・ユニット１５は上述の通
り、情報が書き込まわる個々のバインデイング・レジス
タを含むバインデイング・レジスタ・ファイル８３を備
えている。バインデイング・レジスタ・ファイル８３は
ＣＰＵインターフェース８０に直結されている。芒らに
、バインデイング・レジスタ・ファイル８３は、データ
径路制御回路８４によってプロセッサ・インターフェー
ス８１に接続されている。

さらに、使用者のプロセッサから命Ａ？を受けて使用者
のＣＰＵから出される特定の命令ヲ・デコードする働ぎ
葡する命令デコーダ９０が具備されていて、ＣＰＵイン
ターフェース８０１１ＣＭ−Ｋｔさ第１ている。

命令デコーダ９０からの出力は、シーケンサ９２および
マイクロコード発生器すなわち制御ＲＯＭ　／ＲＡＭ　
９３　Ｋ向けられる。マイクロコード発生器すなわちＲ
ＯＭ　／　ＲＡＭ　９３はＭＭ［７プロセツサと共に、
バインデイング・レジスタ・ファイル８３およびデータ
径路選択回路８４の作動を制御する。

明らかになると思うが、バインデイング・レジスタ・ユ
ニット１５用の回路は、標準のＴＬＬまたはＭＳ工回路
内に作られたり、周知の方法を用いて特製のｘＪ８工ま
たはＶＴＪＢエチツプ上に作られる。上述の通り、説明
されたメモリ・アーキテクチャをもたらすバインデイン
グ・レジスタ１５の作動は、マイクロコードＲＯＭ　／
　ＲＡＭ　９３にあるマイクロコード制御プログラムの
制御を受ける。マイクロコードの設計は、使用されるメ
モリ・プロセッサの形（下記）、メモリ・システム構成
用のハードウェアの形、などのような要素に左右される
と思われる。例として、また完壁を期するために、パイ
ンディング・ユニットを含む本発明のメモリ・システム
の作動ヲシミュレートする標準リスプ（ＩＪＳＦ　）・
マシンで実行′：！−おるリスプ・プログラムが付録Ａ
に示されている。言う！でもなく、メモリ・システムを
寮施する他のいろいろな形も同じ（具合よく使用するこ
とができる。

本発明のメモリ・システム１０を構成すメモリ管理ユニ
ット１１および物理的メモリ１２を実現するハードウェ
アは、全（普通のものであり、第５図に示されている。

図示の通り、メモリ・システム１０は使用者のｃｐｔｒ
　２０　（第１図参照）に接続された前述のようなバイ
ンデイング・レジスタ・ユニット１５全含む。図示の通
り、指令、バインデイング・レジスタ、インデックス、
データ、制御、および状態の各ラインが上述のバインデ
イング・レジスタ・ユニット１５から使用者のＣＰＵ２
０に供給されている。メモリ・ユニット１１の作動は、
図示の通りバインデイング・レジスタ・ユニット１５に
接続する指◆、仮想アドレス、制御、およびデータの各
ラインを具備するプロセッサ１００によって制御される
。本発明のメモリ・システムと共に作動する物理的メモ
リのそれぞれの形により、プロセッサ１００によって制
御されるいろいろなメモリ・インターフェース装置全具
備することができる。かくて図示の通り、主メモリ１０
２は、ページ・テーブル・ユニット１０４によってバイ
ンデイング・レジスタ・ユニット１５に接続されている
。バインデイング・レジスタ・ユニット１５と物理的メ
モリ１０２との間のデータの流れは、ページ・テーブル
・ユニット１０４ｔ−ｉで、バインデイング・レジスタ
・ユニット１５と、プロセッサ１００と、ページ・テー
ブル・ユニット１０４との間に接続される指令、仮想ア
ドレス、制偽１、およびデータの各ラインを持つプロセ
ッサ１００またはバインデイング・レジスタ・ユニット
１５により制御される。さらに、本発明によるメモリ管
理ユニット１１が使用されるメモリの１つの形として、
ディスク・ユニット１０６が具備されることがある。デ
ィスク・ユニット１０６は、技術的に知られた任意の磁
気デイスク・メモリ、光学メモリまたは他の周知のディ
　　　；スフ・メモリであることができる。ディスク・
ユニット１０６はディスク制御器１０８によって制御さ
れ、またディスク制御器１０８も制御、データ、および
指令の各ラインによってプロセッサ１００により制御さ
れ、かつデータ転送のために図示の通り、データ、制御
および物理アドレスの各ラインによってバインディ、タ
グ・レジスタ・ユニット１５およびページ・テーブル・
ユニット１０４とインターフェース接続する。

注目すべきは、物理的主メモリ１０２およびディスク・
ユニット１０６が示されているが、他のメモリの形式お
よび構造も本発明の実施に等しく有利に使用できること
は当業者罠とって明らかであると思うので、本発明は上
記のよ５なメ七り形式に決して制限されないことである
。

上述のようなバインデイング・レジスタ・ユニットの作
動において、ブロック見出しには１個以上のフラグが具
備されている。少なくとも１個のフラグは、セットされ
たときにブロックに対して使用者のＣＰＵにより変化が
作られないように、ロックとして働く。これは例えは、
が−ベツジ収集その他の作用がメモリ管理ユニットで行
われている間に、ブロックがコピーされたり、移動され
たり、配列替えされたりするとき罠役立つ。

使用されるもう１つのフラグは、ブロックが結合される
か否かを決定するものである。かくて、メモリ・システ
ムがブロックを移動したり変えたりしたい場合には、そ
れはブロックがいまバインデイング・レジスタに結合さ
れているかどうかを知ることができなければならない。

さらに、バインデイング・レジスタのｓ分子ａＪのレジ
スタ部分６８におけるグロック・サイズ表示は、インデ
ックスがブロックの妥尚な長さ會越えているかどうかを
知るために必要である。

セグメント６２，６３および６４にあるＭＭＵタグは、
ブロックの見出しおよびデータ部分のいずれにも嗣み合
わされる。メモリ管理ユニットによって要求されろタグ
はバインデイング・レジスタ・ユニットによって強制さ
れるので、使用者のプロセッサはタグまたは「ポインタ
」の誉込みを妨げられ、まｆｃ％定のブロックを結合し
ようとする前にセルが実除にポインタを含んでいること
を確認するのを妨げられる。注目丁べきは、ここに説明
された形式のタグ・メモリでは、タグは使用者のプロセ
ッサによって自由にセットできないことである。かくて
、メモリ管理ユニットは使用者のプロセッサが禁止タグ
、丁なわちポインタ、見出し、まえがき等をセットしよ
うとしていないことを絶えず確認しなければならない。

か（て、各ポインタはデータがポインタを表わ丁旨を示
ｊ　ＭＭＵタグを持っているので、ブロック内のポイン
タは使用者のプロセッサによって変えることができない
。しかし使用者のプロセッサは、ポインタ基準の破壊を
もたらすデータとポインタを書き過ぎることは可能であ
るが、ポインタの変更または変形全禁止される。

上述の方法で作られたメモリ・システムでは、メモリ・
システムは多数の所定の指令によって論理アドレス・ス
ペースでアドレス可能であったり、呼出し可能である。

使用される指令には、（１）ブロック・スペースを割り
当てる指令、（２）ポインタ全論理アドレス・スペース
内の１つのバインデイング・レジスタまたはインデック
ス・ブロック・セルから別のバインデイング・レジスタ
またはブロック・セルにコピーする指令、（３）論理ア
ドレス・スペース内の２つのバインデイング・レジスタ
またはブロック・セルがいずれも（！Ｌ）同じブロック
に関するポインタを有するか（ｂｌ同じデータを有する
かを決定する「ｌｎＱ試験ｊを実行する指令、（４）規
定ブロック内のインデックス位ａｔ読む指令、および（
５）使用者のプロセッサが作ったデータ會規定ブロック
内のインデックス位置に書き込む指令、などがある。割
当て指令、コピー命令お、よび「ＥＱ試駄」は使用者の
プロセッサにメモリ・システムの構造を決定させたり、
メモリ・システムを任意な所望の構造に配列させる働き
七することが認められると思う。読み書き指令は、プロ
セッサ全メモリと相互作用させる。それでもなお、注目
丁べぎは、使用者のプロセッサが論理アドレス・スペー
スにポインタを書き込むのｔ許されないことである。他
の指令は当業者にとって明らかな通り、等しく有利に使
用されるが、上に列記された指令は本発明のメそり・シ
ステムで要求される最小限度と思われ、すなわち５つの
指令がメモリ・システムの作動を可能にするとともにそ
れ全先行技術のメモリ・システムと区別させるものと思
われる。

当業者にとっては明らかであると思うが、他の追加指令
は上述のメモリ・システムと共に容易に実行され、七の
多くは上記に規定された指令のいろいろな組合せによっ
て達成される。メモリ・システム１０は使用者のプロセ
ッサ２０とまず組み合わされる。使用者のプロセッサ２
０は、それがバインデイング・レジスタ・ユニット１５
と通信できる限り、どんな種類または形式のものでもよ
い。

制約はハードウェアの両立性の問題だけであり、メモリ
の作動、その階層、その組織などには無関係である。

使用者のプロセッサがメモリに書き込みをしたいとき、
それはまずメモリ管理ユニット１０にブロック割当て指
令を出す。ブロック割当て指令の一部として、使用者の
プロセッサは所望ブロックのサイズ全規定するとともに
、割り当てられたり作られるブロックと結合されるバイ
ンデイング・レジスタのサイズ全規定する。次にメモリ
・システムは長話されたブロックを作る。次に使用者の
プロセッサ２０は、規定されたバインデイング・レジス
タに向けられ、かつプロセッサがデータを書き込みたい
相対ブロック位置を示す、書込み指４Ｐヲ出すことがで
きる。その後、前に書き込まれたデータケ読み出したい
場合は、プロセッサ２０は、データが前に書き込まれた
オフセットに規定するその時点で、ブロックと結合され
るパインディング・レジ２夕に向けられた読みステート
メント先出す。次にメモリ管理システムは、使用者のプ
ロセッサに前に書き込まれたデータを引き渡す。

メモリ・システム１０の作動の１つの面は、割り当てら
れたブロック内にポインタ・システムの公式化および作
動を含む。かくて例えば、１つのブロック音信のブロッ
クから参照した℃・と思う場合、ポインタは参照するブ
ロックと参照されるブロックの相対アドレスで作られる
。ポインタは使用者のプロセッサによってではなく、メ
モリ管理ユニット１１によって定められ、また参照する
グロック内のインデックス相対位置に詔かれる。

（使用者のプロセッサはポインタを作ることｔＭＭυに
要請することがあるが、ＭＭＵ自体し家ポインタを作っ
て管理する。）所望の場合、使用者のプロセッサは１つ
の特定ブロックまたは２つのブロックにある２つの相対
位置が同じブロックに対するポインタを含むかどうかｔ
決定するために、メモリ・システム１０に’Ｆ、Ｑ試験
指令を出すことができる。（ＫＱ試験は、１ｎｊ−また
は異なるブロックの２つの特定な相対位置が同一データ
迎合むかどうかｔ決定するためにも使用されることがあ
る。）注目すべきば、割り当てられたブロックの相対位
置は使用者のプロセッサでは接読み出せるが、相対位置
が他のブロックに対するポインタを含む場合は、ポイン
タの読みはたとえそれらがＩＱ試験による実行で等しい
ことが示されても必ずしも一一であるとは限らない。例
えば、ブロックは明らかな異なる参照をもたら丁見えな
いポインタを含むことがある。例えばブロックＡのポイ
ンタがブロックＢ’ｌｃ指し、ブロックＣのポインタが
グロックｐｔ指し、これは順次ブロックＢｔ指すならば
、ブロックＡおよびＣのポインタは同一ブロックを指し
、したがってＫＱ、試験によって等しく・ことが示され
るが、使用者のプロセッサからデータとして見た場合は
等しく見えない。

最後に、使用者のＣＰＩ：ｒが特定のブロックに関する
丁べての操作を終えた場合、使用者のプロセッサはブロ
ックが破壊されることを要請しながらメモリ管理ユニッ
ト１１に再割当て指令を比重ことができる。メモリ管理
ユニットがこのように作られると、これまでは使用者の
プロセッサ、コンパイラ、アツセンゾラなどによって必
ず行われた多くの操作が、いまや自動的に実行されたり
災施されることが認められると思う。特に、ガーベソジ
収集は自動的に行われ、ガーベツジ収集の工程で使用者
のプロセッサの前進処理段階を止めろ必要はない。ガー
ベツジ収集法は一般に、これまで使　　　）用されてぎ
たどんな方法でもよく、その例は１９７８年４月発行の
ＡＣＭの通信第２１巻、第４号に記載さｔｔ７’ｃジー
・ベイカー・ジュニア　（Ｇ、　Ｂａｋｅｒ　、　Ｉｒ
、）手記罠よる「直列式コンピュータのリアル・タイム
なリスト処理」に示されている。メモリ・ユニット１０
の内部におけるガーベツジ収集は使用者のＣＰＨには見
えず、またそれ′とは無関係であるので、使用されるが
−ベツジ収集法は実際には効果的に、圧縮ガーベツジ収
集法であると言え、メモリ管理ユニット１０の物理的メ
モリ全一段と有効に使用させる。

さらに、割り当てられる各ブロックの長さは既知であり
かつ使用中にその（ｍ　を越えろことができないので、
メモリは使用者が例えばブロックの長もしく故意の破壊
を蒙ることを免かれる。

また注目すべきは、本発明によるメそり・システムは特
定なハードウェア実施例について説明されたが、他の実
施例は当業者にとって明らかであると思われることであ
る。さらに、本メモリは他の方法、例えはパスカル（Ｐ
ＡＳＯＡＬ　）その他のソフトウェア実施例によるソフ
トウェアで実行することができる。

最後に注目丁べきは、十分な主メモリが存在するならば
、物理的補助メモリは不要であることである。

本発明はある程度の特殊性によって説明されかつ図示さ
れたが、言５までもなく、本開示は例としてのみ行われ
、部品の組合せおよび配列のいろいろな変化は％計請求
の範囲で明記された本発明の主旨および範囲内で、当業
者によって可能である。

【図面の簡単な説明】

第１図は本発明による使用者の０ＰＵｓＴｈ理的メモリ
およびメモリ管理ユニットの相互関係のブロック図、第
２図は組み合わさ名る使用者のプロセッサからは論理メ
モリ・スペースに見えろことを示す本発明によるメそり
・システムの図、第３図は本発明のメモリ・システムの
好適な実施例ケ達成する除にメモリ管理ユニットに用い
られるバインデイング・レジスタ構造のボックス図、第
４図は本発明によるメモリ・システムを達成する際に用
いられるバインデイング・レジスタ・ユニットのボック
ス図である。第５図は本発明によるメモリシステムの総
括的ハードウェア構成のボックス図である。 符号の説明：

Claims (23)

【特許請求の範囲】
1. （１）使用者のプロセッサと組み合わされるメモリ・シ
   ステムであつて、 物理的メモリと、 前記物理的メモリを表わす論理アドレス・スペースのみ
   を呼び出すように使用者のプロセッサを制限するととも
   に使用者のプロセッサに論理アドレス・スペースのブロ
   ックを割り当てさせて、使用者供給データを割り当てら
   れた論理アドレス・スペースに書き込んだり同スペース
   から読み出し、論理アドレス・スペース内の２個のポイ
   ンタが割り当てられた論理アドレス・スペースの同一ブ
   ロックに関係があるかどうかを決定する「ＥＱテスト」
   を実行し、さらに割り当てられた論理アドレス・スペー
   ス内のポインタをコピーする、使用者のプロセッサに物
   理的メモリをインターフェース接続する装置と、 を含むことを特徴とするメモリ・システム。
2. （２）前記使用者のプロセッサとメモリ・システムとが
   別個に作動することを特徴とする特許請求の範囲第１項
   記載のメモリ・システム。
3. （３）インターフェース接続する前記装置は前記使用者
   のプロセッサと前記論理アドレス・スペースとの間に唯
   一のインターフェースを供給するバインデイング・レジ
   スタを含むことを特徴とする特許請求の範囲第１項記載
   のメモリ・システム。
4. （４）前記使用者のプロセッサはメモリのブロックを割
   り当てるとともにブロックの任意な長さを定めることが
   できることを特徴とする特許請求の範囲第１項記載のメ
   モリ・システム。
5. （５）前記使用者のプロセッサは組み合わされるブロッ
   クを識別する前記バインデイング・レジスタの１つのレ
   ジスタを規定するとともにブロック内の場所の相対イン
   デックスを規定することによつて、割り当てられた論理
   アドレス・スペースに出入するデータを伝達する、こと
   を特徴とする特許請求の範囲第４項記載のメモリ・シス
   テム。
6. （６）メモリ・システムの組織を維持するメモリ・プロ
   セッサをさらに含むことを特徴とする特許請求の範囲第
   ５項記載のメモリ・システム。
7. （７）前記物理的メモリは複数個の半導体ＲＡＭデバイ
   スと、デイスク・メモリと、デイスク制御器とを含み、
   それによつて前記メモリ・プロセッサはデイスク・メモ
   リと物理的メモリとの間の情報の流れを制御するデイス
   ク制御器の作動を制御する、ことを特徴とする特許請求
   の範囲第６項記載のメモリ・システム。
8. （８）使用者のプロセッサと組み合わされるメモリ・シ
   ステムであつて、 物理的メモリと、 物理的メモリが使用者のプロセッサにとつてバインデイ
   ング・レジスタのように見え、それによつて使用者のプ
   ロセッサにより任意に割り当られる長さのブロックは使
   用者のプロセッサによる情報の読出しおよび書込みのた
   めに呼び出されるように、物理的メモリを使用者のプロ
   セッサにインターフェース接続する装置と、 を含むことを特徴とするメモリ・システム。
9. （９）前記物理的メモリを表わす論理アドレス・スペー
   スを割り当て、論理アドレス・スペース内の１つのポイ
   ンタが別のポインタと同じ論理アドレス・スペース内の
   場所を指すかどうかを決定し、また論理アドレス・スペ
   ース内の１つの場所から別の場所までポインタをコピー
   する装置をさらに含むことを特徴とする特許請求の範囲
   第８項記載のメモリ・システム。
10. （１０）使用者のプロセッサに使用者供給データを割り
    当てられた論理アドレス・スペースに書き込ませかつ論
    理アドレス・スペースから情報を読み出させる装置をさ
    らに含むことを特徴とする特許請求の範囲第９項記載の
    メモリ・システム。
11. （１１）インターフェース接続する前記装置は前記使用
    者のプロセッサによつてアドレス可能でありかつ論理ア
    ドレス・スペースに作動的に接続されるバインデイング
    ・レジスタを含むことを特徴とする特許請求の範囲第１
    ０項記載のメモリ・システム。
12. （１２）前記使用者のプロセッサに、規定された任意な
    長さのメモリのブロックを割り当てさせる装置を含むこ
    とを特徴とする特許請求の範囲第１１項記載のメモリ・
    システム。
13. （１３）前記使用者のプロセッサは組み合わされるブロ
    ックを識別する前記バインデイング・レジスタの１つの
    レジスタを規定するとともにブロック内の場所の相対イ
    ンデックスを規定することによつて、前記メモリ・ブロ
    ックと通信することを特徴とする特許請求の範囲第１２
    項記載のメモリ・システム。
14. （１４）使用者のプロセッサがポインタ情報を割り当て
    られた論理アドレス・スペースに書き込むことができな
    いように保証する装置をさらに含むことを特徴とする特
    許請求の範囲第１３項記載のメモリ・システム。
15. （１５）使用者のプロセッサと共に使用するメモリ・シ
    ステムであつて、 物理メモリと、 メモリのブロックおよびデータ用の識別子のみを含む使
    用者のプロセッサが呼び出し得る複数個のレジスタを持
    ち、かつデータ操作のために使用者のプロセッサによつ
    て相対場所のインデックス動作を可能にするバインデイ
    ング・レジスタ・ユニットと、 物理的メモリおよびバインデイング・レジスタを操作す
    る使用者のプロセッサとは別個の装置でそれによりメモ
    リ・システムはバインデイング・レジスタ・ユニットを
    通してのみ呼び出し得る使用者規定のブロックの集合を
    使用者のプロセッサに見せかける前記装置と、 を含むことを特徴とするメモリ・システム。
16. （１６）使用者のプロセッサと組み合わされるメモリ・
    システムであつて、 使用者のプロセッサとは別個にすべてのメモリのオーバ
    ーヘッド機能を実行させる前記メモリ・システムを制御
    する装置を含むことを特徴とするメモリ・システム。
17. （１７）使用者のプロセッサと共に使用するメモリ・シ
    ステムであつて、 前記メモリ・システムを使用者のプロセッサにインター
    フェース接続するバインデイング・レジスタと、 前記バインデイング・レジスタを通してのみ前記使用者
    のプロセッサによつて呼び出し得る論理メモリ組織を作
    る装置と、 前記論理メモリにおいて前記使用者のプロセッサに応動
    して、前記使用者のプロセッサにより規定された長さの
    ブロックを作り、前記作られたブロック内の相対位置に
    情報を書き込んだり同位置から情報を読み出し、前記作
    られたブロック内の任意な２つの相対位置を試験してそ
    れらの位置が等しい内容を持つかどうかを決定し、また
    情報を前記作られたブロック内の１つの相対位置から別
    の相対位置まで移動させる装置と、 を含むことを特徴とするメモリ・システム。
18. （１８）使用者のプロセッサと共に使用するメモリ・シ
    ステムであつて、 物理的メモリと、 前記使用者のプロセッサから前記メモリ・システムまで
    呼び出しを与えるバインデイング・レジスタと、 メモリ制御ユニットとを含み、 前記メモリ制御ユニットは 前記使用者のプロセッサから前記バインデイング・レジ
    スタを通る指令に応じて、前記物理的メモリをブロック
    内に割り当てる装置と、 前記ブロックと組み合わされるブロック識別データを作
    る装置と、 前記ブロック内にポインタを作つて他のブロックを識別
    する装置と、 前記使用者のプロセッサが前記ポインタを変化させない
    ようにする装置を含むことを特徴とするメモリ・システ
    ム。
19. （１９）セットされたとき前記使用者のプロセッサによ
    る組み合わされたブロックへの関連を防止するために、
    前記ブロックと組み合わされた少なくとも１個のロック
    ・フラグを作る装置をさらに含むことを特徴とする特許
    請求の範囲第１８項記載のメモリ・システム。
20. （２０）セットされたとき前記ブロックが前記バインデ
    イング・レジスタに結合されることを表示する少なくと
    も１個の「結合」フラグをさらに含むことを特徴とする
    特許請求の範囲第１９項記載のメモリ・システム。
21. （２１）物理的メモリをブロック内に割り当てる前記装
    置はさらに、 前記バインデイング・レジスタ内に少なくとも１つのブ
    ロック識別子を供給することによつて、前記バインデイ
    ング・レジスタ内の前記割り当てられたブロックを結合
    する装置 を含むことを特徴とする特許請求の範囲第１８項記載の
    メモリ・システム。
22. （２２）前記結合装置はさらに、 前記バインデイング・レジスタ内に割り当てられたブロ
    ックの大きさを表示させる装置 を含むことを特徴とする特許請求の範囲第２１項記載の
    メモリ・システム。
23. （２３）前記ブロックと組み合わされるブロック識別デ
    ータを作る前記装置は、 結合すべきブロックに関連するポインタを識別する装置
    と、 結合すべき前記ブロック内にブロック見出しを作る装置
    と、 前記ブロック見出しを前記バインデイング・レジスタに
    複写させる装置とを含み、 それによつて前記バインデイング・レジスタは結合すべ
    きブロックの２セグメント・ブロック識別子を含む、 ことを特徴とする特許請求の範囲第１８項記載のメモリ
    ・システム。