A. Reference Guide#

本章是Pintos代码的参考。参考指南未涵盖Pintos中的所有代码，但确实涵盖了学生最常发现的麻烦部分。您可能会发现，当您在重要的项目上工作时，您想阅读参考指南的每个部分。

我们建议使用“tags”来跟踪对函数和变量名称的引用（请参见F.1标签)部分）。

A.1 Loading#

本节介绍Pintos加载程序和基本内核初始化。

A.1.1 The Loader#

Pintos运行的第一部分是装载程序，在“threads/loader.S”。 PC BIOS将加载程序加载到内存中。反过来，加载程序负责在磁盘上查找内核，将其加载到内存中，然后跳转到其起始位置。确切了解加载程序的工作原理并不重要，但是如果您有兴趣，请继续阅读。您可能应该阅读加载程序的源代码。您还应该了解[IA32-v1]的第3章“基本执行环境”()中描述的80 x 86体系结构的基础。

PC BIOS从第一个硬盘的第一个扇区（称为主启动记录（MBR））加载加载程序。PC约定为分区表保留MBR的64个字节，而Pintos为内核命令行参数使用大约128个额外的字节。剩下的300个字节留给了加载程序自己的代码。这是一个严格的限制，实际上，这意味着加载程序必须使用汇编语言编写。

Pintos加载器和内核不必位于同一磁盘上，也不需要内核位于给定磁盘上的任何特定位置。然后，加载程序的第一项工作是通过读取每个硬盘上的分区表来查找内核，寻找用于Pintos内核的可引导分区。

当加载程序找到可引导的内核分区时，它将分区的内容读入物理地址为128 kB的内存中。内核位于分区的开头，由于分区边界对齐约定，它可能大于所需的大小，因此加载程序读取的内容不超过512 kB（Pintos构建过程将拒绝生成大于该值的内核）。读取的数据量超出这个范围，将跨越640 kB到1 MB的区域，这是PC体系结构为硬件和BIOS保留的空间，并且标准的PC BIOS没有提供任何方法来加载1 MB以上的内核。

加载程序的最后一项工作是从加载的内核映像中提取入口点，并将控制权转移到该入口点。入口点不在可预测的位置，但是内核的ELF标头包含指向它的指针。加载程序提取指针并跳转到其指向的位置。

Pintos内核命令行存储在引导加载程序中。每次运行内核时，pintos程序实际上都会在磁盘上修改引导加载程序的副本，插入用户提供给内核的命令行参数，然后内核在引导时从引导加载程序中读取这些参数。在记忆中。这不是一个很好的解决方案，但它简单有效。

A.1.2 Low-Level Kernel Initialization#

加载程序的最后一个动作是将控制权转移到内核的入口点，即“threads/start.S”中的“start()”。此代码的工作是将所有现代80 x 86操作系统使用的传统16位“实模式”的CPU切换到32位“保护模式”。

启动代码的第一个任务实际上是通过向BIOS询问PC的内存大小来获取机器的内存大小。最简单的BIOS功能只能检测到64 MB的RAM，因此这是Pintos可以支持的实际限制。该函数将内存大小（以页为单位）存储在全局变量“ init_ram_pages”中。

CPU初始化的第一部分是启用A20线，即CPU的地址线编号20。由于历史原因，PC会使用此地址线固定为0进行引导，这意味着尝试访问前1MB（ 2的20次方）将失败。 Pintos希望访问更多的内存，因此我们必须启用它。

接下来，加载器创建一个基本页表。此页表将虚拟内存（从虚拟地址0开始）的64MB直接映射到相同的物理地址。它还从虚拟地址“ LOADER_PHYS_BASE”开始映射相同的物理内存，默认地址为“ 0xc0000000”（3GB）。Pintos内核仅希望使用后者的映射，但是如果不包含前者，则存在一个鸡与蛋的问题：我们当前的虚拟地址大约是“ 0x20000”，即加载程序放置我们的位置，而我们不能跳转到“ 0xc0020000”，直到打开页表。但是如果我们不跳到那里，就不能打开页面表。这好比我们站在地毯上使劲拉地毯。

页表初始化后，我们加载CPU的控制寄存器以打开保护模式和分页，并设置段寄存器。 我们还没有能力在保护模式下处理中断，因此我们禁用了中断。 最后一步是调用main()。

A.1.3 High-Level Kernel Initialization#

内核本身以main()函数开头。 main()函数是用C编写的，从此以后，我们在Pintos中遇到的大多数代码都会如此。

当main()启动时，系统处于非常原始的状态。我们处于启用分页的32位保护模式下，但几乎没有其他准备就绪。因此，“ main()”函数主要包括对其他Pintos模块的初始化函数的调用。这些通常被命名为“ module_init()”，其中 module 是模块的名称，“module.c”是模块的源代码，“module.h”是模块的头。

main()的第一步是调用bss_init()，它清除了内核的“ BSS”，这是应该初始化为全零的段的传统名称。在大多数C实现中，只要在函数外部声明变量而不提供初始化程序，该变量就会进入BSS。因为全为零，所以BSS不会存储在加载程序带入内存的映像中。我们只是使用memset()将其归零。

接下来，main()调用read_command_line()将内核命令行分成参数，然后parse_options()读取命令行开头的所有选项。 （在命令行上指定的操作稍后执行。）

thread_init()初始化线程系统。我们将把完整的讨论推迟到下面的Pintos线程讨论中。之所以在初始化阶段这么早就调用它是因为有效的线程结构是获取锁的先决条件，而锁的获取又对其他Pintos子系统很重要。然后，我们初始化控制台，并将启动消息打印到控制台。

我们调用的下一个功能块将初始化内核的内存系统。 palloc_init()设置内核页面分配器，该页面一次分配一个或多个页面的内存（请参阅[A.5.1 页面分配器]节）。 “malloc_init()”设置处理任意大小的内存块分配的分配器（请参阅[A.5.2 块分配器]部分）。pages_init()为内核设置了一个页表（请参阅[A.7 页表]）。

在项目2和更高版本中，main()也调用tss_init()和gdt_init()。

下一组调用将初始化中断系统。 intr_init()设置CPU的*中断描述符表（IDT）以准备对其进行中断处理（请参阅A.4.1 中断基础结构部分），然后是timer_init()。和kbd_init()分别准备处理定时器中断和键盘中断。 “input_init()”设置为将串行和键盘输入合并为一个流。在项目2和更高版本中，我们还准备使用exception_init()和syscall_init()处理由用户程序引起的中断。

现在已经设置了中断，我们可以使用“thread_start()”启动调度程序，它创建空闲线程并启用中断。 启用中断后，中断驱动的串行端口I/O成为可能，因此我们使用“serial_init_queue()”切换到该模式。 最后，timer_calibrate()为精确的短延时校准定时器。

如果文件系统是从项目2开始编译的，我们将使用“ide_init()”初始化IDE磁盘，然后使用“filesys_init()”初始化文件系统。

引导完成，因此我们打印一条消息。

函数“run_actions()”现在解析并执行内核命令行上指定的操作，例如“运行”以运行测试（在项目1中）或用户程序（在以后的项目中）。

最后，如果在内核命令行上指定了“ -q”，我们将调用“ shutdown_power_off()”来终止机器模拟器。 否则，main()调用thread_exit()，它允许任何其他正在运行的线程继续运行。

A.1.4 Physical Memory Map#

@headitem Memory Range

Owner	Contents
`00000000`--`000003ff`	CPU	Real mode interrupt table.
`00000400`--`000005ff`	BIOS	Miscellaneous data area.
`00000600`--`00007bff`	--	---
`00007c00`--`00007dff`	Pintos	Loader.
`0000e000`--`0000efff`	Pintos	Stack for loader; kernel stack and `struct thread` for initial kernel thread.
`0000f000`--`0000ffff`	Pintos	Page directory for startup code.
`00010000`--`00020000`	Pintos	Page tables for startup code.
`00020000`--`0009ffff`	Pintos	Kernel code, data, and uninitialized data segments.
`000a0000`--`000bffff`	Video	VGA display memory.
`000c0000`--`000effff`	Hardware	Reserved for expansion card RAM and ROM.
`000f0000`--`000fffff`	BIOS	ROM BIOS.
`00100000`--`03ffffff`	Pintos	Dynamic memory allocation.

A.2 Threads#

A.2.1 struct thread#

Pintos中线程的主要数据结构是“struct thread”，在“threads/thread.h”中声明。

Structure: struct thread

• 表示线程或用户进程。在项目中，必须将自己的成员添加到“struct thread”中。您也可以更改或删除现有成员的定义。

• 每个“struct thread”都占据其自身内存页面的开始。页面的其余部分用于线程的堆栈，该堆栈从页面末尾开始向下增长。看起来像这样：

                  4 kB +---------------------------------+
                       |          kernel stack           |
                       |                |                |
                       |                |                |
                       |                V                |
                       |         grows downward          |
                       |                                 |
                       |                                 |
                       |                                 |
                       |                                 |
                       |                                 |
                       |                                 |
                       |                                 |
                       |                                 |
sizeof (struct thread) +---------------------------------+
                       |              magic              |
                       |                :                |
                       |                :                |
                       |              status             |
                       |               tid               |
                  0 kB +---------------------------------+

