JPS60191347A - メモリ管理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （技術分野） 本発明は、複数のプロセスがメモリを効率良くかつ高速
に使用するためのメモリ管理方式に関するものである。

（背景技術） 従来の計算機のメモリ管理方式は、以降に述べる理由に
より複数のプロセス（マルチプロセス）の実行には適し
ていない。従って、実行できるプロセス数が少なかった
り、また、プロセス数が増えると処理速度が極端に低下
するといった欠点があった。

まず、１つのプロセスを構成する情報の種類について述
べる。プロセスは、命令コード列とデータ部からなる。

命令コード列は、その名が示すように、データ部に対す
る処理の流れを表わす命令コードの列である。１つのプ
ロセスの存在中は、その命令コード列自身は、書変わら
ない。データ部は、いわゆるプログラムにおける変数を
保持するためのメモリセルである。データ部は更に静的
データ部と動的データ部に分けることができる。

静的データ部は、プロセスの存在中に、命令コード列よ
り内容の変更をうけたりするが、静的データ部のメモリ
セル自身は、存在し続ける。一方、動的データ部は、ス
タック、Ｆ　Ｉ　ＰＯ（Ｆｉｒｓｔ　ＩｎＦｉｒｓｔ　
Ｏｕｔメモリ）として用いられ、プロセス存在中に成長
したり、収縮し、その大きさが変化する。

従来のメモリ管理方式で、以上に述べたプロセスを複数
実行しようとすると、動的データ部の実現に欠点がある
。以下では、まず従来のメモリ管理方式を固定方式とマ
ツピング方式と呼ぶ２つの方式に大別し、それぞれの場
合についての欠点について述べる。

従来のメモリ管理方式はプロセスのメモリーヒでの存在
形態からみると、固定方式とマツピング方式の２つに大
別できる。固定方式とはプロセスごとにメモリ上の連続
した領域をわりあてるもので、その領域内で命令コード
列、データ部を割付ける。

ここで、命令コード列と、静的データ部はプロセスの存
在中にその大きさは変化しないので、それらに対して割
付けるメモリ領域の大きさはあらかじめ決定できる。一
方、動的データ部の大きさは、あらかじめ決定すること
はできない。そこで、この方式では、何らかの方法で動
的データ部の大きさの最大値を予測し、先の命令コード
列と静的データ部の大きさとを加え合わせたものをその
プロセスに割当てるメモリの領域とする。従ってこの方
式では、動的データ部として割当てられている領域で、
実際に使われているのはごく一部、すなわちメモリの利
用効率が悪い欠点があった。また、動的データ部が予測
した大きさを越えた場合には、それ以上プロセスを実行
できないという欠点もあった。

マツピング方式とは、メモリのアクセスをアドレス変換
テーブルを介して行うものである。この方式ではメモリ
を、例えば５１２語からなるページと呼ぶ単位に分ける
。メモリへのアクセスは、アドレス変換テーブルを用い
て論理アドレスを物理アドレスに変換して行う。論理ア
ドレスは、論理ページ番号とページ内変位からなり、物
理アドレスは物理ページ番号とページ内変位からなる。

アドレス変換テーブルは論理ページ番号をアドレス入力
とし、その論理ページが割付けられている物理ページ番
号を出力する。また、その論理ページに物理ページが未
だ割付けられていない場合には、空物理ページを割付け
る。この方式では、アドレス変換部のハードウェア量が
多いという欠点がある。また、動的データ部の成長にと
もなう物理ページの割付けは、プロセスが意識すること
なくシステムが自動的に行うが、一方、動的データ部が
収縮しても、物理ページは割付けられたままである。従
って、プロセスの実行が進むにつれてメモリの使用効率
が低下してくるという欠点があった。

以上に述べたメモリの使用効率が悪いという欠点は、メ
モリ上に同時に存在できるプロセス数の゛　上限が低い
という欠点につながる。従って、実時間性が要求される
システムでは、プロセス数の制限がきびしくなり、また
、一般の応用に対してはプロセス数が多くなると、メモ
リと２次記憶間のデータ転送量が急激に増大するために
処理速度が大幅に低下するという欠点がある。

（発明の目的） 本発明は上述した従来の問題点を解消し、動的データ部
をメモリ上に効率良くかつ高速にアクセス可能なメモリ
管理方式を提供することを目的とする。

二の目的を達成するための本発明の特徴は、１つのプロ
セスが命令コード列と静的データ部と動的データ部とか
らなり複数のプロセスを実行する計算機において、該計
算機内のメモリをリンク部とデータ部とからなるブロッ
ク単位に分け、前記リンク部はブロック間の論理的な結
合情報を保持し、前記データ部はデータを保持し、前記
動的データ部の成長、収縮にともない前記リンク部内に
保持されたブロック間の論理的な結合情報に従ってブロ
ックの割付け、解放を行ないつつ前記データ部に対する
データの書込み、読出しを行なうメモリ管理方式にある
。

