【计算机操作系统】3-1-内存管理

内存的基础知识

• 什么是内存，有何作用
  • 存储单元
  • 内存地址
• 进程运行的基本原理
  • 指令的工作原理
  • 逻辑地址 vs 物理地址
  • 从写程序到程序运行：编辑—编译—链接—装入
  • 三种链接方式
  • 三种装入方式

什么是内存？有何作用？

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

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

内存中也有一个一个的“小房间”，每个房间就是一个“存储单元”。

如果计算机“按字节编址”，则每个存储单元大小为1字节，即1B，即8各二进制位。

如果字长为16位的计算机“按字编址”，则每个存储单位大小为1个字；每个字的大小为16各二进制位。

进程的运行原理——指令

我们写的代码要翻译成CPU能识别的指令。这些指令会告诉CPU应该去内存的哪个地址存/取数据，这个数据应该做什么样的处理。在这个例子中，指令中直接给出了变量x的实际存放地址(物理地址)。但实际在生成机器指令的时候并不知道该进程的数据会被放到什么位置。所以编译生成指令中一般是使用逻辑地址(相对地址)

逻辑地址 vs 物理地址

指令中的地址也可以采用这种思想。编译时产生的指令只关心“相对地址”，实际放入内存中时再想办法根据起始位置得到“绝对地址”。

Eg:编译时只需确定变量x存放的地址是100(也就是说相对于进程在内存中的起始地址而言的地址)。CPU想要找到x在内存中的实际存放位置，只需要用进程的起始地址+100即可。

相对地址又称逻辑地址，绝对地址又称物理地址。

从写程序到程序运行

• 编译：由编译程序将用户源代码编译成若干个目标模块(编译就是把高级语言翻译成机器语言)
• 链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块
• 装入(装载)：由装入程序将装入模块装入内存运行。

装入模块装入内存

装入模块中的指令地址指的是“相对地址”，即：相对于开始地址而言的地址。相对地址又称逻辑地址。

• 装入的三种方式(用三种不同的方法完成逻辑地址到物理地址的转换)：
  1. 绝对装入
  2. 静态重定位
  3. 动态重定位

装入的三种方式——绝对装入

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

编译、链接后得到的装入模块的指令直接就使用了绝对地址。

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

程序中使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。通常情况下都是编译或汇编时再转换为绝对地址。

装入的三种方式——静态重定位

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

静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。

作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。

装入的三种方式——动态重定位

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

重定位寄存器：存放装入模块存放的起始位置。

采用动态重定位时允许程序在内存中发生移动。并且可将程序分配到不连续的存储区中；在程序运行期那只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存：便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。

链接的三种方式

1. 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接程一个完整的可执行文件(装入模块)，之后不再拆开。
2. 装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式。
3. 运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。

---

总结

• 什么是内存，有何作用
  • 存储单元、内存地址的概念和联系
  • 按字节编址vs按字编址
• 进程运行的基本原理
  • 指令的工作原理
    • 操作码+若干参数(可能包含地址参数)
  • 逻辑地址 vs 物理地址
  • 从写程序到程序运行
    • 编辑源代码文件
    • 编译
      • 由源代码文件生成目标模块(高级语言“翻译”为机器语言)
    • 链接
      • 由目标模块生成装入模块，链接后形成完整的逻辑地址
    • 装入
      • 将装入模块装入内存，装入后形成物理地址
  • 三种链接方式
    • 静态链接
      • 装入前链接成一个完整装入模块
    • 装入时动态链接
      • 运行前边装入边链接
    • 运行时动态链接
      • 运行时需要目标模块才装入并链接
  • 三种装入方式
    • 绝对装入
      • 编译时产生绝对地址
    • 可重定位装入
      • 装入时将逻辑地址转换为物理地址
    • 动态运行时装入
      • 运行时将逻辑地址转换为物理地址，需要设置重定位寄存器

内存管理的概念

• 内存空间的分配与回收
• 内存空间的扩充
• 地址转换
• 存储保护

内存空间的分配与回收

操作系统负责内存空间的分配于回收

内存空间的扩展

操作系统需要提供某种技术从逻辑上对内存空间进行扩充。

地址转换

