DM

Explication

Nous avons choisi d’implémenter les algorithmes FIFO / LIFO avec préemption / SRPT.

Note : Le code est relativement générique et issue du TD, à l’exception faite des modifications apportées pour le LIFO, qui inclue la modification du handler d’arrivé.

gen = function(N=100, lambda =.2, mu='uni', policy = 'fifo'){
  if(mu != "uni" && mu !="gamma" && mu!="exp"){
    print("Loi sup : uniforme,gamma,exp")
  }else{
    
    #Global function and init
    t = 0;
    
    Arrival = cumsum(rexp(n=N, rate=lambda)); #task arrival
    
    # Task time treatment
    if(mu == 'exp'){
      Service = rexp(N,rate = 1);
    } else if(mu == 'gamma'){
      Service = rgamma(N, shape = .1, rate = .1);
    } else if(mu == 'uni'){
      Service = runif(N, min = 0.5, max = 1.5);
    }
    
    #task remaining/task + taks completion
    Remaining = rep(NA,N)
    Completion = rep(NA,N)
    
    #Current Task
    CurrentTask = NA
    
    NextArrival = 1;
    
    #TD's HANDLER CODE
    while(T){
       dtA = NA;
    dtC = NA;
    if(length(Arrival[Arrival>t])>0) {
        dtA = head(Arrival[Arrival>t],n=1)-t  # temps jusqu'à la prochaine arrivée
    }
    if(!is.na(CurrentTask)) {
        dtC = Remaining[CurrentTask]; # temps jusqu'à la prochaine terminaison
    }
    if(is.na(dtA) & is.na(dtC)) {
        break;
    } 
    dt = min(dtA,dtC,na.rm=T)

    # Mettre à jour comme il faut:
    #   la date
    t = t + dt;
    
    #   les arrivées
    if((NextArrival <=N) & (Arrival[NextArrival] <= t)){
      if(policy=='lifo_prempt'){#Handling the preamption of the job
        Remaining[NextArrival] = Service[NextArrival];
        WaitingList=(1:N)[!is.na(Remaining)];
        if(length(WaitingList)>0) {
            CurrentTask = tail(WaitingList,n=1);
        }
        NextArrival = NextArrival + 1;
      }else{
        Remaining[NextArrival] = Service[NextArrival];
        NextArrival = NextArrival + 1;
      }
        
    }
    
    #   le remaining 
    if(!is.na(CurrentTask)) {
        Remaining[CurrentTask] = Remaining[CurrentTask] - dt ;
        if(Remaining[CurrentTask] <= 0) {
            Completion[CurrentTask] = t;
            Remaining[CurrentTask] = NA;
        }
        CurrentTask = NA;
    }
    
    # et currentTask (politique d'ordonnancement: variable)
    if(policy == 'fifo'){ #Copied from the TD
      WaitingList=(1:N)[!is.na(Remaining)];
    if(length(WaitingList)>0) {
        CurrentTask = head(WaitingList,n=1);
    }
    
    }else if(policy == 'lifo_prempt'){
      #We take the last job in the list
      WaitingList=(1:N)[!is.na(Remaining)];
        if(length(WaitingList)>0) {
            CurrentTask = tail(WaitingList,n=1);
        }
    }else if(policy == 'srpt'){#Same as the TD, just change the selector
      WaitingList=(1:N)[!is.na(Remaining)];
        if(length(WaitingList)>0) {
            CurrentTask = which(Remaining==min(Remaining, na.rm=TRUE))[1];
        }

      
    }else{
      print("erreur : policy inconnu")
    }
    }
    #Uniformed data frame by Guillaume
    return(data.frame(lambda=lambda, mu=mu, Idx=1:N, Completion=Completion, Arrival=Arrival,ModeSched=policy,ModeArri=mu))

  
}
}

Etudes statistiques

#Source : http://www.cookbook-r.com/Graphs/Plotting_means_and_error_bars_(ggplot2)/ 

#https://stackoverflow.com/questions/29554796/meaning-of-band-width-in-ggplot-geom-smooth-lm

#https://www.rdocumentation.org/packages/ggplot2/versions/0.9.0/topics/stat_smooth

