個室トイレ待ちをgolangで表現する

この記事に書いている事

• golangのsync.Mutex使った排他制御のサンプル
• Billie Eilish と 💩
• 排他制御で発生するオーバーヘッドについて
• あとがき

sync.Mutex使った簡単な排他制御

記事のタイトルがネタっぽいので最初に真面目な内容を説明します。
まず、排他制御とは複数のプロセス, スレッド, goroutineが同時に1つのリソース(メインメモリ上の特定のアドレス保存されている値など)に対してアクセスする場合に発生する競合を回避して、整合性を保つ処理の事です。
goでは、整合性を保つための方法の1つとしてsyncパッケージにMutexというtypeが用意されていて、これを使って1つのgoroutineしか特定の変数に対してアクセスできないように制御する事ができます。

使い方を分かりやすいように書くとこんな感じ
(本当は変数とmutexを一緒に構造体として定義するのが正しいですが分かりやすさを優先で書いてます)

package main

import (
	"fmt"
	"sync"
)

func main() {
	const worker = 100

	var count int
	var mutex sync.Mutex

	var wg sync.WaitGroup
	wg.Add(worker)

	for w := 0; w < worker; w++ {
		go func() {
			for i := 0; i < 1000; i++ {
				mutex.Lock()
				value := count
				value++
				count = value
				mutex.Unlock()
			}
			wg.Done()
		}()
	}
	wg.Wait()

	fmt.Printf("%d Count\n", count)
}

$ go run main.go
100000 Count

100個のgoroutineが変数countに対してmutex.Lock()でロックを取得してインクリメントしてmutex.Unlock()でロックを解除するという本当に単純なコードです。

もしも、ロックを取得せずに(14, 20, 24行目のmutexをコメントアウトして)何回か実行すると

$ go run main.go
66929 Count
$ go run main.go
60231 Count
$ go run main.go
64009 Count

100000になりません。
これは競合が発生しているからで、-race オプションをつけてbuildして実行することで競合を検知することができます。

$ go build -race
$ ./mutex 
==================
WARNING: DATA RACE
Read at 0x00c0000be008 by goroutine 8:
  main.main.func1()
      /Users/user/mutex/main.go:21 +0x45

Previous write at 0x00c0000be008 by goroutine 7:
  main.main.func1()
      /Users/user/mutex/main.go:23 +0x5b

Goroutine 8 (running) created at:
  main.main()
      /Users/user/mutex/main.go:18 +0xe7

Goroutine 7 (finished) created at:
  main.main()
      /Users/user/mutex/main.go:18 +0xe7
==================
==================
WARNING: DATA RACE
Read at 0x00c0000be008 by goroutine 9:
  main.main.func1()
      /Users/user/mutex/main.go:21 +0x45

Previous write at 0x00c0000be008 by goroutine 7:
  main.main.func1()
      /Users/user/mutex/main.go:23 +0x5b

Goroutine 9 (running) created at:
  main.main()
      /Users/user/mutex/main.go:18 +0xe7

Goroutine 7 (finished) created at:
  main.main()
      /Users/user/mutex/main.go:18 +0xe7
==================
29396 Count
Found 2 data race(s)

こんな感じで複数のgoroutineから1つの変数に対してロックを取得せずにアクセスすると競合がおきて正確さ(correctly)が失われます。

また、-raceをつけてbuildすると少し処理が重たくなります。
なので、前に実行した時(64009 Count)よりも変数の読み書きに不整合が生じやすくなって結果が29396 Countと小さい値になっています。

このように、1つの変数に対して複数のgoroutineからアクセスする時は、排他制御する必要があり、sync.Mutexが使えます。
(channelを使うことでも似たような事ができます)

上記のサンプルみてもらえればいいんですけど、排他制御はとても単純で

1. ロックを取得
2. 何かしらの処理
3. ロックを解除

これは、個室トイレに入ってすることとほぼ同じです。
1.トイレに入る
2.扉をロック
3.処理する
4.扉のロックを解除
5.外にでる

排他制御 ≒ 個室トイレ

これを、コードで表現してみたいと思います。

どうでもいいことですが、
処理をした回数をカウントしたいと思った時に、counterとしての変数名をどうするかが悩んで、
参考にしたのが
Billie Eilishの💩を語る動画(インスタだったかな？)
こんな記事読むのやめてほんとbillie eilish poopsで検索してほしい
I pooped eight times those are the best time in my life
とか言ってて面白いので....