为了使编程更方便，程序员写程序时应该只需要关注指令、数据的逻辑地址。而逻辑地址到物理地址的转换（这个过程称为地址重定位）应该由操作系统负责，这样就保证了程序员写程序时不需要注意物理内存的实际情况。

操作系统需要提供地址转换功能，负责程序的逻辑地址于物理地址的转换。

• 三种装入方式

内存保护

操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰。

• 内存保护可采取两种方法：
  1. 在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。
  2. 采用重定位寄存器(又称基址寄存器)和界地址寄存器(又称限长寄存器)进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

---

总结

• 内存空间的分配与回收
• 内存空间的扩充(实现虚拟性)
• 地址转换
  • 操作系统负责实现逻辑地址到物理地址的转换
  • 三种方式
    • 绝对装入
    • 可重定位装入
    • 动态运行时装入
• 存储保护
  • 保证各进程在自己的内存空间内运行，不会越界访问
  • 两种方式
    • 设置上下限寄存器
    • 利用重定位寄存器、界地址寄存器进行判断

覆盖与交换

• 内存空间的分配与回收
• 内存空间的扩充
  • 覆盖技术
  • 交换技术
  • 虚拟存储技术
• 地址转换
• 存储保护

覆盖技术

早期的计算机内存很小，比如IBM推出的第一台PC机最大只有1MB大小的内存。因此经常会出现内存大小不够的情况。

后来人们引入了覆盖技术，用来解决“程序大小超过物理内存总和”的问题。

覆盖技术的思想：将程序分为多个段(多个模块)。常用的段常驻内存，不常用的段在需要时调入内存。

内存中分为一个“固定区”和若干个“覆盖区”。

需要常驻内存的段放在“固定区”中，调入后就不再调出(除非运行结束)

按照自身逻辑结构，让那些不可能同时被访问的程序段共享同一个覆盖区。

必须由程序员声明覆盖结构，操作系统完成自动覆盖。

缺点：对用户不透明，增加了用户编程负担。

覆盖技术只用于早期的操作系统中，现在已成为历史。

交换技术

交换(对换)技术的设计思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)

**中级调度(内存调度)**，就是要决定将哪个处于挂起状态的进程重新调入内存。

暂时换出外存等待的进程状态为挂起状态(挂起态,suspend)

挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。

1. 应该在外存(磁盘)的什么位置保存被换出的进程？

2. 什么时候应该交换？

3. 应该换出哪些进程？

4. 具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式；对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式。总之，对换区的I/O速度比文件区的更快。

5. 交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如：在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程；如果缺页率明显下降，就可以暂停换出。

6. 可以优先换出阻塞进程；可换出优先级低的进程；为了防止优先级的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间。

PCB会常驻内存，不会被换出外存

---

总结

• 覆盖技术
  • 一个固定区
    • 存放最活跃的程序段
    • 固定区中的程序段在运行过程中不会调入调出
  • 若干覆盖区
    • 不可能同时被的访问程序段可共享一个覆盖区
    • 覆盖区中的程序段在运行过程中会根据需要调入调出
    • 必须由程序员声明覆盖结构，操作系统完成自动覆盖
    • 缺点：对用户不透明，增加了用户编程负担
• 交换技术
  • 内存紧张时，换出某些进程以腾出内存空间，再换入某些进程
  • 磁盘分为文件区和对换区，换出的进程放在对换区
• 覆盖与交换的区别
  • 覆盖是在同一个程序或进程中的
  • 交换是在不同进程(或作业)之间的

连续分配管理方式

• 连续分配管理方式
  • 单一连续分配
  • 固定分区分配
  • 动态分区分配

连续分配：指为用户进程的必须是一个连续的内存空间

单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。

内存中只能有一道用户程序，用户程序独占整个用户区空间。

优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护(eg:早期的PC操作系统MS-DOS)

缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。有很大一部分用户区空闲，内存利用率低。

有内部碎片：分配给某进程的内存区域中，如果有些部分没有用上，就是“内存碎片”。

固定分区分配

• 分区大小相等
• 分区大小不等

20世纪60年代出现了支持多道程序的系统，为了能子啊内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。

分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合(比如：钢铁厂有n个相同的炼钢炉，就可把内存分为n个大小相等的区域存放n个炼钢炉控制程序)

