10.5 页换入换出机制慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

我们前面讲了这个

页异常要干的事情

我们再看看我们重点考虑说

我们要实现页替换算法了

因为在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的实验

祝大家实验顺利好谢谢

操作系统课程列表：

第零讲在线教学环境准备

-0.1 Piazza讨论区

--piazza访问和使用

--html

-0.2 在线实验平台

-0.2在线实验平台

第一讲操作系统概述

-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.2 系统启动流程

-3.3 中断、异常和系统调用比较

--3.3 中断、异常和系统调用比较

-第三讲启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较

-3.4 系统调用

--3.4 系统调用

-第三讲启动、中断、异常和系统调用--3.4 系统调用

-3.5 系统调用示例

--3.5 系统调用示例

-3.6 ucore+系统调用代码

--3.6 ucore+系统调用代码

第四讲实验一 bootloader启动ucore os

-4.1 启动顺序

-4.2 C函数调用的实现

-4.3 GCC内联汇编

-4.4 x86中断处理过程

-4.5 练习一

-4.6 练习二

-4.7 练习三

-4.8 练习四练习五

-4.9 练习六

第五讲物理内存管理: 连续内存分配

-5.1 计算机体系结构和内存层次

-5.2 地址空间和地址生成

-5.3 连续内存分配

-5.4 碎片整理

-5.5 伙伴系统

-第五讲物理内存管理: 连续内存分配--5.6 练习

第六讲物理内存管理: 非连续内存分配

-6.1 非连续内存分配的需求背景

-6.2 段式存储管理

-6.3 页式存储管理

-6.4 页表概述

-6.5 快表和多级页表

-6.6 反置页表

-6.7 段页式存储管理

-第六讲物理内存管理: 非连续内存分配--6.8 练习

第七讲实验二物理内存管理

-7.1 了解x86保护模式中的特权级

--7.1 了解x86保护模式中的特权级

-第七讲实验二物理内存管理--7.1 了解x86保护模式中的特权级

-7.2 了解特权级切换过程

--7.2 了解特权级切换过程

-第七讲实验二物理内存管理--7.2 了解特权级切换过程

-7.3 了解段/页表

--7.3 了解段/页表

-第七讲实验二物理内存管理--7.3 了解段/页表

-7.4 了解UCORE建立段/页表

--7.4 了解ucore建立段/页表

-第七讲实验二物理内存管理--7.4 了解UCORE建立段/页表

-7.5 演示lab2实验环节

--7.5 演示lab2实验环节

第八讲虚拟存储概念

-8.1 虚拟存储的需求背景

-8.2 覆盖和交换

-8.3 局部性原理

-8.4 虚拟存储概念

-8.5 虚拟页式存储

-8.6 缺页异常

第九讲页面置换算法

-9.1 页面置换算法的概念

--9.1 页面置换算法的概念

-9.2 最优算法、先进先出算法和最近最久未使用算法

--9.2 最优算法、先进先出算法和最近最久未使用算法

-第九讲页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法

-9.3 时钟置换算法和最不常用算法

--9.3 时钟置换算法和最不常用算法

-第九讲页面置换算法--9.3 时钟置换算法和最不常用算法

-9.4 Belady现象和局部置换算法比较

--9.4 Belady现象和局部置换算法比较

-第九讲页面置换算法--9.4 Belady现象和局部置换算法比较

-9.5 工作集置换算法

--9.5 工作集置换算法

-第九讲页面置换算法--9.5 工作集置换算法

-9.6 缺页率置换算法

--9.6 缺页率置换算法

-第九讲页面置换算法--9.6 缺页率置换算法

-9.7 抖动和负载控制

--9.7 抖动和负载控制

第十讲实验三虚拟内存管理

-10.1 实验目标：虚存管理

--10.1 实验目标：虚存管理

-第十讲实验三虚拟内存管理--10.1 实验目标：虚存管理

-10.2 回顾历史和了解当下

-- 10.2 回顾历史和了解当下

-第十讲实验三虚拟内存管理--10.2 回顾历史和了解当下

-10.3 处理流程、关键数据结构和功能

--10.3 处理流程、关键数据结构和功能

-第十讲实验三虚拟内存管理--10.3 处理流程、关键数据结构和功能

-10.4 页访问异常

--10.4 页访问异常

-第十讲实验三虚拟内存管理--10.4 页访问异常

-10.5 页换入换出机制

--10.5 页换入换出机制

-第十讲实验三虚拟内存管理--10.5 页换入换出机制

第十一讲进程和线程

-11.1 进程的概念

--11.1 进程的概念

-第十一讲进程和线程--11.1 进程的概念

-11.2 进程控制块

--11.2 进程控制块

-第十一讲进程和线程--11.2 进程控制块

-11.3 进程状态

--11.3 进程状态

-第十一讲进程和线程--11.3 进程状态

-11.4 三状态进程模型

--11.4 三状态进程模型

-11.5 挂起进程模型

--11.5 挂起进程模型

-第十一讲进程和线程--11.5 挂起进程模型

-11.6 线程的概念

--11.6 线程的概念

-第十一讲进程和线程--11.6 线程的概念

-11.7 用户线程

--11.7 用户线程

-第十一讲进程和线程--11.7 用户线程

-11.8 内核线程

--11.8 内核线程

-第十一讲进程和线程--11.8 内核线程

第十二讲进程控制

-12.1 进程切换

--12.1 进程切换

-第十二讲进程控制--12.1 进程切换

-12.2 进程创建

--12.2 进程创建

-第十二讲进程控制--12.2 进程创建

-12.3 进程加载

--12.3 进程加载

-第十二讲进程控制--12.3 进程加载

-12.4 进程等待与退出

--12.4 进程等待与退出

-第十二讲进程控制--12.4 进程等待与退出

