计算机系统结构期末重点题目及考点

第一章：1.2.如有一个经解释实现的计算机，可以按功能划分成4级。每一级为了执行一条指令需要下一级的N条指令解释，若执行第一级的一条指令需kns，那执行第2级、第3级、第4级的指令需要多少时间？第1级1条1级指令kns第2级1条2级指令N条1级指令1·N·kns=Nkns第3级1条3级指令N条2级指令1·N·N·kns=N2kns第4级1条4级指令N条3级指令1·N·N·N·kns=N3kns1.8.从机器（汇编）语言程序员看，以下哪些是透明的？指令地址寄存器；指令缓冲器；时标发生器；条件码寄存器；乘法器；主存地址寄存器；磁盘外设；先行进位链；移位器；通用寄存器；中断字寄存器。见下表，“√”为透明性概念第二章：2.2在尾数采用补码、小数表示且p=6，阶码采用移码、整数表示且q=6，尾数基rm为16，阶码基re为2的情况下：(1)最大尾数为：1－rm-p＝1－16-6，0.FFFFFF(2)最小正尾数为：1/rm＝1/16，0.100000(3)最小尾数为：-1，1.000000(4)最大负尾数为：-(rm-1+rm-p)＝(16-1+16-6)，1.EFFFFF(5)最大阶码为：req－1＝26－1＝63，7F，包括符号位共7个1(6)最小阶码为：-req＝-26＝-64，00，包括符号位共7个0(7)最大正数为：(1－16-6)1663，7FFFFFFF(8)最小正数为：16-65，00100000(9)最大负数为：-(16-1+16-6)16-64，80EFFFFF(10)最小负数为：-1663，FF000000(11)浮点零为：00000000(12)表数精度为：16-5/2＝2-21《13)表数效率为：15/16＝93.75％(14)能表示的规格化浮点数个数为：2×15×165×27+12.13一个处理机共有10条指令，各指令在程序中出现的概率如下表：指令信号出现概率Huffman编砝码2/8扩展编砝码3/7扩展编砝码I10.25010000I20.20110101指令地址寄存器，×，指令缓冲器，√，时标发生器，√，条件码寄存器，×，乘法器，√，主存地址寄存器，√，磁盘，×，先行进位链，√，移位器，√，通用寄存器，×，中断字寄存器，×，I30.15001100010I40.10101100111000I50.080000101011001I60.081001101111010I70.051000110011011I80.0400011110111100I90.03000101111011101I100.020001001111111100已知10条指令使用频度，求3种编码方法的平均码长与信息冗余量。(1)此问中的“最优Huffman编码法”实际是指码长下限，即信源的平均信息量──熵，代公式得H=2.9566。(2)Huffman编码性能如下表；(3)2/8扩展编码是8/64/512法的变种，第一组2条指令，码长为2（1位扩展标志，1位编码）,第二组8条指令，码长为4（1位扩展标志，与第一组区别，加3位编码），编码性能如下表；(4)3/7扩展编码是15/15/15法的变种，第一组3条指令，码长为2（共有4种组合，其中3种组合分别代表3条指令，留1种组合作为扩展前缀标志）,第二组7条指令，码长为5（2位固定的前缀扩展标志，与第一组区别，加3位编码，只用其中7种组合），编码性能如下表。2.14一台模型机共有7条指令，各指令的使用频率分别为35%，25%，20%，10%，5%，3%和2%，有8个通用数据寄存器，2个变址寄存器。(1)要求操作码的平均长度最短，请设计操作码的编码，并计算所设计操作码的平均长度。(2)设计8字长的寄存器-寄存器型指令3条，16位字长的寄存器-存储器型变址寻址方式指令4条，变址范围不小于±127。请设计指令格式，并给出各字段的长度和操作码的编码。解：(1)要使得到的操作码长度最短，应采用Huffman编码，构造Huffman树如下：0.350.250.200.100.050.030.020.050.100.200.400.601.00Huffman编码2/8扩展编码3/7扩展编码平均码长L2.993.13.2信息冗余量R1.10%4.61%7.59%由此可以得到7条指令的编码分别如下：指令出现的频率编码135%00225%01320%10410%11055%111063%1111072%11111这样，采用Huffman编码法得到的操作码的平均长度为：H=2×(0.35+0.25+0.20)+3×0.10+4×0.05+5×(0.03+0.02)=1.6+0.3+0.2+0.25=2.35(2)设计8位字长的寄存器-寄存器型变址寻址方式指令如下，因为只有8个通用寄存器，所以寄存器地址需3位，操作码只有两位，设计格式如下：765320操作码OP源寄存器R1目的寄存器R2三条指令的操作码分别为00，01，10设计16位字长的寄存器-存储器型变址寻址方式指令如下：15121198操作码OP通用寄存器变址寄存器偏移地址70四条指令的操作码分别为1100，1101，1110，11112.15某处理机的指令字长为16位，有双地址指令、单地址指令和零地址指令三类，并假设每个地址字段的长度均为6位。(1)如果双地址指令有15条，单地址指令和零地址指令的条数基本相同，问单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。(2)如果要求三类指令的比例大致为1：9：9，问双地址指令、单地址指令和零地址指令各有多少条？并且为这三类指令分配操作码。解：(1)15条/63条/64条(2)14条/126条/128条(1)根据指令地址的数量来决定各种指令在指令空间上的分布：如果我们按照从小到大的顺序分配操作码，这样，按照指令数值从小到大的顺序，分别为双地址指令、单地址指令和零地址指令。其次可以根据指令的条数来大致的估计操作码的长度：双指令15条，需要4位操作码来区分，剩下的12位操作码平均分给单地址和零地址指令，每种指令可以用6位操作码来区分，这样，各指令的条数为：双地址指令15条，操作码：0000~1110；单地址指令2^6-1=63条，操作码：1111000000~1111111110；零地址指令64条，操作码：1111111111000000~1111111111111111。(2)与上面的分析相同，可以得出答案：双地址指令14条，操作码：0000~1101；单地址指令2^6x2-2=126条，1110000000~1110111110，1111000000~1111111110；零地址指令128条1110111111000000~1110111111111111,1111111111000000~1111111111111111(2)B双地址指令同上,14条，操作码：0000~1101；单地址指令64+62=126条，64条单地址指令操作码1110000000~1110111111，62条单地址指令操作码1111000000~1111111101；零地址指令128条1111111110000000~1110111110111111,1111111111000000~1111111111111111第三章：3.9：一个页式虚拟存储器的虚存空间大小为4Gb，页面大小为4KB，每个页表存储子要占用4个字节。（1）计算这个页式虚拟存储器需要采用几级页表？答：Log2（4G/4K）/Log2（4K/4）=2.0.取整得2，所以需要2级页表（2）如果要求页表所占用的总主存页面数最小，请分配每一级页表的实际存储容量各为多少字节？答：第一季页表为一个页面大小，为4kb，第二级页表被占用1k个页面，为4mb（3）页表的哪些部分必须存放在主存中？哪些可以放在辅存中？答：第一级页表必须放在主存中，二级页表只需将正在运行的程序的相关页表放在主存中，其他都可以放在辅存中。3.12一个有快表和慢表的页式虚拟存储器，最多有64个用户，每个用户最多要用1024个页面，每页4K字节，主存容量8M字节。（1）写出多用户虚地址的格式，并标出各字段的长度。（2）写出主存地址的格式，并标出各字段的长度。（3）快表的字长为多少位？分几个字段？各字段的长度为多少位？（4）慢表的容量是多少个存储字？每个存储字的长度为多少位？答：用户号：64＝26，虚页号：1024＝210，页内地址：4K＝212，主存页数：8M/4K＝211（1）多用户虚地址：用户号（6位）＋虚页号（10位）＋页内地址（12位）共28位（2）主存地址：主存实页号（11位）＋页内地址（12位）共23位（3）快表字长27位；分3个字段：用户号6位，虚页号10位，实页号11位（4）（4）慢表容量为2(6+10)，每个存储字长为：主存页号＋1＝12位。3.143.14在页式虚拟存储器中，一个程序由P1~P5共5个虚页组成。在程序执行过程中依次访问到的页面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2假设系统分配给这个程序的主存有3个页面，分别采用FIFO、LRU和OPT三种替换算法对这三页主存进行调度。（1）画出主存页面调入、替换和命中的情况表。（2）统计三种页面替换算法的页命中率。答案：解：三种替换算法的替换过程：页地址流232152453252FIFO222255553333命中3次33332222255111444442调调命调替替替命替命替替进进中进换换换中换中换换222152453252LRU33215245325命中5次321524533调调命调替命替命替替命命进进中进换中换中换换中中OPT222222444222命中6次333333333331555555555调调命调替命替命命替命命进进中进换中换中中换中中3.15.一个程序由五个虚页组成，采用lfu替换算法，在程序中依次访问的页地址流如下：P4，P5，P3，P2，P5，P1，P3，P2，P3，P5，P1，P3(1)可能的最高页命中率是多少？(2)至少要分配给该程序多少个主存页面才能获得最高的命中率?(3)如果在程序中每访问一个页面，平均要对该页面内的存储单元访问1024次，求访问单元的命中率？答案：（1）在分配的主存页面数目大于等于5的情况下，这时，除了第一次调入不命中，以后的访问均命中，可以达到最高的页面命中率：实际命中的次数为7次，所以可能达到的最高页面命中率为：5833.0127H（2）由于在页面数大于等于5的情况下，肯定可以达到最高命中率，所以我们来看页面数小于5时能否达到该命中率：分配的主存页面数等于4时，调度过程如下：此时也可以达到最高命中率；分配的主存页面等于3时，调度过程如下：LFU算法44444*11111*11命中7次555*55555*5553333*33*333*32222*22222调入调入调入调入命中调入命中命中命中命中命中命中此时不能达到最高命中率。所以至少应该分配4个主存页面。（3)我们假设程序每次只访问一个存储单元，这样，对每一个特定页面的访问过程可以描述如下：因为第一次总是不命中的，而平均起来，随后的1023次总是命中的，然后再次被调出主存，并再次重复先前的过程。所以访问存储单元的命中率为：999.010241023H欲知可能的最高命中率及所需的最少主存页数，较好的办法是通过“堆栈模拟法”，求得命中次数随主存页数变化的函数关系。下图就是“堆栈模拟图”，其中“√”表示命中。(1)Hmax=7/12≈58.3%(2)n=4P=453251323513命中次数4532513235134532513235145325112354432551224444444n=10n=2√1n=3√√√3n=4√√√√√√√7n=5√√√√√√√7LFU算法444*222*33*333*3命中3次555*555*222*11333*1111*555调入调入调入调入命中调入调入调入命中调入调入命中(3)当1次页面访问代表连续1024次该页内存储单元访问时，后1023次单