[PDF] [PDF] Exercices de Files dAttentes

[PDF] Exercices de Files dAttentes

On consid`ere un ensemble de M stations identiques, avec un serveur exponentiel pour chacune, dont le temps de service moyen est E[S]=1/µ Il y a 

[PDF] corrigé - IRIF

Exercice 2 - File d'attente On considère une file d'attente M/M/3 Page 2 1 Expliquez brièvement le sens de cette notation Correction Selon 

[PDF] File dattente simple - Congduc Phams

1/ En modélisant ce système par une file M/M/1, donner : - le taux d'occupation U du serveur En déduire ρ - S, le temps moyen de service - D, le nombre de 

[PDF] File dattente avec deux serveurs - CERMICS

Le but de cet exercice est l'étude d'une file d'attente avec deux serveurs de caractéristiques 1 Montrer que X = (Xt,t ≥ 0) est une chaıne de Markov `a temps continu sur E Donner une file M/M/2 de taux de service µ et taux d' arrivée λ

[PDF] Exemple file dattente

13 mar 2015 · 5 2 Modèle M/M/1 5 3 Modèle M/M/1/N 5 4 Modèle M/D/1 5 1 File d'Attente (Exemples) (Correction exercice 1 1 poly exercices)

[PDF] Files dattente

Reprendre les calculs de la question précédente sous l'hypothèse d'une file résultante M(λ)/M(µ)/1 Exercice 6 (Monoserveur multiclasse avec priorités) Deux  

[PDF] Examen ModSim 18-19 - Université Larbi Ben Mhidi OEB

