Files d’attente et réseaux de files d’attente

Théorie des files d’attente

Il y a deux approches d’évaluation d’un système : l’approche qualitative et l’approche quantitative. Files d’attente et réseaux de files d’attente 45 L’évaluation qualitative s’intéresse à définir des propriétés structurelles et comportementales (absence de blocage, existence d’une solution, gestion de la concurrence,…). Cette approche fait appel aux langages de programmation et aux réseaux de Pétri (voir section précédente). L’analyse quantitative est essentiellement réalisée par les files d’attente (FA) et consiste à calculer les critères de performances (débit, temps de réponse,…). Dans cette section, nous allons étudier les bases fondamentales des files d’attente et les caractéristiques à mettre en œuvre dans une étude des performances d’un réseau par les files d’attente.

L’outil file d’attente du point de vue de la modélisation

Un objet de type file d’attente est apte à m odéliser les phénomènes de consommation de ressources. Le terme ressource désigne toute composante physique, logique ou humaine qui peut être nécessaire à la réalisation d’une activité. Une activité peut être définie ici comme le processus de cheminement d’une entité appelée « client » et qui demande, tout au long de son cycle de vie, l’accès à une succession de ressources indispensables pour sa r éalisation. On peut dès alors dire que la théorie des files d’attente s’attache à m odéliser et à analyser de nombreuses situations très diverses et qui relèvent toutes du schéma descriptif suivant : deux unités (clients) arrivent à intervalles aléatoires dans un système comportant plusieurs serveurs auxquels elles vont adresser une requête pour recevoir un service. Les unités à l’extérieur du système constituent la source ; elles peuvent être en nombre limité ou illimité, et elles pénètrent dans le système par une entrée. Si tous les serveurs sont occupés, les unités sont amenées à at tendre, formant ainsi une ou plusieurs files d’attente. Ces files peuvent être organisées en fonction de priorités variées ; de même, l’admission au service peut se faire par des règles particulières. Après avoir été servies (ce qui suppose un arrêt chez un ou plusieurs serveurs selon le cas), les unités quittent le système par la sortie pour rejoindre la source. Figure 26 : structure générale d’un système de file d’attente. Arrivée de clients Départ de clients 46 L’admission dans le système et l’exécution du service obéissent à un processus des arrivées et à un processus de service qui commandent le processus de départ. La grande variété des processus susceptibles d’être utilisés a conduit à établir une classification. Cette classification comprend six indications mises sous forme d’étiquettes A/B/S/K/M/D (cette notation est connue sous le nom de notation de KENDALL) où : A : désigne la nature du processus des arrivées ; B : désigne la nature du processus de service ; S désigne le nombre de serveurs ; K : désigne le nombre de positions d’attente ; M : désigne le maximum d’unités dans la source ; D : désigne la discipline de service. Pour caractériser la nature des processus des arrivées et du service, on utilise les symboles : M pour la loi exponentielle, D pour la loi constante (ou déterministe), Ek pour la loi d’Erlang d’ordre k, Hr pour la loi hyper exponentielle d’ordre r et G pour la loi générale. La liste suivante énumère les disciplines de service qui peuvent être mises en œuvre dans le processus d’arrivées : – premier arrivé premier servi (PAPS ou FIFO [First In First Out]) – dernier arrivé premier servi (DAPS ou LIFO [Last in First out]) – aléatoire ou « Random Selection for Service » (RSS)) – tourniquet ou « round robin (RR) » : chaque unité dans le système est servie à tour de rôle et pour un laps de temps égal à un quantum de service. – processeur partagé (PS), cas limite de RR où le quantum de service temps vers zéro. – Prioritaire (PR).

Modélisation d’une ressource

Dans un contexte général, on peut partitionner une ressource en deux ensembles en fonction de son comportement vis-à-vis du client qui en fait la demande : l’ensemble des ressources actives et l’ensemble des ressources passives. Les ressources actives, appelées aussi serveurs ou files d’attente, sont celles délivrant un service dont l’attente dans la file associée au serveur ne dépend que du serveur. Une ressource active représente donc une ressource qui possède des propriétés de traitement direct sur le client (ex : CPU, disque,…). Analytiquement un s erveur se caractérise par une loi de 47 probabilité. Schématiquement, une ressource active se dessine par un cercle, pour symboliser le serveur, accolé à un rectangle ouvert pour représenter sa file d’attente. Figure 27 : schéma d’une ressource active. Une ressource passive se compose aussi d’une file d’attente, mais elle est dépourvue de serveur. La réquisition d’une ressource passive peut s’avérer nécessaire pour la conduite d’une activité sans traitement à priori (ex : tampon mémoire, droits d’accès,…). Ces ressources se distinguent par le fait que les clients obtiennent une ou plusieurs instances de la ressource (par exemple une partition de mémoire) au lieu d’un service. Généralement, le nombre de ressources à acquérir est en nombre limité, et, quand toutes sont attribuées, les demandeurs doivent attendre. Schématiquement une ressource passive se dessine différemment. Le triangle équilatéral ayant sa pointe dirigée vers le bas symbolise la libération de la ressource alors que celui ayant sa p ointe orientée vers le haut représente l’allocation de ressources. Le rectangle qui relie ces deux triangles représente le réservoir de ressources passives qui peuvent être attribuées et le nombre n se trouvant dans ce triangle indique le nombre total des instances existantes.