且听风吟

プロセス#

• new: プロセスが作成されたばかりで、まだ初期化が完了していない
• ready: プロセスがスケジュール実行可能
• running: プロセスが CPU 上で実行中
• blocked: ブロックされており、外部イベントの完了を待っている
• terminated: 実行が完了し、再びスケジュールされることはない

Linux はforkを使用して現在のプロセスから新しい子プロセスを作成します：親プロセスに対しては fork が子プロセスの PID を返し、子プロセスに対しては fork が 0 を返します。fork を実行する際、子プロセスは親プロセスのPCB（プロセス制御ブロック）内のデータをコピーします。例えば、オープンされたファイルディスクリプタテーブルですが、両プロセスの FD テーブルが指すファイルデータ構造は同じであり（ポインタをコピーしただけに相当）、両プロセスはオープンファイルのポインタを共有します。ファイルを読み取る際に共有オフセットの影響を受けるため、読み取るデータは一致しません。

fork を通じて、親プロセスとほぼ同じ子プロセスを得ることができ、Linux ではexec系列のインターフェースを使用して現在のプロセス内で新しいプログラムを実行できます。execveを使用すると、オペレーティングシステムは以下の操作を実行します：

1. 指定された実行可能ファイルのパスに基づいてデータセグメントとコードセグメントをアドレス空間にロードします
2. ヒープとスタックを再初期化し、アドレス空間のランダム化を行い、スタックの開始アドレスを変更します
3. PC レジスタを実行可能ファイルのコードセグメントのエントリに設定します

Linux の最初のプロセスはinitプロセスであり、すべてのプロセスは fork を通じて作成されます。各プロセスは自分の親子プロセスを記録し、これによりすべてのプロセスはプロセスツリーを形成します。親プロセスはwaitを通じて子プロセスの終了を監視し、その状態を確認できます。例えば、異常終了したかどうかなどです。親プロセスが wait を実行しないか、実行する暇がない場合、子プロセスがすでに終了していると、子プロセスのリソースは完全には回収されません。Linux ではこのようなプロセスをゾンビプロセスと呼びます。

Linux カーネルはプロセスグループ process groupの概念を定義しており、これは複数のプロセスで構成される集合です。アプリケーションプロセスはkillpgを使用してプロセスグループに信号を送信できます。この信号はグループ内のすべてのプロセスに送信されます。複数のプロセスグループの集合はセッション sessionを構成し、セッションはプロセスグループをフォアグラウンドプロセスグループとバックグラウンドプロセスグループに分けます。フォアグラウンドプロセスグループは通常、制御端末 controlling terminalプロセスの入力（例えば、標準入力や信号など）を受け取るために使用されます。セッションとプロセスグループは主にシェル環境のプロセス管理に使用されます。

スレッド#

スレッドはプロセス内で独立して実行できる単位であり、同じプロセス内のすべてのスレッドは同じアドレス空間を共有しますが、異なる実行コンテキスト（レジスタの状態やスタックなど）を持っています。マルチスレッドアプリケーションのアドレス空間の分布は以下の通りです：

オペレーティングシステム内のスレッドはユーザーモードスレッドとカーネルスレッドに分かれます。ユーザーモードスレッドがシステムコールを行う場合、カーネルスレッドに入って実行する必要があるため、各ユーザーモードスレッドに対応するカーネルスレッドを割り当てる必要があります。割り当て方法はいくつかあります：

• 多対一：複数のユーザースレッドが 1 つのカーネルスレッドに対応し、欠点は同時に 1 つのユーザースレッドしかカーネルに入れないことです
• 一対一：各ユーザースレッドが 1 つのカーネルスレッドに対応し、欠点はユーザープロセスの増加に伴いカーネルスレッドの数が増えることです
• 多対多: N 個のユーザースレッドが M 個のカーネルスレッドに対応（N > M）し、カーネルがマッピング関係を管理し、スケジュールする必要があります

各スレッドにはスレッド制御ブロック TCBデータ構造があり、スレッドのコンテキスト情報を保存します。

