进程控制块
进程是程序的一次运行, MOS中采用进程控制块来记载进程的信息:
1
2
3
4
5
6
7
8
9
10
11
12
struct Env {
struct Trapframe env_tf;
Pde *env_pgdir;
u_int env_id;
u_int env_parent_id;
u_int env_status;
u_int env_cr3;
u_int env_pri;
LIST_ENTRY(Env) env_link;
LIST_ENTRY(Env) env_sched_link;
// ...
};
其中出现了一个结构类型 struct Trapframe , 当发生进程调度时, 需要将当前进程的现场保存到其进程控制块中的 env_tf 中. 该结构类型的定义为:
1
2
3
4
5
6
7
8
9
10
struct Trapframe {
unsigned long regs[32];
unsigned long cp0_status;
unsigned long hi;
unsigned long lo;
unsigned long cp0_badvaddr;
unsigned long cp0_cause;
unsigned long cp0_epc;
unsigned long pc;
};
很容易看出来, 这个结构体用于保存中断现场的寄存器值.
另外, struct Env 中的其他字段的意义如下:
env_pgdir: 进程的页目录基地址的虚拟地址. 进程切换时内核中的mCONTEXT将设置为目标进程的env_pgdir.env_id: 进程号. 需要保证当前存活的进程具有不同的进程号.env_parent_id: 父进程号. 后续实现fork时需要设置该字段.env_status: 进程控制块的状态. 只可能是ENV_FREE,ENV_RUNNABLE,ENV_NOT_RUNNABLE其中之一.ENV_FREE: 意味着此进程控制块处于空闲链表中, 不表征任何存活的进程.ENV_RUNNABLE: 意味着此进程控制块处于调度链表中, 且没有被阻塞, 表征了一个存活的可运行的进程.ENV_NOT_RUNNABLE: 意味着此进程控制块处于调度链表中, 但处于阻塞状态, 表征了一个存活但被阻塞的进程.需要注意的是, 这里的三种状态与进程三状态是不同的.
env_cr3: 保存进程页目录基地址对应的物理地址.env_pri: 进程的优先级.env_link: 若进程控制块处于空闲链表中, 则此字段链接到下一个空闲进程控制块.env_sched_link: 若进程控制块处于调度链表中, 则此字段链接到下一个可调度的进程控制块.
这里有两个链表链接字段(env_link , env_sched_link), 将在下文进一步解释.
进程的地址空间与初始化
MOS的进程在用户态下(SR寄存器中 KUc 位为 0)时无法访问 0x80000000 以上的地址空间, 只有当切换到内核态(SR寄存器中 KUc 为 1)后才能访问这些高地址. 陷入内核的本质是切换到内核态.
MOS的设计为所有进程都具有4GB的虚拟地址空间. 下面是MOS进程的地址空间:
图中, 所有进程的蓝色区域都是一样的(共享内核空间). 另外, 紫色区域:
UVPT用于映射进程页表, 每个进程的这部分都不一样.UPAGES用于映射内存管理中的pages数组, 每个进程的这部分都一样.UENVS用于映射进程管理中的envs数组, 每个进程的这部分都一样.envs数组将在后文的进程控制块管理中详细介绍.
回忆一下启动的过程, 我们在 mips_vm_init 中申请了 pages 和 envs 这两个数组的空间, 并将它们与虚地址 UPAGES 和 UENVS 建立了映射.
1
2
3
4
5
6
7
8
pages = (struct Page *)alloc(npage * sizeof(struct Page), BY2PG, 1);
printf("to memory %x for struct Pages.\n", freemem);
n = ROUND(npage * sizeof(struct Page), BY2PG);
boot_map_segment(pgdir, UPAGES, n, PADDR(pages), PTE_R);
envs = (struct Env *)alloc(NENV * sizeof(struct Env), BY2PG, 1);
n = ROUND(NENV * sizeof(struct Env), BY2PG);
boot_map_segment(pgdir, UENVS, n, PADDR(envs), PTE_R);
而这里的 UPAGES 和 UENVS 恰好就位于紫色区域内. 也就意味着我们可以将这部分映射关系直接复用. 这里就可以解释启动中 boot_map_segment(boot_pgdir, ...) 的重要作用, 即制作了一个页目录映射模板 boot_pgdir , 只要复制其中的 UENVS 和 UPAGES 对应的表项就可以完成映射!
MOS中使用 env_setup_vm 为一个进程控制块表征的进程设置初始虚空间.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static int env_setup_vm(struct Env *e) {
int i;
struct Page *p = NULL;
// Step 1. alloc a page for `e->env_pgdir`
if (page_alloc(&p) != 0) {
panic("env_setup_vm `page_alloc` error");
}
p->pp_ref++;
e->env_pgdir = (Pde *) page2kva(p);
for (i = 0; i < PDX(UTOP); ++i) {
e->env_pgdir[i] = 0;
}
for (; i < PDX(UVPT); ++i) {
e->env_pgdir[i] = /* Step 2. copy entry from template `boot_pgdir` */;
}
e->env_cr3 = PADDR(e->env_pgdir);
e->env_pgdir[PDX(UVPT)] = e->env_cr3 | PTE_V; // ***SELF-MAPPING***
return 0;
}
调用完 env_setup_vm 后, 就为进程设置好了初始虚空间, 但可运行的机器码等程序信息还未加入到内存中, 这需要后文中的 load_icode 进行设置.
进程控制块的管理
进程管理初始化
MOS中允许的最大进程数目是 1024 , 并在 mips_vm_init 时在内核空间中申请了一个 1024 长的进程控制块数组:
1
2
3
4
// Note: NENV == 1024
envs = (struct Env *)alloc(NENV * sizeof(struct Env), BY2PG, 1);
n = ROUND(NENV * sizeof(struct Env), BY2PG);
boot_map_segment(pgdir, UENVS, n, PADDR(envs), PTE_R);
随后进行 env_init , 在此函数中将 envs 数组中的进程控制块挂载到空闲链表中, 并初始化调度链表.
- 空闲链表
env_free_list中存储目前不表征存活进程的进程控制块. - 调度双链表
env_sched_list用于进行进程调度.
1
2
3
4
5
6
7
8
9
10
void env_init() {
int i;
LIST_INIT(&env_free_list);
LIST_INIT(&env_sched_list[0]);
LIST_INIT(&env_sched_list[1]);
for (i = NENV - 1; i >= 0; --i) {
LIST_INSERT_HEAD(&env_free_list, &envs[i], env_link);
envs[i].env_status = ENV_FREE;
}
}
这里定义的 env_init 函数将在 mips_init 中调用:
1
2
3
4
5
6
7
8
9
void mips_init() {
mips_detect_memory();
mips_vm_init();
page_init();
env_init(); // <~~
// ...
trap_init();
// ...
}
链表法管理空闲进程控制块
MOS中采用链表法管理空闲进程控制块. 也就是上文中反复提到的空闲链表 env_free_list . 事实上, 采用何种管理方法(链表法, 位图法)都是无关紧要的, 重点是无论采用什么管理方法, 都要提供一致的对外接口 env_alloc, env_free 来分配和释放资源. 这跟内存管理中的物理内存块管理是一样的.
env_alloc
env_alloc 的主要任务是申请一个进程控制块, 并给它的一些字段设置合理的初始值. 大致框架为:
这里设置的初始值将在进程开始运行时的
env_pop_tf汇编函数中加载到 CPU 的状态:
- 这里初始化的 CPU 状态有栈指针寄存器, CP0 中的 SR 寄存器.
还有一些初始值表示进程的一些属性, 如进程号, 进程状态, 父进程号.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int env_alloc(struct Env **new, u_int parent_id) {
int r;
struct Env *e;
// Step 1. alloc a page for page directory
if (/* `env_free_list` is empty */) {
*new = 0;
return -E_NO_FREE_ENV;
}
e = /* the head of `env_free_list` */;
/* remove `e` from `env_free_list` */;
// Step 2. use `env_setup_vm` to initial virtual memory space of `e`
// Step 3. initial fields of `e`
e->env_id = mkenvid(e);
e->env_status = ENV_RUNNABLE;
e->env_parent_id = parent_id;
e->env_tf.cp0_status = 0x10001004;
e->env_tf.regs[29] = USTACKTOP;
*new = e;
return 0;
}
这里给进程控制块的字段进行了初始化, 这里做一些说明:
env_id: 使用mkenvid创建一个进程号. 官方代码中的mkenvid实现有一些小问题, 我们将在后续的文章中修复它.env_tf.cp0_status: 这一字段将在运行时被放入CP0的SR寄存器中, 对照SR寄存器的位含义, 可知道0x10001004的意思为将SR寄存器中的CU0,IM[8 + 4],IEp置高.CU0被置高, 意味着 CP0 被启用.IM[8 + 4]被置高, 意味着接受 4 号中断(MOS 中 4 号中断是时钟中断)IEp被置高, 返回用户态时,IEc将获得IEp的值(二重栈), 这意味着返回用户态后启用全局中断使能.
env_tf.regs[29]:$29寄存器为sp栈指针寄存器, 这里初始化sp为用户栈栈顶.
env_free
官方给出了 env_free 全部代码, 这里仅作概述:
- 将进程页目录中的所有页面移除(取消映射).
- 将页目录占用的物理页面回收.
- 将进程控制块放回到
env_free_list中.
进程的生命周期
一个进程具有其完整的生命周期: 创建, 运行, 销毁.
创建 - 加载程序到内存
在介绍创建进程的方法之前, 需要关注一下何时会创建进程?
- 系统初始化时(
mips_init)创建初始进程. - 进程通过系统调用来产生子进程.
本文介绍的是系统初始化时创建进程的方法, 另一种方法将在后续的文章中介绍.
MOS初始化时, 可以使用 env_create 或 env_create_priority 来创建进程:
1
2
3
4
5
6
7
8
9
10
11
12
13
void env_create_priority(u_char *binary, int size, int priority) {
struct Env *e;
if (env_alloc(&e, 0) != 0) {
panic("env_create_priority `env_alloc` error");
}
e->env_pri = priority;
load_icode(e, binary, size);
LIST_INSERT_HEAD(&env_sched_list[0], e, env_sched_link);
}
void env_create(u_char *binary, int size) {
env_create_priority(binary, size, 1);
}
这里涉及到两个关键参数
binary和size. 我们希望 MOS 初始化时能够创建若干个初始进程, 而进程是程序的一次执行, 因此需要在 MOS 初始化时取得可执行文件的二进制码(ELF 格式), 因此只需要在编译时, 将外部文件的二进制码与大小链接到 MOS 内核中即可.事实上, MOS 内核编译得到的 vmlinux 文件就包含了 Makefile 指定的外部程序. 假设被链接的外部可执行程序名为
prog, 则 vmlinux 中就存在符号:
binary_prog_start: 存储程序二进制码的起始地址.binary_prog_size: 存储程序二进制码的长度.那么, 在 MOS 初始化时, 就可以通过下述代码来创建进程:
为简化这一创建进程的代码, 可以通过宏来简化:
这里用到了 load_icode 将二进制码加载到内存中, 随后将进程控制块挂入调度双链表中. 下面重点讲解 load_icode 的原理与框架.
icode: image of code
首先, 要知道二进制码有什么特征. 由于链接到 MOS 内核文件的二进制码都由linux下的mips-4KC交叉编译器产生, 这意味着得到的程序二进制码具有ELF格式. 因此我们只需要直接将这段二进制码解释为ELF形式即可得到程序的各种信息.
C 语言中, 类型解释内存. 对于一个 ELF 二进制码, 只需要将其首地址指针转为 ELF 指针类型, 即可通过该指针来获取其中的信息.
而ELF格式中, 已经明确给出了各个段的内容与虚地址, 因此可以直接通过解析ELF来将整个程序加载到内存中. 在MOS中, load_icode 负责为进程初始化栈并调用 load_elf 加载程序, 而 load_elf 负责解析ELF文件并调用 load_icode_mapper, 最后 load_icode_mapper 则将取到的程序段复制到内存中(创建镜像), 并在进程的页目录中为其建立映射(使用 page_insert).
\[\begin{CD} \texttt{load\_icode}\\ @VVV\\ \texttt{load\_elf}\\ @VVV\\ \texttt{load\_icode\_mapper} \end{CD}\]除此之外,
load_elf最终将 ELF 可执行文件的入口地址entry_point以参数形式外传.
根据上述解释, 不难得到 load_icode 与 load_icode_mapper 的大致框架:
load_elf(lib/kernel_elfloader.c)的官方代码已经很明确了, 这里不再做详细解释.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
static void load_icode_mapper( // assert `sgsize` >= `bin_size`
u_long va, u_int32_t sgsize,
u_char *bin, u_int32_t bin_size, void *user_data
) {
struct Env *env = (struct Env *)user_data;
struct Page *p = NULL;
u_long i;
int r;
u_long offset = va - ROUNDDOWN(va, BY2PG);
// difficult & challenging task!
// HINT: `page_alloc`, `page_insert`, `bcopy` help to finish the task
// Step 1. if `offset` != 0, think where to map the unaligned code
// Step 2. map `bin` with the size of `bin_size` to the memory
// Step 3. if `bin_size` < `sgsize`, fill the rest of segment with `0`
}
static void load_icode(struct Env *e, u_char *binary, u_int size) {
struct Page *p = NULL;
u_long entry_point;
// Step 1. initialize stack for the process
if (page_alloc(&p) != 0) {
panic("load_icode `page_alloc` error");
}
if (/* use `page_insert` to map the stack */ != 0) {
panic("load_icode `page_insert` error");
}
// Step 2. load image of the code
if (load_elf(binary, size, &entry_point, e, load_icode_mapper) != 0) {
panic("load_icode `load_elf` error");
}
// Step 3. set initial pc
e->env_tf.pc = entry_point;
}
load_icode 是 env_create_priority 中最关键的一步, 完成这一步后, 进程控制块就被加入到调度双链表中, 参与到时间片调度的序列中. 当调度算法决定让该进程运行时, 就会调用 env_run 函数运行它, 这将在下一节中详细介绍.
运行 - 时间片调度与上下文切换
当定时器发出中断信号后, 系统陷入内核(进入内核态), 保存现场到 TIMESTACK 并将栈指针 sp 寄存器设置为 TIMESTACK. 随后立即调用 sched_yield 函数.
\[\begin{CD} \texttt{except\_vec3}\\ @VVV\\ \texttt{handle\_int}\\ @VVV\\ \texttt{timer\_irq}\\ @VVV\\ \texttt{sched\_yield}\\ @VVV\\ \texttt{env\_run} \end{CD}\]据宏定义,
TIMESTACK事实上是0x82000000, 但此物理页事实上并未由page_alloc获取, 因此这里存在问题(此物理页面有可能会被进程占用). 为修补此问题, 可对page_init进行一点修改: 即将page结构体挂入链表时, 排除pa2page(PADDR(TIMESTACK - BY2PG))这一页面.
sched_yield 的作用就是在调度双链表中决定下一个运行的进程, 并调用 env_run 运行它. 同样, 采用怎样的调度方案都是无关紧要的, 重要的是:
- 若调度链表为空, 应当陷入死循环(系统故障).
- 若调度链表非空, 则应当使得其中的进程都有机会得到运行机会, 并最终调用
env_run运行进程.
MOS中采用的是简单的带优先级的时间片调度方案, sched_yield 的大致框架为:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void sched_yield() {
static int count = 0;
static int point = 0;
static struct Env *e = NULL;
if (count == 0 || e == NULL || e->env_status != ENV_RUNNABLE) {
if (e != NULL) {
/* move `e` to the tail of `env_sched_list[1 - point]` */
}
while (1) {
while (LIST_EMPTY(&env_sched_list[point])) point = 1 - point;
e = LIST_FIRST(&env_sched_list[point]);
if (e->env_status == ENV_RUNNABLE) {
count = e->env_pri; // PRIORITY
break;
} else {
/**
* if the status of `e` is `ENV_NOT_RUNNABLE`,
* move it to the tail of `env_sched_list[1 - point]`
*/
}
}
}
count--;
env_run(e);
}
在 env_run 中, 大致具有如下步骤:
- 若当前有进程在运行, 则应当将该进程的现场保存到其进程控制块的
env_tf中. - 将
mCONTEXT设置为待运行进程的页目录基地址.切换页目录, 可以使得 TLB 缺失, 引发
do_refill时填写正确的映射关系. - 将待运行进程的现场恢复到CPU的状态中.
因此其大致框架为:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void env_run(struct Env *e) {
// Step 1. save registers if necessary
if (curenv != NULL) {
struct Trapframe *cur_tf =
(struct Trapframe *) (TIMESTACK - sizeof(struct Trapframe));
bcopy(cur_tf, &(curenv->env_tf), sizeof(struct Trapframe));
curenv->env_tf.pc = curenv->env_tf.cp0_epc;
}
curenv = e;
// Step 2. switch address space
lcontext(curenv->env_pgdir);
// Step 3. restore registers of `e` and return to user-mode
env_pop_tf(&(curenv->env_tf), GET_ENV_ASID(curenv->env_id));
}
第一步中, 将当前进程的运行现场保存到其进程控制块的 env_tf 字段, 以便后续恢复到此进程时从恢复该现场.
同时, 将
env_tf.pc设置为env_tf.cp0_epc. 这是由于: 当时钟中断到来后, CP0 的 EPC 寄存器存储了当前进程的被中断指令的虚地址,env_pop_tf的恢复现场过程中, 将会通过jr指令跳转到env_tf中的pc值, 从而回滚进程. 因此这里必须要将pc设置为被中断指令的虚地址, 即cp0_epc.
随后使用了 lcontext 汇编函数将 curenv->env_pgdir 存储到 mCONTEXT 中, 用 env_pop_tf 汇编函数恢复待运行进程的现场.
lcontext 的定义很简单, 就是将传入的参数值存入 mCONTEXT:
1
2
3
4
5
6
LEAF(lcontext)
.extern mCONTEXT
sw a0, mCONTEXT
jr ra
nop
END(lcontext)
而 env_pop_tf 则相对复杂, 但核心任务是明确的: 将ASID填入EntryHi中, 以及将参数中的 env_tf 恢复到CPU状态中.
MOS 中切换地址空间, 不仅要让
mCONTEXT改为进程的页目录基地址, 还要将进程的 ASID 存入 EntryHi.
mCONTEXT负责指导 TLB 重填例程do_refill(软件)- EntryHI 的 ASID 则负责指导 TLB 的虚实地址转换 (硬件)
对于 env_pop_tf , 官方已经给出了完整的实现, 读者可详细阅读理解官方代码, 此处不作详述.
销毁 - 释放进程控制块与占用的内存
前文通过 env_create 创建进程, 此处使用 env_destory 销毁进程.
销毁进程的大致步骤是:
- 调用
env_free将该进程对应的进程控制块释放. - 若被销毁的进程是当前进程, 则需要调用
sched_yield让其他进程运行.
1
2
3
4
5
6
7
void env_destroy(struct Env *e) {
env_free(e);
if (curenv == e) {
curenv = NULL;
sched_yield();
}
}
官方代码中, 这里还有一段用
bcopy来复制现场的代码. 但按代码逻辑而言, 这里已经把curenv置NULL, 因此env_run中也不会用到这个现场信息, 故这段bcopy为冗余代码.
