Correction de l’examen du 21 mai 2003

Ce document présente la correction d’un examen de Programmation Système portant sur la mémoire virtuelle et la gestion des processus. Il évalue les compétences en compréhension des mécanismes de pagination, en analyse d’algorithmes de gestion mémoire, ainsi qu’en programmation concurrente avec gestion de fichiers et synchronisation entre processus.

A - Mémoire virtuelle

Il s'agit d'analyser la structure des adresses virtuelles et physiques, d'interpréter une table des pages, d'étudier un algorithme de gestion de pages, et de comprendre les limites liées au codage des entrées de table des pages.

Réponse 1 : Structure des adresses virtuelles et physiques

On demande d’expliquer la décomposition d’une adresse virtuelle en numéro de page virtuelle et déplacement dans la page, ainsi que la traduction vers une adresse physique.

Une seule table des pages par processus impose que l’adresse virtuelle soit décomposée en :

adresse virtuelle = numéro de page virtuelle + déplacement dans la page

Le numéro de page virtuelle sert d’indice dans la table des pages. Si le bit de présence est à 1, alors le numéro de page physique associé est valide et l’adresse physique se calcule par :

adresse physique = numéro de page physique + déplacement dans la page

La taille d’une page virtuelle est égale à la taille d’une page physique.

Si la table des pages contient 8 entrées, alors 3 bits suffisent pour coder le numéro de page virtuelle (car 2^3 = 8). Les bits restants codent le déplacement dans la page.

La taille d’une page, exprimée en octets, est donc :

2^nombre_de_bits_restants

Exemples selon la taille de l’adresse virtuelle :

Adresse virtuelle	Bits numéro page	Taille page physique	Taille mémoire processus
8 bits	3 bits	2^5 = 32 octets	2^8 = 256 octets
16 bits	3 bits	2^13 = 8 Ko	2^16 = 64 Ko
32 bits	3 bits	2^29 = 512 Mo	2^32 = 4 Go

Réponse finale : La décomposition de l’adresse virtuelle en numéro de page virtuelle (3 bits) et déplacement dans la page permet de déterminer la taille de la page et la taille mémoire du processus selon la taille totale de l’adresse virtuelle.

Réponse 2 : Traduction d’adresses virtuelles en adresses physiques

On demande de calculer les adresses physiques correspondant à 16 adresses virtuelles données, en tenant compte du bit de présence et du numéro de page physique.

Les adresses virtuelles sont :

0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88, 0x99, 0xAA, 0xBB, 0xCC, 0xDD, 0xEE, 0xFF

Le numéro de page virtuelle est obtenu par les 3 bits de poids fort (car 8 pages), et le déplacement par les 5 bits restants.

Le bit de présence est à 1 pour les 10 premières adresses, et à 0 pour les 6 suivantes, ce qui signifie que ces dernières ne sont pas en mémoire physique.

Le numéro de page physique est donné pour les pages présentes :

• Page virtuelle 0 → page physique 7
• Page virtuelle 1 → page physique 6
• Page virtuelle 2 → page physique 5
• Page virtuelle 3 → page physique 4
• Page virtuelle 4 → page physique 3
• Page virtuelle 5 → page physique 3

Les adresses physiques sont calculées en remplaçant le numéro de page virtuelle par le numéro de page physique, en conservant le même déplacement :

Adresse virtuelle	Adresse physique
0x00	0xE0
0x11	0xF1
0x22	0xC2
0x33	0xD3
0x44	0xA4
0x55	0xB5
0x66	0x86
0x77	0x97
0x88	0x68
0x99	0x79
0xAA	-
0xBB	-
0xCC	-
0xDD	-
0xEE	-
0xFF	-

Réponse finale : Les adresses physiques sont valides et calculées pour les pages présentes, les autres adresses ne sont pas mappées en mémoire physique.

Réponse 3 : Analyse de l’algorithme FIFO et défauts de pages

