Brevet FR2613505A1 — publié le 19881007

METHODE D'OUVERTURE RAPIDE DE FICHIERS A DISQUES IDENTIFIES PAR LA DENOMINATION DE CHEMINS La présente invention concerne le domaine du traitement des données et plus particulièrement une méthode d'ouverture rapide de fichiers à disques qui sont identifiés par la dénomination de chemins. Arrière plan de l'invention La présente invention constitue une amélioration du système bien connu et disponible sur le marché dans lequel le matériel tel que par exemple un ordinateur personnel IBM, est exploité scus la commande d'un système d'exploitation à disques (DOS) et dans lequel des fichiers sont emmagasinés sur des disques fixes en utilisant des répertoires structurés en arbre et les dénominations des chemins. Les informations sont emmagasinees sur un disque selon une configuratic. prédGtermin-e de cylindres et de secteurs, chacre secteur contenant un nombre prédéterminé de multiplets. Pour accéder à un secteur désire, une tête doit tout d'abord être amenée au cylindre contenant le secteur désiré, Le disque doit être entraîné devant la tête jusqu'à ce que le secteur désiré soit atteint et le secteur doit alors être lu et le contenu placé dans une mémoire intermédiaire. En vérifiant le temps total requis pour accéder aux données sur un disque, on constate que la période de temps principale de l'opération se déroule pendant le mouvement physique d'une tête. Dans le cas o une application requiert une activité E/S physique importante, il est souhaitable de réduire autant que possible l'importance du mouvement de la tête. Des fichiers sont emmagasinés sur le disque en une grappe ou en grappes de secteurs, chaque grappe comprenant un nombre prédéterminé de secteurs. Chaque grappe présente une adresse de début différente et caractéristique. Les emplacements des fichiers sur un disque sont répertoriés au moyen d'une table d'attribution de fichiers (FAT) qui, elle même, est emmagasinée sur le disque. Chaque emplacement de la table FAT est associée à une grappe différente et contient une entrée indiquant qu'il n'y a pas d'autres grappes associées à un fichier ou indiquant la grappe suivante du fichier. De petits fichiers sont disposés dans une seule grappe. Des grappes enchaînées ensemble contiennent les fichiers longs. Les fichiers sont localisés par l'utilisation de répertoires structurés en arbre. Chaque disque contient un répertoire principal, beaucoup de répertoires secondaires et de multiples fichiers. Un fichier donné peut être placé à la fin d'un chemin passant dans le répertoire principal et dars plusieurs r pertoirec secondaires. Chacue répertoire contient des entrees pour répertoires et fichiers supplémentaires. Unr fichier particulier peut être identifié en spécifiant la commande, le chemin et sa dénomination. Par exemple, C:/DIRl/DIR2/FILE1 identifie une dénomination de fichier FILEl qui est listée dans le répertoire DIR2 qui est un répertoire secondaire de DIRI et listé dans celui ci, DIRi étant un répertoire secondaire du répertoire principal et listé dans celui ci, de l'unité de commande C. Lorsqu'un fichier est ouvert, il est nécessaire de permettre l'accès des signaux de commande et de recherche à tous les répertoires spécifiés sur le chemin afin de localiser le répertoire contenant l'entrée de la dénomination de fichier. Dans un tel répertoire, toutes les entrées et dénominations de fichier sont recherchées jusqu'à ce que celle que l'on désire soit localisée. Si un fichier n'a pas été précédemment ouvert, il n'y aura pas d'entrÉe et des entrées devront donc être faites avant de pouvoir utiliser le fichier. Si le fichier a été précédemment ouvert, l'entrée dans le répertoire dans lequel la dénomination de fichier est listée, contient alors une entrée qui est un index dans la table FAT correspondant à la grappe o commence le fichier. Pendant le déroulement d'un tel procédé d'ouverture, l'activité E/S physique doit permettre l'accès au répertoire principal, à chaque répertoire secondaire et la recherche dans une longue liste de dénominations de fichier. Dans certaines applications, les mêmes fichiers sont ouverts beaucoup de fois pendant le déroulement de l'exécution d'un programme donné et puisque chaque ouverture implique une activité E/S physique importante, un temps relativemernt long peut être perdu. L'invention permet d'améliorer la mfthcde d'ouverture de l'art antérieur en présentant une méthode permettant l'ouverture razide de fichiers et la réduction de l'activité E/S physique associée à l'exécution de ce procédé d'ouverture. Résumé de l'invention L'un des objets de l'invention est de fournir une méthode d'ouverture rapide d'un fichier après que ce fichier ait été initialement ouvert au moins une fois. Un autre objet de la présente invention est de fournir une méthode d'ouverture rapide de fichiers dans un système d'ordinateur personnel à hautes performances d'une manière qui réduise l'activité E/S physique associée à ces procédés. Un autre objet de la présente invention est de réduire le temps requis pour ouvrir un fichier en supprimant la nécessite de la recherche dans les répertoires d'une unité de commande à disques et dans les diverses dénominations de fichier et qui serait autrement requise, afin de localiser l'entrée de dénominations de fichier dans un répertoire une fois que le fichier a été précédemment ouvert. Un autre objet de la présente invention est de fournir une méthode pour ré-ouvrir rapidement des fichiers auxquels on a récemment accédé et des fichiers imbriqués qui sont fréquemment ouverts et fermés. En bref, la méthode permettant cette opération consiste à créer et à maintenir dans une antémémoire et mémoire principale un historique de l'utilisation des fichiers. Chaque fois que l'on doit accéder à un répertoire ou un fichier, on vérifie l'historique et si les informations requises pour l'ouverture se trouvent dans l'antémémoire, elles sont utilisées directement sans qu'il soit nécesseire de faire d'autres recherches dans l'arbre de tout répertoire ou dénomination de fichier qui pourrait impliquer une activité E/S physique. En entretenant une antémémoire et mémoire principale, on accède à ces informations aux vitesses élevées de la mémcire principale et les vitesses plus faibles associées à l'activité I/S physique du disque ne sont pas impliquées. DESSINS D'autres objets et avantages de la présente invention ressortiront mieux de la description de la présente invention qui va suivre et faite en se reportant aux dessins ci joints dans lesquels: La figure 1 est une représentation schématique montrant généralement la relation existant entre la présente invention et son environnement ou art antérieur dans lequel elle est mise en oeuvre. La figure 2 est un organigramme montrant le déroulement des étapes générales de la présente invention en réponse à la requête d'un utilisateur. La figure 3 est un organigramme des étapes de sélection depuis les procédures principales de diverses procédures de détails. La figure 4 est un organigramme montrant le déroulement de la procédure de recherche. La figure 5 est un organigramme montrant le déroulement de la procédure d'insertion. La figure 6 est un organigramme montrant le déroulement de la procédure d'annulation de requête. La figure 7 est un organigramme montrant le déroulement de la procédure d'annulation. La figure 8 est un organigramme montrant le déroulement de la procédure de mise è jour et La figure 9 est un organigramme montrant comment le système DOS peut appeler certaines procédures de l'invention. En se reportant maintenant aux dessins et tout d'abord à la figure 1, on voit qu'un système de traitement de données 10 tel qu'un ordinateur personnel IBM AT, comprend un processeur 12 connecté par un bus 14 à une mémoire principale 16 et à l'unité de commande de disques 18. L'unité de commande est à son tour connectée à une unité d'entraînement de disques 20 qui contient un disque 22 portant un milieu d'emmagasinage classique dans lequel des bits d'information sont enregistrés. Pendant le fonctionnement du système 10, les procédures DOS 24 sont chargées ou se trouvent dans la mémoire principale 16 et sont principalement utilisées pour commander l'accès aux informations portées par le disque 22. Le système DOS est associé aux mémoires intermédiaires de système 26 dans ou au travers desquelles des informations sont transférées entre le disque 22 et la mémoire principale 16 de manière classique. Un ensemble de procédures appelées FASTOPEN 28 est aussi chargé et réside dans 1l mémoire principale 16 et sont associées au fonctionnement d'une antémémoire FASTOPEN 30, les détails des procédures serort décrits plus tard. S'il y a plus d'une unité d'entraînement dans le système, il y aura une antémémoire 30 pour chaque unité d'entraînerament. Le disque lui même 22 est formaté de façon à contenir une table d'attribution de fichier (FAT) 32 et le répertoire principal 34. La figure 1 représente aussi un exemple de structure de fichier dans laquelle le fichier 40 appelé FILE1 est situé dans le répertoire secondaire 38 appelé DIR2 qui est lui même est un répertoire secondaire du répertoire secondaire 36 appelé DIR] qui est un répertoire secondaire du répertoire principal 34.Lorsque les procédures FASTOPEN 28 ne sont pas mises en oeuvre, le système fonctionne de la manière classique bien connue. FASTOPEN 28 est mis en oeuvre en initialisant diverses variables décrites ci dessous et qui se terminent ensuite mais continuent de résider dans la mémoire principale 16 afin de rester disponibles pour être utilisées lorque cela est nécessaire. Comme indiqué précédemment, il y a une antémémoire 30 pour chaque unité d'entraînement de disques du système. Chaque antémémoire contient un bloc d'informations connu comme l'en-tête d'antémémoire d'unitC d'entraînement? Cette en-tête contient divers champs dont la signification est donnée à la table 1. Champ Signification l En-tête de chaîne LRU de cette unité d'entraînement. 2 Décalage à dernière entrée de chaîne LRU. 3 Pointeur au premier enfant dans chaîne entrée. 4 Pointeur à l'en-tête d'antémémoire d'unité d'entraînement suivante. -ID entraînement. TABLE I - EN-TETE ANTEMEMOIRE UNITE ENTRAINEMENT Chaque antémémoire 30 contient aussi un certain nombre d'entrées de répertoires et de fichiers contenant chacune les champs d'informations listés à la table 2. Ces entrées forment une structure de données enchaînées qui sera décrite plus en détails ci dessous. La taiiie de l'antémémoire 30 sera déterminée par le nombre désiré d'entrées, lequel nombre peut être choisi par l'intermédiaire d'une valeur par défaut du système ou par la sélection par l'utilisateur du nombre d'entrées. Normalement, le nombre sélectionné par l'utilisateur devra être plus grand que l'emboîtement d'entrées de chemin le plus profond dans l'unité d'entraînement. Champ Signification 1 Pointeur à entrée LRU suivante 2 Pointeur à entrée MRU suivante 3 Pointeur à enfant 4 Pointeur à collatéral Pointeur à noeud précédent 6 Informations répertoires/fichiers TABLE 2 - ENTREE Comme on le verra, les entrées sont maintenues dans une chaîne de telle manière que lorsque l'antémémoire 30 est pleine d'entrées et qu'une nouvelle entrée doit être ajoutée, la nouvelle entrée remplacera l'entrée la moins récemment utilisée (LRU) dans l'antémémoire. Ainsi, les champs 1 et 2 sont utilisés pour enchaîner les entrées selon le concept LRU, MRU (la plus récemment utilisée). Une entrée est ajoutée pour chaaue fichier qui a été ouvert et pour chaque répertoire secondaire compris sur le chemin de ce fichier. Deux fichiers ou répertoires ou combinaisons de ceux ci dans le même répertoire secondaire sont considérés comme étant à des niveaux égaux et sont dits "collatéraux". Toute entrée qui est un répertoire secondaire d'un autre ou d'un fichier est appelée "enfant". Pour la recherche, les entrées dans l'antémémoire sont agencées en une structure en arbre au travers des champs cde pointeur 3-5. Le champ 6 contient les informations qui sont associées à l'entrée de répertoire normale contenue sur le milieu à disque sauf que ces informations sont insérées dans le champ 6 de l'entrée des dénominations et se trouvent donc dans la mémoire principale. On peut donc accéder rapidement à ces informations lorsqu'il est nécessaire d'ouvrir un fichier pour lequel il y a une entrée correspondants dans l'antémémoire 30. Ces informations pour un fichier sont la dénomination du fichier et l'extension, les attributs, l'instant de la dernière écriture, la date de la dernière écriture, la première grappe dans le fichier et la taille du fichier. En se reportant maintenant à la figure 2, lorsque le programme d'application ou de l'utilisateur désire ouvrir un fichier, l'appel d'interruption 21 Hex de DOS qui est connu, est utilisé. Cet appel passe à DOS 24 et FASTOPEN comme indiqué précédemment, est installé de façon à intercepter cette interruption et agit sur elle. La première décision consiste naturellement à déterminer si oui ou non FASTOPEN a été installé et cette opération est réalisée à l'étape 52. Si la réponse est négative, la procédure avance alors selon l'étape de l'art antérieur 54 d'accès au disque pour localiser chaque répertoire secondaire et fichier de manière normale, cette opération étant suivie de l'étape 56 qui revient à l'utilisateur ou, a l'application. Si FASTOPEN est installî, l'étape 58 recherche alors la requête d'une manière qui sera décrite plus en détails par la suite. S'il y avait une erreur pouvant être apparue pendant le déroulement du procédé, l'étape 60 permet alors de passer en 54 et le procédé continue de se dérouler corme dans l'art antérieur. S'il n'y avait pas d'erreur, on détermine alors C l'étape 62 si le chemir a été partieilement trouvé ou inversement, s'il a été entièrement trouvé. S'il n'a pas été partiellement trouvé, c'est à dire si le chemin et la dénomination de fichier complets ont été trouvés, les mêmes informations que celles fournies par l'étape 54 sont alors renvoyées par l'étape 56 à l'utilisateur. Si les informations n'ont été que partiellement trouvées, l'étape 64, en partant du point o les informations ont été trouvées, passe alors à l'accès au disque pour localiser les parties restantes du chemin et de la dénomination de fichier. Chaque partie est insérée à l'étape 66 et l'étape 68 provoque la répétition du procédé depuis l'étape 64 jusqu'à ce que la fin du chemin ou de la dénomination de fichier ait été atteinte, auquel moment les informations appropriées sont renvoyées à l'utilisateur. En se reportant maintenant à la figure 3, on voit que la partie centrale de la procédure est dénommée "principale" et qu'elle est utilisée pour décider lesquelles des quatre procédures secondaires doivent être utilisées. Les procédures secondaires étant dénommées "recherche", "insertion", "suppression" et "mise à jour", respectivement. Ces différentes procédures peuvent, par exemple, être appelées en insérant un chiffre différent qui lui correspond dans l'un des registres du processeur. Dans tous les cas, l'étape 70 décide s'il s'agit d'une opération de recherche, les étapes 72, 74 et 76 décident de manière similaire s'il s'agit d'une opération d'insertion, de suppression ou de mise à jour, respectivement. Si aucune de ces opérations n'est appelée, un signal d'erreur est 2lors renvoya. Ces diverses procédures secondaires seront maintenant décrites en se reportant aux figures particulières qui les concernent. En se reportant maintenant à la figure 4, selon les procédures de recherche, on voit que l'dtape 78 localise tout d'abord l'antémémoire 30 associée à l'unité d'entraînement requise. L'étape 80 conditionne alors la chaîne LRU depuis la pile pré-LRU. Cette pile est une pile logique utilisée pour entretenir le répertoire secondaire structuré en arbre tout en maintenant la chaîne LRU. Puis l'étape 82 forme le début d'une boucle dans laquelle le noeud courant est un pointeur et il est initialement conditionné pour indiquer l'en-tête de commande et est ensuite conditionné pour indiquer l'entrée de noeud courant. L'élément de même origine est établi à zéro et le répertoire ou dénomination de fichier est consulté. La fin du chemin ou de la dénomination de fichier est déterminée par la rencontre de la valeur zéro de ASCII et l'étape 84 décide alors si elle a été atteinte. Si non, ce qui sera le cas habituel lorsqu'une recherche commence tout d'abord, l'étape 86 en utilisant le pointeur de l'enfant depuis l'entrée courante, trouvera alors une entrée d'enfant depuis le mode courant. L'étape 88 essaie de voir s'il y a d'autres enfants. C'est à dire si l'entrée constitue le dernier enfant dans la séquence. Ce fait serait indiqué par un moins un dans le champ enfant. La dénomination désirée est alors comparée au nom de fichier enfant. Si une telle comparaison comme résultat de l'étape 90, est correcte, l'étape 92 crée alors la pile pré-LRU, retient l'adresse de noeud courant dans la pile et se rebranche à l'étape 82. Le déroulement du procédé se poursuit jusqu'à ce que la dénomination de fichier soit trouvée, auquel moment la détermination oui ou positive de l'étape 84 assure le branchement à l'étape 94 et l'enregistrement ou les informations qui sont trouveú sont renvoyés à DOS. Si l'étape 90 résulte en une détermination négative, l'étape 98 vérifie le pointeur du champ d'élément de même origine et par une boucle revenant aux étapes 96, 90 et 98, se poursuivra jusqu'à ce qu'il n'y ait plus d'éléments de même origirne, auquel moment l'étape 94 revient à DOS. Lors du retour à DOS, FASTOPEN conditionnera le pointeur pour indiquer le répertoire ou la dénomination de fichier trouvé dans la suite chemin/dénomination de fichier délivrée par DOS. DOS, à son tour, vérifiera le pointeur pour déterminer si le chemin complet a été trouvé ou si un chemin partiel seulement a été trouvé ou s'il n'a rien trouvé. Lorsqu'il y a plus de collatéraux, l'étape 96 conditionne le pointeur de noeud courant au collatéral courant. En se reportant à la figure 5, on voit que la procédure d'insertion a pour but d'insérer des informations de répertoire ou de fichier comme une entree en antémémoire, en se basant sur les informations de noeud courant et de collatéraux courants. L'étape 102 effectue une entrée d'enregistrement de dénomination depuis l'entrée et l'étape 104 obtient l'entrée disponible suivante. Jusqu'à ce que l'antémémoire soit remplie, une nouvelle entrée sera simplement placée dans n'importe quel emplacement ou entrée qui sera libre. Une fois que l'antémémoire est remplie, l'entrée la moins récemment utilisée en se basant sur la liste LRU, sera alors l'entrée disponible suivante à remplacer par une plus récente. L'étape 106 vide la pile pré-LRU dans la mesure on il y reste quelque chose. Si le pointeur de collatéral courant est éqal à zéro, la nouvelle entrée est alors installée par l'étape 110 comme un enfant sous le noeud courant et l'étape 112 enregistre ce noeud dans la pile pré-LRU. Si un collatéral courant à l'étape 108 n'est pas égal zéro, l'étape 114 installe la nouvelle entrée comme un collatéral du noeud courant. En se reportant maintenant aux figures 6 et 7, on voit que lorsqu'une application ou un ut:ilisateur requiert qu'un fichier particulier soit supprimé, une procédure non seulement supprime le fichier sur le disque de manière habituelle mais supprime aussi toutes les entrées correspondantes en antémémoire. Ainsi, en réponse à la requête de l'utilisateur à l'étape 116, le processus passe par DOS 24 et l'étape 118 décide si FASTOPEN a été installé. Si non, l'étape 122 permet d'accéder au disque et supprime le fichier, après quoi l'étape 124 revient à l'utilisateur. Si FASTOPEN est installé, la requête de suppression 120 est réalisée. En réponse à cette requête, l'étape 126 vérifie l'antémémoire pour déterminer si oui ou non il y a une i3 entrée correspondante. Si aucune entrée n'est trouvée, la procédure est simplement passée en sortie. Si l'entrée est trouvée, elle est retirée de la chaîne LRU structurée en arbre par l'étape 132 et cette entrée particulière est placée sur le haut de la chaîne LRU comme étant disponible pour être utilisée par une nouvelle entree. Une entree de fichier est tout d'abord supprimée et ensuite tous les répertoires parents qui ne contiennent aucun pointeur d'enfant ou de collatéral. En se reportant maintenant aux figures 8 et 9, on voit qu'il y a certaines fonctions construites dans les procédures FASTOPEN qui peuvent être appelées directement par DOS pour assurer certaines fonctions accessoires des fonctions assurées par DOS. Les requêtes de DOS sont accessoires aux fonctions de fermeture d'un fichier, d'écriture de multiplets nuls dans un fichier ou de réalisation d'un noeud et les étapes 142, 1zz et 146 déterminent respectivement si de telles fonctions sont requises et assurent alors le branchement aux étapes de mise à jour de 134-140. Les résultats positifs des étapes 136- 140 mettent respectivement à jour une entree de répertoire, mettent à jour un nombre de grappes associées à un fichier et suppriment une entrée. Dans la discussion précédente, on a mentionné la pile pré-LRU et ceci va maintenant être expliqué en fonction de la pile LRU, ces deux piles impliquant toutes les deux l'utilisation des pointeurs LRU et MRU dans les entrées. A mesure que le déroulement du procédé avance sur un chemin, il va du répertoire principal et au travers de tous les répertoires secondaires, jusqu'à la dénomination de fichier et une pile pré-LRU est réalisée en accord avec l'ordre dans lequel on accède aux divers noeuds. Ainsi, dans l'exemple d'un fichier auquel on a accès ou spécifié par C:/DIR1/DIR2,'FILE1, l'ordre des entrées est le répertoire principal DIR1, DIR2 et FILE1. Cet ordre crée un problème dans la mesure o le répertoire principal est l'entrée la moins récemment utilisée et si cette entrée est supprimée pour remplacement, l'entrée aux entrées restantes sera alors coupée. On évite ce problème en utilisant la pile pré-LRU et en ré-ordonnant les entrées, une fois que le chemin est établi, afin de créer une pile LRU dans laquelle la dénomination de fichier apparaîtra comme étant l'entrée la moins récemment utilisée et alors, au remplacement, ce sera la dénomination de fichier et non un quelconque répertoire parent qui sera initialement remplacé. Il est évident pour l'homme de l'art que d'autres changements et modificatior.s peuvent être apporte?, la présente invention sans pour autant sortir de l'esprit et du cadre de celle ci telle que définie par les revendications ci jointes. Revendications 1. Méthode d'exploitation d'un système de traitement de données permettant d'ouvrir rapidement un fichier récemment ouvert mais actuellement fermé, contenu dans un disque et situé dans une structure en arbre de répertoires et de fichiers, caractérisée en ce qu'elle comprend les étapes suivantes: la création d'une antémémoire en mémoire principale dudit système de traitement de données lorsque ledit fichier est initialement ouvert, contenant plusieurs entrées enchaînées identifiant ledit fichier et chaque répertoire contenu dans ladite structure en arbre qui reste sur le chemin de ce fichier, ladite entrée pour ledit fichier contenant des informations lues depuis ledit disque et identifiant ledit fichier et sonr emplacement sur ledit disque, et en réponse à une requête ultérieure pour ouvrir ledit fichier, la recherche dans lesdites entrées enchaînées dans ladite antémémoire et l'accès auxdites informations afin d'éviter ainsi d'avoir à obtenir les mêmes informations par lecture de celles ci sur ledit disque. 2. La méthode selon la revendication 1 dans laquelle ledit système de traitement de données comprend plusieurs unites d'entraînement de disques, ladite méthode étant caractérisée en ce qu'elle comprend l'étape suivante: la création de plusieurs antémémoires correspondant en nombre au nombre des unités d'entrainement de disques et comprenant dans chaque antémémoire, une en-tête d'unité d'entraînement identifiant chaque unité d'entraînement, ladite étape de recherche étant caractérisée en ce qu'elle comprend tout d'abord l'accès à au moins une en-tête d'unité d'entraînement pour localiser celle desdites antémémoires correspondant à l'unité d'entraînement contenant le fichier à ouvrir. 3. La méthode selon la revendication 1 caractérisée en ce que: ladite étape de création comprend la provision d'une antémémoire d'une certaine taille pour contenir un nombre prédéterminé d'entrées, et par le remplissage initial de ladite antémémoire en plaçant des entrées dans celle ci dans des emplacements inutilisés, et par l'addition de nouvelles entrées en plaçant chacune d'elles dans un emplacement correspondant à l'entrée existante dans ladite artémémoire qui correspond à celle du fichier le moins récemment utilisé. 4. La méthode de la revendication 3 caractérisée en ce qu'elle comprend: l'emmagasinage de pointeurs dans lesdites entrées pour créer une chaîne d'entrées ordonnées depuis le fichier le plus récemment utilisé jusqu'au fichier le moins récemment utilisé. 5. La méthode de la revendication 1 caractérisée en ce qu'elle comprend: l'ouverture d'un fichier pour lequel des entrées existant dans ladite antémémoire forment une partie d'un chemin complet à ce fichier, par accès à ces entrées dans ladite antémémoire correspondant à cette partie et ensuit, par lecture de ces autres informations comme nécessaire pour former un chemin complet depuis ledit disque. 6. La méthode selon la revendication 5 caractérisée en ce qu'elle comprend: la création d'entrées à partir de ces informations et l'addition de ces entrées à ladite antémémoire.