Linuxのsemaphoreとmutexの実装

Linuxのsemaphoreとmutexを見る glibc版

目次 • semaphoreとmutexとは？ • 計算機科学におけるsemaphore • 計算機科学におけるmutex • semaphoreとmutexの実装方法 • semaphoreの実装例 • mutexの実装例 • Linuxの場合 • LinuxのPOSIX semaphoreとmutex • LinuxのPOSIX semaphoreの実装を見る • Linuxのsemaphoreとmutexのまとめ

semaphoreとmutexとは？ • semaphoreとmutexとは？ • 資源の同期・排他を行うための仕組みで、主にsemaphoreは同期のために、 mutexは排他のために使用する • 計算機科学の分野では昔から存在する考え方で、一般的なOS(Operating System)であれば用意されている • 初期のFreeRTOSやuITRONなどsemaphoreのみでmutexが用意されていないも のもある

計算機科学における semaphore semaphoreの排他用途での使用(バイナリセマフォ) Thread 1 run run (got semaphore) run signal() wait() Thread 2 run semaphore stop (wait semaphore) wait() →block 0 1 Thread 1が、semaphore資源 を獲得 run (got semaphore) signal() unblock 1 0 1 Thread 1が、semaphore資源を 開放したため、獲得待ちに なっていたThread2がunblock Thread 2が、semaphore資源を 獲得しようとするが、資源が ないためblock run Thread 2が、semaphore資源を 開放したため、資源が1に戻る semaphoreの排他用途での使用(資源数2の場合) Thread 1 run run (got semaphore) run wait() Thread 2 signal() run run run (got semaphore) wait() Thread 3 signal() run stop (wait semaphore) run (got semaphore) wait() →block semaphore Thread 1が、semaphore 資源を獲得 2 1 Thread 1が、semaphore 資源を獲得 unblock 0 Thread 3が、semaphore 資源を獲得しようとす るが、資源がないため block 1 Thread 1が、semaphore 資源を開放したため、 獲得待ちになっていた Thread3がunblock 0 1 Thread 2が、semaphore資源を 開放したため、資源が1に戻る

計算機科学における semaphore semaphoreの同期用途での使用 queue(データ構造)と組み合わせて、スレッド間通信を行う Thread 1 run enqueue() Thread 2 run stop (wait semaphore) unblock semaphore queue Thread 1が、queueに Thread 2に渡したい データを格納 0 0 Thread 1が、semaphore 資源を与えることで、 Thread 2がunblock enqueue() wait() signal() signal() run stop (wait semaphore) wait() →block unblock 1 dequeue() 0 1 0 Thread 2は、queueか らデータを一個取得 0 1 dequeue() 1 0 受け取ったデータの処理が完了したThread 2は、 semaphoreの資源待ちに入り再度Thread 1から データが送られるのを待つ

計算機科学における mutex mutexの排他用途での使用 Thread 1 run run (mutex locked) run unlock() lock() Thread 2 run mutex stop (wait unlock) unlock Thread 1が、mutexをlockし 所有権を得る lock() →block locked (Thread 1) Thread 2が、mutexをlockしよ うとするが、Thread 1にlockさ れているためblock run (mutex locked) unblock run unlock() locked (Thread 2) Thread 1が、mutexをunlockし たため、lock待ちしていた Thread2が所有権を得てunblock Thread 2が、mutexをunlockし たため、mutexがunlock状態に 戻る mutexの特徴 Thread 1 run run (got semaphore) Thread 2 run unlock() lock() run mutex Thread 1が、mutexをlockし 所有権を得る unlock() →error locked (Thread 1) Thread 2が、mutexをunlockしようとす るが、mutexの所有権を持っているの はThread 1なので、エラーになる。 unlock unlock Thread 1はmutexを所有してい るためunlockに成功する →mutexはsemaphoreとは異なり、同期用途には使えない

semaphoreとmutexとは？ • お題のsemaphoreとmutexとは？ • 資源の同期・排他を行うための仕組みで、主にsemaphoreは同期のために、 mutexは排他のために使用する • 計算機科学の分野では昔から存在する考え方で、一般的なOS(Operating System)であれば用意されている • 初期のFreeRTOSやuITRONではsemaphoreのみでmutexが用意されていないも のもある • semaphoreとmutexの違いは、所有権の概念の有無 • 所有権の概念のないsemaphoreは排他と同期の両方に使うことができる • 所有権の概念のあるmutexは排他用途にしか使えない • 所有権の概念があるため、優先度継承プロトコルや再帰ロックのようなmutex の特徴となる機能が提供される • 優先度継承の概念はRTOS(Real-Time OS)では重要な機能だが、後半の内容 が複雑化するため省略する。 • 所有権の概念が原則としてないが、Linuxなどで使われるPOSIX仕様のmutexは、 初期化時の設定で所有権の概念を持たないmutexを作ることができる。

