OSTEP阅读笔记-Virtuallization（一）

进程虚拟化

Chapter 4 进程

Q：如何提供有许多CPU的假象？

OS通过Visualizing CPU来提供这种假象。通过让一个进程只运行一个时间片，然后切换到其它进程，这样就提供了存在多个虚拟CPU的假象。

• 时分共享：典型的就是时间片划分，将一小段时间分配给不同的进程。
• 空分共享：典型的就是磁盘空间，将空间分配给不同的文件。

Qustions：

• 如何实现context switch
• OS如何执行scheduling policy

4.1 抽象：进程

OS为正在运行的程序提供的抽象，就是所谓的进程。

进程的machine state：

• 进程可访问的内存（address space）：指令和数据存储在address space。
• 寄存器（register）

4.2 进程API

• create
• destroy
• wait
• miscellaneous control
• status

4.3 进程创建的细节

Q: 程序如何转换为进程？换而言之，OS如何启动并运行一个程序？

1. OS将代码和静态数据load到内存中，加载到进程的address space。如图4.1所示：

2. 加载后，OS在运行前需要执行初始化操作。
   • 为程序的运行时栈（run-time stack）分配一些内存。C程序使用栈存放局部变量，函数参数和返回地址。
   • 为堆（heap）分配一些内存，C程序中，堆用于显式请求的动态分配数据（malloc & free）
   • I/O相关的任务。UNIX中每个进程都会有三个打开的文件描述符（file descriptor）

4.4 进程状态

• 运行
• 就绪
• 阻塞

进程的状态转化图如图4.2所示：

4.5 数据结构

对于停止的进程，上下文将保存寄存器的内容，通过上下文切换可以使OS恢复运行该进程。

下图中的context就是上下文的数据结构，proc

Chapter 5 进程API

本章讨论在UNIX系统中的进程创建。

Q：如何创建并控制进程？

fork() 系统调用

fork()用于创建新进程，fork的子进程从fork处开始执行。示例代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc, char const *argv[]) {
    printf("hello world (pid: %d)\n", (int)getpid());
    int rc = fork();
    if (rc < 0) {
        // fork failed
        fprintf(stderr, "fork failed\n");
        exit(1);
    } else if (rc == 0) {
        printf("hello, I'am child (pid: %d)\n", (int)getpid());
    } else {
        printf("hello, I am parent of %d (pid: %d)\n", rc, (int)getpid());
    }
    printf("yes !!\n");
    return 0;
}

运行结果如下：

hello world (pid: 13360)
hello, I am parent of 13361 (pid: 13360)
yes !!
hello, I'am child (pid: 13361)
yes !!

wait() 系统调用

父进程等待子进程执行完毕。示例代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc, char const *argv[]) {
    printf("hello world (pid: %d)\n", (int)getpid());
    int rc = fork();
    if (rc < 0) {
        // fork failed
        fprintf(stderr, "fork failed\n");
        exit(1);
    } else if (rc == 0) {
        printf("hello, I'am child (pid: %d)\n", (int)getpid());
    } else {
        int wc = wait(NULL);
        printf("hello, I am parent of %d (wc: %d)(pid: %d)\n", rc, wc,
               (int)getpid());
    }
    printf("yes !!\n");
    return 0;
}

运行结果如下：

hello world (pid: 13787)
hello, I'am child (pid: 13788)
yes !!
hello, I am parent of 13788 (wc: 13788)(pid: 13787)
yes !!

exec() 系统调用

子进程调用execvp()来运行字符计数程序wc。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>

int main(int argc, char const *argv[]) {
    printf("hello world (pid: %d)\n", (int)getpid());
    int rc = fork();
    if (rc < 0) {
        // fork failed
        fprintf(stderr, "fork failed\n");
        exit(1);
    } else if (rc == 0) {
        printf("hello, I'am child (pid: %d)\n", (int)getpid());
        char *myargs[3];
        myargs[0] = strdup("wc");
        myargs[1] = strdup("p3.c");
        myargs[2] = NULL;
        execvp(myargs[0], myargs);
        printf("this shouldn't print out\n");
    } else {
        int wc = wait(NULL);
        printf("hello, I am parent of %d (wc: %d)(pid: %d)\n", rc, wc,
               (int)getpid());
    }
    return 0;
}

运行结果如下：

hello world (pid: 14384)
hello, I'am child (pid: 14385)
 36 115 906 p3.c
hello, I am parent of 14385 (wc: 14385)(pid: 14384)

Chapter 6 受限直接执行

Q：如何高效、可控地虚拟化CPU？

6.1 基本技巧：受限直接执行

直接执行：直接在CPU上运行程序。

下表展示了基本的直接执行协议：

OS	Program
为进程列表创建条目；为程序分配内存；将程序加载到内存；将参数设置到程序栈
清楚寄存器；执行call main()
	执行main()；从main中执行return
释放进程的内存；将进程从进程列表中清除

但是这会产生问题：

• OS如何确保程序不做不安全的操作
• OS如何进行进程切换

6.2 问题1：受限制的操作

Q：如何执行受限制的操作？

引入用户态/内核态的概念，程序在用户态下运行的代码会受到限制。OS以内核态运行，特权指令在这个模式下运行。

Q：用户希望执行特权操作，如何实现？

硬件提供了用户执行系统调用的能力，允许内核向用户进程暴露一些系统调用，例如访问文件系统、创建和销毁进程、与其他进程通信以及内存分配等操作。