#We discussed with Quentin about how to render properly on GGplot

stats = function(N=1000, mu='uni', policy = 'fifo'){
  lambda = seq(from=0.05, to=.9, by=.1)

  X = data.frame();
  for(i in lambda){
    X = rbind(X,gen(N, mu, lambda=i, policy));
  }
  
  library(dplyr);
library(ggplot2);
  
  #Confidence Interval
  ci = t.test(X$Completion-X$Arrival)$conf.int[2] - mean(X$Completion-X$Arrival)
  


X %>% group_by(lambda) %>% summarise(median = mean(Completion-Arrival)) %>%
ggplot(aes(x=lambda, y=median))+geom_line()+geom_smooth(method ='loess', colour = 'purple')+geom_errorbar(aes(ymin=median-ci, ymax=median+ci),width=.05, position=position_dodge(0.05))
  
}

Simulation avec temps de service sous loi uniforme

Simulation sous politique FIFO :

stats(mu = 'uni', policy='fifo')

## Warning: package 'dplyr' was built under R version 3.4.3

## 
## Attaching package: 'dplyr'

## The following objects are masked from 'package:stats':
## 
##     filter, lag

## The following objects are masked from 'package:base':
## 
##     intersect, setdiff, setequal, union

## Warning: package 'ggplot2' was built under R version 3.4.3

## Warning: package 'bindrcpp' was built under R version 3.4.3

Simulation sous politique SRPT

stats(mu = 'uni', policy='srpt')

Simulation sous politique LIFO avec preemption

stats(mu = 'uni', policy='lifo_prempt')

Simulation avec temps de service sous loi Exponentiel

Simulation sous politique FIFO :

stats(mu = 'exp', policy='fifo')

Simulation sous politique srpt

stats(mu = 'exp', policy='srpt')

Simulation sous politique LIFO avec preemption

stats(mu = 'exp', policy='lifo_prempt')

Simulation avec temps de service sous loi Gamma

Simulation sous politique FIFO :

stats(mu = 'gamma', policy='fifo')

Simulation sous politique SRPT

stats(mu = 'gamma', policy='srpt')

Simulation sous politique LIFO avec preemption

stats(mu = 'gamma', policy='lifo_prempt')

Analyse :

Analyse par politique

• LIFO avec préemption montre des performances très bonne et même meilleure sur des taux d’arrivé faible et donc avec peu de traitement, mais devient rapidement très mauvais quand la quantité de tâches devient important.

• FIFO donne des scores relativement bon dans toutes les circosntances malgrès son implémentation rudimentaire.

• SRPT montre les meilleurs scores quand le nombre de taches devient important, mais reste moyen en cas de lambda faible. Ceci s’explique par la stratégie des jobs courts avant les longs. Cela améliore le temps de réponse en cas de nombreuses taches en attente car le fait de faire passer en priorité les jobs court donne un certain turnover à l’algorithme.

Analyse par loi

En observant la distribution avec des lambdas élevé (donc des taches globalements plus longues) :

• Dans le cadre d’un temps de traitement uniforme, il n’y a globalement que très peu de diffèrences entre les 3 stratégies (avec quand même un léger retard pour le LIFO avec preempt).

• Dans le cadre d’un temps de traitement suivant une loi exponentiel, SRPT et FIFO ont des scores relativement proche (un avantage pour SRPT), mais LIFO avec préemption montre des scores abyssalement mauvais relativement aux deux autres.

• Enfin, dans le cadre de temps de traitement régis par une loi gamma, SRPT montre des scores globalement bien meilleurs que FIFO, sans même parler de LIFO (entre 10 à 60 fois mieux)

En observant à lambda faible (peu de tache en entrée) :

• LIFO se montre supérieur dans ce genre de cas, bien que globalement les algorithmes donnent les même perf.

Conclusion

Si on n’a pas besoin de se soucier de famine et que le nombre de tâches arrivantes est élevé, alors l’algorithme SRPT est celui à privilégier. " Quant on ne sait pas trop, on prend FIFO :-) " Sinon, en cas d’un faible taux d’arrivé de taches, peu importe l“’algorithme !