マルチスレッドのコンテキスト切り替えに伴うコスト

また Linux カーネルの話です。

Linux では fork によるマルチプロセスと、pthread によるマルチスレッドでの並行処理を比較した場合、後者の方がコストが低く高速と言われます。「スレッドはメモリ空間を共有するので、マルチプロセスとは異なりコンテキストスイッチ時にメモリ空間の切り替えを省略できる。切り替えに伴うオーバーヘッドが少ない。」というのが FAQ の答えかと思います。

が「オーバーヘッドが少ない」と一言にいわれても具体的にどういうことなのかがイメージできません。そこで Linux のスレッド周りの実装を見て見ようじゃないか、というのが今回のテーマです。

3分でわかる(?) マルチプロセスとマルチスレッド

まずはうんちく。マルチプロセスとマルチスレッドの違いの図。以前に社内で勉強会をしたときに作った資料にちょうど良いのがあったので掲載します。Pthreadsプログラミングにある図を参考に作りました。

最初はプロセスの場合。fork で子プロセスを作った場合に親子の二つのプロセスのアドレス空間はどうなるか。

マルチプロセスの場合は親のメモリの内容を子にコピーします。(実際にはコピーオンライトで、プロセスを生んでいきなり全部コピーするわけではありません。) 親子の間で実行コンテキストが切り替わるときは、アドレス空間の切り替えが伴います。

一方のスレッドの場合。二つのスレッドは一つのアドレス空間を共有します。その上で命令を並行処理するために、実行コンテキスト毎にスタックポインタ (SP) とプログラムカウンタ (PC。次に実行する命令のアドレスを格納するレジスタ) を持ちます。スレッド間で実行コンテキストを切り替えるときはメモリ空間はそのまま、主にスタックポインタとプログラムカウンタを切り替えることでコンテキストスイッチが可能です。これにより、マルチスレッドではアドレス空間やファイルなどのリソースを共有しながら並行処理が可能になります。

Linux のスレッド (pthread)

Linux のスレッドの概要。

Linux ではカーネルがサポートする実行の単位を LWP (Light Weight Process = 軽量プロセス) と呼びます。
Linux + glibc の NPTL (Native POSIX Threading Library) による pthread の実装は LWP とユーザー空間でのスレッドが 1 対 1 に対応する「1:1 モデル」です。
プロセス、スレッド共にカーネル内部では同じプロセスディスクリプタ(= task_struct 構造体)で管理されます。またプロセススケジューラはプロセスもスレッドも同じアルゴリズム、同じキューの上でスケジューリングを行います。

この辺からもわかるとおり、カーネル内部ではプロセスもスレッドも概念的にはそんなに区別はありません。ので、カーネルの関数で hogehoge_process() というのはプロセスもスレッドも処理する関数だったりしますし、各種書籍あるいはソースコード中のコメントでもプロセスとスレッドという言葉をあまり明確に使い分けずに説明したりします。以下でも同様の扱いで説明します。

pthread で Hello, World! をトレースする

物は試しに pthread で Hello, World! なプログラムを strace で追ってみます。

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

void* hello (void *args)
{
    printf("Hello, World!\n");
    return NULL;
}

int main ()
{
    pthread_t t;
    if (pthread_create(&t, NULL, hello, NULL) < 0) {
        perror("pthread_create");
        exit(-1);
    }

    pthread_join(t, NULL);
    return 0;
}

というプログラムをコンパイルしてトレース。

% strace ./creat 1> /dev/null
...
brk(0)                                  = 0x804a000
brk(0x806b000)                          = 0x806b000
mprotect(0xb769c000, 4096, PROT_NONE)   = 0
clone(child_stack=0xb7e9b4c4, 
flags=CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|CLONE_SYSVSEM|CLONE_SETTLS
|CLONE_PARENT_SETTID|CLONE_CHILD_CLEARTID|CLONE_DETACHED, parent_tidptr=0xb7e9bbf8, 
{entry_number:6, base_addr:0xb7e9bbb0, limit:1048575, seg_32bit:1, contents:0, 
read_exec_only:0, limit_in_pages:1, seg_not_present:0, useable:1}, child_tidptr=0xb7e9bbf8) = 12173
futex(0xb7e9bbf8, FUTEX_WAIT, 12173, NULL) = 0
write(1, "Hello, World!\n", 14)         = 14
munmap(0xb769b000, 4096)                = 0
exit_group(0)                           = ?
Process 12172 detached

