アルリスム テータ構造入門 く第 17 回〉メモリ管理アルゴリズム モリ管理は縁の薄いものかもしれません。 ムプログラムを作成する人以外にとってメ モリ管理機能を提供しているので , システ ンピュータ環境は , OS やコン八イラかメ 今回のテーマは , メモリ管理です。現在のコ 近藤嘉雪 4 リ管理とは ? CPU, メモリ , I / O ( ディスクやプリンタ など , コンピュータ外部とのやりとりをす る装置 ) のことを資源 (resource) といいま す。これらの資源は ( 実世界の資源と同様 に ) 分量が限られた貴重なものて、す。したが って , きちんと管理してムダ遣いしないよ うにしなければなりません。 これらの資源を管理するのはオペレーテ イングシステムの役目て、すが , 今回はこの メモリについてお話します。メモリを割り 当てたり , 解放したりする作業をメモリ管 王里 (memory management) といいます。今 回は , メモリ管理のアルゴリズムを取り上 げます。 プログラムを実行するときに , プログラ ムそのものとプログラムが使用するデータ はメモリ上に置かれます。コンピュータが 持っているメモリの分量には限りがありま す。いくら CPU の処理能力が余っていたと しても , メモリが不足していればその能力 を十分に生かすことはてきません。したが って , メモリは CPU そのものと同じくらい 貴重な資源てあるといえます。 理想をいえば , 使い切れないほどのメモ リが備わっているなら , メモリ不足によっ て CPU が足をひつばられることはありませ ん。しかし , コストの問題 , 技術の限界か ら常にそのような恵まれた環境を実現て、き るわけて、はありません。また , メモリの容 量が増えると , それにともなって複雑なデ ータ構造を使う大きなプログラムを実現て、 きるようになり , 結局メモリ不足が解消し ことは , これまて、のコンピュータの歴 史からも明らかて、す。てすから , コンピュ ータの能力を十分に引き出すためには , 限 られたメモリを有効に使うように心がけな ければなりません。 また , 最近のオペレーティングシステム ては , 仮想記憶 (virtual memory) という技 術が採用されています。仮想記憶システム て、は , 実行中のプログラム ( とそのデータ ) を , 二次記憶上 ( おもにハードディスクを使 う ) に置きます。そしてプログラム ( とその データ ) のうち , その時点て実行に必要な部 分だけを二次記憶からメモリ ( 二次記憶との 対比から主記憶と呼びます ) にロードしま す。また , 必要がなくなった部分は自動的 にメモリから二次記憶へと書き戻されるよ うになっています。 ある時点て、 , プログラムのどの部分が必 要てあるかという判断は , ハードウェアの 助けを借りてオペレーティングシステムが 行います。実行されるプログラムから見れ ば , どの部分が実際にメモリ上に存在する かは , まったく意識する必要はありません。 仮想記憶システム上て、は , 実際に存在する メモリの量よりも大きなプログラムを実行 することも可能て、す。 仮想記憶の導入によってメモリに関する 制限が緩くなったのは確かて、すが , 仮想記 憶が万能なわけて、はありません。仮想記憶 て、使える空間の大きさは二次記憶の大きさ て、制限されますから , プログラムが使える メモリが無尽蔵になるわけてはありません。 また , 実記憶と比べてプログラムが大きす ぎる場合には , 実記憶と二次記憶の間てプ ログラムの転送が頻繁に発生して , 実質的 に使いものにならないという欠点もありま す。仮想記憶は今回の本題てはないのて、 , これくらいにしておきましよう。 - = - 静的割り当てと 的割り当て ふだん私たちがプログラムを書くときに は , プログラムやデータ構造が大きくなり すぎないように注意しますが , 実際にメモ リがどのようにして管理されているかを意 識することはあまりありません。なぜなら , アルゴリズムとデータ構造入門 75