要执行系统调用，程序必须执行特殊的trap指令。该指令同时跳入内核，转为内核态进行系统调用，完成后，OS调用return-from-trap指令，返回到发出调用的用户程序中，同时将级别转为用户态。

为了保证return-from-trap正确返回，需要将进程trap之前的状态保存起来。

Q：陷阱如何知道在OS内运行哪些代码？

内核通过在启动时设置trap table（中断向量表）来实现。

6.3 在进程之间切换

Q：OS如果重新获得CPU的控制权，以便它可以在进程之间切换？

协作方式：等待系统调用

这是一种被动获取方式，还不能确保。

非协作方式：操作系统进行控制

进行时钟中断（timer interrupt），时钟设备可以设置为每隔几毫秒产生一次中断，中断时，当前正在运行的进程 停止，OS中预先准备的中断处理程序会运行，此时OS重新获得CPU的控制权。

保存和恢复上下文

context switch：为当前正在执行的进程保存一些寄存器的值，并为即将运行的进程恢复一些寄存器的值。

需要注意：上下文的切换不仅仅来自于保存和恢复少量的寄存器的操作。程序运行时，会在CPU Cache、TLB、分支预测器和其它片上硬件中建立大量的状态。

图6.1是xv6的上下文切换代码：

Chapter 7 进程调度

Q：如何开发一个考虑调度的基本框架？

7.1 工作负载假设

我们对OS中运行的进程做出如下的工作负载假设（这些假设是不现实）：

• 每一个工作运行相同的时间。
• 所有的工作同时到达。
• 一旦开始，每个工作保持运行直到完成。
• 所有的工作只是用CPU。（不执行IO操作）
• 每个工作的运行时间是已知的。

7.2 调度指标

只用一个指标：周转时间（turnaround time），定义是任务完成时间减去任务到达时间。正式定义：

$$T周转时间 = T完成时间 - T到达时间$$

公平是另一个性能指标，但是性能和公平在调度系统中是矛盾的。

7.3 FIFO

先进先出调度，也称为先来先服务（FCFS），特性：简单并易于实现。

如果存在护航效应（convoy effect）：即前面的任务运行时间长，一些耗时较少的进程排在耗时较长的进程之后。

Q：如何开发以中更好的算法来处理这个情况？

7.4 最短任务优先（SJF）

如果所有任务同时到达，，SJF是一个最优的调度算法。

但是如果不是同时到达，存在饥饿问题。

7.5 最短完成时间优先（STCF）

如果对SJF添加抢占，则被称为最短完成时间优先（STCF）。每当新进程进入系统，它会确认所有的进程，谁的剩余完成时间最少，然后调度它。

7.6 新度量指标：响应时间

对于早期的批处理系统来说，STCF可能是一个很好的策略。但是，引入分时系统之后，用户会对系统的交互性能有所要求。因此诞生了一个新的调度程序度量标准：响应时间。

$$T响应时间 = T首次运行时间 - T到达时间$$

STCF和相关方法在响应时间的表现上并不是很好。例如：如果3个进程同时到达，第三个工作必须等待前两个工作全部运行后才能运行。

7.7 轮转（Round-Robin）

基本思想：RR在一个时间片内运行工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束，反复执行，直到所有任务完成。

注意点：

• 时间片长度必须是时钟中断周期的倍数。
• 时间片长度对于RR至关重要，时间片越短，在响应时间上表现越好，但是会增加上下文切换的性能开销。因此需要权衡时间片的大小。

两种调度程序：

• SJF、STCF：优化周转时间，对响应时间不利。
• RR：优化响应时间，对周转时间不利。

7.8 结合I/O

调度程序会在工作时发起I/O请求，OS会根据具体情况来选择执行顺序，以便更好地交互使用资源。

7.9 无法预知

在通用的OS中，操作系统无法预知每个作业的长度，因此我们如何能够将已经看到的一些想法与RR调度程序结合起来，以便响应时间变得不错？

Chapter 8 多级反馈队列

多级反馈队列（MLFQ）应用于兼容时分共享系统。主要解决两方面问题：

• 优化周转时间：先执行短作业来实现。
• 降低响应时间：如何降低？

Q： 没有工作长度的前提条件，如何设计一个能同时减少响应时间和周转时间的调度程序？

8.1 基本规则

MLFQ中有许多独立的队列，每个队列有不同的优先级，任何时刻，一个任务只能存在于一个队列中，MLFQ总是执行优先级较高的工作。

MLFQ会根据观察到的行为调整它的优先级。例如：一个工作不断放弃CPU去等待键盘输入，MLFQ则推断它是交互式进程，并让它保留高优先级。相反，如果一个工作长时间占用CPU，MLFQ则会降低其优先级。

8.2 尝试1：如何改变优先级

Q：MLFQ如何改变任务的优先级？

既有很多运行时间很短、频繁放弃CPU的交互式进程，也有需要很多CPU时间、响应时间不重要的计算密集型进程。优先级调整算法：

• 任务进入系统，放在最高优先级的队列。
• 任务用完整个时间片，降低其优先级，下移一个队列。
• 如果任务在其时间片内主动释放CPU，则优先级不变。

存在的问题

• 饥饿问题：如果系统有很多交互式进程，就会不断占用CPU，导致长任务永远无法得到CPU。
• 如何阻止调度程序被欺骗？

8.3 尝试2：提升优先级

