從0開始的操作系統手搓教程21：進程子系統的一個核心功能—

具體說說我們的簡單RR調度

處理時鐘中斷處理函數

調度器 schedule

switch_to

我們下面，就要開始真正的進程切換了。在那之前，筆者想要說的是——我們實現的進程切換簡單的無法再簡單了——也就是實現一個超級簡單的輪詢調度器。

每一個進程按照一個priority作為一個擁有時間的開始，然后，我們的調度器就分配給這個進程priority個時間片，每一次時鐘中斷發生的時候，我們當前的進程就發生時間片剝奪減少一次，當我們的運行的elapsed_ticks的值達到了priority，也就是我們預計分配的時間片的時候，剝奪這個進程的運行資格給下一個進程。很簡單吧！

所以，我們需要讓進程們按照一個隊列組織起來，這樣才方便管理。是的，我們就按照一個最好想到的——時不時就會發生動態的插入刪除的一個經典數據結構，也就是我們之前搓的一個重要的數據結構：雙向鏈表。這里筆者就不重復談論這個玩意了。遺忘的朋友就自行到筆者的第六章中稍微查找一下吧！

我們看看我們新Task Struct長啥樣。

/*** @brief Task control block structure.** This structure represents a thread and stores its execution context.*/
typedef struct __cctaskstruct
{uint32_t *self_kstack; ? ? ? ? // Kernel stack pointer for the threadTaskStatus status; ? ? ? ? ? ? // Current status of the threadchar name[TASK_NAME_ARRAY_SZ]; // Thread nameuint8_t priority; ? ? ? ? ? ? ?// Thread priority leveluint8_t ticks;uint32_t elapsed_ticks;list_elem general_tag;list_elem all_list_tag;uint32_t *pg_dir;uint32_t stack_magic; // Magic value for stack overflow detection
} TaskStruct;

很顯然，我們多了elapsed_ticks，ticks和priority三個作為一組變量，這個是用來衡量線程的處理器時間的。

它是任務每次被調度到處理器上執行的時間嘀嗒數，也就是我們所說的任務的時間片，每次時鐘中斷都會將當前任務的 ticks 減1，當減到0 時就被換下處理器。 ticks 和上面的 priority 要配合使用。priority 表示任務的優先級，咱們這里優先級體現在任務執行的時間片上，即優先級越高，每次任務被調度上處理器后執行的時間片就越長。當 ticks 遞減為 0 時，就要被時間中斷處理程序和調度器換下處理器，調度器把 priority 重新賦值給 ticks，這樣當此線程下一次又被調度時，將再次在處理器上運行 ticks 個時間片。 elapsed_ticks 用于記錄任務在處理器上運行的時鐘嘀嗒數，從開始執行，到運行結束所經歷的總時鐘數。

下面多的兩個，是general_tag和all_list_tag。當線程被加入到就緒隊列thread_ready_list 或其他等待隊列中時，我們的general_tag就會發揮作用，剩下的一個all_list_tag是一個完全被加到了所有的全局的線程管理隊列中的。

另一個多的新東西是任務自己的頁表，pg_dir成員。線程與進程的最大區別就是進程獨享自己的地址空間，即進程有自己的頁，而線程共享所在進程的地址空間，即線程無頁表。如果該任務為線程，那么我們的pg_dir則為 NULL，這個時候我們就找共享的那部分頁表。否則就是頁表的虛擬地址。

好了，讓我們看看實現吧。我們會在實現的地方上，好好聊聊。

static TaskStruct *main_thread;
static list_elem *thread_tag;
list thread_ready_list;
list thread_all_list;
?
extern void switch_to(TaskStruct *cur, TaskStruct *next);

TaskStruct* main_thread是定義主線程的PCB，咱們進入內核后一直執行的是main 函數，其實它就是一個線程，我們在后面會將其完善成線程的結構，因此為其先定義了個PCB。

調度器要選擇某個線程上處理器運行的話，必然要先將所有線程收集到某個地方，這個地方就是線程就緒隊列。list thread_ready_list便是就緒隊列，以后每創建一個線程就將其加到此隊列中。

