9.4 Belady现象和局部置换算法比较慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

我们接下来介绍

局部置换算法它的一些特征

那么在这里头呢

我们前边已经介绍了

五种局部置换算法

这五种局部置换算法呢

各有各的优缺点

那么它们之间都有一些什么样的特征

到底它们之间是一个什么样的关系呢

我们在这用一部分时间做讨论

第一个是Belady现象

说的是随着分配给进程的

物理页面的增加

它的缺页率会少吗

好后边这个呢

实际上是对几种算法之间它们的比较

每一种算法呢

它都会在一定的情况下

和另一种算法体现出某种相似性

Belady现象

这里说的是说我们给每一个进程

分配一定数目的物理页面

那如果说它缺页次数比较多

那这时候我会需要增加给它的页面数

那增加完了之后

这时候我们按照通常的理解

它的缺页应该降低

但实际上如果你的算法不好

比如说像我们这里的FIFO

在某些情况下你增加页面之后

它的缺页次数反而会增加

这种现象就叫Belady

那产生这种现象的原因是什么呢

原因是这样的

我们置换算法你置换的话

是标记它的某种特征

然后依据这种特征对它进行置换

那我们标记的这种特征

和进程的内存访问的这种特征

它是不一致的

那也就是说每个进程

是不是会有自己的访问特征呢

你比如说我有一个排序程序

那它的访问特征和另外一个

我一个word的编辑程序那这两种呢

它的内存访问特征

肯定是完全不一样的

好正是由于这种原因

我们置换算法对它的预测呢

和进程实际情况会不一致

好那这种预测不合理

那就有可能出现这种情况

那这时候是说

是我所有的算法都这样吗

这是我们需要考虑的那我们在这呢

还是先从FIFO说起

我们刚才说FIFO是有Belady现象的

我可以找到一个实例

说你用FIFO算法

那分配给它页数少的时候

它会出现一个缺页次数

分配增加之后

缺页次数反而增加的这种情况

那我们具体来看一下这个实例

那在这里头呢这个地方是个FIFO

然后这是访问的序列

然后我们在这呢访问缺页状态

在这跟我们前边的约定

稍微有点不一样

比如说我们在这里

第一次访问我就认为它是缺页

为啥会这样呢

原因在于我们在前边

统计局部置换算法的时候

刚开始我的那一段我是不算的

但是在这呢

因为我分配给它三个物理页面

下一次我分配给它四个

如果这段不算的话

这两个的比较性会不一样

好所以我们在这起头的这几个都算

好那这个是前三次我刚起头的时候

那这个呢怎么着都是一样的

什么算法都是这样

好第四个那这时候呢加进来

你的前三个是不在这的

它会产生缺页再往下一个

这一个也不在它还会是缺页

然后还会是缺页

然后到这5这也还会是缺页

好那到1这个地方呢

没问题了这个1在里头

好那这个时候呢

它没有命中然后2命中

然后3缺页 4缺页 5缺页

那这时候呢总共有多少次呢

总共是在这缺页是9次

我只有三次命中的

那我们在这呢这是个示例

好那我们再这呢我们再看

我分配给它4页的时候

还是同样一个序列

它的缺页次数会增加吗

好由于我们刚才说你分出的三次

那前边这四次是肯定一样的

好那在这里头说

你分配4页肯定比刚才好

那从第一个来讲这肯定是好

因为刚才那个1拿出去了

你就有缺页了

好这1没拿出去是不是好了呢

1没拿出去这确实是命中了

但是这两次都是成功的

好接下来的日子就不好过了

接下来之后5缺页你把它拿出去

好然后在这呢再来1

你又把它拿出去

然后2 又是缺页 3 4 5

你会发现在这个顺序当中

我这访问的总共就五个

你到了4页之后还是有缺页

到什么情况下不会缺页呢

你把这五个全放在这就肯定不会了

那现在就是说对于4页的这种情况

那到这实际上你可以基本上可以看到

你刚才把哪一个拿出去之后

我就要访问哪一个

1 2 3 4 5 正好对着的

那你说在任何一种情况下

是不是你给出一个序列来之后

我就可以针对着你拿出的情况

构造出这个序列来呢

这是我们在这里头

那你说这么来的话

我可以构造出来的话

我是不是任何一个算法

都能做到这样呢

这是我们在这里需要讨论的

好从这呢给出一个实例

就是这个序列分3页和分4页

它的情况是缺页增加的

所以它是存在Belady现象的

那如果说你在这里呢

你证明它有那我举出一个例子来就行了

但是如果你想证明它没有

你把所有的全枚举一遍吗

这是不可能的好那在这呢

我们说LRU它是没有Belady现象的

那在这呢也给出了一个实例

说我这是分配三页缺页十次

然后我在这呢再给它分配四页

那数一遍之后呢

它缺页八次那这个没有

那我仅靠这一个例子

我是没有办法说明这一条的

那有证明吗

好实际上在这里呢

我们是可以有证明的

说只要是你类似于

我们前面那个栈的这种做法

