首发公众号：Rand_cs
进程三:代码部分
本文接着上文深入理解进程之数据结构篇来讲述有关进程的一些操作，主要就是创建，调度切换，加载程序，休眠唤醒，等待退出等等，一个一个来看
调度切换
关于第一部分想了半天，决定还是将进程的调度与切换放在开头，按道理说应该先讲述进程的创建，但是进程的创建与切换息息相关，只有先把进程的切换弄清楚了，才能明白进程的创建，所以还是先将进程切换给说了吧。
开门见山，主要有两个事件会触发进程的调度与切换：
- 一个进程的时间片到了，该下 $CPU$ 了
- 一个进程因为某些事件阻塞主动让出 $CPU$
$xv6$ 进程切换分为三个步骤：
- $A$ 进程切换到调度程序
- 调度程序挑一个进程 $B$
- 调度程序切换到进程 $B$
前后两个步骤为切换操作，中间步骤为调度操作。切换进程实际上进行了两次切换，第一次从 $A$ 进程切换到调度程序，调度程序根据调度算法选择出一个进程 $B$之后，再切换到进程 $B$。
进程的切换就是上下文的保存与恢复，发生了两次切换操作，就会有两次切换上下文保存与恢复。不论是主动让出 CPU 还是被动让出 CPU，肯定还会有一个中断上下文的保存与恢复，比如说发生时钟中断，时间片到了主动让出 CPU，再比如说读写系统调用阻塞等等，期间都会有中断发生，所以进程切换也避免不了中断上下文的保存与恢复，所以如下图所示：
切换和调度都是两个内核函数，所以要弄清楚进程的调度与切换，主要就是弄清楚切换与调度两个函数，先来看切换函数
切换函数
函数原型：
void swtch(struct context **old, struct context *new);
函数定义：
.globl swtch
swtch:
movl 4(%esp), %eax
movl 8(%esp), %edx
# Save old callee-saved registers
pushl %ebp
pushl %ebx
pushl %esi
pushl %edi
# Switch stacks
movl %esp, (%eax)
movl %edx, %esp
# Load new callee-saved registers
popl %edi
popl %esi
popl %ebx
popl %ebp
ret
切换函数很短也很对称，上下两段分别表示保存 $old$ 的上下文和恢复 $new$ 的上下文
进程A切换到调度程序
这个函数空口讲述不太好说，用实际例子来说明，比如现在是从进程 $A$ 切换到调度程序 $scheduler$，进程 $A$ 的任务结构体指针为 $a$，当前 $CPU$ 的指针为 $c$，则会这样调用切换函数：
swtch(&a->context, c->scheduler)，调用前将参数返回地址压栈，所以内核栈中情况如下：
进程 $A$ 内核栈里面的情况如第二个方框所示，我还把 $CPU$ 的栈和结构体画出来了，各种指代关系应该是很明了的，就是有亿点点多，注意两点：
- $swtch$ 的第一个参数是个二级指针，在我们的例子当中就是 $\&a\rightarrow context$，这个二级指针是进程 $A$ 结构体中 $context$ 这个属性字段的地址值。
- 图中的实线才是有着实际的指向关系，而虚线没有没有没有，我曾经在这儿出过错，为了提醒我自己说三遍。结构体里面的指针就是个变量，只有给它赋值的时候才会使它指向某个位置，不改变它的值的话，它就会一直指向某个位置。我这里主要是想表示一下各种数据结构中变量的指向，其实不应该画出来的。但如果是因为系统调用进入内核的话，$trapframe$ 那根线的确是实线，因为处理系统调用的过程中有个更改 $trapframe$ 的赋值语句。而 $kstack$ 这个指针是一直指向内核栈的首地址(不是栈顶)，这在后面 $TSS$ 部分还有提到。
准备好参数之后就开始执行 $swtch$ 函数了，首先是两个 mov 语句，很简单，取参数放到寄存器中。$\&a\rightarrow context$ 放到 $eax$ 中，$c \rightarrow scheduler$ 放到 $edx$ 中。
接着压栈四个寄存器值，保存进程 $A$ 的内核部分上下文，此时栈中布局没有太大变化：
这一部分要注意 $context$ 定义了 5 个寄存器，但实际只显示压栈了 4 个，还有个 $eip$(返回地址)是在调用 $swtch$ 时隐式压栈的
接着又是两个 mov 语句：
movl %esp, (%eax)
movl %edx, %esp
这两个 mov 语句是核心，因为这是一个换栈的过程：
- 将进程 A 的内核栈栈顶保存到任务结构体的 context 字段
- 将 $CPU$ 的内核栈栈顶赋值给 esp 完成换栈
又是注意两点：
- 进程 A 的栈顶地址保存到了任务结构体的 $context$字段而不是 $kstack$ 字段，虽然感觉从命名上来说 $kstack$ 才是内核栈地址，但实际上 $kstack$ 没多少用，具体用处见后面 $TSS$ 部分。
- $CPU$ 的 context 字段值就是栈顶，原因在第一点，后面从调度程序切换到 B 的时候就会看到，将 $CPU$ 的栈顶地址保存到 $CPU$ 结构体的 $context$ 字段，这样保持了一致性。
现在栈中情况：
很清楚的看到现在 $ESP$ 寄存器指向的是 $CPU$ 栈而不是进程 $A$ 的内核栈了，进程 $A$ 的栈顶保存到了任务结构体的 $context$ 字段后，$context$ 字段就指向了进程 $A$ 的内核栈顶。
接着弹出四个寄存器，然后 ret 返回：
弹栈除了将值弹到相应地方，就只是改变 $ESP$ 的值，不会做任何改变，所以各种指向关系没有任何变化。但要知道实际上右边那一块儿比如 $scheduler$ 的指针已经失效，等下次切换更新它的值才会有效。
ret 的时候 $ESP$ 应该指向返回地址，这个地址就是调度程序的返回地址，执行 ret 将其弹到 $EIP$ 寄存器后就开始执行调度程序
调度程序
调度程序主要做两件事(感觉本文说的两件事有点多了啊)：
- 根据调度算法挑一个进程出来，这里我们称之为进程 $B$
- 调用上述的 $swtch$ 函数切换到进程 $B$
调度算法
我在调度算法中总结了常见的几种调度算法，诸位可以一观，其中就包括了 $xv6$ 的调度。$xv6$ 的调度算法就是简单的轮询，平常各类书上网上讲的轮询是单个处理器的情况，多处理器下稍稍有些不同，来看示意图：
内核中只维护了一个全局的“就绪队列”，为所有 $CPU$ 共享。每个 $CPU$ 都有自己的调度器，调度器从这个全局队列挑选合适的进程然后将 $CPU$ 分配给它。
单队列的形式实现起来比较简单，对所有的 $CPU$ 来说很公平。这个队列是全局共享的，所以当一个 $CPU$ 挑选进程时需要加锁，不然多个 $CPU$ 就可能选取同一个进程。但是锁机制不可避免带来额外的开销使得性能降低。
具体代码如下：
void scheduler(void)
{
struct proc *p;
struct CPU *c = myCPU$();
c->proc = 0;
for(;;){
sti(); //允许中断
acquire(&ptable.lock); //取锁
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
//循环找一个RUNNABLE进程
if(p->state != RUNNABLE)
continue;
c->proc = p; //此CPU准备运行p
switchuvm(p); //切换p进程页表
p->state = RUNNING; //设置状态为RUNNING
swtch(&(c->scheduler), p->context); //切换进程
/***************************************************/
switchkvm(); //回来之后切换成内核页表
c->proc = 0; //上个进程下CPU，此时CPU上没进程运行
}
release(&ptable.lock); //释放锁
}
}
分割线之上的部分调度算法挑选一个进程 $B$ 在切换到 $B$ 的部分，分割线之后为从进程 $B$ 切换到调度程序进行新一轮的调度。整个流程感觉上应该是很清晰也很简单，但实际上要细究的话这段代码很复杂
为什么要周期性地允许中断，为什么 $swtch$ 之前需要取锁，这两个问题归根结底还是锁与死锁的问题，这在后面的文章详述。
另外对于调度程序中的 $swtch$ 函数要有这个认识，它不会返回，执行到中途的时候就恢复了进程的上下文去执行进程了，而再次回到调度程序的时候此时 $CPU$ 上没有进程再运行。这里说的有点超前了，下面还是继续调度程序切换到进程 $B$ 的过程
调度程序切换到进程B
类似前面从进程 A 切换到调度程序 scheduler 调用 swtch(&a->context, c->scheduler)，从调度程序切换到进程 B 就调用 swtch(&(c->scheduler), b->context)，这个过程是几乎是一模一样的，不再赘述，最后看张图就可以了。这里主要说明，切换到进程 $B$ 之前需要做两件极其重要的事：更新 $TSS$ 和 切换页表，这两件事都在 $switchuvm$ 函数中进行，分别来看
更新 $TSS$
咱们在数据结构中重点说过 $TSS$ 的作用就可简单的认为提供内核栈的地址，切换进程时必须要将其内核栈的地址写到 $TSS$ 结构体里面，所以有了如下操作。
myCPU()->gdt[SEG_TSS] = SEG16(STS_T32A, &myCPU()->ts, sizeof(myCPU()->ts)-1, 0);
myCPU()->gdt[SEG_TSS].s = 0;
myCPU()->ts.ss0 = SEG_KDATA << 3; //更改SS为新栈的选择子
mycpu()->ts.esp0 = (uint)p->kstack + KSTACKSIZE; //在TSS中记录内核栈地址
myCPU()->ts.iomb = (ushort) 0xFFFF; //用户态禁止使用io指令
ltr(SEG_TSS << 3); //加载TSS段的选择子到TR寄存器
这是 $xv6$ 的源码，大胆地评论一句，私以为这样写不太好，根据前文的分析，$TSS$ 现在唯一的作用就是提供内核栈的地址，所以在切换进程的时候也应该只对 $TSS$ 的 $ESP0$ 字段做更新，甚至 $SS0$ 都不需要更新，因为平坦模式共用选择子嘛。
对此我对 $xv6$ 的代码做了如下修改，除开更新 $ESP0$ 的部分，我将其他部分集中在一起写进了计算机启动时的初始化代码里面：
static void tssinit(void){
struct $CPU$ *c;
c = &CPUs[CPUid()];
c->gdt[SEG_TSS] = SEG16(STS_T32A, &my$CPU$()->ts, sizeof(my$CPU$()->ts)-1, 0); //在GDT中注册TSS描述符
c->gdt[SEG_TSS].s = 0; //修改S位表示这是一个系统段
c->ts.ss0 = SEG_KDATA << 3; //选择子使用内核数据段选择子
c->ts.iomb = (ushort) 0xFFFF; //禁止用户态使用IO指令
ltr(SEG_TSS << 3); //加载选择子到TR
}
在初始化代码中加进这个 $TSS$ 初始化函数：
/*******main.c********/
int main(void){
//初始化BSP的tss
/****略*****/
tssinit();
/****略*****/
}
static void mpenter(void){
//初始化AP的tss
/****略*****/
tssinit();
/****略*****/
}
因为 $xv6$ 支持多处理器，$BSP$ 和 $AP$ 的启动代码稍有不同，两者都需要调用 $tssinit$ 来初始化，下面来看看这段初始化代码：
按照以前的进程切换方式，每个进程都要有一个单独的 $TSS$，但是效率太低，不使用这套。$xv6$ 这是里每个 $CPU$ 一个，所有进程共享。$TSS$ 是内存的一段数据，需要在 $GDT$ 中注册，所谓注册就是在 $GDT$ 添加一个 $TSS$ 描述符，将 $TSS$ 的基址，界限，类型填进去。$TSS$ 是硬件支持的一种数据结构，硬件运行必须要有这个结构，有这样特点的内存数据段(广义的数据)就叫做系统段，系统段的描述符 $S$ 位需要置 0。而像是常说的进程代码段数据段(狭义的数据)都不是系统段，它们的 $S$ 位都是 1。
内核栈段使用内核数据段的选择子，$IO$ 位图的基址设为 $0xFFFF$，这个位置超过了 $TSS$ 界限，表示 $IO$ 位图不存在，$IO$ 位图不存在表示只有 $IOPL$ 能够决定当前特权级能否使用 $IO$ 指令。$EFLAGS$ 的 $IOPL$ 位一直是 0，则表示只有内核能够使用 $IO$ 指令。
最后将 $TSS$ 的选择子加载到 $TR$，这样 $CPU$ 才能够知道 $TSS$ 在哪，这就是 $TSS$ 的初始化部分，这些都不需要再次改变，每次进程切换时只需要更新 $ESP0$ 的值，将其修改为：
myCPU()->ts.esp0 = (uint)p->kstack + KSTACKSIZE;
为什么 $ESP0$ 是个固定值 $(uint)p\rightarrow kstack + KSTACKSIZE$，也就是如下图所示：
从这个图里面可以很清晰的看出 $ESP0$ 的值就是进程内核栈的栈底，这说明什么？说明退出退出内核时内核栈是空的，为什么会这样呢？这个问题在进程创建的时候解释，避免一会儿说这儿，一会儿讲那儿。
切换页表
上面为更新 $TSS$，实际上就只需要更新 $TSS$ 中的 $ESP0$ 为新进程的内核栈地址，每个进程都工作在自己的虚拟地址空间里面，所以切换进程的时候还得把页表给切换了。
lcr3(V2P(p->pgdir));
切换页表就一条语句，将新进程 $B$ 的页目录地址加载到 $CR3$ 寄存器。放进 $CR3$ 的页目录地址一定是个物理地址，地址翻译就是要从 $CR3$ 中获取页目录地址，如果这个地址是个虚拟地址，那还得翻译这个地址岂不“无限递归”出错了嘛，所以 $CR3$ 中一定得放物理地址，因此使用 $V2P$ 这个宏将虚拟地址转化为物理地址
从调度程序切换到进程 B 的图示如下：
到此进程的切换过程完毕，下面再来说说进程的创建。
创建普通进程
有了前面进程切换的铺垫，理解进程的创建就简单多了。在 $xv6$ 或者 $Linux$ 里除了第一个 $init$ 进程需要内核来创建之外，其他的所有进程都是使用 $fork$ 来创建，第一个进程的创建放在本文最后一个部分，这一节先来看普通进程的创建方式，也就是 $fork$ 函数的实现
$fork$ 函数大家应该听得多也用得多了，$fork$ 就好比分身术，以父进程为模板克隆出一个几乎一模一样的子进程出来。克隆的方式也分种类，有朴实无华(傻不拉几)版本的，也有十分巧妙(写时复制)的版本。$xv6$ 的 $fork$ 实现就很朴实无华，将父进程所有的东西几乎都复制了一份。
虽然很”朴实“，但也从中也还是能够学到 $fork$ 的基本思想，这里先将 $fork$ 函数会做的事情罗列出来，好有个大概把握
- 分配任务结构体，初始化任务结构体
- 分配内核栈，模拟上下文填充内核栈($fork$ 时此步骤无用)
- 复制父进程数据、创建“新”页表
- 复制文件描述符表
- 修改进程结构体属性。
分配和初始化任务结构体
关于源码我就只放核心代码了，一些定义还有一些“不太重要”的操作比如上锁放锁就不摆出来占用空间了。一般函数里面锁的使用比较简单，困难重点的部分后面有专门的一节来讲述。这里先来看任务结构体的分配
static struct proc* allocproc(void){
/*************略*************/
/*从头至尾依次寻找空间任务结构体*/
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
if(p->state == UNUSED)
goto found;
/*************略*************/
}
从前置后遍历任务结构体数组，寻找空闲的任务结构体，也就事寻找状态为 $UNUSED$ 的结构体，找到之后就跳转到 $found$
found:
p->state = EMBRYO; //设置状态为EMBRYO
p->pid = nextpid++; //设置进程号
找到一个空闲任务结构体之后就将其状态设置为 $EMBRYO$，意为该结构体刚分配处于，正处于“萌芽”期。
$nextpid$ 是一个全局变量，初始值为 1，每创建一个进程该值就会递增。
任务结构体的分配很简单，就这么多，$allocproc$ 函数的后续部分为分配和初始化内核栈部分
分配和初始化内核栈
if((p->kstack = kalloc()) == 0){
//分配内核栈
p->state = UNUSED; //如果分配失败，回收该任务结构体后返回
return 0;
}
sp = p->kstack + KSTACKSIZE; //栈顶
// #define KSTACKSIZE 4096
使用 $kalloc$ 函数在空闲空间分配了一页作为内核栈，它位置不固定，完全却决于当时内存的使用情况。如果分配内核栈失败就将刚分配的任务结构体回收(状态设置为 $UNUSED$)再返回。
使用 $kalloc$ 分配的一页空间时返回的是这页的首地址(低地址)，刚分配的栈肯定是空的，所以栈顶为这页的首地址加上页大小 $4096$
接下来就要初始化内核栈，在这刚分配内核栈里面做文章了，也就是与进程切换相关的部分来了。从前面我们知道进程的切换实质上就是上下文的保存与恢复，那这与进程的切换有什么关系？我们来捋一捋假如只分配栈空间但不做什么修饰会出现什么情况？
新进程是在内核创建的，我们且称之为进程 $A$，当 A 创建好后，想上 $CPU$ 执行就需要被调度，然后与正在执行的进程 B 进行切换操作(这里我省略了切换到调度程序的过程)。切换操作就是保存 $B$ 的上下文到 $B$ 的内核栈，这没什么问题，还有就是恢复 $A$ 的上下文，恢复上下文的操作就是弹栈，而弹栈那也得有东西弹是吧，而刚才似乎只分配了栈空间里面并没有什么内容？
由此，就捋出来了，我们需要对新进程的内核栈里面填充上下文，填充切换上下文以便切换的时候需要，填充中断上下文，以便从内核回到用户态的时候需要。其中断上下文是复制的父进程的，这在后面会看到，而切换上下文才是模拟填充的。
有了上述了解，回到 $allocproc$ 函数：
sp -= sizeof *p->tf;
p->tf = (struct trapframe*)sp;
这里就是先在栈中预留出中断栈帧的空间，然后将中断栈帧的地址记录在 $PCB$ 里面。这里说明了分配的空栈里面首先存放的是中断栈帧，根据前面的进程切换我们知道在回到用户态的时候需要恢复中断上下文，就是将中断栈帧里面的东西给弹出去。弹出去之后内核栈就变为空栈了，所以对于内核栈，不论中间情况多么复杂，但是栈底部分一定是中断上下文，退出内核时恢复中断上下文又会使得内核栈空。
sp -= 4;
*(uint*)sp = (uint)trapret;
这一步将中断返回程序的地址放进去
sp -= sizeof *p->context;
p->context = (struct context*)sp;
memset(p->context, 0, sizeof *p->context);
p->context->eip = (uint)forkret;
这一步模拟内核态上下文的内容，$eip$(返回地址) 填写为 $forkret$ 函数地址
所以当该进程被调度的话，会先去执行 $forkret$ 函数，执行完之后再返回执行中断返回函数，中断返回后就回到用户态执行用户程序了。这部分详见前文中断@@@@@@@@@@
上述为分配任务结构体，分配内核栈，模拟上下文的过程，接着来看 $fork$ 函数：
复制数据创建页表
if((np->pgdir = copyuvm(curproc->pgdir, curproc->sz)) == 0){
kfree(np->kstack);
np->kstack = 0;
np->state = UNUSED;
return -1;
}
$copyuvm$ 函数会复制父进程用户空间的数据并创建新的页表。如果复制过程中出错，回收上面分配的一切资源再返回。
pde_t* copyuvm(pde_t *pgdir, uint sz) {
/***********略**********/
if((d = setupkvm()) == 0) //构造页表的内核部分，内核部分都是一样的
return 0;
for(i = 0; i < sz; i += PGSIZE){
//循环用户部分sz
if((pte = walkpgdir(pgdir, (void *) i, 0)) == 0) //返回这个地址所在页的页表项地址，判断是否存在
panic("copyuvm: pte should exist"); //为0表示不存在,panic
if(!(*pte & PTE_P)) //判断页表项的P位
panic("copyuvm: page not present"); //如果是0表不存在，panic
pa = PTE_ADDR(*pte); //获取该页的物理地址
flags = PTE_FLAGS(*pte); //获取该页的属性
if((mem = kalloc()) == 0) //分配一页
goto bad;
memmove(mem, (char*)P2V(pa), PGSIZE); //复制该页数据
if(mappages(d, (void*)i, PGSIZE, V2P(mem), flags) < 0) {
//映射该物理页到新的虚拟地址
kfree(mem); //如果出错释放
goto bad;
}
}
return d; //返回页目录虚拟地址
bad:
freevm(d); //释放页目录d指示的所有空间
return 0;
}
进程在用户空间可以使用 $2GB$，但实际只用了 $sz$，这个值记录在进程结构体中，前文数据结构篇对这个值做了讲解，因为加载程序的时候以 0 为起始地址，所以 $sz$ 既表示当前进程在用户空间的大小又表示进程用户部分的末尾地址。
而 $copyuvm$ 就是将这部分全部复制一份到子进程从 0 的虚拟地址空间，并建立映射关系创建一个新页表。这说明了父子进程的虚拟地址空间是一样的，但映射到了不同的物理地址空间。整个流程应该还是挺清晰的：
根据父进程的页表得到用户部分虚拟页的物理地址
给子进程分配物理页，复制数据
- 映射 虚拟页和新分配的物理页
重复上述过程就是复制数据到新进程的用户空间以及创建新页表的过程，这里还有个隐含的注意点，上面一段代码乍一看挺简单的，但是想想这个问题，复制数据的时候相当于是将一个用户空间的数据搬运到另一个用户空间去了，而每个进程的虚拟地址空间是独立的，我们常用的 $memmove$、$memcpy$ 等函数都是在同一个虚拟地址空间进行的，是不能跨越空间的。
那如何解决呢？这里是用内核作为中转，所以仔细看上述的 $memmove$ 的使用，两个地址参数都是内核地址，两个虚拟空间的地址都转化成了内核地址，然后再做数据的搬运。这里我就点到为止，如果有些许疑惑，我在后面的加载程序部分有详细的说明，因为加载程序部分有专门的函数，所以我放在那边详述。
复制文件描述符表，共享文件表
回到 $fork$ 函数，我稍微调整了一下源码的顺序，便于讲述。
for(i = 0; i < NOFILE; i++)
if(curproc->ofile[i])
np->ofile[i] = filedup(curproc->ofile[i]);
np->cwd = idup(curproc->cwd);
父子进程都有文件描述符表这个结构，$fork$ 复制一份父进程的文件描述符表给子进程，这里虽然将文件描述符表复制了一份，但是文件描述符表里面存放的是指针，指向文件表，所以它两就是共享文件表。
最后修改子进程的当前工作路径为父进程的路径，所有的这些文件管理都要调用专门的复制函数 $dup$，因为文件系统对文件系统的引用数链接数有着严格的管理，详见 文件系统调用。
修改进程结构体
np->sz = curproc->sz; //用户部分的大小
np->parent = curproc; //子进程的父进程是当前进程
*np->tf = *curproc->tf; //子进程的栈帧就是父进程的栈帧
// Clear %eax so that fork returns 0 in the child.
np->tf->eax = 0; //将中断栈帧的eax值修改为0
safestrcpy(np->name, curproc->name, sizeof(curproc->name)); //复制进程名字
pid = np->pid; //进程号，这是返回用的
acquire(&ptable.lock);
np->state = RUNNABLE; //子进程可以跑了!!!
release(&ptable.lock);
return pid;
前面分配和初始化内核栈的时候只是预留了中断栈帧的空间，没有对其初始化，在这里直接将父进程的中断栈帧给复制了一份过来。中断栈帧是中断上下文，$fork$ 就是克隆出一个一模一样的进程，在前面已经复制了父进程用户空间的数据，这里再复制父进程的中断上下文(用户态下的现场)，如此待到中断退出恢复上下文后，父子进程就是运行一样的程序(因为复制了用户空间的数据)并且从相同的地方开始执行(因为复制了用户级上下文)。
为什么没有复制切换上下文？切换上下文是进程切换的时候产生的，执行 $fork$ 函数的时候怎么可能执行切换函数呢是吧，所以这里与进程切换没什么关系，主要是创建的子进程要想被调度上 $CPU$，需要模拟填充上下文。这部分后面会有图解
另外中断栈帧里面的上下文也不是原封不动的复制过来，修改了 $eax$ 的值，$eax$ 里面为返回值，将其修改为 0，这就是为什么对于子进程来说 $fork$ 返回值为 0 的原因。
代码剩余的部分就是对进程的名字，状态的处理，很简单，不再多说。
到此一个进程就创建好了，可以看出这简单版本的 $fork$ 实现起来还是很简单的，无非就是将父进程的所有东西全部复制一遍，除了上下文，进程号不大相同之外，其他的可以说是一模一样，$fork$ 函数就到这里，最后来看一张图
这张图显示了 $fork$ 主要复制了哪些数据。下面来看看子进程被创建后第一次被调度而后回到用户态的情景
子进程回到用户态
子进程的内核栈里面包括我们模拟填充的上下文，当它被调度上 $CPU$ 执行的时候，具体的就是执行 $swtch$ 后，$forkret(eip)$ 就会被加载到 $EIP$，然后执行 $forkret$：
void forkret(void){
static int first = 1;
release(&ptable.lock); //解锁
if (first) {
//第一次执行？
first = 0;
iinit(ROOTDEV); //初始化inode
initlog(ROOTDEV); //初始化日志
}
}
$forkret$ 这个函数对于普通进程来说就是个空函数，这里普通函数是对于第一个进程来说的，第一个进程后面讲述，再者这个函数涉及到了释放 $ptable.lock$ 的操作，锁的问题也在后面集中讲述。所以这里就当作是个空函数就行了。
执行完之后去用户栈获取返回地址 $trapret$，随后执行 $trapret$，$trapret$ 就是中断退出函数，将中断栈帧里面的上下文给弹出去，最后执行 $iret$ 退出中断回到用户态。这部分详见中断部分
到此 $fork$ 函数讲述完毕，$fork$ 主要是来创建普通进程，而第一个创建放在加载程序之后比较合适，本篇就先不讲述。
好了本文到这儿也结束了，本文主要讲述了进程的创建与切换，虽然是反着讲的，但影响应该不大。普通进程的创建没什么技巧，$fork$ 将父进程的“所有东西”赋值一份，而它想要被正确被调度执行切换函数的话，就需要将这个新进程模拟成旧进程为它填充切换上下文。而且最主要的是在内核里面放好要执行的函数地址。
加载程序
使用分身术($fork$)创建出来的进程执行的是与父进程相同的程序，通常不是咱们想要的，咱们想要的是子进程去执行不同的程序，这就需要学会另一门技能变身术($exec$)
$exec$ 负责磁盘上的文件程序装载到内存里面去，创建新的内存映像，这个过程说简单也简单，说复杂也复杂。因为 $elf$ 文件里面包括了可装载段的所有信息：比如这个段多大，要加载哪里去，都记录好了，$exec$ 需要做的就是从磁盘读数据，然后将数据搬到对应位置。复杂就在于这个过程有些繁复，咱们一步步来看：
int exec(char *path, char **argv);
参数有两个：$path$ 为文件路径，$argv$ 为指向字符串数组的指针
if((ip = namei(path)) == 0){
//获取该文件的inode
end_op();
cprintf("exec: fail\n");
return -1;
}
ilock(ip); //对该inode上锁，使得数据有效
这一步就是解析路径然后取得该文件的 $inode$，如果失败则返回，成功的话将该 $inode$ 上锁使用，同时 $ilock$ 会使 $inode$ 的数据有效，$inode$ 部分详见前文 @@@@@@@@@@
if(readi(ip, (char*)&elf, 0, sizeof(elf)) != sizeof(elf)) //读取elf头
goto bad;
if(elf.magic != ELF_MAGIC) //判断文件类型
goto bad;
//#define ELF_MAGIC 0x464C457FU // "\x7FELF" in little endian
$elf$ 前 4 个字节分别是 0x7F, 'E', 'L', 'F'，如果一个文件前 4 个字节是这 4 个东东，说明它是一个 $elf$ 文件。
if((pgdir = setupkvm()) == 0)
goto bad;
建立新页表的内核部分，原页表是旧进程的，这里创建一个新的属于自己的页表，也就是创建了一个新的虚拟地址空间。
接下来就是读取可装载段的数据，然后”搬”到新的地址空间。目前的虚拟地址空间就只映射了内核部分，用户部分没有映射到实际的物理内存，要把数据搬到用户部分，在这之前肯定得有一个分配物理内存，然后将用户部分的虚拟内存映射到分配的物理内存的过程，这就是 $allocuvm$ 函数。
分配虚拟内存
int allocuvm(pde_t *pgdir, uint oldsz, uint newsz);
$allocuvm$ 在 $pgdir$ 指向的虚拟地址空间中，分配 $newsz - oldsz$ 大小的虚拟内存，返回 $newsz$。分配虚拟内存就是上述所说的那两步：分配物理内存，填写页表项建立映射，来看具体实现：
a = PGROUNDUP(oldsz); //4K对齐
for(; a < newsz; a += PGSIZE){
mem = kalloc(); //分配物理内存
if(mem == 0){
//如果分配失败
cprintf("allocuvm out of memory\n");
deallocuvm(pgdir, newsz, oldsz); //回收newsz到oldsz这部分空间
return 0;
}
memset(mem, 0, PGSIZE); //清除内存中的数据
if(mappages(pgdir, (char*)a, PGSIZE, V2P(mem), PTE_W|PTE_U) < 0){
//填写页表项建立映射
cprintf("allocuvm out of memory (2)\n"); //如果建立映射失败
deallocuvm(pgdir, newsz, oldsz); //回收newsz到oldsz这部分空间
kfree(mem); //回收刚分配的mem这部分空间
return 0;
}
}
return newsz;
整个流程就是我说的那两步，如果其中哪一步出错，就调用 $deallocuvm$ 函数将已分配的空间回收，$deallocuvm$ 就完全是 $allocuvm$ 的逆操作，释放回收空间之后清除页表项，这里就不再赘述。
因为程序在内存中的虚拟地址是从 0 开始的，所以 $size$ 值不止是程序大小，也是程序末尾的地址，而 $allocuvm$ 分配的虚拟内存就是接着当下程序的大小 $oldsize$ 开始分配的，所以 $allocuvm$ 函数的作用如下图所示：
“搬运”数据
int loaduvm(pde_t *pgdir, char *addr, struct inode *ip, uint offset, uint sz){
if((uint) addr % PGSIZE != 0) //地址必须是对齐的
panic("loaduvm: addr must be page aligned");
for(i = 0; i < sz; i += PGSIZE){
if((pte = walkpgdir(pgdir, addr+i, 0)) == 0) //addr+i地址所在页的页表项地址
panic("loaduvm: address should exist");
pa = PTE_ADDR(*pte); //页表项记录的物理地址
if(sz - i < PGSIZE) //确定一次能够搬运的字节数
n = sz - i;
else
n = PGSIZE;
if(readi(ip, P2V(pa), offset+i, n) != n) //调用readi将数据搬运到地址P2V(pa)处
return -1;
}
return 0;
}
从磁盘搬运数据到内存就是对 $readi$ 函数的封装，$readi$ 函数会根据文件 $inode$ 将数据读取到相应位置，有关 $readi$ 函数详见 $inode$ 部分。
有了上述的了解之后，回到 $exec$ 函数：
sz = 0;
for(i=0, off=elf.phoff; i<elf.phnum; i++, off+=sizeof(ph)){
if(readi(ip, (char*)&ph, off, sizeof(ph)) != sizeof(ph)) //读取程序头
goto bad;
if(ph.type != ELF_PROG_LOAD) //如果是可装载段
continue;
if(ph.memsz < ph.filesz) //memsz不应该小于filesz
goto bad;
if(ph.vaddr + ph.memsz < ph.vaddr) //memsz也不应该是负数
goto bad;
if((sz = allocuvm(pgdir, sz, ph.vaddr + ph.memsz)) == 0) //分配sz到ph.vaddr + ph.memsz之间的虚拟内存
goto bad;
if(ph.vaddr % PGSIZE != 0) //地址应该是对齐的
goto bad;
if(loaduvm(pgdir, (char*)ph.vaddr, ip, ph.off, ph.filesz) < 0) //从磁盘搬运filesz字节的数据到vaddr
goto bad;
}
这段代码就是装载程序的过程，有上述的铺垫之后整个流程应该是非常的清晰，如果不是，可能是对 $elf$ 文件不太熟悉，我在ELF 文件讲述了一定的 $elf$ 文件，本文就不赘述了。只是提一个比较重要的点：$filesz < memsz$，也就是一个段在磁盘上占据的空间大小是要小于装载到内存后的大小的，这是因为 $.bss$ 节的存在，$.bss$ 存放未初始化的全局变量或初始化为 0 的全局变量，它不占据实际的磁盘空间，只是一个占位符，但是加载到内存时，也要为这些变量分配空间，所以 $filesz < memsz$
上述将程序从磁盘装载到内存，接着就应该为该进程分配资源准备运行环境了，
分配用户栈
sz = PGROUNDUP(sz); //size对齐
if((sz = allocuvm(pgdir, sz, sz + 2*PGSIZE)) == 0) //分配两页虚拟内存
goto bad;
clearpteu(pgdir, (char*)(sz - 2*PGSIZE)); //清除第一页的页表项USER位，使得用户态下不可访问
sp = sz;
首先将 $sz$ 向上取整，进程在内存中的映像各个段都是 $4K$ 对齐的，这里栈段也不例外，所以其实各个段之间并不是挨在一起的，如果不是刚好对齐，那么其间是有缝隙的。
调用 $allocuvm$ 分配两页虚拟内存，“高页”作为栈，因为栈是向下扩展的所以"低页"作为保护页。所谓保护页就是将这页对应的页表项 $USER$ 属性位置 0，置 0 之后用户态就不能访问这个页。
将目前的程序大小赋值给 $sp$，$sp$ 就是未来的栈指针，现下程序的内存映像如下图所示：
准备参数
要运行的程序从 $main$ 函数开始，$main$ 函数有两个参数：
- $argc$ 是参数个数
- $argv$ 一个指向字符串数组的指针
在这一部分我们需要将 $main$ 函数的这两个参数以及 $argv$ 指向的那些字符串“搬运”到栈里面。因为 $main$ 函数也是个函数，是函数就要遵循调用约定，将 $main$ 需要的参数压栈，先来看看参数布局图：
搬运参数是个很有意思的事，它不像前面从磁盘搬运数据到内存，磁盘对于每个进程来说共享的，进程 A 将数据从磁盘搬运到 进程 B 的地址空间，没问题，一个 $readi$ 函数搞定。但是搬运参数不太一样，参数位于在进程 $A$ 的地址空间，目的地在进程 $B$ 的地址空间，两个空间独立不互通，没办法直接搬运。
咋个办？很自然的想法就是要找一个两者共享互通的地儿来中转，这个地方就是内核，将内核当作中转站，来看相关函数实现：
char* uva2ka(pde_t *pgdir, char *uva)
{
pte_t *pte;
pte = walkpgdir(pgdir, uva, 0);
if((*pte & PTE_P) == 0)
return 0;
if((*pte & PTE_U) == 0)
return 0;
return (char*)P2V(PTE_ADDR(*pte));
}
这个函数将用户部分的虚拟地址转化为内核虚拟地址，初看这句话是不是觉得挺荒谬？可事实的确如此，要理解这点，就要深入理解 $xv6$ 内存的管理方式，再来看遍这张图：
内核部分(不是全部)映射到了物理内存的 $0-PHYSTOP$，用户部分映射到物理内存的空闲部分，所以物理内存的空闲部分既映射到了用户部分又映射到了内核部分。两个值相同的用户部分虚拟地址对应的物理地址是不同的，但是两个值相同的内核部分虚拟地址对应的物理地址确实相同的。
内核虚拟地址与物理地址之间就相差一个 $KERNBASE(0x8000 0000)$，所以内核虚拟地址转物理地址不需要查页表，减去 $KERNBASE$ 就是物理地址值。相反，物理地址加上 $KERNBASE$ 就是它在内核的虚拟地址
但是用户部分的虚拟地址没有直接对应关系，地址转换必须查页表，用户部分的虚拟地址转换成物理地址，之后再加上 $KERNBASE$ 就是转化到内核的虚拟地址了。上述函数就是做的这件事。
用户虚拟地址与内核虚拟地址转换之后就可以进行参数的搬运了，来看：
int copyout(pde_t *pgdir, uint va, void *p, uint len)
{
char *buf, *pa0;
uint n, va0;
buf = (char*)p;
while(len > 0){
va0 = (uint)PGROUNDDOWN(va);
pa0 = uva2ka(pgdir, (char*)va0); //va0在pgdir的映射下的内核地址
if(pa0 == 0)
return -1;
n = PGSIZE - (va - va0); //一次搬运的字节数
if(n > len)
n = len;
memmove(pa0 + (va - va0), buf, n); //从buf搬运n字节
len -= n;
buf += n;
va = va0 + PGSIZE;
}
return 0;
}
代码初看可能有些麻杂，这里举个例子，现下我要从进程 $A$ 用户部分的地址 $va_a_u$ 搬运 n 字节到进程 $B$ 用户部分的地址 $va_b_u$ 处，要做些什么呢？
- 调用 $uva2ka$ 将 $va_b_u$ 转化为内核虚拟地址 $va_b_k$
- 调用 $memmove$ 从 $va_a_u$ 搬运 n 字节到 $va_b_k$ 处
看似将数据搬运到了内核 $va_b_k$，但是 $va_b_k$ 又对应着 $va_b_u$，所以从逻辑上讲的确是将数据从 $va_a_u$ 搬运到了 $va_b_u$
有了上述了解接着来看 $exec$ 函数：
uint ustack[3+MAXARG+1];
//#define MAXARG 32 // max exec arguments
for(argc = 0; argv[argc]; argc++) {
if(argc >= MAXARG)
goto bad;
sp = (sp - (strlen(argv[argc]) + 1)) & ~3; //栈指针向下移准备放字符串，保证4字节对齐
if(copyout(pgdir, sp, argv[argc], strlen(argv[argc]) + 1) < 0) //搬运字符串
goto bad;
ustack[3+argc] = sp; //记录字符串在栈中的地址
}
这部分搬运字符串到新的用户空栈里面，是字符串，不是参数。栈指针向下移动，留出的空间放字符串，这部分空间首地址地址要满足 $4$ 字节对齐，将地址记录在 $ustack$ 中。
ustack[3+argc] = 0;
ustack[0] = 0xffffffff; // 假的返回地址
ustack[1] = argc; //参数
ustack[2] = sp - (argc+1)*4; // argv pointer 参数
sp -= (3+argc+1) * 4; //栈指针向下移
if(copyout(pgdir, sp, ustack, (3+argc+1)*4) < 0) //将字符串地址搬运到新的用户空间栈里面
goto bad;
这部分搬运参数和字符串的地址，没什么可说的，来看搬运完之后的图：
回来继续看 $exec$ 函数：
for(last=s=path; *s; s++) //解析程序名
if(*s == '/')
last = s+1;
safestrcpy(curproc->name, last, sizeof(curproc->name)); //strncpy
这部分根据 $exec$ 的参数路径修改进程名字，路径本就是一个个文件名组合而成，最后一项就是程序的名称。
oldpgdir = curproc->pgdir; //旧页目录
curproc->pgdir = pgdir; //换新页目录
curproc->sz = sz; //更改程序大小
curproc->tf->eip = elf.entry; //设置执行的入口点
curproc->tf->esp = sp; //新的用户栈顶
switchuvm(curproc); //切换页表
freevm(oldpgdir); //释放旧的用户空间
return 0;
这部分修改进程任务结构体的一些属性，将栈帧中的 $eip$ 修改为 $elf$ 的入口点，当进程在此被调度时就会从这儿开始执行。
$freevm$ 用来释放用户空间映射的所有物理内存和页表本身占用的内存，来看如何实现的：
void freevm(pde_t *pgdir)
{
uint i;
if(pgdir == 0)
panic("freevm: no pgdir");
deallocuvm(pgdir, KERNBASE, 0); //free 用户空间映射的物理内存
for(i = 0; i < NPDENTRIES; i++){
//free 页表占用的物理内存
if(pgdir[i] & PTE_P){
char * v = P2V(PTE_ADDR(pgdir[i]));
kfree(v);
}
}
kfree((char*)pgdir); //free 页目录占用的物理内存
}
过程很清晰，涉及到的函数前面也说过了，分为三步，注释已经标明。这一部分就将进程原本的内存映像全部给删掉了，被新的映像替换掉。
返回
$exec$ 的最后一部分我们来讨论返回相关的问题，$exec$ 是个系统调用，系统调用的流程在前文系统调用如何实现的时候出过一张图，当时是用 $write$ 为例子来说的，这里在来看一眼：
每个系统调用的基本流程都是差不多的，如上图所示，这里我们主要关注返回的部分，当内核功能函数(系统调用实际工作的函数)执行完后，就会去内核栈获取返回地址：$trapret$ 中断退出函数的地址，执行这个函数就是中断退出操作，最后一条指令为 $iret$，执行之后就返回到用户态。
但是 $exec$ 有所不同，举个例子，进程内存映像 $a$ 的某个函数调用了 $exec$，随后进入内核后执行 $sys_exec$ 这个实际的功能函数，$sys_exec$ 创建了一个新的内存映像 $b$，$sys_exec$ 执行完之后同样的去内核栈获取返回地址：$trapret$，但是执行这个函数不会返回原来的内存映像 $a$，而是返回到新的内存映像 $b$，因为 $a$ 已经没了，原因如下：
- 用户级上下文 $trapframe$ 的 $eip$ 已经修改为 $elf$ 的入口点
- 用户栈指针已经修改为新用户栈顶
- 切换到了新页表，旧页表已经释放，页表就可以看作虚拟地址空间。
来看看 $exec$ 系统调用的过程图：
再来看看 $exec$ 实际干了哪些事情的流程图：
好了 $exec$ 到此结束，这条线捋得应该还是蛮清晰得。
创建第一个进程
有了前面创建普通进程和程序加载的铺垫，创建第一个进程是很简单的，相关代码在 $proc.c/userinit$。第一个进程就像是 fork 和 exec 得结合体，因为是第一个，也就没有父进程得内存映像克隆，所以要调用 $exec$ 来加载 $init$ 程序。$xv6$ 得实际情况稍有不同，它是先加载一个 $initcode$ 程序，这个程序再调用 $exec$ 加载 $init$ 程序。来看实际源码：
void userinit(void)
{
struct proc *p;
extern char _binary_initcode_start[], _binary_initcode_size[];
p = allocproc(); //分配任务结构体，预留上下文空间
initproc = p;
if((p->pgdir = setupkvm()) == 0) //建立页表的内核部分
panic("userinit: out of memory?");
inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size); //初始化虚拟地址空间，将initcode程序装进去
p->sz = PGSIZE;
这一部分分配任务结构体，然后调用 $inituvm$ 初始化虚拟地址空间，将 $initcode$ 程序装进去。$initcode$ 程序是进程回到用户空间要执行的初始化程序，程序要在用户空间运行，就要在用户空间分配内存然后将相应的程序加载进去，这就是 $inituvm$ 所作的事情，来看码：
void inituvm(pde_t *pgdir, char *init, uint sz)
{
char *mem;
if(sz >= PGSIZE)
panic("inituvm: more than a page");
mem = kalloc(); //分配一页物理内存
memset(mem, 0, PGSIZE); //清零
mappages(pgdir, 0, PGSIZE, V2P(mem), PTE_W|PTE_U); //映射到虚拟地址空间0-4KB
memmove(mem, init, sz); //将要运行的初始化程序搬到0-4KB
}
$inituvm$ 所做的事情具体如下：
- 分配一页物理内存清零
- 将这页物理内存映射到虚拟地址空间的 $0-4KB$
- 将二进制初始化程序加载到 $0-4KB$ 这个区域
在 $exec$ 里面我们是加载的 $elf$ 文件的可装载段，这里初始化 $initcode$ 程序在编译的时候没有编译成 $elf$ 可执行文件，而是编译成了只有机器码的二进制文件，没有多余的信息，可以直接加载到内存运行，而不像 $elf$ 文件只能加载可装载部分而后运行。$initcode$ 也不是一个单独的程序文件，与其他一些东西一起编译成了整个内核文件，所以直接使用 $memmove$ 就可。具体的原因可以去看看 $Makefile$，这里不赘述了。
接着回到 $userinit$ 函数：
p->sz = PGSIZE;
memset(p->tf, 0, sizeof(*p->tf));
p->tf->cs = (SEG_UCODE << 3) | DPL_USER;
p->tf->ds = (SEG_UDATA << 3) | DPL_USER;
p->tf->es = p->tf->ds;
p->tf->ss = p->tf->ds;
p->tf->eflags = FL_IF;
p->tf->esp = PGSIZE;
p->tf->eip = 0; // beginning of initcode.S
在 $allocproc$ 中预留了中断栈帧的空间，这里填充内容，代码段选择子为用户代码段选择子，数据段选择子为用户数据段选择子，栈段 $SS$ 附加数段 $ES$ 等等都共用数据段的选择子。设置栈帧中的 $eflags$ 的 $IF$ 位，当中断退出将其弹到 $EFLAGS$ 寄存器之后就会允许响应中断。
对这个临时的初始化程序并没有专门为它分配一个用户栈，而是直接使用映射的 $0-4KB$ 的高地址，将 $4KB$ 作为栈底，后面我们会看到这个初始化程序很小，所以这样用没有问题。
栈帧里面的 $eip$ 设置为 0，因为从前面的 $inituvm$ 程序中能够看到，它是将 $initcode$ 搬到了 0 地址处，它跟 $elf$ 文件不同有个专门的入口点，这里直接就从头开始执行，所以 $eip$ 设置为 0 就可。
safestrcpy(p->name, "initcode", sizeof(p->name)); //进程名字
p->cwd = namei("/"); //工作在根目录
acquire(&ptable.lock);
p->state = RUNNABLE; //修改状态为RUNNABLE
release(&ptable.lock);
}
最后这一部分就很简单了，跟 $fork$ 一样，设置进程的名字工作路径和状态，没多少说的。
来看第一个进程刚加载 $initcode$ 程序准备执行时的内存映像示意图：
这第一个进程被调度上 $CPU$ 执行的第一个函数就是 $forkret$，这个函数我们前面说过如果如果是普通函数的话就可以看作一个空函数，但如果是第一个函数的话，会做实际的事情：
void forkret(void)
{
static int first = 1;
release(&ptable.lock);
if (first) {
first = 0;
iinit(ROOTDEV); //初始化inode
initlog(ROOTDEV); //初始化日志，从日志记录中恢复数据，保持磁盘数据的一致性
}
}
主要就是做两件事：
- 初始化 $inode$，主要是对 $inode$ 的锁的初始化
- 初始化日志，并且从日志记录中恢复数据，保证磁盘数据的一致性。
$forkret$ 是每个新进程被调度后都要执行的一个函数，它不是 $initcode$ 中的函数，下面来看看这个 $initcode$ 程序做了啥：
.globl start
start:
pushl $argv #压入参数argv
pushl $init #压入参数路径init
pushl $0 #无效返回地址
movl $SYS_exec, %eax #exec系统调用号
int $T_SYSCALL #执行系统调用
# for(;;) exit(); 正常情况不会执行到这
exit:
movl $SYS_exit, %eax #exit系统调用号
int $T_SYSCALL #执行exit系统调用
jmp exit
# char init[] = "/init\0"; 准备exec第一个参数路径
init:
.string "/init\0"
# char *argv[] = { init, 0 }; 准备exec第二个参数字符串数组
.p2align 2
argv:
.long init
.long 0
所以 $initcode$ 程序就是调用 $exec$ 去加载 $init$ 程序，这段代码本身应该是很好懂的，如果不太明白，可以回看前面关于 $exec$ 的讲解以及前文系统调用。
这里只说一点 $exec$ 如果执行成功是不会返回执行 $exit$ 函数的，原因在 $exec$ 那块已说过。最后来看 $init$ 程序是什么样子的，其中有些东西我还没说过，所以这里就看个大概流程：
int main(void)
{
int pid, wpid;
if(open("console", O_RDWR) < 0){
//打开控制台
mknod("console", 1, 1);
open("console", O_RDWR);
}
dup(0); // stdout
dup(0); // stderr
for(;;){
printf(1, "init: starting sh\n");
pid = fork(); //fork一个子进程
if(pid < 0){
printf(1, "init: fork failed\n");
exit();
}
if(pid == 0){
//子进程运行shell
exec("sh", argv);
printf(1, "init: exec sh failed\n");
exit();
}
while((wpid=wait()) >= 0 && wpid != pid) //wait()
printf(1, "zombie!\n");
}
}
$init$ 程序主要做两件事：
- 打开控制台文件，然后 $fork$ 出一个子进程运行 $shell$ 程序
- $wait$ 子进程，其中就包括孤儿进程
好了，第一个进程就讲述这么多，来看张总图结束：
休眠与唤醒
休眠我们前面提到了很多次，今天在这里得见它们的真身，休眠和唤醒两者本身一点都不复杂，甚至可以说是简单，难就难在用锁来同步，关于锁的问题咱们后面几种讨论，这里先来看休眠唤醒的实际操作部分
void sleep(void *chan, struct spinlock *lk);
void wakeup(void *chan);
进入休眠
$sleep$ 原型：
void sleep(void *chan, struct spinlock *lk);
$sleep$ 使进程休眠在某个对象 $chan$ 上面，$lk$ 是管理这个对象的锁，但不一定归 $chan$ 所有，比如 sleep(curproc, &ptable.lock)，所有任务结构体表就一把锁，用来管理任务结构体，而比如 sleep(&log, &log.lock)，这把锁就是 $log$ 所独有的。
要注意我们这里所说的休眠 $sleep$ 不是系统调用 $sleep$，为避免冲突我后面说 $sleep_sys$ ($sys_sleep$ 是实际存在的内核函数) 。$xv6$ 的代码就是有这问题，一些用户接口，内核函数，还有个别文件里面的函数取名一样，但是我们实际看码的时候要区别对待。$sleep_sys$ 是根据这里的 $sleep$ 实现的，简单提一句，每次时钟中断都会增加滴答数，根据滴答数就可以判断休眠的时间到没，如果没到就持续调用 $sleep$ 来休眠。实现原理很简单的，可以自行看一下，本文就不多说了，这里主要还是看具体的休眠是如何进行的。
void sleep(void *chan, struct spinlock *lk){
/*********略**********/
p->chan = chan; //休眠在chan上
p->state = SLEEPING; //状态更改为SLEEPING
sched(); //让出CPU调度
p->chan = 0; //休眠对象改为0
/*********略**********/
}
整个 $sleep$ 函数实际就做了这么点事，设置当前进程休眠对象和状态，然后再调用 $sched$ 让出 $CPU$，从 $sched$ 返回的时候表示当前进程已经休眠完了并再次被调度上了 $CPU$，此时不再是休眠状态所以将休眠对象更改为 0 表没有。
退出休眠
static void wakeup1(void *chan)
{
struct proc *p;
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
if(p->state == SLEEPING && p->chan == chan) //寻找休眠状态且休眠在chan上的进程
p->state = RUNNABLE; //将其状态更改为RUNNABLE
}
唤醒操作就更简单了，挨个查询任务结构体，寻找状态为 $SLEEPING$ 且休眠对象为参数 $chan$ 的进程，然后将其状态更改为 $RUNNABLE$，表示这个进程被唤醒又可以被调度上 $CPU$ 了。
可以看出进入休眠状态和退出休眠状态是很简单的，简单到不需要多做解释，只是注意调用 $sched$ 之后是不会返回的，而是去执行其他进程了，这就是休眠的好处，提高 $CPU$ 的利用率。
等待与退出
父进程等待子进程退出，$wait$ 和 $exit$ 这两个函数其实都主要来释放资源的，$exit$ 是子进程自己调用，释放一部分资源，但是肯定是释放不完的，因为执行 $exit$ 函数本身就需要资源，比如栈，所以 $exit$ 只能释放一部分，剩下的交给父进程调用 $wait$ 来处理。
子进程退出
void exit(void){
struct proc *curproc = myproc();
if(curproc == initproc)
panic("init exiting");
第一个进程是不能退出的，它有特殊作用，比如回收孤儿进程的资源。
for(fd = 0; fd < NOFILE; fd++){
if(curproc->ofile[fd]){
fileclose(curproc->ofile[fd]);
curproc->ofile[fd] = 0;
}
}
这一部分关闭所有文件，如果减到 0，再释放该文件的 $inode$，如果文件的链接数和引用数都为 0 了，就删除该文件。详见 文件系统调用
begin_op();
iput(curproc->cwd); //放下当前工作路径的inode
end_op();
curproc->cwd = 0; //当前工作路径设为0表空
这一部分释放当前工作路径的 $inode$，工作路径就是个目录，将其设为 0 表空。另外涉及磁盘读写的操作都要用日志系统来保证原子操作，文件操作不细说，有问题见前文。
acquire(&ptable.lock); //取锁
wakeup1(curproc->parent); //唤醒父进程
父进程可能因为 $wait$ 调用休眠，这里唤醒，锁的问题后面一起说
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
//将被遗弃的孩子过继给init进程
if(p->parent == curproc){
p->parent = initproc;
if(p->state == ZOMBIE)
wakeup1(initproc);
}
}
如果将要退出的进程有子进程，这些进程就会变成孤儿进程，因为当前进程(它们的父进程)要退出了，不管它们了，不会调用 $wait$ 来为他们善后回收进程了，所以叫做孤儿进程。孤儿进程也是需要处理的，将它们全部过继给 $init$ 进程，如果其中有处于僵尸状态的进程，则唤醒 $init$ 进程让其立即处理。
curproc->state = ZOMBIE; //状态变为僵尸状态
sched(); //调度，永远不会返回
panic("zombie exit"); //因为不会返回，正常情况是不可能执行到这的
}
进程的状态变为僵尸态，父进程的 $wait$ 会来处理僵尸态的进程，$sched$ 之后是不会再返回的，因为能被调度的只有 $RUNNABLE$ 的进程，况且该进程被父进程的 $wait$ 处理之后，该进程都不存在了，何来返回一说？
等待子进程退出
$wait$ 函数主要就是寻找状态为 $ZOMBIE$ 的进程，找到一个就回收它的资源，来看码
for(;;){
//"无限循环"
havekids = 0;
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
//循环寻找子进程
if(p->parent != curproc) //如果进程p的父进程不是当前进程
continue;
havekids = 1; //当前进程有子进程
if(p->state == ZOMBIE){
//如果子进程的状态是ZOMBIE，回收它的资源
// Found one.
pid = p->pid;
kfree(p->kstack); //回收内核栈
p->kstack = 0;
freevm(p->pgdir); //回收用户空间以及页表占用的五ii内存
p->pid = 0;
p->parent = 0;
p->name[0] = 0;
p->killed = 0;
p->state = UNUSED; //状态变为UNUSED,表该结构体空闲了
release(&ptable.lock); //释放锁
return pid;
}
}
这部分是如果当前进程有子进程且状态为 $ZOMBIE$ 的话，就回收它的资源
if(!havekids || curproc->killed){
release(&ptable.lock);
return -1;
}
这部分是如果当前进程没有子进程或者当前进程被杀死了了，释放锁，返回 $-1$ 表出错了。$kill$ 与锁的问题后面详述
sleep(curproc, &ptable.lock); //DOC: wait-sleep
}
这部分是如果当前进程有子进程，但是子进程还没有退出，父进程休眠等待子进程退出。
上述就是 $wait$ 与 $exit$ 函数，可以看出两者的主要工作的确就是回收子进程的资源，当然还有其他工作，比如如果要退出的进程有子进程，则将其子进程过继给 $init$ 进程。
有了上述的了解再来看状态变化图应该有更深刻的理解：
$KILL$
$exit$ 是一个进程主动调用然后退出，$kill$ 是一个进程强迫另一个进程调用 $exit$ 退出。每个任务结构体都有个 $killed$ 属性，将其置 1 就表示该进程被 “杀死” 了，但实际还未实际进行 $kill$ 这个操作
int kill(int pid)
{
struct proc *p;
acquire(&ptable.lock); //取锁
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
//循环寻找pid号进程
if(p->pid == pid){
//找到了
p->killed = 1; //killed置1
// Wake process from sleep if necessary.
if(p->state == SLEEPING) //如果该进程在睡瞌睡
p->state = RUNNABLE; //唤醒
release(&ptable.lock); //放锁
return 0; //返回正确
}
}
release(&ptable.lock); //放锁
return -1; //返回错误
}
$kill$ 函数就只是简单的将 $killed$ 置为 1，如果该进程在休眠，则唤醒该进程。但是 $kill$ 其实并没有将真正地杀死进程——调用 $exit$ 使其退出，那在什么地儿退出呢？
每个进程总有中断的时候，所以在中断服务总程序 $trap$ 里面检查 $killed$ 值，如果发现 $killed == 1$，则调用 $exit$ 退出：
void trap(struct trapframe *tf){
/**********略*********/
if(myproc() && myproc()->killed && (tf->cs&3) == DPL_USER) //如果被killed
exit(); //退出
if(myproc() && myproc()->state == RUNNING && //发生了时钟中断
tf->trapno == T_IRQ0+IRQ_TIMER)
yield(); //主动让出CPU
if(myproc() && myproc()->killed && (tf->cs&3) == DPL_USER) //再次检查如果被killed
exit(); //退出
}
每个进程总会有进入内核的时候，而在离开内核的时候检查 $killed$ 值，如果被 $killed$ 则调用退出，之所以检查两次是因为在 $yield$ 让出 $CPU$ 的前后都可能被 $killed$，为了更实时地杀死进程，做了两次检查，但其实后面不做检查也行，因为进程总要再此进入内核，到那时 $killed == 1$ 依然会被捕获，但及时性可能就没那么好。
另外某些情况发现 $killed==1$ 后会直接返回一个错误值，外层函数捕获到这个错误值就会 $panic$，$panic$ 在 $xv6$ 中随处可见，而 $panic$ 。而 $panic$ 就是打印一串错误消息后就冻住 $CPU$(无限循环)
再者检查 (tf->cs&3) == DPL_USER 是因为一般是从用户态进入内核后检查当前进程是否被 killed，所以栈帧里面的 $CS$ 的 $RPL$ 应为 $3$ 用户态
总之 $kill$ 就是强迫某个进程执行 $exit$
$LOCK$
锁同步的问题一直是操作系统里面最为复杂的问题之一，$xv6$ 中锁的设计在锁一篇中已经聊过，$xv6$ 的锁设计本身不难，难得是锁的使用，这里就根据进程这一块使用锁的地方来简单聊一聊。进程中与锁的有关地方主要有休眠，唤醒，等待，退出，调度，切换，一个一个地慢慢来看。
休眠唤醒
休眠是休眠在某个对象上，唤醒是唤醒休眠在某个对象上的进程，所以想当然的可以这样来声明 $sleep$ 和 $wakeup$：
void sleep(void *obj);
void wakeup(void *obj);
那这样声明对不对呢？来看个简单的变种生产者消费者的例子：
Send:
while(obj != NULL) //对象还在
; //循环
obj = 1; //制作对象
wakeup(obj); //唤醒休眠在其上的消费者
Recv:
while(obj == NULL) //没有对象可消费
sleep(obj); //休眠
obj = NULL; //消耗对象
乍一看感觉没什么问题，但是如果 $wakeup$ 发生在 $sleep$ 之前就会引起死锁:
比如中断这种典型情况：假如此时 $obj = NULL$，$Recv$ 准备休眠，但在调用 $sleep$ 前发生中断使得 $sleep$ 调用延后。这段时间内 $Send$ 在另一个 $CPU$ 上执行了，将 $obj$ 置为 1 然后唤醒休眠在 $obj$ 上的 $Recv$。而 $Recv$ 呢，中断结束后它却休眠去了，所以休眠在唤醒之后，休眠错过了唤醒，死锁。
就算不是中断，因为是多处理器，两者运行的时间是不确定的，完全也可能出现上述的情况。避免这种前后感知的信息不一致的办法就是加锁，来看第二个版本：
Send:
lock(obj_lock);
while(obj != NULL) //对象还在
; //循环
obj = 1; //制作对象
wakeup(obj); //唤醒休眠在其上的消费者
unlock(obj_lock);
Recv:
lock(obj_lock);
while(obj == NULL) //没有对象可消费
sleep(obj); //休眠
obj = NULL; //消耗对象
unlock(obj_lock);
如此，还是上述同样的情况，$Recv$ 在准备 $sleep$ 之前获得了 $obj_lock$ ，$Send$ 没有 $obj_lock$，是不可能 $wakeup$ 的，所以休眠就不会错过唤醒。
这个问题倒是解决了，又有一个新问题，如果 $Recv$ 带着 $obj_lock$ 休眠不释放的话，同样死锁。
因此将 $sleep$ 的接口定义为：
void sleep(void *obj, void *obj_lock);
将这个锁也作为 $sleep$ 的参数，在 $Recv$ 进入休眠状态时释放该锁 ，在 $Recv$ 返回时重新获取该锁。
我们需要在“进入休眠后释放该锁”，如果在这之前释放锁，可能会出现 $sleep$ 错过 $wakeup$ 的情况，原因同前。
但是都进入休眠状态了，怎么可能释放锁呢？我们在前面已经看过进入休眠状态就是修改当前进程状态为 $SLEEPING$，且让出 $CPU$，$CPU$ 都让出去了，怎么可能释放锁呢？所以释放锁还得在进入休眠状态前操作，那不是又与上面矛盾吗？因此释放锁和进入休眠状态这两个步骤得是一个原子操作，也就是说，再来一个锁。
涉及到了进程状态的改变，那必然是任务结构体数组的那把锁 $ptable.lock$，用它来保证释放休眠对象锁和进入休眠状态这两个步骤是个原子操作，但是 $xv6$ 对其处理有少许不同，更为精巧一些，来看完整的 $sleep$ 代码：
void sleep(void *chan, struct spinlock *lk)
{
struct proc *p = myproc();
if(lk != &ptable.lock){
//如果lk不是ptable.lock
acquire(&ptable.lock); //获取ptable.lock
release(lk); //释放lk
}
// Go to sleep.
p->chan = chan;
p->state = SLEEPING;
sched();
// Tidy up.
p->chan = 0;
// Reacquire original lock.
if(lk != &ptable.lock){
//如果lk不是ptable.lock
release(&ptable.lock); //释放ptable.lock
acquire(lk); //重新获取lk锁
}
}
整个代码上下来看十分对称，先不考虑休眠对象锁就是任务结构体锁这种情况，可以很清楚地看到释放休眠对象锁 $lk$ 和进入休眠状态这两个步骤在 $ptable.lock$ 这把锁的保护下进行，是个原子操作，经过上面的分析，这样就不会出现什么幺蛾子了。
在调用 $sleep$ 的函数通常有对休眠对象锁的取放操作，而 $sleep$ 本身从逻辑上来说并不需要释放锁，只是为了避免死锁所以才临时释放。而在同一个函数中对锁的获取和释放通常是成双成对的，所以 $sleep$ 在返回时还要重新将休眠对象锁取回来。
再来看 $lk = ptble.lock$，休眠对象锁就是任务结构体锁的情况，也就是说休眠在一个进程上，这种情况只有一种：在 $wait$ 函数中，父进程需要等待子进程退出，这个时候它就休眠在自己身上：
sleep(curproc, &ptable.lock);
这种情况从 $sleep$ 函数来看，根本不会释放 $ptable.lock$，如此不会死锁吗？$xv6$ 对此作如下处理：
static void wakeup1(void *chan)
{
struct proc *p;
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
if(p->state == SLEEPING && p->chan == chan)
p->state = RUNNABLE;
}
void wakeup(void *chan)
{
acquire(&ptable.lock);
wakeup1(chan);
release(&ptable.lock);
}
将 $wakeup$ 函数分为两部分，实际干事的为 $wakeup1$，但它不需要锁，所以可以回头看看在 $exit$ 中唤醒父进程实际使用的 $wakeup1$，这样就不会造成死锁。
调度切换
调度切换的过程是进程 $A$ 切换到调度程序，调度程序根据轮询算法选取一个进程 $B$，然后切换到进程 $B$。
进程 $A$ 切换到调度程序一般是调用 $sched$ 函数，$sched$ 是 $swtch$ 的封装，在这之前一定要获取到 $ptable.lock$ 这把锁来保证进程的上下文。例如 $yield$ 通常用在因时间片到了而重新调度，代码如下：
void yield(void)
{
acquire(&ptable.lock); //DOC: yieldlock
myproc()->state = RUNNABLE;
sched();
release(&ptable.lock);
}
在调用 $swtch$ 取了 $ptable.lock$ 这把锁，并把当前进程的状态更改为 $RUNNABLE$，这之后才来调用 $sched$：
void sched(void)
{
int intena;
struct proc *p = myproc();
if(!holding(&ptable.lock))
panic("sched ptable.lock");
if(mycpu()->ncli != 1)
panic("sched locks");
if(p->state == RUNNING)
panic("sched running");
if(readeflags()&FL_IF)
panic("sched interruptible");
intena = mycpu()->intena;
swtch(&p->context, mycpu()->scheduler);
mycpu()->intena = intena;
}
$sched$ 函数在需要重新调度的情况都会被调用，进行了许多检查，调用 $sched$ 当前进程的状态不该是 $RUNNING$，因为 $sched$ 之前已经把状态修改了。此时不该允许中断，因为取锁的时候关中断了，$xv6$ 为了保险，取锁的时候就将中断关闭，避免死锁，这部分详见 锁。$intena$ 是 $pushcli$ 之前 $CPU$ 允许中断的情况，先把这个值保存起来待到该进程再次被调度的时候恢复，保证了同一个进程里中断允许情况一致。下面重点说说为什么 $swtch$ 时必须要取得 $ptable.lock$ 这把锁
这之上总总会发现 $switch$ 的整个过程都持有 $ptable.lock$，要知道执行 $swtch$ 是会切换进程的，因而这个锁在一个进程中获取，在另一个进程中释放。这样使用锁很不常见，但这里是必须的。
如果 $swtch$ 执行的过程中没有持有 $ptable.lock$ 会怎么样呢？举个例子，运行在 $CPU0$ 的进程 $A$ 的时间片到了，调用 $yield$ 将进程 A 的进程设置为 $RUNNABLE$，$CPU0$ 在执行 $sched$ 之前另一个 $CPU1$ 可能调度进程 $A$，这样的话一个进程运行在了两个 $CPU$ 上，其内核栈的上下文就乱套了，所以 $swtch$ 的整个执行期间必须持有锁，保证进程的状态和上下文一致。
由此，$sched$ 前有取锁，后有放锁，但这两个操作不是配对的，进程 $A$ 来取锁，进程 $B$ 来放锁。$sched$ 之后的语句是进程再次被调度重上 $CPU$ 后执行的语句，一般就会先来个释放锁的操作，即使是进程是第一个进程也不例外，在前面我们看到，创建一个新进程，就是把这个新进程模拟成一个旧进程，往它的内核站里面填充各种虚假的上下文，使得它像一个已经上过 $CPU$ 执行的旧进程。不仅上下文要模仿，行为也要模仿才得行，所以在填充内核级上下文的时候将 $eip$ 设置为 $forkret$ 函数的地址：
void forkret(void)
{
static int first = 1;
release(&ptable.lock);
if (first) {
first = 0;
iinit(ROOTDEV);
initlog(ROOTDEV);
}
}
这个函数表示如果创建的进程不是第一个进程的话就干一件事：释放 $ptable.lock$，这就是模仿一个旧进程，因为旧进程执行 $swtch$ 切换了上下文之后就是释放 $ptable.lock$。
但也有 $sched$ 之后不释放的，比如 $exit$ 代码中最后两行：
curproc->state = ZOMBIE;
sched();
panic("zombie exit");
$exit$ 中调度 $sched$ 之后就永远也不会回来了，因为进程都被销毁了，怎么可能还回来。那取锁放锁岂不是没配对？这里再次注意，$sched$ 前后取锁放锁本来就不配对，进程 $A$ 取锁，进程 $B$ 放锁，然后进程 $A$ 没了，有问题吗？没有问题
进程相关系统调用
这里来简单看看有关进程的系统调用，$xv6$ 里系统调用的用户接口和内核函数的名字很多都是一样的，不要搞混了
fork
用户接口：
int fork(void);
内核函数：
int sys_fork(void)
{
return fork();
}
exit
用户接口：
int exit(void) __attribute__((noreturn));
__attribute__((noreturn)) 告诉编译器这个函数不会返回
内核函数：
int sys_exit(void)
{
exit();
return 0; //不会执行到这儿
}
wait
用户接口：
int wait(void);
内核函数：
int sys_wait(void)
{
return wait();
}
kill
用户接口：
int kill(int);
内核函数：
int sys_kill(void)
{
int pid;
if(argint(0, &pid) < 0) //去用户栈去参数:进程号
return -1;
return kill(pid); //杀死这个进程
}
getpid
获取当前进程的进程号
用户接口：
int getpid(void);
内核函数：
int sys_getpid(void)
{
return myproc()->pid;
}
sbrk
为进程分配内存，通常用作堆
用户接口：
char* sbrk(int);
内核函数：
int sys_sbrk(void)
{
int addr;
int n;
if(argint(0, &n) < 0) //获取参数:要分配的空间大小
return -1;
addr = myproc()->sz;
if(growproc(n) < 0) //调用growproc将进程的大小增加n字节
return -1;
return addr; //返回增加的那部分空间的首地址
}
sleep
$sleep(n)$ 休眠 $n$ 个滴答时间
用户接口：
int sleep(int);
内核函数：
int sys_sleep(void)
{
int n;
uint ticks0;
if(argint(0, &n) < 0) //取参数:要休眠的滴答数
return -1;
acquire(&tickslock); //取锁
ticks0 = ticks; //记录当前滴答数
while(ticks - ticks0 < n){
//当过去的滴答数小于要休眠的滴答数
if(myproc()->killed){
//如果该进程被killed
release(&tickslock);
return -1;
}
sleep(&ticks, &tickslock); //休眠
}
release(&tickslock); //解锁
return 0; //返回
}
uptime
$uptime$ 返回当前系统的滴答数，也就是发生了多少次时钟中断
int sys_uptime(void)
{
uint xticks;
acquire(&tickslock); //取滴答数的锁
xticks = ticks; //当前滴答数
release(&tickslock); //解锁
return xticks; //返回当前滴答数
}
HEAP
堆，在数据结构那一块儿说过一些，本文补充完整讲述如何来实现和管理堆。讲述的程序来自 c 程序设计语言，就是 c 语言之父那本书中给出的程序，虽然都说这本书是经典，但某些还是不太好懂的，本文就相当于做做注解吧。
在前面说过 $malloc$ $free$ 只是管理堆空间，将其分配给用户程序，但实际这片可用的堆空间又是向内核申请的，一般两个函数：$sbrk$，$brk$ 函数，两者作用差不多，都是将 $break$ 指针向上移动，$break$ 表示的是数据段末尾，$break$ 向上移动之后，扩展出来的空间就可以作为堆来使用。
这片堆空间采用空闲链表的方法组织起来，如下图所示：
头部设计
每一块应有一个头部，每个头部包括当前块的大小以及指向下一个空闲块的指针。$malloc$ 就是遍历这个空闲链表然后挑出一个合适的块然后返回。
$malloc$ 函数返回的存储空间需要满足将要存储对象的对其要求，虽然机器类型各异，但是每个机器都有一个最受限的类型，如果最受限的类型能够存放在某个特定的地址，那么其他所有的类型都能够存放在这个特定的地址。有些机器是 $double$，有些是 $long$ $int$，这里书上给出的，以及 $xv6$ 给出的都是 $long$
那如何设计使得对齐要求满足呢？首先对这个头部做了对齐设计，使它满足最受限的类型，然后规定所有块的大小必须是这个头部的整数倍。因此在 malloc 分配内存的时候只要块大小满足，那么对齐要求肯定也是满足的。可以这样想，假如用户程序申请大小为 a 的空间，$malloc$ 分配大小为 b 的块(b >= a)，不论 b 将要存放什么对象，基本元素，数组，结构体，它们始终都是基本数据组合而成，而分配的这个块的一个基本单位能够满足最受限的类型，那存放其他的肯定也是能行的。
来看头部的设计：
typedef long Align;
union header {
struct {
union header *ptr; //头部指针
uint size; //块大小
} s;
Align x; //对齐，不会使用
};
头部就包括两个元素：指向下一个空闲块的指针和当前块的大小。$x$ 只是用来对齐，不会使用。而关于对齐的设计就是通过联合体来实现的，联合体中所有元素共用一片存储空间，其大小等于最大的那个元素大小。
头部和其后的空间是一个块，但是返回给用户的地址不应包括头部
有了上述了解之后来看管理堆的三个函数，分别是 $malloc$ 分配空间，$free$ 回收空间，$morecore$ 向内核申请空间，一个个来看，首先是 $malloc$：
malloc
void* malloc(uint nbytes)
{
Header *p, *prevp;
uint nunits;
nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;
if((prevp = freep) == 0){
//freep若为0，表示第一次malloc，什么都还没有
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}
for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){
//从freep开始寻找空闲块
if(p->s.size >= nunits){
//找到的空闲块足够大
if(p->s.size == nunits) //如果大小刚好合适
prevp->s.ptr = p->s.ptr; //那么只需要改变一下指针
else {
//如果比申请的大
p->s.size -= nunits; //将该块切割，尾部分配出去
p += p->s.size;
p->s.size = nunits;
}
freep = prevp; //记录找到空闲块的位置
return (void*)(p + 1); //将该块分配给用户空间，返回给用户的部分不包括头部，所以加1
}
if(p == freep) //没有找到合适的块
if((p = morecore(nunits)) == 0) //向内核申请nunits大小的空间
return 0;
}
}
来看算法流程图：
配合着来看应该没什么问题，就不具体解释了，接着来看 free
free
void
free(void *ap)
{
Header *bp, *p;
bp = (Header*)ap - 1; //要free的块的头部
//从上一次找到空闲块的地方开始，终止条件:要回收的块位置是否在两个空闲块之间
for(p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
if(p >= p->s.ptr && (bp > p || bp < p->s.ptr)) //如果要回收的块在链头或链尾
break;
if(bp + bp->s.size == p->s.ptr){
//当前要回收的块与下个块相邻
bp->s.size += p->s.ptr->s.size; //修改当前块大小
bp->s.ptr = p->s.ptr->s.ptr; //合并:当前块指向下一块的下一块
} else
bp->s.ptr = p->s.ptr; //不相邻，直接指向下一块
if(p + p->s.size == bp){
//当前要回收的块与上个块相邻
p->s.size += bp->s.size; //修改上个块的大小
p->s.ptr = bp->s.ptr; //合并:上个块指向下个块
} else
p->s.ptr = bp; //上个块指向当前块
freep = p; //freep设为刚回收的这个块的上一块
}
free 就是链表中的插入结点操作，只是增加了查找插入位置，是否合并，本质是一样的，看几个例子:
morecore
static Header*
morecore(uint nu)
{
char *p;
Header *hp;
if(nu < 4096) //如果申请小于4096个单元
nu = 4096; //申请4096个单元
p = sbrk(nu * sizeof(Header)); //向内核申请空间
if(p == (char*)-1) //分配失败
return 0;
hp = (Header*)p; //申请的空间地址
hp->s.size = nu; //初始化空间大小
free((void*)(hp + 1)); //将申请到的空间加进原本的空闲链表
return freep; //返回
}
这个函数就是向内核申请空间，一次性最少申请 $4096$ 个基本单元，避免频繁使用系统调用向内核申请空间。将申请回来的空间加进原本的空闲链表后返回。
堆的组织管理大概就是这样，总结下来就是，$morecore$ 向内核进一批货(申请一大片空间)，$malloc$ 和 $free$ 组织管理这片空间。
运行库
最后再来简单聊一聊运行库，运行库是标准库的扩展，这与我们进程有什么关系？$main$ 函数我们都很熟悉，对此有两个常问的问题：程序从 $main$ 开始吗？$main$ 执行完之后又到哪儿去了呢？这两个问题都与运行库相关，$main$ 也是个函数，它也是被调用执行的，而且 $main$ 执行之前还要为它准备参数，执行完之后还要对程序”善后“，这一切都是运行库来做的。
运行库会对程序的运行环境进行初始化，比如参数，堆，$IO$，线程等等，之后调用 $main$ 执行程序主体，$main$ 执行完成之后进行堆的销毁等等操作然后调用 $exit$ 退出，咱们这里来看看极简极简的运行库伪码意思意思：
push argv #准备main函数的参数
push argc
call main #调用main
push eax #准备exit的参数
call exit #调用exit
很清晰地看到在 $main$ 运行之前，压栈 $argv$，$argc$ 两个参数，然后调用 $main$ 函数，之后将 $main$ 函数的返回值压栈，将其作为 $exit$ 的参数调用 $exit$ 使得进程退出。所以这里应该明白 $main$ 函数最后的 $return$ 有什么用处了吧，它会作为 $exit$ 的参数执行 $exit$ 系统调用，根据值的不同系统就可以做出不同的反应。
$xv6$ 并没有实现运行库，关于 $main$ 函数的环境准备隐含的包括在了 $exec$ 函数里面，$exec$ 就在用户栈里面压入了 $main$ 函数的参数。而用户程序执行完之后需要显示的调用 $exit$ 来退出，因为它没有运行库来为它调用 $exit$。像上述那样简单的运行库实现起来也不复杂，但本文这儿就不叙述了，后面有机会专门写写这方面的文章。
最后总结
关于 $xv6$ 的进程方面大概就这么多，关于进程这条线私以为捋得还是够清楚得了，进程如何创建的，第一个进程又是如何创建的，怎么被调度上的 $CPU$，第一次上 $CPU$ 又是什么情况，程序加载是什么意思，进程如何休眠又如何被唤醒，僵尸进程孤儿进程是如何产生的，程序是从 $main$ 开始的吗，$main$ 结束之后又去了哪，以及比较困难的锁同步问题。
上面的这些问题自己感觉还是说明白了，但是我也只是站在 $xv6$ 代码上面去理解它，但实际上为什么要这么设计，这么设计有什么好处，不这样设计可不可以，对此我的水平就不够了，一些问题实在不太清楚。比如锁的粒度问题，开关中断的时机，有些操作看似多余但实际上对于多处理器下的设计十分重要，比如内核页表的切换，类似的问题还有很多。
所以其实我所讲述的都是比较片面简单的东西，$xv6$ 虽小，但五脏俱全，要真细究，跳出原有代码谈设计，这个问题就很难很难，我目前的水平还达不到，所以还需要努力修炼，提升修为。
好了本节就这样吧，有什么问题还请批评指正，也欢迎大家来同我讨论交流学习进步。
首发公众号：Rand_cs
