总复习
第 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