El Hadji Malick FALL, Adji Ndèye Ndaté SAMBE
Question 1 : Gestion de la politique LIFO
Nous commençons tout d'abord par définir la version non préemptive. Nous reprenons les fonctions déjà définies pour les files FIFO concernant le service et l'inter-arrivee.
set.seed(10)
library(ggplot2)
service <- function(law_lamb) {
if (law_lamb == "exp") {
return(rexp(1, 1))
}
if (law_lamb == "unif") {
return(runif(1, 0, 2))
}
if (law_lamb == "det") {
return(runif(1, 1, 1))
}
if (law_lamb == "erlang") {
return(rgamma(1, shape = 1, scale = 1))
}
if (law_lamb == "erlang2") {
return(rgamma(1, shape = 4, scale = 1/4))
}
if (law_lamb == "erlang3") {
return(rgamma(1, shape = 0.2, scale = 1/0.2))
}
}
interarrivee <- function(lambda) {
return(rexp(1, lambda))
}
Voici la première version qui est non préemptive :
nonpreemptif <- function(N, lambda, law, mode = "np") {
t1 <- c()
t2 <- c()
A <- c()
S <- c()
R <- c()
# initialisation des lois
for (i in 1:N) {
S[i] <- service(law)
A[i] <- interarrivee(lambda)
}
t1[1] <- 0
t2[1] <- t1[1] + S[1]
R[1] <- t2[1] - t1[1]
# calcul des dates d'arrivee
for (i in 2:N) {
t1[i] <- t1[i - 1] + A[i]
}
# initialisation le premier processus commence a la date 0 et s'execute
# jusqu'au bout
# initialitasion
tabAttente <- c() #on definit le tableauu qui va contenir la liste des processus en attente d'execution
proCours <- 1 # pointe sur le processus courant
for (i in 2:N) {
if (t1[i] <= t2[proCours]) {
tabAttente <- c(tabAttente, (i))
} else {
if (length(tabAttente) == 0) {
# dans le cas ou je suis le seul processus a s'executer
t2[i] <- t1[i] + S[i] # je calcule ma date de sortie normalement
proCours <- i #je deviens le processus courant
} else {
# il y a des processus en attente
nextProcess <- tabAttente[length(tabAttente)]
t2[nextProcess] <- t2[proCours] + S[nextProcess]
proCours <- nextProcess
tabAttente <- tabAttente[-length(tabAttente)]
}
}
while (length(tabAttente) != 0) {
nextProcess = tabAttente[length(tabAttente)]
t2[nextProcess] = t2[proCours] + S[nextProcess]
proCours = nextProcess
tabAttente = tabAttente[-length(tabAttente)]
}
}
# calcul du temps R de tous les processus sauf le premier vu qu'on le
# connait deja
for (i in 2:N) {
R[i] <- t2[i] - t1[i]
}
data.frame(lambda = lambda, R = mean(R), ci = 2 * sd(R)/sqrt(N), loi = law,
mode = mode)
# ci pour calculer l'intervalle de confiance a 95%
}
Comme cela nous avait été indiqué lors du TD sur FIFO, nous convenons de tracer sur 3000 points pour avoir une meilleure vision de l'état stationnaire du système. (10000 serait l'ideal mais compte tenu du nombre de cours à tracer, cela prendrait beaucoup trop de temps)
tracelambda <- function(law) {
df = data.frame()
for (lambda in seq(0.1, 0.9, by = 0.1)) {
df = rbind(df, nonpreemptif(3000, lambda, law))
}
df
}
tracer <- function() {
tab <- c()
tab[1] = "exp"
tab[2] = "det"
tab[3] = "unif"
tab[4] = "erlang"
tab[5] = "erlang2"
tab[6] = "erlang3"
datafinal = data.frame()
for (i in 1:6) {
datafinal = rbind(datafinal, tracelambda(tab[i]))
}
datafinal
}
daf = tracer()
Voici la version preemptive que nous avons implementé. Nous n'avons malheureusement pas pu réaliser le mode avec reprise.
# mode reinitilisation
preemptifINIT <- function(N, lambda, law, mode = "reinit") {
t1 <- c()
t2 <- c()
A <- c()
S <- c()
R <- c()
# initialisation des lois
for (i in 1:N) {
S[i] <- service(law)
A[i] <- interarrivee(lambda)
}
t1[1] <- 0
# calcul des dates d'arrivee
for (i in 2:N) {
t1[i] <- t1[i - 1] + A[i]
}
t2[1] <- S[1]
# initialitasion
tabAttente <- c() #on definit le tableauu qui va contenir la liste des processus en attente d'execution
proCours <- 1 # pointe sur le processus courant
NbEnAttente = 0
i <- 1
while (i < N) {
prochainearrive <- A[i + 1]
if (prochainearrive <= S[proCours]) {
# si la prochaine arrivee <= au temps de service du processus en courant
tabAttente <- c(proCours, tabAttente) #on empile le processus courant
NbEnAttente <- NbEnAttente + 1
S[proCours] <- service(law)
proCours <- i + 1
i <- i + 1
} else {
t2[proCours] <- t1[proCours] + S[proCours] #le processus calcule son temps
if (NbEnAttente == 0) {
# s'il n'y aucun processus en attente il passe la main au processus suivant
proCours <- i + 1
i <- i + 1
} else {
nextarrivee <- t1[proCours + 1]
tmp <- t2[proCours]
# on dépile tous les processus en attente
for (j in 1:NbEnAttente) {
nextProcess <- tabAttente[1]
tabAttente <- tabAttente[-1]
if (nextarrivee < S[nextProcess] + tmp) {
# on vérifie qu'on est pas préempté
S[nextProcess] <- service(law)
proCours <- proCours + 1
}
t2[nextProcess] <- tmp + S[nextProcess]
tmp <- t2[nextProcess]
NbEnAttente <- NbEnAttente - 1
# tabAttente <- tabAttente[-length(tabAttente)]
}
proCours <- i + 1
i <- i + 1
}
}
} #fin while
t2[proCours] <- t1[proCours] + S[proCours]
if (NbEnAttente == 0) {
# s'il n'y aucun processus en attente on ne fait rien
}
tmp <- t2[proCours]
# on traite les processus encore dans la file
for (j in 1:NbEnAttente) {
nextProcess <- tabAttente[1]
tabAttente <- tabAttente[-1]
t2[nextProcess] <- tmp + S[nextProcess]
tmp <- t2[nextProcess]
NbEnAttente <- NbEnAttente - 1
# tabAttente <- tabAttente[-length(tabAttente)]
}
# calcul du temps R de tous les processus sauf le premier vu qu'on le
# connait deja
for (i in 1:N) {
R[i] <- t2[i] - t1[i]
}
data.frame(lambda = lambda, R = mean(R), ci = 2 * sd(R)/sqrt(N), loi = law,
mode = mode)
# ci pour calculer l'intervalle de confiance a 95%
} #fin fonction
# mode redemarrage
preemptifREDEM <- function(N, lambda, law, mode = "redem") {
t1 <- c()
t2 <- c()
A <- c()
S <- c()
R <- c()
# initialisation des lois
for (i in 1:N) {
S[i] <- service(law)
A[i] <- interarrivee(lambda)
}
t1[1] <- 0
# calcul des dates d'arrivee
for (i in 2:N) {
t1[i] <- t1[i - 1] + A[i]
}
t2[1] <- S[1]
# initialitasion
tabAttente <- c() #on definit le tableauu qui va contenir la liste des processus en attente d'execution
proCours <- 1 # pointe sur le processus courant
NbEnAttente = 0
i <- 1
while (i < N) {
prochainearrive <- A[i + 1]
if (prochainearrive <= S[proCours]) {
# si la prochaine arrivee <= au temps de service du processus en courant
tabAttente <- c(proCours, tabAttente) #on empile le processus courant
NbEnAttente <- NbEnAttente + 1
proCours <- i + 1
i <- i + 1
} else {
t2[proCours] <- t1[proCours] + S[proCours] #le processus calcule son temps
if (NbEnAttente == 0) {
# s'il n'y aucun processus en attente il passe la main au processus suivant
proCours <- i + 1
i <- i + 1
} else {
nextarrivee <- t1[proCours + 1]
tmp <- t2[proCours]
# on dépile tous les processus en attente
for (j in 1:NbEnAttente) {
nextProcess <- tabAttente[1]
tabAttente <- tabAttente[-1]
if (nextarrivee < S[nextProcess] + tmp) {
# on vérifie qu'on est pas préempté
proCours <- proCours + 1
}
t2[nextProcess] <- tmp + S[nextProcess]
tmp <- t2[nextProcess]
NbEnAttente <- NbEnAttente - 1
# tabAttente <- tabAttente[-length(tabAttente)]
}
proCours <- i + 1
i <- i + 1
}
}
} #fin while
t2[proCours] <- t1[proCours] + S[proCours]
if (NbEnAttente == 0) {
# s'il n'y aucun processus en attente on ne fait rien
}
tmp <- t2[proCours]
# on traite les processus encore dans la file
for (j in 1:NbEnAttente) {
nextProcess <- tabAttente[1]
tabAttente <- tabAttente[-1]
t2[nextProcess] <- tmp + S[nextProcess]
tmp <- t2[nextProcess]
NbEnAttente <- NbEnAttente - 1
# tabAttente <- tabAttente[-length(tabAttente)]
}
# calcul du temps R de tous les processus sauf le premier vu qu'on le
# connait deja
for (i in 1:N) {
R[i] <- t2[i] - t1[i]
}
data.frame(lambda = lambda, R = mean(R), ci = 2 * sd(R)/sqrt(N), loi = law,
mode = mode)
# ci pour calculer l'intervalle de confiance a 95%
} #fin fonction
tracelambdaP <- function(mode, law) {
df = data.frame()
for (lambda in seq(0.2, 0.8, by = 0.2)) {
if (mode == "reinit") {
df = rbind(df, preemptifINIT(3000, lambda, law))
} else if (mode == "redem") {
df = rbind(df, preemptifREDEM(3000, lambda, law))
}
}
df
}
tracerm <- function(mode) {
tab <- c()
tab[1] = "exp"
tab[2] = "det"
tab[3] = "unif"
tab[4] = "erlang"
tab[5] = "erlang2"
tab[6] = "erlang3"
datafinal = data.frame()
for (i in 1:6) {
datafinal = rbind(datafinal, tracelambdaP(mode, tab[i]))
}
datafinal
}
dafINIT = tracerm("reinit")
dafREDEM = tracerm("redem")
Question 2 : Étude détaillée de la file M/M/1
Nous regroupons toutes les dataframes en une, en reprenant le même principe que les fonctions précédentes.
tracelambdaMM1 <- function(type, law = "exp") {
df = data.frame()
for (lambda in seq(0.2, 0.8, by = 0.2)) {
if (type == "reinit") {
df = rbind(df, preemptifINIT(3000, lambda, law))
} else if (type == "redem") {
df = rbind(df, preemptifREDEM(3000, lambda, law))
} else if (type == "np") {
df = rbind(df, nonpreemptif(3000, lambda, law))
}
}
df
}
tracerMM1 <- function() {
tab <- c()
tab[1] = "np"
tab[2] = "reinit"
tab[3] = "redem"
finalframe = data.frame()
for (i in 1:3) {
finalframe = rbind(finalframe, tracelambdaMM1(tab[i]))
}
finalframe
}
ff = tracerMM1()
ggplot(data = ff, aes(x = lambda, y = R, ymin = R - ci, ymax = R + ci, color = factor(mode))) +
geom_point() + geom_line() + geom_errorbar(width = 0.01)
Pour les modes redémarrage et réinitialisation, le temps de réponse moyen ne varie pas considérablement. C'est le cas pour le mode non préemptif jusqu’au débit λ=0.6, où il commence à augmenter de de manière plus visible. Dans le mode non preemptif en choisissant de traiter le dernier processus arrivé, celui-ci peut avoir un temps de service conséquent. Si l'inter-arrivée est forte, cela ne pose pas de problème mais si il est faible, le temps de réponse peut exploser rapidement. Pour la réinitialisation le temps moyen est relativement faible à notre grande surprise (sous réserve que notre fonction soit juste). Tant que le nouveau temps de service obtenu est très faible, cela reste logique. Pour le redémarrage, il est de notre avis logique que le temps moyen soit élévé. Car un même processus est traité plusieurs fois avec le même temps de service. Cela devrait évidemment sur le flux de traitement. Ce n'est pas ce que nous obtenons. Peut-etre cela est-il du au fait que les temps de service sont faibles. Globalement, nous trouvons les temps de réponses relativement faibles par rapport à ce que nous avions obtenu pour les files FIFO (où le temps moyen de réponse pour la loi exponentielle pouvait dépasser 6). Rappelons nous que ce même mode FIFO retarde les processus à cause de la sucharge induite.
Question 3 : Étude détaillée de la file M/GI/1
Voici la courbe que nous observons pour le mode non préemptif :
ggplot(data = daf, aes(x = lambda, y = R, ymin = R - ci, ymax = R + ci, color = factor(loi))) +
geom_point() + geom_line() + geom_errorbar(width = 0.01)
Nous pouvons constater une croissance des courbes relativement faibles sauf pour le cas d'erlang de variance 5 où le temps de service explose très vite. Nous pouvons nous dire que le temps moyen de réponse du mode non préeemptif est assez faible, mais plus lambda augmente plus il augmente. En effet lorsque le débit est faible,les processus sont rapidement traitées. Le temps d'attente est par conséquent faible. Alors que lorsqu'il est élevé, les processus les plus anciens attendent longtemps avant d’être traités.
ggplot(data = dafINIT, aes(x = lambda, y = R, ymin = R - ci, ymax = R + ci,
color = factor(loi))) + geom_point() + geom_line() + geom_errorbar(width = 0.01)
Pour le mode réinitialisation, les temps moyens sont plus faibles que poour la mode non préemptif. Cependant, il est étonnant qu'il n'y ait pas “d'explosion” dans le cas de loi d'Erlang de variance. A part cela les courbes suivent la même tendance, meme si la loi exponentielle et la loi d'Erlang de variance 1 fournissent les temps de réponse moyens les plus faibles.
ggplot(data = dafREDEM, aes(x = lambda, y = R, ymin = R - ci, ymax = R + ci,
color = factor(loi))) + geom_point() + geom_line() + geom_errorbar(width = 0.01)
Pour le mode réinitialisation, jusqu'à λ=0.6, excepté la loi d'Erland de variance 5, tous les courbes suivent la même tendance. Les temps de réponse moyens sont presque pareils avec celles du mode avec redémarrage.
Question 4 D'après les courbes obtenus, nous pouvons conclure que la variance a un impact assez considérable notamment dans le cas du mode non préemptif. Les lois ne semblent pas avoir autant d'influence sur les modes. Cependant les modes eux ont un impact bien réels sur les performances. Malheureusement nous n'avons pas pu implémenter le mode avec reprise, mais le mode préemptif en général s'avère plus efficace que le mode non préemptif.