（発明の構成及び作用） 第１図は、本発明におけるメモリ１の論理的構成を示し
たものである。メモリ１はブロック２と呼ぷ２ｎ（例え
ばロー５）個のセルからなる単位で分割されている。■
ブロックはリンク部３とデータ部４からなる。メモリ中
の未使用ブロック（ブロック２ａ、２ｃ、２ｄがこれに
該当するものとする）は、リンク部３を用いて矢印Ａで
示すように連鎖されている。これを空リストと呼ぷ。空
リストの先頭は、メモリ１外にあるフリーリストポイン
タ（以降ＦＰと略す）５で指示されている。

また、動的データ部として使用されているブロック（ブ
ロック２１）がこれに該当する）のリンク部３には、そ
れらの論理的関係を表わす結合情報が入っている。結合
情報の指示するものは、そのブロック２が例えばスタッ
クとして用いられているのか、ＦＩＦＯとして用いられ
ているのかにより異なる。

ここで、ブロック２の先頭セルをリンク部３、そわ以降
のセルをデータ部４とすると、１ブロツクの大きさは２
０であるので、リンク部３及びデータ部４の先頭アドレ
スの下位ｎビットのビットパターンは一意にきまる。

第２図は、本発明のメモリ１の物理的構成を示したもの
である。ここで、ＡＲ７はメモリ本体６にアドレスを供
給するアドレスレジスタ（以降ＡＲと略す）である。比
較器８はＡＲ７の保持しているアドレスがリンク部３を
示しているかどうかを検出する。このため、比較器８の
もう一方の入力は、リンク部３を表わすアドレスの下位
ｎビットのビットパターンである。比較器８は、ビット
パタ・−ンを検出すると論理値１を出力し、それ以外の
場合には論理値０を出力する。書込み信号マスク用回路
９は、比較器８の出力、メモリ６への書込み要求信号Ｗ
Ｒ１０とＤＷＲＩＩを入力とし、メモリ６・＼の書込み
信号ＷＢ］２を発生する。ここで、書込み要求は、ＷＲ
ＩＯあるいはＤＷＲＩＩの論理値を０とすることで行わ
れる。また、メモリ６への書込みはＷＥ１２が論理値Ｏ
となったときに行われる。

ＶＩＩＯとＤＷＲＩＩは同時には論理値０とならないも
のとする。リンク部３への書き込みはＶＩＩＯを論理値
０とすることで行う。ＤＶＩＩＩは、ブロック内のデー
タ部４ヘデータを書込むときに用いられるもので、第２
図に示したように比較器８の出力との論理和かとられて
いるので、ＡＲ，７がブロック中のリンク部３を示して
いるときには、Ｔ）Ｗ几１】が０となってもＷＥ］２は
０にならない。

また、比較器８の出力は、判定結果として制御部に送ら
れ、条件付きジャンプを行う時の条件として用いられる
。制御部はマイクロプログラムによって本発明の計算機
全体の制御を行う機能を有するものとする。尚、制御部
は図示していない。

Ａバス１３はＡＲ７にアドレスを供給するバスであり、
その供給元の一つにスタックポインタ１４とＦＰ５があ
る。

ここで、スタックポインタ１４の加減算と条件付きジャ
ンプは同時に行うことができるものとする。

次に、本発明の詳細な説明する。ここでは簡単の７こめ
１ブロツクは２５＝　３２語からなり、リンク部３の下
位５ビツトは０００００［２進表現〕とし、よって、デ
ータ部４の先頭セルの下位５ビツトは００００１　［２
進表現〕とする。このとき、これらのブロック２を用い
てスタックを実現した場合の動作について説明する。第
３図は、ブロック１５とブロック１６を連結して１つの
スタックを実現している論理的な図である。第４図と第
５図は、このスタックの書込み動作、すなわちブツシュ
動作と、読出し動作、すなわちポツプ動作の論理的な動
作流れ図である。

まずプツシ−動作について第４図を用いて説明する。ブ
ツシュ動作では、まず、スタックポインタ１４の下位５
ビツトがｏｏｏｏｏであるかを検査する。ｏｏｏｏｏで
ない場合は、スタックポインタ１４がデータ部４を示し
ていることになり、そのメモリセルヘデータを書込んだ
後、スタックポインタ１４の内容を１だけ加算する。す
なわち、−ブロックのデータ部４内では、アドレスの大
きくなる方へスタックが成長する。一方、ｏｏｏｏｏで
ある場合には、スタックポインタ１４がメモ１月にで隣
接する次のブロックのリンク部３を示ｊしたことになる
。従って、１ブロツクのデータ部４を全て使ったことに
なるので、フリーリストポインタ（Ｐ　ｌ）　）５につ
ながれている先頭の空きブロックを新たに、このスタッ
クのために用いることにする。この具体的な操作手順を
第６図を参照しつつ説明する。

