第一章 计算机系统漫游1.处理器读并解释储存在内存中的指令1.硬件组成3.主存主存是一个临时存储设备在处理器执行程序时用来存放程序和程序处理的数据。从物理上来说主存是由一组动态随机存取存储器(DRAM)芯片组成的。从逻辑上来说存储 器是一个线性的字节数组每个字节都有其唯一的地址(数组索引),这些地址是从零开始 的。一般来说组成程序的每条机器指令都由不同数量的字节构成。与C程序变量相对应的数据项的大小是根据类型变化的。比如在运行Linux的x86-64机器上short类型的数据需要2个字节int和float类型需要4个字节而long和double类型需要8个字节。4.处理器中央处理单元(CPU),简称处理器是解释(或执行)存储在主存中指令的引擎。处理 器的核心是一个大小为一个字的存储设备(或寄存器),称为程序计数器(P C) 。在任何时 刻 PC 都指向主存中的某条机器语言指令(即含有该条指令的地址)。从系统通电开始直到系统断电处理器一直在不断地执行程序计数器指向的指令再更新程序计数器使其指向下一条指令。处理器看上去是按照一个非常简单的指令执行模型来操作的这个模型是 由指令集架构决定的。在这个模型中指令按照严格的顺序执行而执行一条指令包含执行一系列的步骤。处理器从程序计数器指向的内存处读取指令解释指令中的位执行该指令指示的简单操作然后更新 PC, 使其指向下 一 条指令而这条指令并不 一 定和在内存中刚刚执行的指令相邻。这样的简单操作并不多它们围绕着主存、 寄存器文件(registerfile)和算术/逻辑单元(ALU)进行。寄存器文件是一个小的存储设备由一些单个字长的寄存器组成每个寄存器都有唯一的名字。ALU计算新的数据和地址值。下面是一些简单操作的例子CPU在指令的要求下可能会执行这些操作。●加载从主存复制一个字节或者一个字到寄存器以覆盖寄存器原来的内容。●存储从寄存器复制一个字节或者一个字到主存的某个位置以覆盖这个位置上原来的内容。●操作把两个寄存器的内容复制到ALU,ALU 对这两个字做算术运算并将结果存放到一个寄存器中以覆盖该寄存器中原来的内容。●跳转从指令本身中抽取一个字并将这个字复制到程序计数器(PC) 中以覆盖PC中原来的值。处理器看上去是它的指令集架构的简单实现但是实际上现代处理器使用了非常复杂的机制来加速程序的执行。2.运行程序初始时shell程序执行它的指令等待我们输入一个命令。当我们在键盘上输入字符串“./hello后shell程序将字符逐一读入寄存器再把它存放到内存中当我们在键盘上敲回车键时shell 程序就知道我们已经结束了命令的输入。然后 shell 执行一系列指令来加载可执行的hello 文件这些指令将hello 目标文件中的代码 和数据从磁盘复制到主存。数据包括最终会被输出的字符串 “hello,world\n”。 利用直接存储器存取(DMA, 将在第6章中讨论)技术数据可以不通过处理器而直 接 从 磁 盘 到 达 主 存 。一旦目标文件hello中的代码和数据被加载到主存处理器就开始执行hello程序的 main程序中的机器语言指令。这些指令将“hello,world\n”字符 串 中 的字节从主存复制到寄存器文件再从寄存器文件中复制到显示设备最终显示在屏幕上。2.高速缓存至关重要1.数据复制带来的系统开销问题这个简单的示例揭示了一个重要的问题即系统花费了大量的时间把信息从一个地方挪到另一个地方。hello 程序的机器指令最初是存放在磁盘上当程序加载时它们被复制到主存当处理器运行程序时指令又从主存复制到处理器。相似地数据串 “hello,world/n” 开始时在磁盘上然后被复制到主存最后从主存上复制到显示设备。从程序员的角度来看这些复制就是开销减慢了程序 “真正” 的工作。因此系统设计者的一个主要目标就是使这些复制操作尽可能快地完成。2.存储设备的容量与速度矛盾根据机械原理较大的存储设备要比较小的存储设备运行得慢而快速设备的造价远高于同类的低速设备。比如说一个典型系统上的磁盘驱动器可能比主存大 1000 倍但是对处理器而言从磁盘驱动器上读取一个字的时间开销要比从主存中读取的开销大 1000 万倍。3.处理器与主存的速度差距持续扩大类似地一个典型的寄存器文件只存储几百字节的信息而主存里可存放几十亿字节。然而处理器从寄存器文件中读数据比从主存中读取几乎要快 100 倍。更麻烦的是随着这些年半导体技术的进步这种处理器与主存之间的差距还在持续增大。加快处理器的运行速度比加快主存的运行速度要容易和便宜得多。4.高速缓存存储器的解决方案针对这种处理器与主存之间的差异系统设计者采用了更小更快的存储设备称为高速缓存存储器 (cache memory, 简称为 cache 或高速缓存)作为暂时的集结区域存放处理器近期可能会需要的信息。图 1-8 展示了一个典型系统中的高速缓存存储器。位于处理器芯片上的 L1 高速缓存的容量可以达到数万字节访问速度几乎和访问寄存器文件一样快。一个容量为数十万到数百万字节的更大的 L2 高速缓存通过一条特殊的总线连接到处理器。进程访问 L2 高速缓存的时间要比访问 L1 高速缓存的时间长 5 倍但是这仍然比访问主存的时间快 510 倍。5.高速缓存的实现与多级结构L1 和 L2 高速缓存是用一种叫做静态随机访问存储器 (SRAM) 的硬件技术实现的。比较新的、处理能力更强大的系统甚至有三级高速缓存L1、L2 和 L3。系统可以获得一个很大的存储器同时访问速度也很快原因是利用了高速缓存的局部性原理即程序具有访问局部区域里的数据和代码的趋势。通过让高速缓存里存放可能经常访问的数据大部分的内存操作都能在快速的高速缓存中完成。3.存储设备形成层次结构处理器和一个较大较慢的设备(例如主存)之间插入一个更小更快的存储设备(例如高速缓存)的想法已经成为一个普遍的观念。实际上每个计算机系统中的存储设备都被组织成了一个存储器层次结构如图1-9所示。在这个层次结构中从上至下设备的访问速度越来越慢、容量越来越大并且每字节的造价也越来越便宜。寄存器文件在层次结构中位于最顶部也就是第0级或记为L0。存储器层次结构的主要思想是上一层的存储器作为低一层存储器的高速缓存。因此寄存器文件就是L1的高速缓存L1是L2的高速缓存L2是L3的高速缓存L3是主存的高速缓存而主存又是磁盘的高速缓存。在某些具有分布式文件系统的网络系统中本地磁盘就是存储在其他系统中磁盘上的数据的高速缓存。正如可以运用不同的高速缓存的知识来提高程序性能一样程序员同样可以利用对整个存储器层次结构的理解来提高程序性能。第6章将更详细地讨论这个问题。4.系统之间利用网络通实际上现代系统经常通过网络和其他系统连接到一起。从一个单独的系统来看网络可视为一个I/O设备如图1-14所示。当系统从主存复制一串字节到网络适配器时数据流经过网络 到达另一台机器而不是比如说到达本地磁盘驱动器。相似地系统可以读取从其他机器发送来的数据并把数据复制到自己的主存。回到hello示例我们可以使用熟悉的telnet应用在一个远程主机上运行hello程序。假设用本地主机上的telnet客户端连接远程主机上的telnet服务器。在我们登录到远程主机并运行shell后远端的shell就在等待接收输入命令。此后在远端运行hello程序包括如图1-15所示的五个基本步骤。当我们在 telnet 客户端键入 “hello” 字符串并敲下回车键后客户端软件就会将这 个字符串发送到 telnet 的服务器。telnet 服务器从网络上接收到这个字符串后会把它传 递给远端 shell 程序。接下来远端 shell 运行 hello 程序并将输出行返回给telnet 服务 器。最后telnet 服务器通过网络把输出串转发给 telnet 客户端客户端就将输出串输出 到 我 们 的 本 地 终 端 上 。5.Amdahl 定律Amdahl 定律是计算机系统里的一个重要规律它帮我们回答一个问题我只优化了系统里的某一部分整个系统能变快多少核心思想系统整体性能的提升不只取决于你优化的那部分有多快还取决于这部分在整个系统里占多大比例。只优化一小部分哪怕优化得再狠整体提速也有限想让系统显著变快必须优化占比很大的部分。符号先搞懂​优化前整个系统跑程序需要的总时间你要优化的那部分在总时间里占的比例k这部分被加速的倍数​优化后整个系统需要的总时间S系统整体的加速比原来的总时间分成两部分没优化的部分占比 1−时间还是优化的部分原来占现在变快 k 倍时间变成所以(1-)算加速比 S加速比 原来时间 ÷ 现在时间S举个例子考虑这样一种情况系统的某个部分初始耗时比例为60%(α0.6),其加速比例因子为3(k3)。则我们可以获得的加速比为1/[0.40.6/3]1.67倍。虽然我们对系统的一个主要部分做出了重大改进但是获得的系统加速比却明显小于这部分的加速比。这就是Amdahl定律的主要观点——要想显著加速整个系统必须提升全系统中相当大的部分的速度。你把某一部分提速 3 倍但整个系统只快了 1.67 倍因为剩下 40% 的部分完全没优化拖了后腿这就是 Amdahl 定律的 “扎心” 结论只优化局部整体提升有限怎么表示性能提升推荐用「倍数」比如S2.2就说 “性能提升 2.2×”读作 “2.2 倍”清晰、无歧义一眼就知道变快了多少不推荐用「百分比」比如 “性能提升 120%”到底是100*(-)/还是100*(-)/定义模糊大变化时也不好理解不如倍数直观. 核心结论局部优化的天花板很低哪怕你把某部分优化到无限快k→∞系统最大加速比也只有想显著提速必须优化占比大的部分优化的部分在系统里占比越高整体提速才越明显用倍数表示性能最清晰别用百分比直接说 “X 倍”第二章 信息表示和处理1.信息存储1.内存的基本单位与虚拟内存核心知识点最小可寻址单位字节byte大多数计算机用 8 位bit 组成一个字节byte这是内存里最小的可寻址单位。你不能直接去访问内存里单独的某一位只能以「字节」为单位读写。虚拟内存机器视角的大字节数组机器级程序比如编译后的二进制代码会把内存看成一个非常大的字节数组这个数组就叫虚拟内存virtual memory。每个字节都有一个唯一的数字标识这个数字就是地址address。所有可能的地址合在一起就是虚拟地址空间virtual address space。虚拟 vs 实际概念性映像虚拟地址空间只是给机器级程序看的「概念性映像」并不是真实的物理内存。实际实现第 9 章会讲是把 DRAM动态随机访问存储器就是我们常说的内存、闪存、磁盘、特殊硬件 操作系统 组合起来让程序觉得自己在用一个连续、统一的大字节数组。2.程序对象与指针的本质核心知识点存储器空间的管理编译器和运行时系统会把存储器空间划分成更易管理的单元用来存放不同的程序对象program object程序数据比如变量、数组指令比如函数代码控制信息比如函数调用栈这些分配和管理的操作完全在虚拟地址空间里完成程序不需要关心物理内存的细节。C 语言指针的本质一个指针的值就是某个存储块第一个字节的虚拟地址不管它指向整数、结构体还是其他程序对象。C 编译器会把指针和它的类型信息绑定在一起比如int *、struct A *。编译器会根据指针类型生成不同的机器级代码去访问指针指向位置的值比如int类型要读 4 字节char类型读 1 字节。机器级程序的特点虽然 C 编译器维护着类型信息但最终生成的机器级程序本身并不包含数据类型信息。所以每个程序对象都可以简单看成一个字节块而程序本身就是一个字节序列一串连续的字节。计算机以字节为最小内存单位机器程序看到的是「虚拟内存」这个大字节数组每个字节有唯一地址。编译器在虚拟地址空间里管理程序对象C 指针本质是字节地址编译器靠类型信息生成访问代码但最终机器码里没有类型只有字节序列。2.字数据大小1.字长与虚拟地址空间1. 字长是什么字长指针数据的标称大小决定了虚拟地址的编码长度。对于字长为 w位的机器虚拟地址范围0~程序最多能访问个字节的内存空间3. 向后兼容与编译选项64 位机器可以运行 32 位程序向后兼容编译指令示例gcc -m32 prog.c编译为 32 位程序可在 32/64 位机器运行gcc -m64 prog.c编译为 64 位程序只能在 64 位机器运行32 位程序 / 64 位程序区别在于编译方式不是运行的机器类型个人理解:虚拟地址空间最大的意思并不是内存的最大 也不是磁盘的最大 而是一个进程的最大内存2 位 vs 64 位字长迁移32 位字长虚拟地址空间最大为 4 GB()也就是64 位字长虚拟地址空间扩展到 16 EB(约)也就是迁移历程先在高端科学 / 数据库机器 → 台式机 / 笔记本 → 智能手机向后兼容与编译选项64 位机器可以运行 32 位程序向后兼容编译指令示例gcc -m32 prog.c编译为 32 位程序可在 32/64 位机器运行gcc -m64 prog.c编译为 64 位程序只能在 64 位机器运行32 位程序 / 64 位程序区别在于编译方式不是运行的机器类型3.C 语言数据类型的字节大小char固定 1 字节可存字符或整数int通常固定 4 字节即使 64 位系统long32 位程序 4 字节64 位程序 8 字节指针大小等于字长32 位 4 字节64 位 8 字节float单精度浮点数4 字节double双精度浮点数8 字节固定大小整数类型ISO C99为避免依赖 “典型大小”引入 int32_t / uint32_t / int64_t / uint64_t特点字节数固定不随编译器 / 机器变化作用让程序员精准控制数据表示提升可移植性char 的符号性特殊点C 标准不保证 char 默认是有符号还是无符号要确保 1 字节有符号数必须写 signed char实际开发中多数编译器将 char 视为有符号数但依赖这个行为不安全C 语言允许关键字顺序 / 可选关键字省略以下写法等价unsigned long unsigned long int long unsigned long unsigned int可移植性要求程序员应让程序在不同机器 / 编译器上都能运行核心是对数据类型确切大小不敏感。C 标准的范围约束C 标准只规定了数据类型的数字范围下界没有上界这导致不同机器 / 编译器的字节大小可能不同历史遗留问题1980-2010 年32 位机器 32 位程序是主流很多代码假设 int4字节、指针4字节64 位机器普及后这些假设暴露问题典型错误用 int 存储指针32 位机器int4字节指针 4 字节 → 正常工作64 位机器int4字节指针 8 字节 → 数据截断程序出错4.字节和字长的区别字节Byte是计算机里固定不变的最小存储单位1 字节 8 位bit。字长Word Size是 CPU 一次能处理 / 传输的二进制位数由硬件架构决定常见 32 位 / 64 位。字长决定虚拟地址空间大小字节同时也决定了cpu一次能处理多少位的数据Example:32位机器决定了两件事 一件事cpu可以处理4字节(32/8)的东西其次 虚拟地址空间的最大值是2^32字节为什么地址空间是字节而不是 w 字节地址是 w位二进制能表示个不同的地址编号每个地址编号对应 1 字节 的内存所以总空间 个地址 × 1 字节 / 地址 字节地址只和字长挂钩比如32位机器 地址的大小就是32/84字节64位机器地址的大小就是64/88字节1 字节 8 位bit这个是固定的为什么地址要和字长挂钩?因为地址是 CPU 自己要用的必须跟 CPU 的字长一样宽其他数据是给程序用的CPU 可以分批处理不需要跟字长一样。地址是给 CPU 读内存用的不是给程序逻辑用的。CPU 从内存取数据时要做这一步把 地址 放到地址总线上 → 找到内存位置地址总线有多宽地址就必须是多少位。地址总线宽度 CPU 字长。所以32 位 CPU → 地址总线 32 位 → 地址必须 32 位64 位 CPU → 地址总线 64 位 → 地址必须 64 位地址必须一次性完整传给 CPU不能拆两半。所以地址必须跟字长一样宽。