概述

Go 言语在并发编程方面有强壮的能力，这离不开言语层面临并发编程的支撑。本节会介绍 Go 言语运转时调度器的完成原理，其间包括调度器的规划与完成原理、演化进程以及与运转时调度相关的数据结构。

谈到 Go 言语调度器，咱们绕不开的是操作体系、进程与线程这些概念，线程是操作体系调度时的最基本单元，而 Linux 在调度器并不差异进程和线程的调度，它们在不同操作体系上也有不同的完成，可是在大多数的完成中线程都归于进程：

多个线程可以归于同一个进程并共享内存空间。由于多线程不需求创建新的虚拟内存空间，所以它们也不需求内存办理单元处理上下文的切换，线程之间的通讯也正是依据共享的内存进行的，与重量级的进程相比，线程显得比较轻量。

尽管线程比较轻量，可是在调度时也有比较大的额定开支。每个线程会都占用 1M 以上的内存空间，在切换线程时不止会消耗较多的内存，康复寄存器中的内容还需求向操作体系申请或者销毁资源，每一次线程上下文的切换都需求消耗 ~1us 左右的时刻，可是 Go 调度器对 Goroutine 的上下文切换约为 ~0.2us，削减了 80% 的额定开支。

Go 言语的调度器经过使用与 CPU 数量持平的线程削减线程频频切换的内存开支，一起在每一个线程上履行额定开支更低的 Goroutine 来降低操作体系和硬件的负载。

规划原理

今日的 Go 言语调度器有着优异的功用，可是假如咱们回头看 Go 言语的 0.x 版别的调度器会发现最初的调度器不仅完成十分粗陋，也无法支撑高并发的服务。调度器经过几个大版别的迭代才有今日的优异功用，历史上几个不同版别的调度器引进了不同的改善，也存在着不同的缺点:

  • 单线程调度器 —Go 0.x

    • 改善：只包括 40 多行代码；
    • 缺点：程序中只能存在一个活泼线程，由 G-M 模型组成；

  • 多线程调度器 —Go 1.0

    • 改善：答应运转多线程的程序；
    • 缺点：大局锁导致竞赛严峻；

  • 使命盗取调度器 —Go 1.1

    • 改善1：引进了处理器 P，构成了目前的G-M-P模型；
    • 改善2：在处理器 P 的基础上完成了依据作业盗取的调度器；
    • 缺点1：在某些状况下，Goroutine 不会让出线程，进而形成饥饿问题；
    • 缺点2：时刻过长的废物收回（Stop-the-world，STW）会导致程序长时刻无法作业；

  • 抢占式调度器 —Go 1.2~ 至今

    • 依据协作的抢占式调度器 – 1.2 ~ 1.13

      • 改善：经过编译器在函数调用时刺进抢占查看指令，在函数调用时查看当时 Goroutine 是否发起了抢占恳求，完成依据协作的抢占式调度；
      • 缺点：Goroutine 可能会由于废物收回和循环长时刻占用资源导致程序暂停；

    • 依据信号的抢占式调度器 – 1.14 ~ 至今

      • 改善：完成依据信号的真抢占式调度；
      • 缺点1：废物收回在扫描栈时会触发抢占调度；
      • 缺点2：抢占的时刻点不够多，还不能掩盖全部的边际状况；

  • 非均匀存储拜访调度器 — 提案

    • 改善：对运转时的各种资源进行分区；
    • 缺点：完成十分杂乱，到今日还没有提上日程；

除了多线程、使命盗取和抢占式调度器之外，Go 言语社区目前还有一个非均匀存储拜访（Non-uniform memory access，NUMA）调度器的提案。在这一节中，咱们将顺次介绍不同版别调度器的完成原理以及未来可能会完成的调度器提案。

单线程调度器

0.x 版别调度器只包括两种结构 — 表明 Goroutine 的 G 和表明线程的 M 两种结构，大局也只要一个线程。咱们可以在clean up scheduler 提交中找到单线程调度器的源代码，在这时 Go 言语的调度器仍是由 C 言语完成的，调度函数runtime.scheduler:9682400也只包括 40 多行代码 ：

static void scheduler(void) {
	G* gp;
	lock(&sched);
	if(gosave(&m->sched)){
		lock(&sched);
		gp = m->curg;
		switch(gp->status){
		case Grunnable:
		case Grunning:
			gp->status = Grunnable;
			gput(gp);
			break;
		...
		}
		notewakeup(&gp->stopped);
	}
	gp = nextgandunlock();
	noteclear(&gp->stopped);
	gp->status = Grunning;
	m->curg = gp;
	g = gp;
	gogo(&gp->sched);
}

