Teoria delle code: differenze tra le versioni

Versione delle 20:34, 17 mar 2008

Versione attuale delle 15:08, 14 dic 2023

(94 versioni intermedie di 58 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 andata in onda lunedì 17 marzo a " Chi vuol essere milionario "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/υ.

==Curiosità==

Wikipedia, e nel dettaglio questa pagina, è stata citata nel programma televisivo [[Chi vuol essere milionario?]], come aiuto da casa da parte del concorrente.

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.

[[Categoria:Complessità computazionale]]

[[Categoria:Computazioni]]

[[Categoria:Ricerca operativa]]

[[Categoria:Statistica]]

== Voci correlate ==

[[de:Warteschlangentheorie]]

* [[Traffico (telecomunicazioni)]]

[[en:Queueing theory]]

* [[Coda M/M/1]]

[[es:Teoría de colas]]

* [[Coda (informatica)|Coda]]

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

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

== Altri progetti ==

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

{{interprogetto|preposizione=sulla}}

[[nl:Wachtrijtheorie]]

[[pl:Teoria kolejek]]

== Collegamenti esterni ==

[[pt:Teoria das filas]]

* {{Collegamenti esterni}}

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

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

[[zh:等候理論]]

* [{{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]]