ビジーウェイト

ビジーウェイト（Busy Waiting）とは、プロセスが条件が成り立つかどうかを定期的にチェックする手法の一種。例えば、キーボードからの入力を待ったり、ロックが獲得できるのを待ったりするのに使われる。ある時間だけ遅延させて何かを実行するのに使うこともある。

古いコンピュータでは特定の長さの時間だけ待つ方法がなかったため、何もしないループで時間をつぶした。しかし、最近のコンピュータはプロセッサの速度がそれぞれ異なるため、この種の時間遅延は不正確なことが多く、（ビジーウェイトをこの目的で使用しているプログラムは）プログラミングに不慣れなことを示す印でもある。

ビジーウェイトは特定の状況では正当な手法と言える。特にSMPシステム向けのオペレーティングシステム内のスピンロックの実装などがそうである。しかし、一般にはビジーウェイトすべきでない。CPU時間を費やして待つ時間があれば、他のスレッドを動作させるほうが効率的である。

C言語でのコード例

以下は、C言語コードで2つのスレッドがグローバルな整数 i を共有している。1番目のスレッドはビジーウェイトで i の値の変化を待っている。

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

volatile int i; /* i はグローバルであり、全関数から見える。
                   volatile でもあるので、その値の変化はコンパイラからは
                   予測できない（他のスレッドが変更するため）*/

/* t1 は i が 0 以外になることをスピンして待つ */
static void *f1()
{
    while (i==0)
    {
        /* 何もしない - 単にチェックしながら回り続ける */
    } 
    printf("i's value has changed to %d.\n", i);
  
    return;
}

static void *f2()
{
    sleep(60); /* 60秒間スリープ */
    i = 99;
    printf("t2 changing the value of i to %d.\n", i);

    return;
}

int main()
{
    int x;
    pthread_t t1, t2;
    i = 0; /* グローバル整数 i を 0 にする */
 
    x = pthread_create(&t1, NULL, f1, NULL);
    if (x != 0)
    {
        printf("pthread foo failed.\n");
    }
 
    x = pthread_create(&t2, NULL, f2, NULL);
    if (x != 0)
    {
        printf("pthread bar failed.\n");
    }
 
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("all pthreads finished.\n");
    return 0;
}

UNIX系システムでは、次のように上記コードをコンパイルすることができる:

$ cc spinlock.c -lpthread

CPU の利用状況

上記のコードの中で、2番目のスレッドは直ちに60秒間スリープする。その間、最初のスレッドは、2番目のスレッドが i の値を変更したかどうかを繰り返しチェックする。

UNIX系オペレーティングシステムでは、top や uptime といったユーティリティを使用してこのプログラムのCPU利用状況を知ることができる。プログラムを以下のように実行する:

$ uptime; ./a.out ; uptime
13:25:47 up 53 days, 23:50,  4 users,  load average: 0.00, 0.00, 0.00
t2 changing the value of i to 99.
i's value has changed to 99.
all pthreads finished.
13:26:47 up 53 days, 23:51,  4 users,  load average: 0.75, 0.21, 0.07

もちろん、システムによって表示される値は微妙に異なるだろう。しかし重要な点はプログラム実行前にロードアベレージ（システム負荷平均値）が 0.00 だった点である。プログラムを実行すると最近一分間のロードアベレージは 0.75 までに達した。（訳注：ロードアベレージの計算方法は様々だが、少なくとも 1.00 になるとプロセッサ1個が100%動作していることを示す。）

ビジーウェイトの代替手法

代替手法としてシグナルを利用する方法がある。多くのオペレーティングシステムやスレッドライブラリには、1番目のスレッドをスリープさせておいて2番目のスレッドが i の値を変更したときにシグナルでそれを通知する手段を提供している。この技法をイベント駆動型プログラミングと呼び、CPU時間を消費しないため、効率がよい。

ビジーウェイト自体も、何らかの遅延関数を使ってより効率的にすることができる。遅延関数はスレッドを指定された時間だけスリープさせるもので、その間CPU時間を消費することがなくなる。このループが非常に簡単なチェックをするだけなら、ほとんどの時間をスリープしているようにできるのでCPU時間の浪費を大きく減らすことになるが、ある程度のCPU時間は消費してしまう。

ビジーウェイトが適している状況

低レベルのハードウェアドライバのプログラミングでは、ビジーウェイトが実際上望ましいこともある。あらゆるデバイスに割り込みによる通知機能を実装することは現実的ではない（特にアクセスがほとんど発生しないデバイス）。場合によっては制御データをデバイスに書き込んで、何らかのデータをそのデバイスから読み出すタイプのアクセス法を採用するデバイスもあり、その際の読み出しは場合によっては数十クロックサイクル待たなければならない（例えばリアルタイムクロック）。プログラマはオペレーティングシステムの遅延関数を呼び出すこともできるが、単に関数呼び出しをするだけで待つべきサイクル数を超える可能性が高い。このような場合、ビジーウェイト方式でデバイスのステータス変化をチェックし続けるのが一般的である。このような場合に遅延関数を呼ぶことは、関数呼び出しのオーバヘッドとスレッド切り替えのためにCPU時間を無駄にするだけだろう。

外部リンク

いずれも英文

pthread_spin_lock The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004年版
Article "User-Level Spin Locks - Threads, Processes & IPC" by Gert Boddaert
Austria SpinLock Class Reference

C言語でのコード例

CPU の利用状況

ビジーウェイトの代替手法

ビジーウェイトが適している状況

関連項目

外部リンク