[PDF] Exercices de Files dAttentes PDF FA12%20-PolyCorriges.pdf

7 Exercices non corrigés 21 7 1 Etude de On consid`ere une file d'attente `a un serveur On se propose d'étudier une file d'attente simple ayant 2 serveurs

[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 avec deux serveurs - CERMICS

Le but de cet exercice est l'étude d'une file d'attente avec deux serveurs de caractéristiques On suppose que le processus d'arrivée est un processus de

[PDF] File dattente simple - Congduc Phams

File d'attente simple PHAM Congduc, Université de Pau Exercice 1 Le système que nous considérons est une base de données où le temps de réponse

[PDF] Exemple file dattente

13 mar 2015 · File d'Attente (Exemples) Première partie Analyse opérationnelle 1 Modèle du dentiste (Correction exercice 1 1 poly exercices) Solution

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

12 sept 2019 · Exercice 01 (Réseau de files d'attente : 15 pts) (a) Le taux d'arrivé effectif pour chaque file d'attente (λi) (b) Le taux Corrigé-type + Barème

[PDF] Polytech Lyon M2 Statistique des processus TD 3 Files dattente

Files d'attente Exercice 1 Une station-service comporte une seule pompe à essence Des voitures arrivent selon un processus de Poisson de taux 20 voitures

[PDF] Phénomène dattente

8 jan 2015 · Exercice 1 : Etude de l'affluence d'une station de taxis Considérer le système formé d'un guichet unique, sans file d'attente Quand un client

[PDF] 1 Exercice

12 déc 2005 · file d'attente, les nouvelles requêtes arrivantes seraient trop pénalisées au niveau du temps de réponse Donc on décide que dans ce cas,

Exercices de Files d"Attentes

Monique Becker

Andr´e-Luc Beylot

Alexandre Delye de Clauzade de Mazieux

2006-2007 v.2

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?

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. Chapitre 3Chaˆınes de Markov `a tempscontinu3.1 Processus de Poisson Application des processus de naissance et de mort : cas d"un processus de naissance pure. C"est un processus pour lequel la probabilit´e conditionnelle denaissance entretett+dtvautλdt. SoitKla variable al´eatoire correspondant au nombre de naissances entre 0 ett:

P[K(t+dt) =k+ 1/K(t) =k] =λdt

1-Ecrire les ´equations diff´erentielles permettant d"´etudier la famille de fonctions (Pk), o`u :

P k(t) =P[K(t) =k]

2-D´emontrer que l"on obtient

P k(t) =(λt)k k!e-λt

3-CalculerE[K(t)] etE[K(t)(K(t)-1)]. En d´eduireV ar[K(t)].

4-Calculer la fonction de r´epartition du temps s´eparant deux arriv´ees. En d´eduire sa densit´e de

probabilit´e. Donner son esp´erance math´ematique. 5

6CHAPITRE 3. CHAˆINES DE MARKOV`A TEMPS CONTINU

Chapitre 4Files d"attentes simples4.1 Mod`ele du r´eparateur On consid`ere une chaˆıne de Markov mod´elisantKmachines ind´ependantes. Chacune d"elles peut tomber en panne avec un tauxλ. Un r´eparateur r´epare une seule machine `a la fois avec le tauxμ.

1-Exprimer le taux de passage de l"´etat (nmachines en panne) `a l"´etat (n+1 machines en panne).

On fera une d´emonstration rigoureuse. Il sera peut-ˆetre n´ecessaire de d´emontrer au pr´ealable un

lemme sur la loi de l"inf d"un certain nombre de variables de loi exponentielle.

2-Calculer la probabilit´e d"avoirKmachines en panne.

3-Application num´erique :K= 7,λ= 0.001,μ= 1.

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

E[S] = 400ms

Λ = 2/s

Nplaces

Rejet si plein

On suppose que les messages forment un trafic poissonnien, ded´ebit moyen 2 messages par seconde.

La dur´ee de transmission est exponentielle de moyenneE[S] = 400mset on n´eglige les erreurs de

transmission. On suppose que la priorit´e est FIFO.

Quelle doit ˆetre la capacit´e du noeud de transmission pour que la probabilit´e de rejet soit inf´erieure

`a 10 -3? 7

8CHAPITRE 4. FILES D"ATTENTES SIMPLES

4.3 Unit´e de transmission avec des erreurs de transmission

E[S] = 400ms

Λ = 2/s

p= 0.1

On consid`ere un ´emetteur de messages.

- Les messages arrivent avec un d´ebit moyen de 2 messages parseconde. - La dur´ee moyenne de transmission estE[S] = 400ms. - Le taux d"erreur (donc de retransmission) estp= 10%. - La capacit´e est infinie

On fait les hypoth`eses suivantes : arriv´ees poissonniennes, services exponentiels, priorit´e FIFO.

1-Calculer l"esp´eranceedu nombre de passages d"un client dans cette file.

2-Calculer l"esp´erance du tempsRs´eparant l"arriv´ee du message et le moment o`u il est transmis

correctement.

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

Il s"agit d"une file avec arriv´ees poissonniennes de tauxλavecCserveurs exponentiels de taux

μet avecCplaces dans la file d"attente. Cela signifie que seuls peuvententrer dans la file les clients

qui peuvent imm´ediatement commencer `a ˆetre servis, les autres sont rejet´es.

1-D´emontrer que le nombre de clients dans la file constitue un processus de naissance et de mort.

Calculer les taux d"arriv´ee et de d´epart conditionnels.

2-Calculer la probabilit´e des divers ´etats possibles.

3-En d´eduire la probabilit´e pour qu"un client arrivant de l"ext´erieur soit rejet´e. Le r´esultat est

connu sous le nom de premi`ere formule d"Erlang.

4-Calculer le nombre moyen de clients dans la file et le temps moyen de r´eponse.

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

On se propose d"´etudier une file d"attente simple ayant 2 serveurs. Dans tout l"exercice, les

arriv´ees seront suppos´ees poissonniennes de tauxλ. Les temps de service sont exponentiels, la

discipline est FCFS (premier arriv´e, premier servi), la file est `a capacit´e infinie.

1- Serveurs homog`enes

On suppose dans un premier temps que les deux serveurs sont identiques. Le taux de service est

μ(cf. Fig 4.1). Quand un seul serveur est disponible, le premier client en attente choisit ce serveur.

Quand les deux serveurs sont disponibles, le client choisital´eatoirement et ´equiprobablement un

des deux serveurs.

Fig.4.1 - Serveurs homog`enes

4.5. FILE`A SERVEURS H´ET´EROG`ENES9

a-Donner la notation de Kendall de cette file. b-On noteN(t) le nombre de clients dans la file `a l"instantt. Montrer queN(t) est un processus markovien (on pourra montrer que l"inf de deux lois exponen- tielles ind´ependantes de param`etresμ1etμ2est une loi exponentielle).

D´emontrer queN(t) constitue un processus de naissance et de mort et calculer les taux d"arriv´ee

et de d´epart conditionnels. c-On veut calculer les probabilit´es des divers ´etats possibles. On noteπila probabilit´e qu"il y aiticlients dans la file `a l"´etat stationnaire.

D´emontrer que :

?i≥1πi= 2ρiπ0avec ρ=λ 2μ

D´eterminerπ0.

Quelle est la condition de stabilit´e de la file? d-D´eterminer le nombre moyenE[L] de clients dans la file.

Quel est le temps moyen de r´eponse E[R]?

On rappelle que pourρ <1, on a :∞?

n=0nρ n=ρ (1-ρ)2

2- Serveurs h´et´erog`enes

On suppose maintenant que le serveur 1 est deux fois plus rapide que le serveur 2 (cf. Fig 4.2). On note 2μle taux de service du serveur 1 etμle taux de service du serveur 2. Le choix du serveur se fait de la fa¸con suivante : Si un seul serveur est disponible, le premier client en attente choisit ce serveur. Si les deux serveurs sont libres, le premier client en attente choisit le serveur le plus rapide (le serveur 1).

Fig.4.2 - Serveurs h´et´erog`enes

a-On noteN(t) le nombre de clients dans la file `a l"instantt.

N(t) est-il un processus markovien?

b-On s´epare l"´etat o`u l"on a un seul client dans la file en deux´etats :

´etat 1

?: il y a un seul client dans la file, il se trouve dans le serveur 1. ´etat 1" : il y a un seul client dans la file, il se trouve dans le serveur 2.

On consid`ere le processusE(t) :

E(t) =i, aveci= 0 oui≥2 s"il y aiclients dans la file `a l"instantt. E(t) = 1?, s"il y a un client dans la file `a l"instanttqui se trouve dans le serveur 1. E(t) = 1", s"il y a un client dans la file `a l"instanttqui se trouve dans le serveur 2.

Montrer queE(t) est un processus markovien.

Calculer les taux d"arriv´ee et de d´epart conditionnels.

E(t) est-il un processus de naissance et de mort?

c-On cherche la limite stationnaire de ce processus. Pour simplifier les calculs on suppose queλ=μ.

On noteπila probabilit´e stationnaire d"ˆetre dans l"´etatide la chaˆıne de Markov.

D´eterminer les probabilit´es des diff´erents ´etats.

On pourra suivre la d´emarche suivante : d´eterminerπ3en fonction deπ2, puisπi+2en fonction de

2pouri >0. En ´ecrivant trois ´equations entreπ0,π1?,π1??, etπ2, montrer que :

0= 5π2π1?= 2π2π1??=π2

10CHAPITRE 4. FILES D"ATTENTES SIMPLES

Utiliser la condition de normalisation et d´eterminer lesπi.

Le syst`eme est-il stable?

d-Quel est le nombre moyenE[L] de clients dans la file?

Quel est le temps moyen de r´eponseE[R]?

Quel est le taux d"occupation de chacun des serveurs?

Quel est le temps moyen d"attenteE[W]?

Quelle est la proportion de clients servis par chacun des deux serveurs?

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

Dans le mod`ele d"un lien du r´eseau t´el´ephonique par une file M/M/C/C, on suppose que le

nombre d"utilisateurs potentiels du lien est infini. Si cette hypoth`ese est raisonnable dans le coeur

du r´eseau, elle peut se r´ev´eler un peu forte dans la partied"acc`es (commutateurs d"acc`es, cellule

d"un r´eseau GSM ...). L"objectif de cet exercice est d"´etudier les performances d"un lien dans le cas

o`u le nombre d"utilisateurs pouvant ˆetre joints par ce lien est limit´e `aN(taille de la population

N,C << N).

On mod´elise alors le lien de la fa¸con suivante :

BDA EC serveursN serveurs

La deuxi`eme file correspond au lien. Un client dans cette filecorrespond `a un appel t´el´ephonique

en cours.

La premi`ere file correspond aux abonn´es qui ne sont pas en communication. Le temps de r´eflexion

(temps pass´e dans la file 1) avant une tentative d"appel est suppos´e exponentiel de tauxλ. La dur´ee

de la communication est suppos´ee exponentielle de tauxμ. Quand un appel arrive (en provenance ou `a destination d"un abonn´e qui n"est pas encore en

communication), il est accept´e s"il reste de la place dans la deuxi`eme file ou rejet´e (on suppose