上面存在的问题需要解决，一个简单的思路就是周期性的提升所有任务的优先级。规则如下：

• 经过一段时间S，就将系统中所有任务重新加入最高优先级队列中。

Q：时间S如何设置？

太高会导致长任务饥饿，太低会让交互式任务得不到合适的CPU时间。

8.4 尝试3：更好的计时方式

Q：如何阻止调度程序被欺骗？

解决：为每层队列提供更完善的CPU计时方式，调度程序应该记录一个进程在某一层中消耗的总时间。而不是在调度时重新计时。规则如下：

• 一旦任务用完了其在某一层的时间配额，则降低其优先级。

8.5 MLFQ调优及其他问题

MLFQ调度算法的参数如何设置？

Solaris的MLFQ提供了一组表来决定进程在其生命周期中如何调整优先级，每层的时间片大小、时间S都由管理员动态调整。

8.6 MLFQ 小结

• 规则1：如果A优先级 > B优先级，运行A
• 规则2：如果A优先级 = B优先级，轮转运行A和B
• 规则3：任务进入系统时，放在最高优先级。
• 规则4：一旦任务用完了其在某一层的时间配额，就降低其优先级。
• 规则5：经过一段时间S，就将系统中所有任务重新加入最高优先级队列。

Chapter 9 比例份额

比例份额算法基于一个简单的想法：调度程序的最终目标，是确保每个工作获得一定比例的CPU时间，而不是优化周转时间和响应时间。

Q：如何按比例分配CPU？关键机制与效率如何？

9.1 基本概念：彩票数代表份额

彩票调度（lottery scheduling）背后是一个基本概念：彩票数（ticket）代表了进程占有某个资源的份额。一个进程拥有的ticket占总ticket的百分比，就是它占有资源的份额。

例如：进程A拥有75张ticket，B拥有25张，则将CPU时间按3:1分配给A、B进程。

通过定时地抽取ticket，由于程序知道总ticket，因此每次通过随机数对进程占用时间进行分配。

9.2 彩票机制

该机制提供了一些有效的方式来调度彩票。

• 利用彩票货币（ticket currency）的概念，允许拥有一组ticket的用户以他们喜欢的某种货币，将ticket分给自己的不同工作。之后OS再自动将这种货币兑换成正确的全局ticket。
• 彩票转让（ticket transfer）：一个进程可以临时将自己拥有的彩票交给另一个进程。
• 彩票通胀（ticket inflation）：一个进程可以临时提升或降低自己拥有的彩票数量。

9.3 实现

需要一个随机数生成器来选择中奖彩票和一个记录系统中所有进程的数据结构（链表），以及所有彩票的总数。

int counter = 0;

int winner = getrandom(0, totalTickets);

node_t * current = head;

while(current){
    counter = counter + current->tickets;
    if (counter > winner)
        break;
    current = current->next;
}

Chapter 10 多处理器调度

Q：OS如何在多CPU上进行调度工作？会遇到什么新问题？

10.1 多处理器架构

与单CPU之间的基本区别：对硬件缓存的使用，以及多处理器之间共享数据的方式。

如果系统有多个处理器，并共享同一个内存，会出现什么问题？

案例：如果一个运行在CPU1上的程序从内存地址A读取数据，由于未命中缓存，系统直接访问内存，得到值D，然后修改了地址A处的值，但实际上h只是将缓存修改为新值D’。系统会在一段时间之后再将数据从缓存更新到内存。假设此时，CPU2中的程序读取地址A处的值，然而得到了旧值D。

以上问题被称为缓存一致性（cache coherence）问题。

硬件提供了 这个问题的基本解决方案：通过监控内存访问，硬件可以保证获得正确的数据，并保证共享内存的唯一性。在基于总线的系统中，一种方式是使用bus snooping。每个缓存都通过监听链接所有缓存和内存的总线。如果发现内存访问，则对缓存中的对应数据进行更新。

10.2 同步

跨CPU访问共享数据时，需要使用互斥原语或其他方法（lock-free）才能保证正确性。

10.3 缓存亲和度

cache affinity：一个进程在CPU上运行时，会在该CPU的缓存中维护许多状态。下次该进程在相同CPU上运行时，由于缓存中的数据而执行的更快。相反，在不同的CPU上执行，会由于需要重新加载数据而很慢。因此多处理器调度应该考虑这种缓存亲和性，尽量将进程保持在同一个CPU上执行。

10.4 单队列调度

Q：如何设计一个多处理器系统的调度程序？

最基本的方式是简单地复用单处理器调度的基本架构。将所有进程放到一个队列中。将此称为单队列多处理器调度（SQMS）。

缺点：

• 缺乏可扩展性
• 缓存亲和性

10.5 多队列调度

每个CPU一个队列。将此称为多队列多处理器调度（MQMS）。每个队列使用不同的调度规则。当进程进入系统后，会根据一些启发性原则（随机或选择较空的队列）将其放入某个调度队列。

优点：

• 可扩展性
• 有良好的缓存亲和性

缺点：

• 负载不均

Q：如何应对负载不均？

migration：将工作跨CPU移动。如果CPU1的队列无任务，CPU1的队列中有两个任务，OS会将CPU1队列中的一个任务migration到CPU0的队列。

work stealing：较少任务的队列会从其它队列中steal任务。缺点：频繁检查会引起较高的开销。需要设置合理的检查间隔。

