本文节选自 Allen 在 GitChat 的分享

Allen

前言

一直以来，我们学习线程切换与调度，都是通过阅读操作系统书籍或 Linux 源码甚至反汇编 Window 内核代码。无论怎样，这些东西都很抽象，学习起来十分困难。另外，随着现代化编程语言逐渐流行，C++20 的正式发布，都离不开用户态线程这些基础知识。再比如 Golang 的 Goroutine，腾讯公司的开源的 libco，百度的 BRPC 中的 bhtread，如果想深刻理解它们，都需要扎实的基本功。

本文会带你循序渐近的掌握下面的知识点：

  • 控制流切换原理
  • 上下文切换
  • 线程设计
  • 调度函数的封装与代码模块化
  • 线程的主动切换
  • 时间片轮转调度

本文实验环境：

  • ubuntu 16.04 32 位操作系统（读者请务必提前安装好）；
  • 挑选一个你自己觉得好用的虚拟机软件，比如 VMWare；
  • 请把你的虚拟机环境配置成单核 CPU。

学习时间：大于 5 小时

为什么使用 32 位系统？因为方便初学者学习，能更快速的掌握原理。

最终我们实验完成的效果应该是下面这个样子，动态图地址：

https://images.gitbook.cn/ad977030-47b0-11e9-b53a-b750340c4d0d

图1 用户态线程运行示例

需要注意的是，上面的代码，并没有使用操作系统为我们提供的 pthread系列函数，thread_create和 thread_join函数都是自己纯手工实现的。唯一使用操作系统的函数就是设置时钟，因此会有时钟信号产生，这一步是为了模拟时间片轮转算法而做的。

下面是图1 中的 demo 示例代码：

#include<stdio.h>

#include<stdlib.h>

#include"thread.h"

voidfun1(){

inti = 10;

while(i--) {

printf("hello, I'm fun1n");

mysleep(2);

}

}

voidfun2(){

inti = 10;

while(i--) {

printf("hello, I'm fun2n");

mysleep(1);

}

}

voidfun3(){

inti = 2;

while(i--) {

printf("hello, I'm fun3n");

mysleep(5);

}

}

voidfun4(){

inti = 15;

intm;

intn;

while(i--) {

printf("hello, I'm fun4n");

for(m = 0; m < 10000; ++m)

for(n = 0; n < 10000; ++n);

}

}

intmain(){

inttid1, tid2, tid3, tid4;

thread_create(&tid1, fun1);

printf("create thread %dn", tid1);

thread_create(&tid2, fun2);

printf("create thread %dn", tid2);

thread_create(&tid3, fun3);

printf("create thread %dn", tid3);

thread_create(&tid4, fun4);

printf("create thread %dn", tid4);

inti = 2;

while(i--) {

printf("hello, I'm mainn");

mysleep(3);

}

thread_join(tid1);

thread_join(tid2);

thread_join(tid3);

thread_join(tid4);

return0;

}

控制流切换原理

控制流，指的是一系列按顺序执行的指令。多控制流，是指存在两个或两个以上可以并发（宏观同时，微观不同时）执行的指令序列。比如你编写的多线程程序，每个线程就可以看成是一个控制流，多个线程允许多个控制流一起执行。

在我们学习编程的时候，如果不借助操作系统提供的线程框架，几乎无法完成多控制流的运行的。

接下来先来剖析一下，我们的指令如何”莫名奇妙“的就切换到其它线程的。

1.1 指令执行

不管你用的是什么语言编程，最后都要落实到 CPU 上，而 CPU 只认识它自己的语言，机器语言。机器语言可以抽象出对应 CPU 架构的汇编指令。如下面的 x86 指令序列。

//...

mov eax, 5

push eax

call 0x00401020

add 0x4

//...

程序在执行时，实际上就是汇编指令（准确的说是机器指令）在 CPU 上一条一条执行。对于单核CPU 来说，永远只有一条控制流，也就是只有一条指令序列。所以，宏观上模拟的多线程程序，本质上还只是单控制流，所谓的多线程，只不过是一种被制造出来的假像！

注：有部分同学没有接触过汇编指令，不要害怕，我们用到的汇编不会太难！

1.2 控制流切换(x86 CPU 架构)

汇编指令在执行的时候，最重要地方在于它需要依赖 CPU 环境：

  • 一套通用寄存器 (eax、edx、ecx、ebx、esp、ebp、esi、edi)；
  • 标志寄存器 eflags；
  • 指令寄存器 eip (eip 用来保存下一条要被指令的地址)。

