Load Average はどうやって算出されているのか

これは TECHSCORE Advent Calendar 2017 の8日目の記事です。

今回は、Load Average は単純に平均をとっているわけではないよ、という話をします。

はじめに

バッチサーバのように、ある時間帯だけ一定の CPU 負荷がかかるようなサーバを運用していると、Load Average のグラフがこんな形になるのをよく見かけます。

このグラフは CentOS 6 (Kernel 2.6.32-696.16.1.el6.x86_64) のサーバで 11:05 から 12:00 までの間、CPU 1コア占有する負荷をかけたときのものです。3本の折れ線グラフはそれぞれ過去 1, 5, 15分間の平均負荷です。平均をとる期間が長くなるほどグラフの立ち上がり・立ち下がりが緩やかになる様子が見てとれます。

次のグラフは 11:00 から 11:30 までを拡大したものです。

5分平均のグラフに着目してみましょう。過去 5分間の単純な平均であれば、負荷をかけはじめてから5分経過した 11:10 には Load Average が 1.00 に逹っしていてもよいはずですが、実際は 0.64 でした。どうしてこのようなグラフになるでしょうか？

それは、Load Average が単純な平均ではないからです。

それでは、どのようにして Load Average を算出しているのか見ていきましょう。
以下、引用しているソースコードは CentOS 6 の kernel-2.6.32-696.16.1.el6 のものです。

Load とは

Linux の Load は、

TASK_RUNNING 状態（CPU 上で実行中、あるいは実行可能で CPU の割り当てを待っている状態）
TASK_UNINTERRUPTIBLE 状態（ディスクI/O などで割り込み不可の待ち状態）

のいずれかの状態にあるプロセスの個数です。（以下、このようなプロセスのことを「Active なプロセス」と書くことにします。）
このあたりは多くのブログ記事で解説されているので、ここでは深入りしません。

ところで、Load に TASK_UNINTERRUPTIBLE も含めるのは Linux に特有の定義だそうです。どうしてそうするようになったのかは、Brendan Gregg のブログ記事「Linux Load Averages: Solving the Mystery」に書かれています。英語ですが非常に面白い記事ですので興味のある方は是非読んでみてください。

Load Average の算出

calc_global_load 関数

Load Average は kernel/sched.c 内の calc_global_load 関数で更新されています。

void calc_global_load(void)
{
        unsigned long upd = calc_load_update + 10;
        long active;

        if (time_before(jiffies, upd))
                return;

        active = atomic_long_read(&calc_load_tasks);
        active = active > 0 ? active * FIXED_1 : 0;

        avenrun[0] = calc_load(avenrun[0], EXP_1, active);
        avenrun[1] = calc_load(avenrun[1], EXP_5, active);
        avenrun[2] = calc_load(avenrun[2], EXP_15, active);

        calc_load_update += LOAD_FREQ;
}

void calc_global_load(void)

{

unsigned long upd = calc_load_update + 10;

long active;

if (time_before(jiffies, upd))

return;

active = atomic_long_read(&calc_load_tasks);

active = active > 0 ? active * FIXED_1 : 0;

avenrun[0] = calc_load(avenrun[0], EXP_1, active);

avenrun[1] = calc_load(avenrun[1], EXP_5, active);

avenrun[2] = calc_load(avenrun[2], EXP_15, active);

calc_load_update += LOAD_FREQ;

}

Active なプロセス数は calc_load_tasks 変数で管理されており、9行目で atomic に読み出して active に代入しています。このようにまどろっこしい処理になっているのは、マルチコアで動作させるためです。
Load Average は avenrun[] に保持されています。これは要素数 3 の配列で、それぞれ 1, 5, 15分間の平均値を格納しています。
実際の計算は 12〜14行目で呼び出される calc_load 関数内で行なわれています。どうやら、Load Average は

前回の Load Average
平均をとる期間ごとに定められた定数（EXP_1, EXP_5, EXP_15）
現在の Active なプロセス数

から算出されるようです。

Load Average の算出で利用される定数

FIXED_1, EXP_1 などの定数は include/linux/sched.h で定義されています。

#define FSHIFT          11              /* nr of bits of precision */
#define FIXED_1         (1<<FSHIFT)     /* 1.0 as fixed-point */
#define LOAD_FREQ       (5*HZ+1)        /* 5 sec intervals */
#define EXP_1           1884            /* 1/exp(5sec/1min) as fixed-point */
#define EXP_5           2014            /* 1/exp(5sec/5min) */
#define EXP_15          2037            /* 1/exp(5sec/15min) */

#define FSHIFT 11 /* nr of bits of precision */

