分页存储-快表、两级页表

一、内存的分配?

内存的分配方式主要包括连续分配和非连续分配。

1. 连续分配（Contiguous Allocation）：

   • 连续分配是指在内存中为一个程序或进程分配一块连续的内存空间。
   • 主要的连续分配方式有单一连续分配和分区连续分配。
     • 单一连续分配：整个内存空间只分给一个程序，适用于小型计算机系统。
     • 分区连续分配：将内存分为若干个固定大小的分区，每个分区可以分配给一个进程，适用于多道程序设计环境。

2. 非连续分配（Non-contiguous Allocation）：

   • 非连续分配是指为一个程序或进程分配的内存空间是不连续的，可以分散在内存中的不同位置。
   • 主要的非连续分配方式有分页和分段。
     • 分页：将内存划分为固定大小的页，程序也被划分为相同大小的页，这样可以将程序的不同页分配到内存的不同位置。这种方式可以减少内存碎片，提高内存利用率。
     • 分段：将程序划分为若干个逻辑段，每个段可以有不同的长度，并且可以独立地在内存中分配。这种方式更符合程序的逻辑结构，但可能引入外部碎片。

????????在现代操作系统中，常常采用多种组合的方式，例如在分页的基础上再结合分段，以充分发挥各种分配方式的优点，同时避免它们的缺点。这样可以更灵活地管理内存，提高系统的性能和资源利用率。

二、 分页存储

????????分页存储是一种计算机内存管理的技术，其中物理内存和程序的虚拟地址空间都被划分为固定大小的页（page）。这种方式使得程序的地址空间可以被划分为相等大小的块，而物理内存也按照相同大小的页来进行划分。每个页的大小通常是2的幂次方，例如4KB或8KB。

????????在分页存储中，操作系统负责将程序的虚拟地址空间映射到物理内存中的页。当程序访问某个虚拟地址时，操作系统通过页表（page table）查找，找到对应的物理页的地址，从而实现虚拟地址到物理地址的映射。如果访问的页不在内存中（发生缺页异常），则需要将相应的页从磁盘等外部存储加载到内存中。

分页存储的优势包括：

1. 简化内存管理： 将内存划分为固定大小的页，使得内存管理更为简单和高效。

2. 提高内存利用率： 可以更灵活地利用内存，避免内存碎片，因为分页存储可以更精确地分配和释放内存。

3. 实现虚拟内存： 分页存储为虚拟内存的实现提供了基础。虚拟内存使得程序可以使用比实际物理内存更大的地址空间，允许操作系统将不常用的页放置在磁盘上，从而提高系统的整体性能。

4. 支持多道程序设计： 多个程序可以并发执行，每个程序都被划分为一系列的页，通过操作系统的调度机制在处理器上交替执行。

?2.1 页表

页表（Page Table）是用于实现虚拟地址到物理地址映射的数据结构，它是计算机操作系统中分页存储管理的核心组成部分。当程序通过虚拟地址访问内存时，操作系统使用页表来确定对应的物理地址。

以下是页表的基本概念和工作原理：

1. 基本概念：

   • 页表项（Page Table Entry，PTE）： 页表的每个条目称为页表项，包含了虚拟地址和物理地址之间的映射信息。每个页表项记录了虚拟页号到物理页框号的映射关系，以及一些标志位，例如表示该页是否在内存中、是否可读写等信息。

   • 页目录（Page Directory）： 在一些架构中，页表可能会进一步组织成页目录，其中包含了指向页表的指针。这样的多级结构有助于更有效地管理大量的页表项。

2. 工作原理：

   • 当程序通过虚拟地址访问内存时，操作系统首先通过虚拟地址的高位（或多级页表的高层次）来查找页表。

   • 操作系统根据页表的内容找到对应的页表项，从而得知虚拟地址对应的物理页框号。

   • 如果该页已经在物理内存中，操作系统将虚拟地址转换为物理地址，程序就可以直接访问内存。如果页不在内存中，可能会触发缺页异常。

   • 缺页异常时，操作系统负责将缺失的页从磁盘或其他外部存储加载到内存中，并更新页表，然后重新执行引起缺页异常的指令。

3. 页表的实现方式：

   • 单级页表： 所有的页表项都在一个表中，适用于小型地址空间的系统。

   • 多级页表： 将页表组织成多个级别的结构，从而减小整个页表的大小，提高查找效率。x86架构中的Page Directory和Page Table就是一个两级页表的例子，而一些其他架构可能使用更多级别的页表。

   • 反向页表（Inverted Page Table）： 将物理地址映射到虚拟地址，而不是相反。这种方式适用于大型系统，但可能增加了查找的开销。

2.2 页号

