JP3299294B2

JP3299294B2 - メモリブロック制御方式

Info

Publication number: JP3299294B2
Application number: JP32745091A
Authority: JP
Inventors: 純一森内; 賢一赤松; 勝典星田
Original assignee: Fujitsu Ltd; Nippon Telegraph and Telephone Corp
Current assignee: Fujitsu Ltd; Nippon Telegraph and Telephone Corp
Priority date: 1991-12-11
Filing date: 1991-12-11
Publication date: 2002-07-08
Anticipated expiration: 2017-07-08
Also published as: JPH05158783A

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はマルチプログラミングを
サポートするオペレーティングシステムを備える情報処
理装置におけるメモリ割り当て制御方式に関する。

【０００２】マルチプログラミングをサポートするオペ
レーティングシステム（ＯＳ）では，ユーザプログラム
からのメモリ確保要求に対して速やかに割り当て可能メ
モリを検索して割り当てを行う必要がある。その場合，
ＯＳにより管理するユーザ用のメモリエリアを効率的に
利用すると共に必要なメモリブロックの割り当て及び解
放を高速に行うことが望まれている。

【０００３】

【従来の技術】図１２は従来例１の説明図，図１３は従
来例２の説明図である。図１２に示す従来例１の方法
は，(1) に示すようにメモリのユーザ領域を一定サイズ
（例えば４ＫＢ：キロバイト）のページで分割して管理
する。これらの各ページＰ０，Ｐ１，Ｐ２，Ｐ３・・・
の使用状態（使用中／未使用）を表すビットを(2) に示
すようにａ０，ａ１，ａ２，ａ３・・と割り当てて格納
してビットマップを設ける。このビットマップには, ペ
ージが使用中の時“１”が格納され，未使用の時“０”
が格納され，図１２の(3) にビットマップに実際に使用
状態を表すビット情報が格納された例を示す。ユーザか
らメモリ確保要求があると，ＯＳにより(3) に示すよう
なビットマップを参照して未使用のページを検出して，
そのページを割り当てる。

【０００４】次に図１３に示す従来例２の方法を説明す
ると，メモリをユーザが必要とするサイズを持つブロッ
クで分割する。各ブロックは，次にリンクするブロック
の先頭アドレスと使用状態（使用中／未使用）の情報及
びブロックのサイズを表す情報をブロックの管理エリア
に格納され，その後にそのブロックで実際に使用される
データエリアが設けられ，各ブロックは全て同様な構成
を備えている。この先頭アドレスのリンクにより関係付
けられたブロックは，リンクの最初の方は使用中であ
り，リンクの後の方に未使用のブロックがある。

【０００５】リンクされる順序はメモリの物理的なアド
レスと関係ない。この従来例２の場合，ユーザからのメ
モリ確保要求があると，ＯＳは先頭アドレスのリンクに
従って未使用状態のブロックを探索することにより未使
用のブロックを見つけて，ユーザに割り当てる。

【０００６】

【発明が解決しようとする課題】上記した従来例１のビ
ットマップにより管理する方法では，メモリ割り当て単
位がＯＳの管理単位に限定されてしまい，必要以上に大
きなサイズまたは小さなサイズが割り当てられるという
問題がある。また，常にビットマップを検索するため空
きメモリ検索に時間がかかるという問題があった。

【０００７】また，従来例２のリンクするブロックの先
頭を指すアドレス，サイズ等を管理用エリアに格納する
方法では，メモリ割り当て単位に対して自由度があるも
のの，使用中メモリ領域から空きメモリを検索するた
め，ビットマップによる管理以上に空きメモリ検索に時
間がかかるという問題がある。

【０００８】本発明はメモリ割り当てサイズに対しての
自由度を与えながらメモリブロックの割り当て及び解放
を高速にするメモリブロック制御方式を提供することを
目的とする。

【０００９】

【課題を解決するための手段】図１は本発明の基本構成
図である。図１において，１は処理部，２はビットマッ
プ，３は使用中のメモリページで構成するキューのキュ
ーヘッダ（ＰＱＨで表す），４はメモリである。

【００１０】処理部１内の１０はビットマップ制御部
（ＢＭＣ），１３はメモリページ制御部（ＭＰＣ），１
７はメモリブロック制御部（ＭＢＣ）である。ビットマ
ップ制御部１０は空きメモリページを取得する制御を行
う空きページ検索部（ＢＭＣ０）１１とメモリページを
解放するためのページ未使用設定部（ＢＭＣ１）１２と
を備え，メモリページ制御部１３はメモリページリンク
部（ＭＰＣ０）１４，メモリページアンリンク部（ＭＰ
Ｃ１）１５及びメモリページ検査部（ＭＰＣ２）１６と
を備え，メモリブロック制御部１７は確保要求制御部
（ＭＢＣ０）１８及び解放要求制御部（ＭＢＣ１）１９
とを備える。

【００１１】ビットマップ２は管理する各メモリページ
をそれぞれビットに対応して保持し，各ビット位置は，
それぞれメモリのページポインタを表す。初期状態では
各ビットｂ０〜ｂｎは全て“０”である。

【００１２】メモリ４は，一定のサイズを持つメモリペ
ージ（ＭＰ）５からなり，各メモリページ５は，ユーザ
が希望するサイズを持つ複数のメモリブロック（ＭＢ）
６から成る。

