並行プログラミング言語(2)

並行システム

                               システム情報系情報工学域,
			       システム情報工学研究科コンピュータサイエンス専攻
                               新城 靖
                               <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

■ラムダ計算

並行性とは直接は関係ない。

◆構文

項とは 束縛と自由
β-簡約
(λx.M)N の形の項があった時に M の中の x の出現を E で置き換える。 (sed /x/N/ < M のような意味)
例: 条件判定 if a then b else c は、(ab)cのように書ける。

◆階乗

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)の値

◆Schemeのlambda

> (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
>

◆階乗(Scheme)

(define F
  (lambda (n)
    (if (= n 0) 1
        (* n (F (- n 1))))))
if は関数ではなくて、special form。

■並行オブジェクト指向モデル

オブジェクト指向の一種。世の中をオブジェクトとして扱う。

◆アクタモデル

1977年 C.Hewitt らによって提唱された並行計算モデル。 アクタと呼ばれる計算主体が独立に、かつ、並列に計算を行う能力を持つ。 アクタ内部も可能な限り並列に実行できる枠組みを持つ。

言語としては、何種類か(Plasma、Act-1、Act-2、Act-3、Omega、Ether)ある。 各言語で見かけがけっこうちがう。

アクタ、メッセージ、メールボックス

図? アクタの基本概念

アクタは、メッセージを受け取り、それに対して行為を行うような、通信を行う エージェントである。行為の種類には、次のようなものがある。

アクタは、メッセージを受信するために1つのメールボックスを持つ。 メッセージは、アクタに直接届くというよりは、メールボックスに間接的に届 く。メールボックスは、バッファリングの機能がある。メールボックスにある メッセージは、FIFO に処理されるとは限らない。

アクタがメッセージを受け取ると、いったんロックされる。ロックされるとメッ セージは処理されない。次のアクタに become したら、新しい後継のアクタが 同じメールボックスからメッセージを読み出して処理を続ける。

要素

アクタは、メッセージを送受信できる。 メッセージ自身も、アクタの一種。

◆アクタの継続

継続(continuation、継続点ともいう)を用いる。 究極の goto 文。C 言語の関数で
    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> []

◆階乗

[Hewitt 77a]
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)))))))

◆カウンタ(Scala)

Ted Neward: "多忙な Java 開発者のための Scala ガイド: Scala の並行性を掘り下げる", IBM DeveloperWorks, 2009年 4月 10日. 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) }    
  }
}

■並行論理プログラミング

◆Prolog

Prolog (Programming in Logic) は、フランスマルセイユ大学の Alain Colmerauer らによって開発された言語。 1階述語論理(first-order predicate logic)に基づいている。

◆1階述語論理

述語論理では、次のような概念を用いる。

1階述語論理の論理式は、次の形式で書ける。

P 1 ∨ P 2 ∨ ... ∨ P n ← Q 1 ∧ Q 2 ∧ ... ∧ Q n.

「←」の左がたかだか1個のものがホーン節(Horn clause)。(ORが複数書きたく なったら、複数行にわたって書く)。ホーン節には3種類ある。

◆単純なモデル(事実(fact))

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).

◆規則

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).  

A、B、Y、B1

図? Prolog の append

◆AND並列とOR並列

論理式の評価に順番の考え方はないので、並列に処理を行ってもよい。 OR並列を考えると、バックトラックという考えるは存在しなくなる。

◆quicksort

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).

A、B、

図? Prolog によるクイックソート

quicksort にある並列性

◆GHC (Guarded Horn Clauses)

Prolog と同様に、1階述語論理に基づいている。 並列(並行)論理型言語。

◆GHCの構文

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.
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=[].

■Jini

Jini (ジニー)は、Java を中核にした、情報家電製品を相互接続するための通 信技術。

1999年に、サン・マイクロシステムズ社のビル・ジョイらによって開発され発 表された。

Jini の目標は、ネットワークで Plug & Play を実現すること。 機器をネットワークに接続しただけで、特別な設定 をしなくてもすぐに利用可能になること。

目標

サービスには、ハード的なもの(プリンタ、ディジタルカメラ、CD Player) の他に、ソフト的なもの(スペルチェック、翻訳、アドレス帳)がふくまれる。

JavaSpaces は、内部的に Jini のルックアップ・サービスの実現で使われて いる。JavaSpaces も、Jini でアクセス可能なサービスの1つと考えることも できる。

