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"))