セマフォ

セマフォは、E.W. ダイクストラ (Dijkstra) が 1960 年代の終わりごろに考案したプログラミング手法です。ダイクストラのセマフォモデルは、鉄道線路の運行をモデル化したものです。一度に一本の列車しか走れない単線の鉄道線路を思い浮かべてください。

この鉄道線路を保護するのがセマフォです。列車は単線区間に入るとき、セマフォの状態が進行許可状態になるのを待たなければなりません。列車が単線区間に入るとセマフォの状態は、他の列車が単線区間に入るのを禁止する状態に変化します。単線区間から出る列車は、セマフォの状態を進行許可状態に戻して他の列車が単線区間に入ることができるようにしなければなりません。

コンピュータ内のセマフォは、単一の整数で表現されます。スレッドは進行が許可されるのを待ち、その後進行したことを知らせるためにセマフォに対して P 操作を実行します。

この操作をもう少し具体的に説明しましょう。スレッドは、セマフォの値が正になるのを待たなければなりません。その後 1 を引くことでセマフォの値を変更します。これが P 操作です。処理を完了したセマフォは、V 操作を実行します。この操作は 1 を加えることでセマフォの値を変更します。ここで必ず守らなければならないことがあります。これらの各操作を原子的操作により行うことです。これは操作が分断されると、操作途中にセマフォに対する別の操作が行われる危険性があるからです。P 操作では、1 を引く直前のセマフォの値が正でなければなりません (結果的に、引いた後の値が負にならないことと、その値が引く前の値よりも 1 だけ小さいことが保証されます)。

P 操作と V 操作のどちらの演算操作でも干渉が生じないようにしなければなりません。たとえば、同じセマフォに対して 2 つの V 操作が同時に行われた場合、そのセマフォの新しい値は最初よりも 2 だけ大きくなっていなければなりません。

ダイクストラがオランダ人だったこともあり、P と V の記号的な意味は現在ではほとんど忘れられています。参考までに、P はオランダ語の「prolagen」という単語を表します。その語源は「proberen te verlagen」で、「小さくする」という意味です。また、V は「verhogen」を表し、「大きくする」という意味です。このことは、ダイクストラのテクニカルノート『EWD 74』で説明しています。

sema_wait(3R) と sema_post(3R) は、ダイクストラの P 操作と V 操作にそれぞれ対応しています。また、sema_trywait(3R) は、P 操作の条件付きの形式です。この関数は、呼び出しスレッドがセマフォの値を差し引くために待たなければならない場合は、ただちに 0 以外の値を返します。

セマフォは、2 進セマフォとカウント用セマフォの 2 種類に大別されます。2 進セマフォは 0 と 1 のどちらかの値しかとりません。一方、カウント用セマフォは負以外の任意の値をとることができます。2 進セマフォは、論理的には相互排他ロック (mutex ロック) と似ています。

必須要件ではありませんが、mutex はロックを保持しているスレッドだけがそのロックを解放すべきものです。一方、セマフォには「スレッドがセマフォを保持している」という概念がないので、どのスレッドも V 操作 (すなわち、sem_post(3R)) を実行できます。

カウント用セマフォは、mutex とともに使用される条件変数と同等の能力があります。多くの場合、条件変数よりもカウント用セマフォを使用した方がコードが簡素化されます (詳細は、後述の例を参照してください)。

mutex とともに条件変数を使用する場合は、プログラムのどの部分を保護するかが自然な形で明らかになりました。ところが、セマフォでは必ずしもそうはなりません。強力だからといって安易に使うとプログラムが不統一で理解しにくくなります。このため、「並行プログラミングにおける goto」と呼ばれています。

計数型セマフォ

セマフォは、負の値をとらない整数のカウンタと考えることができます。通常は、資源に対するアクセスの調整をはかる目的で、次のように使用されます。最初に、使用可能な資源の数をセマフォに初期設定します。その後、スレッドは資源が追加されるときにセマフォの値を原子的操作によって 1 増やし、資源が削除されるときに原子的操作によって 1 減らします。

セマフォの値が 0 になった場合は、資源がないことを意味します。この場合、セマフォの値を 1 減らそうとすると、スレッドはセマフォの値が 0 より大きくなるまでブロックされます。

