以下内容涉及知识点较深，可能有误，望指出。参考时建议再次查证内容的准确性。

本篇是以OS的视角，研究分页和分段存储优先看这篇

冯诺依曼型计算机是由运算器、存储器、控制器、输入设备和输出设备五大部件组成，现存计算机都遵循该设计

存储器是一种用于存储程序和数据信息的部件，是一种时序电路

存储器的层次结构

在计算机执行指令时，基本上都会涉及到存储器的访问，故存储器的性能影响到计算机的运行效率。

但如今随着计算机技术的发展，对存储器的容量需求也越来越大，通常一种存储器无法同时满足快速与大容量甚至低廉的成本，故现在计算机均采用多层次的存储器设计。

对于通用计算机，通常将存储器分为三个层次，与中央处理器(CPU)的距离由近到远分为：

• 寄存器

  寄存器常封装在CPU内部，用于暂时存放指令、数据、运算结果，以便CPU能够更快速地访问和操作这些数据。

  由于与核心相连，寄存器具必须有与CPU相同的执行速度，故寄存器的生产成本高。

  为使CPU在执行指令时能够直接、高效的操作寄存器里的数据，通常寄存器的长度与CPU的位数一致，例如：在32位CPU中，寄存器的长度是32位，能够存储一个32位的数值。

• 主存储器

  主存储器也被称为内存，也有人叫它可执行存储器，可由CPU直接随机存取。

  主存储器在速度上逊色于寄存器，当主存储器的容量要比寄存器大得多

  主存储器可用于缓存辅助存储器的数据，现代计算机设计，为了提高性能的同时兼顾价格，常常采用多级的主存储器设计。

  • 高速缓冲存储器

    也被称为高数缓存，被封装在CPU内部。

    与寄存器不同，高速缓存被设计为CPU与其他主存之间，由静态存储芯片(SRAM)，其速度接近于与CPU的速度，容量小于其他主存但比寄存器要大得多，用于缓存其他主存的数据以加速CPU对主存的存取速度，可以显著减少CPU访问主存的延迟。

    

    在现代CPU设计中，高速缓存也被设计成多级结构，通常分为三个级别，等级越高(数字越小)，速度越快、容量越小。

    • L1缓存时计算机中最快的主存储器，当然一般也最小，普遍以KB为单位，部分高端CPU可达1M(例如AMD 7950X)甚至更高，L1缓存常被分割为指令缓存与数据缓存，通常用于存储CPU正在操作的内容。

    • L2缓存要比L1大不少，通常在256KB-16MB左右(2023年)，L2缓存通常存放着CPU下一步可能要执行的内容，通常与L1缓存一样，L2缓存也被封装在CPU核心内部，但不像L1缓存直接与核心相连。

    • L3缓存，在现在计算机设计中，L3缓存是CPU中最大的主存，通常被封在CPU中单独区域，由多个核心甚至是核显共享。

    

    图片来源见水印

    CPU会优先在L1缓存中寻找，然后是L2、L3以及其他主存，若CPU在L1中找到指令或数据，则称之为缓存命中，缓存的命中率是高速缓存的一项重要性能指标

  • 主存储器

    这里的主存储器应该要理解为现在计算机中的内存条，在辅助存储器与高速缓存之间

  • 磁盘缓存

    由于当今磁盘的IO速度要明显低于主存储器，故在现代计算机设计中使用磁盘存储器暂存磁盘中频繁使用的数据，降低磁盘IO负载。

    磁盘缓存可能是系统内存或由分装在磁盘PCB上独立的存储器如SRAM（静态随机存取存储器）负责

    由于操作系统对磁盘的写入操作可能未能及时从磁盘缓存存储到磁盘中，故在磁盘意外断电时可能会导致应存入磁盘的数据发生丢失。

高速缓存与磁盘缓存，属于主存储器，而不是寄存器和辅助存储器

• 辅助存储器

  辅助存储器又被称为外存储器，此类储存器一般采用非易失的存储介质制成，通常断电后能保留数据，如磁盘、固态硬盘、光盘等。

  辅助存储器不可由CPU直接寻址，通常在使用时由操作系统(OS)读取并缓存在主存储器中，这也是主存储器被称为可执行存储器的原因。

