计算机系统结构 (第9讲).

Slides:



Advertisements
Similar presentations
第五节 函数的微分 一、微分的定义 二、微分的几何意义 三、基本初等函数的微分公式与微分运算 法则 四、微分形式不变性 五、微分在近似计算中的应用 六、小结.
Advertisements

2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
高校教师、高级项目经理 任铄 QQ : 第一章 操作系统引论 1.1 操作系统的目标和作用 1.2 操作系统的发展过程 1.3 操作系统的基本特性 1.4 操作系统的主要功能 1.5 OS 结构设计.
第五章 存储系统 5.1 存储器的构成 5.2 存储系统的构成 5.3 Cache 5.4 虚拟存储器.
微机原理与接口技术 第二章: ARM微处理器硬件结构
LSF系统介绍 张焕杰 中国科学技术大学网络信息中心
计算机系统结构 第五章 存储系统.
第 6 章 存储系统 ——本章主要介绍三级存储体系的含义,及存储器的逻辑设计方法。
第四章 存储系统 计算机科学技术系 2006 年 4 月.
第3章 存储系统.
第三章 存储系统 现代计算机系统都以存储器为中心 在计算机运行过程中,存储器是各 种信息存储和交换的中心。
缓存(续).
§2 虚拟存储器 1961年英国曼彻斯特大学Kilbrn等人提出 70年代广泛地应用于大中型计算机系统中 目前许多微型机也开始使用虚拟存储器
实用操作系统概念 张惠娟 副教授 1.
5.5 减少命中时间 容量小、结构简单的Cache 第五章 存储层次
《高等数学》(理学) 常数项级数的概念 袁安锋
第五章 存储层次 5.1 存储器的层次结构 5.2 高速缓冲存储器基本知识 5.3 降低Cache不命中率的方法
第四章 存储体系.
小学生游戏.
计算机组成原理第四章 知识点一:存储系统层次结构和评价方法 主讲教师:吴非.
第5章 定积分及其应用 基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法
Cache综合应用案例 某计算机的主存地址空间大小为256 MB,按字节编址。指令Cache和数据Cache分离,均有8个Cache行,每个Cache行大小为64 B,数据Cache采用直接映射方式。现有两个功能相同的程序A和B,其伪代码如下所示: 程序A: int a[256][256]; …… int.
计算机系统结构 南京航空航天大学 计算机科学与技术学院 主讲:刘佳
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
计算机基础知识 丁家营镇九年制学校 徐中先.
3.1 存储器的构成 3.2 存储系统的构成 3,3 Cache 3,4 虚拟存储器
§3 高速缓冲存储器(Cache) 工作原理和基本结构 地址映象与变换 Cache存储器的LRU替换算法的硬件实现
LSF系统介绍 张焕杰 中国科学技术大学网络信息中心
第3章 存储系统 现代计算机系统以存储器为中心 3.1 存储系统原理 3.2 虚拟存储器 3.3 高速缓冲存储器(Cache)
存储系统.
走进编程 程序的顺序结构(二).
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
computer organization principle
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
逆向工程-汇编语言
动态规划(Dynamic Programming)
CPU结构和功能.
图片与视频数字化. 图片与视频数字化 图片分类 根据图片的构成元素来分 位图: 由像素组成,计算机按顺序存储每个像素点 的颜色信息的保存方式获得的图片。 位图放大后会模糊失真,存储空间相对较大。 矢量图: 由图元组成,通过数学公式计算获得的图片。 放大后不会失真,占用空间小。
内容摘要 ■ 课程概述 ■ 教学安排 ■ 什么是操作系统? ■ 为什么学习操作系统? ■ 如何学习操作系统? ■ 操作系统实例
C语言程序设计 主讲教师:陆幼利.
微机系统的组成.
第四章 存储器管理 4.1 存储器的层次结构 4.2 程序的装入和链接 4.3 连续分配方式 4.4 基本分页存储管理方式
线段的有关计算.
顺序表的删除.
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
WPT MRC. WPT MRC 由题目引出的几个问题 1.做MRC-WPT的多了,与其他文章的区别是什么? 2.Charging Control的手段是什么? 3.Power Reigon是什么东西?
第二章 补充知识 2.1 总线和三态门 一、总线(BUS) 三总线结构 数据总线DB(Data Bus)
<编程达人入门课程> 本节内容 内存的使用 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ: QQ交流群: ,
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
实验三 16位算术逻辑运算实验 不带进位控制的算术运算 置AR=1: 设置开关CN 1 不带进位 0 带进位运算;
iSIGHT 基本培训 使用 Excel的栅栏问题
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
段式存储管理(Segmentation)
3.1.2 空间向量的数量积运算 1.了解空间向量夹角的概念及表示方法. 2.掌握空间向量数量积的计算方法及应用.
第五节 缓冲溶液pH值的计算 两种物质的性质 浓度 pH值 共轭酸碱对间的质子传递平衡 可用通式表示如下: HB+H2O ⇌ H3O++B-
第八章 总线技术 8.1 概述 8.2 局部总线 8.3 系统总线 8.4 通信总线.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
图片与视频数字化. 图片与视频数字化 图片分类 根据图片的构成元素来分 位图: 由像素组成,计算机按顺序存储每个像素点 的颜色信息的保存方式获得的图片。 位图放大后会模糊失真,存储空间相对较大。 矢量图: 由图元组成,通过数学公式计算获得的图片。 放大后不会失真,占用空间小。
基于列存储的RDF数据管理 朱敏
微机原理与接口技术 西安邮电大学计算机学院 宁晓菊.
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
第十七讲 密码执行(1).
第十二讲 密码执行(上).
FVX1100介绍 法视特(上海)图像科技有限公司 施 俊.
入侵检测技术 大连理工大学软件学院 毕玲.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
Presentation transcript:

