操作系统 内存管理

在考虑操作系统如何管理内存之前，你先要知道：

1. 程序是存在硬盘中的二进制文件，需要运行时会经过CPU调度程序将其copy到内存后成为进程

• cpu可以直接访问的大容量存储只有内存

• 内存管理的目的在于快速访问内存，第二在于内存的安全访问（各个进程间的内存不可以随意互相访问）

注：程序是如何形成的

源程序经过编译器变成一个个模块,这些模块和经过 链接器，经过加载模块之后，再和系统库一起经过加载器加载，最后在和动态链接的系统库链接成为二进制程序

这期间有

动态加载技术：不是将所有模块一起加载到内存中，而是按需加载，一个子程序只有当被其他子程序调用时才会被加载。提高了空间利用率

动态链接于共享库：不同程序程序中很多功能其实都是相似的，而这些重复的功能模块加载到内存中无疑要
占用很大一部分物理内存，于是我们把他们抽调出来，形成专用的共享库。这样不仅节省空间，更利于程序的更新

对于1： 根据内存管理方案，调入内存中的进程在执行时可以再内存和磁盘间移动，等待调入内存的进程形成一个输入队列

编译器将符号地址绑定在了可重新定位的的地址（比如本模块开始第14字节）。链接程序或者加载程序再将这些可重定位的地址绑定位绝对地址（如74104）。每次绑定都是一个地址空间到另一个的映射

对于2 ：CPU只能访问内存，那么CPU发出的指令肯定都是基于内存来编址的。再考虑到，编程时总不可能指定实际内存地址，这样在的程序经不起环境改变的考验。
为了解决这样的问题，计算机采用了 逻辑地址 和 * 物理地址* 的设计：

cpu 产生的地址通常称为逻辑地址，而内存单元所看到的地址通常称为物理地址

可以这么想：逻辑地址就是操作系统用户编程时无视不同机器物理地址的不同所设置的屏蔽，编程时不必考虑实际的物理内存分配是很happy的...... 实际使用时会有内存管理单元来把逻辑内存映射为物理内存

对于3 使用高速缓存catch可以增加访存速度，增加基地址和界限地址寄存器，一个可用的方案就是逻辑地址+基地址寄存器地址，如果这个值不大于界限地址寄存器里的值，那么这就可作为物理地址，而基地址寄存器和界限地址寄存器是由操作系统初始化和指定的，用户没有权限去操作。这样就保证了第二点

只要我们使用内存，我们就必然会面临一个问题，内存不够用！！！

这一点是很头疼的，尤其是对于大型单机游戏来说，这就需要我们用到另一个技术交换

交换就是在某个进程在不被使用的时候被交换到备份存储中（一般是磁盘）这样的过程叫滚出.....
需要他的时候再将它加载回来..这样的过程叫...滚入....而且这样的交换总是在相同的物理空间上，通俗的讲就是从哪滚出的，再从哪滚入...

这样的交换其实对效率没有什么良好的帮助，现在UNIX系统就是只要当内存被填满了才会启动交换，平时是不会的

内存必须容纳操作系统和用户的一系列进程，那么怎么才能有效的分配这一济源呢？

这里将提到常用的几个方法

连续内存分配

• 多分区方法，将内存分配成许多个大小相同的模块，这种不考虑具体使用情况而异想天开的平均分配主义已经不再使用了，因为这样造成的浪费是巨大的..其一，进程的大小可能相差甚远，单位块大小不好决定啊。

• 可变分区：操作系统有一个表，用于记录哪些内存可用和哪些内存已被占用。可用内存称为孔，进程进来之后，内存管理单元会帮其找到合适的孔（注1），如果孔还有剩余，那么这个孔..还是孔，变成了小孔而已...
  当内存被释放时，被释放出的内存重新成为孔..如果相邻的内存也是孔..那么，这两个孔就合体成为大孔..

注1：这样的策略有最先适应，最佳适应，最差适应：

最先适应，找到的一个适应的孔
最佳适应；遍历所有孔，找到满足要求的最小孔
最差适应：遍历所有孔，分配最大孔
效率上看 最先》最佳》最差

这两种方案都是常用的连续内存分配方法，但是连续内存分配必然会面临一个问题：碎片问题，每次分配内存，都有部分内存没有被真正使用，如多分区方法中一个分区大小为4KB ，而一个内存是 4KB +1B这样的状态，这种情况下必须要给这个进程分配两个内存块，但是第二个内存块明显存在内存的浪费！这样的碎片称为内部碎片 ，而可变分区方案中，总有一些孔被很小，没有进程能被分配进去，这样的内存称为：内部碎片

那么这样的碎片多吗？...有这样的一个原则--50%规则，有N的内存空间将有0.5N的外部碎片..
解决的方法有

紧缩：把所有随便集中，但是这样先不考虑 重定位的问题。这样的开销也是不可接受的
使用非连续的内存分配

非连续内存分配

分页：将物理内存分为大小固定的块，称为帧（ frame）逻辑地址分为同样大小的块，称为页（page）

由CPU生成的地址分为两部分，页号和页偏移，页号作为页表的索引，页表内存入每页所在物理地址的基地址，基地址于页偏移组合就成为了物理地址，这样就可以避免外部碎片的问题（但内存碎片仍然存在）

当程序需要执行的时候，他将检查该进程的大小，进程的每一页都需要一帧，如果帧够，那么分配，并将帧号放入进程的页表中

操作系统管理内存，所以它必须知道哪些帧已经使用了，哪些没被使用。这个信息存储在帧表中

硬件支持：绝大多数操作系统为每一个进程维护一个页表。页表的指针与其他信息一起存入进程控制块中。
访存操作可能是最频繁的操作了，所以效率是十分关键的。基于效率考虑，页表最好不要存在一般内存中，这样会使得一次访存操作变成消耗两次访存的时间，效率就很低了。对此，我们可以采用专用高速寄存器来存储页表，对于页表比较小的情况下这样做是可以的。但现代操作系统页表通常很大...之后采取的方法是将页表存入内存中，然后将其基地址存入寄存器，之后按照偏移地址来存...这样会很慢...于是我们就采用了比较小但很快的专用缓存来存页表 ，称为转换表缓冲区

TLB相当于一个哈希表，用KEY（页号）可以快速找到VALUE（帧号），找到了之后访存，找不到就去内存中找真正的页表，找到之后用一定的算法（最近最少使用）替换到TLB中方便下次寻找

保护： 通过页表中的保护位来做，确定进程对其是可读还是可写的

采用这样的结构，还可以共享某些页，这样又节省了内存

• 页表结构

  • 层次页表
    现代操作系统中的逻辑空间地址十分大.后果是页表也十分大，怎么样在内存中存储页表呢？一种方法是两级分页算法，将页再分页，对于64位的系统甚至可以再分页

  • 哈希页表
    每个元素有三个域 1. 虚拟页码 2. 所映射的帧号 3. 指向链表中下一个元素的指针

虚拟地址中的虚拟页号转换到哈希表中，用虚拟页号与链表中的每一个元素的第一个域相比较。如果匹配，那么相应的帧号就用来形成物理地址；如果不匹配，那么就去对链表中下一个节点进行比较

* 反向页表

分段

这是为了方便用户角度来看的，将一维的地址空间二维化，原先是这个程序的第XX字节，这样的一维查找，而分段使得 这个程序 XX段的 YY字节 成为二维查找

当然这样的方式需要特别的结构..段表的支持