4.14. Page à la demande et allocation processeur

On dispose d'un système monoprocesseur en multiprogrammation, doté d'une mémoire virtuelle paginée. Les processus se partagent, outre le processeur, un disque comme ressource. Les transferts disque-mémoire centrale sont assurés par un processeur spécialisé.
A- Donner une définition de la multiprogrammation. Dire pourquoi elle peut être réalisée dans notre système et expliquez-en les avantages et les inconvénients en au plus 20 lignes (on pourra prendre le point de vue de l'ingénieur système et celui de l'utilisateur)
B.- La mémoire physique est une suite d'emplacements, découpée en blocs de taille fixe, appelés cases et repérés chacun par un numéro. La mémoire linéaire (mémoire virtuelle) de chaque processus est découpée en blocs de taille fixe (celle d'une case), appelés pages et repérés par un numéro de page virtuelle. Une image de la mémoire virtuelle d'un processus est maintenue sur disque par le système (espace de pagination).
Une adresse a la structure suivante :
bit 31 bit 12
bit 11 bit 0
numéro de page virtuelle
déplacement dans la page
A chaque processus est associée une table des pages, dont la ième entrée décrit la ième page virtuelle du processus :
bit 31
bit 30
bit 29
bit 28 bit 20
bit 19 bit 0
présence
modifiée
accédée
protection
n° de case
Dans le contexte de chaque processus, un registre repère le début de la table des pages.
B.1- Décrire sous forme algorithmique, les opérations réalisées lors du décodage d'une adresse. La table des pages d'un processus est résidente en mémoire centrale. Applications :
B.2- Comment peut-on utiliser le bit page modifiée? On envisagera les cas où la page virtuelle est remplacée et celui où le processus se termine.
B.3- Le bit page accédée est positionné à 1 à chaque référence de la page par le processus, et remis périodiquement à 0 par le système. Quel algorithme de remplacement de page utilise cette information?
C- Le système comporte deux processus ayant chacun trois pages de mémoire virtuelle. A la création d'un processus, le système lance une phase d'initialisation de ce processus sans accéder à la mémoire virtuelle. Le système de pagination est à la demande, c'est-à-dire qu'initialement, aucune page n'est en mémoire centrale. Lors d'un défaut de page, le système initialise un transfert disque de la page vers une case, réalisé par le processeur spécialisé, qui dure 20 ms. On supposera, pour simplifier, que la mémoire centrale contient suffisamment de cases pour les six pages des processus. Lorsqu'un processus se termine, le système réécrit chacune de ses pages sur disque, ce transfert requiert 20ms par page.
L'allocation du processeur est faite selon l'ancienneté dans la file des processus dans l'état "prêt" et les requêtes disque sont gérées à l'ancienneté; en cas d'égalité P1 est prioritaire sur P2. Une seule requête disque peut être traitée à la fois. Le comportement des processus est le suivant :
P1 	Création du processus pendant 10ms
	Calcul utilisant la page 1 pendant 40ms
	Calcul utilisant les pages 1 et 2 pendant 10ms
	Calcul utilisant la page 2 pendant 20ms
	Calcul utilisant la page 3 pendant 30ms
	Fin P1
P2	Création du processus pendant 10ms
	Calcul utilisant la page 3 pendant 30ms
	Calcul utilisant la page 2 pendant 10ms
	Calcul utilisant les pages 2 et 1 pendant 20ms
	Fin P2
On crée le processus P1, puis le processus P2 après 10ms. Etablir le chronogramme des deux processus, du disque et du processeur sur le diagramme ci-dessous, et justifier votre réponse.

Solution de l’exercice 4.14

4.14.1. Question A

La multiprogrammation est le fait d’avoir plusieurs processus (correspondant souvent à plusieurs programmes) simultanément présents en mémoire centrale. Pour pourvoir la mettre en œuvre, il faut pouvoir garantir que ces processus puissent vivre en bonne intelligence, c’est-à-dire, évoluer chacun de leur côté sans se perturber les uns les autres. Dans notre système, les entrées-sorties sont gérées par un processeur spécialisé, ce qui permet libère le processeur central pendant la durée des transferts et lui permet de travailler pour le compte d’un autre processus.
Du point de vue de l’ingénieur système, l’avantage principal est évidemment une meilleure utilisation du processeur et donc une amélioration du temps moyen de réponse de l’ensemble des travaux. Du point de vue de l’utilisateur, deux aspects interviennent. Soit la machine est libre au moment où il soumet sa demande et le temps de réponse sera meilleur s’il est seul présent en mémoire. Par contre si la machine n’est pas libre, en monoprogrammation il devra d’abord attendre que tous les programmes arrivés avant lui soient terminés, alors qu’en multiprogrammation il pourra utiliser le processeur pendant les périodes d’inactivités des programmes arrivés avant lui.
Le système d’exploitation devient cependant plus complexe et occupe une part du temps processeur pour sa gestion (déperdition) : gestion de l’allocation du processeur, gestion du partage de ressources, gestion des défauts de page, gestion de la mémoire centrale, etc.

