algorithme de commande de fil rapide sans atomique CAS

Question

Je cherche une approche qui me permettra d'assigner des nombres ordinaux 0 .. (N-1) à N O/S threads, de sorte que les threads sont dans un ordre numérique. C'est-à-dire que le thread qui obtient aura un ID de thread O/S inférieur au thread avec un ordinal 1.

Pour ce faire, les threads communiquent via un espace mémoire partagé. Le modèle d'ordre de mémoire est tel que les écritures seront atomiques (si deux threads simultanés écrivent un emplacement mémoire en même temps, le résultat sera l'un ou l'autre). La plate-forme ne prendra pas en charge les opérations de comparaison et de définition atomiques. Je recherche un algorithme qui soit efficace en termes de nombre d'écritures dans la mémoire partagée, et qui se termine rapidement avec des dizaines de milliers de threads, sans aucune mauvaise situation d'arrivée de thread.

Le système d'exploitation attribuera des numéros de thread dans un ordre arbitraire dans un espace de 32 bits. Il peut y avoir des retards de création de threads arbitraires - l'algorithme peut être considéré comme terminé lorsque tous les N threads sont présents. Je suis incapable d'utiliser la solution évidente de rassembler tous les threads, puis de les trier - sans opération atomique, je n'ai aucun moyen de collecter en toute sécurité tous les threads individuels (un autre thread pourrait réécrire le slot) .

Answer 1

Si j'ai ce droit, vous voulez mapper Integer-> Integer où l'entrée dans un nombre arbitraire de 32 bits, et la sortie est un nombre de 0-N où N est le nombre de threads?

Dans ce cas, chaque fois que vous créez un nouvel appel de fil cette méthode, la valeur retournée est l'ID:

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

Cet algorithme est évidemment O (N)

En supposant plusieurs choses:

1. fils ne meurent jamais
2. Vous avez une sorte d'incrément atomique qui incrémente un nombre et retourne l'ancienne valeur ou ne w valeur, la différence se situe entre 0 et 1 à base ID basés
3. threads appellent une méthode demande ce que leur identité est juste une fois quand ils sont créés

Answer 2

Sans prétention d'être optimale dans tous les sens (il y a des méthodes nettement plus rapides pour faire cela avec des opérations atomiques de comparaison et d'ensemble, ou comme Martin l'indique, incrément atomique) ...

En supposant que N est connu de tous les threads, et que chaque thread a une valeur d'ID unique non nulle , comme son adresse de pile dans l'espace de 32 bits ...

Utilisez un tableau de taille N dans l'espace partagé; assurez-vous que ce tableau est initialisé à zéro.

Chaque thread possède le premier emplacement du tableau qui contient un ID inférieur ou égal à l'ID du thread; le fil écrit son ID là. Cela continue jusqu'à ce que le tableau soit plein de valeurs non nulles, et toutes les valeurs sont dans l'ordre décroissant.

À la fin de l'algorithme, l'indice de l'emplacement du thread dans le tableau est son nombre ordinal.