sync.Mutexの仕組みを理解する

Transcript

1. sync.Mutexの仕組み
   を理解する
   Go Conference 2023/06/02
   

   View Slide

2. 自己紹介
   Name
   ● Yoshiki Fujikane (ふじを)
   Company
   ● CyberAgent, Inc. 22新卒入社
   ● ABEMA バックエンドエンジニア
   @ffjlabo
   @ffjlabo
   

   View Slide

3. ● 排他制御を実現するプリミティブ
   ● 共有リソースに対する競合を起こさず
   並行処理を実装できる
   sync.Mutexとは
   

   View Slide

4. ● 排他制御を実現するプリミティブ
   ● 共有リソースに対する競合を起こさず
   並行処理を実装できる
   sync.Mutexとは
   🤔どうやって実現してるのだろう
   

   View Slide

5. sync.Mutex
   の仕組みが知りたい
   背景
   

   View Slide

6. 本発表の目的
   ● sync.Mutexの内部実装について把握する
   ● sync.Mutexの仕組みを原理から理解する
   

   View Slide

7. ʕ◔ϖ◔ʔ> Let’s≡Go
   $ git checkout 7f1467ff4ddd882acb318c0ffe24fd3702ce75cc
   

   View Slide

8. ● sync.Mutexが実現する排他制御
   ● sync.Mutexの構造
   ● Lock()の内部実装
   ● 実装背景
   ● まとめ
   アジェンダ
   

   View Slide

9. ● sync.Mutexが実現する排他制御
   ● sync.Mutexの構造
   ● Lock()の内部実装
   ● 実装背景
   ● まとめ
   アジェンダ
   

   View Slide

10. 「リソースへアクセスできるのは 1 goroutineのみ」
    sync.Mutexが実現する排他制御
    

    View Slide

11. リソースへのアクセスが複数来ても、1goroutineのみアクセスを許可
    sync.Mutexが実現する排他制御
    resource
    G
    G
    G
    Mutex
    ✅
    ❌
    ❌
    

    View Slide

12. 1goroutineのみにアクセスを制限するには？
    sync.Mutexが実現する排他制御
    

    View Slide

13. A. 「リソースへのアクセス状況」を記録しておく
    sync.Mutexが実現する排他制御
    

    View Slide

14. リソースへアクセスが来た段階でその状態を変数として記録しておく
    「リソースへのアクセス状況」を記録
    resource
    G
    Mutex
    Locked = false
    

    View Slide

15. リソースへアクセスが来た段階でその状態を変数として記録しておく
    「リソースへのアクセス状況」を記録
    resource
    G
    Mutex
    Locked = true
    ✅
    

    View Slide

16. 別goroutineがアクセスしてきたとき、その変数を元に制御可能！
    「リソースへのアクセス状況」を記録
    resource
    G
    G
    G
    Mutex
    ✅
    ❌
    ❌
    Locked = true
    

    View Slide

17. sync.Mutexが実現する排他制御: まとめ
    ● sync.Mutexの排他制御とは
    「リソースへのアクセスを1 gorutineのみに制限する」
    こと
    ● リソースへのアクセス状況を保持しておくことで実現
    

    View Slide

18. ● sync.Mutexが実現する排他制御
    ● sync.Mutexの構造
    ● Lock()の内部実装
    ● 実装背景
    ● まとめ
    アジェンダ
    

    View Slide

19. 2つの状態変数を保持
    ● state
    ○ Mutexの現在の状態を表す
    ● sema
    ○ goroutineの待機、解放を管理するためのセマフォ
    sync.Mutexの内部構造
    src/sync/mutex.go
    

    View Slide

20. state
    Mutexのロック取得を待機している goroutine（waiter）の数 Mutexの状態
    32bit
    29bit 3bit
    src/sync/mutex.go
    

    View Slide

21. state: Mutexの状態
    ● Mutexの状態は3種類
    ● 各bitがそれぞれの状態に対応
    S W L
    src/sync/mutex.go
    

    View Slide

