Lecture Notes

4-3 割り込み処理

前回は、スレッドが I/O 待ちになったときに自動的にスレッドを切り替える機構を実装した。しかしいったん I/O 待ちになったスレッドが再び実行されるのは、別のスレッドが I/O 待ちになったときか、プログラムが明示的に ThreadYield() を呼んだときである。今回は、一定時間ごとに発生するタイマー割り込みの際にも、強制的にスレッド切り替えがおこなわれるようにスレッド・ライブラリを拡張する。これにより複数のスレッドが時分割処理 (time sharing) により擬似的に並列動作するようになる。

割り込みによるスレッド (およびプロセス) の切り替えは、時分割処理を実現するのに使われるだけではない。実時間システムでは、センサーなどからの割り込みに応じて特定のスレッドの実行を再開し、入力を読み取り、対応する処理をおこなうことは一般的である。またほとんどの高速 I/O 装置は I/O 処理の終了を割り込みによってプロセッサに通知する機能をもつ。プログラムの反応を高速にするためには、I/O 処理の終了を割り込みによって知ると同時に、その I/O 処理を要求したスレッドの実行を再開した方がよい。 I/O 装置によっては、終了を割り込みでプロセッサに通知せず、特定の I/O ポートの値を変えることで通知するものもある。そのような装置の場合、前回の課題で select() システムコールを使っておこなったように、定期的に I/O ポートの値を調べて終了を検出しなければならないので、プロセッサを占有しないかぎり、I/O 処理の終了に高速に反応することはできない。

割り込み

ほとんどのプロセッサは、ハードウェアからの信号 (割り込み) に反応して、プログラム・カウンタを含む全てのレジスタの値を退避し、別な機械語命令へジャンプする機能をもつ。これを割り込み (interrupt) 処理という。またジャンプした先の機械語命令列を割り込みルーチンという。割り込みルーチンの最後には特別な機械語命令(割り込みからのリターン命令)がおかれ、これが実行されると、先に退避したレジスタの値が復帰され、もとの処理の実行が再開される。

割り込み時にどの機械語命令にジャンプするかは、割り込みの種類に応じて、いくつかの中から選ぶことができる。多くのプロセッサでは、種類 i の割り込みが発生すると、プロセッサは割り込みベクタとよばれるジャンプ先の番地の配列を参照し、i 番目の要素の番地へジャンプする。何種類の割り込みを区別できるかは、プロセッサの種類による。

Race condition

割り込みによって、プログラムの実行途中でスレッドを切り替えることにすると、race condition (競合状態) に配慮してプログラムを書く必要がでてくる。例えば

int inc() {
    static int i = 0;
    i = i + 1;
    return i;
}

という関数をふたつのスレッドが呼び出したとする。当然、後から呼び出した方のスレッドは inc() の返り値として 2 を得るはずである。

しかしながらスレッドの切り替えのタイミングによっては、どちらのスレッドも 1 を返り値として得る可能性がある。例えば inc() 中で i の値 (= 0) を読み出した瞬間にスレッドが切り替わり、二つ目のスレッドが inc() を最後まで実行してしまったとする。そうすると最初のスレッドが i の値を増加させる前なので、二つ目のスレッドは inc() の返り値として 1 を得る。一方、最初のスレッドも読み出した i の値が 0 なので、inc() の返り値は 1 である。

複数のスレッドから呼ばれる可能性のある関数は、race condition を避けるため、特別な注意を払いながら実装される必要がある。同様に、複数のスレッドを使うプログラムとリンクされるライブラリについても、特別な注意を払って実装されたものを使う必要がある。そのようなライブラリは、しばしば MT-safe (Multi-thread safe) と呼ばれる。

Race condition を避ける典型的な方法は、プログラム中の race condition を引き起こす可能性のある部分 (critical section) の直前で排他制御をおこない、複数のスレッドが同時にその部分を実行しないようにする方法である。上の例では、

i = i + 1;

の式全体を critical section にし、あるスレッドがこの式の実行を始めたら、式の実行が完全に終了するまでは、他のスレッドがこの式の実行を始めないようにすればよい。後者のスレッドは、前者のスレッドが式の実行を終了するまで、実行を待たされることになる。

Critical section のもっとも単純な実現方法は、特別な機械語命令を使う方法である。例えば x86 プロセッサは、xchg という命令をもっている。この命令は、二つのオペランドの値を入れ替える命令である。ただし 1 命令で入れ替えをおこなうので、入れ替えの途中で割り込まれることはない。片方のオペランドの値だけ変わり、他方のオペランドの値はそのままということはありえない。

