JPH0330897B2

JPH0330897B2 -

Info

Publication number: JPH0330897B2
Application number: JP58160199A
Authority: JP
Inventors: Dei Jooji Denisu; Dei Osukii Benjamin
Original assignee: Yokogawa Hewlett Packard Ltd
Current assignee: Hewlett Packard Japan Inc
Priority date: 1982-11-12
Filing date: 1983-08-31
Publication date: 1991-05-01
Also published as: US4511964A; JPS5990281A

Description

【発明の詳細な説明】本発明は一般的には、各々がいくつかの動的構
造（dynamic structure）より成る多数の独立し
たプログラム環境（programming
environment）を有するコンピユータ・システム
におけるメモリ管理方式に関し、より具体的に
は、この発明は独立したプログラム環境相互間の
干渉を最小限度にするか、少なくとも減らすメモ
リ管理方式に関する。

コンピユータ技術で明らかな問題は、コンピユ
ータの能力を最大限に利用するようにコンピユー
タの資源を効率的に管理する必要があることであ
る。メモリの容量、計算速度および計算能力が増
大するにつれて、新世代の単一ユーザ・コンピユ
ータは多数のタスクを同時に処理することができ
るようになつてきた。単一ユーザにとつて、自分
自身のコンピユータを１つのタスクに専念させた
り、同時に多数のタスクを実行させたりするる融
通性は有益である。従つて、いくつかのタスクを
互いに干渉することなく同時に実行できる状態
（active）にすることができるメモリ管理方式を
開発することは有益である。単一ユーザ・コンピ
ユータにとつて特に重要なことは、他のプログラ
ムを実行しながらあるプログラムを入力したり、
編集したり、デバツグしたりする能力である。

この活動（active）タスクが複数存在するとい
うことはコンピユータのメモリ内の動的構造の複
雑さを増加させ、それによつて動的構造を効率的
に管理する必要性が増大する。従つて、メモリを
別のタスクに利用できるようにするためにメモリ
内のあるタスクを移動させるというような、独立
したタスク間の予期しない相互干渉を減らした
り、最小限度に押さえたりするメモリ管理方式が
必要とされている。

一般に、単一ユーザ・単一タスク・システムに
さえ利用される動的構造には各種の種類がある。
コンピユータに入力されるプログラムは、テキス
トのままの形と、機械で実行可能な形の双方でメ
モリに記憶される。また、各種のデータ構造がメ
モリに記憶される。データを後入れ先出し方式で
記憶したり呼出したりする、スタツクという特殊
なデータ構造も、一時的なデータの記憶用、また
入れ子状になつて（nested）関数やサブルーチン
を伴うプログラムのコントロール・フローの管理
用にしばしば使用される。前述のデータ構造はみ
な、メモリ割当拡張、割当解除を動作時間中に行
うことを必要とする意味で動的構造である。

利用できるメモリを最も効率的に活用するため
には、この動的構造に各一定量のメモリを割当て
るのではなく、必要とされる量だけ可変量のメモ
リを動的に割当てる必要がある。固定割当てで
は、ほとんどの場合、割当てられたメモリの大半
が結局は使用されないと共に、構造の各々に割当
てられるメモリに融通性のない上限を課すことに
なる。1979年、ジヨン・ワイリー・アンド・サン
ズ社（John Wiley and Sons）より発行され、
ブラウン（P.J.Brown）氏の「対話型コンパイラ
とインタプリンタの作成」（“Writing
Interactive Compilers and Interpreters”）とい
う表題の付された著作の77ページ以降に説明され
ているように、複数の動的構造を利用するには、
ある動的構造の情報を別の動的構造の情報に重ね
書きすることにより別の動的構造を破壊してしま
うことを避けるためのメモリ管理方式が必要であ
る。典型的な動的構造には固定端及び情報を加え
たり除去したりする可動端をそれぞれ１つ有す
る。第１Ａ図ないし第１Ｃ図に示すように、動的
構造の各対のメモリに背中合せに記憶し、各構造
の動的な端が互いに離れる方向に伸びて行くよう
にすることによつてメモリ管理を多少簡単にする
ことができる。このようなメモリ管理方式におい
ては、第１Ｂ図の構造２と３の動的な端のような
２つの動的な端がぶつかつたとき、特別な処置が
必要とされる。すなわち、メモリをこの２つの動
的な構造に利用できるようにするためには、１つ
かそれ以上の動的な構造を移動し、それによりぶ
つかり合つた２つの動的な端の間に再度空白を作
らなければならない。第１Ｃ図に示されている例
は、未使用のメモリを動的構造２と３に利用でき
るようにするために、第１Ｂ図における動的構造
１と２を上へまた動的構造３と４を下へ移動させ
た結果を示す。この方式はメモリを最大限に利用
できるものではあるが、１つかそれ以上のメモ
リ・ブロツクを移動させるという時間のかかる処
理をともなうという犠牲を支払わなければならな
い。またこの方式では、固定アドレス・ポインタ
は使用できない。すなわちメモリのブロツク移動
により、動的構造の固定端が移動したときでもす
べてのポインタが指示するアドレスは関連する動
的構造の固定端に対しての相対アドレスとなつて
いなければならない。いずれにしても、使用する
メモリの領域の拡張のために動的構造が利用でき
る空間は、アドレス空間の上限と下限を形成する
２つの境界で制限される。

別の一般的なメモリ管理方式においては、動的
構造はメモリの連続したセグメント上に生成され
る必要はなく、さらにメモリが必要となる主ルー
チンが共通のメモリのプールから制御可能な量の
メモリを取出してそれをメモリをさらに必要とし
ている動的構造に利用できるようにする。１つの
動的構造に利用できる各種のメモリ・ブロツクは
物理的に隣接している必要はなく、そのかわり
に、あるブロツクの終端をこのブロツクに論理的
に連続する次のブロツクの先頭にリンク（link）
するリンクト・リスト（linked list）構造をとつ
ている。一部のシステムでは、メモリの一部分が
使用されなくなると、その部分は自動的に共通の
メモリ・プールに戻される。この方式では、リン
クト・リスト構造を実現するために必要なポイン
タ・フイールドがメモリの一部を消費してしまう
点が欠点である。この方式ではまた、プログラム
が多数の小さなフラグメントに記憶され、それに
よつて実行中に数多くのジヤンプを必要とする。
たとえばＮ×Ｎの行列がこれらのフラグメントの
いくつかに分散して書込まれると、行列の乗算や
逆行列演算のような標準的な行列演算の実行中に
多くのジヤンプが必要とされることがある。この
ように、リンクト・リストの管理は複雑でエラー
を生じやすい。

