<Desc/Clms Page number 1>
METHODE DE TRAITEMENT D'ERREURS
DE SECTEURS DE DISQUES DANS UNE ANTEMEMOIRE
DOMAINE DE L'INVENTION La presente invention concerne des ameliorations apportées aux methodes d'exploitation d'un systeme de traitement de donnes comportant une antémémoire de dispositif d'emmagasinage ä acces direct (DASD) de facon ä traiter des erreurs de secteur de disques provoquées par des défauts du milieu d'emmagasinage. La presente invention concerne plus particulièrement une méthode d'exploitation d'un ordinateur personnel ä performances élevées pour apporter une solution bon marché au probleme du traitement des erreurs graves dans une antememoire DASD.
ART ANTERIEUR 11 est bien connu dans 11 art antérieur d'utiliser des unites de commande à disques fixes ou durs pour emmagasiner des informations pour effectuer des operations de traitement dans une unité de traitement connectée ä une memoire principale. Des informations sont emmagasinées sur des disques selon une configuration prédéterminée de cylindres et de secteurs, chaque secteur contenant un nombre predetermine de multiplets. Une unité de commande comprend plusieurs têtes, une tête étant prévue de chaque côté d'un disque sur lequel des donnees sont emmagasinees. Les donnees sont lues depuis un disque, secteur par secteur.
Pour acceder à un secteur desire, une tete doit tout d'abord être entraînée au cylindre contenant le secteur désiré, le disque doit être entraîne en rotation devant la tête jusqu'à ce que le secteur desire soit atteint et le secteur est alors lu et son contenu place dans une memoire intermédiaire. En
<Desc/Clms Page number 2>
considérant le temps total requis pour accéder ä des donnees sur un disque, on constate que le temps le plus long s'écoule pendant le mouvement physique d'une tete.
Ainsi, lorsque le traitement implique une importante activité d'entrée/sortie (E/S), il est hautement souhaitable de reduire autant que possible l'importance du mouvement de la täte pour bénéficier de performances améliorées.
La mise en antémémoire DASD est une technique connue dans l'art anterieur et constitue un moyen d'améliorer les performances du système en réduisant l'importance du mouvement de la tête et l'activité E/S physique.
Selon cette technique, une partie de la mémoire principale est utilisée comme une antememoire pour emmagasiner des pages de secteurs de donnees. Lorsque l'on accede initialement ä un secteur desire, non seulement ce secteur mais aussi un ou plusieurs secteurs proches supplementaires sont lus dans l'antememoire et les accès suivants ä ces secteurs sont faits ä des vitesse de mémoire principale au lieu d'être faits ä des vitesses d'unite de commande ä disques. L'amelioration des performances est due ä la probabilité de l'emmagasinage des données suivantes ä traiter pres des données qui ont été precedemment traitées.
L'un des problèmes connus dans l'art anterieur survient en raison du fait que des défauts existent dans le milieu d'emmagasinage à disque. Ainsi, des secteurs contenant ces défauts sont considérés comme mauvais et ne peuvent pas être utilises. Ces mauvais secteurs sont normalement identifies par formattage et les utilisations ulterieures de ceux ci sont evitees par simple saut des mauvais secteurs. Le problème devient plus complique dans les systemes ä antememoire puisque, lorsqu'un bon secteur est initialement lu dans
<Desc/Clms Page number 3>
l'antememoire, des secteurs proches de la meme page peuvent contenir des erreurs ou être mauvais. Dans le cadre de l'art anterieur qui nous est connu, ce Probleme a été résolu de deux manières differentes.
Tout d'abord, toute page contenant un mauvais secteur est elle meme consideree comme mauvaise et un signal ou message d'erreur est envoyé ä l'utilisateur. Ensuite, l'unité de commande de disques peut être construite de façon que seuls les bons secteurs soient envoyés ä l'antememoire. Cette solution est une solution materielle et est relativement compliquee et croûteuse ä realiser. La presente invention concerne une methode qui peut etre facilement mise en oeuvre par logiciel ou programmation pour apporter une solution effective bon marché qui serait particulièrement utile dans les ordinateurs personnels ä hautes performances et relativement bon marché.
RESUME DE L'INVENTION L'un des objets de la présente invention est de fournir une nouvelle methode de traitement des erreurs de secteur de disques dans un système ä antememoire DASD.
Un autre objet de la presente invention est d'apporter une solution bon marché au problème du traitement des erreurs de secteur dans un ordinateur personnel ayant un Systeme d'antememoire DASD.
Un autre objet de la presente invention est de fournir une méthode de traitement des erreurs de secteur dans un système d'antememoire DASD, laquelle methode pourra etre facilement mise en oeuvre par la programmation de materiel connu.
Un autre objet de la présente invention est de fournir une methode pouvant être facilement utilisée avec un
<Desc/Clms Page number 4>
système d'exploitation de disques (DOS) disponible dans le commerce pour assurer une fonction d'antememoire qui soit transparente à l'utilisateur tout en résolvant facilement le problème du traitement des erreurs de disques.
En resume, selon les enseignements de la presente invention, ä mesure que chaque page contenant plusieurs secteurs est lue en mémoire principale, une table séparée est construite et emmagasine des informations pour savoir si chaque secteur est bon ou mauvais. Les
EMI4.1
accès ultérieurs à n'importe quel secteur sont ccE a effectues en se reportant ä ou en consultant les informations de cette table et en sautant tout secteur indique comme etant mauvais ou erroné.
DESSINS D'autres objets et avantages de la presente invention ressortiront mieux de la description qui va suivre faite en se reportant aux dessins ci joints dans lesquels : La figure l est une representation schematique d'un système d'ordinateur personnel dans lequel la methode de la presente invention peut etre mise en oeuvre.
La figure 2 est une représentation schematique de la structure de données d'antememoire utilisee dans la presente invention.
La figure 3 est une representation schematique montrant combien de pages sont référencées depuis une table de donnees mêlées.
<Desc/Clms Page number 5>
La figure 5 est une representation schématique illustrant la chaine de liste LRU (la page la moins
EMI5.1
recemment utilisée).
La figure 6 est une représentation schematique montrant comment divers programmes et matériels sont generalement mis en oeuvre dans la présente invention.
Les figures 7-12 sont des organigrammes illustrant la méthode de la presente invention, et La figure 13 est une représentation schématique illustrant la structure des donnees de liste d'erreurs.
DESCRIPTION La description qui va suivre est organisee en deux parties. La première partie décri t le fonctionnement général de l'antémemoire DASD et décrit donc l'environnement dans lequel est utilisée la methode de la présente invention. La deuxieme partie est une description détaillée du traitement des erreurs des milieux d'emmagasinage. 11 est cependant evident que la présente invention réside dans la méthode et non dans la mise en oeuvre d'un logiciel particulier.
ANTEMEMOIRE La methode de la présente invention est de préférence utilisée dans un Systeme de traitement de données classique 10 tel que l'ordinateur personnel IBM AT. Ce système 10 comprend generalement un processeur 12 connecte ä une mémoire principale 14 et ä des dispositifs EIS 15. Ce système peut contenir une ou plusieurs unites de commande de disques 16, chacune de ces unites etant respectivement connectée ä une unite d'entrainement de disques 18.
Une antememoire 20 et une
<Desc/Clms Page number 6>
mémoire intermediaire de données 21 sont formées dans la memoire principale 14 comme des structures de données, la mémoire intermediaire de données etant utilisee par DOS pour emmagasiner temporairement chaque secteur de données en cours de transfert depuis les unités d'entraînement de disques 18.
En se reportant ä la figure 2, on voit que l'antémémoire 20 comprend une structure de pages 21 comprenant une pluralite de pages d'antémémoire 22-1 ä 22-n. L'antememoire 20 contient en outre une table de données mêlées 24, un pointeur de liste libre 26, un pointeur LRU (la page la moins récemment utilisée) 28, un pointeur MRU (la page la plus recemment utilisée) 30 et une liste d'erreurs 31 dont les details seront maintenant décrits. Ces six parties toujours présentes quelque soit la taille de l'antémérnoire, sont :
La page d'antémémoire 22 - Elle définit la structure d'une page d'antémémoire en memoire.
Elle contient des informations pour étiqueter la page physique qui est représentée, la partie de la liste LRU, la partie de la liste de conflits de la table de donnees melees et les données reelles de la page d'antememoire groupees par secteurs.
Le pointeur LRU (la page la moins récemment utilisée) 28 - Ce pointeur indique une page d'antémémoire qui est la page la moins récemment utilisee dans l'antememoire. C'est ä dire que toutes les autres pages dans l'antememoire ont ete accédées plus recemment que la page indiquée par le pointeur LRU.
Le pointeur MRU (la page la plus récemment utilisee) 30 - Ce pointeur indique une page d'antememoire qui est la page la plus récemment
<Desc/Clms Page number 7>
utilisée dans l'antémémoire. C'est ä dire qu'aucune page dans l'antememoire n'a ete accedee plus recemment que la page indiquée par le pointeur MRU.
La table de données mêlées d'antémeoire 24 Cette table est un vecteur des pointeurs des pages d'antememoire. Le vecteur a une longueur de 311 entrees. Lorsqu'un secteur est demande, l'antememoire intercepte la demande et la mêle dans cette table pour déterminer si le secteur est dans l'antememoire. En utilisant une table de donnees mêlées, un temps très court suffit pour determiner si un secteur est dans l'antememoire, meme stil y a un grand nombre de pages dans l'antememoire.
Le pointeur de liste libre 26 - Ce pointeur indique une page d'antememoire qui n'est pas actuellement utilisée dans l'antémémoire.
Initialement, toutes les pages dans l'antémémoire sont sur cette liste. Lorsque l'on constate qu'une page n'est pas dans l'antememoire, une page est retirée de la liste libre et placée dans l'antémémoire.
EMI7.1
..
La liste d'erreurs 31-Cette structure de données décrite en details ci dessous, est utilisée pour indiquer l'historique des erreurs de pages.
La table 1 indique les champs d'une page d'antememoire 22. Les champs dans la structure sont définis ci dessous. On notera que tous les pointeurs sont maintenus sous la forme de deux multiplets. C'est le cas pour une architecture segmentee comme la famille Intel 8086/80186/80286/80386. La valeur emmagasinée dans le pointeur est le segment (8086/80186) ou le
<Desc/Clms Page number 8>
slecteur (80286/80386). Un décalage suppose de 0 est associé ä chaque structure de données.
Les divers champs ont les significations suivantes : Champ 1 Ce champ contient des bits ou des drapeaux qui indiquent les secteurs dans la page qui sont presents et contiennent des donnees valides et les secteurs qui sont manquants en raison d'erreurs.
Champ 2 Ce champ détermine sur quelle unite d'entraînement cette page particulière est contenue.
EMI8.1
Champ 3 Ce champ contient l'adresse de bloc relative (RBA) du secteur de debut de la page sur l'unité d'entrainement.
Champ 4 Ce champ indique la page suivante qui est moins récemment utilisée que cette page. S'il s'agit de la page la moins récemment utilisee, ce champ contiendra alors la valeur
0. Ce champ est aussi utilisé pour lier des pages ensemble sur la liste libre.
Champ 5 Ce champ indique la page suivante qui est plus récemment utilisée que cette page. S'il s'agit de la page la plus récemment utilisée, ce champ contiendra alors la valeur 0.
Champ 6 Ce champ indique la page suivante qui est sur la liste de conflits de la table de données melees.
Champ 7 Ce champ indique la page précédente qui est
<Desc/Clms Page number 9>
sur la liste de conflits de la table de donnees mêlées.
Champ 8 Ce champ contient les données pour la page telles qu'elles sortent de DASD. Si cette page est référencée plusieurs fois, les parties de la page qui sont demandées seront des copies issues de cette mémoire intermediaire plutôt que lues depuis le dispositif.
EMI9.1
<tb>
<tb>
Champ <SEP> Contenu <SEP> Multiplets
<tb> 1 <SEP> Drapeaux <SEP> présents <SEP> 2
<tb> 2 <SEP> ID <SEP> Entraînement <SEP> 1
<tb> 3 <SEP> RBA <SEP> 4
<tb> 4 <SEP> LRU <SEP> suivant <SEP> 2
<tb> 5 <SEP> LRU <SEP> précédent <SEP> 2
<tb> 6 <SEP> Conflit <SEP> suivant <SEP> 2
<tb> 7 <SEP> Conflit <SEP> précédent <SEP> 2
<tb> 8 <SEP> Mémoire <SEP> intermediaire <SEP> pages <SEP> Secteurs <SEP> 1-8
<tb>
TABLE 1 PAGE ANTEMEMOIRE 22 Chaque RBA est déterminé par la formule suivante :
RBA = ( (CN x NH) + HN) x SPT + SN (Formule 1) dans
EMI9.2
laquelle : CN = Nombre de cylindres NH = Nombre de tetes par unite d'entrainement HN = Nombre de têtes SPT = Nombre de secteurs par piste SN = Nombre de secteurs
<Desc/Clms Page number 10>
L'index de données mêlées est déterminé par la formule suivante :
Index données mêlées = RBA shr log (taille page) mod 311 (Formule 2) dans laquelle : shr = RBA decale à droite du nombre de bits selon le logarithme base 2 de la taille de page taille page = nombre de secteurs par page mod = fontions modulo qui renvoient le reste La valeur de 311 est preferee comme longueur de table de donnees mêlées car il s'agit d'un nombre premier relativement important. Etant donne que 311 est un nombre premier important, il est peu probable qu'une application l'utilise très souvent ou l'un de ses multiples pendant l'accès à l'antememoire. Ceci permet de maintenir les chaines de conflits courtes en reduisant les risques d'une application passant en synchronisme avec l'algorithme des donnees mêlées de facon que les données mêlées puissent être résolues rapidement.
En se reportant ä la figure 3, on voit que les diverses positions d'index 0-310 de la table 24 contiendront soit un 0, soit un pointeur de la première et peut être seule page d'antememoire enchaînée ä cette position. Si l'entree de la table de donnees mêlées qui est sélectionnée contient la valeur 0, il n'y a alors pas de pages indiquées par l'entree et la page n'est pas dans l'antememoire. Ceci est considéré comme un"defaut de page".
La position d'index 1 par exemple, contient un zéro indiquant qu'il n'y a pas de pages associées ä celle ci dans l'antSmemoire. Si d'autre part, l'entree
<Desc/Clms Page number 11>
EMI11.1
de la table de donnees melees n'est pas 0, la valeur ici est utilisee comme un pointeur pour indiquer une page d'antdmemoire 22. L'entraînement et RBA sur une page d'antémémoire sont comparés à l'entraînement requis et RBA. S'il apparaît que ce sont les memes, on considère qu'une page a été trouvee et que la page requise est dans l'antememoire. Si ce ne sont pas les mêmes, la valeur Conflit suivant dans cette page est utilisee pour indiquer la page d'antérnémoire suivante.
Si une valeur de 0 est extraite de ce champ, la fin de la chaine de conflits a été atteinte et la page requise
EMI11.2
n'est pas dans l'antememoire. Il s'agit ä nouveau d'un "défaut de page". Comme illustré par les dessins, les pages A-F sont revendiquees ä partir de la table 24 pour former trois chaînes séparées de longueurs differentes.
Si une page 22 est trouvée dans l'antémémoire, la chaîne de conflit pour cette entrée de table de donnees mêlées est ré-ordonnée pour que la page trouvee soit en tête de la chaîne de conflit. L'idee ici est que si la chaîne de conflit est gardee dans une ordre MRU, les balayages en descendant la chaine de conflits seront courts en raison de la probabilite d'un nouvel acces d'une page récemment utilisee. Ceci est particulièrement vrai si une page d'antememoire représente plus d'un secteur physique.
Si une page n'est pas trouvée dans l'antememoire, une nouvelle page est attribuee (les moyens exacts permettant de réaliser cette operation seront decrits ultérieurement). Une page est lue depuis un disque et placee dans la memoire intermediaire de pages (champ 8). La nouvelle structure de page d'antememoire est alors construite en fonction de la table de donnees mêlées avec des algorithmes similaires à ceux qui furent utilisés pour déterminer que la page n'etait pas
<Desc/Clms Page number 12>
dans l'antememoire. 11 y a une différence importante. La chaîne de conflits pour l'entrée de la table de donnees melees n'est pas resolue.
A la place, la nouvelle page est insérée en tête de la chaîne de conflits si bien que les chaines de conflits restent ordonnées par rapport ä MRU. En outre, les pointeurs de chaine LRU sont re-ordonnés pour indiquer cette page comme la plus récemment utilisee.
Une nouvelle page 22 n'est placée dans l'antememoire 20 que lorsqu'un secteur requis n'est pas trouvé dans l'antémémoire. La méthode a été décrite dans la section précédente. Cette section decrira comment une page est réellement attribuée de façon qu'elle puisse être placée dans la structure d'antememoire. 11 y a deux moyens d'attribuer une page. S'il y a une ou plusieurs pages sur la liste libre d'antememoire, une page est retiree de la liste libre et attribuee pour la nouvelle page. S'il n'y a pas de pages sur la liste libre d'antememoire, la page qui est indiquée par le pointeur LRU est retirée de la structure d'antememoire et ré-attribuée ä la nouvelle page.
La figure 4 montre la structure de la liste libre d'antememoire. Le pointeur de liste libre 26 indique la page d'antémémoire 22 en tête de la liste et l'un des champs de pointeur indique la page libre suivante. Initialement, toutes les pages d'antémémoire sont sur la liste libre et aucune page n'est indiquée par la table de données mêlées ou la
EMI12.1
liste LRU. Lorsque des requêtes sont faites au disque et qu'il y ades défauts de page d'antdmemoire, de plus en plus de pages 22 seront retirees de la liste libre jusqu'à ce que finalement, il n'y est plus aucune page sur la liste libre. Dans ce cas, les pages sont ré-utilisées en se basant sur la liste LRU.
La figure 5 montre la structure de la liste LRU avec les pointeurs LRU et MRU 28 et 30 qui indiquent les extrémités de la
<Desc/Clms Page number 13>
liste et les diverses pages 22 étant enchaînées par les pointeurs LRU Suivant et LRU Précédent.
Etant donné que l'antememoire essaie toujours d'effectuer une attribution depuis la liste libre avant de retirer des pages de la liste LRU, il est possibled'ajouter dynamiquement plus de pages à l'antememoire une fois que l'antememoire est opérationnelle. Ceci est particulierement souhaitable si l'antémérnoire n'est mise en oeuvre qu'en logiciel seulement. Le raisonnement derriere tout cela est qu'un Systeme d'exploitation peut voir que la memoire principale n'est pas entierement utilisee et peut décider qu'une partie de cette mémoire pourrait Atre bien utilisée en donnant une partie de ou toute la mémoire inutilisee ä l'antememoire.
L'inverse (le retrait de pages de l'antememoire) est aussi possible en retirant une ou plusieurs pages ä partir de l'extrémité de la liste LRU. Ceci peut ne pas etre souhaitable etant donne qu'on ne peut pas garantir que les pages sont physiquement contigues en memoire. Mais en considerant un Systeme d'exploitation suffisamment sophistiqué, la fragmentation de la mémoire peut ne pas etre un probleme.
Chaque fois qu'une page est accédée dans l'antememoire (soit par un coup au but ou par l'attribution d'une nouvelle page), cette page est retiree de sa position courante dans la liste LRU et passée en tete de la liste indiquee par le pointeur MRU. Etant donne que la structure de page d'antememoire est fondée sur des pointeurs, le mouvement des pages dans la liste LRU est assuree par le simple déplacement alentour des valeurs de pointeur d'une manière connue.
<Desc/Clms Page number 14>
L'épinglage d'antememoire (le placement permanent d'une ou plusieurs pages dans l'antémémoire) est assuré facilement par ce concept. Pour épingler une page, tout ce qu'il est nécessaire de faire est de retirer la page de la liste LRU. Etant donné que des pages sont ré-attribuées ä partir de la liste LRU, une page qui niest pas sur la liste LRU ne peut jamais être ré-attribuée. L'épinglage est souhaitable lorsque l'on n'accede pas suffisamment souvent ä certaines pages pour les conserver dans l'antémémoire. Ceci permettrait ä des structures de Systeme de fichier comme des répertoires, des mappes de bits d'attribution, des fichiers de systeme, etc..., d'etre conservees dans l'antememoire pour assurer de bonnes performances sans qu'elles soient chassees par une lecture d'un fichier important.
Afin d'exécuteur l'epinglage d'antememoire d'une maniere utile, il est souhaitable de faire cooperer l'antememoire et le Systeme d'exploitation ou au moins un accessoire du système d'exploitation.
L'accessoire informera l'antememoire que jusqu'ä indication différente, les pages requises ne sont pas ä placer dans LRU. L'accessoire lira alors le ou les secteurs, le ou les fichiers, etc..., et indiquera alors a l'antememoire que toutes autres requêtes d'antememoire placeraient les pages dans LRU.
L'antememoire devrait êtres sensible au fait que certaines pages peuvent ne pas faire partie de LRU et ne doivent pas être inserees dans LRU en cas d'accès.
On peut s'assurer de cela lorsqu'un coup au but d'antememoire est realise en verifiant si les champs de LRU Suivant et Precedent sont ä 0. Si c'est le cas, la page n'est pas ä placer dans LRU. De cette maniere, aucun bit ou drapeau supplementaire n'a ä faire partie de la structure de page d'antememoire pour supporter l'epinglage.
<Desc/Clms Page number 15>
La figure 6 montre de maniere générale comment la présente invention est mise en oeuvre selon un ensemble de procédures appele CACHESYS associe ä des programmes et du matériel classiques pour executer ladite méthode de la presente invention.
Lorsqu'un programme d'application 40 a besoin de lire des donnees sur un disque 18, DOS 42 est applé et, au moyen d'une interruption classique 13H, l'appel concernera le systeme d'entree/sortie de base (BIOS) 44. CACHESYS 50 est interpose entre DOS 42 et BIOS 44 et peut être construit comme une routine de traitement d'interruption pour intercepter et exécuter les diverses procédures decrites en details ci dessous. 11 apparalt que DOS fonctionne comme BIOS 44 et par rapport ä BIOS 44, le Systeme CACHESYS apparait comme DOS 42. C'est ä dire que le fonctionnement de CACHESYS 50 est transparent pour DOS 42 et BIOS 44.
Sous la commande de BIOS 44, les données du disque 18 seront transmises au travers de l'equipement 46 ä la mémoire intermédiaire de données 21 en mémoire principale et ensuite rendues disponibles pour le programme d'application au travers de DOS d'une manière classique. Lorsque CACHESYS 50 est operationnel et en réponse ä l'interception de l'appel d'interruption 13H, si le secteur désiré contenant les donnees nécessaires sont toujours dans l'antémémoire d'entraînement 20, les données seront alors placées dans la mémoire intermediaire 21 et rendues disponibles pour le programme d'application.
Si les données ne sont pas dans l'antememoire 20, CACHESYS appellera alors BIOS 44 pour faire lire les données du disque 18 dans la mémoire intermédiaire 21, d'où elles seront rendues disponibles pour le programme d'application. De plus, dans le cas de la premiere utilisation de ces données, elles seront aussi placées dans l'antememoire 20 pour être disponibles pour des operations ultérieures. En
<Desc/Clms Page number 16>
outre, des secteurs consecutifs proches seront aussi pré-extraits ou lus dans l'antémémoire 20.
En se reportant ä nouveau ä la figure 7, on voit que
EMI16.1
lorsque les procedures 50 sont appelles comme par l'interception de l'interruption, l'etape 100 determine ou calcule l'index dans la table de donnees mêlées 24 depuis la valeur RBA du secteur désiré. L'etape 102 place alors le contenu de la table de données mêlées à l'index dans une variable connue sous la designation de PAGE PTR et l'étape 104 détermine si oui ou non PAGE PTR est égale ä zéro pour signifier la fin d'une chaîne de conflits. Dans ce cas, une nouvelle page est alors lue ä l'étape 106 et la nouvelle page est placée dans l'antememoire par l'étape 108, après quoi l'étape 110 revient ä DOS et ä l'application.
Si ä la suite de
EMI16.2
l'étape 104, le pointeur de page n'est pas egal ä zero, les etapes 112 et 114 déterminent alors si le pointeur de page indique la page désirée. Cette opération est exécutée en comparant tout d'abord la specification de commande du pointeur de page ä la commande désirée contenant les données, ä l'étape 112, et s'il s'agit de la commande correcte, l'etape 114 compare alors la valeur RBA du pointeur de page ä la valeur RBA mise en condition OU avec le masque de RBA.
Si les étapes 112 et 114 donnent des résultats négatifs, l'etape 116 met alors ä jour le pointeur de page pour indiquer la page suivante dans la chaine de conflits et l'execution de ce procédé se poursuivra jusqu'à ce que la page désirée soit atteinte, apres quoi les résultats positifs de
EMI16.3
l'étape 114 passent ä 118.
Les étapes 118-130 ont comme fonction générale de vérifier si oui ou non les secteurs requis se trouvent dans la page d'antememoire. S'ils y sont, un résultat positif de l'étape 130 permet de passer ä l'étampe de retour 110 et les données de secteur sont transferees
<Desc/Clms Page number 17>
de sa page d'antememoire 22 à la mémoire intermédiaire 21. S'ils n'y sont pas, un résultat négatif de l'étape 130 permet alors de revenir ä l'étape 106 pour lire la page contenant les secteurs désirés. Afin de comprendre ce qui arrive pendant le déroulement des étapes 118-130, il sera maintenant souhaitable de considérer l'étape 106 et comment une nouvelle page est lue dans l'antememoire.
L'étape 106 est une étape generale et les étapes détaillées impliquées dans celle ci seront décrites en se reportant aux figures 8-12. Cependant, avant de décrire en détails ces diverses étapes, on expliquera certaines variables et structures de données utilisées ici.
TRAITEMENT DES ERREURS La table 2 donne la signification des différentes variables utilisées pour l'exécution de ce procédé. Ces variables sont initialisees au debut du procede. La liste d'erreurs 31 (Figure 2) comprend comme le montre schématiquement la figure 13, une table de données mêlées d'erreurs 150, la chaine de conflits 152 et la liste libre 154 où il y'a une entrée par page. Les chaines de conflits et les listes libres sont construites et traitees similairement aux procedures décrites en se reportant aux pages 3 et 4. Une table de données mêlées est utilisée puisque, bien que la liste d'erreurs soit relativement petite, elle est balayee chaque fois qu'il y a une entree/sortie physique et il est souhaitable de conserver un temps de recherche aussi court que possible.
La table de données mêlées 150 a une longueur de 64 repères, cette longueur étant choisie car il s'agit d'une puissance de deux et la valeur RBA de page peut etre manipulée facilement avec des décalages et un masque plutôt qu'avec un partage.
<Desc/Clms Page number 18>
Ceci est justifié sur un nombre principal d'entrées par le fait que des erreurs sur un disque sont generalement réparties plutôt uniformement et que la vitesse est le facteur le plus important étant donné que cette table sera accédée chaque fois que l'antémémoire sera affectee par des entrées/sorties physiques. La table de donnees melees 150 indique les chalnes de conflits des entrées de liste ä erreur.
EMI18.1
<tb>
<tb>
Variable <SEP> Signification
<tb> RBA <SEP> - <SEP> Valeur <SEP> RBA <SEP> de <SEP> la <SEP> page <SEP> ä
<tb> lire.
<tb>
POINTEUR <SEP> MEMOIRE <SEP> - <SEP> Pointeur <SEP> pour <SEP> indiquer <SEP> où
<tb> INTERMEDIAIRE <SEP> les <SEP> donndes <SEP> seront <SEP> lues.
<tb>
DIMENSIONS <SEP> PAGE <SEP> - <SEP> Nombre <SEP> de <SEP> secteurs <SEP> dans
<tb> une <SEP> page <SEP> (2,4 <SEP> ou <SEP> 8).
<tb>
MASQUE <SEP> RBA <SEP> - <SEP> = <SEP> NON <SEP> (DIMENSIONS <SEP> PAGE-1)
<tb> (C'est <SEP> à <SEP> dire <SEP> OFFFFFFFC).
<tb>
DECALAGE <SEP> RBA-= <SEP> log <SEP> (DIMENSIONS <SEP> PAGE)
<tb> (C'est <SEP> ä <SEP> dire <SEP> 1, <SEP> 2 <SEP> ou <SEP> 3 <SEP> pour
<tb> DIMENSIONS <SEP> PAGE <SEP> 2,4 <SEP> ou <SEP> 8).
<tb>
MASQUE <SEP> CPTE <SEP> SEC <SEP> - <SEP> DIMENSIONS <SEP> PAGE-1.
<tb>
MASQUE <SEP> ERREUR-= <SEP> Nombre <SEP> de <SEP> bits <SEP> =
<tb> DIMENSIONS <SEP> PAGE <SEP> Justifie
<tb> droite <SEP> dans <SEP> un <SEP> mot <SEP> (C'est <SEP> ä
<tb> dire <SEP> 0003, <SEP> OOOF, <SEP> OOFF <SEP> pour
<tb> DIMENSIONS <SEP> PAGES <SEP> 2,4 <SEP> ou <SEP> 8).
<tb>
TABLE 2 VARIABLES La table 3 suivante définit la structure de chaque entree dans la liste d'erreur.
<Desc/Clms Page number 19>
EMI19.1
<tb>
<tb> Champ <SEP> Contenus <SEP> Multiplets
<tb> 1 <SEP> Drapeaux <SEP> presents <SEP> 2
<tb> 2 <SEP> ID <SEP> Commande <SEP> 1
<tb> 3 <SEP> Adresse <SEP> bloc <SEP> 4
<tb> 4 <SEP> Conflit <SEP> suivant <SEP> 2
<tb> 5 <SEP> Conflit <SEP> précédent <SEP> 2
<tb>
Champ Signification
1 Ce champ contient un ensemble de drapeaux ou de bits qui indiquent les secteurs d'une page qui présentent des erreurs. Les "Mauvais" secteurs sont indiques avec des bits 0 dans les positions du champ et les secteurs avec
EMI19.2
des bits valides sont indiques par des bits l.
2 Ce champ contient le numero de l'unité de commande où la page est situee.
3 Il s'agit de la valeur RBA du premier secteur de la page.
4 Ce champ indique la structure de liste d'erreurs suivante ou entree dans la chaine de conflits.
5 Ce champ indique la structure de liste d'erreurs précédente dans la chaine de conflits.
TABLE 3 STRUCTURE LISTE ERREURS En se reportant maintenant ä la figure 8, on voit que le debut du procédé pour lire une nouvelle page
<Desc/Clms Page number 20>
commence ä l'étape 132. Le procédé général represente à la figure 8 determine si l'antcmemoire a précédemment vu une erreur dans la page ä lire. A l'etape 132, la valeur RBA du secteur desire est mise en condition ET avec le masque de RBA et le résultat est utilisé ä l'etape 134 pour calculer l'index dans la table de donnees mêlées d'erreurs 150. L'index est calculé comme le reste de la réalisation d'une operation modulo 64 lors du decalage ä droite du resultat de l'étape 132 de la valeur du decalage RBA.
Puis, la variable PTR à l'etape 136 est etablie au contenu de la table de donnees mêlées d'erreurs située dans l'index calculé à
EMI20.1
l'etape 134. Si PTR n'est pas etabli ä zero, l'étampe 138 passe alors ä 140 et représente la condition dans laquelle il y a une entrée d'erreurs sur la chaine de conflits. L'étape 140 determine alors si l'indicateur ID de commande est le même que celui de l'unite contenant la page dans laquelle une erreur est apparue.
Si ga n'est pas le cas, l'étape 144 indexe alors le pointeur et avance ensuite par l'entree suivante dans la chaîne de conflits. Si le résultat de l'etape 140 est positif, l'etape 142 determine alors si la valeur RBA desiree correspond ä celle de l'entrée de liste d'erreurs. Si non, il y a passage sur l'entrée suivante de la liste de conflits. La sortie positive de l'etape 138 indique que la page associee n'a pas eu d'erreur avant et donc un essai sera effectuer pour lire la page entière en envoyant une seule commande à l'unite de commande de disques pour lire le nombre des secteurs dans une page. Une determination positive par l'etape 142 indique que la page a eu une erreur avant et qu'elle sera lue secteur par secteur en envoyant plusieurs commandes ä l'unite de commande de disques pour ne lire qu'un secteur ä la fois.
En se reportant maintenant à la figure 9, on voit que par un appel ä BIOS, l'etape 160 permet d'obtenir
<Desc/Clms Page number 21>
DIMENSIONS PAGE, le nombre des secteurs par page et la valeur RBA du secteur du début. Si aucune erreur n'est
EMI21.1
apparue pendant la lecture, l'étape 162 passe alors à 164 qui ensuite conditionne les bits presents, ce qui indique que tous les secteurs sont presents dans la page. C'est ä dire qu'il n'y a pas de mauvais secteur ou d'erreur rencontree pendant la lecture de ce secteur et que des donnees valides sont presentes dans chaque secteur. L'etape 166 conditionne la variable CURPTR pour indiquer l'adresse de la mémoire intermédiaire de donnees 21 dans laquelle un secteur sera lu. Les etapes 168-176 initialisent alors diverses variables comme
EMI21.2
indique.
Puis, un appel est fait ä BIOS et ä l'etape 178, un secteur est lu en association avec la valeur RBA courante. Si aucune erreur n'apparalt, l'etape 180 permet alors de passer ä l'étape 182. Si une erreur apparalt pendant cette lecture, le drapeau present associe ä cette erreur est conditionne ä zéro ä l'étape 184 par mise en condition OU Exclusif avec un masque de bit pour indiquer que l'erreur ou que le secteur était mauvais. L'etape 186 conditionne alors un code d'erreur selon le code de retour que l'on doit ä l'operation de lecture de l'etape 178.
Les étapes 182-188 mettent ä jour la valeur RBA courante, le pointeur courant, le masque de bit et le compte pour indiquer le secteur suivant, puis le procédé se replete ä l'étape 190 jusqu'à ce que le compte soit ramené ä zero. L'etape 192 decide alors si la page qui vient d'être lue est dans la table d'erreur 31.
Si la page n'est pas dans la table d'erreurs, l'etape 192 permet alors de passer ä l'etape 193 (Figure 10) qui obtient un element de la liste sans erreur 154 en etablissant un nouveau pointeur d'erreur. L'etape 194 determine alors si la liste sans erreur étai t vide,
EMI21.3
c'est ä dire si le nouveau pointeur d'erreur est egal ä zero. Si oui, le branchement est alors realise de
<Desc/Clms Page number 22>
l'étape 194 ä l'étape 204, ce qui ramène les bits presents et le code d'erreur. Si la liste sans erreur n'est pas vide, les etapes 196-202 permettent alors d'inserer une nouvelle entree d'erreur dans la table de donnees mêlées d'erreur.
Cette opération est réalisée en etablissant le pointeur sans erreur egal au pointeur sans erreur suivant ä l'étape 186, ce qui etablit le nouveau pointeur d'erreur present egal au bit present correspondant ä l'étape 198, ce qui etablit le nouveau pointeur d'erreur en position suivante selon la valeur obtenue depuis l'index de la table de donnees melees d'erreur et etablit ensuite l'index de données mêlées d'erreur au nouveau pointeur d'erreur ä l'etape 202.
La procédure représentée ä la figure 11 vérifie les erreurs précédentes dans les secteurs requis. Les étapes 206-218 sont identiques aux étapes 118-130 mais varient selon les points d'entree et de sortie. Ainsi, les étapes 118-130, en raison de cette variation, vérifient si les secteurs requis sont dans la page d'antememoire et produisent un resultat positif ä 1 J étape 130 lorsque tous les secteurs sont dans la page. Le résultat négatif indique que tous les secteurs requis ne sont pas dans une page si bien que le systeme d'exploitation doit essayer d'assurer une certaine forme de recuperation d'erreur. D'autre part, les etapes 206-218 sont utilisées pour verifier si les secteurs requis ont été precedemment affectes d'erreurs.
Le résultat positif de l'etape 218 indique que la page presente des erreurs mais que les secteurs requis n t en présentent pas tandis que le resultat negatif de l'etape 218 indique que les secteurs requis presentent des erreurs.
A l'étape 206, la valeur RBA et le masque SECCOUNT sont mis en condition ET et le resultat est emmagasiné dans le compte de décalage variable. L'etape 208 établi t
<Desc/Clms Page number 23>
alors les bits presents égaux au pointeur present décalé sur la droite de la valeur du compte de decalage. L'etape 210 etablit le decalage de masque egal ä DIMENSIONS PAGE moins le nombre des secteurs. L'étampe 212 produit un masque de test en decalant sur la droite le masque d'erreur d'une valeur correspondant au décalage de masque.
Puis, les bits presents sont mis en condition ET avec un masque de test ä l'etape 214 et alors mis en condition OU Exclusif avec le masque de test ä l'etape 216, après quoi l'etape 218 teste les resultats. Cette procedure est avantageuse car elle permet de determiner rapidement stil y a des erreurs dans les secteurs requis sans avoir recours ä des boucles ou ä de multiples chemins de decision. On comprendra aussi peut être mieux la präsente invention en utilisant l'exemple suivant dans lequel on suppose que DIMENSIONS PAGE a 8 secteurs, le secteur 5 de la page (le sixieme secteur) presentait une erreur la dernière fois que la page a été lue et ainsi son bit present correspondant est conditionne ä zéro.
La table 4 donne un exemple de l'execution de la procédure lorsqu'un secteur requis se trouve dans une page qui presente des erreurs mais que le secteur requis n'est pas l'une des erreurs. L'exemple lira deux secteurs en commençant au secteur 3 de la page. La table 5 montre un exemple du deroulement de cette procedure lorsqu'un secteur requis a presente une erreur pendant une lecture précédente. L'exemple lira deux secteurs en commençant au secteur 4 de la page.
EMI23.1
<tb>
<tb>
0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> masque <SEP> erreur
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> masque <SEP> test
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 110 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> drapeaux <SEP> présents
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> etape <SEP> 212
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> dtape <SEP> 214
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> etape <SEP> 216
<tb>
<Desc/Clms Page number 24>
EMI24.1
TABLE 4 PAS D'ERREURS DANS SECTEURS REQUIS
EMI24.2
<tb>
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> masque <SEP> erreur
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> masque <SEP> test
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 101 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> 1 <SEP> drapeau <SEP> x <SEP> présents
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 1 <SEP> 0 <SEP> 1 <SEP> etape <SEP> 212
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> étape <SEP> 214
<tb> 0 <SEP> 0 <SEP> 0 <SEP> 0
<SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 0 <SEP> 1 <SEP> 0 <SEP> étape <SEP> 216
<tb>
TABLE 5 ERREURS DANS SECTEURS REQUIS En se reportant maintenant ä la figure 12, on voit que l'etape 220 resulte d'une determination négative à l'etape 218 (Figure 11) et provoque le conditionnement d'un bit present selon le PTR présent. L'étape 222 établit le compte egal ä DIMENSIONS PAGE, l'etape 224 etablit la valeur CURRBA egale ä RBA, l'étape 226 établit CURPTR égal au pointeur dans la memoire intermédiaire de données et l'étampe 228 établit le masque de bit égal ä un. L'étape 230 détermine alors si le secteur courant avait une erreur avant en mettant en condition OU le bit present et le masque de bit.
Si le
EMI24.3
resultat n'est pas égal à zéro, l'étape 232 permet alors la lecture au moyen d'un appel BIOS, d'un secteur ä la valeur CURRBA. L'étape 234 détermine alors si il y avait une erreur pendant cette lecture. Si oui, l'étape 236 conditionne les drapeaux presents pour indiquer qu'il y avait une erreur et aussi retenir le code d'erreur ä l'etape 238. L'étape 240 et les suivantes, déplacent le secteur suivant en incrémentant la valeur CURRBA ä l'retape 240. Le CURPTR est alors incrément du nombre de multiplets par secteur à l'étape 242 et le masque de bit est décalé sur la gauche de un ä l'etape 244. Le compte est décrémenté à l'étape 246. Lorsqu'il atteint zero, un branchement est établi ä l'étape 204 (Figure 10).
Autrement, l'etape 248 determine alors que
<Desc/Clms Page number 25>
tous les secteurs n'ont pas ete lus et assure donc un rebranchement ä l'étape 230 pour permettre la repetition de l'execution du procédé.
On va maintenant résumer le déroulement des procédures.
Les défauts du milieu sont gérés avec les drapeaux présents dans la structure de pages d'antememoire. Lorsque l'on essaie de lire une page ä partir d'un disque, si une erreur est renvoyee, l'antememoire est restaurée de la maniere suivante : 1. Elle"sauvegarde"le premier secteur de la page.
2. Elle commence la lecture des secteurs dans la mémoire intermediaire de pages, un par un. Chaque fois qu'elle lit un secteur avec succes, elle conditionne un drapeau présent correspondant.
3. Si une erreur est rencontrée pendant la lecture d'un secteur, le drapeau présent pour ce secteur est libéré (conditionné ä 0) et des pointeurs appropriés sont mis ä jour comme si le secteur était lu.
4. Une fois que tous les secteurs de la page ont été lus (un ä la fois), les bits présents sont balayes pour determiner si un ou plusieurs des secteurs requis depuis l'antémémoire est ou sont manquants, c'est ä dire si le bit présent correspondant est établi ä 0. S'il en est ainsi, la dernière erreur reçue pendant la lecture depuis le dispositif, est renvoyée au demandeur.
La procedure est légèrement différente si la page qui correspond ä la demande est déjà dans l'antémérnoire. Ce cas est traité de la manière suivante :
<Desc/Clms Page number 26>
1. Les drapeaux presents sont balayes pour determiner si un ou plusieurs des secteurs requis est ou sont manquants. Si aucun n'est manquant, l'antememoire fonctionne alors d'une maniere normale et les donnees sont renvoyees au demandeur.
2. Si un ou plusieurs secteurs est ou sont manquants, seuls les secteurs qui ont besoin d'être lus depuis la disquette, sont lus. Si aucune erreur n'est rencontree pendant la lecture, les secteurs appropriés sont marques présents dans la page d'antememoire et le traitement se poursuit.
Ce schéma permet à l'antememoire d'avoir des "trous" qui correspondent aux erreurs dans le milieu sans perte de donnees ou par augmentation significative de la complexitg de l'antememoire. 11 permet aussi au Systeme d'exploitation d'essayer de re-executer des operations et de récupérer des données dans une situation d'erreur sans que l'antememoire rende la tâche du Systeme d'exploitation plus difficile.
Lorsque l'antememoire rencontre une erreur, elle determine quel secteur ou quels secteurs de la page présente ou présentent des erreurs et laisse ou laissent des "trous" dans la page qui correspondent aux secteurs presentant des erreurs. Une valeur de 16 bits est aussi produite par le procede de récupération d'erreur et cette valeur est consideree comme les drapeaux présents. S'il y a des bits zero dans ces drapeaux, c'est que la page présente une ou plusieurs erreurs.
Si la page présente des erreurs, 1'antémérnoire determine si cette page a presente des erreurs precedemment. Ceci est assure par des données melees dans une liste d'erreurs avec la valeur RBA de la page
<Desc/Clms Page number 27>
EMI27.1
pour vérifier si cette page se trouve sur la liste. Si cette page n'est pas sur la liste, elle est ajoutee ä la liste. Si cette page a presente des erreurs précédemment, l'une des operations suivantes peut être exécutée: 1. Conserver les drapeaux presents precedents.
2. Remplacer les drapeaux présents par ceux produits
EMI27.2
ä l'instant. 11 s'agit de ce que l'antememoire de logiciel a mis en oeuvre.
3. Mettre en condition ET les deux ensembles de drapeaux presents et retenir le resultat. Ceci implique que si un secteur dans une page a présenté une erreur, il ne sera pas lu ä moins de demande particulière.
4. Mettre en condition OU logique les deux ensembles de drapeaux présents et retenir le rdsultat. Ceci implique que si un secteur dans une page est lu avec succes, l'antémémoire essaiera toujours de le lire.
Si tous les bits du drapeau present sont toujours tous des zeros, l'entree est retiree de (ou au moins n'est pas placee dans) dans la liste d'erreurs. Ceci est assure pour plusieurs raisons. La première est qu'elle permet ä la liste d'erreurs d'etre beaucoup plus
EMI27.3
petite. Et etant donne que le Systeme d'exploitation tend ä retirer l'attribution de pistes entieres lorsqu'il y a generation de defauts de milieux, le Systeme d'exploitation n'essaiera pas en general de lire ces zones.
La seconde raison est que si une page ne comporte pas de bon secteurs, le systeme d'exploitation est alors dans un etat de recuperation d'erreur generale et les performances ne sont pas
<Desc/Clms Page number 28>
critiques. 11 y a aussi quelque chose que l'antememoire pourrait faire avec la page de toute façon pour que l'antememoire ne perde pas d'espace en gardant la trace de cette erreur.
Lorsqu'une requête est présentée ä l'antémémoire et résulte en un manque d'antememoire, le Systeme determine tout d'abord si la page qu'il est sur le point de lire a déjà present des erreurs précédemment. Si la page a déjà presente des erreurs, le système verifie si l'un des secteurs requis a ete indiqué comme errone. Si aucun des secteurs requis ne comporte d'erreurs, les secteurs de la page sont alors lus un ä la fois en sautant le ou les secteurs qui etait erroné ou etaient errones. Ainsi, l'erreur ou les erreurs a ou
EMI28.1
ont ete evite ou evitees.
De nouveaux essais d'erreurs par l'initiateur d'une requête sont permis etant donne que si un secteur requis a presente des erreurs, il sera lu par l'antememoire. Tout ce que cette action pour eviter des erreurs assure, c'est qu'elle permet ä l'antémemoire d'eviter de pre-extraire un ou des secteurs qui a ou ont presente des erreurs sauf si ce ou ces secteurs sont explicitement requis.
Il est évident pour l'homme de l'art que d'autres changements et modifications peuvent être apportes ä l'invention sans sortir de l'esprit et du cadre de celle ci telle que définie dans les revendications ci jointes.