I-6-4. プロセスの切り替えとスケジューリングアルゴリズム

コンテキストスイッチの概念に触れ、プロセスが切り替わるメカニズムの概要を説明する。スケジューリングアルゴリズムの実際を紹介し、さらにその基礎となる理論でもある待ち行列議論とマルコス連鎖について解説する。

【学習の要点】

* マルチタスク・オペレーティングシステムにおいて、プロセスの切り替えを行う際には、コンテキストスイッチが発生する。これは、CPUの状態を保存したり復元したりする過程のことである。

* スケジューラは、プロセスの切り替え先を決定するプログラムで、各プロセスはタイムスライスと呼ばれる短い時間ずつ実行されたあと、切り替えられる。

* スケジューラは、CPUの負荷を公平かつ平等に分散させるために、スケジューリングアルゴリズムに基づいて、プロセスの制御を行う。

図I-6-4. プロセスの切り替え

【解説】

1) プロセスが切り替わるメカニズム

マルチタスク・オペレーティングシステムにおいては、実行中のプロセスであっても途中でCPUの使用を止め、他のプロセスに切り替えてそのプロセスにCPUの使用が可能となるようにしている。このプロセスの切り替えの際にコンテキストスイッチが発生する。

* コンテキストスイッチとは

プロセスの切り替えの際に、それまでのCPUの状態を保存したり、もしくは復元したりする処理のことである。

* タイムスライスとは

プリエンプティブ・マルチタスクでは、スケジューラが各プロセスを定められた時間だけ実行させて、他のプロセスに切り替えている。この時間のことをタイムスライスと呼ぶ。

* スケジューラ

実行プロセスの切り替え先を決定するプログラムがスケジューラである。スケジューラは、優先度つきキューで優先度を割り当てられたプロセスの制御を行う。

* 割り込み

プロセスがタイムスライスの時間内で終了しなかった場合には、タイマ割り込みが発生して他のプロセスへの切り替えが行われる。

2) スケジューリングアルゴリズムとは

スケジューラの目的は、CPUの負荷を分散し、全体として効率的な稼動を確保することにある。スケジューラは、スケジューリングアルゴリズムに基づいてプロセスの制御を行う。一般的に知られているスケジューリングアルゴリズムには、以下のようなものがある。

* FIFO ( First In, First Out )

「先入れ先出し」方式のこと。最初に発生したリクエストをキューに並べ、そのリクエストの処理が終了してから、次に発生したリクエストの処理を開始する。

* LIFO ( Last In, First Out )

あとから発生したリクエストを、先に処理する方法。公平なスケジューリングは実現されない。

* ラウンドロビンスケジューリング

キューに並んでいる処理待ち状態のプロセスに対して、特に優先度などの設定は行わず、順番に同じタイムスライスを割り当てていく。

* 多段フィードバックキュー

短いプロセスや対話型のプロセスを優先し、プロセスの性質を迅速に把握しスケジューリングを行う。UNIXの基本的なアルゴリズムである。

3) スケジューリングアルゴリズムの基礎となる理論

スケジューリングを行う際、各プロセスはキューと呼ばれる「コンピュータの基本的なデータ構造」の中に並べられる。キューは待ち行列とも呼ばれる。

OSS Course Naviのコンテンツは IPA OSS モデルカリキュラムを基としています。