• 这带来两方面的影响。首先，“struct thread”不能太大。如果结构体太大，则内核堆栈空间就会不够。基本的“struct thread”只有几个字节大小。它可能应该保持在1kB以下。

• 其次，内核堆栈也不允许变得太大。如果堆栈溢出，它将破坏线程状态。因此，内核函数不应将大型结构或数组分配为非静态局部变量。而应该通过malloc()或palloc_get_page()使用动态分配代替（请参阅A.5 Memory Allocation）。

Member of struct thread: tid_t tid
线程的线程标识符即tid。在内核的整个生命周期中，每个线程必须具有唯一的id。默认情况下，“tid_t”是“int”类型的“typedef”，每个新线程接收下一个更大的tid数字，在初始过程中tid从1开始。您可以根据需要更改类型和编号方案。

Member of struct thread: enum thread_status status

• 线程的状态，值为以下之一：

• Thread State: THREAD_RUNNING
  > 线程正在运行。在给定的时刻有且仅有一个线程正在运行。thread_current()返回正在运行的线程。

• Thread State: THREAD_READY
  > 该线程已准备就绪，可以运行，但是目前尚未运行。可以选择该线程在下次调用调度程序时运行。就绪线程被保存在一个名为“ready_list”的双链表中。

• Thread State: THREAD_BLOCKED

  线程正在等待某些东西，例如一个锁变为可用，一个中断被调用。直到调用“thread_unblock()”转换为“THREAD_READY”状态后，线程才会再次进行调度。使用Pintos同步原语之一自动自动阻塞和取消阻塞线程，可以最方便地间接完成此操作（请参阅A.3同步）。

  没有一种先验的方法可以告诉阻塞的线程正在等待什么，但是回溯可以提供帮助（请参阅E.4回溯)部分）。

• Thread State: THREAD_DYING
  切换到下一个线程后，该线程将被调度程序销毁。

Member of struct thread: char name[16]

线程的名称. 字符串，或者至少是字符串的前几个字符。

Member of struct thread: uint8_t *stack

每个线程都有自己的堆栈来跟踪其状态。线程运行时，CPU的堆栈指针寄存器跟踪堆栈的顶部，指向未使用成员。但是，当CPU切换到另一个线程时，该成员将保存线程的堆栈指针。 不需要其他成员来保存线程的寄存器，因为必须保存的其他寄存器都保存在堆栈中。

当发生中断时，无论是在内核还是在用户程序中，都会将“struct intr_frame”压入堆栈。 当中断在用户程序中发生时，“struct intr_frame”始终位于页面的最顶端。有关更多信息，请参见A.4中断处理)部分。

Member of struct thread: int priority

线程优先级，范围从“PRI_MIN”（0）到“PRI_MAX”（63）。较低的数字对应较低的优先级，因此优先级0是最低优先级，优先级63是最高优先级。提供的Pintos忽略线程优先级，但是您将在项目1中实现优先级调度（请参见2.2.3 优先级调度）。

Member of struct thread: struct list_elem allelem

该“列表元素”用于将线程链接到所有线程的列表中。 每个线程在创建时都会插入到该列表中，在退出时会删除。 应该使用thread_foreach()函数来遍历所有线程。

Member of struct thread: struct list_elem elem

一个“列表元素”，用于将线程放入双向链接列表中，可以是“ ready_list”（准备运行的线程列表），也可以是等待“ sema_down()”中的信号量的线程列表。 它可以做双重任务，因为等待信号量的线程尚未准备好，反之亦然。

Member of struct thread: uint32_t *pagedir

• 仅存在于项目2和更高版本中。 请参见4.1.2.3 页表)。

Member of struct thread: unsigned magic

• 始终设置为THREAD_MAGIC，这是在threads/thread.c中定义的任意数字，用于检测堆栈溢出。 “thread_current()”检查运行线程的“结构线程”的“魔术”成员是否设置为“THREAD_MAGIC”。堆栈溢出往往会更改此值，从而触发断言。为了获得最大的利益，在将成员添加到“结构线程”时，请在最后保留“魔术”。

A.2.2 Thread Functions#

“threads/thread.c”实现了几个支持线程的公共函数。让我们看一下最有用的：

Function: void thread_init (void)

由“main()”调用以初始化线程系统。它的主要目的是为Pintos的初始线程创建一个“struct thread”。 这是可能的，因为Pintos加载程序将初始线程的堆栈放在页面顶部，与任何其他Pintos线程的位置相同。

在运行thread_init()之前，thread_current()将失败，因为正在运行的线程的magic值不正确。 许多函数直接或间接调用“ thread_current()”，包括用于锁定锁的“ lock_acquire()”，因此在Pintos初始化的早期就调用了“ thread_init()”。

Function: void thread_start (void)

由“ main()”调用以启动调度程序。创建空闲线程，即没有其他线程就绪时调度的线程。 然后启用中断，这是启用调度程序的一个副作用，因为调度程序使用intr_yield_on_return()在计时器中断返回时运行（请参阅[A.4.3 外部中断处理]）。

Function: void thread_tick (void)

在每个计时器滴答时由计时器中断调用。它跟踪线程统计信息，并在时间片到期时触发调度程序。

Function: void thread_print_stats (void)

在Pintos关闭期间调用以打印线程统计信息。

Function:tid_t thread_create (const char *name, int priority, thread_func *func, void *aux)

使用给定的priority创建并启动一个名为name的新线程，并返回新线程的tid。线程执行func，将aux作为函数的单个参数传递。

“thread_create()”为线程的“结构线程”分配一个页面并堆栈并初始化其成员，然后为其设置一组伪堆栈帧（请参阅[A.2.3 线程切换]）。 线程在阻塞状态下初始化，然后在返回之前解除阻塞，这允许安排新线程（请参阅[线程状态]）。

Type: void thread_func (void *aux)

这是传递给thread_create()的函数的类型，后者的aux参数作为函数的参数传递。

Function: void thread_block (void)
将正在运行的线程从运行状态转换为阻塞状态（请参阅[线程状态]）。 直到调用thread_unblock()线程才会再次运行，因此最好安排一些方法来实现。由于“thread_block()”的级别如此低，因此您应首选使用其中一个同步原语（请参见[A.3 同步]部分）。

Function: void thread_unblock (struct thread *thread)
将必须处于阻塞状态的 thread 转换为就绪状态，以使其可以继续运行（请参阅[线程状态]）。 当线程正在等待的事件发生时，例如 当线程正在等待的锁可用时。

Function: struct thread *thread_current (void)
返回正在运行的线程。

Function: tid_t thread_tid (void)
返回运行线程的线程ID。 相当于thread_current()-> tid。

Function: const char *thread_name (void) 返回运行线程的名称。 等同于“thread_current()-> name”。

Function: void thread_exit (void) NO_RETURN 导致当前线程退出。 永远不会返回，因此会返回“ NO_RETURN”（请参阅[E.3 函数和参数属性]。）

Function: void thread_yield (void)
将CPU交给调度程序，调度程序选择一个新线程来运行。新线程可能是当前线程，因此您不能依赖此函数来阻止该线程运行任何特定时间长度。

Function: void thread_foreach (thread_action_func *action, void *aux)

• 遍历所有线程t，并在每个线程上调用action（t，aux）。 action必须引用与thread_action_func()给出的签名相匹配的函数：

Type: void thread_action_func (struct thread *thread, void *aux)
给定aux，对线程执行一些操作。

Function: int thread_get_priority (void)

Function: void thread_set_priority (int new_priority) 设置并获取线程优先级的桩。 请参阅[2.2.3 优先级调度]

Function: int thread_get_nice (void)

Function: void thread_set_nice (int new_nice)

Function: int thread_get_recent_cpu (void)

Function: int thread_get_load_avg (void)
高级调度程序的存根。 参见[B. 4.4BSD Scheduler].

A.2.3 线程切换#

“schedule()”负责切换线程。它在“threads/thread.c”内部，仅由需要切换线程的三个公共线程函数调用：“thread_block()”，“thread_exit()”和“thread_yield()”。在任何这些函数调用schedule()之前，它们先禁用中断（或确保已将其禁用），然后将运行线程的状态更改为非运行状态。

“schedule()”很短，但很棘手。它将当前线程记录在局部变量cur中，确定下一个要作为局部变量next运行的线程（通过调用next_thread_to_run()），然后调用`switch_threads()做实际的线程切换。我们切换到的线程也正在switch_threads()内部运行，因为所有当前未运行的线程都在运行，因此新线程现在从switch_threads()中返回，并返回先前运行的线程。

switch_threads()是“ threads / switch.S”中的汇编语言例程。它将寄存器保存在堆栈中，将CPU当前的堆栈指针保存在当前的“struct thread”的stack成员中，将新线程的“stack”还原到CPU的堆栈指针中，从堆栈中还原寄存器, 然后返回。

调度程序的其余部分在`thread_schedule_tail()中实现。它将新线程标记为正在运行。如果我们刚从中切换的线程处于快死状态，那么它还会释放包含快死线程的struct thread和堆栈的页面。这些不能在线程切换之前被释放，因为切换需要使用它。