计算机系统结构 (第9讲)

计算机系统结构 第一章 基本概念 第二章 指令系统 第三章 存储系统 第四章 输入输出系统 第五章 标量处理机 第六章 向量处理机 第一章 基本概念 第二章 指令系统 第三章 存储系统 第四章 输入输出系统 第五章 标量处理机 第六章 向量处理机 第七章 互连网络 第八章 并行处理机和 多处理机

第三章 存储系统 3.1 存储系统原理 3.2 虚拟存储器 3.3 高速缓冲存储器 (Cache) 3.4 三级存储系统 第三章 存储系统 现代计算机系统都以存储器为中心 在计算机运行过程中,存储器是各种信息存储和交换的中心 3.1 存储系统原理 3.2 虚拟存储器 3.3 高速缓冲存储器 (Cache) 3.4 三级存储系统

3.1 存储系统原理 什么是存储系统(存储体系、存储器层次) 为什么研究存储系统? 存储系统的性能指标如何表示? 如何构成存储系统? 3.1.1 存储系统的定义 3.1.2 存储器的层次结构 3.1.3 存储器的频带平衡

3.1.1 存储系统的定义 在一台计算机中,通常有多种存储器 种类:主存储器、Cache、通用寄存器、先行缓冲存储器、磁盘存储器、磁带存储器、光盘存储器等 材料工艺:ECL、TTL、MOS、磁表面、激光,SRAM,DRAM 访问方式:直接译码、先进先出、随机访问、相联访问、块传送、文件组

存储器的主要性能:速度、容量、价格 速度用存储器的访问周期、读出时间、频带宽度等表示 容量用字节B、千字节KB、兆字节MB和千兆字节GB等单位表示 价格用单位容量的价格表示,如$/bit 存储系统的关键是如何组织好速度、容量和价格均不相同的存储器,使这个存储器的速度接近速度最快的那个存储器,存储容量与容量最大的那个存储器相等,单位容量的价格接近最便宜的那个存储器。

1、存储系统(存储体系、存储层次)的定义 两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个存储系统。这个系统对应用程序员透明,并且,从应用程序员看,它是一个存储器,这个存储器的速度接近速度最快的那个存储器,存储容量与容量最大的那个存储器相等,单位容量的价格接近最便宜的那个存储器。

从外部看: M1 (T1, S1, C1) M2 (T2, S2, C2) Mn (Tn, Sn, Cn) T≈min(T1, T2, …, Tn), 用存储周期表示 S = max(S1, S2, …, Sn), 用MB或GB表示 C≈min(C1, C2, …, Cn), 用每位的价格表示

在一般计算机系统中主要有两种存储系统: Cache存储系统:由Cache和主存储器构成 主要目的:提高存储器速度 虚拟存储系统:由主存储器和磁盘存储器构成 主要目的:扩大存储器容量 从系统程序员的角度看, 速度接近Cache的速度 存储容量是主存的容量 每位价格接近主存储器 Cache 主存储器

