[C/C++] Teorema del campionamento

[misterx]

ciao,
siccome ho scritto un programma che in definitiva è un campionatore, mi chiedevo se il teorema del campionamento è usabile anche nel mio caso.

Ho un thread che scansiona le porte di un apparato collegato via ethernet e riempe un array di 1024 byte.

Un secondo thread verifica se qualcuno dei suoi bit ha cambiato di stato: mi interessano i singoli bit, se a zero oppure ad uno.

Un terzo thread resta in attesa del secondo e se c'è qualcosa da scrivere su disco viene risvegliato.

Ho notato che i tempi di esecuzione tra i vari thread in windows XP sono dell'ordine di 1/3 millisecondi e quindi del tutto trascurabili per i miei scopi.

La domanda: se il dispositivo più veloce cambia il suo stato ogni 500 millisecondi ed io eseguo il primo thread ogni 250 millisecondi è garantito che riesco a catturare in modo preciso lo stato di tutti i bit dell'apparato?

E' un dubbio un pò forse banalotto ma non avendo esperienza vi chiedo conferme soprattutto in quanto ho verificato che lo scheduler di windows XP è veramente NON deterministico.

grazie 1000

[gugoXX]

Originariamente inviato da misterx

La domanda: se il disositivo più veloce cambia il suo stato ogni 500 millisecondi ed io eseguo il primo thread ogni 250 millisecondi è garantito che riesco a catturare in modo preciso lo stato di tutti i bit dell'apparato?

Non ti serve il teorema del campionamento.
Se agisci cosi' ovviamente riuscirai a catturare il cambio di stato di un bit con "al piu'" 250 millisecondi di ritardo.

[misterx]

Originariamente inviato da gugoXX

Non ti serve il teorema del campionamento.
Se agisci cosi' ovviamente riuscirai a catturare il cambio di stato di un bit con "al piu'" 250 millisecondi di ritardo.

quindi nel mio caso ritardare il secondo thread non servirebbe a nulla?

[gugoXX]

Originariamente inviato da misterx

quindi nel mio caso ritardare il secondo thread non servirebbe a nulla?

Non capisco cosa significa "servire". Servire a cosa?

Se ogni segnale cambia al massimo ogni 500ms, e tu campioni ogni 250ms, non perderai alcuna informazione, ovvero avrai tutte le informazioni che ti servono, ma riceverai un cambio di segnale con un po' di ritardo, al piu' 250ms.

[misterx]

Originariamente inviato da gugoXX

Non capisco cosa significa "servire". Servire a cosa?

Se ogni segnale cambia al massimo ogni 500ms, e tu campioni ogni 250ms, non perderai alcuna informazione, ovvero avrai tutte le informazioni che ti servono, ma riceverai un cambio di segnale con un po' di ritardo, al piu' 250ms.

il ritardo lo introduco per evitare di usare la CPU al 100%. Introducendo ritardi di 250 millisecondi, la CPU può dedicare il suo tempo a fare altro però il dubbio era se riuscivo ugualmente ad accorgermi che un bit era cambiato.

Ho notato che se calcolo il tempo di cambiamento di stato, per uno stesso bit, il tempo totale di variazione che leggo a volte è di 500 ms ed altre 750 ms, come se venissero sommati i 250 ms di attesa del secondo thread.

Continuando a diminuire il tempo di attesa del secondo thread sino a 5 ms la differenza rispetto ai 500 ms del cambiamento di stato sull'apparato si assottiglia, solo a volte leggo anzichè 500 ms, 516 ms

[tomminno]

Originariamente inviato da misterx

La domanda: se il dispositivo più veloce cambia il suo stato ogni 500 millisecondi ed io eseguo il primo thread ogni 250 millisecondi è garantito che riesco a catturare in modo preciso lo stato di tutti i bit dell'apparato?

grazie 1000

Dato che stiamo parlando di sistemi operativi dotati di memoria virtuale non c'è garanzia che il thread venga risvegliato esattamente ogni 250 ms e che riesca a leggere i dati in tempo. Nel caso più catastrofico potrebbero verificarsi dei PageFault a cascata che rallentano l'esecuzione.

In ogni caso le periferiche generalmente hanno un buffer pertanto anche se la lettura arrivasse in ritardo dovresti trovare tutto.
Per riprova fai una lettura ogni 750ms, dovresti riuscire a leggere tutto quello che è stato inviato in precedenza.

