第四章：存储器管理

💡整理不易，先赞后看，养成习惯💡

4.1 存储器的层次结构

在计算机执行时，几乎每一条指令都涉及对存储器的访问，因此存储器的速度必须非常快，能与处理机的速度相匹配。
此外还要求存储器的具有非常大的容量，而且存储器的价格还应很便宜。
这样三个条件，目前是无法同时满足的，因而采取多层结构的存储器系统

存储器的多层结构

在目前的操作系统中，几乎所有的指令都涉及到访存操作，如果想要提高操作系统的工作效率，就一定要保证存储器的速度。
此外存储器的大小，以及价格也是衡量存储器优良的标准。
好的存储器就需要满足以下三点：

• 价格低
• 存储容量大
• 存储速度快

但是目前来说，三个条件无法同时满足，最多只能满足其中两个，所以出现了存储器的多层存储器。

从上到下：容量由小到大，速度由快到慢，价格由高到低。
其中：

• 系统管理：寄存器、高速缓存、主存储器和磁盘缓存

• 设备管理：固定磁盘和可移动存储介质

  可执行存储器：寄存器、主存

  :::info 可执行存储器是一种计算机主存储器，用于存储计算机程序的指令。与只读存储器（ROM）不同的是，可执行存储器可以被写入和擦除，因此其内容可以根据需要更改。当计算机执行程序时，它会从可执行存储器中读取指令并执行它们。 :::

  主存储器

  :::info 💡主存储器用于存放进程运行时的程序和数据。 :::

• CPU的都是从主存中取指令和数据

• CPU与外设交换信息时也依靠主存主存
• 与CPU的速度矛盾,引入寄存器和高速缓存

寄存器

:::info 寄存器具有与处理机相同的速度，完全能与CPU协调工作，但价格十分昂贵，因此容量不可能很大。 :::

• 用于加速存储器的访问速度

• 存放处理机运行时的数据

  缓存

  :::info 缓存是指在数据访问中将经常使用的数据暂时保存到快速访问的存储器中，以便加快数据访问速度的技术。 :::

• 高速缓存：从几十KB到几MB，访问速度快于主存。

  • 将主存中一些经常访问的信息存放在高速缓存中，可提高程序执行速度。
  • 它是介于寄存器和存储器之间的存储器件
  • 其容量大于寄存器，速度快于主存。

• 磁盘缓存：介于磁盘和主存之间

  • 将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。
  • 提供对主存储器存储空间的扩充一个文件的数据可能出现在不同存储器层次中

    内存管理的目标

• 内存分配：

  • 使得各得其所、提高利用率及适应动态增长的需求
  • 连续分配/离散分配
• 地址映射：
  • 逻辑地址转换为物理地址，与分配方式有关
• 内存保护：
  • 基于地址的保护、存取访问控制保护
• 内存扩充：
  • 对换技术、虚拟技术

4.2 程序的装入和连接

内存的物理组织

基本概念

• 物理地址：指在计算机内存中实际的存储位置
• 逻辑地址：应用程序或进程使用的地址，它对应的是虚拟内存中的地址
• 重定位：即是将可执行文件中逻辑地址变换成主存中物理地址的过程，称为地址重定位（或地址映射）。

  操作系统负责将逻辑地址转换为物理地址，然后再去执行具体的读写操作。

为什么要进行地址转换

首先我们要知道为什么需要逻辑地址，这是因为程序再内存当中的存储很多时候都不一定是完全连续的，很多情况下都是东一块西一块的样子，所以可以建立一个虚拟内存，让程序在虚拟内存中是连续的，这样做的目的是：优化内存管理，提高系统的性能。
程序的逻辑地址与分配到内存物理地址不一定一致, 所以要进行地址转换。

可执行程序的执行步骤

在程序被执行前需要执行以下步骤：

