Deux algorithmes ont été implémentés, un pour la file LIFO sans préemption et un autre pour la file LIFO avec préemption.
La syntaxe de la file LIFO sans préemption est la suivante : lifoNoP(Nombre de valeurs, lambda, mu, loi)
La syntaxe de la file LIFO avec préemption est la suivante : lifoP(Nombre de valeurs, lambda, mu, loi, type de préemption)
Loi prend une valeur parmi les suivantes :
Pour nos algorithmes, si un processus venait à finir d'être traité au moment où un autre processus arrive, dans le cas de la file sans préemption le processus arrivant sera mis en attente.
En revanche, dans le cas de la file avec préemption, le processus arrivant préempte celui qui est en cours de traitement.
library(ggplot2)
library(plyr)
set.seed(1)
# première file LIFO -> sans préemption
# EXP : loi exponentielle
# DET : loi déterministe
# UNIF1 : loi uniforme entre 0 et 2
# ERL1 : loi Erlang shape = 0.5
# ERL2 : loi Erlang shape = 5
lifoNoP <- function(N, l, m, L) {
# ici définir s[] et a[]
a <- rexp(N, rate = l)
if (L == "EXP") {
s <- rexp(N, rate = m)
} else if (L == "DET") {
s <- rep(1, N)
} else if (L == "ERL1") {
s <- rgamma(N, shape = 0.5, scale = 1/0.5)
# on doit avoir scale * shape = 1 / mu shape => k, var = 1/k
} else if (L == "ERL2") {
s <- rgamma(N, shape = 5, scale = 1/5)
} else if (L == "UNIF1") {
# centré sur 1 / mu
s <- runif(N, 0, 2)
}
# tableau des dates d'arrivée
t1 <- c()
# tableau des dates de départ
t2 <- c()
# Pile de processus en attente
waiting <- c()
nbWait = 0
# date d'arrivée du premier processus
t1[1] <- 0
# date de départ du premier processus
t2[1] <- s[1]
# calcul des dates d'arrivée
for (i in 2:N) {
t1[i] <- t1[i - 1] + a[i]
}
# temps de fin du processus courant
remain <- s[1]
# processus courant
recup <- 1
i <- 1
while (i < N) {
# Si on a une arrivée avant d'avoir finie, mise en attente
if (a[i + 1] <= remain) {
waiting <- c((i + 1), waiting)
remain <- remain - a[i + 1]
i <- i + 1
nbWait <- nbWait + 1
} else {
# Sinon, on termine et on prend le processus suivant
t2[recup] <- remain + t1[i]
if (nbWait == 0) {
# pas de processus en attente, on prend le suivant qui arrivera
recup <- i + 1
remain <- s[recup]
i <- i + 1
} else {
# On prend le premier de la pile
recup <- waiting[1]
waiting <- waiting[-1]
remain <- s[recup] + remain
nbWait <- nbWait - 1
}
}
}
# fin du processus courant
t2[recup] <- remain + t1[i]
val <- t2[recup]
# maintenant on traite tous les éléments en attente dans la pile
for (j in 1:nbWait) {
recup <- waiting[1]
waiting <- waiting[-1]
t2[recup] <- val + s[recup]
val <- t2[recup]
}
# création de la mon_resrame avant son envoi
df <- data.frame(ENTREE = t1, SORTIE = t2, TEMPST = (t2 - t1), LAMBDA = l,
LOI = L, TYPE = "NONP")
df
}
# deuxième file LIFO, avec préemption
# EXP : loi exponentielle
# DET : loi déterministe
# UNIF1 : loi uniforme entre 0 et 2
# ERL1 : loi Erlang shape = 0.5
# ERL2 : loi Erlang shape = 5
lifoP <- function(N, l, m, L, type) {
# ici définir s[] et a[]
a <- rexp(N, rate = l)
if (L == "EXP") {
s <- rexp(N, rate = m)
} else if (L == "DET") {
s <- rep(1, N)
} else if (L == "ERL1") {
s <- rgamma(N, shape = 0.5, scale = 1/0.5)
# on doit avoir scale * shape = 1 / mu shape => k, var = 1/k
} else if (L == "ERL2") {
s <- rgamma(N, shape = 5, scale = 1/5)
} else if (L == "UNIF1") {
# centré sur 1 / mu
s <- runif(N, 0, 2)
}
# tableau des dates d'arrivée
t1 <- c()
# tableau des dates de départ
t2 <- c()
# Pile de processus en attente
waiting <- c()
nbWait = 0
# date d'arrivée du premier processus
t1[1] <- 0
# temps courant
tcurrent <- 0
# calcul des dates d'arrivée
for (i in 2:N) {
t1[i] <- t1[i - 1] + a[i]
}
# temps de fin du processus courant
remain <- s[1]
# processus courant
recup <- 1
i <- 1
while (i < N) {
# Si on a une arrivée avant d'avoir finie, préemption
if (a[i + 1] <= remain) {
waiting <- c(recup, waiting)
if (type == "RESUME") {
# on soustrait le temps passé
s[recup] <- s[recup] - a[i + 1]
} else if (type == "FORGET") {
# ne rien faire, on recommence l'execution
} else if (type == "RELOAD") {
# affectation d'une nouvelle valeur suivant la loi
if (L == "EXP") {
s[recup] <- rexp(1, rate = m)
} else if (L == "DET") {
s[recup] <- 1
} else if (L == "ERL1") {
s[recup] <- rgamma(1, shape = 0.5, scale = 1/0.5)
} else if (L == "ERL2") {
s[recup] <- rgamma(1, shape = 5, scale = 1/5)
} else if (L == "UNIF1") {
s[recup] <- runif(1, 0, 2)
}
}
remain <- s[i + 1]
tcurrent <- tcurrent + a[i + 1]
recup <- i + 1
i <- i + 1
nbWait <- nbWait + 1
} else {
# Sinon, on termine et on prend le processus suivant
t2[recup] <- remain + tcurrent
tcurrent <- tcurrent + remain
if (nbWait == 0) {
# pas de processus en attente, on prend le suivant qui arrivera
recup <- i + 1
tcurrent <- t1[recup]
remain <- s[recup]
i <- i + 1
} else {
# On prend le premier de la pile
a[i + 1] <- a[i + 1] - s[recup]
recup <- waiting[1]
waiting <- waiting[-1]
remain <- s[recup]
nbWait <- nbWait - 1
}
}
}
# fin du processus courant
t2[recup] <- remain + tcurrent
val <- t2[recup]
# maintenant on traite tous les éléments en attente dans la pile
for (j in 1:nbWait) {
recup <- waiting[1]
waiting <- waiting[-1]
t2[recup] <- val + s[recup]
val <- t2[recup]
}
# création de la mon_resrame avant son envoi
df <- data.frame(ENTREE = t1, SORTIE = t2, TEMPST = (t2 - t1), LAMBDA = l,
LOI = L, TYPE = type)
df
}
Pour cela nous fixons la valeur de N à 2000 de manière à avoir un bon compromis entre temps d'exécution et intervalle de confiance.
mon_res <- data.frame()
lambda_values = seq(from = 0.2, to = 0.8, by = 0.2)
# Loi exponentielle mode non préemptif
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoNoP(2000, lambda_values[i], 1, "EXP"))
}
# Loi exponentielle mode préemptif avec redémarrage du service
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "EXP", "FORGET"))
}
# Loi exponentielle mode préemptif avec reprise du service
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "EXP", "RESUME"))
}
# Loi exponentielle mode préemptif avec redémarrage avec une nouvelle valeur
# du service
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "EXP", "RELOAD"))
}
# calcul final
mon_res2 <- ddply(mon_res, c("LAMBDA", "TYPE"), summarize, TempsMoyen = mean(TEMPST),
vari = var(TEMPST), espint = (sd(TEMPST)/sqrt(length(TEMPST))))
ggplot(data = mon_res2, aes(x = LAMBDA, y = TempsMoyen, ymin = TempsMoyen -
espint, ymax = TempsMoyen + espint, color = TYPE, shape = TYPE)) + geom_point() +
geom_errorbar() + geom_line() + xlab("Lamda") + ylab("Temps de service moyen") +
labs(name = "Type de file", colour = "Type de file", shape = "Type de file")
On remarque de suite une explosion de valeurs pour la file LIFO non préemptive. Pour pouvoir mieux observer les valeurs, nous allons nous limiter sur l'axe Y de 0 à 8.
plt <- ggplot(data = mon_res2, aes(x = LAMBDA, y = TempsMoyen, ymin = TempsMoyen -
espint, ymax = TempsMoyen + espint, color = TYPE, shape = TYPE)) + geom_point() +
geom_errorbar() + geom_line() + ylim(0, 8) + xlab("Lamda") + ylab("Temps de service moyen") +
labs(name = "Type de file", colour = "Type de file", shape = "Type de file")
# Pour effacer les warning
suppressWarnings(print(plt))
Pour la file préemptive avec redémarrage du même temps de service, on remarque une instabilité qui survient rapidement, en revanche, avec les autres politiques de service nous restons avec des courbes progressant doucement, avec des intervalles de confiance restant corrects. On aurait pensé que la courbe du mode préemptif avec nouveau temps de service suivrait la courbe du redémarrage du même temps de service, ce qui n'est pas le cas.
Au final, la file LIFO non préemptive semble la plus intéressante pour la loi exponentielle, car son temps moyen d'attente reste plus faible qu'avec les autres politiques.
Nous allons désormais travailler sur chacun des différents modes. Nous commençons par le mode non préemptif :
mon_res <- data.frame()
lambda_values <- seq(from = 0.2, to = 0.8, by = 0.05)
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoNoP(2000, lambda_values[i], 1, "UNIF1"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoNoP(2000, lambda_values[i], 1, "EXP"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoNoP(2000, lambda_values[i], 1, "ERL1"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoNoP(2000, lambda_values[i], 1, "ERL2"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoNoP(2000, lambda_values[i], 1, "DET"))
}
# calcul final
mon_res2 <- ddply(mon_res, c("LAMBDA", "LOI"), summarize, TempsMoyen = mean(TEMPST),
vari = var(TEMPST), espint = (sd(TEMPST)/sqrt(length(TEMPST))))
plt <- ggplot(data = mon_res2, aes(x = LAMBDA, y = TempsMoyen, ymin = TempsMoyen -
espint, ymax = TempsMoyen + espint, color = LOI, shape = LOI)) + geom_point() +
geom_errorbar() + geom_line() + xlab("Lamda") + ylab("Temps de service moyen") +
labs(name = "Loi", colour = "Loi", shape = "Loi")
# Pour effacer les warning
suppressWarnings(print(plt))
Nous remarquons immédiatement une explosion pour la courbe en rapport avec la loi gamma de paramètre shape = 5. Néanmoins, son temps de service moyen n'est pas pour autant extrêmement élevé. La loi déterministe est celle qui possède le temps de service moyen qui grossit le moins rapidement. Nous remarquons également un phénomène vu dans la file FIFO sur la correction de M. Legrand (http://rpubs.com/alegrand/13532), que les lois ayant les variances les plus élevées grandissent le plus rapidement.
Nous allons maintenant étudier le comportement de la file LIFO préemptive avec reprise du temps de service :
mon_res <- data.frame()
lambda_values <- seq(from = 0.2, to = 0.8, by = 0.05)
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "UNIF1", "RESUME"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "EXP", "RESUME"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "ERL1", "RESUME"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "ERL2", "RESUME"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "DET", "RESUME"))
}
# calcul final
mon_res2 <- ddply(mon_res, c("LAMBDA", "LOI"), summarize, TempsMoyen = mean(TEMPST),
vari = var(TEMPST), espint = (sd(TEMPST)/sqrt(length(TEMPST))))
plt <- ggplot(data = mon_res2, aes(x = LAMBDA, y = TempsMoyen, ymin = TempsMoyen -
espint, ymax = TempsMoyen + espint, color = LOI, shape = LOI)) + geom_point() +
geom_errorbar() + geom_line() + xlab("Lamda") + ylab("Temps de service moyen") +
labs(name = "Loi", colour = "Loi", shape = "Loi")
# Pour effacer les warning
suppressWarnings(print(plt))
Cette fois-ci, les différentes courbes suivent une tendance pratiquement identique pour un lambda inférieur à 0.6, 0.7. Le fait de reprendre le service semble limiter l'effet “d'explosion” que nous pouvions observer sur la file FIFO par exemple ou sur le test précédent avec la loi gamma de paramètre shape = 5. Nous remarquons également que le temps moyen de service est légèrement plus élevé que celui de la file LIFO sans préemption, nous avions en effet pensé naïvement que cela aurait été l'inverse.
Nous continuons l'exercice avec désormais la file LIFO préemptive avec redémarrage du même temps de service.
mon_res <- data.frame()
lambda_values <- seq(from = 0.2, to = 0.8, by = 0.05)
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "UNIF1", "FORGET"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "EXP", "FORGET"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "ERL1", "FORGET"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "ERL2", "FORGET"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "DET", "FORGET"))
}
# calcul final
mon_res2 <- ddply(mon_res, c("LAMBDA", "LOI"), summarize, TempsMoyen = mean(TEMPST),
vari = var(TEMPST), espint = (sd(TEMPST)/sqrt(length(TEMPST))))
plt <- ggplot(data = mon_res2, aes(x = LAMBDA, y = TempsMoyen, ymin = TempsMoyen -
espint, ymax = TempsMoyen + espint, color = LOI, shape = LOI)) + geom_point() +
geom_errorbar() + geom_line() + xlab("Lamda") + ylab("Temps de service moyen") +
labs(name = "Loi", colour = "Loi", shape = "Loi")
# Pour effacer les warning
suppressWarnings(print(plt))
Cette fois-ci, nous observons des résultats impressionnants, avec des valeurs de temps moyen énormes, nous allons donc limiter l'axe Y à la valeur 30 afin de pouvoir mieux observer le phénomène.
plt <- ggplot(data = mon_res2, aes(x = LAMBDA, y = TempsMoyen, ymin = TempsMoyen -
espint, ymax = TempsMoyen + espint, color = LOI, shape = LOI)) + geom_point() +
geom_errorbar() + geom_line() + xlab("Lamda") + ylab("Temps de service moyen") +
labs(name = "Loi", colour = "Loi", shape = "Loi") + ylim(0, 30)
# Pour effacer les warning
suppressWarnings(print(plt))
Les courbes pour les lois gamma de paramètre shape = 0.5 et exponentielle s'envolent rapidement. Les trois autres lois décollent également pour un lambda légèrement supérieur. Nous pensons que cela vient du fait que si nous arrêtons un service, c'est que son temps de service a une probabilité élevée d'être supérieur au temps d'inter arrivée entre deux processus, et que par conséquent, un processus étant préempté risque de se faire préempter une nouvelle fois lors de l'arrivée d'un autre processus alors qu'il était de nouveau en cours de traitement sur le serveur.
Il est intéressant également de visionner le résultat de la file LIFO avec préemption, mais cette fois-ci en générant un nouveau temps de service :
mon_res <- data.frame()
lambda_values <- seq(from = 0.2, to = 0.8, by = 0.05)
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "UNIF1", "RELOAD"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "EXP", "RELOAD"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "ERL1", "RELOAD"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "ERL2", "RELOAD"))
}
for (i in 1:length(lambda_values)) {
mon_res <- rbind(mon_res, lifoP(2000, lambda_values[i], 1, "DET", "RELOAD"))
}
# calcul final
mon_res2 <- ddply(mon_res, c("LAMBDA", "LOI"), summarize, TempsMoyen = mean(TEMPST),
vari = var(TEMPST), espint = (sd(TEMPST)/sqrt(length(TEMPST))))
plt <- ggplot(data = mon_res2, aes(x = LAMBDA, y = TempsMoyen, ymin = TempsMoyen -
espint, ymax = TempsMoyen + espint, color = LOI, shape = LOI)) + geom_point() +
geom_errorbar() + geom_line() + xlab("Lamda") + ylab("Temps de service moyen") +
labs(name = "Loi", colour = "Loi", shape = "Loi")
# Pour effacer les warning
suppressWarnings(print(plt))
Une nouvelle fois certaines courbes s'envolent vers des valeurs lointaines tandis que d'autres restent très terre à terre. Nous allons une nouvelle fois limiter l'axe Y pour pouvoir observer ce qu'il se passe en bas du graphique.
plt <- ggplot(data = mon_res2, aes(x = LAMBDA, y = TempsMoyen, ymin = TempsMoyen -
espint, ymax = TempsMoyen + espint, color = LOI, shape = LOI)) + geom_point() +
geom_errorbar() + geom_line() + xlab("Lamda") + ylab("Temps de service moyen") +
labs(name = "Loi", colour = "Loi", shape = "Loi") + ylim(0, 20)
# Pour effacer les warning
suppressWarnings(print(plt))
La première chose importante qui nous vient à l'esprit est la courbe de la loi gamma de paramètre shape = 0.5, qui ne grandit pratiquement pas. Autre fait marquant, il semble que cette fois-ci, plus la variance est grande, moins les courbes explosent vers des valeurs aberrantes, l'inverse de la politique LIFO non préemptive. Cela nous amène à penser qu'avec un système de processus ayant des inter arrivées suivant une loi exponentielle, un traitement par une loi gamma de paramètre shape = 0.5 semble donner de bon résultat pour l'adoption d'une politique LIFO préemptive avec un nouveau temps de service. Selon nous, cela est causé par le fait qu'au moment du tirage du nouveau temps de service, avec une variance forte, il y a une plus grande probabilité d'avoir un nouveau temps de traitement étant inférieur à notre temps de traitement précédent, pouvant aussi être inférieur au temps des inter arrivées.
Nous avions vu pour la file FIFO que les courbes dépendaient entre autres de la variance de la loi, de lambda et de mu (CF lien cité précédemment).
Nous remarquons dans le cas de la file LIFO qu'en plus de ces paramètres, la politique adoptée par rapport à la préemption ou non provoque un impact important dans les temps moyens de service. Néanmoins, l'influence de la loi en elle même n'est pas extrémement visible, les courbes ayant la même tendance générale.
La politique LIFO avec préemption et tirage d'un nouveau temps de service possède les résultats les plus hétérogènes en fonction de la loi, tandis que ceux de la file LIFO avec préemption et reprise du temps de service sont plus homogènes.