Ma hai veramente necessità di uno sleep? Potresti semplicemente avere un thread che legge in continuazione dal socket con letture bloccanti (pertanto il thread rimane fermo nel caso in cui non ci siano dati in arrivo) e solleva eventi. Questi eventi verranno intercettati da una classe che conosce il protocollo di comunicazione e interpreta quando è arrivato un intero pacchetto logico di dati che a sua volta genererà altre azioni a seconda di quello che devi fare.

[misterx]

Originariamente inviato da tomminno

Dato che stiamo parlando di sistemi operativi dotati di memoria virtuale non c'è garanzia che il thread venga risvegliato esattamente ogni 250 ms e che riesca a leggere i dati in tempo. Nel caso più catastrofico potrebbero verificarsi dei PageFault a cascata che rallentano l'esecuzione.

In ogni caso le periferiche generalmente hanno un buffer pertanto anche se la lettura arrivasse in ritardo dovresti trovare tutto.
Per riprova fai una lettura ogni 750ms, dovresti riuscire a leggere tutto quello che è stato inviato in precedenza.

Ma hai veramente necessità di uno sleep? Potresti semplicemente avere un thread che legge in continuazione dal socket con letture bloccanti (pertanto il thread rimane fermo nel caso in cui non ci siano dati in arrivo) e solleva eventi. Questi eventi verranno intercettati da una classe che conosce il protocollo di comunicazione e interpreta quando è arrivato un intero pacchetto logico di dati che a sua volta genererà altre azioni a seconda di quello che devi fare.

nella mia situazione ho un thread che legge dati da ethernet e riempie un array di 1024 byte ogni tot millisecondi, questo perchè io non posso sapere quando cambia lo stato dei bit dell'apparato; questo è un compito che spetta al mio programma come spetta anche calcolare per quanto tempo è rimasto a zero oppure a uno ognuno dei suoi bit.

Siccome non so ogni quanto cambiano di stato i tali bit, ecco l'esigenza di uno sleep che liberasse la CPU per altri programmi, altrimenti avrei un uso della CPU pari al 100%

[starfred]

Come dice tomino non hai nessuna garanzia sulle temporizzazioni e quindi sulla deadline del thread che effettua la lettura. Anche se vai 100x più veloce prima o poi si potrebbero creare una serie di eventi che farà saltare il ciclo di lettura.
Se non ti ho convito basta immaginare una semplice operazione di I/O su disco di una primitiva di sistema con massima priorità, se dura più di 500ms sei "fritto". (Ho ipotizzato uno scheduler di tipo prioritario ma si può fare lo stesso con uno di time sharing).
A questo punto bisogna verificare se per te il salto di un ciclo di lettura è catastrofico oppure no, ovvero se si sta parlando di processi (nel tuo caso thread) di tipo hard o soft.
Poiché quello che a te interessa è la schedulazione di task periodici di una applicazione real-time, ti consiglio di guardare i seguenti standart per lo sviluppo di applicazioni real-time:
rt-posix
osek
apex
uITRON

Buona lettura.

[gugoXX]

Prova ad usare i Multimedia Timer invece che quelli forniti dal Framwork, sembrano essere piu' precisi.

http://www.softwareinteractions.com/...er-from-c.html

Io organizzerei cosi', il thread che legge la porta Ethernet appende i 1024 risultati in un List<byte[]>, ogni immagine.
quello che legge i risultati parte dal presupposto che ognuno dei byte[] e' spiazzato di esattamente 500ms, e non parte ricaclolando i tempi, ma li da gia' per spiazzati esattamente quanto impostato dal timer di lettura.
Windows non e' come detto un sistema operativo real time, ma questi multimedia timer sembrano essere sufficientemente precisi.

Dai anche un'altra priorita' al tuo processo, per favorirlo nelle schedulazioni.

System.Diagnostics.Process.GetCurrentProcess().PriorityClass =
System.Diagnostics.ProcessPriorityClass.High;

[banryu79]

Originariamente inviato da misterx

Ho notato che se calcolo il tempo di cambiamento di stato, per uno stesso bit, il tempo totale di variazione che leggo a volte è di 500 ms ed altre 750 ms, come se venissero sommati i 250 ms di attesa del secondo thread.