【００１３】各メモリページ（ＭＰ）５には，最初に使
用中メモリページによってキューを構成するための双方
向（前方と後方）のリンクポインタ（ＰＱ）５ａが，そ
の後に使用メモリブロック数カウンタ（ＵＣＮＴ）５ｂ
及び未使用メモリブロックで構成するキューの先頭を表
すキューヘッダ（ＢＱＨ）５ｃが格納されている。

【００１４】また，各メモリブロック（ＭＢ）６は，先
頭に未使用メモリブロック（ＭＢ）によりキューを構成
するための双方向リンクポインタ（ＢＱ）６ａと，自メ
モリブロックを含むメモリページの先頭を示すポインタ
（ＱＰ）６ｂが格納され，その後にユーザプログラムが
使用可能なメモリブロックのデータ領域（ＭＢＤ）６ｃ
が配置されている。

【００１５】本発明は一定の大きさのメモリ管理単位
（メモリページ）でメモリの使用・未使用を管理するメ
モリマップを設け，メモリページ内にメモリページキュ
ーを構成する双方向リンクポインタとメモリページ内に
分割された領域（メモリブロック）を設けて，その使用
量を表すブロック数カウンタとメモリブロックキューを
構成する双方向リンクポインタとそのメモリブロックが
存在するメモリページの先頭を指示するポインタを設
け，これらの各部の制御する手段によりユーザプログラ
ムからのメモリ確保要求に対して速やかに割当て可能な
メモリを検索して割り当てを行うものである。

【００１６】

【作用】プログラムからの確保要求や解放要求に対し
て，図１の処理部１においてビットマップ制御部１０，
メモリページ制御部１３及びメモリブロック制御部１７
のそれぞれに設けられた機構の中から必要なものを組み
合わせることにより実現される。以下，各制御部に設け
られた各部が備える機能を説明する。

【００１７】ビットマップ制御部１０の空きページ検索
部（ＢＭＣ０）１１は，要求によりビットマップ２を検
索して０状態（未使用）のビットを検出し，そのビット
に対応するメモリページ（ＭＰ）の先頭位置のアドレス
であるメモリページポインタ（ＭＰポインタという）を
要求元へ返送し，０状態のビットがなかった場合は要求
元へ未使用のメモリページが無いことを通知する。

【００１８】ビットマップ制御部１０のページ未使用設
定部（ＢＭＣ１）１２は，要求により要求元が指定する
メモリポインタで示されるメモリページに対応するビッ
トマップ（ＢＭ）２の中のビットを“０”にセットす
る。

【００１９】メモリページ制御部１３のメモリページリ
ンク部（ＭＰＣ０）１４は，要求により以下の処理を行
う。要求元がＭＰポインタにより指定するメモリページ
を，同じく要求元が指定するページキューヘッダ（ＰＱ
Ｈ）及び指定されたメモリページのリンクポインタ（Ｐ
Ｑ）により使用中メモリページキューの最後尾へリンク
する。

【００２０】要求元がＭＰポインタにより指定するメ
モリページ５を，同じく要求元が指定する大きさを持つ
メモリブロックに分割し，使用メモリブロック数カウン
タ（ＵＣＮＴ）５ｂを０に初期化する。

【００２１】分割した全メモリブロック６を指定され
たメモリページ内の未使用メモリブロックキューヘッダ
（ＢＱＨ）５ｃ及び各メモリブロック内の双方向リンク
ポインタ（ＢＱ）６ａによって未使用メモリブロックキ
ューを構成する。

【００２２】全メモリブロック６内に設けられた各メ
モリブロックを含むメモリページの先頭を示すポインタ
（ＱＰ）６ｂに，指定されたＭＰポインタを設定する。
メモリページ制御部１３のメモリページアンリンク部
（ＭＰＣ１）１５は，要求により要求元がＭＰポインタ
により指定するメモリページを，メモリページの双方向
リンクポインタ（ＰＱ）５ａによって使用中のメモリペ
ージキューからアンリンク（リンクから外す）する。

【００２３】メモリページ制御部１３のメモリページ検
査部（ＭＰＣ２）１６は，要求により要求元が指定する
メモリブロックサイズを用いて１メモリページの全メモ
リブロック数を算出（１ページのサイズ／指定メモリプ
ログラムサイズを算出）し，要求元が指定するページキ
ューヘッダ（ＰＱＨ）３によって使用中のメモリページ
キュー（双方向リンクポインタＰＱ）５ａを検索し，使
用メモリブロック数カウンタ（ＵＣＮＴ）５ｂがメモリ
ページ内の全メモリブロック数以内であるＭＰポインタ
を要求元に返送し，そのようなメモリページが無い場合
はその旨を通知する。

【００２４】次に，メモリブロック制御部１７の確保要
求制御部（ＭＢＣ０）１８は，要求により以下の処理を
行う。要求元が指定するページキューヘッダ（ＰＱＨ）３を
用いてメモリページ検査部（ＭＰＣ２）１６へ要求を発
生して，使用ブロック数カウンタ（ＵＣＮＴ）５ｂを用
いて要求元が指定するメモリブロック数以内のメモリペ
ージのポインタ（ＭＰポインタ）を確保する。