• 编译：形成目标模块(形成逻辑地址)
• 链接：由多个目标模块或程序库生成可执行装入模块(更新逻辑地址)
• 装入：构造PCB，形成进程(使用物理地址)

  其中的链接这一步可以理解为把多个小块的逻辑地址联合成一个大块的逻辑地址集合。

程序的装入

程序的装入更容易理解的方式：将一个编译好的可执行文件读入计算机内存，并使之运行的过程。
可执行程序装入内存需要解决的问题：

1. 如何装入待执行的程序及其所需的数据？
2. 何时将程序的逻辑地址转换为物理地址？

装入的方式有三种：

• 绝对装入方式
• 静态重定位装入方式

• 动态重定位装入方式

  绝对装入方式

  这种装入方式是最简单的装入方式，即按程序逻辑地址将程序和数据装入内存。逻辑地址即物理地址。
  这样做的优点就是实现简单，无需进行地址变换。
  缺点：

• 程序中使用绝对地址

• 程序装入内存指定地址段
• 程序员熟悉内存的使用情况
• 程序动态修改或装入困难

  静态重定位装入方式

  :::info 装入程序把目标模块中的逻辑地址与本程序在内存中的起始地址相加得到正确的物理地址。 ::: 例如：
  
  左边为逻辑地址块，右边为物理地址块。
  在逻辑地址中，LOAD的地址为1250，而这个逻辑地址对应物理地址的起始地址为10000，所以LOAD的物理地址应该是10000 + 1250 = 11250。
  这种装入方式允许程序装入与逻辑地址不同的物理地址空间。
  用户程序被装入内存时，需进行地址转换。
  地址映射在装入时一次性完成，以后不再更改程序地址，故也称静态重定位。
  优点：实现简单，不要硬件的支持。
  缺点：程序装入内存后，移动就比较困难。

  动态运行时装入方式

  地址转换在程序运行时动态进行。需要硬件支持，即**重定位寄存器**。
  把相对地址和绝对地址的转换推迟到程序真正执行时才进行。程序被执行时，通过重定位寄存器内的起始物理地址和指令或数据的逻辑地址计算其物理地址。
  程序中不执行的部分就不做地址映射的工作，这样节省了CPU的时间。

  现代计算机系统中都采用动态重定位技术。

程序的链接

:::info 链接用于它将分别在不同的目标文件中编译或汇编的代码收集到一个可直接执行的文件中。 :::

比如我们写的c语言文件中的导包，就是链接操作。

3种链接方式：

• 静态链接
• 装入时动态链接

• 运行时动态链接

  静态链接

  :::info 在程序运行之前，将所有目标模块及所需库函数，完全链接成一个装入模块，以后不再拆开。 ::: 主要做了以下两件事：

• 对逻辑地址进行更新：相对于整个模块第一条语句的起始地址重新计算。

• 变换外部调用符号：程序被装入内存之前，将其中的外部调用符号全部转换为相对地址跳转语句。

具体来说，静态链接方式会将所有用到的函数、变量等符号从其它模块拷贝过来，然后重新组合成一个独立可执行的二进制文件。当程序执行时，操作系统将整个可执行文件装载到内存中运行，不再需要额外的依赖关系。
静态链接的优点是可执行文件完全自包含，安装简单、可移植性高，且不需要考虑对应库的版本问题，保证了程序的稳定性。
而缺点则在于可执行文件较大，可能会占用较多的磁盘空间，同时也不支持动态更新和共享，即使库中的某些功能未被使用，也会被全部加载到内存中，影响了系统资源的利用效率。

举个例子： 比如我们写了一个文件，需要生成一个随机数，那么我们就可能需要一个Math库，静态引入就会把整个库引入过来，但实际我们只需要其中的random模块即可，所以这会导致浪费资源的利用率。

装入时动态链接

:::info 装入时动态链接：不用事先进行链接，系统装入可执行模块时，才进行链接。 :::

• 生成的装入模块，含有未被链接的外部模块引用，这些外部模块可以在装入时链接。
• 在装入时，遇到未链接的外部模块引用，则查找并将其装入内存，同时更新模块内的指令地址。

