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

Pas de différence notable constatée pour les défault de cache. Cependant, on observe que la politique Move-Ahead fait tendre A vers la position 1. Ceci explique l’absence d’éviction de A pour le Move-Ahead contrairement au LRU ou A ne pouvait conserver la 1ère position que s’il etait accédé 2 fois d’affilée.

Chaine de Markov :

# Création de la chaine de Markov (Reprise du code du site en adaptant a la politique du cache)
options(width=160)
M=matrix(rep(0,(K+1)*(K+1)),nrow=K+1)

M[1,1]=1-b
M[1,2]=b

for(i in 2:K) {
    M[i,i-1]= a
    M[i,i] = 1-a-b
    M[i,i+1] = b
}
M[K+1,K]=a
M[K+1,K+1]=1-a

Nous nous intéressons au valeurs propres de la transposée de la matrice M En reprenant l

options(digits=3) 
E=head(eigen(t(M)))
head(E$values) 
## [1] 1.000 0.951 0.949 0.945 0.941 0.935
ssp=E$vectors[,1];
ssp = Re(ssp/(sum(ssp)))
options(digits=5);
sum(ssp[1:K])
## [1] 1

Comparaison des politiques en fonction de la taille de cache

# n correspond a l'indice de la valeur dont ont souhaite obtenir l'esperance
# l correspond a la liste renvoyée par les fonction de modélisation des politique de cache
moyenne=function(n,l)
{ f=unlist(l[n],FALSE,FALSE)
  return(mean(f))}

On compare ensuite les probabilité d’Eviction (violet pour LRU et turquoise pour Move-Ahead) et de défaut de cache (rouge pour LRU et Bleu pour M-A).

test = (1: ( 0.8*K ) )*5
p_miss_lru=c()
p_eviction_lru=c()

p_miss_ma=c()
p_eviction_ma=c()

for(o in test){
  K=o
  lr=lru()
  ma=move_ahead()

  p_miss_lru=c(p_miss_lru,moyenne(2,lr))
  p_eviction_lru=c(p_eviction_lru,moyenne(3,lr))
  
  p_miss_ma=c(p_miss_ma,moyenne(2,ma))
  p_eviction_ma=c(p_eviction_ma,moyenne(3,ma))
}

plot(x=test,xlim=c(1,N),ylim=c(0,1), type="n", xlab="Taille du cache", ylab="Probabilité" ) 

lines(x=test, y=p_miss_lru, type="b", lwd=1.5,lty=1, col="red", pch="*") 
lines(x=test, y=p_miss_ma, type="b", lwd=1.5,lty=1, col="blue", pch="*") 
lines(x=test, y=p_eviction_lru, type="b", lwd=1.5,lty=1, col="violet", pch="*") 
lines(x=test, y=p_eviction_ma, type="b", lwd=1.5,lty=1, col="turquoise", pch="*") 

title("LRU vs Move-Ahead : Eviction and Cache Default")

Les résultats constatés indiquent sont mitigés :
- D’une part le LRU semble meilleur que le Move-Ahead pour des tailles de cache plus importantes (supérieurs à 25) (probabilité de default de cache plus faible) - D’une autre, le Move-ahead semble être plus adapté a de petites taille de cache (inférieures à 20) nottament grâce a sont taux d’éviction nul meme pour des tailles extrêmement réduites ainsi que grâce sa probabilité de défaut de cache inférieure.