この命令を使うと次のようにして critical section を実現できる。

mutex = 0;        /* 初期化 */
    :
/* critical section 開始。 */
int value;
do {
    /* xchg 命令を使って mutex の値を value に代入し、
     * 同時に mutex に 1 を代入する。
     */
    value = _TestAndSet(&mutex);
} while (value != 0);
    :
cirtical section
    :
mutex = 0;
/* critical section 終了。 */

あるスレッドが critical section 内部を実行している間は、残りのスレッドは do-while ループを回りつづけ、critical section 内部に入れない。

Unix カーネル

(マルチプロセッサ対応でない) Unix は、システムコール実行中にけしてプロセスを切り替えない。切り替えは、システムコール終了間際におこなう。カーネル・プログラム全体が critical section になっていると考えればよい。このためカーネル・プログラムは race condition を考えなくてよいので、プログラムが簡単になっている。その一方、システムコールを実装している関数は、できるだけ早く終了するか、明示的にプロセスの切り替えをおこなって、プロセッサを長時間占有しないようにしなければならない。

Unix カーネル内の割り込みルーチンは、プロセスがシステムコールを実行している間、たとえ必要であってもプロセスの切り替えをおこなえない。このため、割り込みルーチンが特定のプロセスを動かしたいときは、そのプロセスの優先順位を上げ、実行中のシステムコールが終了したときに、そのプロセスが次に実行されるプロセスとして選ばれるようにする。

Unix のこの特徴は、多くの場合、それほど問題にならない。ほとんどの割り込みルーチンは、プロセスの切り替えを必要とするわけではないからである。例えば、キーボードを押すたびに割り込みが発生するが、割り込み処理ルーチンは、押されているキーが何であるかを調べ、後の read() システムコールに備えてカーネル内のバッファ領域に記録するだけである。プロセスの切り替えは特に必要ない。またディスクからの読み込み終了時にも割り込みが発生するが、割り込みルーチンはプロセスの切り替えをする必要はない。多くのディスク装置は、読み込まれたデータを直接カーネル内のバッファ領域に転送する (DMA: Direct Memory Access)。割り込みルーチンの仕事は、ディスクの読み込みを待ってブロックしていたプロセスの状態を実行可能状態に変更し、次にプロセスが切り替わるときにそのプロセスが選ばれるようにすることだけである。しかしながら Unix のこの特徴は、OS の実時間性能を悪化させる。割り込みが発生してから、関連するプロセスの実行が再開されるまでの時間が長いので、機器制御など厳密な実時間性能を必要とする処理には　Unix はあまり向かない。

対称型マルチプロセッサ (SMP) 対応の Unix カーネルの場合、ふたつのプロセッサによって並列に実行されているプロセスが、同時にシステムコールを実行する可能性がある。これは、システムコール実行中のプロセス切り替えを許したのと同じことになるので、カーネル・プログラム内部に適切に critical section を設定して、race condition によってカーネルが誤動作しないように気を配らなければならない。一般に critical section は並列処理のボトルネックになるので、カーネル・プログラム内部の critical section が狭ければ狭いほど、並列処理性能が向上する。しかし critical section を狭くしようとするあまり、本来 critical section に含めなければいけないコードが critical section の外に出てしまうと、race condition を引き起こして誤動作の原因になってしまう。 SMP 対応の Unix カーネルは、このような理由により設計・実装が非常に難しい。

Signal による割り込みのエミュレート

タイマー割り込みによってスレッドの切り替えをおこなうようにスレッド・ライブラリを拡張するには、まずライブラリがタイマー割り込みを受け取って、何らかの形で割り込み処理をおこなえるようにしなければならない。

Unix では、シグナル (signal) という機構を使うと、プログラム中で擬似的な割り込み処理をおこなうことができる。シグナル機構は、カーネル内で特定の事象 (イベント) が発生したときに、あらかじめ登録してある関数 (シグナルハンドラ) を呼び出して、プロセスにその事象の発生を通知する機構である。シグナルハンドラが呼び出される際に実行中だった関数は、いったん実行を中断されるが、シグナルハンドラ終了後に実行が再開される。シグナル機構が扱える事象には、タイマーの終了や、子プロセスの終了、メモリの参照違反など、さまざまなものがある。

