Operating System Lecture 11/27

Menu Menu

先週の復習

ガントチャート

Process Synchronization

複数のプロセス(process)は、単一のプロセッサ(Processor)、または、複数のプロセッサ上で動作している。このプロセスがおたがいに協調して動作するためには、なんらかの形で、プロセス同士のタイミングをとる必要がある。これを、プロセスの同期 (Sychronization)と呼ぶ。

何故、同期が必要なのか?
プログラムが、要求された仕様を満たすことを 整合(consistent) という。一般的な整合性(Consistency)は、並列に動作するプログラムが直列可能(Serializable)である場合にのみ得られる。並列環境下で直列可能性を保証するためには、同期機構が必要となる。(consitentの反対はinconsitent (矛盾)、従って、整合のことを無矛盾ともいう)
要求仕様の例

以下のような例を考えてみよう。 

    [操作A] 
    a = count;
    [操作B] 
    a += 1;
    [操作C] 
    count = a;
これを複数のユーザが同時に行うと困ったことが起きる。もちろん、プロセスの内部での実行順序はA,B,Cの順だが、それらはスケジューラによって分割されて、他のプロセスのA,B,Cと混じる(Interleaving)されることがある。 

    count は 256
    [操作A1]  by User 1
       count == 256
    [操作B1]  by User 1
       count == 256
    [操作C1]  by User 1
       count == 257
    [操作A2]  by User 2
       count == 257
    [操作B2]  by User 2
       count == 257
    [操作C2]  by User 2
       count == 258
もちろん、count は258になることが期待される。

問題

count が258以外になる操作の列を示せ。(これは、明らかにAやBが予期していたAが単独で操作ABCを行う結果とは異なる。)

同期は、いろいろなレベルで行われる。

これらはお互いに独立なわけではない。より高いレベルのものが、より低いレベルのものにより実装されるのが普通である。さまざまなレベルの同期機構を使っても、個々のレベルでの干渉がないことが保証される必要がある。しかし、それは自動的に保証されるわけではない。これらの機構のユーザが、それぞれを正しく使う必要がある。特に、低いレベルの実装はシステム全体のユーザに影響するので、完全なものである必要がある。

前の例の操作ABCのようなデータの変更のまとまりをというトランザクション(transaction)という。トランザクションは、それを順番にやったようになって欲しい。それが普通の直感である。この場合は、「1を加える」を2回おこなったのだから、2だけ値が増えてほしい。これを直列可能性(Serializability)という。 

 直列可能性が成立していれば、プログラムはトランザクション
の変更の積み重ねとなる。これは、トランザクションの積み重ねからプログラム全体ができていることを意味する。これをプログラムの無矛盾性(Consistency)という。ある条件のもとでConsistencyとSerializabilityは同値であることが証明されている。



これは、a1a2,b1b2 の二つのトランザクションが、s1→ s2の順序に依存するb1b2→ a1a2 という順序と、s2→ s3 によって生じるa1a2 → b1b2 という順序が矛盾していることから生じている。</P> 

 前の人の値を上書きしているという単純なことだが、このよう
に依存関係の矢印を書くことによって、より矛盾が明快になる。また、機械的に矛盾を見つける手順を提供することもできる。あたり前のことを明確にすることがコンピュータサイエンスでは重要なことが多い。

さまざまな同期機構

並列システムでは、Test-and-set または、read-modify-write というのが、ハードウェアレベルでは用いられている。これは、自分が書き込んだ値が相手に読まれることを保証している。これは、単なるatomic read, atomic write では実現できない。これらを用いて、Critical Section や Semaphor, Monitor を実現することができる。

逐次システム上の疑似並列システムでは、割り込まれない区間であるを作れば同期機構を作ることができる。これは、例えば割り込み禁止やcritical sectionにより実現する。

Test-and-set などでの待ち合わせは、CPUがそこを繰り返し読むことで行っても良い。これはspin-lockと呼ばれる。CPUを無駄に消費するが、同期待ちからの回復は、これが一番高速である。複数のCPUが、協調してspin-lock を行うのはBarrier と呼ばれる。これらの同期機構は、thread level で、並列プログラムのPerformance tuning を行う時に重要になる。

spin-lockでは無駄が大きくなる時には、プロセスを一旦、退避させる。この退避を抽象化した機構が、Semaphor である。Semaphor にはP動作とV動作がある。これは、Critical section へ入ることと出ることに相当する。さらに、これを Monitor という形でより柔軟な処理をおこなうことができる。Java などは言語レベルでCritical Section を採用している。(なぜ、Monitor を採用しなかったかは謎である) 並列オブジェクト指向言語では、オブジェクトをMonitor として扱う。

Guard は、lock や critical section などと異なり複数の条件を同時に待つことにより同期をおこなう。この機構は、より複雑な同期状況を実装するのにすぐれている。つまり表現能力が高い方法である。Unix の system call としては、select/listen というのがあり、これは一種の限られたGuradになっている。

通常プロセスでの共有資源

通常プロセスでの同期

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 のそれぞれの同期について、用途、利点と欠点などについて議論せよ。

宿題

「軽量プロセスの作成とスケジューリング」を、来週までに、おこなうこと。レポートはメールで 

    Subject: Practice on Operating System Lecture 11/20
というように、課題を出した日付をサブジェクトに入れたメールで提出して下さい。サブジェクトを間違えないこと!

宿題は毎週出るので提出が延びるとはまりますので気を付けてください。

Shinji KONO / Tue Dec 4 12:49:56 2001