Implémentation d’un mutex FIFO dans les pthreads

J’essaie d’implémenter une arborescence binary prenant en charge les insertions simultanées (ce qui pourrait se produire même entre les nœuds), mais sans avoir à allouer de verrou global ni de mutex ou mutex distinct pour chaque nœud. Au lieu de cela, la quantité allouée de tels verrous devrait être de l’ordre de la quantité de threads utilisant l’arbre.

Par conséquent, je me retrouve avec un type de problème de convoi de serrures . Expliqué plus simplement, c’est ce qui se passe potentiellement lorsque deux ou plusieurs threads procèdent comme suit:

 1 pour (;;) {
 2 serrure (mutex)
 3 do_stuff
 4 déverrouiller (mutex)
 5}

C’est-à-dire que si le fil 1 exécute les instructions 4-> 5-> 1-> 2 tout en un “cpu burst”, le fil 2 sera privé de l’exécution.

D’autre part, s’il existait une option de locking de type FIFO pour les mutex dans les pthreads, un tel problème pourrait être évité. Alors, est-il possible d’implémenter le locking mutex de type FIFO dans les pthreads? Est-ce que la modification des priorités de fil peut accomplir cela?

Vous pouvez faire quelque chose comme ça:

  • Définissez un “verrou en queue” constitué d’un indicateur de disponibilité et d’une liste liée de variables de condition pthread. l’access au queued_lock est protégé par un mutex

  • pour verrouiller le queued_lock:

    • saisir le mutex
    • vérifier le drapeau ‘occupé’
    • si pas occupé; mis occupé = vrai; libérer le mutex; terminé
    • si occupé créer une nouvelle condition @ fin de queue et attendre dessus (relâcher mutex)
  • déverouiller:

    • saisir le mutex
    • si aucun autre thread n’est en queue, busy = false; libérer le mutex; terminé
    • pthread_cond_signal la première condition d’attente
    • n’effacez pas le drapeau ‘occupé’ – la propriété passe à l’autre thread
    • libérer le mutex
  • en attente, le thread est débloqué par pthread_cond_signal:

    • enlever notre condition var de la tête de file
    • libérer le mutex

Notez que le mutex n’est verrouillé que pendant la modification de l’état de queued_lock, pas pendant toute la durée de la détention de queued_lock.

Vous pouvez implémenter un système de mise en queue équitable dans lequel chaque thread est ajouté à une file lorsqu’il bloque, et le premier thread de la file obtient toujours la ressource lorsqu’elle devient disponible. Un tel verrou “équitable” basé sur des primitives pthreads pourrait ressembler à ceci:

 #include  typedef struct ticket_lock { pthread_cond_t cond; pthread_mutex_t mutex; unsigned long queue_head, queue_tail; } ticket_lock_t; #define TICKET_LOCK_INITIALIZER { PTHREAD_COND_INITIALIZER, PTHREAD_MUTEX_INITIALIZER } void ticket_lock(ticket_lock_t *ticket) { unsigned long queue_me; pthread_mutex_lock(&ticket->mutex); queue_me = ticket->queue_tail++; while (queue_me != ticket->queue_head) { pthread_cond_wait(&ticket->cond, &ticket->mutex); } pthread_mutex_unlock(&ticket->mutex); } void ticket_unlock(ticket_lock_t *ticket) { pthread_mutex_lock(&ticket->mutex); ticket->queue_head++; pthread_cond_broadcast(&ticket->cond); pthread_mutex_unlock(&ticket->mutex); } 

L’exemple que vous postez n’a pas de solution. Fondamentalement, vous n’avez qu’une section critique et il n’ya pas de place pour le parallélisme.

Cela dit, vous voyez qu’il est important de réduire au minimum la période pendant laquelle vos threads maintiennent le mutex, à peine quelques instructions. Cela est difficile à insérer dans une structure de données dynamic telle qu’une arborescence. La solution la plus simple est d’avoir un verrou en lecture-écriture par nœud.

Si vous ne voulez pas avoir de verrous individuels par nœud d’arbre, vous pouvez avoir une structure de verrou par niveau de l’arbre. Je ferais des expériences avec des verrous en lecture-écriture pour cela. Vous pouvez simplement verrouiller en lecture le niveau du nœud en main (plus le niveau suivant) lorsque vous parcourez l’arbre. Ensuite, lorsque vous avez trouvé le bon pour insérer verrouiller ce niveau pour l’écriture.

