存储系统基本概念

• 大端法为高位在低地址，小端法为低位在低地址
• 小端模式 ：强制转换数据不需要调整字节内容 大端模式 ：符号位的判定固定为第一个字节，容易判断正负。

存储器的层次结构

高速缓存存储器和主存可被CPU直接读写，辅存中的数据必须先被调入主存才能被CPU访问。

主存——辅存：实现虚拟存储系统，解决了主存容量不够的问题

cache——主存：解决了主存和CPU速度不匹配的问题

存储器的分类

• 按层次结构分类：高速缓存储器(cache)、主存、辅存
• 按存储介质分类：半导体存储器、磁表面存储器、光存储器
• 按存取方式分类：
  • 随机存取存储器（RAM）：按地址访问数据，读写任何一个存储单元所需时间都相同，与存储单元所在的物理位置无关。比如：内存条。
  • 顺序存取存储器（SAM）：按地址访问数据，读写一个存储单元所需时间取决于存储单元所在的物理位置。比如：磁带。
  • 直接存取存储器（DAM）：按地址访问数据，既有随机存取特性，也有顺序存取特性。先直接选取信息所在区域，然后按顺序方式存取。比如：机械硬盘。
    • 串行访问存储器：读写某个存储单元所需时间与存储单元的物理位置有关
  • 相联存储器（CAM）：按内容检索到存储位置进行读写的存储器。比如：快表。
• 按信息的可修改性分类：读写存储器、只读存储器（ROM）
• 按信息的可保存性分类：
  • 断电后信息能否保存：易失性存储器（主存、cache)、非易失性存储器（磁盘、光盘）
  • 信息读出后原有信息是否被破坏：破坏性读出（DRAM读出数据后要重写）、非破坏性读出（SRAM、磁盘、光盘）

存储器的性能指标

• 存储容量：存储字数(存储单元个数)×存储字长
• 单位成本：每位价格=总成本/总容量
• 存储速度：数据传输率=存储字长/存储周期
  • 存储周期：又叫读写周期或访问周期。是存储器进行一次完整的读写操作所需的时间，即两次访问存储器操作所需的最小时间间隔。
  • 存储周期 = 存取时间(Ta) + 恢复时间(Tm)
  • 存取时间：从启动存取到存取完成的时间
  • 恢复时间：从存取完成到下次存取的恢复时间
  • 主存带宽(Bm)：主存带宽又称数据传输率，表示每秒从主存进出信息的最大数量。

主存储器的基本组成

基本元件

• MOS管，作为通电”开关“
• 电容，用来存储电荷，表示二进制0/1

存储芯片的结构

• 译码驱动电路：译码器将地址信号转化成自选通线的高低电平
• 存储矩阵(存储体)：由多个存储单元构成，每个存储单元由多个存储元构成
• 存储元：由MOS管和电容构成
• 读写电路：每次读/写一个存储字
• 地址线、数据线、片选线、读写控制线(1/2根)

寻址

• 现代计算机通常按字节编址，即一个地址对应一个字节

• 按字节寻找、按字寻址、按半字寻址、按双字寻址

SRAM和DRAM

DRAM刷新

• 分散刷新、集中刷新、异步刷新
• 由存储器独立完成，不需要CPU控制

DRAM分两次送地址

• 可使地址线、地址引脚减半

现在的主存常采用SDRAM

ROM

• MROM：掩膜式只读存储器，存储内容在出厂时写好，无法修改

• PROM：一次可编程只读存储器，用户用编程器一次性写入，之后无法修改

• EPROM：可擦除可编程只读存储器，修改次数有限，写入时间很长

  • UVEPROM：紫外线擦除
  • EEPROM：电擦除

• FM：闪存存储器，如U盘等，写入速度比读出速度慢，因为要先擦除再写

• SSD：固态硬盘，由FM和控制单元构成

ROM虽然名字是只读存储器，但很多ROM也可以”写“

ROM是非易失性的 ，很多ROM也有”随机存取“的特性，常用作辅存，如硬盘等；RAM是易失性的，常用作Cache、主存。

CPU与主存的连接

位扩展-增加主存的存储字长

上图实现了用8块8K×1位的存储芯片扩展为1块8K×8位的主存。地址总线一次可访问8块芯片，数据总线也一次可读/写出8位数据。

位扩展法：只加大字长（扩展数据线）

连接时：每个芯片具有相同的地址线，不同的数据线

字扩展-增加主存的存储字数

上图实现了用一块2-4译码器和4块8K×8位的存储芯片扩展为1块32K×8位的主存。片内地址A0-A12控制访问芯片中哪块存储单元，片选地址A13-A14控制访问哪块芯片。

图中芯片间连接线为片内地址A0-A12，为了图例美观便直接让芯片相连接，实际并非是在芯片间传输地址数据。

