精华内容
下载资源
问答
  • 内存页保护属性?

    2012-08-07 13:06:07
    [img=http://img.my.csdn.net/uploads/201208/07/1344316907_7321.PNG][/img] 为什么我查到的是PAGE_READWRITE 它查到的是PAGE_GUARD|PAGE_READWRITE
  • 引言上一篇文章讲述了内存的地址空间抽象,但是还留下了问题,那就是当软件很大的时候虽然利用Swapping技术可以运行,但是每次交换整个进程的空间开销不容忽视,虽然近年来内存也有增长,但是软件大小增长的速度远...
    引言

        上一篇文章讲述了内存的地址空间抽象,但是还留下了问题,那就是当软件很大的时候虽然利用Swapping技术可以运行,但是每次交换整个进程的空间开销不容忽视,虽然近年来内存也有增长,但是软件大小增长的速度远大于内存增长的速度。

        一个解决方法是Overlays(覆盖),Overlays将程序分割为多个片段,称为覆盖,当程序开始时,覆盖管理器加载覆盖0,执行完成后,通知覆盖管理器加载覆盖1,然后覆盖1会在覆盖0top上(如果有空间),或者直接在覆盖0(如果没空间)。虽然,换入换出覆盖块由操作系统完成,但是需要程序员将程序分块,这是一个复杂的工作,并且非常容易出错。因此这种技术无法普及,因此人们又提出了新的解决方案,这次是完全交给系统完成,那就是今天要学习的一个技术-虚拟内存。

    基本概念
    原理

        每个程序都有自己独立的空间,并且这个空间分了多个固定大小的块,这些块通常叫做,每一个页都有一个连续的地址范围,每一个页都映射一个物理范围叫页框(页框的大小通常和页是一样),程序运行不需要所有的页都在内存中,当程序引用到在物理内存中的地址空间时,由硬件(MMU)完成映射;如果不在内存中,由操作系统载入内存并重新执行失败的指令。

    页框

        物理内存中对应虚拟内存的页叫页框,大小和虚拟内存页大小一致。(RAM和磁盘交换数据是以页为单位的。有不同页面大小混合使用的)

    虚拟地址
    • 虚拟地址是程序在虚拟空间生成的地址,类似于上一篇讲的逻辑地址,它不是真实的物理地址,需要通过一定的转换才能得到物理地址。

    • 简单虚拟地址结构,分为两部分,前n位表示页编号,后m位表示偏移量

      f61408bdc7c66145080fb4b342cd2bdb.png

    • 一个例子:假设一个系统页大小为4Kb,而应用程序需要的空间为64Kb,虚拟页有16个,因此页编号需要4位,而偏移量需要12位,总共16位就可以表示虚拟地址

    页表
    • 页表是一个列表项的集合,最简单的虚拟地址分为两部分,前n位表示的页编号便是页表的索引(这里的页表是很简单的页表,后边在讲如何解决大虚拟内存时会讲到多级页表)

    • 页表项示意图

      59bf4595589682a10512e96240cf7caf.png

      • Present/absent位,表示虚拟页是否在内存中

      • 保护位,简单用一个位0-r/w,1-只读。或者用3个位,分别表示可读、可写和可执行

      • 修改位,当一个页面被写入时该位会自动修改,表示该页是脏的

      • 引用位,当一个页面被访问时,该位会被设置,它的值可以用来帮助OS在缺页时选择被淘汰的页面

      • 禁止缓存位,设置该位代表该位禁止被缓存,用于I/O设备,如果I/O设备有独立的内存空间,该位不需要使用

    • 不同计算机的页表项大小可能不同

    内存管理单元(MMU)
    • 作用:解析虚拟地址映射的物理地址,数学形式:F(VA) = PV

    • MMU工作示意图

      4af517a45207800e44dd344651c6c248.png

    • 虚拟内存映射物理内存示意图

      f7c7fb7ab0687e928b194d2d0810db51.png

      上图是程序的虚拟空间64K,内存是32K,页和页框为4K,可以看到0-4095映射到8192-12287

    • MMU映射过程

      e280163ed6b30266312af3ef016b0096.png

      1. 虚拟地址8196取出高4位计算页表索引,0010表示2,因为找到索引为2的页表项

      2. 通过Present/absent位判断虚拟页是否在内存中,此处的值为1,说明在内存中,找到页框号110;否则MMU发现虚拟地址找不到映射的物理地址,使CPU陷入操作系统(缺页中断),OS会选择一个很少使用的页框交换出去,重新执行陷入OS的指令

      3. 将页框号+上偏移量就是物理内存地址,放到bus上

    分页实现问题
    加速分页-TLB
    • 分页系统面临的两个问题

    1. 虚拟内存地址映射为物理内存地址必须快

    2. 如果虚拟地址空间很大,那么页表空间也要很大

    解决方案-TLB(转换检测缓冲区)

    • 原理:通过观察,大部分的程序多数情况都是反复访问很少的的页,也就是说,只有很少的页被反复访问,大多数页很少访问,TLB硬件一般在MMU里。TLB示意图

      59dc0af2ab6328926076a273a369b832.png

    MMU硬件TLB管理

    当TLB失效时,有MMU硬件负责查找并且装载,主要的好处是一个简单的MMU可以节省芯片的很多空间让给缓存和其他可以提升性能的组件,TLB工作原理图

    dc977989d653dcacfcbf6614d7792dff.png

    大内存页表问题
    • 问题:如果内存非常大,那么页表也很大,比如4G的内存,采用4KB的页大小,那么页表将有100w个页表项,因为页可能分散在内存的各个页框,所以需要维护这个包含100w个页表项的页表,并且有多少个进程就有多少个这种页表,非常浪费空间。

    • 分级页表

      • 原理:采用多级的设置,可以避免始终保持所有的页表在内存中。比如一个进程所需空间进程上下文4M,Data段4M,Stack段4M,总共需要12M,因此虽然虚拟页表还是很大,但是很多都是没有用到的,这些没有用到的页表不应该保存在内存中,而采用两级页表时,只需要保存4个页表,一个顶级页表,一个0-4M、一个4-8M,一个8-12M3个2级页表。顶级页表除了0,其他的页表项Present/absent都会设置为0,每个进程的页表都是独立的

        3cf5a19b43121ff547ceeb2e20e43bea.png

        上图a中PT1、PT2分别表示一级页表索引和二级页表索引。上图中一个进程只用3个顶级页表,而其他页表在/不在位被设置为0,当这些不在页表被访问时,会产生一个缺页中断,OS会做处理,这时访问了不该访问的内存。  

      • 4级页表,4k的页,每级页表用9位索引,最大支持256TB内存

        2ed9e66cf2857e1354f9545d1f9c0884.png

    • 倒序页表

      • 解决的问题:64位地址下的页表会非常大,并且每个进程还有自己独立的页表

      • 原理:传统的页表是通过虚拟地址查找对应物理页,但是每个物理页同一时间只能对应一个进程。所以,可以将传统的页表的表项由虚拟页换成页框,这样页表就会小了很多,当搜索的时候利用进程+虚拟页来查找。搜索需要软件实现,可以借助hash结构,倒序页表示意图

        58a80afb01916d2391befcd5d89e440c.png

      • 倒序页表工作示意图

        6f074dc00e84a48a55481fa36ee5aa0a.png

    页面置换算法

        页面置换算法其实就是缓存淘汰算法,因为可以将高速容量小的存储设备看成低速容量大的存储设备的缓存,那么其实主存就是磁盘的缓存,所以这些页面置换算法都是通用的缓存淘汰算法

    最优页面置换算法
    • 原理:用页面需要访问前执行的指令数来标记,置换标记数大的。将缺页中断尽可能推迟

    • 缺点:不可实现,因为OS不知道各个页面将在什么时候被访问

    • 一个例子,当页框为7-0-1要载入2时,选择7置换出去,因为后续页的访问顺序 0->1->7,7在更远的时间线上才会使用

      59c3f178963417483823402df2190019.png

    最近未使用页面置换算法(NRU)
    • 原理:为了统计虚拟页面使用信息,用两个状态位R和M来标识,页面被访问时R(读/写)会被设置,页面被写入(修改)时M会被设置。周期性将R位重置,M位不会被重置,因为不知道该修改的页是否写回了磁盘。将会有以下几种情况

    1. class 0: 没有访问,没有修改

    2. class 1: 没有访问,已修改

    3. class 2: 被访问,没有修改

    4. class 3: 被访问,已修改

      NRU算法随机从类编号(class 0-3)最小的非空类中挑选一个页面置换,它的核心思想置换一个已修改的但未被访问的页比置换一个“干净”但频繁访问的页更好。

    FIFO页面置换算法
    • 原理:链表存储页面装载,发生缺页中断时,用链表头交换

    • 优点:低开销

    • 缺点:老的页面可能是频繁使用的,由于这个原因,该算法很少使用

    • 一个例子,假设这里有三个页框,上边的数字代表虚拟页,下边是页框里映射虚拟页的变化

    a78a3495474fe12a11a0e018533f7cd8.png

    第二次机会页面置换算法
    • 原理:该算法是在FIFO上修正置换频繁使用页面问题,当缺页中断发生时,取出最老的页面判断R标记,如果为0,立即置换,如果为1,则置为0并放入链表尾,并且更新它的载入时间,然后遍历后边的次老页面,直到找到一个满足条件的页面54c150c3c2e8e2f52255761a07a846b6.png

    • 缺点:需要在链表中移动页面

    时钟页面置换算法
    • 原理:解决第二次机会页面置换算法,需要在链表中移动页面。将链表以时钟的形式展示:如下图,一个指针指向最老的页表,缺页发生时,检查R标记为0直接置换,为1清除R标记,指针指向下一个页面0fd566056e0c1f4c7e58b856f29f3e13.png

    最近最少使用(LRU)
    • 原理:置换未使用时间最长的页面。用特殊硬件实现64位原子自增器C,每执行一条指令C原子自增1,并将该值设置访问的页表项,缺页发生时,检查页表中该计数值,最小的就是最近最少使用的页面

    • 缺点:需要硬件支持

    • 一个例子

      806f05771d2233215d60c91de653b12d.png

    软件模拟LRU(NFU)
    • 原理:每个页表项有一个计数器,每当时钟中断时,OS扫描内存中的所有页表,读取R标记(0/1)加到计数器上,等到缺页时,选择计数最低的置换

    • 缺点:计数器不会忘记计数值,假设一个页表在第一阶段频繁使用,但是第二阶段时不常使用,会使得在第二阶段时该页表依然具有很高的计数。第二阶段开始将会频繁使用的页表因为执行时间短,计数低,被不幸的置换出去

    • 优化:一个小优化可以使得NFU可以接近LRU的表现,每次将R位加到计数器时,先将计数器右移一位,然后将R值加到计数器左端而不是右端。这样可以让页表在不使用时指数方式衰减

    • 一个例子

      e09b10787b06caee1babef77ff8084ce.png

    • 和LUR的区别

    1. 上图的page3和5在e的时候,前两次都没有访问过,而在前两次之前的同一个时钟周期都被访问过,则根据LRU规则,3和5页面的计数值是一样的,所以会从中选择出一个页面置换;而NFU规则,会选择页面3置换,因为页面5在更早之前被访问过

    2. 第二个区别是,NFU的计数器有位数限制,本例为8,超过8个时钟周期,早期的记录便会丢失,如前9周期和前1000周期将会被视为一样,LRU不会

    工作集页面置换算法
    • 理论:大部分进程都表现出局部性访问特性。在一个阶段只会访问少部分的页,找出工作集,发生缺页时,找出不在工作集中的页置换出去

    • 假设用代表t时刻k次内存访问的工作集,那么工作集大小和选择k的关系,不会无限变大,因为进程不可能访问比它地址空间所能容纳页上限还多的页面

      04f1775ace49f29b26f96e26553cabdc.png

    • 作用:在多道程序设计系统中,经常把进程交换到磁盘上让其他进程运行,当进程恢复运行时,进程会不断的发生缺页直到它的工作集全部载入内存。利用工作集,可以在程序运行前,将工作集载入内存,就不会频繁发生缺页。

    • 实现

      • 最初设想:硬件实现,每进行一次内存访问,就左移一位,然后在最右边插入最新访问的页号,缺页发生时读出寄存器中的值,然后排序和去重,剩下的便是最近k次内存访问的工作集。维护该寄存器和处理缺页开销太大,导致实际没有使用这种方案

      • 替代方法:用时间来代替k次统计工作集,有一个定期的时钟中断用软件方法清除R位,发生中断时,会遍历页表项,判断R位结合最近上次访问时间来决定哪个页面置换出去具体算法如下

        1. 当R==1时,将实际时间写入页表项的上次使用时间

        2. 当R==0时,则该页作为置换候选项,计算实际时间和上次使用时间的间隔作为生存时间,然后与阈值时间对比,如果大于该阈值,则该页被置换

        3. 当R==0,且生存时间小于阈值,则把它留下来但是要记录上次使用时间的最小值

        4. 如果扫描完成都没有满足的,则选择R==0的生存时间最长的淘汰

        5. 如果没有R==0的则最好选择一个干净的页面淘汰

    示意图如下3b43eb7a278df7f520ef2c63d8f612a5.png

    工作集时钟置换算法
    • 原理:由于工作集页面置换算法,在扫描整个列表,才能确定被置换的页面,开销比较高,所以出现了工作集时钟页面置换算法,该算法会记录最近一次使用的时间,具体算法如图

      f3e5ad92a53d84eba9355e7414eadc54.png

    • 缺页时情况

    1. 如果R=1,说明在当前时钟滴答内被访问过,将R位置为0,指向下一个节点

    2. 如果R=0且M=0,判断当前实际时间-最近使用的时间是否大于阈值,如果大于,直接置换该页,否则指向下一个节点

    3. 如果M=1,考虑到此时置换当前页会调度磁盘可能导致进程切换,指向下一个节点

    扫描回到起点的情况

    1. 至少调度过一次写操作,只需移动指针寻找到第一个调度过写操作的页面(这个页面并不一定是需要第一个调度写操作的页面,因此磁盘为了优化,通常对写操作会重排序)

    2. 没有调度过写操作,随便选择一个干净的页面置换(扫描过程中要记录干净的页面),如果没有干净的页面,就置换当前指针指向的页面

    分页设计和实现问题
    局部分配和全局分配
    • 页面置换时,只能从进程自己分配的页框中选择置换,全局分配页面置换算法作用域是全局页框的。如下例子

      6214b663e7a99d61d5c6843b7349ad61.png

      当进程A发生缺页中断时,如果采用局部分配,那么A5将会被替换出去;如果采用全局分配,那么B3将会被替换出去

    • 通常全局分配比局部分配更好,因为局部分配算法,随着工作集增大,缺页会越来越频繁;但是当工作集减小时,局部算法又会浪费内存

    • 全局分配算法实现

    1. 检测工作集大小,工作集大小由“老化”位指出,但是不能防止颠簸,因为工作集大小可能在几微秒内变化

    2. 定期会确定运行的进程的数目为进程分配等额的内存,看似公平,但是通常进程需要的内存不同,比如为30Kb和300Kb分配同样的内存是不合理的

    3. 按进程大小的比例来分配内存,但是必须程序运行时动态更新,管理内存动态分配的一种方法是PFF(缺页中断率)

    4. 比较明智的方法是为进程分配一个最小的内存

    PFF(缺页中断率)

    用来管理动态为进程增加和减少页框。但是仅仅是控制分配集大小。下图是PFF示意图,A代表高缺页中断率,应该分配内存。B则代表有低中断率,有空余的内存。

    d4bcb7a2488f2b2ba2b6dfe726d3dd57.png

    负载控制
    • 问题:当所有进程组合的工作集需要的内存超过了内存的容量,那么会引起颠簸。一个现象是OS中所有进程PFF都很高,则表示所有的进程都需要额外内存,但是没有进程需要更少的内存,则该种情况所有进程都会颠簸

    • 解决办法:减少运行的进程。可以将进程交换出去,释放占用的页框,然后分配给其他颠簸的进程。交换进程到磁盘还要考虑,在多处理器系统中,过低的进程会浪费CPU周期,所以交换时不光考虑进程大小和分页率还要考虑进程的特性(计算密集型还是I/O密集型)

    分页大小
    • 内部碎片:程序的代码段、数据段和栈段在分页时,通常最后一页不能刚好装满,最后一页估计会浪费的空间。假设内存有n个段,页大小为p bytes,所以内存的内部碎片为

      23fb09115be2454e8ffcb02624097b85.png

    • 选择小页面的好处

    1. 减少内存碎片

    2. 减少内存浪费,假设页大小为32Kb,一个进程分为个阶段,每个阶段需要4Kb,那么进程有28Kb的空间都属于浪费的

    选择大页面的优点

    1. 页表更小

    2. 相对小页面会占用更少的TLB,TLB是非常昂贵的

    3. 在某些机器,进程切换时,会将页表载入硬件寄存器,小页面页表更大,因为花费时间比大页面长

    平衡:OS在系统中采用不同的页面大小,内核采用大页面,而用户空间程序采用小页面

    数学分析:假设进程平均大小为s bytes,页大小为p bytes,页表项大小为e bytes,需要的页表项空间为bc9a22550abb69126a6595e03a7abde1.png内部碎片为8d45486cf616899f386eb69154ec698d.png因此一个进程的空间开销为

    14350b77a54801ea5e3dc05e26cde348.png

    因为要求p的大小的最优值,对p求导,并令等式等于0

    cb11bbb8221e77ad9a59e185b88e8987.png

    p的解为a9c5366f14f9c7a726f888770552f5e3.png假设s为1MB,e为8bytes则p为4KB

    分离指令和数据空间
    • 存在问题:如果地址空间足够大,a的模型是ok的,但是如果地址空间小,就出现问题。程序空间示意图

      ec0572a76508c8a9ea94b818e76c9d7d.png

    • 一种解决方法

      PDP-11分离指令和数据空间,如上图的b,使用此种模型,链接器必须知道何时使用分离的I-space和D-space,因为数据被重定位到虚拟空间的0而不是在程序之后。它们有独立的页表

    • 现实应用

      虽然如今的普遍的x64架构应用64位地址,地址空间已经足够大。但是指令和数据空间分离还是有广泛的应用,比如CPU的L1缓存

    共享页
    • 存在问题:一个系统可能同时运行多个相同的程序或者几个用了相同库的程序,想象一下,即使相同的程序同时运行,系统要分配给它们独立的内存,但是程序的代码段是相同且不会改变的,如果能在同时运行时,内存只维护一个代码段,那就可以节省很多的空间;相同库也是一样的道理

    • 解决办法-利用指令和数据空间分离

      19ed1190e950e39aacef34f5dbd68ef9.png

      为了防止进程被换出而导致共享页被换出,但是全局扫描哪些页是共享的开销很高,因此需要一个特殊的数据结构来跟踪共享页

    • 数据页共享-利用写时复制技术

      Linux中当父进程创建子进程时,因为子进程要共享父进程的代码和数据,因此代码页和数据页都是进程共享的。但是此时共享的数据页都是只读状态,一旦进程对数据页发生写操作,就会陷入内核,系统便会重新拷贝一个副本,这时两个进程的页表分别指向该页的独立副本,页状态也被改为可读写。如下图的b

      490738f600296fa6366fe18d07ca98dc.png

    共享库
    • 传统静态链接

      程序编译时,在目标文件中调用但是没有定义的函数(未定义外部函数),链接器会查找外部库,找到了该函数的代码,然后加入到当前编译的可执行文件中存入磁盘。注意:这个可执行文件中是包含了外部库的方法的代码,如果有多个程序都用了该库,那么每个程序的可执行文件都包含库的代码,并且执行的时候也会有独立的内存存放这些相同的代码。

    • DLL(动态链接库)

      程序编译时,当遇到调用目标文件中没有定义的外部函数时,不在将库中方法的代码加入可执行文件,而是载入一个运行时可以与被调用库的函数绑定的存根例程。依赖系统和配置信息,共享库和程序一起加载到内存或者运行到第一次调用库函数时加载,如果其他程序已经加载那么就不需要再次加载了

    • 位置无关代码:解决库在不同程序调用载入时重定位的问题,如下图,如果进程1在载入共享库时,重定位了共享库的代码,那么进程2再调用时会导致问题,解决办法就是避免使用绝对地址,使用相对偏移量

      ed7e748658b399a4fe8abd1501690a22.png

    清除策略
    • 如果发生缺页时,系统有大量空闲内存时,此时分页系统工作在最佳状态

    • 实现:利用一个后台进程(分页守护进程)定期检查内存,当发现空闲内存较少时,会根据预定的算法置换一些页面出去。利用双指针的结构,当置换算法选择了页置换时,如果页是修改过的,那就写回磁盘,然后加入链表头;如果缺页发生时,就从链表的尾部取空闲页。假如,此时缺页是正好被分页守护进程回收的页且还没被覆盖,那么就直接恢复不用从磁盘载入

    虚拟内存控制

    通常虚拟内存对开发人员都是透明的,但是某些高级系统提供了虚拟内存的控制。主要是用来实现不同进程间共享内存

    • 用途:实现高性能消息传递系统,可以避免进程间消息传递时,数据从一个地址空间复制到另一个地址空间(开销很高)

    缺页处理流程
    1. 缺页发生时陷入内核,保存程序计数器

    2. 启动一个汇编例程保存通用寄存器和其他易失性信息,以免被系统破坏;

    3. OS发现缺页中断,尝试发现需要哪个虚拟页面,如果没有,则取出导致缺页执行的指令用软件分析,该指令在缺页时做什么操作

    4. 检查该地址是否有效且请求的操作与保护权限是否一致,如果不一致,则为非法访问,向进程发一个信号或者杀掉进程。如果有效且没有发生错误,则检查内存是否有空闲的页框,如果没有则执行页面置换算法

    5. 如果选出需要置换的页是修改过的脏页面,则需要先将修改写回磁盘,因为是阻塞操作,则发生上下文切换,挂起中断处理进程(OS内核进程),直到写回数据完成,写的过程中该页框会被设置为忙,防止其他进程操作

    6. 该页面干净后需要找到需要调入的页的磁盘地址,调入页面,该操作也是阻塞的,中断处理进程被挂起,直到磁盘发出中断,页表被更新,载入页面完成

    7. 恢复发生缺页中断指令以前的状态,程序计数器指回缺页的指令

    8. 调度引发缺页的进程,操作系统返回调用它的汇编例程

    9. 例程恢复寄存器和其他状态信息,返回用户空间继续执行,就像没有发生过缺页

    交换空间实现
    • 将整个进程按照程序text,data,statck全部映射到swap区中。每个进程分有固定大小的区,如图

      fd69c170aa3e8f41ec287cf696139d72.png

    • 进程开始时不映射到swap区,仅当发生交换时,将换出的页面写入swap区,但是需要在内存中建一个映射表(disk map)来映射换出的页

      1e3c1b3ce3b6b2fbdeccffa52a7fccda.png

    总结

        这一部分讲了虚拟内存的原理以及调度算法,下一篇文章将会学习高速缓存。

    展开全文
  • 慎入⊙﹏⊙,可以收藏了慢慢看~文章导读内存管理简介连续内存分配(首次适配,最佳适配,最差适配)非连续内存分配(分段,分页)虚拟内存技术页面置换算法(OPT,FIFO,LRU,Clock,LFU,工作集置换算法,...

    c52bb7068963a11b6137f7f4f4d74e49.png

    引言

    文章很长,慎入⊙﹏⊙,可以收藏了慢慢看~

    文章导读

    • 内存管理简介
    • 连续内存分配(首次适配,最佳适配,最差适配)
    • 非连续内存分配(分段,分页)
    • 虚拟内存技术
    • 页面置换算法(OPT,FIFO,LRU,Clock,LFU,工作集页置换算法,缺页率置换算法)

    一、内存管理简介

    1.1 管理内存的方法

    • 程序重定位
    • 分段
    • 分页
    • 虚拟内存
    • 按需分页虚拟内存

    实现依赖于硬件
    MMU(内存管理单元):硬件组件负责处理CPU的内存访问请求。

    1.2 地址空间&地址的生成

    物理地址空间
    硬件支持的地址空间(主存和磁盘)。

    逻辑地址空间
    一个运行的程序所拥有的内存范围。

    1.3 逻辑地址与物理地址的转换

    1.ALU需要某个逻辑地址的内存的内容。
    2.内存管理单元(MMU)寻找在逻辑地址和物理地址之间的映射;如果没有就从内存中找。
    3.控制器从总线发送在物理的内存内容的请求。
    4.内存发送物理地址内存给CPU 。

    具体步骤2是怎么建立逻辑地址和物理地址的映射,是如何查找的就是靠操作系统完成的。

    二、连续内存分配

    内存分配分为连续内存分配和非连续内存分配。首先看下连续内存分配,在内存分配的过程中会产生一些内存碎片,先了解一下内存碎片的概念。

    • 外部碎片:在分配单元间的未使用内存。
    • 内部碎片:在分配单元中的未使用内存。

    连续内存分配算法有首次适配最佳适配最差适配

    首次适配思路
    1.按地址排序的空闲块列表。
    2.分配需要找到一个合适的分区。
    3.重分配时需要检查,看是否自由分区能合并于相邻的空闲分区。

    优点:简单;易于产生更大空闲块。
    缺点:外部碎片;不确定性。

    最佳适配思路
    为了分配n字节,使用最小的比n大的可用空闲块。
    1.按尺寸排列的空闲块列表。
    2.分配需要寻找一个适合的分区。
    3.重分配需要搜索及合并于相邻的空闲分区。

    优点:当大部分分配是小尺寸时非常有效;比较简单。缺点:外部碎片;重分配慢;易产生很多没用的微小碎片。

    最差适配
    和最佳适配思路相反。为了分配n字节,使用最大可用空闲块,尽可能保证空闲块是最大的。1.按查村排列的空闲块列表。
    2.分配很快。
    3.重分配需要合并于相邻的空闲分区,调整空闲块列表。

    优点:每次分配是中等尺寸效果最好。
    缺点:重分配慢;外部碎片;易于破碎大的空闲块以至大分区无法被分配。

    可以看出,在连续的分配算法下难免会产生一下碎片,只要这些进程存在,这些碎片真的就无法利用吗?针对于这个问题,有两种解决内存碎片的思路:

    • 压缩式碎片整理
      将等待中的程序进行内存的挪动,减少外部碎片的出现。
    • 交互式碎片整理
      当运行程序需要更多的内存时,可以回收等待的程序的内存,将其挪到磁盘中(虚拟内存)。

    注:上述所说的内存都是物理内存。

    三、 非连续内存分配

    对于内存的连续分配,总是会有碎片的产生,内存利用率低,而且执行碎片整理的方法也都是有开销的。因此,非连续内存分配就能很好的解决碎片问题,也是操作系统中用的最多的内存分配方法。

    非连续内存分配基本算法有分段分页

    虽然非连续分配的好处挺多,但在实现上也有一些问题,比如如何建立虚拟地址和物理地址之间的转换?

    这就是后序要磕的分段和分页及映射表的设计。

    3.1 分段

    逻辑地址=s(段号),o(段内偏移)
    段表=s(段号),限制(段长),基址

    分段有两种实现方案:

    • 段寄存器+地址寄存器实现方案。
    • 单地址实现方案。

    简单看一下段寄存器+地址寄存器是如何找到逻辑地址对应的物理地址的。

    01e3c9be62acc24aa4a80f9db9e25751.png

    过程:
    1.首先判断逻辑地址的段号s是否超过段表寄存器中的段表长度,如果超过则会产生越界异常。
    2.如果不超过则去段表中找到对应的段号(段表始值+段号)。
    3.判断偏移o是否超过段长,不超过则找到对应的基址+偏移得到物理地址。
    4.这个物理地址就是要访问的主存地址了。

    在分段管理的过程中,段长不是固定的。如果是单地址实现方案则更加简单,没有段表寄存器。直接拿逻辑地址中的段号去段表中查,其他步骤和上述一样。

    3.2 分页

    绝大部分CPU采用分页机制。首先需要划分物理内存至固定大小的帧,划分逻辑地址空间至相同大小的页,然后需要借助页表和MMU/TLB。
    先看一下几个关键的概念~

    物理地址的寻址方式:
    物理地址是通过逻辑地址和页表换算出来的。
    f(帧号,F位,共2^F个帧),o(帧内偏移,S位,每帧2^S字节)
    物理地址=

    逻辑地址的寻址方式:
    页内偏移的大小=帧内偏移的大小。
    p(页号,P位,2^P个页),o(页内偏移,S位,每页有2^S字节)
    逻辑地址=

    页表
    每个运行的程序都有一个页表。属于程序运行状态,会动态变化。
    PTBR是页表基址寄存器。
    页表是页号和一些标志位及帧号的映射。

    下面这个思路是最容易想到的,也是有点小bug的路子。

    63cdf64c2150864f1ff9f84b5950f2dc.png

    其实大体上和分段是一样的,区别在于页号上可能会有标志位,比如判断权限,是否在内存中。因为逻辑地址可能大于物理地址,这些标志位将在后序的虚拟页式内存管理中讲解。

    如果按上述思路来实现,对于一个地址的转换,至少需要访问两次内存。一次是访问页表寻找帧号,一次是访问帧号对应的物理内存。如果计算机64位,一页为1024字节,就需要

    字节大小的页表。而且一个进程建立一个页表,内存是一定不够用的。对于空间的代价也是很大的,但是最理想的状态是让
    空间代价,时间开销最小

    为了解决这个问题,操作系统可以利用CPU的cache对页表做一个缓存,但是cache非常小,所以可以存一些经常访问的页表映射。

    页表的缓存
    MMU(内存管理单元)中有一个TLB对于页表的缓存,一般存一页数据,是近期访问的页帧转换表项的缓存(这也是后序页面置换算法的参考点)。key->p;value->f。
    注:p是页号,f是帧号,后序都用这两个字母表示。

    a899b24bf751fc85c3fdc8e21e791029.png

    如果TLB命中,物理页号可以很快被获取;如果TLB未命中,对应的表项被更新到TLB中。

    多级页表
    解决了时间的开销,再看看空间的代价。由于逻辑地址空间很大,所以需要很大的页表,为了使页表所占的空间变小,所以可以使用多级页表。

    可以将页表中的页号细化,分为p1,p2。每级页表都存储下一级页表的索引,n级页表一次类推。下面是二级页表的寻址过程:

    b1aba12250b371d3289c56ef86574553.png

    3.3 分页和分段的区别

    (1)页是信息的物理单位,分页是为了减少内存碎片,提高内存利用率。分页仅仅是由于系统管理的需要,而不是用户的需要。段是信息的逻辑单位,它包含一组意义相对完整的信息。分段的目的是为了能更好地满足用户的需要

    (2)页的大小固定且由系统确定,逻辑地址的划分是由寄存器实现的,因而一个系统只能有一种大小的页面。段的长度不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时,根据信息的性质来划分

    (3)分页的作业地址空间是一维的,即单一的线性地址空间,程序员只需要利用一个记忆符,即可表示一个地址。分段的作业地址空间是二维的,程序员在标识一个地址时,既需给出段名又需给出段内地址

    此处引用操作系统第六篇【存储器管理】

    四、 虚拟内存

    当前内存不够进程分配时,操作系统会怎么解决。此时,虚存技术就很关键,在虚存技术出来前,用得最多的是覆盖技术和交换技术。覆盖技术
    在较小的内存中运行较大的内存,将没有调用关系的程序放在一个分区。

    48632c12deeb60c33d4d9579e1e98be6.png

    B,D,E没有调用关系,也就是说,在调用B时,不可能同时调用D或E,所以共享一个覆盖区。早期用这个技术来节约内存。
    缺点:有程序员来把一个大程序划分位若干个功能莫尽快,确定模块之间的覆盖关系,增加编程复杂度;覆盖模块从外存装入内存,是以时间换空间。

    交换技术
    将暂时不能运行的程序送到外存,从而获得空闲内存空间。粒度是一个程序,需要操作系统支持,对程序员透明。

    缺点:以进程作为交换单位,需要把进程整个地址空间都换进换出,增加的处理器的开销。

    覆盖与交换的比较

    (1)覆盖只能发生在那些相互之间没有调用关系的程序模块之间。
    (2)交换技术是在以内存中的程序大小为单位来进行的,一般一页以上。不需要程序员给出各个模块之间的逻辑覆盖结构。

    覆盖和交换都有它的局限性,覆盖过于麻烦,而交换的粒度太大,以程序为单位。可以不可以把暂时不用的程序模块放到硬盘,把这一切都交给操作系统赋予特定的算法去完成呢?这就需要下面的虚存技术。

    虚拟内存技术

    把程序中的一部分放入到内存中,对程序员透明。可以根据内存的使用情况,动态的对程序部分内容在内存与外存中进行交换。

    首先了解一下CPU的特性,程序的局部性原理:在程序执行过程中的一个较短时期,所有执行的指令地址和指令的操作地址分别局限于一定区域。

    虚存技术的特征
    1.大的用户空间,通过把物理内存与外存相结合,提供给用户的虚拟内存空间通常大于实际内存空间,实现二者分离。
    2.部分交换,调入调出都是对部分虚拟地址空间进行。
    3.不连续性,物理内存分配的不连续,虚拟地址空间是哦那个的不连续

    虚存技术的实现-虚拟页式内存管理

    虚拟页式内存管理技术=页式内存管理+请求调页+页面置换功能。基本思路
    1.当一个用户程序要调入内存运行时,不是将该程序的所有页面都装入内存,而是只装入部分的页面,就可以启动程序。
    2.在运行的过程中,如果发现要运行的程序或要访问的数据不再内存,则向系统发出缺页中断请求,系统在处理这个中断请求时,将外存中响应的页面调入内存,是程序能够继续运行。

    页表=逻辑页号+访问位+修改位+保护位+驻留位+物理页帧号

    下面挨个看看每个特征位:

    驻留位
    表示该页在内存还是外存。

    保护位
    允许对该页做何种类型的访问(只读,可读写,可执行等)。

    修改位
    表明此页是否被修改过。如果被修改过就会导致内存中和硬盘中的数据不一致,所以换入换出时需要保证数据的一致性。当系统回收物理页面时,根据此位来决定是否把它的内容写回外存。

    访问位
    该页面是否被访问过,用于页面置换算法。

    有了这些,当页表中某个页号没有对应帧号时,会引发缺页中断,我们大概可以推测出缺页中断的流程

    69c3f1d2a7e8941648b1737af2f7a3ac.png
    图片来源于网络

    1)如果在内存中有空闲的物理页面,则分配一物理页帧f,然后转4);否则转2)。
    2)采用某种页面置换算法,选择一个将被替换的物理页帧f,如果对应的逻辑页位q,若在该页在内存中修改过,则需将其写回外存。
    3)对q所对应的页表向进行修改,驻留位=0
    4)将需要访问的页p转入到物理页面f中。
    5)修改p所对应的页表项的内容,驻留位=1,把物理页帧置f。
    6)重新运行被中断的指令。

    那么,没有被映射的页是怎么被存储在硬盘的呢?
    一般放在交换空间,以特殊的格式保存。代码段->映射到可执行的二进制文件。动态加载的共享库程序段->映射到动态调用的库文件。
    其他段->可能被映射到交换文件。

    还有一个问题,如果频繁发生缺页异常,进行页面置换,就会增加操作系统的开销。这里需要引入一个指标来描述虚存技术的性能-EAT(Effective Memory Access Time)。

    EAT(使用有效存储器访问时间)=访存时间*页表命中率+缺页中断处理时间*缺页概率
    从公式可以看出,缺页率越大,EAT越小,性能越差。基于程序的局部性特点,其实缺页率还是比较小的,这个其实跟程序代码的书写也有关系......

    五、页面置换算法

    采用什么样的置换算法对于缺页率的控制还是很关键的~

    置换算法分为局部全局页面置换算法。

    局部页面置换算法:

    • 最优页面置换算法(OPT)
    • 先进先出算法(FIFO)
    • 最近最久未使用(LRU)
    • 时钟页面置换算法(Clock)
    • 最不常用算法(LFU)

    全局页面置换算法:

    • 工作集页置换算法
    • 缺页率置换算法

    5.1 局部页面置换算法

    最优页面置换算法(OPT)

    思路:把将来最长时间不需要的页面置换。
    该算法无法实现,但是会利用该算法作为参考,评价其他算法。

    bbd023d42c03f58207569b170833d61d.png

    如上图所示,当时间=4时,需要置换一页,此时看a,b,c,d在将来什么时候会被访问。a=6,b=5,c=7,d=8,因此置换d。

    先进先出算法(FIFO)

    思路:将内存中驻留时间最长的页面置换。其实就是维护一个队列,每次置换队头那页。
    性能较差,调初的页面可能是经常要访问的页面,并且有Belady现象(类似于逆向优化的现,增加内存的大小,很难降低缺页率)。FIFO很少单独使。

    Belady的产生原因
    算法置换特征与程序访问内存的动态特征是矛盾的,所以置换出去的页面不一定是进程会访问的。

    最近最久未使用(LRU)

    思路:选择最久未使用的那个页面置换。是对最优页面置换算法的近似,根据过去推测未来。

    操作系统具体可以用以下方法实现:

    • 维护一个链表,刚使用的放表头,最久未使用的作为尾节点。每次访问内存时,找到相应的页面,把它移到表头。发生缺页中断后,淘汰链表末尾的页面。
    • 设置一个活动栈,访问页面时,将次页号压入栈顶,将栈内相同的页号都删掉。每次总是置换栈底元素。

    虽然这样会让缺页的次数比较少,但实现效率不高。

    时钟置换算法(Clock)

    利用页表中的访问位(Access Bit),初始化为0,每次访问后都会置为1,操作系统又定期将其变为0。

    思路:当发生缺页中断时,若当前访问位==1则置0,指针向下走,直到遇到访问位==0的页面就进行置换;若当前访问位==0则置换该页,然后指针指向下一个地址。在这个过程中,指针类似于时钟往一个方向走。
    下图就是对于时钟置换完整的复现过程。

    96e3020d9b441ad8e11e73d3318ed22b.png

    一开始,a,b,c,d在内存中,访问位初始化为0。每次访问,更新访问位,直到时间=5,第一次引发缺页中断,将当前访问位置0并向下走,遍历完回来,发现页面a访问位==0则替换a。后面的情况以此类推~
    只有在发生缺页中断时,指针才会向下走。

    二次机会法

    二次机会法是对时钟置换算法的改进。
    在置换的过程中,每次置换都需要先将当前页写回到磁盘。如果在内存中只是读操作,是不是可以减少这个写回的代价呢?

    利用Dirty Bit(修改位),表示该页在内存中是否被修改过来指导置换。当内存中某个页被修改后,dirty bit会被置1。

    思路:每次指针经过时,会将访问位置0,如果访问位已经为0,则将Dirty Bit置0。如果dirty bit已经为0,则直接置换该页。尽可能的让脏页在一次时钟中保留,也就是尽可能置换只读的页。

    最不常用法(LFU)

    思路:当缺页中断发生时,将访问次数最少的那个页面置换。

    缺点:一个页面在一开始频繁访问,后续就不访问了。会导致内存利用率不高。

    LRU,FIFO,Clock总结

    • LRU和FIFO本质上都是先进先出的思路,但LRU是针对页面最近访问时间来排序,每次对内存的访问都要排序而FIFO不需要。
    • 当内存中所有的页面都没被访问过时,LRU就退化为FIFO。
    • LRU算法性能好,但系统开销较大;FIFO系统开销小,但可能会发生Belady。而Clock算法就是他们的折衷,每次页面访问时不用调整页面在链表的顺序,而是用寄存器中原生的标记,等发生缺页中断时再维护链表。Clock性能和LRU差不多,但对于曾经访问过的页面不能记住他们准确的位置。

    5.2 全局页面置换算法

    局部页面置换算法的问题

    操作系统给每个进程分配物理页帧时应该是有所顾虑的。物理页帧的大小会对最终的页面置换算法的缺页率有较大的影响。程序在运行的过程中,对内存的读取一定是动态的,对物理页帧的需求也是变化的,如果按固定的页帧来算,势必会影响程序的灵活性。如何按照程序的需求动态的分配物理页帧呢?下面需要先引入几个概念。

    工作集模型

    如果程序对内存的访问不满足局部性原理,则不管用什么置换算法,一定会导致缺页中断;如果局部性成立,对它进行定量的分析就可以用工作集模型。个人理解工作集模型就是根据窗口大小,确定工作集,描述内存访问规律的模型

    工作集

    单位时间内,访问的所有页面的集合。体现程序执行过程中,对页面访问的属性。

    常驻集

    在当前时刻,进程实际驻留在内存当中的页面集合。

    工作集页置换算法

    思路:随着时间和程序的运行,将不在工作集的窗口范围内的页面丢弃。

    缺页率页面置换算法

    工作集的窗口是固定的,能不能让它灵活的变化呢?

    思路:若缺页率过高,则增加工作集,来分配更多的物理页面;若缺页率过低,则减少工作集。

    设置一个时间段,当前缺页时间-上次缺页时间>时间段,则认为缺页频率低,可以减少给当前进程分配的页帧,从工作集中移除未在这个区间内访问的页面;当前缺页时间-上次缺页时间<时间段,则认为缺页率高,增加缺失的页面。

    5.3 总结

    影响缺页率的因素

    • 页面置换算法
    • 分配给进程的物理页面数目
    • 页面本身的大小
    • 程序的编写方法

    局部和全局置换算法比较
    (1)使用场景:如果程序对内存的需求是有规律的,则全局页面置换算法更有优势。
    (2)执行时机:全局页面置换算法根据工作集,中断间隔来动态调整页面并且只有的中断时才会置换;局部页面置换算法是在当前内存满了才会执行。

    5.4 抖动问题

    当进程造成很多缺页中断时,需要频繁地在内存与外存之间替换页面,从而使进程的运行速度变慢,这种状态就是抖动。

    当驻留内存的进程数增加,分配给每个进程的物理页面数不断减小,缺页率不断上升。所以OS要选一个适当的进程数目和进程需要的帧数,以便在并发水平和缺页率之间达到一个平衡,提高CPU的利用率。

    X轴表示当前有N个程序,Y轴表示CPU的利用率。

    957c057bfd33a2122ab59a2d05f05fa2.png
    图片来源于网络

    深色(紫色)的曲线说明当程序越来越多,对CPU的利用率先增大;超过峰值后,则会频繁出现抖动的现象,以至于利用率不高。 浅色(蓝色)曲线表示平均缺页时间/缺页服务时间比值随程序的增加而减少。这个比值越大则说明操作系统进行页面置换,换入换出的时间越少,程序运行的时间越多。当其约为1时,就是比较好的平衡点,并发量比较不错,CPU利用率也比较高。

    参考文章:操作系统第六篇【存储器管理】

    如果看得不过瘾,可以戳:操作系统(三)—进程管理最后,如果喜欢我的文章,欢迎关注我的专栏~

    展开全文
  • 书上列举页面保护属性---PAGE-EXECUTE PAGEE_READ 。。。 等。 在MSDN上还看到页面状态(state)一说,:MEM_COMMIT MEM_FREE MEM_RESERVE 这三种 在MSDN上看到有一种说法,一些页面类型(type):MEM_IMAGE MEM_...
  • 此时应将缺页的进程阻塞(调完成唤醒),若内存中有空闲块,则分配一个块,将要调入的装入该块,并修改页表中的相应页表项,若此时内存中没有空闲块,则要淘汰某(若被淘汰内存期间被修改过,则要将其写回...

    013bff04d7fefeb85832fc1825b6c305.png
    写在前面:我是【程序员宝藏】的宝藏派发员,致力于创作原创干货。我热爱技术、热爱开源与分享,创作的【计算机基础面试问题】系列文章和【计算机基础主干知识】系列文章广受好评!后期会创作更多优质原创系列文章!如果您对计算机基础知识、编程等感兴趣,可以关注我,我们一起成长!本人力荐:如果觉得知乎排版不够美观,欢迎来我的个人原创公zong号【程序员宝藏】(号如其名,诚不欺你!)查看有红色重点标记和排版美观的全系列文章(不细你来找我要红包
    好多同学问我要pdf版,我干脆把全部文章都整理成了pdf直接打印版,在公zong号后台回复关键字【宝藏】即可免费带回家慢慢看觉得有收获?希望老铁们来个三连击(点赞、评论、收藏),让更多的人看到这篇文章!顺便也激励下我,嘿嘿

    正文开始

    • 正文开始
      • 1.前导知识简述
      • 2.页式虚拟内存
      • 3.段式虚拟内存
      • 4.段页式虚拟内存

    1.前导知识简述

    ❝ 【问】:为什么要进行内存管理? 答:在单道批处理系统阶段,一个系统在一个时间段内只执行一个程序,内存的分配极其简单,即仅分配给当前运行的进程。引入多道程序的并发执行后,进程之间共享的不仅仅是处理机,还有主存储器。然而,共享主存会形成一些特殊的挑战(越界、缺页等)。若不对内存进行管理,则容易导致内存数据的混乱,以至于限制进程的并发执行。因此,为了更好地支持多道程序并发执行,必须进行内存管理。

    链接和装入

    创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序,通常需要以下几个步骤:

    • 编译。由编译程序将用户源代码编译成若干目标模块。
    • 链接。由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起,形成一个完整的装入模块。
    • 装入。由装入程序将装入模块装入内存运行。

    0bd09836abd1de0527742be1f512aa18.png

    程序的链接有以下三种方式:

    1. 静态链接:程序运行前,先将各目标模块及他们所需要的库函数链接成一个完整的可执行程序,以后不再拆开。
    2. 装入时动态链接:在装入时,边装入边链接。
    3. 运行时动态链接:对某些目标模块的链接,是在程序执行中需要该目标模块时才进行的。其优点是便于修改和更新,便于实现对目标模块的共享。

    程序的装入有以下三种方式:

    1. 绝对装入:单道程序环境下,逻辑地址和物理地址完全相同,不需要地址变换。
    2. 静态重定位:装入时一次性将逻辑地址转换为物理地址(重定位)
    3. 动态重定位:运行时才把逻辑地址转换为物理地址,适合程序在内存中会发生移动的情况。
    ❝ 【问】:覆盖与交换? 答:覆盖与交换技术是用来扩充内存的两种方法。 覆盖的【基本思想】如下:由于程序运行时并非任何时候都要访问程序及数据的各个部分(尤其是大程序),因此可把用户空间分成一个固定区和若干覆盖区。将经常活跃的部分放在固定区,其余部分按调用关系分段。首先将那些即将要访问的段放入覆盖区,其他段放在外存中,在需要调用前,系统再将其调入覆盖区,替换覆盖区中原有的段。覆盖技术的特点是,打破了必须将一个进程的全部信息装入主存后才能运行的限制,但当同时运行程序的代码量大于主存时仍不能运行,此外,内存中能够更新的地方只有覆盖区的段,不在覆盖区中的段会常驻内存。 交换(对换)的【基本思想】是,把处于等待状态(或在CPU 调度原则下被剥夺运行权利)的程序从内存移到辅存,把内存空间腾出来,这一过程又称换出;把准备好竞争CPU 运行的程序从辅存移到内存,这一过程又称换入。中级调度采用的就是交换技术。 【区别】交换技术主要在不同进程(或作业)之间进行,而覆盖则用于同一个程序或进程中。由于覆盖技术要求给出程序段之间的覆盖结构,使得其对用户和程序员不透明,所以对于主存无法存放用户程序的矛盾,现代操作系统是通过虚拟内存技术来解决的,覆盖技术则已成为历史;而交换技术在现代操作系统中仍具有较强的生命力。

    连续分配管理方式

    1. 单一连续分配
    2. 固定分区分配
    3. 动态分区分配

    50db0a47c7042c8b587cca4dce52f176.png

    非连续分配方式

    固定分区会产生内部碎片,动态分区会产生外部碎片,这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免碎片的产生,这就引入了分页的思想:把主存空间划分为大小相等且固定的块,块相对较小,作为主存的基本单位。每个进程也以块为单位进行划分,进程在执行时,以块为单位逐个申请主存中的块空间。

    1. 基本分页存储管理方式
    2. 基本分段存储管理方式
    3. 基本段页式管理方式

    2.页式虚拟内存

    基于局部性原理,在程序装入时,将程序的一部分装入内存,而将其余部分留在外存,就可 启动程序执行。在程序执行过程中,当所访问的信息不在内存时,由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面,操作系统将内存中暂时不使用的内容换出到外存上,从而腾出空间存放将要调入内存的信息。这样,系统好像为用户提供了一个比实际内存大得多的存储器,称为虚拟存储器。

    ❝ 【局部性原理】:快表、页高速缓存及虚拟内存技术从广义上讲,都属于高速缓存技术。这个技术所依赖的原理就是局部性原理。 局部性原理表现在以下两个方面:1) 时间局部性。程序中的某条指令一旦执行,不久后该指令可能再次执行;某数据被访问过,不久后该数据可能再次被访问。产生时间局部性的典型原因是程序中存在着大量的循环操作。2) 空间局部性。一旦程序访问了某个存储单元,在不久后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围之内,因为指令通常是顺序存放、顺序执行的,数据也一般是以向量、数组、表等形式簇聚存储的。 时间局部性通过将近来使用的指令和数据保存到高速缓冲存储器中,并使用高速缓存的层次 结构实现。空间局部性通常使用较大的高速缓存,并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上建立了“内存-外存”的两级存储器结构,利用局部性原理实现高速缓存。

    请求分页系统建立在基本分页系统基础之上,为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。

    为了实现请求分页,系统必须提供一定的硬件支持。除了需要一定容量的内存及外存的计算 机系统,还需要有页表机制、缺页中断机构和地址变换机构。

    页表机制

    请求分页系统的页表机制不同于基本分页系统,请求分页系统在一个作业运行之前不要求全部一次性调入内存,因此在作业的运行过程中,必然会出现要访问的页面不在内存中的情况,如何发现和处理这种情况是请求分页系统必须解决的两个基本问题。为此,在请求页表项中增加了4 个字段,如图所示:

    fb748050b0a1aeddc697fd2cb649d301.png

    缺页中断机构

    在请求分页系统中,匈当所要访问的页面不在内存中时,便产生一个缺页中断,请求操作系 统将所缺的页调入内存。此时应将缺页的进程阻塞(调页完成唤醒),若内存中有空闲块,则分配一个块,将要调入的页装入该块,并修改页表中的相应页表项,若此时内存中没有空闲块,则要淘汰某页(若被淘汰页在内存期间被修改过,则要将其写回外存)。

    ❝ 【注意】:缺页中断作为中断,同样要经历诸如保护CPU 环境、分析中断原因、转入缺页中断处理程序、恢复CPU 环境等几个步骤。但与一般的中断相比,它有以下两个明显的【区别】: 1)在指令执行期间而非一条指令执行完后产生和处理中断信号,属于内部中断。 2)一条指令在执行期间,可能产生多次缺页中断。

    地址变换机构

    一张流程图一目了然:

    0fc235666b7a6396dd3a86721b106b1f.png

    页面置换算法

    1. 最佳(OPT) 置换算法

    最佳(Optimal, 0PT) 置换算法选择的被淘汰页面是以后永不使用的页面,或是在最长时间内不再被访问的页面,以便保证获得最低的缺页率。然而,由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的,因而该算法无法实现。

    1. 先进先出(FIFO) 页面置换算法

    优先淘汰最早进入内存的页面,即在内存中驻留时间最久的页面。该算法实现简单,只需把 调入内存的页面根据先后次序链接成队列,设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应,因为在进程中,有的页面经常被访问。

    ❝ FIFO 算法还会产生所分配的物理块数增大而页故障数不减反增的异常现象,称为Belady 异常。只有FIFO 算法可能出现Belady 异常, LRU 和OPT 算法永远不会出现Belady 异常。
    1. 最近最久未使用(LRU)置换算法

    选择最近最长时间未访问过的页面予以淘汰,它认为过去一段时间内未访问过的页面,在最 近的将来可能也不会被访问。该算法为每个页面设置一个访问字段,来记录页面自上次被访问以来所经历的时间,淘汰页面时选择现有页面中值最大的予以淘汰。

    ❝ LRU 算法的性能较好,但需要寄存器和栈的硬件支持。LRU 是堆栈类的算法。理论上可以 证明,堆栈类算法不可能出现Belady 异常。FIFO 算法基于队列实现,不是堆栈类算法。
    1. 时钟(CLOCK) 置换算法

    简单的CLOCK 算法给每帧关联一个附加位,称为使用位。当某页首次装入主存时,将该帧 的使用位设置为1; 当该页随后再被访问到时,其使用位也被置为1 。对于页替换算法,用于替换的候选帧集合可视为一个循环缓冲区,并有一个指针与之相关联。当某一页被替换时,该指针被设置成指向缓冲区中的下一帧。当需要替换一页时,操作系统扫描缓冲区,以查找使用位被置为0 的一帧。每当遇到一个使用位为1 的帧时,操作系统就将该位重新置为0; 若在这个过程开始时,缓冲区中所有帧的使用位均为0, 则选择遇到的第一个帧替换;若所有帧的使用位均为1,则指针在缓冲区中完整地循环一周,把所有使用位都置为0, 并停留在最初的位置上,替换该帧中的页。由于该算法循环检查各页面的情况,因此称CLOCK算法,又称最近未用(Not Recently Used, NRU) 算法。

    在使用位的基础上再增加一个修改位,则得到改进型CLOCK 置换算法。这样,每帧都处于以下4种情况之一: 1)最近未被访问,也未被修改(u= 0, m = 0) 。 2)最近被访问,但未被修改(u=l,m=0) 。 3)最近未被访问,但被修改(u=0,m= 1) 。 4)最近被访问,被修改(u=l,m=l)

    算法执行步骤如下:

    1. 从指针的当前位置开始,扫描帧缓冲区。在这次扫描过程中,对使用位不做任何修改。选择遇到的第一个帧(u = 0, m = 0) 用于替换。
    2. 若第1) 步失败,则重新扫描,查找(u=0,m= 1) 的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中,对每个跳过的帧,把它的使用位设置成0 。
    3. 若第2) 步失败,则指针将回到它的最初位置,且集合中所有帧的使用位均为0 。重复第
    4. 步,并且若有必要,重复第2) 步,以便可以找到供替换的帧。
    ❝ 【注意】:改进型CLOCK 算法优于简单CLOCK 算法的地方在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回,因而这样做会节省时间。

    ❝ 【抖动】:在页面置换过程中,一种最糟糕的情形是,刚刚换出的页面马上又要换入主存,刚刚换入的页面马上又要换出主存,这种频繁的页面调度行为称为抖动或颠簸。若一个进程在换页上用的时间多于执行时间,则这个进程就在颠簸。频繁发生缺页中断(抖动)的主要原因是,某个进程频繁访问的页面数目高于可用的物理页帧数目。

    ❝ 虚拟内存是怎么解决问题的?会带来什么问题? 答:虚拟内存使用外存上的空间来扩充内存空间,通过一定的换入/换出,使得整个系统在逻辑上能够使用一个远远超出其物理内存大小的内存容量。因为虚拟内存技术调换页面时需要访问外存,会导致平均访存时间增加,若使用了不合适的替换算法,则会大大降低系统性能。

    ❝ 【问】:多级页表解决了什么问题?又会带来什么问题? 答:多级页表解决了当逻辑地址空间过大时,页表的长度会大大增加的问题。多级页表是为了节省空间。(单级页表为了随机访问必须连续存储,如果虚拟内存空间很大,就需要很多页表项,就需要很大的连续内存空间【你能想象页表比分配的页(“运行页”)还多吗?】;但是多级页表不需要,最开始只需一页。) 【问题】:而采用多级页表时,一次访盘需要多次访问内存甚至磁盘,会大大增加一次访存的时间。

    3.段式虚拟内存

    段式虚拟存储器中的段是按程序的逻辑结构划分的,各个段的长度因程序而异。把虚拟地址 分为两部分:段号和段内地址。虚拟地址到实地址之间的变换是由段表来实现的。段表是程序的逻辑段和在主存中存放位置的对照表。段表的每行记录与某个段对应的段号、装入位、段起点和段长等信息。由于段的长度可变,所以段表中要给出各段的起始地址与段的长度。

    cf6943f26d2cef131061b18b9920c673.png

    段式虚拟存储器的优点是,段的分界与程序的自然分界相对应,因而具有逻辑独立性,使得它易于编译、管理、修改和保护,也便于多道程序的共享;缺点是因为段长度可变,分配空 间不便,容易在段间留下碎片,不好利用,造成浪费。

    64b6710d93f06b1eb09b36d780ee6ace.png

    4.段页式虚拟内存

    把程序按逻辑结构分段,每段再划分为固定大小的页,主存空间也划分为大小相等的页,程 序对主存的调入、调出仍以页为基本传送单位,这样的虚拟存储器称为段页式虚拟存储器。在段页式虚拟存储器中,每个程序对应一个段表,每段对应一个页表,段的长度必须是页长的整数倍,段的起点必须是某一页的起点。

    虚地址分为段号、段内页号、页内地址三部分。CPU 根据虚地址访存时,首先根据段号得到段表地址;然后从段表中取出该段的页表起始地址,与虚地址段内页号合成,得到页表地址;最后从页表中取出实页号,与页内地址拼接形成主存实地址。

    段页式虚拟存储器的优点是,兼具页式和段式虚拟存储器的优点,可以按段实现共享和保护。缺点是在地址变换过程中需要两次查表,系统开销较大。

    不要忘记去我的个人原创公zong号【程序员宝藏】----专注于计算机基础、编程、分享,获取【宝藏】哦!

    b5f55f2a01a9f2818f085b2254f34d64.png
    作为过来人,有考研的小伙伴可以加我好友(公zong号有二维码,备注【考研】),免费解答相关问题,做你的知心大哥哥!我们一研为定觉得有收获?希望老铁们来个三连击(点赞、评论、收藏),让更多的人看到这篇文章!顺便也激励下我,嘿嘿!
    展开全文
  • 修改牺牲对应的PTE,将地址字段指向虚拟在磁盘的位置,说明该虚拟未被缓存 内核从磁盘复制目标虚拟到该牺牲中,并修改目标虚拟对应的PTE,将地址字段指向牺牲的物理内存地址 缺页异常返回到导致缺页...

    视频地址:

    【精校中英字幕】2015 CMU 15-213 CSAPP 深入理解计算机系统 课程视频_哔哩哔哩 (゜-゜)つロ 干杯~-bilibiliwww.bilibili.com
    e43f3b60d94371951f4de6d18f497a8f.png

    课件地址:

    http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/lectures/17-vm-concepts.pdfwww.cs.cmu.edu

    对应于书中的9.1~9.6。


    • 虚拟内存被组织为存放在磁盘上的N个连续字节大小的单元数组,每个字节都有一个唯一的虚拟地址,而该数组的内容被缓存在主存中。(所以虚拟内存本质上是磁盘上的字节数组,该数组的索引就是虚拟地址,且主存作为该数组的缓存。)
    • CPU通过虚拟内存地址进行访问,会首先确定对应的PTE,然后通过PTE的状态访问对应的物理页。
    • 加载器不会将磁盘内容复制到内存,而是为可执行目标文件分配虚拟页,初始化页表。实际的加载工作由内核完成。
    • 只有分配页面了,CPU才会产生该页的虚拟地址
    • MMU负责地址翻译和访问权限检查
    • 页表和TLB中只需要保存PPN。

    2288438fde6b1bb4c2711cdbf3ab4a5c.png

    进程之间相互共享CPU和主存资源,但是如果太多进程需要太多内存资源,可能就会使得进程无法运行,并且当进程写了另一个进程使用的内存时,会造成错误。所以为了更好管理内存,现代系统提供了一种对主存的抽闲概念,称为虚拟内存(Virtual Memory),它完美交互了硬件异常、硬件地址翻译、主存、磁盘文件和内核软件,为每个进程都提供了一个大的、一致的私有的地址空间

    1 地址空间

    地址空间(Address Space)是一个非负整数地址的有序集合

    ,如果地址空间中的整数是连续的,则称为
    线性地址空间(Linear Address Space)

    计算机系统的主存被组织成一个由M个字节大小的单元组成的数组,每个字节都有一个唯一的物理地址(Physical Address),并且物理地址是连续的。由此就构成了一个物理地址空间(Physical Address Space),对应于系统中物理内存的M个字节。CPU可以通过物理地址来访问内存,这种方式称为物理寻址(Physical Addressing),再将获得的数据字保存到寄存器中。

    55e24cc8d04126f7b6e85bf0c21d7b3b.png

    现代系统会尝试虚拟化资源,提供资源不同的视图,通常会呈现某种抽象或某种不同的资源视图,你可以通过介入对该资源的访问过程来实现。所以当你有一些资源,并且想要进行虚拟化时,可以通过干预或介入对该资源的访问过程来实现,一单你拦截了访问的过程,你就能用任何你想要的方式来处理它,就能有很多方法来改变那个资源对用户的视图。比如访问磁盘特定的扇区,需要制定柱面、磁道和盘面,但是磁盘控制器将磁盘抽象成一系列逻辑块的形式,使得内核能直接直接制定逻辑块号来访问磁盘,这就是一种虚拟化技术,它通过拦截来自内核的读写请求来呈现出这种视图,将内核发送的逻辑块号转化为实际的物理地址。

    对于主存存储器资源也可以通过虚拟内存提供另一种不同的视图。现代CPU从一个有

    个地址的地址空间中生成
    虚拟地址(Virtual Address),该地址空间称为虚拟地址空间(Virtual Address Space),虚拟地址空间的大小由表示最大虚拟地址所需的位数
    来确定,现代系统支持32位或64位的虚拟地址空间。CPU会使用虚拟地址来访问主存,称为
    虚拟寻址(Virtual Addressing),需要首先通过地址翻译(Address Translation)将虚拟地址转换为对应的物理地址,再通过物理地址来访问内存。而地址翻译类似于异常处理(软硬结合),需要CPU上的内存管理单元(Memory Management Unit,MMU),以及内存中由操作系统管理的查询表来动态翻译虚拟内存。所以通过MMU来控制对内存的读写,达到对内存进行虚拟化的目的。

    eb88a9109ca15b7fbb2240cb2d1b6e87.png

    通常虚拟地址空间会比物理地址空间大很多,物理地址空间对应于系统中实际拥有的DRAM容量,对于系统上运行的所有进程,虚拟地址空间是相同的。

    为什么要增加MMU来对内存进行抽象呢?主要原因在于:

    • 虚拟内存将DRAM内存作为磁盘上实际数据的高速缓存,即我们可以在主存访问磁盘大小的空间,而主存只保存活动区域,根据需要在磁盘和主存之间来回传送数据,使得进程可以得到更大的地址空间,并且更有效地利用主存资源。
    • 虚拟内存为每个进程提供一致的虚拟地址空间,代码和数据总是加载到固定的地址,堆栈位于用户课件地址空间的顶部等等,但是实际上与那些虚拟地址相对应的内容分布在整个主存储器中,所以通过使用虚拟内存可以简化内存的管理。
    • 虚拟内存保护每个进程的地址空间不会被别的进程破坏。

    2 虚拟内存的作用

    2.1 虚拟内存作为缓存的工具

    2.1.1 基本概念

    虚拟内存被组织为存放在磁盘上的N个连续字节大小的单元数组,每个字节都有一个唯一的虚拟地址,而该数组的内容被缓存在主存中。(所以虚拟内存本质上是磁盘上的字节数组,该数组的索引就是虚拟地址,且主存作为该数组的缓存。)

    缓存可以参考之前的内容

    虚拟内存是在20世纪60年代早期发明的,早于SRAM高速缓存之前,所以即使两者使用相似的概念,术语也存在很大的不同。在虚拟内存中,数据块被称为页(Page),磁盘和内存之间传送给页称为交换(Swapping)页面调度(Paging)。所有现代系统都使用按序页面调度(Demand Paging)的方式,一直等待直到发生不命中时,才换页面。

    虚拟内存之所以有效,也是因为局部性。虚拟内存作为下一层存储器层次,大小会比物理内存大,所以运行过程中程序引用的不同页面总数可能会超出物理内存大小。如果程序具有好的局部性,则在任意时刻的工作集较小,程序会趋于在一个较小的活动页面(Active Page)集合上工作,所以只需要在一开始将工作集页面调度到物理内存中,过后就不会产生额外的磁盘流量了。但是如果局部性较差,则工作集超过了物理内存大小,则会发生抖动(Thrashing),使得不断从磁盘中读取页到物理内存中,程序性能大大降低。在Linux中,可以通过getrusage函数检测缺页的数量。

    虚拟内存从缓存的概念考虑,要求程序具有较好的局部性

    从缓存的角度来看,内存是作为虚拟内存的缓存,则这两层存储器层次之间传输数据的块大小相同,都为

    字节,在物理内存中的数据块称为
    物理页(Physical Page,PP),也称为页帧(Page Frame),在虚拟内存中的数据块称为虚拟页(Virtual Page,VP)。虚拟页有三种状态:
    • 未分配的:未分配的虚拟页就是没有任何数据和它关联的数据块,不占用任何磁盘空间。
    • 缓存的:已保存在物理页中的已分配的虚拟页
    • 未缓存的:还未保存在物理页中的已分配的虚拟页

    fd61cb84c501f2b85613c67f0c28da0a.png

    其次,主存作为虚拟内存的缓存,如果主存不命中,就会从速度特别慢的磁盘中读取数据,造成很大的开销,所以虚拟内存和主存之间传输的数据块大小P较大,通常为4KB~2MB,由此增强空间局部性。并且为了避免数据块冲突,内存是全相联的,意味着虚拟页能保存在任意的物理页中。最后,由于对磁盘的访问时间较长,内存采用写回的形式

    虚拟页到物理页的映射关系保存在物理内存中常驻的页表(Page Table)数据结构中,该页表由操作系统维护,每个虚拟页在页表中都保存了它对应的物理页,所以一共需要

    页表条目(Page Table Entry,PTE)。每次地址翻译硬件将一个虚拟地址转换为物理地址时,就会访问该页表。

    2d631fc913c1d5e406c62a522ce09ddf.png

    如上所示是一个页表数据结构,每个PTE包含一个有效位和一个n位地址字段组成。当有效位为1时,表示已将该虚拟页缓存在物理页中,则地址字段就是对应的物理页的起始物理地址;当有效位为0时,如果虚拟页是未分配的,则地址字段为NULL,如果虚拟页分配了,则地址字段就是对应的虚拟页在磁盘上的起始地址。

    注意:由于内存采用全相联结构,所以任意的虚拟页能缓存在任意的物理页中。

    2.1.2 操作

    当CPU想要访问位于虚拟地址x中的数据字时,会首先通过地址翻译硬件将虚拟地址作为一个索引来定位PTE,然后通过PTE来确定对应的虚拟页的状态。如果PTE的有效位为1,说明该虚拟页被缓存在物理内存了,则CPU可以通过该PTE的地址字段获得物理内存的地址,然后进行访问

    db2ebcbe2590209347ae572ee6256b71.png

    如果该PTE的有效位为0,且地址字段指向虚拟页在磁盘的位置,则说明该虚拟页还未缓存在物理页中,则出现了缺页(Page Fault)(对应于不命中)。处理器会发起缺页异常,然后调用内核中的缺页异常处理程序,会执行以下步骤:

    • 由于内存使用全相联结构,如果存在空的高速缓存行,则会选择该物理页,否则会从中选择一个牺牲页,由于采用了写回的策略,所以如果该物理页的数据被修改过,就将其复制会磁盘中。
    • 修改牺牲页对应的PTE,将地址字段指向虚拟页在磁盘的位置,说明该虚拟页未被缓存
    • 内核从磁盘复制目标虚拟页到该牺牲页中,并修改目标虚拟页对应的PTE,将地址字段指向牺牲页的物理内存地址
    • 缺页异常返回到导致缺页异常的指令,重新执行该指令,此时由于缓存了目标虚拟页,所以会命中

    f2e934226e2ca5d8df9f7f46ec8ee7ce.png

    当CPU想要分配一个新的虚拟页时,比如调用了malloc函数,则首先在磁盘中创建一个虚拟页大小的空间,然后修改对应的PTE,将有效位置为1,且地址字段指向新的虚拟页在磁盘中的位置。

    2.2 虚拟内存作为内存管理的工具

    (这一节一下解释了之前的很多疑问)

    内核在进程上下文中为每个进程都维护了自己独立的页表,使得每个进程有独立的虚拟地址空间。每个进程的页表将该进程连续的虚拟地址空间映射到DRAM物理地址空间中的任意位置,并且不同的虚拟页和不同的进程可以映射到不同的物理页中。通过这种形式,可以提供一种视图:每个进程都有一个非常相似的虚拟地址空间,有相同大小的地址空间,代码和数据分别从同一个地址开始,但是进程使用的物理页实际上可能会分散在DRAM内存中。

    6a50f4cf9ee3d26a204dc1c89652354c.png

    按序页表调度和独立的虚拟地址空间,提供了以下便利:

    • 简化链接:由于每个进程都有自己独立的虚拟地址空间,则相同的虚拟地址在不同的进程可以通过进程自己的页表来确定最终的物理地址,所以链接器生成可执行目标文件确定内存地址时,无需考虑当前物理内存的状态,可以根据我们预定义的内存模型来分配虚拟内存地址,因为不同进程之间的虚拟地址是独立的,最终可以通过页表来映射到真实的物理地址。这就极大简化了链接器的工作,可以直接按内存模型来分配地址。

    383b7cb986c5de7126a0a9af0cc6f002.png
    • 简化加载:想要把可执行目标文件加载到物理内存中,Linux加载器只需要为可执行目标文件中的代码段和数据段分配虚拟页,然后在页表中将这些虚拟页设置为无效的(表示还未缓存),然后将地址字段指向对应的位置,则实际的加载工作会由操作系统自动地按需执行。当访问某一虚拟地址时,发现其对应的PTE是无效的,则会发起缺页异常,通过缺页异常处理程序自动地将虚拟页加载到物理页中。所以加载器不会将磁盘内容复制到内存,而是为可执行目标文件分配虚拟页。这种将一组连续的虚拟页映射到任意一个文件中的任意位置称为内存映射(Memory Mapping)
      • 加载实际是非常高效的机制,比如你的程序中包含一个巨大的数组,但是你只访问该数组的一部分,实际上不会将整个数组对应的虚拟页保存到物理页中,因为加载器只是初始化页表。当你代码中访问该数组的一部分时,内核会执行缺页异常处理程序,将包含你想要的数据的虚拟页加载到对应的物理页中,所以效率很高。
    • 简化共享:通过为每个进程设置独立的页表,可以很简单地实现共享库和内核的共享。之前介绍过,共享库会在加载时或运行时动态加载到物理内存的任意位置,让所有进程进行共享。这里只需要在进程中通过一个PTE指向该共享的数据或代码的物理页,就能实现在所有进程中共享的结果。也侧面说明了pltgot的必要性,可以避免修改共享库的内容。
    • 简化内存分配:进行内存分配时,可以通过malloc函数在物理内存中的任意位置进行创建,因为页表只需要让虚拟页指向该物理页,就能提供连续的虚拟地址抽象,让进程误以为是在连续的地址空间中进行操作的,由此简化了内存分配需要的工作。

    (妙啊!)

    2.3 虚拟内存作为内存保护的工具

    通过对页表的改进,可以很容易地进行内存保护

    5fb9cfb8dc3dd4793d8ec783a103799a.png

    这里在每个PTE中引入了三个字段:

    • SUP:确定该物理页的访问权限,确定是否需要内核模式才能访问
    • READ:确定该物理页的读权限
    • WRITE:确定该物理页的写权限

    MMU每次访问时都会检查这些位,如果有一条指令违背了这些许可条件,就会触发一个保护故障,Linux shell一般会将这种异常报告为段错误(Segment Fault)

    3 地址翻译

    3.1 基础

    接下来简单介绍下地址翻译,地址翻译就是一个N元素的虚拟地址空间(VAS)中的元素和一个M元素的物理地址空间(PAS)中元素之间的映射

    399624883ad0837c05d5942aef7360c7.png

    主要通过MMU硬件利用保存在物理内存中的页表来实现,MMU具有以下结构

    61b4d0a4803f284cf23e3a6cdd3089fd.png

    首先,虚拟页大小为P个字节,所以需要虚拟地址的低p位来索引一个虚拟页中的字节,得到虚拟页偏移量(Virtual Page Offset,VPO),然后通过虚拟地址的高n-p位来确定虚拟页在也表中的索引,得到虚拟页号(Virtual Page Number,VPN)。而页表的起始地址保存在一个特殊的CPU寄存器页表基址寄存器(Page Table Base Register,PTBR)中,所以可以通过VPN和PTBR得到想要的PTE的物理内存地址。并且由于虚拟页和物理页的大小相同,所以两者编码页中偏移量所需的位数p相同,可以假设数据在虚拟页和在物理页中的偏移量相同,由此就无需在页表中保存物理页偏移量(Physical Page Offset,PPO),只需要保存物理页号(Physical Page Number,PPN),可以直接将VPO复制给PPO,来确定数据在物理页中的偏移量。

    从全相联缓存的角度来看,VPN其实就是标志位,而VPO就是块偏移。

    注意:页表中只保存PPN。

    页面命中主要执行以下步骤,可以发现完全由硬件处理:

    • CPU生成一个虚拟地址,将它发送给MMU
    • MMU根据虚拟地址获得VPN,然后通过PTBR确定该PTE所在的物理内存地址(PTEA)(因为页表保存在物理内存中),然后将PTEA发送给物理内存
    • 物理内存根据PTEA将对应的PTE发送给MMU,其中PTE只包含PPN(因为假设了数据在页内偏移量相同)
    • MMU将PPN和VPO拼接起来,就可以得到虚拟地址对应的物理地址。然后MMU再将物理地址发送给物理内存
    • 物理内存根据物理地址将数据发送给处理器

    1098d5e23e44b8d80daa079a0027a988.png

    缺页主要执行以下步骤,由硬件和操作系统共同完成:

    • 前三步相同,当MMU接收到PTE时,发现有效位为0,说明该虚拟页还未缓存在物理页中,就会发起一个缺页异常,由内核来执行缺页异常处理程序。
    • 通过内核来确定一个牺牲页,如果该牺牲页中的数据被修改过,就将其复制到对应的磁盘虚拟页中
    • 内核将需要的虚拟页保存到对应的物理页中,并修改对应的PTE
    • 从缺页异常处理程序返回到导致异常的指令,重新执行该指令,就会执行页面命中的步骤。

    3bb569f07af1aed27703be93876d3ab0.png

    在高速缓存中,为了不同进程能共享相同的物理页且避免相同虚拟页的冲突,这里使用物理寻址。所以MMU负责地址翻译和访问权限检查,然后使用物理内存地址访问高速缓存

    06285b25d3beee138259988ec3518a45.png

    3.2 利用TLB加速地址翻译

    可以发现,每次CPU将一个虚拟地址发送给MMU时,MMU都会将需要的PTE物理地址发送给高速缓存/内存来获得PTE,如果高速缓存刚好保存了该PTE,则MMU可以很快获得,否则需要等待很多时钟周期从内存中读取。

    为了减小这个开销并进一步利用局部性原理,在MMU中引入了一个保存最近使用的PTE缓存,称为翻译后备缓冲器(Translationi Lookaside Buffer,TLB)。在TLB中,使用虚拟地址进行寻址,具有较高的相联度,每个高速缓存行保存一个PTE,每次都是以一整个PTE进行读写,不需要含有块偏移,记得我们之前是通过VPN在页表中索引获得PTE,所以虚拟地址的划分为

    69acd10e8fa984669fb4f2be2866d28a.png
    这里使用虚拟地址来访问TLB,如果不同进程使用相同虚拟地址访问TLB,不就造成错误了?这里也没使用PTBR来确定使用哪个页表,难道每次进行上下文切换改变进程时,都会将TLB清空,只保存当前进程的PTE来避免冲突??

    所以当TLB命中时的步骤为:

    • CPU产生一个虚拟地址,发送给MMU
    • MMU提取出当前虚拟地址的VPN,发送给TLB
    • TLB对VPN进行分解,得到TLBI和TLBT,根据TLBI确定所在的高速缓存组,然后在高速缓存组中依次比较各个高速缓存行的标记是否和TLBT相同,如果相同,则TLB命中,将对应的PPN发送给MMU
    • MMU将PPN和VPO拼接起来得到虚拟地址对应的物理地址。然后MMU再将物理地址发送给物理内存
    • 物理内存根据物理地址将数据发送给处理器

    由于TLB位于MMU中,速度特别快。

    8b28061ec9755957c38ef6fa430664bc.png

    TLB不命中时的步骤为:

    • CPU产生一个虚拟地址,发送给MMU
    • MMU提取出当前虚拟地址的VPN,发送给TLB
    • TLB对VPN进行分解,得到TLBI和TLBT,没有找到有效的PTE,发生TLB不命中
    • MMU根据PTBR和VPN得到PTE对应的PTEA,将其发送给高速缓存/内存
    • 高速缓存/内存将对应的PTE发送给MMU和TLB
    • TLB会根据VPN将PTE保存在合适的位置
    • MMU接收到PTE后,将PPN和VPO拼接起来得到虚拟地址对应的物理地址。然后MMU再将物理地址发送给物理内存
    • 物理内存根据物理地址将数据发送给处理器

    36d607b17a8bc971eae84821bb2dbf89.png

    3.3 多级页表

    在一个32位地址空间中,每个页面大小为4KB,则一共需要

    个页面,假设每个PTE大小为4字节,则页表总共为4MB。当使用一级页表时,需要始终在内存中保存着4MB大小的页表,我们这里可以使用多级页表来压缩内存中保存的页表内容。

    d611d80fc06b21d6defa540baf4a683d.png

    首先,我们这里有1M个虚拟页,将连续的1024个虚拟页当成一个片(chunk),一级页表就负责指向每个片对应的二级页表,则一级页表需要

    个PTE,每个PTE4字节,则一共需要4KB大小的一级页表。
    注意:这里只有当片中至少一个页被分配了才会指向对应的二级页表,否则为NULL。而二级页表就类似于我们之前的页表结构,这里只需要负责一个片的虚拟页,则每个二级页表为4KB。

    当一级页表的某个PTE为NULL时,表示该片不存在被分配的虚拟页,所以就可以去掉对应的二级页表。并且在内存中只保存一级页表和较常使用的二级页表,极大减小了内存的压力,而其他的二级页表按需创建调入调出。

    44189ec2f6fb21d6255f6693e9d0ebc4.png

    以上是一个k级页表层次结构的地址翻译,前面k-1个页表的PTE都是指向下一级页表的基址,而第k级页表指向的是PPN或磁盘地址。所以每次地址翻译时,MMU需要从内存中访问k个PTE,但是TLB的存在弥补了这个开销。首先,一级页表覆盖了所有的地址空间,所以一定会缓存在TLB中,而二级页表覆盖了大量的地址空间,所以他们也有很大可能会在TLB中,以此类推,只要你程序具有良好的局部性,就有很大概率从TLB中获得想要的PTE,由此弥补了多次访问页表的性能损失。

    TLB应该要将不同层次的PTE独立开来

    3.5 地址翻译实例

    首先我们需要作出以下假设:

    1. 内存是按字节寻址的
    2. 内存访问是针对1字节的字的
    3. 虚拟地址是14位长的
    4. 物理地址是12位长的
    5. 页面大小是64字节的
    6. TLB是四路组相连的,总共有16个条目
    7. L1 d-cache是直接映射的,行大小为4字节,总共有16个字节

    根据以上假设,我们可以从获取页表、TLB和高速缓存的信息:

    • 页表:当前只使用一级页表,页表大小为64字节,则虚拟页有
      个,则页表具有256个PTE;物理页有
      个。根据地址翻译,可以将虚拟地址和物理地址进行以下划分

    f5cb58254d0ab9cb94e91a07a66e0cf6.png

    由此可以通过VPN在页表中获得对应的PTE,然后通过VPO获得在虚拟页中的数据,物理地址也同理。

    • TLB:四路组相连说明每个高速缓存组中具有四个高速缓存行,而TLB是以PTE为单位进行存取的,所以每个高速缓存行能保存一个PTE,而TLB一共能保存16个PTE,说明该缓存具有4个高速缓存组,则需要2位的组索引TLBI。因为TLB是虚拟寻址的,所以是在虚拟地址上进行划分的,且以PTE为单位进行存取,所以是在VPN中进行划分的,低2位为TLBI,则高6位为标志位TLBT

    c3c63be24680e5dd9497eee9317151cd.png
    • 高速缓存:直接映射的高速缓存,说明每个高速缓存组只有一个高速缓存行,行大小为4字节,则需要2位的块偏移(CO),一个有16个组,则需要4位的组索引(CI),其余的为标志位(CT)。由于高速缓存是物理寻址的,所以要在物理地址上进行划分

    5a2a34f63a8e6d7dd8538cd576cf5beb.png

    假设当前页表、TLB和高速缓存的内容如下

    98d1f1edaa4be8bf05e6d34082859c3c.png

    当CPU产生虚拟地址0x03d4时,执行步骤为:

    • 首先根据虚拟地址,我们可以进行以下划分,MMU会将VPN字段0x0f发送给TLB

    ef2c2df7c789e774af424489e715e6c4.png
    • 当TLB接收到VPN时,会从中划分出TLBT0x03和TLBI0x03,然后根据TIBI确定在TLB中的高速缓存组,依次将TLBT和标志位进行比较,可以发现第二个高速缓存行具有相同的标志,则TLB命中,会返回对应的PPN0x0D给MMU
    • MMU将PPN0x0D和VPO0x14拼接起来,得到物理页对应的物理地址0x354
    • 根据物理地址,可以进行以下划分,MMU将物理地址发送给高速缓存

    4bcd412322fa47e447c281a349c2fcac.png
    • 高速缓存根据CI确定所在的高速缓存组,并将组内的高速缓存行的标志位依次与CT进行比较,可以发现高速缓存命中了,并根据CO在块内偏移,得到想要的数据0x36,将其返回给MMU
    • MMU获得数据后,将其返回给CPU

    以上是比较简单的情况,即TLB命中和高速缓存命中,其他较复杂的情况需要MMU很多后续的操作。

    大致的步骤为:

    1. 将虚拟地址根据TLB规则进行划分,在TLB中进行检索,如果存在则将PPN返回给MMU,如果不存在,将地址根据页表规则进行划分,得到对应的PTE,将其保存到TLB,并将PPN返回给MMU
    2. MMU根据PPN和VPO构建出物理地址,并将物理地址发送给高速缓存
    3. 将物理地址根据高速缓存规则进行换分,在高速缓存中检索,如果存在则将数据返回给MMU,如果不存在则需要从内存中进行检索

    综上:页表和TLB是虚拟寻址的,都是返回对应的PPN;高速缓存是物理寻址的,返回对应的数据。

    展开全文
  • 用户对内存页配置页属性成功,但页属性未生效。 例如:对分配到的某块内存进行memset(),然后设置只读属性,再进行memset()时不触发写保护。
  • Rust在语法上和C++类似,但是设计者想要在保证性能的同时提供更好的内存安全。Rust最初是由Mozilla研究院的Graydon Hoare设计创造,然后在Dave Herman, Brendan Eich以及很多其他人的贡献下逐步完善的。Rust的设计者...
  • 512], } 如repr属性所示,页表需要页面对齐,即在4KiB边界上对齐。这一要求可确保页表总是填满完整的页面,并允许优化,使条目非常紧凑。 每个条目为8字节(64位)大,格式如下: 我们看到只有位12-51被用来存储物理...
  • 内存不能为写? 是哪里错了呢..调试了一下,原来是 str[i]-=32 这里错了 str的地址不能写入?为什么呢? 然后带着疑问用OD调试看了一下:   00428020=00428020 (ASCII "abcde") STR的地址在00428020 看了下区段,是...
  • 假设某个元素有一个事件处理程序,在使用前某个属性将该该元素从文档树种删除后,元素与时间处理程序之间的绑定关系在内存中并没有一并删除。如果这种情况频繁出现,页面占用的内存数量就会明显增加。因此在使用...
  • 提供了一种利用内存保护技术实现程序踩内存的检测方法, 利用内存保护技术, 在应用程序申请内存后根据情况将其所申请的内存页面属性设置为只读....
  • 当我们电脑当中的物理内存不足的时候,我们可以通过电脑系统当中的虚拟内存来设置虚拟内存,把虚拟内存设置大一些,这样能够在一定程度上缓解内存不足的压力,...如图所示: 2、打开电脑属性页,在属性页的左边有...
  • 补间动画和属性动画内存泄露分析

    千次阅读 2018-10-19 17:36:25
    在使用属性动画的时候,我们知道如果不在页面结束的时候释放掉动画,就会引起内存泄露。 简单的说就是ValueAnimator在AnimationHandler注册自己的AnimationFrameCallback,AnimationFrameCallback接口的实现类就是...
  • 消息“未设置属性”已禁用“未定义为”0“”我认为它可能是由一个javascript方法引起的,它试图设置一个尚未在表单中声明但我不确定的变量。tempForm = MyPage.getFormByName("menu_form");tempForm.getInpu...
  • 内存断点原理

    2010-06-10 14:54:30
    内存读写断点的实现,众所周知是把相关内存页属性设置为PAGE_NOACCESS,这样当此页内内存被读写的时候会有异常传给调试器。 但异常传给调试器以后的事,就很少有资料说起了,可能我比较孤陋寡闻,研究了几天才搞...
  • 内存断点调试的原理

    2015-03-13 18:27:00
    内存读写断点的实现,是把相关内存页属性设置为PAGE_NOACCESS,这样当此页内内存被读写的时候会有异常传给调试器。 当异常传给调试器时候,debugee进程被挂起,调试器把内存页属性重新修改回去,同时设置一个单步...
  • 前面讲了DOS,PE头。下面详细讲一下映射到内存后有那些变化 前三部分DOS头部,PE头,块表加载到...页属性要按照节的属性来设置。所以,在同属一个模块的内存中, 从不同映射过来的内存页的属性是不同的 节的偏移地
  • <br />PAT(页面属性表Page Attribute Table)    X86的页面属性表(PAT)能够在页面级的粒度上设置内存属性。PAT是对MTRR的补充,通过MTRR可以为物理地址区域设置内存类型。但是PAT比MTRR更灵活...
  • 可分页内存是由操作系统API malloc()在主机上分配的,锁定内存是由CUDA函数cudaHostAlloc()在主机内存上分配的,锁定内存的重要属性是主机的操作系统将不会对这块内存进行分页和交换操作,确保该内存始终驻留在...
  • 原理:对内存页面设置PAGE_NOACCESS保护 当程序内访问改页面内数据时产生ACCESS_VIOLATION 产生异常被VEH捕获 VEH处理函数内还原内存页面PAGE_READWRITE属性 然后设置ExceptionInfo->ContextRecord->EFlags |=...
  • 虚拟内存与页面文件的关系 近日和朋友讲到大内存可以禁用页面文件的事情。他跟我讲Windows的许多核心功能和有些程序都要使用到虚拟内存,不应禁用虚拟内存。...系统属性——高级——性能——设置——高级——虚...
  • Windows内存体系(2) -- 交换文件

    万次阅读 2018-03-19 15:59:18
    交换文件”的大小和位置可以在系统设置(系统属性 -&gt; 高级 -&gt; 性能 -&gt; 设置 -&gt; 高级 )中进行设置: 从微软的官方文档来看,“虚拟内存”等于“物理内存”+...
  • 对于页属性的管理相应思考 我看了下,虚拟地址到物理地址的转换很简单,解释虚拟页号对应找到物理页号,偏移计算出物理地址。而且虚拟偏移和物理偏移是一样的。所以这里这是虚拟页好和物理页号不可能是简单的确定...
  • CUDA学习--锁定主机内存

    千次阅读 2016-09-06 19:04:26
    1. 锁定主机内存 除了通过cudaMalloc()在GPU上分配内存,以及通过标准的C函数malloc()在主机上分配内存,CUDA运行时还提供了自己独有的...锁定的主机内存也称为固定内存或不可分页内存,它的重要属性就是:操作系统
  • 可今天上午有客户突然反应说我们产品占用浏览器资源相当高,一个页面甚至达到了300MB-1000MB,直到内存满。开始我以为是浏览器之前访问过别的页面,资源没及时释放,可后来自己进去测试后,发现每点击一个使用Ext...
  • “pagefile.sys”是页面交换文件,切记,这个文件不能删除,但是可以改变其大小和存放位置:右击“我的电脑/属性”,然后在对话框的“高级”标签下单击“性能”下的“设置”按钮,在”性能选项”对话框中切换到...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,373
精华内容 549
关键字:

内存页属性