Ch6-Memory中文

1、Chapter 6MemoryOutline 6.1 Introduction 6.2 Memory of types 6.3 Memory Hierarchy 6.4 Cache Memory(高速缓冲存储器） 6.5 Virtual Memory（虚拟存储器） 6.6 A Real-world Example of Memory Management23Chapter 6 Objectives Master the concepts of hierarchical memory (存储器层次）organization. Understand how each level of memory

2、 contributes to system performance, and how the performance is measured. Master the concepts behind cache memory, virtual memory, memory segmentation, paging and address translation（存储器段，页和地址的翻译）.存储器概述1 1、存储器：存储器：是计算机系统中的记忆设备，用来存放程序和数据。是计算机系统中的记忆设备，用来存放程序和数据。2 2、存储元存储元：存储器的最小组成单位，用以存储：存储器的最小组成单位，用以存

3、储1 1位二进制代码。位二进制代码。3 3、存储单元：存储单元：是是CPUCPU访问存储器基本单位，由若干个具有相同访问存储器基本单位，由若干个具有相同 操作属性的存储元组成。操作属性的存储元组成。4 4、单元地址：单元地址：在存储器中用以表识存储单元的唯一编号，在存储器中用以表识存储单元的唯一编号，CPUCPU通过该编号访问相应的存储单元。通过该编号访问相应的存储单元。5 5、字存储单元：字存储单元：存放一个字的存储单元，相应的单元地址叫字存放一个字的存储单元，相应的单元地址叫字地址。地址。6 6、字节存储单元：字节存储单元：存放一个字节的存储单元，相应的单元地址存放一个字节的存储单元，相应

4、的单元地址叫字节地址。叫字节地址。7 7、按字寻址计算机：按字寻址计算机：可编址的最小单位是字存储单元的计算机。可编址的最小单位是字存储单元的计算机。8 8、按字节寻址计算机：按字节寻址计算机：可编址的最小单位是字节的计算机。可编址的最小单位是字节的计算机。几个基本概念几个基本概念存储器各个概念之间的关系存储器各个概念之间的关系单元地址单元地址00000001.XXXX存储单元存储单元存储元存储元存储容量存储容量存储体存储体存储器分类存储器分类1. 1. 按存储介质分按存储介质分 半导体存储器：半导体存储器：用半导体器件组成的存储器。用半导体器件组成的存储器。磁表面存储器：磁表面存储器：用磁性

5、材料做成的存储器。用磁性材料做成的存储器。2. 2. 按存储方式分按存储方式分 随机存储器：随机存储器：任何存储单元的内容都能被随机存取，且存取任何存储单元的内容都能被随机存取，且存取 时间和存储单元的物理位置无关。时间和存储单元的物理位置无关。 顺序存储器：顺序存储器：只能按某种顺序来存取，存取时间和存储单元只能按某种顺序来存取，存取时间和存储单元 的物理位置有关。的物理位置有关。3. 3. 按存储器的读写功能分按存储器的读写功能分 只读存储器只读存储器(ROM)：存储的内容是固定不变的，只能读出而：存储的内容是固定不变的，只能读出而 不能写入的半导体存储器。不能写入的半导体存储器。随机读写

6、存储器随机读写存储器(RAM)：既能读出又能写入的半导体存储器。：既能读出又能写入的半导体存储器。 4. 4. 按信息的可保存性分按信息的可保存性分 非永久记忆的存储器非永久记忆的存储器：断电后信息即消失的存储器。：断电后信息即消失的存储器。永久记忆性存储器：永久记忆性存储器：断电后仍能保存信息的存储器。断电后仍能保存信息的存储器。86.1 Introduction Memory lies at the heart of the stored-program computer. In previous chapters, we studied the components from which

7、 memory is built and the ways in which memory is accessed by various ISAs. In this chapter, we focus on memory organization. A clear understanding of these ideas is essential for the analysis of system performance.96.2 Types of Memory There are two kinds of main memory: random access memory, RAM, an

8、d read-only-memory, ROM. There are two types of RAM, dynamic RAM (DRAM) and static RAM (SRAM). Dynamic RAM consists of capacitors that slowly leak their charge over time. Thus they must be refreshed every few milliseconds to prevent data loss. DRAM is “cheap” memory owing to its simple design.106.2

9、Types of Memory SRAM consists of circuits similar to the D flip-flop that we studied in Chapter 3. SRAM is very fast memory and it doesnt need to be refreshed like DRAM does. It is used to build cache memory, which we will discuss in detail later. ROM also does not need to be refreshed, either. In f

10、act, it needs very little charge to retain its memory. ROM is used to store permanent, or semi-permanent data that persists even while the system is turned off.SRAMSRAM存储器存储器 基本存储元是组成存储器的基础和核心基本存储元是组成存储器的基础和核心,它用来存储一位二进制信息它用来存储一位二进制信息0或或1。六管基本存储单元电六管基本存储单元电路路X X地地 址址 译译 码码 线线Y Y地地 址址 译译 码码 线线T 6T5VC

11、C(+5V )BABT1T2T3T4T7T8D DD D写 入读 出16161 bit SRAM1 bit SRAM1K bit SRAM1K bit SRAMSRAMSRAM存储器的组成存储器的组成一个一个SRAM存储器由存储器由存储体、读写电路、地址译码电路和控制电路存储体、读写电路、地址译码电路和控制电路等组成。等组成。 一个基本存储电路只能存储一个二进制位。一个基本存储电路只能存储一个二进制位。 将基本的存储电路有规则地组织起来，就是存储体。将基本的存储电路有规则地组织起来，就是存储体。 存储体又有不同的组织形式：存储体又有不同的组织形式： 将各个字的将各个字的同一位同一位组织在一个芯

12、片中；组织在一个芯片中； 将各个字的将各个字的4 4位位组织在一个芯片中，组织在一个芯片中， 如：如：2114 1K2114 1K4 4； 将各个字的将各个字的8 8位位组织在一个芯片中，组织在一个芯片中， 如：如：6116 2K6116 2K8 8； 如图所示：如图所示： 存储体将存储体将40964096个字的同一位组织在一个集成片中；个字的同一位组织在一个集成片中； 需需1616个片子组成个片子组成409640961616的存储器；的存储器； 40964096通常排列成矩阵形式，如通常排列成矩阵形式，如 64646464，由行选、列选线选中所需的单元。，由行选、列选线选中所需的单元。 双译

13、码方式双译码方式地址译码器分成两个，可有效减少选择线的数目。地址译码器分成两个，可有效减少选择线的数目。x1x64常用典型的SRAM芯片有6116、6264、62256等。 A7 A6 A5 A4 A3 A2 A1 A0 D0 D1 D2 GND VCC A8 A9 WE OE A10 CS D7 D6 D5 D4 D3 1 24 2 23 3 22 4 21 5 20 6 19 7 18 8 17 9 16 10 15 11 14 12 13 SRAM芯片实例芯片实例SRAM 6116 (2K 8)输入输入I/O工作方式工作方式CSWEOEDIDOHXXXHigh-Z非选择非选择LHLHig

14、h-ZDO读读LLHDIHigh-Z写写LLLDIHigh-Z写写LHHXHigh-Z选择选择 DRAM DRAM存储器存储器1.1.单管动态存储元单管动态存储元 数据线数据线 行行( (字字) )选择选择CDCST110T1单管单管DRAM的存储矩阵的存储矩阵 集成度高，功耗低集成度高，功耗低 具有易失性，必须刷新具有易失性，必须刷新 破坏性读出，必须读后重写破坏性读出，必须读后重写 读后重写，刷新均经由刷新放大器进行读后重写，刷新均经由刷新放大器进行 刷新时只提供行地址，由各列所拥有的刷新放大器，刷新时只提供行地址，由各列所拥有的刷新放大器， 对选中行全部存储细胞实施同时集体读后重写对选中

15、行全部存储细胞实施同时集体读后重写( (再生再生) )。DRAMDRAM的电气特征：的电气特征： NC DIN WE RAS A 0 A2 A1 GND VCC CAS DOUT A6 A3 A4 A5 A7 1 16 2 15 3 14 4 13 5 12 6 11 7 10 8 9 Intel 2164(64K1)引脚 A0A7：地址输入线：地址输入线RAS：行地址选通信号线，兼起片选信号作用（整个读：行地址选通信号线，兼起片选信号作用（整个读写周期，写周期，RAS一直处于有效状态）一直处于有效状态）CAS：列地址选通信号线：列地址选通信号线WE：读写控制信号：读写控制信号 0-写写 1-

16、读读Din：数据输入线：数据输入线Dout：数据输出线：数据输出线 半半导导体体存存储储器器 只读只读 存储器存储器 ROMROM 随机读写随机读写存储器存储器RAMRAM 掩膜掩膜ROMROM 可编程可编程ROM ROM （PROMPROM） 可擦除可编程可擦除可编程ROM ROM （EPROMEPROM） 电擦除电擦除ROM ROM （E E2 2PROMPROM） 静态静态RAM RAM （SRAMSRAM） 动态动态RAM RAM （DRAMDRAM） 半导体存储器半导体存储器236.3 The Memory Hierarchy Generally speaking, faster m

17、emory is more expensive than slower memory. To provide the best performance at the lowest cost, memory is organized in a hierarchical fashion. Small, fast storage elements are kept in the CPU, larger, slower main memory is accessed through the data bus. Larger, (almost) permanent storage in the form

18、 of disk and tape drives is still further from the CPU.246.3 The Memory Hierarchy This storage organization can be thought of as a pyramid:256.3 The Memory Hierarchy To access a particular piece of data, the CPU first sends a request to its nearest memory, usually cache. If the data is not in cache,

19、 then main memory is queried. If the data is not in main memory, then the request goes to disk. Once the data is located, then the data, and a number of its nearby data elements are fetched into cache memory.存储器层次结构存储器层次结构对存储器的要求是：对存储器的要求是：容量大，速度快，成本低。容量大，速度快，成本低。为解决三者之间的矛盾，目前通常采用为解决三者之间的矛盾，目前通常采用多级

20、存储器体系结构多级存储器体系结构， 即使用即使用高速缓冲存储器、主存储器和外存储器高速缓冲存储器、主存储器和外存储器。寄存器寄存器Cache主存储器主存储器辅助存储器辅助存储器 名称名称 高速缓冲高速缓冲 存储器存储器 主存储器主存储器 外存储器外存储器 简称简称 Cache 主存主存 外存外存用途用途高速存取指令和数据高速存取指令和数据 存放计算机运行期间的大量程序和数存放计算机运行期间的大量程序和数据据 存放系统程序和大型数据文件及数据库存放系统程序和大型数据文件及数据库特点特点 存取速度快，但存储容量小存取速度快，但存储容量小存取速度较快，存取速度较快， 存储容量不大存储容量不大存储容量

21、大，存储容量大， 位成本低位成本低存储器的用途和特点存储器的用途和特点286.3 The Memory Hierarchy This leads us to some definitions. A hit（命中） is when data is found at a given memory level. A miss（缺失） is when it is not found. The hit rate（命中率） is the percentage of time data is found at a given memory level. The miss rate（缺失率） is the p

22、ercentage of time it is not. Miss rate = 1 - hit rate. The hit time（命中时间） is the time required to access data at a given memory level. The miss penalty（缺失损失） is the time required to process a miss, including the time that it takes to replace a block of memory plus the time it takes to deliver the da

23、ta to the processor.296.3 The Memory Hierarchy An entire blocks of data is copied after a hit because the principle of locality（局部性原理） tells us that once a byte is accessed, it is likely that a nearby data element will be needed soon. There are three forms of locality: Temporal locality（时间局部性）- Rece

24、ntly-accessed data elements tend to be accessed again. Spatial locality（空间局部性） - Accesses tend to cluster. Sequential locality（顺序局部性） - Instructions tend to be accessed sequentially.306.4 Cache Memory The purpose of cache memory is to speed up accesses by storing recently used data closer to the CPU

25、, instead of storing it in main memory. Although cache is much smaller than main memory, its access time is a fraction of that of main memory. Unlike main memory, which is accessed by address, cache is typically accessed by content; hence, it is often called content addressable memory（内容寻址的存储器）. Bec

26、ause of this, a single large cache memory isnt always desirable- it takes longer to search.316.4 Cache Memory The “content” that is addressed in content addressable cache memory is a subset of the bits of a main memory address called a field（域）. The fields into which a memory address is divided prov

27、ide a many-to-one mapping(多对一映射） between larger main memory and the smaller cache memory. Many blocks of main memory map to a single block of cache. A tag field（标记域） in the cache block distinguishes one cached memory block from another.326.4 Cache Memory The simplest cache mapping scheme is direct m

28、apped cache（直接映射）. In a direct mapped cache consisting of N blocks of cache, block X of main memory maps to cache block Y = X mod N. Thus, if we have 10 blocks of cache, block 7 of cache may hold blocks 7, 17, 27, 37, . . . of main memory. Once a block of memory is copied into its slot in cache, a v

29、alid bit（有效位） is set for the cache block to let the system know that the block contains valid data.33346.4 Cache Memory The diagram below is a schematic of what cache looks like. Block 0 contains multiple words from main memory, identified with the tag 00000000. Block 1 contains words identified wit

30、h the tag 11110101. The other two blocks are not valid.356.4 Cache Memory The size of each field into which a memory address is divided depends on the size of the cache. Suppose our memory consists of 214 words, cache has 16 = 24 blocks, and each block holds 8 words. Thus memory is divided into 214

31、/ 2 3 = 211 blocks. For our field sizes, we know we need 4 bits for the block, 3 bits for the word, and the tag is whats left over:366.4 Cache Memory As an example, suppose a program generates the address 1AA. In 14-bit binary, this number is: 00000110101010. The first 7 bits of this address go in t

32、he tag field, the next 4 bits go in the block field, and the final 3 bits indicate the word within the block.376.4 Cache Memory If subsequently the program generates the address 1AB, it will find the data it is looking for in block 0101, word 011. However, if the program generates the address, 3AB（0

33、000111 0101 011）, instead, the block loaded for address 1AA would be evicted from the cache, and replaced by the blocks associated with the 3AB reference.386.4 Cache Memory Suppose a program generates a series of memory references such as: 1AB, 3AB, 1AB, 3AB, . . . The cache will continually evict a

34、nd replace blocks. The theoretical advantage offered by the cache is lost in this extreme case. This is the main disadvantage of direct mapped cache. Other cache mapping schemes are designed to prevent this kind of thrashing. 主存储器地址（来自主存储器地址（来自 CPU） 块号块号 B 块内地址块内地址 W 主存地址主存地址 未命中未命中 主存主存Cache 地址变换地址

35、变换 命中命中 已满已满 未满未满 块号块号 b 块内地址块内地址 w Cache地址地址 Cache 替换策略替换策略 替换块替换块 装入块装入块 Cache 数据送数据送 CPU（一个字）（一个字） 主存储器 地址映象：地址映象： 把主存中的程序按照某种规则装入到把主存中的程序按照某种规则装入到Cache中，并中，并建立主存地址与建立主存地址与Cache地址之间的对应关系。地址之间的对应关系。 地址变换：地址变换： 当程序已经装入到当程序已经装入到Cache之后，在程序运行过程中，之后，在程序运行过程中，把主存地址变换成把主存地址变换成Cache地址。地址。在选取地址映象方法要考虑的主要因

36、素：在选取地址映象方法要考虑的主要因素： 地址变换的硬件实现容易、速度要快，地址变换的硬件实现容易、速度要快， 主存空间利用率要高，主存空间利用率要高， 发生块冲突的概率要小。发生块冲突的概率要小。1. 1. 直接映象及其变换直接映象及其变换 映象规则：映象规则： 主存储器中一块只能映象到主存储器中一块只能映象到Cache的一个的一个特定的块中。特定的块中。 Cache地址的计算公式：地址的计算公式： bB mod Cb 其中：b为Cache块号， B是主存块号， Cb是Cache块数。 实际上，Cache地址与主存储器地址的低地址与主存储器地址的低位部分完全相同。位部分完全相同。 直接映象方

37、式的地址映象规则直接映象方式的地址映象规则 块块 0 块块 1 区区 0 块块 Cb-1 块块 0 块块 Cb 块块 1 块块 Cb+1 区区 1 块块 Cb-1 块块 2Cb-1 Cache 块块 Mb-Cb 块块 Mb-Cb+1 区区 Me-1 块块 Mb-1 主主存存储储器器 直接映象方式的地址变换过程：直接映象方式的地址变换过程： 用主存地址中的块号用主存地址中的块号B去访问区号存储器，去访问区号存储器，把读出来的区号与主存地址中的区号把读出来的区号与主存地址中的区号E进行进行比较：比较： 比较结果相等，有效位为1，则Cache命中，否则该块已经作废。 比较结果不相等，有效位为1，Ca

38、che中的该块是有用的，否则该块是空的。 主主存存地地址址 区区号号 E 块块号号 B 块块内内地地址址W Cache 地地址址 块块号号 b 块块内内地地址址 w 块块失失效效 相相等等比比较较 比比较较相相等等且且有有效效为为 1 E 1 访访问问 Cache 区区号号 E（按按地地址址访访问问） 有有效效位位 区区表表存存储储器器 直接映象方式的地址变换规则直接映象方式的地址变换规则 直接映象及其变换的优缺点直接映象及其变换的优缺点 主要优点：主要优点： 硬件实现很简单，不需要相联访问存储器硬件实现很简单，不需要相联访问存储器 访问速度也比较快，实际上不需要进行地访问速度也比较快，实际上

39、不需要进行地址变换址变换 主要缺点：主要缺点： 块的冲突率比较高。块的冲突率比较高。466.4 Cache Memory Instead of placing memory blocks in specific cache locations based on memory address, we could allow a block to go anywhere in cache. In this way, cache would have to fill up before any blocks are evicted. This is how fully associative（全关联

40、） cache works. A memory address is partitioned into only two fields: the tag and the word.476.4 Cache Memory Suppose, as before, we have 14-bit memory addresses and a cache with 16 blocks, each block of size 8. The field format of a memory reference is: When the cache is searched, all tags are searc

41、hed in parallel to retrieve the data quickly. This requires special, costly hardware.全相联映象及其变换全相联映象及其变换 映象规则：映象规则：主存的任意主存的任意 一块可以映象到一块可以映象到Cache 中的任意一块。中的任意一块。（映象关系有CbMb种）块块 0块块 1块块 0块块 1块块 i块块 Cb-1Cache块块 Mb-1主主存存储储器器 地址变换规则地址变换规则 用硬件实现非常复杂用硬件实现非常复杂 块块号号 B 块块内内地地址址W 主主存存地地址址 Cache 地地址址 块块号号 b 块块内内地

42、地址址 w 相相联联比比较较 命命中中 B b 主主存存块块号号 B Cache 块块号号 b 有有效效位位 目目录录表表（由由相相联联存存储储器器构构成成，共共 Cb个个字字） 506.4 Cache Memory You will recall that direct mapped cache evicts a block whenever another memory reference needs that block. With fully associative cache, we have no such mapping, thus we must devise an algor

43、ithm to determine which block to evict from the cache. The block that is evicted is the victim block(牺牲块）. There are a number of ways to pick a victim, we will discuss them shortly.516.4 Cache Memory Set associative（组相联） cache combines the ideas of direct mapped cache and fully associative cache. An

44、 N-way set associative （N路级相联）cache mapping is like direct mapped cache in that a memory reference maps to a particular location in cache. Unlike direct mapped cache, a memory reference maps to a set of several cache blocks, similar to the way in which fully associative cache works. Instead of mappi

45、ng anywhere in the entire cache, a memory reference can map only to the subset of cache slots.526.4 Cache Memory The number of cache blocks per set in set associative cache varies according to overall system design. For example, a 2-way set associative cache can be conceptualized as shown in the sch

46、ematic below. Each set contains two different memory blocks.536.4 Cache Memory In set associative cache mapping, a memory reference is divided into three fields: tag, set, and word, as shown below. As with direct-mapped cache, the word field chooses the word within the cache block, and the tag field

47、 uniquely identifies the memory address. The set field determines the set to which the memory block maps.546.4 Cache Memory Suppose we have a main memory of 214 bytes. This memory is mapped to a 2-way set associative cache having 16 blocks where each block contains 8 words. Since this is a 2-way cac

48、he, each set consists of 2 blocks, and there are 8 sets. Thus, we need 3 bits for the set, 3 bits for the word, giving 8 leftover bits for the tag:3. 3. 组相联映象及其变换组相联映象及其变换 映象规则：映象规则： 主存和主存和Cache按同样大小划分成块和组。按同样大小划分成块和组。 主存和主存和Cache的组之间采用直接映象方式。的组之间采用直接映象方式。 在两个对应的组内部采用全相联映象方式。在两个对应的组内部采用全相联映象方式。 组相联映

49、象方式的优点：组相联映象方式的优点： 块的冲突概率比较低，块的冲突概率比较低， 块的利用率大幅度提高，块的利用率大幅度提高， 块失效率明显降低。块失效率明显降低。 组相联映象方式的缺点：组相联映象方式的缺点： 实现难度和造价要比直接映象方式高。实现难度和造价要比直接映象方式高。 块块 0 组组 0 Gb-1 Gb 组组 1 2Gb-1 区区 0 块块 0 GbCg-Gb 组组 0 组组 Cg-1 Gb-1 Cb-1=GbCg-1 Gb 1 2Gb-1 GbCg(Me-1) Cg(Me-1) GbCg(Me-1)+Gb-1 Cb-Gb=CgGb-Gb GbCg(Me-1)+Gb Cg-1 CgM

50、e-Cg+1 Cb-1=CgGb-1 GbCg(Me-1)+2Gb-1 块块 2（Cb-1） Me-1 Cache Me-Gb=GbCgMe-Gb CgMe-1 Mb-1=GbCgMe-1 主主存存储储器器 组组相相联联映映象象方方式式 组相联映象的地址变换过程：组相联映象的地址变换过程：用主存地址中的组号用主存地址中的组号G按地址访问块表存储器。按地址访问块表存储器。 把读出来的一组区号和块号与主存地址中的把读出来的一组区号和块号与主存地址中的区号和块号进行区号和块号进行相联比较相联比较。如果有相等的，表示Cache命中；如果全部不相等，表示Cache没有命中。 区区号号 E 组组号号 G

51、组组内内块块号号 B 块块内内地地址址 W 主主存存地地址址 组组号号 g 组组内内块块号号 b 块块内内地地址址 w Cache 地地址址 不不等等 相相联联比比较较 相相等等 相相联联比比较较(Gb个个块块) 区区号号 E,组组内内块块号号 B 组组内内块块号号 b 块块 表表 组相联映象的地址变换组相联映象的地址变换 上节课主要内容上节课主要内容 Cache与主存的三种映射方式与主存的三种映射方式 直接相联 全相联 组相联 本节课主要内容本节课主要内容 三种替换算法三种替换算法 LRU（最久最少使用） FIFO（先进先出） RANDOM（随机替换）59606.4 Cache Memory

52、 With fully associative and set associative cache, a replacement policy（替换策略） is invoked when it becomes necessary to evict a block from cache. An optimal replacement policy（最优替换策略） would be able to look into the future to see which blocks wont be needed for the longest period of time. Although it i

53、s impossible to implement an optimal replacement algorithm, it is instructive to use it as a benchmark for assessing the efficiency of any other scheme we come up with.616.4 Cache Memory The replacement policy that we choose depends upon the locality（局部性） that we are trying to optimize- usually, we

54、are interested in temporal locality（时间局部性）. A least recently used (LRU) （最近最少使用）algorithm keeps track of the last time that a block was assessed and evicts the block that has been unused for the longest period of time. The disadvantage of this approach is its complexity: LRU has to maintain an acces

55、s history for each block, which ultimately slows down the cache.LRULRU算法及其实现算法及其实现为每一块设置一个计数器为每一块设置一个计数器 计数器的长度与块号字段的长度相同计数器的使用及管理规则：计数器的使用及管理规则：新装入或替换的块，计数器清新装入或替换的块，计数器清0，同组中其它，同组中其它块的计数器加块的计数器加1。命中块的计数器清命中块的计数器清0，同组的其它计数器中，同组的其它计数器中，凡计数器的值小于命中块计数器原来值的加凡计数器的值小于命中块计数器原来值的加1，其余计数器不变。，其余计数器不变。需要替换时，在

56、同组的所有计数器中选择计数需要替换时，在同组的所有计数器中选择计数值最大的计数器，它所对应的块被替换。值最大的计数器，它所对应的块被替换。LRU算法的优缺点算法的优缺点主要优点：主要优点： (1)命中率比较高，命中率比较高， (2)能够比较正确地利用程序的局部性特点，能够比较正确地利用程序的局部性特点， (3)充分地利用历史上块地址流的分布情况，充分地利用历史上块地址流的分布情况， (4)是一种堆栈型算法，随着组内块数增加，是一种堆栈型算法，随着组内块数增加，命中率单调上升。命中率单调上升。主要缺点：主要缺点： 控制逻辑复杂，控制逻辑复杂，因为增加了判断和处理是否命中的情况。 例例3.13：I

57、BM 370/165机的机的Cache采用组相联映采用组相联映象方式。每组有象方式。每组有4块，为了实现块，为了实现LRU替换算替换算法，在块表中为每一块设置一个法，在块表中为每一块设置一个 2 位的计数位的计数器。在访问器。在访问Cache的过程中，块的装入、替的过程中，块的装入、替换及命中时，计数器的工作情况如表换及命中时，计数器的工作情况如表：块块地地址址流流主主存存块块1主主存存块块2主主存存块块3主主存存块块4主主存存块块5主主存存块块4块块号号 计计数数器器 块块号号 计计数数器器 块块号号 计计数数器器 块块号号 计计数数器器 块块号号 计计数数器器 块块号号 计计数数器器Cac

58、he块块0100101110111500501Cache块ache块块20110300301310310Cache块块3011011400401400装装入入装装入入装装入入装装入入替替换换命命中中656.4 Cache Memory First-in, first-out (FIFO) （先进先出）is a popular cache replacement policy. In FIFO, the block that has been in the cache the longest, regardless of when it was last

59、used. A random replacement policy（随机替换策略） does what its name implies: It picks a block at random and replaces it with a new block. Random replacement can certainly evict a block that will be needed often or needed soon, but it never thrashes.（抖动）4. 4. 主要页面替换算法主要页面替换算法(1)随机算法随机算法（RAND random algorith

60、m） 算法简单，容易实现。 没有利用历史信息，没有反映程序的局部性 命中率低。(2)先进先出算法先进先出算法 (FIFO first-in first-out algorithm) 容易实现，利用了历史信息， 没有反映局部性。 最先调入的页面，很可能也是要使用的页面676.4 Cache Memory The performance of hierarchical memory is measured by its effective access time (EAT)（有效访问时间）. EAT is a weighted average that takes into account the