Simulateur

Le code suivant permet de simuler une file d’attente LIFO suivant plusieurs lois pour 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.

set.seed(666)
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)
         )
}

FileLIFO <- function(n,lambda,typeservice,x,y,policy) {
    # simulates a M/GI/1 LIFO 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 = rep(NA,n)  # 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)]
      }
    }

    push_task = function() { # insert the next_arrival-th task to the waiting list
                             # and run it if there is preemption
      if(policy != "npmtn") {
        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);
}

Comparaison des lois de service

On commence par faire une comparaison des différentes lois concernant le temps de service. On utilisera des paramètres permettant d’avoir pour chaque loi une espérance égale à 1 afin de rendre les comparaisons pertinentes par la suite.

df = data.frame(type = rep("det", 50), tps = Service(n = 50, typeservice = "det"), num = c(1:50));
df = rbind(df, data.frame(type = rep("uni", 50), tps = Service(n = 50, typeservice = "uni", x = 0, y = 2), num = c(1:50)));
df = rbind(df, data.frame(type = rep("exp", 50), tps = Service(n = 50, typeservice = "exp", x = 1), num = c(1:50)));
df = rbind(df, data.frame(type = rep("gamma", 50), tps = Service(n = 50, typeservice = "gamma", x = 4, y = 0.25), num = c(1:50)));

ggplot(data = df, aes(x = num, y = tps)) + geom_histogram(stat = "identity") + theme_bw() + facet_grid(type~., scale = "free_y");

La première loi retourne une valeur constante pour le temps de service.

La seconde retourne des valeurs uniformes sur un intervalle donné (ici dans l’intervalle $[0.5;1.5]$).

La troisième loi à une forte probabilité de retourner une faible valeur et une plus faible de retourner une grande valeur, il s’agit de la loi exponentielle (de paramètre $\lambda = 1$).

La dernière correspond à la loi Gamma (de paramètre $k = 4, \theta = 0.25$). Ci-dessous, la distribution de la loi gamma utilisée :

Etude de la file M/M/1

Dans cette partie, on s’intéresse à l’évolution du temps de réponse moyen par tâche en fonction du débit et du mode de gestion concernant la préemption. Le temps d’inter-arrivé ainsi que le temps de service sont modélisés par une loi exponentielle.

n = 2000;     # 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(lamb in seq(from = 0.1, to = 0.9, by = 0.1)) {
  for(pol in c("npmtn", "pmtn", "pmtn_restart", "pmtn_reset")) {
    resultat = rbind(resultat, FileLIFO(n = n,lambda = lamb, policy = pol, x = lamb_exp, typeservice = type));
  }
}

resultat = ddply(resultat, c("lambda", "policy"), summarize,
                 tps_rep = mean(val),
                 error = qnorm(0.975)*sd(val)/sqrt(n),
                 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));

Le graphique ci-dessus présente les résultats pour un système de 2000 processus. On constate que les temps de réponse sont similaires ainsi que leurs variabilités pour les politiques non préemptive, préemptive avec réinitialisation et préemptive avec reprise.

En ce qui concerne la politique préemptive avec redémarrage, on observe des temps de réponses qui augmentent d’avantage que les autres lorsque le débit d’entrée des tâches augmente (surtout à partir de $\lambda = 0.5$). L’intervalle de confiance est également élevé ce qui traduit une forte variabilité.

Etude de la file M/GI/1

On mène ici le même type d’étude avec d’autres lois concernant le temps de service

n = 2000;     # Nombre de processus
type = "det"  # Loi régisssant les temps de service
resultat = data.frame();
for(lamb in seq(from = 0.1, to = 0.9, by = 0.1)) {
  for(pol in c("npmtn", "pmtn", "pmtn_restart", "pmtn_reset")) {
    resultat = rbind(resultat, FileLIFO(n = n,lambda = lamb, policy = pol, typeservice = type));
  }
}

n = 2000;     # Nombre de processus
type = "uni"  # Loi régisssant les temps de service
min = 0       # Tps de service minimal
max = 2       # Tps de service maximal
resultat = data.frame();
for(lamb in seq(from = 0.1, to = 0.9, by = 0.1)) {
  for(pol in c("npmtn", "pmtn", "pmtn_restart", "pmtn_reset")) {
    resultat = rbind(resultat, FileLIFO(n = n,lambda = lamb, policy = pol, x = min, y = max, typeservice = type));
  }
}

n = 2000;       # Nombre de processus
type = "gamma"  # Loi régisssant les temps de service
shape = 5       # Paramètre k
scale = 0.2     # Paramètre theta
# Paramètre theta
resultat = data.frame();
for(lamb in seq(from = 0.1, to = 0.9, by = 0.1)) {
  for(pol in c("npmtn", "pmtn", "pmtn_restart", "pmtn_reset")) {
    resultat = rbind(resultat, FileLIFO(n = n,lambda = lamb, policy = pol, x = shape, y = scale, typeservice = type));
  }
}

n = 2000;       # Nombre de processus
type = "gamma"  # Loi régisssant les temps de service
shape = 2       # Paramètre k
scale = 0.5     # Paramètre theta
resultat2 = data.frame();
for(lamb in seq(from = 0.1, to = 0.9, by = 0.1)) {
  for(pol in c("npmtn", "pmtn", "pmtn_restart", "pmtn_reset")) {
    resultat2 = rbind(resultat2, FileLIFO(n = n,lambda = lamb, policy = pol, x = shape, y = scale, typeservice = type));
  }
}