【００２５】メモリページ内の全メモリブロック数以
内( 全メモリブロックが使用状態ではない) の使用メモ
リブロック数カウンタ（ＵＣＮＴ）を持つメモリページ
があった場合は，次の処理を行う。

【００２６】(1) 返送されたメモリページ内の未使用メ
モリブロックのキューヘッダ（ＢＱＨ）５ｃによって示
す先頭のメモリブロックをキューからアンリンクする。 (2) 返送されたＭＰポインタが示すメモリページ内の使
用メモリブロック数カウンタ（ＵＣＮＴ）５ｂを＋１し
て更新する。

【００２７】(3) アンリンクしたメモリブロックの先頭
を示すポインタ（ＭＢポインタ）を要求元に返送する。メモリページ内の全メモリブロック数以内の使用メモ
リブロック数カウンタ（ＵＣＮＴ）を持つメモリページ
が無かった場合，次の処理を行う。

【００２８】(1) 上記した空きページ検索部（ＢＭＣ
０）１１に対し要求を発行し，ビットマップ内の０状態
であるビットに対応するメモリページのＭＰポインタを
取得する。

【００２９】(2) 取得したＭＰポインタ及び要求元が指
定するページキューヘッダ（ＰＱＨ）を用いてＭＰアン
リンク部（ＭＰＣ１）１５へ要求を発行し，取得したＭ
Ｐを使用中ＭＰキューの最後尾にリンクする。

【００３０】(3) 要求元が指定するＰＱＨを用いてメモ
リページ検査部（ＭＰＣ２）１６へ要求を発行して，使
用メモリブロック数カウンタ（ＵＣＮＴ）５ｂが，要求
元の指定するメモリブロックサイズを収容する余裕をも
つメモリページに対応するＭＰポインタを取得する。こ
の後, 上記の(1) 〜(3) と同様の処理が行われる。

【００３１】上記の(1) において，空きページ検索部
（ＭＢＣ０）１１への要求発行に対して０状態のビット
がなかったことが通知された場合，要求元へ割り当て失
敗を通知する。

【００３２】メモリブロック制御部１７の解放要求制御
部（ＭＢＣ１）１９は，要求により次の処理を行う。要求元がＭＢポインタにより指定するメモリブロック
６内のポインタ（ＱＰ）６ｂにより，指定メモリブロッ
クが存在するメモリページのＭＰポインタを取得する。

【００３３】指定するメモリブロック６内の双方向リ
ンクポインタ（ＢＱ）６ａ及び取得したＭＰポインタに
よって示されるメモリページ５内のキューヘッダ（ＢＱ
Ｈ）５ｃによって，指定メモリブロックを未使用ＭＢキ
ューにリンクする。

【００３４】取得したＭＰポインタによって示される
メモリページ内の使用メモリブロック数カウンタ（ＵＣ
ＮＴ）５ｂを−１して更新する。ＵＣＮＴが０の時は，取得したＭＰポインタを用いて
メモリページアンリンク部（ＭＰＣ１）１５へ要求を発
行し，ＭＰポインタで示されるメモリページを使用中Ｍ
Ｐキューからアンリンクし，続いてページ未使用設定部
（ＢＭＣ１）１２へ要求を発行し，ＭＰポインタで示さ
れるメモリページに対応するビットマップ２内のビット
を０に設定する。

【００３５】図１において，ユーザプログラムが希望す
る大きさのメモリ領域を確保したい場合，メモリブロッ
ク制御部１７の確保要求制御部（ＭＢＣ０）１８に対し
て，ページキューヘッダ（ＰＱＨ）及び確保するサイズ
を指定して要求を発行する。

【００３６】これに応じて確保要求制御部（ＭＢＣ０）
１８は，メモリページリンク部（ＭＰＣ０）１４，メモ
リページ検査部（ＭＰＣ２）１６及び空きページ検索部
（ＢＭＣ０）１１を制御することにより，最終的にユー
ザプログラムに対して使用可能なメモリブロックのメモ
リブロックポインタ（アドレス）を返送する。

【００３７】また，メモリ領域を解放する場合，解放要
求制御部（ＭＢＣ１）１９に対して解放するメモリブロ
ックのメモリブロックポインタを指定して要求を発行す
ると，解放要求制御部（ＭＢＣ１）１９はメモリページ
アンリンク部（ＭＰＣ１）１５及びページ未使用設定部
（ＢＭＣ１）１２を制御して指定されたメモリブロック
を解放する。

【００３８】同一サイズのメモリ確保要求がプログラム
から発行した場合，最初の要求及び未使用メモリブロッ
クがなくなり，新たなメモリページを必要とする時以外
は，殆どの場合キューを操作することにより迅速なメモ
リ確保が可能となる。

【００３９】同様に同一サイズのメモリ解放要求が発行
された場合，解放メモリブロックを含むメモリページ内
の全てのメモリブロックが未使用となり，メモリページ
そのものを解放する時以外は，キュー操作だけで行われ
るため迅速なメモリ解放が可能となる。

【００４０】さらに，ユーザブロックが複数のページキ
ューヘッダ（ＰＱＨ）を持つことにより，それぞれのペ
ージキューヘッダ毎に異なったサイズのメモリブロック
の確保・解放を行うことができる。

