Json

JSON(JavaScrip Object Notation)是一种轻量级的数据交换格式。它基于 ECMAScript (欧洲计算机协会制定的js规范)的一个子集，采用完全独立于编程语言的文本格式来存储和表示数据。简洁和清晰的层次结构使得 JSON 成为理想的数据交换语言。 易于人阅读和编写，同时也易于机器解析和生成，并有效地提升网络传输效率。

关于上面的描述可以精简为一句话：Json是一种数据格式，和语言无关，在什么语言中都可以使用Json。基于这种通用的数据格式，一般处理两方面的任务：

• 组织数据（数据序列化），用于数据的网络传输
• 组织数据（数据序列化），写磁盘文件实现数据的持久化存储（一般以.json作为文件后缀）

Json中主要有两种数据格式：Json数组和Json对象，并且这两种格式可以交叉嵌套使用，下面依次介绍下这两种数据格式：

Json数组

Json数组使用 [] 表示，[]里边是元素，元素和元素之间使用逗号间隔，最后一个元素后边没有逗号，一个Json数组中支持同时存在多种不同类型的成员，包括：整形、 浮点、 字符串、 布尔类型、 json数组、 json对象、 空值-null。由此可见Json数组比起C/C++数组要灵活很多。

• Json数组中的元素数据类型一致

1
2
3
4

// 整形
[1,2,3,4,5]
// 字符串
["luffy", "sanji", "zoro", "nami", "robin"]

• Json数组中的元素数据类型不一致

1

[12, 13.34, true, false, "hello,world", null]

• Json数组中的数组嵌套使用

1
2
3
4
5

[
    ["cat", "dog", "panda", "beer", "rabbit"],
    ["北京", "上海", "天津", "重庆"],
    ["luffy", "boy", 19]
]

• Json数组和对象嵌套使用

1
2
3
4
5
6
7
8
9
10
11

[
    {
        "luffy":{
            "age":19,
            "father":"Monkey·D·Dragon",
            "grandpa":"Monkey D Garp",
            "brother1":"Portgas D Ace",
            "brother2":"Sabo"
        }
    }
]

Json对象

Json对象使用 {} 来描述，每个Json对象中可以存储若干个元素，每一个元素对应一个键值对（key：value 结构），元素和元素之间使用逗号间隔，最后一个元素后边没有逗号。对于每个元素中的键值对有以下细节需要注意：

1. 键值（key）必须是字符串，位于同一层级的键值不要重复（因为是通过键值取出对应的value值）
2. value值的类型是可选的，可根据实际需求指定，可用类型包括：整形、 浮点、 字符串、 布尔类型、 json数组、 json对象、 空值-null。

使用Json对象描述一个人的信息:

1
2
3
4
5
6
7
8
9
10
11
12

{
    "Name":"Ace",
    "Sex":"man",
    "Age":20,
    "Family":{
        "Father":"Gol·D·Roger",
        "Mother":"Portgas·D·Rouge",
        "Brother":["Sabo", "Monkey D. Luffy"]
    },
    "IsAlive":false,
    "Comment":"yyds"
}

注意事项

通过上面的介绍可用看到，Json的结构虽然简单，但是进行嵌套之后就可以描述很复杂的事情，在项目开发过程中往往需要我们根据实际需求自己定义Json格式用来存储项目数据。

另外，如果需要将Json数据持久化到磁盘文件中，需要注意一个问题：在一个Json文件中只能有一个Json数组或者Json对象的根节点，不允许同时存储多个并列的根节点。下面举例说明：

• 错误的写法

1
2
3
4
5
6
7
8
9

// test.json
{
    "name":"luffy",
    "age":19
}
{
    "user":"ace",
    "passwd":"123456"
}

错误原因：在一个Json文件中有两个并列的Json根节点（并列包含Json对象和Json对象、Json对象和Json数组、Json数组和Json数组），根节点只能有一个。

• 正确的写法

1
2
3
4
5
6
7
8
9
10
11
12
13

// test.json
{
    "Name":"Ace",
    "Sex":"man",
    "Age":20,
    "Family":{
        "Father":"Gol·D·Roger",
        "Mother":"Portgas·D·Rouge",
        "Brother":["Sabo", "Monkey D. Luffy"]
    },
    "IsAlive":false,
    "Comment":"yyds"
}

在上面的例子中通过Json对象以及Json数组的嵌套描述了一个人的身份信息，并且根节点只有一个就是Json对象，如果还需要使用Json数组或者Json对象描述其他信息，需要将这些信息写入到其他文件中，不要和这个Json对象并列写入到同一个文件里边，切记！！！

作者: 苏丙榅
链接: https://subingwen.cn/qt/json/
来源: 爱编程的大丙
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

概述

如果操作系统崩溃或电源故障，系统主内存的内容可能会丢失。相比之下，非易失性存储是持久的，并且在崩溃和断电时仍能保持其状态。非易失性存储还具有更高的容量和更低的成本。

然而，非易失性存储技术有其自身的缺点。

• 例如，当前的非易失性存储技术（例如磁盘和高密度闪存存储）不允许随机访问单个存储字；相反，访问必须以更粗粒度的单位进行——一次 512、2048 或更多字节。
• 此外，这些访问可能比访问 DRAM 慢得多；

这种巨大的差异（在旋转磁盘的情况下约为五个数量级）促使操作系统以不同于主内存的方式组织和使用持久存储设备。

文件系统是一种常见的操作系统抽象，允许应用程序访问非易失性存储。文件系统使用多种技术来应对非易失性存储设备的物理限制并为用户提供更好的抽象。例如，图 11.1 总结了物理特性如何激发文件系统设计的几个关键方面:

• 性能：文件系统通过对数据的放置位置进行分组来分摊启动昂贵操作的成本，例如移动磁盘臂或擦除固态内存块，以便此类操作访问大范围的连续存储
• 名字：文件系统将相关数据分组到目录和文件中，并为它们提供人类可读的名称（例如，/home/alice/Pictures/summer-vacation/hiking.jpg。）即使在创建文件的程序退出之后，这些数据名称仍然有意义它们帮助用户组织大量存储，并且使用户可以轻松地使用不同的程序来创建、读取和编辑数据。
• 受控共享。文件系统包括有关谁拥有哪些文件以及允许哪些其他用户读取、写入或执行数据和程序文件的元数据
• **可靠性:**文件系统使用事务以原子方式更新多个持久存储块，类似于操作系统如何使用临界区以原子方式更新内存中的不同数据结构

为了获得良好的性能和可接受的可靠性，应用程序编写者和操作系统设计者都必须了解存储设备和文件系统的工作原理。本章和接下来的三章讨论关键问题:

其余部分通过描述典型的 API 和抽象集来介绍文件系统，并概述提供这些抽象的软件层

文件系统抽象

文件系统抽象有两个关键部分：定义数据集的文件和定义文件名称的目录。

1. 文件。文件是文件系统中命名的数据集合。
   1. 文件的信息有两部分：元数据和数据。文件的元数据是操作系统理解和管理的有关文件的信息。例如，文件的元数据通常包括文件的大小、修改时间、所有者及其安全信息，例如文件是否可以由所有者或其他用户读取、写入或执行
   2. 文件的数据可以是用户或应用程序放入其中的任何信息。从文件系统的角度来看，文件的数据只是一个无类型字节数组。

通常，操作系统将文件的数据视为无类型字节数组，将其留给应用程序来解释文件的内容。然而，有时操作系统需要能够解析文件的数据。例如，Linux 支持许多不同的可执行文件类型，例如 ELF 和 a.out 二进制文件以及 tcsh、csh 和 perl 脚本。Linux 通过让可执行文件以标识文件格式的幻数开头来实现此目的。例如，ELF 二进制可执行文件以四个字节 0x7f、0x45、0x4c 和 0x46（ASCII 字符 DEL、E、L 和 F）开头

2. 目录。文件包含系统定义的元数据和任意数据，而目录提供文件的名称。特别是，文件目录是人类可读名称的列表以及从每个名称到特定底层文件或目录的映射。