10.6 Linux多处理器调度

Linux存在三种不同的调度程序：

• O(1)调度程序
  • 基于优先级，随着时间推移改变进程的优先级
• 完全公平调度程序（CFS）
  • 使用多队列
  • 确定的比例调度方法
• BF调度程序（BFS）
  • 使用单队列
  • 基于比例调度

内存虚拟化

Chapter 13 地址空间

13.1 早期系统

早期的机器物理内存看起来如图13.1所示。

13.2 多道程序和时分共享

多道程序系统时代开启后，多个进程运行时，如果一个进程等待IO操作，操作系统会切换进程，以提高CPU的有效利用率。

分时系统中交互性变得很重要，因为许多用户可能同时在使用机器，每个人都在等待任务及时响应。一种实现时分共享的方法，是让一个进程单独占用全部内存运行一小段时间。然后停止它，并将它所有的状态信息保存在磁盘上，进行其他进程的调度，这样可以实现比较粗糙的机器共享。

但是这样操作会使得进程切换变得十分缓慢。可以选择将进程数据保存在内存中。

13.3 地址空间

OS需要提供一个易用的物理内存抽象模型，这个抽象模型叫做address space。是运行的程序看到的内存。

一个进程的地址空间包括运行的程序的所有内存状态，图13.3是一个简单的例子。

Q：OS如何在单一的物理内存上为多个运行的进程构建一个地址空间？

13.4 目标

虚拟内存的目标：

• 透明（transparency）
  • OS实现虚拟内存的方式，应该让运行的程序看不见。
• 效率（efficiency）
  • 追求虚拟化尽可能高效。
• 保护（protection）
  • 当一个进程执行加载、存储等操作不会受其它进程影响，也不能以任何方式访问或影响其他的进程。进程之间需要隔离。

Chapter 14 内存操作API

Q：在UNIX/C系统中，如何分配和管理内存？

14.1 内存类型

在运行一个C程序的时候，会分配两种类型的内存：

• 栈内存：申请和释放是编译器来隐式管理的，有时也称为自动内存。
  • int x = 1;
• 堆内存：申请和释放是由程序员显式地完成，长期内存
  • int *x = (int *) malloc(sizeof(int))
    • 指针存储在栈内存，malloc申请的空间在堆内存

14.2 malloc调用

void malloc(size_t size)

#include<stdio.h>

double *d = (double *) malloc(sizeof(double));

14.3 free调用

释放内存通过调用free()来实现。

int *x = malloc(10 * sizeof(int))
free(x);

14.4 常见错误

• 忘记分配内存
  • 没有malloc就使用指针
• 没有分配足够的内存
• 忘记初始化分配的内存
  • 遇到未初始化的读取，会读取到一些未知值得数据。
• 忘记释放内存
  • 内存泄露（memory leak）
• 在用完之前释放内存
  • 悬挂指针（dangling pointer）
• 反复释放内存
• 错误调用free()
  • 并没有传入指针，错误了传入其他值。

Chapter 15 地址转换

Q：如何实现高效的内存虚拟化？如何提供应用程序所需的灵活性？如何保持控制程序可访问的内存位置，从而确保应用程序的内存访问收到合理的限制？

通过基于硬件的地址转换，它可以看成是受限直接执行这种一般方式的补充。

通过地址转换，硬件对每次对内存的访问进行处理，将指令中的虚拟地址转换为数据实际存储的物理地址。

15.1 假设

我们先假设用户的地址空间必须连续地放在物理内存中。同时，为了简单，我们假设地址空间不是很大，小于物理内存，假设每个地址空间的大小完全一样。

15.2 一个例子

C程序如下：

void func() {
    int x;
    x = x + 3;
}

程序编译成汇编代码后：

128: movl 0x0(%ebx), %eax
132: addl $0x03, %eax
135: movl %eax, 0x0(%ebx)

以上的程序在进行内存访问时，OS会根据内部机制，将对应的虚拟地址转换成物理地址再进行内存访问。

15.3 动态重定位

第一次应用：基址加界限机制（也称为动态重定位 dynamic relocation）。

含义：每个CPU需要两个硬件寄存器，基址寄存器和界限寄存器。

采用这种方式，在编写和编译程序时假设地址空间从零开始，但是当程序真正执行时，OS会决定其在物理内存中的实际加载地址，并将起始地址记录在基址寄存器上。

physical address = virtual address + base

如果虚拟地址超过界限寄存器，CPU将触发异常。

通常将CPU中负责地址转换的部分统称为内存管理单元（MMU）。

15.4 硬件支持

动态重定位的硬件要求：

硬件要求	解释
特权模式	需要，以访用户模式的进程执行特权操作
基址/界限寄存器	每个CPU需要一对寄存器来支持地址转换和界限检查
能够转换虚拟地址并检查是否越界	电路来完成转换和检查界限
修改基址/界限寄存器的特权指令	在用户程序运行前，OS必须能设置这些值
注册异常处理程序的特权指令	OS必须能告诉硬件，异常发生需要执行哪些代码
能够触发异常	如果进程试图使用特权指令或越界的内存

Chapter 16 分段

简单的通过基址寄存器和界限寄存器实现的虚拟内存很浪费，那么就存在了问题。

Q：怎样支持大地址空间？堆栈之间有大量空闲空间的问题如何解决？

16.1 分段：泛化的基址/界限

