计算机组成与体系结构 · 替换写策略与流水线公式

三种。先说触发条件：当 Cache 产生了一次访问未命中之后，相应的数据应同时读入 CPU 和 Cache；但当 Cache 已存满数据后，新数据必须替换掉 Cache 中的某些旧数据。第一种随机算法，这是最简单的替换算法，完全不管 Cache 块过去、现在及将来的使用情况，简单地根据一个随机数选择一块替换掉。

第二种先进先出 FIFO 算法，按调入 Cache 的先后决定淘汰的顺序，在需要更新时将最先进入 Cache 的块作为被替换的块；这种方法要求为每块做一记录，记下它们进入 Cache 的先后次序，容易实现而且系统开销小，缺点是可能会把一些需要经常使用的程序块，例如循环程序，替换掉。

近期最少使用 LRU 算法，是把 CPU 近期最少使用的块作为被替换的块。它需要随时记录 Cache 中各块的使用情况，以便确定哪个块是近期最少使用的块。评价是：LRU 算法相对合理，但实现起来比较复杂、系统开销较大，通常需要对每一块设置一个称为「年龄计数器」的硬件或软件计数器，用以记录其被使用的情况。

完全正确。最后是写操作，三种方法，这块最容易张冠李戴。背景是：因为需要保证缓存在 Cache 中的数据与内存中的内容一致，相对读操作而言，Cache 的写操作比较复杂。

第一种写直达，也称为写通：当要写 Cache 时，数据同时写回内存；当某一块需要替换时，也不必把这一块写回主存，新调入的块可以立即把这一块覆盖掉。评价是实现简单，而且能随时保持主存数据的正确性，但可能增加多次不必要的主存写入，会降低存取速度。所以题目里「数据同时写回内存」这句描述的就是写直达。

对。写回是：CPU 修改 Cache 的某一块后，相应的数据并不立即写入内存单元，而是当该块从 Cache 中被淘汰时才把数据写回到内存中。实现细节也考：在采用这种更新策略的 Cache 块表中一般有一个标志位，当一块中的任何一个单元被修改时标志位被置 1；在需要替换掉这一块时，如果标志位为 1，则必须先把这一块写回到主存中去之后才能再调入新的块；如果标志位为 0，则这一块不必写回主存，只要用新调入的块覆盖掉即可。优点是操作速度快，缺点是因主存中的字块未随时修改而有可能出错。

标记法是：对 Cache 中的每一个数据设置一个有效位，当数据进入 Cache 后有效位置 1；而当 CPU 要对该数据进行修改时，数据只需写入内存，并同时将该有效位置 0。三种一句话区分——写直达是 Cache 和内存一起写、写回是先只写 Cache 等淘汰再写内存、标记法是改的时候只写内存并把 Cache 里那份标记为失效。

到了，这是本章计算题的第二个重仓。先记周期怎么定：把一个任务的执行过程分成 N 个阶段，流水线周期取的是各阶段中最长的那个时间。原文例题：一条指令的执行需要经历取指 2ms、分析 4ms、执行 1ms 三个阶段。所以流水线周期是 4ms，因为分析这一段最慢。

对，绝不是平均。然后是执行时间的通用公式：流水线执行时间等于第 1 条指令的执行时间加上，括号 n 减 1 括号，乘以流水线周期；n 代表需要处理的任务数量。它的道理是：除了第 1 个任务需要完整的时间外，其他都通过并行节省下了大量时间。

这里必须分理论与实践两种算法，考试特别爱在这挖坑。理论上，1 条指令的执行时间为 2ms 加 4ms 加 1ms 等于 7ms，所以理论流水线执行时间等于 2ms 加 4ms 加 1ms 再加，括号 100 减 1 括号，乘以 4，等于 403ms。

而实际上真正做流水线处理时，考虑到处理的复杂性，会将指令每个执行阶段的时间都统一为流水线周期，即 1 条指令的执行时间变成 4ms 加 4ms 加 4ms 等于 12ms，所以实际流水线执行时间等于 4ms 加 4ms 加 4ms 再加，括号 100 减 1 括号，乘以 4，等于 408ms。

原文的提示很明确：考试时 80% 以上的概率采用理论公式计算，所以需要以理论公式计算；若计算的结果无正确选项，才考虑采用实际公式计算。记成一句话——先算 403，选项里没有再试 408。

吞吐率 TP 是指在单位时间内流水线所完成的任务数量或输出的结果数量，有些文献也称为平均吞吐率、实际吞吐率；最基本的算法就是任务数除以执行时间。加速比是：完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比；如果不使用流水线即顺序执行所用的时间为 T0，使用流水线的执行时间为 Tk，那么加速比就是 T0 除以 Tk。

有，这个式子要能默写。设各流水段执行时间都相等为 Dt，则一条 k 段流水线完成 n 个连续任务所需要的时间为，括号 k 加 n 减 1 括号，乘 Dt；如果不使用流水线、顺序执行这 n 个任务，所需时间为 n 乘 k 乘 Dt。所以实际加速比就是 n 乘 k 乘 Dt，除以，括号 k 加 n 减 1 括号乘 Dt——上下的 Dt 可以约掉，剩下 nk 除以 k 加 n 减 1。

最后把全章必背过一遍，你回去照着默写一遍就够了。Cache 三种映射的标记位：直接映像 7 位只记区号、全相联 11 位记主存页号、组相联 8 位等于区号 7 位加组号 1 位；灵活性从低到高是直接、组相联、全相联；每组一页退化为直接映像，只分一组就是全相联；映射由硬件完成，对程序员透明。

流水线四件套：周期取最慢段等于 4ms；执行时间等于第一条指令时间加 n 减 1 乘周期，理论 403ms、实际 408ms，先用理论；吞吐率等于任务数除以执行时间；加速比等于 T0 除以 Tk，等长时为 nk 除以 k 加 n 减 1。再加三个小分：磁盘访问时间等于寻道加旋转延迟、扇区从 1 编号而磁头柱面从 0、写直达是同时写内存。

那就趁热去做，做完把错的那几道对回原文再听一遍对应段落。下一章我们讲操作系统，进程、死锁、内存管理，那边的计算题比这章还密。