View Full Version : [concorrenza] rispettare ordine avvenimenti
mad_hhatter
29-10-2007, 09:51
supponiamo di avere un software multithreaded che gestisce eventi provenienti da diverse sorgenti. ogni sorgente è interrogata continuamente da un thread ad essa dedicato che si occupa di generare e lanciare i messaggi corrispondenti agli eventi generati dalla sorgente stessa.
essendoci N sorgenti ci saranno N thread responsabili della genrazione di eventi logici.
il problema nasce nel momento in cui è importante mantenere l'ordine in cui gli eventi fisici vengono generati: supponiamo che al tempo t0 la sorgente s0 generi l'evento e_s0. il thread t0 che ascolta s0 inizia la generazione dell'evento logico corrsipondente a s0, ma viene interrotto perché il sistema passa a eseguire il thread t1 associato alla sorgente s1 la quale genera a sua volta un evento e_s1 rilevato da t1. Ora, nulla vieta che t1 lanci l'evento e_s1 PRIMA del lancio dell'evento e_s0 da parte di t0 invertendo l'ordine degli eventi.
neppure sincronizzare i thread funziona in quanto t0 potrebbe sospendersi prima di riuscire ad acquisire il lock di sincronizzazione.
resta la strada della rimozione del parallelismo: un solo thread acquisisce in polling le N sorgenti, ma anche questa soluzione (peraltro non ottimale dal punto di vista della "semplicità" dell'implementazione degli ascoltatori di eventi) può portare al sovvertimento dell'ordine degli eventi (se il tempo che intercorre tra l'ultima lettura della sorgente s0 e la lettura di una sorgente sX è tale che in quel lasso di tempo s0 possa generare un evento seguito da un evento generato da sX, l'ordine degli eventi risulterà ancora una volta errato).
esiste una trattazione di questo tipo di problemi?
grazie infinite
Ciao,
potresti usare una coda in cui inserire le varie sorgenti, e poi, ad ogni inserimento, segnalare ad un altro thread che c'è una nuova sorgente da elaborare (questo thread si occupa di generare l'evento rimuovento la sorgente dalla coda).
In altre parole: gli N thread inseriscono in coda le N sorgenti, un altro thread si occupa di estrarre le sorgenti dalla coda e scatenare gli eventi. In questo modo gli eventi seguono l'ordine di arrivo delle sorgenti.
Spero di essere stato chiaro. ;)
ps: ovviamente l'accesso alla coda deve essere sincronizzato
mad_hhatter
29-10-2007, 11:43
Ciao,
potresti usare una coda in cui inserire le varie sorgenti, e poi, ad ogni inserimento, segnalare ad un altro thread che c'è una nuova sorgente da elaborare (questo thread si occupa di generare l'evento rimuovento la sorgente dalla coda).
In altre parole: gli N thread inseriscono in coda le N sorgenti, un altro thread si occupa di estrarre le sorgenti dalla coda e scatenare gli eventi. In questo modo gli eventi seguono l'ordine di arrivo delle sorgenti.
Spero di essere stato chiaro. ;)
chiarissimo, ma hai solo spostato il problema: come garantire che l'accodamento segua l'ordine reale degli eventi?
Ho appena aggiunto un ps...
L'inserimento in coda deve essere atomico e sincronizzato.
Quando un thread riceve una sorgente acquista un lock sulla coda e inserisce, poi rilascia il lock. Nella coda ci sono quindi le sorgenti in ordine di arrivo che poi vengono elaborate dall'altro thread.
ok?
Fintanto sei tu che vai a leggere i valori, (e non sono i valori "a farsi vivi") la soluzione non e' banalissima...
come vengono generati quegli eventi ? Che linguaggio usi ?
mad_hhatter
29-10-2007, 11:57
Ho appena aggiunto un ps...
L'inserimento in coda deve essere atomico e sincronizzato.
Quando un thread riceve una sorgente acquista un lock sulla coda e inserisce, poi rilascia il lock. Nella coda ci sono quindi le sorgenti in ordine di arrivo che poi vengono elaborate dall'altro thread.
ok?
avevo già considerato la sincronizzazione nel mio primo post: cosa vieta che il thread che gestisce il primo (in ordine temporale) evento venga sospeso subito prima che riesca ad acquisire il lock e che il controllo passi al gestore di un evento temporalmente successivo?
mad_hhatter
29-10-2007, 11:59
Fintanto sei tu che vai a leggere i valori, (e non sono i valori "a farsi vivi") la soluzione non e' banalissima...
come vengono generati quegli eventi ? Che linguaggio usi ?
purtroppo la questione nasce proprio dal fatto che non uso interrupt, ma testo in continuazione (da qui l'idea di usare più thread) se il valore letto dal sensore è cambiato.
sul linguaggio stendiamo un velo pietoso: sono obbligato a usare labview
in ogni caso, mi interessa anche la soluzione nel caso di un linguaggio come java o c#... ma per sfruttare gli interrupt hardware l'unica è scrivere un driver, giusto?
Ho appena aggiunto un ps...
L'inserimento in coda deve essere atomico e sincronizzato.
Quando un thread riceve una sorgente acquista un lock sulla coda e inserisce, poi rilascia il lock. Nella coda ci sono quindi le sorgenti in ordine di arrivo che poi vengono elaborate dall'altro thread.
ok?
Se il lock lo acquisisci dopo la comparsa dell'evento, non hai la garanzia che un altro thread non lo acquisisca prima di te. Dovresti acquisirlo prima ancora, ma il come dipende appunto da come vengono generati gli eventi.
purtroppo la questione nasce proprio dal fatto che non uso interrupt, ma testo in continuazione (da qui l'idea di usare più thread) se il valore letto dal sensore è cambiato.
sul linguaggio stendiamo un velo pietoso: sono obbligato a usare labview
Quindi immagino tu abbia N stream che forniscono il testo col valore letto dal sensore ?
In C potresti probabilmente usare una select(2) (ovviamente in un singolo thread) per operare sul primo descrittore con dati disponibili. Questo dovrebbe garantirti l'ordine cronologico, e comunque difficilmente riusciresti a fare di meglio. Non conosco labview per cui non so se esistano funzionalita' analoghe.
mad_hhatter
29-10-2007, 12:10
Quindi immagino tu abbia N stream che forniscono il testo col valore letto dal sensore ?
In C potresti probabilmente usare una select(2) (ovviamente in un singolo thread) per operare sul primo descrittore con dati disponibili. Questo dovrebbe garantirti l'ordine cronologico, e comunque difficilmente riusciresti a fare di meglio. Non conosco labview per cui non so se esistano funzionalita' analoghe.
ti ringrazio molto, indagherò sulla tua proposta :)
chiarissimo, ma hai solo spostato il problema: come garantire che l'accodamento segua l'ordine reale degli eventi?
Dovresti usare una specie di produttore (inserimento degli eventi in coda) / consumatori (gestori degli event)...
Un solo thread riceve le richieste e le mette in coda associandovi un timestamp...
La gestione degli eventi a questo punto può avanzare anche parallelamente, basta che ti porti dietro il timestamp per poter riorganizzare i dati prodotti della gestione degli eventi alla fine dell'elaborazione...
mad_hhatter
29-10-2007, 14:49
Dovresti usare una specie di produttore (inserimento degli eventi in coda) / consumatori (gestori degli event)...
Un solo thread riceve le richieste e le mette in coda associandovi un timestamp...
La gestione degli eventi a questo punto può avanzare anche parallelamente, basta che ti porti dietro il timestamp per poter riorganizzare i dati prodotti della gestione degli eventi alla fine dell'elaborazione...
si, avevo pensato all'uso di un timestamp... in ogni caso la tua soluzione rientra nel caso "resta la strada della rimozione del parallelismo" del mio primo post: abbiamo un thread che ascolta in polling varie sorgenti... e non è garantito che tale thread rilevi gli eventi nell'ordine in cui sono realmente accaduti. Il timestamp sarebbe utile se fosse prodotto dalla sorgente fisica dell'evento, ma farlo produrre al thread ascoltatore è un problema della stessa classe del problema originario
E' chiaro che se le sorgenti sono parallele e non producono un timestamp non sarà possibile riordinare esattamente gli eventi ;)
In ogni caso nel modo in cui ti ho detto io ti permette di ordinarli secondo l'ordine in cui sono stati letti, permettendo comunque una elaborazione parallela.
mad_hhatter
29-10-2007, 14:56
E' chiaro che se le sorgenti sono parallele e non producono un timestamp non sarà possibile riordinare esattamente gli eventi ;)
il problema era proprio quello :)
beh, grazie della conferma dei miei sospetti. cercherò il miglior compromesso :D
grazie mille a tutti per i vostri interventi
L'unico modo è togliere il parallelismo alle sorgenti...ad esempio tramite un driver che reagisce ad un IRQ...in questo modo in kernel mode ci entra un evento alla volta e la coda la puoi creare lì'...
mad_hhatter
29-10-2007, 14:58
In ogni caso nel modo in cui ti ho detto io ti permette di ordinarli secondo l'ordine in cui sono stati letti, permettendo comunque una elaborazione parallela.
chiaro. il fatto è che non mi interessa tanto gestire parallelamente la risposta agli eventi, quanto leggere parallelamente più sorgenti di segnale
comunque grazie infinite per l'aiuto
mad_hhatter
29-10-2007, 15:01
L'unico modo è togliere il parallelismo alle sorgenti...ad esempio tramite un driver che reagisce ad un IRQ...in questo modo in kernel mode ci entra un evento alla volta e la coda la puoi creare lì'...
eh lo so che con un bel driver e gli irq sarei a posto, ma sono sotto winXP, non ho mai sviluppato software non cross-platform (eccezion fatta per un software multithreaded in C per linux) e non "managed" e inoltre ho tempi di consegna molto stretti... quindi direi che di scrivere un driver per win32 non se parla proprio... pazienza, sarebbe stata la soluzione ottimale
inoltre una delle sorgenti è un canale tcp/ip quindi non saprei proprio come interfacciarmi con il network stack di win per riceverne eventuali eventi di basso livello
Ma sono dei sensori ? Come sono collegati alla macchina ?
mad_hhatter
29-10-2007, 15:10
Ma sono dei sensori ? Come sono collegati alla macchina ?
ho un dispositivo di acquisizione su porta seriale, una batteria di sensori collegati a un microcontrollore che interrogo tramite un'altra seriale e infine un connessione tcp/ip con un software che mi genera eventi lato utente
mad_hhatter
29-10-2007, 15:12
e se io suddividessi il tempo in slot di X ms e all'inizio di ogni slot campionassi tutte le sorgenti e generassi gli eventi in base alla "priorità" della sorgente stessa? potrebbe essere una soluzione ragionevole...
Perché...volevi fare un attesa attiva facendo un polling continuo ? :eek:
mad_hhatter
29-10-2007, 16:28
Perché...volevi fare un attesa attiva facendo un polling continuo ? :eek:
no, intendevo rinunciare ad acquisire in parallelo le sorgenti, affidarmi a un unico thread che acquisisce tutte le sorgenti e filtrare gli eventi sulla base della priorità associata a ciascuna sorgente...
il punto della questione non è il time slot, ma l'assegnazione di priorità alle sorgenti
Chiaramente se metti delle priorità potrai pseudo-ordinare gli eventi che te rilevi essere contemporanei (anche se non lo sono).
mad_hhatter
29-10-2007, 17:58
Chiaramente se metti delle priorità potrai pseudo-ordinare gli eventi che te rilevi essere contemporanei (anche se non lo sono).
l'idea è quella... e visto che non vedo faccine perplesse o allibite deduco che non è un'idea tanto strampalata :D forse ho trovato il mio compromesso :)
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.