Operating System Lecture 5/29

先週の復習 -- Scheduling

• Frist come, First serve
• Shortest job first
• Round robing
• dead-line
• reate monononic

• Dead line scheduling
• Rate monotinic scheduling

問題

以下の定期的に要求されるPeriodical プロセスをRate monotonic shcedulingと Dead line scheduling により実行するとどうなるかをGunt chartを 使って表せ。

Process     Period        CPU unit
1           10            3
2           5             1
3           4             3
4           7             2

Process Synchronization

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

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

• Hardware level
  • read-modify-write
  • bus arbitration
  • switching network
• Memory level
  • read-modify-write
  • spin-lock
• thread level, kernel level
  • semaphor
  • critical-section
  • schedular
  • barrier
  • fuzzy barrier
• programming language level
  • monitor
  • guard
  • trigger
  • message passing
• process level
  • lock
  • select
  • wait
  • read-wait

何故、同期が必要なのか?

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

要求仕様の例

• 周辺LSIのC0レジスタに、10byteのコマンドを逐次書き込む
• 預金口座の入金-出金は、残高に等しい
• すべてのプロセスが終了した後に、コマンドaを実行する

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

[操作A] 
a = count;
[操作B] 
count += 1;
[操作C] 
count = a;

count は 256
[操作A1]  by User A
[操作A2]  by User B
[操作B1]  by User A
[操作B2]  by User B
[操作C1]  by User A
[操作C2]  by User B
count は ?

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

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

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

さまざまな同期機構

並列システムでは、 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命令

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

Count Semaphor

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

生産者消費者問題は計数セマフォを使うことにより実現できるが、 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;
    }

    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);
        /* ロックを解放する */
    }

    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);
    }

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

• ファイル
• device
• socket
• mmap
• named pip
• shared memory

通常プロセスでの同期

• fork / wait
• flock, lockf, ioctl
• select
• SYS V IPC
  • semaphor
  • shared memory
  • message

宿題

情報工学実験Iの 4.4 相互排除と 4.5 プロセス間の同期問題を行うこと。 おこなうこと。この実験は nirai/kanai または、pw/nw でおこなうこと。 レポートはメールで

    Subject: Report Operating System Lecture 5/29