◆UPnP (Universal Plugand Play)

Microsoft の、Jini に対抗した技術。

◆ルックアップ・サービス

Jini中心的な技術が、ルックアップ・サービス。

サービスの登録と検索

ルックアップ・サービス自身も、最初から知られている必要はない。 ネットワーク上で自動的に探される。 Discovery と Join。

◆リース

サービスは、永続的に登録されるではなくて、 特定の時間だけ利用可能になる。

Java のオブジェクトが Lease。

リース期間は、延長することができる。 延長されなかった lease は、ルックアップ・サービスから削除される。 登録されているサービスを明示的に削除する仕組みは、存在しない。

サービスが削除された時には、分散型イベント配送サービスにより関係してい る所に知らされる。

トランザクションのインタフェースは定められているが、具体的な実現は各サー ビスにまかされている。

◆Jiniを使うのに必要とされているもの

IPアドレスの割り当ては、Jiniの一部ではない。

◆サービス

サービスは、Java のオブジェクトで実現される。

サービスの提供者とサービスの利用者の間は、最終的にはに RMI で接続される。

ServiceIDLister インタフェースを implements する。

package com.sun.jini.lookup;
public interface ServiceIDListener extends java.util.EventListener {
    void serviceIDNotify(net.jini.core.lookup.ServiceID serviceID);
}
ルックアップ・サービスからコールバックされる。

◆Discovery と Join

各ネットワークには、ルックアップ・サーバを置く。

Discovery
Jini を使うには、まず、ルックアップ・サーバを探す。
Join
サービスの提供者が、インタフェースと属性をルックアップ・サーバに 登録する。

Discovery の実現方法

ルックアップ・サーバは、起動時、再起動時、224.0.1.84:4160 にMulticast Announcement Protocol で、利用可能性を広告する。

サービスの提供者がネットワーク上のルックアップサービスをマルチキャストで探す。

図1 マルチキャストによる Discovery

サービスの提供者がルックアップサービスにサービスオブジェクトを登録する。

図2 Join

◆サービスのグループ

サービスは、1つ以上のグループに属する。

グループは、名前(文字列)で区別される。

名前としては、DNS 風の表記のものが推奨されている。

◆JoinManager(サーバ側)

Discovery と 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

◆Jiniのサーバの例

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();
      }
   }
}

◆Lookup(クライアント側)

クライアントは、サービスを探す。

サービスの利用者がルックアップサービスに対してサービスオブジェクトを検索する。

図3 Lookup

サービスは、次の3つで区別される。 サービスを検索する時に ServiceTemplate のオブジェクトを作成する。 JavaSpaces のように、null を指定すれば、ワイルドカードを意味する。
    public ServiceTemplate(ServiceID serviceID,
                           Class[] serviceTypes,
                           Entry[] attrSetTemplates)
サービス(オブジェクト)の探し方
  1. LookupLocator により、マルチキャスト、または、 ユニキャストで ルックアップ・サービスを探す。
  2. ルックアップ・サービスのプロキシ ServiceRegistrar を作る。
  3. テンプレートを作り、ServiceRegistrar に渡す。
サービスを見つける過程で、サービス(オブジェクト)のRMI のスタブ(クライ アント側スタブ)が転送される。

◆サービスの利用

最終的にクライアントは、サービス・プロバイダを RMI で呼び出す。

サービスの利用者がサービスオブジェクトを通じてサーバを利用する。

図4 Invoke

◆Jiniのクライアントの例

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();
      }
   }
}

◆Leasing

信頼性が低いネットワークと、どう戦う方法の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 を使う。

練習問題

★問題(901) λ計算

次の式を簡約しなさい。階乗の例に習い、途 中の経過も示しなさい。

((λx.λy.(+ x y))1)10

★問題(902) Actorの並列性

Actorモデルで、並行性をどのように表現しているか。簡単に説明しなさい。

★問題(903) Prologの並列性

Prolog の処理系は、逐次的な動作を行っているが、同じプログラムを並列に動 作させることも考えられる。 quicksort の例で、どの部分に並列動作の可能性 があるか。簡単に説明しなさい。

★問題(904) Jini

Jini では、無線のように信頼性が低いネットワークを想定して、いくつかの工 夫がなされている。そのうちの1つを選んで簡単に説明しなさい。
Last updated: 2012/02/15 15:38:44
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>