RICM4: Évaluation de Performance
Table of Contents
Sitemap
Informations Générales
Florence Perronnin est chargée des cours et Arnaud Legrand s'occupe des TDs.
Le planning avec les salles de cours est disponible ici.
La page de l'an dernier est ici.
Voici un PAD pour échanger facilement et rapidement des informations.
Programme du cours
Semaine | Cours (Jeudi, 8h00) | TD (Vendredi, 11:30 ou exceptionnellement 8:00) |
---|---|---|
18-19 janvier | Slides d'introduction + Modélisation des files d'attente | Simulation à évènement discret d'une M/M/1 |
25-26 janvier | Modélisation des files d'attente et des systèmes Markoviens | Pas de TD |
1-2 février | Chaînes de Markov à Temps Discret | Simulation à évènement discret d'une M/M/1 |
8-9 février | Chaînes de Markov à Temps Discret | Présentation du DM et exercice 2 d'un Quick de l'an dernier (chocolats) |
15-16 février | Processus de Poisson | Quick de l'an dernier |
22-23 février | Vacances | Vacances |
1-2 mars | Processus de Poisson | Aloha! |
8-9 mars | Quick | Aloha! |
15-16 mars | Chaîne de Markov à temps continu | Discussions sur le DM + Cache-cache (correction et code R) |
22-23 mars | Processus de naissance et de mort, file M/M/1 | TD sur les iles d'attente. En bonus, un aide mémoire sur la M/M/1 et sur la M/M/K/K. |
29-30 mars | Régression linéaire (Arnaud) | Réseaux de Jackson (Florence) |
3 avril | La régression linéaire en pratique + open questions (Arnaud: le 3 avril à 10h00) |
DM/Projet
Énoncé
Simuler, analyser et comparer les politiques d'au moins trois des files d'attentes suivantes:
- Fair sharing
- à chaque instant \(t\), si on note \(M_t\) le nombre de tâches actuellement présentes sur le serveur. Toutes les tâches soumises et non terminées s'exécutent en parallèle sur le serveur et avancent donc à une vitesse \(1/M_t\) jusqu'à ce qu'une tâche se termine ou qu'une tâche supplémentaire soit soumise dans le système.
- FIFO
- déjà faite en TD…
- LIFO
- Lorsqu'une tâche se termine, la tâche que l'on exécute est la dernière arrivée.
- LIFO avec préemption
- Lorsqu'une tâche arrive dans le système, on préempte la tâche qui s'exécutait pour exécuter la nouvelle tâche. Cette nouvelle tâche peut se faire préempter à son tour si une nouvelle tâche arrive, etc. Lorsque la nouvelle tâche se termine, on reprend la dernière tâche interrompue là où on l'avait arrêtée.
- LIFO avec restart
- Même principe que LIFO avec préemption, à ceci près qu'on recommence la dernière tâche interrompue du début, comme si elle n'avait jamais été exécutée, en retirant nouveau un temps de service.
- SPT
- Shortest Processing Time first. Lorsqu'une tâche se termine, on exécute non pas la première ou la dernière tâche arrivée mais celle ayant le plus petit temps de traitement.
- SRPT
- Shortest Processing Time first. Lorsqu'une tâche se termine ou qu'une nouvelle tâche arrive, on exécute la tâche pour lequel il reste le moins de travail à effectuer.
On supposera que les arrivées suivent une loi exponentielle de taux \(\lambda\) et que les temps de service sont d'espérance 1. Vous comparerez les performances (en fonction de \(\lambda\)) des trois politiques selon que le temps de service suit une loi:
- uniforme entre 0.5 et 1.5
- exponentielle de taux 1
gamma
de paramètreshape=.1
etrate=.1
Vous vérifierez l'espérance et la variance de vos échantillons…
Je vous encourage à avoir une seule fonction de simulation pour l'ensemble des scénarios considérés.
Objectifs pédagogiques
Savoir:
- savoir collecter et organiser les données d'un grand nombre de
simulations (
data.frame
) - savoir calculer des intervalles de confiance (avec
tidyr
etdplyr
) - savoir faire une représentation graphique adaptée (avec
ggplot2
)
Avoir compris:
- la notion d'état du système et comment on le met à jour
- la notion de stabilité d'un système
- la limite de la notion d'intervalle de confiance
Consignes
- Rendu en Rmd sur rpubs pour le 16 mars
- À faire en binôme. Chaque binôme choisi ses trois politiques dans la
liste suivante. Un triplet ne peut être pris que par un binôme afin
de s'assurer que toutes les politiques sont codées et qu'on puisse
vérifier qu'elles sont correctement implémentées en faisant des
validations croisées. Premier servi, à indiquer sur le PAD:
- FIFO, SPT, LIFO-preemption
- FIFO, LIFO, SPT
- FIFO, Fair-sharing, LIFO
- FIFO, LIFO-preemption, SRPT
- FIFO, LIFO-restart, Fair-sharing
- FIFO, SRPT, LIFO-restart
- Vous vous mettrez tous d'accord sur le format de data-frames utilisées afin de sauvegarder les résultats des simulations (et vous les mettrez à disposition (dans un git, framadrop, ou autre). Ça permettra de charger les résultats de différents binômes pour les comparer.
- Partage d'information encouragé mais:
- faites en sorte que ça soit réciproque
- indiquez brièvement à la fin du document avec qui vous avez échangé et sur quoi
- Une séance de TD sera dédié à une brève présentation de vos résultats en vous appuyant sur ce qui est dans Rpubs.
TDs
Simulation à évènement discrets de file d'attentes
L'objectif du TD est de comprendre la bonne façon d'organiser une simulation à évènement discret (sans reposer trop intensément sur les hypothèse type arrivées de Poisson) avec la notion d'état du système, d'évènements possible et de mise à jour de l'état du système. Si vous lisiez des bouquins qui expliquent comment faire de la simulation à évènement discret, il n'est pas clair que ça vous aiderait vraiment. Le mieux est d'en écrire un ensemble pour que vous compreniez comment procéder. Pour celà, on va s'intéresser au cas simple d'une file d'attente.
Modélisation et principe de simulation
- Paramètres du système
- Taux d'arrivée dans le système
lambda
(en tâches par seconde) - Taux de service du système
mu
(en tâches par seconde) - Politique de service (on va coder FIFO là mais on essaye de coder tout ça de la façon la plus générique possible)
- Taux d'arrivée dans le système
Description des variables d'état importantes:
- Date courante
t
- Dates d'arrivées
Arrival
: dates calculées à partir d'inter-arrivées (input) - Temps de service
Service
: temps générés (input) - Temps résiduel
Remaining
: initialisé àNA
, passe à Service quand un job arrive dans le système et décroit alors vers 0. - Date de terminaison
Completion
: initialisé àNA
, passe à la date courantet
lorsqueRemaining
passe à 0. - Client actuellement servi
CurrClient
(utile pour caractériser la politique de service utilisée): initialisé àNA
J'ai finalement rajouté une variable
NextArrival
qui permet d'éviter des contortions ou des notations un peu lourdes. Cette variable est initialisée à1
et sera incrémentée jusqu'à dépasser le nombre de tâches total.- Date courante
- Évolution possible
- Soit une arrivée
- Soit la terminaison d'une tâche
Structure du code:
while(T) { dtA = ... # temps jusqu'à la prochaine arrivée dtC = ... # temps jusqu'à la prochaine terminaison if(is.na(dtA) & is.na(dtC)) {break;} dt = min(dtA,dtC) # Mettre à jour comme il faut. }
Première version faite en TD
set.seed(37); N = 10; # N <- 100; # N <<- 100; Arrival = cumsum(rexp(n=N, rate = .2)); Service = rep(N,x=1); Remaining = rep(N, x=NA); Completion = rep(N, x=NA); t = 0; CurrentTask = NA; NextArrival = 1; while (TRUE) { print(t); print(Arrival); print(Service); print(Remaining); dtA = NA; dtC = NA; if(length(Arrival[Arrival>t])>0) { dtA = head(Arrival[Arrival>t],n=1)-t # temps jusqu'à la prochaine arrivée } if(!is.na(CurrentTask)) { dtC = Remaining[CurrentTask]; # temps jusqu'à la prochaine terminaison } if(is.na(dtA) & is.na(dtC)) { break; } dt = min(dtA,dtC,na.rm=T) # Mettre à jour comme il faut: # la date t = t + dt; # les arrivées if((NextArrival <=N) & (Arrival[NextArrival] <= t)) { ## je met un <= et pas un == car 3-2.9!=0.1 ... Remaining[NextArrival] = Service[NextArrival]; NextArrival = NextArrival + 1; } # le remaining if(!is.na(CurrentTask)) { Remaining[CurrentTask] = Remaining[CurrentTask] - dt ; if(Remaining[CurrentTask] <= 0) { Completion[CurrentTask] = t; Remaining[CurrentTask] = NA; } CurrentTask = NA; } # et currentTask (politique d'ordonnancement: FIFO) WaitingList=(1:N)[!is.na(Remaining)]; if(length(WaitingList)>0) { CurrentTask = head(WaitingList,n=1); } } print(Completion)
Pour la prochaine fois:
- Repartir de votre propre version (si vous voulez bien comprendre comment ça marche) ou à défaut de celle donnée ci dessous (si vous renoncez à écrire ce code vous-même proprement…) et l'encapsuler de façon à pouvoir facilement controler les paramètres du système (lambda, mu)
Fixer le taux de service
mu
à 1 et étudier (je veux une courbe!) le temps de réponse en fonction du taux d'arrivéelambda
. Idéalement, vous devriez obtenir quelque chose du genre:
Bibliographie
- Fooling the masses by Georg Hager ;)
- Mor Harchol Balter - Performance Modeling and Design of Computer Systems: Queuing Theory in Action Cambridge University Press, 2013 http://www.cs.cmu.edu/~harchol/PerformanceModeling/book.html
- Un MOOC qui commence bientôt sur les files d'attente: https://www.edx.org/course/understanding-queues
- P. Brémaud, Initiation aux Probabilités
- R. Jain, The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling, Wiley- Interscience, New York, NY, April 1991.
- Jean-Yves Le Boudec, Performance Evaluation Of Computer And Communication Systems. Une jolie vidéo présentant le livre.