如果你不理解 CPU 寄存器是什么意思，把它想象成它是 CPU 中预先定义好的变量。

还有一个很重要环境，就是栈。因为指令序列在执行时，经常会保存一些临时数据，比如某条指令的地址。当指令执行 ret 指令的时候，CPU 会从当前栈顶弹出一个值到 eip 寄存器！这意味着要发生跳转了！

通用寄存器中，有一个寄存器名为 esp，它保存的是栈顶指针(内存地址的值)。指令 push 、 pop、call、ret 都依赖于 esp 工作。

  • call 指令把它后面的指令地址保存到 esp 指向的内存单元，同时修改 eip。如 call 0x2000，先把 call 0x2000 的下一条指令地址压栈，同时修改 eip 为 0x2000。
  • ret 指令把 esp 指向的内存单元中的值保存到 eip。
  • push 指令把值保存到 esp 指向的内存单元。
  • pop 把 esp 指向的内存单元的值取出。

图2 CPU 寄存器 esp 与内存单元的关系，右侧表示运行栈

想象一下，如果某个时候，我们把 esp 保存的数据 “偷偷” 换了，换句话说我们是把栈换了，而栈中保存的那个“某条指令”的地址的值也不一样了，将会发生什么？图3 把 esp 的值从 0xFFE8 更改成了 0x1FFE8。

图3 切换 esp 即切换栈

所谓的切换控制流，无非就是更改 esp 栈顶指针来做到偷梁换柱的把戏而已。只不过，为了做到惟妙惟肖，我们在更改 esp 的时候，还得顺带的把通用寄存器环境修改修改，以适应新的那段“某条指令”的执行环境。（注意，栈中经常会保存某条指令的地址，比如函数的返回地址。）

通常，这段新的“某条指令”的执行环境，恰好也保存在栈里，就像上图中 esp 到“某条指令地址”之间那段内存的数据（五颜六色的那部分数据）。

说了这么多很抽象，我们来一个具体的例子。简单讲解一下，更改栈中保存“某条指令地址”的后果。

// test.c

// 编译方式：gcc test.c -fno-stack-protector

#include<unistd.h>

#include<stdio.h>

voidfun(){

while(1) {

printf("Hello, I'm fun!n");

sleep(1);

}

}

intmain(){

inta[5] = { 0};

// 传说中的溢出攻击

a[5] = (int)fun;

a[6] = (int)fun;

a[7] = (int)fun;

return0;

}

编译和运行：

$gcc test.c -fno-stack-protector

$./a.out

图4 溢出攻击

这段代码非常短，但却很典型。让我们来看看到底是怎么回事。图 5 左侧是 test.c 程序编译成汇编指令的结果。

编译方法：

$gcc -S test.c -fno-stack-protector

注：-fno-stack-protector 是为了防止编译器插入栈保护检查代码。

图5 溢出攻击指令分析

为了方便看结果，我已经删除了部分影响“视觉效果”的代码。可以看到后面的越界赋值导致蓝色框框中的数据被破坏，导致“某条指令地址”(实际上是 main 函数的返回地址)被更改为 fun 函数地址，也就是图 5 中汇编第 4 行指令 pushl %ebp这条指令的地址。

当指令执行到第 34 行的 ret时，栈是下面的样子：

图6 执行到 ret 指令时栈的“容貌”

ret指令等价于 pop eip，也就是把栈顶的值送入 eip 寄存器。于是，程序就跳转到了 fun函数中执行，形成图 4 中的效果。

如果你阅读上面的执行流程感觉困难，建议你先读一读有关函数执行流程的知识，在文章《打造自己的 longjmp》中有很详细的介绍，推荐你阅读。

1.3 再论控制流切换

在你彻底明白“溢出攻击”实验的原理后，我们换个思路，不修改栈的内容，而是直接换一个栈，本质上也就是换 esp 的值，能不能达到相同的效果？比方说，新的栈里的内容，是我事先构造好的。再看一个实验。

// test2.c

// 编译方式：gcc test2.c

#include<unistd.h>

#include<stdio.h>

voidfun(){

while(1) {

printf("Hello, I'm fun!n");

sleep(1);

}

}

intmain(){

intstack[64] = {0};

stack[63] = (int)fun;

// 新栈的栈顶指针

intnew_esp = (int)(stack+63);

__asm__ (

"mov %0, %%espnt"

"retnt"

::"m"(new_esp));

/* 上面的这段内联汇编翻译成 x86 汇编是这样的：

mov esp, new_esp 切换栈顶指针

ret 返回

*/

return0;

}

编译和运行:

$gcc test2.c

$./a.out

