Étude d’une politique de service SRPT

L’objectif de ce DM est l’étude d’un système de file d’attente où les processus sont élus selon une politique SRPT : Le processus dont le temps restant d’exécution est le minimum est choisi.

Simulateur

Le code suivant permet de simuler une file d’attente SRPT suivant plusieurs lois concernant le temps de service. On peut également jouer sur le fait de préempter ou non une tâche en cours lorsqu’un nouveau processus arrive. Ce code est simplement une modification par rapport au précédent DM.

library(plyr)
library(ggplot2)

Service <- function(n=1,typeservice,x,y) {
# genere un temps de service
  switch(typeservice,
         det = rep(1,n),
         uni = runif(n,x,y),
         gamma = rgamma(n,shape=x,scale=y),
         exp = rexp(n,x)
         )
}

FileSRPT <- function(n,lambda,typeservice,x,y,policy) {
    # simulates a M/GI/1 SRPT queue with different preemption policy
    # parameters:
    #    n :  total number of jobs
    #    lambda : arrival rate
    #    typeservice : service law (det uni gamma exp)
    #    x ,y : parameters of the service law
    #    policy: npmtn, pmtn, pmtn_restart, pmtn_reset
    # return value:
    #    vector with response time of each task assuming the queue is initially empty
    
    A <- rexp(n,lambda)         # inter arrival
    t1 <- cumsum(A)             # arrival dates
    t2 <- rep(NA,n)             # completion dates
    S <- Service(n,typeservice,x,y) # initial service times
    
    #### Variables that define the state of the queue
    t = 0               # current time
    remaining = S;      # how much work remains to do for each task
    running = NA        # index of the currently running task
    waiting = c()       # stack with tasks which have arrived and have not been completed yet
    next_arrival = 1    # index of the next task to arrive
    
    #### A few useful local functions 
    run_task = function() { # runs the last task of the waiting list
      if(length(waiting)>0) {
        # running <<- waiting[length(waiting)]
        # remaining[running] <<- switch(policy,
        #                              npmtn = S[running],
        #                              pmtn = min(S[running],remaining[running],na.rm=T),
        #                              pmtn_restart = S[running],
        #                              pmtn_reset = Service(1,typeservice,x,y)
        #                              )
        # waiting <<- waiting[-length(waiting)]
        
        if (policy == "spt_pmtn") { # Election based on service time
          running <<- waiting[which.min(S[waiting])];
        } else if (policy == "fifo") { # Election is fifo : Always the first of the list
          running <<- waiting[1];
        }
        else { # Election based on remaining time
          running <<- waiting[which.min(remaining[waiting])];
        }
        waiting <<- waiting[-which(waiting == running)];
      }
    }

    push_task = function() { # insert the next_arrival-th task to the waiting list
                             # and run it if there is preemption
      if ((policy != "fifo") & (policy != "spt")) { 
        if(!is.na(running)) {waiting <<- c(waiting,running)}
        running <<- NA
      }
      waiting <<- c(waiting,next_arrival)
      next_arrival <<- next_arrival+1 
      if(is.na(running)) { run_task() }
    }

    #### Main simulation loop
    while(TRUE) { 
      # Look for next event
      dt = NA
      if(next_arrival <=n) { dt = min(dt,(t1[next_arrival]-t), na.rm=T) }
      if(!is.na(running))  { dt = min(dt,remaining[running], na.rm=T)   }
      if(is.na(dt)) { break }
      
      # Update state
      t=t+dt
      if(!is.na(running)) {
        remaining[running] = remaining[running] - dt
        if(remaining[running]<=0) {
          t2[running] = t
          running = NA
          run_task()
        }
      }
      if((next_arrival<=n) & (t==t1[next_arrival])) {
        push_task()
      }
    }
    
    data.frame(val = t2-t1, policy = policy, lambda = lambda);
}

Etude de la file M/GI/1

Nous effectuons, comme lors du précédent DM, une étude du temps de réponse en fonction des différentes lois de temps de service. La graine permettant de générer les nombres aléatoires est réinitialisé après chaque sélection d’une politique : la simulation se fait, pour chaque politique, sur le même jeu de temps de service.

Temps de service exponentielle

n = 10000;     # Nombre de processus
type = "exp"   # Loi régisssant les temps de service
lamb_exp = 1   # Paramètre lambda de la loi exponentielle
resultat = data.frame();
for(pol in c("spt", "spt_pmtn", "srpt_pmtn", "fifo")) {
  set.seed(42);
  for(lamb in seq(from = 0.1, to = 0.9, by = 0.1)) {
    resultat = rbind(resultat, FileSRPT(n = n,lambda = lamb, policy = pol, x = lamb_exp, typeservice = type));
  }
}

resultat = ddply(resultat, c("lambda", "policy"), summarize,
                 tps_rep = mean(val),
                 tps_rep_max = max(val),
                 error = 2*sd(val)/sqrt(length(val)),
                 toperr = tps_rep + error,
                 boterr = tps_rep - error);

ggplot(data = resultat, aes(x = lambda, y = tps_rep, colour = policy)) + geom_line() + theme_bw() + scale_x_continuous(breaks = seq(from = 0.1, to = 0.9, by = 0.1)) + geom_errorbar(aes(ymax = toperr, ymin = boterr, width = 0.01));

