DM2 Evaluation de performance

Modification du code pour une politique SRPT

Nous avons essentiellement modifié la fonction run_task() qui désormais depile une tâche selon l’une des 4 politiques srpt_pmtn, spt_pmtn, spt, et fifo passée en paramètre.

Aussi afin que les comparaisons entre les différentes politiques soient les plus précises possibles, nous avons initialisé le germe aléatoire set.seed(10) au début de la fonction FileLIFO. Ceci implique que les dates d’arrivées et temps de service sont identiques à chaque appel de la fonction pour des paramètres identiques.

#Libraries
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,seed=10) {
    # 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
    set.seed(seed)                #in order to have the same time service each call with the same lambda, x, y
    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 or have not been completed yet
    next_arrival = 1    # index of the next task to arrive
    sys_vide = 0        # by curiosity let's count the number of times the system is empty
    sys_interrupted = 0 # by curiosity let's count the number of times the system is interrupted
    used = rep(0, n)    # by curiosity let's count the total of time used by a process (including its restart)
    waiting_length = rep(NA,n)  # by curiosity let's save the preemptions for counting them later
    
    
    #### A few useful local functions 
    run_task = function() { # runs the last task of the waiting list
      #if there is still a process in the stack to run, we take the last one in
    
      if(length(waiting)>0) {
      
    #print("arrivals")
    #print(t1)

        index = length(waiting)
        #waiting_length[next_arrival-1] <<- index
        #At first affectation it takes S[running], but after remaining[running] is returned
        for(i in 1:length(waiting)) {
        #For some reason multiple process can be pushed in waiting with one call to push function, causing troubles
        #Moreover this issue, may engage other strange behaviors such as 
            request = waiting[i] #it unstacks the last process received to update its remainning time
            remaining[request] <<- min(S[request],remaining[request],na.rm=T)
        }

        #print("index") 
        #print(length(waiting))
        #print("queue") 
        #print(waiting)
    
        #return the waiting index of the process with a minimum remaining time > 0 : depending on the policy chosen
        switch(policy,
                        srpt_pmtn = 
                          { #we elect the min between the new and current request by comparing their remaining time
                            if (index >= 2) { 
                              if (remaining[waiting[index-1]] <= remaining[waiting[index]]) 
                                index = (index - 1)
                            }
                          },
                       
                        spt_pmtn = 
                          { #we elect the min between the new and current request by comparing their service time
                            if (index >= 2) { 
                              if (S[waiting[index-1]] <= S[waiting[index]]) 
                                index = (index - 1)
                            }
                          },
                       
                        spt = 
                          { #we elect the first shortest remaining time process, among all the waiting processes
                            min_process = which(remaining==min(remaining[remaining>0], na.rm=T))
                            
                            #print("spt ")
                            #print(min_process)
                            #print(remaining)
                            
                            index = (which(waiting == min_process)) #[1]
                          },
                        
                        fifo = 
                          { #we elect the first arrived
                            
                            #print("fifo ")
                            #print(remaining)
                            
                            index = 1
                          },
                         {
                           print ("Default case --> Error")
                         }
                )

      
        running <<- waiting[index]        
        waiting <<- waiting[-index] #renvoie le tableau privé de l'element a la position index 
      }
    }

    push_task = function() { # insert the next_arrival-th task to the waiting list
                             # and run it if there is preemption
      if(policy != "spt" && policy != "fifo") {
        #It is preemptif
        if(!is.na(running)) {
          #if a process is running, we stack him because we are in preemption mode, and then stack also the next arrival. 
          waiting <<- c(waiting,running) #it stacks the current process, if t==t1[next_arrival]
        }
        running <<- NA #We set it to NA as if no process is running
      }
      #preemptif or not we stack the next arrival
      waiting <<- c(waiting,next_arrival)
      next_arrival <<- next_arrival+1 
      if(is.na(running)) { run_task() } #if it was preemtpif let run the next arrival, by unstack it
    }

    #### Main simulation loop
    while(TRUE) { 
      #dt is the time we will minus the remaning running process time
      # Look for next event
      dt = NA
      #have we reached the number max of process arrival ?
      if(next_arrival <=n) { dt = min(dt ,(t1[next_arrival]-t), na.rm=T ) } #dt=t1[..]-t it's a bit akward to take the min with dt because NA are deleted. Notice that t1[next_arrival]-t=dt is the next process arrival time - current time. So this is the elapsed time
      
      #is some process running ? if so, we finish executing it if its remaining time is lower than the delta time of the next arrival
      if(!is.na(running))  { dt = min(dt,remaining[running], na.rm=T) }
      
      #we've reached the max of process (no next arrival) and no process is running, we take off
      if(is.na(dt)) { break }
      
      # Update state
      t=t+dt
      if(!is.na(running)) { 
        # if a process is running, we subtract him dt time
        remaining[running] = remaining[running] - dt
        used[running] = used[running] + dt
        if(remaining[running]<=0) {
          #if the process is finished, we note the finish time
          t2[running] = t
          running = NA
          
          #the process is finished, it unstacks the last process and it launchs it depending on the policy chosen (resume, restart, restart with lower time), and affect remaining[running] to the corresponding time service
          run_task()
        }
      }
      
      if((next_arrival<=n) & (t==t1[next_arrival])) {
        #if this is time for the next arrival
        push_task() #insert the next_arrival task to the waiting list and run it if there is preemption
      }
      
    }
    
    #count the number of times the system is empty
    for(i in 2:n) {
      if ( t1[i]>t2[i-1]) {
        sys_vide = sys_vide + 1
      }
    }
    
    list (jobs = data.frame(arrival = t1, completion=t2, service=used, theoricService=S, response=(t2-t1), wl = waiting_length), 
          sys_vide = sys_vide)
}    

