[Threading/C++]Idle Wait

[Tommo]

Salve,
stavo provando a reinventare un accrocchio per il threading task-based... quindi creo n threads che dovranno poi eseguire i tasks che gli passo.

Però, c'è il problema che i threads ausiliari occupano sempre il 100% del core a loro assegnato, indipendentemente da cosa stanno eseguendo...

Per ora ho risolto mettendo un lock se il thread non ha tasks da eseguire, che lo stoppa, però volevo approfondire la differenza tra il thread "main" e i thread ausiliari...

Se nel thread principale metto solo un if() su qualche valore eseguito in loop, la CPU rimane quasi vuota... mentre negli altri threads schizza al 100%.
è possibile "emulare" questo comportamento negli altri threads?

[WarDuck]

Ma il thread è messo in un ciclo while(true) con relativo periodo di sleep?

tipo:

while(true):
    # fai qualcosa
    sleep(1000) # dorme per un secondo

[Tommo]

Si:

	boost::mutex sleepMutex;
	boost::unique_lock<boost::mutex> sleepLock( sleepMutex );
	while(working)
	{
		if( sleeping )
			sleepCondition.wait( sleepLock );

		update();

		this_thread::yield();
	}

Però al posto di sleep uso yield() che dovrebbe rilasciare solo la timeslice in eccesso e non un tempo arbitrario.
Infatti anche se rallentato il sistema è fluido...

[WarDuck]

Originariamente inviato da Tommo

Si:

	boost::mutex sleepMutex;
	boost::unique_lock<boost::mutex> sleepLock( sleepMutex );
	while(working)
	{
		if( sleeping )
			sleepCondition.wait( sleepLock );

		update();

		this_thread::yield();
	}

Però al posto di sleep uso yield() che dovrebbe rilasciare solo la timeslice in eccesso e non un tempo arbitrario.
Infatti anche se rallentato il sistema è fluido...

Mmmm non vorrei dire fesserie, cmq con yield comunichi allo scheduler che il tuo thread ha "finito" e quindi di dare la priorità ad altri thread, tuttavia se ce ne sono pochi è probabile che lo scheduler metta in run lo stesso thread (e da qui il 100% della cpu).

Cmq una cosa carina da implementare è un modello che crea thread dinamicamente al bisogno, ovvero solo quando ci sono effettivamente work da effettuare.

Oppure un'altra strategia potrebbe essere quella di crearne un po' e lasciarli dormienti... fai un lock per ogni thread (a cui può accedere solo il master) e sbloccarli solo quando ci sono compiti da effettuare (puoi fare una condition su una variabile puntatore a funzione).

Dovresti anche tenere traccia di quali sono i thread occupati, poiché il master deve saperlo (ed in caso se li trova in gran parte occupati dovrebbe crearne altri).

[marco.r]

non capisco una cosa... a cosa servono l'if e la yield ?
Sono ridondanti ed inutili se usi il lock.

[Tommo]

Mmmm non vorrei dire fesserie, cmq con yield comunichi allo scheduler che il tuo thread ha "finito" e quindi di dare la priorità ad altri thread, tuttavia se ce ne sono pochi è probabile che lo scheduler metta in run lo stesso thread (e da qui il 100% della cpu).

Boh yield serve nelle condizioni di "full load", cioè quando effettivamente devo usare più CPU possibile (task assegnato).
Tuttavia lo stesso identico codice nel Main Thread genera un'occupazione del 3 o 4% massimo, evidentemente ha qualche controllo in più?

Il lock serve per spegnere il thread, e l'if è necessario perchè sleepCondition.wait() va chiamato nel thread che deve essere messo ad aspettare, non posso chiamarlo in "sleep()".
Se non metto l'if e il lock non è acquisito crasha.

@WarDuck: è proprio quello che sto facendo... mi creo n "WorkerThreads", dove n = numero_thread_nativi*2 (per qualche motivo sulla mia CPU genera le massime prestazioni)
Questi chiedono dei Tasks ad un Dispatcher che mantiene una queue; se c'è una "Task request miss", cioè non c'è niente da fare, il thread si iberna.
Il Dispatcher poi quando riceve un nuovo Task lo userà per svegliare uno dei thread inattivi invece di metterlo in coda, se possibile.

I thread vengono creati all'inizio dal dispatcher e sono privati, il loro numero non dovrebbe mai variare... e poi l'intero attrezzo serve PROPRIO ad evitare i locks obbligando relazioni di dipendenza tra i tasks... infatti l'unico lock che c'è nel programma sta in "issue" e "request" perchè altrmenti la queue da i numeri