字扩展法:仅在字向扩充，而位数不变.需由片选信号来区分各片地址。

芯片的地址总线和数据总线公用，控制总线中R/W公用，芯片使能端CS(chip select)不能公用，它由地址总线的高位段译码来决定片选信号。 R/W——/WE(write enable)，译码器输出端Y0-Y3——芯片使能端CS(chip select)， /MREQ(允许访存， 低电平有效)——译码器使能端。R/W(高电平为读命令，低电平为写命令)。

连接时：每个芯片具有不同的地址线(片选信号不同)，相同的数据线。

字位扩展-增加主存容量

上图实现了将8块16K×4位的存储芯片分为4组，每组2块16K×4位芯片，实现位扩展为16K×8位；将4组用一块2-4译码器连接，实现字扩展为1块64K×8位的主存。片内地址A0-A13控制访问芯片中哪块存储单元，片选地址A14-A15控制访问哪块芯片。

在字向和位向同时进行扩展。字位扩展可以看成先位扩展，再字扩展。

连接时：每个芯片具有不同的地址线，不同的数据线。

组内是位扩展，地址线相同，数据线不同；组间是字扩展，地址线不同(片选信号不同)，数据线相同

补充:3-8译码器

CPU先送出地址信号，待电信号稳定后，才送出存储器请求信号控制译码器使能端，使片选信号开始生效。

并行存储器

存取周期 T = 存取时间 r + 恢复时间

双端口RAM

支持两个CPU同时访问RAM

可同时读/写不同的存储单元；可同时读同一个存储单元；不能同时写（或者一读一写）同一个单元

若发生”冲突“，则发出”BUSY“信号，其中一个CPU的访问端口暂时关闭

多模块交叉存储器

单体多字存储器

• 每次并行读出m个连续的字
• 总线宽度也要扩展为m个字

多体并行存储器

• 高位交叉编址
  • 理论上多个存储体可以被并行访问，但是由于通常都是连续访问，因此实际效果相当于单纯的扩容，并没有提高速度。
• 低位交叉编址
  • 当存储模块数 m ≥ T/r 时，可使流水线不间断
  • 每个存储周期可读写地址连续的m个字
  • 连续取n个存储字耗时=T+(n-1)r
  • 微观上，m个模块被串行访问；宏观上，每个存取周期内所有模块被并行访问

高速缓存存储器Cache

• 双端口RAM、多模块存储器提高了存储器的工作速度，但优化后速度与CPU差距依然很大

• cache工作原理：将主存中某些块复制到cache中，缓和CPU与主存之间的速度矛盾

• 局部性原理

  • 时间局部性：现在访问的地址，不久之后也很有可能被再次访问
  • 空间局部性：现在访问的地址，其附近的地址也很有可能即将被访问

• 性能分析

  • 命中率H：CPU欲访问的信息已在Cache中的比率
  • 缺失率(未命中率)M=1-H
  • Cache——主存 系统的平均访问时间t为
    • 设t_b为访问一次Cache所需时间，t_m为访问一次主存所需时间
    • 先访问Cache，若Cache未命中再访问主存：t=Ht_c+(1-H)(t_c+t_m)
    • 同时访问Cache和主存，若Cache命中则立即停止访问主存：t=Ht_c+(1-H)(t_m)

• 其他概念

  

  • 主存与Cache之间以”块“为单位进行数据交换，多个存储单元组成一个块
  • 主存的”块“又叫”页/页框/页面“；Cache的”块“又叫”行“
  • 主存地址可拆分为(主存块号，块内地址)的形式
  • 每次被访问的主存块一定会被立即调入Cache

Cache-主存映射方式

cache组成：有效位(0/1)+标记+整块数据

其中“标记”用于指明对应的主存块。不同的映射方式“标记”的位数不同。

全相联映射

主存块可以放到cache的任意位置

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

优点：cache存储空间利用充分，命中率高

缺点：查找“标记”最慢，有可能需要对比所有行的标记

直接映射

主存块只能放到特定的某个cache行，行号=主存块号%cache总行数

主存地址结构：标记+行号(主存块号后几位)+块内地址

优点：对于任一主存地址，只需按主存地址后几位确定cache行，然后对比一个“标记”，即可确定cache是否命中，速度最快。

缺点：cache存储空间利用不充分，命中率低

组相联映射

主存块可以放到特定分组中的任意位置，所属组号=主存块号%总组数

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

优点：另外两种方式的折中，综合效果较好

n路组相联映射——每n个cache行为一组

Cache替换算法

随机算法（RAND）

• 随便选一个主存块替换
• 过于自由，效果很差

先进先出算法(FIFO)

