L’objectif est d’analyser l’importance de la distribution du temps de service sur le temps de réponse dans une file d’attente M/GI/1 avec un ordonnancement LIFO. Le processus d’arrivée est un processus de Poisson de taux (débit), les clients ont un temps de service de moyenne 1 pris comme unité de temps de référence.

Simulation de la file LIFO

set.seed(10)
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),
         gamma1 = rgamma(n,shape=x,scale=y),
         gamma2 = 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()
      }
    }
    
    #t2-t1
    df <-data.frame(entree=t1,sortie=t2,diferentiel=t2-t1,servicelaw=typeservice,policy=policy,lambda=lambda)
    df
}    

1. Nature des lois de service

Les explications autour des lois sont issus de notre compréhension générale des explications fournies sur http://www.jybaudot.fr/General/indexstats.html

2. Etude de la file M/M/1 - LIFO

Nous avons choisis de similuer avec une file de 1000 jobs, afin d’avoir un temps de simulation correct et des données représentatives.

res <- data.frame()
lambda_seq <- seq(from=0.2,to=0.8,by=0.2)


for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="npmtn"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="pmtn"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="pmtn_restart"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="pmtn_reset"))
}
res_calc = ddply(res,c("lambda","policy"),summarise,Temps_moyen_service=mean(diferentiel))

ggplot(data=res_calc,aes(x=lambda,y=Temps_moyen_service,color=policy)) + geom_point() + geom_line() + xlab("Fréquence d'arrivée") + ylab("Temps moyen de réponse") + ggtitle("Evolution du temps de réponse M/M/1") + scale_color_brewer(palette="Set1",name="Mode ",breaks=c("npmtn","pmtn","pmtn_restart","pmtn_reset"),labels=c("Non préemptif","Préemptif - resume ","Préemptif - restart ","Préemptif - reset"))

plot of chunk unnamed-chunk-2

Le mode préemptif - restart (redélarrage du même service) nous retourne un temps de réponse nettement supérieurs aux autres modes de gestion.

3. Etude de la file M/GI/1 - LIFO

Non-préemptif :

res <- data.frame()
lambda_seq <- seq(from=0.2,to=0.8,by=0.05)

for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="uni",x=0.5,y=5,policy="npmtn"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="det",x=0.5,y=5,policy="npmtn"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma1",x=1,y=1/lambda_seq[i],policy="npmtn"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma2",x=0.5,y=1/lambda_seq[i],policy="npmtn"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="npmtn"))
}
res_calc = ddply(res,c("lambda","servicelaw"),summarise,Temps_moyen_service=mean(diferentiel))

ggplot(data=res_calc,aes(x=lambda,y=Temps_moyen_service,color=servicelaw)) + geom_point() + geom_line() + xlab("Fréquence d'arrivée") + ylab("Temps moyen de réponse") + ggtitle("Evolution du temps de réponse [Non Préemptif]") + scale_color_brewer(palette="Set1",name="Loi",breaks=c("uni","det","gamma1","gamma2","exp"),labels=c("Uniforme","Déterministe","Gamma (série 1)","Gamma (série 2)","Exponentielle"))

plot of chunk unnamed-chunk-3

On observe une explosion du temps de réponse pour un temps de service suivant une loi uniforme. En ce qui concerne la loi exponentielle, observe une certaine instabilité dans le temps de réponse, qui croit en “dent de scie”. En ce qui concerne la loi Gamma, le temps de service tend à diminuer, on retrouve l’idée d’un “cache” évoqué plus tôt.

Préemptif - Resume job :

res <- data.frame()
lambda_seq <- seq(from=0.2,to=0.8,by=0.05)

for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="uni",x=0.5,y=5,policy="pmtn"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="det",x=0.5,y=5,policy="pmtn"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma1",x=1,y=1/lambda_seq[i],policy="pmtn"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma2",x=0.5,y=1/lambda_seq[i],policy="pmtn"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="pmtn"))
}
res_calc = ddply(res,c("lambda","servicelaw"),summarise,Temps_moyen_service=mean(diferentiel))

ggplot(data=res_calc,aes(x=lambda,y=Temps_moyen_service,color=servicelaw)) + geom_point() + geom_line() + xlab("Fréquence d'arrivée") + ylab("Temps moyen de réponse") + ggtitle("Evolution du temps de réponse [Préemptif - Resume job]") + scale_color_brewer(palette="Set1",name="Loi",breaks=c("uni","det","gamma1","gamma2","exp"),labels=c("Uniforme","Déterministe","Gamma (série 1)","Gamma (série 2)","Exponentielle"))

plot of chunk unnamed-chunk-4

