DM file LIFO - David Levayer

Question 1 : simulons !

Après reflexion sur papier (formule de récurrence, exemples simples déroulés), je commence par réaliser une simulation simple pour vérifier que j'arrive bien à retrouver les résultats que j'attend. Pour cela, je simule :

un temps de service constant égal à 2
des inter-arrivées qui se rapproche (pas de souci au début, puis principe LIFO dans un second temps)
dans un second exemple : un cas limite où les arrivés sont très proches et les temps de traitement plutôt longs

Après plusieurs heures de recherche d'une formule de récurrence efficace, et obtenant un code de plus en plus compliqué à comprendre (même pour moi), j'ai décidé de recommencer à zéro.

J'ai dû recommencer à zéro une bonne dizaine de fois, en essayant plein de choses :

des parcours sur mes tableaux T1 et T2
des piles
un calcul du temps restant

…et j'en passe. Finalement, cette version semble fonctionner (pas d'erreurs et courbes “possibles”) :

genereLifoDF <- function(N, lambdaMin, lambdaMax, lambdaPas, loi, param1 = -1, 
    param2 = -1) {

    df = data.frame()

    for (lambda in seq(lambdaMin, lambdaMax, lambdaPas)) {

        A <- rexp(N, lambda)

        if (loi == "exp") {
            S = rexp(N, param1)  # 1
        } else if (loi == "det") {
            S = array(param1, N)  # 1
        } else if (loi == "unif") {
            S = runif(N, param1, param2)  # 0 2
        } else if (loi == "gamma") {
            S = rgamma(N, param1, param2)  # 1 1
        }

        T1 = c()
        T2 = c()
        R = c()
        stack = c()

        T1[1] = 0
        T2[1] = T1[1] + S[1]
        R[1] = T2[1] - T1[1]
        lastT2 = 1

        for (i in 2:N) {
            T1[i] = T1[i - 1] + A[i]
        }

        i = 2
        while (i <= N) {

            if (i <= N && T1[i] <= T2[lastT2]) {
                # Si des processus arrivent avant la fin de l'execution, on empile
                stack = c(stack, i)
                i = i + 1
            } else {
                # Ici, le processus i a un temps plus grand que celui de la fin de
                # l'execution Deux cas possibles : stack vide (pas d'arrivée pendant
                # l'execution), soit stack pleine

                if (length(stack) == 0) {
                  # Stack vide : on traite le processus i
                  T2[i] = T1[i] + S[i]
                  lastT2 = i
                  i = i + 1
                } else {
                  # Stack pleine : on traite le dernier empilé
                  aTraiter = stack[length(stack)]
                  T2[aTraiter] = T2[lastT2] + S[aTraiter]
                  lastT2 = aTraiter
                  # On dépile
                  stack = stack[-length(stack)]
                }
            }

            # Si on est au bout de la liste des T1, alors les processus restants sont
            # dans la pile On les calcule donc les uns après les autres
            while (i > N && length(stack) != 0) {
                aTraiter = stack[length(stack)]
                T2[aTraiter] = T2[lastT2] + S[aTraiter]
                lastT2 = aTraiter
                stack = stack[-length(stack)]
            }
        }
        # Pris sur votre correction de la file FIFO : création d'un label
        label = as.factor(paste(loi, "(", param1, ",", param2, ")", sep = ""))
        df = rbind(df, data.frame(A = A, Sinit = S, S = S, T1 = T1, T2 = T2, 
            R = T2 - T1, lambda = lambda, loi = loi, param1 = param1, param2 = param2, 
            mode = "non-preemptif", label = label))
    }

    df
}

Quelques tests pour voir ce que ça donne :

library(plyr)
library(ggplot2)

df <- genereLifoDF(N = 10000, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = 0.05, 
    loi = "exp", param1 = 1)
df <- rbind(df, genereLifoDF(N = 10000, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = 0.05, 
    loi = "det", param1 = 1))
df <- rbind(df, genereLifoDF(N = 10000, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = 0.05, 
    loi = "unif", param1 = 0, param2 = 2))
df <- rbind(df, genereLifoDF(N = 10000, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = 0.05, 
    loi = "gamma", param1 = 1, param2 = 1))

df_adapted <- ddply(df, c("lambda", "loi"), summarise, Time = mean(R), CI = sd(R)/sqrt(length(R)), 
    nR = length(R))

ggplot(df_adapted, aes(x = lambda, y = Time, ymin = Time - CI, ymax = Time + 
    CI, color = loi)) + geom_line() + geom_pointrange() + ylim(0, max(df_adapted$Time + 
    df_adapted$CI))