【００４１】

【実施例】図２はメモリの確保・解放制御のための各サ
ブルーチンとユーザプログラムの関係説明図，図３は本
発明によるメモリの構成図である。

【００４２】図２において，２０は処理装置のオペレー
ティングシステム（ＯＳ）であり，ＢＭＣ０・１１〜Ｍ
ＢＣ１・１９はＯＳ内のサブルーチンであり，それぞれ
図１の同一符号の各部に対応する。２１は処理装置のユ
ーザプログラム（ＵＰ）であり，ＰＱＨ０，ＰＱＨ１は
それぞれ異なるページキューヘッダであり，ユーザプロ
グラムによりメモリの確保・解放の要求の時に使用す
る，初期状態では０にセットされている。

【００４３】ＯＳ内のＢＭＣ０（空きページ検索部）１
１，ＭＰＣ０（メモリページリンク部）１４及びＭＰＣ
２（メモリページ検査部）１６はＭＢＣ０（確保要求制
御部）１８によりコールされ，ＢＭＣ１（ページ未使用
設定部）１２，ＭＰＣ１（メモリページアンリンク部）
１５は，ＭＢＣ１（解放要求制御部）１９からコールさ
れる。またＭＢＣ０（確保要求制御部）１８とＭＢＣ１
（解放要求制御部）１９はユーザプログラム（ＵＰ）２
１からコールされる。

【００４４】図３に示すようにメモリ（ＭＭで表示）
は，各ページＭＰ０〜ＭＰｎに分割され，各ページはユ
ーザにより要求されたサイズを持つ複数のメモリブロッ
クＭＢで構成され，先頭のメモリページＭＰ０の場合Ｍ
Ｂ００〜ＭＢ０ｍ（ｍ個に分割した例）から成る。各ペ
ージの先頭には，メモリページＭＰ０を例にすると，図
１の５ａ〜５ｃに対応するＰＱ０（ページキューの双方
向リンクポインタ），ＵＣＮＴ０（使用メモリブロック
数カウンタ），ＢＱＨ０（未使用メモリブロックのキュ
ーヘッダ）が設けられ，メモリブロックＭＢ００には図
１の６ａ〜６ｃに対応するＢＱ００（未使用メモリブロ
ックキューの双方向リンクポインタ），ＱＰ００（メモ
リページの先頭を示すポインタ）及びＭＢＤ００（メモ
リブロックのデータ領域）が格納されている。他のメモ
リブロックＭＢ０１・・・ＭＢ０ｍも同様の情報が格納
されており，他のメモリページＭＰ１・・・ＭＰｎも図
３に示すようにＭＰ０と同様の構成を備えている。

【００４５】次に上記図２に示すＯＳ２０に設けられた
各サブルーチンのフローチャートを図４乃至図９に示
す。図４は空きページ検索部（ＢＭＣ０）の処理フロ
ー，図５はページ未使用設定部（ＢＭＣ１）の処理フロ
ー，図６はメモリページリンク部（ＭＰＣ０）の処理フ
ロー，図７はメモリページアンリンク部（ＭＰＣ１）の
処理フロー及びメモリページの検査部（ＭＰＣ２）の処
理フロー，図８は確保要求制御部（ＭＢＣ０）の処理フ
ロー，図９は解放要求制御部（ＭＢＣ１）の処理フロー
である。

【００４６】図４において，空きページ検索部（ＢＭＣ
０）は入力パラメータを伴わないで起動し，出力として
ＭＰ（メモリページ）先頭アドレスが得られる。起動す
ると，ビットマップＢＭの“０”ビットを検索し（Ｓ
１），検索された“０”のビット（空きメモリページを
取得）を“１”に設定する（Ｓ２）。その検索結果のビ
ットのビット位置から，対応するＭＰ先頭アドレスを算
出し（Ｓ３），算出したＭＰ先頭アドレスを出力パラメ
ータとして設定して終了する（Ｓ４）。

【００４７】図５において，ページ未使用設定部（ＢＭ
Ｃ１）は，入力パラメータとしてＭＰ先頭アドレスを指
定し，出力として発生するものはない処理である。起動
すると，入力パラメータにより指定されたＭＰ先頭アド
レスから，対応するビットマップ内のビット位置を算出
し，算出したビットマップ内に位置するビットを“０”
に設定する。

【００４８】次に図６に示すメモリページリンク部（Ｍ
ＰＣ０）は，起動要求の時に入力パラメータとして，Ｐ
ＱＨ先頭アドレス，メモリページ（ＭＰ）先頭アドレス
及びメモリブロック（ＭＢ）サイズを指定すると，対応
するメモリページがリンクされ，そのページに指定され
たサイズの複数のメモリブロック（未使用）が形成さ
れ，各メモリブロックにそれぞれの制御情報が設定され
る。

【００４９】起動すると，入力パラメータとして指定さ
れたＭＰ先頭アドレスを用いてメモリからＰＱアドレス
（ページキューの双方向リンクポインタ）を取得する
（Ｓ１）。取得したＰＱアドレスにより，入力パラメー
タとして指定されたＭＰを同じく指定されたページキュ
ーヘッダ（ＰＱＨ）にリンクする（Ｓ２）。これにより
指定したＭＰ先頭アドレスをもつメモリページが使用中
のページキュー（ＰＱ）に追加される。

