[PDF] Files dattente 30 oct. 2018 — File M/

View - Download Files dattente

Previous PDF

Next PDF

Files d'attente

Anas Vergne et Celine Comte

30 octobre 2018

1 Introduction

Notation de Kendall

A=B=C[=D=E]

AProcessus d'arrivee des clients dans la le

MpourMarkovianoumemoryless, correspondant a un processus d'arrivee Poisson,Dpourdeterminist,

Gpourgenerally distributed.

BDistribution du temps de service

MpourMarkovianoumemoryless, correspondant a un temps de service distribue selon la loi exponen- tielle,Dpourdeterminist,G(ouGI) pourgenerally distributed(etindependent).

CNombre de serveurs

DNombre de places dans la le, en comptant les clients en service sur un serveur

Valeur par defaut :1.

EDiscipline de service

FIFO pourrst-in, rst-out(premier arrive, premier servi), LIFO pourlast-in, rst-out(qui peut ^etre preemptif ou non), PS pourprocessor-sharing.

Valeur par default : FIFO.

Dans ce cours, on suppose que les temps d'inter-arrivee des clients successifs sont independants et identi-

quement distribues. De m^eme, on suppose que le temps de service d'un client est independant du temps de

service d'un autre client. ExemplesOn se contente de deux exemples qui seront revus plus tard dans le cours.

File M/M/1/ 1/PS

MProcessus d'arrivee : Poisson de parametre >0.

MDistribution du temps de service :

exponentielle de parametre >0.

1/11 serveur, une innite de places dans la le.

PSDiscipline de service processor-sharing.x= 3

File M/M/3[/ 1/FIFO]

MProcessus d'arrivee : Poisson de parametre >0.

MDistribution du temps de service :

exponentielle de parametre >0.

3/13 serveurs, une innite de places dans la le.

FIFODiscipline de service rst-in, rst-out.x= 4

1

2 La le M/M/1

Modele

MLes clients arrivent selon un processus de Poisson de parametre >0. MLe temps de service de chaque client suit une loi exponentielle de parametre >0 (et est independant du temps de service des autres clients).

1/1Un seul serveur, une innite de places dans la le.

FIFODiscipline de service rst-in, rst-out.

La charge de la le est notee=

. C'est une grandeur sans unite, exprimee enErlang. On suppose dans la

suite que <1. Cette condition va s'averer necessaire et susante pour garantir la stabilite de la le. On

suppose de plus que la discipline de service est FIFO, m^eme si la plupart des resultats sont valables pour

d'autres disciplines de service.x= 3 (a) File M/M/1/1/FIFOx= 3 (b) File M/M/1/1/PS Figure1 { Representation d'une le M/M/1 sous plusieurs disciplines de service Etat de la lePour chaquet2R+, on noteXtla variable aleatoire qui compte le nombre de clients dans la le a l'instantt. On suppose que la le est vide a l'instant 0, c'est-a-dire queX0= 0. (Xt)t0est un processus de Markov homogene surN. Plus precisement, (Xt)t0est un processus de naissance et de mort dont le taux de naissance est constant egal aet le taux de mort est constant egal a.

On peut construire une realisation du processus pas-a-pas (sur un intervalle de temps ni) en tirant, pour

