存储管理是操作系统重要组成部分，管理重要资源——内存储器。

存储管理包含以下功能：

• 存储分配
• 地址映射
• 存储保护与共享
• 存储扩充

存储器工作原理

存储器层次

为了在容量大小、速度快慢、价格高低等因素之间取得平衡点，获得较好的性价比，计算机系统的存储器层次从上到下氛围：寄存器、缓存、内存、磁盘、磁带五层。

地址转换与存储保护

写好的源程序要经历编译、链接之后成为可执行程序，装载进内存才可被执行。

磁盘中的装载模块使用的是逻辑地址，逻辑地址的集合称为进程的逻辑地址空间。物理内存从统一的基地址开始顺序编址的存储单元成为物理地址或绝对地址。物理地址的总体构成了物理地址空间。

可执行程序逻辑地址转换为物理地址的过程称地址重定位、地址映射，或地址转换，有三种地址重定位方式：

1. 静态地址重定位：在进程执行前一次性把逻辑地址修改为内存物理地址。易于实现，不允许执行时移动，现在已经不用。

2. 动态地址重定位：装载程序把代码装载进内存指定区域，但不修改链接过的程序逻辑地址，程序内存起始地址被置入重定位寄存器。程序执行时，当CPU访问程序和数据时，硬件截取此逻辑地址，并在发送到内存前加上重定位寄存器的值，实现地址转换。优点是允许程序在内存中移动，便于程序共享和内存利用率高。

   

3. 运行时链接地址重定位：实际应用场合，每次要运行的装载模块可能不同，所以有了运行时链接地址重定位。相对地址到物理地址的转换推迟到程序执行指令时，运行时链接装载方式采用动态重定位的地址转换方法。

连续存储管理

固定分区存储管理

又称静态分区模式。早期操作系统采用了这种方式

基本思想

内存空间被划分成数目固定不变的分区，分区大小不等，每个分区只装入一个作业，若多个作业都装有作业，则可并发执行，是支持多道程序设计最简单的存储管理技术。

通过一张内存分配表，记录内存中分区使用情况，指出各分区其实地址和长度，占用标志用来指示此分区是否被使用，当值为0，表明尚未占用。内存分配时总是用哪些占用标志为0的分区。

作业进入分区有两种排队策略，一是每个分区有单独的作业等待队列，调度程序选中作业后，创建用户进程，进入能装入该作业的最小分区的等待队列中，好处是使装入分区浪费空间最小；二是所有等待处理的作业排一个队列，当分区空闲，就从队首搜索分区长度能容纳的作业执行，为省空间，可以让可容纳的最大作业装入（队列先排序后搜索）。

缺点：

1. 超过最大分区的作业无法装入，可用覆盖补救，但麻烦。
2. 内存利用率低，造成碎片、空间浪费。
3. 无法动态扩充内存空间
4. 分区数目无法改变。

可变分区存储管理

又称动态分区模式，按照作业大小划分分区，但划分时间、大小、位置都是动态的。系统把作业装入内存，根据所需内存容量查看空间是否足够，若够则分割一个分区给此作业，若没有则等待内存资源。由于分区大小按照作业需求分割的，而且分区数目可变，所以不会浪费，能提高内存利用率。

还没有装入作业时，用户区整体是一个大分区，随着作业装入和撤离，内存空间被划分成许多分区，当作业撤离时，回收空间。

常见的可变分区分配算法大致有如下几种：

1. 最先适应（first fit）分配算法：顺序查找未分配区表或链表，直至找到第一个满足长度要求的空闲区，然后分割空间。
2. 下次适应（next fit）分配算法：总是从未分配区的上次扫描结束处顺序查找未分配区表和链表，直至找到第一个满足长度的空闲区，分割空间。
3. 最优适应（best fit）分配算法：扫描整个未分配区表或链表，从空闲区中挑选一个能满足用户进程要求的最小分区进行分配。通常空闲区按长度递增排列，查找总从最小的开始。
4. 最坏适应（worst fit）分配算法：扫描整个未分配区表或链表，总挑选一个最大的空闲区分割给作业使用，优点是使剩下的空闲区不过小。
5. 快速适应（quick fit）分配算法：专为经常用到的长度的空闲区设立单独的空闲区链表。

内存不足的存储管理技术

移动技术