別のメモリ管理技術においては、メモリは同一
の長さのページに分割される。1978年にプレンテ
イス・ホール社（Prentice Hall，Inc.）より発
行されたランス・A.レベンタール氏（Lance A.
Leventhal）の著になる「マイクロプロセツサ入
門：ソフトウエア，ハードウエア及びプログラミ
ング」（“Introduction to Microprocessions：
Software，Hardware and Programming”）と
いう表題の本の77ページから記載されているよう
に、ページに区分されたメモリを使用する主要な
目的は、直接アドレス指定モードでの命令のアド
レス部分の長さを短くすることである。ページに
区分するアドレス指定法においては、メモリ位置
のアドレスはそのページのページ番号とページ内
アドレスとで指定される。メモリ内のあるアドレ
スにアクセスする際、そのアドレスのページ番号
をページ・レジスタにロードし、次にページ内ア
ドレスを直接アドレス指定命令で指示する。ペー
ジ内アドレスを指示するのに必要なビツト長はえ
られたメモリ・アドレスを指示するのに必要な全
ビツト長より短いのが通例であるから、この技術
は命令のアドレス部分の長さを短縮する。

リンクト・リスト法と同様に、ページに区分し
たメモリは必要に応じて動的構造に割当てること
ができる。しかしながら、この方式も前述したリ
ンクト・リスト法の欠点の大部分のものを有す
る。すなわち、ある動作の１ページを越えるメモ
リを必要とする場合、ページ間のジヤンプごとに
ページ・レジスタ内のページ番号を変更しなけれ
ばならない。両技術は仮想メモリ環境で非効率で
ある。というのは、使用されるメモリ領域がメモ
リ全体へ分散され、それによつて仮想メモリが多
量のスワツプ・インとスワツプ・アウト動作を行
う必要があるからである。また両技術は、インデ
スク修飾、ブロツク転送、サーチングのような隣
接するいくつかのメモリ・ブロツクを処理する数
多くの技術を利用するのに適していない。従つ
て、時間を費やすブロツク転送を必要とすること
なく、しかも各構造をアドレスの連続したいくつ
かのブロツクに記憶することができる能力を失う
ことなく、動的構造を拡大したり縮小したりする
ことができるメモリ管理方式が必要とされてい
る。

本発明に従えば、パーテイシヨンと呼ばれるい
くつかの独立したプログラム環境をメモリに記憶
することができると共に、互いの動作に干渉する
ことなく同時にパーテイシヨンを利用できるよう
にするメモリ管理方式が提供される。本発明に従
えば、アドレスは２つの関連している概念的に異
なる意味・機能（すなわち論理アドレスおよび物
理アドレス）を有するものとして使われる。すな
わち、論理アドレスとは、システムが情報を読み
出したり書き込んだりする抽象的なメモリ位置を
表すためのものである。また物理アドレスとは、
データを読み出したり書き込んだりするために物
理メモリ位置をアクセスするのに利用される。

論理アドレス空間と物理アドレス空間の間の結
合は本発明のメモリ管理方式の主要な機能であ
る。論理アドレス空間と物理アドレス空間を区別
する利点は、互いに隣接するいくつかのメモリ・
ブロツクを処理するコンピユータの技術（たとえ
ば、インデクス修飾、ブロツク転送、サーチン
グ）は論理メモリ空間に対する処理であるという
点にある。従つて、必要に応じて動的構造を論理
メモリの互いに隣接するいくつかのブロツクに入
力し、そして物理メモリ上においては、多分隣接
していないいくつかのブロツクにこの動的構造を
割り当てることができる。その結果、動的構造を
拡張する際、メモリのブロツク転送を行う必要は
ない。

システムの論理アドレス空間の管理、および物
理メモリと論理アドレス空間の各部分との結合は
オペレーテイング・システム（以下、OSと称す
る）実行する。このOS、特にそのメモリ管理モ
ジユールは、メモリの割当て、拡張、割当て解除
を実施するためのサービスを行うシステムのソフ
トウエア・モジユールである。この発明の主要な
概念は、システムの論理アドレス空間の各部分を
動的に物理メモリに対応付けるために使用する技
術である。

この技術の基礎は、システムの論理アドレス空
間をパーテイシヨン論理アドレス空間（以下、パ
ーテイシヨンと称する）という個々の範囲に区分
することである。次に独立したプログラム環境の
各々に独自のパーテイシヨンが割当てられる。こ
の様な区分をすることの利点は、ある独立したプ
ログラム環境内の動的構造は、同一プログラム環
境内の他の動的構造とのみ衝突し（conflict）、
他のプログラム環境内の動的構造と衝突しないこ
とである。従来技術で説明した、動的データ構造
を固定するシステム・アドレス空間内の上端及び
下端は合計２つであつたが、この発明の区分法で
は各パーテイシヨン毎に２つ、すなわち論理アド
レス空間全体では多数の上下端が得られる。そし
て、各プログラム環境はそれ自身のパーテイシヨ
ンにある。各パーテイシヨンがシステム内の物理
メモリより大きいため、プログラム環境には新し
いメモリの制限が課されない。それにもかかわら
ず、１つのパーテイシヨンだけで有効な物理メモ
リの全部を利用することができる。

OSのメモリ管理モジユールは、各種のパーテ
イシヨンへの物理メモリの割当てを管理する。物
理メモリは必要な時のみ論理アドレス空間のブロ
ツクと結合される。メモリ管理モジユールは、特
定のパーテイシヨン内の動的構造への要求に応じ
て物理メモリをそのパーテイシヨンに割当てる。
パーテイシヨンにそのように割当てられたどの動
的構造でもその論理アドレス空間に対応して物理
メモリが確実に割当てられるようにするのがメモ
リ管理モジユールの責務である。

