ビジーウェイト

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

素朴な実装手法とその問題点

最も単純な実装は﹁何もしない (nop : No OPerationの略)﹂処理を繰り返し実行することにより、一定の時間を経過させるという方法になる。CPUはnop命令に出会うとCPU固有の一定時間﹁なにもしない﹂ため、実行するnop命令の回数を調整することで狙った時間を経過させることができる。一般にnop命令の繰り返し実行のためにループ構造を使用し、ループの繰り返し数によってnop命令の実行回数を指定する。しかし、この方法では、CPUの処理速度が異なることによってnop命令1つが消費する時間が異なる場合、ある回数のループによって経過させる時間は変化してしまう。特にデバイスとの入出力処理には、デバイスとのコマンド送受信やデータ処理のタイミングが重要であることがあり、素朴なビジーウェイトをタイミング調整に使用していると、動作が不安定になることもある。速度︵クロック周波数︶の異なる互換CPUをサポートしたい場合は、プログラムの開始時にnopを用いたループの実効速度を計測し、ビジーウェイト部分で使用する適切なループ回数を計算してセットする等の対処法もあるが、これはプログラム実行中にクロック周波数が常に同じ値に固定されていることを前提としており、負荷に応じて動的にクロック周波数が変動するようなCPUには対応できない。 SMPシステム向けのオペレーティングシステム内のスピンロックの実装などのような特定の状況下において、ビジーウェイトは有効かつ実用的な手法である。しかし、一般にはビジーウェイトはCPU時間を何もさせずに浪費するという観点から推奨される方法ではない。CPU時間を費やして待つ時間があれば、他のスレッドを動作させるほうが効率的である。

C言語でのコード例

以下のPOSIXスレッドライブラリを使ったC言語コードでは、複数のスレッドがグローバル変数によるフラグを共有している。1番目のスレッドはビジーウェイトでフラグの値の変化を待っている。

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

/* 全関数から見えるグローバルフラグ変数 */
atomic_int g_flag;

/* スレッド#1はフラグが偽 (0) になることをスピンして待つ */
static void *thread_func1(void*) {
    while (g_flag) {
        /* 何もしない - 単にチェックしながら回り続ける */
    } 
    printf("Thread#1 received notification: value of flag has been changed to %d.\n", g_flag);

    return NULL;
}

/* スレッド#2は一定時間待機した後にフラグを偽 (0) にする */
static void *thread_func2(void*) {
    sleep(60); /* 60秒間スリープ */
    g_flag = 0;
    printf("Thread#2 changed the value of flag to %d.\n", g_flag);

    return NULL;
}

int main(void) {
    int ret_code;
    pthread_t t1, t2;
    g_flag = 1; /* フラグを真にする */

    ret_code = pthread_create(&t1, NULL, thread_func1, NULL);
    if (ret_code != 0) {
        printf("Failed to create pthread #1.\n");
        return -1;
    }

    ret_code = pthread_create(&t2, NULL, thread_func2, NULL);
    if (ret_code != 0) {
        printf("Failed to create pthread #2.\n");
        return -1;
    }

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("All pthreads finished.\n");
    return 0;
}

ccコマンドの実態としてGCCまたはClangが利用可能なUNIX系システムでは、次のように上記コードをコンパイルすることができる:

$ cc -std=c11 spinlock.c -pthread

なお、C言語およびC++におけるvolatileキーワードはコンパイラ最適化を抑止するための修飾子であり、効果は処理系に依存する。C/C++の規格でスレッドが標準化されていなかった時代では、スレッド間で共有するフラグ変数にvolatileを指定することで、レジスタキャッシュではなく必ずメモリから値を読み出すように最適化を抑止する効果が期待されることから慣習的に使われていたが、本来はスレッドの同期目的で使ってはならない^[1]。フラグ変数の操作をミューテックス (mutex) によるクリティカルセクションで保護して明示的に同期したり、条件変数 (condition variable) を使ったり、上記コード例のようにC11やC++11規格以降のアトミック変数を使ったりするべきである。一方、JavaあるいはC#のような後発のプログラミング言語では、最初からスレッドが標準化されて言語仕様に組み込まれており、限定された範囲でvolatileキーワードを軽量な同期プリミティブの実装に利用することが可能である^[2]^[3]。

CPU の利用状況

上記のコードの中で、2番目のスレッドは直ちに60秒間スリープする。その間、最初のスレッドは、2番目のスレッドがフラグの値を変更したかどうかを繰り返しチェックする。 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
Thread#2 changed the value of flag to 0.
Thread#1 received notification: value of flag has been changed to 0.
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番目のスレッドがフラグの値を変更したときにシグナルでそれを通知する手段を提供している。この技法をイベント駆動型プログラミングと呼び、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（英語）

[1] POS03-C. volatile を同期用プリミティブとして使用しない

[2] Javaの理論と実践: volatile を扱う | IBM, Internet Archive

[3] volatile (C# リファレンス) | Microsoft Docs

[1]

[2]

[3]