> For the complete documentation index, see [llms.txt](https://osh.fducslg.com/operating-systems-h-24fall/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://osh.fducslg.com/operating-systems-h-24fall/shi-yan/lab-3-user-process.md).

# Lab 3: User Process

负责助教：[陈可](mailto:kchen21@m.fudan.edu.cn)

在本实验中，我们将完善 Lab2 中实现的进程概念，在系统中运行简单的用户态进程。

## 1. 更新

* 更新了信号量的规则，引入了信号量的锁定和解锁机制，便于借助信号量实现更丰富的同步功能。详见 `common/sem.c` 和 `common/sem.h` 。不影响原有代码，但是你可能需要注意一些使用信号量和锁带来的并发问题。
* 在通过 Lab2 的测试后，**请将`activate_proc`中 「若`thisproc()->state==ZOMBIE`则panic」 的规则去除**（如果你是这样写的话）。如果`thisproc()->state==ZOMBIE`，请不做任何操作，并返回false。这项改动有助于你编写`kill`函数。
* 在时钟中断上抽象出了CPU定时器的概念。详见 `kernel/cpu.c` 和 `kernel/cpu.h`。
* 在 `sched` 函数中添加了 `attach_pgdir(&next->pgdir)` ，用于在进入用户态时设置页表。
* 修复了 `common/list.c` 中 `queue_push` 没有增加 `x->sz` 的问题。

## 2. 服务器操作

运行以下命令进行代码的拉取与合并

```shell
# 拉取远端仓库
git fetch --all

# 提交你的更改
git add .
git commit -m "your commit message"

# 切换到新lab的分支
git checkout lab3

# 新建一个分支，用于开发
git checkout -b lab3-dev

# 引入你在上个lab的更改
git merge lab2-dev
```

如果合并发生冲突，请参考错误信息自行解决。

## 3. 页表

理论课中已经学习过分页内存管理的概念。AArch64将64位虚拟地址分为0xffff开头的和0x0000开头的两部分，分别成为高地址和低地址。在我们的实验中，内核代码使用的内存被映射到高地址，用户代码使用的内存被映射到低地址。

高地址的页表基地址寄存器为`ttbr1`，低地址的页表基地址寄存器为`ttbr0`。这两个寄存器都只能在内核模式下访问，他们保存相应页表的**物理地址**。在我们的实验中，默认使用4KB页大小的4级页表，你可以参考ARM Manual，了解此类页表的具体结构，对于实验中出现的简单情况，也可以参考上课时的讲解。页表中的大多数特性我们的实验并没有用到，但了解详细情况有助于你后续扩展功能。

## 4. 系统调用

**系统调用**（system call），指运行在用户空间的程序向操作系统内核请求需要更高权限运行的服务。系统调用提供用户程序与操作系统之间的接口。大多数系统交互式操作需求在内核态执行。如设备IO操作或者进程间通信。

用户程序运行在受限的上下文下，如需访问系统资源，需要通过系统调用陷入内核态，由内核处理请求。系统调用类似于一种特殊的异常，用户程序执行系统调用指令（svc）后，陷入内核态，内核在`trap_global_handler`中识别出类型，然后执行相应操作。

我们的实验采用通用的系统调用约定：x8寄存器存放请求的系统调用id，x0-5寄存器存放系统调用的六个参数。系统调用返回时，设置x0寄存器为系统调用的返回值。

## 5. 任务

{% hint style="success" %}
**任务1**

完成页表配置的相关代码。我们在`Proc`中添加了`pgdir`项，存储进程的用户态内存空间的相关信息。`pgdir`是定义在`pt.h`中的结构体，`pgdir.pt`指向进程的用户页表。如果进程是纯内核态进程，则`pgdir.pt`可以为空。该结构体在后续实验中还会加入内容，我们这里暂时不用关心。

* 你需要完成`pt.c`中的`get_pte`函数。该函数遍历给定的`pgdir`，从中找到对应于指定虚拟地址的页表项，并返回页表项的指针。如果页表项不存在（即其所在的页表未创建），若alloc标记为true，则创建和配置页表项所在的页表及其上级页表（如果需要），然后返回有效的页表项指针，否则返回NULL。（返回的指针指向的页表项可以是无效的。请注意区分页表项和它所引用的物理页。）
* 你需要完成`pt.c`中的`free_pgdir`函数。该函数释放给定的`pgdir`。请注意只要释放页表本身所占的空间，不要释放页表所引用的物理页。（页表所引用的物理页目前由测试代码直接管理。在后续实验中，我们会逐渐完成相关的代码，本次实验只要求大家完成页表本身的操作。）
* 你可能需要在`proc.c`的`init_proc`中加入`init_pgdir`，在`exit`中加入`free_pgdir`。
  {% endhint %}

{% hint style="success" %}
**任务2**

完成系统调用的相关代码。我们在`trap.c`中已经提供了在系统调用时调用`syscall_entry`的代码，你需要完成`syscall.c`中的`syscall_entry`函数。该函数传入UserContext作为参数，请从中提取出相应的寄存器，查询`syscall_table`，执行指定的系统调用，并将系统调用的返回值保存到指定的寄存器。
{% endhint %}

{% hint style="success" %}
**任务3**

修改你的UserContext。你需要保证UserContext中有spsr、elr、sp（`sp_el0`）寄存器，并结合你的UserContext 添加 `test/user_proc.c` 中的 TODO 部分。
{% endhint %}

{% hint style="success" %}
**任务4**

完成结束进程相关的代码。结束进程的逻辑参考了xv6和Linux的设计。我们在`proc.c`中添加了一个函数`kill`。调用kill会设置指定进程的killed标记，并唤醒进程，阻止进程睡眠。进程在返回用户态时会检查killed标记，若有则调用exit退出。

* 实现`proc.c`中的`kill`函数。该函数遍历进程树，搜索指定pid且状态不为unused（可参考`sched.c`中给出的`is_unused`，访问调度信息时加锁是个好习惯，但这里其实不加锁也没啥事）的进程，如果进程不存在，返回-1。对于找到的进程，设置`struct proc`的`killed`标记，并调用`activate_proc`唤醒进程。完成之后，返回0。请注意使用进程树的锁。
* 修改你的`sched`代码，使其能够保证，如果当前进程带有killed标记，且new state不为zombie，则调度器直接返回，不做任何操作。（为什么？）
* 在`aarch64/trap.c`的`trap_global_handler`函数的末尾加上检查，如果当前进程有killed标记且即将返回到用户态，则调用`exit(-1)`。
  {% endhint %}

{% hint style="success" %}
**任务5**

改进你的调度器。Lab2的内核进程调度是非抢占式的，Lab3要求大家进行抢占式的调度，你可能需要在调度器中加入时钟中断相关的代码，并注意**调度的公平性问题**。另请注意：我们现在在时钟中断的基础上封装了一层CPU定时器的抽象，**请使用CPU定时器**。
{% endhint %}

我们在`user_proc.c`中编写了用户页表和用户进程相关的测试代码，在`cpu.c`中通过CPU定时器添加了CPU定时输出消息的代码。如果一切正常，你将看到`vm_test PASS`和`user_proc_test PASS`。

测试还会输出4个CPU和22个进程的工作量，请确认CPU和进程间的相对工作量是否分别基本平衡。

## 6. 提交

**提交方式**：将实验报告提交到 elearning 上，格式为 `学号-lab3.pdf`。

**注意**：从`lab1`开始，用于评分的代码以实验报告提交时为准。如果需要使用新的代码版本，请重新提交实验报告。

**截止时间**：<mark style="color:red;">**10月25日23:59**</mark>。

{% hint style="danger" %}
**逾期提交将扣除部分分数**

计算方式为 $$\text{score}\_{\text{final}} = \text{score} \cdot \left(1 - n \cdot 20% \right)$$，其中 $$n$$ 为迟交天数，不满一天按一天计算）。
{% endhint %}

报告中可以包括下面内容

* 代码运行效果展示
* 实现思路和创新点
* 对后续实验的建议
* 其他任何你想写的内容

  > ~~你甚至可以再放一只可爱猫猫~~

报告中不应有大段代码的复制。如有使用本地环境进行实验的同学，请联系助教提交代码（最好可以给个`git`仓库）。使用服务器进行实验的同学，助教会在服务器上检查，不需要另外提交代码。

在服务器上操作的同学，此次实验完成后请提交（或者说创建一个新分支）到 `lab3-submission` 分支，助教会使用你在此分支上提交记录来批作业。如果此分支最后提交时间晚于实验报告提交时间，助教会选择此分支上在实验报告提交时间前的最后一个提交作为批改代码。

**提交操作**：

```shell
# 提交最后的代码
git add .
git commit -m "your final commit message"

# 新建一个分支，用于提交
git checkout -b lab3-submission
```