段&页

段式存储

基本思想

页面是主存物理空间中划分出来的等长的固定区域。分页方式的优点是页长固定，因而便于构造页表、易于管理，且不存在外碎片。但分页方式的缺点是页长与程序的逻辑大小不相关。例如，某个时刻一个子程序可能有一部分在主存中，另一部分则在辅存中。这不利于编程时的独立性，并给换入换出处理、存储保护和存储共享等操作造成麻烦。

另一种划分可寻址的存储空间的方法称为分段。段是按照程序的自然分界划分的长度可以动态改变的区域。通常，程序员把子程序、操作数和常数等不同类型的数据划分到不同的段中，并且每个程序可以有多个相同类型的段。

段表本身也是一个段，可以存在辅存中，但一般是驻留在主存中。

将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。

分段地址结构

作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例程序段、数据段等。每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间是二维的。

下图中，段号是16位，段内偏移量是为16位，则一个作业最多可有216=65536个段，最大段长为64KB。

在页式系统中，逻辑地址的页号和页内偏移量对用户是透明的，但在段式系统中，段号和段内偏移量必须由用户显示提供，在髙级程序设计语言中，这个工作由编译程序完成。

在段式虚拟存储系统中，虚拟地址由段号和段内地址组成，虚拟地址到实存地址的变换通过段表来实现。每个程序设置一个段表，段表的每一个表项对应一个段，每个表项至少包括三个字段：有效位（指明该段是否已经调入主存）、段起址(该段在实存中的首地址)和段长（记录该段的实际长度）。

段表用于实现从逻辑段到物理内存区的映射。在配置了段表后，执行中的进程可通过查找段表，找到每个段所对应的内存区。

%!(EXTRA markdown.ResourceType=, string=, string=)

地址变换

针对每一个虚拟地址，存储管理部件首先以段号S为索引访问段表的第S个表项。若该表项的有效位为1，则将虚拟地址的段内地址D与该表项的段长字段比较；若段内地址较大则说明地址越界，将产生地址越界中断；否则，将该表项的段起址与段内地址相加，求得主存实地址并访存。如果该表项的有效位为0，则产生缺页中断，从辅存中调入该页，并修改段表。段式虚拟存储器虚实地址变换过程如图所示。

绝对地址=根据段号找到段表中的起始地址+段内地址 (如果段内地址超过限长则产生“地址越界”程序性中断事件达到存储保护)

段的共享和保护

在分段系统中，段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。当一个作业正从共享段中读取数据时，必须防止另一个作业修改此共享段中的数据。

不能修改的代码称为纯代码或可重入代码（它不属于临界资源）。这样的代码和不能修改的数据是可以共享的，而可修改的代码和数据则不能共享。（需要修改数据时，每个访问进程必须配置局部数据区，并在执行中可能改变的部分拷贝到该区域）

与分页管理类似，分段管理的保护方法主要有两种：一种是存取控制保护，另一种是地址越界保护。地址越界保护是利用段表寄存器中的段表长度与逻辑地址中的段号比较，若段号大于段表长度则产生越界中断；再利用段表项中的段长和逻辑地址中的段内位移进行比较，若段内位移大于段长，也会产生越界中断。

分段存储方式的优缺点

分页对程序员而言是不可见的，而分段通常对程序员而言是可见的，因而分段为组织程序和数据提供了方便。与页式虚拟存储器相比，段式虚拟存储器有许多优点：

1. 段的逻辑独立性使其易于编译、管理、修改和保护，也便于多道程序共享。
2. 段长可以根据需要动态改变，允许自由调度，以便有效利用主存空间。
3. 方便编程，分段共享，分段保护，动态链接，动态增长

因为段的长度不固定，段式虚拟存储器也有一些缺点：

1. 主存空间分配比较麻烦。
2. 容易在段间留下许多碎片，造成存储空间利用率降低。
3. 由于段长不一定是2的整数次幂，因而不能简单地像分页方式那样用虚拟地址和实存地址的最低若干二进制位作为段内地址，并与段号进行直接拼接，必须用加法操作通过段起址与段内地址的求和运算得到物理地址。因此，段式存储管理比页式存储管理方式需要更多的硬件支持。

页式存储

