【Linux カーネル: OS 基礎入門2】プロセス管理・CPU 割り当て

Linux

本記事は全5回に渡る Linux カーネルの解説のうち第2回「プロセス管理・CPU 割り当て」に関する記事です。

その他の Linux カーネルの解説については以下の記事をご覧ください。

スポンサーリンク

プロセスとは

プロセスとは、メインメモリにロードされた実行中のプログラムのことです。

メインメモリについて詳細を知りたい方は以下の記事をご覧ください。

プロセスのメモリセグメント

プロセスの持つそれぞれのデータは、次のセグメント(分類)でメインメモリ配置されます。

5つの各セグメントには、次のようなデータが配置されます。

  • テキスト: CPU が実行する命令
  • データ: 初期化済みの static 変数 or グローバル変数
  • bss: 初期化していない static 変数 or グローバル変数
  • ヒープ: プロセス実行時に動的に確保される領域(malloc 等)
  • スタック: ローカル変数、関数パラメータ、メソッド等。スコープが終了すると消えるデータ
スポンサーリンク

プロセス管理とは

プロセス管理は、いつ、どのプロセスにどれぐらいの時間 CPU を割り当てるか管理することです。

なぜプロセス管理をする必要があるか

基本的には1つの CPU は、メモリにロードされた1つのプロセスしか処理できません。そのため、1つのプロセスが CPU を独占してしまうと他の処理ができなくなります。

例えば、音楽を再生するプロセスと、インターネットを閲覧するプロセスが並行に実行できなくなります。

そこで、一定時間が経過すると CPU の処理するプロセスを切り替えることで1つのプロセスによる CPU の独占を防ぎ、複数のプロセスを並行して実行可能となります。

これにより音楽再生とインターネットの閲覧が平行して実行できます。

【補足】プロセスを並列処理するには

プロセスを CPU で処理する際に、並行では無く並列に処理する方法は以下の3つが存在します。

  • マルチ CPU: 複数の CPU を使います。
  • マルチコア: 1つの CPU に複数のコアが存在します。
  • ハイパースレッド:1つのコアを複数のコアに見せかけることで、1つのコアに複数のプロセスを割り当てます。

利用している CPU は以下のコマンドで確認可能です。

lscpu
CPU:                                 2 //論理 CPU の(プロセスを割り当て可能な)数です
オンラインになっている CPU のリスト: 0,1
コアあたりのスレッド数:              2 //ハイパースレッディングによる見せかけのコア数です
ソケットあたりのコア数:              1 //1CPUに含まれるコア数です
ソケット数:                          1 //物理 CPU (実際の CPU)の数です
スポンサーリンク

プロセスのライフサイクル

プロセスのライフサイクルは以下のとおりであり、プロセスは5つのステートをもつ。

  • 開始:初期化するためのステート。「実行可能」ステートに移行
  • 実行可能:CPU の割り当てを待つためのステート。「実行中」のプロセスが他のプロセスに割り込まれて中断した場合にもこのステートとなります
  • 実行中:プロセスに CPU を割り当てた(ディスパッチした)ステート
  • 待機:デバイスの I/O (SSD 等のデータ読み書きの処理)待ちで CPU の処理が必要ない場合のステート。I/O 処理が終わると「実行完了」ステートに移行します
  • 終了:プロセスの処理が完了・中止した場合はこのステートとなります

PCB(Process Control Block)

ステートを含むプロセスに関する情報は以下の PCB と呼ばれるデータ構造で管理します。

各項目の意味は以下のとおりです。他にも色々あります。

  • Process ID: プロセスを一意に識別する番号です。(PID)
  • State: プロセスのライフサイクルのうち、現在どのステートになのかを表します
  • Pointer: 親プロセスのポインタ
  • Priority: プロセスの優先度
  • Program Counter: 次に実行する命令のポインタ
  • CPU registers: 実行中ステートのプロセスのレジスタの値(?)
  • I/O Information: プロセスに割り当てられた I/O デバイスのリスト
  • Accounting information:プロセスの実行に使用されるCPUの量、時間制限、実行ID

プロセススケジューラー

プロセススケジューラーは、CPU に割り当てるプロセスをスケジュールするものです。

プロセススケジューラーは「ディスパッチ」と「割り込み」によってプロセスのライフサイクルのステートを以下のように変更します。

  • ディスパッチ:プロセスのライフサイクルのステートを「実行可能」から「実行中」に変更
  • 割り込み: プロセスのライフサイクルのステートを「実行中」から「実行可能」に変更

割り込みにより、処理を中断した場合は、PCB に再開時に実行する命令のプログラムカウンタやレジスタの値を保存します。この中断処理や再開処理をコンテキストスイッチと言います。

プロセススケジューラーが CPU の割り当てを決定する際に利用するスケジューリングアルゴリズムには、主に以下の4つが存在します。

  • First Come First Serve (FCFS)
  • Shortest Job Next (SJN)
  • Priority Based Scheduling
  • Round Robin Scheduling

First Come First Serve (FCFS)

FCFS は以下の特徴を持ちます。

  • 先着順でプロセスを実行
  • FIFO(First In First Out) キューにて実装
  • non-preemptive(割り込み不可能)
  • 平均待ち時間が長い
https://www.tutorialspoint.com/operating_system/os_process_scheduling_algorithms.htm

平均待ち時間: (0+4+6+13) / 4 = 5.75

Shortest Job Next (SJN)

SJN は以下の特徴を持ちます。

  • 処理時間が短いプロセスから CPU を割り当てます
  • 平均待ち時間を最小に抑えるためのアルゴリズム
  • non-preemptive(割り込み不可能)
  • CPU 処理時間を事前に知っている(もしくは計算する)必要があります
ProcessArrival TimeExecution TimeService Time
P0050
P1135
P22814
P3368

平均待ち時間: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

Priority Based Scheduling

Priority Based Scheduling は以下の特徴を持ちます。

  • 優先度の高いプロセスから実行されます
  • 同じ優先度のプロセスは先着順です
  • 優先度は、メモリ要件、時間要件等に基づいて決定します

なお、プロセスの優先度は以下のコマンドの結果の PRI 列で確認可能です。(低いほうが優先度が高い)

ps alx
F   UID   PID  PPID PRI  NI    VSZ   RSS WCHAN  STAT TTY        TIME COMMAND
1     0     2     0  20   0      0     0 -      S    ?          0:01 [kthreadd]
1     0     4     2   0 -20      0     0 -      I<   ?          0:00 [kworker/0:0H]

PRI は NI(nice 値)を元に決定するため、nice コマンドにてプロセスの優先度を変更可能です。

ProcessArrival TimeExecution TimePriorityService Time
P00510
P113211
P228114
P33635

平均待ち時間: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6

Round Robin Scheduling

Round Robin Scheduling は以下の特徴を持ちます。

  • 各プロセスはクオンタム(CPU を割り当てる固定時間)を持つ
  • preemptive(割り込みが発生する)ため、プロセスが並行して動作可能
  • クオンタムの期間が終了すると、割り込みが発生し次のプロセスに処理が移る

クオンタムが3だとすると、3経過ごとにプロセスが切り替わる。

平均待ち時間: (9+2+12+11) / 4 = 8.5

最後に

Linux カーネル「プロセス管理・CPU割り当て」に関する説明は以上となります。

その他の Linux カーネルの機能について知りたい場合は以下の記事をどうぞ。

参考書籍

以下の書籍を参考にしました。

参考サイト

以下のサイトを参考にしました。

Operating System - Processes - Tutorialspoint
Operating System - Processes - A process is basically a program in execution. The execution of a process must progress in a sequential fashion.
0

コメント