[concorrenza] rispettare ordine avvenimenti

[mad_hhatter]

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

[AlbertE]

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]

Originariamente inviato da AlbertE

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?

[AlbertE]

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?

[marco.r]

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]

Originariamente inviato da AlbertE

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]

Originariamente inviato da marco.r

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?

[marco.r]

Originariamente inviato da AlbertE

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.

[marco.r]

Originariamente inviato da mad_hhatter

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]

Originariamente inviato da marco.r

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

[cionci]

Originariamente inviato da mad_hhatter

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]

Originariamente inviato da cionci

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

[cionci]

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]

Originariamente inviato da cionci

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

grazie mille a tutti per i vostri interventi

[cionci]

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]

Originariamente inviato da cionci

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]

Originariamente inviato da cionci

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

[cionci]

Ma sono dei sensori ? Come sono collegati alla macchina ?

[mad_hhatter]

Originariamente inviato da cionci

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]

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