Lamport's bakery algorithm

Lamport's bakery algorithm experiment in C

ランポートのパン屋のアルゴリズム例をC言語で書いてみる
PCDPはもう大体良いといわれたけど、微妙にわかってないので実装してみる。
まずはじめに、沢山のthreadで排他処理せずに、共有メモリをインクリメントするようなコードを書く。

///  --- だめな例！ ---  ///
#include <stdio.h>
#include <sys/types.h>
#include <stdlib.h>
#include <pthread.h>

#define THREAD_LEN 10
long int acc;

void* thread_temp( void* arg )
{
  long int i;
  for (i=0; i < 100000000; i++){
    acc = (acc + 1); // thread safe でないインクリメント。
  }
}

int main(int args, char *argv)
{
  int thread_len = THREAD_LEN;
  int i;
  pthread_t threads[thread_len];

  for(i=0; i<thread_len; i++){
    printf("[%d] create thread.\n", i);
    pthread_create( &(threads[i]), NULL, thread_temp , NULL);
  }

  for(i=0; i<thread_len; i++){
    printf("[%d] start thread.\n", i);
    pthread_join( threads[i] , NULL );
  }

  printf("*** result acc = %d\n", acc);
  return 0;
}

実行

[0] create thread.
[1] create thread.
[2] create thread.
[3] create thread.
[4] create thread.
[5] create thread.
[6] create thread.
[7] create thread.
[8] create thread.
[9] create thread.
[0] start thread.
[1] start thread.
[2] start thread.
[3] start thread.
[4] start thread.
[5] start thread.
[6] start thread.
[7] start thread.
[8] start thread.
[9] start thread.
*** result acc = 423256012（ <- 1000000000にならない !!!!!!!!）

これは排他処理を行ってないので、アトミックでなければならない処理がインターリーブ上で分割されてしまったためだ。
そこで、「ランポートのパン屋のアルゴリズム」によって排他処理してみる。
- http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%9D%E3%83%BC%E3%83%88%E3%81%AE%E3%83%91%E3%83%B3%E5%B1%8B%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

    // wikipediaによるアルゴリズム
    // 広域変数の宣言と初期値
    Enter, Number: array [1..N] of integer = {0};
    
 1  Thread(i) {
 2      while (true) {
 3          Enter[i] = 1;
 4          Number[i] = 1 + max(Number[1], ..., Number[N]);
 5          Enter[i] = 0;
 6          for (j = 1; j <= N; j++) {
 7              while (Enter[j] != 0) {
 8                  // スレッド j が番号を得るまで待つ
 9              }
10              while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) {
11                  // 小さい番号を持つスレッドや自分と同じだが高い優先順位の
12                  // スレッドが処理を終えるのを待つ
13              }
14          }
15          // クリティカルセクション...
16          Number[i] = 0;
17          // 非クリティカルセクション...
18      }
19  }

実際のコード

#include <stdio.h>
#include <sys/types.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

#define THREAD_LEN 10
int g_enter[THREAD_LEN] = {0};
int g_number[THREAD_LEN] = {0};

long int acc;

int check_mvlt(int a, int b, int c, int d)
{
  return ((a < c) || ((a == c) && (b < d)));
}

int max( int arr[], size_t size){
  int i;
  int max = arr[0];
  for(i=1; i<size; i++)
    if(max < arr[i])
      max = arr[i];
  return max;
}

void* thread_temp( void* args )
{
  int id = *((int*)args);
  long int i;
  int j;
  int thread_len = THREAD_LEN;

  printf("+++ myid is %d\n", id);

  //lock
  g_enter[id] = 1;
  g_number[id] = 1 + max(g_number, thread_len);
  g_enter[id] = 0;
  for (j=0; j<thread_len; j++) {
    while (g_enter[j] != 0) {
      // wait until thread j receives its number
    }
    while ((g_number[j] != 0) &&
           check_mvlt(g_number[j], j, g_number[id], id) /* ((g_number[j], j) < (g_number[id], id)) */)
    {
      // wait until threads with smaller numbers
      // or with the same number, but with higher
      // priority, finish their work
    }
  }

  //critical
  for (i=0; i < 100000000; i++)
    acc = (acc + 1);

  //unlock
  g_number[id] = 0;

}

int main(int args, char *argv)
{
  int thread_len = THREAD_LEN;
  int j[thread_len];
  int i;

  pthread_t threads[thread_len];

  for(i=0; i < thread_len; i++) j[i] = i;

  for(i=0; i<thread_len; i++){
    printf("[%d] create thread.\n", i);
    pthread_create( &(threads[i]), NULL, thread_temp, (void*)(j+i) );
  }

  for(i=0; i<thread_len; i++){
    printf("[%d] start thread.\n", i);
    pthread_join( threads[i] , NULL );
  }

  printf("*** result acc = %d\n", acc);
  return 0;
}

実行してみる

[0] create thread.
[1] create thread.
[2] create thread.
[3] create thread.
[4] create thread.
[5] create thread.
[6] create thread.
[7] create thread.
[8] create thread.
[9] create thread.
[0] start thread.
+++ myid is 0
+++ myid is 1
+++ myid is 2
+++ myid is 3
+++ myid is 4
+++ myid is 5
+++ myid is 6
+++ myid is 7
+++ myid is 8
+++ myid is 9
[1] start thread.
[2] start thread.
[3] start thread.
[4] start thread.
[5] start thread.
[6] start thread.
[7] start thread.
[8] start thread.
[9] start thread.
*** result acc = 1000000000

うまくいっている。
ちなみにlock,unlockは関数で囲えば、もっときれいになるだろう。

void m_lock(int id)
{
  int j;
  int thread_len = THREAD_LEN;
  g_enter[id] = 1;
  g_number[id] = 1 + max(g_number, thread_len);
  g_enter[id] = 0;
  for (j=0; j<thread_len; j++) {
    while (g_enter[j] != 0) {
      // wait until thread j receives its number
    }
    while ((g_number[j] != 0) &&
           check_mvlt(g_number[j], j, g_number[id], id) /* ((g_number[j], j) < (g_number[id], id)) */)
    {
      // wait until threads with smaller numbers
      // or with the same number, but with higher
      // priority, finish their work
    }
  }
}

void m_unlock(int id)
{
  g_number[id] = 0;
}

void* thread_temp( void* args )
{
  int id = *((int*)args);
  long int i;
  int thread_len = THREAD_LEN;

  printf("+++ myid is %d\n", id);

  m_lock(id);

  for (i=0; i < 100000000; i++)
    acc = (acc + 1);

  m_unlock(id);
}

となる。