计组+OS | 【Cache】Cache容量、位数、缺失损失、命中率等相关计算总结与例题

应用题技巧：

主存容量 →  物理地址即主存地址 位数

主存字块标记： 主存容量跟缓存容量之比，主存总地址比缓存总地址长出来的位数.

Cache字块标记： 缓存总容量跟每一块的容量之比，缓存的总的地址长度减去字块内的地址长度

注意点：

        快表是放在cache中，慢表是放在内存中。

        快表是一块小容量的相联存储器（Associative Memory），由高速缓存器组成，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。

        cache中的存储块的大小和主存块的大小是保持一致的，但是cache块的大小在不同的映射方式和读写方式下需要添加相应的标志位（tag）、一致性维护位、替换算法控制位，故实际上cache每一行的容量是大于主存块的。

预备知识

1、主存地址结构

主存地址 = 主存块号 + 块内地址
 
if(直接映射)                          //固定放
	主存地址 = 主存Tag  +  行号  + 块内地址
else if(组相联映射)						 //定位到某一组，任选组内一块进行映射:
	主存地址 = 主存Tag  +  组号  + 块内地址   //组间采用直接映射，组内的块之间采用全相联映射
else //全相联映射                           //随意放
	主存地址 =      主存块号     +  块内地址      //位数较多

注：此处的字块内地址指的是块内偏移量，利用字块内地址取出Cache块某个字 / 字节

   直接映射：主存块在Cache中的位置 即行号 = 主存块号 % Cache总块数 (从0开始)

   组相连映射：组相联映射，所属分组 = 主存块号%分组数 (从0开始)

   行号和组号，只是针对直接映射和组相联映射 主存块号的再分。做题时要看清题目给出的是主存地址还是主存块号。

2、Cache地址结构

主存地址 = 主存字块标记tag + Cache地址
 
if(直接映射)                             //直接定位到某一块
	Cache地址 = Cache行号 + 块内地址
else if(组相联映射)						//定位到某一组，任选组内一块进行映射:
	Cache地址 = Cache组号    + 块内地址   //组间采用直接映射，组内的块之间采用全相联映射
else //全相联映射                        //不定位，任选一个块
	Cache地址 =               块内地址   //位数较多

3、Cache总位数/总容量（一行的）

（容量角度） = 数据区+ 标记区

• （存储容量 + 标记阵列容量）
• 
• 标记阵列容量：标记位tag、有效位、脏位 、 替换算法控制位
• 注：标记项阵列(组相联)或标记项组(直接映射)也叫地址映射表。
• 标记阵列总容量 = 映射表总容量 = 标记项位数 * Cache块数
• 数据区 = Cache块大小(单位B) x 8
• 每个Cache块对应一个Cache标记项，用于标记相应Cache块的数据状态
•  匹配Cache块，就是查找阵列的标记项是否符合要求

4、Cache行的内容

五个构成（地址角度） = Tag + 有效位 + 替换信息位 + 脏位 + 块内数据位数

注：Cache行的内容与Cache地址是不一样的。

（1）*Tag(一定存在)：标志位

• 由物理地址位数 + Cache总行数 + Cache块大小 + Cache映射方式共同决定
• 直接映射：Tag = 物理地址位数 - 行号位数 - 块内地址位数（行号 = Cache总行数）
• 组相联映射：Tag = 物理地址位数 - 组号位数 - 块内地址位数（组号 = Cache总行数 / 几路组相联）
• 全相联映射：Tag = 物理地址位数 - 块内地址位数
   

 （2）*有效位(一定存在)：

• 判断该Cache行的数据是否有效。一定存在且为1bit。

 （3）替换信息位：（特定条件下才有）

• 由映射方式 + 替换算法 + Cache总行数决定
• 或叫替换算法位，用于标记替换cache哪一行会被换出，在cache替换策略中，当采用LRU和LFU替换算法时，这个控制位会作为被换出的依据。
• 直接映射：主存块唯一确定在Cache中的映射位置，故不需替换信息位 → 0 bit
• 全相联映射：RAND → 0 bit；FIFO、LRU → log2 行数 bit
• 组相联映射：RAND → 0 bit；FIFO、LRU → log2 路数 bit

 （4）脏位(修改位)：（特定条件下才有）

• 当该Cache行被替换时，判断是否被修改过，从而判断是否写回主存
• 也叫一致性维护位。
• 当cache写策略采用 写回法 （write - back）时，该位生效并且占 1 bit
• 当cache写策略采用 直接法 （write - throuugh）时，该位占 0 bit

 （5）块内数据：根据Cache块大小确定，例如每个Cache64B，且2 ^ 6 = 64 → 块内数据为6bit
