並行分散ソフトウェア/並列分散ソフトウェア 電子・情報工学系 新城 靖 <yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/sie/pdsoft-2005/2005-12-16
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/sie/
http://www.cs.tsukuba.ac.jp/~yas/
class BoundedBuffer { final Lock lock = new ReentrantLock(); final Condition notFull = lock.newCondition(); final Condition notEmpty = lock.newCondition(); final Object[] items = new Object[100]; int putptr, takeptr, count; public void put(Object x) throws InterruptedException { lock.lock(); try { while (count == items.length) notFull.await(); items[putptr] = x; if (++putptr == items.length) putptr = 0; ++count; notEmpty.signal(); } finally { lock.unlock(); } } public Object take() throws InterruptedException { lock.lock(); try { while (count == 0) notEmpty.await(); Object x = items[takeptr]; if (++takeptr == items.length) takeptr = 0; --count; notFull.signal(); return x; } finally { lock.unlock(); } } }類似の機能は、ArrayBlockingQueue 等のクラスで提供されているので、自分 で作る必要はない。
[1] Steve Kleiman, Devang Shah and Bart Smaalders: "Programming with
Threads", Sun Microsystems Press, 1996. ISBN 0-13-172389-8
[2] Steve Kleiman, Devang Shah,Bart Smaalders著、岩本伸一訳: "実践マルチス
レッドプログラミング",アスキー出版局, 1998年. ISBN 4-7561-1784-8
[3] Doug Lea: "Concurrent Programming in Java: Design Principles and
Patterns, Second edition", Addison-Wesley, November 1999. (ISBN
0-201-31009-0).
[4] ダグ リー (著), Doug Lea (原著), 松野良蔵 (翻訳): " "Javaスレッド
プログラミング―並列オブジェクト指向プログラミングの設計原理",翔泳社
(2000). ISBN: 4881359185
WWW上に追補がある。
http://gee.cs.oswego.edu/dl/cpj/
EDU.oswego.cs.dl.util.concurrent パッケージには、実用になるクラスが多数含まれている。
J2SE 5.0 の java.util.concurrent では、さまざまな並行プログラミングの クラスが標準化された。
master() { 初期化; for( i=0 ; i<nthreads; i++ ) { pthread_create(,,slave,); } マスターの処理;/*必要なら*/ for( i=0 ; i<nthreads; i++ ) { pthread_join(,,slave,); } 終了処理;/*必要なら*/ } slave(void *params) { paramsからiを取り出す; 仕事をする; 結果を大域変数かparamsに返す; return; /* pthread_exit() */ }
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/ms_matrix-main.c台数効果をうまく図る方法% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/ms_matrix.c
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/timeval.c
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/Makefile
% emacs Makefile (CFLAGSの調整)
% make ms_matrix-main
gcc -D_REENTRANT ms_matrix-main.o -lpthread -lposix4 -o ms_matrix-main % ./ms_matrix-main 400 1 1
matrix_size==400, nthreads==1, niters==1, concurrency==1 1.846 [sec] / 1 [iteration] == 1.846 [sec/iteration] 1 [iteration] / 1.846 [sec] == 0.542 [iteration/sec] % ./ms_matrix-main 400 1 1
matrix_size==400, nthreads==1, niters==1, concurrency==1 1.842 [sec] / 1 [iteration] == 1.842 [sec/iteration] 1 [iteration] / 1.842 [sec] == 0.543 [iteration/sec] % ./ms_matrix-main 400 2 1
matrix_size==400, nthreads==2, niters==1, concurrency==2 0.924 [sec] / 1 [iteration] == 0.924 [sec/iteration] 1 [iteration] / 0.924 [sec] == 1.082 [iteration/sec] % ./ms_matrix-main 400 3 1
matrix_size==400, nthreads==3, niters==1, concurrency==3 0.657 [sec] / 1 [iteration] == 0.657 [sec/iteration] 1 [iteration] / 0.657 [sec] == 1.523 [iteration/sec] % ./ms_matrix-main 400 4 1
matrix_size==400, nthreads==4, niters==1, concurrency==4 0.467 [sec] / 1 [iteration] == 0.467 [sec/iteration] 1 [iteration] / 0.467 [sec] == 2.144 [iteration/sec] % ./ms_matrix-main 400 5 1
matrix_size==400, nthreads==5, niters==1, concurrency==5 0.728 [sec] / 1 [iteration] == 0.728 [sec/iteration] 1 [iteration] / 0.728 [sec] == 1.374 [iteration/sec] %
![]()
master() { 初期化; for( i=0 ; i<nthreads; i++ ) { pthread_create(,,slave,); } while( !termcond ) { マスターの処理A;/*必要なら*/ barrier_wait(); マスターの処理B;/*必要なら*/ barrier_wait(); } for( i=0 ; i<nthreads; i++ ) { pthread_join(,,slave,); } 終了処理;/*必要なら*/ } slave(void *params) { paramsからiを取り出す; while( !termcond ) { /* マスターの処理Aの完了を待つ */ barrier_wait(); スレーブ処理B; 結果を大域変数かparamsに返す; barrier_wait(); } return; /* pthread_exit() */ }ループの間、マスタの仕事がないこともある。その場合は、マスタはバリアに は参加しない(relax.c参照)。
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/ms_relax.c% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/ms_relax-main.c
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/barrier.c
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/timeval.c
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/Makefile
% emacs Makefile (CFLAGSの調整)
% make ms_relax-main.c
% ./ms_relax-main 50 1 1
matrix_size==50, nthreads==1, niters==1, concurrency==1 1.575 [sec] / 1 [iteration] == 1.575 [sec/iteration] 1 [iteration] / 1.575 [sec] == 0.635 [iteration/sec] % ./ms_relax-main 50 1 1
matrix_size==50, nthreads==1, niters==1, concurrency==1 1.572 [sec] / 1 [iteration] == 1.572 [sec/iteration] 1 [iteration] / 1.572 [sec] == 0.636 [iteration/sec] % ./ms_relax-main 50 2 1
matrix_size==50, nthreads==2, niters==1, concurrency==2 0.857 [sec] / 1 [iteration] == 0.857 [sec/iteration] 1 [iteration] / 0.857 [sec] == 1.167 [iteration/sec] % ./ms_relax-main 50 3 1
matrix_size==50, nthreads==3, niters==1, concurrency==3 0.646 [sec] / 1 [iteration] == 0.646 [sec/iteration] 1 [iteration] / 0.646 [sec] == 1.547 [iteration/sec] % ./ms_relax-main 50 4 1
matrix_size==50, nthreads==4, niters==1, concurrency==4 0.938 [sec] / 1 [iteration] == 0.938 [sec/iteration] 1 [iteration] / 0.938 [sec] == 1.066 [iteration/sec] % uptime
1:06am up 116 day(s), 14:35, 7 users, load average: 1.33, 1.14, 1.10 %
![]()
worker_thraed() { while( (ptr=work_get(workpile))!=NULL ) { ptrが示す仕事をする; if( 新しい仕事ができた ) { work_put(workpile,新しい仕事); } } }
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/quicksort-main.c% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/quicksort.c
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/workpile.c
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/timeval.c
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/cdsoft-2005/2005-12-16/ex/Makefile
% emacs Makefile (CFLAGSの調整)
% make quicksort-main
% ./quicksort-main 1000000 1
size==1000000, nthreads==1, concurrency==1 execution time: 0.766 [sec] throughput: 1.305 [/sec] % ./quicksort-main 1000000 1
size==1000000, nthreads==1, concurrency==1 execution time: 0.761 [sec] throughput: 1.315 [/sec] % ./quicksort-main 1000000 2
size==1000000, nthreads==2, concurrency==2 execution time: 0.439 [sec] throughput: 2.280 [/sec] % ./quicksort-main 1000000 3
size==1000000, nthreads==3, concurrency==3 execution time: 0.334 [sec] throughput: 2.993 [/sec] % ./quicksort-main 1000000 4
size==1000000, nthreads==4, concurrency==4 execution time: 0.318 [sec] throughput: 3.145 [/sec] % ./quicksort-main 1000000 5
size==1000000, nthreads==5, concurrency==5 execution time: 0.276 [sec] throughput: 3.621 [/sec] %
![]()
コンパイル時: -pg オプションを付ける。
実行すると gmon.out というファイルが作られる。 これを、実行形式ファイルと共に gprof コマンドに渡す。
ロックの種類ロックを確保したスレッドが、CPU を横取りされていたなら待っているのは無 駄になる。
無限のスピンは避けたい。 コンテキスト切り替えに要する時間の 50%-100% だけスピンするのがよい。 [Anderson 90]
プログラミング言語としては、C言語、または、Java を用いなさい。
プログラミング言語としては、C言語、または、Java を用いなさい。
プログラミング言語としては、C言語、または、Java を用いなさい。
プログラミング言語としては、C言語、または、Java を用いなさい。