那从底下往上抽的话

那这些算法呢

它肯定都是没有Belady现象的

这是我们说的那再问一句

我们的时钟和改进的时钟

这两种折中之后有Belady现象吗

LRU没有Belady现象

和关于时钟和改进的时钟算法的

Belady现象

到底是个什么结论

留给大家课后去思考

这个在相关的参考书里

可以找到它的证明

那接下来我们说LRU FIFO和时钟

这三种算法它们之间的比较

那实际上我们在前边已经说过了

这两个是两个极端

除了那个最优算法LRU是最好的实现

然后FIFO是我们在这里给出来比较差的

那这时候呢它们有什么相关性呢

实际上任何一个置换算法

那它在做的时候呢

都会有一个排序

这个排序是什么样的

这对于你有至关重要的影响

这两者的区别在于

LRU是因为是以最近一次访问的时间

前边的访问的时间来做排序

而FIFO是以加载的时候

装入的时间为顺序来排序

这是它排序的它们俩之间的区别

那仅从这个时间点上来说呢

好像这个事比较好弄

第二个是它的这个在执行的过程当中

它是否要动态的调整

那这时候FIFO的这个顺序进来的时候

这个因素在后边就再也不会变了

所以它没有调整所以它的开销就小

而LRU每一次访问

我都要去维护我那个栈的顺序

所以它的开销是很大的

那这样一来的话

就相当于我们说这两种算法是开销大

它的性能好这个开销少它有问题

然后说这两种算法它在一定情况下

是可以相互转换的

LRU它可以退化成FIFO

在什么情况下呢是这样的

如果说你访问的页面是第一次

也就只访问一次然后就不再访问了

对于这种情况这两个算法

你在里用LRU是没有意义的

原因在于它只用一次

你用第一次的时候

没有任何的历史你可以借鉴

所以它俩是一样的

而这时候它的顺序

也是跟你加载的顺序是一样的

所以这两个排序是一样的

好在这这是一个实际的例子

那你说这个例子是你构造出来的

有几个页面

我就顺序的访问比它多一个

这样的话对于FIFO

你就肯定是不行的了

那在我们实际用到的程序里

有啥样的是这种情况的

这种情况也是存在的

比如说我们在看视频

视频信息的输出的时候

你在读入相关的信息那这个信息呢

通常情况下我们播视频的时候

它是从头到尾播一遍

你很少有翻来覆去在那听的这种情况

好正是由于这种原因

所以我们这种只放一遍的

这种情况也是有的

如果说在你的系统当中

这种情况很常见

你就有必要针对这个

别把这个缓存的事做的很复杂

这是LRU和FIFO之间的一些关系

那这时候说LRU的性能好

但是开销大 FIFO的开销小

但是会有Belady 然后说Clock

时钟算法实际上是它们俩之间的折中

怎么做折中呢我们看一下

在这里访问页面的时候

我们前面说一个需要调整顺序

一个不调整顺序

那调整顺序的开销大

那不调整顺序这个呢

我就啥事也没做

那这个做法呢不好

我们在这里取一个折中

就是访问的时候我会做标记

比如说哪些页面访问过

那这是比FIFO做的复杂的事

那由于这件事情有硬件参与

改页表里的页表项

这件事情相对来说比较方便

好然后我不去调整它的顺序

那这样的话

我调整顺序的开销就没了

然后说在这里头呢

那我要想得到LRU的一些特征

我怎么办呢我缺页的时候

那缺页的时候我们的时钟算法会去扫描

实际上这个扫描你可以理解为

它这里对这个顺序做了一定的调整

实际上它怎么调整呢

就是你扫描的过程当中

有一些点它是直接蹦过的

访问过的它是直接蹦过去了

好这种直接蹦过你可以理解为

是把它的顺序是做了某种形式的调整

好那这样一来的话

说时钟算法它和LRU是什么样的呢

对于刚才说的没有访问过的页面

这Clock算法你LRU也已经退化成FIFO了

你Clock也和它是一样的所以你可以说

Clock和LRU是性能一样的好

实际上它和FIFO

它们三个是一样的

因为我没有任何可以借用的信息了

好那在什么情况下

它比FIFO做的好呢

对于被访问过的页面

Clock就比LRU要做的差

但是比FIFO做的好

因为在这里Clock它只记录了

我是否访问过访问过的我留下

而对于LRU不但是访问过的

我要做记录

并且访问的顺序我还要做记录

所以这样的话

它的记录的信息比Clock要多

这是我们对这三种算法

它们之间的一个比较

到这个地方为止

我们就把局部置换算法呢

全部讲完了在这里头说

这些主要的区别是在于

我在这个固定页面的情况下

我怎么来调整我要置换的

这个页面到底是谁我对它做排序

我以什么样的指标来排序

这种排序的情况下

它们的开销是什么样的

好在开销我不可以接受的情况下

我如何对它去做折中和简化

操作系统课程列表：

第零讲在线教学环境准备

-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.4 Belady现象和局部置换算法比较在线视频