内存概述

基础概念

内存是用于存放数据的硬件，程序执行前需要先放到内存中才能被CPU处理

• 存储单元：按字节编址（一个存储单元1个字节，8个二进制位）；按字长编址（一个存储单元1个字长，按计算机的字长决定存储单元大小）

• 内存地址：从0开始，每一个地址对应一个存储单元

逻辑地址与物理地址

代码翻译成CPU可识别的指令，这些指令会告诉CPU该去内存中的哪个地址存/取数据，这时表示的是实际存放的地址，即物理地址

生成机器指令的时候并不知道该进程的数据会放到什么位置，编译生成的指令中使用的是相对地址，即逻辑地址

程序运行基本原理

编译

源代码文件(.c)生成目标模块(.o)，将高级语言翻译为机器语言。每一个目标模块都具有独立的逻辑地址

链接

目标模块生成装入模块(可执行文件，如.exe)，链接完成使得各模块形成整体的链接地址

• 静态链接：装入前链接成一个完整模块

• 装入时动态链接：运行前边装入边链接

• 运行时动态链接：运行时需要什么模块才装入并链接

装载

将装入模块装入内存运行，装入后形成物理地址

• 绝对装入：编译时产生绝对地址，只适用于单道程序环境(那时候还没有操作系统，编译器负责实现)

• 静态重定位：编译链接后的装入模块地址是逻辑地址，装入时进行重定位，将指令中逻辑地址+装入的起始物理地址得到真实的物理地址（地址写死，早期系统使用）

• 动态重定位：运行时才将逻辑地址转换为物理地址。

内存空间的分配与回收

连续分配管理方式

单一连续分配

内存被分为系统区和用户区，系统区通常位于内存的低地址部分，用于存放操作系统相关数据；而用户区用于存放用户进程相关数据

内存中只能有一道用户程序，用户程序独占用户区

固定分区分配

将用户空间划分为若干个固定大小（可以一样大也可以不一样大）的分区，在每个分区中只装入一个作业。操作系统需要建立并管理一个“分区说明表“，用来实现每个分区的分配与回收

• 优点：实现简单，无外部碎片
• 缺点：进程太多必须使用覆盖技术，使得性能降低；同时会采用内部碎片，导致内存利用率低

动态分区分配

不事先划定分区，而是在进程装入内存时，根据进程的大小动态的建立分区（系统分区的大小和数目是可变的）

要实现动态分区分配，操作系统需要维护并管理存储空闲分区信息的数据结构，常用的有空闲分区表和空闲分区链

可以使用”紧凑“方法来解决外部随便，所谓紧凑就是移动进程所分配的内存块从而将空闲内存连续起来

实现动态分区分配的主要方法：

！非连续分配管理方式

为用户进程分配的内存可以是一个离散的内存空间

主要包括：分页管理、分段管理、段页式存储管理

分页管理

基本思想

• 内存空间：分成一个个相等的小分区，每个分区就是一个页框，并从0开始依次分配页框号

• 用户进程地址空间：拆分成一个个与页框大小相等的小部分，称为页，每个页也有一个从0开始分配的页号

之后操作系统以页框为单位为各个进程分配内存空间，进程的页与内存的页框一一对应，各个页不必连续存放，也不必按照一定顺序，实现了离散的存储

页表

为了能知道进程的每个页面在内存中存放的位置，操作系统要为每一个进程建立一张页表，页表具有如下特点：

1、一个进程对应一张页表

2、进程的每一页对应一块页表项

3、每个页表项由”页号“和”块号“组成

4、页表记录进程页面和实际存放的内存块之间的对应关系

5、每个页表项长度是相同的，所以页号是”隐含“的

基本地址转换

页表寄存器：保存页表在内存中的起始地址F和页表长度M。进程未执行的时候，F和M放在PCB中，进程被调度时，操作系统内核将其放到页表寄存器中

利用快表的地址转换

根据局部性原理（见下文），可以使用快表（TLB，是一种告诉存储单元）来存放当前访问的若干页表项，以加速地址转化的过程

多级页表

单级页表存在几个问题：

• 所有页表项都要连续存放，页表很大时占用页框很多
• 进程一段时间可能只访问某几个特定的页面，因此没有必要让页表常驻

为解决这些问题可以采用多级页表

分段管理

基本思想

• 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段有一个段名，每个段从0开始编址

• 内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻

地址转换

程序分为多个段，离散的放入内存，必须能够从物理内存中找到各个逻辑段的存放位置（段表）

记录该段在内存中的起始位置（基址）、段的长度。各个段表项的长度一致，因此段号是隐含的可以不进行记录

段页式管理

