RICM4: Évaluation de Performance

Table of Contents

Sitemap

---> misc
| ---> 2016
| ---> 2015
| ---> 2014
| ---> 2013
| ---> 2012
`--> Agenda

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ètre shape=.1 et rate=.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 et dplyr)
  • 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:
    1. FIFO, SPT, LIFO-preemption
    2. FIFO, LIFO, SPT
    3. FIFO, Fair-sharing, LIFO
    4. FIFO, LIFO-preemption, SRPT
    5. FIFO, LIFO-restart, Fair-sharing
    6. 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:
    1. faites en sorte que ça soit réciproque
    2. 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)

  • 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 courante t lorsque Remaining 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.

  • É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ée lambda. Idéalement, vous devriez obtenir quelque chose du genre:

    MM1.png

Bibliographie