ここ何ヶ月か自作 OS (と Rust) のお勉強として xv6 を Rust に移行していました (xv6-rust)。移行中、この OS を SMP (Symmetric Multiprocessing) 対応させるときに、カーネルの実装でいくつか悩む点がありました。

  • カーネルモード実行中のプロセスでハードウェア割込を受けていいのか
  • カーネルモード実行中のプロセスでプリエンプションを許可していいのか
  • (混乱したのでカーネルモードでは割込を一律禁止したが、その場合) read のようなブロックするシステムコールをどのように実装すればいいのか

xv6 自体も SMP 対応されているので盲目的にこの実装に従ってもよかったのですが、次に OS を自作するときに迷わないようにどういった選択肢がありうるのか、どういった方針を取るべきかについての現時点の理解を整理してみました。

基本的な方針

カーネル空間での同期制御をどのように行うべきかは、個人的な考えですが、以下の 3 点に依存すると考えています。

  • (1) プロセッサ数
  • (2) プロセススケジューリングがプリエンティブか否か
  • (3) プリエンティブカーネルか否か

(1) プロセッサ数というのはそのままで、OS がシングルプロセッサ上で動作するのか、あるいはマルチプロセッサ上で動作するのかということです。

(2) は OS がプリエンプティブスケジューリングをサポートするか、ということです。プリエンプティブスケジューリングをサポートしない場合、プロセスの切り替えは実行中のプロセスが自発的に CPU を手放す (yield) か、プロセスの実行が終了したときにのみ発生します。一方プリエンプティブスケジューリングをサポートする場合は、例えばタイマー割込時だったりシステムコールからユーザ空間に戻るといったときに別のプロセスへ切り替わる可能性があります。

プリエンプティブな方がもちろん考えることは増えるのですが、自作 OS でもプリエンプティブスケジューリングのサポートは一般的だと思うので、以降はプリエンプティブスケジューリングを行う OS を想定しようと思います。

(3) の「プリエンプティブカーネル」とは端的には「カーネル空間におけるプリエンプションを許容する」 カーネルです。これについて Operating System Concepts 8th Edition (旧版だからか Amazon で見つからない?) という手元の本では以下のように説明されています (拙訳)。

  • プリエンプティブカーネル
    • カーネルモード実行中のプリエンプションを許可する
    • リアルタイムプログラミングに適切
  • ノンプリエンプティブカーネル
    • カーネルモード実行中にプリエンプションを許可しない
    • カーネルモードを抜ける、ブロッキング、あるいは自発的に CPU を手放すまで処理を続ける

(なおこの定義においてカーネルモードでの (クリティカルセクション以外での) ハードウェア割込の許可についてはどうなっているのか把握できていません。ただプリエンプションの一因はタイマーなのでプリエンプティブカーネルなら割込許可、ノンプリエンプティブカーネルなら割込不可だと想定するのが自然なのかなと考えています)

プリエンプティブカーネルの方が性能 (e.g. 応答性) は良くなり、一方で実装は複雑になります。

ここからはこの 3 点の組み合わせでよくありそうなものについて、カーネル空間での適切な同期制御方法を整理してみます。OS の SMP 対応を行う場合、基本的にはこれから記述する通りの順番で行うのがセオリーになるかと思います。

シングルプロセッサの場合

シングルプロセッサ環境で動作する OS についてはクリティカルセクションでプリエンプションが禁止さえされていれば問題になりません。

例えば Linux v2.6.9 では spinlock という同期制御の仕組みがありますが、その実装はマルチプロセッサか否かに依存します。シングルプロセッサ環境ではロックの取得、解放が実際にはカーネルプリエンプションの禁止、許可のみを行うようにされています。

// include/linux/spinlock.h

#ifdef CONFIG_SMP

// ...

#else

// ...

// CONFIG_SMP 未定義時のみ存在する nops な関数
// SMP 環境下では include/asm-<arch>/spinlock.h で提供されているはず
#define spin_lock_init(lock)	do { (void)(lock); } while(0)
#define _raw_spin_lock(lock)	do { (void)(lock); } while(0)
#define spin_is_locked(lock)	((void)(lock), 0)
#define _raw_spin_trylock(lock)	(((void)(lock), 1))
#define spin_unlock_wait(lock)	(void)(lock);
#define _raw_spin_unlock(lock) do { (void)(lock); } while(0)

// ...

// ロック取得、解放用関数
// シングルプロセッサ上では spin せず preempt の禁止、許可のみ行っている
#define _spin_lock(lock)	\
do { \
	preempt_disable(); \
	_raw_spin_lock(lock); \
} while(0)

#define _spin_unlock(lock) \
do { \
	_raw_spin_unlock(lock); \
	preempt_enable(); \
} while (0)

// ローカル CPU 割込も禁止する
// 割込ハンドラでも使用するデータ構造の場合こちらを使用しなければならない
// ref. http://www.cs.columbia.edu/~jae/4118/L12-interrupt-spinlock.html
#define _spin_lock_irqsave(lock, flags) \
do {	\
	local_irq_save(flags); \
	preempt_disable(); \
	_raw_spin_lock(lock); \
} while (0)

#define _spin_unlock_irqrestore(lock, flags) \
do { \
	_raw_spin_unlock(lock); \
	local_irq_restore(flags); \
	preempt_enable(); \
} while (0)

// ...

#endif

