网络算法学：第六章传输控制

1、 举例：Web服务器服务一个GET请求的过程 第一步：建立TCP连接 假设客户向服务器发送了一个TCP SYN包。 SYN包到达服务器适配器，适配器将包拷贝到内存 （DMA），然后通过中断通知CPU。 内核响应中断，通过unblock之前的一个系统调用 来通知web服务器。 web服务器接受客户的连接请求。 第二步：处理GET请求 假设客户向服务器发送了一个GET请求（GET File 1）。 GET请求到达服务器适配器，。 服务器进程解析GET请求，得到文件名。 服务器查找一个目录结构，确定文件在磁盘上的位置。 服务器进程启动对文件系统的读操作（一个系统调用）。 如果文件不在file cac

2、he中，文件子系统启动一个磁盘I/O 操作。 当文件进入应用缓冲区后，服务器通过写相应的连接（另 一个系统调用）来发送HTTP响应。 网络代码的组织方式： 每层实现为一个进程：处理一个包产生的进程调度开销 （几百微秒量级）比一个包的到达时间要大得多。 所有层实现为一个进程：控制开销最小。 Web服务器的组织方式： 每个进程服务一个客户：并发度最大，进程调度开销最高 一个进程服务所有客户：上下文切换开销最小，进程须自 己调度客户以实现最大的并发度。 将客户划分成组，每个进程服务一组客户：并发度和切换 开销适中。 进程切换：几百微秒 系统调用：几十微秒 中断处理：几微秒 在一个10Gbps的以太网

3、链路上传输最小长度（64 字节）的包，每隔51.2ns会到来一个包。 一个简单的例子： 应用从键盘读数据，通过TCP发送到网络上； 数据到达接收端后，在接收端屏幕上显示出来。 朴素的实现方法： 每层（IP、TCP、应用）实现为一个进程，模块化好 每发送和接收一个包需要3个进程、2次进程切换，性能差 实现协议的主要困难之一是权衡代码的模块化和系 统性能。 发送端使用两个进程： Keyboard Handler Send 接收端使用两个进程： Receive Interrupt Handler Receive Keyboard Handler进程： 收集从键盘输入的数据； 当有数据发送时，调用tr

4、ansport- arm-to-send，然后将自己挂起 （一个上下文切换）。 Transport-arm-to-send： 导出到Keyboard Handler进程的一 个传输层函数 告诉传输层该连接希望发送数据，但 并不实际传输数据 Send进程： 执行transport-send例程 Transport-send首先调用display- get-data例程（upcall），获取应用 数据。 Transport-send给应用数据加上 TCP头，调用net-send例程发送数据。 display-get-data： 应用导出到Send进程的一个例程，向 传输层协议提供需要发送的应用数据

5、。 Receive Interrupt Handler进程： 使用net-dispatch例程接收包； Net-dispatch调用transport-get- port（upcall），确定处理该包的应用 进程。 net-dispatch唤醒Receive进程。 Transport-get-port： 传输层导出的一个例程，通过检查包 头中的端口号来确定目的应用。 Receive进程： 执行net-receive 执行transport-receive 执行display-receive，显 示数据 在一个进程中执行所有的 协议层次。 将向上调用（upcall）应用到网络分层协议的实现中，

6、是该方案的新颖之处，但在当时被认为违背了传统教 义（某一层只能使用下层的服务）。 设计者认为：向下调用（downcall）是协议规范的 要求，不是协议实现的唯一方法。 一个重要的观点：仅使用一个或两个进程来处理一个 报文，每个进程包括来自两个或多个协议层次的例程。 原则P8：实现者不应受到参考实现的限制。 UNIX将所有协议代码作为内核进程的一部分执行。 当一个包到达时， 网络适配器产生一个硬件中断 中断处理程序将包放入一个内存队列，然后通过软件中 断调度一个内核进程（一次上下文切换） 内核进程执行协议处理，通过检查传输层端口号得到目 的应用，唤醒应用（一次上下文切换） 每个包的处理至少经历两