えるべきてはないてしようか。 あらためて 「定義」とは ? コンパイラにメモリ確保をさせる , う定義 (definition) の定義は , K & R 第二版や ANSI C の文面て、も同じて、す。 とい はずてす。 の , 大きさが S の , メモリ確保が行なわれる ト ) の定義があって初めて , 変数 var のため どこかに , 上のような変数 ( ~ オプジェク / * C 十十のシンタクス * / S var , / * C のシンタクス * / struct S var 教えている情報にすぎませんから。 この構造体の名前と形 ( ~ 大きさ ) を 確保は行なわれないはずてすよ。コンパイ グの宣言」といって , なんら物理的なメモリ ての常識ては , こういうものは「構造体のタ 造体 (struct) もクラスの一種 ) 。私のこれま (df4) は , クラスの宣言て、す ( C 十十ては構 (df4) (df5) の二つはどうてしようか ? M て「これは定義だ」とされていた Fig. 1 の せる文が定義て、ある , とすると , ては , AR 具体的・物理的に , メモリ確保を起こさ は , 定義である。 CANSI C 3.5 ] メモリの確保を起こさせるような宣言 タオプジェクト〕または関数のために て名付けられるオプジェクト〔 = デー と属性を指定する。その識別子によっ 宣言は , 一群の (a set (f) 識別子の解釈 ence ManuaI A8] を , 定義と呼ぶ。 [K&R 2nd ed. Refer しない。メモリを確保する宣言のこと 別子に結びつくメモリを必ずしも確保 れる解釈を指定する。宣言は , その識 宣言は , 各識別子〔 = 名前〕に与えら ります。 OOP が , 現実世界のモデリング機能を豪 語するのなら , こらのセマンティクス ( ひ いては合法と見なされるシンタクス ) は , 変 C 言語フォーラム 137 ARM が言うように , クラスの宣言 = 定義 ( = メモリ確保 ) てあるなら , コンパイラと いつものに関する私の従来の常識の一部を , 大きく変更しなければなりません。しかし , なんてタグ情報をメモリ上に持つ必要があ るのか ? そんな話 , これまて聞いたこと も読んだことも , ありまへんが・・・ 私の勉強不足か ? 誰か , 教えてくれえー 次の ( df5 ) は , 列挙型の宣言てす。 ARM 7.2 には , 列挙型は , 名前付き定数を実体とする , 独自の整数型である。 と書かれていまして , 定数てすから , その ためにメモリ確保が行われて , わざわざメ モリ参照をするなんてことは , どんな馬鹿 なコンパイラてもやんないてすよ。ぜった い。列挙型に関する私の従来の常識は , プ ログラムが , それが int てあることにとくに 依存していないならば , #define up 0 #define down 1 的には定数てあるのなら , 機械命令の定数 る値のフェッチをしていても , それが実質 いちいち , 式の評価や , メモリ参照によ するのは , 次の機会にします。 れまた面倒な話題なのて , const について云々 考察しなければならなくなりそうてす。 んど必然的に , const キーワードについても こんな話を始めると , C 十十の場合はほと からくつがえされます。 てあるのなら , これまた私の C 常識は , 根底 が宣言てあると同時に定義 ( = メモリ確保 ) enum {up, down} ; ARM が言うように 上に存在するようになるはずてす。 りうる , いわゆる列挙型変数としてメモリ p と down だけをその離散的な値域としてと と変数が定義されると , この変数 var は , u enum T var , のようにタグ名が付いて , enum T{up, down} , と , 機能的にはまったく同じはずてすよ。 オペランドに変更する , というのが , 最適 化技法のイロハのイだったはずてす。 それに , ARM の言うように , クラスの宣 言 = 定義てあるのなら , てはなぜ , その中 に書かれている static メンバだけが , 別途に 定義を要するのか , あまりにも ? ? な話じ ゃあーりませんか。 というより , そもそも , クラスの宣言 = 定義てあるとは , 物理的に , そして論理的 , どういう意味なのか ( 先の , 列挙型の宣 言 = 定義 (df5) もそう ) 。 推察するに , TurboC 十十を書いた時点 て、の処理系作家は , ARM の , クラスの宣言 = 定義説を鵜呑みにして , 、、別途定義が書かれ ていなくても "static メンバをメモリ上に実 装したのてしよう。そして BorIand C 十十て は , その、、間違い〃を修正したのてしよう。 とも , コンパイラのアセン フいったこ プラ出力を眺めてみれば , 具体的な事情は ある程度分かると思いますが , 今回はその 時間的余裕がありません。読者の方々から いろいろ教えていただければ , またこの欄 て、ご報告しようと思います。 00P ( オプジェクト指向プログラミング ) は , 面白いと私は思いますよ。コンピュー タブログラムが , 現実の世界 ~ 宇宙と感深い 仲クにならなければならなくなった , プログ ラミング言語 ~ ソースプログラムが , 現実 を記述しなければならなくなった , という 意味て , OOP は何か , 大きな「パンドラの箱」 を開けたと思いますね。現に , もうすてに ヾ継承クという機構の ( 現実表現能力の ) 限界 も指摘されています。 ANSI C 十十もまだ先のことのようてす し , われわれは , プログラミングが ーコロロ 人間の第二の言語 ( いわゆる自然言語よりは コミュニケーション能力がマシてあると期 待したい言語 ) として , 徐々に精錬されてい く様子を見守り , また可能なかぎりの発言 ・関与もしていきたいものてす。

N mo 化 あれば , その領域を一気にフロッピーディ されている。そして「現在宣言中の構造体は void clear x tO z(void) スクに書き込んてやるだけてよく , コーデ incomplete type て、ある」とされている ( とも イングが楽になるからてある。 に ANSI 3.5.2.1 ) 。宣言中の構造体は , 対 memset ( 0 , (size t) ()w ー ) ) ; ところが , 残念ながら C て、は関数の外部て 応する閉じプレースリクが出現して初めて不 宣言された静的変数のメモリ上の配置に関 完全型て、はなくなる。このため , 現在宣一 この問題を回避するひとつの手段が , 連 しての規定は何もなく , 隣あって宣言され 中の構造体て、ある「自分自身」は incomplete 続したメモリ上に配置されることが要求さ type て、あるから , 必然的にメンバとして含 た変数が実際にメモリ上に隣あって配置さ れるすべての変数をひとつの構造体にまと れる保証はない。 めてしまうというコーディング技法て、ある。 むことはて、きない 前回も述べたが , 構造体の内側て、宣言され なお , 自分自身と同じ型の構造体へのポ int X ; int y [ 20 ] ; インタはメンバに含めることがてきる。ポ たメンバは宣言順に順次アドレスの昇順に int z [ 10 ] [ 5 ] ; インタてあれば , そのポイント先の型は不 メモリに割り付けられていくことが保証さ れている。またビットフィールドの場合に 完全型て、あっても ( 取りあえずポインタ変数 int W ・ このようにして , 宣言した 4 個の静的変数 を宣言するには ) , 問題はない ( この例は前 は各ビットフィールドを割り付けた記憶単 x, Y, z, w があった場合 , これらがメモリ 位を基準として , やはり全体としては宣言 回示した ) 。もちろん , そのポインタを用い 上にこの順序て配置されるとはかぎらない 順にメモリに割り付けられていく (ANSI て実際にアクセスを行うステップがソース 中て、登場する時点まて、には , 具体的な型の 実際に , かなりの数のコンパイラは配列 3.5.2.1 ) 。 このようにすればソースレベルて、メモリ 変数と非配列変数をそれぞれグルーヒ。ング 情報が与えられていなければならない への割り付け順序を制御可能になる。これ してメモリに割り付けようとする。そのよ び構造体の うなコンパイラて、は , x と w は直接隣あって がいちばん移植性の高い解決方法て、あると メモリ配置に関して メモリに割り付けられる。それにも関わら 思われる。 こていう移植性とは , 別なハードウェ ず , x, y, z を一括してゼロクリアするため 機器組み込みのプログラムなど , グロー アの上て動作させる , という意味て、はない に次のような乱暴な手段をとっているのを バルな変数をメモリの特定の番地から特定 組み込みプログラムては , 小さなモジュー たまに見かける。これはたいへん危険なコ の順序て割り付けたいなどという要望が出 ルなら話は別だが , ハードウェア構成の異 ーディングてある。うまく動くコンパイラ ることがある。たとえば , あらかじめ定め なる機器にそのままソースレベルて、移植す もあるかもしれないが , コンパイラが変わ られた複数の変数の値を , フロッビーディ こては , む ったらとたんにバグを生み出す原因になる。 る可能性は低いからてある。 スクなどに記録して , 別なマシンて読み出 しろ使用しているコンパイラのべンダが変 #include く string. h > したりしたい場合に , 複数の変数の割り付 更になったり , コンパイラのバーションア けアドレスがメモリ空間の連続した領域に ップが行われたりして , メモリ割り付けに 変数をひとつの構造体にまとめる 関するポリシーが変更になった場合への防 衛策てあると考えている。ただし , この場 合ても構造体の内側に穴がてきるかもしれ ことは記憶しておくべきてある。 この技法を使うと , 先のシーケンスは Li st 5 のように書き換えられる。なお , この例 にかぎっていえば , offsetof (GlobaIs t, x) は 0 てあるから , memset の第三引数の部分 は単に offsetof (GIobals t, w) てもかまわな い。けれども , 後々のことを考えれば引き 算の形て書いておくほうが安全てあろう。 List 1 : #include く string. h> 2 : #include く stddef. h 〉 3 : 4 : typedef struct g10 ls { int x; int y [ 20 ] : int z [ 10 ] [ 5 ] : 7 : 8 : int 響 ; 9 : ) G10 ls ー t : 11 : G10 ls ー t G; 13 : void clear—x—to—z(void) 14 : { memset(&G, 0 , 0ffset0f(GlobaIs—t, の - offsetof(Globals_t, 16 : } ANSI C ー more 125