22. state: Mutexの状態
    ● mutexLocked
    ○ Mutexがロックされた状態
    S W L
    src/sync/mutex.go
    

    View Slide

23. mutexLocked: イメージ
    「ロックを獲得したgoroutineが存在する」状態
    G
    G
    Mutex
    ✅
    ❌
    

    View Slide

24. state: Mutexの状態
    ● mutexWoken
    ○ 該当Mutexをロックしようとgoroutineが起動した状態
    S W L
    src/sync/mutex.go
    

    View Slide

25. mutexWoken: イメージ
    「ロックしようとするgoroutineが存在する」状態
    G
    G
    Mutex
    

    View Slide

26. state: Mutexの状態
    ● mutexStarving
    ○ 該当Mutexを長期間ロックできずにいるgoroutineが存在する状態
    ○ 飢餓状態（Starving mode）と呼ばれる
    S W L
    src/sync/mutex.go
    

    View Slide

27. mutexStarving: イメージ
    「一定時間以上ロックを待たされているgoroutineが存在する」状態
    G
    G
    G
    Mutex
    ✅
    ❌
    G
    
    もうずっと待ってるんだけどな …
    

    View Slide

28. ● バイナリセマフォ
    ○ sema == 0 => リソースが占有された状態
    ○ sema == 1 => リソースが解放された状態
    sema
    runtimeレベルのロック状況を管理するために利用される（詳細は後ほど）
    src/sync/mutex.go
    

    View Slide

29. sync.Mutexの構造: まとめ
    ● sync.Mutexには2つの状態変数が存在
    ○ state: Mutexの様々な状況を表現
    ○ sema: バイナリセマフォでruntimeレベルのロック状況を表現
    

    View Slide

30. sync.Mutexの構造: まとめ
    ● sync.Mutexには2つの状態変数が存在
    ○ state: Mutexの様々な状況を表現
    ○ sema: バイナリセマフォでruntimeレベルのロック状況を表現
    🤔 なぜ2つも状態変数が存在する？
    

    View Slide

31. アジェンダ
    ● sync.Mutexが実現する排他制御
    ● sync.Mutexの構造
    ● Lock()の内部実装
    ● 実装背景
    ● まとめ
    

    View Slide

32. Lock()の内部実装
    ● CompareAndSwapを利用して、stateのmutexLockedフラグを更新
    ● 更新できればその時点でロックされる
    src/sync/mutex.go
    

    View Slide

33. 📝 Compare And Swap
    ● Mutexをアクセス制御する
    リソースにつき1つ作成
    ● それを複数のgoroutineが
    参照する
    resource
    G
    Mutex
    ✅
    ❌
    ❌
    G
    G
    変数の値の更新が競合しないようにatomicな操作で更新
    https://pkg.go.dev/sync/atomic#pkg-overview
    

    View Slide

34. Lock()の内部実装
    ● stateの値を更新できなかった場合はlockSlowへ
    src/sync/mutex.go
    

    View Slide

35. lockSlow(): 全体像
    大まかに以下の3ステップに分かれている
    ● スピンループ
    ● stateの再更新
    ● semaを用いたロック取得
    

    View Slide

36. lockSlow(): スピンループ
    ● 直前のstateがロック状態だった場合にスピンループ
    src/sync/mutex.go
    

    View Slide

37. ● 「何もしない」という空振り処理を実行する
    📝 スピン
    resource
    G
    G
    Mutex
    ✅
    G
    可能な限りロック状態が解除されるのを待つ
    

    View Slide

38. lockSlow(): stateの再更新
    ● 再度stateをロック状態に更新しようと試みる
    src/sync/mutex.go
    

    View Slide

39. lockSlow(): stateの再更新
    ● ロック状態でも飢餓状態でもない場合はbreak
    ● 以降はロック状態に更新できても、直前の状態がロック状態の可能性
    => 別goroutineがロック中だが更新できた可能性
    src/sync/mutex.go
    

    View Slide

