总复习第 1章 计算机系统结构的基本概念
1.1 计算机系统的多级层次结构
1.2 计算机系统结构、组成与实现
1.3 软件取舍与计算机系统的设计思路
1.4 软件、应用、器件对系统结构的影响
1.5 系统结构中的并行性及系统的分类
1.1多级层次结构
1.六 级层次结构应用语言机器 面向用户高级语言机器 面向用户汇编语言机器 面向用户操作系统机器 面向上层机器传统机器 面向上层机器微指令机器 面向上层机器
2.层次结构的实现方式根据性价比,软硬件逻辑是等同的
3.分层优点
*
1.2计算机系统结构、组成与实现
1.结构、组成与实现的概念
1)系统结构:
系统结构 (System Architecture)是对计算机系统中各机器之间界面的划分和定义,以及对各级界面上,下的功能进行分配 。
2)透明性概念:
在计算机中,客观存在的事物或属性从某个角度看不到,称这些事物或属性对它是透明的 。 计算机重的,透明,与社会生活中的,透明,,含义正好相反 。
*
3)计算机系统结构 (Computer Architecture)
是系统结构中的一部分,指层次结构中传统机器级的系统结构,其界面之上的功能包括操作系统级、汇编语言级、高级语言级和应用语言级中所有软件的功能;界面之下的功能包括所有硬件和固件的功能。因此,这个界面实际是软件与硬件或固件的分界面。
4)计算机组成 (Computer Organization)
是计算机系统结构的逻辑实现,包括机器级内的数据流和控制流的组成以及逻辑实现 。
5)计算机实现 (Computer Implementation)
指的是计算机组成的物理实现
2.结构,组成与实现之间的关系
1)具有相同系统结构 (如指令系统相同 )的计算机可以因速度等因素的要求不同而采用不同的组成 。
2)相同的计算机组成可以采用多种不同实现方法。
3)不同的系统结构会使组成技术产生差异
4)计算机组成也会影响系统结构,组成的设计,其上取决于系统结构,其下又受限于所可以用的实现技术。
1.3软硬件取舍与系统的设计思想
1.软件取舍的基本原则
1)在现有的硬件和器件 (主要是逻辑器件和存贮器件 )的条件下,系统要有高的性价比。
2)充分考虑准备采用和可能要用的的组成技术,使它尽可能不要过多或不合理地限制各种组成,实现技术的采用 。
3)不能仅从,硬,的角度去考虑如何便于应用组成技术的成果和发挥器件技术的进展,还应从,软,
的角度为编译和操作系统的实现,以至高级语言程序的设计提供更多,更好的硬件支持 。
2.计算机系统的设计思路
1)由上往下
a)方法:根据用户的要求,设计基本的命令,数据类型与格式等,然后再逐级往下设计,并考虑对上一级进行优化来实现 。
b)优点:适用于专用机的设计,对所面对的具体应用,其效能是很好的 。
c)缺点:不适用于通用机的设计
2)由下往上方法:根据器件条件,先把微程序机器级及传统机器级研制出来,然后再配合不同的操作系统和编译系统软件,使应用人员根据所提供的条件来采用合适的算法满足相应的应用要求 。
3)中间法方法:既考虑能拿到的硬件,器件,又考虑可能所需的算法和数据结构,先进行软,硬功能的合理分配 并定义好这个界面,然后从这一中间点分别往上,往下进行软,硬设计 。
1.4软件、应用、器件对系统结构的影响
1.软件的可移植性
1)概念:指软件可以不加修改或经少量修改,就可以由一台机器搬到另一台机器去运行,使得同一套软件可以应用于不同的硬件环境 。
2)优点:可以大量节省重复工作量,是软件设计者可以集中精力更好的改进或开发全新的软件 。
2.实现可移植性的技术
1)统一高级语言
2)系列机思想
3)模拟与仿真
1.5系统中的并行性及其分类
1.并行性概念
1)并行性,解题中具有可以同时进行运算或操作的特性 。 目的是为了能并行处理,提高解题效率 。
2)广义并行性,只要在同一时刻或是在同一时间间隔内完成两种或两种以上性质相同或不同的工作,
在时间上能相互重叠,都称为并行性 。
3)同时性:两个或多个事情在同一时刻发生 。
4)并发性:两个或多个事情在同一时间间隔内发生 。
*
2.并行性等级
1)从执行角度分
a)指令内部
b)指令之间
c)任务或进程之间
d)作业或进程之间
2)从数据处理角度
a)位串字串
b)位并字串
c)位片串字并
d)全并行
3)从信息加工角度
a)存贮器操作并行
b)处理器操作步骤并行
c)处理器操作并行
d)指令,任务,作业并行
3.并行性开发途径
1)时间重叠
a)方法:在并行性中引入时间因素,让多个处理过程在时间上错开,轮流重复的使用同一套硬件设备的各个部分,以加快硬件周转而提高速度 。
b)优点:不必增加额外硬件设备就可以提高计算机系统的性价比 。
2)资源重复
a)方法:引入空间因素,通过重复设置硬件资源来提高可靠性或性能 。 如双工系统 。
b)优点:系统的速度性能得到很大提高 。
*
3)资源共享
a)方法:利用软件的办法让多个用户按一定时间顺序轮流使用同一套资源,以提高其利用率,这样可以提高整个系统的性能 。 例如,多道程序分时系统就是利用共享 CPU,主存资源,以降低系统价格,提高设备的利用率 。
b)优点:节省资源,效率高,介于上述两种之间 。
4.并行处理系统结构与多机系统耦合度
1)结构
a)流水线计算机
b)阵列处理机
c)多处理机
d)数据流机
2)多级系统的耦合度
a)最低耦合 —— 只是通过某种介质 (如磁盘 )交换信息,各机之间没有物理连接,无共享的联机硬件资源。
b)松散耦合 —— 也叫间接耦合,通过通道或通信线路互连,只共享某些外围设备 。 又分两种形式:
一种形式是多台计算机通过通道和共享的外围设备相联;另一种形式是各台计算机通过通信线路连接成计算机网络 。 这两种都是非对称,异步的 。
c)紧密耦合 —— 也叫直接耦合,通过总线或高速开关互连,共享主存,信息传输速率高,可以实现数据集一级,任务级,作业级的并行 。 大多是对称型多处理系统 。
5.计算机系统的分类
1)弗林分类法根据指令流和数据流的多倍性 (是指在系统性能瓶颈部件上处于同一执行阶段的指令或数据的最大可能个数 )状况对计算机进行分类 。
a)单指令流单数据流 SISD
b)单指令流多数据流 SIMD
c)多指令流单数据流 MISD
d)多指令流多数据流 MDMD
2)库克分类法根据指令流和执行流 (Execution Stream)及其多倍性对计算机系统结构进行分类 。
a)单指令流单执行流 SISE
b)单指令流多执行流 SIME
c)多指令流单执行流 MISE
d)多指令流多执行流 MIME
3)冯泽云分类法根据数据处理并行度对计算机系统结构分类
a)字串位串
b)字串位并
c)字并位串
d)字并位并第 2章 数据表示与指令系统
2.1数据表示
2.2寻址方式
2.3指令系统的设计与改进
2.1数据表示
1.数据表示与数据结构
1)基本概念
a)数据表示:能由机器硬件直接识别和的引用的数据类型 。
b)数据结构:各种数据元素或信息单元之间的结构关系 。
2)两者关系
a)数据结构是通过软件映像将信息变换成数据表示来实现的,表示是结构的元素。
b)不同的表示为结构的实现提供不同的支持
c)结构和表示是软、硬件的交接面
2.高级数据表示
1)自定义数据表示
a)带标志符的数据表示
b)数据描述符目的:进一步减少标志符所占空间,对于向量、
数组、记录等数据,每个元素具有相同属性,为此提出了数据描述符。
两者 区别:
标志符:与每个数据相连,合存一个单元,描述单个数据的类型特征。
描述符:和数据分开,描述要访问数据是单个还是整块,及所需地址等信息。
*
2)向量数组数据表示目的:为向量、数组的实现和快速运算提供更好的硬件支持,引入了向量数组数据表示,组成向量处理机。
3)堆栈数据表示目的:通用机器对堆栈的实现支持很差,指令较少,功能单一,速度低,多用于保护子程序返回地址,少数用于参数传递。
3.引入数据表示的原则
1)看效率是否提高,即时间和空间是否减少
a)主存与 CPU的通讯数据是否减少
b)是否节省了辅助性操作
2)看是否有利于通用性和利用率的提高若只对某些数据结构的效率高,而其它很低,或引入后很少用到,必然导致性价比下降。
4.浮点数尾数基值和下溢处理的选择
1)浮点数尾数基值的选择
a)可表示的范围
rm增大:最小值减小,最大值增大,从而范围变大。
b)可表示数的个数
rm增大:个数增多
c)数在实轴上的分布
rm增大:数的分布越稀,用表示比 e衡量。
d)可表示数的精度
rm增大:数的分布越稀,则数的表示精度下降。
*
e)运算中的精度损失是指运算中尾数右移处机器字而使有效数字丢失造成的精度损失,区别于可表示数的精度。
rm增大:尾数右移可能性降低,精度损失减小
f)运算速度
rm增大:左移、右移次数减少,速度提高
g)表示比 e
定义:在相同的 p,m时,在 rm=2的可表示最大值内,采用 rm>2的可表示浮点数个数与 rm=2的可表示浮点数个数之比。
计算公式:
e= 21-p(1-rm -1)(1+ (2p-1)/ log2 rm)
2)浮点数尾数的下溢处理方法数据运算过程中的相乘或右移,使超出运算器和存贮器字长的部分丢弃造成精度损失,为减少精度损失,关键要处理好尾数下溢问题。
a)截断法方法,将尾数超出机器字部分简单截去。
最大误差:整数接近 1,二进制分数接近 2-m
正负:正数产生负误差分布:间隔相同,均匀分布。
*
b)舍入法方法,在规定字长外增设一位附加位,存放溢出部分高位,处理时该位加 1。
最大误差:整数二进制为 0.5,分数为 2-(m+1)。
正负:有正有负分布:统计平均误差接近零,稍偏正,无法调节
c)恒置,1”法方法,在规定字长之最低位恒置成,1”状态 。
最大误差:整数二进制为 1,分数为 2-m
正负:有正有负。
分布:统计平均误差接近零,稍偏正,无法调节
d)查表舍入法方法,基于存贮逻辑思想,用 ROM或 PLA存放下溢处理表,当 k-1位全位,1”时,以截断法处理;其它以舍入法处理。
最大误差:最大为 1。
正负:有正有负。
分布:不均匀,平均误差为零,可调节。
优点,ROM速度快,平均误差可调为零,可调节。
缺点,增加过多硬件设备
2.2寻址方式
1.寻址方式分析
1)不同机器的编址方式
a)把部件分类,各自从,0”开始单独编址,构成多个一维线性地址空间。
b)把所有部件统一编成一个从,0”开始的一维线性地址,对部件的访问反映为对地址的访问。
c)隐式地址,采用约定的编址方式,不必计算部件地址,加快访问速度。
2)寻址方式
a)面向寄存器 —— 速度快
b)面向堆栈 —— 减轻编译负担
c)面向内存 —— 针对大量数据操作
3)寻址方式的两种指明方式
a)占用操作码的某些位来指明
b)在地址码部分专门设置寻址方式位来指明
2.逻辑地址与主存物理地址
1)程序定位方法
a)静态再定位思想,利用冯,诺依曼型机器指令可修改的特点,
程序装入内存时,用软件方法把逻辑地址变换成物理地址,执行时物理地址不再改变。
b)动态再定位思想,基于变址思想,提出了基址寻址法,增加相应基址寄存器和地址加法器,执行时逻辑地址加基址即可形成物理地址而访问。
2)基址寻址与变址寻址
a)变址寻址,对向量、数组等数据块运算提供支持以利于实现程序的循环。
b)基址寻址,对逻辑地址空间到物理地址空间的支持,以利于实现程序的动态再定位。其实质是将静态再定位的软件实现用地址加法器硬件替换,
以加快地址变换的速度。
3)界限保护设置上下界寄存器,保护上下界地址;还可设置多对上下界寄存器,保证一道程序可以访问多个连续空间。
4)物理地址空间的信息分布同台机器可存贮多种宽度信息,字节、字、半字及双字等。
a)存贮原则:存贮于主存中的各位信息必须是其信息位数的整数倍,即按整数边界存贮。
b)优点:减少了访问周期,有利于提高访问速度。
c)缺点:浪费存贮空间
2.3指令系统的设计和改进
1.指令格式的优化
1)基本概念
a)指令格式的优化:用最短的位数来表示指令的操作信息和地址信息,使程序中指令的平均字长最短。
b)哈夫曼压缩思想:当各种事件发生概率不等时,
概率最高事件用最短位数表示,概率低事件用长位数表示,就会使平均位数缩短。可用于代码、
程序、存贮空间、时间等的压缩。
2)操作码的优化表示
a)目的,缩短指令字长度,减少程序总位数,增加指令字所能表示的操作信息和地址信息。
b)信息源熵 H:
H=- Σpilog2pi
其中,pi是指令的使用频度 。
c)定长操作码的信息冗余量:
(实际平均长度 - H)/实际平均长度
*
d)哈夫曼编码
将指令的使用频度由小到大排序
每次选最小两个频度结合一个新节点
再按频度大小插入余下未结合的频度值中
如此重复直至全部结合完毕成根节点,1”
沿两个分支,分别用,0”或,1”来表示这样,从根节点开始,沿线到达个频度指令的代码序列就是该指令的哈夫曼编码。
*
e)扩展操作码编码结合哈夫曼编码与定长二进制编码思想,只用有限几种码长,仍是概率大的事件用长码,小的用短码。以此来缩短码长,降低冗余量,便于译码。
f)常用扩展方法
等长扩展法
15/15/15编码法适用于 pi在前 15种指令中比较大,而在 30种指令后急剧减小的情况。
8/64/512编码法适用于 pi在前 8种指令中比较大,且之后的 64种指令的 pi也不是过小时。
衡量标准,码长 Σpili最短
3)指令字格式的优化只对操作码表示优化,不对地址码表示和寻址方式采取措施,程序所需总位数难以减少。
a)主存按位编址,指令一条条挨着存贮,会使程序所需总位数减少,但是速度明显下降。为了不降低访存取指速度,就要按整数边界存贮。这样,
操作码优化表示所带来 li的缩短只是使指令字内出现空白浪费 (冗余 )。显然只有地址码也是可变长的,才能用上空白部分。
b)地址码长度优化
从访存范围考虑,地址码越长越好
在满足寻址范围前提下,可以缩短其位数
*
c)寻址方式
基址寻址:指明基址寄存器号
相对寻址:指明相对位移,相对位移不会太大。
地址分段:地址由段号和段内地址组成。段内转移,不需指明段号;断间转移,指明段号。
寄存器间接寻址:操作数存在寄存器内或经寄存器访存,则地址码宽度只需窄到指明寄存器号就可以了。
2.按 CISC方向发展与改进指令系统
1)改进思路如何进一步增强原有指令的功能以及设置更为复杂的新指令取代原来由子程序完成的功能,实现软件功能的硬化。结果是系统愈加庞大、复杂,称为复杂指令系统计算机 (Complex Instruction Set
Computer,CISC)。
2)CISC的改进途径 (三个 )
a)面向目标程序的优化实现来改进
目的:提高各机器语言目标程序的效率,减少存贮空间,提高运行速度,容易实现。
*
思路:
思路一:按统计出的指令和指令串的使用频度来分析改进静态使用频度:对程序中出现的指令及指令串进行统计得到的百分比。目的是减少目标程序所占用的存贮空间。
动态使用频度:在目标程序执行中对指令和指令串统计的百分比。目的是减少目标程序的执行时间。
思路二:增设强功能的复合指令,取代原先由宏指令或子程序实现的功能,可以提高运算速度,
减少程序调用的额外开销,也减少子程序所占用的空间。
原则:
原则一:不删改原有指令,增设强功能指令替代对“瓶颈”有直接影响的常用指令,以满足软件向后兼容,从而新指令程序效率更高。
原则二:尽量减少程序中如存取、传送、转移、
比较等不执行数据变换的非功能型指令,增加真正执行数据变换的加、减、乘、除等功能型指令的比例。
b)面向高级语言的优化来实现
目的:尽可能缩短高级语言和机器语言的语义差距,以利于支持高级语言的编译系统,缩短编译程序的长度和编译所需的时间。
思路:
对源程序中各高级语言的使用频度进行分析面向编译,优化代码生成来实现改进指令系统动态切换发展高级语言机器
c)面向操作系统的优化来实现
目的:缩短 OS与系统结构的语义差距,减少运行 OS所需的辅助时间,节省 OS软件所占用的存贮空间。
思路:
统计和分析 OS中常用指令 (串 )的使用频度增加专用于 OS的新指令硬化或固化子程序的某些功能发展功能分布处理系统结构
3)CISC的结构和思路存在的问题
a)指令系统庞大,设计麻烦,周期长,成本高,
可靠性低,查错和纠错代价大。
b)指令操作烦杂,执行速度很低。
c)难以优化编译生成真正高效的机器语言。
d)各种指令使用频度不高,且差别大,有些指令利用率很低,降低系统性价比。
3.按 RISC方向发展与改进指令系统
1)RISC的改进思路通过减少指令总数和简化指令功能来降低硬件设计的复杂度,提高指令执行速度。按这种途径和方向发展,使机器指令精练简单,因此称为精简指令系统计算机 (Reduced Instruction Set Computer——
RISC)。
2)RISC的设计原则
a)只选择使用频度高的指令,增加少量有效支持 OS和高级语言实现的有用指令,减少条数。
b)减少系统可用的寻址方式,简化指令的格式,
限于两种内,让全部指令等长。
c)让所有指令都在一个机器周期内完成。
d)增加通用寄存器以减少访存操作,所有指令只有存、取可以访存,其它都在寄存器间进行。
e)指令多数用硬联控制,少数用微程序控制。
f)以简单有效的方式支持高级语言的实现。
3)RISC结构采用的基本技术
a)遵循按 RISC机器一般原则设计的技术。
b)在逻辑上采用硬联实现和微程序固件实现相结合的技术。
c)在 CPU中设置数量较大的寄存器组,并采用重叠寄存器窗口的技术。
d)指令的执行采用流水和延迟转移技术。
e)采用认真设计和优化编译系统设计的技术。
*
第 3章总线、中断与 I/O系统
3.1输入输出系统概述
3.2总线设计
3.3中断系统
3.4通道处理机
3.5外围处理机
3.1 I/O系统概述
1,I/O系统的功能
1)功能:对指定的外设进行输入、输出操作,同时完成其它的管理和控制。
2)包括:
a)对指定外设的信息编址,连接好主存与指定外设的信息通路。
b)完成指定外设编址区和 OS指定的主存空间之间的信息传送。
c)对传送信息的格式变换,产生有关 I/O操作是否完成或出错的信息,经中断系统交给 OS分析处理
2,I/O系统的三种方式
1)程序控制 I/O
a)全软的
b)程序查询状态驱动的 — 键盘
c)中断驱动的 — 中断控制器 8259A
2)直接存贮器访问 (DMA)
3)I/O处理机
a)通道方式 (Channel)
有自己的指令和程序,功能简单,使用面窄。
b)外围处理机方式 (PPU)
独立性、通用性和功能较强。
3.2总线设计
I/O系统总线既要能传送数据信息、地址信息、控制信息,还要传送状态信息,并使多台外设与 CPU
或主存交叉地经这些总线传送信息。所以其设计的好坏,对 I/O系统的性能影响较大。
1.总线的类型
1)按信息传送方向分
a)单向传输
b)双向传输
半双向
全双向
2)按用法分
a)专用总线定义:只连接一对物理部件的总线优点:
多个部件可以同时发送和接受信息,几乎不必争用总线,系统流量高。
控制简单,不用指明信息源和目的。
任何总线的失效只影响相连的两个部件不能 直接通信,但可以间接通信,系统可靠性高。
缺点:
总线数目多,N个部件全部互连需 N(N-1)/2组 总线
难以小型化、集成电路化,总线长时成本高。
利用率低
不利于模块化,增加一个部件要增加许多新的接口和连线。
b)非专用总线定义:可以被多种功能或多个部件分时共享,同一时刻只有一对部件使用总线进行通信。
优点:
总线少,造价低。
接口标准化、模块性强,易于简化接口设计
扩充能力强,多重总线提高带宽和可靠性缺点:
经常出现总线争用,系统流量小。
可能成为系统速度瓶颈,导致系统瘫痪
2.总线的控制方式
1)控制方式
a)集中 式控制总线控制逻辑基本上集中放在一起,或者放在连接总线的一个部件中,或者是放在单独的 硬件中。
b)分布式控制总线控制逻辑分散于连到总线的各个部件中。
2)优先次序的三种确定方式
a)串行链接方式完全由“总线可用”线所接部件的物理位置来决定其优先次序,离总线控制器越近部件优先级越高。
*
b)定时查询方式:
总线分配前计数器清,0”,从,0”开始查询,优先级排序类似串行链接。
总线分配前不清,0”,从中止点继续查询,是循环优先级,部件使用总线机会均等。
总线分配前将计数器设置初值,可以指定某个部件为最高优先级。
总线分配前将部件号重新设置,可以为各部件指定任意希望的优先级。
c)独立请求方式:
总线控制器根据某种算法来仲裁
3.总线的通信技术
1)同步通信
a)方式:两个部件之间的信息传送是通过定宽、定距的系统时标进行同步的。
b)优点:信息传送速率高,受总线长度影响小。
c)缺点:
时钟在总线上的时滞会导致误同步
时钟线上的干扰信号易引起误同步
为了可靠性加宽时间片可能使数据传送速率 低于异步通信。
2)异步通信由于 I/O总线一般是为具有不同速度的许多 I/O设备所共享,因此宜采用异步通信。异步通信可分为单向控制和双向 (请求 /回答 )控制。
a)异步单向控制通信过程中只由源或目的部件中的一个控制,分为单向源控制和单向目的控制两种。
b)异步双向控制
目控式异步双向通信
源控式异步双向通信
4.数据宽度与总线线数
1)基本概念
a)数据宽度,I/O设备取得总线使用权后所传送数据的总量,可能经多个时钟周期分时传送。
b)数据通路宽度:指数据传送的物理宽度,比如
16bit,32bit等,即一个时钟周期传送的信息量。
2)数据宽度种类有单字 (或单字节 )、定长块、可变长块、单字 加定长块及单字加可变长块等。
*
*
a)单字 (或单字节 )宽度
适于输入机、打印机等低速设备,每传完一个字
(字节 )后等待时间长,期间释放总线,为其它设备服务,提高总线利用率和系统效率。
不适于磁盘、磁带等快速设备,一旦开始传送,
速率很高,重新分配总线降低效率。
优点,不指明信息长度,减少辅助开销。
缺点,要求总想控制逻辑高速分配总线,防碍总线采用更为合理的分配算法。
b)定长块宽度
优点:适于磁盘等高速设备,不指明传送信息宽度,简化控制,可按整个信息块进行校验。
缺点:块大小固定,当比所传信息块小时,仍多次分配总线;当大于所传信息块时,就会浪费总线的带宽和缓冲器空间。
c)可变长块宽度
优点;适于高优先级的中高速设备,可动态改变传送块的大小,有效利用总线的带宽。
缺点:要增大缓冲器空间和增加信息块大小的辅助开销和控制。
d)单字加定长块宽度
优点,适于速度低而优先级高的设备的总线。 定长块不必过大,超过部分可以用单字处理,减少总线带宽、部件缓冲空间的浪费。
缺点,信息块小于定长块少时,总线利用率低。
e)单字加可变长块宽度灵活有效,适应挂有各种设备的总线,但代价大
3)总线的线数
a)制约因素
总线线数越多,成本高,干扰大,可靠性低,占用空间大,但是传送速度和流量大。
总线长度越长,成本高,干扰大,波形畸变越严重,可靠性低。
b)原则,
总线越长,其线数应尽可能减少。
在满足性能要求及通信类型和速率的情况下,应尽量减少总线的线数。
3.3中断系统
1.中断的分类和分级
1)基本概念
a)中断源:引起中断的各种事件。
b)中断请求:中断源向中断系统发出请求中断的申请。同时可以有多个中断请求,这时中断系统要根据中断响应优先次序对优先级高的中断请求予以相应。
c)中断响应:就是允许其中断 CPU现行程序的运行而转去对该请求进行预处理,包括保存断点现场,
调出相应中断处理程序,准备运行。也可以屏蔽这一请求使其暂时得不到响应。
2)中断分类
a)中断 (Interrupt)
专指与当前进程运行无关的请求暂停的事件,如机器故障中断请求、外设中断请求、定时中断请求等。中断可以被屏蔽,暂时保存在中断寄存器,屏蔽解除后继续得到响应和处理。
b)异常 (Exception)
由现行指令引起的暂停事件,如页面失效、溢出等,一般不能屏蔽,立即得到响应和处理。
*
自陷 (Trap)
发生在引起异常的指令执行的末尾,处理后返回原先正常程序的下一条指令继续执行。
故障 (Fault)、
发生在执行指令的过程中,处理后返回原先发生故障的那条指令出重复执行。
失败 (Abort)
也发生在指令执行过程中,需强制干预或系统复位才可以使指令再正确执行下去。
3)中断级别根据中断的性质、紧迫性、重要性以及软件处理的方便性把中断源分级。优先级高低的划分,不同机器有所差异,一般把机器校验安排为第一级,程序性和管理程序调用为第二级,外部为第三级,I/O
为第四级,重新启动为最低级。
*
4)中断响应次序与处理次序
a)中断响应次序同时发生多个中断请求时,由中断响应硬件的排队器所决定的响应次序,次序是固定的。
b)中断处理次序一个中断处理程序执行前或中再有其它中断产生时中断处理完的次序,可以不同于响应次序 。
c)处理原则在处理某级中断时,只有更高级的请求到来才转去响应和处理,完成后返回原中断继续处理。
*
5)中断处理次序改变
a)方法:
设置中断级屏蔽位寄存器硬件以决定是否让某级中断请求进入中断响应排队器,只要进入排队器中断请求,就让级别高的优先得到响应。
OS对每类中断处理程序的现行 PSW中的中断级屏蔽位进行设置,可以实现希望的处理次序。
b)优点:
改变响应次序中用排队器硬件实现的固定次序为 OS软件实现的灵活性。
*
2.中断系统的软硬件功能分配
1)中断系统的功能
a)中断请求的保存和清除
b)优先级的确定
c)中断断点及现场的保存
d)对中断请求的分析和处理
e)中断返回
2)功能的实现
a)早期大部分功能是由软件完成的,中断响应和中断处理时间长 。
b)后来中断响应及其次序由程序查询软件的方法改为中断响应排队器硬件实现;中断源的分析也由程序查询改为硬件编码,直接或经中断向量表形成入口地址,并把中断源的状况以中断码的方式经旧 PSW告知中断处理程序。
3)中断系统性能指标
a)中断响应时间
b)灵活性
3.4通道处理机
1.工作原理
1)原因
a)为了 I/O与 CPU、主存并行操作,以及让多用户或多道程序共同运行。
b)防止用户自行输入而破坏其他用户程序或系统程序及用户窃取系统不该让其读出的内容。
2)工作过程具体见 P110图 3.9,P110图 3.10及 P111图 3.11。
3)类型:
a)字节多路通道适用于连接大量字符低速设备,传送一个字符或字节占用时间短,但等待时间长。数据通路宽度为单字节,采用字节交叉方式提高效率,或多个子通道独立并行工作。
b)数组多路通道适合于磁盘等高速设备,传送速率高,但传送前辅助操作时间长。数据宽度为定长块,传送 K个字节后重选设备进行下 K个字节的传送。多个子通道分时共享 I/O通路,成组交叉并行传送。
c)选择通道适合于优先级高的高速设备,独占通道,只能执行一道通道程序。数据宽度为可变长块,一次将 N
个字节全部传送完毕,传送期内只选一次设备。
2.通道流量分析
1)通道流量通道在数据传送期内,单位时间内所传送的字节数。它所能达到的最大流量称为通道极限流量。
2)影响极限流量的因素
a)工作方式
b)数据传送期内选择一次设备的时间 TS
c)传送一个字节的时间 TD
*
3)极限流量
a)字节多路通道,每选一台设备传送一个字节。
fmax.byte=1/(TS+TD)
b)数组多路通道,每选一条设备传送 K个字节。
fmax.block=k/(TS+kTD)=1/(TS/k+TD)
c)选择通道,每选一台设备就把 N个字节传送完。
fmax.select=N/(TS+NTD)=1/(TS/N+TD)
若 TS,TD一定,N>k,则:
fmax.select > fmax.block > fmax.byte
*
4)实际最大流量
a)字节多路通道,
fbyte.j=Σ fi.j
b)数组多路通道:
fblock.j =max fi.j
c)选择通道:
fselect.j =max fi.j
*
5)设计原则
a)极限流量大于等于实际最大流量
b)极限流量与实际最大流量的差值越小越好
fmax.byte.j >= fbyte.j
fmax.block.j >= fblock.j
fmax.select.j >= fselect.j
如果 I/O系统由 m个通道,则:
fmax= Σ fmax.byte.j + Σ fmax.block.j + Σ fmax.select.j
且,fmax>= Σ Σ fi.j + Σmax fi.j + Σmax fi.j
*
6)缺点:
a)并非独立的处理机,指令简单,无大容量存贮器
b)I/O过程中需要 CPU承担很多工作。
c)流水等组成技术因为 I/O中断而不能发挥作用,
CPU速度严重下降。
d)访管中断转入 I/O管理程序妨碍 CPU资源的合理利用。
3.5外围处理机 (PPU)
1.外围处理机的优点
1)更接近于一般的处理机,指令丰富,功能强。
2)独立于主处理机异步工作。
3)可以与主处理机共享或不共享主存。
4)可以自由选择通道和设备进行灵活通信 。
2.缺点:
就硬件利用率和成本来讲不如通道处理机好,但随着器件技术不断提高,成本在逐渐降低。
第 4章 存贮体系
4.1存贮体系的形成与性能
4.2虚拟存贮
4.3高速缓冲存贮器 Cache
4.4主存保护
4.1 存贮体系的形成与性能
1.存贮器的性能要求
1)大容量
SM=W · l · m
W:存贮体的字长,单位为 bit或 Byte。
l:每个存贮体的字数。
m:并行工作的存贮体的个数 。
2)低价格可以用总价格 C或每位价格 c来表示。具有 SM位的存贮器每位价格 c=C/SM。其中包括了存贮器本身的价格和为该存贮器操作必须的外围电路的价格。
3)高速度
a)访问时间 TA
TA是存贮器接到访存到信息被读到数据总线上所需的时间。是确定 CPU与存贮器时间关系的重要指标。
b)存贮周期 TM
TM是连续启动一个存贮体所需要的时间间隔。
一般来说总比 TA大。
c)存贮器频宽是指存贮器可以提供的数据传送率,一般用每秒钟所传送的信息位数来衡量。
最大频宽 BM(极限频宽 ):是存贮器连续访问时能提供的频宽。
单体,BM =W/TM
m体并行工作,BM =mW/TM
实际频宽:实际频宽小于最大频宽 BM
4)结论由于存贮器的价格、速度和容量的要求是相互矛盾的,为了同时满足三方面的要求,在一个完整的存贮体系中,必须采用不同工艺的存贮器,使得信息以各种方式分布于不同的存贮体。
2.并行主存系统频宽的分析
1)类型
a)单体单字
b)单体多字
c)多体单字交叉
d)多体多字交叉
2)分析结论由于程序的转移概率不会很低,数据分布的离散性较大,所以单纯靠增大 m来提高并行主存系统的频宽是有限的,且性价比还会随 m的增大而下降。
如果采用并行主存系统仍不能满足速度上的要求,
就必须从系统结构上改进,采用存贮体系。
3.存贮体系的形成与分支
1)容量需求主存 ——辅存存贮层次 程序局部性
2)速度需求
Cache——主存存贮层次 程序局部性
3)多级存贮层次
4.存贮体系的性能参数
1)存贮体系的每位平均价格 c
2)命中率 H=R1/(R1+R2)
3)等效访问时间
TA=HTA1+(1-H)TA2
4.2虚拟存贮器
1.管理方式
1)段式管理
a)思想:
根据程序的模块性,把一个复杂的大程序分解成多个逻辑上相对独立的模块。
b)段表为了进行段式管理,每道程序都由一个段表 (映像表 ),以存放该程序各程序段装入主存的状况信息。
*
段名 (号 ):实际由于段号与行对应,省略掉
装入位:表征是 (1)否 (0)已调入主存
地址:调入主存时,在主存的起始 (绝对 )地址
段长:段的大小,限制偏移越界
访问方式:只读、可写、只执行,提供访问保护
c)段表基址寄存器
断表长度,该道程序的断数 (断表行数 )
断表基地址,程序的断表在主存中的起始地址
d)虚拟地址
基号 (程序号 ):断表在断表基址寄存器的位置
段号,段在断表中的位置
段内位移,所访问单元在段内的偏移
e)实主存管理表
占用区域表
可用区域表
f)可用区域分配算法
首先分配算法
最佳分配算法
2)页式管理思想,把主存空间和程序空间都机械的等分成固定大小的页 (页面大小因机器不同而异,一般在 512
到几 kB)然后按页顺序编号。
3)段页式管理思想:把内存机械的等分成固定大小的页,把程序按模块分段,每个段分成与主存页面大小相同的页,每道程序通过一个段表和相应于每段的一组页表来进行定位。
问题:二次查表,费时间
*
*
2.页式虚拟存贮器的构成
1)地址映像与变换
a)地址映像就是将虚存单元按某种规则装入 (定位于 )实存,
即建立多用户虚地址 NS与实存地址 np的对应关系。
b)地址变换指的是程序按这种映像关系装入实存后,在执行时多用户虚地址 NS如何变换成对应的实地址 np。
c)全相联映像让每道程序的任何虚页可以映像装入到主存的任何实页位置
*
2)替换算法
a)目的当辅存中的页面调入主存发生页面争用时,只有强制腾出主存中某页后,才能接纳从辅存调来的新页面。替换算法就是解决具体从主存中选择哪一页作为被替换的页。
b)原则
有高的主存命中率
算法便于实现
辅助软、硬件成本尽量低
c)常用算法
随机算法 (Random,RAND)
先进先出算法 (First In First Out,FIFO)
近期最少使用算法 (Least Recently Used,LRU)
优化替换算法 (OPT)——衡量标准
d)堆栈型替换算法保证命中率随主存页数的增加只可能提高,至少不会下降。
e)页面失效频率法 (PFF)
根据各道程序运行中的主存页面失效率的高低,由
OS来动态调节分配给每道程序的实页数。
3)影响命命中率的因素
a)与替换算法有关
b)命中率与页地址流有关
c)与主存容量 (即分配给程序的主存页数 )有关
LRU/FIFO/OPT替换算法进行页面替换的过程模拟。
4)虚拟存贮器工作的全过程
P144图 4.25页式虚拟存贮器工作原理
*
*
3.页式虚拟存贮器实现中的问题
1)页面失效处理后援寄存器技术预判技术解决方法 替换算法页面大小不能过大
2)提高虚拟存贮器等效访问速度的措施
a)快表 ——慢表
b)散列快表 ——硬件实现散列函数
3)影响主存命中率和 CPU效率的某些因素
a)与 Sp有关
P150图 4.30 页面大小 Sp,容量 S1与命中率 H的关系曲线图
b)命中率与主存容量 S1有关
P151图 4.31命中率 H与容量 S1的关系图
c)与所采用的页面调度策略有关
4.3高速缓冲存贮器 (Cache)
1.基本结构特点,9个方面 (与虚拟存贮器对比 )
2.地址的映像与变换
1)全相联映像和变换
a)规则:主存中的任意一块均可映像装入到 Cache
内的任意一块的位置。
b)地址变换过程
c)优缺点块冲突率低;代价大,查表速度难以提高。
2)直接映像及其变换规则:主存中每一块只能映像到 Cache中唯一一个特定位置:主存的第 i块只能映像到第 imod2ncb块位置上。相当于把主存空间按 Cache空间分区,每区内各块只能按位置一一对应到 Cache相应位置上。
3)组相联映象及其变换规则:把主存按 Cache大小分区,整个 Cache是一区,每个区再分成相等的组,组内分块。组间直接映象,组内各块全相联映象。
*
*
4)段相联映象规则:把主存和 Cache分成具有相同的 Z块的若干段,段与段之间采用全相联映象,而段内各块之间采用直接映象,实质上就是组相联映象的特例。
3.替换算法的实现
1)堆栈法思想:栈顶恒存放近期最久访问过的页的页号,
而栈底恒存放近期最久没有访问过的页的页号,即准备被替换掉的页的页号。按此思想组成一个硬件堆栈。
*
2)比较对法思路:让各个块成对组合,用一个触发器的状态来表示该比较对内两块访问的远近次序,再经门电路就可以找到 LRU块。
4,Cache的透明性及性能分析
1)Cache的透明性分析
a)写回法在 CPU执行写操作时,只是把信息写入 Cache,
仅当需要被替换时,才将已经被写入过的 Cache块先送回主存,然后再调入新块。
*
b)写直达法也称为存直达法,它利用 Cache——主存存贮层次在处理机和主存之间的直接通路,每当处理机写入 Cache的同时,也通过此通路直接写入主存。
2)Cache的取算法
a)预取法
b)块的大小
c)预取开销
3)任务切换对失效率的影响
a)与任务的切换频度 (平均时间间隔 Qsw)有关
b)与 Cache的容量有关
4)影响 Cache存贮器性能的因素
a)不命中率与 Cache的容量、组的大小和块的大小的一般关系看 P168图 4.47块的大小、组的大小与 Cache容量对
Cache命中率的影响。
b)Cache——主存存贮层次的等效速度与命中率的关系
5.Cache——主存 ——辅存存贮层次
1)对应于虚地址的单元已在 Cache中
2)对应单元已在主存但尚未调入 Cache
3)对应单元还不在主存
4.4主存保护
1.存贮区域的保护
1)页表保护
2)键方式
3)环式保护
2.访问方式的保护计算机系统结构模拟试题模拟试题一一,简答题 (40分 )
1.什么是透明性概念?对于计算机系统结构,下列哪些是透明的?哪些是不透明的?
存贮器的模 m交叉存取;浮点数数据表示; I/O
系统是采用通道方式还是外围处理机方式;数据总线宽度;字符行运算指令;阵列运算部件;通道是采用结合型还是独立型;访问方式保护;程序性中断;串行、重叠还是流水控制方式;堆栈指令;存贮器的最小编址单位; Cache存贮器。
2.当浮点数尾数基值减小时,对机器数的表示会产生哪些方面的影响 (至少列举 5点 )?
3.试述 CISC的改进途径及其目的。
4.描述总线控制方式中采用集中式串行链接时,总线的分配过程。
5.试区别中断响应次序与中断处理次序。
6.在页式虚拟存贮器中,什么叫页面失效?什么叫页面争用?什么时候两者同时发生?什么时候两者不会同时发生?
7.描述 Cache存贮器的组相联映象及其变换。
8.段式管理的思想是什么?
二,问答题 (30分 )
1.浮点数尾数下移处理有哪些方法?各种方法的思想、最大误差、误差的分布及正负情况是什么?
2.三种通道的极限流量与实际最大流量是怎么计算的?设计时应满足什么式子?
3.在一个页式二级虚拟存贮器中,采用 FIFO算法进行页面替换,发现命中率 H太低,有下来建议:
(1)增大辅存容量; (2)增大主存容量 (页数 );
(3)增大主、辅存的页面大小 ;
(4)FIFO改为 LRU;
(5)FIFO改为 LRU,并增大主存容量 (页数 );
(6)FIFO改为 LRU,且增大页面大小。
试分析上述各建议对命中率的影响情况。
三,计算题 (30分 )
1.某机器有 10条指令,使用频度分别为:
0.01,0.15,0.12,0.07,0.08,
0.13,0.15,0.03,0.17,0.09。
(1)计算用等长操作码编码的平均码长;
(2)构造 Huffman树;
(3)写出 Huffman的一种编码,并计算其平均码长;
(4)只有二种码长,求平均码长最短的扩展操作码编码及其平均码长。
2.Cache分 S1= 24块,主存分 S2= 28块,让主存第 i块映象装入到 Cache中的第 j块,j= i mod S1 。
(1)这是什么映象规则?
(2)画出主存地址到 Cache地址变换过程的示意图,
图中应标示出主存与 Cache地址各字段位数及对应关系;指出用于地址映象变换的辅助表存贮器的宽度和单元数;并对变换过程作简单的文字说明。
模拟试题一参考答案一,简答题
1.【 解答 】 客观存在的事物或属性,从某个角度看去却看不到,称这些事物和属性对他是透明的。
透明了就可以简化这部分的设计,然而因为透明而无法控制和干预,就会带来不利。因此,透明性的取舍要正确选择。
对计算机系统结构透明的有:存贮器的模 m
交叉存取;数据总线宽度;阵列运算部件;通道是采用结合型还是独立型;串行、重叠还是流水控制方式; Cache存贮器。
对计算机系统结构不透明的有:浮点数数据表示; I/O系统采用通道方式还是外围处理机方式;
字符行运算指令;访问方式保护;程序性中断;
堆栈指令;存贮器最小编址单位。
2.【 解答 】 (1)数的可表示范围缩小;
(2)可表示数的总个数减少;
(3)数在数轴上的分布变密;
(4)机器数的精度提高;
(5)运算过程中的精度损失增大;
(6)运算速度有所降低。
3.【 解答 】 (1)面向目标程序的优化实现来改进目的:提高各机器语言目标程序的效率,减少存贮空间,提高运行速度,容易实现。
(2)面向高级语言的优化来实现目的:尽可能缩短高级语言和机器语言的语义差距,以利于支持高级语言的编译系统,缩短编译程序的长度和编译所需的时间。
(3)面向操作系统的优化来实现目的:缩短 OS与系统结构的语义差距,减少运行
OS所需的辅助时间,节省 OS软件所占用的存贮空间。
4.【 解答 】 集中式串行链接总线的原来如下图:
各部件经公共的“总线请求”线向总线控制器发出使用总线的请求。仅当“总线忙”未建立时,控制器在“总线可用”线上发出“总线可用”信号,串行送往各个部件。如果某部件未发“总线请求”信号,就部件
0
部件
1
部件
N-1总线控制器总线可用总线请求总线忙集中式串行链接总线控制原理图
“总线可用”信号顺链下去;否则,停止下传,向
“总线忙”送出信号,并取出该部件的“总线请求”,
此次总线分配结束,该部件获得总线使用权。等到该部件数据传送完毕后,由部件去除“总线忙”信号,
“总线可用”信号就随之去除。如果系统仍有总线请求,
就开始新的总线分配过程。
5.【 解答 】 (1)中断响应次序是靠中断响应的硬件排队器事先固定好的。它总是对进入了中断响应排队器的中断级请求按由高到低的次序响应其中的一个高优先级的中断级请求,除非某些中断级请求未进
(2)为了能动态地调节中断处理程序实际执行的次序,即中断处理次序,在中断级请求源与中断响应排队器的入口端之间又加设了一个中断级屏蔽字寄存器和 \相应的控制门电路硬件。中断级屏蔽字寄存器中的每一个中断级屏蔽位可以控制让相应等级的中断请求能否进入中断响应排队器去参加排队。只要能进入中断响应排队器的中断请求,总是让其中断级别相对高的优先得到响应。
操作系统可以通过修改各中断级处理程序的中断级屏蔽位的状况,来使中断处理 (完 )的次序符合我们所希望的次序。
6.【 解答 】 要访问的虚页不在实际主存时,就会发生页面失效。当页面调入主存,主存中的页面位置全部已被其它虚页占用时,就会发生页面争用。当分配给程序的内存已被全部占用之后,只要发生页面失效,就一定会发生页面争用。反之,发生页面失效,并不会发生页面争用。
7.将 Cache空间和主存空间分组,每组 S块 (S= 2s)。
Cache一共 2ncb个块,分成 Q组 (Q= 2q),整个 Cache
是一区。主存分成与 Cache一样大小的 2nd个区,其地址按区号、组号、组内块号、块内地址分成对应的 4个字段。主存地址的组号、组内块号分别用 q、
s' 字段表示,它们的宽度和位置与 Cache地址的 q,s
是一致的。
组相联映象指的是各组之间直接映象,但组内各块间则是全相联映象。
8.【 解答 】 根据程序的模块性,把一个复杂的大程序分解成多个逻辑上相对独立的模块。模块可以是主程序、子程序或过程,也可以是表格、数组以及树、向量等某类数据元素的集合。其大小可以互不相同,甚至事先无法确定。每个模块都是一个单独的程序段,都以该段的起点为 0相对编址。调入主存时,系统按照基址 (该段程序在主存中的起始地址 )
和每个单元在段内的相对位移组合来形成各单元在主存的实际地址。
二,问答题
1,【 解答 】 (1)截断法方法,将尾数超出机器字部分简单截去最大误差:整数接近 1,二进制分数接近 2-m
正负:正数 产生负误差分布:间隔相同,均匀分布
(2)舍入法方法:在规定字长外增设一位附加位,存放溢出部分高位,处理时该位加 1。
最大误差:整数二进制为 0.5,分数为 2-(m+1)
正负:有正有负分布:统计平均误差接近零,稍偏正,无法调节
(3)恒置,1”法方法,在规定字长之最低位恒置成,1”状态最大误差:整数二进制为 1,分数为 2-m
正负:有正有负。
分布:统计平均误差接近零,稍偏正,无法调节
(4)查表舍入法方法,基于存贮逻辑思想,用 ROM或 PLA存放下溢处理表。当 k-1位全位,1”时,以截断法处理;其它以舍入法处理。
最大误差,最大为 1
正负:有正有负分布:不均匀,平均误差为零,可调节
2.【 解答 】 (1)极限流量
a)字节多路通道,每选一台设备传送一个字节
fmax.byte=1/(TS+TD)
b)数组多路通道,每选一条设备传送 K个字节
fmax.block=k/(TS+kTD)=1/(TS/k+TD)
c)选择通道,每选一台设备就把 N个字节传送完
fmax.select=N/(TS+NTD)=1/(TS/N+TD)
(2)实际最大流量
a)字节多路通道,
fbyte.j=Σ fi.j
b)数组多路通道:
fblock.j =max fi.j
c)选择通道:
fselect.j =max fi.j
(3)满足式子
fmax.byte.j >= fbyte.j
fmax.block.j >= fblock.j
fmax.select.j >= fselect.j
i=1
pj
i=1
pj
i=1
pj
3.【 解答 】 (1)增大辅存容量,对主存命中率 H不会有什么影响。因为辅存容量增大,并不是程序空间的增大,程序空间与实存空间的容量差并未改变。
所以,增大物理辅存容量,不会对主存的命中率 H
有什么影响。
(2)如果主存容量 (页数 )增加较多时,将使主存命中率有明显提高的趋势。但如果主存容量增加比较少,命中率 H可能会略有增大,也可能不变,甚至还可能会有少许下降。
这是因为其前提是命中率 H太低。如果主存容量显著增加,要访问的程序页面在主存中的机会大大增加,命中率会显著上升。但如果主存容量 (页数 )
增加较少,加上使用的 FIFO算法不是堆栈型替换算法,所以对命中率的提高可能不明显,甚至还可能有所下降。
(3)因为前提是主存的命中率 H很低,在增大主、
辅存的页面大小时,如果增加量较小,主存命中率可能没有太大的波动。因为 FIFO是非堆栈型的替换算法,主存命中率可能会有所增加,也可能降低和不变。而当页面大小增加量较大时,可能会出现两种相反的情况。当原页面大小较小时,在显著增大了页面大小之后,一般会使主存命中率 H有较大提高。但当原页面大小已较大时,再显著增大页面大小后,由于在主存中的页面数过少,将会使主存命中率继续有所下降。
(4)页面替换算法由 FIFO改为 LRU后,一般会使主存的命中率提高。因为 LRU替换算法比 FIFO替换算法能更好地体现出程序工作的局部性特点。然而主存命中率还与页地址流、分配给主存的实页数多少等有关,所以,主存命中率也可能仍然较低,没有明显改进。
(5)页面替换算法由 FIFO改为 LRU,同时增大主存的容量 (页数 ),一般会使主存命中率有较大的提高。因为 LRU替换算法比 FIFO替换算法能更好地体现出程序工作的局部性,又由于原先主存的命中率太低,现在增大主存容量,一般会使主存命中率上升。如果主存容量增加量大些,主存命中率 H将会显著上升。
(6)FIFO改为 LRU,且增大页面大小时,如果原先页面大小很小,则会使命中率显著上升;如果原先页面大小已很大了,因为主存页数进一步减少而使命中率还会继续有所下降。
三,计算题
1.【 解答 】 (1)4位
(2)Huffman树如下图:
0.04
0.01 0.03
0.07
0.11 0.12
0.23
0.08 0.09
0.17
0.13 0.15
0.28
0.15 0.17
0.32
0.40 0.60
1.00
0
0
0
0
0
0
00 0
1
1
1111
1
1
1
(3),(4)结果如下:
Huffman编码平均码长= ∑ pili= 3.15位扩展编码平均码长= ∑ pili= 3.19位使用频度 Huffman编码 (不唯一 ) 扩展编码 (不唯一 )
0.01
0.03
0.07
0.08
0.09
0.12
0.13
0.15
0.15
0.17
00 00 0
00 00 1
00 01
01 0
01 1
00 1
10 0
10 1
11 0
11 1
00 00
00 01
00 10
00 11
01 0
01 1
10 0
10 1
11 0
11 1
2.【 解答 】 (1)直接映象
(2)主存地址到 Cache地址变换过程的示意图如下图所示,主存块号 块内地址 主存地址
nm
nmb 4位 nmr
ncb 4位 ncr Cache地址
nc

