スレッド

Ruby のスレッドは環境にあるスレッド機能を使うのではなく、ユーザレベルで 実装されている。また非常に移植性が高く、どんな環境でも動く。

またあまり知られていない機能だが Ruby には Call/CC という制御構造がある。 これは最初に実装されたのはschemeで、 「制御された関数越しgoto」みたいなものだ。この Call/CC はスレッドの機能を 使って実装されているので、ここに書くことにしよう。

スケジューリング

スレッドは「みんな同時に動く」というのが建前だが、実際はプロセスと 同じく、少しづつの時間、順番に動いている。それでもちゃんと全部の スレッドが平等に動いているように見えるためには、どこかで動作中の スレッドから動作権を奪って、別のスレッドに主導権を渡してやる必要がある。 その時の主眼はふたつ、「いつ」「だれに」スレッドを渡すかだ。いわゆる スケジューリングである。それを実装しているのは rb_thread_schedule() だ。

いつ?

thread_t 環状(ダブル)リンクリスト

eval.c から呼ばれているのはすべて Thread のメソッド

catch_timer では int rb_trap_immediate がセットされていると schedule TRAP_BEG/TRAP_ENDrb_trap_immediate をオン/オフする

setitimer (posix_)?signal(SIGVTALRM, catch_timer); でハンドラをセット SIGVTALRMVirtual Time Alarm つまりプロセスが走っている間だけ 動くタイマーの時刻が来たことを示す。 posix_signal は Ruby で用意してる関数。 SA_RESTART とかを使ってるところがちょっと違う。 (SAsigaction) posix_signal だと自動的に再設定される。それ以外ではハンドラの中で再度設定する。 Linuxsetitimerposix_signal

最初のスレッドが作られる時に setitimer でインターバルタイマーを設定 setitimer がないところでは rb_evalTHREAD_TICK 回まわったら交代する THREAD_TICK は現在は500

つまり、Rubyのスレッドは、Rubyスクリプト実行中はプリエンプティブ、 C コード実行中はノンプリエンプティブな動作をする。 ただし、C で書いていてもその途中で Ruby インタプリタが介入するような 関数を呼ぶとスレッドが切りかわることはありえる(たとえば rb_funcall など)。

だれに?

timer 待ちだったもの 最初から走っているもの(止められておらず、死んでいない) join 待ちだったもの fd 待ちだったもの

あとのふたつは Runnable に変化するので次のスケジュールの優先順位が上がることになる

もしすべてのスレッドが IO 待ちなら最短時間 select そうでなければノンブロック

select(2) int select(int, fd_set*, fd_set*, fd_set*, struct timeval *timeout); timeoutselect の最大待ち時間。timeout == NULL だとブロック 返り値はIOがあったfdの数 EINTR ブロックされていないシグナルを受けた linux とその他がかなり違う

これで見つからなかったらデッドロック。 全スレッドを止めてメインスレッドに例外発生

次のスレッドがカレントスレッドでなかったらコンテキストスイッチ

スレッド切り替え

ここまでで、Ruby のスレッドは完全な逐次実行であり、ふたつ以上の スレッドが同時に動くことはないということを見てきた。つまり別の スレッドが動くには切り替えが必要である。最後にこの切り替え部分を 見ていこう。

そもそもマルチスレッドで動くために必要なものはなにかというと、 基本的には、手続き型言語においてはスタックの複製だけだ。とにかく ひとつのスレッドにつきひとつのスレッドが使えるようになっていれば いい。その方法にはたとえば、malloc でスタック領域を用意しておいて CPU のスタックポインタ(あれば)にそこへのポインタを入れてやるとか、 あるいはカーネルのページングに紛れこませてやるというのでもうまく いきそうである。

では Ruby ではどうしているかというと…… rb_thread_schedule() の 最後を示す。

    /* コンテキストスイッチ */
    if (curr == curr_thread) {
        if (THREAD_SAVE_CONTEXT(curr)) {
            return;
        }
    }

    curr_thread = next;
    if (next->status == THREAD_TO_KILL) {
        if (!(next->flags & THREAD_TERMINATING)) {
            next->flags |= THREAD_TERMINATING;
            /* terminate; execute ensure-clause if any */
            rb_thread_restore_context(next, RESTORE_FATAL);
        }
    }
    rb_thread_restore_context(next, RESTORE_NORMAL);
}

THREAD_SAVE_CONTEXT() (マクロらしい) と rb_thread_restore_context() が 核のようだ。ではまず THREAD_SAVE_CONTEXT から。

#define THREAD_SAVE_CONTEXT(th) \
    (rb_thread_save_context(th),thread_switch(setjmp((th)->context)))