不同层次的存储器会由OS进行统一管理

存储技术

这里简单介绍些常见的，可快速带过

随机访问存储器

也被称为随机存取存储器(RAM)，被分为两类:SRAM(Static Random Access Memory,静态随机存储器)与DRAM(Dynamic Random Access Memory,动态随机存储器)，SRAM更快，成本也相对更高。

RAM工作时(刷新时除外)可以随时从任何一个指定的地址写入（存入）或读出（取出）信息

RAM的读写速度很快，但存储其中的数据是易失的，这就意味着一旦断电存储的说有数据将丢失，故常被用作临时的存储介质

SRAM

SRAM通常采用6管MOS制成，这种电路结构天生在通电时具有双稳态性（也就是图中，要么1，要么3，在其他状态都是不稳定的，会很快的恢复到一个稳定状态下）

正是由于双稳态性，SRAM无需刷新即可保持在稳定值，即使受到干扰，在干扰消除时也可很快恢复，这些特点使其特别适用于需要高速访问和可靠存储数据的场景，如CPU与主存之间的高速缓存、CPU内部的L1/L2等

但由于SRAM集成密度小、芯片面积大、成本高，现如今DRAM仍是主流

DRAM

DRAM采用电容对数据位进行存储，正是由于采用电容来存储bit数据，由于存储在电容器上的电荷会随着时间的推移而泄漏，因此DRAM需要定期刷新以确保数据的完整性

DRAM存储器对干扰非常敏感，若电容的电压被扰乱就永远无法恢复

DRAM相较于SRAM拥有更高的密度，这也意味着成本更低，但速度要比SRAM慢

非易失性存储器

非易失性存储器:即即使在断电后，仍能保持器数据的存储器

ROM

只读存储器(Read-Only Memory，ROM)，原本是指一种以非破坏性读出方式工作，只能读出无法写入信息的存储器，但随着技术的发展，现如今部分ROM可以实现读写

在计算机主板PCB上封装着一块ROM，用于存放固件(firmware)，这块存储器也属于内存的一种，也可由CPU直接寻址，同样例如显卡、磁盘驱动器等复杂的设备，也需要由固件翻译来自CPU和I/O设备的请求

PROM

可编程只读存储器（Programmable ROM，PROM）允许用户通过专用的设备（编程器）一次性写入自己所需要的信息，这类存储器只可被编程一次，被编写的数据会被永久性保存。

PROM的每个单元时一种融丝，在出厂时，PROM中的数据全为1/0，由用户使用时，再通过编程使PROM存储需要的数据，此时熔丝熔断，数据被写入，这也是只能被编程一次的原因

EPROM

可编程可擦除只读存储器（Erasable Programmable Read Only Memory，EPROM）可多次编程，是一种以读为主的可写可读的存储器，在写入新数据时，需要把原先的内容先擦除才能写入。

EPROM会留有一个透明的石英窗口，当紫外线透过窗口照射在EPROM单元上，该单元会被重置为0。故EPROM需要使用专用设备才能进行擦写。

RPROM采用MOS管，速度较慢

EEPROM

电可擦可编程序只读存储器（Electrically Erasable Programmable Read-Only Memory，EEPROM）是一种可以随时写入而无需先擦除原先内容的存储器，在写入时，也无需使用专用设备。

EEPROM的写入往往要比读取的速度慢

Flash

快擦除读写存储器( Flash Memory)是一种高密度、非易失性的读/写半导体存储器。

其擦写速度要比EERPOM快得多，目前，闪存已广泛用于制作各种移动存储器，如U盘及数码相机/摄像机所用的存储卡等。

程序的装入与链接

要在系统中运行用户程序，就必须将其由外存装入到内存中，并将其转化为一个可执行的程序，

在此过程中，会经历以下三步:

地址绑定

以CPU的视角，生成的地址通常为逻辑地址(Logic Address)，也叫相对地址

以内存单元的视角，能看到的地址为物理地址(Physical Address)，也叫绝对地址