虚拟存储系统 从应用程序员的角度看, 速度接近主存储器的速度 存储容量是虚拟地址空间 每位价格接近磁盘存储器 主存储器 磁盘存储器 2、存储系统的容量 要求: 存储系统的容量等于M2存储器的容量 提供尽可能大、能随机访问的地址空间

方法有两种: 只对M2存储器进行编址,M1存储器只在内部编址 另外设计一个容量很大的逻辑地址空间 3、存储系统的单位容量平均价格 计算公式: S2>>S1时, C≈C2, 但 S2与S1不能相差太大 M1 (S1, C1 , T1) M2 (S2, C2 , T2)

4、存储系统的速度 表示方法:访问周期、存取周期、存储周期、存取时间、读出时间等 命中率定义:在M1存储器中访问到的概率 N1: M1的访问次数 N2: M2的访问次数 访问周期与命中率的关系: T=HT1+(1-H)T2 当命中率H→1时,T→T1

存储系统的访问效率: 存储系统的访问效率主要与命中率和两级存储器的速度之比有关 例3.1: 假设T2=5T1,在命中率H为0.9和0.99两种情况下,分别计算存储系统的访问效率。 解: 当H=0.9时, e1=1/(0.9+5(10.9))=0.72

当H=0.99时, e2=1/(0.99=5(10.99))=0.96 提高存储系统速度的两条途径: 一是提高命中率H 二是两个存储器的速度不要相差太大 其中第二条有时做不到(如虚拟存储器),主要依靠提高命中率 例3.2: 在虚拟存储系统中,两级存储器的速度相差特别悬殊T2=105T1。如果要使访问效率e=0.9,问需要有多高的命中率?

解: 得: H=0.999998888877777...≈0.999999 5、采用预取技术提高命中率 方法:不命中时,把M2存储器中相邻几个单元组成的一个数据块都取出来送入M1存储器中。 计算公式: 0.9H+90000(1H)=1 89999.1H=89999 其中:H’是采用预取技术后的命中率;H是原来的命中率;n为数据块大小与

数据重复使用次数的乘积 证明: 采用预取技术之后,不命中率降低n倍: 也可以采用另外一种证明方法:在原有命中率计算公式中,把访问次数扩大到n倍,这时,由于采用了预取技术,命中次数为:nN1+(n1)N2 ,不命中次数仍为N2,因此新的命中率为:

例3.3: 在一个Cache存储系统中,当Cache的块大小为一个字时,命中率H=0.8;假设数据的重复利用率为5,计算块大小为4个字时,Cache存储系统的命中率是多少?假设T2=5T1,分别计算访问效率。 解: n=45=20, 采用预取技术后, 命中率提高到:

Cache块为1个字大时, H=0.8, 访问效率为: Cache块为4个字大时, H=0.99, 访问效率为: 例3.4: 在一个虚拟存储系统中,T2=105 T1,原来的命中率只有0.8,如果访问磁盘存储器的数据块大小为4K字,并要求访问效率不低于0.9,计算数据在主存储器中的重复利用率至少为多少?

解: 假设数据在主存储器中的重复利用率为m,根据前面的给出关系: 解方程组得m=44,即数据在主存储器中的重复利用率至少为44次。

3.1.2 存储器的层次结构 多个层次的存储器: Register Files  Buffers(Lookahead)  Cache  Main Memory  Online Storage  Off-line Storage 如下页图所示,如果用I表示层数,则有: 工作速度:Ti<Ti+1 存储容量:Si<Si+1 单位价格:Ci>Ci+1

通用寄存器堆 指令和数据缓冲 Cache (SRAM) 主存储器(DRAM) 联机外部存储器 脱机外部存储器 CPU 内部 每位的价格越来越便宜 存储容量越来越大 访问速度越来越快

各级存储器的主要性能特性 存储器层次 通用寄存器 缓冲栈 Cache 存储周期 < 10ns < 10ns 10 - 60ns 存储容量 < 512B < 512B 8K-2MB 价格$c/KB 1200 80 3.2 访问方式 直接译码 先进先出 相联访问 材料工艺 ECL ECL SRAM 分配管理 编译器分配 硬件调度 硬件调度 带宽 400-8000 400-1200 200-800 (待续)