第一次运行线程是一种特殊情况。当thread_create()创建一个新线程时，它会经历很多麻烦才能正确启动。特别是，新线程尚未开始运行，因此无法如调度程序所期望的那样在新的switch_threads()内部运行。为了解决这个问题，thread_create()在新线程的堆栈中创建了一些假堆栈帧：

• 最顶层的伪堆栈帧是针对“ switch_threads()”的，由“ struct switch_threads_frame”表示。 该框架的重要部分是其“ eip”成员，即回信地址。 我们将eip指向switch_entry()，表明它是调用switch_entry()的函数。

• 下一个伪堆栈帧用于switch_entry()，这是“threads/switch.S”中的汇编语言例程，用于调整堆栈指针，（5）){＃3D“ DOCF5”}调用thread_schedule_tail()（这种特殊情况是为什么thread_schedule_tail()与`schedule()分开）并返回。 我们填写其堆栈框架，使其返回“threads/thread.c”中的函数kernel_thread()。

• 最后的堆栈帧用于kernel_thread()，它允许中断并调用线程的函数（该函数传递给thread_create()）。 如果线程的函数返回，则调用thread_exit()终止线程。

A.3 同步#

如果未谨慎、受控地处理线程之间的资源共享，则结果通常是一团糟。 在操作系统内核中尤其如此，错误的共享可能会使整个计算机崩溃。 Pintos提供了几种同步原语来提供帮助。

A.3.1 Disabling Interrupts#

进行同步的最粗略方法是禁用中断，即暂时阻止CPU对中断作出响应。如果中断关闭，则其他任何线程都不会抢占正在运行的线程，因为线程抢占是由计时器中断驱动的。如果中断像往常一样打开，则正在运行的线程可以随时被另一个线程抢占，无论是在两个C语句之间，还是在执行一个C语句之内。

顺便说一句，这意味着Pintos是“可抢占内核”，也就是说，内核线程可以随时被抢占。传统的Unix系统是“不可抢占的”，也就是说，内核线程只能在明确调用调度程序的位置被抢占。 （在两个模型中，用户程序都可以随时被抢占。）您可能会想到，可抢占的内核需要更明确的同步。

您几乎不需要直接设置中断状态。大多数时候，您应该使用以下各节中描述的其他同步原语。禁用中断的主要原因是使内核线程与外部中断处理程序同步，该外部中断处理程序无法休眠，因此无法使用大多数其他形式的同步（请参见A.4.3 外部中断处理)）。

即使禁用中断，某些外部中断也无法延迟。这些中断称为“不可屏蔽中断”（NMI），应该仅在紧急情况下使用，例如当计算机着火时。 Pintos不处理不可屏蔽的中断。

禁用和启用中断的类型和功能在“threads/interrupt.h”中.

Type: enum intr_level
“INTR_OFF”或“INTR_ON”之一，分别表示禁用或启用了中断.

Function: enum intr_level intr_get_level (void)
返回当前的中断状态。

Function: enum intr_level intr_set_level (enum intr_levellevel)
根据level打开或关闭中断。 返回上一个中断状态。

Function: enum intr_level intr_enable (void)
打开中断。返回上一个中断状态.

Function: enum intr_level intr_disable (void)
关闭中断。 返回上一个中断状态.

A.3.2 Semaphores#

semaphore是一个非负整数，以及两个对其进行原子操作的运算符，它们是：

• "Down" or "P": 等待值变正，然后递减.

• "Up" or "V": 增加值（并唤醒一个等待的线程，如果有的话）.

初始化为0的信号量可用于等待将仅发生一次的事件。例如，假设线程A启动了另一个线程B，并想要等待B发出信号，表明某些活动已完成。 A可以创建一个初始化为0的信号量，并在启动时将其传递给B，然后“降低”该信号量。当B完成其活动时，它将“升高”信号量。无论A先“降低”信号量还是B先升高信号量，此方法都有效。

初始化为1的信号量通常用于控制对资源的访问。在代码块开始使用资源之前，它将“降低”信号量，然后在完成资源处理后，将其“升高”资源。在这种情况下，如下所述的锁可能更合适。

信号量也可以初始化为大于1的值。很少使用。

信号量由Edsger Dijkstra发明，并首先在THE操作系统（Dijkstra)）中使用。

Pintos的信号量类型和操作在“threads/synch.h”中声明.

Type: struct semaphore
表示信号量.

Function: void sema_init (struct semaphore *sema, unsigned value)
使用给定的初始值将 sema 初始化为新的信号量.

Function: void sema_down (struct semaphore *sema)
在sema上执行“down”或“P”操作，等待其值变为正，然后将其减1.

Function: bool sema_try_down (struct semaphore *sema) 尝试在sema上执行“down”或“P”操作，而无需等待。 如果成功减小了sema，则返回true；如果已经为零，则返回false，因此如果不等待就无法减小。 在紧密循环中调用此函数会浪费CPU时间，因此请使用sema_down()或寻找其他方法。

Function: void sema_up (struct semaphore *sema)
在 sema 上执行“向上”或“ V”操作，增加其值。 如果有任何线程在 sema 上等待，则唤醒其中之一。

• 与大多数同步原语不同，可以在外部中断处理程序内部调用“ sema_up()”（请参阅[A.4.3外部中断处理]部分）。

信号量是在内部由禁用中断（请参阅A.3.1禁用中断)）以及线程阻塞和取消阻塞（“thread_block()”）建立的。 和thread_unblock()）。 每个信号量使用“lib/kernel/list.c”中的链接列表实现维护一个等待线程的列表。

A.3.3 Locks#

lock就像一个初始值为1的信号量（请参阅A.3.2信号量)一节）。 相当于“升”的锁称为“释放”，而“降”的操作称为“获取”。

与信号量相比，锁具有一个附加的限制：只有获得锁的线程（称为锁的“所有者”）才可以释放它。 如果此限制有问题，则表明应该使用信号量而不是锁，这是一个好兆头。

Pintos中的锁不是“递归的”，也就是说，当前持有锁的线程尝试获取该锁是错误的。

锁的类型和函数在“ threads / synch.h”中声明。.

Type: struct lock
表示锁.

Function: void lock_init (struct lock *lock)
将 lock 初始化为新锁。 该锁最初不属于任何线程.

Function: void lock_acquire (struct lock *lock)
为当前线程获取 lock ，首先等待任何当前所有者将其释放（如有必要）.

Function: bool lock_try_acquire (struct lock *lock)
: 尝试获取 lock ，供当前线程使用，而无需等待。 如果成功，则返回true；如果已拥有锁，则返回false。 在一个紧密的循环中调用此函数是一个坏主意，因为这会浪费CPU时间，因此请改用lock_acquire()。

Function: void lock_release (struct lock *lock)
释放当前线程必须拥有的 lock .

Function: bool lock_held_by_current_thread (const struct lock *lock)
如果正在运行的线程拥有 lock ，则返回true，否则返回false。 没有函数可以测试任意线程是否拥有锁，因为答案可能会在调用者对其执行操作之前更改。

A.3.4 Monitors#

管程是比信号量或锁更高级别的同步形式。监视器由同步数据，锁（称为“监视器锁”）和一个或多个“条件变量”组成。在访问受保护的数据之前，线程首先获取监视器锁定。然后，它被称为“在监视器中”。在监视程序中时，线程可以控制所有受保护的数据，可以自由检查或修改这些数据。对受保护数据的访问完成后，它将释放监视器锁定。

条件变量允许监视器中的代码等待条件变为真。每个条件变量都与一个抽象条件相关联，例如“某些数据已到达以进行处理”或“自用户上一次按键以来已超过10秒钟”。当监视器中的代码需要等待条件变为真时，它将在相关的条件变量上“等待”，这将释放锁定并等待该条件被发出信号。另一方面，如果它导致这些条件之一变为真，则它“发出信号”唤醒一个服务员的条件，或者“广播”一个唤醒所有服务员的条件。

管程的理论框架由C. A. R. Hoare（Hoare提出。稍后在有关Mesa操作系统的论文（Lampson）中详细说明了它们的实际用法。

条件变量类型和函数在“threads/synch.h”中声明.

Type: struct condition
表示条件变量。

Function: void cond_init (struct condition *cond)
将 cond 初始化为新的条件变量。

Function: void cond_wait (struct condition *cond, struct lock *lock)
以原子方式释放lock（管程锁定），并等待其他代码段发出cond信号。发出 cond 信号后，在返回之前重新获取lock。 在调用此函数之前，必须保持lock。
发送信号并从等待中唤醒不是原子操作。因此，通常cond_wait()的调用者必须在等待完成后重新检查条件，如有必要，请再次等待。有关示例，请参见下一部分。

Function: void cond_signal (struct condition *cond, struct lock *lock)
如果有任何线程正在等待cond（受管程锁lock保护），则此功能将唤醒其中一个。如果没有线程在等待，则返回而不执行任何操作。在调用此函数之前，必须保持lock。

Function: void cond_broadcast (struct condition *cond, struct lock *lock)
唤醒所有线程，如果有的话，等待cond（受管程锁lock保护）。 调用此函数之前必须保持lock.

A.3.4.1 Monitor Example#

管程的典型示例是处理一个缓冲区，一个或多个“生产者”线程在其中写入字符，而一个或多个“消费者”线程从中读取字符。 为了实现这一点，我们需要除管程锁之外的两个条件变量，我们将它们称为not_full 和not_empty：

  char buf[BUF_SIZE];     /* Buffer. */
  size_t n = 0;           /* 0 <= n <= BUF_SIZE: # of characters in buffer. */
  size_t head = 0;        /* buf index of next char to write ( mod BUF_SIZE). */ 
  size_t tail = 0;        /* buf index of next char to read (mod BUF_SIZE). */
  struct lock lock;       /* Monitor lock. */
  struct condition not_empty; /* Signaled when the buffer is not empty. */
  struct condition not_full; /* Signaled when the buffer is not full. */

...初始化锁和条件变量...

  void put (char ch) { 
    lock_acquire (&lock); 
    while (n == BUF_SIZE)            /* Can't add to buf as long as it's full. */
      cond_wait (&not_full, &lock);   
    buf[head++ % BUF_SIZE] = ch;     /* Add ch to buf. */ 
    n++;
    cond_signal (&not_empty, &lock); /* buf can't be empty anymore. */ 
    lock_release (&lock);
  } 

  char get (void) {
    char ch; 
    lock_acquire (&lock);
    while (n == 0)                   /* Can't read buf as long as it's empty. */
      cond_wait (&not_empty, &lock);                     
    ch = buf[tail++ % BUF_SIZE];     /* Get ch from buf. */ 
    n--;
    cond_signal (&not_full, &lock);  /* buf can't be full anymore. */
    lock_release (&lock);
  }                             |

请注意，为了使上述代码完全正确，“BUF_SIZE”必须平均分为“SIZE_MAX+1”。 否则，它将在第一次将head换为0时失败。实际上，BUF_SIZE通常是2的幂。

A.3.5 优化屏障#

“优化屏障”是一条特殊的语句，它防止编译器对跨屏障的内存状态做出假设。编译器不会重新设置跨屏障的变量的读取或写入顺序，也不会假定变量的值在跨屏障时不会改变，但从未使用地址的局部变量除外。在Pintos中，“threads/synch.h”将barrier()宏定义为优化屏障。

使用优化屏障的一个原因是，数据可能在编译器不知道的情况下异步更改，比如由另一个线程或中断处理程序修改。例如“devices/timer.c”中的“too_many_loops()”函数。该函数通过在循环中忙等待直到出现计时器滴答声而开始：

   /* Wait for a timer tick. */          
   int64_t start = ticks;   
   while (ticks == start) 
     barrier();              

在循环中没有优化屏障的情况下，编译器可能得出结论，循环将永远不会终止，因为“start”和“ticks”开始时是相等的，并且循环本身也永远不会改变它们。然后编译就会将函数“优化”为无限循环，这显然是我们不希望的。

优化屏障还可用于避免其他编译器优化。同样在“devices/timer.c”中的“busy_wait()”函数就是一个例子。它包含以下循环：

  while (loops-- > 0)         
    barrier();    

该循环的目的是通过将"loops"从其初始值递减为0来忙等待。如果没有屏障，编译器可能完全删除该循环，因为它不会产生有用的输出并且没有副作用。屏障迫使编译器假装循环体具有重要作用。

最后，使用优化屏障可以强制内存读取或写入的顺序。例如，假设我们添加了一个“功能”，无论何时发生计时器中断，控制台上都会打印全局变量“timer_put_char”中的字符，但前提是全局布尔变量“timer_do_put”为true。设置要打印的“x”的最佳方法是使用优化屏障，如下所示：

   timer_put_char = 'x';               
   barrier ();                
   timer_do_put = true;     

没有屏障，代码是有缺陷的，因为当编译器看不到保持操作顺序的理由时，编译器可能自由地对其进行重新排序。在这种情况下，编译器不知道赋值的顺序的重要性，因此允许其优化程序交换其顺序。无法确定是否会真正执行此操作，并且可能会通过不同的优化标志或使用不同版本的编译器来传递不同的行为。

另一种解决方案是在赋值语句周围禁止中断。这不会阻止重新排序，但是会阻止中断处理程序在赋值之间进行干预。它还具有禁用和重新启用中断的额外运行时成本：

    evel old_level = intr_disable ();                           
    timer_put_char = 'x'; 
    timer_do_put = true; 
    intr_set_level (old_level); 

第二种解决方案是将timer_put_char和timer_do_put的声明标记为“volatile”。此关键字告诉编译器变量是外部可观察的，并限制其进行优化的范围。但是，“volatile”的语义定义不明确，因此不是一个好的通用解决方案。基本的Pintos代码根本不使用“volatile”。

以下内容不是解决方案，因为锁既不会阻止中断，也不会阻止编译器对持有该锁的区域内的代码进行重新排序：

    lock_acquire (&timer_lock);     /* INCORRECT CODE */                      
    timer_put_char = 'x';       
    timer_do_put = true;        
    lock_release (&timer_lock);   

编译器将外部定义的任何功能（即在另一个源文件中）的调用视为优化屏障的有限形式。具体地说，编译器假定任何外部定义的函数都可以访问任何静态或动态分配的数据以及使用其地址的任何局部变量。这通常意味着可以省略明确的屏障。这是Pintos包含很少的显式屏障的原因之一。

在同一源文件中或在源文件包含的标头中定义的函数不能作为优化屏障。这甚至适用于函数定义之前的调用，因为编译器可能会在执行优化之前读取并解析整个源文件。

A.4 中断处理#

interrupt通知CPU一些事件。操作系统的许多工作都以一种或另一种方式与中断有关。为了我们的目的，我们将中断分为两大类：

-内部中断，即直接由CPU指令引起的中断。系统调用，试图进行无效的内存访问（页面错误）以及试图除以零的尝试都是导致内部中断的活动。由于内部中断是由CPU指令引起的，因此它们是“同步”或与CPU指令同步的。intr_disable()不禁止内部中断。

-外部中断，即来自CPU外部的中断。这些中断来自硬件设备，例如系统计时器，键盘，串行端口和磁盘。外部中断是“异步的”，这意味着它们的传递与指令执行不同步。外部中断的处理可以通过intr_disable()和相关函数来推迟（请参阅A.3.1 禁用中断）。

CPU对两种中断的处理方式大致相同，因此Pintos具有通用的基础结构来处理两种中断。以下部分描述了这种常见的基础结构。此后的各节给出了外部和内部中断的详细信息。

如果您尚未阅读IA32-v1中的第3章“基本执行环境”，则建议您现在就这样做。您可能还需要浏览IA32-v3a)中的第5章“中断和异常处理”。

A.4.1 中断基础架构#

发生中断时，CPU将其最基本的状态保存在堆栈中，并跳转到中断处理程序例程。80x86体系结构支持256个中断，编号为0到255，每个中断都有一个称为“中断描述符表”或IDT的数组中定义的独立处理程序。

在Pintos中，“threads/interrupt.c”中的“intr_init()”会设置IDT，以便每个入口都指向一个唯一的项。项的名称为“intrNN_stub()”，在“threads/intr-stubs.S”中，其中NN是十六进制的中断号。由于CPU没有提供其他任何方法来查找中断号，因此该入口点将中断号压入堆栈。然后，它跳转到intr_entry()，它将处理器尚未推送的所有寄存器推送给我们，然后调用intr_handler()，这将我们带回到“threads/interrupt.c”中的C语言。

intr_handler()的主要工作是调用为处理特定中断而注册的函数。（如果未注册任何功能，则它将某些信息转储到控制台和恐慌中。）它还对外部中断进行了一些额外的处理（请参阅A.4.3 外部中断处理）。

当intr_handler()返回时，“threads/intr-stubs.S”中的汇编代码将恢复先前保存的所有CPU寄存器，并指示CPU从中断中返回。

以下类型和功能是所有中断所共有的。

Type: void intr_handler_func (struct intr_frame *frame) ：这是必须声明中断处理程序函数的方式。 它的frame参数（请参见下文）允许它确定中断的原因和被中断的线程的状态。

Type: struct intr_frame ：中断处理程序的堆栈帧，由CPU，中断存根和“intr_entry()”保存。 其有趣的成员如下所述。

Member of struct intr_frame: uint32_t edi
Member of struct intr_frame: uint32_t esi
Member of struct intr_frame: uint32_t ebp
Member of struct intr_frame: uint32_t esp_dummy
Member of struct intr_frame: uint32_t ebx
Member of struct intr_frame: uint32_t edx
Member of struct intr_frame: uint32_t ecx
Member of struct intr_frame: uint32_t eax
Member of struct intr_frame: uint16_t es
Member of struct intr_frame: uint16_t ds
：在被中断的线程中注册值，由intr_entry()推动。 esp_dummy`值实际上并未使用（有关详细信息，请参考IA32-v2b)中对“ PUSHA”的描述）。