まず、ＦＰ５の示す空ブロック１７のリンク部１８に保
持されている次の空ブロックのアドレスをＦＰ５に書込
むことによって、先頭の空ブロック１７をフリーリスト
からはずす。はずしたブロック１７のリンク部１８にス
タックポインタ１４の内容、すなわちデータ部を全て使
ったブロックの次のブロックのリンク部のアドレスを書
込む。次に、スタックポインタ１４に、ブロック１７の
データ部］９の先頭アドレスを格納する。ここまでの操
作をブロックの割付は操作と呼ぶ。この後、データを書
込み、スタックポインタ１４を加算する。以上がプツシ
−動作である。尚、ブロック１７’、　１７　’ｈそれ
ぞれスタックとして使用中のブロック及び未使用ブロッ
クである。

次にポンプ動作について、第５図を用いて説明する。ポ
ツプ動作では、まずスタックポインタ１４を１つ減算し
、その結果の下位５ビツトがｏｏｏｏ。

であるかを検査する。ｏｏｏｏｏでない場合は、スタッ
クポインタ１４で示されるメモリセルはデータ部４のセ
ルであり、読出しが行われる。一方、ｏｏｏｏｏである
場合には、スタックポインタ１４はリンク部３を示して
いる。この場合は、そのブロックのデータ部４を全て読
出したので、リンク部３で示されている論理的にスタッ
クとしてつながった次のブロックからデータを読出す必
要がある。

この操作手順を第７図を参照しつつ説明する。

まず、データ部２２を全て読出したブロックをブロック
２０とする。はじめに、スタックポインタ１４にブロッ
ク２０のリンク部２１の内容を格納する。次に、ブロッ
ク２０のリンク部２１にＦＰ５の内容を書込む。そして
ＦＰ５には、ブロック２０のリンク部２１のアドレスを
書込む。これにより、フリーリストにブロック２０が先
頭の空ブロックとしてつながれたことになり、再び使用
されるのを待つ、ここまでの操作をブロックの解放操作
と呼ぶ。さて、スタックポインタ１４はこれから読出そ
うとしているブロック頷の次のブロック２０／／／のリ
ンク部を示しているので、（何故なら、ブツシュ動作に
おいてブロック２０のリンク部２１には、次に読出すべ
きブロック加′に隣接する次のブロック２α″のリンク
部のアドレスが書込まれている）、スタックポインタ１
４を１減算した後、ブロック２０′内のデータを読出す
。以上がポンプ動作である。

以上が、プツシ−、ポツプ動作の論理的な流れであり、
各動作において、スタックポインタ１４の下位５ビツト
がｏｏｏｏｏかどうかを検査している。

従って、この検査がオーバーヘッドにならないようにす
るのが、第２図に示した書込み信号マスク用回路９の働
きである。以下では、第２図のハードウェアでプツシ−
、ポンプ動作を行う物理的な流れについて説明する。

ブツシュ動作、ポツプ動作は、メモリ６への書込み、読
出し動作にほかならない。従って、これらの動作は次の
２ステツプからなる。すなわち、第１のステップはＡ　
Ｒ７にアドレスを設定し、第２のステップはメモリ６ヘ
データを書込む、あるい５まメモリ６からデータを読出
す操作を行う。ここで、スタックポインタ１４の下位５
ピントの検査と、その結果による条件ジャンプを上記の
２ステツプにオーバーラツプさせれば、ブロックの割付
け、解放をともなわない場合はオーバーヘッドを全く生
じない。また、ブロックの割付け、解放をともなう場合
でも、その操作は以上述べたように簡単である。従って
、平均的オーバーヘッドは小さい。

ブツシュ動作について、説明する。ブツシュ動作では、
まず、第１のステップでスタックポインタ１４の内容を
ＡＲ７に書込む。次に、第２のステップで、スタックポ
インタ１４を１つ加算し、条件ジ倉ンプ命令を行い、ま
た、ＤＷＲ，１，１を０とする。

この条件ジャンプ命令は前ステップでＡＲ７に書込まれ
たスタックポインタの下位５ビツトが０ならば、ブロッ
ク割付はルーチンヘジャンプする働きをもつ。さて、も
しスタックポインタ１４の下位５ビツトが０ならば、Ｄ
ＷＲ１ｌ信号は論理値０であるが、比較器８の出力が１
となるのでメモリへの書込み信号ＷＥ］２は１のままで
書込みは行われず、ブロック割付はルーチンヘジャンプ
する。ブロック割付はルーチンにおいて、リンク部３を
書換える場合には、書込み要求信号ＶＩＩＯを論理値０
としてメモリ６への書込み動作を行なう。第１のスタッ
クポインタ１４の下位が０００００でない場合ニは、第
２のステップでＷＥ＋２が論理値Ｏとなり、ブロックの
データ部４への書込みが行われる。