????????在分页存储管理中，一个进程的地址空间被划分成许多固定大小的块，通常称为"页"（page）。为了能够在虚拟地址和物理地址之间建立映射关系，操作系统使用页号（Page Number）来标识一个页在进程的虚拟地址空间中的位置。

????????页号通常是一个整数值，表示进程地址空间中的第几页。虚拟地址通常由两部分组成：页号和页内偏移量（Offset）。通过将虚拟地址的页号与页表中的页表项进行匹配，操作系统可以确定对应的物理页框号，从而完成虚拟地址到物理地址的映射。

????????假设一个系统的页大小为4KB（4096字节），一个进程的虚拟地址空间被划分为许多4KB的页，每一页包含一个唯一的页号。当程序通过虚拟地址访问内存时，系统会根据页号查找页表，找到对应的物理页框号，然后再加上页内偏移量，得到最终的物理地址。

????????例如，对于虚拟地址0x00001234，如果页大小为4KB，那么页号为0x00001，而页内偏移量为0x234。系统会使用页号查找页表，找到对应的物理页框号，然后将物理页框号与页内偏移量相加，得到实际的物理地址。

????????页号的大小取决于虚拟地址空间的大小和系统的页大小。在不同的计算机架构和操作系统中，页号的位数可能会不同。

?三、快表（TLB)

????????TLB（Translation Lookaside Buffer）是一种用于提高虚拟地址到物理地址转换速度的高速缓存。在分页存储管理系统中，TLB主要用于缓存页表项，从而加速地址转换过程。

????????TLB通常是一块小而高速的存储器，位于CPU与内存之间。它存储了最近被访问的虚拟地址到物理地址的映射，以避免频繁地访问较慢的主存中的页表。TLB的大小通常比页表小得多，因为它只存储最常用的映射。

????????TLB的基本工作原理如下：

1. 虚拟地址转换： 当CPU执行程序时，访问的是虚拟地址。在进行虚拟地址到物理地址的转换时，系统首先检查TLB。

2. TLB命中： 如果TLB中包含了所需的虚拟地址到物理地址的映射，这被称为TLB命中。在这种情况下，可以直接从TLB中获取物理地址，而无需访问主存中的页表。

3. TLB未命中： 如果TLB中没有找到所需的映射，这被称为TLB未命中。此时，系统将从主存中的页表中获取相应的页表项，并将其加载到TLB中，以便将来的访问可以更快地完成。

4. 替换策略： 如果TLB已满，并且需要加载新的映射，就需要使用替换策略来确定要替换的现有映射。一些常见的替换策略包括最近最少使用（LRU）和先进先出（FIFO）。

????????TLB的存在加速了地址转换过程，提高了系统的整体性能。由于TLB只能缓存有限数量的映射，因此当程序访问的页面超过TLB的容量时，就可能发生TLB未命中，需要从主存中加载新的映射，导致一些额外的访存开销。因此，设计高效的TLB和合理的替换策略对系统性能至关重要。

?

?四、两级页表

1.1 一级页表存在问题：

问题一：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。

问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。

2.2 二级页表

????????二级页表是一种多级页表结构中的一种形式，用于更有效地管理虚拟内存。多级页表是一种组织页表的方式，将整个地址空间的映射信息分层存储，以减小页表的规模。

????????在多级页表中，每个层级都有一个页表，而每个页表项可能指向下一级的页表或最终的物理页框。二级页表就是指有两级的页表结构，通常由一个顶层页表和多个底层页表组成。

????????以下是二级页表的基本概念和工作原理：

1. 顶层页表： 最高级的页表被称为顶层页表。它的页表项指向底层页表，而不是直接指向物理页框。这样的设计使得顶层页表的规模相对较小，因为它只需要包含指向底层页表的指针。

2. 底层页表： 底层页表包含了更详细的映射信息。它的页表项通常直接指向物理页框，完成了虚拟地址到物理地址的映射。

3. 虚拟地址解析： 当程序访问虚拟地址时，操作系统首先使用虚拟地址的高位在顶层页表中查找，得到底层页表的地址。然后使用虚拟地址的中间位在底层页表中查找，最终得到物理页框的地址。

4. 减小页表规模： 二级页表的主要优势在于减小了顶层页表的规模。这对于大型地址空间非常有用，因为一级页表可能会变得非常大，而使用多级页表可以将大的页表分解为更小的部分。

5. 灵活性： 多级页表结构提供了更灵活的映射机制，允许操作系统更精确地管理内存，提高内存利用率。

????????在一些现代的计算机体系结构中，例如x86架构中的Intel 80386及后续版本，采用了两级页表结构。在这种情况下，顶层页表被称为页目录（Page Directory），底层页表被称为页表（Page Table）。

?