オペレーティングシステム 演習 05¶

並行処理, 競合状態, 排他制御¶

名前と学生証番号を書け. Enter your name and student ID.

  • 名前 Name:
  • 学生証番号 Student ID:

1. 競合状態¶

  • 複数のスレッドが同じ変数を, 並行にアクセスしている
  • それらのスレッドの内少なくとも1つが書き込みをしている

状態を競合状態と呼び, ほとんどの場合, スレッドの実行タイミングによって答えが変わる --- つまりほとんどの場合, 間違った --- プログラムになる

  • 以下は最も単純な例
  • 2スレッドが大域変数 g を多数回更新する
In [ ]:
%%writefile race_increment.c
#include <assert.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>


/* 大域変数 */
volatile int g = 0;

/* スレッドの開始関数 */
void * f(void * arg_) {
  long * arg = arg_;
  long n = arg[0];
  for (long i = 0; i < n; i++) {
    g++;
  }
  return 0;
}


int main(int argc, char ** argv) {
  long n = (argc > 1 ? atol(argv[1]) : 1000000);
  long arg[1] = { n };
  g = 0;
  /* スレッドを作る */
  const int nthreads = 2;
  pthread_t child_thread_id[nthreads];
  for (int i = 0; i < nthreads; i++) {
    if (pthread_create(&child_thread_id[i], 0, f, arg))
      err(1, "pthread_create");
  }
  /* 終了待ち */
  for (int i = 0; i < nthreads; i++) {
    void * ret = 0;
    if (pthread_join(child_thread_id[i], &ret))
      err(1, "pthread_join");
  }
  printf("g = %d\n", g);
  return 0;
}
In [ ]:
gcc -Wall -o race_increment race_increment.c -lpthread
  • 以下を何度も実行し結果が正しくない(ことがある)か確かめよ
In [ ]:
./race_increment 1000000

2. OpenMP¶

  • Pthreadでプログラムを書くと, ちょっとしたことをスレッドにやらせるのにいちいち, 別の関数を作り, 引数を構造体に詰めて, それを受け取ったほうがまた構造体から要素を取り出して, ... という処理が実に煩わしい
  • OpenMPという, 並列処理のためのC言語の機能を使うと簡単なスレッド処理はずっと簡潔に書けるので以降はそれを使う(Pthreadの代わりをするための最低限の機能のみ使う)
  • 以下はOpenMPの一番簡単なプログラム
In [ ]:
%%writefile omp_hello.c
#include <stdio.h>
#include <unistd.h>
#include <omp.h>

int main() {
  printf("hello\n");
#pragma omp parallel
  {
    /* 起動時に環境変数OMP_NUM_THREADS=xxx で指定した
       個数のスレッドが作られ, 各々が以下の文 { ... }
       を実行する.
       omp_get_num_threads() : { ... } を実行しているスレッド数を得る
       omp_get_thread_num() : その中での呼び出したスレッドの番号を得る
    */
    int idx = omp_get_thread_num();
    int nth = omp_get_num_threads();
    for (int i = 0; i < 4; i++) {
      usleep(1000);
      printf("hi I am %d of %d\n", idx, nth);
    }
  }
  printf("bye\n");
  return 0;
}
In [ ]:
gcc -Wall -fopenmp -o omp_hello omp_hello.c

以下のOMP_NUM_THREADS=3の数字をいろいろ変えて実行してみよ.

In [ ]:
OMP_NUM_THREADS=3 ./omp_hello

OpenMP超概説¶

#pragma omp parallel
  S /* Cの文 */

を実行すると,

  • OMP_NUM_THREADS=.. で指定された数のスレッドが出来る
  • 各スレッドがSを実行する

という動作をする

  • コンパイルの際には -fopenmp というオプションを指定する

  • 注意1 上記はparallelと名付けられてはいるが, 同じ文(S)を複数のスレッドが「重複して」実行する指示であり, Sを「並列化」(分割して高速化)する文ではない

  • 注意2 複数のスレッドで実行されるのは #pragma omp parallel の直後の1文のみで, それ以降は再び1スレッドの実行に戻る(上述のomp_helloの実行を参照). 複数の文をスレッドに実行させたければ複合文 { ... } を用いればよい

  • スレッド数はOMP_NUM_THREADSで指定する代わりにプログラム内で以下のように指定することも可能.