現在どのプログラム環境によつても使用されて
いないメモリを管理するためにシステム論理アド
レス空間の１つのパーテイシヨンが使用される。
この特別なパーテイシヨンはすべての未割当物理
メモリを含み、プログラム環境としては使用する
ことができない。あるパーテイシヨンから十分な
サイズの動的構造が割当てを解除されるか、パー
テイシヨン全体が割当てを解除されると、物理メ
モリはこの特別なパーテイシヨンに戻される。あ
るパーテイシヨンが物理メモリの拡張を要求する
と、メモリ管理モジユールは未割当物理メモリが
入つているこの特別なパーテイシヨンから新しい
メモリを必要とするパーテイシヨンに物理メモリ
を割当てる。全部の物理メモリが標準的なパーテ
イシヨンに割当てられ、そして未使用の物理メモ
リのパーテイシヨンが使い果たされたときになつ
て始めて、ある独立したパーテイシヨン内の構造
の動的割当てが別のパーテイシヨンに影響をあた
える。

論理アドレスを物理メモリに対応付ける前述の
方式は、メモリ・コントローラによつてハードウ
エア内で支援される。各メモリ・コントローラは
メモリ・チツプの密度によつて16個または32個の
物理メモリのブロツクを支援する。なお、物理メ
モリの１ブロツクは16kバイトを表す。物理メモ
リの各ブロツクにはマツパ・レジスタ対応付けら
れている。そして各マツパ・レジスタの内容はそ
のレジスタに対応付けられた物理メモリのブロツ
クがが応答すべき論理アドレスを決定する。メモ
リ・コントローラ内にあるこれらのマツパ・レジ
スタはOSのメモリ管理モジユールによつて書込
まれる。メモリ管理モジユールは、論理アドレス
を物理メモリのブロツクに対応するマツパ・レジ
スタに書込むことによつて、システムの論理アド
レス空間の任意の部分を物理メモリの特定のブロ
ツクに対応付けることができる。

以下で説明する好適な実施例においては、１個
の中央演算処理装置（以下、CPUと称する）、１
個の入出力プロセツサ（以下、IOPと称する）、
１個のメモリ・コントローラ、及びメモリ・コン
トローラに結合された等速呼出し記憶装置（以
下、RAMと称する）と固定記憶装置（以下、
ROMと称する）を含む基本システムから、いく
つかのCPU、いくつかのIPO、そして各々が４個
までのメモリ・バンクを管理する10個までのメモ
リ・コントローラを有する規膜システムまで拡張
可能である。本実施例の論理メモリ空間では16個
のメモリ・コントローラにアクセスすることがで
きようが、集積回路基板のサイズやコンピユータ
のサイズといつた物理的制約によつて物理的には
10個のメモリ・コントローラまでしかサポートさ
れない。メモリ・コントローラはメモリとシステ
ムの他の部分とのインタフエイス動作を受け持
つ。

プロセツサ相互間のまたはプロセツサとメモリ
の間の通信はすべてメモリ・プロセツサ母線（以
下、MPBと称する）を通して行われる。NPBに
接続された各CPUは、CPUとMPBの間の通信お
よび相互作用のすべてを処理するMPBインタフ
エイスを有する。これはMPBプロトコルによつ
て要求されるすべての動作を実行することによ
り、MPBのタイミングと制御をCPUから直接に
は見えない（transparent）ようにする。

メモリ・コントローラは、全部のチヤネルにつ
いてメモリの読み書きを処理する。メモリ・コン
トローラはメモリ・インタフエースとして動作
し、メモリをアクセスするのに必要なすべてのタ
イミングと制御信号を発生する。１個かそれ以上
のCPUからメモリ・コントローラへのMPBを介
しての通信によつて、論理メモリ・アドレス・ブ
ロツク番号をメモリ・コントローラ内のレジスタ
に入力することができる。これらレジスタの各々
は１ブロツクの物理メモリに対応付けられてい
る。与えられた論理ブロツクのブロツク番号をあ
る物理メモリのブロツクに対応付けられたレジス
タにロードすることによつて、その物理メモリの
ブロツクを論理メモリの与えられたブロツクに写
像（map）することができる。

システム・デバイスは、論理メモリ位置のアド
レスを有するメモリ・アクセス・ワードをMPB
上に送出することによつて、その論理メモリ位置
にアクセスする。このアドレスの第１の部分がア
クセスされべき論理メモリ位置を含む論理メモ
リ・ブロツクのブロツク番号を指示し、アドレス
の残りの部分はそのブロツクのブロツク内アドレ
スを指示する。MPB上に送出された論理メモリ
位置がメモリ・コントローラ・レジスタに入力さ
れているブロツク番号に対応すると、対応する物
理メモリ位置に対してアクセスが行われる。パー
テイシヨンという、互いの動作に対してほとんど
影響を与えない独立したいくつかの論理メモリ動
的構造を発生させるよう、論理メモリを物理メモ
リの数倍の大きさに選択する。各パーテイシヨン
はそれ自身の動的構造をいくつか有することがで
きる。各パーテイシヨンは物理メモリと同じ大き
さなので、物理メモリの全部か一部を１個のパー
テイシヨンに写像することができる。これによつ
て、物理メモリに未割当てブロツクがある限り、
他のどのパーテイシヨン内のメモリのブロツク転
送も必要とすることなく、あるパーテイシヨン内
の動的構造を拡張することができる。しかし、物
理メモリの全ブロツクが各種のパーテイシヨンに
既に割当てられている比較的まれな場合には、他
のパーテイシヨン内のメモリのブロツク転送が必
要となる。なんとなればあるパーテイシヨン内で
ブロツク転送を行い、そこで未使用領域をまとめ
ることにより、物理メモリの１個のブロツク全体
がからになることもあり、その場合にはそのから
になつた物理メモリをメモリを要求中のパーテイ
シヨンに再び割当てることができるからである。