注目したのは clone() というシステムコールです。

clone(2)

man clone すると

The main use of clone() is to implement threads: multiple threads of control in a program that run concurrently in a shared memory space.

なんてことが書かれています。pthread_create() は裏で clone() を呼んで、新しいプロセスを作っているのがわかります。

clone() はカーネル内で新しいプロセス(スレッド)を作るのに使われるシステムコールです。上記の呼びだしでは CLONE_VM|CLONE_FS|CLONE_FILES... といろんなフラグを指定しています。このフラグに何を指定するかによって、できあがるプロセスの状態が変わります。

フラグには例えば

CLONE_VM を指定すると、新しく作ったタスクとメモリ空間を共有する
CLONE_FS でファイルシステム情報を共有する
CLONE_SIGHAND でシグナルハンドラを共有する
CLONE_THREAD で子プロセスが親プロセスと同じスレッドグループに属させる

といった意味があります。この辺のフラグを操作することで、上記の図のモデル通りのスレッドを組み立てることができるわけです。

clone(2) を深追い

では clone() システムコールからカーネルに潜って、スレッドができあがる過程を見ていきます。arch/i386/kernel/process.c に clone() の実装である sys_clone() が定義されています。

asmlinkage int sys_clone(struct pt_regs regs)
{
    unsigned long clone_flags;
    unsigned long newsp;
    int __user *parent_tidptr, *child_tidptr;

    /* レジスタ経由で渡ってきた引数を取り出す */
    clone_flags = regs.ebx;
    newsp = regs.ecx;
    parent_tidptr = (int __user *)regs.edx;
    child_tidptr = (int __user *)regs.edi;
    if (!newsp)
        newsp = regs.esp;

    /* 取り出した引数を指定して do_fork() */
    return do_fork(clone_flags, newsp, &regs, 0, parent_tidptr, child_tidptr);
}

引数の regs はユーザー空間で指定された引数がレジスタに入って、それが退避されて渡ってきたものです。(詳しくはひとつ前の日記を参照のこと) その regs から値、すなわちシステムコールに与えられた引数を取り出しつつ、それらをパラメータとして do_fork() を呼びだします。pthread_create() におけるここでの clone_flags は先のトレースで見た

CLONE_VM
CLONE_FS
CLONE_FILES
CLONE_SIGHAND
CLONE_THREAD
CLONE_SYSVSEM
CLONE_SETTLS
CLONE_PARENT_SETTID
CLONE_CHILD_CLEARTID
CLONE_DETACHED

というフラグ群になります。

少しわき道にそれます、ここで見ておきたいのは、regs.ecx が newsp という unsigned long な値に代入されて do_fork() が呼ばれている点。この regs.ecx には、clone() の引数として新しいスレッドが使うスタック領域を指したその値が入っています。この時点でスタックの先頭位置が決まってるということは、新しいスレッドのスタック領域を確保するのはカーネルの役目でなく、pthread_create() からカーネルの間、すなわち libc がやっているのがわかります。

話は戻ります。clone() は sys_clone() に、一方 fork() の実装である sys_fork() 関数はというと

asmlinkage int sys_fork(struct pt_regs regs)
{
    return do_fork(SIGCHLD, regs.esp, &regs, 0, NULL, NULL);
}

と同じく do_fork() を呼び出してます。引数、特にフラグが異なりますね。ユーザープロセスもスレッドも同じ手順で作っていくけれども、フラグの違いによってどっちになるかが変わるようになっているのが分かります。

では do_fork() に入ります。kernel/fork.c です。

