Colobu | 鸟窝 晁岳攀修改

// A timers is a per-P set of timers.

type timers struct {
    // 互斥锁保护timers; 虽然timers是每个P的，但是调度器可以访问另一个P的timers，所以我们必须锁定。
	mu mutex
    // heap是一组计时器，按heap[i].when排序。这就是一个四叉堆，虽然没有明确的说明。
    // 必须持有锁才能访问这个堆。
	heap []timerWhen
    // len是heap的长度的原子副本。
	len atomic.Uint32
    // zombies是堆中标记为删除的计时器的数量。
	zombies atomic.Int32
	raceCtx uintptr
    // minWhenHeap是最小的heap[i].when值(= heap[0].when)。
    // wakeTime方法使用minWhenHeap和minWhenModified来确定下一个唤醒时间。
    // 如果minWhenHeap = 0，表示堆中没有计时器。
	minWhenHeap atomic.Int64
    // minWhenModified是具有timerModified位设置的计时器的最小heap[i].when的下界。
    // 如果minWhenModified = 0，表示堆中没有timerModified计时器。
	minWhenModified atomic.Int64
}

type timerWhen struct {
	timer *timer
	when  int64
}

func (ts *timers) lock() {
	lock(&ts.mu)
}

func (ts *timers) unlock() {
	ts.len.Store(uint32(len(ts.heap)))
	unlock(&ts.mu)
}

type timer struct {
	mu mutex
	astate atomic.Uint8 
	state  uint8       
	isChan bool       
	blocked uint32
	when   int64
	period int64
	f      func(arg any, seq uintptr, delay int64)
	arg    any
	seq    uintptr
	ts *timers // 注意这里
	sendLock mutex
	isSending atomic.Int32
}

const timerHeapN = 4

// siftUp将位置i的计时器在堆中合适的位置，通过将其向堆的顶部移动。

func (ts *timers) siftUp(i int) {
	heap := ts.heap
	if i >= len(heap) {
		badTimer()
	}
    // 注意下面两行我们保存了当前i的计时器和它的when值
	tw := heap[i] 
	when := tw.when
	if when <= 0 {
		badTimer()
	}
	for i > 0 {
		p := int(uint(i-1) / timerHeapN) // 父节点 (i-1)/4
		if when >= heap[p].when { // 如果父节点的when <= 当前节点的when，那么就不需要再上浮了
			break
		}
		heap[i] = heap[p] // 父节点下沉到当前的i
		i = p // i指向父节点, 继续循环上浮检查
	}
    // 如果发生了上浮，那么最后将tw放到上浮到的合适位置
	if heap[i].timer != tw.timer {
		heap[i] = tw
	}
}

// siftDown将位置i的计时器放在堆中的正确位置，通过将其向堆的底部移动。

func (ts *timers) siftDown(i int) {
	heap := ts.heap
	n := len(heap)
	if i >= n {
		badTimer()
	}
    // 如果已经是叶子节点，不用下沉了
	if i*timerHeapN+1 >= n {
		return
	}
    // 保存当前i的计时器和when值
	tw := heap[i]
	when := tw.when
	if when <= 0 {
		badTimer()
	}
    // 从左子节点开始，找到最小的when值，然后将当前节点下沉到这个位置
	for {
		leftChild := i*timerHeapN + 1 // 左子节点
		if leftChild >= n {
			break
		}
		w := when
		c := -1
		for j, tw := range heap[leftChild:min(leftChild+timerHeapN, n)] { // 从左子节点开始遍历子节点,找到小于当前w的最小的子节点
			if tw.when < w {
				w = tw.when
				c = leftChild + j
			}
		}
		if c < 0 { // 如果没有找到比当前节点更小的子节点，那么就不用下沉了
			break
		}
        // 将当前节点下沉到最小的子节点
		heap[i] = heap[c]
		i = c
	}
    // 如果发生了下沉，那么最后将tw放到下沉到的合适位置
	if heap[i].timer != tw.timer {
		heap[i] = tw
	}
}

