代码、内容参考来自于包括《操作系统真象还原》、《一个64位操作系统的设计与实现》以及《ORANGE’S：一个操作系统的实现》。
这里要完成的任务是线程的轮询调度。
/thread/thread.h修改如下：
#ifndef __THREAD_THREAD_H
#define __THREAD_THREAD_H
#include "stdint.h"
#include "list.h"
/*自定义通用函数类型，它将在很多线程函数中作为形参类型*/
typedef void thread_func(void*);
/*进程或线程的状态*/
enum task_status{
TASK_RUNNING,
TASK_READY,
TASK_BLOCKED,
TASK_WAITING,
TASK_HANGING,
TASK_DIED
};
/*中断栈intr_stack
用于中断发生时保护程序上下文环境：
进程/线程被外部中断/软中断打断时，会按照此结构压入上下文
寄存器，intr_exit中的出栈操作是此结构的逆操作
此栈在线程自己的内核栈中位置固定，所在页的最顶端
*/
struct intr_stack{
uint32_t vec_no; //kernel.S宏VECTOR中push %1压入的中断号
uint32_t edi;
uint32_t esi;
uint32_t ebp;
uint32_t esp_dummy; //虽然pushad把esp也压入了，但esp是不断变化的，所以会被popad忽略
uint32_t ebx;
uint32_t edx;
uint32_t ecx;
uint32_t eax;
uint32_t gs;
uint32_t fs;
uint32_t es;
uint32_t ds;
/*下面由CPU从低特权级进入高特权级时压入*/
uint32_t err_code; //err_code会被压入在eip之后
void (*eip) (void);
uint32_t cs;
uint32_t eflags;
void* esp;
uint32_t ss;
};
/*线程栈thread_stack
线程自己的栈，用于存储线程中待执行的函数
此结构在线程自己的内核栈中位置不固定
仅用在switch_to时保存线程环境
实际位置取决于实际情况。
*/
struct thread_stack{
uint32_t ebp;
uint32_t ebx;
uint32_t edi;
uint32_t esi;
/*线程第一次执行时，eip指向待调用函数kernel_thread，
其他时候，eip指向switch_to的返回地址*/
void (*eip) (thread_func* func,void* func_arg);
/*以下仅供第一次被调度上CPU时使用*/
/*参数unused_ret只为占位置充数为返回地址*/
void (*unused_retaddr); //占位符，基线，表示返回地址
thread_func* function; //由kernel_thread所调用的函数名
void* func_arg; //由kernel_thread所调用的函数所需的参数
};
/*进程或线程的pcb，程序控制块*/
struct task_struct{
uint32_t* self_kstack; //各内核线程都用自己的内核栈
enum task_status status;
uint8_t priority; //线程优先级
char name[16];
uint8_t ticks; //每次在处理器上的嘀咕数
uint32_t elapsed_ticks; //此任务自上CPU运行至今用了多少CPU嘀咕数，也就是任务运行了多久
struct list_elem general_tag; //用于线程在一般队列中的节点
struct list_elem all_list_tag; //用于线程队列thread_all_list中的结点
uint32_t* pgdir; //进程自己页表的虚拟地址，如果是线程则为NULL
uint32_t stack_magic; //栈的边界标记，用于检测栈的溢出
};
/*由kernel_thread去执行function(func_arg)*/
// static void kernel_thread(thread_func* funcion,void* func_arg);
/*初始化线程栈thread_stack，将待执行的函数和参数放到thread_stack中相应的位置*/
void thread_create(struct task_struct* pthread,thread_func function,void* func_arg);
/*线程初始化*/
void init_thread(struct task_struct* pthread,char* name,int prio);
/*创建一优先级为prio，线程名为name，线程所执行函数为function(func_arg)的线程*/
struct task_struct* thread_start(char* name,int prio,thread_func function,void* func_arg);
#endif上面仅仅是struct task_struct 结构中新增了几个成员。
/*进程或线程的pcb，程序控制块*/
struct task_struct{
uint32_t* self_kstack; //各内核线程都用自己的内核栈
enum task_status status;
uint8_t priority; //线程优先级
char name[16];
uint8_t ticks; //每次在处理器上的嘀咕数
uint32_t elapsed_ticks; //此任务自上CPU运行至今用了多少CPU嘀咕数，也就是任务运行了多久
struct list_elem general_tag; //用于线程在一般队列中的节点
struct list_elem all_list_tag; //用于线程队列thread_all_list中的结点
uint32_t* pgdir; //进程自己页表的虚拟地址，如果是线程则为NULL
uint32_t stack_magic; //栈的边界标记，用于检测栈的溢出
};ticks是任务每次被调度到处理器上执行的时间嘀嗒数，也就是我们所说的任务的时间片，每次时钟中断都会将当前任务的ticks减1，当减到0时就被换下处理器。
ticks和上面的priority要配合使用，priority表示任务的优先级，咱们这里优先级体现在任务执行的时间片上，即优先级越高，每次任务被调度上处理器后执行的时间片就越长。当ticks递减为0时，就要被时间中断处理程序和调度器换下处理器，调度器把priority重新赋值给ticks，这样当此线程下一次又被调度时，将再次在处理器上运行ticks个时间片。
elapsed_ticks用于记录任务在处理器上运行的时钟嘀嗒数，从开始执行，到运行结束所经历的总时钟数。
general_tag的类型是struct list_elem，也就是general_tag是双向链表中的结点。它是线程的标签，当线程被加入到就绪队列thread_ready_list或其他等待队列中时，就把该线程PCB中general_tag的地址加入队列。
一个struct list_elem类型的结点只有一对前躯和后继指针，它只能被加入一个队列，但在我们的系统中，为管理所有线程，还存在一个全部线程队列thread_all_list，因此线程还需要另外一个标签，即all_list_tag。all_list_tag的类型也是struct list_elem，它专用于线程被加入全部线程队列时使用。
这两个标签仅仅是加入队列时用的，将来从队列中把它们取出来时，还需要再通过offset宏与elem2entry宏的”反操作”，实现从&general_tag到&thread的地址转换，将它们还原成线程的PCB地址后才能使用。
pgdir是任务自己的页表。线程与进程的最大区别就是进程独享自己的地址空间，即进程有自己的页表，而线程共享所在进程的地址空间，即线程无页表。如果该任务为线程，pgdir则为NULL，否则pgdir会被赋予页表的虚拟地址，注意此处是虚拟地址，页表加载时还是要被转换成物理地址的。
/thread/thread.c修改如下：
#include "thread.h"
#include "stdint.h"
#include "string.h"
#include "global.h"
#include "memory.h"
#define PG_SIZE 4096
struct task_struct* main_thread; //主线程PCB
struct list thread_ready_list; //就绪队列
struct list thread_all_list; //所有任务队列
static struct list_elem* thread_tag; //用于保存队列中的线程结点
extern void switch_to(struct task_struct* cur,struct task_struct* next);
/*获取当前线程的pcb指针*/
struct task_struct* running_thread(){
uint32_t esp;
asm("mov %%esp,%0":"=g"(esp)); //将当前的栈指针（ESP）的值存储到变量esp中。
return (struct task_struct*)(esp & 0xfffff000); //取esp整数部分，即pcb起始地址
}
/*由kernel_thread去执行function(func_arg)*/
static void kernel_thread(thread_func* funcion,void* func_arg){
intr_enable(); //开中断，避免后面的时钟中断被屏蔽，而无法调度其他线程
funcion(func_arg);
}
/*初始化线程栈thread_stack，将待执行的函数和参数放到thread_stack中相应的位置*/
void thread_create(struct task_struct* pthread,thread_func function,void* func_arg){
/*先预留中断使用栈的空间*/
pthread->self_kstack -= sizeof(struct intr_stack);
/*再预留出线程栈空间*/
pthread->self_kstack -= sizeof(struct thread_stack);
struct thread_stack* kthread_stack = (struct thread_stack*)pthread->self_kstack; //线程栈指针
kthread_stack->eip = kernel_thread;
kthread_stack->function = function;
kthread_stack->func_arg = func_arg;
kthread_stack->ebp = kthread_stack->ebx = kthread_stack->edi = kthread_stack->esi = 0; //寄存器初始化为0
}
/*线程初始化*/
void init_thread(struct task_struct* pthread,char* name,int prio){
memset(pthread,0,sizeof(*pthread));
strcpy(pthread->name,name);
if(pthread == main_thread)
pthread = TASK_RUNNING;
else
pthread = TASK_READY;
/*self_kstack是线程自己在内核态下使用的栈顶地址*/
pthread->self_kstack = (uint32_t*)((uint32_t)pthread + PG_SIZE);
pthread->priority = prio;
pthread->ticks = prio;
pthread->elapsed_ticks = 0;
pthread->pgdir = NULL;
pthread->stack_magic = 0x19870916;
}
/*创建一优先级为prio，线程名为name，线程所执行函数为function(func_arg)的线程*/
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);
// asm volatile("movl %0,%%esp; \
// pop %%ebp;pop %%ebx;pop %%edi;pop %%esi; \
// ret": : "g"(thread->self_kstack) : "memory");
// //esp = thread->self_kstack为栈顶；4个出栈，将初始化的0弹出到相应寄存器中；执行ret，将栈顶数据作为返回地址送入CPU的eip中；thread->self_kstack为输入
return thread;
}
/*将kernel中的main函数完善为主线程*/
static void make_main_thread(void){
/*因为main线程早已在运行，咱们在loader.S中进入内核时的mov esp,0xc009f000，就是为其预留pcb的。
因为pcb的地址为0xc009e000，不需要通过get_kernel_page另外分配一页*/
main_thread = running_thread();
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);
}同样修改的不多
开始定义一些全局的数据结构
struct task_struct* main_thread; //主线程PCB struct list thread_ready_list; //就绪队列 struct list thread_all_list; //所有任务队列 static struct list_elem* thread_tag; //用于保存队列中的线程结点
“struct task_struct* main_thread”是定义主线程的PCB，咱们进入内核后一直执行的是main 函数，其实它就是一个线程，我们在后面会将其完善成线程的结构，因此为其先定义了个PCB。
“struct list thread_ready_list”便是就绪队列，调度器要选择某个线程上处理器运行的话，必然要先将所有线程收集到某个地方，这个地方就是线程就绪队列。以后每创建一个线程就将其加到此队列中。
thread_all_list存放创建的所有(全部)线程队列，就绪队列中的线程都是可用于直接上处理器运行的，可有时候线程因为某些原因阻塞了，不能放在就绪队列中，但我们得有个地方能找到它，得知道我们共创建了多少线程，所以需要一个存放的地方。
全局变量thread_tag来存储tag的值，在队列中的结点并不是线程的PCB，而是线程PCB中的tag，即general_tag或all_list_tag，其类型是 struct list_elem。我们对线程的管理都是基于线程PCB的，其类型是struct task_struct，因此必须要将tag 转换成PCB，在转换过程中需要记录tag的值.
running_thread函数，它的功能是返回线程的PCB地址。各个线程所用的0级栈都是在自己的PCB当中，因此取当前栈指针的高20位作为当前运行线程的PCB。
/*获取当前线程的pcb指针*/
struct task_struct* running_thread(){
uint32_t esp;
asm("mov %%esp,%0":"=g"(esp)); //将当前的栈指针（ESP）的值存储到变量esp中。
return (struct task_struct*)(esp & 0xfffff000); //取esp整数部分，即pcb起始地址
}
kernel_thread函数在函数体中增加了开中断的函数intr_enable，它是任务调度的保证。
/*由kernel_thread去执行function(func_arg)*/
static void kernel_thread(thread_func* funcion,void* func_arg){
intr_enable(); //开中断，避免后面的时钟中断被屏蔽，而无法调度其他线程
funcion(func_arg);
}任务调度机制基于时钟中断，由时钟中断来中断所有任务的执行，借此将控制权交到内核手中，由内核的任务调度器schedule考虑将处理器使用权发放到某个任务的手中，下次中断再发生时，权利将再被回收，而且保证所有任务都有运行的机会。线程的首次运行是由时钟中断处理函数调用任务调度器schedule完成的，进入中断后处理器会自动关中断，因此在执行function前要打开中断，否则kernel_thread中的function在关中断的情况下运行，也就 是时钟中断被屏蔽了，再也不会调度到新的线程，function会独享处理器。
我们从开机到创建第一个线程前，程序都有个执行流，这个执行流带我们从BIOS到mbr到loader到kernel，就是我们所说的主线程。为此我们还在loader中把esp置为0xc009f000，意图是把0xc009e000作为主线程的PCB。
现在我们要创建新线程了，并且打开了时钟中断，时钟中断的处理函数会判断当前线程所用的栈是否会破坏了线程信息，也就是判断thread->stack_magic是否等于0x19870916。可是新创建的线程在首次运行前一直是主线程在跑，但此时主线程还没有身份证，也就是还没有PCB，因此main_thread->stack_magic就是错误的值，所以我们提前调用make_main_thread函数为主线程赋予了PCB。
/*将kernel中的main函数完善为主线程*/
static void make_main_thread(void){
/*因为main线程早已在运行，咱们在loader.S中进入内核时的mov esp,0xc009f000，就是为其预留pcb的。
因为pcb的地址为0xc009e000，不需要通过get_kernel_page另外分配一页*/
main_thread = running_thread();
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);
}make_main_thread函数它在主线程的PCB中写入线程信息。 正如前面介绍，主线程已经跑起来了，所以不需要再为其申请页安装其PCB，也不需要再通过thread_create构造它的线程栈，只需要通过init_thread填充其名称和优先级。 咱们只有两个队列，“就绪队列”只存储准备运行的线程，“全部队列”存储所有线程，包括就绪的、阻塞的、正在执行的，因此，只需要将主线程加入到全部队列thread_all_list中。
init_thread函数加入了对主线程main_thread的判断。
/*线程初始化*/
void init_thread(struct task_struct* pthread,char* name,int prio){
memset(pthread,0,sizeof(*pthread));
strcpy(pthread->name,name);
if(pthread == main_thread)
pthread = TASK_RUNNING;
else
pthread = TASK_READY;
/*self_kstack是线程自己在内核态下使用的栈顶地址*/
pthread->self_kstack = (uint32_t*)((uint32_t)pthread + PG_SIZE);
pthread->priority = prio;
pthread->ticks = prio;
pthread->elapsed_ticks = 0;
pthread->pgdir = NULL;
pthread->stack_magic = 0x19870916;
}如果待初始化的线程是主线程，也就是代码”if(pthread == main_thread)”的判断，那就将线程的状态置为TASK_RUNNING，因为主线程早已经在运行了。否则的话，就表示待初始化的线程不是主线程，它们的状态为准备运行，因此置其状态为TASK_READY。“pthread->elapsed_ticks=0”，表示线程尚未执行过。线程没有自己的地址空间，因此将线程的页表置空”pthread->pgdir=NULL”。
thread_start函数是创建线程的入口，主要变化是在执行完init_thread和thread_create后，通过 list_append 函数把新创建的线程加入了就绪队列和全部线程队列。
/*创建一优先级为prio，线程名为name，线程所执行函数为function(func_arg)的线程*/
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);
// asm volatile("movl %0,%%esp; \
// pop %%ebp;pop %%ebx;pop %%edi;pop %%esi; \
// ret": : "g"(thread->self_kstack) : "memory");
// //esp = thread->self_kstack为栈顶；4个出栈，将初始化的0弹出到相应寄存器中；执行ret，将栈顶数据作为返回地址送入CPU的eip中；thread->self_kstack为输入
return thread;
}拿就绪队列来说，在加入队列之前， 按理说线程不应该出现在就绪队列thread_ready_list中，因此在加入队列之前，先通过ASSERT来保证这一点。ASSERT 中调用的是elem_find(&thread_all_list,&thread->all_list_tag)，第 1 个参数是就绪队列的地 址&thread_ready_list，第2个参数是新线程的标签general_tag的地址。elem_find的功能是在队列中找结点，如果找到就返回1，否则返回0。由此可见，队列中的结点就是线程PCB中的成员general_tag。
list_append的功能就是在队列 thread_ready_list 中加入新创建线程的 general_tag 成员，因此传入的参数是 general_tag 的地址，即”&thread->general_tag”。链表(队列)中的结点并不是PCB，因此这里并不是把PCB加到队列中，我们链表的结点类型是 struct list_elem，只能将 struct list_elem类型的结点插入到队列中，而 PCB中general_tag 的类型就是 struct list_elem。这样做是有好处的，struct list_elem 类型中只有两个指针 成员: struct list_elem*prev和struct list_elem*next，因此它作为结点的话，结点尺寸就8字节，整个队列显得轻量小巧，如果换成PCB做结点，尺寸也太大了。
参考
郑钢著操作系统真象还原
田宇著一个64位操作系统的设计与实现
丁渊著ORANGE’S：一个操作系统的实现
