第6章存储系统（层次化存储）

一、导读

1.1 本章学习目标

理解存储系统层次结构的设计原理：掌握从寄存器、Cache、主存到辅助存储器的层次化存储体系，理解局部性原理（时间局部性和空间局部性）如何支撑这一设计，以及层次化存储如何在性能、容量和成本之间取得最优平衡。

掌握 SRAM 与 DRAM 的工作原理与区别：深入了解静态随机存取存储器（SRAM）和动态随机存取存储器（DRAM）的内部结构、读写机制、性能特征和应用场景，理解为什么 SRAM 用于 Cache 而 DRAM 用于主存。

深入理解 Cache 的组织方式与映射策略：掌握直接映射、全相联映射和组相联映射三种 Cache 组织方式的原理和优缺点，理解 Cache 行的替换策略（LRU、FIFO、随机等）和写入策略（写直达、写回）。

掌握虚拟内存的工作机制：理解虚拟地址到物理地址的映射过程、页表的结构与多级页表的设计、TLB（Translation Lookaside Buffer）的作用和工作原理，以及页面置换算法（FIFO、LRU、OPT 等）的选择与性能影响。

能够分析存储系统的性能：掌握平均内存访问时间（AMAT）的计算方法，理解 Cache 命中率、缺失惩罚和缺失率对系统性能的影响，能够进行简单的存储系统性能优化分析。

理解存储系统对程序设计的影响：掌握缓存友好的编程技术，理解数据布局、访问模式对 Cache 性能的影响，能够编写高效的、充分利用存储层次结构的程序。

1.2 为什么本章如此重要

存储系统是计算机性能的关键决定因素之一。现代处理器每秒可以执行数十亿条指令，但每次运算都需要数据的支持。如果数据不能及时送达处理器，再快的 CPU 也只能空转等待。存储系统设计的核心目标就是确保处理器在任何时刻都能以尽可能低的延迟获得所需的数据和指令。

层次化存储结构是计算机科学中最成功的设计模式之一。它利用程序的局部性原理——程序在短期内倾向于重复访问相同的数据（时间局部性）和访问相邻的数据（空间局部性）——在 CPU 附近放置少量但极快的 Cache 存储器，将最近使用的数据从慢速的主存复制到 Cache 中。统计表明，典型的程序在任意时刻 90% 以上的内存访问都可以被 Cache 满足，这极大地减少了平均内存访问时间。

从系统设计的角度看，存储系统处于硬件和软件的交汇点。Cache 的一致性维护、虚拟内存的管理、页面置换算法的选择——这些问题既涉及硬件电路的设计，也涉及操作系统的策略。理解存储系统的工作原理，对于系统程序员编写高效的代码、操作系统开发者设计合理的内存管理策略都至关重要。

从性能优化的角度看，存储系统往往是程序性能的最大瓶颈。现代 CPU 的一个时钟周期约为 0.3 纳秒，而一次主存访问可能需要 100 纳秒。如果程序频繁发生 Cache 缺失，CPU 大部分时间都在等待内存数据。通过理解 Cache 的工作原理，程序员可以优化数据结构和访问模式，大幅减少 Cache 缺失，从而显著提升程序性能。这种优化往往比算法改进更有效。

1.3 核心问题引导

为什么计算机需要层次化的存储系统？能否只用一种既快又大又便宜的存储器？

SRAM 和 DRAM 在内部结构上有什么根本区别？为什么 SRAM 更快但更贵？

Cache 是如何利用局部性原理来提高内存访问速度的？命中率、缺失率和缺失惩罚之间是什么关系？

直接映射、全相联映射和组相联映射各有什么优缺点？为什么大多数现代 Cache 采用组相联映射？

虚拟内存解决了什么问题？页表和 TLB 在地址转换过程中分别扮演什么角色？

当物理内存不足时，操作系统如何选择哪些页面换出到磁盘？不同的页面置换算法有什么性能差异？

程序员如何编写缓存友好的代码？数据结构的布局如何影响 Cache 性能？

二、核心概念详解

2.1 存储层次结构

存储层次结构（Memory Hierarchy）是计算机系统中最基本的设计模式之一。它将存储设备按照速度、容量和单位成本排列成多个层次，形成从最快最小到最慢最大的金字塔结构。