在装入时动态链接方式中，编译生成的可执行文件包含对所依赖库（如共享库）或外部符号（如另一个可执行文件）的引用，但是并不将这些代码本身加入到可执行文件中。当进程被装载时，操作系统会根据需要，在内存中为其分配适当的空间，并将所需的库或符号加载到进程的地址空间中。
与静态链接相比，动态链接能够节省磁盘空间，提高资源利用效率，且支持运行时更新和共享，当一个共享对象被多个程序使用时，每个程序只需要在内存中保留一份该对象的拷贝即可，因而大大减少了内存使用量，降低了系统开销。同时，也方便了动态库的维护和升级，可以避免重复修改多个应用程序的情况。
优点：

• 有便于目标模块的更新与升级；
• 有利于代码共享；
• 有利于扩充软件的功能，可以将扩充部分作为动态链接模块。

缺点：可能会链接一些不会执行的模块，浪费存储空间和处理机时间。

运行时动态链接

:::info 外部模块引用直到程序执行时才装入内存，并连接到装入模块中，进行地址转换。 ::: 优点：可以解决静态链接和装入时动态链接都面临的存储空间和处理机时间浪费问题，不需要执行的模块不会装入内存。

4.3 连续分配存储管理方式

什么是连续分配存储

连续分配是指为一个用户程序分配一个连续的内存空间。
把内存分成若干个大小不等的连续区域，称作分区，每个作业一般占用一个分区。

基本分配方式

单一连续分配

这种分配方式把内存分为两个区域：系统区，用户区

地址重定位时，只要将指令或数据的逻辑地址加上用户区基地址，就可以形成物理地址。

也就是说进程被调入内存之后就会进入这里的用户区。

固定分区分配

:::info 固定式分区是在作业装入之前，将内存空间划分为若干个固定大小的区域，每个分区中可以装入一道作业。 :::
如上图所示，每一块分区的大小都是相同的，进程无论大小如何都会只占用一个分区。
优点是划分简单，但是缺乏灵活性，内存利用率不高。

• 当程序太小时，会造成内存空间的浪费
• 当程序太大时，可能不足以装入程序，而使程序无法运行；
• 只适合于多个相同程序的并发执行

面对上面的问题，只要让划分分区大小不等，就可以很好解决上述问题。
一般来说会分配多个小分区、适量的中等分区、少量的大分区。

根据程序的大小，分配当前空闲的、适当大小的分区。

不同大小的分区为了方便记录，会采用分区使用表(内存分配表)这种数据结构：

记录分区的区号、起始地址、大小、占用情况

其中：
0-20KB是属于系统的区块，剩下的就是用户区块，而区块1被用户作业A占用。

• 固定分区分配过程：
  • 装入时，由内存分配程序检索内存分配表
  • 找出能满足要求的空闲分区分配给用户
  • 修改内存分配表中该分区对应表项的状态
  • 若找不到大小足够的分区，则拒绝分配内存
• 固定分区回收过程：
  • 程序执行完毕，释放占用分区
  • 内存管理程序将改分区的状态置为未分配

虽然划分分区大小不固定了，可以有效解决空间浪费问题，但是由于作业的大小装入前还是未知的，所以这种方法只能预防，不能彻底解决，还是会存在上述空间浪费等问题。
我们把不能被利用的分区空间叫做**内碎片**。

比如这里的淡黄色区块，就是内碎片。

动态分区分配

:::info 动态分区是指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。 ::: 动态分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分。
这种存储管理技术是固定式分区的改进，既可以获得较大的灵活性，又能提高内存的利用率。
动态分区分配中的数据结构如下：

• 空闲分区表

空闲分区表为每个尚未分配的分区设置一个表项，由多个固定大小、空间已经被预分配好的块组成，包括分区的序号、大小、始址和状态。