3 変数 、一 SECTION 使い方が 制限される名前 的な制限 ・関数のネーミング法 最後に , 名前のつけ方について考えてみ ます。名前というのは , 具体的には変数名 , 関数名などて、す。 まず , つまらない条件からチェックして おきますと , C 言語の仕様により予約されて いる名前は自由に使うことがて、きません。 これらは用途が決まっているのて、 , プログ ラマが勝手に使うことはて、きません。もち ろん , それを無視するとコンパイルする時 点て、多分工ラーになるのて、 , 予約語は変数 名に使えないということさえ頭に入れてお けば , うつかりしても , たいへんな混乱に 至ることは希だと思います。 また , コンパイラやリンカなどの処理系 の制限によって , 一定の長さ以内にしなけ ればならないこともあります。 長さといっても , 最近の処理系だと , 実 用的に十分な長さの名前を自由につけるこ とがて、きるのて、 , ほとんど気にしなくても まず問題ないて、しよう。 かっての BASIC のように , 先頭の 2 文字し か判別に使われない言語があって , a01 と a 02 が同じ変数とされてしまうのて、難儀した といったような苦労は , すて、に昔話として 語り継がれているにすぎません。昔話をも うひとっしておくと , 昔は , 変数名が短い ほうがメモリやディスクの使用量が少なく て済む , といった苦労もありました。 C 言語は基本的にコンパイラの環境が提供 されているため , 変数名とメモリは直接関 係ないように思えるかもしれませんが , メ モリが 64K バイトもあれば大容量といってい た時代には , 変数が長すぎるとコンパイル 64 C MAGAZINE 1992 4 の途中て、メモリが足りなくなってしまった り , ソースファイルが長くなるためにディ スクの空き容量が不足してコンパイルに失 敗するという , 今て、は想像もて、きない世界 があったのて、す ( 1 ) 。 取り敢えず , もはやコンパイル時にメモ リを気にする時代は終わったと考えておく 話がそれますが , 実行形式のプログラム が消費するメモリ量は , ますます少なくな ることを要求されています。 今後はパソコン上て、マルチタスクの環境 を実現する方向へ世界が向かっているから て、す。個々のプログラムが小さくても , プ ログラムを 10 個同時に走らせようとすると , 10 倍のメモリが必要になるかもしれません。 640K バイトのメモリが必要なソフトを 10 個同時に実行するには , 単純に考えても約 6M バイトのメモリが必要て、す。もちろん , 実際は , あの手この手のメモリ管理を行う ため , 共有て、きるコードを共有したり , メ モリが足りなくなったとき , あまりアクセ スされない領域を一時的にディスクに待避 するなどして , 何とか少ないメモリをやり くりするのて、す。 それぞれのプログラムがメモリの使い方 に無頓着かどうかて、 , 全体の使い勝手に多 かれ少なかれ影響することは間違いないて、 という話は今回は全然関係ないのて、 , 取 り敢えず , 変数名 , 関数名の話に戻ります。 Fig. 2 C 言語の予約語 auto defa ult float 「 egister struct volatile break do fo 「 etu rn switch while case double goto short typedef Char else signed umon まず , 予約語 ( Fig. 2 ) は自由な用途には使 えないということを書きました。これはひ とまず問題ないて、しよう。 次に問題になるのは , 予約語て、はないの だが , 自由に使うのは避けたほうがいい名 前て、す。たとえば , C 言語には標準的な関数 がいくつか決まっています。これらと同じ 名前の変数名を使うことは可能て、す。しか し , それは混乱を生むだけて、何のメリット もありません。とくに , ANSI て、定義されて いる関数の名前は , それ以外の用途に使う ことは避けるべきて、す。 たとえば printf や fopen という変数名を使 ってはいけません。後て、プログラムを読む 人が混乱するかもしれないからて、す。また , 自分て勝手に定義した関数に printf という名 前をつけるのは感心しません。もちろん , それが一般的な printf を模倣するための処理 て、あるなら , 話は別て、すが。 さらに次のアドバイスは必須というほど て、はなく , おすすめ程度のニュアンスて、考 えてほしいのて、すが , 原則としてほかの言 語の予約語は , てきるかぎり使わないほう がよいと思います。とくに , C 言語に非常に 近い言語として , C 十十というものがありま す。 C 十十には , C 言語て、は予約語とされて いないいくっかの語が , 新たな予約語とし 予約された名前 VOid static long exte rn continue て追加されています。とくにこれらの予約 unsigned sizeof i nt enum const

