L’objectif de ce DM est l’étude d’un système de file d’attente où les processus sont élus selon une politique SRPT : Le processus dont le temps restant d’exécution est le minimum est choisi.
Le code suivant permet de simuler une file d’attente SRPT suivant plusieurs lois concernant le temps de service. On peut également jouer sur le fait de préempter ou non une tâche en cours lorsqu’un nouveau processus arrive. Ce code est simplement une modification par rapport au précédent DM.
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),
gamma = rgamma(n,shape=x,scale=y),
exp = rexp(n,x)
)
}
FileSRPT <- function(n,lambda,typeservice,x,y,policy) {
# simulates a M/GI/1 SRPT 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 = S; # 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)]
if (policy == "spt_pmtn") { # Election based on service time
running <<- waiting[which.min(S[waiting])];
} else if (policy == "fifo") { # Election is fifo : Always the first of the list
running <<- waiting[1];
}
else { # Election based on remaining time
running <<- waiting[which.min(remaining[waiting])];
}
waiting <<- waiting[-which(waiting == running)];
}
}
push_task = function() { # insert the next_arrival-th task to the waiting list
# and run it if there is preemption
if ((policy != "fifo") & (policy != "spt")) {
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()
}
}
data.frame(val = t2-t1, policy = policy, lambda = lambda);
}
Nous effectuons, comme lors du précédent DM, une étude du temps de réponse en fonction des différentes lois de temps de service. La graine permettant de générer les nombres aléatoires est réinitialisé après chaque sélection d’une politique : la simulation se fait, pour chaque politique, sur le même jeu de temps de service.
n = 10000; # Nombre de processus
type = "exp" # Loi régisssant les temps de service
lamb_exp = 1 # Paramètre lambda de la loi exponentielle
resultat = data.frame();
for(pol in c("spt", "spt_pmtn", "srpt_pmtn", "fifo")) {
set.seed(42);
for(lamb in seq(from = 0.1, to = 0.9, by = 0.1)) {
resultat = rbind(resultat, FileSRPT(n = n,lambda = lamb, policy = pol, x = lamb_exp, typeservice = type));
}
}
resultat = ddply(resultat, c("lambda", "policy"), summarize,
tps_rep = mean(val),
tps_rep_max = max(val),
error = 2*sd(val)/sqrt(length(val)),
toperr = tps_rep + error,
boterr = tps_rep - error);
ggplot(data = resultat, aes(x = lambda, y = tps_rep, colour = policy)) + geom_line() + theme_bw() + scale_x_continuous(breaks = seq(from = 0.1, to = 0.9, by = 0.1)) + geom_errorbar(aes(ymax = toperr, ymin = boterr, width = 0.01));
On observe une différence bien marquée entre FIFO et les autres politiques. Les tâches les plus courtes ne sont pas forcément exécutées en premières. Les temps de réponse ne sont donc pas optimisés.
Pour mieux étudier les 3 autres courbes, réduisons l’échelle des ordonnées :
ggplot(data = resultat, aes(x = lambda, y = tps_rep, colour = policy)) + geom_line() + theme_bw() + scale_x_continuous(breaks = seq(from = 0.1, to = 0.9, by = 0.1)) + geom_errorbar(aes(ymax = toperr, ymin = boterr, width = 0.01)) + ylim(min = 1, max = 5);
## Warning: Removed 1 rows containing missing values (geom_path).
Le SRPT est le plus efficace : à chaque arrivée, on compare l’ensemble des temps restant pour ne garder que le plus faible. On cherche ainsi à évacuer le plus rapidement les tâches de la liste des tâches en attente. La version SPT préemptive est légèrement moins efficace car la comparaison se fait sur les seuls temps de service. Enfin, la SPT non préemptive est encore moins performante car on ne change de tâche que lorsque une autre s’est terminée.
Etudions maintenant le temps de réponse maximal de chaque politique :
ggplot(data = resultat, aes(x = lambda, y = tps_rep_max, colour = policy)) + geom_line() + theme_bw() + scale_x_continuous(breaks = seq(from = 0.1, to = 0.9, by = 0.1));
Ces résultats ne sont pas surprenants : les politiques de la famille SPT privilégient l’élection des tâches les plus courtes en premières. Les tâches les plus longues sont donc reportées à la fin ce qui augmente d’autant plus leur temps de réponse.
On effectue la simulation avec un temps égal à 1 pour toutes les tâches. Certaines courbes semblent se recouvrir, ajoutons un léger bruit artificiel afin de les distinguer (jittering).
ggplot(data = resultat, aes(x = lambda, y = tps_rep, colour = policy)) + geom_line(position = position_jitter(w = 0, h = 0.05)) + theme_bw() + scale_x_continuous(breaks = seq(from = 0.1, to = 0.9, by = 0.1)) + geom_errorbar(aes(ymax = toperr, ymin = boterr, width = 0.01));
Ici, les politiques SPT non préemptive, SRPT préemptive et FIFO semblent être les plus efficaces et équivalentes. Les tâches sont exécutées dans l’ordre de leurs arrivées et d’un coup dans le cas de FIFO et SPT non préemptive. Pour ce qui est de la version SRPT, la tâche élu est forcément celle entamée, la tâche préemptée est donc réélue immédiatement.
En revanche, pour SPT préemptive, la tâche actuelle est remise en fin de liste d’attente avant d’élire un nouveau processus. La comparaison se faisant sur les temps de service, le premier de la liste est élu (fonctionnement de la fonction R which.min()), donc une tâche qui aurait pû être terminée rapidement (en comparaison avec la tâche arrivante) se trouve remise dans la file d’attente. Les temps de réponse sont donc plus importants. Si which.min() retournait la dernière tâche de la liste, les temps de réponse seraient les même pour les 3 politiques.
Les 4 fonctions ayant le même comportemant, l’étude des temps de réponse maximaux est inutile.
Les temps de service suivent une loi uniforme sur l’intervalle \([0;1]\) Comme dans le premier test, la politique FIFO est la moins performante. Cependant, cet écart de performance est moins prononcé que précédemment.
On suppose que cela est dû au fait que, contrairement à la loi exponentielle, la loi uniforme restreint l’intervalle de temps de service (aucune valeur plus grande que 2 n’est générée). Le résultat se rapproche donc de celui observé avec un temps de service unique.
La simulation suivante a pour but d’appuyer cette hypothèse en renouvelant l’expérence avec l’intervalle \([0.75;1.25]\) puis \([0.9,1.1]\). On utilise à nouveau un léger bruit artificiel pour distinguer les courbes trop proches.
SPT non préemptive est à nouveau la politique la moins efficace et les 3 autres ont des performances comparables, l’hypothèse semble donc être vraie.
De nouveau, le temps de réponse max en mode FIFO est bien plus faibles qu’avec les autres méthodes.
On fait ici 2 simulations, une où les paramètres de la loi gamma sont \((0.2;5)\) et une où ils sont à \((4;0.25)\).
On commence par donner la densité de ces 2 fonctions
On lance ensuite la simulation. En ce qui concerne la première loi gamma, le résultat semble assez similaire à la loi exponentielle. La courbe de la densité est d’ailleurs similaire à une loi exponentielle et l’efficacité de la politique FIFO est nettement moins bonne que les trois autres.
Avec la seconde loi gamma, on a peu de faibles valeurs générées pour les temps de service. Les politiques de la famille SPT ont donc plus de difficultés à évacuer rapidement les tâches de la file d’attente et l’écart en performance est donc moins marqué avec FIFO.
Ci-dessous sont présentées les courbes des temps de réponse maximaux.