• 优先替换最先被调入cache的主存块
• 未遵循局部性原理，是从主存全局考虑的，效果差

近期最少使用算法（LRU）

• 将最久没有被访问过的主存块替换。每个Cache行设置一个“计数器”，用于记录多久没被访问
• 基于“局部性原理”，近期被访问过的主存块。在不久的将来也很有可能被再次访问，因此，淘汰最久没被访问过的块是合理的。
• LRU算法实际运行效果好，cache命中率高
• 硬件实现
  • 命中时，所命中行的计数器清零，比其低的计数器加1，其余不变；
  • 未命中且还有空闲行时，新装入的行的计数器置0，其余非空闲行全加1；
  • 未命中且无空闲行时，计数器最大的行的信息块被淘汰，新装行的块的计数器置0，其余全加1。
  • 若cache块的总数为2ⁿ，则计数器只需n位

最不经常使用算法（LFU）

• 将被访问次数最少的主存块替换。每个cache行设置一个“计数器”，用于记录被访问过多少次
• 曾经被经常访问的主存块在未来不一定会用到，LFU实际运行效果不好

Cache写策略

写命中

• 全写法(写直通法)：当CPU对Cache写命中时，必须把数据同时写入Cache和主存，一般使用写缓冲(write buffer)
• 写回法：当CPU对Cache写命中时，只修改Cache的内容，而不立即写入主存，只有当此块被换出时才写回主存

写不命中

• 写分配法：当CPU对Cache写不命中时，把主存中的块调入Cache，在Cache中修改。通常搭配写回法使用。
• 非写分配法：当CPU对Cache写不命中时只写入主存，不调入Cache。通常搭配全写法使用。

多级Cache

• 现代计算机通常采用多级Cache结构，各级Cache间常采用“全写法+非写分配法”，Cache和主存间常采用“写回法+写分配法”

页式存储器

• 页式存储系统：一个程序在逻辑上被分为若干个大小相等的“页面”，“页面”大小与“块”的大小相同。每个页面可以离散地放入不同地主存块中。
  • 操作系统将程序分“页”
• 逻辑地址（虚地址）：程序员视角看到的地址，也就是机器指令中的地址码（要操作的数据的逻辑地址）
  • 逻辑地址=逻辑页号+页内地址

若某程序为4KB，主存中块大小为1KB，则操作系统将程序分为4页。若要访问程序中某数据，则机器指令中地址码的前两位表示逻辑页号即数据在哪一页，后面的表示页内地址。

• 物理地址（实地址）：数据实际在主存中的地址
  • 物理地址=主存块号+块内地址
• CPU访存过程：程序的逻辑地址——主存的物理地址
• CPU执行的机器指令中使用的是“逻辑地址”，因此需要通过“页表”将逻辑地址转为物理地址。
• 页表的作用：记录了每个逻辑页面存放在哪个主存块中

• 页表基地址是页表在主存中的物理地址，每次查页面都相当于一次访问主存，主存是DRAM访问速度不够快。因此增加快表，快表是一种“相连存储器”，可以按内容寻访。
• 快表与Cache区别：快表中存储的是页表项的副本；Cache中存储的是主存块的副本

虚拟存储器

主存——辅存系统，主存中只调用辅存中一部分数据。实际并非是主存容量很大，而是利用主存——辅存系统解决了主存容量问题。所以叫做虚拟存储器

页式虚拟存储器：将程序拆分成大小相等的页面

段式虚拟存储器：按照功能模块拆分程序

段页式虚拟存储器：先分段 再分页，以页为基本传送单位，一个程序对应一个段表；一个段对应一个页表

习题

1.某计算机字长为32位，按字节编址，采用小端 (Little Endian)方式存放数据。假定有一个double型变量(8个字节)，其机器数表示1122 3344 5566 7788H，存放在0000 8040H开始的连续存储单元中，则存储单元0000 8046H中存放的是()

A.22H

B.33H

C.66H

D.77H

解析：

按字节编址，所以存储字长为8位。小端存储：低位在低地址，因为一个十六进制数为4位，存储字长为8位，一个存储单元存两个十六进制数，所以从后往前数第13个和第14个十六进制数，就是第7个存储单元0000 8046H中存储的数据。

所以答案为A

2.某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int型和short型长度分别为32位和16位，并且数据按边界对齐存储，其C语言程序段如下：

struct{

​ int a;

​ char b;

​ short c;

}record;

record.a=273;

若record变量的首地址为0xc008，则地址0xc008中的内容及record.c中的地址是（）

A. 0x00, 0xc00d

B. 0x00, 0xc00e

C. 0x11, 0xc00d

D. 0x11, 0xc00e

解析：

273=0001 0001 0001=111H，小端存储，所以地址0Xc008中内容为11H

