このテキストは、運営している韓国のブログを日本語に翻訳したものです。
韓国のブログ：https://yunsuu.notion.site/e379eccd32c545419f0651f743c12c13?v=35310b282de24cc5a292fe45cc498a32&pvs=74
この記事は「Operating Systems: Three Easy Pieces」を読んでまとめた本です。
著者が無料で公開しているので、興味のある方はぜひ読んでみてください。
本にある良い問題は解いてgithubにアップロードしています。
github：https://github.com/yunsuu/ostep-homework-solution
本のリンク：https://pages.cs.wisc.edu/~remzi/OSTEP/
サムネイル画像
この記事は、OSTEP Chapter 7のスケジューリングを学んだ後に整理しながら書いたものです。
スケジューリング
オペレーティングシステムの目標の一つは、一つのCPUでさまざまな作業を同時に進行させるように見せることです。これをこの本では「CPUの仮想化」と表現しており、スケジューリングの目標はCPUの仮想化にあります。CPUの仮想化を実装するためには、一つのCPUで進行中のプロセスを中断し、別のプロセスに切り替える作業、つまりコンテキストスイッチを行う必要があります。スケジューリングは、各プロセスがどのように切り替えられるべきかを示すタイムテーブルを提供し、コンテキストスイッチを効率的に行えるように支援する方法です。
スケジューリングを説明する前に設定した前提
スケジューリングを説明するために、次の5つの前提を設定します。
これらの前提を一つずつ緩和していき、次第に現実的なスケジューリング方法に近づけていきます。
- すべての作業は同じ時間で実行されます。
- すべての作業は同時に到着します。
- 作業が始まると終了するまで実行されます。
- 作業はCPUのみを使用します（I/O割り込みは発生しません）。
- 各作業の実行時間は事前に知られています。
スケジューリングの評価項目
スケジューリングの評価項目はいくつかあるでしょうが、大きく2つの要素で評価することができます。
返却時間 = 作業が完了した時間 - 作業が到着した時間
応答時間 = 作業が開始された時間 - 作業が到着した時間
理解を深めるために例を挙げてみます。
レストランを評価する審査員が、時間的な観点からレストランがどれだけ優れた店であるかを評価するためには、2つの観点から評価を考えることができます。（このレストランはコース料理を提供するレストランです。）
一つ目は、注文をどれだけ早く処理するかです。
キッチンから見ると、注文を処理するとき、同じ注文でも処理の方法によって時間がかかるか早く終わるかが変わります。
この時間が返却時間です。つまり、コース料理の注文が入ってから最後の料理を客に出すまでの処理時間が短ければ短いほど、素晴らしいキッチンと評価されるでしょう。
二つ目は、客がどれだけ待たされないかです。
キッチンから効率的に処理すると考えても、注文した後のアペタイザーが1時間後に出てくるなら、それは良いレストランとは言えません。キッチンの効率とは別に、アペタイザーや飲み物の準備など、時間が短くかかる作業は、早く客にサービスされるべきで、客の不満が少ないでしょう。
客が一つのリクエストを入れてから次のリアクションを得るまでの時間は、応答時間です。応答時間が短ければ短いほど、良いレビューを得る可能性が高くなるでしょう。
FIFO
- FIRST IN FIRST OUT: 最初に到着した作業から実行する方法
- 我々が設定した前提を守れば問題なく動作し、公平な方法です。
問題点
仮定1（すべての作業は同じ時間で実行される）を緩和してみましょう。
最初に実行する作業Aが大きい場合、B、Cの返却時間もAの影響を受けて急激に増加する可能性があります。（Aが終了するまで待たなければならないため、作業が完了した時間が急激に増えます）
FIFOの問題を解決するためには、最短のプロセスから先に実行すると問題点を解決することができます。
SJF
- 最短のプロセスから実行するスケジューリングポリシーです。
- A, B, Cの順で到着するとしても、プロセスの実行時間の順番であるB, C, Aの順で実行されます。
問題点
仮定2（すべての作業は同時に到着する）を緩和してみましょう。
Aが実行される途中でB、Cが到着すると、最も非効率的なA、B、Cの順で実行しなければならないでしょう。
これを解決する方法は何でしょうか？
STCF
この問題を解決するためには、仮定3を緩和する必要があります（作業は始まると終了するまで実行される）
つまり、実行中に非効率的だと判断された場合は、即座に停止して別のプロセスを実行できるようにする必要があります。
Shortest Time-to-Completion First、SJFにプリエンプション機能を追加したスケジューリング技法です。
現在実行中の作業の残りの実行時間と新たな残り作業の実行時間を比較し、残り時間が最も少ない作業を実行します。
B、Cが到着したときに、すべてのプロセスの実行残り時間を比較して最も少ないBとCから実行することで、SJFで発生する問題を解決することができます。
ROUND ROBIN
これまで見てきたスケジュールポリシーは、返却時間の観点からは良いかもしれませんが、応答時間の観点からは良いスケジューリングではありません。考えてみてください、これまで紹介してきたスケジューリング技法はすべて、最後に実行されるプロセスが最も遅く実行されるのではないでしょうか？お客様がステーキを注文したのに、作業時間が長いとステーキを受け取れない。自分より遅く来たお客様がアイスクリーム、アメリカーノを次々に受け取って行くお客様を見ていると、怒りがこみ上げてくるでしょう。ステーキを注文したお客様が怒らないように、応答しないで放置するのではなく、適切に対応する必要があります。
ラウンドロビンは、一定の時間単位（time sliceと呼びます）でプロセスA、B、Cを交互に実行することです。
これにより、A、B、Cのお客様全員が適切なタイミングで対応を受けることができ、怒るお客様は少なくなるでしょう。
問題点
ラウンドロビンでは、time sliceの時間が最も重要な議論点となります。time sliceの時間が短くなると、応答時間の観点からは性能が向上しますが、コンテキストスイッチが過度に発生することになります。コンテキストスイッチには準備費用がかかるため、あまりにも短く設定すると、全体的なスケジューリングの性能が低下する可能性があります。したがって、time sliceは、コンテキストスイッチのコストを補償するほどの適切な長さであるべきです。
返却時間の観点から見ると、ラウンドロビンは最も基本的なFIFOと比較しても性能が落ちます。
すべてはバランスが重要です。
I/O interuptを考慮する
仮定4を緩和してみましょう（作業はCPUのみを使用し、つまりIO割り込みは発生しない）
割り込みが発生すると、プロセスAとBは次のような形になるでしょう。
しかし、図を見るとCPUが働いていない部分が見えます（CPUがタイムラインが空いている部分）。これを効率的に活用することはできないでしょうか？
CPUが空いている部分でプロセスBを実行すれば、空きなしですべてのリソースを活用し、より効率的な作業が可能になります。この作業はコンピュータアーキテクチャ理論ではパイプラインと呼び、この概念はオペレーティングシステム、コンピュータアーキテクチャ、ネットワークのパケットなど、多くの分野を通じてコンピュータの核心理論の全範囲で使用される概念です。