最顶层是处理器内部的寄存器，访问速度与 CPU 时钟同步（约 0.3 纳秒），容量最小（几十个寄存器），但速度最快。第二层是 Cache 存储器，通常分为 L1、L2、L3 三级。L1 Cache 与 CPU 核心最紧密，访问延迟约 1-4 个时钟周期，容量通常为 32-64KB。L2 Cache 容量更大（256KB-1MB），延迟稍高（约 10 个周期）。L3 Cache 通常被多个核心共享，容量可达数 MB 到数十 MB。第三层是主存（DRAM），容量通常为数 GB 到数百 GB，访问延迟约 50-100 纳秒。最底层是辅助存储器（硬盘、SSD），容量可达数 TB，访问延迟在微秒到毫秒级别。

层次化存储的设计基于两个关键原理。首先是局部性原理（Principle of Locality）。时间局部性指最近被访问的数据很可能在近期再次被访问（如循环中的变量）。空间局部性指最近被访问的数据的邻近数据很可能很快被访问（如数组的顺序遍历）。利用局部性，Cache 可以将最近使用的数据保留在快速存储器中，减少对慢速存储器的访问。

其次是成本-性能权衡。快速存储器（如 SRAM）每个位的成本远高于慢速存储器（如 DRAM 或磁盘）。如果全部使用 SRAM，一个 16GB 的内存系统的成本将高得无法接受。层次化存储用少量快速存储器满足大部分访问需求，用大量慢速存储器提供足够的总容量，在成本和性能之间取得了最优平衡。

平均内存访问时间（Average Memory Access Time, AMAT）是衡量存储层次性能的关键指标。对于一个两级存储系统（Cache 和主存），AMAT = 命中时间 + 缺失率 x 缺失惩罚。其中命中时间是 Cache 的访问时间，缺失率是访问不在 Cache 中的比例，缺失惩罚是将数据从主存传送到 Cache 所需的时间。设计目标是最小化 AMAT。

2.2 SRAM 与 DRAM

SRAM（Static Random Access Memory，静态随机存取存储器）和 DRAM（Dynamic Random Access Memory，动态随机存取存储器）是两种主要的半导体存储器技术，它们在结构、性能和成本方面有显著差异。

SRAM 的每个存储单元由 6 个晶体管组成（6T 结构），形成两个交叉耦合的反相器（构成一个触发器）和两个访问晶体管。触发器可以无限期地保持状态，只要持续供电就不需要刷新。SRAM 的读写速度极快，访问延迟通常在 0.5-5 纳秒之间。但 6 个晶体管的单元面积较大，导致 SRAM 的存储密度低、单位成本高。SRAM 主要用于 Cache 存储器和高速缓冲区。

DRAM 的每个存储单元由 1 个晶体管和 1 个电容组成（1T1C 结构）。电容存储电荷来表示数据（充电表示 1，放电表示 0）。由于电容会自然漏电，DRAM 需要定期刷新（通常每 64 毫秒刷新一次所有行）来保持数据。DRAM 的访问延迟较高（约 50-100 纳秒），但单元面积小、密度高、成本低。DRAM 是主存的标准选择。

DRAM 的读写操作比 SRAM 复杂。读取时，字线（Word Line）被激活，选中一行的所有单元。单元电容通过位线（Bit Line）放电或充电，产生微小的电压变化。这个微小的电压变化需要由灵敏放大器（Sense Amplifier）检测并放大到标准逻辑电平。写入时，位线被驱动到目标电压，同时字线激活，将电荷写入电容。

DRAM 的技术进步主要体现在密度的提升和访问速度的改善。从 SDRAM 到 DDR SDRAM 再到 DDR4/DDR5，每一代都将数据传输速率提高一倍。DDR（Double Data Rate）技术在时钟的上升沿和下降沿都传输数据，实现了双倍的数据吞吐率。此外，多 Bank 结构和预充电技术允许在访问一行的同时预充电下一行，提高了访问效率。

2.3 Cache 组织与映射

Cache 是存储层次中最关键的层次，它直接决定了处理器获取数据的平均延迟。Cache 的基本工作原理是将主存划分为固定大小的块（Cache Line/Block，通常为 64 字节），将最近使用的内存块复制到 Cache 中。当 CPU 访问某个内存地址时，首先检查该地址对应的内存块是否在 Cache 中（Cache Hit），如果在则直接从 Cache 读取（命中），如果不在则从主存读取并放入 Cache（Cache Miss）。

