ucore-lab4

本文最后更新于:2022年5月7日 下午

知识点

由于本人在操作系统精髓与设计原理中学习过这一部分,故略

练习解答

实验目的

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

内核线程是一种特殊的进程,内核线程与用户进程的区别有两个:

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

练习0

填写已有实验

meld合并即可。

kern/mm/vmm.c

练习1

分配并初始化一个进程控制块(需要编码)

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

【提示】在alloc_proc函数的实现中,需要初始化的proc_struct结构中的成员变量至少包括:state/pid/runs/kstack/need_resched/parent/mm/context/tf/cr3/flags/name。

请在实验报告中简要说明你的设计实现过程。请回答如下问题:

  • 请说明proc_struct中struct context contextstruct trapframe *tf成员变量含义和在本实验中的作用是啥?(提示通过看代码和编程调试可以判断出来)

这东西就照着注释写就行,没意思。

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
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
*/
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;
}

不难想到context是上下文的那个context,trapframe应该是陷阱相关代码。

我们看一下proc.c的butterfly图。

在看一下proc.c的内部调用图。

在proc.h中不难找到:

1
2
3
4
5
6
7
8
9
10
struct context {
uint32_t eip;
uint32_t esp;
uint32_t ebx;
uint32_t ecx;
uint32_t edx;
uint32_t esi;
uint32_t edi;
uint32_t ebp;
};

容易发现,context中存储的是进程/线程切换上下文所需要的'寄存器',不管对于内核态还是用户态都要用到这几个寄存器.

学习过csapp的人应该对这几个名字都很熟悉了,不再介绍了。

在trap.h中不难找到:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct trapframe {
struct pushregs tf_regs;
uint16_t tf_gs;
uint16_t tf_padding0;
uint16_t tf_fs;
uint16_t tf_padding1;
uint16_t tf_es;
uint16_t tf_padding2;
uint16_t tf_ds;
uint16_t tf_padding3;
uint32_t tf_trapno;
/* below here defined by x86 hardware */
uint32_t tf_err;
uintptr_t tf_eip;
uint16_t tf_cs;
uint16_t tf_padding4;
uint32_t tf_eflags;
/* below here only when crossing rings, such as from user to kernel */
uintptr_t tf_esp;
uint16_t tf_ss;
uint16_t tf_padding5;
} __attribute__((packed));

显然,trap是用户态转为内核态时所作的操作,上述代码按照名字猜测,cs/ss/ds以及另外三个都是段寄存器的名称,该结构体应该是定义了从内核态切换到用户态所需要的数据。

我们着重看一下pro.c中的copy_thread函数来理解两者的作用。

1
2
3
4
5
6
7
8
9
10
11
static void
copy_thread(struct proc_struct *proc, uintptr_t esp, struct trapframe *tf) {
proc->tf = (struct trapframe *)(proc->kstack + KSTACKSIZE) - 1;
*(proc->tf) = *tf;
proc->tf->tf_regs.reg_eax = 0;
proc->tf->tf_esp = esp;
proc->tf->tf_eflags |= FL_IF;

proc->context.eip = (uintptr_t)forkret;
proc->context.esp = (uintptr_t)(proc->tf);
}

在内核态切换到用户态的过程中,该函数不仅使用了context切换上下文,还使用了tf去切换到用户态。这两者似乎有重复。

然而实际上,通过context代码可以看出来,所谓的上下文切换,只是单纯的切换了寄存器数据,并没有更改内核态为用户态,仅用context切换数据的进程还处于原先的状态,context里面的eip寄存器,用来存储CPU要读取指令的地址,而esp只有设置为tf,才能执行用户代码。

练习2

练习2:为新创建的内核线程分配资源(需要编码)

创建一个内核线程需要分配和设置好很多资源。kernel_thread函数通过调用do_fork函数完成具体内核线程的创建工作。do_kernel函数会调用alloc_proc函数来分配并初始化一个进程控制块,但alloc_proc只是找到了一小块内存用以记录进程的必要信息,并没有实际分配这些资源。ucore一般通过do_fork实际创建新的内核线程。do_fork的作用是,创建当前内核线程的一个副本,它们的执行上下文、代码、数据都一样,但是存储位置不同。在这个过程中,需要给新内核线程分配资源,并且复制原进程的状态。你需要完成在kern/process/proc.c中的do_fork函数中的处理过程。它的大致执行步骤包括:

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

