一、基本概念

内存管理需要实现：重定位，保护，共享，逻辑组织，物理组织。

• 页框（帧frame）：一个固定长度的内存块。（针对硬件）
• 页（page）：一个固定长度的数据块（程序代码或数据），平时存储在二级存储区（如磁盘）。运行程序是，复制到一个内存页框中（页式）。页与页框的长度相等，常用尺寸：4KB。
• 段（segment）：一个变长的数据块，平时存储在二级存储器。运行程序时，整段加载到一个内存区（段式），或将一段分为多页，分别加载到多帧（段页式）。
• 重定位：进程执行的过程中，将程序地址（逻辑地址）转换为实际的内存地址。
• 保护：避免内存中各进程间有意无意的互相干扰；防止地址越界或操作越权。
• 共享：允许多个进程访问同一内存区域。纯代码共享可节省内存空间，数据共享可实现进程通信。
• 逻辑组织：支持模块化程序设计，有效管理线性内存空间和程序模块。
• 内存：由一系列字节组成的线性地址空间。
• 物理组织：OS在内存和外存之间交换数据。

二、内存管理技术

内存管理技术：分区（固定/动态分区），分页（简单分页/虚拟内存分页），分段（简单分段/虚拟内存分段）。

• 分区式属于连续分配方式，即为一个用户程序分配一个连续的内存空间。将内存划分为若干分区，每个分区只存放一个进程，各进程只能在它所驻留的分区中运行。
• 分页、分段是内存中离散分配进程的各页/段。

1、分区

1.1 固定分区

• 在系统初启时，内存已划分为若干个大小相等或大小不等的分区，并将它们排成一个分区说明表。分区建立后大小、边界、数量不再改变。
• 为进程分配一个满足长度要求的最小空闲分区。
• 分配回收容易，但限制了进程个数和最大长度，易产生(区内)内碎片，内存利用率低

1.2 动态分区

• 从可用内存中划出进程所需容量的一块连续区域并分配，其余部分作为一个新空闲区。运行完后回收，若与其它空闲区相邻则合并。易产生(区间)外碎片。
  

1.2.1 碎片与压缩

碎片fragmentation：

• 内碎片：所分配的空闲区一般比所要求的空间稍大。
• 外碎片：经过一段时间的分配与回收后，内存中存在许多很小的空闲块，由于地址不连续而无法分配。

通过压缩compaction解决外碎片：

• 向内存的一端移动进程，使碎片在另一端合并成一个大空闲区。费时，需动态重定位。
• 为了减少碎片：系统设一最小空闲区长度size，若即将产生的新空闲区小于size，则不再划分，而将整个空闲区分配。 

1.2.2 分配策略

首次适配（First Fit）

• 链表结构：空闲区按起始地址递增顺序排列。
• 分配时，从链首开始查找，从第一个满足要求的空闲区中划分出进程需要的大小并分配，其余部分作为一个新空闲区。
• 低地址端遗留许多碎片；高地址端有大空闲区。

下次适配（Next Fit）

• 链表结构：空闲区按起始地址递增顺序排列。
• 分配时，从上次扫描结束处继续查找，从第一个满足要求的空闲去中分配。
• 平均查找时间缩短，空间利用比FF均衡。

最佳适配（Best Fit）

• 链表结构：空闲区按分区大小递增顺序排列。
• 分配时，从链首开始查找，第一个满足要求的空闲区就是满足要求的最小空闲区，划分之。
• 链首部碎片多，查找费时。回收合并时复杂。

最差适配（Worst Fit）

• 链表结构：空闲区按分区大小递减顺序排列。
• 分配时，从链首开始查找，从第一个空闲区不能满足要求时分配失效，否则从第一个空闲区中切出需要的大小分配。
• 小碎片较少，但最大的空闲区也不会很大。

！#: FF,NF,BF比较：FF最常用

    内存分配上，FF最快。（不需调整新空闲区位置）

    内存回收上，FF最佳。（合并空闲区容易）

    NF比FF更均衡地利用内存，碎片遍布内存，但使高地址端的大空闲区很快被划分，压缩次数多。

    查找最合适空闲区时，BF最快，但碎片最多，压缩最频繁。回收时，合并相邻空闲区可能要遍历空闲区链表。通常，BF的性能最差。

