没有原子CAS快线排序算法 [英] fast thread ordering algorithm without atomic CAS

问题描述

我要寻找那会让我指定的序数0 ..（N-1）为NO / S线程，使得线程都在数值顺序的方法。也就是说，是可以获得线程将具有较低的O / S线程ID不是与螺纹序号1

I am looking for an approach that will let me assign ordinal numbers 0..(N-1) to N O/S threads, such that the threads are in numeric order. That is, the thread that gets will have a lower O/S thread ID than the thread with ordinal 1.

为了实施这一点，线程通过共享内存空间连通。

In order to carry this out, the threads communicate via a shared memory space.

存储排序模型是这样的写操作将原子（如果两个并发线程写在同一时间的存储位置，其结果将是一个或其他）。该平台将不支持原子比较和集合操作。

The memory ordering model is such that writes will be atomic (if two concurrent threads write a memory location at the same time, the result will be one or the other). The platform will not support atomic compare-and-set operations.

我寻找一种算法，是有效的写入共享存储器的数量，并且将迅速完成高达数万线程，并与没有讨厌的最坏情况线程到达条件

I am looking for an algorithm that is efficient in the number of writes to shared memory, and will complete rapidly with up to tens of thousands of threads, and with no nasty worse-case thread arrival conditions.

在O / S会以任意顺序分配的线程数在整个32位空间。可能有任意线程的创建延迟 - 该算法可以被认为是完整的，当所有的N个线程是present

The O/S will assign thread numbers in arbitrary order throughout a 32-bit space. There may be arbitrary thread creation delays - the algorithm can be considered complete when all N threads are present.

我无法使用收集所有的线程，然后有一个线程排序它们的显而易见的解决方案 - 没有一个原子操作，我没有办法安全地收集所有的单个线程（另一个线程可以重写的插槽）。

I am unable to use the obvious solution of collecting all the threads, and then having one thread sort them - without an atomic operation, I have no way of safely collecting all the individual threads (another thread could rewrite the slot).

推荐答案

由于没有声称是最佳的任何意义上的（明显有更快的方法与原子比较并设置操作做到这一点，或者正如马丁指出，原子增量）...

With no claim to being optimal in any sense (there are clearly faster ways to do this with atomic compare-and-set operations, or as Martin indicated, atomic increment)...

假设N已知到所有线程，每个线程有一个独特的非零ID值，例如在32位空间的堆栈地址...

Assuming N is known to all the threads, and each thread has a unique non-zero ID value, such as its stack address in 32-bit space...

使用的共享空间大小N的数组;确保此阵列被初始化为零。

Use an array of size N in shared space; ensure that this array is initialized to zero.

每个线程拥有保存比的ID低于或等于线程的ID的阵列中的第一槽;线程写入其ID出现。这继续直到数组是满的非零值，并且所有的值都以递减的顺序。

Each thread owns the first slot in the array that holds an ID lower than or equal to the thread's ID; the thread writes its ID there. This continues until the array is full of non-zero values, and all the values are in decreasing order.

目前完成的算法，该线程的槽的阵列中的索引是它的序号。

At the completion of the algorithm, the index of the thread's slot in the array is its ordinal number.

这篇关于没有原子CAS快线排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！