MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

Go调度循环的实现

2023-12-247.8k 阅读

Go调度器概述

在深入探讨Go调度循环之前，我们先来了解一下Go调度器的整体架构。Go语言的调度器是其运行时系统（runtime）的核心组件之一，负责管理和调度Go协程（goroutine）。与传统操作系统线程模型不同，Go采用了M:N调度模型，即多个goroutine映射到多个操作系统线程上。

Go调度器主要由三个核心组件构成：G（goroutine）、M（machine，操作系统线程）和P（processor，处理器）。

G（goroutine）

G代表一个独立的执行单元，也就是我们通常所说的协程。每个G都有自己的栈空间、程序计数器和局部变量。Go语言通过轻量级的协程模型，使得在一个程序中可以轻松创建成千上万的并发执行单元，而不像传统线程那样消耗大量系统资源。

M（machine）

M对应一个操作系统线程。每个M都有自己的栈空间，用于执行Go代码。M负责执行G，但是M并不直接管理G，而是通过P来获取可执行的G。

P（processor）

P是调度器的中间层，它管理着一组可运行的G队列。P的数量决定了同一时刻能够并发执行的G数量，默认情况下，P的数量等于CPU核心数。P还负责管理M的运行，每个M必须绑定到一个P上才能执行G。

Go调度循环的核心机制

调度循环的入口

Go调度循环的入口位于runtime/proc.go文件中的schedule函数。这个函数是整个调度循环的核心，它不断地从各种队列中寻找可运行的G，并将其分配给M执行。

// runtime/proc.go
func schedule() {
    var gp *g
    top:
    for {
        // 从本地运行队列获取G
        gp = runqget(_g_.m.p.ptr())
        if gp != nil {
            execute(gp, false)
            goto top
        }

        // 尝试从全局运行队列获取G
        gp = globrunqget(_g_.m.p.ptr(), 1)
        if gp != nil {
            execute(gp, false)
            goto top
        }

        // 尝试从其他P的运行队列窃取G
        gp = runqsteal(_g_.m.p.ptr())
        if gp != nil {
            execute(gp, false)
            goto top
        }

        // 没有可运行的G，进入睡眠
        goparkunlock(&_g_.m.p.ptr().sched, waitReasonNoWork, traceEvGoBlockNoWork, 1)
    }
}

从本地运行队列获取G

在schedule函数中，首先尝试从本地运行队列获取G。本地运行队列是每个P私有的，存放着已经准备好运行的G。runqget函数负责从本地运行队列中取出一个G。

// runtime/proc.go
func runqget(p *p) *g {
    qp := &p.runq
    if atomic.Load(&qp.n) == 0 {
        return nil
    }
    // 取出队列头部的G
    gp := qp.head
    if gp == nil {
        throw("runqget: queue is not empty but head is nil")
    }
    qp.head = gp.schedlink
    if qp.head == nil {
        qp.tail = nil
    }
    atomic.Xadd(&qp.n, -1)
    return gp
}

从全局运行队列获取G

如果本地运行队列中没有可运行的G，调度器会尝试从全局运行队列获取G。全局运行队列是所有P共享的，当某个P的本地运行队列满了，多余的G会被放入全局运行队列。globrunqget函数负责从全局运行队列中获取G。

// runtime/proc.go
func globrunqget(_p_ *p, max int) *g {
    for {
        qp := &globlrunq
        n := atomic.Load(&qp.n)
        if n == 0 {
            return nil
        }
        if max > int(n) {
            max = int(n)
        }
        if atomic.Cas(&globlrunq.lock, 0, 1) {
            gp := qp.head
            if gp != nil {
                qp.head = gp.schedlink
                if qp.head == nil {
                    qp.tail = nil
                }
                atomic.Xadd(&qp.n, -1)
                atomic.Store(&globlrunq.lock, 0)
                return gp
            }
            atomic.Store(&globlrunq.lock, 0)
            return nil
        }
    }
}

从其他P的运行队列窃取G

当本地运行队列和全局运行队列都没有可运行的G时，调度器会尝试从其他P的运行队列窃取G。这是一种负载均衡的机制，确保所有的M都能充分利用。runqsteal函数负责从其他P的运行队列中窃取G。

// runtime/proc.go
func runqsteal(runningP *p) *g {
    for i := 0; i < int(gomaxprocs); i++ {
        pid := (runningP.id + 1 + i) % gomaxprocs
        p := allp[pid]
        if p == nil || atomic.Load(&p.status) != _Pidle {
            continue
        }
        qp := &p.runq
        n := atomic.Load(&qp.n)
        if n == 0 {
            continue
        }
        if atomic.Cas(&p.status, _Pidle, _Prunning) {
            // 窃取队列尾部的G
            gp := qp.tail
            if gp == nil {
                throw("runqsteal: queue is not empty but tail is nil")
            }
            qp.tail = gp.schedlink
            if qp.tail == nil {
                qp.head = nil
            }
            atomic.Xadd(&qp.n, -1)
            return gp
        }
    }
    return nil
}

执行G

