【OSTEP】超越物理内存：机制 | 请求分页 | 交换位与存在位 | 页错误

 

💭 写在前面

本系列博客为复习操作系统导论的笔记，内容主要参考自：

• Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy PiecesA. Silberschatz, P. Galvin, and G. Gagne,
• Operating System Concepts, 9th Edition, John Wiley & Sons, Inc., 2014, ISBN 978-1-118-09375-7.Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

📜 文章目录

0x00 引入：如何超越物理内存？

0x01 请求分页（Demand Paging）

0x02 交换空间与存在位（Swap Case and Present bit）

 0x03 页错误（Page Fault）

0x04 页守护进程（Page daemon）

0x05 守护进程页的性能

---

0x00 引入：如何超越物理内存？

到目前为止，我们一直在假设地址空间非常小，能放入物理内存。实际上，我们假设每个正在运行的进程的地址空间都能放入内存。现在，我们将放松这些大的假设，并假设我们需要支持许多同时运行的巨大地址空间。

为了达到这个目的，需要在内存层级上再加上一层。现代操作系统中，硬盘通常能够满足这个需求。因此，在我们的存储层级中，大而慢的硬盘位于顶层，在内存之上。那么问题来了……

❓ 如何超越物理内存？

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

"Program needs to be in memory to execute, but entire program rarely used"

程序需要在内存中执行，但整个程序很少使用。错误码、不寻常的例程、浩大的数据结构。

Entire program is not needed at same time.

然而并不需要在同一时间完成整个程序，因此拥有执行一个只在内存中的程序的能力，自然是大有脾益的。

Virtual memory：separation of user logical (virtual) memory from physical memory

然而 虚拟内存，就是将用户虚拟内存与物理内存分开：

• 当只有较小的物理内存可用时（比如虚拟内存大于物理内存的情况），允许为程序员提供一个非常大的虚拟内存。
• 只有部分程序需要在内存中执行。
• 我们为什么要为进程支持巨大的地址空间？因为这能让程序员可以毫无后顾之忧地编写代码，而不需要担心程序的数据结构是否有足够的空间存储，你只要安心编写程序就行了。

在此之前，一些早期的操作系统是使用 "内存覆盖" 技术的。它需要程序员根据需求手动植入或移出内存中的代码或数据，听起来就很麻烦对吗？举个例子，再调用某个函数前，你需要先安排将代码移入内存后，才能调用…… （这真的很滑稽）

当虚拟内存大于物理内存时：

多道程序和易用性都要操作系统支持比物理内存更大的地址空间，这是所有现代虚拟内存系统都会做的事情。不得不说，虚拟内存比物理内存大，这个 "饼" 画的可谓是相当的好！

0x01 请求分页（Demand Paging）

The concept of virtual memory can be implemented via demand paging.

虚拟内存的概念可以通过 请求分页 来实现。

• 只有在执行过程中需要的时候才会加载页面

In the extreme case, we can start executing a process with no pages in memory – pure demand paging.

在极端情况下，我们可以在内存中没有页的情况下开始执行一个进程 —— 纯需求分页。

• 在需要之前，千万不要将一个页面带入内存。

请求分页 类似于有交换的寻呼系统。

只有在需要时才将一个页面而不是整个进程换入内存。

请求分页的好处：

• 更少的 I/O 和更少的内存需求。
• 更快的响应速度。
• 可以容纳更多用户。

一些页面在内存中，而其他页面在二级存储中。

• Need hardware support to distinguish between in-memory and not-inmemory pages.
• 需要硬件支持来区分内存中和非内存中的页面。

0x02 交换空间与存在位（Swap Case and Present bit）

为了方便物理页的移入或移出，我们需要在硬盘上开辟一部分空间。

在操作系统中，一般这样的空间我们称之为 交换空间（swap case），用于等价交换的。

操作系统需要管理交换空间，以页为单位。

交换空间的大小是非常重要的，它决定了系统在某一时刻能够使用的最大内存页数。

当硬件在 PTE 中查找时，可能发现页不在物理内存中。硬件判断是否在内存中的方法，是通过页表项中的一条叫 存在位（present bit）的新信息去判断的。

• 如果存在位设置为 1，则表示该页存在于物理内存中。
• 如果存在位设置为 0，则表示该页不在内存中，而在硬盘上。

而访问不存在物理内存中的页，这种行为我们称之为 页错误（page fault）。

 0x03 页错误（Page Fault）

在 TLB 未命中的情况下，我们有两种类型的系统：硬件管理的 TLB、软件管理的 TLB。

然而无论在哪种类型的系统中，如果页不存在，都会由操作系统来处理页错误。

操作系统的页错误处理程序（page-fault handler）会出手。

" 页错误处理程序：无所谓，我会出手。"

遇到页错误，都会由操作系统的页错误处理程序确定要做什么。几乎所有的系统都在软件中处理页错误，即使是硬件管理的 TLB，硬件也信任操作系统来管理这个重要的任务。

如果一个页不存在，它已经被交换到硬盘，在处理也错误的时候，操作系统需要将页交换到内存中，那么问题来了……

❓ 操作系统怎么知道所需的页在哪？

许多操作系统中，页表是存储这些信息最自然的地方。因此，操作系统可以用页表项（PTE）中的某些位来存储硬盘地址，这些位通常用来存储像页的 PFN 这样的数据。当操作系统接收到页错误后，他会在页表项中查找地址，并将请求发送到硬盘，将页读取到内存中。

当程序从内存中读取数据会发生什么？

💬 页错误控制流算法（硬件）：

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if ( Success == True )  // TLB 命中
    if ( CanAccess(TlbEntry.ProtectBits) == True )
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else 
        RaiseException(PROTECTION_FAULT)
 