Tornando IT: mi sembra di aver capito che non è ottimale il mio uso dello sleepLock, come faccio a fare un lock "a cui può accedere solo il master"?

[monelli]

Mi intrometto se ti interessa esiste una libreria zthread che permette di fare quello che chiedi te... Puo creare un pool di x thread ed hai una lista di task che vengono mandati in esecuzione su quei thread o accodati...

[marco.r]

Originariamente inviato da Tommo

Boh yield serve nelle condizioni di "full load", cioè quando effettivamente devo usare più CPU possibile (task assegnato).
Tuttavia lo stesso identico codice nel Main Thread genera un'occupazione del 3 o 4% massimo, evidentemente ha qualche controllo in più?

Il lock serve per spegnere il thread, e l'if è necessario perchè sleepCondition.wait() va chiamato nel thread che deve essere messo ad aspettare, non posso chiamarlo in "sleep()".
Se non metto l'if e il lock non è acquisito crasha.

@WarDuck: è proprio quello che sto facendo... mi creo n "WorkerThreads", dove n = numero_thread_nativi*2 (per qualche motivo sulla mia CPU genera le massime prestazioni)
Questi chiedono dei Tasks ad un Dispatcher che mantiene una queue; se c'è una "Task request miss", cioè non c'è niente da fare, il thread si iberna.
Il Dispatcher poi quando riceve un nuovo Task lo userà per svegliare uno dei thread inattivi invece di metterlo in coda, se possibile.

Continuo a non capire... se hai una coda dalla quale prendere i task da eseguire, sara' semplicemente la coda a fare aspettare i thread, a patto di settare le richieste come bloccanti, senza bisogno di if, sleep o wait...
Non ho molta pratica di come usare le boost in questo senso, ma ad esempio sotto unix userei una posix_queue e mi toglierei tutte le rogne.

I thread vengono creati all'inizio dal dispatcher e sono privati, il loro numero non dovrebbe mai variare... e poi l'intero attrezzo serve PROPRIO ad evitare i locks obbligando relazioni di dipendenza tra i tasks... infatti l'unico lock che c'è nel programma sta in "issue" e "request" perchè altrmenti la queue da i numeri

come fai ad evitare le dipendenze ? Prima o poi devi verificare se ci sono task disponibili per cui per il lock ci devi passare, non vedo una gran differenza...

[Tommo]

Uhm... per rispondere anche a monelli, sto facendo sta cosa soprattutto per capire il threading, quindi si, molte cose potrebbero non avere alcun senso

Per esempio, che è una "richiesta bloccante"?

Per le dipendenze: un Task è un nodo di un'albero di dipendenze; per cui il Dispatcher percorre questo albero e "stacca" le foglie, che sono i Task pronti per essere eseguiti... in questa maniera se si organizza bene la struttura si riesce a sfruttare un numero arbitrario di cores, indirizzando le foglie allo stesso livello (cioè indipendenti) su thread separati.
Nota: non è che me lo sono inventato, ho copiato spudoratamente Intel Concurrent Collections
Quindi i lock servono solo a task finito, ma non durante come potrebbe essere in un sistema tradizionale con un thread che fa la fisica uno che fa la grafica etc.
E poi ci sono locks e locks... un conto è un lock attivato sempre che blocca tutto un thread aspettando altro; un conto è il lock sulla queue, che ha più una funzione di sicurezza dato che al 99% il programma funge anche senza.

[banryu79]

[Parzialmente OT]
@Tommo: dato che mi sembra che stiate parlando di usare dei "working threads" ti posto questo articolo presente nel sito della IBM (il linguaggio di rif. è Java, ma nell'articolo la discussione teorica sui thread pool e le "working" queue è valida a prescindere, e non si fa riferimento a particolari librerie dell'SDK per Java [che all'epoca dell'articolo ancora non esistevano, almeno ufficialmente] ma si basa sulle sole funzionalità di multithreading nude e crude incorporate nel linguaggio).
- Java theory and practice: Thread pools and work queues

Poi, a questa pagina di wikipedia ho visto che ci sono link a zilionate di informazioni.
-> http://en.wikipedia.org/wiki/Thread_pool_pattern
@Edit: compresa la pagina che ti ho linkato sopra

[marco.r]

Originariamente inviato da Tommo

Uhm... per rispondere anche a monelli, sto facendo sta cosa soprattutto per capire il threading, quindi si, molte cose potrebbero non avere alcun senso

