быстрый алгоритм упорядочения потоков без атомарного CAS

Question

Я ищу подход, который позволил бы мне присвоить порядковые номера 0 .. (N-1) для N O / S потоков, чтобы потоки были в числовом порядке. То есть получаемый поток будет иметь более низкий идентификатор потока O / S, чем поток с порядковым номером 1.

Для этого потоки взаимодействуют через общее пространство памяти.

Модель упорядочения памяти такова, что запись будет атомарной (если два одновременно работающих потока записывают ячейку памяти одновременно, результат будет один или другой). Платформа не будет поддерживать атомарные операции сравнения и установки.

Я ищу алгоритм, который эффективен по количеству операций записи в разделяемую память и быстро завершится с использованием десятков тысяч потоков без каких-либо неприятных условий поступления потоков в худшем случае.

O / S назначит номера потоков в произвольном порядке на всем протяжении 32-битного пространства. Могут быть произвольные задержки создания потока - алгоритм может считаться завершенным, когда присутствуют все N потоков.

Я не могу использовать очевидное решение - собрать все потоки и затем отсортировать их одним потоком - без атомарной операции у меня нет способа безопасно собрать все отдельные потоки (другой поток может перезаписать слот).

Answer 1

Без претензий на оптимальность в каком-либо смысле (есть явно более быстрые способы сделать это с помощью атомарных операций сравнения и задания, или, как указал Мартин, приращения атомов) ...

Предполагая, что N известно всем потокам, и каждый поток имеет уникальное ненулевое значение идентификатора, например его адрес стека в 32-битном пространстве ...

Использовать массив размера N в общем пространстве; убедитесь, что этот массив инициализирован в ноль.

Каждый поток владеет первым слотом в массиве, который содержит идентификатор, меньший или равный идентификатору потока; поток записывает свой идентификатор там. Это продолжается до тех пор, пока массив не будет заполнен ненулевыми значениями, и все значения не будут в порядке убывания.

По завершении алгоритма индекс слота потока в массиве является его порядковым номером.

Answer 2

Если у меня есть это право, вы хотите отобразить Integer-> Integer, где вход в произвольном 32-битном числе, а вывод это число от 0-N, где N - количество потоков?

В этом случае каждый раз, когда вы создаете новый поток, вызываете этот метод, возвращаемым значением является идентификатор:

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

Этот алгоритм, очевидно, O (N)

Предполагая несколько вещей:

1. темы никогда не умирают
2. У вас есть некоторый атомарный инкремент, который увеличивает число и возвращает старое или новое значение, разница между идентификаторами на основе 0 и 1 на основе
3. Потоки вызывают метод, спрашивающий, какой у них идентификатор, только один раз при создании.