博客

计算机系统课程 笔记总结 CSAPP第九章 虚拟存储器（9.6-9.10）

  • Post author:
  • Post category:其他



目录


9.6 地址翻译


9.6.1 结合高速缓存和虚拟内存


9.6.2 利用TLB加速地址翻译


9.6.3 多级页表


9.8 内存映射


9.8.1 再看共享对象


9.8.2 再看fork函数


9.8.4 使用mmap函数的用户级内存映射


9.9 动态内存分配


9.9.1 malloc和free函数


9.9.3 分配器的要求和目标


9.9.4 碎片


9.9.6 隐式空闲链表


9.10 垃圾收集

9.6 地址翻译



  • Virtual Address Space




    虚拟地址空间


    • V = {0, 1, …, N–1}


  • Physical Address Space




    物理地址空间


    • P = {0, 1, …, M–1}


  • Address Translation




    地址翻译



    • MAP:  V




      ®




      P  U  {





      Æ




      }

    • For virtual address



      a



      :



      • MAP(a)  =  a



        ’


        ：虚拟地址



        a



        处的数据在



        p



        的物理地址



        a’



        处


      • MAP(a)  =




        Æ




        ：



        虚拟地址



        a



        处的数据不在物理内存中

        • 不论无效地址还是存储在磁盘上

1) 处理器生成一个虚拟地址，并将其传送给MMU

2-3) MMU 使用内存中的页表生成PTE地址

4) MMU 将物理地址传送给高速缓存/主存

5) 高速缓存/主存返回所请求的数据字给处理器

1) 处理器将虚拟地址发送给 MMU

2-3) MMU 使用内存中的页表生成PTE地址

4) 有效位为零, 因此 MMU 触发缺页异常

5) 缺页处理程序确定物理内存中牺牲页 (若页面被修改，则换出到磁盘)

6) 缺页处理程序调入新的页面，并更新内存中的PTE

7) 缺页处理程序返回到原来进程，再次执行缺页的指令


9.6.1 结合高速缓存和虚拟内存




VA






: virtual address






虚拟地址






,






PA






: physical address






物理地址






,




PTE






:page table entry






页表条目






,






PTEA






= PTE address






页表条目地址


9.6.2 利用TLB加速地址翻译



  • 页表条目




    (PTEs)




    恰巧缓存在




    L1


    • PTE


      可能被其他数据引用所驱逐

    • PTE


      命中仍然需要


      1-2


      周期的延迟


  • 解决办法




    :





    Translation Lookaside Buffer





    (TLB)




    翻译后备缓冲器


    • MMU


      中一个小的具有高相联度的集合

    • 实现虚拟页码向物理页码的映射

    • 对于页码数很少的页表可以完全包含在


      TLB


      中

  • TLB 命中减少内存访问
  • TLB 不命中引发了额外的内存访问

    • 因为局部性，TLB 不命中很少发生

  • CPU产生一个虚拟地址
  • （2-3）MMU从TLB中取出相应的PTE
  • MMU将这个虚拟地址翻译成一个物理地址，并将它发送到高速缓存/主存
  • 高速缓存/主存将所请求的数据字返回给CPU


9.6.3 多级页表



  • 以二级页表为例：


    • 一级页表


      :


      每个


      PTE


      指向一个页表


      (


      常驻内存


      )

    • 二级页表


      :


      每个


      PTE


      指向一页


      (


      paged in and out like any other data


      页面可以调入或调出页表


      )


  • 程序员的角度看待虚拟内存

    • 每个进程拥有自己私有的线性地址空间
    • 不允许被其他进程干扰

  • 系统的角度看待虚拟内存

    • 通过获取虚拟内存页面来有效使用内存

      • 有效只因为“局部性”的原因
    • 简化编程和内存管理
    • 提供方便的标志位来检查权限以简化内存保护

9.8 内存映射



  • Linux




    通过将虚拟内存区域与磁盘上的对象关联起来以初始化这个虚拟内存区域的内容




    .


    • 这个过程称为内存映射（




      memory mapping






      ）





      .


  • 虚拟内存区域可以映射的对象




    (




    根据初始值的不同来源分




    ) :



    • 磁盘上的





      普通文件




      (e.g.,


      一个可执行目标文件


      )


      • 文件区被分成页大小的片，对虚拟页面初始化



    • 匿名文件




      (


      内核创建，全是二进制零


      )


      • 第一次引用该区域内的虚拟页面时分配一个全是零的物理页


        (




        demand-zero page






        请求二进制零的页




        )

      • 一旦该页面被修改，即和其他页面一样


  • 初始化后的页面在内存和交换文件（





    swap file





    ）之间换来换去


