Architecture III Ordonnancement des processus, mémoires et systèmesde fichier

CHAPITRE 1

Système d'exploitation

1.1 Introduction1.2 Les systèmes d'exploitation1.2.1 Pourquoi un système d'exploitation ?- D'un coté, un (ou plusieurs) utilisateur(s) (user)

- Attend un résultat de l'ordinateur- Utilise des outils pour sa requête- Utilise un (des) programme(s) pour accomplir cette tâche

- D'un autre coté, un ordinnateur- Dispose de resources physiques

- De calcul (CPU)- De mémoire (RAM)- De stockage (Disque Dur, CD, clés…)- D'interface (clavier, écran, imprémante…)

- Comment l'utilisateur peut tier profit des resources à disposition pour obtenir son résultat ?- Comment les ressource peuvent ««communiquer»» entre elles pour arriver au résultat ?- Comment partager ces roussources entre plusieurs utilisateurs simultanés ?- Comment ne pas pas tout recommencer si un élement change (modification du CPU, changementde programme, passage à une autre plate-forme (PC-PDA) …)

Utiliser un système d'exploitation⇒ !Un sysème d'exploitation, ou OS (Operating System),– Sert d'interface entre le matériel et les applications– Gère le partage des roussources matérielles entre les applications et les utilisateurs– Gère les échanges entre les applications– Gère l'indépendance des applications et leur isolation.Exemple de système d'exploitation :— DOS, Windows (3.11, 95, XP, CE, …)— Unix, Linux, BSD, Mac OS X, …— VMS, Symbian, Android , …— Beaucoup d'autres, souvent spécialisés et propriétaire.

1.2.2 Classement des systèmes d'exploitation– Mono-tâche : une seul tâche peut être éffectuée en même temp. Les autres tâche doivent attendrela fin de la tâche courante pour pouvoir commencer.

– Multi-tâches : plusieurs tâche peuvent s'exécuter en parallèle, sans bloquer le lancement d'unenouvelle tâche supplémentaire.

– Mono-utilisateur : un seul utilisateur peut utiliser le système en même temps

– Multi-utilisateur : plusieurs utilisateurs peuvent utiliser le système en même temps

Un système peut être mono/multi-tâches, mono/multi-utilisateur.⇒Il y a des systèmes hybrides (Windows 9x)

1.2.3 Un peu d'histoire1.2.3.1 Windows1.2.3.2 Unix

– Écrit à l'origine en assembleur,– le Langage C a été créé pour Unix et Unix a été réécrit en C pour plus de portabilité,– À l'origine de la norme Posix,– Permet la communication entre machine– Système multi-utilisateur– Système multi-tâches– Système de développement : beaucoup d'outils disponible de base,– Dispose d'interpréteur de commande puissante (shell)

1.2.4 Rôle

Définition Système : ensemble des fonctions et activités qui gèrent les ressources d'un ordinateur pourpermettre leur utilisation par les applications des utilisateurs

Noyau : ensemble des fonctions sysèmes appelées soit par les applications nécessitant desressources, soit par les activités du sytème pour traiter des événement matériels.

RôleTrois rôles principaux : gestion du matériel, de l'information, des utilisateurs

1.3 Gestion des utilisateurs

– Service de connexion/déconnexion– Vérification de validation de l'accès (login/passwd)– Initialise l'environnement et les ressource des utilisateurs

– Service d'administration des utilisateurs– Utilisateur : gestion de leur ressources, modification de paramètres (passwd...)

– Administrateur : gestion globale des ressource, ajout d'utilisateurs, politique d'allocation desressource, sauvegarde, sécurité, etc.

1.4 Gestion des informations

La gestion d'information est une tâche principale d'un système d'exploitation

1.5 Gestion des fichiers

Les rôles principaux du système de gestion des fichies sont de gérer :– L'espace physique pour le stockage,– Les transfert logiques d'informations,– Les protections.

Le support physique est en générale découpé en zone de longueur fixe (blocs).Rôle du système :— Gérer l'espace libre,

Le système assure l'allocation et la restitution des blocs (liste des blocs libre).— Gérer l'allocation des blocs physiques sur le support

Mémorise les informations des fichiers et répertoires de la structure du système de fichier.— Gèrer l'allocation des fichiers au niveau logique et selon la structure du système de gestion defichiers

La protection dans un système de gestion utilise des

– listes de droits d'accès (droit rwx sous unix ),– liste de contrôle d'accès (Access Control List – ACL )Ces listes associées a chaque objet du système de gestion de fichiers précisent les droits del'ensemble des utilisateurs et leur droit d'accès.

– Certains systèmes décrivent pour chaque utilisateur ses droits, – D'autre partitionnent l'ensemble des utilisateurs en groupes

— La deuxième solution est moin souple et moins sûre,Le transfert logique entre ''système de fichier'' et ''processus utilisateurs'' nécessite deuxmécanismes :– Des méthodes d'accès

— Fonction spécifiques à la structure de fichiers (open, read...)— Organisations traditionnellement implantées :

– Les fichiers séquentiels : accès exclusivement séquentiel ;– Les fichiers séquentiels indexés : accès direct via une table d'index et des clés ;– Les fichiers direct : accès direct par le numéro de l'enregistrement.

– Un mécanisme de gestion des tampons— Gère les tampons nécessaire aux entrès/sorties physiques— Résident dans une zone mémoire du système pour rendre les entrées/sorties performantes— Optimisation par heuristique pour l'association tampons-blocs physique

1.6 Classifications des systèmes

Trois familles classés selonn leurs fonctionnalités :– Système temps réel

Caractérisés par la prise en compte des contraintes temporelle de l'envirennement– Système de développement

Système à temps partagé interactifs– Système pour l'exploitation

Utilisé sur des ''main-frame'', traitement par lots (traitement de masse).Objectif : optimisation de l'utilisation coûteuse des ressources matériels.

– Systèmes monoprogrammés— Premiers système d'exploitation développés— Un seul processus réside en mémoire et utilise toutes le ressources — Ordinateur utilisé séquentiellement par différents processus

– Traitement par lot– Système multiprogrammés

— Plusieurs processus résident en mémoire— Partage l'unité centrale

— Cèdent leur tour durant les entrées/sorties

Comparaison ( durant les entrées/sorties, unité centrale inactive) Le temps consommé par lesystème se décompose en 25 % pour les utilisateurs, 10 % pour l'auto-gestion du système

— Système monoprogrammé Inconvénient Un utilisateur doit attendre que l'ordinateur soit libre avant de lancé son programme— Système multiprogrammé Avantage Mise en concurrence des programmes pour leur

exécution Optimisation de l'utilisateur des ressources coûteuse de l'ordinateur

Temps unité centrale monoprogrammé multiprogrammé

En attente 50 % 5%

Utilié par le système 10% 35%

Consommé par les utilisateurs 40% 60%

Remarque : Défférence multiprogrammés/multitâchesSystème multiprogrammés : plusieurs processus utilisateur en mémoire et concurrents pour leurexécutionSystème multi-tâches : Concurence entre un processus utilisateur et des fonctions du système

Inconvénient des systèmes multiprogrammésLes processus ne relâchent l'unité centrale que lors des entrées/sorties

CHAPITRE 2

Les stratégies d'allocation de l'unité centrale ont en générale pour but de trouver un équilibre entrela durée d'utilisation des ressource par les processus et le temps qu'ils mettent pour s'exécuter.L'objectif est de satisfaire les demandes d'exécution des programmes en respectant certainescontraintes parmi les suivantes :— garantir un temps d'attente fini et une durée minimale d'allocation,— respecter certaines priorités entre les processus,— garantir l'allocation avant une date fixée,— arrêter un processus dépassant une durée donnée.

2.1 Stratégies2.1.1 Les différentes étapes de l'allocation de l'unité centrale

1. Entrée des processus demandeurs,2. choix d'un processus en attente,3. choix d'un processus à allouer,4. interruption de service.

2.1.2 Stratégie sans recyclage des demandes

L'allocation de l'unité centrale est effectuée pour une demande compète, il n'y a pas de préemption(suspension de l'exécution au profit d'un autre processus). La stratégie FIFO est simple et a prioriefficace :

– FIFO impératif : on mélange les petits et les gros demandeurs, ce qui défavorise les petits;– FIFO indicatif : la file est triée sur un critère, on fait alors des insertions en milieu de file.

L'éfficacité est raisonnable, mais il y a pénalisation des gros demandeurs; – FIFO à priorités : plusieurs files sont gérés en FIFO. Les files sont classées par priorité, on

ne choisit un demandeur dans une file que si les files de priorité supérieur sont vides

2.1.3 Stratégie avec recyclage

Les stratégies avec recyclage effectuent l'allocation de l'unité centrale par tranche de temps appeléequantum, les demandes ne sont pas servies globalement, mais par fractionLe choix de la durée du quantum est fondamental :

— un quantum très court favorise les traitements interactifs,— un quantum long augmente le débit global du système

2.1.3.1 La stratégie du tourniquet

La stratégie du tourniquet (Round Robin) effectue l'allocation de l'unité centrale par quantum. Leprocesseur est alloué successivement à chaque processus, si au bout du quantum alloué, le processusne s'est pas terminé, il est interompu et placé en queue de la file des demandeurs.

2.1.3.2 La stratégie du tourniquet à deux niveaux

La stratégie du tourniquet à 2 niveaux : par une étude de la charge sur un système de temps partagé(IBM CP/CMS), on a constaté deux catégories de demandes :

— les demandes courtes à caractère fortement interactif : on leur alloue un quantum de 20ms,— les demandes langues, correspendant aux travaux différés : on leur alloue un quantum de 100ms

Le recyclage provoque :— une baisse de la priorité réalisée par un changement de file,— une allocation plus longue.

2.1.3.3 Unix

Dans le système Unix, la stratégie fait appel à un tourniquet multiniveau à quantum unique– à chaque processus prêt est affectée une priorité flottante. Cette priorité reflète la consommation etla demande en resources du processus.– à chaque niveau de priorité correspondant une file desservie selon une politique FIFO,– le tourniquet s'applique sur chaque file,– la durée du quantum est de 100 ms. Cette durée a été déterminée empiriquement et correspond àla durée maximale ne dégradant pas les travaux interactifs.

2.1.4 Stratégie avec échéance : Deeadline

