接前文，要实现调度，需要对前面代码有所修改，主要就是给PCB增添了些信息。 /* 进程或线程 PCB */ struct task_struct { ...... uint8_t priority; // 线程的优先级 uint8_t ticks; // 每次线程在处理器上执行的时间滴答数 uint32_t elapsed_ticks; // 线程从开始执行到结束执行的总时间滴答数 struct list_elem general_tag; // 标记就绪线程队列 struct list_elem all_list_tag; // 标记全部线程队列 uint32_t stack_magic; // 魔数，栈的边界标记，用于检测栈的溢出 }; 在PCB中，我们新增了ticks记录一次时间片。elapsed_ticks记录进程/线程运行的总时间。
另外新增了2个链表(浸入式链表设计)。用来标记2个队列，一个是可以就绪队列，里面的线程/进程可以上CPU运行，还有个是所有的进程/线程队列，总的队列-就绪队列，剩下的就是其他阻塞等不能运行的进程/线程。 /* 初始化线程基本信息 */ void init_thread(struct task_struct* pthread, char* name, int prio) { memset(pthread, 0, sizeof(*pthread)); /* self_kstack是线程自己在内核态下使用的栈顶地址 */ pthread->self_kstack = (uint32_t*)((uint32_t)pthread + PG_SIZE); strcpy(pthread->name, name); if(pthread == main_thread) pthread->status = TASK_RUNNING; else pthread->status = TASK_READY; pthread->priority = prio; pthread->ticks = prio; pthread->elapsed_ticks = 0; pthread->stack_magic = 0x19870916; // 自定义的魔数 } struct task_struct* thread_start(char* name, int prio, thread_func function, void* func_arg) { /* pcb都位于内核空间,包括用户进程的pcb也是在内核空间 */ struct task_struct* thread = get_kernel_pages(1); init_thread(thread, name, prio); thread_create(thread, function, func_arg); /* 加入就绪线程队列 */ ASSERT(!elem_find(&thread_ready_list, &(thread->general_tag))); list_append(&thread_ready_list, &(thread->general_tag)); /* 加入全部线程队列 */ ASSERT(!elem_find(&thread_all_list, &(thread->all_list_tag))); list_append(&thread_all_list, &(thread->all_list_tag)); return thread; } thread_start.png 同时还有个问题，我们内核很早就开始运行了，那时，并没有线程的概念，所以为了让内核支持线程，我们必须也按照格式将其改造。 struct task_struct* main_thread; // main线程PCB static void make_main_thread() { /* 因为main线程早已运行,咱们在loader.S中进入内核时的mov esp, 0xc009f000, * 就是为其预留了PCB,地址为0xc009e000 */ main_thread = running_thread(); // main线程PCB = 0xc009e000 init_thread(main_thread, "main", 31); /* main函数是当前正在执行的线程,当前线程不在thread_ready_list中, 所以只将其加在thread_all_list中. */ ASSERT(!elem_find(&thread_all_list, &main_thread->all_list_tag)); list_append(&thread_all_list, &main_thread->all_list_tag); } void thread_init() { put_str("thread_init start "); list_init(&thread_ready_list); list_init(&thread_all_list); make_main_thread(); put_str("thread_init done "); }

任务调度

完整的任务调度过程需要三部分配合：
【1】 时钟中断处理函数
【2】调度器 schedule
【3】任务切换函数 switch_to

• 时钟中断处理函数
  在每个线程/进程PCB里都有一个ticks变量，负责记录线程执行到期时间。
  每发生一次时钟中断，时钟中断处理程序便将当前运行线程的 ticks 减1。当 ticks 为 0 时，时钟的中断处理程序调用调度器 schedule，它会把当前线程换下处理器，让调度器选择另一个线程上处理器。 /* 时钟的中断处理函数 */ static void intr_timer_handler() { struct task_struct* cur_thread = running_thread(); // 取得当前正在运行的线程的PCB ASSERT(cur_thread->stack_magic == 0x19870916); cur_thread->elpased_ticks++; // 记录此线程执行CPU的时间(滴答数) ticks++; // 全局变量，从内核第一次处理时间中断后开始至今总共的时间(嘀哒数) if (cur_thread->ticks == 0) schedule(); else cur_thread->ticks--; }
• 调度器 schedule
  调度器的主要任务就是 读写就绪队列，增删里面的结点。 所有待执行的线程都在 thread_ready_list 队列(就绪队列)中，我们的调度机制很简单，就是 Round_Robin Schedule，即轮询调度，即按照队列先进先出的顺序调度线程。 就绪线程队列和全部线程队列.png 调度器 schedule 并不仅由时钟中断处理程序来触发调用，它还有被其他函数调用的情况，比如后面要介绍的函数 thread_block(线程阻塞自己时，调度其他线程运行)。因此，在 schedule 中有要判断当前线程是由于什么原因才被换下CPU，是 "线程片时间到了" 还是 "线程片时间未到，它被阻塞了"，不同的原因处理不一样。 void schedule() { ASSERT(intr_get_status() == INTR_OFF); struct task_struct* cur = running_thread(); /* 根据线程状态判断当前线程是出于什么原因才被换下CPU */ if (cur->status == TASK_RUNNING) // 时间片用完 { ASSERT(!elem_find(&thread_ready_list, &cur->gengeral_tag)); cur->ticks = cur->priority; cur->status = TASK_READY; list_append(&thread_ready_list, &cur->gengeral_tag); // 重新加入就绪队列，等待下一次调度运行 } else { } ASSERT(!list_empty(&thread_ready_list)); thread_tag = NULL; thread_tag = list_pop(&thread_ready_list); struct task_struct* next = elem2entry(struct task_struct, general_tag, thread_tag); // 得到将要上CPU的线程PCB next->status = TASK_RUNNING; switch_to(cur, next); }
• 任务切换函数 switch_to [bits 32] section .text_to global switch_to switch_to: ; 栈中此处时返回地址 push esi push edi push ebx push ebp mov eax, [esp + 20] ; [esp+20]即当前线程PCB地址 mov [eax], esp ; 将当前线程栈指针保存到当前线程PCB起始处(self_kstack) ;以上是备份当前线程的环境，下面是恢复下一个线程的环境 mov eax, [esp + 24] ; [esp+24]即即将要执行的线程PCB地址 mov esp, [eax] ; [eax] PCB起始处(self_kstack), 线程栈指针 pop ebp pop ebx pop edi pop esi ret

switch_to 中的栈.png

• 完整的任务切换
  先说说，任务的概念：程序所作的工作可以分为2部分。一部分是"重要工作"，这是由操作系统完成的，另一部分是"普通工作"，这是由用户代码完成，所以"完整的程序=用户代码 + 内核代码"，而这个完整的程序就是我们所说的任务。

在我们的系统中，任务调度是由时钟中断发起，由中断处理程序调用 switch_to 函数实现的。
在进入中断时，我们要保护号第一层执行流的的上下文，即中断前任务A的状态。
之后再执行switch，这属于第二层执行流。 任务切换.png 所以一次完整的线程调度是先从kernel.S开始，然后调用时间中断函数，在时间中断函数里调用schedule，再在schedule中调用switch。完成任务切换。 完整的任务切换过程.png 任务切换，线程栈的信息.png 每个任务中断后，保存上下文的格式都是统一的，最后只需要在switch 中完成各任务栈的切换mov eax, [esp + 24], mov esp, [eax]，再沿着之前保护的上下文恢复上下文，即可以完成从任务A到任务B的切换。