目次 • semaphoreとmutexとは？ • 計算機科学におけるsemaphore • 計算機科学におけるmutex • semaphoreとmutexの実装方法 • semaphoreの実装例 • mutexの実装例 • Linuxの場合 • LinuxのPOSIX semaphoreとmutex • LinuxのPOSIX semaphoreの実装を見る • Linuxのsemaphoreとmutexのまとめ

semaphoreの実装例 semaphoreはカウンタとqueueで実装される 初期状態 Th.1がwait() Th.2がwait() Sem Q. Res. 0 Sem Q. Res. 1 Sem Q. Res. 0 Sem Q. Res. 0 Th.2 資源が1の状態でwait()され たので、資源数をディクリ メントする。 semaphoreは資源数と、 blockしたスレッドを覚える ためのqueueを持つ。 semaphore1個につき、この データが1個作られる。 Th.1がsignal() ① Th.1がsignal() ② Sem Q. Res. 1 Sem Q. Res. 0 Th.2 Th.3 Th.1がsignal()したことで、 資源が1になる。 Th.3 資源が1になったため、 semaphoreの資源待ちqueue にいるスレッドをunblockし、 資源数をディクリメントす る。 Th.3がwait() 資源が0の状態でwait()され たので、Th.2を待ち状態に して、semaphoreの資源待 ちqueueにつなぐ。 Th.2 Th.3 資源が0の状態でさらに wait()されたので、Th.3を待 ち状態にして、semaphore の資源待ちqueueにつなぐ。 RTOSでは、カーネルのシステムコール内で これらの操作が行われる。 LinuxではRTOSとは違った実装になっており、 その解説が後半の内容です。

mutexの実装例 mutexもsemaphoreと同様にqueueを持ち、カウンタの代わりに所有者を格納する形で実装される 初期状態 Th.1がlock() Th.2がlock() Mutex Q. (Th. 1) Mutex Q. (None) Mutex Q. (Th. 1) Th.2 所有者がいない(None) 状態 でlock()されたので、Th. 1 を所有者にする。 mutexはblockしたスレッド を覚えるためのqueueと、 所有者情報を持つ。 mutex 1個につき、このデー タが1個作られる。 Th.1がunlock() ① Th.1がunlock() ② Mutex Q. (None) Th.2 Sem Q. (Th. 2) Th.3 Th.1がsignal()したことで、 資源が1になる。 Th.3 資源が1になったため、 semaphoreの資源待ちqueue にいるスレッドをunblockし、 資源数をディクリメントす る。 資源が0の状態でwait()され たので、Th.2を待ち状態に して、semaphoreの資源待 ちqueueにつなぐ。 Th.3がlock() Mutex Q. (Th. 1) Th.2 Th.3 資源が0の状態でさらに wait()されたので、Th.3を待 ち状態にして、semaphore の資源待ちqueueにつなぐ。 資源がある/ないが所有者がいる/いないに変 わる点が、semaphoreとmutexの違い。 この違いが、優先度継承*1や再帰的ロック*2 を可能にしている。 *1. ロックまちをしているスレッドのうち最も高い優先度 に、mutexをロックしているスレッドを昇格させる *2. 同じmutexを複数回ロックでき、ロックした回数unlock するまで所有権を維持する

目次 • semaphoreとmutexとは？ • 計算機科学におけるsemaphore • 計算機科学におけるmutex • semaphoreとmutexの実装方法 • semaphoreの実装例 • mutexの実装例 • Linuxの場合 • LinuxのPOSIX semaphoreとmutex • LinuxのPOSIX semaphoreの実装を見る • Linuxのsemaphoreとmutexのまとめ

Linuxのsemaphoreとmutex • LinuxのsemaphoreとmutexはNPTLによって提供されている • NPTL(Native POSIX Thread Library)は、RedHatによって開発されたライブ ラリで、glibcでPOSIXスレッドの機能を提供している • POSIXスレッドのAPIは先頭にpthreadがついている • POSIX semaphoreはPOSIXスレッドには含まれないが、NPTLに含まれている • Linuxにはmutexは一種類しか存在しないが、semaphoreは2種類ある • System V semaphore • 古くからあるsemaphoreで、プロセス間での排他・同期向けの作りになって おり、スレッド間の排他・同期には向いていない • UNIXの世界では、スレッドの考え方は後から付け足された概念なので、他に も同じようなつくりの物が結構ある • POSIX semaphore • 機能をシンプルにしたsemaphoreで、プロセス間での利用向け（名前付き） と、プロセス内での利用向け（名前なし）の両方が存在する • 今日中身を解説するのはこちら

