0. Preface
existLecture 4 We introduced how the main goroutine works. The main goroutine describes how the scheduler function schedule works, but it does not describe the scheduling strategy of the scheduler as a whole, which is incomplete, and we will improve the scheduling strategy part of the scheduler in this talk.
1. Movement control points
implements the scheduler's scheduling policy. Then for scheduling time points, it is useful to see which function calls of the It is possible to sort out the scheduler's scheduling time points along the way, as shown below:
Scheduling timepoints are not the focus of this talk, and here interested students can follow the path of triggering scheduling timepoints, which will be skipped here.
2. Movement control strategy
The scheduling strategy is what we're focusing on, going into the：
// One round of scheduler: find a runnable goroutine and execute it.
// Never returns.
func schedule() {
mp := getg().m // Get the current thread of execution
top:
pp := () // Gets the execution thread bound to the P
= false
// Safety check: if we are spinning, the run queue should be empty.
// Check this before calling checkTimers, as that might call
// goready to put a ready goroutine on the local run queue.
if && ( != 0 || != ) {
throw("schedule: spinning with local work")
}
gp, inheritTime, tryWakeP := findRunnable() // blocks until work is available
...
execute(gp, inheritTime) // Execute the found goroutine
}
The focus is onfindRunnable()。findRunnable() The function is very long, in order to avoid affecting the readability, most of the process is commented here, and will be introduced later in a focused manner. EnterfindRunnable()：
// Finds a runnable goroutine to execute.
// Tries to steal from other P's, get g from local or global queue, poll network.
// tryWakeP indicates that the returned goroutine is not normal (GC worker, trace // reader) so the caller should try to wake a P's goroutine.
// reader) so the caller should try to wake a P.
func findRunnable() (gp *g, inheritTime, tryWakeP bool) {
mp := getg().m // Get the current thread of execution.
top.
pp := () // Get the thread-bound P
...
// 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.
// by constantly respawning each other.
If %61 == 0 && > 0 {
lock(&)
gp := globrunqget(pp, 1)
unlock(&)
if gp ! = nil {
return gp, false, false
}
}
// local runq
if gp, inheritTime := runqget(pp); gp ! = nil { // Get the goroutine from P's local queue.
return gp, inheritTime, false
}
// global runq
if ! = 0 { // If the local queue is not available, determine if there is a goroutine in the global queue.
lock(&) // if there is one, lock the global variable
gp := globrunqget(pp, 0) // get the goroutine from the global queue
unlock(&) // unlock the global variable
if gp ! = nil {
return gp, false, false
}
}
// If there is no goroutine in the global queue, fetch the goroutine from the network poller
if netpollinited() && () > 0 && () ! = 0 {
...
}
// If the network poller doesn't have a goroutine either, then try to steal one from another P.
// Spinning Ms: steal work from other Ps.
//... }
// Limit the number of spinning Ms to half the number of busy Ps. // This is necessary to prevent excessive CPU consumption when the network poller has no goroutine.
// This is necessary to prevent excessive CPU consumption when
// GOMAXPROCS>>1 but the program parallelism is low.
// If at least one of the following two conditions is met, the goroutine stealing logic proceeds
// Condition 1: The current thread is spinning.
// Condition 2: the currently active P is much larger than the spinning thread, indicating that threads are needed to share the pressure of the active threads, so don't go to sleep!
if || 2*() < () {
if ! { // Since it's one of two conditions, first determine if the current thread is spinning or not.
() // If not, update the thread's state to spin.
}
gp, inheritTime, tnow, w, newWork := stealWork(now) // steal goroutine
if gp ! = nil {
// Successfully stole.
return gp, inheritTime, false // If gp is not equal to nil, then it was stolen, return the stolen goroutine.
}
if newWork {
// There may be new timer or GC work; restart to
// discover.
goto top // If gp is not equal to nil and network is true, jump to the top tab and rediscover the goroutine.
}
now = tnow
if w ! = 0 && (pollUntil == 0 || w < pollUntil) {
// Earlier timer to wait for.
pollUntil = w
}
}
...
If ! = 0 { // You didn't even steal it, so you have to search the global queue again to prevent it from getting a goroutine in the process.
gp := globrunqget(pp, 0)
unlock(&)
return gp, false, false
unlock(&) return gp, false, false
unlock(&) return gp, false, false } if ! & & () == 1 { // judge it again, if mp is not spin and == 1 then update mp to spin, call top to find the goroutine again.
// See "Delicate dance" comment below.
()
unlock(&)
goto top
}
// If we can't find a goroutine, we're ready to hang the thread because there are too many threads and too few goroutines.
// First, call releasep to unbind the thread from P. If releasep() !
if releasep() ! = pp {
throw("findrunnable: wrong p")
}
...
now = pidleput(pp, now) // put the unbound p into the global free queue
unlock(&)
wasSpinning := // by this point == true, thread is in spinning state
if {
= false // set = false, it's getting ready to hibernate
if (-1) < 0 { // reduce global variable spinning threads by 1, since the current thread is ready to hibernate and not steal the goroutine anymore
throw("findrunnable: negative nmspinning")
}
...
}
stopm() // hibernate the thread until it wakes up.
goto top // If we got this far, the thread has been woken up, so let's keep looking for the goroutine.
}
After reading the scheduling strategy of the thread I have to be touched, how dedicated, exhausting all ways to find work to do, can not find work, hibernation before you have to look for once again, it is really a model of labor ah.
The general process is relatively clear, we put some of the parts worth digging deeper in the single out.
First, look for the goroutine in the local queue, and if you can't find it, then go to the global queue and look for it.gp := globrunqget(pp, 0) It may seem confusing to take the goroutine from the global queue, so why pass in P. Let's see what this function is doing:
// Try get a batch of G's from the global runnable queue.
// Must be held. // The annotation is pretty clear, put the goroutine from the global queue into P's local queue.
func globrunqget(pp *p, max int32) *g {
assertLockHeld(&)
if == 0 {
if == 0 { return nil
}
n := /gomaxprocs + 1 // The global queue is thread-shared, except for gomaxprocs, which is split evenly between each thread-bound P
if n > {
n = // Execute here, stating that gomaxprocs == 1
}
if max > 0 && n > max {
n = max
}
if n > int32(len())/2 {
n = int32(len()) / 2 // if n is longer than half the length of the local queue, n == len()/2
}
-= n // Global queue length minus n, ready to take n goroutines from global queue to P
gp := () // take the goroutine at the head of the global queue, this goroutine is the goroutine to be returned
n-- // take a goroutine from the head of the queue, subtract 1 from n here.
for ; n > 0; n-- {
gp1 := () // Loop over the goroutines in the global queue.
runqput(pp, gp1, false) // put the goroutine into the global queue.
}
return gp
}
call (programming)globrunqget It means that there is no goroutine in the local queue to be taken from the global queue, then the goroutine in the global queue can be put into P, which improves the priority of the goroutine in the global queue.
If the goroutine is not found in the global queue either, the goroutine is not found in the queue from thenetwork poller Find, ifnetwork poller If you don't find one, you're ready to go into spin and steal work from P in another thread. Let's see how the thread steals the job:
// stealWork attempts to steal a runnable goroutine or timer from any P.
//
// If newWork is true, new work may have been readied.
//
// If now is not 0 it is the current time. stealWork returns the passed time or
// the current time if now was passed as 0.
func stealWork(now int64) (gp *g, inheritTime bool, rnow, pollUntil int64, newWork bool) {
pp := getg().() // pp is bound to the current thread P
ranTimer := false
const stealTries = 4 // Thread stolen four times，Randomly loop through all of them one at a time P
for i := 0; i < stealTries; i++ {
stealTimersOrRunNextG := i == stealTries-1
for enum := (fastrand()); !(); () { // To ensure the randomness of the theft，Randomly start stealing P。Random start，each of the following P All can have their turn.
...
p2 := allp[()] // through (a gap) allp Getting P
if pp == p2 {
continue // 如果获取的is bound to the current thread P，then the loop continues with the next P
}
...
// Don't bother to attempt to steal if p2 is idle.
if !(()) { // I'm sure you've got it. P yes or no idle state of affairs，If it is，make known P Not yet. goroutine，Skip it.，lit. steal the next family (idiom); to steal from the rich and powerful
if gp := runqsteal(pp, p2, stealTimersOrRunNextG); gp != nil { // P fault idle，call (programming) runqsteal steal it！
return gp, false, now, pollUntil, ranTimer
}
}
}
}
// No goroutines found to steal. Regardless, running a timer may have
// made some goroutine ready that we missed. Indicate the next timer to
// wait for.
return nil, false, now, pollUntil, ranTimer
}
The thread randomly steals a stealable P. Stealing P is implemented in therunqstealViewrunqsteal How to steal:
// Steal half of elements from local runnable queue of p2
// and put onto local runnable queue of p.
// Returns one of the stolen elements (or nil if failed). // Steal half of the goroutine from a starving baby, ah, that's tough!
func runqsteal(pp, p2 *p, stealRunNextG bool) *g {
t := // t points to the end of P's local queue.
n := runqgrab(p2, &, t, stealRunNextG) // runqgrab takes the goroutine half of P2's local queue and puts it into P's runq queue.
if n == 0 {
if n == 0 { return nil
}
n-- gp := [(t+(gp))
gp := [(t+n)%uint32(len())].ptr() // take the stolen goroutine from the end of the local queue
if n == 0 {
return gp // If this is the only goroutine stolen, return it. Something is better than nothing.
}
h := (&) // load-acquire, synchronize with consumers
if t-h+n >= uint32(len()) {
throw("runqsteal: runq overflow") // if t-h+n >= len() means steal more...
}
(&, t+n) // Update the end of P's local queue.
return gp
}
This stealing is to take half of the remaining grain (goroutine) from the "landlord's house" (P2), I have no choice but to eat too.
If you don't even get to steal it (okay, that's too bad...) then it's ready to hibernate and stop working. Before you do that, check the global queue to see if there is a goroutine (M people who are not what they think they are). It's still not working, so I'm going to hibernate it.
To prepare for hibernation, first unbind to P:
func releasep() *p {
gp := getg()
if == 0 {
throw("releasep: invalid arg")
}
pp := ()
if () != || != _Prunning {
print("releasep: m=", , " m->p=", (), " p->m=", hex(), " p->status=", , "\n")
throw("releasep: invalid p state")
}
...
= 0
= 0
= _Pidle
return pp
}
It's the pointer unbinding operation, and the code is so clear that we don't even need to comment it, so we won't talk about it.
After unbundling.pidleput Put the idle P into the global idle queue.
Next, update the state of the thread from spin to non-spin by calling thestopm Prepare to hibernate:
// Stops execution of the current m until new work is available.
// Returns with acquired P.
func stopm() {
gp := getg() // The current thread executes the goroutine
...
lock(&)
mput() // Putting threads in the global idle thread queue
unlock(&)
mPark()
acquirep(())
= 0
}
stopm puts the thread into the global idle thread queue, followed by a call to themPark Dormant threads:
// mPark causes a thread to park itself, returning once woken.
//
//go:nosplit
func mPark() {
gp := getg()
notesleep(&) // notesleep the thread to sleep.
noteclear(&)
}
func notesleep(n *note) {
gp := getg()
if gp ! = .g0 {
throw("notesleep not on g0")
}
ns := int64(-1)
if *cgo_yield ! = nil {
// Sleep for an arbitrary-but-moderate interval to poll libc interceptors.
ns = 10e6
}
for (key32(&)) == 0 { // Determine if the thread is awake by checking if it's awake, if it's equal to 0, it's not awake, and the thread continues to sleep. if *cgo_yield !
= true
futexsleep(key32(&), 0, ns) // Call futex to hibernate the thread, which will "block" until it is woken up.
if *cgo_yield ! = nil {
asmcgocall(*cgo_yield, nil)
}
= false // "Wake up", set the thread's blocked flag to false.
}
}
// One-time notifications.
func noteclear(n *note) {
= 0 // noteclear means that the thread has been woken up, and the thread reset flag is 0.
}
Thread hibernation is accomplished by callingfutex into the operating system kernel to complete the thread hibernation, about thefutex The content of this article can be found inhere are。
is the hibernation flag bit, when it is not equal to 0, it indicates that a thread is waking up the hibernated thread, and the thread will return to normal state from hibernation. Waking up a hibernating thread is accomplished by calling thenotewakeup(&) function implementation:
func notewakeup(n *note) {
old := (key32(&), 1)
if old ! = 0 {
print("notewakeup - double wakeup (", old, ")\n"))
throw("notewakeup - double wakeup")
}
futexwakeup(key32(&), 1) // call futexwakeup to wake up the dormant thread
}
First, how does a thread find a dormant thread? The thread finds the idle thread through the global idle thread queue and passes the idle thread's hibernation flag bit to thenotewakeupThe last call tofutexwakeup Wake up the dormant thread.
It's worth noting that the waking thread will continue to look for a runnable goroutine even after it wakes up until it finds one:
func stopm() {
...
mPark() // If mPark returns, the thread is woken up and starts working normally.
acquirep(()) // The thread was already unbound to P before it went to sleep. We'll find a P binding for the thread here.
= 0 // Thread is already bound to P, reset nextp.
}
This is basically a very important part of the scheduling strategy, how the thread finds the goroutine, and when it does it calls thegogo Execute the goroutine.
3. Summary
This talk continues to enrich the scheduler's scheduling strategy, and in the next talk, we begin the introduction of the non-main goroutine.