DM1

Simulation de la file LIFO

library(plyr)
library(ggplot2)

set.seed(10)
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)
         )
}

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
}

Question 1:Illustrer les différences de natures entre les différentes lois de temps de service.

–> Pour cette premiere question nous allons tracer les differents temps de services sur un méme graphe en faisant varier la durés N pour pouvoir voir l’aspect global de la courbe, et avoir un graphe lisible. Dans un second temps nous tracerons les courbes précedente sur des

id=1:40
df = data.frame(service1=Service(40,typeservice = "det",id,id),service2=Service(40,typeservice = "uni",id,id),service3=Service(40,typeservice = "gamma",id,id),service4=Service(40,typeservice = "exp",id,id))
 head(df)

##   service1 service2   service3   service4
## 1        1        1  0.5133434 3.50824146
## 2        1        2  2.5656498 0.58453321
## 3        1        3  4.3499954 0.44117381
## 4        1        4 16.2909307 0.15400088
## 5        1        5 26.8243174 0.19765043
## 6        1        6 18.1900335 0.09472218

id=1:40
id

##  [1]  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
## [24] 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

ggplot(data=df)+ geom_point(aes(x=id,y=service1)) + geom_point(aes(x=id,y=service2),color="red") +geom_point(aes(x=id,y=service4),color="blue")+geom_point(aes(x=id,y=service3),color="green")

Nous remarquons quand nous traceons toutes les courbes si l’on garde cette échelle que le temps d’éxecution pour le service 3 est exponentielle( le service 3 correspond au service Gamma). dun autre coté nous pouvons voir que les temps de service pour les service 1 et 4 restent proche de 0. pour le dernier service qui correspond au service un, il augmente a trés petie echelle. Nous allons à présent changer d’echelle pour nous concentres sur les courbes ayant de petites valeurs. pour ce faire nous supprimons dans notre plot la courbe du service 3.

id=1:40
df = data.frame(service1=Service(40,typeservice = "det",id,id),service2=Service(40,typeservice = "uni",id,id),service3=Service(40,typeservice = "gamma",id,id),service4=Service(40,typeservice = "exp",id,id))
 head(df)

##   service1 service2   service3  service4
## 1        1        1  0.3570422 0.6633441
## 2        1        2  5.0120648 0.1030006
## 3        1        3  9.7336102 0.4497184
## 4        1        4 15.2138067 0.9831957
## 5        1        5 30.0419663 0.2509613
## 6        1        6 71.6415426 0.2683332

id=1:40
id

##  [1]  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
## [24] 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

ggplot(data=df)+ geom_point(aes(x=id,y=service1)) + geom_point(aes(x=id,y=service2),color="red") +geom_point(aes(x=id,y=service4),color="blue")

à présent nous voyons beaucoup mieux à quoi correspond la courbe du service uni; nous voyons que cest un service dont le temps d’execution évolue de maniere lineaire. Concernant les autres graphes, nous ne voyons pas encore trés bien l’allure de ces courbes. nous décidons donc de les tracer séparement.

ggplot(data=df)+ geom_step(aes(x=id,y=service1)) +ggtitle("temps d'execution du procéssus pour le service 1 = det")

ggplot(data=df)+ geom_step(aes(x=id,y=service2),color="red")+ggtitle("temps d'execution du procéssus pour le service 2= uni")

ggplot(data=df)+ geom_step(aes(x=id,y=service3),color="green")+ggtitle("temps d'execution du procéssus pour le service 3= gamma")

ggplot(data=df)+ geom_step(aes(x=id,y=service4),color="blue")+ggtitle("temps d'execution du procéssus pour le service 4= exp")

Pour le Service 4 ( le service exponentiel, ce que nous pouvons dire c’ est qu il tend vers 0,sa plus haute valeur est 1, nous pouvons dire que plus l’ on va avancer dans le temps plus son temps d’ execution sera court) Pour le Service 1( qui correspond au service det, celui- ci n’évolue pas, il reste a une valeur constant =1; il y a donc tout le temps le méme temps d’execution.)

Question 2

Pour cette partie je me suis inspiré du code qui à été éffectué en TD 2013. Il y a problem de compilation pour ce sous-partie, donc on le presente directement ici.

**** commence de sous-partie avec problem de compilation**** Service <- function(n = 1, typeservice, x, y) { switch(typeservice, det = seq(from = 1, to = 1, length.out = n), uni = runif(n, x, y), gamma = rgamma(n, shape = x, scale = y), exp = rexp(n, x)) }

create <- function(n, lambda_min, lambda_max, step, typeservice, x, y) { d <- data.frame() for (lambda in seq(lambda_min, lambda_max, step)) { Lifo=FileLIFO(n, lambda, typeservice=“exp”, x, y, “npmt”)

    d = rbind(d, data.frame(n = n, lambda = lambda, response = mean(traj$response), 
        sd = sd(traj$response), sys_vide = traj$sys_vide, sd_S = traj$sd_S))
}
d$input_type = typeservice
d$input_p1 = x
d$input_p2 = y
d$label = as.factor(paste(typeservice, "(", x, ",", y, ")", sep = ""))
d
}