9.8.1 再看共享对象

  • 共享对象:      堆栈、数据、堆区、寄存器

    • 私有的写时复制（Copy-on-write）对象
  • 两个进程都映射了私有的写时复制对象
  • 区域结构被标记为私有的写时复制
  • 私有区域的页表条目都被标记为只读
  • 写私有页的指令触发保护故障
  • 故障处理程序创建这个页面的一个新副本，更新PTE条目，且可写
  • 故障处理程序返回时重新执行写指令
  • 尽可能地延迟拷贝（创建副本）充分利用物理内存


9.8.2 再看fork函数



  • 虚拟内存和内存映射解释了




    fork




    函数




    如何为每个新进程提供私有的虚拟地址空间




    .


  • 为




    新进程




    创建虚拟内存


    • 创建


      当前进程


      的的


      mm_struct, vm_area_struct


      和页表的原样副本


      .

    • 两个进程中的每个页面都标记为只读

    • 两个进程中的每个区域结构（


      vm_area_struct


      ）都标记为私有的写时复制（


      COW


      ）


  • 在新进程中返回时，新进程拥有与调用




    fork




    进程相同的虚拟内存


  • 随后的写操作通过写时复制机制创建新页面


9.8.4 使用mmap函数的用户级内存映射

9.9 动态内存分配



  • 在程序运行时程序员使用





    动态内存分配器





    (




    比如




    malloc)




    获得虚拟内存




    .


    • 数据结构的大小只有运行时才知道


      .


  • 动态内存分配器维护者一个进程的虚拟内存区域，称为





    堆





    .



  • 分配器将堆视为一组不同大小的





    块






    (blocks)





    的集合来维护，每个块要么是已分配的，要么是空闲的。

  • 分配器的类型




    • 显式分配器





      :



      要求应用显式地释放任何已分配的快

      • 例如，C语言中的 malloc 和 free



    • 隐式分配器






      :




      应用检测到已分配块不再被程序所使用，就释放这个块

      • 比如Java，ML和Lisp等高级语言中的垃圾收集 (garbage collection)


9.9.1 malloc和free函数



#include <stdlib.h>



void *malloc(size_t size)


  • 成功


    :


    • 返回已分配块的指针，块大小至少



      size



      字节，对齐方式依赖编译模式：


      8


      字节（


      32


      位模式），


      16


      字节（


      64


      位模式）

    • If



      size == 0



      , returns NULL

  • 出错


    :


    返回


    NULL (0)


    ，同时设置



    errno



void free(void *p)


  • 将


    p


    指向的块返回到可用内存池


  • p



    必须



    malloc




    、




    realloc




    或




    calloc




    已分配块的起止地址



Other functions



  • calloc:




    malloc




    的另一版本，将已分配块初始化为




    0



    .


  • realloc:



    改变之前分配块的大小


    .


  • sbrk:



    分配器隐含地扩展或收缩堆



  • Applications




    应用


    • 可以处理任意的分配


      (



      malloc)



      和释放



      (free)



      请求序列

    • 只能释放已分配的块


  • Allocators




    分配器


    • 无法控制分配块的数量或大小

    • 立即响应



      malloc



      请求


      • 比如


        ,


        不允许分配器重新排列或者缓冲请求

    • 必须从空闲内存分配块

    • 必须对齐块，使得它们可以保护任何类型的数据对象


      • 8


        字节


        (x86) or 16


        字节


        (x86-64)


        对齐在


        Linux


        上框

    • 只能操作或改变空闲块

    • 一旦块被分配，就不允许修改或移动它了


      • 比如


        ,


        压缩已分配块的技术是不允许使用的


9.9.3 分配器的要求和目标



U


k


= ( max


i<=k


P


i


)  /  H


