Chapter 2:

時間をスライス Edit on GitHub

仮にあなたがオペレーティングシステムを構築しており、ユーザーが複数のプログラムを同時に実行できるようにしたいとしましょう。ただし、ファンシーなマルチコアプロセッサは持っていないため、CPUは一度に1つの命令しか実行できません！

幸いなことに、あなたは非常に賢いOS開発者です。プロセスにCPUを交代させることで、並行処理を模倣できることを理解します。プロセスを順番に切り替えて、各プロセスからいくつかの命令を実行すれば、CPUを占有するプロセスがなくても、すべてのプロセスが応答性を持つことができます。

しかし、プログラムコードから制御を取り戻すにはどうすればいいのでしょうか？少しの調査の後、ほとんどのコンピュータにはタイマーチップが付属していることがわかります。タイマーチップをプログラムして、一定の時間が経過した後にOSの割り込みハンドラに切り替えるようにすることができます。

ハードウェア割り込み

以前、ソフトウェア割り込みがユーザーランドプログラムからOSへの制御を渡す方法についてお話ししました。これらは「ソフトウェア」割り込みと呼ばれます。プログラムによって自発的にトリガーされるためです。プロセッサによって実行される機械コードは通常のフェッチ-実行サイクルで、カーネルに制御を切り替えるように指示します。

OSのスケジューラは、PIT（Programmable Interval Timer）などの タイマーチップ を使用して、マルチタスキングのためのハードウェア割り込みをトリガーします：

1. プログラムコードにジャンプする前に、OSはタイマーチップを設定して、一定時間後に割り込みをトリガーするようにします。
2. OSはユーザーモードに切り替え、プログラムの次の命令にジャンプします。
3. タイマーが経過すると、カーネルモードに切り替え、OSコードにジャンプする割り込みがトリガーされます。
4. OSは今、プログラムが中断した場所を保存し、異なるプログラムをロードしてプロセスを繰り返すことができます。

これは 優先的なマルチタスキング と呼ばれ、プロセスの中断は 優先度変更（preemption） と呼ばれます。たとえば、ブラウザでこの記事を読んでいて、同じコンピュータで音楽を聴いている場合、あなたのコンピュータはおそらく1秒間に何千回もこの正確なサイクルを実行しています。

タイムスライス計算

タイムスライス は、OSのスケジューラがプロセスを中断する前に実行を許可する期間です。タイムスライスを選ぶもっとも簡単な方法は、すべてのプロセスに同じタイムスライスを与え、おそらく10ミリ秒程度の範囲で、タスクを順番にサイクルさせることです。これは 固定タイムスライス・ラウンドロビン スケジューリングと呼ばれます。

余談: 面白い専門用語の事実！

タイムスライスはしばしば “クォンタム” と呼ばれることがあります。これを知っていたら、テック仲間たちに感心されるでしょう。この記事の中でクォンタムを他の文で何度も言わなかったことに対して、私はたくさんの称賛を受けるべきだと思います。

タイムスライスの専門用語に関して言えば、Linuxカーネル開発者は jiffy 時間単位を使用して固定周波数のタイマータイク数をカウントします。ジフィは、タイムスライスの長さを測定するために使用されます。Linuxのジフィ周波数は通常、1000 Hzですが、カーネルをコンパイルする際に設定することができます。

固定タイムスライススケジューリングへのわずかな改善策は、ターゲットレイテンシー を選択することです — プロセスが応答するための理想的な最長時間です。ターゲットレイテンシーは、プロセスが中断された後に実行を再開するまでの時間であり、合理的な数のプロセスを想定しています。これはかなり視覚化が難しいです！心配しないでください、すぐにダイアグラムが登場します。

タイムスライスは、ターゲットレイテンシーをタスクの総数で割ることで計算されます。これは、より少ないプロセスで無駄なタスク切り替えを排除するために固定タイムスライススケジューリングよりも優れています。ターゲットレイテンシーが15ミリ秒でプロセスが10個ある場合、各プロセスには15/10または1.5ミリ秒のタイムスライスが与えられます。プロセスが3つしかない場合でも、各プロセスは目標のレイテンシーを達成しながら、5ミリ秒のより長いタイムスライスを取得します。

プロセスの切り替えは計算上の負荷が高いです。なぜなら、現在のプログラムの完全な状態を保存し、異なるプログラムを復元する必要があるからです。ある一定のポイントを過ぎると、タイムスライスが小さすぎるとプロセスの切り替えが過度に頻繁に発生し、パフォーマンスの問題が発生する可能性があります。通常、タイムスライスの長さに下限（最小の粒度）を設けることが一般的です。これは、最小の粒度が効果を発揮するプロセスの数がある場合、ターゲットレイテンシーが超えられることを意味します。

この記事を執筆時点では、Linuxのスケジューラはターゲットレイテンシーを6ミリ秒、最小の粒度を0.75ミリ秒で使用しています。

この基本的なタイムスライス計算を用いたラウンドロビンスケジューリングは、現代のほとんどのコンピュータが行うことに近いです。それでも、これは少し単純な方法です。ほとんどのオペレーティングシステムは、プロセスの優先順位や締切を考慮に入れるより複雑なスケジューラを持つ傾向があります。2007年以来、Linuxは 完全に公平なスケジューラ と呼ばれるスケジューラを使用しています。CFSはタスクを優先順位付けし、CPU時間を分配するために非常に高度なコンピュータサイエンスのテクニックを使用します。

OSがプロセスを中断するたびに、新しいプログラムの保存された実行コンテキスト、メモリ環境を読み込む必要があります。これはCPUに異なる ページテーブル、つまり “仮想” から物理アドレスへのマッピングを使用するように指示することで実現されます。これはまた、プログラムが互いのメモリにアクセスできないようにするシステムでもあります。この記事の第5章 と第6章 でこのテーマについて詳しく掘り下げていきます。

ノート #1: カーネルの優先度設定

これまで、ユーザーランドプロセスの優先度とスケジューリングについてしか話していませんでした。カーネルコードがシスコールを処理するのに時間がかかるか、ドライバーコードを実行するのに時間がかかりすぎる場合、プログラムは遅く感じることがあります。

Linuxを含む現代のカーネルは、プリエンプティブカーネル として知られています。これは、カーネルコード自体もユーザーランドプロセスと同様に中断され、スケジュールされるようにプログラムされていることを意味します。

これはカーネルを書いている場合を除いてはあまり重要ではありませんが、基本的には私が読んだ記事には必ず言及されているので、私も言及してみました！余分な知識はほとんど悪いことではありません。

ノート #2: 歴史の教訓

古代のオペレーティングシステム、クラシックなMac OSやNT以前のWindowsのバージョンなどは、プリエンプティブマルチタスキングの前身を使用していました。OSがプログラムを優先的に中断するタイミングを決定するのではなく、プログラム自体がOSに譲歩することを選択しました。彼らはソフトウェア割り込みをトリガーして、「ねえ、別のプログラムを実行させてもいいよ」と伝えました。これらの明示的な譲歩が、OSが制御を取り戻し、次にスケジュールされたプロセスに切り替える唯一の方法でした。

これは 協力的マルチタスキング と呼ばれています。これにはいくつかの重大な欠点があります：悪意のあるか、単に設計が不良なプログラムは、オペレーティングシステム全体を簡単に凍結させることができ、リアルタイム/時間に敏感なタスクの時間的整合性を確保することはほぼ不可能です。これらの理由から、テックワールドはずっと前にプリエンプティブマルチタスキングに切り替え、一度も戻ることはありませんでした。