1.1.存储层次的设计依据（程序局部性原理）
①程序局部性原理定义：对大量典型程序运行情况分析的结果表明，在较短时间内，程序产生的地址往往集中在存储器的一个很小的范围，这种现象称为程序访问的局部性，可细分为时间局部性和空间局部性。
②时间局部性定义：时间局部性是指被访问的存储单元在一个较短的时间间隔内很可能又被访问（如循环中的变量）。
③空间局部性定义：被访问的某个存储单元的临近单元在一个较短的时间间隔内很可能也被访问（如数组中的元素）。
④工作集合的定义与变化：处理机在某段时间经常使用的空间范围被称为工作集合。在几乎所有的程序中，工作集合的改变都是非常缓慢的，有时甚至是不变的。
⑤程序的执行时的地址不是随机分布的，而是自然簇集形成的“块”或“页”。
1.2.存储层次的模型和性能指标
①存储层次的定义：存储层次是指两个或两个以上速度、容量和价格不相同的存储器用硬件、软件或硬件软件结合的方式构成存储系统。
②存储系统的设计目标：访问速度尽可能快，容量尽可能大，价格尽可能低。
③常用的访问时间、存储容量、位价格表示：TAi表示访问时间，Si表示存储容量，Ci为每位的价格。
④命中率的定义：是指在某个存储器中访问到的次数与访问所有存储器的总次数之比。
2.1.Cache的功能
①Cache的概述：Cache是一种高速缓冲存储器，用于解决CPU与主存速度不匹配的问题。
②Cache功能概述：Cache容量小，速度快，由SRAM组成。Cache直接制作在CPU芯片内，速度与CPU几乎相同。程序运行时，CPU使用的一部分数据和指令会预先成批拷贝到Cache中，因此Cache的内容是主存储器中部分内容的映像。当CPU需要从内存中读写数据或指令时，首先检查Cache，如果有则直接从Cache中读取，而不用访问主存储器。
2.2.Cache的基本原理
①Cache的基本原理：CPU每次需要访问主存进行存取数据时，首先将根据数据地址判断对应地址的块是否在Cache中。如果在则直接从Cache中取出信息而不用访问主存；如果不在则从主存中取出地址所对应的块并放入Cache中，再将内容送到CPU内。
②Cache的命中和失靶的定义：如果被访问的信息在Cache中则称为命中，如果被访问的信息不在cache中则称为缺失或失靶。
③Cache和主存的块与行：Cache与主存之间以块（或称为行）为单位交换数据，块的大小以主存一个周期内能访问到的数据长度为限。
④相联存储器：相联存储器是Cache的一部分，用于比较判断某一个数据块是否在Cache中。
⑤Cache工作原理（重点）：Cache和主存的块容量均相同。任意一个主存地址，都可以写为“主存块号（标记号）+块内地址”的形式；同样Cache中的内容也可以写为“Cache块号+块内地址”的形式。并可以以这种形式放入Cache中。主存块号和Cache块号的对应关系存储在相联存储器中。当CPU访问主存时，首先将主存地址转换为“主存块号+块内地址”的形式，再与相联存储器中的内容进行比较判断这个数据块是否Cache中。CPU将地址与相联存储器中的标记内容进行比较判断块是否在Cache中，如果在则命中，不在则失靶。如果失靶，则判断Cache是否已满，如果未满则把块直接送入Cache，如果已满则用替换算法将别的块换出后再将该块放入。
⑥Cache的调度过程：Cache完全由计算机硬件负责调度，对系统和应用程序员完成透明。
2.3.Cache的命中率
①Cache的命中率的定义：Cache中存取次数与总共存取次数（Cache的存取次数和主存的存取次数之和）的比例称为Cache的命中率。
②一般计算机的Cache命中率：一般计算机的Cache命中率达到百分之九十五以上。
3.1.主存与cache地址映射的概述
①Cache的映射功能定义：在引入Cache之后，CPU每次访问主存之前都会根据相联存储器中的内容判断所访问的主存块是否在cache中，又因为主存块的数量远多于Cache块的数量，因此需要考虑多个主存数据块如何映射到一个Cache块中才能实现快速查找。
②Cache的三种常见映射方法：三种常见的映射方式分别是全相联映射、直接相联映射和组相联映射。
③Cache中的有效位的定义：Cache中在一般情况下每一行有一个额外数位V称为有效位，表示该行的数据是否有效。当Cache中该行不为空时，有效位置一，否则置零。操作系统程序员可以通过设置“Cache冲刷指令”将其中所有行的有效位置零，因此Cache对操作系统程序员不是透明的。
④Cache的容量定义：Cache的容量包括数据区容量和其他区域容量。在一般情况下，Cache容量就是指Cache数据区的容量。
3.2.全相联映射的工作原理
①全相联映射方式的定义：全相联映射算法是指主存的每一个数据块可以映射到cache中的任意行。全相联映射方式中没有Cache索引字段。
②全相联映射方式的优点和缺点：全相联映射方式的优点为：块冲突率低，Cache的利用率高；缺点为：淘汰算法复杂，比较电路难以设计。
③全相联映射方式的适用情况：全相联映射方式适用于小容量的Cache。
④全相联映射方式的工作原理（重点）：
A.CPU需要访问主存时，将主存地址转换为“块号（标记）+块内地址”形式，其中块内地址与块的大小有关，块号与主存大小和主存中块的个数有关。
B.CPU根据块号到相联存储器中进行查找，判断该主存块是否在Cache中；
C.判断过程：将CPU提供的块号和相联存储器中所有块号进行比对，如果存在一个块号和CPU提供的块号相同则说明数据库在Cache中，否则不在Cache中。
D.对于数据块不在Cache中的情况，则将主存中相应的块取出并放入Cache中。此时需要把新加入的块的块号装入相联存储器中。
例题：某全相联映射的高速缓存为128B，每块为4个字（1个字32位），主存容量4096B，写出缓存地址和主存地址。
解析：
①由于Cache的每块为4个字，并且一个字为32位，因此Cache每块有128位=16B；
②由于Cache中每块有16B，因此主存和Cache中都需要4位表示块内地址；
③Cache中的块数=128B/16B=8（块），因此需要3位表示块号；
④主存中的块数=4096B/16B=256（块），因此需要8位表示块号。
综上所述，缓存地址为“3位块号+4位块内地址”；主存地址为“8位块号+4位块内地址”
3.3.直接映射的工作原理
①直接映射方式定义：主存中的每一个块都固定映射到Cache中的一个特定行。
②直接映射方式的优点和缺点：直接映射方式的优点为：淘汰算法简单，方便电路设计；缺点为：块冲突率高，Cache的空间利用率低。
③直接映射方式的适用情况：直接映射方式适用于大容量的Cache。
④直接映射方式主存块号与Cache行号关系：Cache行号=主存块号 % Cache块容量
⑤直接映射方式的工作原理：
A.CPU需要访问主存时，将主存地址转化为“区号+区内块号+块内地址”的形式，其中块内地址与块的大小有关，区内块号与缓存块的个数有关，区号与主存大小和区的大小有关。
B.CPU根据地址的区内块号，将相联存储器中特定行的区号与地址的区号（区号作为标记）进行比较，判断主存块是否在Cache中；
C.判断过程：如果特定行的区号与地址的区号相同且标记位为1则为命中，否则失靶。
D.对于失靶的情况，则需要将内存中特定的数据块取出放入Cache中并更新相联存储器。
例题1：某直接映射的高速缓存为128B，每块为4个字（1个字32位），主存容量4096B，写出缓存地址和主存地址。
解析：
①由于Cache的每个块有4个字，且每个字32位，因此每个Cache块为128位=16B；
②由于Cache的容量为128B，因此Cache中的块数=128B/16B=8（块），因此需要需要3位表示区内块号；
③由于每块为16B，因此需要4位来表示块内地址；
④由于主存容量为4096B，且每一个块为16B，一个区有8个块，因此共有4096/(16*8)=32个区，所以需要5位表示区号。
综上所述，缓存地址为“3位块号+4位块内地址”，主存地址为“5位区号+3位区内块号+4位块内地址”。
例题2：某直接映射高速缓存有8块，每块为16B，则字节为191的地址应该对应Cache中的哪一块？
解析：根据直接映射的原理可知，内存单元191在主存中的块数为191整除16=11（块），因此对应Cache中的块数为11%8=3（块）。
例题3：假设某Cache有16块，每块为2个字节，则内存中地址为1200的单元应该对应Cache中的哪一块？
解析：1200所对应的单元在内存中的块数为1200整除16=75，因此在Cache中的块数为75%16=11（块）。
例题4：主存和cache之间采用直接映射，块大小为16B。cache的数据区容量为64KB，主存地址为32位，按字节编址。如果考虑有效位和标记位在内，计算cache的容量大小（C）
A.64KB B.64K×16b(tag)+64K×8b C.4K×(1+16)b+64K×8b D.4K×16b+64K×8b+1b(V有效位)
解析：
①在不作特殊说明的情况下Cache的容量大小就默认为数据区的容量大小，但是此处考虑了相联存储器的部分。
②由于每一个块大小为16B，因此块内地址为4位。
③由于Cache的数据区容量为64KB，因此一共有64KB/16B=4K（块），因此区内块号需要用12位进行表示。
④由于主存地址为32位，因此剩余32-4-12=16位用于作标记位。
⑤由于Cache中一共有4K个块，每个块有16位标记位和1位有效位因此Cache的总容量为64KB+4K×(1+16)b=64K×8b+4K×(1+16)b。
3.4.组相联映射的工作原理
①组相联映射方式定义：组相联映射是组间采用直接映像，组内采用全相联的映射方式。组相联映射方式对Cache块进行分组，对于任意一个主存块，其可以映射到Cache指定组的任意一行中。
②组相联映射和其他两种映射方式的关系：全相联映射和直接相联映射都可以视为组相联映射的一种极端情况。
③组相联映射的优点和缺点：组相联映射方式结合了全相联映射和直接相联映射的特点，因此其特点介于全相联映射和直接相联映射之间。
④组相联映射的主存块号与Cache组号公式：Cache组号=主存块号 % Cache组数
⑤组相联映射方式的工作原理（重点）：
A.CPU需要访问主存时，将主存地址转换为“主存组号+块在组中的编号+块内地址”的形式，其中块在组中的编号即为Cache组号，与主存块号和Cache的组数有关。 B.CPU根据转换后地址的主存组号，并由块在组中的编号，将Cache中的特定组的每一行与当前主存组号进行比较，判断主存块是否在Cache中。 C.判断过程：如果指定的Cache组中存在一行的标记和当前主存组号相同且标记位有效，则说明命中，否则失靶。
3.5.Cache映射算法的相关概念
①命中率的定义：CPU所访问的主存块在Cache中的概率。
②命中时间的定义：在Cache中的访问时间，包括判断时间和Cache访问时间两部分。
③缺失率的定义：CPU所访问的主存块不在Cache中的概率。
④缺失损失的定义：由于CPU所访问的内容不在Cache中而导致CPU需要访问一个主存块所花的时间。缺失损失远高于命中时间。
⑤提高命中率的意义：提高命中率可以显著降低平均访问时间，提高系统效率。
⑥提高命中率的方法：
A.增大Cache的容量；
B.采用2级或3级Cache技术；
C.在Cache中采用快速查找算法以判定是否命中；
D.失靶时采用更加有效的替代算法；
E.通过编译器对目标程序进行优化；
F.程序员编写程序时考虑到Cache的影响。
⑦关联度的定义：一个主存块映射到Cache中可能存放的位置的个数。直接映射的关联度最低为1，全相联映射的关联度最高为Cache的行数，N-路组相联映射的关联度居中。
⑧关联度和命中率和命中时间的关系：关联度越高，命中率越高且命中时间越短。
⑨关联度与标记位长度和空间开销的关系：关联度越高，总的标记位越长且额外的空间开销越大。
常见的四种替换算法：先进先出（FIFO）算法、最不经常使用（LFU）算法、近期最少使用（LRU）算法、随机替换算法。
四种替换算法概述：
①先进先出法：总是把最先进入Cache的一行替换掉；
②最不经常使用算法：将一段时间内被访问次数最少的行取出。最不经常使用算法的缺点是不能反映近期的情况。
③近期最少使用算法：近期最少使用的行被换出。该算法同样需要配合一个计数器使用：当Cache命中一次，被命中的一行清零，而其他行的计数器都加一。每一次将计数器值最大的一行换出。
④随机替换算法：从特定位置中随机选择一行换出。该方法在硬件上容易实现且效率也高于前两种算法，但是降低了命中率和Cache的工作效率。
①先进先出算法和最近最少使用算法的命中率比较：先进先出算法并不是一种栈算法，其命中率不会随组的增大而提高。LRU是一种栈算法，其命中率随组的增大而显著提高。
②最近最少使用算法的实现方式：该算法在实现时并不是通过移动块来实现，而是给每一个Cache行设置一个计数器，根据计数器的数值来判断主存块的使用情况。该计数值称为LRU位。
③颠簸的定义：当某段时间集中访问的内存超过了Cache的最大容量时，如果这部分内存中的内容循环出现，则不管是FIFO算法还是LRU算法的命中率都始终为零，该现象称为颠簸。简单理解就是“刚刚被替换出Cache中的块紧接着右马上被调用”。
④需要进行替换的映射算法：直接映射算法无需考虑替换，全相联映射和组相联映射需要考虑替换。
①Cache写操作的作用：解决Cache与主存的一致性问题。例如从输入输出到来的设备已经修改了主存，但是Cache中的内容还没有发生变化；又例如Cache中的内容进行了修改但是主存没有更新。
②Cache写操作的两种常用策略：全写法和回写法。
③全写法的定义：全写法又称为写直达WT，在CPU执行写操作时，如果命中则必须将数据同时写入Cache和主存中。这种算法在相联存储器中无需用于判定内容是否发生修改了的“修改位”。全写法的可靠性高。
④回写法的定义：回写法WB中，在CPU进行写操作时只写Cache，只有当Cache中的内容被替换时才根据相联存储器中的修改位决定是否需要重写主存对应内容。回写法与主存的通信量少于全写法。
无论是全写法还是回写法，都可能出现写Cache但是没有命中的问题。如果没有命中，则直接向主存写入。因此两种算法都有一个是否把所写字在主存中的块读入Cache的问题，有两种读入方法。
①按写分配法的定义：写Cache不命中时需要把所写的字所在的主存数据块调入Cache中，在Cache中对数据块进行修改，在将数据块换出时才写回主存。全写法和回写法都可以使用按写分配法。
②不按写分配法定义：写Cache不命中时，只把要写的字写入主存，而不用包括所写的字在内的块从主存调入Cache中。该方法常用于全写法中。