alors que l"utilisateur repasse dans la file 1, on ne tient pascompte de son impatience potentielle).

On veut d´eterminer la probabilit´e de rejet d"appel.

1-SoitNtle nombre d"appels en cours `a l"instantt. Montrer que (Nt,t?R) est un processus

markovien ergodique.

2-D´eterminer les probabilit´es en r´egime stationnaire.

3-On veut d´eterminer la probabilit´e de rejet. Pour cela, d´eterminer le flux offert au lien (d´ebit au

pointA: ΛA) et le d´ebit rejet´e (d´ebit au pointB: ΛB). En d´eduire la probabilit´e de rejet. Que

constate-t-on?

4.7. INFLUENCE DE LA VARIANCE DES SERVICES ET DE LA LOI DE PRIORIT´E11

4.7 Influence de la variance des services et de la loi de prio-

rit´e

S1,S2λ1

λ2

On suppose qu"il y a deux classes de clients.

Les arriv´ees sont poissonniennes :

- classe 1 : une arriv´ee toutes les 2,4s; - classe 2 : une arriv´ee toutes les 0,8s.

Les services :

- classe 1 : moyenneE[S1] = 0,6s; - classe 2 : moyenneE[S2] = 0,3s. Comparer les temps de r´eponse (globaux et par classe) dans le cas de services exponentiels et d´eterministes et de discipline PS ou FCFS.