論理メモリのパーテイシヨンは、別々のプログ
ラム群のような１組の独立した構造群（たとえ
ば、１つのジヨブのためのタスク群）を収容する
ために利用することができる。従つて、何組かの
互いに独立したプログラム群をそれぞれの群毎に
専用のパーテイシヨンに入力して同時に実行する
ことができる。物理メモリに未割当ブロツクがあ
る限り、これらのプログラム内の動的構造は他の
パーテイシヨンでプログラムをブロツク転送する
ことなく、必要に応じて拡大したり縮小したりす
ることができる。これらのプログラムは１個のプ
ロセツサを用いて時分割的に同時に実行すること
もできるし、また複数のプロセツサを利用してあ
るプログラムの実行に対する別のプログラムの実
行の影響をさらに減らすこともできる。２つのプ
ログラムの実行が相互に干渉し合うのは、２つの
プログラムが同時にメモリ・アクセス用の母線へ
のアクセスを求めている場合、あるいは物理メモ
リが既に皆割当てられているにもかかわらず、一
方のプログラムがさらにメモリを要求している場
合のみである。

マルチ・タスク・システム等の様に、表面上独
立したプログラム間で通信を行うことが有益なこ
ともある。たとえば、あるプログラムが工業プロ
セスを積極的に監視したり制御したりして、第２
のプログラムが第１のプログラムで発生されたデ
ータを分析するようにすることができる。従つ
て、本発明の好適な実施例においては、各動的構
造の間で情報を交換できるよう複数の自動構造か
らアクセスすることができる大域（global）デー
タ・セグメントを含む。

以下、図面に基いて本発明を詳細に説明する。

第２図には、動的構造間の望ましくない相互干
渉を最小限に抑えて、メモリに同時に存在する多
数の動的構造に必要に応じて動的にメモリを割当
てる本発明のメモリ管理方式による論理アドレス
と物理アドレスとの対応関係の一例を示してい
る。同図の左に示されているのはコンピユータ内
の物理メモリ位置に割当てられた物理アドレス空
間であり、この図の右に示されているのは論理ア
ドレス空間である。図示の実施例では、物理メモ
リは2²³バイト（すなわち、8388608バイト。8M
バイトと表示することもある）を有しておりこれ
らのバイトは2⁹（すなわち、512）個のブロツクに
分割され、各ブロツクは2¹⁴バイト（すなわち、
16384バイト。16kバイトと表示することもある）
を含む。同様にして、論理アドレス空間は2²⁹バ
イト（512Mバイトと表示することも多い）を有
し、これらのラミネート物は2⁶（すなわち64）個
のパーテイシヨンに分割され、各パーテイシヨン
は2⁹に（すなわち512）個のメモリ・ブロツクに
分割される。

ブロツクの大きさは物理アドレス空間と論理ア
ドレス空間の両者において同一であるので、物理
メモリは一度に１ブロツクずつ論理アドレス空間
に写像することができる。各パーテイシヨンは物
理空間と同じ大きさであるが、パーテイシヨン相
互間の望ましくない相互干渉は最小限にとどめら
れる。相互干渉を抑えることができるというわけ
は、１つのタスク（あるいはジヨブ）のためにあ
るパーテイシヨンに物理メモリ全体を割当てるこ
ともできるし、あるいはそのかわりに、複数のタ
スクの実行にあたつて、物理メモリの複数のブロ
ツクをこれらのタスクが記憶されている各種のパ
ーテイシヨンに割当てることによつて複数のタス
クの各々を独立した論理メモリ環境に置くことが
できるからである。各パーテイシヨンが物理メモ
リ空間と同じ大きさであるため、物理メモリのブ
ロツクをあるパーテイシヨンに割当てたり、この
パーテイシヨンから割当てを解除したりしても、
他のパーテイシヨン内のプログラムのブロツク移
動は必要とされない。従つて、64個のパーテイシ
ヨンは独立したプログラム環境として機能すると
共に、コンピユータが64台の仮想コンピユータを
含んでいるかのように想定してプログラムをコン
ピユータに入力することができる。

ブロツクの大きさは厳密に選択する必要はな
く、物理メモリの好都合な一部分であればよい。
論理アドレス空間の大きさは2²⁹バイトに選択す
るる。それは、この長さが32ビツトのアドレス・
ワードでアクセスすることができるためである。
なお、この32ビツトのアドレス・ワードのうち上
位３ビツトはそのワードのフアンクシヨン・コー
ドを指示するために利用する。64個のパーテイシ
ヨンががあるのは論理アドレス空間を、各々に物
理メモリ全体を割当てることができる（すなわ
ち、物理アドレス空間と同じ大きさの）パーテイ
シヨンに分割するためである。もちろんこれらの
パラメータに他の数値を選択することができる
し、集積回路技術が進展するにつれて別の選択を
する方が好都合になるであろう。

第２図に示されているように、タスクのために
必要とされるいくつかのメモリ・ブロツクは論理
アドレス空間でも物理アドレス空間でも互いに隣
接してい必要はない。たとえば、パーテイシヨン
Ａ内の論理アドレス空間の一部にあるタスクが置
かれており、ここで当初に必要とされる動的構造
として、辞書用の第１の動的構造、サブルーチン
や関数の終結後、どこへ戻るべきかを示す情報を
保持するリターン・スタツク用の第２の動的構造
があると仮定する。この場合、第２図に示す様
に、物理アドレス空間内のブロツク０と１を論理
アドレス空間内のブロツクＢ＋１に割当てて第１
の動的構造用として用い、また物理アドレス空間
内のブロツクＥを論理アドレス空間内のブロツク
Ｃに割当てて第２の動的構造用して用いることが
できる。