#pragma omp parallel num_threads(n)
  S

  • Sの実行中に以下の関数を呼び出すと,

    • omp_get_num_threads() --- Sを実行しているスレッド数(OMP_NUM_THREADSやnum_threadsで指定した数)を返す
    • omp_get_thread_num() --- その中での呼び出したスレッドの番号を返す(0, 1, ..., スレッド数-1)

  • 以下は上述した競合状態を持つプログラムをOpenMPで書き直したもの

In [ ]:
%%writefile race_increment_omp.c
#include <assert.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>


/* 大域変数 */
volatile int g = 0;



int main(int argc, char ** argv) {
  long n = (argc > 1 ? atol(argv[1]) : 1000000);
  g = 0;
#pragma omp parallel
  {
    for (long i = 0; i < n; i++) {
      g++;
    }
  }
  printf("g = %d\n", g);
  return 0;
}
In [ ]:
gcc -Wall -fopenmp -o race_increment_omp race_increment_omp.c

以下を何度も実行して見よ

In [ ]:
OMP_NUM_THREADS=3 ./race_increment_omp 1000000
  • 上述したとおり上記は「各スレッドが」$n$回の更新を行う. 並列処理でしばしば必要なのは合計n個の仕事を何個かのスレッドで分け合って高速化するというもので, そのための構文が #pragma omp for
  • 詳しいことは省略して,
#pragma omp parallel
{
  ...
#pragma omp for
  for (int i = 0; i < n; i++) {
    T;
  }
}

と書くと, for文のn回の繰り返しが #pragma omp parallel で作られたスレッド間で分け合って実行されるということだけ覚えれば良い.

  • 以下は上述したプログラムを, 全スレッド合計で, 与えられた$n$回更新するようにしたもの
In [ ]:
%%writefile race_increment_n.c
#include <assert.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>


/* 大域変数 */
volatile int g = 0;



int main(int argc, char ** argv) {
  long n = (argc > 1 ? atol(argv[1]) : 1000000);
  g = 0;
#pragma omp parallel
  {
#pragma omp for
    for (long i = 0; i < n; i++) {
      g++;
    }
  }
  printf("g = %d\n", g);
  return 0;
}
In [ ]:
gcc -Wall -fopenmp -o race_increment_n race_increment_n.c

以下を何度も実行して見よ

In [ ]:
OMP_NUM_THREADS=3 ./race_increment_n 1000000

3. Python¶

  • Python でもスレッドを使う限り, 当然同じ問題が生ずる
  • ただし, 話すと脇道にそれるので今は省略(後述)理由(Global Interpreter Lock)によって, g += 1 のような短い操作の排他性は保証されるようで, 以下の例では問題は生じないようである (ただし, それが言語仕様で保証されているなどとは思わないほうが無難)
In [ ]:
%%writefile race_increment_working.py
import random
import sys
import threading
g = 0

def parallel(f, nthreads):
    """
    #pragma omp parallel に似たもの

    f(0), f(1), ..., f(nthreads - 1) の各々をスレッドで実行
    """
    threads = [threading.Thread(target=f, args=(i, ))
               for i in range(nthreads)]
    for th in threads:
        th.start()
    for th in threads:
        th.join()

def main():
    global g
    argv = sys.argv
    argc = len(argv)
    i = 1
    n = int(argv[i]) if i < argc else 1000000
    i += 1
    nthreads = int(argv[i]) if i < argc else 2
    i += 1

    g = 0
    def thread_fun(idx):
        global g
        for i in range(n):
            g += 1
    parallel(thread_fun, nthreads)
    print(f"g = {g}")
    return 0

sys.exit(main())
In [ ]:
python3 race_increment_working.py 1000000 2
  • 少し余計な処理(関数呼び出し)を挟んで, 実質的に同じプログラムを以下のように書き換えると問題が(無事?)観測できる
In [ ]:
%%writefile race_increment.py
import random
import sys
import threading
g = 0

def plus_one(x):
    return x + 1

def parallel(f, nthreads):
    """
    #pragma omp parallel に似たもの

    f(0), f(1), ..., f(nthreads - 1) の各々をスレッドで実行
    """
    threads = [threading.Thread(target=f, args=(i, ))
               for i in range(nthreads)]
    for th in threads:
        th.start()
    for th in threads:
        th.join()

