JP3316593B2 - メモリ・スペース割当方法及び装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、メモリの割当(allocat
ion)に係り、特に、可視のピクセル・データを格納して
いないディスプレイ・メモリの割当に関するものであ
る。

【０００２】

【従来の技術】コンピュータは一般的にデータを発生
し、そのデータは出力ディスプレイ装置にディスプレイ
される。出力ディスプレイ装置はＣＲＴ（陰極線管）で
あることが多く、そのＣＲＴはスクリーン全体のイメー
ジを次々と見る人の目にとまらぬ速さでディスプレイす
るので、プログラムが静止画をディスプレイしている場
合には静止した映像に見えるディスプレイが生じる。

【０００３】次々にディスプレイされるイメージ（フレ
ーム）を個々に発生するために、データがフレーム・バ
ッファに書き込まれる。フレーム・バッファには、スク
リーン全体のイメージを発生するために、ディスプレイ
装置の発光可能な個々の位置（個々の画素ないし個々の
ピクセル）についての情報が格納される。たとえば、あ
るディスプレイ装置では、一行に約１０００のピクセル
を約１０００行分ディスプレイすることができる。それ
らについての全ての情報がフレーム・バッファに格納さ
れ、ディスプレイ装置のために繰り返し走査される。

【０００４】通常、データはフレーム・バッファからデ
ィスプレイ装置へ次のように転送される。すなわち、ピ
クセル毎かつ行毎に、ディスプレイ装置の上方の左隅を
始点として、水平に左から右へ、行毎に下方へ、下方の
右隅へという順序で、転送される。このプロセスはラス
タ走査と呼ばれる。ディスプレイ装置に画像が連続的に
現れるようにするため、フレーム・バッファの引き続く
フレームが、毎秒６０フレームまたはそれ以上の速度
（レート）で、ディスプレイ装置のために一定に走査さ
れる。

【０００５】データのフレームが走査されている間に、
次のフレームに含まれる新しいデータはフレーム・バッ
ファに転送されなければならない。フレームでディスプ
レイされるべき新しいデータは、フレーム・バッファの
変更中の部分に何時でも書き込むことができる。情報を
フレーム・バッファに書き込むことと、情報をフレーム
・バッファからディスプレイ装置へと走査することを、
同時にできるようにするために、２ポートのビデオ・ラ
ンダム・アクセス・メモリ（ＶＲＡＭ）が、通常、フレ
ーム・バッファのために用いられる。２ポートの一方を
介して書き込みが行われ、他方を介して走査が行われ
る。

【０００６】もし、ディスプレイ装置への情報の走査中
に、同時に、データをフレーム・バッファへ置かれつつ
あるとすると、走査中の情報が２つの時間的にずれたフ
レームから得られることになる。たとえば、もし、フレ
ーム・バッファへのデータの書き込み速度よりも速い速
度で、走査が行われ、そして、フレーム・バッファの変
更中（書き込み中）の部分が走査されるものとすると、
ディスプレイの或る部分は前のフレームのものとなり、
ディスプレイの或る部分は次のフレームのものとなろ
う。時間的にずれた２つのフレームの部分が同時にディ
スプレイされると、実時間ビデオにおけるように速く変
化するディスプレイの場合には使用者はめんくらうこと
になる。生成されるイメージは著しく歪み、フレーム・
ティア（ｆｒａｍｅ ｔｅａｒｓ）と呼ばれている。

【０００７】かかるフレーム・ティアの回避のために、
ダブル・バッファのディスプレイ・メモリを用いること
ができる。ダブル・バッファでは、それぞれ１つのフレ
ームの全体を格納できる２つの完全なフレーム・バッフ
ァが使用される。一方のフレーム・バッファにデータを
書き込み、他方のフレーム・バッファが走査される。走
査中のフレーム・バッファにデータが書き込まれること
がないから、フレーム・ティアは生じ得ない。ダブル・
バッファは、通常、出力ディスプレイ装置に高速度で変
化するデータを与えるプログラムで使用される。