これらの動的構造のいずれもパーテイシヨンＡ
の先頭アドレスから始まる必要はない。従つて、
第２図においてはパーテイシヨンＡ内のブロツク
Ｂより上位のアドレス部分にギヤツプ（すなわち
未使用領域）が示されている。後にキーボード等
からのプログラムの入力中に、またはプログラム
の実行中に、動的構造１にメモリがさらに必要と
なると、物理空間から簡単にメモリを割当てるこ
とができる。これは論理アドレス空間内のブロツ
クＢ＋２への物理アドレス空間内のブロツクＦの
割当てとして第２図中に示されている。物理アド
レス空間においてブロツク１とブロツクＦの間の
ブロツクが既に他の動的構造に割当てられてしま
つているかもしれないし、また何か別の都合があ
るかもしれないので、ブロツクＦがブロツクＢ＋
１に割当てられたブロツクに物理メモリ内で隣接
する必要はない。しかし、たとえブロツク１とＦ
が物理メモリで隣接していなくとも、ブロツクＢ
とＢ＋１は論理アドレス空間内で隣接している。
連続アドレス空間についての処理に適している技
術、たとえばインデクス修飾、ブロツク転送、サ
ーチングは物理メモリ空間ではなく論理メモリ空
間を利用するため、これらの技術はこのメモリ管
理方式において利用することができる。

物理メモリの各ブロツクを論理アドレス空間の
各ブロツクに割当てるに適するハードウエアのブ
ロツク図は第３図に示されている。論理アドレス
空間への物理メモリの割当てはメモリ・コントロ
ーラと呼ばれる回路で行う。システムは１つかそ
れ以上の中央演算処理装置（CPU）、メモリプロ
セツサ母線（MPB）および最大16個のメモリ・
コントローラを含むことができ、各メモリ・コン
トローラは４個までのメモリ・バンクを制御す
る。第３図に示されている実施例では、MPB３
１は７個のCPU３２〜３８と10個のメモリ・コ
ントローラ３９〜３１８に接続され、各メモリ・
コントローラはメモリ・バンク群３１９〜３２８
のうち対応付けられた１つを制御する。各メモ
リ・バンクは実装密度に応じて16kまたは32kの
32ビツト・ワードのRAMを含む。

CPUとメモリの間、またはCPU相互間の通信
はすべてMPBを通して行われる。MPBインタフ
エイスはCPUとMPBの間のすべての通信と相互
作用を処理し、MPBプロトコルに必要なあらゆ
る動作を実行する。これにより通信のタイミング
と制御をCPUから直接には見えないようにする。

MPBは全部で８系統のチヤンネルを支援し、
MPBに接続されている各装置はチヤネル番号を
割当てられる。MPB上の優先度はチヤネル番号
に従つて決められ、小さなチヤネル番号ほど高い
優先度を有する。チヤネル０はメモリ・コントロ
ーラ用に確保されているので、メモリ・コントロ
ーラの通信はMPB上で最高の優先度を有する。
MPBを介する通信はチヤネル相互間またはチヤ
ネルとメモリの間のいずれかで行われる。メモ
リ・コントローラとの通信はチヤネル０で行われ
る。一方、メモリとの通信はメモリ・アクセス・
ワードをMPB上に与えることにより行われる。
このメモリ・アクセス・ワードは、対応する物理
アドレスに対する制御権を有するメモリ・コント
ローラによつてアクセス要求として認識されて処
理される。したがつて、メモリ・コントローラへ
のコマンドは１つかそれ以上のCPUからチヤネ
ル０経由でメモリ・コントローラに送られ、アド
レス変換用等の制御データがメモリ・コントロー
ラの内部レジスタに入力される。斯くして物理メ
モリの論理メモリ空間への写像が設定される。同
様にして、メモリ・コントローラ内のレジスタの
内容へのアクセスがチヤネル０経由で行われる。

第４図には第３図のメモリ・コントローラ３９
〜３２８の機能的ブロツク図を示す。MPB３１
は、メモリ・コントローラ信号をメモリ・コント
ローラとの間で送受するよう、メモリ・コントロ
ーラ内のMPBインタフエイス４１に接続されて
いる。MPBインタフエイス４１はMPB３１から
メモリ・コントローラ・アドレス母線４２へ送ら
れるアドレスのバツフアとして、またメモリ・コ
ントローラ・データ母線４３との間で入出力され
るデータのバツフアとして動作する。メモリ・コ
ントローラ・アドレス母線４２は、物理メモリを
各種の動的プログラム構造に動的に割当てるアド
レス・マツパ４４に接続されている。

アドレス・マツパ４４は変換されたアドレスを
メモリ・アドレス母線（以下、MABと称する）
４５に送出し、４本のチツプ選択（以下、CSと
称する）ライン４６にチツプ選択信号を送る。
CSライン４６の各々は、４個のメモリ・バンク
４７〜４１０の１個に接続され、４個のバンクは
MAB４５に並列に接続されている。メモリ・バ
ンク４７〜４１０の各々はメモリ・バンク４７内
の４つのチツプ４１１〜４１５のような16k×８
ビツト構成のメモリ・チツプを５個有する。メモ
リ・コントローラはメモリ・コントローラのコン
トロール機能の中枢であるプログラマブル・ロジ
ツク・アレイ（以下、PLAと称する）４１６も
含む。このPLA４１６はアドレスとデータの転
送を統制し、MPBインタフエイス４１を制御し、
また他のチヤネルからの内部メモリ・コントロー
ラ・レジスタへのアクセスの処理も行う。

