Computer System

通读 CSAPP 是入门 CS 的最好路径

本书的结构:第 1 章概述计算机系统;第 2 至 6 章介绍程序与系统硬件的关系;第 7 至 9 章介绍程序与系统软件的关系;第 10 至 12 章介绍程序与其他程序的关系。

1. 计算机系统漫游

源程序是一个由 1 和 0 组成的比特(位)序列。8 个比特是一个字节,即程序中的一个文本字符。系统中所有的信息都是由比特序列组成的,但相同的比特序列在不同的上下文中有不同的含义,如数据或指令。程序可以被其他程序翻译成不同的格式:源程序(文本)通过编译系统变成可执行目标程序(二进制)。

总线是贯穿整个系统的电子管道,负责在系统部件(处理器、主存和 I/O 设备)之间传递字节。总线所携带的字节数是一个基本的系统参数,通常是 4 个字节或 8 个字节,分别代表 32 位系统和 64 位系统。

程序的运行本质上是处理器读取并解释指令的过程,其中最耗时的是信息在处理器和主存之间的复制开销。提高程序性能的关键是将上层存储器(容量小、速度快、成本高)作为下层存储器(容量大、速度慢、成本低)的高速缓存,进而形成一个存储器层次结构:寄存器 → 高速缓存 → 主存 → 本地磁盘 → 远程磁盘。

计算机系统是由硬件和软件组成的,它们共同工作来运行应用程序。操作系统是应用程序和硬件之间的系统软件,应用程序对硬件的操作必须通过操作系统,这是借助操作系统的几个基本抽象来实现的:文件、虚拟内存和进程。

抽象是计算机科学中重要的概念。操作系统内核提供 3 个基本的抽象:将 I/O 设备抽象为文件;将存储器(主存和 I/O 设备)抽象为虚拟内存;将程序(处理器、主存和 I/O 设备)抽象为进程。此外,指令集架构提供了对实际处理器硬件的抽象;虚拟机提供了对整个计算机的抽象。

系统之间通过网络连接在一起,并相互进行通信。对一个系统来说,网络可以被视为 I/O 设备:经由网络适配器,一台主机的信息可以从主存复制到另一台主机的主存中。各种网络应用的本质都是基于网络复制信息。

Amdahl 定律描述了改善任何过程的一般原则:想要显著的加速整个系统,必须提升系统中相当大的部门的速度。在计算机系统中,如果处理器能做的更多更快,系统性能就能得到显著提升。我们用并发(concurrency)来描述系统同时具有多个活动,用并行(parallelism)来描述系统因为并发而运行得更快。

2. 信息的表示和处理

字节是内存中最小的可寻址单元。机器级程序将内存视为字节数组,每个字节的标识被称为虚拟地址。C 程序用指针来表示某个对象的位置,指针的值就是某个字节块的第一个字节的虚拟地址。

数字是通过有限数量的位来进行编码的。由于编码长度的限制,整数运算和浮点运算可能会因为超出表示范围而引起数值溢出。整数的表示是精确的,但只能编码较小的数值范围;浮点数的表示是近似的,但可以编码较大的数值范围。

3. 程序的机器级表示

高级语言通过抽象隐藏了机器级操作的实现细节,如数据读写、数据处理、内存管理和网络通信。高级语言通常具有执行代码的运行时(runtime)。如果源代码在执行前全部被翻译为机器码则被称为静态编译,如果源代码是边翻译边执行则被称为动态解释。后者如果使用即时编译(JIT)的方法则可提高解释器的性能。

过程是一种代码封装的抽象机制。它通过一组参数和一个返回值实现某种功能,并可以在程序的其他地方调用。过程隐藏了行为实现,提供了接口定义。过程的形式包括函数(function)、方法(method)、子例程(subroutine)和处理函数(handler)等。

过程机制的关键在于传递控制和数据,分配和释放内存。运行时栈被划分为栈帧,当前正在执行的过程位于栈顶,调用链的其他过程被暂时挂起。每个过程调用都具有自己的私有状态信息的存储空间:过程在调用时,栈为其分配新的空间;过程在返回时,栈会释放这些空间。

4. 处理器体系结构

处理器所支持的指令及其字节级编码被称为它的指令集体系结构(ISA),ISA 为处理器设计者和编译器编写者提供了一个抽象概念层。每条指令都存在依次进行的多个阶段。借助流水线的不同阶段并行化,在任意时刻可以有多条指令被同时处理。流水线化提高了系统的吞吐量(单位时间内处理的指令数目),但也增加了延迟(单条指令的处理时间)。