这里的6bit的意思是，按照字节编址，6个bit的位数可以完整的把整个块的地址表达出来

 （6）隐含，不会额外占用标志位。实际上Cache的行号是地址映射表（相联存储器）的地址。

• 组号（组相联映射）：由 Cache总行数 + 几路（总行数 / 路数）组相联映射 决定
• 行号（直接映射）：由Cache总行数

5、 TLB - Cache - Page命中关系小结

• 前置知识——CPU根据虚地址访存流程

• ①访问虚地址读取虚页号 → 访问基址寄存器读取页表起始地址 → 拼接起始地址和虚页号得到页表地址 → 依据页表地址访问对应的页表项 → 根据装入位判断是否命中

  ②命中 → 对应的实页号 + 页内地址 = 实地址 → 执行Cache的映射操作

  ③未命中 → 利用 I/O 系统将页调入主存 → 执行第②步

• Cache未命中，与TLB、Page是否命中无关
  Cache命中，Page必然命中，TLB不一定命中
  TLB命中，Page必然命中
   Page命中，TLB不一定命中
   Page不命中，Cache不命中

• 分析助记

      TLB在Cache中，Page在主存中，TLB是Cache一个很小的副本
      Cache命中 ：意味着虚拟存储器访存流程进入了最后一步——执行Cache的映射操作，则所在页面必然已调入主存 → Page必然命中，而TLB是位于Cache内的Page小副本，故不一定命中
      Cache未命中：意味着Cache内没有与CPU请求页面相同的页，无法直接进行映射操作——但虚存访存流程前几步（查找页表地址、访问页表项、判断装入位）并不受影响 → 与TLB、Page无关
      TLB是Page的子集，根据数学集合关系可知：TLB命中是Page命中的充分不必要条件
      Page命中：意味着访存流程进行到 执行Cache映射操作 一步，但之后Cache映射能否命中与Page无关
      Page未命中：Page位于主存，Page未命中意味着主存内没有对应的页，Cache自然无法执行 主存→Cache 的映射操作，故Cache不命中

• Page、Cache命中示意图（以直接映射和页式虚拟存储器为例）

 详细图例助记

例题

1、各种容量计算

1、在高速缓存系统中，主存容量为12MB，Cache容量为400KB，则该存储系统的容量为（  ) 

 解答：

   Cache中存放的是主存信息的副本，我们认为存储系统的容量指的是主存容量。则为12MB。

2、某32位计算机的Cache容量为16KB,Cache行的大小为16B，若主存与Cache地址映像采用直接映像方式则主存地址为Ox1234E8F8的单元装入Cache的地址是(  ) 。

解答： 

  选项都为14位，隐藏了按字节编址。

  Cache行大小 16B → 字块内地址4bit

  行号 → Cache容量/块大小=16KB/16B =2^10

  则装入Cache的地址为低14位。选择C。

3、某存储系统中，主存容量是Cache容量的4096倍，Cache被分为64个块，当主存地址和Cache地址采用直接映像方式时，地址映射表的大小应为（    ）。(假设不考虑一致维护和替换算法位。)

解答：

映射表要做的事情：

      直接映射：主存地址 → Cache块

      位置是否有信息 → 有效位

      是否是所需信息 → 主存字块

      标记是否已修改 → 一致性维护

  Cache共64块(64行) → 映射表一共64行

  直接映射，主存容量是Cache容量的4096倍 → 高位主存块标志位有12位(2^12=4096)

  有效位1位

  所以，容量为64*(12+1)位。

4、有效容量为128KB的Cache，每块16字节，采用8路组相联。字节地址为1234567H的单元调入该Cache,则其Tag应为(  )。 

 解答：

  Cache块数 = 128KB/16B = 2^13

  组号 = Cache块数/8 =2^10  →10bit

  字块内地址 = 16B =2^4  → 4bit

  Tag → 7*4 - 10 - 4 = 14bit

  化为十六进制，从低位起每4位划分。

  即为 00.0100.1000.1101 → 048D H

