Teoria delle code: differenze tra le versioni

Versione delle 20:36, 17 mar 2008

Versione attuale delle 15:08, 14 dic 2023

(93 versioni intermedie di 57 utenti non mostrate)

Riga 1:

[[File:Teoria_de_colas.svg|thumb|Schema di un sistema a coda, con clienti, serventi, code di attesa e flussi di traffico in ingresso e uscita]]

{{S}}

La '''teoria delle code''' è lo studio [[matematica|matematico]] delle linee di attesa (o [[Coda (informatica)|code]]) e di vari processi correlati, comequali l'arrivoil alla fineprocesso di unaarrivo in coda, l'attesa (essenzialmente un processo di immagazzinamento) e l'essereil servitoprocesso all'inizio delladi codaservizio. Può essere applicata neiad un'ampia varietà di problemi, soprattutto nel campo dei [[Trasportitrasporti]], delle [[telecomunicazioni]], della fornitura di servizi (argomenti)ad es. in [[Sistema sanitario|trasportisanità]]) e nelledelle [[telecomunicazionioperations|operazioni]]; occasionalmente[[azienda]]li. èUsualmente collegataconsiderata allauna branca della [[Ridericerca theoryoperativa]], le sue origini risalgono al [[1909]] quando l'ingegnere [[Danimarca|danese]] [[Agner Krarup Erlang]] pubblicò un articolo intitolato ''The theory of probability and telephone conversations'' relativo alle attese nelle chiamate telefoniche.

==Descrizione==

La prima pubblicazione sulla teoria delle code è del [[1909]] dell'ingegnere [[Danimarca|danese]] [[Agner Krarup Erlang]].

=== Notazione di Kendall ===

[[File:Exponential_pdf.svg|thumb|[[Distribuzione esponenziale|Distribuzione esponenziale negativa]]]]

[[File:Degenerate_distribution_PMF.png|thumb|[[Distribuzione degenere]]]]

[[File:Gamma_distribution_pdf.svg|thumb|[[variabile casuale Erlanghiana|Distribuzione di Erlang]]]]

Nel [[1953]], [[David_George_Kendall|David G.George Kendall]] introdusse la notazione '''A/B/C''', successivamente estesa come '''1/2/3/(4/5/6)''' nellaal qualefine idi numerifornire sonouna sostituitidescrizione conimmediata quantodel segue.modello del sistema a code:

# Un codice che descrive illa processodistribuzione di probabilità dei tempi di arrivo dei ''jobs'' nel sistema; i codici più usati sono:

Nel [[1953]], [[David_George_Kendall|David G. Kendall]] introdusse la notazione '''A/B/C''', successivamente estesa come '''1/2/3/(4/5/6)''' nella quale i numeri sono sostituiti con quanto segue.

#* '''"M''' " per "di Markov", implicante una [[variabile casuale esponenziale negativa|distribuzione esponenziale negativa]] unilatera per i tempi di servizio o tra gli arrivi: ciò implica l'[[mancanza di memoria|assenza di memoria]] di questi ultimi;

#* '''"D'''" per [[variabile casuale degenere|distribuzione "degenere"]] o "deterministica" dei tempi di servizio;

#* '''Ek'''"E<math>_k</math>" per una [[variabile casuale Erlanghiana|distribuzione di Erlang]] con <math>k</math> come parametro di forma;

#* '''"G'''" per una distribuzione "Generalegenerale".

# Un codice simile che rappresenta illa processodistribuzione di probabilità dei tempi di servizio dei ''jobs'', usando gli stessi simboli precedenti.

# Il numero di canali di servizio, detti anche ''serventi'', o ''server'' (ad esempio gli sportelli alla posta).

# Le dimensioni massime del sistema:, ilche massimocorrisponde numeroalla disomma clientitra permessii nel''jobs'' sistemain compresicoda coloroe chei vengono''jobs'' servitinei canali di attualmenteservizio; quando questoil massimo viene raggiunto ulteriori arrivi vengono rifiutati. Se non indicata la dimensione si intende infinita.

# Le dimensioni della fonte di arrivi: le dimensioni della popolazione da cui possono arrivare i clienti; questo limita il ritmo di arrivi, tanti più ''jobs'' sono presenti nella coda tanti meno ne sono disponibili per entrare nel sistema. Se non indicata la dimensione si intende infinita.