分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分(比如：划分多个小分区、适量中等分区、少量大分区)

操作系统需要建立一个数据结构——分区说明表，来实现各个分区的分配于回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态(是否已分配)

分区号	大小(MB)	起始地址(M)	状态
1	2	8	未分配
2	2	10	未分配
3	4	12	已分配
…	…	…	…

当用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为“已分配”。

• 优点：
  1. 实现简单
  2. 无外部碎片
• 缺点：
  1. 当用户程序太大时可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能
  2. 会产生内部碎片，内存利用率低

动态分区分配

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

动态分区分配没有内部碎片，但是有外部碎片。

• 内部碎片：分配给某进程的内存区域内，如果有些部分没有用上。
• 外部碎片：是指内存中的某些空闲翻去由于太小而难以利用。

如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。

可以通过紧凑技术来解决外部碎片。

1. 系统要用什么样的数据结构记录内存的使用情况？
2. 当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？
3. 如何进行分区的分配与回收操作？

系统要用什么样的数据结构记录内存的使用情况？

• 空闲分区表
• 空闲分区链

空闲分区表：每个空闲分区对应一个表项。表项中包括分区号、分区大小、分区起始地址等信息。

分区号	分区大小(MB)	起始地址(M)	状态
1	20	8	空闲
2	10	32	空闲
3	4	60	空闲

---

空闲分区表：每个分区的其实部分和末尾部分分别设置前向指针和后向指针。起始部出处可记录分区大小等信息。

就是一个双向链表。

当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？

把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表(或空闲分区链)中选出一个分区分配给该作业。由于分配算法对系统性能有很大的影响，因此有多种情况。

如何进行分区的分配与回收操作？

---

总结

• 单一连续分配
  • 只支持单道程序，内存分为系统区和用户区，用户程序放在用户区
  • 无外部碎片，有内部碎片
• 固定分区分配
  • 支持多道程序，内存用户空间分为若干个固定大小的分区，每个分区只能装一道作业
  • 无外部碎片，有内部碎片
  • 两种分区方式
    • 分区大小相等
    • 分区大小不等
• 动态分区分配
  • 支持多道程序，在进程装入内存时，根据进程的大小动态地建立分区
  • 无内部碎片，有外部碎片
  • 外部碎片可用“紧凑”技术来解决
  • 回收内存分区时，可能遇到四种情况

动态分区分配算法

动态分区分配算法：在动态分区分配方式中，当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？

• 首次适应算法(First Fit)
• 最佳适应算法(Best Fit)
• 最坏适应算法(Worst Fit)
• 邻近适应算法(Next Fit)

首次适应算法

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

如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

最佳适应算法

算法思想：由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。

如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

最坏适应算法

又称最大适应算法

算法思想：为了解决最佳适应算法的问题——即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

邻近适应算法

算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

如何实现：空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来(最佳适应算法的优点)

邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用(最大适应算法的缺点)。

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

• 考虑支持多道程序的两种连续分配方式：
  1. 固定分区分配：缺乏灵活性，会产生大量的内部碎片，内存的利用率很低。
  2. 动态分区分配：会产生很多外部碎片，虽然可以用“紧凑”技术来处理，但是“紧凑”时间代价很高。

如果允许将一个进程分散地装入到许多不相邻的分区中，便可充分地利用内存，而无需再进行“紧凑”。

基于这一思想，产生了“非连续分配方式”，或者称为“离散分配方式”。

• 非连续分配管理方式

  • 基本分页存储管理
  • 基本分段存储管理
  • 段页式存储管理

• 连续分配：为用户进程分配的必须是一个连续的内存空间

• 非连续分配：为用户进程分配的可以时一些分散地内存空间

把“固定分区分配”改造为“非连续分配版本”

如果把分区大小设置的更小一些。内部碎片会更小，内存利用率会更高。

基本分区存储管理的思想——把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。

分页存储管理的基本概念

将内存空间分为一个个大小相等的分区(比如：每个分区4KB)，每个分区就是一个“页框”，或称“页帧”、“内存块”、“物理块”。每个页框有一个编号，即“页框号”(或者“内存块号”、“页帧号”、“物理块号”)页框号从0开始。

