当前课程知识点：操作系统 > 第六讲 物理内存管理: 非连续内存分配 > 6.6 反置页表 > 6.6 反置页表
下面我们来介绍反置页表
反置页表也是一种
为了减少页表所占用
存储空间的一种做法
那它是怎么做的呢
提出反置页表的原因
还是说我们多级页表
它访问存储空间的次数比较多
然后特别是在大地址空间的情况下
那这时候呢
由于大地址空间和多级页表
它和逻辑地址空间
的大小呢有对应关系
每一个逻辑页面
都会对应着页表项的一项
那这样的话我的进程数目的增加
都会导致你页表的数目
占用的空间增大
好 针对这种情况呢
反置页表和页寄存器
是两个类似的做法
那它们在这里头做法是
让页表项和物理地址空间
的大小相对应起来
而不是说像多级页表里
和逻辑地址空间相对应起来
那这样的话 你的进程数目的增加
和虚拟地址空间的增大
都对这页表占用的空间没有影响
下面我们来讨论页寄存器的实现
那么在页寄存器里头呢
它是把每一个物理帧
和一个页寄存器相对应
那在这个寄存器里头
存的内容有些啥呢
一个是 这个物理帧
是否被某一个进程占用
这是使用位
第二个就是页号 占用页号
那么在这个
占用页号相当于
我一个进程占用了这一页
它的逻辑页号是多少
那我在这里头给它保存
那这样的话我就知道
这个物理帧它分配给了哪一个进程
它的逻辑地址是多少
另外还有一个保护位
是来约定这一页的访问方式
你比如说可读 可写
有了这样一种对应关系之后
我们看它占用的存储的情况
在这儿通过一个例子来说明
在这个例子当中呢
它整个系统里有16M的物理内存
然后页面大小呢是4K
那这时候呢16M 4K
那这时候呢我有4096个页面
好 那这4096个页面
它的页寄存器占多大呢
那在这儿是说 假定
每一个页寄存器占8字节
那4096乘8是32K字节
那这32K字节
和16M物理内存比较起来呢
占到的比例是0.2%
那这个比例相对来说还是比较小的
那这时候 它和虚拟内存的大小
就没有关系了
那这时候我在里创建多少个进程
它只是每一个物理页面
和一个页寄存器相对应
那这是它占用存储的情况
那具体说起来这样的话
这种方法它的好处是说
我跟物理内存相比较起来
它占用的空间比较小
而且和逻辑地址空间没关系
但是它也有很大的麻烦
它的麻烦是什么
在多级页表里头
我们这个信息查询呢
我是从逻辑页号到物理页号
利用下标查里头的内容
我就可以找到它的页帧号
而现在呢我排序的办法呢是页帧号
我要从 找的是里头的逻辑页号
是否是我想找的那个
那这样的话
就要在页寄存器里头进行搜索
那这个搜索是会比较困难的
下面我们来讨论
页寄存器机制的地址转换
CPU生成的是逻辑地址
那在页寄存器机制下
它所对应的物理地址是多少呢
那么这个多少呢
是把逻辑地址做Hash
Hash的原因是这样
我可以减少搜索范围
然后呢如果说有冲突
Hash之后的值 它可能是
两个不同的逻辑地址
对应到同一个Hash值上
那这种情况下Hash值相同
那这时候我就会产生冲突
这种冲突是需要解决的
好 这时候呢
我们可以利用快表来和
这个页寄存器机制搁到一起来用
那么这时候的做法什么呢
逻辑地址进行Hash
然后在快表当中去查找相应的页表项
如果说查找的过程当中出现冲突
这时 我就需要遍历所有的冲突链表
好 如果说查找不到
那么这时候呢它就会出现异常
好 那么在这里头
它也有一个问题
和我们前面的快表是一样的
由于快表它的容量有限
这时候呢快表的功耗又很大
这对于我们页寄存器机制
还是有很大影响的
比如说在这里说到StrongARM上的
快表的功耗占到27%
这是不可以忽视的
好 接下来我们说反置页表
反置页表和页寄存器的做法的区别是
在于它把进程ID也考虑进来了
那它和页寄存器做法一样的
它需要进行Hash
不同的地方是把进程标识
也加在里头一块做Hash
Hash完的结果呢也可能会有冲突
那也需要解决冲突
那Hash完的结果呢
它是以页帧号来作为排序的
那我在这儿找到的结果是说
我需要到相应的页表项里去核对
Hash之前的结果和之后的
里头的进程ID和逻辑号是否一致
如果一致呢这就是我要找的那一项
我就可以得到相应的物理页号了
如果不一样
那这时候呢它就会产生冲突
那么对于冲突情况呢
我们以这个例子来说
一个逻辑地址加上它的进程ID
那我首先做Hash
Hash完的结果是在这儿
到相应的反置页表当中进行查找
看进程ID和逻辑页号
是不是跟Hash之前的一样
如果不一样那就是说明有冲突
这时候告诉你下一项在哪
这地方是有冲突
好 告诉你下一项
然后我再到下一项里头进行核对
这时候呢这两者跟那儿是一样的
好 那么这时候呢
我要找这个地方
它的序号就是我的页帧号，
好 页帧号和页内偏移合到一起
那就得到它的物理页号和页内偏移
那到目前为止呢我们介绍了三种做法
来缓解或者是解决页表所带来的麻烦
一种是快表 它是通过缓存的机制
来减少对物理内存 对页表的访问
第二种是多级页表
多级页表的做法呢
通过多级来减少页表的大小
反置页表是另一种减少页表大小的做法
这几种做法呢都可以有效的解决
或者是缓解我们引入页表所带来的麻烦
那在这些麻烦解决掉之后
我们现在用到计算机
都是采用这种页表的机制来进行转换的
那这是呢 我们说到的这个页存储机制
-0.1 Piazza讨论区
--html
-0.2 在线实验平台
--实验平台使用帮助
--平台使用帮助
-0.2在线实验平台
--Raw HTML
-1.1 课程概述
--视频
-第一讲 操作系统概述--练习
-1.2 教学安排
--视频
-1.3 什么是操作系统
--Video
-1.4 为什么学习操作系统，如何学习操作系统
--Video
-1.5 操作系统实例
--视频
-1.6 操作系统的演变
--视频
-1.7 操作系统结构
--视频
-2.1 前言和国内外现状
-2.2 OS实验目标
-2.3 8个OS实验概述
-2.4 实验环境搭建
-2.5 x86-32硬件介绍
-2.6 ucore部分编程技巧
-2.7 演示实验操作过程
--Q6
--Q7
--Q10
-3.1 BIOS
--3.1 BIOS
-3.2 系统启动流程
-3.3 中断、异常和系统调用比较
-第三讲 启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较
-3.4 系统调用
--3.4 系统调用
-第三讲 启动、中断、异常和系统调用--3.4 系统调用
-3.5 系统调用示例
-3.6 ucore+系统调用代码
-4.1 启动顺序
--4.1 启动顺序
-4.2 C函数调用的实现
-4.3 GCC内联汇编
-4.4 x86中断处理过程
-4.5 练习一
--4.5 练习一
-4.6 练习二
--4.6 练习二
-4.7 练习三
--4.7 练习三
-4.8 练习四 练习五
-4.9 练习六
--4.9 练习六
-5.1 计算机体系结构和内存层次
-5.2 地址空间和地址生成
-5.3 连续内存分配
-5.4 碎片整理
--5.4 碎片整理
-5.5 伙伴系统
--5.5 伙伴系统
-第五讲 物理内存管理: 连续内存分配--5.6 练习
-6.1 非连续内存分配的需求背景
-6.2 段式存储管理
-- 6.2 段式存储管理
-6.3 页式存储管理
-6.4 页表概述
--6.4 页表概述
-6.5 快表和多级页表
-6.6 反置页表
--6.6 反置页表
-6.7 段页式存储管理
-第六讲 物理内存管理: 非连续内存分配--6.8 练习
-7.1 了解x86保护模式中的特权级
-第七讲 实验二 物理内存管理--7.1 了解x86保护模式中的特权级
-7.2 了解特权级切换过程
-第七讲 实验二 物理内存管理--7.2 了解特权级切换过程
-7.3 了解段/页表
-第七讲 实验二 物理内存管理--7.3 了解段/页表
-7.4 了解UCORE建立段/页表
-第七讲 实验二 物理内存管理--7.4 了解UCORE建立段/页表
-7.5 演示lab2实验环节
-8.1 虚拟存储的需求背景
-8.2 覆盖和交换
-8.3 局部性原理
-8.4 虚拟存储概念
-8.5 虚拟页式存储
-8.6 缺页异常
--8.6 缺页异常
-9.1 页面置换算法的概念
-9.2 最优算法、先进先出算法和最近最久未使用算法
-第九讲 页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法
-9.3 时钟置换算法和最不常用算法
-第九讲 页面置换算法--9.3 时钟置换算法和最不常用算法
-9.4 Belady现象和局部置换算法比较
-第九讲 页面置换算法--9.4 Belady现象和局部置换算法比较
-9.5 工作集置换算法
-第九讲 页面置换算法--9.5 工作集置换算法
-9.6 缺页率置换算法
-第九讲 页面置换算法--9.6 缺页率置换算法
-9.7 抖动和负载控制
-10.1 实验目标：虚存管理
-第十讲 实验三 虚拟内存管理--10.1 实验目标：虚存管理
-10.2 回顾历史和了解当下
-第十讲 实验三 虚拟内存管理--10.2 回顾历史和了解当下
-10.3 处理流程、关键数据结构和功能
-第十讲 实验三 虚拟内存管理--10.3 处理流程、关键数据结构和功能
-10.4 页访问异常
-第十讲 实验三 虚拟内存管理--10.4 页访问异常
-10.5 页换入换出机制
-第十讲 实验三 虚拟内存管理--10.5 页换入换出机制
-11.1 进程的概念
-第十一讲 进程和线程--11.1 进程的概念
-11.2 进程控制块
-第十一讲 进程和线程--11.2 进程控制块
-11.3 进程状态
-第十一讲 进程和线程--11.3 进程状态
-11.4 三状态进程模型
-11.5 挂起进程模型
-第十一讲 进程和线程--11.5 挂起进程模型
-11.6 线程的概念
-第十一讲 进程和线程--11.6 线程的概念
-11.7 用户线程
-第十一讲 进程和线程--11.7 用户线程
-11.8 内核线程
-第十一讲 进程和线程--11.8 内核线程
-12.1 进程切换
-第十二讲 进程控制--12.1 进程切换
-12.2 进程创建
-第十二讲 进程控制--12.2 进程创建
-12.3 进程加载
-第十二讲 进程控制--12.3 进程加载
-12.4 进程等待与退出
-第十二讲 进程控制--12.4 进程等待与退出
-13.1 总体介绍
-13.2 关键数据结构
-13.3 执行流程
-13.4 实际操作
-14.1 总体介绍
-14.2 进程的内存布局
-14.3 执行ELF格式的二进制代码-do_execve的实现
--14.3 执行ELF格式的二进制代码-do_execve的实现
-14.4 执行ELF格式的二进制代码-load_icode的实现
--14.4 执行ELF格式的二进制代码-load_icode的实现
-14.5 进程复制
-14.6 内存管理的copy-on-write机制
-15.1 处理机调度概念
-第十五讲 处理机调度--15.1 处理机调度概念
-15.2 调度准则
-15.3 先来先服务、短进程优先和最高响应比优先调度算法
--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-第十五讲 处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
-第十五讲 处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc
-15.5 实时调度和多处理器调度
-第十五讲 处理机调度--15.5 实时调度和多处理器调度
-15.6 优先级反置
-第十五讲 处理机调度--15.6 优先级反置
-16.1 总体介绍和调度过程
-16.2 调度算法支撑框架
-16.3 时间片轮转调度算法
-16.4 Stride调度算法
-17.1 背景
--17.1 背景
-17.2 现实生活中的同步问题
-第十七讲 同步互斥--17.2 现实生活中的同步问题
-17.3 临界区和禁用硬件中断同步方法
-第十七讲 同步互斥--17.3 临界区和禁用硬件中断同步方法
-17.4 基于软件的同步方法
-第十七讲 同步互斥--17.4 基于软件的同步方法
-17.5 高级抽象的同步方法
-第十七讲 同步互斥--17.5 高级抽象的同步方法
-18.1 信号量
--18.1 信号量
-第十八讲 信号量与管程--18.1 信号量
-18.2 信号量使用
-第十八讲 信号量与管程--18.2 信号量使用
-18.3 管程
--18.3 管程
-第十八讲 信号量与管程--18.3 管程
-18.4 哲学家就餐问题
-18.5 读者-写者问题
-19.1 总体介绍
-19.2 底层支撑
-第十九讲 实验七 同步互斥--19.2 底层支撑
-19.3 信号量设计实现
-第十九讲 实验七 同步互斥--19.3 信号量设计实现
-19.4 管程和条件变量设计实现
-第十九讲 实验七 同步互斥--19.4 管程和条件变量设计实现
-19.5 哲学家就餐问题
-20.1 死锁概念
-第二十讲 死锁和进程通信--20.1 死锁概念
-20.2 死锁处理方法
-第二十讲 死锁和进程通信--20.2 死锁处理方法
-20.3 银行家算法
-第二十讲 死锁和进程通信--20.3 银行家算法
-20.4 死锁检测
-第二十讲 死锁和进程通信--20.4 死锁检测
-20.5 进程通信概念
-第二十讲 死锁和进程通信--20.5 进程通信概念
-20.6 信号和管道
-第二十讲 死锁和进程通信--20.6 信号和管道
-20.7 消息队列和共享内存
-第二十讲 死锁和进程通信--20.7 消息队列和共享内存
-21.1 文件系统和文件
-第二十一讲 文件系统--21.1 文件系统和文件
-21.2 文件描述符
-第二十一讲 文件系统--21.2 文件描述符
-21.3 目录、文件别名和文件系统种类
-第二十一讲 文件系统--21.3 目录、文件别名和文件系统种类
-21.4 虚拟文件系统
-第二十一讲 文件系统--21.4 虚拟文件系统
-21.5 文件缓存和打开文件
-第二十一讲 文件系统--21.5 文件缓存和打开文件
-21.6 文件分配
-第二十一讲 文件系统--21.6 文件分配
-21.7 空闲空间管理和冗余磁盘阵列RAID
-第二十一讲 文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID
-22.1 总体介绍
-第二十二讲 实验八 文件系统--22.1 总体介绍
-22.2 ucore 文件系统架构
-第二十二讲 实验八 文件系统--22.2 ucore 文件系统架构
-22.3 Simple File System分析
-第二十二讲 实验八 文件系统--22.3 Simple File System分析
-22.4 Virtual File System分析
-第二十二讲 实验八 文件系统--22.4 Virtual File System分
-22.5 I/O设备接口分析
-第二十二讲 实验八 文件系统--22.5 I/O设备接口分析
-22.6 执行流程分析
-23.1 I/O特点
--视频
-第二十三讲 I/O子系统--23.1 I/O特点
-23.2 I/O结构
--816C80A0F5E3B8809C33DC5901307461
-第二十三讲 I/O子系统--23.2 I/O结构
-23.3 I/O数据传输
--C58221E14388B9DB9C33DC5901307461
-第二十三讲 I/O子系统--23.3 I/O数据传输
-23.4 磁盘调度
--567A3F1FCBFB3F4C9C33DC5901307461
-第二十三讲 I/O子系统--23.4 磁盘调度
-23.5 磁盘缓存
--C327536B80D25CE79C33DC5901307461
-第二十三讲 I/O子系统--23.5 磁盘缓存
-html
--html
