プロセス間の同期・通信
Menu Menu
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. 実験
この実験で用いるファイルは、 /net/open/classes/slab/info1/6-synch にある。次のようにして、各自、自分のホームディレクトリの下に、この実験用のディレクトリを作りなさい。そして、上のディレクトリにあるファイルをコピーしなさい。
% 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 は、ここ である。
#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 に、セマフォを使った生産者消費者問題の解の一部を示す。このプログラムの生産者プロセスの部分は完成されている。課題は、消費者プロセスの部分を完成させることである。以下に半完成のプログラム 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 についても説明すること)、および、その実行結果を付けなさい。ソースの場所は、明示すること。この実験では、プログラムの説明では、フローチャートを付加する必要はない。開発環境と実行環境 (計算機、オペレーティング・システムのバージョン、コンパイラ)を載せなさい。それぞれの実験について、プログラム作成に要した時間を書きなさい。
一般的な注意
報告書は、日本語または英語で記述すること。プログラム、表、図、数式の羅列は、報告書とは認めない。図は必ず本文から参照すること。数学における証明のように、示すべき結論、用いる仮定と前提、推論の詳細について論理的に記述しなさい。