func (ts *timers) initHeap() {
	if len(ts.heap) <= 1 {
		return
	}
    
    // 从最后一个非叶子节点开始，依次下沉
	for i := int(uint(len(ts.heap)-1-1) / timerHeapN); i >= 0; i-- {
		ts.siftDown(i)
	}
}

func (ts *timers) deleteMin() {
    // 得到堆顶元素
	t := ts.heap[0].timer
	if t.ts != ts {
		throw("wrong timers")
	}
	t.ts = nil // 将timer的ts置为nil，自此和ts一别两宽，再无瓜葛
    // 将最后一个元素设置为堆顶
	last := len(ts.heap) - 1
	if last > 0 {
		ts.heap[0] = ts.heap[last]
	}
	ts.heap[last] = timerWhen{} // 将最后一个元素置为空
	ts.heap = ts.heap[:last] // 缩减slice,剔除最后的空元素
	if last > 0 { // 将堆顶元素下沉
		ts.siftDown(0)
	}
	ts.updateMinWhenHeap()
	if last == 0 {
		ts.minWhenModified.Store(0)
	}
}

func (ts *timers) addHeap(t *timer) {
	if netpollInited.Load() == 0 {
		netpollGenericInit()
	}
	if t.ts != nil {
		throw("ts set in timer")
	}
    // 设置timer的ts为当前的timers,从此执子之手，笑傲江湖
	t.ts = ts
    // 添加到最后
	ts.heap = append(ts.heap, timerWhen{t, t.when})
	ts.siftUp(len(ts.heap) - 1) // 上浮它到合适的位置
	if t == ts.heap[0].timer {
		ts.updateMinWhenHeap()
	}
}

import "github.com/ahrav/go-d-ary-heap"

package main

import (
    "fmt"
    "github.com/ahrav/go-d-ary-heap"
)

func main() {
    // Create a min-heap for integers with a branching factor of 3.
    minHeap := heap.NewHeap[int](3, func(a, b int) bool { return a < b })
    // Create a max-heap for integers with a branching factor of 4.
    maxHeap := heap.NewHeap[int](4, func(a, b int) bool { return a > b })
}

minHeap.Push(10)
minHeap.Push(5)
minHeap.Push(15)
maxHeap.Push(10)
maxHeap.Push(5)
maxHeap.Push(15)

fmt.Println(minHeap.Pop()) // Outputs: 5
fmt.Println(maxHeap.Pop()) // Outputs: 15

fmt.Println(minHeap.Peek()) // Assuming more elements were added, outputs the smallest
fmt.Println(maxHeap.Peek()) // Assuming more elements were added, outputs the largest

type Entry[K comparable, V, P any] struct {
	Key      K
	Value    V
	Priority P
	index    int
}

type heapmap[K comparable, V, P any] struct {
	h pq[K, V, P]
	m map[K]*Entry[K, V, P]
}

func (hm *heapmap[K, V, P]) Len() int {
	return len(hm.m)
}

func (hm *heapmap[K, V, P]) Peek() (Entry[K, V, P], bool) {
	if hm.Empty() {
		return Entry[K, V, P]{}, false
	}
	return *hm.h.entries[0], true
}

func (hm *heapmap[K, V, P]) Pop() (Entry[K, V, P], bool) {
	if hm.Empty() {
		return Entry[K, V, P]{}, false
	}
	e := *heap.Pop(&hm.h).(*Entry[K, V, P])
	delete(hm.m, e.Key)
	return e, true
}

func (hm *heapmap[K, V, P]) Set(key K, value V, priority P) {
	if e, ok := hm.m[key]; ok {
		e.Value = value
		e.Priority = priority
		heap.Fix(&hm.h, e.index)
		return
	}
	e := &Entry[K, V, P]{
		Key:      key,
		Value:    value,
		Priority: priority,
	}
	heap.Push(&hm.h, e)
	hm.m[key] = e
}

