Comment faire la synchronisation des threads sans utiliser mutex, semorphore, spinLock et futex?

Ceci est une question d’entretien, l’interview a été faite.

Comment faire la synchronisation des threads sans utiliser mutex, semorphore, spinLock et futex?

Étant donné 5 threads, comment faire 4 d’entre eux attendre un signal du thread gauche au même point? cela signifie que lorsque tous les threads (1,2,3,4) s’exécutent à un moment donné de leur fonction thread, ils s’arrêtent et attendent que le signal du thread 5 envoie un signal, sinon ils ne continueront pas.

Mon idée:

Utilisez la variable bool globale en tant qu’indicateur, si le thread 5 ne le définit pas comme vrai, tous les autres threads attendent à un moment donné et définissent également leur variable flag. Une fois que le thread 5 a trouvé que les variables de l’indicateur de tous les threads sont vraies, il lui affectera le drapeau var true.

C’est une attente occupée.

De meilleures idées?

Merci

the pseudo code: bool globalflag = false; bool a[10] = {false} ; int main() { for (int i = 0 ; i < 10; i++) pthread_create( threadfunc, i ) ; while(1) { bool b = true; for (int i = 0 ; i < 10 ; i++) { b = a[i] & b ; } if (b) break; } } void threadfunc(i) { a[i] = true; while(!globalflag); } 

Commencez par une liste vide de liens en attente. La tête devrait être mise à 0.

Utilisez CAS, compare et swap, pour insérer un thread en tête de la liste des serveurs. Si la tête = -1, ne pas insérer ou attendre. Vous pouvez utiliser CAS en toute sécurité pour insérer des éléments en tête d’une liste chaînée si vous le faites correctement.

Après avoir été inséré, le thread en attente doit attendre sur SIGUSR1. Utilisez sigwait () pour cela.

Lorsque vous êtes prêt, le thread de signalisation utilise CAS pour définir la tête de la liste d’attente sur -1. Cela évite que d’autres threads ne s’ajoutent à la liste d’attente. Ensuite, le thread de signalisation itère les threads dans la liste d’attente et appelle pthread_kill (& thread, SIGUSR1) pour réveiller chaque thread en attente.

Si SIGUSR1 est envoyé avant un appel à sigwait, sigwait reviendra immédiatement. Ainsi, il n’y aura pas de course entre l’ajout d’un thread à la liste d’attente et l’appel à sigwait.

MODIFIER:

Pourquoi CAS est-il plus rapide qu’un mutex? La réponse des laïcs (je suis un profane). C’est plus rapide pour certaines choses dans certaines situations, car il y a moins de frais généraux quand il n’y a pas de course. Donc, si vous parvenez à réduire votre problème simultané à la nécessité de changer les 8-16-32-64-128 bits de mémoire contiguë, et qu’une course ne se produira pas très souvent, CAS gagnera. CAS est fondamentalement une instruction mov un peu plus sophistiquée / chère là où vous alliez faire un “mov” de toute façon. C’est un “verrou” ou quelque chose comme ça.

Par contre, un mutex est un tas de choses supplémentaires, qui amoindrissent les autres lignes de cache et utilisent plus de barrières de mémoire, etc. Bien que CAS agisse comme une barrière de mémoire sur le x86, x64, etc. le mutex qui est probablement à peu près la même quantité de choses supplémentaires.

Voici comment append un élément à une liste chaînée à l’aide de CAS:

 while (1) { pOldHead = pHead; <-- snapshot of the world. Start of the race. pItem->pNext = pHead; if (CAS(&pHead, pOldHead, pItem)) <-- end of the race if phead still is pOldHead break; // success } 

Alors, à quelle fréquence pensez-vous que votre code aura plusieurs threads sur cette ligne CAS exactement au même moment? En réalité .... pas très souvent. Nous avons fait des tests en boucle en ajoutant des millions d'éléments avec plusieurs threads en même temps et cela se produit bien moins de 1% du temps. Dans un vrai programme, cela pourrait ne jamais arriver.

Évidemment, s'il y a une course, vous devez revenir en arrière et refaire cette boucle, mais dans le cas d'une liste chaînée, qu'est-ce que cela vous coûte?

L'inconvénient est que vous ne pouvez pas faire des choses très complexes à cette liste si vous utilisez cette méthode pour append des éléments à la tête. Essayez d'implémenter une double liste de liens. Quelle douleur.

MODIFIER:

Dans le code ci-dessus, j'utilise une macro CAS. Si vous utilisez linux, CAS = macro en utilisant __sync_bool_compare_and_swap. Voir gn atomic builtins . Si vous utilisez Windows, CAS = macro en utilisant quelque chose comme InterlockedCompareExchange. Voici à quoi pourrait ressembler une fonction inline dans windows:

 inline bool CAS(volatile WORD* p, const WORD nOld, const WORD nNew) { return InterlockedCompareExchange16((short*)p, nNew, nOld) == nOld; } inline bool CAS(volatile DWORD* p, const DWORD nOld, const DWORD nNew) { return InterlockedCompareExchange((long*)p, nNew, nOld) == nOld; } inline bool CAS(volatile QWORD* p, const QWORD nOld, const QWORD nNew) { return InterlockedCompareExchange64((LONGLONG*)p, nNew, nOld) == nOld; } inline bool CAS(void*volatile* p, const void* pOld, const void* pNew) { return InterlockedCompareExchangePointer(p, (PVOID)pNew, (PVOID)pOld) == pOld; } 
  1. Choisissez un signal à utiliser, par exemple SIGUSR1.
  2. Utilisez pthread_sigmask pour bloquer SIGUSR1.
  3. Créez les threads (ils héritent du masque de signal, donc 1 doit être fait en premier!)
  4. Les threads 1-4 appellent sigwait, bloquant jusqu’à la réception de SIGUSR1.
  5. Thread 5 appelle kill () ou pthread_kill 4 fois avec SIGUSR1. Étant donné que POSIX spécifie que les signaux seront livrés à un thread qui ne bloque pas le signal, il sera transmis à l’un des threads en attente dans sigwait (). Il n’est donc pas nécessaire de garder une trace des threads qui ont déjà reçu le signal et ceux qui ne l’ont pas été, avec la synchronisation associée.

Vous pouvez le faire en utilisant les instructions MONITOR et MWAIT de SSE3, disponibles via les insortingnsèques _mm_mwait et _mm_monitor . Intel a un article ici . (il existe également un brevet d’utilisation de memory-monitor-wait pour contention de verrou qui peut être intéressant).

Je pense que vous regardez l’ algorithme de Peterson ou l’algorithme de Dekker

Ils ont synchronisé les threads uniquement en fonction de la mémoire partagée