内存管理

3.1_1 内存的基础知识

何为内存？有何作用？

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

内存中有很多存储单元，内存地址从0开始，每个地址对应一个存储单元，一个存储单元能存储多少比特位取决于计算机

几个常用的数量单位

$1K = 2^{10} = 1024$

$1M = 2^{20}$

$1G = 2^{30}$

程序的链接与装入

1. 编译：由编译程序将用户源代码编译成若干目标模块
2. 链接：由链接程序将编译形成的一组目标模块以及他们所需的库函数链接在一起，形成一个完整的装入模块
3. 装入：由装入程序将装入模块装入内存运行

绝对装入

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

绝对装入只适用于单道程序环境

可重定位装入

又称静态重定位。编译连接后装入模块的地址都从0开始，指令中使用的地址都是相对于起始地址而言的逻辑地址。装入模块装入到内存的时候进行重定位
重定位：装入时对目标程序中指令和数据地址进行修改的过程

静态重定位的特点是：

1. 在一个作业装入内存时，必须分配其要求的全部内存空间，否则就不能装入该作业
2. 作业一旦进入内存，在运行期间就不能再移动，也不能再申请内存空间

动态重定位

编译链接后的装入模块的地址都从0开始。装入程序将模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是在真正执行时才进行。这种方法需要一个重定位寄存器支持

特点：

1. 可以将程序分配到不连续的存储区中
2. 程序运行前只需要装入部分代码即可投入运行
3. 在程序运行期间可以根据需要，动态申请分配内存
4. 便于程序段的共享
5. 可以向用户提供一个比存储空间大得多的地址空间
6. 允许程序在内存中移动

链接的三种方式

1. 静态链接
   1. 在程序运行前，现将各自目标模块以及库函数链接形成一个完整的装配模块，以后不再拆开。
   2. 需要解决地址变换问题
2. 装入时动态链接
   1. 在装入内存时，一边装入一边链接
   2. 优点在于便于修改和更新，实现对目标模块的共享
3. 运行时动态链接
   1. 在程序执行中需要该目标模块时才进行链接
   2. 加快程序的装入，节省大量内存空间

逻辑地址和物理地址

1. 逻辑地址
   1. 编译后，每个目标模块都从0号单元开始编址，称为该目标模块的相对地址（逻辑地址
   2. 程序在运行时使用的是逻辑地址，内存管理的具体机制对程序员和用户程序是透明的
   3. 不同进程可以有相同的逻辑地址，可以映射到主存的不同位置
2. 物理地址
   1. 是地址转换的最终地址。指令和数据都需要通过物理地址从主存中存取
   2. 装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换为物理地址（重定位

进程的内存映像

1. 代码段：程序的二进制代码，只读，可被多个进程共享
2. 数据段：程序运行时加工处理的对象，包括全局和静态变量
3. 进程控制快PCB：存放在系统区，os通过PCB控制、管理进程
4. 堆：存放动态分配变量。malloc函数动态地向高地址分配空间
5. 栈：用来实现函数调用。从用户空间最大地址往低地址增长

3.1_2 内存管理的概念

1. 内存空间的分配与回收
2. 内存空间的扩展
   1. 覆盖技术
   2. 交换技术
   3. 虚拟存储技术
3. 负责地址转换功能（将逻辑地址转换为物理地址），这个过程称为重定位
4. 内存保护：各个进程在各自的内存空间内进行，互不干扰
   1. CPU中设置一对上下限寄存器，进程访问时检查是否越界
   2. 采用重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）进行越界检查（限长寄存器存储进程的最大逻辑地址
5. 内存共享
   1. 只读的区域才可以被共享
   2. 可重入代码：又称纯代码，是允许多个进程同时访问但不允许被任何进程修改的代码

3.1_3 覆盖与交换*

覆盖技术

目的：解决程序大小超过物理内存总和的问题

思想：将程序分为多段（模块），常用的段常驻内存，不常用的段在需要时调入内存