On retrouve un comportement similaire au mode non-préemptif. Cependant, le phénomène de cache que l’on peut observer sur la série 1 de la loi Gamma est plus “réaliste” ( dans le mode non préemptif, nous constations une augmentation du temps de service dans un premier temps). Les courbes suivent la même tendance, cependant on peut noter que le temps de réponse est particulièrement impacté par le mode de la file LIFO dans le cas d’une temps de service suivant une loi uniforme. Le temps de service suivant une loi exponentielle est impacté, dans une moindre mesure également. Cela s’explique par le fait qu’ici, un job peut être interompu, et “l’équitée” de la loi uniforme aura pour conséquence une plus longue attente avant que le job soit de nouveau “selectionné” et traité. Le temps de réponse suivant la loi exponentielle est croit de façon plus stable ici (les dents de scie sont aténuées ).

Préemptif - Restart job

res <- data.frame()
lambda_seq <- seq(from=0.2,to=0.8,by=0.05)

for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="uni",x=0.5,y=5,policy="pmtn_restart"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="det",x=0.5,y=5,policy="pmtn_restart"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma1",x=1,y=1/lambda_seq[i],policy="pmtn_restart"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma2",x=0.5,y=1/lambda_seq[i],policy="pmtn_restart"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="pmtn_restart"))
}
res_calc = ddply(res,c("lambda","servicelaw"),summarise,Temps_moyen_service=mean(diferentiel))

ggplot(data=res_calc,aes(x=lambda,y=Temps_moyen_service,color=servicelaw)) + geom_point() + geom_line() + xlab("Fréquence d'arrivée") + ylab("Temps moyen de réponse") + ggtitle("Evolution du temps de réponse [Préemptif - Restart job]") + scale_color_brewer(palette="Set1",name="Loi",breaks=c("uni","det","gamma1","gamma2","exp"),labels=c("Uniforme","Déterministe","Gamma (série 1)","Gamma (série 2)","Exponentielle"))

plot of chunk unnamed-chunk-5

Les lois Gamma illustrent la forte influence d’un système de cache, pour éviter de répéter par exemple de lourds calculs, et améliorer le temps de réponse. Une nouvelle fois, un temps de service suivant une loi uniforme sera pleinement impacté par le mode restart, qui aura des conséquence catastrophiques sur le temps de réponse. Déjà que le job a autant de chance qu’un autre d’être selectionné, si il doit en plus recommencer au début à chaque fois qu’il est interompu… Un temps de service suivant une loi exponentielle semble tendre vers un palier, et se stabiliser autour d’une valeur. Cela est particulièrement interessant !

Préemptif - Reset job

res <- data.frame()
lambda_seq <- seq(from=0.2,to=0.8,by=0.05)

for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="uni",x=0.5,y=5,policy="pmtn_reset"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="det",x=0.5,y=5,policy="pmtn_reset"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma1",x=1,y=1/lambda_seq[i],policy="pmtn_reset"))
}
for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma2",x=0.5,y=1/lambda_seq[i],policy="pmtn_reset"))
}

for(i in 1:length(lambda_seq)){
  res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="pmtn_reset"))
}
res_calc = ddply(res,c("lambda","servicelaw"),summarise,Temps_moyen_service=mean(diferentiel))

ggplot(data=res_calc,aes(x=lambda,y=Temps_moyen_service,color=servicelaw)) + geom_point() + geom_line() + xlab("Fréquence d'arrivée") + ylab("Temps moyen de réponse") + ggtitle("Evolution du temps de réponse [Préemptif - Reset job]") + scale_color_brewer(palette="Set1",name="Loi",breaks=c("uni","det","gamma1","gamma2","exp"),labels=c("Uniforme","Déterministe","Gamma (série 1)","Gamma (série 2)","Exponentielle"))

plot of chunk unnamed-chunk-6

Initialement, nous pensions obtenir des courbes similaires au précédent mode (restart), mais l’amélioration des performances est flagrante sur les loi Gamma. Dès le début, nous avons un temps de réponse, qui diminuera légèrement au cours du temps. Les performances s’améliorent légèrement sur le temps de service suivant une loi uniforme. Ce “nouveau tirage” semble améliorer les performances sur les différentes lois.

4. Conclusion

Le mode de fonctionnement non préemptif apportera un meilleur temps de réponse en moyenne. Il peut être intéressant de pouvoir interrompre une tache, et dans ce cas, le mode préemptif - resume ( reprise de la tache au point où on l’avait abandonnée) est assez logiquement le mode préemptif le plus performant.

Suivant la nature de la tache exécutée, ce dernier mode ne sera pas souhaitable : sur une section critique de code, protégée par un verrou,le job sera interompu, mais le verrou ne sera pas libéré pour autant. Pire encore, la section critique demeurera innacessible tant que le processus interompu n’aura pas repris la main et terminé son execution.