各级存储器的主要性能特性(续) 存储器层次 主存储器 磁盘存储器 脱机存储器 存储周期 60-300ns 10 - 30ms 2 - 20 min 存储容量 32M-1GB 1G-1TB 5G-10TB 价格$c/KB 0.36 0.01 0.0001 访问方式 随机访问 块访问 文件组 材料工艺 DRAM 磁表面 磁、光等 分配管理 操作系统 系统/用户 系统/用户 带宽 80-160 10-100 0.2 - 0.6

CPU与主存储器的速度差距越来越大 1955年,第一台大型机IBM704,CPU和主存储器的工作周期均为12微秒,目前,CPU的工作速度提高了4个数量级以上,主存储器的工作速度仅提高两个数量级。 研究存储系统的目的就是要找出解决这一问题的办法。

3.1.3 频带平衡 计算机中各级存储器频带应该达到平衡 例如: 一台速度为500MIPS的计算机系统, 主存储器的各种访问源的频带宽度如下: CPU取指令: 500MW/s CPU取操作数和保存运算结果:1000MW/s 各种输入输出设备访问存储器:50MW/s 三项相加,要求存储器的频带宽度不低于1550MW/s, 访问周期不大于0.64ns, 实际上目前主存储器的工作周期为100ns左右, 两者相差150多倍。

计算机系统结构 (第10讲)

第三章 存储系统 3.1 存储系统原理 3.2 虚拟存储器 3.3 高速缓冲存储器 (Cache) 3.4 三级存储系统 第三章 存储系统 现代计算机系统都以存储器为中心 在计算机运行过程中,存储器是各种信息存储和交换的中心 3.1 存储系统原理 3.2 虚拟存储器 3.3 高速缓冲存储器 (Cache) 3.4 三级存储系统

3.3 高速缓冲存储器(Cache) 3.3.1 基本工作原理 3.3.2 地址映象与变换方法 3.3.3 Cache替换算法及其实现 3.3.1 基本工作原理 3.3.2 地址映象与变换方法 3.3.3 Cache替换算法及其实现 3.3.4 Cache的一致性问题 3.3.5 Cache的预取算法

Cache存储系统与虚拟存储系统比较 存储系统 Cache 虚拟存储器 要达到的目标 提高速度 扩大容量 实现方法 全部硬件 软件为主 硬件为辅 两级存储器速度比 3~10倍 105倍 页(块)大小 1~16字 1KB~16KB 等效存储容量 主存储器 虚拟存储器 透明性 对系统和 应用程序员 仅对应用 程序员 不命中时处理方式 等待主存储器 任务切换

3.3.1 基本工作原理 主存地址 来自CPU 块号B 块内地址W 未命中 主存/Cache 地址变换 已满 未满 命中 储器 替换块 Cache 装入块 数据送 CPU

3.3.2 地址映象与变换方法 地址映象: 把存放在主存中的程序按照某种规则装入到Cache中,并建立主存地址与Cache地址之间的对应关系 在选取地址映象方法要考虑的主要因素: 地址变换的硬件容易实现;地址变换的速度要快;主存空间利用率要高;发生块冲突的概率要小

1、全相联映象及其变换 映象规则:主存中的任意一块都可以映象到Cache中的任意一块。 如果Cache的块数为Cb,主存的块数为Mb,映象关系共有:Cb×Mb种。 用硬件实现非常复杂 在虚拟存储器中,全部用软件实现

块0 块0 块1 块1 …… …… 块i 块Cb-1 …… 块Mb-1 Cache 主存储器 全相联映象方式

主存地址 块号B 块内地址 块号b 块内地址w Cache地址 命中 相联比较 B b 主存块号B Cache块号b 有效位 目录表(由相联存储器组成,共Cb个字)

2、直接映象及其变换 映象规则:主存中一块只能映象到Cache的一个特定的块中。 计算公式:b=B mod Cb,其中: b为Cache的块号, B是主存的块号, Cb是Cache的块数。 整个Cache地址与主存地址的低位部分完全相同。

块0 …… 区0 块0 块Cb-1 块1 块Cb …… …… 区1 块Cb-1 块2Cb-1 …… Cache 块Mb-Cb …… 区Me-1 主存 储器 块Mb-1 直接相联映象方式

提高Cache速度的一种方法: 把区号存储器与Cache合并成一个存储器 直接映象方法的主要优点: 硬件实现很简单, 不需要相联访问存储器 访问速度也比较快, 实际上不做地址变换 直接映象方式的主要缺点: 块的冲突率较高