On étudie l’algorithme de libération des pages FIFO (premier arrivé, premier enlevé) avec 3 puis 4 pages libres, en comptant les défauts de pages (indiqués par *).

Avec 3 pages libres, on obtient 9 défauts de pages. Avec 4 pages libres, on obtient 10 défauts de pages.

Cette augmentation du nombre de défauts de pages alors que la mémoire physique disponible augmente est une anomalie connue sous le nom d’anomalie de Belady, caractéristique de l’algorithme FIFO.

Réponse finale : L’algorithme FIFO peut générer plus de défauts de pages en augmentant la mémoire disponible, ce qui est une anomalie de Belady.

Réponse 4 : Limites du codage des entrées de table des pages

On considère un adressage sur 8 bits, avec une entrée de table des pages codée sur 6 bits : 3 bits d’état et 3 bits pour le numéro de page physique.

La mémoire physique est donc limitée à 8 pages de 32 octets. Cela limite fortement le nombre de processus pouvant être en mémoire simultanément (8 processus dans le cas favorable d’une page par processus).

Augmenter le nombre de bits pour coder le numéro de page physique permet d’augmenter la mémoire physique sans changer l’espace d’adressage virtuel des processus.

Ce principe s’applique aussi aux machines 32 bits actuelles : la mémoire physique peut dépasser 4 Go, alors que l’espace d’adressage virtuel reste limité à 4 Go par processus.

Réponse finale : Le codage limité du numéro de page physique restreint la mémoire physique accessible, ce qui limite le nombre de processus en mémoire et l’efficacité du système.

B – Problème de création de processus

On analyse un programme utilisant fork(), open(), read(), print() et la gestion partagée du descripteur de fichier entre père et fils. On étudie les ordres d’exécution, les affichages produits, puis on modifie le programme pour synchroniser l’accès au fichier via sémaphores et gérer l’arrêt par signal.

Question 1 : Enchaînement des fonctions exécutées par père et fils

On demande de lister l’ordre d’exécution des fonctions open(), read(), print(), fork(), read(), print() pour le père et le fils.

Le père exécute :

open()
read()
print()
fork()
read()
print()

Le fils exécute :

read()
print()

Réponse finale : Le père exécute open(), read(), print(), fork(), puis read(), print(). Le fils exécute read(), print() après fork().

Question 2 : Deux affichages différents produits par le programme

On observe deux cas d’affichage possibles :

• CAS 1 :

abcdefghij
klmno
pqrst

• CAS 2 :

abcdefghij
pqrst
klmno

Réponse finale : Le programme peut afficher ces deux séquences différentes selon l’ordonnancement des processus père et fils.

Question 3 : Explication des différences d’affichage

Le système UNIX ne garantit pas d’ordonnancement précis entre père et fils. Le pointeur de position dans le fichier est partagé, donc l’ordre des read() et print() peut varier :

• Dans le cas 1, le père effectue read()/print() avant le fils, puis le fils lit et affiche.
• Dans le cas 2, le père lit et affiche, puis fork(), puis le fils lit et affiche avant le père.

Le pointeur de fichier est modifié par chaque read(), ce qui explique les différences d’affichage.

Réponse finale : L’absence de synchronisation et le partage du pointeur de fichier entraînent des ordres d’exécution variables, produisant deux affichages différents.

Question 4 : Écriture de la boucle du processus père

Le père doit lire des données sur un capteur puis les écrire au début du fichier, en boucle infinie.

Exemple de boucle :

do {
    lire_capteur(buffer);
    lseek(fd, 0, SEEK_SET);
    write(fd, buffer, 5);
} while (1)

Réponse finale : La boucle du père lit 5 caractères du capteur, positionne le pointeur au début du fichier, puis écrit les données, en répétant indéfiniment.

Question 5 : Explication du problème de lecture incorrecte par le fils

Parfois, le fils lit les caractères 5 à 9 au lieu de 0 à 4. Cela s’explique par un problème d’ordonnancement :

