我正在寻找一种方法，让我可以将序号 0..(N-1) 分配给 N 个 O/S 线程，以便线程按数字顺序排列。也就是说，获取的线程将比序号为 1 的线程具有更低的 O/S 线程 ID。
为了执行此操作，线程通过共享内存空间进行通信。
内存排序模型使得写入将是原子的(如果两个并发线程同时写入一个内存位置，结果将是一个或另一个)。该平台将不支持原子比较和设置操作。
我正在寻找一种算法，该算法在共享内存的写入次数方面非常高效，并且可以在多达数万个线程的情况下快速完成，并且不会出现糟糕的线程到达情况。
操作系统将在整个 32 位空间中以任意顺序分配线程号。可能存在任意线程创建延迟 - 当所有 N 个线程都存在时，可以认为算法已完成。
我无法使用明显的解决方案收集所有线程，然后让一个线程对它们进行排序 - 如果没有原子操作，我无法安全地收集所有单独的线程(另一个线程可以重写插槽)。
最佳答案
在任何意义上都没有声称是最优的(显然有更快的方法可以使用原子比较和设置操作，或者如 Martin 所指出的，原子增量)...
假设所有线程都知道N，并且每个线程都有一个唯一的非零ID值，比如它在32位空间的栈地址...
在共享空间使用大小为N的数组；确保此数组初始化为零。
每个线程都拥有数组中第一个槽，该槽的 ID 小于或等于线程的 ID；线程在那里写它的ID。这一直持续到数组充满非零值，并且所有值都按降序排列。
算法完成时，线程槽在数组中的索引就是它的序号。
关于algorithm - 没有原子 CAS 的快速线程排序算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2745068/