DM

library(ggplot2);
library(tidyr);
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

# lambda : Taux d'arrivée dans le système lambda (en tâches par seconde)
# mu : Taux de service du système mu (en tâches par seconde)
# rep = repetition et rate = le taux donc on a rep = 1/mu et rate = mu
# TOUJOURS METTRE à L'EXTERIEUR !

model_simulator = function(N = 1000, lambda, mode_sched, mode_arri) {
  
  # Simulation des temps d'arrivées et de traitement
  Arrival = cumsum(rexp(n = N, rate = lambda));
  
  # LOI DU TEMPS DE SERVICE :
    # Uniforme
  if(mode_arri == 'unif') {
    Service = runif(n = N, min = 0.5, max = 1.5);
  }
    # Exponencielle
  if(mode_arri == 'exp') {
    Service = rexp(n = N, rate = 1);
  }
    # Gamma
  if(mode_arri == 'gamma') {
    Service = rgamma(n = N, shape = 0.1, rate = 0.1);
  }
  # Initalisation des variables :
    # Temps restant pour chaque tâche
  Remaining = rep(N, x = NA);
  
    # Temps de terminaison des tâches
  Completion = rep(N, x = NA);
  
    # Temps courant
  t = 0;
  
    # Tâche en cours de traitement
  CurrentTask = NA;
  
    # La prochaine tâche
  NextArrival = 1;

  while (TRUE) {
    
    # On recupère le temps jusqu'à la prochaine arrivée, si elle existe
    dtA = NA;
    if(length(Arrival[Arrival > t]) > 0) {
        dtA = head(Arrival[Arrival > t], n = 1) - t;
    }
    
    # On recupère le temps jusqu'à la prochaine terminaison, si on a une tâche en cours
    dtC = NA;
    if(!is.na(CurrentTask)) {
        dtC = Remaining[CurrentTask];
    }
    
    # Si on a aucun évènement, on sort de la boucle !
    if(is.na(dtA) & is.na(dtC)) {
        break; 
    } 
    
    # dt est le temps du 1er évènement entre arrivée et terminaison.
    dt = min(dtA, dtC, na.rm = T)
  
  # Mettre à jour les variables comme il faut :
    #   la date : on avance jusqu'au prochain évènement
    t = t + dt;
    
    #   les arrivées : on met à jour leur temps restant et on pointe NextArrival sur l'arrivée suivante
    if((NextArrival <= N) & (Arrival[NextArrival] <= t)) { 
      Remaining[NextArrival] = Service[NextArrival];
      NextArrival = NextArrival + 1;
    }
    #   le remaining de la tâche courante : 
    if(!is.na(CurrentTask)) {
      # On met à jour le temps restant
      Remaining[CurrentTask] = Remaining[CurrentTask] - dt ;
      # Si on a un temps restant nul,  
      if(Remaining[CurrentTask] <= 0) {
        # on remplis la table de terminaision  
        Completion[CurrentTask] = t;
        # On met le temps restant à NA
        Remaining[CurrentTask] = NA;
        # On met la tâche courante à NA
        CurrentTask = NA
      }
    }
    
    # POLITIQUE D'ORDONNANCEMENT
    #   On stocke les identifiants des tâches de la file d'attente
    WaitingList = match(Remaining[!is.na(Remaining)], Remaining);
    if(length(WaitingList) > 0 & is.na(CurrentTask)) {
      # FIFO
      if (mode_sched == 'fifo') {
        # On prend le premier de la liste
        CurrentTask = head(WaitingList, n = 1);
      }
      # LIFO
      if (mode_sched == 'lifo') {
        # On prend le dernier de la liste
        CurrentTask = tail(WaitingList, n = 1);
      }
      # SPT
      if (mode_sched == 'spt') {
        # On prend celui avec le temps d'execution le plus court
        CurrentTask = WaitingList[which.min(Remaining[WaitingList])];
      }
    } 
    
  }
  
  return(data.frame(lambda = lambda, Idx = 1:N, Completion = Completion, Arrival = Arrival, Service = Service, ModeSched = mode_sched, ModeArri = mode_arri));
}

library(ggplot2);
library(tidyr);
library(dplyr);
Mode_Sched = c('fifo', 'lifo', 'spt');
Mode_Arri = c('unif', 'exp', 'gamma');
lambda = seq(from = 0.05, to = 0.9, by = .1);

df = data.frame();
for(a in 1:3){
  for(s in 1:3){
    for(l in lambda){
      df = rbind(df, model_simulator(1000, l, Mode_Sched[s], Mode_Arri[a]));
    }
  }
}