按字节编址，存储字长为8位。a变量为int型，长度为32位即4个字节，占4个存储单元；b变量为char型，长度为1个字节，占1个存储单元；**边界对齐，即对于存放某长度为m字节的数据，存放地址需在m字节的整数倍存放，结构体整体的大小是最大成员长度的整数倍。**本题结构体最大成员为4字节

所以答案为D

3.存储容量：32M×16位需要多少数据线？多少地址线？

​ 2G×32位需要多少数据线？多少地址线？

解析：

32M×16b=2²⁵×2⁴，所以需要25条地址线，4条数据线

2G×32b=2³¹×2⁵，所以需要31条地址线，5条数据线

4.说明1M×1位DRAM片子的刷新方法，刷新周期定为8ms，读写周期为定为1 µs。(1M芯片排列为1024×1024)

解析：

如果行地址为A9~A0，一行上有1024个存储元，在8ms内必须完成1024个行的刷新。

刷新方式可采用集中刷新方式 ，用8000-1024=6976µs进行读写周期，用1024µs进行刷新。

刷新方式还可采用异步刷新方式：8000µs/1024=7.8125µs，按7.8µs刷新一行的异步刷新方式

5.下列有关RAM和ROM得叙述中正确的是（）

I. RAM是易失性存储器，ROM是非易失性存储器

II. RAM和ROM都是采用随机存取方式进行信息访问

III. RAM和ROM都可用做Cache

IV . RAM和ROM都需要进行刷新

A. 仅I和II

B. 仅II和III

C. 仅I ，II， III

D. 仅II，III，IV

解析：

易失性：断电后信息是否保存，I对；RAM和ROM都是采用随机存取方式进行信息访问 ，II对；ROM是只读存储器不用作cache，III错；SRAM不是破坏性读出，不需要刷新，IV错

所以答案为A

6.下列各类存储器中，不采用随机存取方式的是（）

A. EPROM

B. CDROM

C. DRAM

D. SRAM

解析：

EPROM是可擦除可编程只读存储器，采用随机存取方式；CDROM是光盘只读存储器，不是随机存取方式；RAM是随机存取存储器

所以答案为B

7.下列关于闪存（flash memory）的叙述中，错误的是（）

A. 信息可读可写，并且读、写的速度一样

B. 存储元由MOS管组成，是一种半导体存储器

C. 掉电后信息不丢失，是一种非易失性存储器

D. 采用随机访问方式，可替代计算机的外部存储器

解析：

闪存要先擦除才能写，所以写比读慢，A错

所以答案为A

8.用2114（1K×4）的存储芯片组成8K×8存储器，设计步骤如下（需要进行字扩展及位扩展）

解析：

1.确定所需该芯片的个数：8K×8/(1K×4)=16(片)

2.字位扩展，确定地址线，数据线个数：位由4扩展到8，一组2个芯片，共8组，数据线8根(D0-D7)；单个芯片字长1K，片内地址线10根(A0-A9)；8组，片选地址线3根(A10-A12)。总计16根地址线，8根数据线。

3.连线

9.CPU的地址总线16根(A15—A0，A0为低位)，双向数据总线8根(D7— D0)，控制总线中与主存有关的信号有/MREQ(允许访存， 低电平有效)， R/W(高电平为读命令，低电平为写命令)。主存地址空间分配如下：0—8191 为系统程序区，由只读存储芯片组成；8192—32767为用户程序区；最后(最大地址)2K地址空间为系统程序工作区。上述地址为十进制，按字节编址。

现有如下存储器芯片：

EPROM：8K×8位(控制端仅有/CS);

SRAM：16K×1位，2K×8位，4K×8位，8K×8位.

问1： 请从上述芯片中选择适当芯片设计该计算机主存储器，

问2 ： 画出主存储器逻辑框图，注意画出选片逻辑(可选用门电路及3∶8译码器74LS138)与CPU的连接，说明选哪些存储器芯片，选多少片。

解析：

(1)

8192/1024=8K，因为是系统程序区，所以选1片8K的EPROM；(32767-8192)/1024=24K，因为是用户程序区，所以选3片8K的SRAM；因为是2K的系统程序工作区，所以选1片2K的SRAM

(2)

CPU提供地址线16根，数据线8根，控制总线2根。

此题属于位扩展。数据线8根(D0-D7)；控制总线2根(/MREQ，R/W)；最大单个芯片为8K，片内地址线13根(A0-A12)；片选地址线3根(A13-A15)

10.设CPU有16根地址线，8根数据线，并用MREQ作为访存控制信号（低电平有效），用WR作为读写控制信号（高电平为读、低电平为写）。现有下列存储芯片：

1K×4位RAM、 4K×8位RAM、8K×8位RAM、2K×8位ROM、4K×8位 ROM、8K×8位ROM

