Le buffer est un espace mémoire dans la mémoire centrale (généralement, la RAM) qui est utilisé pour stocker temporairement les pages chargées à partir des fichiers qui constituent la base de données. Il est très similaire, dans son principe, au principe de pagination et de la mémoire virtuelle utilisées par les Systèmes d'Exploitation.
Il est utilisé parce que la taille de la base de données dépace largement l'espace disponible dans la mémoire centrale pour effectuer les différents traitements.
Néanmoins, le problème est beaucoup plus simple vu que la pagination concerne seulement des données et non pas un mélange de données et de traitements (les processus) tel qu'il est le cas avec les Systèmes d'Exploiatation. Pour cela, les algorithmes largement utilisés sont seulement deux : FIFO et LRU.
Les deux algorithme visent à choisir la page à remplacer lorsqu'on veut accéder à une nouvelle page et le buffer est plein (ne contient pas d'emplacements vides).
L'algorithme FIFO consiste à remplacer la page la plus ancienne. Il est intuitive et simple : lorsqu'une nouvelle page arrive, on remplace la page qui a passé le plus du temps dans la mémoire. Il est simple à implémenter : il suffit d'utiliser une structure de file simple. Néanmoins, il n'est pas adapté à un contexte de données. En effet, des données telles que les comptes des utilisateurs et leurs privilèges et droits d'accès sont chargées dès le lancement du système et doivent rester toujours disponibles.
L'algorithme LRU est notre deuxième algorithme et l'algorithme le plus utilisé dans le contexte des données. Il se base sur l'affirmation qui dit que : "Si on accède à une donnée à un instant t, il est très probable qu'on aura besoin d'accéder à la même donnée à un moment proche t + dt". Par exemple, il est possible de lire des informations d'un client pour lui vérifier son état financier pour ensuite lui accorder un nouveau crédit et qu'on aura besoin à nouveau de ses informations pour imprimer les états de sortie.
Pour implémenter ces deux algorithmes, plusieurs approches peuvent être suivies. Dans cet article, nous nous intéressons à une approche très simple qui n'utilise pas la structure de file mais sur un simple compteur associé à un tableau d'indices pour pouvoir connaître la page la plus ancienne dans le cas de l'algorithme FIFO ou bien la page la moins récemment utilisée dans le cas de l'algorithme LRU.
Entre les deux approches, quelques lignes de codes changent seulement. En effet, la différence réside dans la mise à jour de l'indice d'une page :
Il est utilisé parce que la taille de la base de données dépace largement l'espace disponible dans la mémoire centrale pour effectuer les différents traitements.
Néanmoins, le problème est beaucoup plus simple vu que la pagination concerne seulement des données et non pas un mélange de données et de traitements (les processus) tel qu'il est le cas avec les Systèmes d'Exploiatation. Pour cela, les algorithmes largement utilisés sont seulement deux : FIFO et LRU.
Les deux algorithme visent à choisir la page à remplacer lorsqu'on veut accéder à une nouvelle page et le buffer est plein (ne contient pas d'emplacements vides).
L'algorithme FIFO consiste à remplacer la page la plus ancienne. Il est intuitive et simple : lorsqu'une nouvelle page arrive, on remplace la page qui a passé le plus du temps dans la mémoire. Il est simple à implémenter : il suffit d'utiliser une structure de file simple. Néanmoins, il n'est pas adapté à un contexte de données. En effet, des données telles que les comptes des utilisateurs et leurs privilèges et droits d'accès sont chargées dès le lancement du système et doivent rester toujours disponibles.
L'algorithme LRU est notre deuxième algorithme et l'algorithme le plus utilisé dans le contexte des données. Il se base sur l'affirmation qui dit que : "Si on accède à une donnée à un instant t, il est très probable qu'on aura besoin d'accéder à la même donnée à un moment proche t + dt". Par exemple, il est possible de lire des informations d'un client pour lui vérifier son état financier pour ensuite lui accorder un nouveau crédit et qu'on aura besoin à nouveau de ses informations pour imprimer les états de sortie.
Pour implémenter ces deux algorithmes, plusieurs approches peuvent être suivies. Dans cet article, nous nous intéressons à une approche très simple qui n'utilise pas la structure de file mais sur un simple compteur associé à un tableau d'indices pour pouvoir connaître la page la plus ancienne dans le cas de l'algorithme FIFO ou bien la page la moins récemment utilisée dans le cas de l'algorithme LRU.
Entre les deux approches, quelques lignes de codes changent seulement. En effet, la différence réside dans la mise à jour de l'indice d'une page :
- Dans le cas de l'algorithme FIFO : l'indice prend sa valeur au moment de chargement de la page et ne change pas. Le compteur n'est incrémenté que dans le cas d'un défaut de page. La page avec l'indice le plus petit est la page la plus ancienne.
public void chargerPage(int numero) { // Recherche si la page est déjà chargée int i = 0; boolean trouve = false; while (i < pagesOccupees && !trouve) { if (pages[i] == numero) { trouve = true; } else { i++; } } if (trouve) { // On ne fait rien } else { // Voir est ce qu'il y a des places vides if (pagesOccupees < TAILLE_MEMOIRE) { pages[pagesOccupees] = numero; indices[pagesOccupees] = compteur; pagesOccupees++; } else { // Si le buffer est déja rempli // Recherche de l'indice minimale int valeurMin = indices[0]; int positionMin = 0; for (int j = 0; j < indices.length; j++) { if(indices[j] < valeurMin){ positionMin = j; valeurMin = indices[j]; } } // On la remplace pages[positionMin] = numero; indices[positionMin] = compteur; } defautsDePage++; compteur++; } }
- Dans le cas de l'algorithme LRU : le compteur doit garder trace de l'utilisation de la page et non pas du moment de son chargement ainsi le compteur est incrémenté à chaque opération d'accès même s'il ne s'agit pas d'un défaut de page et dans ce cas l'indice de la page est mis à jour même si la page est déjà dans le buffer. La page avec l'indice le plus petit est la page la moins récemment utilisée.
public void chargerPage(int numero) { // Recherche si la page est déjà chargée int i = 0; boolean trouve = false; while (i < pagesOccupees && !trouve) { if (pages[i] == numero) { trouve = true; } else { i++; } } if (trouve) { // L'unique différence entre FIFO et LRU // L'indice de la page est mis à jour et le compteur est incrémenté même si la page est déjà en mémoire. indices[i] = compteur; compteur++; } else { // Voir est ce qu'il y a des places vides if (pagesOccupees < TAILLE_MEMOIRE) { pages[pagesOccupees] = numero; indices[pagesOccupees] = compteur; pagesOccupees++; } else { // Si le buffer est déja rempli // Recherche de l'indice minimale int valeurMin = indices[0]; int positionMin = 0; for (int j = 0; j < indices.length; j++) { if(indices[j] < valeurMin){ positionMin = j; valeurMin = indices[j]; } } // On la remplace pages[positionMin] = numero; indices[positionMin] = compteur; } defautsDePage++; compteur++; } }
Le code complet peut être téléchargé par ici
Le dossier contient un projet NetBeans ouvrable, sinon, vous avez toujours la possibilité de construire un nouveau projet dans les autres éditeurs en utilisant le dossier "src".
Il est possible d'exécuter le jar directement, sans recompilation, il suffit d'utiliser la commande :
java -jar ABD05.jar
Si vous pensez que l'affichage est un peu rapide, vous pouvez mettre la sortie dans un fichier texte si vous exécutez la commande suivante :
java -jar ABD05.jar >> test.txt
Le dossier ./dist/javadoc contient la documentation générée si vous voulez voir les différentes structures utilisées.
Le code contient un bug : les valeurs initiales sont des "0" à ne pas confondre avec la page numéro "0".