Per esempio, che è una "richiesta bloccante"?

In questo caso, una chiamata alla coda che ritorna solo se ci sono oggetti nella stessa; in caso contrario il thread rimane in attesa che qualche altro thread "spinga" un nuovo oggetto sulla stessa.

Per le dipendenze: un Task è un nodo di un'albero di dipendenze; per cui il Dispatcher percorre questo albero e "stacca" le foglie, che sono i Task pronti per essere eseguiti... in questa maniera se si organizza bene la struttura si riesce a sfruttare un numero arbitrario di cores, indirizzando le foglie allo stesso livello (cioè indipendenti) su thread separati.
Nota: non è che me lo sono inventato, ho copiato spudoratamente Intel Concurrent Collections
Quindi i lock servono solo a task finito, ma non durante come potrebbe essere in un sistema tradizionale con un thread che fa la fisica uno che fa la grafica etc.
E poi ci sono locks e locks... un conto è un lock attivato sempre che blocca tutto un thread aspettando altro; un conto è il lock sulla queue, che ha più una funzione di sicurezza dato che al 99% il programma funge anche senza.

I lock li intendevo sulla sola coda di task e servono solo per sincronizzare l'accesso alla coda. A seconda dei casi l'accesso lo devi gestire tu, oppure puo' essere parte delle API della coda (ade sempio come e' nel caso delle code messaggi POSIX).

Io una buona implementazione della tua idea la vedrei nel seguente modo:

- Utilizzi due code. Una coda di task da fare e una di task fatti. Il thread principale legge i task fatti e mette i task da fare. I thread worker leggono dalla coda dei task da fare e spingono indietro quelli fatti

- Il thread principale procede come segue:

* fa una prima scansione dell'albero : spingi ogni foglia "libera" sullla coda dei task da fare
* Mettiti in ascolto sulla coda dei task fatti. Per ogni task che arriva verifica il padre del task. Se il padre ha tutti i figli completati, allora spingi tale nodo sui task da fare

Mentre gli altri thread procedono semplicemente come

* mettiti in ascolto sulla coda dei task. Quando arriva un task eseguilo, una volta finito rimettilo sull'altra coda

Poi dipende da come costruisci/mantieni/aggiorni l'albero, ma come idea di base dovrebbe essere semplice da codificare, e anche sufficientemente performante.

[cionci]

La condition non avrebbe bisogno di avere una mutex acquisita ?

	boost::mutex sleepMutex;
	boost::unique_lock<boost::mutex> sleepLock( sleepMutex );
	while(working)
	{
		sleepLock.lock();
		if( sleeping )
			sleepCondition.wait( sleepLock );
		sleepLock.unlock();

		update();

		this_thread::yield();
	}

PS: non conosco libboost, ma vado per analogia con pthread

[cionci]

Io sinceramente farei tutto senza condition...una coda circolare con i thread in attesa, una mutex per ogni elemento della coda. Quando un thread è disponibile acquisisce un elemento della coda, la relativa mutex e scrive i risultati in un'apposita struttura (ad esempio allocando una opportuna struttura dati).
Il thread principale si occupa di recuperare i risultati e poi fa una signal sulla mutex.

La struttura della coda può essere quella classica, con semaforo pieno e semaforo vuoto.

[Tommo]

Grazie per le idee, mi sa che qua ci sta un bel refactoring
La coda dei task finiti in realtà non mi è sembrata troppo utile, perchè richiede un lock in più quando ci si va a scrivere, e poi un altro thread che volesse trovarci dentro un task a cui è interessato dovrebbe leggersela tutta.
Invece io ho messo uno stato interno di Task (completed, etc), un Listener, e un Garbage Collector per i Tasks: cioè se si assegna un listener ad un task, quando termina questo aggiunge un evento "listenedTaskCompleted" su una queue di Dispatcher, quindi dispatcher provvede a chiamare il Listener quando ci si trova sul main thread.
Quindi (se il thread è "autoDeletable"), percorre l'albero a partire dal Task completato e distrugge quello e tutti i parents diventati inutili col completamento del Task corrente (es: erano aspettati solo da lui).

Comunque il problema principale è che la documentazione di Boost fa un pò pena, è difficile capire come fungono mutex eccetera.

@cionci: mi sembra che lock e unlock li gestisce wait, nel senso che quando ci entra chiama unlock() + lock() e quando esce chiama lock() + unlock() se possibile.

[cionci]

Originariamente inviato da Tommo