【００５０】次に入力パラメータにより指定されたＭＢ
サイズにより１メモリページ内のメモリブロック数を算
出し（Ｓ３），同じく指定されたＭＰ内の使用メモリブ
ロック数カウンタ（ＵＣＮＴ）に０を設定する（Ｓ
４）。これは，このページのメモリブロックはこの時点
では未使用であるからである。

【００５１】この後，指定のメモリページを算出したメ
モリブロック数分のメモリブロックに分割し（Ｓ５），
分割した各メモリブロック内の未使用メモリブロックキ
ューの双方向リンクポインタ（ＢＱ）を取得する（Ｓ
６）。取得したＢＱアドレス（ポインタ）により，全メ
モリブロックをメモリページ内の未使用メモリブロック
のキューヘッダ（ＢＱＨ）にリンクする（Ｓ７）。この
Ｓ５〜Ｓ７の処理によりメモリページ内の全メモリブロ
ックが空き状態にされる。

【００５２】次に分割した各メモリブロック内のＱＰ
（自メモリブロックが属するメモリページの先頭アドレ
ス）を格納すべきアドレスを取得し（Ｓ８），取得した
各アドレスに全メモリブロック内のＱＰにメモリページ
先頭アドレスを設定し（Ｓ９），終了する。

【００５３】上記のメモリページリンク部の処理におい
て実行される使用メモリページのキュー及び未使用メモ
リブロック等のキューのリンク構成を，図１０及び図１
１を用いて説明する。

【００５４】図１０にはキュー１，キュー２の２つのキ
ューが形成されている例であり，この状態をリンク前の
状態とする。この時，リンクヘッダにはキューの先頭の
キュー１のポインタを表す前方リンクと最後尾のキュー
２のポインタを表す後方リンクとで双方向ポインタが構
成される。リンクヘッダの前方リンクで示す位置にキュ
ー１が設けられ，その中に同様に双方向リンクが格納さ
れており，このキュー１の前方リンクにより示す位置に
キュー２が図１０に示すように設けられている。この状
態で，新たに別のキュー（例えば，使用メモリページや
未使用メモリブロック）をリンク対象キューとして追加
する場合の構成を図１１に示す。

【００５５】すなわち，図１１に示すように，リンク対
象キューのアドレスは，現在のリンクヘッダの前方リン
クに設定され，リンク前の状態（図１０）でリンクヘッ
ダに格納されていた前方リンクの内容をリンク対象キュ
ーの前方リンクに設定する。また，リンク前のキュー１
に格納されていた後方リンク（リンクヘッダのポイン
タ）の内容をリンク対象キューの後方リンクに設定し，
キュー１の後方リンクにリンク対象キューのアドレスが
設定される。

【００５６】次に，メモリページアンリンク部（ＭＰＣ
１）の処理フローを図７のＡ．により説明すると，この
処理は入力パラメータとしてアンリンクしたいメモリペ
ージ（ＭＰ）先頭アドレスを指定すると，そのメモリペ
ージが使用中メモリページキューからアンリンクされ
る。この場合のアンリンクの動作は，上記図１０，図１
１に説明したリンクの動作と逆の動作（図１１の状態か
ら図１０の状態にする動作）に相当する。

【００５７】起動すると，指定されたＭＰ先頭アドレス
から，メモリページ内のＰＱアドレス（双方向リンクポ
インタ）を取得し（図７のＡ．のＳ１），取得したＰＱ
アドレスを元に指定されたＭＰをＰＱＨからアンリンク
する（同Ｓ２）。

【００５８】次にメモリページの検査部（ＭＰＣ２）の
処理フローを図７のＢ．により説明すると，入力パラメ
ータとしてＰＱＨ先頭アドレス（ＰＱＨが格納されたア
ドレス）と必要なメモリブロックサイズを指定すると，
指定したメモリブロックサイズを割り当てることができ
るメモリページを探して，検出するとＭＰ先頭アドレス
を出力し，検出できない場合はその旨の検索結果を出力
する。

【００５９】図７のＢ．のメモリページ検査部が起動す
ると，指定（要求）されたメモリブロックサイズで１メ
モリページのサイズを除算して全メモリブロック数（こ
れをｚとする）を算出する（図７のＢ．のＳ１）。なお
指定されたメモリブロックサイズは既に使用されている
メモリページ内に設けたメモリブロック（ＭＢ）１個の
サイズと一致する場合や一致しない場合があり，この演
算でメモリページのメモリブロックが何個分で指定され
たメモリサイズに相当するかを求める。

【００６０】次に指定されたＰＱＨ先頭アドレスをもと
に，順次使用されている各メモリページ内のＵＣＮＴア
ドレスを取得する（同Ｓ２）。取得したＵＣＮＴアドレ
スにより，各メモリページ内のＵＣＮＴを判定し，ＵＣ
ＮＴの値が算出した１メモリページ内のメモリブロック
数（ｚ）と一致しない（但し，ＵＣＮＴ＞ｚの場合だ
け）メモリページを検索する（Ｓ３）。この検索の結
果，該当するメモリページが検索できないと，検索ＮＧ
（失敗）を出力パラメータとして設定し（Ｓ４，Ｓ
５），該当するメモリページが検索されるとその先頭ア
ドレス及び検索ＯＫ（成功）を出力パラメータとして設
定して（Ｓ６，Ｓ７），終了する。出力パラメータは要
求元に対して通知される。

