Hatena::ブログ(Diary)

naoyaのはてなダイアリー

February 22, 2007

負荷とは何か

調べごとをしたので blog に書いて理解を深めようのコーナーです。長文です。

Linux でシステム負荷を見る場合にお世話になるのが top や sar (sysstat パッケージに同梱されてるコマンド) などのツールです。

top ではシステム統計のスナップショットを見ることができます。今システムがどういう状態かなーというときは top が便利。

top - 08:16:54 up 3 days, 14:43,  6 users,  load average: 0.18, 0.07, 0.03
Tasks:  43 total,   2 running,  41 sleeping,   0 stopped,   0 zombie
Cpu(s): 18.2% us,  0.0% sy,  0.0% ni, 81.8% id,  0.0% wa,  0.0% hi,  0.0% si

一方の sar では10分ごとのシステム統計を時間を遡ってみたりという目的で使うことができます。昨日の夜はどういう状況だったか調べる、みたいなときに sar が便利です。

% sar -u | head
Linux 2.6.14-1.1656_FC4smp (kurio.hatena.ne.jp)         02/22/07

00:00:01          CPU     %user     %nice   %system   %iowait     %idle
00:10:01          all     11.70      0.00      0.94      0.35     87.00
00:20:01          all      8.88      0.00      0.71      0.38     90.02
00:30:01          all      1.16      0.00      0.40      0.39     98.05
00:40:01          all      8.71      0.00      0.59      0.35     90.35

% sar -q | head -7
Linux 2.6.14-1.1656_FC4smp (kurio.hatena.ne.jp)         02/22/07

00:00:01      runq-sz  plist-sz   ldavg-1   ldavg-5  ldavg-15
00:10:01            1       170      0.00      0.08      0.10
00:20:01            2       168      0.08      0.16      0.12
00:30:01            3       171      0.00      0.02      0.05
00:40:01            2       169      0.00      0.05      0.08

top や sar ではシステム負荷を計測する指標としてCPU使用率とロードアベレージの数値を見ることができます。どちらも負荷を表す数字ですが、少し性格が異なります。

  • ロードアベレージは過去1分、5分、15分の間の実行待ちプロセス数の平均数 = 実行したくても他のプロセスが実行中で実行できないプロセスが平均で何個ぐらい存在してるか
  • CPU使用率は、文字の通り CPU が度の程度利用されている/いたかの割合

となります。

ロードアベレージの方にはシステムがページアウトして辛い状況などもそれが数値になって表れます。つまり、メモリが不足しているであるとか、ディスクの読み書きに時間がかかっているといったシステムの色々な状況を総括して数値に反映したものと見ることができます。

一方のCPU使用率の方には純粋に CPU の使用率が表示されています。ですので、

  • "負荷が高い"というときにロードアベレージを見て数字が高い
  • CPU 使用率を見たところ idle は結構ある
  • のでボトルネックは CPU ではなく他が考えられる
  • vmstat でメモリの利用状況をみたらページアウトしまくってる
  • 搭載メモリが足りないよ

といった感じでそれぞれの数値を使い分けて分析していくことで、どこが原因なのかを特定することができます。

さて、ロードアベレージとCPU使用率という数字ですが、それぞれどうやって数値化されているのでしょう。OS (カーネル)がその情報を収集しているのであろうことは想像がつきますが、具体的にそれぞれどういう基準で数値化されてるかというのは自明ではありません。と、いうことが気になったのでカーネルの中を覗いてみました。

まずはロードアベレージ。

Linux がロードアベレージを計算する処理を起動するタイミングは、ハードウェアタイマの割り込み時になります。例えば PC/AT 互換機の場合は PIT (Programmable Interval Timer) というデバイスがあって、これが周期的にタイマー割り込みを発生させます。(PIT が発生させるタイマ割り込みはシステムの時刻を進めるためなどに使われます。一方、マルチプロセッサの場合に CPU が複数あって、それぞれにタイマ割り込みが必要になったとき、その割り込みを発生させるのはプロセッサ固有のローカルAPIC です。前者を"グローバルタイマ割り込み"、後者を"ローカルタイマ割り込みと呼ぶそう。")