def main():
    global g
    argv = sys.argv
    argc = len(argv)
    i = 1
    n = int(argv[i]) if i < argc else 1000000
    i += 1
    nthreads = int(argv[i]) if i < argc else 2
    i += 1

    g = 0
    def thread_fun(idx):
        global g
        for i in range(n):
            g = plus_one(g)
    parallel(thread_fun, nthreads)
    print(f"g = {g}")
    return 0

sys.exit(main())
In [ ]:
python3 race_increment.py 1000000 2
  • 以下はスレッド数によらず合計で$n$回incrementするもの
In [ ]:
%%writefile race_increment_parallel_for.py
import random
import sys
import threading
g = 0

def plus_one(x):
    return x + 1

def parallel(f, nthreads):
    """
    #pragma omp parallel に似たもの

    f(0), f(1), ..., f(nthreads - 1) の各々をスレッドで実行
    """
    threads = [threading.Thread(target=f, args=(i, ))
               for i in range(nthreads)]
    for th in threads:
        th.start()
    for th in threads:
        th.join()

def parallel_for(f, a, b, nthreads):
    """
    #pragma omp parallel for に似たもの
    f(a), f(a+1), ..., f(b-1) を nthreads で分割して実行
    """
    def thread_fun(i):
        ai = (a * (nthreads - i)     + b * i) // nthreads
        bi = (a * (nthreads - i - 1) + b * (i + 1)) // nthreads
        for i in range(ai, bi):
            f(i)
    parallel(thread_fun, nthreads)

def main():
    global g
    argv = sys.argv
    argc = len(argv)
    i = 1
    n = int(argv[i]) if i < argc else 1000000
    i += 1
    nthreads = int(argv[i]) if i < argc else 2
    i += 1

    g = 0
    # 1 iteration分の処理
    def iter_fun(i):
        global g
        g = plus_one(g)
    parallel_for(iter_fun, 0, n, nthreads)
    print(f"g = {g}")
    return 0

sys.exit(main())
In [ ]:
python3 race_increment_parallel_for.py 1000000 2

4. 課題前の準備¶

  • 以下の課題に取り掛かる前に, しくじったときのリカバリーの仕方を覚える必要がある
  • 「しくじり」とは何らかの理由でプログラムが終了しないケース
    • そうなるとセルの左が [*] となったまま数字にならず, 他のセルでSHIFT + ENTERしても反応しなくなる
  • 同期を伴うプログラムで間違うとそういうことになる
  • リカバリー(走っているプログラムの強制終了)の仕方
    • まず, 仕様上は画面上部の停止■ボタンで停止することにはなっているが停止しないこともしばしば
    • ■で停止しなかった場合は,
    • 左上の「Jupyter」メニューでJupyterのトップページに戻る
    • File -> New -> Terminal を選択してターミナルを開く
    • コマンドラインプロンプトが現れたら以下のコマンドを実行
      • やりかた1
ps auxww | grep 実行しているプログラム名

または

pgrep -fa 実行しているプログラム名

どちらかによってプロセスIDを突き止めたら

kill プロセスID

* やりかた2

1をなんどか経験して, 誤爆の心配がないとわかったら

killall 実行しているプログラム名

* やりかた3
top

を実行. 'u'で自分のユーザIDを持つプロセスだけを表示. killしたいプロセスが見つかったら'k' (キャンセルは ESC)

  • Jupyterのターミナルの代わりに直接SSHでログインしてもよい(推奨)
  • 懸命な諸君はお気づきだろうが, プログラミング自体をSSHでログインしてコマンドラインや好きなエディタで行っても良い(Jupyter上よりもvimやEmacsでプログラムが書く方がよいという人はそうしてもよい)
  • エディタなど複雑な画面表示を行うプログラムはJupyterターミナルでの実行は推奨しない
  • そうすれば, GDBなどデバッグ用のツールも使える
  • ただし, 課題部分はJupyter上にコードと, 実行記録を残すこと
  • プロセスを殺すこともなぜかできない場合, Jupyterカーネルのリセットやサーバの再起動が最後の手段. Jupyter環境の使い方 ページの「おかしなことになったら」の節を参照

練習¶

  1. JupyterターミナルまたはSSHでログインしておき,
  2. 以下を実行し,
  3. 1234秒以内にそのプロセスを ps コマンドで発見し,
  4. killして終了させよ
In [ ]:
sleep 1234