【００６１】図８に示す確保要求制御部（ＭＢＣ０）の
処理フローは，ユーザプログラムからのメモリ確保要求
により起動する。入力パラメータとしてＰＱＨ先頭アド
レスと，メモリブロックサイズが指定され，この確保要
求制御部の処理の結果として確保されたメモリページの
先頭アドレスが出力される。

【００６２】図８において，最初にメモリページの検査
部（ＭＰＣ２：図７のＢ参照）を起動して要求されたサ
イズのメモリブロックをもつメモリページを検索する
（Ｓ１）。この検索の結果，該当するメモリページが無
い（ＮＧ）の場合，空きページ検索部（ＭＢＣ０：図４
参照）を起動して新たに空きメモリページ（ＭＰ）を確
保する（Ｓ３）。次いで，ＭＰリンク部（ＭＰＣ０：図
６参照）を起動して確保したメモリページ（ＭＰ）を要
求したサイズのメモリブロックで初期化し，空きメモリ
ブロックを作成する（Ｓ４）。この後，再びメモリペー
ジの検査部（ＭＰＣ２：図７のＢ参照）を起動して，空
きメモリブロックがあるメモリページを検索する（Ｓ
５）。この場合，既に空きＭＢが作成されているので要
求されたサイズのメモリブロックを持つ空きメモリペー
ジが検索される。

【００６３】上記の各ステップ（Ｓ２，Ｓ５）に続い
て，検索された結果であるＭＰ先頭アドレスをもとにメ
モリページ内のＢＱＨ（ブロックキューヘッダ）のアド
レスを取得し（Ｓ６），ＢＱＨにリンクしている先頭メ
モリブロックを未使用リンクからアンリンクし（Ｓ
７），アンリンクしたメモリブロックの先頭アドレスを
出力パラメータとして設定する（Ｓ８）。

【００６４】次に図９に示す解放要求制御部（ＭＢＣ
１）の処理フローは，上記の確保要求制御部と同様にユ
ーザブロックからのメモリ解放要求により起動する。入
力パラメータとして解放したいメモリブロックの先頭ア
ドレスが指定される。

【００６５】起動すると，最初に指定されたメモリブロ
ック先頭アドレスを元にメモリブロック内のＢＱアドレ
ス（未使用メモリブロックキューの双方向リンクポイン
タが格納された位置）を取得し（Ｓ１），同様にメモリ
ブロック内のＱＰアドレス（メモリページの先頭を示す
ポインタが格納された位置）を取得する（Ｓ２）。取得
したＱＰにより，メモリページの先頭アドレスを取得し
（Ｓ３），これをもとにメモリページ内のＢＱＨアドレ
ス（未使用メモリブロックのキューヘッダの格納位置）
を取得する（Ｓ４）。

【００６６】次いで上記Ｓ１で取得したＢＱアドレスに
より，指定されたメモリブロックをＢＱＨにリンクし
（Ｓ５），上記Ｓ３で取得したＭＰ先頭アドレスをもと
にＭＰ内のＵＣＮＴアドレスを取得し（Ｓ６），そのＵ
ＣＮＴの内容を−１にして更新する（Ｓ７）。続いて，
更新したＵＣＮＴが０か判断し（Ｓ８），０でなければ
終了し，０の場合は，メモリページアンリンク部（ＭＰ
Ｃ１：図７のＡ参照）を起動して，ＰＱＨからそのメモ
リページを解放し（Ｓ９），更にページ未使用設定部
（ＢＭＣ１：図５参照）を起動してビットマップからそ
のメモリページを解放する（Ｓ１０）。

【００６７】ここで，具体例により実施例の動作を説明
する。図２に示すユーザプログラム（以下ＵＰという）
が，ＰＱＨ０を用いて，ｘ１バイト（ｘ１はＭＰサイズ
に比較して充分小さい）のメモリブロックの確保を行う
場合，次のように動作する。この説明の中で使用するメ
モリのメモリページ，メモリブロックの符号は図３を参
照されたい。

【００６８】(1) ＵＰは入力パラメータとしてＰＱＨ０
の先頭アドレスと数値ｘ１（要求ブロックサイズ）を設
定し，確保要求制御部（ＭＢＣ０）をコールする。 (2) ＭＢＣ０はＵＰからの入力パラメータをそのまま引
き継ぎ，メモリページ検査部（ＭＰＣ２）をコールす
る。

【００６９】(3) ＭＰＣ２は，ＭＰサイズからＰＱ，Ｕ
ＣＮＴ，ＢＱＨのサイズを減算したのち，ｘ１で除算し
てメモリページ内の全メモリブロック数ｚ１を算出す
る。 (4) ＭＰＣ２は，ＰＱＨ０をキューヘッダとして，ＵＣ
ＮＴがｚ１でないＭＰを検索する。