メモリ管理のメカニズムは , オペレーティ ングシステムやコンパイラ ( とそのライプラ リ ) て、サポートされていて , 表舞台には現れ ないからてす。 メモリの割り当てには , 静的割り当てと 動的割り当てがあります。静的割り当ては , 文字どおりプログラムを実行している間中 , 領域を割り当てておく方式てす。 C 言語て、い えば , 記憶クラスが extern と static の変数は 静的割り当てになります。静的割り当てさ れるデータは , プログラムをリンクする時 点てそのアドレスが確定します。静的割り 当てに関してはただこれだけのことて , メ モリ管理のための仕組みは必要としません。 動的割り当ては , 領域が必要になった時 点てメモリを割り当て , 不要になった時点 て解放するという方式て、す。 C 言語て、いえ ば , 記憶クラスが auto ( と register) の変数が 動的割り当てになっています。 auto 変数 は , その変数が定義されている関数に制御 が渡ったときにメモリが割り当てられます。 そして , その関数から戻る時点て、 aut 。変数 の領域は解放されます。 auto 変数の割り当 て / 解放は , 関数の呼び出し / 戻りに同期し ているのて , 通常はスタックを用いて実現 されます。スタックを使えば , 関数から戻 るときに確実にメモリが解放されるという メリットがあります。 こてデータの寿命について考えてみま しよう。データが割り当てられてから解放 されるまて、をデータの寿命といいます。静 的割り当てされたデータの寿命は , プログ ラムの実行開始から終了まて、て、す。 auto 変 数の場合は , その変数の定義を含む関数の 実行開始から終了まてが寿命になります。 ほとんどの場合はこれて、十分て、すが , 関 数の実行が終了してもメモリを解放してほ しくないというケースもあります。つまり , aut 。変数のように関数の実行に左右されず に , 任意のタイミングて、割り当て / 解放する ことがてきるデータがほしいわけて、す。 「メモリの動的割り当て』といえば , 76 C MAGAZINE 1 的 2 4 のように任意のタイミングて自由に割り当 て / 解放がてきる方式を指し , auto 変数のよ うなスタックを使ったものは除外するのが 普通てす。これ以降 , この記事ても「動的 割り当て』という用語を , スタックを除い た狭い意味て、使うことにします。 動的割り当ては , 連結リストや木構造な どを扱うときにも必要になります。これら のデータ構造は , あらかじめその形が決ま っていない上に実行中にも形が変化するの て、 , 必要に応じてメモリを自由に割り当て / 解放てきなければならないからてす。動的割 り当てをサポートするために , C 言語のライ プラリには malloc と free が用意されています。 、割り当ての分類 動的割り当てを行うには , あらかじめ大 きなメモリプロックを確保しておきます。 これをヒープ ( heap ) と呼びます。この「ヒー プ」という単語は , ヒープソートのヒープと 同じてすが , まったく別の概念なのて、注意 してください。メモリ割り当て要求がきた ら , ヒープの一部を切り出してそれを返し ます。また , 必要がなくなったメモリは , 解放されてヒープに戻されます。 動的割り当てには , いくっかバリエーシ ョンがあります (TabIe 1 ) 。まず , 割り当て るメモリプロックの大きさが一定てあるか どうかによって分類することがて、きます。 C の malloc / free は任意の大きさのプロック を割り当てることがて、きます。また BASI C, awk, perl て、は可変長の文字列を動的割 り当てします。これに対して Lisp ては , 常 に一定の大きさのセル (cell : またはコンス TabIe 1 動的割り当ての分類 セル conscell) 単位て、割り当てが行われます ( 近代的な Lisp には , このほかに可変長のデ ータを動的割り当てする機構が含まれてい る ) 。また , ファイルを管理するには固定長 のプロック ( クラスタなどとも呼ぶ ) を単位 に割り当てを行います。 もうひとつの分類は , 不要になったメモ リプロックをどのように解放するかという 点てす。これにはふたつの流儀があります。 まずひとつは , プロックが不要になった時 点て、明示的に解放する方法て、す。 C の ma110 c/free は , 明示的にプロックの解放を指定す る方式をとっています。つまり , malloc て、 割り当てたプロックが不要になったら , fre e を呼び出してそのプロックを解放しなけれ ばなりません。ファイルの管理ても , ファ イルを削除するときにプロックを解放する のて、 , 明示的に解放することになります。 もうひとつの方法は , システム側が不要 になったプロックを自動的に判断して回収 するものて、す。この作業をごみ集め ( garba gecollecting) といいます。またごみ集めを 行うルーチンを , ガべージコレクタ (garba ge collector) といいます。 ージコレクタ ガべージコレクタは , ヒープ中のプロッ クをチェックして , まだ使用中のプロック に印をつけます。そして印がついていない プロックを不要なものとして回収し , 再び 割り当てられるようにします。 Lisp て、はメ モリ管理に全面的にガべージコレクタを使 用しています。また , BASIC, awk, perl などの可変長の文字列を扱えるプログラミ 解放するタイミング 明示的に解放する ファイルの管理 ごみ集めを行う Lisp のセル領域 割り当てる プロックの 大きさ 一定である 一定でない BASIC, awk, pe などの 可変長文字列 C の malloc/free