表 4-7 セマフォに関するルーチン

「セマフォの初期化」	「sem_init(3R)」
「セマフォの加算」	「sem_post(3R)」
「セマフォの値によるブロック」	「sem_wait(3R)」
「セマフォの減算」	「sem_trywait(3R)」
「セマフォの削除」	「sem_destroy(3R)」

セマフォは、その獲得と解放を同じスレッドで行う必要がないため、シグナルハンドラで行われているような非同期のイベント通知を実現できます。また、セマフォ自身が状態を持っているため、条件変数を使用する場合と違って相互排他ロックを獲得しなくても非同期で使用できます。ただし、セマフォは相互排他ロックほど効率的ではありません。

セマフォで複数のスレッドがブロックされているとき、それらのスレッドがどの順番でブロック解除されるかは、特に指定しなければ不定です。

セマフォは、使用する前に初期化されている必要がありますが、属性はありません。

セマフォの初期化

sem_init(3R)

プロトタイプ:
int	sem_init(sem_t *sem, int pshared, unsigned int value);

#include <semaphore.h>

sem_t sem;
int pshared;
int ret;
int value;

/* セマフォの初期化 */
pshared = 0;
value = 1;
ret = sem_init(&sem, pshared, value); 

sem_init() は、sem が指すセマフォ変数を value の値に初期設定します。pshared の値が 0 なら、そのセマフォはプロセス間で共有できません。pshared の値が 0 以外なら、そのセマフォはプロセス間で共有できます。

複数のスレッドから同じセマフォを初期化してはいけません。

また、一度初期化したセマフォは、他のスレッドで使用されている可能性があるので再初期化してはいけません。

戻り値

正常終了時は 0 です。それ以外の戻り値は、エラーが発生したことを示します。以下の条件のいずれかが検出されると、この関数は失敗し、次の値を戻します。

EINVAL

value の値が SEM_VALUE_MAX を超えています。

ENOSPC

そのセマフォを初期化するのに必要な資源が使い果たされています。セマフォの制限 SEM_NSEMS_MAX に達しています。

EPERM

そのセマフォを初期化するのに必要な特権をそのプロセスがもっていません。

プロセス間スコープでセマフォを初期化する

pshared の値が 0 の場合は、そのプロセス内のスレッドだけがそのセマフォを使用できます。

#include <semaphore.h>

sem_t sem;
int ret;
int count = 4;

/* このプロセスでのみ使用 */
ret = sem_init(&sem, 0, count); 

プロセス間スコープでセマフォを初期化する

pshared の値が 0 以外の場合は、他のプロセスによってそのセマフォは共有されます。

#include <semaphore.h>

sem_t sem;
int ret;
int count = 4;

/* プロセス間で共有 */
ret = sem_init(&sem, 1, count);

名前付きセマフォ

sem_open(3R)、sem_getvalue(3R)、sem_close(3R)、sem_unlink(3R) の各関数が、名前付きセマフォを開く、取得する、閉じる、削除するのにそれぞれ使用できます。sem_open() では、ファイルシステムの名前空間で名前が定義されたセマフォを生成できます。

名前付きセマフォはプロセス間で共有されるセマフォに似ていますが、pshared 値ではなくパス名で参照される点が異なります。

名前付きセマフォの詳細は、sem_open(3R)、sem_getvalue(3R)、sem_close(3R)、sem_unlink(3R) のマニュアルページを参照してください。

セマフォの加算

sem_post(3R)

プロトタイプ:
int	sem_post(sem_t *sem);

#include <semaphore.h>

sem_t sem;
int ret;

ret = sem_post(&sem); /* セマフォを加算する */

sem_post() は、sem が指すセマフォの値を原子的操作によって 1 増やします。そのセマフォでブロックされているスレッドがある場合は、そのスレッドのうちの 1 つのスレッドがブロック解除されます。

戻り値

正常終了時は 0 です。それ以外の戻り値は、エラーが発生したことを示します。以下の条件が検出されると、この関数は失敗し、次の値を戻します。

EINVAL

sem が指すアドレスが正しくありません。

セマフォの値によるブロック

sem_wait(3R)

プロトタイプ:
int	sem_wait(sem_t *sem);

#include <semaphore.h>

sem_t sem;
int ret;

