ALGORITMI SULLE CODE: LA TEORIA
In informatica con il termine coda si intende una struttura dati di tipo FIFO, First In First Out (il primo in ingresso è il primo ad uscire).
Un esempio pratico sono le code che si fanno per ottenere un servizio, come pagare al supermercato o farsi tagliare i capelli dal parrucchiere: idealmente si viene serviti nello stesso ordine con cui ci si è presentati. Questo è esattamente il funzionamento di una coda FIFO.
Questo tipo di struttura dati è molto utilizzata in informatica, ad esempio nella gestione delle operazioni da eseguire da parte di un sistema operativo (scheduler), ed è fondamentale nelle telecomunicazioni, in particolare nelle reti a commutazione di pacchetto, dove descrive la gestione dei pacchetti in attesa di essere trasmessi su un collegamento da un server verso un client. Le proprietà matematico-statistiche delle code sono studiate nella teoria delle code.
First In, First Out (FIFO) Queue è una organizzazione cronologica astratta di dati. Le code (queue) sono quotidianamente considerate una perdita di tempo, come quando si aspetta al cinema per vedere un film o in banca per ritirare un assegno. Ma un’organizzazione a code permette complessivamente una maggiore efficienza poiché riduce i tempi d’attesa dei singoli clienti per l’esecuzione di un programma, accontentando così un maggior numero di persone. 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. Esse sono anche chiamate FiFs (first input, first served), FiFo (first input, first output) o FcFs (first come, first served).
ESEMPIO E GRAFICO FIFO
Selezioniamo ad esempio 16 time frame, “segmenti” di tempo T misurati in unità di lavoro ul.
T1= 1 ul T2= 3 ul T3= 2 ul T4= 1 ul T5= 4 ul T6= 3 ul T7= 2 ul T8= 1 ul T9= 2 ul T10= 4 ul T11= 2 ul T12= 3 ul T13= 4 ul T14= 1 ul T15= 2 ul T16= 3 ul
Possiamo calcolare i tempi medi d’attesa per ciascuna T ed un tempo totale Ttot grazie al quale è calcolabile il tempo medio totale. Possiamo dunque disegnare il grafico.
T1= 0 T2= 1 T3= 1+3=4 T4= 4+2=6 T5= 6+1=7 T6= 7+4=11 T7= 11+3=14 T8= 14+2=16 T9= 16+1=17 T10= 17+2=19 T11= 19+4=23 T12= 23+2=25 T13= 25+3=28 T14= 28+4=32 T15= 32+1=33 T16= 33+2=35
Ttot= 271 per cui Tmedio= 271/16= 17
ESEMPIO E GRAFICO LWFG
Possiamo quindi fare la stessa cosa con un altro metodo: LWFG. Questo algoritmo come quello precedente è definito algoritmo sulle code ma grazie ad esso i tempi medi di attesa si riducono ulteriormente, permettendo di accontentare più persone in minor tempo motivo per cui è algoritmo utilizzato da Amazon. Esso esegue i programmi non in ordine di arrivo; il primo ad essere eseguito è il task con meno unità di lavoro e poi vengono eseguiti gli altri procedendo in ordine crescente di unità di lavoro. Per verificare l’effettiva riduzione dei tempi di attesa con il metodo LWFG abbiamo calcolato il tempo di attesa medio.
Possiamo dunque disegnare il grafico.
T1= 0 T4= 1 T8= 1+1=2 T14= 2+1=3 T3=3+1=4 T7=4+2=6 T9=6+2=8 T11= 8+2=10 T15=10+2=12 T2=12+2=13 T6= 14+3=17 T12= 17+3=20 T16=20+3=23 T5=23+3=26 T10=26+4=30 T13=30+4=34
Ttot= 210 per cui Tmedio= 210/16= 13
