7
votes

Ces lignes sont-elles dans une file d'attente sans verrouillage non nécessaire?

Voici un certain code à partir d'une file d'attente sans verrouillage à l'aide de comparaisant (en Java): xxx

(tête et queue sont les membres de la file d'attente)

in La fonction DEQ et ENQ, le premier chèque semble inutile pour moi. (Ceux commencient avec "???") Je soupçonne que c'est là juste pour une sorte d'optimisation.

est-ce que je manque quelque chose ici? Ces chèques affectent-ils l'exactitude du code?

(le code est extrait de "l'art de la programmation multi-processeur", bien que j'ai refacturé le style de code pour avoir moins imbriqué IFS et ESSES, tout en maintenant l'équivalent de code)

java multithreading lock-free

1 commentaires

Ils semblent vérifier que les variables locales ont été fixées de manière cohérente, mais je laisserai à d'autres personnes de répondre si elles affectent l'exactitude du code.

3 Réponses :

2
votes

Ils ne sont pas nécessaires mais utilisés pour des raisons de performance, remarquez que le chèque se produit sans utiliser d'opération atomique.

Exemple coûts de MSDN :

MemoryBarrier a été mesuré comme prenant 20-90 cycles.
Interlockedincrement a été mesuré comme prenant 36-90 cycles.
L'acquisition ou la libération d'une section critique a été mesurée comme prenant 40-100 cycles.
L'acquisition ou la libération d'un mutex a été mesurée comme prenant environ 750-2500 cycles.
référence pour cette technique particulière:

[Rudolph & Segall 84] Rudolph, L. et Segall, Z. Dy-Namic décentralisé Schémas de cache formime parallèle Processeurs. Invù Roancements de Theíúvúth Symposium annuel sur Architecture COM-Puter, Pages 340i> 347, 1984.

0 commentaires

3
votes

Ouais, en Java, étant donné qu'il a une collection de déchets, ces ifs n'ont qu'une valeur réelle comme optimisation, et c'est un peu une grosse: CAS est incroyablement coûteux comparé à une lecture de la mémoire. t a changé entre-temps et diminuant ainsi les chances d'échouer sur le CAS ultérieur, contribue à réduire le nombre de tentatives de réseau, ce qui aide les performances.

Vous pouvez également déplacer le premier == Vérification de la mise à jour de la queue à l'intérieur. La tête.ca, une optimisation supplémentaire: la queue ne peut être décalée derrière uniquement si la tête a été mise à jour, ce qui ne vérifie donc que si le CAS a réussi a du sens. Vous pouvez également déplacer Tail.get là-bas alors, comme vous n'en avez pas besoin nulle part ailleurs. Exemple de code ci-dessous. J'espère que cela aide! xxx

}

0 commentaires

0
votes

C'est un algorithme de liste lié non bloquante. Une description détaillée se trouve dans le livre JCP (15.4.2. Une liste liée non bloquante)

0 commentaires