ret = sem_wait(&sem); /* セマフォの値の変化を待つ */

sem_wait() は、sem が指すセマフォの値が 0 より大きくなるまでスレッドをブロックし、0 より大きくなったらセマフォの値を原子的操作によって 1 減らします。

戻り値

正常終了時は 0 です。それ以外の戻り値は、エラーが発生したことを示します。以下のいずれかの条件が検出されると、この関数は失敗し、次の値を戻します。

EINVAL

sem が不当なアドレスを指しています。

EINTR

シグナルによってこの関数が割り込まれました。

セマフォの減算

sem_trywait(3R)

プロトタイプ:
int	sem_trywait(sem_t *sem);

#include <semaphore.h>

sem_t sem;
int ret;

ret = sem_trywait(&sem); /* セマフォの値の変化を待つ */

sem_trywait() は、sem が指すセマフォの値が 0 より大きい場合は原子的操作によって 1 減らします。この関数はブロックしない点を除いて、sem_wait() と同じ働きをします。つまり、失敗した場合にはすぐに戻ります。

戻り値

正常終了時は 0 です。それ以外の戻り値は、エラーが発生したことを示します。以下のいずれかの条件が検出されると、この関数は失敗し、次の値を戻します。

EINVAL

sem が不当なアドレスを指しています。

EINTR

シグナルによってこの関数が割り込まれました。

EAGAIN

そのセマフォはすでにロックされているので、sem_trywait() でただちにロックできません。

セマフォの削除

sem_destroy(3R)

プロトタイプ:
int	sem_destroy(sem_t *sem);

#include <semaphore.h>

sem_t sem;
int ret;

ret = sem_destroy(&sem); /* セマフォを削除する */

sem_destroy() は、sem が指すセマフォを削除します。セマフォの記憶領域は解放されません。

戻り値

正常終了時は 0 です。それ以外の戻り値は、エラーが発生したことを示します。以下の条件が検出されると、この関数は失敗し、次の値を戻します。

EINVAL

sem が指すアドレスが正しくありません。

「生産者 / 消費者」問題 − セマフォを使った例

例 4-14 のデータ構造は、条件変数による「生産者 / 消費者」問題のコード例 (例 4-11 参照) のデータ構造と似ています。2 つのセマフォでそれぞれ、バッファの使用済スロット数と未使用スロット数を表します。これらのセマフォは、未使用スロットができるまで生産者を待たせ、使用済スロットができるまで消費者を待たせます。

---

例 4-14 「生産者 / 消費者」問題 − セマフォを使った例

typedef struct {
    char buf[BSIZE];
    sem_t occupied;
    sem_t empty;
    int nextin;
    int nextout;
    sem_t pmut;
    sem_t cmut;
} buffer_t;

buffer_t buffer;

sem_init(&buffer.occupied, 0, 0);
sem_init(&buffer.empty,0, BSIZE);
sem_init(&buffer.pmut, 0, 1);
sem_init(&buffer.cmut, 0, 1);

buffer.nextin = buffer.nextout = 0;

---

ここでは、もう一組の (バイナリ) セマフォを使用しています。これは 2 値型セマフォで、相互排他ロック (mutex ロック) と同じ働きをします。この 2 つのセマフォは、複数の生産者と複数の未使用スロットが存在する場合と、複数の消費者と複数の使用済みスロットが存在する場合に、バッファへのアクセスを制御します。本来このような場合では mutex を使用すべきですが、セマフォの使用例を示すために特に使用しています。

---

例 4-15 「生産者 / 消費者」問題 − 生産者

void producer(buffer_t *b, char item) {
    sem_wait(&b->empty);
   sem_wait(&b->pmut);

    b->buf[b->nextin] = item;
    b->nextin++;
    b->nextin %= BSIZE;

    sem_post(&b->pmut);
   sem_post(&b->occupied);
}

---

---

例 4-16 「生産者 / 消費者」問題 − 消費者

char consumer(buffer_t *b) {
    char item;

    sem_wait(&b->occupied);
   
    sem_wait(&b->cmut);

    item = b->buf[b->nextout];
    b->nextout++;
    b->nextout %= BSIZE;

    sem_post(&b->cmut);

    sem_post(&b->empty);

    return(item);
}

---