从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