func (hm *heapmap[K, V, P]) Get(key K) (Entry[K, V, P], bool) {
	if e, ok := hm.m[key]; ok {
		return *e, true
	}
	return Entry[K, V, P]{}, false
}

type Data struct {
    x int64 // 线程A更新的变量
    y int64 // 线程B更新的变量
}

type Data struct {
    x int64           // 线程A更新的变量
    _ [7]int64        // 填充7个int64以对齐至64字节的cache line大小
    y int64           // 线程B更新的变量
}

package main

import (
	"testing"
)
// NonAlignedStruct 未对齐的结构体，补充后占24个字节

type NonAlignedStruct struct {
	a byte // 1字节,补齐7字节
	b int64 // 8字节
	c byte // 1字节,补齐7字节
}
// AlignedStruct 已对齐的结构体，补充后占16个字节

type AlignedStruct struct {
	b int64 // 8字节
	a byte // 1字节
	c byte // 1字节
	_ [6]byte // 填充6个字节，总共16个字节
}

const arraySize = 1024 * 1024

var (
	nonAlignedArray [arraySize]NonAlignedStruct
	alignedArray    [arraySize]AlignedStruct
	result          int64
)
// 初始化数组

func init() {
	for i := 0; i < arraySize; i++ {
		nonAlignedArray[i] = NonAlignedStruct{
			a: byte(i),
			b: int64(i),
			c: byte(i),
		}
		alignedArray[i] = AlignedStruct{
			a: byte(i),
			b: int64(i),
			c: byte(i),
		}
	}
}
// BenchmarkNonAligned 测试未对齐结构体的性能

func BenchmarkNonAligned(b *testing.B) {
	var sum int64
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for j := 0; j < arraySize; j++ {
			sum += nonAlignedArray[j].b // 读取未对齐结构体的字段
		}
	}
	result = sum // 防止编译器优化
}
// BenchmarkAligned 测试已对齐结构体的性能

func BenchmarkAligned(b *testing.B) {
	var sum int64
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for j := 0; j < arraySize; j++ {
			sum += alignedArray[j].b // 读取已对齐结构体的字段
		}
	}
	result = sum // 防止编译器优化
}

// CacheLinePad 用来填充结构体，避免伪共享

type CacheLinePad struct{ _ [CacheLinePadSize]byte }
// CacheLineSize 是 CPU 的缓存行大小，不同的 CPU 架构可能不同.
// 目前 Go 运行时没有检测真实的缓存行大小，所以代码实现使用每个 GOARCH 的常量 CacheLinePadSize 作为近似值。

var CacheLineSize uintptr = CacheLinePadSize

// CacheLinePadSize is used to prevent false sharing of cache lines.
// We choose 128 because Apple Silicon, a.k.a. M1, has 128-byte cache line size.
// It doesn't cost much and is much more future-proof.

const CacheLinePadSize = 128

// CacheLinePadSize is used to prevent false sharing of cache lines.
// We choose 64 because Loongson 3A5000 the L1 Dcache is 4-way 256-line 64-byte-per-line.

const CacheLinePadSize = 64

//go:build 386 || amd64

package cpu

const CacheLinePadSize = 64

type CacheLinePad struct{ _ [cacheLineSize]byte }

type semaRoot struct {
	lock  mutex
	treap *sudog        // root of balanced tree of unique waiters.
	nwait atomic.Uint32 // Number of waiters. Read w/o the lock.
}

var semtable semTable
// Prime to not correlate with any user patterns.

const semTabSize = 251

type semTable [semTabSize]struct {
	root semaRoot
	pad  [cpu.CacheLinePadSize - unsafe.Sizeof(semaRoot{})]byte
}