【０００８】ダブル・バッファのディスプレイ・システ
ムにより提供される能力の利用を、全てのプログラムが
必要としているわけではない。典型例は、主としてテキ
ストの発生または２次元グラフィックス出力に限定され
たプログラムである。そのようなプログラムがダブル・
バッファの能力を有するコンピュータ上をランしてい
て、そのダブル・バッファの能力が利用されていないと
きには、高価なフレーム・バッファ・メモリの相当な容
量が使用されていないことになる。このメモリは、出力
ディスプレイ装置に密接に関連しているのであるから、
ディスプレイ装置に関する情報のオフ・スクリーン記憶
装置のために用いるのに都合の良い位置にある。たとえ
ば、このメモリは、他のウインドウにより現時点でカバ
ーされた部分が存在するウインドウからの、現時点では
見えない情報の格納のために使用できる。このメモリ
は、ふつう低速度のセントラル・プロセッサによりディ
スプレイ装置を更新しなければならない時に生じる遅れ
を除去するためのグラフィックス・アクセラレータが、
ディスプレイ装置とともに使用されるものでは、特に有
用である。なぜなら、このメモリにより、それがなけれ
ばシステム・メモリに格納されてセントラル・プロセッ
サにより操作されねばならないデータを、メモリグラフ
ィックス・アクセラレータが操作できるからである。こ
のことは、不使用のダブル・バッファ領域のような特に
大きな余剰メモリが、フレーム・バッファにより提供さ
れる場合には、特に重要である。ある特定の例では、フ
レーム・バッファ・メモリのほぼ３メガバイトを、オフ
・スクリーン記憶のために利用でき、その相当量のメモ
リに格納される情報については、システム・メモリへの
転送（それには遅れが伴う）が不要となる。

【０００９】勿論、グラフィックス・アクセラレータに
よるディスプレイ装置上での提示や他のシステム・メン
テナンス動作における遅れを与えることなしに、その余
剰メモリの使用が可能である場合においてのみ、その余
剰メモリは有用なのである。メモリの利用において必要
なステップの１つは、メモリの異なる部分を、メモリの
種々の用途それぞれに割り当てることである。マルチタ
スク環境で進歩したカラー出力を動作させるのに供給し
なければならない情報は、非常に量が多く、高速で変化
する性質を有するので、もし割当プロセスが遅いと、出
力ディスプレイ装置にディスプレイする情報のオペレー
ションも遅くなる。極端な場合には、コンピュータ・シ
ステムの全体のオペレーションがメモリ割当を待つため
に遅くなる。従来の割当プロセスは、フレーム・バッフ
ァの臨時のメモリをオフ・スクリーン・データの格納に
利用できる程には十分に速くはなかった。

【００１０】

【発明により解決すべき課題】それ故、本発明の目的
は、オフ・スクリーン情報の格納のためにディスプレイ
・メモリ・スペースを効果的に割り当てる方法を提供す
ることにある。本発明のより具体的な目的は、オフ・ス
クリーン情報の格納にディスプレイ・メモリ・スペース
を極めて効果的に割り当てる方法を提供することにあ
る。

【００１１】

【課題を解決する手段】本発明の目的は次のようにして
達成される。

【００１２】

【実施例】

〔表記法および命名法〕以下の説明は部分的に、コンピ
ュータ・メモリ内でのデータ・ビットに関するオペレー
ションのアルゴリズムやシンボル表示により行われる。
これらのアルゴリズムの記述や表示は、データ・プロセ
ス技術の分野で通常の知識を有する者が相互に、成果を
伝える最も効果的な手段である。アルゴリズムは、ここ
では、そして一般に、所望の結果へと導く、ステップの
自己矛盾のないシーケエンスであると考えられている。
ステップは、物理量の物理的操作を要求するものであ
る。それらの物理量は、通常（必要的ではないが）、格
納でき、転送でき、結合でき比較でき、その他の操作を
できる、電気的または磁気的な形態をとる。これらの信
号を、ビット（ｂｉｔ）、値（ｖａｌｕｅ）、要素（ｅ
ｌｅｍｅｎｔ）、シンボル、キャラクタ、項（ｔｅｒ
ｍ）、数（ｎｕｍｂｅｒ）などと称するのが、共通的使
用のために、原理的に便利であることが判明している。
しかし、これらのこのような語は、然るべき物理量に関
係付けられているもので、物理量に便宜上付された名前
である。

