Brevet FR2344093A1 — publié le 19771007

La présente invention a pour objet un système de gestion cohérente des échanges d'informations entre deux niveaux contigus, l'un plus rapide que l'autre, d'une hiérarchie de mémoires et, plus particulièrement entre une mémoire de données du niveau moins rapide et une pluralité de mémoires de données du niveau plus rapide individuellement exploitées par des processeurs distincts. Dans les échanges d'informations entre ces mémoires de données, celle du niveau moins rapide qui sera dite ici par la suite mémoire principale pour simplifier la terminologie alors que chacune des mémoires de données du niveau plus rapide sera dite, pour la mAeme raison, une mémoire tampon, voire un "tampon". Les échanges entre mémoire principale et taions, bilatéraux bien entendu, concernent des informations, ou données, dont partie est modifiable. Lorsqu'il existe en plusieurs tampons des copies d'une même donnée modifiable provenant de la mémoire principale, ces copies peuvent se trouver modifiées indépendamment l'une de l'autre. Sans plus, alors, il y a danger certain d'incohérence. En fait, cependant, on peut distinguer trois catégories d'informations :- les données concernant les programmes, inmodifiables et ne-pouvant donner lieu i incohérence ; - des données modifiables mais ne pouvant appartenir qu'd une seule tâche parmi la pluralité de tâches que peut exécuter l'équipement complet ; elles ne peuvent donc donner lieu à incohérence tant que la tâche reste active sur le même processeur ; - des données qui sont au contraire partageables et qui peuvent donc être exploitées en des tâches diverses ; elles peuvent donner lieu à incohérence i tout instant. Les premières données modifiables citées seront ici dites locales: les secondes, "globales". Ces catégories d'informations sont tou tefois indiscernables au niveau moins rapide. Elles peuvent l'être à un degré plus ou moins précis, au niveau plus rapide car un processeur d'instructions pourra savoir quelles sont les informations de caractère global selon les instructions qu'il exécutera pour les appeler et les utiliser et, comme il discrimine les informations de programme, il pourra donc, s'il distingue les inrormations globales, discriminer alors les informations locales, à leur appel et leur exploitation tout au moins. On a proposé de nombreux systèmes pour assurer la gestion cohdrente des migrations d'informations entre niveaux contigus agencés comme susdit, en exploitant à des degrés divers et en des combinaisons variées des repérages systématiques des migrations, des recopies systématiques, immédiates ou différées, des informa- tions modifiées avec recherches également systématiques de la pré- sence des données dans les tampons où elles peuvent exister sous leur forme première ou sous forme modifiée.Toutefois ces systèmes ont pour préoccupation essentielle d'assurer la cohérence dans des équipements de traitement de données à programmes multiples hautement concurrents entre eux et y préservant une efficacité globale la moins réduite possible, à savoir une réduction faible des taux de succès des tampons en lecture (tout au moins) et un moindre ralentissement dans ltexécution des tâches i ce niveau. En contrepartie naturelle, de tels systèmes sont coûteux en matériel et, pour certains, introduisent une complexité accrue dans la gestion. Le but de l'invention est, au contraire, de prévoir un procédé de gestion cohérente particulièrement économique et efficace pour des systèmes à faible compétitivité des programmes et(ou) relati veinent faible capacité individuelle des tampons et(ou) admettant un certain taux d'insuccès dans les accès aux données, tant en écriture qu'en lecture, de ces tampons. Ce procédé a recours i diverses remarques et notions de la pratique courante, de laquelle, de plus, doit se retenir l'orga- nisation de la gestion des mouvements en mémoires de données par des circuits de gestion autonome de ces mémoires, cette gestion ayant aussi recours, le plus souvent, à des répertoires de mots d'état d'emplacements adressés en ces mémoires et gérés par de tels circuits:: On sait par exemple que lorsqu'une mémoire de données travaille en coopération avec plusieurs- processeurs exécutant des taches distinctes, ce qui est le cas pour la mémoire "principale" susdéfinie, l'un de ces processeurs peut, quand de besoin, fermer un verrou (loch) sur une partie de cette mémoire dont il entend ainsi se réserver l'usage pendant le temps qu'exige le déroulement de son propre programme, en une section critique tout au moins. Pendant l'application de ce verrou, si le logiciel de l'équipement est correctement établi, aucun autre des processeurs ne pourra accéder aux informations de la partie de mémoire ainsi verrouillée. On sait aussi que dans les algorithmes des programmes des tâches, en phases critiques, celles qui font justement appel à des données de caractère global, l'exploitation simple du matériel a recours généralement au type d'instruction bien connu que l'on peut dénommer TS, de l'anglais Test & Set. Ce type d'instruction assure la lecture et la modification d'une donnée d'une façon indivisible en soi.Dans un programme correctement rédigé, tout accès de lecture et d'écriture en mémoire principale i une donnée partageable est précédé d'une instruction de ce type TS qui, si la section de mémoire adressée n'est pas verrouillée, y place le verrou sur lequel il opère, à savoir un multiplet (en anglais, "byte") définissant la section de mémoire dont le processeur entend ainsi se réserver l'accès en exclusion d'accès des autres processeurs à ladite section. On sait également qu'en une mémoire rapide, une "page" de données peut être invalidée en y adjoignant un indicateur approprié ou, d'une façon plus simple, en repérant l'invalidation par changement de valeur d'un des bits du mot d'état correspondant i cette "page" dans le registre correspondant du répertoire de sots d'état usuellement associé aux circuits de gestion de ladite mémoire re.Dans le présent exposé, on désigne par "page, tout groupe de données faisant en soi l'objet d'un tel mot d'état, 8me si la mémoire n'est pas "paginée" (la pagination étant toutefois la pré- sentation la plus courante d'une telle mémoire). On sait enfin aucun processeur qui termine l'exécution d'une tâche procède i son acquittement et peut alors engendrer un signal d'acquittement. Un tel signal est couranient utilisé en des systèmes de traitement de données pour la régie de diverses opérations, de transfert de données notamment. Selon la présente invention, la cohérence est assurée du fait que, d'une part, toute exécution d'une instruction de type TS par un processeur entraîne l'invalidation d'au moins toutes les données globales présentes dans la mémoire-tampon associée A ce processeur et que, d'autre part et complémentairement, toute exécution d'un acquittement de tâche entratne l'invalidation d'au moins toutes les données locales et globales présentes en cette mémoire. St lors du chargement de la mémoire-tampon, le processeur a repéré et indexé les catégories d'informations:- instructions, données modifiables locales et données modifiables globales, ces invalidations pourront, de préférence, Aetre effectivement sélectives. Si, au contraire, aucun repérage et donc aucun indexage n'a eu lieu au chargement, ces invalidations affecteront la totalité des informations, ce qui pourra demeurer acceptable si la capacité du tampon n'est pas trop grande. D'un autre point de vue, ce procédé est d'exploitation#di- recte lorsque chaque modification de donnée dans le tampon du niveau plus rapide concerné est immédiatement recopiée dans la section de la mémoire principale objet du verrouillage. Ainsi ladite section est à jour lorsque le verrou est ultérieurement levé. Si toutefois, on estime désirable de retarder la mise à Jour de cette section de mémoire principale jusqu tri chaque temps de levée de verrou et(ou) chaque acquittement de tâche ou chaque changement de contexte dans les registres de travail du processeur, il sera alors nécessaire de recourir à un artifice déjà utilisé dans certains des procédés antérieurs de maintien de la cohérence, à savoir l'association a toute donnée qui a été efrec- tivement modifiée dans le tampon d'un bit de repérage de la condition modifiée de la donnée. Ce bit sera, de préférence, porté dans le mot d'état du répertoire associé aux circuits de gestion de la mémoire-tampon.Ainsi, l'opération de mise à jour ne portera que sur les données réellement modifiées d'où un double avantage:- d'une part, une réduction du nombre des cycles de reécriture dans la mémoire principale ; d'autre part, une protection contre un danger d'incohérence car des données qui n'ont pas été modifiées par le processeur concerné peuvent l'avoir été par un autre processeur qui les aurait antérieurement acquises avant le verrouillage. Pour exposer l'invention plus en détail, on se réfère à la figure unique jointe qui schématise à un degré suffisant une organisation de système de gestion cohérente des migrations d'in- formations entre deux niveaux contigus (i+l) et (i) d'une hiérarchie de mémoire dans le cas où le niveau (i) est le niveau plus rapide de cette hiérarchie. On a illustrativement indiqué que le niveau moins rapide (i+l > pouvait aussi échanger des informations avec un niveau plus lent (i+2) non figuré car #'entrant pas dans le cadre de l'invention. Le niveau (i+l) ntest représenté que par une seule unité de mémoire, BS, qui est dite "mémoire principale" dans le présent exposé. On doit comprendre qu'il peut exister au niveau (i+l) plusieurs unités de mémoire pouvant échanger leurs informations avec le niveau (i+2). C'est pourquoi on a indiqué en ce qu'on doit comprendre comme faisant partie d'un interface entre (i+l) et (i+2), trois bus, à savoir AB, bus dladresrses, DB, bus de données auxquels on a ajouté pour une définition plus facile, le bus TSL, ligne utilisée dans l'exécution de l'instruction TS ayant les effets ci-dessus rappelés. Chaque bus est bidirectionnel. Le niveau (i) doit se comprendre comme comprenant plusieurs de ces unités de mémoire qui sont dites ici des "tampons" pour ce que chacune d'elles est exploitée par un processeur d'instructions@ Les trois mêmes bus AD, BD et TSL se retrouvent donc dans l'interface entre (i+l) et (i). Le schéma ne montre, au niveau (i) qu'une seule de ces mémoires-tampons, la mémoire Bk exploitée par un processeur d'instructions ssIk et gérée par des circuits de gestion CGBk auxquels est associé un répertoire de mots d'état RPk. Le registre d'adresse de Bk est indiqué en RA, son registre d'écriture-lecture, en REL. La mémoire Bk est divisée en pages, de Pi a Pm.Chaque page contient n informations, de IF1 à IFh. Le répertoire, dont le registre d'adresse est indiqué en AD et le registre d'écriturelecture en EL, comprend sous sa forme la plus simple autant de registres, de Ri à Rm, que de pages en mémoire Bk. Chaque registre de mot d'état peut, si désiré, être subdivisé en autant d'emplacements distincts que d'informations en chaque page.Chaque mot d'état comprend, outre une adresse ADR qui permet d'établir une correspondance entre au moins le contenu de la page P i laquelle ce mot état se réfère et son adresse physique en mémoire principale BJ (le plus souvent, ADR permet aussi d'établir une correspondance entre cette adresse physique et une adresse de donnée de programme AP, exploitée en/Ik, sauf à prévoir une conversion de AP à ADR dans la logique des circuits de gestion ou à tout autre emplacement approprié tel qu'un interface > , des bits ou codes d'état qui, pour la mise en pratique de l'invention, seront définis plus loin. L'organisation des circuits de gestion CGBk peut, pour ltex- posé, se résumer en disant qu'elle consiste en une micromachine assurant les quatre fonctions logiques repérées sur le schéma, à savoir la gestion des échanges avec le niveau contigu moins rapide, L~G. EX. (i+l), la logique de gestion des écritures-lectures en Bk, soit G.Bk, la logique de gestion du répertoire, soit IFG. RPk, une logique, LOG.EX.#IK, de gestion des échanges avec le processeur d'instructions ~Ik. La "mémoire principale" Bj est gérée similairement par des circuits de gestion assurant les fonctions logiques de gestion d'échanges avec le niveau (i), soit L#G.EX.(i), de gestion d'é- changes avec le niveau (i+2), lorsque ce dernier existe, soit L~G.EX.(i+2), de gestion de la mémoire proprement dite L~G.BJ, qui commande les écritures et lectures par le registre de lecture-écriture REL et le registre d'adresse RA de Bj, et de gestion d'un répertoire de mots d'état RPJ. Normalement, la mémoire Bj n'a pas besoin d'être paginée > bien qu'il soit souvent avantageux qu'elle soit ainsi organisée pour les transferts d'informations dans une hiérarchie de mémoires cohérente. Le schéma ne montre donc qu'une indication que la mémoire Bj peut, évolutivement et selon les besoins, comporter des "sections" de S1 à Sx (au maximum), le répertoire RPS comportant alors le nombre de registres, de RI à Rx, correspondant i cette subdivision maximale de B. Un registre de RPX est alors chargé, quand de besoin, d'une adresse AS de section créée en BS, éventuellement d'une adresse de mémoire-tampon repérée ABi, permettant aux circuits de gestion de connaître où se trouve l'information de ladite section dans le niveau (i), de bits d'état ET qui ne seront pas détaillés car n' in- tervenant pas dans l'exposé de l'invention, et d'un indice ou code LK qui sera mis à 1 pour l'application d'un verrou sur la section S définie par l'adresse AS lorsque le processeur d'adresse ABi aura exécuté une instruction de type TS. Ce verrou sera levé et le code LK remis à zéro par une instruction de type RS (de l'angLais RESET) émise par le processeur d'instructions, si cette instruction existe en soi dans le programme, sinon par une instruction de re-écriture du code pris pour verrou tel que déterminé par #I. Ce code pourra avoir été écrit en LK. Lorsque ~Ik ordonne un chargement de données dans Bk, son unité logique U6G.K peut associer i l'adresse AP qu'il dirige par la liaison a sur les circuits CGBk des indicateurs qui définissent la nature de la donnée concernée :-programme P, locale L, globale G, dans son registre RAK. Ces indicateurs sont "examinés" par la logique L~G.RPk qui en reproduit un code correspondant dans le registre R concerné du répertoire RPk.Bien que, sur le schéma, on ait indiqué, tant en RAK qu'en tout registre de mot d'état R du répertoire, trois cases distinctes pour P, L et G, il est bien évident qu'un code d deux bits suffit pour une telle discrimination, par exemple :- P = O O L=lO G = I 1, le premier bit marque le caractère non modifiable (0) ou modifiable (I) de l'information, le second bit marque alors le caractère local (o) ou global (î) de l'information modifiable. Si le processeur ne peut assurer une discrimination des informations de cette nature, ces indices sont bien évidemment absents des mots d'état du répertoire. En chaque mémoire d'une hiérarchie, on doit pouvoir invalider une donnée, une section ou une "pagel'. Dans le cas de l'invention, seule l'invalidation de donnes en mémoires-tampons est à consi dérer. C'est pourquoi, on a indiqué dans les registres du répertoire RPk une case repérée V, dont la condition sera assurée å partir de la logique de gestion. Si, par exemple, le bit V est à zéro, la donnée est valide, si ce bit est à 1, la donnée est invalidée. L'invalidation est repérée par page dans cet exemple, elle pourrait être définie information IF par information IF, auquel cas il y aurait autant de cases V, adressées de 1 à n que d'informations IF par page. On a également indiqué, dans les registres RPk la possibilité d'existence d'une case repérée M, pour "odirié". Elle peut indiquer si l'information de la page a été modifiée (bit M à 1) ou ne l'a pas été (bit M i O). En rats, pour l'exploitation de cet indice, il conviendra que, dans chaque registre R, il y ait autant de cases M que d'informations IF, adressées de 1 à n, par page. Un tel indice sera alors utilisé en cas de recopie différée pour ne retransmettre vers Bj que les informations réellement modifiées en Bk-Il est inutile dans le processus, qui sera plus courant dans la mise en pratique de l'invention, en lequel chaque information modifiée sera recopiée en Bk à l'instant de sa modification. Outre sa logique L~G.K et son registre d'adresse RAK, est indiquée en (MT) dans le processeur jdlk une mémoire de travail, constituée de façon classique par un certain nombre de registres emmagasinant au fur et à mesure les contextes de tâches prélevés en Bk. Entre l'opérateur-processeur ~IK et les circuits CGBk sont indiquées les liaisons suivantes::- une liaison d, bilatérale pour les transferts de contexte de Bk à (mut) et réciproquement, une liaison a pour ltenvoi de l'adresse AP, éventuellement assortie, comme dit, des indices PLG selon le code susdéfini, et des commandes k comprenant, outre des commandes générales c qui ne seront pas définies car extérieures au cadre de l'invention, une commande d'invalidation, identifiée v, une commande éventuelle de l'indice M, soit m, et une commande ts pour l'exécution de l'instruction de type TS définiesen début d'exposé.L'activation de ts déclenchera, en tour, l'activation de la liaison TSL vers les circuits de gestion de la mémoire Bj pour lecture å l'adresse définie par AP alors transmise à partir de RAK et mise du verrou sur la section adressée en Bj si elle n'était pas déJb verrouillée. En meme temps alors, la logique 1$G. K déclenche, selon une caractéristique de l'invention, la liaison v de demande d'invalidation des données présentes en Bk dont le code PLG est de valeur II si cet indice est présent dans les mots d'état du répertoire.La sélection est assurée par une exploration systèmatique des registres de RPk avec décodage par le décodeur DEC du code PLG à chaque pas de cette exploration, d'où le placement de l'indice V i "î" dans ceux des mots d'état dont le code PLG est de valeur 111111. Cette organisation n'est pas représentée en son détail ais, de façon évidente en soi, peut consister un microprogramme se déroulant en \~G.K déroulant les adresses de pages en Bk ou des adresses permettant par adressage associatif en AD de RPk, l'appel successif des contenus des registres R en EL auquel le décodeur DEC doit se comprendre comice connecté alors que le maintien activé de la liaison v assure l'introduction dans l'emplacement V d'un bit elle chaque fois que la sortie de DEC indique la présence du code "11" dans le registre. En l'absence du code PLG dans l'équipement, la case V est impérativement mise à 1 en tous# les registres au fur et à mesure de la susdite exploration. En cas d'une recopie différée, le processus d'invalidation sus-décrit doit être précédé de, ou concomitant à la recopie en Bj de toutes les informations repérées par le code "11" si l'in- dice PLG est utilisé dans l'équipement. Cette recopie est réduite à celles des informations présentant également l'indice M k 1, si ce dernier est aussi utilisé:- il suffit alors de prendre en intersection (opération logique ET) la sortie de DEC et la sortie de case M de l'informations au ours de l'exploration susdite. Si le code PLG n'est pas utilisé mais que l'indice M le soit, c'est ce seul indice qui provoquera la re-écriture en Bj au cours de l'exploration de RPk avant ou simultanément à l'invalidation. Il est bien évident qu'après toute instruction TS, tout appel du programme qui pourra ensuite être émis par ~Ik et concernant une information invalidée provoquera alors le transfert en Bk de l'information adressée recopiée de BJ. Si elle a été antérieurement modifiée, la mémoire-tampon Bk, et donc le processeur, recevra la dernière version de cette information existant dans le système complet. Toute nouvelle écriture en Bk supprime alors, comme usuel, l'invalidation dans le registre de RPk correspondant à l'adresse de Bk en laquelle est écrite cette nouvelle information. Tout changement de tâche, matérialisé soit par un acquittement, activation de la liaison acq par I~G.K vers CGBk, ou par un changement de contexte en (MT) si la condition acq n'est pas envoyée à CGBk, provoquera l'activation de la liaison v. Le même processus d'exploration du répertoire que ci-dessus se renouve#ra mais avec, lorsqu'il existe, une modification de la sortie du décodeur DEC (ou l'activation simultanée de deux sorties de DEC):il suffira, dans le code PLG lorsqu'existant, que le premier bit soit A nlt, que le second soit à "O" ou à "1". Au microprogramme. susdit exécuté par I~G.K pour les invalidations, peut être substitué, dans CGBk, logique L~G.RPk, un automate déroulant les adresses successives des registres de RPk sitôt la liaison v (de demande d'invalidation, en fait) activée par L~G.K. A la reprise d'une nouvelle tâche par le processeur, ou d'une exécution d'un programme sur un nouveau contexte, toute donnée invalidée sera alors obligatoirement rappelée de Bj, comme dans le cas précédent, Un tel système Simple assure donc la cohérence recherchée sans nécessiter de matériel supplémentaire appréciable. REVENDICATIONS 1. - Système de gestion cohérente d'une hiérarchie de mS- moires à deux niveaux contigus dont le moins rapide incorpore une mémoire échangeant des données avec plusieurs mémoires du niveau plus rapide, chacune gérée de façon autonome par une organisation de gestion et chacune servant de tampon pour un processeur d'insu tructions qui, avant toute accès en cette mémoire d'une donnée modifiable partageable, exécute une instruction de type TS pour placer un verrou sur une section adressée en cette instruction de la mémoire du niveau moins rapide et qui, å chaque acquittement de tâche et(ou) changement de contexte de tâche, active une sortie sige*ficative de cette condition, système en lequel outre les données modifiables partageables, donc globales, il existe des données immodifiables de programme et des données modifiables locales à des tâchesj système en lequel, de plus, chaque organisation de gestion de mémoire du niveau plus rapide incorpore un répertoire de mots d'état des contenus d'emplacements prédéterminés de la mémoire, et système également en lequel chaque organisation de gestion d'une mémoire incorpore des moyens d'invalidation sélective des données en mémoire, caractérisé en ce qu'il incorpore des moyens activés par chaque exécution d'une instruction de type TS par un processeur pour provoquer dans la mémoire du niveau plus rapide qu'il exploite l'invalidation d'au moins les données globales en cette mémoire et des moyens activés par chaque acquittement et(ou) changement de contexte de taches pour provoquer dans ladite mémoire l'invalidation d'au moins les données locales et(ou) globales en cette mémoire. 2. - Système selon la revendication 1, caractérisé en ce que ces moyens assurent l'activation d'une exploration séquentelle des mots d'état en ce répertoire et la commutation à l'état "invalide" des indices de validité des informations concernées. 3. - Système selon la revendication 2, caractérisé en ce que ces mots d'état ne comportent aucun repère de nature immodifiable et modifiable des données auxquels ils se rapportent et que 1'in- validation est affichée en chacun de ces mots. 4. - Système selon la revendication 2, caractérisé en ce que le processeur dispose de moyens pour repérer la nature Immodi- fiable, modifiable locale et modifiable globale de chacune des données, l'organisation de gestion de la mémoire dispose de moyens d'écriture de ces repères dans les mots dudit répertoire et en ce que des moyens de décodage de ces repères assurent, au cours de cette exploration, la sélectivité de l'invalidation affichée en ces mots d'état. 5. - Système selon la revendication 2, caractérisé en ce que ladite exploration est commandée par le déroulement d'un microprogramme de modification d'adresses dans le processeur. 6. - Système selon la revendication 2, caractérisé en ce que ladite exploration est commandée par un automate local de l'orga- nisation de gestion déclenché par la demande d'invalidation en provenance du processeur. 7. - Système selon la revendication 2, caractérisé en ce qu taur cours de cette exploration, et lorsque le processeur n'a pas ordonné au coup par coup la recopie immédiate des données qu t il modifie dans la mémoire du niveau moins rapide, des moyens assurent ladite recopie préalablement ou concomitamment à ladite invalidation. 8. - Système selon la revendication 7, caractérisé en ce que des moyens placent un repère de modification de donnée au moins dans le mot d'état concerné du répertoire à l'occurrence d'une modification de cette donnée par le processeur.