以前的unix系统中，线程被当作和进程同样的东西，也就是说没有特别的数据结构来完成线程。以至于在打印主次线程的pid时，会发现是不同的。而现在的操作系统里，执行相同的程序可以看到他们共享同样的pid，不过有不同的tid。在我们的系统中我们没有必要完全模仿某一种特定的线程实现，我们需要针对JOS和unix系统的结构区别来决定JOS中的线程实现。为了决定如何实现线程，我们需要进行很多必要的讨论。
综合多方面的考虑，我决定向每一个进程内部加入对多线程的支持。总体设计上，我希望进程是线程与系统资源交互的一个接口。
我的想法是
首先是线程的创建。pthread_create库函数在内核中的支持是clone()系统调用。在linux系统中clone有更加广泛的使用，但是在这里只用来创建进程。首先使用env_alloc申请一个空闲的任务块，然后处理的是地址空间。主线程的地址空间可以直接赋给子线程（通过页表地址），但是要处理子线程的栈空间。栈空间对应到任务的数据结构中也就是任务上下文中的esp寄存器了，同时父进程通过pthread_create函数的start_routine参数来决定子线程的eip（也就是接下来要执行的指令位置）。对于栈空间，这里需要有一些讨论。
首先，我们在阶段一要有两个假设：1)不考虑线程销毁的情况，也就是说线程栈也不会销毁2)假设子线程不会占用异常栈。实现过程中的任何假设在后续阶段都需要解决。那么从USTACKTOP向下的每两个PGSIZE中，靠上的一个PGSIZE作为一个线程栈，靠下的一个PGSIZE被当作保护区，防止不被察觉的栈溢出情况。在创建线程的时候就需要找到新线程“对应”的栈位置。显然，每一个进程应该有相应的机制来确定这个位置；在不考虑线程销毁的情况下，只需要在父进程中保存有多少个线程即可。但是这个栈不可以是空的，因为从函数调用的角度考虑：1)新的线程需要从栈上获取参数2)在线程结束之后return语句将要在栈上获取返回地址。新的问题来了：线程结束之后应该返回到哪里。
到这里，阶段一已经结束了，因为程序已经可以执行基本的功能：创建进程，并且在线程上执行代码。
为线程设定返回地址本应该是一个简单的事情：线程栈的最上方的四字节是线程函数的参数，接下来的四个字节是返回地址位置。不过问题就在于，这个地址的值由谁来设定。如果直接clone里面在返回地址处填上pthread_exit，编译器是找不到定义的；如果强行包含头文件，那么在执行时会出现页错误，因为此时是内核地址空间中的代码，用户进程不可以执行。所以我设定了专门的系统调用，来从用户空间中传入这个返回函数地址应有的值，sys_set_thread_rtn_routine。
在这个接口调通之后，按理来说应该是进一步实现终止进程的例程了，不过在那之前还需要解决第一阶段的假设之一：线程不会被销毁。首先需要调整线程的结构，每一个进程有一个进程数的上限，在进程控制块中保存线程指针的数组，每一个任务都会被分配一个线程号（主线程是0号），所有线程栈在进程分配的时候就进行映射(load_icode)。在对数据结构进行改进之后，还需要调整clone中的实现。然后是完善线程的终止例程。线程终止分为两个部分，一是释放主线程中的线程相关资源，二是释放任务块。
之后就可以实现pthread_join的功能了。关于join的实现，一定是用表来记录的，而不能只用一个值来表示有多少个join。
在pthread_join实现之后，第二阶段就完成了。
首先我用多个CPU来并行的执行多线程的计数程序，由于多线程在同一个变量上计数，最后的结果是错误的。自旋锁的实现是很简单的，只需要使用xchg指令就可以了。
补充了之前实现过程中的一处疏漏，在主线程退出的时候，将子线程全部退出。
现在需要在原有的基础上拓充实现一些功能。这里有一些基本的思路：
- 设计并实现pthread_mutex_lock
- 允许线程中使用异常栈
- 设计并实现信号量
- 设计并实现进程间信号机制
但是问题是，就算是拓充了一些点，本质上还是没有办法将整个毕业设计提升档次。不过还是先完成这些点。 在继续之前要先思考一个问题：在一个线程释放自旋锁的时候，如果有多个线程同时试图获取自旋锁，会不会错误。其实这就是在说，在多个CPU同时取用一个值，会不会出现硬件级别上的竞争。这个问题的答案其实就在xchg这条指令中，在Intel的开发者手册第七章有关Bus Locking的部分中有写道在硬件级别上xchg的原子性是如何保证的。
接下来实现上面提到的四个点：
先要说明什么是mutex lock，以及其基本的实现思路。mutex，mutual exclusion，也就是互斥。在初始化了一个mutex lock之后，线程可以对之上锁，如果上锁成功那么这个锁就被标记为属于这个线程，只有这个线程本身能够解锁这个锁。最为核心的部分就是上锁的过程是怎样的
pthread_mutex_lock: atomic_dec(pthread_mutex_t.value); if(pthread_mutex_t.value!=0) futex(WAIT) else success
pthread_mutex_unlock: atomic_inc(pthread_mutex_t.value); if(pthread_mutex_t.value!=1) futex(WAKEUP) else success
互斥锁和信号量之间最为核心的区别就是，互斥锁的本质是锁机制，只有一个线程上锁解锁，其他的线程来检查这个锁是否开了；而信号量的本质是信号机制，由一个线程发出信号，别的线程对这个“资源被释放”的信号做出响应。
想要实现信号量和互斥锁，就需要先实现futex。futex的本质是一个内核空间中的队列，用户线程可以请求挂起自己从而等待共享资源，当占用资源的线程用完之后，让内核唤醒之前被挂起的线程。在linux的futex实现中，锁变量本身是在用户空间中的内核根据这个变量的地址，通过哈希函数来确定一个队列。显然这里的哈希表不是必须的，为了简单起见，这里只用普通的结构数组来完成从锁变量地址到队列的映射。之所以在设计系统的时候，使用变量地址来进行哈希索引，是因为我们希望事情尽量都在用户空间里完成，而不是用户向内核请求一个futex编号；同时我们也不可能完全让用户来完成。
接下来就是futex有关系统调用的具体实现。我首先需要对futex系统调用的接口进行简化和设计。在linux-2.6内核中，系统调用的执行流是pthread_function(线程有关的库函数)->sys_futex(系统调用)->do_futex->futex_wait。由于Jos系统本身的结构是简单的，我们这里让sys_futex完成全部的工作。关于futex的结构，首先内核中应该有一个足够大的数组来容纳全部的futex映射，每一个元素是一个地址和一个队列头指针的映射；然后队列包含了全部在这个futex下阻塞的线程，队列的结构应该是一个链表，不过为了简化处理我们这里可以考虑用定长的数组来代替（如果用链表实现的话，这里需要添加很多的链表操作。在我的设计中，所有的同步机制都是在线程之间而非进程之间的，那么这里提到的结构都可以被认为是进程自己内部的，这样区分的原因是，jos没有支持不同地址空间中变量的交互。
现在来考虑一个问题。在上面的伪代码中，（不会因为有内核锁）
###Semaphore 信号量的底层实现也是原子操作和futex，其实现的难点在于两个地方，一是如何实现原子操作atomic_dec_if_positive，二是如何组织信号量的数据结构。关于原子操作的实现，可以参考linux源码中的实现，后面可以慢慢推进。关于数据结构的组织，信号量的申请和初始化里，是可以决定信号量的个数的，我想的是给每一个信号量固定数量的元素，这个数量就是用户能够申请的上限。也就是说，信号量的组织形式是一个二维数组，每一行的第一个元素标志了这个信号量是否是空闲的，这里也可以用位图的形式来标记。这些数据结构都是内核中的静态资源。
sem_wait(sem_t sem) { for (;;) { if (atomic_decrement_if_positive(sem->count)) break; futex_wait(&sem->count, 0) } } sem_post(sem_t sem) { n = atomic_increment(sem->count); // Pass the new value of sem->count futex_wake(&sem->count, n + 1); }
/////////////////!!!!!! 线程的返回值
|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
| |
| ...... |
UTOP,UENVS ------> +------------------------------+ 0xeec00000 UXSTACKTOP -/ | User Exception Stack | RW/RW PGSIZE +------------------------------+ 0xeebff000 | Empty Memory (*) | --/-- PGSIZE USTACKTOP ---> +------------------------------+ 0xeebfe000 | User Stack TID = 0 | RW/RW PGSIZE +------------------------------+ 0xeebfd000 | Invalid Memory | RW/RW PGSIZE +------------------------------+ 0xeebfc000 | User Stack TID = 1 | RW/RW PGSIZE +------------------------------+ 0xeebfb000 | Invalid Memory | RW/RW PGSIZE +------------------------------+ 0xeebfa000 | | | ...... | |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| | Program Data & Heap | UTEXT --------> +------------------------------+ 0x00800000
+------------+ <-最开始的stacktop
| arg |
+------------+
| 返回%eip |
+============+
| 保存的%ebp | \
%ebp-> +------------+ |
| | |
| | \
| 本地变量 | >- 当前函数的栈帧
| | /
| | |
| | |
%esp-> +------------+ /