文章

南京大学操作系统课程实验报告

发表于
作者 曾荣豪
47 分钟阅读
南京大学操作系统课程实验报告

这些实验包括一个大项目实验和一些小实验，我先说一下大项目实验吧。

第一个实验是实现malloc和free，叫pmm。

第二个实验是在第一个实验的基础上，增加中断和线程管理的功能，允许操作系统代码注册中断发生时的回调函数和创建线程，模块名是kmt，要实现的东西有：

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

typedef Context *(*handler_t)(Event, Context *);
MODULE(os)
{
    void (*init)();
    void (*run)();
    Context *(*trap)(Event ev, Context *context);
    void (*on_irq)(int seq, int event, handler_t handler);
};

MODULE(pmm)
{
    void (*init)();
    void *(*alloc)(size_t size);
    void (*free)(void *ptr);
};

typedef struct task task_t;
typedef struct spinlock spinlock_t;
typedef struct semaphore sem_t;
MODULE(kmt)
{
    void (*init)();
    int (*create)(task_t *task, const char *name, void (*entry)(void *arg), void *arg);
    void (*teardown)(task_t *task);
    void (*spin_init)(spinlock_t *lk, const char *name);
    void (*spin_lock)(spinlock_t *lk);
    void (*spin_unlock)(spinlock_t *lk);
    void (*sem_init)(sem_t *sem, const char *name, int value);
    void (*sem_wait)(sem_t *sem);
    void (*sem_signal)(sem_t *sem);
};

我的task_t包括一个栈和一些元数据。

框架会提供一个函数os->trap(ev, context)，在中断发生的时候，context保存有中断发生时的上下文，这个上下文保存在task的栈上，如果是cpu中断，我要实现一个调度函数，保存并选择一个新的task恢复到cpu上，然后继续执行。

create和teardown函数是创建和销毁一个进程，首先我要使用malloc创建一个task_t，然后指定入口函数和入参，框架会提供一个接口，调用这个接口可以将pc指向entry，然后我可以把这个task放到调度的队列里面等待调度。

还有六个关于自旋锁和信号量的函数。

做完这些可以得到一个支持多线程的内核。

然后是第三个实验（uproc），这个实验在 pmm 和 kmt 的基础上，增加用户态的进程。在这个实验中，操作系统将会加载第一个用户态进程 (进程的代码 “硬编码” 在操作系统启动时的内存中)，并且允许用户态进程执行系统调用。实现以下系统调用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

MODULE(uproc) {
    void (*init)();
    int (*kputc)(task_t *task, char ch);
    int (*fork)(task_t *task);
    int (*wait)(task_t *task, int *status);
    int (*exit)(task_t *task, int status);
    int (*kill)(task_t *task, int pid);
    void *(*mmap)(task_t *task, void *addr, int length, int prot, int flags);
    int (*getpid)(task_t *task);
    int (*sleep)(task_t *task, int seconds);
    int64_t (*uptime)(task_t *task);
};
int kputc(task_t *task, char ch)
{
    putch(ch); // safe for qemu even if not lock-protected
    return 0;
}

框架会提供操作页表的接口 void map (AddrSpace *as, void *vaddr, void *paddr, int prot);简单来说，就是修改当前线程的页表，将虚拟地址vaddr映射到物理地址

1

int fork(task_t *task);

创建当前进程 (状态机) 的一个副本：

  • 创建的进程从用户态执行看来没有任何区别，除了 GPRx (rax) 的返回值：父进程返回子进程进程号，子进程返回 0。
  • 实现 Copy-on-Write 。
1

void *mmap(task_t *task, void *addr, int length, int prot, int flags);

修改进程的地址空间，为其分配一个地址不小于 addr、对其到页边界 (protect 返回 AddrSpace 中的 pgsize)、大小不小于 length 的一段内存。

flags (已定义在框架代码中)：

  • MAP_SHARED - 在 fork 时，该内存在父子进程之间共享。
  • MAP_PRIVATE - 在 fork 时，该内存会被复制一份 (尽可能地实现成 copy-on-write)。
  • MAP_UNMAP - 删除从 addr 开始、长度为 length 的映射 (而不是分配)。

prot 映射权限：

  • PROT_READ - 可读。
  • PROT_WRITE - 可写。
允许 PROT_READPROT_WRITE 这样的权限。

我只列出了最重要的两个系统调用，剩下的系统调用和正如其名

以上是三个大项目的实验，还有五个小项目的实验，我摘抄一些课程主页上的介绍

1. 实现 pstree 打印进程之间的树状的父子关系