该函数会遵循如下的进程调度 Goroutine：

  1. 获取调度器的大局锁；
  2. 调用runtime.gosave:9682400保存栈寄存器和程序计数器；
  3. 调用runtime.nextgandunlock:9682400获取下一个需求运转的 Goroutine 并解锁调度器；
  4. 修正大局线程m上要履行的 Goroutine；
  5. 调用runtime.gogo:9682400函数运转最新的 Goroutine；

尽管这个单线程调度器的唯一优点就是能运转，可是这次提交现已包括了 G 和 M 两个重要的数据结构，也建立了 Go 言语调度器的框架。

多线程调度器

Go 言语在 1.0 版别正式发布时就支撑了多线程的调度器，与上一个版别几乎不可用的调度器相比，Go 言语团队在这一阶段完成了从不可用到可用的跨越。咱们可以在pkg/runtime/proc.c文件中找到 1.0.1 版别的调度器，多线程版别的调度函数runtime.schedule:go1.0.1包括 70 多行代码，咱们在这儿保留了该函数的核心逻辑：

static void schedule(G *gp) {
	schedlock();
	if(gp != nil) {
		gp->m = nil;
		uint32 v = runtimexadd(&runtimesched.atomic, -1<<mcpuShift);
		if(atomic_mcpu(v) > maxgomaxprocs)
			runtimethrow("negative mcpu in scheduler");
		switch(gp->status){
		case Grunning:
			gp->status = Grunnable;
			gput(gp);
			break;
		case ...:
		}
	} else {
		...
	}
	gp = nextgandunlock();
	gp->status = Grunning;
	m->curg = gp;
	gp->m = m;
	runtimegogo(&gp->sched, 0);
}

全体的逻辑与单线程调度器没有太多差异，由于咱们的程序中可能一起存在多个活泼线程，所以多线程调度器引进了GOMAXPROCS变量协助咱们灵活控制程序中的最大处理器数，即活泼线程数。

多线程调度器的主要问题是调度时的锁竞赛会严峻浪费资源，Scalable Go Scheduler Design Doc 中对调度器做的功用测验发现 14% 的时刻都花费在runtime.futex:go1.0.1上，该调度器有以下问题需求处理：

  1. 调度器和锁是大局资源，一切的调度状况都是中心化存储的，锁竞赛问题严峻；
  2. 线程需求常常相互传递可运转的 Goroutine，引进了很多的推迟；
  3. 每个线程都需求处理内存缓存，导致很多的内存占用并影响数据局部性；
  4. 体系调用频频堵塞和解除堵塞正在运转的线程，添加了额定开支；

这儿的大局锁问题和 Linux 操作体系调度器在前期遇到的问题比较类似，处理的计划也都大同小异。

使命盗取调度器

2012 年 Google 的工程师 Dmitry Vyukov 在Scalable Go Scheduler Design Doc中指出了现有多线程调度器的问题并在多线程调度器上提出了两个改善的手段：

  1. 在当时的 G-M 模型中引进了处理器 P，添加中间层；
  2. 在处理器 P 的基础上完成依据作业盗取的调度器；

依据使命盗取的 Go 言语调度器使用了沿用至今的 G-M-P 模型，咱们能在runtime: improved scheduler提交中找到使命盗取调度器刚被完成时的源代码，调度器的runtime.schedule:779c45a在这个版别的调度器中反而更简略了：

static void schedule(void) {
    G *gp;
 top:
    if(runtimegcwaiting) {
        gcstopm();
        goto top;
    }
    gp = runqget(m->p);
    if(gp == nil)
        gp = findrunnable();
    ...
    execute(gp);
}
  1. 假如当时运转时在等待废物收回，调用runtime.gcstopm:779c45a函数；
  2. 调用runtime.runqget:779c45a和runtime.findrunnable:779c45a从本地或者大局的运转行列中获取待履行的 Goroutine；
  3. 调用runtime.execute:779c45a在当时线程 M 上运转 Goroutine；

当时处理器本地的运转行列中不包括 Goroutine 时，调用runtime.findrunnable:779c45a会触发作业盗取，从其它的处理器的行列中随机获取一些 Goroutine。

运转时 G-M-P 模型中引进的处理器 P 是线程和 Goroutine 的中间层，咱们从它的结构体中就能看到处理器与 M 和 G 的联系：

struct P {
	Lock;
	uint32	status;
	P*	link;
	uint32	tick;
	M*	m;
	MCache*	mcache;
	G**	runq;
	int32	runqhead;
	int32	runqtail;
	int32	runqsize;
	G*	gfree;
	int32	gfreecnt;
};

处理器持有一个由可运转的 Goroutine 组成的环形的运转行列runq，还反向持有一个线程。调度器在调度时会从处理器的行列中挑选行列头的 Goroutine 放到线程 M 上履行。

Go语言 — 调度器

