Existe-t-il un moyen pour que ce problème puisse bénéficier d'une solution avec plusieurs threads plutôt qu'un seul thread?
Dans une interview, on m'a demandé de résoudre un problème en utilisant plusieurs threads. Il me semble que les multiples threads ne présentent aucun avantage.
Voici le problème:
On vous donne un paragraphe, qui contient n nombre de mots, on vous donne m fils. Ce que vous devez faire, c'est que chaque thread doit imprimer un mot et donner le contrôle au thread suivant, de cette façon, chaque thread continuera à imprimer un mot, au cas où le dernier thread arriverait, il devrait invoquer le premier thread. L'impression se répétera jusqu'à ce que tous les mots soient imprimés dans le paragraphe. Enfin, tous les threads devraient se terminer correctement. Quel type de synchronisation utilisera?
Je pense fermement que nous ne pouvons pas tirer parti des discussions ici, mais je crois que l'intervieweur essaie de mesurer mes compétences en synchronisation. Suis-je en train de manquer quelque chose dans ce problème qui donnerait de la valeur à plusieurs threads?
Pas besoin de code, mettez juste quelques réflexions. Je mettrai en œuvre par moi-même.
Réponses:
Il me semble qu'ils vous conduisent vers une solution de sémaphore. Les sémaphores sont utilisés pour signaler à un autre thread que c'est leur tour. Ils sont utilisés beaucoup moins fréquemment que les mutex, ce qui explique pourquoi je pense que c'est une bonne question d'entrevue. C'est aussi pourquoi l'exemple semble artificiel.
Fondamentalement, vous créez des
m
sémaphores. Chaque threadx
attend le sémaphorex
puis publie sur le sémaphorex+1
après avoir fait son travail. En pseudocode:la source
À mon avis, il s'agit d'une fabuleuse question d'entrevue - du moins en supposant (1) que le candidat devrait avoir une connaissance approfondie du filetage, et (2) l'intervieweur possède également une connaissance approfondie et utilise la question pour sonder le candidat. Il est toujours possible que l'intervieweur recherchait une réponse précise et étroite, mais un intervieweur compétent devrait rechercher les éléments suivants:
Ce dernier point est, à mon avis, le plus important. Encore une fois, d'après mon expérience, il devient exponentiellement plus difficile de déboguer du code threadé si le threading est mélangé avec la logique d'application (regardez juste toutes les questions Swing sur SO pour des exemples). Je crois que le meilleur code multithread est écrit en tant que code monothread autonome, avec des transferts clairement définis.
Dans cet esprit, mon approche serait de donner à chaque thread deux files d'attente: une pour l'entrée, une pour la sortie. Le thread se bloque lors de la lecture de la file d'attente d'entrée, prend le premier mot de la chaîne et transmet le reste de la chaîne à sa file d'attente de sortie. Certaines des caractéristiques de cette approche:
Cela dit, il y a encore beaucoup de zones grises qu'un enquêteur compétent peut sonder:
Enfin, si vous avez de l'expérience en programmation concurrente, vous pourriez parler de certains cadres (par exemple, Akka pour Java / Scala) qui suivent déjà ce modèle.
la source
Les questions d'entrevue sont parfois en fait des questions pièges, destinées à vous faire réfléchir au problème que vous essayez de résoudre. Poser des questions sur une question fait partie intégrante de l'approche de tout problème, que ce soit dans le monde réel ou lors d'un entretien. Il existe un certain nombre de vidéos circulant sur Internet sur la façon d'aborder les questions dans les entretiens techniques (recherchez en particulier Google et peut-être Microsoft).
Approcher les entretiens avec ce schéma de pensée vous conduira à bombarder n'importe quel entretien pour toute entreprise qui vaut la peine de travailler.
Si vous ne pensez pas que vous gagnez beaucoup (si quelque chose de filetage), dites-le-leur. Dites-leur pourquoi vous pensez qu'il n'y a aucun avantage. Discutez avec eux. Les entretiens techniques sont censés être une plateforme de discussion ouverte. Vous pourriez finir par apprendre quelque chose sur la façon dont cela peut être utile. Ne vous contentez pas d'aller de l'avant aveuglément en essayant de mettre en œuvre quelque chose que votre intervieweur vous a dit de faire.
la source
Commencez par symboliser le paragraphe avec les délimiteurs appropriés et ajoutez les mots à une file d'attente.
Créez N nombre de threads et conservez-le dans un pool de threads.
Parcourez le pool de threads et démarrez le thread et attendez
qu'il se joigne. Et commencez le fil suivant une fois le premier fil terminé et ainsi de suite.
Chaque thread doit simplement interroger la file d'attente et l'imprimer.
Une fois que tous les threads sont utilisés dans le pool de threads, commencez par le début du pool.
la source
Comme vous l'avez dit, je ne pense pas que ce scénario profite grandement, voire pas du tout, du threading. C'est probablement plus lent qu'une implémentation à un seul thread.
Cependant, ma réponse serait d'avoir chaque thread dans une boucle serrée essayant d'accéder à un verrou qui contrôle l'accès à l'index du tableau de mots. Chaque thread saisit le verrou, obtient l'index, obtient le mot correspondant du tableau, l'imprime, incrémente l'index puis libère le verrou. Les threads se terminent lorsque l'index se trouve à la fin du tableau.
Quelque chose comme ça:
Je pense que cela devrait atteindre l'un thread après une autre exigence, mais l'ordre des threads n'est pas garanti. Je suis curieux d'entendre d'autres solutions également.
la source
Utilisez les API de condition d'attente / signal pour résoudre ce problème.
Disons que le premier thread choisit 1 mot et que pendant ce temps, tous les threads attendent un signal. Le 1er fil imprime le 1er mot et génère le signal vers le fil suivant, puis le 2e fil imprime le deuxième mot et génère le signal vers le 3e fil et ainsi de suite.
la source
[Les termes utilisés ici peuvent être spécifiques aux threads POSIX]
Il devrait également être possible d'utiliser un mutex FIFO pour résoudre ce problème.
Où utiliser:
Supposons que deux threads T1 et T2 tentent d'exécuter une section critique. Les deux n'ont pas grand-chose à faire en dehors de cette section critique et maintiennent les verrous pendant une bonne période. Ainsi, T1 peut verrouiller, exécuter et déverrouiller et signaler T2 pour le réveil. Mais avant que T2 ne puisse se réveiller et acquérir le verrou, T1 réacquiert le verrou et l'exécute. De cette façon, T2 peut devoir attendre très longtemps avant d'obtenir le verrou ou ne pas l'être.
Comment ça marche / Comment mettre en œuvre:
Ayez un mutex à verrouiller. Initialisez les données spécifiques au thread (TSD) pour chaque thread vers un nœud contenant l'ID de thread et le sémaphore. En outre, ont deux variables - appartenant (TRUE ou FALSE ou -1), propriétaire (id de thread propriétaire). En outre, conservez une file d'attente de serveurs et un pointeur waiterLast pointant vers le dernier nœud de la file d'attente des serveurs.
opération de verrouillage:
opération de déverrouillage:
la source
Question interessante. Voici ma solution en Java utilisant SynchronousQueue pour créer un canal de rendez-vous entre les threads:
la source
Je dirais que ce genre de question est très difficile à répondre, car il demande la meilleure façon de faire quelque chose de complètement stupide. Mon cerveau ne fonctionne tout simplement pas de cette façon. Il ne peut pas trouver de solutions à des questions stupides. Mon cerveau dirait immédiatement que dans ces conditions, l'utilisation de plusieurs threads est inutile, donc j'utiliserais un seul thread.
Je leur demanderais alors soit de poser une question réelle sur le filetage, soit de me laisser donner un exemple concret de filetage sérieux.
la source