第4章プロセススケジューラ
Linuxカーネルは、複数プロセスを同時に動作させる（正確には動作させているように見せかける）ための、プロセススケジューラという機能を持っている。
スケジューラの説明
1つのCPU上で同時に処理するプロセスは1つだけ。
複数プロセスが同時可能な場合、個々のプロセスを適当な長さの時間ごとにCPU上で順番に処理する。
マルチコアCPUは、LInuxからは1つのコアが1つのCPUとして認識される。
システムにCPUとして認識されるもの（コア）を論理CPUと言う。
ハイパースレッド機能が有効になっている場合は、各コア内のそれぞれのハイパースレッドが論理CPUとして認識される。
ハイパースレッドは第6章記憶階層
ひたすらCPU時間を使う処理をするプロセスを1つまたは複数個同時に動かし、以下のような統計情報を取得する。
ある時点で、論理CPU上ではどのプロセスが動作しているか。
それぞれの進捗がどれぐらいか。
code:sched.c
#include <sys/types.h>
#include <sys/wait.h>
#include <time.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>
#define NLOOP_FOR_ESTIMATION 1000000000UL
#define NSECS_PER_MSEC 1000000UL
#define NSECS_PER_SEC 1000000000UL
static inline long diff_nsec(struct timespec before, struct timespec after)
{
return ((after.tv_sec * NSECS_PER_SEC + after.tv_nsec)
- (before.tv_sec * NSECS_PER_SEC + before.tv_nsec));
}
static unsigned long loops_per_msec()
{
struct timespec before, after;
clock_gettime(CLOCK_MONOTONIC, &before);
unsigned long i;
for (i = 0; i < NLOOP_FOR_ESTIMATION; i++)
;
clock_gettime(CLOCK_MONOTONIC, &after);
int ret;
return NLOOP_FOR_ESTIMATION * NSECS_PER_MSEC / diff_nsec(before, after);
}
static inline void load(unsigned long nloop)
{
unsigned long i;
for (i = 0; i < nloop; i++)
;
}
static void child_fn(int id, struct timespec *buf, int nrecord, unsigned long nloop_per_resol, struct timespec start)
{
int i;
for (i = 0; i < nrecord; i++) {
struct timespec ts;
load(nloop_per_resol);
clock_gettime(CLOCK_MONOTONIC, &ts);
bufi = ts;
}
for (i = 0; i < nrecord; i++) {
printf("%d\t%ld\t%d\n", id, diff_nsec(start, bufi) / NSECS_PER_MSEC, (i + 1) * 100 / nrecord);
}
exit(EXIT_SUCCESS);
}
static void parent_fn(int nproc)
{
int i;
for (i = 0; i < nproc; i++)
wait(NULL);
}
static pid_t *pids;
int main(int argc, char *argv[])
{
int ret = EXIT_FAILURE;
if (argc < 4) {
fprintf(stderr, "usage: %s <nproc> <totalms> <resolutionms>\n", argv0);
exit(EXIT_FAILURE);
}
int nproc = atoi(argv1);
int total = atoi(argv2);
int resol = atoi(argv3);
if (nproc < 1) {
fprintf(stderr, "<nproc>(%d) should be >= 1\n", nproc);
exit(EXIT_FAILURE);
}
if (total < 1) {
fprintf(stderr, "<total>(%d) should be >= 1\n", total);
exit(EXIT_FAILURE);
}
if (resol < 1) {
fprintf(stderr, "<resol>(%d) should be >= １\n", resol);
exit(EXIT_FAILURE);
}
if (total % resol) {
fprintf(stderr, "<total>(%d) should be multiple of <resolution>(%d)\n", total, resol);
exit(EXIT_FAILURE);
}
int nrecord = total / resol;
struct timespec *logbuf = malloc(nrecord * sizeof(struct timespec));
if (!logbuf)
err(EXIT_FAILURE, "malloc(logbuf) failed");
puts("estimating workload which takes just one milisecond");
unsigned long nloop_per_resol = loops_per_msec() * resol;
puts("end estimation");
fflush(stdout);
pids = malloc(nproc * sizeof(pid_t));
if (pids == NULL) {
warn("malloc(pids) failed");
goto free_logbuf;
}
struct timespec start;
clock_gettime(CLOCK_MONOTONIC, &start);
int i, ncreated;
for (i = 0, ncreated = 0; i < nproc; i++, ncreated++) {
pidsi = fork();
if (pidsi < 0) {
goto wait_children;
} else if (pidsi == 0) {
// children
child_fn(i, logbuf, nrecord, nloop_per_resol, start);
/* shouldn't reach here */
}
}
ret = EXIT_SUCCESS;
// parent
wait_children:
if (ret == EXIT_FAILURE)
for (i = 0; i < ncreated; i++)
if (kill(pidsi, SIGINT) < 0)
warn("kill(%d) failed", pidsi);
for (i = 0; i < ncreated; i++)
if (wait(NULL) < 0)
warn("wait() failed.");
free_pids:
free(pids);
free_logbuf:
free(logbuf);
exit(ret);
}
0番の論理CPUのみで実行
$ taskset -c 0 ./sched <n> <total> <resol>
$ taskset -c 0 ./sched 1 100 1
code:core1
0 1 1
0 2 2
0 3 3
0 4 4
0 6 5
0 7 6
0 8 7
0 9 8
0 10 9
0 11 10
(中略)
0 110 94
0 111 95
0 113 96
0 114 97
0 115 98
0 116 99
0 117 100
ただ1つ存在するプロセス0が常に動作している。
プロセス0以外に動作中のプロセスはないので、進捗は単純に経過時間に比例して増加していく。
$ taskset -c 0 ./sched 2 100 1
code:core2
0 12 1
0 13 2
0 14 3
0 15 4
0 16 5
0 17 6
0 18 7
0 20 8
0 21 9
0 22 10
(中略）
0 227 98
0 228 99
0 229 100
1 1 1
1 2 2
1 3 3
（中略）
1 217 93
1 218 94
1 230 95
1 231 96
1 233 97
1 234 98
1 235 99
1 236 100
2つのプロセスは交互に論理CPUを使う。（=同時に論理CPUを使うことはない）
2つのプロセスは、おおよそ等しいタイムスライス（数ミリ秒）を持つ。
各プロセスは論理CPUを使っている間だけ処理が進捗し、それ以外、つまりCPU上でもう一方のプロセスが動作している間は進捗しない。
単位時間あたりの進捗は、プロセス数=1の場合のおよそ半分、プロセス数=1の場合は1ミリ秒ごとに1%程度、プロセス数=2の場合は1ミリ秒ごとに0.5%程度。
処理完了までの経過時間は、プロセス数=1の場合のおよそ2倍。
$ taskset -c 0 ./sched 4 100 1
code:core4
3 1 1
3 2 2
3 3 3
3 5 4
3 6 5
3 7 6
3 32 7
3 33 8
3 34 9
3 36 10
(中略)
3 452 98
3 453 99
3 455 100
1 17 1
1 18 2
1 19 3
(中略)
1 466 99
1 467 100
0 25 1
2 9 1
2 10 2
(中略)
2 475 99
2 476 100
0 26 2
0 27 3
(中略)
0 470 97
0 472 98
0 473 99
0 474 100
各プロセスが同時に動くことはない。
各プロセスは概ね均等にCPU時間を使っている。
単位時間の進捗はプロセス数=1の場合の約1/4に、終了までの経過時間は約4倍に。
コンテキストスイッチ
論理CPU上で動作するプロセスが切り替わること。
プロセスがいかなるコードを実行中であっても、タイムスライスが切れると発生する。
なので、例えばある処理の完了に想定より多くの時間がかかっていた場合、その処理自体の問題だけではなく、処理中にコンテキストスイッチが発生して他のプロセスが動いた可能性も考えることができる。
プロセスの状態
総プロセス数は以下のコマンドで確認可能。
$ ps ax | wc -l
各プロセスの状態は、以下コマンドの第3フィールドのSTATの最初の一文字で確認できる。
$ ps ax
table:process-state
R 実行状態、あるいは実行待ち状態
SまたはD スリープ状態。シグナルによって実行状態に戻るものがS、そうでないものがD
Z ゾンビ状態
Dの状態のプロセスは通常ミリ秒程度で別の状態に遷移するが、そうならない場合の理由としては
ストレージのI/Oが終了しない状態になっている。
カーネル内で何らかの問題が発生している。
code:ps ax
PID TTY STAT TIME COMMAND
1 ? Ss 0:01 /sbin/init
2 ? S 0:00 kthreadd
4 ? I< 0:00 kworker/0:0H
6 ? I< 0:00 mm_percpu_wq
7 ? S 0:00 ksoftirqd/0
8 ? I 0:00 rcu_sched
9 ? I 0:00 rcu_bh
10 ? S 0:00 migration/0
11 ? S 0:00 watchdog/0
12 ? S 0:00 cpuhp/0
13 ? S 0:00 cpuhp/1
14 ? S 0:00 watchdog/1
15 ? S 0:00 migration/1
(略)
多くはSの状態となっている。
プロセスの状態の種類（一部）
table:process-kind
実行状態 現在論理CPUを使っている。
実行待ち状態 CPU時間が割り当てられるのを待っている
スリープ状態 何らかのイベントが発生するのを待っている。イベント発生までCPU時間は使わない。
ゾンビ状態 プロセスが終了した後に親プロセスが終了状態を受け取るのを待っている。
例として、スリープ状態で待つイベントは以下のようなものがある。
所定時間が経過するのを待つ。
キーボードやマウスなどによるユーザ入力を待つ。
HDDやSSDなどのストレージデバイスへの読み書きの終了を待つ。
ネットワークによるデータ送受信の終了を待つ。
状態遷移
プロセスは生成されてから、生存中に実行状態と実行可能状態、スリープ状態という複数の状態を何度も行き来する。
アイドル状態
何もしない特殊なプロセスの状態。
論理CPU上で一度に実行できるプロセスは1つだけ
スリープ状態においてはCPU時間を使わない
スループットとレイテンシ
スループット
単位時間あたりの総仕事量。高いほど良い。
完了したプロセスの数 / 経過時間
アイドル状態の割合が低いほど高くなる
100ミリ秒の間に40%がアイドル状態の場合、1プロセス/100ミリ秒 = 10プロセス/秒
論理CPUの能力を使い切っている場合、いくらプロセスを増やしてもスループットは変わらない。
レイテンシ
それぞれの処理の開始から終了までの経過時間。短いほど良い。
処理終了時間 - 処理開始時間
プロセスを増やすとレイテンシは悪化する。
各プロセスの平均レイテンシは等しい。
スケジューラがラウンドロビン方式ではない場合、各プロセスのレイテンシに不平等が生じる。
論理CPUが複数の場合のスケジューリング
ロードバランサがプロセスを公平に分配
1つのCPU上で同時に処理できるプロセスは1つだけ。
複数プロセスが実行可能な場合、個々のプロセスを適当な長さの時間ごとにCPU上で順番に処理する。
マルチコアCPU環境では、複数プロセスを同時に動かさないとスループットが上がらない。
単一論理CPU環境の場合と同様に、プロセス数を論理CPU数より多くしてもスループットは上がらない。