为了解决上述问题，引入分段概念。一个段是地址空间里的一个连续定长的区域。一般有三个逻辑段：代码、栈和堆。分段机制使得OS能够将不同的段放到不同的物理内存区域。从而避免了虚拟地址空间中的未使用部分占用物理内存。

16.2 引用哪个段

硬件在地址转换时如何知道段内偏移量？以及地址引用了哪个段？

显式方式：用虚拟地址的前几位标识不同的段。如图所示：

硬件获取物理地址的操作：

segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
Offset = VirtualAddress & OFFSET_MASK
if(Offset >= Bounds[Segment])
	Exception(FAULT)
else
	PhysAddr = Base[Segment] + Offset
	Register = AccessMemory(PhysAddr)

硬件还有其它方法来确定特定地址在哪个段，在隐式方式中，硬件通过地址产生的方式来确定段。例如，如果地址由PC产生，那么地址在代码段，如果基于栈或基址指针，它一定在栈段，其他地址在堆段。

16.3 栈怎么办

由于栈模型在内存中是反向增长的，例如：在物理内存中，开始于28KB，增长到26KB，相应虚拟地址从16KB到14KB，地址转换与正向增长略微不同。

首先需要硬件支持，硬件需要知道段的增长方向。

16.4 支持共享

随着分段机制的不断改进，人们意识到通过再多一点的硬件支持，就能实现新的效率提升。为了节省内存，在地址空间里共享某些内存段是有必要的。

为了支持共享，需要增加一些额外的硬件支持，通过保护位（protection bit），标识程序是否能读写该段，

16.5 细粒度与细粒度的分段

上述方式的分段是粗粒度的，它将地址空间分成较大的、粗粒度的块。一些早期系统更灵活，允许将地址空间划分为大量较小的段。

段的数量增加需要进一步的硬件支持，并在内存中保存segment table。

16.6 操作系统支持

分段带来了新的问题：

• OS在context switch时应该做什么？
  • 各个段寄存器中内容的保存和恢复
• 管理物理内存的空闲空间
• 内存碎片
  • 紧凑（compact）物理内存，重新安排原有的段
    • OS先终止运行进程，将它们的数据重新移动到新的段
    • 成本高，拷贝段是内存密集型，会占用大量的处理器时间
  • 分配算法可以适当解决该问题

Chapter 17 空闲空间管理

Q：如何管理空闲空间？什么策略可以让碎片最小化？不同方法的时空开销如何？

17.1 假设

我们假设基本的接口像malloc()和free()那样，在堆上管理空闲空间。

进一步假设，我们主要关心的是外部碎片（external fragmentation），分配程序也可能出现内部碎片问题。如果分配程序给出的内存块超出请求的大小，在这种情况下会被称为内部碎片。

还假设：内存一旦分配给用户，就不可以被重定位到其他位置。也就是不能进行compaction操作，但是OS在实现分段时，可以通过紧凑来减少碎片。

最后假设：分配程序所管理的是连续的一块字节区域。在一些情况下，分配程序可以要求这块区域增长，例如：用户级的内存分配库在空间即将用完时，可以向内核申请增加堆空间。

17.2 底层机制

分割与合并：

• 如果请求的空间大小小于某块空闲块，分配程序通常会进行分割
• 如果回收一块空闲内存时，如果回收的内存块地址与其它空闲块地址邻近，就将它们合并为一个较大的空闲块。

Q：如何追踪已分配空间的大小？

用户请求N字节的内存，库分配的是N+header大小的空闲块。

header中保存一些额外的信息：

typedef struct header_t {
    int size;
    int magic;
}header_t;

用户在调用free(ptr)时，库会通过简单的指针运算得到header的位置：

void free(void *ptr) {
    header_t *hptr = (void *) ptr - sizeof(header_t);
}

获得header的指针后，库可以很容易的确定幻数是否符合预期值，简单计算释放的空间大小（header大小 + 分配给用户的空间的大小）。

Q：如何在空闲内存内部建立一个列表？

typedef struct node_t {
    int size;
    struct node_t *next;
}node_t;

如何初始化列表？

node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE,
                   MAP_ANON|MAP_PRIVATE, -1, 0);
head->size = 4096 - sizeof(node_t);
head->next = NULL;

假设此时有一个100字节的内存请求，，堆中空间如图17.4所示：

17.3 基本策略

最优匹配 best fit

遍历整个空闲链表，找到和请求大小一样或更大的空闲块，然后返回当中符合要求最小的一块。

能减少空间浪费，但是要付出较高的性能代价。

最差匹配 worst fit

遍历整个空闲链表，找到满足要求最大的空闲块。

碎片不仅多，还有很好的性能代价。

首次匹配 first fit

找到第一个足够大的块，将请求的空间返回给用户。

有速度优势，但是会让空闲链表开头部分有很多小块。可以基于地址排序，通过合并操作减少内存碎片。

下次匹配 next fit

维护一个指针，指向上一次查找结束的位置。从该指针开始查找合适的节点。

避免了对链表开头的频繁操作。

17.4 其他方式

分离空闲链表

如果应用程序经常申请一种或几种大小的内存空间，那就用一个独立的链表，管理这些大小的对象，其它大小的请求都交给更通用的内存分配程序。

例如：在内核启动时，它为可能频繁请求的内核对象创建一些对象缓存，比如锁和文件系统inode等。

伙伴系统

