# go调度

\[TOC]

## 调度器由来

### CPU成本

操作系统经过不断改善，在`多进程/多线程`的操作系统中，如果`进程/线程`的任务阻塞，CPU会切换到其他其他`进程/线程`中去执行。

并且调度算法可以保证在运行的进程都可以被分配到CPU的运行时间片，从宏观来看，似乎多个进程实在同时被运行。但是`进程`的创建、切换、销毁都会占用很长的时间（意味着占用的CPU资源多），所以CPU资源虽然利用起来了，但是如果进程过多，CPU有很大部分都被用来进行调度了。

在Linux系统中，CPU对`进程`和`线程`的态度是一样的。

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2Fdfce23a9d0ce1bd3f1138763d58e354332d3ddd4.png!large?generation=1626533892224791\&alt=media)

### 内存成本

在32位的操作系统中创建`进程`大概消耗4GB虚拟内存，创建线程大概需要4MB。

在高并发场景下，每个任务如果都创建一个线程来处理，那么内存成本也是相当昂贵。

### 用户态线程

对于操作系统的`线程`使用起来有昂贵的`CPU成本`和`内存成本`，因此产生了`用户态线程`。

一个`用户态线程`必须要绑定一个`内核态线程`，但是CPU并不知道`用户态线程`的存在，它只知道它运行的是`内核态线程`（Linux的PCB进程控制块）

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2F466e8efc9ef8c4351fc415c93ec64db11074ee73.png!large?generation=1626533892099875\&alt=media)

用户态线程也叫协程，内核态线程也叫线程。

**goroutine（go协程）**，go的用户态线程，创建一个goroutine只需约2KB，远比线程、进程开销小，这样就能在有限的内存空间内支持大量的goroutine。

详见[\[典藏版\] Golang 调度器 GMP 原理与调度全分析](https://learnku.com/articles/41728) “Golang 调度器的由来”部分

### 协程与线程的映射关系

#### N:1关系，N个协程绑定在1个线程

**优点**：协程在用户态线程即完成切换，不会陷入到内核态，切换上下文开销小。

**缺点**：某个程序用不了多核加速能力；一旦某个协程阻塞，本进程线程所绑定的其他协程都无法执行了。

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2F8c9def85119dba6b4250838ec01a69971bedfe23.png!large?generation=1626533892119981\&alt=media)

#### M:N关系，M个协程绑定N个线程

避免了“一旦某个协程阻塞，本进程线程所绑定的其他协程都无法执行”的情况产生。

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2F1b844b00c66410b1b4b0027cb4ebfb810151bca9.png!large?generation=1626533892106072\&alt=media)

但是在`go1.13`版本以及之前`协程`由用户态调度是协作式的，一个协程让出CPU后其所绑定的的线程才会执行下一个协程。这样看来如果在M>N时，有N个协程正在执行并且都阻塞了，那么N个线程就无法处理下一个协程了？

## Go调度器模型

### GM模型

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2Fd1b035bd9232d6ef87b53241088b228fd1584286.png!large?generation=1626601170967183\&alt=media)

#### 激烈的锁竞争

该模型通过一个全局队列来维护go协程，多个M操作G都需要访问全局队列，因此需要加锁来进行保护，这样无论是创建、销毁还是调度G的M都需要获取锁，就形成了激烈的锁竞争。

#### 传递造成延迟和额外的开销

当G1中存在创建协程动作时，假设创建了G2，那么G2会被存放在全局队列而不是本地，并且有可能被其他M所持有从而造成延迟和额外的开销。

#### 浪费内存缓存

每个 `M`持有 `mcache` 和`stack alloc`，然而只有在`M`运行`Go代码`时才需要使用的内存(每个`mcache`可以高达`2mb`)，当`M`在处于`syscall`时并不需要。当前在M运行后对M的内存进行了预热，因为现在G调度到同一个 M 的概率并不高就降低了缓存命中率，从而造成内存上的浪费。

### GMP模型

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2Fa244a2d0aad1998b3938f36abb214eb77eac970a.png?generation=1626601170777170\&alt=media)

GMP模型和GM模型相比，新增了`P（process）`，在`P`中维护着一个本地队列可以用来存储`G`且上限为256个。如果本地的G所创建G‘则优先加入到runnext，如果runnext之前绑定了 G ，则将之前的G放到本地队列（[Go：并发以及调度器亲和](https://zhuanlan.zhihu.com/p/387011586)），如果本地队列容量不够了，则会把本地队列中一半（队列前半部分）的 G 和当前创建的 G' 移动到全局队列。

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2Fee9d195117194bb5427061bb5b955fa6d8dbe8b6.png?generation=1627131656570274\&alt=media)

