Project 1: Threads #

需要提交代码和文档。代码即为包含了 pintos/src 的源代码，文档则是在本网站 Resources 区“实验文档模板”和“Project 1 DesignDoc 模板”的整合版本，云平台上可下载。请将其整合导出为一个 PDF 文件，命名为 p1-组长学号-组长姓名.pdf ，并与代码文件打包为 Zip，提交至云平台。

提交的目录结构为：

p1-组长学号-组长姓名
   ├── pintos
      ├── src
      ......
   ├── p1-组长学号-组长姓名.pdf

本次实验的 DDL 是 2021 年 11 月 11 日晚 23 时。

实验背景知识 #

Pintos 简介 #

Pintos 是一个小型的操作系统，其运行在 x86 硬件模拟器 bochs 之上。其已经实现了一个功能较少的操作系统，我们要做的事情就是给这个操作系统添加功能。

Pintos 结构图如上所示。和市面上常见的操作系统类似，Pintos 将整个体系分为了用户态和内核态，用户态的程序通过系统调用获得内核的服务。其操作系统内核主要分为进程管理、内存管理、文件系统、设备驱动程序等四个部分。本次实验所涉及到的主要是进程管理的部分，同学们需要根据需求实现特定的进程调度方案。

Pintos 目录结构 #

本节将主要给大家介绍 Pintos 中比较重要的几个文件夹。

在整个 Pintos 实验课中，我们要修改的代码都在 src 目录下。Project 1 的实验中，我们所要修改的文件主要集中在 src/threads 和 src/devices 这两个目录中，由于具体实现方式不同，有的同学也会有可能修改到少量其他目录中的文件。

.
├── devices # 包含一些与硬件交互的内容
├── examples # 包含 Pintos 对一些常用 Shell 命令的实现
├── filesys # 包含 Pintos 中对文件系统的实现
├── lib # 包含 C 语言中的一些标准库
├── LICENSE
├── Make.config
├── Makefile
├── Makefile.build
├── Makefile.kernel
├── Makefile.userprog
├── misc
├── tests # 包含各实验的测试文件
├── threads # 包含 Pintos 对于内核线程的实现
├── userprog # 包含 Pintos 对于用户线程的实现
├── utils
└── vm
10 directories, 6 files

实验运行方式 #

在实验正式开始前，请同学们修改文件 pintos/src/tests/Make.tests 中的第 55 行

TESTCMD = pintos -v -k -T $(TIMEOUT) # 修改前
TESTCMD = pintos -k -T $(TIMEOUT) # 修改后

否则，在某些同学的电脑上可能测试无法正常进行。

修改完毕后，在 Project 1 实验中，代码的运行方式为：

1. 进入 src/threads 目录
2. 使用 make clean 命令清除上次编译后的信息
3. 使用 make check 命令对文件进行编译并运行，首次运行会得到如图所示的过点信息：

pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
FAIL tests/threads/alarm-simultaneous
FAIL tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
FAIL tests/threads/priority-change
FAIL tests/threads/priority-donate-one
FAIL tests/threads/priority-donate-multiple
FAIL tests/threads/priority-donate-multiple2
FAIL tests/threads/priority-donate-nest
FAIL tests/threads/priority-donate-sema
FAIL tests/threads/priority-donate-lower
FAIL tests/threads/priority-fifo
FAIL tests/threads/priority-preempt
FAIL tests/threads/priority-sema
FAIL tests/threads/priority-condvar
FAIL tests/threads/priority-donate-chain
FAIL tests/threads/mlfqs-load-1
FAIL tests/threads/mlfqs-load-60
FAIL tests/threads/mlfqs-load-avg
FAIL tests/threads/mlfqs-recent-1
pass tests/threads/mlfqs-fair-2
pass tests/threads/mlfqs-fair-20
FAIL tests/threads/mlfqs-nice-2
FAIL tests/threads/mlfqs-nice-10
FAIL tests/threads/mlfqs-block
21 of 27 tests failed.

常用文件介绍 #

1. 在 src/tests/threads 文件夹中，包含了实验一的所有测试文件。
2. make check 之后，src/threads 中会生成一个 build 文件，文件夹 src/threads/build/tests/threads 中包含了程序在每一个测试点的输出。

实验介绍 #

本次实验一共有三个小任务，本文档将依次对它们进行介绍。 实验一文档中有更加详细的介绍，同学们做实验过程中有任何疑问都可以自行查阅官方文档。

任务一：唤醒时钟 #

这个是本次实验中最为简单的一个任务。在原始的代码实现中，timer_sleep() 函数的实现如下：

void
timer_sleep (int64_t ticks)
{
  int64_t start = timer_ticks ();
  ASSERT (intr_get_level () == INTR_ON);
  while (timer_elapsed (start) < ticks)
    thread_yield ();
}

由代码最后两行，在原本的代码实现中，timer_sleep() 函数实现的是一个“忙等待”，当线程在调用 timer_sleep() 函数之后，会睡眠 ticks 个单位时间。

