Principles of Computer System Design 读书笔记 II

CHAPTER 2 Elements of Computer System Organization

OVERVIEW

实践中最重要的三个对计算机系统组件的抽象是：

• The memory（存储器）
• The interpreter （解释器）
• The communication link (通信链路）

设计者运用这三个抽象来组织物理硬件的结构，不仅仅因为它们是直接的通道，还因为：

• 它们提供了最基础的函数，包括调用(取值），处理和通信；
• 它们也是对硬件最简单，接口最清晰的抽象。

Reference - 引用，一种将计算机系统中交互组件抽象的方式。通常一个组件用过特定的命名方式通另一个组件相连。

2.1 THE THREE FUNDAMENTAL ABSTRACTIONS

2.1.1 Memory

Memory - 存储器，是系统在做计算时用来储存数值的组件。

注解：文中的上下文中Memory是更广泛含义的存储，包括内存，文件储存或一些其它的存储形式的总称。

虽然图 2.1 列出了许多种存储，但所有的存储都可以被抽象成一个模块，一个包括“读”和“写”操作的模块：

WRITE(name, value)
value <- READ(name)

存储器分为：

• 易失性存储器(volatile memory)
• 非易失性存储器(non-volatile memory or stable storage)

硬件层的存储器设备在存储单元上来读写的数据，通常是一段固定长度的bit，比如bytes(8bits)，words(number of bytes, typically 2, 4, 8), lines(several words)和block(a number of bytes, usually a power of 2)。

高层次的存储器系统也是读写一段连续的bit，但在长度上更灵活，可以是record，segment或者file。

2.1.1.1 Read/Write Coherence and Atomicity

存储器有两个特性：

• read/write coherence - 读写一致性
• before-or-after atomicity - 前后原子性

设计者通常为简单地假定这两个特性，但是这种假设是有风险且容易出错的，有许多情况都会威胁到存储器的读写一致性和前后原子性：

• Concurrency - 并发
• Remote storage - 远程存储，延迟带来的问题；
• Performance enhancements - 性能优化，在一些编译器和高性能处理器优化过程中可能会改变操作存储器的顺序，从而破坏读写一致性；
• Cell size incommensurate with value size - 存储单元与数值大小不匹配，一个非常大的数值可能会占据很多存储单元，而在读写过程中由于只能一次操作一个存储单元，可能会破坏前后原子性。同样在操作小数值时，两个同时对同一存储单元进行的写操作也会破坏原子性。
• Replicated storage - 分布式（分片）存储。

系统设计者可能会同时面对上面的多种情况，其中分布式和远程延迟是最具挑战的，有时设计者会设计出弱一致性的存储。
注解：可参考分布式系统CAP理论^[0]

最后我们通常会假定物理的存储设备保证了单存储单元的读写一致性，但是对于多存储单元的前后一致性就需要上层的具体实现来保证了。

2.1.1.2 Memory Latency

Access time / Latency - 磁盘读或写操作消耗的时间。

Random access memory(RAM) - 随机存取存储器^[1]

对于大块数据的READ和WRITE操作有时又被称为GET和PUT，传统上memory也特指随机存取的易失性存储器，而storage指非易失性的存储器，storage对大块数据的读写是GET（取）和PUT（存）。

2.1.1.3 Memory Names and Addresses

图 2.2 展示了结合储存(Associativity memory)的应用架构，通常结合储存位于地址储存的上层，负责高效返回需要经常查询的值。

注解：其实就是我们熟悉的缓存(Cache)

2.1.1.4 Exploiting the Memory Abstraction: RAID

RAID^[2]的全称是 Redundant Array of Independent(or Inexpensive) Disks，它如图 2.2 所示，由许多磁盘和一个控制器组成，其中控制器的接口同单个磁盘的数据接口是一样的。

注解：这个图是不是很像负载均衡

RAID控制器会将READ和WRITE的请求通过接口分发到磁盘上。RAID主要作用有两个：

• 提高性能，并发的读写磁盘；
• 保护数据，多个磁盘有多个数据备份。

2.1.2 Interpreters

图 2.4 列举计算机中常见的解释器。

Interpreter - 解释器，包括了三个基本元素：

• 指令引用，告诉解释器去哪里寻找下一个指令；
• 指令集，定义了解释器将要执行的指令的集合，这些指令通过上面的指令引用来获得；
• 环境引用，告诉了解释器哪里去获得相关的环境，环境的状态会影响当期指令的进行的动作。

图 2.5 是程序运行时解释器的流程图和伪代码，解释器从环境引用里获得当前环境，从指令引用中获得程序指令，然后执行指令，此操作可能会改变环境中的数据，当完成指令后解释器会继续上面的流程执行下一个指令，周而复始。但在这个过程中有一个事件会让解释器停止当前成俗的工作，这就是中断(Interrupts)。被中断的程序不在有解释器的控制权，相应地一个新程序会接管解释器，更新指令和环境。

许多系统都有不止一个解释器，多解释器通常是异步(Asynchronous)工作的，导致即使同一个程序中，解释器的进度都会不一致。正是由于解释器的异步导致内存中的读写一致性和前后原子性变成了设计的一个难点。

2.1.2.1 Processors

通常处理器就是一个解释器的具体实现，处理器的指令引用称作程序计数器(PC - Program Counter)，存在处理器的高速缓存中。PC中包含了具体指令的内存地址，而环境引用放在了寄存器(Register)中。

处理器的指令集包括了一些计算表达式，不如加(ADD)、减(SUB)、数据比较(CMP)和指令更替(JMP)等等，这些指令存储在处理器的寄存器里，有时昵称为“操作代码(Op-codes)。

指令集还包括了许多在寄存器和内存之间移动数据的操作：

• LOAD - 表示寄存器从内存中读取数值；
• STORE - 表示把寄存器里的数值写到内存单元上。

处理器提供了一个先进后出的数据结构——栈，在内存上实现程序的调用。处理器里有个专门的寄存器来存储栈顶的内存地址(Stack point)。

最后，处理器还实现了中断，中断可以让处理器检测到运行程序中的问题（比如程序试图执行一个解释器无法执行的指令，比如除零）。中断也可以是因为外部的一些信号，让处理器处理一些更紧急的工作。

2.1.2.2 Interpreter Layers

解释器通常是用层次结构来描述的，最底层一般包括的是硬件的最基本指令，上面的层次会在此基础上提供一些复杂的指令集，如图 2.6 所示：

图 2.7 列举的一个用Java实现的日历程序中指令如何从高层级往低层级转化的过程：

注解：程序的任务操作或事件都被逐层的翻译给下一层来调用，最后变成硬件能识别的机器语言

2.1.3 Communication Links

图 2.8 列举了一些常见的通信链路的技术，其实就是提供了一种让不同的物理组件能够通信交互的途径。

通信链路可以抽象成：

SEND(link_name, outgoing_message_buffer)
RECEIVE(link_name, incoming_message_buffer)

• SEND操作指定了具体的通信链路名称(link_name)和需要发送信息内容(message)。
• RECEIVE操作同样指定了link_name和接受的信息。

注解：因为在内存中字符串内容的通常是以字符串第一个指针和字符串长度来获取的，所以伪代码中用message_buffer来表示message的内容。

虽然看起来数据链路的SEND和RECEIVE很像是从一个内存READ或WRITE到另一个内存的操作，看似不需要再抽象出这一层。但是实际上数据链路传输数据的情况要复杂许多（比如网络错误，发送失败等等），需要实现比READ和WRITE更多的细节，所以数据链路的这层抽象还是很有必要的。

2.2 NAMING IN COMPUTER SYSTEMS

在程序函数中调用对象的两种方式：

• 获得一个对象的拷贝（值）
• 获得一个对象的命名（引用）

虽然在函数中传递参数时只获取另一对象的值显得更模块化，因为在函数内修改对象的值并不会影响到对象本身，但如果需要这个对象更新的状态被更多的函数感知时，传递值就不行了。所以很多程序都提供了可以共享对象的命名机制。
注解：即C/C++中的指针，其实很多无指针概念的编程语言在传递对象是也是传递的引用。

解耦两个对象的有效方式就是通过命名来起到中介代理的作用。
注解：其实就是说在一个对象里需要用到另一个对象时，只要用那个对象的间接引用（C语言里就是指针）就可以了。

2.2.1 The Naming Model

命名体系的三要素：

• Name Space - 命名空间
• Name-mapping algorithm - 命名映射算法
• Universe of values - 值域

如图 2.10，其中命名映射是更根据上下文(Context)来切换的，具体操作如下：

value <- RESOLVE(name, context)

除此之外，还有另外四个操作：

status <- BIND(name, value, context)
status <- UNBIND(name, context)
list <- ENUMERATE(context)
result <- COMPARE(name1, name2)

第一个操作BIND是在特定上下文中为一个命名绑定了一个新值，stauts是执行的状态（是否成功），第二个操作UNBIND就是解绑，status同第一个操作。ENUMERATE就是列举出当前Context中的所有已被绑定的值。最后COMPARE是用来判断两个命名所绑定的值是否相等的。

三种常见的命名映射算法：

• Table lookup - 表查找
• Recursive lookup - 递归查找
• Multiple lookup - 重复查找

2.2.2 Default and Explicit Context References

当程序解释器遇到一个对象时，需要上下文的引用得到具体的命名映射算法，然后才能通过对象名来进行解析。上下文的引用有两类：

• Default - 默认的
• Explicit - 显式的

默认的解析器是由解析器提供的，而显示的解析器是由对象所提供，如图 2.12。

注解：图2.12 中显示引用的第二种形式是限定名(qualified name)，现实中的像特定对象的属性(N.x)或XML格式的命名(X)都可以认为是限定名。

2.2.3 Path Names, Naming Networks, and Recursive Name Resolution

上图都是一些路径名的例子，它们都包含了多层组件名字。解析路径时我们需要不断重复的去识别出命名中最小区别的步部分，比如：

路径名中常见的一些概念：

• root - 根路径
• Absolute path name - 绝对路径
• Relative path name - 相对路径
• Synonyms/Aliases - 别名
• Links - 链接

2.2.4 Multiple Lookup: Searching through Layered Contexts

当对象被绑定到多个上下文中，解析对象时需要系统地从不同的上下文中来寻找时，就要用到重复查找，常见的有：

• Search path - 查找路径，常用在编程时进行设置，方便编译器去寻找库文件。

注解：Shell环境中配置的SEARCH_PATH

2.2.5 Comparing Names

result <- COMPARE(name1, name2)

其中result是一个布尔值，True（真）或False（假）。不同的编程语言会提供不同层级的比较，比如两个name的命名是否一致，两个name的值师傅一致，两个name在底层的存储位置是否一致等，比如像LISP^[3]语言就提供了三种不同的比较语法 —— EQ（比较参数的名字）、EQU（比较参数的值）、EQUALS（比较整个数据结构）。

2.2.6 Name Discovery

命名发现的两个要素：

• 提供者能表现(Advertise)名字的存在感
• 使用者能搜索(Search)合适的关键字

2.3 ORGANIZING COMPUTER SYSTEMS WITH NAMES AND LAYERS

图 2.16 展示了一个典型而清晰的计算机三层架构，最底层是硬件组件例如处理器、内存和通信链路等，中间层是操作系统，提供了应用可编程接口(API)，最上层是一些具体的应用程序，如文字处理工具，游戏或网页浏览器等。其中每一层内部也是由层次结构组织起来的。

软件和硬件实际上可以相互实现对方的大部分功能，所以在的工程设计上就是一种取舍(Trade-off)的结果，主要考量包括了性能，灵活性，易用性等等。

可以发现操作系统层次有一种有意思的现象称为层次跳跃(layer bypass)，就是操作系统只隐藏了底层硬件一部分的高危指令，所以高层次的应用程序实际上可以绕过操作系统去调用硬件的另一部分较安全的指令。

2.3.1 A Hardware Layer: The Bus

硬件层的实现就包括了本文最开始提到的三种基本抽象，如图 2.17 所示：

• 解释器 —— 处理器解释程序
• 存储器 —— 内存存储程序和数据
• 通信链路 —— I/O设备和外界交互

多个组件都会接到总线(Bus)上，以实现高速的信息传递。总线的基本特征包括：

• 总线接口(Bus Interface)连接各种组件的地址线，数据线和控制线；
• 总线仲裁协议(Bus Arbitration Protocol)限制了组件的行为，即在什么时候可以发送和接受信息，使同一时刻内的信号不会产生混乱；
• 广播(Broadcast)保证了连上总线的组件可以接受到每条消息，总线地址(Bus Address)保证了特定的消息可以发送给特定的组件。

一种常见的总线设计方法被称为拆分事务(Split-transaction)。

注解：就是把一个完整的操作周期拆分成两个子过程，比如IO读写请求中“主设备请求->从设备发送->主设备接受”就被拆分成了“主设备请求->从设备确认“和“从设备准备发送->主设备接收“两个阶段的事务，这样在两个事务中间总线的资源可以释放出来被其它设备使用。这个原理和并发中IO的多路复用类似。

两个提高总线效率的技术：

• 直接内存访问(Direct Memory Access, DMA)^[4]
• 内存映射IO(Memory-mapped I/O, MMIO)^[5]

The principle of least astonishment
People are part of the system. The design should match the user’s experience, expectations, and mental models.

注解：在计算机系统设计时，要让系统易设置，易使用，易编程，易维护。

2.3.2 A Software Layer: The File Abstraction

计算机系统中文件的两个特性：

• 持久性(Durable)，可以长期保持在介质中；
• 实名性(Name)，可以通过文件名来共享。

图 2.18 展示了一个应用如何从键盘读取输入，把输入写到文件中以及如歌在显示设备上显示出来的伪代码：

一个典型的文件系统API包括了打开(OPEN)文件，读写(READ/WRITE)文件和关闭(CLOSE)文件的操作。

OPEN的主要任务包括:

• 给文件创建一个临时的引用名，方便后续READ和WRITE操作；
• 检查用户是否有权限操作文件；
• 在文件内容的最开始设置一个游标(Cursor)或文件指针(File Pointer)来记录文件内容的位移(Offset)情况。

READ和WRITE根据游标位置和指定的长度来操作读写内容，循环往复把内容读或写到Buf中，一直到文件的末尾才停止。其中写操作也可能会因为存储容量不足而中断。

CLOSE操作释放文件中的所有状态，包括引用名和游标，有些系统会在CLOSE时保证所有对文件的修改都会保存到非易失性存储设备中，有些系统则会在CLOSE后在后台完成这个动作。

现今的文件系统会通过OPEN和CLOSE来标记原子操作的开始和结束，保证：

1. 文件系统可以保证并发访问文件时的一致性，比如一个程序在OPEN文件时如果另一个程序想OPEN这个文件，文件系统可以让第二个程序处于等待状态，直到第一个文件CLOSE这个文件。这种一致性的行为又称作前后原子性(Before-or-after Atomicity)。
2. 如果文件系统在应用CLOSE文件前宕机了，之前的WRITE操作都不会反映到文件中；如果文件系统在应用CLOSE文件后宕机，所有的WRITE操作都会反映到文件中。这种一致性称为无中间状态原子性(All-or-nothin Atomicity)

在一些操作系统（类Unix）中，所有的输入/输出设备，包括键盘、显示器、通信链路等，都会提供类似于文件系统的接口，如图 2.19 所示。这样用户只需要与简单的操作函数打交道，而不需要直到具体的实现细节。

2.4 LOOKING BACK AND AHEAD

目前已涉及的内容包括：

• 计算机系统设计的三种重要抽象
  • 存储器
  • 解释器
  • 通信链路
• 如何将模块抽象的通用模型
• 计算机系统典型的三层架构

下会具体的分析现实中的实现案例。

2.5 CASE STUDY: UNIX^®️ FILE SYSTEM LAYERING AND NAMING

2.5.1 Application Programming Interface for the UNIX File System

UNIX文件系统提供的应用编程接口(API)如表 2.1 所示：

UNIX文件系统通过分治法(Divide-and-conquer)来实现这些API函数，将底层的面向机器(Machine-oriented)的命名，比如地址，通过更上层的抽象隐藏起来，最后实现文件的表述，如表 2.2 所示：

2.5.2 The Block Layer

在UNIX文件系统的底层，文件被分割成大小固定的单元——块(Blocks)存储在非易失性介质里。块是磁盘空间的最小单元，其大小的设定是根据多种因素权衡得到的。

可以用数字编号来命名块，代表了从存储设备最开始到当前块的偏移。其名字和内容的映射关系可以用下面的伪代码表示：

procedure BLOCK_NUMBER_TO_BLOCK (integer b) returns block
    return device[b]

文件系统通过超级块(Super block)来记录磁盘的使用情况。现代的UNIX文件系统还会通过位图(Bitmap)来追踪块是否被占用。图 2.2 列举了一种简单文件系统的块结构，其中Inode表中存了每个文件的入口。

2.5.3 The File Layer

为了支持文件大小可以自由的增大和减小，UNIX文件系统提供了新的一层抽象使文件系统可以知道哪些块属于某一个特定的文件。这个记录文件元数据(Metadata)的容器就是索引节点(Index node)，通常称作Inode。Inode的定义如下：

structure inode
    integer block_numbers[N]    // the numbers of the blocks that constitute the file
    integer size    // the size of the file in bytes

Inode中块的映射算法：

procedure INDEX_TO_BLOCK_NUMBER (inode instance i, integer index) returns integer
    return i.block_numbers[index]

在大文件的映射上，第六版UNIX文件系统采用了间接块(Indirect blocks)的方式，而现代的UNIX系统会用更先进的数据结构来组织文件，比如B+树。

通过Offset和前面的两个函数来获得文件中特定的字节，即块：

procedure INODE_TO_BLOCK (integer offset, inode instance i) returns block
    o <- offset / BLOCKSIZE
    b <- INDEX_TO_BLOCK_NUMBER(i, o)
    return BLOCK_NUMBER_TO_BLOCK(b)

2.5.4 The Inode Number Layer

UNIX文件系统还提供了一个包含所有Inode的表，用Inode的编号来做索引，下面就是具体的算法:

procedure INODE_NUMBER_TO_INODE(integer inode_number) returns inode
    return inode_table[inode_number]

下面的函数通过offset和inode_number来得到特定的块，块中的内容就是inode_number指向的文件里从offset位置开始的字节：

procedure INODE_NUMBER_TO_BLOCK(integer offset, integer inode_number) returns block
    inode instance i <- INODE_NUMBER_TO_INODE(inode_number)
    o <- offset / BLOCKSIZE
    b <- INDEX_TO_BLOCK_NUMBER(i, o)
    return BLOCK_NUMBER_TO_BLOCK(b)

2.5.5 The File Name Layer

因为数字对用户来说可读性不高，所以UNIX文件系统增加了一个新的命名层，用来隐藏文件管理中的元数据(Metadata)，其中就包括目录(Directory)，下面展示了如何在目录中检索一个文件的伪代码，如果找到文件的入口就会返回其Inode编号。

procedure NAME_TO_INODE_NUMBER(character string filename, integer dir) returns integer
  return LOOKUP(filename, dir)

structure inode
    integer block_numbers[N]
    integer size
    integer type // type of file: regular file, directory,...

2.5.6 The Path Name Layer

路径的算法是通过递归的调用上面的LOOKUP函数实现的：

其中第二行的PLAIN_NAME会扫描参数中的标准路径分隔符（UNIX中是‘/’），如果没有分隔符就返回TRUE，所以递归的终点就是返回指定路径的Inode编号。

CHDIR用来切换工作目录：

procedure CHDIR (path character string)
    wd <- PATH_TO_INODE_NUMBER(path, wd)

2.5.7 Links

LINK(from_name, to_name)
UNLINK(filename)

因为有了链接，所以只有在文件所有绑定都被移除的情况下，UNIX文件系统才会删除这个文件。所以需要在Inode中记录引用的次数：

structure inode
  integer block_numbers[N]
  integer size
  integer type
  integer refcnt

其中“.”和“..”是两个特殊的链接，代表当前目录和上级目录。

2.5.8 Renaming

LINK(from_name, to_name)
UNLINK(from_name)

2.5.9 The Absolute Path Name Layer

绝对路径的算法如下：

2.5.10 The Symbolic Link Layer

用户可以把存储设备加载到新的空间下：

MOUNT("/dev/df1", "/flash")

加载信息只会被存在内存中，所以计算机宕机后，管理员需要重新加载。

Symbolic(Soft) Link —— 符号（软）链接，将一个文件名与另一个名字绑定在一起。

表 2.3 比 表 2.2 更详细地列出了每层接口的名字，值，上下文和伪函数：

2.5.11 Implementing the File System API

2.5.12 The Shell and Implied Context, Search Paths, and Name Discovery

注释

---

1. 0.Perspectives on the CAP Theorem ↩
2. 1.随机存取存储器（英语：Random Access Memory，RAM），是与CPU直接交换数据的内部存储器，也叫主存。[1]它可以随时读写（刷新时除外，见下文），而且速度很快，通常作为操作系统或其他正在运行中的程序的临时数据存储媒介。 ↩
3. 2.独立硬盘冗余阵列（RAID, Redundant Array of Independent Disks），旧称廉价磁盘冗余阵列（Redundant Array of Inexpensive Disks），简称磁盘阵列。其基本思想就是把多个相对便宜的硬盘组合起来，成为一个硬盘阵列组，使性能达到甚至超过一个价格昂贵、容量巨大的硬盘。 ↩
4. 3.LISP是第一个函数式程序语言，区别于C语言、Fortran等命令型程序语言和Java、C#、Objective-C等面向对象程序语言。 ↩
5. 4.DMA允许某些电脑内部的硬件子系统（电脑外设），可以独立地直接读写系统内存，而不需中央处理器（CPU）介入处理 。 ↩
6. 5.MMIO使用相同的地址总线来寻址内存和输入输出设备（简称IO设备），前提是IO设备上的设备内存和寄存器都已经被映射到内存空间的某个地址。 ↩