计算机系统结构作业

说明：

大二下学期计算机系统结构课程课后作业，题目来源：课后题

1.1

题目

解释下列术语

层次结构；计算机系统结构；计算机组成；计算机实现；透明性；由上往下设计；由下往上设计；系列机；软件兼容；兼容机；模拟；仿真；虚拟机；宿主机；指令流；数据流；Amdahl定律；CPI；MIPS；MFLOPS

答

层次结构

• 定义

  层次结构在这里指计算机系统层次结构。计算机系统系统由硬件和软件组成，按功能划分为7级层次结构。

  每一级对应一种机器（虚拟机器由软件实现，实际机器由硬件实现），从第0级到第6级，级数越低越靠近硬件，级数越高越靠近软件。

  在某层次的观察者视角中，他只是通过该层次的语言了解和使用计算机，不必关心低层次的那些机器的工作原理，也就是对于高层来说低层是透明的。

• 个人理解

  计算机系统层次结构是计算机领域分层思想的一种应用，计算机网络的体系结构（OSI七层协议等）也是。在层次结构中，每层负责解决一定的问题，即具有一定的功能。一般来说，底层为高层提供一定的服务。

• 示意图

  

计算机系统结构

• 定义

  “计算机系统结构”这个名词来源于英文computer architecture，目前并无统一定义，现以Amdahl定义举例。

  Amdahl等人在1964年提出计算机系统结构这个名词，他们将其定义为程序设计者所看到的一个计算机系统（也就是上边提到的机器）的属性，即概念性结构和功能特性，这是程序员为了使其编写的程序能在机器上正确运行，需要了解和遵循的计算机属性。

  计算机系统结构主要研究软件、硬件功能分配和对软件、硬件界面的确定，即哪些功能由软件完成、哪些功能由硬件完成。

  Amdahl等人对计算机系统结构定义的主要内容是指令系统及其执行模型，然而随着新器件的出现，计算机系统结构的定义还应包括功能模块的设计。

• 个人理解

  如果把计算机这门科学涉及的知识进行分层，计算机系统结构则是软件和硬件的交界处，硬件是计算机组成原理的主要内容，软件则是操作系统等。

• 分类方法

  • Flynn分类法

    按照指令流和数据流的不同组织方式进行分类，分为以下四类：

    • 单指令流单数据流SISD
    • 单指令流多数据流SIMD
    • 多指令流单数据流MISD
    • 多指令流多数据流MIMD

  • 冯氏分类法

    冯泽云提出用最大并行度对计算机系统结构进行分类，分为以下四类：

    • 字串位串WSBS
    • 字并位串WPBS
    • 字串位并WSBP
    • 字并位并WPBP

  • Handler分类法

    Wolfgan Handler在1977年根据并行度和流水线提出了一种分类法，其将计算机的硬件结构分为三个层次，并分别考虑它们的可并行-流水处理程度，以下为三个层次：

    1. 程序控制部件的个数
    2. 算术逻辑部件或处理部件的个数
    3. 每个算术逻辑部件包含基本逻辑线路的套数

计算机组成

计算机组成是计算机系统结构的逻辑实现，包括机器内部的数据流和控制流的组成以及逻辑设计等。

其任务是在计算机系统结构确定分配给硬件子系统的功能及其概念结构之后，研究各组成部分的内部构造和相互联系，以实现机器指令级的各种功能和特性。

计算机实现

计算机实现是指计算机组成的物理实现。

透明性

透明指的是本来存在的事物和属性，从某种角度来看，它是不存在的。

个人理解：

计算机网络中物理层的实现对于网络层来说就是透明的，网络层并不知道物理层的内部实现，仅知道物理层的外部接口而已。

就像课堂上老师要收作业，他不知道课代表是怎么收的，课代表怎么收作业对于老师来说就是透明的。

由上往下设计

与由下往上设计对应，根据计算机系统结构的分成，从最高层开始设计每层的功能与实现。

由下往上设计

根据计算机系统结构的分层，从最低层开始设计每层的功能与实现。

这种方法以前较为适宜，因为那时硬件成本昂贵，硬件技术水平低，软件技术和硬件技术相比往往处于被动地位。

系列机

系列机是指在一个厂家内生产的具有相同的系统结构，但具有不同组成和实现的一系列不同型号的机器。

软件兼容

同一个软件可以不加修改地运行于系统结构相同的各档机器，可获得相同的结果，差别只在于不同的运行时间。

系列机的软件兼容分为向上兼容、向下兼容、向左兼容、向右兼容。