@cionci: mi sembra che lock e unlock li gestisce wait, nel senso che quando ci entra chiama unlock() + lock() e quando esce chiama lock() + unlock() se possibile.

No, altrimenti non può gestire la concorrenza sulla condizione.
Solitamente la condition si chiama per attendere che si verifichi una determinata condizione. Questa condizione viene testata tramite variabili condivise, è chiaro che queste variabili condivise debbano essere gestite in mutua esclusione. Inoltre se guardi la documentazione vedrai che genera un'eccezione se il lock non è acquisito.
Se acquisisse il lock dentro la wait la mutua esclusione sulla condizione non sarebbe garantita. Ci potrebbero essere tra l'altro delle corse critiche.

[marco.r]

Originariamente inviato da Tommo

Grazie per le idee, mi sa che qua ci sta un bel refactoring
La coda dei task finiti in realtà non mi è sembrata troppo utile, perchè richiede un lock in più quando ci si va a scrivere, e poi un altro thread che volesse trovarci dentro un task a cui è interessato dovrebbe leggersela tutta.
Invece io ho messo uno stato interno di Task (completed, etc), un Listener, e un Garbage Collector per i Tasks: cioè se si assegna un listener ad un task, quando termina questo aggiunge un evento "listenedTaskCompleted" su una queue di Dispatcher, quindi dispatcher provvede a chiamare il Listener quando ci si trova sul main thread.

Uhm, la coda è poco utile perchè la puoi sostituire con tre-quattro oggetti differenti ? . Tieni presente che parlavo di coda di task, ma all'atto pratico la puoi benissimo (anzi meglio) implementare come coda di numeri (task id).

Quindi (se il thread è "autoDeletable"), percorre l'albero a partire dal Task completato e distrugge quello e tutti i parents diventati inutili col completamento del Task corrente (es: erano aspettati solo da lui).

È quello che fa la mia soluzione con una differenza sostanziale. Cosa succede quando due listener finiscono contemporaneamente si mettono a modificare l'albero contemporaneamente. In bocca al lupo.
Puoi sistemare facilmente... riempiendo di lock l'albero ( o anche uno solo che blocchi tutto ).
Peggio ancora. Se la callback viene eseguita all'atto della conclusione del task, per come l'hai descritto verra' eseguita dal thread stesso. Il che vuol dire che tutti i processori della tua macchina dovrano costantemente sincronizzare la loro cache devastando le prestazioni.
Idealmente vuoi che le informazioni condivise tra i vari thread siano il minimo possibile. Se riesci a far stare l'albero sulla cache di un solo processore è molto meglio, tanto non ti serve per eseguire i singoli task. E l'implementazione, ripeto, è veramente semplcie.

[cionci]

Non avevo letto molto bene la struttura che vuoi realizzare. Comunque la concorrenza secondo me può essere gestita sui risultati, non sulla struttura dei thread. I thread dovrebbero essere gestiti separatamente.

Dato un albero di dipendenza il dispatcher si occupa solo di allocare il o i thread che dipendono da tutti gli altri.
C'è un canale di comunicazione fra i thread. Un thread che dipende da un altro si registra sul canale inviando i dati da elaborare e si mette in attesa dei risultati. Quando l'elaborazione di un thread finisce questo invia i risultati sul canale di comunicazione e si mette in attesa di ricevere nuovi dati su cui lavorare.

[Tommo]

Originariamente inviato da marco.r

Uhm, la coda è poco utile perchè la puoi sostituire con tre-quattro oggetti differenti ? . Tieni presente che parlavo di coda di task, ma all'atto pratico la puoi benissimo (anzi meglio) implementare come coda di numeri (task id).

Beh la mia implementazione fa anche altro, visto che si prende la briga di chiamare una funzione dell'User nel main thread per poi cancellare da solo il Task...
quello che intendevo con "poco utile" è che con una semplice completed queue hai che il main thread si deve prendere la briga di verificare da sè lo stato di completamento, quindi andarsi a cercare il task in oggetto tra i completi e toglierlo.
Nè comodo nè efficiente

Originariamente inviato da marco.r

È quello che fa la mia soluzione con una differenza sostanziale. Cosa succede quando due listener finiscono contemporaneamente si mettono a modificare l'albero contemporaneamente. In bocca al lupo.
Puoi sistemare facilmente... riempiendo di lock l'albero ( o anche uno solo che blocchi tutto ).
Peggio ancora. Se la callback viene eseguita all'atto della conclusione del task, per come l'hai descritto verra' eseguita dal thread stesso. Il che vuol dire che tutti i processori della tua macchina dovrano costantemente sincronizzare la loro cache devastando le prestazioni.
Idealmente vuoi che le informazioni condivise tra i vari thread siano il minimo possibile. Se riesci a far stare l'albero sulla cache di un solo processore è molto meglio, tanto non ti serve per eseguire i singoli task. E l'implementazione, ripeto, è veramente semplcie.