请在实验报告中简要说明你的设计实现过程。请回答如下问题:

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

注意该句:

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

显然,我们需要注意上下文、代码、数据

do_fork:

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
// 分配一个PCB
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--上下文
copy_thread(proc, stack, tf);
// 将子进程的PCB添加进hash表,让内核认识pcb
bool intr_flag;
local_intr_save(intr_flag);
{
proc->pid = get_pid();
hash_proc(proc);
list_add(&proc_list, &(proc->list_link));
nr_process ++;
}
local_intr_restore(intr_flag);
// 设置新的子进程可执行
wakeup_proc(proc);
// 返回子进程的pid
ret = proc->pid;

ucore是否做到给每个新fork的线程一个唯一的id?显然,既然需要加入hash表,那么一定可以唯一的标识一个线程,查看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
32
33
34
35
36
37
38
39
40
41
42
43
44
static int
get_pid(void) {
//确认pid大于进程数量
static_assert(MAX_PID > MAX_PROCESS);
struct proc_struct *proc;
list_entry_t *list = &proc_list, *le;
//注意是static,储存在静态存储空间而非栈
static int next_safe = MAX_PID, last_pid = MAX_PID;
//last_pid大于max_pid的话,设置last_pid=1
//即跳转到inside,重新设置next_safe
if (++ last_pid >= MAX_PID) {
last_pid = 1;
goto inside;
}
//last_pid>next_safe,
if (last_pid >= next_safe) {
inside:
next_safe = MAX_PID;
repeat:
le = list;
//分配唯一的pid
while ((le = list_next(le)) != list) {
//在proc_list构建结构体
proc = le2proc(le, list_link);
//两者pid相等的话
if (proc->pid == last_pid) {
//last_pid>=next_safe|max_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) {
//以proc的pid构建next_safe
next_safe = proc->pid;
}
}
}
return last_pid;
}

上述代码实际上是构建了一个next_safe,last_pid的区间。通过确认没有进程的id在则这个区间内部,来分配一个合适的pid。

通过移动last_pid(+1,重置时置1),移动proc->pid(已有进程的pid),以及next_safe(等于max_pid,分配成功时置为proc->pid)

结果:

需要注意的是,这个grade.sh有点问题,需要修改kern/mm/kmalloc.c的代码为:

1
2
3
void check_slab(void) {
cprintf("check_slab() succeeded!\n");
}

才可以100分。应该是设计评分系统时与之前输出语句不同,因此会造成上图的error

练习3

阅读代码,理解 proc_run 函数和它调用的函数如何完成进程切换的。(无编码工作)

请在实验报告中简要说明你对proc_run函数的分析。并回答如下问题:

  • 在本实验的执行过程中,创建且运行了几个内核线程?
  • 语句local_intr_save(intr_flag);....local_intr_restore(intr_flag);在这里有何作用?请说明理由

proc_run:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
// 设置ring0的内核栈地址
load_esp0(next->kstack + KSTACKSIZE);
// 加载页目录表
lcr3(next->cr3);
// 切换上下文
switch_to(&(prev->context), &(next->context));
}
local_intr_restore(intr_flag);
}
}

butterfly图:

涉及到的函数及注释:

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
static inline bool
__intr_save(void) {
//读取flag,关闭中断
if (read_eflags() & FL_IF) {
intr_disable();
return 1;
}
return 0;
}

/* *
* load_esp0 - change the ESP0 in default task state segment,
* so that we can use different kernel stack when we trap frame
* user to kernel.
* */
//加载内核栈基地址
void
load_esp0(uintptr_t esp0) {
ts.ts_esp0 = esp0;
}

//cr3页寄存器改为页目录表
static inline void
lcr3(uintptr_t cr3) {
asm volatile ("mov %0, %%cr3" :: "r" (cr3) : "memory");
}