兼容机

不同厂家生产的具有相同系统结构的计算机称为兼容机。它的思想与系列机的思想是一致的。

模拟

模拟指用软件方法在一台现有的计算机上实现另一台计算机的指令系统。

通过解释方法把B机器的每一条指令用A机器的指令进行解释执行。

A机器称为宿主机，B机器称为虚拟机。

仿真

用微程序直接解释另一种机器指令系统的方法称为仿真。

虚拟机

模拟中已介绍。

宿主机

模拟中已介绍。

指令流

机器执行的指令序列。

数据流

由指令流调用的数据序列，包括输入数据和中间结果。

Amdahl定律

系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关。

CPI

每条指令的平均时钟周期。

$$CPI=CPU时钟周期数目/IC$$

MIPS

每秒百万条指令数。

$$MIPS=\frac{指令条数}{执行时间\times10^6}=\frac{时钟频率}{CPI\times10^6}$$

MFLOPS

每秒百万次浮点操作次数。

$$MFLOPS=\frac{程序中的浮点操作次数}{执行时间\times10^6}$$

1.5

题目

硬件和软件在什么意义上是等效的？在什么意义上又是不等效的？试举例说明

答

• 个人理解

  计算机系统结构的设计主要在功能这一层次上考虑问题。

  在功能这个层次上考虑，软件和硬件是等效的，即软件和硬件都实现了同样的功能。

  从功能实现的原理这个层次上考虑，软件和硬件是不等效的，两者的实现方式是不同的，成本、效率等指标也会有不同。

• 举例

  比如存储器管理，不管用硬件还是软件，都可以实现相同的存储器管理功能，但两者的实现方法和性能都是不同的。

1.6

题目

试以实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系和相互影响。

答

• 相互关系

  • 一种系统结构可以有多种组成

    比如系列机系统结构相同，指令的执行顺序既可以是顺序执行，又可以是重叠、流水线等执行顺序。

  • 一种组成可以有多种物理实现

    比如同样的组成，主存既可以使用双极型，又可以使用MOS型。

• 相互影响

  系统结构不同，采用的计算机组成也不同，同样计算机组成也会影响系统结构。

1.12

题目

如果某一计算任务用向量方式求解比用标量方式求解快20倍，称可用向量方式求解部分所花时间占总的时间的百分比为可向量化百分比。

画出加速比与向量化比例两者关系的曲线。

答

该题考察Amdahl定律，

$$S_n=\frac{T_0}{T_n}=\frac{1}{(1-Fe)+\frac{Fe}{Se}}$$

上式中$Sn$为加速比；

$Fe$为$\frac{可改进部分占用时间}{改进前整个任务的执行时间}$；

$Se$为$\frac{改进前改进部分的执行时间}{改进后改进部分的执行时间}$。

可知可向量化百分比即为$Fe$，且$Se=\frac{20}{1}=20$。（虽说快20倍，这里应该是21的，为简化计算，就这样吧..…）

由上，可得下式：

$$S_n=\frac{1}{1-0.95Fe}$$

MATLAB代码：

Fe=0:0.02:1;
Sn=1./(1-0.95*Fe);
plot(Fe,Sn);
grid minor;
xlabel('加速比Sn');
ylabel('向量化比例Fe');

作图如下：

1.13

题目

题1.12中为达到加速比2，可向量化的百分比应是多少？

答

解下式：

$$2=\frac{1}{1-0.95Fe}$$

得$Fe\approx0.526$。

2.14

问题

一台模型机共有7条指令，各指令的使用频度分别为35%，25%，20%，10%，5%，3%，2%，有8个通用数据寄存器，2个变址寄存器。问题如下：

1. 要求操作码的平均长度最短，请设计操作码的编码，并设计所设计操作码的平均长度。
2. 设计8位字长的寄存器-寄存器型指令3条，16位字长的寄存器-存储器型变址寻址方式指令4条，变址范围不小于正、负127。请设计指令格式，并给出各字段的长度和操作码的编码。

答

第1问

由题可知，要求操作码平均长度最短，所以应使用哈夫曼编码，指令使用频度越高，其操作码长度应越短。

指令操作码设计如下

指令序号	使用频度	Huffman编码	操作码长度
1	0.35	0	1
2	0.25	10	2
3	0.20	110	3
4	0.10	1110	4
5	0.05	11110	5
6	0.03	111110	6
7	0.02	111111	6

指令操作码平均长度为：

