1、第4章 存储系统4.4高速缓冲存储器4.4高速缓冲存储器 计算机系统中，因为CPU的工作速度提高很快，所以对存储器的速度和容量的要求越来越高。在CPU和主存之间插入一快速存储器，用于存放CPU最经常访问的指令或操作数据，这个快速存储器称为高速缓冲存储器(Cache)。这是当前计算机系统中为了提高运行速率所采取的改进计算机结构的主要措施之一。在高档微机中为了获得更高的效率，不仅设置了独立的指令Cache和数据Cache，还把Cache设置成二级或三级。4.4.1工作原理 高速缓冲存储器Cache由Cache存储体和Cache控制部件组成。Cache存储体通常由双极型半导体存储器或SRAM组成。C
2、ache控制部件是完成Cache管理算法的硬件电路，这个电路对程序员透明。Cache的组成结构如图4-19所示。4.4.1工作原理 在具有高速缓冲存储器的存储体系中，当CPU发出访问主存的操作请求后，CPU要访问的主存地址送到Cache，经相联存储映像表进行地址变换，就是把主存地址转换为Cache地址 如果CPU要访问的内容在Cache中，称为“命中”，则从Cache中读取数据送CPU。如果CPU要访问的内容不在Cache中，称“不命中”或“失靶”，则CPU送来的地址直接送到主存，在主存中读取数据，同时主存和Cache之间还要交换数据。4.4.1工作原理 为了便于在Cache和主存间交换数据，
3、Cache和主存空间都划分为大小相同的页，即主存空间的页和Cache空间页所包含的字节数相同。Cache空间的分配以及数据交换都以页为单位进行。在主存内容写入Cache时，如果Cache已满，要按某种替换策略选择被替换的内容。地址变换、替换策略等算法全部由Cache控制部件硬件来完成。4.4.1工作原理 另外，当CPU对内存执行写操作，要写的内容恰在Cache中，则Cache内容被更改，但该单元对应的主存内容尚没有改变，这就产生了Cache和主存内容不一致的情况。这就需要选择更新主存内容的算法。一般采用“写回法(Write back)”和“写直达法(Write through)”。写回法是CP
4、U对内存写的信息只写入Cache，在Cache页被替换时，先将该页内容写回主存后，再调入新页。写直达法又称存直达法，在每次CPU进行写操作时，将信息也写回主存。这样，在页替换时，就不必将被替换的Cache页内容写回，而可以直接调入新页。4.4.2映像方式 CPU提供给Cache的地址是主存地址，要访问Cache，必须把主存地址转换为Cache地址，这种地址变换叫做地址映像。常用的地址映像方式有全相联映像、直接映像和组相联映像。（1）全相联映像方式 全相联方式的映像规则是：主存中任一页可装入Cache内任一页的位置。采用相联存储器中的目录表来存放地址映像关系，即记录Cache中每一页所对应的主存
5、中的页。主存地址分为主存页号和页内地址，Cache地址分为Cache页号和页内地址。4.4.2映像方式 主存中一页数据装入Cache中一页后，将主存页号存入目录表中对应Cache页号的行单元中。当CPU送出主存地址后，让主存页号与目录表中各行单元中的页号作相联比较。如果有相同的，则将对应行的Cache页号取出，拼接上页内地址就形成了Cache地址。如相联表中无相同的页号，表示主存页未装入Cache，失靶，则去主存读。4.4.2映像方式 例4-5若Cache中有4页，主存中有16页。每页有4个字节。写出主存地址和Cache地址的对应关系。解：Cache有4页，共44=16个字节，所以字节地址为4
6、位，最后2位为页内地址，前2位为页号。主存共有164=64个字节，所以字节地址为6位，最后2位为页内地址，最高4位是标记。4.4.2映像方式 例4-6Cache中有4页，主存中有16页。每页有4个字节。已知Cache中目录表（存储映像表）如表4-1。写出CPU连续访问主存中第01H单元、31H单元和36H单元的命中情况。4.4.2映像方式 解：主存地址6位，前4位为主存页号，后2位为页内地址。CPU送出主存地址01H=000001H，主存页号为0000。在相联映像表中查表，找到了表中登记的主存页号0000，所以，命中。并且得到对应的Cache页号为00,即主存中0000页，在cache的00页
7、。拼接上页内地址，就是在Cache的0001单元。CPU送出主存地址30H=110000H，主存页号为1100。在相联映像表中查表，找到了表中登记的主存页号1100，所以，命中。并且得到对应的Cache页号为01,即主存中1100页，在Cache的01页。拼接上页内地址，就是在Cache的0100单元。CPU送出主存地址36H=110110H，主存页号为1101。在相联映像表中查表，表中没有登记主存页号1101，所以，Cache未命中,要去访问主存。4.4.2映像方式 全相联映像方式的优点是块冲突概率最低，只要Cache有空闲页，便可装入。只有当全部装满后，才会出现冲突。Cache 访问过程中
8、，需要依次查找目录表中的每一行，全部查完才能确定不命中，计算机系统中Cache容量一般都较大，目录表容量大，查表速度难以提高，所以目前很少使用。4.4.2映像方式（2）直接映像方式 直接映像方式中，一个主存页只能放入到Cache中的一个固定页中。直接映像的方法是将主存地址对Cache页数取模，得到的结果就是映像的Cache的页号。主存地址分为页面标记、页号和页内地址，Cache地址分为cache页号和页内地址。主存中某一页按照映像关系装入Cache中规定页后，将主存标记部分装入相联映像表中对应Cache页的行中。4.4.2映像方式 CPU访问时，首先根据主存地址，直接查出该主存页对应的Cach
9、e页号。在相联映像表中找到对应的Cache页后，检查它的标记和要访问的主存页标记是否一致。若一致，访问“命中”，再根据页内地址，从Cache中读数据。否则“不命中”(或失靶)，CPU直接从主存中读出。4.4.2映像方式 例4-7若Cache中有4页，主存中有16页。每页有4个字节。写出主存地址和Cache地址的对应关系。解：Cache有4页，共44=16个字节，所以字节地址为4位，最后2位为页内地址，前2位为页号。主存共有164=64个字节，所以字节地址为6位，最后2位为页内地址，中间2位为页号，最高2位为标记。4.4.2映像方式 例4-8Cache中有4页，主存中有16页。每页有4个字节。已
10、知Cache中存储映像表如表4-2。写出CPU连续访问主存中第01H单元和31H单元，36H单元的命中情况。4.4.2映像方式 解：主存地址6位，其中2位为标记，2位为页号，2位为页内地址。Cache地址为4位，2位为页号，2位为页内地址。当CPU送出主存地址01H=000001H，其中页号为00，到相联映像表中对应的00页，查得表中登记的标记是00，与要访问的主存地址标记一样，所以命中，即主存0000页在Cache 的00页，拼接上页内地址，得到要访问的主存单元在Cache的0001单元。当CPU送出主存地址31H=110001H，其中页号为00，到相联映像表中对应的00页，查得表中登记的标
11、记是00，与要访问的主存地址标记11不一样，所以未命中，要到主存访问数据。当CPU送出主存地址36H=110110H，其中页号为01，到相联映像表中对应的01页，查得表中登记的标记是11，与要访问的主存地址标记11一样，所以命中，即主存1101页在Cache 的01页，拼接上页内地址，得到要访问的主存单元在Cache的0110单元。4.4.2映像方式 例4-9CPU访问下列访主存字节地址序列1，4，8，5，20，17，19，56，9，11，4，43，5，6。假定Cache采用直接映像法，每页4字节，Cache容量为16字节。初始Cache为空，写出Cache的装入数据和命中情况。4.4.2映像
12、方式4.4.2映像方式 直接映像的优点是地址变换简单，实现容易且速度快；其缺点是页冲突的概率较高。当主存页需要装入Cache时，只能对应唯一的Cache页面，即使Cache中还有很多空页，也必须对指定的Cache页进行替换。4.4.2映像方式（3）组相联映像方式 组相联映像方式中将Cache空间分成组，每组多页。主存页号对Cache组数取模，得到主存中一页对应Cache中的组号，允许该页映射到指定组内的任意页。组相联映像法在各组间是直接映像，组内各页则是全相联映像，这样就实现了前两种方式的兼顾。组相联映像中，Cache页冲突概率比直接映像法低得多，由于只有组内各页采用全相联映像，地址相联表较小
13、，易于实现，而且查找速度也快得多。组相联映像方式中，主存地址包含页面标记、组号和页内地址，Cache地址包含组号、组内页号、页内地址。4.4.2映像方式 当CPU送出主存地址，主存页号对Cache组数取模，得到该页映像的组号，在映像表中相应组的若干页中查找是否有相同的主存标记，如果有相同的，则命中，在Cache中读取数据；若未命中，则在主存中进行访问并将该页调入Cache中，将标记写入相联映像表中。4.4.2映像方式 例4-10若Cache中有4页，主存中有16页。每页有4个字节。若Cache中每2页为1组，共有2组。写出主存地址和 Cache地址的对应关系。解：Cache有4页，共4*4=1
14、6个字节，所以Cache字节地址为4位，最后2位为页内地址，1位为组内页号，最高1位为组号。主存16页，共16*4=64字节，主存字节地址6位，2位为页内地址，1位为组号，3位为标记。4.4.2映像方式 例4-11Cache中有4页，主存中有16页。每页有4个字节，每组2页。已知Cache中标记情况表（存储映像表，如表4-3。）。写出CPU连续访问主存中第01H单元和31H单元、36H单元的命中情况。4.4.2映像方式 解：CPU送出主存地址01H=000001，除以每页字节数，得到主存页号为0000，页内地址为01。用主存页号对Cache组数2取模，得到组号为0，标记为000。在映像表中0组
15、的2页中查找标记000，命中。CPU送出主存地址31H=110001，除以每页字节数，得到主存页号为1100，页内地址为01。用主存页号对Cache组数2取模，得到组号为0，标记为110。在映像表中0组的2页中查找标记110，命中。CPU送出主存地址36H=110110，除以每页字节数，得到主存页号为1101，页内地址为10。用主存页号对Cache组数2取模，得到组号为1，标记为110。在映像表中1组的2页中查找标记110，命中。4.4.3替换算法 在访存时如果出现Cache页失效(即失靶)，就需要将主存页按所采用的映像规则装入Cache。如果此时出现页冲突，就必须按某种策略将Cache页替换
16、出来。替换策略的选取要根据实现的难易，以及是否能获得高的命中率两方面因素来决定。常用的方法有FIFO法及LRU法。在采用直接映像的Cache中，替换的页是确定的，不需要研究替换策略。在采用全相联映像的Cache中，由于可以将页装入Cache中任意一页，则需要替换策略。在采用组相联映像的Cache中，由于可以将页装入指定组中的任意一页，也需要替换策略。教材第108页4.4.3替换算法（1）先进先出法(FlFO)先进先出法的策略是选择最早装入的Cache页为被替换的页，这种算法实现起来较方便，但不能正确反映程序的局部性，因为最先进入的页也可能是目前经常要用的页，因此采用这种算法，有可能产生较大的页
17、失效率。教材第108页4.4.3替换算法 例4-12Cache中有3页，CPU访问主存页的页号地址流为1，2，3，4，1，2，5，1，2，3，4，5，采用FIFO替换策略。画出Cache中的替换情况。4.4.3替换算法 例4-13Cache中有4页，CPU访问主存页的页号地址流为1，2，3，4，1，2，5，1，2，3，4，5，采用FIFO替换策略。画出Cache中的替换情况。4.4.3替换算法（2）“近期最少使用”算法(LRU)“近期最少使用”算法能比较正确地反映程序的局部性，因为当前最少使用的页一般来说也是未来最少被访问的页。但是它的具体实现比FIFO算法要复杂一些。4.4.3替换算法 例4-14Cache中有4页时，CPU访存地址页号流为1、2、3、4、1、2、5、1、2、3、4、5时，采用LRU替换策略，写出Cache的替换情况。
