Esiste un algoritmo per determinare la quantità di lavoro necessaria per mantenere occupati i lavoratori?

Question

Esiste un algoritmo per determinare la quantità di lavoro necessaria per mantenere occupati i lavoratori?

#1 da (3 voti)
#2 da (2 voti)
#3 da (2 voti)

1

Ho scritto un programma multi-thread che genera casualmente stringhe e, dopo la generazione, controlla se la stringa contiene un determinato valore. Vale a dire, StringGenerator e StringChecker . Quello che sto cercando di capire è quanti thread StringGenerator mi servirebbero per mantenere StringChecker occupato.

Tutti i StringGenerator thread hanno un riferimento a un Queue che contiene tutte le stringhe necessarie per essere controllato e quando generano una stringa, viene aggiunto a Queue . Tutti i thread StringChecker hanno anche un riferimento allo stesso Queue e lo interrogano per ottenere la stringa successiva e controlla se contiene la parola chiave.

Dato che la generazione delle stringhe richiede più tempo rispetto al loro controllo, quello che voglio sapere è se ci sono equazioni, algoritmi o analisi che possono essere fatti sul codice che possono aiutarmi a dirmi approssimativamente quanti fili di ciascun io avrò bisogno in modo tale che la somma di tutte le stringhe generate da StringGenerator s sia il più vicino possibile al numero di stringhe controllate da StringChecker s.

algorithms concurrency multithreading

posta Zymus 31.12.2014 - 23:58

fonte

3 risposte

Leggi altre domande sui tag algorithms concurrency multithreading

Perché Double.parseDouble ("ABC") non restituisce Double.NaN? La ragione per scala non supporta l'ereditarietà multipla [chiusa]

score 3 · Answer 1

Non è possibile avere più thread produttivi rispetto ai processori. (Per ora sto ignorando I / O.) Supponiamo che maxThreads sia il numero massimo totale di thread che si desidera avere. Questo è un limite morbido. Potrebbe essere superato temporaneamente, ma l'eccesso si correggerà da solo.

Avere una coda di stringhe deselezionate, inizialmente vuote. Avvia un thread StringChecker.

Ogni volta che un StringChecker vede la coda vuota, avvia un nuovo thread StringGenerator. Se il numero totale di thread ora supera maxThreads e questo non è l'unico thread di StringChecker, si arresta. Altrimenti, tira una stringa dalla coda e la controlla.

Ogni volta che un StringGenerator ha una stringa pronta per essere controllata ma trova che la coda è piena, avvia un nuovo thread StringChecker. Dopo aver atteso che la coda si sblocchi e lascia che metta la stringa nella coda, se il numero totale di thread supera ora maxThreads e non è l'ultimo StringGenerator, si ferma.

Risposta migliore

Stavo giocando nella mia mente come si comporterebbe questo sistema e quello descritto da @rwong, e ci siamo resi conto che ci stiamo sbagliando tutto questo. Quanto tempo ci vuole per generare una stringa rispetto a quanto tempo ci vuole per controllarne uno è irrilevante. Quando il sistema raggiunge lo stato stazionario, controllerà le stringhe esattamente alla stessa velocità con cui le genera. stringsGenerated = stringsChecked + stringsInQueue + stringsBeingChecked e gli ultimi due termini sono sia piccoli che limitati.

Ciò significa che puoi anche iniziare come molti thread che ritieni utili e avere ogni thread:

loop
    generate a string
    check it
end loop

Vedo che @Doval ha avuto la stessa idea, quindi ho aggiunto il suo commento.

score 2 · Answer 2

Supponendo che il tempo necessario per generare e controllare le stringhe sia abbastanza regolare, è possibile codificare un rapporto hard dopo aver fatto un po 'di tempo. Supponiamo che la generazione di una stringa richieda in media N nanosecondi e che il controllo richieda M nanosecondi. Se ci vuole tre volte il tempo per generare come per controllare, cioè se N / M = 3, allora ci dovrebbero essere tre volte più generatori quanti sono i controllori - tre generatori per ogni correttore. Quindi fai qualche profilazione, trova delle medie e calcola il rapporto che ti serve.

score 2 · Answer 3

C'è un altro approccio. Questo è simile alla risposta di @ ganbustein, ma con una differenza. È noto come il parallelismo delle attività paradigma.

Nel parallelismo delle attività,

Tutta l'esecuzione è scomposta e le attività scomposte sono impacchettate in attività.
(Conosciuto anche come "chiusure", che significa un'unità autonoma di codice eseguibile e tutti i dati necessari.) Se alcuni dati non sono t immediatamente disponibile (cioè dipendente da un'altra attività), questa dipendenza viene rilevata dal motore del parallelismo delle attività e il codice eseguibile lo tratterà racchiudendolo in Future .)
Le dipendenze tra le attività sono stabilite.
I task pronti per l'esecuzione vengono inseriti in una coda comune.
Qualsiasi CPU disponibile, catturerà qualsiasi attività che si trova sulla parte anteriore della coda comune.
Dopo aver eseguito l'attività, tutte le attività successive la cui dipendenza dai dati sarà soddisfatta verranno ora aggiunte alla coda comune.

La differenza fondamentale tra il parallelismo delle attività e la risposta di @ ganbustein è questa: "non c'è affinità tra tipi di attività, thread o core della CPU".

Per riformulare in una frase semplice, "qualsiasi thread può eseguire qualsiasi tipo di attività che appare in coda."

Dato il tuo esempio, puoi istanziare tutti i thread quanti sono i core della CPU, e tutti questi thread eseguiranno il seguente ciclo infinito:

Se c'è una stringa nella coda "in attesa di controllo", verrà spuntata e controllata.
(Nel pensiero orientato all'attività, questa è una semplificazione dell'esecuzione di StringCheckerTask .)
Altrimenti, genera una nuova stringa casuale e aggiungi alla coda "waiting to be checked".
(Nel pensiero orientato all'attività, questa è una semplificazione dell'esecuzione di StringGeneratorTask .)
Continua a eseguire il ciclo fino all'interruzione.

Risultato previsto: vedrai che tutti i core sono completamente occupati. Assicurati che la tua CPU abbia una buona ventilazione.

Effetti collaterali: massimizzando l'utilizzo della CPU, noterai che pone un strong stress all'implementazione della struttura Queue . Tutte le CPU leggeranno e scrivono questa coda, quindi questo crea molti conflitti di accesso alla memoria. (Se la tua coda non è thread-safe, inizierà anche a perdere o danneggiare i dati abbastanza rapidamente.)