所有的P在程序启动的时候创建并保存在一个数组中，最多有`GOMAXPROCS`个，`GOMAXPROCS`可以通过设置环境变量`$GOMAXPROCS`或由`runtime`的`GOMAXPROCS()`函数决定。

对于`M`来说，要想运行任务就需要获得`P`，如果本地队列没有`G`则需要进行窃取，窃取策略见`work stealing 机制` 部分。由于如M被阻塞导致许多就绪任务分配不了给空闲的M，那么就会去创建新的`M`。

## 调度策略与机制

### 调度策略

* `复用线程`：避免频繁地创建、销毁线程。
* 利用并行：`GOMAXPROCS`设置P的数量，最多有`GOMAXPROCECS`个协程分布在多个CPU上同时运行。
* 抢占：一个goroutine每次调度最多占用CPU`10ms`，避免其他goroutine饥饿。
* 全局队列：当M执行`work stealing`从其他P偷不到G时，它可以去全局队列中获取。

### work stealing 机制

当本地队列的G都被执行完了，就会尝试从其他的P中窃取一半数量的G，如果多次窃取都失败，那么就去全局队列中获取`min(total/GOMAXPROCS+1, 128)`个G。

```
[Scalable Go Scheduler Design Doc](https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y_kqxDv3I3XMw/) Scheduling中写道：
When a new G is created or an existing G becomes runnable, it is pushed onto a list of runnable goroutines of current P. When P finishes executing G, it first tries to pop a G from own list of runnable goroutines; if the list is empty, P chooses a random victim (another P) and tries to steal a half of runnable goroutines from it.
```

从实现的大致逻辑看：

**在本地队列为空时会有1/61的机会先去全局队列中获取G**

```go
// https://github.com/golang/go/blob/master/src/runtime/proc.go#L3355
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)
		}
}
```

![runtime schedule](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-8dadb3ff3c42a7adf899921e7c9872aa6e116836%2Fimage-20210718201026109-6610229.png?alt=media)

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2F53d3eefbda4e700d7e3befb4c08505b553484e0d.png?generation=1626601171491161\&alt=media)

### hand off 机制

当本线程因为G进行如`系统调用`等造成阻塞时，线程会释放其所绑定的`P`，让`P`可以转移到其他空闲的线程执行。

![G1发生阻塞](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2Fe09ae8ab84fbec2bc7d365d40e07b821fd3f022e.png?generation=1626613563244945\&alt=media)

![唤醒一个空闲的的M或者创建一个M](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2Fdf72496c2c01a3d5215402e6a237c8d0b9d69ced.png?generation=1626613562200604\&alt=media)

![将P绑定到新的M上](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2F479037dd48e46c33c79019f335eaa21c501f5881.png?generation=1626613561203463\&alt=media)

等待阻塞操作（比如阻塞的系统调用 syscall）完成后：

1. 尝试获取G1原来所绑定的P，恢复G1的执行。
2. 尝试从睡眠列表中获取其他空闲 P，恢复执行G1的执行。
3. G1则会被放入全局队列等待下次被调度，M1就会睡眠队列或者被销毁。

## 调度流程

### 生产者

当使用 `go` 关键字，如执行 `go fun(){ do something }` 时，会向 runtime 提交一个计算任务，do something 就是任务内容。

go 维护了`本地队列`和`全局队列`两种队列，本地队列是一个容量为256的数组，全局队列则是一个链表。

依据 局部性原理，最新提交的 `goroutine` 会更优先执行，他会放入 `runnext` 中，意味着在下次被调度到时马上执行，而原来 runnext 中的 goroutine 则会尝试放入本地队列，如果本地队列满了则将本地队列前面一半的goroutine拿出同原来在 runnext 中的goroutine一起放入全局队列。

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-b2c41a3cda5514f3bd58794bd8232c63964c6906%2Fimage-20221130194221222.png?alt=media)

```go
// https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L4250
func newproc(siz int32, fn *funcval) {
	argp := add(unsafe.Pointer(&fn), sys.PtrSize)
	gp := getg()
	pc := getcallerpc()
	systemstack(func() {
		newg := newproc1(fn, argp, siz, gp, pc)

		_p_ := getg().m.p.ptr()
		runqput(_p_, newg, true)

		if mainStarted {
			wakep()
		}
	})
}
```

