操作系统之内存管理科普

简介

本篇文章主要介绍操作系统是如何进行内存管理的。

文章会介绍几本的分段，分页，以及虚拟内存的相关知识。

内存管理

需求

1. 重定位

   现在操作系统中, 一个进程运行过程中可能会因为进程切换而在内存和磁盘中来回切换。如果没有重定位, 进程在重新回到内存来运行的时候, 就必须要加载到上一次在内存中运行的时候的同一段内存当中。这样对操作系统的管理来说是一个非常大的成本。

2. 保护

   主要是为了避免进程A通过各种手段读取或者修改了进程B的数据。

3. 共享

   在同一台机器上运行的多个进程, 势必会有不同进程要访问同一个内存块的需求。这里就需要共享内存的机制了。

   最典型的例子是, 当同一个二进制文件起了多个进程的时候, 访问二进制文件程序的时候, 最好是访问同一份, 而不是访问多份。

内存分区

内存分区要解决的问题就是一个进程所需要的内存到底是怎么在物理内存中给他分配的。历史上存在的一些方案整理如下：

方案	说明	优势	劣势
固定分区	在系统初始化的时候, 将可用内存划分成数个大小相等或者不等的内存区域。每次进程运行的时候可以加载到某个大于自己所需内存的内存区域中。	实现简单, 只需要很少的操作系统开销	有大量的内存碎片, 内存利用不充分
动态分区	同固定分区, 只是每次都在内存中动态分配一个跟进程所需内存一样大小的内存块用来装内存	没有内部碎片, 内存利用更充分	随着进程的启动和终止, 还是不可避免的会有碎片出现, 为了提高内存利用率, 又得增加压缩内存的处理进程, 在压缩过程中消耗巨大
简单分页	将主存划分为大小相同的小区块, 进程所需内存也划分为同样大小的区块。进程所需内存被装入到不一定连续的区块中。	没有外部碎片	无
简单分段	类似动态分区, 只是将进程分成数个段, 每个段单独申请一块内存	相比动态分区, 提高了内存利用效率	还是会有外部碎片以及内存整理的工作
虚拟内存分页	跟简单分页一样, 只是不需要一次性将所有进程所需内存都加载到内存中, 按需索取	内存使用效率更高, 巨大的虚拟地址空间	复杂的内存管理
虚拟内存分段	跟简单分段类似, 但是不需要一次性加载所有分段, 按需加载	同虚拟内存分页	复杂的内存管理

分页 逻辑地址与物理地址

逻辑地址是指程序中使用该地址来访问程序; 物理地址是指需要访问的内存真实位于内存中什么位置。

之所以需要逻辑地址是为了方便程序在运行过程中在内存的换进换出过程中, 可以根据当时情况被分配到不同位置。

在真实访问内存的时候, 程序发出的是逻辑地址, 操作系统的内存管理模块需要将逻辑地址转换为物理地址。

以如上分区方案中的固定分区为例子的话, 一个程序只有一个分区, 那么逻辑地址可以是相对于程序起始位置的相对地址, 在转换过程中, 操作系统会在某个寄存器中记录一个该进程加载位置的初始物理地址, 然后将该地址和逻辑地址相加便成为了物理地址。

在如上的简单分页的分区算法中, 要转换逻辑地址就比较复杂了, 对每个进程都需要存储一个逻辑地址分页表到物理地址分页表的hashmap的映射关系, 每次在操作内存的时候, 需要从这个hashmap中获取到真正物理内存的地址再进行访存。

但是这个映射表的存储开销也特别的大, 试想一下, 最简单的实现方案, 就是将所有逻辑地址和物理地址的映射关系都存下来, 这样假设在一个4G的机器上, 每页是4K, 那么一共需要存储4G/4K=1M个页表项, 每个页表项需要存储一个物理帧地址, 每个地址用一个int来存储, 需要32byte, 那么一个进程就需要存储32M空间, 如果一台机器上运行100个进程, 那么久需要3.2G空间, 那这台机器就不用干别的事情了。

但是如上的映射表有一个很大的问题, 就是有意义的表项过于稀疏, 很有可能在1M个页表项中占有极少数会真正有用, 其他页表项都是空置, 因为一个进程往往只会用到少数空间, 导致内存空间极大浪费。

那么为了解决这个问题, 现代操作系统一般使用二级分页模式来管理内存达到节约内存空间的目的。该方案的实现方案是将逻辑页号分成两部分(在上面的例子中, 每部分包含10个bit), 在查找物理页的时候, 首先通过一个寄存器里找到一级页表内存地址, 一级页表内存地址存储的是前10位到二级页表地址的映射, 通过一级页面找到二级页表地址, 二级页表存储的是后10位到物理地址的映射关系, 这样就通过二级页表找到了物理地址。

该方案最主要的节约是, 一级页表项可能只有很少的几个, 如果没分配的内存就不会占据映射表项, 从而节约实际内存。