5. 排他制御 (mutual exclusion, mutex)¶

  • 排他制御は文字通り, ある一連の処理を「排他的に」実行するためのAPI
lock(m);
  何か
unlock(m);

を複数のスレッドが実行しても, 「何か」の部分が時間的に重なることがないことを保証する

5-1. C¶

  • C言語 Pthreadの排他制御関連のAPIは以下
    • pthread_mutex_init
    • pthread_mutex_lock
    • pthread_mutex_unlock
    • pthread_mutex_trylock

Problem 1 : 排他制御の練習 (C)¶

  • 以下に排他制御(mutex)を導入し, 結果が常に正しく(gの値が$n$に)なるようにせよ
  • 注: 実はOpenMPにはOpenMPの排他制御APIがあるのだが気にせずPthreadのものを使えば良い
In [ ]:
%%writefile race_increment_n.c
#include <assert.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>


/* 大域変数 */
volatile int g = 0;



int main(int argc, char ** argv) {
  long n = (argc > 1 ? atol(argv[1]) : 1000000);
  g = 0;
#pragma omp parallel
  {
#pragma omp for
    for (long i = 0; i < n; i++) {
      g++;
    }
  }
  printf("g = %d\n", g);
  return 0;
}
In [ ]:
gcc -Wall -fopenmp -o race_increment_n race_increment_n.c
In [ ]:
%%writefile race_increment_n_ans.c
#include <assert.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>


/* 大域変数 */
volatile int g = 0;



int main(int argc, char ** argv) {
  long n = (argc > 1 ? atol(argv[1]) : 1000000);
  g = 0;
  pthread_mutex_t m[1];
  pthread_mutex_init(m, 0);
#pragma omp parallel
  {
#pragma omp for
    for (long i = 0; i < n; i++) {
      pthread_mutex_lock(m);
      g++;
      pthread_mutex_unlock(m);
    }
  }
  printf("g = %d\n", g);
  return 0;
}
In [ ]:
gcc -Wall -fopenmp -o race_increment_n_ans race_increment_n_ans.c
  • nやスレッド数を変えて実行せよ(g = 1000000 が表示されたら成功)
In [ ]:
OMP_NUM_THREADS=3  ./race_increment_n 1000000
OMP_NUM_THREADS=20 ./race_increment_n 1000000
In [ ]:
OMP_NUM_THREADS=3  ./race_increment_n_ans 1000000
OMP_NUM_THREADS=20 ./race_increment_n_ans 1000000

5-2. Python¶

  • Python threading モジュール排他制御関連のAPIは以下
    • m = threading.Lock() ... mutexを作る
    • m.acquire() ... lock
    • m.release() ... unlock

Problem 2 : 排他制御の練習 (Python)¶

  • 以下に排他制御を導入し, 結果が常に正しく(gの値が$n$に)なるようにせよ
In [ ]:
%%writefile race_increment_n.py
import random
import sys
import threading
g = 0

def plus_one(x):
    return x + 1

def parallel(f, nthreads):
    """
    #pragma omp parallel に似たもの

    f(0), f(1), ..., f(nthreads - 1) の各々をスレッドで実行
    """
    threads = [threading.Thread(target=f, args=(i, ))
               for i in range(nthreads)]
    for th in threads:
        th.start()
    for th in threads:
        th.join()

def parallel_for(f, a, b, nthreads):
    """
    #pragma omp parallel for に似たもの
    f(a), f(a+1), ..., f(b-1) を nthreads で分割して実行
    """
    def thread_fun(i):
        ai = (a * (nthreads - i)     + b * i) // nthreads
        bi = (a * (nthreads - i - 1) + b * (i + 1)) // nthreads
        for i in range(ai, bi):
            f(i)
    parallel(thread_fun, nthreads)

def main():
    global g
    argv = sys.argv
    argc = len(argv)
    i = 1
    n = int(argv[i]) if i < argc else 1000000
    i += 1
    nthreads = int(argv[i]) if i < argc else 2
    i += 1

    g = 0
    # 1 iteration分の処理
    def iter_fun(i):
        global g
        g = plus_one(g)
    parallel_for(iter_fun, 0, n, nthreads)
    print(f"g = {g}")
    return 0

sys.exit(main())
In [ ]:
python3 race_increment_n.py
In [ ]:
%%writefile race_increment_n_ans.py
import random
import sys
import threading
g = 0

def plus_one(x):
    return x + 1

