本文節選自 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. 時間片輪轉調度
相關文章