【００１３】さらに、遂行される操作（ｍａｎｉｐｕｌ
ａｔｉｏｎｓ）は、普通はオペレータのような人間の頭
脳的活動に関する加算（ａｄｄｉｎｇ）、比較（ｃｏｍ
ｐａｒｉｎｇ）の語で呼ばれる。本発明の一部をなすも
のとして記載されているオペレーションの何れにおいて
も、オペレータの頭脳的活動能力はほとんど必要とされ
ない。そのオペレーションはマシン・オペレーションで
ある。本発明のオペレーションの遂行には汎用のデジタ
ル・コンピュータ、それに類似の装置を利用できる。全
ての場合に、コンピュータのオペレーティングにおける
メソッド・オペレーションと、計算方法とを、区別して
おく必要がある。本発明は、電気的その他の（機械的、
化学的な）物理量を処理して別の所望の物理的信号を生
成する場合に、コンピュータのオペレーティングをする
ための方法のステップに関するものである。

【００１４】〔詳細な説明〕第１図には、（コンピュー
タ・システムにおけるランダム・アクセス・メモリに利
用される）連続したリニア・メモリ１０として記述でき
るものの、短いセクションが示されている。図示のリニ
ア・メモリ１０は、十分な数の個々の格納位置を有し、
合計で２０４８バイト（２Ｋバイト）のデータを格納す
る。リニア・メモリ１０をピクセル・データの格納に使
用するものとし、そのピクセル・データそれぞれが仮に
８ビットにより記述されるものとすると、リニア・メモ
リ１０は２０４８のピクセル・データの格納スペースを
有する。通常、そのようなメモリの容量は、出力ディス
プレイ装置上に１〜２の水平行を表示するデータを格納
するのに十分であると考えられる。ディスプレイされる
行を増やすためには、増やされる各行のデータの格納の
ために、メモリの容量の増大が必要となる（もし、ディ
スプレイ装置が例えば２０４８ｘ２０４８ピクセルのも
のであるなら、２０４８行の格納位置が必要）。

【００１５】そのような多大のピクセル位置により、こ
のメモリから成るフレーム・バッファは、ディスプレイ
の各水平行に２Ｋバイトまでのピクセルをディスプレイ
するディスプレイ・モニタとともに使用され得る。もち
ろん、各行にそのように多数のピクセルをディスプレイ
することは、全てのモニタで可能なわけではない（可能
なものは実際には少ない）。そのようなフレーム・バッ
ファは、より少ないピクセルの表示をするモニタととも
にも、フレーム・バッファのより少ない部分を出力ディ
スプレイ装置のために割り当てることにより、使用でき
る。そのような場合には、当然、フレーム・バッファの
相当の部分が使用されないままになる。たとえば、ダブ
ル・バッファ動作をすると必要になるような、２つのフ
ル・フレームを別々にディスプレイすることのために、
十分な量のフレーム・バッファ・メモリが存在する場合
でも、多大のメモリが潜在的な不使用状態に置かれ、コ
ンピュータでランしているアプリケーション・プログラ
ムによってはダブル・バッファは使用されない。

【００１６】ディスプレイすべきデータのみをフレーム
・バッファに格納する場合には、フレームバッファの部
分を割り当てる方法は、システムのオペーレーション速
度の点では重要ではない。そのような場合、使用中のモ
ニタのためにある領域が割り当てられ、割り当てられた
領域のスタート・アドレスとエンド・アドレスがシステ
ム・メモリのあるメモリ位置に格納される。一般に、割
り当てられる１つの領域が相当に大きく、プログラムの
オペレーション中は変更されない。従って、割当の際の
速度は重要でない。しかし、メモリの余剰な部分を他の
目的のために使用しようとすると、メモリのより小さい
部分を迅速に割り当てる方法を開発し、変更中の情報を
その余剰スペースへマップできるようにする必要があ
る。

【００１７】さらに、このオフ・スクリーン・メモリ中
のピクセルを操作する、付随のグラフィックス実行（ｒ
ｅｎｄｅｒｉｎｇ）ハードウエアの使用が望まれるな
ら、メモリ割当のテクニック上、メモリ・アクセス・サ
イズ・ストライド（１つの走査線から次の走査線へのピ
クセルの数）を考慮しておかねばならない。実際、オフ
・スクリーン・メモリは、フレーム・バッファの見える
部分と同じ２次元のアドレッシング・アーキテクチャを
持つものとして扱われる。かくして、メモリの連続した
リニア・ブロックを割り当てる、より複雑なメカニズム
を用いなければならない。

