par BOEY Lionel et GUO Tianming
Non-preemptif
Dans le mode non-preemptif, on a utilise deux listes “waiting list(WL)” et “final order(FO)”
*Waiting list est cree pour registrer les processus qui sont en attente par l'ordre inverse
*Final order est crée pour register les processus qui sont deja execute par l'ordre normale
A la fin de l'execution, il y a certain de processus reste dans waiting list avec ordre “LIFO”(inverse)
Final order = final order + waiting list
Donc, le “final order” devien un nouvel liste qui registrent tous les processus par l'ordre d'execution.
t1 sont toujours = cumsum(A)
En ce moment la , le nouveau “final order” est bien comme le file FIFO,
donc, t2[i] = max(t2[i-1],t1[i])+S[i]
Definition des generateurs
library(ggplot2)
library(plyr)
set.seed(10)
service <- function(loi, mu = 1) {
if (loi == "exp") {
return(rexp(1, mu))
}
if (loi == "unif") {
return(runif(1, 0, mu))
}
if (loi == "dete") {
return(runif(1, mu, mu))
}
if (loi == "erlang") {
return(rgamma(1, shape = 1, rate = mu))
}
}
interarrivee <- function(lambda) {
return(rexp(1, lambda))
}
# Fonction simulation() pour generer le tableau de dataframe
Nonpree <- function(N, lamb, loi) {
t1 <- c(1:N)
t2 <- c(1:N)
S <- c(1:N)
A <- c(1:N)
R <- c(1:N)
for (i in 1:N) {
S[i] <- service(loi)
A[i] <- interarrivee(lamb)
}
# Comme condition initiale on prendra t1[1]=t2[1]=0
t1[1] <- 0
t2[1] <- t1[1] + S[1]
FO <- c() #final order
FO <- c(FO, (1))
WL <- c() #waiting list
cp = 1 #current processus
t1 <- cumsum(A) #t1 for all
for (i in 1:N) {
S[i] <- service(loi)
A[i] <- interarrivee(lamb)
}
# Comme condition initiale on prendra t1[1]=t2[1]=0
t1[1] <- 0
t2[1] <- t1[1] + S[1]
FO <- c() #final order
FO <- c(FO, (1))
WL <- c() #waiting list
cp = 1 #current processus
t1 <- cumsum(A) #t1 for all
for (i in 2:N) {
if (t1[i] <= t2[cp]) {
# new process coming and the current process have not finished it's excution
WL <- c((i), WL) #put the new process it into the waiting list
} else {
if (length(WL) == 0) {
# if the system is free and waiting list is empty
t2[i] = t1[i] + S[i] #the new process execute
FO <- c(FO, (i))
cp = i
} else {
# waiting list is not empty when the new process arrival time is always
# larger && waiting list is not null
while (t1[i] > t2[cp] && length(WL) > 0) {
x = WL[1] #put the last process into the stack
c_wait = WL[-1] #delete the process from the waiting list
WL = c_wait
t2[x] = t2[cp] + S[x]
FO <- c(FO, (x)) #put it into final list
cp = x
}
WL <- c((i), WL) #add the new process into the top of the waiting list
}
}
}
p <- length(WL)
for (i in 1:p) {
# add the waiting list into the final order
FO <- c(FO, (WL[i]))
}
# we've changed a list with order LIFO into a new list with order FIFO
for (i in 2:N) {
t2[FO[i]] <- S[FO[i]] + max(t1[FO[i]], t2[FO[i - 1]])
}
for (i in 1:N) {
R[i] <- t2[i] - t1[i] #temps de sortie - temps d'entrée
}
data.frame(lambda = lamb, R = mean(R), A = mean(A), S = mean(S), ci = 2 *
sd(R)/sqrt(N), loi = loi)
}
tracelambda <- function(loi) {
df = data.frame()
for (lambda in seq(0.2, 0.8, by = 0.2)) {
df = rbind(df, Nonpree(10000, lambda, loi))
}
df
}
loi <- c()
loi[1] = "exp"
loi[2] = "unif"
loi[3] = "dete"
loi[4] = "erlang"
dataframe = data.frame()
for (i in 1:4) {
set.seed(10)
dataframe = rbind(dataframe, tracelambda(loi[i]))
}
Tracons la courbe
ggplot(data = dataframe, aes(x = lambda, y = R, ymin = R - ci, ymax = R + ci,
color = factor(loi))) + geom_point() + geom_line() + geom_errorbar(width = 0.01)
On a utilesé 10000 échantillons pour tester, comme FIFO, le temps moyen de reponse devient grande avec l'augmentation du lambda.
Pour la loi uniforme, le temps de service S est toujours dans [0,1], la reponse R est très rapide, donc, le temps moyen de reponse et l'intervalle de confiance sont toujours petits.Concernant les autres trois courbes, dans notre cas, les durées des services sont constantes pour la loi deterministe, son temps de reponse R est décidé par l'inter-arrivée A(loi exponentielle). Loi de Erlang peut être considérée comme la somme de N variables aléatoires indépendantes de même loi exponentielle de paramètre lambda. Pour la loi exponentielle, les S=rexp(1,0.X) sont probablement grande que les A=rexp(1,1), alors le paramètre lambda sur loi exponentielle a bien influencé les temps moyen de reponse R dans ce trois cas. Pour la taille de l'intervalle de confiance ci=2*sd®/sqrt(N), elle est bien influencé par lambda aussi.
Preemption redemarrage
Dans ce methode, quand une arrivée entre dans le système, il peut etre interrompu par une autre arrivé. Dans ce cas, on la met dans la pile d'attente et essaye de la traiter si possible avec la politique LIFO, en recommencant avec le temps de traitement initial. L'algo est personel et commenté pour mieux comprendre :
library(ggplot2)
library(plyr)
set.seed(15)
service <- function(loi, mu = 1) {
if (loi == "exp") {
return(rexp(1, mu))
}
if (loi == "unif") {
return(runif(1, 0, mu))
}
if (loi == "dete") {
return(runif(1, mu, mu))
}
if (loi == "erlang") {
return(rgamma(1, shape = 1, rate = mu))
}
}
interarrivee <- function(lambda) {
return(rexp(1, lambda))
}
Response <- function(n, typeservice, lambda, mu) {
t1 <- c(1:n)
t2 <- c(1:n)
S <- c(1:n)
A <- c(1:n)
R <- c(1:n)
for (i in 1:n) {
S[i] <- service(typeservice)
A[i] <- interarrivee(lambda)
}
t1 <- cumsum(A)
# DEBUT ALGO REDEMARRAGE
# une fonction pour reperer la position d'une arrive dans la liste t1 a
# partir de la liste de message a 4 decimal pres
repere <- function(x) {
for (i in 1:n) {
if (round(x, 4) == round(t1[i], 4)) {
return(i)
}
}
}
waiting = c() #pile d'attente initialisé vide
justout = 0 #cet variable indique le dernier temps de sortie t2 du système
i = 1
while (i < n) {
myjustout = t1[i] + S[i] #myjustout indique le temps de sortie si le processus courant i execute
if (t1[i + 1] > myjustout) {
# i pourrait executer, il faut verifier ce qu'il y a dans la pile d'attente
# qeulquechose dans la pile d'attente
if (length(waiting) != 0) {
last = length(waiting) # je recupere le sommet de la pile d'attente
x = repere(waiting[last]) # j'utilise la fonction repere() pour reperer la position vrai du sommet de la pile, dans la liste t1
if ((justout + S[x]) > t1[i]) {
# le sommet de pile n'a pas droit d'executer, du coup i peut executer
t2[i] = t1[i] + S[i]
justout = t2[i]
i = i + 1
} else {
# sommet de pile peut executer, on garde i pour reboucler
t2[x] = justout + S[x]
justout = t2[x]
waiting = waiting[-last]
}
} else {
# i peut executer!!! on mettre à jour justout chaque fois
t2[i] = myjustout
justout = t2[i]
i = i + 1
}
} else {
# i ne peut pas executer, on le met dans la liste d'attente
waiting = c(waiting, t1[i])
justout = t1[i + 1]
i = i + 1
}
}
# waiting = c(waiting,t1[i]) # on ajoute la dernier de la liste dans le pile
# car il est forcement préempté justout = t1[i]
# on traite les derniers arrives dans la liste d'attente par ordre
# decroissant dans la liste
j = length(waiting)
while (j != 0) {
x = repere(waiting[j])
t2[x] = justout + S[x]
justout = t2[x]
waiting = waiting[-j]
j = length(waiting)
}
##### FIN ALGO REDEMARRAGE######
R = t2 - t1
data.frame(lambda = lambda, R = mean(R), A = mean(A), S = mean(S), ci = 2 *
sd(R)/sqrt(n), loi = typeservice)
}
tracelambda <- function(loi) {
df = data.frame()
for (lambda in seq(0.2, 0.8, by = 0.2)) {
df = rbind(df, Response(1000, loi, lambda, 1)) # nb d'arrivée
}
df
}
loi <- c()
loi[1] = "exp" # Loi exponentielle
loi[2] = "unif" # Loi uniforme
loi[3] = "dete" # Loi deterministe
loi[4] = "erlang" # Loi erlang
dataframe = data.frame()
for (i in 1:4) {
set.seed(15)
dataframe = rbind(dataframe, tracelambda(loi[i]))
}
ggplot(data = dataframe, aes(x = lambda, y = R, ymin = R - ci, ymax = R + ci,
color = factor(loi))) + geom_point() + geom_line() + geom_errorbar(width = 0.01)
Ici on constate un temps de réponse très grand (environ 250 pour 1000 processus), ce qui est normal car la méthode démarrage est plutot barbare and on perd du temps exponentiellement chaque fois un processus est préempté.
Si on zoom sur le graph, on peut voir l'éclatement des temps de reponse à partir de lambda = 0.4, plus significant sur la loi exponentiel, ensuite la loi Erlang, suivi de la loi deterministe
La courbe n'est pas très parlant et je suppose qu'il faut prend plus d'échantillons pour la lisser un peu. Mais vu la complexité de l'algo, un echantillon de 2000 peut prendre jusqu'à 5 minutes et donc je me contente de 1000.
Préemption réinitialise
Cette méthode ressemble au précedent (redémarrage) car on reinitialise le temps de service après un préemption. Pour l'implementer, il suffit juste de recuperer un nouveau temps de service et le mettre dans S[i] si un processus est préempté(passe dans la pile d'attente). Sinon l'algo est le meme que précédemment.
Response <- function(n, typeservice, lambda, mu) {
t1 <- c(1:n)
t2 <- c(1:n)
S <- c(1:n)
A <- c(1:n)
R <- c(1:n)
for (i in 1:n) {
S[i] <- service(typeservice)
A[i] <- interarrivee(lambda)
}
t1 <- cumsum(A)
### DEBUT ALGO REINIt###
# une fonction pour reperer la position d'une arrive dans la liste t1 a
# partir de la liste de message a 4 decimal pres
repere <- function(x) {
for (i in 1:n) {
if (round(x, 4) == round(t1[i], 4)) {
return(i)
}
}
}
waiting = c() #pile d'attente initialisé vide
justout = 0 #cet variable indique le dernier temps de sortie t2 du système
i = 1
while (i < n) {
myjustout = t1[i] + S[i] #myjustout indique le temps de sortie si le processus courant i execute
if (t1[i + 1] > myjustout) {
# i pourrait executer, il faut verifier ce qu'il y a dans la pile d'attente
# qeulquechose dans la pile d'attente
if (length(waiting) != 0) {
last = length(waiting) # je recupere le sommet de la pile d'attente
x = repere(waiting[last]) # j'utilise la fonction repere() pour reperer la position vrai du sommet de la pile, dans la liste t1
if ((justout + S[x]) > t1[i]) {
# le sommet de pile n'a pas droit d'executer, du coup i peut executer
t2[i] = t1[i] + S[i]
justout = t2[i]
i = i + 1
} else {
# sommet de pile peut executer, on garde i pour reboucler
t2[x] = justout + S[x]
justout = t2[x]
waiting = waiting[-last]
}
} else {
# i peut executer!!! on mettre à jour justout chaque fois
t2[i] = myjustout
justout = t2[i]
i = i + 1
}
} else {
# i ne peut pas executer, on le met dans la liste d'attente
waiting = c(waiting, t1[i])
S[i] = service(typeservice) #reinitialisation de temps de service
justout = t1[i + 1]
i = i + 1
}
}
# waiting = c(waiting,t1[i]) # on ajoute la dernier de la liste dans le pile
# car il est forcement préempté justout = t1[i]
# on traite les derniers arrives dans la liste d'attente par ordre
# decroissant dans la liste
j = length(waiting)
while (j != 0) {
x = repere(waiting[j])
t2[x] = justout + S[x]
justout = t2[x]
waiting = waiting[-j]
j = length(waiting)
}
##### FIN ALGO REINIT######
R = t2 - t1
data.frame(lambda = lambda, R = mean(R), A = mean(A), S = mean(S), ci = 2 *
sd(R)/sqrt(n), loi = typeservice)
}
tracelambda <- function(loi) {
df = data.frame()
for (lambda in seq(0.2, 0.8, by = 0.2)) {
df = rbind(df, Response(2000, loi, lambda, 1)) # nb d'arrivé
}
df
}
loi <- c()
loi[1] = "exp" # Loi exponentielle
loi[2] = "unif" # Loi uniforme
loi[3] = "dete" # Loi deterministe
loi[4] = "erlang" # Loi erlang
dataframe = data.frame()
for (i in 1:4) {
set.seed(10)
dataframe = rbind(dataframe, tracelambda(loi[i]))
}
ggplot(data = dataframe, aes(x = lambda, y = R, ymin = R - ci, ymax = R + ci,
color = factor(loi))) + geom_point() + geom_line() + geom_errorbar(width = 0.01)
Le temps de reponse reste toujours grande. Avec cette méthode, on voit que l'explosion est plus significant par la loi deterministe en lambda ascendant, suivi de la loi exponentielle puis Erlang.
====Conclusion==== En faisant ces testes par le principe de LIFO, nous constatons que la méthode sans préemption donne une meuilleur temps de réponse que celle avec préemptiion (plus ou moins comme FIFO). Nous n'avons pas pu faire la méthode “reprise” mais on peut supposer que son temps de réponse va etre beaucoup moins que les 2 autres méthode préemptive etant donné qu'il n'y a pas de temps supplémentaire ajouté à cause de la préemption (on continue d'ou on a arreté).