依据作业盗取的多线程调度器将每一个线程绑定到了独立的 CPU 上，这些线程会被不同处理器办理，不同的处理器经过作业盗取对使命进行再分配完成使命的平衡，也能提高调度器和 Go 言语程序的全体功用，今日一切的 Go 言语服务都受益于这一改动。

抢占式调度器

对 Go 言语并发模型的修正提高了调度器的功用，可是 1.1 版别中的调度器依然不支撑抢占式调度，程序只能依托 Goroutine 主动让出 CPU 资源才干触发调度。Go 言语的调度器在 1.2 版别中引进依据协作的抢占式调度处理下面的问题：

  • 某些 Goroutine 可以长时刻占用线程，形成其它 Goroutine 的饥饿；
  • 废物收回需求暂停整个程序（Stop-the-world，STW），最长可能需求几分钟的时刻，导致整个程序无法作业；

1.2 版别的抢占式调度尽管可以缓解这个问题，可是它完成的抢占式调度是依据协作的，在之后很长的一段时刻里 Go 言语的调度器都有一些无法被抢占的边际状况，例如：for 循环或者废物收回长时刻占用线程，这些问题中的一部分直到 1.14 才被依据信号的抢占式调度处理。

依据协作的抢占式调度

咱们可以在pkg/runtime/proc.c文件中找到引进依据协作的抢占式调度后的调度器。Go 言语会在分段栈的机制上完成抢占调度，利用编译器在分段栈上刺进的函数，一切 Goroutine 在函数调用时都有机会进入运转时查看是否需求履行抢占。Go 团队经过以下的多个提交完成该特性：

  • runtime: add stackguard0 to G

    • 为 Goroutine 引进stackguard0字段，该字段被设置成StackPreempt意味着当时 Goroutine 宣布了抢占恳求；

  • runtime: introduce preemption function (not used for now)

    • 引进抢占函数runtime.preemptone:1e112cd和runtime.preemptall:1e112cd，这两个函数会改变 Goroutine 的stackguard0字段宣布抢占恳求；
    • 定义抢占恳求StackPreempt；

  • runtime: preempt goroutines for GC

    • 在runtime.stoptheworld:1e112cd中调用runtime.preemptall:1e112cd设置一切处理器上正在运转的 Goroutine 的stackguard0为StackPreempt；
    • 在runtime.newstack:1e112cd中添加抢占的代码，当stackguard0等于StackPreempt时触发调度器抢占让出线程；

  • runtime: preempt long-running goroutines

    • 在体系监控中，假如一个 Goroutine 的运转时刻超越 10ms，就会调用runtime.retake:1e112cd和runtime.preemptone:1e112cd；

  • runtime: more reliable preemption

    • 修正 Goroutine 由于周期性履行非堵塞的 CGO 或者体系调用不会被抢占的问题；

上面的多个提交完成了抢占式调度，可是还短少最要害的一个环节 — 编译器如安在函数调用前刺进函数，咱们能在十分陈旧的提交runtime: stack growth adjustments, cleanup中找到编译器刺进函数的雏形，最新版别的 Go 言语会经过cmd/internal/obj/x86.stacksplit刺进runtime.morestack，该函数可能会调用runtime.newstack触发抢占。从上面的多个提交中，咱们能概括出依据协作的抢占式调度的作业原理：

  1. 编译器会在调用函数前刺进runtime.morestack；
  2. Go 言语运转时会在废物收回暂停程序、体系监控发现 Goroutine 运转超越 10ms 时宣布抢占恳求StackPreempt；
  3. 当发生函数调用时，可能会履行编译器刺进的runtime.morestack，它调用的runtime.newstack会查看 Goroutine 的stackguard0字段是否为StackPreempt；
  4. 假如stackguard0是StackPreempt，就会触发抢占让出当时线程；

这种完成方法尽管添加了运转时的杂乱度，可是完成相对简略，也没有带来过多的额定开支，总体来看仍是比较成功的完成，也在 Go 言语中使用了 10 几个版别。由于这儿的抢占是经过编译器刺进函数完成的，仍是需求函数调用作为进口才干触发抢占，所以这是一种协作式的抢占式调度。

依据信号的抢占式调度

依据协作的抢占式调度尽管完成巧妙，可是并不齐备，咱们能在runtime: non-cooperative goroutine preemption中找到一些遗留问题：

  • runtime: tight loops should be preemptible
  • An empty for{} will block large slice allocation in another goroutine, even with GOMAXPROCS > 1 ?
  • runtime: tight loop hangs process completely after some time
  • …

