Question d'entretien de synchronisation multithreading: Trouver n mots donnés m fils

23

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.

rplusg
la source
L'ajout d'une balise C ++ n'aidera probablement pas beaucoup ici. Ces questions ici sont des choses plus conceptuelles qui transcendent n'importe quelle langue particulière.
cHao
Faites confiance à vos sentiments. Je comprends à quoi ils servent, mais je n'ai jamais aimé les questions d'entrevue qui s'écartent si loin de la façon dont vous devriez résoudre le problème dans le monde réel.
G_P
16
@rplusg - Je serais beaucoup plus impressionné par une personne interrogée qui a souligné que la solution sérialise le problème et ajoute simplement des frais généraux de thread sans effectuer de traitement simultané. L'intervieweur peut toujours insister pour que vous répondiez à la question telle que posée.
David Harkness
si "chaque thread doit imprimer un mot et donner le contrôle au thread suivant", cela ressemble à un travail en série, c'est-à-dire qu'un thread attend que le précédent se termine et c'est comme passer un relais. pourquoi ne pas simplement en faire une application monothread dans ce cas?
amphibient
1
je l'obtiens @Blrfl. c'est un peu comme si je devais vérifier que vous savez comment utiliser l'outil X, mais que vous étiez trop paresseux ou bâclé pour concevoir un scénario de cas d'utilisation d'application authentique qui justifie vraiment l'utilisation de cet outil, j'ai donc saisi tout ce qui était à portée de main et j'ai pigeonné mon exemple. en elle bâclée. franchement, si on me le demandait dans une interview, je l'appellerais et je ne voudrais probablement pas travailler avec quelqu'un de bâclé et de demi-bon comme ça
amphibient

Réponses:

22

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 msémaphores. Chaque thread xattend le sémaphore xpuis publie sur le sémaphore x+1après avoir fait son travail. En pseudocode:

loop:
    wait(semaphore[x])
    if no more words:
        post(semaphore[(x+1) % m])
        exit
    print word
    increment current word pointer
    post(semaphore[(x+1) % m])
Karl Bielefeldt
la source
Merci pour la générosité. Il m'a fallu un certain temps pour comprendre que le survol de la souris indiquerait qui l'a donné.
kdgregory
Excusez mon ignorance, pouvez-vous nous expliquer comment cette solution est correcte? est-ce un nouveau type de sémaphores de fantaisie? Je suis sûr cependant que la question est résolue par une solution d'attente / notification [que les sémaphores utilisent].
AJed
C'est juste un tableau de sémaphores standard. Rien de spécial à leur sujet. Notify est appelé "post" dans certaines implémentations.
Karl Bielefeldt
@KarlBielefeldt Eh bien, si chaque thread x attend le sémaphore x, alors tous les threads seront bloqués et rien ne se passera. Si wait (sem) est en fait acquis (sem) - alors ils entreront en même temps et il n'y aura pas d'exclusion. Jusqu'à ce qu'il y ait plus de clarifications, je pense qu'il y a quelque chose qui ne va pas dans ce pseudocode et ce ne devrait pas être la meilleure réponse.
AJed
Cela montre simplement la boucle pour chaque thread. Le code d'installation devrait être publié dans le premier sémaphore pour lancer les choses.
Karl Bielefeldt
23

À 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:

  • Capacité à différencier les concepts abstraits de la mise en œuvre concrète. Je jette celui-ci principalement comme un méta-commentaire sur certains des commentaires. Non, cela n'a aucun sens de traiter une seule liste de mots de cette façon. Cependant, le concept abstrait d'un pipeline d'opérations, qui peut s'étendre sur plusieurs machines de capacités différentes, est important.
  • D'après mon expérience (près de 30 ans d'applications distribuées, multi-processus et multi-thread), la distribution du travail n'est pas la partie difficile. La collecte des résultats et la coordination des processus indépendants sont les domaines où la plupart des bogues de thread se produisent (encore une fois, selon mon expérience). En distillant le problème jusqu'à une chaîne simple, l'intervieweur peut voir dans quelle mesure le candidat pense à la coordination. De plus, l'intervieweur a la possibilité de poser toutes sortes de questions complémentaires, telles que «OK, que se passe-t-il si chaque thread doit envoyer sa parole à un autre thread pour la reconstruction».
  • Le candidat pense-t-il à la façon dont le modèle de mémoire du processeur pourrait affecter la mise en œuvre? Si les résultats d'une opération ne sont jamais vidés du cache L1, c'est un bogue même s'il n'y a aucune concurrence apparente.
  • Le candidat sépare-t-il le filetage de la logique d'application?

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:

  • Le code d'application est responsable de la lecture d'une file d'attente, de la modification des données et de l'écriture de la file d'attente. Peu importe si elle est multithread ou non, ou si la file d'attente est une file d'attente en mémoire sur une machine ou une file d'attente basée sur TCP entre des machines qui vivent sur des côtés opposés du monde.
  • Parce que le code d'application est écrit comme un seul thread, il peut être testé de manière déterministe sans avoir besoin de beaucoup d'échafaudage.
  • Pendant sa phase d'exécution, le code d'application possède la chaîne en cours de traitement. Il n'a pas à se soucier de la synchronisation avec les threads exécutés simultanément.