74138译码器和各种门电路。

画出 CPU与存储器的连接图，要求如下：

①主存地址空间分配： 6000H～67FFH为系统程序区。 6800H～6BFFH为用户程序区。

②合理选用上述存储芯片，说明各选几片。

③详细画出存储芯片的片选逻辑图

解析：

67FFH-6000H+1=7FFH=0111 1111 1111+1=1000 0000 0000=2¹¹=2K，因为是系统程序区，所以选1个2K的ROM

6BFFH-6800H+1=2¹⁰，因为是用户程序区，所以选2个1K×4位的RAM为一组将位扩展位8位

数据线8根(D0-D7)；最大单个芯片是2K，片内地址线11根(A0-A10)；因为只有3-8译码器，所以片选地址线3根(A11-A13)；使能端3根(A14-A15、MREQ)；读写控制线1根(WR)

11.某计算机字长32位，存储容量256MB，若按字编址，它的寻址范围是（）

A. 1M

B. 512KB

C. 64M

D. 256KB

解析：

按字编址，字长32位，存储容量256MB，则存储字数为256MB/32b=2²⁸B/2²B=2²⁶B=64MB

所以答案为C

12.某计算机字长32位，存储容量4GB，若按双字编址，它的寻址范围是（）

A. 4G

B. 0.5G

C. 8G

D. 2G

解析：

按双字编址，单字长32位，双字64位，则存储字数为4GB/64b=2³²B/8B=2²⁹B=0.5GB

所以答案为B

13.某DRAM芯片，其存储容量为512K×8bit，则该芯片的地址线和数据线数目为（）

A. 8,512

B. 512,8

C. 18,8

D. 19,8

解析：

512K=2¹⁹,19根地址线

所以答案为D

14.假定用若干个2K×4位芯片组成一个8K×8为存储器,则0B1FH所在芯片的最小地址是（）

A. 0000H

B. 0600H

C. 0700H

D. 0800H

解析：

位扩展4位到8位，每组2个2K×4位；字扩展2K到8K，4组；2位片选信号，11位片内信号。

0B1FH=0000 1011 0001 1111，片选信号为01，即第二组芯片，每组芯片寻址范围为2K=2¹¹，所以第二组芯片寻址范围最小为2¹¹=0000 1000 0000 0000 = 0800H

所以答案为D

15.某一RAM芯片，其容量为128K×16位。除电源和接地端外，该芯片引出线最小数目为 ()

A.33

B.35

C.17

D.12

解析：

128K=2¹⁷，片内地址17根，16位，数据线16根

所以答案为A

16.设存储器容量为32字，字长64位，模块数m=4，分别用顺序方式和交叉方式进行组织。存储周期T=200ns，数据总线宽度为64位，总线传送周期τ=50ns。问顺序存储器和交叉存储器的带宽各是多少?

解析：

模块数为4，假设访问4个字，字长64位，共256b

1ns=10^-9s

顺序存储器所需时间：4T=800ns=8×10^-7s，带宽：256b/(8×10^-7s)=3.2×10⁸b/s

交叉存储器所需时间：T+(4-1)τ=350ns=3.5×10^-7s，带宽：256b/(3.5×10^-7s)≈7.3×10⁸b/s

17.CPU执行一段程序时，cache完成存取的次数为1900次，主存完成存取的次数为100次，已知cache存取周期为50ns， 主存存取周期为250ns，求cache/主存系统的效率和平均访问时间

解析：

cache命中率h=1900/(1900+100)=0.95

cache/主存系统的平均访问时间t=0.95×50ns+0.05×250ns=60ns

cache/主存系统的效率e=50ns/60ns≈0.833

18.设有一个cache的容量为2k字，每行为16字，求：

1.该cache可容纳多少个行?

2.如果主存容量为256k字，则有多少个块?

3.主存的地址有多少位？Cache的地址有多少位？

4.在直接映射方式下，主存中的第i块映射到Cache中的哪一个行中？

5.进行直接地址映射时，存储器的地址分成哪几段？各段分别有多少位?

解析：

(1)2K/16=2⁷，该cache可容纳2⁷个行

(2)256K/16=2¹⁴个块

(3)256K=2¹⁸，主存地址18位；2K=2¹¹，cache地址11位

(4)i%2⁷，

(5)由(2)知主存块数2¹⁴个块，所以块号14位；由(1)知cache行数2⁷个行，所以块号可细分为前7位是标记号，后7位是行号；主存的地址共256K=2¹⁸，即18位，所以块内地址4位。综上，存储器地址可分成3段：标记7位，行号7位，块内地址4位。

19.一个容量为4个行的全相联cache，设访问的主存地址块号序列为2，11，2，9，7，6，4，3在先进先出替换方式下， cache中的内容变化情况为