come già detto da gugoXX:

Originariamente inviato da gugoXX

Se ogni segnale cambia al massimo ogni 500ms, e tu campioni ogni 250ms, non perderai alcuna informazione, ovvero avrai tutte le informazioni che ti servono, ma riceverai un cambio di segnale con un po' di ritardo, al piu' 250ms.

A) quando il thread lettore rileva un tempo di cambiamento di 500 ms significa che è stato risvegliato dalla sleep e quindi ha effettuato la lettura subito dopo che il valore nel dispositivo è stato cambiato (cambia appunto ogni 500 ms).

B) quando invece rileva un tempo di cambiamento di 750 ms (500 + 250) significa che è stato risvegliato dalla sleep appena prima della successiva mutazione del valore nel dispositivo, quindi la leggerà dopo la prossima sleep, tra 250 ms (il ritardo si accumula rispetto al tempo rilevato all'ultima lettura).

Originariamente inviato da misterx

Continuando a diminuire il tempo di attesa del secondo thread sino a 5 ms la differenza rispetto ai 500 ms del cambiamento di stato sull'apparato si assottiglia, solo a volte leggo anzichè 500 ms, 516 ms

Come sopra, nel caso A leggi 500, nel caso B leggi 516 ms anche se al più dovrebbe essere (500 + 5 = 505) per via del discorso che abbiamo fatto in un altro thread circa la granularità del timer di sistema in Windows di circa 16 millisec (o almeno è quello che penso succeda).

[misterx]

Originariamente inviato da starfred

Come dice tomino non hai nessuna garanzia sulle temporizzazioni e quindi sulla deadline del thread che effettua la lettura. Anche se vai 100x più veloce prima o poi si potrebbero creare una serie di eventi che farà saltare il ciclo di lettura.
Se non ti ho convito basta immaginare una semplice operazione di I/O su disco di una primitiva di sistema con massima priorità, se dura più di 500ms sei "fritto". (Ho ipotizzato uno scheduler di tipo prioritario ma si può fare lo stesso con uno di time sharing).
A questo punto bisogna verificare se per te il salto di un ciclo di lettura è catastrofico oppure no, ovvero se si sta parlando di processi (nel tuo caso thread) di tipo hard o soft.
Poiché quello che a te interessa è la schedulazione di task periodici di una applicazione real-time, ti consiglio di guardare i seguenti standart per lo sviluppo di applicazioni real-time:
rt-posix
osek
apex
uITRON

Buona lettura.

ciao,
dopo innumerevoli prove so che XP non è nato per il real time però volevo riuscire lo stesso a quantificare i ritardi introdotti.

Il mio vincolo è scrivere su XP

Se ad esempio ho dei bit che cambiano di stato ogni 1,5 secondi anche XP va bene per effettuare tali misurazioni, ma con che grado di precisione forse dico, forse in più o meno 20 millisecondi.

[banryu79]

edit*

[starfred]

Allora considera che prima o poi il worst case si verificherà.
Il mio consiglio è quello di scrivere il programma rispondendo alla domanda:
"se un thread fa una sleep di 2 secondi, cosa succede?"

E poi renderlo immune a questo tipo di eventi gestendo l'eccezione.

Un altro consiglio è quello di utilizzare la temporizzazione (la sleep) su un solo thread e poi (attraverso sezioni critiche/monitor etc. etc.) gestire gli altri di conseguenza.

[misterx]

Originariamente inviato da banryu79

come già detto da gugoXX:

A) quando il thread lettore rileva un tempo di cambiamento di 500 ms significa che è stato risvegliato dalla sleep e quindi ha effettuato la lettura subito dopo che il valore nel dispositivo è stato cambiato (cambia appunto ogni 500 ms).

B) quando invece rileva un tempo di cambiamento di 750 ms (500 + 250) significa che è stato risvegliato dalla sleep appena prima della successiva mutazione del valore nel dispositivo, quindi la leggerà dopo la prossima sleep, tra 250 ms.


Come sopra, nel caso A leggi 500, nel caso B leggi 516 ms anche se al più dovrebbe essere (500 + 5 = 505) per via del discorso che abbiamo fatto in un altro thread circa la granularità del timer di sistema in Windows (o almeno è quello che penso succeda).