？#：设空闲分区的平均个数是h，则：

    最佳适配，首次适配，下次适配的平均查找长度时h/2。

    最差适配的平均查找长度时1。

2、伙伴系统

UNIX、Linux采用伙伴系统分配内存页框(帧)。

• 伙伴：两个相邻的帧块。每块大小必须相同，包含2 i个帧（i=0, 1, 2, 3, …）。如帧长4KB：帧数1,2,4,8,16,32...，尺寸4,8,16,32,64,128KB...
• 将更大块的物理内存对半分裂，得到两个伙伴。

具体算法过程：

• 分配时，先查找是否有最合适尺寸s的空闲块，（若有则分配。如需分配60KB，则s=64KB）。
• 若没有则查看是否有长为2s的空闲块，仍没有则查找长4s、8s 、16s……的块，直至找到一个空闲块。
• 然后把该块对半分为两个伙伴L和R。R保留作为新空闲块。如果L长为s则直接分配。如果L仍过大，则再次对半分裂为L’和R’……，直至得到长为s的左伙伴，将其分配。所有右伙伴都被保留作为新空闲块。
• 回收时，如果该左（右）伙伴块的右（左）伙伴块也空闲，则这一对伙伴合并为一大空闲块。合并是递归的，直到没有相邻的空闲伙伴为止。

3、重定位

进程进行时，动态加载及重定位：

• 在运行过程中，每次要访问内存单元之前，把有关的逻辑地址转成成实际的物理地址。
• 硬件支持：基址寄存器+界限寄存器
• 加载模块装入内存后可搬迁，可实现虚拟内存。

重定位：将逻辑地址转换为物理地址。

逻辑（相对）地址：程序中引用的地址，从0顺序编址。

物理（绝对）地址：数据在内存中的单元地址。

存储保护：用两个寄存器标识合法访问地址访问。

基址+界限（Base register+Bounds register）:最小合法内存地址+最大合法内存地址。

基址+限长（Base register+Limit register）:最小合法内存地址+地址范围的大小。

Q：采用固定分区管理的最大缺点是内存利用率不高。

可变分区的地址转换公式：物理地址=机制寄存器值+逻辑地址

4、分页

页框（帧frame）：内存划分为大小相等的物理块。

页面（页page）：进程的逻辑地址空间划分为同样大小的逻辑块。

Q：逻辑地址A，所在页号p=INT(A/L)       页内偏移d=A mod L

页表：记录进程的每个页存放在哪一个内存帧。

• 进程装入内存时，分配帧，并创建页表。
• 进程运行完后，释放帧，销毁页表。
• 每个进程有一张自己的页表。页表位于内存。

## 位图：每一bit表示一个内存帧状态。0-空闲，1-占用。

内存帧号i=字号*字长+位号

字号=INT（帧号/字长），位号=帧号mod字长。

4.1页式地址转换

页式地址转换：由逻辑地址（页号，页内偏移量）和页表，得到物理地址（页框号，偏移量）。

页式地址转换步骤：

    ① 根据页号找页表，得到相应页的内存帧号；
    ② 物理地址＝帧号×帧长＋页内偏移量

5、分段

程序员或编译器将程序按逻辑上有完整意义的段划分。段长不固定，每段有自己的段号，每段都从0开始编址。共享保护容易。

逻辑地址：<段号s，段内偏移量d>

段式管理的内存分配与释放：

• 每段占用一块连续的内存区，各段不必连续。
• 无(段内)内碎片，有(段间)外碎片。
• 段的分配和回收算法基于动态分区，如 FF、NF、BF、WF。回收时相邻空闲区合并。

段表：每个进程有一个段表。电表结构如下;

硬件支持：

• 段表基址寄存器：根据此地址找到段表。
• 段表长度寄存器：当段号s＜段表长度时，段号s合法。如果段号s≥段表长度，则越界。

段式地址转换步骤：逻辑地址->物理地址

• 在段表中查找段号，得到相应段的内存起始地址；
• 段内偏移量和该段长度比较，如果段内偏移量≥段长，则越界，这个逻辑地址无效。
• 物理地址＝段起址＋段内偏移量。

！# 段基址B，段长L，合法的逻辑地址A是 0<=A < L

    合法的物理地址R是 B <= R <B+L