当调度器获取到一个可运行的G后，会调用execute函数来执行这个G。execute函数负责设置当前M要执行的G，并跳转到G的入口函数开始执行。

// runtime/proc.go
func execute(gp *g, inheritTime bool) {
    _g_.m.curg = gp
    gp.waitsince = 0
    gp.preempt = false
    gp.stackguard0 = gp.stack.lo + _StackGuard
    if inheritTime {
        gp.timer = _g_.m.p.ptr().schedtick
    } else {
        gp.timer = 0
    }
    gogo(&gp.sched)
}

Go调度循环中的特殊情况处理

G的阻塞与唤醒

当一个G执行系统调用（如I/O操作）或调用gopark等函数时，会进入阻塞状态。此时，调度器需要将这个G从运行队列中移除，并将M释放，以便执行其他可运行的G。

// runtime/proc.go
func gopark(unlockf func(*g, unsafe.Pointer) bool, lock unsafe.Pointer, reason waitReason, traceEv byte, traceskip int) {
    mp := acquirem()
    gp := mp.curg
    if gp == gp.m.g0 {
        throw("gopark on g0")
    }
    gp.waitreason = reason
    gp.param = nil
    mp.waitlock = lock
    mp.waitunlockf = unlockf
    mp.waittraceev = traceEv
    mp.waittraceskip = traceskip
    mcall(park_m)
}

当阻塞的条件解除时，需要唤醒对应的G。唤醒操作通常通过goready函数将G重新放入运行队列。

// runtime/proc.go
func goready(gp *g, traceskip int) {
    _g_ := getg()
    casgstatus(gp, _Gwaiting, _Grunnable)
    if _g_.m.p.ptr().runqput(gp) {
        return
    }
    globrunqput(gp)
}

抢占式调度

Go调度器还支持抢占式调度，这意味着即使一个G没有主动让出CPU，调度器也可以在适当的时候暂停它的执行，以便让其他G有机会运行。

在Go 1.20之前，抢占式调度主要依赖于协作式抢占，即G在执行某些特定的函数（如系统调用、GC标记等）时，会主动检查是否需要被抢占。从Go 1.20开始，引入了基于信号的抢占式调度，使得调度器可以更及时地暂停正在运行的G。

基于信号的抢占式调度原理如下：

  1. 当一个G开始运行时，调度器会为其设置一个信号处理函数。
  2. 当调度器决定抢占某个G时，会向对应的M发送一个信号。
  3. M收到信号后，会跳转到信号处理函数，在信号处理函数中，会将当前正在执行的G标记为需要抢占，并安排下一次调度。
// runtime/os_linux.go
func sigtrampgo(buf *sigctxt) {
    _g_ := getg()
    if _g_.m.p == nil {
        return
    }
    if _g_.m.p.ptr().syscallsp == (uintptr)(buf) {
        if _g_.m.sigmask == 0 {
            return
        }
    }
    sig := uint32(_g_.m.sigmask)
    _g_.m.sigmask = 0
    if sig&_SIGURG != 0 {
        if _g_.m.p.ptr().syscallsp != 0 {
            asminit()
            gosigurg(_g_.m.p.ptr().syscallsp)
        }
    }
    if sig&_SIGPROF != 0 {
        asminit()
        gosigprof()
    }
}

示例代码解析

下面通过一个简单的示例代码来展示Go调度循环的实际运行情况。

package main

import (
    "fmt"
    "time"
)

func worker(id int) {
    for i := 0; i < 3; i++ {
        fmt.Printf("Worker %d: %d\n", id, i)
        time.Sleep(time.Millisecond * 100)
    }
}

func main() {
    for i := 0; i < 5; i++ {
        go worker(i)
    }
    time.Sleep(time.Second * 2)
}

在这个示例中，我们创建了5个goroutine，每个goroutine执行worker函数。worker函数会打印一些信息，并暂停100毫秒。主函数通过go关键字启动这些goroutine，并等待2秒后退出。

当程序运行时，调度器会不断地在这些goroutine之间切换，确保每个goroutine都有机会执行。通过time.Sleep函数，我们模拟了一些I/O操作或其他阻塞操作，这样调度器就有机会将M分配给其他可运行的G。

总结Go调度循环的实现要点

  1. 调度器组件协作：G、M和P三个组件紧密协作，通过本地运行队列、全局运行队列和窃取机制，实现高效的goroutine调度。
  2. 阻塞与唤醒机制：当G进入阻塞状态时，调度器能够及时将其移除运行队列，并在条件满足时唤醒它，重新放入运行队列。
  3. 抢占式调度：从协作式抢占到基于信号的抢占式调度，Go调度器不断优化，以确保每个goroutine都能公平地获得CPU时间。
  4. 负载均衡：通过窃取机制，调度器能够在不同的P之间实现负载均衡，充分利用系统资源。

通过深入理解Go调度循环的实现原理，我们可以更好地编写高效的并发程序，充分发挥Go语言在并发编程方面的优势。同时，了解调度器的内部机制也有助于我们分析和解决并发程序中可能出现的性能问题。