我们前面讲了这个
页异常要干的事情
我们再看看 我们重点考虑说
我们要实现页替换算法了
因为在do_pgfault里面
还是把这个整个机制给实现完毕
但是你要完成这个页替换算法
那你还需要考虑一些问题
对于我们原理课讲的时候
比较简单一点是说
我们根据某种策略来选择某一个页
把它换出去 到这儿ok了
那落到我们具体的
操作系统里面呢
你会去考虑以下一些问题
第一个问题应该换出哪个页
那么这个应该换出
这是一个策略问题 那实际上
是和我们页替换算法是紧密相连的
但是在做这一步的时候
你还需要考虑很多问题
比如说你怎么来建立虚拟页
和磁盘扇区的对应关系
我前面说到了
知道一个页出错了
那么怎么知道它在硬盘什么地方
你要把这个对应关系给建立起来
你还需要什么呢
还需要知道何时进行换入换出
是主动地要把一些页换出去
还是说是被动地
产生了内存不够之后
才开始换入换出的这个操作
这是换入换出操作的一个实际问题
以及你要设计什么样的数据结构
来支持页替换算法
这一点很重要的
就是我们希望大家在做实验的时候
就可以设计不同的页替换算法
但是呢对我们上层OS
其它部分的实现呢没有影响
这里面就用到了
我们在lab0里面讲到的
要设计一套函数指针的一个链表
只要把这些函数实现完之后
它接口没变
虽然它的实现可以有千变万化的
一些不同的算法实现
但是它接口不变
从而可以灵活地通过ucore
来实现不同的页替换算法
所以要设计一个比较通用的
抽象度比较高的一个数据结构
来支持我们不同类型的页替换算法
这一块已经做好了
大家可以在这基础之上
来完成我们说的
我们的实验需要FIFO这个页替换算法
最后怎么来进行页面的换入换出
其实就是说你要去完成这个读写
对disk读写 这是说你要能够实现
让这个页替换算法
能够在这个ucore里面正常工作
需要考虑的一系列问题
我们可以逐一去解决
第一个问题就是
你要考虑你那个页替换的算法
这个页替换算法它的一个框架
实现在swap.c里面
你看swap.c和swap.h
那么这里面定义了一个数据结构
一个函数指针的列表
这里面是相当于
把页替换框架给实现了
那内核其它部分呢
只需要用框架里面的函数就OK了
那具体的页替换的算法的
具体的实现呢
可以放在另外一个地方
比如说对我们这个实验来说
可以写一个文件叫
swap_fifo.c和swap_fifo.h
在这里面填写你的算法
这些算法的名字是和我们swap.c里面
swap_manager定义的函数指针
是一致就OK了
这是说你要在哪实现这些问题
然后假设实现好之后呢
我们会有一套检测机制check_swap
来看你这个实现是否对
就是说你那个语义
FIFO那个语义就是我们页替换算法
那个语义能否正确的完成
我们这儿有一个check
好 另一方面呢
我们也提到你怎么去建立虚拟页
和磁盘扇区的对应关系
我怎么知道一个页和一个disk
到底什么样的关系
这个关系怎么建立 大家想一想
放在哪建立比较合适
其实我们这里呢用到了什么呢
用到了swap_entry_t
来代表这么一个对应关系的一个建立
比如说这里面它有一个24个bit
这个offset来代表磁盘扇区的一个编号
那磁盘扇区的编号可以用这个来表示
那虚拟页的编号在哪表示呢
其实很简单 它和我们的页表是一样的
靠那个页表里面的index 来表示虚拟页号
那既然用页表里面的index
来表示虚拟页号 那也意味着我们可以
把这个磁盘扇区这个offset
其实可以写到页表项里面去
那页表项其实多了一个功能
我们以前说页表项完成了什么呢
完成的是虚拟页和物理页帧的
一个对应关系
是放在我们这个页表项里面的
那一旦说我们把这个页表项
换了一个功能
它是虚拟页和我们磁盘扇区的
一个对应关系也可以放这里面
那怎么能够保证一个页表项
同时具有两个功能呢
其实同时是不可能的
只能是在不同情况下它有不同的含义
什么情况呢
如果它那个present位这就需要知道
我们页表项里面有一系列的bit
这个bit有特定的含义
比如它有个P位叫present位
这个位如果是0
代表这个映射关系没有
也意味着不存在一个虚拟页
和一个物理页帧的对应关系
因为它的present位是0
既然在这种情况下
我们不需要去用这个页表项来表示
表示这个虚拟页
和物理页帧的对应关系
那我们可以用这个表项来表示什么呢
虚拟页和我们的硬盘扇区的对应关系
其实这是 正好是根据这个bit的
0和1来区分它到底表示什么含义的
那同时我们节省了空间
这种方式就可以有效地来完成
虚拟页和磁盘扇区对应关系的一个建立
那我们知道swap_entry_t它的一个结构之后
我们可以进一步了解到
这个每一个swap_entry_t是表明了
一个虚拟页和一个所谓的这个
我们的磁盘的扇区的一个映射关系
那这地方是放在哪呢 是放在PTE里面的
那我们要用好这个宏 swap_offset之后
就可以有效地从一个PTE里面
PTE是什么呢 Page Table Entry
就是页表项
从页表项里面把对应的那个
swap_entry_t取出来
从而可以知道我们这个硬盘扇区
的位置在什么地方
它的一个索引值就知道了
从而可以正确完成
对这个硬盘数据的读或者写操作
那我们其实可以进一步扩展开来
我们页替换算法其实还有很多种
我们讲原理课的时候除了FIFO之外
还讲了clock算法enhanced clock算法等等
那其实基于我们刚才讲的这个呢
也可以在此基础上
来实现clock和enhanced clock这个算法
大家可以去尝试一下
作为我们的challenge练习
可以去尝试一下
需要注意的是你要用这种算法呢
你可能还需要考虑很重要的
一些时间相关的一些因素
怎么能够在ucore里面进行记录
这一点需要大家去在课后
再去仔细想一想
好 假定我们设计好这个页替换算法
那其实页替换算法
大家想一想页替换算法
只是考虑了什么 只是考虑了
我要把哪一页换出去是吧
那么这是页替换算法要考虑的问题
什么时候触发这个事情呢
我们要考虑换出 触发的事情
那其实大家想一想 我们的ucore
在执行什么操作的时候会出现这种
会触发页替换算法
去执行把某一页换出去呢
其实就和我们前面讲到的
动态分配内存相关
如果要去分配一个虚拟页 这时候呢
我们的页替换算法发现说页不够了
那我们就需要把某一页换出去
这时候会触发页替换算法
所以说这是一种
被动的页替换算法策略
它属于产生某一个
内存分配一个请求之后
发现内存不够了
我们才去被动地去完成这个
把某一个不采用的页给换出去
这么一个操作 这是换出
但是页替换算法
还没有解决的问题是换入 是吧
那换入在哪出现呢
换入其实应该是在我们刚才说的
page fault的时候会出现
就是当我访问某一个页
这个页是合法的页
但是它又不在内存中的时候
这个时候就会触发换入操作
这一块呢是跟我们换入操作相关
那么我们的换入换出结合在一起
才形成一个完整的虚存管理系统
那我们知道这个页替换算法
其实需要用到一些
我们ucore里面的一些支持
包含数据结构 有两个重要结构
大家需要注意在做的时候
第一结构是什么 page
这个结构其实在我们lab2里面
管理物理内存页的时候
其实已经用到了 在这里面一开始
就用来管理物理内存页的
我们放在lab3里面
其实它还有很重要的作用
就是把这个空闲页给管理起来
从而可以知道
当前剩下多少空闲物理页
是否当前空闲页已经没有了 还是有
那么专门有一个这个page_link你需要注意
它这里面会用来链接这个空闲页
如果说我们需要换入的时候
从这里面去找出来一个页去换入
如果说空闲页没了
那我们就要把某一个页给换出去
那把某一个页换出去
其实是它这个页替换算法的一个实现
我们这里面是放在
swap fifo里面来实现的
这里面刚才已经提到了
这里面为了更好的理解这里面各个函数
到底要完成什么样的功能
建议大家读一读这里面的注释
以及对这个结构
特别是说到的swap_manager这几个结构
这个结构里每一个函数指针
到底要干什么事情 有更清楚的理解
我们这里面说要把某一页换出去
最终是通过这儿来完成一个
策略的选择 到底要换哪个页
对于FIFO来说
它就是最早进入那个页就要被换出去
OK 什么是最早 就是靠我们
刚才我们说page里面那个list
来找到最早这个页
最早放进去那个list里面的那个node
那一项那就是我们要换出去的
所以说这个呢我们这个函数的实现
swap_out_victim这一块就是要找到那个页
就要从哪找呢就刚才我说的page
形成一个list里面找出来
当大家如果完成了这个实验之后呢
如果是一个正确的实现可以看到
这么一个类似这样的一个输出
我把这个输出给大家简单解释一下
刚才说有一个vma的一个check
这里面就是如果
vma和mm结构设置好之后呢
这个check是可以成功的
如果你这个do_pgfault
能基本完成工作的话
那么当有一次缺页异常产生之后呢
那我们这个do_pgfault会分配一个页
从而可以使得do_pgfault
这个功能能够完成
把合法的虚拟地址和一个物理地址
建立对应的映射关系
从而可以让这一块check_pgfault能够成功
然后再接下来会完成什么
就是说的关于页替换算法这一块
那么它会建立好一个FIFO的
一个页替换算法
这里面是需要大家去实现相应的一个
我们说swap_fifo.c和swap_fifo.h里面
完成相应的工作
然后会建立一个环境 建立好环境之后
它会进行一系列的测试
这些输出是在do_pgfault里面实现的
就是说你可以知道
当产生一个异常之后 到底是什么原因
这是什么原因
在什么地址出现这种页访问异常
那从而可以知道出了这个问题
你要去做相应的一些什么样的操作
如果说是你实现正确的FIFO
这个check的话 那么你这个顺序
我们说我们把刚才说的具体数字呢
用一种我们说字母来表示ABCDE
这么一个顺序
跟我们这个做原理课里面提到的序列
页的序列是一样的
这个序列如果产生之后应该是
有一个在哪一时刻产生缺页
以及缺页的次数是确定的
接下来是做一系列的探测
看是否是这么一回事
从而如果这些所有探测都过了之后
那我们说你这个check_swap是成功的
这就是对结果的一个简单的描述
大家可以去仔细看一下这几个函数
check_swap check_pgfault check_vmm
这几个函数具体的测了什么东西
从而可以指导你们
来完成各自的实现的细节
好 那我们把lab3这一块呢
给大家做了一个简要的介绍
希望大家能够结合视频
结合我们的实验指导书
来完成lab3的实验
祝大家实验顺利 好 谢谢