把在内存中的进程分区连接到一起，使分散的空闲区汇集成片，也称内存紧凑。

对换技术

如果当前一个或多个驻留进程都处于阻塞态，此时选择其中一个进程，将其暂时移出内存，腾出空间爱你给其他进程使用，同时把磁盘中的某个进程换入内存。

覆盖技术

程序执行过程中程序不同模块在内存中相互替代。

分页存储管理

分页存储基本原理

基本概念

1. 页面：进程逻辑地址空间分成大小相等的区，每个区称为页面或页，页号从0开始。
2. 页框：又称页帧，把内存物理地址空间分成大小相等的区，其大小与页面大小相等，每个区是一个页框（物理块），块号从0开始。
3. 逻辑地址：与此对应，分页存储器逻辑地址由页号和页內位移组成。计算机地址总线如果是32位，页面尺寸规定为12位，那么页号共20位，表示地址空间最多包含2^20个页面。
4. 内存页框表：该表长度取决于内存划分的物理块数，编号可与物理块号一致，页框表的表项给出物理块使用情况，0为空，1为满。
5. 页表：在进行内存分配时以页框为单位，进程信息有多少页则装入时分配多少页框。程序以页面为单位存储，所以每个页面设立一个重定位寄存器，这些重定位寄存器的集合称为页表。
6. 物理地址=页框号×块长+页内位移

进程运行前系统吧页表基地址送入页表基址寄存器，运行时按页面动态地址重定位，当CPU获得逻辑地址后，按设定页面尺寸分成页号和页面位移，先从页表基址寄存器找到页表基地址，再用页号作为索引查页表，得到对应页框号，计算出物理地址，过程如图：

快表

Translation Look_aside Buffer，TLB，为提高运算速度，在硬件中设置相联存储器，用来存放最近访问的部分页表项。速度快成本高容量小。

假设访问内存时间为100ns，访问快表20ns，当快表有32个但愿，查找命中率90%，内存地址先存入快表，再由处理器存取，所以按照逻辑地址进行存取平均时间为(100+20)×90%+(100+100+20)×(1-90%)=130ns

分段存储管理

基本原理

进程的逻辑地址空间分成多段，分为段号和段内位移。基于可变分区存储管理原理，以段位单位来划分和连续存放，为作业的各段分配一个连续内存空间，各段之间不一定连续。分配空间时先建立段表，各段在内存中的情况可由段表来记录。

分段和分页的比较

分段是信息的逻辑单位，由源程序的逻辑结构和含义所决定，用户可见，段长根据用户需要确定，段起始地址可从任何内存地址开始。源程序经过连接装入后仍然保持二维地址结构，目的是满足用户模块化程序设计的需要。

分页是信息的物理单位，与源程序的逻辑结构无关，用户不可见，页长由系统确定，页面只能从页大小的整数倍地址开始。源程序经连接装入变成一维地址结构，目的是实现离散分配并提高内存利用率。

虚拟存储管理

概念

在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比屋里没从容量大得多的、可寻址的内存。

Intel x86地址线32位，寻址地址是4GB。

部分装入

当程序即将执行的指令和访问的数据在磁盘上，为继续执行要从磁盘装入，这叫做部分装入。

部分替换

如果内存空间不够，就把内存中暂时不用的信息移至磁盘，这叫做部分替换。

请求分页虚拟存储管理

通过一个Memory Management Unit存储管理部件管理地址转换、虚存管理等。主要功能有：

1. 管理硬件页表基址寄存器
2. 分解逻辑地址
3. 管理快表
4. 访问页表
5. 发出异常：当产生页面越界产生越界中断，当页表中有页失效位发出缺页异常。
6. 管理特征位

缺页异常

发现当前页面不在内存时，由MMU发出的特殊中断信号。一条指令可能会涉及到多个页面，所以一条指令可能会发出多次缺页异常。

MMU工作过程

简单的总结起来就是三步：

1. 快表命中？否↓
2. 页表命中？否↓
3. 缺页中断

细致地说：

