Domanda dell'intervista sulla sincronizzazione multithreading: trova n parole date m thread

A me sembra che ti stiano conducendo verso una soluzione di semaforo. I semafori sono usati per segnalare un altro thread che è il loro turno. Sono usati molto meno frequentemente rispetto ai mutex, il che credo sia il motivo per cui pensano che sia una buona domanda di intervista. È anche il motivo per cui l'esempio sembra forzato.

Fondamentalmente, creeresti m semaphores. Ogni thread x attende il semaforo x quindi i post al semaforo x+1 dopo aver eseguito la sua azione. In 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])

Secondo me, questa è una favolosa domanda di intervista - almeno ipotizzando (1) che il candidato abbia una profonda conoscenza del threading e (2) l'intervistatore abbia anche una profonda conoscenza e stia usando la domanda per sondare il candidato. È sempre possibile che l'intervistatore cercasse una risposta specifica e ristretta, ma un intervistatore competente dovrebbe cercare quanto segue:

• Capacità di differenziare i concetti astratti dall'implementazione concreta. Lo lancio principalmente come meta-commento su alcuni dei commenti. No, non ha senso elaborare un unico elenco di parole in questo modo. Tuttavia, il concetto astratto di una pipeline di operazioni, che può estendersi su più macchine con capacità diverse, è importante.
• Nella mia esperienza (circa 30 anni di applicazioni distribuite, multi-processo e multi-thread), la distribuzione del lavoro non è la parte difficile. Raccogliere i risultati e coordinare processi indipendenti sono i punti in cui si verificano la maggior parte dei bug (ancora una volta, nella mia esperienza). Distillando il problema in una catena semplice, l'intervistatore può vedere quanto il candidato pensa bene sul coordinamento. Inoltre, l'intervistatore ha l'opportunità di porre ogni sorta di domande successive, come "OK, e se ogni thread deve inviare la sua parola ad un altro thread per la ricostruzione."
• Il candidato pensa a come il modello di memoria del processore potrebbe influenzare l'implementazione? Se i risultati di una operazione non vengono mai svuotati dalla cache L1, si tratta di un bug anche se non c'è concorrenza apparente.
• Il candidato separa il threading dalla logica dell'applicazione?

Quest'ultimo punto è, a mio parere, il più importante. Di nuovo, in base alla mia esperienza, diventa esponenzialmente più difficile eseguire il debug del codice threadato se il threading è combinato con la logica dell'applicazione (basta guardare tutte le domande Swing su SO per gli esempi). Credo che il miglior codice multi-threaded sia scritto come codice single-threaded autonomo, con handoff definiti chiaramente.

Con questo in mente, il mio approccio sarebbe quello di dare a ogni thread due code: una per l'input, una per l'output. Il thread si blocca durante la lettura della coda di input, prende la prima parola fuori dalla stringa e passa il resto della stringa alla coda di output. Alcune delle caratteristiche di questo approccio:

• Il codice dell'applicazione è responsabile della lettura di una coda, dell'elaborazione di dati e della scrittura della coda. Non importa se è multi-thread o no, o se la coda è una coda in memoria su una macchina o una coda basata su TCP tra macchine che vivono su lati opposti del mondo.
• Poiché il codice dell'applicazione è scritto come se fosse single-thread, è testabile in modo deterministico senza la necessità di un sacco di scaffolding.
• Durante la sua fase di esecuzione, il codice dell'applicazione possiede la stringa in fase di elaborazione. Non deve preoccuparsi della sincronizzazione con i thread in esecuzione simultanea.

Detto questo, ci sono ancora molte aree grigie che un intervistatore competente può sondare:

• "OK, ma stiamo cercando di vedere le tue conoscenze sulle primitive della concorrenza, puoi implementare una coda di blocco?" La tua prima risposta, ovviamente, dovrebbe essere quella di utilizzare una coda di blocco pre-costruita dalla tua piattaforma preferita. Tuttavia, se si capiscono i thread, è possibile creare un'implementazione di coda in meno di una dozzina di righe di codice, utilizzando qualsiasi primitiva di sincronizzazione supportata dalla piattaforma.
• "Che cosa succede se un passaggio nel processo richiede molto tempo?" Dovresti pensare se vuoi una coda di output limitata o illimitata, come potresti gestire gli errori e gli effetti sul throughput complessivo se hai un ritardo.
• Come accodare in modo efficiente la stringa di origine. Non è necessariamente un problema se si ha a che fare con code in memoria, ma potrebbe esserci un problema se ci si sposta tra le macchine. Potresti anche esplorare wrapper di sola lettura sopra un array di byte immutabile sottostante.