相联比较不等块失效区号 4位

0
1
15
相等访 Cache
(按地址访问存贮器 )
辅助映象表存贮器用按地址访问的存贮器构成,
共 16个单元,每个单元 4位宽。
变换过程:主存地址中截取对应 Cache地址部分的字段来访 Cache,同时用区内 (Cache)块号访问辅助映象表存贮器,将其内容读出,与主存区号字段进行比较。若比较相等,让访 Cache操作继续进行下去,表示 Cache命中;否则,表示访 Cache失效,
由主存中调块。
模拟试题二一,简答题 (40分 )
1.分别解释结构、组成与实现。
2.提高计算机系统并行性的技术途径有哪三个?简要解释并各举一系统类型的例子。
3.设计 RISC机器的基本技术是什么?
4.简要说明构造 Huffman树的过程。
5.通道分为哪 3种类型?各适合连接什么类型的设备?
满负荷时,设备对通道要求的实际流量与所连的设备有什么关系?
6.列举定时查询中确定部件优先级次序的方法。
7.CPU写 Cache时,会发生 Cache与主存的对应副本内容不一致的现象,解决这个问题有哪些方法?
各需要增加什么开销?
8.LRU块替换算法的硬件实现有哪 2种方法?各自的思路是什么?
二,问答题 (30分 )
1.什么叫“程序的动态再定位”?
2.中断分类的依据是什么?目的是什么?具体分为哪几类?各自是如何定义的?
3.采用组相联映象,LRU替换算法的 Cache存贮器,
发现等效访问速度不高,为此提议:
(1)增大主存容量;
(2)增大 Cache中的块数 (块的大小不变 );
(3)增大组相联组的大小 (块的大小不变 );
(4)增大块的大小 (组的大小和 Cache总容量不变 );
(5)提高 Cache本身器件的访问速度。
试问分别采用上述措施后,对等效访问速度可能会有什么样的显著变化?其变化趋势如何?如果采取措施后并未能使等效访问速度有明显提高的话,
又是什么原因?
三,计算题 (30分 )
1.机器有 5级中断,中断响应次序为 1 2 3 4 5,现要求中断处理次序为 2 3 1 5 4。
(1)设计各级中断处理程序的中断级屏蔽位的状态,
令,0”表示开放,,1”表示屏蔽。
(2)若在运行用户程序时,同时发生第 1,3级中断请求,而在第 1级中断未完成时,又发生 2,3,4,5
级中断,请画出处理机执行程序的全过程示意图
(标出交换 PSW的时间 )。
2.设某虚拟存贮器上运行的程序包含 5个页面,其页地址流依次为 4,5,3,2,5,1,3,2,5,1,3
用 LRU替换算法。
(1)用堆栈对该页地址流模拟一次,画出这一模拟过程,并标出实页数为 3,4,5时的命中情况。
(2)为获得最高的命中率,应分配给该程序几个实页即可?其可能的最高命中率是多少?
模拟试题二参考答案一,简答题
1.【 解答 】 (1)系统结构:是对计算机系统中各机器之间界面的划分和定义,以及对各级界面上、下的功能进行分配。
(2)计算机系统结构,是系统结构中的一部分,指层次结构中传统机器级的系统结构,其界面之上的功能包括操作系统级、汇编语言级、高级语言级和应用语言级中所有软件的功能;界面之下的功能包括所有硬件和固件的功能。因此,这个界面实际是软件与硬件或固件的分界面。
(3)计算机组成:是计算机系统结构的逻辑实现,
包括机器级内的数据流和控制流的组成以及逻辑实现 。
(4)计算机实现:指的是计算机组成的物理实现 。
2.【 解答 】 (1)时间重叠:在并行性中引入时间因素,让多个处理过程在时间上错开,轮流重复的使用同一套硬件设备的各个部分,以加快硬件周转而提高速度 。 例如,流水线处理机 。
(2)资源重复:引入空间因素,通过重复设置硬件资源来提高可靠性或性能 。 例如,双工系统 。
(3)资源共享:利用软件的办法让多个用户按一定时间顺序轮流使用同一套资源,以提高其利用率,
这样可以提高整个系统的性能 。 例如,多道程序分时系统,多处理机,分布处理系统,计算机网络 。
3.【 解答 】 (1)遵循 RISC机器一般原则设计的技术 。
(2)在逻辑上采用硬联实现和微程序固件实现相结合的技术。
(3)在 CPU中设置数量较大的寄存器组,并采用重叠寄存器窗口的技术。
(4)指令的执行采用流水和延迟转移技术。
(5)采用认真设计和优化编译系统设计的技术。
4.【 解答 】 (1)将指令的使用频度由小到大排序
(2)每次选最小两个频度结合一个新节点
(3)再按频度大小插入余下未结合的频度值中
(4)如此重复直至全部结合完毕成根节点,1”
(5)沿两个分支,分别用,0”或,1”来表示这样,从根节点开始,沿线到达个频度指令的代码序列就是该指令的哈夫曼编码。
5.【 解答 】 通道分为字节多路通道、数组多路通道以及选择通道 3种。
(1)字节多路通道适合连接大量低速的字符设备。
满负荷时,设备对通道要求的实际流量应是所连各设备的流量之和。
(2)数组多路通道适合于连接高速的设备。满负荷时,设备对通道要求的实际流量应是所连各个设备中,流量最大的那个。
(3)选择通道适合于连接中、高速的高优先级的设备。满负荷时,设备对通道要求的实际流量应是所连各个设备中,流量最大的那个。
6.【 解答 】 (1)总线分配前计数器清,0”,从,0”开始查询,优先级排序类似串行链接。
(2)总线分配前不清,0”,从中止点继续查询,是循环优先级,部件使用总线机会均等。
(3)总线分配前将计数器设置初值,可以指定某个部件为最高优先级。
(4)总线分配前将部件号重新设置,可以为各部件指定任意希望的优先级。
7.【 解答 】 (1) 写回法:在 CPU执行写操作时,只是把信息写入 Cache,仅当需要被替换时,才将已经被写入过的 Cache块先送回主存,然后再调入新块进行替换。这种方法要求对每个 Cache块增加一个修改位的资源开销。
(2)写直达法:也称为存直达法,它利用 Cache—
—主存存贮层次在处理机和主存之间的直接通路,
每当处理机写入 Cache的同时,也通过此通路直接写入主存。这种方法要增加写主存的时间开销。
8.【 解答 】 (1)堆栈法:栈顶恒存放近期最久访问过的页的页号,而栈底恒存放近期最久没有访问过的页的页号,即准备被替换掉的页的页号。按此思想组成一个硬件堆栈。
(2)比较对法:让各个块成对组合,用一个触发器的状态来表示该比较对内两块访问的远近次序,再经门电路就可以找到 LRU块。
二,问答题
1.【 解答 】 程序在实际主存空间中的位置可以动态移动的定位技术。一种做法是,在硬件上设置基址寄存器和地址加法器,即在程序装入主存时,只把程序装在主存中的起始地址 (基址 )装入基址寄存器中,对指令各地址字段不作修改;在程序运行时,
由逻辑地址根据需要,加上基址寄存器中的基址来形成访存有效地址。另一种做法是,设置逻辑地址到主存物理有效地址的映象表硬件,即程序装入主存时,在映象表中建立起逻辑地址与主存物理地址的映象关系;程序执行时,由逻辑地址查映象表来获得访主存的物理有效地址。这样,只需修改基址寄存器中的基址或地址映象表的内容,就可以使程序在主存中动态改变所存贮的位置。
2.【 解答 】 (1)中断分类的依据是:把中断源性质相近、中断处理过程类似的归为一类。
(2)中断分类的目的是:为了减少中断处理程序的入口,每一类给一个中断服务程序总入口,可以减少中断服务程序入口地址形成的硬件数量。
(3)中断分为中断 (Interrupt)和异常 (Exception)两类,而异常又细分为自陷 (Trap)、故障 (Fault)和失败 (Abort)三类。具体定义如下:
中断:专指与当前进程运行无关的请求暂停的事件,如机器故障中断请求、外设中断请求、定时中断请求等。中断可以被屏蔽,暂时保存在中断寄存器,屏蔽解除后继续得到响应和处理。
异常:专指由现行指令引起的暂停事件,如页面失效、溢出等,一般不能屏蔽,立即得到响应和处理。
自陷:发生在引起异常的指令执行的末尾,处理后返回原先正常程序的下一条指令继续执行。
故障:发生在执行指令的过程中,处理后返回原先发生故障的那条指令出重复执行。
失败:也发生在指令执行过程中,需强制干预或系统复位才可以使指令再正确执行下去。
3.【 分析 】 Cache存贮器的等效访问时间为:
ta= Hc tc+ (1 - Hc)tm
等效访问速度不高,就是 ta太长。要想缩短 ta,一是要使命中率 Hc尽可能提高,这样,(1 - Hc)tm的分量就会越小,使 ta缩短,越来越接近于 tc 。但如果已非常接近于 tc时,表明 Hc已趋于 1,还想要提高等效访问速度,则只有减小 tc,即更换成更高速的 Cache物理存贮器芯片,才能缩短 ta 。另外,还应考虑 Cache存贮器内部,在查映象表进行 Cache
地址变换的过程时,是否是与访物理 Cache流水地进行,因为它也会影响到 ta 。当命中率 Hc已经很高时,内部的查映象表与访 Cache由不流水改为流水,会对 ta有明显的改进,可以缩短接近一半的时间。所以,分析时要根据不同情况做出不同的结论。
如果 Cache存贮器的等效访问速度不高是由于命中率 Hc太低引起的,在采用 LRU替换算法的基础上,就要设法调整块的大小、组相联映象中组的大小,使之适当增大,这将会使 Hc有所提高。在此基础上再考虑增大 Cache的容量。 Cache存贮器中,只要 Cache 的容量比较大时,由于块的大小受调块时间的限制不可能太大,增大块的大小一般总能使 Cache命中率得到提高。
【 解答 】 (1)增大主存容量,对 Hc基本不影响。虽然增大主存容量可能会使 tm稍微有所增大,如果 Hc
已经很高时,这种 tm的增大,对 ta的增大不会有明显的影响。
(2)增大 Cache的块数,而块的大小不变,这意味着增大 Cache的容量。由于 LRU替换算法是堆栈型替换算法,所以,将使 Hc上升,从而使 ta缩短。 ta的缩短是否明显,还要看当前的 Hc处在什么水平上。
如果原有 Cache的块数较少,Hc较低,则 ta会因 Hc
迅速提高而显著缩短。但如果原 Cache的块数已经较多,Hc已经很高了,则增大 Cache中的块数,不会使 Hc再有明显提高,此时其 ta的缩短也就不明显了。
(3)增大组相联组的大小,块的大小保持不变,从而使组内的块数有了增加,它会使块冲突的概率下降,这也会使 Cache块替换次数减少。而当 Cache各组组内的位置已全部装满了主存的块之后,块替换次数的减少也就意味着 Hc的提高。所以,增大组的大小能使 Hc提高,从而可以提高等效访问速度。不过,Cache存贮器的等效访问速度改进是否明显还要看目前的 Hc处于什么水平。如果原先组内的块数太少,增大组的大小,会明显缩短 ta ;如果原先组内块数已较多,则 ta的缩短就不明显了。
(4)组的大小和 Cache总容量不变,增大 Cache块的大小,其对 ta影响的分析大致与 (3)相同,会使 ta缩短,但要看目前的 Hc水平而定。如果 Hc已经很高,
则增大 Cache块的大小对 ta的改进也就不明显了。
(5)提高 Cache本身器件的访问速度,即减小 tc,只有当命中率 Hc已很高时,才会显著缩短 ta 。如果命中率 Hc较低时,对减小 ta的作用就不明显了。
三,应用题
1.【 解答 】 (1)各级中断处理程序的中断级屏蔽位状态如下表:
中断处理程序级别中断级屏蔽位
1级 2级 3级 4级 5级第 1级第 2级第 3级第 4级第 5级
1
1
1
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
(2)处理机执行程序的全过程如下图:
中断请求 用户程序 1 2 3 4 5
中断处理程序
1 3
2 3 4 5
t
2.【 分析 】 由于 LRU替换算法是堆栈型替换算法,
因而随着分配给该道程序的实页数增加,实页命中率只会上升,至少是不会下降的。但是,当实页数增加到一定程度后,其命中率就不会再提高了。如果要增加分配给该道程序的实页数,只会导致实存空间的利用率下降。所以,只要分别求出分配给该道程序不同实页数时的命中率,找出大到最高命中率时所分配的最少实页数即可。
既然 LRU替换算法是堆栈型的替换算法,对虚页地址流只需用堆栈处理技术处理一次,就可以同时求出不同实页数时各自的命中率。这样,可以大大减少模拟的工作量。
【 解答 】 (1)模拟过程及命中情况如下表:
(2)为获得最高命中率,应分配给该程序 4个实页即可,最高命中率为 H= 6/11。
页地址流堆栈内容实页数
4 5 3 2 5 1 3 2
S(1)
S(2)
S(3)
S(4)
S(5)
时间 t 1 2 3 4 5 6 7 8 9 10 11
n=3
n=4
n≥5
4 5 3 2 5 1 3 2
4 5 3 2 5 1 3
4 5 3 2 5 1
4 4 23
4 4 4 4 4 4
H
H
H
H
H
H
H
H
H
H
H
H
H
5 1 3
5 1 3
2 5 1
3 2 5
3 215