17
Analyse de performance en utilisant Les probabilités et les files d’attente Rapport présenté à l’équipe professorale de S3 Par Jean-René Bédard 01128041 _______________________ Groupe T1-P2

Probabilité et Statistiques

Embed Size (px)

Citation preview

Page 1: Probabilité et Statistiques

Analyse de performance en utilisantLes probabilités et les files d’attente

Rapport présenté àl’équipe professorale de S3

Par

Jean-René Bédard 01128041 _______________________

Groupe T1-P2

Mercredi le 8 octobre 2002

Page 2: Probabilité et Statistiques

Table des matières

Page couverture………………………………………………………………………..page 1Table des matières………………………………………….………………………….page 21.0 Introduction………………………………………………………………..………page 31.1 Déterminer la valeur du temps de service…………………………………………page 31.2 Fonction de densité et de répartition de probabilité de s…………………………..page 42.0 Valeurs moyennes…………………………………………………………………page 53.0 Calculer la TL de la FDP de q…………………………..…………………………page 74.0 Trouver la fonction génératrice de N…………………………………………...…page 85.0 Probabilité du nombre de clients dans le système…………………………………page 106.0 Modélisation et hypothèses………………………………………………………..page 117.0 Influence des paramètres…………………………………………………………..page 118.0 Conclusion………………………………………………………………………....page 12

Liste des figures

Figure 1- schéma de la modélisation du serveur………………………………………page 3

Page 3: Probabilité et Statistiques

1.0 Introduction

L’objectif de cette problématique est d’utiliser le formalisme des probabilités et des files d’attentes afin de développer une méthode générale qui permettrait l’analyse de performance de tout système informatique comprenant un seul serveur. J’ai suivi les conseils de Anna-Lyse de Performance et j’ai procédé en deux étapes. Dans la première étape, j’ai calculé la FDP et la FRP de s ainsi que les valeurs moyennes des cinq paramètres décrivant le système. Dans une seconde étape, j’ai calculer les Transformées de Laplace des FDP des paramètres de temps. J’ai aussi trouvé la fonction génératrice du nombre de client dans le système qui m’a servi à faire un calcul de probabilité sur le nombre de client dans le système. En dernier lieu, j’ai procédé à l’analyse de stabilité du système ainsi que de l’influence des paramètres.

Figure 1- schéma de la modélisation du serveur.

1.1 Déterminer la valeur du temps de service s

Le système que nous étudions ne possède qu’un seul serveur. Les requêtes sont traitées dans l’ordre ou elles arrivent. La succession des arrivées des requêtes est régie par le processus de Poisson. Le serveur effectue d’abord un traitement spécifique dont la durée est une constante . Ensuite, le serveur effectue un accès disque pour y modifier, ajouter ou supprimer les données. Nous pouvons trouver le temps de traitement des données par le serveur à partir des paramètres suivants :

- r : constante déterminant la vitesse de rotation du disque- k : constante déterminant le nombre de secteurs du disque- b : constante déterminant le nombre de secteurs lut ou écrit à chaque accès

Nous pouvons modéliser le temps de service d’une requête s par :s = +T, ou T est le temps d’accès et d’opération du disque.

Hypothèse : Toutes opérations de lecture et écriture s’effectue à un moment ou la tête se trouve à un frontière entre deux secteurs.

Nous allons définir le temps T par :T = temps d’accès au secteur + temps d’opération

Vitesse en secteur par minutes = r*k

Clients entrantDans le système

Clients dans la file d’attente Traitement de

la requête

Client servis

Page 4: Probabilité et Statistiques

Nous allons définir d qui est la variable aléatoire qui détermine à combien de secteurs se trouve la tête comparé au lieu d’opération.

s est donc donné par

1.2 Fonction de densité et de répartition de probabilité de s

La distribution uniforme continue caractérise le mieux les fonctions de répartition et de densité de s. En effet, il est possible de modéliser les bornes de la distribution en variant les constantes b, k et d

Le temps minimum pour le traitement serait la situation ou la tête serait directement sur le secteur désiré et il n’y aurait qu’un seul secteur à lire ou écrire (b=1).

Le maximum serait dans le cas ou la tête se trouverais à (k-1) secteurs du secteur désiré donc (d=(k-1)) et qu’il faudrait écrire ou lire k secteurs d’information (b=k)

X modélise la variable aléatoire sLa fonction de densité probabilité (FDP) de s serait exprimée par :

La fonction de répartition de probabilité (FRP) de s serait exprimée par :

X < min

min <= X <= max

X > max

X <= min

min <= X <= max

X > max

Page 5: Probabilité et Statistiques

2.0 Valeurs moyennes

2.1 Valeur moyenne de s et variance de s

La valeur de s est donnée par :