plot of chunk unnamed-chunk-2

Passons maintenant à la version préemptible; je construis une fonction simple (facile à débugger) avant de passer à une fonction plus complète. La version complète est commentée, elle sera donc plus lisible (je laisse quand même cette version qui m'a beaucoup servi pour débugger) :


N = 7
A = c(1, 1, 1, 1, 1, 1, 45)
S = array(10, N)

# N = 6 A = c(0,3,1,1,1,1) S = array(2,N)

# N = 5 A = c(0,7,1,7,4) S = c(3,9,3,6,2)

T1 = c()
T2 = c()
R = c()
stack = c()

T1[1] = 0
lastT2 = 0

for (i in 2:N) {
    T1[i] = T1[i - 1] + A[i]
}

i = 1
while (i <= N) {

    if (i < N && T1[i + 1] > (T1[i] + S[i])) {
        T2[i] = max(T2[lastT2], T1[i]) + S[i]
        lastT2 = i
        while (length(stack) != 0) {
            aTraiter = stack[length(stack)]
            m = max(T2[aTraiter + 1], T2[lastT2])
            if (m + S[aTraiter] > T1[i + 1]) {
                S[aTraiter] = S[aTraiter] - (T1[i + 1] - m)
                break
            }
            T2[aTraiter] = max(T2[lastT2], T1[aTraiter]) + S[aTraiter]
            lastT2 = aTraiter
            stack = stack[-length(stack)]
        }
        i = i + 1
    } else {
        if (i < N) {
            S[i] = S[i] - (T1[i + 1] - T1[i])
        }
        stack = c(stack, i)
        i = i + 1
    }
    # }

    while (i > N && length(stack) != 0) {
        aTraiter = stack[length(stack)]
        T2[aTraiter] = max(T2[lastT2], T1[aTraiter]) + S[aTraiter]
        lastT2 = aTraiter
        stack = stack[-length(stack)]
    }
}

Version généralisée :

genereLifoDFPrempt <- function(N, lambdaMin, lambdaMax, lambdaPas, loi, param1 = -1, 
    param2 = -1, mode = "reprise") {

    df = data.frame()

    for (lambda in seq(lambdaMin, lambdaMax, lambdaPas)) {

        A <- rexp(N, lambda)

        if (loi == "exp") {
            S = rexp(N, param1)  # 1
        } else if (loi == "det") {
            S = array(param1, N)  # 1
        } else if (loi == "unif") {
            S = runif(N, param1, param2)  # 0 2
        } else if (loi == "gamma") {
            S = rgamma(N, param1, param2)  # 1 1
        }

        Sinit = S
        T1 = c()
        T2 = c()
        R = c()
        stack = c()

        lastT2 = 0
        T1[1] = 0

        # On calcule les T1 (temps d'arrivées des processus)
        for (i in 2:N) {
            T1[i] = T1[i - 1] + A[i]
        }

        i = 1
        while (i <= N) {
            # On regarde si le processus a le temps de s'executer entierement
            if (i < N && T1[i + 1] > (T1[i] + S[i])) {
                # S'il a le temps (il n'est pas préempté), on calcule son T2
                T2[i] = max(T2[lastT2], T1[i]) + S[i]
                lastT2 = i
                # On regarde parmis les processus déjà empiler si certains peuvent
                # poursuivre leur execution avant l'éventuelle arrivée d'un nouveau
                # processus
                while (length(stack) != 0) {
                  aTraiter = stack[length(stack)]
                  m = max(T2[aTraiter + 1], T2[lastT2])
                  if (m + S[aTraiter] > T1[i + 1]) {
                    # Un processus arrive et prend la main : on met à jour le temps (ou pas) et
                    # on quitte la boucle
                    if (mode == "reprise") {
                      S[aTraiter] = S[aTraiter] - (T1[i + 1] - m)
                    } else if (mode == "reinit") {
                      if (loi == "exp") {
                        S[aTraiter] = rexp(1, param1)
                      } else if (loi == "det") {
                        S[aTraiter] = array(param1, 1)
                      } else if (loi == "unif") {
                        S[aTraiter] = runif(1, param1, param2)
                      } else if (loi == "gamma") {
                        S[aTraiter] = rgamma(1, param1, param2)
                      }
                    }

                    break
                  }
                  # Si personne n'arrive, on calcule T2
                  T2[aTraiter] = max(T2[lastT2], T1[aTraiter]) + S[aTraiter]
                  lastT2 = aTraiter
                  # on dépile
                  stack = stack[-length(stack)]
                }
                i = i + 1
            } else {
                # Si pas le temps (un processus nous préempte)
                if (i < N) {
                  # On met à jour le temps (ou pas) en fonction du temps disponible avant de
                  # se faire préempté

                  if (mode == "reprise") {
                    S[i] = S[i] - (T1[i + 1] - T1[i])
                  } else if (mode == "reinit") {
                    if (loi == "exp") {
                      S[i] = rexp(1, param1)
                    } else if (loi == "det") {
                      S[i] = array(param1, 1)
                    } else if (loi == "unif") {
                      S[i] = runif(1, param1, param2)
                    } else if (loi == "gamma") {
                      S[i] = rgamma(1, param1, param2)
                    }
                  }
                }
                # on empile pour finir ultérieurement
                stack = c(stack, i)

                i = i + 1
            }


            while (i > N && length(stack) != 0) {
                # Si on a parcourut tous les processus, alors on a : - soit déjà calculé le
                # T2 - soit empilé le processus On finit donc ici de calculer les T2 des
                # processus préemptés précédement
                aTraiter = stack[length(stack)]
                T2[aTraiter] = max(T2[lastT2], T1[aTraiter]) + S[aTraiter]

                lastT2 = aTraiter
                stack = stack[-length(stack)]

            }
        }
        # Pris sur votre correction de la file FIFO : création d'un label
        label = as.factor(paste(loi, "(", param1, ",", param2, ")", sep = ""))
        df = rbind(df, data.frame(A = A, Sinit = Sinit, S = S, T1 = T1, T2 = T2, 
            R = T2 - T1, lambda = lambda, loi = loi, param1 = param1, param2 = param2, 
            mode = mode, label = label))
    }

    df
}

df1 <- genereLifoDFPrempt(N = 10000, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = 0.05, 
    loi = "exp", param1 = 1, mode = "reprise")
df1 <- rbind(df1, genereLifoDFPrempt(N = 10000, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = 0.05, loi = "det", param1 = 1, mode = "reprise"))
df1 <- rbind(df1, genereLifoDFPrempt(N = 10000, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = 0.05, loi = "unif", param1 = 0, param2 = 2, mode = "reprise"))
df1 <- rbind(df1, genereLifoDFPrempt(N = 10000, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = 0.05, loi = "gamma", param1 = 1, param2 = 1, mode = "reprise"))

df_adapted1 <- ddply(df1, c("lambda", "loi"), summarise, Time = mean(R), CI = sd(R)/sqrt(length(R)), 
    nR = length(R))

ggplot(df_adapted1, aes(x = lambda, y = Time, ymin = Time - CI, ymax = Time + 
    CI, color = loi)) + geom_line() + geom_pointrange() + ylim(0, max(df_adapted1$Time + 
    df_adapted1$CI))

plot of chunk unnamed-chunk-5

Question 2 : Traçons !

On trace les courbes des files M/M/1 (avec les lois exponentielles) pour les différents modes :

dfQ2 <- genereLifoDF(N = 1000, lambdaMin = 0.2, lambdaMax = 0.8, lambdaPas = 0.2, 
    loi = "exp", param1 = 1)
dfQ2 <- rbind(dfQ2, genereLifoDFPrempt(N = 1000, lambdaMin = 0.2, lambdaMax = 0.8, 
    lambdaPas = 0.2, loi = "exp", param1 = 1, mode = "reprise"))
dfQ2 <- rbind(dfQ2, genereLifoDFPrempt(N = 1000, lambdaMin = 0.2, lambdaMax = 0.8, 
    lambdaPas = 0.2, loi = "exp", param1 = 1, mode = "reboot"))
dfQ2 <- rbind(dfQ2, genereLifoDFPrempt(N = 1000, lambdaMin = 0.2, lambdaMax = 0.8, 
    lambdaPas = 0.2, loi = "exp", param1 = 1, mode = "reinit"))

df_adaptedQ2 <- ddply(dfQ2, c("lambda", "mode"), summarise, Time = mean(R), 
    CI = sd(R)/sqrt(length(R)), nR = length(R))

ggplot(df_adaptedQ2, aes(x = lambda, y = Time, ymin = Time - CI, ymax = Time + 
    CI, color = mode)) + geom_line() + geom_pointrange() + ylim(0, max(df_adaptedQ2$Time + 
    df_adaptedQ2$CI))

plot of chunk unnamed-chunk-6


ggplot(df_adaptedQ2, aes(x = lambda, y = Time, ymin = Time - CI, ymax = Time + 
    CI, color = mode)) + geom_line() + geom_pointrange() + ylim(0, 15)

## Warning: Removed 2 rows containing missing values (geom_path).
## Warning: Removed 2 rows containing missing values (geom_segment).
## Warning: Removed 2 rows containing missing values (geom_point).

plot of chunk unnamed-chunk-6

Analyse :

le mode “reboot” explose bien avant les autres modes. Plutôt normal : dès lors que le processus doit recommencer depuis le début s'il est préempté, le temps de traitement augmente considérablement lorsque les arrivées se rapprochent
le mode “non-préempté” semblent augmenter un peu avant les deux autres. Cela peut s'expliquer par le fait que, lorsque le temps d'inter-arrivées diminue, beaucoup de processus se retrouve sur la pile. Dans les cas avec préemption, ils peuvent “commencer” leurs traitements (et diminuer le temps de service) avant de se faire préempter
les modes “avec reprise” et “réinitialiser” semblent être les meilleurs compromis, même s'ils sont probablement les plus lourds à mettre en place…

Malgré les instructions du sujet sur la variation de lambda, je trouve la courbe suivante plus complète (je la trace donc) :

dfQ2 <- genereLifoDF(N = 1000, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = 0.05, 
    loi = "exp", param1 = 1)
dfQ2 <- rbind(dfQ2, genereLifoDFPrempt(N = 1000, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = 0.05, loi = "exp", param1 = 1, mode = "reprise"))
dfQ2 <- rbind(dfQ2, genereLifoDFPrempt(N = 1000, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = 0.05, loi = "exp", param1 = 1, mode = "reboot"))
dfQ2 <- rbind(dfQ2, genereLifoDFPrempt(N = 1000, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = 0.05, loi = "exp", param1 = 1, mode = "reinit"))

df_adaptedQ2 <- ddply(dfQ2, c("lambda", "mode"), summarise, Time = mean(R), 
    CI = sd(R)/sqrt(length(R)), nR = length(R))

ggplot(df_adaptedQ2, aes(x = lambda, y = Time, ymin = Time - CI, ymax = Time + 
    CI, color = mode)) + geom_line() + geom_pointrange() + ylim(0, max(df_adaptedQ2$Time + 
    df_adaptedQ2$CI))

plot of chunk unnamed-chunk-7

Question 3 :

Comparons maintenant les différentes lois;

A. Mode non-préemptif

nb = 5000
pas = 0.05
dfQ3 <- genereLifoDF(N = nb, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = pas, 
    loi = "exp", param1 = 1)
dfQ3 <- rbind(dfQ3, genereLifoDF(N = nb, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = pas, 
    loi = "det", param1 = 1))
dfQ3 <- rbind(dfQ3, genereLifoDF(N = nb, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = pas, 
    loi = "unif", param1 = 0, param2 = 2))
dfQ3 <- rbind(dfQ3, genereLifoDF(N = nb, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = pas, 
    loi = "gamma", param1 = 1, param2 = 1))
dfQ3 <- rbind(dfQ3, genereLifoDF(N = nb, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = pas, 
    loi = "gamma", param1 = 4, param2 = 0.25))

df_adaptedQ3 <- ddply(dfQ3, c("lambda", "label"), summarise, Time = mean(R), 
    CI = sd(R)/sqrt(length(R)), nR = length(R))

ggplot(df_adaptedQ3, aes(x = lambda, y = Time, ymin = Time - CI, ymax = Time + 
    CI, color = label)) + geom_line() + geom_pointrange() + ylim(0, max(df_adaptedQ3$Time + 
    df_adaptedQ3$CI))

plot of chunk unnamed-chunk-8

On voit pas grand chose… je coupe donc au niveau de l'axe des y :

ggplot(df_adaptedQ3, aes(x = lambda, y = Time, ymin = Time - CI, ymax = Time + 
    CI, color = label)) + geom_line() + geom_pointrange() + ylim(0, 60)

## Warning: Removed 19 rows containing missing values (geom_segment).
## Warning: Removed 19 rows containing missing values (geom_point).

plot of chunk unnamed-chunk-9

Moralité :

soit je met les paramètres (4,0.25) et la courbe explose complètement (valeurs très très largement supérieurs comme ci-dessus)
soit je met les paramètres (0.25,4) et la courbe ne bouge pas (constante égale à 0)

Dans les courbes suivantes, je n'ai laissé qu'une seule valeur de gamma, vu que j'utilise probablement mal la fonction et que la variation que j'essaye d'introduire n'apporte rien d'exploitable…

B. Mode préemptif - avec reprise

dfQ3 <- genereLifoDFPrempt(N = nb, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = pas, 
    loi = "exp", param1 = 1, mode = "reprise")
dfQ3 <- rbind(dfQ3, genereLifoDFPrempt(N = nb, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = pas, loi = "det", param1 = 1, mode = "reprise"))
dfQ3 <- rbind(dfQ3, genereLifoDFPrempt(N = nb, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = pas, loi = "unif", param1 = 0, param2 = 2, mode = "reprise"))
dfQ3 <- rbind(dfQ3, genereLifoDFPrempt(N = nb, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = pas, loi = "gamma", param1 = 1, param2 = 1, mode = "reprise"))

df_adaptedQ3 <- ddply(dfQ3, c("lambda", "label"), summarise, Time = mean(R), 
    CI = sd(R)/sqrt(length(R)), nR = length(R))

ggplot(df_adaptedQ3, aes(x = lambda, y = Time, ymin = Time - CI, ymax = Time + 
    CI, color = label)) + geom_line() + geom_pointrange() + ylim(0, max(df_adaptedQ3$Time + 
    df_adaptedQ3$CI))

plot of chunk unnamed-chunk-10

C. Mode préemptif - avec redémarrage du service

dfQ3 <- genereLifoDFPrempt(N = nb, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = pas, 
    loi = "exp", param1 = 1, mode = "reboot")
dfQ3 <- rbind(dfQ3, genereLifoDFPrempt(N = nb, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = pas, loi = "det", param1 = 1, mode = "reboot"))
dfQ3 <- rbind(dfQ3, genereLifoDFPrempt(N = nb, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = pas, loi = "unif", param1 = 0, param2 = 2, mode = "reboot"))
dfQ3 <- rbind(dfQ3, genereLifoDFPrempt(N = nb, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = pas, loi = "gamma", param1 = 1, param2 = 1, mode = "reboot"))

df_adaptedQ3 <- ddply(dfQ3, c("lambda", "label"), summarise, Time = mean(R), 
    CI = sd(R)/sqrt(length(R)), nR = length(R))

ggplot(df_adaptedQ3, aes(x = lambda, y = Time, ymin = Time - CI, ymax = Time + 
    CI, color = label)) + geom_line() + geom_pointrange() + ylim(0, max(df_adaptedQ3$Time + 
    df_adaptedQ3$CI))

plot of chunk unnamed-chunk-11

D. Mode préemptif - avec nouveau temps de service

dfQ3 <- genereLifoDFPrempt(N = nb, lambdaMin = 0.1, lambdaMax = 1, lambdaPas = pas, 
    loi = "exp", param1 = 1, mode = "reinit")
dfQ3 <- rbind(dfQ3, genereLifoDFPrempt(N = nb, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = pas, loi = "det", param1 = 1, mode = "reinit"))
dfQ3 <- rbind(dfQ3, genereLifoDFPrempt(N = nb, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = pas, loi = "unif", param1 = 0, param2 = 2, mode = "reinit"))
dfQ3 <- rbind(dfQ3, genereLifoDFPrempt(N = nb, lambdaMin = 0.1, lambdaMax = 1, 
    lambdaPas = pas, loi = "gamma", param1 = 1, param2 = 1, mode = "reinit"))

df_adaptedQ3 <- ddply(dfQ3, c("lambda", "label"), summarise, Time = mean(R), 
    CI = sd(R)/sqrt(length(R)), nR = length(R))

ggplot(df_adaptedQ3, aes(x = lambda, y = Time, ymin = Time - CI, ymax = Time + 
    CI, color = label)) + geom_line() + geom_pointrange() + ylim(0, max(df_adaptedQ3$Time + 
    df_adaptedQ3$CI))

plot of chunk unnamed-chunk-12

Question 4 : Conclusion

D'après les courbes de la question précédente, on peut conclure que :

comme pour la file FIFO, le type de loi ne semble avoir qu'une influence limitée. On remarque bien que certaines lois semblent meilleures sur la fin, mais globalement les courbes sont plutôt sérées (par ailleurs, les dernières valeurs ne sont pas très pertinentes –> indice de confiance)
d'un autre côté, le mode (préemptible ou pas) influe réellement sur les performances de la file. On notera par exemple le mode préemptible avec redémarrage est particulierement lent. Reste à voir si, lors de l'implémentation concrète de l'une de ces files, tous les modes sont disponibles s'il y a des contraintes (temps réel ?)
enfin, la valeur de la variance semble avoir une importance réelle, à l'instar de la file FIFO. Même si je n'ai pas pu simuler correctement cette variation, j'ai bien vu que le changement de variance avait un impact important (peut-être même un peu trop, fausse manip de ma part ?)