OS 内存管理

内存管理的目标是：一方面实现内存分配、内存回收等基本内存管理功能；另一方面要提高内存空间的利用率土和内存的访问速度。

存储器的层次结构

存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构。

程序的执行遵循 局部性原理。程序执行的局部性原理指出：程序在执行时呈现局部性规律，即在一段较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。

程序的链接和装入

程序的链接

静态链接（Static Linking）：在程序运行前，用链接程序将目标模块链接成一个完整的装入模块。静态链接程序的任务一是对逻辑地址进行修改，二是变换外部调用符号。

动态链接（Runtime Dynamic Linking）：可将某些目标模块的链接推迟到这些模块中的函数被调用执行时才进行。

程序的装入

• 绝对装入方式。
• 可重定位装入方式（静态重定位）。
• 动态运行时装入方式（动态重定位）。

连续分配存储管理方式

单一连续分配

单一连续分配方式适用于单用户、单任务的操作系统，它把内存分为系统区和用户区。系统区仅供操作系统使用，用户区供用户使用。

固定分区分配

1. 划分分区的方法

2. 支持固定分区分配的数据结构

3. 固定分区分配的过程

动态分区分配

基本分页存储管理方式

分页存储管理的基本原理

1. 基本概念

页（Page）：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页。

页框（Page Frame）：将物理内存空间分成与页大小相同的若干个存储块，称为页框或页帧。

分页存储：在为进程分配内存时，以面框为单位将进程中的若干页分别装入多个可以不相等邻接的面框中。

页内碎片：进程的最后一页一般装不满一个页框，而形成了不可利用的碎片，称为页内碎片，也是一种内部碎片。

页表（Page Table）：是系统为进程建立的数据结构，页表的作用是实现从页号到页框号的映射。

2. 基本分页存储管理方式中的地址结构

若 A 为逻辑地址，L 为页大小，P 为页号，W 为页内偏移量，则有以下计算关系：

1
2

P=INT(A/L)
W=MOD(a/L)

3. 分页地址变换

地址变换的过程：

• 进程执行，PCB 中页表起始地址和页表长度送 CPU 的页表寄存器。
• CPU 访问逻辑单元 A。
• 由分页地址变换硬件自动将 A 分为页号和页内偏移两部分。
• 由硬件检索页表，等到 A 所在的页对应的页框号。
• 页框号和页内偏移地址送物理地址寄存器，计算物理地址。物理地址=页框大小*页框号+页内偏移量。

4. 页大小的选择

在分页系统中，页的大小是由机器的 体系结构 和 操作系统 共同决定的。

一般页的大小为 2 的整数次幂。在目前的计算机系统中，大多选择 4KB 大小的页。

影响页大小设计的因素：

• 管理内存的开销。
• 内存的利用率。

快表

为了减少两次访存带来的时间开销，减少 CPU 在有效访存上的时间开销，提高访存速度，在硬件上引入了快表机制。

1. 快表

快表：也称转换后援缓冲（TLB - Translate Look-aside Buffer），是为了提高 CPU 访存速度而采用的专用缓存，用来存放最近被访问过的页表项。

TLB 是关联的快速闪存。TLB 的条目由两部分组成：键和值，键对应页号，值对应页框号。TLB 条目数有限，在 64~1024 个之间。

2. 引入 TLB 之后的地址变换过程

• CPU 产生分页的逻辑地址页号和页内偏移后，将该逻辑地址的页号提交给 TLB。
• 查找 TLB，如果找到页号，则把该页所在的页框号用于形成物理地址。否则（TLB 失效）查找内存页表，从内存页表中找到相应的页表项，读取页所在的页框号，以形成物理地址。
• 如果所查找的页表项不在 TLB 中，在访问完内存页表后，要把找到的页表项中的页号和页框号写到 TLB 中。如果 TLB 中的条目已满，系统会根据某种策略（如最近最少使用替换）选择一个 TLB 中的条目，用刚访问的页表项信息替换选中的这个 TLB 条目。

3. 引入 TLB 的性能分析

在 TLB 中找到某一个页号对应的页表项的百分比称为 TLB 命中率。

两级和多级页表

从系统性能考虑，不希望用太大的连续地址空间存放页表，解决的办法就是把页表再分页，形成两级或多级页表。

1. 两级页表

2. 多级页表结构

反置页表

1. 反置页表

2. 反置页表的地址映射

地址映射过程：

• 根据进程号和页号找到页框号。
• 物理地址=页框号*页框大小+页内偏移地址。

空闲面框的管理

1. 使用位图管理空闲页框

2. 使用空闲页框的链表

基于分页的虚拟存储系统

虚拟存储器：指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。

虚拟存储技术实现的基本思想：只把进程的一部分装入内存。进程执行过程中，CPU 访问内存时如果发现所访问的内存不在内存中，则通过异常处理将所需要的内容从外存调入内存。

请求调入：将进程的一部分装入内存，其余的部分什么时候需要，什么时候请求系统装入。

置换功能：如果在请求系统装入进程在外存中的某一部分时，没有足够的内存，则由操作系统选择一部分内存中的进程内容换出到外存，以腾出内存空间把当前需要装入到内容调入到内存。

虚拟存储技术的优点：

• 提高内存利用率土。
• 提高多道程序度。
• 把逻辑地址空间和物理地址空间分开，使程序员不用关心物理内存的容量对编程的限制。

