Les files d’attentes

I/ Définition

Une file d’attente est caractérisée par :
– Un flot d’arrivées
– Un mécanisme de service
– Une file d’attente
– Une discipline de service

Capacité de la file d’attente :
– nombre de places possibles : limité ou illimité.
– Si capacité limitée : les clients supplémentaires sont perdus ou rejoignent une autre file d’attente.
– Le nombre de clients dans le système est différent du nombre de clients dans la file d’attente

Discipline de service :

• règle d’ordonnancement des clients au service.
  • FIFO : first in first out (exemple file d’attente à la sécu, 1er arrivé 1er servie)
  • LIFO : Last in first out (ex : l’ascenseur : dernier rentré, premier sortie)
  • PS : processor sharing, un serveur donne à chaque client en attente une “tranche” de service. (c’est du partage de ressources, le processeur accomplit un bout de tache sur un client puis passe au suivant ... )
  • ALEA un serveur libre choisit un client au hasard dans la file
  • Priorité : on ajoute une suite Un, n appartient à N+, au flot des arrivées où Un est une variable aléatoire prenant ses valeurs dans l’ensemble des classes de priorités P. Un=i, signifie que le neme client, arrivant au temps Tn est de la classe i.
  • Priorité préemptive : le programme preemptif passe en premier devant tous les autres et est servi en premier

Notation de KENDALL A/B/C/D/E
– A : statistique du processus d’arrivée (M = markovien ; D=déterministe ; G=générale)
– B : statistique des lois de service (M = markovien ; D=déterministe ; G=générale)
– C : nombre de serveurs
– D : nombre de clients dans le système
– E : discipline du service
– M/M/1 ==> Modèle le plus classique
– M/M/5/20
– M///5/infini/LIFO

LOI DE LITTLE

cette loi part du principe que sur le terme, la vitesse d’arrivée = vitesse de traitement

HYPOTHESES

• Lorsqu’un client, ayant terminé son service, quitte le système, il laisse, en moyenne, derrière lui, un nombre de clients égal à E(k). Ce client a trouvé en arrivant E(k) clients déjà présents et a passé dans le système un temps, E(T).
• Nous supposons que :
  • Le nombre moyen des arrivées est égal au nombre moyen des départs du système.
  • La longueur moyenne de la file lors des arrivées est égale à la longueur moyenne de la file lors des départs

ENONCE

• Si on appelle, l, le taux moyen des arrivées on a :
  Nombre moyen de clients arrivés pendant le séjour du client dans le système =
  \lambda E(t) = nombre moyen de clients qu’il laisse

Et en régime permanent, si T temps passé dans la file :

E(k)= \lambda E(T)
\bar N = \lambda \bar T

\bar N : nombre de client dans le système
\lambda : taux moyen d’arrivé des clients
\bar T : temps passé dans la file

VALIDITE
– Régime permanent
– Les formules de Little sont valides pour les files G/G/S. Elles ont un caractère très général. En effet, il n’ y a aucune restriction quant à :

– Elles peuvent prendre en compte le cas où il existe plusieurs classes de clients mais la discipline de service doit être définie, nous avons considéré la discipline FIFO.

II/ File M/M/1

M/M/1 = statistique du processus d’arrivée : markovien / statistique des lois de service : markovien / 1 serveur

Les formules à retenir :

État : nombre de clients, k, dans le système

\rho_{0} = \left (1-{\lambda \over \mu} \right )=1-\rho
\rho_{0} : probabilité d’avoir 0 clients dans la file d’attente

Taux de trafic, r (charge, activité du serveur) :

\rho = {\lambda \over \mu}
\rho : taux de traffic
\lambda : taux moyen d’arrivée des clients
\mu : taux moyen de traitement, débit du serveur, taux de service du serveur

• Condition de stabilité :
  • activité du serveur <1

\rho = {\lambda \over \mu} < 1

• \lambda<\mu
  • Débit d’entrée < débit du serveur
  • Temps moyen inter-arrivée > temps de service moyen
• Si serveur saturé (\rho—>1) :
  • La distribution des intervalles de temps séparant deux départ consécutifs de la file saturée tend vers la distribution des temps de service

Nombre moyen de clients dans le système, N

\bar N = {\rho \over {1-\rho}}
\rho : taux de traffic
\bar N : Nombre de client dans le système

Nombre moyen de clients dans la file, E(v)

E(\nu) = {\rho^{2} \over {1-\rho}}
\rho : Taux de traffic
E(\nu) : Nombre moyen de client dans la file

Temps moyen, T, passé par un client dans le système

\bar T = {1 \over \mu}{1 \over {1-\rho}}

\rho : taux de traffic
\bar T : temps passé par un client dans le système
\mu : taux moyen de traitement, débit du serveur, taux de service

III/ File M/M/S

M/M/S = statistique du processus d’arrivée : markovien / statistique des lois de service : markovien / S serveurs

Les formules à retenir :

Taux de trafic

\rho = {\lambda \over {S\mu}} < 1

\rho : taux de traffic
\lambda : taux moyen d’arrivée des clients
\mu : taux moyen de traitement, débit du serveur, taux de service du serveur
S : Nombre de serveurs

Nombre moyen de guichets, g, occupés :

\bar g = {\lambda \over \mu}

\bar g : Nombre de guichets occupés
\lambda : taux moyen d’arrivée des clients
\mu : taux moyen de traitement, débit du serveur, taux de service du serveur

Nombre moyen de clients, v , dans la file :
k>s, k : nombre de clients, s nombre de serveurs

\nu= {1 \over {S&nbsp;!S}} \left ({\lambda \over \mu} \right) ^{S+1} {1 \over {\left(1- {\lambda \over {S \mu}}\right)^{2}}} \rho_{0}

\nu : nombre moyen de clients dans la file
\lambda : taux moyen d’arrivée des clients
\mu : taux moyen de traitement, débit du serveur, taux de service du serveur
\rho_{0} : probabilité qu’il y ait 0 client dans le système
S : nombre de serveurs

Temps d’attente moyen, tf , dans la file :

t_{f}= {1 \over {S&nbsp;!}} \left({\lambda \over \mu} \right)^{S} {1 \over {S\mu}} {1 \over {\left (1- {\lambda \over {S\mu}} \right )^{2}}}\rho_{0}

t_f : temps d’attente moyen des clients dans la file
\lambda : taux moyen d’arrivée des clients
\mu : taux moyen de traitement, débit du serveur, taux de service du serveur
\rho_{0} : probabilité qu’il y ait 0 client dans le système
S : nombre de serveurs

Nombre moyen de clients dans le système

\bar N= {\lambda \over \mu} \left ( \mu \bar t _f +1 \right)

\bar N : Nombre de client dans le système
t_f : temps d’attente moyen des clients dans la file
\lambda : taux moyen d’arrivée des clients
\mu : taux moyen de traitement

Temps d’attentes dans le système

\bar T= {\bar N \over \lambda

\bar T : temps d’attente dans le système
\bar N : Nombre de client dans le système
\lambda : taux moyen d’arrivée des clients