内存管理

一、内存管理的基本需求

重定位

数据（代码）经常换入换出，需要能定位到数据（代码）的位置

保护

安全访问

共享

多进程共享

逻辑组织

物理地址是连续的，这不符合程序构造的方法，可以把数据组织称模块，有以下好处。
模块可以独立编译
分模块设置不同的保护界别
在模块级别提供共享，更符合用户看待问题的方式

物理组织

存储的层级结构，以及在不同存储间移动数据

二、内存分区

技术	说明	优势	弱点
固定分区	内存被划分成固定大小的分区，进程装入大于或者等于自身大小的分区中	实现简单，开销小	1. 内部碎片 2.活动进程的最大数目有限制
动态分区	分区动态创建，进程装入与自身大小正好相等的分区中	内、外部碎片都比较小	有内部碎片，也有外部碎片
伙伴系统	固定分区和动态分区的折中。内存被分成大小为2^K的块，L<= K <=U	无内部碎片	有外部碎片，需要压缩外部碎片
简单分页	内存被分成大小相等的页框，进程被分成与也框大小相等的页。进程中所有页装入到内存中不一定连续的页框中	无外部碎片	少量内部碎片
简单分段	进程分成许多段，把进程所有段装入内存中不一定连续的动态分区中	无内部碎片，相对于动态分区，提高了内存利用率	有外部碎片
虚拟内存分页	不需要装入进程的所有页，非驻留页需要时自动载入，其他同简单分页	无外部碎片，支持更高道数的多道程序	复杂的内存管理
虚拟内存分段	不需要装入进程的所有段，非驻留段需要时自动载入，其他同简单分段	无外部碎片，支持更高道数的多道程序。支持保护和共享	复杂的内存管理

1. 固定分区

把物理内存分割成大小相等小模块，或者固定大小的几个模块，这个方案主要有以下问题：

1.1 放置算法

把每个进程分配到能够容纳它的最小分区.

每个分区一个调度队列, 局部最优，全局差，比如： 16M 分区空闲，但是 7M 的进程，只能等待8M的分区，不能直接放入16M的分区
所有进程只提供一个队列，

1.2 缺点

有内部碎片，内存利用率低
程序可能太大，单个分区装不下，这是需要使用覆盖技术（程序部分数据装入内存块，其余部分需要的时候，再载入，覆盖掉内存中已有数据）
分区数目固定，限制了活动进程的数目

2. 动态分区

当进程被载入时，系统自动分配一块和它所需容量完全相等的内存。由于有外部碎片，所以放置算法就比较重要

2.1 放置算法

最佳适配

选择与进程大小最接近的块。效率低，内部碎片小，但是外部碎片大

首次适配从头开始扫描，选择大小足够的第一个可用块。会在内存前部分形成小空间，每次分配都要扫描到这部分。效率低
下次适配从上一次分配的位置开始扫描，选择大小足够的第一个可用块。会导致在内存末尾分配空间，会导致末尾的大块很快被分裂成小块。所以需要更多的压缩

3. 伙伴系统

伙伴系统是固定分区和可变分区的折中。内存被分成大小为2^K的块，L<= K <=U , 其中

2^L 表示分配的最小块的尺寸
2^U 表示分配的最大块的尺寸，通常是可分配的整个内存块的大小假设请求大小为s, 如果 2^(U-1) <= s <= 2^U. 则分配整个空间，否则，内存做二等分，得到两个 2^U-1 的块，如果 2^(U-2) <= s <= 2^(U-1), 则分配其中一块，否则取其中一块，继续二等分，重复上面的循环在任何时候，伙伴系统为大小为 2^i 的块维护一个列表。一个块可以从 2^(i+1) 剥离出去，分裂成两个2^i的块，也可以从两个2^i 的块合并成一个2^(i+1)的块

javascript

void get_hole(int i){
    if(i==(U+1)) <failure>
    if (<i_list empty>){
        get_hole(i+1);
        <split hole int buddies>
        <put buddies on i_list>
    }
    <take first hole on i_list>
 }

4. 分页

内存被分成大小相等且很小的页框，每个进程被分成同样大小的页。较小的进程需要较少的页，较大的进程需要较多的页。当进程被载入时，它的所有页被载入可用的页框中，并建立一个页表。页大小和页框大小必须是2的幂。以便更容易表示相对地址。相对地址用页号+偏移量表示.

逻辑地址转换成物理地址需要经过地址转换，也就是通过查找页表，把页号转换成对应页框的基地址。这种转换是通过页表来完成的

4.1 地址转换逻辑

考虑一个n+m位的地址，最左边位是页号。最右边的m位是偏移量

提取页号，即逻辑地址最左面的n位
以这个页号为索引，查找进程页表中相应的页框号k
物理地址为 k*2^m + 偏移量

5. 分段

进程被分成许多段，段的大小不需要相等。当一个进程被调入时，他的所有段都装入内存中的可用区域，并建立一个段表分段和分区的核心区别在于，段的大小是不固定的

虚拟内存

virtual_memory.md

内存管理 ​

一、内存管理的基本需求 ​

二、内存分区 ​

1. 固定分区 ​

1.1 放置算法 ​

1.2 缺点 ​

2. 动态分区 ​

2.1 放置算法 ​

3. 伙伴系统 ​

4. 分页 ​

4.1 地址转换逻辑 ​

5. 分段 ​

虚拟内存 ​