long do_fork(unsigned long clone_flags,
          unsigned long stack_start,
          struct pt_regs *regs,
          unsigned long stack_size,
          int __user *parent_tidptr,
          int __user *child_tidptr)
{
    struct task_struct *p;
    int trace = 0;

    /* 新しい PID を取得 */
    struct pid *pid = alloc_pid();
    long nr;
    if (!pid)
        return -EAGAIN;
    nr = pid->nr;

    /* カレントプロセスがトレースされているか調べる */
    if (unlikely(current->ptrace)) {
        trace = fork_traceflag (clone_flags);
        if (trace)
            clone_flags |= CLONE_PTRACE;
    }

    /* プロセスを複製する */
    p = copy_process(clone_flags, stack_start, regs, stack_size, parent_tidptr, child_tidptr, nr);
    ...

do_fork() では現在実行中のプロセスがトレースされているかを調べた後、copy_process() を呼びます。この copy_process() がプロセスを作る核の処理になっています。

さらに copy_process() 関数を追う

copy_process() は結構長い関数で重要な処理をたくさんやってるのですが、大部分を端折ります。あくまで今回注目したいアドレス空間の共有とかその辺だけに絞るのですが、ほかにも重要な部分はたくさんあるのでその点はご注意を。

static struct task_struct *copy_process(unsigned long clone_flags,
                    unsigned long stack_start,
                    struct pt_regs *regs,
                    unsigned long stack_size,
                    int __user *parent_tidptr,
                    int __user *child_tidptr,
                    int pid)
{
    int retval;
    struct task_struct *p = NULL;

    ...

    /* current (カレントプロセス) からディスクリプタ (task_struct) のコピーを作る */
    p = dup_task_struct(current);
    if (!p)
        goto fork_out;
    ...

新しく作るプロセス用のプロセスディスクリプタを作成するために dup_task_struct(current) して、カレントプロセスからディスクリプタのコピーを作ります。なお「task_struct をコピーする」といってもコピーされるのは管理情報(ディスクリプタ)であって、プロセス全部がまるごとコピーされるわけではありません。

dup_task_struct() の中も見てみます。同じ fork.c にあります。

static struct task_struct *dup_task_struct(struct task_struct *orig)
{
    struct task_struct *tsk;
    struct thread_info *ti;

    prepare_to_copy(orig);

    /* 新しい task_struct をアロケート */
    tsk = alloc_task_struct();
    if (!tsk)
        return NULL;

    /* 新しい thread_info をアロケート */
    ti = alloc_thread_info(tsk);
    if (!ti) {
        free_task_struct(tsk);
        return NULL;
    }

    /* カレントプロセスのプロセスディスクリプタの内容をコピー */
    *tsk = *orig;

    /* thread_info をセット、カーネルスタックをセットアップ */
    tsk->thread_info = ti;
    setup_thread_stack(tsk, orig);

    ...

    return tsk;
}

カレントプロセスのプロセスディスクリプタを基に新しいディスクリプタを作り、カーネルスタック (前回 id:naoya:20071008:1191824562 参照) を用意しています。できがったプロセスディスクリプタを呼びだし元に返します。

dup_task_struct() の後は OS が上限を超えてスレッドを作成していないかをチェックしたり、プロセスディスクリプタの各種メンバ(いっぱいある)の初期化と設定、プロセスグループやスレッドグループを形成するためのスレッドグループIDやプロセスIDの調整を行います。その後に続いて

    /* copy all the process information */
    if ((retval = copy_semundo(clone_flags, p)))
        goto bad_fork_cleanup_audit;
    if ((retval = copy_files(clone_flags, p)))
        goto bad_fork_cleanup_semundo;
    if ((retval = copy_fs(clone_flags, p)))
        goto bad_fork_cleanup_files;
    if ((retval = copy_sighand(clone_flags, p)))
        goto bad_fork_cleanup_fs;
    if ((retval = copy_signal(clone_flags, p)))
        goto bad_fork_cleanup_sighand;
    if ((retval = copy_mm(clone_flags, p)))
        goto bad_fork_cleanup_signal;
    if ((retval = copy_keys(clone_flags, p)))
        goto bad_fork_cleanup_mm;
    if ((retval = copy_namespaces(clone_flags, p)))
        goto bad_fork_cleanup_keys;
    retval = copy_thread(0, clone_flags, stack_start, stack_size, p, regs);
    if (retval)
        goto bad_fork_cleanup_namespaces;

と、各種プロセス情報のコピーが始まります。今回のテーマにおいてはとても重要な箇所がここになります。例えば関数の名前からも想像がつきますが、copy_files はファイルディスクリプタのコピーをします。実装を見てみます。

static int copy_files(unsigned long clone_flags, struct task_struct * tsk)
{
    struct files_struct *oldf, *newf;
    int error = 0;

    /* カレントプロセスが開いているファイルディスリプタを取得 */
    oldf = current->files;
    if (!oldf)
        goto out;

    /* CLONE_FILES だったら参照カウントを足すだけで何もしない */
    /* tsk は current のコピーなので tsk->files はこの時点で current と同じ */
    if (clone_flags & CLONE_FILES) {
        atomic_inc(&oldf->count);
        goto out;
    }

    /* ディスクリプタを新しいプロセスに複製 (dup) */
    tsk->files = NULL;
    newf = dup_fd(oldf, &error);
    if (!newf)
        goto out;

    tsk->files = newf;
    error = 0;
out:
    return error;
}

ファイルディスクリプタをコピーしていますが、引数の clone_flags (clone() 呼びだし時に指定されてたあれ) で CLONE_FILES フラグが指定されている場合は、コピーはしません。このとき先の dup_task_struct() で新しいプロセスディスクリプタの内容はカレントプロセスのそれから作成されています。従って tsk->files に何もしない = カレントプロセスと同じものを使う = 親と共有する、ということになります。コード上でのフラグの意味が明らかになってきました。

メモリディスクリプタのコピー処理 copy_mm()

さて、核心に迫ってきました。各コピー処理の中でアドレス空間をコピーしている copy_mm() をみてみます。先に述べたとおりプロセスのメモリ空間の情報は task_struct の mm メンバのメモリディスクリプタ mm_struct 構造体が保持します。copy_mm() というのは名前からもわかるとおりメモリディスクリプタのコピー処理です。

static int copy_mm(unsigned long clone_flags, struct task_struct * tsk)
{
    struct mm_struct * mm, *oldmm;
    int retval;

    tsk->min_flt = tsk->maj_flt = 0;
    tsk->nvcsw = tsk->nivcsw = 0;

    tsk->mm = NULL;
    tsk->active_mm = NULL;

    /*
     * Are we cloning a kernel thread?
     *
     * We need to steal a active VM for that..
     */
    oldmm = current->mm;
    if (!oldmm)
        return 0;

    /* CLONE_VM だった場合は親プロセスの mm を子にもセット */
    if (clone_flags & CLONE_VM) {
        atomic_inc(&oldmm->mm_users);
        mm = oldmm;
        goto good_mm;
    }

    retval = -ENOMEM;
    mm = dup_mm(tsk);
    if (!mm)
        goto fail_nomem;

good_mm:
    /* Initializing for Swap token stuff */
    mm->token_priority = 0;
    mm->last_interval = 0;

    tsk->mm = mm;
    tsk->active_mm = mm;
    return 0;

fail_nomem:
    return retval;
}

いくつか処理をしてるのですが、今回注目したいのは中央の CLONE_VM の処理。先の CLONE_FILES のときと同様、CLONE_VM が指定されている場合はメモリディスクリプタを新たに用意する(= 子プロセスに新しいアドレス空間を用意する)のではなく、親と同じものを使う(= 親とアドレス空間を共有する) ことがわかります。

mm_struct には、x86 のページング機構において論理アドレスを物理アドレスに変換するためのテーブルの場所を保持する pgd メンバがあります。前回 id:naoya:20071008:1191824562 でも見たとおり、pgd の値を cr3 というレジスタにセットするとアドレス空間が切り替わります。A と B というプロセスがあったとき A の mm.pgd が cr3 にセットされていたところを、B の mm.pgd に変える命令が、結果プロセスの A → B へとアドレス空間を切り替えたことになるのでした。

ここで CLONE_VM を指定したということは二つの実行コンテキストで mm.pgd が一緒。つまりこの二つの実行コンテキストにとっては(通常のプロセスとは異なり)同じ論理アドレスが同じ物理アドレスを指すことになります。スレッドがアドレスを共有する、というのはまさにこのことです。

ハードウェアコンテキストのコピー、スタックの調整をする copy_thread()

各種コピーの締めとして、arch/i386/kernel/process.c の copy_thread() が呼ばれます。ここではハードウェアコンテキストのコピーや設定が行われます。

int copy_thread(int nr, unsigned long clone_flags, unsigned long esp,
    unsigned long unused,
    struct task_struct * p, struct pt_regs * regs)
{
    struct pt_regs * childregs;
    struct task_struct *tsk;
    int err;

    /* 子のカーネルスタックのベースアドレスを取得 */
    childregs = task_pt_regs(p);

    /* 親プロセスのレジスタの内容をコピー */
    *childregs = *regs;

    /* fork(), clone() の子プロセスの返値 0 */
    childregs->eax = 0;

    /* ユーザー空間用のスタックポインタは clone() の時に指定されたスタック */
    childregs->esp = esp; 

    /* カーネルスタックのベースを esp にセット */
    p->thread.esp = (unsigned long) childregs;

    /* TSS の esp0 に指定されるメンバ */
    p->thread.esp0 = (unsigned long) (childregs+1);

    /* このプロセスがスケジューリングされると ret_from_fork() が実行されるように */
    p->thread.eip = (unsigned long) ret_from_fork;
...

カーネルスタックに、プロセス復帰後に使うレジスタの値を積んでおきつつそれを esp / esp0 にセット。プロセスが復帰して特権モードが切り替わる前に、chilregs に積んだ esp や eax は復帰されて、ユーザー空間で生かされます。

なお、ret_from_fork は以下のようなアセンブリ命令です。スタックに退避されたほかのレジスタを復帰して (schedule_tail でプロセス切り替えの後処理をした後) システムコールを抜けます。

ENTRY(ret_from_fork)
        CFI_STARTPROC
        pushl %eax
        CFI_ADJUST_CFA_OFFSET 4
        call schedule_tail
        GET_THREAD_INFO(%ebp)
        popl %eax
        CFI_ADJUST_CFA_OFFSET -4
        pushl $0x0202                   # Reset kernel eflags
        CFI_ADJUST_CFA_OFFSET 4
        popfl
        CFI_ADJUST_CFA_OFFSET -4
        jmp syscall_exit
        CFI_ENDPROC

copy_process() の処理はまだ色々とあるのですが、今回みたい処理はこのあたりまで。特に copy_mm() で CLONE_VM が指定されていると task_struct の mm メンバが、親プロセスと子プロセスの間で同じものになるというところがポイントでした。

コンテキストスイッチのコードを見る

では、最後にコンテキストスイッチのコードを見てみます。

コンテキストスイッチ処理の context_switch() は主に (1) プロセス空間の切り替え (2) ハードウェアコンテキストの退避の二つの処理が中心でした。(1) は前回 id:naoya:20071008:1191824562 で、(2) は前々回 id:naoya:20070924:1190653790 でも見てきました。

この (2) プロセス空間の切り替えは include/asm-i386/mmu_context.h のインライン関数 switch_mm() でやっているのでした。改めてみてみます。簡単のためマルチプロセッサ対応のコード (#ifdef CONFIG_SMP 〜 #endif) を削除したものを以下に記します。

static inline void switch_mm(struct mm_struct *prev,
                 struct mm_struct *next,
                 struct task_struct *tsk)
{
    int cpu = smp_processor_id();

    /* 両者のメモリディスクリプタ mm_struct が同じだったら何もしない */
    if (likely(prev != next)) {
        /* stop flush ipis for the previous mm */
        cpu_clear(cpu, prev->cpu_vm_mask);
        cpu_set(cpu, next->cpu_vm_mask);

        /* Re-load page tables */
        load_cr3(next->pgd);

        /*
         * load the LDT, if the LDT is different:
         */
        if (unlikely(prev->context.ldt != next->context.ldt))
            load_LDT_nolock(&next->context);
    }
}

switch_mm() に渡された二つのメモリディスクリプタ mm_struct が同じだった場合は、切り替えのための処理は何も行われないのがわかります。ここで、先に見てきた箇所が繋がります。つまり、

スレッドの場合 CLONE_VM が指定されて clone() が呼ばれる
copy_mm() で親子で同じ mm を使う (= アドレス空間の共有)
親プロセス (prev) と子プロセス (next) は mm メンバが一緒
switch_mm() では何もしない

ということになるのがわかります。(正確には switch_mm() では prev の active_mm と next の mm を比較しているのですが、プロセス/スレッドの場合は active_mm == mm なのでほぼ同じ。) すなわち同じプロセス内で生成されたスレッド同士のコンテキスト切り替え時にはアドレス空間切り替え処理がほぼノーコスト、ということがわかります。

cr3 制御レジスタの更新 = TLB フラッシュ

ここからはハード (x86) の話。この辺は前回まとめたので、ざっくりと。

switch_mm() で何もしないということは、load_cr3(next->gpd) による cr3 レジスタの更新も発生しません。
前回まとめたとおり、cr3 レジスタを切り替える = プロセスアドレス空間の切り替えです。
cr3 レジスタにはページグローバルディレクトリのアドレスが指定されています。
ページング機構によるアドレス変換では普通にしてると毎回メモリにアドレス変換テーブルを探しにいって遅いので、TLB (Translation Lookaside Buffer http://ja.wikipedia.org/wiki/TLB) がテーブルのエントリをキャッシュしています。
cr3 を切り替えると別のページグローバルディレクトリを使うことになるので、キャッシュをフラッシュする必要があります。この TLB のフラッシュは cr3 を更新すると x86 が自動で行います。
TLB をフラッシュする → TLB キャッシュミスが発生します。
この TLB フラッシュのコストは相対的にかなり大きいそうです。
- なお、TLB フラッシュそのもののコストが大きいのが問題なのか、その後のキャッシュミスによるコストが大きいのかをちゃんと理解できてません。すいません。(参考: 議論/メッセージ/CR3切替コスト - Mona OS developers Wiki (特にコメント欄))

つまり、アドレス空間を切り替えるときに論理→物理アドレス変換用のキャッシュをクリアする必要があってそのコストが高い、ということです。そしてここまで実装を見たとおり、通常のマルチプロセスではそれがコンテキストスイッチ毎に発生するが、マルチスレッドであればスレッド間同士で切り替えをしている間に限っては、そのコストが発生しない、ということがわかりました。

また、前々回 id:naoya:20070924:1190653790 でみた限りではハードウェアコンテキスト切り替えの際、プロセスとスレッドを意識した処理の分岐をしている箇所はなかったように思います。よって x86 Linux におけるスレッドとプロセスのコンテキスト切り替えで差がつく原因はこのプロセスアドレス空間切り替えに伴う TLB フラッシュの影響が大きいと言えそうです。(...という風に理解したのですがこれで OK でしょうか。 > 識者の方々。)

まとめ

マルチプロセスとマルチスレッドの違いを知るためにカーネルの実装を見てきました。
Linux の pthread は LWP とユーザー空間でのスレッドが 1対1 に対応する 1:1 モデルです。
Linux カーネルはプロセスもスレッドも内部では同じ task_struct 構造体で管理し、同じようにスケジューリングします。
pthread_create() をすると CLONE_VM そのほかのフラグを指定した clone() システムコールが呼ばれます。
システムコールの処理を追っていくと、スレッドの場合はメモリディスクリプタは新規に用意することはせず、新しいコンテキストとの間で元々使っていたものを共有することがわかりました。これによりメモリの共有が実現されています。
更にコンテキストスイッチの処理を追っていくと、メモリディスクリプタが同一の場合は、アドレス空間切り替えの switch_mm() では何もしないことがわかります。
switch_mm() で何もしない = cr3 レジスタの書き換えが発生しない = コストの高い TLB フラッシュを避けられる = マルチプロセスよりコストが低いということがわかりました。
TLB フラッシュ(とその後の TLB キャッシュミス)の影響によるコストがどの程度高いのか、というのを定量的に測ったドキュメントなどをご存知でしたら教えてください。

naoyaのはてなダイアリー