执行效果和图 4 中是一模一样的。

图7 手工修改 esp

这个实验和“溢出攻击实验”区别就是不再修改栈内容，而是使用我们自己构造的新栈，以达到相同的控制流切换的效果。这里就不再画栈的样子了，留给读者自己分析。

话说回来，这个真的是控制流“切换”吗，只是看起来像而已，本质上它只是个跳转。

上下文切换

当你完全明白了第 1 节的内容后，现在我们尝试一些新的东西。否则继续往后阅读你可能会有些吃力。

在上一小节中已经用 C 语言和汇编分别完成了两个小实验，告诉你如何通过更改栈来达到控制流转向你所期望的目的地。不过，这只是切换出去，要完成线程调度，最关键的一点在于还得切换回来。

2.1 上下文切换原理

上下文切换不同于第 1 节所述的暴力切换，因为在那个实验里，我们永远无法重新返回到main函数中。如果你想从那个fun函数再跳回目的地，我们需要在切换控制流前保存当前寄存器环境，以及当前的栈顶位置。

上面那段话是说，当我们什么时候想切换回来的时候，只要更改一下栈（这个你已经学会了）同时在恢复寄存器环境，看起来就好像从以前切出去的那个位置继续执行。

2.2 保存寄存器环境

有很多种手段保存寄存器环境，最简单的一种就是保存到定义好结构体去。假设我们有 3 个线程，那就需要 3 结构体变量，分别保存自己的寄存器环境。

structcontext{

inteax;

intedx;

intecx;

intebx;

intesp;

intebp;

intesi;

intedi;

inteflags;

}

三个线程对应的结构体数组是 struct context ctx[3]。当我们从线程 0 切换到线程 1 的时候，我们就将线程 0 当前的寄存器环境保存到 ctx[0] 里去。什么时候我们重新切换回线程 0 的时候，再把 ctx[0] 中的值恢复到所有寄存器中。

图8 从 “线程0” 切换到 “线程1”

上面的过程用汇编很容易实现，不过在实际的实现版本中，没有采用这种方法，而是使用了更加简洁的方法——将当前寄存器的环境保存在当前所使用的栈中。具体过程见图 9。

图9 从 “线程0” 切换到 “线程1”

图 9 中的步骤可以叙述为下：

  • 线程 0 （请允许我称此为线程吧）正准备切换时，将当前 CPU 中的寄存器环境一个一个压入到自己的栈中，最后一个压栈的是 eflags 寄存器；
  • 线程 0 将自己的栈顶指针（保存 eflags 的那个位置）保存到全局数组 task[0] 中；
  • 线程 0 从全局数据 task 中取出下一个线程的栈顶，假设下一个要运行的线程是 1 号线程，则从 task[1] 中取出线程 1 的栈顶指针保存到 CPU 的 esp 寄存器中。此时意味着栈已经被切换。栈切换完成后，本质上已经在线程 1 中了；
  • 线程 1 将自己栈中的寄存器环境 pop 到对应的 CPU 寄存器中，比如第一个 pop 到 eflags 中，最后一个是 pop ebp。
2.3 上下文切换实验

你需要创建两个文件，分别是 main.c 和 switch.s。

// main.c

#include<unistd.h> // for sleep

#include<stdio.h>

inttask[3] = {0, 0, 0}; // for esp

intcur = 0; // current esp

voidswitch_to(intn); // 定义在 switch.s 中

voidfun1(){

while(1) {

printf("hello, I'm fun1n");

sleep(1);

// 强制切换到线程 2

switch_to(2);

}

}

voidfun2(){

while(1) {

printf("hello, I'm fun2n");

sleep(1);

// 强制切换到线程 1

switch_to(1);

}

}

// 线程启动函数

voidstart(intn){

if(n == 1) fun1();

elseif(n == 2) fun2();

}

intmain(){

intstack1[1024] = {0};

intstack2[1024] = {0};

task[1] = (int)(stack1+1013);

task[2] = (int)(stack2+1013);

// 创建 fun1 线程

// 初始 switch_to 函数栈帧

stack1[1013] = 7; // eflags

stack1[1014] = 6; // eax

stack1[1015] = 5; // edx

stack1[1016] = 4; // ecx

stack1[1017] = 3; // ebx

stack1[1018] = 2; // esi

stack1[1019] = 1; // edi

stack1[1020] = 0; // old ebp

stack1[1021] = (int)start; // ret to start

// start 函数栈帧，刚进入 start 函数的样子

stack1[1022] = 100;// ret to unknown，如果 start 执行结束，表明线程结束

stack1[1023] = 1; // start 的参数

// 创建 fun2 线程

// 初始 switch_to 函数栈帧

stack2[1013] = 7; // eflags

stack2[1014] = 6; // eax

stack2[1015] = 5; // edx

stack2[1016] = 4; // ecx

stack2[1017] = 3; // ebx

stack2[1018] = 2; // esi

stack2[1019] = 1; // edi

stack2[1020] = 0; // old ebp

stack2[1021] = (int)start; // ret to start

// start 函数栈帧，刚进入 start 函数的样子

stack2[1022] = 100;// ret to unknown，如果 start 执行结束，表明线程结束

stack2[1023] = 2; // start 的参数

switch_to(1);

}