def parallel(f, nthreads):
    """
    #pragma omp parallel に似たもの

    f(0), f(1), ..., f(nthreads - 1) の各々をスレッドで実行
    """
    threads = [threading.Thread(target=f, args=(i, ))
               for i in range(nthreads)]
    for th in threads:
        th.start()
    for th in threads:
        th.join()

def parallel_for(f, a, b, nthreads):
    """
    #pragma omp parallel for に似たもの
    f(a), f(a+1), ..., f(b-1) を nthreads で分割して実行
    """
    def thread_fun(i):
        ai = (a * (nthreads - i)     + b * i) // nthreads
        bi = (a * (nthreads - i - 1) + b * (i + 1)) // nthreads
        for i in range(ai, bi):
            f(i)
    parallel(thread_fun, nthreads)

def main():
    global g
    argv = sys.argv
    argc = len(argv)
    i = 1
    n = int(argv[i]) if i < argc else 1000000
    i += 1
    nthreads = int(argv[i]) if i < argc else 2
    i += 1

    g = 0
    # 1 iteration分の処理
    m = threading.Lock()
    def iter_fun(i):
        global g
        m.acquire()
        g = plus_one(g)
        m.release()
    parallel_for(iter_fun, 0, n, nthreads)
    print(f"g = {g}")
    return 0

sys.exit(main())
In [ ]:
python3 race_increment_n_ans.py
  • nやスレッド数を変えて実行せよ(g = 1000000 が表示されたら成功)
In [ ]:
python3 race_increment_n.py 1000000 3
python3 race_increment_n.py 1000000 20
In [ ]:
python3 race_increment_n_ans.py 1000000 3
python3 race_increment_n_ans.py 1000000 20

Problem 3 : 排他制御の実践¶

  • 以下は素数を数えるプログラムをOpenMPで書いたもの
  • これに排他制御(mutex)を導入し, 結果が正しくなるようにせよ
  • なお, 正しい結果を知りたければ1スレッド (OMP_NUM_THREADS=1) で実行した結果を信じればよいだろう
  • 注: OpenMPにはOpenMPの排他制御APIがあるのだが気にせずPthreadのものを使えば良い
In [ ]:
%%writefile count_prime_omp.c
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>
#include <omp.h>

int check_prime(long n) {
  for (long d = 2; d * d <= n; d++) {
    if (n % d == 0) return 0;
  }
  return n > 1;
}

void count_primes(long a, long b, long * s) {
#pragma omp for
  for (long n = a; n < b; n++) {
    if (check_prime(n)) {
      *s += 1;
    }
  }
}


double cur_time() {
  struct timespec ts[1];
  clock_gettime(CLOCK_REALTIME, ts);
  return ts->tv_nsec * 1.0E-9 + ts->tv_sec;
}

int main(int argc, char ** argv) {
  long i = 1;
  long a = (argc > i ? atol(argv[i]) : 1000000); i++;
  long b = (argc > i ? atol(argv[i]) : 2000000); i++;
  long s = 0;
  double t0 = cur_time();
#pragma omp parallel            
  {
    /* 起動時に環境変数OMP_NUM_THREADS=xxx で指定した
       個数のスレッドが作られ, 各々が以下の文 { ... }
       を実行する.
       関数内のpragma omp for 下のfor文をそれらのスレッドが
       分割して実行する */
    count_primes(a, b, &s);
  }
  double t1 = cur_time();
  printf("%ld primes in [%ld,%ld)\n", s, a, b);
  printf("%f sec\n", t1 - t0);
  return 0;
}
In [ ]:
gcc -Wall -fopenmp -o count_prime_omp count_prime_omp.c
In [ ]:
if OMP_NUM_THREADS=4  ./count_prime_omp       0 1000000 | grep 78498 ; then echo OK ; else echo NG ; fi
if OMP_NUM_THREADS=4  ./count_prime_omp 1000000 2000000 | grep 70435 ; then echo OK ; else echo NG ; fi
if OMP_NUM_THREADS=4  ./count_prime_omp 2000000 3000000 | grep 67883 ; then echo OK ; else echo NG ; fi
if OMP_NUM_THREADS=20 ./count_prime_omp 2000000 3000000 | grep 67883 ; then echo OK ; else echo NG ; fi
In [ ]:
%%writefile count_prime_ans.c
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>
#include <omp.h>

