fast thread ordering algorithm without atomic CAS

Question

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.

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).

Answer 1

If I have this right you want to map Integer->Integer where the input in an arbitrary 32 bit number, and the output is a number from 0-N where N is the number of threads?

In that case, every time you create a new thread call this method, the returned value is the ID:

integer nextId = 0;
integer GetInteger()
{
    return AtomicIncrement(nextId);
}

This algorithm is obviously O(N)

Assuming several things:

1. threads never die
2. You have some kind of atomic increment which increments a number and returns the old value or the new value, the difference is between 0 based and 1 based IDs
3. Threads call a method asking what their ID is just once when they're created

Answer 2

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)...

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...

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

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.