グローバルタイマ割り込みは割り込みコントローラの APIC (Advanced Programmable Interrupt Controller) によって CPU (のローカルAPIC)に転送され、割り込み要求を発生させます。この割り込み要求をトリガにして、カーネルのグローバルタイマ用割り込みハンドラが起動します。

このグローバルタイマ割り込みに対する割り込みハンドラから呼ばれる処理は Linux 2.6.20 だと kernel/timer.c の do_timer() に定義されています。(割り込みを受け付けて do_timer() を呼び出すまでの処理のは各アーキテクチャごとのタイマ周りの実装、x86_64 であれば arch/x86_64/kernel/time.c あたりにあります。)

ま、色々書いてますが、要はカーネルの中で do_timer() 関数が定期的に呼び出されて実行されている、ということです。

   1208 void do_timer(unsigned long ticks)
   1209 {
   1210         jiffies_64 += ticks;
   1211         update_times(ticks);
   1212 }

do_timer() からは続けて update_times() が呼ばれています。

   1196 static inline void update_times(unsigned long ticks)
   1197 {
   1198         update_wall_time();
   1199         calc_load(ticks);
   1200 }

この update_times() に calc_load() があって、これがロードアベレージの計算をする関数です。ハードウェアタイマ割り込み毎にロードアベレージを計算して値を更新しているのが分かります。calc_load() の中身は以下になります。

   1144 static inline void calc_load(unsigned long ticks)
   1145 {
   1146         unsigned long active_tasks; /* fixed-point */
   1147         static int count = LOAD_FREQ;
   1148
   1149         count -= ticks;
   1150         if (unlikely(count < 0)) {
   1151                 active_tasks = count_active_tasks();
   1152                 do {
   1153                         CALC_LOAD(avenrun[0], EXP_1, active_tasks);
   1154                         CALC_LOAD(avenrun[1], EXP_5, active_tasks);
   1155                         CALC_LOAD(avenrun[2], EXP_15, active_tasks);
   1156                         count += LOAD_FREQ;
   1157                 } while (count < 0);
   1158         }
   1159 }

count_active_tasks() で、システムでアクティブなタスクの数を取得してそれを CALC_LOAD マクロにかけてロードアベレージを計算、グローバルな配列の avenrun にそれぞれ 1分、5分、15分のロードアベレージ値を保存しています。

だんだんとキモに近づいてきました。実際ロードアベレージの計算に使われている「アクティブなタスク」ってなんだろう、ということで count_active_tasks() の中身を更に追っていくと、kernel/sched.c の nr_active() 関数に到達します。sched.c はプロセススケジューラの実装です。

   1929 unsigned long nr_active(void)
   1930 {
   1931         unsigned long i, running = 0, uninterruptible = 0;
   1932
   1933         for_each_online_cpu(i) {
   1934                 running += cpu_rq(i)->nr_running;
   1935                 uninterruptible += cpu_rq(i)->nr_uninterruptible;
   1936         }
   1937
   1938         if (unlikely((long)uninterruptible < 0))
   1939                 uninterruptible = 0;
   1940
   1941         return running + uninterruptible;
   1942 }

cpu_rq(i) で各CPUに紐付けられたランキュー(実行可能になってCPU割り当てをまっているプロセスがキューイングされている場所) のメンバから nr_running、nr_uninterruptible という二つの数を引っ張りだして足しこんでいます。この nr_running、nr_uninterruptible ですが、いずれも特定の状態のプロセスの数を表す数字です。

Linux のプロセスの実体はカーネル構造体の task_struct 構造体です。この構造体には state というメンバがあって、このメンバを見るといまプロセスがどのような状態にあるかが分かるようになっています。state メンバの主な値は

TASK_RUNNING
実行中もしくは実行可能でCPU割り当てを待っている状態
TASK_INTERRUPTIBLE
割り込み可能な待ち状態。ユーザーからの入力待ちなど比較的時間がかかる事象。
TASK_UNINTERRUPTIBLE
割り込み不可能な待ち状態。ディスクI/O待ちなど短い事象。

などです。(他にもいくつかあります。)

カーネルのスケジューラはプロセスの状態を見ながら CPU に割り当てるプロセスを切り替えていきますが、例えばこのプロセスは I/O 待ちに入ったから TASK_UNINTERRUPTIBLE にして I/O が完了するまで待ち状態にしておき、別のプロセスを TASK_RUNNING で実行可能にして...ということをランキュー(やウェイトキュー)に対してやっているわけです。