【００１８】例えば、コンピュータ設計者の第１の目標
は、複数の個々のプログラムが、コンピュータ上でラン
でき、同時にそのコンピュータの出力ディスプレイ装置
上でディスプレイできるようにすることである。典型的
には、複数の個々のプログラムがコンピュータの出力デ
ィスプレイ装置にディスプレイされている場合、個々の
プログラムはウインドウ内に現れる。そのウインドウ
は、通常はスクリーン上の方形の領域であり、移動で
き、サイズの拡大、縮小、その他の操作を加えることが
できるものである。複数のプログラムをランさせ、複数
のウインドウに同時にディスプレイできると、あるプロ
グラムで行われているオペレーションを他のプログラム
のオペレーションに容易に関連させることが出来、デー
タをプログラム間で転送でき、そして、一般に、コンピ
ュータを用いて行っている仕事の速度を向上させること
ができる。なぜなら、コンピュータがマルチ・タスクを
同時に遂行する場合には、特定のタスクのためのリソー
スを待たなければならいという時間的な遊びが少なくな
るからである。

【００１９】しばしば、あるアプリケーション・プログ
ラムをディスプレイしているウインドウが、他のアプリ
ケーション・プログラムをディスプレイ中のウインドウ
に重なって見えなくなることがある。カバーされている
方のデータを格納しておき、カバーをしている方のウイ
ンドウが移動させられたり、消されたりした時に、シス
テム・メモリを参照する必要なしに、その再ディスプレ
イをできるようにすることが望まれる。また、ウインド
ウのこの見えない部分を、ウインドウの見える部分の内
容（これは変更される）とともに、更新することも必要
である。出力ディスプレイ装置のウインドウにディスプ
レイされているアプリケーション・プログラムのカバー
されている部分を、余剰のフレーム・バッファ・メモリ
に格納するものとすると、種々のサイズのウインドウの
ために十分なメモリ・スペースを割り当て、それが使用
されなくなったら割当を取消する方法がなければならな
い。さらに、この割当は、割当の遅れによる歪を生じる
ことなく通常の速度でディスプレイ装置を動作させるた
めに、非常に迅速に機能できるものでなければならな
い。

【００２０】連続リニア・メモリのある領域がコンピュ
ータ内で割り当てられる典型的な高速実行方法は、リニ
ア・メモリの適当な量から始めて、その記憶領域を半分
に、各その半分を半分に、その１／４を半分に、以下同
様に、例えばリニア・メモリ１０として示される列をい
くつかのバイトをそれぞれが含むような最小のサイズの
グループに分割することである。例えば、２０４８バイ
トのリニア・メモリ１０をそれぞれが２５６バイトを含
む連続したバイトのグループに分割することである。そ
してこれらの独立したグループが個々の記憶目的に割り
当てられる。

【００２１】メモリの大きな領域の記憶グループの割当
を記録するため、メモリは２のべき数のサイズの連続し
た最小サイズの多くのグループに分けられる。リニア・
メモリのビット・マップは、各ビットがサイズを最小に
されたグループの一つにマップされるように形成され
る。グループが割り当てられればその一つのビットが
１、割り当てられていなければ（フリーであれば）０と
する。リニア・メモリ１０が割り当てられるときは、最
小領域、その２倍、その４倍、・・・のような、最小領
域の２のべき数倍のサイズであって、要求されたサイズ
を満たすに十分な大きさのブロックとなるサイズに一致
するように割り当てられる。

【００２２】例えば、メモリに５１２バイトを記憶する
ことが要求されると、割当システムは２５６バイトの各
グループの隣接した空いたビットのペアをビット・マッ
プ（図２）上で探す。そのサーチはリニア・メモリ１０
の左端の最初の０位置から始めて右へ続ける。もし二つ
の隣接グループが必要とされるとすると、プログラムは
ビット・マップ（図２）上で２ビットのインクレメント
によって探し、２ビット・バイナリ分割境界線で分けら
れていないメモリ・スペースを探すことはしない。図１
に図示されたメモリ位置のライン上のグループ０が割り
当てられている（図１では×を付して示されている）と
すると、たとえ空であってもグループ１のチェックをス
キップし、サーチはペアとしてのグループ２、３をチェ
ックする。もし、このグループ２、３が空であることが
分かると、それらの位置が割り当てられ、ビット・マッ
プ上で１が印される。もしメモリのより大きな量を割り
当てることが要求されれば、システムはその大きな量に
よって分けられるバイナリ分割線をチェックする。この
割当技法はメモリに多くの使用されない部分を残すこと
になるが、必要なメモリを非常に早く見つけることがで
きるという利点を有していることを理解できるであろ
う。