experiment <- function(sample_size = 10000) { resp_exp <- create(sample_size, 0.01, 0.99, 0.02, “exp”, 1, 0) resp_det <- create(sample_size, 0.01, 0.99, 0.02, “det”, 0, 0) resp_u02 <- create(sample_size, 0.01, 0.99, 0.02, “uni”, 0, 2) resp_gamma4 <- create(sample_size, 0.01, 0.99, 0.02, “gamma”, 4, 1/4) rbind(resp_exp, resp_det, resp_u02, resp_gamma4) } df <- experiment() head(df)

ggplot(df, aes(x = df$lambda, y = df$response, color = df$label, shape = df$label)) + geom_line() + geom_point() + geom_errorbar(width = 0.02, aes(x = df$lambda, y = df$response, ymin = df$response - 2 * df$sd/sqrt(df$n), ymax = df$response + 2 * df$sd/sqrt(df$n))) + geom_vline(xintercept = 1) + geom_hline(yintercept = 1) + theme_bw()

****fin de sous-partie avec problem de compilation****

Nous commencons par étudier les résultats avec la politique: “Pmtn”pour une valeur de landa de 0,2

id=1:10
df = data.frame(service1=FileLIFO(n = 10,lambda = 0.2,typeservice = 1,x = id,y=id,policy = 1),service2=FileLIFO(n = 10,lambda = 0.2,typeservice = 2,x = id,y=id,policy = 1),service3=FileLIFO(n = 10,lambda = 0.2,typeservice = 3,x = id,y=id,policy = 1),service4=FileLIFO(n = 10,lambda = 0.2,typeservice = 4,x = id,y=id,policy = 1))


ggplot(data=df)+ geom_point(aes(x=id,y=service1)) + geom_point(aes(x=id,y=service3),color="red") +geom_point(aes(x=id,y=service2),color="green")+geom_point(aes(x=id,y=service4),color="blue")

nous commencons par étudier les résultats avec la politique: “Pmtn”pour une valeur de landa de 0,4

id=1:10
df = data.frame(service1=FileLIFO(n = 10,lambda = 0.4,typeservice = 1,x = id,y=id,policy = 1),service2=FileLIFO(n = 10,lambda = 0.4,typeservice = 2,x = id,y=id,policy = 1),service3=FileLIFO(n = 10,lambda = 0.4,typeservice = 3,x = id,y=id,policy = 1),service4=FileLIFO(n = 10,lambda = 0.4,typeservice = 4,x = id,y=id,policy = 1))


ggplot(data=df)+ geom_point(aes(x=id,y=service1)) + geom_point(aes(x=id,y=service3),color="red") +geom_point(aes(x=id,y=service2),color="green")+geom_point(aes(x=id,y=service4),color="blue")

nous commencons par étudier les résultats avec la politique: “Pmtn”pour une valeur de landa de 0,6

id=1:10
df = data.frame(service1=FileLIFO(n = 10,lambda = 0.6,typeservice = 1,x = id,y=id,policy = 1),service2=FileLIFO(n = 10,lambda = 0.6,typeservice = 2,x = id,y=id,policy = 1),service3=FileLIFO(n = 10,lambda = 0.6,typeservice = 3,x = id,y=id,policy = 1),service4=FileLIFO(n = 10,lambda = 0.6,typeservice = 4,x = id,y=id,policy = 1))


ggplot(data=df)+ geom_point(aes(x=id,y=service1)) + geom_point(aes(x=id,y=service3),color="red") +geom_point(aes(x=id,y=service2),color="green")+geom_point(aes(x=id,y=service4),color="blue")

nous commencons par étudier les résultats avec la politique: “Pmtn”pour une valeur de landa de 0,8

id=1:10
df = data.frame(service1=FileLIFO(n = 10,lambda = 0.8,typeservice = 1,x = id,y=id,policy = 1),service2=FileLIFO(n = 10,lambda = 0.8,typeservice = 2,x = id,y=id,policy = 1),service3=FileLIFO(n = 10,lambda = 0.8,typeservice = 3,x = id,y=id,policy = 1),service4=FileLIFO(n = 10,lambda = 0.8,typeservice = 4,x = id,y=id,policy = 1))


ggplot(data=df)+ geom_point(aes(x=id,y=service1)) + geom_point(aes(x=id,y=service3),color="red") +geom_point(aes(x=id,y=service2),color="green")+geom_point(aes(x=id,y=service4),color="blue")

Nous remarquons avec ces courpes précédentes que plus lambda augmente plus nos courbes sont cohérantes et arrivent vers un point de convergence, nous remarquons de plus que nos courbes n’ont pas les mémes formes, à l’exception des courbes rouge, et bleu,la courbe rouge correspond à la courbe gama

ggplot(data=df) + geom_step(aes(x=id,y=service2))+geom_step(aes(x=id,y=service3),color="red")+geom_step(aes(x=id,y=service4),color="green")+geom_step(aes(x=id,y=service1),color="blue")

II nous rééfectuons les mémes manipulations avec la méthode préemptif le client en cours de service est interrompu pour permettre le service du client qui vient d’arriver.

III nous rééfectuons les mémes manipulations avec la méthode reprise un client interrompu reprend son service là où il avait été interrompu ;

IV nous rééfectuons les mémes manipulations avec la méthode redémarrage du même service ;

V nous rééfectuons les mémes manipulations avec la méthode réinitialise : nouveau temps de service.