第六讲_物理内存管理_非连续内存分配

在我们前面讲到的连续内存分配, 要给一个进程分配内存, 那必须分配物理地址连续的一块内存区域, 这给分配带来了很多的麻烦. 你比如说用户想要一块区域, 而在内存中又没有满足这个大小的连续区域, 那这个分配就会失败.

基于这种现状, 那提出了一种需求, 说我们是否可以不连续, 分配的内存空间不连续.

OK, 不连续呢当然是说我可以找到它的几率会更高, 但这时候也会面临一些新的麻烦. 说我不连续之后我把哪些内容, 我是任意一个最小的单位, 一个字节就可以算成一个区域还是说我会受到一些限制, 那这个时候你这个分配到一个字节为一个单位太短了.

基于这种情况呢, 我们会选择不同的尺度来说, 我这个非连续内存分配我能每一块, 基本的块会有多大. 基于这种基本块的大小呢, 我们这里有两种, 一种是段式, 一种是页式.

段式分的块比较大, 页式分的块比较小. 分的块小了之后, 我这两者之间的对应关系, 逻辑地址到物理地址之间的对应关系就会变得比较复杂. 因为这个, 我们这种对应关系就形成我们这里说的页表.

还有一种方式就是, 我是不是可以把这两种方式结合起来, 那这就是我们这里的段页式.

非连续内存分配的需求背景

我们先讲一讲非连续内存分配的需求

• 连续内存分配的缺点
  • 分配给程序的物理内存必须连续
  • 存在外碎片和内碎片
  • 内存分配的动态修改困难
  • 内存利用率较低

那在连续分配的缺点中, 我们说你要求必须连续, 这一条很难达到. 即使能达到, 在分配回收的过程当中, 里面也会有内碎片和外碎片.

如果说一个程序在执行的过程当中, 它需求的内存空间大小又有变化, 那这种变化就导致你很难进行动态的增加或者说减少, 这样最后的结果就是我们内存的利用效率比较低. 原因在于用户应用进程的需求, 你没有办法满足.

• 非连续内存分配的目标 : 提高内存利用效率和管理灵活性
  • 允许一个程序的使用非连续的物理地址空间
  • 允许共享代码和数据
  • 支持动态加载和动态链接

针对这种情况, 我们非连续内存分配要达到的目标就是希望能提高利用效率, 提高它的管理的灵活性.

具体说起来有这么一些. 第一个我希望分配的空间不再是有连续性的要求, 这样的话我找着你要的大小的区域的几率就会提高.

第二个是说我们在用的过程当中, 每个进程它都要执行代码, 这些进程直接有很多代码是共同的, 那各个进程也会用到一些共用的数据, 我们希望通过共享数据和代码实现减少内存的使用量. 也就是说我们在这里面, 两个应用进程都要用到同一个函数库, 那我把这个函数库的代码放到内存之后, 如果它们两个都能访问的话, 能够实现共享, 那这样我占用的内存区域就变少了.

第三个是说我们希望能够变得更灵活, 那我在这里面是不是分小了之后, 我想再要的时候我再给它加一块, 或者说其中某一块的大小的动态变化, 有了这些之后, 我们就可以很方便地能够支持动态加载和动态链接.

非连续内存分配的实现

• 非连续分配需要解决的问题
  • 如何实现虚拟地址和物理地址的转换
  • 软件实现 (灵活, 开销大)
  • 硬件实现 (够用, 开销小)

目标是已经说完了, 好像这个目标很好, 但是这在实现的时候是有很多麻烦的.

首先第一个麻烦就是虚拟地址到物理地址的转换. 程序里面在实现的时候, 那它希望是说我给你一个地址然后告诉你, 你要告诉我它在物理内存的什么地方, 这种转换呢如果它是连续的, 我只需要知道它开头在哪里, 剩下的就都在这一个进程的区域里了.

那现在是不连续了, 那这时候这个转换就有可能是说你在哪一段逻辑地址, 你转换的区域在内存里的一个地方, 而逻辑地址的另一段你在这边是连续的, 到那边可能要转到另外一个区域里面去, 这两种区域的不同就会导致我在这里面的转换过程会比较复杂.

这种转换的复杂, 我们这实现的时候, 有两种选择.

一种是用软件来实现, 比如说我要往内存里存数据, 像一个排序程序, 那由于我没有办法事先确定我要排序的数据的总量, 这时我给它分配多大的存储空间都有不合适的情况.

那我们数据结构里面学会有什么方法, 我们在这里面可以先读一部分进来, 排完之后放到硬盘上去, 然后再读一部分进来, 排完之后放到硬盘上去, 那这时候呢, 最后我再把排好的数据重新捋一遍, 那这就是数据结构里面说到的外排序.

那这种方法也可以用到操作系统里的内存分配上面来. 如果说你的代码空间存不下, 把所有的代码存内存里面放不下的话, 那可以把其中的当前要执行的代码放到内存里面, 把另外一部分代码放到硬盘上去, 那这时候这个怎么来做呢.

可以由软件来做, 也跟我们刚才说的数据外排序类似的方法, 那这种做法就是我们通过你的操作系统软件, 或者说甚至于是应用软件来干这件事.

另一种做法是硬件实现. 如果你要想用硬件来实现的话, 原因在于我们现在做的地址转换过于频繁, 基本上是说你每执行一条指令, 都会去访问内存, 那都要做成转换, 这时候用硬件来实现, 它的效果是比较好的, 开销比较小, 而且这个转换相对来说它要计算的过程是比较简单的重复.