在空闲分区表中，所有未被占用的内存块都按照大小顺序排列，最小的内存块位于链表的头部，而最大的内存块位于尾部。

• 空闲分区链

为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息以及用于链接其它分区的前向指针；在分区尾部，则设置了一个后向指针。通过前、后向指针将所有的分区链接成一个双向链表。
当需要新的内存块时，操作系统会从链表头部开始查找，找到第一个大小不小于所需内存的空闲块，如果该块过大，则需要对其进行划分；释放回收内存时，新的空闲块将会和原先的空闲块合并形成更大的连续内存块。

在未回收内存的时候，内存分配如下。系统运行过程中，形成多个空闲的不连续的存储区，称为空闲区
外碎片：分区之间无法利用的存储空间，通常是小空闲区

空闲区是未被进程占用的分区 外碎片是被进程占用之后分区剩下的部分

解决办法就是拼接或紧凑技术，把分散的多个小空闲区合并为一个大的空闲分区。
回收合并内存的原则如下：

1. 上邻空闲区：合并，改大小
2. 下邻空闲区：合并，改大小，首址。
3. 上、下邻空闲区：合并，改大小。
4. 不邻接：则建立一新表项。

   动态重定位分区分配

   本小节需要先看完基于顺序搜多的动态分区分配算法

如果系统中只有若干空闲小分区，即使总容量和大于要装入的程序，由于连续分配方式要求连续，所以还是不能装入新的程序。
如果可以将所有程序进行移动，可以将原来分散的空闲的小分区挪成一个大分区。就可以装入新程序。这种方式叫“拼接”或“紧凑”。

动态重定位分区分配算法与动态分区分配算法基本相同，差别仅在于，在动态重定位算法中增加了紧凑的功能。

基于顺序搜索的动态分区分配算法

:::info 动态分区分配中的分区分配算法是指，用于决定系统如何从一系列空闲物理内存块中选择一个与进程所需的大小相匹配的块，并对之进行划分、分配和释放等操作。 :::

首次适应算法FF (first-fit)

首次适应算法（First-Fit）从链表头开始查找，选择第一个大小大于或等于所需内存大小的空闲块进行分配。由于该算法实现简单、容易理解，因此被广泛使用。
下面是一个例子，假设内存初始状态如下表：

进程 A、B、C 按顺序请求内存空间为 160、64 和 256。使用首次适应算法进行分配，步骤如下：

1. 进程 A 请求内存 160，算法找到第一个可用空间为 **256** 的内存块，分配前 160 字节并将其状态改为已占据，此时内存状态变为： | 内存地址 | 状态 | 大小 | | —- | —- | —- | | 0 | 已占据 | 128 | | 128 | 已占据 | 160 | | 288 | 可用 | 96 | | 384 | 已占据 | 64 | | 448 | 可用 | 512 | | 960 | 已占据 | 128 |

2. 进程 B 请求内存 64，算法找到第一个可用空间为 96 的内存块，分配前 64 字节并将其状态改为已占据，此时内存状态变为： | 内存地址 | 状态 | 大小 | | —- | —- | —- | | 0 | 已占据 | 128 | | 128 | 已占据 | 160 | | 288 | 已占据 | 64 | | 352 | 可用 | 32 | | 384 | 已占据 | 64 | | 448 | 可用 | 512 | | 960 | 已占据 | 128 |

3. 进程 C 请求内存 256，算法找到第一个可用空间为 512 的内存块，分配前 256 字节并将其状态改为已占据，此时内存状态变为： | 内存地址 | 状态 | 大小 | | —- | —- | —- | | 0 | 已占据 | 128 | | 128 | 已占据 | 160 | | 288 | 已占据 | 64 | | 352 | 可用 | 32 | | 384 | 已占据 | 64 | | 448 | 已占据 | 256 | | 704 | 可用 | 256 | | 960 | 已占据 | 128 |

用图表示另一个例子：