【００２３】メモリが連続した直線的な方法で割り当て
られる場合は非常に有益である。しかしながら、ウィン
ドウに書込むデータを記憶する、例えばフレーム・バッ
ファとして用いられるようなディスプレイ・メモリでは
二次元領域に割り当てる必要がある。このメモリの二次
元アーキテクチャのために、割当は連続直線的には行わ
れず、二次元でおこなうので不連続となる。従来技術で
これを行うとすると、各メモリの水平列は個々に割り当
てしなければならない。これは極端に時間がかかり、デ
ータの実際のディスプレイが遅延するところまで割当の
速度が低下する。したがって、急速に変化するデータを
処理するシステムでは余剰の不使用スペースの割当を不
可能にする。

【００２４】図３に本発明による割当方法を図示したフ
レーム・バッファ２０の一部が示してある。この方法を
用いると、フレーム・バッファ・メモリのスペースは二
次元を基礎として割り当てることができる。図３ではメ
モリ２０は、２のべき数に基づいたピクセル領域の広が
りを備えた部分に分割される。しかも、連続した直線の
グループでなく、水平及び垂直の双方の方向に分割され
る。分割したメモリのそれぞれの量は最小の量とされて
いる。本実施例では水平、垂直各方向に６４バイトで割
り当てられる。各ピクセルが１バイトを要求すると、各
最小領域に４０９６ピクセルを記憶することができる。

【００２５】各最小領域の割当位置は同様に１ビットで
記録される。割り当てられていれば１、割り当てられて
いなければ０である。この情報を記録するビット・マッ
プ（図４）は同様に直線上に記憶される。一方、領域は
図３に示すように分割される。すなわち、水平及び垂直
方向にそれぞれ最小領域の広がりの２倍の広がりを持つ
次に大きい領域を、位置０〜３で形成するというよう
に、領域は図３に示す方法でパターン化され、数字が付
けられる。位置０から始まる最小領域のサーチは、割り
当てられていない最小領域が見つかるまでビット・マッ
プ上で数字の順に続けられる。もし最小領域より大きい
領域、例えば１最小領域より大きく、４最小領域より少
ない領域を探すときは、４最小領域を境界として進めら
れる。これはビット・マップ上では単に４ビット位置ご
とにアドレスを増加することで実行されることを意味す
る。同様に、例えば４最小領域より大きく、１６最小領
域より小さい領域を探すときは、ビット・マップ上で各
１６ビットごとにアドレスを調べればよい。本実施例シ
ステムではこの原理に基づくインクレメントを非常に早
く行うように１６ビットがショート・インテジャア（ｓ
ｈｏｒｔ ｉｎｔｅｇｅｒ）のサイズである。これによ
ってサーチは非常に早くなされる。

【００２６】割当のため従来技術によって実施されるサ
ーチと比べて、本発明を用いた割当は、列から列への時
間を要する割当の必要をなくするように、水平方向及び
垂直方向双方に延びるビット位置の領域を容易する。こ
れにより本方法は、グラフィック・アクセラレータに用
いるフレーム・バッファ内でスペースを割り当てるのに
用いることができる。すなわちディスプレイに送る動作
が遅れることがない。

【００２７】ディスプレイ及びオフ・スクリーン双方用
のフレームバッファ内でのディスプレイ・メモリを割当
るために述べた方法の各ステップが図５に示されてい
る。コンピュータ・システムが最初にオンさせられたと
き、オフ・スクリーンとして用いることができるメモリ
・スペースをフレーム・バッファが有していることを示
す多くの値（一般にフレーム・バッファ・ハードウエア
のＥＰＲＯＭによって生成される）を動作システムの一
部である低レベル駆動プログラムを図５に示されている
ように読み出す。次にシステム・メモリに記憶されたデ
ィスプレイ・モニタのサイズを表す値がステップ５１で
決定され、ディスプレイそれ自身に割り当てられるディ
スプレイ・メモリの量を決定するために用いる。典型的
には、ステップ５２で割当が、メモリの最初にアドレス
する位置から開始し、十分なメモリがディスプレイ目的
に割り当てられるまで継続する。