7、次上下文切换： 中断上下文到内核进程（协议处理） 内核进程到应用进程 基本思想： 协议处理与应用在同一个进程中，可以通过upcall 进行通信。 用户级实现的好处： 可以绕过内核，直接从中断上下文到应用进程，减 少一次上下文切换 协议代码可以在用户空间编写和调试 问题： 中断例程如何确定将包交给哪个应用进程？ 方案一：使用一个解复用进程 解复用进程检查所有的包，确定包的目标进程， 将包交给目标进程。 缺点：增加一次进程切换。 方案二：应用传递一些信息到内核（P9） 内核定义一个接口（如Berkeley Packet Filter，BPF）， 允许应用声明自己要处理的包类型。 中断例程根据一组包

8、过滤器进行解复用（提前解复用） 用户级协议实现要求每个应用进程应当实现协议 栈。 通常将TCP/IP代码实现为一个共享库，避免在每 个应用中复制TCP/IP代码 TCP/IP代码必须是可重入的 P13的运用：协议并不一定要实现在内核中。 考虑一个需要处理大量连接的web服务器 web服务器内潜在的并发性： 由于磁盘读写、网络输入输出比指令执行时间 大得多，当一个客户等待I/O时，CPU可以转去 处理另一个客户。 服务器应用的组织方式主要权衡并发性和 调度开销 调度由操作系统完成，编程最简单。 内存和寄存器之间大量的读写操作（上下 文保存和恢复） 页表更新（每个进程有自己的页表） TLB mis

9、s，d-cache miss，I-cache miss 需要大量空间保存上下文，减少了文件 cache的使用空间，文件cache miss增大 每个进程处理一个客户还涉及进程的频繁 创建和销毁 通过预先计算（P2a）及推迟销毁（P2b） 可以避免创建/销毁进程的开销： 预先创建一批进程供使用 客户释放连接时，其进程放入空闲进程池中 当一个新客户到来时，需要从空闲进程池 中为新客户分配一个进程 Unix使用一个系统调用accept： 进程结束时执行一个accept系统调用，然后在 一个内核数据结构中排队 当一个新客户到来时，其套接字被转交给队列 中第一个空闲进程 代价为一次系统调用 每个线程处理

10、一个客户请求，所有线程属于同一 个进程，共享同一个虚拟内存。 优点： 切换线程不需要刷新TLB 所有线程可以使用一个公共的文件cache 缺点： 仍然必须保存和恢复每个线程的上下文 需要存储空间保存线程上下文 由内核提供线程调度：简单（不需编程实现）， 但代价高 应用自己实现客户调度：代价小 应用需要知道之前启动的I/O是否结束了 许多操作系统提供查询I/O结束的系统调用 While(1) FindActive(); Process a list of I/O descriptors; 原则上，如果操作系统提供对非阻塞I/O操作的支持， 一个事件驱动服务器可以获得与多进程/多线程服务 器一样的

11、并发度。 例如，一个事件驱动服务器执行一个文件read()调用， 而文件不在cache中： 非阻塞磁盘I/O： read()立即返回，指出文件当前不可 用，服务器处理其它客户。 阻塞型磁盘I/O：服务器主循环停顿，等待磁盘I/O结束 （几个毫秒）。 许多操作系统（如Solaris和UNIX）支持网络连接 上的非阻塞读写，但不支持非阻塞的磁盘I/O操作 虽然这些操作系统允许使用其它的异步系统调用 进行磁盘I/O，但这些系统调用未与select()集成 程序员必须在损失并发性和放弃单进程模型之间 进行选择！ Flash Web服务器的解决方案： 当要读一个文件时，主服务器进程首先检查文件是否已在