将用户进程的地址空间也分为与页框大小相等的一个个区域。称为页或页面，每个页面也有一个编号，即页号，页号也是从0开始

注：进程的最后一个页面可能没有一个页框那么大。因此，页框不能太大，否则可能产生过大的内部碎片。

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。

各个页面不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中。

如何实现地址的转换

1. 要算出逻辑地址对应的页号
2. 要知道该页号对应页面在内存中的起始地址
3. 要算出逻辑地址在页面内的“偏移量”。
4. 物理地址=页面始址+页内偏移量

• 如何计算：
  • 页号=逻辑地址/页面长度(取除法的整数部分)
  • 页内偏移量 = 逻辑地址%页面长度(取除法的余数部分)
  • 页面在内存中的其实位置：操作系统需要用某种数据结构记录进程各个页面的起始位置。

页号 = 80/50 = 1
页内偏移量 = 80 % 50 = 30
1号页在内存中存放的其实位置为450

为了方便计算页号、页内偏移量，页面大小一般设为2的整数幂。

如果每个页面大小为2的k次方B，用二进制数表示逻辑地址，则末尾k位即为页内偏移量，其余部分就是页号。

因此，如果让每个页面的大小为2的整数幂，计算机就可以很方便地得出一个逻辑地址对应的页号和页内偏移量。

逻辑地址结构

分页存储管理的逻辑地址结构如下所示：

31 … 12	11 … 0
页面P	页内偏移量W

地址结构包含两个部分：前一部分为页号，后一部分为页内偏移量W。在上图所示的例子中，地址长度为32位，其中011位位“页内偏移量”，或称“页内地址”；1231位为“页号”。

如果有K为表示“页内偏移量”，则说明该系统中一个页面的大小是2的K次方各内存单元。

如果有M位表示“页内”，则说明在该系统中，一个进程最多允许有2的M次方个页面。

• 分页存储管理中，实现地址转化：
  1. 要算出逻辑地址对应的页号
  2. 要知道该页号对应页面在内存中的起始地址
  3. 要算出逻辑地址在页面内的“偏移量”
  4. 物理地址=页面始址+页面偏移量

页表

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

1. 一个进程对应一张页表
2. 进程的每一页对应一个页表项
3. 每个页表项由“页号”和“块号”组成
4. 页表记录进程页面和实际存放的内存块之间的对应关系。

M号内存块的起始地址就是M*内存块大小

块号（页表项长度）是固定的，只需要知道页表存放的起始位置和页表项长度，即可找到各个对应的页表项存放的位置。

---

总结

• 基本分页存储管理的思想：把进程分页，各个页面可离散地放到各个内存块中
• 重要概念
  • 页框、页帧、内存块、物理块 VS 页、页面
  • 页框号、页帧号、内存块号、物理块号 VS 页号、页面号
• 如何实现地址转换
  1. 计算出逻辑地址对应的页号
  2. 找到对应页面在内存中的存放位置
  3. 算出逻辑地址对应的页内偏移量
  4. 物理地址 = 页面始址 + 页内偏移量
• 页号、页内偏移量的计算
  • 页号 = 逻辑地址/页面大小;页内偏移量 = 逻辑地址%页面大小
  • 或根据逻辑地址结构计算，逻辑地址 = [页号P,页内偏移量W]
• 页表
  • 页表记录进程页面和实际存放的内存块之间的对应关系
  • 一个进程对应一张页表，进程的每一页对应一个页表项，每个页表项由“页号”和“块号”组成
  • 每个页表项的长度时相同的，页号时“隐含”的。

基本地址变换机构

这个内容属于基本分页存储管理

重点理解、记忆基本地址变换机构(用于实现逻辑地址到物理地址转换的一组硬件机构)的原理和流程

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

通常会在系统中设置一个页表寄存器(PTR)，存放页表在内存中的起始地址F和页表长度M。

进程未执行时，页表的始址 和 页表长度 放在进程控制块(PCB)中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

理论上，页表项长度为3B即可表示内存块号的范围，但是，为了方便页表的查询，常常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整数个页表项。

进程页通常是装在连续的内存块中。

---

总结

• 页表寄存器的作用
  • 存放页表起始地址
  • 存放页表长度