chaque instanttou se produit une transition, le temps avant la prochaine transition et son type (arrivee ou

depart d'un client) : Si Xt= 0, alors la prochaine arrivee se produit apres un tempsExp(). Si Xt>0, alors la prochaine arrivee se produit apres un tempsExp() et le prochain depart se produit apres un tempsExp(). De facon equivalente, !le prochain evenement se produit apres un tempsExp(+); !independamment du temps qui s'est ecoule, il s'agit d'une arrivee avec probabilite+et d'un depart avec probabilite +.012::: (a) Diagramme de transition (+)3 7

7777752

6

666664A=(b) Generateur innitesimal (les entrees vides valent 0)

Figure2 { Processus de Markov decrivant l'etat de la le M/M/1 representee en Figure 1 2 Distribution stationnaireOn cherche les mesures, denies surN, qui sont solutions de l'equation matricielleA= 0, ouAest le generateur innitesimal du processus (Xt)t0, rappele enFigure2b. Cela revient a resoudre le systeme d'equations : (0) +(1) = 0; (i1)(+)(i) +(i+ 1) = 0;8i1: On peut remarquer que les deux premieres equations (0) +(1) = 0 et(0)(+)(1) +(2) = 0; impliquent que (1) +(2) = 0: En injectant cette egalite dans l'equation obtenue pouri= 2, on obtient (2) +(3) = 0: En raisonnant par recurrence suri1, on peut ainsi montrer que le systeme ci-dessus est equivalent a (i1) +(i) = 0;8i1:

On deduit directement que(i) =(0)(

)i=(0)ipour chaquei2N. On obtient la valeur de(0) par normalisation (en utilisant le fait que <1) : 1 = X i2N(i) =(0)X i2N i=(0)11; d'ou(0) = 1et(i) = (1)ipour chaquei2N. La distribution stationnaire de l'etat d'une le M/M/1 de chargeest doncgeometriquede parametre. On peut remarquer que cette distribution stationnaire ne depend que du rapport= , et pas des valeurs exactes deet de. Augmenter ou diminuer ces quantites en gardant leur rapport constant revient a \accelerer"

ou a \ralentir" l'evolution de la le, mais n'a pas d'impact sur son comportement a l'etat stationnaire.

Dans la suite, on noteXune variable aleatoire de distribution. On s'interesse au comportement de la le

lorsqu'elle est a l'etat stationnaire. Loi de conservationLa probabilite qu'il y ait au moins un client dans la le est donnee par

P(X1) =X

i1(i) = 1(0) = 1(1) =:

La chargedonne donc la probabilite que le serveur soit actif (a un instant donne). Par ergodicite, c'est

aussi la fraction du temps ou le serveur est actif. Remarquons que l'on peut reecrire l'egalite= 1(0) sous la forme =(1(0)):

On obtient laloi de conservationselon laquelle, en regime stationnaire, le taux d'arrivee des clients dans la

le (donne par) doit ^etre egal au taux de service eectivement fourni par le serveur (donne par(1(0))).

3 Nombre moyen de clients dans la leL'esperanceLdu nombre de clients dans la le est donnee par

L=E(X) =+1X

i=0i(i) =+1X i=1i(1)i=(1)+1X i=1i i1=(1)1(1)2; ce qui donne L=1=: Comme on peut s'y attendre, lorsque la chargede la le augmente :

la fraction de temps 1 (0) =ou le serveur est actif augmente, i.e., le serveur est utilise plus souvent;

le nom bremo yende clien tsdans la le E(X) =1=111 augmente aussi.

Lorsque!1, la fraction du temps ou le serveur est actif tend vers 1 et le nombre moyen de clients dans

la le tend vers +1. Nombre moyen de clientsen attentedans la leSeul le premier client est en service, donc le nombre de clients en attente dans la le est donne parX1 des queX1 :

E((X1)+) =X

i1(i1)(i) =X i1i(i) |{z} E(X) X i1(i) |{z} 1(0)=

1=21=E(X):

Ce resultat peut ^etre interprete de la facon suivante. La probabilite qu'il y ait au moins un client dans la

le est egale a. Sachant cela, le reste de la le se comporte comme une le M/M/1 de charge. Plus precisement, pour chaquei2N, on a P(X1 =ijX1) =P(X=i+ 1jX1) =P(X=i+ 1)P(X1)=(i+ 1)1(0)=(1)i+11(1)= (1)i=(i): Propriete PASTA (Poisson arrivals see time averages)On applique la formule des transitions condi-

tionnelles. Pour chaquei2N, la probabilite qu'un client entrant trouve la le dans l'etatiest donnee par

(i)P j2N(j)=(i):

Cette propriete est vraie en general, des que les clients entrent dans la le selon un processus de Poisson.

On l'appelle la propriete PASTA, pourPoisson arrivals see time averages. Loi de LittleLe temps moyenqu'un client passe dans la le est la somme de son temps d'attente et de son temps de service. On a donc =X i2N(i)|{z} (PASTA) Probabilite qu'un client trouveiclients devant lui a son arrivee(i+ 1)1 |{z}

Temps moyen pour

servir lesiclients deja presents, plus celui qui arrive

On obtient

=1 X i2N(i+ 1)(i) =1 X i2N(i+ 1)(i+ 1) =1 X i1i(i) =L

On peut reecrire cette egalite sous la formeL=. Il s'agit de la loi de Little, vraie dans n'importe quelle

le d'attente a l'etat stationnaire. 4

3 Systemes a attente et a perte

On distingue les systemes a perte des systemes a attente. Lessystemes a pertesont ceux dont la le d'attente

a un nombre limite de places, de sorte que des clients sont perdus (rejetes) s'ils arrivent alors que la le est

deja pleine. Lessystemes a attentesont ceux dont la le d'attente a un nombre inni de places.

En pratique, il n'existe pas de systeme a attente. On modelisera cependant par un systeme a attente tout

systeme dont le dimensionnement (du nombre de serveurs et de la le d'attente) est tel que les pertes sont

negligeables.

Systeme a attentePuisque les clients peuvent arriver et trouver une le arbitrairement longue, le critere

principal de performance est letemps moyen d'attente. Theoreme(Formule de Little).Dans un systeme a attente qui se trouve a l'etat stationnaire, le nombre

moyenLde clients dans la le (en attente ou en service) est egal au produit du taux d'arriveedes clients

dans la le par leur delai moyen. Autrement dit, on aL=.

Cela revient a dire que le temps moyen de sejour d'un client dans la le est egal au nombre moyen de clients

dans la le, divise par leur taux d'arrivee. Exemple(File M/M/1).La loi de Little redonne directement le resultat enonce plus t^ot : =11 1 1 =1: Systeme a perteLa taille de la le d'attente etant nie, on dispose automatiquement d'une borne sur le

temps moyen de sejour d'un client. En contrepartie, les clients peuvent ^etre rejetes a leur arrivee. Le critere

principal de performance est donc laprobabilite de perte, denie comme la probabilite qu'un client soit perdu

lorsqu'il arrive dans le systeme. D'apres la formule des transitions conditionnelles, on a informellement

Probabilite de perte =

P i2E;ietat bloquant(i)taux d'arrivee des clients dans l'etatiP i2E(i)taux d'arrivee des clients dans l'etati:

Le denominateur est appele letaux d'arrivee. Il s'agit de la frequence moyenne a laquelle les clients arrivent

dans la le. Le numerateur est appele letaux de perte. Il s'agit de la frequence moyenne a laquelle les clients

sont rejetes de la le. On a ainsi

Probabilite de perte =

Taux de perteTaux d'arrivee

Lorsque les clients arrivent selon un processus de Poisson de parametre, le taux d'arrivee des clients dans

l'etatiest egal aquel que soit l'etati2Econsidere. En simpliant l'egalite ci-dessus, on obtient alors

que la probabilite de perte est egale a laprobabilite de blocage, denie comme la probabilite que le systeme

soit dans un etat ou les nouveaux clients sont rejetes. Plus generalement : Theoreme(Propriete PASTA (Poisson arrivals see time averages)).Quand le processus d'arrivee est un

processus de Poisson, un point du processus (c'est-a-dire un client entrant) voit la distribution stationnaire.

Intuitivement, la propriete PASTA signie que les instants d'arrivee des clients dans la le sont independants

de l'etat de la le. Autrement dit, la probabilite qu'un nouveau client trouveiclients devant lui a sont arrivee

est egale a(i). 5

4 Modele d'Erlang a pertes

ModeleLe modele d'Erlang a perte a ete introduit en 1917 par le mathematicien et ingenieur danois

Agner Krarup Erlang alors qu'il travaillait pour laCopenhagen Telephone Company. Ce modele correspond

a unele M/M/S/S:x= 2 MLes clients arrivent selon un processus de Poisson de parametre >0. MLe temps de service de chaque client suit une loi exponentielle de pa- rametre >0 (et est independant du temps de service des autres clients).

SSserveurs.

SIl y a autant de places dans la le que de serveurs. Un client qui arrive alors qu'il y a dejaSclients (en service) dans la le est perdu.

La charge de la le est a nouveau donnee par=

Ce modele a ete introduit pour modeliser les allocations de lignes telephoniques dans les reseaux d'operateurs.

Dans ce contexte, chaque serveur correspond a une ligne telephonique et chaque client represente un appel

entrant. Un appel est rejete si toutes les lignes sont occupees. L'objectif est de calculer la probabilite de

perte, c'est-a-dire la probabilite qu'un appel entrant soit perdu. Etat de la lePour chaquet2R+, on noteXtla variable aleatoire qui compte le nombre de clients

dans la le a l'instantt. On suppose que la le est vide a l'instant 0, c'est-a-dire queX0= 0. (Xt)t0est

un processus de Markov homogene de type naissance et mort. Son espace d'etatE=f0;1;2;:::;Sgest ni.

Les transitions qui regissent l'evolution du processus sont representees sur le diagramme de laFigure3a :

Arriv ees.La pro chainearriv eese pro duitapr esun te mpsde loi exp onentiellede param etre. S'il y a

dejamclients dans la le, le client entrant est perdu et l'etat de la le reste inchange. D eparts.Lorsqu eiserveurs sont occupes, le temps avant le prochain depart est le minimum dei

variables aleatoires independantes de loi exponentielle de parametre, donc il suit une loi exponentielle

de parametrei.

Le processus (Xt)t0est irreductible (on peut relier n'importe quel couple d'etats en suivant le chemin le

plus direct dans le diagramme de transition) et recurrent (l'espace d'etat est ni).012:::S1S

23(S1)S

(a) Diagramme de transition

2(+ 2)

3(+ 3)

(S1)(+ (S1)) SS3 7

777777777777752

6

66666666666664A=(b) Generateur innitesimal

Figure3 { Processus de Markov decrivant l'etat d'une le M/M/S/S 6 Distribution stationnaireOn cherche les mesures, denies surE, qui sont solutions de l'equation matricielleA= 0, ouAest le generateur innitesimal du processus (Xt)t0, donne enFigure3b. Cela revient a resoudre le systeme d'equations : 8>< :(0) +(1) = 0; (i1)(+i)(i) + (i+ 1)(i+ 1) = 0;8i= 1;:::;S1; (S1)S(S) = 0: Comme pour la le M/M/1, on peut montrer par recurrence suri= 1;:::;S1 que le systeme ci-dessus est equivalent a (i1) +i(i) = 0;8i= 1;:::;S; de sorte que (i) =(0)ii!;8i= 0;1;:::;S: La condition de normalisation impose la valeur de(0) : 1 = SX i=0(0)ii!;soit(0) =1P S i=0 ii!: La distribution stationnaire du processus (Xt)t0est donc donnee par (i) = ii!P S j=0 jj!;8i= 1;:::;S: Performance et dimensionnementComme il s'agit d'un systeme a perte, on s'interesse a la probabilite

de perte. Les clients arrivent selon un processus de Poisson. D'apres la propriete PASTA, la probabilite de

perte est donc egale a la probabilite de blocage, donnee par (S) = SS!P S j=0 jj!: L'egalite ci-dessus s'appelle laformule d'Erlang-B, notee

E(;S) =

SS!P S j=0 jj!:

Cette formule a ete beaucoup utilisee pour dimensionner les reseaux telephoniques. En general, on conna^t

la charge, on xe une probabilite de blocage a ne pas depasser, et on cherche le nombre minimumSde serveurs garantissant queE(;S) est inferieur ou egal a cette probabilite. Pour une chargexee, on peut calculerE(;S) par recurrence sur le nombreSde serveurs. Son inverse est donne par

1E(;S)=P

S j=0jj! SS!=

SS!+PS1

j=0jj! SS!= SS! SS!+P S1 j=0jj! S

S1(S1)!= 1 +S

1E(;S1):

En reinversant, on obtient

E(;S) =E(;S1)S

+E(;S1): 7 On peut utiliser cette formule pour demontrer queE(;S) decro^t bien lorsqueSaugmente1. En pratique, on initialise la recurrence avecE(;0) = 1 (perte s^ure) pourS= 0 puis on incrementeSjusqu'a ce que

E(;S) passe sous le seuil souhaite.

InsensibiliteNous avons suppose la distribution des temps de service exponentielle. On peut montrer que

la formule d'Erlang-B reste valable sous des hypotheses plus generales. On dit que le modele d'Erlang a perte

estinsensiblea la distribution des temps de service des clients.

5 Modele d'Erlang a attente

ModeleLe modele d'Erlang a attente correspond a une le M/M/S[/1/FIFO]. Il est similaire au modele

d'Erlang a perte, sauf que la taille de la le d'attente est innie. La partie 1 donne un exemple avecS= 3.

Etat de la leSoit (Xt)t0le processus qui compte le nombre de clients dans la le a chaque instant, avecX0= 0. (Xt)t0est un processus de Markov homogene de type naissance et mort. Son espace d'etat

E=Nest inni. Les transitions qui regissent l'evolution de la le sont representees sur le diagramme de la

Figure4a :

Arriv ees.La pro chainearriv eese pro duitapr esun temps de loi exp onentiellede par ametre. Il n'y a

pas de blocage. D eparts.Lorsque iclients sont dans la le, le nombre de serveurs occupes est donne par min(i;k). Le

temps avant le prochain depart suit donc une loi exponentielle de parametre min(i;k).012:::S1SS+ 1...

23(S1)SSS

(a) Diagramme de transition de l'etat de la le M/M/S/S

2(+ 2)

3(+ 3)

S(+S)

S(+S)3

7

777777777777777752

6

66666666666666664A=(b) Generateur innitesimal

Figure4 { Processus de Markov decrivant l'etat d'une le M/M/S1. On peut montrer par recurrence que S +E(;S)1 pour n'importe quelle valeur deS. L'initialisation est immediate puisqueE(;0) = 1 (perte s^ure). L'heredite s'ecrit S +E(;S) =S +E(;S1)S +E(;S1)=S + 1S S +E(;S1)S + 1S S1 +E(;S1)S + 1S = 1; ou la deuxieme inegalite decoule de l'hypothese de recurrence. 8

Le processus (Xt)t0est irreductible. On va montrer qu'il est recurrent positif si et seulement si < S,

c'est-a-dire < S. Distribution stationnaireOn cherche les mesures, denies surE=N, qui sont solutions de l'equation matricielleA= 0, ouAest le generateur innitesimal du processus (Xt)t0, donne enFigure4b. Cela revient a resoudre le systeme d'equations :8>< :(0) +(1) = 0; (i1)(+i)(i) + (i+ 1)(i+ 1) = 0;8i= 1;:::;S1; (i1)(+S)(i) +S(i+ 1) = 0;8iS:

Apres resolution, on obtient

(i) =8 :(0)ii!sii= 0;1;:::;S; (0)iS!SiSsiiS;

Lorsque < S, le processus de Markov est recurrent positif et la probabilite que le systeme soit vide est

donnee par (0) =1P S j=0 jj!+SS!S1S car +1X j=S+1 jS!SjS=SS!+1X j=1 S j=SS!Squotesdbs_dbs35.pdfusesText_40

[PDF] statistique drogue 2015

[PDF] chiffre d'affaire de la drogue dans le monde

[PDF] onudc recrutement

[PDF] consommation de drogue par pays

[PDF] nombre de drogue dans le monde

[PDF] filière es matières

[PDF] filière es wikipédia

[PDF] montrer que l'action politique ne se limite pas au vote

[PDF] filière es premiere

[PDF] le répertoire de l'action politique se limite-t-il au vote ?

[PDF] montrer que la participation politique repose sur des répertoires d'action politique variés

[PDF] montrez que les répertoires de l'action politique sont variés.

[PDF] définition de l'éducation pdf

[PDF] connectés pour apprendre les élèves et les nouvelles technologies

[PDF] education english pdf