type mheap struct {
	_ sys.NotInHeap
	lock mutex
	pages pageAlloc // page allocation data structure
	sweepgen uint32 // sweep generation, see comment in mspan; written during STW
	allspans []*mspan // all spans out there
	pagesInUse         atomic.Uintptr // pages of spans in stats mSpanInUse
	pagesSwept         atomic.Uint64  // pages swept this cycle
	pagesSweptBasis    atomic.Uint64  // pagesSwept to use as the origin of the sweep ratio
	sweepHeapLiveBasis uint64         // value of gcController.heapLive to use as the origin of sweep ratio; written with lock, read without
	sweepPagesPerByte  float64        // proportional sweep ratio; written with lock, read without
	reclaimIndex atomic.Uint64
	reclaimCredit atomic.Uintptr
	_ cpu.CacheLinePad // prevents false-sharing between arenas and preceding variables
	
	arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena
    ...
}

var stackpool [_NumStackOrders]struct {
	item stackpoolItem
	_    [(cpu.CacheLinePadSize - unsafe.Sizeof(stackpoolItem{})%cpu.CacheLinePadSize) % cpu.CacheLinePadSize]byte
}

type semaRoot struct {
	lock  mutex
	treap *sudog        // 不重复的等待者(goroutine)的平衡树(treap)的根节点
	nwait atomic.Uint32 // 等待者(goroutine)的数量
}

type sudog struct {
	g *g
	next *sudog
	prev *sudog
	elem unsafe.Pointer // data element (may point to stack)
	acquiretime int64
	releasetime int64
	ticket      uint32
	isSelect bool
	success bool
	waiters uint16
	parent   *sudog // semaRoot binary tree
	waitlink *sudog // g.waiting list or semaRoot
	waittail *sudog // semaRoot
	c        *hchan // channel
}

func (root *semaRoot) queue(addr *uint32, s *sudog, lifo bool) {
	// 设置这个要加入的节点
	s.g = getg()
	s.elem = unsafe.Pointer(addr)
	s.next = nil
	s.prev = nil
	s.waiters = 0
	var last *sudog
	pt := &root.treap
	// 从根节点开始
	for t := *pt; t != nil; t = *pt { // ①
		// 如果地址已经在列表中,则加入到这个地址的链表中
		if t.elem == unsafe.Pointer(addr) {
			// 如果地址已经在列表中，并且指定了先入后出flag,这是一个替换操作
			if lifo {
				// 替换操作
				*pt = s
				s.ticket = t.ticket
				... // 把t的各种信息复制给s
			} else {
				// 增加到到等待列表的末尾
				if t.waittail == nil {
					t.waitlink = s
				} else {
					t.waittail.waitlink = s
				}
				t.waittail = s
				s.waitlink = nil
				if t.waiters+1 != 0 {
					t.waiters++
				}
			}
			return
		}
		last = t
		// 二叉搜索树查找
		if uintptr(unsafe.Pointer(addr)) < uintptr(t.elem) { // ②
			pt = &t.prev
		} else {
			pt = &t.next
		}
	}
	// 为新节点设置ticket.这个ticket是一个随机值，作为随机堆的优先级，用于保持treap的平衡。
	s.ticket = cheaprand() | 1 // ③
	s.parent = last
	*pt = s
	// 根据优先级(ticket)旋转以保持treap的平衡
	for s.parent != nil && s.parent.ticket > s.ticket { // ④
		if s.parent.prev == s {
			root.rotateRight(s.parent) // ⑤
		} else {
			if s.parent.next != s {
				panic("semaRoot queue")
			}
			root.rotateLeft(s.parent) // ⑥
		}
	}
}

type Mutex struct {
	state int32
	sema  uint32
}

func (root *semaRoot) dequeue(addr *uint32) (found *sudog, now, tailtime int64) {
	ps := &root.treap
	s := *ps
	for ; s != nil; s = *ps { // ①， 二叉搜索树查找
		if s.elem == unsafe.Pointer(addr) { // ②
			goto Found
		}
		if uintptr(unsafe.Pointer(addr)) < uintptr(s.elem) {
			ps = &s.prev
		} else {
			ps = &s.next
		}
	}
	return nil, 0, 0
Found: // ③
	...
	if t := s.waitlink; t != nil { // ④
		*ps = t
		...
	} else { // ⑤
		// 旋转s到叶节点，以便删除
		for s.next != nil || s.prev != nil {
			if s.next == nil || s.prev != nil && s.prev.ticket < s.next.ticket {
				root.rotateRight(s)
			} else {
				root.rotateLeft(s)
			}
		}
		// ⑤ 删除s
		if s.parent != nil {
			if s.parent.prev == s {
				s.parent.prev = nil
			} else {
				s.parent.next = nil
			}
		} else {
			root.treap = nil
		}
		tailtime = s.acquiretime
	}
	... // 清理s的不需要的信息
	return s, now, tailtime
}