1. 内存中分为一个“固定区”和若干个“覆盖区”
2. 需要常驻内存的段放在固定区中，调入后就不再调出，除非运行结束
3. 不常用的段放在覆盖区，需要时调入内存，不需要时调出内存

1. 必须由程序员声明覆盖结构，操作系统完成自动覆盖。
2. 缺点：对用户不透明，增加了用户编程负担

交换技术（对换

思想：内存空间紧张时，系统将内存中某些进程暂时换出外村，外存中某些已具备运行条件的进程换入内存

1. 暂时换出外存等待的进程状态为挂起状态，又可以分为就绪挂起、阻塞挂起
2. 在具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区
   1. 文件区用于存储文件，追求空间利用率，因此采用离散分配方式
   2. 对换区用于存储被换出的进程，追求换入换出效率，因此采用连续分配方式
   3. 对换区只占磁盘空间一小部分，IO速度比文件区的快
3. 可以优先换出阻塞进程、优先级低的进程
4. PCB会常驻内存，不会被换出

3.1_4 连续分配管理方式

连续分配：为用户进程分配一个连续的内存空间
内部碎片：分配给某个进程的内存区域中，有些部分没有用上
外部碎片：内存中的某些空闲分区因为太小，难以利用

单一连续分配

1. 内存被分为系统区和用户区
2. 系统区用于存放操作系统相关数据，仅供操作系统使用，通常在低地址部分；用户区用于存放用户进程相关数据
3. 用户区中只能有一道用户程序，用户程序独占整个用户区空间

优点：实现简单；无外部碎片

缺点：只能单用户、单任务；有内部碎片，存储器利用率极低

固定分区分配

将用户空间划分为若干个固定大小的分区，每个分区中只装入一道作业

1. 分区大小相等：缺乏灵活性，适用于一台计算机控制多个相同对象的场合
2. 分区大小不等：增加了灵活性，可以满足不同大小的进程需求

操作系统需要建立一个数据结构，实现各个分区的分配和回收。每个表项需要包括分区的大小、起始地址、状态

优点：实现简单，无外部碎片

缺点：用户程序过大时可能分区不能满足需求，需要覆盖技术，这会降低性能；会产生内部碎片

动态分区分配

又称可变分区分配。不会预先划分内存区，而是进程装入内存时，根据进程大小动态建立分区，使得分区的大小正好适合进程的需要

1. 使用空闲分区表或者空闲分区链记录内存的使用情况
2. 作业装入内存时，必须按照一定的动态分区分配算法
3. 动态分区分配没有内部碎片，但是有外部碎片
4. 可以使用紧凑技术来解决外部碎片

3.1_5 动态分区分配算法

首次适应算法

思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区

实现：空闲分区按地址递增次序排列，每次分配内存时顺序查找空闲分区链/表，找到第一个满足要求的空闲分区

邻近适应算法（循环首次适应算法

思想：在首次适应算法基础上，查找时不从头查找，而是从上次查找结束的位置开始

最佳适应算法

思想：优先使用小的空闲区，留下大片连续空间

实现：空闲分区按照容量递增次序链接

缺点：会产生很多的外部碎片

最坏适应算法（最大适应算法

思想：为了解决最佳适应算法的问题，优先使用最大的空闲分区

实现：空闲分区按照容量递减次序链接

缺点：导致容量较大的空闲内存被迅速用完，之后如果有大进程到达，就没有空闲分区可用了

3.1_6 基本分页存储管理的概念

页框（页帧）：将内存空间划分为一个个大小相等的分区，每个分区就是一个页框，每个页框有一个页框号（从0开始

页（页面）：将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分成为一个页，每个页有一个页号（从0开始

为了方便地址转换，页面的大小通常为2的整数幂

操作系统以页框为单位为各个进程分配内存空间，进程的每一个页面放入一个页框中，一一对应。页面不必连续存放，可以放在不相邻的各个页框中

