实验题目: Lab4

实验目的

  • 了解内核线程创建/执行的管理过程
  • 了解内核线程的切换和基本调度过程

实验环境

1
2
3
操作系统: Ubuntu 20.04 LTS
虚拟机: Vmware Player Workstation 16 Player
依赖: build-essential git qemu-system-x86 gdb make diffutils lib32z1

实验内容及操作步骤

实验2/3完成了物理和虚拟内存管理,这给创建内核线程(内核线程是一种特殊的进程)打下了提供内存管理的基础。当一个程序加载到内存中运行时,首先通过ucore OS的内存管理子系统分配合适的空间,然后就需要考虑如何分时使用CPU来“并发”执行多个程序,让每个运行的程序(这里用线程或进程表示)“感到”它们各自拥有“自己”的CPU。

本次实验将首先接触的是内核线程的管理。内核线程是一种特殊的进程,内核线程与用户进程的区别有两个:

  • 内核线程只运行在内核态
  • 用户进程会在在用户态和内核态交替运行
  • 所有内核线程共用ucore内核内存空间,不需为每个内核线程维护单独的内存空间
  • 而用户进程需要维护各自的用户内存空间

练习0:填写已有实验

涉及改动的文件如下,详见详见 >>这里<<

  • Lab1
    • kern/debug/kdebug.c
      • print_stackframe
    • kern/trap/trap.c
      • idt_init
      • trap_dispatch
  • Lab 2
    • kern/mm/default_pmm.c
      • default_init_memmap
      • default_alloc_pages
      • default_free_pages
    • kern/mm/pmm.c
      • get_pte
      • page_remove_pte
  • Lab 3
    • kern/mm/vmm.c
      • do_pgfault
    • kern/mm/swap_fifo.c
      • map_swappable
      • swap_out_victim

练习1:分配并初始化一个进程控制块

alloc_proc函数(位于kern/process/proc.c中)负责分配并返回一个新的struct proc_struct结构,用于存储新建立的内核线程的管理信息。ucore需要对这个结构进行最基本的初始化,你需要完成这个初始化过程。

首先查看kern/process/proc.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
// alloc_proc - alloc a proc_struct and init all fields of proc_struct
static struct proc_struct *
alloc_proc(void) {
struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
if (proc != NULL) {
//LAB4:EXERCISE1 YOUR CODE
/*
* below fields in proc_struct need to be initialized
* enum proc_state state; // Process state
* int pid; // Process ID
* int runs; // the running times of Proces
* uintptr_t kstack; // Process kernel stack
* volatile bool need_resched; // bool value: need to be rescheduled to release CPU?
* struct proc_struct *parent; // the parent process
* struct mm_struct *mm; // Process's memory management field
* struct context context; // Switch here to run process
* struct trapframe *tf; // Trap frame for current interrupt
* uintptr_t cr3; // CR3 register: the base addr of Page Directroy Table(PDT)
* uint32_t flags; // Process flag
* char name[PROC_NAME_LEN + 1]; // Process name
*/
}
return proc;
}

根据里面的注释,加上对照着kern/process/proc.h里结构体proc_struct的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct proc_struct {
enum proc_state state; // Process state
int pid; // Process ID
int runs; // the running times of Proces
uintptr_t kstack; // Process kernel stack
volatile bool need_resched; // bool value: need to be rescheduled to release CPU?
struct proc_struct *parent; // the parent process
struct mm_struct *mm; // Process's memory management field
struct context context; // Switch here to run process
struct trapframe *tf; // Trap frame for current interrupt
uintptr_t cr3; // CR3 register: the base addr of Page Directroy Table(PDT)
uint32_t flags; // Process flag
char name[PROC_NAME_LEN + 1]; // Process name
list_entry_t list_link; // Process link list
list_entry_t hash_link; // Process hash list
};

指导书[1]中有对其中几个比较重要的成员变量进行说明,根据说明我们可以确定这些成员初始赋值。

第一个proc_state记录的是进程状态,在结构体上面可以找到定义:

