-title: プロセス間の同期・通信

--1. 目的

この実験では、軽量プロセスを用いて、基本的なプロセス間の同期について
学ぶ。C言語によりセマフォを用いるプログラムを作成する。

--2. 関連科目

   情204  オペレーティング・システム  必修2単位

--3. 準備

プロセス間の同期とプロセス間通信の概念をつかみなさい。プロセス
間の同期と通信に関する次のキーワードの意味を調べなさい。

   相互排除  (mutal exclusion )
   セマフォ、計数セマフォ、P命令、V命令 (semaphor)
   生産者消費者問題  (producer consumer problem )
   軽量プロセスとコルーチン  (light weight process, co-routine )
   プロセス切り替え (コンテキスト切り替え) (context switch)
   横取り (preemptive )
   バリア同期

通常の重いプロセスの場合は、以下のようなキーワードが重要である。

   フォークとジョイン  (fork join)
   ソケット (socket )
   ストリーム通信とセレクト (stream select)
   ロック lock ( lockf, flock )

これらは、3年の実験でさまざまなプログラムをすることになる。

--4. 実験

この実験で用いるファイルは、
<a href="src/"> /net/open/classes/slab/info1/6-synch </a>
にある。次のようにして、各自、自分のホームディレクトリの下に、
この実験用のディレクトリを作りなさい。そして、上のディレクトリに
あるファイルをコピーしなさい。

   % mkdir  ~/実験用ディレクトリ
   % cd ~/実験用ディレクトリ
   % cp /net/open/classes/slab/info1/6-synch/* .

ここで実験用ディレクトリには、各自、自分で考えた名前を付けなさい。
他のじっっ権と混ざらないように、実験日ごとにディレクトリを作りなさい。
そうしなければ、Makefile のような同じ名前のファイルが上書きされる
不都合が起きる可能性がある。

この実験では、POSIX準拠のpthread を使う。これは、SunのSolalirs
または、BSD/OS で動作する。

--4.1 相互排除

次のようにして、mp-sem-mutex をコンパイルし、実行して見なさい。

   % make mp-sem-mutex
   % ./mp-sem-mutex
   process_A() done. shared_resource == 5.
   process_B() done. shared_resource == 5.

mp-sem-mutex.c は、href="src/mp-sem-mutex.c" ここ である。

    #include <stdio.h>
    #include <pthread.h>

ptread を使うためには、 pthread.h が必要である。
これはどこにあるのだろうか?  また、どういうことが書いてあるのだろうか?

    void ready_print();
    void *process_A(void *), *process_B(void *);
    pthread_t thread_a,thread_b;

共有資源を使う二つのthreadを定義している。

    int shared_resource ;       /* 共有資源 */

これが共有資源となる。

    pthread_mutex_t     mutex ;                 /* 相互排除用の計数セマフォ */

これが共有資源を相互排除するためのsemaphorである。

    int
    main(int ac,char *av[])
    {
        /* 計数セマフォの初期化する。初期値を１にすると
                                 * バイナリ・セマフォと同じ
                                 */
        pthread_mutex_init(&mutex, NULL);

semaphorの初期化である。

        pthread_create(&thread_a, NULL, &process_A, NULL);
        pthread_create(&thread_b, NULL, &process_B, NULL);
        pthread_join(thread_a, NULL);
        pthread_join(thread_b, NULL);
    }

二つのthreadを生成する。また終了を待ち合わせる。待ち合わせが終了
するとmain()は終了する。

以下のプロセスでは、二つのプロセスが並列に共有資源である
整数の変数に1 を加える動作をする。

以下の sched_yield() の呼び出しは、プロセス切り替えが起きる可能性があ
る場所を示す。sahred_resoruce++ と記述してもハードウェアレベルでは、こ
のように三つの段階に分割されて実行される。

相互排除を実現するためには、そのためのハードウェア的なサポートが必要で
ある。そのための基本的な命令が機械語レベルで用意されていることもある。
read-modify-write などと呼ばれる命令が用意されていることが多い。
OSのカーネル内部での相互排除は、ハードウェアレベルで実現されている
必要がある。


    void *
    process_A(void *arg)
    {
         int i ;
         register int x ;
            for( i=0 ; i<5 ; i++ )
            {
                x = shared_resource ;   /* 共有資源の読み出し */
        sched_yield();
                x = x + 1 ;                     /* １を加える */
        sched_yield();
                shared_resource = x ;   /* 共有資源に書き戻す */
        sched_yield();
            }
            printf("process_A() done. shared_resource == %d.\n",
                    shared_resource );
    }

    void *
    process_B(void *arg)
    {
         int i ;
         register int x ;
            for( i=0 ; i<5 ; i++ )
            {
                x = shared_resource ;
        sched_yield();
                x = x + 1 ;
        sched_yield();
                shared_resource = x ;
        sched_yield();
            }
            printf("process_B() done. shared_resource == %d.\n",
                    shared_resource );
    }

このプログラムは、メイン部分で、process_A(),process_B()の2個の
軽量プロセスを生成している。各プロセスは、sahred_resourceという
変数を呼び出し、その内容に1を加え、もう一度 shared_resoruce
を書き戻している。(ここでは、まず sched_yield() を無視して
考えて良い) 5回ループを回るので、一つのプロセスにき
5回、2つのプロセスにより合計10回、1を加える動作が行われる。
これにより、shared_resource は、10加えられ、最終的に値が
10になることが期待される。ところが、プログラムを実行してみると
わかるように、実際には5しか増えていない。

このように10増えて欲しい所、実際に5しか増えてないことは、2つのプロセス
が並列(同時に)実行されることを考えると理解しやすい。共有メモリ型マルチ
プロセッサと呼ばれる計算機では、複数のCPUがあるため、実際に2つのプロセ
スは、物理的に並列に実行されることがある。nirai, kanaiは4つのCPUをそれ
ぞれ持っていて、は、物理的に並行に実行される可能性がある。

BSD/OSを使う場合には、単一プロセッサシステムなので、並列動作は、タイム
シェアリング(time sharing system, TSS)という手法による一種のシミュレー
ションで行われる。これは、CPUの横取り (preemptive-dispatch )とも呼ばれ
る機構により実現される。横取りは、時間、あるいは、I/O関係の割り込み、
そして、軽量プロセスの場合は、自発的な資源の解放により起こる。

このプログラムでは、shced_yield() により自発的にCPU資源を解放している。
この時点でCPUの横取りが起きると考えて良い。それ以外の場所で横取り
が起きるかどうかは軽量プロセスの実装によるが、プログラミングは、
任意の時点で横取りが起きる可能性があると考えて行うべきである。
もし、並列動作により、共有資源の奪い合いが起きる場合は、必ず
同期処理が必要になる。

---課題1 相互排除を行わないプログラムの実行の考察

上のプログラムを、単一プロセッサ情で動作させた時の動作について
考察しなさい。


上のプログラムを 
                shared_resource++ ;
の形に書き換える。

gcc -S 使ってをコンパイルして、この状態で、Multi CPU 上で、
実行し、shared_resource の結果が正しくないことがあることを
確認せよ。

さらに、アセンブラソース上で、同期命令を付加し、正しい
結果が出ることを確認せよ。


---課題2 セマフォによる相互排除

上のプログラムにセマフォの同期命令を入れることで、相互排除
を行い、5しか増えてない問題を解決しなさい。

セマフォには、教科書にあるようにP命令とV命令がある。このプログラム
では、セマフォを以下のように用いる。

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

pthreadのセマフォは、
     P命令    pthread_mutex_lock(pthread_mutex_t *mutex);
     V命令    pthread_mutex_unlock(pthread_mutex_t *mutex);
となってる。それぞれの引数は、初期化されたセマフォへのポインタ
である。

課題は、共有資源を利用している間の相互排除を実現することである。以下の 
process_A(), process_B() のプログラムの適当な所に、
     pthread_mutex_lock(pthread_mutex_t *mutex);
     pthread_mutex_unlock(pthread_mutex_t *mutex);
の呼び出しを挿入しなさい。この時に、shced_yield() を任意の場所に
挿入しても共有資源が正しく同期していることを確認しなさい。例えば、

      A;
   shced_yield();
      B;

に pthread_mutex_lock(pthread_mutex_t *mutex); を挿入する時に、

      A;
   shced_yield();
   pthread_mutex_lock(pthread_mutex_t *mutex);
   shced_yield();
      B;

というようにしても、ちゃんと動作すること。






---課題3 生産者消費者問題

mp-sem-prodcons.c に、セマフォを使った生産者消費者問題の
解の一部を示す。このプログラムの生産者プロセスの部分は
完成されている。課題は、消費者プロセスの部分を完成させる
ことである。以下に半完成のプログラム  
href="src/mp-sem-prodcons.c" mp-sem-prodcons.c 
を示す。