5、有一主存—Cache层次的存储器，其主存容量为1MB，Cache容量为16KB，每字块有8个字，每字32位，采用直接地址映像方式，若主存地址为35301 H，且CPU访问Cache命中，则在Cache的第(    )(十进制表示)字块中(Cache起始字块为第0字块)。 

 解答：

  每个Cache块大小 = 8*32/8 =2^5 B → 字块内地址 5bit

  Cache行数 = 16KB/2^5 = 2^9 → 行号 9bit

  主存容量 → 主存地址位数 20bit

  标记 → 20 - 9 - 5 = 6bit

   蓝色即为行号。

6、假定主存地址位数为 32 位，按字节编址，主存和 cache 之间采用全相联映射方式，主存块大小为一个字，每字 32 位，采用回写（ Write Back ）方式和随机替换策略，则能存放 32K 字数据的 cache 的总容量至少应有多少位？

解答：

  Cache总容量 = 数据区 + 标记区

  数据区位数：32位（主存块大小 = Cache块/行 大小）

  标记区位数： 

  主存块大小32位 → 4B → 字块内位数 2bit

  tag位 → 32 - 字块内位数 =30bit

  有效位 → 1bit

  回写方式 → 脏位1bit

  32K行 x 一行Cache容量 = 32K x (数据区 + 标记区) = 32K x (32+30+1+1) = 32 x 64 K

  标记阵列容量：标记位tag、有效位、脏位 + 替换算法控制位

7、假设主存按字节编址，Cache共有64行，采用四路组相联映射方式，主存块大小为32字节，所有编号都从0开始，则第2593号存储单元所在主存块的Cache组号是？

解答：

  主存块大小32字节 → 字块内地址 5bit

  Cache共64行 → 四路组相联 → 64/4 =16组 组号4bit

  法一：

  2593号存储单元在 2593/32 = 81...1 ，所在的主存块号为 81 (从0开始编号)

  主存的某一字块按模16映像到Cache某组的任一字块中，即主存的第0，16，32…字块可以映像到Cache第0组2个字块的任一字块中，而2593号单元是位于第81块(从0开始)主存块中，因此将映射到Cache第1组2个字块的任一字块中。

  组号 = 81 % 16 = 6...1 ，则在第1组

   法二：

  2593对应的二进制地址为 101.0 001.0 0001

  则组号为1

 2、Cache缺失

1、假定CPU通过存储器总线读取数据的过程为：发送地址和读命令需1个时钟周期，存储器准备一个数据需8个时钟周期，总线上每传送1个数据需1个时钟周期。若主存和cache之间交换的主存块大小为64B，存取宽度和总线宽度都为4B，则cache的一次缺失损失至少为多少个时钟周期？

A.72      B.80      C.160      D.64

解答：

一次缺失损失需要从主存读出一个主存块（64B），每个总线事务读取4B，

因此，需要64B/4B=16个总线事务。

每个总线事务所用时间为1+8+1=10个时钟周期，总共需要160个时钟周期。

2、假定采用多模块交叉存储器组织方式，存储器芯片和总线支持突发传送，CPU通过存储器总线读取数据的过程为：发送首地址和读命令需1个时钟周期，存储器准备第一个数据需8个时钟周期（即CAS潜伏期=8)，随后每个时钟周期总线上传送1个数据，可连续传送8个数据（即突发长度=8)。若主存和cache之间交换的主存块大小为64B，存取宽度和总线宽度都为8B，则cache的一次缺失损失至少为（）个时钟周期？

A．17

B．20

C．33

D．65

解答：

一次缺失损失需要从主存读出一个主存块（64B），每个突发总线事务读取8x8=64B，

因此，需要64B/64B=1个总线事务。

每个总线事务所用时间为1+8+8=17个时钟周期，总共需要17个时钟周期。

3、408真题

（2009）

某计算机的Cache共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大小为32字节，按字节编制。主存129号单元所在主存块应装入到的Cache组号是
   A.0    B. 2    C. 4    D.6

答案：C
考点：Cache组相联映射方式

解析：主存按字节变址，第129号单元代表第129个字节。主存129单元，所在的块号为129/32=4(从0开始编号)；
由于Cache共有16块，采用2路组相联，因此共有8组，0，1，2，…，7。
主存的某一字块按模8映像到Cache某组的任一字块中，即主存的第0，8，16…字块可以映像到Cache第0组2个字块的任一字块中，而129号单元是位于第4块主存块中，因此将映射到Cache第4组2个字块的任一字块中。

（2009）

假设某计算机的存储系统由 Cache 和主存组成，某程序执行过程中访存 1000 次，其中访问 Cache 缺失（未命中）50 次，则 Cache 的命中率是
A  5%                   B.9.5%
C. 50%                 D.95%

