2014年12月 | プログラマーズ雑記帳

2014年12月別記事

エディターを乗り物に例えると 2014-12-17
データ共有の新潮流 - アクター, Agent, STM 2014-12-24

エディターを乗り物に例えると

Emacs

今回はエディター(開発ツール)について、ふと思ったことを書いてみます。

IDE : 公共の交通機関: 電車、バスなど (飛行機、新幹線は除く)

Visual Studio や Eclipse などの IDE は誰でもすぐに使える。
電車も切符を買えば簡単に乗れる。けど、決まった路線しか走れない。
Emacs : 自動車: 誰でもすぐ乗れるというわけではないが、乗りこなせるようになると、どこでも自由に行ける。
また、自由にチューンナップできる。しかも、現実と違ってチューンナップの部品はタダ
vi : 自転車(チャリンコ): 最初に乗れるようになるまで、練習が必要。
手軽に使えるけど、速度を出すには人力で頑張るのみ。
Vim : オートバイ: 自動車とどっちが好きかで、好みが分かれる。
ただ、自転車に乗れないとオートバイにも乗れない。

ちなみに、「バイク」というと本当は自転車のこと。エンジン(Auto) がついたのが「オートバイ」。

スポンサーサイト

データ共有の新潮流 - アクター, Agent, STM

関数型 Clojure 言語比較

スレッドなどの並列処理でデータを共有する場合、従来はロックを使って共有する方法が主流でした。
しかし、最近では関数型言語を中心に新しいデータの共有方法が出てきています。今回はその内の アクター、 Agent 、 STM について説明します。

これらの方式のうち、どれを採用するかは言語によって変わってきます。
わかりやすさと言語に依存しないようにするため、 C++ 風の擬似コードをサンプルとして説明し、その後実際の言語でのコードを挙げています。

ロック : 従来の方法の問題点

ロック方式とは

今までよく使われていたのは ロック や Mutex(排他制御) と呼ばれる方式です。

データを扱う場合、普通は次のような一連の処理になります。

データの読み取り
なにかの処理
データの更新(書き込み)

主にデータベース(DB)で使われる用語ですが、この関連・依存する複数の処理をまとめて トランザクション(transaction) 呼ばれています。

データ読み取りから書き込みまでの間によそから値が変更されると整合性に問題が生じます。このため、並列処理で共有しているデータを使う場合には、そのデータを変更する側がデータをロックし、他の処理からはアクセスできないようにします。

他の処理からも値を読み取るだけであれば、通常問題は無いのですが、読み取った値を更新に使うのかどうか分からないため、読み取りもロックされます。

この処理はすべて実行するか、全くしないかなので、アトミック(Atomic)実行とも呼ばれます。
ちなみに、原子のアトム(Atom)の名前も「これ以上分けられないもの」というところからきています。ただ、実際は科学が進んで、電子、陽子、中性子とさらに分けられることがわかっています。

ロック方式の問題点

ロック方式には大きな問題点があります。
それはロックしている間は他の処理が待ちになってしまう点です。せっかく並列処理にしているのに、他の処理が終わる待っているようではその時間が無駄になってしまいます。

ただ、この方式でも今まではそれほど問題ではありませんでした。それはコンピューターの多くが CPU が一つだけのシングルコアだったためです。
シングルコアの場合、並列処理といっても実際に動作しているのは一つの処理だけで、それを切り替えていく擬似的なものです。

しかし、最近では複数の CPU を積んだマルチコアが増えてきました。マルチコアでは並列処理は本当に平行して動作し、ロックによる待ちは時間のロスになってしまいます。
これから紹介する方式はマルチコア時代のための止めないデータ共有方法です。

アクターモデル (Actor Model) : メッセージの送信

アクターモデルとは

アクターモデル と呼ばれる方法では並列処理の一方から他の処理にメッセージ(データ)を送信します。この時、キューを使って受け渡しされるので、受け手の応答を待つ必要はありません。

送り手、受け手の要素をアクターといいます。棒人形を使って書いていますが、ユースケース図のアクターとはあまり関係無いです。

このアクターモデル、実はそれほど新しい概念というわけでもありません。プロセス間のメッセージキュー、 PC 間のソケット通信のような非同期通信と同じものです。アクターはそれをプログラム内で行います。
というよりも、アクターの方が定義が広く、それらの非同期通信もアクターモデルに入ります。もっと言えば、電子メール、郵便などもアクターモデルです。

