Webエンジニアのブログ

「はじめてのOSコードリーディング UNIX V6で学ぶカーネルのしくみ」要約メモ


UNIX V6の全体像

UNIX V6は1975年にベル研究所からリリースされ、本書ではオリジナルと言える「DEC社のPDP-11/40」というプロセッサ上で動くカーネルを扱う。UNIX V6のカーネルは次の機能を提供している。

  • プロセスの管理
  • メモリ管理
  • ファイルシステム
  • ファイルと周辺デバイスで共通のI/O
  • 割り込み
  • 端末処理サポート

CPUやディスク操作は、カーネルやデバイスドライバによって隠されている。ユーザプログラムはシステムコールというしくみを使って、カーネルに要求を行う。

PDP-11

PDP-11/40は16ビットマシンで、命令やデータを基本的に16ビットの単位で処理する。このようなデータ単位をワードと呼び、PDP-11/40では1ワードは16ビットである。PDP-11/40はUnibusという18ビットのアドレスバスを持つバスを入出力に用いる。PDP-11/40や周辺デバイスのレジスタをメモリの最上位8Kバイトにマッピングし、メモリ操作を行うのと同様の方法でそれらのレジスタを操作する。このことをMemory Mapped I/Oと呼ぶ。

PDP-11/40はプロセッサステータスワード(PSW)という16ビットのレジスタを持ち、そこでプロセッサの状態などを表している(15~14ビットが00ならカーネルモード、など)。またr0からr7までの8つの汎用レジスタがあり、特に重要なものはr5(フレームポインタ、環境ポインタ)、r6(スタックポインタ)、r7(プログラムカウンタ)である。プロセッサはr7で示されたメモリアドレスから命令を読み込み、処理する。r6のみカーネルモード用とユーザモード用に分かれている。

MMU(Memory Management Unit)はアドレス変換やアクセス権限の管理などを行う。PDP-11/40は8Kバイトのセグメントやページと呼ばれる単位で、プロセスが扱うメモリを管理する。権限のないメモリ領域へアクセスした場合などには、このMMUによってトラップ(第5章参照)が引き起こされる。PDP-11/40のメモリは8ビット単位にアドレスが振られ、18ビットのアドレスを持つ。容量は2^18で256Kバイトである。

プロセス

カーネルはプロセスという概念を用いて、実行中のプログラムを管理する。プロセスは一意のIDを持つ。プロセスごとにメモリが割り当てられ、各プロセスの仮想アドレス空間は独立しているため、他のプロセスと影響し合うことはない。カーネルは複数あるプロセスを随時切り替えながら、一つのプロセッサで処理を行う。これをTSS(タイムシェアリングシステム)と呼ぶ。

プロセッサはユーザモードとカーネルモードを持ち、PSWによって切り替えられる。モードが切り替えられると、仮想アドレスにマッピングされるメモリ領域がMMUによって切り替えられる。ユーザモードのときの仮想アドレス空間をユーザ空間、カーネルモードのときの仮想アドレス空間をカーネル空間と呼ぶ。カーネルプログラムはシステム起動時にメモリに読み込まれる。ユーザープログラムがカーネルプログラムを実行するためには、システムコールを発行しなければならない。

プロセスの数が増えてくるとメモリの容量が足りなくなるため、カーネルは定期的に休眠状態にあるプロセスなどをメモリからスワップ領域に対比する。これをスワップアウトと呼ぶ。メモリに復帰させることはスワップインと呼び、これらの処理はスワッピングと呼ぶ。

proc構造体とuser構造体

各プロセスの状態や制御は、proc構造体とuser構造体の組により管理される。

proc構造体は常にカーネルから必要とされる情報を扱う。カーネルはプロセスの状態を調べることがしばしばあるため、このproc構造体はメモリに常駐しておりスワッピングされることはない。この構造体にはプロセスIDやユーザーID、割り当てられたメモリサイズなどが格納されている。user構造体はプロセスがオープンしたファイルやカレントディレクトリ情報などを扱う。

プロセスに割り当てられるメモリ

各プロセスには、テキストセグメントとデータセグメントの2つの連続した物理メモリ領域が割り当てられる。テキストセグメントは読み取り専用であり、プログラムの命令列や機械語が格納されている。あるプログラムが複数同時に実行される場合は、1つのテキストセグメントをプロセス間で共有する。

データセグメントにはプログラムが使用する変数などのデータが格納される。データセグメントはプロセス間で共有されることはない。データセグメントは下位アドレスから順にPPDA、データ領域、スタック領域の3つで構成される。