構造体のビットフィールドのメンバに対し ては単項の & 〃を適用してはならない。 先の例て , b と c の間にある無名のメンバ は , 指定したビット数 ( ここて、は 3 ビット ) だ け間隔を開けよという指定て、ある。 たとえばハードウェアレジスタなどて , 中の何ビットかが「死んて、いる」ことはよく あり , そのような場合に便利て、ある。また c と d の間の 0 という指定は特別な意味を持っ ている。 これは「次のメンバのビット割り当ては , メモリの次の語の境界から開始してほし い」 , いい換えれば , 「ワード境界に整合さ せよ」という指示てある。 すなわち , おのおののビットフィールド は , それがひとつの記憶単位 ( ANSI ての用 ロロ 0 原語は storageunito 通常そのコンピュー タにとっての自然なメモリワードと考えれ ばよい ) の中に入るかぎり , てきるだけ詰め 込む形て、割り当てられていく。 ひとつのビットフィールドが記憶単位の 境界をまたがらないかぎり , 同じメモリワ ードに割り付けなければならない (ANSI 3.5.2.1 ) 。 しかし , ときとして , その記憶単位の中 にはこれ以上メンバを割り付けたくないと いう場合がある。そのようなときにこの幅 0 の指定を行えばよい ビットフィールドて、は次のことは処理系 定義となっている。 ・「ひとつの記憶単位」の具体的な大きさ ・ひとつの記憶単位のなかて , MSB ( 上位ビ ット ) 側から割り付けを開始するのか , L SB ( 下位ビット ) 側から割り付けを開始す るのか ・あるビットフィールドの割り付けは記憶 単位をまたがることがてきるかどうか。 またがることがて、きない場合には次の記 憶単位へ割り付けることになる。必然的 にそのような処理系ては記憶単位のビッ 124 C MAGAZINE 1992 4 ト幅を越える幅を持つビットフィールド は定義てきない ・ int として宣言した場合にそれが符号っき て、あるかどうか これらのことから , 実際にメモリ上て、の 正確なビットの配置のコントロールが必要 な場合には , ビットフィールドは避けたほ どうしても使う場合には特定の うがよい 処理系の特定のバージョンに依存している ということを承知しておく必要がある。 ビットフィールドと通常のメンバをひと つの構造体の内部て、共存させることは可能 てある。ある種の記号表などて、 , ビット単 位の情報と , それ以外の情報をいくっかひ とつのデータとしてまとめて取り扱いたい などという用途などには有用てあろう。 その場合 , ビットフィールドに引き続き , 非ビットフィールドのメンバが宣言された ならば , その型に応じて , ビットフィール ドのために用意された記憶単位の次の適切 なアライメント境界からメンバが割り当て られる。このため , ビットフィールドのメ ンバはなるべく 1 か所てまとめて宣言したほ うがメモリのムダが少なくなる。 onst/volatile 修飾された構造体メンバ 先に示した構造体の構文定義をよく観察 すると , 一部のメンバだけを const とか vola tile 修飾することが可能なように定められて いる。そもそもそのようなことは現実的な のかということになると , これは現実にも あり得る事態だと考える。 たとえば , ハードウェアのレジスタバン クを , 何らかの構造体によってマップする ようなことは十分あり得る。その場合 , 部のレジスタは read only, 他方は write 0 nly などということはあるだろう。そうなる と , 一部だけ const とか , 一部だけ volatile と いうのはありえない話て、はない。さらに 構造体が別な構造体を含み , その別な構造 体の中に const のメンバが存在するというこ ともありえるだろう。 問題は , そのような構造体に対するアク セスには制限が加えられることて、ある。た とえば , 含んて、いるメンバの中にひとって、 も const 修飾されてるものがあれば , その構 造体全体に対して代入することが禁止され る。さらにそのメンバがまた構造体て、あっ た場合 , このルールは再帰的に適用され , ネストの奧深いところて、どれかひとっても const 修飾されていればその構造体全体への 代入は禁じられることになる。構造体にお いては , const 性 (const-ness) は一種の伝染 性をもっているといえる。 自己を含む構造体は 許されない さて , 構造体は任意の型のオプジェクト を含めるということから , 次のような構造 体宣言を考えてみよう。 struct f00 { int bar ・ struct f00 zot ; / * 誤り * / この宣言は自分自身をそのメンバとして 含めようとしている。しかし , このような 宣言は誤りてある。常識的に考えて , 自分 自身の一部として自分と同じ構造を含むこ とはて、きそうもない。流行のフラクタルは そうだという反論があるかもしれないが , あれは無限にスケールダウンしていけるか ら可能なのてある。構造体の場合にはネス トしてもサイズが小さくなっていくわけて はない。逆に大きくなっていく。したがっ て , 自分自身を含む構造体はサイズが無限 大になってしまう。これて、は明らかに無理 がある。 ANSI て、は , 自分自身を含む構造体は直接 禁じられているわけて、はない。まず , 「構造 体には関数型 , あるいは不完全型 (incompl etetype) のメンバを含むことはてきない」と

嘘新 MS ー DOS プロクラミンク入門 ーズ , AX マシンに対応させたことて、お許し [ 16 ] TTURBO C 十十 1.0 INTRODUCTI DOS ファンクション 06h(Table 3 ) 直接コンソール I / O ください。なお , J ー 3100 シリーズと AX マシ ON 』 , BORLAND [ 17 ] TTURBO C 十十 1.0 USER'S GUID DOS ファンクション 07h(Table 4 ) デバッグし ンは手元にマシンがないため , 直接コンソール入力 ておりません。 E 』 , BORLAND [ 18 ] fTURBO C 十十 1.0 PROGRAMME を使用して表示とキー入力を行っています。 毎回くパスワード > を入力するのがめん R'S GUIDE 』 , BORLAND [ 参考文献 ] どうな場合は特定のキー ( たとえば , + [ 19 ] TTURBO C 十十 1.0 LIBRARY RE 十など ) を押しているとくパス [ 1 ] 中島信行 , 「 C によるメモリ管理技法」 , FERENCE V01.1 , V01.2 』 , BORLAN ワード > を確認しないモードを追加するの 「別冊インターフェース』 , CQ 出版社 C2]fMS-DOS 工ンサイクロペディア Vo [ 20 ] TLSI C ー 86 Ver 3.2 試食版ユーザー もおもしろいて、しよう。今回は機種依存を 避けるため , あえて追加していません。 ズマニュアル』 , 工ノレ・エス・アイジャ lume 1 , 2 』 , アスキー C3]fMS-DOS 3.1 プログラマーズリファレ 複数のコンパイラに条件コンパイルて、対 応したため , リストが見にくくなってしま ンスマニュアル』 , NEC C4]fMS-DOS 3.1 マクロアセンプラマニュ いました。基本的にはコンパイラごとに説 明した手法を用いていますのて、 , 詳細はリ アル』 , NEC [5] 「 MS-DOS 3.1 ューザーズリファレンス ストを参照してください。コンパイルは Fi g. 5 のように行います。 マニュアル』 , NEC [6]fMS-DOS 3.3B プログラマーズリファ まとめ レンスマニュアル』 V01. 1 , V01. 2 , N EC [7] 「 MS-DOS 3.3B ューザーズリファレン 今回は一風変わった常駐しないデバイス ドライバを取り上げてみました。今回の例 スマニュアル』 , NEC て、初期設定ルーチンの最後てフリーメモリ [ 8 ] rMicrosoft C 6.00A ProfessionaI De 開始アドレスを設定するように変更すれば , vel opment System Programming Gu 本来の常駐デバイスドライバを記述するこ ide 』 , Microsoft [ 9 ] fMicrosoft C 6.00A Professional De とがて、きます。 参考として 1991 年 7 月号の特集て取り上げ vel opment System Reference 』 , Mic た ESC/P プリンタドライバを今回の手法て、 rosoft 書き直したもの (escp_prn. c) を付録ディスク [ 10 ] 「 Microsoft C 5.1 Optimizing Compi に収録しました。 ler User's Guide 』 , Microsoft ただし , 常駐するデバイスドライバて、は [ 11 ] 『 Microsoft C 5.1 Optimizing Compi 特集て、紹介した TSR 型デバイスドライバの ler Language Reference 』 , Microsoft 手法のほうが ADDDRV/DEI DRV コマンド [ 12 ] 「 Microsoft C 5.1 Optimizing Compi を使用しなくてもコマンドラインから常駐 ler Mixed Language Programming G 部を解放てきるため , 使い勝手ははるかに uide 』 , Microsoft よいと思います ( プログラムは少し複雑にな [ 13 ] fMicrosoft C 5.1 Optimizing Compi りますが ) 。 ler Run- Time Library Reference 1 , なお , 付録ディスクに収録した ESC / P プ 2 』 , Microsoft リンタドライバ ( e p ー prn. c ) はデバイスドラ [ 14 ] TTURBO C 2.0 USER'S GUIDE 』 , イバという性格上 , 本連載の趣旨に反して BORLAND 機種依存を避けることがて、きません。手元 [ 15 ] TTURBO C 2.0 REFERENCE GUI に資料のある PC ー 9801 シリーズ , J ー 3100 シリ DE 』 , BORLAND 愛読者プレゼント 本連載の筆者 , 中島信行氏から愛読者プ レゼントとして中島信行著 , CQ 出版社刊 ー MS ー DOS メモリ管理ソフト技法』 ゴ C によるメモリ管理技法』 「 MS ー DOS 完全活用法」 3 冊 1 組をご提供いただきました。、ご希望 の方は , 官製葉書に本連載に対するご意 見をご感想・ご要望などを明記のうえご 応募ください。 4 月 18 日消印までを有効と させていただきます。なお , 当選者の発 表は商品の発送をもってかえさせていた だきます。 あて先 〒 108 東京都港区高輪 2 ー 19 ー 13 NS 高輪ビルソフトバンク ( 株 ) C マガジン編集部 「新 MS ー DOS プログラミング入門」係 96 C MAGAZINE 1992 4