在编译和装入的过程中，地址绑定会产生相同的逻辑地址和物理地址

在执行时，地址绑定会生成不同的逻辑地址和物理地址，此时成逻辑地址为虚拟地址(Virtual Address)

由程序所生成的所有逻辑地址集合被称为逻辑地址空间(Virtual Address Space)

由这些逻辑地址所对于的物理地址的集合被称为物理地址空间(Physical Address Space)

内存保护

内存保护是操作系统对电脑上的内存进行访问权限管理的一个机制。其主要目的是防止某个进程去访问不是操作系统配置给它的寻址空间，从而防止该进程因某些程序错误或问题而有意或无意地影响到其他进程或是操作系统本身的运行状态和数据，保证进程之间不会相互影响。

这种保证通常时基于硬件实现的，因为一旦OS进行干预就会严重影响性能

编译

一种由编译器(一种程序)将用户程序进行处理，并转换为若干模块的过程，这一过程就是编译

链接

由链接程序将编译后产生的一组目标模块以及所需的库函数链接到一起，形成一个完整的装入模块的过程

根据进行装配的时机不同，分为一下三种

静态链接

在程序运行前，先将各目标模块以及其所需函数库链接成一个完整的装配模块，以后不再拆开,

静态链接有以下特点:

• 代码装载速度快、执行速度略快与动态转载

• 只需保证开发者电脑上有正确的函数依赖库文件，再以二进制形式发布程序时无需考虑用户电脑上库文件是否存在或版本问题

• 生成的可执行文件大、可执行文件包含公共代码

• 每次需要更新其中的目标模块时，则需要重新打开装入模块，影响效率。

在模块装配时，需解决以下问题:

设有三个模块A、B、C，长度分别为L、M、N，A模块调用B模块；B模块调用C模块

这部分内容与书本有出入，待核实！！

• 修改相对地址

  由于上一步编译所产生的目标模块(A、B、C)中所采用的都是相对地址，每个目标模块之间的起始地址都是0，而将其装转载为一个模块时，除原模块A外，被调用的B、C模块在装入模块中的起始位置将不再为0.

  B模块的起始位置为L(0 + A模块长度)

  C模块的起始位置为L+M(B模块的起始位置 + B模块的长度)

  也就是在装入模块中，各目标按顺序相连

• 变换外部调用信号

  由于模块的起始位置发生变化，则要将所用的外部调用符号改为装入模块中的相对位置

  CALL B 指向的就是L

  CALL C 指向的就是 L + M

动态链接

动态链接则是不一口气将模块装入，而是按需装入

具有以下特点:

• 生成的可执行文件较静态链接生成的可执行文件小；

• 适用于大规模的软件开发，使开发过程独立、耦合度小，便于不同开发者和开发组织之间进行开发和测试；

• 不同编程语言编写的程序只要按照函数调用约定就可以调用同一个DLL函数；

• DLL文件与EXE文件独立，只要输出接口不变（即名称、参数、返回值类型和调用约定不变），更换DLL文件不会对EXE文件造成任何影响，因而极大地提高了可维护性和可扩展性；

• 使用动态链接库的应用程序不是自完备的，它依赖的DLL模块也要存在，如果使用载入时动态链接，程序启动时发现DLL不存在，系统将终止程序并给出错误信息；

• 速度比静态链接慢；

装入时动态链接

将用户源程序编译后得到的一组目标模块，在装入内存时，采用边装入边链接的方式。

当发生一个外部调用事件，则让装入程序去找到被调用的外部目标模块，并装入。

运行时动态链接

对某些目标模块的链接，是在程序执行中需要该模块时才进行的。其优点是便于修改和更新，便于实现对目标模块的共享。

装入

也被称为加载：由装入程序 将装入模块 装入内存的过程

绝对装入方式

当计算机系统很小，且仅能运行单道程序时(即:所有进程一个一个排对执行。若A阻塞，B只能等待的一种程序设计)，此时用户程序在编译后产生的目标模块会带有一个目标代码，代码中包含模块所要装载的位置，这个位置是个内存中的绝对地址。也可以理解为，此时编译产生的目标模块内，逻辑地址=物理地址，程序中的所有内存引用都是基于这个绝对地址。

