当前位置：问答库＞考研试题

一、应用题

1． 某计算机的主存地址空间大小为256MB ，按字节编址，指令Cache 和数据Cache 分离，均有8个Cache 行，每个Cache 行大小为64B , 数据Cache 采用直接映射方式。现有两个功能相同的程序A 和B , 其伪代码如下所本：程序A :程序B :

假定int 类型数据用32位补码表示，程序编译时i , j , sum 均分配在寄存器中，数组a 按行优先方式存放，首地址320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。

（1）若不考虑用于Cache —致性维护和替换算法的控制位，则数据Cache 的总容量为多少？ （2）数组数据号从0开始）？

（3）程序A 和B 的数据访问命中率各是多少? 哪个程序的执行时间更短？

【答案】（1）每个Cache 行对应一个标记项，标记项包括有效位、脏位、替换控制位以及标记位。由主存空间大小为256M 可知地址总长度为28位，其中块内地址为log264=6位，Cache 块号为log28=3位，不考虑一致性维护和替换算法的控制位，则Tag 的位数为28-6-3=19位，还需一位有效位，数据Cache 共有8行，故Cache 的总容量为

（2）数组a 在主存的存放位置及其与Cache 之间的映射关系如下图所示： 和各自所在的主存块对应的Cache 行号分别是多少（Cache 行

图

数组按行优先方式存放，首地址为320, 数组元素占4个字节。

Cache 行号

为

（3）数组a 的大小为逐行访问数

组a ，共需访问的次数为

A 的数据访问命中率为次，每个字块的第一个数未面中，因此未面中次数为Cache 总容量为次，程序数组a —行的大占用个主存块，按行优先存放，程序A 所在的主存块对应的所在的主存块对应的Cache 行号

为小为1KB 正好是Cache 容量的2倍，可知不同行的同一列数组元素使用的是同一个Cache 单元，而程序B 逐列访问数组a 的数据时，都会将之前的字块置换出，也即每次访问都不会面中，故程序B 的数据访问命中率是0, 因此程序A 的执行过程更短。

2． 设某计算机的逻辑地址空间和物理地址空间均为64KB , 按字节编址。若某进程最多需要6页（Page ）数据存储空间，页的大小为1KB , 操作系统采用固定分配局部置换策略为此进程分配4个页框（PageFrame ）。在时刻260前的该进程访问情况如下表所示（访问位即使用位）。

当该进程执行到时刻260时，要访问的逻辑地址为17CAH 的数据，请回答下列问题： （1）该逻辑地址对应的页号是多少？

（2）若采用先进先出（FIFO ）置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过程。

（3）若采用时钟（CLOCK ）置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过

程。（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，如图所示）

图

【答案】（1）由题可知计算机的逻辑地址空间和物理地址空间均为64KB=216B, 按字节编址，并且页的大小为IK=210, 故逻辑地址和物理地址的地址格式均为：

地址17CA=0001011111001010B，故可知其逻辑页号为000101B=5。

（2）根据FIFO 算法，需要替换出最早装入的页，故需置换0号页，将5号页装入7号页框中，所以物理地址为0001111111001010B=1FCAH。

（3）根据CLOCK 算法，如果当前指针所指页框的使用位为0, 则替换该页，否则将使用位清零，并将指针指向下一个页框，继续查找。由题可知，将从2号页框开始，前4次查找页框号的顺序为2、4、7、9, 并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2号页框的使用位已经为0, 故将2号页框的页将5号装入2号页框，并将其对应使用位设置为1, 所以对应的物理地址为0000101111001010B=0BCAH。

3． 画出对算术表达式求值时操作数栈和运算符栈的变化过程。

【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式

表所示。

表 操作数栈和运算符找的变化过程 求值，过程如