【OS Pintos】Pintos 内核库基本数据结构 | 运行测试用例 alarm-multiple

💭 写在前面

Pintos 是操作系统课程下的一项动手实践，简单来说就是让你撸出一个操作系统。本篇博客是第一篇，先带着大家了解了解 Pintos 内核基本的数据结。随后我草草记录了一些我们配置 Pintos 的过程，且可能并不适用所有人，过程并不完整！配置Pintos环境请参考别处！作为斯坦福操作系统项目实践的 Pintos，难度极大，需要很多时间去做，工程浩大。Pintos 非常有价值，可以从中学到很多东西。

Ⅰ.  Pintos 内核库基本数据结构

0x00 引入：介绍

在我们在学习 Pintos 之前，我们将练习 Pintos 数据结构。

Pintos提供了内核和用户库，你可以在 pintos/src/lib/kernel 和 pintos/src/lib/user 中找到它。

在这个项目中，我们将介绍 Pintos 内核库的数据结构：List, Hash table and Bitmap.

0x01 链表（List）

Pintos 中的链表是一个双链表。

它不同于我们常见的链表结构，它是将链表元素的指针和数据分开的。

struct list_elem：

• 每个将成为链表项的结构都必须嵌入一个 struct list_elem 成员。
• 所有的链表函数都在 list_elem 上操作，而不是在链表项上。
• 源代码中只给出了 list_elem 结构。
• 你必须实现由 list_elem 和数据组成的新结构。

* 源代码中没有给出 'struct list_item' ，你需要自己实现！

📚 链表函数分析：

void list_init(struct list *list)

• 将 LIST 初始化为一个空链表。
• 应该在 LIST 中插入一个元素之前被执行。
  

struct list_elem* list_begin(struct list *list)

• 返回链表的首元素
• 通常用于链表的遍历（遍历的起始位置）

struct list_elem* list_next(struct list_elem *elem)

• 返回 ELEM 的下一个元素。
• 通常用于遍历链表或在链表中搜索 ELEM。

struct list_elem* list_end(struct list *list)

• 返回 LIST 中的最后一个 ELEM。
• 通常用于链表的遍历（遍历的终点位置）

#define list_entry(list_elem, struct, member)

• 将 list_elem 的指针转换成 list_elem 所嵌入的 struct 的指针。
• 通常用于获取嵌入list_elem 的 struct 的地址。

/* Assume that there already exists a list, sample_list */
struct list_elem *e;
e = list_begin (&sample_list);
struct list_item *temp = list_entry(e, struct list_item, elem)
int temp_data = temp->data
By using list_elem, we can get address of list_item

0x02 哈希表（Hash Table）

哈希表是一种将键与值关联的数据结构，主要操作是查找，给定一个键，找到相应的值。

它是通过使用 hash function 将 key 转换为散列工作的。

📚 哈希表函数分析：

void hash_init (
    struct hash *h, 
    hash_hash_func *hash, 
    hash_less_func *less, 
    void *aux
    )

• 初始化哈希表H，设置哈希函数 HASH 和比较函数 LESS。
• 你可以看到哈希函数的例子，如 hash_int，hash_bytes 和 hash_string（你必须使用 hash_int 函数才能通过测试）。
• 比较函数LESS是用来比较两个哈希元素的。

void hash_apply (
    struct hash *h, 
    hash_action_func *action
    )

• 你可以将你制作的任何 ACTION 函数应用于哈希表 H。
• 用于将特定的函数应用于哈希表的所有元素，例如：平方函数。
• 你可以从 tester 目录下的 "hash_apply.in" 和 "hash_apply.out " 中了解它的用法。

#define hash_entry(hash_elem, struct, member)

• 将 hash_elem 的指针转换成 hash_elem 所嵌入的 struct 的指针。
• 通常用于获取嵌入 hash_elem 的 struct 的地址。
  

struct hash_elem {
    struct list_elem list_elem;
};

0x03 位图（Bitmap）

bit array（位数组），在某些情况下或称为位图（bitmap）。

位图是一个存储单个位（布尔值）的阵列，位图（bitmap）可以减少内存空间的浪费。

📚 位图函数分析：

struct bitmap *bitmap_create(size_t bit_cnt)

