9.1 页面置换算法的概念慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

各位同学大家好

今天我们来开始介绍置换算法

那在置换算法这一部分里头呢

我们分成这样三部分来讨论

首先是置换算法的概念

也就是说置换算法

到底是干什么的

然后接下来两个部分是

两种类型的置换算法

局部置换算法是说我

假定分配给一个物理页面数

已经定了之后

然后我去选择到底哪个被置换

而全局置换算法

是不区分置换的这个页面

到底属于哪个进程这样的话

隐含着后边有每个进程

分配的物理页面数

也会做调整的这样一种情况

好那我们接下来一个一个的说

置换算法是干什么的呢

置换算法是说我们在

虚拟存储系统当中

出现缺页的时候

我需要把一个新的页面

换到内存当中来换入

但这时候内存当中的页面

已经全部都用完了

那这时候我必须选择一个页面

把它放到外存当中去

那我新要用的页面才能放进来

置换算法的功能就是

选择被置换的物理页面

你到底选择哪一个

那你说我选择的时候

我怎么来选择呢

那选择有它的依据

那这时候就是我们在这里头

你的依据到底是啥

这就是置换算法的设计目标

那在这里头呢

我们想要来设计一种置换算法

它的目标呢是说我希望尽可能的

减少页面的调入和调出的次数

那要想让你这个调入调出的次数

实际上这个时候

跟你实际运行的那个程序

对存储访问的特征

是有密切关系的

好那这时候我希望能够了解

程序在执行的过程当中

它的内存的访问特征

然后我来设计这个置换算法

那这样一来

你得是针对

每一个应用程序来设计吗

那不是这样的

我在操作系统没办法这么做

我只能是设计一个置换算法

然后考虑到它可能运行环境的

这一系列的进程的访问特征

然后从里头找出

适用面比较广的这种情况

那具体说起来呢我们希望是这样的

把未来不再访问

或者说近期不再访问的

这些页面调出去

那这一条实际上很大的麻烦

是在于我如何能知道这一点

我如何能对未来的情况做一个估计

而这是我们在设计置换算法的时候

考虑最多的一些因素

好在具体讨论我如何来做这种选择

如何来设计置换算法之前呢

还有一个小问题需要在这先说一下

就是页面锁定

这个是虚拟存储当中的一个概念

说我在进行置换的时候

有一些页面

你是不可以把它换到外存里头的

那这种情况呢通常情况下是说

我有一些必须在内存里头的

重要的这些逻辑页面

这时候你比如说

操作系统里头的关键代码

然后还有一些呢

它并不一定是操作系统里的关键代码

但是它要求响应速度比较快

你要是说访问的那页在外存里头

那这个性能下降是它接受不了的

好这些代码我也放在这里头

好我们怎么来做到这一点呢

实际上在虚拟页式里头

它就在页表里的页表项

相应的页面上加一个锁定标志

有了这个标志之后

置换算法在运行的过程当中就

不会把这个页面放在外存里面去

那在具体讨论之前呢

我们还有一个问题需要大家讨论

那就是我设计了一种置换算法

你设计一种到底我们俩谁算好

那这种好实际上在这

是通过统计测试用例

的形式来给出来的

那在这我们为了后续讨论方便

我们需要给出一些约定

也就是说我怎么知道

一个进程的访问内存的序列呢

我就是记录它访问

所有存储单元的这个轨迹

然后那你比如说这里头

我们通常情况下

访问页面的时候是页号页内偏移

那在我们这里头呢

我们关心的是访问的是哪一页

实际上一页内部

到底是哪一个存储单元

这时候是我们不太关心的

好我们在这页号页内偏移

我得到这个序列

然后我把页内偏移都去掉

做简化就变成了底下这个序列了

好为了我们在后边说置换算法的时候

说起来方便

我们在这里头又给它换了一种表示

用字母来表示

这样避免和我们的顺序的1 2 3 4搞混了

好有了这个之后

那这时候哪种算法比较好呢

那我们的评价标准是

模拟置换算法的行为然后记录

在这个置换的过程当中

各个算法到底有多少次缺页

少的就是好的那有了这两条之后

我们大概就可以开始

来讨论置换算法了

那在讨论之前呢

我们还是首先把置换算法做一个分类

因为你要界定你在讨论

置换算法的时候能够借用的外界条件

那在这里头呢

按照借用的外界条件的不同

我们分成两类

一类叫做局部置换算法

那在局部置换算法里头呢

分配给一个进程的物理页面数

是已经确定了

那我们在置换的时候

选择的范围仅限于当前进程

有了这一条之后

那也就相当于我在置换的过程当中

每个进程分配的

页面的总数是不会变化的

那这里头呢

我们有一系列的算法最优算法

也就是说如果我能预测未来的话

我依据未来来决定我换哪个页面

这个是理论上的最好状态

没有算法比它更好

但是它的问题是

这个算法你在实际用的时候

你没办法知道

它所依赖的那个前提条件

就是未来什么时候会用到这个页面

第二个呢是先进先出

这个算法是说用最简单的办法

我不知道它未来是啥情况

我就按照进来的时候的先后顺序

但是这个进来的先后顺序呢

并不一定反映了

实际的存储的访问特征

好那这样的话

这个算法的性能不好

再有一个就是

最近最久未使用算法

那它实际上是在这里头呢

这个算法先进先出太差

最优算法没法实现

因为你是预测未来没法实现

好那在这最近最久未使用算法

就是我把预测未来

变成是我统计过去

在过去一段时间的特征

我们通常情况下认为你过去的特征

对你未来是一种预测

好我们基于这样一种假设前提呢

来讨论最近最久未使用算法

但是这种算法呢它可能实现

但是仍然它的复杂度比较高

好那这时候呢

就由它的这两种近似算法

我们这会说到

时钟算法和最不常用算法

那这都是对最近最久

未使用算法的一种近似

那具体的近似的做法呢

我们在后边再详细去说

这是一类也就是相当于

我在当前进程暂用的页面里

来讨论我换谁

还有一类算法呢

叫全局置换算法

它不关心你当前换的这个页面

属于哪个进程

它讨论的范围是说置换的范围

是在所有可能换出的物理页面

它不管是哪个进程的

这隐含着如果说我在置换的时候

是进程A的一个需要访问的页面

被置换出去那是进程B的

实际上这时候就隐含了

这两个进程之间分配的

物理页面数的一个变化

好这时候呢它也有两种算法

我们在这会说到

工作集算法和缺页率算法

好有了这样一个大致分类之后

我们就先按照局部置换算法和

全局置换算法的顺序

来一个一个的进行讨论

操作系统课程列表：

第零讲在线教学环境准备

-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.1 页面置换算法的概念在线视频