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