虚拟存储系统的特点：

• 离散性。
• 多次性。
• 对换性。
• 虚拟性。

请求分页中的硬件支持

页表

页表是支持请求分页系统最重要的数据结构，其作用时记录描述页的各种数据，包括在实现逻辑地址到物理地址映射时需要的页号和页框号的对应关系。

对页表项中的各字段说明：

• 页框号：存放页所在的页框号。
• 状态位 P：用来标识页是否在内存中。
• 访问字段 A：用户记录页最近被访问的情况。
• 修改位 M：用于标识页最近是否被修改过。
• 保护位：用于标识页的访问权限。

缺页异常机构

地址变换

页分配策略

1. 最少页框数

最少页框数：指能保证进程正常运行所需要的最少面框数。

2. 页分配和置换策略

固定分配策略：指在进程从创建到撤销的过程中，为进程分配的页框数保持不变。

可变分配策略：指在进程从创建到撤销的过程中，为进程分配的页框数是可变的。

局部置换：指发生置换时，只从请求调页进程本身的内存页中选择一个被淘汰的页，以腾出内存页框，装入请求调入的页。

全局置换：指发生置换时，从系统中所有进程的内存页中选择被淘汰的页。

页分配和置换策略：

• 固定分配局部置换。
• 可变分配全局置换。
• 可变分配局部置换。

3. 分配算法

操作系统为进程分配的页框数通常都是大于最少页框数。

页框分配算法：

• 平均分配算法：采用平均分配算法，如果系统中有 n 个进程，m 个可供分配的内存页框，则为每个进程分配 INT(m/n) 个页框，其余的 MOD[m/n] 个页框可以放入空闲页框缓冲池中。该算法的缺点是不考虑进程规模，可能使大进程分配到的页框与小进程一样多。大进程能进入内存的页数占本进程页总数的比例远远小于小进程，大进程可能因此频繁缺页。
• 按比例分配算法：为进程分配的页框数=进程页数/所有进程页数的总和*页框数。

在两个进程之间按比例分配 40 个页框，进程 p1 大小为 80 页，进程 p2 大小为 240 页，则为 p1 分配 10 个页框，为 p2 分配 30 个页框，则计算如下：

• 为 p1 进程分配的页框数=80/(80+240)*40=10。
• 为 p2 进程分配的页框数=240/(80+240)*40=30。

按比例分配算法的思想是为了优先权高的进程分配较多的页框数，为优先权低的进程分配较少的页框数。

页调入策略

何时调入页

系统可以设计成只有在进程需要时才将页调入内存。

在实际系统中，通常是在调入缺页时，把与所缺页相邻的若干页也调入内存中。

从何调入页

• 从对换区调入：对换区中的页是进程运行前从文件区复制到对换区的。
• UNIX 方式：没有被访问过的页都直接从文件区调入。换出页都存放在对换区，曾经运行过而又被换出的页从对换区中调入。

页调入过程

页置换算法

1. 最佳置换算法和先进先出置换算法

2. 最近最久未使用 LRU 置换算法

3. 其它置换算法

请求分页系统的性能分析

1. 缺页率对有效访问时间的影响

2. 工作集

3. 抖动产生的原因和预防方法

分段存储管理

分段机制的引入

解决部分存储空间动态增长、信息共享和信息保护的问题。

分段系统的基本原理

分段

段表的每一个表项记录的信息包括段号、段长和该段的基址，段表存放在内存中。

分段的逻辑地址结构

分段机制的逻辑地址是二维的，由段号和段内的地址组成。

段表

段表是由操作系统维护的用于支持分段存储管理地址映射的数据结构。通常情况下，每个进程有一个段表，段表由段表项构成。每个段表项包含段号、段基址（段的起始地址）和段长（段的大小）三个部分。

分段系统的地址变换

段表项长度是指一个段表项所占用的字节数。

分页和分段的主要区别

分页和分段都属于离散分配方式，都要通过数据结构和硬件的配合来实现逻辑地址到物理地址的映射。

主要区别：

• 页是按物理单位划分的，分页的引入是为了提高内存的利用率和支持虚拟存储。而段是按逻辑单位划分的，一个段含有一组意义相对完整的信息。引入分段的目的是为了方便程序员编程。
• 页的大小是固定的。而段的大小不固定，取决于用户编写的程序和编译器。
• 分页的地址空间是一维的，程序员给出的地址只是一个助记符，已知的逻辑地址是一个数。分段的地址空间是二维的，程序员在标识一个逻辑地址时需要给出两个数：一个是段号，一个是段内偏移。

信息共享

采用分段机制比分页机制更容易实现信息的共享。

段页式存储管理

段页式存储管理的基本原理

在段页式存储管理系统中，将用户进程的逻辑空间先划分成若干个段，每个段再划分成若干个页。进程以页为单位在物理内存中离散存放，每个段中被离散存放的页具有逻辑相关性。

地址变换过程

Linux 的伙伴系统

Linux 的伙伴系统算法把所有的空闲面框分组为 11 个块链表，每个块链表分别包含大小为 1、2、4、8、16、32、64、128、256、512、1024 个连续的页框。对 1024 个页框的最大请求对应着 4MB 大小的连续页框。每个块的第一个页框的物理地址是该块大小的整数倍。

大小为 16 个页框的块，其起始地址是 16*2¹²（2¹²=4096B，这是一个常规页的大小）的倍数。