É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));