5. 优化程序性能

优化程序性能有一些基本策略。高级设计方面,为遇到的问题选择合适的算法和数据结构。基本编码方面,消除连续的函数调用(尽可能将计算移到循环外);避免不必要的内存引用(引入临时变量来保存中间结果)。低级优化方面,通过展开循环降低开销;寻找方法提高指令级并行;使用条件数据传送代替条件控制转移(如三元赋值代替分支逻辑)。

6. 存储器层次结构

在存储器的命名上,memory 通常泛指内存,storage 通常泛指硬盘。不同存储技术的访问速度各不相同,由此催生了存储器的层次结构。比高速缓存(SRAM)缓解了寄存器和主存(DRAM)之间的速度差距,而固态硬盘缓解了主存和旋转磁盘之间的速度差距。

K、M、G 和 T 等前缀的含义依赖于上下文。与 RAM 相关的容量单位是二进制,如 1K = 1024;与 ROM 或 网络相关的容量单位是十进制,如 1K = 1000。但相同前缀的不同进制表述所代表的容量差别并不大。

存储器层次结构的中心思想是缓存(cache):上层结构缓存下层结构的数据对象,即第 k 层更快更小的存储设备作为第 k+1 层更慢更大的存储设备的缓存。缓存管理的主要逻辑是划分块和传送块,块是一些数据对象的集合,是相邻层次中相同大小的描述单元:第 k-1 层和第 k 层之间的块划分要比第 k 层和第 k+1 层之间的块划分要小,即上层所缓存的对象实质上是下层的块的子集的副本。

当程序需要第 k+1 层的某个数据对象 d 时,会先在第 k 层进行查找。若能找到则直接在第 k 层读取,这被称为缓存命中(hit)。若不能找到,即缓存未命中(miss),则第 k 层就将第 k+1 层中包含 d 的块复制过来,然后再从第 k 层中读取 d。复制块的时候存在两种情况:若第 k 层缓存未满,就执行放置策略(place),若第 k 层缓存已满,就执行替换策略(replace)。

系统中缓存的使用十分普遍,并且缓存机制通常是自动运行的。浏览器缓存是由浏览器管理的,它将资源缓存到本地客户端的磁盘;web 缓存是由代理管理的,它将资源缓存到远程服务器的磁盘。命中率用来衡量缓存性能,对于低层级的存储器来说,缓存未命中带来的复制成本较高,需要设计更好的放置策略和替换策略。

局部性(locality)是一种倾向性,倾向于再次访问曾被引用的内存位置被称为时间局部性;倾向于访问曾被引用的内存位置附近的内存位置被称为空间局部性。读取某个数据对象时,若未命中就会被缓存下来从而提高之后对它的访问速度,这体现了时间局部性;被缓存的块中存在多个数据对象,当访问其他对象时也会因为命中而补偿复制这个块的开销,这体现了空间局部性。

在加载(从内存读到寄存器)和存储(从寄存器写到内存)的总次数相同的情况下,提高核心函数中循环语句的缓存命中率,可以将大部分的数据访问从内存迁移至寄存器,从而加快速度。反复引用已使用的局部变量可以迎合时间局部性;采用步长为 1 的顺序引用模式可以迎合空间局部性。

7. 链接

链接是将各种代码和数据片段收集并组合成为一个单一文件的过程,该文件可以被加载(复制)到内存并执行。链接过程可以处于编译时(compile time)、或者在加载时(load time),甚至在运行时(run time)。相比静态链接,动态链接通过让多个进程共享内存中的共享库代码,节约了内存资源。

8. 异常控制流

通常来说,如果地址相邻的指令序列会平滑的进行过渡,这种控制转移序列被称为控制流(control flow)。跳转、调用和返回等指令会造成平滑流的突变,即发生了前后两个指令的地址不相邻的情况,被称为异常控制流。

在硬件层,异常(exception)就是控制流中的突变,用来响应处理器状态的某些变化。具体来说,状态的变化被称为事件(event),会触发一个从应用程序到异常处理程序(handler)的突发的控制转移。当异常处理程序完成处理后,会根据引起异常的事件类型,将控制返回给程序,或者将程序终止。