12、内存中（如通过一个系统调用） 如果文件不在内存中，主进程指示一个助手进程执行磁盘 操作 助手进程完成后，通过进程间通信（如管道）通知主进程 助手进程还可用于目录查找，确定文件在磁盘上的位置 与多进程模型的区别： 仅对每个并发的磁盘操作需要一个助手进程，而不是每个 并发的客户请求都需要。 助手进程应当预先生成，以避免创建进程的延迟。 生成多少个助手进程比较合适？ 数量太少损失并发度 数量太多消耗内存 Flash Web服务器根据系统负载动态生成和销毁 助手进程。 实现复杂度高： 应用必须管理状态机，调度那些不需要帮助的客户请求 代码模块性差： 服务器代码是一体化的，不利于代码重用 过载控制困难：

13、 只使用一个主进程，难以应付大量客户造成的负载波动 将服务器代码按照处理任务分解成某干个阶段，每个阶段 由一个或多个线程处理，阶段之间通过队列通信。 实现复杂度低： 利用操作系统调度线程 代码模块性好： 每个阶段的代码可重用 过载控制灵活： 可在每个阶段进行细粒度的过载控制 多进程/多线程模型： 每个进程/线程服务于一个客户，执行全部的处理任务。 纯事件驱动模型： 一个进程服务于全部客户，执行全部的处理任务。 基于任务的模型： 使用若干组线程（每组有一个主线程及可能的子线程）， 每一组线程服务于全部客户，但只执行一种处理任务。 Web服务器性能测试： CERN web服务器采用每个进程处理一个

14、客户的实 现方式，Squid web服务器采用事件驱动方式（一 个进程服务全部客户）。 在LAN环境中进行测试：Squid服务器的性能高一 个数量级。 在WAN上进行相同的测试：两种服务器的性能没有 差异！ 一个重要的观察： 在相同的吞吐量（每秒新建连接数）下，WAN 中的服务器存在大量并发的TCP连接。 举例： 假设web服务器的吞吐量为3000连接/秒 若WAN中的平均来回延迟为2秒，则服务器中 并发连接数约为6000条 若LAN中平均来回延迟为2ms，则服务器中并 发连接数只有6条 LAN中服务器的平均并发连接数为6条： CERN服务器：涉及至少6个进程的进程切换 Squid服务器：查询

15、6个客户的I/O事件（FindActive） 相比而言，CERN服务器的控制开销远大于Squid服务器 WAN中服务器的平均并发连接数为6000条： CERN服务器：涉及6000个进程，但多数进程处于阻塞状 态（等待响应），就绪的进程不多，进程切换频率并不高 Squid服务器：需查询6000个客户的I/O结束事件 FindActive()成为Squid服务器的瓶颈，抵销了消除进程切 换带来的好处 事件驱动服务器使用两个系统调用，在Unix中分别 是select() 和 ufalloc()。 Select()： 提供给应用查询I/O结束事件 当有500个连接时，select()消耗一半以上的CP

16、U时间。 Ufalloc()： 服务器使用 ufalloc() 为新的套接字或文件分配最低未 使用的描述符 当有500个连接时，ufalloc()消耗1/3的CPU时间。 使用高效的数据结构（如堆）可以极大地降低这个开销。 输入参数（比特串用引用传递）: 一个希望读的描述符比特串 一个希望写的描述符比特串 一个希望监听异常的描述符比特串 一个超时值 输出参数（比特串用引用传递） 就绪的描述符数量（用函数值返回） 读就绪的描述符比特串（改写输入比特串） 写就绪的描述符比特串（改写输入比特串） 监听到异常的描述符比特串（改写输入比特串） 初始化： 应用清除比特串，根据想要读、写和监视的描述符 设置

17、比特串中的相应位。（建立比特串） 调用： 应用使用构造好的比特串调用select()；如果没有描 述符准备好，应用被阻塞；如果超时发生，应用进 行异常处理。 响应： 应用扫描返回的比特串，对在比特串中置位的描述 符调用相应的读或写例程。 （扫描比特串） Prune： 内核将要检查的描述符汇总到一个描述符比特串中， 称为选择集（selected set）。 Check： 对于选择集中的每个描述符，内核检查描述符是否 就绪； 如果检查的描述符未就绪，内核将应用进程ID放入 该描述符的select队列； 如果所有描述符均未就绪，内核令应用进程睡眠； 如果有描述符就绪，select()返回。 Resu