地址结构：页号P+页内偏移量W
例如32位地址，低0～11位为W，12～32位为页号
那么每一页大小为：$2^{12}=4KB$，最多有$2^{20}$页

页表

为了得知进程的每个页面在内存块中存放的位置，操作系统需要为每个进程建立一张页表，通常存放在PCB中

页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组

页表记录的是内存块号而不是内存块起始地址，J号内存块起始地址=J*内存块大小（从0开始

3.1_7 基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址

1. 设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M
2. 进程未执行时，页表的起始地址和页表长度放在PCB中，进程被调度时，操作系统内核会将其放到页表寄存器中

例题

页面大小 L=1KB，页号2对应物理块号b=8，计算逻辑地址2500的物理地址

2500对应的页号：2500/1024 = 2，对应的页内偏移量：2500%1024 = 452
b=8，所以 物理地址=1024*8+452

3.1_8 具有快表的地址变换机构

什么是快表（TLB

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

3.1_9 两级页表

单级页表存在的问题

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

如何解决

• 为页表再建立一张页表，称为页目录表(顶级页表、外层页表)

• 使用虚拟内存技术，在需要访问页面时，才把页面调入内存

3.1_10 基本分段存储管理方式

分页管理方式从计算机角度考虑设计；分段管理考虑了用户和程序员，满足方便用户编程、信息共享和保护、动态增长以及动态链接

与分页最大的区别就是：离散分配时所分配的地址空间的基本单位不同

分段

进程按照自身逻辑关系划分为若干个段，每个段都有一个段名，从0开始编址

地址结构：段号S+段内偏移量

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

优点：用户编程方便，可读性强

1. 分段系统的逻辑地址由段号（段名）和段内地址（段内偏移量）组成
2. 段号的位数决定了每个进程最多可以分多少段
3. 段内地址的位数决定了每个段的最大长度是多少

段表

目的：从物理内存中找到各个逻辑段的存放位置，所以为每个进程建立一张段映射表

地址变换

同样可以引入快表，加快访问

可重入代码 / 纯代码：不能被修改的代码，不属于临界资源，可以进行共享

3.1_11 段页式管理方式

分页、分段管理的优缺点分析

1. 分页管理
   1. 内存空间利用率高，不会产生外部碎片，只有少量内部碎片
   2. 不方便按照逻辑模块实现信息的共享和保护
2. 分段管理
   1. 可以方便地进行实现信息共享和保护
   2. 如果段长过大，为其分配很大的连续空间会很不方便
   3. 会产生外部碎片

段页式管理

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

在一个进程中，段表只有一个，页表可能有多个

错题区
1. 动态重定位在作业的执行过程中进行
2. 分页和分段管理提供给用户的物理地址空间谁大谁小无法确定，和划分标准有关
3. 分页管理中的页面为操作系统感知
4. 页表的起始地址放在寄存器中
5. 操作系统实现分区存储管理的代价最小
6. 外存对换区的管理应该以提高换入换出速度为主
7. os对内存的管理采用分页管理，所划分的页面大小必须相同
8. 对主存储器的访问以字节或字为单位
9. 操作系统采用分页存储管理，要求每个进程拥有一张页表，进程的页表驻留在内存中（页号在PCB中，PCB也在内存中，需要时调入寄存器

3.2_1 虚拟内存的基本概念

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

指的是上面一系列存储管理方式

1. 许多暂时用不上的数据也会长期占用内存，导致内存利用率不高
2. 一次性：作业必须一次性全部装入内存才能开始运行
   1. 作业很大时不能全部装入内存，导致大作业无法运行
   2. 大量作业需要运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致并发度下降
3. 驻留性：作业一但装入内存，就一直驻留在内存中直到运行结束。事实上一个时间段内只需要访问作业的一小部分数据即可正常运行，这就导致了内存中驻留大量的暂时用不到的数据