40. lockSlow(): stateの再更新
    ● stateのみでは1goroutineのみがロック中か保証できない
    src/sync/mutex.go
    

    View Slide

41. lockSlow(): semaを用いたロック取得
    ● runtime_SemacquireMutexへ
    ● semaを用いてruntimeレベルで1goroutineのみがロックした状態を
    確保しにいく
    src/sync/mutex.go
    

    View Slide

42. ここまでのまとめ
    ● Lock時はまずはじめにstateを用いて、ロック状態に更新できるか
    確認する
    ● stateをロック状態に更新できたとしても、1goroutineのみが
    アクセスしていることを保証できない
    ● stateを用いてもロック状態を保証できない場合は
    semaを用いてロック状態を確保しようと試みる
    

    View Slide

43. runtime_SemacquireMutex()
    ● //go:linkname によってruntime側のprivateメソッドをリンクさせる
    ● 実体はsync_runtime_SemacquireMutex => semacquire1
    src/sync/runtime.go
    src/runtime/sema.go
    

    View Slide

44. semacquire1()
    ● easy caseとharder caseの2パターンの処理が存在
    src/runtime/sema.go
    

    View Slide

45. semacquire1(): easy case
    ● sema(addr) をロック状態に更新しようと試みる
    src/runtime/sema.go
    src/runtime/sema.go
    

    View Slide

46. semacquire1(): harder case
    ● waiter countをインクリメント
    ● cansemacquireを複数回実行
    ● waiterとしてenqueue???
    ● sleep???
    runtimeレベルでgoroutineがどのように動作するか着目する必要あり
    src/runtime/sema.go
    

    View Slide

47. goroutine実行過程の概要
    X := 3
    pow(x)
    P
    G G
    M G
    G (goroutine): goroutine本体
    P (Prosessor): 論理プロセッサ
    M (Machine): OSスレッド
    Inspired by
    https://speakerdeck.com/sakiengineer/sukeziyurakaraxue-bugorantaimu-code-reading-of-runtime-pkg
    

    View Slide

48. goroutine実行過程の概要
    X := 3
    pow(x)
    P
    G G
    M G
    実行待ちのgoroutineを貯めるqueue
    実行中のgoroutine
    

    View Slide

49. goroutine実行過程の概要
    fmt.Println(“Hello”)
    P
    G G
    M G
    実行待ちのgoroutineがqueueから取り出され、逐次実行される
    

    View Slide

50. G
    semacquire1(): harder case
    sudog を用意
    P
    G G
    M G
    G
    src/runtime/sema.go
    

    View Slide

51. ● 待ち行列を表現するための構造体
    ● チャネルの内部実装にも使われる
    sudog
    G
    prev addr next addr
    src/runtime/runtime2.go
    

    View Slide

52. ● semtableからsemaのアドレスを元に、rootノードを取得
    semacquire1(): harder case
    src/runtime/sema.go
    

    View Slide

53. semtable
    Mutex
    Mutex
    G G G
    G G
    各Mutexをロックしようと待機している goroutineの待ち行列
    「各Mutexのsemaをロック状態に更新しようと待機する
    goroutineの待ち行列」の集合
    G
    Mutex
    Mutex
    G G
    G
    sematable (semaRootの配列)
    src/runtime/sema.go
    

    View Slide

54. semacquire1(): harder case
    P
    G G
    M G
    G
    Mutex
    Mutex
    G G
    G
    Mutexのsemaをロック状態に更新しよ
    うと待機するgoroutineの待ち行列の先
    頭ノードを取得！！
    G
    src/runtime/sema.go
    

    View Slide

55. semacquire1(): harder case
    ● semaをロック状態に更新しようと試みる
    src/runtime/sema.go
    

    View Slide

56. semacquire1(): harder case
    ● この段階でロック状態に更新できない場合は、
    現状ロックを取得できない状態と判断
    => ロック更新を一時停止し、goroutineをsleepさせるフェーズへ
    src/runtime/sema.go
    

    View Slide