Evaluons les performances, en temps de réponse, des différentes stratégies SPRT à la politique FIFO

Maintenant que nous avons à disposition les outils permettant d’analyser les performances pour les différentes politiques, nous pouvons comparer les différentes politiques.

lambda_min  = 0.1
lambda_max  = 0.95
lambdas     = c(.2, .4, .6, .8) #seq(lambda_min, lambda_max, step)
step        = 0.05
n           = 10000
x           = 1
y           = 1
policies    = c("srpt_pmtn","spt_pmtn", "spt", "fifo")

laws        = data.frame()
laws        = rbind(laws, data.frame(name="exp(1,0)", fun="exp", x=1, y=0))
laws        = rbind(laws, data.frame(name="gamma(4,0.25)", fun="gamma", x=4, y=0.25))
laws        = rbind(laws, data.frame(name="gamma(0.2,5)", fun="gamma", x=0.2, y=5))

df = data.frame()
for(law in 1:nrow(laws)) {
    for(lambda in lambdas) {
      for(policy in policies){ 
        route=FileLIFO(n, lambda, typeservice=as.character(laws[law,]$fun), laws[law,]$x, laws[law,]$y, policy)
        tmp=route$jobs
        tmp$mode = policy
        tmp$lambda = lambda
        tmp$id=1:length(tmp$arrival)
        tmp$law = laws[law,]$name
        tmp$n = n
        tmp$sys_vide = route$sys_vide
        tmp$sys_interrupted=(tmp$n-tmp$sys_vide)
        df = rbind(df, tmp)
     }
  }
}

library(plyr)
res = ddply(df, c("law", "mode", "lambda", "n", "sys_vide", "sys_interrupted"), summarize, serviceM= mean(service), sd_service=sd(service), responseM=mean(response), sd_response=sd(response))

ggplot(data=res, aes(x = lambda, y = responseM, color = mode, shape = mode)) + 
  geom_line() +
  geom_point() + 
  geom_errorbar(width = 0.02, aes(x = lambda, y = responseM, ymin = responseM - 2 * sd_response/sqrt(n), ymax = responseM + 2 * sd_response/sqrt(n))) + 
  geom_vline(xintercept = 1) +
  geom_hline(yintercept = 1) +
  theme_bw() +
  facet_wrap(~law) +
  xlab("lambda") +
  ylab("Temps de réponse moyen") +
  ggtitle("Influence du taux d'arrivée (lambda) sur le temps de réponse")