18、me： 当I/O发生使得某个描述符就绪时，内核I/O模 块检查描述符的select队列，唤醒所有等待该描 述符的进程。 Rediscover： 被唤醒的应用进程重新调度执行时，select模块 对选择集中的描述符再做一次扫描，以发现自 应用休眠至重新调度这段时间内就绪的所有描 述符。 1. 每次调用都要重建比特串： 同一个比特串既用作输入也用作输出，这使得应用 每次调用前必须重建比特串。 原因：API设计不当，或应用没有进行增量计算 2. 进程恢复后重新扫描选择集： 进程恢复时，内核I/O模块没有将就绪的描述符信 息传递给它，从而select必须重新扫描选择集。 原因：内核实现不佳 3. 内核

19、重复检查明知没有就绪的描述符： 假设套接字9是到远程客户的一个连接，服务器于时刻 t在套 接字9上发送了一个报文，响应在时刻t+1到来。假设在时间 t, t+1内服务器调用了15000次select()，则每次调用 select()时内核都要检查套接字9。 其实内核可以根据以下事实推断套接字9上没有包到来：套 接字9在时刻 t 被检查过，从时刻 t 开始没有收到去往该套 接字的包，从而可免去15000次的无用检查。当数据包于时 刻t+1到达时，内核传递信息给select，恢复检查套接字9。 原因：内核实现不佳 4. 比特串长度与描述符数量成正比： 假设服务器最多时必须处理6000个描述符，但某

20、个时间 段应用只感兴趣200个描述符，每次调用select()时只有 10个比特被置位。 尽管如此， 应用：每次调用前初始化全长度的比特串，响应时扫描全长 度的比特串 内核：prune、check、rediscovery阶段，都对全长度比特 串进行扫描。 原因：API实现不佳 1. 问题：每次调用都重建比特串 修改： 修改API，令输入和输出使用不同的比特串。 保留API，使用增量计算（应用保留原始输入串，进行 增量更新）。 2. 问题：线程恢复后重新扫描选择集 修改： 令内核I/O模块向select模块传递信息。 3. 问题：内核重复检查明知没有就绪的描述符 修改： 令内核保存状态，不检查明

21、知没有就绪的描述符。 4. 问题：比特串长度与描述符数量成正比 修改： 从根本上改变API，避免对比特串中给出的所有描述符 进行检查。 1. 避免从头开始重建比特串： 修改应用代码，使用两个比特串 A 和 B ，A用于增 量更新，B用作传入参数。 在两次调用select()之间，将发生改变的描述符更新 到 A 中（增量更新）。 调用select()前，应用将 A 拷贝到 B（传入参数）。 拷贝以字为单位进行，比根据描述符逐个设置比 特位高效得多。 修改内核实现： 每个进程维护一个线索集H（比特串），记录自上 一次调用select()以来就绪的描述符。 当一个I/O完成时，内核I/O模块将描述符

22、索引写入 等待该描述符的所有进程的线索集H中。 Select恢复执行后，只检查线索集H中的描述符。 该优化的本质是在层间传递线索（P9）。 以下描述符不需检查： 一个正在等待数据的描述符不需要被检查，直至异 步通知发生（如描述符被放到H中）。 以下描述符必须检查： 自上一次调用后就绪的描述符 任何新来的描述符（如一个新打开的套接字） 未消费完数据的套接字 对于每个进程，内核需要维护三个集合： 线索集H：自上一次调用后就绪的描述符 就绪集R：已知准备就绪的描述符 兴趣集I：感兴趣的所有描述符（长期兴趣） 兴趣集I： 当一个套接字第一次出现在select()中时，将其加入 I，仅当该套接字释放时移