Linuxのsemaphore実装を見る
• POSIX semaphoreは、sem_initで作成する
int
__new_sem_init (sem_t *sem, int pshared, unsigned int value)
{
/* Parameter sanity check. */
if (__glibc_unlikely (value > SEM_VALUE_MAX))
{
__set_errno (EINVAL);
return -1;
}
pshared = pshared != 0 ? PTHREAD_PROCESS_SHARED : PTHREAD_PROCESS_PRIVATE;
int err = futex_supports_pshared (pshared);
if (err != 0)
{
__set_errno (err);
return -1;
}

Semaphoreの上限値を超えた値を初
期値にしていたらエラーにする

Semaphoreをプロセス間共有する指
定がされていた場合に、futex(ここ大
事)がプロセス間共有をサポートして
いるかどうかをチェックする

/* Map to the internal type. */
struct new_sem *isem = (struct new_sem *) sem;
/* Use the values the caller provided. */
#if __HAVE_64B_ATOMICS
isem->data = value;
#else
isem->value = value << SEM_VALUE_SHIFT;
/* pad is used as a mutex on pre-v9 sparc and ignored otherwise. */
isem->pad = 0;
isem->nwaiters = 0;
#endif
isem->private = (pshared == PTHREAD_PROCESS_PRIVATE
? FUTEX_PRIVATE : FUTEX_SHARED);
return 0;
}

Semaphore構造体のメンバを初期化

Linuxのsemaphore実装を見る
• POSIX semaphoreは、sem_initで作成する
int
__new_sem_init (sem_t *sem, int pshared, unsigned int value)
{
/* Parameter sanity check. */
if (__glibc_unlikely (value > SEM_VALUE_MAX))
{
__set_errno (EINVAL);
return -1;
}
pshared = pshared != 0 ? PTHREAD_PROCESS_SHARED : PTHREAD_PROCESS_PRIVATE;
int err = futex_supports_pshared (pshared);
if (err != 0)
{
__set_errno (err);
return -1;
}

Semaphoreの上限値を超えた値を初
期値にしていたらエラーにする

Semaphoreをプロセス間共有する指
定がされていた場合に、futex(ここ大
事)がプロセス間共有をサポートして
いるかどうかをチェックする

Semaphoreの作成時に、カーネルの資源
を作成していない
/* Map to the internal type. */
struct new_sem *isem = (struct new_sem *) sem;

/* Use the values the caller provided. */
#if __HAVE_64B_ATOMICS
isem->data = value;
#else
isem->value = value << SEM_VALUE_SHIFT;
/* pad is used as a mutex on pre-v9 sparc and ignored otherwise. */
isem->pad = 0;
isem->nwaiters = 0;
#endif
isem->private = (pshared == PTHREAD_PROCESS_PRIVATE
? FUTEX_PRIVATE : FUTEX_SHARED);
return 0;
}

Semaphore構造体のメンバを初期化

