Lecture 21: 并发编程 (Concurrent Programming)
Lecture 21: 并发编程 (Concurrent Programming)
讲义对应：CMU 15-213 Lecture 21 — Concurrent Programming（素材：
F25-21-concprog.txt，2025 年 11 月 18 日） 教材对应：CS:APP3e 第 12 章 12.1–12.3（基于进程的并发、基于 I/O 多路复用的并发、基于线程的并发） 关联 Lab：L7 Proxy Lab（并发代理 + 缓存同步）／L8 SFS Lab（文件系统层面的并行与性能）
21.1 概述
第 20 讲结束时的 echo 服务器是迭代式（iterative）的：accept 一个连接，服务到对端关闭，再回去 accept 下一个。它有一个致命缺陷——只要一个客户端连上后发呆不输入，服务器就永远阻塞在 read 上；第二个客户端虽然 connect 成功（TCP 监听队列替他排队），却在 read 上无限等待。本讲回答的就是：如何让一个服务器同时服务多个客户端？
课程给出的答案是三条路线：基于进程（process-based）、基于 I/O 多路复用的事件驱动（event-based）、基于线程（thread-based）。三者共享同一个抽象——逻辑控制流（logical flow）：进程由内核自动交错，事件驱动由程序员手工交错，线程则是两者的混合体。本讲同时抛出并发编程的三大经典病：竞态（race）、死锁（deadlock）、活锁／饥饿（livelock / starvation），并用 badcnt.c 的”两亿次自增却数不到两亿”把竞态钉在案发现场。本讲为 Lecture 22–23 的同步机制（互斥锁、信号量、条件变量）铺路，也直接决定 Proxy Lab 并发与缓存两部分的成败。
21.2 核心概念与底层机制图解
21.2.1 三种并发模型（Three Approaches to Concurrency）
- 定义与目的：并发服务器用多个并发流同时服务多个客户端。区别只在于两件事——谁来交错这些流（内核还是程序员），以及这些流是否共享地址空间。
- 直观解释：进程法像”给每位客人单开一间包厢”（互不打扰，但开店关店成本高）；事件驱动法像”一位服务员端着托盘在大厅里轮转”（一人搞定所有桌，但忙不过来时全场都等）；线程法像”多个服务员共用同一个厨房和仓库”（协作快，可抢同一个锅就出事）。
- 底层机制图解：
┌──────────────────────────────────────────────────────────────┐
│ 并发服务器的三种实现 │
└──────────────────────────────────────────────────────────────┘
① 基于进程 Process-based ② 事件驱动 Event-based ③ 基于线程 Thread-based
──────────────────────── ────────────────────── ────────────────────────
main 进程 单进程 / 单线程 主线程 + N 个对等线程
├── fork ─► 子进程 1 一个 select/epoll 循环 ├─► 对等线程 1
├── fork ─► 子进程 2 ┌────────────────┐ ├─► 对等线程 2
└── fork ─► 子进程 3 │ while(1){ │ └─► 对等线程 3
│ select(...) │
地址空间: 各自独立 │ 分发事件 │ 地址空间: 全部共享
交错者: 内核自动 │ } │ 交错者: 内核自动
开销: 大(~20K cycles) └────────────────┘ 开销: 中(~10K cycles)
地址空间: 共享(单一)
交错者: 程序员手工
开销: 极小
隔离好 / 难共享 无竞态 / 不能用多核 易共享 / 易出竞态
- 与机器码/硬件的对应：三者的差别最终都落到地址空间上。
fork会复制页表并触发写时复制（copy-on-write），所以父子进程的connfd是同一张打开文件表项的两个引用（内核维护引用计数）；线程由clone(CLONE_VM\|CLONE_FS\|...)创建，共享同一张页表，只是各自持有一套寄存器上下文（PC、SP、通用寄存器、条件码）和一块栈。
21.2.2 基于进程的并发服务器（Process-based Servers，教材 12.1）
- 定义与目的：父进程
accept得到connfd，fork一个子进程去服务该客户端，父进程立刻回头accept。每个客户端由独立的子进程处理。 - 直观解释：这是”复制一家分店”——每家分店有自己的账本、自己的钥匙，谁也改不到别人；代价是开分店要真金白银（复制地址空间、页表）。
- 底层机制图解（描述符引用计数的变化）：
时刻 T0：父进程 accept 返回 connfd=4
父进程描述符表: [0][1][2][3]=listenfd [4]=connfd ──► refcnt(connfd)=1
时刻 T1：fork 之后（父子各持一份描述符表副本）
父进程: [3]=listenfd ──┐ ┌── [3]=listenfd :子进程
[4]=connfd ───┼────────┼── [4]=connfd :子进程
▼ ▼
两个描述符指向内核里同一张打开文件表项
refcnt(listenfd)=2 refcnt(connfd)=2 ← 内核引用计数
时刻 T2：子进程 close(listenfd)，父进程 close(connfd)
refcnt(listenfd)=1 refcnt(connfd)=1
⇒ 连接只有在 refcnt(connfd) 降到 0 时才真正关闭（发 FIN）
- 与机器码/硬件的对应：
fork之后两个进程的connfd是同一个整数 4，但它们指向内核里同一张打开文件表项。父进程若不close(connfd)，那张表项的引用计数永远是 2，客户端关闭连接后服务器也无法感知 EOF——连接被永久泄漏。子进程若不close(listenfd)，则每个子进程都占着一个监听描述符，且监听套接字在最后一个引用关闭前不会释放。
21.2.3 I/O 多路复用与 select（I/O Multiplexing with select，教材 12.2）
- 定义与目的：I/O 多路复用（I/O multiplexing） 让一个进程同时等待多个描述符上的事件。
select阻塞直到集合中至少一个描述符可读／可写／异常，然后告诉你是哪些。 - 直观解释：
select是”总机接线员”：你不用为每通电话配一个专人，接线员盯着所有线路，哪条线亮了就转到对应分机。 - 接口速查：
#include <sys/select.h>
int select(int nfds, fd_set *readset, fd_set *writeset,
fd_set *exceptset, struct timeval *timeout);
void FD_ZERO(fd_set *set); /* 清空集合：必须最先做 */
void FD_SET(int fd, fd_set *set); /* 加入 fd */
void FD_CLR(int fd, fd_set *set); /* 移除 fd */
int FD_ISSET(int fd, fd_set *set); /* 判断 fd 是否就绪 */
- 底层机制图解（
fd_set位向量与内核改写）：
用户态 fd_set（128 字节 = 1024 位）── FD_SETSIZE = 1024
位号: 0 1 2 3 4 5 ... 1023
┌──┬──┬──┬──┬──┬──┬───┬───┐
调用前│ 0│ 0│ 0│ 1│ 1│ 1│ 0 │ 0 │ FD_SET(3,&rs); FD_SET(4,&rs); FD_SET(5,&rs);
└──┴──┴──┴──┴──┴──┴───┴───┘
│ │ │ │
│ └──┴──┴──► 只有 4、5 有输入挂起
▼
┌──┬──┬──┬──┬──┬──┬───┬───┐
返回后│ 0│ 0│ 0│ 0│ 1│ 1│ 0 │ 0 │ ← 内核"就地"清除了未就绪的位！
└──┴──┴──┴──┴──┴───┴───┴───┘
▲ ▲
│ └─ FD_ISSET(4,&rs) == 1 ⇒ 处理 connfd=4
└──── FD_ISSET(3,&rs) == 0 ⇒ listenfd 无事件
nfds = maxfd + 1（最大描述符 + 1，不是描述符个数！）
返回值 = 就绪描述符的个数（0 = 超时；-1 = 出错，errno=EINTR 表示被信号打断）
- 陷阱：
select把readset／writeset／exceptset当作输入输出参数——传入时表示”我关心这些 fd”，返回时被改写成”这些 fd 就绪了”。所以下一次调用前必须FD_ZERO+ 重新FD_SET。这一步漏掉的程序会表现得像”随机漏事件”，是最经典的selectbug。 - 与机器码/硬件的对应：
select在 Linux 上的复杂度是 $O(n)$，内核要线性扫描位向量；poll用struct pollfd数组去掉了FD_SETSIZE限制但仍需 $O(n)$；epoll则在内核中维护红黑树 + 就绪链表，$O(1)$ 拿到就绪集合，适合十万级连接。三者语义相通，Proxy Lab 与教材用的是select。
21.2.4 基于线程的并发服务器（Thread-based Servers，教材 12.3）
- 定义与目的：主线程
accept得到connfd，把它复制到堆上，pthread_create一个对等线程去服务该客户端。所有线程共享同一个地址空间（代码、全局数据、堆、内核上下文），各自只有独立的线程上下文与栈。 - 直观解释：进程法像”每来一桌客人就新开一家餐厅”，线程法像”同一家餐厅里多雇一个服务员”——共用厨房（数据）所以上菜快，可同一个账本被两人同时改就乱套。
- 底层机制图解（进程地址空间 vs 多线程地址空间）：
传统视角：进程 = 上下文 + 代码/数据/栈 替代视角：进程 = 线程 + 代码/数据/内核上下文
┌────────────────────────┐ ┌────────────────────────┐
│ 内核上下文 │ │ 内核上下文 │
│ VM 结构/描述符表/brk │ │ VM 结构/描述符表/brk │ ← 全进程共享
├────────────────────────┤ ├────────────────────────┤
│ 栈 (SP) ↑向下增长 │ │ 线程1栈(SP1) PC1 │
│ │ │ 线程2栈(SP2) PC2 │ ← 各自独立
├────────────────────────┤ ├────────────────────────┤
│ 共享库 │ │ 共享库 │
├────────────────────────┤ ├────────────────────────┤
│ 运行时堆 (brk) │ │ 运行时堆 (brk) │ ← 共享！malloc 要加锁
├────────────────────────┤ ├────────────────────────┤
│ 读/写数据 (.data/.bss) │ │ 读/写数据 (.data/.bss) │ ← 全局变量共享
├────────────────────────┤ ├────────────────────────┤
│ 只读代码/数据 (.text) │ │ 只读代码/数据 (.text) │ ← 共享
└────────────────────────┘ └────────────────────────┘
一个控制流 每个线程一个控制流，但共享一切可写内存
- 与机器码/硬件的对应：多核机器上线程可以真并行（时间轴上重叠），单核上则是时间片（time slicing）模拟并行。讲义给出的 Linux 实测数量级：创建并回收一个进程约 20K 个周期，一个线程约 10K 个周期（或更少）——进程控制的开销大约是线程的两倍。
21.2.5 共享变量与竞态（Shared Variables and Races）
- 定义与目的：若一个变量被多个线程引用，且至少有一个线程在写它，则它是共享变量（shared variable）。若两个线程对同一共享变量的访问顺序会影响结果，就发生了竞态（race）。
- 直观解释：合租公寓的公用洗衣机旁挂着一块记账板——两人同时去写”洗衣次数”，谁最后写谁的数字留下，另一次就凭空消失了。
- 底层机制图解（进度图与不安全区域）：
进度图 Progress Graph：H1..H5 = 线程1的指令，L1..L5 = 线程2的指令
把两条指令流的交错画成网格，每个点 = 一个执行状态
L 轴（线程2）
▲
L5 │ * * * * * * ┌───────┐
L4 │ * * * * * * ┌───┤ 不安 │
L3 │ * * * * * * │ │ 全区 │
L2 │ * * * * * * │ │ 域 │
L1 │ * * * * * * │ └───────┘
│ │
│ ┌──────────┘
│ │ 不安全区域 Unsafe Region
└──────────────┴────────────────────────► H 轴（线程1）
H1 H2 H3 H4 H5
说明：H2 = load cnt→%rax, H3 = add $1,%rax, H4 = store %rax→cnt
L2/L3/L4 同理。当两个线程的这三条指令在图上"交叉进入"同一个
矩形（不安全区域）时，两条 store 可能都基于同一个旧值 ⇒ 丢失一次自增。
任何一条轨迹只要不穿过不安全区域，结果就是正确的 2n。
- 与机器码/硬件的对应：
cnt++不是一条指令！即使cnt只占 8 字节且 8 字节对齐（x86-64 保证单条对齐的 8 字节访存本身是原子的），读—改—写三步之间随时可能被切走。教材 12.4 节用objdump展示的正是这个事实（见 21.3.1 的真实反汇编）。
21.3 代码示例与底层机制分析
21.3.1 示例 (a)：竞态的真实面孔 —— badcnt.c
代码 (C)：
/*
* badcnt.c - CS:APP3e Figure 12.4/12.5 风格的竞态演示
* 两个线程各对全局共享变量 cnt 自增 niters 次。
* 正确结果是 2*niters，但因为没有同步，实际结果往往远小于它。
* 编译: gcc -g -Wall -O1 -std=c11 badcnt.c -o badcnt -lpthread
*/
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
volatile long cnt = 0; /* 全局共享计数器：被两个线程同时读写 */
void *thread(void *vargp)
{
long i, niters = *((long *)vargp);
for (i = 0; i < niters; i++)
cnt++; /* 非原子！编译成 load/add/store 三条指令 */
return NULL;
}
int main(int argc, char **argv)
{
long niters;
pthread_t tid1, tid2;
if (argc != 2) { fprintf(stderr, "usage: %s <niters>\n", argv[0]); exit(1); }
niters = atol(argv[1]);
pthread_create(&tid1, NULL, thread, &niters);
pthread_create(&tid2, NULL, thread, &niters);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
if (cnt != 2 * niters)
printf("BOOM! cnt=%ld (期望 %ld, 丢失 %ld, 完成率 %.2f%%)\n",
cnt, 2 * niters, 2 * niters - cnt,
100.0 * cnt / (2.0 * niters));
else
printf("OK! cnt=%ld\n", cnt);
return 0;
}
【代码做什么？】
- 主线程把
niters的地址（不是值）传给两个线程——两个线程读同一个long，各自循环niters次做cnt++。 - 两个
pthread_create之后，主线程pthread_join等两个线程都结束，此时理论上cnt == 2*niters。 - 若不等，打印实际值、丢失量与完成率。
【底层机制透视】：volatile 只禁止编译器把 cnt 缓存在寄存器里（讲义用它把”编译器优化掉整个循环”这种干扰排除掉），它完全不能保证原子性。真正的祸根是 cnt++ 在机器层是三条指令，而线程切换可能发生在任意两条之间。
【与汇编 / 硬件的对应】（本机 GCC 12.2.0 -O1 的真实 objdump -d -M intel 输出）：
0000000000401176 <thread>:
401183: 48 8b 05 e6 2e 00 00 mov rax,QWORD PTR [rip+0x2ee6] # 404070 <cnt>
40118a: 48 83 c0 01 add rax,0x1 # 在寄存器里 +1
40118e: 48 89 05 db 2e 00 00 mov QWORD PTR [rip+0x2edb],rax # 404070 <cnt> 写回
401195: 48 83 c2 01 add rdx,0x1 # i++
401199: 48 39 d1 cmp rcx,rdx
40119c: 75 e5 jne 401183 <thread+0xd>
（-O0 与 -O2 生成的循环体在语义上完全一致，都含 mov cnt→%rax / add / mov %rax→cnt 这一组非原子的读—改—写。若有某台机器把 cnt++ 编译成单条 addq $1, cnt(%rip)，那么内存总线会保证该条指令的原子性，结果就会是 2n——同一源程序在不同平台上后果不同。）
【实测验证】（本机：128 核 x86-64，Linux 5.14；./badcnt 100000000，期望值 200000000）：
run1: BOOM! cnt=107604110 (完成率 53.80%)
run2: BOOM! cnt=118579515 (完成率 59.29%)
run3: BOOM! cnt=133676070 (完成率 66.84%)
run4: BOOM! cnt=117806990 (完成率 58.90%)
run5: BOOM! cnt=104715193 (完成率 52.36%)
run6: BOOM! cnt=106804770 (完成率 53.40%)
run7: BOOM! cnt=100219366 (完成率 50.11%)
run8: BOOM! cnt=106027442 (完成率 53.01%)
run9: BOOM! cnt=106138139 (完成率 53.07%)
run10: BOOM! cnt=117326988 (完成率 58.66%)
run11: BOOM! cnt=107518336 (完成率 53.76%)
run12: BOOM! cnt=113237432 (完成率 56.62%)
再连续跑 20 次，把 cnt 排序后得到真实的波动区间：
90981898 95290435 100131967 100990322 101797854 102568726 102974309 104123542
106527522 106729898 106785066 112503470 113448002 116027908 120644332 123291741
125099447 155505430 172539375 175343844
最小值 = 90,981,898 最大值 = 175,343,844 均值 ≈ 116,665,254
期望值 = 200,000,000 最坏完成率 ≈ 45.5% 最好完成率 ≈ 87.7%
三次运行中没有一次得到 200000000。作为对照，taskset -c 0 ./badcnt 100000000（强制两个线程跑在同一个核上，靠时间片切换制造交错）同样出错，且其中一次恰好得到 cnt=100000000——丢了整整一半，即两个线程的每一次自增都被对方覆盖了一次。这说明竞态不需要多核，单核时间片切换同样致命：
BOOM! cnt=100000000 (期望 200000000, 丢失 100000000, 完成率 50.00%)
BOOM! cnt=139271793 (期望 200000000, 丢失 60728207, 完成率 69.64%)
BOOM! cnt=104832708 (期望 200000000, 丢失 95167292, 完成率 52.42%)
21.3.2 示例 (b)：基于线程的并发 echo 服务器 echoservert.c
代码 (C)（为可独立编译，把教材 csapp.c 里的 open_listenfd 与 rio_readlineb 换了最简等价实现）：
#define _GNU_SOURCE
/*
* echoservert.c - 基于线程的并发 echo 服务器（CS:APP3e 12.3 的独立可编译版本）
* 每来一个连接就 malloc 一个 connfd 副本 -> pthread_create -> 线程内 detach + free + echo + close
* 用法: ./echoservert <port>
* 编译: gcc -g -Wall -std=c11 echoservert.c -o echoservert -lpthread
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include <pthread.h>
#include <netdb.h>
#include <sys/socket.h>
#include <sys/types.h>
#define LISTENQ 1024
#define MAXLINE 8192
/* ---- 讲义 csapp.c 中 open_listenfd 的最简等价实现 ---- */
static int open_listenfd(const char *port)
{
struct addrinfo hints, *listp, *p;
int listenfd, optval = 1;
memset(&hints, 0, sizeof(hints));
hints.ai_socktype = SOCK_STREAM;
hints.ai_flags = AI_PASSIVE | AI_ADDRCONFIG | AI_NUMERICSERV;
if (getaddrinfo(NULL, port, &hints, &listp) != 0) return -1;
for (p = listp; p; p = p->ai_next) {
if ((listenfd = socket(p->ai_family, p->ai_socktype, p->ai_protocol)) < 0)
continue;
setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &optval, sizeof(int));
if (bind(listenfd, p->ai_addr, p->ai_addrlen) == 0) break;
close(listenfd);
}
freeaddrinfo(listp);
if (!p) return -1;
if (listen(listenfd, LISTENQ) < 0) { close(listenfd); return -1; }
return listenfd;
}
/* ---- rio_readlineb 的等价实现：读满一行（含 '\n'）才返回 ---- */
static ssize_t rio_readlineb_fd(int fd, char *buf, size_t maxlen)
{
size_t i = 0;
char c;
ssize_t rc;
while (i < maxlen - 1) {
if ((rc = read(fd, &c, 1)) == 1) {
buf[i++] = c;
if (c == '\n') break; /* 行结束 */
} else if (rc == 0) { /* EOF */
if (i == 0) return 0;
break;
} else {
if (errno == EINTR) continue;
return -1;
}
}
buf[i] = '\0';
return (ssize_t)i;
}
/* ---- 讲义里的 echo(): 逐行读、原样写回，直到 EOF ---- */
static void echo(int connfd)
{
size_t n;
char buf[MAXLINE];
while ((n = rio_readlineb_fd(connfd, buf, MAXLINE)) != 0)
if (write(connfd, buf, n) != (ssize_t)n) break;
}
/* ---- 线程例程：vargp 指向主线程 malloc 出来的 connfd 副本 ---- */
static void *thread(void *vargp)
{
int connfd = *((int *)vargp); /* 先把值拷到自己栈上，再释放堆内存 */
pthread_detach(pthread_self()); /* 分离态：终止时内核自动回收，无僵尸线程 */
free(vargp); /* 立刻释放参数：生产者-消费者模型 */
printf("[thread %lu] serving fd=%d\n", (unsigned long)pthread_self(), connfd);
fflush(stdout);
echo(connfd);
close(connfd); /* 重要！否则 fd 泄漏 */
return NULL;
}
int main(int argc, char **argv)
{
int listenfd, *connfdp;
socklen_t clientlen;
struct sockaddr_storage clientaddr;
pthread_t tid;
if (argc != 2) { fprintf(stderr, "usage: %s <port>\n", argv[0]); exit(1); }
listenfd = open_listenfd(argv[1]);
if (listenfd < 0) { fprintf(stderr, "open_listenfd failed\n"); exit(1); }
while (1) {
clientlen = sizeof(struct sockaddr_storage);
connfdp = malloc(sizeof(int)); /* 堆上分配，不是栈！ */
*connfdp = accept(listenfd, (struct sockaddr *)&clientaddr, &clientlen);
if (*connfdp < 0) { free(connfdp); continue; }
pthread_create(&tid, NULL, thread, connfdp);
}
return 0;
}
【代码做什么？】
- 主线程在
accept之前就malloc(sizeof(int))，把返回的connfd写进堆，再把堆地址交给新线程。 - 新线程第一件事是从
vargp读出connfd到自己栈上的局部变量，然后pthread_detach(pthread_self())转入分离态。 free(vargp)释放那块堆内存（生产者-消费者模型：主线程分配、线程例程释放）。echo(connfd)逐行读、逐行回写，直到对端关闭；最后close(connfd)。
【底层机制透视】：为什么必须在堆上分配？如果写成 Pthread_create(&tid, NULL, thread, &connfd)，所有线程拿到的 vargp 都指向主线程栈上同一个 connfd 变量。主线程 accept 返回 5 以后马上又 accept 返回 6 并覆盖同一地址，第一个线程醒来时读到的就是 6——它服务的其实是别人的连接。堆上每次 malloc 返回不同地址，从根本上杜绝了共享。这就是讲义所说的”unintended sharing”。
【内存布局 / 数据结构图解】：
✗ 错误写法（传栈地址） ✓ 正确写法（传堆地址）
┌──── 主线程栈 ────┐ ┌──── 主线程栈 ────┐
│ connfd [4字节] │ ◄── &connfd │ connfdp [8字节] │
└──────────────────┘ （所有线程共用） └────────┬─────────┘
▲ ▲ │
│ │ 两个线程的 vargp 都指向这里 ▼
┌────┴──┐┌┴───────┐ ┌──────────────┐
│peer1 ││peer2 │ │ 堆 (brk) │
│vargp ││vargp │ │ [0x...2a0]=4 │◄─ 线程1 独享
└───────┘└────────┘ │ [0x...2c0]=5 │◄─ 线程2 独享
│ [0x...2e0]=6 │◄─ 线程3 独享
└──────────────┘
【实测验证】：三个客户端并发连接（每个客户端发一行、收一行，中间 usleep(300000) 故意停顿 0.3 秒，共 4 轮）：
=== 服务器输出 (server2.log) ===
[thread 139858408371776] serving fd=4
[thread 139858399979072] serving fd=5
[thread 139858391586368] serving fd=6
=== 三个客户端并行总耗时: 1.210508545 秒（若服务器是迭代式的，串行应约 3.6 秒）===
[A] recv: [A] line 0 [B] recv: [B] line 0 [C] recv: [C] line 0
[A] recv: [A] line 1 [B] recv: [B] line 1 [C] recv: [C] line 1
[A] recv: [A] line 2 [B] recv: [B] line 2 [C] recv: [C] line 2
[A] recv: [A] line 3 [B] recv: [B] line 3 [C] recv: [C] line 3
[A] done [B] done [C] done
服务器日志出现三个不同 TID 与三个不同 connfd，说明每个客户端真的由独立线程服务；耗时 1.21 秒 ≈ 4 轮 × 0.3 秒，而非串行的 3 × 1.2 秒——交错执行得到实证。
21.3.3 示例 (c)：基于 select 的事件驱动服务器 selectserver.c
代码 (C)：
/*
* selectserver.c - 基于 I/O 多路复用（select）的事件驱动并发 echo 服务器
* 单线程、单地址空间，用一个 select 循环同时照看 listenfd 与所有 connfd。
* 用法: ./selectserver <port>
* 编译: gcc -g -Wall -std=c11 selectserver.c -o selectserver
*/
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include <netdb.h>
#include <sys/select.h>
#include <sys/socket.h>
#define LISTENQ 1024
#define MAXLINE 8192
#define MAXCONN 16 /* 连接池容量，受 FD_SETSIZE(1024) 限制 */
static int connfd_pool[MAXCONN]; /* -1 表示该槽位空闲 */
static int open_listenfd(const char *port)
{
struct addrinfo hints, *listp, *p;
int listenfd, optval = 1;
memset(&hints, 0, sizeof(hints));
hints.ai_socktype = SOCK_STREAM;
hints.ai_flags = AI_PASSIVE | AI_ADDRCONFIG | AI_NUMERICSERV;
if (getaddrinfo(NULL, port, &hints, &listp) != 0) return -1;
for (p = listp; p; p = p->ai_next) {
if ((listenfd = socket(p->ai_family, p->ai_socktype, p->ai_protocol)) < 0) continue;
setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &optval, sizeof(int));
if (bind(listenfd, p->ai_addr, p->ai_addrlen) == 0) break;
close(listenfd);
}
freeaddrinfo(listp);
if (!p) return -1;
if (listen(listenfd, LISTENQ) < 0) { close(listenfd); return -1; }
return listenfd;
}
int main(int argc, char **argv)
{
int listenfd, connfd, maxfd, nready, i;
fd_set readset;
socklen_t clientlen;
struct sockaddr_storage clientaddr;
char buf[MAXLINE];
if (argc != 2) { fprintf(stderr, "usage: %s <port>\n", argv[0]); exit(1); }
for (i = 0; i < MAXCONN; i++) connfd_pool[i] = -1;
listenfd = open_listenfd(argv[1]);
if (listenfd < 0) { fprintf(stderr, "open_listenfd failed\n"); exit(1); }
printf("[select-server] listening on port %s, listenfd=%d\n", argv[1], listenfd);
fflush(stdout);
while (1) {
/* ------ 每次循环都必须重建 fd_set！select 会就地修改它 ------ */
FD_ZERO(&readset);
FD_SET(listenfd, &readset);
maxfd = listenfd;
for (i = 0; i < MAXCONN; i++) {
if (connfd_pool[i] < 0) continue;
FD_SET(connfd_pool[i], &readset);
if (connfd_pool[i] > maxfd) maxfd = connfd_pool[i]; /* maxfd = 最大描述符 */
}
/* 阻塞直到至少一个描述符就绪，返回就绪个数 */
nready = select(maxfd + 1, &readset, NULL, NULL, NULL);
if (nready < 0) {
if (errno == EINTR) continue; /* 被信号打断，重建 fd_set 再来 */
perror("select"); exit(1);
}
/* ---- 事件 1：listenfd 就绪 => 有新连接到达 ---- */
if (FD_ISSET(listenfd, &readset)) {
clientlen = sizeof(struct sockaddr_storage);
connfd = accept(listenfd, (struct sockaddr *)&clientaddr, &clientlen);
if (connfd >= 0) {
for (i = 0; i < MAXCONN; i++) if (connfd_pool[i] < 0) break;
if (i == MAXCONN) { /* 池满：拒绝该连接 */
printf("[select-server] pool full, reject fd=%d\n", connfd);
close(connfd);
} else {
connfd_pool[i] = connfd;
printf("[select-server] accept fd=%d -> slot %d\n", connfd, i);
fflush(stdout);
}
}
if (--nready == 0) continue; /* 没有别的就绪 fd 了 */
}
/* ---- 事件 2：某个 connfd 就绪 => 读一行并回写 ---- */
for (i = 0; i < MAXCONN; i++) {
connfd = connfd_pool[i];
if (connfd < 0 || !FD_ISSET(connfd, &readset)) continue;
ssize_t n = read(connfd, buf, sizeof(buf) - 1);
if (n > 0) {
buf[n] = '\0';
write(connfd, buf, n); /* echo 回去 */
} else if (n == 0) { /* 对端关闭：EOF 事件 */
printf("[select-server] EOF fd=%d, close slot %d\n", connfd, i);
fflush(stdout);
close(connfd);
connfd_pool[i] = -1;
} else if (errno != EINTR) {
close(connfd);
connfd_pool[i] = -1;
}
if (--nready == 0) break;
}
}
return 0;
}
【代码做什么？】
- 用
connfd_pool[]（连接池）记录当前所有活动连接，-1表示空闲槽位。 - 每轮循环重建
fd_set，把listenfd与池中所有活动connfd都加入，同时求出maxfd，调用select(maxfd+1, ...)。 select返回后先看FD_ISSET(listenfd, &readset)：是则accept，把新connfd塞进池子。- 再遍历池子，对每个
FD_ISSET(connfd, &readset)的就绪连接做一次非阻塞式的读—回写；读到 0 表示对端关闭，close并释放槽位。 - 用
nready提前退出：所有就绪事件处理完就不再空转。
【底层机制透视 —— 状态机视角】：教材 echoservers.c 把每个连接建模成一个状态机（state machine），因为 rio_readlineb 是阻塞的，不能在一个连接上停太久：
┌──────────────┐ 读到一行完整请求 ┌──────────────┐
│ STATE_READ │ ─────────────────► │ STATE_WRITE │
│ 读请求行/头 │ │ 写响应 │
└──────────────┘ └──────┬───────┘
▲ │ 写完成
│ 数据未读完（partial read） ▼
└─────────────────────────── ┌──────────────┐
│ close(connfd)│
└──────────────┘
一旦 read 只返回了半行，服务器必须记住“这个连接读到哪了”，先回去服务别的连接，等 select 下次报告它就绪再接着读。本示例用最简策略（每次就绪读一次、写一次），真正的 echoservers.c 会为每个连接挂一个 rio_t 缓冲区并在状态间迁移。
【实测验证】：三个客户端并发连接同一端口：
=== 服务器输出 (selv.log) ===
[select-server] listening on port 15215, listenfd=3
[select-server] accept fd=4 -> slot 0
[select-server] accept fd=5 -> slot 1
[select-server] accept fd=6 -> slot 2
[select-server] EOF fd=4, close slot 0
[select-server] EOF fd=5, close slot 1
[select-server] EOF fd=6, close slot 2
=== 三个客户端并行总耗时: 0.912821335 秒（串行应约 2.7 秒）===
[A] recv: [A] line 0 / line 1 / line 2 / [A] done
[B] recv: [B] line 0 / line 1 / line 2 / [B] done
[C] recv: [C] line 0 / line 1 / line 2 / [C] done
整个过程只有一条 select 循环、一个线程，却让三个客户端同时得到服务。
补充示例：select 同时监视 stdin 与 socket（本机实跑，用于观察 select 的返回语义）：
=== ./selecttwo 15216（stdin 由管道喂入，另有一路 telnet 式连接）===
round 1: select 返回 1, FD_ISSET(0)=1 FD_ISSET(3)=0 -> 从 stdin 读到: hello-from-stdin
round 2: select 返回 1, FD_ISSET(0)=0 FD_ISSET(3)=1 -> 新连接 connfd=4
round 3: select 返回 1, FD_ISSET(0)=1 FD_ISSET(3)=0 -> 读到 second-line，转发到 connfd=4
round 4: select 返回 1, FD_ISSET(0)=1 FD_ISSET(3)=0 -> 读到 third-line，转发到 connfd=4
round 5: select 返回 1, FD_ISSET(0)=1 FD_ISSET(3)=0 -> stdin EOF，退出
注意第 2 轮 FD_ISSET(0) 从上一轮的 1 变回 0——正是 select 改写了 readset，程序每轮重建集合才得到正确结果。另测得本机 FD_SETSIZE = 1024、sizeof(fd_set) = 128 字节（正好 1024 位）：描述符值 ≥ 1024 时 FD_SET 会越界写，行为未定义——这就是大流量场景必须换成 epoll 的根本原因。
21.4 实验关联
L7 Proxy Lab（写一个带缓存的 HTTP 代理，共 70 分：基础正确性 40 + 并发 15 + 缓存 15）与本讲几乎一一对应：
- Part II（并发，15 分）：writeup 明确要求”为每个新连接派生一个新线程”，并且“线程必须跑在分离态以避免内存泄漏”——正是 21.3.2 中
pthread_detach(pthread_self())那一行。open_clientfd/open_listenfd基于getaddrinfo，是线程安全的。 - Part III（缓存，15 分）：
MAX_CACHE_SIZE = 1 MiB、MAX_OBJECT_SIZE = 100 KiB，淘汰策略近似 LRU。writeup 特别指出：“用一个大的独占锁保护缓存是不可接受的方案”——必须允许多个读者并发读缓存，只允许一个写者写缓存。这就是 Lecture 22–23 的读者-写者锁（readers-writers lock）。缓存数据量的上限是MAX_CACHE_SIZE + T * MAX_OBJECT_SIZE（$T$ 为最大并发连接数）。 - 其他坑：必须忽略
SIGPIPE并优雅处理EPIPE；read可能返回-1且errno == ECONNRESET，不能因此退出；代理长期运行，出错不能exit（csapp.c的错误包装函数需改写）；原请求是 HTTP/1.1 也必须转发为 HTTP/1.0；内容可能是二进制。调试手段：curl -v --proxy、nc -l 12345（可看到代理发出的请求原文）。
L8 SFS Lab 需要在文件系统层面处理并发请求与性能，本讲是它的直接前提；badcnt.c 的”并发写元数据丢失更新”与文件系统的目录/位图更新是同一类问题，而”锁的粒度是整个文件系统还是每个 inode”正是 SFS 的核心设计决策。
21.5 常见错误与调试技巧
- 忘掉
close(connfd)：线程法服务器跑一会儿就accept: Too many open files。调试：ls -l /proc/<pid>/fd \| wc -l观察描述符增长，或strace -f -e trace=close ./server。 - 忘掉
pthread_detach：线程默认是 joinable 的，终止后资源不回收，形成”僵尸线程”式内存泄漏，长期运行必然耗尽内存。调试：周期性打印/proc/self/status的Threads:字段；valgrind --tool=helgrind观察线程状态。 - 把栈地址传给
pthread_create：Pthread_create(&tid, NULL, thread, &connfd)会让多个线程读写主线程栈上同一个int，症状是”某客户端收到别人的数据”或”连接被服务两次”。调试：在线程入口打印vargp与*vargp，多个线程打印出相同地址就是它；gcc -fsanitize=thread能直接报 data race。 select前不重建fd_set：表现为”随机漏事件”、”连接卡住不响应”。调试：在select前后各打印一次位图，能看到返回后被清零的位；strace -e trace=select,pselect6核对每次调用的参数。nfds传错：传成描述符个数而不是maxfd + 1，会漏检编号更大的 fd（例如listenfd=3、connfd=4却传 3）。调试：打印maxfd+1与实际connfd对比。- 在信号处理函数里调用
printf／malloc：讲义用一整段真实 gdb 回溯演示了这个死锁——printf内部要拿 stdout 缓冲区的锁，若主程序正在printf时被SIGCHLD打断，处理函数再次进入printf就会永久阻塞。调试：gdb -p <pid>后bt，堆栈会停在__lll_lock_wait_private→_IO_vfprintf_internal→printf→sigchld→<signal handler called>；处理函数里只允许调用异步信号安全的函数（write、waitpid）。 - 以为
volatile能解决竞态：它只阻止编译器缓存到寄存器，不提供任何原子性。调试：gcc -fsanitize=thread -g x.c -o x -lpthread && ./x，TSan 会打印出冲突的两个访问行号与线程栈。 fork后父子共享描述符造成的”连接不关闭”：客户端已经断开，服务器却一直感知不到 EOF。调试：lsof -p <pid>看是否有多个进程持有同一个 socket。
21.6 关键要点
- 三种并发是”谁交错 + 是否共享地址空间”的二维分类：进程法由内核交错且地址空间独立，事件驱动由程序员交错且单一地址空间，线程法由内核交错但共享地址空间。
select的 fd_set 是输入输出参数——它会被内核就地改写，因此每次调用前都必须FD_ZERO+ 重新FD_SET，且nfds必须是”最大描述符 + 1”，且fd_set上限为FD_SETSIZE = 1024。- 线程服务器的两条铁律：参数必须从栈复制到堆（避免未预期共享），线程必须分离（detach）（避免资源泄漏）；
close(connfd)与free(vargp)一个都不能少。 cnt++不是原子操作——它是 load / add / store 三条指令；两个线程各做一亿次，实测计数落在 90,981,898 ～ 175,343,844 之间，20 次里一次都没到 200,000,000。- 线程的最大优点与最大缺点都是同一件事：数据共享太容易了。竞态的错误结果往往概率很低但绝不为零，而且靠测试几乎抓不到（讲义中同一个
Pthread_create(..., &i)的竞态实验，在多核服务器上”看起来完全正常”，在单核笔记本上则”值到处都是”）。 - 并发的能力边界：进程法隔离好但开销大、共享难；事件驱动开销极小、可控性最强但编码复杂、无法利用多核，一个连接的阻塞会拖垮全部；线程法居中——开销适中、共享容易，但调度不可控、最难调试。
21.7 思考题（带答案）
Q1（推演题 · select 顺序陷阱） 下面这段循环漏掉了对新连接的响应，请指出漏掉的是哪个 fd，并说明为什么：
while (1) {
FD_ZERO(&readset);
FD_SET(listenfd, &readset); /* (1) */
for (i = 0; i < MAXCONN; i++)
if (connfd_pool[i] >= 0) FD_SET(connfd_pool[i], &readset); /* (2) */
select(maxfd + 1, &readset, NULL, NULL, NULL); /* maxfd 在主循环外只算过一次 */
/* (3) 之后直接处理 connfd_pool[]，未再检查 listenfd */
}
答：有两处错误。其一，maxfd 若在主循环外只算一次，则新 accept 到的 connfd（编号更大）永远不会被 select 监视——select 只看 [0, nfds) 范围内的位，FD_SET 设了位也不会被检查，正确做法是每轮重算 maxfd = max(listenfd, 所有 connfd)。其二，若在 (3) 处只遍历 connfd_pool[] 而不先判断 FD_ISSET(listenfd, &readset)，则 listenfd 上的就绪事件被完全丢弃，新连接会一直堆在 TCP 监听队列里（直到队列满、客户端 connect 超时）。还有一个隐藏陷阱：select 返回 EINTR 时 readset 已不可信，必须 continue 重新构建集合。
Q2（推演题 · 线程法服务器的错误写法） 下面这个”简化”的线程服务器错在哪里？给出错误场景与修复：
int connfd;
while (1) {
connfd = Accept(listenfd, (SA *)&clientaddr, &clientlen);
Pthread_create(&tid, NULL, thread, (void *)&connfd);
}
void *thread(void *vargp) {
int fd = *((int *)vargp);
echo(fd);
Close(fd);
return NULL;
}
答：&connfd 是主线程栈上同一个变量的地址，所有线程的 vargp 都指向它。典型坏事序列：主线程 accept 得到 4 并创建线程 1；线程 1 尚未被调度，主线程又 accept 得到 5 覆盖了同一地址；线程 1 醒来读到 5，于是两个线程都去 echo(5)——客户端 4 收不到任何数据（挂死），而 connfd==4 这个描述符永远没人 close（泄漏）。此外该写法还缺少 pthread_detach（线程资源永不回收）与 free（若改成堆分配）。修复：主线程 Malloc(sizeof(int))，把 connfd 写进堆，Pthread_create(&tid, NULL, thread, connfdp)；线程例程第一行先 int fd = *((int *)vargp); 再 Pthread_detach(pthread_self()); Free(vargp);，最后 Close(fd)。
Q3（计算题 · 事件驱动 vs 迭代式的性能） 一个迭代式 echo 服务器，每个客户端请求的服务时间为 $t_{svc} = 2\ \text{ms}$ CPU 时间加 $t_{wait} = 50\ \text{ms}$ 等待用户输入的网络时间；同一份服务逻辑改成事件驱动后，每条连接每次事件的处理开销降为 $0.2\ \text{ms}$。若 100 个客户端同时连接、每个客户端需要 5 轮交互，分别估算两种设计的完成时间，并解释差距来源。
答：迭代式服务器在 read 上阻塞等待，每个客户端每轮要串行占用 $2 + 50 = 52$ ms，因此总时间约为 $100 \times 5 \times 52\ \text{ms} = 26\ \text{s}$。事件驱动服务器不阻塞：它只在数据就绪时才花 $0.2$ ms 处理，100 个客户端的等待时间相互重叠，主导因素是用户输入延迟（约 $5 \times 50\ \text{ms} = 250\ \text{ms}$）加上 CPU 处理量 $100 \times 5 \times 0.2\ \text{ms} = 100\ \text{ms}$，合计约 $350\ \text{ms}$——快约 74 倍。差距来源不是”CPU 更快”，而是等待时间的重叠：迭代式把 100 份等待串行累加，事件驱动让它们并行发生。
Q4（辨析题 · “直觉但错误”的想法） 有同学说：”我把 cnt 声明成 volatile，又在双核机器上跑，badcnt 应该就没问题了吧？实在不行就把 niters 调小一点，问题自然消失。”请指出两处错误。
答：第一处错误：volatile 与并发正确性无关。它只保证每次访问都真的从内存读写（不被优化进寄存器），不保证读—改—写的原子性。真正的执行序列仍是 mov cnt→%rax; add $1,%rax; mov %rax→cnt，两条 mov 之间线程随时可被切走，两个线程可能都基于同一个旧值写回，丢失一次自增。要修好必须用互斥锁、信号量或原子指令（lock addq／C11 atomic_fetch_add）——这正是 Lecture 22 的内容。第二处错误：把 niters 调小并不会让 bug 消失，只会让它更难复现。讲义的原话是”坏结果的概率往往非常低，但非零”；每次自增都有被交错覆盖的可能，niters 越小，撞上的概率越低，但程序依然是错的，而且这种”测试时好好的、上线后偶尔丢数据”的错误代价最高。正确做法是用 gcc -fsanitize=thread 这类工具在开发阶段主动暴露竞态，而不是靠调小负载掩盖它。