如果异常是来自处理器外部的 I/O 设备的信号,则被称为异步异常(中断)。I/O 设备包括网络适配器、磁盘控制器和定时芯片等。中断(interrupt)是指在当前指令的执行过程中,I/O 设备向处理器芯片的中断引脚发信号,处理器会在当前指令执行之后,注意到中断引脚的电压升高,然后就调用中断处理程序,并最终返回到下一条指令。

如果异常是因为执行当前的指令而发生的,则被称为同步异常(陷阱、故障和终止)。陷阱(trap)是故意的异常,会提供一个系统调用,并最终返回到下一条指令;故障(fault)是可能恢复的错误,如果成功恢复就返回到当前出错的指令,如果没有恢复就终止程序;终止(abort)是不能恢复的错误,会终止程序。

在操作系统层,进程(process)是在异常的基础上构建的抽象。进程是一个执行中的程序的实例,程序运行在上下文中,上下文是程序运行所需要的状态。内核通过上下文切换来实现进程间的调度,从而实现多任务:保存当前进程的上下文,恢复之前进程的上下文,将控制传递给新恢复的进程。进程通常运行在用户模式,而在上下文切换时将运行在内核模式。

进程轮流使用处理器,但独立的逻辑流提供了这种假象:每个进程独占处理器。逻辑流如果在时间上有重叠(即使没有运行在同一个处理器或计算机上),就称为并发(concurrency)。如果两个流既是并发流又运行在不同的处理器或计算机上,就称为并行(parallel)。

进程共享内存系统,但私有的地址空间提供了这种假象:每个进程独占内存系统。每个私有的地址空间所关联的内容具有通用的地址结构,即用户程序的虚拟内存和内核的虚拟内存。二者均包含了只读的代码区域、可读写的数据区域、运行时堆区域、用户栈区域和共享库区域。

进程具有三种状态:运行、停止和终止。理解程序和进程的关系很重要:程序是一堆代码和数据,可以作为目标文件存在于磁盘上,或者作为段存在于地址空间中,进程是执行中程序的一个具体实例,程序总是运行在某个进程的上下文中。fork 函数是在新的进程中运行相同的程序,execve 函数式在当前进程中运行相同的程序。前者具有独立的地址空间,而后者会覆盖旧的地址空间。

此外,信号(signal)允许进程和内核中断其他进程。系统中发生某类型的事件时,信号可以通知进程,或者说进程可以捕获到信号。另外,非本地跳转可以规避正常的调用/返回栈规则,允许直接从一个函数分支到另一个函数,这在高级语言中通常用 try/catch/throw 来封装。

9. 虚拟内存

虚拟内存可以用于磁盘缓存。它本质上是主存和磁盘之间的缓存机制:物理内存缓存在主存上,虚拟内存存储在磁盘上。磁盘和内存之间传送块(页)的活动叫做交换(swap)。尽管程序在整个运行过程的总页数会超过主存大小,但局部性原则保证了任意时刻的活动页将趋向于一个小的工作集。程序运行的初始开销(将工作集调度到主存)之后,后续的引用命中将避免产生额外的磁盘流量。

虚拟内存可以用于内存管理。虚拟内存采用按需页面调度的策略:直到发生未命中,才会将页面拷贝至主存。虚拟内存简化了代码和数据共享:不同进程的虚拟页可以映射到相同的物理页。虚拟内存简化了内存分配:当运行在用户进程中的程序需要额外的堆空间时,系统会为其分配几个连续位置的虚拟页,并将这几个虚拟页随机的映射到任意位置的物理页。

虚拟内存可以用于内存保护。虚拟内存为每个进程提供独立的虚拟地址空间,从而区分不同进程的私有内存。每个进程的虚拟页都有控制读写访问的许可位,违反许可条件的指令将触发一个保护性故障,并将故障传递给内核的异常处理程序。这种异常被称为段错误(segment fault)。

虚拟内存的大小由磁盘的交换空间决定。针对一个进程的虚拟地址空间,除了按具体类型划分(代码、数据、堆、栈和共享库),也可以按缓存情况划分(未分配、已分配但未缓存,以及已分配且已缓存)。

地址翻译是指将虚拟地址转换为物理地址。内存映射是指将磁盘上的对象与虚拟内存区域关联起来,从而实现虚拟页的初始化。

动态内存分配器用来管理一个进程虚拟内存的堆(heap)区域。动态内存分配的主要原因是一些数据结构的大小直到实际运行时才能确定,比如大小依赖于输入的时候。分配器将堆视为一组块,包括已分配的和未分配的。显式分配器要求应用显式的释放已分配的块,隐式分配器则自动的释放已分配的块,这些块是未被引用的数据对象。