La variable aléatoire d représente le nombre de secteur que l’on doit se déplacer pour aller effectuer un opération. Étant donné que la variable d obéis à la loi de distribution uniforme discrète. En effet :

Nous devons dans un premier lieu, trouver l’espérance de d, c’est-à-dire E[d]

L’espérance de la loi de distribution uniforme est donnée par

Dans notre cas, n = (k-1),

Donc

Ensuite, à partir de E[d], nous pouvons trouver E[s] en remplaçant d par l’espérance de d

Il faut ensuite calculer Var[s] pour les autres valeurs moyennes des paramètre q, W, N, Nq

La variance pour une distribution uniforme est donnée par Dans notre cas n=(k-1)

Ensuite, à partir de Var[d], nous pouvons trouver Var[s]

ou

Page 6: Probabilité et Statistiques

Dans cette section j’énumère les autres valeurs moyennes trouvées pour les paramètres q,W, N et Nq. Les calculs au long ne sont pas énoncés pour alléger le document.

Dans ces équations, la variance Var[s] est donnée par

2.2 Valeur moyenne du nombre de client dans le systèmeparamètre N : Le nombre de clients dans le système

2.3 Valeur moyenne du temps de séjour moyen dans le système paramètre W : Le temps de séjour moyen

2.4 Valeur moyenne du temps d’attente d’un clientparamètre q: Le temps d’attente moyen d’un client

2.5 Valeur moyenne du nombre de client en attente d’être servisparamètre Nq : Le nombre de client en attente d’être servis

Page 7: Probabilité et Statistiques

3.0 Calculer la TL de la FDP de q

Nous savons que q est le temps d’attente d’une requête séparant l’arrivée d’une requête chez le serveur et le début de son traitement par le serveur. Étant donné que le temps d’attente minimum peut être de 0 et que le temps maximum est inconnu et peux être virtuellement l’infini, q est régit par une fonction de densité de probabilité de la forme exponentielle.

La transformée de Laplace de la FDP de q est donnée par :

3.1 Calculer la TL de la FDP de w

Nous savons que w est le temps de séjour d’une requête séparant l’arrivée de la requête chez le serveur jusqu’à la fin de son traitement.

Nous savons que w=q+s, soit le temps total dans le système (w) est égal à la somme de l’attente (q ) et du temps de traitement (s). Nous savons que q et s sont deux variables aléatoires indépendantes.

Etant donnée que q et s sont considérées comme étant deux variables aléatoires indépendantes, la transformée de Laplace de W est égal à la somme transformée de Laplace de q et de la transformée de Laplace de s.

Nous avons déjà la transformée de Laplace de q :

La transformée de Laplace pour le temps de service s est donnée par l’équation suivante :

Nous obtenons donc que w est égal à la somme transformée de Laplace de la FDP de q et de s, soit :

Page 8: Probabilité et Statistiques

4.0 Trouver la fonction génératrice de N

A partir des transformées de Laplace de FDP et FRP de s ainsi que de q et w, nous pouvons trouver la fonction génératrice .Nous allons définir B(x) comme étant égal à la FDP de s et b(x) est égal à la FRP de s. Il s’agit d’un résumé du calcul effectué.Nous définissons F(z,x) comme étant :

En multipliant la kième équation par et en faisant la sommation nous obtenons :

Changement de variables pour définir la fonction génératrice

Rappelons que B(x) est la FRP du temps de service sEn remplacant par G(z,x), nous obtenons :

Ce qui peut être interprété comme étant :

Page 9: Probabilité et Statistiques

Notons que F(z,0)=G(z,0)

est la transformée de Laplace de b(x) qui est la FRP de sNous trouvons G(z,0) et G(z,x)

ou est la probabilité que le système soit vide

et donc :

On peut maintenant définir par :

En reportant en sommation on note que :

en évaluant F(z) à z=1, on obtient F(1)=1-

On Utilise donc

La fonction génératrice de N, en indiquant les transformées de Laplace de s:

Page 10: Probabilité et Statistiques

5.0 Probabilités du nombre de clients dans le système

Afin d’évaluer les probabilités suivantes : prob[N=1] et prob[N=2], j’ai effectué un script Matlab pour trouver les équations régissant les probabilités de trouver un usager ou deux usagers dans le système. Dans ce script trla est la transformée de Laplace de la FDP du temps de service s.

Script prob3.m

syms z trla lambda ro;

z = 0g = ((1-ro)*(1-z)*trla)/((trla-z*lambda*(1-z)));

prob1 = eval(diff(g,'z'))prob2 = eval(diff(g,'z', 2))/2

Résultats du script prob3.m

prob1 =-1+ro+(1-ro)/trla*lambda prob2 =-(2-2*ro)/trla*lambda+1/2*(2-2*ro)/trla^2*lambda^2

Nous obtenons donc les formules suivantes pour les probabilités de 1 et 2 usagers dans le système.