现代操作系统如上的转换过程都是通过硬件实现, 保证效率。

如上方案是现在主流内存映射解决方案, 但是还是有一个问题, 就是页表映射占用内存会跟虚拟空间大小和进程数成正比。于是在某些操作系统上, 也有另外一种典型的解决方案反向页表结构。

该方案的实现原理是利用一个hash函数, 将虚拟页号转换成物理页号, 如果该物理页号已经被该进程或者别的进程给占用了, 就通过类似二次hash的方式重新找到一个可用的物理页号分配给该进程的虚拟页号。

这样, 页表映射项存储就是固定大小了, 但是付出的代价将会是每次做映射的代价会更大。

分段

分段是指将一个程序所需内存分成多段分别加载, 而不是将一个程序所有所需程序当成一段连续内存统一加载。

现代操作系统一般都用了分段机制, 分段会带来如下一些好处:

1. 有助于简化内存动态增长的应对方案。进程往往分为静态数据和动态数据段, 如果我们把动态部分和静态部分分成不同段的话, 就能保证静态数据部分不受影响, 动态数据也可以更容易找到适合的空间
2. 允许程序可以独立的改变或重新编译, 如动态加载, 就避免每个程序都需要将所有所需程序静态链接进自己的程序
3. 有助于进程间共享

虚拟内存

虚拟内存是指一个进程所需的所有内存不一定要全都在实存里, 可以一部分在辅存里, 在有需要的时候再从辅存中把数据加载到实存里。

虚拟内存带来的好处是可以更充分的利用内存, 因为在进程运行过程当中, 很可能不需要用到全部内存, 只需要用到部分内存; 同时, 对于进程而言, 还可能会让进程拥有比实际内存还大的空间。

虚拟内存带来的开销是每次在内存中读不到空间的时候, 该进程就需要被阻塞, 然后从辅存中读取相应数据, 然后再重新唤醒该进程, 这样会导致操作系统运行进程效率低下。

但是所幸, 经过实际验证, 大部分进程都有局部性原理, 经过精心设计的预加载部分内容以及淘汰算法, 虚拟内存的效率已经被绝大部分操作系统给证实了。

而在操作系统实现虚存管理的逻辑中, 主要考虑如下两点:

1. 内存占用

   内存占用是指一个进程到底能占用多少物理空间。一般分为固定分配策略和可变分配策略。

   固定分配策略是指一个进程占用的物理内存大小是固定的, 可变分配策略是指一个进程所占用的物理内存大小是可以调整的。

   可变分配策略会更合理, 因为不同进程的局部性表现是不一样的, 可以弹性的提高或者降低进程占用物理内存能提高内存利用效率, 但是这会消耗更多的操作系统管理资源。

2. 替换页来源

   替换页来源是指出现缺页的时候, 从哪里找到一个另外的内存页提供给该进程。一般分为局部替换和全局替换两种。

   局部替换是指当一个缺页的时候只在自己进程所占用的内存中找一页来替换; 全局替换是指在所有物理内存中找一页来替换, 而不管该页属于哪个进程。

   根据内存占用和替换算法, 我们可以列出如下虚存管理方式的表格:

   内存占用方案	替换页来源	说明
   固定分配	局部替换	每个进程的固定大小并不好决策, 如果太小, 则导致页错误率太高; 如果太大, 又导致内存浪费过多, 内存中能存下的进程数量有限, 导致整体性能降低
   固定分配	全局替换	不可能, 否则每个进程所占用的空间就发生变化了
   可变分配	局部替换	该方案实现复杂, 但是内存利用效率最高, 但是内存管理成本也最高。发生缺页从自己占用内存中替换一页, 并且会实时动态评估自己占用内存是否合理, 并做动态的增加/减少的动作
   可变分配	全局替换	这个是最容易实现的, 目前绝大部分操作系统都采用了这个方案。该方案的唯一复杂的点在于替换页的选择算法, 这类算法我们下面再讲

3. 替换算法

   替换算法是指确定了替换页来源的情况下, 如何选择一个合适的页面来做替换, 常见算法包括:

   算法	说明
   最佳算法(OPT)	这是理想方案, 不能实现, 只能用来用作基准对比。原理是在所有页中找一个将来最不可能用到的页来作为替换页
   最近最少使用(LRU)	这个是根据局部性原理, 可实现的相对合理的方案。一般认为最近最没有用到的页可能将来用到的概率也不大。该方案实现成本相对较高, 需要为每个页都做一个标记, 并且在寻找替换页的时候需要遍历该标记, 找到最老被使用的替换页
   FIFO	这个方案实现简单, 但是效果一般。因为有可能最早进来的页面也会一直被使用, 被替换了可能对整体性能造成影响
   Clock	这个是相对在FIFO和LRU之间的一个折衷的方案。效果没有LRU好, 但是实现成本也比较简单

参考

1. 操作系统精髓与设计原理. http://book.douban.com/subject/5064311/