【００７０】(5) 初期状態では, 使用ＭＰキューは空き
状態であるため，検索は失敗となり，ＭＰＣ２は０を返
送する。 (6) 確保要求制御部（ＭＢＣ０）はＭＰＣ２から０が返
送されたため，新たなＭＰを確保するため，空きページ
検索部（ＢＭＣ０）をコールする。

【００７１】(7) 初期状態ではビットマップは全て０で
あるため，ＢＭＣ０はｂ０（ビットマップの先頭ビッ
ト）を選択し，その結果対応するメモリページ０（ＭＰ
０）の先頭アドレスを返送する。

【００７２】(8) ＭＢＣ０はＵＰからの入力パラメータ
及びＢＭＣ０から返送されたＭＰ０の先頭アドレスを入
力パラメータとして設定し，メモリページリンク部（Ｍ
ＰＣ０）をコールする。

【００７３】(9) ＭＰＣ０は，ＭＰ０をＰＨＱ０へリン
クする。 (10)ＭＰＣ０はＭＰサイズ（ｙ１とする）から，ＰＱ，
ＵＣＮＴ，ＢＱＨのサイズを減算（制御情報のサイズを
除く）したのち，ｘ１で除算することでＭＰ内の全メモ
リブロック数ｚ１を算出する。

【００７４】(11)ＭＰＣ０は，ＭＰ０内のＢＱＨ０と，
ＢＱＨ０の次を先頭アドレスとするメモリブロック００
（ＭＢ００，図３参照）内のＢＱ００をリンクする。以
下，ＭＢ０ｍまでの全ＭＢをリンクし，未使用ＭＢキュ
ーを構成する。

【００７５】(12)ＭＰＣ０は，全ＭＢ内のＱＰ（ＱＰ０
０〜ＱＰ０ｍ）にＭＰ０の先頭アドレスを設定して処理
を終了する。 (13)ＭＢＣ０は，上記(2) と同様にＭＰＣ２をコールす
る。

【００７６】(14)上記(6) 〜(12)により，未使用ＭＢを
もつＭＰ０がリンクされているため，ＭＰＣ２はＭＰ０
の先頭アドレスを返送する。 (15)ＭＢＣ０は返送されたＭＰ０の先頭アドレスによ
り，ＭＰ０内のＢＱＨ０にリンクされている先頭の未使
用ＭＢ（ＭＢ００）をアンリンクする。

【００７７】(16)ＭＢＣ０はＭＢ００の先頭アドレスを
ＵＰへ返送する。この後，ＵＰがさらにＰＨＱ０を用い
て二つ目のｘ１バイトのメモリブロック（ＭＢ）を確保
する場合には，上記(1) 〜(4) を行った後,(5)において
検索成功となって(15),(16) が行われることになる。

【００７８】また，ＰＱＨ１を用いて，メモリブロック
サイズがｘ２バイトのＭＢを確保する場合も，上記の同
じ動作が行われる。次に初期状態からｘ１バイトのＭＢ
（ＭＢ００）を確保したのち，確保したＭＢを解放する
場合は以下のように行われる。

【００７９】(1) ＵＰはＭＢ００の先頭アドレスを入力
パラメータとして設定し，解放要求制御部（ＭＢＣ１）
をコールする。 (2) ＭＢＣ１は，ＭＢ００の先頭アドレスからＭＢ００
内ＢＱ００を取得し，さらにＭＢ００内ＱＰ００からＰ
Ｑ０の先頭アドレスを取得する。さらにＰＱ０の先頭ア
ドレスからＢＱＨ０を取得する。

【００８０】(3) ＭＢＣ１は，ＢＱ００及びＢＱＨ０に
よって，ＭＢ００をＭＰ０内の未使用ＭＢキューにリン
クする。 (4) ＭＢＣ１は，ＭＰ０内のＵＣＮＴ０を更新する。

【００８１】(5) 現在ＭＢ００のみ確保されてるだけな
のでＵＣＮＴ０は０となる。 (6) ＭＢＣ１はＵＣＮＴ０が０であるため，ＭＰ０を解
放するために，ＭＰ０の先頭アドレスを入力パラメータ
として設定し，ＭＰアンリンク部（ＭＰＣ１）をコール
する。

【００８２】(7) ＭＰＣ１はＭＰ０の先頭アドレスを入
力パラメータとして設定し，ＢＭＣ１をコールする。 (8) ＭＢＣ１は，ＭＰ０の先頭アドレスを入力パラメー
タとして設定し，ＢＭＣ１をコールする。

【００８３】(9) ＢＭＣ１は，ＭＰ０の先頭アドレスか
ら対応するＢＭ内のビットｂ０を０にリセットして処理
を終了する。 (10)ＭＢＣ１は処理を終了し，ＵＰへリターンする。

【００８４】また，二つのｘ１バイトのＭＢを確保した
後，ＭＢを解放する場合は，上記(1) 〜(4) を行ったの
ち,(5)でＵＣＮＴ０は０をとらないので，その時点でＵ
Ｐへリターンする。

【００８５】

【発明の効果】本発明によれば異なるサイズのメモリ確
保が可能となる上に，一般的なユーザブロックのメモリ
確保（同一サイズのメモリ領域を複数個確保する）の要
求に対して，ほとんどの場合にメモリブロックの割り当
て・解放をキュー操作だけで行うため高速な処理を実現
することができる。