func (root *semaRoot) rotateLeft(x *sudog) {
	// p -> (x a (y b c))
	p := x.parent
	y := x.next
	b := y.prev
	y.prev = x // ①
	x.parent = y // ②
	x.next = b // ③
	if b != nil {
		b.parent = x // ④
	}
	y.parent = p // ⑤
	if p == nil {
		root.treap = y // ⑥
	} else if p.prev == x { // ⑦
		p.prev = y
	} else {
		if p.next != x {
			throw("semaRoot rotateLeft")
		}
		p.next = y
	}
}

func (root *semaRoot) rotateRight(y *sudog) {
	// p -> (y (x a b) c)
	p := y.parent
	x := y.prev
	b := x.next
	x.next = y // ①
	y.parent = x // ②
	y.prev = b // ③
	if b != nil {
		b.parent = y // ④
	}
	x.parent = p // ⑤
	if p == nil {
		root.treap = x // ⑥
	} else if p.prev == y { // ⑦
		p.prev = x
	} else {
		if p.next != y {
			throw("semaRoot rotateRight")
		}
		p.next = x
	}
}

// 旋转s到叶节点，以便删除

for s.next != nil || s.prev != nil {
	if s.next == nil || s.prev != nil && s.prev.ticket < s.next.ticket {
		root.rotateRight(s)
	} else {
		root.rotateLeft(s)
	}
}

type BitVec struct {
	N int32    // 这个向量中包含的bit数
	B []uint32 // 保存这些bit所需的数组
}

func New(n int32) BitVec {
	nword := (n + wordBits - 1) / wordBits // 计算保存这些bit所需的最少的数组
	return BitVec{n, make([]uint32, nword)}
}

func (dst BitVec) And(src1, src2 BitVec) {
	if len(src1.B) == 0 {
		return
	}
	_, _ = dst.B[len(src1.B)-1], src2.B[len(src1.B)-1] // hoist bounds checks out of the loop
	for i, x := range src1.B {
		dst.B[i] = x & src2.B[i]
	}
}

func (bv BitVec) Not() {
	for i, x := range bv.B {
		bv.B[i] = ^x
	}
	if bv.N%wordBits != 0 {
		bv.B[len(bv.B)-1] &= 1<<uint(bv.N%wordBits) - 1 // clear bits past N in the last word
	}
}

func (bv BitVec) Count() int {
	n := 0
	for _, x := range bv.B {
		n += bits.OnesCount32(x)
	}
	return n
}

// 一个goroutine的指针

type guintptr uintptr
//go:nosplit

func (gp guintptr) ptr() *g { return (*g)(unsafe.Pointer(gp)) }
//go:nosplit

func (gp *guintptr) set(g *g) { *gp = guintptr(unsafe.Pointer(g)) }
//go:nosplit

func (gp *guintptr) cas(old, new guintptr) bool {
	return atomic.Casuintptr((*uintptr)(unsafe.Pointer(gp)), uintptr(old), uintptr(new))
}

type p struct {
	id          int32
	status      uint32 // one of pidle/prunning/...
	link        puintptr
	schedtick   uint32     // incremented on every scheduler call
	syscalltick uint32     // incremented on every system call
	sysmontick  sysmontick // last tick observed by sysmon
	m           muintptr   // back-link to associated m (nil if idle)
	mcache      *mcache
	pcache      pageCache
	raceprocctx uintptr
	deferpool    []*_defer // pool of available defer structs (see panic.go)
	deferpoolbuf [32]*_defer
	// Cache of goroutine ids, amortizes accesses to runtime·sched.goidgen.
	goidcache    uint64
	goidcacheend uint64
	// 本地运行的无锁循环队列
	runqhead uint32
	runqtail uint32
	runq     [256]guintptr
	// 如果非nil，是一个可优先运行的G
	runnext guintptr
	...
}