答案：D
考点：Cache命中率的计算

（2010）

下列命令组合情况，一次访存过程中，不可能发生的是( )
A.TLB未命中，Cache未命中，Page未命中
B.TLB未命中，Cache命中，Page命中
C.TLB命中，Cache未命中，Page命中
D.TLB命中，Cache命中，Page未命中

答案：D
考点：TLB，Cache，Page的含义。
解析：TLB即为快表，快表只是慢表(Page)的小小副本，因此TLB命中，必然Page也命中，而当Page命中，TLB则未必命中，故D不可能发生；而Cache的命中与否与TLB、Page的命中与否并无必然联系。

（2012）

假设某计算机按字编址，Cache 有 4 个行，Cache 和主存之间交换的块为 1 个字。若 Cache 的内容初始为空，采用 2 路组相联映射方式和 LRU 替换算法。当访问的主存地址依次为 0,4,8,2,0,6,8,6,4,8 时，命中 Cache 的次数是
A. 1     B. 2         C. 3         D. 4

答案：C

4行表示有4个组，每块有一个字，每组有两块。

在组相联映像中，组间是直接映像，组内字块为全相联映像

命中后的字块就是被使用了的字块了

（2013）

某主存地址空间大小为 256  MB，按字节编址。虚拟地址空间大小为 4 GB，采用页式管理，页面大小为 4KB，TLB（快表）采用全相联映射，有 4 个页表项，内容如下表所示。则对虚拟地址 03FF F180H 进行虚实地址变换的结果是
A.  015 3180H     B. 003 5180H       C. TLB 缺失      D. 缺页

答案：A

虚地址有32位（4GB=2^32B），页面大小为 4KB（2^12B），那么虚页号有20位。页内地址有32-20=12位。

实地址有28位（256MB=2^28B），实地址由页框号和页内地址组成，其页内地址与虚地址的页内地址相同都为12位不变，则页框号有16位。

虚拟地址为03FF F180H，其中页号为03FFFH，页内地址为180H，根据题目中给出的页表项可知页标记为03FFFH所对应的页框号为0153H，页框号与页内地址之和即为物理地址015 3180 H。

若有效位为0，那么应该去选C。TLB 缺失。

（2014）

16. 采用指令Cache与数据Cache分离的主要目的是
A  减低Cache的缺失损失                       
B  提高Cache的命中率
C  减低CPU平均访问时间                     
D  减少指令流水线资源冲突

答案：D

解析：

Cache分为一级L1和二级L2。

L1集成在CPU中，称为片内Cache。

在L1中还分数据Cache和指令Cache。分别用来存放数据和执行这些数据的指令，两个Cache可以同时被CPU访问，减少了争用Cache所造成的冲突，提高了处理器效能。

（2015）

假定主存地址为32位，按字节编址，主存和Cache之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写( Write Back )方式，则能存放4K字数据的Cache的总容量的位数至少是(  )。

 解析：

    主存块大小4个字，每字32位 → 字块内地址 4x32/8 =2^4 →4b

    4K字数据的Cache → 4K/4=1K个Cache行 → 2^10 → 行号10b

    主存Tag → 32-10-4=18b

    回写方式 → 脏位1b

    有效位1b

    总容量=1K x (4x32+1+18+1) =148K

（2016）

有如下C语言程序段：

    for(int k = 0; k < 1000; k++)
    {
        a[k] = a[k]+32;
    }

若数组a以及变量k均为int型，int型数据占4B，数据Cache采用直接映射 方式，数据区大小是1KB，块大小是16B，该程序段执行前Cache为空，则该程序段执行过程中，访问数组a的Cache的缺失率是：
A. 1.25%
B. 2.5%
C. 12.5%
D. 25%

解析：

注意循环次数必为4的倍数，否则分别算。

注意写入和写出！

 （2017）

某C语言程序段如下：

for(i=0;i<=9;i++)

{       temp=1;
        for(j=0;j<=i;j++)temp *=a[j];
        sum+=temp;
}

下列关于数组a的访问局部性的描述中，正确的是（  ）。

A、时间局部性和空间局部性皆有

B、无时间局部性，有空间局部性

C、有时间局部性，无空间局部性

D、时间局部性和空间局部性皆无

解析：

时间局部性:一旦一条指令被执行了，则在不久的将来它可能再被执行

典型代表∶循环指令

空间局部性:一旦一个存储单元被访问，那么它附近的存储单元也很快被访问

典型代表:顺序指令、数组

答案：A

 （2021）