Volume卷(分区）:

文件系统是以分区为单位来进行管理的：

• 不同的分区都有各自独立的文件系统。一台计算机可以通过在单个逻辑层次结构（目录层次结构）中挂载（安装）多个卷来利用多个卷上存储的文件系统。
• 分区是逻辑磁盘的抽象。
  • 一个磁盘可以对应一个分区
  • 一个磁盘也可以对应多分区。每个分区可以使用各自的文件系统组织数据。
  • 多个磁盘也可以对应一个分区。使得文件系统跨物理磁盘管理

例如，假设 USB 驱动器包含一个带有目录 /Movies 和 /Backup 的文件系统，如图 11.4 所示。如果 Alice 将该驱动器插入她的笔记本电脑，笔记本电脑的操作系统可能会使用路径 /Volumes/usb1/ 挂载 USB 卷的文件系统，如图 11.5 所示。然后，如果 Alice 调用 open(“/Volumes/usb1/Movies/vacation.mov”)，她将从 USB 驱动器卷上的文件系统中打开文件 /Movies/vacation.mov。相反，如果 Bob 将该驱动器插入他的笔记本电脑，则笔记本电脑的操作系统可能会使用路径 /media/disk-1 挂载卷的文件系统，并且 Bob 将使用路径 /media/disk-1/Movies 访问同一文件/vacation.mov。

API

文件系统的软件层次

如图11.7所示，操作系统通过一系列软件层来实现文件系统抽象。从广义上讲，这些层有两组任务：

• 向上 提供API给用户 软件堆栈的顶层——库、内核级文件系统和内核的块缓存——提供了一个方便的API来访问命名文件，并通过缓存、写缓冲（延迟写，回写）和预取来最大限度地减少缓慢的存储访问
• 向下 提供设备访问。 软件堆栈的较低级别为操作系统提供了访问各种 I/O 设备的方法。 设备驱动程序通过为每个设备提供专用于此硬件的代码，并将该代码放置在操作系统其余部分可以使用的更简单、更通用的接口（例如块设备接口）后面，隐藏特定 I/O 硬件的详细信息。设备驱动程序使用系统的主处理器和内存作为正常的内核级代码执行，但它们（CPU和内存）必须与 I/O 设备交互。系统的处理器和内存使用内存映射 I/O、DMA 和中断与其 I/O 设备进行通信。

在其余部分中，我们首先讨论文件系统 API 和性能层。然后我们讨论设备访问。

API

文件系统软件堆栈的顶层（分为应用程序库和操作系统内核代码）提供文件系统 API，并提供缓存和写入缓冲以提高性能。

• 系统调用和库。文件系统抽象（如图 11.6 所示的 API）可以直接由系统调用提供。或者，应用程序库可以包装系统调用以添加附加功能，例如缓冲(系统调用IO和标准库IO就这样)
  • 后者（c库函数）的优点是该库包含缓冲区，可将程序的小型读取和写入聚合到访问较大块的系统调用中，从而减少开销。例如，如果程序使用库函数 fread() 读取 1 个字节的数据，则 fread() 实现可以使用 read() 系统调用将更大的数据块（例如 4 KB）读取到维护的缓冲区中通过应用程序地址空间中的库。然后，如果进程再次调用 fread() 来读取另一个字节，则库只需从缓冲区返回该字节，而无需执行系统调用。
• 块缓存 Block cache：典型的存储设备比计算机的主内存慢得多。因此，操作系统的块缓存会缓存最近读取的块，并缓冲最近写入的块，以便稍后将它们写回存储设备。
  • 除了通过缓存和写缓冲提高性能之外，块缓存还充当同步点：因为对给定块的所有请求都经过块缓存，所以操作系统在每个缓冲区缓存条目中包含信息，例如，阻止进程在另一个进程写入块时读取该块，或者确保给定的块仅从存储设备中获取一次，即使它被许多进程同时读取。
• 预取Prefetching。操作系统使用预取来提高 I/O 性能。例如，如果进程读取文件的前两个块，操作系统可能会预取接下来的十个块

设备驱动程序：通用抽象

设备驱动程序在操作系统实现的高级抽象与I/O设备的硬件特定细节之间转换。

操作系统可能必须处理许多不同的I/O设备。

例如，笔记本电脑可能连接到两个键盘（一个内部和一个外部），触控板，一只鼠标，一个有线以太网，无线802.11网络，一个无线蓝牙网络，两个磁盘驱动器（一个内部和一个磁盘驱动器（一个外部），麦克风，扬声器，相机，打印机，扫描仪和USB拇指驱动器。这只是当今可以连接到计算机的数千台设备中的少数。构建一个分别处理每种情况的操作系统将是不可能的。

分层提供了访问各类设备的通用方法，有助于简化操作系统。例如，对于任何给定的操作系统，存储设备驱动程序通常实现标准块设备接口，允许以固定大小的块（例如，512、2048 或 4096 字节）读取或写入数据。

在标准块设备接口上运行的文件系统可以将文件存储在任何存储设备上，只要该存储设备的驱动程序实现了该接口，无论是 Seagate 旋转磁盘驱动器、Intel 固态驱动器、Western Digital RAID 还是 Amazon Elastic Block Store 卷。这些设备都有不同的内部组织和控制寄存器，但如果每个制造商都提供导出标准接口的设备驱动程序，则操作系统的其余部分无需关心这些每个设备的详细信息

设备访问

操作系统的设备驱动程序应如何与存储设备通信并控制存储设备？乍一看，存储设备似乎与我们迄今为止讨论的内存和 CPU 资源有很大不同。例如，磁盘驱动器包括多个电机、用于读取数据的传感器和用于写入数据的电磁体。

内存映射IO （还有个端口映射IO）

端口映射IO：提供额外的 I/O 指令

内存映射 I/O（memory- mapped I/O）：硬件将设备寄存器作为内存地址提供。

端口映射 I/O 在物理内存地址受限的体系结构中非常有用，因为 I/O 设备不需要消耗物理内存地址范围。另一方面，对于具有足够大物理地址空间的系统，内存映射 I/O 可以更简单，因为不需要定义新指令或地址范围，并且设备驱动程序可以使用任何标准内存访问指令来访问设备。此外，内存映射 I/O 提供了更统一的模型来支持 DMA—-I/O 设备和主存之间的直接传输

每个 I/O 设备都有一个带有一组寄存器的控制器，可以写入和读取这些寄存器，以将命令和数据传输到设备或从设备传输命令和数据。例如，一个简单的键盘控制器可能有一个寄存器，可以通过读取该寄存器来了解最近按下的按键，以及另一个可以写入的寄存器来打开或关闭大写锁定灯。为了允许读写 I/O 控制寄存器，系统实现了内存映射 I/O。内存映射 I/O 将每个设备的控制寄存器映射到内存总线上的一系列物理地址。 CPU 对此物理地址范围的读取和写入不会进入主内存。相反，它们会访问 I/O 设备控制器上的寄存器。

DMA

许多 I/O 设备（包括大多数存储设备）都会批量传输数据。例如，操作系统不会从磁盘读取一两个字，它们通常一次至少传输几千字节。 I/O 设备可以使用直接内存访问，而不是要求 CPU 读取或写入大量传输的每个字。当使用直接内存访问 (DMA) 时，I/O 设备在其自己的内存和系统主内存之间复制数据块。为了设置 DMA 传输，简单的操作系统可以使用内存映射 I/O 来向设备提供目标物理地址、传输长度和操作代码。然后，设备将数据复制到目标地址或从目标地址复制数据，而无需额外的处理器参与。设置 DMA 传输后，在 DMA 传输完成之前，操作系统不得将目标物理页用于任何其他目的。因此，操作系统将目标页面“固定”在内存中，以便在取消固定之前无法重用它们。例如，固定的物理页无法交换到磁盘，然后重新映射到其他虚拟地址。

为了设置 DMA 传输，简单的操作系统可以使用内存映射 I/O 来向设备提供目标物理地址、传输长度和操作代码。然后，设备将数据复制到目标地址或从目标地址复制数据，而无需额外的处理器参与。设置 DMA 传输后，在 DMA 传输完成之前，操作系统不得将目标物理页用于任何其他目的。因此，操作系统将目标页面“固定”在内存中，以便在取消固定之前无法重用它们。例如，固定的物理页无法交换到磁盘，然后重新映射到其他虚拟地址

中断

操作系统需要知道 I/O 设备何时完成对请求的处理或者新的外部输入何时到达。一种选择是轮询，即重复使用内存映射 I/O 来读取设备上的状态寄存器。由于 I/O 设备通常比 CPU 慢得多，并且 I/O 设备接收的输入可能以不规则的速率到达，因此 I/O 设备通常最好使用中断来通知操作系统重要事件

将它们放在一起：简单的磁盘请求

当进程发出像 read() 这样的系统调用来将数据从磁盘读取到进程的内存中时，操作系统会将调用线程移至等待队列。然后，操作系统使用内存映射 I/O 来告诉磁盘读取请求的数据并设置 DMA，以便磁盘可以将该数据放入内核内存中。然后磁盘读取数据并将其 DMA 到主内存中；一旦完成，磁盘就会触发中断。然后，操作系统的中断处理程序将数据从内核缓冲区复制到进程的地址空间中。最后，操作系统将线程移动到就绪列表中。当线程下次运行时，它将从系统调用中返回，数据现在存在于指定的缓冲区中。

磁盘

根据存储器层次结构，磁盘容量大但访问速度极其慢。

并且磁盘设备不像内存设备是通用的（所有内存几乎具有一致的访问接口）

不同的磁盘特性各不相同（所以需要后面的文件系统软件统一这些接口，抽象思想）

• 访问粒度不同：内存可以按字节粒度访问，磁盘的访问单位至少要几百字节。
• 访问速度（时间）不同：内存可以随机访问，磁盘能在顺序访问，如果要访问不连续的位置吗，需要机械运动（慢）

磁盘结构

磁盘驱动器存储数据的原理是 通过磁性将写入到快速旋转的金属薄盘上。

一个完整的磁盘结构组成：

• 磁头：每个表面都有一个磁头，能够按同心圆读取数据。

  • 为了达到整个表面（任意一个磁道），每个磁头都连接到一个磁臂，所有磁臂连接到同一臂杆（可以由内向外反复移动）。所以所有磁头都是同时移动的。

• 盘片（可能有多个）：容纳磁性材料的薄圆板。通常两面（两面都可存储数据）。盘片不断旋转。

• 磁道(track)：每个盘片被划分为一圈一圈的有一定宽度的同心圆，这就是磁道。

  • 磁盘可以在无需移动磁臂的情况下，读取同一磁道的所有数据（因为盘片在转）。所以磁盘访问同一磁道上的数据，比不同磁道上的要快。

• 扇区（sector）：扇区是磁盘的最小访问单元（一般为，512B），磁盘不能读取单个字节。它必须至少读取或写入一个扇区。

  • 操作系统如果要更改磁盘中的一个字节，就不得不读取整个扇区，然后写入整个扇区。（这是个问题，解决办法：延迟磁盘的读写。）

• 柱面：

  • 一些早期的文件系统将相关数据放在不同的表面但在同一个柱面中。这个想法是可以读取来自柱面中不同磁道的数据，而无需进行寻道。一旦柱面已满，文件系统就会开始将数据放置在相邻柱面之一中。随着磁盘密度的增加，柱面的重要性下降了。如今，访问同一柱面内的不同磁道的成本与访问同一盘片上相邻磁道的成本大致相同。

两点实现细节：

1. 轨道倾斜（track skewing）：为了最大化顺序存取速度，每个磁道上的逻辑扇区零与前一磁道上的扇区零错开一定量，该量对应于磁盘将磁头 从一个磁道移动到另一磁道，或者 从一个表面上的磁头切换到另一个表面上的磁头扇区往往会偏斜，因为从一个磁道切换到另一个磁道时，磁盘需要时间来重新定位磁头（即便移到相邻磁道）。如果没有这种偏斜，磁头将移动到下一个磁道，但所需的下一个块已经旋转到磁头下，因此驱动器将不得不等待整个旋转延迟，才能访问下一个块。
2. 另一个事实是，外圈磁道通常比内圈磁道具有更多扇区，这是几何结构的结果。那里空间更多。这些磁道通常被称为多区域（multi-zoned）磁盘驱动器，其中磁盘被组织成多个区域，区域是表面上连续的一组磁道。每个区域每个磁道具有相同的扇区数量，并且外圈区域具有比内圈区域更多的扇区。

磁盘驱动器通常包含几 MB 的缓冲内存(buffer memory)，磁盘控制器使用该内存来缓冲从磁盘读取或写入磁盘的数据、用于磁道缓冲和写入加速。

• 磁道缓冲（track buffering）： 预读

  磁道缓冲通过存储磁头已读取但操作系统尚未请求的扇区来提高性能。特别是，当磁头移动到磁道时，它可能必须等待其需要访问的扇区在磁头下方旋转。当磁盘等待时，它将未请求的扇区读取到其机架缓冲区，以便如果操作系统稍后请求这些扇区，它们可以立即返回。

• 写入加速（write acceleration）：延迟写(后写，write back)

  将要写入的数据存到自己的内存中，就向操作系统报告（写入）。磁盘固件稍后将写入内容从内存刷新到盘片。后写缓存有时会使驱动器看起来“更快”，但可能有危险。如果文件系统或应用程序要求将数据按特定顺序写入磁盘以保证正确性，后写缓存可能会导致问题（请阅读文件系统日志的章节以了解详细息）。

磁盘访问过程和性能

通过一个场景来查看磁盘的访问过程：操作系统向磁盘发出读取一个或多个连续扇区的请求（命令）。

磁盘扇区通过逻辑块地址（logical block address，LBA）来指定要访问的盘面，磁道和扇区

LBA: 每个磁盘扇区或闪存块的唯一标识符，通常编号从 1 到磁盘/闪存设备的大小。磁盘接口将此标识符转换为扇区的物理位置。

为了响应操作系统的请求：

磁盘必须

• 首先寻找（seek）正确的磁道，【寻道，Seek】
• 等待第一个所需扇区旋转到磁头，【旋转，Rotate】
• 然后传输块。【传输，Transfer】

因此，一次磁盘访问的时间为：

1

磁盘访问时间=寻道时间+旋转时间+传输时间

• 寻道：

磁盘必须首先寻找——将其臂移动到所需的磁道上。为了进行寻道，磁盘首先启动电机，将臂组件移动到磁盘上大致正确的位置。然后，当磁臂停止因寻道运动而振动时，磁盘开始读取嵌入在扇区中的定位信息，以确定其准确位置，并进行细粒度的定位校正以固定在所需的磁道上。一旦磁头定位在正确的磁道上，磁盘就会使用信号强度和定位信息对磁臂位置进行微小修正，以将磁头保持在所需的磁道上

• 旋转：

一旦磁盘头定位在正确的磁道上，它必须等待目标扇区在其下方旋转。该等待时间称为旋转延迟。如今，大多数磁盘的旋转速度为 4200 RPM 到 15,000 RPM（每次旋转 15 毫秒到 4 毫秒），对于许多工作负载，旋转延迟的合理估计是完整旋转时间的一半 — 7.5 毫秒到 2 毫秒

一旦磁盘头确定在新磁道上，大多数磁盘立即开始将扇区读入其缓冲存储器，无论请求了哪些扇区。这样，如果有对已经通过磁头下方的扇区之一的请求，则可以立即传输数据，而不必延迟近一个完整旋转的请求来重新读取数据。

• 传输：

  • 一旦磁盘头到达所需的扇区，当扇区在磁头下方旋转时，磁盘必须将数据从该扇区传输到其缓冲存储器（用于读取），反之亦然（用于写入）。然后，对于读取，它必须将数据从其缓冲存储器传输到主机的主存储器。对于写入，传输顺序相反

  • 由于磁盘的外部磁道比其内部磁道具有容纳更多扇区的空间，并且由于给定磁盘以恒定速率旋转，因此外部磁道的表面传输带宽通常高于内部磁道。

  • 对于磁盘读取，一旦扇区已传输到磁盘的缓冲存储器，它们必须通过某些连接传输到主机的内存，例如 SATA（串行 ATA）、SAS（串行连接 SCSI）、光纤通道或 USB（通用串行bus）。对于写入，传输朝另一个方向进行。主机内存和磁盘缓冲区之间传输数据的时间就是主机传输时间。典型带宽范围为USB 2.0的60 MB/s 到光纤通道的2500 MB/s。

  • 对于多扇区读取，磁盘在表面和磁盘缓冲存储器之间以及缓冲存储器和主机内存之间进行管道(串行）传输；因此，对于大型传输，总传输时间将由其中的瓶颈决定。类似地，对于写入，磁盘将主机传输与寻道、旋转和表面传输重叠；同样，总传输时间将由瓶颈决定。

案例研究 ： 东芝 MK3254GSY

图 12.3 显示了最新的笔记本电脑 2.5 英寸磁盘的一些关键参数。

Platters/Heads 2/4：两个盘（四个盘面），四个磁头

• Spindle speed 7200 RPM:该磁盘将320 GB的数据存储在两个盘片上，因此每盘面存储80 GB。盘片以每分钟7200RPM（每分钟转数）旋转，每转为8.3ms；由于每个盘片的直径约为6.3厘米，因此每个盘片的外边缘以85km/h的速度移动！
• **Average seek time read/write 10.5 ms / 12.0 ms: **读取和写入的寻道时间不同，因为磁盘在磁盘臂完全稳定之前开始尝试读取数据，但必须等待一段时间才能安全写入
• Transfer rate (surface to buffer) ：54–128 MB/s当传输大量连续扇区时，磁盘的带宽为 54-128 MB/s。带宽用一个范围来表示，因为磁盘的外磁道比内磁道有更多的扇区，因此当磁盘访问外磁道上的数据时，扇区以更高的速率扫过磁头
• Transfer rate (buffer to host) 375 MB/s：一旦数据从盘片上传输出来，磁盘就可以通过 SATA（串行 ATA）接口【现代SATA已经过时了。有更快的PCIE等】以高达 375 MB/s 的速度将其发送到计算机的主内存。

随机与顺序访问性能

给定的寻求和旋转时间以毫秒为单位，对磁盘上随机扇区的小访问比大的顺序访问要慢得多

磁盘调度

由于移动磁盘臂和等待盘片旋转的成本非常高，因此通过优化待处理请求的服务顺序可以显着提高性能。磁盘调度可以由操作系统、磁盘固件或两者共同完成。

先进先出。最简单的做法是按照先进先出 (FIFO) 的顺序处理请求。不幸的是，FIFO 调度程序的性能可能很差。

SPTF/SSTF。一个最初有吸引力的选择是使用贪婪调度程序，在给定磁盘头和盘片的当前位置的情况下，该调度程序始终为可以在最短时间内处理的待处理请求提供服务。这种方法称为最短定位时间优先 (SPTF)（如果不考虑旋转定位，则称为最短寻道时间优先 (SSTF)）。

SPTF 和 SSTF 有两个明显的局限性。首先，由于移动磁盘臂并等待一些旋转时间会影响服务后续请求的成本，因此这些贪婪方法并不能保证优化磁盘性能。其次，这些贪婪的方法可能会导致饥饿，例如，当对内部轨道的连续请求流阻止对外部轨道的请求得到服务时。

网络层及其协议IP

我们将主要讨论互联网寻址——对于理解互联网网络层的工作原理至关重要。

掌握IP寻址就是掌握互联网的网络层本身。

IPV4 数据报格式

IPv4数据报格式如图4.17所示。 IPv4数据报中的关键字段如下：

• 版本号
• 头部长度
• 服务类型
• 数据报长度
• 标识符
• 生存时间TTL
• 协议
• 头部校验和
• 源和目的IP地址
• 选项
• 数据

请注意，IP 数据报总共有 20 个字节的报头（假设没有选项）。如果数据报携带 TCP 报文段，则每个数据报携带总共 40 字节的报头（20 字节 IP 报头加 20 字节 TCP 报头）以及应用层消息。

IPv4 寻址

然而，在讨论 IP 寻址之前，我们需要先介绍一下主机和路由器如何连接到互联网。

主机通常只有一个连接到网络的链路；当主机中的 IP 想要发送数据报时，它会通过此链接进行发送。主机和物理链路之间的边界称为接口interface。

现在考虑路由器及其接口。由于路由器的工作是在一个链路上接收数据报并在其他链路上转发该数据报，因此路由器必须连接两个或多个链路。路由器与其任一链路之间的边界也称为接口。因此，路由器具有多个接口，每个接口对应其每条链路。由于每个主机和路由器都能够发送和接收 IP 数据报，因此 IP 要求每个主机和路由器接口都有自己的 IP 地址。

因此，IP 地址与接口相关联，而不是与包含该接口的主机或路由器相关联

全球互联网中每台主机和路由器上的每个接口都必须有一个全球唯一的 IP 地址（NAT 后面的接口除外，如第 4.3.3 节所述）。然而，这些地址不能随意选择。接口 IP 地址的一部分将由其连接的子网确定。

图 4.18 提供了 IP 寻址和接口的示例。在该图中，一台路由器（具有三个接口）用于互连七台主机。仔细查看分配给主机和路由器接口的 IP 地址，有几件事需要注意。

• 图 4.18 左上部分的三台主机以及它们所连接的路由器接口都具有 223.1.1.xxx 形式的 IP 地址。也就是说，它们的 IP 地址都具有相同的最左边 24 位。
• 这四个接口也通过不包含路由器的网络相互互连。该网络可以通过以太网 LAN 互连，在这种情况下，接口将通过以太网交换机（我们将在第 6 章中讨论）或无线接入点（我们将在第 7 章中讨论）互连。我们暂时将连接这些主机的无路由器网络表示为云，并在第 6 章和第 7 章中深入研究此类网络的内部结构

在 IP 术语中，该网络互连三个主机接口和一个路由器接口形成一个子网。 （子网也称为 IP 网络或简称为网络）

223.1.1.0/24:

• /24： 子网掩码，表示32位数量的最左边24位定义子网地址

从上面的讨论可以清楚地看出，具有多个以太网段和点对点链路的组织将拥有多个子网，给定子网上的所有设备都具有相同的子网地址。

原则上，不同的子网可以具有完全不同的子网地址。但实际上，它们的子网地址通常有很多共同点。为了理解其中的原因，接下来让我们将注意力转向互联网中如何处理寻址。

互联网的地址分配策略称为无类别域间路由CIDR 。

CIDR 泛化了子网寻址的概念。与子网寻址一样，32 位 IP 地址分为两部分，并再次采用点分十进制形式 a.b.c.d/x，其中 x 表示地址第一部分的位数。

a.b.c.d/x

• 地址的 x 个最高有效位构成 IP 地址的网络部分，通常称为地址的前缀（或网络前缀）。通常会为组织分配一个连续地址块，即具有公共前缀的一系列地址。在这种情况下，组织内的设备的 IP 地址将共享公共前缀。当外部路由器转发此子网中的数据时，就只需考虑网络前缀就可以进入到此子网中，而不用考虑后面的位。
• 地址的其余 32-x 位识别组织中的设备（主机部分），所有设备都具有相同的网络前缀。这些是在组织内的路由器上转发数据包时要考虑的位。这些低阶位可以（或可以不）具有额外的子网划分结构。

例如，假设地址 a.b.c.d/21 的前 21 位指定组织的网络前缀，其余 11 位则标识组织中的特定主机。

但可以继续用这11个主机位，继续划分子网：

• a.b.c.d/24：前24位都是属于子网，只有后8位标识主机。
• a.b.c.d/30:前30位都是属于子网，只有后两位标识主机。

地址聚合（路由聚合、路由汇总）

通过ISP的无分类编址，使得同一组织内的所有主机都通过最大的IP地址来寻址，内部细节不需要外界路由器关心。

这种使用单个前缀(分配给组织的那个顶级子网)通告多个网络（组织内部细分的许多网络）的能力通常称为地址聚合（也称为路由聚合或路由汇总）

广播地址

如果我们没有提到另一种类型的 IP 地址，即 IP 广播地址 255.255.255.255，那就是我们的失职。当主机发送目标地址为 255.255.255.255 的数据报时，该消息将传递到同一子网上的所有主机。路由器也可以选择将消息转发到相邻子网（尽管它们通常不这样做）

组织如何获得一组地址

一个组织或者企业如何获取一组用于本组织内部的IP地址呢？

• 方法1：通过中介ISP（ISP本身已经从互联网名称与数字地址分配机构 (ICANN)）获取一大块地址）

• 方法2：直接向ICANN申请IP地址。

获取主机地址：动态主机配置协议( DHCP)

一旦组织获得了地址块，它就可以将单独的 IP 地址分配给组织中的主机和路由器接口。

路由器中的IP地址通常是手动配置的（通常使用网络管理工具进行远程配置）

主机地址也可以手动配置，但这通常是使用动态主机配置协议（DHCP）[RFC 2131]完成的。

DHCP 允许主机自动获取（分配）IP 地址。网络管理员可以配置 DHCP，以便给定主机每次连接到网络时都会收到相同的 IP 地址，或者可以为主机分配一个临时 IP 地址，该地址每次连接到网络时都会有所不同。

除了主机 IP 地址分配之外，DHCP 还允许主机了解其他信息

• 子网掩码、
• 第一跳路由器的地址（通常称为默认网关）
• 本地 DNS 服务器的地址。

DHCP 是一种客户端-服务器协议。客户端通常是想要获取网络配置信息的新到达的主机。

在最简单的情况下，每个子网都有一个 DHCP 服务器。如果子网上没有服务器，则需要有DHCP服务器的中继代理（通常是路由器）。图 4.23 显示了连接到子网 223.1.2/24 的 DHCP 服务器，路由器充当连接到子网 223.1.1/24 和 223.1.3/24 的到达客户端的中继代理。在下面的讨论中，我们假设子网上有 DHCP 服务器可用。

对于新到达的主机，DHCP 协议是一个四步过程，如图 4.24 所示，网络设置如图 4.23 所示。在此图中，yiaddr（如“您的互联网地址”）表示分配给新到达的客户端的地址。这四个步骤是：

• DHCP 服务器发现：找到与客户端交互的DHCP服务器。通过发送DHCP发现消息完成的（UDP协议）：
  • 由于此时不知道目的IP，自己也没有IP。
  • 所以发送源IP为0.0.0.0目的IP为255.255.255.255的广播，发现DHCP服务器。
• DHCP 服务器提供者：
  • 收到发现消息的服务器也会发送一个DHCP offer message，这个消息也是一个广播消息。(因为新客户端没有被分配IP，所以只能广播)。
  • 通常会有多个服务器响应客户端，从而各自发送这条消息。
• DHCP 请求：
  • 客户端在收到（数条）提供者的回应信息之后，选择其中一个，向他发送DHCP request message。
• DHCP ACK
  • ​ 服务器用 DHCP ACK message响应 DHCP 请求消息，确认请求的参数。

网络地址转换

支持 NAT 的路由器在外界看来并不像路由器。相反，NAT 路由器对于外界来说就像具有单个 IP 地址的单个设备。

本质上，启用 NAT 的路由器向外界隐藏了家庭网络的详细信息。

如果从 WAN 到达 NAT 路由器的所有数据报都具有相同的目标 IP 地址，那么路由器如何知道应将数据转发到哪个内部主机？技巧是在 NAT 路由器上使用 NAT 转换表，并在表条目中包含端口号和 IP 地址。

考虑图 4.25 中的示例。假设位于主机 10.0.0.1 后面的家庭网络中的用户请求 IP 地址为 128.119.40.186 的某个 Web 服务器（端口 80）上的网页。主机 10.0.0.1 分配了源端口号 3345 并将数据报发送到 LAN。 NAT路由器收到数据报后，为该数据报生成新的源端口号5001，并用其WAN侧IP地址138.76.29.7替换源IP地址，并用新的源端口号5001替换原来的源端口号3345。当生成新的源端口号时，NAT 路由器可以选择当前不在 NAT 转换表中的任何源端口号。 （请注意，由于端口号字段为 16 位长，因此 NAT 协议可以通过路由器的单个 WAN 侧 IP 地址支持超过 60,000 个同时连接！）路由器中的 NAT 还会在其 NAT 转换表中添加一个条目。 Web 服务器完全没有意识到包含 HTTP 请求的到达数据报已被 NAT 路由器操纵，它以目标地址为 NAT 路由器的 IP 地址、目标端口号为 5001 的数据报进行响应。当该数据报到达时在 NAT 路由器处，路由器使用目标 IP 地址和目标端口号索引 NAT 转换表，以为家庭网络中的浏览器获取适当的 IP 地址（10.0.0.1）和目标端口号（3345）。然后路由器重写数据报的目标地址和目标端口号，并将数据报转发到家庭网络。

近年来，NAT 得到了广泛的部署。但 NAT 也并非没有批评者。首先，有人可能会争辩说，端口号旨在用于寻址进程，而不是用于寻址主机。这种违规确实会给在家庭网络上运行的服务器带来问题，因为正如我们在第 2 章中所看到的，服务器进程在众所周知的端口号处等待传入请求，P2P 协议中的对等点在充当服务器时需要接受传入连接。一个对等点如何连接到位于 NAT 服务器后面且具有 DHCP 提供的 NAT 地址的另一个对等点？

在P2P应用程序中，任何参与对等方A应当能够对任何其他参与的对等方B发起一条TCP连接。所以该问题实质在于，如果对等方B在一个NAT后面，那么它将不能充当服务器并接受TCP连接。（A单独无法得知B的地址）

现在假设对等方A不在NAT后面，对等方B在NAT后面，对等方C不在NAT后面。C与B已经创建了一条TCP连接，如果A想与B创建连接，则需要通过C请求对等方B，发起直接返回对等方A的一条TCP连接。一旦二者建立一条直接的P2P TCP连接，两个对等方就可以交换报文或文件了。

这种雇佣关系被称为连接反转（connection reversal），已被许多P2P应用程序用于NAT穿越（NAT traversal）。

若A，B二者都在NAT后面则可使用应用程序进行中继处理。

IPV6

路由器结构

已经概述了网络层内的数据和控制平面、转发和路由之间的重要区别以及网络层的服务和功能。

我们将注意力转向网络层的转发功能——数据包从路由器的传入链路到该路由器相应的传出链路的实际传输。

图 4.4 显示了通用路由器架构的高级视图。可以识别四个路由器组件：

1. 输入端口：输入端口执行几个关键功能。
   1. perform the physical layer function of terminating an incoming physical link at a router。这显示在图4.4中输入端口的最左侧框和输出端口的最右边框。
   2. also perform link-layer functions needed to interoperate with the link layer at the other side of the incoming link。这由输入和输出端口中的中间框表示。
   3. a lookup function is also performed at the input port这将发生在输入端口的最右边框中。在这里，查询转发表以确定到达的数据包将通过交换结构转发到路由器的哪个输出端口。控制数据包（例如，携带路由协议信息的数据包）从输入端口转发到路由处理器
   4. 请注意，这里的“端口”一词 - 引入物理输入和输出路由器接口 - 与第2章和第3章中讨论的与网络应用程序和socket相关的软件端口明显不同。
2. 交换结构：交换结构将路由器的输入端口连接到其输出端口。此交换结构完全包含在路由器内——网络路由器内的网络
3. 输出端口：
4. 路由处理器：

路由器的输入端口、输出端口和交换结构几乎总是以硬件实现，如图 4.4 所示。（在下层）

因为软件跟不上速度。

要理解为什么需要硬件实现，请考虑使用 100 Gbps 输入链路和 64 字节 IP 数据报，输入端口只有 5.12 纳秒的时间来处理数据报，然后另一个数据报才会到达。如果 N 个端口组合在线卡上（实践中经常这样做），数据报处理管道必须以 N 倍的速度运行——对于软件实现来说太快了

当数据平面以纳秒时间尺度运行时，路由器的控制功能（执行路由协议、响应向上或向下的附加链路、与远程控制器通信（在 SDN 情况下）以及执行管理功能）运行在毫秒或秒的时间尺度上。

因此，这些控制平面功能通常以软件实现并在路由处理器（通常是传统 CPU）上执行。

在深入研究路由器内部细节之前，让我们回到本章开头的类比，其中将数据包转发与进入和离开立交桥的汽车进行比较。假设立交桥是一个环岛，当汽车进入环岛时，需要进行一些处理。让我们考虑一下此处理需要哪些信息:

基于目的地的转发。假设汽车停在入口站并指示其最终目的地（不是当地的环岛，而是其旅程的最终目的地）。入口站的工作人员会查找最终目的地，确定通往最终目的地的环岛出口，并告诉司机要走哪个环岛出口。

通用转发。除了目的地之外，乘务员还可以根据许多其他因素来确定汽车的出口坡道。例如，所选的出口坡道可能取决于汽车的来源，例如颁发汽车牌照的州。来自某一组州的汽车可能会被指示使用一个出口坡道（通过慢速道路通向目的地），而来自其他州的汽车可能会被指示使用不同的出口坡道（通过超级道路通向目的地）高速公路）。可能会根据汽车的型号、品牌和年份做出相同的决定。或者，一辆不适合上路的汽车可能会被封锁，不被允许通过环岛。在通用转发的情况下，许多因素都可能影响乘务员为给定汽车选择出口坡道

一旦车辆进入环岛（其中可能挤满了从其他输入道路进入并前往其他环岛出口的其他车辆），它最终会在规定的环岛出口坡道处离开，在那里它可能会遇到在该出口离开环岛的其他车辆。通过这个类比，我们可以很容易地识别出图 4.4 中的主要路由器组件——入口道路和入口站对应于输入端口（具有查找功能以确定本地输出端口）；环岛对应于交换结构；环岛出口道路对应输出口。通过这个类比，考虑瓶颈可能出现在哪里是有启发性的。如果汽车到达速度极快（例如，环岛在德国或意大利！）但车站服务员却很慢，会发生什么？服务员必须以多快的速度工作才能确保入口道路上没有后援？即使有速度极快的服务员，如果汽车缓慢地穿过环岛——还能进行倒车吗？如果进入环岛所有入口坡道的大多数车辆都想在同一个出口坡道离开环岛，会发生什么情况——可以在出口坡道或其他地方进行备份吗？如果我们想为不同的车辆分配优先级，或者首先阻止某些车辆进入环岛，那么环岛应该如何运行？这些都类似于路由器和交换机设计人员面临的关键问题。

为了具体和简单起见，我们最初在本节中假设转发决策仅基于数据包的目标地址，而不是基于一组通用的数据包标头字段。

我们将在 4.4 节中介绍更广义的数据包转发情况

输入端口处理和基于目的地的转发

输入处理的更详细视图如图 4.5 所示。

正如刚才所讨论的，输入端口的线路终止功能和链路层处理实现了各个输入链路的物理层和链路层。

在输入端口中执行的查找是路由器操作的核心——路由器在这里使用转发表来查找输出端口，到达的数据包将通过交换结构转发到该输出端口。

转发表要么由路由处理器计算和更新（使用路由协议与其他网络路由器中的路由处理器交互），要么从远程 SDN 控制器接收。

转发表通过单独的总线（例如 PCI 总线）从路由处理器复制到线卡，如图 4.4 中从路由处理器到输入线卡的虚线所示。

通过每个线卡上的副本，可以在每个输入端口本地做出转发决策，而无需针对每个数据包调用集中式路由处理器，从而避免集中式处理瓶颈。

现在让我们考虑“最简单”的情况，即传入数据包要交换到的输出端口基于数据包的目标地址。

对于 32 位 IP 地址，转发表的暴力解法将为每个可能的目标地址都有一个条目。由于可能的地址超过 40 亿个，因此该选项完全不可能。

实际做法是：

将IP地址划分范围，每个范围指定一个转发端口。然后使用最长前缀匹配算法，匹配最合适的范围，如果全部都没匹配，则走默认端口。（有点像switch）

而不是每个Ip地址都对应一个端口号。

• 有了转发表，查找在概念上很简单——硬件逻辑只是搜索转发表以查找最长的前缀匹配。但在千兆位传输速率下，此查找必须在纳秒内完成（所以查找的复杂度也不能太高））。

• 一旦通过查找确定了数据包的输出端口，就可以将数据包发送到交换结构中。在某些设计中，如果来自其他输入端口的数据包当前正在使用交换结构，则可能会暂时阻止数据包进入交换结构。被阻止的数据包将在输入端口排队，然后安排在稍后的时间点穿过交换结构。

• 输入端口除了查找，还要采取许多其他操作：

  • 必须进行物理层和链路层处理，如前所述；
  • 必须检查数据包的版本号、校验和和生存时间字段并重写后两个字段；
  • 用于网络管理的计数器（例如接收到的IP数据报的数量）必须更新。

查找目标 IP 地址（“匹配”）然后将数据包发送到交换结构再到指定输出端口（“操作”）的输入端口步骤是更一般的“匹配加操作”抽象的特定情况，即在许多联网设备中执行，而不仅仅是路由器。

在链路层交换机（第 6 章中介绍）中，查找链路层目标地址，并且除了将帧发送到交换结构并朝向输出端口之外，还可以采取多种操作。

在防火墙（第 8 章介绍）中（过滤选定的传入数据包的设备），如果传入数据包的报头符合给定的标准（例如，源/目标 IP 地址和传输层端口号的组合），则可能会被丢。

在网络地址转换器（NAT，第 4.3 节中介绍）中，传输层端口号与给定值匹配的传入数据包将在转发（操作）之前重写其端口号。

事实上， the “match plus action” abstraction在当今的网络设备中既强大又普遍，并且是广义转发概念的核心。

交换（结构）

交换结构是路由器的核心，因为数据包实际上是通过该结构从输入端口交换（即转发）到输出端口的。交换可以通过多种方式完成，如图4.6所示：

• 通过内存交换：最简单、最早的路由器是传统计算机，输入和输出端口之间的交换是在 CPU（路由处理器）的直接控制下完成的。输入和输出端口在传统操作系统中充当传统I/O设备。输入端口首先通过中断向路由处理器发出信号。然后，数据包从输入端口复制到处理器内存中。然后，路由处理器从报头中提取目标地址，在转发表中查找适当的输出端口，并将数据包复制到输出端口的缓冲区。在这种情况下，如果内存带宽使得每秒最多可以将 B 个数据包写入内存或从内存中读取，则总体转发吞吐量（数据包从输入端口传输到输出端口的总速率）端口）一定小于 B/2。两个数据包不能同时转发，即使他们有不同的目的端口。因为共享系统总线一次只能执行一次内存读/写操作。一些现代路由器通过内存进行切换。然而，与早期路由器的主要区别在于，目标地址的查找以及将数据包存储到适当的内存位置是通过对输入线卡进行处理来执行的。在某些方面，通过内存进行交换的路由器看起来非常像共享内存多处理器，通过线卡上的处理将数据包交换（写入）到适当输出端口的内存中。
• 通过总线交换
• 通过互联网交换

输出端口处理

如图4.7所示的输出端口处理，采用已存储在输出端口内存中的数据包，并通过输出链接传输它们。这包括选择（即调度）和用于传输的出队数据包，并执行所需的链路层和物理层传输功能。

排队在哪发生

如果我们考虑输入和输出端口功能以及图 4.6 中所示的配置，很明显，数据包队列可能在输入端口和输出端口处形成，就像我们识别出汽车可能在输入和输出处等待的情况一样。

现在让我们更详细地考虑这些队列，因为随着这些队列变大，路由器的内存最终可能会耗尽，并且当没有内存可用于存储到达的数据包时，就会发生数据包丢失。回想一下，在我们之前的讨论中，我们说过数据包“在网络内丢失”或“在路由器处丢失”。正是在这里，在路由器内的这些队列中，这些数据包实际上被扔掉和丢失。

数据包调度

现在让我们回到确定排队数据包通过传出链路传输的顺序的问题。由于您自己无疑曾多次排长队等待并观察如何为等待的客户提供服务，因此您无疑熟悉路由器中常用的许多排队规则。先来先服务（FCFS，也称为先进先出，FIFO）。英国人以在公交车站和市场上耐心有序的 FCFS 排队而闻名（“哦，你在排队吗？”）。其他国家/地区以优先权为基础，一类等待的客户比其他等待的客户获得优先服务。还有循环排队，顾客再次被分为不同的类别（如优先级排队），但每个类别的顾客依次获得服务。

• 先进先出
• 优先级
• 循环和赋予权重

参考

计算机网络-自顶向下方法 8th

网络层（数据平面）

现在提供网络层的概述，我们将在本章的以下部分中介绍网络层的数据平面组件。

在4.2节中，我们将深入研究路由器的内部硬件操作，包括输入和输出数据包处理、路由器的内部交换机制以及数据包排队和调度。

在 4.3 节中，我们将了解传统的 IP 转发，其中数据包根据其目标 IP 地址转发到输出端口。我们将遇到 IP 寻址、著名的 IPv4 和 IPv6 协议等等。

在第 4.4 节中，我们将介绍更广义的转发，其中数据包可以基于大量标头值（即，不仅基于目标 IP 地址）转发到输出端口。数据包可能会在路由器处被阻止或重复，或者可能会重写某些标头字段值——所有这些都在软件控制下。这种更通用的数据包转发形式是现代网络数据平面的关键组成部分，包括软件定义网络 (SDN) 中的数据平面。

在 4.5 节中，我们将了解“中间盒(middleboxes)”，它除了转发之外还可以执行其他功能

概述

网络层分解为两个相互作用的部分：

• 数据平面—-网络层中每个路由器的功能
  • 确定到达路由器输入链路之一的数据报【datagram】如何转发到该路由器的输出链路之一。
• 控制平面—-
  • 控制 数据报如何在 源主机和目的主机之间的路由器之间路由。

以前，这些控制平面路由协议和数据平面转发功能是在路由器内一起整体实现的。

软件定义网络（SDN）通过将这些控制平面功能实现为单独的服务（通常在远程“控制器”中）来明确分离数据平面和控制平面。

每个路由器的主要数据平面作用是将数据报从其输入链路转发到其输出链路；网络控制平面的主要作用是协调每个路由器的转发行为，以便数据报最终沿着源主机和目标主机之间的路由器路径进行端到端传输。

转发和路由：数据平面和控制平面

网络层的主要作用——将数据包从发送主机移动到接收主机。

为此，可以确定两个重要的网络层功能：

1. 转发：当数据包到达路由器的输入链路时，路由器必须将数据包移动到适当的输出链路。例如，上图 中从主机 H1 到达路由器 R1 的数据包必须转发到通往 H2 的路径上的下一个路由器。转发仅仅是数据平面中的一个函数。

2. 路由：网络层必须确定数据包从发送方流向接收方时所采用的路由或路径。计算这些路径的算法称为路由算法。例如，路由算法将确定数据包从图中的 H1 流向 H2 的路径。路由是在网络层的控制平面中实现的。

我们将在本书中更准确地使用这些术语。

转发

• 是指将数据包从输入链路接口传输到适当的输出链路接口的路由器本地操作。
• 转发发生在非常短的时间尺度（通常为几纳秒），因此通常在硬件中实现。

路由

• 是指确定数据包从源到目的地所采用的端到端路径的过程。
• 路由发生在更长的时间尺度（通常是几秒），通常是在软件中实现的。

使用我们的驾驶类比，考虑我们的旅行者从宾夕法尼亚州到佛罗里达州的旅行。在这次旅行中，我们的司机在前往佛罗里达州的途中经过了许多交汇处。我们可以将转发视为通过单个立交桥的过程：一辆汽车从一条道路进入立交桥，并确定应该走哪条路离开立交桥。我们可以将路由视为规划从宾夕法尼亚州到佛罗里达州的行程的过程：在出发之前，驾驶员查阅了地图并选择了许多可能的路径之一，每条路径都由一系列在交汇处连接的路段组成。

每个路由器的一个关键元素是其转发表。路由器通过检查到达数据包头部（首部）中的一个或多个字段的值来转发数据包，然后使用这些头部值索引其转发表。存储在转发表条目中的值指示该数据包要转发到的该路由器的哪一个传链路接口。

例如，在图 4.2 中，头字段值为 0110 的数据包到达路由器。路由器索引其转发表并确定该数据包的输出链路接口是接口 2。然后路由器在内部将数据包转发到接口 2。

转发是网络层数据平面功能执行的关键功能。

控制平面：传统方法

路由器的转发表是如何配置的。这是一个至关重要的问题，它揭示了转发（在数据平面中）和路由（在控制平面中）之间的重要相互作用。

• 如图4.2：路由算法决定路由器转发表的内容

在此示例中，路由算法在每个路由器中运行，并且转发和路由功能都包含在路由器内。

一台路由器中的路由算法函数与其他路由器中的路由算法函数进行通信，以计算其转发表的值。

这种通信是如何进行的？

• 通过根据路由协议交换包含路由信息的路由消息！路由算法和协议。

转发和路由的不同目的可以通过考虑假设的（不现实的，但技术上可行的）网络情景来进一步说明，其中所有转发表均由物理上存在于路由器处的人类网络操作员直接配置。在这种情景下，不需要路由协议！当然，操作员需要相互交互，以确保转发表的配置方式使数据包能够到达其预期目的地。

控制平面：SDN（软件定义网络） 方法

实现路由功能的方法（每个路由器都有一个与其他路由器的路由组件通信的路由组件）一直是路由供应商采用的传统方法。

图 4.3 显示了另一种方法，其中物理上独立的远程控制器计算并分发转发表以供每个路由器使用。

图 4.2 和 4.3 的数据平面组件是相同的。但是，控制平面路由功能与物理路由器是分开的——路由设备仅执行转发，而远程控制器计算和分发转发表

远程控制器可能在具有高可靠性和冗余性的远程数据中心中实现，并且可能由ISP或某些第三方管理。

路由器和遥控器如何通信？

• 通过交换包含转发表和其他路由信息的消息。

图 4.3 所示的控制平面方法是软件定义网络 (SDN) 的核心，其中网络是“软件定义的”，因为计算转发表并与路由器交互的控制器是在软件中实现的。

Internet（网络层）服务模型

在深入研究网络层的数据平面之前，让我们以更广泛的视角来总结我们的介绍，并考虑网络层可能提供的不同类型的服务。

• 当发送主机的传输层将数据包传输到网络中（即，将其向下传递到发送主机的网络层）时，传输层是否可以依赖网络层将数据包传送到目的地？（不可以，不可靠）
• 当发送多个数据包时，它们是否会按照发送的顺序传递到接收主机中的传输层？（不可以，不保证顺序）
• 发送两个连续数据包传输之间的时间量是否与其接收之间的时间量相同？（不，不提供时间保证）
• 网络会提供有关网络拥塞的任何反馈吗？

这些问题和其他问题的答案取决于网络层提供的服务模型。

网络服务模型定义了发送主机和接收主机之间端到端数据包传送的特性：

互联网（Internet）的网络层提供单一服务，称为尽力服务。

对于尽力而为的服务，既不能保证数据包按照发送顺序接收，也不能保证它们的最终交付。无法保证端到端延迟，也没有最小带宽保证。尽力而为服务可能是根本不提供服务的委婉说法。

其他网络架构已经定义并实现了超出互联网尽力服务范围的服务模型。

例如，ATM 网络体系结构 [Black 1995] 提供有保证的有序延迟、有界延迟和有保证的最小带宽。

例如，Intserv 架构 [RFC 1633] 旨在提供端到端延迟保证和无拥塞通信。

我们实现的是一个线程池，他是一个应用的一部分组件，可以算作一个库。并不能算作中间件。因为，他不能够独立完成一个功能或服务。

最终打包成一个动态库供别人使用。

使用方式

1
2
3
4
5
6
7
8
9
10

// 建立线程池对象
ThreadPool	pool;
// 选择模式，固定大小或者可变大小
pool.setMode(fixed(default) | cached);
// 启动线程池
pool.start();
// 提交任务到线程池,返回任务计算完成的的值（可选的返回值，也可能没有）
Result  result = pool.submitTask(concreteTask);
// 获得最终的结果类型
result.get().Cast<>();

还需要一个线程容器存放Thread对象。（也是有大小的）

还需要一个任务容器存放任务对象。（也是有大小的）

任务容器存放的是任务抽象基类（里面有一个纯虚函数run方法），以便可以存放任何任务。用户需要继承task基类来实现自己的任务。

条件变量加互斥锁确保task容器线程安全。

概述

体系结构(协议和物理)实际上是一组设计决策,涉及支持哪些特征和在哪里实现这些特征。

设计一个体系结构更多的是艺术而不是科学,但我们将讨论体系结构中随着时间推移被认为可行的那些特征。

体系结构（架构）和协议族（实现）

协议族

协议的集合

协议族的体系（架构）结构（或参考模型）

• 指定协议族中的各种协议之间的相互关系

• 分工各层协议要完成的任务

体系结构（架构）举例

• ISO体系结构（并不是互联网的体系结构）
  • 内容：七层体系结构，规定了每层之间的关系及其任务
• Internet（当今互联网体系结构）体系结构
  • 内容：4层体系结构，规定了每层之间的关系及其任务。

体系结构的实现

满足体系结构的要求。就叫他的实现

• TCP/IP实现Internet体系结构。

实现方式：

按照体系结构的层次，也分层实现各个协议的任务。及其交互关系。

各层之间的交互方式（通信方式）

• 本层实现自己的协议（自己所要完成的功能）

• 下层利用本层实现的功能（协议）向上层提供服务。

体系结构原则（通用体系结构，不涉及具体的）

Intemet体系结构在几个目标的指导下建立。

首要目标：

体系结构应将多种网络互联起来,并在互联的网络上同时运行多个应用。

分组

数据分完组之后，随便你怎么独立传输。

在分组交换中,包含一定字节数的数字信息“块”(分组)独立通过网络。

来自不同来源或发送方的块可以组合,而且以后可以分解,这称为“(多路)复用”。

这些块在到达目的地的过程中,需要在交换设备之间传输,并且路径可以改变。

面向连接的协议（服务）

通信之前要建立一条连接（不论是逻辑还是物理上的）

需要为每个连接存储一些信息或状态。

数据报

所有通信信息都包含在自己的分组中，不需要外物帮助自己存储必要信息。

它是一个特定类型的分组,有关来源和最终目的地的所有识别信息都位于分组中(而不是分组交换机中)。虽然这通常需要较大的数据包,但不需要在交换机中维护连接状态,它可用于建立一个无连接的网络。

消息边界（记录标记）

保留消息边界的协议：发送的什么消息，就原封不动的接受什么

不保留的：发送的A消息，有可能仅仅就被解释一个个字节接受。

比如：发送3个组，我123、你456、他789

• 保留的：接受：也是带边界的三个组。
• 不保留的：仅仅是字节序列。

端到端论点和命运共享

端到端论点:

重要功能尽量在端系统实现

重要功能(例如差错控制、加密、交付确认)通常不会在大型系统的低层(见1.2.1节)实现。但是,低层可以提供方便端系统工作的功能,并最终可能改善性能。这种观点表明低层功能不应以完美为目标,这是因为对应用程序需求做出完美推测是不可能的。

命运共享：

选择哪些功能在同一计算机、网络或软件栈中实现。

差错控制和流量控制

• 在网络中存在数据损坏或丢失的情况。这可能出于各种原因,例如硬件间题、数据传输中被修改、在无线网络中超出范围,以及其他因素。对这种错误的处理称为差错控制,

• 针对网络中可靠、按顺序交付的实现开销，Intemet协议采用一种称为尽力而为交付的服务：

  • 那些可能影响一个数据报定向的差错,当检测到这种差错时,出错的数据报仅被丢弃而没有进一步行动。

• 如果尽力而为的交付成功,发送方能以超过接收方处理能力的速度生成信息。在尽力而为的IP网络中,降低发送方的发送速度可通过流量控制机制实现,它在网络外部或通信系统高层中运行。

  • 注意,TCP会处理这种问题,这与端到端论点一致：TCP在端主机中实现速率控制。
  • 它也与命运共享一致:这种方案在网络基础设施中有些单元失效的情况下,不会影响网络设备的通信能力(只要有些通信路径仍然可用)。

设计和实现

一个体系结构并不是只有一个唯一实现（如果是这样的话，那就不用区分结构和实现了），所以体系结构和实现并不是相同的概念。

实现体系结构定义了协议体系结构中的概念如何用于软件形式的实现中。

但实现一般是分层的

分层

通过分层,每层只负责通信的一个方面。

• ISO体系结构（并不是互联网的体系结构）
  • 内容：七层体系结构，规定了每层之间的关系及其任务
• Internet（当今互联网体系结构）体系结构
  • 内容：4层体系结构，规定了每层之间的关系及其任务。

分层实现中的复用、分解、和封装

• 分层体系结构的一个主要优点是具有协议复用的能力：

第N层的协议数据单元(PDU)可以通过N-1层的封装而复用。。第N-1层的协议数据单元(PDU)在第N层的分解过程中用于接受原数据。

• 也允许相同协议对象(例如连接)的多个实例同时存在,并且不会被混淆。

A层的协议有的概念，B层也可以有，都用到了这个概念实现协议，但他们因为是不同层，所以是不同的。

TCP/lP 体系结构和协议（具体的体系结构/因特网的事实标准）

TCP/ IP 参考模型

• 应用层

• 传输层(TCP/UDP)

• 网络层（IP/Intemet控制消息协议(ICMP)是IP的一个辅助协议）

  • IP发送给链路层协议的PDU称为IP数据报,它的大小是64KB(IPv6将它扩大为4GB)。
  • 大的分组放人链路层PDU(称为帧)时需要进行缩小处理,这个过程称为分片,它通常由IP主机和某些路由器在必要时执行。
  • 在分片的过程中,大数据报的一部分被放人多个称为分片的小数据报中,并在到达目的地后组合(称为重组)

  **3种类型的IP地址,**地址类型决定如何进行转发:

  • 单播(目的地是一台主机)、

  • 广播(目的地是一个指定网络中的所有主机)和

  • 组播(目的地是属于一个组播组中的一组主机)。

• 链路层（ARP）

TcP/lP中的复用、分解和封装

每层都会有一个标识符（ID）,允许接收方决定哪些协议或数据流可复用在一起。每层通常也有地址信息,它用于保证一个PDU被交付到正确的地方。

虽然它不是TCP/IP协议族的真实部分,但我们也能自底向上地说明从链路层开始如何进行分解,这里使用以太网作为例子。

• 链路层以太网帧包含一个48位的目的地址(介质访问控制(MAC)地址)和一个16位的以太网类型字段00x0800表示这个帧包含IPv4数据报，0x0806和0x86DD分别表示ARP和IPv6，假设目的地址与接收方的一个地址匹配,这个帧将被接收并校验差错,以太网类型（type）字段用于选择处理它的网络层协议。如果接收到的帧包含一个IP数据报,以太网头部和尾部信息将被清除,并将剩余字节(包含帧的有效载荷)交给IP来处理。
• IP检测一系列的字段,包括数据报中的目的地址。如果目的地址与自已的一个IP地址匹配,并且数据报头部(IP不检测有效载荷)没有错误,则检测8位的IPv4协议字段(在IPv6中称为下一个头部字段),以决定接下来调用哪个协议来处理。常见的值包括1(ICMP)、2(IGMP)、4(IPv4)、6(TCP)和17(UDP)。数值4的含义是有趣的：因为它表示一个IP数据报可能出现在另一个IP数据报的有效载荷中。它违反了分层和封装的原有概念,但是作为隧道技术的基础。如果网络层(IPv4或IPv6)认为传人的数据报有效,并且已确定正确的传输层协议,则将数据报(必要时由分片重组而成)交给传输层处理。
• 传输层中,大部分协议(包括TCP和UDP)通过端口号将复用分解到适当的应用。

端口号

端口号是16位的非负整数(范围是0-65535)。这些数字是抽象的,在物理上没有指任何东西。

在某些情况下(例如在客户端),端口号的值无关紧要,这是因为它们只是短期被使用。这些端口号又称为临时端口号。它们被认为是临时的,因为客户机只需支持一个应用的客户程序,并不需要被服务器发现以建立一个连接。相反,服务器通常需要不变的名称和端口号,以便被客户机所发现。

名称（name）、地址和DNS

在TCP/IP中,每台计算机(包括路由器)的每个链路层接口至少有一个IP地址。IP地址足以识别主机,但它们不方便被人们记忆或操作(尤其是更长的IPv6地址)。在TCP/IP环境中,DNS是一个分布式数据库,提供主机名和IP地址之间的映射(反之亦然)。

虽然大多数TCP/IP协议不必关心域名,但用户(例如使用Web测览器)通常会频繁使用域名,因此如果DNS不能正常工作,正常的Intemet访问也难以使用。

Internet、内联网和外联网

内联网是一个用于描述专用互联网络的术语。

在很多情况下,一个企业或商业机构可能希望建立一个网络,其中包含可供合作伙伴或其他相关公司通Intemet访问的服务器。这种涉及VPN的网络通常被称为外联网,由连接在提供服务的企业防火墙之外的计算机组成(见第7章)

设计应用（程序）

网络应用的典型结构基于少数几种模式。

最常见的模式是客户机/服务器模式和对等模式

CS模式

P2P模式

API

无论是P2P或客户机/服务器,都需要表述其所需的网络操作(例如建立一个连接、写人或读取数据)。这通常由主机操作系统使用一个网络应用程序编程接口(API)来实现。最流行的API被称为套接字或Berkeley套接字。

网络安全

内核级阻塞与应用级阻塞

异步与同步：

阻塞与非阻塞：

线程概念

linux进程可以看做只有一个单独控制线程的进程：单一线程的进程在同一时间只能做一件事。

单一进程中有了多个控制线程之后，可以将程序设计成某一时刻能够做不止一件事。每个线程都可以同时处理各自的任务。

单处理器上可以实现快速的线程切换（相比于进程切换开销小很多），这样相当于”同时”做着不同的任务。

多线程优点：

• 在处理异步（应用程序不会被异步事件阻塞。但内核里实际有可能阻塞。）事件时，可以简化处理代码。在单线程时，多个异步事件需要单个安排执行适当的顺序，在多线程时，单个异步事件分别交给不同的线程处理，单个线程内部使用同步模型，处理事件。简化了编程的复杂度。
• 多个进程之间的内存和文件描述符共享需要依赖操作系统提供的复杂机制，多个线程之间本就共享进程的存储空间和文件描述符。
• 要解决的问题本身就是可以分解成多个独立的任务的。这时，使用多线程明显可以提高系统的吞吐量。
• 交互式程序可以使用多线程来改善响应时间：输入输出（IO）可以与其他处理IO的逻辑分别执行。

每个线程包含的信息（数据结构和资源）：

• 线程ID
• 单独的寄存器值
• 单独栈
• 调度的优先级和策略
• 信号屏蔽字
• 线程私有数据（线程本地存储TLS）

并且，同一个进程的所有线程共享进程的某些资源

• 可执行程序代码
• 全局内存：（初始化数据段，未初始化数据段）
• 堆内存
• 程序栈
• 文件描述符

Pthread API详细背景

有几个概念贯穿整个Pthreads API，下面首先介绍：

线程数据类型

Pthreads API 定义了一干数据类型，表 29-1 列出了其中的一部分。后续会对这些数据类型中的绝大部分加以描述。

线程 errno

一言以蔽之，errno 机制在保留传统 UNIX API 报错方式的同时，也适应了多线程环境。

Pthreads 函数返回值

从系统调用和库函数中返回状态，传统的做法是：返回 0 表示成功，返回-1 表示失败，并设置 errno 以标识错误原因。

Pthreads API 所有 Pthreads 函数均以返回 0 表示成功，返回一正值表示失败。这一失败时的返回值，与传统 UNIX 系统调用置于 errno 中的值含义相同。

创建线程

启动程序时，产生的进程只有单条线程，称之为初始（initial）或主（main）线程。

函数 pthread_create()负责创建一条新线程。

1
2
3
4

#include<pthread.h>
int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                    void * (*start)(void*),void *args);
// 成功返回0，错误返回一个正错误号。

• 新线程通过带有参数（args）的函数start开始执行。原线程继续执行后续语句。如果执行的执行函数不需要参数，则可以将args设置为NULL
• start()的返回值类型为 void*，对其使用方式与参数 arg 相同。对后续 pthread_join()函数的描述中，将论及对该返回值的使用方式。
• 将经强制转换的整型数作为线程 start 函数的返回值时，必须小心谨慎。原因在于，取消线程（见第 32 章）时的返回值 PTHREAD_CANCELED，通常是由实现所定义的整型值，再经强制转换为 void*。如果某一线程B恰好返回实现定义此取消值，那么正在执行pthread_join()操作的线程B，会误认为A遭到了取消。
• 参数 thread 指向 pthread_t 类型的缓冲区，在 pthread_create()返回前，会在此保存一个该线程的唯一标识。后续的 Pthreads 函数将使用该标识来引用此线程。在新线程开始执行之前，实现无需对 thread 参数所指向的缓冲区进行初始化，即新线程可能会在 pthread_create()返回给调用者之前已经开始运行。如**新线程需要获取自己的线程 ID，则只能使用 pthread_self()**（29.5 节描述）方法。
• 参数 attr 是指向 pthread_attr_t 对象的指针，该对象指定了新线程的各种属性。29.8 节将述及其中的部分属性。如果将 attr 设置为 NULL，那么创建新线程时将使用各种默认属性，

调用 pthread_create()后，应用程序无从确定系统接着会调度哪一个线程来使用 CPU 资源（在多处理器系统中，多个线程可能会在不同 CPU 上同时执行）。

终止线程

有如下方式

• 执行函数（start）执行return语句，返回指定值
• 线程调用pthread_exit()
  • 调用和执行return类似，不同之处在于，可在线程start函数所调用的任意函数中调用pthread_exit()
  • retval不应分配在线程栈中，start函数的返回值也不应分配在堆栈中
  • 如果主线程调用pthread_exit()，而非调用exit()或return，其他线程将继续运行

1
2
3

include<pthread.h>
void pthread_exit(void *retval);
// 其返回值可由其他线程调用pthread_jion()获得。

• 调用pthread_cancel()取消线程
• 任意线程调用了exit()，或主线程执行return，都会导致所有线程立即退出

线程标识（ID）

一个线程可以通过pthread_self()获取自己的ID

1
2

#include<pthread.h>
pthread_t pthread_self(void);

函数pthread_equal()可检查两个线程ID是否相同

1
2
3
4

#include<pthread.h>
pthread_t pthread_equal(pthread_t t1,pthread_t t2);
// 如果相同返回非0，否则0
// pthread_t是由实现定义的，可移植程序不应依赖它

链接（joioning）已终止的线程

函数pthread_join()等待 特定ID的已终止线程。

1
2
3

#include<pthread.h>
pthread_t pthread_join(pthread_t thread, void **retval);
// 0成功，失败返回一个正错误号

• retval保存终止进程的返回值

pthread_join()执行的功能类似于针对进程的 waitpid()调用，不过二者之间存在一些显著差别。

• 线程之间的关系是对等的（peers），进程中的任意线程均可以调用 pthread_join()与该进程的任何其他线程连接起来。例如，如果线程 A 创建线程 B，线程 B 再创建线程 C，那么线程 A 可以连接线程 C，线程 C 也可以连接线程 A。这与进程间的层次关系不同，父进程如果使用 fork()创建了子进程，那么它也是唯能够对子进程调用 wait()的进程。调用 pthread_create()创建的新线程与发起调用的线程之间，就没有这样的关系。
• 无法“连接任意线程”（对于进程，则可以通过调用 waitpid(-1, &status, options)做到这一点），也不能以非阻塞（nonblocking）方式进行连接（类似于设置 WHOHANG 标志的 waitpid()）。使用条件（condition）变量可以实现类似的功能。

线程的分离

有时，程序员并不关心线程的返回状态，只是希望系统在线程终止时能够自动清理并移除之。在这种情况下，可以调用 pthread_detach()并向 thread 参数传入指定线程的标识符，将该线程标记为处于分离（detached）状态。

1
2
3

#include<pthread.h>
pthread_t pthread_detch(pthread_t thread);
// 0成功，失败返回一个正错误号

• 一旦线程处于分离状态，就不能再使用 pthread_join()来获取其状态，也无法使其重返“可连接”状态
• 其他线程调用了 exit()，或是主线程执行 return 语句时，即便遭到分离的线程也还是会受到影响。此时，不管线程处于可连接状态还是已分离状态，进程的所有线程会立即终止。换言之，pthread_detach()只是控制线程终止之后所发生的事情（被自动回收，而不是成为僵尸），而非何时或如何终止线程。

线程属性

点出如下之类的一些属性：

• 线程栈的位置和大小、
• 线程调度策略和优先级（类似于 35.2 节和 35.3
  节所描述的进程实时调度策略和优先级），
• 以及线程是否处于可连接或分离状态。

锁并不是并发设计的唯一原语。

在某些情况下，线程需要检查某一条件（condition）满足之后，才会继续运行。

例如：父线程需要检查子线程是否执行完毕（jion（））。如何实现这种等待？—- 信号量

线程等待条件满足的方法

方法1： 自旋知直到条件满足

1

while (done == 0); // spin

简单的方案是自旋直到条件满足，这是极其低效的，某些情况下甚至是错误的。

方法2： 条件变量

条件变量是一个显式队列，当某些执行状态（即条件，condition）不满足时，线程可以把自己加入队列，等待（waiting）该条件。另外某个线程，当它改变了上述状态时，就可以唤醒一个或者多个等待线程（通过在该条件上发信号），让它们继续执行。

要声明这样的条件变量，只要像这样写：pthread_cond_t c;，这里声明 c 是一个条件变量（注意：还需要适当的初始化）。条件变量有两种相关操作：wait()和 signal()。线程要睡眠的时候，调用 wait()。当线程想唤醒等待在某个条件变量上的睡眠线程时，调用 signal()。具体来说，POSIX 调用如图 30.3 所示：

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

pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);
pthread_cond_signal(pthread_cond_t*c);
int done = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;
void thr_exit() {
    Pthread_mutex_lock(&m);
    done = 1;
    Pthread_cond_signal(&c);
    Pthread_mutex_unlock(&m);
}