Cache 映射策略决定了内存块可以放置在 Cache 的哪个位置。直接映射（Direct Mapping）中，每个内存块只能映射到 Cache 中唯一的一个位置（行）。映射关系为：Cache 行号 = 内存块号 mod Cache 总行数。直接映射的优点是查找简单——只需要比较标记位（Tag）即可确定是否命中，硬件实现简单、速度快。缺点是冲突率高——即使 Cache 中有很多空闲行，如果两个频繁使用的内存块映射到同一行，就会不断发生冲突替换（Thrashing）。

全相联映射（Fully Associative Mapping）中，任何内存块可以放置在 Cache 的任何位置。这种映射方式完全消除了冲突替换——只要 Cache 中有空闲行，就不会发生因冲突导致的缺失。但查找时需要同时比较所有 Cache 行的标记位，需要大量的比较器硬件，查找速度较慢，硬件成本高。

组相联映射（Set Associative Mapping）是直接映射和全相联映射的折中方案。Cache 被分为若干组（Set），每组包含 N 行（N 路组相联）。内存块首先映射到特定的组，然后可以在该组内的任意一行存放。映射关系为：组号 = 内存块号 mod 组数。N 路组相联的查找需要比较一组内 N 行的标记位。2 路组相联是最常见的选择，它在硬件复杂度和冲突率之间取得了良好的平衡。现代处理器的 L1 Cache 通常采用 4 路或 8 路组相联，L2/L3 Cache 采用更高的相联度。

Cache 的替换策略决定当 Cache 满时哪个块被替换出去。常见的替换策略包括：LRU（Least Recently Used，最近最少使用）替换最久未被访问的块，性能最好但实现复杂；FIFO（First In First Out，先进先出）替换最早进入 Cache 的块，实现简单但性能不如 LRU；随机替换（Random）随机选择一个块替换，实现最简单，性能介于 LRU 和 FIFO 之间。

2.4 虚拟内存

虚拟内存（Virtual Memory）是现代操作系统中最重要的内存管理机制之一。它为每个进程提供一个独立的、连续的地址空间（虚拟地址空间），通过地址映射机制将虚拟地址转换为物理地址。虚拟内存的核心优势包括：内存隔离——每个进程拥有独立的地址空间，不能访问其他进程的内存，提高了系统安全性和稳定性；内存扩展——虚拟地址空间可以远大于物理内存，当物理内存不足时，不活跃的页面被换出到磁盘（交换空间），需要时再换入。

地址转换的核心数据结构是页表（Page Table）。虚拟地址被分为两部分：虚拟页号（Virtual Page Number, VPN）和页内偏移（Page Offset）。页表以 VPN 为索引，查找对应的物理页帧号（Physical Frame Number, PFN）。物理地址由 PFN 和页内偏移拼接而成。页表中的每个条目（Page Table Entry, PTE）还包含有效位（Valid Bit，表示页面是否在物理内存中）、保护位（Protection Bits，表示读/写/执行权限）、_dirty 位（表示页面是否被修改过）等控制信息。

页表的访问本身需要内存读取，如果不加优化，每次内存访问都需要两次内存读取（一次查页表，一次访问数据），这将使内存访问延迟翻倍。TLB（Translation Lookaside Buffer，转译后备缓冲器）是解决这一问题的关键。TLB 是一个小型的、高速的 Cache，用于缓存最近的地址转换结果。当 CPU 产生虚拟地址时，首先在 TLB 中查找对应的物理地址（TLB Hit），如果命中则直接使用，无需访问页表。TLB 的命中率通常在 99% 以上，有效地消除了地址转换的额外开销。

多级页表是处理大型地址空间的有效方法。对于 64 位地址空间，如果使用单级页表，页表本身可能需要数 GB 的存储空间。多级页表将页表分层组织（如 x86-64 使用 4 级页表），只有实际使用的虚拟地址范围才需要分配对应的页表条目。这种按需分配的方式大大减少了页表的内存占用。

2.5 页面置换算法

当物理内存已满且需要加载新页面时，操作系统必须选择一个现有页面换出（如果该页面被修改过，还需要先写回磁盘）。页面置换算法的目标是最小化页面换入换出的总次数，从而减少磁盘 I/O 开销。

