執筆者 : 小田 逸郎
※ 「OS徒然草」連載記事一覧はこちら
マルチプロセス(続)
マルチプロセッサ(断り書き)
最近では、すっかりマルチプロセッサ(MP)*1が普通になってしまいました。ラズパイですら、MPですもんね。前回のスケジューラの話題のところで、どのCPUで実行するかの選択も必要と言った感じで、CPUがひとつだけでないことをバラしてしまいました。そのため、次はMPの話題が出るのではないかと予想される方もいらっしゃるかもしれません。そのとおり、MPの話題ですが、予想した方向ではないかもしれません。
MPが普及してきたのは、2000年を超えてからのことだと思います。ハード屋さんとしては、CPU単体の性能向上が頭打ちになってしまったため、新しい売りとして、数を増やす方向に舵を切ったのでしょう。筆者が、最も脂の乗っていた90年代前半くらいは、まだユニプロセッサ(UP)が普通でした。その頃は、時間の掛かる処理があっても、待っていれば、CPUが速くなっていってくれて、何もせずに解決していたので楽な時代でした*2。OSの方はと言えば、筆者が開発していたOSのベースとなっていた、UNIX System V では Release 4.2MP(1993年)でMP対応が完成したという状況で、それまでは、UPを前提としていました*3。
当時(90年代)、HPC(スパコン)の世界では、SMP構成で、CPU数を多く搭載するタイプもありましたが、筆者が関わっていたのは、ベクトル演算機構を搭載したプロセッサエレメント(PE)を多数、クロスバーネットワークという高速ネットワークで接続するという形態でした。PEというのは、CPUとベクトル演算器があり、それらがメモリを共有する構成で、これ自体をひとつのスパコンと考えてよいです。各PEはメモリを共有するわけではないので、分散メモリ型の構成となります。PEは、UPだったため、筆者は、MPにまつわる面倒事を避けられていました。
と、思わず、MPが面倒という本音が漏れてしまいましたが、実際のところ、とても面倒なものでして、Linuxのコード肥大化の大きな要因のひとつであることは間違いありません。元々、OSの機能としては、UPでも一応完成していて、そこから苦労してMP対応してきたという歴史があります。今は、MPが当たり前なので、今OSを設計するのであれば、初めからMPを前提にするのが正しいと考えますが、それでも、UPで出来る範囲をきちんと把握した上で、設計した方が良いものができると思います。という訳で、本ブログでは、まずは、UPで行けるとことまで行く予定です。その上で、MP対応として、何が必要なのか、独立した話題にしたいと思っていますが、多分、かなり先の話になります。初回にコンピュータの構成図(CPUがひとつの図)を示しましたが、当分の間、そのままということになります。
競合状態
マルチプロセスが可能となると、複数のプロセスが協調して何らかの処理を行うことを考えたくなります。複数のプロセスが共通のリソースを扱おうとすると、いろいろと考慮することが出てきます。ここでは、２つのプロセスがひとつのファイルを更新するケースを考えてみましょう。ファイルの内容は何らかのカウント(数字)で、それぞれのプロセスが何らかの処理を行う度にインクリメントすることとします。２つのプロセスで処理した総数を示すファイルと考えることもできます。ファイルの内容を更新する処理を少し分解すると以下のようになります。
更新処理:
- (1)ファイルの内容(カウント)を読む
- (2)読んだカウントをインクリメントする
- (3)インクリメントしたカウントをファイルに書く
各々のプロセスが単純にこの処理を行えば良いというのは、少々能天気すぎます。仮にファイル内の値が、「3」だとして、２つのプロセスがそれぞれ更新処理を行ったとすると、期待するファイル内の値は、「5」となります。ところが、２つのプロセスでの処理が、以下のような時系列で行われたケースを考えてみましょう。
期待した値「5」よりも1少ない値「4」になってしまっています。CPUはひとつなので、プロセスAとプロセスBが同時に実行されることはありませんが、プロセスAが(1)を実行した後、タイムスライス切れでプロセスBに実行権が移って、上記の時系列の処理が実行されることはあり得ます。
もう少しミクロな例も見てみましょう。カウンタを２つのプロセスの共有メモリに置いたケースを考えてみます。更新処理は以下のようになります。
/* int count; これは、共有メモリ上の変数とする。*/
count++;
1ステップなのでOK、ということにはなりません。実際にCPUで実行する命令は複数となります。RISC-Vの命令を例に取ると、以下のようになります。
// a0 に countのアドレスをストア(数命令) lw a1, 0(a0) // ロード: アドレスa0の内容をa1にロード。 (a1 = *a0) addiw a0, a1, 1 // ストア: アドレスa0にa1の値に1足した値をストア。 (*a0 = a1 + 1)
プロセスAとプロセスBが以下のような時系列で処理が実行されると、やはりまずいことになります。
こんな絶妙なタイミングでプロセス切り替えが起きるんかい、と思った方もいらっしゃるかと思います。長年の経験から言わせて貰うと、論理的に起きうる可能性のあるものは、大体実際に起きます*4。
このように処理が競合する状態のことを競合状態と言います(なんか、そのまんまですが)。競合が起きてはまずい処理の区間(この例だと、更新処理と言った部分)をクリティカルセクションと言います。
話は飛びますが、筆者は昔、とある大学の工学部情報工学科で非常勤講師として、OS講座というのを教えたことがあります*5。当時は、情報工学科というのがまだ珍しく、教えられる先生も少なかったことから、コンピュータ関係の企業に講師を依頼していたようです。筆者以外にも他の企業から他の講座を受け持っておられた方が来ていました。なぜか、講義の最終日は、実際のOS開発の現場を見ようという建前で会社見学になっていました。企業側としては、採用活動にもなりますし、大学側としても学生が就職先のイメージを持ちやすくなりますので、win-winの関係だったのかと思います。筆者としては、大学の出身としては、まったく専門外で修士すら持っていない*6にも関わらず、大学の非常勤講師まで体験できて、良い経験となりましたが、これもOS屋をやっていたおかげというわけです。
OS講座では、タネンバウム先生の「Modern Operating Systems」*7という本を教材にしました。情報工学科というからには、きちんとしたOSの知識を身に付けて欲しいということと、筆者自身も大学で教育を受けたわけではなく、OS開発の現場でたたき上げられた人間なので、本格的な教科書を読んでみたいということで、自身も勉強しながら、教材を作って講義したのです。内容は2部構成になっていて、第1部がひとつのマシン上で動作する普通のOSの話で、第2部が分散OSの話でした。第1部の範囲を教材にしたのですが、その冒頭がマルチプロセスによる競合状態の話から始まっていて、え、その話題から始まるの、と思ったものです。まあ、重要な話題であることは確かです。話の流れでは、OSとして、マルチプロセスでの競合を抑止するための機能を提供しなければならないということになっていました。
という訳で、本線に戻りますが、競合状態を避けるためには、OSの力を借りることになります。OSとしては、単純には、ロック機能をシステムコールとして用意することが考えられます。ロックというのは、ひとつのプロセスしか獲得することができず、あるプロセスがロックを持っている間に別のプロセスがロックを獲得しようとすると待ち状態になります。ロックが解放されれば、ロック待ちのプロセス(のうちのひとつ)がロックを獲得し、待ち状態が解除されます。クリティカルセクションをロックで保護することにより、排他制御を行います。カウンタのプログラム例では以下のようにします。
/* int count; これは、共有メモリ上の変数とする。*/
lock(lock-identifier);
count++;
unlock(lock-identifier);
これで、ロードとストアの間でプロセス切り替えが起きても大丈夫です。以下のような時系列で処理されることになります。
プロセスBからすると、やっと順番が回ってきたと思ったら、すぐに待ち状態になって悲しいですが、カウンタの整合性は保たれました。
OSの競合状態
プロセスの排他制御は、OSが行うので良いとして、OS自身はそうした競合状態が起きる心配はないのでしょうか。以前、OSは割り込みドリブンで、割り込み種別に応じたスレッドが実行されると説明しました。OS実行中は、割り込みを禁止しておけば、複数のOSスレッドの処理がかぶることはないので、競合は発生しません。めでたし、めでたし。と、行かないのが世の常です。実際のところ、筆者が関わっていたOSも当初はそうなっていて、何の心配もありませんでした。TSSで人間の相手をする程度では、大した応答性能はいらなかったということでしょう。ところが、いろいろなデバイスの接続をサポートするにつれ、デバイスからの割り込みに素早く応答する必要が出てきました。例えば、何らかのセンサからデバイスがデータを受け取ったとして、デバイスのバッファから素早くデータをメモリにコピーして、デバイスのバッファを空けておかないと、後続のデータを取りこぼしてしまう、というようなシチュエーションが考えられます。そのため、OSの実行中も割り込み可能とするようになりました。そうすると、OSのスレッド間で競合状態が発生するようになります。
例えば、システムコール処理とデバイスの割り込み処理で、リンクリストを共有していて、割り込み処理ではリストに繋ぎ、システムコール処理ではリストから外して処理するケースを考えると、リストに繋いだり外したりする部分は、クリティカルセクションとなります*8。競合状態をどうやって防ぐかですが、クリティカルセクション実行中は割り込みを禁止しておく、という手段で解決できます。OSの実行時、ずっと割り込みを禁止しておくのではなく、クリティカルセクションだけ、割り込みを禁止しようということですね。OSのコードからクリティカルセクションを洗い出して、その前後で割り込み禁止と解除を入れて回るというのを苦労して行った覚えがあります。OSが一段階複雑になった瞬間でした。
基本的に割り込み処理は短いことが想定されるので、割り込みを開けるのは、システムコール処理のみとすることが考えられます。割り込み処理終了後は、元のスレッドに戻るのが基本です(上図の１回目の割り込みの部分)。しかし、割り込みを契機として、別のスレッド(すなわち、別プロセスのシステムコールコンテキスト)に切り替えることも考えられます(上図の２回目の割り込みの部分)。センサから受け取ったデータを直ちにあるプロセスが処理する必要があるというようなケースに対応するためで、このような要件をリアルタイム要件と言います。リアルタイムOSと名乗るための条件のひとつとなります。通常では、プロセスの切り替えは、システムコール処理で待ち状態に移行するところ、すなわち、決まった箇所で行われますが、それが、システムコール処理の任意の地点(ただし、クリティカルセクションを除く)で、切り替えが行われるようになるため、考慮する事項が増えて行きます。ここでは細かいことには触れませんが、こうして、OSが複雑化していくのです。
さて、割り込み処理は短いと想定しましたが、本当にそうなのでしょうか。確かにデバイスドライバの処理だけ取れば短いと言えますが、その後、OSが処理しないといけない部分は必ずしも短いとは言えなくなってきました。典型的な例としては、ネットワークデバイスの受信処理が挙げられます。OSが処理しないといけない部分というのは、パケットの宛先を見て、受信プロセスの特定を行ったりする部分で、これは短いとは言えないです。そのため、デバイスドライバの処理部分は割り込み禁止で動作させるが、その後のOS処理部分は、割り込み可能で動作させるようになって来ました。OS処理部分は、割り込み可能といっても、割り込まれて、同じ処理部分が実行されては面倒なことになるので、それなりに工夫が必要です。実装方法はいろいろ考えられますが、Linuxカーネルでは、softirqという仕組みを導入していますね。こうして、またOSが複雑化しました。
筆者がOS屋を始めたころは、OSは割り込み禁止で動いていたという話をしましたが、ネットワーク処理はどうなっていたのよ、と思ったかもしれません。今でこそ、TCP/IPは当たり前のように使用されていますが、当時は、BSD系のUNIXに実装されたばかりで、筆者がやっていた System V系のUNIXにはまだ実装されていなくて、別のグループの人たちが、一生懸命移植していました。出来た後もしばらくは、オプション製品として提供されていました。そんな状況でまだネットワークは一般的じゃなかったんですよね。
閑話休題。
マルチスレッド
マルチプロセスの話をしてきましたが、ひとつのプロセスをマルチスレッドにした場合はどうなるでしょう。第2回にマルチスレッドプログラムの例を出しましたが、スレッドの切り替えが行われるポイントが決まっていて、任意の地点での切り替えが行われることはないので、競合状態の心配はありません。
POSIXスレッド(pthread)を使用した場合はどうでしょうか。MPが当たり前の現在では、OSがスレッドレベルでCPUのスケジューリングを行う機能(OSレベルスレッド)をサポートしているので、pthreadはそれを使用して実装されているはずです(それが一番楽ですし)。UPしかないアーキテクチャでは、OSレベルスレッドはサポートされていない(意味がないので)ため、ユーザレベルでpthreadを実装する必要があります(ユーザレベルスレッド)。ユーザレベルスレッドの場合、あるスレッドが待ちになる処理(例えば、I/O処理)を行うと、プロセス全体が待ちになってしまうという課題がありそうですが、ユーザレベルスレッドの実装では、I/O処理を非同期処理に置き換えるなどして、別スレッドが動作できるよう工夫されています。自ら非同期I/Oを使ってプログラミングするとかマルチプロセスにするとかもできそうですが、pthreadという標準的なAPIを使用して、あまり苦労せずプログラミングできるというところで、pthread(ユーザレベルスレッド)の存在価値がありそうです。
pthreadと言えば、実は筆者は、pthreadをユーザレベルで実装したことがあります。筆者が関わっていたスパコンはUPだったという話をしましたが、そのため、ユーザレベルで実装する必要がありました。スパコンの商談は、数10億円の規模になることもあり、商談相手の要求事項に「pthreadライブラリが使用できること」とあれば、否応なしにサポートすることになる訳です。
閑話休題。
(ユーザレベルで実装した)pthread使用時もスレッドの切り替えポイントは、予め決められているので、競合状態は発生しません*9
さて、pthreadの話はこれくらいにしますが、実は、いにしえのUNIXから、マルチスレッドというものが存在していました。それはシグナル処理です。
シグナルを使った簡単なプログラムを示します。
/* SPDX-License-Identifier: BSD-2-Clause
* Copyright(c) 2024 Itsuro Oda
*/
#include <stdio.h>
#include <signal.h>
#include <unistd.h>
volatile static int done = 0;
static void alarm_handler(int not_used)
{
done = 1;
}
int main(void)
{
unsigned int count = 0;
if (signal(SIGALRM, alarm_handler) == SIG_ERR) {
perror("signal");
return 1;
}
(void)alarm(1U);
while (!done) {
count++;
}
printf("count: %u\n", count);
return 0;
}
シグナル処理というのは、OSの割り込み処理を模したもので、上のプログラム例では、alarm_handlerが割り込みハンドラに当たり、main関数のwhileループ実行中のどこかのポイントで割り込んで実行されることになります。上のプログラムでは、mainとalarm_handlerでdone変数のアクセスが競合する可能性があります。上のプログラムの意図は、1秒間にどのくらいカウントアップできるか調べることなので、競合が起きたところで、カウントが高々１違ってくるだけなので、競合は無視しています。もし、競合を防ぐのであれば、クリティカルセクションの前後で、シグナルのブロックとブロック解除を行えばよいです。OSの競合抑止を割り込み禁止で行ったのと同様の理屈になります。
上のプログラムでは原始的なsignalシステムコールを使用しています。alarm_handlerのスタックは、割り込んだときのスタックをそのまま使用しますが、独立したスタックを使用することもできます。シグナルに関する補足説明をgithubにしてありますので、ご参照ください。
あとがき
OSの役割の中で、CPUに命令列を流し込むという機能は、最もプリミティブな部分かと思います。初回(1)から今回(5)まで、その部分を意識した話題を取り上げて来たつもりです(途中、マルチプロセスの配置問題をすっきりさせるため、仮想空間の話題を挟みましたが)。結構低レイヤの話が続いたので、次回からはもう少し上位レイヤの話をするつもりです。ではまた次回。
*1:ハードウェアの観点では、プロセッサ、コア、ハイパースレッディング等の区別がありますが、本稿では、OSから論理的にCPUとして認識するものをプロセッサと呼びます。また、CPUがメモリを共有するSMP(Symmetric MP)構成を前提とします。
*2:CPUの数を増やす方は、性能をスケールさせるのは一筋縄ではいきません。ソフトウェアの方にかなりの工夫が必要になります。
*3:4.2MPの前に4.0MPという限定対応版もあるにはありましたが。
*4:恣意的には簡単なプログラムで再現できます。githubの補足資料を参照ください。
*5:1992年くらいに3年生の後期の授業として。
*6:筆者は、理学部数学科卒業。
*7:Modern Operating Systems by Andrew Tanenbaum。現在も出ていますが、筆者が使ったのは、当時のものなので、内容も違っているかもしれませんし、ISBN等は割愛します。どうも初版が1992年とのことなので、出たばかりのものを使ったようです。
*9:実装にもよりますが、まともな実装であれば、そうなります。
