自律分散協調

自律分散協調
KMSF M1 tomotaka
今回のお題
•  シングルプロセス内でのマルチスレッド協調 •  Producer/Consumerパターンを実装してみま
す •  まずはサンプルプログラムをDownload –  h:p://www.ht.sfc.keio.ac.jp/~tomotaka/mtpnf.zip –  Eclipseにインポートしてください
Producer/Consumer Pa:ern
•  作る人/消費する人 Worker
PUT
Worker
Task Queue
Task Producer
TAKE
Worker
Task Producer
•  タスクを作る人 •  今回のサンプルプログラムではここはシング
ルスレッドです •  タスクを作ってTask Queueに放り込むだけの仕
事しかしません
Task Queue
•  Task Producer(Taskを作る人)とWorker(Taskを
消費する人)の間でTaskを受け渡すためのパ
イプ役 •  Thread Safeでなければいけない: –  極めて同じタイミングのTask PUTでも壊れない –  極めて同じタイミングのTask TAKEでも壊れない –  空のときのTAKEはPUTを待ってblockする –  満タンのときのPUTはTAKEを待ってblockする Worker(Task Consumer)
•  Task Queue経由でTaskを受け取り, 消化する
人 •  僕のPCにはデュアルコアCPUがのってる!! –  2つのWorkerを使うことで計算の効率を上げられるはず!!
CoreBが暇 でもったいない!
CoreA: 90% CoreB: 5%
CoreA: 90% CoreB: 90%
MulT Thread Programming on Java
•  知っておくべきキーワード –  Thread(class) –  Runnable(interface) –  synchronized(keyword) –  wait() (method) –  noTfy() (method) –  noTfyAll() (method)
ThreadとRunnableはわかるよね?
Thread Sample
class Mazu extends Thread {
public void run() {
System.out.println(“yabaissu”);
}
}
Thread myMazu = new Mazu();
myMazu.start();
Runnable Sample
class Mochi implements Runnable {
public void run() {
System.out.println(“Ramen Tsukemen Boku IKEMEN!!”);
}
}
Mochi myMochi = new Mochi();
Thraed mochiThread = new Thread(mochi);
mochiThread.start();
synchronized
•  synchronizedキーワードを持つメソッドは1インスタ
ンスにつき、同時に1つしか起動できない(lockを
取得する) •  以下のようなhogeメソッドを使うと2行連続して
hogeが出てくることはありえない
// hogeとfugaの間に割り込めない
public synchronized void hoge() {
System.out.println(“hoge”);
System.out.println(“fuga”);
}
wait
•  各オブジェクトには待機中のスレッドがぶち込
まれるwait poolがある •  wait()をたたいたスレッドはそのwaitのレシー
バオブジェクトのwait poolに入る •  noTfy(), noTfyAll()されるまでじっとしてる
noTfy(), noTfyAll()
•  ロックを取得している(synchronizedメソッドの
中)で呼ぶとwait poolに入っているスレッドを
wait poolから出す(けど、まだロックを譲りはし
ない) •  noTfy()は狙ったスレッドだけをwait poolから
出す •  noTfyAll()は全部出す •  Wait/noTfy/noTfyAllは概念が難しいのでTask Queueの実装のところで詳細に話すよ
サンプルプログラムの説明
•  Eclipseにインポートできた? •  MulTThreadNumberFinder –  メインプログラム, 主にProducer役 •  Queue –  Task Queue役, push/popというメソッドを備える •  NumberFinder –  Consumer役(Worker Thread), Queueからタスクを
取り出して処理をする Queueの動作1: push()
•  値をqueueにつめる •  synchronizedメソッド
1をPush
Queue
1
Queueの動作2: pop()
•  FIFOなので現存する中で一番古くに詰められ
た値を返す •  synchronizedメソッド
New
Old
3
2
1
Pop 返り値は1
同時にpopしようとすると?
•  同時にpopできない –  pop()はsynchronizedだから! •  順番に実行されます
同時にpushしようとすると?
•  同時にpushできない –  push()はsynchronizedだから! •  順番に実行されます
空のときpopしようとすると?
•  キューが空であることを検知するととりあえず
wait •  これ以上減ることはない –  pop()はsynchronizedだから! •  Pushが実行されるとnoTfyAllされる –  wait poolから抜け出せる –  抜け出たころにはキューの中身が増えている –  取り出せて値を返すことができる キューが満タンのときにpushしようと
すると?
•  満タンであることを検知するととりあえずwait •  これ以上増えることはないことが保証されて
いる –  push()はsynchronizedだから! •  pop()が実行されるとnoTfyAllされる –  wait poolから抜け出ることができる –  抜けでたころにはキューの中身が減っている –  新しい値を詰めることができる
なんとなくわかったところで動かす
•  MulTThreadNumberFinderを起動してください •  1から100までの数を1スレッドでナベアツがア
ホになる数を探してみます •  1[Enter] •  100[Enter] •  1[Enter] •  と入力 •  探す数の範囲やスレッドの数を増やしたり減ら
したりして遊んでみよう 数の検査アルゴリズムを入れ替える
•  NumberFinderはQueueからタスクを取り出し、
一定のルールに合致する数を探すだけの働
きです •  「一定のルール」はNumberFindingAlgorithmオ
ブジェクトによって定義されます •  僕があらかじめ二つ入れておきました •  NabeatsuAlgorithm •  PrimeNumberFindingAlgorithm
数の検査アルゴリズムを入れ替える
• 
• 
• 
• 
• 
MulTThreadNumberFinder.javaを開いて algorithmTypeという変数の値を “PrimeNumberFindingAlgorithm” に変更！ またいろいろパラメータを変えながら遊んでみ
る
2つのアルゴリズムの実行時の差
•  NabeatsuAlgorithm: –  どちらかというとI/O Boundアルゴリズム –  CPUタイムをあまり食わない –  PopやnoTfyAllでCPUを食ってしまうため, スレッド
が少ないほうが実行効率がいい •  PrimeNumberFindingAlgorithm: –  完全なCPU Boundアルゴリズム –  PopやnoTfyAllより実際の計算の方が重いのでス
レッドを増やすとスループットがあがる
新しいアルゴリズムを実装せよ!
• 
• 
• 
• 
• 
1. NumberFindingAlgorithmを拡張するクラスを定義 2. NumberFindingAlgorithmFactoryを加筆修正 3. MulTThreadNumberFinderを加筆修正 実装したアルゴリズムの特徴を考察してみよう アルゴリズム案(思い浮かばない人用): – 
– 
– 
– 
桁の数字全部を足したもので割り切れる数字(ex: 120, 280) 回文になっている数字(ex: 123454321, 101, 89098) 自分の誕生日のn乗になっている数(ex: =26214=45/12→512) 16進数に変換するとA Fの文字しか使わない数(ex: 255) •  実装できたらhjsにアップしたりしてみんなで共有してみよう •  ひとり1個できたらおしまい