• 非连续分配的硬件辅助机制
  • 如何选择费连续分配中的内存分块大小
  • 段式存储管理 (segmentation)
  • 页式存储管理 (paging)

那有了这样一个实现之后, 还有个什么问题呢.

我们在这里面要把这个进程分配的内存, 放到不连续的地方, 那我每一块大小有多大. 那简单来讲你可能会说要多大给多大就完了, 那这时候是你连续的那样一块, 我分成小块之后, 我可以分成什么样的小块. 这时, 我前面连续内存分配说到的, 内碎块外碎块这些问题是否还存在.

这种分配的不同会导致非连续内存分配的办法有很大的区别. 这里我们大致有两类办法. 一类叫作段式存储, 一类叫作页式存储.

简单来说这两者区别就是段式存储分的块比较大, 它以一个段作为一个基本的单位. 那你在分配的时候, 这一个段的内容必须在物理内存里面是连续的, 不同段之间可以放到不同的地方, 这是段式.

页式呢, 我就把它分成更小的块, 这个块的名字叫作页, 那你在分配的时候就是以页为单位来分配. 页与页之间是不连续的.

那由于这两者分配的情况不同, 实际上它在实现的时候会有很大的区别.

有了这些描述之后我们就可以具体讨论说段式和页式到底是怎么实现的了.

段式存储管理

在段式存储管理里面, 我们会来说明段的地址空间是如何来组织的, 然后在段式存储管理当中, 我的内存访问是如何进行的.

段地址空间

在段式存储管理中, 我们把进程的地址空间看成由若干个段组成的. 每一个段在这里是给出了一些实例.

比如说我的程序, 有主程序有子模块, 那各个模块我可以看成是相对独立的一个段, 主代码我看成是一个段, 然后我的公共库可以看成时另外一个段, 这几个都是代码; 同时还有一些堆, 初始化的数据, 堆栈, 符号表这样的一些数据段.

• 段式存储管理的目的
  • 更细粒度和灵活的分离与共享

那在这里面, 我们把它看成是一个, 组织成一个段地址空间的话, 实际这时我们希望是能够达到把进程的地址空间, 能够以更精细更灵活的方式分离开, 分离开之后我可以实现更好的共享.

段式地址空间的不连续二维结构

有了上面关于段地址空间的描述, 这时候我们就可以把逻辑地址空间转换成一个不连续的二维结构.

那在这里面我们看到, 我们把代码分成了两个部分; 数据和堆栈和对这几个部分, 各个部分内部它是需要连续的, 我会用它的偏移来进行访问. 但各个部分之间, 我们很少有跨越, 很少有从一个段访问另一个段的这种情况, 也就是以一个段的基址去访问另一个段的情况.

段地址空间的逻辑视图

有了这个讨论之后, 我们就可以把段地址空间的逻辑视图转换成一个这样的结构 :

到物理地址空间里面呢, 它就可以是不连续的. 那由于各个段之间我们是相对独立的, 那这里面的不连续对我们访问带来的影响是相对来说比较小的.

段访问机制

有了这种概念之后, 这时候我们来看访问过程是什么样的.

• 段的概念
  • 段表示访问方式和存储数据等属性相同的一段地址空间
  • 对应一个连续的内存 "块"
  • 若干个段组成进程逻辑地址空间

我们可以把它理解为, 段实际上是, 每个段是访问方式和存储数据. 存储的到底是什么数据, 到底用什么样的方式在访问. 这个相对一致的一段地址空间, 这一段我要求它是连续的.

有了这个之后, 如果每一个段对应到一块连续的内存块, 然后若干个组成了进程的逻辑地址空间.

• 段访问 : 逻辑地址由二元组 (s,addr) 表示
  • s --- 段号
  • addr --- 段内偏移

我们再来看段的访问是什么.

我就会把逻辑地址分成一个二元组, 段号和段内偏移. 那原来的地址, 我们是一个连续的若干位.

现在在段式地址空间里面, 我们把它分成两段, 段号和段内偏移. 转化过来之后, 我们看到的逻辑结构变成是段号和段内偏移.

这个时候分开之后, 我再访问的话, 就必须把它转换成原来的地址.

段访问的硬件实现

有了这种地址的划分之后, 它的访问过程会变成什么样子 ?

这是进程的地址空间, 这是物理的地址空间. 然后程序在 CPU 上执行, 它要访问一个存储单元的时候, 首先是它的逻辑地址, 在段地址空间里面把它分成两段, 段号和段内偏移.

首先用段号查进程的段表, 所有的段在这个表里都有一项, 每一项对应一个段描述符. 段表的基本内容是段的起始地址和它的长度. 我们可以用操作系统的软件来对段表的内容进行控制. 也就是说每个段在什么位置, 它的相关信息操作系统可以控制.

有了段的长度之后, 存储管理单元 MMU, 它就会把这个长度和你的偏移取出来, 两个进行比较, 看看是不是越界. 如果越界就会出异常; 如果说偏移是小于段的长度的, 那这是一个合法的访问 (看图, 偏移就是长度).

然后 MMU 里面再利用段基址和偏移两个加到一起, 就可以找到你实际要访问的内容了. 有了这个访问之后, 那我们基于段的这种机制就可以工作起来了.

页式存储管理

• 页帧 (帧, 物理页面, Frame, Page Frame)
  • 把物理地址空间划分为大小相同的基本分配单位
  • 2 的 n 次方, 如 512, 4096, 8192

在页式存储管理中, 它把物理的页面, 物理的地址空间分成的基本单位叫页帧或者叫帧 frame