On observe une différence bien marquée entre FIFO et les autres politiques. Les tâches les plus courtes ne sont pas forcément exécutées en premières. Les temps de réponse ne sont donc pas optimisés.

Pour mieux étudier les 3 autres courbes, réduisons l’échelle des ordonnées :

ggplot(data = resultat, aes(x = lambda, y = tps_rep, colour = policy)) + geom_line() + theme_bw() + scale_x_continuous(breaks = seq(from = 0.1, to = 0.9, by = 0.1)) + geom_errorbar(aes(ymax = toperr, ymin = boterr, width = 0.01)) + ylim(min = 1, max = 5);
## Warning: Removed 1 rows containing missing values (geom_path).

Le SRPT est le plus efficace : à chaque arrivée, on compare l’ensemble des temps restant pour ne garder que le plus faible. On cherche ainsi à évacuer le plus rapidement les tâches de la liste des tâches en attente. La version SPT préemptive est légèrement moins efficace car la comparaison se fait sur les seuls temps de service. Enfin, la SPT non préemptive est encore moins performante car on ne change de tâche que lorsque une autre s’est terminée.

Etudions maintenant le temps de réponse maximal de chaque politique :

ggplot(data = resultat, aes(x = lambda, y = tps_rep_max, colour = policy)) + geom_line() + theme_bw() + scale_x_continuous(breaks = seq(from = 0.1, to = 0.9, by = 0.1));

Ces résultats ne sont pas surprenants : les politiques de la famille SPT privilégient l’élection des tâches les plus courtes en premières. Les tâches les plus longues sont donc reportées à la fin ce qui augmente d’autant plus leur temps de réponse.

Temps de service unique

On effectue la simulation avec un temps égal à 1 pour toutes les tâches. Certaines courbes semblent se recouvrir, ajoutons un léger bruit artificiel afin de les distinguer (jittering).

ggplot(data = resultat, aes(x = lambda, y = tps_rep, colour = policy)) + geom_line(position = position_jitter(w = 0, h = 0.05)) + theme_bw() + scale_x_continuous(breaks = seq(from = 0.1, to = 0.9, by = 0.1)) + geom_errorbar(aes(ymax = toperr, ymin = boterr, width = 0.01));

Ici, les politiques SPT non préemptive, SRPT préemptive et FIFO semblent être les plus efficaces et équivalentes. Les tâches sont exécutées dans l’ordre de leurs arrivées et d’un coup dans le cas de FIFO et SPT non préemptive. Pour ce qui est de la version SRPT, la tâche élu est forcément celle entamée, la tâche préemptée est donc réélue immédiatement.

En revanche, pour SPT préemptive, la tâche actuelle est remise en fin de liste d’attente avant d’élire un nouveau processus. La comparaison se faisant sur les temps de service, le premier de la liste est élu (fonctionnement de la fonction R which.min()), donc une tâche qui aurait pû être terminée rapidement (en comparaison avec la tâche arrivante) se trouve remise dans la file d’attente. Les temps de réponse sont donc plus importants. Si which.min() retournait la dernière tâche de la liste, les temps de réponse seraient les même pour les 3 politiques.

Les 4 fonctions ayant le même comportemant, l’étude des temps de réponse maximaux est inutile.

Temps de service uniforme

Les temps de service suivent une loi uniforme sur l’intervalle \([0;1]\) Comme dans le premier test, la politique FIFO est la moins performante. Cependant, cet écart de performance est moins prononcé que précédemment.

On suppose que cela est dû au fait que, contrairement à la loi exponentielle, la loi uniforme restreint l’intervalle de temps de service (aucune valeur plus grande que 2 n’est générée). Le résultat se rapproche donc de celui observé avec un temps de service unique.

La simulation suivante a pour but d’appuyer cette hypothèse en renouvelant l’expérence avec l’intervalle \([0.75;1.25]\) puis \([0.9,1.1]\). On utilise à nouveau un léger bruit artificiel pour distinguer les courbes trop proches.

SPT non préemptive est à nouveau la politique la moins efficace et les 3 autres ont des performances comparables, l’hypothèse semble donc être vraie.

De nouveau, le temps de réponse max en mode FIFO est bien plus faibles qu’avec les autres méthodes.

Temps de service de loi Gamma

On fait ici 2 simulations, une où les paramètres de la loi gamma sont \((0.2;5)\) et une où ils sont à \((4;0.25)\).

On commence par donner la densité de ces 2 fonctions

On lance ensuite la simulation. En ce qui concerne la première loi gamma, le résultat semble assez similaire à la loi exponentielle. La courbe de la densité est d’ailleurs similaire à une loi exponentielle et l’efficacité de la politique FIFO est nettement moins bonne que les trois autres.

Avec la seconde loi gamma, on a peu de faibles valeurs générées pour les temps de service. Les politiques de la famille SPT ont donc plus de difficultés à évacuer rapidement les tâches de la file d’attente et l’écart en performance est donc moins marqué avec FIFO.

Ci-dessous sont présentées les courbes des temps de réponse maximaux.