就緒隊列中的線程都是可用于直接上處理器運行的，可有時候線程因為某些原因阻塞了，不能放在就緒隊列中，但我們得有個地方能找到它，得知道我們共創建了多少線程，為此我們創建了所有（全部）線程隊列，也就是 thread_all_list。

很好，下面，我們開始梭哈新東西：首先是一個叫做current_thread函數，如你所見，current_thread是一個迫真含義的返回當前線程的PCB地址的。

TaskStruct *current_thread(void)
{uint32_t esp;asm volatile("mov %%esp, %0" : "=g"(esp));return (TaskStruct*)(esp & PG_FETCH_OFFSET);
}

PG_FETCH_OFFSET是筆者在memory文件夾下建立的一個叫做memory_settings.h中的一個定義。這個意味著是取出來頁表轉換的部分的高20位，如你所見：

#define PG_FETCH_OFFSET ? ? (0xfffff000)

這個函數是咋做的呢？顯然，我們要準備獲取的是當前的內核棧的PCB地址，咋做的呢？我們知道，PCB是被安排在了一個頁的頁首，那么，直接將當前頁的頁首取出來不久完事了？esp & PG_FETCH_OFFSET就是在做這個事情！

kernel_thread別看只添加了一行，實際上變化非常大。我們這里強迫中斷在線程調度之后是必須開啟的。因為我們的任務調度機制基于時鐘中斷，由時鐘中斷這種“不可抗力”來中斷所有任務的執行，借此將控制權交到內核手中，由內核的任務調度器 schedule考慮將處理器使用權發放到某個任務的手中，下次中斷再發生時，權利將再被回收，周而復始，這樣便保證操作系統不會被“架空”，而且保證所有任務都有運行的機會。

static void kernel_thread(TaskFunction function, void *func_arg)
{set_intr_status(INTR_ON);function(func_arg);
}

下面這個函數，就是將我們的main函數入正了！

static void make_main_thread(void)
{main_thread = current_thread();init_thread(main_thread, "main", 31);KERNEL_ASSERT(!elem_find(&thread_all_list, &main_thread->all_list_tag));list_append(&thread_all_list, &main_thread->all_list_tag);
}

首先，我們在Loader中，設置了0xc009f000作為我們的ESP，然后分配好了頁之后，顯然，求得的PCB的地址位于頁首也就是0xc009e000（牢記我們的內核棧始終在頁首上！）

下一步就是init_thread，初始化我們的成員變量，這個沒啥好說的。KERNEL_ASSERT(!elem_find(&thread_all_list, &main_thread->all_list_tag));是一個例行判斷，檢測一下我們當前的main_thread不應該出現在thread_all_list里，因為我們還沒添加呢！

void init_thread(TaskStruct *pthread, char *name, int priority)
{k_memset(pthread, 0, sizeof(TaskStruct));k_strcpy(pthread->name, name);
?if (pthread == main_thread){pthread->status = TASK_RUNNING;}else{pthread->status = TASK_READY;}
?pthread->priority = priority;pthread->ticks = priority;pthread->elapsed_ticks = 0;pthread->pg_dir = NULL;pthread->self_kstack = (uint32_t *)((uint32_t)pthread + PG_SIZE);pthread->stack_magic = TASK_MAGIC;
}

看到main_thread特化了嘛，因為我們是需要對當前線程也歸納到init_thread初始化中，我們選擇了對main_thread搞特殊——因為他已經在事實上運行了。所以是TASK_RUNNING。

TaskStruct *thread_start(char *name, int priority,TaskFunction function, void *func_arg)
{TaskStruct *thread = get_kernel_pages(PCB_SZ_PG_CNT);init_thread(thread, name, priority);create_thread(thread, function, func_arg);KERNEL_ASSERT(!elem_find(&thread_ready_list, &thread->general_tag));list_append(&thread_ready_list, &thread->general_tag);KERNEL_ASSERT(!elem_find(&thread_all_list, &thread->all_list_tag));list_append(&thread_all_list, &thread->all_list_tag);return thread;
}

