Table of Contents

  1. Basic Structures
  2. The Beginning
  3. The Start of the Other Goroutines
  4. Change the Current Executing Goroutine
  5. A Slide

Notes On Go Scheduler

Posted on 01 Sep 2014, tagged golangscheduler

I read the Go source code about scheduler these days. They are under src/pkg/runtime, mainly in runtime.h, proc.c and some Assembly files. The scheduler’s policy is easy to understand, because there are already many articles on this. I’m more interesting in the details. I learned how to switch the current running goroutine, which is a little mystery for me before.

Basic Structures

Go scheduler mainly uses three structures:

  • G as a Goroutine.
  • M as an OS thread.
  • P as a context. Running under threads and control the goroutines.

The number of P is setted by GOMAXPROCS.

Each M has a G called g0 to do schedule jobs. (mcall will use g0 to execute functions).

The Beginning

As the comments in the source code, the bootstrap sequence is:

  • call osinit
  • call schedinit
  • make & queue new G
  • call runtime·mstart

Well, it is not very detailed. Let’s read the code. The bootstrap code is Assembly. You can find one example in asm_386.s:

 2        // set up m and g "registers"
 3        get_tls(BX)
 4        LEAL        runtime·g0(SB), CX
 5        MOVL        CX, g(BX)
 6        LEAL        runtime·m0(SB), AX
 8        // save m->g0 = g0
 9        MOVL        CX, m_g0(AX)
10        // save g0->m = m0
11        MOVL        AX, g_m(CX)
13        CALL        runtime·emptyfunc(SB)        // fault if stack check is wrong
15        // convention is D is always cleared
16        CLD
18        CALL        runtime·check(SB)
20        // saved argc, argv
21        MOVL        120(SP), AX
22        MOVL        AX, 0(SP)
23        MOVL        124(SP), AX
24        MOVL        AX, 4(SP)
25        CALL        runtime·args(SB)
26        CALL        runtime·osinit(SB)
27        CALL        runtime·hashinit(SB)
28        CALL        runtime·schedinit(SB)
30        // create a new goroutine to start program
31        PUSHL        $runtime·main·f(SB)        // entry
32        PUSHL        $0        // arg size
33        ARGSIZE(8)
34        CALL        runtime·newproc(SB)
35        ARGSIZE(-1)
36        POPL        AX
37        POPL        AX
39        // start this M
40        CALL        runtime·mstart(SB)
42        INT $3
43        RET

It init an M, and a G as this M’s g0.

runtime·schedinit init the global scheduler, read GOMAXPROCS and start the Ps.

runtime.main and runtime.newproc create and queue the main Goroutine.

runtime.mstart start this M at last.

runtime.mstart will call schedule, schedule will find a runnable G and call execute on it, execute will call runtime·gogo which is defined in the Assembly files, set the program pointer and stack to run a G. Now the program starts running and will never return. This main goroutine is locked to the main OS thread.

Here is what runtime.gogo do, for example in asm_386.s:

 1// void gogo(Gobuf*)
 2// restore state from Gobuf; longjmp
 3TEXT runtime·gogo(SB), NOSPLIT, $0-4
 4        MOVL        4(SP), BX                // gobuf
 5        MOVL        gobuf_g(BX), DX
 6        MOVL        0(DX), CX                // make sure g != nil
 7        get_tls(CX)
 8        MOVL        DX, g(CX)
 9        MOVL        gobuf_sp(BX), SP        // restore SP
10        MOVL        gobuf_ret(BX), AX
11        MOVL        gobuf_ctxt(BX), DX
12        MOVL        $0, gobuf_sp(BX)        // clear to help garbage collector
13        MOVL        $0, gobuf_ret(BX)
14        MOVL        $0, gobuf_ctxt(BX)
15        MOVL        gobuf_pc(BX), BX
16        JMP        BX

The Start of the Other Goroutines

When the program use the keyword go, it will start a new Goroutine. runtime·proc could start a G given the function. It put this new G in the current P’s run queue, then call wakep in order to call startm, which will get an idle P and run a G on it. If the P don’t have an M for now, it will call newm which will alloc an M using startm as its executing function. As we already known, startm will start this M, call scheduler to find a G to run.

How the P finds the executable G will be explained in the next section.

Change the Current Executing Goroutine

When to Change

We know when the G is executing, the code will never return. It means that the scheduler of Go is non-preemptive. So when to change the current running G?

When the current Goroutine call a system call, it is the chance. It will call handoffp, which will release the current P (and set it’s state to idle), start a new M to run the system call G, and then call startm, which will find an idle P and run it.

From Go 1.2, it increases the chance to run the scheduler. For example, when the goroutine call a function, it will check the memory and deside whether to do a scheduling.

This could be verified by a piece of code:

 1package main
 3import (
 4        "fmt"
 5        "sync"
 6        "time"
 9type Counter struct {
10        Count int
11        Mu    sync.Mutex
14func loop1() {
15        loop1()
18func loop2() {
19        for {
20        }
23func main() {
24        counter := Counter{Count: 0}
25        loop2()
27        for j := 0; j < 10; j++ {
28                go func() {
29                        // get uid
30                        counter.Mu.Lock()
31                        id := counter.Count
32                        counter.Count += 1
33                        counter.Mu.Unlock()
35                        /*
36                           It will print the current number of goroutine.
37                           It is a system call, so it will give other goroutines a chance to run,
38                           but it just happens in the beginning,
39                           so it will just allow a limited number of Goroutines to run.
40                        */
41                        fmt.Println(id)
43                        /*
44                          loop2() is a dead end loop. So it will block other Goroutines to run.
45                          loop1() keeps call functions, so it give other Goroutines a chance to run.
46                          You can see what will happen when change it to loop1()
47                        */
48                        loop2()
49                }()
50        }
51        fmt.Println("hi")
52        time.Sleep(time.Second * 1000)

Run it with the debug options:

1GODEBUG=schedtrace=1000,scheddetail=1 GOMAXPROCS=10 go run a.go

How to Change

We’ve know that the first Gorutine is run by the main program and never returns. So how to change the current Goroutine? The answer is it just change the current SP to the g0 by the Assembly code. The current Goroutine’s context is saved in order to be swapped back in the future. g0 will then call the scheduler to decide which Goroutine to run next.

Which One to Change

In the last section, we know that the new started G is just put under the P that calls the go keyword. So the queue don’t ensure fairness. However, while the P is able to run a new G but could not find any G in its queue, it will look up other Ps and steal half of their Gs if there are any. This is more effective that ensure the fairness while put G in the run queue since it need not lock all the scheduler to check all the Ps run queue to ensure the fairness.

The code could be found in findrunnable.

A Slide

A slide could be more suitable to show the point:

comments powered by Disqus