tshimizu's diary

日々の記録

サンタクロース問題（スレッド・アクター・チャンネル）

はじめに

この記事は Treasure Advent Calendar 2018 23日目の記事です。

今回はクリスマスにちなんで、並列プログラミングの古典的なトピックである「サンタクロース問題」を取り上げます。この問題を、並列処理を記述するための一般的なモデルであるスレッド(Java)、アクター(Java, Akka)、そしてチャンネル(Go)を使ってそれぞれどのようになるか試しに書いてみます。

各言語、ライブラリについて、「らしい書き方」ができていない部分も多いかと思います。特に、ビジーループを使ってしまっている部分はもっと適切な方法がありそうです。「もっとこう書いたほうが良さそう。」などあれば、教えていただけるとありがたいです。

サンタクロース問題

サンタクロースの家には、１人のサンタクロースとそれぞれ複数のトナカイと妖精が住んでいます。いま、サンタクロースは家で寝ていますが、トナカイと妖精は外へ出かけていいます。サンタクロースは、状況に合わせて次の行動をとります。

  • 妖精が３人集まった場合
    • 起床して新しいおもちゃの開発をする。
    • 終わったら解散してまた眠る。
  • トナカイが９匹集まった場合
    • 起床してプレゼントを届けに出かける。
    • 終わったら解散してまた眠る。

今回は妖精は9人、トナカイは27匹存在し、それぞれ１回のみ働くとします。すべての妖精とトナカイが仕事をしたら終了です。

実装

ここでは、各実装の概要のみを説明します。それぞれの実装の詳細は以下のリンク先に置いてあります。

スレッド（Java）

妖精とトナカイをそれぞれThreadを継承したクラスとして定義し、フィールドとしてサンタのオブジェクトをもたせるようにしました。

コード（一部抜粋）

public class Santa {
    /* ... */

    public void addElf(){
        synchronized (this){
            if(this.state == 0 && this.elfCount < elfMax) this.elfCount++;
            if(this.elfCount == elfMax) develop();
        }
    }

    /* ... */

    private void develop(){
        this.state = 1;
        System.out.println("Santa starts to develop.");
    }

    /* ... */
}


public class Elf extends Thread {
    final private String name;
    
    /* ... */

    @Override
    public void run() {
        while(!this.working){
            synchronized (this.santa){
                if(this.santa.getState() == 0){
                    System.out.println(this.name + " start to wait.");
                    this.santa.addElf();
                    this.working = true;
                }
            }
        }
        while(this.working){
            synchronized (this.santa){
                if(this.santa.getState() == 1){
                    this.santa.remElf();
                    this.working = false;
                    System.out.println(this.name + " finished working.");
                }
            }
        }
    }
}

環境：Java8

アクター（Java, Akka）

アクターはそれぞれが処理主体で、個別にメールボックス（受信メッセージを貯めておくキュー）を持っています。異なるアクター同士のメッセージのやり取りによって全体の処理が進んでいきます。アクター上では、常に１個以下のメッセージがシングルスレッドで処理されるので、ロックなどの排他制御の記述が基本的には登場しません。Akkaにおいては、アクターに受信したメッセージの振る舞いを記述することによって、アクターを定義します。他のアクターへのメッセージは、ActorRef 型のメッセージ用の参照を介して送信され、直接アクターオブジェクトの状態をいじるようなことはできなくなっています。

サンタと妖精、トナカイをそれぞれアクターとして定義しました。外出先からサンタの元に帰ってくる行為や、仕事の完了通知などは、それぞれ個別のメッセージとして定義しています。

コード（一部抜粋）

public class Santa extends AbstractActor {

    /* ... */

    @Override
    public Receive createReceive() {
        return receiveBuilder()
                .match(Messages.AddElfMsg.class, this::addElfMsg)
                .match(Messages.AddReindeerMsg.class, this::addReindeerMsg)
                .match(Messages.StoppedElfMsg.class, this::stoppedElf)
                .match(Messages.StoppedReindeerMsg.class, this::stoppedReindeer)
                .build();
    }

    private void addElfMsg(Messages.AddElfMsg msg){
        this.elfSet.add(msg.ref);
        if(this.elfSet.size() == elfMax){
            develop();
        }
    }

    /* ... */