binary buddy allocator：空闲空间首先从概念上被看成为$2^N$大小，当有一个内存分配请求时，空闲空间被递归地一分为二，直至刚好满足请求的大小。

这种分配策略只允许分配2的整数次幂大小的空闲块。

如果回收内存时，会检查对应伙伴（与其相等大小的另一半）是否空闲，如果空闲则进行合并，直至整个内存区域。

其它想法

查询链表的时间复杂度较高，可以采用查询性能更为高效的数据结构来优化开销哦啊，例如平衡二叉树、伸展树等。

Chapter 18 分页介绍

分段技术随着时间推移，分配内存会变得比较困难。

还可以考虑第二种方法：将空间分割成固定长度的分片。这种思想成为分页。分页是将一个进程的地址空间分割成几个不同长度的逻辑段（代码、堆、段），而是分割成固定大小的党员，每个单元成为一页。相应地，我们把物理内存看成是定长槽块的阵列，叫做页帧（page frame）。每个这样的页帧包含一个虚拟内存页。

Q：如何通过页来实现虚拟内存？从而避免分段产生的问题？基本技术是什么？

18.1 一个简单例子

如图所示，物理内存由一组固定大小的槽块组成。

为了记录地址空间的每个虚拟页放在物理内存中的位置，操作系统通常为每个进程保存一个数据结构，称为页表（page table），主要作用是为地址空间的每个虚拟页面保存地址转换（address translation），从而让我们知道每一页在物理内存中的位置。

分页如何进行地址转换？

虚拟地址的格式如下：

分成：

• 虚拟页面号（virtual page number VPN）
• 页内的偏移量（offset）

18.2 页表存在哪里

页面会变得非常大，例如：典型的32位地址空间，带有4KB的页，这个虚拟地址分成20位VPN和VPN的12位偏移量。20位的VPN意味着操作系统需要管理$2^{20}$个地址转换，假设每个页表条目（Page Table Entry）需要4个字节，那么每个页表则需要4MB内存。

图18.4是OS内存中的页表：

18.3 Page Table Entry

PTE中有什么？

• 有效位（valid bit）：通常用于指示特定地址转换是否有效
  • 例如：一个程序开始运行时，它的代码和堆在其地址空间的一端，栈在另一端。所有未使用的中间空间都会被标记为无效，如果进程访问这部分，则会trap，导致进程终止。
  • 有效位对于支持稀疏地址空间至关重要，通过简单地将地址空间中所有未使用的页面标记为无效。我们不需要再为这些页面分配物理帧，从而节省大量内存。
• 保护位（protection bit）：表明页是否可以读取、写入或执行。
  • 以不允许的方式来访问页，会trap。
• 存在位（present bit）：表明该页是在内存中还是在磁盘上（是否被换出）
• 脏位（dirty bit）：表明页面被带入内存后是否被修改过
• 参考位（reference bit）：表明用于追踪页是否被访问，也用于确定哪些页很受欢迎。
  • 在page replacement时十分重要。

X86架构的示例PTE如图18.5所示：

主要包含：

• 存在位P
• 是否允许读写R/W
• 确定用户是否可以访问该页面的用户/超级用户位U/S
• 确定硬件缓存如何为这些页面工作PWT、PCD、PAT、G
• 访问位A
• 脏位D
• 页帧号PFN

18.3 分页：也很慢

分页模式中进行地址转换，硬件必须知道正在运行的进程的页表的位置，现在假设一个页表基址寄存器（page-table base register）包含了页表的起始位置的物理地址，为了找到想要的PTE位置，硬件将执行以下功能：

VPN_MASK = 0x30 //110000
SHIFT = 4  //偏移量的位数
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE))

主要是：

• 将VPN向右移动以形成正确的整数虚拟页码。
  • 例如21（010101）掩码将此值转换为010000，移位将它变为01，或虚拟页1
• 使用此值作为页表基址寄存器指向的PTE数组的索引

一旦知道了PTE的物理地址，硬件就可以从内存中获取PTE，提取PFN，将其与虚拟地址的偏移量连接起来，形成所需的物理地址。

其流程如图18.6所示：

最后，硬件可以从内存中获取所需的数据放入寄存器中。

Chapter 19 快速地址转换（TLB）

使用分页作为核心机制来实现虚拟内存，可能会带来较高的性能开销，因为页表存储在物理内存，需要额外多处一次内存访问。

Q：如何加速地址转换，尽量避免额外的内存访问？需要什么样的硬件支持？操作系统如何支持？

地址转换旁路缓冲寄存器（translation-lookaside buffer TLB）：它是频繁发生的虚拟到物理地址转换的硬件cache。对于每次的内存访问，硬件先检查TLB，看其中是否有期望的转换映射。如果有，就完成转换，不用访问页表。

19.1 TLB的基本算法

TLB的基本算法如图所示：

主要步骤如下：

1. 首先容虚拟地址中提取页号（VPN）
2. 然后检查TLB中是否有该VPN的转换映射
3. 如果TLB命中，这意味着TLB有该页的转换映射。那么去除对应的页帧号（PFN），与原来的虚拟地址中的偏移量组合形成期望的物理地址，并访问内存。
4. 如果CPU没有在TLB中找到转换映射，那么访问页表来寻找转换映射，并用该转换映射更新TLB。

19.2 示例：访问数组