thread_start函數封裝了這一系列流程，同時安排線程/進程進入我們的鏈表中，就像這樣了：

具體說說我們的簡單RR調度

調度器是從就緒隊列 thread_ready_list 中“取出”上處理器運行的線程，所有待執行的線程都在 thread_ready_list 中，我們的調度機制很簡單，就是 Round-Robin Scheduling，俗稱 RR，即輪詢調度，說白了就是讓候選線程按順序一個一個地執行，咱們就是按先進先出的順序始終調度隊頭的線程。注意，這里說的是“取出”，也就是從隊列中彈出，意思是說隊頭的線程被選中后，其結點不會再從就緒隊列 thread_ready_list 中保存，因此，按照先入先出的順序，位于隊頭的線程永遠是下一個上處理器運行的線程。

就緒隊列 thread_ready_list 中的線程都屬于運行條件已具備，但還在等待被調度運行的線程，因此 thread_ready_list 中的線程的狀態都是TASK_READY。而當前運行線程的狀態為 TASK_RUNNING，它僅保存在全部隊列 thread_all_list 當中。

調度器 schedule 并不僅由時鐘中斷處理程序來調用，它還有被其他函數調用的情況，比如后面要說的函數 thread_block。

因此，在 schedule 中要判斷當前線程是出于什么原因才“淪落到”要被換下處理器的地步。是線程的時間片到期了？還是線程時間片未到，但它被阻塞了，以至于不得不換下處理器？其實這就是查看線程的狀態，如果線程的狀態為 TASK_RUNNING，這說明時間片到期了，將其 ticks 重新賦值為它的優先級 prio，將其狀態由TASK_RUNNING 置為TASK_READY，并將其加入到就緒隊列的末尾。如果狀態為其他，這不需要任何操作，因為調度器是從就緒隊列中取出下一個線程，而當前運行的線程并不在就緒隊列中。

調度器按照隊列先進先出的順序，把就緒隊列中的第1 個結點作為下一個要運行的新線程，將該線程的狀態置為TASK_RUNNING，之后通過函數switch_to 將新線程的寄存器環境恢復，這樣新線程便開始執行。因此，完整的調度過程需要三部分的配合。

時鐘中斷處理函數。
調度器 schedule。
任務切換函數 switch_to。

這樣看，我們就來活了。

處理時鐘中斷處理函數

第一步，稍微優化一下我們的通用處理/

