Mon verrou rotation mise en œuvre correcte et optimale?

Question

J'utilise un verrou de rotation pour protéger une très petite section critique. Contention arrive très rarement un verrou de rotation plus approprié qu'un mutex régulier.

Mon code actuel est le suivant, et prend 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;
}

Je me demande:

• Est-ce bon code? Est-il assurer correctement l'exclusion mutuelle?
• Est-ce que ça fonctionne sur tous les systèmes d'exploitation x86?
• Est-ce que ça marche sur x86_64 aussi? Sur tous les systèmes d'exploitation?
• Est-il optimal?
  • J'ai vu des implémentations de verrouillage de spin à l'aide de comparer et-échange, mais je ne suis pas sûr de mieux.
  • Selon la documentation builtins atomique 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 sur les obstacles de mémoire, donc je ne suis pas sûr que ça me va bien pour d'utiliser ce lieu de __sync_synchronize.
  • Je l'optimisation pour le cas où il n'y a pas de conflit.

Je ne me soucie pas tout sur les conflits. Il peut y avoir 1, peut-être deux autres threads essayant de verrouiller le verrou de rotation une fois tous les quelques jours .

Answer 1

Je me demande:

* Is it correct?

Dans le contexte mentionné, je dirais que oui.

* Is it optimal?

C'est une question chargée. En réinventant la roue vous réinventent aussi beaucoup de problèmes qui ont été résolus par d'autres implémentations

• J'attends une boucle de déchets en cas d'échec où vous essayez de ne pas 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 la raison pour laquelle vous utiliseriez __sync_lock_release, de sorte que vous obtiendrez sur st1.rel itanium au lieu de mf, ou un lwsync sur powerpc, ...). Si vous avez vraiment ne vous préoccupez x86 ou x86_64 les types d'obstacles utilisés ici ou ne pas faire pas autant d'importance (mais si vous où faire le saut au itanium de intel pour un port HP-IPF alors vous ne voulez pas cela).

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

• quand il y a affirmation que vous voulez quelque chose , semop, ou même un sommeil stupide en désespoir de cause. Si vous avez vraiment besoin de la performance que cela vous achète alors la suggestion de futex est probablement un bon. Si vous avez besoin de la performance que cela vous achète assez mauvais 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'a pas été nécessaire. Ce n'est pas vrai même sur x86, car la barrière de libération sert également une instruction au compilateur de ne pas autre lecture aléatoire accès mémoire autour de la « barrière ». Très semblable à ce que vous obtiendriez si vous avez utilisé asm ( "" ::: "mémoire").

* on compare and swap