// runqput 尝试将 g 放到本地可运行队列上。
// 如果 next 为 false，runqput 将 g 添加到可运行队列的尾部。
// 如果 next 为 true，runqput 将 g 放在 pp.runnext 位置。
// 如果可运行队列已满，runnext 将 g 放到全局队列上。
// 只能由拥有 P 的所有者执行。

func runqput(pp *p, gp *g, next bool) {
	if !haveSysmon && next {
        // 如果没有 sysmon，我们必须完全避免 runnext，否则会导致饥饿。
		next = false
	}
	if randomizeScheduler && next && randn(2) == 0 {
        // 如果随机调度器打开，我们有一半的机会避免运行 runnext
		next = false
	}
    // 如果 next 为 true，优先处理 runnext
    // 将当前的goroutine放到 runnext 中, 如果原来runnext中有goroutine, 则将其放到runq中
	if next {
	retryNext:
		oldnext := pp.runnext
		if !pp.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()
	}
    // 重点来了，将goroutine放入runq中
retry:
	h := atomic.LoadAcq(&pp.runqhead) // ①
	t := pp.runqtail
	if t-h < uint32(len(pp.runq)) { // ② 如果队列未满
		pp.runq[t%uint32(len(pp.runq))].set(gp) // ③ 将goroutine放入队列
		atomic.StoreRel(&pp.runqtail, t+1) // ④ 更新队尾
		return
	}
	if runqputslow(pp, gp, h, t) { // ⑤ 如果队列满了，调用runqputslow 尝试将goroutine放入全局队列
		return
	}
	// 如果队列未满，上面的操作应该已经成功返回，否则重试
	goto retry
}

// runqputbatch 尝试将 q 上的所有 G 放到本地可运行队列上。
// 如果队列已满，它们将被放到全局队列上；在这种情况下，这将暂时获取调度器锁。
// 只能由拥有 P 的所有者执行。

func runqputbatch(pp *p, q *gQueue, qsize int) {
	h := atomic.LoadAcq(&pp.runqhead) // ①
	t := pp.runqtail
	n := uint32(0)
	for !q.empty() && t-h < uint32(len(pp.runq)) { // ② 放入的批量goroutine非空， 并且本地队列还足以放入
		gp := q.pop()
		pp.runq[t%uint32(len(pp.runq))].set(gp)
		t++
		n++
	}
	qsize -= int(n)
	if randomizeScheduler { // ③ 随机调度器, 随机打乱
		off := func(o uint32) uint32 {
			return (pp.runqtail + o) % uint32(len(pp.runq))
		}
		for i := uint32(1); i < n; i++ {
			j := cheaprandn(i + 1)
			pp.runq[off(i)], pp.runq[off(j)] = pp.runq[off(j)], pp.runq[off(i)]
		}
	}
	atomic.StoreRel(&pp.runqtail, t) // ④ 更新队尾
	if !q.empty() {
		lock(&sched.lock)
		globrunqputbatch(q, int32(qsize))
		unlock(&sched.lock)
	}
}

// runqget 从本地可运行队列中获取一个 G。
// 如果 inheritTime 为 true，gp 应该继承当前时间片的剩余时间。
// 否则，它应该开始一个新的时间片。
// 只能由拥有 P 的所有者执行。

func runqget(pp *p) (gp *g, inheritTime bool) {
	next := pp.runnext
    // 如果有 runnext，优先处理 runnext
	if next != 0 && pp.runnext.cas(next, 0) { // ①
		return next.ptr(), true
	}
	for {
		h := atomic.LoadAcq(&pp.runqhead) // ② 获取队头
		t := pp.runqtail
		if t == h { // ③ 队列为空
			return nil, false
		}
		gp := pp.runq[h%uint32(len(pp.runq))].ptr() // ④ 获取队头的goroutine
		if atomic.CasRel(&pp.runqhead, h, h+1) { // ⑤ 更新队头
			return gp, false
		}
	}
}