void *child(void *arg) {
    printf("child\n");
    thr_exit();
    return NULL;
}

void thr_join() {
	Pthread_mutex_lock(&m);
	while (done == 0)
        Pthread_cond_wait(&c, &m);
    Pthread_mutex_unlock(&m);
}
int main(int argc, char *argv[]) {
    printf("parent: begin\n");
    pthread_t p;
    Pthread_create(&p, NULL, child, NULL);
    thr_join();
    printf("parent: end\n");
    return 0;
}

条件变量是一个队列,声明一个条件变量就是声明一个存放线程的队列。这些线程等待某些条件。

本代码中的条件就是done的值（状态）。done叫做状态变量

以上状态变量和锁，对于条件变量来说都是必不可少的。

• 状态变量记录了所有线程都关注（所有线程都在观察着这个变量的动向）的值。睡眠唤醒锁都离不开他。

1
2
3
4
5
6
7
8
9
10
11

void thr_exit() {
    Pthread_mutex_lock(&m);
    Pthread_cond_signal(&c);
    Pthread_mutex_unlock(&m);
}
void thr_join() {
    Pthread_mutex_lock(&m);
    Pthread_cond_wait(&c, &m);
    Pthread_mutex_unlock(&m);
}
// 如果缺少状态变量，假设子线程立即执行，调用exit，子线程发送信号，此时没有在条件变量(队列）上睡眠的线程。所以不会唤醒任何人，父进程在执行，就会一直等待在条件变量上，因为已经没有人可以唤醒他了。

