当前课程知识点:操作系统(RISC-V) > 第五讲 物理内存管理: 非连续内存分配 > 5.5 快表和多级页表 > 5.5 快表和多级页表
接下来我们讲快表和多级页表
那在刚才我们说
快表是利用缓存的机制
来减少对内存的访问
而多级页表 是通过间接引用的方式
来减少页表的长度
那么它们具体怎么做的呢
快表实际上就是把近期访问过的页表项
缓存到CPU里头
底下是我们在前面没有使用快表的时候
正常情况下 你获取物理页号的过程
逻辑页号在内存当中去查页表
找到物理页号 然后得到物理地址
那现在在这里缓存之后怎么办呢
我在CPU里头 加上一组关联存储器
关联存储器是什么呢
关联存储器是说我这里有一个key
我进来之后它可以并行的
同时查所有的这些表项
有匹配的 把匹配的找出来
那你说这里
原先在内存里访问一次你觉得费事
到这里来你访问这么多次
它就不费事吗
实际上在这里头呢
由于是在CPU里头
它的速度会很快
当然由于它的速度快 成本高 功耗大
所以这个地方不能做的很大
如果说匹配得上
那这时候呢它直接得到它的物理页号
也就相当于我逻辑页号作为key
找到它的物理页号
那我就得到你的物理页号
这就不需要到内存当中访问了
如果说在这里头你找的时候
因为你这里容量很小
肯定没有办法把整个页表
全部装到这个CPU里头去
好 那这些有不命中的
那不命中的时候呢
它就会从这儿
你得再去找内存当中的页表
这时候你只能是两次访问了
好 找到这个页表之后呢
我得到它的页帧号
同时我把这个内容
再缓存到CPU里的快表里头去
下次再访问这一页里的数据的时候
你就不必要再去访问内存了
好 如果说我们在这里头
99%的访问我都是在这个TLB里
快表里命中的
那只有一次1%
是要到物理内存当中去查页表的
这时我们的性能就能大幅度提高
这是快表的基本原理
好 接下来我们介绍多级页表
多级页表是通过间接引用
将页号分成若干级
比如说在这里头
我们原来的逻辑地址的格式
是页号加页内偏移
现在变成了三级页号
P1 P2 P3 然后再加上页内偏移
和它相对应的 我们的页表呢
也会因此而形成一个树状结构
比如说原来一张大的线性页表
我把它切成若干段
这切到段的个数呢
和你最后一级页表的宽度是一致的
然后它每一个子页表的起头呢
作为上一级页表的物理页号
填到上一级页表当中
在第二级的页表的宽度
和你第二级页号的宽度是一致的
然后再一个 第二级页表的起头
再作为第一级页表项的物理页号
那这时候它的项数
和你第一级页表的宽度是相一致的
在这种情况下
我们要访问相应的物理内存单元
那怎么访问呢
是从第一级查第二级 再查第三级
那这时候我们整个访问次数就是K+1
你这里是三级 那就是四次
具体的访问过程是这样的
第一级作为第一级页表的偏移
找到第二级页表上的起始
第二级页表项
再作为在第二级页表当中的偏移
加在一起找到第三级页表项的
起始页号 物理页号
然后这地方呢 这一页呢
每一页这些页表都是和页相对齐的
所以从这儿呢它就不再有页内偏移
好 然后从这儿找到
最后的 你要实际访问的
那个内存单元的物理页号
再加上最后一次物理内存的访问
那通过这种方式
我们可以有效地减少每一级页表的长度
那如果说 你是所有的页表项都存在的话
你用多级页表实际上对它的存储并没有减少
但实际上 我们实际运行的进程呢
多数并不会用到整个所有的页表
所有的内存地址空间 逻辑地址空间
在这种情况下
我们可以通过各级页表当中的存在位
把那些不存在的给省掉
如果说我在第一级页表里头
有一个下一块区域都不存在的话
那么这样一来
我节省出来的空间就会大幅度增加
我使用的空间就会大幅度减少
好 用这种方式呢
实际上我们使用多级页表呢
可以有效地的减少页表的大小
下面我们通过一个简单的
但是更具体的例子 二级页表
我们看它是怎么做的
这儿呢我们把20位的地址总线
把它切成了三段
0到10 1K
10位作为页内偏移
然后前面切成两个五位的页号
第一级和第二级
那在实际访问的时候是什么样
这是这里头第一级
那第一级页表的起头在哪呢
它是写到固定寄存器里的
在因特尔的CPU上
有一个叫CR3的寄存器
好 在这个寄存器里头存的起始位置
加上你的第一级的页号
作为它的索引 下标
找到相应的页表项
这是第二级页表的起始页号
好 那第二级页表呢
你找这个起始位置
加上第二级的页表号
把它俩找到你的实际的物理页号
那这时候把偏移直接搬过来
那就得到你的物理地址了
有了这样一种做法呢
我们就可以很方便地
利用多级页表减少你整个页表的长度
-1.1 课程概述
--课程概述
-1.2 教学安排
--视频
-1.3 什么是操作系统
--Video
-1.4 为什么学习操作系统,如何学习操作系统
--Video
-1.5 操作系统实例
--视频
-1.6 操作系统的演变
--视频
-1.7 操作系统结构
--视频
-1.8 OS实验概述
--视频
-2.1 从OS角度看计算机系统
-2.2 从OS角度看RISC-V
-2.3 Rust语言与系统编程
-2.4 RISC-V CPU启动
-2.5 RISC-V CPU启动进一步分析
-3.1 基本概念与原理
-3.2 硬件架构支持
-3.3 中断处理机制
-3.4 系统调用
--3.4 系统调用
-4.1 计算机体系结构和内存层次
-4.2 地址空间和地址生成
-4.3 连续内存分配
-4.4 碎片整理
--4.4 碎片整理
-4.5 伙伴系统
--4.5 伙伴系统
-4.6 SLAB分配器
-5.1 非连续内存分配的需求背景
-5.2 段式存储管理
-- 5.2 段式存储管理
-5.3 页式存储管理
-5.4 页表概述
--5.4 页表概述
-5.5 快表和多级页表
-5.6 RISC-V页映射机制
-5.7 使能RISC-V页表
-6.1 虚拟存储的需求背景
-6.2 覆盖和交换
-6.3 局部性原理
-6.4 虚拟存储概念
-6.5 虚拟页式存储
-6.6 缺页异常
--6.6 缺页异常
-6.7 RISC-V缺页异常
-7.1 页面置换算法的概念
-7.2 最优算法、先进先出算法和最近最久未使用算法
-7.3 时钟置换算法和最不常用算法
-7.4 Belady现象和局部置换算法比较
-7.5 页表自映射
-8.1 工作集置换算法
-8.2 缺页率置换算法
-8.3 抖动和负载控制
-8.4 面向缓存的页替换算法
-9.1 进程的概念
-9.2 进程控制块
-9.3 进程状态
--9.3 进程状态
-9.4 三状态进程模型
-9.5 挂起进程模型
-9.6 线程的概念
-9.7 用户线程
--9.7 用户线程
-9.8 内核线程
--9.8 内核线程
-9.9 进程地址空间与熔断 (meltdown) 漏洞
-10.1 进程切换
-10.2 进程创建
-10.3 进程加载
-10.4 进程等待与退出
-10.5 rCore进程和线程控制
-11.1 处理机调度概念
-11.2 调度准则
-11.3 先来先服务、短进程优先和最高响应比优先调度算法
--11.3 先来先服务、短进程优先和最高响应比优先调度算法
-11.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
--11.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
-11.5 实时调度
-11.6 优先级反置
-11.7 rCore调度框架
-12.1 对称多处理与多核架构
-12.2 多处理器调度概述
-12.3 O(1)调度
-12.4 CFS调度
-12.5 BFS调度算法
-13.1 背景
--13.1 背景
-13.2 现实生活中的同步问题
-13.3 临界区和禁用硬件中断同步方法
-13.4 基于软件的同步方法
-13.5 高级抽象的同步方法
-14.1 信号量
--14.1 信号量
-14.2 信号量使用
-14.3 管程
--14.3 管程
-14.4 哲学家就餐问题
-14.5 读者-写者问题
-14.6 Rust语言中的同步机制
-15.1 死锁概念
-15.2 死锁处理方法
-15.3 银行家算法
-15.4 死锁检测
-15.5 并发错误检测
-16.1 进程通信概念
-16.2 信号和管道
-16.3 Linux信号机制
-16.4 消息队列和共享内存
-16.5 D-Bus机制
-16.6 Binder机制
-17.1 文件系统和文件
-17.2 文件描述符
-17.3 目录、文件别名和文件系统种类
-17.4 虚拟文件系统
-17.5 文件缓存和打开文件
-17.6 文件分配
-17.7 空闲空间管理和冗余磁盘阵列RAID
-18.1 FAT文件系统
-18.2.1 EXT4文件系统-历史
-18.2.2 EXT4文件系统-支持大容量存储
-18.2.3 EXT4文件系统-支持恢复异常
-18.3 ZFS文件系统
-19.1 I/O特点
-19.2 I/O结构
-19.3 I/O数据传输
-19.4 磁盘调度
-19.5 Linux I/O子系统
-20.1 Linux内核错误分析
-20.2.1 用rust写操作系统-系统编程语言rust
--20.2.1 用rust写操作系统-系统编程语言rust
-20.2.2 用rust写操作系统-rust与操作系统开发
--20.2.2 用rust写操作系统-rust与操作系统开发
-21.1 Background
-21.2 Futures in Rust
-21.3 Generators and async/await
--21.3 Generators and async/await
-21.4 Self-Referential Structs & Pin
--21.4 Self-Referential Structs & Pin
-21.5 Waker and Reactor
-22.1 Overview
-22.2.1 How VMM works - CPU
-22.2.2 How VMM works - memory & I/O