Home
Accesso / Registrazione
 di 

FIFO (First In First Out) - Gestire le code

FIFO

First In, First Out (FIFO) Queue e' una organizzazione cronologica astratta di dati. Le code (queue) sono considerate insopportabili, una perdita di tempo, anche quando si aspetta al cinema per vedere un film, quando si aspetta in banca per ritirare un assegno. Le code di cui parleremo in seguito non sono una perdita di tempo, ma, al contrario, ci risparmieranno un sacco di tempo (e qualche mal di testa) in alcuni tipi di applicazioni.

Le code First In, First Out (FIFO) possono essere descritte come: chi prima arriva, per primo viene servito, chi arriva dopo attende che il primo abbia finito.

Ma di cosa stiamo parlando? Cosa è la FIFO?

Nei sistemi embedded spesso dati sono resi disponibili dal mondo esterno per essere manipolati dal firmware.
A seconda delle richieste e capacita' del sistema, i dati possono, o piu' verosibilmente devono, essere processati appena resi disponibili. In altri casi, specialmente per certe periferiche, possono, o devono, essere processati in un secondo tempo, quindi con molta calma.
Prendiamo in considerazione il secondo caso.
Allora il problema da affrontare e': una sorgente esterna fornisce i dati, non li voglio perdere, d'altra parte li processero' quando la mia applicazione lo riterra' necessario.

First in First Out (FIFO) - concetto base

Il concetto base e' First In First Out, alias FIFO come una coda all'ufficio postale, dove il Sig. Rossi e' in fila dalle 8:00, Il Sig. Verdi dalle 8:01, e la Sig.ra Bianchi dalle 8:02, allo stesso sportello. L'impiegato, il cui turno incomincia alle 8:05, servira' prima il Sig. Rossi, quindi il Sig. Verdi, ed in ultimo la Sig.ra Bianchi. L'ordine di servizio rispetta l'ordine di arrivo.
Noi cercheremo di implementare questo sistema nel nostro software.
L'idea di partenza e' di creare una area di memoria di immagazinamento temporaneo dei dati di ingresso, e delle funzioni per scrivere e leggere dati in questa area (generalmente chiamata buffer).
Diamo uno sguardo al seguente diagramma

Coda Inizializzata

Abbiamo assunto un area di 8 locazioni (un vettore base 0 a 8 elementi chiamato Buffer) senza specificare il tipo dei dati contenuti.
Abbiamo anche dichiarato tre variabili : writePosQ, readPosQ, countItemQ, tutte inizializzate a zero.
Questo layout identifica il prototipo di coda.
All'inizio la coda e' vuota, e possiamo identificare questo stato osservando:

  1. countItemQ e' pari a zero.
  2. writePosQ e uguale a readPosQ.

Bene, teniamo a mente le precedenti osservazioni, ne faremo uso dopo.
Supponiamo ora che un evento esterno renda disponibile il dato "X", e che lo si voglia inserire nella coda, chiamiamo quindi la funzione insertDataQueue() di seguito descritta passo passo :

  1. Scrivi "X" nell'elemento Buffer[writePosQ], poiche' writePosQ vale zero questo equivale a Buffer[0]="X".
  2. Incrementa writePosQ.
  3. Incrementa countItemQ.

Il diagramma seguente mostra la coda dopo la prima insersione.

Coda, Primo Elemento Inserito

Supponiamo che un ulteriore evento renda disponibile il dato "Y", e lo si voglia inserire nella coda:

  1. Scrivi "Y" nell'elemento Buffer[writePosQ], poiche' writePosQ vale 1 cio' equivale a Buffer[1]="Y".
  2. Incrementa writePosQ.
  3. Incrementa countItemQ..

Il diagramma seguente mostra la coda dopo la seconda inserzione:

Coda, Secondo Elemento Inserito

Fermiamoci qui per quanto riguarda l'inserzione di dati, passiamo alla estrazione, ma torneremo qui in seguito, avendo lasciato aperte alcune questioni.
Nel frattempo la nostra applicazione vuole sapere se ci sono dati disponibili.
Possiamo quindi pensare ad una funzione che ritorni lo stato della coda, chiamiamola isQueueEmpty.

"isQueueEmpty restituisce true se la coda e' vuota, false altrimenti".

Qualche riga fa, abbiamo notato che una coda e' vuota quando countItemQ vale zero.
Perche' non riscrivere la precedente definizione nel modo seguente ?

"isQueueEmpty restituisce true se countItemQ vale zero, false altrimenti".

Fino a qui ci siamo.
Adesso vogliamo estrarre un elemento dalla nostra coda con la funzione extractDataQueue() di seguito descritta passo passo:

  1. Restituisci l'elemento Buffer[readPosQ], poiche' readPosQ vale zero cio' equivale a restituire Buffer[0].
  2. Incrementa readPosQ.
  3. Decrementa countItemQ.

Il seguente diagramma mostra lo stato della coda dopo la prima estrazione:

Coda, Primo Elemento Estratto

Siccome la coda non e' ancora vuota (ce lo dice isQueueEmpty()),vogliamo estrarre un ulteriore elemento chiamando di nuovo extractDataQueue() :
Come dalla precedente spiegazione :

  1. Restituisci l'elemento Buffer[readPosQ], poiche' readPosQ vale 1 cio' equivale a restituire Buffer[1].
  2. Incrementa readPosQ.
  3. Decrementa countItemQ..

Il seguente diagramma mostra lo stato della coda dopo la seconda estrazione :

Coda, Secondo Elemento Estratto