ユーザーモードスレッドは特別なスレッドローカルストレージ TLSスレッドローカルストレージ変数を作成できます。複数のスレッドは同じ TLS 変数を使用できますが、各スレッドが読み書きするのは本スレッド内のデータのコピーのみです。以下は擬似コードです：

__thread int count; // TLS変数を宣言

thread1.set(&count, 1); // スレッド1がcountに1を書き込む
thread2.set(&count, 2); // スレッド2がcountに2を書き込む
thread1.get(&count) == 1; // スレッド1がcountを読み取った結果は1
thread1.get(&count) == 2; // スレッド2がcountを読み取った結果は2

x86-64アーキテクチャでは、スレッドがスケジュールされると、libpthread はそのスレッドの TLS の開始アドレスをFSセグメントレジスタに書き込みます。スレッドが TLS 変数にアクセスする際は、FS レジスタ内のアドレスに変数のオフセットを加えてアクセスします。つまり、実際にはマルチスレッドが各自の TLS 変数を読み書きする際に使用するアドレスは異なります。

Linux では、スレッドの作成、終了などの操作はすべてlibpthreadインターフェースを呼び出すことで実現されます：

• pthread_create: 現在のプロセス内にスレッドを作成し、指定された関数を実行します。底層では clone 呼び出しを通じて実現されます
• pthread_exit: 現在のスレッドを終了します。関数の実行終了時に暗黙的に呼び出され、明示的に呼び出して戻り値を設定できます
• pthread_yield: 現在のスレッドを積極的に一時停止し、リソースを譲渡し、次のスケジュールを待ちますが、スレッドは依然として ready 状態にあります
• pthread_join: 指定されたスレッドの終了を待ち、その戻り値を取得します
• pthread_cond_wait: 指定された条件変数を待ち、マルチスレッドの同期に使用されます

スケジューリングの概念#

スケジューリングの指標#

• スループット：単位時間内に処理されるタスクの数
• 周転時間：タスクが開始から終了までにかかる時間
• 応答時間：インタラクティブタスクのリクエスト応答にかかる時間
• リアルタイム性：リアルタイムタスクの完了度（特定の締切前に完了する必要があるタスク）
• エネルギー消費
• リソース利用率
• 公平性
• スケジューラ自体のオーバーヘッド

長期、中期、短期スケジューリング#

長期スケジューリング#

長期スケジューリングは、システム内でスケジュール可能なタスクの総量を主に制御します。例えば、短時間内に大量のプロセスが作成された場合、長期スケジューリングはすべてのプロセスを即座に ready 状態に移行させることはありません（リアルタイム性が高いインタラクティブタスクは例外です）。そうしないと、タスクの数が急増し、スケジューリングのオーバーヘッドが増大します。また、長期スケジューリングは現在のシステムの CPU および I/O の使用状況に基づいて、スケジュール可能なプロセスを適切にバランスさせ、大量の I/O タスクや CPU タスクが同時に発生してリソース競合や利用率不足を引き起こすのを避けます。全体として、長期スケジューリングはタスクをスケジュールに組み込むかどうかを決定することで総量を制御し、短期スケジューリングの負担を軽減します。

短期スケジューリング#

短期スケジューリングは具体的なスケジューリングの決定を実行し、タスクの状態をblocked/ready/runningの間で変換します。例えば：

• running 状態のプロセスが予想されるタイムスライスを超えて実行されると、スケジュールが奪われ、ready 状態に変換されて次のスケジュールを待ちます
• タスクが実行中または I/O を待っていると、blocked 状態に変換され、I/O イベントが準備完了すると ready 状態に変換されます
• ソフトウェア / ハードウェア（例えば、クロック）による割り込み、システムコールなどがタスクの実行を中断します

中期スケジューリング#

中期スケジューリングはページ置換メカニズムの一部であり、システム内で実行可能および実行中のタスクのメモリ使用を制御し、使用量がメモリリソースの総量を超えないようにします。実際の運用中に、システム内のタスクが大量のメモリを占有している場合、中期スケジューリングは特定のタスク（例えば、ページフォルトが頻繁に発生するタスク）を選択して一時停止suspendし、その後ページ置換メカニズムは一時停止されたプロセスのメモリをディスクにスワップアウトしてシステムのメモリ圧力を軽減する傾向があります。一時停止されたタスクは短期スケジューリングで使用できず、短期スケジューリングの負担をさらに軽減します。