アクターの処理

アクターを使う場合には、受け手側はループで待機し、データの受信をトリガーとして処理する仕組みにする必要があります。

// 受け手側の処理
void act(msgQueue)
{
    while (true)
    {
        int x = msgQueue.receive();
        print("Reciever : %d", x);
    }
}
// アクターを作成して、処理を登録
Actor agent;
agent.set_action(act);


// 受け手側の並列処理を起動
agent.start()


// 送り手側の処理
print("Sender : 1, 10");
agent.send(1);
agent.send(10);

$ pseudo actor.psd
Sender : 1, 10
Reciever :  1 
Reciever :  10

アクターは Scala, F#, Erlang(Elixir) といった関数型言語だけでなく、 Io, Fantom といったオブジェクト指向言語でも使わています。

新しい言語では言語の機能として取り込まれていますが、 Ruby での Celluloid ように昔からある言語でもライブラリーがあるものも多いです。
(昔といっても自分の中では結構最近だったのですが、この前、生まれたときから Ruby があるという人が Ruby の開発に参加しているというブログを見かけて若干ショックでした)

気を取り直し、ここでは F# を使って、サンプルコードを書いてみます。 F# ではアクターは MailboxProcessor というクラスを使って実現します。

open System
open Microsoft.FSharp.Control

let agent =
    new MailboxProcessor<int>(
        fun inbox ->
            let rec loop n = async {
                let! x = inbox.Receive ()
                System.Console.WriteLine ("Reciever :  {0} ", x)
                return! loop x
            }
            loop 0
    )

agent.Start()

System.Console.WriteLine ("Sender : 1, 10")
agent.Post(1)
agent.Post(10)

// 処理が終わらないように止めておく
System.Console.Read () |> ignore

Agent : アクターの改良

Agent とは

Agent はアクターとほぼ同じ意味で、アクターのサンプルコードで Agent を使っているのもわざとです。
ただ、 Agent というときはアクターとは微妙に違っています。 Wikipedia によるとエージェントシステムは多くの場合アクターモデルに何らかの制限を課している点が異なり、自発的で自律的であることが要求されるということらしいです。

例えば、 Visual Studio の C++ ライブラリーの Agent では、アクターのやり取りを一方向ではなく、双方向で行います。

非同期エージェントライブラリ

Agent はアクターモデルをベースとした非同期処理のための機能であることは共通していますが、ハッキリとどういった機能ということは決まっていないようです。
そのため、ここでは言語機能として Agent を採用している Clojure での agent の機能に限って説明していきたいと思います。

Clojure, Leiningen の Windows へのインストールと使い方 | プログラマーズ雑記帳

agent の処理

agent では、それ用の型(クラス)を用意します。データが変更される前に agent にアクセスすると更新前の値を返すので、必ず初期値が必要です。

agent の値を更新する場合は、値を直接送るのではなく、処理(関数)を渡します。送るのはトランザクション処理で、 agent は受け取った関数を自分で別スレッドを立てて実行し、データを変更します。

// 初期値 1 で Agent を作成
Agent foo(1);

// Agent に処理を送る
int act(int x)
{
    return x + 10;
}
foo.send(act)


// Agent の値を表示
print(foo);  // 11

これを Clojure で書くと次のようになります。

(def foo (agent 1))

(defn act [x]
  (+ x 10))
(send foo act)

(println @foo)  ; 11

;; agent を使うときは、これを呼ばないと終了しない
(shutdown-agents)

Clojure の agent は、状態を変更する必要があってもそれを待機する必要がない場合、複数の並列処理によって変更が行われるときにその順序は問題にならない場合など特定の場面でのみ使える簡易的なものです。(待機もできるのですが、それだとロックです)
そのため、 Clojure では他のデータ共有方法もいろいろ用意されていて、そのうちの一つが次の STM です。

STM (Software Transactional Memory) : トランザクションの管理

STM とは

最初に説明したトランザクションの用語はハードにある DB に対して使われることが多いですが、 STM はメモリー上にあるデータに対するトランザクション処理のシステムです。

STM ではトランザクションの処理は、それが明示的にわかるようにします。(サンプルでは transaction_block)
そのため、一方の処理がトランザクション中でも、読み取りだけなら、そのまま読み取れます。