局部性原理

• 时间局部性：执行了程序中某条指令后，不久这条指令很可能再次执行；数据也是（原因是程序中存在大量循环
• 空间局部性：访问了某个存储单元后，不久其相邻的存储单元也很可能被访问（原因是很多数据在内存中连续存放，指令也是顺序存放

广义上讲，快表、页高速缓存、虚拟内存技术都属于高速缓存技术，依赖的原理就是局部性原理

虚拟内存技术实际上建立了“内存-外存”的两级存储器结构，利用局部性原理实现高速缓存

虚拟内存的定义和特征

1. 基于局部性原理，在程序装入时，将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行
2. 当访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序
3. 此时用户看来似乎有一个比实际内存大得多的内存

虚拟内存三个主要特征

1. 多次性：无需在作业运行时一次装入所有内存，而是分为多次调入内存。只需要将当前运行的那部分程序和数据装入内存即可开始运行，需要运行尚未调入的部分时再调入那部分
2. 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中将作业换入换出
3. 虚拟性：从逻辑上扩充了内存容量，使用户看到的内存容量远大于实际的容量

如何实现虚拟内存技术

需要建立在离散分配的内存管理方式基础上，分为以下三种方式

• 请求分页存储管理
• 请求分段存储管理
• 请求段页式存储管理

均需要一定的硬件支持，一般包括

• 一定容量的内存和外存
• 页表/段表机制，作为主要的数据结构
• 中断机构。用户程序需要访问的部分未调入内存时，产生中断
• 地址变换机构。实现逻辑地址到物理地址的变换

3.2_2 请求分页存储管理方式

和基本分页存储管理主要区别

1. 访问信息不在内存时，操作系统负责将所需信息从外存调入内存（将缺失页面从外存调入内存
2. 内存空间不够时，操作系统负责将内存中暂时不用的信息换出到外存（页面置换

页表机制

1. 系统需要知道页面是否已经调入；若没有调入，需要知道该页面在外存的位置
2. 没有修改过的页面不用浪费时间写回外存；操作系统需要记录各个页面是否被修改过的信息

缺页中断机构

请求分页系统中，要访问的页面不在内存时，产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断

此时缺页的进程阻塞，放入阻塞队列；调页完成后唤醒，放回就绪队列

如果内存中有空闲块，则为进程分配一个空闲块，所缺页面装入，并修改页表中相应的页表项

如果没有空闲块，则由页面置换算法选择一个页面淘汰；若页面在内存期间被修改过，则写回外存

1. 缺页中断属于内中断，故障类型（可能被故障处理程序修复
2. 一条指令在执行期间可能产生多次中断

地址变化机构

1. 先检索快表
   1. 若找到需要访问的页，则修改页表项中的“访问位”，写指令需要修改“修改位”，然后通过快表给出的物理块号和业页内地址形成物理地址
   2. 若未在快表中找到，则去内存中查找页表。对比页表项中“状态位”，看是否调入内存。
      1. 如果已调入内存，则写入快表，快表满则通过页面置换算法替换一张
      2. 如果未调入内存，则产生缺页中断，请求从外存中调入

3.2_3 页面置换算法

页面的换入换出需要磁盘IO，开销较大，因此好的页面置换算法需要追求更少的缺页率

1. 最佳置换算法（OPT
   1. 淘汰以后永不使用，或者最长时间内不再被访问的页面，保证最低缺页率
   2. 需要知道进程接下来访问哪些页面，然而这是无法预知的，因此最佳置换算法是无法实现的，但可以利用该算法评价其他算法
   3. 题目做法：内存满需要换页时，往后查找当前内存中的页面首次出现需要访问的位置，淘汰最后出现的页面
