プログラムとは、特定のタスクを実行するコンピュータ命令のセットである。 プログラムは、低水準コンピュータ言語であるアセンブラでも記述でき、C のような マシンに依存しない高水準のプログラム言語でも記述できる。オペレーティ ングシステムは、特別なプログラムであり、ユーザによるスプレッドシートやワード プロセッサといったアプリケーションの実行を可能にするものである。この章 では、基本的なプログラミングの原則を紹介し、オペレーティングシステムの目的や 機能の概観を述べる。
CPU がメモリから取り出して実行する命令は、人間が見ても全く意味不明である。 それらの命令はマシン語であり、コンピュータに何を実行すべきかを正確に伝達する。 例えば、16 進数 0x89E5 は、Intel 80486 の場合、ESP レジスタの内容を EBP レジ スタにコピーせよという命令に該当する。黎明期のコンピュータのために最初に 発明されたソフトウェアのひとつにアセンブラがある。それは、人間が読んで意味の わかるソースをマシン語に変換するプログラムである。アセンブリ言語は直接レジスタ を操作し、そこにあるデータを処理することができるが、その方法はマイクロプロ セッサに固有のものとなる。Intel X86 プロセッサのアセンブリ言語は、Alpha AXP マイクロプロセッサのアセンブリ言語とはかなり異なっている。次の Alpha AXP アセンブリコードは、プログラムが実行する処理の一種を示している。
ldr r16, (r15) ; Line 1
ldr r17, 4(r15) ; Line 2
beq r16,r17,100 ; Line 3
str r17, (r15) ; Line 4
100: ; Line 5
第一文(Line1)は、レジスタ 16 に対して、レジスタ 15 に保持されたアドレスに ある(メモリの)内容をロードする。次の命令は、レジスタ 17 に対して、次のアドレス (レジスタ 15 + 4)のメモリ内容をロードする。Line 3 は、レジスタ 16 とレジスタ 17 の内容を比較し、同一なら Label 100 に分岐する。両方のレジスタが 同じ内容でない場合、プログラムは 4 行目に移行し、レジスタ 17 の内容がメモリに 保存される。同じ内容の場合は、データを保存する必要はない。アセンブリレベルの プログラムは、冗長であり、トリッキーな書き方が必要で、エラーが生じやすい。 Linux カーネルはアセンブリ言語で書かれた部分はほとんどなく、その部分も処理効 率を上げる目的のためだけに書かれたものであり、それらは特定のプロセッサに固有 のものとなっている。
アセンブリ言語でプログラムを書くことは、困難で時間のかかる仕事である。 エラーを生じやすく、出来たプログラムは特定のプロセッサファミリーに束縛される ので移植性がない。マシンに依存しない C のような言語を使う方がずっとよい。 C を使えば、C で利用可能な論理アルゴリズムとデータ構造を使ってプログラムを 書くことができる。コンパイラと呼ばれる特別なプログラムは、C プログラム を読み込んで、アセンブリ言語に変換し、それによってマシン語を生成する。よく 出来たコンパイラは、優秀なアセンブリプログラマが書いたのとほとんど同じくらい 効率的なアセンブリ命令を生成することができる。Linux カーネルの大部分は、C 言語で書かれている。次に C プログラムの一部を示す。
if (x != y)
x = y ;
これは、先ほどのアセンブリコードの例とまったく同じ処理をするものである。 変数 x の内容が変数 y の内容と同一でない場合、y の内容が x にコピーされる。 C コードは、特定のタスクを処理するルーチンとしてまとめることができる。ルーチン は C でサポートされているすべての値やデータ型を返すことができる。Linux カーネル のような巨大なプログラムは、多数の独立した C ソースモジュールから構成されてい て、それぞれが独自のルーチンとデータ構造を持っている。そうした C のソースコード モジュールは、ファイルシステム処理コードのグループのように、論理的な機能 別にグループ化されている。
C では、種々の変数型がサポートされているが、変数とは、シンボル名で参照可能な メモリ内の位置のことである。上記の C のプログラムでは、x と y は、メモリ内の 位置を参照している。プログラマは、メモリ内に変数が置かれた位置を知る必要はな く、それに配慮する必要があるのはリンカ(linker)(下記参照)だけである。変数には、 さまざまな種類のデータ、整数、浮動小数点数を格納するためのものとポインタ (pointer)とがある。
ポインタは、アドレスを内容とする変数である。すなわち、他のデータのメモリ内 での位置を表す。x という変数があるとして、それがメモリ内のアドレス 0x80010000 に存在するとする。その場合、x を差すポインタ、たとえば px を作 ることができる。ここで px は、アドレス 0x80010030 にあるとする。だとすると、 px の値は、変数 x のアドレスである 0x80010000 を内容として持つ。
C を使えば、関連のある変数をデータ構造体としてまとめることができる。たとえ ば、次のようなデータ構造体があるとする。
struct {
int i ;
char b ;
} my_struct ;
上記の my_struct というデータ構造は、ふたつの要素を含んでいる。i という整数 (32 ビットのデータ記憶領域)と、b という文字(8 ビットのデータ)という要素である。
リンカとは、いくつかのオブジェクトモジュールやライブラリをリンクさせ、ひと つの整合性のあるプログラムを作成するためのプログラムである。ここでオブジェクト モジュールとは、アセンブラやコンパイラが出力したマシンコードであり、それに は、実行可能なマシンコードとデータが含まれると同時に、リンカがモジュールを 結合してひとつのプログラムを作るための情報も含まれている。たとえば、ある モジュールには、あるプログラムのデータベース関数のすべてが含まれているかもし れず、ほかのモジュールにはコマンドライン引数を処理するための関数が含まれてい るかもしれない。リンカはそうしたモジュール間での参照関係を解決するので、それ によって、あるモジュールで参照されているルーチンやデータ構造が、別のモジュー ルで実際に存在できるようになる。Linux カーネルという単一の巨大なプログラム は、多くの構成要素であるオブジェクトモジュールを相互にリンクすることによって 作られている。
ソフトウェアがなければ、コンピュータは単に熱を放出する電子部品の固まりに すぎない。ハードウェアがコンピュータの心臓だとすると、ソフトウェアはその 魂である。オペレーティングシステムは、システムプログラムの集合体であり、それ がユーザによるアプリケーションプログラムの実行を可能にしている。オペレー ティングシステムは、システム上の実(real)ハードウェアを抽象化して、システムの ユーザやアプリケーションに仮想マシンを提供する。オペレーティングシステムは、 本当の意味での「システム」を提供しているのである。大部分の PC では、複数の オペレーティングシステムの走行が可能であり、それらはそれぞれに違った外観と 操作性を持っている。Linux は、機能的には別個の複数の部分から成り立っていて、 それらがひとつになってオペレーティングシステムを構成している。Linux の特徴的 な部分のひとつが、カーネルである。しかし、それさえもライブラリやシェルがなけ れば役に立たない。
オペレーティングシステムがどういうものか理解するために、非常に単純なコマンド を打ったときに何が起こるのかを考えてみよう。
$ ls
Mail c images perl
docs tcl
$
$ は、ログインシェル(ここでは、bash)が出力するプロンプトである。
プロンプトとは、ユーザのコマンド入力をシェルが待っているということを
意味する。ls と打ち込むと、キーボードドライバは、文字が打ち込ま
れたことを認識し、そのコマンドをシェルに渡す。シェルは、それを処理するため
に、同じ名前の実行イメージがあるかどうかを探す。シェルが /bin/ls に
そのイメージがあることを発見すると、カーネルサービスを呼び出す。呼び出された
カーネルサービスは ls の実行イメージを仮想メモリに置いて、その実行を
始める。実行された ls のイメージは、カーネルのファイルサブシステムを
呼び出して、どのようなファイルがあるのかを探し出すよう命じる。ファイルシステ
ムは、キャッシュしておいたファイルシステムの情報を利用するか、ディスクデバイ
スドライバを使ってディスクからその情報を読み出させる。あるいは、(Network File
System(NFS)経由でファイルシステムをリモートマウントしている場合)ネットワーク
ドライバを使用してリモートマシンと情報交換をし、ローカルシステムがアクセスし
ているリモートファイルの詳細について情報を探し出させるかもしれない。その情報
がいずれにある場合でも、ls はそうした情報を出力し、ビデオドライバが
それをスクリーンに表示する。
上記の説明はやや複雑に思えるかもしれない。しかし、この非常に単純なコマンド の実行からでも明らかなように、オペレーティングシステムとは、実際、協調して働 く一連の関数のセットであり、それらが一体となることで、ユーザに整合性のあるシ ステムの概観を提供しているのである。
メモリ等のリソースが無限にあるなら、オペレーティングシステムが果たすべき 役割の多くは、余計なものとなるかもしれない。どんなオペレーティングシステム にもある基本的なトリックのひとつに、少ない物理メモリを実際以上に見せる能力 がある。この一見巨大なメモリは、仮想メモリと呼ばれる。このアイデアは、システム 上で実行されているソフトウェアを騙して、大量のメモリがあるように思いこませる というものである。すなわち、システムはメモリをページという扱いやすい単位に 分割して、システム実行時に、そうしたページをハードディスク上にスワップ(swap) する。ソフトウェアがそれに気付かないのは、もうひとつのトリックであるマルチ プロセス機能のせいである。
プロセスとは、実行中のプログラムであると考えることができる。個々のプロセス
は個別の実体であり、それぞれが特定のプログラムを実行している。Linux
システム上のプロセスを見た場合、かなり多くのプロセスが存在することに気付くだ
ろう。たとえば、ps とタイプすると、筆者のシステム上では次のプロセスが
表示される。
$ ps
PID TTY STAT TIME COMMAND
158 pRe 1 0:00 -bash
174 pRe 1 0:00 sh /usr/X11R6/bin/startx
175 pRe 1 0:00 xinit /usr/X11R6/lib/X11/xinit/xinitrc --
178 pRe 1 N 0:00 bowman
182 pRe 1 N 0:01 rxvt -geometry 120x35 -fg white -bg black
184 pRe 1 < 0:00 xclock -bg grey -geometry -1500-1500 -padding 0
185 pRe 1 < 0:00 xload -bg grey -geometry -0-0 -label xload
187 pp6 1 9:26 /bin/bash
202 pRe 1 N 0:00 rxvt -geometry 120x35 -fg white -bg black
203 ppc 2 0:00 /bin/bash
1796 pRe 1 N 0:00 rxvt -geometry 120x35 -fg white -bg black
1797 v06 1 0:00 /bin/bash
3056 pp6 3 < 0:02 emacs intro/introduction.tex
3270 pp6 3 0:00 ps
$
筆者のシステムに複数の CPU があれば、それぞれのプロセスを、(少なくとも 理論的には)違う CPU 上で実行することが可能である。しかし残念ながらひとつ しかないため、オペレーティングシステムはここでもトリックを使って、短い時間で プロセスを順番に実行する。その時間間隔はタイムスライス(time-slice)と呼ばれ、 このトリックは、マルチプロセッシング(multi-processing)もしくはスケジューリン グ(scheduling)と呼ばれる。すなわちこれは、個々のプロセスを騙して、自分が唯一の プロセスであると思い込ませるようにするものである。個々のプロセスは他のプロセ スから保護された状態にあるので、ひとつのプロセスがクラッシュしたりおかしな動き をしても、他のプロセスに影響を与えることはない。オペレーティングシステムはこの ことを実現するために、個々のプロセスに自分だけがアクセスできる個別のアドレス 空間を付与している。
デバイスドライバは、Linux カーネルの重要な部分を形成している。オペレーティ ングシステムの他の部分と同様に、デバイスドライバは非常に特権的な環境で 実行されるため、それらが上手く動かない場合は酷い状態になることがある。デバイス ドライバは、デバイスを制御すると同時に、オペレーティングシステムとハードウェア 間での相互作用も制御する。たとえば、ファイルシステムは、IDE ディスクにブロック 単位の書き込みを行うとき、汎用のブロックデバイスインターフェイスを利用する。 ドライバはその IDE ディスクの詳細に気を配り、そのディスク固有の処理が適切に 実行されるようにする。デバイスドライバは、操作対象であるコントローラチップに 固有のものであるため、たとえば、システムで NCR810 SCSI コントローラを使用してい る場合、NCR810 SCSI ドライバーが必要になる。
Linux では、Unix と同様に、システム上で個別のファイルシステムを使用する場
合、そのアクセス手段として、(ドライブ番号やドライブ名などの)デバイス識別子は
利用しない。そのかわり、ファイルシステムは、単一の階層的なツリー構造に組み込
まれ、それによって単一の実体として表現される。Linux は、新しい個々のファイル
システムをその単一のファイルシステムに付け加える際、たとえば /mnt/cdrom といったマウントディレクトリ上にマウントするという方法を取る。Linux の
最も重要な特徴のひとつは、多くの異なるファイルシステムのサポートである。
それによって、Linux は、非常に柔軟で、他のオペレーティングシステム
とも上手く共存できるものになっている。Linux の最も一般的なファイルシステムは、
EXT2 ファイルシステムであり、このファイルシステムは、ほとんどの Linux
ディストリビューションでサポートされている。
ファイルシステムは、システムのハードディスク上に保存されているファイルや ディレクトリに関する分かり易い展望をユーザに与える。その際、ファイルシステム のタイプや、基礎となる物理デバイスの性質の違いは捨象される。Linux は多くの異 なるファイルシステム(たとえば MS-DOS や EXT2)を透過的にサポートし、マウントされ たファイルやファイルシステムをひとつに統合された仮想ファイルシステムとして 提供する。したがって、一般的に、ユーザやプロセスは、特定のファイルがどのよう な種類のファイルシステムに属しているのかを知る必要なしに、それを使用できる。
ブロックデバイスドライバは、物理的なブロックデバイスのタイプ(たとえば、IDE や SCSI)の違いを隠すことが出来る。それゆえ、ファイルシステムに関する限り、物理 デバイスは、データブロックの線形的な集合にすぎない。ブロックサイズは、デバイス によって異なり、たとえば、フロッピーディスクは 512 バイトが一般的であり、IDE ハードディスクでは 1024 バイトが一般的である。しかし、これについても、システム のユーザからは隠されている。EXT2 ファイルシステムは、そのファイルシステムが置 かれたデバイスがどのようなものであっても、同じ外観を持つ。
オペレーティングシステムは、システムの現在の状態について多くの情報を保持 する必要がある。システム内で何かが起こったら、それに関するデータ構造は 現在の状態を反映するように書き換えられなければならない。たとえば、ユーザがシス テムにログオンすると、新しいプロセスが生成される。カーネルは、新しいプロセス を表現するデータ構造体を作成して、それ以外のシステム上の全プロセスを表現し ているデータ構造体にそれをリンクさせなければならない。
このようなデータ構造体の大部分は、物理メモリ内に存在し、カーネルとそのサブ システムからしかアクセスできないようになっている。データ構造体には、データと ポインタ、すなわち他のデータ構造のアドレスやルーチンのアドレスが含まれている。 それらすべてを一度に見ようとした場合、Linux カーネルによって利用されている データ構造体は、非常に紛らわしく分かりにくいものに思えるかもしれない。しか し、すべてのデータ構造体には目的があり、数種のカーネルサブシステムから利用 される(複雑な)構造体もあるが、一般的には、それらは最初に一見した時の印象より もずっとシンプルである。
Linux カーネルの理解は、そのデータ構造と、Linux カーネル内の種々の 関数がそれを使用する方法とを理解できるかどうかにかかっている。本書は、 Linux カーネルの説明に際し、そのデータ構造の解説に重点を置く。 個々のカーネルのサブシステムを説明するときは、そのアルゴリズム、処理方法と 同時に、それらが使用しているカーネルのデータ構造という観点を重視する。
Linux は、多くのソフトウェア工学上のテクニックを使って、データ構造を相互に リンクしている。多くの場合、Linux では連結あるいは連鎖データ構造体が使用されて いる。もし、個々のデータ構造体が、単一のプロセスやネットワークデバイスといった 個別の現象や事物を記述するだけなら、カーネルにはそれらの個別データをすべて 探し出す能力が必要になる。連結リストでは、ルートポインタがリスト上の 最初のデータ構造体もしくは要素のアドレスを含んでいて、それぞれのデータ構造体が リスト上の次の要素へのポインタを含んでいる。最後の要素に含まれる次の要素への ポインタは(リストの終わりを示す意味がある) 0 か NULL のどちらかである。 二重連結リストでは、個々の要素が、リスト上の次の要素へのポインタとひとつ前の 要素へのポインタの両方を含んでいる。二重連結リストを使えば、リストの真ん中で 要素の追加や削除をすることが容易になるが、ただし、メモリへのアクセス頻度は増加 する。これは、メモリアクセスと CPU サイクルのどちらを優先するかという、オペレー ティングシステムに典型的な二者択一の問題である。
連結リストは、データ構造体を結びつけるには手軽な方法だが、連結リストを辿る のは非効率な場合がある。特定の要素を検索するなら、リスト全体を簡単に眺めて、 その上で必要な要素を見つけるようにすべきだろう。Linux は、ハッシング(hashing) という別のテクニックを使って、連結リストの限界を克服している。 ハッシュテーブル(hash table)は、ポインタの配列(array)もしくはベクトル(vector) である。配列もしくはベクトルとは、単にメモリ内に連続する一連の要素のことであ る。たとえば、本棚は、本の配列(array)であると言える。配列はインデックスでアクセ スが可能である。インデックスとは配列へのオフセット(offset)である。再度本棚の 類推で考えると、それぞれの本は、本棚上の位置で表すことができる。5 冊目 (offset)の本という言い方でそれを指定できる。
ハッシュテーブルは、データ構造体に対するポインタの配列であり、そのインデッ クスは、それらのデータ構造体内の情報から抽出される。ある村の人口を表すデータ 構造体があるとすると、その住人の年齢をインデックスとして使うことができる。 特定の住人のデータを検索する場合、年齢をインデックスとして使用して、その村の 人口についてのハッシュテーブルを検索し、該当するポインタを辿れば、ポイント先 の構造体にその住人の詳細が含まれている。残念ながら、村には、同年齢の住人が 大勢いる場合が多いので、ハッシュテーブルのポインタは、同年齢の住人を記述した データ構造体の連鎖かリストに対するポインタになるだろう。しかし、こうした短 い連鎖を検索することは、データ構造体すべてを検索するよりもずっと高速である。
ハッシュテーブルを使うと、よく利用されるデータ構造体へのアクセスを高速化で きるので、Linux は、しばしばハッシュテーブルを、キャッシュ(cache)の実装のために 使用している。キャッシュはすばやいアクセスが必要な際の手軽な情報源であり、 通常、手に入る情報のフルセットに対するサブセットとなっている。 カーネルがあるデータ構造体に対し頻繁にアクセスする場合、そのデータ構造体は キャッシュに入れられて保存される。キャッシュの欠点は、単純な連結リストや ハッシュテーブルよりも使用と管理が複雑になることである。もしデータ構造体が キャッシュ内で見つかれば(これは、キャッシュヒット(cache hit)と言われる)、 問題のない良い結果が得られる。しかし、もし見つからない場合、関連するすべて のデータ構造体が検索され、該当するデータ構造体が存在した際には、それを キャッシュに追加しなければならない。データ構造体をキャッシュに追加すると、 古いキャッシュエントリを破棄する必要が生じる。Linux はどれを破棄するか決定し なければならないのだが、問題は、破棄されたデータ構造体は、Linux が次に必要とす るデータそのものである場合があることである。
Linux はしばしばそのインターフェイスを抽象化する。インターフェイスとは、 特定の方法で操作されるルーチンとデータ構造体の集合である。たとえば、すべての ネットワークデバイスドライバは、一定のルーチンを提供しなければならない。 そして、そのドライバのルーチンが、デバイス固有のデータ構造体を処理する。 この方法を使うと、汎用コードから成るレイヤーの存在が可能になる。すなわち、 汎用レイヤーのコードは、下層レイヤーにあるデバイス固有のコードが提供する サービス(あるいは、インターフェイス)を使用するわけである。ネットワーク レイヤーは汎用コードから成り、その汎用コードが、標準インターフェイスに準拠 した、デバイス固有のコードによってサポートされている。
しばしばそうした下層レイヤーは、起動時に上層レイヤーと伴に登録される。
この登録の際には、通常、データ構造体を連結リストに追加する処理がなされる。
たとえば、あるファイルシステムがカーネルに組み込まれている場合、その個々の
ファイルシステムは起動時にカーネルに登録される。あるいは、もしモジュールに
なっている場合は、ファイルシステムが最初に呼びだされたときに、登録がなされ
る。/proc/filesystems というファイルを見れば、どのファイルシステムが
登録されているかが分かる。
カーネルへの登録に使用されるデータ構造体には、しばしば、複数の関数へのポイン
タが含まれている。それらは、特定のタスクを実行する関数のアドレスである。
再度、ファイルシステムの登録を例にとると、個々のファイルシステムが登録の際に
カーネルに渡すデータ構造体には、そのファイルシステムに固有のルーチンのアドレ
スが含まれている。そして、そのルーチンのアドレスを使用して当該ルーチンを呼び
出すことで、当該ファイルシステムがマウントされる仕組みになっている。