Sur le x86 sync_lock_test_and_set tracera à une instruction de xchg qui a un préfixe de verrouillage implicite. Certainement le code généré le plus compact (en particulier. Si vous utilisez un octet pour le « mot de verrouillage » au lieu d'un int), mais pas moins correct que si vous utilisez BLOCAGE cmpxchg. Utilisation de comparaison et d'échange peut être utilisée pour plus chics algorthims (comme mettre un pointeur non nul de métadonnées pour le premier « serveur » dans le mot de verrouillage en cas d'échec).

Answer 2

On dirait bien pour moi. , Est ici BTW la mise en œuvre manuel qui est plus efficace, même dans le cas soutenu.

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

Answer 3

En réponse à vos questions:

1. On dirait ok me
2. En supposant que le système d'exploitation prend en charge GCC (GCC et a les fonctions mises en oeuvre); cela devrait fonctionner sur tous les systèmes x86 d'exploitation. La documentation de GCC indique que sera produit un avertissement si elles ne sont pas pris en charge sur une plate-forme donnée.
3. Il n'y a rien x86-64 spécifique ici, donc je ne vois pas pourquoi pas. Cela peut être étendu à any architecture du CCG soutient, mais il peut y avoir des moyens plus optimaux d'y parvenir sur des architectures non x86.
4. Vous pourriez être un peu mieux à l'utilisation __sync_lock_release() dans le cas de unlock(); car cela décrémenter la serrure et ajouter une barrière de mémoire en une seule opération. Cependant, en supposant que votre affirmation selon laquelle il y aura rarement discorde; il me semble bon.

Answer 4

Si vous êtes sur une version récente de Linux, vous pouvez être en mesure d'utiliser un futex - un "mutex rapide userspace":

  

Un verrou à base de futex-correctement programmé ne sera pas utiliser des appels système, sauf lorsque le verrou est soutenu

Dans le cas non contesté, que vous essayez d'optimiser pour votre spinlock, le futex se comportera comme un spinlock, sans nécessiter un syscall du noyau. Si le verrou est contesté, l'attente se déroule dans le noyau sans attente active.

Answer 5

Je me demande si la mise en œuvre du CAS suivant est le correct sur x86_64. Il est presque deux fois plus rapide sur mon ordinateur portable X920 Core i7 (fedora 13 x86_64, gcc 4.4.5).

inline void lock(volatile int *locked) {
    while (__sync_val_compare_and_swap(locked, 0, 1));
    asm volatile("lfence" ::: "memory");
}
inline void unlock(volatile int *locked) {
    *locked=0;
    asm volatile("sfence" ::: "memory");
}

Answer 6

Je ne peux pas commenter l'exactitude, mais le titre de votre question soulevée un drapeau rouge avant d'avoir lu le corps même de la question. primitives de synchronisation sont diaboliquement difficiles pour assurer la justesse ... si possible, vous êtes mieux d'utiliser un système bien conçu / bibliothèque gérée, peut-être ou href="http://www.boost.org/doc/libs/1_40_0/doc/html/thread.html" rel="nofollow noreferrer"> boost: :. fil

Answer 7

Une amélioration est Suggest est en utilisant tatas (test et test -Et mettre). Utilisation des opérations CAS sont considérées comme assez cher pour le processeur, il est donc préférable de les éviter si possible. Une autre chose, assurez-vous que vous ne souffrirez pas d'inversion de priorité (si un thread avec une priorité élevée tente d'acquérir le verrou tout en un fil avec une faible priorité essaie de libérer le verrou? Sous Windows par exemple ce problème sera en fin de compte par résolu par le planificateur à l'aide d'un coup de pouce de priorité, mais vous pouvez donner explicitement jusqu'à la tranche horaire de votre fil dans le cas où vous n'avez pas réussi à acquérir le verrou en vous 20 essais (par exemple ..)

Answer 8

Votre procédure de déverrouillage n'a pas besoin de la barrière de mémoire; l'affectation d'exclusion est atomique tant qu'il DWORD aligné sur le x86.

Answer 9

Dans le cas particulier de x86 (32/64) Je ne pense pas que vous avez besoin d'une clôture de mémoire du tout dans le code de déverrouillage. x86 ne fait pas de réordonnancement, sauf que les magasins sont d'abord placés dans un tampon de stockage et donc les devenir visible peut être retardée pour d'autres threads. Et un fil qui fait un magasin et lit de la même variable sera lu à partir de son tampon de stockage si elle n'a pas encore été vidées à la mémoire. Donc, tout ce dont vous avez besoin est une déclaration asm pour éviter réordonnancements du compilateur. Vous courez le risque d'un fil tenant le verrou légèrement plus long que nécessaire du point de vue des autres threads, mais si vous ne se soucient pas de discorde qui ne devrait pas d'importance. En fait, pthread_spin_unlock est mis en œuvre comme ça sur mon système (x86_64 linux).

Mon système met également en œuvre à l'aide pthread_spin_lock lock decl lockvar; jne spinloop; au lieu d'utiliser xchg (qui est ce que __sync_lock_test_and_set utilisations), mais je ne sais pas s'il y a effectivement une différence de performance.

Answer 10

Il y a quelques hypothèses erronées.

D'abord, SpinLock n'a de sens que si est verrouillé sur ressource autre CPU. Si est verrouillé sur ressource même CPU (ce qui est toujours le cas sur les systèmes monoprocesseurs), vous avez besoin de vous détendre dans ordonnanceur de déverrouillage de ressource commande. Vous travaillerez code actuel sur le système monoprocesseur, car le programmateur passe tâches automatiquement, mais une perte de ressource.

Le système multi-processeurs, la même chose peut happends, mais la tâche peut migrer d'un processeur à l'autre. En bref, l'utilisation de verrouillage de rotation est correct si vous garantissons que vos tâches seront exécutées sur différents CPU.

En second lieu, le verrouillage d'un mutex est rapide (aussi vite que spinlock) quand est est déverrouillé. Mutex verrouillage (et déverrouillage) est lent (très lent) que si mutex est déjà verrouillé.

Alors, dans votre cas, je vous suggère d'utiliser les mutex.