Le code fourni dans ce document provient majoritairement de mon propre travail ainsi que de certains exemples de cours fournis sur ce site. En ayant repris ce code, je l’ai modifié pour l’adapter au sujet et modéliser une politique de cache différente.

Initialisation :

set.seed(1337)
# Nombre d'objets differents
N = 100
# Probabilité d'accès à l'objet A d'indice 1
a = 0.1
# Probabilité d'accès aux autres objets
b = (1-a)/(N-1)
# Taille du cache
K = 20
# Nombre d'accès
T = 1000

# Génération d'une séquence d'accès
access = sample(x= 1:N,size = T,prob =c(a,rep(b,N-1)),replace = TRUE )

# Génération d'une séquence d'accès pour remplir les cache ayant differentes politiques de la même manière
remplissage =  sample(c(1:N),T,prob =c(a,rep(b,N-1)),replace = TRUE )

Fonction simulant le cache avec la politique Move-Ahead:

move_ahead<-function(){
  miss=c()
  eviction=c()
  posA=c()

  cache_ma = remplissage[1]
  remplissage = remplissage[-1]

  # boucle de remplissage du cache
  for(obj in remplissage){
    if(obj %in% cache_ma)
    {
      pos = match(obj,cache_ma)
      
      # on permute deux objet dans le cache pour décaler vers la gauche celui qui vient d'arriver
      if(pos!=1)
      {
        cache_ma=replace(cache_ma, c(pos-1, pos), cache_ma[c(pos, pos-1)])
      }
    }
    else 
    {
      # ajout du nouvel objet
      cache_ma=c(obj,cache_ma)
    }
    if(length(cache_ma)>=K)
    {
      break
    }
  }


  # boucle principale
  for(obj in access){
    if(obj %in% cache_ma)
    {
      # la fonction match est utilisable car l'objet n'est pas répété (s'arrête au premier rencontré)
      pos = match(obj,cache_ma)
      
      # on permute deux objet dans le cache pour décaler vers la gauche celui qui vient d'arriver
      if(pos!=1)
      {
        cache_ma=replace(cache_ma, c(pos-1, pos), cache_ma[c(pos, pos-1)])
      }
      miss = c(miss,0)
      eviction = c(eviction,0)
    }
    else 
    {
      miss=c(miss,1)
      if(cache_ma[K]==1)
      {
        eviction = c(eviction,1)
      }
      else
      {
        eviction = c(eviction,0)
      }
      
      # éviction de l'objet le plus a droite pour placer le nouvel objet
      cache_ma=c(cache_ma[-K],obj)
    }
    # Permet de calculer la position de A (provient entièrement du site de du cours)
    if(1 %in% cache_ma) {
        posA  = c(posA,((1:K)[!is.na(cache_ma) & cache_ma==1]))
    } else {
        posA  = c(posA,NA)
    }
  }
  
  err=sd(miss)/sqrt(length(miss))
  err=sd(eviction)/sqrt(length(eviction))

  L<-list("cache"=cache_ma, "miss"=miss, "eviction"=  eviction, "position"=posA)
  return(L)
}

Fonction simulant le cache avec la politique LRU, celui ci a été modifié pour être rempli de la même manière que le cache Move-Ahead

lru<-function(){

  miss=c()
  eviction=c()
  posA=c()
  
  cache_lru = remplissage[1]
  remplissage = remplissage[-1]
  
  for (obj in access){
    if(obj %in% cache_lru)
    {
      pos = (1:N)[cache_lru==obj]
      cache_lru = c(obj,cache_lru[-pos])
      
    }
    else 
    {
      cache_lru = c(obj,cache_lru)
    }
    if(length(cache_lru)>=K)
    {
      break
    }
  }
  
  for (obj in access){
    if(obj %in% cache_lru)
    {
      pos = (1:N)[cache_lru==obj]
      cache_lru = c(obj,cache_lru[-pos])
      miss=c(miss,0)
      eviction=c(eviction,0)
    }
    else 
    {
      if(cache_lru[K]==1)
      {
        eviction=c(eviction,1)
      }
      else
      {
        eviction=c(eviction,0)
      }
      cache_lru = c(obj,cache_lru[-K])
      miss=c(miss,1)
    }
    if(1 %in% cache_lru) {
      posA  = c(posA,((1:K)[!is.na(cache_lru) & cache_lru==1]));
    } else {
      posA  = c(posA,NA);
    }
  }
  
  err=sd(miss)/sqrt(length(miss))
  err=sd(eviction)/sqrt(length(eviction))
  
  L<-list("cache"=cache_lru, "miss"=miss, "eviction"=  eviction, "position" = posA)
  return(L)
}

Fonction qui calcule le l’interval de confiance des probabilité de défaut de cache et d’éviction de A

int_confiance <- function(liste){
  # le fait de mettre en liste les resultats nécéssite de les retransformer en vecteur
  mi=unlist(liste[2],FALSE,FALSE)
  ev=unlist(liste[3],FALSE,FALSE)
  
  err=sd(mi)/sqrt(length(mi))
  err=sd(ev)/sqrt(length(ev))
  list("Miss"=c(mean(mi)-2*err,mean(mi)+2*err),"Eviction"=c(mean(ev)-2*err,mean(ev)+2*err))
}

Première observation des probabilité d’éviction et de défaut de cache :

lr=lru()
ma=move_ahead()

int_confiance(lr)
## $Miss
## [1] 0.7264 0.7396
## 
## $Eviction
## [1] 0.004400033 0.017599967
int_confiance(ma)
## $Miss
## [1] 0.734 0.734
## 
## $Eviction
## [1] 0 0

On remarquera (sauf erreur de modélisation) que la politique move_ahead a une probabilité de défaut de cache plus élevé mais empêche l’éviction de A.

On observe les défauts de cache ainsi que la position de a

plot(unlist(lr[2],FALSE,FALSE),xlab = "Sequence",ylab = "Miss",main = "LRU" )

plot(unlist(ma[2],FALSE,FALSE),xlab = "Sequence",ylab = "Miss",main = "Move Ahead" )

plot(unlist(lr[4],FALSE,FALSE),xlab = "Sequence",ylab = "posA",main = "LRU" )

plot(unlist(ma[4],FALSE,FALSE),xlab = "Sequence",ylab = "posA",main = "Move Ahead") # problème de calcul de la position