else // TLB 未命中
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    
    // 第三种情况：访问的是一个无效页，可能由于程序中的错误导致。
    if ( PTE.Valid == False )
        RaiseException(SEGMENTATION_FAULT)
    else
        if ( CanAccess(PTE.ProtectBits) == False )
            RaiseException(PROTECTION_FAULT)
 
        // 第一种情况：该页存在且有效。
        else if ( PTE.Present == True )
            // 假设软件管理TLB
            TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
            RetryInstruction()
        // 第二种情况：页错误处理程序需要运行。
 
        else if ( PTE.Present == False )
            RaiseException(PAGE_FAULT)

当 TLB 未命中时会有 3 种重要情景：

• 第一种情况：该页存在且有效。在这种情况下，TLB 未命中处理程序可以简单地从 PTE 中获取 PFN，然后重试指令（这次 TLB 会命中），并因此继续前面的流程。
• 第二种情况：页错误处理程序需要运行。虽然这是进程可以访问的合法页（毕竟是有效的），但是它并不在物理内存中。
• 第三种情况：访问的是一个无效页，可能由于程序中的错误导致。在这种情况下，PTE 中的其他位都不重要了。硬件捕获这个非法访问，操作系统陷阱处理程序运行，可能会杀死非法进程。

💬 页错误控制流算法：

PFN = FindFreePhysicalPage()
if ( PFN == -1 )                   // no free page found
    PFN = EvictPage()              // run replacement algorithm
    DiskRead(PTE.DiskAddr, pfn)    // sleep (waiting for I/O)
    PTE.present = True             // update page table with present
    PTE.PFN = PFN                  // bit and translation (PFN)
    RetryInstruction()             // retry instruction

通过这串代码，我们可以看到为了处理页错误，操作系统大致做了什么。

首先，操作系统必须为将要换入的页找到一个物理帧，如果没有这样的物理帧，我们将不得不等待交换算法的运行，并从内存中踢出一些页，释放帧供这里使用。

在获得物理帧后，处理程序发出 I/O 请求从交换空间读取页。最后，当这个慢操作完成时，操作系统更新页表并重试指令。重试将导致 TLB 未命中，然后再一次重试时，TLB 命中，此时硬件将能够访问所需的值。

🔺 总结：为了处理页错误，操作系统必须为该页找到一个物理帧（frame），如果没有这样的物理帧，那么将等待 替换算法（replacement algorithm）的运行，将一些页面从内存中踢出。

" If there is no such page, waiting for the replacement algorithm to run and kick some pages out of memory.  "

例子：页替换

在没有自由框架的情况下 —— 页替换（page replacement）

0x04 页守护进程（Page daemon）

"The hardware includes a modified bit (a.k.a dirty bit) "

硬件包括一个修改过的位（又称脏位）。

• 页已被修改，因此是脏的，它必须被写回磁盘以 "踢出" 它。
• 因为页没有被修改，所以让他们爬，是没有心理负担的。

❓ 交换何时真正发生？

操作系统会摆烂么？（Lazy approach）

• 操作系统一直等到内存完全满了，才会替换一个页面，为其他页面腾出空间。
• 这显然是不现实的，操作系统怎么会摆烂呢。

到目前为止，我们一直描述的是操作系统会等到内存完全满了以后才会执行交换流程，然后才替换（踢出）一个页为其它页腾出空间。这确实有些不切实际了，因为操作系统可以主动地预留一小部分空闲内存。

交换守护进程或页守护进程（Swap daemon or page daemon）：

为了保证有少量的空闲内存大多数操作系统会设置 高水位线（High Watermark, HW）和 低水位线（Low Watermark, LW），来决定何时从内存中清除页。

• 当可用页数少于 低水位线（LW）时，一个后台负责释放内存的线程就会开始运行。
• 该线程会踢出页面，直到有 HW 个物理页。这个后台线程有时称为 守护进程，或 页守护进程。（守护完后，他会很开心地进入休眠状态，因为他为操作系统是放了一些内存，这让他 feel good）。

0x05 守护进程页的性能

守护进程页可以显著影响计算机系统的性能！

页错误率：0≤p≤1.0" role="presentation" style="position: relative;">0≤p≤1.0$0\le p\le 1.0$

• 若 p=0" role="presentation" style="position: relative;">p=0$p=0$，表示无页错误。
• 若 p=1" role="presentation" style="position: relative;">p=1$p=1$，表示 每一个引用都是一个错误。

有效访问时间（Effective access time, EAT）：

EAT=(1−p)×Tmemory access+p×Tpage fault" role="presentation" style="position: relative;">EAT=(1−p)×Tmemory access+p×Tpage fault$EAT=(1-p)\times T_{\text{memory access}}+p\times T_{\text{page fault}}$

• 页错误时间包括：
  • 页错误的开销
  • 换入页面的时间
  • 如有必要，换出页面的时间（换出修改过的页面）
  • 重新启动的开销（包括页错误后的内存访问时间）

例1：

设内存访问时间为 1 microsec，被替换的50%的页已经被修改，因此需要被换掉。

交换页的时间为：10 millisec = 10,000 microsec

EAT=(1−p)×1+p×(15000)∼1+15000p (in microsec)" role="presentation" style="position: relative;">EAT=(1−p)×1+p×(15000)∼1+15000p (in microsec)$EAT=(1-p)\times 1+p\times (15000)\sim 1+15000p\text{ (in microsec)}$

例2：

设内存访问时间为 200 nanosec，平均页错误服务时间为 8 millisec

如果1,000 次访问中有一次导致页错误，那么 EAT=8.2 microsec

这是一个放缓了40倍的速度！

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