FIFO Buffer

Lezione del 20189-01-10.

Da qui vedremo tre diversi modi per implementare un buffer. Per riferimento si può consultare [CODV2001].

Fissiamo le seguenti specifiche:

  • capacità del buffer: \((N > 0) + 2\) (il +2 ci serve per semplificare il calcolo degli indici);
  • il set dei dati memorizzabili è \(V = \{ 0, 1 \}\) [1];
  • le stringhe sono sequenze di bit: \(s, t, u, v \cdots \in V^*\);
  • la lunghezza di una stringa s si indica con \(\lvert s \rvert\), dove per lunghezza si intende il numero di elementi che formano la stringa [2];

FIFO buffer: software architecture

Un buffer FIFO (acronimo di First In First Out) è alimentato da un produttore esterno (source), ed alimenta un consumatore esterno (destination).

I dati oggetto del trattamento sono gestiti secondo una coda organizzata in modo che il dato entrato temporalmente per primo sia anche il primo ad uscire.

Avremo la seguente architettura:

_images/fifo.svg

dove fifo(s) ci indica che abbiamo una capacità di memorizzazione tale tale da poter registrare la stringa s.

Inizialmente avremo fifo(s) vuota; ovvero avremo memorizzato la stringa vuota (\(\epsilon\)) nel corpo del buffer.

La definizione di fifo(s) può essere la seguente.

Inizialmente, per buffer vuoto, è possibile solo l’input di un dato: zero o uno; abbiamo una non deterministic composition:

\[s = \epsilon, \; fifo(s) = in(0) \cdot fifo(0) + in(1) \cdot fifo(1) = \sum_{e \in V}in(e) \cdot fifo(e)\]

Quando il buffer è impegnato parzialmente, potremo eseguire sia input che output. Diciamo che il nostro buffer è composto \(s = e \, s'\), cioè la stringa s ha il dato e in testa, e la coda è \(s'\), come indicato nella seguente rappresentazione grafica:

_images/fifo_2.svg

Avremo:

\[0 < \lvert s \rvert < N+2, s = e \, s', \; fifo(s) = \sum_{e \in V}in(e) \cdot fifo(s \, e) + out(e) \cdot fifo(s')\]

ovvero possiamo inserire in coda un nuovo dato e, per poi passare la fifo nello stato \(s \, e\); oppure possiamo ricevere il dato e dalla testa di s, passando la fifo allo stato \(s'\).

Rimane da considerare il caso di buffer pieno: \(\lvert s \rvert = N+2\). Qui l’unica azione possibile è la ricezione del dato; l’input è vietato perché il buffer pieno. Se, come nel caso precedente, il buffer è composto da \(s = e \, s'\), abbiamo:

\[\lvert s \rvert = N+2, s = e \, s', \; fifo(s) = out(e) \cdot fifo(s')\]

Se le azioni deposit e withdraw dell'implementazione sequenziale del producer-consumer avessero un valore associato, questa implementazione sarebbe bisimilar equivalent a quella del producer-consumer.

Un esempio di interazione può essere il seguente:

action   in(0) in(1) in(1) out(0) out(1) out(1)
state \(\epsilon\) 0 01 011 11 1 \(\epsilon\)

La prima colonna della tabella identifica cosa è nelle celle seguenti della riga.

La seconda colonna riporta lo stato iniziale del buffer: vuoto (stringa nulla: \(\epsilon\)).

Dalla terza colonna in poi sono indicate nella prima riga le azioni, nella seconda riga il relativo stato del buffer in conseguenza dell’azione.


[1]Questa è una semplificazione. Possiamo pensare di memorizzare qualunque tipo di informazione di dimensione finita.
[2]

Per induzione:

\[\begin{split}\lvert s \rvert = \begin{cases} 0 \quad & \, se \, s = \epsilon, \; \text{stringa nulla} \\ 1+\lvert s' \rvert \quad & \, se \, s = a\,s', \; a \in V \end{cases}\end{split}\]