Member of struct intr_frame: uint32_t vec_no : 中断向量号，范围为0到255。

Member of struct intr_frame: uint32_t error_code= ：由于某些内部中断，CPU将“错误代码”压入堆栈。

Member of struct intr_frame: void (*eip) (void) ：被中断的线程执行的下一条指令的地址。

Member of struct intr_frame: void *esp : 中断线程的堆栈指针。

Function: const char *intr_name (uint8_t vec) : 返回编号为vec的中断的名称，如果该中断没有注册名称，则返回“unknown”。

A.4.2 内部中断处理#

内部中断直接由正在运行的内核线程或用户进程（从项目2开始）执行的CPU指令引起。因此，内部中断被称为在“过程上下文”中发生。

在内部中断的处理程序中，检查传递给中断处理程序的“struct intr_frame”，甚至进行修改都是有意义的。当中断返回时，struct intr_frame中的修改将变为对调用线程或进程状态的更改。例如，Pintos系统调用处理程序通过修改保存的EAX寄存器将一个值返回给用户程序（请参见3.5.2系统调用详细信息）。 `

对于内部中断处理程序可以做什么或不能做什么没有特别的限制。通常，它们应与其他代码一样在启用了中断的情况下运行，因此它们可以被其他内核线程抢占。因此，它们确实需要与共享数据和其他资源上的其他线程同步（请参阅A.3 同步一节）。

内部中断处理程序可以递归调用。例如，在尝试读取用户内存时，系统调用处理程序可能会导致页面错误。深度递归可能会溢出有限的内核堆栈（请参阅A.2.1 struct thread），但应该没有必要。

Function: void intr_register_int (uint8_t vec,int dpl, enum intr_level level, intr_handler_func *<var>handler, const char *name)

：当触发编号为 vec 的内部中断时，注册要调用的 handler 。 为调试目的将中断命名为 name 。

如果<var>level</var>为“INTR_ON”，则在执行中断处理程序期间将正常处理外部中断。指定“INTR_OFF”将导致CPU在调用中断处理程序时禁用外部中断。其效果与在处理程序中调用`intr_disable()`稍有不同，因为这留下了一个或多个CPU指令的窗口，该窗口中仍启用了外部中断。这对于页面错误处理程序很重要。有关详细信息，请参阅“`userprog/exception.c”中的注释。 “”

