8.3 局部性原理慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

接下来我们介绍虚拟存储当中的局部性原理

那我们在这里说虚拟存储是想

把原来放到内存里的这个进程地址空间的信息

把其中的一部分放到外存当中来

那要把它放到外存当中来呢

实际上这时候呢需要有一系列的准备工作

那我们首先看一下

我们在这里头如何把这个放到外存里头来

我们想达到的目标具体准确的描述出来

这是我们虚拟存储希望达到的效果

进程地址空间实际的物理内存和外存

这两个搁在一起呢

来存放地址空间的内容

这一些呢放在内存一些放到外存里头

中间呢是由操作系统来干这件事情

那我们把这个目标具体的描述出来呢

就有这样两条第一条是说

我们只让一部分程序加载到内存当中来

这时候呢就可以让程序运行

那这是跟以前不一样的

以前我们说要想一个程序运行

我必须把整个进程加到地址空间当中

那这时候才能开始运行只加一部分让它

怎么能让它运行起来

那这时候呢需要我们做的是说要操作系统

自动的来完成我需要加载哪一部分

而不需要程序员的参与

而在我们前面用的覆盖技术呢

这是需要程序员来参与的

另一个呢是说我们可以把一部分

内存空间当中的信息放到外存当中去

内存和外存之间做一个交换

这样做的目的是让正在运行的进程

能够有更多的空闲空间

而这一条也是需要由操作系统来做

它在内外存之间进行交换

需要讨论的问题是说我到底要把哪些东西放出去

实际上这时候我们前面说的第一个

我到底要把哪些东西放进来

这是我用到的放进来

这个地方我把哪个东西放出去呢

实际上是说我需要把不常用的放到外存当中去

这就是我们后面会说到的置换算法

那在具体讨论之前呢

我们需要来讨论程序访问的一些特征

这就是我们这里说到的局部性原理

所谓局部性原理呢是指程序在执行的过程当中

在一个较短的时间里头

它所执行的指令和指令操作数的地址

分别局限于在一定区域里头

因为通常情况下我们指令是存在代码段里的

指令所访问的操作数呢通常是存在数据段里的

这两个呢各是一个地方

那这两个各自一个地方呢

分别局限在一定区域里头

这怎么说呢这种特征呢体现在以下几个方面

第一个呢叫时间局部性

也就是说我一条指令的连续两次执行

我一个数据的连续两次访问通常情况下

它们都集中在一段较短的时间里头

正是因为有了这种较短的时间所以我可以把

放到内存里的这一段内容它会频繁的访问

如果没这一条的话可能出现一种什么样的情况

就是你刚放进来内存里的这个信息

下一步要访问另一个你刚拿出去的

如果出现这种极端情况的话

你这个虚拟存储就性能大幅度下降了

好这是时间局部性

另一个呢是说空间局部性

空间局部性是指我相邻的几条指令

或者说我访问的相邻的几个数据

访问区域呢是局限在一个较小的区域里头

也就是说我相邻的访问的两条指令

相邻访问的两个数据

比如说我们在对数据进行排序的时候

那我会有循环

那这个循环呢就是你要访问这几条指令

而我排序的相邻这些数据呢

那就是你这儿要访问的数据

它们呢通常情况下是局限在一个较小的区域里头

再有一条呢是叫分支局部性

分支局部性是指什么呢说我有一条跳转指令

这跳转指令的两次执行呢很多时候

它是会跳转到同一个地址的

这种情况在实际的例子中会是什么样的

比如说我有一个循环循环一千次

那进到这个循环体里头

到那个循环的跳转指令的地方

判断小于你的循环次数

它就蹦回到开头那这样的话

你从这条指令上来看

前面只要没到你的循环次数

那前面都是蹦到开头

那这样的话只有最后一次是例外

好那这种呢我们称之为叫分支局部性

有了这几条之后我们就可以认为

我们所运行的程序它具有它所执行的指令

所访问的数据有很好的这种集中特征

它们会集中在一个局部的区域里头

那这样的话如果我们能够判断清楚

它局限在的那个区域到底是哪些

我们可以对它做很好的预测的话

那这时候我们就可以把这些内容放到内存里头来

而把那些不常用的放到外存当中

而这种经常用的放到内存里头之后

那我们的计算的程序执行的性能

就不会有大幅度下降这也是由于这一条

我们局部性原理那从理论上呢保证了

我们虚拟存储它是可能实现的

它具有可行性并且呢

它实现完了之后应该能有很好的这个效果

好那具体呢我们通过一个例子来说明

说这个局部性到底体现在什么地方

同时这种局部性

也跟我们写的程序特征是有关系的

在这儿给一个例子

说我在这里呢4K为一个页面

然后我给一个进程呢这仅仅是个示例

分配一个页面这是用来放数据的

好那这里头我约定一个二维数组

那1024乘1024 假定你的int是整数呢

是占四个字节为一个整数

好那这时候呢我在这个页面

再被这个数组呢进行清零

我们看它访问的次数会是啥样的

好清零呢我来写我这程序的时候呢

这是一种写法两个循环

二维数组第一维第二维

那需要大家注意的是我第一维呢

在里头这个循环是用的第一个下标

在外头这个循环是用的第二个下标

而还有一种另外的写法我把它反过来

i j i j 这样的话在里头那个小循环里头

那我是先循环的第二位

那如果说我们在实际的存储当中

它的存储顺序和你这两个循环

实际上它在访问的时候

它的位置的分布呢是很不相同的

那我们具体看一下这两个到底会有什么样的情况

那这是呢我们看到的刚才那个

二维数组它在存储空间当中的情况

这里呢每一行代表一页

你比如说每个元素我占四个字节

1024个刚才说的4K 4K我占一页

我们用来存数据的呢分配的页面是

物理页面是一个那这样的话我每使用一行

蹦到下一行的时候我就会产生缺页

那对应着我们刚才前面的两种清零的办法

那第一种办法呢我是从第一个元素

然后它并不是在这一页里的第二个

而是第二页里的第一个

一直到最后一页的第一个

然后再是这样循环下来的

我们看它它的访问顺序第一页一直到1023

然后又是第0页到1023

这样的话我每一次相邻的一次访问

我都会切到下一页那这种切换呢会导致一次缺页

那这样总共缺页次数是什么

就是1024乘1024 而我们的第二种做法呢

它的访问方式是先把这一行全部清零

然后再把第二行全部清零

如果说你意识到背后是虚拟存储

那么这时候呢这地方的缺页次数

就变成了1024次

如果说你认为这些数据全在内存里头

那么这两种做法

我们在内存里头任何一个单元在访问的时候

它都是使用的时间是一样的

那这两种算法是没有区别的

好如果说我们在这里头考虑到物理内存的量小

那么这时候呢这两种做法

它的区别呢就是巨大的

所以在这儿呢不同的程序

如果说你背后利用了虚拟存储

那你在这里头呢需要很小心的

去使用你的编程方法以便于提高它的局部性

这个提高它的局部性

也有利于提高你的程序的这个性能

好基于这样一种做法呢

我们说在这里头它可以很好的有局部性的特征

那接下来我们会说基于这种局部性的特征

我们怎么来实现我们的虚拟存储系统

操作系统课程列表：

第零讲在线教学环境准备

-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

8.3 局部性原理在线视频