绝对装入方式仅适用于单道程序环境，因为在多道程序环境中，编译器无法预知编译后的程序该放在内存中的何处

可重定向装入方式

装入时对目标程序中指令和数据的修改过程称为重定位，因此可以将模块装载在内存的''任何位置''，地址变换通常实在装入时一次完成的，所以又称静态重定位

由于是一次性完成，故在装入内存时，需为装入模块分配全部的内存空间，这段空间应该是连续的。

若此时系统内存剩余容量不足以装载模块时，模块将不会被装载

若容量足够，但无连续空间装载模块时，OS可能会尝试移动其他模块，以空出合适的空间装载模块。

本方式在装载模块后不允许程序运行时在内存中移动位置，此时对模块的移动会影响模块中数据地址发生错误。

动态运行时装入方式

装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转化为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此装入内存后的所有地址均为逻辑地址，这种方式需要一个重定位寄存器的支持。

故这种装入方式，允许程序在内存中发生移动，且在程序运行前只装载部分代码，后续再陆续按需动态分配内存，故这种装入方式可将程序分配在不连续的内存中。

存储分配方式

为使用户程序装入内存，则必须为其分配一定大小的存储空间

连续分配存储方式(分区)

简称连续分配方式，被广泛用于20世纪60-80年代的OS

这种分配方式为用户程序只分配一段连续的内存空间，用户程序中的代码或数据被放置在连续的内存空间中

单一连续分配

在早期单道批处理系统的小型机中，内存常被分为系统内存区和用户内存区，系统内存区被分配至低位，而高位的其他空间，也就是用户内存区中仅有一道用户程序，故整个用户内存区有一个用户程序独占，而这种存储分配方式称为单一内存分配。

正因如此，早期部分的单用户单任务的OS，并未采取存储器保护机制，这是因为单用户环境不存在用户之间互相干扰的问题，并且若OS部分内存遭受破坏，课程通过重启重新载入，相对影响较小，而不采取保护机制，可以节约硬件资源

固定连续分配

20世纪60年代出现了多道程序系统，为使得内存可以装入多道程序，且这些程序之间不会互相干扰，于是将用户用户内存区的空间划分为多个大小固定的区域，这些区域也被称为分区，每个分区只装入一个作业。这也是最早的、最简单的一种可以运行多道程序的分区式存储方式。

此时加入用户空间中有4个分区，那么现在便能允许4个程序并发运行并且互不干扰。当一个作业结束时，分区将空出，并从外存中后备作业列队中选择一个合适大小的作业装入。

虽然这种分配方式实现简单，但可能会出现当用户程序过于大，可能所有分区都无法满足需求，此时还需使用覆盖技术解决，影响性能

且分区技术虽不会产生外部碎片，但会产生内部碎片。

分区的划分

分区的大小可以时相等或是不相等的

• 分区大小相等

  将用户空间内的分区划分为多个等大的分区

  这种分区方式适合一台计算机同时控制多个相同对象的场合

  但这种方法缺少灵活性，当程序太小时，会造成空间的浪费，若程序太大，一个分区将装不下该程序

• 分区大小不等

  将存储器划分为多个大小不等的分区，分区大小视系统中作业大小决定

  通常OS会创建较多的小分区，适量的中分区以及少量的大分区

内存的分配

为方便内存分配，OS常将分区按照其大小进行排队，并建立一张分区表。

表通常使用数组或链表实现，记录有分区大小、起始地址、是否已被分配状态等信息。

动态分区分配

动态分区分配属于可变分区分配，它是不会事先划分内存分区，而是根据实际需求动态的对为用户程序分配合适的内存空间。

使用数据结构记录使用情况

为实现动态分区分配，OS必须配置相应的数据结构，以描述分区的分配情况，进而为分区的分配提供依据。

以这张内存分配情况示意图举例，常用的数据结构有以下两种：

• 空闲分区表

  OS将建立一张表，于之前的分区表类似，只不过用于记录空闲分区，表中每个条目表示一个空闲分区，条目包含分区号、分区大小、起始位置等数据，如下图所示。

  