$$H=0.35\times1+0.25\times2+0.20\times3+0.10\times4+0.05\times5+0.03\times6+0.02\times6=2.4$$

第2问

• 寄存器-寄存器型指令

指令序号	编码（2位）	通用寄存器（3位）	通用寄存器（3位）
1	00	R	R
2	01	R	R
3	10	R	R

• 寄存器-存储器型变址寻址方式指令

指令序号	编码（4位）	通用寄存器（3位）	变址寄存器（1位）	地址偏移量（8位）
1	1100	R	X	A
2	1101	R	X	A
3	1110	R	X	A
4	1111	R	X	A

2.17

问题

在一般通用计算机中，按照指令所完成的功能来划分，应该有哪几类指令？各类指令的主要任务是什么？

答

一般来说，要有5类基本指令：数据传输类指令、运算类指令、程序控制类指令、输入输出指令、处理机控制和调试指令。

数据传送类指令

• 主要任务

  在相同或不同的数据存储设备之间传送数据。

• 数据传输指令的种类有如下三个主要因素决定：

  • 数据存储设备的种类
  • 数据传送的单位
  • 采用的寻址方式

运算类指令

• 主要任务

  承担计算机的主要任务：运算（包括数据计算和符号处理）

• 设计运算类指令时主要考虑如下四个因素的组合

  • 操作种类
  • 数据表示
  • 数据长度
  • 数据存储设备

程序控制指令

• 主要任务

  实现流程控制

• 程序控制指令主要包括三类

  • 转移指令（包括无条件转移和有条件转移）
  • 程序调用和返回指令
  • 循环控制指令

输入输出指令

• 主要任务
  • 启动、停止、测试设备
  • 数据输入、输出
  • 对设备进行控制
  • 等等

处理机控制和调试指令

一般计算机系统中，处理机有两个状态：管态和用户态，或称主态和从态。这两个状态需要相互切换，而且这两个状态下所能使用的指令应该有所区别

• 主要任务

  对不同状态的处理机进行控制

3.9

问题

一个页式虚拟存储器的虚存空间大小为4GB，页面大小为4KB，每个页表存储字要占用4个字节。

1. 计算这个页式虚拟存储器需要采用几级页表？
2. 如果要求页表所占的主存页面数最少，请分配每一级页表的实际存储容量各为多少字节？
3. 页表的哪些部分必须存放在主存中？哪些可以存放在辅存中？

答

第1问

由题可知

$N_v=4GB$，$N_p=4KB$，$N_d=4B$

可得页表级数：

$$g=\lceil\frac{log_2N_v-log_2N_p}{log_2N_p-log_2N_d}\rceil=\lceil\frac{32-12}{12-2}\rceil=2$$

所以需要采用2级页表

第2问

一个页可存储的页表存储字的个数为：$\frac{N_p}{N_d}=1K=2^{10}$

虚拟空间的总页数为：$\frac{N_v}{N_p}=1M=2^{20}$

设第一级页表要用N个页表存储字

由第1问可得，使用2级页表，则$N\times\frac{N_p}{N_d}=\frac{N_v}{N_p}$，得$N=2^{10}$，

由上可得

第一级页表占用一个页面的大小，即$N_d\times\frac{N_p}{N_d}=4KB$。

第二级页表占用1K个页面的大小，即$N_d\times\frac{N_v}{N_p}=4MB$。

第3问

为节省内存空间，第一级页表必须存放在主存中，第二级页表只需要把正在运行的程序的相关页表放在主存中，其他的可以放在外存中。

3.11

问题

一个页式虚拟存储器按字节编址，页面大小为1K个字节，每个数据的字长为4个字节。现有一个程序的页表如下：

虚页号	装入标志	主存（实）页号	修改标志	访问方式
0	1	2	0	RW
1	1	3	0	R
2	0	0	0	R
3	1	1	0	X
4	0	0	0	RW
5	1	0	0	R
6	0	0	0	X

表中的装入标志为‘1’表示该虚页已经装入主存，为‘0’则表示还未装入主存。修改标志为‘0’表示该页还没有被修改过，为‘1’则表示该页已经被修改过。访问方式‘RW’表示该页可以读可以写，但不能作为指令来执行；‘R’表该页只能读，不能写和执行；‘X’表示该页只能作为指令来执行，不能读和写。

虚地址经变址寻址和基址寻址（B）+（X）+D形成。现有一个程序，出现下列访问主存的操作：