• 回收过程：若有相邻空闲区，则合并。否则，将释放区按首地址升序的规则插入到空闲区表适当的位置。
• 优点：保留高地址大空闲区，利于大作业。
• 缺点：容易产生碎片。低地址端过多小空闲区，增加查找开销

  循环首次适应算法NF

  该算法与首次适应算法相似，但是查找的位置从上一次分配的下一个地址开始查找，找到第一个适合的空闲区。
  还是上面的例子。

进程 A、B、C 按顺序请求内存空间为 12、10 和 3。使用循环首次适应算法进行分配，简要步骤如下：

• 首先A从头开始寻找，区块1合适，所以装入，此时区块1剩余8k空间，空闲地址的起始地址变为128+12 = 140
• 接下来B从140开始寻找，后续空闲地址为8，装不下，所以寻找到了区块2，占用10，区块2的空闲地址的起始地址变为212+10 = 222
• 最后C从222开始寻找，后续空闲地址为7，可以装入，占用区块2

• 优点：使存储空间更均衡，便于查找
• 缺点：缺乏大的空闲分区，不利于大作业。

  最佳适应算法BF

  该算法以容量递增的次序链接，从表(链)首开始顺序查找，直到找到第一个适合的空闲分区。若该空闲区大于作业，则划出适当空间分配出去，剩余空闲区仍留在空闲分区表(链)中。
  
  这里A从头开始找，两个区块都可以装入，但此时区块2更小，所以优先装入区块2中，后面两个区块装入同理。
  优点：找到的空闲区总既满足要求又是最小的。
  缺点：留下较小的无法利用的外碎片。

  最坏适应算法WF

  要求空闲分区按容量递减排列。从表(链)首开始顺序查找，若第一个表目都不能满足要求，分配失败；否则，划出适当分区给申请者，剩余空闲区插入空闲区表适当位置。
  
  这里A从头开始找，两个区块都可以装入，但此时区块1更大，所以优先装入区块1中，后面两个区块装入同理。
  优点：基本不留小分区
  缺点：较大的空闲分区不被保留。

4.4 对换(swapping)

对换的引入

对换的定义

:::info 操作系统每次只调入一个作业进入内存运行，此作业的时间的时间片用完时，又将该作业调至外存，再将后备队列中的一个作业调入内存运行一个时间片。 ::: 在多道程序环境下为了提高内存和CPU的利用率，增加系统吞吐量，系统中增设了对换，把内存中暂不能运行的进程调出到外存上，以腾出足够的内存空间，把已具备运行条件的进程换入内存。

对换的类型

1. 整体对换

处理机中的中级调度实际上就是存储器的对换功能，其目的是为了解决内存紧张问题，进一步提高内存利用率和系统吞吐量。中级调度是以进程为单位的对换。

1. 页面（分段）对换。

对换是以进程的一个“页面”或“分段”为单位进行的，则称之为“页面对换”或“分段对换”，又统称为“部分对换”。

为了实现进程对换，系统必须实现对对换空间的管理，进程换入和进程换出等三项功能。

对换空间管理的主要目标

在具有对换功能的OS中，通常把磁盘空间分为文件区和对换区两部分。

1. 对文件区管理的主要目标

文件区用于存放文件，对文件区管理目标是提高文件存储空间的利用率，为此系统采用离散分配方式

1. 对对换空间管理的主要目标

对换区用于存放从内存频繁换出的进程，它的管理目标是提高进程换入换出速度，为此系统采用连续分配方式。

进程的换出与换入

进程的换出

1. 选择被换出的进程。首先选择阻塞进程，存在多个时，优先选择优先级低的，同时还要考虑进程在内存中的贮存时间。如无阻塞，则选择优先级低的就绪进程换出。
2. 进程换出过程。只能换出非共享的程序和数据段。换出时，先申请对换空间，成功换出后修改进程控制块和内存分配表等数据结构。

   进程的换入

   对换进程定时执行换入操作，它首先查看PCB集合中所有进程的状态，从中找出“就绪”但已换出的进程。当同时存在多个这样的进程，则选择已换出到磁盘时间最久的进程
   换入过程：