最优置换算法（OPT, Optimal）换出将来最长时间不会被访问的页面。OPT 算法产生最少的页面缺失，是理论上的最优解。但 OPT 需要预知未来的页面访问序列，在实际系统中无法实现，主要用于与其他算法的性能比较基准。

FIFO（First In First Out）算法换出最早进入内存的页面。FIFO 实现简单，使用一个队列即可。但 FIFO 不考虑页面的访问频率，可能换出频繁使用的页面。FIFO 还存在一个反直觉的现象——Belady 异常：在某些情况下，增加物理内存帧数反而会增加页面缺失次数。

LRU（Least Recently Used）算法换出最近最久未被访问的页面。LRU 试图近似 OPT 算法的行为，性能通常优于 FIFO。但 LRU 的精确实现需要记录每个页面的访问时间或使用栈结构，硬件开销较大。实际系统中通常使用 LRU 的近似实现，如时钟算法（Clock Algorithm）或使用引用位的 aging 算法。

工作集模型（Working Set Model）从另一个角度解决页面置换问题。它认为每个进程在一段时间内只活跃地访问一小部分页面（工作集）。操作系统为每个进程分配足够的内存帧来容纳其当前工作集，超出工作集的页面才被换出。工作集的大小通过观察最近的页面访问历史来估计。

三、深入分析与讨论

3.1 Cache 一致性问题

在多处理器系统中，每个处理器核心通常拥有自己的私有 L1 和 L2 Cache。当多个核心共享同一物理内存区域时，不同 Cache 中可能保存同一内存地址的不同副本，导致数据不一致。Cache 一致性协议（Cache Coherence Protocol）用于确保所有核心看到的内存值是一致的。

总线嗅探（Bus Snooping）是最基本的缓存一致性机制。每个 Cache 控制器监听（嗅探）共享总线上的所有内存操作。当一个核心写入某个地址时，其他核心检测到该写入操作，将自己 Cache 中对应地址的副本标记为无效。后续对这些地址的访问将触发 Cache 缺失，从内存或其他 Cache 获取最新值。

MESI 协议是最经典的缓存一致性协议。它为每个 Cache 行定义四种状态：Modified（已修改，只有本 Cache 持有且已修改）、Exclusive（独占，只有本 Cache 持有且未修改）、Shared（共享，多个 Cache 持有相同副本）、Invalid（无效）。通过状态之间的转换规则，MESI 协议保证了缓存一致性。现代处理器使用 MESI 的变体（如 MOESI、MESIF）来优化特定场景的性能。

伪共享（False Sharing）是缓存一致性带来的一个性能问题。当两个线程分别修改同一 Cache 行中的不同变量时，由于 Cache 行是 consistency 的基本单位，两个核心的 Cache 行会不断在 Modified 和 Shared 状态之间切换，导致大量的 Cache 一致性流量。解决方案是在数据结构中插入填充（Padding），确保不同线程访问的变量不在同一 Cache 行中。

3.2 存储技术的最新发展

非易失性存储器（Non-Volatile Memory, NVM）技术正在改变存储层次的结构。Intel Optane（基于 3D XPoint 技术）是一种介于 DRAM 和 NAND Flash 之间的存储介质，具有非易失性、接近 DRAM 的访问延迟和比 DRAM 更高的密度。NVM 的出现模糊了主存和存储之间的界限，可能催生新的存储层次结构。

HBM（High Bandwidth Memory）通过 3D 堆叠和宽总线接口提供极高的内存带宽。HBM 将多个 DRAM 芯片垂直堆叠，通过硅通孔（TSV）连接，总线宽度可达 1024 位。HBM 主要用于高性能计算和图形处理，其带宽是传统 DDR 内存的数倍。

近存计算（Near-Memory Computing）和存内计算（In-Memory Computing）是应对内存墙问题的新兴技术方向。近存计算将计算单元放置在靠近存储器的位置，减少数据搬运的开销。存内计算直接在存储器阵列中执行计算操作（如矩阵乘法），从根本上消除数据搬运。这些技术有望在未来显著改变存储系统的设计范式。

3.3 存储系统性能分析与优化