メモリ・コントローラとメモリ・チツプの間で
データを転送するため、39ビツト幅のメモリ・デ
ータ母線４１７がドライバ／レシーバ４１８とメ
モリ・チツプとの間に接続されている。これによ
つてメモリは39ビツト・ワードを記憶することが
できる。このうち32ビツトはデータ・ビツトとし
て使用され、残７ビツトはエラーの検出／訂正用
のチエツク・ビツトとして利用される。メモリ・
バンク４７に記憶されるワードについては、各ワ
ードのバイト０，１，２および３はそれぞれチツ
プ４１１，４１２，４１３および４１４に記憶さ
れる。チツプ４１１〜４１５の各々の第１（すな
わちアドレスの先頭部の）の4kバイト（すなわ
ちチツプ４１１〜４１４からの各4kバイトのデ
ータ・ビツトおよびチツプ４１５からの4k×７
ビツトのチエツク・ビツト）によつて物理メモリ
の16kバイトの１つのブロツクが形成される。同
様にして、チツプ４１１〜４１５の各々の4kバ
イトの第２，第３および第４のブロツクによりそ
れぞれ物理メモリの他のブロツクが１つずつ形成
される。チツプ４１１〜４１５を32k×８ビツト
構成RAMに交換すれば、各バンクは８個のメモ
リ・ブロツクを含む。従つて、一種類のメモリ・
コントローラにより、16k×８ビツトおよび32k
×８ビツトの両方のチツプを制御可能とするた
め、各メモリ・コントローラは32個の物理アドレ
ス・ブロツクを制御可能である。従つて第３図で
はメモリ・コントローラ３９は物理メモリ・ブロ
ツク０〜３１の割当てを制御し、メモリ・コント
ローラ３１０は物理メモリ・ブロツク３２〜６３
の割当てを制御する。他のメモリ・コントローラ
についても同様である。システムは論理的には16
個までのメモリ・コントローラを使用できるの
で、第２図に示されている物理メモリ空間は2⁹個
のブロツクを有する。しかし、本発明の好適な実
施例は物理的に10個のメモリ・コントローラを支
援することができるだけであるので、実際の物理
メモリ空間には10×2⁵個の物理メモリのブロツク
しか実装されていない。

物理アドレス空間をどのようにして論理アドレ
ス空間に割当てるのかについては第５図および第
６図を参照して詳細に説明する。アドレス・マツ
パ４４は物理メモリを一度に１ブロツクづつ論理
アドレス空間に割当てる。第５図には、メモリを
アクセスするのに用いるメモリ・アクセス・ワー
ド内の32個のビツトの意味が示されている。
PLA４１６はメモリ・アクセスの形式を表すフ
アンクシヨン・コード用のビツト０〜２に応答す
る。このフアンクシヨン・コードはメモリがアク
セスされているのかどうか、またアクセスされて
いるのなら、フル・ワード（32ビツト）、ハー
フ・ワード（16ビツト）、バイトのどれがアクセ
スされているのかを指示する。ハーフ・ワードが
アクセスされている場合、メモリ・ワードのどち
ら半分がアクセスされているのかを指示するため
にビツト30が用いられる。バイトがアクセスされ
ている場合、ビツト30と31が１つのメモリ・ワー
ド（すなわちフル・ワード）内の４バイトのどれ
がアクセスされているのかを指示する。フアンク
シヨン・コードはまた、MPB３１上のメモリ・
アクセス・ワードがチヤネル間通信のためのチヤ
ネル間メツセージであるかどうかを指示する。こ
のチヤネル間メツセージを送出している装置をマ
スタといい、メツセージを受信している装置をス
レーブという。チヤネル間通信では、ビツト３〜
５がスレーブ・チヤネルの番号を指示し、残りの
24個のビツトがスレーブ内のアドレスを指示す
る。メモリ・コントローラがチヤネル０経由でア
クセスされた場合、ビツト６〜９はどのメモリ・
コントローラを選択すべきかを指示し、ビツト23
〜29はメモリ・コントローラ内のアドレスを選択
する。

メモリ・アクセス・ワードがMPB３１に送ら
れると、PLA４１６がアドレス・ワード内のフ
アンクシヨン・コードに応答してワードのアドレ
ス部分（すなわち、ビツト３〜29）をアドレス母
線４２を通して伝送する。ビツト３〜17はアクセ
スされるメモリ位置の論理ブロツク番号を含み、
ビツト18〜29がそのブロツク内のどのワードがア
クセスされているかを指示する。アドレス・マツ
パ４４は物理メモリの１つのブロツクを論理アド
レス空間の１つのブロツクに割当てるので、15個
のビツト３〜17だけがアドレス・マツパ４４によ
つて変換される。

アドレス・マツパ４４のブロツク図が第６図に
示されている。アドレス母線４２のアドレスはマ
ルチプレクサ６１によりアドレス・アツパ４４に
与えられる。このマルチプレクサ６１はマツパ内
容アドレス指定可能母線（以下、MCABと称す
る）６２かマツパ内部レジスタ（以下、MIRAと
称する）母線６３のどちらか一方に、メモリ・コ
ントローラ・アドレス母線４２を接続する。
MIRA母線６３は32個のマツパ内容アドレス指定
メモリ（以下、MCAMと称する）レジスタ６４
に接続される。MCAMレジスタ６４の各々はこ
のメモリ・コントローラによつて制御される４個
のメモリ・バンク内の物理メモリの１ブロツクと
対応している。これらのレジスタの各々は一致が
検知されたことを通知するマツチ・ライン６５に
よつてマツパROM６６に接続される。マツパ
ROM６６はMCAMレジスタ６４の各々とそれ
に関連付けられた物理メモリのブロツクとを対応
付ける。各MCAMレジスタ６４はまた１組の比
較器６７のうち関連付けられた比較器に接続さ
れ、この比較器はメモリ・コントローラ・アドレ
ス母線４２上の入力アドレスとそれに関連付けら
れたMCAMレジスタの内容が一致しているかど
うかをチエツクする。メモリ・アクセス・ワード
がMPB３１に送られると、メモリ・コントロー
ラ３９〜３１８の各々に設けられている比較器６
７が、同時にメモリ・アクセス・ワードのブロツ
ク番号部分（すなわち、ビツト３〜17）がそれら
に関連付けられたMCAMレジスタ６４の内容と
一致するかどうかをチエツクする。これによつて
一致の確認のため、時間をかけてMCAMレジス
タ６４を逐次的に検索することが避けられる。こ
のように１組のMCAMレジスタは、物理メモリ
のブロツクから論理メモリのブロツクへの割当て
を行う、非常に高速なルツク・アツプ・テーブル
として機能する。転送されてきた論理ブロツク番
号がメモリ・コントローラ内のMCAMレジスタ
のどの内容とも一致しないと、マツチ・ライン６
５はすべて低レベル状態にとどまる。