【００２８】ディスプレイすべきピクセルに割り当てる
最後のアドレスが、本発明による割当プロセスが進行す
る第１位置を決定するために用いられる。この最初のア
ドレスは図示された割当方法ではゼロ・アドレスとして
記憶され、フレーム・バッファの使用し得るオフ・スク
リーン領域開始のためのポインタ（ステップ５３）とし
て利用される。ディスプレイ・メモリのフレーム・バッ
ファ領域がこの方法で割り当てられるので、二重バッフ
ァを用いることができるアプリケーションが用いられて
いるとその領域のサイズは変化させられる。オフ・スク
リーン・メモリのサイズはプログラムの動作とともに大
きくも小さくもなる。

【００２９】動作が、特定の目的のためのオフ・スクリ
ーンとして用いられるべき領域のサイズを得るためにス
テップ５４へ移動する。例えば、あるウインドウがカバ
ーされなくなったときに再び現れるようにオフ・スクリ
ーン・メモリにバックアップされると、このウインドウ
のサイズがウインドウ・システム・プログラムから得ら
れる。このサイズとともに動作は割り当てられる領域が
決定されるステップ５６へ進む。

【００３０】割り当てる領域は、幅及び高さを得てその
値を最小領域の幅及び高さと比較することで決定され
る。実施例での幅が１ピクセルと６４ピクセルとの間で
あれば、６４ピクセルが幅寸法として選択される。幅が
６４ピクセルと１２８ピクセルの間であれば、幅寸法と
して１２８ピクセルが選択される。幅が１２８ピクセル
と２５６ピクセルとの間であれば２５６ピクセルが幅寸
法として選択される。以下同様に次の２のべき数値が選
択される。同様に、高さが１と６４ピクセルとの間であ
れば６４ピクセルが高さ寸法として選択される。所望の
スペースに適する最も小さな領域の高さ寸法と幅寸法と
のうち、小さい方が、基本サーチ・プロセスにおいて、
大きな方と同じ値にかさ上げされる。これによって矩形
の２のべき数サイズ境界に沿って分割される領域の割当
てができる。最小スペースが決定されると、このスペー
ス内で実際のウインドウ形のマスクが生成され、求めた
領域を十分に含む領域のためにビット・マップでサーチ
が開始する（ステップ５８として示す）。

【００３１】このサーチは求める領域のサイズと等価の
２のべき数境界上で行われる。もし最小領域が探される
と、サーチはビット・マップによってビットごとに連続
してインクレメントされる。求める領域が、図３の最小
領域０〜３を含むブロックのようなブロックであれば、
サーチはビット・マップによって十分な記憶領域を求め
て大きなインクレメントで進む。図３に示すように、四
つの最小サイズ領域を含むブロックのサーチはフレーム
・バッファの上左隅から開始し、右の４ブロック領域へ
移動し、次に左下の４ブロック領域へ移動し、最後にさ
らにその右の４ブロックへ移動する。もし、スペースが
なお発見されないと、更に他の４ブロックだけ右へそし
て更に上の４ブロックへと進む。このとき最初のサーチ
・パターンが「Ｂ」と印された領域で繰り返す。割り当
てる領域がこの領域「Ｂ」にも見いだせないときには領
域「Ｃ」へ進み、最後は「Ｄ」へ移動する。このサーチ
でよい結果がでないときには直ちに領域「Ａ、Ｂ、Ｃ、
Ｄ」の右の領域へ移動して同様に繰り返す。上記したそ
れぞれの領域は図３に表示してある。このサーチ・テク
ニックは２次元グラフィック・アルゴリズムで用いられ
る「クワッド・ツリー・サーチ（ｑｕａｄ ｔｒｅｅ
ｓｅａｒｃｈ）と呼ばれるサーチ・テクニックに似てい
る。

【００３２】求めるスペースに十分にマッチした記憶ス
ペースが得られると、その領域がステップ５９で割り当
てられる。最後に、割り当てられた領域がビット・マッ
プに他の目的で使用されないように割り当てられたこと
を印す。