解析：

20.一个容量为4个块的全相联cache，设访问的主存地址块号序列为2， 11，2，9，7，6，4，3在近期最少使用法替换方式下，cache中的内容变化情况为：

解析：

21.设主存容量512KB，Cache容量4KB，每个块16个字， 字长32位。

（1）Cache地址多少位？Cache共有多少行？

（2）主存地址多少位？可容纳多少个块？

（3）在直接地址映射方式下，主存的第几个块映射到Cache中的第5块？

（4）画出直接映射方式下主存地址地段中各段的位数？

解析：

(1)cache容量4K×8位，4K=2¹²cache地址12位；4KB/(16×32b)=2⁶，共2⁶个行

(2)主存容量512K×8位，512K=2¹⁹，主存地址19位；512KB/(16×32b)=2¹³，共2¹³个块

(3)i%2⁶=5，则i=n64+5(n=0,1,2,3,……)

(4)块号13位(标号7位，行号6位)，块内地址6位

22.设主存容量512K×16位，Cache容量4096×16位，块长4个16位的字，访存地址为字地址。

（1）直接映射方式下，设计主存的地址格式。

（2）全相联映射方式下，设计主存的地址格式。

（3）二路组相联映射方式下，设计主存的地址格式。

（4）四路组相联映射方式下，设计主存的地址格式

解析：

(1)512K=2¹⁹，主存地址共19位；512K×16b/(4×16b)=2¹⁷，主存可容纳2¹⁷个块，块号17位；4096×16b/(4×16b)=2¹⁰，cache共有2¹⁰个行；标号7位，行号10位，块内地址2位

(2)由(1)知，块号17位，块内地址2位

(3)由(1)知，cache共10行，2行1组，可分为2⁹个组；标号8位，组号9位，块内地址2位

(4)由(1)知，cache共10行，4行1组，可分为2⁸个组；标号9位，组号8位，块内地址2位

23.某计算机Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在的主存块应装入到Cache的组号是：()

A、0

B、2

C、4

D、6

解析：

16/2=8，8个组。每个主存块大小为32字节，按字节编址，则1块32个存储单元；128/32=4，所以主存129号存储单元在第5块；5%8=5，所以应装入第五组，也就是cache #4

所以答案为C

24.假设计算机的存储系统由Cache和主存构成。某执行过程访存1000次，其中Cache访问缺失（未命中）50次，则 Cache的命中率是（）

A. 5%

B. 9.5%

C. 50%

D. 95%

解析：

1-50/1000=0.95

所以答案为D

25.假设某计算机按字编址，Cache有四个行， Cache与主存之间交换的块为1个存储字。若Cache的内容初始为空，采用2路组相联的映射方式和LRU替换策略。访问的主存地址是0,4,8,2,0,6,8,6,4,8时，命中Cache的次数是（）

A. 1

B. 2

C. 3

D. 4

解析：

2路组相联，#0#1一组，#2#3一组，LRU近期最少使用算法

所以答案为A

补充：本题为 2012年考研题，标准答案给的C。因为当时教材中组相联映射方法与如今有些许区别，本题我以如今统一的组相联映射方法作答。

相关链接：

关于该问题的讨论1

关于该问题的讨论2

关于该问题的讨论3

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

A．146k

B．147K

C．148K

D．158K

解析：

主存容量2³²×8位，主存地址共32位；2³²×8b/4×32b=2²⁸，块号28位；4K字/4字=2¹⁰，cache共2¹⁰行，标记18位，行号10位；

cache总容量=存储容量+标记阵列容量，标记阵列容量包括4种标记：标记位、有效位、一致性维护位/脏位、替换算法控制位。有效位和标记位是一定有的，而一致性维护位（脏位）和替换算法控制位的取舍标准是看题眼，题目中，明确说明了采用写回法，则一定包含一致性维护位，而关于替换算法的词眼题目中未提及，所以不予考虑。

cache存储容量：4K字=4K×32b=2⁷Kb

每行标记阵列：标记18位，有效位1位，脏位1位，共20位

cache共2¹⁰行，所以标记阵列容量为：2¹⁰×20=20Kb

故cache总容量=2⁷Kb+20Kb=148Kb

所以答案为C

27.有如下C语言程序段：