Elles sont essentiellement utilisées dans les systèmes temps réel pour le contrôle de processusindustriels. L'exemple ci-dessous, de correction d'un satellite, explique l'utilisation de ce type destratégie.– Les coordonnées du satellite sont envoyées au calculateur à intervalles de temps réguliers t.– Le traitement d'une position du satellite dure k seconde et doit être impérativement achevé avantl'arrivée des coordonnées de la position suivante.– Lors de l'arrivée des coordonnées d'une position X à l'instant t, on détermine l'échéance E commela date t + t + k.– Si le traitement des coordonnées de cette position X n'est pas commencé au temps E, le traitementn'est pas ordonnancé et ne sera pas effectué.

2.2 Allocation de l'unité centrale dans le système Unix BSD

Ce paragraphe présente la gestion des processus dans la version HP-UX du système Unix BSD 4.3

2.2.1 Les états d'un processusL'unité d'allocation du processeur centrale est le processus; les processus constituent l'unitéd'exécution gérée par l'ordonnanceur.Au cours de leur vie, les processus peuvent se trouver dans différents états ; Les processus setrouvant dans l'état Runnable sont regroupés dans les files d'attente gérées par l'ordonnanceur.

2.2.2 L'ordonnancement des processus2.2.2.1 Principe

L'unité d'allocation du temps unité centrale est le quantum et la stratégie utilisée est le tourniquetmulti-niveaux géré en FIFO.Le critère du choix pour l'ordonnancement est la priorité flottante attribuée à chaque processus. Lecalcul de cette priorité respecte la régle suivante :– La priorité augmente avant le service– la priorité diminue fortement après le service

2.2.2.2 Structuration de l'ordonnanceur

Deux familles de fonction noyau assurent la gestion des processus :— les fonctions explicitement appelées par les processus pour leur sychronisation et leurcommunication— les fonctions appelées par les activités liées au traitement des interruption horloge. Cet ensemblede fonction constitue l'ordonnanceur :

–schedcpu est arrivée toutes les secondes et recalcule la priorité flottante des processus selonla formule ??

– roundrobin est activée 10 fois par seconde et assure le temps partagé en allouant à chaque processus un quantum de 100 ms et en faisant circuler les processus dans les files

–hardclock est activée 100 fois par seconde et met à jour la variable p_cpu comptabilisant la consommation en temps unité centrale du processus

– setpri est activée toutes les 400 ms et recalcule la priorité flottante des processus selon la formule ??

–switch recherche le processus le plus prioritaire et opère le changement de conteste pour son activation.

2.2.2.3 Organisateur des files d'attente dans le système HP-UX

Les files d'attente du système HP-UX regroupent l'ensemble des processus prêts ou enattente. A chaque niveau de priorité flottante, depuis 0 jusqu'à 255, correspond une file d'attente.

Les processus en attente sont rangés dans les files correspondant à leur priorité de réveil.Cette priorité est supérieur à celle des processus utilisateurs prêts car au réveil le processus exécuteen général une fonction système prioritaire. Cette priorité d'attente est totalement différent de lapriorité des processus utilisateurs prêts gérés par l'ordonnanceur.

1. Priorité 0-127 : priorités des processus temps réel, ces priorités sont fixes, une file est associée àchaque priorité et les processus sur la file dont gérés en tourniquet sans temps partagé.2. Priorité 128-177 : priorités des processus en attente sur évènement dans l'état Asleep. La prioritéest fixe durant toute l'attente et dépend de la nature de l'attende :

–priorité 128-152 : priorités des processus insensibles aux signaux : ils ne seront réveillésque par l'arrivée de l'évènement attendu,

– priorité 153-177 : priorités des processus sensible aux signaux : ils sont réveillés parl'évènement attendu ou par un signal quelconque.3. Priorité 178-255 : priorités des processus utilisateurs s'exécutant en temps partagé. Cette prioritéest recalculée toutes les secondes à partir de la priorité de base (PUSER=178) et du temps cpuconsommé.L'ensemble de ces files constitue le run queue, file des processus prêts, scrutée par l'ordonnanceurpour le choix du processus à activer La préemption est effectuée au profit d'un processus plus prioritaire :— à la sortie du mode kernel, si un processus plus prioritaire a été réveillé,

— en fin de quantum, lors de la ré-actualisation des priorités flottantes.

Remarque : Lorsqu'un processus n'a pas consommé tout son quantum, par exemple par la suited'une mise en attende de fin d'entée/sortie, le temps restant est attribué au nouveau processus activé.Ainsi, ce processus ne reçoit pas un quantum entier pour son exécution.

2.2.3 Algorithme simplifié de l'ordonnanceur

Pour tous le processus appartenant à la runqueue :

1. choisir le processus résidant en mémoire centrale ayant la plus forte priorité,2. ôter le processus de la runqueue et effectuer un changement de contexte pour l'exécuter,3. si aucun processus n'est éligible, mise de la machine dans l'état idle.

2.2.4 Principe du calcul de priorité

– Pour calculer la priorité flottante des processus prêts, l'ordonnanceur prend en compte deuxparamètres :

— le temps CPU précédemment consommé par le processus et comptabilisé dans la variablep_cpu,

— le temps d'attente passé dans la runqueue.– La priorité des processus en attente est fonction :

— des caractéristiques de l'évènement ou de la ressource attendu,— des ressources bloquées par le processus en attente.

– La priorité de réactivation des processus après une attente est calculée en utilisant la durée del'attente comptabilisée dans la variable p_slptime.

2.3 Ordonnancement2.3.1 Priorité flottante dans Unix BSD2.3.1.1 Implantation de la run queue

L'ensemble des processus dans l'état Runnable constituent la file des processus prêts : la run queue.Dans le système Unix BSD, l'implantation du tourniquet multi-niveau est réalisée ainsi :

– les niveaux de priorité flottante sont regroupés par 4,– une liste chaînée des processus est associée à chaque groupe de priorité flottante,– la table des têtes et queues de liste des files est implantée sous forme d'un tableau appelé

qs. Une seconde table de booléens, appelée whichqs, est associée à la table qs pour indiquerl'occupation de chaque file.

2.3.2 Priorité flottante dans Unix System V

A la fin de chaque quantum Ti on recalcule la consommation CPU dans la variable CPU_usageselon la formule suivante :

CPU_usage(Ti-1) + nb(Ti)CPU_usage(Ti) = ______________________

2

Où nb(Ti) représente le nombre de ticks CPU accumulés pendant la durée Ti.Un tick est comptabilisé à un processus si l'interruption horloge arrive lorsque le processuss'exécute.

Le calcul de la nouvelle priorité se fait selon cette formaule :

CPU_usage(Ti) Priorité( Ti ) = P_USER + ———–———–- 2

2.3.2.1 Exemple

Soit le contexte suivant :– 3 processus A, B et C dans la même file de priorité 178,– un quantum dure 100 ticks d'horloge ,– le recalcul de la priorité se fait en fin de quantum,– les processus ne font pas d'appels noyau,– aucun autre procesus ne se trouve dans l'état Runnable.

Processus A Processus B Processus C

Quanta Priorité CPU_usage ticks Priorité CPU_usage ticks Priorité CPU_usage Ticks

T1 exécution178 0

(P_USER)

1.100

178(P_USER)

00..

178(P_USER)

00..

T2203 50

(= 0+100/2)

0..

exécution178 0

1.100

178 00..

T3190 25

(=50+0/2)

1..

203 500..

exécution178 0

1.100

T4 exécution184 12

(=25+0/2)

0.100

190 250..

203 500..

T5206 56

(=12+100/2)

0..

exécution184 12

1.100

190 250..

2.3.3 LinuxA mettre à jourLinux offre trois politiques d'ordonnancement. Deux d'entre elles sont des politiquesd'ordonnancement en temps réel ''soft'', c'est à dire qu'elles accordent aux processus une très hautepriorité par rapport aux autre processus mais ne garantissent pas une réponse dans un tempsspécifié. La troisième politique d'ordonnancement utilise un alogorithme de temps partagé basé surdes valeurs de priorité.Par défaut, un processus est associé à la politique de temps partagé. Seul root peut associer unprocessus à une des clesses d'ordonnancement en temps réel.En Linux, chaque processus se voit attribuer une politique d'ordonnancement. Dans tous les cas, leprocessus possède aussi une valeur de priorité variant de 1 à 40. Plus la valeur est élevée, plus lapriorité est faible. Par défaut, un processus utilisateur a une valeur de priorité de 20. il est possible,pour un processus, de modifier sa priorité, en utilisant l'appel système nice(valeur), où la valeur estun nombre compris entre -20 et 20. Si la valeur est positive, on diminue d'autant la priorité duprocessus. Inversement, si la valeur est négative, on augmente la priorité. A noter que seul root peutaugmenter la priorité d'un processus.

2.3.3.1 Temps réel

Une première politique d'ordonnancement, dénommée SCHED_FIFO, garantit au processus une

utilisation illimitée du processeur. Il ne sera interrompu que dans une des circonstances suivantes :– Le processus bloque sur un appel système ou se termine ;– Un autre processus de la classe SCHED_FIFO de priorité plus élevée est prêt. Dans ce cas leprocessus actuel est remplacé par celui-ci ;– Le processus libère lui-même le processeur, en exécutant l'appel système sched_yield().Rien n'est plus prioritaire qu'un processus de la classe SCHED_FIFO, à l'exception d'un autreprocessus de la même classe qui possède une valeur de priorité supérieur.

