ucore-lab4

本文最后更新于：2023年6月22日 上午

知识点

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

练习解答

实验目的

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

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

  • 内核线程只运行在内核态
  • 用户进程会在在用户态和内核态交替运行
  • 所有内核线程共用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 context和struct 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
  • 在本实验的执行过程中，创建且运行了几个内核线程？

两个内核线程，分别是idleproc和initproc

首先是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;
		}
	}
}
blog
cs ucore

本文作者: Heeler-Deer
本文链接: https://heeler-deer.top/posts/27771/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！