• 申请内存，如果申请成功，直接调入；
• 如果失败，则先将内存中的某些进程换出，腾出足够的内存空间后，再将进程调入。

由于对换操作需要很多的时间，因此目前常见的方法是在进程经常发生缺页且显现出内存紧张的情况下，才启动对换程序。

4.5 💡 分页存储管理方式

:::info 分页存储管理是一种虚拟内存技术，它将一个进程的虚拟地址空间划分为大小相等的页面，每个页面都被单独映射到物理内存中。 ::: 其主要解决的问题是，进程过大，导致无法连续的装入内存中。
所以采取了分页存储这种离散型存储方式。

简单来说比如内存剩余空闲空间有64k和64k，如果测试需要装入一个128k的进程肯定装不下，但是把进程进行分页，每一页64k分别进行存储，就可以存储下来了。 当然如果进程是96k，还是以64k为一页，那么第2页就会只有32k是实际存储的，剩余32k还是被浪费了，这种叫做页内碎片。

分页存储管理的基本方法

基本原理

1. 将进程的逻辑地址空间划分成若干大小相等的页(或页面),各页加以编号，从0开始。
2. 内存空间也划分成与页大小相等的块（或物理块，存储块或页框）。
3. 在为进程分配存储空间时，总是以块为单位来分配

上述三个原理表明：进程分页的大小和内存空间分块大小相同。

分页存储的特点:将连续的逻辑地址空间的页面，通过页面地址转换机构，映射到不连续的内存块中，实现内存离散分配，节省空间。

页面和物理块

将进程的逻辑地址空间分成若干个页，并为各页加以编号。相应的，将内存物理地址分为若干个块，同时加以编号。 :::info 页面的大小又物理块的大小决定。 :::

• 若页面太大：以至和进程大小相差无几，则退化为分区分配，同时页内碎片也较大。
• 若页面太小：虽然可减少页内碎片，但会导致页表增长，换入/出效率低。

  因此页面大小应适中，与计算机的物理内存大小有关：通常为2的幂，一般在1KB到8KB。

地址结构

在分页结构下，进程中单元的地址结构如下：

其中：

• 页号：用于标记该存储单元（表项）位于进程的哪一页面
• 位移量：用于标记该存储单元（表项）位于此页面的哪一位

  可以理解为一本的书的页码和行号

如图所示，页号20位，说明最多可以存储220=1M个页面，位移量12位，说明最多可以存储212=4K个存储单元（表项）。
内存中物理地址也是相对应的结构：

由页表实现逻辑地址到物理地址的转换。

页表

页表用于地址映射，也就是显示进程中的页号对应内存中块号。
页表首地址一般用寄存器记录，其中包含页表在内存的始地址和长度。

起始地址可以理解为一本书的起始页面的地址 长度可以理解为一本书有多少页

例如，进程中一个存储单元的逻辑地址为：页号：3，偏移量：975，对应内存的块号就应该是8。
假设一页的大小为1K，内存的其实地址为2K，那么对应实际内存中的物理地址为**2K + 8 * 1K + 975**
也就是：
内存起始地址 + 块号 * 块大小 + 偏移量

如果没有说明内存起始地址，就默认为0。

地址变换机构

工作原理

地址变换机构工作为：逻辑页号—物理块号的映射，由页表完成。
页表驻留内存中，在系统中只设置一个页表寄存器PTR，其中存放页表在内存的始址和页表的长度。
工作流程如下：

1. 进程访问某个逻辑地址时，地址变换机构自动地把有效地址/相对地址分为两部分->页号与页内地址；
2. 页内地址（0~1023，页面大小为1KB）与块内地址/页框内地址（0~1023）一 一对应，无须转换。