• 锁也是必不可少的。

保证发信号时，总是持有锁

使用条件变量的一些基本要求：

• 有锁
• 有等待的条件。

信号量

信号量是一个有数值的整数对象。 信号量就代表资源量。

可以用两个函数来操作他。

在 POSIX 标准中，是sem_wait()【P操作】和 sem_post()【V操作】。因为信号量的初始值能够决定其行为，所以首先要初始化信号量，才能调用其他函数与之交互，如图 31.1 所示。

1
2
3

#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);

其中申明了一个信号量 s，通过第三个参数，将它的值初始化为 1。sem_init()的第二个参数，在我们看到的所有例子中都设置为 0，表示信号量是在同一进程的多个线程共享的。

PV操作

1
2
3
4
5
6
7
8
9

int sem_wait(sem_t *s) {
	信号量值减1;
	如果值是负值，等待。
}

int sem_post(sem_t *s) {
   信号量值加1
   如果值大于等于1，唤醒。
}

• 首先，sem_wait()要么立刻返回（调用 sem_wait()时，信号量的值大于等于 1），要么会让调用线程挂起，直到之后的一个 post 操作。当然，
  也可能多个调用线程都调用 sem_wait()，因此都在队列中等待被唤醒。
• 其次，sem_post()并没有等待某些条件满足。它直接增加信号量的值，如果有等待线程，唤醒其中一个。
• 最后，当信号量的值为负数时，这个值就是等待线程的个数[D68b]。虽然这个值通常不会暴露给信号量的使用者，但这个恒定的关系值得了解，可能有助于记住信号量的工作原理。

