Ce devoir maison a pour objectif de comparer le performances de trois politiques d’ordonnancements, suivant un taux d’arrivée modélisé par trois lois différentes.

Initialisations et fonctions diverses

# Adding libraries
library(ggplot2)
library(dplyr);
## 
## 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
# setting random things
set.seed(37);

# functions to generate graphs
trace_simple = function(x_data, y_data){
  plot(x_data, y_data);
}

trace_response_time= function(data){
  # d'après le stub
  data %>% group_by(lambda) %>% summarise(resp_mean = mean(Completion-Arrival), se = sd(Completion-Arrival)/sqrt(n())) %>%
  ggplot(aes(x=lambda, y=resp_mean)) + geom_point() + geom_line(color='red') + geom_errorbar(aes(ymin =resp_mean-2*se, ymax=resp_mean+2*se))
}

trace_completion_time = function(data){
  # on perd en visibilité quand N >>
  ggplot(data, aes(xmin = Completion-Service, xmax= Completion, ymin=Idx, ymax=Idx+1)) + geom_rect()
}

Politiques

Paramètres : - Le nombre de jobs : N = 1000 - Le taux d’arrivée dans le système : lambda (variable) - Le taux de service du système : mu = 1

N = 1000;
mu = 1;

FIFO

Code

simul_fifo = function(N = 1000, lambda = 0.1, Service = Service, mu = 1){
  Arrival = cumsum(rexp(n=N, rate = lambda));  # exponential
  Service = Service;

  Remaining = rep(N, x=NA);
  Completion = rep(N, x=NA);
  t = 0;
  CurrentTask = NA;
  NextArrival = 1;
  while (TRUE) {
      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)) { ## je met un <= et pas un == car 3-2.9!=0.1 ...
          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: FIFO)
      WaitingList=(1:N)[!is.na(Remaining)];
      if(length(WaitingList)>0) {
          CurrentTask = head(WaitingList,n=1);
      }
  }
  # print(Completion);
  
  return(data.frame(Arrival,  Completion, lambda, Idx = 1:N, Service, mu = mu, lambda = lambda));

}

Exécution

Suivant une loi uniforme
# setting service
Service = runif(n=N, min = 0.5, max = 1.5);

# executing simulation
lambda = seq(from=0.05 , to= .9, by = .1);
df = data.frame();
for(l in lambda){
  df = rbind(df, simul_fifo(N, lambda=l, Service = Service));
}

# plotting
trace_completion_time(df);

trace_response_time(df);

Suivant une loi exponentielle
Service = rexp(n=N, rate = 1); 

# executing simulation
lambda = seq(from=0.05 , to= .9, by = .1);
df = data.frame();
for(l in lambda){
  df = rbind(df, simul_fifo(N, lambda=l, Service = Service));
}

# plotting
trace_completion_time(df);

trace_response_time(df);

Suivant une loi gamma
Service = rgamma(n=N, 0.1, 0.1);

# executing simulation
lambda = seq(from=0.05 , to= .9, by = .1);
df = data.frame();
for(l in lambda){
  df = rbind(df, simul_fifo(N, lambda=l, Service = Service));
}

# plotting
trace_completion_time(df);

trace_response_time(df);

SPT

Code

simul_spt = function(N = 1000, lambda = 0.1, Service = Service){
  Arrival = cumsum(rexp(n=N, rate = lambda));  # exponential
  Service = Service;

  Remaining = rep(N, x=NA);
  Completion = rep(N, x=NA);
  t = 0;
  CurrentTask = NA;
  NextArrival = 1;
  while (TRUE) {
      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)) { ## je met un <= et pas un == car 3-2.9!=0.1 ...
          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: SPT)
      WaitingList=(1:N)[!is.na(Remaining)];
    
      if(length(WaitingList)>0) {
          # here we choose the task that has the mininal time to complete
          # old : CurrentTask = head(WaitingList,n=1);
          CurrentTask = head(WaitingList,n=1);
          for(job in WaitingList){
            CurrentTask = min(CurrentTask, job);
          }
          #print("Choosed job duration is (currenttask is)");
          #print(CurrentTask);
          
      }
  }
  # print(Completion);
  
  return(data.frame(Arrival,  Completion, lambda, Idx = 1:N, Service));
  

  # TODO
  # return(data.frame(lambda=lambda, mu=mu, idx = 1:N, arrival = Arrival, completion = Completion, service = Service))
}

Exécutions

Suivant une loi uniforme
Service = runif(n=N, min = 0.5, max = 1.5);

# executing simulation
lambda = seq(from=0.05 , to= .9, by = .1);
df = data.frame();
for(l in lambda){
  df = rbind(df, simul_spt(N=100, lambda=l, Service = Service));
}

# plotting
trace_completion_time(df);