1
2
3
4
5
6
7
// process's state in his life cycle
enum proc_state {
PROC_UNINIT = 0, // uninitialized
PROC_SLEEPING, // sleeping
PROC_RUNNABLE, // runnable(maybe running)
PROC_ZOMBIE, // almost dead, and wait parent proc to reclaim his resource
};

因为结构体初始化,还没有进程,所以赋值PROC_UNINIT;

pid也还没有分配,用-1表示;

runs往后的几个对应赋0或者NULL,剩余的用memset来初始化;

cr3根据指导书给出的解释,我们给它赋值boot_cr3

当某个进程是一个普通用户态进程的时候,PCB 中的 cr3 就是 mm 中页表(pgdir)的物理地址;而当它是内核线程的时候,cr3 等于boot_cr3。而boot_cr3指向了uCore启动时建立好的饿内核虚拟空间的页目录表首地址

对应实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static struct proc_struct * 
alloc_proc(void) {
struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
if (proc != NULL) {
proc->state = PROC_UNINIT;
proc->pid = -1;
proc->runs = 0;
proc->kstack = 0;
proc->need_resched = 0;
proc->parent = NULL;
proc->mm = NULL;
memset(&(proc->context), 0, sizeof(struct context));
proc->tf = NULL;
proc->cr3 = boot_cr3;
proc->flags = 0;
memset(proc->name, 0, PROC_NAME_LEN);
}
return proc;
}

其实指导书[2]创建内核线程里面也有对于一些赋予特殊初始值的成员变量进行说明:

但有些成员变量设置了特殊的值,比如:

1
2
3
4
proc->state = PROC_UNINIT;  设置进程为“初始”态
proc->pid = -1; 设置进程pid的未初始化值
proc->cr3 = boot_cr3; 使用内核页目录表的基址
...

对照着上面也能写出这些成员变量的初始值。

请说明proc_struct中struct context contextstruct trapframe *tf成员变量含义和在本实验中的作用是啥?

根据指导书的解释:

context:进程的上下文,用于进程切换(参见switch.S)。在 uCore中,所有的进程在内核中也是相对独立的(例如独立的内核堆栈以及上下文等等)。使用 context 保存寄存器的目的就在于在内核态中能够进行上下文之间的切换。实际利用context进行上下文切换的函数是在kern/process/switch.S中定义switch_to。

tf:中断帧的指针,总是指向内核栈的某个位置:当进程从用户空间跳到内核空间时,中断帧记录了进程在被中断前的状态。当内核需要跳回用户空间时,需要调整中断帧以恢复让进程继续执行的各寄存器值。除此之外,uCore内核允许嵌套中断。因此为了保证嵌套中断发生时tf 总是能够指向当前的trapframe,uCore 在内核栈上维护了 tf 的链,可以参考trap.c::trap函数做进一步的了解。

可以知道,context 储存进程当前状态,用于进程切换中上下文的保存与恢复。

tf 指向的是中断帧的指针,指向内核栈的某个位置,用来在进程执行中发生中断时保存中断现场用,例如在用户态中断到核心态的时候。

练习2:为新创建的内核线程分配资源

创建一个内核线程需要分配和设置好很多资源。

kernel_thread函数通过调用do_fork函数完成具体内核线程的创建工作。

do_kernel函数会调用alloc_proc函数来分配并初始化一个进程控制块,但alloc_proc只是找到了一小块内存用以记录进程的必要信息,并没有实际分配这些资源。

ucore一般通过do_fork实际创建新的内核线程。

do_fork的作用是,创建当前内核线程的一个副本,它们的执行上下文、代码、数据都一样,但是存储位置不同。

在这个过程中,需要给新内核线程分配资源,并且复制原进程的状态。

你需要完成在kern/process/proc.c中的do_fork函数中的处理过程。它的大致执行步骤包括:

  • 调用alloc_proc,首先获得一块用户信息块。
  • 为进程分配一个内核栈。
  • 复制原进程的内存管理信息到新进程(但内核线程不必做此事)
  • 复制原进程上下文到新进程
  • 将新进程添加到进程列表
  • 唤醒新进程
  • 返回新进程号

