L'implémentation de mon verrou de rotation est-elle correcte et optimale ?

Question

J'utilise un verrou tournant pour protéger une très petite section critique. La contestation se produit très rarement donc un verrou tournant est plus approprié qu'un mutex régulier.

Mon code actuel est le suivant, et suppose x86 et GCC :

volatile int exclusion = 0;

void lock() {
    while (__sync_lock_test_and_set(&exclusion, 1)) {
        // Do nothing. This GCC builtin instruction
        // ensures memory barrier.
    }
}

void unlock() {
    __sync_synchronize(); // Memory barrier.
    exclusion = 0;
}

Alors je me demande :

• Ce code est-il correct ? Assure-t-il correctement l'exclusion mutuelle ?
• Fonctionne-t-il sur tous les systèmes d'exploitation x86 ?
• Fonctionne-t-il aussi sur x86_64 ? Sur tous les systèmes d'exploitation ?
• Est-il optimal ?
  • J'ai vu des implémentations de verrous tournants utilisant le principe de comparaison et d'échange, mais je ne suis pas sûr de la meilleure solution.
  • Selon la documentation des builtins atomiques de GCC ( http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html ), il y a aussi __sync_lock_release . Je ne suis pas un expert en matière de barrières mémorielles et je ne suis donc pas sûr qu'il soit correct pour moi d'utiliser ceci au lieu de __sync_synchronize .
  • J'optimise pour le cas où il n'y a pas de conflit.

Je m'en fiche. du tout sur la contention. Il peut y avoir un, voire deux autres threads qui essaient de verrouiller le spin lock tous les quelques jours. jours .

Answer 1

Cela me semble correct. Btw, voici le manuel scolaire qui est plus efficace même dans le cas contesté.

void lock(volatile int *exclusion)
{
    while (__sync_lock_test_and_set(exclusion, 1))
        while (*exclusion)
            ;
}

Answer 2

Alors je me demande :

* Is it correct?

Dans le contexte mentionné, je dirais oui.

* Is it optimal?

C'est une question tendancieuse. En réinventant la roue, vous réinventez également de nombreux problèmes qui ont été résolus par d'autres implémentations.

• Je m'attendrais à une boucle de gaspillage en cas d'échec où vous n'essayez pas d'accéder au mot de verrouillage.

• L'utilisation d'une barrière complète dans le déverrouillage doit seulement avoir une sémantique de libération (c'est pourquoi vous utiliseriez __sync_lock_release, afin d'obtenir st1.rel sur itanium au lieu de mf, ou un lwsync sur powerpc, ...). Si vous ne vous intéressez qu'à x86 ou x86_64, les types de barrières utilisées ici n'ont pas beaucoup d'importance (mais si vous voulez faire le saut vers l'itanium d'intel pour un portage HP-IPF, vous ne voudrez pas de cela).

• vous n'avez pas l'instruction pause() que vous mettriez normalement avant votre boucle de déchets.

• quand il y a une contention que vous voulez quelque chose , semop, ou même un sommeil stupide en cas de désespoir. Si vous avez vraiment besoin des performances que cela vous apporte, la suggestion de futex est probablement la bonne. Si vous avez suffisamment besoin des performances que cela vous procure pour maintenir ce code, vous avez beaucoup de recherches à faire.

Notez qu'il y avait un commentaire disant que la barrière de libération n'était pas nécessaire. Ce n'est pas vrai, même sur x86, car la barrière de libération sert également d'instruction au compilateur pour ne pas mélanger les autres accès mémoire autour de la "barrière". Cela ressemble beaucoup à ce que vous obtiendriez si vous utilisiez asm ("" :: : "mémoire" ).

* on compare and swap

Sur x86, le sync_lock_test_and_set correspondra à une instruction xchg qui a un préfixe de verrouillage implicite. C'est certainement le code généré le plus compact (en particulier si vous utilisez un octet pour le "lock word" au lieu d'un int), mais pas moins correct que si vous utilisiez LOCK CMPXCHG. L'utilisation de compare and swap peut être utilisée pour des algorthims plus fantaisistes (comme mettre un pointeur non nul sur les métadonnées du premier "serveur" dans le mot de verrouillage en cas d'échec).

Answer 3

En réponse à vos questions :

1. Ça me semble correct
2. En supposant que le système d'exploitation supporte GCC (et que GCC a les fonctions implémentées) ; ceci devrait fonctionner sur tous les systèmes d'exploitation x86. La documentation de GCC suggère qu'un avertissement sera produit si elles ne sont pas supportées sur une plateforme donnée.
3. Il n'y a rien de spécifique aux x86-64 ici, donc je ne vois pas pourquoi pas. Cela peut être étendu pour couvrir tout que GCC prend en charge, mais il existe peut-être des moyens plus optimaux d'y parvenir sur les architectures non x86.
4. Vous pourriez être légèrement mieux en utilisant __sync_lock_release() dans le unlock() car cela décrémentera le verrou et ajoutera une barrière mémoire en une seule opération. Cependant, en supposant que votre affirmation qu'il y aura rarement de la contention ; cela me semble bon.

Answer 4

Si vous êtes sous une version récente de Linux, vous pouvez utiliser un fichier futex -- un "fast userspace mutex" :

Un verrou correctement programmé basé sur futex n'utilisera pas d'appels système, sauf si le verrou est contesté.

Dans le cas non contesté, pour lequel vous essayez d'optimiser votre spinlock, le futex se comportera comme un spinlock, sans nécessiter un appel système du noyau. Si le verrou est contesté, l'attente a lieu dans le noyau sans busy-waiting.

Answer 5

Je ne peux pas me prononcer sur l'exactitude de la réponse, mais le titre de votre question a déclenché un signal d'alarme avant même que je ne lise le corps de la question. Les primitives de synchronisation sont diablement difficiles à garantir... si possible, vous feriez mieux d'utiliser une bibliothèque bien conçue/maintenue, par exemple pthreads o boost::thread .