Linux 系统中可以同时运行多个程序。运行的程序称为进程。除了所有进程的根之外，每个进程都有它唯一的父进程，你的任务就是把这棵树在命令行中输出。你可以自由选择展示树的方式 (例如使用缩进表示父子关系，这是最容易的)。

这个实验并没有给很多具体的指导，当时做的时候卡了很长时间。

2. 协程库 (libco)

在这个实验中，我们实现轻量级的用户态携谐协程 (coroutine，“协同程序”)，也称为 green threads、user-level threads，可以在一个不支持线程的操作系统上实现共享内存多任务并发。即我们希望实现 C 语言的 “函数”，它能够：

  • 被 start() 调用，从头开始运行；
  • 在运行到中途时，调用 yield() 被 “切换” 出去；
  • 稍后有其他协程调用 yield() 后，选择一个先前被切换的协程继续执行。

这个小实验对实现第二个大实验有很大帮助。

3. 实现命令行工具 sperf COMMAND [ARG]...

它会在系统中执行 COMMAND 命令 (如果 COMMAND 是以 / 开头的绝对路径，则直接执行；否则在 PATH 环境变量中搜索到第一个存在且可执行的文件)，并为 COMMAND 传入 ARG 参数 (列表)，然后统计命令执行的系统调用所占的时间。例如执行 sperf find / 会在系统中执行 find /，并且在屏幕上显示出耗时最多的若干系统调用的时间。

一些假设和约定：

  • 输出的形式不限。对于较短时间运行的程序，你可以一次性打印出耗时最多的几个系统调用；对于耗时较长的程序，你需要定期 (如每秒) 打印出系统调用的耗时信息；
  • 假设 COMMAND 是单进程、单线程的，无需处理多进程 (fork) 和多线程 (clone/pthread_create) 的情况；虽然 strace 明确支持多进程/多线程程序。
  • 作为对大家的考验，必须使用 execve 系统调用；使用 glibc 对 execve 的包装 (execl, execlp, execle, execv, execvp, execvpe) 将导致编译错误，但我们鼓励你阅读后者的手册。

实际上是使用strace这个已有的程序，并通过管道获取他的输出，再整理统计信息并打印出来，完成这个实验可以加深对系统调用的认识

4. crepl 逐行从 stdin 中输入，根据内容进行处理。

  • 如果输入的一行定义了一个函数，则把函数编译并加载到进程的地址空间中；
  • 如果输入是一个表达式，则把它的值输出。

这个是他的演示：

5. frecov

在这个实验中，我们要求你编写程序，best-effort 恢复经过了快速格式化的文件系统中 bmp 格式的图片即可 (即尽可能地抢救文件即可)。

你需要实现命令行工具 frecov，给定一个格式化过的 FAT32 文件系统镜像，假设其中绝大部分文件都是以 BMP 格式存储的。请你尽可能地从文件系统中恢复出完整的图片文件。命令行工具使用方法：

frecov FILE

其中 FILE 是一个 FAT-32 文件系统的镜像。每恢复一张图片文件 (完整的文件，包含 BMP 头和所有数据)，调用系统中的 sha1sum 命令获得它的校验和，在标准输出中逐行输出图片文件的校验和以及你恢复出的文件名。只有校验和与文件名都恢复正确且一致，才被认为正确恢复了一个文件。

这个实验要求我们阅读手册，可以锻炼手册阅读的能力


进程与虚拟内存部分实验报告

一、实验目的

  1. 理解进程的概念，了解描述一个进程的基本数据结构。
  2. 理解什么是中断，如何利用中断来实现调度，错误处理，page_fault处理，系统调用等等。
  3. 学会多线程（在此实验中表现为多处理器）编程。
  4. 学会虚拟内存的概念，理解x86架构下页表的实现，了解何为用户态地址空间。
  5. 学会linux下gnu工具链的使用，学会调试代码。

二、实验内容

1.进程管理实验

实验要求：

设计进程的数据结构，利用时钟中断执行调度算法，保存并恢复上下文，实现互斥锁，实现信号量，让多个进程可以并发执行，实现一系列系统调用。

以下是要实现的结构体和系统调用，在内核中可以通过 MODULE(name) 来定义一个模块，然后通过 #include "klib.h" 来使用这个模块，以下是 klib.h 中的定义：

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

typedef Context *(*handler_t)(Event, Context *);
MODULE(os)
{
    void (*init)();
    void (*run)();
    Context *(*trap)(Event ev, Context *context);
    void (*on_irq)(int seq, int event, handler_t handler);
};

MODULE(pmm)
{
    void (*init)();
    void *(*alloc)(size_t size);
    void (*free)(void *ptr);
};

