はじめに
本書の主な対象読者はlinuxを含むOSのプロセススケジューラについて聞いたことがない人や、名前は知っているけど具体的に何をするものかをよく知らない人です。
linux kernelは複数プロセスを同時に動作させる(正確にはさせているように見せかける)ためのプロセススケジューラという機能を持っています。といっても、みなさんがlinuxシステムを使う場合は通常プロセススケジューラを意識しないで済むようになっています。では、あえて意識したい場合、どのような機能なのかを知ってみたい場合はどうすればよいのでしょうか。
kernel機能(ここではプロセススケジューラ)の挙動を明らかにするには、ソースを読む、色々ソース改変しながら動かしてみる1、などが有効です。しかし、ここでは一切ソースを読まずに、ユーザプロセスを使う実験のみによってカーネルの挙動を観測してみます。これは、まるで神様2の作った宇宙の仕組みを解き明かそうとする科学実験のようです。
コンピュータに関する本にはスケジューラについて、
- CPU上で同時に動けるプロセスは一つだけ
- 複数プロセスが実行可能な場合、個々のプロセスを適当な長さの時間(タイムスライスと呼びます)ごとにCPU上で順番に動かしている
などという文言が書いていることが多いですが、殆どの人は知らないか、あるいは何となく耳学問として知っているというだけではないでしょうか。本記事では、この文言を仮説とみなして、それが本当かどうかを自作プログラムを使った実験によって検証してみます。実際に「知っている」だけよりも「やって、確認した」ことによって、linux、ひいてはコンピューターシステムについて、より理解が深まると思います。
実験方法
まずは単一CPU上で、ひたすらCPUを使い続けるプロセスを複数個同時に動かし、その統計情報(ある時点でどのプロセスが動作していたか。及び、それぞれの進捗はどれだけか)を採取します。そのデータの分析によって、上述の仮説が正しいかどうかを検証します。
この目的を達成するために、次のような仕様のプログラムを作成します。
以下の引数を持つ
- n: 同時に動かすプロセス数
- total: 動作させる時間(マイクロ秒単位)
- resol: 1データごとの測定間隔(マイクロ秒単位)
n個のプロセスを同時に動作させ、それらが終了したらプログラム全体も終了する
それぞれのプロセスは次のような動作をする
- totalという時間CPUを使い続けた後に終了する
- resolという時間CPUを使うごとに、ID(0から始まるプロセスごとに固有の数値)、プログラム開始時点からの経過時間(マイクロ秒単位)、進捗(0〜1)を記録する
- 終了時に上記の統計情報を出力する
プログラムのソース
本記事で使用するソースはgithub上に置いています。
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/mman.h>
#include <sys/time.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <err.h>
#define NLOOP_FOR_ESTIMATION 10000000000L
static inline long diff_usec(struct timeval before, struct timeval after)
{
return (after.tv_sec * 1000000L + after.tv_usec)
- (before.tv_sec * 1000000L + before.tv_usec);
}
static double loops_per_usec()
{
long i;
struct timeval before, after;
if (gettimeofday(&before, NULL) == -1)
err(EXIT_FAILURE, "gettimeofday(before) failed");
for (i = 0; i < NLOOP_FOR_ESTIMATION; i++)
;
if (gettimeofday(&after, NULL) == -1)
err(EXIT_FAILURE, "gettimeofday(after) failed");
return NLOOP_FOR_ESTIMATION / diff_usec(before, after);
}
static inline void load(int nloop)
{
int i;
for (i = 0; i < nloop; i++)
;
}
static void child_fn(pid_t id, struct timeval *buf, int nrecord, int nloop_per_resol, struct timeval start)
__attribute__ ((noreturn));
static void child_fn(pid_t id, struct timeval *buf, int nrecord, int nloop_per_resol, struct timeval start)
{
int i;
for (i = 0; i < nrecord; i++) {
load(nloop_per_resol);
struct timeval tv;
if (gettimeofday(&tv, NULL) == -1)
err(EXIT_FAILURE, "gettimeofday() failed");
buf[i] = tv;
}
for (i = 0; i < nrecord; i++) {
printf("%d,%ld,%f\n", id, diff_usec(start, buf[i]), (double)(i+1)/nrecord);
}
exit(EXIT_SUCCESS);
}
static void parent_fn(int nproc)
{
int i;
for (i = 0; i < nproc; i++)
wait(NULL);
}
static struct timeval **logbuf;
static pid_t *pids;
int main(int argc, char *argv[])
{
int ret = EXIT_FAILURE;
if (argc < 4) {
fprintf(stderr, "usage: %s <nproc> <total[us]> <resolution[us]>\n", argv[0]);
exit(EXIT_FAILURE);
}
int nproc = atoi(argv[1]);
int total = atoi(argv[2]);
int resol = atoi(argv[3]);
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;
long pagesize = sysconf(_SC_PAGESIZE);
if (pagesize < 0)
err(EXIT_FAILURE, "sysconf() failed");
logbuf = malloc(nproc * sizeof(struct timeval *));
if (logbuf == NULL)
err(EXIT_FAILURE, "malloc(logbuf) failed");
int i, nallocated;
for (i = 0, nallocated = 0; i < nproc; i++) {
int ret_pma = posix_memalign((void **)&logbuf[i], pagesize, nrecord * sizeof(struct timeval));
if (ret_pma) {
errno = ret;
warn("posix_memalign() failed");
goto free_logbuf;
}
nallocated++;
if (mlock(logbuf[i], nrecord * sizeof(struct timeval))) {
warn("mlock() failed");
goto free_logbuf;
}
}
int nloop_per_resol = (int)(loops_per_usec() * resol);
pids = malloc(nproc * sizeof(pid_t));
if (pids == NULL) {
warn("malloc(pids) failed");
goto free_logbuf;
}
struct timeval start;
if (gettimeofday(&start, NULL) == -1) {
warn("gettimeofday(start) failed");
goto free_logbuf;
}
int ncreated;
for (i = 0, ncreated = 0; i < nproc; i++, ncreated++) {
pids[i] = fork();
if (pids[i] < 0) {
goto wait_children;
} else if (pids[i] == 0) {
// children
child_fn(i, logbuf[i], 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(pids[i], SIGINT) < 0)
warn("kill() failed");
for (i = 0; i < ncreated; i++)
if (wait(NULL) < 0)
warn("wait() failed.");
free_pids:
free(pids);
free_logbuf:
for (i = 0; i < nallocated; i++)
free(logbuf[i]);
free(logbuf);
exit(ret);
}
素直に仕様通りに実装したため、それほど難しいことはしていません。気になるかたのためにポイントをいつくか説明しておきます。
- mlock(2)によってデータを記録するバッファ(logbuf[])の物理メモリ上への貼り付けを強制し(物理メモリ上にlockし)、ページフォールトによる測定誤差を無くしています。
- ユーザ空間からカーネル空間への状態遷移無しに時間を測定できるgettimeofday(2)を用いることによって測定誤差を減らしています。他にもCPUのrdtsc命令などによってさらに誤差を減らすこともできますが、ここでは割愛
- loops_per_usec()では、1マイクロ秒CPUを使うのに必要なループの数を推定しています。適当な数(NLOOP_FOR_ESTIMATION)だけ何もしないループを回すのに要した所要時間を測定し、ループ数をその時間で割ることによって求めます。
なお、本記事はプログラムの実装について学ぶのが主目的ではないので、わからなくても気にする必要はありません。
今回は4CPU(正確には1CPU4コア)環境において、CPU3上でプログラムを同時に1〜4個動作させてみます。個々のプロセスごとに100msだけCPUを使います。その間のデータ測定の間隔は1msです。これを実現するためのスクリプトは次の通りです。
#!/bin/bash
NCPU=$(grep -c processor /proc/cpuinfo)
LASTCPU=$(($NCPU - 1))
PATTERN="1 2 3 4"
TOTAL_US=100000
RESOL_US=1000
for i in ${PATTERN} ; do
taskset --cpu-list ${LASTCPU} ./sched $i ${TOTAL_US} ${RESOL_US} >$i.txt
done
あとは make sched && ./captureによって結果が得られます。以下、注意点を示します。
- makeの際に最適化オプションを付けてしまうと、loops_per_sec()やload()の中のループ処理が、意味の無い処理として削除されてしまうことがあります。これらの処理は、人間から見ると「所定の時間だけCPUを使う」という意味のある処理なのですが、コンパイラからすると「論理的に意味の無い、無くても良い処理」とみなされる恐れがあるということです。このため、最適化はしないでください。
- 上記プログラムの実行中は測定誤差を避けるために、なるべく他のプロセスを実行しないでください3。
実験環境
- ハードウェア
- CPU: Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz x 1 (4 core 1 thread)
- RAM: 8GB
ソフトウェア
OS: 2017/2/2 時点での最新の Debian GNU/Linux stretch
- kernel: 4.8.0-1-amd64
測定結果
私の環境で得られた結果をもとにグラフを作成しました。並列度1〜4のそれぞれについて、
CPU上で動作中のプロセス
x軸: 開始時点からの経過時間[us]
y軸: はプロセスの番号(0〜3)
各プロセスの進捗
x軸: 上記グラフと同じ
- y軸: 進捗(0が何もしていない状態。1が完了状態。単調増加する)
という2つのグラフを描きました。筆者がグラフ作りに不慣れなために見た目がダサいですが、そこはご容赦。
プロセス数1
CPU上で動作中のプロセス
ただ一つ存在するp0が常に動作しています。total引数で指定した通り、およそ100ms後に全ての処理が終わります。これについては、仕事量見積もりの誤差やデータ測定のオーバーヘッドなどの理由によって、ちょうど100ms後にするのはなかなか難しいですが、頑張ればこの誤差はある程度は減らせます。興味のあるかたは後述の参考資料をごらんください。
各プロセスの進捗
p0以外に動作中のプロセスはいないため、進捗は単純に経過時間に比例します。
プロセス数2
CPU上で動作中のプロセス
p0, p1が交互にCPUを使っていることがわかります。全プロセスが同じ長さのタイムスライスを持っていると推測できます。処理完了までの経過時間はプロセス数1の場合のおよそ2倍です。それぞれのプロセスは単一CPUの計算能力を半分づつしか使えないので、これは当然の話です。
各プロセスの進捗
それぞれ自分がCPUを使っている間だけ処理が進捗し、それ以外、つまりCPU上で別のプロセスが動作している間は進捗がありません(グラフ上ではx軸にほぼ平行な線として現れる)。これは1つ上のグラフからなんとなく推測できることです。
また、ややカクカクしていますが、大まかに見るとp0, p1とも、プロセス数1の場合の線の傾きを半分にした直線に似た線になります。仮にそれぞれのプロセスがCPUを使えていない時間が気にならない、気づかない(数mmなどというのは人間にとって非常に小さな時間です)というのであれば、人間には二つのプロセスが同時に動いているように錯覚させられます。
プロセス数3
CPU上で動作中のプロセス
プロセス数2の場合と傾向は同じです。p0->p2->p1の順番にCPU実行権が遷移しています。タイムスライスはプロセス数2の場合に比べて短くなっているようです(これは生データの分析によってわかります)。終了までの経過時間は1プロセスの場合の約3倍です。
各プロセスの進捗
3プロセスになっても2プロセスの場合と傾向は同じです。
プロセス数4
CPU上で動作中のプロセス
これも他の場合と傾向は同じです。p0->p2->p1->p3の順にCPU実行権が遷移しています。タイムスライスはプロセス数3の場合に比べて、さらに短くなっているようです。終了までの経過時間はプロセス数1の場合の約4倍です。
各プロセスの進捗
これも他のものと傾向が同じです。
考察
実験結果から次のようなことがことがわかりました。
- 同時に何個のプロセスが実行可能状態で存在しようとも、1CPU上である瞬間に動作できるプロセスは1つだけ
- 複数プロセスの間でラウンドロビン形式でCPU実行権が移ってゆく
- タイムスライスはプロセス数が増加するほど減少する
スケジューラになじみのないかたがたにとっては、なかなかおもしろいデータだったのではないでしょうか。是非ご自分の環境でも試してみて下さい。さきほども言いましたが、人がやっているのを見るのと自分でやってみるのでは全然理解の深さが変わってきます。
終わりに
本書で実施したことに加えて、次のようなことをするとまた新たな面白い情報が得られます。興味のあるかたは挑戦してみてください。
- プロセス数に応じてタイムスライスがどのように変わるかの法則を明らかにする
- resolの値をタイムスライスより大きな値に増やしてみる
- 複数CPUで実行する: たとえば本記事で使用したtaskset(1)の--cpu-listオプションが使えます。例えば--cpu-list 2,3とすると、プロセスがCPU2,3のどちらかの上でのみ実行できるようになります。また、この場合にはresol毎の情報採取時に、sched_getcpu(3)を用いてプロセスが動作中のCPUの情報を追加採取するとよいでしょう
- nice値を変えたプロセスを動かしてみる
- リアルタイムプロセスで同じことをしてみる: chrt(1)コマンドが使えます
- CPUを使い続けるだけではなく、nanosleep(2)などによってスリープ処理を入れてみる
当初はこれらについては記事に盛り込むつもりでしたが、本記事を書くのが意外と大変だったため、力尽きました。続きは参考資料に挙げた「[試して理解]Linuxのしくみ ~実験と図解で学ぶOSとハードウェアの基礎知識」に書きました。
実はlinuxのプロセススケジューラはv2.6.23から大規模な書き直しをされており、このバージョン前後で挙動がかなり異なっています。たとえば本記事の実験においてタイムスライスはプロセス数に応じて減少しましたが、古いスケジューラでは別の挙動をします。興味のあるかたは、本記事で使用したプログラムを、古いスケジューラを採用するカーネル(v2.6.22以前。CentOSでいうと5.x以前が使用)で実行して結果を比較してみるのもよいと思います。
最後にもう一点だけ。ユーザ空間からだけでなくカーネルのスケジューラのソースも見ると神様の視点から直接カーネルの内部がわかって楽しいですよ。そこには観測したデータではなく、事実が直接書いています。ようこそカーネルの世界へ。
参考資料
- タスクスケジューラ用のsysctlパラメタ: スケジューラに関するsysctlパラメタに加えてスケジューラそのものの挙動についても少し説明しています
- Linux スケジューラーのコア実装とシステムコール: スケジューラのソースについての解説記事
- RHEL7のパフォーマンスチューニングガイドに記載の推奨設定: 本書に記載したような測定プログラムの精度を下げる敵である外乱(割り込み処理や測定用プロセス以外のプロセス)を減らすための方法について記載しています
- [試して理解]Linuxのしくみ ~実験と図解で学ぶOSとハードウェアの基礎知識: プロセススケジューラの章において、複数CPU環境におけるスケジューリングの実験など、本記事の内容をさらに突っ込んだとことを説明しています