// Function to set up a default callback for exception interrupts
static void __def_exception_callback(uint8_t nvec)
{if (nvec == 0x27 || nvec == 0x2f){ // Ignore certain interruptsreturn;}ccos_puts("\n\n");ccos_puts("----------- Exceptions occurs! ---------------\n");ccos_puts("Man! Exception Occurs! :\n");ccos_puts(interrupt_name[nvec]); // Display the name of the interruptccos_puts("\nSee this fuck shit by debugging your code!\n");if (nvec ==PAGE_FAULT_NUM){ // If it's a page fault, print the missing addressint page_fault_vaddr = 0;asm("movl %%cr2, %0": "=r"(page_fault_vaddr)); // CR2 holds the address causing the page// faultccos_puts("And this is sweety fuckingly page fault, happened with addr is 0x");__ccos_display_int(page_fault_vaddr);ccos_puts("\n\n");}ccos_puts("----------- Exceptions Message End! ---------------\n");
?// Once inside the interrupt handler, the interrupt is disabled,// so the following infinite loop cannot be interrupted.while (1);
}

排除掉之前就說過的偽異常，我們還加進了 Pagefault 的處理。Pagefault 就是通常所說的缺頁異常，它表示虛擬地址對應的物理地址不存在，也就是虛擬地址尚未在頁表中分配物理頁，這樣會導致 Pagefault 異常。導致 Pagefault 的虛擬地址會被存放到控制寄存器 CR2 中，我們加入的內聯匯編代碼就是讓 Pagefault 發生時，將寄存器 cr2 中的值轉儲到整型變量page_fault_vaddr 中，并通過put_str 函數打印出來。因此，如果程序運行過程中出現異常 Pagefault 時，將會打印出導致 Pagefault 出現的虛擬地址。

之后呢，我們會為每一個獨特含義的中斷專門注冊異常，這就是為什么筆者叫他：__def_exception_callback函數。

/* Timer interrupt handler */
static void intr_timer_handler(void) {TaskStruct *cur_thread = current_thread();
?KERNEL_ASSERT(cur_thread->stack_magic == TASK_MAGIC); // Check for stack overflow
?cur_thread->elapsed_ticks++; // Record the CPU time consumed by this threadticks++; // Total ticks since the first kernel timer interrupt, including both kernel and user mode
?if (cur_thread->ticks == 0) { // If the process time slice is exhausted, schedule a new processschedule();} else { // Decrease the remaining time slice of the current processcur_thread->ticks--;}
}
?
/*** init_system_timer initializes the system timer (PIT8253)* This function sets up the timer and configures counter 0 with the appropriate settings.*/
void init_system_timer(void)
{// Print message indicating the timer is being initializedverbose_ccputs(" ? timer is initing...\n");
?// Configure the timer's counter 0 with appropriate settings// The function frequency_set will configure the counter 0 port, set the mode,// and initialize it with the value defined in COUNTER0_VALUE.frequency_set(CONTRER0_PORT, COUNTER0_NO, READ_WRITE_LATCH, COUNTER_MODE, COUNTER0_VALUE);register_intr_handler(SCHED_INTERRUPT_CALLBACK_N, intr_timer_handler);// Print message indicating the timer has been successfully initializedverbose_ccputs(" ? timer is initing! done!\n");
}
?

很簡單吧，就是如此！我們定期檢查一下棧有沒有出問題。然后更新一下ticks。如果觸發了cur_thread->ticks沒了，那就是到點嘗試切換了。

調度器 schedule

/* Task scheduling function */
void schedule(void)
{KERNEL_ASSERT(get_intr_status() == INTR_OFF);
?TaskStruct *cur = current_thread(); // Get the current running threadif (cur->status == TASK_RUNNING){ // If the current thread is still runningKERNEL_ASSERT(!elem_find(&thread_ready_list, &cur->general_tag));list_append(&thread_ready_list,&cur->general_tag); // Add it to the ready listcur->ticks =cur->priority; ? ? ? ?// Reset the thread's ticks based on prioritycur->status = TASK_READY; // Set the thread status to ready}
?KERNEL_ASSERT(!list_empty(&thread_ready_list));thread_tag = NULL; // Clear the thread_tag/* Pop the first thread from the ready list to schedule */thread_tag = list_pop(&thread_ready_list);TaskStruct *next = elem2entry(TaskStruct, general_tag, thread_tag);next->status = TASK_RUNNING;
?switch_to(cur, next); // Switch to the next thread
}

我們檢查一下：有沒有關中斷，不然的話多少有點危險，這樣調度本身會被打斷，不知道跑哪里去了。接下來分兩種情況來考慮，如果當前線程 cur 的時間片到期了，就將其通過 list_append 函數重新加入到就緒隊列 thread_ready_list。由于此時它的時間片 ticks 已經為 0，為了下次運行時不至于馬上被換下處理器，將 ticks 的值再次賦值為它的優先級 prio，最后將 cur 的狀態 status 置為 TASK_READY。

如果當前線程 cur 并不是因為時間片到期而被換下處理器，肯定是由于某種原因被阻塞了（比如對 0 值的信號量進行 P 操作就會讓線程阻塞，到同步機制時會介紹），這時候不需要處理就緒隊列，因為當前運行線程并不在就緒隊列中，咱們下面來看當前運行的線程是如何從就緒隊列中“出隊”的。

我們尚未實現idle 線程，因此有可能就緒隊列為空，為避免這種無線程可調度的情況，暫時用“KERNEL_ASSERT(!list_empty(&thread_ready_list))”來保障。

接下來通過“thread_tag = list_pop(&thread_ready_list)”從就緒隊列中彈出一個可用線程并存入thread_tag。

注意，thread_tag 并不是線程，它僅僅是線程PCB 中的general_tag 或all_list_tag，要獲得線程的信息，必須將其轉換成PCB 才行，因此我們用到了宏elem2entry

// Macro to calculate the offset of a member within a struct type
#define offset(struct_type, member) (int)(&((struct_type *)0)->member)
?
// Macro to convert an element pointer to the corresponding struct type pointer
#define elem2entry(struct_type, struct_member_name, elem_ptr) \(struct_type *)((int)elem_ptr - offset(struct_type, struct_member_name))

在這呢，之前就說過了。貼過來看一眼而已。通過 elem2entry 獲得了新線程的 PCB 地址，將其賦值給 next，緊接著通過“next-> status = TASK_RUNNING”將新線程的狀態置為 TASK_RUNNING，這表示新線程next 可以上處理器了，于是準備切換寄存器映像，這是通過調用 switch_to 函數完成的，調用形式為“switch_to(cur, next)”，意為將線程 cur 的上下文保護好，再將線程 next 的上下文裝載到處理器，從而完成了任務切換。

switch_to

完整的程序就也因此分為兩部分，一部分是做重要工作的內核級代碼，另一部分就是做普通工作的用戶級代碼。所以，“完整的程序=用戶代碼+內核代碼”。而這個完整的程序就是我們所說的任務，也就是線程或進程。換而言之，我們的Application是離不開我們的內核服務的。

當處理器處于低特權級下執行用戶代碼時我們稱之為用戶態，當處理器進入高特權級執行到內核代碼時，我們稱之為內核態，當處理器從用戶代碼所在的低特權級過渡到內核代碼所在的高特權級時，這稱為陷入內核。因此一定要清楚，無論是執行用戶代碼，還是執行內核代碼，這些代碼都屬于這個完整的程序，即屬于當前任務，并不是說當前任務由用戶態進入內核態后當前任務就切換成內核了，這樣理解是不對的。

任務與任務的區別在于執行流一整套的上下文資源，這包括寄存器映像、地址空間、IO 位圖等。擁有這些資源才稱得上是任務。因此，處理器只有被新的上下文資源重新裝載后，當前任務才被替換為新的任務，這才叫任務切換。當任務進入內核態時，其上下文資源并未完全替換，只是執行了“更厲害”的代碼。

每個任務都有個執行流，這都是事先規劃好的執行路徑，按道理應該是從頭執行到結束。不過實際的情況是執行流經常被臨時改道，突然就執行了規劃外的指令，這在多任務系統中是很正常的，因為操作系統是由中斷驅動的，每一次中斷都將使處理器放下手頭的工作轉去執行中斷處理程序。為了在中斷處理完成后能夠恢復任務原有的執行路徑，必須在執行流被改變前，將任務的上下文保護好。

執行流被改變后，在其后續的執行過程中還可能會再次發生被改變“流向”的情況，也就是說隨著執行的深入，這種改變的深度很可能是多層的。如果希望將來能夠返回到本層的執行流，依然要在改變前保護好本層的上下文。總之，凡是涉及到執行流的改變，不管被改變了幾層，為了將來能夠恢復到本層繼續執行，必須在改變發生前將本層執行流的上下文保護好。因此，執行流被改變了幾層就要做幾次上下文保護。

在咱們的系統中，任務調度是由時鐘中斷發起，由中斷處理程序調用 switch_to 函數實現的。假設當前任務在中斷發生前所處的執行流屬于第一層，受時鐘中斷的影響，處理器會進入中斷處理程序，這使當前的任務執行流被第一次改變，因此在進入中斷時，我們要保護好第一層的上下文，即中斷前的任務狀態。之后在內核中執行中斷處理程序，這屬于第二層執行流。當中斷處理程序調用任務切換函數 switch_to 時，當前的中斷處理程序又要被中斷，因此要保護好第二層的上下文，即中斷處理過程中的任務狀態。

因此，咱們系統中的任務調度，過程中需要保護好任務兩層執行流的上下文，這分兩部分來完成。第一部分是進入中斷時的保護，這保存的是任務的全部寄存器映像，也就是進入中斷前任務所屬第一層的狀態，這些寄存器映像相當于任務中用戶代碼的上下文。

當把這些寄存器映像恢復到處理器中后，任務便完全退出中斷，繼續執行自己的代碼部分。換句話說，當恢復寄存器后，如果此任務是用戶進程，任務就完全恢復為用戶程序繼續在用戶態下執行，如果此任務是內核線程，任務就完全恢復為另一段被中斷執行的內核代碼，依然是在內核態下運行。

第二部分是保護內核環境上下文，根據ABI，除esp 外，只保護esi、edi、ebx 和ebp 這4 個寄存器就夠了。這4 個寄存器映像相當于任務中的內核代碼的上下文，也就是第二層執行流，此部分只負責恢復第二層的執行流，即恢復為在內核的中斷處理程序中繼續執行的狀態。下面需要結合咱們的實現來解釋為什么這么做了。

[bits 32]
section .text
global switch_to
switch_to:; The return address is located here on the stack.push esipush edipush ebxpush ebp
?mov eax, [esp + 20] ? ? ? ? ; Get the parameter `cur` from the stack, cur = [esp + 20].mov [eax], esp ? ? ? ? ? ? ?; Save the stack pointer (esp) into the `self_kstack` field of the task_struct.; The `self_kstack` field is at offset 0 in the task_struct,; so we can directly store 4 bytes at the beginning of the thread structure.
?
;------------------  Above is backing up the current thread's context. Below is restoring the next thread's context. ----------------mov eax, [esp + 24] ? ? ? ? ; Get the parameter `next` from the stack, next = [esp + 24].mov esp, [eax] ? ? ? ? ? ? ?; The first member of the PCB is the `self_kstack` member, which records the top of the 0-level stack.; It is used to restore the 0-level stack when the thread is scheduled on the CPU.; The 0-level stack contains all the information of the process or thread, including the 3-level stack pointer.pop ebppop ebxpop edipop esiret ? ? ? ? ? ? ? ? ? ? ? ? ; Return to the return address mentioned in the comment below `switch_to`.; If not entered via an interrupt, the first execution will return to `kernel_thread`.

switch_to 的操作對象是線程棧 struct thread_stack，對棧中的返回地址及參數的設置在上面呢。上下文的保護工作分為兩部分，第一部分用于恢復中斷前的狀態，這相對好理解。咱們的函數switch_to 完成的是第二部分，用于任務切換后恢復執行中斷處理程序中的后續代碼。

注意，不要誤以為此時恢復的寄存器映像是在上面剛剛保存過的那些寄存器。你仔細看！我們是將esp切換到了我們的next所指向的地址上去的。所以沒有恢復，不過是保存完之后，調用曾經被觸發schedule而保存的內容而已！！！

#include "include/library/ccos_print.h"
#include "include/kernel/init.h"
#include "include/library/kernel_assert.h"
#include "include/memory/memory.h"
#include "include/thread/thread.h"
?
void thread_a(void* args);
void thread_b(void* args);
int main(void)
{init_all();thread_start("k_thread_a", 31, thread_a, "argA "); thread_start("k_thread_b", 16, thread_b, "argB "); interrupt_enabled();// code is baddy! we need LOCK!!!!while(1);
}
?
void thread_a(void* args){char* arg = (char*)args;while(1){ccos_puts(arg);}
}
?
void thread_b(void* args){char* arg = (char*)args;while(1){ccos_puts(arg);}
}

上電試一下：

代碼開始運行良好，后面崩潰了，發生什么呢？請看后會分解！

代碼：CCOperateSystem/Documentations/8_Thread_Management/8.2_Implement_schedule_code at main · Charliechen114514/CCOperateSystemhttps://github.com/Charliechen114514/CCOperateSystem/tree/main/Documentations/8_Thread_Management/8.2_Implement_schedule_code