为了弄清TLB的操作，我们来看一个简单的虚拟地址追踪。本案例中，假设有一个由10个4字节整型组成的数组，起始虚地址是100，进一步假设，有一个8位的小虚地址空间，页大小为16B，那么我们可以将虚地址划分为4位的VPN（那么总共有16个虚拟内存页）和4位的偏移量（每个页中有16个字节）

图19.2展示了数组的布局。

那么考虑一个简单的程序：访问数组的每个元素

int sum = 0;
for(int i = 0; i < 10; i++){
    sum += a[i];
}

那么程序的执行步骤如下：

• 首先访问a[0]，CPU会看到虚拟地址100，硬件从中提取VPN = 06，然后检查TLB，此时TLB未命中
• 访问a[1]，TLB命中，因为和第一个元素位于同一页
• a[2]命中，同理
• a[3]未命中，和上述同理
• ……

通过TLB的表现来看，命中率为70%。得益于空间局部性。同时，页大小也会影响本例的结果。

如果这次循环不久，再次访问，TLB的命中率会大大提高，这是因为时间局部性，所以TLB的命中率会提高。

19.3 谁来处理TLB未命中

两个答案：硬件或OS

以前硬件的复杂指令集（CISC）全权处理TLB未命中，为了做到这一点，硬件必须知道页表在内存中的确切位置（通过页表基址寄存器）以及页表的确切格式，发生未命中时，硬件会遍历页表，找到正确的entry，取出想要的地址映射。用它更新TLB。

RISC有所谓的软件管理TLB，发生TLB未命中时，硬件会抛出一个异常，这时会暂停当前的指令流，将特权级提升至内核模式，跳转至陷阱处理程序（trap handler），这段代码用于处理TLB未命中的情况。

• 先查找页表中的转换映射
• 然后用特权指令更新TLB，并从陷阱返回
• 此时硬件会重试该指令

几个细节：

• 从陷阱返回指令于不用于系统调用从陷阱返回
  • 系统调用返回是，会继续执行此调用之后的语句
  • TLB未命中时，陷阱返回后，硬件必须从导致陷阱的指令继续执行。那么此次会命中TLB。
• 运行TLB未命中的处理代码时，OS需要避免引起TLB未命中的无限递归
  • 可以将TLB未命中的陷阱处理程序直接放入物理内存中。
  • 或者在TLB中保留一些项，记录永久有效的地址转换，并将其中一些永久地址转换槽块留给处理代码本身。

19.4 TLB的内容

典型的TLB有32项、64项或128项，并且是全相联的（fully associative）。基本上这意味着一条地址映射可能存在TLB中的任意位置。一条TLB的entry内容可能如下：

VPN | FPN | 其它位

注意：TLB的有效位 != 页表的有效位

• 页表中，如果PTE被标为无效，意味着该页不能被进程申请使用。
• TLB有效位只是指出TLB的entry不是有效的地址映射。

19.5 上下文切换时对TLB的处理

TLB中包含的地址映射只是对当前线程有效，因此发生进程切换时，OS或硬件需要确保即将运行的进程不要错误读取了之前进程的地址映射。

Q：进程切换时如何管理TLB的内容？

可能的解决方案：上下文切换时，简单地flush TLB。但是此方案有一定开销。

因此一些系统中增加了硬件支持，实现跨上下文切换的TLB共享。比如有的系统在TLB中添加一个地址空间标识符（Address Space Identifier ASID），可以将ASID看成是进程标识符（PID）。该位标识该地址映射是哪个进程所持有的。如图19.3所示：

19.6 TLB替换策略

Q：如何设计TLB替换策略？

• LRU
• random

19.7 实际系统的TLB表项

MIPS R4000采用软件管理TLB，图19.4展示了简化的MIPS TLB表项：

支持32位的地址空间，页大小为4KB，因此有20位的VPN和12位偏移量。

MIPS TLB还有一些标识位：

• 全局位（Global G）：指示这个页是不是所有进程共享的，如果是，则忽略ASID
• 一致性位（Coherence C）：决定硬件如何缓存该页
• 脏位（Dirty D）：表示该页是否被写入新数据
• 有效位（valid）：告诉硬件该项的地址映射是否有效

Chapter 20 分页：较小的表

上述方案会有一个问题：页表太大，消耗太多内存，那么问题来了：

Q： 如何让页表更小？

20.1 简单的解决方案：更大的页

如果32位的地址空间为例：如每页大小为16KB，则会有18位的VPN，14位的偏移量。假设页表项大小为4字节，那么线性页表中有218项，则每个页表的总大小为1MB。

但是大内存页面会导致每页内部的浪费（内部碎片），因此大部分OS通常使用较小的页：4KB。

20.2 混合方法：分页和分段

将分页和分段结合，减少页表的内存开销。

分段中，有一个基址寄存器，告诉我们每个段在物理内存中的位置，还有一个界限寄存器，告诉我们段的大小。

但是分页分段结合的模式下，使用基址寄存器保存该段的页表的物理地址，界限寄存器用于指示一共有多少页。

虚拟地址示例如下：

Seg  | VPN | Offset
x bit | y bit | z bit

TLB未命中时，硬件使用分段位（SN）来确定要用哪个基址和界限对，然后硬件将其中的物理地址与VPN结合起来，形成页表项的地址。

使用分段会存在问题：

• 例如：如果有一个大而稀疏的堆，仍然可能导致大量的页表浪费。

20.3 多级页表

如何去掉页表中无效区域？而不是将它们全部保存在内存中。

使用多级页表，将线性页表变成了类似树的东西。

