JPH06309197A - 記憶領域管理方式 - Google Patents
記憶領域管理方式Info
- Publication number
- JPH06309197A JPH06309197A JP5098044A JP9804493A JPH06309197A JP H06309197 A JPH06309197 A JP H06309197A JP 5098044 A JP5098044 A JP 5098044A JP 9804493 A JP9804493 A JP 9804493A JP H06309197 A JPH06309197 A JP H06309197A
- Authority
- JP
- Japan
- Prior art keywords
- hole
- block
- size
- free list
- memory
- 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.)
- Granted
Links
Landscapes
- Memory System (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【目的】 メモリ割当及び解放処理でのリストの探索を
解消し、高速なリアルタイムＯＳのメモリ管理方式を得
る。 【構成】 メモリブロック毎に使用中か未使用かを識別
する情報を持たせた管理データを設け、メモリ解放時の
前後ブロックとの連結の必要性を、この管理データを調
べることで識別する。
解消し、高速なリアルタイムＯＳのメモリ管理方式を得
る。 【構成】 メモリブロック毎に使用中か未使用かを識別
する情報を持たせた管理データを設け、メモリ解放時の
前後ブロックとの連結の必要性を、この管理データを調
べることで識別する。
Description
【０００１】
【産業上の利用分野】本発明は、ＯＳ内の処理時間を保
証することを目的としたリアルタイムＯＳに関し、特に
任意サイズのメモリ割付及び解放を可能とするリアルタ
イムＯＳのメモリ管理方式に関する。
証することを目的としたリアルタイムＯＳに関し、特に
任意サイズのメモリ割付及び解放を可能とするリアルタ
イムＯＳのメモリ管理方式に関する。
【０００２】
【従来の技術】一般にリアルタイムＯＳでは、メモリの
効率的な管理及び利用者の要求に対する高速な応答性を
確保するために、メモリをある固定サイズのブロックで
区切り、利用者へ現在割り当てている使用中ブロック
と、割当てていない空きブロック（または使用可能ブロ
ック）とに分けて管理している。メモリ割り当て要求時
には要求サイズを満たす連続した空きブロック（以降一
つ以上の連続した空きブロックをホールと呼ぶ）を検出
し、要求サイズ分を利用者へ割り当てる。残部は新しい
ホールとして管理する。メモリ解放要求時には全空きブ
ロック中での解放位置を検出し、ブロックの断片化を防
止するため、解放要求のあるメモリ域の前後のホールと
連続しているならば結合し、新しいホールとして管理す
る。
効率的な管理及び利用者の要求に対する高速な応答性を
確保するために、メモリをある固定サイズのブロックで
区切り、利用者へ現在割り当てている使用中ブロック
と、割当てていない空きブロック（または使用可能ブロ
ック）とに分けて管理している。メモリ割り当て要求時
には要求サイズを満たす連続した空きブロック（以降一
つ以上の連続した空きブロックをホールと呼ぶ）を検出
し、要求サイズ分を利用者へ割り当てる。残部は新しい
ホールとして管理する。メモリ解放要求時には全空きブ
ロック中での解放位置を検出し、ブロックの断片化を防
止するため、解放要求のあるメモリ域の前後のホールと
連続しているならば結合し、新しいホールとして管理す
る。
【０００３】従来、このようなホールの管理として、１
９８９年４月２１日株式会社アスキー出版の「ＭＩＮＩ
Ｘオペレーティングシステム」２４２ページ〜２４４ペ
ージに記載の方式がある。この方式の１例として、図１
５にリアルタイムＯＳの保持する管理データと、メモリ
との関係を示す。図１５において、１はメモリを概念的
に示したもので、斜線部分がホール、白抜き部分が既に
割当済みのメモリブロックである。４１は１つのホール
に対して１つ対応付けられているホール管理テーブルで
あり、そのホールのサイズ及び次のホールを指すポイン
タを持つ。３は上記ホール管理テーブル４１からなるリ
ストの先頭を指すフリーリストである。リアルタイムＯ
Ｓはメモリ確保要求が発生するとフリーリスト３をもと
に検索し、要求サイズを満たすホールを検出する。この
検出したホールが要求サイズと等しい時には、フリーリ
スト３からホールを取り出し、利用者へ割り当てる。ま
た、検出したホールが要求サイズより大きい時には、要
求サイズ分利用者へ割り当て、ホールのサイズから要求
サイズを差し引く。一方、メモリの解放要求が発生する
とフリーリスト３を順に検索し、解放ホールの前後に連
続するホールがあるかを検出する。前後に連続するホー
ルがある場合にはそのホールをフリーリスト３から取り
外し、解放ホールと連結した後、再度フリーリスト３へ
繋げる。
９８９年４月２１日株式会社アスキー出版の「ＭＩＮＩ
Ｘオペレーティングシステム」２４２ページ〜２４４ペ
ージに記載の方式がある。この方式の１例として、図１
５にリアルタイムＯＳの保持する管理データと、メモリ
との関係を示す。図１５において、１はメモリを概念的
に示したもので、斜線部分がホール、白抜き部分が既に
割当済みのメモリブロックである。４１は１つのホール
に対して１つ対応付けられているホール管理テーブルで
あり、そのホールのサイズ及び次のホールを指すポイン
タを持つ。３は上記ホール管理テーブル４１からなるリ
ストの先頭を指すフリーリストである。リアルタイムＯ
Ｓはメモリ確保要求が発生するとフリーリスト３をもと
に検索し、要求サイズを満たすホールを検出する。この
検出したホールが要求サイズと等しい時には、フリーリ
スト３からホールを取り出し、利用者へ割り当てる。ま
た、検出したホールが要求サイズより大きい時には、要
求サイズ分利用者へ割り当て、ホールのサイズから要求
サイズを差し引く。一方、メモリの解放要求が発生する
とフリーリスト３を順に検索し、解放ホールの前後に連
続するホールがあるかを検出する。前後に連続するホー
ルがある場合にはそのホールをフリーリスト３から取り
外し、解放ホールと連結した後、再度フリーリスト３へ
繋げる。
【０００４】
【発明が解決しようとする課題】ところが上記メモリ管
理方式においては、メモリの割当時には要求サイズを満
たすホールを検出するために、また解放時には、前後の
ホールとの連結のために解放メモリ域の解放位置を検出
するために、フリーリストの探索が必要であった。その
ため、フリーリストの先頭近くに所望のホールが繋がれ
ている場合には高速だが、最後尾に近いホールで初めて
所望のホールが検出される場合には検索時間が長くな
り、ＣＰＵの占有時間が長くなるという問題があった。
理方式においては、メモリの割当時には要求サイズを満
たすホールを検出するために、また解放時には、前後の
ホールとの連結のために解放メモリ域の解放位置を検出
するために、フリーリストの探索が必要であった。その
ため、フリーリストの先頭近くに所望のホールが繋がれ
ている場合には高速だが、最後尾に近いホールで初めて
所望のホールが検出される場合には検索時間が長くな
り、ＣＰＵの占有時間が長くなるという問題があった。
【０００５】本発明は上記問題点を鑑みてなされたもの
で、メモリ割り当て及び解放時に、フリーリストの検索
を不要とし、効率の良いメモリ管理を提供するものであ
る。
で、メモリ割り当て及び解放時に、フリーリストの検索
を不要とし、効率の良いメモリ管理を提供するものであ
る。
【０００６】
【課題を解決するための手段】請求項１に記載の発明に
係る記憶領域管理方式は、記憶装置を固定長サイズのブ
ロックに分割して、使用中のブロックと未使用のブロッ
クに分け、一つ以上の連続した未使用のブロックをホー
ルとして管理する記憶領域管理方式において、下記の要
素を有するものである。 （ａ）前記ホールをリストとして管理するためのフリー
リスト （ｂ）分割されたブロックに対応して存在し、少なくと
もそのサイズと次ホールの先頭を指すポインターと使用
中か否かを示すフラグを格納するブロック管理テーブル （ｃ）記憶領域の解放時に解放するブロックの前後の前
記フラグを参照してそのブロックがホールか否かを判定
する手段 （ｄ）前記フラグの状態を判定する手段により判定した
結果を用いてブロック管理テーブルをメンテナンスする
手段。
係る記憶領域管理方式は、記憶装置を固定長サイズのブ
ロックに分割して、使用中のブロックと未使用のブロッ
クに分け、一つ以上の連続した未使用のブロックをホー
ルとして管理する記憶領域管理方式において、下記の要
素を有するものである。 （ａ）前記ホールをリストとして管理するためのフリー
リスト （ｂ）分割されたブロックに対応して存在し、少なくと
もそのサイズと次ホールの先頭を指すポインターと使用
中か否かを示すフラグを格納するブロック管理テーブル （ｃ）記憶領域の解放時に解放するブロックの前後の前
記フラグを参照してそのブロックがホールか否かを判定
する手段 （ｄ）前記フラグの状態を判定する手段により判定した
結果を用いてブロック管理テーブルをメンテナンスする
手段。
【０００７】請求項２に記載の発明に係る記憶領域管理
方式は、記憶装置を固定長サイズのブロックに分割し
て、使用中のブロックと未使用のブロックに分け、一つ
以上の連続した未使用のブロックをホールとして管理す
る記憶領域管理方式において、下記の要素を有するもの
である。 （ａ）前記ホールをリストとして管理するＮ個のフリー
リストからなるフリーリスト群 （ｂ）前記フリーリストよりポイントされ、ホールを管
理する少なくともそのサイズ、次のホールを示すための
ポインターおよび対応する記憶装置上のアドレスから成
るホール管理データ群 （ｃ）前記フリーリスト群のｋ番目のフリーリストには
下記の式を満足するホールを管理する前記ホール管理デ
ータをポインターで接続する手段 ０≦ｋ≦Ｎ、 ２k ≦ ホールのサイズ ＜２k+1 （ｄ）記憶領域の割当処理時において下記の式を満足す
るフリーリストｎにポイントされている先頭のホールを
割り当てる手段。 １≦ｎ≦Ｎ、 ２n-1 ≦ 割り当てる記憶サイズ ＜２
n
方式は、記憶装置を固定長サイズのブロックに分割し
て、使用中のブロックと未使用のブロックに分け、一つ
以上の連続した未使用のブロックをホールとして管理す
る記憶領域管理方式において、下記の要素を有するもの
である。 （ａ）前記ホールをリストとして管理するＮ個のフリー
リストからなるフリーリスト群 （ｂ）前記フリーリストよりポイントされ、ホールを管
理する少なくともそのサイズ、次のホールを示すための
ポインターおよび対応する記憶装置上のアドレスから成
るホール管理データ群 （ｃ）前記フリーリスト群のｋ番目のフリーリストには
下記の式を満足するホールを管理する前記ホール管理デ
ータをポインターで接続する手段 ０≦ｋ≦Ｎ、 ２k ≦ ホールのサイズ ＜２k+1 （ｄ）記憶領域の割当処理時において下記の式を満足す
るフリーリストｎにポイントされている先頭のホールを
割り当てる手段。 １≦ｎ≦Ｎ、 ２n-1 ≦ 割り当てる記憶サイズ ＜２
n
【０００８】請求項３に記載の発明に係る記憶領域管理
方式は、前記請求項２に記載の発明に加えて、前記フリ
ーリスト群の各々に前記ホール管理データが存在するか
否かを示すフラグを有するリスト管理テーブルを前記フ
リーリスト群に対応して設けたものである。
方式は、前記請求項２に記載の発明に加えて、前記フリ
ーリスト群の各々に前記ホール管理データが存在するか
否かを示すフラグを有するリスト管理テーブルを前記フ
リーリスト群に対応して設けたものである。
【０００９】
【作用】請求項１に記載の発明に係る記憶領域管理方式
においては、分割されたブロックと１対１に対応するブ
ロック管理テーブルにサイズ等と共に使用中か否かを示
すフラグを設けたことに特徴がある。このことにより、
記憶領域の解放時に解放する領域の前後のブロックのフ
ラグを参照して解放処理を行うことができるので処理の
高速化が図れる。
においては、分割されたブロックと１対１に対応するブ
ロック管理テーブルにサイズ等と共に使用中か否かを示
すフラグを設けたことに特徴がある。このことにより、
記憶領域の解放時に解放する領域の前後のブロックのフ
ラグを参照して解放処理を行うことができるので処理の
高速化が図れる。
【００１０】請求項２に記載の発明に係る記憶領域管理
方式においては、ホールのサイズを（２n ≦ ホールの
サイズ ＜２n+1 ）の区分で分類し、ｎを指標として持
つフリーリストの群である冪乗番号リストを設けたこと
に特徴がある。このようにして記憶領域の割り当て要求
時には要求サイズを満たすホールの繋がれている冪乗番
号リストを要求サイズから求め、そのリストの先頭ホー
ルを所望のホールとしてリストからはずし、要求サイズ
を割り当てた後、残部を再度冪乗番号リストへ返却す
る。記憶領域の解放要求時には、解放要求の前後のホー
ルと連結可能であれば、連結し、その後解放領域のサイ
ズから繋げるべき冪乗番号リストを求め、そのリストの
最後尾に繋げる。このようにして特に記憶領域の割り当
て処理の高速化が図れる。
方式においては、ホールのサイズを（２n ≦ ホールの
サイズ ＜２n+1 ）の区分で分類し、ｎを指標として持
つフリーリストの群である冪乗番号リストを設けたこと
に特徴がある。このようにして記憶領域の割り当て要求
時には要求サイズを満たすホールの繋がれている冪乗番
号リストを要求サイズから求め、そのリストの先頭ホー
ルを所望のホールとしてリストからはずし、要求サイズ
を割り当てた後、残部を再度冪乗番号リストへ返却す
る。記憶領域の解放要求時には、解放要求の前後のホー
ルと連結可能であれば、連結し、その後解放領域のサイ
ズから繋げるべき冪乗番号リストを求め、そのリストの
最後尾に繋げる。このようにして特に記憶領域の割り当
て処理の高速化が図れる。
【００１１】請求項３に記載の発明に係る記憶領域管理
方式においては、請求項２に記載の発明に加えて、フリ
ーリスト群の各々に対応したリスト管理テーブルを設け
たことに特徴がある。このことにより所望のホールの繋
がれている冪乗番号リストを検出するために、冪乗リス
トの探索ではなく、リスト管理テーブルのフラグチェッ
クにより可能として、更なる処理の高速化を可能とす
る。
方式においては、請求項２に記載の発明に加えて、フリ
ーリスト群の各々に対応したリスト管理テーブルを設け
たことに特徴がある。このことにより所望のホールの繋
がれている冪乗番号リストを検出するために、冪乗リス
トの探索ではなく、リスト管理テーブルのフラグチェッ
クにより可能として、更なる処理の高速化を可能とす
る。
【００１２】
実施例１ 本発明の１実施例について説明する。図１は、本発明に
係る記憶領域管理方式における、管理データ及びメモリ
との関連図であり、図において１は概念的に記述したメ
モリで、従来例と同じく一定サイズのブロックに分割さ
れ、使用中のブロック（白抜き部分）と未使用のブロッ
ク（斜線部分）に分かれ、連続した未使用ブロックは１
つのホールとして管理されている。
係る記憶領域管理方式における、管理データ及びメモリ
との関連図であり、図において１は概念的に記述したメ
モリで、従来例と同じく一定サイズのブロックに分割さ
れ、使用中のブロック（白抜き部分）と未使用のブロッ
ク（斜線部分）に分かれ、連続した未使用ブロックは１
つのホールとして管理されている。
【００１３】２は上記ブロックの個々に対応付けられた
ブロック管理データ群で、次のホールの先頭ブロックの
ブロック管理データを指し示すｎｅｘｔと、ホールのサ
イズを示すｓｉｚｅと、ホールの最後尾ブロックならＦ
が、それ以外ならＵが、格納されているｆｌａｇの情報
から構成される。
ブロック管理データ群で、次のホールの先頭ブロックの
ブロック管理データを指し示すｎｅｘｔと、ホールのサ
イズを示すｓｉｚｅと、ホールの最後尾ブロックならＦ
が、それ以外ならＵが、格納されているｆｌａｇの情報
から構成される。
【００１４】３はホールを繋げたリストの先頭ブロック
管理データを指し示すフリーリストである。本実施例に
おいてメモリの割り付け発生時の処理は従来例と同じ
く、フリーリストの検索によって所望のホールを検出す
る。
管理データを指し示すフリーリストである。本実施例に
おいてメモリの割り付け発生時の処理は従来例と同じ
く、フリーリストの検索によって所望のホールを検出す
る。
【００１５】次にメモリ領域の解放要求が発生した時の
メモリ管理の動作について図１及び図２のフローチャー
トに沿って説明する。図１において例えばブロック２２
（対応するブロック管理データは図１のＢ２２）の解放
要求が発生した場合、まず、ブロック２２の直前のブロ
ック２１のブロック管理データＢ２１の情報を調べ（ス
テップ１０）、ｆｌａｇ情報がＦであるため（ステップ
１１）、直前のホールと連結するために図３のフローチ
ャートに示す処理を行なう（ステップ１２）。
メモリ管理の動作について図１及び図２のフローチャー
トに沿って説明する。図１において例えばブロック２２
（対応するブロック管理データは図１のＢ２２）の解放
要求が発生した場合、まず、ブロック２２の直前のブロ
ック２１のブロック管理データＢ２１の情報を調べ（ス
テップ１０）、ｆｌａｇ情報がＦであるため（ステップ
１１）、直前のホールと連結するために図３のフローチ
ャートに示す処理を行なう（ステップ１２）。
【００１６】次に、ブロック２２の直後のブロック２３
のブロック管理データＢ２３のｓｉｚｅ情報から求めら
れるブロック３２のブロック管理データＢ３２を調べ
（ステップ１３）、ｆｌａｇ情報がＦであるため（ステ
ップ１４）、直後のホールと連結するために図４のフロ
ーチャートに示す処理を行ない（ステップ１５）、解放
処理を完了する。
のブロック管理データＢ２３のｓｉｚｅ情報から求めら
れるブロック３２のブロック管理データＢ３２を調べ
（ステップ１３）、ｆｌａｇ情報がＦであるため（ステ
ップ１４）、直後のホールと連結するために図４のフロ
ーチャートに示す処理を行ない（ステップ１５）、解放
処理を完了する。
【００１７】また、ブロック１５（対応するブロック管
理データは図１のＢ１５）の解放要求が発生した場合、
ステップ１１にてブロック１４のブロック管理データＢ
１４のｆｌａｇ情報がＦでないため、ステップ１６でフ
リーリストの先頭にブロック管理データＢ１５を繋げ、
ｆｌａｇ情報をＦに変更する。また、ステップ１４にて
ブロック１６のブロック管理データＢ１６のｆｌａｇ情
報がＦでないため、そのまま解放処理を完了する。図５
にブロック１５の解放処理を実施した後のブロック管理
テーブルとメモリの関係図を示す。
理データは図１のＢ１５）の解放要求が発生した場合、
ステップ１１にてブロック１４のブロック管理データＢ
１４のｆｌａｇ情報がＦでないため、ステップ１６でフ
リーリストの先頭にブロック管理データＢ１５を繋げ、
ｆｌａｇ情報をＦに変更する。また、ステップ１４にて
ブロック１６のブロック管理データＢ１６のｆｌａｇ情
報がＦでないため、そのまま解放処理を完了する。図５
にブロック１５の解放処理を実施した後のブロック管理
テーブルとメモリの関係図を示す。
【００１８】次に図２のステップ１２における直前のホ
ール（ブロック２１）との連結を図３のフローチャート
に沿って説明する。直前のホールとの連結は、直前のホ
ールの先頭ブロック管理データＢ２１のｎｅｘｔ情報を
そのまま利用することにより、フリーリストへの挿入は
不要となる。
ール（ブロック２１）との連結を図３のフローチャート
に沿って説明する。直前のホールとの連結は、直前のホ
ールの先頭ブロック管理データＢ２１のｎｅｘｔ情報を
そのまま利用することにより、フリーリストへの挿入は
不要となる。
【００１９】そこでまず、直前のホールの先頭ブロック
管理データＢ２１のｓｉｚｅ情報に解放領域のサイズ１
を加える（ステップ２０）。そして、ブロック管理デー
タＢ２１のｆｌａｇ情報をクリアし（ステップ２１）、
解放領域の最後尾ブロック管理データＢ２２のｆｌａｇ
情報にＦをセットし（ステップ２２）、直前ホールとの
連結処理を完了する。
管理データＢ２１のｓｉｚｅ情報に解放領域のサイズ１
を加える（ステップ２０）。そして、ブロック管理デー
タＢ２１のｆｌａｇ情報をクリアし（ステップ２１）、
解放領域の最後尾ブロック管理データＢ２２のｆｌａｇ
情報にＦをセットし（ステップ２２）、直前ホールとの
連結処理を完了する。
【００２０】次に図２のステップ１５における直後のホ
ール（ブロック２３〜３２）との連結を図４のフローチ
ャートに沿って説明する。図２のステップ１１による直
前のホールとの連結処理の有無に係わらず、解放領域は
既にフリーリストに繋がれているため、フリーリストで
利用するｎｅｘｔ情報は解放領域の先頭ブロック管理デ
ータＢ２１ものを利用すれば良い。
ール（ブロック２３〜３２）との連結を図４のフローチ
ャートに沿って説明する。図２のステップ１１による直
前のホールとの連結処理の有無に係わらず、解放領域は
既にフリーリストに繋がれているため、フリーリストで
利用するｎｅｘｔ情報は解放領域の先頭ブロック管理デ
ータＢ２１ものを利用すれば良い。
【００２１】そこでまず、直後のホールの先頭ブロック
管理データＢ２３をフリーリストからはずし（ステップ
３０）、解放領域の先頭ブロック管理データＢ２１のｓ
ｉｚｅ情報にブロック管理データＢ２３のｓｉｚｅ情報
である１０を加える（ステップ３１）。そして、解放領
域の最後尾ブロック管理データＢ２２のｆｌａｇ情報を
クリアする（ステップ３２）。図６にブロック２２を解
放処理した結果、得られるブロック管理テーブルとメモ
リの関連図を示す。
管理データＢ２３をフリーリストからはずし（ステップ
３０）、解放領域の先頭ブロック管理データＢ２１のｓ
ｉｚｅ情報にブロック管理データＢ２３のｓｉｚｅ情報
である１０を加える（ステップ３１）。そして、解放領
域の最後尾ブロック管理データＢ２２のｆｌａｇ情報を
クリアする（ステップ３２）。図６にブロック２２を解
放処理した結果、得られるブロック管理テーブルとメモ
リの関連図を示す。
【００２２】実施例２ 次に本発明に係る他の実施例について説明する。図７
は、本実施例に係るメモリ管理における、管理データ及
びメモリとの関連図であり、図において１はメモリを示
し、割当済みの使用中メモリブロック（白抜部分）と、
未使用ブロックの集まりであるホール（斜線部分）で満
たされている。４１は、従来例と同じくホールを管理す
るための管理データで、少くともホールのサイズとメモ
リブロックを示すアドレス及びリストを構成するための
ポインタからなる。
は、本実施例に係るメモリ管理における、管理データ及
びメモリとの関連図であり、図において１はメモリを示
し、割当済みの使用中メモリブロック（白抜部分）と、
未使用ブロックの集まりであるホール（斜線部分）で満
たされている。４１は、従来例と同じくホールを管理す
るための管理データで、少くともホールのサイズとメモ
リブロックを示すアドレス及びリストを構成するための
ポインタからなる。
【００２３】４２は、フリーリスト群であり、ホールの
サイズを２n 〜２n+1 で区切り、各ｎ毎に一つのフリー
リストを構成している。ここでは説明を簡単にするため
に、図７に示すように、メモリは３２のブロックから構
成され、サイズ１、２、５、６、１０のホールがそれぞ
れ一つずつ存在しているものと仮定する。また、フリー
リストの個数は、３２＝２5 であるため５つのリストか
ら構成すれば良く、フリーリスト０にはサイズ１のホー
ルが、フリーリスト１にはサイズ２〜３のホールが、フ
リーリスト２にはサイズ４〜７のホールが、フリーリス
ト３にはサイズ８〜１５のホールが、フリーリスト４に
はサイズ１６〜３１のホールがそれぞれ繋がれる。
サイズを２n 〜２n+1 で区切り、各ｎ毎に一つのフリー
リストを構成している。ここでは説明を簡単にするため
に、図７に示すように、メモリは３２のブロックから構
成され、サイズ１、２、５、６、１０のホールがそれぞ
れ一つずつ存在しているものと仮定する。また、フリー
リストの個数は、３２＝２5 であるため５つのリストか
ら構成すれば良く、フリーリスト０にはサイズ１のホー
ルが、フリーリスト１にはサイズ２〜３のホールが、フ
リーリスト２にはサイズ４〜７のホールが、フリーリス
ト３にはサイズ８〜１５のホールが、フリーリスト４に
はサイズ１６〜３１のホールがそれぞれ繋がれる。
【００２４】このような状態において、サイズ５のメモ
リ割り当て要求が発生した時の動作を図７及び図８のフ
ローチャートに沿って説明する。まず、サイズ５の割当
を確実に満たすことのできるホールを持つフリーリスト
の番号を求める（ステップ５０）。この時、求めるフリ
ーリストの番号をｎとすれば、２n-1 ≦要求サイズ＜２
n を満たすｎを求めれば良い。これは５を２進表記した
時の最上位ビット番号に１を加えた値、即ちｎ＝３とな
る。
リ割り当て要求が発生した時の動作を図７及び図８のフ
ローチャートに沿って説明する。まず、サイズ５の割当
を確実に満たすことのできるホールを持つフリーリスト
の番号を求める（ステップ５０）。この時、求めるフリ
ーリストの番号をｎとすれば、２n-1 ≦要求サイズ＜２
n を満たすｎを求めれば良い。これは５を２進表記した
時の最上位ビット番号に１を加えた値、即ちｎ＝３とな
る。
【００２５】次にステップ５０にて求めたｎ＝３がフリ
ーリストの番号の上限を越えているかをチェックする
（ステップ５１）。本実施例の場合フリーリストの番号
の上限値は４であり、ｎは上限値を越えていないため、
フリーリスト３にホールが繋がれているかをチェックす
る（ステップ５２）。本実施例では、フリーリスト３に
はホールが繋がれているため、フリーリスト３の先頭の
ホール管理データを取り外し（ステップ５３）、このホ
ールのサイズが要求サイズ５より大きいかをチェックす
る（ステップ５４）。本実施例の場合、ホール管理デー
タのサイズは１０であり、要求サイズ５より大きいた
め、ホール管理データのサイズを要求サイズ分減算して
５にセットする（ステップ５５）。次に、この残ホール
管理データを繋げるべきフリーリストの番号を求める
（ステップ５６）。この時、求めるフリーリストの番号
をｎとすれば、２n ≦ホールの残サイズ＜２n+1 を満た
すｎを求めれば良い。これは５を２進表記した時の最上
位ビット番号の値、即ちｎ＝２となる。
ーリストの番号の上限を越えているかをチェックする
（ステップ５１）。本実施例の場合フリーリストの番号
の上限値は４であり、ｎは上限値を越えていないため、
フリーリスト３にホールが繋がれているかをチェックす
る（ステップ５２）。本実施例では、フリーリスト３に
はホールが繋がれているため、フリーリスト３の先頭の
ホール管理データを取り外し（ステップ５３）、このホ
ールのサイズが要求サイズ５より大きいかをチェックす
る（ステップ５４）。本実施例の場合、ホール管理デー
タのサイズは１０であり、要求サイズ５より大きいた
め、ホール管理データのサイズを要求サイズ分減算して
５にセットする（ステップ５５）。次に、この残ホール
管理データを繋げるべきフリーリストの番号を求める
（ステップ５６）。この時、求めるフリーリストの番号
をｎとすれば、２n ≦ホールの残サイズ＜２n+1 を満た
すｎを求めれば良い。これは５を２進表記した時の最上
位ビット番号の値、即ちｎ＝２となる。
【００２６】次にステップ５６にて求めたｎ＝２から、
フリーリスト２の最後尾に残ホールを繋げ（ステップ５
７）、メモリ割当処理を完了する。図１０に以上の処理
をした後のホール管理データとメモリの関係図を示す。
フリーリスト２の最後尾に残ホールを繋げ（ステップ５
７）、メモリ割当処理を完了する。図１０に以上の処理
をした後のホール管理データとメモリの関係図を示す。
【００２７】一方、サイズ１０のメモリ割り当て要求が
発生した場合には、ステップ５０にてｎ＝４となり、ス
テップ５２ではフリーリスト４にホールが繋がれていな
いため、ステップ５８に進む。ステップ５８ではｎに１
を加えてｎ＝５にし、ｎの値が上限を越えていないかを
チェックする（ステップ５１）。本実施例の場合、上限
値４をｎが越えるため、ステップ５９にすすむ。ステッ
プ５９ではフリーリスト（ｎ−１）＝３を探索し、サイ
ズ１０を満たすホールがあるかを探索する。探索の結
果、サイズ１０を満たすホールがない場合は、要求サイ
ズのメモリ割り付けができないことを利用者へ通知す
る。
発生した場合には、ステップ５０にてｎ＝４となり、ス
テップ５２ではフリーリスト４にホールが繋がれていな
いため、ステップ５８に進む。ステップ５８ではｎに１
を加えてｎ＝５にし、ｎの値が上限を越えていないかを
チェックする（ステップ５１）。本実施例の場合、上限
値４をｎが越えるため、ステップ５９にすすむ。ステッ
プ５９ではフリーリスト（ｎ−１）＝３を探索し、サイ
ズ１０を満たすホールがあるかを探索する。探索の結
果、サイズ１０を満たすホールがない場合は、要求サイ
ズのメモリ割り付けができないことを利用者へ通知す
る。
【００２８】本実施例の場合ホール管理データが要求サ
イズ１０を満たすため、ステップ５３へ進み、ホール管
理データをフリーリスト４からはずす。次にホール５の
サイズと要求サイズを比較する（ステップ５４）。その
結果、ホール５のサイズと要求サイズはとはもに１０で
等しいため、そのまま割付処理を終了する。図１１にサ
イズ１０のメモリ割当てを実施した後のホール管理デー
タとメモリの関係図を示す。
イズ１０を満たすため、ステップ５３へ進み、ホール管
理データをフリーリスト４からはずす。次にホール５の
サイズと要求サイズを比較する（ステップ５４）。その
結果、ホール５のサイズと要求サイズはとはもに１０で
等しいため、そのまま割付処理を終了する。図１１にサ
イズ１０のメモリ割当てを実施した後のホール管理デー
タとメモリの関係図を示す。
【００２９】次に図７の状態において、ブロック２２の
解放要求が発生した場合について、図７及び図９のフロ
ーチャートに沿って説明する。まず、従来例と同じよう
にホール管理データ群をたどってブロック２２の直前に
ホールが存在するかを検出する（ステップ６０）。もし
直前にホールが存在しなければそのままステップ６１へ
進む。本実施例の場合には、ホール４が存在するため、
ステップ６１にてホール４を管理するホール管理データ
（本実施例の場合フリーリスト０がポイントしている）
をフリーリスト０からはずす。その後、ブロック２２を
ホール４と連結し、サイズ２のホールとする（ステップ
６２）。次にブロック２２の直後にホールが存在するか
を検出する（ステップ６３）。もし、直後にホールが存
在しなければそのままステップ６４へ進む。本実施例の
場合には、ホール５が存在するため、ステップ６４にて
ホール５を管理するホール管理データをフリーリスト３
からはずす。その後、ブロック２１〜２２をホール５と
連結し、サイズ１２のホールとする。
解放要求が発生した場合について、図７及び図９のフロ
ーチャートに沿って説明する。まず、従来例と同じよう
にホール管理データ群をたどってブロック２２の直前に
ホールが存在するかを検出する（ステップ６０）。もし
直前にホールが存在しなければそのままステップ６１へ
進む。本実施例の場合には、ホール４が存在するため、
ステップ６１にてホール４を管理するホール管理データ
（本実施例の場合フリーリスト０がポイントしている）
をフリーリスト０からはずす。その後、ブロック２２を
ホール４と連結し、サイズ２のホールとする（ステップ
６２）。次にブロック２２の直後にホールが存在するか
を検出する（ステップ６３）。もし、直後にホールが存
在しなければそのままステップ６４へ進む。本実施例の
場合には、ホール５が存在するため、ステップ６４にて
ホール５を管理するホール管理データをフリーリスト３
からはずす。その後、ブロック２１〜２２をホール５と
連結し、サイズ１２のホールとする。
【００３０】次に連結の完了したホールをつなげるべき
フリーリストの番号を求める（ステップ６６）。この
時、求めるフリーリストの番号をｎとすれば、２n ≦ホ
ールの残サイズ＜２n+1 を満たすｎを求めれば良い。こ
れは１２を２進表記した時の最上位ビット番号の値、即
ちｎ＝３となる。
フリーリストの番号を求める（ステップ６６）。この
時、求めるフリーリストの番号をｎとすれば、２n ≦ホ
ールの残サイズ＜２n+1 を満たすｎを求めれば良い。こ
れは１２を２進表記した時の最上位ビット番号の値、即
ちｎ＝３となる。
【００３１】次にステップ６６にて求めたｎ＝３から、
フリーリスト３の最後尾に連結したホールをつなげ（ス
テップ６７）、メモリ解放処理を完了する。図１２にブ
ロック２２の解放処理を実施した後のホール管理データ
とメモリの関係図を示す。
フリーリスト３の最後尾に連結したホールをつなげ（ス
テップ６７）、メモリ解放処理を完了する。図１２にブ
ロック２２の解放処理を実施した後のホール管理データ
とメモリの関係図を示す。
【００３２】実施例３ 次に本発明に係る他の実施例について説明する。図１３
は、請求項第３項に係るメモリ管理における、管理デー
タ及びメモリとの関連図であり、図において、１〜４２
は実施例２における図７のものと同じ、７１はフリーリ
スト群４２の各フリーリストに１対１に対応したリスト
管理ビット列を示すリスト管理テーブルであり、対応す
るフリーリストにホール管理データがつながれている場
合には１が、つながれていない場合には０がセットされ
ている。
は、請求項第３項に係るメモリ管理における、管理デー
タ及びメモリとの関連図であり、図において、１〜４２
は実施例２における図７のものと同じ、７１はフリーリ
スト群４２の各フリーリストに１対１に対応したリスト
管理ビット列を示すリスト管理テーブルであり、対応す
るフリーリストにホール管理データがつながれている場
合には１が、つながれていない場合には０がセットされ
ている。
【００３３】このような状態におけるメモリ割り付け処
理を図１４のフローチャートに沿って説明する。図１４
においてステップ５０〜ステップ５９は、図８のフロー
チャートと同じ処理である。
理を図１４のフローチャートに沿って説明する。図１４
においてステップ５０〜ステップ５９は、図８のフロー
チャートと同じ処理である。
【００３４】ステップ５１にて、ステップ５０で求めた
ｎが上限を越えていない場合、ビット番号ｎよりリスト
管理テーブルをサーチし、最初にビットが“１”である
ビット番号を求める（ステップ８０）。求めるビットが
リスト管理テーブルにない場合には（ステップ８１）ス
テップ５９に進み、以降実施例２と同じ動作をする。
ｎが上限を越えていない場合、ビット番号ｎよりリスト
管理テーブルをサーチし、最初にビットが“１”である
ビット番号を求める（ステップ８０）。求めるビットが
リスト管理テーブルにない場合には（ステップ８１）ス
テップ５９に進み、以降実施例２と同じ動作をする。
【００３５】ステップ８１にて求めるビットがリスト管
理テーブルにあった場合にはステップ５３に進み、以降
実施例２と同じ動作をする。
理テーブルにあった場合にはステップ５３に進み、以降
実施例２と同じ動作をする。
【００３６】
【発明の効果】以上のように本発明では、リアルタイム
ＯＳでのメモリの管理単位であるブロックに、１つづつ
管理データを対応させ、この管理データに対応するブロ
ックが割当済みか利用可能かを判定する情報を持たせ、
割当済みメモリ域の解放要求発生時には、前後のホール
との連結の必要性の有無を、解放域の直前のブロックに
対応する管理データと、直後のブロックに対応する管理
データの情報を調べれば良い構成にしたので、メモリ解
放要求時での繰り返し処理の回避を実現することができ
る。
ＯＳでのメモリの管理単位であるブロックに、１つづつ
管理データを対応させ、この管理データに対応するブロ
ックが割当済みか利用可能かを判定する情報を持たせ、
割当済みメモリ域の解放要求発生時には、前後のホール
との連結の必要性の有無を、解放域の直前のブロックに
対応する管理データと、直後のブロックに対応する管理
データの情報を調べれば良い構成にしたので、メモリ解
放要求時での繰り返し処理の回避を実現することができ
る。
【００３７】また、利用可能な連続したブロックである
ホールを管理するフリーリストを複数持たせ、各ホール
をそのサイズの冪乗で分類し、メモリ割り当て要求時に
は、確実に割り付け可能なホールのリストから得ること
ができる構成にしたので、メモリ割り当て要求時での繰
り返し処理の回避を実現することができる。
ホールを管理するフリーリストを複数持たせ、各ホール
をそのサイズの冪乗で分類し、メモリ割り当て要求時に
は、確実に割り付け可能なホールのリストから得ること
ができる構成にしたので、メモリ割り当て要求時での繰
り返し処理の回避を実現することができる。
【００３８】また、フリーリストにホール管理データが
繋がっているかどうかを示すリスト管理テーブルを設け
たので、更なる処理の高速化が図れる。
繋がっているかどうかを示すリスト管理テーブルを設け
たので、更なる処理の高速化が図れる。
【図１】本発明の実施例１に係る管理データとメモリの
関係図である。
関係図である。
【図２】本発明の実施例１に係るメモリ解放処理を示す
フローチャートである。
フローチャートである。
【図３】図２における直前のホールとの連結処理を示す
フローチャートである。
フローチャートである。
【図４】図２における直後のホールとの連結処理を示す
フローチャートである。
フローチャートである。
【図５】本発明の実施例１におけるブロック１５のメモ
リ領域解放処理後のブロック管理テーブルとメモリの関
係図である。
リ領域解放処理後のブロック管理テーブルとメモリの関
係図である。
【図６】本発明の実施例１におけるブロック２２のメモ
リ領域解放後のブロック管理テーブルとメモリの関係図
である。
リ領域解放後のブロック管理テーブルとメモリの関係図
である。
【図７】本発明の実施例２に係るホール管理データとメ
モリの関係図である。
モリの関係図である。
【図８】本発明の実施例２に係るメモリ割当処理を示す
フローチャートである。
フローチャートである。
【図９】本発明の実施例２に係るメモリ解放処理を示す
フローチャートである。
フローチャートである。
【図１０】本発明の実施例２におけるサイズ５のメモリ
領域割当後のホール管理データとメモリの関係図であ
る。
領域割当後のホール管理データとメモリの関係図であ
る。
【図１１】本発明の実施例２におけるサイズ１０のメモ
リ領域割当後のホール管理データとメモリの関係図であ
る。
リ領域割当後のホール管理データとメモリの関係図であ
る。
【図１２】本発明の実施例２におけるブロック２２のメ
モリ領域割当後のホール管理データとメモリの関係図で
ある。
モリ領域割当後のホール管理データとメモリの関係図で
ある。
【図１３】本発明の実施例３に係るホール管理データと
メモリの関係図である。
メモリの関係図である。
【図１４】本発明の実施例３に係るメモリ割当処理を示
すフローチャートである。
すフローチャートである。
【図１５】従来のメモリ管理に係るホール管理データと
メモリの関係図である。
メモリの関係図である。
１ メモリ ２ ブロック管理テーブル ３ フリーリスト ４１ ホール管理データ群 ４２ フリーリスト群 ７１ リスト管理テーブル
Claims (3)
- 【請求項１】 記憶装置を固定長サイズのブロックに分
割して、使用中のブロックと未使用のブロックに分け、
一つ以上の連続した未使用のブロックをホールとして管
理する記憶領域管理方式において、下記の要素を有する
記憶領域管理方式。 （ａ）前記ホールをリストとして管理するためのフリー
リスト （ｂ）分割されたブロックに対応して存在し、少なくと
もそのサイズと次ホールの先頭を指すポインターおよび
使用中か否かを示すフラグとを格納するブロック管理テ
ーブル （ｃ）記憶領域の解放時に解放するブロックの前後の前
記フラグを参照してそのブロックがホールか否かを判定
する手段 （ｄ）前記フラグの状態を判定する手段により判定した
結果を用いてブロック管理テーブルをメンテナンスする
手段。 - 【請求項２】 記憶装置を固定長サイズのブロックに分
割して、使用中のブロックと未使用のブロックに分け、
一つ以上の連続した未使用のブロックをホールとして管
理する記憶領域管理方式において、下記の要素を有する
記憶領域管理方式。 （ａ）前記ホールをリストとして管理するＮ個のフリー
リストからなるフリーリスト群 （ｂ）前記フリーリストよりポイントされ、ホールを管
理する少なくともそのサイズと次のホールを示すための
ポインターおよび対応する記憶装置上のアドレスから成
るホール管理データ群 （ｃ）前記フリーリスト群のｋ番目のフリーリストには
下記の式を満足するホールを管理する前記ホール管理デ
ータをポインターで接続する手段 ０≦ｋ≦Ｎ、 ２k ≦ ホールのサイズ ＜２k+1 （ｄ）記憶領域の割当処理時において下記の式を満足す
るフリーリストｎにポイントされている先頭のホールを
割り当てる手段。 １≦ｎ≦Ｎ、 ２n-1 ≦ 割り当てる記憶サイズ ＜２
n - 【請求項３】 前記フリーリスト群の各々に前記ホール
管理データが存在するか否かを示すフラグを有するリス
ト管理テーブルを前記フリーリスト群に対応して設けた
ことを特徴とする請求項２に記載の記憶領域管理方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP09804493A JP3353376B2 (ja) | 1993-04-23 | 1993-04-23 | 記憶領域管理方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP09804493A JP3353376B2 (ja) | 1993-04-23 | 1993-04-23 | 記憶領域管理方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH06309197A true JPH06309197A (ja) | 1994-11-04 |
| JP3353376B2 JP3353376B2 (ja) | 2002-12-03 |
Family
ID=14209153
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP09804493A Expired - Fee Related JP3353376B2 (ja) | 1993-04-23 | 1993-04-23 | 記憶領域管理方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3353376B2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2006126973A (ja) * | 2004-10-26 | 2006-05-18 | Mitsubishi Electric Corp | 記憶領域管理方法、記憶領域割当プログラム、ガベージコレクション処理プログラム、記憶領域管理プログラム、およびメッセージ管理プログラム |
| US7613895B2 (en) | 2006-05-18 | 2009-11-03 | Konica Minolta Business Technologies, Inc. | Memory administrating method |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS58171780A (ja) * | 1982-03-31 | 1983-10-08 | Fujitsu Ltd | 主記憶の管理方法 |
| JPH02193231A (ja) * | 1989-01-20 | 1990-07-30 | Fujitsu Ltd | ファイルスペース空き領域管理方式 |
| JPH03265944A (ja) * | 1990-03-15 | 1991-11-27 | Fujitsu Ltd | ファイル管理方式 |
| JPH04219836A (ja) * | 1990-12-20 | 1992-08-10 | Nec Corp | ブロック管理方式 |
| JPH04236639A (ja) * | 1991-01-21 | 1992-08-25 | Nec Corp | ファイル空き管理方式 |
| JPH04349546A (ja) * | 1991-05-28 | 1992-12-04 | Hitachi Ltd | 共用メモリプール管理方式 |
-
1993
- 1993-04-23 JP JP09804493A patent/JP3353376B2/ja not_active Expired - Fee Related
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS58171780A (ja) * | 1982-03-31 | 1983-10-08 | Fujitsu Ltd | 主記憶の管理方法 |
| JPH02193231A (ja) * | 1989-01-20 | 1990-07-30 | Fujitsu Ltd | ファイルスペース空き領域管理方式 |
| JPH03265944A (ja) * | 1990-03-15 | 1991-11-27 | Fujitsu Ltd | ファイル管理方式 |
| JPH04219836A (ja) * | 1990-12-20 | 1992-08-10 | Nec Corp | ブロック管理方式 |
| JPH04236639A (ja) * | 1991-01-21 | 1992-08-25 | Nec Corp | ファイル空き管理方式 |
| JPH04349546A (ja) * | 1991-05-28 | 1992-12-04 | Hitachi Ltd | 共用メモリプール管理方式 |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2006126973A (ja) * | 2004-10-26 | 2006-05-18 | Mitsubishi Electric Corp | 記憶領域管理方法、記憶領域割当プログラム、ガベージコレクション処理プログラム、記憶領域管理プログラム、およびメッセージ管理プログラム |
| US7613895B2 (en) | 2006-05-18 | 2009-11-03 | Konica Minolta Business Technologies, Inc. | Memory administrating method |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3353376B2 (ja) | 2002-12-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5109336A (en) | Unified working storage management | |
| US6324631B1 (en) | Method and system for detecting and coalescing free areas during garbage collection | |
| JP4250190B2 (ja) | ファイルシステムにおけるオブジェクトの効率的な記憶 | |
| US5481702A (en) | Allocation optimization with different block-sized allocation maps | |
| US7085781B2 (en) | Multi-volume extent based file system | |
| JP2858795B2 (ja) | 実記憶割り当て方法 | |
| US7900008B2 (en) | Disk space allocation | |
| JP4176857B2 (ja) | リファレンスされたオブジェクトを管理するための３状態リファレンスの使用 | |
| JPH11511272A (ja) | 実時間データ移送のシステムおよびスパースファイルを用いる方法 | |
| JP2001236249A (ja) | メモリ管理装置およびメモリ管理方法 | |
| JP2002536761A (ja) | 実行時環境でのメモリ管理 | |
| JPH05274152A (ja) | オブジェクト管理方式 | |
| US20080162830A1 (en) | Methods, systems, and computer program products for providing memory management with constant defragmentation time | |
| JPH07325669A (ja) | ディスク管理方法 | |
| JPH06309197A (ja) | 記憶領域管理方式 | |
| US7644232B2 (en) | Cache method and cache system for storing file's data in memory blocks divided from cache memory | |
| US7509461B1 (en) | Method and apparatus for intelligent buffer cache pre-emption | |
| CN120523419B (zh) | 数据存储方法、电子设备、存储介质及计算机程序产品 | |
| JPS5883377A (ja) | バツフアメモリ制御方式 | |
| JPH07182239A (ja) | セグメント分割管理システム | |
| CN109284234A (zh) | 一种存储地址分配方法及系统 | |
| KR20030044498A (ko) | 주기억 장치 데이터베이스 관리 시스템의 자료 구조와블록 할당 및 레코드 검색 방법 | |
| JPH0793192A (ja) | ファイル管理方法 | |
| JP2743857B2 (ja) | 領域共用ファイルのデータ領域管理システム | |
| JP2003085036A (ja) | メモリ管理方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080927 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080927 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090927 Year of fee payment: 7 |
|
| LAPS | Cancellation because of no payment of annual fees |