PPDA(Per Process Data Area)は、user構造体とカーネルスタック領域からなるもの。カーネルスタック領域はカーネル処理の作業領域として使用される。PPDAのサイズは1Kバイトあり、ユーザ空間からアクセスすることはできない。データ領域は、グローバル変数や静的な変数が置かれる領域と、プロセスが動的にメモリ領域を管理するヒープ領域からなる。ヒープ領域の拡張にはシステムコールを発行する必要がある。スタック領域は、関数の引数やローカルデータなどを一時的に格納する領域のこと。必要になったときに自動的に拡張される。

仮想アドレス空間

各プロセスには64Kバイトの仮想アドレス空間が与えられる。各プロセスは16ビットの仮想アドレスを用いて物理メモリにアクセスする。仮想アドレスはMMUによって18ビットの物理アドレスにマッピングされている。

仮想アドレスを使うことにより、プロセスがスワッピングされてもメモリアドレスが変わらないため、物理メモリアドレスを意識しなくてよくなる。またプロセスごとにアクセスできる物理メモリ領域を指定することができ、アクセス管理が行える。分断された物理メモリ領域を連続した仮想メモリ領域にマッピングすれば、メモリの使用効率も高まる。

アドレス変換

MMUは、APR(Active Page Register)という、PAR(Page Address Register)とPDR(Page Description Register)の2つ1組のレジスタを用いて、アドレスマッチングを行う。PDP-11/40はカーネルモードとユーザモード用に2セットのARPを持つ。各プロセスの仮想アドレス空間はページ、もしくはセグメントと呼ばれる単位で管理され、1組のAPRが1ページに対応する。PARは物理アドレス上のアドレスに関する情報を保持し、PDRは各ページのブロック(64バイト単位)数やアクセス拒否などの情報を保持する。

プロセスの制御

プロセスのライフサイクル

  1. 親プロセスがforkシステムコールを発行して子プロセスを発行する(子プロセスは親プロセスの情報をコピーして生成する)
  2. 親プロセスはwaitシステムコールを発行して子プロセスの処理が完了するのを待つ
  3. 子プロセスはexecシステムコールを発行してプログラムを読み込む
  4. 子プロセスは実行し終えるとexitシステムコールを発行してプロセスを終了し、親プロセスに制御が移る
  5. 親プロセスは子プロセスの実行結果を取得し、子プロセスの後始末を行う

実行プロセスの切り替え

実行プロセスがカーネルのsleep()を実行すると、実行プロセスが休眠状態になって処理が中断された後、swtch()が呼ばれて実行プロセスが切り替わる。カーネルのsleep()が呼び出される時は、以下のような場合である。

  • ユーザプログラムがwaitシステムコールを発行したとき
  • 周辺デバイスの処理完了を待つとき
  • 使用中の資源が開放されるのを待つとき

プロセスの終了

プロセスの終了の手順は2段階ある。

  1. ユーザプログラムがexitシステムコールを発行し、プロセスをゾンビ状態にする。user構造体はスワップ領域に退避され、使用していたメモリ領域は開放される。
  2. 親プロセスのwaitシステムコール処理によって、子プロセスの終了状態が取得され、ゾンビ状態の子プロセスが始末される。

exitシステムコールはの主要な役割は次の通りである。

  • 開いていたファイルを閉じる
  • テキストセグメントを開放する
  • user構造体をスワップ領域にコピーする
  • データセグメントを開放する
  • プロセスをゾンビ状態にする
  • 親プロセスとinitプロセスを起こす
  • 自身の子プロセスが存在していたら、それらをinitプロセスの子プロセスにする

スワップ領域にコピーされたuser構造体は、親プロセスが子プロセスを始末するときに使用される。initプロセスはシステム起動時に生成され、そのようなプロセスの後始末や端末の初期設定などの債務を持っている。

メモリとスワップ領域の管理

物理メモリはcoremap[]で管理され、APRの最小管理単位である64バイトが管理単位になる。スワップ領域はswapmap[]で管理され、ブロック単位である512バイトが管理単位となる。これらの配列はシステムの起動時に初期化される。空き容量の獲得は、「配列の先頭からたどり、要求を満たす要素を探す」というFirst Fitと呼ばれるアルゴリズムである。

スワッピング

プログラムを実行するには命令列とデータをメモリに読み込まなければならない。メモリは高速で動作するが容量が限られているため、定期的にスワッピング処理を行わなければならない。スワップ領域に退避することをスワップアウト、復帰することをスワップインと呼ぶ。

プロセスがスワップインし、テキストセグメントがメモリに読み込まれても、スワップ領域中のテキストセグメントはそのまま残る。これはテキストセグメントが読み取り専用であり、データに差異が生まれることがないため、このような最適化処理が行われている。

割り込み

割り込みとは、周辺デバイスなどから要求があったときに実行プロセスを中断し、要求に対する処理を行った後、プロセスを再開する仕組みのことである。割り込み要求に対する処理を割り込みハンドラと呼ぶ。

