Accueil > Informatique > RCP101 : Recherche opérationnelle et aide à la décision > Les files d’attentes

Les files d’attentes

lundi 27 juillet 2009, par Pti Gars

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 à :

la loi d’arrivée, la loi des services, le nombre de serveurs.

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$

- Débit d’entrée < débit du serveur
- Temps moyen inter-arrivée > temps de service moyen
Si serveur saturé (—>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 !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 !}} \left({\lambda \over \mu} \right)^{S} {1 \over {S\mu}} {1 \over {\left (1- {\lambda \over {S\mu}} \right )^{2}}}\rho_{0}$

: 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
: 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

Les files d’attentes

I/ Définition

LOI DE LITTLE

la loi d’arrivée, la loi des services, le nombre de serveurs.

II/ File M/M/1

III/ File M/M/S

Informatique

Dans la même rubrique