La solution pourrait être d’utiliser des opérations atomiques . Pas de locking, pas de changement de contexte, pas de sumil et beaucoup plus rapide que les mutex ou les variables de condition. Les opérations atomiques ne sont pas la solution finale à tout, mais nous avons créé de nombreuses versions thread-safe de structures de données communes utilisant uniquement des opérations atomiques. Ils sont très rapides.

Les opérations atomiques sont une série d’opérations simples telles que l’incrément, ou la décrémentation ou l’affectation, qui sont garanties pour une exécution atomique dans un environnement multithread. Si deux threads touchent l’op en même temps, le cpu s’assure qu’un thread l’exécute à la fois. Les opérations atomiques sont des instructions matérielles, elles sont donc rapides. “Comparer et échanger” est très utile pour les structures de données thread-safe. dans nos tests, la comparaison et l’échange swap sont à peu près aussi rapides que l’atsortingbution d’un entier 32 bits. Peut-être 2x aussi lent. Lorsque vous considérez combien de cpu est consommé avec les mutex, les opérations atomiques sont infiniment plus rapides.

Ce n’est pas sortingvial de faire des rotations pour équilibrer votre arbre avec des opérations atomiques, mais ce n’est pas impossible. J’ai déjà rencontré cette exigence dans le passé et j’ai sortingché en créant un skipliste sûr, car un skipliste peut être réalisé très facilement avec des opérations atomiques. Désolé je ne peux pas vous donner une copie de notre code … ma compagnie me virerait, mais c’est assez facile à faire vous-même.

La manière dont les opérations atomiques permettent de créer des structures de données sans locking peut être visualisée à l’aide du simple exemple de liste chaînée threadsafe. Pour append un élément à une liste liée globale (_pHead) sans utiliser de verrou. Commencez par enregistrer une copie de _pHead, pOld. Je considère ces copies comme “l’état du monde” lors de l’exécution d’opérations simultanées. Créez ensuite un nouveau noeud, pNew, et définissez son pNext sur COPY . Ensuite, utilisez atomique “comparer et échanger” pour remplacer _pHead par pNew UNIQUEMENT si pHead est toujours enfoncé. L’opération atomique ne réussira que si _pHead n’a pas changé. Si cela échoue, revenez en arrière pour obtenir une copie du nouveau _pHead et recommencez.

Si l’opération réussit, le rest du monde verra maintenant une nouvelle tête. Si un fil a reçu l’ancienne tête une nanoseconde auparavant, il ne verra pas le nouvel élément, mais la liste pourra toujours être parcourue en toute sécurité. Comme nous avons prédéfini le pNext à l’ancienne tête AVANT d’append notre nouvel élément à la liste, si un fil de discussion voit la nouvelle tête une nanoseconde après l’ajouté, la liste est sans danger pour la liste.

Truc global:

 typedef struct _TList { int data; struct _TList *pNext; } TList; TList *_pHead; 

Ajouter à la liste:

 TList *pOld, *pNew; ... // allocate/fill/whatever to make pNew ... while (1) { // concurrency loop pOld = _pHead; // copy the state of the world. We operate on the copy pNew->pNext = pOld; // chain the new node to the current head of recycled items if (CAS(&_pHead, pOld, pNew)) // switch head of recycled items to new node break; // success } 

CAS est un raccourci pour __sync_bool_compare_and_swap ou similaire. Vous voyez comme c’est facile? Pas de mutex … pas de serrures! Dans le cas rare où 2 threads atteignent ce code en même temps, on boucle simplement une seconde fois. Nous ne voyons que la deuxième boucle, car le planificateur remplace un thread par la boucle d’access simultané. c’est donc rare et sans conséquence.

Les choses peuvent être retirées de la tête d’une liste chaînée de la même manière. Vous pouvez modifier de manière atomique plusieurs valeurs si vous utilisez des unions et vous pouvez utiliser des opérations atomiques allant jusqu’à 128 bits. Nous avons testé 128 bits sur linux redhat 32 bits et ils ont la même vitesse que les ops atomiques 32, 64 bits.