根据题意，我们所要做的事便是消除这种忙等待。根据这个要求，可以想到使用时钟中断。在 thread.h 文件中，可以看到，Pintos 线程一共有以下几个状态：

enum thread_status
{
    THREAD_RUNNING,     /* 运行态。 */
    THREAD_READY,       /* 就绪态。 */
    THREAD_BLOCKED,     /* 阻塞态。 */
    THREAD_DYING        /* 销毁态。 */
};

因此，线程睡眠时，我们可以将其设置为阻塞态。而睡眠时间结束之后，将其设置为就绪态即可。

在第一个小实验中，涉及到的测试点一共有以下几个：

注意点：

需要考虑到睡眠时长为 0 或者负数的情况

任务二：优先级调度 #

这是本次实验最难的任务，主要包含以下两大部分：实现优先级调度和实现优先级捐赠。

实现优先级调度 #

优先级调度概念：

在原始的代码实现中，线程的就绪队列基本采用的是先来先服务（FCFS）的调度方式，即先进入就绪队列的线程在调度时会先获得 CPU，这个实验的目的是将这种调度策略改成优先级调度。即当一个线程被添加到就绪列表中，并且该线程的优先级高于当前正在运行的线程时，当前线程应该立即将处理器交付给新线程。类似地，当有多个线程正在等待锁、信号量或条件变量时，优先级最高的等待线程应该首先被唤醒。

在 Pintos 中，线程优先级范围为 0 到 63。 较低的数字对应较低的优先级，因此优先级 0 是最低优先级，优先级 63 是最高优先级。 线程创建时默认的优先级为 PRI_DEFAULT = 31。

在这一部分涉及的代码测试点主要有：

注意点：

在实现优先级调度的时候，不仅仅需要考虑线程的就绪队列，还要考虑信号量和条件变量的等待队列。

实现优先级捐赠 #

优先级捐赠概念：

在本实验中，优先级捐赠主要是针对线程对于锁的获取的。例如：如果线程 H 拥有较高的优先级，线程 M 拥有中等的优先级，线程 L 拥有较低的优先级。此时若线程 H 正在等待 L 持有的锁, 且 M 一直在就绪队列之中，那么线程 H 将永远无法获得 CPU。因此，这个时候需要将 H 的优先级捐赠给 L。

H        M        L
|                 ^
|                 |
└------------------
       申请锁

注意点：

1. 一个锁只能被单个线程持有，而一个线程却可以持有多个锁。当线程持有多个锁时，需要将线程的优先级设置为其被捐赠的优先级中最大的。
2. 会出现递归捐赠的问题。例如当前存在一个高优先级线程 H，一个中优先级线程 M，一个低优先级线程 L。如果 H 正在申请 M 持有的锁，M 正在申请 L 持有的锁，那么 M 和 L 的优先级都需要被设置为 H 的优先级。

  等待锁    等待锁
H   ->   M   ->   L

以下是这部分内容所涉及的测试点：

任务三：高级调度 #

在优先级调度策略之中，高优先级的进程永远抢占着 CPU，而低优先级线程能获得的时间非常少。在本实验中，我们会实现更加复杂的调度器，该实验所实现的调度器会自动维护线程的优先级。同样的，在任何给定的时间，调度程序从最高优先级的非空队列中选择一个线程。本实验需要弄清楚以下几个概念：

1. ready_threads：代表当前正在处于运行态和就绪态的线程的数量。
2. load_avg：代表对过去一秒钟内准备运行的线程的数量的估计，其初始值被设置为 0，每一秒（100 个 ticks），load_avg 会按照以下公式进行更新：load_avg = 59/60 * load_avg + 1/60 * ready_threads。
3. recent_cpu：每一个线程都拥有的变量，反应该线程获得 cpu 的多少。每一个 ticks，正在运行的线程的 recent_cpu 会增加 1。每一秒(100 个 ticks)，所有的线程的 recent_cpu 会按照以下公式进行更新：recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu + nice。
4. nice：代表线程对其他线程的友好程度，取值范围为 0 到 20，nice 值为 0 不会影响该线程的优先级，nice 值越大，该线程对其他线程越友好，即该线程的优先级越低，线程创建时初始 nice 值为 0。
5. priority：线程的优先级，每四个 ticks，线程的优先级应当按照以下公式进行更新：priority = PRI_MAX - 1/4 * recent_cpu - 2 * nice。

注意点：

1. 在 Pintos 中，存在一个 thread_mlfqs 的布尔量控制高级调度，当其值为 true 时，使用高级调度，当值为 false 时，使用优先级调度。高级调度和优先级调度存在少部分冲突，需要特殊判断。
2. 如果前两个任务实现的时间复杂度过高，会影响该任务的测试。
3. 使用公式计算的优先级可能超出 Pintos 设定的优先级范围(0-63)
4. 在本实验之前请各位确保已经阅读 任务三详细文档，本实验中涉及到浮点运算的部分都需要使用该文档中所提及到的方法。

任务三的测试样例如下：