• 地址变换过程
  1. 根据逻辑地址算出页号、页内偏移量
  2. 页号的合法性检查(与页表长度对比)
  3. 若页号合法，再根据页表起始地址、页号找到对应页表项
     1. 第一次访问内存：查页表
  4. 根据页表项中记录的内存块号、页内偏移量 得到最终的物理地址
  5. 访问物理内存对应的内存单元
     1. 第二次访问内存：访问目标内存单元
• 其他小细节
  • 页内偏移量位数与页面大小之间的关系(要能用其中一个条件推出另一个条件)
  • 页式管理中地址是一维的
  • 实际应用中，通常使一个页框恰好能放入整数个页表项
  • 为了方便找到页表项，页表一般时放在连续的内存块中的

具有块表的地址变换机构

• 局部性原理
• 什么是块表(TLB)
• 引入块表后，地址的变换过程

局部性原理

int i = 0;
int a[100];
while(i<100){
  a[i] = i;
  i++;
}
  //这个程序执行时，会频繁访问“存放程序对应的指令”，“存放程序中定义的变量”。

• 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能子啊次被访问(因为程序中存在大量的循环)
• 空间局限性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(连续存放)

由于局部性原理，可能连续很多查到的都是同一个页表。既然如此，能否利用这个特性减少访问页表次数？

什么是块表(TLB)

块表，又称联想寄存器(TLB)，是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

就是一个高速缓冲而已。

在找到页表项后，应同时将其存入块表，以便后面的可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换。

两级页表

• 单级页表存在什么问题？如何解决？
• 两级页表的原理、逻辑地址结构
• 如何实现地址变换
• 两级页表问题需要注意的几个细节

单级页表存在的问题

需要给进程分配多个连续的页表框来存放页表，丧失了离散分配的优点。

进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。

如何解决单级页表的问题？

对长页表进行分组，再建立一张页表，称为页目录表，或称外层页表，或称顶层页表。

可以在需要访问页面时才把页面调入内存(虚拟存储技术)。可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存

若想访问的页面不在内存中，则产生缺页中断(内中断)，然后将目标页面从外存调入内存。

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

两级页表结构的逻辑地址结构
|31 … 22|21 … 12|11 … 0|
|:—:|:—:|:—:|
|一级目录|二级目录|页内偏移量|

如何实现地址变换

1. 按照地址结构将逻辑地址拆分成三部分
2. 从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置
3. 根据二级页号查表，找到最终想访问的内存块号
4. 结合页内偏移量得到物理地址

需要注意的几个细节

1. 若采用多级页表机制，则各级页表的大小不能超过一个页面
2. 两级页表的访问次数分析(假设没有快表机构)：
   1. 第一次访存：访问内存中的页目录表
   2. 第二次访存：访问内存中的二级页表
   3. 第三次访存：访问目标内存单元

---

总结

• 单级页表存在的问题
  • 所有页表项必须连续存放，页表过大时需要很大的连续空间
  • 在一段时间内并非所有页面都用得到，没有必要让整个页表常驻内存
• 两级页表
  • 将长长的页表再分页
  • 逻辑地址结构：(一级页号，二级页号，页内偏移量)
  • 注意几个术语：页目录表/外层页表/顶级页表
• 如何实现地址变换
  1. 按照地址结构将逻辑地址拆分成三部分
  2. 从PCB中读出页目录表始址，根据一级页号查页目录表，找到下一级页表再内存中的存放位置
  3. 根据二级页号查表，找到最终想访问的内存块号
  4. 结合页内偏移量得到物理地址
• 几个细节
  • 多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级。
  • 多级页表的访存次数(假设没有快表机构)——N级页表访问一个逻辑地址需要N+1次访存

基本分段存储管理方式

• 什么是分段(类似于分页管理中的“分区”)
• 什么是段表(类似于分页管理中的“页表”)
• 如何实现地址变换
• 分段、分页管理的对比

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

分段

进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名(在低级语言中，程序员使用段名来编程)，每段从0开始编址。

由于是按逻辑功能模块划分，用户编程更方便，程序的可读性更高

LOAD 1,[D]|<A>; //将分段D中A单元内的值读入寄存器1
STORE 1,[X]|<B>;  //将寄存器1的内容存入X分段的B单位中

编译程序会将段名转换为段号