シグナルは、ハードウェアによる割り込み機構をソフトウェアで忠実にエミュレートしたものである。プロセッサには、割り込みルーチン実行中に、他の割り込みによって再帰的に割り込まれないように、割り込みマスクが用意されている。割り込みマスクを変更することで、プロセッサが受け付け可能な割り込みの種類を細かく制御することができる。たとえばある割り込みルーチン実行中には、処理中の割り込みより優先度の高い割り込みだけを受け付け、優先度の低いものは受け付けないようにすることができる。

シグナル機構にも、割り込みマスクと同様の機能をもつ、シグナルマスクが用意してある。このシグナルマスクを変更すると、プロセスが受け付け可能なシグナルの種類を制御することができる。ちなみにシグナルハンドラの内部では、明示的にシグナルマスクを変更しない限り、同じ種類の別なシグナルによってそのシグナルハンドラの実行が割り込まれ、同じシグナルハンドラが再帰的に呼び出されることはない。もちろん異なる種類のシグナルについてはこの限りではない。

割り込み機構でも、シグナル機構でも、マスクの設定によっては、他の割り込みやシグナルをまったく受け付けないようにして、割り込みルーチンやシグナルハンドラが長時間プロセッサ（そのプロセスに割り当てられた CPU 時間) を占有してしまうことも可能である。一般に長時間の占有は、全体としての応答速度を悪化させるので、割り込みルーチンやシグナルハンドラの処理時間はできるだけ短くした方がよい。例えば Unix の場合、ハードウェア割り込みにともなって必要な処理をふたつにわけ、割り込みルーチンはハードウェアに関係したごく低レベルの処理だけをおこなう。これによって割り込みルーチンの処理時間を短くしている。残りの処理については、通常のシステムコールの処理の一部としておこなわれる。

スレッド・ライブラリの拡張

一定時間が経過するごとに、スレッドライブラリがシグナルを受け取れるようにするには、main() が ThreadMain() を呼ぶ直前に、シグナルハンドラを登録すればよい。

struct itimerval s, t;
t.it_interval.tv_sec = t.it_value.tv_sec = 0;           /* sec.       */
t.it_interval.tv_usec = t.it_value.tv_usec = 10000;     /* micro sec. */
signal(SIGALRM, PreemptiveScheduler);
setitimer(ITIMER_REAL, &t, &s);

上のようにすると、およそ 10 ミリ秒に 1 回、シグナルハンドラ PreemptiveScheduler() が呼ばれるようになる。

void PreemptiveScheduler(int x){
    :
}

一方、プログラムが終了してそれ以上、シグナルハンドラが呼び出されないようにするには、

signal(SIGALRM, SIG_IGN);

として、登録されたシグナルハンドラを削除すればよい。シグナルハンドラを削除するのは、ThreadYield() の中、main() スレッド以外のスレッドが全て終了して、main() に戻る直前である。

これまではシグナルを使用してこなかったので、スレッドを切り替える際、シグナルマスクを退避しなかった。シグナルマスクもレジスタ同様に退避させるためには次のようにする。まず Thread 構造体の中にシグナルマスクを退避する場所を用意する。

sigset_t  signal_mask;

そして、スレッド切り替えの際にシステムコール sigprocmask() を呼ぶようにする。

sigprocmask(SIG_SETMASK, &p->signal_mask, &q->signal_mask);

変数 p, q は、Thread 構造体を指すポインタである。 sigprocmask() は、現在のシグナルマスクを第 3 引数が指す sigset_t 構造体に退避し、第 2 引数が指す sigset_t 構造体の内容を新しいシグナルマスクとする。

sigprocmask() システムコールを呼ぶ位置には注意が必要である。まずこのシステムコールを呼ばなかればならない位置は、ThreadCreate() の中、_MakeThread() を呼ぶ直前である。現在のシグナルマスクを、新しく作ろうとしているスレッドの Thread 構造体の signal_mask に初期値としてコピーしておく必要がある。このとき、現在のシグナルマスクを別な値に変更する必要はないので、sigprocmask() の第 2 引数は NULL でよい。 NULL を第 2 引数にすると、シグナルマスクの値は変更されない。

次に sigprocmask() を呼ばなければならないのは、ThreadYield() の中、_ContextSwitch() を呼ぶ前後である。現在のシグナルマスクを退避し、実行が再開されるスレッド用のシグナルマスクを有効にしなければならない。

