在传输层中，主要学习三种协议

• User Datagram Protocol (UDP, 用户数据报协议) 是一种简单 (simple)、不可靠 (unreliable) 的数据报协议
• Transmission Control Protocol (TCP, 传输控制协议) 是一种复杂的 (sophisticated)、可靠的 (reliable)、字节流协议
• Stream Control Transmission Protocol (SCTP, 流控制传输协议) 是一种较新的、可靠的协议，但它还提供消息边界 (message boundaries)、传输层级别的多宿 (multihoming)、最小化头端阻塞 (head-of-line blocking)

总图

图中最左边的应用 tcpdump 直接使用数据链路层接口 BPF (BSD packet filter, BSD 分组过滤器) 或 Datalink provider interface (DLPI, 数据链路提供者接口) 进行通信。而其他应用都是用 API 所提供的 socket 或 XTI。当然在 Linux 上提供了 SOCK_PACKET 这种 socket 来访问数据链路。

从一个简单的时间获取客户端开始

接下来，将从一个使用 TCP 连接的获取时间的客户端开始。

Sorting something that you will never search is a complete waste; searching something you never sorted is merely inefficient.

— Brian Christian

我们假设对数组进行排序，数组的所有位置都有元素，且长度为 N。对于排序，假设元素存在 \(<\) 和 \(>\) 用以将输入按一致的次序放置，比较运算是除赋值运算外仅有的能对输入数据进行的操作。这种条件下的排序称之为 比较排序 (comparison-based sorting)。另外对于已经排序完成的数组，如果可以保持原本的数据次序我们称之为 稳定排序 (stable sorting)。

模型

优先队列 (priority queue) 的 ADT 与 queue 类似，它们都提供了基本的 enqueue 与 dequeue 操作。但是 priority queue 可以在 dequeue 时将数据按照一定顺序弹出队列，而不是 FIFO。我们这里主要讨论每次出队最小的元素 (即 delete_min)，如果你希望进行其他一些有规范的操作，方法与这类似。

She made a hash of the proper names, to be sure.

— Grant Allen

散列函数

如果可以将存储的数据，其中某一项用于查找，则这个项被称为 键 (key)，而通过一定规则将键映射到表中的一个合适的单元，这个规则被称为 散列函数 (hash function)。我们希望 hash 足够简单且保证两个不同的 key 映射到不同的单元，但是单元是有限的，因此我们需要寻找一个 hash function 尽量均匀的产生 hash value。当映射不是单射而是多射时，即发生了 冲突 (collision)，有两个不同的 key 经过 hash function 得到了相同的 hash value，我们应该处理这个 collision。

如果给定一个序列，你将如何在这个序列中查找一个给定元素 target，当找到时返回该元素的迭代器，否则返回末尾迭代器。首先排除时间复杂度 \(\mathcal{O}(N)\) 的朴素算法，这不是本文的重点。

Not all roots are buried down in the ground, some are at the top of a tree.

— Jinvirle

树 (tree)

Tree 是一些结点的集合，这个集合可以是空集；若不是空集，则 Tree 是由称为 根 的结点 r 以及零或多个非空的子树 \(T_{1}, T_{2}, \cdots, T_{N}\) 组成，这些子树的根都与 r 有一条有向边 (edge) 连接。这些子树的根被称为根 r 的孩子 (child)，而 r 是这些 child 的父亲 (parent)。

Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.

— Stan Kelly-Bootle

表 (List)

我们将形如 \(a_0, a_1, a_2, \cdots, a_{N-1}\) 组成的有限序列称为 list，这个 list 的大小是 \(N (N \in \mathbb{N})\) ，我们将大小为 0 的表称之为 空表 (empty list)。

I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships.

— Linus Torvalds

基本的数学知识

首先我们需要复习一些在初高中可能学过的基础数学知识。

集合

集合 (Set) 是基本的数学概念，指具体的某种性质的事物的总体，集合中的事物称之为 元素 (element)。

计算机中有很多独占 resource，在任一时刻它们只能被一个进程使用，因此 OS 需要授权一个进程临时地、排他地访问某一 resource 的能力。一般进程会排他性地访问若干资源，假设进程 A 在先使用扫描仪的情况请求蓝光光盘刻录机，而进程 B 在先使用蓝光光盘刻录机的情况下请求扫描仪，由于两个进程都占有一定 resouce 且不会释放，并且互相请求了对方的 Resource，而造成这两个进程无限阻塞下去，这样的状态被称为 死锁 (deadlock)。请不要单纯理解只有一台机器才会产生 deadlock，在多台机器同时访问局域网下的多个独占 resource 时也可能发生。

除了提供抽象外，操作系统还要控制计算机的所有 IO (输入/输出) 设备，必须向设备发送命令、捕获中断并处理设备的各种错误。它还应该在设备和其他部分之间提供简单且易于使用的接口，且这些接口应该尽可能的对所有设备都相同，即设备无关。

对于长期存储的信息有三个基本要求：

1. 能够存储大量信息
2. 使用信息的进程终止时，信息依旧存在
3. 必须能使多个进程并发访问相关信息

磁盘由于其长期存储的性质，已有多年的使用历史。今年固态硬盘因其没有易损坏的移动部件、可以提供高速的随即访问，而流行起来。但磁盘和光盘虽然性能较差但也广泛用于备份。磁盘可以看做一种大小固定的块的线性序列，且支持：