sync.Mutex の仕組みを調べてみた

はじめに

sync.Mutex の Lock メソッドや Unlcok メソッドを使うことでアトミックに値の操作を行うことができますが、これらの仕組みが一体どうなっているのか調べてみたので記事にまとめました。

ざっくりまとめ

2つのスレッドで sync.Mutex を利用して lock/unlock するシーケンス図を以下にまとめました。 sync.Mutex には state と sema の2つのフィールドがあり、これらの値によって状態を保持します。

Lock メソッド実行時に既に lock されている場合は runtime_SemacquireMutex 関数で待機します。他のスレッドで Unlock メソッドが実行されて、その中で runtime_Semrelease 関数が実行されると、 runtime_SemacquireMutex 関数で待機していたスレッドに notify されて処理が再開します。

次の章から、sync.Mutex の使い方や、詳細をみていきます。

使い方

かんたんに sync.Mutex の使い方をおさらいします。
今回は、A Tour of Go のコードを例にみてみます。

以下のように、 sync.Mutex 型の変数をフィールドにもつ SafeCounter 構造体を定義したとします。
Inc メソッドでアトミックに値を操作していますが、このようにクリティカルセクションを Lock メソッドと Unlock メソッドで囲むように使用します。 defer c.mu.Unlock() のように書くことも多いかと思います。

// SafeCounter is safe to use concurrently.
type SafeCounter struct {
	mu sync.Mutex
	v  map[string]int
}

// Inc increments the counter for the given key.
func (c *SafeCounter) Inc(key string) {
	c.mu.Lock()
	// Lock so only one goroutine at a time can access the map c.v.
	c.v[key]++
	c.mu.Unlock()
}

Mutex 構造体

先ほど、sync.Mutex をゼロ値のまま使う例を示しましたが、構造体のフィールドは以下のようになっています。 sync.Mutex のゼロ値は unlock されている状態となるので、state と sema が0の場合は unlock されています。

type Mutex struct {
	state int32
	sema  uint32
}

Lock の仕組み

sync パッケージをみてみると、Lock メソッドは以下のように実装されています。

// Lock locks m.
// If the lock is already in use, the calling goroutine
// blocks until the mutex is available.
func (m *Mutex) Lock() {
	// Fast path: grab unlocked mutex.
	if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
		if race.Enabled {
			race.Acquire(unsafe.Pointer(m))
		}
		return
	}
	// Slow path (outlined so that the fast path can be inlined)
	m.lockSlow()
}

CompareAndSwapInt32 は初見だと何やってるかよくわからないかと思います。これは、Compare-and-swap(CAS) と呼ばれるアトミックな命令になります。指定したポインタの値を比較 (compare) して、等しい場合には値を交換 (swap) します。

CAS の擬似的なコードは以下のようになります。 pointer が指しているアドレスの値が old と等しい場合は、 new の値を代入して true を返し、等しくない場合は何もしないまま false を返します。

function cas(p: pointer to int, old: int, new: int) is
    if *p ≠ old
        return false

    *p ← new

    return true

つまり、atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) では、 state フィールドの値が0の場合は state を mutexLocked に更新して、true を返します。

ちなみに、state の値は以下のように定義された定数が利用されます。

const (
	mutexLocked = 1 << iota // mutex is locked
	mutexWoken
	mutexStarving
	mutexWaiterShift = iota
)

その後の race.Enabled は定数の false なので無視して良さそうです。したがって、1回目の Lock メソッドでは state に mutexLocked フラグを代入して、処理が終わります。

つづけて unlock しないまま、他のスレッドなどで lock した場合を考えてみます。
すると、 atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) は state の値が0ではないので、false を返します。したがって、2回目の実行では lockSlow が実行されます。

lockSlow

lockSlow は複雑な処理をしているのですが、 かなりざっくりと書くと以下のようになっています。 m.state を新しい値に更新した後、runtime_SemacquireMutex を実行しています。このメソッドを実行すると、第一引数のポインタが指す値が0よりも大きくなるまで待機します。 runtime_SemacquireMutex の詳細が気になる方は、runtime パッケージの sema.go を読んでみてください。

Lock メソッドが2回呼ばれて、まだ unlock されていないと仮定すると m.sema の値は0になるので、ここで値が変わるのを待機します。

func (m *Mutex) lockSlow() {
	for {
		...
		if atomic.CompareAndSwapInt32(&m.state, old, new) {
			...
			runtime_SemacquireMutex(&m.sema, queueLifo, 1)
			...
		}
		...
	}
}

Unlock の仕組み

Unlock のコードは以下のようになります。 AddInt32 の返り値は計算した結果となるので、m.state の値が mutexLocked だった場合は m.state の値が0になって処理が終了します。
それ以外の場合は、 unlockSlow メソッドを実行します。つまり、先ほどの lockSlow メソッドによって m.state が mutexLocked 以外の値に更新されていた場合は、この unlockSlow が実行されます。

func (m *Mutex) Unlock() {
	if race.Enabled {
		_ = m.state
		race.Release(unsafe.Pointer(m))
	}

	// Fast path: drop lock bit.
	new := atomic.AddInt32(&m.state, -mutexLocked)
	if new != 0 {
		// Outlined slow path to allow inlining the fast path.
		// To hide unlockSlow during tracing we skip one extra frame when tracing GoUnblock.
		m.unlockSlow(new)
	}
}

unlockSlow

unlockSlow メソッドをかなりざっくりと書くと以下のようになっています。
runtime_Semrelease で &m.sema の値をインクリメントして、 Semacquire で待機しているゴルーチンに notify します。
このメソッドも詳細が気になる方は、sema.goを読んでみてください。

したがって、unlockSlow を実行することで、lockSlow の runtime_SemacquireMutex で待機していたスレッドに通知がとんで、処理が再開するという流れになります。

func (m *Mutex) unlockSlow(new int32) {
	...
	runtime_Semrelease(&m.sema, false, 1)
	...
}

さいごに

ここまでで Lock と Unlock の詳細をみてきたので、図を再掲しておきます。この記事を読むより、少しでも sync.Mutex の処理がイメージしやすくなれば幸いです。