1.  使用 go 关键字创建一个协程，会向 runtime 提交一个计算任务，通过 runqput 入队

    ```go
    //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L5953
    // runqput tries to put g on the local runnable queue.
    // If next is false, runqput adds g to the tail of the runnable queue.
    // If next is true, runqput puts g in the _p_.runnext slot.
    // If the run queue is full, runnext puts g on the global queue.
    // Executed only by the owner P.
    func runqput(_p_ *p, gp *g, next bool) {
    	if randomizeScheduler && next && fastrand()%2 == 0 {
    		next = false
    	}

    	if next {
    	retryNext:
    		oldnext := _p_.runnext
    		if !_p_.runnext.cas(oldnext, guintptr(unsafe.Pointer(gp))) {
    			goto retryNext
    		}
    		if oldnext == 0 {
    			return
    		}
    		// Kick the old runnext out to the regular run queue.
    		gp = oldnext.ptr()
    	}

    retry:
    	h := atomic.LoadAcq(&_p_.runqhead) // load-acquire, synchronize with consumers
    	t := _p_.runqtail
    	if t-h < uint32(len(_p_.runq)) {
    		_p_.runq[t%uint32(len(_p_.runq))].set(gp)
    		atomic.StoreRel(&_p_.runqtail, t+1) // store-release, makes the item available for consumption
    		return
    	}
    	if runqputslow(_p_, gp, h, t) {
    		return
    	}
    	// the queue is not full, now the put above must succeed
    	goto retry
    }
    ```
2.  新创建的 G 绑定到 runnext

    ```go
    retryNext:
    		oldnext := _p_.runnext
    		if !_p_.runnext.cas(oldnext, guintptr(unsafe.Pointer(gp))) {
    			goto retryNext
    		}
    ```
3.  如果之前 runnext 有绑定 G，则将现试着放入本地队列中

    ```go
    	if t-h < uint32(len(_p_.runq)) {
    		_p_.runq[t%uint32(len(_p_.runq))].set(gp)
    		atomic.StoreRel(&_p_.runqtail, t+1) // store-release, makes the item available for consumption
    		return
    	}
    ```
4.  如果本地队列满了，则将本地队列前半部分（128个）的 G 和 之前绑定在 runnext 上的 G 一起放到全局队列

    ```go
    //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L5988
    // Put g and a batch of work from local runnable queue on global queue.
    // Executed only by the owner P.
    func runqputslow(_p_ *p, gp *g, h, t uint32) bool {
    	var batch [len(_p_.runq)/2 + 1]*g

    	// First, grab a batch from local queue.
    	n := t - h
    	n = n / 2
    	if n != uint32(len(_p_.runq)/2) {
    		throw("runqputslow: queue is not full")
    	}
    	for i := uint32(0); i < n; i++ {
    		batch[i] = _p_.runq[(h+i)%uint32(len(_p_.runq))].ptr()
    	}
    	if !atomic.CasRel(&_p_.runqhead, h, h+n) { // cas-release, commits consume
    		return false
    	}
    	batch[n] = gp

    	if randomizeScheduler {
    		for i := uint32(1); i <= n; i++ {
    			j := fastrandn(i + 1)
    			batch[i], batch[j] = batch[j], batch[i]
    		}
    	}

    	// Link the goroutines.
    	for i := uint32(0); i < n; i++ {
    		batch[i].schedlink.set(batch[i+1])
    	}
    	var q gQueue
    	q.head.set(batch[0])
    	q.tail.set(batch[n])

    	// Now put the batch on global queue.
    	lock(&sched.lock)
    	globrunqputbatch(&q, int32(n+1))
    	unlock(&sched.lock)
    	return true
    } 
    ```

### 消费者

是一个死循环， `schedule` -> `execute` -> `gogo` -> `goexit` ... -> `schedule`

schedule 是核心，负责获取要执行的goroutine。

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-3e87fbc3c8146ee37de1c26e08cd20f83e93d6f5%2Fimage-20221123232833861.png?alt=media)

图中红色部分为 GC 相关逻辑

1.  `globalrunqget/61`会检查是否是每第 61 次（意味着 schedtick % 61 == 0）获取 groutine，如果是则本次从全局队列中获取一个 g

    ```go
    //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L3355
    // 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) // 指定 max=1
      unlock(&sched.lock)
    }
    ```