Chiamando di nuovo isQueueEmpty() questa ci restituisce True, quindi possiamo andare avanti con altri compiti.
Sembra semplice da implementare, e a noi piacciono le cose semplici.....

Nel seguente sorgente C e' mostrata una prima implementazione di queste funzioni, dove si assume che i dati siano chars da una porta seriale.

//	Imposta la massima lunghezza della coda
#define	MAXQUEUELEN		8
#define	QUEUEMASK		MAXQUEUELEN-1

//	Dechiara variabili di coda
int writePosQ=0, readPosQ=0, countItemQ=0;
char Buffer[MAXQUEUELEN];

//	Restituisce TRUE se la coda e' vuota
int isQueueEmpty()
{
int retval=TRUE;

	if(countItemQ!=0)
	{
		retval=FALSE;
	}
	return retval;

}

//	Inserisce un nuovo elemento nella coda
void insertDataQueue(char d)
{
	//	Controlla che la coda non sia piena
	if(countItemQ!=MAXQUEUELEN)
	{
		//	C'e' ancora spazio per i dati
		Buffer[writePosQ]=d;
		//	Sposta il puntatore alla locazione successiva
		writePosQ++;
		//	Rendilo Circolare
		writePosQ&=QUEUEMASK;
		//	Un elemento in piu', contalo.
		countItemQ++;
	}
}Primo

//	Estrae un nuovo elemento dalla coda.
//	Assumiamo di aver gia controllato lo stato della coda e verificato la disponibilita' di dati.
//	Quindi non vengono fatti ulteriori controlli.
char extractDataQueue(void)
{
char retval='\0';

	retval=Buffer[readPosQ];
	//	Sposta il puntatore alla locazione successiva
	readPosQ++;
	//	Rendilo Circolare
	readPosQ&=QUEUEMASK;
	//	Un elemento in meno, contalo
	countItemQ--;
	return retval;
}

Osservando il codice possiamo vedere che abbiamo affrontato due problemi prima lasciati aperti :

  1. Circular Array
  2. Buffer Overrun
  • Cosa devo fare quando uno dei due puntatori (writePosQ, readPosQ) raggiunge la fine del buffer array ?

Semplice, lo impostiamo all'inizio del buffer stesso. Come un cane che si morde la coda... questo tipo di struttura viene chiamata circular array. Questa operazione di riposizionamento e' fatta con un bitwise AND (&).
Questo metodo e' conveniente in termini di velocita' perche' i bitwise AND sono veloci.
Cio' d'altro canto obbliga il programmataore ad utilizzare per MAXQUEUELEN potenze di 2 (1,2,4,8,16,32,64,128,256,512....), e non sempre la RAM disponibile e' molta...
Se la RAM (e non la velocita0 e' un problemaallora possiamo usare dimensioni di MAXQUEUELEN che sono il giusto equilibrio fra RAM disponibile e prestazioni del sistema. In questo caso dobbiamo riscrivere il codice nel modo seguente:

	//	Rendilo Circolare
	if(readPosQ==MAXQUEUELEN)
	{
		readPosQ=0;	
	}
  • E se il processo che estrae i dati e' piu' lento di quello che li inserisce? Per questo tipo di errore chiamato buffer overrun abbiamo due scelte :
  1. Perdiamo tutti i dati in ingresso eccedenti la capacita del buffer, i dati gia' immagazzinati non vengono sovrascritti.
  2. Sovrascriviamo l'ultima locazione del buffer con i dati in eccedenza.

Quale delle due opzioni dovremmo adottare ?
La prima per me ha piu' senso (il codice scritto segue questa linea..), ma potrebbero esserci casi dove la scelta numero 2 sia piu' conveniente.
Di fatto se c'e errore di buffer overrun, dobbiamo seriamente considerare di riprendere le specifiche di progetto, rianalizzare le capacita' del sistema e ridimensionare opportunamente il buffer ....

Segue un esempio di utilizzo:

void main(void)
{

	while(1)
	{
		................
		................

		//	Ci sono dati disponibili ?
		if(EXERNALDATAAVAILABLE)
		{
			data=READPORT();
			insertDataQueue(data);
		}

		................
		................



		while(!isQueeueEmpty())
		{
			//	Estrai e processa i dati
			mean=extractDataQueue();
			//	Fai cio' che vuoi
			................
			................
			................
			................
		}

	}
}

Sebbene il codice sia scritto in C, si puo' facilmente implementare in altri linguaggi ad alto livello, per effettuare delle prove sul vostro PC.

Comunque, prendente nota delle seguenti assunzioni :

  • Il programma gestisce una sola coda. Il codice non e' ottimizzato per gestire piu' code.
  • Accesso al Buffer non e' concorrente, cioe' mentre si esegue una estrazione non e' permesso eseguire insersioni e viceversa. Questo significa che l'utilizzo di questo codice "as it is" in una applicazione che utilizza code in ISR, o in RTOS la gatta da pelare diventa estremamente grossa e vivace.

Pensandoci bene, forse potrei affrontare questi due problemi in un prossimo articolo....
Nel frattempo, divertitevi.

 

 

Scrivi un commento all'articolo esprimendo la tua opinione sul tema, chiedendo eventuali spiegazioni e/o approfondimenti e contribuendo allo sviluppo dell'argomento proposto. Verranno accettati solo commenti a tema con l'argomento dell'articolo stesso. Commenti NON a tema dovranno essere necessariamente inseriti nel Forum creando un "nuovo argomento di discussione". Per commentare devi accedere al Blog

 

 

Login   
 Twitter Facebook LinkedIn Youtube Google RSS

Chi è online

Ci sono attualmente 0 utenti e 46 visitatori collegati.

Ultimi Commenti