// switch.s

/*void switch_to(int n)*/

.section .text

.global switch_to // 导出函数 switch_to

switch_to:

push %ebp

mov %esp, %ebp /* 更改栈帧，以便寻参 */

/* 保存现场 */

push %edi

push %esi

push %ebx

push %edx

push %ecx

push %eax

pushfl

/* 准备切换栈 */

mov cur, %eax /* 保存当前 esp */

mov %esp, task(,%eax,4)

mov 8(%ebp), %eax /* 取下一个线程 id */

mov %eax, cur /* 将 cur 重置为下一个线程 id */

mov task(,%eax,4), %esp /* 切换到下一个线程的栈 */

/* 恢复现场, 到这里，已经进入另一个线程环境了，本质是 esp 改变 */

popfl

popl %eax

popl %edx

popl %ecx

popl %ebx

popl %esi

popl %edi

popl %ebp

ret

图10 上下文切换实例运行结果，动态图地址https://images.gitbook.cn/5ef27c30-47c5-11e9-9afc-37690262ac34

2.4 程序分析

实验的难点在于第一次切换到另一个线程时，那个线程的上下文并不存在。所以在 main 函数中，我们要事先构造出要被切换的那些线程的上下文。

特别注意的是，为了方便管理所有的线程回调函数 fun1 和 fun2，这里借助了一个 start 函数来统一管理它们，这样一来，每次构造环境的代码就可以统一起来。窍门在于 main 函数中的初始环境的构造。以 fun1 为例。

// 创建 fun1 线程

// 初始 switch_to 函数栈帧

stack1[1013] = 7; // eflags

stack1[1014] = 6; // eax

stack1[1015] = 5; // edx

stack1[1016] = 4; // ecx

stack1[1017] = 3; // ebx

stack1[1018] = 2; // esi

stack1[1019] = 1; // edi

stack1[1020] = 0; // old ebp

stack1[1021] = (int)start; // ret to start

// start 函数栈帧，刚进入 start 函数的样子

stack1[1022] = 100;// ret to unknown，如果 start 执行结束，表明线程结束

stack1[1023] = 1; // start 的参数

图11 构造线程 1 的运行栈的样子

为什么要填充 0~7 这些数字呢？其实这些数据本身并没有意义，单纯的只是为了调试方便。

当 main 函数执行到switch_to(1)的时候，注意进入switch_to里面时，switch_to的前半段（图 12 中第 6 行到 第 22 行），使用的栈都还是主线程的栈，第 6 行到第 16 行将当前寄存器环境保存到主线程的自己的栈中，如图 11 中右侧的栈。

图12 switch.s 代码

第 19 到第 23 行，相当于：

eax = cur; // cur 是全局变量，保存当前“线程” id

task[eax] = esp; // mov %esp, task(,%eax,4)

eax = n; // n 是 switch_to 函数的参数，保存在 8(%ebp) 这个位置

cur = eax;

esp = task[cur]; // mov task(,%eax,4), %esp

执行图 12 中的第 23 行时，正是栈的切换操作，这一行执行完成后，当前运行栈就变成了图 11 中左侧的栈。接下来的 26 开始，就已经算是进入了另一个“线程”了。

很奇妙吧，一个switch_to函数竟然同时跨越了 2 个“线程”，其本质就是栈变了。

从 26 行开始，一连串的 pop 动作将栈中的值弹到 cpu 寄存器中。我们在构造的时候，只是随便填了一些值，因为这并不会有任何影响，你继续跟踪代码就知道了。switch_to函数执行到ret指令的时候，esp这个时候指向的是stack1[1021]这个位置，一旦ret，就进入了 start 函数，这个技巧在上一篇文章你早已学会。

后文中还将带你循序渐近的掌握下面的知识点：

  1. 线程设计
  2. 调度函数的封装与代码模块化
  3. 线程的主动切换
  4. 时间片轮转调度
相关文章