2.  不是第 61 的倍数次获取，或者是每第 61 次获取但是全局队列为空，则执行 `runqget` 从本地获取，依次从 runnext、本地队列中获取（队首的 g ）

    ```go
    //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L6065
    // Get g from local runnable queue.
    // If inheritTime is true, gp should inherit the remaining time in the
    // current time slice. Otherwise, it should start a new time slice.
    // Executed only by the owner P.
    func runqget(_p_ *p) (gp *g, inheritTime bool) {
    	// If there's a runnext, it's the next G to run.
    	for {
    		next := _p_.runnext
    		if next == 0 {
    			break
    		}
    		if _p_.runnext.cas(next, 0) {
    			return next.ptr(), true
    		}
    	}

    	for {
    		h := atomic.LoadAcq(&_p_.runqhead) // load-acquire, synchronize with other consumers
    		t := _p_.runqtail
    		if t == h {
    			return nil, false
    		}
    		gp := _p_.runq[h%uint32(len(_p_.runq))].ptr()
    		if atomic.CasRel(&_p_.runqhead, h, h+1) { // cas-release, commits consume
    			return gp, false
    		}
    	}
    }
    ```
3.  如果没有获取到就进入到 `findrunnable`，分为 `top` （图中绿色）和 `stop`（图中蓝色） 两部分

    代码：https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L2705

    * top阶段：
      1.  再试一次 `runqget` 从本地获取

          ```go
          //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L2734
          // local runq
          if gp, inheritTime := runqget(_p_); gp != nil {
            return gp, inheritTime
          }
          ```
      2.  仍然没有获取到就继续执行 `globalrunqget` 从全局队列获取

          ```go
          //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L2741
          // global runq
          if sched.runqsize != 0 {
            lock(&sched.lock)
            gp := globrunqget(_p_, 0)
            unlock(&sched.lock)
            if gp != nil {
              return gp, false
            }
          }
          ```
      3.  如果没有从全局队列中获取到 goroutine，就通过 `netpoll` 检查之前由于网络读写而阻塞的 goroutine 是否 runnable， 先尝试先放入当前从 TLS（Thread-local Storage）或者专用寄存器中获取到的 g 绑定的 p（`pp := getg().m.p.ptr()`） ，如果没有获取到就将 runnable 的 goroutine 全部推送到全局队列中；如果获取到了从 runnable queue 中取出当前闲置 p （npidle）数个（如果足够的话）放入全局队列，并激活 p （npidle）数个 m，然后将 runnable queue 中剩余的 g 依次（每次取出队首的 g）放入 pp（当前从专用寄存器中获取到 p），直到 pp 的本地队列满了，如果runnable queue 中还有剩余的 g 则全部放入全局队列。

          ```go
          //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L2755
          // Poll network.
          // This netpoll is only an optimization before we resort to stealing.
          // We can safely skip it if there are no waiters or a thread is blocked
          // in netpoll already. If there is any kind of logical race with that
          // blocked thread (e.g. it has already returned from netpoll, but does
          // not set lastpoll yet), this thread will do blocking netpoll below
          // anyway.
          if netpollinited() && atomic.Load(&netpollWaiters) > 0 && atomic.Load64(&sched.lastpoll) != 0 {
            if list := netpoll(0); !list.empty() { // non-blocking
              gp := list.pop()
              injectglist(&list)
              casgstatus(gp, _Gwaiting, _Grunnable)
              if trace.enabled {
                traceGoUnpark(gp, 0)
              }
              return gp, false
            }
          }
          ```
      4.  如果网络读写而阻塞的 goroutine 没有 runnable 的，那么就其他 P 中偷取其队列前面一半的 goroutine 执行（runqsteal -> runqgrab 流程也称为 work stealing）

          从细节看：会重试 4 次（`const stealTries = 4`），并且最后一次如果从其他 p 的本地队列中窃取不到 g，就尝试窃取其他 p 的 runnext g。

          ```go
          //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L3022
          stealTimersOrRunNextG := i == stealTries-1

          //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L6140
          if n == 0 {
             if stealRunNextG {
                // Try to steal from _p_.runnext.
          ```

          ```go
          //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L2779
          gp, inheritTime, tnow, w, newWork := stealWork(now)
          now = tnow
          if gp != nil {
            // Successfully stole.
            return gp, inheritTime
          }


          //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L3015
          // 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().m.p.ptr()

          	ranTimer := false

          	const stealTries = 4
          	for i := 0; i < stealTries; i++ {
          		stealTimersOrRunNextG := i == stealTries-1

          		for enum := stealOrder.start(fastrand()); !enum.done(); enum.next() {
          			if sched.gcwaiting != 0 {
          				// GC work may be available.
          				return nil, false, now, pollUntil, true
          			}
          			p2 := allp[enum.position()]
          			if pp == p2 {
          				continue
          			}

          			// Steal timers from p2. This call to checkTimers is the only place
          			// where we might hold a lock on a different P's timers. We do this
          			// once on the last pass before checking runnext because stealing
          			// from the other P's runnext should be the last resort, so if there
          			// are timers to steal do that first.
          			//
          			// We only check timers on one of the stealing iterations because
          			// the time stored in now doesn't change in this loop and checking
          			// the timers for each P more than once with the same value of now
          			// is probably a waste of time.
          			//
          			// timerpMask tells us whether the P may have timers at all. If it
          			// can't, no need to check at all.
          			if stealTimersOrRunNextG && timerpMask.read(enum.position()) {
          				tnow, w, ran := checkTimers(p2, now)
          				now = tnow
          				if w != 0 && (pollUntil == 0 || w < pollUntil) {
          					pollUntil = w
          				}
          				if ran {
          					// Running the timers may have
          					// made an arbitrary number of G's
          					// ready and added them to this P's
          					// local run queue. That invalidates
          					// the assumption of runqsteal
          					// that it always has room to add
          					// stolen G's. So check now if there
          					// is a local G to run.
          					if gp, inheritTime := runqget(pp); gp != nil {
          						return gp, inheritTime, now, pollUntil, ranTimer
          					}
          					ranTimer = true
          				}
          			}

          			// Don't bother to attempt to steal if p2 is idle.
          			if !idlepMask.read(enum.position()) {
          				if gp := runqsteal(pp, p2, stealTimersOrRunNextG); gp != nil {
          					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
          }
          ```
    * stop阶段（休眠阶段），执行 top 阶段后未获得可执行的 g 时：
      1. 在休眠前仍尝试 `globalrunqget` 从全局队列中获取 goroutine （没有获取到将当前 p 绑定的 m 解绑，并把当前的 p 闲置队列中）
      2.  没有获取到就 `check again all runq`，自旋检查所有的队列有无 goroutine

          ```go
          //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L2891
          // Check all runqueues once again.
          _p_ = checkRunqsNoP(allpSnapshot, idlepMaskSnapshot)
          if _p_ != nil {
            acquirep(_p_)
            _g_.m.spinning = true
            atomic.Xadd(&sched.nmspinning, 1)
            goto top
          }

          //https://github.com/golang/go/blob/go1.17.13/src/runtime/proc.go#L3089
          // Check all Ps for a runnable G to steal.
          //
          // On entry we have no P. If a G is available to steal and a P is available,
          // the P is returned which the caller should acquire and attempt to steal the
          // work to.
          func checkRunqsNoP(allpSnapshot []*p, idlepMaskSnapshot pMask) *p {
          	for id, p2 := range allpSnapshot {
          		if !idlepMaskSnapshot.read(uint32(id)) && !runqempty(p2) {
          			lock(&sched.lock)
          			pp := pidleget()
          			unlock(&sched.lock)
          			if pp != nil {
          				return pp
          			}

          			// Can't get a P, don't bother checking remaining Ps.
          			break
          		}
          	}

          	return nil
          }
          ```
      3. 没有获取到，执行 `netpoll` 流程，检查网络读写阻塞的 goroutine 有无可执行的
      4. 仍然没有获取到，就执行 `stopm` 将这个线程休眠