若计算机主存地址为32位，按字节编址，Cache 数据区大小为32KB，主存块大小为32B，采用直接映射方式和回写(Write Back)策略，则cache行的位数至少是( )。

A.275

B.274

C.258

D.257

 解析：

cache行的位数=主存区的标记位数+1位有效位+1位脏位+cache块的数据位

注：因为直接映射方式是分了很多主存区的，有主存区号，所以我们通过 主存区的标记位数，我们就能知道这个cache是属于主存的第几区。

对于直接映射方式而言

主存区的个数=主存大小/cache大小

而主存大小是2^32

所以主存区的标记位数是 2^32/32KB 17位

或者利用

17+1位有效位+1位脏位+256位(32B=32*8)=275,

所以本题选A
 

4、解答题

【例题】假设某个计算机的主存地址空间大小为256MB，按字节编址，其数据Cache有8个Cache行，行长为64B。

（1）若不考虑用于Cache的一致维护位和替换算法控制位，并且采用直接映射方式，则该数据Cache的总容量为多少？

（2）若该Cache采用直接映射方式，则主存地址为3200（十进制）的主存块对应的Cache行号是多少？采用二路组相联映射时又是多少？

（3）以直接映射为例，简述访存过程（设访存的地址为 0123456 H）

解答：

（1）Cache总容量 = 标记阵列容量 + 存储容量

    标记区 = 有效位 + 替换算法控制位 + 标记位Tag + 脏位(一致性维护位)

    直接映射主存地址结构：Tag + 行号 + 块内地址

    块内地址：行长64B → 2^6 → 6bit

    行号：8行 → 2^3 → 3bit

    Tag：主存地址256MB=2^28 → 28-3-6=19bit

    则一行Cache容量：64x8(数据区存储容量)+19(Tag)+1(有效位) = 532位

    Cache总容量 = 8行 x 532位 = 4256位

（2）

若为直接映射：

    法一：利用主存地址二进制，由（1）可知主存地址结构。

    3200化为二进制为：110 010 000000

    则行号为 010 → 2号

    法二：计算主存块号，对应Cache行数。主存块大小=Cache块大小

    主存块号：3200/64B = 50 → 主存块号50 (从0开始编号)

    行号：50%8=6...2 → 行号为2

    主存的某一字块按模8映像到Cache某组的任一字块中，即主存的第0，8，16…字块可以映像到Cache第0组2个字块的任一字块中，而3200号单元是位于第50块(从0开始)主存块中，因此将映射到Cache第2组的2个字块任一字块中。

若为二路组相联映射：

    法一：利用主存地址二进制

    主存地址结构：Tag+组号+块内地址

    组号所占位数 → 行数/路数 = 8/2 =4组 → 2bit

    由1100 10 000000 → 组号为2 → 对应的Cache行号4或5(从0开始编号)

     法二：计算主存块号，对应Cache组号。主存块大小=Cache块大小

     组号：主存块号%组数 → 主存块号50%4=2

 （3）

直接映射主存地址结构：Tag + 行号 + 块内地址

0000000100100011010 001 010110

① 首先根据块号，对比Cache(即001号Cache行)中对应的主存标记位 → 再看Cache行的有效位是否为1

→ 是1则访问命中 →  读出Cache行对应的单元送入CPU →  完成

→ 不是1则不命中 →  访问主存将数据取出并送往CPU和Cache的对应块中，把主存的最高19位存入001行的Tag，并将有效位置1

【例题】有一Cache系统，字长为16位，主存容量为16字×256块，Cache的容量为16字×8块。采用全相联映射，求:

1）主存和Cache的容量各为多少字节?主存和Cache的字地址各为多少位?

2）如果原先已经依次装入了5块信息，问字地址为338H所在的主存块将装入Cache块的块号及在Cache中的字地址是多少位?

3）如果块表中地址为1的行中标记着36H的主存块号标志，Cache块号标志为5H，则在CPU送来主存的字地址为368H时是否命中?如果命中，此时Cache的字地址为多少?

 解析：

1）

    一个字为16/8=2字节

    → 主存容量：16×256×2B=8192B=8KB

    → Cache容量:16×8×2B=256B

    按字寻址，主存可寻址单元个数为 16×256=4K个 → 主存地址：12位

    Cache可寻址单元个数为 16×8=128个 →  Cache地址：7位

2） Cache块号：101 → 完整Cache地址：101 1000B

 3）Cache地址 = Cache块号+块内地址 → 完整Cache地址：101 1000B =58H