• 空闲分区链

  为实现空闲分区的分配和链接，在每个分区的头部设置一些用于表示分配信息的控制位以及一个向前的指针，并在每个分区尾部设置一个向后的指针。

  这就使得空闲分区形成一个双向的连表，如下：

  

动态分区分配算法

若多个分区都满足需求，那作业应该装入到那个分区，这就有相应的动态分区分配算法决定。

由于分配算法往往对系统性能会产生较大影响，故人们发明了很多中算法，如下:

基于顺序搜索

• 首次适应(First Fit,FF)算法

  该算法由地址地位向上顺序查找，直到一个大小合适的分区为止。

  若遍历整个链后任无法找到一个合适的分区，则表明目前系统只能没有合适大小的空闲分区，也就意味着内存分配失败。

  该算法的特点是，在分配内存时，会更加倾向使用低位空间，而高位往往保留着大量空闲的空间，方便以后到达的大作业的使用，但由于频繁划分地位空间，会导致地位保留许多难以利用的小空闲分区，也就是碎片，这些碎片也会增大查找空闲分区的开销，如下：

  

• 循环首次适应(Next Fit,NF)算法

  循环首次适应算法于首先适应算法类似，只不过在查找空闲分区时，并不每次从链首开始查找，而是基于上次查找到的空闲分区的位置向上进行查找

  这么做时可以有效避免过度倾向使用地位的空间，可以使空闲分区分布更加均匀，缓解一个地方堆积大量无法利用的碎片，但这么做会使得空间中连续的大块分区变少。

  应该看得懂，就不配图了

• 最佳适应(Best Fit,BF)算法

  最佳：指的是将最小可用的空闲分区分配给作业

  最佳适应算法将所有可用空闲分区由小到大排序，形成空闲分区链。当需要装入作业时，由小至大遍历分区链，直到找到一个可以容纳作业的最小空闲分区，将作业装入该分区，由于倾向于使用小分区，则会更有可能保留大分区以应对大作业。如下：

  

  孤立的看，这种算法貌似是最好的，因为看上去每次浪费的空间是最小的，但长远来看，由于每次装入后产生的空闲分区也最小，着也导致后续会产生大量无法利用的碎片

• 最坏使用(Worst Fit,WF)算法

  最坏：也就是和最好唱反调

  最佳适应算法将所有可用空闲分区由大到小排序，形成空闲分区链。当需要装入作业时，由大至小遍历分区链。

  由于更加倾向于使用大分区，故这种算法必然会导致存储器中缺乏大空闲分区，也就意味着当有大作业时，很有可能会因为没有合适的分区而导致内存分配失败。

  但换个角度看，最坏使用算法每次被切割后产生的空闲分区并不小，被利用的概率要比最佳使用算法要好，故对小作业场景更有好，所以最坏也未必坏

  应该看得懂，就不配图了

基于索引搜索

• 快速适应算法

  OS先依据常用的分区大小(大小由OS决定)，先将用户空间划分为若种不同大小的分区，分区不再被二次分割，再将相同大小的分区建立单独的空闲分区链表，然后再交友一张索引表管理。

  当有作业需要装入时，系统会在索引表中找到最小可容纳的分区大小，然后去对应链表中拿一个分区用于装入作业。

  可以看出，快速适应算法比较复杂，对于装入过程，查找效率高，且倾向于使用更小的空闲分区，但在分区回收时，由于算法复杂，对系统开销也大。

  而且由于分区不再被二次分割，虽然不会产生外碎片，但会产生内碎片

  e，要是小分区都用完了，这时还有很多小作业怎么办

  还能怎么办，这时只能土豪一点，拿大分区装小作业，这也是一种典型的拿空间换时间的做法