地址变换过程: 用主存地址中的块号B去访问区号存储器 把读出来的区号与主存地址中的区号E进行比较 比较结果相等, 且有效位为1, 则Cache命中 比较结果相等, 有效位为0, 表示Cache中的这一块已经作废 比较结果不相等, 有效位为0, 表示Cache中的这一块是空的 比较结果不相等, 有效位为1, 表示原来在Cache中的这一块是有用的

主存 地址 区号E 块号B 块内地址w 块号b 块内地址w Cache地址 块失效 命中 相等比较 比较相等且 有效位为1, 访问Cache E 1 区号E (按地址访问) 有效位 区表存储器

区号E 块号B 块内地址w 块号b 块内地址w 送CPU 访主存 相等 相等比较 1/w … 1 E D0 D1 …… Dw-1 有效位 区号 数据0 数据1 …… 数据w-1 按地址访问的Cache

3、组相联映象及其变换 映象规则: 主存和Cache按同样大小划分成块,还按同样大小划分成组 从主存的组到Cache的组之间采用直接映象方式 在两个对应的组内部采用全相联映象方式

组相联映象方式的优点: 块的冲突概率比较低 块的利用率大幅度提高 块失效率明显降低 组相联映象方式的缺点: 实现难度和造价要比直接映象方式高 地址变换过程: 用主存地址的组号G按地址访问块表存储器

把读出来的一组区号和块号与主存地址中的区号和块号进行相联比较 如果有相等的,表示Cache命中 如果没有相等的,表示Cache没有命中

主存 地址 区号E 组号G 组内块号B 块内地址W 组号g 组内块号b 块内地址w Cache地址 不等 相联比较 相等 相联比较 (Gb个块) E区号,组内块号B 组内块号b 块表

Cache替换算法要解决的问题: 1、记录每次访问Cache的块号 2、管理好所记录的Cache块号,为找出被替换的块号提供方便 3、根据记录和管理的结果,找出被替换的块号

计算机系统结构 (第11讲)

第三章 存储系统 3.1 存储系统原理 3.2 虚拟存储器 3.3 高速缓冲存储器 (Cache) 3.4 三级存储系统 第三章 存储系统 现代计算机系统都以存储器为中心 在计算机运行过程中,存储器是各种信息存储和交换的中心 3.1 存储系统原理 3.2 虚拟存储器 3.3 高速缓冲存储器 (Cache) 3.4 三级存储系统

3.2 虚拟存储器 1961年英国曼彻斯特大学Kilbrn等人提出 70年代广泛地应用于大中型计算机系统中 目前许多微型机也开始使用虚拟存储器 3.2.1 虚拟存储器工作原理 3.2.2 地址的映象和变换方法 3.3.3 加快内部地址变换速度的方法 3.3.4 页面替换算法及其实现方法 3.3.5 提高主存命中率的方法

3.2.1 虚拟存储器工作原理 把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的页,主存储器的页称为实页,虚拟存储器中的页称为虚页。 一个主存地址A由两部分组成,实页号p和页内偏移d 一个虚地址Av由三部分组成,用户号U、虚页号P和页内偏移D。

用户号U 虚页号P 页内偏移D 多用户虚拟地址Av的组成 实页号p 页内偏移d 主存地址A的组成 内部地址变换: 多用户虚拟地址Av变换成主存实地址A 多用户虚拟地址中的页内偏移D直接作为主存实地址中的页内偏移d 主存实页号p与它的页内偏移d直接拼接起来就得到主存实地址A

外部地址变换: 首先查外页表得到磁盘存储器实地址 把磁盘存储器实地址和主存储器实页号送入输入输出处理机 把要访问数据所在的一整页都从磁盘存储器调入到主存储器 3.2.2 地址的映象与变换 三种地址空间:虚拟地址空间,主存储器地址空间,辅存地址空间 地址映象: 把虚拟地址空间映象到主存地址空间

地址变换:在程序运行时,把虚地址变换成主存实地址 因地址映象和变换方法不同,有三种虚拟存储器:页式虚拟存储器、段式虚拟存储器、段页式虚拟存储器 1、段式虚拟存储器 地址映象方法:每个程序段都从0地址开始编址,长度可长可短,可以在程序执行过程中动态改变程序段的长度。

