且听风吟

プロセス#

• 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 を実行していない場合、または 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 になります。ストライドスケジューリングは固定のタイムスライスを設定し、毎回現在の移動距離が最小のタスクを選択して 1 回実行し、そのタスクの移動距離に対応するストライドを加えます。ストライドが異なるため、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 リソースが浪費される可能性があります。

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

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

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

プロセッサの親和性#

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