<var>dpl</var>确定如何调用中断。如果<var>dpl</var>为0，则该中断只能由内核线程调用。否则，<var>dpl</var>应该为3，这允许用户进程使用显式INT指令调用中断。 <var>dpl</var>的值不影响用户进程间接调用中断的能力，例如无效的内存引用将导致页面错误，而不考虑<var>dpl</var>。

A.4.3 外部中断处理#

外部中断是由CPU外部的事件引起的。它们是异步的，因此可以在未禁用中断的任何时间调用它们。我们说外部中断是在“中断上下文”中运行的。

在外部中断中，传递给处理程序的“ struct intr_frame”不是很有意义。它描述了被中断的线程或进程的状态，但是无法预测哪个线程或进程被中断。尽管很少有用，但有可能对其进行检查，但是对其进行修改是造成灾难的秘诀。

一次只能处理一个外部中断。内部或外部中断都不能嵌套在外部中断处理程序中。因此，外部中断的处理程序必须在禁用中断的情况下运行（请参见[A.3.1 禁用中断]。）

外部中断处理程序不得进入休眠或让步状态，从而避免调用“ lock_acquire()”，“thread_yield()”和许多其他函数。在中断上下文中休眠也会有效地使被中断的线程进入休眠状态，直到再次调度并返回中断处理程序为止。这对于不幸的线程将是不公平的，并且如果处理程序正在等待睡眠线程例如释放锁，则它将死锁。

外部中断处理程序有效地垄断了机器并延迟了所有其他活动。因此，外部中断处理程序应尽快完成。任何需要大量CPU时间的操作都应该在内核线程中运行，可能是中断使用同步原语触发的线程。

外部中断由CPU外部的一对设备控制，这些设备称为“可编程中断控制器”，“ PICs”。当intr_init()设置CPU的IDT时，它也会初始化PIC以进行中断处理。对于每个外部中断，在处理结束时还必须“确认” PIC。 intr_handler()负责通过调用pic_end_of_interrupt()可以正确通知PIC。

以下功能与外部中断有关.

Function: void intr_register_ext (uint8_t vec,intr_handler_func *handler, const char *name) : 触发编号为 vec 的外部中断时，注册要调用的 handler 。 为调试目的将中断命名为 name 。 处理程序将在禁用中断的情况下运行.

Function: bool intr_context (void) : 如果我们在中断上下文中运行，则返回true，否则返回false。 主要用于可能会休眠或不应从中断上下文中调用的函数，其形式为:

 ASSERT (!intr_context ());

Function: void intr_yield_on_return (void)