【００３３】実施例では、所望の領域の幅又は高さのい
ずれかが他の最小寸法の二分の一以下の場合、フレーム
・バッファ・メモリの割り当てられていないスペースと
保存スペースの領域内の割当密度を改善するため、すで
に１つ又は多くの割り当てられた最小領域を有する割当
サーチ領域内で追加のテストが行われる。すなわち、求
める領域の狭い方の寸法がサーチされた最小領域の寸法
の二分の一以下か否かの比較がされ、二分の一以下であ
ると、サーチされた各最小サイズ領域がフリーであるか
割り当てられているかを調べるというテストが行われ
る。

【００３４】本発明を実施例によって説明したが、本発
明の精神及び範囲から離れないで当業者は多くの変形を
なすことができる。したがって本発明は請求の範囲の記
載によって解釈されるべきである。

【図面の簡単な説明】

【図１】従来のメモリ割当システムの理解のための、リ
ニア・メモリ位置の連続した１つのアレイを示す図であ
る。

【図２】従来の典型的なメモリ割当システムで使用され
るビット・マップを示す図である。

【図３】本発明のメモリ割当の方法の理解のための、フ
レーム・バッファ・メモリの一部を示す図である。

【図４】本発明によるメモリ割当システムで使用される
ビット・マップを示す図である。

【図５】本発明によるフレーム・バッファ・メモリを割
り当てる方法を示すフローチャートである。

【符号の説明】

１０ リニア・メモリ

───────────────────────────────────────────────────── フロントページの続き (73)特許権者 591064003 901 ＳＡＮ ＡＮＴＯＮＩＯ ＲＯＡ Ｄ ＰＡＬＯ ＡＬＴＯ，ＣＡ 94303, Ｕ．Ｓ．Ａ. (72)発明者 カーティス・プリーム アメリカ合衆国 94536 カリフォルニ ア州・フレモント・ケタリング テラ ス・4052 (72)発明者 ロバート・ロッチェッティ アメリカ合衆国 95014 カリフォルニ ア州・カッパチーノ・ケンドル ストリ ート・22261 (56)参考文献 特開 平２−257230（ＪＰ，Ａ) 特開 昭62−139057（ＪＰ，Ａ) 特開 平４−222069（ＪＰ，Ａ) 特表 平３−500459（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) G09G 5/00 G06T 1/60

Claims (8)

(57)【特許請求の範囲】
1. 【請求項１】 フレーム・バッファ・メモリを備えるコ
   ンピュータ・システムにあって、フレーム・バッファ・
   メモリの選択した部分にスペースを割り当ててオフ・ス
   クリーン情報を格納するスペース割り当て方法であっ
   て： 前記フレーム・バッファ・メモリの選択した部分を、ブ
   ロックのマトリクスに分割するステップを備え、各ブロ
   ックは同じ幅と同じ高さを有し、そのブロック幅および
   ブロック高さは２のべき数であり； 要求幅および要求高さを持つ要求メモリ・サイズの調節
   をするステップであって、一連の２のべき数のうちの、
   要求幅および要求高さと比べて大きく且つ最も近い２の
   べき数に、要求幅および要求高さを丸める調節をする調
   節ステップを備え； 前記フレーム・バッファ・メモリの選択した部分を、割
   り当てのためにフリーな領域を求めてサーチをするサー
   チ・ステップを備え、そのフリーな領域は、調節された
   要求メモリ・サイズに等しいサイズで、フレーム・バッ
   ファ・メモリの前記ブロックの整数倍を有しており、前
   記サーチは、最初のコーナ領域および隣接した３領域の
   セットにおいて前記フリーな領域が見つかるまで行わ
   れ、最初のコーナ領域および隣接した３領域の１番目の
   セットにおける領域それぞれは前記求めているフリーな
   領域と同じサイズであり、そして、隣接した３領域のｎ
   番目のセットにおいては領域それぞれが隣接した３領域
   のｎ−１番目のセットにおける領域の４倍のサイズであ
   り、且つ、隣接した３領域のｎ番目のセット中の２つの
   領域が、隣接した３領域のｎ−１番目のセット中の２つ
   の領域に隣接しており、さらに、隣接した３領域のｎ番
   目のセットにおける領域それぞれは、最初のコーナ領域
   および隣接した３領域のｎ−１番目のセットにおけるサ
   ーチと同じやり方でサーチされるようにされており； 前記サーチで見つけられたフリーな領域内に前記ブロッ
   クを割り当てる割当てステップを備えていることを特徴
   とするスペースの割り当て方法。