k



  • 给定




    n




    个分配和释放请求的某种顺序




    :



    • R




      0




      , R




      1




      , …, R




      k




      , … , R




      n-1



  • 定义






    :






    聚集有效载荷






    (Aggregate payload) P






    k




    • malloc(p)



      结果是一个有效载荷


      p


      字节的块

    • 请求



      R




      k



      完成后


      ,




      聚集有效载荷





      P




      k



      为当前已分配的块的有效载荷之和



  • 定义






    :






    堆的当前的大小






    H






    k



    • 假设



      H




      k



      是单调非递减的

      • 比如, 只有分配器使用

        sbrk

        时堆才会增大



  • 定义






    :






    前






    k+1






    个请求的峰值利用率
  • 最大化内存利用率


  • 目标




    :




    最大化吞吐量，最大化内存利用率


    • 这些目标经常是互相



      矛盾



      的


  • 最大化吞吐量




    Throughput:


    • 每个单位时间内完成的请求数

    • 例如


      :


      • 10


        秒内完成


        5,000


        个分配请求和


        5,000


        个释放请求

      • 吞吐量是


        1,000


        次操作


        /


        秒


9.9.4 碎片


  • 是当空闲内存合计起来足够满足一个分配请求，但是没有一个独立的空闲块足够大可以来处理这个请求时发生的。

  • 取决于将来请求的模式

    • 难以量化



  • 外部




    碎片


  • 对一个给定块




    ,




    当有效荷载小于块的大小时会产生





    内部碎片

  • 产生原因

    • 维护数据结构产生的开销
    • 增加块大小以满足对齐的约束条件
    • 显式的策略决定

      (比如, 返回一个大块以满足一个小的请求)


  • 只取决于





    以前





    请求的模式

    • 易于量化



  • 碎片化





    导致内存利用率低




    • 内部




      碎片



知道释放多少


  • Standard method


    标准方法


    • 在块的前面的


      word


      中记录该块的长度


      .



      • 这个




        word




        被称为





        头部

    • 每个被分配块都需要一个这样的“


      word”



记录空闲块



  • 方法




    1:





    隐式空闲链表






    (Implicit list)





    通过头部中的大小字段




    —




    隐含地连接所有块


  • 方法




    2:





    显式空闲链表






    (






    Explicit list)





    在空闲块中使用指针


  • 方法




    3:





    分离的空闲列表






    (Segregated free list)


    • 按照大小分类，构成不同大小的空闲链表


  • 方法




    4:




    按





    块按大小排序






    —






    平衡树


    • 在每个空闲块中使用一个带指针的平衡树，并使用长度作为权值


9.9.6 隐式空闲链表



  • 对于每个块我们都需要知道块的大小和分配状态


    • 可以将这些信息存储在两个


      words


      中


      :


      浪费


      !


  • Standard trick




    标准技巧


    • 如果块是对齐的，那么一些低阶地址位总是


      0

    • 不要存储这些


      0


      位，而是使用它作为一个已分配


      /


      未分配的标志

    • 读大小字段时，必须将其屏蔽掉



隐式链表法：找到一个空闲块



  • 首次适配




    (First fit):



    • 从头开始搜索空闲链表，选择





      第一个





      合适的空闲块




      :

    • 可以取总块数


      (


      包括已分配和空闲块


      )


      的线性时间

    • 在靠近链表起始处留下小空闲块的 “碎片”


  • 下一次适配




    (Next fit):


    • 和首次适配相似，只是从链表中上一次查询结束的地方开始

    • 比首次适应更快


      :


      避免重复扫描那些无用块

    • 一些研究表明，下一次适配的内存利用率要比首次适配低得多


  • 最佳适配




    (Best fit):



    • 查询链表，选择一个





      最好的





      空闲块：




      适配，剩余最少空闲空间

    • 保证碎片最小


      ——


      提高内存利用率

    • 通常运行速度会慢于首次适配



隐式链表


—-


分配空闲块



  • 分配空闲块




    :





    分割






    (splitting)



    • 既然分配块比空闲块小


      ,


      我们可以把空闲块分割成两部分
  • 释放一个块

  • 最简单的实现


    :


    • 清除 “已分配


      (allocated) ”


      标志


      • void free_block(ptr p) { *p = *p & -2 }

    • 但有可能会产生 “假碎片


      (false fragmentation)”




合并



  • 合并





    (coalesce)





    ：合并相邻的空闲块


    • 和下一个空闲块合并



  • 边界标记






    ( Boundary tags )




    [Knuth73]


    • 在空闲块的“底部”标记


      大小


      /


      已分配

    • 允许我们反查 “链表


      ”


      ，但这需要额外的空间

    • 重要且普遍的技术


      !