for (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%

解析：

a[k]的访问步骤是：先访问cache，cache缺失，之后从主存中取出一个块调入cache，由于数组在内存中是连续存放，所以这个块中的后几个数据都是命中的。本题中一个int数据占4B，一个块大小是16B，这说明一个块中有4个int数据，关键是后面还有一次写操作，这说明一次循环要八次访问cache，其中只有第一次是缺失的，后面七次都是命中的，所以缺失率是1/8=12.5%；

所以答案为C

28.假定主存地址位数为32位，按字节编址，主存和cache之间采用直接映射，主存块大小为一个字，每字32位，写操作时采用直写法（write through）,则能存放32K字数据的cache的总容量至少应为（ ）位。

A.1504K

B.1536K

C.1568K

D.1600K

解析：

cache存储容量：32K×32b=2¹⁰Kb=1024Kb

主存块大小为一个字，每字32位，按字节编址，一块4个字节，块内地址2位；32K字/1字=32K=2¹⁵，行号15位；主存地址为32位，所以标号32-15-2=15位；有效位1位，直写法无脏位，无替换算法控制位；

cache标记阵列容量2¹⁵×16b=512Kb；

cache总容量：：1024Kb+512Kb=1536Kb

所以答案为B

29.假定主存地址位数为32位，按字节编址，主存和cache之间采用直接映射，主存块大小为一个字，每字32位写操作 时采用回写法（write back）,则能存放32K字数据的cache的总容量至少应为（ ）位。

A.1504K

B.1536K

C.1568K

D.1600K

解析：

与上题不同点在于使用了回写法，故多了脏位1位

cache标记阵列容量2¹⁵×17b=544Kb；

cache总容量：1024Kb+544Kb=1568Kb

所以答案为C

30.假定主存按字节编址，cache共有64行，采用4路组向量映射方式，主存块大小为32B,所有编号从0开始。主存第2593 号单元所在的主存块会映射到cache的第（ ）组。

A.1

B.17

C.34

D.81

解析：

cache可分为16组，每组4行；主存按字节编址，即一个存储单元存储一个字节；一块32B，32个字节，即一块是32个存储单元。2592/32=81，所以2593单元在第82块，编号为81；81%16=1

所以答案为A

31.某计算机的主存地址空间大小为256M，按字节编址。 指令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)

cache存储容量：64B×16=2¹⁰B

主存地址28位；256M×8b/64×8b=2²²,块号22位；标号18位；行号4位；块内地址6位

标号18位，有效位1位，cache标记阵列容量：16×19b=38B

cache总容量：2¹⁰B+38B=1062B

数据cache总容量：1062/2=531B

(2)

数组a按行优先方式存放，其地址为 320(十进制)。按字节编制，一个存储单元存储1个字节，a[0] [31]所在存储单元：320+31×4=444；一块64B，即一块64个存储单元；444/64=7块，即a[0] [31]在第7块，块号为6，6%8=6，即a[0] [31]所在主存块对应的cache行号是6

a[1] [1]所在存储单元：320+257×4=1348，1348/64=22块，块号21，21%8=5，即a[0] [31]所在主存块对应的cache行号是5

(3)

每块16个int，每次不命中时调入16个元素，后面连续15个都命中，程序A的命中率为：15/16×100%=93.75%

程序B列优先计算a[0] [0]，a[1] [0]，a[2] [0]，………每次连 续计算的元素肯定不在同一个调入cache的块，每次都不命中， 命中率为0%

32.假设有三道程序(用户标志号为A，B，C)，其基址寄存器内容分别 为SA，SB，SC ，在主存中，每道程序都有一张段表，A程序有4段，C程序有3段。每段应有一张页表，段表的每行就表示相应页表的起始位置， 而页表内的每行即为相应的物理页号。请说明虚实地址变换过程。

解析：

①根据基号C执行SC加1（段号）操作，得到段表相应行地址， 其内容为页表的起始地址ｂ。

②执行b+2（页号），得到物理页号的地址，其内容即为物理页10。

③物理页号与页内地址拼接即得物理地址。

如计算机只有一个基址寄存器，基号可不要，多道程序切换时，操作系统修改基址寄存器内容。 可以看出，段页式虚拟存储系统由虚拟地址向主存地址的变换至少需要查两次表。

33.假设主存只有a,b,c三个页框，组成a进c出的FIFO队列，进程访问页面的序列是0，1，2，4，2，3，0，2，1，3，2号。若采用①FIFO算法， ②FIFO算法+LRU算法，用列表法分别求两种替换策略情况下的命中率

解析

FIFO算法，先进先出

命中率：2/11≈0.182

LRU算法，近期最少使用

命中率：3/11≈0.273

34.某计算机的页式虚存管理中，采用长度为32字的页，页表内容如下， 求当cpu程序按下列2进制虚拟字地址访问存储器时产生的实地址为多少？

（1）00001101

（2）10000000

（3）00101000

解析：

由表知虚页号3位；由选项知，页内地址8-3=5位。

逻辑地址：虚页号3位+页内地址5位；物理地址：实页号3位+页内地址5位

(1)00001101——0101101

(2)10000000——1000000

(3)00101000——缺页，需要从虚拟存储器调入主存