# L'ordine dicon priorità nelil quale sono serviti i ''jobs'' nella coda (per default è FIFO):

#* First Come First Served ('''FCFS''') (o First In First Out - [[FIFO]]) (il primo che arriva viene servito per primo);

#* Last Come First Served ('''LCFS''') (o Last In First Out - [[LIFO]]) (l'ultimo che arriva viene servito per primo);

#* Service In Random Order ('''SIRO''') (servizio in ordine casuale).;

#* PRI (esiste un sistema di selezione degli utenti a priorità (un esempio è il pronto soccorso, con i codici bianco, verde e rosso).

I modelli più studiati sono i sistemi M/M/<math>S</math>/<math>K</math>, con <math>S</math> e <math>K</math> che possono assumere diversi valori (il modello più semplice è l'[[Coda M/M/1|M/M/1]], con un servente e a capacità illimitata): questo perché la distribuzione esponenziale degli intertempi di arrivo e di servizio permette di studiare i sistemi a coda come dei [[processo di nascita e morte|processi di nascita e morte]].

#Un codice che descrive il processo di arrivo; i codici usati sono:

#* '''M''' per "di Markov", implicante una distribuzione esponenziale negativa unilatera per i tempi di servizio o tra gli arrivi: ciò implica l'assenza di memoria di questi ultimi;

#* '''D''' per distribuzione "degenere" o "deterministica" dei tempi di servizio;

#* '''Ek''' per una [[variabile casuale Erlanghiana|distribuzione di Erlang]] con k come parametro di forma;

#* '''G''' per una distribuzione "Generale".

#Un codice simile che rappresenta il processo di servizio, usando gli stessi simboli.

#Il numero di canali di servizio.

#Le dimensioni massime del sistema: il massimo numero di clienti permessi nel sistema compresi coloro che vengono serviti attualmente; quando questo massimo viene raggiunto ulteriori arrivi vengono rifiutati.

#Le dimensioni della fonte di arrivi: le dimensioni della popolazione da cui possono arrivare i clienti; questo limita il ritmo di arrivi, tanti più ''jobs'' sono presenti nella coda tanti meno ne sono disponibili per entrare nel sistema.

#L'ordine di priorità nel quale sono serviti i ''jobs'' nella coda:

#* First Come First Served ('''FCFS''') (o First In First Out - [[FIFO]]) (il primo che arriva viene servito per primo);

#* Last Come First Served ('''LCFS''') (o Last In First Out - [[LIFO]]) (l'ultimo che arriva viene servito per primo);

#* Service In Random Order ('''SIRO''') (servizio in ordine casuale).

=== Sistemi a coda e teoria del traffico ===

==Curiosità==

{{vedi anche|Traffico (telecomunicazioni)}}

Nella puntata di "Chi vuol essere milionario?" andata in onda lunedì 17 marzo 2008 fu chiesto, in una domanda da 15 mila euro,a che cosa riguardasse la teorie delle code. C'è da considerare che la Teoria delle Code è uno dei campi più importanti in Informatica e modellizza le strutture per la gestione di processi concorrenti e la soluzione delle relative problematiche.

[[File:FIFO-LIFO.svg|thumb|Confronto tra tecnica FIFO e LIFO.]]

[[File:Mminfinity-statespace.svg|thumb|upright=1.0|[[Catene di Markov]] per sistemi a coda con stati, transizione di stati e relative probabilità, usata per la modellazione dei sistemi a coda]]

I sistemi a coda sono modellizzabili tramite [[processo markoviano|catene di Markov]] a tempo continuo ossia con [[sistema dinamico|sistemi dinamici]] caratterizzati da <math>N</math> stati, probabilità di stato <math>P(N_i)</math> e [[probabilità di transizione]] da uno stato a un altro uguale al prodotto tra la frequenza di transizione <math>f</math> e l'intervallo di tempo <math>dt,</math> dipendente solo dallo stato presente del sistema e non da quelli precedenti (sistema senza memoria). Lo stato rappresenta la situazione in cui si trova il sistema rispetto a variabili prese come riferimento (in linea di massima non univoche) e l'evoluzione del sistema è mappata con una sequenza di salti fra gli stati stessi. Note le frequenze di transizione, ossia la probabilità di transizione di stato, è possibile derivare le probabilità di stato <math>P(S_i)</math> risolvendo la catena di Markov; dalla conoscenza di queste probabilità si possono poi derivare i parametri prestazionali di interesse quali il traffico smaltito, la probabilità di rifiuto, il tempo di coda, ecc…

Definendo il flusso proveniente dallo stato <math>i</math>-esimo verso lo stato <math>k</math>-esimo come il prodotto <math>P(S_k)\cdot q_k,</math> tra la probabilità di stato in <math>k</math> e la frequenza di transizione verso lo stato <math>k,</math> per il calcolo della probabilità di stato si utilizza la condizione espressa dalla [[legge di conservazione]] dei flussi la quale afferma che la somma dei flussi entranti è uguale alla somma dei flussi uscenti da uno stato. Applicando tale principio ad ogni stato si ottiene un sistema di <math>S</math> equazioni in <math>S</math> incognite (le probabilità di stato) tante quante gli stati <math>S;</math> le equazioni non sono tutte indipendenti tra loro, quindi la soluzione del sistema è impossibile (determinante nullo) a meno di sostituire un'equazione con la somma delle probabilità degli stati pari ad uno.

==Collegamenti esterni==

* http://www2.uwindsor.ca/~hlynka/queue.html

* [http://jmt.sourceforge.net Java Modelling Tools - Una suite GPL per la risoluzione di modelli a reti di code e per studi di performance]

Un tipo di catene di Markov sono le catene di nascita e morte dove sono ammesse transizioni solo tra strati "adiacenti" e per i quali è identificabile una linea di taglio di flusso. Un sistema a coda è detto Markoviano se è modellabile tramite una catena di Markov di nascita e morte con processo di arrivo e di servizio di tipo [[esponenziale]] negativo di parametri λ (nascita) e υ (morte) e valori attesi corrispondentemente pari a 1/λ e 1/υ.

[[Categoria:Complessità computazionale]]

[[Categoria:Computazioni]]

[[Categoria:Ricerca operativa]]

[[Categoria:Statistica]]

In un sistema con <math>S</math> serventi diventa fondamentale un parametro prestazionale detto probabilità di blocco, che dipende dal numero <math>S</math> di serventi e dal traffico offerto <math>A</math> in ingresso. Tale parametro si calcola facendo riferimento alla [[formula di Erlang B]] i cui valori, per <math>S</math> e <math>A</math> fissati, sono espressi in forma tabulata. Altrettanto di interesse è la probabilità di attesa in coda espressa in funzione del numero di serventi e del traffico offerto attraverso la [[formula di Erlang C]]. In una [[rete di telecomunicazione]] i sistemi a coda e i relativi problemi di gestione del traffico sono presenti all'interno dello ''stack'' protocollare dei sistemi di elaborazione, trasmissione e ricezione del flusso informativo ossia i terminali [[host]] e i sottosistemi interni di commutazione ([[router]]) e più in generale in tutti gli [[apparato di rete|apparati di rete]] che presentano del traffico in ingresso.

[[de:Warteschlangentheorie]]

[[en:Queueing theory]]

== Voci correlate ==

[[es:Teoría de colas]]

* [[Traffico (telecomunicazioni)]]

[[fr:Théorie des files d'attente]]

* [[Coda M/M/1]]

[[ja:待ち行列理論]]

* [[Coda (informatica)|Coda]]

[[ko:대기행렬이론]]

[[nl:Wachtrijtheorie]]

== Altri progetti ==

[[pl:Teoria kolejek]]

{{interprogetto|preposizione=sulla}}

[[pt:Teoria das filas]]

[[ru:Теория массового обслуживания]]

== Collegamenti esterni ==

[[zh:等候理論]]

* {{Collegamenti esterni}}

* http://www2web2.uwindsor.ca/~math/hlynka/queue.html

* [{{cita web|http://jmt.sourceforge.net |Java Modelling Tools - Una suite GPL per la risoluzione di modelli a reti di code e per studi di performance]}}

{{Controllo di autorità}}

{{portale|ingegneria|matematica|telematica}}

[[Categoria:Teorie delle telecomunicazioni]]

[[Categoria:ComputazioniTeorie di rete]]

[[Categoria:ComplessitàTeoria della complessità computazionale]]

[[Categoria:Ricerca operativa]]

[[Categoria:StatisticaProcessi stocastici]]