ということで、ここまでのコードでこのキューに入れられたプロセスの状態のうち TASK_RUNNING と TASK_UNINTERRUPTIBLE 状態のものの数を数えて単位時間で割って、ロードアベレージの値としている、というのが分かります。今まさに実行可能なプロセスの TASK_RUNNING が含まれるのは想像がつきますが、ディスク I/O 待ちなどのプロセス数もロードアベレージに加えられているというのもポイントではないでしょうか。

ロードアベレージの実装が分かったところで、次は CPU 使用率の実装を見てみます。CPU使用率の統計取得はプロセスアカウンティングなどと呼ばれることからも分かるとおり、個別のプロセスの統計から取っていくようになっています。

ロードアベレージがシステム全体の数字だったのに対して、CPU 使用率はマルチプロセッサ環境では各 CPU ごとに統計が取られています。そのため、kernel/timer.c に定義されているCPU 使用率を計算する関数であるところの update_process_times() は

  • ユニプロセッサの場合はグローバルタイマ割り込みハンドラから呼ばれる do_timer() の直後に呼ばれる
  • マルチプロセッサの場合は CPU 毎に周期的に割り込みを発生させるデバイス(ローカルAPIC)の割り込みハンドラから呼ばれる

となっています。後者は arch/x86_64/kernel/apic.c の smp_local_timer_interrupt() あたりです。

    978 void smp_local_timer_interrupt(void)
    979 {
    980         profile_tick(CPU_PROFILING);
    981 #ifdef CONFIG_SMP
    982         update_process_times(user_mode(get_irq_regs()));
    983 #endif
    984         if (apic_runs_main_timer > 1 && smp_processor_id() == boot_cpu_id)
    985                 main_timer_handler();
    986         /*
    987          * We take the 'long' return path, and there every subsystem
    988          * grabs the appropriate locks (kernel lock/ irq lock).
    989          *
    990          * We might want to decouple profiling from the 'long path',
    991          * and do the profiling totally in assembly.
    992          *
    993          * Currently this isn't too much of an issue (performance wise),
    994          * we can take more than 100K local irqs per second on a 100 MHz P5.
    995          */
    996 }

確かに smp_local_timer_interrupt() から update_process_times() が呼ばれていますね。

update_process_times の中の実装を見る前に、収集された情報が格納される構造体の定義を見ておくと見通しがよさそうです。include/linux/kernel_stat.h の cpu_usage_stat 構造体がそれになります。

     17 struct cpu_usage_stat {
     18         cputime64_t user;
     19         cputime64_t nice;
     20         cputime64_t system;
     21         cputime64_t softirq;
     22         cputime64_t irq;
     23         cputime64_t idle;
     24         cputime64_t iowait;
     25         cputime64_t steal;
     26 };
     27
     28 struct kernel_stat {
     29         struct cpu_usage_stat   cpustat;
     30         unsigned int irqs[NR_IRQS];
     31 };
     32
     33 DECLARE_PER_CPU(struct kernel_stat, kstat);

cpu_usage_stat 構造体のメンバにはユーザーモードの値、システムモードでの値、iowait の値等々があります。この cpu_usage_stat 構造体は kernel_stat 構造体から参照される形で DECLARE_PER_CPU で CPU 毎に一つ用意されます。

さて、話を戻して update_process_times() の中を覗いてみます。kernel/timer.c に定義されています。

   1099 /*
   1100  * Called from the timer interrupt handler to charge one tick to the current
   1101  * process.  user_tick is 1 if the tick is user time, 0 for system.
   1102  */
   1103 void update_process_times(int user_tick)
   1104 {
   1105         struct task_struct *p = current;
   1106         int cpu = smp_processor_id();
   1107
   1108         /* Note: this timer irq context must be accounted for as well. */
   1109         if (user_tick)
   1110                 account_user_time(p, jiffies_to_cputime(1));
   1111         else
   1112                 account_system_time(p, HARDIRQ_OFFSET, jiffies_to_cputime(1));
   1113         run_local_timers();
   1114         if (rcu_pending(cpu))
   1115                 rcu_check_callbacks(cpu, user_tick);
   1116         scheduler_tick();
   1117         run_posix_cpu_timers(p);
   1118 }

