前回通常モードの動きを見ました。
今回はstarvingModeについていきます。
まずはいつstarvingModeになるかから見ていきましょう。
#いつStarvingModeになるか
前回canSpin条件を満たせず、runtime_SemacquireMutexでGが寝てしまったことを思い出しましょう。
今回はGが目覚めたところから話を始めていきます。
goparkunlock(&root.lock, waitReasonSemacquire, traceEvGoBlockSync, 4+skipframes)
if s.ticket != 0 || cansemacquire(addr) {
break
}
Gが目覚めると、sema.goの上記の部分に戻ります。
s.ticket!=0という条件は後で解説しますので今は飛ばします。starvingModeの時しか関係ない条件です。
ここで、cansemacquireできればbreakしてmutex.goまで戻ります。
他のsema.goにいるＧとのcansemaquireの取り合いですね。
取り合いに勝ち、mutex.goに戻ったとします。
if atomic.CompareAndSwapInt32(&m.state, old, new) {
if old&(mutexLocked|mutexStarving) == 0 {
break // locked the mutex with CAS
}
// If we were already waiting before, queue at the front of the queue.
queueLifo := waitStartTime != 0
if waitStartTime == 0 {
waitStartTime = runtime_nanotime()
}
runtime_SemacquireMutex(&m.sema, queueLifo, 1) <---ここに戻ってくる
starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
old = m.state
戻ってくると、戻ってきたGがtsarvingかそうでないかを判定します。
starvationThresholdNsが1msなので、それ以上眠っていればstarvingとなります。
starving=trueとなったのち、またforループを回り始めます。
if old&(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin(iter) {
old = m.state
continue
}
new := old
// Don't try to acquire starving mutex, new arriving goroutines must queue.
if old&mutexStarving == 0 { -☆
new |= mutexLocked
}
// The current goroutine switches mutex to starvation mode.
// But if the mutex is currently unlocked, don't do the switch.
// Unlock expects that starving mutex has waiters, which will not
// be true in this case.
if starving && old&mutexLocked != 0 { - ■
new |= mutexStarving
}
上記でmutexStarvingフラグをセットしているところがありますね。
どんなシチュエーションならセットされるのでしょうか。
眠りから目覚めて、starving=trueになっているGがここに来た時で、
old & mutexLocked != 0となるのはoldにlockフラグが立っているときです。
->old=??? mutexLocked= ...0000001で最下位ビットが０になるのはoldの最下位ビットが0の時だけ
spinから脱出する条件を思い出すと、まだmutexStarvingでない今の状態で、spinから脱出できるのはロック解除状態か、canSpin条件を満たせないときなので、眠りから覚めてstqarving=trueになっているときでもmutexLockedフラグが立っていて、ロック状態である可能性もあります。
なので、目覚めたのにまだロックされていて、ロック獲得できる目がないならmutexStarvingとします。
もしold&mutexLocked == 0で、ロックをとれる目があるならstarvingModeにはなりません。
では、☆の条件はなぜあるのでしょうか。
☆の条件は、mutexdStarvingでないなら新しいstateにmutexLockedフラグを立てて、ロック取得可能性を得られるということですが、
mutexStarvingになるときの条件がmutexLockedであることならば、StarvingのときにはずっとmutexLockedとなっているので新しくmutexLockedを立てる意味があるのか？となります。
ここだけ見たらそうなのですが、Unlockされた時のことを考えてみます。
Unlock時に、
new := atomic.AddInt32(&m.state, -mutexLocked)としていたことを思い出してみると、mutexLockedとmutexStarvingがセットでなくなります。
ロック解除時に、新しくきたGがstarvingModeであるなら、ロックを獲得できないようにするというのが☆の役割となっています。（後々この役割が重要になってきます。）
脱線しすぎたので、元に戻ってmutexStarvingフラグが立ったところから進みましょう。
if atomic.CompareAndSwapInt32(&m.state, old, new) {
if old&(mutexLocked|mutexStarving) == 0 {
break // locked the mutex with CAS
}
// If we were already waiting before, queue at the front of the queue.
queueLifo := waitStartTime != 0
if waitStartTime == 0 {
waitStartTime = runtime_nanotime()
}
runtime_SemacquireMutex(&m.sema, queueLifo, 1)
starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
old = m.state
省略....
ここでCASに成功すると晴れて？stateにmutexStarvingが加わります。
if old&(mutexLocked|mutexStarving) == 0では、確かにoldではmutexStarvingフラグは立っていませんが、■の条件を思い出すと、
mutexStarvingフラグが加わるときはoldがmutexLockedであることが条件なのでした。
なので、breakすることはできず、そのまま眠りにつきます。
二回目の眠りなのでwaitStartTimeがセットされています。なのでqueueLifoがtrueになり、コメントにもあるようにroot.queue(sudoGのTreap)の先頭に配置されます。
先頭に配置された奴がdequeueで出ていくので優先度が最高ということですね。
sema.goのqueue,dequeueにコードがあるのですが、本筋ではないので今回は省略します。
ここまででいつstarvingModeになるのかについて見ていきました。
次はstarvingModeでのUnlockについて見ていきましょう。一番工夫が凝らされているところです。
#Unlock
func (m *Mutex) Unlock() {
// 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)
}
}
func (m *Mutex) unlockSlow(new int32) {
if (new+mutexLocked)&mutexLocked == 0 {
throw("sync: unlock of unlocked mutex")
}
if new&mutexStarving == 0 {
...
runtime_Semrelease(&m.sema, false, 1)
} else {
// Starving mode: handoff mutex ownership to the next waiter, and yield
// our time slice so that the next waiter can start to run immediately.
// Note: mutexLocked is not set, the waiter will set it after wakeup.
// But mutex is still considered locked if mutexStarving is set,
// so new coming goroutines won't acquire it.
runtime_Semrelease(&m.sema, true, 1)
}
}
今回はstarvingModeなのでunlockSlowのelse条件に入っていきます。
通常モードとの違いは第二引数にtrueが入っていることですね。
func semrelease1(addr *uint32, handoff bool, skipframes int) {
root := semroot(addr)
atomic.Xadd(addr, 1)
// Easy case: no waiters?
// This check must happen after the xadd, to avoid a missed wakeup
// (see loop in semacquire).
if atomic.Load(&root.nwait) == 0 {
return
}
// Harder case: search for a waiter and wake it.
lockWithRank(&root.lock, lockRankRoot)
if atomic.Load(&root.nwait) == 0 {
// The count is already consumed by another goroutine,
// so no need to wake up another goroutine.
unlock(&root.lock)
return
}
s, t0 := root.dequeue(addr)
if s != nil {
atomic.Xadd(&root.nwait, -1)
}
unlock(&root.lock)
if s != nil { // May be slow or even yield, so unlock first
acquiretime := s.acquiretime
if acquiretime != 0 {
mutexevent(t0-acquiretime, 3+skipframes)
}
if s.ticket != 0 {
throw("corrupted semaphore ticket")
}
if handoff && cansemacquire(addr) { <- ここ
s.ticket = 1
}
readyWithTime(s, 5+skipframes)
if s.ticket == 1 && getg().m.locks == 0 {
// Direct G handoff
// readyWithTime has added the waiter G as runnext in the
// current P; we now call the scheduler so that we start running
// the waiter G immediately.
// Note that waiter inherits our time slice: this is desirable
// to avoid having a highly contended semaphore hog the P
// indefinitely. goyield is like Gosched, but it emits a
// "preempted" trace event instead and, more importantly, puts
// the current G on the local runq instead of the global one.
// We only do this in the starving regime (handoff=true), as in
// the non-starving case it is possible for a different waiter
// to acquire the semaphore while we are yielding/scheduling,
// and this would be wasteful. We wait instead to enter starving
// regime, and then we start to do direct handoffs of ticket and
// P.
// See issue 33747 for discussion.
goyield()
}
}
}
第二引数のhandoff=trueが入った状態では、s.ticketという部分が変わってきます。sはsudoGです。
Treapでは優先度の概念があり、queueに入った順のほかに優先度で取り出し方を変えています。
その優先度がs.ticketです。
Treapについての参考
https://medium.com/carpanese/a-visual-introduction-to-treap-data-structure-part-1-6196d6cc12ee
ただ、dequeueしてTreapから出すときはもう優先度は関係ないのでdequeueの際にs.ticket=0に戻します。
通常モードだとs.ticket=0となるのですが、handoff=true,starvingModeの時はs.ticket=1となります。(canacquireによってはstarvingModeでもならない場合がありますが、これは最後に説明します。今はstarvingModeならs.ticket=1とします。)
s.ticket=1となったら、次は通常モードのときにもやったreadyWithTimeです。これでPのrunqに入れてschedule待ち...では終わりません。
通常モードとは違いgoyieldを行い、今のunlockを起動しているGから先程root.queue->P.runqに移したGに実行を移します。
なのでshceduleとは違い、unlockからPのrunqに移したGに実行が移るようになっています。
これが途中変数であったhandoffの由来です。UnlockしたGからUnlockでdequeueを使って取り出したGに直接移っていきます。
さて、それではUnlockからhandoffされて目覚めたGについて見ていきましょう。
goparkunlock(&root.lock, waitReasonSemacquire, traceEvGoBlockSync, 4+skipframes)
if s.ticket != 0 || cansemacquire(addr) {
break
}
goparkunlockから戻ってきました。
ここでif s.ticket != 0 || cansemacquire(addr)という条件がありますね。
starvingModeの時は、s.ticket=1となっているので、こちらの条件でbreakし、mutex.goに戻ります。
なぜs.ticket != 0としているのか
通常モードの時は飛ばしていましたが、s.ticketについて分かったところでなぜこの条件なのかも解説します。
まずここの条件は眠りから目覚めた直後にチェックするところですが、その時s.ticketは通常モードなら0、starvingModeなら1となっています。
なので、通常モードはcansemacquireの条件、starvingModeはs.ticket=1なので条件なしでbreakすることができます。
cansemaquireは、unLockでaddrに+1されていて、0以上で他にsemaを取得しようとしている人がいなければaddr-=1としてtrueとなれるのでした。
func cansemacquire(addr *uint32) bool {
for {
v := atomic.Load(addr)
if v == 0 {
return false
}
if atomic.Cas(addr, v, v-1) {
return true
}
}
}
ただ、通常モードだけでなく、starvingModeでもcansemacquireは使用できるので、なぜs.ticketの条件をわざわざ追加したのでしょうか。
コードを読んでいるときに浮かんだ疑問点を一つ一つ解決していきながら、s.ticketの条件が追加された訳を見ていきます。
疑問
Unlock->semareleaseでatomic.Xadd(addr, 1)としている。addrはcansemacquire成功時に-1されるが、starvingModeの際、眠りから覚めるとs.ticket条件があるのでcansemacquireは行われない。これではaddrの値が無駄に増えてしまっているが大丈夫か。
回答
眠りから覚めた直後のcansemacquireの代わりに、semareleaseでcansemacquireをしてあげている(releaseなのにacquire...)
下記コードからわかる通りhandoff=trueの時限定なので、starvingModeの時のみ行われる
if handoff && cansemacquire(addr) {
s.ticket = 1
}
疑問
それでもやっぱりs.ticket条件を追加した意味が分からない、普通にcansemacquireを眠りから覚めたときでも使えば良さそう。
回答
starvingMode中で新規のGが入ってきた場合ロックは取得できないのでsemaまで来ることになる。
その際にやはりcansemaquireを使うことになるが、unlockとsema.goにいる新規Gとのsema.goからのsemaの取り合いになってくる。
下記に取り合いの部分を掲載する。
// Easy case.
if cansemacquire(addr) { <----☆
return
}
if handoff && cansemacquire(addr) { <---☆
s.ticket = 1
}
unlockされたGからhandoffされるG以外は脱出してほしくないので、cansemaquireがtrueとはなってほしくない、なので*addr=m.sema=0となっていてほしいはず
もちろんUnlockされるまではm.sema=0なので脱出不可で問題ない
ここからはUnLockされている最中のことを考えよう
UnLockの最中、handoffGが目覚めるまでにcansemaquireがtrueになってはまずそうなのでそこを確かめる
Unlockでm.sema+1をするが、別にsemaにロックがかかっているわけではないので、すぐにNewGがcansemaquireをできる。実はこれはこれで問題ない。
if handoff && cansemacquire(addr) {
s.ticket = 1
}
の条件の通り、release側でcansemaquireをする際にcansemaquireをしている、
もしcansemaquire(release側) < cansemaquire(newG)なのであれば、release側のcansemaquireを失敗するので、s.ticketは0のまま
なのでhandoffをそもそもしないということになる
cansemaquire(release側) > cansemaquire(newG)なのであればnewGでのcansemaquireは失敗し、目論見通りhandoffされるGが優先される
release側で自分でcansemaquireを取得したならば（release側でcansemaquireするのはstarvingModeでだけ）、acquire側では、cansemaquireが失敗することになる、
なので、s.ticket != 0 || cansemacquire(addr)の条件を入れている
この条件は通常時はcansemacquireを使って判定
starvingModeでは、release側でcansemaquireできたならば、すでにrelease側semaを取得していたので、もうm.sema=0となっていて、眠りから覚めた後のcansemacquireはできない。
なので、s.ticket!=0の条件を入れて、handoffGのみ脱出可能としている。
まとめると、
handoffをするときは、handoffG以外には脱出してほしくないので、m.sema=0となってほしい。
↓
なので、handoff時にsema+=1とした張本人のrelease側でsema-=1としてsemaを取得することでhandoff時に他のGが脱出できないようにしている(semaを取得できないならそもそもhandoffは行わない)
↓
release側でsemaを取得したので、眠りから覚めた後、acquire側でcansemacquireはできない、なのでs.ticket!=0条件を加えている
なぜgoyield()を使うか
Goには他にもGoSched()というGのコンテキストスイッチを促す関数があります。
こちらを使ってはなぜいけないのでしょうか。
GoSchedで使われているgoschedImpl内で、下記のようにglobalrunqに自身を入れています。
func goschedImpl(gp *g) {
status := readgstatus(gp)
if status&^_Gscan != _Grunning {
dumpgstatus(gp)
throw("bad g status")
}
casgstatus(gp, _Grunning, _Grunnable)
dropg()
lock(&sched.lock)
globrunqput(gp) <------ここ
unlock(&sched.lock)
schedule()
}
対して、goYield()はlocalRunqに自身を入れる（Not先頭）、readyWithTimeではlocalRunqの先頭に入れていたので、
localRunqではroot.queueから取り出したGが一番最初にPのlocalRunqから取り出されることになります。
func goyield_m(gp *g) {
if trace.enabled {
traceGoPreempt()
}
pp := gp.m.p.ptr()
casgstatus(gp, _Grunning, _Grunnable)
dropg()
runqput(pp, gp, false)
schedule()
}
どちらもscheduleを使う点は同じです。
if gp == nil {
// Check the global runnable queue once in a while to ensure fairness.
// Otherwise two goroutines can completely occupy the local runqueue
// by constantly respawning each other.
if _g_.m.p.ptr().schedtick%61 == 0 && sched.runqsize > 0 {
lock(&sched.lock)
gp = globrunqget(_g_.m.p.ptr(), 1)
unlock(&sched.lock)
}
}
if gp == nil {
gp, inheritTime = runqget(_g_.m.p.ptr())
// We can see gp != nil here even if the M is spinning,
// if checkTimers added a local goroutine via goready.
}
scheduleでは、次に使うGを取得する順番がglobalqueue->localqueueなので、
上手くstarvingModeの時に対象のGをlocalRunqから引っ張ってこれない可能性がありまう。(可能性があるだけで、グローバルからとらずにそのままローカルから取るかもしれない)
なので、次にscheduleされるやつがgoSched()を呼んだGになってしまう可能性が発生し、
下記のplayGroundでは普通Scheduleがうまくいって2,1と表示されるが、10回に一回くらい1のみが表示されてScheduleがGoSchedを呼んだG自身になってしまうことがあります。
https://play.golang.org/p/tSGmp7oF0aE
mutex.goに戻ってきました。
runtime_SemacquireMutex(&m.sema, queueLifo, 1) <---ここに戻ってくる
starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
old = m.state
if old&mutexStarving != 0 {
// If this goroutine was woken and mutex is in starvation mode,
// ownership was handed off to us but mutex is in somewhat
// inconsistent state: mutexLocked is not set and we are still
// accounted as waiter. Fix that.
if old&(mutexLocked|mutexWoken) != 0 || old>>mutexWaiterShift == 0 {
throw("sync: inconsistent mutex state")
}
delta := int32(mutexLocked - 1<<mutexWaiterShift)
if !starving || old>>mutexWaiterShift == 1 {
// Exit starvation mode.
// Critical to do it here and consider wait time.
// Starvation mode is so inefficient, that two goroutines
// can go lock-step infinitely once they switch mutex
// to starvation mode.
delta -= mutexStarving
}
atomic.AddInt32(&m.state, delta)
break
}
通常モードの時とは違い今回は old&mutexStarving != 0なのでその中も見ていきます。
なにをやっているかというとmutexStarvingを解除するかどうかの判定です。解除するしないに関わらずLockから脱出自体はできます。
ここは見た目にはわかりづらいビット演算ですが、計算してみましょう。
#StarvingModeが解除されるとき
if old&(mutexLocked|mutexWoken) != 0 || old>>mutexWaiterShift == 0 {
throw("sync: inconsistent mutex state")
}
まずこの条件ですが、mutexWoken関連は飛ばして、UnlockでmutexLockedは解除してあり、waiterが0人であるならそもそもunLockでsemaまで行って目覚めさせません。
なので例外のメッセージにある通り、stateの不一致ですね。
delta := int32(mutexLocked - 1<<mutexWaiterShift)
if !starving || old>>mutexWaiterShift == 1 {
// Exit starvation mode.
// Critical to do it here and consider wait time.
// Starvation mode is so inefficient, that two goroutines
// can go lock-step infinitely once they switch mutex
// to starvation mode.
delta -= mutexStarving
}
atomic.AddInt32(&m.state, delta)
break
ここでは条件次第でmutexStarvingが解除されていますね。
starvingかどうかは、
starving = starving || runtime_nanotime()-waitStartTime > 1ms
で決まります。
一番最初にやった、starving=trueとなり、mutexStarvingをセットするきっかけとなったGだとここは恒常的にstarving=trueとなりますが、
starvingModeに入ってから、semaroot.queueに入って目覚めたGはstarving=falseなので、後ろの条件を使い目覚めるのにどれくらいかかったか計算してtrueかどうか決めます。
もし最初からstarving=falseだったGが1ms未満しか眠っていないならstarving=falseとなり、starvingModeの原因であった待ち時間が長いことが改善されたと判定されるので、starvingModeを解除します。
old>>mutesxQaiterShift == 1の条件は今自分がsemaroot.queueから出てきて待ち人数があと一人、つまり自分しかもう待っている人はいないときです。(starvingModeの時は通常モードと違ってUnlockでwaiterの数を減らしていないので、ここで減らすことになります。)
この時もstarvingModeは解除されます。
では、ビット演算をして本当に上記でうまくいくのかやってみましょう。
delta := int32(mutexLocked - 1<<mutexWaiterShift)
if !starving || old>>mutexWaiterShift == 1 {
// Exit starvation mode.
// Critical to do it here and consider wait time.
// Starvation mode is so inefficient, that two goroutines
// can go lock-step infinitely once they switch mutex
// to starvation mode.
delta -= mutexStarving
}
atomic.AddInt32(&m.state, delta)
Starvingが続行して、waiterが２の時
m.state = old = 000...10/100となる、ラスト3bitがstarving,woken,locked,
3bitを除いた部分はwaiterの数、今回は２
delta := mutexLocked=1 - 1 << mutexWaiterShift=3 = 1 - 8 = -7
m.stateにdeltaを加える
000...10/100 = 20なので20-8=12 = 000...01/100でちゃんとwaiterが一つ減っている
starvingが続行でwaiterが一人の時
m.state = old = 000...01/100
if条件に合致するので、mutexStarvingを引く
delta = -7 - mutexStarving = 4 = -11
なので
000...01/100 = 12 - 11 = 1
000...00/001となるので、waiterの数が０，mutexStarving部分のビットも消えて、代わりにmutexLock部分のビットがついている
mutexStarvingフラグが消え、mutexLockedフラグが立つことでstarvingModeから脱出したということになる。
starvingがfalseでwaiterが2の時
m.state = old = 000...10/100=20
if条件に合致するので、mutexStarvingを引く
delta = -7 - mutexStarving = 4 = -11
20-11 = 9
000...01/001となり、待ち人数が一人、mutexLockedの状態に遷移します。
ぱっと見ただけではわからないけど、計算してみるとうまく出来ていることに感心してしまいます。(できれば見ただけでわかりやすくあってほしい、慣れればそうでもないのかも？)
#シチュエーションによる再考
ここまでstarvingModeの流れを見てきましたが、再度starvingModeで本当にUnlockから直接処理が渡されたGがsema.go->mutex.go->自分で書いたロックをかけた箇所と脱出できるか、いくつかシチュエーションを考えてみましょう。
starvingModeであることを前提とします。
複数のGがsemaroot.queueに入っているとき
UnLockでsemaroot.queueの先頭がPのrunqの先頭に入ります。
このときgoyieldでUnlockのGからrunqの先頭のGに処理が移ります。
semaroot.queueに眠っているGは眠りっぱなしでPのqueueに入るチャンスもなくsemaroot.queueの中での争いはunlockでdequeueされたGが勝つことになります。
なので他の眠っているGに邪魔されずにsema.go -> mutex.go -> 自分で書いたロックをかけた箇所と脱出できます。
新しくLockに入ってきたGと争う時
新しく入ってきたGは、LockSlow()の下記の条件でLockを取得できずにそのままsema.goに行ってしまいます。
ここからはcansemaquireの取り合いになり、もし新規Gがunlockがhandoffをする前(readyWithTimeとgoyield)に新規Gがsemaを獲得するならそもそもhandoffが行われず新規Gの勝ち、
handoffが行われたら、handoffされたGの勝ちとなります。
if old&mutexStarving == 0 { -☆
new |= mutexLocked
}
これでstarvingModeの挙動についても終了です。
次回は今まで放っておいたawokeについて見ていきたいと思います。