【2010统考真题】

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

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

1）若不考虑用于Cache一致性维护和替换算法的控制位，则数据Cache的总容量为多少？

2）数组元素a[0][31]和a[1][1]各自所在的主存块对应的Cache行号分别是多少（Cache行号从0开始）？

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

 1）

 2）

解法1：看地址位

每个数据32位，即4B，按字节编址，行优先存放，故a[0][0]地址为320，a[0][1]地址为324...

a[0][31]地址为320+31×4=444，a[1][1]地址为320+1×256×4+1×4=1348

解法2：计算块号

每个int型数据4B占用四个连续存储单元

a[0][31]对应的主存块号 → 444/64=6 → 第6块主存块(从0开始)

对应的行号 → 6%8=5

a[0][32]对应的主存块号 → 1348/64=21 → 第21块主存块(从0开始)

对应的行号 → 21%8=5

 3）

 每个int型数据4B，一个主存块存放16个数据

为什么出现重复相互覆盖？

Cache可存放的数据量为64B×8=512B，数组a一行的大小为1KB，正好是Cache容量的2倍(整数倍)，故不同行的同一列数组元素使用的是同一个cache单元 。

 由于从Cache读数据比从主存读数据快很多，所以程序A的执行比程序B快得多。

 解析：

1）

虚拟地址：虚页号+页内地址    物理地址：实页号+页内地址

组相联映射主存地址结构：主存Tag+组地址+字块内地址

D：页内地址 8KB=2^13 → 13b

A：虚页号 32-13=19 → 19b

C：实页号 24-13=11 → 11b

B：B中存放虚页号，表示该TLB项对应哪个虚页的页表项=A → 19b

G：字块内地址 64B=2^6 → 6b

F：组号 组数/路数=(64KB/64B)/2=2^9 → 9b

E：主存Tag = 24-9-6 =9 → 9b

H：主存Tag = E → 9b

注：F的箭头含义是地址，而E的箭头指的是值的概念。

 2）注意题目中给的是块号：主存Tag+组号

3）

Cache存放主存中比较活跃的块，Cache缺失说明该主存块还未调入Cache，访问主存调入该块即可。

缺页说明该页面还未调入主存，需要从辅存(主要是磁盘)中调入，即需要访问辅存。

而访问辅存（例如磁盘，机械式串行）耗时远大于访问主存（电信号选中单元），故缺页处理的时间开销更大。

4）

直写策略:修改内容时同时写快速存储器和慢速存储器。

回写策略:修改内容时只写快速存储器，调出该块或者该页面时再写慢速存储器。

【2020统考真题】

（10分）假定主存地址为32位，按字节编址，指令Cache 和数据Cache 与主存之间均采用8路组相联映射方式，直写（Write Through）写策略和LRU替换算法，主存块大小为64B，数据区容量各为32KB。开始时Cache 均为空。请回答下列问题。
（1）Cache 每一行中标记（Tag）、LRU 位各占几位?是否有修改位?
（2）有如下C语言程序段：
        for (k = 0; k<1024; k++)
        s[k] = 2* s[k];
若数组s及其变量k均为 int 型，int 型数据占4B，变量k分配在寄存器中，数组s在主存中的起始地址为0080 00C0H，则该程序段执行过程中，访问数组s的数据 Cache 缺失次数为多少?
（3）若CPU最先开始的访问操作是读取主存单元0001003H中的指令，简要说明从Cache 中访问该指令的过程，包括 Cache 缺失处理过程。 

 解析：

1）组相联映射主存地址结构：Tag+组号+块内地址

   块内地址：64B → 2^6B →  6b

   组号：组数/路数=(32KB/64B)/8 =2^6 → 6b

   则Tag = 32-6-6=20b

   LRU算法：log2(路数) = log2(8) = 3b

   LRU替换算法→当分组内8个块已满时，淘汰最近最久未使用的Cache块

   修改位(脏位)：直写法，写Cache时同时写主存，不会出现Cache和主存不一致的情况，则不需要。

2）

3）

部分参考于

王道

【计组】存储器_AmosTian的博客-CSDN博客

https://www.jianshu.com/p/89ec526c3a4c

2021年计算机408真题讲解_13422900的技术博客_51CTO博客

计算机组成原理——主存储器考研题 - 王陸 - 博客园

【计组原理学习小结】虚拟存储器、Cache访存过程中，TLB - Cache - Page的命中关系_流浪的五花肉的博客-CSDN博客