### 为什么会在休眠阶段要自旋

### runtime.getg() 的实现

getg() 函数目的是从 TLS（Thread-local Storage）或者专用寄存器中获取 g

```go
//https://github.com/golang/go/blob/go1.17.13/src/runtime/stubs.go#L22
// getg returns the pointer to the current g.
// The compiler rewrites calls to this function into instructions
// that fetch the g directly (from TLS or from the dedicated register).
func getg() *g
```

它的具体实现又在哪？Search for OpGetG in $GOROOT/src/cmd/compile/internal

https://groups.google.com/g/golang-nuts/c/KgPOzaMylHo/m/zX0GosvnAQAJ?pli=1

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-8f772e06ab7ae1b5886a663aa79073e86ea52072%2Fimage-20221130224450297.png?alt=media)

以 amd64 为例：

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-1ac55befeee64a5e8d5920a7cf7185b3f70badce%2Fimage-20221130233925536.png?alt=media)

搜索到对应代码为：

```go
//https://github.com/golang/go/blob/go1.17.10/src/cmd/compile/internal/amd64/ssa.go#L999	
case ssa.OpAMD64LoweredGetG:
		if buildcfg.Experiment.RegabiG && s.ABI == obj.ABIInternal {
			v.Fatalf("LoweredGetG should not appear in ABIInternal")
		}
		r := v.Reg()
		getgFromTLS(s, r)
```

