8
votes

Comment faire de la synchronisation de fil sans utiliser Mutex, Semorphore, Spinlock et Fuex?

Ceci est une question d'entrevue, l'entretien a été fait.

Comment faire de la synchronisation de fil sans utiliser mutex, Semorphore, Spinlock et Futex?

donné 5 threads, comment faire 4 d'entre eux attendre un signal du fil de gauche au même point? cela signifie que lorsque tous les filets (1,2,3,4) exécutent à un point de leur fonction de thread, ils arrêtent et attendent Signal de thread 5 Envoyez un signal sinon ils ne procéderont pas.

mon idée:

Utilisez la variable globale de Bool comme drapeau, si le thread 5 ne le définit pas vrai, tous les autres threads attendent à un point et définissent également leur Drapeau variable true. Après le thread 5, les variables de drapeau de toutes les threads sont vraies, il le définira Flag Var True.

C'est une attente occupée.

Des idées meilleures?

merci xxx

linux c++ multithreading mutex pthreads

2 commentaires

Votre temps (! GlobalFlag) est l'équivalent d'une serrure de spin. Mais j'ai bien peur de ne pas comprendre la question. Si vous utilisez un signal, ce que je ferais, vous utilisez toujours une forme de sémaphore ou de mutex (bien que caché par le système.) Sans attente sur un signal, vous auriez un spinlock. L'utilisation de GlobalFlag est bonne si vous pouvez faire du travail en attendant et passer à une tâche différente (ou une tâche supplémentaire) une fois que le drapeau est vrai.

En plus de ce que vous avez ici, vous devrez probablement déclarer GlobalFlag comme volatile pour vous assurer que le compilateur lit en réalité la mémoire plutôt que de regarder le code et de décider qu'il ne peut pas changer de valeur. Et utilisez une sorte de barrière de mémoire pour vous assurer que les valeurs écrites par un thread sont visibles dans une autre,

4 Réponses :

5
votes

Commencez par une liste liée à vide des threads d'attente. La tête doit être réglée sur 0.

Utiliser CAS, comparer et échanger, insérer un fil à la tête de la liste des serveurs. Si la tête = -1, alors ne pas insérer ni attendre. Vous pouvez utiliser en toute sécurité CAS pour insérer des éléments à la tête d'une liste liée si vous le faites correctement. P>

Après avoir été inséré, le fil d'attente devrait attendre sur SIGUSR1. Utilisez SIGWAIT () pour le faire. P>

Lorsqu'il est prêt, le thread de signalisation utilise CAS pour définir la tête de la liste d'attente à -1. Cela empêche plus de threads de s'ajouter à la liste d'attente. Ensuite, le fil de signalisation iTère les threads de la liste d'attente et appelle pthread_kill (& thread, sigusr1) pour réveiller chaque fil d'attente. P>

Si SIGUSR1 est envoyé avant un appel à SIGWAIT, SIGWAIT reviendra immédiatement. Ainsi, il n'y aura pas de race entre ajouter un fil à la liste d'attente et appeler Sigwait. P>

EDIT: P>

Pourquoi CAS est-il plus rapide qu'un mutex? La réponse de Laymen (je suis un laïc). Son plus rapide pour certaines choses dans certaines situations, car il a une surcharge inférieure quand il n'y a pas de race. Donc, si vous pouvez réduire votre problème simultané pour avoir besoin de changer 8-16-32-64-128 bits de mémoire contiguë et une race ne va pas arriver très souvent, CAS WINS. CAS est fondamentalement une instruction MOV légèrement plus fantaisie / coûteuse où vous alliez faire un "MOV" régulier de toute façon. C'est un "serrure" ou quelque chose comme ça. P>

Un mutex d'autre part est un tas de choses supplémentaires, qui obtiennent d'autres lignes de cache sale et utilise plus de barrières de mémoire, etc. Bien que CAS agisse comme une barrière de mémoire sur le X86, X64, etc. Ensuite, bien sûr, vous devez déverrouiller le mutex qui est probablement à peu près la même quantité de choses supplémentaires. p>

Voici comment vous ajoutez un élément à une liste liée à l'aide de CAS: P>

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; 
}

9 commentaires

Merci, cette synchronisation a une surcharge inférieure à celle de Mutex / Feux / Semaphore?

J'ai expliqué il y a environ 1 à 2 ans, alors ma mémoire s'estompe. Nous avons expressément essayé de voir à quelle vitesse nous pourrions dormir et réveiller les fils individuels. Cette méthode semblait être d'environ 10 fois (ou était-elle 40X?) Plus rapidement que les mutiles et les variables de condition. Nous avons comparé cette méthode à l'aide d'une variable mutex / condition individuelle pour chaque thread. Je n'ai jamais posté mon test ici pour le voir, il était imparfait ou non ... Nous n'avons pas testé les futurs ou les sémaphores.

Souhaitez-vous s'il vous plaît expliquer très brièvement pourquoi les CAS sont plus rapides que MuTex? Cela fonctionne comme Futex (aucun appel SYS si aucun argument de verrouillage?)? Merci!