生産者消費者問題は計数セマフォを使うことにより実現できるが、
pthread には残念ながら計数セマフォはない。その代わり条件付き
変数があるので、それを用いる。


    /*
            mp-sem-prodcons.c -- セマフォを使った生産者消費者問題の解
            $Header: /net/home/cvs/teacher/kono/os/ex/synch/sync.ind,v 1.1.1.1 2007/12/18 03:39:43 kono Exp $
            Start: 1995/03/01 19:54:55
    */

    #include <stdio.h>
    #include <pthread.h>

    void *consumer(void *);
    void *producer(void *);
    pthread_t thread_consumer,thread_producer;

    #define BUFFSIZE 3  /* バッファの大きさ, 教科書では N */
    int i_p ;           /* 書き込む位置, 教科書では i */
    int j_c ;           /* 読み出す位置, 教科書では j */

    /*
            POSIX thread にはセマフォがないので、自分で作ります。
     */

条件付き変数と、セマフォを組み合わせて計数セマフォを作る。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);
    }

    sem_t mutex_c ;             /* 生産者間の相互排除, 教科書では a  */
    sem_t mutex_p ;             /* 消費者間の相互排除, 教科書では b  */
    sem_t rem ;         /* バッファの空き容量, 教科書では e */
    sem_t count ;               /* バッファ内のデータ数, 教科書では f */
    int buffer[BUFFSIZE] ;      /* バッファ */

    int nloop = 10 ;    /* 何回繰り返して止るか */

    int
    main(int ac,char *av[])
    {
    /* mp_user_main() は、軽量プロセスを２個作り終了する。*/
            j_c = 0 ;
            i_p = 0 ;

            sem_init( &mutex_p,1 );     /* 相互排除用のセマフォの初期化 */
            sem_init( &mutex_c,1 );     /* 相互排除用のセマフォの初期化 */
            sem_init( &rem,BUFFSIZE ); /* バッファの空きは、Ｎ, e=0 */
            sem_init( &count,0 );       /* バッファは空, f=0 */

            pthread_create(&thread_consumer, NULL, &consumer, NULL);
            pthread_create(&thread_producer, NULL, &producer, NULL);
            pthread_join(thread_consumer, NULL);
            pthread_join(thread_producer, NULL);
    }

    void *
    producer(void *arg) /* 生産者プロセス */
    {
        int x ;
        int i ;
            x = 0 ;
            fprintf(stderr,"producer(): started.\n");
            for( i=0 ; i<nloop ; i++ )
            {
                sem_p( &rem );  /* 空きができるのを待つ */
                sem_p( &mutex_p );      /* 生産者間の相互排除 */
                x = i * 2 ;             /* 次の情報を生産する。*/
                fprintf(stderr,"producer(): put %d.\n", x );
                buffer[i_p] = x ;       /* バッファに情報を入れる */
                i_p++ ;         /* i_p = (i_p+1) % BUFFSIZE */
                if( i_p>=BUFFSIZE )
                    i_p = 0 ;
                sem_v( &mutex_p );      /* 生産者間の相互排除 */
                sem_v( &count );        /* 情報を入れたことを伝える */
            }
    }

    void *
    consumer(void *arg) /* 消費者プロセス */
    {
    /*
    課題は、この部分を完成させることである。最終的に生産者と消費者は、対称
    的なプログラムになるはずである。
    */
    }

mp-sem-prodcons.cのコンパイル方法、実行方法を以下に示す。(この
プログラムは未完成であり、そのままでは動作しない)

    % make mp-sem-prodcons
    % ./mp-sem-prodcons

プログラムのテスト中に、プログラムの動作が進まなくなることもありえる。
これは、デッドロック(dead-lock) と呼ばれる。また、複数のthreadが
動作しているのだが、全体として動作が進まなくなる場合もある。これは、
ライブロック(live-lock)といわれる。

---課題4 複数の生産者と複数の消費者

課題3では、生産者と消費者プロセスがそれぞれ1つづつしか生成されない。
これを変更して、複数の生産者プロセスと複数の消費者プロセスを
生成し、動作させなさい。

生産者プロセスと消費者プロセスの数は異なる場合が普通である。しかし、
生産量と消費量がバランスしないとデッドロックに陥る可能性がある。

---報告書

それぞれの実験に付いて、作成したプログラム、その説明 (Makefile
についても説明すること)、および、その実行結果を付けなさい。
ソースの場所は、明示すること。
この実験では、プログラムの説明では、フローチャートを付加する
必要はない。開発環境と実行環境 (計算機、オペレーティング・
システムのバージョン、コンパイラ)を載せなさい。それぞれの
実験について、プログラム作成に要した時間を書きなさい。

---一般的な注意

報告書は、日本語または英語で記述すること。プログラム、
表、図、数式の羅列は、報告書とは認めない。図は必ず
本文から参照すること。数学における証明のように、
示すべき結論、用いる仮定と前提、推論の詳細について
論理的に記述しなさい。