段号 段长 起址 主程序 (0段) 1k 8k 8k 1k 1 500 16k 9k 1段 2 200 9k 500 3 200 30k 16k 2段 200 30k 3段 程序 空间 200 主存储器

地址变换方法: 由用户号找到基址寄存器 从基址寄存器中读出段表的起始地址 把起始地址与多用户虚地址中段号相加得到段表地址 把段表中给出的起始地址与段内偏移D相加就能得到主存实地址

多用户 虚地址 用户号U 段号S 段内偏移D 主存实地址 As 1 6 As 2 1 3 n-1 4 段表 长度 段表 基址 段名 起始 地址 装入 位 段长 访问 方式 段表基址寄存器 一个用户(一道作业)的段表

段式虚拟存储器的主要优点: (1) 程序的模块化性能好 (2) 便于程序和数据的共享 (3) 程序的动态链接和调度比较容易 (4) 便于实现信息保护 段式虚拟存储器的主要缺点: (1) 地址变换所花费的时间比较长,做两次加法运算 (2) 主存储器的利用率往往比较低 (3) 对辅存(磁盘存储器)的管理比较困难

2、页式虚拟存储器 主要优点: (1) 主存储器的利用率比较高 (2) 页表相对比较简单 (3) 地址变换的速度比较快 (4) 对磁盘的管理比较容易 主要缺点: (1) 程序的模块化性能不好 (2) 页表很长,需要占用很大的存储空间。例如:虚拟存储空间4GB,页大小1KB,则页表的容量为4M字,16MB

页号 主存页号 0页 1 1页 2 2页 3 页表 3页 用户程序 主存储器 页式虚拟存储器的地址映象

用户号U 虚页号P 页内偏移D 实页号p 页内偏移d Pa Pa 2 p 装入 修改 主存页号 标志 页表基址 页表

3、段页式虚拟存储器 用户按照程序段来编写程序,每个程序段分成几个固定大小的页。 地址变换方法: (1) 先查段表,得到该程序段的页表起始地址和页表长度, (2) 再查页表找到要访问的主存实页号, (3) 最后把实页号p与页内偏移d拼接得到主存的实地址。

用户号U 段号S 虚页号P 页内偏移 实页号p 页内偏移 As A As 1 0/1 Ap 1 p 0/1 装入 修改 页表 地址 装入 实页号 修改 标志

4、外部地址变换 在操作系统中,把页面失效当作一种异常故障来处理。 每个用户程序都有一张外页表,虚拟地址空间中的每一页或每个程序段,在外页表中都有对应的一个存储字。 每一个存储字除了磁盘存储器的地址之外,至少还包括一个装入位。

多用户 虚地址 用户号 虚页号 页内偏移 磁盘号 柱面号 磁头号 块号 外部地址 变换(软 件实现) 1 装入 磁盘实地址 外页表

3.2.3 加快内部地址变换的方法 造成虚拟存储器速度降低的主要原因: (1) 要访问主存储器须先查段表或页表 (2) 可能需要多级页表 页表级数的计算公式: 其中: Np为页面的大小 Nv为虚拟存储空间大小 Nd为一个页表存储字的大小 例如:虚拟存储空间大小Nv=4GB,页的大小Np=1KB,每个页表存储字占

用4个字节。计算得到页表的级数: 25625664=4M字 通常把1级页表驻留在主存储器中,2、3级页表只驻留一小部分在主存。 1、目录表 基本思想:用一个小容量高速存储器存放页表。

地址变换过程:把多用户虚地址中U与P拼接起来,相联访问目录表。读出主存实页号p,把p与多用户虚地址中的D拼接得到主存实地址。如果相联访问失败,发出页面失效请求。 主要优点:与页表放在主存中相比,查表速度快。 主要缺点:可扩展性比较差。 主存储器容量增加时,目录表的造价高,速度降低。

多用户 虚地址 用户号U 虚页号P 页内偏移D 实页号p 页内偏移d 主存实地址 相联访问 U, P p 0/1 多用户虚页号 实页号 修改 其它标志 目录表(按内容访问的相联存储器)

2、快慢表 快表TLB(Translation Lookaside Buffer): 小容量(几~几十个字),高速硬件实现,采用相联方式访问 慢表:当快表中查不到时,从存放在主存储器中的慢表中查找 按地址访问,用软件实现。 快表与慢表也构成了一个两级存储系统。

