# 内存基础知识

# 内存概述

内存可存放数据。程序执行前需要先放到内存中才能被 CPU 处理 —— 缓和 CPU 与硬盘之间的速度矛盾

# 装入的三种方式

# 绝对装入

绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存

# 可重定位装入

静态重定位：又称可重定位装入。编译、链接后的装入模块的地址都是从 0 开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行 “重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的）

# 动态运行时装入

动态重定位：又称动态运行时装入。编译、链接后的装入模块的地址都是从 0 开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持

# 内存管理的概念

# 操作系统对内存管理的管理

1. 操作系统负责内存空间的分配与回收
2. 操作系统需要提供某种技术从逻辑上对内存空间进行扩充
3. 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换
4. 操作系统需要提供内存保护功护功能。保证各进程在各自存储空间内运行，互不干扰

# 覆盖与交换

# 覆盖技术

1. 覆盖技术思想：将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存
2. 内存中分为一个 “固定区” 和若干个 “覆盖区”
3. 需要常驻内存的段放在 “固定区” 中，调入后就不再调出（除非运行结束）
4. 不常用的段放在 “覆盖区”，需要用到时调入内存，用不到时调出内存
5. 缺点：对用户不透明，增加了用户编程负担

# 交换技术

1. 交换技术设计思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）
2. 中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存
   1. 暂时换出外存等待的进程状态为挂起状态（挂起态，suspend）
   2. 挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态

# 连续分配管理方式

# 单一连续分配

1. 在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间
2. 优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护
3. 缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低

# 固定分区分配

# 动态分区分配

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的

# 动态分区分配算法

# 首次适应算法（First Fit）

1. 算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区
2. 实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区

# 最佳适应算法（Best Fit）

1. 算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当 “大进程” 到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区
2. 如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区

# 最坏适应算法（Worst Fit）

1. 算法思想：为了解决最佳适应算法的问题 —— 即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用
2. 如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区

# 邻近适应算法（Next Fit）

1. 算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题
2. 实现：空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区

# 基本分页存储管理的基本概念

# 分页存储概念

# 页表

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

# 每个页表项占用多少字节

# 如何实现地址转换

# 如何确定逻辑地址对应的页号，页内偏移量

# 逻辑地址结构

# 基本地址变换机构

# 基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址 F 和页表长度 M。进程未执行时，页表的始址 和 页表长度 放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中

# 图解

# 例题

# 具有块表的地址变换机构

# 块表（TLB）

快表，又称联想寄存器（TLB， translation lookaside buffer ），是一种访问速度比内存快很多的高速缓存（TLB 不是内存！），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表

# 快表图解

# 引入块表，地址的交换过程

# 局部性原理

# 基本地址变换结构与具有快表的地址交换机构

	地址变换过程	访问一个逻辑地址的访问次数
基本地址交换机构	1. 算页面，页内偏移量 2. 检查页号合法性 3. 查页表，找到页面存放的内存块号 4. 根据内存块号与页内偏移量得到物理地址 5. 访问目标内存单元	两次访存
具有快表的地址交换机构	1. 算页号，页内偏移量 2. 检查页号合法性 3. 查快表，若命中，即可直到存放内存块号，可直接进行 5，若未命中则进行 4 4. 查页表，找到页面存放的内存块号，并且将页表项复制到快表中 5. 根据内存块号偏移量得到物理地址 6. 访问目标内存单元	快表命中，只需要一次访存，快表未命中，需要两次访存

# 两级页表

# 单极页表的问题

1. 页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框
2. 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面

# 两级页表的原理、地址结构

# 实现地址变换

# 注意

# 基本分段存储管理方式

# 分段

1. 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从 0 开始编址
2. 内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻

# 段表

# 地址变换

# 分页管理与分段管理

1. 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的
2. 段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名
3. 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址
4. 分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址
5. 分段比分页更容易实现信息的共享和保护
6. 不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的（比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致）

# 段页式管理方式

# 分页分段对比

	优点	缺点
分页管理	内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片	不方便按照逻辑模块实现信息的共享和保护
分段管理	很方便按照逻辑模块实现信息的共享与保护	如果段过长，为其分配很大的连续空间会很不方便，段式管理会产生外部碎片

# 段页式管理

# 虚拟内存的基本概念

# 传统存储管理方式的特征、缺点

1. 一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：①作业很大时，不能全部装入内存，导致大作业无法运行；②当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降
2. 驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源

# 虚拟内存的特征

1. 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
2. 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出
3. 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量

# 虚拟内存实现方式

1. 请求分页存储管理
2. 请求分段存储管理
3. 请求段页式存储管理

# 请求分页管理方式

# 页表机制

# 缺页中断机构

# 地址变换机构

# 页面置换算法

	算法规则	优缺点
OPT	优先淘汰最长时间不被访问的页面	缺页率最小，性能最好，无法实现
FIFO	优先淘汰最先进入内存的页面	实现简单，但性能很差，可能出现 Belady 异常
LRU	优先淘汰最近最久没访问的页面	性能很好，但是需要硬件支持，算法开销大
CLOCK（NRU）	循环扫描各页面，第一轮淘汰访问位 0，并将扫描过的访问位改为 1，若第一轮没选中，则进行第二轮扫描	实现简单，算法开销小，但未考虑页面是否被修改过
改进 CLOCK	若用（访问为，修改位）的形式表述：则第一轮：淘汰（0，0），第二轮：淘汰（0，1），第三轮：淘汰（0，0），第四轮：淘汰（0，1）	算法开销小，性能也不错

# 页面分配策略

# 页面分配、置换策略

# 调入页面

# 抖动现象

# 工作集