12 sept 2019 · Exercice 01 (Réseau de files d'attente : 15 pts) Considérons le 2018-2019 Corrigé-type + Barème Réponse à l'exercice 01 : 1 Matrice de 

[PDF] Processus markoviens de sauts - Laboratoire de Probabilités

à la loi du nombre de personnes dans une file d'attente au bout d'une heure On s'intéresse ici à Figure 1 17 – Graphe de transition d'une file M/M/1 Cette file 

[PDF] Files dattente - Stephan ROBERT-NICOUD

3 jui 2016 · Exercice 1 Dr Stephan Robert, HEIG-Vd Files d'attente 8/1 File M/M/1 Représentation de la file d'attente M/M/1 (Processus de naissance

[PDF] 14 Introduction aux files dattente - GERAD

Le mod`ele de base en files d'attente se nomme M/M/1 et se généralise en notation de Kendall A/B/C/K/N/D : ▻ A : processus d'arrivée (M = markovien ou 

[PDF] file d'attente m/m/1/k

[PDF] file d'attente m/m/s

[PDF] file d'attente m/m/s/

[PDF] filet presse

[PDF] filiale danone

[PDF] filiale la poste

[PDF] filiale orange sosh

[PDF] filiales nestlé monde

[PDF] filialisation d'une activité

[PDF] filialisation d'une branche d'activité

[PDF] filiere

[PDF] filière agricole definition

[PDF] filière agriculture

[PDF] filière agroalimentaire

[PDF] filiere apres bac s

Exercices de Files d"Attentes

Monique Becker

Andr´e-Luc Beylot

Alexandre Delye de Clauzade de Mazieux

2006-2007 v.2

ii

Table des mati`eres1 Exercices g´en´eraux1

1.1 Mod`ele du dentiste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 1

1.2 Temps d"attente d"un train . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 1

2 Chaˆınes de Markov `a temps discret3

2.1 Etude d"une Chaˆıne de Markov `a Temps Discret . . . . . . . . .. . . . . . . . . . 3

2.2 Processus de naissance et de mort . . . . . . . . . . . . . . . . . . . .. . . . . . . 3

2.3 Mod`eles de trafic sur un lien . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 3

3 Chaˆınes de Markov `a temps continu5

3.1 Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 5

4 Files d"attentes simples7

4.1 Mod`ele du r´eparateur . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 7

4.2 Unit´e de transmission `a capacit´e limit´ee . . . . . . . . .. . . . . . . . . . . . . . . 7

4.3 Unit´e de transmission avec des erreurs de transmission. . . . . . . . . . . . . . . . 8

4.4 Etude de la file M/M/C/C . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 8

4.5 File `a Serveurs H´et´erog`enes . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 8

4.6 Performance d"un ´etage d"abonn´es - File M/M/C/C/N . . .. . . . . . . . . . . . . 10

4.7 Influence de la variance des services et de la loi de priorit´e . . . . . . . . . . . . . . 11

4.8 Longueur des paquets IP . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 11

5 R´eseaux de files d"attentes13

5.1 Syst`eme multi-programm´e `a m´emoire virtuelle . . . . .. . . . . . . . . . . . . . . 13

5.2 Du choix du point o`u l"on compte le d´ebit global dans un r´eseau ferm´e . . . . . . . 14

5.3 Th´eor`eme de Jackson et Analyse Op´erationnelle . . . . .. . . . . . . . . . . . . . . 15

5.4 R´eseau local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 15

6 M´ethodes d"agr´egation17

6.1 R´eseau sym´etrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 17

6.2 Agr´egation de chaˆınes de Markov . . . . . . . . . . . . . . . . . . .. . . . . . . . . 17

6.3 Agr´egation de files d"attente . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 18

7 Exercices non corrig´es21

7.1 Etude de la transform´ee en z . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 21

7.2 Etude de la file M/GI/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 22

8 Corrig´es25

Mod`ele du dentiste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 25 Temps d"attente d"un train . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 25 Etude d"une Chaˆıne de Markov `a Temps Discret . . . . . . . . . . . .. . . . . . . . . . 26 Processus de naissance et de mort . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 27 Mod`eles de trafic sur un lien . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 27 Processus de Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 29 Modele du r´eparateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 31 iii ivTABLE DES MATI`ERES

Unit´e de transmission `a capacit´e limit´ee . . . . . . . . . . . .. . . . . . . . . . . . . . . 32

Unit´e de transmission avec des erreurs de transmission . . .. . . . . . . . . . . . . . . . 32 Etude de la file M/M/C/C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 33

File `a Serveurs H´et´erog`enes . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 34

Performance d"un ´etage d"abonn´es - File M/M/C/C/N . . . . . .. . . . . . . . . . . . . 37

Influence de la variance des services et de la loi de priorit´e. . . . . . . . . . . . . . . . . 40

Longueur des paquets IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 41

Syst`eme multi-programm´e `a m´emoire virtuelle . . . . . . . .. . . . . . . . . . . . . . . 42

Du choix du point o`u l"on compte le d´ebit global dans un r´eseau ferm´e . . . . . . . . . . 45

Th´eor`eme de Jackson et Analyse Op´erationnelle . . . . . . . .. . . . . . . . . . . . . . 48

R´eseau local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 49

R´eseau sym´etrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 50

Agr´egation de chaˆınes de Markov . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 50

Agr´egation de files d"attente . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . 51

Chapitre 1Exercices g´en´eraux1.1 Mod`ele du dentiste

On consid`ere une file d"attente `a un serveur.

On suppose que le d´ebit moyen est Λ, le temps moyen de r´eponse estE[R], le temps moyen d"attente

estE[W], le temps moyen de service est [E]S, l"esp´erance de longueur de la file d"attente estE[L],

le nombre moyen de clients en train d"attendre estE[LW], le nombre moyen de clients en train d"ˆetre servis estE[LS] et la probabilit´e pour que le serveur soit occup´e estU.

1-Ecrire une relation entreE[R],E[S] etE[W] (relation 1).

2-Ecrire une relation entreE[L],E[LW] etE[LS] (relation 2).

3-ExprimerE[LS] en fonction deU.

4-Montrer que l"on passe de la relation 1 `a la relation 2 en faisant une op´eration simple et montrer

qu"on trouve ainsi une relation connue entreU, Λ etE[S].

5-On consid`ere un dentiste. Le nombre moyen de patients pr´esents chez lui est 2.8, le nombre

moyen de patients dans la salle d"attente est 2, le nombre moyen de clients arrivant en une heure est 4. D´eduire les autres crit`eres de performances et caract´eristiques du traitement.

1.2 Temps d"attente d"un train

On consid`ere une voie ferr´ee sur laquelle les passages destrains sont s´epar´es par des dur´ees

(dur´ee entre deux trains successifs) de deux types possibles : - 90% de ces dur´ees sont constantes et ´egales `a 6mn. - 10% de ces dur´ees sont constantes et ´egales `a 54mn.

1-Calculer la dur´ee moyenne s´eparant deux trains successifs

2-Un individu arrive `a un instant quelconque. Au bout de combien de temps en moyenne pourra-

t-il prendre un train? On fera le calcul de deux fa¸cons diff´erentes : a-En calculant la probabilit´e pour que l"individu arrive pendant un intervalle court entre deux trains. On en d´eduira le temps d"attente r´esiduelle. b-En appliquant la formule de Pollaczek Khintchine.

3-Comparer les r´esultats de 1 et 2. Ces r´esultats semblent-ils paradoxaux?

1

2CHAPITRE 1. EXERCICES G´EN´ERAUX

Chapitre 2Chaˆınes de Markov `a tempsdiscret2.1 Etude d"une Chaˆıne de Markov `a Temps Discret

Soit une chaˆıne de Markov `a trois ´etats : 1, 2 et 3.

Les probabilit´es de transition de l"´etat 1 vers les ´etats2 et 3 sont respectivement 1-petp.

La probabilit´e de transition de l"´etat 2 vers l"´etat 1 est1.

Les probabilit´es de transition de l"´etat 3 vers les ´etats2 et 3 sont respectivementαet 1-α.

1-Pour quelles valeurs du couple (α,p) cette chaˆıne est-elle irr´eductible et ap´eriodique?

2-Pour (α,p) v´erifiant ces conditions, d´eterminer les probabilit´esd"´etat `a l"´equilibre.

3-En r´egime permanent, pour quelles valeurs de (α,p) les trois ´etats sont-ils ´equiprobables?

4-Calculer le temps moyen de premier retour en 2.

2.2 Processus de naissance et de mort

Soit une chaˆıne de Markov infinie dont les ´etats sont num´erot´es `a partir de 0. La probabilit´e de transition de l"´etatn`an+ 1 estp. La probabilit´e de transition de l"´etatn`an-1 estq.

D´emontrer qu"il faut avoirp < qpour que les ´etats soient r´ecurrents non nuls. On utilisera un

th´eor`eme vu en cours et on effectuera des coupes pour trouver rapidement la solution.

2.3 Mod`eles de trafic sur un lien

On consid`ere un lien transportant des cellules de longueurconstante. Compte tenu du synchro- nisme global, on mod´elise le trafic sous forme d"une chaˆınede Markov `a temps discret.

1-Trafic de Bernoulli

On suppose que les cellules sont ind´ependantes les unes desautres et qu"`a chaque unit´e de temps

on a une probabilit´epqu"il y ait une cellule et 1-pqu"il n"y en ait pas. Si l"on noteZ(t) la variable al´eatoire qui vaut 1 s"il y a une cellule `a l"instanttet 0 sinon, on aP[Z(t) = 1] =pet

P[Z(t) = 0] = 1-ppour toutes les valeurs det.

a-Mod´eliser ce processus sous forme d"une chaˆıne de Markov `a deux ´etats.

b-Calculer les probabilit´es des ´etats, le d´ebit de cellules et les deux premiers moments du temps

s´eparant deux cellules successives.

2-Trafic Bursty Geometric

On suppose que le trafic comporte des silences et des rafales.Pendant les silences il n"y a pas de

cellule sur le lien; pendant les rafales, il y a une cellule `achaque unit´e de temps. On noteX(t)

la variable al´eatoire qui vaut 1 si l"on est dans une rafale `a l"instanttet 0 dans un silence. On

suppose queP[X(t+ 1) = 1/X(t) = 1] =petP[X(t+ 1) = 0/X(t) = 0] =q. a-Montrer que l"on peut repr´esenter le processus (X(t)) par une chaˆıne de Markov. 3

4CHAPITRE 2. CHAˆINES DE MARKOV`A TEMPS DISCRET

b-D´eterminer les probabilit´es stationnaires des deux ´etats et le d´ebit de cellules. Montrer que les

dur´ees des silences et des rafales sont g´eom´etriquementdistribu´ees. En d´eduire leur dur´ee moyenne.

D´eterminer les deux premiers moments du temps s´eparant deux cellules successives. c-Pour quelles valeurs depetqun processus Bursty Geometric est-il un processus de Bernoulli?

3-Trafic Interrupted Bernoulli Process (IBP)

Le trafic comporte de nouveau des silences et des rafales de dur´ees g´eom´etriquement distribu´ees de

param`etres respectifspetq. Durant les rafales, les cellules arrivent selon un processus de Bernoulli

de param`etreα. SoitY(t) le processus des arriv´ees de cellules. On aura doncP[Y(t) = 1/X(t) =

1] =αetP[Y(t) = 0/X(t) = 0] = 1.

a-Y(t) est-il un processus markovien? b-D´eterminer le d´ebit, les longueurs moyennes des silenceset des rafales d"un processus IBP.quotesdbs_dbs7.pdfusesText_5