从静态地址翻译到段页式内存管理

 

  内存管理需要完成两个任务:地址保护,一个程序不能访问另一个程序的地址空间;地址独立:程序发出的地址应该与物理地址无关。段式管理/页式管理/段页式管理都是为了实现这两个目标而产生的内存管理方式。

内存管理的演变过程

静态地址翻译

  将用户程序固定放在同一个物理地址。这种方式只支持单道编程环境,整个内存只有两个进程,操作系统和唯一的用户进程。因为操作系统占用的空间是恒定的,所以我们可以将用户程序永远加载在同一个内存地址上。所以用户程序里面的地址可以在运行前计算出来,这种运行前即将物理地址计算好的方式叫做静态地址翻译。

  这种方式的优点是简单,因为其没有运行时地址翻译的必要。缺点也很明显,一是程序必须完整的被加载到内存中;二是因为程序的内存起始地址恒定,整个内存只能加载一个用户程序;三是无法在不同的操作系统运行,因为不同的操作系统占用的内存大小是不一样的。

动态地址翻译

  相对于静态地址翻译,动态地址翻译是指在程序运行时进行地址翻译。动态地址翻译分为固定分区的动态地址翻译和基于基址/极限的动态地址翻译。对于固定分区即是将虚拟内存分为固定的几块,每块连续的虚拟内存可以加载运行不同的用户程序。这样便可以支持多道编程,达到地址保护的目的。每个分区维护一个等待加载的程序队列,程序需要被加载时被指派到某个分区的等待队列中等待。相比于静态地址翻译,固定分区的动态地址翻译可以支持多道编程,但这样做的缺点也很明显,一是OS并不能确定会加载多大的用户程序,分区大小的合理性很难保证;二是用户程序运行时间的不确定,导致等待队列忙闲不一,无法有效的使用内存。

  基于基址/极限的动态翻译方式下,用户程序可以被加载到任意地址的内存地址中(只要连续的空间足够)。程序在运行时,只要知道其所在内存的起始地址,便可以通过偏移量来计算出真实地址。 相比于固定分区的动态翻译方式,内存使用效率有了极大的提升。

  相比于静态地址翻译,动态地址翻译增加了系统的复杂性,降低了管理效率。但其所带来的优点远远大于这个缺点。第一个优点便是灵活,我们无需再借助编译器或者加载器在程序运行前进行静态地址翻译,便可以将程序加载到任何位置;二是其支持多道编程,并实现了地址保护。在基址/极限的管理方式下,任何越过极限的访问都将被禁止;三是使虚拟内存的概念得以实现。

虚拟内存

  虚拟内存在用户程序与物理存储之间隔了一层,用户程序访问的不再是物理地址,而是虚拟地址,一个物理地址的抽象,必须由 MUU 翻译为物理地址后才可以使用。 

  虚拟内存的中心思想是将物理内存扩大到便宜、大容量的磁盘上,即将磁盘看做主存空间的一部分。有了虚拟内存,我们编写的程序不再受到主存大小的限制,而仅受限于处理器的寻址范围。同时程序将不再与真实的物理存储打交道,而是向操作系统申请虚拟内存即可,不再需要关注物理内存分配的细节。

