Principles of Concurrent and Distributed Programming

study PCDP

Chapter3 The Mutual Exclusion Problem

3.1 Introduction
  • Mutexの実装方法について議論する

1. Critical_Sections の中の処理は2プロセス以上にinterleavedされてはならない(同時に実行されてはならない）
2. Critical_Sectionは？？(英語が読めない…）
3. プロセスは、Non_Critical_Section内で終了する可能性がある。たとえ終了したとしても、ほかのプロセスに影響を与えてはならない。
4. プログラムはdeadlockしてはならない。
5. ひとつのプロセスのリクエストがずっと付与されない状況(飢餓)になってしまってはならない。(There must be no starvation of one of the processes).
6. 他のだれもリクエストを出していない状態では、リクエストが付与されるだけでなく、それが速やかに行われなければならない。

3.2 First Attempt
  • Cで実装してみる。
#include <stdio.h>
#include <sys/types.h>
#include <stdlib.h>
#include <pthread.h>

int turn;
int sum;

void Non_Critical_Section(int p)
{
  printf("Non_Critical_Section_%d;\n",p);
}

void Critical_Section(int p)
{
  printf("Critical_Section_%d;\n",p);
  sum += 1;
}

void* P1(void* arg)
{
  int i = 0;
  for(i=0;i<100;i++) {
    Non_Critical_Section(1);
    for(;turn != 1;); // mutual exclusion
    Critical_Section(1);
    turn = 2;
  }
}

void* P2(void* arg)
{
  int i = 0;
  for(i=0;i<100;i++) {
    Non_Critical_Section(2);
    for(;turn != 2;); // mutual exclusion
    Critical_Section(2);
    turn = 1;
  }
}

int main(int args,char *argv){
  pthread_t thread1;
  pthread_t thread2;

  //initialize global num
  turn = 1;
  sum = 0;

  printf("evaluation start");

  printf("create thread.\n");
  pthread_create( &thread1, NULL, P1, NULL);
  pthread_create( &thread2, NULL, P2, NULL);
  pthread_join( thread1, NULL );
  pthread_join( thread2, NULL );

  printf("sum:%d;\n",sum);

  return 0;
}
  • 実行結果
Non_Critical_Section_1
Critical_Section_2;
Non_Critical_Section_2
Critical_Section_1;
Non_Critical_Section_1
Critical_Section_2;
Non_Critical_Section_2
Critical_Section_1;
Critical_Section_2;
sum:200;
  • うまくいっているようだが、非常に時間がかかる。
  • ためしに、for(;turn != 1;)のところをそれぞれ、以下のようにしてみた。
for(;turn != 1;) printf("waiting for P2.\n");
for(;turn != 2;) printf("waiting for P1.\n");
  • 実行結果
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for p2.
waiting for   C-c C-c
//バッファがあふれそうなので途中で終了。
  • この実装の問題点として、必ず交互に行わなければならない点が上げられる。
  • たとえば、Non_Critical_Sectionを以下のようにすると、ひどいことになる。
void Non_Critical_Section(int p)
{
  printf("Non_Critical_Section_%d;\n",p);
  if(p==1) sleep(10); //P1の場合のみ、10秒時間がかかる。
}
  • P2はP1の処理を待ち続けることになる。
    • これは6に抵触する、「他のだれもリクエストを出していない状態では、リクエストが付与されるだけでなく、それが速やかに行われなければならない。」
    • P1を待たず、P2のみ先に処理を終わるということができない。よってこれは正しい方法ではない。
3.3 Second Attempt
  • Cで実装してみる。
#include <stdio.h>
#include <sys/types.h>
#include <stdlib.h>
#include <pthread.h>

int C1, C2;
int sum;

void Non_Critical_Section(int p)
{
  printf("Non_Critical_Section_%d;\n",p);
}

void Critical_Section(int p)
{
  printf("Critical_Section_%d;\n",p);
  sum += 1;
}

void* P1(void* arg)
{
  int i = 0;
  for(i=0;i<10000;i++) {
    Non_Critical_Section(1);
    for(;C2 != 1;) ;//printf("waiting for p2.\n"); // mutual exclusion
    C1 = 0;
    Critical_Section(1);
    C1 = 1;
  }
}

void* P2(void* arg)
{
  int i = 0;
  for(i=0;i<10000;i++) {
    Non_Critical_Section(2);
    for(;C1 != 1;) ;//printf("waiting for p1.\n"); // mutual exclusion
    C2 = 0;
    Critical_Section(2);
    C2 = 1;
  }
}

int main(int args,char *argv){
  pthread_t thread1;
  pthread_t thread2;

  //initialize global num
  C1, C2 = 1;
  sum = 0;

  printf("evaluation start\n");

  printf("create thread.\n");
  pthread_create( &thread1, NULL, P1, NULL);
  pthread_create( &thread2, NULL, P2, NULL);
  pthread_join( thread1, NULL );
  pthread_join( thread2, NULL );

  printf("sum:%d;\n",sum);

  return 0;
}
  • 実行結果
evaluation start
create thread.
sum:20000;
  • なぜかうまくいってしまうが、偶然である。うまくいかない可能性もある。
  • たとえば、Interleavingが完全に交互に収まってしまう場合。

//はじめの状態はC1,C2 = 1;
1. P1がC2をチェックして、C2 = 1を確認する。
2. P2がC1をチェックして、C1 = 1を確認する。
3. P1がC1に0を代入
4. P2がC2に0を代入
5. P1がCritical_Sectionに入る
6. P2がCritical_Sectionに入る

  • これは1番に抵触する。「2つ以上のプロセスが同時にCritical_Sectionに入って実行してはならない」
    • 要するにロックの意味がない。
    • 実際はCritical_Sectionの中には共有メモリへの副作用のある操作などが加えられるのでそこで問題が起こる可能性がある。(この場合はsum+=1)
3.4 Third Attempt
  • 3.3の順序を逆にしたバージョン
  • 3.3で以下のようになっていた部分を
for(;C2 != 1;); //check
C1 = 0;
Critical_Section(1);
C1 = 1;

for(;C1 != 1;); //check
C2 = 0;
Critical_Section(2);
C2 = 1;
  • 以下のようにする。
C1 = 0; //順番を変えた
for(;C2 != 1;); //check
Critical_Section(1);
C1 = 1;

C2 = 0; //順番を変えた
for(;C1 != 1;); //check
Critical_Section(2);
C2 = 1;
  • 「チェックが先だからどっちも入っちゃうんじゃね？先にCを0にしちゃえばいいんじゃね？」という浅はかな考え。
  • 実行結果
evaluation start
create thread.
Non_Critical_Section_1;
Critical_Section_1;
Non_Critical_Section_1;
Critical_Section_1;
Non_Critical_Section_2;
Non_Critical_Section_1;

-> Dead Lock !!!

//はじめの状態はC1,C2 = 1;
1. P1がC1を0とする。
2. P2がC2を0とする。
3. P1がC2が1になるまで待つループに入る。
4. P2がC1が1になるまで待つループに入る。

    • > Dead Lock !!
  • よって、4番に抵触するため、これはだめ。
3.5 Fourth Attempt
  • ならばということで、forの部分を変える。
  • デッドロックした場合、お互いに、C1,C2をすばやく切り替えて、どちらかが1となっている時にforのブレイクチェックがかかるようなInterleavingが起こることを期待している。
void* P1(void* arg)
{
  int i = 0;
  for(i=0;i<100;i++) {
    Non_Critical_Section(1);
    C1 = 0;
    for(;C2 != 1;){
      C1 = 1;
      //この間にP2のforの終了チェックがかかってほしい
      C1 = 0;
    };
    Critical_Section(1);
    C1 = 1;
  }
}

void* P2(void* arg)
{
  int i = 0;
  for(i=0;i<100;i++) {
    Non_Critical_Section(2);
    C2 = 0;
    for(;C1 != 1;){
      C2 = 1;
      //この間にP1のforの終了チェックがかかってほしい
      C2 = 0;
    }
    Critical_Section(2);
    C2 = 1;
  }
}
  • 実行結果(デッドロックではないが、評価が長々とまることがあるので、実際はC1,C2の代入のところに適当にsleepを入れた)
Critical_Section_1;
Critical_Section_2;
////////////////ここで一時停止する。/////////////////////
Non_Critical_Section_2;
Critical_Section_2;
Non_Critical_Section_2;
Critical_Section_2;
Non_Critical_Section_2;
Critical_Section_2;
Non_Critical_Section_2;
Critical_Section_2;
sum:200;
  • このやり方だと、以下のような、完全に交互のInterleavingの場合にライブロックがかかる可能性がある。

1. P1がC1に0を代入
2. P2がC2に0を代入 // -> 前の場合だとこの時点でデッドロック
3. P1がC2が1かどうかをチェック
4. P2がC1が1かどうかをチェック
5. P1がC1に1を代入
6. P2がC2に1を代入
7. P1がC1に0を代入
8. P2がC2に0を代入
9. P1がC2が1かどうかをチェック
10.P2がC1が1かどうかをチェック

  • > 5へ戻る(繰り返し)
  • このほかにも、以下のような場合もある。

1. P1がC1に0を代入
2. P2がC2に0を代入 // -> 前の場合だとこの時点でデッドロック
3. P1がC2が1かどうかをチェック
5. P1がC1に1を代入
7. P1がC1に0を代入
4. P2がC1が1かどうかをチェック
6. P2がC2に1を代入
8. P2がC2に0を代入

  • > 3へ戻る(繰り返し)
  • 実際はこんなにきれいに交互のInterlieavingになり続けることはあまりなく、いろいろな割り込みやらなんやらがあるので、結果的にずれていき、うまくいく。(しかし上記の実験プログラムでは、かなり長い間止まり続ける場合があった。)
  • この方法は、一応は仕様を満たしている。これで十分な場合もある（らしい）。
3.6 Dekker's Algorithm
  • Cで実装してみる。
void* P1(void* arg)
{
  int i = 0;
  for(i=0;i<100;i++) {
    Non_Critical_Section(1);
    C1 = 0;
    for(;C2 != 1;){
      if(Turn == 2){
        C1 = 1;
        for(;Turn != 1;);
        C1 = 0;
      }
    }
    Critical_Section(1);
    C1 = 1;
    Turn = 2;
  }
}

void* P2(void* arg)
{
  int i = 0;
  for(i=0;i<100;i++) {
    Non_Critical_Section(2);
    C2 = 0;
    for(;C1 != 1;){
      if(Turn == 1){
        C2 = 1;
        for(;Turn != 2;);
        C2 = 0;
      }
    }
    Critical_Section(2);
    C2 = 1;
    Turn = 1;
  }
}
  • 複雑だがうまくいく。
3.7 Mutual Exclusion for N Processes
3.8 Hardware-Assisted mutual Exclusion
  • ハードウェアのサポートを使ってやるのが一般的らしい。
3.9 Further Reading
  • もっと読みたい人向け
3.10 Exercises
  • あとでやる。