9.6 缺页率置换算法慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

接下来我们讨论

全局置换算法当中的缺页率算法

那缺页率算法呢

实际上它是依据缺页之间的间隔

来调整我哪些页面放到内存里头

哪些页面被置换

在具体说明缺页率算法之前

我们需要对缺页率

给出一个准确的定义

通常情况下我们理解的缺页率

是缺页的次数和访存次数之间的

一个比值这个比值实际上

在我们缺页率算法里用的时候

它比较不好把握那我们更多的

会用缺页平均时间间隔的倒数

这个来作为我们缺页率

也就是说两次缺页之间

它有个间隔这个间隔可能长可能短

那我们在这取它的平均值

然后给倒数作为它缺页率

好那缺页率受哪些因素的影响呢

影响缺页率的因素有这样一些

我用的置换算法

然后我给进程分配的物理页面数

这个页面的大小

以及与我在实现我程序的时候

我所用的方法

比如说像前边说的我的局部性

跟我的实验方法有关系一样的

这几个因素里头

我们目前能控制的是置换算法

我们希望通过置换算法的选择

来影响这个缺页率

具体的做法是这样的

说我们的缺页率会随着分配给

进程的物理页面数的增加而降低

物理页面数越少缺页率会越高

那我们的缺页率算法的思路

是什么样子呢

是说我通过调节常驻集的大小

这个调节过程当中呢

会使得缺页率有变化

我去观测它这个变化

让它的缺页率保持在一定的范围里头

那具体说起来怎么保持呢

如果说缺页率过高那这时候呢

明显是我的分配给它的

物理页面数比较少

好那在这我就增加它的物理页面数

使得这条线能够回到下边来

好然后还有一种情况呢

是说我往里加那不会越加越多吗

那缺页率会低

低到一定程度之后

我的并发度就会降低

然后我的CPU的利用效率也会下降

好那这时候我会增加第二条

缺页率过低的时候我减少常驻集

这时候呢把一些页面给置换出去

那这样的话我的缺页率

就会回到一个合理的范围里头

那这是我们在这里

缺页率置换算法它的基本思路

那它如何来实现呢它是这样来做的

访存的时候我们去设置引用标志位

这和我们前边的

局部置换算法是一样的

然后不同的地方是在于

出现缺页的时候的处理

出现缺页的时候

我就计算上一次缺页的时间

和当前这个时间

也就是这一次缺页的时间

它们之间的间隔

根据这个间隔的大小的不同

我来做不同的处理

这个大小的不同实际上就是对应着

我们刚才说到的

缺页率置换算法里头的上界和下界

好在这里头我们有一个常量T

如果说这两个间隔是大于T的

也就是说这一段时间隔的比较长

这表示什么意思

这表示我这里头缺页比较少

那对于这种情况我就会把

在这一段时间没有引用的这些页面

我就把它置换出去

这样的话我就是减少常驻集的大小

就相当于缺页率比较低

然后我把这些不用的页面

我就把它置换出去

这样我可以

把它用到更有意义的地方

另一种情况是小

如果说这个缺页的间隔

小于这个时间T 那这时候我认为

这个缺页率是比较高的那这时候呢

我增加它的常驻集的大小

所谓增加怎么办呢

就是把你缺失的那一页

放到常驻集里头那这样一来的话

我们就实现了我们这里所说的

缺页率置换算法

那具体说起来呢

我们还是通过一个实例

来给出它到底是如何工作的

在这假定这个窗口是2

这和我们刚才说的

工作集里的那个窗口然后我们在

每次访问存储单元的时候

相当于正常访问的时候

你就直接访问做标记

缺页的时候我们来看它怎么处理

那首先第一次出现缺页

那这第一次没有以前了

那这时候直接往里加

然后接着往下访问

C不出现缺页正常访问你做修改

访问D也是一样的

在访问B的时候出现了缺页

那这个时候呢时间间隔是3

大于我们的2

那这时候我们说大于2的话

我就需要把在这一段时间里头

没有访问过的页面把它剔除出去

那这时候我们看

在这里头没有访问过的

这2里头访问的是哪

C和D 只把C和D留下

那这时候它就变成是

加上你刚才缺的这页B

就变成这个样子了

剩下的A和E就被置换出去了

在访问C的时候是正常的

在访问E的时候又出现缺页

那这个时候这个间隔是2

那小于等于我们刚才这个值

我直接加上再访问C是正常的

然后再访问E也是正常的

再访问A的时候它又出现缺页了

那这个缺页的时候呢我们再来看

在这里头我要把哪些留下

我在这一段时间里头访问过的

这里头就相当于是C E A这三种

这是目前这种情况

那实际上在这里头呢

再来访问D又缺页

这两个间隔比较小

我直接把它加进来那到这个地方呢

我们缺页率算法就算是说清楚了

那实际上我们看到

在这个执行的过程当中

进程驻留在内存里面的

页面数是有变化的

那这就是我们的常驻集的大小

在缺页率置换算法里

它会自动做调节

你比如说在这段时间里头

我是有四个页面

那分配给它的物理页面数就是四

然后在这一段时间里头呢

它是只有三个

在这一段时间里呢又是四个

那到这变成三个

这样的话每一个进程

它的物理页面数是在

整个运行过程当中动态调节的

某种角度上来讲

我们这个算法就是在逼近

我们刚才前边说的工作集

那个变化的那条曲线

我们希望它尽可能的接近

同时我又把这开销降下去

那这时候缺页率算法

和前边的工作集算法的区别在哪

区别在于原来你去看

我淘汰哪一个的时候

我是在每一次访问的时候

来做这件事情

那这个开销太大了现在怎么办呢

在中间你访问的时候

只要间隔足够大

那这时候我就认为这是需要加进去的

只是间隔大到一定程度之后

我才认为那里头有你不用的

我把它淘汰一次

这样的话我就把置换这件事情

放到缺页中断里头来完成

这和我们局部置换算法又一致了

这时候它的开销也就降下来了

好这是我们说到的缺页率置换算法

操作系统课程列表：

第零讲在线教学环境准备

-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

9.6 缺页率置换算法在线视频