在一个简单的二级页表中，页目录中每个页目录项（Page Directory Entries PDE）包括：有效位和页帧号（page frame number PFN），类似于PTE。

多级页表的基本思想很简单，将页表分成页大小的单元，如果页目录项无效，就不分配该页的页表。

问题：

• 多级页表是有成本的，在TLB未命中时，需要从内存加载两次，才能从页表中获得正确的地址转换信息。（一次用于页目录，另一次用于PTE本身）
• 复杂性

案例

假设有一个大小为16KB的地址空间，每个页大小为64byte，因此需要一个14位的虚拟地址，其中VPN8位，偏移量6位。

那么即使只有一小部分地址空间正在使用，线性页表也会有$2 ^ 8$个项。

要为这个地址空间构建一个二级页表，我们从完整的线性页表开始，将他分解为页大小的单元。

假设PTE大小为4 bytes，那么页表大小为1KB（256 * 4 bytes）,页表可以被分成16个 64byte大小的页，每个页有16个PTE。

那么如何获取VPN并且用它索引到页目录中，然后索引到页表的页中。

首先通过4位VPN来索引Page Directory，那么可以通过简单的计算得到PDE的地址。

$$PDEAddr = PageDirBase + (PDIndex * sizeof(PDE))$$

如果获取的页目录项标记为无效，则会引发异常，有效则通过页目录项指向的页表中获得PTE。

通过page table index可以得到PTE地址。

$$PTEAddr = (PDE.PFN) << SHIFT + (PTIndex * sizeof(PTE))$$

最后根据PTE中的映射地址加上偏移量得到物理地址。

20.4 反向页表

只保留一个页表，其中的项代表系统的每个物理页，而不是每个进程一个页表，页表项告诉我们哪个进程正在使用该页，以及该进程的哪个虚拟页映射到此物理页。

如果进行线性扫描，性能开销较高，因此通常使用散列表来加速查找。

20.5 将页表交换到磁盘

一些系统在内存压力较大时，允许将页表swap到磁盘中。

Chapter 21 超越物理内存：机制

Q：如何利用大而慢的设备，透明地提供巨大虚拟地址空间的假象？

为了支持更大的地址空间，就需要更大的内存存储页表，一般可以通过swap，将暂时没用的页表swap到磁盘中。

21.1 交换空间

在OS中，一般将硬盘中存储换入换出的空间称为交换空间。

21.2 存在位

如果页表项的存在位为1，则表示该页存在于物理内存中，如果为0，则在硬盘上，访问为0的页会有page fault。

21.3 page fault

如果一个页不存在，它已被交换到硬盘，那么在处理该错误的时候，OS需要将该页交换到内存中。

Q：OS如何知道需要的页在哪？

可以用PTE存储硬盘地址。

当硬盘I/O完成时，操作系统会更新页表，将此页标记为存在，更新PTE的PFN字段以记录新获取页的内存位置，并重试指令，将PTE更新到TLB中。

21.4 内存满了怎么办

OS希望先交换出一个或多个页，以便为操作系统即将交换新页留出空间。这被称为页交换策略（page-replacement policy）。

21.5 页错误处理流程

• 当TLB未命中会有三种情景：
  1. present and valid：TLB未命中处理程序从PTE中获取PFN，然后重试指令更新TLB，然后继续前面的流程
  2. 页不存在于内存中，抛出page fault
  3. 访问的是无效页的话，抛出segment fault

那么page fault处理程序的流程是什么样呢？

• OS必须为换出的页找到一个物理帧
• 如果没有这样的物理帧，等待置换算法从内存中换出一些页
• 处理程序通过IO请求从swap space中读取页
• OS更新页表并重试指令来更新TLB

21.6 交换的时机

如果是等OS发现内存满了之后，才执行置换算法，有点不切实际。OS是更主动地预留了一小部分空闲内存。

为了保证有少量地空闲内存，大部分OS会设置高水位线（HW）和低水位线（LW），来帮助决定何时从内存中清除页。

如果OS发现有少于LW个页可用时，后台负责释放内存的线程会开始运行，直到有HW个可用物理页。这个后台线程有时被称为swap daemon或者page daemon。

Chapter 22 超越物理内存：策略

Q： 如何决定置换哪个页？

22.1 缓存管理

选择置换策略时，我们的目标是让cache miss最少。程序的平均内存访问时间（Average Memory Access Time， AMAT），这是衡量硬件缓存的指标。可按照如下公式计算AMAT：

$$AMAT = (P_{Hit} * T_M) + (P_{miss} * P_D)$$

其中$T_M$表示访问内存的成本，$T_D$表示访问磁盘的成本，$T_{Hit}$表示缓存命中率，$T_{miss}$表示缓存未命中率。

22.2 最优替换策略

optional：是Belady发明的，最优替换策略能达到总体未命中数量最少。

基本策略：替换内存中在最远将来才会被访问的页。

这个策略不存在，因为无法预知用户使用哪个页面。

Belady异常：缓存大小变大时，命中率反而下降。

22.3 简单策略：FIFO

一些系统使用FIFO替换策略，发生替换时，替换最先进入的页。

22.4 随机

随机置换页面。

22.5 LRU

最近最久未使用

22.9 考虑脏页

如果内存中的页已经被修改，那么替换该页会引起写磁盘操作，性能开销大。因此可以优先选择未修改的页面。

22.11 抖动

频繁换入换出。