页式内存管理  

  基于基址/极限的动态翻译方式带来的好处上面已经做了列举,再说说它存在的问题。

    基址/极限的动态翻译方式存在的最大的两个问题便是空间浪费和程序大小受限。

  它们的本质都在于,程序申请的虚拟内存是一块连续的内存地址,而这块连续的虚拟内存地址所对应的物理内存地址依然是连续的。也就是说,程序依然需要被加载到整块连续的物理内存中。分配连续的物理内存会导致内存在不断的申请和释放后,遗留大小不一的外部内存碎片,它们不是连续的,无法被有效的使用;同时如果没有足够大的连续物理空间,程序将无法被加载到内存中,即使空闲的碎片内存的总和大小远远大于待加载程序的需要。另外,虽然引入了虚拟内存的概念,但基址/极限模式下,内存的申请与分配是以进程为单位的,如果我们将程序的一部分放在内存中,一部分放在硬盘上,当使用到硬盘上的数据时,我们很难抉择应该将多少数据刷回内存中,也无法记录新刷回部分的虚拟内存与实际内存的对应关系。

  程序的运行需要连续的虚拟地址,但并不代表其对应的物理地址也必须是连续的。与其它缓冲区一样,虚拟地址作为用户程序与物理地址之间的缓冲地带,可以帮助我们做很多事情。我们将虚拟地址与物理地址一道,分割成大小相等的“页”,比如4,8,16k。并维护一个数据结构记录其对应关系,便可以做到消除外部碎片的目的。

  比如程序申请了 600k - 800k 之间的连续虚拟内存,按照 4k 分页的情况下,这部分虚拟内存包含 50 个内存页。操作系统只需要同样为其分配 50 页物理内存页即可,而这50页物理内存页并不需要在连续的内存空间上。这样 OS 访问内存需要按页翻译,或者说按页访问,所以我们在设置一些内存中的缓冲区时,需要充分考虑到内存页的大小。比如 4k 大小的分页,我们设置 5k 的缓冲区或者设置 8k 的缓冲区,都需要进行两页的地址翻译,效率是差不多的。但我们申请 4k 的缓冲区则只需要一页地址翻译,比 5k 只少了 1k,提升的效率却远远不止百分之二十。通常情况下我们使用内存应尽量按页大小的整数倍进行申请,也就是所谓的 4k 对齐 8k 对齐。

  当使用到某页时,如果其对应的物理内存有效,则直接加载物理内存页中的数据。而如果其对应的物理内存页在磁盘上,则触发缺页异常将其加载到物理内存中。使用到哪一页加载哪一页,程序的运行不需要其全部被加载到内存中。但是因为涉及到缺页中断,新加载内存页数据时,如果物理内存没有足够的空间则必然导致物理内存中内存页的替换问题。如果替换算法不合理,造成的影响将是灾难性的。比如每次缺页中断替换的内存页,在很短的时间内会被再次使用,那么将再次触发缺页中断,OS 陷入不断的缺页中断中将导致绝大部分计算资源被消耗在页面替换上(内存抖动,内存抽筋,比莱迪异常),因此必须设计合理的页面替换算法来避免这一问题的发生。页面更换算法的目标是降低更换后缺页中断发生的次数或者概率,目前常用的页面更换算法有:随机算法(公平)、FIFO算法(公平)、第二次机会算法(公平)、时钟算法(公平);最优算法(非公平)、NRU算法(非公平)、LRU算法(非公平)、工作集算法(非公平)。

  页式管理需要解决的问题是对处理器的整个寻址空间来说,可分出来的内存页数量非常庞大,所以需要维护一张非常巨大的页表来存储虚拟内存页与物理内存页之间的对应关系。这样一来页表的存储所占内存空间太大,并且页表的查找效率不能得到保障。对于页表所占内存空间太大的问题,目前主要采用多级页表或反转页表的方式解决,也就是为页表加索引,甚至为索引再加索引,内存中只存储索引,而真实的页表放在磁盘上。这样常驻内存的次级页表很少,大部分次级页表都放在磁盘中。但如果访问的次级页表不在内存中,需要触发缺页中断将其加载到内存中,这样一来地址翻译的过程又夹杂了磁盘操作,效率无法得到保证。所以在此基础上,又增加了翻译快表模块 TLB ,TLB 中对我们的地址翻译历史进行了缓存,同时 TLB 模块配备了多套比较电路以提高其查询效率,所以 TLB 非常昂贵。不管 TLB 的实现多么昂贵,其本质上依然是一层缓存,那么跟其它缓存一样,其作用的大小很大一部分原因取决于缓存的命中率,如何提高缓存的命中率则需要具体算法的支撑了。比如 Linux 系统使用三级页表,并且某些资料宣称其 TLB 命中率达到了恐怖的 98%。

