L’objectif est d’analyser l’importance de la distribution du temps de service sur le temps de réponse dans une file d’attente M/GI/1 avec un ordonnancement LIFO. Le processus d’arrivée est un processus de Poisson de taux (débit), les clients ont un temps de service de moyenne 1 pris comme unité de temps de référence.
set.seed(10)
library(plyr)
library(ggplot2)
Service <- function(n=1,typeservice,x,y) {
# genere un temps de service
switch(typeservice,
det = rep(1,n),
uni = runif(n,x,y),
gamma1 = rgamma(n,shape=x,scale=y),
gamma2 = rgamma(n,shape=x,scale=y),
exp = rexp(n,x)
)
}
FileLIFO <- function(n,lambda,typeservice,x,y,policy) {
# simulates a M/GI/1 LIFO queue with different preemption policy
# parameters:
# n : total number of jobs
# lambda : arrival rate
# typeservice : service law (det uni gamma exp)
# x ,y : parameters of the service law
# policy: npmtn, pmtn, pmtn_restart, pmtn_reset
# return value:
# vector with response time of each task assuming the queue is initially empty
A <- rexp(n,lambda) # inter arrival
t1 <- cumsum(A) # arrival dates
t2 <- rep(NA,n) # completion dates
S <- Service(n,typeservice,x,y) # initial service times
#### Variables that define the state of the queue
t = 0 # current time
remaining = rep(NA,n) # how much work remains to do for each task
running = NA # index of the currently running task
waiting = c() # stack with tasks which have arrived and have not been completed yet
next_arrival = 1 # index of the next task to arrive
#### A few useful local functions
run_task = function() { # runs the last task of the waiting list
if(length(waiting)>0) {
running <<- waiting[length(waiting)]
remaining[running] <<- switch(policy,
npmtn = S[running],
pmtn = min(S[running],remaining[running],na.rm=T),
pmtn_restart = S[running],
pmtn_reset = Service(1,typeservice,x,y)
)
waiting <<- waiting[-length(waiting)]
}
}
push_task = function() { # insert the next_arrival-th task to the waiting list
# and run it if there is preemption
if(policy != "npmtn") {
if(!is.na(running)) {waiting <<- c(waiting,running)}
running <<- NA
}
waiting <<- c(waiting,next_arrival)
next_arrival <<- next_arrival+1
if(is.na(running)) { run_task() }
}
#### Main simulation loop
while(TRUE) {
# Look for next event
dt = NA
if(next_arrival <=n) { dt = min(dt,(t1[next_arrival]-t), na.rm=T) }
if(!is.na(running)) { dt = min(dt,remaining[running], na.rm=T) }
if(is.na(dt)) { break }
# Update state
t=t+dt
if(!is.na(running)) {
remaining[running] = remaining[running] - dt
if(remaining[running]<=0) {
t2[running] = t
running = NA
run_task()
}
}
if((next_arrival<=n) & (t==t1[next_arrival])) {
push_task()
}
}
#t2-t1
df <-data.frame(entree=t1,sortie=t2,diferentiel=t2-t1,servicelaw=typeservice,policy=policy,lambda=lambda)
df
}
Les explications autour des lois sont issus de notre compréhension générale des explications fournies sur http://www.jybaudot.fr/General/indexstats.html
La loi Déterministe
Le temps de service restera constant, quelque soit la fréquence d’arrivée (charge). Si, en plus la file LIFO n’est pas préemptive, alors le temps de service restera infime. Il ne dépend pas du nombre de clients à servir, le serveur suit une politique LIFO en servant la dernière requete (après avoir fini le job courant). On est ici dans un cas “idéal”, vers lequel on voudra tendre (load balancing, etc). Les autres lois de service sont plus réalistes quand à la gestion de la charge par un serveur, et du temps de service associé.
La loi Exponentielle
Celle ci est généralement utilisée dans des problèmes de durée de vie ( électronique ). La loi exponentielle est “sans mémoire”, c’est-à-dire qu’un phénomène a autant de chance de se produire à l’instant t1 qu’à l’instant t2, il ne dépend pas de notre attente. Pour cette étude, cela signifie que le temps de réponse ne dépend pas de la position de la requête dans la file.
La loi Gamma
Quand le paramètre k ( x dans notre fonction ) est un entier, alors la loi Gamma corespond à une distribution d’Erlang. Cette loi nous permet d’étudier une suite de variables aléatoires suivant elles même une loi exponentielle. Dans notre étude, cela nous permet d’étudier l’évolution du temps de réponse, après plusieurs “requêtes”. Au vu des courbes observées pour la loi Gamma, on pense à la simulation d’un système de cache, le délai de réponse diminuant au fur et à mesure que le cache se complète.
La loi Uniforme
On se retrouve dans le cas du “hasard” par défaut, la loi de l’équiprobabilité. Ainsi, une requête aura une probabilité 1/n d’être traitée, ce qui a pour conséquence une augmentation rapide du temps de réponse, suivant l’augmentation de la fréquence des arrivées. En effet, plus il y a de requêtes qui arrivent, moins notre requête en attente aura de chance d’être traitée, donc le temps de réponse global du système augmente. Pour notre simulation, on peut rapprocher cette loi d’une politique “équitable”, “non préférentielle”, personne ne sera “mieux servi”.
Nous avons choisis de similuer avec une file de 1000 jobs, afin d’avoir un temps de simulation correct et des données représentatives.
res <- data.frame()
lambda_seq <- seq(from=0.2,to=0.8,by=0.2)
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="npmtn"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="pmtn"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="pmtn_restart"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="pmtn_reset"))
}
res_calc = ddply(res,c("lambda","policy"),summarise,Temps_moyen_service=mean(diferentiel))
ggplot(data=res_calc,aes(x=lambda,y=Temps_moyen_service,color=policy)) + geom_point() + geom_line() + xlab("Fréquence d'arrivée") + ylab("Temps moyen de réponse") + ggtitle("Evolution du temps de réponse M/M/1") + scale_color_brewer(palette="Set1",name="Mode ",breaks=c("npmtn","pmtn","pmtn_restart","pmtn_reset"),labels=c("Non préemptif","Préemptif - resume ","Préemptif - restart ","Préemptif - reset"))
Le mode préemptif - restart (redélarrage du même service) nous retourne un temps de réponse nettement supérieurs aux autres modes de gestion.
Non-préemptif :
res <- data.frame()
lambda_seq <- seq(from=0.2,to=0.8,by=0.05)
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="uni",x=0.5,y=5,policy="npmtn"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="det",x=0.5,y=5,policy="npmtn"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma1",x=1,y=1/lambda_seq[i],policy="npmtn"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma2",x=0.5,y=1/lambda_seq[i],policy="npmtn"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="npmtn"))
}
res_calc = ddply(res,c("lambda","servicelaw"),summarise,Temps_moyen_service=mean(diferentiel))
ggplot(data=res_calc,aes(x=lambda,y=Temps_moyen_service,color=servicelaw)) + geom_point() + geom_line() + xlab("Fréquence d'arrivée") + ylab("Temps moyen de réponse") + ggtitle("Evolution du temps de réponse [Non Préemptif]") + scale_color_brewer(palette="Set1",name="Loi",breaks=c("uni","det","gamma1","gamma2","exp"),labels=c("Uniforme","Déterministe","Gamma (série 1)","Gamma (série 2)","Exponentielle"))
On observe une explosion du temps de réponse pour un temps de service suivant une loi uniforme. En ce qui concerne la loi exponentielle, observe une certaine instabilité dans le temps de réponse, qui croit en “dent de scie”. En ce qui concerne la loi Gamma, le temps de service tend à diminuer, on retrouve l’idée d’un “cache” évoqué plus tôt.
Préemptif - Resume job :
res <- data.frame()
lambda_seq <- seq(from=0.2,to=0.8,by=0.05)
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="uni",x=0.5,y=5,policy="pmtn"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="det",x=0.5,y=5,policy="pmtn"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma1",x=1,y=1/lambda_seq[i],policy="pmtn"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma2",x=0.5,y=1/lambda_seq[i],policy="pmtn"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="pmtn"))
}
res_calc = ddply(res,c("lambda","servicelaw"),summarise,Temps_moyen_service=mean(diferentiel))
ggplot(data=res_calc,aes(x=lambda,y=Temps_moyen_service,color=servicelaw)) + geom_point() + geom_line() + xlab("Fréquence d'arrivée") + ylab("Temps moyen de réponse") + ggtitle("Evolution du temps de réponse [Préemptif - Resume job]") + scale_color_brewer(palette="Set1",name="Loi",breaks=c("uni","det","gamma1","gamma2","exp"),labels=c("Uniforme","Déterministe","Gamma (série 1)","Gamma (série 2)","Exponentielle"))
On retrouve un comportement similaire au mode non-préemptif. Cependant, le phénomène de cache que l’on peut observer sur la série 1 de la loi Gamma est plus “réaliste” ( dans le mode non préemptif, nous constations une augmentation du temps de service dans un premier temps). Les courbes suivent la même tendance, cependant on peut noter que le temps de réponse est particulièrement impacté par le mode de la file LIFO dans le cas d’une temps de service suivant une loi uniforme. Le temps de service suivant une loi exponentielle est impacté, dans une moindre mesure également. Cela s’explique par le fait qu’ici, un job peut être interompu, et “l’équitée” de la loi uniforme aura pour conséquence une plus longue attente avant que le job soit de nouveau “selectionné” et traité. Le temps de réponse suivant la loi exponentielle est croit de façon plus stable ici (les dents de scie sont aténuées ).
Préemptif - Restart job
res <- data.frame()
lambda_seq <- seq(from=0.2,to=0.8,by=0.05)
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="uni",x=0.5,y=5,policy="pmtn_restart"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="det",x=0.5,y=5,policy="pmtn_restart"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma1",x=1,y=1/lambda_seq[i],policy="pmtn_restart"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma2",x=0.5,y=1/lambda_seq[i],policy="pmtn_restart"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="pmtn_restart"))
}
res_calc = ddply(res,c("lambda","servicelaw"),summarise,Temps_moyen_service=mean(diferentiel))
ggplot(data=res_calc,aes(x=lambda,y=Temps_moyen_service,color=servicelaw)) + geom_point() + geom_line() + xlab("Fréquence d'arrivée") + ylab("Temps moyen de réponse") + ggtitle("Evolution du temps de réponse [Préemptif - Restart job]") + scale_color_brewer(palette="Set1",name="Loi",breaks=c("uni","det","gamma1","gamma2","exp"),labels=c("Uniforme","Déterministe","Gamma (série 1)","Gamma (série 2)","Exponentielle"))
Les lois Gamma illustrent la forte influence d’un système de cache, pour éviter de répéter par exemple de lourds calculs, et améliorer le temps de réponse. Une nouvelle fois, un temps de service suivant une loi uniforme sera pleinement impacté par le mode restart, qui aura des conséquence catastrophiques sur le temps de réponse. Déjà que le job a autant de chance qu’un autre d’être selectionné, si il doit en plus recommencer au début à chaque fois qu’il est interompu… Un temps de service suivant une loi exponentielle semble tendre vers un palier, et se stabiliser autour d’une valeur. Cela est particulièrement interessant !
Préemptif - Reset job
res <- data.frame()
lambda_seq <- seq(from=0.2,to=0.8,by=0.05)
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="uni",x=0.5,y=5,policy="pmtn_reset"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="det",x=0.5,y=5,policy="pmtn_reset"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma1",x=1,y=1/lambda_seq[i],policy="pmtn_reset"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="gamma2",x=0.5,y=1/lambda_seq[i],policy="pmtn_reset"))
}
for(i in 1:length(lambda_seq)){
res <- rbind(res,FileLIFO(n=1000,lambda=lambda_seq[i],typeservice="exp",x=0.5,policy="pmtn_reset"))
}
res_calc = ddply(res,c("lambda","servicelaw"),summarise,Temps_moyen_service=mean(diferentiel))
ggplot(data=res_calc,aes(x=lambda,y=Temps_moyen_service,color=servicelaw)) + geom_point() + geom_line() + xlab("Fréquence d'arrivée") + ylab("Temps moyen de réponse") + ggtitle("Evolution du temps de réponse [Préemptif - Reset job]") + scale_color_brewer(palette="Set1",name="Loi",breaks=c("uni","det","gamma1","gamma2","exp"),labels=c("Uniforme","Déterministe","Gamma (série 1)","Gamma (série 2)","Exponentielle"))
Initialement, nous pensions obtenir des courbes similaires au précédent mode (restart), mais l’amélioration des performances est flagrante sur les loi Gamma. Dès le début, nous avons un temps de réponse, qui diminuera légèrement au cours du temps. Les performances s’améliorent légèrement sur le temps de service suivant une loi uniforme. Ce “nouveau tirage” semble améliorer les performances sur les différentes lois.
Le mode de fonctionnement non préemptif apportera un meilleur temps de réponse en moyenne. Il peut être intéressant de pouvoir interrompre une tache, et dans ce cas, le mode préemptif - resume ( reprise de la tache au point où on l’avait abandonnée) est assez logiquement le mode préemptif le plus performant.
Suivant la nature de la tache exécutée, ce dernier mode ne sera pas souhaitable : sur une section critique de code, protégée par un verrou,le job sera interompu, mais le verrou ne sera pas libéré pour autant. Pire encore, la section critique demeurera innacessible tant que le processus interompu n’aura pas repris la main et terminé son execution.