```go
//https://github.com/golang/go/blob/go1.17.10/src/cmd/compile/internal/amd64/ssa.go#L171
func getgFromTLS(s *ssagen.State, r int16) {
	// See the comments in cmd/internal/obj/x86/obj6.go
	// near CanUse1InsnTLS for a detailed explanation of these instructions.
	if x86.CanUse1InsnTLS(base.Ctxt) {
		// MOVQ (TLS), r
		p := s.Prog(x86.AMOVQ)
		p.From.Type = obj.TYPE_MEM
		p.From.Reg = x86.REG_TLS
		p.To.Type = obj.TYPE_REG
		p.To.Reg = r
	} else {
		// MOVQ TLS, r
		// MOVQ (r)(TLS*1), r
		p := s.Prog(x86.AMOVQ)
		p.From.Type = obj.TYPE_REG
		p.From.Reg = x86.REG_TLS
		p.To.Type = obj.TYPE_REG
		p.To.Reg = r
		q := s.Prog(x86.AMOVQ)
		q.From.Type = obj.TYPE_MEM
		q.From.Reg = r
		q.From.Index = x86.REG_TLS
		q.From.Scale = 1
		q.To.Type = obj.TYPE_REG
		q.To.Reg = r
	}
}
```

另外：`getg` 返回指向当前g的指针。编译器将对此函数的调用重写为直接获取g的指令（来自TLS或来自专用寄存器）。 要获取当前用户堆栈的g，可以使用`getg().m.curg`。`getg()`返回当前g，但是当在系统或信号堆栈上执行时，这将分别返回当前m的 g0 或 gsignal 。 要确定g是在用户堆栈还是系统堆栈上运行，可以使用`getg() == getg().m.curg`，相等表示在用户态堆栈，不相等表示在系统堆栈。

## 处理阻塞

### 可被 runtime 拦截到的阻塞

怎么找到可以被 runtime 接管的阻塞代码，看 runtime.gopark 的调用方。

#### 操作没有可用 buffer 的 channel

往没有 buffer 的 channel 写：

```go
var ch = make(chan struct{})
ch <- struct{}{}
```

会通过生成 sudog 放入 channel sendq 中，挂起

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-9b409f20090be0358aecfbbeca563d08688994f7%2Fimage-20221126141441661.png?alt=media)

从没有 buffer 的 channel 读：

```go
var ch = make(chan int)
<- ch
```

会通过生成 sudog 放入 channel recvq 中，挂起

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-cd237e7bc70400dc9aede975db1a5b2f16dd67d1%2Fimage-20221126141534380.png?alt=media)

#### 网络读写

从网络中读，但没有可读取的数据

```go
var c net.Conn
var buf = make([]byte, 1024)

// 没有可读取的数据，阻塞
var n, err = c.Read(buf)
```

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-c61852f5453f55a1b4a5f3d311a12d7d1290656d%2Fimage-20221126141640008.png?alt=media)

往网络中写，但没有 buffer

```go
var c net.Conn
var buf = []byte("hello")

// 没有可用 buffer，写操作被阻塞
var n, err = c.Write(buf)
```

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-5474f8ce0a38c1754748bc996026e174f88c6218%2Fimage-20221126141704350.png?alt=media)

#### Sleep

```go
// 主动休眠，阻塞
time.Sleep(time.Hour)
```

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-196deb4d230d0a13c5645c8a096eed63fc908171%2Fimage-20221126141845661.png?alt=media)

#### 同步等待

select 没有满足执行条件的分支，阻塞

```go
var (
  ch1 = make(chan int)
  ch2 = make(chan int)
)

select {
  case <- ch1:
  	println("ch1 ready")
  case <- ch2:
  	println("ch2 ready")
}
```

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-90dd09d18cc541d6bdf9c8309454b25e30cfcd08%2Fimage-20221126141746739.png?alt=media)

没有获得锁，将阻塞

```go
var lock sync.RWMutex

lock.Lock()
```

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-6e8aa3fb6ac4b5aa46de3bf326df0f292f2ec280%2Fimage-20221126141920504.png?alt=media)

### runtime 无法拦截的阻塞

#### 执行 c 代码发生的的阻塞

```go
package main

/*
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
void output(char *str) {
	usleep(1000000);
	printf("%s\n", str);
}
/*
import "C"
import "unsafe"
```

#### 系统调用阻塞

TODO

## 通过 sysmon 处理 runtime 无法拦截的阻塞

