计算机操作系统中的基本分页存储管理

计算机操作系统中的基本分页存储管理

引用

CSDN

1.

https://m.blog.csdn.net/m0_74209563/article/details/141335406

分页存储管理是计算机操作系统中一种重要的内存管理方式，它通过将主存空间和进程的逻辑地址空间划分为固定大小的页面，实现内存的高效利用和管理。本文将详细介绍分页存储管理的基本概念、页表结构、地址转换机制以及快表（TLB）和两级页表等高级优化技术。

基本分页存储管理

非连续分配：为用户进程分配的可以是一些分散的内存空间。

分页存储的概念

固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免碎片的产生，这就引入了分页的思想：

把主存空间划分为大小相等且固定的分区，每个分区相对较小，作为主存的基本单位

每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间

内存空间被分为一个个大小相等的分区，每个分区就是一个“页框”，每个页框有一个编号，即“页框号”，页框号从0开始

(页框=页帧=内存块=物理块=物理页面)

(页框号=页帧号=内存块号=物理块号=物理页号)

为了把各个进程的数据存放到各个页框中，操作系统会将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分成为一个 ”页“ 或 ”页面“ ，每个页面也有一个编号，即 ”页号“ ，页号也是从 0 开始

操作系统以页框为单位为各个进程分配内存空间，进程的每个页面分别放入一个页框中，也就是说，进程的页面与内存的页框有一一对应的关系

各个页面不必连续存放，可以放到不相邻的各个页框中

重要的数据结构——页表

页表是一个存储在内存中的数据结构，用于将逻辑地址中的页号映射到物理内存中的页框号

为了能知道进程的每个页面在内存中存放的位置（实现逻辑地址到物理地址的转换），操作系统要为每个进程建立一张页表（页表通常存在PCB(进程控制块)中）

1. 一个进程对应一张页表
2. 进程的每个页面对应一个页表项
3. 每个页表项由 “页号” 和 “块号” 组成
   （注意：页表记录的只是内存块号，而不是内存块的起始地址，物理页面的起始地址=物理页框号×页大小）
4. 页表记录进程页面和实际存放的内存块(页框) 之间的映射关系

页表项大小计算

页表项占用字节大小 = 页号占用字节 + 块号占用字节，但是由于页表项是连续存放，因此页号可以是隐含的，不占存储空间（类比数组），故在物理上页表项占用的存储空间大小就是块号占用的存储空间大小

下面介绍如何计算每个页表项占用字节大小

【例】假设某系统物理内存大小为 4GB，页面大小为 4KB，则每个页表项至少应该为多少字节？

【解】内存块大小 = 页面大小 = 4KB = 2¹²B

➡️ 4GB 的内存总共会被分为 2³²/2¹² = 2²⁰ 个内存块

➡️ 内存块号的范围应该是 0 ~ 2²⁰-1

➡️ 内存块号至少要用 20bits 来表示

➡️ 至少要用 3B 来表示块号（3*8=24bits）

➡️ 由于页号是隐含的，因此每个页表占 3B，若页表有n个页表项，那么存储整个页表至少需要 3*(n+1)B

地址转换实现

之前介绍过进程在内存中连续存放时，操作系统是通过三种装入方式实现逻辑地址和物理地址之间的转换的，接下来介绍将进程地址空间分页之后，操作系统是如何实现逻辑地址到物理地址的转换的

分页存储的特点：虽然进程的各个页面是离散存放的，但是页面内部是连续存放的

如果要访问逻辑地址 A，则：

① 确定逻辑地址 A 对应的 “页号” P

② 找到 P 号页面在内存中的起始地址(需要查页表，物理页面的起始地址=物理页框号×页大小)

③ 确定逻辑地址A的 “页内偏移量” W

逻辑地址A对应的物理地址 = P号页面在内存中的起始地址 + 页内偏移量W

【例】在某计算机系统中，页面大小是 50B，某进程逻辑地址空间大小为 200B，则逻辑地址 110 对应的页号、页内偏移量是多少?

用二进制表示逻辑地址：