多用户 虚地址 用户号U 虚页号P 页内偏移D 实页号p 页内偏移d 主存实地址 1 p U, P p 装入 实页号 多用户虚页号 实页号 慢表 快表(按内容相联访问)

3、散列函数 目的:把相联访问变成按地址访问,从而加大快表容量 散列(Hashing)函数:Ah=H(Pv), 20位左右  5~8位 采用散列变换实现快表按地址访问 避免散列冲突:采用相等比较器 地址变换过程:相等比较与访问存储器同时进行

多用户 虚地址 用户号U 虚页号P 页内偏移D 实页号p 页内偏移d 多用户虚页号 主存实地址 快表 命中 相等比较 散列变 换(硬 件实现) 查慢表 Pv p Ah 快表地址 多用户虚页号 实页号 按地址访问的快表

5、虚拟存储器举例 例3.7: IMB370/168计算机的虚拟存储器快表结构及地址变换过程。虚拟地址长36位,页面大小为4KB,每个用户最多占用4K个页面,最多允许16G个用户,但同时上机的用户数一般不超过6个。 采用了两项新的措施: 一是采用两个相等比较器 二是用相联寄存器组把24位用户号U压缩成3位

计算机系统结构 (第12讲)

3.2.4 页面替换算法及其实现方法 页面替换发生时间: 当发生页面失效时,要从磁盘中调入一页到主存。如果主存所有页面都已经被占用,必须从主存储器中淘汰掉一个不常使用的页面,以便腾出主存空间来存放新调入的页面。 评价页面替换算法好坏的标准: 一是命中率要高 二是算法要容易实现

页面替换算法的使用场合: (1) 虚拟存储器中,主存页面的替换,一般用软件实现 (2) Cache块替换一般用硬件实现 (3) 虚拟存储器的快慢表中,快表存储字的替换,用硬件实现 (4) 虚拟存储器中,用户基地址寄存器的替换,用硬件实现 (5) 在有些虚拟存储器中目录表的替换 1、页面替换算法 (1) 随机算法(RAND Random algorithm):

算法简单,容易实现; 没有利用历史信息,没有反映程序的局部性,命中率低。 (2) 先进先出算法 (FIFO First-In First-Out algorithm): 比较容易实现,利用了历史信息,没有反映程序的局部性。 最先调入主存的页面,很可能也是经常要使用的页面。 (3) 近期最少使用算法 (LFU Least Frequently Used algorithm):

既充分利用了历史信息,又反映了程序的局部性,实现起来非常困难。 (4) 最久没有使用算法 (LRU Least Recently Used algorithm): 把LRU算法中的“多”与“少”简化成“有”与“无”,实现起来比较容易。 (5) 最优替换算法 (OPT OPTimal replacemant algorithm): 是一种理想化的算法。用来作为评价其它页面替换算法好坏的标准。 在虚拟存储器中,实际上有可能采用只有FIFO和LRU两种算法。

例3. 8: 一个程序共有5个页面组成,程序执行过程中的页地址流如下: 例3.8: 一个程序共有5个页面组成,程序执行过程中的页地址流如下: P1, P2, P1, P5, P5, P1, P3, P4, P3, P4 假设分配给这个程序的主存储器共有3个页面。给出FIFO、LRU、OPT 三种页面替换算法对这3页主存的使用情况,包括调入、替换和命中等。

例3.9: 一个循环程序,依次使用P1,P2,P3,P4四个页面,分配给这个程序的主存页面数为3个。FIFO、LRU和OPT三种页面替换算法对主存页面的调度情况如下图所示。在FIFO和LRU算法中,总是发生下次就要使用的页面本次被替换出去的情况,这就是“颠簸”现象。

2、堆栈型替换算法 定义: 对任意一个程序的页地址流作两次主存页面数分配,分别分配m个主存页面和n个主存页面,并且有m≤n。如果在任何时刻t,主存页面数集合Bt都满足关系:Bt(m) Bt(n),则这类算法称为堆栈型替换算法。

3.2.5 提高主存命中率的方法 堆栈型算法的基本特点: 随着分配给程序的主存页面数增加,主存的命中率也提高,至少不下降。 影响主存命中率的主要因素: (1) 程序执行过程中的页地址流分布情况 (2) 所采用的页面替换算法 (3) 页面大小 (4) 主存储器的容量 (5) 所采用的页面调度算法 以下,对后三个因素进行分析