@ user1000107: Si vous êtes intéressé par la performance des serrures, voir l'article d'Intel ici: logiciel.intel.com/en-us/articles/...

@Nécrolis, l'article est intéressant, Intel a-t-il des choses similaires sur Linux? Merci !

Le commentaire de Jannb ci-dessous vous donne un peu plus d'informations sur la configuration des masques de signal pour les threads avant de les créer.

@ user1000107: En fait, je n'ai pas beaucoup connu pour Linux, probablement parce que je les endroits que j'ai l'air est orienté Windows. Toutefois, les verrous en mode utilisateur décrit dans cet article sont les meilleurs que vous obtiendrez sous un système d'exploitation

Pouvez-vous me donner plus de détails pour CAS?

Woops désolé. CAS est ma macro. Si vous utilisez Linux, CAS = macro utilisant __sync_bool_compare_and_swap. Voir GCC Atomic Countrines. Si vous utilisez Windows, CAS = macro en utilisant quelque chose comme InterlockedCompeExchange.

1
votes

Choisissez un signal à utiliser, dites SIGUSR1.
Utilisez pthread_sigmask pour bloquer SIGUSR1.
Créez les threads (ils héritent du masque de signal, donc 1 doit être fait en premier!)
threads 1-4 Appelez SIGWAIT, blocage jusqu'à la réception de SIGUSR1.
thread 5 appels tue () ou pthread_kill 4 fois avec SIGUSR1. Puisque POSIX Spécifie que les signaux seront livrés à un fil qui ne bloque pas le signal, il sera livré à l'une des threads en attente dans SIGWAIT (). Il n'est donc pas nécessaire de garder une trace dont les threads ont déjà reçu le signal et qui ne l'ont pas fait, avec la synchronisation associée.

5 commentaires

Merci, il semble que Pthread_sigmask est un appel système et cette synchronisation a une surcharge inférieure à celle de MuTex / FUEX / SEMAPHORE?

@ user1000107: Non, je ne le pense pas. Les futex non compris ne nécessitent pas de syscall et doivent être aussi rapides que quelques instructions de synchronisation de la CPU (CAS, barrières, etc.), il est donc difficile de battre cela pour un mécanisme de synchronisation à usage général.

pthread_sigmask a quelques avantages sur le mutex, le sémaphore? Merci !

@ user1000107, les signaux sont généralement pires que les mutiles ou les sémaphores. Ils ont tendance à être plus lents et plus complexes à utiliser. Mais comme vous avez dit que vous ne pouvez pas utiliser des mutiles ou des sémaphores, ce sont une option.

@bdonlan, pourquoi les signaux sont plus lents que le mutex ou le sémaphore? Ils ont besoin de plus d'appels système? Quelles autres moyens peuvent être utilisés pour la synchronisation plus rapidement que le mutex ou le sémaphore? futex? ou sinon ? Merci !

1
votes

Vous pouvez le faire en utilisant et et MWAIT MWAIT , disponible via le _mm_mwait et _mm_monitor intrinsique, Intel a un article sur celui-ci ici . (Il existe également un brevet d'utilisation de Memory-Monitor-Wait pour Lock Contention ici qui peut être de intérêt).



                                                                    
                                    
                                    
                                        5 commentaires
                                        
                                                                                            
                                                    Ceci est une fonctionnalité NIFTY. Un jour je le sais ou quelque chose de similaire sera utile. Merci!                                                
                                                
                                                                                            
                                                    @Nécrolis, ces instructions sont pour Windows, que si Linux / UNIX?                                                
                                                
                                                                                            
                                                    @ user1000107: Ces instructions sont destinées à  X86 et SSE3 , elles n'ont rien à voir avec Windows, je viens de choisir d'utiliser les documents MSDN pour les intrinsèques disponibles dans MSVC, ils doivent être les mêmes en vertu de la CPI (qui Fonctionne sous Linux & OSX)                                                

                                                
                                                                                            
                                                    @Necrolis, SSE3 est plus rapide que le mutex, le sémaphore ou le futex? Si non, quel est ses avantages? Il n'a aucun appel système en cas de non-convention? Merci !                                                
                                                
                                                                                            
                                                    @ user1000107: Je n'ai aucune idée de la performance (les listes de Agner FOG peuvent avoir des informations sur cela), cependant,  MWAIT  fournit généralement des économies d'alimentation.  Monitor  &  MWAIT  sont des instructions, il n'y a pas d'appel du tout pour les utiliser.

1 votes Je pense que vous cherchez le algorithme de Peterson ou Algorithme de Dekker Ils ont synchronisé les threads uniquement basés sur la mémoire partagée 0 commentaires

Articles qui pourrait vous intéresser : Délai d'expiration d'un script bash lorsqu'il n'y a pas de sortie pendant un certain temps Convertir des images Webp en PNG par la commande Linux Comment mettre à jour la dernière version de minikube? Est-il possible de désactiver le délai d'expiration sudo dans le shell actuel?