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/