Page 11: Probabilité et Statistiques

6.0 Modélisation et hypothèses

Le modèle de la succession des arrivées des requêtes est décrit est régie par le processus de Poisson de paramètre lambda. On peut utiliser le modèle des arrivées par le processus de Poisson quand les changements d’états ne se produisent pas à des moments fixés à l’avance. L’utilisation du processus de Poisson est indiqué pour tout modèle se répartissant sur une échelle de temps continue. Il modélise parfaitement l’idée de l’arrivée « au hasard » de personnes ou d’objets à un endroit donné.

Pour ce qui est des paramètres physiques du serveur j’avais proposé l’hypothèse que toutes opérations de lecture et écriture s’effectue à un moment ou la tête se trouve à un frontière entre deux secteurs. Ceci est un peu une exagération de la réalité étant donné que la tête peut se situer virtuellement à n’importe quel endroit sur le disque. Néanmoins, cette hypothèse permet de simplifier les calculs probabilistes et est plus acceptable pour un disque possédant un grand nombre de secteurs.

7.0 Influence des paramètres

Paramètre kLe paramètre k définit le nombre de secteurs sur le disque. Plus k est grand, plus le système est instable stable car le nombre de secteurs disponibles pour l’écriture va être grand permettant des temps d’accès et de traitements plus longs. Plus k est grand, plus les valeurs moyennes de temps s, q et W vont être élevés car la tête devra parcourir en moyenne une plus grande distance pour atteindre le secteur désiré. Plus k est grand, plus les valeurs moyennes du nombre de clients en attente Nq va être grand état donnée le moins grande rapidité à traiter les demandes. La croissance du paramètre k augmente les probabilité de trouver un ou deux utilisateurs dans le système.

Paramètre bLe paramètre b définit le nombre de secteur lut ou écrit à chaque à chaque accès. Plus le paramètre b est grand, moins le système est stable car le temps de lecture et d’écriture sera augmenter. Le paramètre b influence les valeurs moyennes de temps s, q et w dans le sens qu’ils vont être plus grand si b est grand car il faudra plus de temps de traitement, aussi il y aura plus de personne dans la file d’attente Nq et de personnes dans le système N. La croissance du paramètre b augmente les probabilités de trouver un ou deux personnes dans le système.

Paramètre rLe paramètre r définit la vitesse de rotation du disque. Plus le paramètre r est grand, plus le système est stable car le disque aura une plus grande vitesse d’accès au secteur désiré et une plus grande vitesse de lecture et d’écriture. Plus le paramètre r est grand, plus les valeurs moyennes de temps s, q et w seront petites étant donné que le système fonctionne plus rapidement. Le nombre de personnes moyen Nq et N va être plus petit car le traitement des requêtes va s’effectuer plus rapidement. La croissance du paramètre r diminue les probabilités de trouver un ou deux personnes dans le système.

Page 12: Probabilité et Statistiques

Paramètre Le paramètre définit le temps de traitement spécifique. Plus le paramètre est grand plus le système est instable car le temps de traitement des données sera plus long congestionnant donc le système. Les valeurs moyennes de temps s, q et w seront généralement plus grandes si est plus grand, car le temps s augmentera ainsi il y aura plus de personnes dans la file d’attente et le temps global sera évidemment augmenté. Le paramètre influence aussi le nombre de personne se trouvant dans le système et dans la file d’attente N et Nq dans le sens que si le temps de traitement est plus grand, plus de personnes seront en attente. La croissance du paramètre augmenter les probabilités de trouver une ou deux personnes dans le système.

Paramètre Le paramètre définit l’intensité du taux d’arrivée des clients par unité de temps. Plus le paramètre est grand (plus il tend vers 1), plus le système sera instable car le nombre de clients dans le système va être exprimé de façon exponentielle. Les valeurs moyennes de temps q et w seront généralement plus grandes si est plus grand, car le taux d’arrivé influencera le temps d’attente mais pas le temps de traitement s. Si est grand, le nombre de clients en attente Nq et le nombre de clients globaux dans le système N seront eux aussi grands. La croissance du paramètre fera augmenter les probabilités de trouver une ou deux personnes dans le système.

8.0 Conclusion

Dans ce rapport j’ai énoncé le cheminement parcouru afin de résoudre la problématique. J’ai suivi les conseils de Anna-Lyse de Performance et j’ai procédé en deux étapes. Dans la première étape, j’ai calculé la FDP et la FRP de s ainsi que les valeurs moyennes des cinq paramètres décrivant le système. Dans une seconde étape, j’ai calculé les Transformées de Laplace des FDP des paramètres de temps. J’ai aussi trouvé la fonction génératrice du nombre de client dans le système qui m’a servi à faire un calcul de probabilité sur le nombre de client dans le système.