11
不知不觉已经写了11篇日志了，本篇博客将完成LAB 4的PART A的剩余部分，包括内核锁、进程（环境）的简单调度算法，以及fork系统调用。
一、内核锁
1、锁实现
考虑到当多个CPU同时陷入内核的场景，若对于关键数据结构不加锁必然就会导致重入错误（如cprintf不加锁会在屏幕上输出奇怪的结果），因此使用锁来保证内核函数内部的逻辑正确性是很有必要的。
内核锁相关代码都在spinlock.c和spinlock.h中，关键代码如下：
以及x86.h里面的xchg函数：
可以看到，xchg函数首先使用lock指令使xchgl变为原子操作，然后尝试将xchgl两个操作数互换，并把原先第一个操作数的结果放入result中返回。
若此时锁是空闲的，则xchg返回0，spin_lock函数执行完成，否则继续执行pause指令，然后接着执行xchg函数直到其返回值为1.
关于lock引用一段汇编手册的资料：
总线加锁前缀“lock”，它是为了在多处理器环境中，保证在当前指令执行期间禁止一切中断。这个前缀仅仅对ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG,DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD,XCHG指令有效，如果将Lock前缀用在其它指令之前，将会引起异常。
关于pause：
提升spin-wait-loop的性能，当执行spin-wait循环的时候，笨死和小强处理器会因为在退出循环的时候检测到memory order violation而导致严重的性能损失，pause指令就相当于提示处理器哥目前处于spin-wait中。在绝大多数情况下，处理器根据这个提示来避免violation，藉此大幅提高性能，由于这个原因，我们建议在spin-wait中加上一个pause指令。（出自于intel 汇编手册）
2、实验相关：
实验要求在以下4个地方加锁：
（1）i386_init中，启动多个ap之前。
（2）mp_main中，开始把任务调度到cpu上之前。
（3）trap中，若从用户态陷入内核则加锁。
（4）env_run中，从内核态返回用户态需要释放锁。
加锁后，将原有的并行执行过程在关键位置变为串行执行过程，整个启动过程大概如下：
i386_init-->BSP获得锁-->boot_ap-->(BSP建立为每个cpu建立idle任务、建立用户任务，mp_main)--->BSP的sched_yield-->其中的env_run释放锁-->AP1获得锁-->执行sched_yield-->释放锁-->AP2获得锁-->执行sched_yield-->释放锁..... 其中括号表示并行执行
具体代码如下：
（1）i386_init
（2）mp_main
（3）trap
（4）env_run
二、任务调度
1、原理
在JOS中，任务调度在内核中是函数sched_yield，同时在用户态有相应的系统调用sys_yield也可以调用内核中的这个函数。
i386_init启动时，在boot_ap函数调用后，为每个CPU创建一个idle任务，相应代码在user/idle.c，通过代码可以看到，这些任务使用一个死循环，不断调用sys_yield尝试切换任务。
所以在这种机制下我们需要实现sched_yield函数，具有以下几个要求：
（1）找到状态为runnable的任务，并切换执行
（2）如果找到一个running状态的任务，且此任务执行的CPU为当前CPU，也可将此任务切换执行
（3）若没有runnable任务，则执行idle任务。
（4）从当前CPU执行的任务处开始遍历链表（为了保证公平性）
2、代码
sched_yield的任务调度代码如下：
首先找到CPU当前任务的下标，然后从下标的下一个开始遍历数组。博主这段代码写的比较笨，主要是为了方便调试所用。
同时还要增加系统调用的部分代码，把进入内核态后的系统调用号和具体的系统调用对应起来，较为容易故不再详细论述。
三、fork
1、原理
fork作为一个系统调用，其功能是根据父进程创建出一个一模一样的子进程，若返回的是0则说明是子进程，否则是父进程，同时返回值为子进程的系统调用号。
JOS实现fork过程采用的是用户态“类库”的形式封装了一系列系统调用，包括创建新进程、设置新进程状态、虚拟地址映射等等，这部分已经在user/dumbfork.c中封装好了，实验所要求的是实现相关的系统调用，包括：
- sys_exofork:若为父进程返回子进程号，子进程则返回0。
- sys_env_set_status:设置子进程格式为runnable或者not_runnable
- sys_page_alloc:分配一个物理页并对应到某个虚拟地址
- sys_page_map:拷贝父进程的某个PTE，以此来建立子进程的虚拟内存映射
- sys_page_unmap:解除某个虚拟地址的映射（在PART B中使用）
2、代码
sys_exofork:
可以看出，该函数首先复制各寄存器的状态（env_tf），然后系统调用本身返回子进程的id，因为调用此系统调用的进程为父进程。同时将子进程的eax寄存器设置为0，因为系统调用的结果存放在eax寄存器中，这样子进程返回后得到的系统调用返回结果就为0。
sys_env_set_status
首先判断状态会否合法，然后根据进程ID进行查找，最后设置状态并返回。
sys_page_alloc:
按实验要求判断各种条件。
sys_page_map:
主要是一些判断+LAB 2中的函数的封装，没什么可说的。
sys_page_unmap:
到此PART A基本结束了，运行结果如下：
PS：写起来怎么感觉这个实验好简单啊，做起来怎么感觉难到爆啊。。。。