1105 行目で current マクロで現在実行されているプロセス(task_struct 構造体)を取得し、そのプロセスに対して account_user_time や account_system_time() などを実行しているのが分かります。この account_* が計算の本体のようですね。

さらに潜っていきます。kernel/sched.c に account_* は定義されています。まずはユーザーモードでのプロセスアカウンティングから見てみます。

   3059 /*
   3060  * Account user cpu time to a process.
   3061  * @p: the process that the cpu time gets accounted to
   3062  * @hardirq_offset: the offset to subtract from hardirq_count()
   3063  * @cputime: the cpu time spent in user space since the last update
   3064  */
   3065 void account_user_time(struct task_struct *p, cputime_t cputime)
   3066 {
   3067         struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
   3068         cputime64_t tmp;
   3069
   3070         p->utime = cputime_add(p->utime, cputime);
   3071
   3072         /* Add user time to cpustat. */
   3073         tmp = cputime_to_cputime64(cputime);
   3074         if (TASK_NICE(p) > 0)
   3075                 cpustat->nice = cputime64_add(cpustat->nice, tmp);
   3076         else
   3077                 cpustat->user = cputime64_add(cpustat->user, tmp);
   3078 }

ここで p は現在実行されているプロセスですね。

  • まず現在実行中のプロセスの utime を増やす。これによりそのプロセスがユーザーモードで使用した時間がそのプロセス内の情報として保存される。 (p->utime = cputime_add(p->utime, cputime))
  • 次に先に見た cpu_usage_stat 構造体 user に、そのプロセスの使用時間を追加する。

つまり現在実行中のプロセスがどの程度 CPU を使ったかを最初に計算して、その値を全体での値にも足しこんでいる、という処理になっています。

システムモードの方も見てみます。

   3080 /*
   3081  * Account system cpu time to a process.
   3082  * @p: the process that the cpu time gets accounted to
   3083  * @hardirq_offset: the offset to subtract from hardirq_count()
   3084  * @cputime: the cpu time spent in kernel space since the last update
   3085  */
   3086 void account_system_time(struct task_struct *p, int hardirq_offset,
   3087                          cputime_t cputime)
   3088 {
   3089         struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
   3090         struct rq *rq = this_rq();
   3091         cputime64_t tmp;
   3092
   3093         p->stime = cputime_add(p->stime, cputime);
   3094
   3095         /* Add system time to cpustat. */
   3096         tmp = cputime_to_cputime64(cputime);
   3097         if (hardirq_count() - hardirq_offset)
   3098                 cpustat->irq = cputime64_add(cpustat->irq, tmp);
   3099         else if (softirq_count())
   3100                 cpustat->softirq = cputime64_add(cpustat->softirq, tmp);
   3101         else if (p != rq->idle)
   3102                 cpustat->system = cputime64_add(cpustat->system, tmp);
   3103         else if (atomic_read(&rq->nr_iowait) > 0)
   3104                 cpustat->iowait = cputime64_add(cpustat->iowait, tmp);
   3105         else
   3106                 cpustat->idle = cputime64_add(cpustat->idle, tmp);
   3107         /* Account for system time used */
   3108         acct_update_integrals(p);
   3109 }

やっていることはほとんど一緒ですが if 分の分岐により、消費した時間が

  • システム時間(カーネルスレッドが計算を行った時間)
  • ハードウェア割り込みに要した時間
  • ソフトウェア割り込みに要した時間
  • IO に要した時間

のいずれだったのかを判定して、足しこみを行っているのが分かります。

と、プロセスアカウンティングのおおまかな処理はこんな感じです。タイマ割り込みを利用してプロセスごとの統計を取ったあと、それを全体の統計に足しこむというのをひたすら繰り返しているわけですね。

ところで、ロードアベレージにしてもプロセスアカウンティングの結果にしても、計算したのはいいとして top や sar などのツールはこれらの値をどうやって参照するかという話があります。これらは /proc ファイルシステムを経由して取得することができます。

  • システム全体の値は /proc/stat
  • プロセス毎の値は /proc/${PID}/stat