页式存储管理页式存储管理中，物理内存被划分为大小相同的基本分配单位，我们称为页帧，页帧的大小必须是2的幂次方，这样进行地址转换的时候比较快，可以通过二进制移位实现。比如32位系统中，4Kbyte是常见的页帧大小。而逻辑内存也被划分为大小相同的基本分配单位，我们称为页面，页面与页帧大小必须相等。

页帧与页面一个是对物理内存地址一个是对逻辑内存地址而言的。因此页式存储管理中要处理逻辑地址与物理地址的转换，也就变为对页面到页帧的转换。而储存映射关系的表我们称为页表，由操作系统维护。具体硬件实现则是由MMU和TLB共同实现。

帧

物理内存被分为大小相等的帧，物理内存的地址用一个二元组表示%!(EXTRA markdown.ResourceType=, string=, string=)

，其中 f 是帧号，比如一个帧号由F bit表示，那也就是说一共有%!(EXTRA markdown.ResourceType=, string=, string=)

个帧，o 是帧内偏移，比如偏移由S bit表示，那么一个帧内有

字节。那么物理地址 = 

页

逻辑内存被划分为大小相等的页，表示方式与帧类似。由于帧与页的大小是相等的。因此在映射关系中 ，页内偏移与帧内偏移是相等的，但是页号与帧号通常是不相等的。因为逻辑内存是连续的，物理地址不是连续的。

页表

那么如何实现页与帧之间的地址转换呢？也就是如何实现逻辑地址与物理地址之间的转换。如下图：操作系统维护页表，页表内存储页号与帧号之间的映射关系。页表基址表明了页表存储在什么地方。比如当程序P执行过程中，CPU要访问(p, o)，操作系统通过页表得到帧号f，通过(f, o)找到物理内存地址。而由于帧和页的大小是2的幂次方，因此实际上地址就是将 f 左移 S 位之后加上 o 即得到物理地址。

每个进程都有一个页表，且有以下特点：

• 每个页面对应一个页表项
• 页表随进程运行状态而动态变化
• 页表的起始地址即基址存储在页表基址寄存器（PTBR: Page Table Base Register）中

页表内除了存储前面提过的帧号，还存储了一些页表项标志位：

• 存在位，记录该页号是否有对应的帧
• 修改位，记录页面的内容是否修改了
• 引用位，记录是否有对该页面的访问

那么实际操作中，如下图，标志位为0意味着没有给页分配帧，就可以动态的进行变化。

页表项

页目录和页表的表项格式如图4-18所示。其中位31～12含有物理地址的高20位，用于定位物理地址空间中一个页面（也称为页帧）的物理基地址。表项的低12位含有页属性信息。

• P:位0是存在（Present）标志，用于指明表项对地址转换是否有效。P=1表示有效；P=0表示无效。在页转换过程中，如果说涉及的页目录或页表的表项无效，则会导致一个异常。如果P=0，那么除表示表项无效外，其余位可供程序自由使用，如图4-18b所示。例如，操作系统可以使用这些位来保存已存储在磁盘上的页面的序号。
• R/W:位1是读/写（Read/Write）标志。如果等于1，表示页面可以被读、写或执行。如果为0，表示页面只读或可执行。当处理器运行在超级用户特权级（级别0、1或2）时，则R/W位不起作用。页目录项中的R/W位对其所映射的所有页面起作用。
• U/S:位2是用户/超级用户（User/Supervisor）标志。如果为1，那么运行在任何特权级上的程序都可以访问该页面。如果为0，那么页面只能被运行在超级用户特权级（0、1或2）上的程序访问。页目录项中的U/S位对其所映射的所有页面起作用。
• A:位5是已访问（Accessed）标志。当处理器访问页表项映射的页面时，页表表项的这个标志就会被置为1。当处理器访问页目录表项映射的任何页面时，页目录表项的这个标志就会被置为1。处理器只负责设置该标志，操作系统可通过定期地复位该标志来统计页面的使用情况。
• D:位6是页面已被修改（Dirty）标志。当处理器对一个页面执行写操作时，就会设置对应页表表项的D标志。处理器并不会修改页目录项中的D标志。
• AVL:该字段保留专供程序使用。处理器不会修改这几位，以后的升级处理器也不会。

页式访问的性能问题