刀牛 = = ロ 0 グラフィックライプラリ② 第 6 回 安田英之 ( 株 ) プロシード 先月に引き続いて , dJgcc の旧 M-PC 用グラフィックライ プラリⅱ bg 「と , その PC -9801 への移植について解説しま す。今回は , クラスとして実現された C 十十用のライプラリ を紹介します。また , 386 版の gas を使ったアセンプリ言語で のプログラミング時の注意点も説明します。 ・デフォルト描画色 y, w, h を指定すると , 収まるように領域が ・ビットマップデータ 縮小されます。 などの情報が格納されています。 int GrRegion :. MaxX ( ) このような仕様を考えると , ウインドウ int GrRegion :. MaxY ( ) システムのべースとして使うことを考慮し それぞれ矩形領域内の相対座標の x 成分 , C ライプラリについては前回説明したの たライプラリのように思えます。 y 成分の最大値を返します。 て、 , 今回は C 十十ライプラリ ( *. (c) のみを GrRegion * GrScreenRegion ( ) int GrRegion : : SizeX ( ) 解説します。 C 十十の知識がある程度必要 グラフィック画面全体に対応する矩形領 int GrRegion : : SizeY ( ) て、す。 域を生成します。幅 , 高さはグラフィック それぞれ矩形領域内の幅・高さを返しま 画面の大きさと同じてす。また , この矩形 す。 MaxX ( ) 十 1 および MaxY ( ) 十 1 と同 reglon. CC 領域に対して描画を行い , 直接グラフィッ じて、す。 このファイルて、は , GrRegion というクラ ク画面に反映されます。 void GrRegion : : P10t スを定義しています。これは , グラフィッ (int x, int y, int c) GrRegion : : GrRegion ( ) クス操作の対象となる矩形領域を管理する 矩形領域内の相対座標 ( x , y ) の位置に色 幅・高さがともに 0 の , 空の矩形領域を生 クラスてす。この矩形領域は , VRAM 上に 成します。 c< ドットを描画します。 取ることも , メインメモリ上に置くことも GrRegion :. GrRegion (int w, int h) 引数 c を省略するか , あるいは c に一 1 を指 て、きます。さらに , 次に述べる b ⅱ t. cc を使っ Ww ドット , 高さ h ドットの矩形領域を生 定すると , その矩形領域のデフォルト描画 て矩形領域間の転送がてきるのて , メイン 成し , その大きさのビットマップを収める 色が使われます ( このへんが C 十十の便利な メモリ上の矩形領域と VRAM 上の矩形領域 バッフアがメインメモリ上に取られます。 ところて、す ) 。以下のメソッドについても引 との間の転送も簡単に行えます。 GrRegion : : ¯GrRegion ( ) 数 c の扱いはこの PIot と同様て、す。 また , ある矩形領域の中に収まるような 矩形領域を解放 ( 破壊 ) します。 void GrRegion : : Line(int xl, 部分矩形領域を指定することがてきます。 int yl, int x2, int y2, int c) GrRegion * GrRegion : : SubRegion 各矩形領域には , 矩形領域内の相対座標 ( xl , (l) から (x2, (int x, int y, int w, int h) ・幅・高さ y2 ) への線分を描画します。 現在の矩形領域の中の相対座標 (), y) の ・画面上での絶対位置 位置に部分矩形領域 (subregion) を作り , そ void GrRegion : : HLine(int xl, ・親矩形領域からの相対位置 int x2, int y, int c) の部分矩形領域を返します。 ( 部分矩形領域の場合のみ ) (xl, y ) から (x2, y ) への線分を描画しま 親の矩形領域の中に収まらないような x, djgcc 詳解講座・ HellO GCC World 83 グラフィックライプラリ C 十十ライプラリの仕様

ライフボート lnformation from Compiler Makers Q PC ー 9801 シリーズで , DOS / 16 M を使ったツールを RAM ディスク などと共存させる場合に , 拡張メ モリの競合が起こらないように環 境変数を適切に設定する必要があ ります。設定すべき値を取得する いい方法はありませんか。 A MS-DOS についてくる RAM DISK. SYS や EMM. SYS の場合 , これらのデバイスドライバが使用 した残りの拡張メモリの大きさが , 0040 : 0001 番地に 128K バイト単位 て入っています。ただし , 将来の 機種にわたって , このアドレスに 拡張メモリの大きさが格納される ことはメーカによって保証されて いるわけてはありませんのて、 , 新 しい機種や型名が同じても ROM が 変わったりした場合には , 確認が 必要てす。しかし , このことはか なり広く知られているのてあまり 心配はいらないと思われます。ま ハイレゾモードては , メモリ ウインドウ機構により , デフォル との状態ては , 80000h—BFFFFh 番地が , 100000h ~ 13FFFFh 番地 と同じ RAM に割り付けられていま すから , 拡張メモリとしては , 14 0000h 番地から使用するように指定 しなければなりません。ハイレゾ モードとノーマルモードの区別を プログラムて行うには , 0050 : 00 01 番地の第 3 ビットを参照して , そ の値が 1 の場合には , ハイレゾモー ドになります。 List 1 のようなプロ グラムて , 設定値が判断てきると 思います。なお , この部分を DOS / 16M が自動的に行えるように , 現 在作業中てす。 Q stdaux を使って RS ー 232C ポー トを通して , データのやり取りを したいのですが , データをうまく 受け取れません。データの送信は 行えるのですが , stdaux からの読 み込みはできないのですか。 A stdaux は , 読み書きの両方が 可能て、す。 f 叩 en 関数のパラメータ て、いうと , 、、 r 十〃て、オープンされた 状態になります。てすから , ひと つのファイルポインタ stdaux て、 , 読み込みと書き込みを兼用するこ とがてきます。ただし , こて、注 意が必要なことは , 読み込み状態 から , 書き込み状態へ移るとき , または , その逆に書き込み状態か ら読み込み状態へ移るときに , モ ードを切り換えることを知らせる ために , fseek 関数を呼び出さなけ ればならないということてす。し たがって , fprintf 関数などを用い て , stdaux に書き込んだ後 Mfget s 関数を使って stdaux から読み込む 場合には , fgets 関数を使用する前 に , fseek (stdaux, OL, I) を呼び 出さなければなりません (List 2 参 照 ) 。 fseek 関数に渡すパラメータの 意味は , ファイルポインタ stdaux に対して , ファイル内の現在の位 置から相対的に 0 バイト移動 , すな わち移動しないということて , うすることにより副作用を与えず に , f ek 関数を呼び出すことがて きます。 Q マニュアルには , 日本語処理 を行うときに一 e0 〃オプションを指 定するように書かれていますが , この指定をしなくても , 何も異常 が見られません。もちろん , プロ グラム中には , 漢字を表示したり , 日本語文字列を扱う箇所が多数あ ります。なぜでしようか。 A 文字列の中て , \ 記号は特別な 意味を持ちます。たとえば , \ 記号 の後に , n があれば , 改行コード (ASCII コードの 0x0C ) に変換され ます。 MS-DOS 上て、は , 漢字コー ドとしてシフト JIS コードが使われ ますが , シフト JIS コードの第 2 バ イトにはこの \ 記号と同じ値 ( 0x5C ) を持っ漢字があります。たとえば , 、、導クという漢字のシフト JIS コード は , 0X895C てすから , 、、噂〃という 文字列は , 、、 \ X89 \ 〃と同値て、す。 すると , 第 2 バイトの次の引用符 は , 文字列終了の引用符て、はなく , 文字列中に引用符を表示するコー List 1 1 : #include く s i0. h > Lattice C ドになってしまい , 文字列を終了 させる引用符がなくなってしまい ます。 ー e0 オプションの日本語処理と は , 文字列中の漢字コードを正し く認識し , 漢字の第 2 バイトが \ 記 号と同じコードてあっても , \ 記号 の処理をしないようにするオプシ ョンて、す。て、すから , 、、クという 文字列を一 e0 オプションなして , コ ンパイルした場合には , コンパイ ルエラー ( 文字列が閉じていない ) になりますが , ー e0 オプションをつ ければ , 正しくコンパイルてきま す。また , 偶然にも第 2 バイトに \ 記 号と同じコードを含んだ漢字コー ドを使っていなかった場合には , ー e0 オプションをつけても , つけな くても , 正しくコンパイルて、きま す。 2 : unsigned char far * DATA401 = ( si 馴 char far * ) 0X00400001 : 3 : unsigned char far 事 DATA501 = ( 凹 si 馴 char far * ) 0X00500001 : 4 : 皿ⅲ ( ) 6 : if(*DATA501 & 0X08 ) ( / * High resolution * / printf("set DOS16M = 1 280 ー " , *DATA401 * 128 + 1024 ) : 9 : else ( / * NormaI * / printf("set DOS16M = 1 01 \ n " , *DATA401 * 128 ) ; 11 : 10 : 8 : 7 : List 2 lnformation from Compiler Makers 161 17 : fprintf(stdaux, " : 16 : fseek(stdaux, 0 し 1 ) : 15 : printf("Received ね : buff) : 14 : fgets(buff, 80 , stdaux) : 13 : fseek(stdaux, 0 し 1 ) : 12 : fprintf(stdaux, Require reply"); 11 : fprintf(stdaux, "Transfer parameter") : 10 : fprintf(stdaux, "Transfer commnad") : 9 : system( ” S般記「 0 1200 b8 none sl xon ” ) : 8 : memset(buff, 0 , 8 の ; 6 : char 面 ff [ 8 の : 4 : main() 3 : #include く string. h> 2 : #include く stdlib. h> 1 : #include く s i0. h 〉 7 :

いない部分を再利用て、きるようにします。 文字列のごみ集めて、は , どの変数からも 指されていない部分が不要な部分になりま す。たとえば , Fig. 1 (b) の左端の、、 he110 〃は 使われていないのて , 回収の対象になりま す。このままて、は空き領域が細切れになっ ているのて、 , 使っているすべての文字列を 先頭寄りに移動して空き領域をひとつにま とめなければなりません。これを詰め直し (compaction) といいます。同じごみ集めを 使うのて、も , Lisp のように割り当てるメモ リプロックの大きさが一定の場合には詰め 直しは必要ありません。 ごみ集めを行うためには , ガべージコレ クタがどのメモリプロックが使用中て、ある かを識別て、きなければなりません。つまり , ごみ集めによって管理を行うためには , ヒ ープ領域を『行儀よく』使わなければなり ません。 Lisp て、は , 大もとのセルから到達 可能て、あるかどうかて、 , 判断することがて、 きます。また , BASIC, awk, perl の可変 長文字列て、は , すべての変数をチェックす れば , ヒープのうちどの部分が使用中て、あ るかがわかります。 C 言語の ma Ⅱ oc 関数て、割り当てたプロック は , 使用中て、あるかどうかを機械的に判断 することはて、きません。 malloc て、割り当て たメモリプロックがいつ不要になるかは , プログラムを書いた人だけが知っています ( 応々にしてプログラムを書いた人にもわか らなくなってしまい , バグの原因になりま す ) 。したがって , ガべージコレクタによっ てメモリを回収再生することはて、きず , 明 示的に free 関数を使って解放しなければなり ません。ガべージコレクタについては , のくらいにしておきましよう。 片化と詰め直し 割り当てるプロックの大きさが固定長の ほうがメモリの管理は楽て、す。なぜなら , プロックの大きさが可変長の場合には , 断 78 C MAGAZINE 1 2 4 片化 (fragmentation) という現象が発生する からて、す。たとえば , 1000 バイトのヒープ 領域があったとします。このヒープ領域か らプロックを割り当て / 解放を行って Fig. 2 (a) の状態になったとしましよう。ここて、ア ミのかかった部分が使用中 , そうてない部 分が空いている領域て、す。 1000 バイトのう ち 600 バイトが使用中て、 400 バイトが空き領 域になっています。 この時点て、 200 バイトのプロックの割り当 て要求があったとしましよう。しかし Fig. 2 ( a ) からわかるように , 合計て、 400 バイトの 空きがあるにもかかわらず 200 バイト連続し た空き領域は存在しないのて、 , 割り当てに 失敗してしまいます。このように , 空き領 域が細かなプロックに分散してしまって有 効に活用て、きない現象を断片化といいます。 割り当てるプロックの大きさが一定てあれ ば , 断片化は問題になりません。 ヒープの使用中のプロックを移動すれば 断片化を解消することがてきます。これを 詰め直し (compacting) といいます。 Fig. 2 Fig. 2 断片化と詰め直し 200 (a) 200 (b) Fig. 3 断片化の防止 ① 100 300 200 200 200 200 300 100 600 100 100 100 150 400 300 300 300 100 400 150