割り込み要求にはブロックデバイスの動作完了通知や端末からの入力などがある。割り込みによって、あるプロセスがデバイスに対して動作要求を行ったあと、デバイスの動作が完了するまで別のプロセスの処理を行うことができる。もし割り込みの仕組みがなければ、定期的にデバイスが動作完了したかどうかをチェック(ポーリング)しなければならない。

割り込みハンドラはカーネルプロセスにより実行される。ユーザプロセスの実行中に割り込みが発生した場合は、ハードウェアによってカーネルプロセスに切り替えられる。割り込まれたプロセスの情報はカーネルスタックに退避される。

トラップ

トラップが発生すると、割り込みと同様に実行プロセスの中断と再開処理が行われる。トラップはCPU内部の出来事(0除算や割り当てられていないメモリへのアクセスなど)によって引き起こされる。システムコールはこのトラップを用いて実現されている。

優先度

各割り込みには0から7までの優先度が設定されている。PSWのプロセッサ優先度が、割り込み優先度以上の場合、その割り込みは処理されない。処理されるまで周辺デバイスは割り込み要求を送り続けることになる。トラップは優先度8であり、優先度に関わらずすぐに処理される。

クロック割り込みハンドラ

クロック装置とは、定期的にシステムに対して割り込みをかける装置のことである。システムはこのクロック割り込みを使って時刻の管理などを行う。

クロック割り込みハンドラは以下のような処理を行う。

  • クロック割り込みごとに行う処理
    • クロック装置のレジスタを再設定
    • 指定された時刻に登録された関数を実行
    • CPU時間のインクリメント
  • 1秒に1回行う処理
    • 時刻処理
    • sleepシステムコールでスリープしているプロセスを起こす
    • プロセスの実行優先度再計算
    • 再スケジューリングを促す
    • シグナル処理
  • 4秒に1回行う処理
    • lighting bolt

シグナル

シグナルはプロセス間通信を行う仕組みの1つである。プロセスは実行プロセスになった時などにシグナルを受け取っていないかチェックし、受け取っていればシグナルハンドラを実行する。ユーザ側でシグナルを無視したり、独自のシグナルハンドラを実行させることができる。

シグナルはkillシステムコールを発行することによって送ることができる。シグナルが送られると、その送られたプロセスのproc.p_sigにシグナルの種類を表す値が格納される。シグナルの処理が行われる前に新たなシグナルを受信すると、古いシグナルは上書きされてしまう。ただ最近のOSではシグナルをビットベクタなどで扱い、上書きされないようになっている。

シグナルを受信しているかどうかは、カーネルプロセスが「クロック割り込みハンドラ」「トラップ」などの処理で確認する。実行プロセス以外はシグナルの受信確認ができないため、シグナルを送っても即座にシグナルの処理が行われるとは限らない。

トレース

トレースとは子プロセスのシグナル処理のたびに、親プロセスが子プロセスに介入する機会が与えられる仕組みのこと。ptraceシステムコールを使い、子プロセスのデータなどを操作できる。これはデバッガなどで用いられる。

ブロックデバイス

デバイスドライバとは、デバイスの操作を行うプログラムのことである。デバイスドライバはデバイスドライバテーブルによって管理され、各デバイスはクラスと16ビットのデバイス番号の組で管理されている。クラスはブロックデバイスかキャラクタデバイスを指し、デバイス番号は上位8ビットがメジャー番号(デバイスの種類)、下位8ビットがマイナー番号(デバイスごとの数字)で構成されている。

デバイスを使用するためには、そのデバイスに対応するスペシャルファイルを作成しなければならない。スペシャルファイルにopen,read,write,closeシステムコールを発行することで、デバイスドライバが呼び出され、デバイスを操作できる。ユーザから見るとファイル操作と同じインターフェースでデバイスを操作できるようになっている。

ブロックデバイスサブシステム

ブロックデバイスに対するアクセス処理は、ブロックデバイスサブシステムに集約されている。これはいくつかの関数で構成されている。

ブロックデバイスサブシステムはバッファを用いてブロックデバイスとデータのやり取りを行う。バッファを用いる目的は2つある。1つめは、複数のプロセスから同時に同じブロックのアクセスが起きた時に整合性を保つためである。バッファは排他処理を行い、これを実現している。2つめは、よく読み書きするブロックのコピー(キャッシュ)をメモリ中に置くことで性能を改善するためである。

RAW(無処理)入出力と呼ばれる、バッファを経由せずかつブロックサイズ(512バイト)の制限を受けないデータ転送を行うこともできる。これはブロックデバイスのデータを丸ごとコピーしてバックアップを取るときなどに使用されている。

読み込み

読み込みには、同期読み込み非同期読み込みの2つがある。