全体的なスケジューリングの概念図：

スケジューリングメカニズム#

優先度スケジューリング#

タイムスライスラウンドロビン：各タスクは指定されたタイムスライスの時間を実行し、その後次のタスクに切り替えます。このスケジューリング戦略は平均周転時間を長くする可能性があります（例えば、システム内にタスクが 2 つしかない場合、タイムスライスラウンドロビンは 2 つのタスクの切り替えに大量の時間を費やします）。また、タイムスライスのサイズをバランスさせる必要があります：小さすぎると、スケジューリングと状態変換のオーバーヘッドが大きくなります；大きすぎると、特定のタスクが過度に遅延します。

インタラクティブタスクのリアルタイム性の要求を考慮して、各プロセスに優先度を指定できます。高優先度のタスク（例えば、インタラクティブタスクやリアルタイムタスク）は、スケジューラによって優先的に実行されます。

実際の運用では、一般的に複数の高優先度のタスクが存在するため、マルチレベルキューの方式を使用してすべてのタスクを異なる優先度に割り当て、高優先度のタスクが先に実行されますが、同一優先度内の複数のタスクは 1 つのキューに配置され、タイムスライスラウンドロビンまたは他の戦略でスケジュールされます。この戦略は、低優先度のタスクが長時間実行できない原因となる可能性があります。

マルチレベルキューの基礎の上に、タスクの実行状況に応じて優先度を動的に調整することができ、これをマルチレベルフィードバックキュー Multi-Level Feedback Queueと呼びます。この方法は、短いタスク（例えば、I/O 集約型やインタラクティブなタスクなど、CPU 上での実行時間が短いタスク）により高い優先度を設定し、より良い平均周転時間を得ることを目指します。

動的優先度調整戦略：タスクの実行開始時に MLFQ は新しいタスクに高い優先度を設定します（インタラクティブおよびリアルタイムタスクに便利です）。各優先度に対して MLFQ は最大実行時間（タスクが複数回実行される総時間）を設定します。このキューでのタスクの実行時間がこの時間を超えると、MLFQ はそのタスクを長いタスクと見なし、次のレベルのキューに移動させます。複数回の実行後、そのタスクは実行時間に応じて適切な優先度に調整されます。

低優先度のタスクは一般的に長いタスクであるため、低優先度キューのタイムスライスも比較的長く、高優先度キューのタイムスライスは比較的短くなります。

公平共有スケジューリング#

スケジューリング指標を向上させるだけでなく、特定の状況ではリソースの公平なスケジューリングを実現する必要があります。例えば、ユーザー A とユーザー B が同じ価格で 1 台のマシンを共有しているが、ユーザー A が 3 つのプロセスを実行し、ユーザー B が 1 つのプロセスしか実行していない場合、システムはユーザー A とユーザー B がそれぞれ 50% のリソース、すなわち CPU のタイムスライスを占有できることを保証する必要があります。

宝くじスケジューリング#

宝くじスケジューリングは、各タスクに一定の割合の宝くじを割り当て、各スケジューリング時に当選番号を抽選し、この当選番号に基づいて実行するタスクを選択します。これは重み付きのランダムに似ています。擬似コードは以下の通りです：

loop:
    R = random(0, total_tickets)
    for sum = 0; task in task_list; {
        sum += task->tickets
        if sum > R {
            schedule(task)
            goto loop
        }
    }

この方法により、各ユーザーに同じ宝くじの額を割り当てることで、CPU 時間の公平な分配を保証できます。しかし、実際の分配状況はランダムに依存し、スケジューリング回数が少ない場合、ランダムデータが不均一であるため、短期間の不均等な分配を引き起こす可能性があります。

ストライドスケジューリング#