查看kern/process/proc.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
37
38
39
40
41
42
int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
int ret = -E_NO_FREE_PROC;
struct proc_struct *proc;
if (nr_process >= MAX_PROCESS) {
goto fork_out;
}
ret = -E_NO_MEM;
//LAB4:EXERCISE2 YOUR CODE
/*
* Some Useful MACROs, Functions and DEFINEs, you can use them in below implementation.
* MACROs or Functions:
* alloc_proc: create a proc struct and init fields (lab4:exercise1)
* setup_kstack: alloc pages with size KSTACKPAGE as process kernel stack
* copy_mm: process "proc" duplicate OR share process "current"'s mm according clone_flags
* if clone_flags & CLONE_VM, then "share" ; else "duplicate"
* copy_thread: setup the trapframe on the process's kernel stack top and
* setup the kernel entry point and stack of process
* hash_proc: add proc into proc hash_list
* get_pid: alloc a unique pid for process
* wakeup_proc: set proc->state = PROC_RUNNABLE
* VARIABLES:
* proc_list: the process set's list
* nr_process: the number of process set
*/

// 1. call alloc_proc to allocate a proc_struct
// 2. call setup_kstack to allocate a kernel stack for child process
// 3. call copy_mm to dup OR share mm according clone_flag
// 4. call copy_thread to setup tf & context in proc_struct
// 5. insert proc_struct into hash_list && proc_list
// 6. call wakeup_proc to make the new child process RUNNABLE
// 7. set ret vaule using child proc's pid
fork_out:
return ret;

bad_fork_cleanup_kstack:
put_kstack(proc);
bad_fork_cleanup_proc:
kfree(proc);
goto fork_out;
}

因为题目把函数实现过程讲的比较清楚了,加上代码里面的注释给我们提供了一些用得上的函数:

1
2
3
4
5
6
void alloc_proc(void); // 创建 proc 并初始化所有成员变量
static int setup_kstack(struct proc_struct *proc); // 为内核线程分配物理页
static int copy_mm(uint32_t clone_flags, struct proc_struct *proc); // 复制原进程的内存管理信息到新进程
static void copy_thread(struct proc struct *proc, uintptr_t esp, struct trapframe *tf); // 复制原进程上下文到新进程
static int get_pid(void); // 返回 pid
static void hash_proc(struct proc_struct *proc); // 将新进程添加到进程列表

参照着这些函数定义跟代码注释,不难写出具体实现:

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
37
38
int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
int ret = -E_NO_FREE_PROC;
struct proc_struct *proc;
if (nr_process >= MAX_PROCESS) {
goto fork_out;
}
ret = -E_NO_MEM;
// 调用alloc_proc,首先获得一块用户信息块。
if ((proc = alloc_proc()) == NULL)
goto fork_out;
proc->parent = current;
// 为进程分配一个内核栈
if (setup_kstack(proc) != 0)
goto bad_fork_cleanup_proc;
// 复制原进程的内存管理信息到新进程
if (copy_mm(clone_flags, proc) != 0)
goto bad_fork_cleanup_kstack;
// 复制原进程上下文到新进程
copy_thread(proc, stack, tf);
// 将新进程添加到进程列表
proc->pid = get_pid();
hash_proc(proc);
list_add(&proc_list, &(proc->list_link));
nr_process ++;
// 唤醒新进程
wakeup_proc(proc);
// 返回新进程号
ret = proc->pid;
fork_out:
return ret;

bad_fork_cleanup_kstack:
put_kstack(proc);
bad_fork_cleanup_proc:
kfree(proc);
goto fork_out;
}

请说明ucore是否做到给每个新fork的线程一个唯一的id?请说明你的分析和理由。