2. 【請求項２】 請求項１記載の方法において、前記サー
   チには、前記フレーム・バッファ・メモリ中のブロック
   それぞれを１ビットのデータで表したビット・マップを
   サーチするビット・マップ・サーチが含まれている、こ
   とを特徴とするスペースの割り当て方法。
3. 【請求項３】 請求項２記載の方法において、前記ビッ
   ト・マップ・サーチには、前記ビット・マップ中の引き
   続くビット群であって、最初のコーナ領域および隣接し
   た３領域に対応しているビット群をサーチすることが含
   まれている、ことを特徴とするスペースの割り当て方
   法。
4. 【請求項４】 請求項３記載の方法において、前記要求
   幅および要求高さの選択した一方が、求められているフ
   リーな領域の幅または高さの半分以下である場合に、当
   該サーチのそれぞれにおいて、サーチをされている各領
   域の半分が割り当てのためにフリーであるか否かを調べ
   る追加のテストが行われる、ことを特徴とするスペース
   の割り当て方法。
5. 【請求項５】 フレーム・バッファ・メモリを備えるコ
   ンピュータ・システムにあって、フレーム・バッファ・
   メモリの選択した部分にスペースを割り当ててオフ・ス
   クリーン情報を格納するスペース割り当て装置であっ
   て： 前記フレーム・バッファ・メモリの選択した部分を、ブ
   ロックのマトリクスに分割する分割手段を備え、各ブロ
   ックは同じ幅と同じ高さを有し、そのブロック幅および
   ブロック高さは２のべき数であり； 要求幅および要求高さを持つ要求メモリ・サイズの調節
   をする調節手段であって、一連の２のべき数のうちの、
   要求幅および要求高さと比べて大きく且つ最も近い２の
   べき数に、要求幅および要求高さを丸める調節をする調
   節手段を備え； この調節手段および前記フレーム・バッファ・メモリに
   結合されていて、前記フレーム・バッファ・メモリの選
   択した部分を、割り当てのためにフリーな領域を求めて
   サーチをするサーチ手段を備え、そのフリーな領域は、
   調節された要求メモリ・サイズに等しいサイズで、フレ
   ーム・バッファ・メモリの前記ブロックの整数倍を有し
   ており、前記サーチは、最初のコーナ領域および隣接し
   た３領域のセットにおいて前記フリーな領域が見つかる
   まで行われ、最初のコーナ領域および隣接した３領域の
   １番目のセットにおける領域それぞれは前記求めている
   フリーな領域と同じサイズであり、そして、隣接した３
   領域のｎ番目のセットにおいては領域それぞれが隣接し
   た３領域のｎ−１番目のセットにおける領域の４倍のサ
   イズであり、且つ、隣接した３領域のｎ番目のセット中
   の２つの領域が、隣接した３領域のｎ−１番目のセット
   中の２つの領域に隣接しており、さらに、隣接した３領
   域のｎ番目のセットにおける領域それぞれは、最初のコ
   ーナ領域および隣接した３領域のｎ−１番目のセットに
   おけるサーチと同じやり方でサーチされるようにされて
   おり； 前記サーチ手段に結合されていて、前記サーチで見つけ
   られたフリーな領域内に前記ブロックを割り当てる割当
   て割当て手段を備えていることを特徴とするスペースの
   割り当て装置。
6. 【請求項６】 請求項５記載の装置において、前記サー
   チ手段における前記サーチには、前記フレーム・バッフ
   ァ・メモリ中のブロックそれぞれを１ビットのデータで
   表したビット・マップをサーチするビット・マップ・サ
   ーチが含まれている、ことを特徴とするスペースの割り
   当て装置。
7. 【請求項７】 請求項６記載の装置において、前記サー
   チ手段における前記ビット・マップ・サーチには、前記
   ビット・マップ中の引き続くビット群であって、最初の
   コーナ領域および隣接した３領域に対応しているビット
   群をサーチすることが含まれている、ことを特徴とする
   スペースの割り当て装置。
8. 【請求項８】 請求項７記載の装置において、前記サー
   チ手段における前記サーチでは、前記要求幅および要求
   高さの選択した一方が、求められているフリーな領域の
   幅または高さの半分以下である場合に、当該サーチのそ
   れぞれにおいて、サーチをされている各領域の半分が割
   り当てのためにフリーであるか否かを調べる追加のテス
   トが行われる、ことを特徴とするスペースの割り当て装
   置。