typedef struct task task_t;
typedef struct spinlock spinlock_t;
typedef struct semaphore sem_t;
MODULE(kmt)
{
    void (*init)();
    int (*create)(task_t *task, const char *name, void (*entry)(void *arg), void *arg);
    void (*teardown)(task_t *task);
    void (*spin_init)(spinlock_t *lk, const char *name);
    void (*spin_lock)(spinlock_t *lk);
    void (*spin_unlock)(spinlock_t *lk);
    void (*sem_init)(sem_t *sem, const char *name, int value);
    void (*sem_wait)(sem_t *sem);
    void (*sem_signal)(sem_t *sem);
};

实验过程：

在这个实验中，设计上，我使用了轮询调度算法，这个算法实现比较简单，我认为我完成这个实验的目的是初步的学习一个操作系统是怎么搭建起来的，所以并没有运用到更高级的算法。

这里的task_t是我要实现的进程的数据结构，spinlock_t是我要实现的自旋锁的数据结构，sem_t是我要实现的信号量的数据结构。task_t是保存进程上下文和状态的数据结构，即PCB，以下是task_t的定义：

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

struct task
{
    union
    {
        struct
        {
            int id;
            enum
            {
                RUNNING = 1,
                RUNNABLE,
                ZOMBIE,
                DEAD,
                CAN_BE_CLEAR
            } status;                 // 当前task状态
            struct spinlock lock;     // 锁
            char name[KMT_NAME_SIZE]; // task名
            void *entry;              // task 最初的入口
            void *arg;                // task 入参
            struct task *next;        // 指向下一个节点
            Context *context;         // 指向保存的上下文的地址，这个地址在task_t的kstack里
            AddrSpace as;             // 保存着用户态的地址空间范围，一个page的大小和cr3
            struct task *parent;      // 记录着此线程的父线程
            int exit_status;          // 记录着此线程是否以及调用exit
            struct
            {
                struct
                {
                    uintptr_t va, pa;
                    int prot;        // PROT_NONE PROT_WRITE PROT_READ
                    int flags;       // MAP_PRIVATE MAP_SHARED MAP_UNMAP
                    int page_nums;   // 标记含有几个page
                } log[KMT_LOG_SIZE]; // 记录map过的pa，存储进程内存段的信息，简单的设计成一个数组
                int log_len;
            };

            uint8_t fence[KMT_FENCE_SIZE]; // 用来防止overflow
        };

        uint8_t stack[KMT_STACK_SIZE]; // 栈指针
    };
}; // 这样做使整个task的大小为KMT_STACK_SIZE，我设置成了8k

kmt是线程管理模块，我使用了一个链表来存放所有的task

调用kmt->create时，我会先使用malloc创建一个task_t，然后将调用框架代码kcontext创建一个上下文，kcontext会正确的设置rsp，pc，rdi等等寄存器，然后这个上下文会保存在task_t的stack上，最后将这个task_t加入到task_list中，以下是kmt->create的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13

static int kmt_create(task_t *task, const char *name, void (*entry)(void *arg), void *arg)
{
    char buf[32];
    strncpy(buf, name, 32);
    kmt->spin_init(&task->lock, strcat(buf, " spin lock"));
    task->status = RUNNABLE;
    task->entry = entry;
    task->arg = arg;
    task->context = kcontext((Area){.start = &task->fence + 1, .end = task + 1}, entry, arg);
    strncpy(task->name, name, KMT_NAME_SIZE);
    memset(task->fence, 'x', KMT_FENCE_SIZE);
    return task_list_insert(task);
}

当发生时钟中断后，框架会将进程上下文保存在kstack上，并设置context指向存放的地址，然后我会将这个线程设置成RUNNABLE（而不是RUNNING）然后遍历一遍task链表，找到第一个RUNNABLE（多处理器下会有别的处理器在执行进程）的task，然后返回它的context给框架代码，这个框架代码会接着执行进程。

核心代码如下：

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

static Context *yield_handler(Event ev, Context *context)
{
    int saved = ienabled();
    iset(0); // 设置关闭中断
    Context *ret = NULL;

    // 保存当前进程
    if (current_task != NULL)
    {
        kmt->spin_lock(&current_task->lock);
        if (current_task->status == DEAD)
        {
            current_task->status = CAN_BE_CLEAR;
            kmt->spin_unlock(&current_task->lock);
            kmt->teardown(current_task);
            current_task = task_list.head;
        }
        else if (current_task->status == ZOMBIE)
        {
            // 不改成RUNNABLE, 不记录context
            kmt->spin_unlock(&current_task->lock);
        }
        else
        {
            current_task->context = context;
            current_task->status = RUNNABLE;
            kmt->spin_unlock(&current_task->lock);
        }
    }
    else
    {
        current_task = task_list.head;
    }

    // 选择下一个进程执行
    if (current_task == NULL)
    { // 到这里还是NULL的话，没有task被创建，直接返回ctx
        ret = context;
    }
    else
    {
        kmt->spin_lock(&task_list.lock); // 锁整个链表
        do
        {
            current_task = current_task->next;
        } while (current_task->status != RUNNABLE);
        current_task->status = RUNNING;
        kmt->spin_unlock(&task_list.lock);
        ret = current_task->context;
    }
    iset(saved);
    return ret;
}