sysmon 即 system monitor，是一个高优先级任务，在专用线程中执行，不需要绑定 P 就可以执行。

会在 sysmon 的 retake 阶段处理：

1. 如果是系统调用（syscall）卡了很久（10ms），那就把 P 剥离（handoffp）
2. 1.14 新增信号抢占，如果是用户 g 运行了很久（10ms），那么就发信号抢占

sysmon 会每隔一段时间执行，最开始是 20us，指数增长（20us、40us、80us ... 10ms），直到超过 10ms，重置为 20us

## 语法实现分析

### 使用 `go` 关键字创建协程到底发生了什么？

```go
package main

func main() {
	go func() {}()
}

//go tool objdump go | grep "go.go:4"
//go.go:4               0x1054d14               31c0                    XORL AX, AX
//go.go:4               0x1054d16               488d1d430b0100          LEAQ go.func.*+315(SB), BX
//go.go:4               0x1054d1d               0f1f00                  NOPL 0(AX)
//go.go:4               0x1054d20               e8db0bfeff              CALL runtime.newproc(SB)
//go.go:4               0x1054d40               c3                      RET    
```

## 调度分析

### 特殊的M：M0

`M0`是启动程序后编号为0的主线程，负责执行初始化和启动第一个G，之后`M0`就和其他的`M`一样了。

### 特殊的G：G0

`G0`是每次启动一个M都会第一个创建的`G`，`G0`负责其所运行着的线程上的 Goroutine 进行调度和管理，当出现`go func() {}`需要创建`goroutine`的时候会将函数的创建交给`G0`。

### 协作式调度

在1.13及以前是基于栈增长检测实现的协作式调度模式。没有函数调用的循环是如何无法被调度的：

```go
func main() {
   var total int
   var wg sync.WaitGroup

   for i := 0; i < 20; i++ {
      wg.Add(1)
      go func() {
         for j := 0; j < 1e6; j++ {
            total ++
         }
         wg.Done()
      }()
   }

   wg.Wait()
}
```

由于没有函数调用，也就没有机会执行栈增长检测的代码，所有的 Goroutine 永远都不会被 block，所以调度器没有抢占这些 goroutine。我们来看一下 tracing 中的状态：\*（所有的 goroutines 没有被抢占）

![force\_preemption\_tracing](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-df6f6b06bc8e29c0ab687673333aa385cfedbfff%2Fforce_preemption_tracing.png?alt=media)

### 抢占式调度

go1.14及以后在原来的执行栈增长检测基础上添加注册异步回调函数的方式实现真正意义上的抢占式调度。

抢占信号的发送是由 preemptM 进行的，在以下场景会发生抢占：

1. Go 后台监控 runtime.sysmon 检测超时（每个goroutine单次调度最多持有10ms CPU分片）发送抢占信号；
2. Go GC 栈扫描发送抢占信号；
3. Go GC STW 的时候调用 preemptall 抢占所有 P，让其暂停；