scusa ma detto così sembrerebbe che io stia calcolando solo il tempo di mandata in esecuzione dei vari thread e non quello dei vari cambiamenti di stato

[misterx]

Originariamente inviato da starfred

Allora considera che prima o poi il worst case si verificherà.
Il mio consiglio è quello di scrivere il programma rispondendo alla domanda:
"se un thread fa una sleep di 2 secondi, cosa succede?"

E poi renderlo immune a questo tipo di eventi gestendo l'eccezione.

Un altro consiglio è quello di utilizzare la temporizzazione (la sleep) su un solo thread e poi (attraverso sezioni critiche/monitor etc. etc.) gestire gli altri di conseguenza.

tra il secondo ed il terzo ad esempio ho usato un evento, difatti il terzo è legato al secondo da questo.

Tra il primo thread ed il secondo ho usato un semaforo per evitare inconsistenza di dati.

Il mio problema ora sono i tempi che sembrano legati ai vari sleep ed è ciò che vorrei evitare


Comunque credo di aver capito la tua idea: metto un evento anche tra il primo e secondo thread e lascio l'evento tra secondo e terzo così, quando il primo ha riempito l'array risveglia il secondo ed il secondo che lo interpreta se trova delle differenze risveglia il terzo; e tutto viaggia cone velocità settata nel primo

[banryu79]

Originariamente inviato da misterx

scusa ma detto così sembrerebbe che io stia calcolando solo il tempo di mandata in esecuzione dei vari thread e non quello dei vari cambiamenti di stato

Sì infatti.
Tu hai detto che hai introdotto la sleep solo per non occupare la CPU in maniera aggressiva.
Solo che così il thread lettore si atttiva e legge in un attimo restando dormiente (e cieco alle mutazioni nel dispositivo) per ben 250 millisecondi circa ogni volta.

Fai il contrario: il tuo thread lettore farà polling per 250 millis consecutivi per poi andare a nanna per, ad esempio, 20 millis.

[gugoXX]

Originariamente inviato da misterx

scusa ma detto così sembrerebbe che io stia calcolando solo il tempo di mandata in esecuzione dei vari thread e non quello dei vari cambiamenti di stato

Non i tempi di esecuzione, ma la frequenza di campionamento.
Se campioni la porta ogni 500ms, avrai sempre e comunque una speranza di precisione a multipli di 500ms, ma di sicuro non di meno.
Magari il segnale passa da 0 a 1, resta a 1 per 2589 ms e poi torna a zero, ma tu leggendo la porta ogni 500ms penserai che sara' rimasto attivo per 3000ms, se ti va comunque bene. Non hai modo di raggiungere una precisione maggiore se non campionando la porta piu' frequentemente.

Evita di aggiungere altri errori in cascata. Leggi ogni 500ms, salva tutto (anche solo in memoria), e processa in seguito cio' che hai letto.
Questo se non ti serve reagire immediatamente ad un cambio di stato per fare altro ovviamente, il che non e' chiaro.

[misterx]

*edit

[misterx]

Originariamente inviato da banryu79

Sì infatti.
Tu hai detto che hai introdotto la sleep solo per non occupare la CPU in maniera aggressiva.
Solo che così il thread lettore si atttiva e legge in un attimo restando dormiente (e cieco alle mutazioni nel dispositivo) per ben 250 millisecondi circa ogni volta.

Fai il contrario: il tuo thread lettore farà polling per 250 millis consecutivi per poi andare a nanna per, ad esempio, 20 millis.

però scusa,
se creassi io un thread che cambia un bit ogni 500 ms e volessi testare con un altro thread ogni quanto varia tale bit e trovassi sempre 500 ms cosa implicherebbe?

[starfred]

La parola sempre è un po' azzardata. Come si può intendere sempre?
1 minuto? 1 ora? 1 giorno? E' troppo relativo. Questo tipo di programmazione deve essere corretto dal punto di vista teorico.
Bisogna sempre ricondursi al worst case (che prima o poi si verificherà) e gestire il sistema di conseguenza.
Prova ad immaginare un sistema con 3 thread che eseguono questa operazione per 1000 volte:
TH1: Sleep(10); signal(TH2); wait();
TH2: Sleep(10); signal(TH3); wait();
TH3: Sleep(10); signal(TH1); wait();

Segnati l'orario di inizio e fine rimarrai molto sorpreso dal risultato