剩余还有自旋锁和信号量的实现，这两个的实现比较简单，就不贴代码了。

实验成果：

做完这个实验之后，我使用了框架提供的测试代码，这是两个虚拟的终端设备，我可以切换这两个不同的终端，然后输入一些内容，这个终端会输出接收了多少个字符。

以下是演示：

2.虚拟内存管理

实验要求：

加载一个用户态的进程，使用MMU让用户态地址能够映射到物理地址，实现进程分裂函数fork，设计共享内存和私有内存的语义，并将私有内存实现成copy-on-write，实现一系列的系统调用。

实验过程：

在这个实验中，一个用户态的代码将被硬编码到内核内存中，此用户态代码可以调用系统调用。以下是需要实现的系统调用：

1
2
3
4
5
6
7
8
9
10
11
12
13

MODULE(uproc)
{
    void (*init)();
    int (*kputc)(task_t *task, char ch);
    int (*fork)(task_t *task);
    int (*wait)(task_t *task, int *status);
    int (*exit)(task_t *task, int status);
    int (*kill)(task_t *task, int pid);
    void *(*mmap)(task_t *task, void *addr, int length, int prot, int flags);
    int (*getpid)(task_t *task);
    int (*sleep)(task_t *task, int seconds);
    int64_t (*uptime)(task_t *task);
};

首先，要先将用户态代码运行起来，再考虑实现系统调用，这个用户态代码的汇编代码会通过一个数组保存起来，并被内核用 #include引入，然后我会使用malloc创建两个一页大小（我设置为4k）的内存，通过框架代码 void map(AddrSpace *as, void *vaddr, void *paddr, int prot);我用内存空间as里最低的空间存放这个用户态代码，用最高的空间作为栈，然后使用框架代码 Context *ucontext (AddrSpace *as, Area kstack, void *entry);创建一个线程上下文，将rsp指针指向最高空间的末尾，然后将这个上下文加入到task_list中等待调用。以下是uinit代码实现：

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

int uinit(task_t *task, const char *name, void (*entry)(void *arg), size_t len)
{
    assign_id(&task->id);

    char buf[32];
    strncpy(buf, name, 32);
    kmt->spin_init(&task->lock, strcat(buf, "user spin lock"));
    task->status = RUNNABLE;
    task->arg = NULL;
    task->log_len = 0;
    task->parent = NULL;
    protect(&task->as);

    void *place = pmm->alloc(task->as.pgsize);
    memcpy(place, entry, len);
    void *begin = task->as.area.start;
    // 先给用户态代码找一个地方存放
    log_map(task, begin, place, PROT_READ | PROT_WRITE, MAP_PRIVATE, 1);

    void *pstack = pmm->alloc(task->as.pgsize);
    uint64_t vrsp = (uint64_t)task->as.area.end;
    void *vstack = (void *)vrsp - task->as.pgsize;

    // 再map一个栈给它
    log_map(task, vstack, pstack, PROT_READ | PROT_WRITE, MAP_PRIVATE, 1);

    task->context = ucontext(&task->as, (Area){.start = &task->fence + 1, .end = task + 1}, begin);
    task->context->rsp = vrsp;
    task->entry = begin;

    strncpy(task->name, name, KMT_NAME_SIZE);
    memset(task->fence, 'x', KMT_FENCE_SIZE);
    return task_list_insert(task);
}

在task的内核元数据里，我会保存所有的段到PCB的log里，当这个进程销毁的时候会根据这个映射释放资源，而当调用fork时，新的进程会再重新进行一次映射，得到一个和父线程一模一样的副本，除了fork的返回值即$RAP寄存器，其中replay是对所有映射的页的再次映射，我使用哈希表来记录一个被映射的物理页的引用计数，当replay时，我会让所有的内存段指向的物理页的引用计数加一，当进程退出时，对所有页的引用计数减一，减到0时就释放空间，以下是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
28