4.8 Longueur des paquets IP

L"analyse de la distribution des paquets IP dans l"Internetmontre qu"il y a de tr`es nombreux paquets de petite taille (Acquittements TCP, paquet ICMP).

Dans le pr´esent exercice, on les suppose tous de la mˆeme taille ´egale `al1= 50 octets. Un deuxi`eme

pic est constitu´e par des paquets d"environl2= 500 octets (limit´es par le MSS standard) et un

troisi`eme pic de paquets rentrant dans des trames Ethernet(l3= 1500 octets). On suppose que les

fr´equences d"apparition des autres types de paquets sont n´egligeables. Une campagne de mesure a

donn´e les r´esultats suivants :

Taille moyenne des paquets :E[L] = 500 octets.

Ecart-Type :σ(L) = 500 octets.

On consid`ere un lien `a 100 Mb/s reliant un routeurA`a un routeurBcharg´e `a 80% dans le sens deAversB.

On s"int´eresse au temps moyen pass´e dans la file de sortie durouteurAen attente d"´emission vers

le routeurB. On consid`ere que les arriv´ees des paquets dans la file constituent pour chacun des trois types de paquets un processus poissonnien et que la discipline est FIFO.

1-D´eterminer le temps moyen pass´e par un paquet de chacun destrois types dans la file de sortie

