並行システム システム情報系情報工学域, システム情報工学研究科コンピュータサイエンス専攻 新城 靖 <yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2011/2012-02-16
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/
参考文献
Marko Boger: Java in Distributed Systems: Concurrency, Distribution and Persistence, John Wiley & Sons, 2001. ISBN: 0471498386
http://www.dpunkt.de/buch/3-932588-32-0.html
(ドイツ語)
jivs code
F≡λx.(((=0 x)1)(*x(F(- x 1))))ただし、=0 という関数は、0 と等しい時に True、そうでない時に False を返 す。
例 2 の階乗 F2 → λx.(((=0 x)1)(*x(F(- x 1))))2 → -- Fの定義 (((=0 2)1)(*2(F(- 2 1)))) → -- β-簡約 ((False 1)(*2(F(- 2 1)))) → -- (=0 2) の値 ((λx.(λy.y) 1)(*2(F(- 2 1)))) → -- Falseの定義 ((λy.y)(*2(F(- 2 1)))) → -- β-簡約 (*2(F(- 2 1))) → -- β-簡約 (*2(F 1)) → -- (- 2 1)の値 (*2(λx.(((=0 x)1)(*x(F(- x 1))))1)) → -- Fの定義 (*2(((=0 1)1)(*x(F(- 1 1))))) → -- β-簡約 (*2((False 1)(*x(F(- 1 1))))) → -- (=0 1) の値 (*2((λx.(λy.y) 1)(*1(F(- 1 1))))) → -- Falseの定義 (*2((λy.y))(*1(F(- 1 1)))) → -- β-簡約 (*2(*1(F(- 1 1)))) → -- β-簡約 (*2(*1(F 0))) → -- (- 2 1)の値 (*2(*1(λx.(((=0 x)1)(*x(F(- x 1)))) 0))) → --Fの定義 (*2(*1(((=0 0)1)(*0(F(- 0 1)))) )) → -- β-簡約 (*2(*1((True 1)(*0(F(- 0 1)))) )) → -- (=0 0) の値 (*2(*1((λx.(λy.x) 1)(*0(F(- 0 1)))) )) → -- Trueの定義 (*2(*1 1)) → -- β-簡約 (*2 1) → -- (*1 1)の値 2 -- (*2 1)の値
> (define add1 (lambda (x) (+ x 1))) > (add1 2) 3 > ((lambda (x) (+ x 1)) 2) 3 > > (define sum-square (lambda (x) (lambda (y) (+ (* x x) (* y y))))) > sum-square #<procedure:sum-square> > (sum-square 1) #<procedure:349> > ((sum-square 1)2) 5 > > (lambda (x) (lambda (y) (+ (* x x) (* y y)))) #<procedure:429> > ((lambda (x) (lambda (y) (+ (* x x) (* y y))))1) #<procedure:488> > (((lambda (x) (lambda (y) (+ (* x x) (* y y))))1)2) 5 >
(define F (lambda (n) (if (= n 0) 1 (* n (F (- n 1))))))if は関数ではなくて、special form。
言語としては、何種類か(Plasma、Act-1、Act-2、Act-3、Omega、Ether)ある。 各言語で見かけがけっこうちがう。
アクタは、メッセージを受け取り、それに対して行為を行うような、通信を行う エージェントである。行為の種類には、次のようなものがある。
アクタがメッセージを受け取ると、いったんロックされる。ロックされるとメッ セージは処理されない。次のアクタに become したら、新しい後継のアクタが 同じメールボックスからメッセージを読み出して処理を続ける。
要素
goto f(1, 2, 3);のようなもの。
通常の階乗(in Scheme)
(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))継続を取るような階乗
(define (fact-c n c) (if (= n 0) (c 1) (let ((c2 (lambda (x) (c (* n x))))) (fact-c (- n 1) c2))))
実行例
> (fact 3)
6
> (fact 4)
24
> (fact-c 3 print)
6> (fact-c 4 print)
24>
factorial≡λm. match m <n c> if n = 1 then (send c <1>) else if n > 1 then (send factorial <(n-1) (λk.(send c <n * K>))>)3の階乗を計算して、継続print_answerに送りたい時には、 次のように書く。
(send factorial <3 print_answer>)
(define (Factorial( )) (Is-Communication (a doit (with customer =m) (with number =n)) do (become Factorial) (if (NOT (= n 0)) (then (send m 1)) (else (let (x = (new FactCust (with customer m) (with number n))) (send Factorial (a do (with customer x) (with number (- n 1))))))))) (define (FactCust (with customer =m) (with number =n)) (Is-Communicaton (a number k) do (send m (* n k))))
振る舞い記述 (define (名前 (with id パタン)) 通信ハンドラの並び) 通信ハンドラ (Is-Communication パタン do コマンド) letコマンド (let (変数名 = 式) do コマンド) 条件コマンド (if 式 (then do コマンドの並び) (else do コマンドの並び)) メッセージ送信コマンド (send メールボックス 値) becomコマンド (become 式) 新しいアクタの生成 (new 式)
(define (Account (with Balance =b)) (Is-Request (a Balance) do (reply b)) (Is-Request (a Deposit (with Amount =a)) do (become (Account (with Balance (+ b a)))) (reply (a Deposit-Receipt (with Amount a)))) (Is-Request (a Withdrawal (with Amount =a)) do (if (> a b) (then do (become (Account (with Balnce b))) (complain (an Overdraft))) (else do (become (Account (with Balnce(- b a)))) (reply (a Withdrawal-Receipt (with Amount n)))))))
http://www.ibm.com/developerworks/jp/java/library/j-scala04109.html
Ted Neward: "The busy Java developer's guide to Scala: Dive
deeper into Scala concurrency", IBM DeveloperWorks, 10 Apr 2009.
http://www.ibm.com/developerworks/java/library/j-scala04109.html
リスト 9. Counter の例 (アクターによる方法) より。
object CountingSample { case class Incr case class Value(sender : Actor) case class Lock(sender : Actor) case class UnLock(value : Int) class Counter extends Actor { override def act(): Unit = loop(0) def loop(value: int): Unit = { receive { case Incr() => loop(value + 1) case Value(a) => a ! value; loop(value) case Lock(a) => a ! value receive { case UnLock(v) => loop(v) } case _ => loop(value) } } } def main(args : Array[String]) : Unit = { val counter = new Counter counter.start() counter ! Incr() counter ! Incr() counter ! Incr() counter ! Value(self) receive { case cvalue => Console.println(cvalue) } counter ! Incr() counter ! Incr() counter ! Value(self) receive { case cvalue => Console.println(cvalue) } } }
1階述語論理の論理式は、次の形式で書ける。
P 1 ∨ P 2 ∨ ... ∨ P n ← Q 1 ∧ Q 2 ∧ ... ∧ Q n.
「←」の左がたかだか1個のものがホーン節(Horn clause)。(ORが複数書きたく なったら、複数行にわたって書く)。ホーン節には3種類ある。
fatherof(isaac,abraham). -- isaac の父は abraham である fatherof(ishmail,abraham). fatherof(shuah,abraham). fatherof(jacob,isaac). fatherof(esau,isaac). fatherof(reuben,jacob). fatherof(dinah,jacob). fatherof(dan,jacob). fatherof(asher,jacob). fatherof(joseph,jacob). motherof(isaac,sarah). -- isaac の母は sarah である。 motherof(ishmail,hagar). motherof(shuah,ketura). motherof(jacob,rebeccah). motherof(easu,rebeccah). motherof(reuben,leah). motherof(dinah,leah). motherof(dan,bilhah). motherof(asher,zilpah). motherof(joseph,rachel).
"_"
は、無名変数。値は残らない。
"motherof(isaac,_)?"
の質問には、
"motherof(isaac,sarha)"
だけがマッチする。
"fatherof(_,_)"
の質問には、全ての"fatherof"
がマッ
チする。
"fatherof(joseph,X)"
の質問には、"X=jacob"
の時に
マッチする。この時に変数 "X"
は、"jacob"
に束縛(bind)されている。
"motherof(C,leah)?"
の質問には、
"C=reuben"
という束縛が起きた後に、
バックトラックが行われて、「別のコンテキストで」
"C=dinah"
という束縛が起きることがある。
parentof(C,P) :- motherof(C, P). -- P が C の母なら、 P は C の親である。 parentof(C,P) :- fatherof(C, P). -- P が C の父なら、 P は C の親である。 grandparentof(C,GP) :- parentof(C,P), parentof(P,GP). -- C の親が P で、かつ、P の親が GP なら、GP は C の祖父母である。 ancestor(C,A) :- parentof(C,A). ancestor(C,A) :- parentof(C,P), ancestor(P,A). -- C の親が P で、かつ、P の祖先が A ならば、A は C の祖先である。
teaches(name(shinjo,yasushi),01CH303,time(fri,3)).
append([],Y,Y). append([A|B],Y,[A|B1]) :- append(B,Y,B1).
図? Prolog の append
quicksort(List,Sorted) :- qsort(List, Sorted, []). qsort([],H,H). qsort([A|B],H,T) :- partition(B,A,S,L), qsort(S,H,[A|T1]), qsort(L,T1,T). partition([],X,[],[]). partition([A|B],X,[A|S],L) :- A<X, partition(B,X,S,L). partition([A|B],X,S,[A|L]) :- A>=X, partition(B,X,S,L).
図? Prolog によるクイックソート
quicksort にある並列性H :- G 1, G 2,...,G n | B 1, B 2, ..., B m.
「|」は、コミット演算子。 G 1, G 2,...,G n はガード部。 B 1, B 2, ..., B m は、ボディ部。append([A|X1],Y,Z) :- true | Z = [A|Z1], append(X1,Y,Z1). append([],Y,Z) :- true | Z=Y.Prolog ならこうなる
append([A|X1],Y,[A|Z1]) :- append(X1,Y,Z1). append([],Y,Y).H 1 :- G 11, G 12,...,G 1n | B 11, B 12, ..., B 1m. H 2 :- G 21, G 22,...,G 2n | B 21, B 22, ..., B 2m.
:- append(U,[4,5],W),U=[1,2,3].なら、append の処理は最初は中断する。U が具体化された後で再開する。
quicksort(Xs,Ys) :- true | qsort(Xs, Ys-[]). qsort([X|Xs],Ys0-Ys3) :- true | partition(Xs,X,S,L), qsort(S,Ys0-Ys1), Ys1=[X|Ys2], qsort(L,Ys2-Ys3). qsort([],Ys0-Ys1) :- true | Ys0 = Ys1. partition([X|Xs],A,S,L0) :- A<X | L0=[X|L1], partition(Xs,A,S,L1). partition([X|Xs],A,S0,L) :- A>=X | S0=[X|S1], partition(Xs,A,S1,L). partition([],A,S,L) := true | S=[], L=[].
1999年に、サン・マイクロシステムズ社のビル・ジョイらによって開発され発 表された。
Jini の目標は、ネットワークで Plug & Play を実現すること。 機器をネットワークに接続しただけで、特別な設定 をしなくてもすぐに利用可能になること。
目標
JavaSpaces は、内部的に Jini のルックアップ・サービスの実現で使われて いる。JavaSpaces も、Jini でアクセス可能なサービスの1つと考えることも できる。
Microsoft の、Jini に対抗した技術。
サービスの登録と検索
ルックアップ・サービス自身も、最初から知られている必要はない。 ネットワーク上で自動的に探される。 Discovery と Join。
Java のオブジェクトが Lease。
リース期間は、延長することができる。 延長されなかった lease は、ルックアップ・サービスから削除される。 登録されているサービスを明示的に削除する仕組みは、存在しない。
サービスが削除された時には、分散型イベント配送サービスにより関係してい る所に知らされる。
トランザクションのインタフェースは定められているが、具体的な実現は各サー ビスにまかされている。
サービスの提供者とサービスの利用者の間は、最終的にはに RMI で接続される。
ServiceIDLister インタフェースを implements する。
package com.sun.jini.lookup; public interface ServiceIDListener extends java.util.EventListener { void serviceIDNotify(net.jini.core.lookup.ServiceID serviceID); }ルックアップ・サービスからコールバックされる。
Discovery の実現方法
図1 マルチキャストによる Discovery
図2 Join
グループは、名前(文字列)で区別される。
Jini パッケージは、JoinManager という参照クラスを含む。
public JoinManager(Object obj, Entry[] attrSets, ServiceIDListener callback, LeaseRenewalManager leaseMgr) throws IOException public JoinManager(Object obj, Entry[] attrSets, String[] groups, LookupLocator[] locators, ServiceIDListener callback, LeaseRenewalManager leaseMgr ) throws IOException
import java.rmi.*; public interface RemoteBall extends Remote { public void hit() throws java.rmi.RemoteException; }
import java.rmi.*; import java.rmi.server.*; import net.jini.core.lookup.*; import com.sun.jini.lookup.*; public class Ball extends UnicastRemoteObject implements RemoteBall, ServiceIDListener { public Ball() throws RemoteException { super(); } public void serviceIDNotify(ServiceID id) { System.out.println("ServiceId is "+id); } public void hit() { System.out.println("Ball has been hit"); } }
import java.rmi.*; import net.jini.core.entry.*; import net.jini.lookup.entry.*; import com.sun.jini.lookup.*; import com.sun.jini.lease.*; public class BallStarter { public static void main(String[] args) { try { System.setSecurityManager(new RMISecurityManager()); RemoteBall ball = (RemoteBall) new Ball(); LeaseRenewalManager renewal = new LeaseRenewalManager(); Entry[] attributes = new Entry [] { new Name("Jini enabled ball")}; JoinManager join = new JoinManager( ball, attributes, (Ball) ball, renewal ); System.out.println("Ball started and registered at Lookup-Server"); } catch (Exception e) { e.printStackTrace(); } } }
図3 Lookup
サービスは、次の3つで区別される。public ServiceTemplate(ServiceID serviceID, Class[] serviceTypes, Entry[] attrSetTemplates)サービス(オブジェクト)の探し方
import java.rmi.*; import net.jini.core.discovery.*; import net.jini.core.lookup.*; public class Bat { public Ball ball; public void play(RemoteBall ball) { try { ball.hit(); System.out.println("I hit the ball"); } catch (RemoteException e) { System.out.println(e); } } public static void main (String[] args) { Bat bat = new Bat(); try { System.setSecurityManager(new RMISecurityManager()); LookupLocator locator = new LookupLocator("jini://localhost"); ServiceRegistrar registrar = locator.getRegistrar(); Class[] classes = new Class[] { RemoteBall.class }; ServiceTemplate template = new ServiceTemplate( null, classes, null); RemoteBall remoteBall = (RemoteBall) registrar.lookup(template); bat.play(remoteBall); } catch (Exception e) { e.printStackTrace(); } } }
信頼性が低いネットワークと、どう戦う方法の1つ。
lease には、期限がある。
期限の長さは、交渉可能。 期限が短い(1分以下、数秒)というのは、あまり想定されていない。
リースの利点
Jini のサービスを提供しているオブジェクトは、Lease インタフェースを実 装している。
public interface Lease { long FOREVER = Long.MAX_VALUE; ... long getExpiration(); void renew(long duration) throws LeaseDeniedException, UnknownLeaseException, RemoteException; void cancel() throws UnknownLeaseException, RemoteException; ... }getExpiration() で、リースの残り時間がわかる。ミリ秒単位。
renew() で延長する。 延長できない時には、LeaseDeniedException が返される。
もう使わなくなった時には、cancel() できる。 期限切れと同じことになる。
リースの管理には、LeaseRenewalManager を使う。
((λx.λy.(+ x y))1)10