这里需要注意的是必须做一个越界中断，也就是判断页号是否超出了页面的长度，如果超过了，说明这个逻辑地址不合法，需要做中断处理。

整体工作流程

1. 当进程访问某个逻辑地址中的数据时，分页地址变换机构根据PTR找到页表。
2. 分页地址变换机构自动把逻辑地址分化为页号和页内地址。并把页号与页表寄存器中页表的大小比较,确定访问的合法性。
3. 如果访问合法，则以页号为索引去检索页表。得到该页的物理块号，将之装入物理地址寄存器中。
4. 页内地址送入物理地址寄存器的块内地址字段中，完成从逻辑地址到物理地址的变换。

   例题

   有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。

由题意可知，页大小为2KB，所以页内偏移的位数就应该是11位，地址0AFEH，1ADDH都是十六进制，又四位，所以化为二进制为16位。
所以：

• 虚地址：0AFEH
• 转为二进制：0000 1010 1111 1110
• P＝1 W＝010 1111 1110
• 对应块号是9
• PA＝0100 1010 1111 1110
• 物理地址：4AFEH

  其中P表示页号，PA表示物理地址的二进制，W表示偏移量 对应实际物理地址：偏移量不变，页号根据页表映射修改。

具有快表的地址变换机构

由于页表放在主存中，故存取数据时CPU至少要访问两次主存。降低了内存访问速度。

• 访页表,得到绝对地址
• 访问内存内容

为了提高访问速度，增设一个具有并行查找能力的特殊高速缓冲寄存器，又称“联想寄存器”，或称“快表”。用它存放当前访问过的那些页表项。

相当于页表的一张缓存表

具有快表的地址变换过程如下：

1. 在CPU给出有效地址后，由地址变换机构自动地将页号送入快表中。
2. 若快表中有此页号，则直接从快表中读出该页对应的物理块号，送到物理地址寄存器。否则，再访问内存中的页表，从页表项中读出物理块号送到地址寄存器，同时，将此页表项放入快表中。
3. 若快表已满，OS找到一个被认为不再需要的表项，将它换出。

   由于成本问题，快表一般都不大常只能存放16~512个页表项。

访问内存的有效时间

访问的有效就和访问快表的命中率有关：
假设：

• t为访问一次内存的时间
• α为访问快表的命中率
• λ为访问一次快表的时间

那么如果没有快表，访问内存的时间的为：
EAT=t+t=2t

一次访问页表，一次访问真实物理地址。

如果有快表

访问命中快表的时间：λ + α（访问一次快表，成功，直接访问真实物理地址） 访问没命中快表的时间：λ + α + α（访问一次快表，失败，于是访问页表，再访问真实物理地址）

两级页表和多级页表

在两级页表（two-level page table）中，整个页表被划分为两个部分：一个页目录（page directory）和多个页表（page table）。
在多级页表（multi-level page table）中，整个页表被划分为多个部分：根页表（root page table）、一级页表（level-1 page table）、二级页表（level-2 page table）等

简单来说就是对页表建立一个页表，方便查找。 可以理解为索引的索引。

4.6 分段存储管理方式

分段存储的引入

基本概念

段式存储是指将逻辑地址空间划分为若干个不同长度的段，每个段可以包含一个完整的程序或者数据结构。通常，段的大小可以根据程序的要求来设定，从而更加有效地利用内存空间。

段的大小不固定，页的大小固定。

引入段式存储的主要目的是解决程序的动态加载和共享问题。
在传统的基于页式存储的方案中，所有页面的长度都是固定的且相等的，因此难以满足一些特殊需求。比如说，当程序需要动态加载某些代码段或者数据段时，即使只需要加载很小的一部分，也会浪费非常多的内存空间。而对于段式存储，由于每个段的长度可以不同，因此可以更加灵活地管理和分配内存空间。
另外，段式存储还可以实现程序的共享。不同进程中可能有一些公用的代码段或者数据段，如果采用基于页式存储的方案，则需要将这些页面复制一份到每个进程的虚拟地址空间中，占用大量的物理内存。而在段式存储中，可以通过将多个进程映射到同一个共享段上，实现这些段的共享使用，减少内存占用。