static int fork(task_t *task)
{
    task_t *tasknew = (task_t *)pmm->alloc(sizeof(task_t));
    // 将父进程的所有信息拷贝到子进程
    memcpy(tasknew, task, sizeof(task_t));
    L(&task->lock);
    tasknew->parent = task;
    assign_id(&tasknew->id);
    protect(&tasknew->as); // 重新初始化页表

    uint64_t offect = (uint64_t)(task + 1) - (uint64_t)task->context;
    tasknew->context = (Context *)((uint64_t)(tasknew + 1) - offect);

    // 将cr3指向新的页表
    tasknew->context->cr3 = tasknew->as.ptr;
    // 返回值设置为0
    tasknew->context->GPRx = 0;
    // 内核栈指针设置为子进程的内核栈地址
    tasknew->context->rsp0 = (uintptr_t)(tasknew + 1);
    // 加入进程队列
    tasknew->status = RUNNABLE;
    replay(task, tasknew);
    task->context->GPRx = tasknew->id;
    task_list_insert(tasknew);
    U(&task->lock);

    return 0; // 不使用返回值
}

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

static void replay(task_t *taskold, task_t *tasknew)
{
    for (int i = 0; i < taskold->log_len; i++)
    {
        if (taskold->log[i].flags & MAP_PRIVATE)
        { // COW
            for (int j = 0; j < taskold->log[i].page_nums; j++)
            {
                // 对所有页面map
                // 先unmap
                map(&taskold->as, (void *)taskold->log[i].va + taskold->as.pgsize * j, NULL, MMAP_NONE);

                // 修改映射成只读，当pagefault时，查看此虚拟页被引用的次数，决定cow或改映射
                map(&taskold->as, (void *)taskold->log[i].va + taskold->as.pgsize * j, (void *)taskold->log[i].pa + taskold->as.pgsize * j, MMAP_READ);
                // 不修改prot，要在page_handler 中检查
                // 记录是一样的，所以不用log_map
                map(&tasknew->as, (void *)tasknew->log[i].va + taskold->as.pgsize * j, (void *)tasknew->log[i].pa + taskold->as.pgsize * j, MMAP_READ);
                increase((void *)taskold->log[i].pa + taskold->as.pgsize * i);
            }
        }
        else if (taskold->log[i].flags & MAP_SHARED)
        {
            for (int j = 0; j < taskold->log[i].page_nums; j++)
            {
                int prot = taskold->log[i].prot;
                int map_prot = (prot & PROT_READ) ? MMAP_READ : 0;
                map_prot |= (prot & PROT_WRITE) ? MMAP_WRITE : 0;

                map(&tasknew->as, (void *)tasknew->log[i].va + taskold->as.pgsize * j, (void *)tasknew->log[i].pa + taskold->as.pgsize * j, map_prot); // 记录是一样的，所以不用log_map
                increase((void *)taskold->log[i].pa + taskold->as.pgsize * j);
            }
        }
        else
        { // MAP_UNMAP nothing to do
            ;
        }
    }
}

接下来是 void *mmap(task_t *task, void *addr, int length, int prot, int flags);的实现，这个mmap可以是只读或可读可写的，并且可以设置成是shared或private的，对于shared的页，父子进程的相同用户页会映射到同一个物理页。对于private的页，如果是可读可写的，一开始我会将子进程的页映射到同一个物理页，并将这个页设置为只读，当父进程或子进程进行写入操作时，会引起page_fault，这个时候我会新建一个页，并修改引起page_fault的进程的页表，让其指向新的物理页，以下是mmap的实现：

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

static void *mmap(task_t *task, void *addr, int length, int prot, int flags)
{
    L(&task->lock);
    if (flags == MAP_UNMAP)
    {
        for (int i = 0; i < task->log_len; i++)
        {
            if ((void *)task->log[i].va != addr || task->log[i].flags == MAP_UNMAP)
            {
                continue;
            }
            for (int j = 0; i < task->log[i].page_nums; j++)
            {
                decrease((void *)task->log[i].pa + task->as.pgsize * j); // ref减小到0就会free掉
                map(&task->as, addr, NULL, MMAP_NONE);
            }
            task->log[i].flags = MAP_UNMAP;
            break;
        }
        U(&task->lock);
        return NULL;
    }
    else
    {
        addr = (void *)ROUNDUP(addr, task->as.pgsize);
        length = (int)ROUNDUP(length, task->as.pgsize);
        void *paddr = pmm->alloc(length);
        log_map(task, addr, paddr, prot, flags, length / task->as.pgsize);
    }
    U(&task->lock);
    return addr;
}
// 记录map，更新pa的引用次数，fork时简单的replay
void log_map(task_t *task, void *vaddr, void *paddr, int prot, int flags, int page_nums)
{
    task->log[task->log_len].va = (uintptr_t)vaddr;
    task->log[task->log_len].pa = (uintptr_t)paddr;
    task->log[task->log_len].prot = prot;
    task->log[task->log_len].flags = flags;
    task->log[task->log_len].page_nums = page_nums;
    task->log_len++;
    int map_prot = (prot & PROT_READ) ? MMAP_READ : 0;
    map_prot |= (prot & PROT_WRITE) ? MMAP_WRITE : 0;
    for (int i = 0; i < page_nums; i++)
    {
        increase(paddr + task->as.pgsize * i);
        map(&task->as, vaddr + task->as.pgsize * i, paddr + task->as.pgsize * i, map_prot);
    }
}