ストライドスケジューリングは、ストライドを設定することでタスクに公平な時間を割り当て、宝くじスケジューリングのランダム性の影響を排除します。

例えば、タスク A と B が割り当てられるリソースの比率が 6:5 である場合、ストライドスケジューリングはその逆比をストライドとして使用します。つまり、A と B のストライドは 5 と 6 です。ストライドスケジューリングは固定のタイムスライスを設定し、毎回現在の移動距離が最小のタスクを選択して実行し、その移動距離に対応するストライドを加えます。ストライドが異なるため、2 つのタスクが最終的に実行するタイムスライスの数量比は 6:5 となり、安定した公平な分配の目的を達成します。擬似コードは以下の通りです：

loop:
    task = queue.pop_min()
    schedule(task)
    task.pass += task.stride
    queue.push(task)
    goto loop

マルチコアスケジューリング#

マルチコアのシナリオでは、システムが同時に複数のタスクを実行できるため、スケジューラは同時にどのタスクを実行できるかを決定し、これらのタスクがどのコアで実行されるかを考慮する必要があります。また、同じコア上で異なるタスクをスケジュールする場合、頻繁な切り替えによる性能損失（ページテーブルの切り替え、レジスタのアクセスなど）も考慮する必要があります。

協調スケジューリング#

特定のタスク間に関連があるシナリオ、例えばリクエスト - レスポンス関係のある 2 つのタスクがある場合、同時に実行できないと、A がメッセージを送信したときに B が実行されていないと、そのメッセージは次回 B がスケジュールされるまで受信できません。また、B がスケジュールされて実行されるとき、A が再びスケジュールされる可能性があり、返されたメッセージを即座に受信できません。このように、リクエストを送信するたびに応答を受け取るたびに、スケジューリングによって少なくとも 1 つのタイムスライスの遅延が発生し、プログラムの実行効率が低下します。このようなシナリオでは、協調スケジューリングを使用する必要があります：毎回一組のタスクを並行して実行します。これにより、関連するタスク（同時に実行する必要があるタスク）を同じグループに割り当てて並行して実行でき、依存関係のあるタスク（あるタスクが別のタスクの実行を待つ必要がある）は異なるグループに割り当てられ、無駄な待機による CPU リソースの浪費を避けます。

協調スケジューリングは一般的に並列計算に使用されます。つまり、大きなタスクを複数のサブタスクに分割し、マルチコアで並行して実行して計算を加速します。しかし、より一般的なシナリオでは、協調スケジューリングを使用すると、グループ内のタスクの相互待機（注意：協調スケジューリングはタスク単位ではなくグループ単位であるため）によって CPU リソースが浪費される可能性があります。

協調スケジューリングの古典的な戦略の 1 つはグループスケジューリングであり、基本的な考え方はすべてのタスクを異なるグループに分け、関連するタスクを同じグループに割り当て、グループ単位でタスクを複数のコアで実行することです。例えば、現在 4 つの CPU コアと 3 つのタスクグループ A/B/C があり、各グループ内にそれぞれ 4/3/2 のタスクがある場合、スケジューリングの状況は以下の通りです：

二段階スケジューリング#

マルチコアのシナリオでは、タスクが異なるコア間で切り替えられる際のオーバーヘッドを考慮し、特定のタスクを固定のコアに割り当ててスケジューリングおよび実行することができます。つまり、新しいタスクはまずグローバルスケジューラを通じて特定のコアに割り当てられ、各コアは単一コアスケジューリング戦略を使用して自分に割り当てられたタスクを実行します。システムの運用中、グローバルスケジューラは各コアの負荷状況に応じて、異なるコア間でタスクの割り当てをバランスさせます。このスケジューリング方式は二段階スケジューリングと呼ばれます。

プロセッサの親和性#

特定のオペレーティングシステムは、自身のスケジューラの上にユーザープロセスに対してプロセッサの親和性に関連する呼び出しインターフェースを提供し、アプリケーションプロセスが CPU コアの使用状況を制御できるようにします。例えば、Linux はsched_setaffinityインターフェースを提供し、ユーザープロセスが特定のコアでのみ実行されるように制御できます。