初始化一个 BIT_CNT 位的位图，并将其所有位设置为 False。

void bitmap_set (struct bitmap *b, size_t idx, bool value)

原子化式地将 b 中编号为 idx 的位设置为 value。

size_t bitmap_count (
    const struct bitmap *b, 
    size_t start, 
    size_t cnt, 
    bool value
    )

返回 start 和 start + cnt 之间的 b 中设置为 value 的位数。

Ⅲ.  Pintos 环境配置

0x00 介绍 （Pintos & Emulator）

📚 Pintos 是基于 80x86 架构的简易 OS 框架，它利用系统模拟器模拟 80x86 CPU 及其外设。

📃 项目类别：

• 用户程序（User Programs）
• 内核线程（Kernel Threads）
• 虚拟内存（Virtual Memory）
• 文件系统（File Systems）

💡 项目特点：

• 支持用户（user）和内核线程（kernel thread）
• 允许运行用户程序，使用基本的 UNIX 命令，譬如 echo, ls, cat, pwd…
• 支持简单的文件系统
• 它是用纯C实现的
• 能很好地记录项目 & 拥有评分系统

我们将利用 QEMU 作为 Pintos 的仿真器！

KVM 和 Qemu 都是 Linux 操作系统的虚拟化解决方案。之所以把 KVM 和 Qemu 捆绑安装在一起，是因为 KVM 和 Qemu 存在着互补的关系。

👻 虚拟化（Virtualization）：通过管理程序提供内核转换和资源分配等功能，以运行一个可以使用虚拟机中硬件的操作系统。

🐴 仿真（Emulation）：在软件中实现硬件，从而提供一个特定的执行环境。

0x01  安装 Pintos

Step1：下载 Pintos 文件

🔗 资源链接：点击 snapshot 下载

或直接获取最新的 Pintos，git clone git://pintos-os.org/pintos-anon

Step2：安装 QUMU

sudo apt-get install qemu

Step3：把压缩文件 ftp 传输到云服务器上，并解压文件。

$ tar -xvf pintos_modified.tar.gz

Step4：运行前准备

运行 Pintos 前，我们需要进入 home 目录设置 .bashrc 文件：

这里我们可以用记事本打开它：

nano ~/.bashrc

在文件末尾处添加下列信息：

export PATH=/sogang/under/<你的学号>/pintos/src/utils:$PATH

当然这里也可以使用 vim 打开， i 进入插入模式，编辑完后   :wq   退出即可。

0x02 运行 Pintos

Step1：构建Pintos（默认已经解压完毕了）

$ cd ~/pintos/src/threads    # 跳转至pintos的threads目录
$ make                       # Makefile

这么做是为了在当前目录（src/threads）下创建 "build" 目录。

① cd 至 thread 目录：

② Makefile：

…… 此处省略一万字

完毕。

Step2：运行 Pintos

Pintos 提供了 "Pintos"  utility ，用于帮助 QEMU 运行 Pintos。

"Pintos" utility 位于 src/utils 中

转到 src/threads 目录下并运行以下命令（应该在 threads 目录下运行而不是在 utils 目录 ）

可能当前你已经在这个目录了， pwd 看一下在不在，不在就 cd

$ cd ~/pintos/src/threads

在 src/threads 路径下输入：

$ ../utils/pintos -v -- -q run alarm-multiple

（注意，要在 -v（关闭VGA）、-- 和 -q（执行后退出）之间输入一个空格）

📌 注意：如果遇到如下错误，请自行 pwd 检查运行 pintos 的当前目录。

如果当前目录是 src/utils ，Pintos 就无法找到其内核，从而导致错误。

如果在 src/threads 中执行 Pintos，Pintos 将在 src/threads/build/kernel.bin 中成功找到内核。

0x03 项目测试

每个项目都有自己专属的测试程序，测试程序在 src/tests 中。

你可以使用这些测试程序去测试自己实现的项目。

例如在 Project3 中，您可以通过在 src/threads 目录下输入 make check 进行测试。

~/pintos/src/threads $ make check

每个测试用例都能一目了然地显示 PASS 或 FAIL。

📌 [ 笔者 ]   王亦优
📃 [ 更新 ]   2022.9.17
❌ [ 勘误 ]   /* 暂无 */
📜 [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！