分段系统的逻辑地址结构由段号(段名)和段内地址(段内偏移量)所组成：

31 … 16	15 … 0
段号	段内地址

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

段内地址位数决定了每个段的最大长度时多少

程序分为多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称“段表”。

段号	段长	基址
0	7K	80K
1	3K	120K
2	6K	40K

1. 每个段对应一个段表项，其中记录了该段在内存中的起始位置(又称“基址”)和段的长度。
2. 各个段表项的长度是相同的。由于长度相同，因此段号可以是隐含的，不占存储空间。

LOAD 1,[D]|<A>; //将分段D中A单元内的值读入寄存器1

分段、分页管理的对比

页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行文，对用户是不可见的。

段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。

页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。

• 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
• 分段的用户进程地址空间是二维的，程序员在表示一个地址时，既要给出段名，也要给出段内地址。

分段比分页更容易实现信息的共享和保护。不同的进程可以在自己的段表内添加同一个段就能实现进程间数据共享。

不能被修改的代码称为纯代码或可重入代码(不属于临界资源)，这样的代码时可以共享的。可修改的代码时不能共享的(比如：有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致)

---

总结

• 分段
  • 将地址空间按照程序自身的逻辑关系划分为若干个段，每段从0开始编址
  • 每个段在内存中占据连续空间，但各段之间可以不相邻
  • 逻辑地址结构：(段号,段内地址)
• 段表
  • 记录逻辑段到实际存储地址的映射关系
  • 每个段对应一个段表项，各段表项长度相同，由段号(隐含)、段长、基址组成
• 地址变换
  1. 由逻辑地址得到段号、段内地址
  2. 段号与段表寄存器中的段长比较，检查是否越界
  3. 由段表始址、段号找到对应段表项
  4. 根据段表中记录的段长，检查段内地址是否越界
  5. 由段表中的“基址+段内地址”得到最终的物理地址
  6. 访问目标单元
• 分段 VS 分页
  • 分页对用户不可见，分段对用户可见
  • 分页的地址空间是一维的，分段的地址空间是二维的
  • 分段更容易实现信息的共享和保护(纯代码/可重入代码可以共享)
  • 分页(单级页表)、分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构

段页式管理方式

• 分页、分段管理方式中最大的优缺点
• 分段+分页的结合——段页式管理方式
• 段表、页表
• 如何实现地址变换

分页、分段的优缺点分析

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

分段+分页=段页式管理

将进程按逻辑模块分段，再将各段分页(如每个页面4KB)

再将内存空间分为大小相同的内存块/页框/页帧/物理块

段页式管理的逻辑地址结构

|31 … 16|15 … 12|11 … 0|
|段号|分页|页内偏移量|

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

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

页内偏移量决定了页面大小、内存块大小是多少

“分段”对用户是可见的，程序员编程时需要显式地给出段号、段内地址。而将各段“分页”对用户是不可见的。系统会根据段内地址自动划分页号和页内偏移量。

因此段页式管理的地址结构是二维的。

段表、页表

每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号(页表起始地址)组成。每个段表项长度相等，段号是隐含的。

每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的。

---

总结

• 分段+分页
  • 将地址空间按照程序自身的逻辑关系划分为若干个段，在将各段分为大小相等的页面
  • 将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存
  • 逻辑地址结构：（段号，页号，页面偏移量）
• 段表、页表
  • 每个段对应一个段表项。各段表项长度相同，由段号(隐含)、页表长度、页面存放地址 组成
  • 每个页对应一个页表项。各页表项长度相同，由页号(隐含)、页面存放的内存块号 组成
• 地址变换
  1. 由逻辑地址得到段号、页号、页面偏移量
  2. 段号与段表寄存器中的段长度比较，检查是否越界
  3. 由段表始址、段号找到对应段表项
  4. 根据段表中记录的页表长度，检查页号是否越界
  5. 由段表中的页表地址、页号得到查询页表，找到相应页表项
  6. 由页面存放的内存块号、页内偏移量得到最终的物理地址
  7. 访问目标单元
• 访问一个逻辑地址所需访存次数
  • 第一次——查段表、第二次——查页表、第三次——访问目标单元
  • 可引入快表机构，以段号和页号Wie关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存。