// runqdrain 从 pp 的本地可运行队列中获取所有的 G 并返回。
// 只能由拥有 P 的所有者执行。

func runqdrain(pp *p) (drainQ gQueue, n uint32) {
	oldNext := pp.runnext
	if oldNext != 0 && pp.runnext.cas(oldNext, 0) {
		drainQ.pushBack(oldNext.ptr()) // ① 将 runnext 中的goroutine放入队列
		n++
	}
retry:
	h := atomic.LoadAcq(&pp.runqhead) // ② 获取队头
	t := pp.runqtail
	qn := t - h
	if qn == 0 {
		return
	}
	if qn > uint32(len(pp.runq)) { // ③ 居然超出队列的长度了？
		goto retry
	}
	if !atomic.CasRel(&pp.runqhead, h, h+qn) { // ④ 更新队头
		goto retry
	}
    // ⑤ 将队列中的goroutine放入队列drainQ中
	for i := uint32(0); i < qn; i++ {
		gp := pp.runq[(h+i)%uint32(len(pp.runq))].ptr()
		drainQ.pushBack(gp)
		n++
	}
	return
}

// runqgrab 从 pp 的本地可运行队列中获取一半的 G 并返回。
// Batch 是一个环形缓冲区，从 batchHead 开始。
// 返回获取的 goroutine 数量。
// 可以由任何 P 执行。

func runqgrab(pp *p, batch *[256]guintptr, batchHead uint32, stealRunNextG bool) uint32 {
	for {
		h := atomic.LoadAcq(&pp.runqhead) // load-acquire, synchronize with other consumers
		t := atomic.LoadAcq(&pp.runqtail) // load-acquire, synchronize with the producer
		n := t - h
		n = n - n/2 // ① 取一半的goroutine
		if n == 0 {
			if stealRunNextG {
                // ② 如果要偷取runnext中的goroutine
				if next := pp.runnext; next != 0 {
					if pp.status == _Prunning {
                        // ② 如果要偷取runnext中的goroutine，这里会sleep一会
						if !osHasLowResTimer {
							usleep(3)
						} else {
							osyield()
						}
					}
					if !pp.runnext.cas(next, 0) {
						continue
					}
					batch[batchHead%uint32(len(batch))] = next
					return 1
				}
			}
			return 0
		}
		if n > uint32(len(pp.runq)/2) { // ③ 如果要偷取的goroutine数量超过一半, 重试
			continue
		}
        // ④ 将队列中至多一半的goroutine放入batch中
		for i := uint32(0); i < n; i++ {
			g := pp.runq[(h+i)%uint32(len(pp.runq))]
			batch[(batchHead+i)%uint32(len(batch))] = g
		}
		if atomic.CasRel(&pp.runqhead, h, h+n) { // ⑤ 更新队头
			return n
		}
	}
}

// runqsteal 从 p2 的本地可运行队列中偷取一半的 G 并返回。
// 如果 stealRunNextG 为 true，它还会尝试偷取 runnext 中的 G。

func runqsteal(pp, p2 *p, stealRunNextG bool) *g {
	t := pp.runqtail
	n := runqgrab(p2, &pp.runq, t, stealRunNextG) // ① 从p2中偷取一半的goroutine
	if n == 0 {
		return nil
	}
	n--
	gp := pp.runq[(t+n)%uint32(len(pp.runq))].ptr() // ② 获取偷取的一个goroutine
	if n == 0 {
		return gp
	}
	h := atomic.LoadAcq(&pp.runqhead) // ③ 获取队头
	if t-h+n >= uint32(len(pp.runq)) { // ④ 如果队列满了，重置队列
		throw("runqsteal: runq overflow")
	}
	atomic.StoreRel(&pp.runqtail, t+n) // ⑤ 更新队尾
	return gp
}

