Brevet FR2077507A1 — publié le 19711029

La présente invention concerne un système pour mesurer l'efficacité d'un algorithme de remplacement de blocs de données au cours même du déroulement du programme dans lequel s'effectuent ces remplacements. Un nombre croissant d'ordinateurs sont fondés sur le concept de l'utili-5 sation d'une mémoire de données à vitesse élevée, à capacité faible (telle qu'une mémoire è ferrite) en liaison avec une mémoire de réserve à vitesse faible, et à capacité élevée (telle que des unités à bande, à disque au à tambour) et de l'utilisation du système de telle sorte qu'un nombre relativement petit de blocs ou pages d'information que le calculateur utilise 10 couramment se trouve dans la mémoire à vitesse élevéetque l'on désigne parfois sous le nom de "mémoire rapide" ou comme "mémoire ne travail") où ils sont plus facilement accessibles, alors que la plupart nés blocs ou pages d'information qui ne sont pas couramment utilisés par le calculateur restent dans la mémoire de réserve. Initialement tous les blocs ou pages d'information 15 Sont situés dans la mémoire de réserve, et lorsqu'un bloc est demandé par le calculateur» il est transférér à la mémoire :e vitesse élevée car on suppose (hypothèse habituellement valide) qu'il y aura probablement d'autres demandes pour l'information contenue dans ce bloc au cours du déroulement au programme. Cependant, le bloc est toujours identifié Dar son adresse originale (numéro 20 de bloc) dans la mémoire de réserve même si son adresse dans la mémoire de travail est différente. Les dispositifs de traitement de donnée ne cette sorte sont connus sous divers noms, tels que système "à mémoire virtuelle", système "à emplacement de mémoire dynamique", "machines de mise en page", ou "machines à un niveau de mémoire". De tels dispositifs présentent l'avantage que la 25 plupart de leurs capacités de mémoire d'information peuvent être sous la forme de mémoires à vitesse lente adressables qui sont beaucoup moins coûteuses que les mémoires à vitesse élevée, et l'on peut réaliser une économie considérable. Lorsque la mémoire rapide d'un système ce cette sorte est remplie, et qu'une demande est réalisée pour un bloc d'information ne se trouvant pas déjà 30 dans cette mémoire le système doit décider lequel des blocs actuellement situés dans la mémoire rapide doit être remplacé par le bloc nouvellement demandé. La procédure pour réaliser cette décision est appelée "un algorithme de remplacement". Idéalement un algorithme de remplacement devrait fonctionner de telle sorte que le nombre des transferts de bloc entre la mémoire de réserve et la 35 mémoire à vitesse élevée soit réduit au minimum comoatible avec le programme particulier que l'on exécute. Cela signifie qu'un algorithme de remplacement doit normalement fonctionner de telle sorte qu'il ne maintienne pas les blocs oe données peu utilisés dans la mémoire à vitesse élevée durant un pourcentage de temps trop élevé alors que cela entraine le transfert des blocs de donnée 40 utilisés fréquemment en un mouvement de va et vient entre les mémoires rapides BAD origine 70 34360 2 2077597 et de réserve un nombre de fois excessif. Tous ces transferts non nécessaires représentent une perte du temps pour l'ordinateur, ce qui détruit l'avantage économique inhérent d'un système à mémoire virtuelle. En pratique, il n'est pas possible d'obtenir un fonctionnement idéal 5 mais puisque l'algorithme de remplacement doit prendre ces décisions en "temps réel" sans connaître ce qui se produira durant le reste du programme, il y aura des décisions de remplacement occasionnelles qui aboutiront plus tard à des transferts non nécessaires, dont chacun détruit partiellement le but du système à mémoire virtuelle. De nombreux algorithmes de remplacementexistent 10 actuellement et ils ne sont pas tous aussi bien adaptés à des programmes particuliers ou classe de programme. Le choix de l'algorithme de remplacement par conséquent à une portée directe sur l'efficacité de l'utilisation du système de traitement de données. Il n'est pas facile en utilisant les procédés classiques, de juger si un 15 algorithme de remplacement donné, donne un fonctionnement optimum. Habituellement cela nécessite une procédure d'interprétation indépendante et prenant du temps que l'utilisateur de l'ordinateur peut considérer comme ennuyeuse et qu'il ne suivra probablement pas dans la plupart des cas. Sans un moyen facile pour mesurer l'efficacité des cas de remplacement il n'existe aucune façon facile 20 pratique pour les utilisateurs d'ordinateurs d'effectuer des comparaisons valables entre les algorithmes de remplacement. En conséquence, il sont contraints d'utiliser des algorithmes qui dans la plupart des. cas ne sont pas les mieux adaptés aux conditions de leurs problèmes particuliers. Il existe actuellement un besoin pour une méthode permettant de mesurer dynamiquement l'effica-25 cité d'un algorithme de remplacement lors de son exécution, sans amener une dégradation significative du fonctionnement de l'ordinateur. La présente invention rend possible la mesure de 1'efficacitéd'un algorithme de remplacement lors de son utilisation et sans amener une perte substantielle de temps d'ordinateur. Pour atteindre cet objectif on utilise une 30 technique de mesure directe dans laquelle une décision de remplacementeffectuée à tout moment donné est comparée automatiquement, à un moment ultérieur approprié, avec la décision qui aurait été prise par un algorithme de remplacement supposé optimum en prenant en considération les événements qui se sont produits entre ces deux moments. Pour effectuer de telles comparaison, le calculateur 35 central est utilisé durant les intervalles "d'interruption" pendant que le programme attend la réalisation d'échange de place entre la mémoire rapide et la mémoire de réserve, de sorte qu'on évite d'utiliser ce calculateur pour faire des mesures d'efficacité de remplacement pendant les périodes où il reçoit des informations de la mémoire rapide et ne demande pas des remplacements de 40 nouvelles pages. Ainsi, l'exécution du programme n'est pas retardé matériel- BAD ORIGINAL 70 34360 3 2077507 lement par les calculs progressifs de l'efficacité de remplacement. L'invention permet ainsi de contrôler de façon intermittente l'algorithme de remplacement réel en le comparant avec un algorithme de remplacement optimal simulé qui le suit légèrement dans le temps.Le système présent donne 5 une mesure fiable à l'efficacité du remplacement sans nécessiter une interprétation "hors-travail'' du comportement du programme. Pour préciser ce qui précède, l'invention utilise des données indiquant la séquence des références qui ont été faites aux blocs d'information mis en mémoire par l'ordinateur, pour construire par étapes successives un algorithme 10 de remplacement optimal qui tend à minimiser le nombre de fois où il est nécessaire de transférer les blocs d'information dans une mémoire à vitesse élevée de capacité donnée pour satisfaire à cette séquence réelle de références au bloc. L'ordinateur assemble de façon continue et automatique certaines données tabulaires (que l'on appelle ici les tables "E" et "C") et d'autres 15 valeurs cumulatives (que l'on appelle ici des valeurs "A" et "B") qui à tout instant donné reflètent les travaux de l'algorithme de remplacement optimal jusqu'à l'instant présent et à partir de telles données, le système détermine alors le nombre minimum de remplacements de blocs ou pages qui auraient été nécessaire jusqu'à cet instant. Ce nombre minimum" est celui des rem-20 placements qui auraient été effectués par l'algorithme de remplacement optimal si il avait pris la commande de système. Pour obtenir un système de mesure direct pratique, l'algorithme optimal adopte une hypothèse arbitraire au sujet de l'ordonnancement des pages ou blocs qui ont été référenciés entee les remplacements et de ce fait, il peut spécifier à l'occasion un transfert de bloc 25 que l'algorithme de remplacement réel ne trouve pas nécessaire. Des dispositions automatiques sont prises pour ajuster le compte de transfert "non nécessaire" en conséquence, si et lorsque cela se produit. Dans l'ensemble cependant, l'algorithme optimal définit un fonctionnement plus efficace que tout ce que l'on peut obtenir par un algorithme de travail, et le nombre "minimum" de 30 templacements déterminé par l'algorithme optimal, par conséquent, peut être comparé avec le nombre de remplacements effectué réellement pour donner une mesure de l'efficacité de remplacement. Par l'introduction de certaines nouvelles caractéristiques dans le système de référenciationdes blocs dans la mémoire à vitesse élevée, (en uti-35 lisant une sorte d'indice de référence mis en mémoire que l'on appelle ici "bits R"), le système de réalisation de l'invention permet de réaliser une mesure efficace d'une façon dynamique ou directe tout en fonctionnantsous un programme vrai. Chaque fois que le fonctionnement du calculateur central est interrompu en réponse à une demande pour une information de page de bloc qui 40 ne se trouve pas dans la mémoire à vitesse élevée, il est utilisé le calcula- ». 70 34360 4 ' 2077507 teur pour réaliser une détermination de mise à jour du nombre de remplacements qui aurait été effectué jusqu'à ce moment par l'algorithme de remplacement optimal en prenant en considération toute référence faite aux pages dans la mémoire à vitesse élevée durant la période d'intervention. 5 Ainsi le procédé de mise à jour fonctionne au moment où le calculateur attend des remplacements de bloc, de telle sorte qu'il n'interfère pas de façon importante avec l'exécution du programme. Lorsque l'on atteint la fin du programme, une mise à jour finale donne immédiatement l'information d'efficacité de remplacement global. Cette technique permet de comparer les efficacités 10 respectives d'un nombre important d'algorithmes de remplacement en moins de temps qu'il n'en est nécessaire pour mesurer une seule fois l'efficacité d'un, algorithme de remplacement par l'utilisation d'un procédé classique. L'algorithme de remplacement "optimum" mentionné ci-dessus est analogue mais pour des raisons pratiques non absolument identique .à un algorithme 15 "MIN" décrit dans un article de L.A Belady ayant pour titre "A Study of Remplacement Algorithms for a Virtual-Storage Computer" publiédans IBM Systems Journal Vol. 5, N° 2, 1966, pages 78-101. Le dispositif de mesure efficace considéré agit chaque fois que le calculateur est interrompupour le remplacement par un nouveau bloc pour déterminer automatiquement si un tel remplacement 20 aurait été nécessaire si l'algorithme optimal que l'on vient de mentionner avait été suivi jusqu'à ce moment du programme. Naturellement, cette détermination de ce qu'aurait fait l'algorithme optimal doit nécessairement être effectuée d'une façon tardive, puisqu'elle doit attendre l'identification du bloc en cours de demande et qui est sur le point d'être introduit dans la 25 mémoire de travail, moment auquel la décision de templacement réelle a déjà été faite. De plus l'algorithme optimal doit faire certaines hypothèses arbitraires au sujet de l'ordre des références aux blocs entre les remplacements comme mentionné ci-dessus, alors que l'algorithme WIN" ne reposerait que sur une information complète au sujet de ces références. 30 Occasionnellement comme on l'a déjà mentionné, selon la nature de l'al gorithme de remplacement que l'on utilise et de la séquence spécifique par laquelle les blocs sont demandés, il peut arriver que l'algorithme de remplacement optimal trouve nécessaire de transférer dans la mémoire de travail un bloc qui y était déjà du fait de l'algorithme de remplacement réel. Dans ces 35 conditions, chaque fois qu'elles peuvent se produire, le système de mesure actuel peut donner un crédit à l'algorithme de remplacement réel pour avoir évité un transfert de bloc que l'algorithme de remplacement optimal peut avoir trouvé nécessaire. Comme mentionné ci-dessus, l'algorithme de remplacement optimum ne prend pas nécessairement une décision aussi bonne ou meilleure 40 que la décision prise par l'algorithme de remplacement réel dans tous les cas. î 70 34360 5 ' 2077507 10 15 20 25 30 35 Quelquefois l'algorithme optimal peut avoir à faire un choix qui à ce moment parait le meilleur, mais qui ultérieurement peut ne présenter aucun avantage en comparaison du choix effectué par l'algorithme de remplacement réel, ou même être inférieur à un tel choix, selon l'ordre dans lequel les blocs ont été demandé dans le programme. Dans une situation de cette sorte, le système présent peut ajuster automatiquement sa mesure pour refléter de façon plus précise l'état vrai des affaires. Dans la plupart des cas si ce n'est dans tous, cependant, la décision de remplacement formulée par l'algorithme opimal pourrait, à longue échéance s'être révélée meilleure ou au moins aussi bonne que celle prise par l'algorithme de remplacement réel, et dans ces circonstances il n'est pas nécessaire de réaliser de tels ajustements. Il peut exister d'autres situations dans lequelles, à cause de l'hypothèse arbitraire au sujet de l'ordre de référenciation entre les remplacements, il peut être douteux que l'algorithme de remplacement optimal ait dans tous les cas fonctionné plus efficacement que l'algorithme de remplacement réel pour éviter des transferts de blocs non nécessaires. Lorsqu'une telle situation existe le système considéré peut manifester ce doute en spécifiant une marge de modification possible pour le compte de "transfert non nécessaire". D'autres objets, caractéristiques et avantages de la présente invention ressortiront mieux de l'exposé qui suit fait en réféence aux dessins annexés à ce texte qui représentent des modes de réalisation préférée de celle-ci. Sur les dessins, les carrés marqués OK représentent des circuits OU les carrés référenciés A représentent les circuits ET, et les rectangles marqués FF représentent des basculeurs. La figure 1 représente un diagramme général d'un système de traitement de donnée à mémoire virtuelle dans lequel on à l'intention d'utiliser l'invention. Les figures 2,3, 4A, 4E et 5 sont des tables décrivant des procédures de mesure typiques réalisées selon l'enseignement de l'invention. Les figures B et 7 sont des diagrammes généraux ou des organigrammes qui indiquent les relations fonctionnelles entre l'algorithme de remplacement réel qui est utilisé et la procédure de mesure d'efficacité que l'on lui applique. Les figures 8A à 9D lorsqu'assemblées de la façon indiquée par la figure 8 constituent un diagramme de circuit d'une mémoire associative qui peut être utilisée dans le système présent. Les figures 9 à 9K lorsqu'assemblées de la façon indiquée par la figure 9 , constituent un diagramme complet des circuits permettant de réaliser l'invention. La figure 10 est un diagramme de circuits montrant un type de tables 70 34360 e 'mim mémoire qui est utilisé dans le système mentionné ci-dessus. Les figures 11A à 11D lorsqu'assemblées de la façon indiquée par la figure 11 constituent un ordinogramme de ce système. Les figures 12A à 12L lorsqu'on les considère avec l'ordre indiqué 5 illustrent de façon progressive la séquence des opérations décrites dans les figures 4A et 4B. La figure 13 est une table décrivant un autre type de fonctionnement qui peut être réalisé par le système. Les figures 14A à 14F, lorsqu'on les considère dans l'ordre indiqué 10 illustrent progressivement la séquence des opérations décrites dans la figure 13. On expliquera en général l'organisation d'un système de traitement de données à mémoire virtuelle dans cette partie de la description. Ensuite par une série d'exemples élémentaires, on comparera les fonctions de l'algorithme 15 de remplacement "optimum" avec celles d'un algorithme de remplacement réel. Le système de mesure présent est naturellement adapté pour fonctionner avec de nombreux types d'algorithmes de remplacement qui existent actuellement. La figure 1 représente un diagramme illustrant un système de traitement de données appelé "à mémoire virtuelle" où l'unité de traitement centrale 20 CPU communique directement avec et seulement avec, une mémoire de travail à capacité faible, à vitesse élevée, WM. Cette mémoire WM, par exemple, peut constituer une mémoire à ferrites à accès au hasard de taille limitée. Un système de traitement de donnée à mémoire virtuelle est caractérisé par le fait que l'unité CPU ne communique pas directement avec le canal CH par lequel 25 l'information est obtenue à partir ou transférée de la mémoire de vitesse faible à capacité élevée BS. En d'autres termes le seul appareil de mémoire que le CPU "voit" est la mémoire de travail WM. Chaque fois que le CPU demande un bloc ou page d'information, cette demande de mémoire est envoyée au dispositif de commande de recherche SC. Dans une première étapele dispositif 30 de commande de recherche SC oblige une mémoire associative AM (ou mémoire à dispositif de transformation équivalente) à effectuer une recherche afin de déterminer si le bloc demandé d'information a une contre-partie dans la mémoire de travail WM. Si aucune contrepartie n'est trouvée, le dispositif de commande de recherche SC envoie alors la demande de mémoire aux commandes de 35 canaux CH qui extraient le bloc demandé de la mémoire de réserve BS et le dispose dans la mémoire de travail WM, où il est maintenant accessible à l'unité CPU. Après avoir été envoyé dans la mémoire WM, le bloc d'information demandé possède deux adresses l'une étant son adresse virtuelle ou numéro de bloc dans la mémoire de réserve BS, et l'autre étant son adresse de travail 40 réel dans la mémoire de travail WT1. Les deux adresses sont mises en mémoire S 70 34360 7 2077507 de façon appropriée dans l'une des rangées ou "mot" de la mémoire AM, avec d'autres données utiles qui seront décrites bientôt. Au moyen des commandes de mémoire de travail WMC, avec la mémoire associative AM et les commandes de recherche SC, une connexion logique est établie entre l'adresse virtuelle ou 5 numéro de bloc et l'adresse de travail du bloc lorsqu'il est dans la mémoire de travail. Tant que le bloc cité ci-dessus reste dans la mémoire de travail WM, une demande provenant de l'unité CPU pour l'information contenue dans ce bloc, (identifiée par son numéro de bloc) sera envoyée directement à la mémoire de travail WM, et la mémoire de réserve BS et le canal CH ne seront pas mis 10 en cause dans le transfert d'information résultant. De façon semblable, lorsque l'information traitée par l'unité CPU peut être inscrite dans un bloc ayant une adresse dans la mémoire de travail WM une telle information sera transférée de CPU directement à la mémoire de travail WM sans utiliser le canal CH et la mémoire de réserve BS. 15 Puisque la mémoire de travail à vitesse élevée WM est de construction beaucoup plus couteuse (par unité d'information de mise en mémoire) que la mémoire de réserve à vitesse faible BS la plus grande partie de la capacité d'emmagasinage d'information du système est constituée par la mémoire de réserve et la mémoire de travail WM n'a qu'une capacité limitée de mémoire. 20 Lorsque la mémoire WM est pleine, et que l'unité CPU demande un bloc d'information qui ne se trouve que dans la mémoire de réserve BS, il devient alors nécessaire de remplacer l'un des blocs de la mémoire WM avec le bloc nouvellement demandé. Le remplacement peut consister simplement à supprimer ou écrire par dessus le bloc désigné dans la mémoire de travail, ou dans le cas où le contenu 25 du bloc a été modifié lorsque le bloc était dans la mémoire de travail, le remplacement peut entraîner le transfert du bloc modifié dans la mémoire de réserve BSj où il est écrit par dessus le contenu original du bloc. Le choix du bloc qui do;Lt être remplacé dans la mémoire de travail est fait par l'algorithme de remplacement particulier que l'utilisateur emploie à ce moment. 30 Cet algorithme de remplacement agit par le moyen de nombreuses commandes SC, WMC et CH pour effectuer de tels remplacements de colonnes selon la nécessité. Jusque là il a été très difficile ou pratiquement impossible à déterminer si l'algorithme réalise cette tâche de façon efficace ou inefficace. La présente invention, cependant, rend réalisable et plus facile cette détermina-35 tion. Chaque fois que l'on se réfère ici à "algorithme de remplacement réel" ou simplement "algorithme de remplacement", cela indique l'algorithme de remplacement qui est réellement utilisé dans le système, en distinction de "l'algorithme de remplacement optimal" que l'on suppose être l'algorithme de rempla-40 cernent qui aurait l'efficacité globale la meilleure pour le programme particu- ». 70 3436Û 6 ' 207750/ lier qui est donné à la machine. L'algorithme optimal a pour but de réduire au minimum le nombre de remplacements de blocs qu'il est nécessaire de réaliser. Par définition il est 100% efficace. Si l'on prend le nombre total de transferts de blocs dans la mémoire de travail effectuée par l'algorithme de remplacement 5 réel et si on lui soustrait le nombre total de transfert de bloc dans la mémoire de travail qui aurait été effectué par l'algorithme optimal durant l'exécution d'un programme identique, la différence représentera le nombre de transfert non nécessaire (U). Si P représente le nombre de fois total où les blocs d'information ont été retirés de la mémoire de réserve, l'efficacité de rempla- 10 cernent est P-U . P En l'absence de tout procédé fiable de sélection judicieuse parmi les nombreux algorithmes de remplacement existants sur la base de mesures d'efficacités comparatives, les valeurs d'efficacité de remplacement pratiquas sont faibles (par exemple de 30 à 50%). Un but de la présente invention est d'accélérer la réalisation des mesures d'efficacité de remplacement de telle aorte que l'utilisateur puisse comparer rapidement les algorithmes de remplacemert de façon précise et qu'il n'ait pas besoin de se fier à la chance ou à l'intuition pour la sélectiond'un algorithme de remplacement pour le type particulier de programme qu'il peut avoir l'intention d'utiliser. Comme mentionné ci-dessus, les décisions de remplacement de blocs qui devraient avoir été prises par le système de traitement de donnée jusqûà un point donné de l'exécution d'un programme ne peuvent être habituellement déterminées avant que le moment de changement de certaines de ces décisions 2g soit passé. De là : les décisions de remplacement de bloc optimal ne peuvent être toujours réalisées en "temps réel" ce qui serait le plus désirable. La caractéristique suivante la plus désirable, que la présente invention rend possible est de déterminer automatiquement à des intervalles "d'interruption pratique" le nombre minimum de remplacements de blocs qui aurait pu être réalisé avant certains points de contrôle dans le temps si la séquence de remplacement optimale avait été suivie jusqu'à ce point, et à l'aide d'une mise à jour continue de cette information durant le déroulement d'un programme il est possible d'engendrer un comptage cumulatif des "transferts non nécessaires" jusqu'à la fin du programme. Si l'efficacité de remplacement calculée semble faible, alors à l'occasion suivante lorsque le même programme ou un programme similaire est traité, on peut essayer un algorithme de remplacement différent et comparer son efficacité avec celui de son prédécesseur. Une caractéristique de la présente invention est que ces mesures cumulatives sont réalisées sans gêner de façon significative l'utilisation normale du système de traitement de données. Cela est rendu possible par une nouvelle technique de commande qui permet d'adresser de façon répétée des blocs d'information à 70 34360 9 2Û77507 localisés dans la mémoire à vitesse élevée sans nécessiter d'interruption dans les opérations de lecture et d'écriture dans des buts de mise à jour de mesure, tant qu'aucune demande n'est effectuée pour une information qui n'est pas actuellement contenue dans la mémoire à vitesse élevée, et d'ajourner 5 les opérations de mise à jour de mesure jusqu'à ce que la nouvelle demande soit ré Usée pour une information de la mémoire de réserve, moment où les tables de remplacement sont alors mises à jour automatiquement. On présente dans la figure 2 une comparaison tabulaire des façons respectives par lesquelles deux algorithmes de remplacement manipuleraient une 10 séquence très simple de demande de bloc ou page, l'un étant un algorithme de remplacement réel de la sorte déjà mentionnée, et l'autre étant un algorithme de remplacement "optimal", L'opération est divisée en une série d'"intervalles" numérotés chaque intervalle commençant juste avant le transfert d'un bloc d'information dans la mémoire de travail WM en réponse à une demande pour un 15 bloc qui ne s'y trouve pas actuellement. On suppose que la mémoire de travail est initialement libre de toute information et que le dispositif demande une série de blocs d'information selon la séquence BL1, BL2, BL3, BL4, BL5 BL2 Dans des buts d'illustration on suppose que la mémoire de travail a unecapa-cité de trois blocs. En pratique, la capacité de mémoire à vitesse rapide sera 20 de beaucoup supérieure. L'"algorithme de remplacement réel" que l'on utilise dans l'exemple présent est représenté sous forme de diagramme dans la figure 7 et les autres dessins de la présente demande de brevet. Sans rentrer dans les détails de l'algorithme de remplacement réel, il suffira de souligner maintenant que lorsque la mémoire de travail est remplie 25 complètement par les blocsBLI, BL2 et BL3 et qu'une demande est alors faite pour le bloc BL4 (intervalle n°4 figure 23 une décision doit être prise, pour remplacer l'un des trois autres blocs de la mémoire de travail. Dans ce cas le choix très probablement se portera sur le bloc qui est resté le plas longtemps dans la mémoire de travail sans avoir été récemment référencié c'est-à-dire le bloc BL1. Ainsi durant l'intervalle n°4 BL1 est remplacé par BL4, mainte-30 nant lorsque le bloc BL5 est demandé dans l'intervalle 5 un choix doit être fait entre le remplacement du bloc BL2 ou BL3. N'ayant aucune autre base pour choisir entre BL2 et BL3 l'algorithme de remplacement réel choisit BL2 ponr remplacement car BL3 a été référencié plus récemment que BL2. Ainsi dans l'intervalle 5 BL2 est remplacé par BL5. Cependant, ce choix se révèle avoir 35 été plus tard le mauvais du point de vue efficacité car à l'instant suivant, c'est-à-dire durantl'intervalle 6, le bloc BL2 est de nouveau demandé II est alors nécessaire de ramener BL2 de la mémoire de travail presqu'immédiatement après qu'il en a été sorti. 40 En rétrospective il aurait été mieux (suivant l'algorithme de remplacement 70 34360 10 2077507 optimal d'avoir remplacé le bloc BL3 ou BL1 au lieu du bloc BL2au moment où le bloc BL5 a été amené à l'intérieur, c'est-à-dire durant l'intervalle 5. Alors BL2 serait resté dans la mémoire de travail où il a été nécessaire plus tard, et le temps perdu à sa recherche dans la mémoire de réserve aurait été 5 épargné. Ainsi l'un des six transfertsde bloc effectués par l'algorithme de remplacement réel s'est révélé être non nécessaire et l'efficacité de remplacement de cet algorithme jusqu'à ce point n'est que de 63,3%. □n peut remarquer, cependant, qu'au commencement de l'intervalle 5, lorsque la décision de remplacement devait être réllement prise, il n'y avait 10 aucune donnée permettant de déduire logiquement que le remplacement du bloc BL3 ou BL1 était un meilleur choix que celui du remplacement du bloc BL2. Une telle connaissance a dû être acquise rétrospectivement, et elle n'aurait pu être avantageusement utilisée que si l'on était capable de retarderla prise de décision de remplacement nécessaire. Puisqu'il n'est pas réalisable 15 en pratique de retarder les prises de décisions de remplacement, unB telle décision doit être exécutée rapidement lorsqu'elle est demandée en accord avec l'algorithme de remplacement que l'on utilise réellement. A un moment plas tard on peut analyser les actions de remplacement de blocs lesplus récents et déterminer que l'algorithme de remplacement réel a demandé un transfert non 20 nécessaire, si il en est ainsi. Dans la présente description, chaque fois que les références sont faites à des blocs qui sont "remplacés" sous la commande de l'algorithme de remplacement optimal cela doit être compris comme signifiant un remplacement figuré plutôt qu'un remplacement de bloc exécuté littéralement. L'algorithme optimal cons-25 truit empiriquement à partir de décisions de remplacement qui ont été déjà faites dans le dispositif, détermine principalement, en effet des blocs qui auraient pu être retenus dans la mémoire de travail durant les opérations de remplacement exécutées précédemment, à la lumière de nécessités de référencia-tion de bloc en cours. De plus, l'algorithme optimal à la différence de 30 l'algorithme de remplacement réel peut, dans de nombreuses conditions reconnaître des options ou alternatives. Par exemple (en référence de nouveau à la figure 2) durant l'intervalle 4 de la séquence optimum, soit le bloc BLIsoit le bloc BL3 aurait pu être remplacé par le bloc BL4. De façon semblable, durant l'intervalle 5, l'algorithme optimal aurait été satisfait par le rempla-35 cernent soit de BL3 BL1 ou BL4 quel que soit celui quise trouve dans la mémoire de travail à ce moment. En d'autres termes, l'algorithme optimal nécessite que le bloc BL2 soit retenu dans la mémoire de travail jusqu'à ce qu'il puisse être référencié de nouveau durant l'intervalle 5 et la façon dont cela est réalisé n'est pas critique dans les conditions citées ici. Par commodité, 40 cependant, on pourra supposer dans la description qui suit que l'algorithme à j 70 34360 11 2077507 optimal en fait décide qu'un bloc particulier devrait Stre remplacé, mSme si plusieurs optiques peuvent exister dans cette considération. Dans certains cas, l'algorithme optimal peut aussi réduire réellement le choix jusqu'à un bloc particulier, cela étant l'occasion lorsque l'algorithme optimal définit un 5 "jeu complet", cela signifie une condition sous laquelle il alitait été possible, en suivant une configuration particulière de remplacement de bloc, d'avoir rempli la mémoire de travail jusqu'à sa capacité avec des blocs sélectionnés qui auraient tous pu être référenciés durant le môme intervalle ou à l'intérieur d'un nombre limité d'intervalle suivant (c'est-à-dire N-1 inter-10 valle lorsque N est la capacité de la mémoire de t ravail). On expliquera cela avec plus de détails ci-après. Si l'on désire connaître la séquence particulière par laquelle les blocs ont été demandés par le système de traitement durant l'exécution d'un programme spécifique, on peut déterminer le nombre minimum de remplacement de 15 bloc nécessité pour ce programme en utilisant un algorithm "MIN" décrit dans l'article mentionné ci-dessus intitulé "A Study of Remplacement Algorithms for a Virtual-Storage Computer" par L.A. Belady publié dans le IBM systems Journal vol. 5 N" i 1966, pages 70 - 101. Une telle détermination peut aussi être réalisée dynamiquement dans l'exécution du programme comme on le révèle 20 ici. La présente invention apporte un moyen de comparaison automatique du nombre des décisions de remplacement qui auraient été prises par un algorithme optimal hypothétique (dérivé de l'algorithme MIN cité déjà), et fondé sur l'information de référenciation de bloc mise à jour àe façon intermittente, avec le nombre de décisions de remplacement effectuées à des instants anté-25 rieurs, lorsque ces remplacements de blocs devraient effectivement se produire. Cette comparaison automatique estobtenue par utilisation d'une nouvelle façon d'engendrer des informations de référenciation de bloc significatives durant les intervalles entre les opérations de remplacement réelles. Comme déjà mentionné ici, et aussi expliqué avec plus de détail ci-après, le 30 procédé présent implique la génération d'indice mis en mémoire (ayant ici pour référence les bits R') pour identifier les blocs dans la mémoire à vitesse élevée qui sont référenciés par le système de traitement durant la partie d'un intervalle où aucun nouveau bloc n'est demandé à la mémoire de réserve par le système de traitement. La prochaine fois qu'un bloc est demandé à la 35 mémoire de réserve ce qui entraine l'exécution d'une interruption de machine du type connu comme "exception de page!* ou "exception de bloc", il y aura d'abord une opération de mise à jour très rapide où les bits de référence mis en mémoire (R') sont balayés avec les tables déjà mentionnées EC pour fournir les données déterminant le bloc qui aurait dû correctement être 40 présent dans la mémoire de travail à vitesse élevée WM à ce temps, lorsque â r 2Ô775Ô? l'opération de remplacement de blocs suivante la plus récente s'est produite, prenant en considération le numéro du bloc qui est demandé à la mémoire de réserve. Si ce numéro de bloc en cours de demande (ne se trouvant pas présentement dans la mémoire de travail) coïncide avec le numéro de l'un des blocs 5 qui aurait été laissé de façon continue dans la mémoire de travail par l'algorithme de remplacement optimal à partir de certaines opérations de remplacement de bloc précédentes, l'algorithme de remplacement réel est considéré alors comme ayant réalisé un transfert non nécessaire (figure 2). La figure 3 décrit la situation par laquelle certaines données utiles 10 peuvent être assemblées par le système de mesure efficace présent afin de déterminer les cas dans lesquels les décisions de remplacement optimum, si exécutées, auraient différé les décisions de remplacement effectuées réellement par l'algorithme que l'on utilise. Comme mentionné précédemment, l'algorithme de remplacement optimal est basé sur l'algorithme MIN décrit dans l'article 15 publié déjà cité de L.A. Qelady. On suppose dans l'exemple présent que la séquence selon laquelle les blocs sont demandés est BL1, BL2, BL3, BL4, BL5, BL2, BL4. Cette séquence ds demande de bloc diffère de l'exemple donné dans l'exemple 2 seulement par le fait que la séquence de la figure 3 comprend à sa fin une référence supplémentaire à BL4. 20 La "séquence réelle" d'opération de la figure 3 décrit le transfert de bloc et les opérations de référenciation sous la forme où elles sont réalisées effectivement. Par exemple, la notation "ENT.BL4^, remplace BL1" signifie que le bloc BL4 a été amené dans la mémoire de travail à l'adresse qui était précédemment occupée par le bloc BL1 "référence BL4" signifie que le bloc 25 BL4 peu après avoir été amené dans la mémoire de travail est référencié par l'unité de traitement centrale du calculateur, (figure 1) de telle sorte que l'information conservée dans BL4 puisse être lue et utilisée dans une opération de traitement de données, ou de telle sorte que BL4 puisse recevoir et emmagasiner la sortie d'une opération de traitement de donnéœ selon le cas. La 30 séquence d'opération optimale de la figure 3 décrit divers transferts de bloc et opération de référenciation qui peuvent être réalisés sous commande de l'algorithme de remplacement optimal afin d'exécuter la même séquence de référenciation de bloc avec des intervalles plus faibles (c'est-à-dire avec moins d'entréœ de bloc). La colonne "U" indique la valeur de la différence 35 entre le nombre des entrées de bloc nécessité par l'algorithme de remplacement réel et les entrées qui auraient été nécessaires pour l'algorithme de remplacement optimal. L'un des problèmes auxquels répond la présente invention est de déterminer de façon cumulative, et avec un retard aussi faible que possible si chacune 40 des décisions de remplacement prises effectivement par le système est en fait 70 34360 70 34360 13 2Ô77SÔ? la meilleure des décisions qui puissent être prise d'un point de vue efficacité global. Cette détermination est favorisée par le développement progressif de certaines variables appelées respectivement P,A,E,C et B que l'on définit ci-après, etqui sont utilisées comme indices pratiqua pour représenter l'état 5 comparatif des deux séquences opérationnelles. Comme dans le cas de la figure 2, chacune de ces séquences est représentée comme étant formée d'une série "d'intervalles" chaque intervalle commencçant lorsque le système de traitement central nécessite un bloc d'information ne se trouvant pas présentement dans la mémoire de travail et se poursuivant jusqu'au moment suivant où le système 10 de traitement nécessite un bloc qui n'est pas dans la mémoire de travail. Durant cet intervalle, le système de traitement peut se référencier une ou plusieurs fois des blocs localisés dans la mémoire de travail. Ces intervalles peuvent avoir des durées \a riables selon le nombre d'actions de référencia-tions de blocs réalisées à l'intérieur de chaque intervalle. La performance 15 de l'algorithme de remplacement réel est comparé avec celui de l'algorithme de remplacement optimal en notant la différence entre les nombres respectifs d'intervalles dans les deux séquences, cette différence en règle, étant le compte de transfert non nécessaire. (U). Il reste maintenant à expliquer la procédure spécifique par laquelle selon 20 les enseignements de la présente invention, on peut arriver à la détermination qu'un des intervalles "réels" par exemple intervalle 6 figure 3 est un intervalle "non nécessaire" du point de vue de remplacement optimal. Une question attenante dont on remet la discussion à plus tard dans cette description, est de savoir comment la détermination citée ci-dessus peut être réalisée 25 efficacement, cela signifie sans gêner inutilement le fonctionnement machine. Il est évident que l'intérêt de mesurer l'efficacité d'un algorithme de remplacement serait faible si le procédé de mesure d'efficacité lui-même devait consommer une quantité de temps exagérée du système de fonctionnement machine. L'un des objets importants de la présente invention est de permettre 30 de réaliser la mesure d'efficacité de façon efficace aussi bien que précise. Dans la table des opérations, figure 3, comme mentionné ci-dessus, certaines valeurs variables représentées par les symboles P, A, E, C, B et U sont développées lors de la progression du fonctionnement. P est le nombre d'extractions", c'est-à-dire le nombre de fois où des 35 blocs d'information ont été extraits de la mémoire de réserve en réponse à des demandes. C'est aussi le nombre d'intervalles de la séquence réelle d'opérations. A est le nombre d'intervalles dans la séquence optimale d'opérations, ou le nombre de fois où il aurait été nécessaire d'extraire des blocs d'infor-40 mation de la mémoire de réserve si l'on avait suivi l'algorithme de rempla- â 70 34360 2Û775Ô7 cernent optimal. E est une valeur d'index pouvant être augmentée, assignée à chaque numéro de bloc adressable, correspondant en général au numéro de l'intervalle dans lequel le bloc aurait été soumis à référence le plus récemment si l'algorithme 5 de remplacement optimal avait été suivi. C est une valeur de comptage pouvant être diminuée par quantités fixes a chacun des intervalles de la séquence optimale d'opérations la première fois qu'un bloc est soumis à référence dans cet intervalle. Initialement la valeur C est N-1 où N est le nombre des blocs qui peuvent être simultanément conser-10 vés dans la mémoire de travail. Ensuite la valeur C pour chaque intervalle "optimal" peut être réduite de 1 pour chaque bloc séparé auquel il est référé ici mémoire de travail à un moment correspondant à cet intervalle. Lorsqu'une valeur C passe d'une valeur supérieure à O.cela indique que tous les blocs N de la mémoire de travail ont fait l'objet d'une référence à cer-15 tains moments durant une période comprenant l'intervalle correspondant et pas plus de N-1 d'intervalles successifs de la séquence optimum. Dans chaque cas où C passe 0, un "jeu complet" de référencœ aux blocs est défini pour cet intervalle. La valeur C d'un intervalle n'est significative que lorsqu'elle est réduite à zéro, moment auquel elle exclut toute autre considération du 20 système de mesure d'efficacité, ces événements qui se produisent durant l'intervalle avant la définition de ce "jeu complet" .Le système commence alors à chercher le nouveau "jeu complet" qui doit être défini dans un intervalle ultérieur. La signification du terme "jeu complet" deviendra plus compréhensible au cours des descriptions. 25 B est une valeur indicatrice qui lorsqu'elle dépasse la valeur de départ aribtraire de 1 indique le numéro de l'intervalle le plus récent dans lequel l'algorithme de remplacement optimal aurait défini un jeu complet de références aux blocs. Comme on l'expliquera en détail ci-après la relation entre les valeurs E et B est un facteur important dans certaines des décisions logiques 30 qui sont effectuées dans le système de mesure. U est le compte des transferts non nécessaire. Habituellement il est égal au nombre des "extractions" CP] réalisé par l'algorithme de remplacement actuel moins le nombre [A) qui aurait été nécessaire à l'algorithme de remplacement optimal. Dans certains cas, cependant,gette relation est modifiée par un fac-35 teur G), "d'incertitude", dont la nature sera expliquée ci-après. En référence de nouveau à la figure 3, les opérations réalisées sous la commande de l'algorithme de remplacement réel (partie gauche de la figure) sont identiques à celles qui auraient spécifiées par l'algorithme de remplacement optimal (partie droite de la figure) durant les quatre premiers intervalles 40 dans les deux séquences. (La mémoire de travail pour le rappel est supposée 70 34360 15 2077507 avoir une capacité de trois blocs dans la description actuelle). Durant l'intervalle 5, lorsqu'il doit faire le choix entre remplacer soit le bloc BL2 soit le bloc BL3 afin de faire de la place pour l'entrée du bloc BL5, l'algorithme de remplacement réel décide de remplacer BL2 puisque BL3 a été 5 référencié plus récemment. Cependant, durant l'intervalle 6 qui suit immédiatement, l'algorithme de remplacement réel trouve qu'il est maintenant nécessaire de transférer de nouveau BL2 dans la mémoire de travail, remplaçant cette fois-ci BL3. L'algorithme de remplacement optimal dans lequel on ne demande pas de 10 prendre la décision de remplacement en même temps que l'algorithme de remplacement réel, attend la demande pour le bloc suivant, le bloc BL5 avant de décider lequel des blocs se trouvant alors dans la mémoire de travail doit être désigné pour remplacement au moment où BL5 entre dans la mémoire. Ainsi, l'algorithme optimal indique qu'il aurait retenu BL2 et non BL3 dans la mémoire 15 de travail durant l'intervalle 5, sachant que BL2 aurait été demandé immédiatement après BL5. On doit comprendre naturellement que l'algorithme de remplacement optimal [étant construit empiriquement "après coup" pour ainsi dire) ne peut pas effectuer réellement le remplacement d'un bloc dans la mémoire de travail. La notation "remplacer BL3" dans l'intervalle 5 de la séquence optima-20 le figure 3, signifie que cela est l'opération de remplacement de bloc qui aurait été réalisée durant l'intervalle 5 si le système de traitement de donnée avait pu retarder son action de remplacement de bloc déjà citée suffisamment longtemps pour s'assurer que BL2 serait le bloc suivant demandé par le système de traitement central après la référence au bloc BL5. En pratique, naturslle-25 ment il n'est pas possible de retarder les décisions de remplacement de cette façon, et ainsi l'opération de remplacement de bloc doit être réalisée selon toutes les règles qui peuvent avoir été sélectionnées par l'opérateur pour diriger ces choix. Pour récapituler, l'algorithme de remplacement réel amène la référence 30 à BL2 durant l'intervalle 6 (c'est-à-dire suivant la sixième interruption d'exception de bloc du système de traitement), alors que l'algorithme optimum aurait permis la référence à BL2 durant le cinquième intervalle ce qui aurait évité la nécessité d'une sixième interruption dans des buts de remplacement de bloc. Ainsi l'opération de remplacement réelle a une efficacité inférieure 35 à l'efficacité optimum du fait de cet appel pour ce sixième remplacement, et un compte "U" de 1 est en conséquence enregistré contre lui. Comme étape finale dans la séquence de références aux blocs représentée dans la figure 3, le système fait référence au bloc BL4, qui dans chacune des séquences d'opération se trouvera dans la mémoire de travail. Donc dans les 40 deux cas il est référé simplement à BL4 dans la mémoire de travail sans néces- â à 70 34360 16 2Ô77S01 siter une opération de remplacement de bloc. On peut remarquer cependant, une différence par le fait que durant le sixième intervalle de la séquence réalisée, seulement deux des trois blocs actuellement emmagasinés dans la mémoire de travail sont l'objet d'une référence (BL2 et BL4), alors que dans la séquence 5 optimale les trois blocs effectivement emmagasinés dans la mémoire de travail (BL2, BL4, BL5) sont l'objet d'une référence. Ainsi on peut dire qu'un "jeu complet" de références a été défini pour l'intervalle 5 de la séquence optimale. Ce fait devient significatif si la séquence de référence doit être poursuivie avec des demandes de bloc supplémentaires tant que l'apparition de chaque 10 nouveau "jeu complet" signale un nouveau point de départ dans le procédé de détermination des choix de remplacement de bloc optimal. La détermination optimisée "oublie" effectivement toute demande de bloc qui peut avoir été faite avant la formation du "jeu complet" actuel. Considérons maintenant la façon par laquelle diverses tables de données 15 représentées par les colonnes appelées P,A,E,C et , figure 3 peuvent être progressivement construites à l'aide du système afin de faciliter la mesure de l'efficacité de remplacement de l'exemple illustré. (Ces variables P,A,E,C et B seront concernées aussi dans la description plus détaillée du système qui suit cette description générale). P est simplement le compte des rempla-20 cements de bloc réalisés par le système, et est identique au nombre d'intervalles réel. De façon semblable, A est le compte des remplacements de blocs optimaux ou le nombre d'intervalles optimal. E est une valeur incrémentale attribuée à chaque blac et indiquant le numéro de l'intervalle dans lequel il aurait fait l'objet de la référence la plus récente selon l'algorithme de 25 remplacement optimale. Dans le cas du bloc BL2, par exemple, la valeur E fixée initialement à ce bloc est 2, cette valeur étant le numéro de l'intervalle dans lequel BL2 a fait l'objet d'une référence pour la première fois. Ainsi lorsque BL2 fait de nouveau l'objet d'une référence durant l'intervalle optimal 5 (correspondant à l'intervalle réel 6) la valeur E de BL2 est amenée à 30 5. De façon semblable lorsque BL4 fait une seconde fois l'objet d'une référence durant l'intervalle optimal 5 (intervalle 6) sa valeur E est amenée de 4 à 5. La valeur de E de BL5 est déjà 5, de là on a maintenant un jeu complet de blocs portant tous des valeurs E égales à 5 dans l'intervalle optimal 35 de numéro 5. Il serait approprié à ce moment de considérer brièvement la signification d'un "jeu complet".Habituellement la fonction de l'algorithme de remplacement optimal est de considérer les remplacements de bloc qui ont été effectués effectivement par l'algorithme de travail et de déterminer si les blocs rem-40 placés auraient dû être retenus dans la mémoire de travail afin de pouvoir £ A 70 34360 17 2Ô7?597 être utilisés pour des références futures. Intuitivement, on peut reconnaître que ce procédé n'est utile que dans certaines limites pratiques, au-delà desquelles on recherche le gain inutile et il n'y a rien à gagner en amenant le système à rechercher encore dans l'histoire la suite de références aux 5 blocs pour voir si une collection plus parfaite des blocs aurait pu être assemblée dans la mémoire de travail. En identifiant un "jeu complet" on établit par là un état dans lequel tout bloc référencé précédemment qui n'est pas un élément de cet ensemble, lorsqu'il est demandé par le système de traitement, est traité comme s'il était un nouveau bloc, et maintenant demandé pour la 10 première fois, ce qui évite au système de considérer ce qui aurait pu se produire si ce bloc avait été conservé précédemment au lieu d'avoir été remplacé. Cela réduit de façon importante les recherches qui doivent être effectuées et rend réalisable les calculs de remplacement optimal dans les temps limités alloués à ce but. Ainsi en un sens, la formation de chaque "jeu complet" signifie un 15 nouveau départ dans la procédure de détermination de la configuration de remplacement optimale pour les demandes de bloc futures. La valeur C initialement attribuée à chaque intervalle de la séquence optimale (au moment où un bloc fait pour la première fois l'objet d'une référence dans cet intervalle)est égale à 2, c'est-à-dire un de moins que la 20 capacité d'emmagasinage de bloc, de la mémoire de travail. Ainsi dans la figure 3, une valeur initiale C de "2" est attribuée à l'intervalle 5 au moment où BL5 fait l'objet d'une référence. Lorsque BL2 fait à son tour l'objet d'une référence, la valeur C de l'intervalle 5 est diminuée de 1. Simultanément à cette action les valeurs C de tous les intervalles précédents jusqu'à l'in-25 tervalle 2 exclusivement, sont diminuées de 2 à 1. La diminution des valeurs C des intervalles 3 et 4 à 1 est sans signification à ce moment particulier, indiquant principalement qu'il aurait été possible sous certaines conditions qui ne se matérialisent pas réellement de définir un "jeu complet" comprenant BL2 soit dans l'intervalle 3, soit l'intervalle 4. Cette information n'a 30 maintenant qu'un intérêt académique. Cependant, la diminution de C de 2 à 1 dans cette partie de l'intervalle 5 lorsque BL2 fait l'objet d'une référence est très significative car lorsque BL4 fait l'objet d'une référence durant une partie ultérieure de l'intervalle 5 de la séquence optimale la valeur C de l'intervalle 5 est réduite à zéro, ce qui définit un "jeu complet" pour 35 l'intervalle 5. End'autres termes, si les décisions de remplacement de bloc optimal avaient été en fait exécutées, on aurait atteint un état dans le cinquième intervalle caractérisé en ce que N blocs demandés aurait pu avoir été référencés dans la mémoire de travail sans qu'il soit nécessaire d'amener l'un de ces blocs dans la mémoire de travail dans ce but. On considère cela 40 comme étant un état l'efficacité optimale. * 70 34360 10 2077507 □ans le schéma considéré, comme on l'expliquera avec plus de détail ci-après, les déterminations de ce qui pourrait constituer des opérations de remplacement optimal sont réalisées progressivement d'un intervalle de "jeu complet" à l'intervalle "jeu complet" suivant, l'intervalle 1 étant traité 5 arbitrairement comme le premier intervalle jeu complet dans ce but. Ainsi dans chaque nouvel intervalle suivant l'intervalle 5, la valeur C pour cet intervalle est initialement réglée à 2, et le système recherche les états à développer pour que les valeurs C puissent être diminuées à zéro selon la logique expliquée ci-dessus, ce qui permet de définir un nouvel intervalle 10 jeu complet. Chaque fois qu'un jeu complet est défini, la valeur de B est égale au numéro de l'intervalle optimal dans lequel un tel ensemble est trouvé exister. B devient alors un point de référence ou indicateur, avec lequel les valeurs E des divers blocs demandés sont comparées dans divers buts qui seront expliqués dans la description détaillée suivant la présente description 15 générale. Chaque fois qu'un jeu complet est défini comme durant l'intervalle 5 dans la séquence maximum (figure 3) cela peut entraîner l'augmentation de la valeur de P (le numéro d'intervalle réel) plus rapidement que celle de A (le numéro optimal maximum). Ainsi dans l'exemple présent, le numéro d'intervalle réel P 20 augmente de 5 à 6 alors que le numéro d'intervalle optimum A reste à 5. Chaque fois que la marche de P par rapport à A augmente, le compte de transfert non nécessaire U est augmenté, puisque U est la différence entre P et A. Dans ce cas particulier les intervalles 5 et B de la séquence réelle sont dits être "contemporains" avec l'intervalle 5 de la séquence optimale. Il est possible 25 d'avoir plusieurs intervalles réels "contemporains" avec un intervalle optimal unique, selon les conditions particulières qui sont rencontrées à ce moment. Ainsi dans l'exemple présent où la capacité N de la mémoire de travail est supposée être de trois blocs, il est passibled 'avoir de un à trois intervalles de la séquence réelle contemporains avec un intervalle unique de la séquence 30 optimale.(Un cas de trois intervalles contemporains sera considéré plus tard avec l'exemple représenté dans la figure 5). Les figures 4A et 4B décrivent un exemple plus compréhensif que ceux traités dans les figures 2 et 3 respectivement. Dans cet exemple, on suppose que la séquence de référenciation de blocs suivante se produit. (La capacité de 35 mémoire N étant de trois blocs comme précédemment). BL1 BL2 BL3 BL4 40 BL5 à 70 34360 19 2077597 BL2 BL4 [altérer BL4) BL1 BL6 5 BL1 BL2 BL4. L'algorithme de remplacement que l'on suppose être "l'algorithme de remplacement réel" dont l'efficacité est mesuré donne à tout bloc de la mémoire 10 de travail dont les contenus ont été altérés un statut qui est différent de celui des blocs non altérés emmagasinés dans la mémoire de travail à ce moment. Un système agissant dans cet algorithme peut choisir entre le remplacement d'un bloc qui a été altéré et d'un bloc qui n'a pas été altéré, et choisit le bloc non altéré pour remplacement, pour la raison qu'un duplicata du bloc non altéré 15 se trouve déjà dans la mémoire de réserve, ce qui évite d'écrire un tel bloc dans la mémoire de rfiserve lorsqu'il est retiré de la mémoire de travail. Dans le cas d'un bloc qui a été altéré pendant son séjour dans la mémoire de travail cependant, l'information contenue dans ce bloc est unique et lorsqu'un tel bloc doit être remplacé dans la mémoire de travail, son contenu doit être écrit 20 à l'adresse l'adresse correspondante de la mémoire de réserve à la place du contenu original de ce bloc. Puisque l'opération d'écriture d'un bloc d'information dans la mémoire de réserve à vitesse faible prend plus de temps que la sur-impression simple d'un bloc dans la mémoire rapide, on donne habituellement la préférence au bloc altéré pour la décision concernant les blocs qui 25 doivent être maintenus dans la mémoire de travail durant une opération de remplacement. On suppose dans l'exemple que BL4 a ce statut préférentiel. Ce fait "altération" de l'algorithme de remplacement que l'on vient de décrire peut amener la conservation d'un bloc altéré tel que BL4 dans la mémoire de travail bien au-delà du temps où il aurait été autrement remplacé. 30 Par suite il est possible que le bloc soit déjà dans la mémoire de travail la fois suivante où il est demandé même si l'algorithme de remplacement optimal (qui n'accorde pas un statut spécial au bloc altéré) pourrait demander le remplacement de ce bloc durant la période intervenant entre des demandes successives pour un tel bloc. Cela crée une situation spéciale dans laquelle il est 35 possible que l'algorithme de remplacement réel agisse plus efficacement que l'algorithme de remplacement optimal durant une phase particulière d'une séquence de références aux blocs. On considérera un cas de cette sorte dans la description qui suit. Jusqu'au moment où l'altération du bloc BL4 (figure 4A) se produit dans 40 la séquence des opérations que l'on considère actuellement, le système se 70 34360 20 20775Ô7 comporte dans la façon décrite dans la figure 3.Ensuite lorsque BL4 est altéré par le système de traitement, son bit "d'altération" correspondant (emmagasiné dans la mémoire associative AM, figure 1) est réglé à 1. Cette fonction sera décrite avec plus de détail ci-après. Durant l'intervalle suivant (7 dans la 5 séquence réelle : 6 dans la séquence optimale, figure 4BJ, le bloc BL1 est demandé par le système de traitement et est amené dans la mémoire de travail WM remplaçant BL5 qui est le bloc le plus ancien actuellement dans WM. Ensuite durant l'intervalle suivant (8 dans la séquence réelle j 7 dans la séquence optimale), le bloc BLB est demandé par le système de traitement et est amené 10 dans la mémoire de travail. A ce moment, un choix critique doit être effectué entre BL2 et BL4 lors de la sélection d'un bloc à remplacer par le bloc arrivant BLB. Ordinairement si BL4 n'était pas altéré, il serait choisi pour remplacement car il est le bloc le plus ancien se trouvant maintenant dans la mémoire de travail. Cependant, l'algorithme de remplacement que l'on utilise 15 réellement dans ce cas "négligera" le bloc altéré BL4 pour le remplacement et amènera le remplacement du bloc BL2 par BLB. L'algorithme optimal d'autre part, aura choisi BL4 comme le bloc à remplacer retenant BL1 et BL2 dans la mémoire de travail du fait que BL1 et BL2 vont être directement référenciés après BL6. (L'algorithme optimal, on doit le rappeler, peut retarder ces décisions de 20 remplacement jusqu'à ce qu'il voit quels blocs vont être référencés immédiatement après). On doit expliquer que chaque fois que l'algorithme optimal est décrit ici comme "remplaçant" un bloc, on ne doit considérer cela que comme un remplacement figuré ou symbolique. Ce qui arrive réellement est que l'algorithme 25 optimal désigne quel bloc aurait dû être retenu dans la mémoire de travail d'après les règles de sa propre logique et à partir de cette information, on peut déduire quel bloc l'algorithme optimal aurait remplacé s'il avait été l'algorithme de travail réel. Donc dans l'intervalle 7 de la séquence optimale on peut tirer la conclusion que l'algorithme optimal aurait remplacé BL4, s'il 30 avait eu le pouvoir de le faire, du fait que BL2 est représenté comme étant encore présent dans la mémoire de travail durant l'intervalle 7 de la séquence optimale. Par conséquent, lorsque BL2 est demandé par le système de traitement, l'algorithme optimal n'aurait pas trouvé nécessaire d'initier un nouvel intervalle (c'est-à-dire une opération de remplacement de bloc) afin d'obtenir 35 BL2 dans la mémoire de travail. Ainsi, la valeur A reste inchangée lorsque BL2 est demandé par un système de traitement. Cependant, l'algorithme réel a trouvé nécessaire d'initier un nouvel intervalle (9) lorsque BL2 est demandé, afin d'amener BL2 dans la mémoire de travail. Ainsi P est augmenté à 9, alors que A reste à 7 et le compte U en conséquence est porté à 2. De plus, un nou-40 veau "jeu complet" de référence de bloc est défini (BLB, BL1, BL2) dans l'in- à 70 34360 21 2077507 tervalle optimal 7, et la valeur de B en conséquence est augmentée de 5 à 7. Il est significatif de remarquer que le système de mesure présent[qui utilise un algorithme de remplacement optimal qui est très proche mais n'est pas nécessairement identique à l'algorithme MIN déjà mentionné), reconnaît 5 les implications résultant du fait de permettre qu'un bloc tel que BL4 qui est un élément de jeu complet précédent (intervalle 5) reste continuellement dans la mémoire de travail où il peut être référencé facilement à la fin de l'intervalle 9 même si il n'est pas un élément du ernier jeu complet défini par l'algorithme optimal (intervalle 7 de la séquence optimale) figure 4B. Le 10 système de traitement, s'il il lui arrive de demander ce bloc particulier à ce moment, trouvera le bloc prêt dans la mémoire de travail lorsque, selon la logique de l'algorithme optimal, il n'aurait pas dû s'y trouver. Donc dans ce cas particulier, l'algorithme de remplacement réel aura travaillé plus effi- * cacement que l'algorithme de remplacement optimal. Le système de mesure 15 d'efficacité donne crédit à l'algorithme de remplacement réel après avoir réalisé cela en dimunant le compte U et en augmentant le compte A, ce qui permet uns mesure vraie de l'efficacité de remplacement. Ce type d'action est représenté dans la dernière partie de l'intervalle 9 figure 4B. Ayant demandé BL4 et l'ayant trouvé prêt dans la mémoire de travail à un moment où selon la logique de 20 l'algorithme de remplacement optimal il n'aurait pas dû y être le système de traitement fait référence à ce bloc sans appeler une action de remplacement de bloc. Ensuite, suivant la logique de l'algorithme de mesure d'efficacité le système de traitement diminue le compte U de 2 à 1 et augmente le compte A de 7 à 8. Ainsi, on donne crédit à l'algorithme de remplacement réel pour avoir 25 évité une action de remplacement de bloc que l'algorithme optimal aurait trouvée nécessaire afin d'atteindre le même point dans le programme. Afin de détecter la possibilité d'une situation de cette sorte le système de mesure utilise un indicateur qui est enclenché chaque fois que la variable E d'un bloc actuellement localisé dans la mémoire de travail reste à une 30 valeur au moins égale à la valeur précédente de B mais inférieure à la nouvelle valeur deB, comme dans le cas présent où la valeur de BL4 est restée à 5 alors que la valeur de B est passée de 5 à 7. Cet état dénote que BL4 est resté dans la mémoire de travail depuis avant la formation de jeu complet actuel et par conséquent ne devra pas être transféré à partir de la mémoire de soutien 35 afin de pouvoir être obtenu pour référenciation ultérieure dans la mémoire de travail, même si BL4 n'est pas un élément de jeu complet actuel (BL6, BL1 BL2) qui a été défini effectivement par l'algorithme de remplacement optimal. L'indicateur que l'on vient de mentionner est ici appelé un "bit "L", il y a un de ces bits dans chacune des rangées mise dB mot de la mémoire associative AM. Le réglage d'un bit L à 1 conditionne le système pour diminuer le compte U ê 70 34360 22 ; 207710? si le bloc en question doit être soumis à référence par le système de traitement avant qu'un tel bloc quitte la mémoire de travail. Ainsi lorsque le bit L de BL4 est réglé à 1 durant l'intervalle 9, figure 4B, cela conditionne le système pour diminuer le compte U dans le cas où BL4 est référencié alors qu'il 5 se trouve encore dans la mémoire de travail. Cette action sera expliquée avec plus détail dans la description qui suit. L'exemple suivant montre que les actions de remplacement et les assemblages de bloc qui sont prescrits par l'algorithme de remplacement optimal ne sont que des transactions symboliques ou fictives et n'ont aucun effet physique sur 10 les travaux de l'algorithme de remplacement réel qui agit librement. Ainsi dans l'intervalle 7 de la séquence optimale, figure 4B, il apparaîtrait qu'un jeu complet de bloc BLB, BL1, BL2 occupe simultanément la mémoire de travail. En fait, cependant, un tel jeu complet n'a jamais existé. Durant l'intervalle contemporain 8 de la séquence réelle des opérations, la mémoire de travail est 15 occupée par les blocs BL6, BL1, BL4 et durant l'intervalle contemporain 9, elle est occupée par les blocs BL2, BL1 et BL4. L'algorithme optimal ignore simplement la présence de BL4 puisqu'il n'était pas logiquement présent dans la mémoire de travail.. L'utilisation du bit "L" comme décrit brièvement ci-dessus et plus complètement ci-après permet la reconciliation de logique de l'algo-20 rithme de remplacement optimal avec la situation réelle dans ces cas occasionnels où une différence peut exister. L'exemple représenté dans la figure 5 révèle une caractéristique supplémentaire de l'algorithme de remplacement optimal,c'est-à-dire qu'un jeu complet peut être défini pour un intervalle particulier de la séquence optimale 25 même si les blocs de ce jeu complet ne sont pas tous soumis à référence durant cet intervalle. La capacité de mémoire de travail N, est supposée être de trois blocs comme dans les exemples précédents. Les blocs sont soumis à référence dans l'ordre suivant : BL1 30 BL2 BL3 BL4 BL5 BL2 35 BL3 BLB BL1 BL2 BL7 40 BL4 70 34360 23 2077507 BLB Durant l'intervalle 7 de la séquence optimale, correspondant aux intervalles contemporains 9 et 10 de la séquence réelle, un "jeu complet" de blocs BL6, BL1 et BL2 peut être supposé exister. Cependant, ce fait ne sera pas apparent jusqu'à l'intervalle 9 de la séquence optimale, où BL6 est de nouveau 5 soumis à référence. Le point que l'on doit observer ici est que l'algorithme de remplacement optimal si il avait commandé le système aurait assemblé durant l'intervalle 7 un ensemble de blocs BL6, BL1 et BL2, qui aurait été soumis à référence avant de quitter la mémoire de travail durant la période occupée par l'intervalle 7 à 9 de la séquence optimale, ce qui veut dire durant une période 10 de N intervalles optimaux commençant avec l'intervalle 7. La table C reconnaît ce fait en amenant la diminution à 0 de la valeur C de l'intervalle 7 au moment où BL6 est demandé par le système de traitement au commencement d'un intervalle 13 de la séquence réelle, qui est contemporaine avec l'intervalle 9 de la séquence optimales Attendu que c'est la valeur C de l'intervalle 7 qui est 15 passée à 0, la valeur de l'indicateur B est restaurée à "7" même si une telle action ne se produit pas jusqu'à l'intervalle 9 de la séquence optimale, (N-1 intervalle plus tard). "7" devient maintenant la nouvelle valeur de référence de jeu complet à laquelle les valeurs indexe "E" des blocs demandés sont comparées et/ou mises à jour. 20 Description détaillée d'un mode de réalisation préféré. La réalisation préférée illustrée dans les figures 6 et suivantes représente l'invention sous la forme où elle sera utilisée pour mesurer l'efficacité de l'algorithme de remplacement de page ou de bloc décrit dans la demande de brevet déjà citée déposée en France le 5.12.1966 et obtenue sous le n° 25 1 509 223. le principe de l'invention n'est pas limitée à la mesure de l'efficacité d'un algorithme de remplacement unique, cependant, et aucune conclusion ne doit être tirée au fait que les dessins représentent un appareil conçu apparamment dans ce but particulier. Certaines parties du système illustré qui correspondent ou concernent 30 des schémas de remplacement de Nelson sont identifiées dans la figure 6 et les dessins suivante à l'aide de symboles de synchronisation ou opérationnels qui portent le préfixe "T" (par exemple TO, T5, T6). Les parties du système que l'on décrit ici et concernant uniquement le concept de mesure d'efficacité présent sont identifiées par des symboles opérationnels portant le préfixe "ME" 35 (par exemple ME 1, ME8, ME66). L'algorithme de remplacement réel, (c'est-à-dire l'algorithme de remplacement de Nelson dans ce cas) fonctionne librement, l'opération de mesure d'efficacité étant réalisée de façon telle qu'elle n'en-traine pas un retard significatif surles opérations de remplacement réelles. L'algorithme de remplacement de Nelson dont le fonctionnement est illustré â 70 34360 24 ; 2077507 sous forme de diagramme dans la figure 7, choisit en général pour remplacement l'un des blocs qui n'a pas été récemment soumis à référence et qui n'a pas été altéré durant son séjour dans la mémoire de travail. Tout bloc qui a été récemment soumis à référence est, en règle générale habilité à rester dans la 5 mémoire de travail sans considération du temps qu'il peut y avoir passé avant un tel appel. Si un bloc est altéré lorsqu'il est au mis à référence il acquiert un statut spécial qui l'habilite à rester dans la mémoire de travail tant que la mémoire contient au moins un bloc non altéré qui n'a pas été récemment soumis à référence. Lorsque le "bit de référence" (bit R] associé avec un bloc 10 a une valeur de 1, cela indique que le bloc a été récemment soumis à référence. Lorsque les bits R de tous les blocs de la mémoire de travail ont atteint un état "1" ils sont tous restaurés automatiquement à "0" et dans ces conditions il n'est pas possible de dire quel bloc a été le plus récemment soumis à référence. En ce cas aucun n'est supposé avoir été récemment soumis à réfé-15 rence. L'altération d'un bloc est indiquée par le réglage de son "bit d'altération" [bit AL) à "1". Aucun bloc dont le bit AL est 1 ne peut être remplacé tant que la mémoire de travail contient un bloc dont les bits AL et R sont zéro. Si tous les blocs non altérés, ont leurs bits R = 1, le système choisit alors pour remplacement un bloc ayant sont bit AL réglé à 1 et son bit R réglé 20 à 0. Du au fait que les bits R du bloc ne peuvent tous conserver un état "1", comme expliqué ci-dessus, il y aura au moins un bloc dont le bit R est zéro. Lorsqu'un bloc quitte la mémoire de travail, les bits AL et R associés avec chaque adresse de travail sont restaurés à 0. Le fonctionnement de cet algorithme de remplacement particulier sera expliqué avec plus de détail ultérieurement 25 en référence à la figure 7. On doit faire attention de ne pas confondre les bits R mentionnés ci-dessus avec l'autre type des bits de référence appelés ici les bits R*. Le bit R et le bit R' associés à l'adresse de travail d'un bloc sont tous les deux réglés à un la première fois que ce bloc est soumis à référence après son 30 entrée dans la mémoire de travail, et chaque référence ultérieure à ce bloc laisse en règle générale ses bits de référence R et R' dans leur état "1". Cependant, ces bits R et R' ne sont pas toujours réglés à 1 ou restaurés à 0 simultanément. Un bit "R 1" sera restauré automatiquement à 0 si, et lorsque les bits R associés avec tous les autres blocs de la mémoire de travail at-35 teignent un réglage à 1. Les bits R' ne sont pas restaurés dans de telles conditions. Lorsqu'un remplacement de bloc est réalisé, le bit R' des blocs restants dans la mémoire de travail sont finalement restaurés à 0 si ils n'ont pas déjà cette valeur, mais les bits R de tels blocs ne sont pas affectés par cette action. Les fonctions respectives des bits R et R' serant implicités 40 au cours de la description. â 70 34360 25 2Û7?5Q7 Certains des symboles et des termes utilisés dans la présente invention ont été employés avec des significations différentes de celles de la demande de brevet déjà cité deNelson. Par exemple, le symbôle"A", qui dans la présente invention représente le nombre des intervalles réels de la séquence optimale 5 des opérations a été utilisé dans le brevet cité 1 509 223 comme représentant la valeur du "bit d'altération". Pour éviter la confusion la valeur du bit d'altération est ici appelée "AL" au lieu de "A" comme on l'a déjà mentionné, la système da remplacement de Nelson utilise certains bits de référence qui sont désignés par le symbâle "R", alors que l'on utilise dans le système 10 présent des bits de référence supplémentaires ayant une fonction quelque peu différente, celle-ci étant désignée par des bits R'. D'autres modifications de la nomenclature de Nelson seront soulignées spécifiquement ci-après. Comme introduction à la description plus détaillée du système qui suit» on se réfère maintenant à la description générale du système représenté dans 15 la figure 6, qui représenta l'application de la procédure d'efficacité (identifiée par les symbSles ME] au schéma de remplacement réel (c'est-à-dire décrit dans le brevet cité (identifié par les symbôles "T"). Sur la figure 6, les différentes étapes de l'opération sont représentées par des rectangles et les opérations élémentaires constituées par chacune 20 de ces étapes peuvent être brièvement décrites comme suit : 500 Le bloc demandé est-il dans la mémoire de travail ? 501 Utilisant les bits R' en mémoire, mettre à jour les valeurs de P,A,E,C,B,U,L, et Q chaque fois que nécessaire. 502 Entrer le bloc demandé dans WM à l'adresse de travail choisie 25 par l'algorithme de remplacement réel, ce bloc remplaçant le bloc s'y trouvant primitivement, régler les bits R' et L correspondant à 0. 503 Mettre en mémoire numéro de bloc et le bit L dans le registre "Maintien". 30 504 Placer l'adresse de travail dans position LH de MAR de WM et l'adres se du bloc dans la partie RH de MAR de WM. 505 Mettre à jour les bits de référence (R) et d'altération (AL) dans le mot de la mémoire associative correspondant à l'adresse de travail du bloc demandé . 35 506 Si bit "L" du bloc demandé = 1, régler les valeurs A et U en conséquence. Dans tous les cas régler le bit du mot de la mémoire associative correspondant à 1. En comparant la figure 6 avec la figure 1, chaque action de référenciation de bloc du système est initiée par une demande de mémoire provenant de l'unité de traitement centrale CPU. Cette 40 demande est dirigée vers la partie du système représentée en général par le 70 34360 26 : 2077507 rectangle ou boîtier 500, figure 6 qui réalise l'étape initiale consistant à déterminer si le bloc demandé est ou n'est pas dans la mémoire de travail. Si le bloc demandé n'est pas présent dans la mémoire de travail l'action suit la ligne de branchement 1000 de l'organigramme versl'étape.501 qui représen-5 te une procédure de mise à jour qui est réalisée chaque fois qu'un bloc doit être transféré de la mémoire de soutien à la mémoire de travail. En utilisant les bits de référence mis en mémoire R' (dont la nature sera décrite plus complètement ci-après) le système met à jour automatiquement les variables représentées par les symboles P,A,E,C,B,U,L,Q respectivement qui sont utilisées 10 dans le procédé de mesure d'efficacité cité ci-dessus dans lequel une comparaison est réalisée entre le nombre des remplacements de bloc réellement effectués et le nombre des remplacements qui auraient été spécifiés par l'algorithme de remplacement optimal. Les fonctions de la plupart de ces variables ont été expliquées de façon générale ci-dessus. La valeur "t}'' est un indica-15 teur "d'incertitude" dont le but sera expliqué au moment approprié de la description suivante. Lorsque l'étape de mise à jour de valeur 501 figure B, a été réalisée, selon les conditions qui ont été rencontrées, l'action se poursuit soit par la ligne d'ordinogramme 1004 ou 1006 vers l'étape 502 ce qui entraine la ren-20 trée du bloc demandé dans la mémoire de travail à une adresse qui est sélectée par l'algorithme de remplacement. Par le remplacement du bloc qui précédemment était mis en mémoire à cette adresse de travail, les bits R' et L associés avec une telle adresse ont réglé un 0. L'action revient par la ligne d'ordinogramme 1007 à l'étape d'interrogation 500, où la question est de nouveau posée pour 25 déterminer si le bloc demandé est dans la mémoire de travail. Si,le bloc demandé est présent dans la mémoire de travail, soit comme résultat de la demande de mémoire en cours oud'une demande de mémoire précédente, l'action passe alors de l'étape 500 par la ligne d'ordinogramme 1001 aux étapes 503 et 504 et 505. Dans l'étape 503 le numéro de bloc et la valeur de bit L 30 du bloc demandé sont principalement mis en mémoire dans un registre "maintien" pour une utilisation future possible, (une telle utilisation ayant lieu sous certaines conditions décrites ci-après). Dans l'étape 504, l'adresse de travail du bloc demandé et l'adresse particulière de l'information désirée à l'intérieur de ce bloc sont disposées dans la partie gauche et la partie droite du regis-35 tre d'adresse de mémoire MAR de la mémoire de travail WM. Cela rend l'information mis en mémoire à l'adresse choisie disponible pour sa lecture dans le registre de donnée de mémoire MDR de la mémoire de travail WM, ou autrement cela rend possible au MDR de recevoir l'information qui doit être écrite dans cette adresse de travail particulière comme le cas peut se produire. Dans les 40 deux cas, l'opération particulière ainsi réalisée soit une lecture ou une 70 34360 27 2077507 écriture an l'a décrira ici comme "référenciation" du bloc adressé. Dans l'étape 505 certaines fonctions de mise à jour supplémentaires sont réalisées en prélude à la référenciation du bloc demandé. Les fonctions consitent dans le marquage du bit R associé avec ls bloc demandé pour montrer 5 que ce bloc est référencé et aussi dans le marquage du bit AL dans le cas où le bloc doit être modifié (re-écrit). L'action se poursuit alors par la ligne d'ordinigramme 1002 jusqu'à l'étape 506. A l'étape 506 figure 6, si il arrive que le bit L associé avec le bloc demandé est un "1" on réalise un ajustement dans les valeurs de A et de U 10 comme expliqué ci-dessus dansles figures 4A et 4B. Après cela ou immédiatement après le commencement de l'étape 506 dans le cas où L = 0, le mot associé avec le bloc demandé est référencé dans le registre de donnée de mémoire MDR de la mémoire associative AM et le bit R' associé avec le bloc référencié est réglé à "1". Cela termine l'opération de référenciation de bloc qui a été initiée 15 par la demande de mémoire en cours, et l'action revient par la ligne de l'organigramme 1008, figures 6 et 9A à l'unité centrale CPU. La figure 7 est un diagramme général du système semblable à la figure 6 mais présentant une représentation plus détaillée des fonctions réalisées dans les étapes ayant pour numéros généraux 502 et 505 de la figure 6. Les étapes 20 restantes de la figure 6 C500, 501, 503, 504 et 506] seront explicitées avec leurs fonctions constitutives durant une partie ultérieure de cette description. Les opérations élémentaires représentées par les rectangles 510 à 520 de la figure 7 sont les suivantes : 510 AM contient-il au moins 1 mot dans les bits AL et R sont tous deux 25 0 ? 511 Avancer l'indicateur de mot à la combinaison suivante 0-0 512 Replacer le bloc à l'adresse choisie dans WM 513 Trouver le mtot ou les mots dans AM avec bit AL = 1 et bit R = 0 514 Avancer l'indicateur de mot à la combinaison 1-0 suivante 30 515 Réécrire et replacer le bloc à l'adresse choisie dans WM 516 Dans Mot AM correspondant au bloc demandé régler bit R à 1 517 Si demandé, le bloc est-il altéré ? 518 Dans le mot AM correspondant au bloc demandé, régler le bit AL à 1 519 Tous les bits R sont-ils réglés à 0 ? 35 520 Restaurer tous les bits R à 0 . En référence à la figure 7, on portera son attention sur le mode spécifique de fonctionnement de l'algorithme de remplacement de Nelson déjà cité celui-ci étant "l'algorithme de remplacement réel" supposé être utilisé dans des buts illustratifs dans ce cas. Les symboles opérationnels avec des préfixes "T" 40 (par exemple T0, T1, T2 etc...) associés avec les diverses étapes de cet â 70 34360 28 : 2077507 algorithme de remplacement se réfèrent aux parties correspondantes des organigrammes et des schémas de circuits plus détaillés qui sont présentés ultérieurement. Si le bloc demandé ne se trouve pas actuellement dans la mémoire de travail 5 WM, figure 1, il devra être transféré dans cette mémoire WM à partir de la mémoire de soutien BS. Cela signifie que le système doit choisir un emplacement de travail ou adresse à l'intérieur de la mémoire de travail WM dans lequel le bloc identifié par le numéro de bloc demandé doit être amené et duquel le bloc qui s'y trouve actuellement emmagasiné doit être retiré. La façon par laquelle 10 le bloc remplacé est traité durant cette opération dépend de son altération où non durant son séjour dans la mémoire de travail. Si le bloc a remplacer n'a pas été altéré alors on peut par exemple simplement écrire par dessus le bloc puisqu'un duplicata du bloc remplacé est déjà dans la mémoire de soutien. Si le bloc a remplacer a été altéré, cependant, il doit être écrit dans la 15 mémoire de réserve avant son retrait de la mémoire de travail. Puisque l'écriture d'information dans la mémoire de réserve est un procédé relativement lent, il st préférable d'éviter cela chaque fois que cela est possible. Pour cette raison on donne la préférence aux emplacements de la mémoire de travail dont les blocs n'ont pas été altérés lorsque l'on recherche une place pour 20 y loger le bloc arrivant. D'autre part, il n'est pas désirable en règle générale de remplacer un bloc non altéré qui a été récemment sounis à référence dans la mémoire de travail, puisqu'il existe une probabilité élevée qu'un tel bloc soit rapidement soumis de nouveau à référence dans le système de traitement. 25 Les diverses considérations que l'on vient de mentionner sont satisfaites par le procédé de sélectiond'adresse dans les étapes 510 à 515 de l'organigramme général représenté dans la figure 7. Si le test réalisé à l'étape 510 indique que la mémoire associative AM (figure 1) maintient au moins un mot dont les bits AL et R sont tous les deux égaux à 0, alors un indicateur de mot 30 (décrit ci-après) est amené au mot suivant dans AM dont la combinaison de bit AL et de bit R est 0-0 (étape 511). Le bloc mis en mémoire à l'emplacement ou l'adresse de la mémoire de travail correspondant à ce mot dans AM est le bloc à remplacer (étape 512). Puisque son bit AL est 0 on remplace simplement ce bloc par sur-impression avec le bloc arrivant, il n'est pas nécessaire de 35 transférer les contenus d'un bloc non altéré dans la mémoire de soutien, l'action revient alors par la ligne de l'organigramme 1007 à l'étape 500 où une recherche est de nouveau effectuée pour déterminer si le bloc demandé est maintenant présent dans la mémoire de travail, la réponse naturellement étant "OUI" dans ce cas particulier. 40 Si le test de l'étape 510 indique qu'aucun des mots de la mémoire asso- è * 70 34360 29 2077507 ciative n'a ses deux bits AL et R égaux à zéro, alors un autre test est réalisé Cétape 513) pour déterminer lequel des mots dans AL a un bit AL égal à 1 et un bit R égal à 0. Il est obligé qu'il y ait au moins un mot dans AM dont le bit R est 0 attendu que tous les bits R sont restaurés automatiquement à 0 chaque 5 fois qu'ils atteignent tous un réglage à 1. Parmi les mots ayant des bits AL égaux à 1 au moins l'un de ces mots aura un bit R 0. L'indicateur de mot est maintenant avancé vers le mot suivant dont la combinaison de bits AL et de bit R et 1 = 0 Cétape 514). Le bloc localisé à l'adresse correspondante dans WM est celui qui doit être remplacé et puisque ce bloc a été altéré j son contenu 10 doit être réécrit dans la mémoire de réserve BS lorsqu'il est remplacé Cétape 515). Après cela l'action revient à l'étape 500 comme ci-dessus. Lorsqu'il s'avère que le bloc demandé est présent dans la mémoire de travail WM, les opérations sont effectuées pour mettre à jour les bits AL et R dans le mot correspondant de la mémoire associative. Dans l'étape 516 [figure 7), le bit 15 R de ce mot est réglé à 1, ce qui indique que le bloc respectif doit être référencé. Ensuite l'étape 517, une recherche est effectuée pour savoir si le bloc doit être altéré pendant qu'il est soumis à référence. Si il en est ainsi, son bit AL réglé à 1 Cétape 518). Si non, le bit AL reste à 0. L'action passe ensuite à l'étape 519, où un test est réalisé pour déterminer 20 si les bits R de tous les mots de la mémoire associative sont tous égaux à 1. S'il en est ainsi, alors tous ces bits R sont restaurés à 0, Cétape 520). Sinon, aucune modification n'est réalisée dans les bits R. Cela termine la mise à jour des bits AL et R, et l'action se poursuit par la ligne d'ordinogramme 1002 dans l'étape 506 (figure 6). 25 Bien que les figures 6 et 7 soient particulièrement concernées que les inter-relations entre les systèmes de mesure d'efficacité présents (représentés par les étapes "ME") et l'algorithme de remplacement de Nelson, (représenté par les étapes "T"), ces diagrammes indiquent aussi comment l'on peut appliquer la technique de mesure d'efficacité présente à d'autres algorithmes de 30 remplacement. Tous les algorithmes de remplacement présentent des faits communs certains, dont l'un appelé "exception de page" ou "exception de bloc" par lequel le système demande une interruption de l'unité centrale de traitement (CPU) chaque fois qu'un bloc ou page demandé ne peut pas être trouvé dans la mémoire de travail. Le procédé de mesure d'efficacité décrit ici est adapté 35 pour agir de façon intermittente durant cette période d'interruption alors que l'unité centrale de traitement attend l'obtention des blocs demandés dans la mémoire de travail. En un sens par conséquent, la procédure de mesure d'efficacité et l'algorithme de remplacement utilisent une unité centrale de traitement sur une base à temps partagé qui ne gêne pas de façon significative les 40 opérations de remplacement. â 70 34360 30 : 2077507 La. mémoire- assocfatiLve: AM de 1® figure; 1 est un schéma de transformation de mémoire pratique pour relier les adresses de bloc réel de la mémoire de travail WM aux adresses de EpIetc virtuelles dans la mémoire de soutien BS. En effet, certains schémas de transformation de mémoire câblée sont permanents. On 5 ne dit pas cela pour affirmer que la fonction de transformation de mémoire doit nécessairement être effectuée à l'aide d'un appareil spécial avec une mémoire associative. Cependant puisque ce type d'appareil est bien adapté dans ce but et conduit par lui-même à la facilité de la description, il est incorporé comme partie du système décrit. 10 Les figures 8A-8D illustrent une mémoire associative AM, un registre d'argument 32, des commandes de mémoire associatives 34 et un masque d'argument 46 qui sont tous représentés de façon plus générale dans les figures 9D, 9E et 9J. La mémoire associative AM, MDR 20 [représentée seulement dans la figure 9E), le masque d'écriture 47 (représenté que dans la figure 9GÎ, le registre d'ar-15 gument 32, et le masque d'argument 46 sont du type représenté dans le brevet obtenu en France par la demanderesse sous le n° 1 412 453 le 23.8.65. Le fonctionnement de ces éléments est décrit après et une compréhension plus détaillée de leur fonctionnement peut être obtenue par la lecture du brevet cité ci-dessus. Les commandes de mémoire associatives 34 sont pour une certaine 20 partie, les mêmes que celles représentées dans le brevet cité ci-dessus, et en diffèrent principalement par la présence des bascules indicatrices et par les commandes associées avec ces bascules. Une description détaillée du fonctionnement des commandes 34 suit. De nombreuses opérations peuvent être réalisées avec la mémoire asso-25 ciative AM. La première opération que l'on va décrire est une opération d'association pour déterminer quelle entrée dans la mémoire associative AM a un champ ou des champs, qui satisfont un champ particulier (ou des champs) du registre argument 32. On réalise cela en appliquant la combinaison désirée à des lignes de commande appropriées 48 et 49, figure BD, aux éléments d'em-30 magasinage de bit bistables 50 du champ désiré du registre d'argument 32. Un signal sur une ligne 48 enclenche l'élément bistables correspondant 50 dans son état 0 et un signai sur une ligne 49 enclenche l'élément bistable correspondant à son état 1'., Le registre d"argument est restauré par l'application simultanée de signaux sur toutes les lignes 48. Lorsque les signaux sont 35 appliqués aux lignes; de. commande 48 et 49 du registre d'argument 32, comme dit précédemment, les signaux sont aussi appliqués aux lignes de commande 52, figure; 8Ea, pour enclencher les éléments bistables 53 du masque d'argument 46 quâ sont; dams le champ ou les champs qui sont satisfaits. Tous les éléments bistables 53 ont précédemment été restaurés par un signal appliqué simultané-40 ment à toutes les lignes 51. Les signaux sur les lignes 52 agissent alors pour r v 70 34360 31 2077597 enclencher des éléments bistables 53 des champs désirés à leur état 1. Comme opération préliminaire supplémentaire, un signal est appliqué par la ligne 54 pour enclencher toutes les bascules indicatrices de correspondance C MI 3 55 (figure 8B) à leur état 1. Lorsqu'un signal est appliqué à la ligne associée 57, figure 8D, les contenus des éléments d'emmagasinage de bit argument 50 sont extraits par les lignes 56 e t vers les éléments bistables 53 qui mettent en mémoire les bits du masque d'argument 46. Ces éléments d'emmagasinage de bit 53 du masque argument qui sont enclenchés à 1 passeront l'information qui leur est appliquée par les lignes 58 aux éléments d'emmagasinage de bits bistables correspondants 60 (figure BC) dans chaque mot ou rangée de la mémoire associative 16. Tant que les contenus de chaque élément de bit de mot 60 sont les mêmes que les contenus de l'élément de bit d'argument correspondant 50, la mémoire associative AM n'engendre qu'une sortie. Cependant, lorsque le signal binaire appliqué par une ligne 58 à un élément de bit de mot 60 diffère du bit réellement mis en mémoire dans l'élément 60, l'élément 60 engendre un signal de sortie sur la ligne correspondante de dépareillage 62. Le signal sur la ligne 62 est appliqué pour restaurer la bascule indicatrice de correspondance correspondante 55 à son état 0. La lecture d'un mot de correspondance est réalisée comme ci-dessus. Les indicateurs de correspondance 55 (figure BB] sont interrogés par un signal appliqué à la ligne 64. Le signal sur la ligne 64 est appliqué comme entrée aux portes ET 66 et B4 pour le premier mot dans la mémoire associative. L'autre entrée à la porte 66 est constituée par la sortie "0" de la bascule 55 et l'autre entrée à la porte ET 84 est constituée par la sortie "1" de la bascule 55. Si la bascule 55 pour le mot le plus élevé dans la mémoire associative est dans son état "1", le signal sur la ligne 64 passera à travers la porte ET 84 par le câble 88 et sera appliqué à la porte DU 90 pour le mot le plus élevé de la mémoire associative. Si la bascule 55 pour le mot le plus élevé de la mémoire associative est dans son état "0", le signal sur . la ligne 64 passera par les portes ET 66 et sera appliqué aux portes ET 66 et 84 pour le mot inférieur suivant de la mémoire associative. Si toutes les bascules 55 sont dans leur état "0", un signal sur la ligne 64 apparaitra sur la ligne 72 et enclenchera la bascule "EOL" à son état "1". L'information peut être soit extraite soit écrite dans un mot dans la mémoire associative 16 sous commande des bascules d'indication de correspondance 55. Pour une opération d'écriture un signal est appliqué sur la ligne 74 à une entrée de chacune des portes ET 76 (figure 8B) et pour une opération de lecture un signal est appliqué par la ligne 78 à une entrée de chacune des portes ET B0. Le signal sur la ligne d'interrogation 64 , figure 8B, est appliqué à une borne d'entrée d'une porte ET 84 associée avec le mot le plus 70 34360 32 '2077507 élevé de la mémoire associative AM. Une porte semblable ET 84 est associée avec chacun des autres mots de la mémoire AM et une entrée de chaque porte ET 84 dans le dernier groupe est connectée par le conducteur 70 à la sortie de la porte ET 66 associée avec le mot précédent. L'autre borne d'entrée de 5 chaque porte ET 84 est connectée par un conducteur 86 à la borne de sortie n° 1 de l'indicateur de correspondance 55 associé avec le même mot.de la mémoire associative AM. Des portes ET 84 i figure SB, qui vont- être conditionnées par les signaux de sortie 1 provenant de leurs indicateurs de correspondance respective 55 àu moment où un signal est appliqué à la ligne d'interro-10 gation 64, seule la porte la plus élevée de ces portes ET conditionnées 84 agit pour passer un signal de la ligne 84 par une ligne de sortie 88, une porte OU 90 associées et la ligne 92 à la seconde borne d'entrée de chacune des portes ET correspondantes 76. et 80. Si une opération d'écriture doit être réalisée, la porte ET correspondante 76 est conditionnée pour engendrer un 15 signal de sortie sur la ligne 94, signal qui agit pour permettre l'insertion des contenus du MDR 20 ffigure 9E) pour les champs qui comprennent en mémoire un bit dans un masque d'écriture 47, dans les éléments d'emmagasinage de bit 60 du mot correspondant de la mémoire associative 16. Le masque d'écriture 47 agit ainsi pour déterminer quel champ d'un mot dans la mémoire associative 20 AM sera écrit durant une opération d'écriture. Si il existe un signal sur la ligne de lecture 78 au moment où un signal apparaît sur la ligne 64, la porte ET 80 [figure 8B) est complètement conditionnée pour engendrer un signal de sortie sur la ligne 96 qui agit pour amener l'extraction des contenus du mot correspondant de la mémoire associative 16 par les lignes 97 dans MDR 25 20. Les commandes 34 représentées dans les figures 8A et 8B comprennent aussi une bascule indicatrice 98 (figure SA] pour chaque mot de la mémoire associative AM. Un signal de départ est appliqué à la ligne 101 pour enclencher les bascules indicatrices à un état initial où la bascule indicatrice du premier mot 30 est dans son état 1 et les bascules indicatrices des mots restants sont dans leurs états 0. Spécifiquement, on réalise cela en appliquant le signal sur la ligne 101 par la porte DU 102 au côté d'entrée 1 de la bascule indicatrice du premier mot et par les portes OU 104 pour chacun des mots restants dans la mémoire associative au côté d'entrée 0 de la bascule indicatrice correspondan-35 te. Le signal de restauration initial est appliqué à la ligne 101 au commencement d'un cycle machine et n'est plus ensuite répété pendant que le même programme est en cours de traitement. Lorsque l'on désire changer le réglage dès bascules indicatrices, un signal de conditionnement est appliqué à la ligne 106 à une entrée de la 40 porte ET 103 (figure 8A] pour chaque mot de la mémoire]. L'autre entrée de 70 34360 33 2Û775Ô7 chacune des portes ET 108 est fournie par la ligne de sortie 110 provenant du côté 1 de la bascule indicatrice correspondante. Puisque seule l'une des bascules indicatrices est dans son état 1, à tout moment donné, seulement une des portes ET 108 sera complètement conditionnée par le signal sur la ligne 5 106 pour engendrer un signal de sortie sur la ligne de sortie correspondante 112. Le signal sur une ligne de sortie 112 provenant d'une porte ET 108 pour une position de mot donnée est appliqué comme entrée aux portes ET 114 et 116 de la position de mot suivante. On voit que cela forme une boucle fermée avec la ligne de sortie 112 provenant de la porte ET 108 pour le mot N consti-10 tuant une entrée aux portes ET 114 et 116 pour le mot le plus élevé ou le premier. Les autres entrées aux portes ET 114 et 116 respectivement, sont des lignes de sortie 68 provenant du côté 0 et une ligne de sortie 86 provenant du côté 1 de l'indicateur correspondant 55. La ligne de sortie 118 provenant de la porte ET 114 est connectée comme entrée à la porte ET 120, l'autre 15 entrée de cette porte ET étant la ligne de sortie 122 provenant du côté 0 de la bascule indicatrice correspondante 98. La porte ET 120 partage la ligne de sortie 112 avec la porte ET 108 pour chaque position de mot. La ligne de sortie 124 provenant de chacune des portes ET 116 est connectée au côté d'entrée 1 de la bascule intermédiaire correspondante 126. 20 L'effet des connexions que l'on vient de décrire est de permettre qu'un signal appliqué à la ligne 106 traverse la porte ET 108 pour la position qui comprend la bascule indicatrice 98 à son état 1 vers la ligne correspondante 112. Le signal sur la ligne 112 est appliqué aux portes ET 114 et 116 pour la position de mot suivant. Si l'indicateur correspondant pour cette 25 position de mot est dans son état 0, le signal se propage à travers la porte ET 114, la ligne 118, la porte ET 120, et la ligne 112, pour ce mot et aux portes ET 114 et 116 pour le mot suivant. Le signal se propage de cette façon jusqu'à ce qu'un mot soit atteint pour lequel l'indicateur de correspondance correspondant est dans son état 1. Lorsque ce mot est atteint, la porte ET 30 correspondante 116 est complètement conditionnée pour engendrer un signal de sortie qui est appliqué pour enclencher la bascule intermédiaire correspondante 126 à son état 1. Si le signal indicateur est appliqué à la ligne 106 à un moment où la bascule indicatrice la plus basse 98, figure 3A, est - enclenchée à 1, ou sice signal de décalage est propagé à la porte la plus 35 basse 114 au moment où à la fois la bascule indicatrice la plus basse 98 et l'indicateur de correspondance le plus bas 55 (figure 3B) sont dans leurs états 0, le signal de décalage est alors propagé vers les portes les plus élevées 114 et 116, figure 8A. Le signal sur la ligne 106 est suivi par un signal sur la ligne 130. Le signal de la ligne 130 est appliqué pour actionner chacune des portes 132 40 (figure 8A) pour transférer les contenus des bascules correspondantes 126 ê 70 34360 34 ; 2077501 dans la bascule indicatrice correspondante 98. Cela restaure effectivement la bascule indicatrice correspondant à celle des bascules intermédiaires 126 qui a été enclenchées à son état 1 par le signal de la ligne 106, de telle sorte que ladite bascule indicatrice est enclenchée à son état 1. L'opération de 5 changement d'indicateur est terminé par un signal provenant de l'une des nombreuses sources appliqué à travers la porte DU 250, figure 9B et la ligne 134 pour restaurer toutes les bascules intermédiaires 126 à leur état 0. Il est possible que l'indicateur soit complètement recyclé à sa position de mot initiale, si aucun autre mot de correspondance ne peut être trouvé. 10 Comme comme une opération d'écriture ou de lecture peut être commandée par la bascule indicatrice de correspondance 55 d'une façon précédemment décrite, les opérations écriture et lecture peuvent aussi être commandées à ,l'aide des: bascules indicatrices. Afin de réaliser cela l'entrée écriture ou lecture désirée est appliquée à la ligne appropriée 74 ou 76 en même temps 15 qu'un signal est appliqué à la ligne à accès sous commande des bascules indicatrices 136. Le signal de la ligne 136 est appliqué comme entrée aux portes ET 13B (figure 8B), l'autre entrée de chacune de ces portes ET étant constituée par la ligne de sortie 110 provenant du côté 1 de la bascule indicatrice correspondante 98. Puisque seulement l'une des bascules indicatrices 20 sera dans son état 1 à ce moment donné, seulement l'une des portes ET engendrera un signal de sortie lorsqu'un signal est appliqué à la ligne 136. Le signal sur la ligne 140 provenant de cette porte ET est appliqué par la porte OU correspondante 90 pour exciter la porte ET appropriée 76 ou 60 pour amener la réalisation de l'opération d'écriture ou de lecture désirée d'une façon iden-. ' 25 tique à celle précédemment décrite pour un accès sur commande de bascules indicatrices de correspondance 55. Lorsque la mémoire associative est chargée initialement, la bascule indicatrice la plus élevée 98, (figure 8A), est enclenchée à 1 alors que les autres bascules indicatrices 98 sont réglées à 0. Dans ces conditions, le 30 premier mot qui est chargé dans la mémoire associative sera envoyé effectivement dans la seconde rangée ou adressa de mot de cette mémoire. Le second mot sera chargé dans la troisième adresse, et (si l'on suppose que la mémoire associative est limitée à une capacité de trois.mots, le troisième mot pénétrera dans la première adresse ou position de la mémoire associative). En 35 correspondance, le premier bloc qui sera emmagasiné dans la mémoire de travail WM, figures 1 et 9C, sera entré effectivement dans la seconde adresse de bloc ; le second bloc sera chargé dans la troisième adresse de position, et le troisième bloc sera entré dans la première adresse ou position de la mémoire de travail WM. Ces relations seront illustrées avec plus de détail graphiquement 40 ci-après lors de la description détaillée du fonctionnement du système. 70 34360 35 2077507 Les figures 9A à 9K lorsqu'assemblées de la façon décrite dans la figure 9, constituent un diagramme de circuit d'un système mettant en application la présente invention. Le système décrit met en oeuvre à la fois à l'algorithme de remplacement décrit dans le brevet français 1 509 223 déjà cité j 5 et l'algorithme de mesure d'efficacité qui constitue le sujet de la présente invention. Ces parties du système global qui concernent plus particulièrement l'algorithme de remplacement de Nelson sont commandées par une horloge "T" 198, figure 9A qui comprend plusieurs générateurs d'impulsions de synchronisation ou monostables désignés par les références TO à T37 pour correspondre avec 1Q leurs sorties respectives. Chacun des monostablœ T0-T37 engendre un signal sur une ligne de sortie 200-237 respectivement lorsqu'il est enclenché. Lorsque le monostable bascule de son état enclenché à son état restauré (c'est-à-dire lorsque le monostable "expire"), il engendre un signal "NON" (par exemple T4). Dans certains cas ces signaux "NON" apparaissent sur les lignes "Expiration* 15 telles que 204' provenant de l'horloge 190. Dans d'autres cas ils sont utilisés à l'intérieur seulement de l'horloge. Afin de simplifier les dessins, on n'a effectué aucune tentative pour connecter les sorties provenant de l'horloge 198 aux divers points du système où ils sont utilisés. Au lieu de cela, à chaque point du système où une ligne d'horloge est utilisée, une ligne apparait 20 avec les désignations de numéros et de lettres de la ligne d'horloge appropriée. Dans la plupart des cas lorsqu'un monostable de l'horloge 198 expire le monostable suivant est enclenché. Dans certains cas, cependant, un monostable est enclenché par un signal de sortie provenant d'un point du système. Ces signaux ont été représentés comme entrés du côté gauche de l'horloge 198 25 (figure 9A). Les connexions intérieures de l'horloge 198 sont décrites fonc-tionnellement dans le brevet citée ci-dessus, auquel on se réfère pour une compréhension plus complète. Les parties du système décrit qui donnent particulièrement corps à l'algorithme de mesure d'efficacité avec lequel la présente invention est parti-30 culièrement concernée sont identifiées par divers signaux de synchronisation ou étapes de procédure portant le préfixe "ME" figures 6,7, 9E. L'horloge utilisée pour engendrer ces signaux n'est pas représentée, mais serait semblable à l'horloge 198, figure 9A décrite ci-dessus. Cela signifie que divers générateurs d'impulsions ou monostable de cette horloge engendreront les impulsions 35 "ME" en une séquence qui est en partie prédéterminée et en partie déterminée par les conditions particulières rencontrées dans le fonctionnement du système. Les fonctions des signaux d'horloge "ME" ou étapes de procédé seront expliquées au cours des descriptions et seront aussi résumées ci-après. En référence maintenant aux figures 9A, 9E, on voit que le système de la réalisation préférée de l'invention comprend comme éléments fondamentaux une 40 unité de traitement centrale (CPU), figure 9A, une mémoire de travail à vitesse â 70 34360 38 2077507 élevée et à capacité faible WM, figure 9B qui peut être une mémoire à ferrite et une mémoire associative AM [figure 9D). La mémoire de soutien BS (qui peut par exemple être une unité à disque) communique avec la mémoire de travail WM (qui peut être la mémoire à ferrite magnétique à vitesse élevée associée avec 5 tout système de calculateur numérique) par le canal CH. Le canal CH qui comprend de nombreuses commandes, peut par exemple être le canal du système calculateur IBM 7040 lorsque c'est l'unité centrale de traitement que l'on utilise ou un grand nombre de dispositifs de canaux qui peuvent réaliser les fonctions demandées de commande et intermédiaires. Le canal CH accepte 10 l'information appliquée en série provenant de la mémoire à vitesse faible BS, assemble les bits en mots, et applique ces mots en parallèle à la mémoire de travail WM. Le canal peut aussi accepter des mots en parallèle provenant de la mémoire WM et appliquer les bits en provenant en série dans la mémoire de soutien BS. Le canal contient aussi des circuits de commande pour augmenter 15 de façon convenable les adresses à partir desquelles l'information est prise ou auxquelles l'information doit être appliquée et pour indiquer lorsque le transfert d'un bloc d'information a été terminé. La mémoire associative AM de la figure 9D, comprend une entrée ou une rangée de mémoire de mot pour chacune des positions de bloc de la mémoire à. 20 ferrite WM. Chacune de ces entrées contient 8 champs qui sont représentés dans le registre de donnée de mémoire (MDR) 20 figure 9E. En lisant ces champs de gauche a droite, ce sont : un champ à un bit R' (dont la fonction est expliquée ci-dessus), un champ à un bit L qui a aussi été expliqué ci-dessus ; un champ à un bit SS (recherché en série) dont la fonctionsera expliquée 25 ultérieurement î un champ à un bit AL (champ d'altération) qui est réglé à 1 chaque fois que le contenu du bloc correspondant de la mémoire à ferrite WM est altérée un champ à un bit R (référence) qui est réglé à 1 chaque fois que le bloc correspondant de la mémoire à ferrite WM est utilisé et restauré à 0 lorsque toutes les entrées de la mémoire associative AM ont leurs champs 30 R enclenchés ; un champ ID qui identifie le programme dans l'unité de traitement centrale CPU avec lequel le bloc de la position correspondante dans la mémoire à ferrite WM est associé ; l'adresse de bloc de la mémoire de soutien BS pour le bloc de la position correspondante dans la mémoire à ferrite WM, et l'adresse de bloc dans la mémoire à ferrite WM à laquelle l'entrée 35 correspond. Le champ le plus à droite de.chaque entrée dans la mémoire associative WM peut être lu mais non écrit. Les autres champs de la mémoire associative AM peuvent être altérés de temps en temps d'une façon à décrire plus tard. L'unité de traitement centrale CPU, figures 1 et 9A initie l'opération 40 en demandant un bloc d'information dans la mémoire WM. Lorsque cela se produit. 70 34360 37 2077507 le programme 10 et l'adresse du bloc demandé dans la mémoire de soutien DS sont appliqués par les lignes 22 au registre d'adresse 24 (figure 9B) et un signal est appliqué par le CPU soit par la ligne 2G, soit par la ligne 28 pour enclencher convenablement la bascule d'altération 3D. La bascule 30 est enclenchée 5 à son état 1 si le mot recherché doit être altéré. Après des opérations de charge préliminaires, le système est prêt à réaliser l'étape 500 des figures B et 7. Durant cette étape une détermination est effectuée pour savoir si le bloc contenant le mot. que l'on désire utiliser est en mémoire dans la mémoire de travail WM (figure 9C). Une telle détermi-10 nation st réalisée par lecture de l'information contenue dans le champ I □ et du numéro de bloc à partir du registre 24 (figure 9B) dans les champs appropriés du registre d'argument 32 ffigure 9J) de la mémoire associative AM et en réalisant une opération d'association de ces champs pour déterminer si le champ ID et le numéro de bloc sont contenus dans la mémoire associative. Pour 15 examiner rapidement l'opération d'association, les commandes de mémoire associative 34 (figure 90, 8A et BB) contiennent un indicateur de correspondance bistable 55 (figure 8B] pour chaque entrée dans la mémoire. Les indicateurs de correspondance sont tous enclenchés à 1 durant une opération d'association. Les champs dans le registre d'argument 32 qui doivent être mis 20 en correspondance sont alors appliqués à la mémoire associative AM et comparés aux champs correspondants dans chaque entrée s'y trouvant. Chacun des désap-pareillage entraine la restauration dans les unités de commande 34 de l'indicateur de correspondance correspondant 55. Les indicateur de correspondance 55 sont alors interrogés et, une bascule de fin de ligne (EOL) 3B est enclenchée 25 à 1 si tous les indicateurs de correspondance sont restaurés à 0. Si aucune correspondance n'est trouvée dans la mémoire associative AM sur l'ID indiquée, et l'information de bloc, cela indique que le bloc demandé n'est pas dans la mémoire à ferrite WM, et le circuit agit pour réaliser l'étape 501 des figures 6 et 7. Les étapes qui sont réalisées si le bloc demandé est trouvé dans la 30 mémoire à ferrité 14 sercnt décrites plus tard. Les actions qui se produisent dans l'étape 501 sont décrites avec plus de détail ci-après lors de la considération d'un problème illustratif. Pour le présent, il suffira d'expliquer que de telles actions sont concernées par les commandes opérationnelles (ME) représentées à côté du boitier 201 dans 35 les figures 6 et 7. A la fin de l'étape 501, le traitement passe à l'étape 510 (figure 7). Durant l'étape 510 figure 7, on effectue une détermination pour savoir si il y a des entrées dans la mémoire associative AM (figure 9DÎ pour lesquelles les bits dans les deux champs A et R sont 0. Le bit R de telles 40 entrées qui sont 0 indiquent que cette entrée n'a pas été récemment utilisée. # 70 34360 36 ' 20775Ô7 Le bit A de l'entrée1 qui est 0 indique que I"entrée n'a pas été altérée durant son passage dans la mémoire à ferrite. A partir de la discussion précédente, il est apparent qu'un bloc pour lequel ces caractéristiques existent est un un candidat bien placé pour remplacement. L'étape 510 est réalisée en enclen-5 chant à la fois les champs AR dans, le registre d'argument-32 [figure 9J) à 0 et en réalisant une opération d'association dans les circuits de commande de mémoire associative 34 correspondant à chaque entrée de la mémoire associative ayant à la fois un champA "zéro" et un champ R "0", et pour restaurer tout autre indicateur de correspondance à zéro. Si il n'y a aucune entrée avec 10 des champs A "0" et R "0", la bascule de fin de ligne 36 est enclenchée à son état 1 à la fin de l'opération d'association. Supposons au départ qu'il y a au moins une entrée dans la mémoire associative AM pour laquelle à la fois les bits A et R sont zéro. Dans ces conditions le système passe de l'étape 510 [figure 7) à l'étape 511. Puisqu'il 15 est possible qu'il y ait plus d'une entrée dans la mémoire associative ayant des bits 0 à la fois dans ces champs A et R, il est nécessaire d'obtenir un critère supplémentaire pour sélectionner parmi ces entrées, l'entrée dont le bloc correspondant doit être remplacé. Cette sélection est réalisée durant l'étape 511 du fonctionnement. Pour résumer rapidement cette opération, il y 20 a une bascule indicatrice 98, figure 8A dans les commandes de mémoire associative 34 pour chaque entrée de la mémoire associative AM. Toutes les bascules indicatrices 98 sont restaurées à l'exception de celle correspondant au dernier bloc qui a été remplacé dans la mémoire WM. Durant l'étape 511 de fonctionnement, une recherche est initiée commençant avec l'entrée suivant celle pour 25 laquelle la bascule indicatrice est enclenchée, pour trouver une entrée pour laquelle l'indicateur correspondant 55 dans les dispositifs de commande 34 est enclenché. Lorsque l'entrée est trouvée la bascule indicatrice de cette entrée est enclenchée et la bascule indicatrice qui a été enclenchée est restaurée à condition qu'elle ne soit pas à la position de mot correspondant. 30 (Il est possible dans certaines circonstances que la recherche de mot correspondant s'arrête à la même position de mot où elle a débutée comme on l'a noté ci-dessus). De l'étape 511 le circuit passe à l'étape 512, figure 7, pour amener le remplacement du bloc de la mémoire de travail WM correspondant à l'entrée 35 sélectionnée de la mémoire associative AM durant l'étape 511. Dn .réalise cela en lisant l'adresse du bloc de la mémoire ferrite de l'entrée sélectionnée dans le registre d'adresse à ferrite (CAR) 38, figure 9C, en lisant l'ID et l'information en provenance du nouveau bloc qui doit être appliqué à la mémoire de-, travail WM: en. provenance du registre 24 (figure 9B) dans le registre 40 d'adresse de remplacement (RAR) 40» figure SC., et en appliquant un signal 70 34360 33 2Û775Ô7 d'entrée "remplacer" au canal CH. L'effet de ces entrées sur le canal CH est d'amener la lecture par le canal du bloc d'information commençant à l'adresse indiquée dans RAR 40 dans la mémoire de travail WM aux adresses commençant à l'adresse indiquée dans CAR 38. Lorsqu'un bloc complet d'information a été 5 transféré, ce fait est indiqué (d'une façon que l'on va décrire plus tard) par le canal CH. Lorsque l'étape 512 de fonctionnement a été terminée, l'action revient par la ligne de l'organigramme 1007, figure 7 à l'étape 500. On suppose maintenant que durant l'étape 510 de fonctionnement, on a déterminé qu'il n'y avait aucune entrée dans la mémoie associative AM pour 10 lesquelles à la fois les bits A et R sont 0. Dans ces conditions, le système passe de l'étape 510 à l'étape 513. Dans l'algorithme sur lequEl le système est fondé l'utilisation est le critère de remplacement principal et l'altération n'est seulement qu'un critère supplémentaire. Par conséquent si aucune entrée ne peut être trouvée pour lesquelles à la fois les bits A et R sont 15 0, on choisit une entrée pour laquelle le bit A est 1 et le bit R 0. Puisque, comme on le verra lorsque tous les bits R sont 1, les champs de bits R pour toutes les entrées de la mémoire associative AM sont restaurés à 0, il y aura toujours au moins une entrée ayant un bit R "0". L'étape 513 du fonctionnement est réalisée de la même façon que l'étape 510 à l'exception que le registre 20 d'argument 32 est chargé initialement avec le bit 1 dans le champ A et un bit 0 dans la champ R. Une opération d'association est alors réalisée, avec pour résultat que les indicateurs de correspondance dans les commandes 34 pour les entrées ayant un bit 1 dans le champ A et un bit 0 dans le champ R sont laissés dans leur état 1 alors que les autres indicateurs de correspondance sont 25 restaurés à 0. De l'étape 513, le système passe à l'étape 514 (figure 7) de fonctionnement. Puisqu'il est possible que plus d'un indicateur de correspondance soit enclenché durant l'étape 513 du fonctionnement, l'étape 514 est nécessaire afin de réaliser une détermination finale du bloc de la mémoire de travail WM qui doit 30 être remplacée. Les bascules indicatrices 98 dans les commandes 34 sont utilisées pour réaliser l'étape 514 du fonctionnèrent d'une façon identique à celle décrite précédemment pour l'étape 511 de fonctionnement. Le fonctionnement ne sera pas par conséquent de nouveau décrit pour ce point. De l'étape 514, le système passe à l'étape 515 (figure 7). Puisque le bloc 35 qui a maintenant été choisi pour remplacement dans la mémoire de travail WM a été altéré durant son passage, il est nécessaire de réinscrire ce bloc dans la mémoire de soutien BS (figure 9B) avant de le remplacer. Par conséquent, durant l'étape 515 de fonctionnement, une opération de ré-incription et de remplacement sont réalisées. En réalisant l'étape 515, l'adresse de la position 40 de bloc sélectionnée dans la mémoire de travail WM est lue dans CAR 38, » 70 34360 40 2Û775Ô7 figure 9C, l'adresse dans la mémoire de soutien BS à laquelle le bloc d'information actuellement en mémoire dans le bloc à ferrite sélectionné doit être incriteCadresse qui est obtenue à partir de la mémoire associative AM) est lu dans le registre d'adresse d'écriture (WAR) 42, l'adresse dans la mémoire de 5 soutien BS nouveau bloc qui doit être transféré dans la mémoire de travail WM, est lue dans RAR 40, et un signal est appliqué à la borne d'entrée "réinscription et remplacement" du canal CH. Le canal fonctionne alors d'une façon classique pour réinscrire dans la mémoire de soutien BS le bloc de donnée du bloc sélectionné dans la mémoire de travail, à une adresse commençant avec 10 l'adresse contenue dans le WAR 42 et ensuite pour transférer le bloc de donnée commençant à l'adresse indiquée dans RAR 40 dans le bloc sélectionné de la mémoire de. travail WM. Lorsque le bloc complet a été écrit dans la mémoire à ferrite WM, un canal CH engendre un signal de sortie indiquant la fin de l'étape 515 du fonctionnement et amenant le système à revenir par la ligne 15 d'organigramme 17 [figure 7) à l'étape 500. □n suppose maintenant que durant l'étape 500 du fonctionnement il a été déterminé que le bloc désiré est maintenant en mémoire dans la mémoire de travail WM. Cette détermination peut être réalisée soit initialement lorsque la demande pour l'information est réalisée par le CPU, soit comme une consé-20 quence de la lecture du bloc d'information dans la mémoire de travail WM durant les étapes 512, 515 (figure 7) du fonctionnement. Lorsque le bloc désiré est trouvé dans la mémoire de travail WM durant l'étape 500 de fonctionnement, le système peut agir simultanément pour réaliser les étapes 503, 504, 505 du fonctionnement,figure B. Durant l'étape 503 du fonctionnement l'adresse du 25 bloc dans la mémoire de travail WM à laquelle le bloc désiré d'information est mis en mémoire et la valeur de bit L du mot associé dans la mémoire AM (maintenant enregistrée dans le registre de donnée de mémoire MDR figure 9E), sont entrées dans le registre de maintien figure 9F pour référence future possible. Durant l'étape 504, figure B, l'adresse de bloc dans la mémoire WM 30 du bloc demandé est extraite du registre 24 (figure 9B) et disposée dans la partie gauche du registre d'adresse de mémoire (MAR) 44, figure 9C et l'adresse particulière à l'intérieur du bloc est extraite du registre 24 (figure 9B) et disposée dans la partie droite de MAR 44. L'unité centrale de traitement peut maintenant récupérer le mot désiré dans la mémoire de travail WM et de 35 l'utiliser selon les besoins. Lorsque le mot associé avec un bloc errmagasiné dans la mémoire de travail WM est utilisé, certaines opérations domestiques sur les champs A et R de l'entrée correspondante de la mémoire associtaive AM (figure 9B) sont nécessaires. Ces opérations domestiques sont réalisées durant les étapes516-520 40 (figure 7) de fonctionnement. Durant l'étape 516 le bit de référence (R) de ê 70 34360 41 ' 2077507 l'entrée correspondante au bloc dont le mot vient d'être utilisé est enclenché à 1. On réalise cela en enclenchant le champ R du registre de donnée de mémoire associative CMDR) 20 figure 9E à 1, et en écrivant alors ce champ dans l'entrée correcte de la mémoire associative de la façon décrite ci-dessus. 5 De l'étape 516 le système passe à l'étape 517. Durant l'étape 517 la bascule d'altération 30, figure 9A est interrogée pour déterminer si le bloc que l'on vient d'utiliser a été altéré. La bascule d'altération est enclenchée à son état 1 avant l'initiation de l'opération si le bloc doit être altéré. Si le bloc n'est pas altéré, le système passe directement à l'étape 519 10 figure 7. Si le bloc a été altéré le système passe à l'étape 51& Durant l'étape 518, le bloc qui vient d'être utilisé dans les mémoires à ferrite WM, a son bit d'altération [c'est-à-dire le champ A) enclenché à 1. Dn réalise cela en disposant un bit 1 dans le champ A du MDR 20, [figure 9E) et en écrivant ce champ dans l'entrée sélectionnée de la mémoire associative AM comme 15 expliqué ci-dessus. De l'étape 518 l'action passe à l'étape 519, figure 7. Durant l'étape 519 il est déterminé si tous les bits de référence [R) sont réglés à 1. On réalise cela en enclenchant le champ R du registre d'argument 32 [figure 9E) à 0 et en associant ce champ dans la mémoire associative AM. Si aucune 20 correspondance n'est trouvée durant cette opération associative cela signifie que tous les bits R sont réglés à 1. De la discussion précédente, on se rappellera que si tous les bits R sont réglés à 1, ces bits R doivent alors être restaurés à 0. Par conséquent, lorsque cela se produit, le système passe de l'étape 519 à l'étape 520 de l'action. Durant l'étape 520, un signal T13 25 est appliqué à la mémoire associative AM figure 9D pour restaurer les champ R, de toutes les entrées qui s'y trouvent; à 0. Lorsque l'étape 520 est terminée, un signal "ME1" est appliqué par la ligne 10Q2, figure 7 et 9A à une porte de sortie pour le registre de maintien figure 9F. La même action se produit aussi directement si durant l'étape 519, figure 7, il a été déterminé 30 que tous les bits de référence (R) ne sont pas des 1. Dans l'un ou l'autre des cas, l'action passe ensuite à l'étape 506, figure 6 qui commence avec un test pour déterminer si le bit L associé avec le bloc qui est en cours de référenciation est enclenché à 1. Dans la description précédente l'attention s'est principalement portée 35 sur les actions qui se sont produites durant les étapes principales 500, 502, 503, 504 et 505 figures 6 et 7 de la procédure de remplacement. L'explication de ce qui produit dans les étapes principales 501 et 506 qui concernent plus particulièrement la procédure de mesure d'efficacité sera retardée jusqu'à ce que des exemples pratiques soient présentées pour analyse. Avant de passer 40 à l'explication de ces exemples illustratifs, on va donner une description â 70 34360 r207?§Ô7 de certains éléments représentés dans les figures 9F, 9H, 91 et 9K qui n'ont pas leur contrepartie dans le brevet cité ci-dessus et qui sont particuliers au système présent. □n a déjà fait mention du registre "maintien" représenté dans la figure 5 9F, qui concerne les valeurs de bit L et le numéro de bloc du bloc qui est en cours de référenciation dans la mémoire de travail WM. On montre aussi sous forme de schéma dans la figure 9F les compteurs P, 0 et Q, qui conservent respectivement les comptes du numéro réel de transfert dé bloc P, des transferts de bloc non nécessaires U et des transferts "incertains" ou "contestables" 10 Q (l'utilisation du compte mentionné le dernier est illustré par un exemple ci-après. Une bascule "F" dont la fonctionsera expliquée est aussi représentée-dans la figure 9F. Les registres A et B, figure 91 sont adaptés pour enregistrer les valeurs en cours des variables A et B respectivement. Le registre A est un compteur 15 qui est augmenté chaque fois qu'un nouvel intervalle est défini dans la séquence optimum d'opération. Le registre B a un réglage initial de 1 et est restauré à une nouvelle valeur chaque fois qu'un "jeu complet" est défini dans la séquence optimum. Dans les figures 9H et 91, les tables qui conservait les valeurs C et E sont elles-mêmes appelées "C" et "E" respectivement pour faciliter 20 l'identification. Le sens avec lequel on utilise les symboles "C" et "E" apparaitra à partir du contexte. Les tables C et E sont des registres à plusieurs entrées, les entrées respectives de telles tables pouvant être adressées par un décodeur à la fois pour entrée et sortie. Le décodeur de la table C est enclenché sous la commande d'un registre Y. En d'autres termes le registre 25 "Y" adresse la table C. De façon semblable un registre X adressé la table E. On se référera aux réglagœ des registre X et Y ci-après comme indicateur X et Y. La sortie de la table C est envoyée à un registre "DÈC", dont le réglage peut être diminué sélectivement sous certaines conditions comme on le décrira ci-après. Chaque fois que le réglage "DEC" atteint Û les contenus du 30 registre Y sont transférés au registre B dans un but que l'on décrira. Diverses unités "comparer" représentées dans lés figures 9H et 9K. sont utilisées pour réaliser des comparaisons parmi lés valeurs.de E, A, B et Y pour des raisons qui seront expliquées. La figure 10 illustre en détail la constructionùe la table C ou de la table 35 E, ces deux tables étant de construction identique. Chacune de ces tables est formée de plusieurs registres, dont le nombre dépend du nombre qui peut être contenu dans chaque registre Y (dans la figure 9H) ou registre X (dans la figure 91). En référence à la figure 9H on remarquera que le réglage du registre Y est décodé par un décodeur représenté dans la figure 9H, ce décodeur 40 comprenant plusieurs lignes de sortie dont le nombre est égal au nombre 70 34360 '2077507 maximum des registres que l'on vient de mentionner. Par exemple, si le registre Y est construit pour contenir un nombre binaire à 3 bits, le décodeur aura alors B lignes de sortie. Dans la pratique actuelle le nombre des lignes de sortie peut être supérieur. Par commodité les registres de la table C sont 5 ci-après identifiés par les adresses 1,2,3 etc... pour correspondre avec les réglages significatifs qui peuvent être pris par le registre Y, le réglage 0 de Y n'ayant aucune signification. Dans la table E les adresses des registres respectifs correspondent avec les numéros de blocs enregistrés dans le registre X. 10 La figure 10 représente en détail trois registres tels que celui ayant pour référence B00 dans la figure 9H. La ligne de commande "indicatrice" appelée 602, figures 9H et 10 provenant dans ce cas dudécodeur Y est excitée lorsque l'on désire connecter le registre 600 à la fois aux lignes d'entrée 604 et aux lignes de sortie B06 de la table C. On se réfère à la figure 10 où 15 l'on remarquera que si la ligne 602 est active, les portes 608, 610 et 612 seront conditionnées afin de permettre aux lignes d'entrée du câble 604 d'enclencher des bascule 614, 616 et 618. De cette façon la ligne de commande "indicatrice" 602 agit pour connecter les bascules 614, 61B, 618 qui sont des exemples des bascules qui forment le registre 600, à la ligne d'entrée 20 604. Toujours dans la figure 10 on remarquera que la ligne 602 agit pour conditionner les portes 620, 622, 624. De cette façon les contenus des bascules 614, B16, 618 sont placés sur les lignes de sortie 606. La table E est la même que la table C, bien que le nombre des registres de la table E puisse différer du nombre des registres de la table C. 25 Comme mentionné ci-dessus les étages d'horloge "ME" dont on se réfère aux sorties dans le diagramme de circuit, figures 9A-9K. commandent la synchronisation et la séquence des diverses étapes du procédé de mesure d'efficacité. L'horloge "ME" n'est-pas représentée en détail, mais est semblable à l'horloge "T" figure 9A, qui commande la procédure de remplacement de bloc. On donne 30 ci-dessous la liste des diverses fonctions "ME" dont chacune est initiée par une impulsion appropriée ME comme indiqué. Ces fonctions ME sont décrites aussi dans l'organigramme, figures 11A-11D : ME1 : Tester le bit L dans le registre de maintien, fig. 9F. Si L = 0 aller à ME 32. 35 Si L = 1 aller à ME 2. ME2 : Enclencher la bascule F à 1 figure 9F. Diminuer le compteur LJ, figure 3F. Restaurer le masque d'argument 46, figure GE. Restaurer le masque d'écriture 47, figure 9G. 40 â 7.0 34360 44 r 2077507 Enclencher tous les indicateurs de correspondance à 1 (ligne 54 figures 9B et 9D). Transférer le numéro de bloc du registre maintien figure 9F. au champ de numéro de bloc du registre d'argument 32, fig. 9G. 5 Lorsque ME2 expire aller à ME3. ME3 : Régler à 1 le.champ du numéro de bloc du masque d'argument 46, figure 9E. A l'expiration de ME3 aller à ME4. ME4 : Associer sur le numéro de bloc mis en mémoire dans le registre 10 à argument 32, figure 9J. . A l'expiration de ME4 aller à ME5. ME5 : Interroger les indicateurs de correspondance (lignes 64 et 78 ffgures 9B et 9D). Extraire le mot de correspondance de AM et le disposer dans MDR, figures 9D et 9E. 15 Aller à ME6. ME6 : Restaurer le bit L dans MDR à 0 figure 9E. Régler le bit L dans le masque d'écriture à 1, figure 9G. Aller à ME7. ME7 : Ecrire le bit L (maintenant 0) de MDR de nouveau dans le mot de 20 correspondance dans AM (lignes 64 et 74, figures 9B et 9D). Aller à MES. ME8 : Restaurer le masque d'argument, figure 9E. Restaurer le masque d'écriture, figure 9G. Enclencher tous les indicateurs de correspondance à 1 25 (ligne 54 figures 9B et 9D). Restaurer la bascule EOL (fin de ligne] à 0. Aller à ME9. ME9 : Enclencher le bit R' dans le registre d'argument à 1 figure 9J Enclencher le bit R' dans le masque d'argument à 1, fig. 9E. 30 Enclencher le bit R' dans le masque d'écriture à 1, fig. 9G. aLler à ME10. ME10 : Faire une association sur le bit R' = 1, fig. 9J. Aller à ME 11. ME11 : Interroger les indicateurs de correspondance (lignes 64 et 78 35 figures 9B et 9D). Transférer le mot de correspondance à partir de AM à MDR, figures 9D et 9E, ou si aucun mot de correspondance enclencher la bascule EOL à 1. Aller à ME 12. ME12 : Tester la bascule EOL, figure 9D. 40 Si elle se trouve à 0 aller à ME 13. 70 34360 45 '2077507 10 15 Si elle se trouve à 1 aller à ME 27, ME 13 : Restaurer le bit R* dans MDR à 0, figure 9E Transférer le numéro de bloc de MDR au registre X figures 9E, 9F et 91 Aller à ME14 ME 14 : Ecrire le bit R' (maintenant 0) de nouveau dans le mot de correspondance le plus élevé dans AM (lignes 64 et 74J, figures 9B et 9D). Tester la sortie de l'unité de comparaison figure 9K. pour déterminer si E = A. Si E = A aller à ME8. Si E î* A aller à ME15. ME15 : Tester la sortie de l'unité de comparaison, fig. 9K.j pour déterminer si E est derrière B. Si "non" aller à ME20. Si-oui" aller à ME16. ME 16 : Augmenter le compteur Q, figure 9F. Augmenter le registre A, figure 91. Aller à ME 17. 20 ME 17 : Transférer le contenu du registre A au registre Y, figures 91 et 9H. Aller à ME 18. ME18 : Transférer (N-1) aux lignes d'entrée de la table C, figure 9B. Aller à ME 19. ME19 : Transférer le contenu du registre A aux lignes d'entrée cte la table E, figure 91. Aller à ME 8. ME2: Transférer le contenu du registre A au registre Y, figures 91 et 9H. Aller à ME 21. ME21 : Contrôler la sortie de l'unité de comparaison, figure 9H, pour déterminer si Y = E. Si Y = E aller à ME 19. i Y / E aller à ME22. ME22 ; Transférer la sortie de la table C au registre DEC, figure 9H. Aller à ME23. ME23 : Diminuer le réglage du registre DEC, figure 9H. Aller.à ME 24 25 30 35 40 £ 70 3^360 46 2Q775Q? 10 15 20 ME24 : Transférer le réglage du registre DEC aux lignes d'entrée de la table C et effectuer un test pour déterminer si le réglage DEC = 0 figure 9H. Si DEC = 0» aller à ME25. Si DEC / 0 aller à ME26. ME25 : Transférer le contenu du registre Y au registre B, figures SH et 91. Aller à ME19. ME26 : Diminuer le registre Y, figure 9H. Aller à ME21. ME27 : Tester la bascule F» figure 9F. Si F = 0 aller à ME24. si F t 0 aller à ME28. ME28 : Augmenter le registre A, figure 91 Aller à ME29. ME29 : Transférer le contenu du registre A au registre Y •figures 91 et 9H. Aller à ME30. ME30 Transférer le numéro de bloc du registre maintien au registre X, figures 9F et 91. Aller à ME 31. ME31 : Transférer le contenu du registre A aux lignes d'entrée ëela table E, figure 91. Transférer CN-1) aux lignes d'entrée de la table C, •figure 9H. Aller à ME32. ME32 : Restaurer le masque argument, figure 9E. Restaurer le masque écriture, figure 9E. Enclencher tous les indicateurs de correspondance à 1 Cligne 54, figures 9B et 9D). Transférer le numéro de bloc du registre de maintien auchamp dunuméro de bloc du registre d'argument fig. 9F et 9J. Aller à ME 33. Enclencher complètement à 1 le champ du numéro de bloc du masque d'argument, figure 9E. Aller à ME34. Effectuer une association sur le numéro de bloc ri s en mémoire dans le registre d'argument 32, fig.9J Aller à ME35-. 40 ME35 : Interroger les indicateurs de correspondance Clignes 64 et 78) 25 30 35 ME33 : ME34 : â 70 34360 47 2077507 figures 9B et 9D. Extraire le" mot de correspondance AM et le mettre dans MDR, figures 9D et 9E. Aller à ME 36. ME36 : Enclencher le bit R' dans MDR à 1, figure 9E. 5 Enclencher le bit R' dans le masque d'écriture à 1, fig. 9G. Aller à ME 37. ME37 : Ecrire le bit R' (1) dans MDR de nouveau dans le mot de correspondance dans AM (lignés 64 à 74), fig. 9B et9D. Aller à FIN (disposer l'impulsion sur la ligne 1000, figure 9, pour signaler au CPU d'initier la demande de mémoire suivante. (ME30 à ME41 ne sont pas utilisés dans la présente réalisation). ME42 Transférer le numéro du bloc demandé en cours du registre 24 au registre X, figures 9B, 9F, et 91. Aller à ME 43. ME 43 : Tester la sortie du circuit de comparaison sur la figure 9K pour déterminer si E est derrière B. si "non" aller à ME 44. 2q si "oui" aller à ME40. ME44 : Transférer les contenus du registre A au registre Y, ■figures 91 et 9H. Aller à ME 45. ME45 : Tester la sortie du circuit de comparaison, figure 9H, 25 pour déterminer si Y = E. Si Y = E aller à ME 47 Si Y * E aller à ME 51. (ME46 n'est pas utilisé dans cette réalisation). ME47 : Augmenter le compteur U, figure 9F. 3Q Transférer les contenus du registre A aux lignes d'entrée de la table E, figure 91. Lorsque ME 47 expire revenir a l'étape 502, figure 6, de l'algorithme de remplacement réel par la ligne 1006, figures 6 et 9A. 35 (cela initie le fonctionnement du monostable T16 dans l'horloge "T" 190, figure 9A). ME4S : Augmenter le registre A, figure 91. aller à ME 49. ME49 : Transférer les contenus du registre A au registre Y 40 figures 91 et 9H. 34360 48 2077507 Aller à ME 50. Transférer (N-1) aux lignes d'entrée de la table C, figure 9H. . . - - Transférer les contenus du registre A aux lignes d'entrée de la table E, figure 91. - Revenir à l'étape 5D2,■figure,B, par la ligne 1004 figures B et 9A. • - - ■ . (Cela initie-l'opération du monostable T1B de l'horloge "T" 198, figure 9A). - Transférer la sortie de la table C au registre DEC figure 9H aller à ME 52, Diminuer le registre DEC figure 9H. Aller à ME53. Transférer le réglage du registre DEC aux lignes d'entrée de la table C, figure 9H. Tester pour déterminer si le réglage de DEC = 0 figure 9H. Si DEC = 0 aller à ME55. Si DEC t 0 aller à ME54. Diminuer le registreY, figure 9H. - Aller à ME 45. Transférer les contenus du registre Y au registre B. Aller à ME 56. Restaurer le masque d'argument, figure SE. Restaurer le registre d'écriture, figure 9G. -Enclencher les indicateurs de correspondance à 1 (lignes 54 figures 9B et 9D). Restaurer la bascule EOL à 0. Enclencher tous les bits SS dans AM à 1 figure 9D. Aller à ME57. Enclencher le bit SS dans le registre d'argument à 1, figure 93. Enclencher le bit SS dans le masque d'argument à 1 Figure 9E. Enclencher le bit SS dans le masque d'écriture à 1 ■figure 9G. Aller à ME5B. Faire une opération d'association sur le bit SS mis en mémoire dans le registre d'argument, figure 91. Aller à ME59. 70 34360 49 2Ô775Ô7 ME59 : Interroger les indicateurs de correspondance Clignes 64 et 76) figures 9B et 90. Extraire le mot le plus élevé de AM, le mettre dans MDR, figures 9D et 9E, ou si aucun root de correspondance enclencher la bascule 5" EOL à 1, figure 9D. Aller à ME60. ME60 : Tester le réglage de la bascule EOL : Si 0 aller à ME61 ; si 1 aller à ME47. ME61 : Transférer le numéro de bloc aii mot de correspondance ■JO dë MDR au registre X , figures 9E, 9F et 91. Aller à ME62. ME62 : Tester le circuit de comparaison, figure 9K pour déterminer si E est derrière B. Si "oui" aller à ME63, si "non" aller à ME65. 15 ME63 : Restaurer le bit SS dans MDR à 0 figure 9E. Enclencher le bit L dans MDR à 1, figure 9E. Enclencher le bit L dans le masque d'écriture à 1 figure 9G. Aller à ME64. 20 ME64 : Ecrire le mot dans MDR de nouveau dans AM Clignes 64 Èt74, figures 9B et 9D). Aller à ME57. ME65 : Restaurer le bit SS dans MDR à 0, figure 9E. Restaurer le bit L dans le masque d'écriture à 0, 25 figure 9G Aller à ME64. ME66 : Restaurer la bascule F à 0, figure 9F. Augmenter le compteur P,figure 9F. Aller à ME8. 30 CME66 n'est excité que lorsque le bloc demandé n'est pas dans la mémoire de travail, figure 11A et figure 6, moment auquel une opération de mise à jour peut être réalisée comme spécifié dans l'étape 501 figure 6). Cela termine la liste des fonctions ME qui sont représentées schématiquement dans l'organigramme figures 11A— 11D. Les fonctions "T" repré-35 sentées dans la figure 7 sont décrites complètement dans le brevet de Nelson cité ci-dessus et ne sont pas décrites ici avec plus de détail. Pour une compréhension plus complète des fonctions "T" qui concernent l'algorithme de remplacement réel, on peut se référer audit brevet cité ci-dessus. On suppose que le système représenté dans les figures 9A-9K. fonc-40 tionne selon un mode d'uniprogrammation. Cependant, l'invention ne se limite â 70 3t»3êÛ ' 2Q775Q7 pas nécessairement à ce mode de fonctionnement. Lorsqu'une demande de mémoire est initiée par l'unité centrale de traitement, CPU, figure 9A, l'information ID et l'adresse du bloc désiré sont appliquées par une ligne 22 au registre 24, figure 9B et simultanément un signal est appliqué par .le CPU soit à la 5 ligne 26, soit à la ligne 28 pour enclencher la bascule d'altération 30, figure 9A. La bascule 30 est enclenchée à son état 1 si le bloc demandé doit être altéré. Autrement elle est laissée dans son état 0. Le CPU applique alors un signal à la ligne départ 100 qui est transmis par la porte OU 252 à la ligne 254 pour enclencher le monostable T0 de l'horloge "T" 198, ce qui 10 initie un cycle de fonctionnement du système. Premier exemple de fonctionnement Figures 4A, 4B, 12A, 12L Cet exemple comprend une routine "L" qui est uniquement définie par les étapes ME55 - ME65, figures 11B et 11H ME2 - ME7, figure 11A et ME28 - ME31, 15 figures 11A et 11C. La routine L qui rentre en jeu durant la phase finale de cette opération particulière, sera décrite au moment approprié ci-après. Dans l'exemple présent, figures 4A et 4B, la séquence de référenciation de bloc suivante est supposée : BL1, BL2, BL3, BL4, BL5, BL2, BL4 (altéré), 20 BL1, BLB, BL1, BL2, BL4. La séquence des opérations représentées en général dans les figures 4A - 4B est décrite avec plus de détail dans les figures 12A-12L. Comme première étape de cette séquence, le bloc BL1, est demandé par l'unité centrale de traitement CPU et il s'avère qu'il ne se trouve pas dans la mémoire de travail 25 WM (qui est supposée être initialement dans un état libre). Donc, le bloc BL1 doit être amené de la mémoire de soutien dans la mémoire de travail. En se référant particulièrement à la figure 11A, l'opération par laquelle on s'inté-' resse maintenant débute à l'étape ME66, qui dans ce cas amène l'augmentation du compteur P de 0 à 1, figure 12A. 30 Les étapes ME8 - ME12 sont alors réalisées pour déterminer si une opéra tion de mise à jour sera nécessaire (comme indiqué par la présence des bits R' emmagasinés dans la mémoire associative .AM). Dans le cas présent, on peut supposer que tous les bits R' sont à leur valeur initiale 0, et l'action se poursuit de l'étape ME12 à ME27, figure 11A, et de là à l'étape ME42, 35 figure 11B (la bascule F étant enclenchée à 0 dans l'étape ME66). Le numéro du bloc en cours de demande (BL1) est transféré au registre X, qui enclenche l'indicateur X dans la table E à l'adresse correspodant à BL1, figure 12A. Le registre B a un réglage initial de 1, comme expliqué ci-dessus, et puisque la valeur 1 de BL1 est initialement de 0 à Eàce moment est inférieur à B. Par 40 conséquent le résultat du test réalisé à ME43 figure 11D, est "oui". Cela 70 34360 51 2077507 aboutit à une séquence d'opération représentés par les étapes ME43-ME5Q. Ainsi le registre A est augmenté de 0 à 1, et ce nouveau réglage de A est transféré au registre Y pour enclencher l'indicateur Y à l'adresse 1 de la table C. Ensuite, la quantité (N-1) qui dans ce cas est 2 est amenée à la table C comme 5 valeur C finale pour l'adresse 1. Les contenus du registre A sont alors transférés aux lignes d'entrée de la table E ce qui enclenche la valeur E pour le blûc BL1 à 1. Le système est maintenant prêt à réaliser l'opération d'entrée 'de bloc réelle. Les positions de mémoire de bloc dans la mémoire de travail WM sont 10 supposées être disposées dans le même ordre que les positions de mot de mémoire correspondant dans la mémoire associative AM. Lorsque l'on charge initialement la mémoire de travail, l'entrée de chaque nouveau bloc dans la mémoire remplace un réglage tout en zéro de la position de mémoire sélectionnée avec le bloc demandé de l'information. En règle, générale, cependant, la position de mémoire 15 sélectionnée contiendra déjà un bloc d'information qui y a été précédemment amené, et dans un tel cas, le bloc arrivant est sur-écrit sur le bloc qui est remplacé. Dans le cas présent le bloc BL1 est entré dans la seconde adresse ou position de mémoire de la mémoire de travail, et le numéro de bloc correspondant BL1 est entré dans le mot correspondant de la mémoire associative. 20 Le choix de la seconde adresse dans ce cas s'explique en ce que l'indicateur de mot (représenté par le réglage des bascules indicatrices dans la mémoire associative) est supposé être initialement à la position la plus élevée ou première adresse, ce qui amène l'entrée suivante a être effectuée dans la position suivante ou seconde adresse, après quoi l'indicateur de mot est placé 25 à la seconde position de l'adresse correspondante pour indiquer que cette entrée est maintenant remplie. Après avoir amené le bloc demandé BL1 dans la mémoire de travail, le système demande de nouveau si le bloc demandé est dans la mémoire de travail, (ligne d'organigramme 1007 figures B et 7). Cette fois naturellement, la 30 réponse est "Oui" et les opérations décrites dans les étapes 503 - 504 et 505 - 506 figure B sont alors initiées. Le bloc BL1 est référencié dans la mémoire de travail par l'unité de traitement CPU et les bits R et AL dans la mémoire associative qui est associée avec le bloc BL1 dans la mémoire de travail sont enclenchés aux valeurs appropriées qui dans ce cas seraient R = 1 et AL = 0 35 puisque le bloc a été référencié mais non altéré. Le bit R' associé avec le bloc BL1 est aussi enclenché à 1. Toutes ces actions sont décrites dans la figure 12A, qui représente le réglage initial et final de la mémoire associative et les divers tables des registres qui sont utilisés par le système. Le bloc suivant d'information demandé par le CPU et dans l'exemple 40 présent est BL2. La séquence de l'Qpération est très semblable à celle décrite â 70 34360 52 2077507 ci-dessus en référence à BL1. La figure 12B représente l'action qui se produit lorsque BL2 est référencié par le système. Ainsi, P passe de 1 à 2, et A passe de 1 à 2. On donne à BL2 une valeur E de 2 pour correspondre avec la nouvelle valeur de A. Une valeur C de N-1 ou 2, est amenée dans la seconde adresse de 5 la table C. Les bits R et R' associés avec BL2 sont enclenchés a 1. La figure 12C représente l'action qui se produit lorsque le système demande le bloc BL3, qui ne se trouve pas dans la mémoire de travail à ce moment. Le compte P passe de 2 à 3, alors que le compte A de façon semblable passe de 2 à 3. Une valeur E de 3 est fixée à BL3. La troisième position de la table 1Q C contient maintenant une valeur C de 2. BL3 est amené dans la première adresse de la mémoire de travail et son bit R' associé est enclenché à 1. Le bit R associé est momentanément-enclenché à 1. Cependant, on doit rappeler que lorsque tous les bits R dans la mémoire associative atteignent un réglage à 1 simultané, ils sont automatiquement restaurés à 0. La figure 12C montre le 15 résultat de cette action dans le réglage final C = 0 des registres de bit R. L'action qui se produit durant les intervalles 4 et 5 de la séquence réelle des opérations de la figure 4A est décrite respectivement dans les figures 12D et 12E et puisqu'elle est très semblable aux actions qui se sont produites durant les intervalles 1-3, aucune description détaillée ne sera 20 présentée. Durant l'intervalle B de la séquence réelle des opérations, figure 4, un type différent d'action se produit, car c'est un cas où l'algorithme de remplacement réel trouve nécessaire de rechercher dans la mémoire de réserve un bloc d'information (BL2) qui récemment a été remplacé dans la mémoire de 25 travail. Cette actionest représentée dans la figure 12F. Le compte P passe de 5 à B, étape ME66 figure 11A. Dans ce cas, cependant le compte A reste à son réglage précédent de 5. Cela provient du test réalisé à l'étape ME43, figure 11B. La valeur de B est encore 1, mais la valeur E du bloc en cours de demande CBL2] est 2, cette valeur E ayant été fixée à BL2 lorsqu'il a été précédemment 30 référencié durant l'intervalle 2, figure 4A comme représenté dans la figure 12B. Ainsi, dans ces conditions la sortie du test réalisée à ME43 figure 11B est "non". L'étape suivante (ME44) met en cause le transfert des contenus du registre A au registre Y, enclenchant par là l'indicateur Y à la cinquième adresse 35 de la table C figure 12F. Puisque la valeur Y présente (5) n'est pas égale à la valeur E en cours (2) le test réalisé à l'étape ME45, figure 11B aboutit à une sortie "non", ce qui entraine la réalisation des étapes ME51 - ME54 de façon répétée jusqu'à ce que le réglage Y soit réduit à la valeur E en cours. Cela amène la réduction des valeurs C pour les adresses 5,4,3 de la 40 table C de 2 à 1 figure 12F. Avec Y étant maintenant égal à 1, la sortie de 70 34360 53 2Û7?507 l'étape ME45 devient"oui" et l'opération passe à l'étape ME47 figure 11D. Le compteur U est maintenant augmenté de 0 à 1 pour indiquer qu'un transfert de bloc non nécessaire BL2 a été réalisé par l'algorithme de remplacement réel, et la valeur E du bloc BL2 est mise à jour de 2 à 5, qui est la valeur A réel-5 le. La valeur A on doit le rappeler correspond au numéro de l'intervalle dans la séquence optimale des opérations lorsque le bloc en cours de demande (BL2 dans ce cas) aura été soumis à référence. Ainsi dans la séquence optimale d'opération, figure 4, le bloc BL2 aura été soumis à référence durant l'intervalle 5, et non durant l'intervalle B comme dans la séquence réelle des 10 opérations. Il existe maintenant une différence entre ces deux numéros d'intervalles, et cela est réfléchi dans le nouveau réglage 1 du compteur de transfert non nécessaire. Le bloc suivant qui doit être référencé par le CPU est BL4, qui réside effectivement dans la mémoire de travail n'ayant pas été remplacé puisqu'il 15 y a été amené durant l'intervalle 4 figure 4A. On suppose dans l'exemple présent que dans cette étape de fonctionnement, le bloc BL4 doit être modifié lorsqu'il est soumis à référence. Par suite lorsque les bits R et AL associés avec BL4 sont mis à jour comme indiqué dans l'étape 505, figure 6, les étapes 51B - 520, figure 7, les bits R et AL associés avec BL4 sont tous les deux 20 enclenchés à 1. Cette action est décrite aussi dans la figure 12G. L'action passe ensuite par l'étape 50B, figure B, dont les opérations constitutives sont représentées [dans le cas présent) par les étapes appelées ME1 et ME32-ME37 dans les figures 11A et 11C. Comme étape finale de cette séquence, le bit R' associé avec BL4 est enclenché à 1, figure 12G. La mémoire associative 25 contient maintenant deux mots dont les bits R' sont 1, c'est-à-dire les mots associés avec les blocs BL2 et BL4. La partie suivante de l'action [intervalle 7 de la séquence réelle figure 4B) donne un exemple d'utilisation de plusieurs bits R' de mémoire dans des buts de mise à jour, et elle illustre aussi comment un "jeu complet" peut 30 être défini. Cette phase de fonctionnement est initiée lorsque l'unité CPU demande le bloc BL1 qui ne se trouve pas alors dans la mémoire de travail WM. En référence à la figure 12H et avec la figure 4B, la première action qui se produit en réponse à la demande en cours pour BL1 est la restauration de la bascule F à 0 et l'augmentation du compteur P de 6 à 7 (étape. ME66 figure 11A), 35 ces deux éléments F et P sont représentés dans la. figure 9F du diagramme de circuit. La mémoire associative est ensuite conditionnée pour rechercher pour tous les mots dont les bits R' ont été enclenchés à 1 comme indiqué dans la figure 12H, les mots correspondant aux blocs 3L2 et BL4 (qui sont respectivement mis en mémoire dans les première et seconde positions pour le mot 40 de la mémoire associative) ont des bits R' » 1. En référence de nouveau aux â 70 34360 54 2077507 figures. 11A et 11C et particulièrement'aux étapes ME8 et suivante, la mémoire associative réalise la recherche initiale et extrait le mot de correspondance supérieur et le dispose dans le registre de donnée de mémoire MDR (figure 9E). Dans ce cas., le mqt de correspondance supérieure à la mémoire associative AM 5 est le mot correspondant au bloc BL2 dans la mémoire de travail WM. Le numéro de bloc BL2 est transmis au registre X (figure 91] pour réglage de l'indicateur X de la table E à sa position BL2 (figure 12H). Simultanément, le bit R* correspondant à BL2 est restauré à 0, ayant servi son but (étape ME13, ME14 figure 10 La valeur E actuelle de BL2 est 5, qui est égale à la valeur A actuelle de 5. De là l'opération passe de l'étape ME14, figure 11C à l'étape ME8, amenant la réalisation d'une nouvelle recherche dans la mémoire associative pour tout mot supplémentaire dont les bits R' sont 1. Le bit R' de BL2 ayant précédemment restauré 0, (étape ME13) , le seul mot dont le bit R' est présen--15 ternent 1 est le mot correspondant au bloc BL4 (figure 12H). Le numéro de bloc BL4, par conséquent est transféré au registre X pour enclencher l'indicateur X de la position BL4 dans la position E. La valeur E actuelle de BL4 est 4, qui est inférieure à la valeur actuelle de A ou 5. De là l'opération passe à l'étape ME14, figure 11C à l'étape ME15, où un test supplémentaire est 20 réalisé pour déterminer si la valeur E actuelle est derrière la valeur B actuelle. Dans ce cas, la valeur E de BL4 étant 4, un branchement "non" est effectué de l'étape ME15, figure 11C à l'étape ME20, où les contenus du registre A sont transférés au registre Y pour enclencher l'indicateur Y à la.cinquième position d'adresse C, figure 12H. A l'étape ME21, le test est effectué pour 25 déterminer si le réglage du registre Y actuel est égal à la valeur E actuelle. Attendu que la valeur E de BL4 est 4, alors que la valeur Y effective est 5 le test à l'étape ME21 engendre une sortie "non",, et l'opération se branche à l'étape ME22, figure 11C. Suivant les étapes ME22 à. FIE25 en séquence, la valeur C (1) ppur la cinquième position d'adresse C est transférée au registre 30 DEC, qui est diminué ce qui amène le réglage DEC à 0. Cela aboutit au transfert du réglage du registre Y au registre B (étape ME25) ce qui augmente la valeur B de 1 à 5. „ • L'opération passe maintenant de l'étape ME25, figure 11C à l'étape- ME19 où.le réglage, du registre A est transféré à la table E pour augmenter la valeur 35 E de BL4 à 5. On peut observer maintenant que les trois blocs BL2, BL4, BL5 actuellement en mémoire dans la mémoire de travail WM, ont des valeurs E de 5 qui st le réglage du registre B actuel. Ceci indique qu'un jeu complet a été défini pour l'intervalle de numéro 5 (c'est-à-dire, A = 5]. Dans la séquence optimale des opérations, figure 4A. 40 L'opération passe maintenant de l'étape ME19, figure 11C à l'étape ME8, 11C). à 70 34360 55 2077507 figure 1A, pour l'initiation d'une nouvelle recherche de la mémoire associative pour trouver des mots ayant des bits R' ■ 1. Puisqu'aucun mot de cette sorte n'est dans la mémoire associative au temps présent, une sortie "non" est engendrée à l'étape ME12, et l'action passe à l'étape ME27. 5 Attendu que la bascule F est enclenchée à 0, l'action passe de nouveau à l'étape ME42, figure 113 où le numéro de bloc demandé actuellement (BL13 est transféré au registre X. A ce moment, la valeur E de EL1 est 1(figure 12H] et puisque elle est inférieure à la nouvelle valeur B de 5 l'étape ME43 engendre une sortie "Oui" et l'action passe à l'étape ME48. 10 Les étapes ME48 à ME50 sont les opérations de mise à jour et le réglage du registre A est augmenté de 5 à B (figure 4B) ; la valeur N-1 (2) est insérée dans la table C à la sixième position d'adresse C (figure 12H) et la valeur A de 6 est insérée dans la table E comme nouvelle valeur de E de BL1. Toutes les opérations de mise à jour ayant maintenant été réalisées sur les 15 variables A,C et E (aussi bien que les valeurs variables précédemment réglées P et U), l'action passe maintenant à l'étape 502, figure B, où l'opération de remplacement de bloc est réalisée. En se référant à la division de l'étape 502 en ses étapes constitutives 510, 515, figure 7, on remarque que l'indicateur de mot passe de son réglage 20 actuel au mot suivant ayant une combinaison 0-0 des bits AL et R (étape 511). A partir de la figure 12H il est apparent que le second mot dans la mémoire associative ne satisfait pas cette description, car ces bits AL et R sont tous deux égaux à 1. Ainsi, l'indicateur de mot passe de la première position de mot à la troisième position de mot, où les deux bits AL et R sont enclen-25 chés initialement à 0. L'algorithme de remplacement amène alors le bloc nouvellement demandé BL1 dans la troisième adresse de la mémoire de travail WM, remplaçant le bloc BL5 qui s'y trouvait précédemment. Ainsi, dans un réglage final de la mémoire associative à cette étape de l'opération, les numéros de bloc BL2, BL4, BL1 occupent respectivement les première, deuxième, 30 troisième positions de la mémoire associative. L'action revient alors à l'étape 500 figure 7. Attendu que le bloc demandé actuellement BL1 est maintenant dans la mémoire de travail WM, une sortie "oui" est engendrée par l'étape 500 ce qui entraine la réalisation des étapes 503, B04, 505 et 506. Dans l'étape 505 qui 35 est subdivisée entre les étapes 51B à 520, figure 7, le bit R de BL1 est enclenché à 1 pour indique que le bloc BL1 est maintenant sur le point d'être référencé Rar le système. De façon semblable le bit R' du bloc BL1 est enclenché à 1 figure 12H (étape 506 figure B). Après que BL1 a été soumis à référence comme on vient de le décrire, le 40 système de traitement CPU initie une nouvelle demande de mémoire, demandant 70 34360 56 2077507 cette fois le bloc BL6 qui ne se trouve pas dans la mémoire de travail WM. Les actions qui se produisent en réponse à cette demande de mémoire sont décrites dans la figure 121. La valeur P passe de 7 à 8 et la valeur A passe de 6 à 7 (figure 4B). Le bloc BLB est amené dans la mémoire de travail dans la pre-5 mière adresse, remplaçant le bloc BL2 qui s'y trouvait précédemment. Le bloc BL6 est ensuite soumis à référence dans la mémoire de travail et son bit R' est enclenché à 1. La valeur E de BL6 est augmentée de 0 à 7, la valeur A actuelle. L'unité CPU demande maintenant le bloc BL1, qui se trouve actuellement 1Q dans la mémoire de travail WM. Puis le bloc BL1 est soumis à référence dans la mémoire de travail, il n'y aucune modification dans les valeurs de P et A en conséquence de cette opération (figure 12J). Le bit R' deBL1 est enclenché à 1, et le bit R de BL1 de façon semblable est enclenché à 1 comme représenté dans la figure 12J. 15 Le CPU demande maintenant de nouveau le bloc BL2, figure 12K. Dn doit rappeler a été remplacé au moment où BL6 a été amené dans la mémoire de travail (figure 121). De là BL2 doit être ramené dans la mémoire de travail. A ce moment, la mémoire de travail contient les blocs BL6, BL4, BL1 arrangés dans cet ordre comme indiqué sur la figure 12K. Les bits R' de BL6 et BL1 sont 20 enclenchés à 1. Par conséquent, lorsque la mémoire associative AM est explorée pour des mots ayant R' = 1 (étapes ME8-ME12, figure 11A), on trouvera BL6 et BL1. Attendu que la valeur E de BL6 est égale à la valeur A actuelle, c'est-à-dire 7, l'examen de BLB est sans effet dans ce cas, l'action passant simplement de l'étape ME14, figure 11C, à l'étape ME8, figure 11A. 25 Lorsque la mémoire associative est de nouveau explorée (étape ME10) on trouvera BL1 ayant un bit R' de 1, et dans ce cas, la valeur E actuelle (6) de BL1 n'est pas égale à la valeur A actuelle (7). De là, l'opération passe de l'étape ME14, figure 11C à l'étape ME15 et à partir de là elle se poursuit à l'étape ME20 jusqu'à l'étape ME24. Durant le cours de cetteséquence la 30 valeur C pour la septième position de la table C, figure 12K est réduite de 2 à 1. L'action passe alors par les étapes ME2B, ME21 à l'étape 19 où la valeur E du bloc BL2 est augmentée de 5 à 7, la valeur A actuelle. Cette actionest indiquée dans la figure 12K. L'action revient maintenant à l'étape ME8, figure 11A et progresse jusqu'à l'étape ME12. A ce moment n'ayant plus 35 de mot dans la mémoire associative dont les bits R' sont 1 à ce moment, l'action passe de l'étape ME27, figure 11A à l'étape ME42, figure 11B. A l'étape ME42, le numéro de bloc actuellement demandé (BL2) est transféré au registre X, enclenchant l'indicateur Y à la position BL2 de la table E figure 12K. La valeur E actuelle (5) de BL2 est égale à la valeur B (5) ; 40 de là à l'étape ME43 l'action passe à l'étape ME44, figure 11B. La valeur 70 34360 57 2077507 A (7) est transférée au registre Y, ce qui enclenche l'indicateur Y à la septième position d'adresse C dans la table C, figure 12K. On doit rappeler que la valeur C à cette adresse a déjà été réduite de 2 à 1 comme décrite ci-dessus. De là lorsque la valeur C diminue à ME52, figure 11B elle devient 5 0. Cela produit une opération différente de toutes les opérations décrites ci-dessus amenant le branchement de la séquence de ME53 à ME55 et initiant ainsi une nouvelle routine concernant l'utilisation des bits SSet L. A la première étape de cette routine (ME553 le réglage Y de 7 est transféré au registre B ce qui augmente la valeur B de 5 à 7. Ensuite à l'étape 10 ME56, tous les bits SS de la mémoire associative sont enclenchés à 1 en préparation 'une recherche ensérie dans tous les mots de la mémoire associative. Les étapes ME57 à ME61 sont effectuées sur chaque mot de correspondance (chaque mot dont le bit SS égal 13 dans la mémoire associative en commencçant avec le mot de correspondance du haut. Dans ce cas le mot de correspondance 15 du haut est BLB. Puisque la valeur E de BL6 (73 est égale à la nouvelle valeur de B l'action résultante entraine principale la restauration du bit SS à 0 (étapes ME65 à ME643. L'action revient maintenant à l'étape ME57 figure 11B pour initier une nouvelle séquence de recherche. Le mot suivant qui va être rencontré dans la 20 présente opération de recherche en série est celui correspondant au bloc BL4 (figure 12K3. On doit rappeler que le bloc BL4, du à son état altéré, a résidé de façon continue dans la mémoire de travail WM, puisqu'il a été le dernier référencié durant l'intervalle B de la séquence réelle des opérations (figure 4A3 s alors qu'autrement il aurait été remplacé à ce moment. Le bloc BL4 25 a une valeur E actuelle de 5 qui est inférieure à la nouvelle valeur B de 7 (figure 12K.3. Ainsi, le test réalisé à l'étape MEB2, figure 11D produit un branchement "oui" à l'étape MEB3 et MEB4 dans lesquels le bit L du mot associé avec BL4 est enclenché à 1, comme indiqué dans la figure 12K.(La signification du fait que le bit L de BL4 a été enclenché à 1 apparaitra lors de la référen-30 ce ultérieure à BL4, comme on le décrira bientôt]. Le dernier mot rencontré dans la recherche en série est celui correspondant à BL1, figure 12K.. Attendu que la valeur E actuelle de BL1 (7) est égale à la valeur actuelle de B, la sortie du test MEB2 (figure 11B3 est "non" et aucune action significative ne se produit. L'action passe par les étapes 35 MEB5, MEB4, ME57, ME60, ME47 où le compte de transfert non nécessaire (U) est augmenté de 1 à 2 pour souligner le fait que BL2 a dû être retransféré dans la mémoire de travail par l'algorithme de remplacement réel, alors que l'algorithme de remplacement optimal aurait conservé BL2 de façon continue dans la mémoire de travail (figure 4B3. La nouvelle valeur A (73 est maintenant 40 transférée à la table E, ce qui augmente la valeur E de BL2 de 5 à 7. La 70 34360 58 20/7507 mémoire de travail est maintenant remplie avec des blocs dont les valeurs E sont égales à 7 qui est le numéro de l'intervalle de la séquence optimale où ces trois blocs auraient été référencés successivement (figure 4B). De là on peut dire qu'un jeu complet a été défini pour l'intervalle optimal7, es qui 5 est réflété par le réglage B actuel de 7. Comme phase finale de la séquence de références aux blocs considérée maintenant, le bloc BL4 est soumis à référence. A cause de son état altéré comme décrit ci-dessus, il a été permis au bloc BL4 par l'algorithme de remplacement réel considéré dans la présente description (c'est-à-dire l'algorithme 10 décrit dans le brevet déjà cité) de rester dans la mémoire de travail WM à un moment où selon la logique de l'algorithme de remplacement optimal il n'aurait pas du y être. L'algorithme optimal aurait remplacé BL4 durant l'intervalle défini par A = 7, figure 4B. Cet état est reconnu par la procédure de mesure d'efficacité concernée à l'aide d'une demande d'opération de mise 15 à jour spéciale, dont les détails vont être décrits : En référence à la figure 11A et aux figures B et 12L une demande par CPU pour un bloc dans la mémoire de travail dont le bit L est présentement 1 amène le passage de l'action de l'étape ME1 aux étapes ME2 et ME3, où la bascule F (figure 9F) est enclenchée à 1 dans un but qui va être décrit, et 20 le compteur U est diminué (figure 9F) ce qui indique le fait que l'algorithme de remplacement pouvait éviter de réaliser un transfert de bloc que l'algorithme optimal aurait trouvé nécessaire. Ainsi,, on donne à l'algorithme de remplacement réel un "crédit" de 1. Le bit L du mot de correspondance (BL4 dans ce cas) est maintenant restauré à 0 (étapes ME4 - ME7) et l'action 25 passe à l'étape ME8 figure 11A. A ce moment, le système exécute une procédure de mise à jour de valeur identique à celle qui se produit normalement durant "une exception de bloc" lorsque le CPU a demandé un bloc qui n'est pas dans la mémoire de travail. Dans ce cas, le bloc demandé (BL4) est dans la mémoire de travail -, néanmoins 30 le système agit comme si une exception de bloc normale s'était produite. Pour cette raison l'action qui provient de la demande d'un bloc déjà dans la mémoire de travail dont le bit L est 1 peut être considéré comme "une pseudo-exception de bloc". Ce fait est souligné afin d'observer que les opérations de mise à jour réalisées sur U, A et les autres sont variables ne sont pas toutes 35 initiées par des demandes pour des blocs qui sont absents de la mémoire de travail. A ce moment (figure 12L) le seul bloc dans la mémoire de travail dont le bit R' = 1 est BL2. Puisque la valeur E de BL2 est égale à la valeur B actuelle 7, l'opération de recherche progresse en une boucle par les étapes 40 MES - ME14 et de nouveau à MES, figures 11A et 11B. Ensuite elle se déroule 70 34360 59 20/7507 par les étapes MES à ME12 à ME25. Puisque la bascule F a maintenant un réglage à 1 Cétape ME2) l'action se branche de l'étape ME 27 à ME28 où la valeur de A est augmentée de 7 à 8, figures 12L et 4B. Ensuite, la valeur C de la huitième adresse de la table G est augmentée à 2 et la valeur E du bloc BL4 est réglée 5 à 8 [étapes ME 29 à ME31 figures 11A et 11C). Suivant cela le bit R' de BL4 est enclenché à 1 (étapes ME32 - ME37), et l'action se termine. Le réglage A augmenté de 8 et le réglage U diminué de 1, figures 4B et 12L réfléchissant le fait que l'algorithme de remplacement réel a reçu un crédit pour avoir évité un transfert de bloc que l'algorithme de remplacement 10 optimal ou logique aurait trouvé nécessaire. On doit remarquer cependant, que ce résultat n'a été obtenu que parce que CPU a demandé un bloc ayant son bit L enclenché à 1, un tel bloc ayant résidé de façon continue dans la mémoire de travail depuis qu'il a acquis cet état. Si pour quelque raison le bloc BL4 avait été déplacé hors de la mémoire de travail entre le moment où son bit "L" 15 a été enclenché à 1, et le moment où il a été de nouveau demandé par le CPU, alors son bit "L" aurait été perdu et la remise de BL4 dans la mémoire de travail dans ces conditions n'aurait produit aucun effet du type que l'on vient de décrire. Second exemple de fonctionnement. 20 Figures 13 et 14A - 14F Le présent exemple utilise la routine "0" qui n'est définie que par les étapes ME16 - ME18 de l'ordinogramme figure 11C. Cette routine est décrite à la phase finale de la description se rapportant à ce fonctionnement. L'exemple représenté dans la figure 13 suppose la séquence de référen-25 ces aux blûcs suivante : BL1 BL2 BL3 BL4 30 BL5 BL2 BL4 (altéré) BL1 (altéré) BL6 35 BL2 BL4 BL1 BL7 Les sept premières actions de références aux blocs (allant jusou'è et 40 comprenant l'altération de BL4) sont identiques aux actions décrites dans » 70 34360 60 2077507 les six premiers intervalles de la séquence réelle des opérations représentées dans la figure 4A. Par conséquent ces étapes ne sont pas répétées en détail dans la figure 13, on se référera à la figure 4A pour cette partie du fonctionnement. Le système est maintenant dans l'état décrit dans la figure 12G. 5 La phase suivante du fonctionnement (figure 14A) est initiée lorsque le CPU demande le bloc BL1, qui n'est pas présent dans la mémoire de travail. L'action qui se produit durant cet intervalle comprend l'altération de BL1, ce qui entraine l'enclenchement à 1 du bit AL associé à BL1 figures 13 et 14A. Les blocs BL4 ET BL1 ont tous les deux un état, altéré. 10 Lorsque le CPU demande le bloc suivant BL6, l'algorithme de remplacement n'a pas d'autre choix que d'amener le bloc nouvellement demandé dans la première adresse de WM, où il remplace BL2, figure 14B. Lorsque BL6 est référencié dans la mémoire de travail, son bit R devient 1, mais puisque tous les bits R de la mémoire associative ont maintenant la valeur de 1, ils sont tous 15 restaurés à ce moment. Lorsque BL2 est demandé (figure 14C) la seule adresse à laquelle il peut être amené dans la mémoire de travail est la première adresse, due à l'état altéré des blocs BL4 et BL1. Le système de mesure identifie le transfert de BL2 dans la mémoire de travail comme un transfert non nécessaire (figure 13) 20 et augmente le compte de U à 2. La référence à BL2 est alors suivie par la référence à BL4 (figure 14D) et BL 1 (figure 14E) qui sont tous les deux dans la mémoire de travail. Les trois blocs dans la mémoire de travail (BL2, BL4, BL1) ont maintenant des bits R' égaux à 1. Fortuitement, bien que la référence à BL1 soit représentée dans les figures 13 comme se produisant durant l'inter-25 valle optimum 8, la mise à jour de A de 7 à 8 est effectivement retardée comme indiqué dans la figure 14E et décrit plus complètement ci-après. La demande pour le bloc BL7 effectuée par le CPU (figure 14F] initie une opération de mise à jour de valeur. On se réfère à la figure 11A, le compteur P premièrement est augmenté, étape ME66, ce qui amène le passage du compte P 30 de 9 à 10, comme indiqué dans la figure 13 et la figure 14F. Ensuite dans les étapes MES - ME14, figures 11A et 11C la mémoire associative est explorée pour les mots dont les bits R' sont 1. Le premier mot tel rencontré est BL2 (BL7 n'ayant pas été amené encore dans la mémoire de travail). La valeur E de BL2 est égale à la valeur A actuelle de 7 ; de là l'action revient à l'étape ME14 35 à l'étape ME8, et une nouvelle recherche est effectuée. Cette fois le mot dans la mémoire associative correspondant à BL4 est rencontré. La valeur E de BL4 (maintenant 5) diffère de la valeur A actuelle (7) mais est égale à la valeur actuelle B (5). De là le fonctionnement du système progresse par les étapes ME14 à ME15 à ME20, figure 11C et de là par 40 les étapes ME21 - ME24 à un point de décision. Comme résultat d'une opération â 70 34360 61 2077507 de mise à jour de valeur précédente [figure 14C) la valeur C à la septième position d'adresse dans la table C a été réduite de 2 à 1. Maintenant ( figure 14F) la valeur C dans la même position a été réduite à 0 (figure 14F). Par conséquent la sortie de l'étape ME 24, figure 11C, est "oui". Cela amène 5 l'augmentation de la valeur B de 5 à 7 [étapes ME 25) ce qui définit un jeu complet pour l'intervalle 7 de la séquence optimale (figure 13), un tel ensemble comprenant BL6, BL2 et BL4. Suivant cela la valeur E de BL4 est augmentée de 5 à 7 (étape ME 13). L'action revient maintenant à l'étape MES figure 11A pour la recherche finale. 10 Le dernier mot restant dans le bit R' = 1 est BL1. La valeur E de BL1 est B, alors que la valeur mise à jour de B est maintenant 7 comme noté ci-dessus. A est aussi égal à 7 au moment présent. De là lorsque les tests aux étapes ME14 et ME15 sont réalisés, figure 11C, l'étape ME14 engendrera une sortie "non" et l'étape ME15 engendrera une sortie "oui". Cela dirige 15 l'action à l'étape ME16, où le compteur Q passe de 0 à 1. (figure 14F), et la valeur A passe de 7 à 8. L'augmentation de Q comme on viert de le décrire amène "un facteur d'incertitude" dans la mesure de l'efficacité de remplacement. La formule d'efficacité de remplacement peut être écrite comme : P-(U-Q) > Eff. > P-U P P 20 Cette équation spécifie un domaine de valeurs possibles pour l'efficacité plutôt qu'une valeur particulière. La nécessité pour cette spécification de domaine provient du fait que le système de mesure décrit n'a aucun moyen pour indiquer l'ordre suivant les blocs ayant les valeurs de bits "R' 1" 25 ont été soumis à référence par le système de traitement et il suppose que ces blocs ont été soumis à référence dans l'ordre dans lequel ils ont été disposés dans la mémoire de travail. Dans certaines conditions cette hypothèse peut conduire à une conclusion erronée sur l'efficacité de l'algorithme de remplacement réel. Dans l'exemple présent, il arrive ainsi que les blocs ont été 30 soumis à référence dans le même ordre que celui selon lequel ils ont été disposés dans la mémoire de travail et dans ces circonstances, l'algorithme de remplacement obtient un crédit pour avoir gardé le bloc BL1 disponible dans la mémoire de travail (à cause de son état altéré) lorsque la logique de l'algorithme de remplacement optimal (qui ne donne aucune signification 35 spéciale à l'état altéré) aurd-t rendu nécessaire de transcrire à nouveau BL1 dans la mémoire de travail à partir de la mémoire de réserve. Dans ce cas cependant, le crédit donné à l'algorithme de remplacement réel est un crédit conditionnel ou "contestable" (Q), car avec une mise en ordre différente des actions de référence aux blocs (ne correspondant pas à l'ordre dans 40 lequel les blocs référencés ont été mis en mémoire dans la mémoire de travail), â 70 34360 62 2077507 il est possible que l'algorithme de remplacement optimal ait fonctionné plus efficacement que l'algorithme de remplacement réel. Cela n'est pas susceptible de se produire lorsque la mémoire de travail n'a qu'une capacité de trois blocs, comme supposé ici dans des buts illustratifs mais cela peut très bien se 5 produire pour une mémoire ayant une capacité beaucoup plus importante comme cela est généralement vrai dans la pratique. Par conséquent, le système reconnaît les diverses possibilités inhérentes à ce type de situation en augmentant les valeurs Q et A mais en ne diminuant pas le compte U de telle sorte que le compte U non modifié par le compte Q fixe la limite inférieure du domaine 10 d'efficacité alors que le compte U réduit par le compte C} fixe la limite supérieure du domaine d'efficacité, comme spécifié par l'équation ci-dessus. L'action e poursuit maintenant dans l'étape ME17 figure 11C où la nouvelle valeur A de 8 est transférée au registre Y pour enclencher l'indicateur Y de la table C à la huitième position d'adresse C figure 14F. Ensuite à l'étape 15 ME18, la valeur (N-1) de deux est amenée dans la table C comme nouvelle valeur C pour cette huitième position. L'action revient maintenant à l'étape ME19 où la nouvelle valeur A de 8 est tranférée à la table E comme nouvelle valeur E de BL1. Ensuite l'action revient à l'étape initiale ME 8 dans la séquence de recherche. Puisqu'il n'y a plus de mot ayant leur bit égal à 1, cette phase 20 de l'opération de mise à jour de valeur est terminée, et l'action passe maintenant successivement par les étapes ME8, ME12, ME27 à ME42 figure 11B. A l'étape ME42 le numéro de bloc demandé actuel (BL7) est transféré du registre 24 (figure 91). Puisque la valeur E actuelle (0) de BL7 est inférieure à la valeur actuelle B (7) le test de l'étape ME 43 figure 11B aboutit à un 25 branchement à l'étape ME48, où le réglage du registre A est augmenté à 9 (figures 13 et 14F). Ensuite à l'étape ME49 la nouvelle valeur A de 9 est transférée au registre Y, et à l'étape ME50, la valeur (N-1) est transférée à la 9ème position Y de la table C, figure 14F. (On suppose dans les buts présents que le compteur d'adresse C a une capacité suffisante pour une 9ème 30 position. Cependant si seulement trois ordres binaires sont utilisés dans des buts d'adressage, le réglage d'adresse reviendra alors à sa position n°1 et le fait que cela est réellement la 9ème position C devra être reconnu au moyen d'un expédient convenable tel que l'utilisation d'un bit de report d'ordre supérieur). A l'étape ME50, la nouvelle valeur A de 9 est amenée dans 35 la table E comme valeur E mise à jour de BL7 figures 13 et 14F. Cela termine l'opération de mise à jour des valeurs pour le bloc BL7. Le système passe maintenant à l'étape 502, figures 6 et 7 où l'opération de remplacement de bloc est exécutée, amenant le remplacement de BL2 par BL7 dans la mémoire de travail. CPU référence alors le bloc BL7 dans la mémoire 40 de travail, action au cours duquel les bits R et R' de BL7 sont enclenchés à 1. â 70 34360 63 2077501 Cela termine la séquence représentée dans la figure 13. On peut mentionner un autre point en relation avec la séquence que l'on vient de décrire. On remarquera que dans le septième intervalle de la séquence optimum [A = 7)figure 13 le système de mesure indique un "jeu complet" des blocs 5 BL6, BL2, BL4 pourrait avoir été rendu simultanément possible pour référenciation dans la mémoire de travail durant ce même intervalle sans nécessiter une opération de remplacement de bloc: En fait cependant, aucun tel jeu complet de bloc n'a jamais existé dans la mémoire de travail durant la séquence réelle des opérations. En référence aux figures 14B et 14C et avec la figure 13 on 10 peut remarquer qu'à divers moments durant les intervalles 8 et 9 de la séquence réelle la mémoire de travail contenait soit l'ensemble des blocs BL2, BL4, BL1, soit l'ensemble des blocs BLB, BL4, BL1 mais n'a jamais contenu l'ensemble des blocs BL6, BL2, BL4. Cela ne signifie pas nécessairement que chaque "jeu complet " défini par 15 le système de mesure n'existerait que dans l'abstrait et non dans les faits réels. Occasionnellement, il peut arriver qu'un jeu complet défini par le système de mesure coïncide avec l'ensemble des blocs qui résident effectivement dans la mémoire de travail à ce moment. Souvent, cependant cela n'est pas le cas et dans les exemples particuliers choisis pour illustration, cela n'est jamais 20 le cas. Le procédé de mesure d'efficacité de remplacement décrit ici permet de réaliser une mesure en direct, dynamique de l'efficacité de remplacement de bloc d'un système de traitement de donnée à mémoire virtuelle sans diminuer de façon significative les possibilités de ce système. Cela est rendu possible 25 dans la présente application par l'utilisation de bits R' mis en mémoire, qui permettent la réalisation des fonctions de mise à jour durant des périodes où elles interfèrent très peu ou pas du tout avecle fonctionnement normal des système Cela permetd'effectuer une comparaison sur une base progressive intermittente entre le fonctionnement de l'algorithme de remplacement réel 30 et celui de l'algorithme de remplacement optimal qui est dérivé de l'algorithme "MIN" mentionné ci-dessus. Afin de réaliser une telle comparaison sur une base complètement conforme à la réalité la présente technique de mesure comprend des dispositifs pour reconnaître les cas occasionnels ou rares où un algorithme de remplacement réel peut agir de façon plus efficace que l'algorithme de 35 remplacement optimal Croutine "L") ou lorsqu'il y a un doute pour savoir si l'algorithme optimal peut avoir fonctionner de façon plus efficace que l'algorithme réel (routine "Q"] du à l'incertitude sur l'ordre réel de référenciation représentées par les bits R' mis en mémoire. Bien que l'on ait décrit dans ce qui précède et représenté sur les dessins, 40 les caractéristiques principales de l'invention, appliquées à un mode de réa- â 70 34360 64 2077507 lisation préférée de celle-ci, il est évident que l'homme de l'art peut y apporter toutes modifications de forme ou de détail qu'il juge utiles sans pour autant sortir du cadre de ladite invention. 70 34360 B5 2077507 REVENDICATIONS 1. Dispositif utilisable dans un système de traitement de données du type à "mémoire virtuelle" dans lequel des blocs d'information sont emmagasinés à des adresses de bloc numérotées dans une mémoire de réserve et à certains moments sont aussi emmagasinés, à des adresses de travail temporairement 5 associées avec les dites adresses de bloc, dans une mémoire de tia/ail ayant une capacité limitée à N blocs, ledit système comportant une unité centrale capable de demander des blocs d'information désignés par leur adresse dans la mémoire de réserve et de "faire référence" à de tels blocs pour en extraire ou y introduire des informations lorsqu'ils se trouvent dans la mémoire de 10 travail et capable également lorsque le bloc qu'il demande est emmagasiné seulement dans la mémoire de réserve, d'extraire ce bloc de la mémoire de réserve et de l'introduire dans la mémoire de travail à une adresse de travail sélectionnée en conformité avec un algorithme de remplacement prédéterminé, le bloc introduit remplaçant celui qui était précédemment emmagasiné à ladite 15 adresse de travail., ce dispositif ayant pour fonction de mesurer l'efficacité dudit algorithme de remplacement en comparant progressivement le nombre des remplacements de bloc réellement effectués avec le nombre des remplacements de bloc qui auraient été effectués si l'unité de traitement de données avait opéré sous la 20 commande d'un algorithme de remplacement "optimal" qui prend connaissance des blocs ayant résidé ou qui sont sur le point de résider dans la mémoire de travail y compris le bloc actuellement demandé par l'unité de traitement, et de l'ordre dans lequel ces blocs ont été introduits dans ladite mémoire de travail. remplacement déjà écoulés depuis le début de l'opération, un intervalle de remplacementCappelé également "intervalle" par la suite) étant défini comme l'intervalle de temps séparant deux remplacements successifs, des moyens de marquage pour enregistrer des indices CR') affectés au 30 cours de chacun des intervalles à ceux des blocs auxquels il est fait référence par l'unité de traitement au moins une fois pendant cet intervalle» ces indices étant ramenés à zéro à chaque remplacement, des moyens de calcul pour commander à certains moments le fonctionnement de l'unité de traitement de façon que cette unité détermine, en fonction 35 des dits indices et de l'adresse du dernier bloc damandé, le nombre optimal d'intervalles, c'est-à-dire le nombre des intervalles de remplacement qui aurait été nécessaire pour exécuter le programme jusqu'au point atteint au moment du calcul, si le système avait fonctionné sous le contrôle d'un algori- 25 et étant caractérisé par la combinaison des éléments suivants : des moyens de comptage pour compter le nombre des intervalles de T 70 34360 66 20/7507 thme de remplacement optimal élaboré selon des règles déterminées à partir d'indications sur la séquence selon laquelle les blocs ant été demandés par l'unité de traitement,. et des moyens de déclenchement pour mettre en action les dits moyens 5 de calcul en vue de mettre à jour la détermination dudit nombre optimal d'intervalles pendant les périodes de temps où le système attend qu'un bloc demandé soit transféré dans la mémoire de travail. 2. Dispositif selon la revendication 1 caractérisé en .outre en ce que les 10 moyens de calcul comprennent : des organes d'enregistrement, agissant toutes les fois que l'unité de traitement demande un bloc non présent dans la mémoire de travail pour enregistrer le numéro d'adresse de ce bloc et le numéro de l'intervalle optimal correspondant à l'intervalle réel au cours duquel ledit bloc efet demandé, 15 des moyens de désignation pour désigner les intervalles définis par l'algorithme de remplacement optimal et contenant un "jeu complet", c'est-à-dire les intervalles optimaux correspondant à un ou plusieurs intervalles de remplacements réels et durant lesquels la mémoire de travail aurait contenu N blocs avec cette particularité que l'unité de traitement aurait fait réfé-20 rence au moins une fois à chacun de ces N blocs durant une période comportant l'intervalle optimal en question et pouvant comporter également une séquence de 1 à N-1 intervalles optimaux suivant ledit intervalle optimal, et des moyens placés sous la dépendance des dits organes d'enregistrement et des dits moyens de désignation des intervalles optimaux contenant un jeu 25 complétât agissant sur les moyens de calcul pour exclure de la détermination courante des numéros de l'intervalle optimal toutes les demandes de bloc qui ont été faites avant le plus récent des intervalles désignés comme contenant un jeu complet. 3. Dispositif selon la revendication 2, caractérisé en outre par les éléments 30 - suivants : - des moyens de détection placés sous la dépendance des numéros d'adresse enregistrés par les organes d'enregistrement et des numéros d'intervalles optimaux contenant un jeu complet, numéros fournis par les moyens de désignation, pour détecter les cas où l'algorithme de remplacement effectivement 35 utilisé a permis à un bloc particulier de rester.dans la mémoire de travail sans être soumis à référence pendant plusieurs intervalles de remplacement successifs correspondant à une série d'au moins N intervalles optimaux successifs commençant par un intervalle qui contient un jeu complet, et des moyens placés sous la dépendance des dits moyens de détection à 70 34360 67 2077507 lorsque ceux-ci ont détecté un tel cas et agissant si l'unité de traitement fait de nouveau référence audit bloc particulier avant que ce bloc quitte la mémoire de travail pour augmenter le numéro de l'intervalle optimal sans changer le numéro de l'intervalle réel en cours. 5 4. Dispositif conforme à la revendication 2 ou 3 caractérisé en outre en ce que les moyens de calcul comprennent : des moyens d'indexage de bloc pour attribuer à chaque bloc auquel il est fait référence un index CE) représentant le numéro de l'intervalle optimal le plus récent correspondant à l'intervalle réel durant lequel il 10 a été fait référence à ce bloc, une table de compteurs ayant des positions d'enregistrement adressables en fonction des nombres représentant les numéros des intervalles dans la séquence d'opérations optimale, chacune de ces positions étant capable d'enregistrer une variable CC) susceptible de prendre des valeurs comprises 15 entre 0 et N-1, la première valeur attribuée à cette variable pour un intervalle donné étant égale à l'une de ces limites et cette valeur étant attribuée la première fois que l'unité de traitement fait référence à un bloc dont l'index CE) correspond au numéro dudit intervalle donné, des moyens de modification du contenu de la table de compteurs agissant 20 chaque fois que l'unité de traitement fait référence à un autre bloc ayant la même valeur d'index CE) pour modifier d'une unité la variable CC)de manière à la rapprocher de l'autre limite, de sorte que cette variable CC) atteint cette deuxième limite toutes les fois que N blocs ayant le même index (E) sont soumis à référence par l'unité de traitement, la détection du fait que 25 cette deuxième limite est atteinte étant utilisée pour reconnaître que l'intervalle optimal dont le numéro correspond à cet index (E) contenait un jeu complet, des moyens de modification d'index agissant chaque fois qu'un bloc ayant une valeur d'index CE) inférieure au numéro B du plus récent des intervalles 30 optimaux désigné par les moyens de désignation comme contenant un jeu complet est demandé par l'unité de traitement, pour augmenter le numéro CA) de l'intervalle optimal correspondant à l'intervalle réel en cours et pour porter la valeur d'index CE) dudit bloc à la nouvelle valeur (A), et des moyens de mise à jour placés sous la dépendance des indices CR') 35 enregistrés par les moyens de marquage et agissant toutes les fois que l'unité de traitement demande un bloc d'information qui n'est pas présent dans la mémoire de travail, pour provoquer une opération de mise à jour du numéro d'intervalle optimal CA), des valeurs d'index affectées aux blocs (E), des contenus des compteurs CC)-Et du numéro (B) du dernier intervalle optimal 7.0 34360 68 2077507 contenant un jeu complet, cette action des moyens de mise à jour intervenant toutes les fois que le système est en attente pendant l'exécution d'un remplacement de bloc.