Ucore里面给fork线程分配id的函数get_pid代码如下:

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
static int
get_pid(void) {
static_assert(MAX_PID > MAX_PROCESS);
struct proc_struct *proc;
list_entry_t *list = &proc_list, *le;
static int next_safe = MAX_PID, last_pid = MAX_PID;
if (++ last_pid >= MAX_PID) {
last_pid = 1;
goto inside;
}
if (last_pid >= next_safe) {
inside:
next_safe = MAX_PID;
repeat:
le = list;
while ((le = list_next(le)) != list) {
proc = le2proc(le, list_link);
if (proc->pid == last_pid) {
if (++ last_pid >= next_safe) {
if (last_pid >= MAX_PID)
last_pid = 1;
next_safe = MAX_PID;
goto repeat;
}
}
else if (proc->pid > last_pid && next_safe > proc->pid)
next_safe = proc->pid;
}
}
return last_pid;
}

分析代码可以发现,这个函数在变量 last_pid 中记录了最后一次分配的 pid,而 next_safe 记录了 pid 的安全值。

在函数get_pid中,如果静态成员last_pid小于next_safe,则当前分配的last_pid一定是安全的,即唯一的PID。

但如果last_pid大于等于next_safe,或者last_pid的值超过MAX_PID,则当前的last_pid就不一定是唯一的PID,此时就需要遍历proc_list,重新对last_pidnext_safe进行设置,为下一次的get_pid调用打下基础。

同时,在 do_fork 调用 get_pid 的时候,会关闭中断,确保 get_pid 是原子操作,所以 ucore 做到了给每个新 fork 的线程一个唯一的 id。

练习3:阅读代码,理解 proc_run 函数和它调用的函数如何完成进程切换的。

在本实验的执行过程中,创建且运行了几个内核线程?

查看相关代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void
proc_run(struct proc_struct *proc) {
if (proc != current) {
bool intr_flag;
struct proc_struct *prev = current, *next = proc;
local_intr_save(intr_flag);
{
current = proc;
load_esp0(next->kstack + KSTACKSIZE);
lcr3(next->cr3);
switch_to(&(prev->context), &(next->context));
}
local_intr_restore(intr_flag);
}
}

该函数只有一个调用,在void schedule中:

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
void
schedule(void) {
bool intr_flag;
list_entry_t *le, *last;
struct proc_struct *next = NULL;
local_intr_save(intr_flag);
{
current->need_resched = 0;
last = (current == idleproc) ? &proc_list : &(current->list_link);
le = last;
do {
if ((le = list_next(le)) != &proc_list) {
next = le2proc(le, list_link);
if (next->state == PROC_RUNNABLE) {
break;
}
}
} while (le != last);
if (next == NULL || next->state != PROC_RUNNABLE) {
next = idleproc;
}
next->runs ++;
if (next != current) {
proc_run(next); // 这里调用 proc_run
}
}
local_intr_restore(intr_flag);
}

结合指导书[3]的内容,

uCore在实验四中只实现了一个最简单的FIFO调度器,其核心就是schedule函数。它的执行逻辑很简单:

1.设置当前内核线程current->need_resched为0; 2.在proc_list队列中查找下一个处于“就绪”态的线程或进程next; 3.找到这样的进程后,就调用proc_run函数,保存当前进程current的执行现场(进程上下文),恢复新进程的执行现场,完成进程切换。

执行proc_run的作用,就是保存当前进程current的执行现场(进程上下文),恢复新进程的执行现场,完成进程切换。

参考指导书[3:1]给出的资料,我们可以知道,本实验创建的内核线程数量是2个。

在uCore执行完proc_init函数后,就创建好了两个内核线程:idleproc和initproc,这时uCore当前的执行现场就是idleproc,等到执行到init函数的最后一个函数cpu_idle之前,uCore的所有初始化工作就结束了

语句local_intr_save(intr_flag);....local_intr_restore(intr_flag);在这里有何作用?请说明理由

这两句代码的作用分别是阻塞中断解除中断的阻塞

这两句的配合,使得这两句代码之间的代码块形成原子操作,可以使得某些关键的代码不会被打断,从而避免引起一些未预料到的错误,避免条件竞争。

实验结果及分析

收获及体会


  1. 设计关键数据结构 – 进程控制块 · ucore_os_docs (gitbooks.io) ↩︎

  2. 创建第0个内核线程idleproc · ucore_os_docs (gitbooks.io) ↩︎

  3. 调度并执行内核线程initproc · ucore_os_docs (gitbooks.io) ↩︎ ↩︎