[从源码剖析Go语言基于信号抢占式调度](https://www.luozhiyun.com/archives/485)

[深度探索Go语言：抢占式调度](https://www.bilibili.com/video/BV1kL411p7mW?from=search\&seid=10107882756813415779)

[深度探索Go语言：抢占式调度(2)](https://www.bilibili.com/video/BV1Ab4y1k7Rb?from=search\&seid=10107882756813415779)

对于如下一段代码，在在go1.14之前会阻塞（依赖栈增长的检测），在go1.14及之后运行正常。

原因是空的`for{}`一直在等待，没有机会执行栈增长检测代码也就意味着没有机会让出，但在GC的时候STW一直在等待它让出，从而陷入了僵局。而对于`fmt.Println`所在`goroutine`由于收到GC的通知而让出，就不会在继续打印，需要等待GC完毕之后，goroutine调度才能继续执行。

```go
package main

import "fmt"

// 在go1.14之前会阻塞
// 在go1.14及之后运行正常
func main() {
	go func(n int) {
		for {
			n++
			fmt.Println(n)
		}
	}(0)

	for {
	}
}

```

#### 发送信号

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2F71f539897a3975afc849227e53a461f859b2fb3c.png?generation=1627714851048368\&alt=media)

#### 处理信号

![](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MdfDl3QJAHc255-HTfO%2Fuploads%2Fgit-blob-8a92c09c27e3d7bc91c360f3a4638603e7372c9b%2Fimage-20210731141131540-7711894.png?alt=media)

![image-20210731141309753](https://544672031-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MdfDl3QJAHc255-HTfO%2Fsync%2F28eda4928a5180868ee6573b5c6b658ba14e4037.png?generation=1627714850969476\&alt=media)

## 疑问

### 切换的时候G保存的上下文有哪些？

主要在调度器保存或者恢复上下文的时候用到【参考：[详解Go语言调度循环源码实现](https://www.luozhiyun.com/archives/448)，[6.5 调度器](https://draveness.me/golang/docs/part3-runtime/ch06-concurrency/golang-goroutine/)】：

```go
type gobuf struct {
    // 栈指针
    sp   uintptr
    // 程序计数器
    pc   uintptr
    // 持有 runtime.gobuf 的 Goroutine
    g    guintptr 
    // 系统调用的返回值
    ret  sys.Uintreg
    ...
}
```

1. 栈指针，为了恢复栈内数据
2. 系统调用的返回值，判断是否正在进行系统函数调用
3. 持有 [`runtime.gobuf`](https://draveness.me/golang/tree/runtime.gobuf) 的 Goroutine，也就是G
4. 程序计数器，存放着下一条指令所在单元的地址，方便恢复运行时继续执行

### 应该尽最大努力将P调度到上一次所绑定的M上？

M会记录上次所调度的P的信息，在活跃状态下会优先判断上次处理的P是否可以被调度。

### 新创建的 goroutine 调度优先级一定比老的 goroutine 优先级高？

在同一个 P 中是的。优先级是 runnext、local queue、global queue。新创建的 goroutine 会放入到 runnext。

### 如果 groutine 执行的程序中有阻塞，那该 goroutine 所绑定的线程也会阻塞吗？为什么

在 runtime 中有处理阻塞，将 groutine 挂起，让出线程，待 ready 后再开始。这个线程又会进入调度循环，继续消费其他队列。详见：**处理阻塞**

还有些是 runtime 中无法拦截的，比如 cgo 执行 c 代码、发生系统阻塞等情况，则通过 `sysmon（system monitor）` 处理

### 在处理阻塞时，为啥有的等待是 sudog，有的等待是 g ?

一个 g 可以对应多个 sudog。比如一个 g 中的 select 可以对应多个 case，当发生阻塞时，每个 case 会对应一个 sudog

## reference

[\[典藏版\] Golang 调度器 GMP 原理与调度全分析](https://learnku.com/articles/41728)

[视频-Golang深入理解GMP](https://www.bilibili.com/video/BV19r4y1w7Nx)

[Go：协程，操作系统线程和 CPU 管理](https://zhuanlan.zhihu.com/p/367601147)

[Go：并发以及调度器亲和](https://zhuanlan.zhihu.com/p/387011586)

[Go 调度器的任务窃取（Work-Stealing）](https://zhuanlan.zhihu.com/p/374033004)

[Go：Goroutine 与抢占机制 基于go1.13](https://zhuanlan.zhihu.com/p/386678889)

[调度系统设计精要](https://draveness.me/system-design-scheduler/)

[详解Go语言调度循环源码实现](https://www.luozhiyun.com/archives/448)

[Go：g0，特殊的 Goroutine](https://zhuanlan.zhihu.com/p/213745994)

[从源码剖析Go语言基于信号抢占式调度](https://www.luozhiyun.com/archives/485)

[Scalable Go Scheduler Design Doc](https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y_kqxDv3I3XMw/)

[6.5 调度器](https://draveness.me/golang/docs/part3-runtime/ch06-concurrency/golang-goroutine/)

[深度探索Go语言：抢占式调度](https://www.bilibili.com/video/BV1kL411p7mW?from=search\&seid=10107882756813415779)

[深度探索Go语言：抢占式调度(2)](https://www.bilibili.com/video/BV1Ab4y1k7Rb?from=search\&seid=10107882756813415779)

[深度探索Go语言(六)：抢占式调度](https://mp.weixin.qq.com/s/31nZzJ-gUBeAh7X9QdubFQ)

[深度探索Go语言(七)：抢占式调度](https://mp.weixin.qq.com/s/ucRS8bxJu7IkHDUW7bMQnA)

[Go语言的抢占式调度.pdf](https://github.com/gopherchina/conference/blob/master/2021/2.2.3%20Go%E8%AF%AD%E8%A8%80%E7%9A%84%E6%8A%A2%E5%8D%A0%E5%BC%8F%E8%B0%83%E5%BA%A6.pdf)

[runtime: tight loops should be preemptible](https://github.com/golang/go/issues/10958)

[深入golang runtime的调度](https://zboya.github.io/post/go_scheduler/)
