test

マルチスレッドのプログラミング

セマフォーによる同期

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

この鉄道線路上の運行の同期を取るのがセマフォー (腕木信号機) です。列車は単線区間に入るとき、セマフォーの状態が進行許可状態になるのを待たなければなりません。列車が単線区間に入るとセマフォーの状態は、ほかの列車が単線区間に入るのを禁止する状態に変化します。単線区間から出る列車は、セマフォーの状態を進行許可状態に戻して、ほかの列車が単線区間に入ることができるようにしなければなりません。

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

スレッドは、セマフォーの値が正になるのを待たなければなりません。その後、値から 1 を引いて、セマフォーの値を変更します。処理を完了したセマフォーは、V 操作を実行します。この操作は 1 を加えることでセマフォーの値を変更します。これらの操作は不可分的に行う必要があります。これらの操作を分割して、次の操作までの間に、セマフォーに対してその他のアクションが実行されるようなことがあってはなりません。P 操作では、1 を引く直前のセマフォーの値が正でなければなりません。結果的に、引いた後の値が負にならないことと、その値が引く前の値よりも 1 だけ小さいことが保証されます。

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

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

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

セマフォーは、大きく 2 つに分類できます。1 つは 2 進型セマフォーで、0 および 1 以外の値はとりません。もう 1 つは計数型セマフォーで、0 以上の任意の値をとります。2 進型セマフォーは、論理的に mutex と同じです。

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

計数型セマフォーは、mutex とともに使用される条件変数と同等の能力があります。多くの場合、条件変数よりも計数型セマフォーを使用した方がコードが簡素化されます。例 4–14、例 4–15、例 4–16 を参照してください。

しかし、mutex を条件変数といっしょに使用した場合は、暗黙のくくりが存在します。このくくりは、プログラム内で保護されている部分を明確に区別します。この動作はセマフォーに限定されたものではなく、「並行プログラミングにおける go to」と呼ばれることがあります。セマフォーは強力ですが、構造化されないあいまいな方法で使用してしまいがちです。

名前付きセマフォーと名前なしセマフォー

POSIX セマフォーは、名前付きの場合と名前なしの場合があります。名前なしセマフォーは、プロセスメモリー内で割り当てられ、初期化されます。名前なしセマフォーは、割り当てと初期化の状態によっては、複数のプロセスで使用できます。名前なしセマフォーは、fork() から継承された専用セマフォーであるか、またはその割り当てとマッピングが行われた通常ファイルのアクセス保護によって保護されたセマフォーです。

名前付きセマフォーはプロセス間で共有されるセマフォーに似ていますが、pshared 値ではなくパス名で参照される点が異なります。名前付きセマフォーは、複数のプロセスによる共有が可能です。名前付きセマフォーは、固有のユーザー ID、グループ ID、および保護モードを持ちます。

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

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

計数型セマフォーの概要

セマフォーの概念は、0 以上の整数カウントです。通常は、リソースに対するアクセスの調整をはかる目的で、次のように使用されます。最初に、使用可能なリソースの数をセマフォーに初期設定します。スレッドは、リソースが追加されると不可分操作的にカウントを 1 加算し、リソースが削除されると不可分操作的に 1 減算します。

これ以上リソースが存在しなくなると、セマフォーカウントは 0 になります。この場合、スレッドがカウントを 1 減らそうとすると、カウントが 0 より大きくなるまでブロックされます。

表 4–6 セマフォーに関するルーチン

操作 

参照先 

セマフォーの初期化 

「sem_init の構文」

セマフォーの加算 

「sem_post の構文」

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

「sem_wait の構文」

セマフォーの減算 

「sem_trywait の構文」

セマフォーの削除 

「sem_destroy の構文」

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

スケジューリングポリシーは、ブロックされたスレッドがどのように呼び起こされるかを決定します。デフォルトスケジューリングポリシー SCHED_OTHER は、スレッドが呼び起こされる順序を指定していません。SCHED_FIFO および SCHED_RR リアルタイムスケジューリングポリシーの下では、スレッドは優先順位に従って呼び起こされます。

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

セマフォーの初期化

sem が指す名前なしセマフォー変数を value の値に初期化するには、sem_init(3RT) を使用します。

sem_init の構文

int sem_init(sem_t *sem, int pshared, unsigned int value);
#include <semaphore.h>

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

/* initialize a private semaphore */
pshared = 0;
value = 1;
ret = sem_init(&sem, pshared, value);

pshared の値が 0 なら、そのセマフォーはプロセス間で共有できません。pshared の値が 0 以外なら、そのセマフォーはプロセス間で共有できます。

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

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

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

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

#include <semaphore.h>

sem_t sem;
int ret;
int count = 4;

/* to be used within this process only */
ret = sem_init(&sem, 0, count);

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

pshared が 0 以外の場合、セマフォーは複数のプロセスで共有可能です。

#include <semaphore.h>

sem_t sem;
int ret;
int count = 4;

/* to be shared among processes */
ret = sem_init(&sem, 1, count);

sem_init の戻り値

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


EINVAL

説明:

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


ENOSPC

説明:

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


EPERM

説明:

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

セマフォーの加算

sem が指すセマフォーを不可分的に加算するには、sem_post(3RT) を使用します。

sem_post の構文

int sem_post(sem_t *sem);
#include <semaphore.h>

sem_t sem;
int ret;

ret = sem_post(&sem); /* semaphore is posted */

そのセマフォーでブロックされているスレッドがある場合は、そのスレッドのうちの 1 つのスレッドがブロック解除されます

sem_post の戻り値

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


EINVAL

説明:

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

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

sem が指すセマフォーカウントが 0 より大きくなるまで呼び出しスレッドをブロックし、0 より大きくなったら不可分的にカウントを減らすには、sem_wait(3RT) を使用します。

sem_wait の構文

int sem_wait(sem_t *sem);
#include <semaphore.h>

sem_t sem;
int ret;

ret = sem_wait(&sem); /* wait for semaphore */

sem_wait の戻り値

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


EINVAL

説明:

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


EINTR

説明:

この関数にシグナルが割り込みを行いました。

セマフォーの減算

sem が指すセマフォー内のカウントが 0 より大きいときにこの値を不可分的に減らすには、sem_trywait(3RT) を使用します。

sem_trywait の構文

int sem_trywait(sem_t *sem);
#include <semaphore.h>

sem_t sem;
int ret;

ret = sem_trywait(&sem); /* try to wait for semaphore*/

この関数はブロックしない点を除いて、sem_wait() と同じ働きをします。つまり、失敗した場合にはただちに終了します。()

sem_trywait の戻り値

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


EINVAL

説明:

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


EINTR

説明:

この関数にシグナルが割り込みを行いました。


EAGAIN

説明:

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

セマフォーの削除

sem が指す名前なしセマフォーに関連付けられた状態を削除するには、sem_destroy(3RT) を使用します。

sem_destroy の構文

int sem_destroy(sem_t *sem);
#include <semaphore.h>

sem_t sem;
int ret;

ret = sem_destroy(&sem); /* the semaphore is destroyed */

セマフォーの記憶領域は解放されません。

sem_destroy の戻り値

sem_destroy() は、正常終了時に 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 として使用しています。このセマフォーは、複数の生産者が複数の空バッファースロットを使用するときと、複数の消費者が複数のいっぱいになったバッファースロットを使用するときのバッファーへのアクセスを制御します。本来このような場合では 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);
}