int check_prime(long n) {
  for (long d = 2; d * d <= n; d++) {
    if (n % d == 0) return 0;
  }
  return n > 1;
}

void count_primes(long a, long b, long * s, pthread_mutex_t * m) {
#pragma omp for
  for (long n = a; n < b; n++) {
    if (check_prime(n)) {
      pthread_mutex_lock(m);
      *s += 1;
      pthread_mutex_unlock(m);
    }
  }
}


double cur_time() {
  struct timespec ts[1];
  clock_gettime(CLOCK_REALTIME, ts);
  return ts->tv_nsec * 1.0E-9 + ts->tv_sec;
}

int main(int argc, char ** argv) {
  long i = 1;
  long a = (argc > i ? atol(argv[i]) : 1000000); i++;
  long b = (argc > i ? atol(argv[i]) : 2000000); i++;
  long s = 0;
  pthread_mutex_t m[1];
  pthread_mutex_init(m, 0);
  double t0 = cur_time();
#pragma omp parallel            
  {
    /* 起動時に環境変数OMP_NUM_THREADS=xxx で指定した
       個数のスレッドが作られ, 各々が以下の文 { ... }
       を実行する.
       関数内のpragma omp for 下のfor文をそれらのスレッドが
       分割して実行する */
    count_primes(a, b, &s, m);
  }
  double t1 = cur_time();
  printf("%ld primes in [%ld,%ld)\n", s, a, b);
  printf("%f sec\n", t1 - t0);
  return 0;
}
In [ ]:
gcc -Wall -fopenmp -o count_prime_ans count_prime_ans.c
In [ ]:
if OMP_NUM_THREADS=4  ./count_prime_ans       0 1000000 | grep 78498 ; then echo OK ; else echo NG ; fi
if OMP_NUM_THREADS=4  ./count_prime_ans 1000000 2000000 | grep 70435 ; then echo OK ; else echo NG ; fi
if OMP_NUM_THREADS=4  ./count_prime_ans 2000000 3000000 | grep 67883 ; then echo OK ; else echo NG ; fi
if OMP_NUM_THREADS=20 ./count_prime_ans 2000000 3000000 | grep 67883 ; then echo OK ; else echo NG ; fi

6. 同期を隠蔽した(スレッドセーフな)データ構造¶

  • ある変数をスレッドで更新・参照するたびに排他制御を導入するとプログラムは汚く, 見通しが悪くなる
  • そこで通常, 「データとそれを守る排他制御」をセットにしたデータ構造と, それを操作する関数を作る. スレッドがそれを呼び出すだけで安全に動作するようにする
  • その練習として, 値を足していくカウンタを作り, 素数を数えるプログラムに適用する
  • 以下をカウンタのインターフェスとする
typedef struct { ... } counter_t;
/* 0 にする */
void counter_init(counter_t * c);
/* +1 する (返り値: 深い意味はないが, 元の値を返すとする) */
long counter_inc(counter_t * c);
/* 今の値を返す */
long counter_get(counter_t * c);

Problem 4 : スレッドセーフなカウンタ¶

  • 上記インターフェースを持つデータ構造と関数を作り, 素数を数えるプログラムに適用せよ
  • 以下のコード中の所定のデータ構造や関数の中身を書き足して正しく動くようにせよ
In [ ]:
%%writefile count_prime_counter.c
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>
#include <omp.h>

int check_prime(long n) {
  for (long d = 2; d * d <= n; d++) {
    if (n % d == 0) return 0;
  }
  return n > 1;
}

/* 以下のstruct, 関数の中身を埋めよ */
typedef struct {
} counter_t;

void counter_init(counter_t * c) {
  /* 0 にする 
     (void)cは変数を使っていないという警告を消すためのもの.
     修正後は消して良い */
  (void)c;
}

long counter_inc(counter_t * c) {
  /* +1 する (返り値: 深い意味はなく, 元の値を返すとする) */
  (void)c;
  return -1;
}

long counter_get(counter_t * c) {
  /* 今の値を返す */
  (void)c;
  return -1;
}

void count_primes(long a, long b, counter_t * c) {
#pragma omp for
  for (long n = a; n < b; n++) {
    if (check_prime(n)) {
    }
  }
}


double cur_time() {
  struct timespec ts[1];
  clock_gettime(CLOCK_REALTIME, ts);
  return ts->tv_nsec * 1.0E-9 + ts->tv_sec;
}

