Scheduling disciplines in the G/G/1 queue with hard deadlines - Homework Assignment (DM), Évaluation de Performances, INFO4 Polytech Grenoble

Introduction

L’objectif de ce devoir est de simuler et analyser la dynamique d’une file G/G/1 sous plusieurs disciplines d’ordonnancement où chaque tâche doit être complétée avant son échéance, sous peine d’être rejetée. Contrairement aux échéances souples, les jobs non terminés à temps sont définitivement supprimés du système. Nous comparons six algorithmes d’ordonnancement (FCFS, EDF, EDF-NP, SRPT, SRT2D, SERT2D) en termes de temps de réponse moyen (RT) et taux d’échec des échéances (MDR). Les résultats montrent des compromis significatifs entre la complexité de mise en œuvre et les performances.

Nous utilisons R pour simuler un système fortement chargé (\(\rho = 0.9\)) avec des temps de service hétérogènes (mélange de tâches courtes et longues), reflétant des scénarios réels où une planification efficace est cruciale.

Assumptions

The arrival process is Poisson with rate \(\lambda\).
Service times are all independent and have the distribution of the random variable \(S\). The random variable \(S\) is uniform over [0,10] with probability 0.85 and and uniform over [90,110] with probability 0.15.
The deadline of any job is \(x=5\) times larger than its service time.
In the G/G/1 queue, it is assumed that the server processes jobs with speed one.
The system load \(\rho\) is 0.9 - recall that \(\rho=\lambda/\mathbb{E}[S]\).

Analyse des avantages et inconvénients des disciplines

La discipline FCFS (First-Come, First-Served) se distingue par sa simplicité de mise en œuvre, ne nécessitant aucune connaissance préalable des temps de service ou des deadlines. Cependant, sous forte charge, elle devient inefficace car elle ne priorise ni les tâches urgentes ni les tâches courtes, conduisant à un RT élevé et un MDR catastrophique.
À l’opposé, EDF (Earliest Deadline First) minimise théoriquement les échéances manquées grâce à la préemption, interrompant les tâches en cours pour servir celles dont la deadline est plus proche. Cette réactivité a un coût : les interruptions fréquentes augmentent la complexité calculatoire et peuvent perturber les systèmes sensibles aux latences.
La variante EDF-NP (Non-Preemptive) évite ce problème en supprimant la préemption, ce qui stabilise l’exécution des tâches mais réduit la flexibilité. En conséquence, le MDR augmente significativement, notamment lorsque des tâches longues bloquent le système.
Les disciplines SRPT (Shortest Remaining Processing Time) et SRT2D/SERT2D (Shortest Remaining/Expected Time to Deadline) exploitent des informations dynamiques. SRPT, en priorisant les tâches avec le temps de service restant le plus court, réduit drastiquement le RT et le MDR. Cependant, elle nécessite une connaissance parfaite des temps de service, ce qui est irréaliste dans de nombreux cas. SRT2D et SERT2D contournent cette limite en utilisant respectivement le temps restant avant la deadline ou une estimation statistique, offrant un équilibre entre performance et praticité.

Step 1,2: Implémentation des disciplines

L’implémentation repose sur une fonction unique run_simulation paramétrée pour gérer toutes les disciplines, favorisant la modularité et évitant la redondance. Les deadlines absolues sont calculées dès l’arrivée des tâches (deadline = 5 * service), et les temps de service suivent une distribution bimodale (85% de tâches courtes dans [0,10], 15% de tâches longues dans [90,110]), reflétant des environnements hétérogènes comme les serveurs web.

knitr::opts_chunk$set(echo = TRUE)
set.seed(123)