这是page_fault的处理代码：

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 Context *page_handler(Event ev, Context *ctx)
{
    int index = 0;
    void *va = (void *)ROUNDDOWN(ev.ref, current_task->as.pgsize);

    task_t *cur = current_task;

    for (; index < cur->log_len; index++)
    {
        // 先查看修改的页是否在页表中
        if (cur->log[index].va <= (uintptr_t)va && (uintptr_t)va < cur->log[index].va + cur->log[index].page_nums * cur->as.pgsize)
            break;
    }

    panic_on(index == cur->log_len, "page_handler");
    // 新建一个mmap区
    void *pa_new = (void *)pmm->alloc(cur->as.pgsize * cur->log[index].page_nums);
    void *pa_old = (void *)cur->log[index].pa;
    size_t size = cur->as.pgsize * cur->log[index].page_nums;

    memcpy(pa_new, pa_old, size);

    for (int i = 0; i < cur->log[index].page_nums; i++)
    {
        // 先取消映射
        map(&cur->as, va + i * cur->log[index].page_nums, NULL, MMAP_NONE);
        // 修改映射到新建的一个区
        map(&cur->as, va + i * cur->log[index].page_nums, pa_new + i * cur->log[index].page_nums, MMAP_READ | MMAP_WRITE);
        // decrease函数会在一个页被映射的次数为0时free掉此页
        decrease(pa_old + i * cur->log[index].page_nums);
        // increase函数会增加一个页被映射的次数
        increase(pa_new + i * cur->log[index].page_nums);
    }
    cur->log[index].pa = (uintptr_t)pa_new;
    return ctx;
}

实验成果：

我用了一段用户代码来验证我的实现是否正确，这段代码会创建一个子进程，然后子进程和父进程都会分别对一个私有以及共有mmap区进行写入，然后父进程会等待子进程结束，然后打印出这个mmap区的内容，如果实现正确，父进程打印出来的共有区内容应该是和子进程写入后一样的，而私有区的内容应该是自己写入的内容。

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
71
72
73
74
75
76
77
78
79
80
81
82

#include "ulib.h"

void puts(char *s)
{
    int i = 0;
    while (s[i] != '\0')
    {
        syscall(SYS_kputc, s[i], 0, 0, 0);
        i++;
    }
}
void lf()
{
    syscall(SYS_kputc, '\n', 0, 0, 0);
}
void strcpy(char *dst, char *src)
{
    for (int i = 0; src[i] != '\0'; i++)
    {
        dst[i] = src[i];
    }
}

int main()
{
    int id;

    char *map_shared_addr = (char *)syscall(SYS_mmap, (long)main + 4096, 4096, PROT_READ | PROT_WRITE, MAP_SHARED);
    *((char *)map_shared_addr) = '0';
    puts("far shared before: ");
    strcpy(map_shared_addr, "shared memory created by farther\n");
    puts(map_shared_addr);

    void *map_private_addr = (void *)syscall(SYS_mmap, (long)main + 10000, 4096, PROT_READ | PROT_WRITE, MAP_PRIVATE);
    *((char *)map_private_addr) = '0';
    puts("far private before: ");
    strcpy(map_private_addr, "private memory created by farther\n");
    puts(map_private_addr);

    for (int i = 0; i < 1; i++)
    { // 创建一个子进程
        if ((id = syscall(SYS_fork, 0, 0, 0, 0)) == 0)
        { // son
            puts("in son before modify shared memory: ");
            puts(map_shared_addr);

            puts("in son after modify shared memory: ");
            strcpy(map_shared_addr, "shared memory modified by son\n");
            puts(map_shared_addr);

            puts("in son before modify praivate memory:");
            puts(map_private_addr);

            puts("in son after modify praivate memory:");
            strcpy(map_private_addr, "private memory modified by son\n");
            puts(map_private_addr);

            return 0;
        }
    }
    int a;
    for (int i = 0; i < 100000000; i++)
    { // sleep
        a++;
    }

    puts("in far after son modify shared memory: ");
    puts(map_shared_addr);

    puts("in far after son modify praivate memory: ");
    puts(map_private_addr);

    while (1)
    {
        int status;
        syscall(SYS_wait, (long)&status, 0, 0, 0);
        if (status != -1)
            syscall(SYS_kputc, status + '0', 0, 0, 0);
    }

    return 0;
}