23、出I。 假设传入select()的选择集为S，则Inew = IoldS。 内核仅检查以下描述符： 出现在Inew中，且出现在H中；（最近就绪的描述符） 出现在Inew中，但不在Iold中；（新的描述符） 出现在Inew中，且出现在Rold中；（已知就绪的描述符） 该次检查发现的就绪描述符记录在Rnew中。 select()返回出现在RnewS中的元素。 该优化的本质是增加状态来加快处理速度（P12） 当套接字15第一次出现在select()中时，套接字15进 入I（感兴趣）。 当一个500字节的包到达时，套接字15进入H（最近 就绪）。 若套接字15的数据未被读完，套接字15进入R （已 知

24、就绪）。 当应用读完套接字15中全部的数据时，套接字15离 开R。 套接字15总共被检查1+1+k次。 内核需要扫描和更新4个比特串（H、I、R、S）。 扫描4个比特串所用的时间与连接的总数成正比， 而不是和活跃的连接数成正比。 对于同一个I/O事件，可能需要多次检查一个描述 符（比如一个未消费完数据的套接字）。 使用事件通知来代替对描述符状态的检查 传统的基于事件的通知基本不能用： 异步通知：类似中断机制，事件一发生应用就 得到通知，导致过多开销，也难以编程。 事件速率过高：每个包到来都通知一次，代价 高（与CPU通信，存储事件通知）。 应用真正感兴趣的是引起状态改变的事件（如文 件I/O结

25、束，包到达等），而不是原始事件流。 对于一次大的传输，应用可能希望对于一批数据 得到一次通知，而不是每个包得到一次通知。 同步查询： 应用可以查询待处理的事件，在服务完当前事 件前不会被告知新的事件。 合并事件通知： 每个描述符最多只有一个事件通知被发出。 1）应用同步地请求下一组事件，没有事件则 休眠； 2）当系统调用返回时，应用检查每个事件通 知，调用相应的读或写例程； 3）回到1） 每个线程关联一组感兴趣的描述符。 每个描述符维护一个对该描述符感兴趣的线程列 表（称反向映射列表）。 每个线程使用一个比特串记录正在队列中等待处 理的事件，每个描述符对应一位。 当I/O事件发生时： I/O模

26、块使用反向映射表确定感兴趣的线程 将一个通知事件加入线程的待处理事件队列 当应用请求下一批事件时，返回待处理事件。 使用用户级协议栈，收发包过程还需要内核 吗？ 应用应告诉适配器要发送或接收的数据放在什么 地方，这在Unix中是通过系统调用实现的。 因此，即使在用户空间实现了协议栈，发送和接 收每一个数据包都必须进行系统调用。 确实是这样吗？ 内核并不参与每一次内存访问： 硬件确定X的虚拟页，通过TLB转换成一个物理页； 若物理页已映射到应用的虚拟内存，应用可以直接访问。 内核仅在以下两种场合用到： 为应用建立虚拟内存； 当应用违反内核建立的页面访问时，硬件产生一个异常。 采用虚拟内存的方法让

27、应用与适配器共享内存： 将存储器映射的适配器内存划分成若干个物理页。 为每个应用分配并映射一定数量的物理页。 应用可以直接读写映射给自己的物理页（通过TLB进行 地址映射）。 如果应用试图读写映射给其它应用的物理页，虚拟存储 硬件将产生一个异常。 运用原则P4c：利用已有TLB硬件保护页面访问。 由于适配器内存有限，通常数据包保存在存储子系统 的内存空间，适配器中只存放包缓冲区信息。 为接收数据包，应用将一个描述符写入适配器内存的 一个队列，描述符指出数据包要放入的内存缓冲区。 收到包后，适配器将包解复用到应用的描述符队列， 得到空闲缓冲区的描述符，将包拷贝到空闲缓冲区。 发送数据包与此类似。 页10：由web应用写入一系列空闲缓冲区描述符 页9：已经装入数据的缓冲区描述符 页18、12：内核分配给web应用的内存页。 当一个包到来时， 适配器将包解复用到页10； 将包拷贝到页18； 将描述符18移入页9； 包处理完后， 应用将描述符18移入页10 问题： 若web应用在页10中写入155，适配器会将web应 用的下一个包写入物理页155。 为什么虚拟存储硬件不能检测到该错误？