4.14.2. Question B

4.14.2.1. Question B.1

L’opération de décodage d’adresse peut se représenter comme suit :
Procédure décodage (var adreel : adresse ; advirt :adresse) est
var A : adresse ;
début A := table_de_page (advirt.numéro_page_virtuelle) ;
	  si non A.présence alors traitement défaut de page ; finsi ;
	  adreel.déplacement := advirt.déplacement ;
	  adreel.numéro_de_page := A.n°_de_case ;
fin ;
En appliquant cet algorithme à l’adresse 10/3000, avec une entrée 10 de la table des pages telle que présence=1 et n°_de_case=20, il n’y a pas de défaut de page, et l’adresse réelle résultante est 20/3000.
En appliquant cet algorithme à l’adresse 15/2500, avec une entrée 15 de la table des pages telle que présence=0 et n°_de_case=15, il y a défaut de page, et l’on ne peut savoir actuellement ce que sera l’adresse réelle. Le n° de case associé n’a actuellement aucune signification : c’est sans doute la dernière case associée à cette page, mais elle ne l’est plus maintenant. Le système, pour traiter ce défaut de page, doit allouer une nouvelle case à cette page, charger son contenu depuis le disque et réinitialiser l’entrée correspondante de la table des pages avant de relancer l’opération de décodage.

4.14.2.2. Question B.2

Le bit modifiée indique que la page a été modifiée depuis qu’elle a été chargée en mémoire. En d’autres termes, ce bit est mis à 1 chaque fois que le processus référence la page en écriture. Lorsque la page est remplacée, ce bit permet de savoir si elle doit être réécrite ou non sur disque avant de charger celle qui la remplace dans la case. Lorsque le processus se termine, les cases qu’il occupait en mémoire centrale sont libérées. Ce bit permet de savoir s’il est nécessaire de réécrire les pages correspondantes sur disque avant leur libération, pour ne pas perdre les dernières modifications, du moins lorsqu’elles doivent survivre à la fin d’exécution du processus (elles correspondent à des objets externes).

4.14.2.3. Question B.3

Le bit accédée indique que la page a été référencée récemment. Ce bit est mis à 1 lors de chaque accès à la page, et remis à 0 de temps en temps par l’algorithme de remplacement de page. Deux algorithmes utilisant ce bit ont été présentés en §14.3.4 : l’algorithme de la seconde chance et NRU. L’algorithme de la seconde chance est une modification de l’algorithme FIFO : au lieu de remplacer systématiquement la page la plus ancienne en mémoire, on ne la remplace que si elle n’a pas été référencée dans un passé récent. L’algorithme NRU tente d’approcher l’algorithme LRU, en dressant régulièrement les listes des pages ayant été référencées dans la période récente.

4.14.3. Question B

Voici le graphe, suivi de la chronologie des événements.

À 10, P1 accède à sa page 1, ce qui provoque un défaut de page, et P1 se bloque en attendant la fin de la lecture (fin en 30). P2 devient actif.
À 20, P2 accède à sa page 3, ce qui provoque un défaut de page, et P2 se bloque en attendant la fin de la lecture, mais le disque est occupé par la lecture de la page 1 de P1.
À 30, la page 1 de P1 étant lue, P1 redevient actif, jusqu’à son prochain défaut (en 70), et la lecture de la page 3 de P2 commence (fin en 50).
À 50, P2 devient prêt.
À 70, P1 accède à sa page 2, ce qui provoque un défaut de page et bloque P1 en attendant la fin de la lecture (fin en 90) ; P2 devient actif, jusqu’à son prochain défaut (en 100).
À 90, P1 devient prêt.
À 100, P2 accède à sa page 2, ce qui provoque un défaut de page et bloque P2 en attendant la fin de la lecture (fin en 120) ; P1 devient actif, jusqu’à son prochain défaut (en 130).
À 120, P2 devient prêt.
À 130, P1 accède à sa page 3, ce qui provoque un défaut de page et bloque P1 en attendant la fin de la lecture (fin en 150) ; P2 devient actif, jusqu’à son prochain défaut (en 140).
À 140, P2 accède à sa page 1, ce qui provoque un défaut de page et bloque P2 en attendant la fin de la lecture, mais le disque est occupé par la lecture de la page 3 de P1.
À 150, la page 3 de P1 étant lue, P1 redevient actif, jusqu’à sa terminaison (en 180), et la lecture de la page 1 de P2 commence (fin en 170).
À 170, P2 devient prêt.
À 180, P1 se termine, et les 3 pages de P1 doivent être réécrites sur le disque (fin en 240) ; P2 devient actif jusqu’à sa terminaison (en 200)
À 200, P2 se termine, et les 3 pages de P2 doivent être réécrites sur le disque, qui est occupé avec la réécriture de celles de P1.
À 240, les pages de P1 sont toutes réécrites, et on commence la réécriture des 3 pages de P2 (fin en 300).
À 300, toutes les pages de P2 ont été réécrites sur le disque.