57. semacquire1(): goroutineの一時停止
    P
    G G
    M G
    G
    G
    G
    Mutex
    現在実行中のgoroutineを待ち行列に追加
    src/runtime/sema.go
    

    View Slide

58. ● goparkunlockを呼び出して、
    現在のgoroutineを一時停止 & 別goroutineに実行を譲る
    semacquire1(): goroutineの一時停止
    src/runtime/sema.go
    

    View Slide

59. goparkunlockの挙動
    P
    G G
    M
    goroutineを一時停止状態にする
    G
    Sleeping…
    src/runtime/sema.go
    

    View Slide

60. goparkunlockの挙動
    P
    G G
    M G
    Sleeping…
    実行待ちのgoroutineを取り出して、起動させる
    G
    src/runtime/sema.go
    

    View Slide

61. Lockの内部実装 まとめ
    ● まずはじめにstateを用いて、ロック状態に更新できるか確認する
    ● stateを用いてもロック状態を保証できない場合は
    semaを用いてロック状態を確保しようと試みる
    ● semaによるロック取得も無理だった場合、次にスケジューリング
    されるまでgoroutineは一時停止する
    

    View Slide

62. Lockの内部実装 まとめ
    ● まずはじめにstateを用いて、ロック状態に更新できるか確認する
    ● stateを用いてもロック状態を保証できない場合は
    semaを用いてロック状態を確保しようと試みる
    ● semaによるロック取得も無理だった場合、次にスケジューリング
    されるまでgoroutineは一時停止する
    🤔 semaのみ使えばいいのでは？
    

    View Slide

63. ● sync.Mutexが実現する排他制御
    ● sync.Mutexの構造
    ● Lock()の内部実装
    ● 実装背景
    ● まとめ
    アジェンダ
    

    View Slide

64. なぜわざわざstateとsemaの2つの状態変数を使って
    2段階の処理を行っているの？
    実装背景
    

    View Slide

65. A. コンテキストスイッチを最小限に抑えて効率化するため
    実装背景
    

    View Slide

66. src/runtime/sema.go
    ● Semaphores in Plan 9.
    ● https://swtch.com/semaphore.pdf
    src/runtime/sema.go
    

    View Slide

67. Semaphores in Plan 9
    ● Plan 9におけるセマフォ機構の実装方針などが書かれている
    ○ Plan 9: かつてRuss Coxらが開発していた教育用OS
    

    View Slide

68. Semaphores in Plan 9
    ●
    ● u: ユーザ空間上のセマフォ
    ● k: カーネル空間上のセマフォ
    効率を高めるために、競合がない場合は完全にユーザー空間で実行でき、競合を処理するためにカー
    ネルにのみフォールバックするセマフォ実装があると便利です
    

    View Slide

69. Semaphores in Plan 9
    ● 基本的にユーザ空間上で処理を行う
    ● 競合が起きた時にだけカーネル空間上で処理を行う
    ユーザ空間 <-> カーネル空間のコンテキストスイッチを軽減する
    

    View Slide

70. Semaphores in Plan 9
    Goで考えると…
    ● 基本的にgoroutine空間上で処理を行う
    ● 競合が起きた時にだけruntime空間上で処理を行う
    goroutine空間 <-> runtime空間のコンテキストスイッチを軽減する
    

    View Slide

71. アジェンダ
    ● sync.Mutexが実現する排他制御
    ● sync.Mutexの構造
    ● Lock()の内部実装
    ● 実装背景
    ● まとめ
    

    View Slide

72. まとめ
    sync.Mutexは
    ● 「リソースへのアクセス状況」を管理する役割を持つ
    ● stateとsemaの2つの状態変数を用いて管理
    ● コンテキストスイッチを極力減らす工夫
    

    View Slide

73. ありがとうございましたʕ◔ϖ◔ʔ
    

    View Slide