GUO KAI & ZHANG ZHENGMENG C'est la première part “non préemptif”
library(ggplot2)
library(plyr)
set.seed(3)
lifo_San_Pre <- function(loi, n, lanb, mu) {
# definition de queue de LIFO
a <- rexp(n, rate = 1) #intervalle de temps de service du serveur
b <- c() #intervalle de temps de 2 msg arrive suivants
d <- c() #tableau enregistant le temps de service pour chaque msg dans le pile
t_arrv <- c() #date d'arrivee d'un msg
t_sort <- c() #date de sort d'un msg
wait <- c() #temps d'attente d'etre servi d'un msg
waitNum <- 0 #nombre de msg d'attente dans le pile
pt <- 0 #pointeur de toit de pile d'attente
pc <- 0 #pointeur de msg courant du toit dans le queue d'attente du pile
pmct <- 0 #pointeur de msg courant traité par le serveur
t_reste <- 0 #
rec <- c() #le numero de msg dans le pile
reo <- c()
# initialisation de loi observee
switch(loi, exp = {
# distribution exponentiel
b <- rexp(n, rate = lanb)
}, unif = {
# distribution uniform
b <- runif(n, 0, mu)
}, det = {
# distribution deterministe
b <- rep(1, n)
}, erlang = {
# distribution erlang
b <- rgamma(n, shape = lanb, scale = mu)
})
# initialisation de variable
t_arrv[1] <- 0 # initialiser le queue d'attente
for (i in 2:n) {
t_arrv[i] <- t_arrv[i - 1] + b[i]
}
t_sort[1] <- a[1] #le premier msg va être complètement servi sans être interrompu
# l'algo commence..
pt <- 0
# pmct<-1
reo[1] <- 1
re <- 1
i <- 2 #compteur de msg d'envisager d'etre servi
while (i <= n) {
if (t_arrv[i] <= t_sort[re]) {
pt <- pt + 1 #si un message arrive avant le sortie du message courant traité, met le dans le pile d'attente,incrémente le pointeur pour qu'il pointe le toit du pile d'attent
wait[pt] <- t_sort[re] - t_arrv[i] #donc la date d'etre servi de ce message égale la date de sortie du message
waitNum <- waitNum + 1
rec[pt] <- i
i <- i + 1
} else {
if (waitNum == 0) {
# s'il n'y a pas de msg attend dans le pile, ce message sera servi tout de
# suite
re <- i
t_sort[i] <- t_arrv[i] + a[i] #donc t_sort[i] egale le temps qu'il est arrive plus the temps de traitement au serveur
i <- i + 1
} else {
t_sort[rec[pt]] <- t_sort[re] + a[rec[pt]]
re <- rec[pt]
pt <- pt - 1
waitNum <- waitNum - 1
# t_reste<-t_arrv[pt]-t_arrv[i] #temps d'attente potentiel optimisme du msg
# au toit du pile d'etre servi if(t_reste<wait[pt]){ #si pendant la lacune
# d'attendre d'etre servi du msg au toit du pile d'attente, msg[i] arrive
# alors # pc<-pt pt<-pt+1 #on met ce msg nouvellement arrivant au toit du
# pile wait[pt]<-t_sort[re]-t_arrv[i]#donc le temps d'attend potentiellment
# pour msg[i] egale le t_sort courant plus le temps de service d[pt]<-a[i]
# #on enregistre le temps de service de ce msg egalement pour le recurrence
# futur rec[pt]<-i waitNum<-waitNum+1 #puisque chaque msg dans le pile ne
# sera servi que dans le msg precedant est servi }else{
# t_sort[pt]<-t_sort[re]+d[pt]#sinon on fait sortir le msg au toit du pile
# re<-pt ss<-t_sort[pt] # wait[pt]<-ss-t_arrv[i] rec[pt]<-pt # pmct<-pmct+1
# #on augmente le msg sortie par 1 }
}
}
# chaque loop, on a toujours traite un msg n'import que l'a mis dans le pile
# ou l'a traite
}
# t_sort[rec[pt]]<-t_sort[re]+d[pt] waitNum<-waitNum-1 pt<-pt-1 for(j in
# 1:waitNum){ t_sort[rec[pt]]<-t_sort[rec[pt+1]]+d[pt] pt<-pt-1 }
plot(t_arrv, main = paste("LIFO: MSG arrive in rule: ", loi), cex.main = 1,
xlab = "time dimension", col = "red")
plot(t_sort, main = "LIFO: MSG served in rule: exp", cex.main = 1, xlab = "time dimension",
col = "green")
}
par(mfrow = c(4, 2), mar = c(4, 4, 2, 2), bg = "black", col.axis = "yellow",
col.lab = "yellow", fg = "yellow")
lifo_San_Pre("exp", 100, 1, 1)
lifo_San_Pre("unif", 100, 1, 1)
lifo_San_Pre("det", 100, 1, 1)
lifo_San_Pre("erlang", 100, 1, 1)
C'est la deuxière part “préemptif”
lifo_Pre <- function(loi, n, lanb, mu) {
df = data.frame
# definition de queue de LIFO
a <- rexp(n, rate = 1) #intervalle de temps de service du serveur
b <- c() #intervalle de temps de 2 msg arrive suivants
d <- c() #tableau enregistant le temps de service pour chaque msg dans le pile
t_arrv <- c() #date d'arrivee d'un msg
t_sort <- c() #date de sort d'un msg
wait <- c() #temps d'attente d'etre servi d'un msg
waitNum <- 0 #nombre de msg d'attente dans le pile
pt <- 0 #pointeur de toit de pile d'attente
pc <- 0 #pointeur de msg courant du toit dans le queue d'attente du pile
pmct <- 0 #pointeur de msg courant traité par le serveur
t_reste <- 0 #
rec <- c() #le numero de msg dans le pile
t_remain <- c() #temps servi d'1 msg i
re <- 0 # l'indice de msg traité en cours
# initialisation de loi observee
switch(loi, exp = {
# distribution exponentiel
b <- rexp(n, rate = lanb)
}, unif = {
# distribution uniform
b <- runif(n, 0, mu)
}, det = {
# distribution deterministe
b <- rep(1, n)
}, erlang = {
# distribution erlang
b <- rgamma(n, shape = lanb, scale = mu)
})
# initialisation de variable
t_arrv[1] <- 0 # initialiser le queue d'attente
for (i in 2:n) {
t_arrv[i] <- t_arrv[i - 1] + b[i]
}
t_sort[1] <- a[1] #le premier msg va être complètement servi sans être interrompu
plot(t_arrv, main = paste("LIFO:Message arrive in rule: ", loi), cex = 0.3,
xlab = "time dimension", ylab = "Message", col = "dark red", col.main = "red",
type = "h")
# l'algo commence..
pt <- 0 # a l'inititiation, le pile d'attente est vide
re <- 1 # le pointeur de msg traité en cours pointe à le premier msg
i <- 2 #compteur de msg d'envisager d'etre servi
while (i <= n) {
if (t_arrv[i] <= t_sort[re]) {
# un message arrive avant que le msg traité en cours se termine, il sera
# servi.
t_sort[i] <- t_arrv[i] + a[i] # ce msg va être servi tout de suite n'import quoi
pt <- pt + 1 #mettre le msg traité en cours dans le pile d'attente
t_remain[pt] <- t_sort[re] - t_arrv[i] #note le temps restant de service pour qu'on le reprendra après
t_arrv[re] <- t_sort[i] #en théorie la date que ce msg sera repris débutera dès que le nouveau msg sort du serveur
waitNum <- waitNum + 1
rec[pt] = re #noter le numéro de ce msg empilé
re <- i #modifie le pointeur du msg traité en cours à celui nouvellement arrivant
i <- i + 1 # on traite le msg suivant
} else {
if (waitNum == 0) {
t_sort[i] <- t_arrv[i] + a[i] # dès qu'un message arrive, il sera servi.
re <- i #s'il n'y a pas de msg attend dans le pile, ce message sera servi et aucun message sera interrompu
i <- i + 1 #on traite le msg suivant
} else {
# sinon, c'est-à-dire qu'il y a eu des message en pile sortant d'être servi
# si la lacune entre le temps d'arriver le msg i et le msg servé tout à
# l'heure est > le temps restant d'être servi de msg au toit du pile
if (t_arrv[i] - t_sort[re] > t_remain[pt]) {
t_sort[rec[pt]] <- t_sort[re] + t_remain[pt] #alors on empile le msg au toit du pile et le traite
re <- rec[pt] #on modifie le pointeur courant traité à le msg empilé toute à l'heure
pt <- pt - 1 #modifier le pointeur du toit du pile
waitNum <- waitNum - 1 #le nombre de msg d'attendre est réduit par 1
# remarque qu'on ne incrémente pas le compteur de message arrivant, afin de
# prendre en compte le traitement du pile
} else {
t_sort[i] <- t_sort[re] + a[i] #si cette lacune n'est pas suffisant pour traité le msg au toit du pile, on traite le msg nouvellement arrivant
re <- i
i <- i + 1
}
}
}
}
plot(t_sort, main = "LIFO: Message served: exp", xlab = "time dimension",
col = "blue", col.main = "red", type = "h")
}
par(mfrow = c(4, 2), mar = c(4, 4, 2, 2), bg = "black", col.axis = "yellow",
col.lab = "yellow", fg = "yellow")
lifo_Pre("exp", 100, 1, 1)
lifo_Pre("unif", 100, 1, 1)
lifo_Pre("det", 100, 1, 1)
lifo_Pre("erlang", 100, 1, 1)