序号	操作	（B）	（X）	D
1	取数	124	30	50
2	取数	2000	1000	60
3	存数	4000	2000	600
4	存数	1200	4600	60
5	取数	3000	640	100
6	取数	4096	500	20
7	加并存数	400	1200	80
8	加并存数	36	360	64
9	转移	2500	600	100
10	转移	3600	1200	56

1. 列出产生主存页面失效的操作序号
2. 如果不发生主存页面失效的话，计算访问主存的物理地址
3. 列出被修改过的主存页面号
4. 列出非法操作的序号

答

由题可知，该页式虚拟存储器按字节编址，页面大小为1K个字节，每个数据的字长为4个字节。

地址0-999是0号虚/实页，地址1000~1999是1号虚/实页，以此类推

实页内的偏移地址和虚页内的偏移地址相同

操作序号	虚地址	虚页号	实页号	页内偏移	实（物理）地址	操作	合法性
1	204	0	2	50	2098	未改	合法
2	3060	3	1	60	1084	未改	非法
3	6600	6	未装入	600	无	失效	无
4	5860	5	0	60	0060	未改	非法
5	3740	3	1	100	1124	未改	非法
6	4616	4	未装入	20	无	失效	无
7	1680	1	3	80	3116	未改	非法
8	460	0	2	64	2128	修改	合法
9	3200	3	1	100	1124	未改	合法
10	4856	4	未装入	56	无	失效	无

第1问

3、6、10

第2问

表中已计算

第3问

2

第4问

2、4、5、7

3.14

问题

在页式虚拟存储器中，一个程序由P1~P5共5个页面组成。在程序执行过程中依次访问到的页面如下：

P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2

假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LFU、OPT三种页面替换算法对这3页主存进行调度。

1. 画出主存页面调入、替换和命中的情况表。
2. 统计三种页面替换算法的页命中率。

答

• FIFO

  把最先进来的替换走。

  方法：向每行回看，出现次数最多的指令待换出

• LFU

  把最久没有使用的替换掉。

  方法：向页地址流回看，最后出现的指令待换出

• OPT

  把最晚要使用的替换掉。

  方法：向页地址流后看，最后访问的指令待换出

4.4

问题

有5个中断源D1、D2、D3、D4和D5，它们的中断优先级从高到低分别是1级、2级、3级、4级和5级。这些中断源的中断优先级、正常情况下的中断屏蔽码和改变后的中断屏蔽码见下表。每个中断源有5位中断屏蔽码，其中，‘1’表示该中断源被屏蔽，‘0’表示该中断源开放。

中断源名称	中断优先级	正常的中断屏蔽码D1 D2 D3 D4 D5	改变后的中断屏蔽码
D1	1	1 1 1 1 1	1 0 0 0 0
D2	2	0 1 1 1 1	0 1 0 0 0
D3	3	0 0 1 1 1	1 0 1 0 0
D4	4	0 0 0 1 1	1 1 0 1 1
D5	5	0 0 0 0 1	1 1 1 0 1

1. 当使用正常的中断屏蔽码时，处理机响应各中断源的中断服务请求的先后次序是什么？实际的中断处理次序是什么？
2. 当使用改变后的中断屏蔽码时，处理机响应各中断源的中断服务请求的先后次序是什么？实际上中断处理的次序是什么？
3. 如果采用改变后的中断屏蔽码，当D1、D2、D3、D4和D5这5个中断源同时请求中断服务时，画出处理机响应中断源的中断服务请求和实际运行中断服务程序过程的示意图。
4. 假设从处理机响应中断源的中断服务请求开始，到运行中断服务程序中第一次开中断所用的时间为1个单位时间，处理机运行中断服务程序的其他部分所用的时间为4个单位时间。当处理机在执行主程序时，中断源D3、D4和D5同时发出中断服务请求，过3个单位时间之后，中断源D1和D2同时发出中断服务请求。采用改变后的中断屏蔽码，画出处理机响应各中断源的中断服务请求和实际运行中断服务程序过程的示意图。

答

第1问

使用正常的中断屏蔽码，处理机的中断服务顺序将严格按照中断源的中断优先级进行。

中断服务请求的响应顺序是D1、D2、D3、D4、D5。

实际的中断处理次序是D1、D2、D3、D4、D5。

第2问

中断服务请求的响应顺序是D1、D2、D3、D4、D5。

实际的中断处理次序是D4、D5、D3、D2、D1。

第3问

第4问

---

作者：@臭咸鱼

转载请注明出处：https://chouxianyu.github.io

欢迎讨论和交流!

---