trace_response_time(df);

Nous ne saurions expliquer ce pic à lambda ~ 0.55.

Suivant une loi exponentielle

Service = rexp(n=N, rate = 1); 

# executing simulation
lambda = seq(from=0.05 , to= .9, by = .1);
df = data.frame();
for(l in lambda){
  df = rbind(df, simul_spt(N, lambda=l, Service = Service));
}

# plotting
trace_completion_time(df);

trace_response_time(df);

Suivant une loi gamma

Service = rgamma(n=N, 0.1, 0.1);

# executing simulation
lambda = seq(from=0.05 , to= .9, by = .1);
df = data.frame();
for(l in lambda){
  df = rbind(df, simul_spt(N=100, lambda=l, Service = Service));
}

# plotting
trace_completion_time(df);

trace_response_time(df);

LIFO-préemption

Code

simul_lifop = function(N = 1000, lambda = 0.1, Service = Service){
  preemption_number = 0;
  Arrival = cumsum(rexp(n=N, rate = lambda));  # exponential
  #print(Arrival);
  Service = Service;

  Remaining = rep(N, x=NA);
  #print("Remaining :")
  #print(Remaining);
  Completion = rep(N, x=NA);
  t = 0;
  CurrentTask = NA;
  NextArrival = 1;
  while (TRUE) {
    #print(t);
    #print(Arrival);
    #print(Service);
    #print(Remaining);
      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 t + remaining[currentask] < arrival (de next task) then préempter else continuer ??    
    #print(dtA);
    #print(dtC);
    
     if(is.na(dtA) & is.na(dtC)) {
          #print("one value is na");
          break;
      }
      
      dt = min(dtA,dtC,na.rm=T);
      
     if(!is.na(dtA) & !is.na(dtC)){
       if(dtC > dtA){
         #print("current task has been preempted");
         preemption_number = preemption_number + 1;
         Remaining[CurrentTask] = t - dtA;
       }
     }

      # Mettre à jour comme il faut:
      #   la date
      t = t + dt;
      #   les arrivées
      if((NextArrival <=N) & (Arrival[NextArrival] <= t)) {
          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 
      WaitingList=(1:N)[!is.na(Remaining)];
      if(length(WaitingList)>0) {
          CurrentTask = tail(WaitingList,n=1); # tail for LIFO
      }
  }
  # print(Completion);
  #message("Preemption number : ", preemption_number);
  return(data.frame(Arrival,  Completion, lambda, Idx = 1:N, Service, mu=mu));
}

Exécutions

Suivant une loi uniforme
Service = runif(n=N, min = 0.5, max = 1.5);

# executing simulation
lambda = seq(from=0.05 , to= .9, by = .1);
df = data.frame();
for(l in lambda){
  df = rbind(df, simul_lifop(N=1000, lambda=l, Service = Service));
}

# plotting
trace_completion_time(df);

trace_response_time(df);

Contrairement aux deux précédentes politiques, le temps moyen de réponse croît plus rapidement lorsque lambda augmente.

Suivant une loi exponentielle
Service = rexp(n=N, rate = 1); 

# executing simulation
lambda = seq(from=0.05 , to= .9, by = .1);
df = data.frame();
for(l in lambda){
  df = rbind(df, simul_lifop(N, lambda=l, Service = Service));
}

# plotting
trace_completion_time(df);

trace_response_time(df);

Suivant une loi gamma

Service = rgamma(n=N, 0.1, 0.1);

# executing simulation
lambda = seq(from=0.05 , to= .9, by = .1);
df = data.frame();
for(l in lambda){
  df = rbind(df, simul_lifop(N=100, lambda=l, Service = Service));
}

# plotting
trace_completion_time(df);

On remarque que certaines tâches ne sont exécutées très tardivement…

# plotting
trace_response_time(df);

Oula. Si ce n’est pas causé par une mauvaise implantation de LIFO-préempté (cela comforte notre première remarque), et même si l’amplitude est importante, la temps moyen de réponse semble être assez stationnaire (on pourrait faire une “régression linéaire” pour le vérifier), et “n’explose” pas comme sur les autres politiques pour la même loi.

Remarques

On remarque que plus lambda est grand, plus l’intervalle de confiance (représentée par les barres sur ggplot) devient important.

D’après les graphiques générés pour les deux premières politiques (FIFO et SPT), il est assez difficile de montrer quelle politique est la plus performante, mais on remarque que le temps de réponse croît légèrement moins vite pour SPT.

Dans le cas du LIFO préempté, le temps moyen de réponse augmente rapidement, mais à tendance à se stabiliser lorsque le taux d’arrivé augmente.

Note : dans certains graphes de montrant le temps de complétion, on ne voit pas/peu les points car N est assez important. Il faut alors le réduire.