分段与分页的优缺点

基本思想

将进程按逻辑模块分段，再进行分页

地址转换

逻辑：段号、页号、页内地址（业内偏移量）

段号决定了每个进程最多可以分几个段

页号决定了每个段最大有多少页

内存空间的扩充

覆盖技术

按自身逻辑结构，让一些不可能被同时访问的程序段共享同一覆盖区（只存在于早期操作系统）

交换技术

将磁盘分为对换区（swap）和文件区，前者连续分配追求I/O速度，后者离散分配追求存储空间利用率

内存紧张时，把进程暂时换出到外存相应区域。优先换出阻塞进程、低优先级进程（可能导致饥饿）、还要考虑进程在内存的驻留时间，PCB不会换出

！虚拟存储技术

传统内存分配方法缺陷

• 一次性：作业必须一次性全部装入内存后才能开始运行。大作业无法运行，多道程序并发度下降（比如一些几十个G的游戏显然无法在有限的内存中运行）。
• 驻留性：作业在运行期间一直驻留在内存，内存中驻留大量的暂时用不到的数据，浪费了宝贵的内存资源。

局部性原理

• 时间局部性：现在访问的指令、数据在不久后很可能再次访问
• 空间局部性：现在访问的内存单元周围的内存空间很可能在不久之后访问
• 高速缓存：频繁访问的数据放到更高速的储存器中

虚拟内存概述

根据传统内存分配方法的缺陷以及局部性原理的特点，使用虚拟内存方法进行改进：

程序不需要全部装入内存即可运行，运行时根据需要动态调入数据，内存不够时，换出一些数据到外存

• 多次性：作业无需在运行时一次装入内存，而是允许分多次调用
• 对换性：作业无需在运行时常驻内存，允许作业换入、换出
• 虚拟性：从逻辑上扩充了内存容量，用户看到的容量，远大于实际容量

虚拟内存的实现

请求换页

访问的信息不存在时，操作系统负责将需要的信息从外存调入内存

新增页表项

• 状态位：表示页面是否已在内存中
• 访问字段：记录最近的被访问情况，供页面置换算法参考
• 修改位：表示页面调入内存中是否修改过，只有修改过的页面才需要在置换时写回外存
• 外存地址：页面在外存中存放的位置

缺页中断机制

每当访问的页面不存在时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，掉页完成后再将其放入就绪队列

页面置换

内存空间不足时，将内存中暂时不用的信息换到外存

页面的换入换出需要磁盘I/O，时间开销是很大的，缺页率越小越好

最佳置换算法(OPT)

每次选择淘汰的页面将是以后再不使用的，或是在最长时间内不再被访问的页面，以保证最低的缺页率

该算法实现的前提是知道页面的访问序列，这是无法预知的，因此该方法无法实现

先进先出置换算法(FIFO)

每次选择淘汰的页面是最早进入内存的页面，可以使用队列进行实现

Belady异常：当为进程分配的物理块增大时，缺页次数不增反降

FIFO算法会产生Belady异常，其实现简单，但性能差（最早进入与最近是否访问没有明显关联）

最近最久未使用算法(LRU)

LRU（least recently used）：每次选择淘汰的页面是最近最久未使用的页面

实现方式：给每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t，当需要淘汰一个页面时，选择所有页面中t最大的，即最近最久未使用的页面

时钟置换算法(CLOCK)

实现方法：

为每个页面设置一个访问位（如1表示最近访问过，0表示最近没访问过），再将内存中的页面链接为一个循环队列

若某页被访问，则将访问位置为1。当需要淘汰一个页面时，则淘汰第一个访问位为0的页面，若遇到访问位为1的页面，则将其访问位置为0

因此，使用该方法选择一个淘汰页面最多会进行两轮扫描

改进型时钟置换算法

相对于普通时钟置换算法，最大的改变就是使用（访问位，修改位）的形式表示各页面的状态

以优先找到最近既没被访问过，又没被修改过的页面

页面置换算法总结与比较

页面分配策略

相关概念

驻留集：请求分页存储管理中给进程分配的物理块的集合。在采用了虚拟存储技术的系统中，驻留集大小一般小于进程大小

• 固定分配：操作系统为进程分配一组固定数目的物理块，在运行期间不变（驻留集不变）

• 可变分配：在运行期间驻留集大小可变

• 局部置换：发生缺页时只能进程自己的物理块进行置换

• 全局置换：可以使用其他空间进行置换

• 抖动现象：给进程分配的物理块太少，刚刚换出的页面马上又要换入内存,刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动或颠簸。

从何处调页

对换区空间足够

对换区空间不够

Unix 方式