在中断上下文中调用时，导致在中断返回之前调用`thread_yield()。 当线程的时间片到期时，在计时器中断处理程序中使用，以导致计划新线程。

A.5 内存分配#

Pintos包含两个内存分配器，一个以页面为单位分配内存，另一个可以分配任何大小的块。

A.5.1 页分配器#

在“threads/palloc.h”中声明的页分配器以页面为单位分配内存。它最常用于一次分配一个页面的内存，但是它也可以一次分配多个连续的页面。

页分配器将其分配的内存分为两个池，称为内核池和用户池。默认情况下，每个池获得的系统内存超过1MB的一半，但是可以使用“-ul”内核命令行选项更改分区（请参阅Why PAL_USER？）。分配请求来自一个池或另一个池。如果一个池变为空，则另一个池可能仍具有可用页。用户池应用于为用户进程分配内存，并为所有其他分配分配内核池。从项目3开始，这才变得很重要。在那之前，所有分配都应从内核池进行。

通过位图跟踪每个池的使用情况，该位图在池中每页一位。分配n页的请求会扫描位图，以查找设置为false的n个连续位，表明这些页是空闲的，然后将这些位设置为true以将其标记为已使用。这是一种“最适合”的分配策略（请参阅Wilson）。

页面分配器容易碎片化。也就是说，即使n个或更多页面是空闲的，也可能无法分配n个连续页面，因为可用页面由使用过的页面分隔开。实际上，在病理情况下，即使池的一半页面是空闲的，也可能无法分配2个连续页面。单页请求不会因碎片而失败，因此对多个连续页面的请求应尽可能地受到限制。

页面可能不会从中断上下文中分配，但是它们可能被释放。

释放页面后，作为调试辅助，页面的所有字节都被清除为0xcc（请参阅E.8 提示部分）。

页分配器的类型和功能如下所述。

Function: void *palloc_get_page (enum palloc_flags flags)

Function: void *palloc_get_multiple (enum palloc_flags flags, size_t page_cnt)

• 分别获取并返回一页或page_cnt连续页。 如果无法分配页面，则返回空指针。

  flags 参数可以是以下标志的任意组合：
  Page Allocator Flag: PAL_ASSERT ：如果无法分配页面，请使内核崩溃。 这仅在内核初始化期间适用。 绝对不允许用户进程恐慌内核。

  Page Allocator Flag: PAL_ZERO : 将分配的页面中的所有字节清零，然后返回它们。 如果未设置，则新分配的页面的内容是不可预测的。

  Page Allocator Flag: PAL_USER : 从用户池中获取页面。 如果未设置，则从内核池分配页面.

Function: void palloc_free_page (void *page)

Function: void palloc_free_multiple (void *pages, size_t page_cnt)
+ 从pages开始分别释放一页或page_cnt连续页面。 所有页面都必须使用palloc_get_page()或palloc_get_multiple()获得。

A.5.2 块分配器#

在“threads/malloc.h”中声明的块分配器可以分配任何大小的块。它位于上一节中介绍的页面分配器的顶部。块分配器返回的块是从内核池中获得的。

块分配器使用两种不同的策略来分配内存。第一种策略适用于1 kB或更小的块（页面大小的四分之一）。这些分配将四舍五入到最接近的2或16字节（以较大者为准）的幂。然后，将它们分组到仅用于该大小分配的页面中。

第二种策略适用于大于1 kB的块。这些分配（加上少量开销）将四舍五入到最接近的页面大小，然后块分配器向页面分配器请求该数目的连续页面。

无论哪种情况，都浪费了分配请求大小与实际块大小之间的差异。真正的操作系统会仔细调整其分配器，以最大程度地减少这种浪费，但这在像Pintos这样的教学系统中并不重要。

只要可以从页面分配器获取页面，小分配总是成功的。大多数小型分配根本不需要页面分配器中的新页面，因为它们对已经分配的页面的一部分很满意。但是，大型分配始终需要调用页面分配器，而任何需要如上一节中所述，一个以上的连续页面可能由于碎片而失败。因此，您应该减少代码中大型分配的数量，尤其是每个分配大于4kB的分配。

释放一个块后，作为调试辅助，其所有字节都被清除为0xcc（请参见E.8 技巧部分）。

不能从中断上下文中调用块分配器。

块分配器功能描述如下。 它们的接口与具有相同名称的标准C库函数相同。

Function: void *malloc (size_t size)
从内核池获取并返回一个新的块，该块的长度至少为 size 个字节。 如果size为零或内存不可用，则返回空指针。

Function: void *calloc (size_t a, size_t b)
从内核池获得a返回一个至少长为a*b字节的新块。 块的内容将清零。 如果a或b为零或没有足够的可用内存，则返回空指针。

Function: void *realloc (void *block, size_t <var>new_size)

• 尝试将block的大小调整为new_size个字节，可能会在此过程中将其移动。如果成功，则返回新块，在这种情况下，必须不再访问旧块。失败时，返回空指针，旧块保持有效。

• block为null的调用等效于malloc()。 new_size为零的调用等效于free()。

Function: void free (void *block) 释放block，必须先前已由malloc()，calloc()或realloc())返回（并且尚未释放）。

A.6 虚拟地址#

32位虚拟地址可以分为20位页号和12位页偏移量（或仅偏移量），如下所示：

                   31               12 11        0                           
                  +-------------------+-----------+               
                  |    Page Number    |   Offset  |               
                  +-------------------+-----------+               
                           Virtual Address                        

头文件“threads/vaddr.h”定义了用于处理虚拟地址的以下函数和宏：

Macro: PGSHIFT Macro: PGBITS : 虚拟地址偏移量部分的位索引（0）和位数（12）.

Macro: PGMASK : 一个位掩码，页面偏移量中的位设置为1，其余设置为0（0xfff）.

Macro: PGSIZE : 页面大小以字节为单位（4,096）.

Function: unsigned pg_ofs (const void *va) : 提取并返回虚拟地址 va 中的页面偏移量.

Function: uintptr_t pg_no (const void *va) : 提取并返回虚拟地址 va 中的页码.

Function: void *pg_round_down (const void *va) : 返回 va 指向的虚拟页面的开始，即 va ，页面偏移设置为0。

Function: void *pg_round_up (const void *va) : 返回 va ，四舍五入到最接近的页面边界.

Pintos中的虚拟内存分为两个区域：用户虚拟内存和内核虚拟内存（请参阅[3.1.4 虚拟内存布局]部分）。 它们之间的边界是“ PHYS_BASE”：

Macro: PHYS_BASE

: 内核虚拟内存的基地址。 默认为“0xc0000000”（3 GB），但可以将其从“ 0x80000000”更改为“ 0xf0000000”的“ 0x10000000”的任意倍数。

用户虚拟内存的范围从虚拟地址0到“PHYS_BASE”。 内核虚拟内存占据了其余的虚拟地址空间，从“ PHYS_BASE”到最大4GB。

Function: bool is_user_vaddr (const void *va)

Function: bool is_kernel_vaddr (const void *va</var>) 如果 va 分别是用户或内核虚拟地址，则返回true，否则返回false。

80x86没有提供任何直接访问给定物理地址的内存的方法。此功能在操作系统内核中通常是必需的，因此Pintos通过将内核虚拟内存一对一映射到物理内存来解决此问题。 也就是说，虚拟地址“ PHYS_BASE”访问物理地址0，虚拟地址“ PHYS_BASE” +“ 0x1234”访问物理地址“ 0x1234”，依此类推，直到机器的物理内存大小为止。 因此，在物理地址上添加“ PHYS_BASE”可获得访问该地址的内核虚拟地址。 相反，从内核虚拟地址中减去“ PHYS_BASE”可获得相应的物理地址。头文件“threads/vaddr.h”提供了一对函数来进行以下转换：

Function: void *ptov (uintptr_t pa) 返回与物理地址 pa 对应的内核虚拟地址，该地址应介于0和物理内存的字节数之间。

Function: uintptr_t vtop (void *va) 返回与 va 相对应的物理地址，该地址必须是内核虚拟地址。

A.7 页表#

“pagedir.c”中的代码是80x86硬件页面表的抽象接口，在英特尔处理器文档中也称为“页面目录”。页表接口使用uint32_t *表示页表，因为这便于访问其内部结构。

以下各节描述了页表界面和内部结构。

A.7.1 创建,销毁和激活#

这些函数创建、销毁和激活页表。基本的Pintos代码已经在必要时调用了这些函数，因此不必自己调用它们。

Function: uint32_t *pagedir_create (void)

创建并返回一个新的页表。新页面表包含Pintos的常规内核虚拟页面映射，但不包含用户虚拟映射。  
如果无法获得内存，则返回空指针。

Function: void pagedir_destroy (uint32_t *pd)
释放pd所拥有的所有资源，包括页表本身及其映射的框架。

Function:void pagedir_activate (uint32_t *pd)
激活pd。 活动页表是CPU用于翻译内存引用的表.

A.7.2 检查和更新#

这些功能检查或更新从页面到页面表封装的帧的映射。它们在活动和非活动页表（即正在运行和挂起的进程的页表）上都起作用，并在必要时刷新TLB。
Function: bool pagedir_set_page (uint32_t *pd,void *upage, void *kpage, bool writable)

• 向pd添加从用户页面upage到由内核虚拟地址kpage标识的帧的映射。如果writable为true，则页面被映射为可读写。否则，它被映射为只读。

  用户页面upage必须尚未映射到pd中。

  内核页面kpage应该是使用palloc_get_page（PAL_USER）从用户池中获得的内核虚拟地址（请参阅为什么使用PAL_USER？）。

  如果成功，则返回true，失败则返回false。如果无法获得页表所需的额外内存，则会发生故障。

Function: void *pagedir_get_page (uint32_t *pd, const void *uaddr)

• 在pd中查找映射到uaddr的帧。如果已映射uaddr,则返回该帧的内核虚拟地址，否则返回空指针。

Function: void pagedir_clear_page (uint32_t *pd, void *page)

• 在pd中标记page“不存在”。以后对该页面的访问将出错。

  页面表中page的其他位被保留，从而允许检查访问位和脏位（请参阅下一节）。

  如果未映射page，则此函数无效。

A.7.3 访问位和脏位#

80x86硬件通过每个页面的页面表项（PTE）中的一对位，为实现页面替换算法提供了一些帮助。在对页面进行任何读取或写入时，CPU会将页面PTE中的 accessed位设置为1，而在写入时，CPU会将dirty位设置为1。CPU从不将这些位重置为0，但是操作系统可能会这样做。

正确解释这些位需要了解别名，也就是说，两个（或更多）页面引用同一帧。当访问别名帧时，仅在一个页表条目（用于访问的页的条目）中更新已访问位和脏位。其他别名的访问位和脏位不会更新。

有关在实现页面替换算法中应用这些位的信息，请参见4.1.5.1 访问位和脏位。

Function: bool pagedir_is_dirty (uint32_t *pd,const void *page)
Function: bool pagedir_is_accessed (uint32_t *pd, const void *page)
如果页面目录pd包含标记为“脏”（或已访问）的page的页面表条目，则返回true。否则，返回false。

Function: void pagedir_set_dirty (uint32_t *pd, const void *page, bool value)
Function: void pagedir_set_accessed (uint32_t *pd, const void *page, bool value)
如果页面目录pd具有用于page的页面表条目，则其脏（或访问）位设置为value。

A.7.4 页表详细信息#

Pintos提供的功能足以实施项目。 但是，您可能仍然觉得了解硬件页表格式值得，因此我们将在本节中进行一些详细介绍。

A.7.4.1 Structure#

顶层分页数据结构是称为“页面目录”（PD）的页面，该页面排列为1,024个32位页面目录条目（PDE）的数组，每个条目代表4MB的虚拟内存。每个PDE都可以指向另一个页面的物理地址，该页面称为“页面表”（PT），以类似方式排列为1,024个32位页面表项（PTE）的数组，每个表项将单个4 kB虚拟页面转换为物理页面。

虚拟地址到物理地址的转换遵循下图所示的三步过程：（6）{ }

1.虚拟地址的最高有效10位（位22 ... 31）表示页面目录索引。如果PDE标记为“存在”，则从由此获得的PDE中读取页表的物理地址。如果PDE标记为“不存在”，则发生页面错误。

2.虚拟地址的后10位（位12 ... 21）表示页表索引。如果PTE被标记为“存在”，则从如此获得的PTE读取数据页的物理地址。如果PTE被标记为“不存在”，则发生页面错误。

3.将虚拟地址的最低有效12位（位0 ... 11）添加到数据页的物理基地址中，生成最终的物理地址。

 31                  22 21                  12 11                   0
+----------------------+----------------------+----------------------+
| Page Directory Index |   Page Table Index   |    Page Offset       |
+----------------------+----------------------+----------------------+
             |                    |                     |
     _______/             _______/                _____/
    /                    /                       /
   /    Page Directory  /      Page Table       /    Data Page
  /     .____________. /     .____________.    /   .____________.
  |1,023|____________| |1,023|____________|    |   |____________|
  |1,022|____________| |1,022|____________|    |   |____________|
  |1,021|____________| |1,021|____________|    \__\|____________|
  |1,020|____________| |1,020|____________|       /|____________|
  |     |            | |     |            |        |            |
  |     |            | \____\|            |_       |            |
  |     |      .     |      /|      .     | \      |      .     |
  \____\|      .     |_      |      .     |  |     |      .     |
       /|      .     | \     |      .     |  |     |      .     |
        |      .     |  |    |      .     |  |     |      .     |
        |            |  |    |            |  |     |            |
        |____________|  |    |____________|  |     |____________|
       4|____________|  |   4|____________|  |     |____________|
       3|____________|  |   3|____________|  |     |____________|
       2|____________|  |   2|____________|  |     |____________|
       1|____________|  |   1|____________|  |     |____________|
       0|____________|  \__\0|____________|  \____\|____________|
                           /                      /

Pintos提供了一些宏和函数，这些宏和函数对于处理原始页表很有用:

Macro: PTSHIFT
Macro: PTBITS
页表索引中的起始位索引（12）和位数（10）。
Macro: PTMASK
一个位掩码，其中页表索引中的位设置为1，其余设置为0（0x3ff000）.
Macro: PTSPAN
单个页面表页面覆盖的虚拟地址空间的字节数（4,194,304字节，或4MB）.
Macro: PDSHIFT
Macro: PDBITS
页面目录索引中的起始位索引（22）和位数（10）.
Macro: PDMASK
位掩码，其页面目录索引中的位设置为1，其他位设置为0（0xffc00000）.
Function: uintptr_t pd_no (const void *va)
Function: uintptr_t pt_no (const void *va)
分别返回虚拟地址va的页面目录索引或页面表索引。这些功能在“threads/pte.h”中定义。 Function: unsigned pg_ofs (const void *va)
返回虚拟地址va的页面偏移量。该功能在“threads/vaddr.h”中定义.

A.7.4.2 Page Table Entry Format#

除非您希望将页面表合并到补充页面表中，否则您不需要了解PTE格式即可进行Pintos项目（请参阅[4.1.4 管理补充页表]）。

页表条目的实际格式总结如下。 有关完整的信息，请参见IA32-v3a中的第3.7节“使用32位物理寻址的页面转换”。

 31                                   12 11 9      6 5     2 1 0
+---------------------------------------+----+----+-+-+---+-+-+-+
|           Physical Address            | AVL|    |D|A|   |U|W|P|
+---------------------------------------+----+----+-+-+---+-+-+-+

有关每个位的更多信息，请参见下文。 名称是“threads/pte.h”宏，它们代表位的值：

Macro: PTE_P
：位0，“存在”位。当该位为1时，其他位的解释如下。当该位为0时，任何访问该页面的尝试都会出现页面错误。 然后，其余位将不被CPU使用，并且OS可以出于任何目的使用它们。 Macro: PTE_W
：位1，“读/写”位。 为1时，页面可写。 为0时，写尝试将发生页面错误。
Macro: PTE_U
：位2，“用户/内核”位。 为1时，用户进程可以访问该页面。 当它为0时，只有内核可以访问该页面（用户访问将出现页面错误）。 Pintos清除了PTE中内核虚拟内存的该位，以防止用户进程访问它们。
Macro: PTE_A
：位5，“已访问”位。 参见A.7.3访问和脏位.
Macro: PTE_D
：位6，即“脏”位。 参见A.7.3访问和脏位.
Macro: PTE_AVL
：位9...11，可用于操作系统。所提供的Pintos不使用它们，而是将它们设置为0。
Macro: PTE_ADDR
：位12 ... 31，即帧物理地址的高20位。 帧地址的低12位始终为0.

在Pintos上下文中，其他位保留或不感兴趣，应将其设置为0。

头文件“threads/pte.h”定义了用于处理页表条目的三个功能：
Function: uint32_t pte_create_kernel (uint32_t *page, bool writable)
：返回指向 page 的页面表条目，该条目应该是内核虚拟地址。 PTE的当前位将被设置。 它将标记为仅内核访问。 如果 writable 为true，则PTE也将标记为读/写； 否则，它将是只读的。

Function: uint32_t pte_create_user (uint32_t *page, bool writable)
：返回指向 page 的页表项，该页表项应该是用户池中框架的内核虚拟地址（请参阅[Why PAL_USER？]（htt =））。 PTE的当前位将被设置并标记为允许用户模式访问。 如果 writable 为true，则PTE也将标记为读/写； 否则，它将是只读的。

Function: void *pte_get_page (uint32_t pte)
：返回 pte 指向的帧的内核虚拟地址。 pte 可以存在或不存在； 如果不存在，则仅当PTE中的地址位实际代表物理地址时，返回的指针才有意义。

A.7.4.3 Page Directory Entry Format#

页目录条目具有与PTE相同的格式，除了物理地址指向页表页而不是框架。 标题“threads/pte.h”定义了两个用于处理页面目录条目的函数：

Function: uint32_t pde_create (uint32_t *pt)
：返回指向 page 的页面目录，该目录应该是页面表页面的内核虚拟地址。 PDE的当前位将被置位，将其标记为允许用户模式访问，并将其标记为读/写。

Function: uint32_t *pde_get_pt (uint32_t pde)
：返回必须标记为存在的 pde 指向的页表页面的内核虚拟地址。

A.8 哈希表#

Pintos在“lib/kernel/hash.c”中提供了哈希表数据结构。要使用它，您需要包含其头文件lib/kernel/hash.h, 即使用#include 。Pintos附带的任何代码都不会使用哈希表，这意味着您可以自由使用它，可以出于自己的目的修改其实现，也可以根据需要忽略它。

虚拟内存项目的大多数实现都使用哈希表将页面转换为页框。您可能还会发现哈希表的其他用途。

A.8.1 数据类型#

哈希表由struct hash表示.

Type: struct hash

表示整个哈希表。struct hash的实际成员是“不透明的”。也就是说，使用哈希表的代码不应该直接访问struct hash成员，也不需要访问。而应该使用哈希表函数和宏。

哈希表对类型为struct hash_elem的元素进行操作.

Type: struct hash_elem

在要包含在哈希表中的结构中嵌入一个“struct hash_elem”成员。像struct hash一样，“struct hash_elem”也是不透明的。操作哈希表元素的所有函数实际上都使用并返回指向struct hash_elem的指针，而不是指向哈希表的实际元素类型的指针。

您通常需要获取某个给定哈希表的真实元素的struct hash_elem结构，反之亦然。给定哈希表的真实元素，您可以使用“＆”运算符获取指向其struct hash_elem结构的指针。使用hash_entry()宏来执行反向操作。

Macro: type *hash_entry (struct hash_elem *elem, type, member)

返回指向嵌入elem的结构的指针，即struct hash_elem的指针。您必须提供type，即elem所在结构的名称，以及member，即elem指向的type中成员的名称。

比如，假设“h”是一个“struct hash_elem *”变量，它指向名为“h_elem”的“struct thread”成员（类型为“struct hash_elem”）。那么，hash_entry(h，struct thread，h_elem)返回h所指向的struct thread的地址。

有关示例，请参见A.8.5 哈希表示例。

每个哈希表元素必须包含一个键，即标识和区分元素的数据，该数据在哈希表中的元素之间必须是唯一的。（元素还可以包含不需要唯一的非关键数据。）当元素在哈希表中时，不得更改其关键数据。相反，如果需要，请从哈希表中删除该元素，修改其键，然后重新插入该元素。

对于每个哈希表，您必须编写两个对键起作用的函数：哈希函数和比较函数。这些函数必须与以下原型匹配：

Type: unsigned hash_hash_func (const struct hash_elem *element, void *aux)

返回element数据的哈希，结果是“unsigned int”范围内任ｕ意值。元素的哈希应该是元素键的伪随机函数。它不得依赖于元素中的非键数据或键以外的任何非常量数据。 Pintos提供以下功能，作为哈希函数的基础。

-<u>Function:</u> unsigned **hash\_bytes** (const void \*<var>buf</var>, size\_t \*<var>size</var>) 
    返回从<var>buf</var>开始的<var>size</var>个字节的哈希。该实现是针对32位字的[Fowler-Noll-Vo hash](http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash)的通用实现。

-<u>Function:</u> unsigned **hash\_string** (const char \*<var>s</var>) 
    返回以空值结尾的字符串<var>s</var>的哈希。

-<u>Function:</u> unsigned **hash\_int** (int <var>i</var>) 
    返回整数<var>i</var>的哈希。

如果键是适当类型的单个数据，则明智的做法是让您的哈希函数直接返回这些函数之一的输出。对于多条数据，您可能希望使用“\^”(异或)运算符组合多个调用的输出。最后，您可能会完全忽略这些函数，并从头开始编写自己的哈希函数，但请记住，您的目标是构建一个系统内核，而不是设计哈希函数。

有关aux的说明，请参见[A.8.6 辅助数据](#a86-辅助数据)部分。

Type: bool hash_less_func (const struct hash_elem *a, const struct hash_elem *b, void *aux)

比较存储在元素a和b中的键。如果a小于b，则返回true；如果a大于或等于b，则返回false。

如果两个元素比较相等，则它们的哈希必须为相等的值。

有关aux的说明，请参见[A.8.6 辅助数据](#a86-辅助数据)部分。

有关哈希和比较函数的示例，请参见A.8.5 哈希表示例。

一些函数接受第三个，指向以下函数的函数指针参数:

Type: void hash_action_func (struct hash_elem *element, void *aux)

在*element*上执行调用者选择的某种操作。

有关*aux*的说明，请参见[A.8.6 辅助数据](#a86-辅助数据)部分。

A.8.2 基础函数#

这些函数创建，销毁和检查哈希表。

Function: bool hash_init (struct hash *hash, hash_hash_func *hash_func, hash_less_func *less_func, void *aux)

将hash初始化为哈希表，其中hash_func作为哈希函数，less_func作为比较函数，而aux作为辅助函数数据。如果成功，则返回true，失败则返回false。hash_init()调用malloc()，如果无法分配内存则失败。

有关<var>aux</var>的说明，请参阅[A.8.6 辅助数据](#a86-辅助数据)部分，通常为null指针。

Function: void hash_clear (struct hash *hash, hash_action_func *action)

从hash中删除所有元素，这些元素必须先前已使用`hash_init()初始化。

