14 Introduction aux files dattente - GERAD
On consid ere une le d’attente M=M=1 avec priorit e : Les clients de classe 1 ont une priorit e absolue sur les clients de classe 2, c’est- a-dire qu’ils d epassent automatiquement tous les clients de classe 2 dans la le De plus, un client de classe 2 en service retourne imm ediatement dans la le d’attente si un client de
Comprendre les Files dAttente - Lean: Six Sigma
2 Vitesse; Stabilité: Minimiser les temps d'attente D M A A C La suite de calculs pour calculer la longueur d'une File d'Attente Calcul de Temps en File et Longueur de la File Paramètre Formule Valeur Unités Dimensions Taux d'Arrivée λ 1,6 clients/min t-1 Temps de Service/Serveur b 2 min/serveur t Nbre de Serveurs n 4 serveurs
Exercices de Files d’Attentes - OsmoZ 2009com
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 des trains sont s´epar´es par des dur´ees
Modélisation & Simulation
le domaine de la modélisation se sont focalisées sur la théorie de la file d’attente Plusieurs modèles de file d’attente sont établis Exemple : le modèle M/M/1 le modèle M/M/S M/M/1 : Arrivée suivant la loi de Poisson Service suivant la loi exponentielle Un serveur
Approche régénérative de la file d’attente M G/1 avec rappels
Récemment, Aïssani (Aïssani, 2008) considère une file d’attente M=G=1 avec la politique de rappels constants et vacances du serveur, quand les temps de rap-
Introduction
Une file d’attente est constituée des clients qui demandent un service à un ou plusieurs serveurs et d’une salle d’attente Le taux des clients qui arrivent et le taux de service par unité de temps sont respectivement notés λ et µ L’apparition d’une file d’attente résulte d’un processus similaire à ce qui conduit
COURS DE MODELISATION ET SIMULATION M1 - INFORMATIQUE
le domaine de la modélisation se sont focalisées sur la théorie de la file d’attente Plusieurs modèles de file d’attente sont établis Exemple : le modèle M/M/1 le modèle M/M/S M/M/1 : Arrivée suivant la loi de Poisson Service suivant la loi exponentielle Un serveur
CHAPITRE III : GESTION DES PROCESSUS
périphériques, on peut imaginer une file d’attente pour chaque périphérique Quand un processus demande une opération d’E/S, il est mis dans la file d’attente concernée Concrètement une file d’attente est représentée par une liste chaînée de PCB, comme le montre le schéma suivant File d’attente des processus prêts :
[PDF] chaine de markov résumé
[PDF] chaine de markov matrice de transition
[PDF] exercice corrigé chaine de markov a etat absorbante
[PDF] chaine d'acquisition de données
[PDF] chaine de mesure audioprothèse
[PDF] acquisition de données du capteur ? l ordinateur
[PDF] chaine de mesure pdf
[PDF] chaine d'acquisition capteur
[PDF] les capteurs exercices corrigés
[PDF] chaine de markov apériodique
[PDF] chaine de markov apériodique exemple
[PDF] chaine de markov reversible
[PDF] chaine de markov récurrente
[PDF] chaine de markov exemple
Exercices de Files d"Attentes
Monique Becker
Andr´e-Luc Beylot
Alexandre Delye de Clauzade de Mazieux
2006-2007 v.2
iiTable 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`ERESUnit´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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 33File `a Serveurs H´et´erog`enes . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 34
Performance d"un ´etage d"abonn´es - File M/M/C/C/N . . . . . .. . . . . . . . . . . . . 37Influence de la variance des services et de la loi de priorit´e. . . . . . . . . . . . . . . . . 40
Longueur des paquets IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 41Syst`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 . . . . . . . .. . . . . . . . . . . . . . 48R´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 dentisteOn 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?
12CHAPITRE 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] =petP[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 decellule 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. 34CHAPITRE 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-λt3-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. 56CHAPITRE 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? 78CHAPITRE 4. FILES D"ATTENTES SIMPLES
4.3 Unit´e de transmission avec des erreurs de transmission
E[S] = 400ms
Λ = 2/s
p= 0.1On 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 infinieOn 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, lesarriv´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-ρ)22- 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 lenombre 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 encommunication), 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´eS1,S2λ1
λ2On 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 lesfr´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? 1314CHAPITRE 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 duprobl`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´eOn 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? Quelest 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].