Vous devrez comprendre comment utiliser ce type de technique avec votre arbre. Un nœud d’arborescence b aura deux ptr en nœuds enfants. Vous pouvez leur demander de les changer. Le problème d’équilibrage est difficile. Je peux voir comment parsingr une twig d’arbre avant d’append quelque chose et d’en faire une copie à partir d’un certain point. lorsque vous avez terminé de changer de twig, vous insérez la nouvelle dans le système. Cela poserait un problème pour les grandes succursales. Peut-être que l’équilibrage peut être fait “plus tard” lorsque les discussions ne se disputent pas l’arborescence. Peut-être que vous pouvez faire en sorte que l’arborescence soit toujours consultable même si vous n’avez pas encore cascadé la rotation … autrement dit, si le thread A ajoutait un nœud et effectuait une rotation récursive des nœuds, le thread b pouvait toujours lire ou append des nœuds. Juste quelques idées. Dans certains cas, nous créons une structure qui a des numéros de version ou des indicateurs de locking dans les 32 bits après les 32 bits de pNext. Nous utilisons alors le CAS 64 bits. Peut-être pourriez-vous sécuriser la lecture de l’arborescence à tout moment sans verrou, mais vous devrez peut-être utiliser la technique de gestion des versions sur une twig en cours de modification.

Voici quelques articles que j’ai publiés sur les avantages des opérations atomiques:

Pthreads et mutexes; partie de locking d’un tableau

Manière efficace et rapide d’argument de thread

Rechargement automatique de la configuration avec pthreads

Avantages de l’utilisation de variables de condition par rapport au mutex

manipulation de bit unique

L’allocation de mémoire sous Linux est-elle non bloquante?

Vous pouvez obtenir un Mutex équitable avec l’idée esquissée par @caf, mais en utilisant des opérations atomiques pour acquérir le ticket avant de verrouiller.

 #if defined(_MSC_VER) typedef volatile LONG Sync32_t; #define SyncFetchAndIncrement32(V) (InterlockedIncrement(V) - 1) #elif (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) > 40100 typedef volatile uint32_t Sync32_t; #define SyncFetchAndIncrement32(V) __sync_fetch_and_add(V, 1) #else #error No atomic operations #endif class FairMutex { private: Sync32_t _nextTicket; Sync32_t _curTicket; pthread_mutex_t _mutex; pthread_cond_t _cond; public: inline FairMutex() : _nextTicket(0), _curTicket(0), _mutex(PTHREAD_MUTEX_INITIALIZER), _cond(PTHREAD_COND_INITIALIZER) { } inline ~FairMutex() { pthread_cond_destroy(&_cond); pthread_mutex_destroy(&_mutex); } inline void lock() { unsigned long myTicket = SyncFetchAndIncrement32(&_nextTicket); pthread_mutex_lock(&_mutex); while (_curTicket != myTicket) { pthread_cond_wait(&_cond, &_mutex); } } inline void unlock() { _curTicket++; pthread_cond_broadcast(&_cond); pthread_mutex_unlock(&_mutex); } }; 

Plus largement, je n’appellerais pas cela une FIFO Mutex, car cela donne l’impression de maintenir une commande qui n’y figure pas au départ. Si vos threads appellent un verrou () en parallèle, ils ne peuvent pas avoir d’ordre avant d’appeler le verrou. Il est donc inutile de créer un mutex préservant une relation d’ordre qui n’y est pas.

Vous pouvez jeter un oeil à la fonction pthread_mutexattr_setprioceiling .

 int pthread_mutexattr_setprioceiling ( pthread_mutexatt_t * attr, int prioceiling, int * oldceiling ); 

De la documentation:

pthread_mutexattr_setprioceiling (3THR) définit l’atsortingbut plafond de priorité d’un object atsortingbut mutex.

attr pointe vers un object atsortingbut mutex créé par un précédent appel à pthread_mutexattr_init ().

prioceiling spécifie le plafond de priorité des mutex initialisés. Le plafond définit le niveau de priorité minimum auquel la section critique gardée par le mutex est exécutée. les prix seront dans la plage maximale de priorités définie par SCHED_FIFO. Pour éviter l’inversion des priorités, prioceiling sera défini sur une priorité supérieure ou égale à la priorité la plus élevée de tous les threads susceptibles de verrouiller le mutex concerné.

oldceiling contient l’ancienne valeur du plafond de priorité.