段式内存管理

  页式内存管理已经足够复杂和周到,但依然存在一些问题。

  第一个问题便是数据共享的困难,因为内存是按页进行分配的,如果一个页中既包含程序又包含数据,那么该页无法被共享。或者换一种说法,一个页面中,即使只包含一个字节的数据不能被共享,那么这个页面便是不能被共享的。

  第二个问题不是分页特有的问题,而是上面所说的内存管理方式普遍存在的问题,那就是一个进程只能占用一个连续的虚拟地址空间。这个问题初看并不是问题,但在一些特殊场景下确实被需要的,比如编译器的运行。编译器中既有常数段,又有词法分析树等等,而这些模块都是可以独立增长和收缩的,如果将其放在同一块虚拟内存空间中,其增长空间会受到其它模块起始地址的限制,导致无法正常运行。

  如果没有过具体实践,可能很难理解第二种情况。想要理解第二种问题的存在,首先要明白的是这里指的空间是虚拟空间的增长而不是物理空间的增长。举个例子,我们编写一段程序,程序起始的虚拟内存地址是0,我们为第一个程序模块分配了 0-20k 的空间,那么第二个模块的虚拟地址起始位置为 21。那么当第一个模块所需内存超过 20k 时,将无法为其分配足够的内存。

  为了解决上述两个问题我们又有了新的内存管理方式,段式内存管理。段式内存管理便是将程序按其逻辑单元分为多个程序段,每个程序段拥有自己独立的虚拟地址空间。一个程序占据多个虚拟地址空间,那么不同的段可能有同样的虚拟地址空间。我们需要用段号区分不同段的程序,即用段号和段内偏移地址来进行地址翻译。

  继续上面的例子,如果采用段式内存管理,上述例子中的两个模块被分为两个程序段。它们对应的虚拟内存起始地址均为 0k ,那么第二个模块无论实际内存分配的起始地址在何处,都不会对为第一个模块分配更多的内存产生影响。也就是说每个程序段的虚拟内存地址都是独立的,都是从 0 开始的,其最大容量都仅仅受限于处理器的寻址范围。

  段式内存管理与基于基址/极限的动态地址翻译类似,不同在于段式内存管理中一个程序可以拥有多个独立的虚拟地址空间。动态地址翻译存在的缺点段式内存管理几乎都存在,空间浪费和必须将程序全部加载到内存中。因此单纯的段式很少使用。

段页式管理

  段页式管理便是把程序分为多个逻辑段,同时在每个逻辑段内部进行分页。同时获得分段分页的好处,并避免单纯使用分页或分段时的缺陷。如果我们将每个段看作一段独立的程序,那么逻辑分段就相当于同时加载了多个程序。实现段页式管理,我们只需要在多级页表的最外层再套一层段表,将段号作为寻找页号的索引即可。在分页模式下,程序发出虚拟地址请求,MMU 会根据页大小计算出该地址处在虚拟地址的哪一页,再通过查询页表找到物理页,最后根据页内偏移找到数据;在段页式管理中,程序发出虚拟地址请求,MMU 会先根据程序所处程序段找到与之对应的页表,再重复上述过程。分段与分页的不同是,页号是占用虚地址空间的位数的,而段号并不占用虚地址空间的位数。页号是我们在运行期间动态翻译出的,是对内存的管理;而我们对程序进行的逻辑分段,一定程度上说是对程序的管理,段号可以在运行前便确定下来。因此可以将段号隐藏在指令操作码中,或者采用专门的寄存器进行存储,因此段号不需要占用虚地址的地址位。段号的唯一作用便是帮我们找到该段程序对应的页表。

  

原文地址:https://www.cnblogs.com/niuyourou/p/12771249.html