Allora, i listener sono assolutamente read-only e vengono chiamati SOLO sul main thread.
Il lock serve solo quando il WorkerThread notifica il Dispatcher che un Task Listened (non lo sono tutti, anzi, dovrebbero essere uno o due) è completato.
Questo fa si che il Task sia considerato automaticamente NON deletable, ma viene cancellato solo dal main thread alla fine della chiamata al listener se permane in stato "autoDeletable".

Però non c'entra niente, ma il problema dell'albero in effetti esiste... dato che tutti i Task eccetto quelli listened vengono eliminati sul thread di appartenenza... mi sa che in effetti a sto punto va unificata la cosa con una completed queue

Originariamente inviato da cionci

Non avevo letto molto bene la struttura che vuoi realizzare. Comunque la concorrenza secondo me può essere gestita sui risultati, non sulla struttura dei thread. I thread dovrebbero essere gestiti separatamente.

Dato un albero di dipendenza il dispatcher si occupa solo di allocare il o i thread che dipendono da tutti gli altri.
C'è un canale di comunicazione fra i thread. Un thread che dipende da un altro si registra sul canale inviando i dati da elaborare e si mette in attesa dei risultati. Quando l'elaborazione di un thread finisce questo invia i risultati sul canale di comunicazione e si mette in attesa di ricevere nuovi dati su cui lavorare.

Ma, quello che proponi te a "canali di comunicazione" sembra l'approccio vecchio che NON volevo seguire, con 2 threads in continue race conditions tra di loro...
nel mio design si allocano n thread (con n sconosciuto all'utente, e con i thread classe privata di Dispatcher) e viene esposta solo l'interfaccia "ad albero" dei Task.
La dipendenza è resa semplicemente dalle relazioni tra questi ultimi, e i thread sono faccenda del dispatcher...
Un task dovrebbe essere completamente data parallel, cioè deve eseguirsi dall'inizio alla fine senza alcuna richiesta verso threads di livello uguale o superiore al suo, per definizione

Comunque, non pensavo di doverlo mai chiedere in questi termini ma avete un buon testo di riferimento da studiare?
Il threading mi sembra proprio difficile da afferrare per prove...
PS: preferibilmente roba gratis

[cionci]

Originariamente inviato da Tommo

Ma, quello che proponi te a "canali di comunicazione" sembra l'approccio vecchio che NON volevo seguire, con 2 threads in continue race conditions tra di loro...

Non necessariamente. Dipende da come implementi il canale e i thread
Ad esempio puoi implementare con due stati:
- registrazione richieste sul canale
- elaborazione e invio risultati sul canale
I due stati possono anche non necessariamente essere lo stesso thread
Il canale può anche essere il dispatcher stesso.

Alloco il thread A, nel costruttore si registra sul canale per un thread di tipo B e due thread di tipo C. Termina il costruttore.

Il canale vedendo le richieste alloca i thread richiesti. Il thread di tipo B richiede l'esecuzione di un thread del tipo D. Il canale alloca un thread di tipo D. Il thread di tipo D non registra alcuna richiesta, quindi i requisiti sono soddisfatti e il canale "invia i risultati" (fra virgolette perché di fatto mette in esecuzione il thread).
Alla fine di D, D invia i risultati sul canale, il canale verifica che i requisiti del thread B sono soddisfatti...invia i risultati ed esegue il thread B.
L'unico che cicla è il thread del canale. Volendo si potrebbe lavorare anche su questo aspetto.

[marco.r]

Originariamente inviato da Tommo

Beh la mia implementazione fa anche altro, visto che si prende la briga di chiamare una funzione dell'User nel main thread per poi cancellare da solo il Task...
quello che intendevo con "poco utile" è che con una semplice completed queue hai che il main thread si deve prendere la briga di verificare da sè lo stato di completamento, quindi andarsi a cercare il task in oggetto tra i completi e toglierlo.
Nè comodo nè efficiente

Dipende come implementi l'albero. saranno 20 linee di codice che lavorano in tempo costante.
Se ci dai un esempio di come dovrebbero essere le api si puo' provare una implementazione rapida, cosi' possiamo confrontare le varie idee.