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

简介: 【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 引入:如何超越物理内存?

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

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

❓ 如何超越物理内存?

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

"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 守护进程页的性能

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

页错误率:

  • ,表示无页错误。
  • ,表示 每一个引用都是一个错误。

有效访问时间(Effective access time, EAT)

  • 页错误时间包括:
  • 页错误的开销
  • 换入页面的时间
  • 如有必要,换出页面的时间(换出修改过的页面)
  • 重新启动的开销(包括页错误后的内存访问时间)

例1:

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

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

例2:

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

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

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

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

📜 参考资料 

Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces

A. 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]. []. .

百度百科[EB/OL]. []. https://baike.baidu.com/.

相关文章
|
7天前
|
存储 缓存 监控
Flink内存管理机制及其参数调优
Flink内存管理机制及其参数调优
|
12天前
|
存储 算法 调度
深入理解操作系统的内存管理机制
【7月更文挑战第12天】本文将深入探讨操作系统中至关重要的内存管理机制。内存是计算机系统中宝贵的资源,其管理效率直接影响系统性能。我们将从内存管理的基本原理出发,逐步解析分页和分段技术、虚拟内存的概念以及内存分配策略等核心内容。通过实例分析,揭示现代操作系统如何优化内存使用,提高系统响应速度及资源利用效率。
|
11天前
|
存储 缓存 算法
操作系统中的内存管理机制探究
【7月更文挑战第13天】本文深入探讨了操作系统中至关重要的内存管理机制,揭示了其对系统性能与稳定性的影响。通过分析现代操作系统中内存管理的基本原理、关键技术以及面临的挑战,文章提供了对内存分配策略、虚拟内存技术和缓存管理等核心概念的深度解析。进一步地,文章讨论了内存泄漏和碎片化问题,提出了相应的解决策略,旨在为读者提供操作系统内存管理的全面视角,并指出未来可能的发展趋势。
|
13天前
|
缓存 监控 关系型数据库
深入理解Linux操作系统的内存管理机制
【7月更文挑战第11天】在数字时代的浪潮中,Linux操作系统凭借其强大的功能和灵活性,成为了服务器、云计算以及嵌入式系统等领域的首选平台。内存管理作为操作系统的核心组成部分,对于系统的性能和稳定性有着至关重要的影响。本文将深入探讨Linux内存管理的基本原理、关键技术以及性能优化策略,旨在为读者提供一个全面而深入的理解视角,帮助开发者和系统管理员更好地优化和管理Linux系统。
|
17天前
|
存储 算法 数据处理
深入理解操作系统之内存管理机制
【7月更文挑战第7天】本文旨在探讨操作系统中的内存管理机制,揭示其对现代计算机系统性能和稳定性的关键影响。我们将从内存管理的基础知识出发,逐步深入到高级概念如虚拟内存、分页和分段等技术,并讨论内存泄漏、碎片化及其解决方案。通过理论与实践的结合,读者将获得对操作系统内存管理机制的全面认识,并了解其在提升系统效率和资源利用方面的重要性。
|
19天前
|
算法 UED
深入理解操作系统:虚拟内存管理机制
【7月更文挑战第4天】在数字时代的浪潮中,操作系统的虚拟内存管理机制如同一座精巧的时间桥梁,连接着有限的物理资源与无限的程序需求。本文将揭开这座桥梁的秘密,从虚拟内存的基本概念出发,逐步深入到页面置换算法的世界,探讨它们如何影响系统性能和用户体验。通过对比分析不同的页面置换策略,我们旨在为读者提供一种全新的视角,以理解和评估现代操作系统中这一至关重要的功能。
18 1
|
22天前
|
存储 缓存 算法
操作系统的内存管理机制及其对系统性能的影响
本文深入探讨了操作系统中内存管理的关键技术和策略,以及它们如何影响计算机系统的整体性能。通过分析不同的内存分配算法、虚拟内存技术、以及缓存策略,本文旨在揭示这些机制对于提高资源利用效率、减少延迟和优化用户体验的重要性。结合最新的研究成果和实际案例,本文为读者提供了对操作系统内存管理深度理解的视角,并讨论了未来可能的发展趋势。
|
28天前
|
存储 缓存
操作系统的虚拟内存管理机制
在现代计算机系统中,虚拟内存是一种至关重要的内存管理技术。它允许操作系统使用硬盘空间来扩展物理内存容量,从而支持更多并发运行的程序。本文将深入探讨虚拟内存的概念、实现方式以及其在操作系统中的作用和重要性。
|
1月前
|
缓存 算法 Linux
深入理解操作系统的内存管理机制
【6月更文挑战第23天】内存管理是操作系统中一个至关重要的功能,它直接影响到系统性能和资源利用效率。本文旨在深入探讨现代操作系统中内存管理的核心概念、关键技术以及面临的挑战。通过分析内存管理的基本原理、内存分配策略、虚拟内存技术、缓存管理和内存安全等方面,揭示内存管理在提升操作系统稳定性、安全性与高效性方面的作用。文章将结合具体操作系统实例,如Windows、Linux等,阐述不同内存管理技术的实现细节和优化策略,为读者提供对操作系统内存管理机制全面而深刻的认识。
27 3
|
9天前
|
存储 缓存 安全
探索现代操作系统的内存管理机制
【7月更文挑战第15天】在数字时代的脉络中,操作系统作为计算机硬件与软件之间的桥梁,承担着至关重要的角色。其中,内存管理是操作系统核心功能之一,它直接关系到系统性能与稳定性。本文将深入探讨现代操作系统中内存管理的基本原理、关键技术以及面临的挑战,旨在为读者提供对内存管理机制深层次的理解,并展望其未来的发展方向。