Infine, se hai esperienza nella programmazione concorrente, potresti parlare di alcuni framework (ad esempio, Akka per Java / Scala) che già seguono questo modello.

A volte le domande di intervista sono in realtà domande a sorpresa, intese a farti pensare sul problema che stai cercando di risolvere. Fare domande su una domanda è una parte integrale di approccio a qualsiasi problema, sia nel mondo reale sia in un'intervista. Ci sono un certo numero di video che circolano su internet come affrontare le domande nelle interviste tecniche (guarda in particolare Google e forse Microsoft).

"Just try to answer, and get the hell out of there.."

Avvicinarsi alle interviste con questo schema di pensiero ti porterà a bombardare qualsiasi intervista per qualsiasi azienda per cui valga la pena di lavorare.

Se non pensi di guadagnare molto (se non altro dal threading), diglielo. Ditegli perché non pensate che ci sia alcun beneficio. Discuti con loro. Le interviste tecniche sono pensate per essere una piattaforma di discussione aperta. Potresti finire per imparare qualcosa su come può essere utile. Non andare avanti alla cieca cercando di implementare qualcosa che ti ha detto il tuo intervistatore.

• In primo luogo, tokenizzare il paragrafo con i delimitatori appropriati e aggiungere le parole a una coda.

• Crea N numero di thread e tienilo in un pool di thread.

• Iterare sul pool di thread e avviare il thread e attendere il termine filo per unirsi. E inizia il thread successivo al termine del primo thread e così via.

• Ogni discussione deve solo eseguire il polling della coda e stamparla.

• Una volta che tutti i thread sono stati utilizzati nel pool di thread, iniziare da inizio del pool.

Come hai detto, non penso che questo scenario tragga grandi benefici, se non addirittura dal threading. Molto probabilmente è più lento di una singola implementazione con thread.

Tuttavia, la mia risposta sarebbe quella di avere ogni thread in un ciclo stretto che tenta di accedere a un blocco che controlla l'accesso all'indice della parola array. Ogni thread afferra il blocco, ottiene l'indice, ottiene la parola corrispondente dall'array, lo stampa, incrementa l'indice e rilascia il blocco. I thread si chiudono quando l'indice si trova alla fine dell'array.

Qualcosa del genere:

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

Penso che questo dovrebbe ottenere il thread singolo dopo un altro requisito, ma l'ordinamento dei thread non è garantito. Sono curioso di sentire anche altre soluzioni.

Utilizza le condizioni di attesa / segnale API per risolvere questo problema.

Diciamo che il primo thread preleva 1 parola e nel frattempo resto tutti i thread stanno aspettando un segnale. 1st thread print 1st word e genera il segnale al thread successivo e quindi 2nd thread stampa la seconda parola e genera il segnale su 3rd thread e così via.

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

[I termini usati qui sono forse specifici per i thread POSIX]

Dovrebbe essere possibile utilizzare anche un mutex FIFO per risolvere questo problema.

Dove usare:

Supponiamo che due thread T1 e T2 stiano cercando di eseguire una sezione critica. Entrambi non hanno molto da fare al di fuori di questa sezione critica e tengono le serrature per una buona quantità di tempo. Quindi, T1 può bloccare, eseguire e sbloccare e segnalare T2 per la sveglia. Ma prima che T2 possa riattivarsi e acquisire il blocco, T1 riacquista il lock e l'esecuzione. In questo modo, T2 potrebbe dover attendere molto tempo prima che effettivamente ottenga il blocco o non lo sia.

Come funziona / Come implementare:

Avere un mutex per bloccare. Inizializza i dati specifici del thread (TSD) per ciascun thread in un nodo contenente ID thread e semaforo. Inoltre, avere due variabili - di proprietà (VERO o FALSO o -1), proprietario (id del thread proprietario). Inoltre, mantieni una coda di camerieri e un cameriere puntatoreIl puntatore punta all'ultimo nodo nella coda dei camerieri.

operazione di blocco:

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

operazione di sblocco:

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

Domanda interessante. Ecco la mia soluzione in Java utilizzando SynchronousQueue per creare un canale rendezvous tra i thread:

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

Direi che questo tipo di domanda è molto difficile da rispondere, perché richiede il modo migliore per fare qualcosa di completamente stupido. Il mio cervello non funziona in questo modo. Non riesce a trovare soluzioni per domande stupide. Il mio cervello direbbe immediatamente che in queste condizioni, l'utilizzo di più thread non ha senso, quindi utilizzerei un singolo thread.

Quindi chiederei loro di dare una vera domanda sul threading o di farmi dare un esempio reale di alcuni threading seriali.