第十三讲实验四内核线程管理

-13.1 总体介绍

-13.2 关键数据结构

-13.3 执行流程

-13.4 实际操作

第十四讲实验五用户进程管理

-14.1 总体介绍

--14.1 总体介绍

-14.2 进程的内存布局

--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.5 进程复制

-14.6 内存管理的copy-on-write机制

--14.6 内存管理的copy-on-write机制

第十五讲处理机调度

-15.1 处理机调度概念

--15.1 处理机调度概念

-第十五讲处理机调度--15.1 处理机调度概念

-15.2 调度准则

--15.2 调度准则

-15.3 先来先服务、短进程优先和最高响应比优先调度算法

--15.3 先来先服务、短进程优先和最高响应比优先调度算法

-第十五讲处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法

-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

-第十五讲处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc

-15.5 实时调度和多处理器调度

--15.5 实时调度和多处理器调度

-第十五讲处理机调度--15.5 实时调度和多处理器调度

-15.6 优先级反置

--15.6 优先级反置

-第十五讲处理机调度--15.6 优先级反置

第十六讲实验六调度器

-16.1 总体介绍和调度过程

-16.2 调度算法支撑框架

-16.3 时间片轮转调度算法

-16.4 Stride调度算法

第十七讲同步互斥

-17.1 背景

--17.1 背景

-17.2 现实生活中的同步问题

--17.2 现实生活中的同步问题

-第十七讲同步互斥--17.2 现实生活中的同步问题

-17.3 临界区和禁用硬件中断同步方法

--17.3 临界区和禁用硬件中断同步方法

-第十七讲同步互斥--17.3 临界区和禁用硬件中断同步方法

-17.4 基于软件的同步方法

--17.4 基于软件的同步方法

-第十七讲同步互斥--17.4 基于软件的同步方法

-17.5 高级抽象的同步方法

--17.5 高级抽象的同步方法

-第十七讲同步互斥--17.5 高级抽象的同步方法

第十八讲信号量与管程

-18.1 信号量

--18.1 信号量

-第十八讲信号量与管程--18.1 信号量

-18.2 信号量使用

--18.2 信号量使用

-第十八讲信号量与管程--18.2 信号量使用

-18.3 管程

--18.3 管程

-第十八讲信号量与管程--18.3 管程

-18.4 哲学家就餐问题

--18.4 哲学家就餐问题

-18.5 读者-写者问题

--18.5 读者-写者问题

第十九讲实验七同步互斥

-19.1 总体介绍

--19.1 总体介绍

-19.2 底层支撑

--19.2 底层支撑

-第十九讲实验七同步互斥--19.2 底层支撑

-19.3 信号量设计实现

--19.3 信号量设计实现

-第十九讲实验七同步互斥--19.3 信号量设计实现

-19.4 管程和条件变量设计实现

--19.4 管程和条件变量设计实现

-第十九讲实验七同步互斥--19.4 管程和条件变量设计实现

-19.5 哲学家就餐问题

--19.5 哲学家就餐问题

第二十讲死锁和进程通信

-20.1 死锁概念

--20.1 死锁概念

-第二十讲死锁和进程通信--20.1 死锁概念

-20.2 死锁处理方法

--20.2 死锁处理方法

-第二十讲死锁和进程通信--20.2 死锁处理方法

-20.3 银行家算法

--20.3 银行家算法

-第二十讲死锁和进程通信--20.3 银行家算法

-20.4 死锁检测

--20.4 死锁检测

-第二十讲死锁和进程通信--20.4 死锁检测

-20.5 进程通信概念

--20.5 进程通信概念

-第二十讲死锁和进程通信--20.5 进程通信概念

-20.6 信号和管道

--20.6 信号和管道

-第二十讲死锁和进程通信--20.6 信号和管道

-20.7 消息队列和共享内存

--20.7 消息队列和共享内存

-第二十讲死锁和进程通信--20.7 消息队列和共享内存

第二十一讲文件系统

-21.1 文件系统和文件

--21.1 文件系统和文件

-第二十一讲文件系统--21.1 文件系统和文件

-21.2 文件描述符

--21.2 文件描述符

-第二十一讲文件系统--21.2 文件描述符

-21.3 目录、文件别名和文件系统种类

--21.3 目录、文件别名和文件系统种类

-第二十一讲文件系统--21.3 目录、文件别名和文件系统种类

-21.4 虚拟文件系统

--21.4 虚拟文件系统

-第二十一讲文件系统--21.4 虚拟文件系统

-21.5 文件缓存和打开文件

--21.5 文件缓存和打开文件

-第二十一讲文件系统--21.5 文件缓存和打开文件

-21.6 文件分配

--21.6 文件分配

-第二十一讲文件系统--21.6 文件分配

-21.7 空闲空间管理和冗余磁盘阵列RAID

--21.7 空闲空间管理和冗余磁盘阵列RAID

-第二十一讲文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID

第二十二讲实验八文件系统

-22.1 总体介绍

--22.1 总体介绍

-第二十二讲实验八文件系统--22.1 总体介绍

-22.2 ucore 文件系统架构

--22.2 ucore 文件系统架构

-第二十二讲实验八文件系统--22.2 ucore 文件系统架构

-22.3 Simple File System分析

--22.3 Simple File System分析

-第二十二讲实验八文件系统--22.3 Simple File System分析

-22.4 Virtual File System分析

--22.4 Virtual File System分析

-第二十二讲实验八文件系统--22.4 Virtual File System分

-22.5 I/O设备接口分析

--22.5 I/O设备接口分析

-第二十二讲实验八文件系统--22.5 I/O设备接口分析

-22.6 执行流程分析

--22.6 执行流程分析

第二十三讲 I/O子系统

-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

--html

10.5 页换入换出机制在线视频