//允许中断
static inline void
__intr_restore(bool flag) {
if (flag) {
intr_enable();
}
}



//kern/process/switch.S
.text
.globl switch_to
switch_to: # switch_to(from, to)

# save from's registers
movl 4(%esp), %eax # eax points to from
popl 0(%eax) # save eip !popl
#从这里开始保存寄存器到context
movl %esp, 4(%eax)
movl %ebx, 8(%eax)
movl %ecx, 12(%eax)
movl %edx, 16(%eax)
movl %esi, 20(%eax)
movl %edi, 24(%eax)
movl %ebp, 28(%eax)

# restore to's registers
#从这里开始恢复context
movl 4(%esp), %eax # not 8(%esp): popped return address already
# eax now points to to
movl 28(%eax), %ebp
movl 24(%eax), %edi
movl 20(%eax), %esi
movl 16(%eax), %edx
movl 12(%eax), %ecx
movl 8(%eax), %ebx
movl 4(%eax), %esp

pushl 0(%eax) # push eip

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

两个内核线程,分别是idleprocinitproc

首先是idleproc内核线程,该线程是最初的内核线程,完成内核中各个子线程的创建以及初始化。之后循环执行调度,执行其他进程。还有一个是initproc内核线程,该线程主要是为了显示实验的完成而打印出字符串"hello world"的内核线程。

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

见上文

challenge

实现支持任意大小的内存分配算法

这不是本实验的内容,其实是上一次实验内存的扩展,但考虑到现在的slab算法比较复杂,有必要实现一个比较简单的任意大小内存分配算法。可参考本实验中的slab如何调用基于页的内存分配算法(注意,不是要你关注slab的具体实现)来实现first-fit/best-fit/worst-fit/buddy等支持任意大小的内存分配算法。

由first-fit更改为best-fit代码参考github

核心代码为:

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
static void *best_fit_alloc(size_t size, gfp_t gfp, int align)
{
assert( (size + SLOB_UNIT) < PAGE_SIZE );
// This best fit allocator does not consider situations where align != 0
//确认align==0
assert(align == 0);
//slob大小
int units = SLOB_UNITS(size);

unsigned long flags;
spin_lock_irqsave(&slob_lock, flags);

slob_t *prev = slobfree, *cur = slobfree->next;
int find_available = 0;
int best_frag_units = 100000;
slob_t *best_slob = NULL;
slob_t *best_slob_prev = NULL;
//循环找到符合条件的单元
for (; ; prev = cur, cur = cur->next) {
if (cur->units >= units) {
// Find available one.
if (cur->units == units) {
// If found a perfect one...
prev->next = cur->next;
slobfree = prev;
spin_unlock_irqrestore(&slob_lock, flags);
// That's it!
return cur;
}
else {
// This is not a prefect one.
//如果不能完美的放进去,就更改你的best大小
if (cur->units - units < best_frag_units) {
// This seems to be better than previous one.
best_frag_units = cur->units - units;
best_slob = cur;
best_slob_prev = prev;
find_available = 1;
}
}

}

// Get to the end of iteration.
//符合条件就分配
if (cur == slobfree) {
if (find_available) {
// use the found best fit.
best_slob_prev->next = best_slob + units;
best_slob_prev->next->units = best_frag_units;
best_slob_prev->next->next = best_slob->next;
best_slob->units = units;
slobfree = best_slob_prev;
spin_unlock_irqrestore(&slob_lock, flags);
// That's it!
return best_slob;
}
// Initially, there's no available arena. So get some.
spin_unlock_irqrestore(&slob_lock, flags);
if (size == PAGE_SIZE) return 0;

cur = (slob_t *)__slob_get_free_page(gfp);
if (!cur) return 0;

slob_free(cur, PAGE_SIZE);
spin_lock_irqsave(&slob_lock, flags);
cur = slobfree;
}
}
}

本文作者: Heeler-Deer
本文链接: https://heeler-deer.github.io/2022/05/07/ucore-lab4/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!