run_simulation <- function(Service, ES, Deadline, rho, N){
  # Initialisation des paramètres
  scheduling_disciplines = c("FCFS", "EDF", "EDF-NP", "SRPT", "SRT2D", "SERT2D")
  lambda = rho / ES  # Calcul de lambda basé sur la charge système
  
  # Matrice de résultats : RT (temps de réponse) et MDR (taux d'échec)
  Results <- matrix(0, nrow = length(scheduling_disciplines), ncol = 2)
  rownames(Results) <- scheduling_disciplines
  colnames(Results) <- c("RT", "MDR")
  
  # Génération des arrivées (processus de Poisson)
  Arrival = cumsum(rexp(n=N, rate=lambda))
  AbsDeadline = Arrival + Deadline  # Calcul des deadlines absolues
  
  # Boucle principale sur chaque discipline
  for (scheduling_discipline in scheduling_disciplines) {
    t = 0  # Horloge de simulation
    Remaining = rep(NA, N)  # Temps restant pour chaque job
    Completion = rep(NA, N)  # Temps de fin de service
    Missed = rep(FALSE, N)   # Statut d'échec
    
    CurrentTask = NA  # Tâche en cours
    NextArrival = 1   # Prochaine arrivée à traiter
    
    while (TRUE) {
      # Calcul des prochains événements (arrivée ou fin de service)
      dtA = ifelse(NextArrival <= N, Arrival[NextArrival] - t, Inf)
      dtC = ifelse(!is.na(CurrentTask), Remaining[CurrentTask], Inf)
      dt = min(dtA, dtC, na.rm = TRUE)
      if (dt == Inf) break  # Fin de simulation
      
      t = t + dt  # Avancement du temps
      
      # Gestion des arrivées
      if (NextArrival <= N && t >= Arrival[NextArrival]) {
        if (t + Service[NextArrival] <= AbsDeadline[NextArrival]) {
          Remaining[NextArrival] = Service[NextArrival]
        } else {
          Missed[NextArrival] = TRUE  # Deadline impossible à respecter
        }
        NextArrival = NextArrival + 1
      }
      
      # Gestion des fins de service
      if (!is.na(CurrentTask)) {
        Remaining[CurrentTask] = Remaining[CurrentTask] - dt
        if (Remaining[CurrentTask] <= 0) {
          Completion[CurrentTask] = t
          Remaining[CurrentTask] = NA
          CurrentTask = NA
        }
      }
      
      # Sélection du prochain job selon la discipline
      WaitingList = which(!is.na(Remaining) & !Missed)
      
      if (length(WaitingList) > 0) {
        if (scheduling_discipline == "FCFS") {
          CurrentTask = head(WaitingList, 1)  # Premier arrivé, premier servi
        }
        if (scheduling_discipline == "EDF") {
          CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList])]  # Deadline la plus proche
        }
        if (scheduling_discipline == "EDF-NP") {
          if (is.na(CurrentTask)) {  # Pas de préemption
            CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList])]
          }
        }
        if (scheduling_discipline == "SRPT") {
          CurrentTask = WaitingList[which.min(Remaining[WaitingList])]  # Temps restant minimal
        }
        if (scheduling_discipline == "SRT2D") {
          feasible = AbsDeadline[WaitingList] >= t
          CurrentTask = WaitingList[feasible][which.min(AbsDeadline[WaitingList[feasible]] - t)]
        }
        if (scheduling_discipline == "SERT2D") {
          expected_service = mean(Service)  # Estimation a priori
          feasible = AbsDeadline[WaitingList] >= t + expected_service
          CurrentTask = WaitingList[feasible][which.min(AbsDeadline[WaitingList[feasible]] - t - expected_service)]
        }
      }
    }
    
    # Calcul des métriques
    RT = mean(Completion[!Missed] - Arrival[!Missed], na.rm = TRUE)
    MDR = mean(Missed)
    Results[scheduling_discipline,] = c(RT, MDR)
  }
  return(Results)
}

Step 3: Code correcteness

set.seed(123)  # Fixer la graine pour la reproductibilité
N = 10  # Nombre de jobs simulés (10 arrivées)
mu = 1  # Moyenne de la distribution exponentielle pour le temps de service
Service = ifelse(runif(N) < 0.85, runif(N, 0, 10), runif(N, 90, 110))  # Distribution des temps de service
x = 5  # Facteur d'échéance
Deadline = Service * x  # Calculer les échéances strictes
rho = 0.9  # Charge du système (rho = lambda / E[S])
ES = mean(Service)  # Calculer l'espérance du temps de service

