| Discipline | Avantages | Inconvénients |
|---|---|---|
| FCFS (First-Come-First-Served) | - Simple à implémenter - Équitable - Aucune information requise |
- Inefficace pour les délais courts - Taux de délais manqués élevé |
| EDF (Earliest Deadline First) | - Efficace pour minimiser les délais manqués - Optimise l’utilisation du temps |
- Nécessite la connaissance préalable des deadlines - La préemption engendre une surcharge |
| EDF-NP (Earliest Deadline First Non-preemptive) | - Moins de surcharge (pas de préemption) - Priorise les délais urgents |
- Nécessite la connaissance préalable des deadlines - Moins réactif que l’EDF. |
| SRPT (Shortest Remaining Processing Time) | - Minimise le temps de réponse moyen - Réduit l’encombrement du système |
- Nécessite la connaissance des temps de service restants - Risque de famine pour les tâches longues |
| SRT2D (Shortest Remaining Time to Deadline) | - Robuste face à des temps de service variables - Priorise les tâches proches de leur échéance |
- Difficile à mettre en place dans la pratique |
| SERT2D (Shortest Expected Remaining Time to Deadline) | - Robuste face à des temps de service variables - Priorise les tâches proches de leur échéance |
- Difficile à mettre en place dans la pratique |
###############################################################################
# Simulation d'une queue G/G/1 #
###############################################################################
# service_time S : Distribution de probabilité pour le temps de service #
# mean_service_time E[S] : Espérance de S (temps moyen passé par client) #
# deadline : Durée maximale à ne pas dépasser #
# Le cas échant le client sera expulsé du système. #
# rho : Intesité du trafic | rho = lambda/mu #
# total_client_num : Nombre de clients au total entrant dans le système #
###############################################################################
run_simulation <- function(service_time,
mean_service_time,
deadline,
rho,
total_client_num,
is_hard) {
# Politiques d'ordonnancement
service_orders <- c("FCFS", "EDF", "EDF-NP", "SRPT", "SRT2D", "SERT2D")
results <- matrix(0, nrow = length(service_orders), ncol = 2)
rownames(results) <- service_orders
colnames(results) <- c("response_time", "missed_deadline_ratio")
# Taux moyen d’arrivée de clients dans le système (Average Arrival Rate)
lambda <- rho / mean_service_time
# Pour un processus de Poisson
# La loi d'inter-arrivée suit une loi exponentielle de paramètre lambda
interarrival_time <- rexp(total_client_num, rate = lambda)
# Temps absolu auquel les arrivées se produisent
arrival_time <- cumsum(interarrival_time)
# Temps absolu après lequel un client sera expulsé
# s'il n'est pas complètement traîté par le serveur
expiration_time <- arrival_time + deadline
# On lance une simulation pour chaque politique d'ordonnancement
for (service_order in service_orders) {
# Temps absolu courant
t <- 0
# Temps de service (relatif) restant pour chaque client
remaining_service_time <- rep(total_client_num, x = NA)
# Temps absolu à partir duquel un client sort du système
departure_time <- rep(total_client_num, x = NA)
# TRUE : Le client a été totalement traîté par le serveur
# FALSE : Le client a été expulsé car sa deadline a été dépassé
client_finished <- rep(total_client_num, x = NA)
# Temps de service (relatif) passé sur chaque client noté s
current_service_time <- rep(total_client_num, x = NA)
# E[S | S > s] pour SERT2D
expectation <- rep(total_client_num, x = NA)
# Indice du client traité actuellement par le serveur
served_client_idx <- NA
# Indice du prochain client qui arrive dans le système
arriving_client_idx <- 1
# Nombre moyen de clients dans le système E[X]
mean_client_num <- 0
while (TRUE) {
# Temps restant jusqu'à l'arrivée d'un prochain client
dt_a <- NA
# Temps restant pour terminé de s'occuper du client courant
dt_c <- NA
# Après un temps dt_a, une arrivée se produit
if (length(arrival_time[arrival_time > t]) > 0) {
dt_a <- head(arrival_time[arrival_time > t], n = 1) - t
}
# Il reste un temps dt_c pour traiter le client
if (!is.na(served_client_idx)) {
dt_c <- remaining_service_time[served_client_idx]
}
# S'il n'y a plus de clients, la simulation est finie
if (is.na(dt_a) && is.na(dt_c)) {
break
}
# On mets à jour les variables du système
dt <- min(dt_a, dt_c, na.rm = TRUE)
t <- t + dt
mean_client_num <-
mean_client_num + dt * sum(!is.na(remaining_service_time))
# Si un client arrive dans le système
if ((arriving_client_idx <= total_client_num) &&
(arrival_time[arriving_client_idx] == t)) {
# On initialise le client
current_service_time[arriving_client_idx] <- 0
expectation[arriving_client_idx] <- 0
remaining_service_time[arriving_client_idx] <- service_time[arriving_client_idx]
arriving_client_idx <- arriving_client_idx + 1
}
# Si le temps de service est plus grand que la deadline
# On doit expulser le client du système SAUF pour EDF et EDF-NP
if (is_hard && !is.na(served_client_idx) &&
(expiration_time[served_client_idx] - t) <= 0 &&
(service_order != "EDF" || service_order != "EDF-NP")) {
client_finished[served_client_idx] <- FALSE
departure_time[served_client_idx] <- t
remaining_service_time[served_client_idx] <- NA
current_service_time[served_client_idx] <- NA
expectation[served_client_idx] <- NA
served_client_idx <- NA
}
if (!is.na(served_client_idx)) {
# Calcul de E[S | S > s] pour SERT2D
if (service_time[served_client_idx] > current_service_time[served_client_idx]) {
expectation[served_client_idx] <-
(expectation[served_client_idx] * current_service_time[served_client_idx] + service_time[served_client_idx]) / (current_service_time[served_client_idx] + dt)
current_service_time[served_client_idx] <-
current_service_time[served_client_idx] + dt
}
# Mets à jour le temps restant
remaining_service_time[served_client_idx] <-
remaining_service_time[served_client_idx] - dt
# Départ d'un client du système
if (remaining_service_time[served_client_idx] <= 0) {
client_finished[served_client_idx] <- TRUE
departure_time[served_client_idx] <- t
remaining_service_time[served_client_idx] <- NA
current_service_time[served_client_idx] <- NA
expectation[served_client_idx] <- NA
served_client_idx <- NA
}
}
# Liste d'indices des clients présents dans la file d'attente
waiting_list <- (1:arriving_client_idx)[!is.na(remaining_service_time)]
# Si aucun client n'est dans la file, pas besoin d'en choisir un
if (length(waiting_list) <= 0) {
next
}
# Le premier client arrivé est le premier servi (ordre FIFO)
if (service_order == "FCFS") {
served_client_idx <- head(waiting_list, n = 1)
}
# Le client dont la deadline est la plus petite est choisi avec préemption
# (Une tache peut être interrompue même si elle n'est pas finie)
else if (service_order == "EDF") {
served_client_idx <-
waiting_list[which.min(expiration_time[waiting_list])]
}
# Le client dont la deadline est la plus petite est choisi
# (Seulement après que le client servi par le serveur le soit totalement)
else if (service_order == "EDF-NP") {
if (is.na(served_client_idx)) {
served_client_idx <-
waiting_list[which.min(expiration_time[waiting_list])]
}
}
# Le client qui demande le moins de temps de service est choisi
else if (service_order == "SRPT") {
served_client_idx <- which.min(remaining_service_time)
}
# Le client, dont l'intervalle de temps entre le temps d'expiration
# et le temps de service restant est le plus petit, est choisi
else if (service_order == "SRT2D") {
served_client_idx <- waiting_list[which.min(expiration_time[waiting_list] - (t + remaining_service_time[waiting_list]))]
}
# pareil sauf qu'on utilise le temps moyen calculé que le serveur prend pour traiter un client
else if (service_order == "SERT2D") {
served_client_idx <- waiting_list[which.min(expiration_time[waiting_list] - (t + expectation[waiting_list]))]
}
} # while
# Mesures de performance
# Nombre moyen de clients dans le système
mean_client_num <-
mean_client_num / (tail(departure_time, n = 1) - arrival_time[1])
# Temps moyen qu'un client passe dans le système (Response/Waiting Time)
if(is_hard) {
response_time <- mean(
departure_time[client_finished == TRUE]
- arrival_time[client_finished == TRUE]
)
} else {
response_time <- mean(departure_time - arrival_time)
}
# Proportion de clients traités partiellement (ou pas du tout)
# Soit : Nombre de clients expulsés / Nombre de clients total
if(is_hard) {
missed_deadline_ratio <- mean(client_finished == FALSE)
} else {
missed_deadline_ratio <- mean(departure_time > expiration_time)
}
# Résultats de la simulation
results[service_order, 1] <- response_time
results[service_order, 2] <- missed_deadline_ratio
# Vérification de la simulation avec la loi de Little
# Nombre de clients moyen = Taux d'arrivée x Temps moyen d'attente
cat(paste( "[", service_order, "] ",
"Verification : (mean_client_num) ",
round(mean_client_num, digits = 4),
"==",
round(lambda * mean(departure_time - arrival_time), digits = 4),
" (lambda * response_time)\n"
))
} # for
cat("\nResults:\n")
print(results)
} # run_simulation
###############################################################################
# Fonction pour générer la loi de S (a.k.a le temps de service) #
###############################################################################
# Elle est uniforme sur [0, 10] avec probabilité 0.85 #
# et uniforme sur [90, 110] avec probabilité 0.15 #
###############################################################################
generate_service_time <- function() {
u <- runif(1, min = 0, max = 1)
if (u <= 0.85) {
return(runif(1, min = 0, max = 10))
}
runif(1, min = 90, max = 110)
}
###############################################################################
# Exemple de simulation #
###############################################################################
# On choisit le germe pour pouvoir réobtenir les mêmes résultats
set.seed(1)
# Nombre total de clients qui vont rentrer dans le système
total_client_num <- 1e4
# Intesité du trafic : rho = lambda/(c . mu) avec c=1, le nombre de serveurs
rho <- 0.9
# Loi de probabilité du temps de service
service_time <- replicate(total_client_num, generate_service_time())
# E[S] : Espérance de S
mean_service_time <- (0 + 10) / 2 * 0.85 + (90 + 110) / 2 * 0.15
# Temps relatif maximal avant que le client soit expulsé du système
deadline <- service_time * 5
# Indique si on doit expulser ou non les clients
# Si la deadline a été dépassé
is_hard <- TRUE
# service_time <- rexp(total_client_num, rate = 1)
# mean_service_time <- 1
# deadline <- 5 * service_time
run_simulation(service_time, mean_service_time, deadline, rho, total_client_num, is_hard)## [ FCFS ] Verification : (mean_client_num) 9.0854 == 9.0947 (lambda * response_time)
## [ EDF ] Verification : (mean_client_num) 2.5342 == 2.5362 (lambda * response_time)
## [ EDF-NP ] Verification : (mean_client_num) 3.828 == 3.8319 (lambda * response_time)
## [ SRPT ] Verification : (mean_client_num) 2.3335 == 2.3353 (lambda * response_time)
## [ SRT2D ] Verification : (mean_client_num) 3.007 == 3.0093 (lambda * response_time)
## [ SERT2D ] Verification : (mean_client_num) 2.56 == 2.562 (lambda * response_time)
##
## Results:
## response_time missed_deadline_ratio
## FCFS 118.89290 0.7034
## EDF 42.25213 0.0436
## EDF-NP 87.61698 0.5698
## SRPT 32.53313 0.0217
## SRT2D 45.78239 0.1134
## SERT2D 42.99490 0.0537Calcul de l’espérance du temps de service
Soit \(X \sim \mathcal{B}(0.15)\). Alors, \(X(\Omega) = \{0, 1\}\), \(P(X=0) = 0.85\) et \(P(X=1) = 0.15\).
Soit \(S\) une variable aléaoitre à densité telle que \(S\mid Y =0 \sim \mathcal{U}([0,10])\) et \(S\mid Y=1 \sim \mathcal{U}([90,110])\).
Alors \(S(\Omega) = [0,10] \cup [90,110]\) et pour tout \(x \in S(\Omega), f_S(x) = \sum_{k\in X(\Omega) } P(X=k) f_{S\mid X = k} (x)\).
Dès lors, par linéarité de l’intégrale, \(\mathbb E[S] = \int_{\mathbb R} x f_S(x) \, dx = P(X=0) \int_{0}^{10} x \cdot \frac{1}{10 - 0} \, dx \, + P(X=1) \, \int^{110}_{90} x \cdot \frac{1}{110-90} \, dx = 0.85 \times \frac{0+10}{2} + 0.15 \times \frac{90+110}{2}\).
Comparaison des services
On observe avec une politique d’ordonnancement “hard” que la pire performance est celle du FCFS, avec un taux de pertes de 70% et un temps de réponse de 119 secondes. À l’inverse, la meilleure performance semble être obtenue avec le SRPT, avec un temps de réponse de 33 secondes et un taux de pertes de seulement 2%.