とにかく、変数名は poops に決定して簡単に書いてみました。

package main

import (
	"fmt"
	"math/rand"
	"sync"
	"time"
)

type toiletBowl struct {
	name  string
	poops int
	mutex sync.Mutex
}

// 個室トイレでする処理
func (p *toiletBowl) poop(t int) {
	// 個室トイレに入って鍵をロック
	p.mutex.Lock()
	// 個室トイレを出る時に鍵をアンロック
	defer p.mutex.Unlock()
	// 処理時間(個人差があるのでt分waitさせる)
	time.Sleep(time.Duration(t) * time.Second)
	// あいつを増やす
	p.poops++
}

func (p *toiletBowl) collect() int {
	p.mutex.Lock()
	defer p.mutex.Unlock()
	return p.poops
}

func main() {
	var totalWaitTime float64
	rand.Seed(time.Now().Unix())
	waitTimes := make(chan float64)
	// トイレの前で待つ人の数(起動するgoroutineの数)
	human := 100
	// 5個の個室があるトイレをスライスで再現
	toilet := []*toiletBowl{{name: "A"}, {name: "B"}, {name: "C"}, {name: "D"}, {name: "E"}}

	wg := sync.WaitGroup{}

	start := time.Now()
	for i := 1; i <= human; i++ {
		wg.Add(1)
		// goroutineを人数分起動させてランダムな個室トイレの前で待たせる
		go func() {
			toilet[rand.Intn(5)].poop(rand.Intn(5))
			waitTimes <- time.Now().Sub(start).Seconds()
			wg.Done()
		}()
	}

	// 各人の処理開始時間からトイレを出た時間を合計する
	go func() {
		for w := range waitTimes {
			totalWaitTime = totalWaitTime + w
		}
	}()

	wg.Wait()
	close(waitTimes)

	fmt.Printf("Took %f Seconds\n", time.Now().Sub(start).Seconds())
	for _, t := range toilet {
		fmt.Printf("ToiletBowl %s is %d poops\n", t.name, t.collect())
	}
	fmt.Printf("Total wait time: %f Seconds\n", totalWaitTime)
}

で実行....

Took 50.038915 Seconds
ToiletBowl A is 25 poops
ToiletBowl B is 13 poops
ToiletBowl C is 20 poops
ToiletBowl D is 21 poops
ToiletBowl E is 21 poops
Total wait time: 2222.626789 Seconds

排他制御で発生するオーバーヘッドについて

この記事で伝えたいことはgoの sync.Mutex のことでも 💩や💩のことではないです。
上記の計測結果から、全体の処理時間は50秒であったのにも関わらず、各goroutineの待ち時間の合計は2222秒もかかっていることが分かると思います。
このことから並列処理の際に、排他制御で１つのリソースをロックするのはとてもオーバヘッドが大きいということが分かると思います。
goroutineの数が多くなればなるほど、待ち時間の合計はもっと増えるようになるでしょう。
なので並列処理 + 排他制御する場合は、それなりのオーバーヘッドがかかることを考慮にいれる必要があります。
ちなみに、goのgithubにMutexを使うべきかそれともchannelを使うべきかの説明されているので1度読むのをおすすめします。
https://github.com/golang/go/wiki/MutexOrChannel

One of Go's mottos is "Share memory by communicating, don't communicate by sharing memory."

とはじめに書いてありますが、

Don't be afraid to use a sync.Mutex if that fits your problem best

とも書いてあります。
なので、sync.Mutexを使う場合は sync.Mutexがbestなのかよく考えて 実装するのがよさそうです。
そして、sync.Mutexを使う場合はロックしてアンロックするまでの処理時間を極限まで短くすべきです。デバックのためのPrint文等をロック取得後の処理に記述するとパフォーマンスを著しく落とすことになるので注意が必要です。

ちなみに上記のコードをChannelを使った感じで書き直すことができるので普通にChannelを使える時は使った方が効率がよいです(個室トイレっぽくはなくなるけれども...)
Channelを使った並列処理のサンプルは以下の記事に少し書いているのでそちらも見てみてください。
https://qiita.com/suminofff/items/823774b1df9bab6a1336

あとがき

この記事から、トイレの待ち時間でどれだけ無駄な時間が発生しているかも分かったと思います。
なので、2人以上トイレに待ってるような場合は、個室トイレでの処理は限りなく短くするように促すこととトイレの数を増やすことが、社員の効率を上げることに繋がるかもしれません。