10. 系统级 I/O

I/O 是指主存和外部设备之间复制数据的过程:输入操作是从 I/O 设备复制数据到主存,输出操作是从主存复制数据到 I/O 设备。所有的 I/O 设备(网络、磁盘和终端等)都被抽象为文件,并由内核提供的统一 I/O 接口进行操作,比如文件的打开、关闭、读、写、位置更改、提取元数据,以及的 I/O 重定向。

打开的文件被抽象为流(stream)。shell 创建的进程默认具有 3 个已打开的文件:标准输入、标准输出和标准错误。内存与文件之间的数据传送通常是网络 I/O 或者磁盘 I/O,这些操作通常开销很大。通过在内存和文件之间引入读写缓冲(buffer),可以在必要时才进行实际的 I/O 操作,从而减少 I/O 次数。

每个文件都有一个类型:普通文件、目录、套接字、命名管道、符号链接,以及字符和块设备。普通文件包括了二进制文件(binary file)和文本文件(text file)。文本文件是只含有 ASCII 字符或 Unicode 字符,并被换行符分隔为文本行,其他文件都属于二进制文件,尽管对内核来说二者并无区别。套接字负责与另一个进程进行跨网络通信。

目录是一组链接的集合,链接将文件名(filename)映射到文件或目录。每个目录至少包含两个链接:到目录自身的链接和到其父目录的链接。内核将所有文件组织为文件层次结构,除了叶节点是具体文件,其他节点均是目录。文件的位置由路径名(pathname)来指定:绝对路径的定位起点是层次结构的根目录,相对路径的定位起点是进程的当前工作目录。

11. 网络编程

网络应用基于 client-server 模型。client 和 server 是进程而非主机,因此二者可以运行在同一台主机上。server 管理资源,并为 client 提供服务。模型的基本操作是事务:发送请求,处理请求,发送响应,处理响应。

对主机而言,网络只是一种 I/O 设备。硬件上,低级网络设备将主机连接为局域网,高级网络设备连接局域网和广域网,并构建为互联网络。软件上,主机和路由器上的软件协议负责消除网络之间的差异,从而实现主机之间的通信。

Internet 是最成功的互联网络实现。借助 TCP/IP 协议族,因特网被映射为主机集合,主机被映射为 IP 地址,而 IP 地址通过 DNS 被映射为域名。最终,主机上的进程可以通过连接(connection)和任何其他主机上的进程通信。连接的特点是:点对点,全双工,可靠的。连接的端点是套接字(socket),网络应用借助 socket interface 函数和 Unix I/O 函数构建。

套接字地址是 IP 地址和端口号的组合。两个进程所构成的连接由 client 套接字地址和 server 套接字地址共同标识。client 端口号由内核临时分配,server 端口号则是知名端口,如 web 服务器所提供的 http 服务,其端口号为 80。web 服务器使用基于文本的 HTTP 协议提供服务:向 web 客户端提供静态内容(磁盘文件)或动态内容(程序输出)。

12. 并发编程

如果逻辑控制流在时间上重叠,就称它们为并发。应用级并发有很多用途:访问慢速 I/O 设备,与人交互,通过推迟工作以降低延迟,服务多个网络客户端,在多核机器上进行并行运算等。

基于多进程可以构造并发。每个逻辑流使用单独的进程,并由内核自动调度。每个进程有独立的地址空间,因而流之间难以共享数据。

基于 I/O 多路复用可以构造并发。逻辑流由自己创建,并利用 I/O 多路复用显示的调度流。由于单进程,所以多个流共享整个地址空间。逻辑流被抽象为状态机,实现事件驱动的状态转移(transition):输入的状态(state)和事件(event)被映射为输出的状态。

基于多线程可以构造并发。线程是运行在进程上下文中的逻辑流,结合了基于进程的流和基于 I/O 多路复用的流的特性:既可以被内核自动调度,又能共享进程的地址空间。多线程与多进程的差别在于,线程之间的上下文切换要比进程更快,而且线程之间是对等关系的而非进程之间的父子关系。

无论哪种并发机制,同步对共享数据的并发访问都是一个难题,如生产/消费程序中的读写缓冲,资源读写程序中的互斥访问等。

参考

  1. computer systems: a programer’s perspective

results matching ""

    No results matching ""