以上説明したように、通常のプツシ−動作のなかに、ス
タックポインタ］４がリンク部３を示しているときは、
データを書込まずに、ブロック割付はルーチンヘジャン
プする動作を埋込んでいる。従って、ブロックの割付け
を行わない通常のブツシュ動作の場合には、オーバーヘ
ッドは生じない。

ポンプ動作について説明する。ポツプ動作では、まず第
１のステップでスタックポインタ】４を１つ減算し、そ
してその内容をＡＲ７に書込む。次に、第２ステツプで
メモリ６の内容を読出す右とともに、条件ジャンプ命令
を実行する。この条件ジャンプ命令は、第１のステップ
でＡ、　Ｒ７に書込まれたスタックポインタＪ４の内容
の下位５ビツトがＯナラばブロック解放ルーチンヘジャ
ンプする働きをもつ。下位５ビツトが０でない場合は、
メモリ６が出力した値が、スタックからポツプされたデ
ータである。

（発明の効果） 以上説明したように、本発明によれば、プロセスのスタ
ック等の動的データ部の成長、収縮にともない、メモリ
の割付け、解放を小さいオーバーヘッドで動的に行う。

従って、メモリの利用効率が良いので、多数のプロセス
をメモリ上に配置でき、処理能力が向上するという利点
がある。

本発明は、多数のプロセスをメモリ上に配置できるので
、応答性、実時間性が要求される工業用のプロセス制御
等に利用することができる。

【図面の簡単な説明】

第１図は本発明におけるメモリの論理的構成を示す図、
第２図はメモリの物理的構成を示す図、第３図はブロッ
クを連鎖させ１つのスタックを構成している図、第４図
はスタックへのブツシュ動作の流れ図、第５図はスタッ
クからのポツプ動作の流れ図、第６図はブロックの割付
は操作の説明図、第７図はブロックの解放操作の説明図
である。 ■・・・メモリ、２・・・ブロック、３・・・リンク部
、４・・・データ部、５・・・フリーリストポインタ（
ＦＰ　）、６・・・メモリ、７・・・アドレスレジスタ
（Ａ　Ｒ）、８・・・比較器、９・・・書込み信号マス
ク用回路、１０・・・リンク部への書込み要求信号（Ｗ
ａ）、１１・・・データ部への書込み要求信号（ＤＷＲ
）、１２・・・メモリへの書込み信号（ＷＥ）、１３・
・・Ａ　／’ｖス、１４・・・スタックポインタ。 特許出願人 沖電気工業株式会社 特許出願代理人 弁理士　山　本　恵　− 第４図 第５図 第６図 第７図 手続補正書（自発） 昭和５９年８月１６日 特許庁長官　古賀　学殿 １　事件の表示 昭和５９年　特許願　第４５６０３号 ２　発明の名称 メモリ管理方式 ３　補正をする者 事件との関係　特許出願人 名　称　（０２９）沖電気工業株式会社４代理人 住所　〒１０５　東京都港区西新橋１丁目５番１２号タ
ンパビル明細書の発明の詳細な説明の欄 ６　補正の内容 明細書第１５頁第９行の「のスタック」を「のステップ
でスタック」と補正する。 以上

Claims (3)

【特許請求の範囲】
1. （１）１つのプロセスが命令コード列と静的データ部と
   動的データ部とからなり複数のプロセスを実行する計算
   機において、該計算機内のメモリをリンク部とデータ部
   とからなるブロック単位に分け、前記リンク部はブロッ
   ク間の論理的な結合情報を保持し、前記データ部はデー
   タを保持し、前記動的データ部の成長、収縮にともない
   前記リンク部内に保持されたブロック間の論理的な結合
   情報に従ってブロックの割付け、解放を行ないつつ前記
   データ部に対するデータの書込み、読出しを行なうこと
   を特徴とするメモリ管理方式。
2. （２）前記ブロックの割付けは、リンク部内の結合情報
   に従って空リストとして連鎖された未使用のブロックを
   割付けることを特徴とする特許請求の範囲第１項に記載
   のメモリ管理方式。
3. （３）前記ブロックの解放は使用終了したブロックを空
   リストとするとともに、他の空リストに対し７てリンク
   部内の結合情報に従って連鎖させることを特徴とする特
   許請求の範囲第１項に記載のメモリ管理方式。