二值信号量（锁）

使用信号量作为锁。

1
2
3
4
5

sem_t m;
sem_init(&m, 0, X); // initialize semaphore to X; what should X be?
sem_wait(&m);
// critical section here
sem_post(&m);

信号量初始值应该为1

信号量用作条件变量

信号量也可以用在一个线程暂停执行，等待某一条件成立的场景。例如，一个线程要等待一个链表非空，然后才能删除一个元素。在这种场景下，通常一个线程等待条件成立，另外一个线程修改条件并发信号给等待线程，从而唤醒等待线程。因为等待线程在等待某些条件（condition）发生变化，所以我们将信号量作为条件变量（condition variable）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

下面是一个简单例子。假设一个线程创建另外一线程，并且等待它结束（见图 31.4）。
sem_t s;
void *child(void *arg) {
    printf("child\n");
    sem_post(&s); // signal here: child is done

return NULL;
}

int main(int argc, char *argv[]) {
    sem_init(&s, 0, X); // what should X be?
    printf("parent: begin\n");
    pthread_t c;
    Pthread_create(c, NULL, child, NULL);
    sem_wait(&s); // wait here for child
    printf("parent: end\n");
    return 0;
}

如何实现信号量

最后，我们用底层的同步原语（锁和条件变量），来实现自己的信号量，名字叫作Zemaphore。这个任务相当简单，如图 31.12 所示。

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