2. 先进先出置换算法（FIFO
   1. 每次淘汰的页面是最早进入内存的页面
   2. 实现：用一个队列，根据页面调入内存的时间根据先后次序链接
   3. Belady异常：为进程分配的物理块数增大时，缺页次数不减反增的异常现象；只有FIFO算法会产生Belady异常
   4. 该算法与进程实际运行时的规律不相适，先进入的页面也有可能最常被访问，算法性能差
   5. 做题：模拟一个队列即可
3. 最近最久未使用置换算法（LRU
   1. 过去一段时间内未访问的页面，在最近的将来也不会被访问。每次淘汰最近最久未使用的页面
   2. 
   3. 需要寄存器和栈的硬件支持，实现难，虽然性能好
   4. 做题：内存满需要换页时，向前查找当前内存中的页面最近一次被访问的时间，淘汰最早出现的页面
4. 时钟置换算法（CLOCK
   1. 为每一帧设置一个“访问位”
   2. 页面首次被装入或被访问时，访问位置1
   3. 页面被链接为一个循环队列，设置一个指针检查各个页面访问位
   4. 如果页面访问位为0，则换出该页面
   5. 如果访问位为1，则暂不换出，访问位置0，指针移到下一个页面检查
   6. 
5. 改进型时钟置换算法
   1. 由于被修改过的页面需要写回外存，有开销，因此增加了“修改位”-M（记“访问位”为A
      1. A=0，M=0，最近没访问，也没被修改，是最佳淘汰页
      2. A=0，M=1，最近没被访问，被修改过，次好
      3. A=1，M=0，最近被访问，没被修改，可能近期会再被访问
      4. A=1，M=1，最近被修改被访问
   2. 算法步骤
      1. 从当前位置开始第一轮扫描：找第一类页面即A=M=0
      2. 若1失败，则第二轮扫描，找第二类页面即A=0，M=1，遇到A=1的页面将其置0
      3. 若2也失败，第三轮扫描，找第一类页面
      4. 若3也失败，第四轮扫描，找第二类页面，此时一定可以成功
   3. 

3.2_4 页面分配策略

驻留集：请求分页存储管理中给进程分配的物理块的集合

分配驻留集时需要考虑：

1. 分配给一个进程的页框越少，驻留在主存中的进程数量就越多，可以提高并发度
2. 若进程在主存中页面过少，则缺页率会增加
3. 分配的页框过多，由于局部性原理，缺页率不会有太大影响，并发度降低

固定分配：进程运行期间驻留集大小不变
可变分配：进程运行期间驻留集大小可变
局部置换：缺页时只能选进程自己的物理块进行置换
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程

内存分配策略

1. 固定分配局部置换
   1. 平均分配算法
   2. 按比例分配算法：依据进程大小按比例分配物理块
   3. 优先权分配算法：重要和紧迫的进程分配较多物理块
2. 可变分配全局置换：只要缺页就分配新的空闲物理块
3. 可变分配局部置换：根据缺页频率动态地增减进程的物理块

调入页面的时机

1. 预调页策略：基于局部性原理，一次调入若干个相邻的页面。主要用于进程的首次调入
2. 请求调页策略：缺页才将所缺页面调入内存

从何处调入页面？

抖动（颠簸）现象

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存
产生抖动主要原因是：进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够

工作集：某段时间间隔里进程实际访问页面的集合，由时间$t$和窗口大小$\Delta$确定

工作集题目：求某一时刻的工作集，在该时间点往前找窗口，访问的页面集合就是工作集

题目总结区
1. 考虑页面置换算法，系统中有m个物理块供调度，初始全空，页面引用字符串长度p，包含n个不同页号，无论采用什么算法，缺页次数不会少于n次
2. 虚拟存储器的最大容量由计算机的地址结构决定
3. LRU算法实现起来耗费高的原因：需要对所有页实现排序
4. 虚拟存储器系统页表项中，决定是否发生页故障的是：“合法位”
5. 内存抖动的主要原因：页面置换算法不合理
6. 计算机系统中，快表用于地址变换

赏

谢谢你请我吃糖果

支付宝

微信