どの２つのMCAMレジスタも同一の内容を有
することを禁止されている。従つてどのメモリ・
コントローラをとつてみても、その中の32本のマ
ツチ・ライン６５のうち同時には高々１本だけが
１個のMCAMレジスタの内容と１個のメモリ・
アクセス・ワードに割当てられた論理ブロツク番
号の一致を指示することができるだけである。従
つて、マツチ・ライン６５を通してマツパROM
６６に加えられるゼロ以外の互いにことなる入力
は32個だけである。このマツパROM６６はこれ
ら32個の異なるゼロ以外の入力をCSライン群４
６のうちの１本に送られる高レベル状態の出力と
３ビツト・アドレスに変換し、この３ビツト・ア
ドレスは第５図に示されているようにメモリ・ア
クセス・ワードのビツト18〜21と結合してＹアド
レスを形成する。ＸアドレスとＹアドレスは２つ
のとなり合うクロツク・タイミングにおいて切換
え出力され、CSライン群４６によるメモリ・バ
ンクの選択と共に機能することにより、与えられ
た論理メモリ・アドレスに割当てられた物理メモ
リ位置をアクセスする。なお、ここで言うＸアド
レス、Ｙアドレスという用語は、標準的なダイナ
ミツクRAMのアドレス・マルチプレクシングに
おける使い方と同じ意味を持つ。第４図に示され
ているように、CSライン群４６はメモリバンク
４７〜４１０のうちどれがアクセスされるかを決
定し、マツパ・ROM６６によつて供給されるＹ
アドレスの３ビツトが、そのバンク内の物理メモ
リのどの4kバイトのブロツクがアクセスされる
のかを選択する。ＸアドレスとＹアドレスの残り
（すなわち、マツパ４４によつて写像されない部
分）は物理メモリに選択されたブロツク内部のア
クセスされるメモリ位置を選択する。メモリ・バ
ンクが32k×８ビツト構成のROMを含む場合、
マツパROM６６からの32通りの可能な出力４６
の全部が利用される。しかし、メモリ・バンクが
16k×８ビツト構成のRAMを含む場合、マツパ
ROM６６によつて発生されるＹアドレスの３ビ
ツトは０から７までではなくて、０から３までの
値しか取れない。

各MCAMレジスタ６４は16ビツト幅であり、
そのうち15ビツトはそのレジスタに対応付けられ
た物理メモリ・ブロツクに割当てられるべき論理
アドレス・ブロツク番号を記憶するために使用さ
れる。また、16番目のビツトはマツプ・アウト・
ビツトと呼ばれる。メモリ・アクセス・ワード内
のブロツク番号とMCAMレジスタ６４の内容と
を比較するのに際し、メモリ・アクセス・ワード
内のブロツク番号は、実際には第５図からもわか
るように15ビツトなのであるが、これを16番目の
ビツトが“０”になつている16ビツトであるもの
として取り扱う。従つて、マツプ・アウト・ビツ
トが“１”にセツトされると、そのMCAMレジ
スタ６４とメモリ・アクセス・ワード・ブロツク
番号との一致が起らないことが保証される。これ
によつて欠陥記憶位置を有するメモリ・ブロツク
へのアクセスを不能にすることができる。このビ
ツトはチヤネル間の通信により点検したり変換し
たりすることができる。チヤネル間通信に応答し
てMCAMレジスタの内容をMIRA母線６３を介
してアクセスし、MCAMレジスタの読み出し・
書き込みを行うことができる。これによつてこれ
らレジスタの内容を変更して動的なアドレス変更
を行うことができる。

物理メモリを論理メモリに動的に写像するため
には、どのようなメモリ割当要求が与えられても
それに応答して、写像が行われるベき物理メモリ
のブロツクを特定して選択する方法が必要であ
る。特に、未使用領域、すなわちOSやシステム
のユーザが使用するための割当がまだなされてい
ない物理メモリのブロツク、を管理するための方
法が必要である。メモリの未割当ブロツクに対応
するMCAMレジスタは既に割当てられているブ
ロツクと同じ内容を有してはいけない。さもなく
ば、その未割当ブロツクはあるメモリ・アクセ
ス・ワードによつてアクセスされてしまうことに
なる。以上の目的は、未割当メモリ管理用に設け
られている１個のパーテイシヨンに物理メモリの
未割当ブロツクの全部を写像することによつて達
成される。メモリ管理モジユールが、物理メモリ
のどのブロツクがシステムの論理アドレス空間の
どの使用可能部分にも割当てられていないかを記
憶するデータ構造を維持・管理する。

新たに物理メモリ・ブロツクの割当てが要求さ
れた場合に、どのブロツクを選択するかを容易に
決めることができるようにするため、各未割当物
理メモリ・ブロツクにそのパーテイシヨン内の異
なる論理ブロツク番号を割当てる。すなわち未割
当ブロツク管理用のパーテイシヨン内のブロツク
は、その各々に付された論理ブロツク番号の順に
編成されたリストとして管理される。そして、割
当てられるべき次の物理メモリ・ブロツクはこの
リストの一番上にあるブロツクである。このパー
テイシヨンにおいては、全物理メモリ・ブロツク
を論理アドレス空間内の１つの連続領域に写像す
る。その結果このリストの１番上を追跡すること
はプツシユダウン・スタツクの一番上を追跡する
ことと同じことになる。従つて、プツシユダウ
ン・スタツク・ポインタと同様なポインタを設け
ることによりリストの一番上の論理ブロツク番号
を常に支持させておく。一番上のブロツクに割当
てられると、このポインタは現在のリストの一番
上にある項目を示すために更新される。同様にし
て、割当てられていたメモリのブロツクが未使用
状態になると、そのブロツクはメモリ割当ての次
の要求に応えられるよう、未割当ブロツクのリス
ト（すなわちプツシユダウン・スタツク）の一番
上に写像される。

メモリ・アクセス・ワードがMPB３１に送ら
れると、メモリ・コントローラ３９〜３１８の
各々はメモリ・アクセス・ワードによつて指示さ
れる論理ブロツクがMCAMレジスタ６４のいず
れかの内容に一致するかどうかチエツクする。一
致があると、それを発見したメモリ・コントロー
ラがMPB３１に信号を送つて一致が生じたこと
を表示する。一致を検出したメモリ・コントロー
ラは次いでメモリ内のアドレス指定されたワード
にアクセスすることによつて要求のあつたメモ
リ・アクセスを完遂する。

