查看源代码 进程和端口表
问题
进程表是从进程标识符到进程结构指针的映射。进程结构包含关于进程的各种信息，例如指向其堆、消息队列等的指针。当运行时系统需要对进程进行操作时，它会使用进程标识符在进程表中查找进程结构。一个例子是将消息传递给进程。
长期以来，进程表只是一个指向进程结构的指针数组。由于运行时系统内部的进程标识符是 28 位整数，因此很容易将进程标识符映射到数组中的索引。这 28 位被分为两组。最低有效位组用作数组中的索引。最高有效位组仅用于区分映射到数组中同一索引的多个标识符。只要使用 2 的幂的进程表大小，我们就有 2^28 个唯一的进程标识符。
当首次实现 SMP 支持时，该表仍然保持或多或少相同的方式，但受到两种类型的锁的保护。一个锁保护整个表免受修改，而一个锁数组保护表的不同部分。之前使用的确切锁定策略并不重要。重要的是，它遭受了严重的锁争用，尤其是在进行大量修改时，以及仅执行查找时。
为了能够检测何时可以安全地释放先前使用的进程结构，使用了该结构的引用计数。这也是有问题的，因为同时查找需要修改引用计数器，这也导致了引用计数器所在的缓存行的争用。这是因为所有修改都需要在所有涉及的处理器之间进行通信。
端口表与进程表非常相似。至少在概念上，主要的区别在于它是从端口标识符到端口结构的映射。它的实现类似，但有一些差异。它不是指针数组，而是一个结构数组，并且它不是受两种类型的锁的保护，而是仅受一个全局锁的保护。该表在各种情况下也遭受锁争用。
解决方案
进程表是要解决的主要问题，因为进程的使用频率远高于端口。第一个实现仅针对进程实现了这一点，但是由于端口表非常相似，并且在端口表上发生了非常类似的问题，因此进程表实现后来被推广，以便也可以用于实现端口表。为简单起见，在以下文本中我将仅讨论进程表，但除非另有说明，否则同样适用于端口表。
如果我们忽略锁定问题，原始解决方案非常吸引人。从进程标识符到数组索引的映射非常快，并且这是我们想要保留的属性。这些表上的绝大多数操作都是查找，因此优化查找是我们想要做的。
查找
使用进程标识符中的一组位作为数组索引似乎很难被超越。通过将指针数组替换为我们的指针大小原子数据类型数组，查找将包括以下内容
将 28 位整数映射到数组中的索引。
稍后会详细介绍此映射。
使用原子内存操作读取数组中确定索引处的指针。
在我们提供原子内存操作的所有平台上，这只是一个
volatile读取，阻止编译器使用寄存器中的值，从而强制从内存读取。根据使用情况，发出适当的内存屏障。
常用的一种屏障是具有获取语义的屏障。在 x86/x86_64 上，这映射到阻止编译器重新排序指令的编译器屏障，但在其他硬件上，通常也需要某种轻量级硬件内存屏障。
在与锁定方法比较时，在大多数（如果不是全部）硬件架构（包括 x86/x86_64）上锁定锁时，至少会发出一个重量级内存屏障，并且在解锁锁时通常会发出某种轻量级内存屏障。
当查看这个开销非常小的简单解决方案时，您可能想知道为什么我们从一开始就没有以这种方式实现它。这一切都归结为指针的读取操作。我们需要某种方法来知道访问指向的内存是安全的。一种方法是在进程结构中放置一个引用计数器。查找时引用计数器的递增需要与查找原子地完成。锁通常可以为我们提供此服务，这是我们先前使用的方法。另一种方法是将引用计数器与表中的指针并置。此方法的主要问题是修改引用计数器。这是因为这些修改必须在所有涉及的处理器之间进行通信，从而导致包含引用计数器的缓存行的争用。上面的新查找方法是可行的，因为我们可以使用“线程进度”功能来确定何时可以安全地释放进程结构。我们将在描述表中删除时回到这一点。
使用这种新的查找方法，我们将根本不修改任何内存，这非常重要。从概念上讲，查找只是读取内存，现在在实现中也是如此，这从可扩展性的角度来看很重要。之前的实现每次查找都修改了两次包含引用计数器的缓存行，以及两次包含相应锁的缓存行。
表的修改
表中的轻量级查找是最重要的功能，但我们也希望改进表的修改。当生成新进程时（即，将新指针插入到表中），以及当进程终止时（即，从表中删除指针），会修改进程表。
假设我们生成的进程数量少于系统中唯一进程标识符的最大数量，则始终可以通过比较进程标识符来确定进程创建的顺序。如果 PidX 大于 PidY，则假设两个标识符都来自同一节点，则 PidX 是在 PidY 之后创建的。但是，由于我们今天拥有的唯一标识符数量非常有限 (2^28)，如果我们创建大量进程，则不能依赖此属性。但无论如何，这是系统一直具有的属性。
如果我们有大量的可用唯一标识符，那么放弃或修改上面描述的排序属性将是很诱人的。例如，排序属性可以基于执行生成操作的调度程序。可以为每个调度程序线程保留大量的独占标识符范围，这些标识符可用于最大程度地减少分配标识符时的通信需求。但是，我们今天可用的标识符数量甚至不足以采用这种方法。
由于我们拥有的唯一标识符数量有限，因此我们需要小心不要浪费它们。如果过快地重用先前使用的标识符，则来自已终止进程的标识符将引用新创建的进程，并且会发生混淆。先前使用的方法在不浪费标识符方面做得很好。使用相同方法的修改版本也可以让我们保留我们一直拥有的排序属性。
插入
原始方法或多或少是在数组中搜索下一个空闲索引或槽。搜索从最后分配的槽开始。如果我们到达数组的末尾，我们会增加一个“包装计数器”，然后继续搜索。进程标识符是通过将索引写入最低有效位组，并将“包装计数器”写入最高有效位组来构造的。每组中的位数是在启动时确定的，以便最大索引正好适合最低有效位组。
在此方法的修改后的无锁版本中，我们或多或少以相同的方式进行操作，但进行了一些重要的修改，试图避免多个调度程序同时创建进程时发生不必要的争用。由于多个线程可能同时从同一起点尝试搜索下一个空闲槽，因此我们希望后续的槽位于不同的缓存行中。因此，多个调度程序同时将新指针写入表很可能会写入相邻的槽。如果相邻的槽位于同一缓存行中，则此缓存行的所有修改都需要在所有涉及的处理器之间进行通信，这将非常昂贵且扩展性很差。通过将相邻的槽定位在不同的缓存行中，只有真正的冲突才会触发涉及的处理器之间的通信，即避免错误共享。
缓存行比指针大，通常是 8 或 16 倍，因此为每个仅包含一个指针的槽使用一个缓存行会浪费空间。每个缓存行能够容纳固定数量的槽。表的第一个槽将是第一个缓存行的第一个槽，表的第二个槽将是第二个缓存行的第一个槽，直到到达数组末尾。之后的下一个槽将是第一个缓存行的第二个槽，依此类推，每次换行时向前移动一个缓存行内部槽。这样，我们可以在保持相同大小的数组中容纳相同数量的指针，同时始终保持相邻的槽位于不同的缓存行中。
从标识符到槽或数组索引的映射比以前稍微复杂一些。我们不再使用 shift 和按位 and，而是使用两个 shift、两个按位 and 和一个 add（请参阅 erl_ptab.h 中 erts_ptab_data2pix() 的实现）。但是，通过存储针对查找优化的此信息，我们只需要在 32 位平台上使用一个 shift 和一个按位 and。在 64 位平台上，我们有足够的空间将 28 位标识符放在最低有效半字中，将索引放在最高有效半字中，换句话说，我们只需要读取最高有效半字即可获得索引。也就是说，此操作与以前一样快，甚至更快。缺点是在 32 位平台上，在打印或对来自同一节点的标识符进行排序时，我们需要将此信息转换为 28 位标识符编号。然而，与查找相比，这些操作非常不频繁。
当我们在表中插入新元素时，我们执行以下操作
首先，通过原子递增表中进程的计数器，在表中预留空间。如果我们的递增使计数器超过表的最大大小，则操作失败并引发
system_limit异常。该表包含一个 64 位原子变量，表示最后使用的标识符。在实际创建标识符时，只会使用最低有效位。此标识符是搜索的起点。
我们递增最后使用的标识符值。为了确定与此标识符对应的槽，我们调用
erts_ptab_data2pix()，它将标识符映射到槽。我们读取槽的内容。如果槽是空闲的，我们会尝试使用原子比较和交换写入预留标记。如果失败，我们将重复此步骤，直到成功为止。更改最后使用的标识符的表变量。由于可能同时发生多次写入，因此此值可能已被更改为大于我们获取的标识符。在这种情况下，我们可以继续；否则，我们需要将其更改为我们获取的标识符。
我们现在对进程结构进行一些初始化，这些初始化在知道进程标识符之前无法完成，并且必须在将结构发布到表中之前完成。例如，这包括将标识符存储在进程结构中。
现在，我们可以通过在之前在第 3 步预留的槽中写入指向进程结构的指针，将结构发布到表中。
使用这种方法，我们保留了诸如标识符排序和标识符重用之类的属性，同时提高了性能和可伸缩性。但是，它有一个缺陷。无法保证操作会终止。但这很容易修复，并且将在下一个版本中修复。我们将在下面回到这一点。
删除
当进程终止时，我们在进程结构中将进程标记为已终止，表中进程数的计数器会递减，并通过在相应的槽中写入 NULL 指针来删除对进程结构的引用。执行此操作的调度程序线程随后调度一个线程进度后期作业，该作业将执行最终清理并释放进程结构。线程进度功能将确保此作业在确定所有托管线程都已删除对进程结构的所有引用之前不会执行。
BIF 迭代表
erlang:processes/0 和 erlang:ports/0 BIF 会迭代表并返回相应的标识符。这些 BIF 应该在 BIF 执行期间返回表内容的一致快照。为了实现这一点，我们以一种奇怪的方式使用锁定。我们使用“反向读写锁”。
在表中执行查找时，我们根本不需要担心锁定，但是当修改表时，我们会读取锁定保护表的读写锁，这允许在正常操作期间有多个写入器。当迭代表的 BIF 需要访问表时，它会写入锁定读写锁并读取表的内容。BIF 不会一次读取整个表，而是每次读取小块，仅在读取时写入锁定。BIF 的实际实现不在本文档的范围内。
一个现成的读写锁通常会遭受包含读写锁状态的单个缓存行上的争用，即使我们只是进行读取锁定也是如此。我们没有使用这样的读写锁，而是拥有我们自己实现的读取器优化读写锁，它在单独的线程特定缓存行中跟踪读取器线程。这是为了避免在单个缓存行上发生争用。只要我们只执行读取锁定操作，线程就只需要读取全局缓存行并修改自己的缓存行，从而最大程度地减少相关处理器之间的通信。迭代 BIF 通常很少使用，因此在正常情况下，我们只会在表全局读写锁上执行读取锁定操作。
未来的改进
第一个改进是修复保证，以便保证插入操作会终止。当操作开始时，我们会验证是否确实存在可以使用的空闲槽。问题是，我们可能找不到它，因为它可能会在多个线程在尝试查找槽的同时修改表时移动。简单的修复方法是在有限的操作次数中找不到空闲槽时中止操作，然后在写入锁下重新启动操作。这将在下一个版本中实现，但应该进行更多工作，尝试找到更好的解决方案。
当表几乎满时，此实现和以前的实现都不能很好地工作。我们将获得更长的空闲槽搜索时间，并且由于在搜索期间我们更频繁地换行，因此我们将更频繁地重用标识符。当表比同时存在的进程数量大得多时，这些表效果最佳。一个简单的改进是始终有空间容纳比我们在表中允许的更多的进程。这也将在下一个版本中实现，但可能也应该更多地努力寻找更好的解决方案。
如果能够完全摆脱读写锁，那就太好了。使用读取器优化读写锁可以确保我们在锁上没有任何争用，但是由于锁，将会发出不必要的内存屏障。这里的主要问题是修改迭代 BIF，使其在读取一系列槽时不需要独占访问表。原则上，这应该相当容易，代码可以处理可变大小的序列，因此将槽的序列大小缩小为一个就可以解决问题。但是，这需要对非平凡代码进行一些调整和修改，但这应该是将来应该考虑的事情。
通过增加标识符的大小，至少在 64 位计算机上（这并不像乍看起来那么容易），我们可以获得进一步的改进空间。除了不象我们目前这样快地重用标识符的明显改进之外，它还可以在将元素插入表时进一步避免争用。至少如果我们放弃此排序属性的话，反正它也不是那么有用。
一些基准测试结果
为了测试进程表的修改，我们运行了一些基准测试，其中同时生成和终止大量进程，并获得了 150-200% 的加速。运行类似的基准测试，但使用端口，我们获得了大约 130% 的加速。
BIF erlang:is_process_alive/1 是您能获得的最近似于进程表查找的操作。BIF 会查找与作为参数传递的进程标识符对应的进程，然后检查它是否处于活动状态。通过运行多个进程循环执行此 BIF 并检查同一进程，我们获得了 20000-23000% 的加速。从概念上讲，此操作仅涉及读取操作。在 R16B 中使用的实现中，也仅执行读取操作，而之前的实现需要锁定结构才能读取数据，从而遭受锁定争用以及由于修改锁内部数据结构和要查找的进程上的引用计数器使用的缓存行而引起的争用。
这些基准测试是在一台相对较新的机器上运行的，该机器配备了具有超线程的 Intel i7 四核处理器，并使用了 8 个调度程序。在具有更多通信开销和/或更多逻辑处理器的机器上，预计加速会更大。