在传输层中，主要学习三种协议
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 来访问数据链路。
IPv4 Internet Protocol (IP, 网际协议)，版本 4。 这是自 1980 年代早期以来网际协议族中的主力协议，使用 32 bit 编码地址，为 TCP、 UDP、SCTP、ICMP 和 IGMP 提供分组传递服务。
信息 关于 UNP 的所有代码可以在 https://github.com/unpbook/unpv13e 上找到 从一个简单的时间获取客户端开始接下来，将从一个使用 TCP 连接的获取时间的客户端开始。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 // 以下代码与 UNP intro/daytimetcpcli.
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)。
当然这与 STL 的算法有一点点出入，sort 接收的是迭代器来表示待排序的范围，以及一个可选的比较器。而且 sort 的底层算法也更加复杂，这里只是简单地说明各个基础排序。
1 2 3 4 template <class Iterator> void sort(Iterator begin, Iterator end); template <class Iterator, class Comparator> void sort(Iterator begin, Iterator end, Comparator cmp); 为了方便理解，将使用 Wikipedia 上关于排序的动图来帮助理解这种排序。先放个大招
表格 排序算法简要比较 摘自 Wikipedia
模型优先队列 (priority queue) 的 ADT 与 queue 类似，它们都提供了基本的 enqueue 与 dequeue 操作。但是 priority queue 可以在 dequeue 时将数据按照一定顺序弹出队列，而不是 FIFO。我们这里主要讨论每次出队最小的元素 (即 delete_min)，如果你希望进行其他一些有规范的操作，方法与这类似。
显然 priority queue 有一个朴素解，那就是在每次 delete_min 时遍历整个存储单元，找到最小的元素并删除，其时间复杂度 \(\mathcal{O}(N)\) ，当然插入元素的时间复杂度会好很多，只需要 \(\mathcal{O}(1)\) 。当然你也可以将其反过来，在插入时就找到最小的元素。
显然这是无法接受的，即使是利用前几篇中介绍过的 AVL 树都可以将其时间复杂度压缩到 \(\mathcal{O}(\log_{}{N})\) 。不过这有点太过分了，平衡 BST 的很多操作可能是用不上的，而且为了优先队列再实现一个平衡树实在是太难为人了。
我们将要介绍的工具叫做 二叉堆 (binary heap)，用以实现有限队列。但是需要注意的是， 堆 (heap) 这里指的是一种数据结构，而非操作系统中用以分配动态内存的地方。
二叉堆 结构性质binary heap 是一棵被完全填满的二叉树，或者说是一棵 complete binary tree。由于 complete binary tree 的排列十分有规律，因此我们可以将其转化为数组，不再需要链来链接它。
对于数组任一位置 \(i\) 上的元素，其左右儿子分别在在位置 \(2i + 1\) 和 \(2i +2\) 上，而它的父亲则在位置 \(\lfloor(i - 1)/2\rfloor\) 上。当然如果根从 \(1\) 开始，那么位置 \(i\) 上元素的左右儿子的位置分别为 \(2i\) 和 \(2i + 1\) ，而父亲的位置是 \(\lfloor i/2 \rfloor\) 。以下未说明的情况，我们将 1 作为 root 的下标。
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。
顺便一提，我们一般使用 hash value 对表长进行取模，从而确定数据在表中的位置，表长为素数是可以很好的让 hash value 取模后均匀分布在表中。
我们假设一个简单的字符串 hash function，即将字符串中所有的字符的 ASCII 相加所得到的。如果表很大，就不能很好的平均分配数据。比如 \(TableSize = 10'007\) ，并设所有的键长度为 8，而这些键的最大 hash value 不超过 1016 (\(127 * 8\))，这显然不是平均分配的。
如果假设 Key 至少有 3 个字符，并且设置一个只考虑前 3 个字符的 hash function： \(c_{0} + 27 * c_{1} + 27 * 27 * c_{2}\) 。我们假设键的前三个字符是随机的，表的大小依然是 10007，那么我们就会得到一个均匀分布的 hash value。但是英文实际上并不是随机的，虽然前三个字符有 \(26^{3} = 16576\) 种可能的组合，但是事实证明 3 个字母不同的组合数实际上只有 2851 。
如果给定一个序列，你将如何在这个序列中查找一个给定元素 target，当找到时返回该元素的迭代器，否则返回末尾迭代器。首先排除时间复杂度 \(\mathcal{O}(N)\) 的朴素算法，这不是本文的重点。
二分查找二分法 (Dichotomy) 是一种思想，将一个整体事物分割成两部分，这两部分必须是互补事件，即所有事物必须属于双方中的一方且互斥。如此我们就可以在 \(\mathcal{O}(1)\) 的时间内将问题大小减半。
二分查找 (binary search)，又称折半查找，这是一种可以在 \(\mathcal{O}(\log_{}{N})\) 时间复杂度下完成查找的算法。二分查找要求序列必须是有序的，才能正确执行：将序列划分为两部分，如果中间值大于 target，意味着这之后的值都大于 target，需要继续向前找；如果中间值小于 target，意味着这之前的所有值都小于 target，需要继续向后找。
AVL 树上一篇介绍树时分析了 BST 中为什么很容易发生不平衡现象。在极端情况下，只有一个 leaf 的树，在查找元素时其时间复杂度退化为 \(\mathcal{O}(N)\) 。
为了防止 BST 退化为链表，必须保证其可以维持树的平衡，一次需要有一个 平衡条件 (balanced condition)。如果每个结点都要求其左右子树具有相同的高度，显然是不可能的，因为这样实在是太难了。在 1962 年，由苏联计算机科学家 G.M.Adelson-Velsky 和 Evgenii Landis 在其论文 An algorithm for the organization of information 中公开了数据结构 AVL (Adelson-Velsky and Landis) 树，这是计算机科学中 最早被发现的 自平衡二叉树。
AVL 的平衡因子AVL 树将子树的高度限制在差为 1，即一个结点，如果其左子树与由子树的高度差 \(|D_{h}| \leq 1\) ，则认为这棵树是平衡的。因此带有平衡因子 \(-1\) 、 \(0\) 或 \(1\) 的结点被认为是平衡的，而 \(-2\) 或 \(2\) 的平衡因子被认为是需要调整的。平衡因子可以直接存储于结点之中，也可以利用存储在结点中的子树高度计算得出。
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)。
树的属性根据给出的树的递归定义，可以发现一个树是由 \(N\) 个 node 和 \(N - 1\) 条 edge 的集合。而除 root 外的所有 node 都有一个由其 parent 指向它的 edge。在树中有一些特殊的属性是需要注意的，这里先给出相关概念与示例，如果不是很理解，可以通过结合示例来理解这些概念。
结点的度 (degree) 一个节点含有的子树的个数称为该节点的度 树的度 (degree of tree) 一棵树中最大的 node degree 称为树的度 叶结点 (leaf) 或称终端结点，如果结点满足 \(degree = 0\) 则该结点为叶结点 分支结点 (branch node) 或称内部结点 (internal node)、非终端结点，度不为 0 的结点 层次 (level) 从 root 开始，root 所在的层为第 1 层，root 的 child 为第二层，以此类推 关系 树就像一本族谱，从 root 开始结点直接有一定的亲缘关系 兄弟 (sibling): 具有相同父节点的节点互为兄弟节点 叔父 (uncle): 父结点的兄弟结点为该结点的叔父结点 堂兄弟: 父结点在同一层的结点互为堂兄弟 路径 (path) 结点 \(n_{1}, n_{2}, \cdots, n_{k}\) 的一个序列，使得对于 \(1 \leq i < k\) 满足 \(n_{i}\) 是 \(n_{i + 1}\) 的 parent，则这个序列被称为从 \(n_{1}\) 到结点 \(n_{k}\) 的 path。其路径长度 (length) 为路径上的 edge 的数量，即 \(k - 1\) 。特别地，每个结点到自己的 path lenth 为 0 深度 (depth) 对于结点 \(n_{i}\) ，从 root 到 \(n_{i}\) 的唯一路径的长度 (\(Depth_{root} = 0\)) 高度 (height) 对于结点 \(n_{i}\) ，从 \(n_{i}\) 到 leaf 的最长路径长度 (\(Height_{leaf} = 0\)) 树的高度 或称树的深度，其总是等于根的高度，或最深的结点的深度，可以认为一棵空树的高度为 \(-1\) 祖先 (ancestor) 对于结点 \(n_{i}\) 与 \(n_{j}\) 存在一条 \(n_{i}\) 到 \(n_{j}\) 的路径，那么称 \(n_{i}\) 是 \(n_{j}\) 的祖先 (ancestor)，而 \(n_{j}\) 是 \(n_{i}\) 的 后裔 (descendant) 距离 (distance) 对于结点 \(n_{i}\) 与 \(n_{j}\) ，从最近的公共祖先结点 \(n_{k}\) 分别到它们的路径长度之和被称为距离 (distance)。特别地，如果 \(n_{i} = n_{k}\) ，则 \(n_{i}\) 与 \(n_{j}\) 的距离为 \(n_{i}\) 到 \(n_{j}\) 的路径的长度 信息 严蔚敏老师的数据结构中，或者往常的实现中，根的高度为 1，而叶的深度也为 1，树的高度一般指其最大的层次，因此认为空树的高度为 0。 树的实现实现树的一种方法是在每一个结点上，除数据外还需要一些链域来指向该结点的每个子结点，然而由于每个结点的子结点数量是不确定的，我们不能直接建立到各个子结点的直接链接。如果申请一定大小的空间以存放子结点，则可能会造成空间的浪费，或不足。因此我们链表的形式存储子结点，而父结点中只存储第一个子结点的指针，如果该链域为空则意味着该结点是叶结点 (\(degree = 0\))。每个结点中存在一个指向其下一个兄弟的指针，为遍历父结点的所有孩子提供了方法，当该结点 \(next\_sibling = nullptr\) 时意味着这是父结点的最后一个子结点。
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)。
除空表外的任何表，我们从 0 开始标记元素，最后一个元素的下标为 \(N - 1\) ，那么第 \(i (i \in \mathbb{N}^{*})\) 个元素是 \(a_{i-1}\) ，称 \(a_{i}\) 是 \(a_{i + 1}\) 的 前驱 ， \(a_{i}\) 是 \(a_{i - 1}\) 的 后继 。
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)。
element 通常使用小写字母表示，而 set 通常使用大写字母表示。若 \(x\) 是集合 \(A\) 中的元素，记作 \(x \in A\) ；反之不在集合中记作 \(x \notin A\) 。当两个 set 中所包含的 element 完全一样时，就称这两个 set 相等，记作 \(A = B\) 。
计算机中有很多独占 resource，在任一时刻它们只能被一个进程使用，因此 OS 需要授权一个进程临时地、排他地访问某一 resource 的能力。一般进程会排他性地访问若干资源，假设进程 A 在先使用扫描仪的情况请求蓝光光盘刻录机，而进程 B 在先使用蓝光光盘刻录机的情况下请求扫描仪，由于两个进程都占有一定 resouce 且不会释放，并且互相请求了对方的 Resource，而造成这两个进程无限阻塞下去，这样的状态被称为 死锁 (deadlock)。请不要单纯理解只有一台机器才会产生 deadlock，在多台机器同时访问局域网下的多个独占 resource 时也可能发生。
资源我们将需要排他访问的对象称为 资源 (resource)，资源可以是硬件设备或一组信息，通常有多种资源同时存在，且一些类型的资源存在若干实例 (打印店在同一局域网下会存在多台打印机)。
还记得学习进程与线程时所说的，scheduling algorithm 分为两类： 抢占式 (preemptable) 与 非抢占式 (nonpreemptable)，这里我们也将 resource 分为这两类，且意义相同。比如说 RAM 就是 preemptable resource，一个进程可以在使用时被 OS 换出 RAM；而蓝光刻录机则是 nonpreemptable resource，将正在刻录的蓝光刻录机分配给另一个进程可能造成蓝光光盘的损坏。不过需要思考一个问题，如果这台计算机不支持交换和页面调度，那么内存也就变为了 nonpreemptable resource。因此区分 preemptable / nonpreemptable resource 取决于上下文环境。
preemptable resource 的 deadlock 可以通过 resource 的重新配分而化解，因此 deadlock 主要与 nonpreemptable resource 有关。若 resource 变得不可用，则请求进程将不可用，有的 OS 在这时会阻塞该进程，直到 resource 可用时再次唤醒；有些 OS 则会返回一个错误代码，请求进程自己处理这个错误。但是大部分进程会选择请求、休眠、再请求的方式进行循环，这与被阻塞没什么两样，因此假设 OS 在 resource 不可用时阻塞进程。
除了提供抽象外，操作系统还要控制计算机的所有 IO (输入/输出) 设备，必须向设备发送命令、捕获中断并处理设备的各种错误。它还应该在设备和其他部分之间提供简单且易于使用的接口，且这些接口应该尽可能的对所有设备都相同，即设备无关。
单位在进行本篇之前，需要明确一下计算机领域常用单位，只有统一了单位，我们才能更好的交流。
计算机领域以 bit (b，位) 和 byte (B，字节) 作为基本单位，bit 是只能表示 1 或 0 的单位数据，\(1 \texttt{Byte} = 8 \texttt{bit}\)，即 1 Byte 可以表示 256 种不同的状态。另外在 IO 传输数据时，最常用的单位即 比特率 (单位：bit/s 或 bps)，即每秒传输的 bit 数量，当然也可以对其进行除以 8 运算转变为 Byte/s。
传统单位以 SI (10 进制) 前缀为词头，而计算机领域多以 IEC 60027 (2 进制) 前缀为词头。一般内存与 CD 使用 IEC-60027 词头，而磁盘、闪存、DVD 常用 SI 词头表示容量。至于 Windows 系统对于容量的显示问题，内部转换为 IEC-60027 但显示的词头却是 SI，这也是历史原因所造成的。
词头 prefix 符号 \(10^{n}\) prefix 符号 \(2^{n}\) \(16^{n}\) 尧 yotta Y \(10^{24}\) yobi Yi \(2^{80}\) \(16^{20}\) 泽 zetta Z \(10^{21}\) zebi Zi \(2^{70}\) \(16^{17.
对于长期存储的信息有三个基本要求：
能够存储大量信息 使用信息的进程终止时，信息依旧存在 必须能使多个进程并发访问相关信息 磁盘由于其长期存储的性质，已有多年的使用历史。今年固态硬盘因其没有易损坏的移动部件、可以提供高速的随即访问，而流行起来。但磁盘和光盘虽然性能较差但也广泛用于备份。磁盘可以看做一种大小固定的块的线性序列，且支持：
读块 k 写块 k 磁盘一般支持更多操作，但只要存在这两个操作，原则上就可以解决长期存储问题。当然这还远远不够，一些操作不便于实现，在思考时往往还产生一些问题：
如何找到信息 如何防止一个用户读取另一个用户的数据 如何知道哪些块是空闲的 就像 OS 提取处理器的概念来创建进程的抽象，以及提取 RAM 的概念来创建进程虚拟地址空间的抽象一样，使用 文件 (File) 来解决磁盘的问题。File 是 进程创建的信息逻辑单元，文件是对磁盘的建模而非 RAM，因此将文件看做地址空间就能理解了。
进程可以读取已存在的 File，并在需要时建立新 File，存储的文件必须是持久的，因此不会受到进程的创建与终止而受到影响，只有在其所有者明确删除它的情况下才会消失。File 受操作系统管理，有关的构造、命名、访问、使用、保护、实现和管理方法都是 OS 设计的主要内容。从总体上看，OS 处理文件的部分被称为 文件系统 (file system)，这才是 OS 的核心问题之一。从用户的角度看，File System 中最重要的就是其表现形式，即文件由什么组成的，如何命名、修改等操作。至于如何实现，和我这个用户有什么关系呢。
文件首先先从用户的角度观察文件，文件是对磁盘上保存信息的一种抽象，用户不必关心磁盘如何存储、存储到哪里、实际的工作方式等细节。
文件系统是实现这些细节的程序，在 MS-DOS 中使用的是 FAT-16 文件系统，Windows98 对其进行了扩展，从而成为今天耳熟能详的 FAT-32 文件系统，Windows 如今是用一种更为先进的 NTFS 文件系统。微软还根据 FAT 文件系统开发出了 exFAT ，这是针对于闪存和大文件开发的系统，并且也是唯一能满足 OS X 读写操作的微软开发的文件系统。UNIX 的文件系统也有很多，目前主流的是 Linux 的 ext4 (其是 ext2 和 ext3 的升级版本)、 Solaris 的 ZFS 、Unix 传统的 FFS 以及 OS X 的 HFS+ 等，还有一些著名公司如 SGI 开发的 XFS 、RedHat 主导的 BtrFS 等。这些文件系统可能底层实现、适用环境不同，但大部分都遵循 POSIX 实现，对用户操作来说是透明的。