Linuxのsemaphore実装を見る • Semaphore資源の獲得は、sem_waitで行う int __new_sem_wait (sem_t *sem) { __pthread_testcancel (); if (__new_sem_wait_fast ((struct new_sem *) sem, 0) == 0) return 0; else return __new_sem_wait_slow((struct new_sem *) sem, NULL); } static int __new_sem_wait_fast (struct new_sem *sem, int definitive_result) { #if __HAVE_64B_ATOMICS uint64_t d = atomic_load_relaxed (&sem->data); do { if ((d & SEM_VALUE_MASK) == 0) break; if (atomic_compare_exchange_weak_acquire (&sem->data, &d, d - 1)) return 0; } while (definitive_result); return -1; #else 省略 #endif } とりあえず、fastパスでOKになったら、 確保成功を返す Semaphore構造体から、現在のセマ フォの資源数を取得(アトミック読み 込み) →メモリから値をコピーしているだけ 資源数0の場合は、エラーを返す →slowパスに流す アトミックダウンカウントを行い、資 源数を1減らせたら確保成功 →だめだったら(競合したら)slowパス に流す

Linuxのsemaphore実装を見る • Semaphore資源の獲得は、sem_waitで行う int __new_sem_wait (sem_t *sem) { __pthread_testcancel (); if (__new_sem_wait_fast ((struct new_sem *) sem, 0) == 0) return 0; else return __new_sem_wait_slow((struct new_sem *) sem, NULL); } static int __new_sem_wait_fast (struct new_sem *sem, int definitive_result) { #if __HAVE_64B_ATOMICS uint64_t d = atomic_load_relaxed (&sem->data); do { if ((d & SEM_VALUE_MASK) == 0) break; if (atomic_compare_exchange_weak_acquire (&sem->data, &d, d - 1)) return 0; } while (definitive_result); return -1; #else 省略 #endif } とりあえず、fastパスでOKになったら、 確保成功を返す Semaphore構造体から、現在のセマ フォの資源数を取得(アトミック読み 込み) →メモリから値をコピーしているだけ 資源数0の場合は、エラーを返す Semaphoreの資源を確保するだけであれ →slowパスに流す ば、ユーザ空間で変数ディクリメントす アトミックダウンカウントを行い、資 源数を1減らせたら確保成功 るだけで処理が終わる →だめだったら(競合したら)slowパス に流す

Linuxのsemaphore実装を見る
• Semaphore資源の獲得は、sem_waitで行う
static int __attribute__ ((noinline))
__new_sem_wait_slow (struct new_sem *sem, const struct timespec *abstime)
{
int err = 0;
uint64_t d = atomic_fetch_add_relaxed (&sem->data, (uint64_t) 1 << SEM_NWAITERS_SHIFT);
for (;;)
{
if ((d & SEM_VALUE_MASK) == 0)
{
err = do_futex_wait (sem, abstime);
if (err == ETIMEDOUT || err == EINTR)
{
__set_errno (err);
err = -1;
atomic_fetch_add_relaxed (&sem->data,
-((uint64_t) 1 << SEM_NWAITERS_SHIFT));
break;
}
d = atomic_load_relaxed (&sem->data);
}
else
{
省略
}
}
return err;

}

もう一回セマフォの資源をアトミック
読み込みで取得する
本当に資源が存在しないことを確認し
て、futex待ちに入る。
もし資源があった場合は、fastパスと
同じアトミックディクリメントを行う
シグナルに割り込まれた場合やタイム
アウトした場合は、一度sem_waitをエ
ラーで返す
futex待ちから出た後、アトミック読み
込みを行い、再度資源確保を試みる。
資源数を1減らせたら確保成功
→だめだったら、またfutex待ちに入る

注. スペースの都合上、32bit向け実装やsemaphoreの動きと直接関係ない行は省略しています

Linuxのsemaphore実装を見る
• Semaphore資源の開放は、sem_postで行う
int
__new_sem_post (sem_t *sem)
{
struct new_sem *isem = (struct new_sem *) sem;
int private = isem->private;
uint64_t d = atomic_load_relaxed (&isem->data);
do
{
if ((d & SEM_VALUE_MASK) == SEM_VALUE_MAX)
{
__set_errno (EOVERFLOW);
return -1;
}
}
while (!atomic_compare_exchange_weak_release (&isem->data, &d, d + 1));

セマフォの資源をアトミック読み込み
で取得する

資源数が限界値だったらエラーにする

資源数をアトミックインクリメント

if ((d >> SEM_NWAITERS_SHIFT) > 0)
futex_wake (((unsigned int *) &isem->data) + SEM_VALUE_OFFSET, 1, private);

return 0;
}

資源数を0から1にした場合は、誰かが
待っているので、futexに希少要求をか
ける

注. スペースの都合上、32bit向け実装やsemaphoreの動きと直接関係ない行は省略しています

Linuxのsemaphore実装を見る • 途中で出てきたfutexとは？ • NPTLの開発と同時に作られたシステムコールで、アトミックな休眠と起 床を実現するための仕組み int futex(int *uaddr, int op, int val, const struct timespec *timeout, int *uaddr2, int val3); • パラメタuadderの部分に、資源数を格納しているメモリのアドレス渡し ている • 実は、カーネル内部ではuadderをキーにしてwaitキューを作るようになっ ており、誰かが起床待ちになった時に作成、全員が起床されると破棄さ れる • つまり、競合状態にあるときのみ、カーネル内部の資源が作られる

Linuxのsemaphoreとmutexのまとめ • Linuxのsemaphoreの実装とは？ • アトミックインクリメント・ディクリメントによってほとんどの操作が 終わってしまう • 競合が発生しない限り、カウントアップorカウントダウンしかしないので、 速い • 競合が発生したときのみ、futexを使った待ち制御を行う • 競合が発生すると、システムコールを使うので遅くなる • RTOSの場合は？ • RTOSのsemaphoreはカーネルリソースで、資源数の管理も休眠・起床制 御もすべてカーネルが行う • 広域ロックをとって、カーネル内のキューを探索・変更するため、数が 少ないと性能がよくなる LinuxとRTOSでは、semaphoreに対する考え方が全く異なる

Linuxのsemaphoreとmutexのまとめ • これまでの流れで代替予想できると思いますが • Linuxのsemaphoreとmutexの実装は、ほとんど同じ • semaphoreはアトミックカウンタによる制御 • mutexは、アトミックカウンタの代わりにpid(tid)を格納 • 結局のところ、開放状態か否かがわかればやること(futexで寝る・起き る)は同じ • futexを作ると、カーネルリソースを使うが、競合しないと作らない RTOSの常識 semaphoreやmutexは極力減らして、リソース削減や動作効率をよくする Linuxの常識 ユーザ空間のsemaphoreやmutexは作りまくって競合をなくし、 リソース削減や動作効率をよくする