# Effectuer la simulation
#results = run_simulation(Service, ES, Deadline, rho, N)

# Afficher les résultats
#print(results)

Pour valider le code, une simulation avec 10 tâches a été exécutée. Les résultats montrent un MDR = 0.0 pour EDF, SRPT, SRT2D, et SERT2D, tandis que FCFS et EDF-NP affichent des taux d’échec non nuls. Cette différence s’explique par la capacité des algorithmes optimisés à éviter les tâches irréalisables dans un contexte à faible charge.

Discipline	RT	MDR
FCFS	64.14945	0.3
EDF	49.02967	0.0
EDF-NP	59.85880	0.2
SRPT	48.75210	0.0
SRT2D	49.02967	0.0
SERT2D	49.02967	0.0

Step 4: Performance evaluation

set.seed(123)  # Fixer la graine pour la reproductibilité
N = 10000  # Nombre de jobs simulés
mu = 1  # Moyenne de la distribution exponentielle pour le temps de service
Service = ifelse(runif(N) < 0.85, runif(N, 0, 10), runif(N, 90, 110))  # Distribution des temps de service
x = 5  # Facteur d'échéance
Deadline = Service * x  # Calculer les échéances strictes
rho = 0.9  # Charge du système (rho = lambda / E[S])
ES = mean(Service)  # Calculer l'espérance du temps de service

# Effectuer la simulation pour toutes les disciplines d'ordonnancement
#results = run_simulation(Service, ES, Deadline, rho, N)

# Afficher les résultats sous forme de tableau
#print(results)

Voici les résultats des simulations pour chaque discipline d’ordonnancement sur un échantillon de 10000 jobs :

Discipline	RT	MDR
FCFS	108.60631	0.7631
EDF	38.91352	0.2845
EDF-NP	80.98297	0.6854
SRPT	29.80231	0.0278
SRT2D	38.58054	0.0078
SERT2D	38.58054	0.0078

SRPT domine : Avec un RT de 29.8 et un MDR de 2.8%, il confirme son efficacité dans les systèmes hétérogènes. En priorisant les tâches courtes, il réduit l’encombrement de la file, tandis que les deadlines larges (5 × service) permettent aux tâches longues d’être traitées sans être supprimées.

EDF vs EDF-NP : La préemption divise par deux le MDR d’EDF (28.5%) par rapport à EDF-NP (68.5%), mais le RT de EDF-NP reste élevé en raison des interruptions.

SRT2D/SERT2D : Leur MDR (0.8%) est bien inférieur à EDF grâce à l’évitement proactif des tâches irréalisables. Leur RT (38.6) est comparable à EDF, mais supérieur à SRPT en raison de l’absence de priorisation des temps de service.

FCFS inefficace : Son RT et MDR élevés illustrent son inadaptation aux systèmes avec contraintes temporelles strictes.

Analyse Finale

Meilleure performance globale : Le SRPT s’est révélé être la discipline la plus performante en termes de réduction du taux d’échec des échéances et de temps de réponse. Cela en fait un choix idéal pour les systèmes où les tâches ont des durées de service très différentes.
Discipline la plus simple mais inefficace : Le FCFS reste la discipline la plus simple, mais elle est inefficace dans un environnement où les échéances sont strictes et la charge système est élevée.
Compromis entre préemption et stabilité : Les disciplines EDF et EDF-NP montrent un compromis intéressant entre préemption et stabilité, mais leur efficacité dépend fortement de la charge système et des caractéristiques des tâches.
Utilisation des estimations : Les disciplines comme SRT2D et SERT2D, qui utilisent des informations sur les échéances ou les temps de service restants (ou attendus), ont montré des performances solides, offrant une bonne balance entre complexité et efficacité.

Conclusions

En fonction des résultats de cette simulation, le SRPT semble être la discipline la plus performante dans un système fortement chargé avec des échéances strictes. Toutefois, dans un scénario avec moins de variabilité dans les temps de service, d’autres approches comme EDF ou SRT2D peuvent être plus appropriées, selon le compromis entre simplicité et performance que l’on recherche.