Cela dit, il y a encore beaucoup de zones grises qu'un enquêteur compétent peut sonder:

  • "D'accord, mais nous cherchons à connaître votre connaissance des primitives de concurrence. Pouvez-vous implémenter une file d'attente de blocage?" Votre première réponse, bien sûr, devrait être que vous utilisiez une file d'attente de blocage prédéfinie à partir de la plate-forme de votre choix. Cependant, si vous comprenez les threads, vous pouvez créer une implémentation de file d'attente dans moins d'une douzaine de lignes de code, en utilisant les primitives de synchronisation prises en charge par votre plateforme.
  • "Et si une étape du processus prend très longtemps?" Vous devez vous demander si vous souhaitez une file d'attente de sortie limitée ou illimitée, comment vous pouvez gérer les erreurs et les effets sur le débit global en cas de retard.
  • Comment mettre efficacement en file d'attente la chaîne source. Ce n'est pas nécessairement un problème si vous avez affaire à des files d'attente en mémoire, mais cela pourrait être un problème si vous passez d'une machine à l'autre. Vous pouvez également explorer des wrappers en lecture seule au-dessus d'un tableau d'octets immuable sous-jacent.

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.

kdgregory
la source
Toute cette note sur le cache L1 du processeur m'a vraiment intrigué. A voté.
Marc DiMillo
J'ai récemment utilisé projectReactor avec Spring 5. Ce qui me permet d'écrire du code agnostique pour les threads.
kundan bora
16

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).

"Essayez juste de répondre, et sortez de là ..."

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.

Demian Brecht
la source
3
J'ai rétrogradé cette réponse (même si elle a inexplicablement obtenu 4 votes positifs), car elle ne répond pas à la question qui a été posée.
Robert Harvey
1
@RobertHarvey: Parfois, les gens posent les mauvaises questions . Le PO a un mauvais état d'esprit pour aborder les entretiens techniques et cette réponse était une tentative pour l'aider à se mettre sur la bonne voie.
Demian Brecht
1
@RobertHarvey Je crois honnêtement que c'est la bonne réponse à la question. Le mot-clé ici est "question d'entretien" qui est mentionnée dans le titre et dans le corps de la question. Pour une telle question, c'est la bonne réponse. Si la question était seulement "J'ai m fils et un paragraphe de n mots, et je veux faire ceci et cela avec eux, quelle est la meilleure approche", alors oui, cette réponse n'aurait pas été appropriée pour la question. En l'état, je pense que c'est génial. Paraphrase: j'ai bombardé pas mal de questions d'entrevue parce que je n'ai pas suivi les conseils donnés ici
Shivan Dragon
@RobertHarvey, il répond à une question connexe, le vote négatif n'a rien accompli.
Marc DiMillo
0
  • 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.

java_mouse
la source
0

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:

while(true)
{
    lock(index)
    {
        if(index >= array.length())
          break;
        Console.WriteLine(array[index]);
        index++;
    }
}

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.

ConditionRacer
la source
-1

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.

#include <iostream>
#include <fstream>
#include <pthread.h>
#include <signal.h>
pthread_cond_t cond[5] = {PTHREAD_COND_INITIALIZER,};
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

using namespace std;

string gstr;

