HeZephyr's Blog

1 分段：广义基数/边界

到目前为止，我们已经将每个进程的整个地址空间放入内存中。通过基址寄存器和边界寄存器，操作系统可以轻松地将进程重新定位到物理内存的不同部分。然而，您可能已经注意到我们的这些地址空间有一些有趣的地方：在栈和堆之间的中间有一大块“空闲”空间，如下图所示。

虚拟化内存使用的通用技术被称为基于硬件的地址转换，或者简称为地址转换，您可以将其视为对有限直接执行的通用方法的补充。通过地址转换，硬件可以转换每个内存访问（例如，指令提取、加载或存储），将指令提供的虚拟地址更改为所需信息实际所在的物理地址。因此，对于每个存储器引用，硬件都会执行地址转换，以将应用程序存储器引用重定向到它们在存储器中的实际位置。当然，硬件本身无法虚拟化内存，因为它只是提供了有效地虚拟化内存的低级机制。操作系统必须在关键点参与设置硬件，以便进行正确的转换；因此，它必须管理内存，跟踪哪些位置是空闲的，哪些位置正在使用，并明智地进行干预以保持对内存使用方式的控制。

所有这些工作的目标再次是创造一个美丽的幻觉：程序拥有自己的私有内存，其中驻留着自己的代码和数据。虚拟现实的背后隐藏着丑陋的物理事实：当 CPU（或多个 CPU）在运行一个程序和下一个程序之间切换时，许多程序实际上同时共享内存。通过虚拟化，操作系统（在硬件的帮助下）将丑陋的机器现实转变为有用、强大且易于使用的抽象。

github地址

1. 首先，编写一个名为 null.c 的简单程序，该程序创建一个指向整数的指针，将其设置为 NULL，然后尝试取消引用它。将其编译为名为 null 的可执行文件。当你运行这个程序时会发生什么？

   1 2 3 4 5 6 7

   #include <stdio.h> int main() { int *p = NULL; printf("Value of p: %d\n", *p); return 0; }

   1 2 3

   ❯ gcc null.c -o null ❯ ./null [1] 67350 segmentation fault ./null

2. 接下来，在编译程序时加入符号信息（使用 -g 标志）。这样做可以在可执行文件中加入更多信息，使调试器可以访问更多有用的变量名等信息。在调试器下运行程序，键入 gdb null，然后在 gdb 运行后键入 run。gdb 会显示什么？

• 什么是内存虚拟化？
  • 操作系统虚拟其物理内存。
  • 操作系统为每个进程提供一个虚拟内存空间。
  • 看起来每个进程都使用整个内存。
• 内存虚拟化的好处
  • 易于编程
  • 在时间和空间方面提高内存效率
  • 保证进程和操作系统的隔离，防止其他进程的错误访问

1 早期操作系统

从内存的角度来看，早期的机器并没有为用户提供太多的抽象概念。基本上，机器的物理内存如下图所示。

1 多处理器架构

要理解围绕多处理器调度的新问题，我们必须了解单 CPU 硬件与多 CPU 硬件之间的一个新的根本区别。这种区别主要围绕硬件缓存的使用（如下图所示），以及多个处理器之间共享数据的具体方式。

在本章中，我们将研究一种不同类型的调度器，称为比例份额（Proportional-share）调度器，有时也称为公平共享调度器。比例共享基于一个简单的概念：调度器可能会尝试保证每个作业获得一定百分比的 CPU 时间，而不是针对周转时间或响应时间进行优化。

比例份额调度有一个非常出色的早期例子是彩票调度（lottery scheduling），由 Waldspurger 和 Weihl 发现。其基本思想非常简单，每隔一段时间，就会举行一次彩票抽奖，来确定接下来该运行哪个进程。更频繁运行的进程则更有机会中奖。

github地址

1 Note/Translation

• 基本规则

  MLFQ有许多不同的队列，每个队列分配了不同的优先级。在任何给定时间，准备运行的作业都位于单个队列上。 MLFQ 使用优先级来决定在给定时间应运行哪个作业：选择运行具有较高优先级的作业（即较高队列上的作业）。当然，一个队列上可能有多个作业，即具有相同的优先级，这种情况则对这些工作使用RR调度。则MLFQ基本规则如下：

github代码

1 Program Explanation

程序scheduler.py允许您查看不同调度程序在响应时间、周转时间和总等待时间等调度指标下的执行情况。 “实现”了三个调度程序：FIFO、SJF 和 RR。 要运行该程序获取其选项，可执行以下操作： ./scheduler.py -h 或者 python scheduler.py -h 得到：

github代码 在本作业中，您将测量系统调用和上下文切换的成本。测量系统调用的成本相对容易。例如，您可以反复调用一个简单的系统调用（如执行 0 字节读取），并计算所需时间；将时间除以迭代次数，就能估算出系统调用的成本。 您必须考虑的一件事是计时器的精度和准确性。可以使用的典型计时器是 gettimeofday()；阅读手册页了解详细信息。您将看到 gettimeofday() 返回 1970 年以来的时间（以微秒为单位）；然而，这并不意味着计时器精确到微秒。测量对 gettimeofday() 的连续调用，以了解计时器的精确度；这将告诉您必须运行多少次空系统调用测试迭代才能获得良好的测量结果。如果 gettimeofday() 对您来说不够精确，您可以考虑使用 x86 机器上可用的 rdtsc 指令。 测量上下文切换的成本比较麻烦。lmbench 基准测试的方法是在单个 CPU 上运行两个进程，并在它们之间设置两个 UNIX 管道；管道只是 UNIX 系统中进程相互通信的众多方式之一。第一个进程向第一个管道发出写操作，并等待第二个管道的读操作；当看到第一个进程在等待从第二个管道读取数据时，操作系统会将第一个进程置于阻塞状态，并切换到另一个进程，后者从第一个管道读取数据，然后向第二个管道写操作。当第二个进程再次尝试从第一个管道读取数据时，它就会阻塞，这样来回循环的通信就继续进行。通过测量这样反复通信的成本，lmbench 可以很好地估算出上下文切换的成本。您可以尝试使用管道或其他通信机制（如 UNIX 套接字）在这里重新创建类似的功能。 在拥有多个 CPU 的系统中，测量上下文切换成本是个难题；在这样的系统中，你需要做的是确保上下文切换进程位于同一个处理器上。幸运的是，大多数操作系统都有将进程绑定到特定处理器的调用；例如，在 Linux 系统中，调用 sched_setaffinity() 就是你要找的。通过确保两个进程位于同一处理器上，就能确保衡量操作系统在同一 CPU 上停止一个进程并恢复另一个进程的成本。

github代码

1. 编写一个调用 fork() 的程序。在调用 fork() 之前，让主进程访问一个变量（如 x）并将其值设为某个值（如 100）。子进程中的变量值是多少？当子进程和父进程都改变 x 的值时，变量会发生什么变化？

   调用fork会创建一个与父进程几乎完全一样的副本，且会复制当前执行的上下文，所以子进程中的变量值是100，它们改变x的值都是互不影响的。执行python q1.py可得到结果如下：