df %>% group_by(lambda, ModeSched, ModeArri) %>% mutate(mean = mean(Completion - Arrival)) %>% ggplot(aes(x = lambda, y = mean, group = ModeArri)) + geom_point(aes(colour = ModeArri)) + geom_line(aes(colour = ModeArri)) + facet_wrap(~ModeSched) + coord_cartesian(ylim = c(0, 25)) + ggtitle('Comportement en fonction des politiques de traitement')

Au premier regard, SPT semble être, généralement, la politique la plus avantageuse. Il n’y a pas d’énorme explosion du traffic, peu importe le taux d’arrivée ou la loi selon laquelle les processus sont traités. Ce qui semble cohérent. En effet, si je prends une grosse tâche alors qu’elle est suivi de plein de tâches très courtes, les tâches courtes vont passer autant de temps qu’il faut, dans la liste d’attente, pour traiter la longue tâche créant ainsi une accumulation, voir une congestion du traffic. Alors que, si je m’occupe des petites d’abord, le traffic reste globalement fluide. On peut alors se poser la question suivante : si j’ai énormément de petites tâches, cela pose-t-il problème? En effet, avec beaucoup de courtes tâches je risque de retarder indéfiniment le traitement de cette longue tâche. Et même dans le cas où je n’ai pas de limite d’arrivée, le risque de ne jamais traiter ma tâche est non nul. On ne peut pas donc entièrement se reposer sur SPT.

En regardant de façon plus détaillée, les modes d’arrivées uniformes et exponentielles offrent quand même une certaine stabilité du sysème avec des politiques LIFO et FIFO. En revanche, gamma est une véritable catastrophe. Cherchons pourquoi.

Lorsque l’on regarde la distribution de la fonction gamma, on s’apperçoit que plus le k augmente, plus la courbe est étalée et plus elle peut prendre de valeurs différentes. Mathématiquement parlant, son écart-type est plus important. Donc, plus j’avance avec ce paramètre, plus mes temps de services sont différents. J’ai ainsi dans mon système des tâches courtes et des tâches plus longues. On se retrouve dans la situation détaillée dans la partie sur SPT, ce qui explique que cette dernière soit plus adaptée. L’écart entre les temps de service demande un système réactif pour stabiliser la situation. On comprend donc pourquoi une politique Lifo ou fifo peu réactive n’est pas du tout compatible avec un temps de service gamma.

Globalement les temps de services uniformes et exponentielles sont similaires. Etudions plus en détail l’influence de ces paramètres en se plaçant sur un autre point de vue. Cette fois-ci on regroupe par type de service, et on observe le comportement de chaque politique.

df %>% group_by(lambda, ModeSched, ModeArri) %>% mutate(mean = mean(Completion - Arrival)) %>% ggplot(aes(x = lambda, y = mean, group = ModeSched)) + geom_point(aes(colour = ModeSched)) + geom_line(aes(colour = ModeSched)) + facet_wrap(~ModeArri) + coord_cartesian(ylim = c(0, 25)) + ggtitle('Comportement en fonction des politiques de traitement')

Au premier regard, gamma est encore une fois le mauvais élève et générer des temps de services de façon uniforme semble être la meilleure solution. Quand, dans mon système, la durée des tâches est à peu près similaire, l’ordre dans lequel je les traite n’a que peu d’importance sur la charge moyenne. Ce qui semble cohérent. Imaginons un système avec 2 processus arrivants : A et B. Ces 2 processus ont des temps de services similaires. Alors, que je prenne le processus A en premier, en dernier ou bien que je prenne le plus court des deux, sachant que cette différence est faible, cela ne change rien. Globalement, la charge de mon système est la même. Donc si j’ai des temps de services tirées uniformément, une politique FIFO, LIFO ou SPT ne va pas vraiment impacter mon système.

Gamma semble être encore plus incompatible avec LIFO qu’avec FIFO. Si on résume la situation, j’ai des temps de service assez étalés, LIFO va prendre le dernier arrivé et FIFO le premier. Encore une fois, alors qu’avec FIFO, je suis sûre de décharger le système au bout d’un certain temps, avec LIFO cette probabilité est moins importante et chaque arrivée d’une grande tâche me recule dans la file d’attente m’éloignant du moment où je vais sortir. Ceci pourrait expliquer cette explosion avec gamma.

Comme on peut le voir avec ce schéma, plus il y a d’arrivée de grandes tâches, plus le temps de completion sera élevé par rapport au temps de service.

En conclusion, la meilleure des 3 politiques étudiées semble être SPT. C’est une politique réactive, qui sait s’adapter au type de service et permet assez facilement de garder une certaine stabilité du système. Il reste quand même ce risque avec cette politique d’avoir une processus long toujours en attente. Cela dépend des arrivées. On pourrait donc tenter de l’améliorer avec une détection de ce genre de problème. La mise en place d’un timer d’attente ou un nombre de processus ayant le droit de doubler par exemple.