シグナルが発生すると、OS は暗黙のうちにシグナルマスクを変更する。シグナルハンドラの実行中に、再びシグナルが発生して同じシグナルハンドラが再帰的に実行されるのを防ぐためである。変更されたシグナルマスクは、シグナルハンドラが終了するまで元に戻されないので、シグナルハンドラ PreemptiveScheduler() の中から ThreadYield() 経由で _ContextSwitch() が呼ばれたときには、sigprocmask() を呼んでシグナルマスクを変更し、再びシグナルが発生するようにしなければならない。

なお、もし _ContextSwitch() の直前に sigprocmask() を呼んだ場合、sigprocmask() が終了した後 _ContextSwitch() を呼ぶ直前に、シグナルが通知され、シグナルハンドラが呼ばれる可能性がある。 _ContextSwitch() の直前に sigprocmask() を呼ぶ場合は、そのような極端なタイミングでシグナルが通知されても、全体として正しくスレッドライブラリが動作することを確認するよう注意しなければならない。

ライブラリの critical section 化

スレッド・ライブラリの中でも、スレッドの切り替えをおこなう瞬間や、Thread 構造体のリストをつなぎかえている間は、critical section にしなければならない。もしそのようなときにシグナルが通知され、PreemptiveScheduler() が呼び出されると、多くの場合、ライブラリが誤動作するだろう。例えば構造体のリストのつなぎかえの途中では、リンクの値が一時的に正しくない値になることがありうる。このような状態で、次に動かすスレッドを探すために Thread 構造体のリストを探索すると、メモリの参照違反 (segmentation fault) などを引き起こしてしまうだろう。

Critical section を実行中には、PreemptiveScheduler() が呼び出されても、スレッドの切り替えをおこなわないようにするため、まず critical section を実行中か否かを示す大域変数 kernelLock を導入する。この変数は普段は FALSE であるが、各ライブラリ関数の適切な場所に kernelLock の値を変更する行を挿入して、critical section の実行中だけ TRUE となるようにする。

安全性を優先するのなら、スレッドライブラリの全ての関数を critical section にしてしまえばよい。関数の先頭で kernelLock を TRUE にし、return の直前で FALSE にすれば、ライブラリの関数の実行中に不用意にスレッドが切り替わって、ライブラリの動作がおかしくなる事態を避けることができる。必要最小限の領域だけを critical section にするのなら、Thread 構造体のつなぎかえをやっている領域などを限定的に critical section にすればよい。ただし後者の方法では、本来 critical section でなければならない領域を誤って critical section に入れ忘れ、ライブラリの誤動作を引き起こす可能性があるので注意しなければならない。

さて critical section を設定したら、PreemptiveScheduler() を次のようにする。

void PreemptiveScheduler(int x)
{
    if (kernelLock == FALSE)
        ThreadYield();
    else
        needContextSwitch = TRUE;
}

このシグナルハンドラは kernelLock の値を調べて、FALSE ならば ThreadYield() を呼び出してスレッドを強制的に切り替えるが、そうでなければ大域変数 needContextSwitch を TRUE にして終了する。

大域変数 needContextSwitch は通常 FALSE であるが、critical section の実行中に PreemptiveScheduler() が呼ばれたときに TRUE に変わり、スレッドの切り替えが必要であることを示す。スレッド・ライブラリの各関数は critical section から抜けたときに、この変数の値を調べ、TRUE ならば ThreadYield() を呼んでスレッドを切り替えなければならない。もちろん ThreadYield() を呼んだあとは needContextSwitch の値を FALSE に戻して二重に ThreadYield() が呼ばれないようにしなければならない。 (ThreadYield() の中で必ず needContextSwitch の値を FALSE にするようにすればよい。)

以上のような方法は、Unix におけるシステムコール実行中のプロセス切り替えの扱いを模倣したものである。 Unix では、システムコール実行中にプロセス切り替えをおこなわない。割り込みルーチンはプロセスの優先順位だけを変更し、実行中のシステムコールが終了した後にプロセスが切り替わるようにしている。

課題3

thread.c を拡張して、タイマー割り込みによる強制的なスレッド切替えの機能を実現したスレッドライブラリ thread3.c を作れ。

完成後、test3.c を使って、ライブラリが正しく動くか確かめよ。コンパイルするには次のようにすればよい。

% gcc -g -o test3 test3.c thread.c csw-i386.S

目次へ戻る

Email: chiba@is.tsukuba.ac.jp