(王道计算机组成原理)第三章存储系统 |
您所在的位置：网站首页 › 如何计算cache的命中率 › (王道计算机组成原理)第三章存储系统 |
(王道计算机组成原理)第三章存储系统
|
王道考研复习指导获取：密码7281专栏目录首页：【专栏必读】王道考研408计算机组成原理万字笔记、题目题型总结、注意事项、目录导航和思维导图
文章目录
本节思维导图一：随机算法（RAND）二：先进先出算法（FIFO）三：近期最少使用算法（LRU）——效率最高四：最不经常使用算法（LFU）
本节思维导图
在第六节2：Cache和主存的映射方式（全相联映射、直接映射和组相连映射）中我们讲到了Cache和主存之间的映射关系，细致分析了三种映射方式各自的特点。那么下一个亟待解决的问题就是：Cache是很小的，主存却很大，如果Cache满了应该怎么办？ 这就是本节的主题——Cache的替换算法。当然，不同的映射方式其替换机制也会有所不同 全相联映射：Cache完全满了才需要替换，需要在全局中选择替换哪一块直接映射：如果对应位置为空则直接替换，无需考虑替换算法组相联映射：分组内满了才需要替换，需要在分组内选择替换哪一块本节以全相联映射为例，介绍以下四种替换算法 随机算法（RAND）先进先出算法（FIFO）近期最少使用算法（LRU）最不频繁使用算法（LFU）在讲解之前大家一定明白一点，CPU每访问一个内存块，都会立即把该内存块调入Cache中 一：随机算法（RAND）随机算法（RAND）：若Cache已满，则随机选择一块进行替换 通过以下叙述可知：随机算法十分简单，但是它完全没有考虑到局部性原理，命中率很低，实际效果很不稳定如下有4个Cache块，初始状态下4个Cache块均为空，采用全相连映射，CPU访问主存块的顺序为：{1,2,3,4,1,2,5,1,2,3,4,5}，CPU每访问一个内存块，都会立即把该内存块调入Cache中，前四次调入时由于都有空闲Cahce块，所以不会发生替换 访问主存块123412512345Cache #01111Cache #1222Cache #233Cache #34是否命中？否否否否是否替换？否否否否继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。由于1,2主存块已经被调入了Cache，所以直接命中 访问主存块123412512345Cache #0111111Cache #122222Cache #23333Cache #3444是否命中？否否否否是是是否替换？否否否否否否继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。对于5号主存块，它并没有调入Cache中，因此需要立即被调入，但此时已经没有空闲Cache块了，所以需要使用替换算法选择一块换出，然后再把5号主存块调入。这里采用的是随机算法，所以我们可以任意挑选一块调入，比如把3号主存块给替换出去 访问主存块123412512345Cache #01111111Cache #1222222Cache #233335Cache #34444是否命中？否否否否是是否是否替换？否否否否否否是继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。直接命中 访问主存块123412512345Cache #0111111111Cache #122222222Cache #23333555Cache #3444444是否命中？否否否否是是否是是是否替换？否否否否否否是否否继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。和上面一样，随机挑选一块换出 访问主存块123412512345Cache #01111111111Cache #1222222222Cache #233335555Cache #34444443是否命中？否否否否是是否是是否是否替换？否否否否否否是否否是继续访存，也即{1,2,3,4,1,2,5,1,2,3,4,5}。和上面一样，随机挑选一块换出 访问主存块123412512345Cache #011111111114Cache #12222222222Cache #2333355555Cache #344444433是否命中？否否否否是是否是是否否是否替换？否否否否否否是否否是是访存结束，{1,2,3,4,1,2,5,1,2,3,4,5}。直接命中 访问主存块123412512345Cache #0111111111144Cache #122222222222Cache #23333555555Cache #3444444333是否命中？否否否否是是否是是否否是是否替换？否否否否否否是否否是是否 二：先进先出算法（FIFO）先进先出算法（FIFO）：若Cache已满，则替换最先被调入Cache的块 通过以下叙述可知：先进先出算法实现也很简单，但该算法依然没有考虑到局部性原理，因为最先被调入的Cache块也有可能是会频繁访问到的。而且此算法容易产生抖动现象（—刚换上去的块又立马被换下）仍然采用之前的例子，直接进行到这一步 访问主存块123412512345Cache #0111111Cache #122222Cache #23333Cache #3444是否命中？否否否否是是是否替换？否否否否否否继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。对于5号主存块，它并没有调入Cache中，因此需要立即被调入，但此时已经没有空闲Cache块了，所以需要使用替换算法选择一块换出，然后再把5号主存块调入。这里采用的是FIFO算法，根据先进先出原则，最先被调入Cache的最先被替换，因此1号被替换 访问主存块123412512345Cache #01111115Cache #1222222Cache #233333Cache #34444是否命中？否否否否是是否是否替换？否否否否否否是继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。此时应该替换2号 访问主存块123412512345Cache #011111155Cache #12222221Cache #2333333Cache #344444是否命中？否否否否是是否否是否替换？否否否否否否是是后续步骤不再详细演示，最终结束状态如下 访问主存块123412512345Cache #0111111555544Cache #122222211115Cache #23333332222Cache #3444444333是否命中？否否否否是是否否否否否否是否替换？否否否否否否是是是是是是 三：近期最少使用算法（LRU）——效率最高近期最少使用算法（LRU）：该算法会为每一个Cache块设置一个计数器，用于记录每个Cache块究竟有多长时间没有被访问了。在替换时直接选取计数器最大的替换即可 通过以下叙述可知：LRU算法是基于局部性原理的，近期访问过的主存块，在不久的将来很有可能会被再次访问到，因此这种淘汰机制是合理的。LRU算法的实际运行效果也很优秀，Cache命中率也高计数器的变化规则如下 命中时：所命中的块的计数器清零，计数器比其低的块的计数器+1，其余不变未命中且还有空闲块时：新装入的块的计数器置为0，其余非空闲块的计数器全+1未命中且没有空闲块时：计数器最大的块被淘汰，新装入块的计数器置为0，其余块的计数器+1如下表格表示初始状态 计时器访问主存块1234125123450Cache #00Cache #10Cache #20Cache #3是否命中？是否替换？继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。由于1装入了第一个Cache块，属于未命中且还有空闲块，因此该块计数器置为0，其余非空闲块计数器全+1 计时器访问主存块1234125123450Cache #010Cache #10Cache #20Cache #3是否命中？否是否替换？否继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。情况同上 计时器访问主存块1234125123451Cache #0110Cache #120Cache #20Cache #3是否命中？否否是否替换？否否第三、四个主存块亦是如此 计时器访问主存块1234125123453Cache #011112Cache #12221Cache #2330Cache #34是否命中？否否否否是否替换？否否否否继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。此时Cache命中，因此需要将所命中块的计数器清零，比其低的块的计数器+1，其余不变 这一点其实就体现了LRU算法的核心，它能保证最近访问的块的计数器一定很低 计时器访问主存块1234125123450Cache #0111113Cache #122222Cache #23331Cache #344是否命中？否否否否是是否替换？否否否否否继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}，情况同上 计时器访问主存块1234125123451Cache #01111110Cache #1222223Cache #233332Cache #3444是否命中？否否否否是是是否替换？否否否否否否继续访存，也即{1,2,3,4,1,2,5,1,2,3,4,5}。此时属于 “未命中且没有空闲行”，所以计数器最大的块会被淘汰（淘汰3号主存块），新装入块的计数器置为0，其余块计数器全+1 计时器访问主存块1234125123452Cache #011111111Cache #12222220Cache #2333353Cache #34444是否命中？否否否否是是否是否替换？否否否否否否是继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。直接命中 注意：只需要将“比该块计数器值小的块的计数器+1”即可，大的不变，因此上面表格中的3号Cache的计时器就不用动了，这里很容易犯错 计时器访问主存块1234125123450Cache #0111111112Cache #122222221Cache #23333553Cache #344444是否命中？否否否否是是否是是否替换？否否否否否否是否继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。直接命中 计时器访问主存块1234125123451Cache #01111111110Cache #1222222222Cache #233335553Cache #3444444是否命中？否否否否是是否是是是否替换？否否否否否否是否否继续访存，{1,2,3,4,1,2,5,1,2,3,4,5}。未命中，且没有空行 计时器访问主存块1234125123452Cache #011111111111Cache #12222222223Cache #2333355550Cache #34444443是否命中？否否否否是是否是是否是否替换？否否否否否否是否否是继续访存，也即{1,2,3,4,1,2,5,1,2,3,4,5}。未命中，且没有空行 计时器访问主存块1234125123453Cache #0111111111112Cache #122222222220Cache #23333555541Cache #344444433是否命中？否否否否是是否是是否否是否替换？否否否否否否是否否是是继续访存，也即{1,2,3,4,1,2,5,1,2,3,4,5}。未命中，且没有空行 计时器访问主存块1234125123450Cache #01111111111153Cache #1222222222221Cache #233335555442Cache #3444444333是否命中？否否否否是是否是是否否否是否替换？否否否否否否是否否是是是 四：最不经常使用算法（LFU）最不经常使用算法（LFU）：该算法会为每一个Cache块设置一个计数器，用于记录每个Cache块被访问过几次。在替换时直接选取计数器最小的替换即可 通过以下叙述可知：LFU算法并没有很好地遵循局部性原理，比如微信聊天相关的块，在某个时间段内使用率会很高，但是一段时间后使用率会很低，并不科学计数器的变化规则为： 新调入的块计数器为0，之后每访问一次计数器就+1。需要替换时，选择计数器最小的一行替换若有多个计数器最小的行，可以按照行号递增或FIFO策略进行选择 计时器访问主存块1234125123450Cache #00Cache #10Cache #20Cache #3是否命中？是否替换？继续访存，也即{1,2,3,4,1,2,5,1,2,3,4,5} 计时器访问主存块1234125123450Cache #011110Cache #12220Cache #2330Cache #34是否命中？否否否否是否替换？否否否否继续访存，也即{1,2,3,4,1,2,5,1,2,3,4,5}。发生命中，计数器+1 计时器访问主存块1234125123451Cache #01111111Cache #1222220Cache #233330Cache #3444是否命中？否否否否是是是否替换？否否否否否否继续访存，也即{1,2,3,4,1,2,5,1,2,3,4,5}。选择计数器最小的那一行，但是这里有两行相同（都是0），所以再按照FIFO策略选择3号主存块淘汰 计时器访问主存块1234125123451Cache #011111111Cache #12222220Cache #2333350Cache #34444是否命中？否否否否是是否是否替换？否否否否否否是继续访存，也即{1,2,3,4,1,2,5,1,2,3,4,5}。1,2命中，计数器+1 计时器访问主存块1234125123452Cache #01111111112Cache #1222222220Cache #233335550Cache #3444444是否命中？否否否否是是否是是是否替换？否否否否否否是否否继续访存，也即{1,2,3,4,1,2,5,1,2,3,4,5}。需要进行替换，这里我们再采用行号递增的规则淘汰5号主存块 计时器访问主存块1234125123452Cache #011111111112Cache #12222222220Cache #2333355530Cache #34444444是否命中？否否否否是是否是是否是否替换？否否否否否否是否否是继续访存，也即{1,2,3,4,1,2,5,1,2,3,4,5}。命中，计时器+1 计时器访问主存块1234125123452Cache #0111111111112Cache #122222222220Cache #23333555331Cache #344444444是否命中？否否否否是是否是是否是是否替换？否否否否否否是否否是否继续访存，也即{1,2,3,4,1,2,5,1,2,3,4,5}。需要替换，只剩一个最小的了，替换3号主存块即可 计时器访问主存块1234125123452Cache #01111111111112Cache #1222222222220Cache #233335553351Cache #3444444444是否命中？否否否否是是否是是否是否是否替换？否否否否否否是否否是否是 |
【本文地址】
今日新闻 |
推荐新闻 |