优点

1. 方便编程
2. 信息共享
3. 信息保护
4. 动态增长
5. 动态链接

   分段系统的基本原理

   分段系统的逻辑地址结构

   类似于分页系统：
   

   段表

   段表是内存管理中用于实现段式存储的一种数据结构，它记录了每个进程（或程序）所包含的所有段的信息。通常，每个进程都有一个独立的段表来记录其对应的所有段信息。
   具体地说，每个段表中存储了若干个段描述符（segment descriptor），每个描述符对应着一个段。段描述符通常包含以下信息：

• 段基址（Base Address）：表示段在物理内存中的起始地址。
• 段界限（Limit）：表示段的长度/大小。
• 段属性信息（Attribute Information）：包括可执行性、读写权限等信息。

  一般来说值包含前两个。

例如：

左边是一个完整的进程，被拆分成为了四个段，四个段的段长都不一样。段表中主要记录的就是三个信息：

• 段号：该段的编号
• 段长：该段的大小
• 基址：该段在内存空间中实际物理地址的起始地址

进程就可以通过查询段表来获得内存中的实际位置。

地址变换机构

同样类似于页表的地址变换结构：

主要功能就是验证偏移量是否越界，例如当偏移量是500，但是段的总大小为100，此时就会系统中断，越界大致两类：

• 段号越界
• 段内偏移量越界

  分页和分段的主要区别

1. 页是信息的物理单位，段是信息的逻辑单位
2. 页大小是系统固定的，而段大小则通常不固定。
3. 逻辑地址表示：
   1. 分页的程序地址空间是一维的，各个模块在链接时必须组织成同一个地址空间
   2. 分段的程序地址空间是二维的，各个模块在链接时可以每个段组织成一个地址空间。

      例子

      比如：

假设一个段为[0,430]，也就是说是0号段，且偏移量为430，对应真实的物理地址为：219 + 430 = 449。

信息共享

可重入代码

可重入代码：又称为“纯代码”(Pure Code),在实现共享时，需要用到可重入代码(Reentrant Code) 。它是一种允许多个进程同时访问的代码，是一种不允许任何进程对其进行修改的代码。

比如c语言里面写了一个函数，实际上函数本身不用改变，改变的就是传入的参数，所以实际上每个程序只需要改变传参即可，不需要改变函数本身。

设同时有40个用户并发执行并使用该EDITOR：

如果EDITOR部分不可重入，40个用户就需要40*（160+40）=8MB空间支持。
如果可重入，则可以剩下可重入的区域，只需要：40*40+160=1760KB空间支持。

分页系统

分段系统

图中ed的区域就是可重入的区域。 分段是信息的逻辑单位，因而实现共享比分页系统方便。

分段保护方法

• 地址越界保护：段号与段表长度的比较，段内位移与段长的比较,利用界限寄存器。
• 存取控制保护：设置存取权限，访问段时判断访问类型与存取权限是否相符

段页式存储管理方式

基本原理

段页式存储管理方式是对段式存储和分页式存储两种内存管理方式的结合，它可以充分发挥两种模式的优势，同时弥补其缺陷。
在段页式存储管理方式中，逻辑地址空间被划分为若干个段，每个段又由若干个页组成。其中，逻辑地址由两部分组成：段号和页号。
当进程访问一个逻辑地址时，首先将该地址分解为段号和页号。然后，通过段表找到对应的段描述符，在段描述符中记录了该段所对应的页表基址。通过页表中的页表项将页号映射为物理地址。
最终将段描述符中的段基址加上页表项中的页内偏移（Offset）即可得到最终的物理地址。
逻辑地址结构：

举个例子：
设作业包含分为三段，页面大小为2K

阴影部分为空闲区域。