0521《计算机系统结构》 2018年6月期末考试指导
发布时间:2023-11-21 12:11:15浏览次数:310521《计算机系统结构》2018 年 6 月期末考试指导一、考试说明(一)说明:考试为闭卷,试卷满分为 100 分,考试时间 90 分钟。(二)题型及各题型所占分数和相应的答题技巧1.单项选择题(每题 2 分,共 5 题,总计 10 分)答题技巧:选择与题干相匹配的答案。可以考虑排除法等选择技巧。2.简答题(每题 10 分,共 4 题,总计 40 分)答题技巧:需要答出与问题相关的重要知识点(即讲义与课件中的知识点),如需要,可对相关内容展开阐述。2.分析题(每题 15 分,共 2 题,总计 30 分)答题技巧:需要分析与问题相关的重要知识点(即讲义与课件中的知识点),并对相关内容展开阐述。3.计算题(每题 20 分,共 1 题,总计 20 分)答题技巧:选择可以解决问题的计算方法,注意不要计算错误。二、重点内容第一章 基本概念1. 计算机系统的层次结构计算机系统可分为 7 个层次,由第 0 层到第 6 层依次是: 硬联逻辑、微程序、及其语言、操作语言、汇编语言、高级语言、应用语言。2. 计算机体系结构:计算机体系结构是程序员所看到的计算机属性,即概念性结构与功能特性。(Amdahl 提出的系统结构实际上指传统机器语言级程序员所能看到的计算机属性。) 3. 软硬件取舍从改进性能考虑的软硬件取舍基本方法:加快经常性事件的执行速度 Amdahl 定律:系统中某一部件由于采用更快的执行方式后,整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关。 在 Amdahl 定律中,加速比与两个因素有关:改进后整个任务的执行时间为: 其中:T0为改进前的整个任务的执行时间。 改进后整个系统的加速比达到: 其中:Fe 表示可改进部分所占的百分比,
(1)CPU 与外围设备能够并行工作。(2)能够处理例外事件。(3)数据的输入和输出都要经过 CPU。(4)用于连接低速外围设备。 (3)直接存储器访问方式直接存储器访问方式(DMA:Direct Memory Access),主要用来连接高速外围设备。如磁盘存储器,磁带存储器、光盘辅助存储器,行式打印机等。DMA 方式具有如下特点:(1)外围设备的访问请求直接发往主存储器,数据的传送过程不需要 CPU 的干预。(2)全部用硬件实现,不需要做保存现场和恢复现场等工作。(3)DMA 控制器复杂,需要设置数据寄存器、设备状态控制寄存器、主存地址寄存器、设备地址寄存器和数据交换个数计数器及控制逻辑等。(4)在 DMA 方式开始和结束时,需要处理机进行管理。 2. 中断系统的软硬件分配(1)主要考虑的两个因素:中断响应时间:中断响应时间是一个非常重要的指标。灵活性:硬件实现速度快,灵活性差;软件实现正好相反(2)中断处理过程(3)中断响应时间定义:从中断源向处理机发出中断服务请求开始,到处理机开始执行这个中断源的中断服务程序时为止,这一段时间称为中断响应时间。影响中断响应时间的因素主要有 4 个: (前 2 个属于处理机设计,后 2 个属于中断系统)I最长指令执行时间有些指令的执行时间很长,甚至无法预测。II处理其它更紧急的任务所用时间 如处理 DMA 请求等。III从第一次关 CPU 中断到第一次开 CPU 中断所经历的时间中断系统的软件与硬件功能分配,主要就是要考虑这一段内要所的事情用软件来实现,还是用硬件来实现。 IV通过软件找到中断服务程序入口所用时间主要是第 1 和第 3 两部分。其中,第 1 部分是指令系统设计时考虑的问题,在中断系统的设计中,主要考虑第 3 部分。3. 中断屏蔽设置中断屏蔽有三个用处:(1)在中断优先级由硬件确定了的情况下,改变中断源的中断服务顺序。(2)决定设备是否采用中断方式工作。(3)在多处理机系统中,把外围设备的服务工作分配到不同的处理机中。中断屏蔽的实现方法主要有两种: 方法一:每级中断源设置一个中断屏蔽位。方法二:改变处理机优先级4. 通道中的数据传送过程字节多路通道的数据传送过程:
选择通道的数据传送过程:数组多路通道的数据传送过程:5. 通道流量分析通道流量:单位时间内能够传送的最大数据量。又称通道吞吐率,通道数据传输率等。通道最大流量:通道在满负荷工作状态下的流量。通道流量与连接在通道上的设备的数据传输率的关系如下:
三种通道的最大流量计算公式: 为 保 证通 道 不 丢 失 数 据, 通 道 的 实 际 流 量 应 不大 于 通 道 最 大 流量 : fBYTE ≤ fMAX·BYTEfSELETE≤fMAX·SELETE fBLOCK≤fMAX·BLOCK6. 输入输出处理机的作用通道处理机存在的问题:(1) 每完成一次输入输出操作要两次中断 CPU 的现行程序。(2) 通道处理机不能处理自身及输入输出设备的故障。(3) 数据格式转换、码制转换、数据块检验等工作要 CPU 完成。(4) 文件管理、设备管理等工作,通道处理机本身无能为力。输入输出处理机除了能够完成通道处理机的全部功能之外,还具有如下功能:(1) 码制转换。(2) 数据校验和校正。(3) 故障处理。(4) 文件管理。(5) 诊断和显示系统状态。(6) 处理人机对话。(7) 连接网络或远程终端。7. 输入输出处理机的种类根据是否共享主存储器分为:(1)共享主存储器的输入输出处理机。 CDC 公司的 CYBER,Texas 公司的 ASC,(2)不共享主存储器的输入输出处理机。 STAT-100 巨型机根据运算部件和指令控制部件是否共享分为:(1) 合用同一个运算部件和指令控制部件。 造价低,控制复杂。如 CDC-CYBER 和 ASC(2) 独立运算部件和指令控制部件。 独立运算部件和指令控制部件已经成为主流。 如 B-6700 大型机和 STAT-100 巨型机等。第五章 标量处理机流水线技术:是指将一个重复的时序过程,分解为若干个子过程,而每一个子过程都可有效地在其专用功能段上与其它子过程同时执行。1. 线性流水线的性能分析主要指标:吞吐率、加速比和效率
吞吐率:是指单位时间内流水线所完成的任务数或输出结果的数量。流水线吞吐率的最基本公式: 计算加速比的基本公式:计算流水线效率的一般公式:2. 非线性流水线的调度非线性流水线调度的任务是要找出一个最小的循环周期,按照这周期向流水线输入新任务,流水线的各个功能段都不会发生冲突,而且流水线的吞吐率和效率最高。3. 数据相关数据相关:在执行本条指令的过程中,如果用到的指令、操作数、变址量等是前面指令的执行结果,这种相关称为数据相关。 控制相关:由条件分支指令、转子程序指令、中断等引起的相关。 可以采取静态分支预测技术、动态分支预测技术、提前形成条件码等来解决控制相关。解决数据相关的方法有两种:推后处理;设置专用路径。4. 动态分支预测技术动态转移预测技术的两个关键问题: 如何记录转移历史信息如何根据记录的转移历史信息预测转移方向 记录转移历史信息的方法有三种: (1)最近一次或几次转移是否成功的信息记录在转移指令中 (2)用一个高速缓冲栈保存条件转移指令的转移目标地址 (3)用 Cache 保存转移目标地址之后的 n 条指令 5. 静态分支预测技术软件“猜测法”; 硬件“猜测法”;两个先行指令缓冲栈6. 乱序流动中的数据相关在乱序流动方式中,可能发生三种数据相关:(1)写读相关:指令 k 与指令 k+1 之间关于 F1 的相关,又称为数据相关、先写后读相关、流相关、WR 相关、RAW 相关等。(2)读写相关:指令 k+1 与指令 k+2 之间关于 F1 的相关,变量名相关、先读后写相关、反相关、RW 相关、WAR 相关等。(3)写写相关:指令 k 与指令 k+2 左边的 F1 之间的相关关系称为:输出相关、写写相关、WW相关、WAW 相关或写后再写相关等。7. 单发射与多发射(1)单发射处理机:每个周期只取一条指令、只译码一条指令,只执行一条指令,只写回一个运算结果。 取指令部件和指令译码部件各设置一套;只设置一个多功能操作部件或设置多个独立的操作部件;操作部件中可以采用流水线结构,也可以不采用流水线结构。
目标是每个时钟周期平均执行一条指令,ILP 的期望值为 1。(2)多发射处理机每个周期同时取多条指令、同时译码多条指令,同时执行多条指令,同时写回多个运算结果。多个取指令部件,多个指令译码部件和多个写结果部件。设置多个指令执行部件,有些指令执行部件采用流水线结构。目标是每个时钟周期平均执行多条指令,ILP 的期望值大于 1。8. 超标量处理机有两条或两条以上能同时工作的指令流水线先行指令窗口:能够从指令 Cache 中预取多条指令,能够对窗口内的指令进行数据相关性分析和功能部件冲突检测。超标量处理机性能:单流水线普通标量处理机的指令级并行度记作(1, 1),超标量处理机的指令级并行度记作(m, 1),超流水线处理机的指令级并行度记作(1, n),而超标量超流水线处理机的指令级并行度记作(m, n)。在理想情况下,N 条指令在单流水线标量处理机上的执行时间为: T(1, 1)=(k+N-1)Dt9. 超流水线处理机典型处理机结构MIPS R4000 处理机: 每个时钟周期包含两个流水段 是一种很标准的超流水线处理机结构。指令流水线有 8 个流水段。指令 Cache 和数据 Cache 的容量各 8KB,每个时钟周期可以访问 Cache 两次,在一个时钟周期内可以从指令 Cache 中读出两条指令,从数据 Cache 中读出或写入两个数据。主要运算部件有整数部件和浮点部件。超流水线处理机性能指令级并行度为(1,n)的超流水线处理机,执行 N 条指令所的时间为:超流水线处理机相对于单流水线普通标量处理机的加速比为: 加速比的最大值为:S(1, n)MAX=n 第六章 向量处理机1. 向量的表示方法等间距向量表示法:三个参数表示一个等间距向量:向量起始地址:A向量长度:L向量间距:f带位移量的向量表示法:用三个参数表示一个向量:
向量基地址:A 向量长度:L 向量位移量:f向量有效长度:L-f 向量起始地址:A+f稀疏向量表示法:定义:0 元素很多,非 0 元素很少的向量称为稀疏向量采用压缩方法存储稀疏向量可以节省存储空间。可以还原之后进行运算,也可以用压缩方法直接进行运算2. 向量链接技术当前一条指令的结果寄存器可以作为后继指令的操作数寄存器时,多条有数据相关的向量指令并行执行,这种技术称为两条流水线的链接技术。实现链接的条件:(1)没有向量寄存器冲突和运算部件冲突。(2)只有第一个结果送入向量寄存器的那一个 周期可以链接。(3)先行的两条指令产生运算结果的时间必须 相等。(4)两条向量指令的向量长度必须相等。3. 向量递归技术向量指令一般为 3 地址,但递归运算用两地址。用递归向量技术求和: V0¬V0+V1C0 和 C1 分别是与向量寄存器 V0 和 V1 相关的分量计数器。初始时,计数器 C0 和 C1 都置成0,V00中的初始值也置成 0。浮点加法流水线的延迟时间为 8 个周期。假定向量长度为 64,只作一个向量循环。在开始的 8 个周期,计数器 C0 一直为 0,在此之后,每个周期期加 1。C1 每个周期加 1。4. 向量处理机的性能评价衡量向量处理机性能的主要指标有:向量指令处理时间 Tvp、最大性能 R¥、半性能向量长度 n1/2等。 三、重点习题(一)单项选择题1、对于线性流水,在每段经过的时间相等的情况下,流水线的效率与( )成正比。A、任务数, B、流水线段数, C、吞吐率, D、排空时间2、下面哪个页面替换算法实际上是不能够实现的?( )A、随机页面替换算法 B、先进先出替换算法 C、最久没有使用算法 D、最优替换算法3、在计算机系统中,表征系统运行状态的部件是( )。 A、程序计数器 B、累加计数器 C、中断计数器 D、程序状态字(PSW)4、存储器读写速率越高,每位的成本也越高,存储容量也小。解决这一问题的主要方法是采用( )。A、Cache B、并行存储器 C、多级存储体系结构 D、缓冲技术(二)简答题
1、简述加速内部地址变换的方法。2、简述堆栈型替换算法的过程。3、什么是指令级并行?4、简述 Cache 地址映像的方法。(二)分析题1、程序中有哪两类相关,分别可以采取什么方法来解决?(三)计算题1、设计指令存储器有两种方案:一是采用价格较贵的高速存储器芯片,另一种是采用价格便宜的低速存储芯片。采用后一方案时,用同样的经费可使存储器总线带宽加倍,从而每隔2 个时钟周期就可取出 2 条指令(每条指令为单字长 32 位);而采用前一方案时,每个时钟周期存储器总线仅取出 1 条单字长指令。由于访存空间局部性原理,当取出 2 个指令字时,通常这 2 个指令字都要使用,但仍有 25%的时钟周期中,取出的 2 个指令字中仅有 1 个指令字是有用的。试问采用这两种实现方法所构成的存储器带宽为多少?(令 f 代表时钟频率T=1/f 代表时钟周期)四、重点习题答案(答案仅供参考)(一)单项选择题1.C 2.D 3.D 4.C(一)简答题1、答:加速内部地址变换方法:(1)目录表:用一个小容量高速存储器存放页表;(2)快慢表:快表、慢表构成一个两级存储系统;(3)散列函数:把相联访问变成接地址访问。2、答:堆栈型替换算法:对任意一个程序的页地址流作两次主存页面数分配,分别分配 m个主存页面和 n 个主存页面,并且 m≤n 。如果在任何时刻 t 主存页面数集合 Bt 都满足关系:Bt(m)≤Bt(n),则这类算法成为堆栈型替换算法。3、 当指令之间不存在相关时,它们在流水线中时可以重叠起来并行执行的,这种指令序列中存在的潜在并行性称为指令级并行。4、 Cache 地址映像方法:1)全相联映像;2)直接映像;3)组相联映像;4)位选择组相联映像;5)段相联映像(二)分析题1、答:1)数据相关:数据相关指在执行本条指令的过程中,如果用到的指令、操作数、变址偏移量等是前面指令的执行结果,则必须等待前面的指令执行完成,并把结果写到主存或通用寄存器中之后,本条指令才能开始执行;2)控制相关:控制相关指由条件分支指令、转子程序指令、中断等引起的相关。可以采取静态分支预测技术、动态分支预测技术、提前形成条件码等来解决控制相关。(三)计算题1、答:记 f ── 时钟频率,T=1/f ── 时钟周期,B ── 带宽(Byte/s)。32 位=4 个字节
方案一:方案二:说明:本考试指导只适用于 201803 学期 6 月期末考试使用。指导中的章节知识点涵盖考试所有内容,给出的习题为考试类型题,习题答案要点只作为参考,详见课程讲义或笔记。如果在复习中有疑难问题请到课程答疑区提问。最后祝大家考试顺利!)/(4411sBytefTB )/(5.3421%252%752sBytefTB
(1-Fe)表示不可改进部分所占的百分比, Se 表示改进后,可改进部分的加速比。4. 冯·诺依曼结构包括:输入设备、存储器、运算器、控制器、输出设备。特点: 存储程序、运算器为中心、集中控制现代处理机对冯·诺依曼结构的改进 不变的:存储程序 改变的:存储器为中心, 总线结构, 分散控制 从基于串行算法变为适应并行算法,出现了向量计算机,并行计算机、多处理机等;流水线处理机,超标量处理机,超流水线处理机,超标量超流水线处理机;数据库计算机和知识库计算机;专用计算机,如 FFT 变换机、过程控制计算机;为获得高可靠性而研制容错计算机;功能分散化、专业化,出现了各种分布计算机、外围处理机、通信处理机等。5. 透明性:本来是存在的事物或属性,但从某种角度看又好像不存在的概念称为透明性(transparency),在一个计算机系统中,低层机器的属性对高层机器的程序员往往是透明的,如传统机器级的概念性结构和功能特性,对高级语言程序员来说是透明的。系列机的软件兼容方式:软件兼容有(向上兼容)和(向下兼容)之分,又有(向前兼容)和(向后兼容)之分。系列机软件必须保证(向后兼容),力争(向上兼容)。兼容机:不同制造商生产的具有相同系统结构的计算机。系列机:在一个厂家内生产的具有相同的体系结构,但具有不同组织和实现的一系列不同型号的机器。软件兼容:同一个软件可以不加修改第运行于体系结构相同的各档及其,而且它们所获得的结果一样,差别只在于运行时间不同。6. 计算机系统的分类按大小划分:巨型、大型、中型、小型、微型机 按用途划分:科学计算、事务处理、实时控制、工作站、服务器、家用计算机等。按数据类型划分:定点计算机、浮点计算机、向量计算机、堆栈计算机等按处理机个数和种类划分:单处理机;并行处理机、多处理机、分布处理机;关联处理机;超标量处理机, 超流水线处理机, VLIW 处理机;SMP(对称多处理机)、MPP(大规模并行处理机)、机群(Cluster)系统等 按使用的器件划分计算机系统的时代: 第一代:电子管(Valve)计算机 第二代:晶体管(Transistor)计算机 第三代:集成电路(LSI)计算机 第四代:大规模集成电路(VLSI)计算机 按照指令流和数据流的多倍性特征进行分类: (1)单指令流单数据流 SISD(Single Instruction Single Datastream) (2)单指令流多数据流 SIMD(Single Instruction Multiple Datastream) (3)多指令流单数据流 MISD(Multiple Instruction Single Datastream) (4)多指令流多数据流 MIMS(Multiple Instruction Multiple Datastream)第二章 指 令 系 统
1. 浮点数的表示方式• 两个数值: 尾数 m:数制(小数或整数)和码制(原码或补码) 阶码 e:整数, 移码(偏码、增码、余码)或补码• 两个基值: 尾数基值 rm:2、4、8、16 和 10 进制等 阶码基值 re: 通常为 2 进制• 两个字长:长度和物理位置,均不包括符号位 尾数长度 p:尾数部分按基值计算的长度阶码长度 q:阶码部分的二进制位数 2. 浮点数格式设计定义浮点数格式的 6 个参数,确定原则如下:• 尾数:多数机器用原码、小数表示 采用原码表示:加减法比补码表示复杂,乘除法比补码简单,而且非常直观。 采用小数表示能简化运算,特别是乘法和除法运算。• 阶码:一般机器用整数、移码表示 采用移码表示的主要原因是:浮点 0 与机器 0 一致。阶码进行加减运算时,移码的加减法运算要比补码复杂 。• 基值: 尾数的基值 rm=2, 阶码的基值 re=2,• 采用隐藏位表示方式能够使规格化浮点数的表数效率达到 100%(当 rm=2 时)• 浮点数格式设计的关键问题是: 在表数范围和表数精度给定的情况下,如何确定最短的尾数字长 p 和阶码字长 q,并根据总字长的要求,恰当分配 p 与 q 。3. 浮点数的舍入处理• 浮点数要进行舍入处理的原因是:(1)十进制数转化为浮点数时,有效位长度超过给定的尾数字长。(2)两个浮点数的加减乘除结果,尾数长度超过给定的尾数字长。• 舍入处理要解决的问题是:把规格化尾数的 p+g 位处理成只有 p 位。其中:p 是浮点数表示方式给定的尾数字长, g 是超过给定尾数字长的部分。• 舍入方法的主要性能标准是:绝对误差小, 积累误差小, 容易实现。• 进行舍入处理时要注意的问题是: 必须先规格化,然后再舍入,否则舍入是没有意义的。 在计算积累误差时,要同时考虑到正数区和负数区的情况。4. 关于舍入方法的主要结论• 恒置法虽有少量的积累误差,且损失一位精度,但由于实现很容易,普遍在小型微型机中使用。
• R*舍入法是唯一积累误差能达到完全平衡的舍入方法,但由于实现非常复杂,仅在少数对误差要求非常高的机器中采用。• 下舍上入法只有少量积累误差,且精度比较高,但实现很复杂,用于软件实现的算法中。• 查表法实现比较容易,积累误差很小,且可以通过改变 ROM 或 PLA 中的内容来修正积累误差,是一种很有前途的舍入方法。 5. 警戒位的设置方法• 在规定的尾数字长之外,运算器中的累加器需要另外增加的长度称为警戒位(GuardBit) • 不设置警戒位,可能出现很大的误差• 警戒位的用处只有两个: (1) 用于左规格化时移入尾数有效字长内。(2) 用于舍入。• 警戒位的来源有以下几个方面: (1) 做加、减法时,因对阶从有效字长内移出去的部分。(2) 做乘法时,双倍字长乘积的低字长部分。(3) 做除法时,因没有除尽而多上商的几位。(4) 右规格化时移出有效字长的那部分。(5) 从十进制转换成二进制时,尾数超出有效字长的部分。 加减法运算对警戒位的需要(1) 同号相加或异号相减,浮点数的尾数之和不需要左规格化,因此不必设置警戒位。(2) 同号相减或异号相加,阶差为 0,(3) 同号相减或异号相加,阶差为 1,只需要设置一位警戒位。(4) 同号相减或异号相加,阶差大于等于 2,只需一位警戒位。6. 自定义数据表示一般处理机中的数据表示方法:• 数据存储单元(寄存器、主存储器、外存储器等)只存放纯数据,数据的属性通过指令中的操作码来解释: 数据的类型,如定点、浮点、字符、字符串、逻辑数、向量等; 进位制,如 2 进制、10 进制、16 进制等; 数据字长,如字、半字、双字、字节等; 寻址方式,如直接寻址、间接寻址、相对寻址、寄存器寻址等; 数据的功能,如地址、地址偏移量、数值、控制字、标志等; 同一种操作(如加法)通常有很多条指令。• 在高级语言和应用软件中: 数据的属性由数据自己定义; 在高级语言与机器语言之间的语义差距,要靠编译器等填补。7. 编址方式主要内容:编址单位、零地址空间个数、并行存储器的编址、输入输出设备的编址 间接寻址方式与变址寻址方式。8. 定位方式 直接定位方式:在程序装入主存储器之前,程序中的指令和数据的主存物理就已经确定了的称为直接定位方式。
静态定位:在程序装入主存储器的过程中随即进行地址变换,确定指令和数据的主存物理地址的称为静态定位方式。 动态定位:在程序执行过程中,当访问到相应的指令或数据时才进行地址变换,确定指令和数据的主存物理地址的称为动态定位方式。 动态定位方式的优点:1)在程序开始执行前,不一定要把整个程序都调入到主存中,而且,一个程序可以被分配在多个不连续的主存物理空间内,从而,可以使用较小的主存分配单位,以提高主存储器的利用率。2)几个程序可以共享存放在主存中的同一程序段,而不必在主存中存放多个副本。3)支持虚拟存储器。9. 指令格式的优化设计主要目标:节省程序的存储空间;指令格式尽量规整,便于译码10. 基本指令系统通用计算机必须有5类基本指令:数据传送类指令运算类指令; 程序控制指令;输入输出指令;处理机控制和调试指令。11. RISC 思想减少 CPI 是 RISC 思想的精华。程序执行时间的计算公式: P=I· CPI · T 其中: P是执行这个程序所使用的总的时间; I是这个程序所需执行的总的指令条数; CPI(Cycles Per Instruction)是每条指令执行的平均周期数; T是一个周期的时间长度。 硬件方面: 采用硬布线控制逻辑 减少指令和寻址方式的种类 使用固定的指令格式 采用 LOAD/STORE 结构 指令执行过程中设置多级流水线等 软件方面: 十分强调优化编译技术的作用。 12. RISC 的关键技术延时转移技术;指令取消技术;重叠寄存器窗口技术;指令流调整技术;以硬件为主固件为辅。第三章 存储系统1. 存储系统的定义及主要性能两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个存储系统。这个存储系统对应用程序员是透明的,并且,从应用程序员看,它是一个存储器,这个存储器的速度接近速度最快的那个存储器,存储容量与容量最大的那个存储器相等,单位容量的价格接近最便宜的那个存储器。存储器的主要性能:速度、容量、价格 速度用存储器的访问周期、读出时间、频带宽度等表示。 容量用字节 B、千字节 KB、兆字节 MB 和千兆字节 GB 等单位表示。 价格用单位容量的价格表示,例如:$C/bit。存储系统的容量
要求: 提供尽可能大的地址空间;能够随机访问。方法有两种:只对系统中存储容量最大的那个存储器进行编址,其他存储器只在内部编址或不编址(Cache 存储系统)另外设计一个容量很大的逻辑地址空间,把相关存储器都映射这个地址空间中(虚拟存储系统)存储系统的价格计算公式: 存储系统的速度表示方法:访问周期、存取周期、存储周期、存取时间等命中率定义:在 M1 存储器中访问到的概率 其中:N1 是对 M1 存储器的访问次数 N2 是对 M2 存储器的访问次数访问周期与命中率的关系: T=HT1+(1-H)T2 当命中率 H→1 时,T→T1存储系统的访问效率:访问效率主要与命中率和两级存储器的速度之比有关。提高存储系统速度的两条途径:一是提高命中率 H,二是两个存储器的速度不要相差太大。2. 并行访问存储器方法:把 m 字 w 位的存储器改变成为 m/n 字 n×w 位的存储器 逻辑实现:把地址码分成两个部分,一部分作为存储器的地址另一部分负责选择数据 主要缺点:访问冲突大 (1)取指令冲突 (2)读操作数冲突 (3)写数据冲突 (4)读写冲突3. 虚拟存储器把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的页。主存储器的页称为实页 ,虚拟存储器中的页称为虚页 。
内部地址变换: 多用户虚拟地址 Av 变换成主存实地址 A 多用户虚拟地址中的页内偏移 D 直接作为主存实地址中的页内偏移 d,主存实页号 p 与它的页内偏移 d 直接拼接起来就得到主存实地址 A。 4. 虚拟存储器中加快地址变换的方法目录表基本思想:用一个小容量高速存储器存放页表 。 地址变换过程:把多用户虚地址中 U 与 P 拼接,相联访问目录表。读出主存实页号 p,把 p与多用户虚地址中的 D 拼接得到主存实地址。如果相联访问失败,发出页面失效请求。快慢表 快表:TLB(Translation Lookaside Buffer):小容量(几~几十个字),高速硬件实现,采用相联方式访问。 慢表:当快表中查不到时,从主存的慢表中查找;慢表按地址访问;用软件实现。 快表与慢表也构成一个两级存储系统。散列函数 目的:把相联访问变成按地址访问 散列(Hashing)函数:Ah=H(Pv) 采用散列变换实现快表按地址访问 避免散列冲突:采用相等比较器 地址变换:相等比较与访问存储器同时进行 5. 虚拟存储系统的页面替换算法(1)随机算法(RAND random algorithm) 算法简单,容易实现。 没有利用历史信息,没有反映程序的局部性 命中率低。(2)先进先出算法 (FIFO first-in first-out algorithm) 容易实现,利用了历史信息, 没有反映局部性。 最先调入的页面,很可能也是要使用的页面(3)近期最少使用算法(LFU least frequently used algorithm):既充分利用了历史信息,又反映了程序的局部性实现起来非常困难。(4)最久没有使用算法(LRU least recently used algorithm):把 LFU 算法中的“多”与“少”简化成“有”与“无”,实现比较容易(5)最优替换算法(OPT optimal replacement algorithm):是一种理想算法,仅用作评价其它页面替换算法好坏的标准。 在虚拟存储器中,实际上可能采用的只有 FIFO 和 LRU 两种算法。6. Cache 存储系统的地址映象及变换方法地址映象: 把主存中的程序按照某种规则装入到 Cache 中,并建立主存地址与 Cache 地址之间的对应关系。 地址变换: 当程序已经装入到 Cache 之后,在程序运行过程中,把主存地址变换成 Cache 地址。
在选取地址映象方法要考虑的主要因素: 地址变换的硬件实现容易、速度要快, 主存空间利用率要高, 发生块冲突的概率要小。(1)全相联映象及其变换映象规则:主存的任意 一块可以映象到 Cache 中的任意一块。(2)直接映象及其变换映象规则: 主存储器中一块只能映象到 Cache 的一个特定的块中。 Cache 地址的计算公式: b=B mod Cb 其中:b 为 Cache 块号, B 是主存块号, Cb是 Cache 块数。直接映象方式的地址变换过程:用主存地址中的块号 B 去访问区号存储器,把读出来的区号与主存地址中的区号 E 进行比较:比较结果相等,有效位为 1,则 Cache 命中,否则该块已经作废。比较结果不相等,有效位为 1,Cache 中的该块是有用的,否则该块是空的。(3)组相联映象及其变换映象规则: 主存和 Cache 按同样大小划分成块和组。 主存和 Cache 的组之间采用直接映象方式。 在两个对应的组内部采用全相联映象方式。组相联映象的地址变换过程:用主存地址中的组号 G 按地址访问块表存储器。 把读出来的一组区号和块号与主存地址中的区号和块号进行相联比较。如果有相等的,表示 Cache 命中;如果全部不相等,表示 Cache 没有命中。(4)位选择组相联映象及其变换地址映象规则: 主存和 Cache 都按同样大小分块,Cache 在分块的基础上再分组,主存按照 Cache 的组容量分区。主存的块与 Cache 的组之间采用直接映象方式,主存中的块与 Cache 中组内部的各个块之间采用全相联映象方式。(5)段相联映象及其变换映象规则: 主存和 Cache 都按同样大小分块和段 段之间采用全相联映象方式 段内部的块之间采用直接映象方式地址变换过程:用主存地址中的段号与段表中的主存段号进行相联比较如果有相等的,用主存地址的段内块号按地址访问 Cache 的段号部分。
把读出的段号 s 与主存地址的段内块号 b 及块内地址 w 拼接起来得到 Cache 地址;7. Cache 替换算法轮换法;LRU 算法;比较对法;堆栈法。8. Cache 存储系统的加速比(1)加速比与命中率的关系Cache 存储系统的加速比 SP为: 其中:Tm为主存储器的访问周期, Tc为 Cache 的访问周期, T 为 Cache 存储系统的等效访问周期, H 为命中率。(2)Cache 命中率与容量的关系Cache 的命中率随它的容量的增加而提高。 关系曲线可以近似地表示为: (3). Cache 命中率与块大小的关系 在组相联方式中, 块大小对命中率非常敏感, 块很小时,命中率很低。 随着块大小增加命中率也增加, 有一个极大值; 当块非常大时, 进入 Cache 中的数据可能无用; 当块大小等于 Cache 容量时, 命中率将趋近零。(4)Cache 命中率与组数的关系 在组相联方式中, 组数对命中率的影响很明显 随着组数的增加,Cache 的命中率要降低。 当组数不太大时(小于 512), 命中率的降低很少。 当组数超过一定数量时, 命中率的下降非常快。第四章 输入输出系统1. 基本输入输出方式(1)程序控制输入输出方式状态驱动输入输出方式、应答输入输出方式、查询输入输出方式、条件驱动输入输出方式程序控制输入输出方式的 4 个特点:(1)何时对何设备进行输入输出操作受 CPU 控制(2)CPU 要通过指令对设备进行测试才能知道设备的工作状态。空闲、准备就绪、忙碌等(3)数据的输入和输出都要经过 CPU(4)用于连接低速外围设备,如终端、打印机等(2)中断输入输出方式定义:当出现来自系统外部,机器内部,甚至处理机本身的任何例外的,或者虽然是事先安排的,但出现在现行程序的什么地方是事先不知道的事件时, CPU 暂停执行现行程序,转去处理这些事件,等处理完成后再返回来继续执行原先的程序。特点: