FR 2072028 A1 19710924 FR 7046394 A 19701223 70 46394 2072028 L'invention concerne un procédé d'adressage dans un ensemble de mémoires constitué de mémoires ayant des - temps d'accès différents alors que dans les mémoires des régions peuvent être occupées par des parties de programme et des données, appelés "domaines de travail", 5 ou "stacks" (empilements) dans le cas des groupes de domaines de travail jointes qui sont identifiables, à l'aide;âLune adresse de base de domaine de travail ou de stacks, c ' est-à-^dire • l'adresse -qui donne ,l'emplacement du domaine de travail ou d'un stack dans un ëhsemble de mémoires, alors que les domaines de travail ou les stacks sont liés hiérarchiquement sui-10 vant une structure d'arbre, .alors que pour l'identification des lignes hiérarchiques, de l'extérieur vers la racine de' l'arbre, on prévoit des adresses de référence alors que les domaines ou les stacks sont- dépla-çables d'une mémoire vers une autre mémoire. Pour l'obtention de vitesses de traitement d'infor-15 mation élevées une calculatrice électronique doit comporter une mémoire travaillant rapidement c'est-à-dire une mémoire à temps d'accès court. De telles mémoires sont coûteuses et «'est pourquoi la grandeur d'une telle mémoire dans une calculatrice est limitée. Ces mémoires à temps d'accès court également appelées "mémoires dé travail" de la calculatrice 20 ne suffisent cependant pas. ïïn Système de calculatrice comporte également à côté de mémoire de travail rapide d'autres mémoires (dénommées "mémoires d'arrière-plan") qui ont un temps d'accès plus long mais qui sont moins coûteuses.et qui ont une grande capacité d'emmagasinage. Il peut s'agir de mémoires à tambour, de mémoires à noyaux lentes, de mémoires à disques 25 etc. Toutes ces mémoires, dans un système dé calculatrice, sont dénommées "ensemble de mémoires". Pour atteindre une haute vitesse de travails on fait c sorte dans des systèmes de ce genre que pendant le transport d'infor-• ï;..- '.• a des mémoires d'arrière-plan ou vers celles-ci le processeur ^ .lié GG CÛ.XOU.1 j pG _".ûL-.iU.G Un prOCGSSUS sans v-euarâ, c'est-à-dire à l'exécution d'un programme ou d'une partie de programme donnée sur des variables d'entrée déterminées. Il faut cependant qu'un tel programme ou partie de pre^ranaae &"?ec les données à traiter se trouve déjà dans la mémoire de travail d'où il doit pouvoir L'invention concerne un procédé d'adressage dans un système de mémoires, ce procédé convenant particulièrement lors qu'un nombre de processus précités, qui font partie d'un système hiérarchique, doivent se dérouler simultanément à l'intérieur d'une calcula-40 trice. «ad original1 70 46394 2072028 L'ordre de succession dans lequel les instructions d'un programme sont effectuées est en- général.entièrement*déterminé - par le programme lui-mimé et par les données1 d'entrée? -les données de sortie le sont également. Le rythree auquëtt' déroule lë- programme est 5 cependant influençable pair des circonstances secondaires* telaïque le fait que des données ne soient pas présentes ëîi temps voulu,- ce'S 'données devant venir de la mémoire' d'arrière-plan, bu interruption' au profit d'un autre processus à plris grande priorité,, *■" î " "-ar" "âmuifanei'ijë :de deux 'procesË-uSs "il -y. a lieu d'en-10 tendre le fait que pendant'un'intervalle de simultanéité, les cLeux processus sont mis en route mais non encoré tërmïnésrv-Si-' l'un- deé "processus est interrompu momentanément, cela n' enîèVe 'rien à -la simultanéité. Une calculatrice' qui ne -comporte qii'Uh -processeur central peut donc traiter un certain nombre de processus, aussi bien 15 qu'une calculatrice comportant plusieurs processeurs. Le fait que les relations entré.les processus5 peuvent être représentées par un système hiérarchique peut être interprêté de diverses façons. L®interprétation la plus larges applicable ici, est 20 que pour chaque processus donné A il n'existe qu'un seul autre processus B qui fournit la combinaison de données' d'entrée et le programme qui caractérise A. -. . . . , • ' 'Dans 4e nombreu:: cas, A sera démarré par B, cependant dans le présent cas eeïà ne pas indispensable. - ' 25 Dans ces circonstances, la liaison entre les proces sus peut être comparée avec celle des blocs nichés dans"un language structure par blocs tels que Algel *60; PLI5 Algel '68. Sur la figo 10 on a représenté la façon dont an tel programme à structure par blocs nichés est rèprésentable. "Il jr s des 50 blocs9 c'est-à-dire dès parties de programme9 B"°g0 B'®y "et B®^ et 0^2» C°^. Le "bloc contient' tous les autres bloôs» B°g contient le bloc 3%, B°^ st 0°^ contient les blocs C0^" st C°^. Par "comprendre", il y a lieu entendra au» il existe une liaison' "6i£"ûtte" relation subordonnée entre us bloc qui est contenu (hïoo 'inférieur) et le bloc qui '5 BAD ORIGINAL Tft «ooi 5 2072028 70 46394 superflues dès que toutes les instructions du bloc ont été exécutées; les domaines de- travail réservés sont alors à nouveau libérés). Le stack (où empilement) constitue pour un programme simple une méthode simple pour réservér les domaines de travail de mémoires précitées ou pour les. 5 libérer. Lorsqu'un nouveau bloc est utilisé, dans lequel^ £ variables sont déclarées, qui couvrent chacune une cellule de mémoires, An réserve d'abord en premier lieu n cellules de mémoire pour ces variables et encore un nombre fixe c pour des données auxiliaires qui sont nécessaires pour tenir à jour une table de display (voir plus loin), et le stack lui-même. 10 La fig. 2 représente un exemple d'une structure de stack. Il y a des domaines de travail , Bg et B^ comportant les parties n^ et c^ telles que définies ci-dessus. Il y a un sommet du pointeur de stack (TSP) qui indique la limite entre une région de mémoire de travail liée, libre, et la région liée qui est réservée par le programme. Si un 15 nouveàÂ^domaine de travail B^ est engendré, celui-ci peut être alloué au stack par l'élévation du soiimet du pointeur de stack TSP d'une valeur n^ + c^. Tant qu'il existe un domaine de travail, il est évident que des positions de mémoires physiques seront occupées par des variables qui sont déclarées dans chacun des blocs d'un programme à structure par blocs. Ces 20 positions physiques des variables de différents blocs sont différe*tes de cas en cas, car ceci dépend justement de l'occupation par des domaines de travail de domaines libres ou libérés dans la mémoire de travail de la calculatrice. Les parties d'adresses des instructions de programme du programme lui-même sont cependant,inchangeables, tant que le programme 25 n'est pas de nouveau compilé. Pour faire correspondre ces deux faits, on utilise des adresses doubles dans les instructions de programme, la première partie de l'adresse donne le niveau de bloc ("lexigraphic level" _iL), cette partie est utilisée pour sélectionner dans une table (appelée display), une position qui est spécifique au bloc déclarant. A cette po-30 sition se trouve l'adresse de base de la partie (domaine de travail) du stack où se trouvent les variables déclarées dans ce bloc. En additionnant la deuxième partie d'adresse, on obtient alors la position de la variable demandée. La fig. 3 représente une table de display DT avec 35 stack ST correspondant. Le stack ST a des domaines de travail B^, B2 et B^ avec comme adresse de base BA^, Big et BA^ des parties où se trouvent les variables. Ces adresses de base sont emmagasinées dans le display aux positions 1, 2 et 3. Les écarts qui se présentent par rapport à l'exécution de l'appèl de procédure dans la description précédente ne sont 40 pas important*?, pour cette explication. 70 46394 4 2072028 L'organisation du stack telle qu'indiquée ci-dessus fonctionne par suite du fait que dans un programme réalisé séquentiellement il n'y a jamais, plus d'un bloc intérieur qui est actif simultanément, c'est-à-dire qu'ici des instructions provenant du premier bloc in-5 térieur sont exécutées tandis qu'un ^utre bloc intérieur est démarré et également achevé. L'état décrit en dernier lieu que produit avec le programme exécuté purement séquentiellement ne se présente pas, mais se produit si l'on veut faire sa produire simultanément an ou quelques sub-10 blocs d'un programme comme processus séparé. Pour rendre œei clair, on peut se référer à l'exemple de la fig. 1 * En supposant que la structure du programme, de structure de bloc est telle que tandis que le bloc B*g est exécuté indépendamment, le processus qui exécute B0^ peut aller avec l'exécution de B'g. A un moment donné B*^ et C°^ peuvent être simultané— 15 ment actifs et ces deux blocs doivent pouvoir exécuter des opérations sur des variables qui sont déclarées par et éventuellement encore des blocs extérieurs de Ba^. En d'autre mots, B"^ et des blocs extérieurs 1 devraient se présenter simultanément dans les stacks pour lea deux processus. Sur la fig. 4» on a représenté cette situation telle qu'elle peut 20 se présenter en pratique. est le display et ST^ est le stack du premier processus, DTg es't Ie display et STg est le stack du deuxième processus. Les instructions du domaine de travail B^ peuvent atteindre des variables de B^ lui—mime et également Bg de la façon qui est tout à fait analogue aux méthodes pour un programme entièrement séquentiel. Les 25 variables de B^ et de blocs le comportant sont trouvées dans un autre stack qui peut être atteint en faisant renvoyer dans le display DT^ du deuxième processus vers la base de B^ dans le premier stack ST^. Bans le cas de la fig. 4 la hiérarchie de processus n'a que deux niveaux (voir B^ et dans les différents stacks). En ap-30 pliquant de façon répétée le même principe , le procédé peut cependant être appliqué à une hiérarchie de processus nichés à n'importe quelle profondeur et à large embranchement alors que chaque processus a son stack propre et que les stacks sont reliés entre eux suivant une structure d'arbre réelle, arbitraire, c'est-à-dire qu'à partir de chaque stack, 35 il n'y a qu'un trajet vers la "racine" de l'arbre, le stack de ce processus qui a engendré tout les autres, (voir plus loin en regard de la fig. 5)» Il est également connu que cette structure n'est pas seulement utilisée pour des parties d'un programme d'utilisateur réali-40 sables séparément mais que tous les programmes d'utilisateur peuvent être BAD ORIGINAL 70 46394 5 2072028 compris comme processus, qui sont hiérarchiquement inférieurs au système opérant (des library routines entre autres peuvent être comprises comme des variables ou des fonctions qui sont déclarées dans l'operating system). Avec l'opêrating systèm lui-même on peut construire hierarchique-5 ment en quelques niveaux, selon les mêmes principes. Les coniidérations précitées précèdent la question que la mémoire de travail peut être trop petite (et ce suivant des considérations économiques, telles que l'on a déjà dit dans le préambule) pour comprendre simultanément tous les stacks et également conserver la possi-10 bilité que des stacks grandissent de façon non prévisible (par exemple pour le hichement profond ou pour'appèl de procédure fortement récursif). Il est plus économique d'avoir à chaque moment seulement ces données dans la mémoire de travail qui sont traitées au moment même, ou qui respectivement se trouvënt sous les premières qui peuvent 15 venir ensuite. Cela signifie que si de nombreux processus fonctionnent en parallèle des stacks pour seulement une petite partie de ces processus peuvent se trouver dans la mémoire de travail. Lorsqu'un nouveau stack est appelé celui-ci sera de préférence placé en un endroit 20 qui par hasard, me trouvé libre à ce moment dans la mémoire de travail. La mise en place d'un stack en ion tel emplacement arbitraire est appelé "relogement dynamique". Une :jaéthode connue pour satisfaire à cette exigence de relogement dynamique des stacks est constituée en ce que dès qu'un processus est engendré, le stack correspondant reçoit un nombre 25 fixe (numéro de stack) qui est conservé pour toute l'existence de ce stack. Le numéro correspond à une position dans une liste (stack vector array) et à cette position l'adresse de base du stack est conservée lors de chaque déplacement de celui-ci. La fig. 5 représente ceci schématiquement. En suppo-30 sant qu'il y a des stacks 13, 41?» 38 et 1. Ces stacks forment un trajet dans l'arbre précité allant de l'extérieur dans ce cas numéro de stack 13 par 417-38 vers le nombre de stacks de racine 1Leur revoi de l'extérieur vers l'intérieur né së fait pas par les adresses de base des stacks eux-mêmes, en effet celles-ci varient toujours lors des reloge-35 ments, mais par le stack vector array VA. Les" numéros de stack correspondent en ordre dé succession ("13, 417» 3&» 1) avec des positions successives dans VA. A ces positions se trouvent alors les adresses de base-physiques BA„, BA,.,,,, BA,Q et BA^ "des statsks. ,Si une adresse de base varie, celle-ci 13» 417 58 1 seule doit être tenue à jour dans le staick vector array VA toujours pré-40 sent pendant un processus, dans la mémoire de travail. Il ne doit pas se 6 70 46394 2072028 produire de modifications dans le stack à partir .duquel on renvoie à un des niveaux vers le stack situé â 11 int£s& Bien que la méthode précitée offre une solution par rapport au relogement dynamique, elle peut introduire des retards si l'on 5 fie prend pas d'autre mesure lors du ..réglage du passage. de la mémoire d'arrière plan vers la mémoire de travail des stacks nécessaires pour le prcessus envisagé (stack propre et les stacks ss trouvant hiérarchiquement au-dessus de celui-ci ou dans en d'autres mots les stacks qui se trouvent dans une. branche plus près de la racine). Cette difficulté est décrite 10 ci-après. Lors de la reprise d'un processus qui ,a été momentanément interrompu, le risque moindre po.ur une nouvelle interruption avant la prise d'abord des stacks horsïde la méthode d'arrière-plan existe si les stacks de ce processus ainsi que tous les precessus se trouvant 15 hiérarchiquement au-dessus de celui«ci. se trouvent la mémoire de travail. (On peut imaginer un raffinement avec lequel le seul de ces stacks est connu qui ne sont pas adressés momentanément, de sorte qu'il ne sont momentanément pas nécessairesdans la mémoire de travail). Il est donc désirable pour le système opérant, avant 20 le démarrage d'un processus que l'on puisse examiner si en effet tous les stacks nécessaires (donc en général tous les stacks hiérarchiques) se trouvent déjà la mémoire de travail, de façon que si ce n'est pas le cas, le rédémarrage peut être retardé au profit d'ion autre processus, jusqu'à ce que tous les stacks se trouvent dans la mémoire. 25 Le système opérant devra disposer pour pouvoir réa liser sa tâche d'une liste d'attente de processus qui entre en ligne de compte pour le redémarrage, et dans cette liste d'attente il devra y avoir quelques, données par processus attendant et une administration efficace exige que ces données soient aussi limitées que possible. Un 30 processus attendant peut être entièrement identifié par son numéro de stack, dès que le contrôle de présence sur le stack du processus Àa donne pas de difficultés. - Si l'on peut cependant éviter que dans Ja position de liste d'attente d'un processus outre le numéro de stack du stack propre 35 également ©8tf3£ de tous les staeks le précédant hiérarchiquement doivent être notés ,. le contrôle de présanee de ces .derniers devient un processus relativement- complique si l'on '.pplique pas le -..processus préconisé par 1* investira. .... liï.'fîetiX-ié est ea effet que la. relation hierar-40 clique entre .-êeua-.&tgeks se sesÉort pas d';un bad original 70 46394 7 2072028 duite non plus entièrement de la relation hiérarchique des modules ou blocs de programme correspondants au processus. La difficulté est illustrée par un exemple simple représenté sur la fig. 6. 5 Dans ce cas, le module de programme ^ est subordonné à /§, qui est lui-même subordonné à o(. Il y a un stack pour 0{ mais il y a deux processus B^ et Bg démarrés qui sont tous deux commandés par y®, et B^ et Bg ont chacun un sub-processus ou Cg démarré qui sont tous deux commandés.par ^ . 10 Or, du fait que correspond à j^, on ne peut déduire si est subordonné à B^ ou à Bg. En général, en fait dans un environnement de time-sharing, on ne peut pas déterminer préalablement combien de processus analogues (tels que B^, Bg, ... B^) seront commandés simultanément par un 15 module de programme (tel que . Pour l'organisation usuelle des stacks la difficulté n'est pas prohibitive du fait que pour d'autres raisons se trouvent avec la donnée dans le domaine de travail de chaque bloc une référence vers le domaine de travail de blocs qui se trouvent au-dessus de celui-ci 20 hiérarchiquement. Dans le domaine de travail "inférieur" de se trouve donc une référence vers un les domaines de travail dans B^ et cette référence devra contenir, si elle veut être invariable pour le relogement, le numéro de stack de B^. 25 On peut eependant déduire de ce qui précède que l'uti lisation unique de ces circuits de référence avec numéros de stack exigerait qu'un nombre d'accès dans le stack serait nécessaire avant que B.j soit identifé. B^ est trouvé par l'intermédiaire du stack vector array, alors que dans le stack vector array on doit trouver si B^ se 30 trouve déjà ou non dans la mémoire de travail. Le contrôle de présence pour A présentera encore d'autres difficultés, car si B^ ne se trouve pas dans la mémoire de travail, il faut d'abord attendre que B^ soit rentré avant que A puisse être identifié. 35 Le processus conforme à l'invention a pour but d'ob vier à ces inconvénients. Le procédé conforme à l'invention est de ce fait caractérisé en ce qu'à chacun- des domaines de travail ou stacks est allouée une cellule dite de display, ces cellules de display, indépendamment des domaines de travail, sont présentes dans la méaaire . 40 ou sfcaeks avec les temps d'accès les plus courts l'ensatSe BAD ORIGNAL 70 46394 2072028 et alors qu'une cellule de display comporte un gu plusieurs mots de mémoire qui contiennent au moins deux adresses de: référence, la première adresse de référence (pointer) correspond à l'adresse de base du domaine de travail ou de stack, à laquelle la cellule correspond et la deuxième 5 adresse-de référence (pointer) donne l'adresse d'une cellule de display qui est allouée à un domaine de travail ou stack qui se situe à un niveau plus haut sur une ligné hiérarchique dans l'arbre précité. La présence de ces cellules de display dans cet ensemble de mémoire qui a un temps d'accès faible esfc très avantageuse parce 10 qu'il existe une référence facile le long d'une ligne hiérarchique de l'extérieur vers l'intérieur. Les deux adresses de référence dans une cellule de display font en sorte que la chose soit possible. B*autre part, il existe un point important que les cellules dé display sont indépendant tes des domaines de travail correspondants ou des-groupes de domaines 15 de travail joints , c'est-à-dire des stacks. Un& domaine de travail ou un stack peut être déplacé vers une mémoire d'arrière-plan, mais les cellules de display restent dans la mémoire de travail rapide» L'emplacement (« adresse) d'une cellule de display ne varie pas normalement pendant son existence. Si 20 l'on doit faire subitement usage d'un domaine de travail ou d'un stack déterminé et si celûè-ci se trouve dans la mémoire dêarrière-plan, celui-ci peut en être sorti directement sans détour par un nombre d'autres domaines de travail ou stacks. L'appel vers tua des domaines de travail d'un processus et des processus situés au-dessus hiérarchiquement n'exige 25 que l'utilisation d'un circuit de référence court, à savoir les cellules de display dans la mémoire rapidë, ''contrairement au cas précité où l'appel doit se faire par l'intermédiaire d'un certain nombre de stacks intermédiaires (renvoi en série). Lors de la génération d'une nouveàù domaine de travail ou stack, la méthode par cellule de display offre 30 l'avantage que le nouveau domaine de travail ou stack se voit allouer sans plus une cellule de display conformément à l'invention et de ce fait le nouveau domaine de travail ou stack peut être utilisée immédiatement et pleinement. Dans les dominés de travail ou stacks on peut placer éventuellement les adresses de cellulesà* iiftpiàp d'autre domaine de tra-35 vail ou stacks éventuellement arbitraires. Le contenu d'une cellule de display peut alors toutefois être modifié à discrétion, cela n'entraîne pour 3ês domaines de travail ou stacks aucune conséquence tant que l'adresse d'une te11y cellule de display reste la même. Dans le préambule on a cité l'utilisation d'une.table de display employée pour donner les 40 adresses de base de domaines ds base de domaines de travail de blocs se BAD ORIGINAL 70 46394 9 2072028 S'apportent mutuellement qui doivent être adressés. Au cas où il existe plusieurs processeurs il faudra une telle table de display pour chaque processus et si quelques-uns des domaines de travail dans la mémoire de travail sont déplacés de la mémoire d'arrière-plan ou vers 5 cells-ci, chacune de' ces tables de display doit être tenue à jour avec les adresses de base de domaines de travail ou les adresses de base dans le stack modifié. Selon 1'invention, on peut faire usage pour une telle table des.cellules de display. A cet effet, une autre forme de réalisation de l'ensemble de mémoires conforme à l'invention est caractérisée 10 en ce que.dans la mémoire de l'ensemble, de mémoires qui a le plus petit temps d'^ocès une table d'adresse de cellules de display est tenue à jour dans laquelle sont emmagasinées les adresses des Gellules de display qui correspondent aux domaines de travail, de domaines de travail liés hiérarchiquement. Ces tables de cellules de display œ subissent alors pas 15 de modifications pour les relogements des domaines de travail ou des stacks. Les modifications d'adresse de base de domaine^ de travail ou de ..stack sont apportéesdirectement dans.-les cellules de display envisagées. . L'allocation d'une cellule de display à chaque do maine de travail d'un: stack présente l'inconvénient.pratique que leur 20 nombre ast élevé. Pour éyiter cela, on peut introduire une limitation en n'allouant qu'une cellule de display par st&ck, Cela a cependant des conséquences pour la table de display précitée. Construire la table d'adresses de display .précitée nla aucun sens mais .on doit utiliser une autre. forme de table de display. Selon l'invention, cela se fait fruc-.25 tueusement du fa.it que par stack-il n'y a qu'une cellule de display allouée aux stacks, alors que dans une. table de display se trouvent des raots qui comportent chacun! en premier lieu les adresses de cellules de aisnlay. des cellules.de display qui correspondent au stack de ètacks liés hi s.^archiquement et en second lieu les adresses des domaines de travail 30 nécessaires selon la hiérarchie dans les stacks et ce relativement à l'adresse de base de-stack. La.cellule de display conforme.à l'invention peut encore comporter un,certain nombre de ^données. secondaires concernant le domaine de travail ou le stack auquel cette cellule est allouée. 35 C'est ainsi qu'il peut se, trouver des données indiquant la longueur du domaine de travail ou du stack .(capacifé d'emmagasinage) auquel renvoie la cellule de display. Eventuellement,, il peut se. trouver également un certain nombre d'autres données spécifiques à c.e domaine de travail ou stack ■ que l'accessibilité pour certains, ^programmes uniquement ou 40 l'indication que .l'on ne peut que lire -mais, par exemple ne pa.s inscrire,etc. BAD orignal 70 46394 10 2072028 Ces données dans les oellules de display sont très avantageuses s'il arrive une demanda pour une opération qui ne peut ou ne doit pas être effectuée dans le domaine de travail ou dans le stackque ce domaine de travail ou stack ne soiÉ pas non plus vainement relevés. 5 Cela économise beaucoup de temps tandis que l'introduction d'une telle donnée dans les cellules de display ne ' coûte pas Ohbvé*' Dans les cellules de display on peut également placer une indication sur le nombre le processus se trouvant ' 8. l'entrée qui fait usage encore da domaine de travail ou du stack. Si c** nombre est zéro 10 le domaine de travail ou le stack correspondant peuvent être dépâàcés vers la mémoire d'arrière-plan. Dans la cellule de display peut également-se trouver une indication de niveau qui indique les niveaux dudomaine de travail ou du stack correspondant dans l'arbre. ' r La description qui va suivre en rê-gard des dessins 15 annexés fera bien comprendre comment l'invention peut être réalisée. La fig. 7 représente un système de calculatrice électronique dans laquelle le procédé conforme à l'invention est applicable. La fig. 8 représente un ensemble de mémoires adressées selon l'invention. '" ' " * " r 20 La fig. 9 représente un éxemple d'une table d'adresses de cellulesde display selon l'invention. v v - La fig. 10 représenté une autre forme d'une table de ■ - . . -- display conforme à l'invention, et ' ' la fig. 11 représenté une cellule dé display avec 25- domaine pour informations secondaires. ' ' La fig. 7 représente un système de calculatrice dans lequel on peut utiliser un ensemble de mémoires dans lesquels le procédé conforme à l'invention peut être appliqué comme on le décrira par la " » suite en regard de la fig. 8. " " 1 30 . CP désigne le processeur central dans" lequel le traite ment des données est affectué suivant les commandes dans les programmes. On suppose ici que dans le CP se trouvent également" des microgrammes. Il . peut y .avoir plusieurs processeurs CP', CP" ...*. Les processeurs sont reliés à l'ensemvle de mémoires S. S est constitué de deux parties prin-.35 cipales! MS„ la mémoire de travail de la calculatrice qui est une mémoire rapide et la mémoire d'arrière-plan AS qui a une titès grande capacité s * e njmagas iaage mais qui est constituée par les éléments ayant tua temps â'acsès .clus au ..moine tl est possible que dans là mémoire de travail se 40 trouve une partis de mémoire (DC) ayant un temps d'accès plus court encore BAD ORIGINAL 70 46394 2072028 que/reste de la mémoire de travail dans laquelle se trouvent notamment les cellules de diBplay conformes â l'invention. On peut penser par exemple & une mémoire de travail constituée de petits noyaux magnétiques très rapides à boucle d'hystérisis rectangulaire et une partie encore 5 plus rapide constituée par des rangées de circuits intégrés ou même par une partie intégrée à grande échelle. Les parties 1, 2, ... 6 des mémoires d'arrière-plan sont reliées à la mémoire de travail par l'intermédiaire des canaux CHP.| » CHP2. Les parties 1, 2, ... 6 peuvent être un groupe de noyaux de mémoires moins rapides, des mémoires à disques, des. 10 mémoires à bande magnétique et autres mémoires du même genre. Le nombre de deux processeurs de canal n'est pris qu'à titre d'exemple et 11 peut J y en avoir plus s CHP^... auxquels sont couplées d'autres mémoires d1arrière-plan. La fig. 8 représente en S l'ensemble de mémoire d'un 15 système de calculàtrice déjà, décrit sur la fig. 4- A remarquer que dans la suite, on parlera autant que possible uniquement de domaines de travail mais ceux-ci .peuvent également être des stacks. On pourrait ne parler uniquement que de stacks auquel cas un domaine de travail peut être considéré comme un stack comportant un seul domaine de travail. MS dé-20 signe la mémoire de travail qui dans ce cas ne se compose que d'une seule partie. Le plan du dessin représente ici à titre d'illustration le domain» de mémoire. Le remplissage de celui-ci peut se faire de façpn relativement arbitraire. L'adressage, l'inscription et la lecture se font pour chaque sorte de mémoire, de façon connue, 25 Les rectangles désignés par des minuscules représentent les cellules de display conformes à l'invention: aO, a1, ... dt, d2, ... a1, ... fp, ... g6 ... .Chaque cellule de display qui en fonction de sa grandeur comporte un ou plusieurs mots de mémoire physiques, contient deux adresses de référence. La cellule de display ao contient l'adresse 50 de base Ao du domaine de travail correspondant Ao et une adresse de renvoi 0 qui dans ce cas renvoie vers une adresse d'origine 0 non représentée qui renferme par exémple une commande initiale. La cellule de display ai comporte l'adresse de base Ai du domaine de travail correspondant Ai et une adresse de renvoi aO qui indique l'adresse de la cellule de dis-35 play ao qui est allouée au domaine de travail Ao qui se situe à tin niveau plus haut. De même, une cellule de display dj contient l'adresse de base Dj du domaine de travail Dj à"laquelle est allouée la cellule de display dj et une adresse de renvoi a1, qui donne l'adresse de la cellule de display a1, qui est allouée au domaine de travail A1 qui se situe à un 40 niveau hiérarchique plus haut. Les domainès de travail ne peuvent pas BAD ORIGINAL 70 46394 12 2072028 sans inconvénients se trouver également dans la mémoire à'arrière-plan AS. Ainsi par exemple, un-domaine A2. La cellule de display a2 qui est allouée à A2 se trouve dans la mémoire de travail MS. Dans cette cellule de display a2 se trouve l'adresse de ba.se A2.de ce^àoHaine de travail A2 5 dans la mémoire d'arrière-plan AS. D'autre part3 cette cellule de display renferme également une référence vers le niveau situé plus haut â savoir avec ao avec la cellule de display ao &* dèmaine de travail Ao. L» même raisonnement est valable pour les autres domaines de travail et leurs cellules de diêplay. 10 En supposant que le processus qui a lui-même le do maine de travail G10 entre en ligne de compte dans la mémoire de travail MS pour un redémarrage, de sorte qu'il faut rendre utilisable des données d'un domaine de travail situé plus"haut A2 qui est cependant emmagasiné lui-même dans la mémoire d'arrière-plan AS. Dans ce cas, cela peut se 15 faire de la façon suivante: dans la cellule de display glO du domaine de travail G10 se trouve l'adresse e1 de la cellule de display e1 dans laquelle se trouve l'adresse a2 de la cellule de display a1. Dans la 1 cellule de display a2 se trouvé l'adresse A2 qui est l'adresse de hase du domaine de travail- A2 dans :la mémoire â'arrière*plan AS. Ce domaine de 20 travail peut donc être retiré. Il est évident que 1'opération peut se faire rapidement du fait qu'il n'est pas nécessaire de retirer également le domaine de travail intermédiaire Et qui était également ici dans la mémoire d'arrière-plan, pour pouvoir arriver par l'intermédiaire de ce domaine de travail à A2. La présence de la cellule de display ç1 du do-25 maine de travail E1 dans la mémoire dé travail est déjà suffiaânte pour trouver l'adresse du domaine A2. Lo^s de la génération d'un nouveau domaine de travail par un domaine de travail précédent, il se produit ce qui suit: en supposant que le domaine dé travail A1 engendre le domaine de travail Dj. Pour 30 incorporer ce domaine de travail entièrement dans la hiérarchie à structure d'arbre existante, il suffit que lors de la génération de Dj également un nouveau domaine de cellule de display soit engendré, à savoir dj dans laquelle l'adresse de base Dj dû nouveau domaine de travail Dj se trouve et dans laquelle l'adresse at de la cellule de display a1 qui 35 correspond 'au domaine de travail générateur A1, est emmagasiné». La fig. 9 représente deux exemples de tables d'adresse de display conformes à l'invention. On suppose qu'il y a deux stacks ST.j et STg selon la fig. 4« Les displays DT^ et DTg représentés sur la fig. 4 sont remplacés par des tables d'adressesde cellule de display 40 SCT.J et DCTg dans laquelle les adresses sont placées des cellules de BAD ORIGINAL 70 46394 15 ' 2072028 display qui corresponderit aux domaines de travail désignés dans le display précédent DT1 et DT2 par l'intermédiaire de leurs adresses de base. Dans ce cas, les domaines de travail B1,B2, B4 et C2 et C3 ont une analogie hiérarchique avec la structure par bloc des blocs B°1, B°2 ... C°2, 5 C°3 et C°4 âe la fig. 1. Cela s'exprime dans les cellules de display groupées sur la fig. 9 aux adresses b1, ... b4 et c2 ... c4. Les adresses b1, b2 et b4 sont notées dans la table d'adresse de cellule de display DCT2 et les adresses b1, c2 et c3 sont notées dans la table DCT1. Lors des relogements, par exemple lors d'une interruption, il ne faut donc 10 pas apporter de changement dans les tables d'adresses de display. Des changements d'adresse de base dé domaine de travail sont uniquement ténus à jour dans leurs cellules de display correspondantesi Là fig. 10 représente un exemple d'une table dè-display conforme à l'invention, dans laquelle on part du principe qu'il n'y qu'une cellule de display 15 par stack et non par domaine de travail, • • •On suppose qu'il y a deux" stacks ST1.et ST2 suivant là fig. 4. Là où, dans la fïg.'4 se trouve l'adresse physique (comme CA2) d'un domaine de travail déterminé (comme C2) dans un display (comme DT1) vient maintenant â ce même emplacement dans DT1, la première adresse de 20 là cellule de display" (stl ) et en second lieu 1'-adresse relative (rc2) du domaine de" travail (C2) dans le stack (ST1). Le même raisonnement est valâblè pour les autres stacks désignés ST2 avec domaines de travail B2 et B4." L'es "Cellules de display pour les stacks ST1 et ST2 se trouvent aux-adrësses sti et st2, rangéés à titre d'exemple ici*sur une ligne dans 25 un cordon de cellules de display DCS. Lors de l'adressage, on part d'une, position dans un display. Par exemple, la position en DT2 où Se trouve st2, rb2. Avec st2 la cellule de display est adressée pour le stack ST2. Dans cette cellule se J"?ouve l'adressé de base ST2 de ce stack ST2. A cette adresse de base 30 ST2 est ajoutée l'adresse relative rc2 hors de la table de display. Il est évident que pour adresser dans le domaine de travail lui-même dans ce cas et dans les autres exemples cités, il faut une autre composante d'adresse, relative par rapport à l'adresse de base de domaine de travail relative ou non. Ceci est cependant de pratique normale et de ce fait, 35 on n1entrera pas dans les détails. Les relations mutuelles sont représentées sur la fig.-10 pai des lignes de liaison. Pour une interruption qui-amène -le programme dans un état d'attente des données sur le statut du programme peuvent être placées au-dessus sur le stack! actif- Si l'on place alors un bloc de .contrôle 40 comportant l'adresse de cellule de display.et de données concernant la BAD ORIGINAL 70 46394 2072028 hauteur de ce stack actif, à la disposition du planificateur, le stack actif peut être emmagasiné et dans les cellules de display de tous les stacks situés au-dessus hiérarchiquement, on peut emmagasiner les'états de compteur (N sur la fig. 11, voir plus loin) dont le fait qu'ils sont 5 désirés pour leur processing est représenté dans le domaine de travail par une diminution d'une unité. Si un des états de' compteur vient de ce fait sur zéro, le stack correspondant peut également être enlevé de la , mémoire de travail. Lorsque le programme interrompu peut de nouveau être 10 mis en route, le stack le plus bas hiérarchiquement peut Stre atteint par l'intermédiaire du bloc de contrôle et tous les autres par l'intermédiaire du circuit de référence de cellule de display'en cellule de display. A l'intérieur d'un stack il y a, en supposant encore que les domaines de travail eux-mêmes n'ont pas de cellules de display, 15 selon un procédé connu, un circuit de référence de domaine de travail à domaine de travail. Celui—çi peut être utilisé pour rétablir le contenu des positions de display pour le programme envisagé, une fois que les stacks sont rentrés. La fig. 11 représente une cellule de display a2 dans 20 laquelle sont également emmagasinées un certain nombre de données secondaires concernant le domaine de travail A2 àuquel est allouée cette cellule de display. L désigne une indication de longueur de domaine de travail. NW-Q est un exemple d'indication de ce qu'il peut et/ou ce qui peut se produire dans un tel domaine de travail. Par exemple: interdiction 25 d'inscrire, excepté par une commande caractérisée par Q. IT est le nombre qui indique le nombre de processus se trouvant à l'entrée qui font encore usage de ce domaine de travail A2. On peut prévoir dans le système de calculatrice une routine qui lorsque N = 0 fait déplacer le domaine de travail vers la mémoire d'arrière-plan. NV" est une indication 30 pour le niveau du domaine de travail. L'utilisation de cette sorte de données secondaires est connue en soi et ne sera par conséquent pas considérée plus en détail. Le fait qu'un domaine de travail soit ou non présent dans une mémoire de travail, peut être déduit directement de l'adresse 35 du domaine de travail qui se trouve dans la cellule de display correspondante,, Il est plus facile cependant parfois de placer dans la cellule le display une indication additionnelle de ce que le domaine de travail correspondant se trouve eu non dans la mémoire d'arrière-plan. ; i Vâ maintenant examiner deux exemples d'un procédé 40 possible avec les cellules de display dans le système de calculatrice / . * , .. BAD ORIGINAL 70 46394 2072028 dans lequel le -procédé conforme à l'invention est utilisé. On ne donne pas de détails étant donné qu'il vont de soi pour le spécialiste. I. Lorsque dans le système de calculatrice on demande l'exécution d'un certain nombre de processus, parmi ce nombre de pro-5 cessus est exécutée la tâche dont tou« les domaines de travail nécessaires (respectivement les stacks) se trouvent dans la mémoire de travail. Pour les t&ches pour lesquelles ceci n'est pas valable les domaines de travail manquants seront introduits dans la mémoire de travail à des instants où le système est libre. Le test pour considérer si tou* les 10 domaines de tra\aîl pour une tâche sont présents peut se faire de la façon suivante: 70 46394 2072028 70 46394 2072028 Ce microprogramme pour le tést de présence va en grande partie de soi. Il faut considérer cependant qu'en premier lieu une tâche (quelconque) est prise dans une liste d'attente de tâches à la tête. La tâche est caractérisée par le circuit de référence â partir de sa propre cellule 5 de display, â partir de laquelle sont lues les:cellules de display successivement à l'aide de l'adresse de référence dans chaque présence dans chaque cellule de .display vers la cellule de display qui correspond au domaine de travail qui se situe à un niveau plus haut sur la ligne hiérarchique. Dans-les cellules de display se trouve directement (avec un 10 indice particulier) ou indirectement par l'adresse du domaine de travail correspondant, si le domaine de travail est" oui ou non présent dans la mémoire de travail. Si oui, il vient à 1, et si non, il vient à 0 sur la position suivante dans le mot V. C'est ainsi que par exemple: les cellules de display pour domaines de travail Ao, A2, E1 et G10 (voir fig. 8) 15 Ao se trouve dans la mémoire de travail, A2, E2 ne s'y trourerfcpas et G10 s'y trouve, "de sorte que V est le suivant: 1001. Y est complète lorsqu'une cellule de display d'un niveau 0 est: lue. A ce point, on peut lire un mot V hors de la position T dans la rangée d'attenteQ qui par ordre .de succession des niveaux dans la tâche comporte un,1 pour les ni-20 veaux (désignés par les cellules de display) pour lesquels lors de l'exécution .de cette tâché,-il n'a y pas "besoin de domaine de travail dans la mémoire de .trayail,.. On suppose par exemple W = 0110. On applique alors aux mots V et W -la: fonction OU: 1001 + 0110 = 1111, XIre s'agit donc que de uns. Cela veut dire que tous les domaines nécessaires sont pré- 25 sents et que la tâche, si les autres conditions sont remplies, peut être exécutée. II. On va maintenant décrire un microprogramme, utilisable pour faire rentrer un domaine de travail (ou stack) qui ne se trouve pas dans la mémoire de travail. Le début est une cellule de display d'une 30 tâche sélectionnée. Dans un mot W (déjà cité plus haut) on peut lire si le domaine de travail auquel est associé la cellule de display est nécessaire. Dans l'affirmative, il faut chercher dans la cellule de display si ce domaine de travail est déjà présent dans la mémoire de travail Si c'est le cas, cela peut être noté sur un compteur de réservation dans 35 la cellule de display en augmentant ce compteur d'une unité. Si cela n'est pas le cas, l'adresse de ce domaine de travail, non présent, est placée sur une queue qui contient des commandements d'introduction. Le compteur de réservation, présent dans la cellule de display, est alors également augmenté d1une unité. Tant que le niveau dans le circuit de 40 référence de cellule de display est différent de 0, le cycle se poursuit: • * 70 46394 18 2072028 la cellule de display suivante dans la table est lue, et ainsi de suite. Par l'apparition des commandes d'introduction pour ces domaines dé travail qui ne sont pas présents dans la mémoire de travail, ces domaines de travail seront introduits après un certain temps dans la mémoire de travail. Le.diagramme pour ce microprogramme est s .Début = cellule de display de tâche sélectionnée i t jh, [ Lisez dans le mot W si le domaine dfe V correspondant est nécessaire ; ??.vail oui non Lisez dans la celïule de display s'il est présent oui Le compteur de réservation haut daiis le display est.plein non D D Placez l'adresse du domaine de travail, sur" une queue pour la commande d'introduction, compteur de réservation Haut plein, E Niveau de "la cellule de display :^ 0? non- - . Remplace2 la cellule de display par celle de renvoi avec l'adresse de; renvoi - - prêt BAD ORIGINAL 70 46394 2072028 RBVEHPICJLTIOKSt 1. Procédé d'adressage dans un ensemble de mémoires constitué de mémoires ayant dis temjs d'accès différents alors que dans les mémoires des régions peuvent être occupées par des parties de programme 5 et des données, appelées "domaines de travail" ou "stacks" (empilements) dans le cas des groupes de domaines de travail joints qui sont identifiables à l'aide d'une adresse de base de domaine de travail ou de stackj, c'est-à-dire l'adresse qui donne l'emplacement du domaine de travail ou d'un stack dans un ensemble de mémoires, alors que les domaines de tra-10 vail ou les stacks sont liés hiérarchiquement suivant une structure d'arbre, alors que pour l'identification des lignes hiérarchiques, de l'extérieur vers la racine de l'arbre, on prévoit des adresses de références alors que les domaines ou les stacks sont déplaçables d'une mémoire vers une autre mémoire* ce prdcédé étant caractérisé en ce qu'à 15 chacun des domaines de travail ou stacks est allouée une cellule dite de display, ces cellules de display, indépendamment des domaines cte travail, sont présentes dans la mémoire ou stacks avee les temps d'accès les plus courts de l'ensemble de imémoîceset alors qu'une cellule de display comporte un ou plusieurs mots de mémoire qui contiennent au moins 20 deux adresses de référence, la première adresse de référence (pointer) correspond à l'adresse de base du domaine de travail ou de stack, â laquelle la cellule correspond et la deuxième adresse de référence (pointer) donne l'adresse d'une cellule de display qui est allouéee â un domaine de travail ou stack qui se situe à un niveau plus haut sur 25 une ligne hiérarchique dans l'arbre précité. 2. Procédé d'adressage dans un ensemble de mémoires selon la revendication 1, caractérisé en ce que dans la mémoire de l'ensemble de mémoires qui a le plus petit temps d'accès une table d'adresses de cellules de display est tenue à jour dans laquelle sont emmagasinées les 30 adresses des cellules de display qui correspondent aux domaines de travail, de domaines de travail liés hiérarchiquement. 3. Procédé d'adressage dans un ensemble de mémoires selon la revendication 1, caractérisé en ce qu'il n'y a qu'une cellule de display allouée aux stacks, alors que dans une table de display se 35 trouvent des mots qui comportent chacun: en premier lieu les adresses de cellules de display des cellules de display qui correspondent au stack de stacks liés hiérarchiquement et en second lieu les adresses des domaines de travail nécessaires selon la hiérarchie dans les stacks et ce relativement à l'adresse de base de stack. 40 4. Procédé d'adressage dans un ensemble de mémoires selon 5£t070 46394 20 *• • •: h 2072028 la revendication 1, caractérisé en ce que dans une cellule de display sont placées un certain nombre de aonnées secondaires concernant le domaine de travail'ou stack, auquel cette cellule, est^àllouée. " " ~ ; BAD ORIGINAL