恐竜本5章です。
用語に関して
プロセスが処理に必要とする時間のことをバーストと呼ぶ。CPUを使った処理に必要な時間はCPUバースト、I/Oに必要な時間はI/Oバーストと呼ぶ。バースト量はプロセスの種類や、そのプロセスがどのような状態となっているかに依存して決まる。
CPUがアイドル状態となったら、常にOSは次に実行するプロセスをreadyキューから取り出す。この取り出し方を決めるものをshort-term schedulerという。キューの種類はFIFOだけでなく、優先度付きキューや木でも良い。
スケジューリングの種類のうち、実行中のプロセスの完了を待たず中断して次のプロセスを実行する種類をプリエンプティブなスケジューリングという。プリエンプティブなスケジューリングでは、プロセスがデータを更新中に中断し、別のプロセスが同じデータを読み出すような状況が起こりうる。これを避けるため、排他制御が必要となる。また、システムコールによってカーネルが作業している間にプロセスが中断され、別のプロセスに移ったあとで同じデータを触ることがあると大きな問題となる。UNIX系ではシステムコールが完了するまでプロセスは中断されないように設計されているが、リアルタイムシステムやマルチプロセッシングでは性能を引き出すことができない。
ディスパッチャーはスケジューラによって選ばれたプロセスに実行を移す際に、コンテキストスイッチ、ユーザーモードへの遷移、プログラム上の前回実行位置への移動を行う機能である。ディスパッチャーはプロセス中断と再開の間に必ず実行され、ディスパッチレイテンシーというオーバーヘッドが必ず生じる。
スケジューリングの良さを決める基準
- CPU利用率
- スループット：単位時間あたりのプロセス完了数
- ターンアラウンドタイム：プロセス開始から終了までの時間
- 待ち時間：ready queue上でプロセスが費やす時間
- レスポンス時間：インタラクティブなプロセスでユーザーが入力してからレスポンスが返ってくるまでの時間
First-Come First-Servedスケジューリング
First-Come First-Served(FCFS)スケジューリングは最初に来たプロセスから順番に実行する、非プリエンプティブスケジューリングである。もし最初のプロセスに時間がかかるなら後ろのプロセスはそれまで待ち続けることになる。後ろのプロセスがI/OバウンドでCPUをあまり使わない場合には明らかに無駄が多い。
Shortest-Job-Firstスケジューリング
Shortest-Job-First(SJF)スケジューリングはCPUバーストが最も短いプロセスから実行する。プロセスの待ち時間はスケジューリングアルゴリズムの中で最短となる。ただし、CPUバーストを予め知ることは困難である。代わりに、指数平滑移動平均を使って過去のCPUバーストから今回のCPUバーストを予測することが考えられる。また、SJFスケジューリングはプリエンプティブにも非プリエンプティブにもできる。プリエンプティブにする場合、残りのCPUバースト時間で処理順を決めるのでshortest-remaining-time-firstスケジューリングということもある。
優先度スケジューリング
SJFアルゴリズムは優先度スケジューリングの特殊例と見ることができる。優先度スケジューリングはプロセスに優先度をつけてその順番で実行する。SJFではCPUバーストの逆数で優先度をつけているとみなせる。優先度スケジューリングの問題としては、低優先度のプロセスが永久に実行されないというものがある。これを無限ブロッキング、starvationなどという。対策としては、エージングがある。エージングは低い優先度のプロセスの優先度を時間とともに上げていく手法である。
ラウンドロビンスケジューリング
ラウンドロビンスケジューリングはタイムクオンタム（タイムスライス）という制限時間をプロセスに割当て、その中で処理が終わらなかったら中断してreadyキューの最後に回すプリエンプティブなスケジューリング手法である。タイムクオンタムが非常に長い極限ではFCFSとなる。非常に短くするとプロセッサシェアリングと呼ばれる状態になり、処理時間をプロセスに等分配していることになる。ただし、コンテキストスイッチのオーバーヘッドが処理時間中に占める割合が増え、非効率性が上がる。タイムクオンタムとしては80%のCPUバーストが収まる程度にするのが良いと経験則的にいわれている。
マルチレベルキュースケジューリング
複数のキューを用意しておき、それらの間に優先度を決めておく。また、プロセスごとにどの優先度に属するかを決める。存在するプロセスの中で最も優先度が高いキューに入っているものを実行するのがマルチレベルキュースケジューリングである。高い優先度には通常インタラクティブなプロセス、低い優先度にはバッチプロセスを入れる。
マルチレベルフィードバックキュースケジューリング
マルチレベルキュースケジューリングではプロセスは最初にアサインされた優先度のキューにずっと入り続ける。より柔軟にするためには、マルチレベルフィードバックキュースケジューリングが使用される。複数のキューが存在し、優先度がついているのは変わらない。ただし、それぞれのキューごとにスケジューリングアルゴリズムが存在しており、プロセスがどのキューに入るか動的に変化する。例えば、それぞれのキューに異なるタイムクオンタムが割り当てられており、上位のキューのタイムクオンタムで終わらなかったプロセスは低い優先度のキューに回す、などの方式が存在する。この方式はキューの数、キューごとのスケジューリングアルゴリズム、プロセス優先度の変更基準などの組み合わせで定義づけられる。
スレッドのスケジューリング
4章にて、スレッドにはユーザーレベルスレッドとカーネルレベルスレッドが存在することを述べた。スレッドのスケジューリングはこれらの間で異なる。ユーザーレベルスレッドのスケジューリングはスレッドライブラリが行い、どのスレッドをLWP(カーネルスレッドに対応)上で実行するか決める。これをprocess-contention-scope(PCS)という。カーネルレベルスレッドはカーネルがスケジューリングする。これをsystem-contention-scopeという。PCSでの優先度はプログラマーが指定できる。
マルチプロセッサスケジューリング
マルチプロセッシングにおいては、readyキューから取り出されたプロセスが実行されるプロセッサが変化すると、キャッシュメモリの内容も移動しなければならずオーバーヘッドが大きくなるという問題がある。これを解決するため、できる限り同じプロセッサで同じプロセスを実行するprocessor affinityが重要となる。Solarisではプロセスが特定のプロセッサセットで実行されることを保証できる。
また、プロセッサごとの負荷が偏ると全体としての処理能力が減ってしまうためロードバランシングが重要である。ロードバランシングの方法としては、負荷の監視をして負荷が上がっているプロセッサから負荷が低いプロセッサにプロセスを移動するpush migrationと、負荷が低いプロセッサが負荷の高いプロセッサからプロセスを引き抜くpull migrationがある。いずれにしても、processor affinityとmigrationは相反する概念なので、どちらが効率が良いかはシステムの目的に依存する。
マルチコアプロセッサでは、別の問題が存在している。キャッシュミスなどであるプロセッサがメモリにアクセスしようとすると長い時間待たされる現象である、メモリストールがそれに当たる。最悪の場合実行時間の半分はメモリストールで待たされる事がある。このような場合にはメモリストール中に別ハードウェアスレッドで別のことを行うことが対処法となる。ハードウェアスレッドとソフトウェアスレッドは別物である。ハードウェアスレッドの動かし方としては、coarse-grainedとfine-grainedの2種類がある。coarse-grainedはメモリストールなどの長レイテンシーイベントが起きた場合にスレッドを切り替え、fine-grainedは命令サイクルの境界などでより細かい切り替えを行う。OSとしてはハードウェアスレッドを1コアと認識して処理を行う。
仮想化において、ゲストシステムのスケジューリングとホストシステムのスケジューリングが組み合わさるとレスポンス速度の低下が起こりうる。これは、各ゲストシステムに割り当てるCPU時間が既に分割済みであるのにゲストシステムが更にそれを分割してプロセスに配分するからである。
スケジューリングアルゴリズムの評価
どのスケジューリングが良いのかの評価手法は複数存在する。
決定論的モデリングでは、プロセスのCPUバーストとreadyキューへの到着順を固定で想定して待ち時間を解析する。解析は簡単だが非現実的な見積もりとなる。
待ち行列理論を使った解析では、平均的なreadyキュー到着頻度λ、待ち行列の長さnから待ち時間Wを求める。Littleの式と呼ばれる関係式では、n=λ×Wが成り立つ。この式はどんなスケジューリングアルゴリズム、どんなプロセス到着分布であっても成り立つ。しかしながら、スケジューリングアルゴリズムや到着分布が複雑になると計算が難しくなる。そのため、計算しやすいアルゴリズムや分布を想定したりするが、そうすると非現実的な見積もりと化す。
より正確に見積もる方法として、シミュレーションがある。実際のスケジューリングアルゴリズムを使い、何らかの到着分布を仮定して スケジューリングの様子をシミュレートする。分布の仮定が難しいなら実際のシステムからサンプリングしてそれを使えば良い。しかし、データ量が大きくなったり、シミュレータの実装に時間がかかったりなどの問題点がある。
最後に、実際に製品に色々なスケジューリングアルゴリズムを組み込んでデータを取るというのがある。しかし、この方法は性能が低下した場合にユーザーに負担を強いることになる。また、組み込むコストが高いのも言うまでもない。
ユーザーが自分自身である程度スケジューリングをチューニングできるようにしておき、自分で最適化できるようにするというアプローチもある。
所感
ここまで知識の確認みたいなことが多く退屈でしたが、本格的な仕組みの解説に入ってきた感があり読み応えがありました。スケジューリングみたいなものを実装したり利用することは時たまあると思うので、メリデメをわかっておくことはOSを作る機会がなくても役立ちそうですね。
コメント