• 伙伴系统

  伙伴系统相对而言就没那么死板

  伙伴系统规定，无论分区是否被分配，所有分区都必须是2ᵏ(k为整数，n ≤ k ≤ m)，2ⁿ为分配的最小分区大小，2ᵐ为可分配的最大分区大小，通常2ᵐ为整个可分配内存

  系统启动初期，只有一个空闲分区，也就是整个内存

  随着系统的运行，由于不断划分，会产生若干个不同大小的分区

  对于相同的大小的所有空闲分区，会为其单独设立一个空闲分区链表，

  若装载一个大小为k的作业，首先计算出一个值i，使得2ⁱ⁻¹ < k ≤ 2ⁱ

  然后尝试去大小为2ⁱ的空闲分区链表中找到一个空闲分区，若能，则将该分区分配给该作业独享

  若此时无可满足大小的分区，则尝试向2ⁱ⁺¹大小的空闲分区链表查找是否有空闲分区，若有，借用一个2ⁱ⁺¹大小的空闲分区，将其拆分为两个2ⁱ大小的空闲分区，并将其中一个分配给作业独享，剩余一个加入2ⁱ大小的空闲分区链表中备用

  如此循环，直到遍历到最大的分区链表，若还找不到，则分配失败

  被拆分的分区被称为'一对伙伴'，在回收分区时也将被合并

  伙伴系统依旧存在内碎片，但要比快速适应算法好得多。

讲人话就是，作业来了，会尝试将内存不停的对半分，直到得到一个最小的能装的下专业的内存空间

由于是对半分，这两半就是一对伙伴

当两个伙伴都空闲时，就会合并回去

• 哈希算法

  哈希(Hash)：一种散列函数，可以将任意长度的输入通过散列算法变换成固定长度的输出，该输出就是散列值。同一输入得到的哈希值是唯一的，哈希值很难被逆向。

  哈希表作为一种高效的数据存储结构，可以使数据的存储位置与关键码之间建立一一映射的关系，从而加快元素的搜索速度，这里不细究原理。

  基于哈希快速查找的优点，将空闲空间大小作为关键字，并将这些关键字经过计算得到哈希值，并再将这些哈希值存储到一个链表中，这就得到了一个哈希表。

  在需要分配空间时，将按照需要分配的空间大小，提供哈希计算出相应空闲分区链表在哈希表中的位置，并取出一个空闲分区分配。

  利用哈希主要还是利用其特性加速查找。

可变分区的分配与回收

可变分区的分配

设请求的分区大小为u.size，空闲分区表中每个空闲分区大小为m.size，事先规定的最小不可切分大小为size

• 当当前空闲分区小于请求分区大小时，也就是u.size > m.size，将继续向下一表项遍历

• 若当前空闲分区在分配后剩余的空间小于等于不可分割的大小，也就是m.size - u.size ≤ size，则将这个空闲分区不切割进行分配

• 若剩余大小大于不可分割的大小，则分配u.size大小的分区

可变分区的回收

系统在回收分区时，会从当前链表中找到相应的插入点用于插入空闲分区信息，此时就存在以下3种情况

• 回收区时插入点与一个分区相邻时，合并这两个分区

  

• 回收区时插入点与前后各一个分区相邻时，合并这三个分区

  

• 回收区时插入点与前后两个分区都不相连时，此时单独新建一个表项，并将其按照回收区的起始位置插入到表中合适位置

动态重定向分配

在连续分配存储方式中，随着计算机的运行，计算机内存中将产生很多小而零散的分区，这些小分区难以被利用，这些分区也就是外碎片

怎么解决

紧凑是将内存中的作业进行移动，将它们移动到一起，以腾出一块大的空闲空间的方法

紧凑有时也被称作:紧缩、拼接

由于紧凑操作对内存中的程序和数据进行移动，这就导致位置发生改变，此时就需要对移动后的程序和数据进行重定位

OS会在一段时间对内存进行一次紧缩和重定位操作，以确保系统的内存利用率，但这些操作比较复杂，其实对系统性能影响很大，过于频繁的操作可能会严重影响系统的性能

分页存储方式

连续分配方式在计算机的运行过程中会产生很多碎片，虽然可以提供紧凑解决，但对系统性能开销较大，如果允许单个作业零散的被分配到不相邻的区域中，就能更加有效的利用内存空间

分页存储方式中，将用户程序地址空间划分为若干各大小固定的区域，这些区域就是页也叫页面

每个页都有对于的编号，也就是页号，从0开始编号