du routeur (attente + service) en fonction des grandeurs caract´eristiques du syst`eme.

2-Faire les applications num´eriques.

12CHAPITRE 4. FILES D"ATTENTES SIMPLES

Chapitre 5R´eseaux de files d"attentes5.1 Syst`eme multi-programm´e `a m´emoire virtuelle On consid`ere un syst`eme interactif, compos´e essentiellement deNterminaux, d"une unit´e cen- trale (UC) et d"un disque de pagination (DK). Le degr´e de multiprogrammation (nombre de pro-

grammes autoris´es `a partager l"UC et le disque) est limit´e `a une certaine valeur maximaleM. Les

programmes ´emis des terminaux (un programme par"interaction») qui ne peuvent pas ˆetre admis

dans le syst`eme central sont plac´es en attente dans une fileWAIT. Le syst`eme est sch´ematis´e sur

la figure suivante :

Le nombre de terminaux estN= 10.

Le temps de reflexion moyen estE[Z] = 4s.

Le degr´e de multiprogrammation estM= 4.

La dur´ee moyenne du service disque estE[Sdk] = 40ms. On effectue des mesures sur une dur´ee assez longue et on obtient les estimations suivantes : L"esp´erance du temps d"execution d"une interaction (en cumulant tous les temps entre deux inter- ruptions est) est de 2s. D´ebit : 0,4 interactions/s.

Taux d"occupation CPU : 0,8.

Nombre moyen d"appels au disque par interaction : 50.

1-On a constat´e que la file WAIT n"´etait jamais vide. Que peut-on en conclure?

Quels sont les temps de r´eponse moyenRdu syst`eme complet (vu des terminaux) etR?du syst`eme central? En d´eduire le temps d"attente moyen dans la file WAIT.

2-Calculer les demandes totales de traitement au CPU et au disque, par interaction.

Pour ces demandes totales au CPU et au disque, peut-on majorer le d´ebit de sortie du syst`eme central? 13

14CHAPITRE 5. R´ESEAUX DE FILES D"ATTENTES

Par la suite, on fera l"hypoth`ese que les services disque etCPU sont distribu´es suivant des lois

exponentielles et ind´ependantes, que la loi de priorit´e est FIFO et que les files sont infinies.

3-Si les entr´ees dans le syst`eme ´etaient poissonniennes, quel th´eor`eme pourrait-on utiliser?

Quels seraient alors le degr´e de multiprogrammation et le temps de r´eponse du syst`eme central,

pour le d´ebit et les demandes de service obtenues par mesures. Conclusion : les entr´ees sont-elles poissonniennes?

4-On d´ecide de mod´eliser le syst`eme central avec un r´eseauferm´e avecMinteractions. En

consid´erant le casM= 4 et les demandes de service mesur´ees, calculer pour le mod`ele ferm´e

le temps de r´eponse et le d´ebit du syst`eme central. On peutappliquer le th´eor`eme de Gordon et

Newell.

On pourra refaire le calcul en utilisant l"algorithme de Reiser. Compte tenu des sym´etries du

probl`eme, aurait-il ´et´e possible de n"appliquer l"algorithme de Reiser qu"en partant du bas de la

colonne correspondante `a K=3?

Conclusion : le mod`ele ferm´e est-il valable?

Quelle est la dur´ee d"une entr´ee/sortie (attente + service)?

5-On suppose qu"avec un degr´e de multiprogrammation limit´e`a 2, le nombre d"entr´ees/sorties

par interaction est r´eduit de moiti´e. On suppose que la demande totale au CPU est inchang´ee et

la file WAIT jamais vide. Evaluer le temps de r´eponse qu"aurait le syst`eme central dans cette nouvelle situation? Calculer le taux d"occupation CPU et le taux de recouvrementCPU/disque (probabilit´e pour que ces deux unit´es soient actives simultan´ement).

Conclusion : cette nouvelle configuration donne-t-elle de meilleures performances? On r´efl´echira

pour voir s"il vaut mieux comparer les d´ebits ou les temps der´eponse des deux configurations.

5.2 Du choix du point o`u l"on compte le d´ebit global dans

un r´eseau ferm´e

On consid`ere le r´eseau suivant. Les arriv´ees sont suppos´ees poissonniennes, les temps de service

exponentiels, la discipline de service PAPS, les files infinies et les routages probabilistes.

1-D´eterminer les nombres moyens de passages par chacune des files. Le r´eseau est-il stable?

D´eterminer son temps de r´eponse.

2-On ferme le r´eseau sur lui-mˆeme et l"on suppose qu"il y a au plusK= 2 clients `a l"int´erieur.

Quel est le temps moyen entre deux passages successifs d"un client donn´e par la station 2? Quel

est le temps moyen entre deux passages de clients successifs(eventuellement diff´erents)? Quel est

le d´ebit au pointD?

Applications Num´eriques :

5.3. TH´EOR`EME DE JACKSON ET ANALYSE OP´ERATIONNELLE15

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

On consid`ere un syst`eme comportant une Unit´e Centrale etdeux disques sur lequel on a fait les mesures suivantes : . Dur´ee de la mesure : 1800s; . Dur´ee totale d"utilisation UC : 1440s; . Nombre de transactions trait´ees : 720; . Nombre total d"acc`es au disque 1 : 36000; . Nombre total d"acc`es au disque 2 : 18000; . Dur´ee d"un acc`es au disque 1 : 40ms; . Dur´ee d"un acc`es au disque 2 : 100ms.

On fait les hypoth`eses suivantes :

. Arriv´ees exponentielles; . Services exponentiels; . Acc`es probabilistes; . Ind´ependance entre les services; . Files infinies et politique PAPS.

1-Calculer le temps de r´eponse moyen du syst`eme, le taux d"occupation de l"UC et le taux de

recouvrement UC/disque.

2-La dur´ee d"un acc`es au disque 2 est maintenant de 10ms. Calculer le temps de r´eponse moyen

du syst`eme, le taux d"occupation de l"UC et le taux de recouvrement UC/disque.

5.4 R´eseau local

On consid`ere le r´eseau local comportantN(N= 6) terminaux, un serveur (CPU) etm(m= 2)

disques. Le serveur et les disques fournissent des traitements qui seront suppos´es exponentiels et

appliquant une politique PAPS. Leurs files d"attente ont au moins une capacit´eN. La consom- mation CPU est de 5s. Une interaction fait en moyenne 500 appels `a chacun des disques dont le temps de service estE[S] (E[S] = 10ms). Le temps de r´eflexion est de 10s.

1-Quel th´eor`eme peut-on utiliser?

2-Appliquer l"algorithme de Reiser pour calculer le temps de r´eponse de ce r´eseau.

16CHAPITRE 5. R´ESEAUX DE FILES D"ATTENTES

Chapitre 6M´ethodes d"agr´egation6.1 R´eseau sym´etrique On consid`ere un ensemble deMstations identiques, avec un serveur exponentiel pour chacune,

dont le temps de service moyen estE[S] = 1/μ. Il y a ´equir´epartition des acc`es, les clients sont

envoy´es par une source exponentielle. On mod´elise l"ensemble sous la forme d"un r´eseau ferm´e avec

Nclients.

On utilise une m´ethode d"agr´egation. Calculer le tauxμ(n) du serveur ´equivalent `a l"ensemble des

Mstations, en utilisant la r´ecurrence Mean Value Analysis (algorithme de Reiser) en fonction de n,MetE[S].

6.2 Agr´egation de chaˆınes de Markov

On consid`ere la chaˆıne de Markov suivante qui mod´elise letrafic en entr´ee d"une file de sortie

d"un commutateur ATM. La source peut se trouver dans trois ´etats : - 0 : silence - 1 : rafale envoy´ee vers la sortie qui nous int´eresse - 2 : rafale envoy´ee vers une autre sortie

On a donc une chaˆıne de Markov `a temps discret dont les probabilit´es de transitions sont les sui-

vantes : P

00= 1/8, P02= 5/8, P10=P20= 1/8

18CHAPITRE 6. M´ETHODES D"AGR´EGATION

1-CalculerP01,P11etP22.

2-Calculer les probabilit´es des trois ´etats.

3-On veut agr´eger les deux ´etats 0 et 2 en un ´etatA. On souhaiterait maintenir la bonne valeur

pourP(1) et obtenirP(A) =P(0) +P(2) Quelles probabilit´es de transitions faudrait-il prendre pourPA1etP1A? Cette agr´egation est-elle exacte?

6.3 Agr´egation de files d"attente

Soit un r´eseau ferm´e comportant trois stations. Les services sont exponentiels, les capacit´es des

files infinies ou au moins ´egales `aK, le nombre de clients dans le r´eseau. La discipline est PAPS

et les routages probabilistes. On veut trouver le taux d"utilisation du serveur 1 pourK= 1,2,3,4, en utilisant une m´ethode d"agr´egation.

1-Consid´erer le sous-r´eseau suivant et d´eterminer le d´ebit Λ(n).

6.3. AGR´EGATION DE FILES D"ATTENTE19

2-Consid´erer le r´eseaucomportant la station 1 et la file composite dont le service d´epend du nombre

nde clients dans cette file et est exponentiel de param`etreμ(n) avecμ(n) = Λ(n). Calculer alors

le taux d"utilisation du serveur 1.quotesdbs_dbs17.pdfusesText_23

[PDF] [PDF] Exercices de Files dAttentes

Exercices de Files d"Attentes

Monique Becker

Andr´e-Luc Beylot

Alexandre Delye de Clauzade de Mazieux

2006-2007 v.2

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

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

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

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

1.2 Temps d"attente d"un train

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-

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

2CHAPITRE 1. EXERCICES G´EN´ERAUX

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

2.3 Mod`eles de trafic sur un lien

1-Trafic de Bernoulli

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

2-Trafic Bursty Geometric

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

3-Trafic Interrupted Bernoulli Process (IBP)

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

P[K(t+dt) =k+ 1/K(t) =k] =λdt

1-Ecrire les ´equations diff´erentielles permettant d"´etudier la famille de fonctions (Pk), o`u :

2-D´emontrer que l"on obtient

3-CalculerE[K(t)] etE[K(t)(K(t)-1)]. En d´eduireV ar[K(t)].

4-Calculer la fonction de r´epartition du temps s´eparant deux arriv´ees. En d´eduire sa densit´e de

6CHAPITRE 3. CHAˆINES DE MARKOV`A TEMPS CONTINU

1-Exprimer le taux de passage de l"´etat (nmachines en panne) `a l"´etat (n+1 machines en panne).

2-Calculer la probabilit´e d"avoirKmachines en panne.

3-Application num´erique :K= 7,λ= 0.001,μ= 1.

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

E[S] = 400ms

Λ = 2/s

Nplaces

Rejet si plein

8CHAPITRE 4. FILES D"ATTENTES SIMPLES

4.3 Unit´e de transmission avec des erreurs de transmission

E[S] = 400ms

Λ = 2/s

On consid`ere un ´emetteur de messages.

1-Calculer l"esp´eranceedu nombre de passages d"un client dans cette file.