    private void develop(){
        System.out.println("Santa starts to develop.");
        for (ActorRef ref : this.elfSet) {
            ref.tell(new Messages.FinishWorkingMsg(), this.getSelf());
        }
        this.elfSet = new HashSet<>();
        System.out.println("Santa starts to sleep..");
    }

    /* ... */

    private void stoppedElf(Messages.StoppedElfMsg msg){
        this.stoppedElfCount++;
        terminateSystem();
    }

    /* ... */
}


public class Elf extends AbstractActor {
    final private String name;
    final private ActorRef santaRef; 

    /* ... */

    @Override
    public Receive createReceive() {
        return receiveBuilder()
                .match(Messages.StartWorkingMsg.class, this::addElf)
                .match(Messages.FinishWorkingMsg.class, this::finishWorking)
                .build();
    }

    private void addElf(Messages.StartWorkingMsg msg){
        System.out.println(this.name + " starts to work.");
        this.santaRef.tell(new Messages.AddElfMsg(this.getSelf()), this.getSelf());
    }

    private void finishWorking(Messages.FinishWorkingMsg msg){
        System.out.println(this.name + " has finished working.");
        this.santaRef.tell(new Messages.StoppedElfMsg(), this.getSelf());
        this.context().system().stop(this.getSelf());
    }
}

// 各メッセージはクラスとして定義
public class Messages {
    public static class AddElfMsg {
        public ActorRef ref;

        public AddElfMsg(ActorRef ref){
            this.ref = ref;
        }
    }

    /* ... */
}

環境：Java8, Akka 2.5.19

チャンネル（Go）

サンタと妖精、トナカイをそれぞれ関数として定義してgroutineを起動させました。それぞれやり取りについては、チャンネルを介して行っています。アクターと同様に、チャンネルへの書き込みはメッセージと見ることができそうです。ただ、アクターの場合との違いとしては、送信先の存在を直接知っているのではなく、チャンネルという共通のメッセージ置き場を介して、受信側も能動的にメッセージを取りに行っている（ように見える）という点でしょうか。

コード（一部抜粋）

type Streams struct {
    ElfChan           chan int
    ReindeerChan      chan int
    NotifElfChan      chan int
    NotifReindeerChan chan int
}

func main() {
    wg := sync.WaitGroup{}

    streams := Streams{
        ElfChan:           make(chan int),
        ReindeerChan:      make(chan int),
        NotifElfChan:      make(chan int),
        NotifReindeerChan: make(chan int),
    }

    wg.Add(1)
    go santa(&wg, streams)

    for i := 0; i < elfSize; i++ {
        wg.Add(1)
        go elf(&wg, i, streams.ElfChan, streams.NotifElfChan)
    }

        /* ... */

    wg.Wait()
}

func santa(wg *sync.WaitGroup, streams Streams) {
    defer wg.Done()

    elfCount := 0
    reindeerCount := 0

        /* ... */

    for {
        select {
        case t := <-streams.ElfChan:
            elfCount += t
        case t := <-streams.ReindeerChan:
            reindeerCount += t
        default:
            fmt.Println("Santa starts to sleep.")
        }

        if elfCount >= 3 {
            fmt.Println("Santa starts to develop.")
            for i := 0; i < 3; i++ {
                streams.NotifElfChan <- 1
            }
            elfCount = 0
            developCount++
        }

                /* ... */

        if developCount == elfSize/3 && shipCount == reindeerSize/9 {
            break
        }
    }
}

func elf(wg *sync.WaitGroup, num int, elfChan chan int, Notif chan int) {
    defer wg.Done()
    fmt.Println("start elf-", num)

    elfChan <- 1

    <-Notif

    fmt.Println("end elf-", num)
}

環境：go 1.10.1

最後に

アクターを使った書き方が、物理的な世界とのイメージとの対応という意味で、問題を一番自然に記述できた気がします。「メッセージを投げたらあとは知らない」といった雰囲気で、サンタと妖精、トナカイがそれぞれ完全に独立した存在として記述できると感じました。共有するロックやチャンネルが登場しないことが大きいかもしれません。

普通のプログラミングにおける「FizzBuzz」のようなものとして、新しい並列プログラミングのスタイルを試すときに「サンタクロース問題」も使えそうです。

参考