双向合并




  • 边界标记






    ( Boundary tags )




    [Knuth73]


    • 在空闲块的“底部”标记


      大小


      /


      已分配

    • 允许我们反查 “链表


      ”


      ，但这需要额外的空间

    • 重要且普遍的技术


      !


边界标记法的缺陷


  • Internal fragmentation


    内部碎片

    • 头部脚部双标记，小块浪费空间

  • Can it be optimized?


    它是最优的么？

    • 把前面块的已分配/空闲位存放在当前块中多出来的地位中！！！
    • 哪些块需要脚标?
    • 有什么作用?

关键的分配策略总结


  • Placement policy:


    放置策略

    • 首次适配, 下一次适配, 最佳适配, 等等.
    • 减少碎片以提高吞吐量



    • 有趣的观察





      :



      近似于最佳适配算法，独立的空闲链表不需要搜索整个空闲链表

  • Splitting policy


    分割策略


    :

    • 我们什么时候开始分割空闲块?
    • 我们能够容忍多少内部碎片?

  • Coalescing policy


    合并策略


    :




    • 立即合并






      (Immediate coalescing):




      每次释放都合并



    • 延迟合并






      (Deferred coalescing):




      尝试通过延迟合并，即直到需要才合并来提高释放的性能


      .


      例如


      :

      • 为

        malloc

        扫描空闲链表时可以合并
      • 外部碎片达到阈值时可以合并

隐式链表：总结


  • 实现


    :


    非常简单

  • 分配开销


    :

    • linear time worst case  最坏情况线性时间

  • Free cost


    释放开销


    :

    • constant time worst case 最坏情况常数时间
    • even with coalescing 即使合并

  • Memory usage


    内存使用


    :

    • will depend on placement policy 取决于分配策略
    • First-fit, next-fit or best-fit 首次适配，下一次适配或最佳适配

  • Not used in practice for malloc/free because of linear-time allocation


    由于现行时间分配，没有用于


    malloc/free

    • used in many special purpose applications 用于许多特殊目的的应用


  • However, the concepts of splitting and boundary tag coalescing are general to





    all





    allocators

  • 然而，分割和边界标记合并的概念对于所有的分配器来说都是通用的

9.10 垃圾收集

隐式内存管理




  • 垃圾收集






    :





    自动回收堆存储的过程




    —




    应用从不显式释放

  • 常见于多种动态语言中


    :

    • Python, Ruby, Java, Perl, ML, Lisp, Mathematica

  • “


    保守的”垃圾收集器为


    C


    和


    C++


    程序提供垃圾收集

    • 然而，它并不能收集所有的垃圾



  • 内存管理器如何知道何时可以释放内存？

    • 一般我们不知道下一步会用到什么，因为这取决于具体条件
    • 但是我们知道如果没有指针，某些块就不能被使用

  • 必须做些关于指针的假设

    • 内存管理器可以区分指针和非指针
    • 所有指针都指向一个块的起始地址
    • 无法隐藏指针

      (e.g., by coercing them to an

      int

      , and then back again)

  • 应用


    • new(n):

      返回指向所有位置已被清除的新块的指针

    • read(b,i):

      读取

      b

      块位置

      i

      的内容到寄存器

    • write(b,i,v):

      将内容

      v

      写入到

      b

      块位置 I

  • 每个块都会有一个包含一个字的头部

    • 对于块

      b

      ，标记为

      b[-1]
    • 用在不同的收集器中，可以起到不同的作用

  • 垃圾收集器使用函数的说明


    • is_ptr(p):

      判断p是不是指针

    • length(b):

      返回块b以字为单位的长度（不包括头部）

    • get_roots():

      返回所有根节点


内存相关的风险和陷阱


  • Dereferencing bad pointers


    不要引用坏指针

  • Reading uninitialized memory


    读未初始化的内存

  • Overwriting memory


    覆盖内存

  • Referencing nonexistent variables


    引用不存在的变量

  • Freeing blocks multiple times


    多次释放内存

  • Referencing freed blocks


    引用空闲堆块中的数据

  • Failing to free blocks


    释放内存失败


版权声明：本文为gzn00417原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。