にそれぞれあります。

% cat /proc/stat
cpu  4409373 5621 147573 10089174 1293 68 4400 0
cpu0 4409373 5621 147573 10089174 1293 68 4400 0
intr 14838028 14657502 0 180526 0 0 0 0 ...(略)
ctxt 1332839
btime 1171787591
processes 3730
procs_running 2
procs_blocked 0

これらの値を取得して整形して表示することで、普段目にしているロードアベレージや CPU 使用率の値としてみることができるようです。

余談ですが、Linux はカーネル 2.5 から sar などで iowait の統計を見ることができるようになりました。サーバーを運用する上で iowait の統計が見れるというのは重要なのですが、Solaris などの 商用 UNIX では当たり前なこの統計情報が Linux 2.4 では取れなかったようです。

カーネル 2.4.34.1 のプロセスアカウンティングの実装を見てみます。

/*
 * Called from the timer interrupt handler to charge one tick to the current
 * process.  user_tick is 1 if the tick is user time, 0 for system.
 */
void update_process_times(int user_tick)
{
        struct task_struct *p = current;
        int cpu = smp_processor_id(), system = user_tick ^ 1;

        update_one_process(p, user_tick, system, cpu);
        if (p->pid) {
                if (--p->counter <= 0) {
                        p->counter = 0;
                        /*
                         * SCHED_FIFO is priority preemption, so this is
                         * not the place to decide whether to reschedule a
                         * SCHED_FIFO task or not - Bhavesh Davda
                         */
                        if (p->policy != SCHED_FIFO) {
                                p->need_resched = 1;
                        }
                }
                if (p->nice > 0)
                        kstat.per_cpu_nice[cpu] += user_tick;
                else
                        kstat.per_cpu_user[cpu] += user_tick;
                kstat.per_cpu_system[cpu] += system;
        } else if (local_bh_count(cpu) || local_irq_count(cpu) > 1)
                kstat.per_cpu_system[cpu] += system;
}

2.6 のものに比べるとだいぶ単純(?)な内容になっているのがわかります。iowait の計算箇所はどこにもありませんね。

まとめ

サーバー負荷の見極めの鍵になるロードアベレージやCPU使用率が、Linux 上でどのように計算されているのかカーネルのコードを実際に追ってみてみました。

  • ロードアベレージは、タイマ割り込み時に、キューに溜まったプロセスのうち TASK_RUNNING と TASK_UNINTERRUPTIBLE 状態の数を数えて計算している
  • CPU使用時間は各プロセスごとのCPU使用時間をタイマ割り込み時に足しこんでいき、システム全体の値にそれを加算するというので取っている

というのが分かりました。またカーネル 2.4 から 2.6 に進化する過程でプロセスアカウンティングの実装にも変更が加えられて iowait など重要な情報が取れるようになったことも分かりました。

こんな具合でカーネルのコードに潜っていくと、普段目にしている値の本来の意味であるとか、どういうタイミングで更新されているのかという点に理解が深まっていい具合です。

なおソースを読んだり、仕組みを理解するために

Linuxカーネル2.6解読室

Linuxカーネル2.6解読室

に大変お世話になっています。

追記

この辺りの話をまとめて本に書きました。

[24時間365日] サーバ/インフラを支える技術 ?スケーラビリティ、ハイパフォーマンス、省力運用 (WEB+DB PRESS plusシリーズ)

よろしければご一読ください。

lockcolelockcole 2007/02/22 15:28 これは素晴らしいです。勉強になりました。
久しぶりにnaoyaさんの技術ネタ記事が読めて幸せです。

kimata24kimata24 2007/02/24 15:37 面白い記事有り難うございます.勉強になりました.
せっかっっく「負荷とは何か」とつけたのですから(Load average とは何か,ではなく),次回はもっと扱うレイヤの幅を広げたものを期待してます!

てら〜てら〜 2007/05/15 17:35 有用な記事をありがとうございます。

> TASK_RUNNING と TASK_UNINTERRUPTED 状態の数を数えて計算している

TASK_UNINTERRUPTIBLE ですね。
このプロセス状態には具体的にどの状態が含まれるのかは
ドライバコードに依存するのでしょうか?