// 用锁和条件变量实现 Zemahpore
typedef struct _Zem_t {
    int value;
    pthread_cond_t cond;
	pthread_mutex_t lock;
} Zem_t;

// only one thread can call this
void Zem_init(Zem_t *s, int value) {
    s->value = value;
    Cond_init(&s->cond);
    Mutex_init(&s->lock);
}

// p操作
void Zem_wait(Zem_t *s) {
	Mutex_lock(&s->lock);
	while (s->value <= 0)
		Cond_wait(&s->cond, &s->lock);
	s->value--;
	Mutex_unlock(&s->lock);
}
// V操作
void Zem_post(Zem_t *s) {
	Mutex_lock(&s->lock);
	s->value++;
	Cond_signal(&s->cond);
	Mutex_unlock(&s->lock);
}

可以看到，我们只用了一把锁、一个条件变量和一个状态的变量来记录信号量的值。

我们实现的 Zemaphore 和 Dijkstra 定义的信号量有一点细微区别，就是我们没有保持当信号量的值为负数时，让它反映出等待的线程数。事实上，该值永远不会小于 0。这一行为更容易实现，并符合现有的 Linux 实现

小心泛化

我们可以把信号量当作锁和条件变量的泛化。但这种泛化有必要吗？考虑基于信号量去实现条件变量的难度，可能这种泛化并没有你想的那么通用。

很奇怪，利用信号量来实现锁和条件变量，是棘手得多的问题。某些富有经验的并发程序员曾经在 Windows 环境下尝试过，随之而来的是很多缺陷[B04]。你自己试一下，看看是否能明白为什么使用信号量实现条件变量比看起来更困难。

参考：

​ ostep