関数を三つ呼ぶだけだ。まず rb_thread_save_context() は 構造体 rb_thread_t 型の th にスタックとグローバル変数をひたすら コピーしまくる。グローバル変数のほうはただ代入を繰り返すだけ なので省略して、スタックのコピーだけ見よう。

static void
rb_thread_save_context(th)
    rb_thread_t th;
{
    VALUE *pos;
    int len;

    len = stack_length(&pos);
    th->stk_len = 0;
    th->stk_pos = (rb_gc_stack_start<pos)?rb_gc_stack_start
                                         :rb_gc_stack_start - len;
    if (len > th->stk_max) {
        REALLOC_N(th->stk_ptr, VALUE, len);
        th->stk_max = len;
    }
    th->stk_len = len;
    FLUSH_REGISTER_WINDOWS; 
    MEMCPY(th->stk_ptr, th->stk_pos, VALUE, th->stk_len);

簡単にまとめると、まず最初の数行でスタックの範囲を特定したのち、 th->stk_ptrth->stk_max 分のメモリを確保して、len の長さだけ コピーする。FLUSH_REGISTER_WINDOWS は、gc.c にもあったが、スタック 領域のキャッシュをメモリに落とすマクロ(実体はアセンブラ)だ。 sparc で使われる。

ではスタック範囲を調べる方法を詳しく見ていこう。 まず、この関数の実行時に pos はスタックの先端に置かれるので &pos は スタックの先端アドレス。一方 rb_gc_stack_start はスタックの 開始アドレス(main に近いほう)で、gc.cInit_stack() で初期化される。 そしてこれを利用して th->stk_pos がスタックの下端(低番地)アドレスを 決定する。スタックは上にのびるタイプと下にのびるタイプがあるので、下に のびるものの場合「下端」は pos になり、上にのびるなら rb_gc_stack_start になる。

また stack_length() は以下のとおり。

static int
stack_length(p)
    VALUE **p;
{
#ifdef C_ALLOCA
    VALUE stack_end;
    alloca(0);
# define STACK_END (&stack_end)
#else
# if defined(__GNUC__) && defined(USE_BUILTIN_FRAME_ADDRESS)
    VALUE *stack_end = __builtin_frame_address(0);
# else
    VALUE *stack_end = alloca(1);
# endif
# define STACK_END (stack_end)
#endif
    if (p) *p = STACK_END;

#ifdef __sparc__
    return rb_gc_stack_start - STACK_END + 0x80;
#else
    return (STACK_END < rb_gc_stack_start) ? rb_gc_stack_start - STACK_END
                                           : STACK_END - rb_gc_stack_start;
#endif
}

まずネイティブの alloca() がないところ(ifdef C_ALLOCA)では、 alloca() した時の最初のローカル変数のアドレスをスタック終端にする。 なんで alloca() するのかはわからない。そうするとなんかいいことが あるようだ。

次に、gcc の場合は __builtin_frame_address という組み込み関数を 呼んで直接的に一番上のフレームのアドレスを取る。それ以外ならば、 ネイティブの alloca() があるので、それを呼んで返ってきたアドレスを スタック終端とする。

そのあとの #ifdef __sparc__ しているところの +0x80 は、たぶん レジスタウィンドウをフラッシュする場所を確保しているのだろう。 で、それ以外なら単に引き算する。これも上端と下端がどっちかわからない ので分岐。

ひとつ疑問。alloca() がスタック先端にメモリを確保するのはわかるけども、 ローカル変数は常にスタックの「先端」のほうに確保されるものなのだろうか? そうでないと、その前にあるフレーム管理部分が消えてしまうことがあると 思うのだが……。alloca() のない OS では先端にあることがわかっていると いうことか? ていうかそれって DOS

さて、これでやっと rb_thread_save_context() が終わった。次になにを していたかというと、まず setjmp、続いて thread_switch だった。

#define THREAD_SAVE_CONTEXT(th) \
    (rb_thread_save_context(th),thread_switch(setjmp((th)->context)))

setjmp は最初は 0 を返し、戻ってきたときは longjmp の引数を返すのだった。 そして thread_switch() ではそれを次のように使う。

static int
thread_switch(n)
    int n;
{
    switch (n) {
      case 0:
        return 0;
      case RESTORE_FATAL:
        JUMP_TAG(TAG_FATAL);
        break;
      case RESTORE_INTERRUPT:
        rb_interrupt();
        break;
      case RESTORE_TRAP:
        rb_trap_eval(th_cmd, th_sig);
        errno = EINTR;
        break;
      case RESTORE_RAISE:
        ruby_frame->last_func = 0;
        ruby_sourcefile = th_raise_file;
        ruby_sourceline = th_raise_line;
        rb_f_raise(th_raise_argc, th_raise_argv);
        break;
      case RESTORE_SIGNAL:
        rb_raise(rb_eSignal, "SIG%s", th_signm);
        break;
      case RESTORE_NORMAL:
      default:
        break;
    }
    return 1;
}

0 なら(最初の呼びだしなら)そのまま返る。それ以外なら、いろいろ やったあと 1 を返す。ではこの setjmp はどんなとき 0 以外を返すかと 言うと、これが実は、このスレッドに実行が戻ってきたとき、なのである。 つまり別のスレッドからこのスレッドを対象に rb_thread_restore_context() が 呼ばれたときだ。というわけで今度はそれを見る。

static void
rb_thread_restore_context(th, exit)
    rb_thread_t th;
    int exit;
{
    VALUE v;
    static rb_thread_t tmp;
    static int ex;

    if (!th->stk_ptr) rb_bug("unsaved context");

    if (&v < rb_gc_stack_start) {
        /* 下にのびるスタック */
        if (&v > th->stk_pos) stack_extend(th, exit);
    }
    else {
        /* 上にのびるスタック */
        if (&v < th->stk_pos + th->stk_len) stack_extend(th, exit);
    }

    /*  省略……
        グローバル変数を戻す */

    tmp = th;
    ex = exit;
    FLUSH_REGISTER_WINDOWS;
    MEMCPY(tmp->stk_pos, tmp->stk_ptr, VALUE, tmp->stk_len);

    /* スレッドローカル変数を復帰 */
    rb_lastline_set(tmp->last_line);
    rb_backref_set(tmp->last_match);

    longjmp(tmp->context, ex);
}

th が実行を戻す相手だ。その核になる部分は最後の十数行で、 まずスタックを memcpyth のものに戻したあと、longjmp して スタックポインタとレジスタ、インストラクションポインタを 戻すだけである。しかしただスタックを書き戻すと th よりカレント スレッドのスタックが短かかった場合に実行中の関数のスタック領域を 上書きしてしまい、引数 th が壊れる。だからまずstack_extend で スタックを th よりも長くする。stack_extend() は以下。

static void
stack_extend(th, exit)
    rb_thread_t th;
    int exit;
{
    VALUE space[1024];

    memset(space, 0, 1);	/* space が最適化で消えないように */
    rb_thread_restore_context(th, exit);
}

1KB のローカル変数を確保して、スタックを延ばす。しかるのちに rb_thread_restore_context() を呼び直す。十分スタックがのびるまで これを繰り返すわけだ。十分な長さになったら longjmp を呼び出して 二度と戻らないので、stack_extend から返ったあとのことを気にする 必要はない。

それと rb_lastline_setrb_backref_set だけメモリを復帰した あとに変数を戻しているが、これはもちろん、実際に戻す先がスタック だからである。スタックを書き戻す前にスタックに代入したら、運が 運がよくても変数がちゃんと戻らないし、運が悪ければ segv する。

以上が Ruby のスレッド切り替えの実装だ。どう考えても軽くはない。 大量に malloc して大量に memcpy して挙句 setjmp longjmp して スタックをのばすために空の関数を呼びまくるのだから、相当に重いと 言ってよい。しかし OS 依存のシステムコールもアセンブラも (SPARC のレジスタウィンドウ関連以外は)使っておらず、確かに 移植性は高そうなことを確認できた。

Call/CC

Call/CC はようするに catch/throw みたいなものなのだが、違うのは スタックが深くなる方向にもジャンプできることだ。たとえば catch/throw では

A B C D (catch) E F G

という状態から

A B C D

に戻ることはできる。だが Call/CC では、

A B C D (callcc) E F G

という状態から

A B C X Y Z

となったとしても、Continuation#call

A B C D

に復帰できてしまう。catch/throw だけでも相当に危険なワザなのに、 ここまで来ると考えるだけでも恐ろしい機構である。はっきり言って 普通は使わない。Ruby に実装されている主な理由は 「実装できてしまったから」である。将来なくなる可能性も考えて おいたほうがいいと思う。

Call/CC の実装

というわけでどうして実装できてしまったのか見よう。Call/CC に必要 なのは、実は、ある時点でのスタックの複製である。これはまさに Ruby スレッドがやっていることだ。それゆえ Call/CC の実装は非常に単純で、 関っているのはおおむね関数ふたつだけ、しかもどちらも非常に短い。