每个页在物理内存中就是一段段连续的空间块，这些空间被叫做页框，同样页框也会从0开始编号，也就是页框号，页框号和页号是两个东西 $$ 页框号 = INT[逻辑地址 / 单个页框长度] $$ 页框的在物理地址中的起始位置就是页基址，在页框大小相同时 $$ 页基址 = 页框号 * 页框大小 $$ 程序/数据在页框中的位置，基于页基址的偏移量叫页内偏移量，也叫页内地址 $$ 物理地址 = 页基址 + 页内偏移量 $$ 更多细节可以参考这个

页面大小与内碎片

页面的大小不是越大/越小就越好

由于一个作业常常占不满分配给该作业的最后一个页，这就势必会产生内碎片

通过设置更小的页可以提高内存的利用率，但更小的页也将会使一个作业分配到更多的页，这会使该进程的页表过长，不仅占用内存，也会降低页面换入/换出的效率

分页地址结构

以下只考虑纯分页管理的情况，不涉及段页式混合管理，且只考虑X86架构

分页地址由 低位的12位页内偏移量 和处于 高位的20位的页号组成

页表

在分页系统中，各进程的各页可能零散的存放于物理内存空间中，位确保进程能够顺利运行，系统将为每个进程新建页面映射表，简称页表

页表由操作系统进行维护，一般程序无权访问与修改，操作系统会定期维护页表

在进程地址空间中的所有页，都依次在页表中由一个页表项，页表中存放着页基址等信息，实现页号到物理地址(页框)之间的映射

分页地址的变址

为使用户地址空间的逻辑地址转换为内存空间的物理地址，系统中必须设置地址的变换机构

基于地址的变址机构

变址操作的频率非常高，故变址机构会利用硬件进行实现

例如页表就是利用一组专门的寄存器实现

由于寄存器制造成本高，故大多数页表存储在内存中

在索引时，先将页号与页表长度进行比较，若大于页表长度，也就是越界，此时就会产生一个越界中断

若未越界，页号将在页表中得到页基址，将页基址对应的物理块号存放于物理地址寄存器中

再加上逻辑地址中的页内偏移量就得到数据的物理地址

具有快表的地址变换机构

由于页表被存放于内存中，这就意味着当CPU每次存取数据时，就需要访问内存两次，着就降低了系统的运行效率

为提高变址效率，再变址机构中设立一个具有并行查能力的高速缓冲寄存器，也就是联想寄存器,也就是快表(TLB， translation lookaside buffer)

TLB页表不受操作系统维护，而是交由MMU硬件。MMU会不间断更改TLB页表的内容，例如在TLB miss(TLB 未命中)时，MMU会将未命中的页表项插入TLB页表。

在进行变址时，会优先去TBL中查找，若未命中，才去内存中找页表查找

引入快表后的内存有效访问时间

从进程法术指定逻辑地址的访问请求，经过变址。再到内存中找到对应的物理地址，这一流程所花费的时间被称为有效访问时间(Effective access time, EAT)

计算公式如下: $$ EAT = a λ +(t + λ)(1 - a) + t \\ = 2t + λ - t a $$ λ表示查找快表所需要的时间 | a表示命中率 | t表示访问一次内存所需要的时间

多级页表

以下只考虑纯分页管理的情况，不涉及段页式混合管理，且只考虑X86架构

页表存储虽然可以使一个作业分配在若干个零散的内存空间中，但页表必须连续存放，当一个页表很大时，就需要占用一段很大的连续空间。且链表必须常驻内存，大量表也会造成内存浪费

我们可以将链表进行分组，使一个内存块正好放下一个页表(这里以一个内存块4KB为例)

对离散的页表专门分配一张页表，这张页表就是外页表，也叫页目录/顶层页表

为方便实现地址转换，在变址机构中，需要增设一个外层页表寄存器，用于存放外城页表的起始位置

外页表中的每个页表向记录着各页表的物理块号，如下

当页面大小为4KB(12位)时，若采用一级页表结构则应具有20位(32-12)的页号，即此时页表项有1M个

当采用两级页表结构时，假设每个页表项占用4B，则每个页可包含2^10个页表项，最多有2^10个分页。