あるパーテイシヨン内の動的構造の要求によつ
てそのパーテイシヨンが今保有している物理メモ
リより多いメモリが必要となり、また、全部の物
理メモリ・ブロツクが既に割当てられていると、
既に説明したような形で、そのパーテイシヨン内
でメモリのブロツク転送が開始される。そのパー
テイシヨンに割当てられたメモリがほぼ一杯であ
るため自パーテイシヨン内でのメモリのブロツク
転送が単なる時間の浪費であるのなら、他のパー
テイシヨンチエツクされ、そこでのブロツク転送
により物理メモリの１ブロツク全体がからになつ
て、そのブロツクをメモリ要求中のパーテイシヨ
ンに割当てることができるか否かが確かめられ
る。

各パーテイシヨンは物理メモリと同じ大きさ
（もちろん物理メモリより大きく設定してもかま
わない）であるが、一般には物理メモリの一部が
割当てられているだけであるので、論理アドレス
空間には通常以上に動的構造を入力させる余地が
ある。従つてこれによつて、パーテイシヨン内の
動的構造が隣接する動的構造によつて使用される
論理メモリまで拡大する頻度が減少する。しか
し、そのような拡大が起これば、既に説明したよ
うにメモリのブロツク転送を実行する必要があ
る。一般に、これらのブロツクに転送によつて他
のパーテイシヨンでブロツク転送が必要となるこ
とはない。同様に、あるパーテイシヨンが物理メ
モリの割当てを必要としても、通常は他のパーテ
イシヨンの論理アドレス空間内でブロツク転送が
必要となることはない。しかし、１個のパーテイ
シヨンに割当てられた物理メモリのほぼ全部が使
い尽され、物理メモリの全ブロツクが各種のパー
テイシヨンに割当てられている、というまれな場
合には、別のパーテイシヨン内部でのブロツク転
送によつて物理メモリの１ブロツク全体からにし
て、そのブロツクを次に別のパーテイシヨンに再
び割当てることができることもある。このような
他のパーテイシヨンからの侵入によつて悪影響を
受けるかもしれないプログラムを含む選択された
パーテイシヨンはプライベートであると表示する
ことによつて保護することができる。このような
プライベート・パーテイシヨンは、他のパーテイ
シヨンの必要性による論理メモリのブロツク転送
やその割当てられた物理メモリの割当ての影響を
受けることはない。

各パーテイシヨンは、１つの独立したプログラ
ム環境であり、その独立した動作のために必要と
されるコード・セグメント、セグメント・テーブ
ルおよびスタツク・セグメントのようなすべての
ソフトウエア構造を含む。各パーテイシヨンはま
た、プログラム、サブプログラムおよびプロシー
ジヤ（procedure）のような独立したプログラム
構造をその内部に含むことができる。これらの独
立した構造の各々は局所変数用の局所データ・セ
グメントを有することができる。各パーテイシヨ
ンはまたその内部のプログラム構造のいずれから
もアクセスすることができる大域データ・セグメ
ントを有する。従つて大域データ・セグメントに
より、上述の独立した構造間での情報交換が可能
となり、これによつてこれらの構造間でのある程
度の相互作用がなされる。

１個のCPUの時分割や多数のCPUを使用する
ことによつて、独立したプログラム構造を同時に
実行することができる。これは異なるパーテイシ
ヨン内の構造についても、また同じパーテイシヨ
ン内の独立したプログラム構造についても当ては
まる。多くの場合、これらの独立したプログラム
構造は独立しているが互いに関連している動作を
実行する。従つて、たとえそれが複数の動作を同
期化するためだけであつても、プログラム構造に
情報を交換する能力を付与することが有益であ
る。

【図面の簡単な説明】

第１Ａ図乃至第１Ｃ図は従来のメモリ管理方式
の問題点を説明するための図、第２図は本発明の
メモリ管理方式にかかる論理アドレスと物理アド
レスとの対応関係の一例を示す図、第３図は本発
明のメモリ管理方式を実現するコンピユータ・シ
ステムの一実施例の概略ブロツク図、第４図は第
３図中のメモリ・コントローラのブロツク図、第
５図はメモリ・アクセス・ワード中の各ビツトの
意味を説明するための図、第６図は第４図中のア
ドレス・マツパのブロツク図である。３１……メモリ・プロセツサ母線、３２〜３８
……CPU、３９〜３１８……メモリ・コントロ
ーラ、３１９〜３２８……メモリ・バンク群、４
１……MPBインタフエイス、４１６……PLA、
４２……メモリ・コントローラ・アドレス母線、
４３……メモリ・コントローラ・データ母線、４
７〜４１０……メモリ・バンク。

Claims

【特許請求の範囲】１夫々の語に論理アドレスが割り当てられたデ
ータ構造に物理メモリ位置を動的に割り当てるメ
モリ管理方式において、前記論理アドレスを入力して少なくともその一
部のフイールドを物理メモリのブロツクを指定す
るブロツク・アドレスに変更可能に写像する写像
手段と、前記論理アドレスの残余のフイールドを前記ブ
ロツク・アドレスと結合して物理アドレスを形成
することにより前記論理アドレスの写像先の物理
メモリ位置をアクセスする手段とを設け、前記論理アドレスの空間を複数のパーテイシヨ
ンに分けるとともに、物理メモリのブロツク内の
現在使用されていないものを前記論理アドレスの
空間の特定のパーテイシヨン中の互いに異なる論
理アドレスであつてかつ連続した領域に対応付け
られるように前記写像手段を設定し、前記特定のパーテイシヨン中の前記連続した領
域の端部の論理アドレスを保持し、前記物理メモリの割り当て要求に対しては前記
領域の端部に写像されている物理メモリのブロツ
クを割り当て、前記物理メモリの任意のブロツクが使用されて
いない状態になつた場合には、当該ブロツクに対
して前記特定のパーテイシヨン中の前記連続した
領域の端部に隣接する論理アドレスが写像される
ように前記写像手段を設定することを特徴とするメモリ管理方式。