论文阅读笔记：The Native POSIX Thread Library for Linux
注：讲解 nptl 设计的论文，背景是 LinuxThread 的实现不够好，后面有 nptl 路线和 ngpt 两个路线，最终 nptl 胜出。
Drepper 提前说明，文章内容可能是过时的。注：这篇文章发表于2005年。
最早的实现
1996年 LinuxThreads 的实现：
- 基本假设，相关进程之间上下文切换速度足够快，可以让一个内核线程去处理一个用户级线程。
- 设计上没有使用线程寄存器，线程本地内存依靠线程控制块和堆栈指针定位。
- 为了实现信号处理、线程创建以及其他的进程管理，引入了管理线程。
- 最大的问题，内核缺少同步原语，使得不得不使用信号。同时，内核中没有线程组的概念，也使得线程库中信号处理脆弱。
随着时间的推移的改进
接下来Linux线程库的改进，主要是两部分，ABI和内核。
ABI扩展允许线程寄存器像寄存器一样工作，从而使得定位TLS不再是一个耗时的操作。有些架构为此预留了这样的寄存器，有些架构提供了执行上下文中存储值的功能。有一些这两者都没有提供， 还是只能依靠堆栈地址计算。
IA-32是最重要的架构，它有两个没有使用的段寄存器%fs和%gs。虽然这两个寄存器不能存储任意值，但是可以访问任意的虚拟地址。通过不同的基地址+同样的偏移量，可以实现TLS想要的功能。
但是，这个做法的问题是，段寄存器必须由处理器使用某些数据结构支持。段的基地址在描述符表中，而对描述符表的访问必须由操作系统操作，所以修改描述符表很慢。
另外，由于需要描述符号表的参与，因此，表示不同地址的数量被限制在了8192，同样的，线程的数量因此受到了同样的限制。
另外，clone 调用也被做了改进，用来消除对管理线程的某些要求，但是管理线程还是没有办法去掉，因为：
1）线程的栈内存无法由这个线程本身释放。
2）为了避免僵尸线程。
当前实现的问题
- 管理线程的问题，管理线程成为了瓶颈。并且如果管理线程被杀死，那么其他的线程只能手动清理。
- 信号的实现不符合 POSIX 标准，没有实现向整个线程发送信号。
- 信号实现同步原语的问题，延迟很高；虚假唤醒一直存在，需要处理；对虚假唤醒的处理给内核信号系统带来了更大的压力。
- SIGSTOP 和 SIGCOND ，如果内核没有正确处理这些信号，那么无法停止多线程，只能停止一个线程，我们的调试器 debugger 就没法使用了。
- 每个线程都有自己的 PID，这和 POSIX 的标准也不兼容。
- 线程数量 8192 的限制也是问题，尽管出现问题的场景，大概率是因为错误的使用了线程库。
同时，给内核也带来了一些问题：
- /proc 下面的文件系统几乎无法使用了，塞满了线程。
- 类似 SIGISTOP 这种操作需要操作所有线程，只能让内核来做。
- 信号当作同步原语，太重了。
新的实现的目标
为什么不修复当前的实现，而是要重写，原因是，当前的实现的核心是以当时 Linux 内核的限制为中心的。
新的实现需要是 ABI 兼容的，这个主要是依靠 POSIX 提供的标准。
- 最重要的，POSIX 兼容性的支持，同时也可以添加一些 POSIX 之外的扩展。
- 充分利用 SMP 系统。
- 创建线程的代价要很小，这样即使很小的工作，可以使用新的线程解决。
- 尽量在二进制上和原来的 LinuxThreads 库保持兼容。（但是由于 LinuxThread 没有实现 POSIX 规范，因此完全的兼容很难。）
- 硬件扩展行好：处理器增加，管理成本不会增加太多。
- 软件扩展性好：线程是在另外的一个上下文运行，可以创建大量的线程，新的线程或者其他的对象没有固定的限制。
- NUMA 支持。
设计决策
1:1 还是 M:N
内核线程和用户级别线程的对应关系是一个基本的需要决策的。1:1的实现下，用户级线程只是在内核线程上面再做比较薄的一层。而 M:N 模型，则需要在内核态和用户态各维护一个线程调度器，并且两者需要比较好的配合协作。如果协作的不好，那么会影响性能。
内核开发者的普遍共识是，M:N 模型不适合引入内核，引入的话，对内核的基础能力需要的修改太大。为了做到用户态的线程切换，需要从内核态向用户态拷贝寄存器的内容。
另外，需要用户态调度解决的问题，内核态当前的调度也能够搞定，因为已经有了 O(1) 调度器，大量的线程并不是问题。
最后，1:1 的实现简洁很多。
信号处理
注：信号的出现比线程要早，信号处理范围是进程级别的属性。
信号掩码是线程范围的（注：POSIX定义的吗？），所以，这就要求，内核需要处理所有线程的掩码，以确认是否可以给该线程传递信号。
考虑使用 M:N 模型，我们将 M 控制在低水平，那么信号掩码的确认，就可以在用户态完成了。但是在用户态处理信号有一些缺点，为此，可能使用专用信号处理线程或者让内核支持另外一种新的信号机制。
对应的是，可以采用 1:1 模型，内核唯一需要关注的是，处理所有线程的信号掩码，但是这也是唯一的问题。
管理线程？
之前的实现中，存在不执行业务的管理线程，主要为了：
- 为了能够处理致命信号，杀死所有的线程，如果没有管理线程，那么内核就需要处理这种场景。
- 线程销毁之后的栈内存需要回收，因为线程本身没有办法回收。
- 处理僵尸线程。
- 主线程调用 pthread_exit 之后，不会退出，而是进入睡眠，如果进程退出，需要管理线程通知主线程。
- 帮助处理信号量问题。
- 线程局部数据的释放，需要遍历所有线程，只能由管理线程来处理。
这些原因并不是都一定需要管理线程做，如果内核实现了，那么管理线程就不必自己处理，比如
- 如果内核正确实现了 POSIX 信号，那么问题1就不需要管理线程。
- 问题 2 可以让内核来做，暂且不论怎么实现。
- 问题 3 可以让内存处理终止的线程。
其他的问题也可以让内核或者线程库来解决。
并且，管理线程只能在一个 CPU 上运行，因此，任何同步都会导致 SMP 系统上产生严重的问题，更不用说 NUMA 系统架构了。
线程列表
之前的线程库的实现中，保存了所有线程的列表，一个重要的原因是，在 kill 所有线程的场景，需要线程列表。
线程列表也被用于实现 pthread_key_delete 操作。在调用 pthread_key_delele 之后，然后再调用 pthread_key_create 重新使用这个 key 时，必须保证所有线程中与这个 key 关联的值均为 NULL。
这个可以通过一个递增计数器来替代实现。
但是，维护线程列表是无法完全避免的。当调用 fork 的时候，必须清除当前fork线程之外的所有线程，否则就会导致内存泄漏。
同步原语
互斥、读写锁、条件变量、信号量、屏障等同步原语需要内核某种形式的支持；忙等待是不可行的，因为线程拥有不同的优先级，因此同样 sched yield 也不合适。（注：为什么？）
在旧的实现中，信号成了唯一可行的机制——线程阻塞在内核中，等待被唤醒。
信号处理的方式，性能不是很好，并且也不是很可靠，因为虚假唤醒的机制，以及在应用程序中处理信号。
所幸，内核提供了 futex 机制（注：从2.5起），可以用来实现这些同步原语。
futex 的原理很简单，但是功能很强大，可以被广泛应用。
mutex 互斥量可以 6 条指令实现，其中快速路径（注：比如没有竞争）完全可以在用户级别实现。
futex 的另一个好处是，适用于共享内存区域。因此，futex 可以由访问相同共享内存的 process 共享。另外，等待队列由内核维护，这些正符合 POSIX 的同步原语的要求。
内存分配
新的线程库的一个目标，即降低线程创建的成本。其中最大的问题，就是线程的数据结构、TLS以及栈空间。优化方式主要有两个方法。
1）合并某些内存，比如线程的数据结构和TLS是放在栈上的。
2）复用了线程栈，因为 munmap 是比较影响性能的，munmap 会引起 TLB 的刷新，进而需要广播道其他的 CPU。这个方案的好处很多，唯一的缺点是，我们前后可能拿到相同的线程句柄，但是这其实并不是一个问题。
内核的改进
内核功能和线程库的设计是同时进行的，以确保两个组件之间的最佳接口。
1）引入了 TLS 系统调用，支持了任意数量的线程特定数据区域。主要解决了使用线程寄存器带来的 8192 个线程的限制。
实现了1:1模型，且不受线程数量的限制。在这之前的实现，因为 LDT ，每个进程的线程被限制在了8192。
2）clone 的改进用来避免管理线程，新的实现中， thread ID 存在给定的位置；另外，内核也可以使用 futex 唤醒这个 thread ID，这个特性被用来实现 pthread_join。
3）POSIX 的多线程的信号实现，当前是在内核中。发送给进程的信号，被传递给一个可以接受信号的线程；致命信号结束整个线程。
4）在原有的 exit 外，又引入了 exit_group; exit 保持了结束当前线程的语意，而 exit_group 则是会结束整个进程；exit 自身的性能也得到了很大的提升。
5）exec 系统调用，给新的进程提供原始进程的进程ID。
6）报告给上游的统计信息，是针对整个进程，而不是某个线程。
7）/proc 目录针对多线程做了改进。
8）提供了线程 detach，detach 的线程不需要 join，系统会使用 futex 通知内核。
9）内核在每个线程退出之前，一直保留初始线程，保证了进程在 /proc 可见，并且保证了信号可以传递。
结果
主要是和 LinuxThreads 以及 NGPT 对比。
待改进的挑战
在完全实现 POSIX 兼容之前，还有一些挑战。
- setuid 和 setgid 需要影响整个进程，而不只是初始化的线程。
- nice 级别应该是进程级别，影响所有线程。
- cpu 的统计信息。
- 实时调度的支持。