int main(int argc, char ** argv) {
  long i = 1;
  long a = (argc > i ? atol(argv[i]) : 1000000); i++;
  long b = (argc > i ? atol(argv[i]) : 2000000); i++;
  counter_t c[1];
  counter_init(c);
  double t0 = cur_time();
#pragma omp parallel            
  {
    /* 起動時に環境変数OMP_NUM_THREADS=xxx で指定した
       個数のスレッドが作られ, 各々が以下の文 { ... }
       を実行する.
       関数内のpragma omp for 下のfor文をそれらのスレッドが
       分割して実行する */
    count_primes(a, b, c);
  }
  double t1 = cur_time();
  printf("%ld primes in [%ld,%ld)\n", counter_get(c), a, b);
  printf("%f sec\n", t1 - t0);
  return 0;
}
In [ ]:
gcc -Wall -fopenmp -o count_prime_counter count_prime_counter.c
In [ ]:
%%writefile count_prime_counter_ans.c
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <pthread.h>
#include <omp.h>

int check_prime(long n) {
  for (long d = 2; d * d <= n; d++) {
    if (n % d == 0) return 0;
  }
  return n > 1;
}

/* 以下のstruct, 関数の中身を埋めよ */
typedef struct {
  long x;
  pthread_mutex_t m[1];
} counter_t;

void counter_init(counter_t * c) {
  c->x = 0;
  pthread_mutex_init(c->m, 0);
}

long counter_inc(counter_t * c) {
  /* +1 する (返り値: 深い意味はなく, 元の値を返すとする) */
  pthread_mutex_lock(c->m);
  long x = c->x;
  c->x = x + 1;
  pthread_mutex_unlock(c->m);
  return x;
}

long counter_get(counter_t * c) {
  return c->x;
}

void count_primes(long a, long b, counter_t * c) {
#pragma omp for
  for (long n = a; n < b; n++) {
    if (check_prime(n)) {
      counter_inc(c);
    }
  }
}


double cur_time() {
  struct timespec ts[1];
  clock_gettime(CLOCK_REALTIME, ts);
  return ts->tv_nsec * 1.0E-9 + ts->tv_sec;
}

int main(int argc, char ** argv) {
  long i = 1;
  long a = (argc > i ? atol(argv[i]) : 1000000); i++;
  long b = (argc > i ? atol(argv[i]) : 2000000); i++;
  counter_t c[1];
  counter_init(c);
  double t0 = cur_time();
#pragma omp parallel            
  {
    /* 起動時に環境変数OMP_NUM_THREADS=xxx で指定した
       個数のスレッドが作られ, 各々が以下の文 { ... }
       を実行する.
       関数内のpragma omp for 下のfor文をそれらのスレッドが
       分割して実行する */
    count_primes(a, b, c);
  }
  double t1 = cur_time();
  printf("%ld primes in [%ld,%ld)\n", counter_get(c), a, b);
  printf("%f sec\n", t1 - t0);
  return 0;
}
In [ ]:
gcc -Wall -fopenmp -o count_prime_counter_ans count_prime_counter_ans.c
In [ ]:
if OMP_NUM_THREADS=4  ./count_prime_counter       0 1000000 | grep 78498 ; then echo OK ; else echo NG ; fi
if OMP_NUM_THREADS=4  ./count_prime_counter 1000000 2000000 | grep 70435 ; then echo OK ; else echo NG ; fi
if OMP_NUM_THREADS=4  ./count_prime_counter 2000000 3000000 | grep 67883 ; then echo OK ; else echo NG ; fi
if OMP_NUM_THREADS=20 ./count_prime_counter 2000000 3000000 | grep 67883 ; then echo OK ; else echo NG ; fi
In [ ]:
if OMP_NUM_THREADS=4  ./count_prime_counter_ans       0 1000000 | grep 78498 ; then echo OK ; else echo NG ; fi
if OMP_NUM_THREADS=4  ./count_prime_counter_ans 1000000 2000000 | grep 70435 ; then echo OK ; else echo NG ; fi
if OMP_NUM_THREADS=4  ./count_prime_counter_ans 2000000 3000000 | grep 67883 ; then echo OK ; else echo NG ; fi
if OMP_NUM_THREADS=20 ./count_prime_counter_ans 2000000 3000000 | grep 67883 ; then echo OK ; else echo NG ; fi