OSのおはなし #1 並列処理

なにがおもしろい？

時代とともに効率化されていくOS。そこには色々な工夫が組み込まれていた。アプリ開発がメインの私は今まであまりOS周りについて知らなかったので今回学んだことをまとめてみました。広く浅く解説しているので深く知りたい方は詳しく調べてみてください。

OSとは？

OSとはWindowsやMacなどのオペレーションシステムの事ですが、その目的はハードウェア（メモリやCPUなど）をアプリケーションが効率的かつ信用して使えるように割り当てることにあります。

OSの進化

初期のコンピューターはバッチシステムと呼ばれ計算してほしいものの一覧を作成してから一気に計算させていました。次の世代のMulti-Programmedバッチシステムでは「読み込み」「計算」「出力」を上手くスケジュールすることで複数のジョブを高速に並列処理することが可能になりました。そしてTime Sharingシステムでは複数のユーザーが同時に1つのコンピューターを使うことができるようになり、その後ついに我々が知るパーソナルコンピューターが生まれたのです。今ではクラスターコンピューティングなど、複数台のコンピューターが協力して1つ、または複数の計算を高速で行うようになりました。

こうしてOSはより効率的にそして複雑になっていったのですが、今回はOSがどのように効率化を行なっているかについて書いていきます。（本記事はカリフォルニア大学の講義「Principles of Computer Systems Design」の要約になります）

プロセス

プロセスはWebブラウザなどの1つ1つのプログラムであり、それぞれのプロセスが実行または並列処理に必要な情報、コンテキスト（プロセスID、レジスタ、現在使っているファイルの一覧）を持ち、これらの情報はプロセスコントロールブロックによって管理され、どの順番でプロセスをCPUに当て処理を行うかを決める。

プロセスは作られるとまず処理待ちのReadyリストに入る。そこから順番がまわってくるとRunning(実行中)になり、ファイル読み込みなどでI/O待ちになると時間がかかるため他のプロセスに実行権を譲り、読み込みが終わり次第Readyリストに戻る。実行中にInterrupt(キーボード操作やOSの重要な処理)が入るとそちらに実行権を譲る。最終的に全ての処理を終えたプロセスはExitする。

マルチプロセスと呼ばれるこのI/O待ち中に他のプロセスを実行する手法は処理を高速化し、さらに複数のオペレーションを同時に行うことができるようになる。(Youtubeで音楽を聴きながらレポートを書くなど)

しかし、プロセスが多ければ多いほど良いというわけではなく、I/O待ちが短い場合、プロセスの数が一定数を越しても処理速度(CPUの利用率)は変わらなくなってくる。

スレッド

CPUが実行するプロセスを入れ替えることをコンテキストスイッチといい、レジスタなどの入れ替えを行うが、この作業はかなりの時間がかかる。そこで1つのプロセス内でも複数の処理を同時におこなえる（動画を読み込みながら再生）ようにしたのがスレッドである。スレッドはコードやメモリを共有しておりコンテキストスイッチで入れ替える必要がないので高速である。

スレッドの種類として、カーネルレベルスレッドとユーザーレベルスレッドがある。カーネルレベルスレッドとはOSによって管理されているスレッドでユーザーレベルスレッドより遅いが1つのスレッドがI/O待ち中、同じプロセス内の他のスレッドが処理される。ユーザーレベルスレッドは高速でユーザーにより処理の順番をスケジュールすることが可能であるがOSにとっては単一のプロセスであるため、1つのスレッドがI/O待ちになるとプロセス全体が保留となる。

そこで考えられたのが「Many-to-Many」であり、複数のカーネルレベルスレッドが多数のユーザーレベルスレッドを交代で処理することである。これで無駄なく並列処理できるようになる。

並列処理による問題

並列処理はそれぞれのプロセス、またはスレッドの処理順番が決まっていないため、安易に行うと処理が正しく行われない場合がある。

例えば上のAとBの処理が同時に行われるとする。実行前のxの値が1だとするとAとBの実行後も1になっていてほしいところだが、Aがxの値をメモリに書き込む前にBの処理に移ってしまった場合Bによるxの読み込み値は1のままであり、実行結果が予想と変わってしまう。この処理順番により結果が変わってしまう恐れがある部分をクリティカルセクションといい、一度に実行される必要がある。

A() {
    Load(x)
    x++
    Write(x)
}

B() {
    Load(x)
    x--
    Write(x)
}

解決法としてグローバル変数で(turn=A or B)とし、turn == 自分でないときは処理を開始しないとすることもできるがこれではAが2回連続で処理を行うことができない。ハードウェアレベルで実装されている以下のメカニズムを使う必要がある。

セマフォ

int mutex = 1 の値を1つ上げるP()と1つ下げるV()からなり、V()はmutexの値が1以上になるまで次の処理に進まない。下記の例ではプロセスAが2つ同時に実行されていたとしてもV(mutex)が片方しか同時にクリティカルセクションに入らないことを保証する。

A() {
    int mutex = 1
    V(mutex)
    // クリティカルセクション
    P(mutex)
}

条件変数

簡単な並列処理でも複数のセマフォが必要になったり、複数のセマフォを同時に待つことはできなかったりとセマフォだけではどんどん複雑になってしまう。そこで必要となるのが条件変数である。条件変数とは待ちスレッドのコンテナであり、指定された条件が正となった時に全ての待ちスレッドが呼び起こされる仕様である。セマフォ、条件変数を用いて同期処理対応したオブジェクトをモニタと呼ぶ。

デッドロック

デッドロックとは「行き止まり」を指す言葉であるが、この場合は、ある他のスレッドのアクションを待っていて全てのスレッドが次に進めない状況次に進めない状況を指す。スターベーションと呼ばれる、あるスレッドの処理順番が長い間周ってこない状態もデッドロックによって引き起こされうる。

デッドロックは以下の4つの条件が全て揃った時に起こる。逆に言えば4つのうち1つでも解決すればデッドロックを防ぐことができる。①少なくとも1つのリソースが同期処理に対応していない。②リソースは途中で他に譲れること（プリエンプティブ）ができない。③少なくとも1つのスレッドがリソースを保持した上でさらに他のリソースを待っている。④循環待ち(AがBを待ち、BがAを待つ)

デッドロックしない順番で処理を行うように計算してスケジュールすることも可能だがコストがかかるため、実際はデッドロックが起きた（時間がかかりすぎている）場合、実行中のスレッドを停止し、順番を変え再実行する。

次回はOSがどのようにプロセスやスレッドを効率よくスケジュールしているかについてまとめたいと思います。