#define FIXED_1 (1<<FSHIFT) /* 1.0 as fixed-point */

#define LOAD_FREQ (5*HZ+1) /* 5 sec intervals */

#define EXP_1 1884 /* 1/exp(5sec/1min) as fixed-point */

#define EXP_5 2014 /* 1/exp(5sec/5min) */

#define EXP_15 2037 /* 1/exp(5sec/15min) */

calc_load 関数の処理を追いかけていく前に、これら定数の意味を押さえておきましょう。

Load Average を算出する際、数値を 11 ビット左にシフトさせた固定小数点数を使っています。FSHIFT はこのシフトさせるビット数(＝小数部の精度)です。FIXED_1 はこの固定小数点演算における 1 を意味しており、値は 2048 (1<<11) です。
calc_global_load 関数の 10行目

active = active > 0 ? active * FIXED_1 : 0;

1	active = active > 0 ? active * FIXED_1 : 0;

は、active が正のときに FIXED_1 をかけることによって、固定小数点数に変換しています。

LOAD_FREQ は Load Average を更新する間隔で、その値は 5秒に相当します。(正確には 5秒 + 1 Tick なのですが、この 1 Tick の由来については割愛します。）確かに、uptime コマンドを連続して実行してみると 5秒毎に値が更新されていきます。

EXP_1, EXP_5, EXP_15 はそれぞれ e^-5/60, e^-5/300, e^-5/900 （e はネイピア数で値は 2.71828...) を固定小数点数として表現したものです。e の肩に乗っている指数は、LOAD_FREQ に -1 をかけて、平均をとる期間で割ったものです。具体例として EXP_1 の値を計算してみましょう。e^-5/60 の値はおよそ 0.92004 です。これに FIXED_1 (2048) をかけて 1884.3、小数部分を四捨五入して 1884 が得られます。

これで各定数の意味が把握できました。それでは、calc_load 関数を見てみましょう。

calc_load 関数

calc_load 関数も kernel/sched.c で定義されています。

static unsigned long
calc_load(unsigned long load, unsigned long exp, unsigned long active)
{
        load *= exp;
        load += active * (FIXED_1 - exp);
        return load >> FSHIFT;
}

static unsigned long

calc_load(unsigned long load, unsigned long exp, unsigned long active)

{

load *= exp;

load += active * (FIXED_1 - exp);

return load >> FSHIFT;

}

load には前回の Load Average が、exp には平均をとる期間に応じて EXP_1, EXP_5, EXP_15 のいずれかが、active には Active なプロセス数がそれぞれ固定小数点数で渡されます。関数内の式を1行にまとめると

(load * exp + active * (FIXED_1 - exp)) >> FSHIFT

となります。これを通常の演算に焼き直すと次の式で表わすことができます。

(前回の Load Average) * e^-5/T + (現在の Active なプロセス数) * (1 - e^-5/T)
T: 平均をとる期間の秒数

この式は、指数移動平均の計算式と同じ構造をしています。
Wikipedia の解説文中の計算式の平滑係数 α を (1 - e^-5/T) としたものに相当します。

実はこれ、平均をとる期間（1, 5, 15分）で 1/e に減衰する指数関数で過去データを重み付けして平均をとるのと同じ意味になります。例えば、5分で 1/e に減衰する指数関数は下図のような曲線を描きます。横軸は経過時間です。

理論的には過去の全期間について平均をとっていることになるのですが、1/e に減衰するまでの間（上のグラフの網掛け部分）の寄与が大きな割合を占めるので、便宜的にその期間における平均と呼んでいます。指数関数の特殊な性質のおかげで、前回の平均値と今回の値だけからこの平均値を算出できます。

また、このようにして Load Average を算出していることから、最初にお見せしたグラフの立ち上がり部分の曲線が

1 - e^-t/T

となることが導けます。T は平均をとる期間、t は負荷をかけ始めてからの経過時間です。
5分平均の 5分後の値は 1 - e^-300/300 = 1 - e^-1 = 1 - 0.368 = 0.632 となります。これは実測値の 0.64 とほぼ一致します。

まとめ

Load Average は指数移動平均で算出されており、その重みは平均をとる期間（1, 5, 15分）で 1/e に減衰する指数関数になっていることが分かりました。その算出の過程で必要になるデータは前の Load Average の値と現在の Active なプロセス数だけであることも分かりました。また、計算の高速化のために固定小数点演算をしていることも見ました。

実は、Load Average を算出するコードはいまだに改良が続けられており、2010年と 2016年にちょっとした変更が加えられています。そのため、CentOS 7 の Load Average には小さなバグがあります。次の機会にはそのあたりのことを書きたいと思います。