// STM 用のデータを用意
stm_data<int> foo(1);


// 処理 B
async 
{
    sleep(1000);
    int tmp = foo.get();    // 読み取り
    print("B : Get %d", tmp);
}

// 処理 A (メイン)のトランザクション処理
transaction_block
{
    int tmp = foo.get();
    print("A : Get %d", tmp);
    sleep(2000);
    tmp += 10;
    foo.set(tmp);
    print("A : Set %d", tmp);
}

問題はトランザクション処理が並列実行で被った場合です。

この時の処理を逐次的に見ていきます。

例として、値が 1 である STM 用のデータ foo があったとします。
まず、値を読み取るときには特に問題なく並列処理 A, B ともに 1 を取得します。

処理 A は foo の値を 11 に更新します。この時、処理 B はまだ処理中です。

今度は処理 B が foo の値を 11 に更新しようとします。
しかし、ここで問題が生じます。処理 B の読み取り時の値は 1 なのに書き込もうとした時には 11 に変更されています。

STM では読み取り、書き込み時の値をログを取って覚えています。書き込もうとした時に読み取った時の値から変更されている場合、すなわちトランザクション中に値が変更された場合には 処理をもう一度繰り返します。

このようにトランザクションが被った場合には、その処理をやり直します。

アクターモデルは従来のロック方式と比べると受け手がループで待機しておく必要があり、シーケンスそのものがガラッと変わっています。それに対して STM は従来の方式と基本的な流れは同じで、処理を止めないように改良されています。
その代わり、トランザクション処理はやり直しがあり、何度も繰り返す可能性があります。このため、繰り返した際に結果が変わるようなものではダメで、副作用を起こさない(状態を変更しない)純粋な関数である必要があります。

また、トランザクション処理が頻発にかぶる場合にはやり直しが何度もおきて、パフォーマンスが低下します。

STM の処理

先ほどのシーケンスを擬似コードを使って書いてみます。

// STM 用のデータを用意
stm_data<int> foo(1);


// 処理 B
async 
{
    sleep(1000);
    // トランザクション処理
    transaction_block
    {
        int tmp = foo.get();    // 読み取り
        print("B : Get %d", tmp);
        sleep(2000);
        tmp += 10;
        foo.set(tmp);           // 書き込み
        print("B : Set %d", tmp);
    }
}

// 処理 A (メイン)のトランザクション処理
transaction_block
{
    int tmp = foo.get();
    print("A : Get %d", tmp);
    sleep(2000);
    tmp += 10;
    foo.set(tmp);
    print("A : Set %d", tmp);
}

出力は次のようになります。処理 A では最初の書き込みでは矛盾ができるのでやり直しています。
なお、次の Clojure で実際に実行した場合には IO の都合で少し出力順は変わります。

$ pseudo stm.psd
A : Get  1
B : Get  1
A : Set  11
B : Get  11
B : Set  21

STM を言語機能としてで対応しているのは Clojure と Haskell です。どちらも関数型言語ですが、トランザクション処理は純粋関数型である必要があるため、関数型言語の方が向いている機能だと思います。

Haskell の Windows へのインストールと Emacs モードの設定 | プログラマーズ雑記帳

STM としては Clojure の方が有名な気がするので、Clojure のコードを挙げておきます。

(def foo (ref 1))

(.start (Thread.
         (Thread/sleep 1000)
         (fn []
           (dosync
            (let [tmp @foo]
              (Thread/sleep 2000)
              (println "B : Get " tmp)
              (ref-set foo (+ tmp 10))
              (println "B : Set " (+ tmp 10)))))))

(dosync
 (let [tmp @foo]
   (Thread/sleep 2000)
   (println "A : Get " tmp)
   (ref-set foo (+ tmp 10))
   (println "A : Set " (+ tmp 10))))

なお、「やり直しではなく、トランザクションとしてアクセスするときだけロックした方がいい時もあるのでは？」と思った人もいるかもしれません。
確かにその通りで、やり直しの方法をとっているのは、単に Haskell や Clojure のデフォルトがそうだというだけです。例えば Clojure では ensure を使うとロックになります。
STM のポイントはトランザクション処理を管理する というところです。効率的に対処法を切り替えるなど、今後いろいろな発展が期待される分野です。

日	月	火	水	木	金	土
-	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31	-	-	-

プログラマーズ雑記帳