Selon les résultats ci-dessus, les performances des politiques spt_pmtn et srpt_pmtn sont bien meilleures en comparaison à la politique FIFO. Cela s’explique par le fait que contrairement à la politique FIFO, les autres traitent les activités les plus courtes en premier, ce qui implique que la pile des éléments restants à traiter sera plus petite que si le serveur traitait un service quelconque. En effet, si le serveur s’occupe d’une tâche longue, les tâches plus courtes attendront en parallèle. Si les tâches plus courtes s’exécutent avant, il n’y aura au final que le service plus long qui aura à attendre. Nous avons donc une moyenne de temps de réponse plus faible.

La politique spt_pmtn est légèrement moins efficace que srpt_pmtn, ce qui est logique puisque le temps d’exécution total peut être grand en comparaison aux autres processus alors que le temps restant peut être petit. Nous avons donc quelques processus qui attendent pour rien.

Le cas de la politique spt est proche de spt_pmtn et de srpt_pmtn lorsque le traitement des plus longs processus n’est pas assez grand pour mettre en attente beaucoup de requêtes. Ainsi, lorsque la variance est grande (gamma(0.2,5)), spt est un intermédiaire entre FIFO et spt_pmtn/srpt_pmtn, et se rapproche de ces politiques dans les autres cas.

Il est à noter que lorsque la variance est très faible (gamma(4,0.25)), les différences entre les politiques sont très faibles, ce qui est normal puisqu’il y a peu de différence entre l’ordre de traitement optimal et un ordre fifo.

Etudions la distribution du temps de réponse et en particulier les valeurs extrêmes

Fixons nous a la loi exponentielle nous permettant de faire ressortir les résultats les plus intéressants.

Afin d’accentuer l’apparition des pics des temps de réponse nous choississons une valeur lambda > au débit crête. Au vu du graphe de la question 2, nous prenons un Lambda de 0.8

ggplot(data=df[df$law=="exp(1,0)" & df$lambda==0.8,], aes(x = id)) + 
  geom_bar(stat="identity", position="identity", aes(y=response)) + 
  theme_bw() +
  ylim(0,100) + 
  #xlim(0, 1) +
  xlab("Requêtes") +
  facet_wrap(~mode) + 
  ylab("Distribution des temps de réponse") +
  ggtitle("Temps de réponse avec lambda = 0.8, loi exp(1,0)")

ggplot(data=df[df$lambda==0.8,], aes(x = id, color = mode, shape = mode)) + 
  geom_bar(stat="identity", position="identity", aes(y=response)) + 
  theme_bw() +
  xlab("id") +
  ylab("Temps de réponse") +
  ggtitle("Influence du taux d'arrivée (lambda) sur le temps de réponse")

Nous pouvons voir qu’en dehors de la politique FIFO, les temps d’exécution sont généralement extrêmement faibles, cela se voit assez bien en raison de la faible densité de la distribution. Cela explique la différence notable en temps moyen entre FIFO et les autres politiques. Cependant, sur les politiques spt/srpt_pmtn/spt_pmtn, contrairement à la politique FIFO, les quelques temps de réponses qui ne sont pas dans le cas précédent ont un temps de réponse bien plus important. Nous pouvons deviner que ces cas là sont ceux où le temps de service est grand en comparaison aux autres, ils laissent donc la place aux traitements pouvant se faire plus rapidement, ce qui n’est pas le cas lors de la politique FIFO qui traite chaque tâche dans l’ordre d’arrivée.

Les pics sont par ailleurs d’autant plus marqués lors de la politique spt_pmtn. Les tâches les plus longues sont laissées de côté dès qu’une nouvelle tâche arrive peu importe le temps restant du traitement en cours, ce qui augmente significativement son temps de réponse.

Conclusion

En dehors des cas de variance extrêmes proposés par la loi gamma, nous constatons pour une loi exponentielle que les politiques spt, srpt_pmtn et spt_pmtn ont des performances exceptionnelles grâce à un nombre de tâches en attente minimal. Cependant, il ne faut pas oublier qu’en contrepartie, les tâches les plus coûteuses sont traitées uniquement lorsque personne ne leur fait de concurrence. Ainsi, contrairement au FIFO, les politiques spt, spt_pmtn et srpt_pmtn font le choix de ne pas être tout à fait équitable vis-à-vis de ses clients afin d’avoir des résultats moyens optimaux, ce qui est une approche tout à fait valable.