3.libco 协程实验

实验要求：

在这个实验中，我们实现轻量级的用户态携谐协程 (coroutine，“协同程序”)，也称为 green threads、user-level threads，可以在一个不支持线程的操作系统上实现共享内存多任务并发。即我们希望实现 C 语言的 “函数”，它能够：

  • 被 start() 调用，从头开始运行；
  • 在运行到中途时，调用 yield() 被 “切换” 出去；
  • 稍后有其他协程调用 yield() 后，选择一个先前被切换的协程继续执行。

这个实验我认为是最有意思的一个小实验，这个实验的设计思想我认为和操作系统的进程上下文切换很类似，不过每个协程是手动地让出CPU的，而不是被中断后由操作系统调度的。

实验过程：

在这个实验中，我使用了一个数组来存放所有的协程，以下是协程的数据结构：

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

enum co_status
{
    CO_NEW = 1, // 新创建，还未执行过
    CO_RUNNING, // 已经执行过
    CO_WAITING, // 在 co_wait 上等待
    CO_DEAD,    // 已经结束，但还未释放资源
};

struct co
{

    __uint8_t stack[STACKSIZE]; // 协程的堆栈
    const char *name;
    void (*func)(void *); // co_start 指定的入口地址和参数
    void *arg;

    enum co_status status; // 协程的状态
    struct co *waiter;     // 是否有其他协程在等待当前协程
    jmp_buf jb;            // 寄存器现场 (setjmp.h)
};

struct _q
{
    struct co *array[128];
    size_t size;
};

首先一个线程要调用co_start来开启一个协程，这个函数会创建一个协程，然后将这个协程加入到数组中，然后调用co_yield来切换到这个协程，以下是co_start的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13

struct co *co_start(const char *name, void (*func)(void *), void *arg)
{
    struct co *newco = malloc(sizeof(struct co));
    newco->name = name;
    newco->func = func;
    newco->arg = arg;
    newco->status = CO_NEW;
    newco->waiter = NULL;

    push(newco);

    return newco;
}

在co_yield函数中，我会调用setjmp来保存寄存器状态，这个函数会返回两次，当从别的协程切换回来时，setjmp会返回1，这个时候我会直接返回，当从co_start切换回来时，setjmp会返回0，这个时候我会调用pick函数来选择一个协程来执行，如果这个协程是新创建的，我会在栈的顶部设置一个返回函数，当这个协程进行的函数返回时，会接着进入co_finish函数，这个函数会将协程的状态设置成CO_DEAD，然后切换到别的协程（不是使用co_yield），以下是co_yield和co_finish的实现：

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

void co_yield ()
{
    int val = setjmp(current->jb);
    if (val == 0)
    {
        // pick one routinue to run
        struct co *next = pick();

        // printf("cur:%s cur->status:%d next:%s next->status:%d\n", current->name, current->status, next->name, next->status );
        // printf("yield():");
        // co_print();
        current = next;
        if (next->status == CO_NEW)
        {

            void *base = (void *)((((uintptr_t)next) + STACKSIZE) & ~0xf); // 获取对齐的地址
            next->status = CO_RUNNING;

            void **retfun = base - sizeof(void *);
            *retfun = co_finish;
            // printf("base=%p next=%p next+stacksize=%p\n" , base, next, &next->stack[STACKSIZE]);
            stack_switch_call(base - sizeof(void *), next->func, (uintptr_t)next->arg); // 数据结构在堆上申请，低地址是结构的第一个参数，而栈是向下增长，所以要用高地址作为栈顶
        }
        else
        {
            longjmp(next->jb, 1);
        }
    }
    else
    {
        ;
    }
}
static void co_finish()
{
    current->status = CO_DEAD;
    if (current->waiter != NULL)
    {
        // switch to waiter
        // struct co*temp = current;s
        current = current->waiter;
        longjmp(current->jb, 0);
    }
    else
    {
        // switch to other
        // pick one routinue to run
        struct co *next = pick();

        // printf("cur:%s next:%s\n", current->name, next->name);
        current = next;
        if (next->status == CO_NEW)
        {

            void *base = (void *)((((uintptr_t)next) - 15 + STACKSIZE) & ~0xf); // 获取对齐的地址
            next->status = CO_RUNNING;

            void **retfun = base - sizeof(void *);
            *retfun = co_finish;
            // printf("base=%p next=%p next+stacksize=%p\n" , base, next, &next->stack[STACKSIZE]);
            stack_switch_call(base - sizeof(void *), next->func, (uintptr_t)next->arg); // 数据结构在堆上申请，低地址是结构的第一个参数，而栈是向下增长，所以要用高地址作为栈顶
        }
        else
        {
            longjmp(next->jb, 1);
        }
    }
}