内存访问的性能问题：访问一个物理内存单元需要两次访问内存。第一次先访问页表进行查询，第二次才是访问物理内存获取数据。页表的大小问题：页表可能非常大。比如一个64位机器（

字节内存），假如一页大小为1024字节（%!(EXTRA markdown.ResourceType=, string=, string=)

），那么一共可以产生

页（帧），64位的系统想要表示一个帧的地址就需要64位，也就是8字节，也就是说想表示一个帧，即使不考虑标志位也需要8字节，那使用很多页面，比如全部使用

页，就需要%!(EXTRA markdown.ResourceType=, string=, string=)

字节，仅仅存储页表就要这么多字节占用了很多空间。

针对这些问题，也有一些对应的解决方案：

• 缓存：程序执行时具有连续性即相邻性，访问了一个数组第一个元素，下一个极有可能访问第二个元素，因此当我缓存下来页表项，利用缓存可以极大可能地访问到想要的数据。
• 间接访问：将长页表切断，实际就是多级页表，一层层去查询。

为了缓解上述性能问题，出现了一些解决方案，比如快表、多级页表和反置页表。

快表（TLB: Translation Look-aside Buffer）

快表是指缓存近期访问过的页表项。

它有以下特点：

TLB使用关联存储（associative memory）实现，具备快速访问性能，因为关联存储在CPU内；如果TLB命中，可以直接访问物理内存；如果TLB未命中，仍需查询页表，并将对应表项更新到TLB中。

如果能够很大比例地命中，就可以大幅度提高访问效率。

多级页表

多级页表顾名思义，类似于树的概念，一级一级往下查询，图示如下：比如图中是三级页表，逻辑地址的表示由四元组%!(EXTRA markdown.ResourceType=, string=, string=)

表示。p1、p2、p3 分别表示在各级页表中的偏移，o 则表示物理内存中的偏移。通过多级页表可以有效减少每级页表的长度。

具体操作中，比二级页表的操作如下：一级页表的起始地址存储在CPU寄存器CR3中，然后一级一级根据偏移获取实际内存地址。

优势：

1. 使用多级页表可以使得页表在内存中离散存储。多级页表实际上是增加了索引，有了索引就可以定位到具体的项。举个例子：比如虚拟地址空间大小为4G，每个页大小依然为4K，如果使用一级页表的话，共有2^20个页表项，如果每一个页表项占4B，那么存放所有页表项需要4M，为了能够随机访问，那么就需要连续4M的内存空间来存放所有的页表项。随着虚拟地址空间的增大，存放页表所需要的连续空间也会增大，在操作系统内存紧张或者内存碎片较多时，这无疑会带来额外的开销。但是如果使用多级页表，我们可以使用一页来存放页目录项，页表项存放在内存中的其他位置，不用保证页目录项和页表项连续。
   2。 使用多级页表可以节省页表内存。使用一级页表，需要连续的内存空间来存放所有的页表项。多级页表通过只为进程实际使用的那些虚拟地址内存区请求页表来减少内存使用量（出自《深入理解Linux内核》第三版51页）。举个例子：一个进程的虚拟地址空间是4GB，假如进程只使用4MB内存空间。对于一级页表，我们需要4M空间来存放这4GB虚拟地址空间对应的页表，然后可以找到进程真正使用的4M内存空间。也就是说，虽然进程实际上只使用了4MB的内存空间，但是为了访问它们我们需要为所有的虚拟地址空间建立页表。但是如果使用二级页表的话，一个页目录项可以定位4M内存空间，存放一个页目录项占4K，还需要一页用于存放进程使用的4M（4M=1024*4K，也就是用1024个页表项可以映射4M内存空间）内存空间对应的页表，总共需要4K（页表）+4K（页目录）=8K来存放进程使用的这4M内存空间对应页表和页目录项，这比使用一级页表节省了很多内存空间。当然，在这种情况下，使用多级页表确实是可以节省内存的。但是，我们需要注意另一种情况，如果进程的虚拟地址空间是4GB，而进程真正使用的内存也是4GB，如果是使用一级页表，则只需要4MB连续的内存空间存放页表，我们就可以寻址这4GB内存空间。而如果使用的是二级页表的话，我们需要4MB内存存放页表，还需要4KB内存来存放页目录项，此时多级页表反倒是多占用了内存空间。注意在大多数情况都是进程的4GB虚拟地址空间都是没有使用的，实际使用的都是小于4GB的，所以我们说多级页表可以节省页表内存。

