系统结构第三章答案存储系统

一、在页式虚拟存储器中，一个程序由0~4共5个虚页组成，在程序执行过程中，访存虚页地址流为：0，1，0，4，3，0，2，3，1，3假设分配给这个程序的主存空间有3个实页，分别采用FIFO、LRU和OPT替换算法进行替换调度。（1）分别画出3种替换算法对主存3个实页位置的使用过程。（2）分别计算3种替换算法的主存命中率。解（1）分别用FIFO、LRU和OPT替换算法对主存3个实页位置的使用过程如图（2）由使用过程可得：FIFO替换算法的主存命中率为：H1=2/10=0.20；LRU替换算法的主存命中率为：H2=4/10=0.40；OPT替换算法的主存命中率为：H3=5/10=0.50。二、有一个Cache存储器，主存有8块（0~7），Cache有4块（0~3），采用组相联映像，组内块数为2块。采用LRU替换算法。（1）写出主存地址和Cache地址的格式，并指出各字段的长度。（2）指出主存各块与Cache各块之间的映像关系。（3）某程序运行过程中，访存的主存块地址流为：1，2，4，1，3，7，0，1，2，5，4，6，4，7，2说明该程序访存对Cache的块位置的使用情况，指出发生块失效且块争用的时刻，计算Cache命中率。解：（1）采用组相联映像时，主存地址格式和Cache地址格式为：主存按Cache大小划分为区，主存容量为8块，Cache容量为4块，故主存分为2个区，区号E的长度为1位。组内有2块，故组内块号B和b的长度都是1位。Cache被分为2组，故组号g的长度是1位；主存的一个区也被分为2组，故区内组号G的长度也是1位。块内地址W和w的长度由块的大小确定，由本题给出的条件，不能确定块的大小，因而不能确定W和w的长度。（2）组相联映像规定：主存的组到Cache的组之间是直接映像，对应组的块之间是全相联映像。因此，主存块0~7与Cache块0~3之间的映像关系如图4.15所示。可得出主存块0~7与Cache块0~3之间的映像关系是：主存块0、1、4、5只能装入Cache块0、1的任何块位置上主存块2、3、6、7只能装入Cache块2、3的任何块位置上（3）采用LRU替换算法时，Cache的块0~3被该程序使用的过程如图4.16所示。需要注意的是：当装入Cache块0和块1位置上的主存块发生块冲突时，就要由替换算法指定其中的被替换主存块；当装入Cache块2和块3位置上的主存块发生块冲突时，也要由替换算法指定其中的被替换主存块。因此，当Cache的4个块位置（0~3）都被装入时，其中的2个主存块就会被指定为被替换块。在图4.16中用星号“*”标示被替换算法指定的被替换块。发生块失效且块争用时需要进行替换，在Cache使用过程中，发生块失效且块争用的时刻有：t6,t7,t9,t10,t11,t12,t14,t15。命中3次：在t4时，命中Cache块0位置上的主存块1；在t8时，再次命中主存块1；在t13时，命中Cache块0位置上的主存块4。Cache命中率为H=3/15=0.20。三、假设某程序不计访存时间的指令执行时间都为2个时钟周期，平均每条指令访存1.33次。增设Cache后，程序访存命中Cache的概率为98%，命中Cache时指令用于访存所需时间为2个时钟周期，未命中Cache时指令用于访存所需时间为50个时钟周期。请分别计算不设置Cache和增设Cache两种情况下的程序的指令平均执行时间（指令平均时钟周期数），以及增设Cache相对于不设置Cache的加速比。解:不设置Cache时，平均每条指令访存所需时间为：50×1.33=66.5时钟周期不计访存时间的指令平均执行时间为2个时钟周期，所以，包括访存时间在内的指令执行的平均时钟周期数为：CPIM=66.5+2=68.5时钟周期增设Cache后，平均每条指令一次访存所需时间为：T=HTc+(1–H)TM=0.98×2+(1–0.98)×50=2.96时钟周期包括访存时间在内的指令执行的平均时钟周期数为：CPI=2.96×1.33+2=5.94时钟周期增设Cache相对于不设置Cache的加速比为：S=CPIM/CPI=68.5/5.94=11.53