这个实验还设计了一个co_wait函数，这个函数会让当前协程等待另一个协程，当这个协程结束时，waiter会清理这个协程，以下是co_wait的实现：

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

void co_wait(struct co *co)
{
    while (1)
    {
        if (co->status == CO_DEAD)
        {
            delete (co);
            free(co);
            int i = 0;
            for (; i < q.size; i++)
            { // 如果没人等，那就改状态
                if (q.array[i]->waiter == current)
                {
                    break;
                }
            }
            if (i == q.size)
            {
                current->status = CO_RUNNING;
            }
            break;
        }
        else
        {
            co->waiter = current;
            current->status = CO_WAITING;
            co_yield ();
        }
    }
}

但是我认为这个co_wait是不需要的，因为我认为协程应该是一个独立的执行单元，不应该有等待的概念，意思就是在返回之后直接清除这个协程，但是想到既然线程也同时有等待和分离的概念并且实验要求实现这个函数，而且测试代码也用到了这个函数，我还是实现了这个函数。实验没有要求实现co_finish函数，但是我认为这个函数是必须的，因为如果没有这个函数，协程执行完毕后会直接返回，而栈顶的返回地址是随机的，因为他超出了栈的范围，这样会导致程序崩溃，不实现这个函数，那么表明这个协程不能通过返回退出，这显然不合理，所以我认为这个实验的要求可以有所改进。

实验成果：

通过这个实验，我了解了协程的工作原理，什么是协程，如何写一个协程框架的demo，我认为这个实验的趣味性是挺强的。并且这个实验对第二个大实验即进程调度实验很有帮助，所以我添加了这个实验的介绍。

三、实验结论

这些就是我在大二下学期进行的实验的一部分，全部包括了三个大实验和五个小实验，花费了我大概三个多月的时间，现在回顾起来，我还是认为这个实验充满挑战，同时也感觉到收获满满，其实我当时在纠结是看mit6.828还是南京大学的实验，因此我找了一个群的群友问了下，他们说南京大学的课程难度更高一点，然后我就想着挑战一下高难度的东西，因此我就尝试了这个课程而不是mit的课程。当时在做的时候说实话是有点自闭的，难度是真的大，我在睡觉的时候都在想这个实验的内容，他的课程网页里的指导看过一遍又一遍，实现出来的时候bug还很多，我其实考虑过放弃，但是我觉得既然都选择了这个课程，那就要坚持下去，不过苦尽甘来，最后我认为我还是实现了基本的功能，能够将这个系统跑起来了，但是由于我不能使用他的网上评测，也就不能验证正确性，不过我认为这也变相地降低了些许难度，我也没有追求更完善的实现，因为我认为这个课程的目的是让我学习操作系统基本的知识，而不是让我写一个完美的操作系统，所以我认为我已经达到了这个课程的目的。

做完这个实验之后，我感觉我的代码能力得到了很大的提升，感谢这个课程，感谢公开这个课程的老师，也感谢我自己的坚持。

在进程管理实验中，我学习了进程的概念，学习了如何用数据结构描绘一个进程的状态，了解在内核中进程是如何调度的，学会了什么是中断，如何处理中断。学会如何使用互斥锁，并通过一段多线程的程序验证自己的代码是否正确。学会如何存储一个进程的上下文，学会如何在进程间切换。加强了我多线程编程的能力。

在虚拟内存实验中，我学习了如何在内核中加载用户态代码，如何使用MMU将用户态地址映射到物理地址，如何实现fork，如何实现系统调用，完成这个实验后加深了我对虚拟内存的理解，对MMU的理解，对系统调用的理解，对copy-on-write的理解。

总的来说，通过这个课程的所有实验，我不仅学习了操作系统的知识，同时我的代码能力也得到了增强，现在的我已经懂得如何使用gdb调试代码。懂得如何在Linux下使用gnu工具链。学会如何配置Makefile。并且学会了如何使用git进行版本控制。这个课程给我的收获颇丰，我相信这个课程会对我的未来工作有很大的帮助。这个课程老师在最后一堂课上说的话我觉得很有意义，我也想引用在这里：

你们这一代人有很大的一个使命，就是重新定义什么是“专家”，“专家”不是一个得了什么什么奖，发了多少多少成果，“专家”是那些愿意站出来颠覆一个行业的人，那些能管理好工程项目的人，那些能驾驭的了大规模代码的人，去共同完成一些旁人看起来“惊为天人”的事情，去推动人类的进步，去改变世界的人。

本文由作者按照 CC BY 4.0 进行授权