劣势：

使用以及页表时，读取内存中一页内容需要2次访问内存，第一次是访问页表项，第二次是访问要读取的一页数据。但如果是使用二级页表的话，就需要3次访问内存了，第一次访问页目录项，第二次访问页表项，第三次访问要读取的一页数据。访存次数的增加也就意味着访问数据所花费的总时间增加。

反置页表

反置页表也是为了减少页表占用存储空间的一种做法。对于大地址空间系统，比如64位系统，多级页表变的非常繁琐，比如5级页表，正常情况下总共需要6次查询。并且逻辑地址空间的增长速度快于物理地址空间。每个进程有一个页表，随进程数量增加页表占用的存储空间也会增加。

针对上述情况，出现了页寄存器，页寄存器与反置页表思路相同：

• 不让页表与逻辑地址空间的大小相对应
• 让页表与物理地址空间的大小相对应

通过这个思路就可以使页表占用空间与进程数目没有关系，而至于物理内存的大小有关。

页寄存器

理解了页寄存器就可以轻松理解反置页表。

页寄存器将每个物理帧与与一个页寄存器关联，寄存器内存储以下内容：

• 使用位：此帧是否被进程占用
• 占用页号：对应的逻辑页号p
• 保护位：比如可读、可写等性质

由上面的内容我们可以看到页寄存器的优点是与逻辑地址空间大小无关，并且大小相对物理内存而言很小。

缺点是需要在页寄存器中存储页号，也就是帧号是键，页号是值，而进程运行时CPU产生的是逻辑地址页号，因此需要在页寄存器中搜索逻辑地址的页号。那么这种搜索是比较困难的。

实际操作中，采用hash将页号映射到帧号，提高检索效率。这样又产生一个问题就是hash冲突，出现冲突时遍历冲突链表，找到需要的帧号。同时还可以将快表的思想融入进来，缓存使用过的页号帧号映射。引入快表又引入了新的问题，快表存储在CPU缓存中容量被限制到很小，同时快表的功耗是很大的。

反置页表

反置页表也是基于hash映射查找页对应的帧，但是反置页表将进程号也考虑进来，对进程号和页号同时进行hash。这里我自己的理解是最初给进程分配帧的时候就是根据哈希值进行分配的，因此查找时自然可以根据哈希值进行查询。冲突解决方式依然是链表的方式解决，查询发现第一个地址内的进程号与页号与需要的进程号与页号不一致时则继续查询链表中的下一个节点。

过程如下图：哈希值加反置页表基址得到反置页表中的位置，验证进程号和页号，命中则根据hash结果查询物理内存。

具体实现看下图。pid和vpn（virtual page number）共同参与哈希，得到一个物理地址，根据这个地址去查询反置页表，验证pid和vpn是否匹配，不匹配则查询next中存储的地址，此时匹配，则访问此时对应的物理地址。

段页式存储

原理

页式存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享。如果将这两种存储管理方法结合起来，就形成了段页式存储管理方式。

在段页式系统中，作业的地址空间首先被分成若干个逻辑段，每段都有自己的段号，然后再将每一段分成若干个大小固定的页。对内存空间的管理仍然和分页存储管理一样，将其分成若干个和页面大小相同的存储块，对内存的分配以存储块为单位，如图所示：

在段页式系统中，作业的逻辑地址分为三部分：段号、页号和页内偏移量：

%!(EXTRA markdown.ResourceType=, string=, string=)

注意：在一个进程中，段表只有一个，而页表可能有多个。

在进行地址变换时，首先通过段表查到页表起始地址，然后通过页表找到页帧号，最后形成物理地址。如图所示，进行一次访问实际需要三次访问主存，这里同样可以使用快表以加快查找速度，其关键字由段号、页号组成，值是对应的页帧号和保护码。

优缺点

优点

1. 它提供了大量的虚拟存储空间。
2. 能有效地利用主存，为组织多道程序运行提供了方便。

缺点：

1. 增加了硬件成本、系统的复杂性和管理上的开消。
2. 存在着系统发生抖动的危险。
3. 存在着内碎片（页内的碎片）。
4. 还有各种表格要占用主存空间。