Principles of Concurrent and Distributed Programming

Principles of Concurrent and Distributed Programming (Prentice-Hall International Series in Computer Science)

• Onlispの絶賛読書中ですが、仕事で使うから読んどけといわれたので並行して読んでいきます。
• 並列とか並行処理の形式的な概念について書いてるっぽいです。
  • 英語読むのが大変。。

Chapter1

1.8

• 1
  • 問題文の意味が今ひとつわからない。
• 2
  • 並行処理を使ったquickソートを実装せよ的な。
  • Cで書くとのことなので、あまり知らないがCで書いた。

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

int g_thread_num;

struct qs_st {
  int* data;
  int n;
};

void* quicksort( void* arg )
{
  pthread_t thread1;
  struct qs_st nex_st1;
  pthread_t thread2;
  struct qs_st nex_st2;
  struct qs_st *st;
  st = (struct qs_st *)arg;
  int* data = st->data;
  int N = st->n;

  int i, j;
  int v, t;

  if( N <= 1 )
    return;

  // Partition elements
  v = data[0];
  i = 0;
  j = N;
  for(;;)
  {
    while(data[++i] < v && i < N) { }
    while(data[--j] > v) { }
    if( i >= j )
      break;
    t = data[i];
    data[i] = data[j];
    data[j] = t;
  }
  t = data[i-1];
  data[i-1] = data[0];
  data[0] = t;

  nex_st1.data = data;
  nex_st1.n = i-1;
  nex_st2.data = data+i;
  nex_st2.n = N-i;

  printf("[%d] create thread.\n",g_thread_num++);
  pthread_create( &thread1, NULL, quicksort, (void *)(&nex_st1));
  printf("[%d] create thread.\n",g_thread_num++);
  pthread_create( &thread2, NULL, quicksort, (void *)(&nex_st2));
  pthread_join( thread1, NULL );
  pthread_join( thread2, NULL );

}

int rand_int(int limit)
{
  return rand()%limit;
}

int main(int args,char *argv){
  int len = 100;
  int x[len];
  pthread_t thread;
  struct qs_st st;
  int i;
  g_thread_num = 0;

  srand((unsigned) time(NULL));
  for(i=0; i<len; i++) x[i] = rand_int(len);

  st.data = x;
  st.n = len;

  printf("sort start -> { ");
  for(i=0; i<len; i++) printf("%d,", x[i]);
  printf(" }\n");

  printf("[%d] create thread.\n",g_thread_num++);
  pthread_create( &thread, NULL, quicksort, (void*)(&st));
  pthread_join( thread, NULL );

  printf("sort finish -> { ");
  for(i=0; i<len; i++) printf("%d,", x[i]);
  printf(" }\n");

  return 0;
}

% gcc -o thread_qs -pthread qs.c
% ./thread_qs
sort start -> { 70,17,17,46,17,3,10,4,72,41,54,14,97,37,76,95,33,42,6,87,53,30,94,85,88,9,46,3,93,25,22,16,81,31,70,67,30,20,98,3,37,71,4,83,69,45,86,40,70,69,87,47,67,36,68,57,6,60,6,27,30,12,87,92,37,61,50,82,97,53,73,80,22,6,59,85,80,66,28,86,14,40,42,19,77,72,37,78,37,40,23,3,73,88,73,3,64,54,40,8, }
[0] create thread.
[1] create thread.
[2] create thread.

..........

[123] create thread.
[124] create thread.
[125] create thread.
sort finish -> { 3,3,3,3,3,4,4,6,6,6,6,8,9,10,12,14,14,16,17,17,17,19,20,22,22,23,25,27,28,30,30,30,31,33,36,37,37,37,37,37,40,40,40,40,41,42,42,45,46,46,47,50,53,53,54,54,57,59,60,61,64,66,67,67,68,69,69,70,70,70,71,72,72,73,73,73,76,77,78,80,80,81,82,83,85,85,86,86,87,87,87,88,88,92,93,94,95,97,97,98, }

• 排他制御してないので多分誤差はあるが、大体要素数ぐらいthreadができるようだ。
  • それにしてもrandomの精度がひどい。