J'ai terminé mon implémentation de base sur un seul producteur / consommateur sur une file d'attente sans verrure et elle fonctionne bien. Cependant, lorsque j'essaie de l'étendre à un producteur / consommateur multiple, je commence à obtenir des conflits. J'ai trouvé à travers un post similaire lié à cette question ( Y a-t-il une file d'attente sans verrouillage pour plusieurs threads de lecture ou d'écriture? ) et j'ai trouvé un article qui a passé un peu plus loin sur la mise en œuvre initiale. Je suis également confondu sur cet article qui espérerait une certaine orientation.
Le premier est que cette implémentation fonctionne vraiment lors de l'utilisation de plusieurs producteurs / consommateurs ou existe-t-il quelque chose qui me manque dans la mise en œuvre originale Michael-Scott qui fonctionne avec la configuration multiple productrice / consommateur.
La seconde est dans l'article une approche optimiste de la liberté de verrouillage FIFO Les files d'attente La section DEQUEUE indique l'utilisation d'une valeur nominale. Comment puis-je déterminer ce qui est une valeur appropriée à utiliser? Si j'utilise des entiers ce qui me rendra certain que l'entier que je choisis pour la valeur nominale n'est pas une valeur réelle que j'ai décidée de faire la queue?
Un conseil ou une direction générale serait génial. Et si quelqu'un souhaite savoir que je crée cela dans Visual Studio pour mieux comprendre les algorithmes non bloquants. Je voudrais que cela soit aussi universel que possible afin de pouvoir faire la queue de quoi que ce soit souhaité (les données de la file d'attente soient amplifiées afin que l'utilisateur puisse spécifier quoi faire la queue).
3 Réponses :
Vous pouvez créer un type d'emballage bon marché afin que vous puissiez garder une trace de la validité des éléments et que l'utilisateur peut transparence de transmettre des valeurs sans s'en soucier. Cela encourt une petite mémoire de mémoire, mais il n'y a pas vraiment de meilleure façon si vous souhaitez autoriser Enqueue et la déquelle des valeurs null (plutôt que de les traiter comme des sentinelles "mannequin").
Exemple: P>
template<typename T>
class MyQueue
{
/* . . . */
public:
void Enqueue(T * value)
{
MyQueueItem item;
item.value = value;
item.isValid = true;
/* enqueue it now
. . . */
}
T * Dequeue()
{
MyQueueItem validItem;
/* Get the first element where isValid == true
. . . */
return validItem.value;
}
private:
struct MyQueueItem
{
T * value;
bool isValid;
};
};
Il n'y a pas de support explicite pour les instructions de la CPU atomique nécessaires pour mettre en œuvre des files d'attente non bloquantes en C ++ (pourtant, c'est dans les spécifications plus récentes).
Il est possible d'accéder aux instructions de votre machine, mais vous devrez être sous forme d'assemblage ou de trouver une bibliothèque (TBB ou peut-être) qui le fait pour vous.
Peut-être que Cet article est d'intérêt.
J'ai toujours senti qu'un Ringbuffer sans verrouillage est le mieux adapté à un LL-FIFO (je ne sais toujours pas à quel point ils sont sûrs, occupé testant certaines de mes idées ATM).
@Kerreksb: Je cherchais cet article. Merci
@Kerreksb: Après avoir lu cet article, j'ai eu quelques questions, vous pouvez peut-être éclaircir. Cela mentionne l'utilisation de sections critiques et de serrures de spin, donc en général, cela utilise toujours un type de serrure. Dans ce cas, devons-nous avoir une serrure? Est-il là, à l'heure actuelle, aucun algorithme multi-producteur / consommateur moins multi-producteur / consommateur?
@Seb: la "verrouillage" en question n'est qu'un local qui protège une très courte opération, à savoir la mise à jour de deux pointeurs. La filature n'est pas un problème dans ce cas, car vous ne serez pas en train de tourner pendant très longtemps et une attente occupée peut être plus rapide que tout autre type de serrure qui déclencherait un commutateur de contexte. Vous ne pouvez pas faire sans Certains type de synchronisation, et comme il n'y a pas en général une primitive matérielle atomique pour la section critique, le Spinlock est une solution appropriée ...
Jetez un coup d'œil à Concurrencykit.org