存储系统的性能分析通常使用 AMAT（Average Memory Access Time）模型。对于一个包含 L1 Cache、L2 Cache 和主存的三级存储系统：

AMAT = L1 命中时间 + L1 缺失率 x (L2 命中时间 + L2 缺失率 x 主存访问时间)

例如，如果 L1 命中时间为 1 周期，L1 缺失率为 5%，L2 命中时间为 10 周期，L2 缺失率为 20%，主存访问时间为 100 周期，则：

AMAT = 1 + 0.05 x (10 + 0.20 x 100) = 1 + 0.05 x 30 = 2.5 周期

性能优化可以从多个维度入手。降低缺失率：增大 Cache 容量、提高相联度、使用更好的替换策略。降低缺失惩罚：使用多级 Cache、提高内存带宽、使用预取技术。减少命中时间：减小 Cache 容量（L1 Cache 通常较小以保证速度）、使用流水线 Cache 访问。

四、实践案例

4.1 案例分析：数组遍历的 Cache 性能分析

考虑一个 1024 x 1024 的整数矩阵（每个整数 4 字节，总计 4MB）。假设 L1 Data Cache 为 32KB，Cache 行为 64 字节，采用直接映射。

按行遍历矩阵（C 语言默认存储顺序）：

for (int i = 0; i < 1024; i++)
  for (int j = 0; j < 1024; j++)
    sum += matrix[i][j];

每次内存访问读取 4 字节，但由于空间局部性，一个 Cache 行（64 字节）包含 16 个连续的整数。按行遍历时，访问 matrix[i][0] 会将 matrix[i][0] 到 matrix[i][15] 一起加载到 Cache。后续 15 次访问都命中 Cache。缺失率约为 1/16 = 6.25%。

按列遍历矩阵：

for (int j = 0; j < 1024; j++)
  for (int i = 0; i < 1024; i++)
    sum += matrix[i][j];

每次访问跳到下一行（间隔 4096 字节），每次都导致 Cache 缺失。缺失率为 100%。此外，由于直接映射的冲突，不同行的元素可能映射到同一 Cache 行，导致额外的冲突缺失。

这个案例清楚地展示了数据访问模式对 Cache 性能的巨大影响。按行遍历的缺失率（6.25%）远低于按列遍历（100%），性能差异可达数十倍。在实际编程中，应该始终按照数据的存储顺序进行遍历。

4.2 案例分析：虚拟内存与页面置换

假设一个系统有 4 个物理页帧（初始为空），页面访问序列为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。

使用 FIFO 置换算法：

访问 1：缺失，页帧 = [1]
访问 2：缺失，页帧 = [1, 2]
访问 3：缺失，页帧 = [1, 2, 3]
访问 4：缺失，页帧 = [1, 2, 3, 4]
访问 1：命中，页帧 = [1, 2, 3, 4]
访问 2：命中，页帧 = [1, 2, 3, 4]
访问 5：缺失，替换最旧的页 1，页帧 = [5, 2, 3, 4]
访问 1：缺失，替换最旧的页 2，页帧 = [5, 1, 3, 4]
访问 2：缺失，替换最旧的页 3，页帧 = [5, 1, 2, 4]
访问 3：缺失，替换最旧的页 4，页帧 = [5, 1, 2, 3]
访问 4：缺失，替换最旧的页 5，页帧 = [4, 1, 2, 3]
访问 5：缺失，替换最旧的页 1，页帧 = [4, 5, 2, 3]

FIFO 的缺失次数为 10 次，缺失率为 10/12 = 83.3%。

使用 LRU 置换算法：

访问 1-4：4 次缺失，页帧 = [1, 2, 3, 4]
访问 1：命中，最近使用顺序 = [2, 3, 4, 1]
访问 2：命中，最近使用顺序 = [3, 4, 1, 2]
访问 5：缺失，替换最久未用的 3，页帧 = [1, 2, 4, 5]
访问 1：命中
访问 2：命中
访问 3：缺失，替换最久未用的 4，页帧 = [1, 2, 5, 3]
访问 4：缺失，替换最久未用的 1，页帧 = [2, 5, 3, 4]
访问 5：命中

LRU 的缺失次数为 8 次，缺失率为 8/12 = 66.7%。LRU 的性能优于 FIFO。

五、常见误区与注意事项

5.1 误区一：Cache 越大一定越好