同期読み込みはバッファを取得したあと、ブロックデバイスに対して読み出し要求を行いスリープする。ブロックデバイスの動作が完了すると、割り込みハンドラが呼び出される。その後バッファを自分で解放する。

非同期読み込みはブロックデバイスの読み込み動作が完了するのを待たずに処理を続ける。バッファは割り込みハンドラが実行するiodone()関数により自動的に解放される。非同期読み込みは先読みに使用される。先読みは、あるファイルのブロックを順に読んでいるとき、次のブロックのデータをあらかじめバッファに読み出しておく機能である。

書き込み

書き込みには、同期書き込み、非同期書き込み、遅延書き込みの3つがある。同期書き込みと非同期書き込みは、読み込みと同じでそれぞれデバイスの処理完了を待つ待たないの方式である。

遅延書き込みは、バッファを取得したあと、デバイスに書き込むデータをバッファに詰めるがその時点ではデバイスに対し書き込み要求を行わない。別のプロセスなどからバッファが再割り当てされようとしたときに、非同期にデバイスに書き込み要求を行う。

ブロックデバイスドライバ

ブロックデバイスドライバはブロックデバイスの操作を行うプログラムである。デバイスドライバはデバイス処理キーを持ち、キューにはバッファが追加される。典型的なブロックデバイスの処理は以下のようになっている。

  1. カーネル(主にブロックデバイスサブシステム)が、アクセス関数を実行する
  2. 渡されたバッファをデバイス処理キューに追加する
  3. デバイスのレジスタを操作し、デバイス処理キューの先頭のバッファの入出力処理を開始する
  4. デバイスの処理が完了するとデバイスから割り込み処理がかかる
  5. 割り込みハンドラはデバイス処理キューにバッファが残っていたら入出力処理を継続する

ファイルシステム

ファイルシステムとは

ファイルシステムとは、ブロックデバイスのデータを構造的に扱う仕組みのことである。ファイルシステムはファイルディレクトリという概念でブロックデバイスのデータを扱う。ディレクトリはファイルに名前を付けて管理するための概念で、その実体はファイルと同じものである。複数のユーザが使うことを考慮し、各ファイルやディレクトリにはアクセス権限を設定できる。

ファイルは、そのファイルを定義するinodeとファイルのデータからなっている。inodeはファイルサイズやファイルのアクセス権限、ブロックデバイスのブロック番号情報などを扱う。ファイル操作を行う際、カーネルはまず一番最初にinodeを探す。inodeもブロックデバイスに保存されている。

マウント

ブロックデバイスのファイルシステムを、システム上で利用可能にする仕組みをマウントと呼ぶ。逆にシステムから取り除く仕組みをアンマウントと呼ぶ。マウントを行うにはデバイスに対応するスペシャルファイルを作成し、mountシステムコールを発行してマウントポイントに対応付ける。マウントポイントとは、「この先はマウントしたブロックデバイスのファイルシステムである」ことを示すパスである。

アクセス権限

ログインしたユーザにはユーザIDが与えられる。そのユーザがファイルを作成すると、ファイルには作成したユーザーのIDと属するグループのIDが記録される。アクセス権限はパーミッションと呼ばれる11ビットの制御情報を使う。SUIDビットが立っていると、そのファイルを実行する時にユーザIDをファイル所有者のIDに一時的に変更する。もう一つのSGIDビットが立っている時も同じくグループIDを一時的に変更する。

ブロックデバイスの領域

ブロックデバイスは4つの領域に分けられる。0番目のブロックはシステム起動時に使用される。1番目のブロックはスーパーブロックと呼ばれ、ブロックデバイスの情報が含まれる。その後ろの領域にはinode領域が含まれる。さらにその後ろにはストレージ領域が含まれる。スーパーブロックはinodeやストレージの広さや空き領域を管理している。

パイプ

パイプは親子プロセス間で通信を行うための仕組みである。パイプはファイルシステムを活用して実現しており、ストレージ領域越しにデータをやり取りする。

/tmpなどに一時ファイルを作成し使用するプロセス間通信の手段もあるが、パイプの方がメリットが大きい。まずパイプは4096バイトしかブロックデバイスを使用しないため、それ以上の領域は必要ない。またバッファが効きやすく、他にも受け手のプロセスがすぐに読み込み処理を行うことができるメリットがある。

システムの起動

UNIX V6は次の流れで起動する。

  1. ROMに保存されているブートストラップローダプログラムが、ルートディスクのブロック番号0にあるブートストラッププログラムをメモリのアドレス0に読み込んで実行する。
  2. ブートストラッププログラムはルートディスクのファイルシステムから/unixや/rkunixといったカーネルプログラム本体をメモリのアドレス0に読み込んで実行する
  3. カーネルがシステムの初期化を行う

{ "name": "hareku", "job": "Software Engineer" }