【００８６】特に，近年マイクロプロセッサではそれぞ
れの計算機特有の大きさの単位（一般的には数キロバイ
ト）でのメモリ管理が充実してきており，さらに高速な
キュー操作機能を備えつつあるため，これらの計算機特
有の大きさの単位でメモリページを設定する場合に本発
明による効果は更に増大すると考えられる。

【図面の簡単な説明】

【図１】本発明の基本構成図である。

【図２】メモリの確保・解放制御のための各サブルーチ
ンとユーザプログラムの関係説明図である。

【図３】本発明によるメモリの構成図である。

【図４】空きページ検索部（ＢＭＣ０）の処理フローで
ある。

【図５】ページ未使用設定部（ＢＭＣ１）の処理フロー
である。

【図６】メモリページリンク部（ＭＰＣ０）の処理フロ
ーである。

【図７】メモリページアンリンク部（ＭＰＣ１）の処理
フロー及びメモリページの検査部（ＭＰＣ２）の処理フ
ローである。

【図８】確保要求制御部（ＭＢＣ０）の処理フローであ
る。

【図９】解放要求制御部（ＭＢＣ１）の処理フローであ
る。

【図１０】キューのリンク構成説明図（リンク前）であ
る。

【図１１】キューのリンク構成説明図（リンク後）であ
る。

【図１２】従来例１の説明図である。

【図１３】従来例２の説明図である。

【符号の説明】

１処理部２ビットマップ３使用中のメモリページで構成するキューのキュ
ーヘッダ（ＰＱＨ）４メモリ１０ビットマップ制御部（ＢＭＣ）１１空きページ検索部（ＢＭＣ０）１２ページ未使用設定部（ＢＭＣ１）１３メモリページ制御部（ＭＰＣ）１４メモリページリンク部（ＭＰＣ０）１５メモリページアンリンク部（ＭＰＣ１）１６メモリページ検査部（ＭＰＣ２）１７メモリブロック制御部（ＭＢＣ）１８確保要求制御部（ＭＢＣ０）１９解放要求制御部（ＭＢＣ１）

───────────────────────────────────────────────────── フロントページの続き (72)発明者星田勝典東京都千代田区内幸町一町目１番６号日本電信電話株式会社内 (56)参考文献特開平３−34042（ＪＰ，Ａ) 特開平１−209546（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06F 12/00 - 12/06

Claims

(57)【特許請求の範囲】

【請求項１】マルチプログラミングをサポートする処
理部を備える情報処理装置において，メモリを所定サイ
ズの複数のメモリページ単位で分割し，各メモリページ
をユーザが要求するサイズを持つ複数個のメモリブロッ
クで分割し，各メモリページは使用中のメモリページキ
ューを構成するための双方向リンクポインタ(PQ)，現在
の使用メモリブロック数を表すカウンタ(UCNT)及び未使
用メモリブロックのキューヘッダ(BQH) の各情報と複数
のメモリブロックとを備え，各メモリブロックは，未使
用メモリブロックのキューを構成する双方向リンクポイ
ンタ(BQ)と当該メモリブロックが所属するメモリページ
のポインタ(QP)の各情報とデータを格納するエリア(MB
D) を備え，各メモリページの使用状態をそれぞれ１ビ
ットで表すビットマップを設け，前記処理部はビットマ
ップを制御するビットマップ制御部，メモリページを制
御するメモリページ制御部及びユーザプログラムから発
生するメモリ確保または解放の要求に応じて前記ビット
マップ制御部とメモリページ制御部を駆動することによ
り要求されたメモリブロックの確保または解放を行うメ
モリブロック制御部とを備えることを特徴とするメモリ
ブロック制御方式。
【請求項２】請求項１において，前記ビットマップ制
御部に, 要求によりビットマップから未使用状態のメモ
リページを検索してメモリページポインタを出力する空
きページ検索部と, 要求されたメモリページに対応する
メモリページのビットを未使用状態に設定するページ未
使用設定部とを備え,前記メモリページ制御部は, 指定
されたメモリページ及びメモリブロックサイズを使用中
のメモリページのキューにリンクするメモリページリン
ク部, 指定されたメモリページを使用中メモリページキ
ューからアンリンクするメモリページアンリンク部, 要
求された条件を備えるメモリブロックを備えるメモリペ
ージのポインタを発生するメモリページの検査部とを備
えることを特徴とするメモリブロック制御方式。
【請求項３】請求項２において，前記メモリブロック
制御部は，ユーザプログラムによりメモリブロックのサ
イズ及びページキューヘッダを指定した要求により起動
して，前記空きページ検索部，メモリページリンク部及
びメモリページの検査部を駆動して要求されたサイズの
空きメモリブロックを確保して出力する確保要求制御部
と，ユーザプログラムによりメモリブロックのアドレス
を指定した要求により起動して，該メモリブロックを未
使用メモリブロックのキューにリンクして解放すると共
に，使用メモリブロック数を表すカウンタを更新し，該
カウンタ値が０の時メモリページアンリンク部及びペー
ジ未使用設定部を駆動して指定メモリブロックを解放す
る解放要求制御部とを備えることを特徴とするメモリブ
ロック制御方式。