• Le fils effectue lseek(fd, 0, SEEK_SET), puis est interrompu.
• Le père exécute lseek(fd, 0, SEEK_SET) et write(fd, buffer, 5), ce qui déplace le pointeur à 5.
• Le fils reprend et lit à partir de la position 5, donc lit les caractères 5 à 9.

Le pointeur de fichier partagé est modifié de façon concurrente sans synchronisation.

Réponse finale : L’absence de protection des sections critiques lseek()/read() et lseek()/write() provoque des lectures décalées.

Question 5 (suite) : Identification des sections critiques et solution avec sémaphores

Les sections critiques sont :

• Pour le père : lseek() et write()
• Pour le fils : lseek() et read()

Pour éviter les interférences, on encadre ces sections critiques par des opérations P(semaphore) et V(semaphore), avec un sémaphore initialisé à 1.

Exemple de code modifié :

init(semaphore, 1);

PID = fork();
if (PID == 0)
{
  do {
    P(semaphore);
    lseek(fd, 0, SEEK_SET);
    count = read(fd, buffer, 5);
    V(semaphore);
    if (count == 5)
    {
      traiter_données(buffer);
      print(buffer);
    }
  } while (1);
}
else
{
  do {
    lire_capteur(buffer);
    P(semaphore);
    lseek(fd, 0, SEEK_SET);
    write(fd, buffer, 5);
    V(semaphore);
  } while (1);
}

Réponse finale : L’utilisation d’un sémaphore protège les accès concurrents au fichier, évitant les lectures erronées.

Question 6 : Modification pour arrêt des boucles sur signal SIG_USR1

Il faut que les deux processus puissent recevoir l’information d’arrêt. Une solution est d’envoyer le signal au père, qui le transmet au fils.

Exemple de gestionnaire de signal :

int cont = 1;
int PID;

usr1_handler()
{
    cont = 0;
    if (PID)
        kill(PID, SIG_USR1);
}

Dans main(), on installe le gestionnaire :

signal(SIG_USR1, usr1_handler);

Les boucles deviennent conditionnelles sur la variable cont :

do {
    P(semaphore);
    lseek(fd, 0, SEEK_SET);
    count = read(fd, buffer, 5);
    V(semaphore);
    if (count == 5)
    {
      traiter_données(buffer);
      print(buffer);
    }
} while (cont);

et

do {
    lire_capteur(buffer);
    P(semaphore);
    lseek(fd, 0, SEEK_SET);
    write(fd, buffer, 5);
    V(semaphore);
} while (cont);

Réponse finale : La variable globale cont contrôlée par le gestionnaire de signal permet d’arrêter proprement les boucles dans les deux processus, avec propagation du signal du père au fils.

Méthode

Ce sujet récompense une bonne compréhension des mécanismes de mémoire virtuelle, notamment la décomposition des adresses et la gestion des tables de pages. Il valorise également la capacité à analyser des algorithmes classiques comme FIFO et à identifier des anomalies telles que celle de Belady.

En programmation système, il est crucial de comprendre le partage des ressources entre processus, en particulier des descripteurs de fichiers et des pointeurs de position. Le sujet met en avant l’importance de la synchronisation via sémaphores pour protéger les sections critiques et éviter les comportements indéterminés.

Enfin, la gestion des signaux et l’arrêt coordonné de processus concurrents sont des compétences clés. La proposition d’un gestionnaire de signal et la communication entre processus via kill() montrent la maîtrise des mécanismes UNIX.

Les erreurs pénalisées sont principalement :

• Confusion dans la décomposition des adresses virtuelles et physiques.
• Omission des bits de présence ou mauvaise interprétation des tables de pages.
• Ignorer les effets du partage du pointeur de fichier entre père et fils.
• Ne pas protéger les accès concurrents aux fichiers, conduisant à des lectures incorrectes.
• Ne pas gérer correctement l’arrêt des processus avec les signaux.