在64位环境下

对于32位计算机，采用二级页表结构很合适

但对于64位计算机就不一定，例如此时页面大小仍是4KB，即2^12B，每个页占用4B，地址还剩下52位(64-12)，假定物理块大小还是4KB，则还剩下42位(64-12-10)用于外层页号，也就是外层页表凯南有4096G个页表项，将占用4096GB的空间，很显然是不可接受的

此时必须将现在的外层页表在分成两层，也就是三层页表的结构

分段存储方式

分页存储主要是为了提高内存利用率，而分段存储主要目的则是为了更好地满足用户的逻辑需求，如数据共享、数据保护和动态链接等。因此，当今许多高级语言支持也使用分段存储方式。

分页存储是以进程为单位分配连续的空间，而分段存储将以分段为单位分配连续空间，而一个进程可能由多个分段组成

分段管理的诞生，最早是为了扩充8086处理器的寻址空间另一篇文字细说

分段

在分段管理方式中，作业地址空间被分为若干段，并用段号表示不同段

每个段都从0开始编址，并采用一段连续的地址空间，且各个段之间彼此独立

每个段都具有自己的段基址(段在物理地址中的起始位置)以及长度。

每个段可以定义一组相对完整的逻辑信息，如主程序段、子程序段、数据段等

段的长度不固定，而是由程序自身逻辑关系进行划分，一个进程可划分为多个段

分段地址由地位的段内地址以及高位的段号组成

段表

由于分段存储是将一个作业空间按照程序自身逻辑关系，划分为若干大小不等的段，这些段可以零散的存储在内存用户区或是分页中（段页结合管理方式)

由于段的位置不好确定，OS会维护一张段号和段基址之间对应关系的映射表，也就是段表。

段表中的每个项表示一个段，记录了段号、段基址、段长度等信息

段表可放置于寄存器中，以提高运行效率

分段地址的变址

系统中通常会设置段表寄存器，段表寄存器中存储了段表的起始位置以及段表的长度(TL)

当分段地址需要变址时，会先将段号与段表起始位置进行累加，再与段表长度TL进行比较

若大于段表长度，也就越界了，此时将发出中断信号

若小于，则会尝试在段表中查找段表项，得到段基址于段长

此时利用累加器对段基址于段内偏移量进行相加

此时若大于段长，也是越界、发出中断

若小于则可得到段起始位置的物理地址，编制结束

可以看出，和分页存储利用页表进行变址一样，访问一次数据，就需要读取两次内存

所以，分段存储也会使用“快表”对段表进行存储，和分页类似，就不多赘述了

一维和二维的问题

主要是怎么理解分页是一维的，而分段是二维的这一说法。

发现在网上有争论，我这里结合书中的讲解，赞成‘wfs’的说法

分页完全是系统行为，分页大小可预见，程序员只需利用一个页号就可以表示一个地址，这是一维

而分段是用户行为，分段大小由程序逻辑决定，故大小不好遇见，所以程序员既要给出段号，还要给出段内地址，这是二维

参考资料：

《计算机操作系统(慕课版)》 - 中国通信出版集团 人民邮电出版社

《深入理解计算机系统》 - 机械工业出版社

存储器_百度百科 (baidu.com)

寄存器_百度百科 (baidu.com)

主存储器_百度百科 (baidu.com)

外存储器_百度百科 (baidu.com)

随机存取存储器_百度百科 (baidu.com)

SRAM存储器_百度百科 (baidu.com)

动态随机存取存储器_百度百科 (baidu.com)

只读存储器_百度百科 (baidu.com)

操作系统-程序的装入和链接_怎么区分链接和装入-CSDN博客

单一连续分区分配方式_百度百科 (baidu.com)

连续分配管理方式（单一连续分配 固定分区分配 动态分区分配）-CSDN博客

动态分区分配算法（1、首次适应算法 2、最佳适应算法 3、最坏适应算法 4、邻近适应算法）-CSDN博客

Hash（散列函数）_百度百科 (baidu.com)

分页和分段有什区别？ - 掘金 (juejin.cn)

一些有关AI生成的内容