35.下列命令组合情况，一次访存过程中，不可能发生的是（）

A. TLB未命中，Cache未命中，Page未命中

B. TLB未命中，Cache命中，Page命中

C. TLB命中，Cache未命中，Page命中

D. TLB命中，Cache命中，Page未命

解析：

TLB中数据由Page项复制调入，若TLB命中则Page一定会命中

所以答案为D

36.某计算机主存地址空间大小为256MB，按字节编址。虚拟地址空间大小为4GB，采用页式存储管理，页面大小为4KB， TLB（快表）采用全相联映射，有4个页表项，内容如下表所示：

则对虚拟地址03FF F180H进行虚实地址变换的结果是（）

A. 015 3180H

B. 008 5180H

C. TLB缺页

D. 缺页

解析：

03FFFH——015 3180H

所以答案为A

37.假定编译器将赋值语句“x=x+3;”转换为指令”add xaddt, 3”，其中xaddt 是x对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的 TLB，且Cache 使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（）

A．0

B．1

C．2

D．3

通过查TLB获得实页号拼接页内地址获得主存物理地址，访问cache命中，用直写法直接写入cache和主存

所以答案为B

38.某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为 16MB，主存（物理）地址空间大小为1 MB，页面大小为4 KB；Cache 采用直接映射方式，共8行；主存与Cache 之间交换的块大小为32 B。 系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别下两图所示，图中页框号及标记字段的内容为十六进制形式。

请回答下列问题。

（1）虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位， 哪几位表示页框号（物理页号）？

（2）使用物理地址访问Cache 时，物理地址应划分成哪几个字段？ 要求说明每个字段的位数及在物理地址中的位置。

（3）虚拟地址001C60H 所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否Cache 命中？ 要求说明理由。

（4）假定为该机配置一个4路组相联的TLB，该TLB 共可存放8 个页项，若其当前内容（十六进制）如下图所示，则此时虚拟地址 024BACH 所在的页面是否在主存中？要求说明理由。

解析：

(1)因为虚拟（逻辑）地址空间大小为 16MB，按字节编址，所以虚拟地址共有24位；因为页面大小为4 KB，16MB/4KB=2¹²个页，所以虚页号是虚拟地址前12位，页内地址是虚拟地址后12位；

按字节编址，主存1MB=2²⁰B，物理地址共20位，前8位是物理页号，后12位是页内地址

(2)Cache 采用直接映射方式，共8行；主存与Cache 之间交换的块大小为32 B，块内地址5位，行号3位，标号12位

综上，划分三个字段，最前面12位标号，中间3位行号，最后5位块内地址

(3)001C60H——04C60H，虚页号为前12 位，即001H=1。查表可知，有效位为1，在主存中；物理地址为04C60H；0000 0100 1100 0110 0000，行号011=3，标记位04CH≠105H，未命中

(4)4路组相联，共8个页项，可分为2组，组号1位；0000 0010 0100 1011 1010 1101，组号为0，标号012H；由图可得有效位为1，故虚拟地址024BACH 所在的页面在主存中。

39.某计算机采用页式虚拟存储管理方式， 按字节编址。CPU进行存储访问过程如图所示

回答下列问题。

（1）主存物理地址占多少位？

（2）TLB采用什么映射方式？TLB用SRAM还是 DRAM实现？

（3）cache采用什么映射方式？若cache采用LRU替换算法和回写（Write Back）策略，则cache每行中除数据（Data）、Tag和有效位外，还应有哪些附加位？ Cache总容量是多少？Cache中有效位的作用是什么？

（4）若CPU给出的虚拟地址是0008 C040H，则对应的物理地址是多少？是否在cache中命中？说明理由。 若CPU给出的虚拟地址是0007 C260H，则该地址所在的主存块映射到Cache的组号是多少？

解析：

(1)由图知，主存物理地址占28位

(2)由图知，TLB中每项都有一个比较器，故TLB采用全相联映射方式。TLB采用SRAM实现。

(3)Cache中每组有两行，故采用2路组相联映射方式。 因为2路组相联并采用LRU替换算法，所以每行（或每组） 需要1位LRU位；因为采用回写策略，所以每行有1位修改位（脏位）

组号3位，2路组相联映射，所以cache共16行；块内地址5位，按字节编址，所以cache存储容量16×2⁵B=2⁹B

cache标号阵列容量=(20+1+1+1)b×16=46B

cache总容量=2⁹B+46B=558B

有效位用来指出所在Cache行中的信息是否有效

(4)虚页号20位=0008CH，对应物理地址为0040040H；0000 0000 0100 0000 0000 0100 0000，组号010=2，标号00400H，有效位为0，cache未命中。

虚拟地址0007 C260H=0000 0000 0000 0111 1100 0010 0110 0000，组号011=3