100行代碼實現一個RISC-V架構下的多線程管理框架
1. 摘要
本文將基於RISC-V架構和qemu仿真器實現一個簡單的多線程調度和管理框架, 旨在通過簡單的代碼闡明如何實現線程的上下文保存和切換, 線程的調度並非本文的重點, 故線程調度模塊只是簡單地採用了輪詢的方式.
2. 上下文是什麼
對於一個運行中的程序, 我們可以把它看作一個狀態機, CPU每次執行一條指令會導致這個狀態機從一個狀態轉換到另一個狀態, 而這裡的狀態就是CPU的寄存器值和當前時刻內存的狀態, 即state = (Regs, Mem). 一個程序的執行過程就是狀態機狀態遷移的過程, 如果希望在一個線程執行過程到某條指令時切換到另一個線程, 我們必須額外實現一段代碼去完成這種切換, 並把這段代碼插入到希望的切換點的後面, 這段代碼必須要滿足兩個條件: 1): 能夠正確保存當前線程A的狀態. 我們可以先假設完成這段切換的代碼不存在, 線程A本該執行它的下一條指令, 而在執行下一條指令之前, 線程A有一個確定的狀態, 即CPU的寄存器和內存中的值, 具體來說包括pc指針, 棧寄存器sp, 通用寄存器等以及線程使用到的內存的狀態. 線程切換代碼, 首先必須能夠當前線程A的狀態保存起來, 以便後續調度器再切換回當前的這個線程. 2): 能夠正確恢復被選中的線程B的狀態. 為了切換到另一個線程B去執行, 我們必須從保存線程B狀態的內存地址處讀取線程B的狀態, 然後更新CPU寄存器以及內存的狀態, 更新完成之後就可以繼續線程B被中斷的執行流了. 這裡保存和恢復的線程狀態就是線程的上下文, 在一個線程還沒有運行過的情況下, 我們需要手工構造一個線程的上下文, 這個上下文的作用是使得線程一旦被調度, 就能夠從創建線程時指定的入口地址處執行.
3. 保存上下文
以下都以RISC-V為基礎進行討論. 從線程A的角度看, 當它在自己的正常執行流中調用我們實現的上下文切換代碼時, 只是相當於調用了一個普通函數, 因此編譯器會根據RISC-V架構的ABI約定, 在調用這個函數之前去保存caller saved registers, 即ABI約定中應該由調用者去保存的寄存器, 並且在調用結束之後插入恢復這些寄存器的指令序列, 上下文切換代碼段首先要做的就是保存ABI中約定由被調用者保存的寄存器, 我們可以在表示線程的結構體中開闢一塊區域用來保存這些寄存器, 具體實現可以定義一個描述上下文的結構體, 並在線程結構體中嵌入一個上下文描述結構體.
4. 切換上下文
線程切換代碼段的下一個任務是恢複線程B的狀態到CPU和內存, 只要使用若干load指令去恢複線程B的寄存器狀態即可, 最後使用調用返回指令ret就完成了線程的切換. ret指令會根據ra寄存器的值更新pc寄存器, 從而完成跳轉, 而ra寄存器保存了線程B被中斷的那條指令的地址, 需要注意的是, 在RISC-V架構下, 我們無法通過類似mv這樣的指令直接修改pc寄存器的值.
5. 輪詢調度
線程調度算法並非本文討論重點, 在代碼實現中只簡單定義了一個線程數組, 調度器在調度時依次選擇數組中處於READY狀態的線程去執行, 當沒有線程可調度時, 調度器會自動退出.
6. 代碼實現
代碼部分需要使用RISC-V工具鏈進行編譯, 線程切換代碼使用簡單的彙編指令實現, 調試和運行需要qemu仿真工具, 軟件工具的安裝這裡不進行討論, 詳情可參考相關網絡資源.
6.1 整體流程
進入到main函數之後, 首先創將兩個線程, 然後調用本文實現調度模塊提供的接口對線程列表中的線程進行調度, 直到沒有可供調度的線程.
int main(int argc, char **argv)
{
qthread_create(thread1_start);
qthread_create(thread2_start);
printf("Start to run all threads...\n");
qthread_run_all();
printf("All threads are done!\n");
return 0;
}
兩個線程的入口函數分別為thread1_start和thread2_start, 線程完成的任務如下:
void *thread1_start(void *args)
{
int i = 1;
while (i < 1000)
{
if ((i % 100) == 0)
{
printf("Thread #1: running\n");
qthread_yield();
}
i++;
}
qthread_exit();
return 0;
}
兩個線程的入口函數功能類似, 都會在使用佔用一段時間的CPU之後主動放棄使用權, 任務完成之後主動退出, 通過qemu仿真器可以得到運行結果:
junan@u1:~/Documents/random_coding/01_context_swtch$ qemu-riscv64 -L /usr/riscv64-linux-gnu/ ./main
Start to run all threads...
Thread #1: running
Thread #2: running
Thread #1: running
Thread #2: running
Thread #1: running
Thread #2: running
Thread #1: running
Thread #2: running
Thread #1: running
Thread #2: running
Thread #1: running
Thread #2: running
Thread #1: running
Thread #2: running
Thread #1: running
Thread #2: running
Thread #1: running
Thread #2: running
All threads are done!
6.2 線程調度模塊接口
對於本文實現的線程調度模塊qthread, 其對外的接口包含:
int qthread_create(qthread_entry_t entry);
void qthread_yield();
void qthread_exit();
void qthread_run_all();
分別完成線程的創建, 線程釋放CPU, 線程退出以及線程調度.
6.3 線程描述結構體
為了管理創建出來的線程, 需要一個描述線程的結構體, 記錄線程的id, 調度狀態, 線程上下文等信息. 需要注意的是, 每個線程的運行都需要棧的支持, 這裡在線程結構體中定義了一個1024位元組大小的數組, 用於線程函數運行使用的棧, 在創建線程時, 會手動設置線程上下文中的sp指針的值.
typedef struct
{
uint64 tid;
enum thread_state state;
qthread_entry_t qthread_entry;
char stack[1024];
struct context context;
} qthread_t;
創建線程的接口實現如下:
int qthread_create(qthread_entry_t entry)
{
int index_found = -1;
for (int i = 0; i < MAX_THREADS_NR; ++i)
{
if (qthread_table[i].state == UNUSED)
{
index_found = i;
break;
}
}
if (index_found < 0 || index_found >= MAX_THREADS_NR)
{
return -1;
}
qthread_table[index_found].tid = get_next_tid();
qthread_table[index_found].state = READY;
qthread_table[index_found].qthread_entry = entry;
qthread_table[index_found].context.ra = (uint64)entry;
qthread_table[index_found].context.sp = (uint64)qthread_table[index_found].stack + 1024;
return 0;
}
因為棧的增長方向是由高地址向低地址, 所以線程上下文中的sp指針賦值時需要加上棧的大小, 否則會出現棧溢出的問題.
6.4 上下文描述結構體
對於RISC-V架構, 在進行上下文切換時需要保存ABI約定中callee維護的寄存器外加ra寄存器, 因為ra寄存器記錄了調用完線程切換代碼段對應的函數之後的返回地址, 即線程A被打斷的指令地址. 上下文描述結構體如下:
struct context
{
uint64 ra;
uint64 sp;
uint64 s0;
uint64 s1;
uint64 s2;
uint64 s3;
uint64 s4;
uint64 s5;
uint64 s6;
uint64 s7;
uint64 s8;
uint64 s9;
uint64 s10;
uint64 s11;
};
6.5 線程切換代碼段
如上文所述, 線程切換代碼段需要保存一個上下文, 並恢復另一個上下文, 這部分代碼使用彙編指令去實現:
.section .text
.global swtch
swtch:
sd ra, 0(a0)
sd sp, 8(a0)
sd s0, 16(a0)
sd s1, 24(a0)
sd s2, 32(a0)
sd s3, 40(a0)
sd s4, 48(a0)
sd s5, 56(a0)
sd s6, 64(a0)
sd s7, 72(a0)
sd s8, 80(a0)
sd s9, 88(a0)
sd s10, 96(a0)
sd s11, 104(a0)
ld ra, 0(a1)
ld sp, 8(a1)
ld s0, 16(a1)
ld s1, 24(a1)
ld s2, 32(a1)
ld s3, 40(a1)
ld s4, 48(a1)
ld s5, 56(a1)
ld s6, 64(a1)
ld s7, 72(a1)
ld s8, 80(a1)
ld s9, 88(a1)
ld s10, 96(a1)
ld s11, 104(a1)
ret
代碼的前半部分用於保存上下文, 後半部分用於恢復上下文, 按照ABI約定, 寄存器a0和a1分別用來傳遞函數調用的第一個和第二個參數, 這裡在調用時傳遞的就是兩段保存和恢復各自上下文的內存地址. 最後的ret指令, 會用寄存器ra的值更新寄存器pc, 因為ra已經被恢復成了線程B被中斷的指令地址, 所以ret指令執行過後CPU就會執行線程B對應的代碼. 在恢復上下文時也更新了棧指針寄存器sp, 所以線程B在執行時使用的時自己的棧內存. 線程主動釋放CPU資源時會調用qthread_yield(), 在這個函數中會調用線程切換函數swtch:
void qthread_yield()
{
current->state = READY;
swtch(¤t->context, &qthread_context);
}
對於調用qthread_yield()的線程A來說, 當其內部調用swtch函數時, 實際上CPU已經切換到了另一個線程B去執行, 但線程A是不能感知到的, 當這個swtch函數返回之後, 對線程A來說就像調用了一個普通的函數一樣, 線程A會繼續自己的執行流.
6.6 輪詢調度實現
調度採用輪詢的方式, 每次選取一個可用線程去切換.
void qthread_run_all()
{
int count = 0;
while (1)
{
for (int i = 0; i < MAX_THREADS_NR; ++i)
{
if (qthread_table[i].state == READY)
{
current = &qthread_table[i];
current->state = RUNNING;
count++;
swtch(&qthread_context, ¤t->context);
}
}
if (count == 0)
break;
count = 0;
}
}
7. gdb調試上下文切換
- 首先啟動qemu-riscv64, 指定gdb調試端口:
junan@u1:~/Documents/random_coding/01_context_swtch$ qemu-riscv64 -L /usr/riscv64-linux-gnu/ -g 1234 ./main
- 使用gdb-multiarch連接調試端口, 下發調試命令:
junan@u1:~/Documents/random_coding/01_context_swtch$ gdb-multiarch main
GNU gdb (Ubuntu 12.0.90-0ubuntu1) 12.0.90
Copyright (C) 2022 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <//gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<//www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<//www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from main...
(gdb) target remote :1234
調用swtch之前各個寄存器的狀態如下:
此時正在運行的是線程1, 即將進入swtch函數, 在swtch函數執行過程中寄存器的狀態如下:
可以看到在swtch函數中, ret指令執行之前, ra寄存器的值保存的是調度函數qthread_run_all()中某條指令的地址, 因此ret執行完之後CPU首先跳轉到調度函數, 調度函數接着被中斷的循環繼續運行, 並從線程列表中選取下一個READY狀態的線程, 然後再使用swtch函數切換到被選中的線程, 同時把自己的上下文保存到一個全局的上下文處. 即用戶線程的切換需要依賴調度函數qthread_run_all, 線程釋放CPU時會先切換到qthread_run_all的上下文, 然後由這個調度器去選取下一個應該運行的線程並進行切換.
8. 總結
本文使用儘可能簡單的代碼闡述了上下文切換的原理. 個人認為簡單的情況更有利於理解一項技術背後的原理, 當然, 文中講述的上下文切換不僅能夠用來實現一個demo. 設想以下, 當一個用戶進程通過一個系統調用進入到內核態時, 假如這個syscall想訪問某個此時不可用硬件資源, 那麼內核通常情況下需要將當前的這個進程休眠, 即需要調度器選擇另一個可用進程佔據當前的這個CPU, 這裡同樣需要進行上下文切換. 內核需要保存即將休眠的進程在內核態中的上下文, 然後切換到調度器, 再由調度器去完成進程調度並切換到被選中的進程. 實際上這個過程涉及到的技術原理和本文討論的內容時一致的. 對於用戶態切換到內核態的上下文保存後續文章會展開討論.
本文的完整代碼鏈接如下: //github.com/kfggww/random_coding/tree/main/01_context_swtch, 歡迎”一鍵三連” 😛, 代碼實現或者文中表述若有不妥之處還清批評指正.
9. 參考資源
[1] //riscv.org/technical/specifications/
[2] //pdos.csail.mit.edu/6.S081/2021/
