La file d'attente délimitée multi-producteurs/multi-consommateurs de liblfds est-elle vraiment sans verrouillage ?

Analyse de l'algorithme de file d'attente sans verrouillage

Question : L'algorithme de file d'attente délimitée multi-producteurs/multi-consommateurs est-il dans liblfds sans verrouillage ?

Définition de Sans verrouillage :

Un algorithme sans verrouillage garantit qu'au moins un thread peut progresser indépendamment des threads simultanés. Cela signifie qu'il ne peut pas y avoir de code dans lequel un thread s'appuie sur un autre pour continuer, comme attendre qu'un indicateur soit réinitialisé ou désactivé.

Analyse de l'algorithme :

Le L'algorithme réserve un emplacement dans la file d'attente à l'aide d'une boucle CAS pour incrémenter l'index d'écriture. Il copie ensuite les données utilisateur dans l'emplacement réservé et met à jour le numéro de séquence. Cependant, cette réserve signifie que l'opération POP dépend du fait que le thread PUSH termine la mise à jour du numéro de séquence.

Manque de garantie de progrès :

Selon la définition de « faire progrès", l'algorithme ne répond pas aux critères de verrouillage. La file d'attente peut être observée comme pleine ou vide même si des opérations PUSH ou POP sont en cours, empêchant d'autres threads d'effectuer ces opérations.

Progression partiellement bloquée :

Pendant le L'algorithme peut permettre aux opérations POP de se poursuivre jusqu'à l'élément en cours, cette progression est limitée. Si un thread est modifié en fonction du contexte pendant la région critique entre la mise à jour de l'index d'écriture et l'écriture du numéro de séquence, tous les threads consommateurs signaleront une file d'attente vide.

Mutex caché :

La combinaison de l'index d'écriture et des numéros de séquence d'emplacement agit essentiellement comme un mutex par élément. Une fois qu'un thread incrémente avec succès l'index d'écriture, tous les threads suivants ne peuvent pas écrire dans la file d'attente jusqu'à ce que le thread d'origine termine l'opération.

Avantages en termes de performances :

Malgré le fait que étant strictement sans verrouillage, l'algorithme offre des avantages en termes de performances en termes de :

• Performances incontestées : le chemin rapide consiste à une seule opération CompareAndSwap.
• Performances contestées : la variable d'index d'écriture est contestée, mais le comportement est raisonnable avec une implémentation CAS bien optimisée.

Conclusion :

Bien que l'algorithme fournisse certaines propriétés de performances utiles, il lui manque la propriété d'exactitude clé d'un fonctionnement sans verrouillage en raison du système de réservation et du dépendance entre les opérations PUSH et POP.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!