分页&段存储管理方式
目录
参考资料：
技术背景
连续分配方式会形成许多“碎片”，虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间，但须为之付出很大开销。如果允许将一个进程直接分散地装入到许多不相邻接的分区中，便可充分地利用内存空间，而无须再进行“紧凑”。
基于这一思想而产生了离散分配方式。根据在离散分配时所分配地址空间的基本单位的不同，又可将离散分配分为以下三种：
- 分页存储管理方式
- 分段存储管理方式
- 段页式存储管理方式
分页存储管理方式 | 程序分页，存储分块
- 在该方式中，将用户程序的地址空间分为若千个固定大小的区域，称为“页”或“页面”。典型的页面大小为 1KB。
- 相应地，也将内存空间分为若干个物理块或页框(frame)
- 页和块的大小相同。这样可将用户程序的任一页放入任一物理块中，实现了离散分配
1 分页存管理的基本方法
将进程的逻辑地址空间分成若干个页，并为各页加以编号，从 0 开始，如第 0 页、第 1 页等。页或者页面，典型的页面大小为 1KB。
把内存的物理地址空间分成若干个块，同样也为它们加以编号，如 0# 块、1# 块等等。
页面大小和物理块大小相同
- 在为进程分配内存时，以块为单位，将进程中的若干个页分别装入到多个可以不相邻接的物理块中。
由于进程的最后一页经常装不满块，而形成了不可利用的碎片，称之为页内碎片。
方便记忆：程序页放入物理块
页面大小
- 过小的页面大小，虽然一方面可以减小内存碎片，起到减少内存碎片总空间的作用，有利于内存利用率的提高，但另一方面却会造成每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存。此外，还会降低页面换进换出的效率。
- 页面过大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。
因此，页面的大小应选择适中，且页面大小应是 2 的幂，通常为 1 KB ~ 8 KB。
地址结构
分页地址中的地址结构如下：
31 12 11 0
| 页号 P | 页内地址 W |它包含两部分内容：前一部分为页号 P，后一部分为位(偏)移量 ，即页内地址。图中的地址长度为 32 位，其中 0~11 位为页内地址，即每页的大小为 4KB(2^12B)；12~31 位为页号，地址空间最多允许有 1M(2^20B) 页。
每页的最大大小和页号的最大值是由地址结构限制的
对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为 A(Address)，页面的大小为 L(Length)，则页号 P(Page) 和页内地址 d 可按下式求得：
其中，INT 是整除函数，MOD 是取余函数。例如，其系统的页面大小为 1 KB，设 A = 2170 B，则由上式可以求得 P = 2，d = 122。
// 2170 / 1024(1K) ：商为 2，余数为 122
// 逻辑空间地址为 2170，页面大小为 1 KB，那么至少需要在第 3 个页面进行存储（页面编号从 0 开始），然后页内地址为 122（获取余数后，此时不用 -1，因为页内地址也是从 0 开始，减 1 和加 1 后，正好就是逻辑地址的起始位置，刚好抵消）
1.3 页表
在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表。
在进程地址空间内的所有页（0~n），依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号。在配置了页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。
即使在简单的分页系统中，也常在页表的表项中设置一存取控制字段，用于对该存储块中的内容加以保护。当存取控制字段仅有一位时，可用来规定该存储块中的内容是允许读/写，还是只读 ；若存取控制字段为二位，则可规定为读/写、只读和只执行等存取方式。如果有一进程试图去写一个只允许读的存储块时，将引起操作系统的一次中断。如果要利用分页系统去实现虚拟存储器，则还须增设一个数据项。
2 地址变换机构
为了能将用户地址空间中的逻辑地址转换为内存空间中的物理地址，在系统中必须设置地址变换机构。该机构的基本任务是实现从逻辑地址到物理地址的转换。由于页内地址和物理地址是一一对应的，因此， 地址变换机构的任务实际上只是将逻辑地址中的页号转换为内存中的物理块号。又因为页面映射表的作用就是用于实现从页号到物理块号的变换，因此，地址变换任务是借助于页表来完成的。
用户空间(程序)内的逻辑地址(2170) -> 页表&页内地址(2 122) -> 页表(2->6#) -> 物理块号(6# 122) -> 物理地址(1024 * 6 + 122 = 6266)
2.1 基本的地址变换机构
进程在运行期间，需要对程序和数据的地址进行变换，即将用户地址空间中的逻辑地址变换为内存空间中的物理地址，由于它执行的频率非常高，每条指令的地址都需要进行变换，因此 需要采用硬件来实现（速度更快）。
页表功能是由一组专门的寄存器来实现的。一个页表项用一个寄存器。由于寄存器具有较高的访问速度，因而有利于提高地址变换的速度；但由于寄存器成本较高，且大多数现代计算机的页表又可能很大，使页表项的总数可达几千甚至几十万个，显然，这些页表项不可能都用寄存器来实现。因此，页表大多驻留在内存中。 在系统中只设置一个页表寄存器 PTR(Page-Table Register)，在其中存放页表在内存的始址和页表的长度。
平时， 进程未执行时，页表的始址和页表长度存放在本进程的 PCB 中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器中。因此，在单处理机环境下，虽然系统中可以运行多个进程，但只需一个页表寄存器。
当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址分为页号和页内地址两部分，再以页号为索引去检索页表，查找操作由硬件执行。
在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间。于是，这一错误将被系统发现，并产生一地址越界中断。若未出现越界错误，则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的变换。
2.2 具有快表的地址变换机构
基本的地址变换机构的缺点：由于页表是存放在内存中的，这使 CPU 在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量 W 拼接以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据。因此，采用这种方式将使计算机的处理速度降低近 1/2。可见，以此高昂代价来换取存储器空间利用率的提高，是得不偿失的。
解决方案：为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”(Associative Memory)，或称为“快表”，用以 存放当前访问的那些页表项。
此时的地址变换过程是：在 CPU 给出有效地址后，由地址变换机构自动地将页号 P 送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在快表中未找到对应的页表项，则还须再访问内存中的页表，找到后，把从页表项中读出的物理块号送往地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，亦即，重新修改快表。但如果联想寄存器已满，则 OS 必须找到一个老的且已被认为是不再需要的页表项，将它换出。
由于成本的关系，快表不可能做得很大，通常只存放 16~512 个页表项，这对中、小型作业来说，已有可能把全部页表项放在快表中；但对于大型作业而言，则只能将其一部分页表项放入其中。由于对程序和数据的访问往往带有局限性，因此，据统计，从快表中能找到所需页表项的概率可达 90% 以上。这样，由于增加了地址变换机构而造成的速度损失可减少到 10% 以下，达到了可接受的程度。
使用高速缓存寄存器可以有效提高程序速度
3 访问内存的有效时间
从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所需要花费的总时间，称为内存的有效访问时间（Effective Access Time，EAT）。
4 两级和多级页表
现代的大多数计算机系统都支持非常大的逻辑地址空间，在这样的环境下，页表就变得非常大，要占用相当大的内存空间。
例如，对于一个具有 32 位逻辑地址空间的分页系统，规定页面大小为 4KB，则在每个进程页表中的页表项数可达 1MB 之多。又因为每个页表项占用一个字节，故每个进程仅仅其页表就要占用 1MB 的内存空间，而且还要求是连续的。显然这是不现实的，我们可以采用这样两个方法来解决这一问题：
注意这里的 1MB 上限是由地址结构确定的，不是由内存的实际大小确定的，如果内存不够大，那么就会出现无法达到 1MB 的情况
- 对于页表所需的内存空间，可采用离散分配方式，以解决难以找到一块连续的大内存空间的问题。 //离散分配
- 只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上需要时再调入。 //用时调度
两级和多级页表的思想： 对页表进行再分页，在外层页表（Outer Page Table）的每个页表项中记录页表页面的物理块号。
每个页表的大小同物理块的大小相同，这样每张页表刚好能放到对应的物理块，查找也方便
5 反置页表（Inverted Page Table）
5.1 反置页表的引入
在分页系统中，为每个进程配置了一张页表，进程逻辑地址空间中的每一页，在页表中都对应有一个页表项。
在现代计算机系统中，通常允许一个进程的逻辑地址空间非常大，因此就需要有许多的页表项，而因此也会占用大量的内存空间。 为了减少页表占用的内存空间，引入了反置页表。
一般页表的页表项是按页号进行排序的，页表项中的内容是物理块号。而反置页表则是为每一个物理块设置一个页表项，并将它们按物理块的编号排序，其中的内容则是页号和其所隶属进程的标识符。
需要 PID 的原因：不同进程的页号可能相同，所以需要 PID 来区分
// 页表是逻辑地址 -> 物理地址的映射，反置页表是由物理地址 -> 逻辑地址的映射，刚好反过来了
5.2 地址变换
参考资料：
在利用反置页表进行地址变换时，是根据进程标识符和页号，去检索反置页表。如果检索到与之匹配的页表项，则该页表项的序号 i 便是该页所在的物理块号，可用该块号与页内地址一起构成物理地址送内存地址寄存器。若检索了整个反置页表仍未找到匹配的页表项，则表明此页尚未装入内存。对于不具有请求调页功能的存储器管理系统，此时则表示地址出错。对于具有请求调页功能的存储器管理系统，此时应产生请求调页中断，系统将把此页调入内存。 //只能保存部分数据
虽然反置页表可有效地减少页表占用的内存，然而，在该表中只包含了已经调入内存的页面，并未包含尚未调入内存的页面。因此，还必须为每个进程建立一个外部页表（External Page Table）。该页表与传统的页表一样，当所访问的页面在内存时，并不需要访问外部页表，仅当发现所需之页面不在内存时，才使用它。在页表中包含了各个页在外存的物理位置，通过它可将所需之页面调入内存。
由于在反置页表中是为每一个物理块设置一个页表项，当内存容量很大时，页表项的数目还是会非常大的。要利用进程标识符和页号去检索这样大的一张线性表是相当费时的。于是可 利用 Hash 算法来进行检索，这样可以很快地找到在反置页表中的相应页表项。不过在采用 Hash 算法时，可能会出现所谓的“地址冲突”，即有多个逻辑地址被映射到同一个 Hash 表项上，必须妥善解决这一问题。
将为页号 A 的块项放到 A MOD N 的位置上，有多个页号映射到同一个位置上，就会出现地址冲突，使用 next 指针构成链表，解决地址冲突
当搜索到的页号与所要查找的页号相同时，查看 PID 是否相同，相同则找到，不同则通过 next 指针继续查找
好像需要额外维护一张 hash 表，用于记录每个位置的第一个块
分段存储管理方式
连续分配 -> 固定分区分配 -> 动态分区分配 -> 离散分配（分页存储）
如果说，推动上述发展的主要动力都是直接或间接地出于提高内存利用率的目的，那么，引入分段存储管理方式的目的则主要是为了满足程序员在编程和使用上多方面的要求，其中有些要求是其它几种存储管理方式所难以满足的。因此，这种分段存储管理方式已成为当今所有存储管理方式的基础，许多高级语言和 C 语言的编译程序也都支持分段存储管理方式。
1 分段存储管理式的引入
为什么要引入分段存储管理方式？可从下面两个方面说明：
- 一方面是由于通常的程序都可分为若干个段，如主程序段、子程序段 A、子程序段 B、···、数据段以及栈段等，每个段大多是一个相对独立的逻辑单位。
- 另一方面，实现和满足信息共享、信息保护、动态链接以及信息的动态增长等需要，也都是以段为基本单位的。更具体地说，分段存储管理方式更符合用户和程序员如下多方面的需要。
1.1 方便编程
通常，用户把自己的作业按照逻辑关系划分为若千个段，每个段都从 0 开始编址，并有自己的名字和长度。因此，程序员们都迫切地需要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的，这不仅可以方便程序员编程，也可使程序非常直观，更具可读性。
例如，下述的两条指令便使用段名和段内地址：
LOAD 1, [A] | (D); //将分段 A 中 D 单元内的值读入寄存器 1
STORE 1, [B] | (C); //将寄存器 1 的内容存入 B 分段的 C 单元中1.2 信息共享
在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。比如，为了共享某个过程、函数或文件。分页系统中的 “页” 只是存放信息的物理单位(块)，并无完整的逻辑意义，这样，一个可被共享的过程往往可能需要占用数十个页面，这为实现共享增加了困难。如前所述，段可以是信息的逻辑单位，因此，我们可以 为该被共享过程建立一个独立的段，这就极大地简化了共享的实现。
可重入代码：
可重入代码（Reentrant Code）又称为“纯代码”（Pure Code），是一种允许多个进程同时访问的代码。为使各个进程所执行的代码完全相同，绝对不允许可重入代码在执行中有任何改变。因此，可重入代码是一种不允许任何进程对它进行修改的代码。
但事实上，大多数代码在执行时都可能有些改变，例如，用于控制程序执行次数的变量以及指针、信号量及数组等。为此，在每个进程中，都必须配以局部数据区，把在执行中可能改变的部分拷贝到该数据区，这样，程序在执行时，只需对该数据区（属于该进程私有）中的内容进行修改，并不去改变共享的代码，这时的可共享代码即成为可重入代码。
1.3 信息保护
信息保护同样是以信息的逻辑单位为基础的，而且经常是以一个过程、函数或文件为基本单位进行保护的。例如，我们希望函数 A 仅允许进程执行，而不允许读，更不允许写。那么，我们只须在包含了函数 A 的这个段上标上只执行标志即可。但是在分页系统中，函数 A 可能要占用若干个页面，而且其中的第一个和最后一个页面还会装有其它程序段的数据，它们可能有着不同的保护属性，如可以允许进程读写，这样就很难对这些页面实施统的保护，因此，分段管理方式能更有效和方便地实现对信息的保护功能。
1.4 动态增长
在实际应用中，往往存在着一些段，尤其是数据段，在它们的 使用过程中，由于数据量的不断增加，而使数据段动态增长，相应地它所需要的存储空间也会动态增加。然而，对于数据段究竟会增长到多大，事先又很难确切地知道。对此，很难采取预先多分配的方法进行解决。前述的其它几种存储管理方式都难以应付这种动态增长的情况，而分段存储管理方式却能较好地解决这一问题。
1.5 动态链接
为了提高内存的利用率，系统只将真正要运行的目标程序装入内存，也就是说，动态链接在作业运行之前，并不是把所有的目标程序段都链接起来。当程序要运行时，首先将主程序和它立即需要用到的目标程序装入内存，即启动运行。而在程序运行过程中，当需要调用某个目标程序时，才将该段(目标程序)调入内存并进行链接。可见，动态链接要求的是以目标程序(即段)作为链接的基本单位，因此，分段存储管理方式非常适合于动态链接。
2 分段系统的基本原理
2.1 分段
在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。每个段都有自己的名字，为了实现简单起见，通常可用一个段号来代替段名，每个段都从 0 开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因此各段的长度并不相等。整个作业的地址空间由于被分成多个段，每个段既包含了一部分地址空间，又标识了逻辑关系。其逻辑地址由段号和段内地址所组成。 //段号+段内地址
分段地址中的地址具有如下结构：
在该地址结构中，允许一个作业最长有 64K 个段，每个段的最大长度为 64 KB。
2^16 = (2^10) * (2^2) = 64 K(1024 = 1K)
段内地址应该理解为指针，指向内存的某一个位置
2.2 段表
在动态分区分配方式中，系统为整个进程分配一个连续的内存空间。而 在分段式存储管理系统中，则是为每个分段分配一个连续的分区。
进程中的各个段，可以离散地装入内存中不同的分区中。为保证程序能正常运行，就必须能从物理内存中找出每个逻辑段所对应的位置。为此，在系统中，类似于分页系统，需为每个进程建立一张段映射表，简称段表。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址和段的长度。
段表可以存放在一组寄存器中，以利于提高地址转换速度。但更常见的方法是将段表放在内存中。在配置了段表后，执行中的进程可通过查找段表，找到每个段所对应的内存区。可见，段表是用于实现从逻辑段到物理内存区的映射的。
2.3 地址变换机构
为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址和段表长度 TL。
在进行地址变换时，系统将逻辑地址中的段号 S与段表长度 TL进行比较。若 S > TL，表示段号太大，是访问越界，于是产生越界中断信号。若未越界则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址。然后，再检查段内地址 d 是否超过该段的段长 SL。若超过，即 d > SL，同样发出越界中断信号。若未越界，则将该段的基址 d 与段内地址相加，即可得到要访问的内存物理地址。
像分页系统一样，当段表放在内存中时，每要访问一个数据，都须访问两次内存，从而成倍地降低了计算机的速率。 解决的方法和分页系统类似，也增设一个联想存储器，用于保存最近常用的段表项。一般情况下，由于是段比页大，因而段表项的数目比页表项的数目少，其所需的联想存储器也相对较小，所以可以显著地减少存取数据的时间，与没有地址变换的常规存储器相比而言，其存取速度约慢 10%~15%。
分页和分段的主要区别
由上所述不难看出，分页和分段系统有许多相似之处。比如，两者都采用离散分配方式，且都是通过地址映射机构实现地址变换。但在概念上两者完全不同，主要表现在下述三个方面：
- 页是信息的物理单位。采用分页存储管理方式是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅只是系统管理上的需要，完全是系统的行为，对用户是不可见的。分段存储管理方式中的 段则是信息的逻辑单位，它通常包含的是一组意义相对完整的信息。分段的目的主要在于能更好地满足用户的需要。
- 页的大小固定且由系统决定。在采用分页存储管理方式的系统中，在硬件结构上就把用户程序的逻辑地址划分为页号和页内地址两部分，也就是说是直接由硬件实现的，因而在每个系统中只能有一种大小的页面。而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
- 分页的用户程序地址空间是一维的。分页完全是系统的行为，故在分页系统中用户程序的地址是属于单一的线性地址空间，程序员只需利用一个记忆符即可表示一个地址。而分段是用户的行为，故在分段系统中，用户程序的地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。
段页式存储管理方式
分页系统以页面作为内存分配的基本单位，能有效地提高内存利用率，而分段系统以段作为内存分配的基本单位，它能够更好地满足用户多方面的需要。如果能对两种存储管理方式“各取所长”，则可形成一种新的存储器管理方式————段页式存储管理方式。这种新的系统既具有分段系统的便于实现、分段可共享、易于保护、可动态链接等一系列优点，又能像分页系统那样，很好地解决内存的外部碎片问题。
分页 -> 提高内存利用率
分段 -> 满足编程需要
1 基本原理
段页式系统的基本原理是分段和分页原理的结合，即 先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成。
在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。段表的内容与分段系统略有不同，它不再是内存始址和段长，而是页表始址和页表长度。
2 地址变换过程
在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段长 TL。进行地址变换时，首先利用段号 S，将它与段长 TL进行比较。若 S > TL 表示未越界，于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号 P来获得对应页的页表项位置，从中读出该页所在的物理块号 b，再利用块号 b 和页内地址来构成物理地址。
// 段表始址+段长 —> 确定段表项位置 —> 页表始址+页号 —> 确定页表项位置 —> 获取物理块号 —> 物理地址
在段页式系统中，为了获得一条指令或数据，须三次访问内存。
- 第一次访问是访问内从中取出该页所在的存中的段表，从中取得页表始址。
- 第二次访问是访问内存中的页表，物理块号，并将该块号与页内地址一起形成指令或数据的物理地址。
- 第三次访问才是真正从第二次访问所得的地址中取出指令或数据。
显然，这使访问内存的次数增加了近两倍。为了提高执行速度，在地址变换机构中增设一个高速缓冲寄存器。每次访问它时，都须同时利用段号和页号去检索高速缓存，若找到匹配的表项，便可从中得到相应页的物理块号，用来与页内地址一起形成物理地址；若未找到匹配表项，则仍需第三次访问内存，它的基本原理与分页及分段的情况相似。