Operating System Lecture 11/21

Menu Menu


先週の復習 -- 同期


Binary Semaphor or Lock

BSD/OSのthreadでは、ロックを使って同期をおこなう。これはバイナリセマフォとも呼ばれる。セマフォには、P命令とV命令がある。このプログラムでは、セマフォを以下のように用いる。

     P命令
        きわどい部分 (critical section)
     V命令

pthreadのセマフォは、

     P命令    pthread_mutex_lock(pthread_mutex_t *mutex);
     V命令    pthread_mutex_unlock(pthread_mutex_t *mutex);

となってる。それぞれの引数は、初期化されたセマフォへのポインタである。


Count Semaphor

バイナリセマフォでは、P命令を実行して通過できるのはただ一つのprocess/thread だけである。しかし、資源がただ一つだけなく複数ある時には、複数のプロセスがP命令を実行できても良いと考えられる。この場合、P命令が消費に相当し、V命令が生産に相当する。この場合は、P命令を実行した回数とV命令を実行した回数は、最大N 個の差まで容認される。このようなセマフォを計数セマフォ(counting semaphor)という。

例えば、最初にN個の資源があり、生産者がN 個まで随時、資源を生成し、消費者がそれを消費していくとする。消費者は資源がある限り、それを同時に使用して良いという生産者消費者問題を考えよう。

生産者消費者問題は計数セマフォを使うことにより実現できるが、pthread には残念ながら計数セマフォはない。その代わり条件付き変数があるので、それを用いて計数セマフォを作成する。条件付き変数というのは歴史的な理由でそういう名前がついているのだが、これは同期を待ち合わせるprocess / thread のqueue (キュー)である。このキューには、条件付き変数
pthread_cond_wait(&sem->cond,&sem->mutex); 自分を待ち行列に加える。実行キューから取り除かれる
pthread_cond_signal(&sem->cond); 待ち行列から一つ取り出し、実行キューに加える

条件付き変数と、セマフォを組み合わせて計数セマフォを作る。cond は、待ち合わせを行う軽量プロセスのキューがである。

    typedef struct sem_t {
        int value;
        pthread_mutex_t mutex;  /* セマフォの値の整合性を得るためのロック */
        pthread_cond_t cond;    /* 待ち合わせのキューを作るための条件付き変数 */
    } sem_t,* sem_ptr;
    void sem_init(sem_t *,int);
    void sem_v(sem_t *);
    void sem_p(sem_t *);

計数セマフォの初期化は、資源の量を指定する。

    void
    sem_init(sem_t *sem,int value) 
    {
         pthread_mutex_init(&sem->mutex,NULL);
         pthread_cond_init(&sem->cond,NULL);
         sem->value = value;
    }

P動作、バイナリセマフォと違って、複数の待ち合わせが行われることがある。

    void
    sem_p(sem_t *sem) 
    {
        /* まずvalueをみるためだけにlockする */
        pthread_mutex_lock(&sem->mutex);
        while(sem->value == 0) {    /* もう、残ってない */
            /* 条件付き変数に自分を登録して、ロックを解放して、他の
               プロセスが資源を解放してくれるのを待つ */
            pthread_cond_wait(&sem->cond,&sem->mutex);
        } 
        /* 自分の分の資源があったので、それを確保する */
        sem->value--;
        pthread_mutex_unlock(&sem->mutex);
        /* ロックを解放する */
    }

V動作では、解放される資源は一つしかないので、一人だけしか起こす必要はない。

    void
    sem_v(sem_t *sem) 
    {
        /* まずvalueをみるためだけにlockする */
        pthread_mutex_lock(&sem->mutex);
        /* 資源を解放する */
        sem->value++;
        pthread_mutex_unlock(&sem->mutex);
        /* 他に資源が待って寝ている人がいれば、その人を起こす */
        pthread_cond_signal(&sem->cond);
    }

このように共有資源と同時に使わなくてはならないPosix threadの同期機構は非常にださい。計数セマフォのP/Vの処理に比べて非常に複雑な印象を受ける。しかし、たぶん、作った人の意図は、これらを用いて、より高度な同期機構を作って欲しいということなのだろう。それならば、条件付き変数の内容をより進んだ形で処理したいが、それは用意されていない。OSの設計者は、良くそういう手抜きをする。しかし、本来は同期機構は、その使い方といっしょに設計されるべきものである。


symbolic link を使った同期

Unix ではディレクトリは、どのプロセスからでも同じに見える。つまりディレクトリへのアクセスは、直列化されている。

これを利用して、symbolic link を使ったロックを実現する手法を示せ。


flock, pthread_mutex, symbolic link のそれぞれの同期について、用途、利点と欠点などについて議論せよ。


宿題

情報工学実験Iのプロセスの同期 を再来週までに行うこと。レポートはメールで

    Subject: Report Operating System Lecture 11/21

というように、課題を出した日付をサブジェクトに入れたメールで提出して下さい。


Shinji KONO / Tue Nov 21 13:25:45 2000