由于在计算机内部，地址是用二进制表示的，如果页面大小刚好是2 的整数幂，则计算机硬件可以很快速的把逻辑地址拆分为（页号，页内偏移量）

逻辑地址通常由两个部分组成：

• 页号（Page Number, PN）：逻辑地址的高位部分，用于索引页表，确定该逻辑地址对应的页在物理内存中的位置。
• 页内偏移（Page Offset, PO）：逻辑地址的低位部分，表示在该页内的具体偏移量

重点：知道页面大小就能知道页内偏移量位数，知道页内偏移量位数也能知道页面大小，就可以推出逻辑地址结构

【例】某计算机用 32 个二进制位表示逻辑地址，页面大小为 4KB = 2¹²B = 4096B

可以发现：后 12 位表示的就是页内偏移量，前 20 位表示的就是页号

再用两道例题理解一下

结论：如果每个页面大小为2 K B 2^KB2KB，用二进制数表示逻辑地址，则末尾 K 位即为页内偏移量，其余部分就是页号

用二进制表示物理地址：

结论：如果页面大小刚好是2 的整数幂，则只需要把页表中记录的物理块号拼接上页内偏移量就能得到对应的物理地址，如果不是2 的整数幂，那么就需要使用物理页面的起始地址=物理页框号×页大小的公式进行计算

基本地址变换机构

重点掌握基本地址变换机构的原理和流程

基本地址变换机构是借助进程的页表将逻辑地址转换为内存中的物理地址的一组硬件机构

通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始位置F和页表长度M

进程未执行时，页表的起始位置和页表长度放在进程控制块（PCB）中

当进程被调度时，操作系统内核会把他们放到页表寄存器中

注意：页面大小是 2 的整数幂

设页面大小为L，逻辑地址A到物理地址E的变换过程如下：

【分析】

① 计算 页号P 和 页内偏移量W (如果用十进制数手算，则 P=A/L ，W=A%L ；但是在计算机实际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量)

② 比较 页号P 和 页表长度M ，若P≥M，则产生越界中断，否则继续执行 (注意：页号是从 0 开始的，而页表长度至少是 1，因此P=M 时也会越界)

③ 页表中 页号P 对应的页表项地址 = 页表起始地址F + 页号P * 页表项长度，取出该页表项内容b，即为内存块号 (注意区分页表项长度、页表长度、页面大小的区别：页表长度指的是这个页表中总共有几个页表项，即总共有几个页；页表项长度指的是每个页表项占多大的存储空间；页面大小指的是一个页面占多大的存储空间)

④ 计算E=b*L+W，用得到的 物理地址E 去访存 (如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址了)

【例】

在分页存储管理(页式管理)的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了

因此，页式管理中地址是一维的，即只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统这个逻辑地址中，页内偏移量占多少位

具有快表的地址变换机构

具有快表的地址变换机构是基本地址变换机构的改进版本

快表（TLB）的概念

由上面介绍的地址变换过程可知，若页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存：

第一次是访问页表，确定所存取的数据或指令的物理地址；

第二次是根据该地址存取数据或指令，

显然，这种方法比通常执行指令的速度慢了一半

为此，在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器一一快表，又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓存（TBL不是内存!），用来存放最近访问的页表项的副本，可以加速地址变换的过程

与此对应，主存中的页表常称为慢表

【寄存器、高速缓存、内存、外存之间的关系】

引入快表后的地址变换

【分析】

① CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较

② 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后访问该物理地址对应的内存单元，因此若快表命中，则访问某个逻辑地址仅需一次访存即可

③ 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元，因此若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表，以便后面可能的再次访问，但若快表已满，则必须按照一定的算法对旧的页表项进行替换）

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间

因为局部性原理，一般来说快表的命中率可以达到90%以上

局部性原理

时间局部性

如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行

如果某个数据被访问过，不久之后该数据很可能再次被访问

(因为程序中存在大量的循环)

空间局部性

一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问

(因为很多数据在内存中都是连续存放的)

在基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表项，这就是为什么快表的命中率可以达到90%以上

两级页表

单级页表 vs 两级页表

【计算机操作系统】 专栏的文章 均有参考《王道计算机考研 操作系统》课程视频