内存管理笔记(分页，分段，逻辑地址，物理地址与地址转换方式)
http://www.cnblogs.com/felixfang/p/3420462.html本文内容参考自如下博客与书籍：
http://blog.csdn.net/windowseight/article/details/8279863
http://bbs.chinaunix.net/thread-2083672-1-1.html
http://blog.csdn.net/erazy0/article/details/6457626#comments
http://blog.csdn.net/drshenlei/article/details/4261909
http://duartes.org/gustavo/blog/post/memory-translation-and-segmentation
《操作系统概念》第六版中文版，高等教育出版社，第九章，郑扣根译。
《Operating System Concepts》7th Edition, 高等教育出版社。
文中很多处是根据自己理解所写，若有错误，欢迎指出和探讨。
1. 物理地址和逻辑地址
物理地址：加载到内存地址寄存器中的地址，内存单元的真正地址。在前端总线上传输的内存地址都是物理内存地址，编号从0开始一直到可用物理内存的最高端。这些数字被北桥(Nortbridge chip)映射到实际的内存条上。物理地址是明确的、最终用在总线上的编号，不必转换，不必分页，也没有特权级检查(no translation, no paging, no privilege checks)。
逻辑地址：CPU所生成的地址。逻辑地址是内部和编程使用的、并不唯一。例如，你在进行C语言指针编程中，可以读取指针变量本身值(&操作)，实际上这个值就是逻辑地址，它是相对于你当前进程数据段的地址（偏移地址），不和绝对物理地址相干。
为什么会有这两种地址？
个人觉的原因在于逻辑地址分配更加灵活，可以允许不唯一，看起来也较为直观，例如，一段代码中分配数组，逻辑地址上是连续的，然而在物理地址上，这个数组所占用的页可能分散开来，物理地址上就是不连续的，这样对程序的可理解性上有影响。另外，有了逻辑地址这个概念，才能使用虚拟内存技术。
2. Paging，分页内存管理方案
(1) 分页的最大作用就在于：使得进程的物理地址空间可以是非连续的。
逻辑地址：页号+页内地址
物理地址：块号+页内地址
根据逻辑地址转物理地址：先将逻辑地址分成页号和页内地址两部分，根据页号查询页表得到块号，则物理地址=块号+页内地址。
以一个例子的形式讲解逻辑地址到物理地址的转换：
某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：
页号 |
物理块号 |
0 |
3 |
1 |
7 |
2 |
11 |
3 |
8 |
则逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。
解题过程：
首先要知道页式存储管理的逻辑地址分为两部分：页号和页内地址。物理地址分为两部分：
关系为：逻辑地址＝ 页号＋页内地址
物理地址＝ 块号＋页内地址；
分析题：已知：用户编程空间共３２个页面，２ˆ５ ＝ ３２ 得知页号部分占５位，由“每页为1KB”，1K=210，可知内页地址占10位。
由“内存为16KB”，２^４＝１６得知块号占4位。
逻辑地址0A5C（H）所对应的二进制表示形式是：００００１０１００１０１１１００，后十位１００１０１１１００是页内地址，
０００１０为为页号，页号化为十进制是２，在对照表中找到２对应的物理块号是１１,１１转换二进制是１０１１，即可求出物理地址为１０１１１００１０１１１００，化成十六进制为２Ｅ５Ｃ；
即则逻辑地址0A5C(H)所对应的物理地址是２Ｅ５Ｃ；
采用分页技术不会产生外部碎片(内存都被划分为帧)，但可能产生内部碎片(帧已经是最小单元，因此帧内部可能有空间没有用到)。
按概率计算下来，每个进程平均可有半个帧大小的内部碎片。
(2) 页表的硬件实现
上一小节中写到页表是逻辑地址转化到物理地址的关键所在。那么页表如何存储？
每个操作系统都有自己的方法来保存页表。绝大多数都会为每个进程分配一个页表。现在由于页表都比较大，所以放在内存中(以往是放在一组专用寄存器里)，其指针存在进程控制块(PCB)里，当进程被调度程序选中投入运行时，系统将其页表指针从进程控制块中取出并送入用户寄存器中。随后可以根据此首地址访问页表。
页表的存储方式是TBL(Translation look-aside buffer, 翻译后备缓冲器)+内存。TBL实际上是一组硬件缓冲所关联的快速内存。若没有TBL，操作系统需要两次内存访问来完成逻辑地址到物理地址的转换，访问页表算一次，在页表中查找算一次。TBL中存储页表中的一小部分条目，条目以键值对方式存储。
(3) 页表的数据结构
a.
今年是2013年，现有的笔记本电脑，内存地址空间一般为2^32字节以上。对于具有32位逻辑地址空间的计算机系统，如果系统的页大小为4KB(2^12B)，那么页表可以拥有2^(32-12)个，也就是一百多万个条目，假设每个条目占有4B，那每个进程都需要4MB的物理地址空间来存放页表本身。而且，页表本身需要分配在连续内存中。
为此，Hierarchical Paging(层次化分页)被提出，实际上就是将页号分为两部分，第一部分作为索引，第二部分作为页号的偏移。
以一个4kb页大小的32位系统为例。一个逻辑地址被分为20位的页码和12位的页偏移。因为要对页表进行再分页，所以该页号可分为10位的页码和10位的页偏移。这样一个逻辑地址就表示如下形式：
地址转换过程如下：
地址由外向内转换，因此此方法也被称为forward-mapped page table(向前映射表)。
b. Hashed Page Tables 哈希页表
处理超过32位地址空间的常用方法是使用hashed page table(哈希页表)，并以虚拟页码作为哈希值。哈希页表的每一条目都包括一个链表的元素，这些元素哈希成同一位置。每个元素有三个域：虚拟页码，所映射的帧号，指向链表中下一个元素的指针。
个人看来，哈希页表的地址转换方式，实际上是Chaining(链接)方式，也就是一种哈希函数的溢出处理方式(另一种溢出处理方式叫做Open Addressing，开放寻址)，具体过程如下：
逻辑地址需要大于32bit的地址空间来表示，但是操作系统仍只有32bit来表示地址。此时人们便想到虚拟页地址，虚拟地址可以在32bit表示范围之内，然后利用哈希函数完成逻辑地址到虚拟地址的映射，由于虚拟地址更少，哈希函数会出现溢出，这里使用Chaining来解决溢出。
逻辑地址中的页号(下图中的p)经过哈希函数的计算，算出虚拟地址中的页号，根据虚拟页号可以在哈希表中以O(1)方式寻址，用p与链表中的每一个元素的第一个域相比较。如果匹配，那么相应的帧号就用来形成物理地址。如果不匹配，就对链表中的下一个节点进行比较，以寻找一个匹配的页号。
c. Inverted page table 反向页表
时间关系，这段暂时略过。
3. Segmentation，分段内存管理方案
采用分页内存管理有一个不可避免的问题：用户视角的内存和实际内存的分离。设想一段main函数代码，里面包含Sqrt函数的调用。按照编写者的理解，这段代码运行时，操作系统应该分配内存给：符号表(编译时使用)，栈(存放局部变量与函数参数值)，Sqrt代码段，主函数代码段等。这样，编写者就可以方便地指出："函数sqrt内存模块的第五条指令"，来定位一个元素。而实际上，由于采用Paging的管理方式，所有的一切都只是散落在物理内存中的各个帧上，并不是以编写者的理解来划分模块。
Segmentation的内存管理方式可以支持这种思路。逻辑地址空间由一组段组成。每个段都有名字和长度。地址指定了段名称和段内偏移。因此用户通过两个量来指定地址：段名称和偏移。段是编号的，通过段号而非段名称来引用。因此逻辑地址由有序对构成：
<segment-number,offset>(<段号s, 段内偏移d>)
段偏移d因该在0和段界限之间，如果合法，那么就与基地址相加而得到所需字节在物理内存中的地址。因此段表是一组基地址和界限寄存器对。
例如下图，有5个段，编号0~4，例如段2为400B开始于位置4300，对段2第53字节的引用映射成位置4300+53=4353。而段0字节1222的引用则会触发地址错误，因为该段的仅为1000B长(界限为1000)。
4. 合并分段和分页的管理方案
在现有的Intel兼容计算机(x86)上，采用的内存管理方案是分段和分页合并的管理方案。
在这个方案中，逻辑地址，如前一节中所说，是由一个段标识符加上一个指定段内相对地址的偏移量，表示为 [段标识符：段内偏移量]。
这样的逻辑地址转换的过程是怎样呢？如下图所示：
当CPU要执行一条引用了内存地址的指令时，转换过程就开始了。第一步是把逻辑地址转换成线性地址。但是，为什么不跳过这一步，而让软件直接使用线性地址（或物理地址呢？）原因主要是因为：
(1) Intel的更新是渐进式而非革命式，新的处理器需要兼容和保留过往的设置。具体的原因，博文Memory Translation and Segmentation (http://blog.csdn.net/drshenlei/article/details/4261909) 中讲的较为清楚。
(2) 如上节所说，采用段内存管理，可以跟方便地进行地址保护(同一类型的地址逻辑地址在一起)。
下面讲逻辑地址到线性地址的部分。
在IBM OS/2 32位版本的操作系统，和Intel 386的环境下。操作系统采用的内存分配方式就是分段和分页合并的方式。
逻辑地址的实际上是一对<选择符，偏移>。
选择符的内容如下：
从左开始，13位是索引(或者称为段号)，通过这个索引，可以定位到段描述符(segment descriptor)，而段描述符是可以真正记载了有关一个段的位置和大小信息， 以及访问控制的状态信息。段描述符一般由8个字节组成。由于8B较大，而Intel为了保持向后兼容，将段寄存器仍然规定为16-bit(尽管每个段寄存器事实上有一个64-bit长的不可见部分，但对于程序员来说，段寄存器就是16-bit的)，那么很明显，我们无法通过16-bit长度的段寄存器来直接引用64-bit的段描述符。因此在逻辑地址中，只用13bit记录其索引。而真正的段描述符，被放于数组之中。
这个内存中的数组就叫做GDT(Global Descriptor Table，全局描述表)，Intel的设计者门提供了一个寄存器GDTR用来存放GDT的入口地址。程序员将GDT设定在内存中某个位置之后，可以通过LGDT指令将GDT的入口地址装入此寄存器，从此以后，CPU就根据此寄存器中的内容作为GDT的入口来访问GDT了。
除了GDT之外，还有LDT(Local Descriptor Table，本地描述表)，但与GDT不同的是，LDT在系统中可以存在多个，每个进程可以拥有自己的LDT。LDT的内存地址在LDTR寄存器中。
在之前图中的TI位，就是用来表示此索引所指向的段描述符是存于全局描述表中，还是本地描述表中。=0，表示用GDT，=1表示用LDT。
RPL位，占2bit，是保护信息位，还没有仔细了解过这一块，暂时先不写。
找到，段描述符后，加上偏移量，便是线性地址。转换过程如下：
在Intel 386的环境下，线性地址转换为物理地址的过程，和第二节分页式内存管理中，层次分页中，逻辑地址转换为物理地址的方法类似。如下图。
Intel 80386的地址转换全过程如下图：
内存管理部分是操作系统的核心功能之一，这次将理论部分整理出来，一是为了复习，二也是为了提纲挈领地为深入学习操作系统做准备。
文中的图片均非本人原创，主要来自文章开头所引用的博文，以及参考书籍中的图片。若有侵权行为，请指出，博主将尽快移除。