本题采用直接映射的 cache,已知请求访问的字地址依次为: 3,180,43,2,191,88,190,14,181,44,186,253 对于一个 3 路组相联,块大小为 2 个字,总容量为 24 个字,使用 LRU 替换算法的 cache,画图表指出 cache 中最终的内容,对每个访问,标识出索引位,标记位,块偏移位,以及当前访问是命中还是缺失。
时间: 2023-09-10 08:07:34 浏览: 44
首先,我们需要确定 cache 的基本参数:
- 块大小为 2 个字,即 4 字节。
- 总容量为 24 个字,即 6 个块。
- 采用 3 路组相联。
- 使用 LRU 替换算法。
然后,我们需要计算出每个地址的索引位、标记位和块偏移位。由于采用直接映射的 cache,索引位只需要取地址的低 3 位即可。标记位需要取地址的高 8 位。块偏移位需要取地址的中间 7 位。
下表展示了每个地址的索引位、标记位和块偏移位:
| 地址 | 二进制表示 | 索引位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- |
| 3 | 0000 0011 | 011 | 0000 00 | 11 |
| 180 | 1011 0100 | 100 | 1011 01 | 00 |
| 43 | 0010 1011 | 011 | 0010 10 | 11 |
| 2 | 0000 0010 | 010 | 0000 00 | 10 |
| 191 | 1011 1111 | 111 | 1011 11 | 11 |
| 88 | 0101 1000 | 000 | 0101 10 | 00 |
| 190 | 1011 1110 | 110 | 1011 11 | 10 |
| 14 | 0000 1110 | 110 | 0000 00 | 14 |
| 181 | 1011 0101 | 101 | 1011 01 | 01 |
| 44 | 0010 1100 | 100 | 0010 11 | 00 |
| 186 | 1011 1010 | 010 | 1011 10 | 10 |
| 253 | 1111 1101 | 101 | 1111 11 | 01 |
接下来,我们按照地址的顺序,依次访问 cache,并记录每次访问的结果。假设 cache 初始为空,则第一次访问缺失。我们将 3 存入索引为 011 的第 0 组的第 0 块,此时 cache 的状态如下:
| 索引位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- | --- | --- |
| 011 | 0000 00 | 11 | | | | |
| 011 | 0000 00 | 10 | | | | |
| 011 | 0000 00 | 01 | | | | |
下面依次分析其他地址的访问情况:
- 地址 180:缺失。将其存入索引为 100 的第 0 组的第 0 块,此时 cache 的状态如下:
| 索引位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- | --- | --- |
| 011 | 0000 00 | 11 | 100 | 1011 01 | 00 | |
| 011 | 0000 00 | 10 | | | | |
| 011 | 0000 00 | 01 | | | | |
- 地址 43:缺失。将其存入索引为 011 的第 1 组的第 0 块,此时 cache 的状态如下:
| 索引位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- | --- | --- |
| 011 | 0000 00 | 11 | 100 | 1011 01 | 00 | |
| 011 | 0010 10 | 11 | | | | |
| 011 | 0000 00 | 01 | | | | |
- 地址 2:缺失。将其存入索引为 010 的第 0 组的第 0 块,此时 cache 的状态如下:
| 索引位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- | --- | --- |
| 011 | 0000 00 | 11 | 100 | 1011 01 | 00 | |
| 011 | 0010 10 | 11 | | | | |
| 010 | 0000 00 | 10 | | | | |
- 地址 191:缺失。将其存入索引为 111 的第 0 组的第 0 块,此时 cache 的状态如下:
| 索引位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- | --- | --- |
| 011 | 0000 00 | 11 | 100 | 1011 01 | 00 | |
| 011 | 0010 10 | 11 | | | | |
| 010 | 0000 00 | 10 | | | | |
| 111 | 1011 11 | 11 | | | | |
- 地址 88:缺失。将其存入索引为 000 的第 0 组的第 0 块,此时 cache 的状态如下:
| 索引位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- | --- | --- |
| 000 | 0101 10 | 00 | 100 | 1011 01 | 00 | |
| 011 | 0010 10 | 11 | | | | |
| 010 | 0000 00 | 10 | | | | |
| 111 | 1011 11 | 11 | | | | |
- 地址 190:命中。由于索引位为 110 的第 0 组的第 0 块已经存有标记位为 1011 11 的数据块,因此不需要再次存入数据。此时,cache 的状态不变。
- 地址 14:缺失。由于索引位为 110 的第 0 组的第 0 块存有标记位为 1011 11 的数据块,因此需要替换该块。由于采用 LRU 替换算法,根据最近最少使用原则,选择该组中最久未使用的块进行替换,即第 1 块。将地址 14 存入该块,此时 cache 的状态如下:
| 索引位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- | --- | --- |
| 000 | 0101 10 | 00 | 100 | 1011 01 | 00 | |
| 011 | 0010 10 | 11 | | | | |
| 110 | 0000 00 | 14 | | | | |
| 111 | 1011 11 | 11 | | | | |
- 地址 181:缺失。由于索引位为 101 的第 0 组还没有存储任何数据块,因此直接将地址 181 存入该组的第 0 块,此时 cache 的状态如下:
| 索引位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- | --- | --- |
| 000 | 0101 10 | 00 | 100 | 1011 01 | 00 | |
| 011 | 0010 10 | 11 | | | | |
| 110 | 0000 00 | 14 | | | | |
| 101 | 1011 01 | 01 | | | | |
- 地址 44:缺失。由于索引位为 100 的第 0 组的两个块都已经存有数据,因此需要替换其中一个块。根据 LRU 替换算法,选择该组中最久未使用的块进行替换,即第 1 块。将地址 44 存入该块,此时 cache 的状态如下:
| 索引位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- | --- | --- |
| 000 | 0101 10 | 00 | 100 | 1011 01 | 00 | |
| 100 | 0010 11 | 00 | | | | |
| 110 | 0000 00 | 14 | | | | |
| 101 | 1011 01 | 01 | | | | |
- 地址 186:缺失。由于索引位为 010 的第 0 组已经存有标记位为 1011 10 的数据块,因此需要替换该块。由于采用 LRU 替换算法,选择该组中最久未使用的块进行替换,即第 1 块。将地址 186 存入该块,此时 cache 的状态如下:
| 索引位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- | --- | --- |
| 000 | 0101 10 | 00 | 100 | 1011 01 | 00 | |
| 100 | 0010 11 | 00 | | | | |
| 010 | 1011 10 | 10 | | | | |
| 101 | 1011 01 | 01 | | | | |
- 地址 253:缺失。由于索引位为 101 的第 0 组已经存有标记位为 1011 01 的数据块,因此需要替换该块。由于采用 LRU 替换算法,选择该组中最久未使用的块进行替换,即第 0 块。将地址 253 存入该块,此时 cache 的状态如下:
| 索引位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- | --- | --- |
| 000 | 0101 10 | 00 | 100 | 1011 01 | 00 | |
| 100 | 0010 11 | 00 | | | | |
| 010 | 1011 10 | 10 | | | | |
| 101 | 1111 11 | 01 | | | | |
最终,cache 中存储的数据如下:
| 索引位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 | 标记位 | 块偏移位 |
| --- | --- | --- | --- | --- | --- | --- |
| 000 | 0101 10 | 00 | 100 | 1011 01 | 00 | |
| 100 | 0010 11 | 00 | | | | |
| 010 | 1011 10 | 10 | | | | |
| 101 | 1111 11 | 01 | | | | |
| 011 | 0010 10 | 11 | | | | |
| 110 | 0000 00 | 14 | | | | |
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)