Go 言语在 1.14 版别中完成了非协作的抢占式调度，在完成的进程中咱们重构已有的逻辑并为 Goroutine 添加新的状况和字段来支撑抢占。Go 团队经过下面的一系列提交完成了这一功用，咱们可以按时刻顺序剖析相关提交了解它的作业原理：

  • runtime: add general suspendG/resumeG

    • 挂起 Goroutine 的进程是在废物收回的栈扫描时完成的，咱们经过runtime.suspendG和runtime.resumeG两个函数重构栈扫描这一进程；
    • 调用runtime.suspendG时会将处于运转状况的 Goroutine 的preemptStop标记成true；
    • 调用runtime.preemptPark可以挂起当时 Goroutine、将其状况更新成_Gpreempted并触发调度器的重新调度，该函数可以交出线程控制权；

  • runtime: asynchronous preemption function for x86

    • 在 x86 架构上添加异步抢占的函数runtime.asyncPreempt和runtime.asyncPreempt2；

  • runtime: use signals to preempt Gs for suspendG

    • 支撑经过向线程发送信号的方法暂停运转的 Goroutine；
    • 在runtime.sighandler函数中注册SIGURG信号的处理函数runtime.doSigPreempt；
    • 完成runtime.preemptM，它可以经过SIGURG信号向线程发送抢占恳求；

  • runtime: implement async scheduler preemption

    • 修正runtime.preemptone函数的完成，加入异步抢占的逻辑；

目前的抢占式调度也只会在废物收回扫描使命时触发，咱们可以梳理一下上述代码完成的抢占式调度进程：

  1. 程序启动时，在runtime.sighandler中注册SIGURG信号的处理函数runtime.doSigPreempt；

  2. 在触发废物收回的栈扫描时会调用runtime.suspendG挂起 Goroutine，该函数会履行下面的逻辑：

    1. 将_Grunning状况的 Goroutine 标记成可以被抢占，即将preemptStop设置成true；
    2. 调用runtime.preemptM触发抢占；

  3. runtime.preemptM会调用runtime.signalM向线程发送信号SIGURG；

  4. 操作体系会中断正在运转的线程并履行预先注册的信号处理函数runtime.doSigPreempt；

  5. runtime.doSigPreempt 函数会处理抢占信号，获取当时的 SP 和 PC 寄存器并调用runtime.sigctxt.pushCall；

  6. runtime.sigctxt.pushCall会修正寄存器并在程序回到用户态时履行runtime.asyncPreempt；

  7. 汇编指令runtime.asyncPreempt会调用运转时函数runtime.asyncPreempt2；

  8. runtime.asyncPreempt2会调用runtime.preemptPark；

  9. runtime.preemptPark会修正当时 Goroutine 的状况到_Gpreempted并调用runtime.schedule让当时函数堕入休眠并让出线程，调度器会挑选其它的 Goroutine 继续履行；

上述 9 个进程展示了依据信号的抢占式调度的履行进程。除了剖析抢占的进程之外，咱们还需求讨论一下抢占信号的挑选，提案依据以下的四个原因挑选SIGURG作为触发异步抢占的信号；

  1. 该信号需求被调试器透传；
  2. 该信号不会被内部的 libc 库使用并阻拦；
  3. 该信号可以随意呈现并且不触发任何结果；
  4. 咱们需求处理多个平台上的不同信号；

STW 和栈扫描是一个可以抢占的安全点（Safe-points），所以 Go 言语会在这儿先加入抢占功用。依据信号的抢占式调度只处理了废物收回和栈扫描时存在的问题，它到目前为止没有处理一切问题，可是这种真抢占式调度是调度器走向齐备的开端，信任在未来咱们会在更多的当地触发抢占。

非均匀内存拜访调度器

非均匀内存拜访（Non-uniform memory access，NUMA）调度器现在只是 Go 言语的提案。该提案的原理就是经过拆分大局资源，让各个处理器可以就近获取，削减锁竞赛并添加数据的局部性。

在目前的运转时中，线程、处理器、网络轮询器、运转行列、大局内存分配器状况、内存分配缓存和废物收集器都是大局资源。运转时没有保证本地化，也不清楚体系的拓扑结构，部分结构可以提供必定的局部性，可是从大局来看没有这种保证。

Go语言 — 调度器

如上图所示，仓库、大局运转行列和线程池会依照 NUMA 节点进行分区，网络轮询器和计时器会由单独的处理器持有。这种方法尽管可以利用局部性提高调度器的功用，可是本身的完成过于杂乱，所以 Go 言语团队还没有着手完成这一提案。

小结

Go 言语的调度器在最初的几个版别中敏捷迭代，可是从 1.2 版别之后调度器就没有太多的变化，直到 1.14 版别引进了真实的抢占式调度才处理了自 1.2 以来一直存在的问题。在可预见的未来，Go 言语的调度器还会进一步演进，添加触发抢占式调度的时刻点以削减存在的边际状况。