Structure des systèmes de fichiers

L'auteur de cette page est : Jean-Baptiste Yunes

Le buffer cache

Il fonctionne à l'aide de deux fonctions principales :

getblk(): qui attribue à un numéro de bloc un cache pouvant le contenir.
brelse(): qui libère un cache dont on a plus l'utilité imméditate.

Un cache peut être :

vérrouillé: ce qui signifie qu'il est en cours d'utilisation (par le système ou par un autre processus), cette propriété est à opposée à l'appartenance à la liste des caches libres.
sale (par opposition à propre): signifie que le contenu du cache (c'est-à-dire ses données) a été modifié lors d'une écriture. Cette écriture est différée jusqu'à une certaine limite : cache non récemment utilisé qui devient donc prioritaire pour l'allocation par LRU (Least Recently Used).
libre: signifie qu'il est à priori disponible pour une utilisation. Il appartient donc à la liste des caches libres dans laquelle on recherche un cache lorsqu'on ne trouve pas celui dont on a besoin par ailleurs.
vieux: signifie qu'un cache n'a pas été récemment utilisé (relativement aux autres).
valide (par opposition à invalide): signifie que le cache contient (ou non) les données du bloc en question. Si ce n'est pas le cas il faudra les lire sur le disque.

getblk()

Cette fonction distingue différents cas :

il existe déjà un cache contenant le bloc recherché mais ce cache est en cours d'utilisation, alors le demandeur est mis en sommeil en attente de la libération du cache. Lorsqu'il sera réveillé il recommencera la compétition depuis le départ.
il existe déjà un cache contenant le bloc recherché et ce cache est libre d'utilisation, alors le demandeur le vérouiile, l'enlève de la liste des caches libres en le renvoie.
il n'existe pas de cache contenant le bloc recherché et tous sont en cours d'utilisation, alors le demandeur est mis en sommeil attendant qu'un cache quelconque se libère. Lorsqu'il sera réveillé il recommencera la compétition depuis le départ.
il n'existe pas de cache contenant le bloc recherché et il en existe un de libre mais celui-ci est sale, alors le demandeur se contente de le supprimer de la liste des caches libres, de le vérrouiller et de réclamer sa recopie (asynchrone) sur le disque puis recommence la compétition.
il n'existe pas de cache contenant le bloc recherché, il en existe un de libre et propre, alors le demandeur le marque comme invalide, le vérouille, le supprime de la liste des caches libres, le replace dans la bonne liste puis le renvoie.

Cache *getblk(BlockNum_t block_num) {
  int not_found = TRUE;
  Cache *cache;

  while (not_found) {
    if ( (cache=isincore(block_num))!=NULL ) {
      if ( islocked(cache) ) {
        sleep(WAITING(cache));
        continue;
      }
      lock(cache);
      remove(cache,freelist);
      not_found = FALSE;
    } else {
      if ( (cache=getfree())==NULL ) {
        sleep(WAITING(FREE_CACHE));
        continue;
      }
      lock(cache);
      remove(cache,freelist);
      if ( isdirty(cache) ) {
        async_write(cache);
        continue;
      }
      invalid(cache);
      list = getlist(cache->block_num);
      remove(cache,list);
      cache->block_num = block_num;
      list = getlist(cache->block_num);
      insert_head(cache,list);
      not_found = FALSE;
    }
  }
  return cache;
}

brelse()

Cette fonction a pour but principal de libérer un cache. Puisqu'un cache va être libéré il est nécessaire de réveiller ceux qui attendent la libération de ce cache en particulier ou d'un cache quelconque. Si le cache était un vieux cache (écriture différée par exemple il a bien été récemment utilisé par le système pour effectuer la recopie sur le disque mais il n'a pas été récemment utilisé par un processus) alors il est ajouté en début de la liste des caches libres, sinon en fin de liste. Pour terminer il est dévérouillé.

void brelse(Cache *cache) {
  wake(WAITING(FREE_CACHE));
  wake(WAITING(cache));
  if ( isold(cache) ) {
    insert_head(cache,freelist);
  } else {
    insert_tail(cache,free_list);
  }
  unlock(cache);
}

Lecture/Écriture d'un bloc

Il existe pour effectuer de telles opérations les fonctions suivantes :

bread(): qui renvoie un cache contenant le bloc recherché en effectuant une éventuelle lecture sur le disque si c'est nécessaire.
breada(): qui réalise la même opération que bread() tout en provoquant la lecture anticipée d'un deuxième bloc dans le cache.
bwrite(): qui effectue une écriture du bloc contenu dans le cache.
bawrite(): qui marque un cache pour écriture aynchrone et appelle bwrite().
bdwrite(): qui marque un cache comme sale.

bread()

Cette fonction renvoie un cache contenant les données d'un bloc désiré. Elle fait d'abord appel à getblk(), puis vérifie que le cache est valide et si c'est bien le cas renvoie immédiatement le cache. Lorsque les données ne sont pas valides, une lecture asynchrone est initiée et le demandeur mis en sommeil en attente de la terminaison de la lecture. Lorsqu'il est enfin réveillé, le cache est validé puis renvoyé.

Cache *bread(BlockNum_t block_num) {
  Cache *cache;

  cache = getblk(block_num);
  if ( isvalid(cache) )
    return cache;
  async_read(cache);
  sleep(READING(cache));
  valid(cache);
  return cache;
}

Lecture/Écriture sur fichier

Il existe deux fonctions :

read(): qui lit un certain nombre d'octets dans un fichier en effectuant les lectures de blocs nécessaires.
write(): qui écrit un certain nombre d'octets dans un fichier.

read()

int read(int descriptor,void *buffer,unsigned int length) {
  OpenFile *of;
  InCoreInode *ii;
  BlockNum_t lblock, pblock;
  unsigned int l, total, offset;

  of = getopenfile(descriptor);
  if ( ! forreading(of) ) {
    errno = EBADF;
    return -1;
  }
  ii = getincoreinode(of);
  total = 0;
  lock(of);
  offset = of->offset;
  lock(ii);
  while (length) {
    if (offset>=ii->size) break;
    lblock = lblocknum(offset);
    pblock = pblocknum(lblock,ii);
    block_off = offset%BLOCK_SIZE;
    cache = bread(pblock);
    l = copy(buffer,cache,block_off,MIN(length,BLOCK_SIZE));
    brelse(cache);
    offset += l;
    buffer += l;
    total += l;
  }
  unlock(ii);
  of->offset = offset;
  unlock(of);
  return total;
}

Fragmentation