如果<var>action</var>不为null，则为哈希表中的每个元素调用一次，这为调用者提供了释放该元素使用的任何内存或其他资源的机会。例如，如果哈希表元素是使用“malloc()”动态分配的，则<var>action</var>可以“free()”该元素。 这是安全的，因为`hash_clear()`在调用<var> action </var>后不会访问给定哈希元素中的内存。 但是，<var> action </var>不得调用任何可能会修改哈希表的函数，例如“ hash_insert()或hash_delete()”。

Function: void hash_destroy (struct hash *hash= , hash_action_func *action)

如果 action 为非null，则对散列中的每个元素都调用它，其语义与对hash_clear()的调用相同。 然后，释放 hash 保留的内存。 之后，必须在没有对hash_init()的中间调用的情况下，将<var> hash </var>传递给任何哈希表函数。

Function: size_t hash_size (struct hash *hash) ：返回当前存储在 hash 中的元素数

Function: bool hash_empty (struct hash *hash) ：返回当前存储在 hash 中的元素数

A.8.3 查找函数#

这些函数中的每一个都在哈希表中查找一个元素，该元素与提供的元素进行比较。 基于搜索的成功，他们将执行一些操作，例如将新元素插入哈希表，或仅返回搜索结果。

Function: struct hash_elem *hash_insert (struct hash *hash, struct hash_elem *element) 在 hash 中搜索等于 element 的元素。 如果未找到，则将 element 插入 hash 并返回空指针。 如果表已经包含等于 element 的元素，则返回该表而无需修改 hash 。