void* thread1(void*)
{
    do {
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[0],&mutex);
    cout <<"thread1 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread2(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[1],&mutex);
    cout <<"thread2 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread3(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[2],&mutex);
    cout <<"thread3 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread4(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[3],&mutex);
    cout <<"thread4 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread5(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[4],&mutex);
    cout <<"thread5 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

int main()
{
    pthread_t t[5];
    void* (*fun[5])(void*);
    fun[0]=thread1;
    fun[1]=thread2;
    fun[2]=thread3;
    fun[3]=thread4;
    fun[4]=thread5;

    for (int i =0 ; i < 5; ++i)
    {
        pthread_create(&t[i],NULL,fun[i],NULL);
    }
    ifstream in;
    in.open("paragraph.txt");
    int i=0;
    while(in >> gstr)
    {

        pthread_cond_signal(&cond[i++]);
        if(i == 5)
            i=0;
        usleep(10);
    }
    for (int i =0 ; i < 5; ++i)
    {
        int ret = pthread_cancel(t[i]);
        if(ret != 0)
            perror("pthread_cancel:");
        else
            cout <<"canceled\n";
    }
    pthread_exit(NULL);
}
shashank
la source
-1

[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:

node = get_thread_specific_data(node_key);
lock(mutex);
    if(!owned)
    {
        owned = true;
        owner = self;
        return success;
    }

    node->next = nullptr;
    if(waiters_queue == null) waiters_queue = node;
    else waiters_last->next = node;

    waiters_last = node;
unlock(mutex);
sem_wait(node->semaphore);

lock(mutex);
    if(owned != -1) abort();
    owned = true;
    owner = self;
    waiters_queue = waiters_queue->next;
 unlock(mutex);

opération de déverrouillage:

lock(mutex);
    owner = null;
    if(waiters_queue == null)
    {
        owned = false;
        return success;
    }
    owned = -1;
    sem_post(waiters_queue->semaphore);
unlock(mutex);
user2615724
la source
-1

Question interessante. Voici ma solution en Java utilisant SynchronousQueue pour créer un canal de rendez-vous entre les threads:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.SynchronousQueue;

public class FindNWordsGivenMThreads {

    private static final int NUMBER_OF_WORDS = 100;
    private static final int NUMBER_OF_THREADS = 5;
    private static final Stack<String> POISON_PILL = new Stack<String>();

    public static void main(String[] args) throws Exception {
        new FindNWordsGivenMThreads().run();
    }

    private void run() throws Exception {
        final Stack<String> words = loadWords();
        SynchronousQueue<Stack<String>> init = new SynchronousQueue<Stack<String>>();
        createProcessors(init);
        init.put(words);
    }

    private void createProcessors(SynchronousQueue<Stack<String>> init) {
        List<Processor> processors = new ArrayList<Processor>();

        for (int i = 0; i < NUMBER_OF_THREADS; i++) {

            SynchronousQueue in;
            SynchronousQueue out;

            if (i == 0) {
                in = init;
            } else {
                in = processors.get(i - 1).getOut();
            }

            if (i == (NUMBER_OF_THREADS - 1)) {
                out = init;
            } else {
                out = new SynchronousQueue();
            }

            Processor processor = new Processor("Thread-" + i, in, out);
            processors.add(processor);
            processor.start();

        }

    }

    class Processor extends Thread {

        private SynchronousQueue<Stack<String>> in;
        private SynchronousQueue<Stack<String>> out;

        Processor(String name, SynchronousQueue in, SynchronousQueue out) {
            super(name);
            this.in = in;
            this.out = out;
        }

        @Override
        public void run() {

            while (true) {

                Stack<String> stack = null;
                try {
                    stack = in.take();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                if (stack.empty() || stack == POISON_PILL) {
                    System.out.println(Thread.currentThread().getName() + " Done!");
                    out.offer(POISON_PILL);
                    break;
                }

                System.out.println(Thread.currentThread().getName() + " " + stack.pop());
                out.offer(stack);
            }
        }

        public SynchronousQueue getOut() {
            return out;
        }
    }

    private Stack<String> loadWords() throws Exception {

        Stack<String> words = new Stack<String>();

        BufferedReader reader = new BufferedReader(new FileReader(new File("/usr/share/dict/words")));
        String line;
        while ((line = reader.readLine()) != null) {
            words.push(line);
            if (words.size() == NUMBER_OF_WORDS) {
                break;
            }
        }
        return words;
    }
}
Sid
la source
-2

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.

gnasher729
la source