type gQueue struct {
	head guintptr
	tail guintptr
}

func (q *gQueue) empty() bool {
	return q.head == 0
}
// push 将gp添加到q的头部。

func (q *gQueue) push(gp *g) {
	gp.schedlink = q.head
	q.head.set(gp)
	if q.tail == 0 {
		q.tail.set(gp)
	}
}
// pushBack 增加gp到q的尾部。

func (q *gQueue) pushBack(gp *g) {
	gp.schedlink = 0
	if q.tail != 0 {
		q.tail.ptr().schedlink.set(gp)
	} else {
		q.head.set(gp)
	}
	q.tail.set(gp)
}
// q2的所有G添加到q的尾部。之后不能再使用q2。

func (q *gQueue) pushBackAll(q2 gQueue) {
	if q2.tail == 0 {
		return
	}
	q2.tail.ptr().schedlink = 0
	if q.tail != 0 {
		q.tail.ptr().schedlink = q2.head
	} else {
		q.head = q2.head
	}
	q.tail = q2.tail
}
// pop 移除并返回队列q的头部。如果q为空，则返回nil。

func (q *gQueue) pop() *g {
	gp := q.head.ptr()
	if gp != nil {
		q.head = gp.schedlink
		if q.head == 0 {
			q.tail = 0
		}
	}
	return gp
}
// popList 将所有的元素从队列q中取出并返回一个gList。

func (q *gQueue) popList() gList {
	stack := gList{q.head}
	*q = gQueue{}
	return stack
}

type gList struct {
	head guintptr
}

func (l *gList) empty() bool {
	return l.head == 0
}
// push 将gp添加到l的头部。

func (l *gList) push(gp *g) {
	gp.schedlink = l.head
	l.head.set(gp)
}
// pushAll 将q中的所有G添加到l的头部。

func (l *gList) pushAll(q gQueue) {
	if !q.empty() {
		q.tail.ptr().schedlink = l.head
		l.head = q.head
	}
}
// pop 移除并返回l的头部。如果l为空，则返回nil。

func (l *gList) pop() *g {
	gp := l.head.ptr()
	if gp != nil {
		l.head = gp.schedlink
	}
	return gp
}

var (
	sched      schedt
)

type schedt struct {
	...
	// Global runnable queue.
	runq     gQueue
	runqsize int32
    ...
}

func globrunqput(gp *g) {
	assertLockHeld(&sched.lock) // 保证锁被持有
	sched.runq.pushBack(gp)
	sched.runqsize++
}

func globrunqputhead(gp *g) {
	assertLockHeld(&sched.lock) // 保证锁被持有
	sched.runq.push(gp)
	sched.runqsize++
}

func globrunqputbatch(batch *gQueue, n int32) {
	assertLockHeld(&sched.lock) // 保证锁被持有
	sched.runq.pushBackAll(*batch)
	sched.runqsize += n
	*batch = gQueue{}
}

func globrunqget(pp *p, max int32) *g {
	assertLockHeld(&sched.lock) // 保证锁被持有
	if sched.runqsize == 0 { // 如果全局队列为空
		return nil
	}
	n := sched.runqsize/gomaxprocs + 1 // 从全局队列中获取goroutine的数量
	if n > sched.runqsize {
		n = sched.runqsize
	}
	if max > 0 && n > max { // 如果max大于0，取最小值
		n = max
	}
	if n > int32(len(pp.runq))/2 { // 如果要获取的goroutine数量超过一半，只取一半，不贪婪
		n = int32(len(pp.runq)) / 2
	}
	sched.runqsize -= n
	gp := sched.runq.pop() // 从全局队列中获取一个goroutine
	n--
	for ; n > 0; n-- { // 从全局队列中获取n-1个goroutine
		gp1 := sched.runq.pop()
		runqput(pp, gp1, false) // 将goroutine放入本地队列
	}
	return gp // 返回获取的goroutine
}