Function: struct hash_elem *hash_replace (struct hash *hash, struct hash_elem *element)

将<var>element</var>插入<var>hash</var>中。<var>hash</var>中已经存在的等于<var>element</var>的所有元素都将被删除。返回删除的元素，如果<var>hash</var>不包含等于<var>element</var>的元素，则返回null指针。

调用方负责酌情取消分配与返回的元素关联的任何资源。例如，如果哈希表元素是使用malloc()动态分配的，那么在不再需要该元素之后，调用者必须将其释放为free()。

传递给以下函数的元素仅用于哈希和比较目的。 实际上，它永远不会插入到哈希表中。 因此，仅需要初始化元素中的关键数据，而不会使用元素中的其他数据。 通常将元素类型的实例声明为局部变量，初始化键数据，然后将其“ struct hash_elem”的地址传递给hash_find()或“ hash_delete()”通常是有意义的。 有关示例，请参见[A.8.5 哈希表示例]。 （不应将大型结构分配为局部变量。有关更多信息，请参见[A.2.1 struct thread]。）

Function: struct hash_elem *hash_find (struct hash *hash, struct hash_elem *element) ：在hash中搜索等于element的元素。 返回找到的元素（如果有），否则返回空指针。

Function: struct hash_elem *hash_delete (struct hash *hash, struct hash_elem *element)

：在 hash 中搜索等于 element 的元素。 如果找到一个，则将其从 hash 中删除并返回。 否则，将返回空指针，并且 hash 不变。

调用方负责酌情取消分配与返回的元素关联的任何资源。 例如，如果哈希表元素是使用malloc()动态分配的，那么在不再需要该元素之后，调用者必须将其释放为free()。

A.8.4 迭代函数#

这些函数允许遍历哈希表中的元素。提供了两个接口。第一个要求编写并提供一个hash_action_func来对每个元素起作用（请参见[A.8.1 数据类型]部分）。

Function: void hash_apply (struct hash *hash, hash_action_func *action) 对hash中的每个元素以任意顺序调用一次action。 action不得调用任何可能会修改哈希表的函数，例如“hash_insert()”或“hash_delete()”。 action不得修改元素中的key数据，尽管它可以修改任何其他数据。

第二个接口基于“迭代器”数据类型。 习惯上，迭代器的用法如下:

  struct hash_iterator i; 

    hash_first (&i, h); 
    while (hash_next (&i))
      { 
        struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
        ...do something with f...
      } 

Type: struct hash_iterator

：表示哈希表中的位置。 调用任何可能会修改哈希表的函数，例如“ hash_insert()”或“ hash_delete()”，会使该哈希表中的所有迭代器无效。

 像`struct hash`和`struct hash_elem`一样，`struct hash_elem`是不透明的。

Function: void hash_first (struct hash_iterator *iterator, struct hash *hash) ：将 iterator 初始化为 hash 中的第一个元素之前。

Function: struct hash_elem *hash_next (struct hash_iterator *iterator) ：将 iterator 推进到 hash 中的下一个元素，并返回该元素。 如果没有剩余元素，则返回空指针。 在hash_next()为 iterator 返回null之后，再次调用它会产生未定义的行为。

Function: struct hash_elem *hash_cur (struct hash_iterator *iterator) ：返回`hash_next()为迭代器最近返回的值。 在迭代器上调用hash_first()之后但首次调用hash_next()之后，产生未定义的行为。

A.8.5 哈希表示例#

假设您有一个要放入哈希表的结构，称为“struct page”。 首先，定义“struct page”以包含“struct hash_elem”成员：

 struct page
   {
     struct hash_elem hash_elem; /* Hash table element. */
     void *addr;                /* Virtual address. */
     /* ...other members... */ 
   };

我们使用addr作为键编写哈希函数和比较函数。可以根据指针的字节对指针进行哈希处理，并且“<”运算符可以很好地比较指针：

/* Returns a hash value for page p. */
unsigned
page_hash (const struct hash_elem *p_, void *aux UNUSED)
{
  const struct page *p = hash_entry (p_, struct page, hash_elem);
  return hash_bytes (&p->addr, sizeof p->addr);
}

/* Returns true if page a precedes page b. */
bool
page_less (const struct hash_elem *a_, const struct hash_elem *b_,
           void *aux UNUSED)
{
  const struct page *a = hash_entry (a_, struct page, hash_elem);
  const struct page *b = hash_entry (b_, struct page, hash_elem);

  return a->addr < b->addr;
}

（在这些函数的原型中使用UNUSED会禁止显示aux未使用的警告。有关信息，请参见E.3函数和参数属性 有关“UNUSED”的信息，请参见A.8.6辅助数据，以获取aux的解释。）

然后，我们可以创建一个哈希表，如下所示：

struct hash pages;

hash_init (&pages, page_hash, page_less, NULL);

现在我们可以操作我们创建的哈希表。 如果p是指向struct page的指针，我们可以将其插入到哈希表中: hash_insert (&pages, &p->hash_elem);

如果pages有可能已经包含具有相同addr的页面，那么我们应该检查hash_insert()的返回值。

要在哈希表中搜索元素，请使用“ hash_find()”。 这需要一些设置，因为hash_find()需要一个要比较的元素。 假设pages是在文件范围内定义的，这是一个基于虚拟地址查找并返回页面的函数：

/* Returns the page containing the given virtual address,
   or a null pointer if no such page exists. */
struct page *
page_lookup (const void *address)
{
  struct page p;
  struct hash_elem *e;

  p.addr = address;
  e = hash_find (&pages, &p.hash_elem);
  return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
}

假设struct page是一个局部变量，假设它相当小。 大型结构不应分配为局部变量。 有关更多信息，请参见A.2.1 sturct thread信息。

类似的功能可以使用“ hash_delete()”按地址删除页面。

A.8.6 辅助数据#

在上面的示例这样的简单情况下，不需要aux参数。 在这种情况下，只需将aux的空指针传递给hash_init()，而忽略传递给哈希函数和比较函数的值。 （如果您不使用aux参数，则会收到编译器警告，但您可以使用UNUSED宏将其关闭，如示例中所示，也可以忽略它 ）

当哈希表中数据的某些属性既是常量又是哈希或比较所需的，但不存储在数据项本身中时，aux很有用。 例如，如果哈希表中的项目是固定长度的字符串，但是项目本身未指示该固定长度是什么，则可以将长度作为aux参数传递。

A.8.7 同步#

哈希表不执行任何内部同步。调用者有责任将调用与哈希表函数同步。通常，可以检查同时执行但不修改哈希表的许多函数，例如“ hash_find()”或“ hash_next()”。但是，这些函数不能安全地与可能修改给定哈希表的任何函数（例如，“ hash_insert()”或“ hash_delete()”）同时执行，也不能超过一个可以修改给定哈希表的函数安全地执行。

同步对哈希表元素中数据的访问也是调用者的责任。与任何其他数据结构一样，如何同步对此数据的访问取决于其设计和组织方式。