シングルプロセッサ環境で (スピンしてロック待ちするような) spin lock を使用するのは意味がないばかりでなくデッドロックの原因にもなり得るので危険、という記述をいくつか見ました (例えば ここ)。しかし具体的にどう危険なのか把握できていません。Linux の spinlock のように適切にプリエンプションと割込を禁止していればデッドロックは防止できるように感じます (spinlock on non-preemptive linux kernels の質問に対する回答でもその認識)。

またより実装を単純にするなら (x86 想定で) システムコール含め割込ハンドラを interrupt gate にしてカーネルプリエンプションを一律禁止してしまうというのもありだと思います。というか次に一から自作 OS を始めるならまずはそうします。

マルチプロセッサ、ノンプリエンプティブカーネルの場合

マルチプロセッサ環境で動作するノンプリエンプティブカーネルとして自分が知っている例は Linux v1.3.99 と JOS (MIT 6.828 授業で使用される OS 教材。元は xv6) なのですが、どちらも giant lock (big kernel lock) を使用しています。giant lock とはいわば「カーネル全体用のロック」であり、カーネルモード実行中のプロセッサが常に最大 1 つとなることを保証します。これにより (シングルプロセッサで動作する) 既存のカーネルの実装をあまり変えずに SMP 対応が可能、カーネルの実装をシンプルに保てるといったメリットがあります。

giant lock を使わなくても (このあと見る) プリエンプティブカーネルの場合と同様に spin lock で適切に同期制御ができると思うのですが、そこまでするならプリエンプティブカーネルにしてしまうのかなと思います。Linux がそうであったように giant lock を採用するモチベーションとしては SMP 対応の第一歩目として着手しやすいというのが大きそうです。

マルチプロセッサ、プリエンプティブカーネルの場合

giant lock はお手軽に SMP 対応するにはよいのですが、同時にカーネル空間に入れるプロセッサが 1 つに限定されてしまうので性能面に難があります。

プリエンプティブカーネルの場合、giant lock を撤廃し、クリティカルセクションを find-grained なロック (データ構造や処理の単位でロックを取得する) で守ることで、複数のプロセッサが同時にカーネルモードを実行することを許可しつつ適切に同期制御を行うことができます。自分の知識の範囲内では xv6 や Linux v2.6 以降は find-grained locking を採用しプリエンプティブカーネルとして実装されています。実装の詳細は複雑ですしそもそも Linux v2.6 については完全に理解もできてはいませんが、共通して見られる実装として以下の 2 点を挙げておきます。

  • spin lock を使用する (ref. Interrupts, Spin Locks, and Preemption)
    • ロック取得中はプリエンプションを禁止する
    • システムコール、ハードウェア割込で共通に使用するロックではハードウェア割込も禁止する
      • Linux v2.6 では spin_lock() と spin_lock_irqsave() を使い分ける
      • xv6 では一律ロック取得時に cli 命令を実行する
  • システムコール用の割込ハンドラを trap gate として設定する
    • ハンドラ処理開始時に EFLAGS の FL_IF ビットをそのままにする
      • なので例えばタイマー割込からのプリエンプションが発生し得る

「遅い」システムコールの実装

自作 OS を SMP 対応する中で一番混乱したのは、read のようなブロックする可能性のあるシステムコール (いわゆる「遅い」システムコール?、この名称は 詳解UNIXプログラミング 第3版 の 10.5 より) をどう実装すればいいのかということでした。

例えば UNIX 系の OS ではパイプからのデータ読み取りのために read を実行するプロセスは、writer 側のプロセスがデータを書き込まない限り無制限にブロックされます。処理を進めるためには reader 側のプロセスが何らかの仕組みで自発的に CPU を手放す必要があり、また writer がデータを書き込んだことを認識してスケジューリングを再度可能にしてもらう必要があります。

このように「遅い」システムコールを実装するには CPU を手放すプロセスが何らかの条件 (e.g. パイプにデータが用意される) が満たされるまで待つための仕組み、別のプロセス (e.g. パイプの writer) や割込 (e.g. キーボード割込ハンドラ) との意思疎通のための同期機構が必要になります。

xv6 では sleep と wakeup という関数でそのような同期制御を行います。

// Atomically release lock and sleep on chan.
// Reacquires lock when awakened.
void sleep(void *chan, struct spinlock *lk);

// Wake up all processes sleeping on chan.
void wakeup(void *chan);

xv6 では各プロセス (proc 構造体) は chan というメンバを持ち、sleep 時に任意のデータを設定します。その後プロセスのステータスを実行中からスリープ中へと変更してスケジューリングします。ここでは sleep に渡す lk が同期制御用の spin lock です。関数シグネチャからはわかりにくいですが、同一 chan については sleep, wakeup を実行する前に同一 lk を取得するというのが暗黙の了解になっています。wakeup ではプロセステーブルから chan が設定されているものを探してステータスを実行可能に変更します。もし sleep 後のスケジューリングで実行可能なプロセスが無い場合 (e.g. キーボード割込待ち)、xv6 では可能なプロセスが出現するまでスケジューラを回し続けるようです。

Linux v1.3.99 では wait_queue という仕組みが利用されます。xv6 では wakeup するにはプロセステーブル全体を舐める必要がありましたが、こちらではプロセスが wait_queue 上に自身を登録して wakeup 時にはそこから探せばいいようになっています。xv6 の仕組みではプロセス数に応じて wakeup に時間がかかりますし、またプロセステーブルのロックが競合しやすくなるので、その点で wait_queue の方が性能のよい仕組みだと言えます。なお Linux v1.3.99 のスケジューリングでは実行可能なプロセスが存在しない場合、プロセッサ毎に用意した idle 用のプロセスを実行するようです。

参考