1. MMU根据页面大小切割逻辑地址，得到页号和页内位移。
2. 以页号为索引搜索快表。命中→送出页框号，与页内位移拼接成物理地址，访问权限检查，通过进行访存，结束。未命中↓
3. 以页号为索引搜索页表。命中→送出页框号，与页内位移品家诚物理地址，访问权限检查，通过进行访存，结束，并把该页面和页框信息装入快表。未命中↓
4. MMU发出缺页异常，缺页异常处理
   1. 挂起请求调页进程
   2. 根据页号搜索外页表，找到此页物理地址
   3. 内存有空闲页框？有→调页，把页面装入页框，修改页框表进程表项。无↓
   4. 按照替换算法淘汰页面，淘汰的页面修改过则写回磁盘，未修改过直接替换，调页，把页面装入页框，修改页框表进程表项。
   5. 返回进程断点，重启被中断指令。

缺页中断率

如果选用不适合的替换算法，会导致刚刚被替换的页面又需要调用，调入不久又被淘汰，如此反复会导致大部分时间用在调度页面上，这个现象叫做抖动或颠簸。

缺页中断率计算方法为：缺页次数/总访问次数。

防止页面抖动，三个方法：增加配给进程的页框数、挑选页面替换算法、改进程序结构。

全局页面替换算法

最佳页面替换算法

OPT，OPTimal replacement，当需要调入新页必须替换旧页时，淘汰以后再不访问的或距现在最长时间才访问的页。然而这是个嘴炮算法，因为页面引用串无法预知。

先进先出页面替换算法

FIFO，First In First Out replacement，物理页框会存储页面，排成队列，随着不断有页面进队，也有最先使用的页面出队。据估计，FIFO是嘴炮算法中断率的2-3倍。

页面缓冲算法是对FIFO的改进，建立一个修改页面队列和一个非修改页面队列，当缺页中断，按照FIFO找到淘汰页面，根据修改与否进入队列，需要装入的页面进非修改队列的队首页框。当淘汰页被写回磁盘只需要把该页框连接到非修改队列末尾，当修改页面队列大道一定数量，成批写回，并把空闲页框放入非修改页面队列队尾。

最近最少页面使用算法

LRU，Least Recently Used replacement，淘汰最长时间没访问的页面，这个算法基于程序时间局部性。

第二次机会页面替换算法

Second Chance Replacement，最先进入内存的页面如果最近还在使用，仍然有机会像新调入内存的页面一样留在内存，检查FIFO的队首，检查他的引用位，如果是0直接淘汰，如果是1则清0再进队列，再给一次机会。

时钟页面替换算法

Clock policy replacement，本质上和SCR没区别，采用了循环队列构造页面队列。

局部页面替换算法

当某个进程引起缺页，不能通过缩小其他进程驻留页面集来解决问题。所以有了局部页面替换算法。

请求段页式虚拟存储管理

把段式存储和页式存储的优点结合起来，在分段存储管理的基础上实现存储管理就是段页式虚存管理。

原理：

1. 虚地址以程序的逻辑结构划分成段。
2. 实地址划分成位置固定、大小相等的页框（块）
3. 每一段线性地址空间划分成于页框大小相同的页面。
4. 逻辑地址分为三个部分，段号s，段内页号p，页内位移d。段内位移d’=p×块长+d。
5. 请求段页式虚存管理数据结构分为作业表、段表、页表三级结构。

存储管理方案小结

分类	管理方案	维数	多道支持	共享内存	重定位	内存扩充	保护机制	硬件支持
实存管理	单连续分区	一维	单道	不能	静态	覆盖、对换	无	无
实存管理	固定分区	一维	多道	多界地址	静态	覆盖、对换	界地址或键保护	单/多重定位寄存器
实存管理	可变分区	一维	多道	多界地址	动态	覆盖、对换	界地址或键保护	单/多重定位寄存器
实存管理	分页	一维	多道	可以	动态	覆盖、对换	页表、越界保护存取控制保护	地址转换/保护机制、快表
实存管理	分段	二维	多道	可以	动态	覆盖、对换	段表、越界保护存取控制保护	地址转换/保护机制、快表
实存管理	段页式	二维	多道	可以	动态	覆盖、对换	段页表、越界保护存取控制保护	地址转换/保护机制、快表
虚存管理	请求分页	一维	多道	可以	动态	虚存	页表、越界保护存取控制保护	同上+动态链接+中断
虚存管理	请求段页	二维	多道	可以	动态	虚存	段页表、越界保护存取控制保护	同上+动态链接+中断