1、页面大小与命中率的关系 页面大小为某个值时,命中率达到最大。 页面大小与命中率关系的解释:   假设At和At+1是相邻两次访问主存的逻辑地址,d=|At-At+1|。   如果d<Sp,随着Sp的增大,At和At+1在同一页面的可能性增加,即H随着Sp的增大而提高。   如果d>Sp,At和At+1一定不在同一个页面内。随着Sp的增大,主存页面数减少,页面替换将更加频繁。H随着Sp的增大而降低。

  当Sp比较小的时候,前一种情况是主要的,H随着Sp的增大而提高。   当Sp达到某一个最大值之后,后一种情况成为主要的,H随着Sp的增大而降低。   当页面大小增大时,造成的浪费也要增加。   当页面大小 减小时,页表和 页面表在主存储 器中所占的比例 将增加。 页面大小 SP 命中率 H 1 S 2S

2、主存容量与命中率的关系 主存命中率H随着分配给该程序的主存容量S的增加而单调上升。 在S比较小的时候, H提高得非常快。 随着S的逐渐增 加,H提高的速 度逐渐降低。当 S增加到某一个 值之后,H几乎 不再提高。 命中率 H 主存容量S 1.0

3、页面调度方式与命中率的关系 请求式: 当使用到的时候,再调入主存 预取式:   在程序重新开始运行之前,把上次停止运行前一段时间内用到的页面先调入到主存储器,然后才开始运行程序。   可以避免在程序开始运行时,频繁发生页面失效的情况。   如果调入的页面用不上,浪费了调入的时间,占用了主存资源。

Cache存储系统与虚拟存储系统比较 存储系统 Cache 虚拟存储器 要达到的目标 提高速度 扩大容量 实现方法 全部硬件 软件为主 硬件为辅 两级存储器速度比 3~10倍 105倍 页(块)大小 1~16字 1KB~16KB 等效存储容量 主存储器 虚拟存储器 透明性 对系统和 应用程序员 仅对应用 程序员 不命中时处理方式 等待主存储器 任务切换

第三章 存储系统 3.1 存储系统原理 3.2 虚拟存储器 3.3 高速缓冲存储器 (Cache) 3.4 三级存储系统 第三章 存储系统 现代计算机系统都以存储器为中心 在计算机运行过程中,存储器是各种信息存储和交换的中心 3.1 存储系统原理 3.2 虚拟存储器 3.3 高速缓冲存储器 (Cache) 3.4 三级存储系统

3.4 三级存储系统 在大部分计算机系统中,既有虚拟存储器,也有Cache存储系统。 存储系统可以有多种构成方法 不同的构成只是实现技术不同 3.4 三级存储系统 在大部分计算机系统中,既有虚拟存储器,也有Cache存储系统。 存储系统可以有多种构成方法 不同的构成只是实现技术不同 速度接近Cache 的速度,存储容 量是主存的容量 每位价格接近主 存储器 主存储器 Cache 系统程序员看 Cache存储系统

速度接近主存储 器的速度,存储 容量是虚拟地址 空间,每位价格 接近磁盘存储器 磁盘 存储器 主存 储器 应用程序员看 虚拟存储系统 Cache Cache 主存储器 磁盘存储器 磁盘存储器 一种三级存储系统 一种新的二级存储系统

存储系统的几种组织方式: 1、两个存储系统的组织方式:物理地址Cache存储系统;目前的大部分处理机均采用这种两级存储系统。 CPU 虚拟 地址 物理 地址 物理地址 MMU Cache 主存 储器 数据或指令

2、一个存储系统组织方式:虚拟地址Cache存储系统;如Intel公司的i860等处理机采用这种组织方式。 3、全Cache系统。没有主存储器,Cache-磁盘存储系统。 物理 地址 CPU 虚拟地址 MMU 主存 储器 数据 或指令 Cache 数据或指令

本 章 重 点 1、存储系统的定义及主要性能 2、并行存储器和无冲突访问存储器的工 作原理 3、虚拟存储系统的工作原理 4、虚拟存储器中加快地址变换的方法 5、虚拟存储系统的页面替换算法

6、Cache存储系统地址映象及变换方法 7、Cache存储系统的块替换算法 练习题: 3.1 3.2 3.3 3.7 3.8 3.13 3.15 3.18 3.19