L'autre politique d'ordonnancement en temps réel, dénommée SCHED_RR, est, contrairement à lapremière, préemptive. Chaque processus de cette classe ne se voit attribuer un quantum (tempslimite d'exécution). Lorsque ce quantum sera écoulé, le contrôle sera donné à un autre processus demême priorité de la classe SCHED_RR, s'il y en a un, en appliquant l'algorithme du tourniquet. Anoter que le tourniquet ne se fait qu'avec des processus de même priorité. Un processus temps réelde plus haute priorité a toujours préséance. Ainsi si deux processus de la classe SCHED_RR avecpriorité 20 s'éxecutent, ils alterneront dans le processeur. Si entre temps apparaît un processus de lamême classe, mais de priorité 25, c'est ce dernier qui prend le contrôle du processeur et neredonnera que lorsqu'il se terminera. A moins, bien sûr, que n'apparaisse un autre processusSCHED_RR de priorité supérieure ou égale, ou encore un processus SCHED_FIFO.

Le quantum attribué à un processus de la classe SCHED_RR est variable et établi selon les mêmeprincipe que ceux appliqués aux processus à temps partagé, décrits à la section suivante.

2.3.3.2 Temps partagé

Nous avons vu, à la section précédente, les deux politiques d'ordonnancement en temps réel offertespar Linux. Il nous reste maintenant à voir la dernière politique d'ordonnancement, qui regroupe tousles processus de la classe OTHER. Les processus de cette classe se partagenet le processeur demanière inégale, selon leur priorité et leur usage du processeur.

Premièrement, comme nous l'avon déjà dit, chaque processus possède une valeur de priorité qui luiest attribuée au moment de la création. C'est ce que nous appellons la priorité statique.

Initialement, on attribue à chaque processus un quantum dont la valeur utilise une unité de tempsqui correspond normalement à 10ms. La valeur initiale du quantum est égale à la valeur de priorité.Ainsi un processeur de priorité 25 aura un quantum de 25 unité, ce qui correspond à 250ms. Cequantum est le temps alloué au processus. À chaque 10ms, on diminue de 1 la valeur du quantumdu processus en cours d'exécution dans le processeur.

Chaque fois que l'ordonnanceur est appelé, une note est attribuée à tous les processus. Cette notecomme nous le verrons à la section suivante, dépend à la fois de la priorité du processus et de lavaleur actuelle de son quantum. C'est cette note qui permettera de déterminer quel processusprendra le contrôle du processeur.Éventuellement, on peut arriver à une situation où tous les processus sont dans une des deuxsituation suivante :— Son quantum est 0. il a écoulé tout le temps qui lui était alloué.— Il est bloqué. Il n'a pas nécessairement épuisé son quantum.Dans ce cas, tous les quanta (y compris les quanta des processus en attente qui ont encore unevaleur non nulle) sont réajustés selon la formule suivante :

Quantum Quantum/2 + priorité⇐

Ceci a pour effet de favoriser les processus qui n'ont pas utilisé tout le temps qui leur est alloué. Eneffet, un processus qui n'a pas épuisé son quantum se retrouve avec un nouveau quantum plus élevéque l'ancien. On peut facilement vérifier que la valeur maximale du quantum est deux fois lapriorité.Comme nous le verrons dans la prochaine section, un processus qui voit son quantum augmenterpeut se retrouver avec une meilleur note lorsque vient le moment de choisir un processus à exécuter.

2.3.3.3 Algorithme d'ordonnancement

Lorsque l'ordonnanceur est appelé, Linux attribue une note à chaque processus, en utilisant laméthode suivante : Si le processus est de la classe SCHED_FIFO ou SCHED_RR Note = 1000 + priorité. Sinon Si Quantum > 0 Note = Quantum + PrioritéSinon Note = 0On remarquera qu'un processus membre d'une des deux classes de temps réel aura toujours prioritésur les autres. En effet, puisque le quantum ne peut dépasser le double de la priorité du processus, etque la valeur maximale de la priorité d'un processus est 40, on n'aura jamais une note supérieure à120 pour un processus de la classe OTHER, ce qui est nettement inférieur au minimum de 1000pour un processus en temps réel.On remarquera aussi qu'un processus qui a écoulé tout son quantum reste en attente tant qu'il y a desprocessus qui peuvent s'exécuter. Comme nous l'avons déjà dit, il ne se verra attribuer au nouveauquantum que lorsque tous les autre processus auront épuisé leur quantum ou seront bloqués.

2.3.3.4 Exemple

Supposons trois processus A, B et C, tous de la classe OTHER, et dont les priorités sont lessuivantes :

Processus A B C

Priorité 20 18 10

Supponsons qu'ils arrivent tous dans le système au même moment et qu'ils sont seuls. A et B sontdes processus qui s'interreompent pour faire des appels système bloquant, alors que C ne bloquejamais.Initialement, c'est évidemment le processus A qui a la meilleure note. C'est donc lui qui est exécuté,ayant droit à 200ms. Supposons maintenant qu'il s'interremopt après 160ms pour exécuter un appelsystème bloquant. Le système doit maintenant choisir entre B et C. B est élu et s'exécute pendant40ms (lui aussi bloque sur un appel système), À ce moment, le processus C prend le contrôle etutilise toutes les 100ms qui lui sont accordées.On se retrouve alors dans la situation suivante : A et B sont toujours bloqués, et C a un quantum nul.Le système réalisera donc un réajustement des quanta. Les processus se verront attribuer lesnouvelles valeurs suivantes (rappelons qu'il reste 40ms à A et 140ms à B) :

Processus A B C

Nouveau quantum 4/2 + 20 = 22 14/2 + 18 = 25 0/2 + 10 = 10

Comme A et B sont toujours bloqué, C s'exécute à nouveau. Supposons maintenant que A et Bredeviennent prêt durant ce temps. Après 100ms, C a épuisé son quantum. Il aura une note égale àzéro. Le sytème choisira alors entre A et B. Voici les notes qui sont attribuées aux processus :

Processus A B C

Nouveau quantum 22 + 20 = 42 25 + 18 = 43 0

C'est donc B qui sera choisi, malgé sa priorité statique plus basse. Il est favorisé parce qu'il a utiliséune proportion plus petite du temps qui lui avait été alloué.

2.3.4 Les structures de données décrivant les processus

Deux tables décrivent les processus : la table proc, décrite par la structure proc.h et la table userdécrite par la structure user.hLes structures proc et user d'un processus sont au même indice dans les deux tables.La table proc est une table dimensionnée à nproc entrées, elle possède une entrée par processus. Lastructure proc résident en mémoire et contient essentiellenment :– Le chaînage vers les autres entrées de la table proc pour matérialiser les files d'attente :

–- La file des processus de même priorité, –- La liste des processus partageant le même texte exécutable, — La liste des processus prêt (run queue).

– Les identificateur associés au processus,– Les variables associées à la gestion des priorité,– Les variables associées à la gestion des temps,– Les variables associées à la gestion des signaux,– Les liens vers d'autres structures du système.La table user possède une entrèe par processus présent en mémoire. Elle accompagne les processusdurant leurs va-et-vients entre la mémoire centrale et la mémoire secondaire. La structure usercontient essentiellent :– Les pointeurs vers les zones de sauvegarde et l'entrée proc du processus,– Le nom du processus,– Les identifications associés au processus,– Les informations liées à la gestion mémoire,– Les informations liées à la gestion des signaux– Les descripteurs de fichiers ouverts,– Les noms des chemins (pathname) du répertoire de travail (working directory) et du répertoirepersonnel (home directory)

2.3.4.1 Filiation des processus

Le mécanisme de création des processus implique l'héritage des attributs. La connaissance de l'arbrede filiation des processus est fondamentale pour le système.La première structure proc de la table proc correspond au processus ancêtre de tous les autres : lesprocessus Init. Chaque structure proc possède les pointeurs nécessaire à la description de lafiliation :— Le pointeur sur le fils le plus récement créé,— Le pointeur père,— Le pointeur sur le cader ( frère plus jeune),— Le pointeur sur l'aîné (frère plus vieux, mais pas le plus vieux).

2.3.4.2 La Run Queue

L'ensemeble des processus dans l'état Runnable constitue la file des processus prêts : la run queue.Dans le système Unix BSD, l'implantation du touniquet multi-niveau est réalisée ainsi :— Les niveaux de priorité flottante sont regroupés par 4,— Une liste chaînée des processus est associée à chaque groupe de priorité flottante,— La table des têtes et des queues de listes des files est implantée sous forme d'un tableau –- La table des têtes et queues de liste des files est implantée sous forme d'un tableau appelé qs. Uneseconde table de booléens, appelée whichqs, est associée à la table qs pour indiquer l'occupation dechaque file.

CHAPITRE 3

Allocation de la mémoire centrale3.1 Les mémoires

L'espace d'adressage d'un processeur est l'ensemble des objets auxquels les instructions desprogrammes qui s'y exécutent peuvent accéder. La taille de l'espace est fonction de la longueur duchamps adresse de l'instruction.Deux stratégies différentes peuvent être mise en place pour gérer l'espace d'adressage d'unprocesseur :– Utiliser un espace d'adressage réel correspondant à la mémoire physique implantée. La mémoireest alors organisée linéairement et est gérée comme un vecteur d'emplacement. Dans ce cas , l'unitécentrale manipule des adresses physique qu'elle envoie directement à la mémoire.– Utiliser un espace d'accès différents, par exemple la mémoire centrale et le disque. Dans ce cas,l'unité centrale manipule des adresses virtuelles qu'elle envoie à une unité de traduction d'adresseappelée MMU ( Memory Management Unit) qui traduit les adresse virtuelles en adresses réellesqu'elle émet vers la mémoire physique.

3.1.1 Mémoire classique versus mémoire associative3.1.1.1 Mémoire classique

Une mémoire est la réalisation matérielle d'une fonction qui associe une valeur à une adresse. Parexemple, une mémoire de type 2D peut être vue comme un vecteur. Les composantes du vecteursont appelées mots. L'indice de chaque mot constitue son adresse.

3.1.1.2 Mémoire associative

Une mémoire associative ( Content Adressable Memory) implante la fonction inverse : elle associeun prédit d'existance binaire à une valeur. Le prédicat d'existence sera affecté ainsi :

— Vrai, si la valeur existe en mémoire ;— Faux, si elle n'existe pas.

Une valeur filtrée par un masque est recherchée dans l'ensemble des mots de la mémoireassociative.A chaque mot de cette mémoire est associé le prédicat binaire d'existance. Si un mot contient lavaleur filtrée, alors son prédicat est 1.

Remaque : Ce mécanisme élémentaire peut être complété par un mécanisme d'adressage : le vecteurcomposé par l'ensemble des prédicats est utilisé comme une adresse dans une mémoire classique.

3.1.1.3 Exemple d'utilisation des mémoire associative

On désire tabuler une fonction discontinue y = f(x), c'est à dire une fonction présentant de nombreux trousdans le domaine de définition de la variable x.– implantation avec une mémoire classiqueLa valeur de la variable x est prise comme adresse dans une mémoire bornée par les extrema du domaine dedéfinition. A un mot d'indice c correspond la valeur f(x). Cette implantation est peut efficace puiqu'elle engendre un gâchis de mémoire important par suite del'existence de trous dans le domaine de définition de la variable x.– Implantation avec une mémoire associative, complétée par une mémoire classiqueLa mémoire associative ne contient que les valeurs pour lesquelles la variable x est définie, la mémoireclassique contient les valeurs correspondantes de la fonction f(x). Le lien entre les mémoires deux mémoiresest effectué par adressage utilisant le prédicat d'existence : la rang du mot dans la mémoire associative ayantson prédicat positionné est utilisé comme adresse pour la mémoire classqiue.

3.1.1.4 Implantation des mémoires associatives

La technologie utilisée pour la réalisation des mémoires associatives est fonction de leur taille :– Pour des mémoires de petite taille réalisant la recherche sur un champs réduit, la réalisation est purementélectronique avec un comparateur par mot mémoire ;– Pour des mémoires de taille intermédiaire, la recherche est effectuée par des algorithme micro-programmés– Pour de grandes mémoires, les technique de rangement calculé utilisant les fonctions de hashage sontutilisées.

3.2 La mémoire physique 3.2.1 Organisation de la mémoire physique3.2.2 Manipulations sur les adresses

L'objectif est de privilégier soit l'extensibilite par l'ajout de modules mémoire à une mémoire existante, soitles performances par la parallélisation des accès à la mémoire.

3.2.2.1 Découpage en modules

Un module est un bloc de mémoire contenant un nombre fixe d'emplacements situés à des adressescontiguës. Les module sont désignés par leur numéro ou rang et sont placés dans l'espace d'adressage defaçon à assurer la continuité des adresses.Le champs adresse pour une mémoire organisée en module est découpée en deux parties :– Les poids fort de l'adresse désignant le numéro du module ;– Les poids faibles de l'adresse permettent à la sélection d'un mot dans le module.

Avantage : L'extension est aisée puisque la mémoire est découpée en module indépendants dont les adressesdans l'espace d'adressage sont contiguës.

Inconvénient : Aucun parallélisme n'est possible pour accélérer les accées en utilisant la propriété de localitécar le voisinage proche d'une adresse se trouve dans le même module.

3.2.2.2 Découpage en bancs entrelacés

Un banc est un bloc de mémoire contenant un nombre fixe d'emplacement situé à des adresses contiguësmodulo le nombre de bancs.Le champ adresse pour une mémoire organisée en bancs entrelacés(Interleaved banks) est découpé en deuxparties :— Les poids fort de l'adresse permettent la sélection d'un mot dans le banc ;— Les poids faibles de l'adresse désignent le numéro du banc.

Avantage : Ce découpage permet d'exploiter la propriété de localité pour paralléliser les accès : deux adressesconsécutives dans l'espace d'adressage du processeur sont situées dans deux banc différents qui peuvent êtreaccédés simultanément.

Inconvénient : La mémoire n'est pas extensible

3.2.2.3 Compromis

Le Compromis fréquemment mis en œuvre consiste à découper la mémoire en module, chaque modulecontenant des bancs entrelacés.L'adressage s'effectue d'abord par sélection du module, puis du banc et enfin du mot.

3.2.3 Manipulation sur les longueurs des mots

Définitions : Un mot physique est le contenu de l'emplacement mémoire désigné par une adresse physique.Un mot logique est la quantité d'information manipulée par les instructions.

Remarque : La taille du mot physique ne correspond pas forcément à celle du mot logique.

Objectif : Le but de cette distinction est de privilégier, soit les performances, soit les accès à la mémoire.

3.2.3.1 Parallélisation des accès

Dans ce type d'ogranisation, un mot physique contient plusieurs mots logiques. Utilisant la propriété delocalité, cette organisation permet d'anticiper les accès mais elle augmente fortement le coût de la mémoire etde sa logique d'accès.Le principe de l'adressage avec un découpage de l'adresse en deux champs :— Les poids fort contiennent l'adresse physique ;— Les poids faibles contiennent un pointeur sur le mot logique manipulé.

3.2.3.2 Sérialisation des accès

Dans le but de diminuer le coût de réalisation de la mémoire, un mot mémoire physique ne contient qu'unefraction d'un mot logique.Plusieur accès en série à la mémoire centrale, pour lire plusieurs mots physique contigus, permettent derecomposer un mot logique. Cette organisation permet d'obtenir des mémoires et des processus économiquesau prix d'un ralentissement des accès.Le processeur I8088 d'Intel accède à la mémoire selon ce principe.Le principe de l'adressage avec un découpage de l'adresse en deux champs :— Les poids forts contiennent l'adresse physique ;— Les poids faibles contiennent un compteur sur la fraction du mot logique manipulé.Dans l'exemple présenté, deux accès à la mémoire sont nécessaires pour reconstruire un mot logique.

3.2.4 Manipulation sur les accès

Définition : Une voie d'accès à la mémoire est constituée par le bus d'adresses, le bus de données et leslignes de contrôle des bus

Objectif : Privilégier les performance ou l'économie sur les voies d'accès.

3.2.4.1 Une seule voie d'accès

Une architecture n'utilisant qu'une seule voie d'accès pour les instructions et les données ne permet aucunparallélisme dans les accès. Cette solution est économique mais peu performante.

3.2.4.2 Plusieurs voies d'accès

La manipulation des voie d'accès peut se faire selon différents critères :— Une voie d'accès par type d'information manipulée par l'unité centrale. L'architecture de type Harvard,illustrée par la figure ?? affecte une voie d'accès pour les instructions et une voie d'accès pour les données.— Une voie d'accès par banc entrelacé. Ce choix est mis en œuvre dans les super-calculateurs.— Une voie d'accès par processeur comme l'unité centrale et les contrôleurs d'entrée/sortie. Ce type demémoire est appelé mémoire multi-port.— Sur des architectures spécialisées, comme certaines machines d'acquisition de données en temps réel, unevoie d'accès est mise en œuvre pour chaque mot de la mémoire.

3.2.5 Gestion de la mémoire physique

Après que le processeur ait placé l'adresse sur le bus d'adresse, le contrôleur de la mémoire se charge desélectionner le module ou le banc puis d'envoyer le déplacement de l'adresse sur le composant mémoiresélectionné. Le mot correspondant à cet emplacement est alors renvoyé vers l'unité centrale parl'intermédiaire du bus de données.

3.3 Organisation d'une mémoire hiérarchisée

3.3.1 Niveaux de mémoires

Une mémoire hiérarchisée est constituée par un ensemble de mémoire de taille et de temps d'accès différents.Cette hiérarchie est essentiellement fondé sur la théorie de la localité. En général, une hiérarchie de mémoirecomprend les niveaux suivants :— Le niveau le plus haut est en général composé des registres internes de l'unité centrale, ce niveau estexplicitement visible par les programmes ;— Le niveau immédiatement inférieur est en général appelé anté-mémoire ou cache. Ce niveau est caché auxprogrammes utilisateurs et n'est pas visible explicitement. Un cache est une petite mémoire très rapide parrapport à mémoire centrale contenant une projection d'une partie des informations de celle-ci. Ce point posele problème de son adressage qui sera en général associatif ;— Le niveau intermédiaire est constitué par la mémoire centrale appelée mémoire réelle. Ce niveau esttoujours visible et est explicitement adressé par les programmes ;— Le dernier niveau est constitué par la mémoire secondaire qui en général réside sur disque. Ce niveaun'est visible que du système d'exploitation qui assure sa gestion et son adressage.Chaque niveau de mémoire ne contient qu'une projection et d'une partie des information du niveau inférieur.

3.3.2 Quelques définitions

Quelques notations sur le sens des objets manipulés doivent être précisées :– Zone : ensemble d'un nombre variable d'emplacements contigus. Une zone est donc définie par sonadressse de début et sa longueur ;

– Bloc : ensemble d'un nombre fixe d'emplacements contigus. Un bloc est définit par son adressed'implantation en mémoire ;

– Segment : partie de l'espace virtuel de longueur variable correspondant à un découpage logique. Ainsi unsegment contient une procédure, un fichier, etc ;

– Page : partie de l'espace virtuel de longueur fixe correspondant à un découpage physique ne tenant pascompte du contenu logique ;

– Case : partie de la mémoire réelle de longueur fixe destinée à contenir une page de l'espace virtuel. Unecase est donc une partie physique de la mémoire réelle, inamovible et définie par son adresse. La case est lecontenant, la page est le contenu.

3.3.3 Taille de l'information gérée à chaque niveau

Comme la taille des mémoires de la hiérarchie décroît en s'approchant de l'unité centrale, la taille desinformations gérées par les différents niveux décroit également. Ce phénomène s'explique aisément par lescoûts relatifs du stockage et par les vitesses relatives des accès et des transferts.

– La mémoire secondaire, en générale située sur disque, contient des pages entières, entre 512 octets et 8Kio, correspondant à la taille des blocs physiques du disque ;– La mémoire centrale est découpée en case de même taille que les pages ;– L'unité d'information gérée par le cache est le bloc contenant un ou plusieurs mots ;– Les registres contiennent des mots de 1, 2, 4 ou 8 octets.La contiguïté des informations n'est respectée que dans le sens descendant, c'est-à-dire du cache vers

le dique :– Les blocs sont dispersés dans le cache mais les mots restent contigus dans le bloc ;– Les pages sont dispersées dans les cases mais les blocs restent contigus dans une page ; – Les pages d'un même espace virtuel sont contiguës sur le disque.

3.4 La mémoire virtuelle

3.4.1 Principe

La taille d'un programme, des données et de la pile ne peut pas dépasser l'espace disponible en mémoirecentrale.Pour éliminer cette contrainte, le système d'exploitation ne conserve en mémoire que les parties duprogramme qui sont en cours d'utilisation et stocke le reste sur disque. Les va-et-vient des fragements del'espace d'adressage sont effectués dynamiquement lors de l'exécution du processus. La mémoire virtuelle est particulièrement bien adaptée aux système multiprogrammé. En effet, lorsqu'unprocessus attend le chargement de l'une de ses parties, l'unité centrale peut être allouée à un autre processus.

3.4.2 Espace virtuel privé ou global

L'espace virtuel peut être implanté selon deux philosophies différentes :– Chaque processus peut possèder son propre espace virtuel privé. Le principal avantage de ce chois est queles processus sont de facto protégés les uns des autres, chaque processus n'ayant une visibilité que sur sonespace privé.– Tous les processus partagent un espace virtuel global. L'inconvénient de ce choix est qu'il faut prévoirexplicitement un mécanisme de protection entre les processus.En général, le mécanisme implanté correspond à un compromis entre ces deux philosophies. En effet, lasolution des espaces virtuels privés pénalise le partage d'objets communs, comme le noyau du système, et lavérification des protections alourdit le mécanisme de traduction dans les architectures à espace virtuel global.Le choix du type d'espace virtuel global ou privé a une conséquence importante sur les performances del'architecture :— Une architecture à espace virtuel privé nécessite que chaque processus possède sa propre fonction detraduction, donc ses propres tables. Un changement de contexte entre deux processus sera donc très coûteuxpuisqu'il faudra échanger les tables de la fonction de traduction et mettre à jour le mécanisme de traductionaccéléré ;— Une architecture à espace virtuel global évite ce problème, la fonction de traduction est commune à tousles processus.

3.4.3 Segmentation et pagination

Le transfert des parties d'un programme entre le disque et la mémoire centrale peut être effectué selon deuxstratégies différentes :— Le système d'exploitation peut mettre en œuvre une gestion par segement et transférer des zones delongueur variable correspondant à un découpage logique du programme

- Segement de code,- Segement des données initialisées,- Segement des données non initialisées,- Segement de pileCe mécanisme est appelé segmentation : il consiste à charger les segments dans des zones de la

mémoire centrale. Comme les segments sont de longueur variable, ce type de gestion rend les entrées/sortiestrès pénalisantes.— Le système d'exploitation peut mettre en oeuve une gestion par page et manipuler des pages de longueurfixe. Les entrées/sorties sont beaucoup plus efficaces que le cas de la gestion par segments mais la stucturelogique des programmes est ignorée.Ce mécanisme est appelé pagination : la pagination consiste à transférer des pages depuis la mémoiresecondaire dans des cases de la mémoire centrale.

Remarques :– Les pages et les cases ont la même taille,– Les transferts entre le disque et la mémoire centrale se font toujours par page entière,– Il est également possible de mélanger les deux stratégies en gérant des segments découpés en page (segmentation paginée).

3.4.4 Allocation de la mémoire centrale

Pour s'exécuter, les instructions d'un programme doivent être chargées en mémoire centrale.Les instructions exécutées par un processus désignent les objets qu'elles manipulent dans un espace appelé''espace d'adressage''. Les adresses émises par le processeur peuvent être de deux types :

— Adresse réelles : ces adresses sont envoyées directement à la mémoire et désignent desemplacement physiques de celle-ci ;

— Adresses virtuelles : ces adresses sont envoyées à une unité de traduction, la MMU (MemoryManagement Unit) qui les traduit en adresses réelles.Lorsque les instructions contiennent des adresses virtuelles, l'espace d'adressage est appelé espace virtuel.Lorsque le mécanisme de traduction est propre à chaque processus, l'espace virtuel est appelé espace virtuelprivé. Réciproquement, lorsque ce mécanisme est commun à l'ensemble des processus, l'espace virtuel estappelé espace virtuel global.Lors de la traduction d'un programme par le compilateur celui-ci range les objets dans un espace logique.L'éditeur de liens mets à jour les adresses logiques pour les transformer en adresses de l'espace d'adressageréel ou virtuel.Définition concernant les organisations de la mémoire :— La mémoire uniforme : la mémoire centrale, seule mémoire accessible, est organisée linéairement et estgérée comme un vecteur d'emplacement contigus. Dans ce type de mémoire l'espace d'adressage est au plus àl'espace réel ;— La mémoire hiérarchisée : la mémoire est constituée d'un ensemble structuré de mémoires de tailles et detemps d'accès différents, de telle sorte que les références se fassent toujours à la mémoire la plus rapide. Lecas le plus simple de mémoire hiérarchisée est constitué de deux niveaux :

- La mémoire centrale, - La mémoire secondaire situé généralement sur disque.

A un instant donné, seuls des fragments de l'espace virtuel d'un processus sont présents en mémoire centrale.Le fonctionnement s'appuie sur le principe de la localité : on suppose que les fragments transférés dans lamémoire centrale sont utilisés par l'unité centrale pendant une durée supérieure au temps de leur transfert.Dans ce type de mémoire, l'espace virtuel a une taille très supérieure à celle de m'espace réel.Définitions concernant l'allocation et la gestion de la mémoire :— Zone : c'est un ensemble d'un nombre variable d'emplacement contigus,— Bloc : c'est un ensemble d'un nombre fixe d'emplacement contigus,— Segment : c'est une partie de longueur variable de l'espace virtuel correspondant à un découpage logique.Ainsi, un segment contient une procédure, un fichier, …— Page : c'est une partie de longueur fixe de l'espace virtuel correspondant à un découpage physique,— Case : c'est une partie de longueur fixe de la mémoire réelle destinée à contenir une page de l'espacevirtuel d'un processus.

3.4.5 Liaison espace d'adressage – espace réel

A l'exécution d'un programme, les objets manipulés par les instructions doivent se trouver en mémoire réelleet y être accessible par les modes d'adressage. Il est nécessaire d'établir la liaison entre l'espace d'adressaged'un processus et l'espace de la mémoire réelle.

Rappel :— Un module exécutable est translatables s'il peut être chargé à n'importe quelle adresse de la mémoireréelle. Le chargeur assure la translation à l'aide du dictionnaire de translation ;— Un module exécutable est relogeable si une fois son exécution démarrée il peut encore être déplacé enmémoire.

3.4.5.1 Liaison statique

La chaine de production de programmes, compilateur et éditeur de liens, produit un code utilisant desadresses réelles. La liaison est au courant sur les micro-ordinateurs à système mono-tâche.Le module exécutable généré est non translatable et non relogeable.

3.4.5.2 Liaison effectuée au chargement en mémoire

La chaîne de production de programme produit un code translatable. Le chargeur effectue le translation del'implantation en mémoire réelle.Le module doit être translatable, la translation peut être statique.

3.4.5.3 Liaison effectuée à l'exécution de chaque instruction

On effectue la correspondance espace d'adressage virtuel – espace réel à l'exécution de chaque instruction.Le lien adresse virtuelle – adresse réelle contient :— Une adresse si l'objet désigné est en mémoire à cet instant,— Nil si ce n'est pas le casCe mécanisme est très simple souple mais coûteux, l'execution des instructions est ralentie par la traductiondes adresses.Conséquences sur le module exécutable :– Le module est translatable : le chargeur charge le module dans une region de l'espace virtuel, à aucunmoment le programme se manipulera des adresses réelles ;– Le module est relogeable grâce au mécanismes de traduction dynamique des adresses.

3.4.6 Les mécanismes d'adressage

Dans ce paragraphe nous décrivons les différents mécanismes matériels qui réalisent la liaison entre l'espaced'adresse et l'espace réel.

3.4.6.1 Cas de la mémoire uniforme

les registres de base Lors de l'exécution de chaque instruction, ce mécanismes ajoute à chaque adresse lecontenu d'un registre spécial, en général inaccessible au programmeur. Cette addition provoque la translationcomplète de l'espace d'adressage pour le faire coïncider avec la zone de la mémoire réelle attribuée auprocessus.

La mémoire topographique : memory mapping Le principe est analogue à celui des registres de basemais à la place d'une addition on effectue une substitution des poids forts de l'adresse avec le contenu d'unregistre pris dans une table.

3.4.6.2 Cas de la mémoire hiérarchisée

Deux types de mécanismes d'adressage peuvent être utilisés dans une mémoire hiérarchisée : le découpageen segments ou le découpage en page. Chacun des ces découpages est un compromis entre :— Les performances pour les transferts entre les niveaux de mémoires,— La protection des informations,— La facilité de gestion.Les transferts de page sont plus simples et plus performants que les transfert de segments mais la protectiondes segments est plus souple et plus facile à gérer.

La segmentation Une adresse virtuelle est composée de deux champs :— Le numéro du segment : poids fort de l'adresse,— Le déplacement dans le segment : poids faible de l'adresse.Le numéro de segment est utilisé comme indice dans la Table Des Segments (TDS), dont chaque entrée contient un descripteur de segment. En général, un descripeur est constitué des champs suivants :– Un indicateur de validité pour l'entrée – L'adresse de base du segment en mémoire réelle,– La longeur du segment,– Des informations pour la protection du segment.L'algorithme de traduction d'une adresse segmentée est schématiquement le suivant :

1. Récupération du numéro de segment et accès à la table des segments,2. Si (indicateur_de_vilidité = faux) alors Défaut_de_segments,3. Si (longueur_du_segment ¡ déplacement_de_l'instruction) alors Erreur_d'adressage,4. Si ( informations_de_protection != droit_du_processus) alors Violation_Protection_Mémoire,5. Calcul de l'adresse réelle en additionnant l'adresse de base et déplacement

La pagination Une adresse virtuelle est composée de deux champs :— Le numéro de page : poids fort de l'adresse,— Le déplacement dans la page poids faible de l'adresse.Le numéro de page est utilisé comme indice dans la Tables Des Pages (TDP), dont chaque entrée

contient un descripteur de page. En général, un descripteur est constitué des champs suivants— Un indecteur de validité pour l'entrée — Le numéro de la case associée à la page,— Des informations diverses : protection de la page, information de service pour les algorithmes de

gestios des transferts de page…L'algorithme de traduction d'une adresse paginée est schématiquement le suivant :1. Récupération du numéro de page et accès à la table des pages,2. Si (indicateur_de_validité = faux) alors Défaut_de_page,3. Si (information_de_protection!= droit_du_processus) alors Violation_Protection_Mémoire,4. Mise à jour des information de service5. Calcul de l'adresse réelle en substituant le numéro de page par le numéro de case.L'accès systématique à la Table des Page rend cette traduction lourde et coûteuse en temps. Des

mécanismes d'accélération ont été proposés, le plus récent est la TLB( Translation Lookaside Buffer ). LaTLB est une table dont chaque entrée possède les champs suivants :

– Un indicateur de validité de l'entrée,– Un préfixe de discrimination des synonymes (Tag),– Un numéro de case,– Des information de service.L'indice d'une entrée est calculée à partir du numéro de page à l'aide d'une fonction de hashage. A

l'issue de ce calcul, il faut vérifier si l'entrée sélectionnée correspond à l'adresse virtuelle qu'on souhaitetraduire. A cet effet, le préfixe de descrimination des synonymes est comparé avec une partie de l'adressevirtuelle de départ. En cas de discordance, il y a émission du signal Défaut_TLB traité par le système.

La TLB n'étant qu'un mécanisme d'accélération, un Défaut_TLB ne signifie pas que la page n'est paschargé en mémoire. Le sytème devra alors parcourir la Table des Pages pour effectuer la traduction.

Des problèmes liés à la taille et à l'accès des tables apparaissent lors de la mise en œuvre del'adressage dans une mémoire paginée :

- La taille de la Table des Pages est directement liée à la taille de l'espace virtuel. Sur les processeursactuels, la taille de l'espace virtuel est de l'ordre de plusieur Gio, ce qui implique une Table des Pages deplusieurs millions d'entrées, ce qui est beaucoup.

- L'accès aux tables : les tables étant très grandes, dans certains systèmes elles ne sont pas résidentesen mémoire centrale ce qui allonge leur temps d'accès.

Une technique d'accélération consiste à ne conserver dans une petite table que les derniers couples(numéro_page, numéro_case) accédés par un processus. Cette technique met en œuvre le principe de lalocalité. L'utilisateur d'une mémoire associative, ou d'une TLB, s'avère très efficace.

La pagination à deux niveaux a été introduite pour remédier aux inconvénients de la paginationsimple, elle a pour objectifs :

— La réduction de la taille de la table de pages,— Le partage des morceaux de l'espace virtuel.

Définition : Une hyperpage est un ensemble de pages dont la liaison avec la mémoire réelle est décrite par lamême Table des pages. La table des Hyperpages contient les pointeurs sur les Tables des pages.

3.4.7 Les stratégies d'allocation de la mémoire

Dans ce paragraphe nous présentons les différentes stratégies d'allocation de la mémoire centrale. Après unebrève présentation en mémoire uniforme, nous détaillons l'allocation dans une mémoire hiérarchisée paginée.

Le contexte général est le suivant:— Plusieurs processus se partagent la mémoire,— Un processus qui s'exécute effectue des demandes et des libérations de mémoire.Plusieurs problèmes apparaissent alors :— Si le nombre de processus présents en mémoire à un instant donné augmente, la place disponible pourchacun d'eux diminue et les processus inactifs occupent inutilement de l'espace mémoire ;–- Le phénomène de l'interblocage ;–- Le phénomène de fragmentation : il s'agit du morcellement de la mémoire lié aux différences entre lestailles demandées et les tailles restituées par les processus. La mémoire n'est pas saturée mais les fragmentsdisponibles sont trop petits pour être utilisés ;–- Le phénomène de famine : un ou plusieur processus s'approprient toute les mémoire et empêchentl'exécution des autre processus.

3.4.7.1 Allocationn en mémoire uniforme

Dans ce paragraphe, nous ne présenterons que l'allocation statique : on alloue à un processus, lorse de sonchargement, toute la mémoire dont il a besoin et on lui impose de rester dans ses limites :— Le problème de l'interblocage est résolu par l'élimination de la concurrence,— La fragmentation est estreinte à la zone occupée par le processus,— La famine est supprimée grâce au limites imposées.La mise en œuvre de cette solution impose :-– Le découpage de la mémoire en partitions, zone de taille limitée :

- Soit statiquement à la génération du système,- Soit dynamiquement lors de l'allocation de la mémoire à un processus.

— La connaissance de la taille mémoire nécessaire à un processus pour s'exécuter.

3.4.7.2 Allocation en mémoire hiérarchisée

En mémoire hiérarchisée, on va projeter l'espace virtuel en mémoire réelle par fragment, en utilisant lemécanisme d'entrées/sorties.Les problèmes classiques de gestion de la mémoire sont résolus :— La fragmentation : elle reste interne à une page et peut donc vue comme un problème mineur ;— L'interblocage : il est inexistant car il n'y a pas concurrence entre les processus pour la mémoire réelle ;— La femine : elle est inexistante.Deux stratégies peuvent être mises en œuvre :

– Le swapping global,– Le swapping à la demande.

Le swapping global On dispose sur disque d'un fichier contenant l'image complète du processus. Lesopérations possibles sont :— swap out (roll out) : vider la zone mémoire du processus dans le fichier,— swap in (roll in) : transférer le fichier en mémoire.Ce mécanisme pose des problemes :– Les performances : le transfer de gros programmes provoque la saturation des canaux d'entrées/sorties,– Le choix des processus à swapper,– La gestion des tampons d'entrées/sorties sur fichier,– La nécessité de la relogeabilité du code exécutable.Ces problèmes limitent l'utilisation de cette stratégie à des cas très particuliers.

Le swapping à la demande On ne tranfert à la demande, sur échec de la traduction des adresses virtuelles,que des fragments de la mémoire d'un processus. Lorsqu'une référence à un emplcement non chargé enmémoire réelle est émise, on provoque le chargement de la zone ou du bloc englobant cette référence. Cettestatégie nécessite un mécanisme permettant la ré-implantation dynamique de zones.

La segmentation à la demande Elle nécessite le transfert de segments de longeurs variables en mémoire, cequi pose des problèmes analogues au swapping global : les segments sont peu adaptés aux entrées/sorties

La pagination à la demande Rappels : une page représente le contenu, une case représente le contenant.Pour des raisons de performances, la pagination est la stratégie généralement mise en œuvre dans lessytèmes.L'espace virtuel est découpé en pages et l'espace réel est découpé en cases, A chaque case est associée la pagequi s'y trouve chargée à un instant donné.La taille des pages est choisie de façon à réaliser un compromis entre l'optimisation des entrées/sorties, ellessont plus efficaces sur de grandes pages, et la minimisation de la fragmentation, qui est plus faible sur despetites pages. En général, la taille des pages varie entre 512 octetc et 2Kio.

Les stratégies de chargement

— Pre-fetch : anticipation du chargement des pages. Cette stratégie est peu utilisée dans les systèmesd'exploitation. Elle est en générale mise en œuvre dans les sytèmes de gestion de base de données à mémoire paginée. Néanmoins, dans le système Unix BSD, le regroupement des pages en clusters s'inspire de cette stratégie.

— Demand paging : chargemnt des pages à la demande, sur Defaut_de_page. Le défaut de page est un évenement émis lors de l'échec de la traduction des adresses virtuelles. Il permet d'activer le processus système chargé de la pagination.

Le remplacement des pages Lors de la traduction d'une adresse pour laquelle le lien espace virtuel – espaceréel n'existe pas, le système est appelé pour établir ce lien et charger par entrée/sortie la page de mémoirevirtuelle concerné. En général, l'établissement de cette liaison nécessite le remplacement d'une page déjàchargé en mémoire. Ceci pose de nouveaux problèmes :

— Trouver une case libre,— S'il n'existe pas de case libre, comment choisir la case à vider ?

Les solutions suivantes sont possibles :— La liste des cases libres est implantée dans la Table des Cases,— Si cette liste est vide il faut vider une case. Le choix de celle-ci est fait en évitant si possible des

recopies inutiles en mémoire secondaire.Afin de mettre en œuvre un algorithme performant pour implanter ces solutions proposées, les

structures de données de la Table des Pages et de la Table des Cases sont complétées à l'aide d'information deservice :

- Bit de référence à la case,- Bit de modification de la case,Il existe toute une famille d'algorithme abondamment décrits dans la littérature qui à l'aide

d'heuristique effectuent le choix pour le remplacement des pages en mémoire : FIFO, RANDOM, LRU (LestRecently Used), LFU (Least Frequently Used), … LRU est l'heuristique qui repecte le mieux la propriété delocalité, elle est mise en œuvre dans le système Unix BSD par le Global Clock Algorithm.

Le Global Clock Algorithm Les performances d'un système paginé à la demande sont liées à l'efficacité del'algorithme traitant l'échec de la traduction d'une adresse virtuelle en adresse réelle.Voici les principales étapes de l'algorithme de traitement du défaut de page dans l'architecture HP 9000/800.Traduction de l'adresse virtuelle par le mécanisme de la TLB : Si échec alors utilisation du mécanisme PIDR si échec alors Défaut_de_page recherche d'une case dans laliste des cases libres si echec alors choix d'une case à libérer recopie éventuelle de son contenu sur disque( normalement cela ne doit pas arriver) fsi lecture de la page en mémoire secondaire mise à jour du PIDR, dela pfdat, du VFD et de la TLB sinon la page est en mémoire mise à jour de la TLB fsi ré-exécution del'instruction fsi.La libération d'une case, surtout lorsqu'elle provoque une recopie sur disque, est une opération très coûteuseà éviter le plus souvent possible.Une solution possible consiste à conserver en permanance une réserve minimale de cases dans la liste descases libres. De plus, le choix des cases mises en réserve doit respecter une stratégies LRU.Il est possible de mettre en œuvre une telle stratégie en :––– Implantant l'algorithme de traitement du défaut de page sous la forme de deux activités coopérantes :

– Pagedeamon : processus système chargé de garnir en permanance la liste de cases libres, il exécute

la fonction pageout ;– Pagein : fonction liée au traitement du défaut de page et chargée des entrées/sorties de pages, Elle

est activée lors de l'apparition de l'exception Défaut_de_page et s'exécute dans le contexte du processusl'ayant provoqué.

––– Utilisant la stratégies LRU sur une fenêtre de temps.Le processus Pagedeamon, qui scrute la liste des régions actives (régions dont les pages sont chargées enmémoire), est activé cycliquement pour libérer les cases non référencées durant la fenêtre de temps.

A chaque activation, il examine n cases à l'aide de deux pointeurs Purger et Salvager :— Le bit de référence des cases pointées par Purger est remis à zéro,— Si le bit de référence des cases pointées par Salvager est nul, alors la case est mise dans la liste des caselibres.

Au bout d'un certain nombre d'activations, ce qui correspond à une fenêtre de temps, une case vue par Purgersera traitée par Salvager.La remise à zéro du bit de référence d'une case est destinée à vérifier si la case a été référencée dansl'intervalle de temps séparant le passage de Purger et de Salvager.Paramètres :– hand : écart entre les deux pointeurs P Purger et S Salvager,– n : nombre de case scrutées pendant une activation.Pageout : pour i de 1 à n faire :

Si référence.case(S) = 0) alors : la page n'a pas été référencée dans la fenêtre de temps mettre la case en tête de liste pour respecter la stratégie LRU mise à jour de la TLB du PDIR et du VFD fsi Référence.case(P) ¡-0 S¡-S+1 P¡-P+1 finpour.

Le nombre maximal de pages volées à une région est borné et dépend de la taille de la région.Dans ce contexte, un défaut de page signifie que la page n'appartient pas à la liste des pages des régionsactives :– Soit la page est sur disque,– Soit la page est encore en mémoire mais elle est chargée dans une case de la liste libre des cases.

La récupération reclaim consiste à extraire la case de la liste des cases libres et à remettre dans la liste despages actives.Pagein : Si la page est chargée dans une case de la liste libre (recherche accélérée par une fonction de hashdans la pfdat) alors récupération sinon lecture de la page sur le disque mise à jour du PDIR et du VFD fsi.Valeur des paramètres dans le système HP-UX : La période d'activation du processus pagedeamon est de0.25 seconde, mais son activation peut être forcée si le nombre de cases de la liste libre est inférieur à unparamètre du système : lostfree dont la valeur par défaut est 1024.4000 cases séparent les pointeurs P et S.200 cases sont scrutées à chaque activation.

3.4.7.3 L'écoulement dans un système paginé : trashing

Les performances d'un système à mémoire virtuelle paginée peuvent être affectées par un phénomène trèsparticulier : l'écroulement ou trashing.Quand le nombre de processus concurrents pour l'unité centrale augmente, leur espace en mémoire réellediminue, le nombre de défauts de pages augmente, et chaque processus va être de plus en plus souvent endéfaut de page. Le temps de réponse se dégrade très fortement. Ce phénomène n'est pas linéaire.

Solution par détection/guérison— Détection : surveillance du nombre de processus et swapping.Si le seuil d'écroulement est connu a priori, lorsque le nombre de processus tend vers ce seuil, on

interdit la création de nouveaux processus.

Si le seuil d'écroulement n'est pas connu, la détection de l'écroulement utilise plusieurs variables :— Le taux d'activité de l'unité centrale,— Le taux d'activité de l'unité de pagination,— Le nombre de cases libres en mémoire centrale.

— Guérison : swapping global pour libérer la mémoire.Lorsque le seuil d'écroulement est atteint, le swapping est déclanché pour libérer de la mémoire.Cette sollicitation de l'unité de swap ralentit encore plus la pagination. Dans le système Unix BSD, le

swapping est global et le ou les processus les plus gourmands en mémoire sont vidés.

Solution par prévention : stratégie du working set (espace de travail)— Le Working Set d'un processus est l'ensemble des pages nécessaires au processus pour avoir un taux dedéfauts de page raisonnable entre les instants t et t+ z. C'est une fenêtre qui se déplace très lentement dansl'espace virtuel du processus. Elle est définie par deux paramètres : le temps t et l'intervalle z.La valeur de z est fonction du comportement intrinsèque des processus et de la taille de la mémoire centrale.De plus, z est spécifique à chaque processus et évolue au cour du temps t.L'estimation de z utilise le passé récent comme une bonne approximation du futur proche, son evaluationutilise un calul dynamique ou heuristiques.

3.5 Les anté-mémoire, mémoires caches

Une mémoire cache est une petite mémoire très rapide par rapport à la mémoire centrale et qui ne contientqu'une projection d'une partie des information de la mémoire centrale. Son rôle est d'accélérer l'accès à lamémoire centrale par l'utilisation d'un mécanisme fondé sur la théorie de la localité.Le cache n'est pas visible par l'unité centrale, il est caché. L'unité centrale ne peut adresser que la mémoirecentrale.Dans une hiérarchie de mémoires composée d'un cache et de la mémoire centrale, le temps d'accès à lamémoire centrale est modifié par la présence du cache. Il est calculé en tenant compte de la probabilité deprésence des informations dans le cache. Le temps d'accès est alors appelé temps d'accès apparent, il estcalculé avec la formule suivante :

TAP = TPC × TAC + (1 – TPC ) × TAMC

où TAP est le temps d'accès apparent,TPC est le taux de présence en cache,TAC est le temps d'accès au cache,TAMC est le temps d'accès à la mémoire centrale,1–TPC est le taux d'échec ou la taux d'absence des informations dans le cache.

L'élément d'information rangé dans le cache est le bloc. Un bloc correspond à un mot physique du cache etpeut contenir plusieurs mots logiques du processeur.Les adresses utilisées par les instructions ne références pas le cache, son accès est transparent, il est effectué,soit par indexation, soit associativement sur un champs préfixe reprenant tout ou partie de l'adresse mémoire.Cette particularité dans le mécanisme d'adressage permet de distinguer plusieurs types de caches différents.

3.5.1 Typologie des caches en fonction de leur mode d'accès3.5.1.1 Les caches full-associative

Dans ce type de cache, il y a mémorisation des blocs d'information et leurs adresses complètes en mémoirecentrale. Les adresses mémorisées dans les cache sont appelées étiquettes ou préfixes (Tag). Un bloc dedonnée et son préfixe associé peuvent être rangés dans un emplacement quelconque du cache.Lorsque le processus demande l'accès à une donnée, le contrôleur du cache compare l'adresse del'information requise avec les prédixe stockés. S'il y a correspondance, il envoie le bloc de donnée associé auprocesseur.Le cache a une capacité de 512 emplacements, chacun contenant un préfixe de 22 bits et un bloc de donnéesde 32 bits. Le préfixe contient l'adresse complète du bloc de données en mémoire centrale. Ainsi le mot situéà l'adresse 0xFFFFFC est référencé dans le cache par le préfixe 0x3FFFFF.Les poids faibles de l'adresse permettent au processeur de séléctionner le mot désigné dans le bloc récupéré

grâce à un multiplexeur.

3.5.1.2 Les caches direct-mapped

Le mécanisme d'accès à ce type de cache repose sur le principe qu'un bloc d'information situé en mémoirecentrale à une adresse x ne peut être placé dans le cache qu'à un et un seul emplacement (slot) fonction de x.Cet emplacement est désigné par un index calculé à partir de l'adresse du bloc en mémoire centrale.La fonction de calcul de l'index réalise la projection des blocs situés en mémoire centrale dans lesemplacement du cache, cette projection est non injective. En effet, deux blocs situés à des adressesdifférentes en mémoire centrale peuvent être projetés dans le même emplacement du cache. Dans ce cas, cesblocs sont appelés des blocs synonymes.Le cache est adressé par un index codé sur 14 bits variant de 0X0000 à 0X3FFF. A la partie contenant lesblocs de données, un bloc contient un mot de 32 bits, on associe une partie préfixe. Chaque préfixe est codésur 8 bits et précise pour un bloc le complément, par rapport à l'index calculé, de son adresse en mémoirecentrale.L'accès est effectué selon le schéma suivant:1. L'index obtenu par extraction de la chaîne de bits A15 à A2 de l'adresse désigne un emplacement uniquedans le cache. Le préfixe de discrimination des blocs synonymes correspond aux 8 bits de poids fort del'adresse.2. Le contrôleur du cache compare le préfixe de l'emplacement trouvé avec la partie préfixe de l'adresse enmémoire centrale du bloc cherché. S'il y a égalité alors on renvoie le bloc de données du cache vers l'unitécentrale. En cas de non égalité, le contrôleur du cache génère un signal de défaut de cache (Cache miss) etl'unité centrale accède à la mémoire centrale pour y lire l'information. La mise à jour du cache est ensuiteeffactuée.

3.5.1.3 Les caches set-associative

Il est possible d'accélérer le fonctionnement des caches direct-mapped en parallélisant les accès au cache.A partir de l'adresse en mémoire centrale d'un bloc de données, un index unique est calculé et une recherchedans plusieurs sous-caches est effectuée en parallèle. Chaque sous-cache possède sa propre mémoire depréfixes et sa propre mémoire de données.Le préfixe de discrimmination des blocs synonymes correspond aux 9 bits de poids fort de l'adresse.A un index correspondent deux préfixes, le contôleur du cache effectue deux comparaisons en parllèle pourdéterminer dans quel sous-cache est situé le préfixe issu de l'adresse en mémoire centrale.Ce type de cache requiert deux comparaisons en parallèle, ce qui complique sa logique mais améliorenettement, par rapport à un cache direct-mapped, la probabilité de trouver l'information recherchée.Exemples de fonctionnement :Exemple 1 :– Le processeur recherche une information située à l'adresse 0x00FFFC en mémoire centrale.– Le contôleur du cache examine le contenu du premier sous-cache à l'index 0x1FFF pour vérifier si lepréfixe est égale à 0x001.– En parallèle, le contôleur a effectué une opération identique sur le second sous-cache et a trouvé lacorrespondance. Le bloc de données contenant 55556666 est transmis du second sous-cache vers leprocesseur.Exemple 2 :– Le processeur recherche une information situé à l'adresse 0x008004 en mémoire centrale.– L'index calculé est 0x001 et le préfixe est 0x001– Ce bloc de données est trouvé dans le prmier sous-cacheExemple 3 :– Le processeur recherche une information située à l'adresse 0x0010000 en mémoire centrale.– L'index calculé est 0x000 et le préfixe est 0x002.– Ce bloc de données n'est pas présent dans le cache. L'unité centrale le récupère depuis la mémoire centraleet une mise à jour du cache est effectuée. Le choix du sous-cache mis à jour sera fait par le contrôleur ducache selon une heuristique, par exemple LRU.

3.5.2 Gestion des caches3.5.2.1 Adresses utilisées pour le recherche

La recherche dans le cache peut être effectuée :– Soit à partir de l'adresse réelle : le contôleur du cache utilise l'adresse traduite par la MMU. Cette solution

est en générale retenue pour la simplicité de sa mise en œuvre.Le fonctionnement est séquentiel, l'adresse virtuelle est traduite puis une recherche dans le cache à l'aide de l'adresse réelle est effectuée.

– Soit à partir de l'adresse virtuelle. Cette seconde méthode est plus complexe à mettre en œuvre mais elle améliore les performances des accès. La recherche dans le cache et la traduction des adresse virtuelles se font en parallèle.

Cette technique nécessite une vérification supplémentaire. En effet, le cache est une projection de la mémoireréelle et non de l'espace virtuel. Il faut donc vérifier la correspondance entre l'objet désigné en mémoireréelle et l'objet accédé dans le cache. La vérification est effectuée en comparant le préfixe du cache avec unpréfixe calculé à partir de l'adresse traduite.

3.5.2.2 Stratégie de remplacement

Les stratégies de remplacement applicables à un cache dont identiques à celle applicables aux tables despages et tables de segments :– RANDOM : choix aléatoire de l'information à vider du cache.– FIFO : l'information entrée la première dans le cache est vidée.– LRU : L'information qui a été inutilisée durant la plus longue période est vidée du cache.Remarque : La stratégies LRU est très souvent appliquée car elle est plus proche de la stratégie optimale.

3.5.2.3 Mise à jour de la mémoire centrale

Lorsque le processeur effectue la modification d'une donnée du cache, plusieurs techniques peuvent êtreappliquées pour la mise à jour de l'objet correspondant en mémoire centrale :— Ecriture simultanée : write throughChaque fois que le processeur modifie une donnée du cache, il y a automatiquement écriture de lamodification dans la mémoire centrale. Le temps perdu par le processeur pour une écriture dans le cacheéquivaut alors à celui perdu pour un défaut de cache pour une lecture. Cependant, la cohérence des donnéesest forte.

— Ecriture postée : posted writeCette technique constitue une amélioration de la méthode précédente. L'écriture en mémoire centrales'effectue de manière asynchrone en utilisant un tampon d'écriture (buffer) contenant l'adresse et la valeur dumot à écrire. La logique d'écriture du tampon se charge de la mise à jour de la mémoire centrale pendant lapoursuite de l'exécution du flot d'instruction par l'unité centrale et que le tampon d'ecriture est plein, l'unitécentrale va attendre son vidage.— Ecriture retardée : write back ou copy backDans ce mécanisme, à chaque bloc du cache est associé un bit indiquant si la donnée a été modifiée ( FlagDirty). A chaque modification d'une valeur dans un bloc, ce bit est positionné à 1 sans mettre à jour lamémoire centrale. Au moment de ranger un autre bloc dans ce même emplacement du cache, le contrôleur ducache teste le flag Dirty. S'il est positionné, il effectue une copie en mémoire centrale du bloc modifié avantde charger le nouveau bloc dans le cache.Cette méthode est plus rapide que le write through puisque la recopie n'est pas systématique.Toutefois, à un instant donné, le contenu du cache n'est pas strictement cohérent avec celui de la mémoirecentrale.Les techniques souvent utilisées sont write through et write back.

3.5.2.4 Problème posés par le gestion des caches

Cohérence du cacheLa mise à jour de la mémoire centrale par la méthode write back pose le problème de la cohérence du cache.Ces problèmes apparaissent dans un système multiprocesseur fortement couplé où les processeurs separtagent la mémoire centrale, ou dans un système monoprocesseur avec des périphériques effectuant desentrées/sorties par DMA (Direct Memory Access). Dans ce cas, il faut garantir la cohérence des caches afinque chaque processeur ou organe d'entrée/sortie n'accède pas à des données périmées.Plusieurs solutions à ce problème de cohérence peuvent être mise en œuvre :— Mettre en place une mémoire non cachée partagée entre les processeurs,— Utiliser la technique appelée bus snooping, bus watch, snoopy cache :Elle consiste à espionner les bus d'accès à la mémoire centrale pour déceler les signaux d'écriture concernantdes adresses présentes dans le cache. Lors de la détection d'une adresse d'un bloc présent dans le cache, lecontrôleur du cache met à jour dynamiquement le contenu du bloc correspondant dans le cache.— Vider le cache, cache flush :Avant de céder le bus à un autre processeur ou organe d'entré/sortie, on peut vider complétement le cache. Cevidage implique l'invalidation de toutes les entrées et pour chaque entrée ayant le Dirty Flag positionné,l'écriture en mémoire centrale du bloc correspondant.Cependant, pour retrouver les performances optimales du mécanisme de cache, il faudra attendre que lecache soit de nouveau rempli.

TrashingUn autre problème posé par l'emploi de cache est celui du trashing. Ce problème se produit dans un sytèmemultiprogrammé utilisant un cache direct-mapped.Supposons que plusieurs processus réfèrences des adresses mémoires différentes générant le même indexpour le cache. Les données correspondant à ces adresses sont donc projetées dans le même emplacement ducache.De ce fait, lors de changement de contexte successifs, le processeur va successivement charge la donnéecorrespondant au processus 1, puis la vider du cache pour mettre la donnée correspondant au processus 2,puis la vider du cache pour mettre la donnée correspondant au processus 3,…Ce phénomène de défaut de cache répété est appelé trashing par analogie avec le phénomène d'écroulementdans un système à mémoire virtuelle paginée.L'utilisation d'un cache plus grand géré en set-associative avec partitions résout ce problème. Le phénomènede trashing se produit d'autant moins que le nombre de partitions est élevé.

3.5.3 Caractéristisue des caches de suelsues micro-processeurs

Les micro-processeurs peuvent être subdivisés en deux catégories selon l'implantation du cache : interne ouexterne.

3.5.3.1 Micro-processeurs à cache interne

Dans cette catégorie de processeurs, le cache est implanté au plus près de l'unité centrale, dans le mêmecomposant.— Motorola 68030

– 2 caches direct-mapped de 256 octets chacun : un pour les instructions, une pour les données ;– Largeur d'un bloc du cache : 128 bits, soit 4 mots ;– Le cache n'effectue pas de bus snooping ;– La mise à jour de la mémoire centrale est effectuée par write through.

— Intel 80486– Un seul cache de 8 Kio commun aux instructions et aux données, appelé cache unifié ;– Largeur d'un bloc du cache : 128 bits, soit 4 mots ;– Le cache est géré en 4 way set-associative, son mécanisme d'accèss utilise des adresses physiques ;– Le cache fonctionne en mode bus snooping ;

– Dans la plupart des cas, un cache de second niveau complète l'architecture (I 80385).

3.5.3.2 Micro-processeurs à cache externe— Intel 80386

L'intel 386 ne possède pas de cache interne. Il pré-charge (pré-fetch) les instructions par 16 octets et utilise un cache externe de type I 80385 dont les caractéristiques sont les suivantes :– La capacité du cache est fonction de la SRAM associée : 34, 64, 128 ou 256 Kio ;– Largeur d'un bloc : 32 bits, soit 1 mot ;– Le cache est géré en 2 way set-associative, son mécanisme d'accès utilise des adresses physiques ;– La mise à jour de la mémoire centrale est faite par Posted Write ;– Le cache fonctionne en mode bus snooping.

3.5.4 Exemple complet d'architecture utilisant des caches3.5.4.1 IBM S/370-195

La machine IBM 360/85 conçue en 1965 a été la prmière machine utilisant un cache. L'IBM S/370-195construit en 1970 est un super calculateur à pipeline à 24 stations dotée du même cache que l'IBM 360/85.Ce cache est une réalisation pariculière d'un cache set-associative.— L'unité centrale a un temps de cycle de 54 ns pour chaque station du pipline ;— La mémoire centrale a un temps d'acèes de 750ns. Elles est organisée en 16 bancs entrelacés de 16 Kmots,un mots mémoire a une longueur de 512 bits. Les adresses générées par l'unité centrale sont des adressesoctets sur 24 bits ;— Le cache a un temps de 60 ns. Il est lui aussi organisée en 16 bancs entrelacés de 16 Kmot, un motsmémoire a une longueur de 512 bits. La recherche dans le cache utilise les adresses physiques. La stratégiede remplacement utilisée est une stratégie LRU câblée avec un LRU-stack ;— Le taux de présence en cache est de 99.8 %.La vitesse apparente de la mémoire est alors de : 0.998 * 60 + 0.002 * 750 = 61.38 nsLe fonctionnement du cache suit le schéma suivant :1. Les 4 bits de poids faible de l'adresse physique désignent un des 16 bancs du cache.2. Une recherche associative des 14 bit de poids fort de l'adresse physique est effectuée dans la mémoire despréfixes du banc désigné.— Si le recherche réussit, le mot de 512 bits associé est transmis à l'unité centrale.— Si elle échoue, une recherche en mémoire centrale avec l'adresse physique est effectuée. Le mot obtenuest transmis à l'unité centrale et au cache pour sa mise à jour. Si nécessaire, il y a vidage de l'entrée LRU ducache.

3.5.4.2 Fairchild CLIPPER

Le CLIPPER est un micro-processeurs 32 bits RISC cadencé à 50 MHz conçu initialement par Fairchild.La gestion mémoire du CLPPER utilise un module appelé CAMMU contenant un cache et une MMU.Le CLIPPER est équipé de deux CAMMUs : un ICAMMU pour les instructions et un DCAMMU pour lesdonnées.Le cache du CAMMU est indexé par les adresses virtuelles, rendant ainsi possible un fonctionnementparallèle entre le cache et la MMU. La vérification de l'identité entre l'objet accédé dans le cache et l'objetdésigné par l'adresse virtuelle est effectuée en comparant le préfixe du cache et le numéro de case obtenuaprès traduction de l'adresse virtuelle.Le cache est 2 way set-associative possèdant 128 entrées de 4 mots de 32 bits. Il est géré avec une stratégiede remplacement LRU.La TLB du CAMMU est 2 way set-associative à 64 entrées, la stratégie de remplacement est égalementLRU.Le problème de la cohérence entre le cache et la mémoire centrale peut être résolu en utilisant soit latechnique write through, soit la technique copy-back. La technique write through est imposée par le matérielpour la gestion des pages partagées entre différents CAMMUs.Sur cette architecture se pose le problème de l'aliasing dû à l'espace virtuel privé. En effet, un objet partagépar deux processus peut se trouver à deux adresses virtuelles distinctes dans l'espace d'adressage de chaqueprocessus. La projection dans le cache étant établie à partir des adresses virtuelles, un objet unique partagépeut posséder deux images distinctes dans le cache. Ce problème est résolu en imposant aux objets partagésd'être alignés sur une frontière de page, seul le déplacement dans une page étant utilisé pour le calcul del'index d'accès au cache.