存储器管理【计算机操作系统】
- 前言
- 推荐
- 第四章 存储器管理
- 4.1 存储器的层次结构
- 4.1.1 多层结构的存储器系统
- 4.1.2主存储器与寄存器
- 4.1.3 高速缓存和磁盘缓存
- 4.2 程序的装入和链接
- 4.2.1 程序的装入
- 4.2.2 程序的链接
- 4.3 连续分配存储管理方式
- 4.3.1 单一连续分配
- 4.3.2 固定分区分配
- 4.3.3 动态分区分配
- 4.3.4 基于顺序搜索的动态分区分配算法
- 4.3.5 基于索引搜索的动态分区分配算法
- 4.3.6 动态可重定位分区分配
- 4.4 对换
- 4.4.1 多道程序环境下的对换技术
- 4.4.2 对换空间的管理
- 4.4.3 进程的换出与换入
- 4.5 分页存储管理方式
- 4.5.1 分页存储管理的基本方法
- 4.5.2 地址变换机构
- 4.5.3 访问内存的有效时间
- 4.5.4 两级和多级页表
- 4.5.5 反置页表
- 4.6 分段存储管理方式
- 4.6.1 分段存储管理方式的引入
- 4.6.2 分段系统的基本原理
- 4.6.3 信息共享
- 4.6.4 段页式存储管理方式
- 最后
前言
以下内容源自计算机操作系统（第四版）
关于操作系统，
CSDN有很多的优秀博客。
在这里，
本文摘取其他博客内容，
并附上相关链接，
如有侵权，
联系删除，
仅供学习交流使用
第四章 存储器管理
4.1 存储器的层次结构
4.1.1 多层结构的存储器系统
1.存储器的多层结构。
存储层次至少应具有三级：最高层为 CPU 寄存器，中间为主存，最底层是辅存。还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等 6 层。在存储层次中越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。
寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。固定磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。
2.可执行存储器。
寄存器和主存储器又被称为可执行存储器。
4.1.2主存储器与寄存器
1.主存储器
主存储器简称内存或主存。由于主存储器的访问速度远低于 CPU 执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。
2.寄存器
寄存器具有与处理机相同的速度。主要用于存放处理机运行时的数据。如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。
4.1.3 高速缓存和磁盘缓存
1.高速缓存
高速缓存是介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据。其容量远大于寄存器，而比内存约小两到三个数量级左右。
根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中。当 CPU 访问一组特定信息时，首先检查它是否在高速缓存中，在则直接取出使用，否则再从主存中读取。
2.磁盘缓存
由于目前磁盘的 I/O 速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。但磁盘缓存与高速缓存不同，它本身并不是一种实际存在的存储介质，而是利用主存中的部分存储空间暂存从磁盘中读出(或写入)的信息。
4.2 程序的装入和链接
用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过以下几个步骤：
1）编译，由编译程序将用户源代码编译成若干个目标模块。
2）链接，由链接程序将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块。
3）装入，由装入程序将装入模块装入内存。
4.2.1 程序的装入
1.绝对装入方式
仅能运行单道程序时可以采用该种方式。装入模块被装入内存后，程序中的逻辑地址与实际内存地址完全相同。
2.可重定位装入方式
采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。值得注意的是，在采用可重定位装入程序将装入模块装入内存后，会使装入模块中的所有逻辑地址与实际装入内存的物理地址不同。通常是把在装入时对目标程序中指令和数据地址的修改过程称为重定位。又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。
3.动态运行时装入方式
动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一个重定位寄存器的支持。
4.2.2 程序的链接
1.静态链接方式
在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：
1）对相对地址进行修改。这是因为在由编译程序所产生的所有目标模块中，使用的都是相对地址，其起始地址都为 0，每个模块中的地址都是相对于起始地址计算的。
2）变换外部调用符号。将每个模块中所用的外部调用符号也都变换为相对地址。
这种先进行链接所形成的一个完整的装入模块，又称为可执行文件。
2.装入时动态链接
指用户源程序经编译后所得的目标模块，在装入内存时采用边装入边链接的链接方式。这样便于装入前修改和更新，以及实现对目标模块的共享。
3.运行时动态链接
将对某些模块的链接推迟到程序执行时才进行链接，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由 OS 去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。
4.3 连续分配存储管理方式
为了能将用户程序装入内存，必须为它分配一定大小的内存空间。
4.3.1 单一连续分配
只能用于单道程序环境下，整个内存的用户空间由一个程序独占。
4.3.2 固定分区分配
将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业。
1.划分分区的方法
分区大小相等、分区大小不等。
2.内存分配
通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”。
4.3.3 动态分区分配
又称可变分区分配。
1.动态分区分配中的数据结构
常用的数据结构有以下两种形式：
空闲分区表，表目：分区号、分区大小、分区始址、状态。
空闲分区链，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，以及前后都重复设置状态位和分区大小表目。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。
2.动态分区分配算法
顺序式搜索算法、索引式搜索算法。
3.分区分配操作
1）分配内存：
系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为 u.size，表中每个空闲分区的大小可表示为 m.size。若 m.size-u.size≤size(size 是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过 size)，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。
2）回收内存：
当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：
①回收区与插入点的前一个空闲分区相邻接，此时应将回收区与插入点的前一分区合并。
②回收分区与插入点的后一空闲分区相邻接，此时也可将两分区合并。
③回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并。
④回收区既不与前一个邻接，又不与后一个邻接，这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。
4.3.4 基于顺序搜索的动态分区分配算法
顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。
碎片：内存空间不断被划分，会留下许多难以利用的、很小的空闲分区。
1.首次适应（first fit，FF）算法
要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止，缺点是低址部分会不断被划分，形成碎片。
2.循环首次适应（next fit，NF）算法
在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找。实现可通过设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式。缺点缺乏大的空闲分区。
3.最佳适应（best fit，BF）算法
总是把能满足要求、又是最小的空闲分区分配给作业，为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。缺点产生许多碎片。
4.最坏适应（worst fit，WF）算法
在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，分割一部分空间给作业使用。要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求即可。缺点缺乏大的空闲分区。
4.3.5 基于索引搜索的动态分区分配算法
1.快速适应算法
又称为分类搜索法。是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。
该算法仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。在分配过程中，不会对任何分区产生分割。
2.伙伴系统
规定，无论已分配分区或空闲分区，其大小均为 2 的 k 次幂（k 为整数，l≤k≤m）。通常 2^m是整个可分配内存的大小。
对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。
当需要为进程分配一个长度为 n 的存储空间时，首先计算一个 i 值，使 2^(i-1) < n ≤ 2^i，然后在空闲分区大小为 2^i 的空闲分区链表中查找。若找到则直接分配。否则，则在分区大小为 2^(i+1) 的空闲分区链表中寻找。若存在 2^(i+1) 的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为 2^i 的空闲分区链表中。若仍然找不到，依次类推去寻找更高1次幂的分区。
与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为 2i的空闲分区时，若事先已存在回收块所对应的2i伙伴块的空闲分区时，则应将其与伙伴分区合并为大小为2(i+1)的空闲分区，若事先已存在新合并空闲块对应的2(i+1)伙伴块的空闲分区时，依次类推合并。
对于一个大小为2^k，地址为x的内存块，其伙伴块的地址则用buddy k (x)表示，其通式为：
if(x MOD 2^(k+1) == 0) {
buddy k (x) = x + 2^k;
}
else if(x MOD 2^(k+1) == 2^k) {
buddy k (x) = x - 2^k;
} 3.哈希算法
构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。
4.3.6 动态可重定位分区分配
1.紧凑
在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。当一台计算机运行了一段时间后，它的内存空间将会被分割成许多小的分区，而缺乏大的空闲分区。
通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。由于经过紧凑后的某些用户程序在内存中的位置发生了变化。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。
2.动态重定位
在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对(逻辑)地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。
地址变换过程是在程序执行期间，随着对每条指令或数据的访问借助重定位寄存器自动进行的，故称为动态重定位。当系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。
3.动态重定位分区分配算法
动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能。
4.4 对换
4.4.1 多道程序环境下的对换技术
1.对换的引入
所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。
2.对换的类型
1）整体对换。
处理机中级调度实际上就是存储器的对换功能。其目的用于解决内存紧张问题。由于中级调度是以进程为单位的，故又称之为“进程对换”或“整体对换”。
2）页面(分段)对换。
以进程的一个“页面”或“分段”为单位进行的，分别称为“页面对换”、“分段对换”，又统称为“部分对换”。
在此，我们只介绍进程对换，而分页或分段对换将放在虚拟存储器中介绍。
4.4.2 对换空间的管理
1.对对换空间管理的主要目标
在具有对换功能的 OS 中，通常把外存分为文件区和对换区。
1）对文件区管理的主要目标。
是提高文件存储空间的利用率，为此，对文件区采取离散分配方式。
2）对对换区管理的主要目标。
对换操作较频繁。故是提高进程换入和换出的速度。为此，采取的是连续分配方式，较少考虑外存中的碎片问题。
2.对换空间空闲盘块管理中的数据结构
与动态分区分配方式中的数据结构相似，即空闲分区表或空闲分区链。在每个表目中包含两项：对换区的首址及其大小，分表用盘块号和盘块数表示。
3.对换空间的分配与回收
与动态分区分配方式中内存分配与回收方法雷同。
4.4.3 进程的换出与换入
1.,进程的换出
换出过程：
1）选择被换出的进程。首先选择处于阻塞或睡眠状态的进程，如果有多个，则选择优先级最低的进程。在有的系统除了考虑优先级，还需考虑进程在内存的驻留时间。如果系统中已无阻塞进程且内存仍不足时，则选择优先级最低的就绪进程换出。
2）进程换出过程。只能换出非共享的程序和数据段，对于共享的只要还有进程需要，就不能换出。在进行换出时，①需要申请对换空间。②若申请成功，就启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。③若传送成功，便可回收该进程所占的内存空间，并对该进程的PCB和内存分配表等进行相应的修改，若还有可换出进程，则继续换出，直至内存中再无阻塞进程为止。
2.进程的换入
定时执行换入操作。找出“就绪”状态但已换出的进程，将其中换出时间最久的进程作为换入进程，为它申请内存。若申请成功则调入，若失败则需先将内存中的某些进程换出，再将进程换入。直到外存中再无“就绪且换出”状态的进程为止，或者已无足够的内存来换入进程时，对换进程停止换入。
4.5 分页存储管理方式
基于允许将一个进程直接分散地装入到许多不相邻接的分区中，则无须再进行“紧凑” 的思想而产生了离散分配方式。分为以下三种：
1）分页存储管理方式：将用户程序的地址空间分为若干个固定大小的区域，称为“页”或者“页面”。也将内存空间分为若干个物理块或页框，页和框的大小相同。
2）分段存储管理方式：把用户程序的地址空间分为若干个大小不同的段。分配以段为单位。
3）段页式存储管理方式：是分页和分段两种存储方式相结合的产物。
4.5.1 分页存储管理的基本方法
1.页面和物理块
1）页面：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号。相应地，也把内存的物理空间分成若干个块，并为各块加以编号。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。
2）页面大小：页面的大小应选择适中，且页面大小应是 2 的幂，通常为 1 KB～8 KB。
2.地址结构
逻辑地址的地址结构如下：
含有两部分：前一部分为页号 P，后一部分为位移量 W(或称为页内地址)。图中的地址长度为 32 位，其中 0～11 位为页内地址，即每页的大小为 4 KB；12～31 位为页号，即地址空间最多允许有 1 M 页。可见系统中允许的最大进程为4kb * 2^20 = 4GB。
对于某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为 A，页面的大小为 L，则页号 P 和页内地址 d 可按下式求得：
其中，INT 是整除函数，MOD 是取余函数。例如，其系统的页面大小为 1 KB，设 A = 2170 B，则由上式可以求得 P = 2，d = 122。
3.页表
为保证进程的正确运行，即能在内存中找到每个页面所对应的物理块。为此，系统又为每个进程建立了一张页面映像表，简称页表。在进程地址空间内的所有页，依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。
4.5.2 地址变换机构
实现从逻辑地址到物理地址的转换。由于页内地址和物理地址是一一对应的(例如，对于页面大小是 1 KB 的页内地址是 0～1023，其相应的物理块内的地址也是 0～1023，无须再进行转换)，因此，地址变换机构的任务实际上只是将逻辑地址中的页号，转换为内存中的物理块号。又因为页面映射表的作用就是用于实现从页号到物理块号的变换，因此，地址变换任务是借助于页表来完成的。
1.基本的地址变换机构
页表大多驻留在内存中。在系统中只设置一个页表寄存器 PTR，在其中存放页表在内存的始址和页表的长度。平时，进程未执行时，页表的始址和页表长度存放在本进程的 PCB 中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器中。因此，在单处理机环境下，虽然系统中可以运行多个进程，但只需一个页表寄存器。
当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址(相对地址)分为页号和页内地址两部分，再以页号为索引去检索页表。查找操作由硬件执行。在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间。于是，这一错误将被系统发现并产生一地址越界中断。若未出现越界错误，则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的变换。
2.具有快表的地址变换机构
由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据。
为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”，或称为“快表”，在 IBM 系统中又取名为 TLB，用以存放当前访问的那些页表项。此时的地址变换过程是：在 CPU 给出有效地址后，由地址变换机构自动地将页号 P 送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在块表中未找到对应的页表项，则还须再访问内存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，亦即，重新修改快表。但如果联想寄存器已满，则 OS 必须找到一个老的且已被认为不再需要的页表项，将它换出。
由于成本的关系，快表不可能做得很大，通常只存放 16～512 个页表项，如果页面大小为4kb，那么支持的最大进程为2 MB，这对中、小型作业来说，已有可能把全部页表项放在快表中。据统计，从快表中能找到所需页表项的机率可达 90%以上。
4.5.3 访问内存的有效时间
从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所需要花费的总时间，称为内存的有效访问时间(EAT)。
假设访问一次内存的时间为t，在基本分页存储管理方式中，有效访问时间分为第一次访问内存时间(即查找页表对应的页表项所耗费的时间t)与第二次访问内存时间(即访问页表项中的物理块号与页内地址所拼接成的实际物理地址所耗费的时间t)之和： EAT = t + t = 2t；
在快表中查找到所需表项存在着命中率的问题。所谓命中率，是指使用快表并在其中成功查找到所需页面的表项的比率。
则：EAT = а×λ + (t+λ)(1-а) + t = 2t + λ - t×а；
上式中，λ表示查找快表所需要的时间，а表示命中率，t表示访问一次内存所需要的时间。
4.5.4 两级和多级页表
现代的大多数计算机系统，都支持非常大的逻辑地址空间，因此页表就变得非常大，要占用相当大的内存空间。因为每个页表项占用一个字节，故页表长度 * 1字节就是页表所占的内存空间大小。且页表内存空间还要求是连续的，显然这是不现实的。解决方法：
(1) 对于页表所需的内存空间，可采用离散分配方式来解决难以找到一块连续的大内存空间的问题；
(2) 只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。
1.两级页表
将页表进行分页，然后离散地将各个页面分别存放在不同的物理块中。也要为离散分配的页表再建立一张页表，称为外层页表，在每个页表项中记录了页表页面的物理块号。
以前面的 32 位逻辑地址空间为例来说明，当页面大小为 4 KB 时，采用两级页表结构时，再对页表进行分页，使每页中包含 2^10 (即 1024)个页表项，最多允许有 2^10个页表分页。此时的逻辑地址结构如下：
在页表的每个表项中存放的是进程的某页在内存中的物理块号，而在外层页表的每个页表项中，所存放的是某页表分页的在内存中的物理块号。可以利用外层页表和页表这两级页表，来实现从进程的逻辑地址到内存中物理地址间的变换。在地址变换机构中同样需要增设一个外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号，找到指定页表分页的始址，再根据外层页内地址找到指定的页表项，再从该页表项中读出该页在内存中的物理块号。
虽然解决了对大页表无需大片连续存储空间的问题，但并未解决用较少的内存空间去存放大页表的问题。只用离散分配空间的办法并未减少页表所占用的内存空间。解决方法是把当前需要的一批页表项调入内存，以后再根据需要陆续调入。在采用两级页表结构的情况下，对于正在运行的进程，必须将其外层页表调入内存，而对页表则只需调入一页或几页。为了表征某页的页表是否已经调入内存，还应在外层页表项中增设一个状态位 S，其值若为 0，表示该页表分页尚未调入内存；否则，
说明其分页已在内存中。进程运行时，地址变换机构根据逻辑地址中的外层页号 P1，去查找外层页表；若所找到的页表项中的状态位为 0，则产生一中断信号，请求 OS 将该页表分页调入内存。关于请求调页的详细情况，这是下一章虚拟存储器中的知识。
2.多级页表
对于 32 位的机器，采用两级页表结构是合适的；但对于 64 位的机器，必须采用多级页表，将外层页表再进行分页。
4.5.5 反置页表
1.反置页表的引入
在现代计算机系统中，通常允许一个进程的逻辑地址空间非常大，因此就需要有许多的页表项，而因此也会占用大量的内存空间。 引入反置页表，一般页表的页表项是按页号进行排序的，页表项中的内容是物理块号。而反置页表则是为每一个物理块设置一个页表项，并按物理块的编号排序。其中的内容是页号和其所隶属进程的标识符。
2.地址变换
利用反置页表进行地址变换时，是根据进程标识符和页号，去检索反置页表。如果检索到与之匹配的页表项，则该页表项(中)的序号i便是该页所在的物理块号，可用该块号与页内地址一起构成物理地址送内存地址寄存器。
在反置页表可能只包含已经调入内存中的页面，并未包含尚未调入内存的页面。因此还必须为每个进程建立一个外部页表。当发现所需之页面不在内存时，因在外部页表中包含了各个页面在外存的物理地址，通过它可将所需之页面调入内存。
当内存容量很大时，也表项的数目还是会非常大的。要利用进程标识符和页号去检索这样大的一个线性表是相当费时的。可利用Hash算法来进行检索，可以很快找到在反置页表中相应页表项，不过可能会出现所谓的“地址冲突”。
4.6 分段存储管理方式
如果说推动存储管理方式从固定分区到动态分区分配，进而又发展到分页存储管理方式的主要动力，是提高内存利用率，那么，引入分段存储管理方式的目的，则主要是为了满足用户(程序员)在编程和使用上多方面的要求。
4.6.1 分段存储管理方式的引入
1.方便编程
通常，用户把自己的作业按照逻辑关系划分为若干个段。程序员们都迫切地需要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的。
2.信息共享
实现对程序和数据的共享时，是以信息的逻辑单位为基础的。分页系统中的“页”只是存放信息的物理单位(块)，并无完整的意义。而段却是信息的逻辑单位，因此可以为该被共享过程建立一个独立的段，极大地简化了共享的实现。
3.信息保护
信息保护同样是对信息的逻辑单位进行保护的。在分页系统中，一个函数可能要占用若干个页面，而且其中的第一个和最后一个页面还会装有其它程序段的数据，它们可能有着不同的保护属性。
4.动态增长
5.动态链接
运行时动态链接要求的是以目标程序(即段)作为链接的基本单位，因此，分段存储管理方式非常适合动态链接。
4.6.2 分段系统的基本原理
1.分段
作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。每个段都从 0 开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间由于是分成多个段，因而呈现出二维特性。其逻辑地址由短号和段内地址组成。
2.段表
在分段式存储管理系统中，则是为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度。可见，段表是用于实现从逻辑段到物理内存区的映射。
3.地址变换机构
为了实现从进程的逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址和段表长度 TL。在进行地址变换时，系统将逻辑地址中的段号与段表长度TL 进行比较。若 S>TL，表示段号太大，是访问越界，于是产生越界中断信号；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址，然后，再检查段内地址 d 是否超过该段的段长 SL。若超过，即 d>SL，同样发出越界中断信号；若未越界，则将该段的基址与段内地址相加，即可得到要访问的内存物理地址。
像分页系统一样，当段表放在内存中时，每要访问一个数据，都须访问两次内存，从而极大地降低了计算机的速率。解决的方法也和分页系统类似，再增设一个联想存储器，用于保存最近常用的段表项。
4.分页和分段的主要区别
相似之处：
两者都采用离散分配方式，且都要通过地址映射机构来实现地址变换。
不同：
1）页是信息的物理单位，分页是为了提高内存的利用率。段则是信息的逻辑单位，分段的目的是为了能更好地满足用户的需要。
2）页的大小固定且由系统决定。而段的长度却不固定，决定于用户所编写的程序。
3）分页中用户程序的的逻辑地址空间是一维的，分页完全是系统的行为，只需要一个记忆符即可表示一个地址。而分段中用户程序的逻辑地址空间是二维的，在标识一个地址时，既需给出段名， 又需给出段内地址（正是因为段的大小不固定导致的）。
4.6.3 信息共享
1.分页系统中对程序和数据的共享
虽然也能实现对程序和数据的共享，但远不如分段系统来得方便。
2.分段系统中对程序和数据的共享
可重入代码又称为“纯代码”，是一种允许多个进程同时访问的代码。可重入代码是一种不允许任何进程对它进行修改的代码。但事实上，大多数代码在执行时都可能有些改变。为此，在每个进程中，都必须配以局部数据区，把在执行中可能改变的部分拷贝到该数据区，这样，程序在执行时，只需对该数据区(属于该进程私有)中的内容进行修改，并不去改变共享的代码，这时的可共享代码即成为可重入码。
4.6.4 段页式存储管理方式
1.基本原理
段页式系统的基本原理是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成。
为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。段表的内容与分段系统略有不同，它不再是内存始址和段长，而是页表始址和页表长度。即一个分段对应一个页表。
2.地址变换过程
为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段长TL。进行地址变换时，首先利用段号S，将它与段长TL进行比较。若S < TL，表示未越界，于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址。