增大 Cache 容量确实可以降低缺失率，但也带来负面影响。更大的 Cache 意味着更长的访问延迟（因为信号需要在更大的阵列中传播），这可能增加命中时间。此外，更大的 Cache 消耗更多的芯片面积和功耗。对于 L1 Cache，命中时间对处理器时钟频率的影响很大，因此 L1 Cache 通常保持较小（32-64KB）以保证最快的访问速度。

5.2 误区二：组相联度越高越好

提高组相联度可以减少冲突缺失，但也增加了每次 Cache 访问的延迟（需要比较更多的标记位）和硬件复杂度。研究表明，2 路组相联已经能消除大部分冲突缺失，4 路组相联接近全相联的性能。超过 8 路的组相联带来的性能提升微乎其微，但硬件成本显著增加。

5.3 误区三：虚拟内存对程序员是透明的

虽然虚拟内存的大部分管理由操作系统自动完成，但程序员仍然需要了解虚拟内存的工作原理。内存映射文件、共享内存、大页（Huge Pages）等技术都需要程序员的理解和配合。此外，虚拟内存的页面切换（Thrashing）会严重影响程序性能，程序员需要通过合理的工作集控制来避免这种情况。

5.4 误区四：DRAM 不需要刷新

DRAM 使用电容存储数据，电容会自然漏电。如果不定期刷新，存储的数据会在几毫秒内丢失。DRAM 控制器每隔 64 毫秒（具体取决于芯片规格）必须刷新所有行。刷新期间，被刷新的 Bank 不可用于正常的读写操作。这是 DRAM 访问延迟高于 SRAM 的原因之一。

5.5 误区五：Cache 一致性只影响多处理器系统

即使在单处理器系统中，DMA（Direct Memory Access）设备与 CPU 共享内存时也会出现一致性问题。如果 DMA 设备修改了内存中的数据，而 CPU 的 Cache 中保存着旧的数据副本，CPU 读取到的将是过时的值。解决这个问题需要 Cache 一致性机制或软件显式地进行 Cache 维护操作。

六、本章小结

本章详细讲解了存储系统的层次结构和关键技术。存储层次利用局部性原理，通过多级缓存将快速但昂贵的存储器与慢速但廉价的存储器结合，在成本和性能之间取得最优平衡。SRAM 和 DRAM 各有特点，分别用于 Cache 和主存。Cache 的组织方式（直接映射、组相联、全相联）影响命中率和访问延迟，设计时需要在两者之间权衡。虚拟内存通过地址映射为每个进程提供独立的地址空间，TLB 加速地址转换，页面置换算法管理物理内存的分配。存储系统的性能由 AMAT 衡量，程序员可以通过理解 Cache 工作原理来编写缓存友好的代码，显著提升程序性能。多处理器环境下的 Cache 一致性和新兴存储技术是当前研究的热点方向。

七、思考题与练习

请解释局部性原理的含义，并分别给出时间局部性和空间局部性的编程实例。如何利用局部性原理来优化程序性能？

比较 SRAM 和 DRAM 的存储单元结构。为什么 SRAM 的访问速度更快但成本更高？为什么 DRAM 需要刷新而 SRAM 不需要？

一个直接映射 Cache 有 64 行，Cache 行为 16 字节。主存地址为 0x0000 到 0xFFFF。请计算地址中标记（Tag）、行号（Index）和块内偏移（Offset）各占多少位。

比较直接映射、全相联映射和组相联映射的优缺点。为什么大多数现代处理器的 L1 Cache 采用 4 路或 8 路组相联而不是全相联？

一个三级存储系统的参数如下：L1 命中时间 1 周期，L1 缺失率 5%；L2 命中时间 5 周期，L2 全局缺失率 1%；主存访问时间 50 周期。请计算 AMAT。

解释 TLB 的工作原理。如果 TLB 缺失，会发生什么？多级页表如何减少页表的内存占用？

比较 FIFO、LRU 和 OPT 三种页面置换算法的性能。为什么 LRU 在实际系统中通常使用近似实现？时钟算法是如何近似 LRU 的？

以下两段代码遍历同一个二维数组，请分析它们的 Cache 性能差异并解释原因。如何修改第二段代码使其 Cache 性能接近第一段？

```c

// 代码 A

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

a[i][j] = 0;

// 代码 B