Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
sync.Mutexの仕組みを理解する
Search
Yoshiki Fujikane
June 02, 2023
Programming
2
1.7k
sync.Mutexの仕組みを理解する
Go Conference 2023
https://gocon.jp/2023/sessions/A14-S/
Yoshiki Fujikane
June 02, 2023
Tweet
Share
More Decks by Yoshiki Fujikane
See All by Yoshiki Fujikane
Our Journey from in-House CD System to Open Source
ffjlabo
0
100
KubeCon NA 2023 Recap for Balancing AI’s Productivity Boost with Ethical Considerations in Cloud Native
ffjlabo
0
100
GoにおけるCall Graphを用いた 大規模コードベースの影響調査
ffjlabo
0
4.5k
Other Decks in Programming
See All in Programming
これからの時代の新標準!SwiftTestingへの移行とトラブルシューティング
uetyo
0
440
僕が思い描くTypeScriptの未来を勝手に先取りする
yukukotani
3
580
dotfiles について話したい #湘なんか
stefafafan
2
280
Swiftで高速フーリエ変換してオーディオビジュアライザーを作る / iOSDC Japan 2024 Day1 Track D
kyome22
2
460
dRuby 入門者によるあなたの身近にあるdRuby 入門
makicamel
4
340
Regular Expressions, REXML, Automata Learning
makenowjust
0
180
フロントエンドカンファレンス北海道2024 『小規模サイトでも使えるVite 〜HTMLコーディングをよりスマートに〜』長谷川広武(ハム)
h2ham
1
2.5k
プログラマのための音楽入門
cheebow
4
540
Playwrightから始めるVisual Regression Testingのススメ by とっと
totto2727
2
1.8k
rbs-inlineを導入してYARDからRBSに移行する
euglena1215
1
200
ECMAScript、Web標準の型はどう管理されているか / How ECMAScript and Web standards types are maintained
petamoriken
3
370
Hono・Prisma・AWSでGeoなAPI開発
nokonoko1203
5
610
Featured
See All Featured
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
38
9.1k
The Straight Up "How To Draw Better" Workshop
denniskardys
230
130k
It's Worth the Effort
3n
182
27k
Making Projects Easy
brettharned
113
5.8k
How to name files
jennybc
75
97k
Large-scale JavaScript Application Architecture
addyosmani
508
110k
A better future with KSS
kneath
235
17k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
28
2.2k
Principles of Awesome APIs and How to Build Them.
keavy
125
16k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
662
120k
Fireside Chat
paigeccino
31
2.9k
StorybookのUI Testing Handbookを読んだ
zakiyama
25
5k
Transcript
sync.Mutexの仕組み を理解する Go Conference 2023/06/02
自己紹介 Name • Yoshiki Fujikane (ふじを) Company • CyberAgent, Inc.
22新卒入社 • ABEMA バックエンドエンジニア @ffjlabo @ffjlabo
• 排他制御を実現するプリミティブ • 共有リソースに対する競合を起こさず 並行処理を実装できる sync.Mutexとは
• 排他制御を実現するプリミティブ • 共有リソースに対する競合を起こさず 並行処理を実装できる sync.Mutexとは 🤔どうやって実現してるのだろう
sync.Mutex の仕組みが知りたい 背景
本発表の目的 • sync.Mutexの内部実装について把握する • sync.Mutexの仕組みを原理から理解する
ʕ◔ϖ◔ʔ> Let’s≡Go $ git checkout 7f1467ff4ddd882acb318c0ffe24fd3702ce75cc
• sync.Mutexが実現する排他制御 • sync.Mutexの構造 • Lock()の内部実装 • 実装背景 • まとめ
アジェンダ
• sync.Mutexが実現する排他制御 • sync.Mutexの構造 • Lock()の内部実装 • 実装背景 • まとめ
アジェンダ
「リソースへアクセスできるのは 1 goroutineのみ」 sync.Mutexが実現する排他制御
リソースへのアクセスが複数来ても、1goroutineのみアクセスを許可 sync.Mutexが実現する排他制御 resource G G G Mutex ✅ ❌ ❌
1goroutineのみにアクセスを制限するには? sync.Mutexが実現する排他制御
A. 「リソースへのアクセス状況」を記録しておく sync.Mutexが実現する排他制御
リソースへアクセスが来た段階でその状態を変数として記録しておく 「リソースへのアクセス状況」を記録 resource G Mutex Locked = false
リソースへアクセスが来た段階でその状態を変数として記録しておく 「リソースへのアクセス状況」を記録 resource G Mutex Locked = true ✅
別goroutineがアクセスしてきたとき、その変数を元に制御可能! 「リソースへのアクセス状況」を記録 resource G G G Mutex ✅ ❌ ❌
Locked = true
sync.Mutexが実現する排他制御: まとめ • sync.Mutexの排他制御とは 「リソースへのアクセスを1 gorutineのみに制限する」 こと • リソースへのアクセス状況を保持しておくことで実現
• sync.Mutexが実現する排他制御 • sync.Mutexの構造 • Lock()の内部実装 • 実装背景 • まとめ
アジェンダ
2つの状態変数を保持 • state ◦ Mutexの現在の状態を表す • sema ◦ goroutineの待機、解放を管理するためのセマフォ sync.Mutexの内部構造
src/sync/mutex.go
state Mutexのロック取得を待機している goroutine(waiter)の数 Mutexの状態 32bit 29bit 3bit src/sync/mutex.go
state: Mutexの状態 • Mutexの状態は3種類 • 各bitがそれぞれの状態に対応 S W L src/sync/mutex.go
state: Mutexの状態 • mutexLocked ◦ Mutexがロックされた状態 S W L src/sync/mutex.go
mutexLocked: イメージ 「ロックを獲得したgoroutineが存在する」状態 G G Mutex ✅ ❌
state: Mutexの状態 • mutexWoken ◦ 該当Mutexをロックしようとgoroutineが起動した状態 S W L src/sync/mutex.go
mutexWoken: イメージ 「ロックしようとするgoroutineが存在する」状態 G G Mutex
state: Mutexの状態 • mutexStarving ◦ 該当Mutexを長期間ロックできずにいるgoroutineが存在する状態 ◦ 飢餓状態(Starving mode)と呼ばれる S
W L src/sync/mutex.go
mutexStarving: イメージ 「一定時間以上ロックを待たされているgoroutineが存在する」状態 G G G Mutex ✅ ❌ G
もうずっと待ってるんだけどな …
• バイナリセマフォ ◦ sema == 0 => リソースが占有された状態 ◦ sema
== 1 => リソースが解放された状態 sema runtimeレベルのロック状況を管理するために利用される(詳細は後ほど) src/sync/mutex.go
sync.Mutexの構造: まとめ • sync.Mutexには2つの状態変数が存在 ◦ state: Mutexの様々な状況を表現 ◦ sema: バイナリセマフォでruntimeレベルのロック状況を表現
sync.Mutexの構造: まとめ • sync.Mutexには2つの状態変数が存在 ◦ state: Mutexの様々な状況を表現 ◦ sema: バイナリセマフォでruntimeレベルのロック状況を表現
🤔 なぜ2つも状態変数が存在する?
アジェンダ • sync.Mutexが実現する排他制御 • sync.Mutexの構造 • Lock()の内部実装 • 実装背景 •
まとめ
Lock()の内部実装 • CompareAndSwapを利用して、stateのmutexLockedフラグを更新 • 更新できればその時点でロックされる src/sync/mutex.go
📝 Compare And Swap • Mutexをアクセス制御する リソースにつき1つ作成 • それを複数のgoroutineが 参照する
resource G Mutex ✅ ❌ ❌ G G 変数の値の更新が競合しないようにatomicな操作で更新 https://pkg.go.dev/sync/atomic#pkg-overview
Lock()の内部実装 • stateの値を更新できなかった場合はlockSlowへ src/sync/mutex.go
lockSlow(): 全体像 大まかに以下の3ステップに分かれている • スピンループ • stateの再更新 • semaを用いたロック取得
lockSlow(): スピンループ • 直前のstateがロック状態だった場合にスピンループ src/sync/mutex.go
• 「何もしない」という空振り処理を実行する 📝 スピン resource G G Mutex ✅ G
可能な限りロック状態が解除されるのを待つ
lockSlow(): stateの再更新 • 再度stateをロック状態に更新しようと試みる src/sync/mutex.go
lockSlow(): stateの再更新 • ロック状態でも飢餓状態でもない場合はbreak • 以降はロック状態に更新できても、直前の状態がロック状態の可能性 => 別goroutineがロック中だが更新できた可能性 src/sync/mutex.go
lockSlow(): stateの再更新 • stateのみでは1goroutineのみがロック中か保証できない src/sync/mutex.go
lockSlow(): semaを用いたロック取得 • runtime_SemacquireMutexへ • semaを用いてruntimeレベルで1goroutineのみがロックした状態を 確保しにいく src/sync/mutex.go
ここまでのまとめ • Lock時はまずはじめにstateを用いて、ロック状態に更新できるか 確認する • stateをロック状態に更新できたとしても、1goroutineのみが アクセスしていることを保証できない • stateを用いてもロック状態を保証できない場合は semaを用いてロック状態を確保しようと試みる
runtime_SemacquireMutex() • //go:linkname によってruntime側のprivateメソッドをリンクさせる • 実体はsync_runtime_SemacquireMutex => semacquire1 src/sync/runtime.go src/runtime/sema.go
semacquire1() • easy caseとharder caseの2パターンの処理が存在 src/runtime/sema.go
semacquire1(): easy case • sema(addr) をロック状態に更新しようと試みる src/runtime/sema.go src/runtime/sema.go
semacquire1(): harder case • waiter countをインクリメント • cansemacquireを複数回実行 • waiterとしてenqueue???
• sleep??? runtimeレベルでgoroutineがどのように動作するか着目する必要あり src/runtime/sema.go
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
goroutine実行過程の概要 X := 3 pow(x) P G G M G
実行待ちのgoroutineを貯めるqueue 実行中のgoroutine
goroutine実行過程の概要 fmt.Println(“Hello”) P G G M G 実行待ちのgoroutineがqueueから取り出され、逐次実行される
G semacquire1(): harder case sudog を用意 P G G M
G G src/runtime/sema.go
• 待ち行列を表現するための構造体 • チャネルの内部実装にも使われる sudog G prev addr next addr
src/runtime/runtime2.go
• semtableからsemaのアドレスを元に、rootノードを取得 semacquire1(): harder case src/runtime/sema.go
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
semacquire1(): harder case P G G M G G Mutex
Mutex G G G Mutexのsemaをロック状態に更新しよ うと待機するgoroutineの待ち行列の先 頭ノードを取得!! G src/runtime/sema.go
semacquire1(): harder case • semaをロック状態に更新しようと試みる src/runtime/sema.go
semacquire1(): harder case • この段階でロック状態に更新できない場合は、 現状ロックを取得できない状態と判断 => ロック更新を一時停止し、goroutineをsleepさせるフェーズへ src/runtime/sema.go
semacquire1(): goroutineの一時停止 P G G M G G G G
Mutex 現在実行中のgoroutineを待ち行列に追加 src/runtime/sema.go
• goparkunlockを呼び出して、 現在のgoroutineを一時停止 & 別goroutineに実行を譲る semacquire1(): goroutineの一時停止 src/runtime/sema.go
goparkunlockの挙動 P G G M goroutineを一時停止状態にする G Sleeping… src/runtime/sema.go
goparkunlockの挙動 P G G M G Sleeping… 実行待ちのgoroutineを取り出して、起動させる G src/runtime/sema.go
Lockの内部実装 まとめ • まずはじめにstateを用いて、ロック状態に更新できるか確認する • stateを用いてもロック状態を保証できない場合は semaを用いてロック状態を確保しようと試みる • semaによるロック取得も無理だった場合、次にスケジューリング されるまでgoroutineは一時停止する
Lockの内部実装 まとめ • まずはじめにstateを用いて、ロック状態に更新できるか確認する • stateを用いてもロック状態を保証できない場合は semaを用いてロック状態を確保しようと試みる • semaによるロック取得も無理だった場合、次にスケジューリング されるまでgoroutineは一時停止する
🤔 semaのみ使えばいいのでは?
• sync.Mutexが実現する排他制御 • sync.Mutexの構造 • Lock()の内部実装 • 実装背景 • まとめ
アジェンダ
なぜわざわざstateとsemaの2つの状態変数を使って 2段階の処理を行っているの? 実装背景
A. コンテキストスイッチを最小限に抑えて効率化するため 実装背景
src/runtime/sema.go • Semaphores in Plan 9. • https://swtch.com/semaphore.pdf src/runtime/sema.go
Semaphores in Plan 9 • Plan 9におけるセマフォ機構の実装方針などが書かれている ◦ Plan 9:
かつてRuss Coxらが開発していた教育用OS
Semaphores in Plan 9 • • u: ユーザ空間上のセマフォ • k:
カーネル空間上のセマフォ 効率を高めるために、競合がない場合は完全にユーザー空間で実行でき、競合を処理するためにカー ネルにのみフォールバックするセマフォ実装があると便利です
Semaphores in Plan 9 • 基本的にユーザ空間上で処理を行う • 競合が起きた時にだけカーネル空間上で処理を行う ユーザ空間 <->
カーネル空間のコンテキストスイッチを軽減する
Semaphores in Plan 9 Goで考えると… • 基本的にgoroutine空間上で処理を行う • 競合が起きた時にだけruntime空間上で処理を行う goroutine空間
<-> runtime空間のコンテキストスイッチを軽減する
アジェンダ • sync.Mutexが実現する排他制御 • sync.Mutexの構造 • Lock()の内部実装 • 実装背景 •
まとめ
まとめ sync.Mutexは • 「リソースへのアクセス状況」を管理する役割を持つ • stateとsemaの2つの状態変数を用いて管理 • コンテキストスイッチを極力減らす工夫
ありがとうございましたʕ◔ϖ◔ʔ