Programmation Système

Ce sujet porte sur la programmation système et se présente sous la forme d'un devoir surveillé. Il évalue les compétences en gestion de mémoire virtuelle, en création de processus et en compréhension des systèmes de fichiers. Chaque partie propose des questions demandant des raisonnements précis et des calculs techniques.

Partie A - Problème de mémoire virtuelle

Cette partie porte sur la gestion de la mémoire virtuelle dans une machine avec adresses 32 bits et pages de 4K mots.

Question A-1

Calculer le nombre de pages, sous forme de puissance de 2, définissant l'espace adressable total d'un processus 32 bits, sachant que la taille d'un mot est de 32 bits.

Un espace d'adressage 32 bits signifie que l'adresse virtuelle est codée sur 32 bits, donc l'espace adressable total est de 2^32 mots.

La taille d'une page est de 4K mots, soit 4 × 1024 = 4096 mots = 2^12 mots.

Le nombre total de pages est donc :

Nombre de pages = 2^32 / 2^12 = 2^(32 - 12) = 2^20

Réponse : Le nombre de pages est 2^20.

Question A-2

Représenter la traduction d'une adresse virtuelle 32 bits en adresse physique 32 bits.

Une adresse virtuelle de 32 bits est divisée en deux parties :

• Le numéro de page virtuelle (VPN) : les 20 bits de poids fort (car 2^20 pages)
• Le décalage (offset) dans la page : les 12 bits de poids faible (car taille page = 2^12 mots)

La traduction utilise la table des pages pour convertir le VPN en numéro de page physique (PPN), puis l'adresse physique est :

Adresse physique = (PPN << 12) + offset

Schéma :

Adresse virtuelle (32 bits) : | VPN (20 bits) | Offset (12 bits) |
Table des pages : VPN → PPN
Adresse physique (32 bits) : | PPN (20 bits) | Offset (12 bits) |

Réponse : L'adresse virtuelle est divisée en 20 bits de numéro de page et 12 bits d'offset, la table des pages traduit le numéro de page virtuelle en numéro de page physique, puis l'adresse physique est recomposée.

Question A-3

La mémoire physique est limitée à 256 Mo. Quelle est la taille minimale en bits d'une entrée de la table des pages, sachant que seuls les bits V (valide) et M (modifiée) sont nécessaires ?

Calcul du nombre de pages physiques :

• 256 Mo = 256 × 2^20 octets = 2^8 × 2^20 = 2^28 octets
• Chaque mot est de 32 bits = 4 octets
• Nombre de mots en mémoire physique = 2^28 octets / 4 octets = 2^26 mots
• Taille d'une page = 2^12 mots
• Nombre de pages physiques = 2^26 / 2^12 = 2^(26 - 12) = 2^14 pages

Pour coder le numéro de page physique, il faut 14 bits.

Ajouter 2 bits pour V et M :

Taille minimale d'une entrée = 14 + 2 = 16 bits

Réponse : Une entrée de la table des pages doit être codée sur 16 bits minimum.

Question A-4

Calculer le nombre minimum de pages physiques nécessaires pour représenter la table des pages d'un processus, compte tenu des plages d'adresses virtuelles réservées :

• 0x00000000 - 0x01FFFFFF : noyau
• 0x02000000 - 0x03FFFFFF : code
• 0x04000000 - 0x05FFFFFF : pile
• 0x06000000 - 0xFFFFFFFF : allocations mémoire

Calculer le nombre de pages virtuelles utilisées par ces plages :

• Plage noyau : 0x02000000 - 0x00000000 = 0x02000000 = 33 554 432 octets = 2^25 octets
• Plage code : 0x04000000 - 0x02000000 = 0x02000000 = 2^25 octets
• Plage pile : 0x06000000 - 0x04000000 = 0x02000000 = 2^25 octets
• Plage allocations : 0xFFFFFFFF - 0x06000000 + 1 = 0x9A000000 octets (environ 2,58 × 10^9 octets)

Mais on cherche le nombre minimum de pages physiques nécessaires pour stocker la table des pages. La table des pages contient une entrée par page virtuelle.

Calcul du nombre total de pages virtuelles :

• Taille totale de l'espace virtuel : 2^32 mots × 4 octets = 2^34 octets (mais ici l'adresse est en mots, donc 4 octets par mot)
• Chaque page contient 4K mots = 2^12 mots = 2^14 octets
• Nombre total de pages virtuelles = 2^34 / 2^14 = 2^20 (confirmé A-1)

Mais ici, on ne considère que les plages utilisées :

• Plage noyau : 2^25 octets / 2^14 octets = 2^(25-14) = 2^11 pages
• Plage code : 2^11 pages
• Plage pile : 2^11 pages
• Plage allocations : (0xFFFFFFFF - 0x06000000 + 1) octets / 2^14 octets

Calcul de la plage allocations :

0xFFFFFFFF = 4 294 967 295 (décimal)

0x06000000 = 100 663 296 (décimal)

Différence = 4 294 967 295 - 100 663 296 + 1 = 4 194 304 000 octets environ

Nombre de pages allocations = 4 194 304 000 / 16 384 = 256 000 pages environ (2^18)

Nombre total de pages utilisées :

2^11 (noyau) + 2^11 (code) + 2^11 (pile) + 2^18 (allocations) ≈ 2048 + 2048 + 2048 + 262 144 = 270 288 pages

La table des pages contient une entrée par page virtuelle, donc il faut stocker 270 288 entrées.

Chaque page de table des pages contient 2^12 entrées (car taille page = 4K mots, et chaque entrée est 1 mot).

Nombre de pages physiques nécessaires pour stocker la table des pages :

270 288 / 4096 ≈ 66 pages

Réponse : Le nombre minimum de pages physiques nécessaires pour la table des pages est 66.

Question A-5

Quel est le nombre maximum de pages nécessaires pour représenter la table des pages d'un processus actif ?

Le maximum correspond au cas où toutes les pages virtuelles sont utilisées, soit 2^20 pages (cf. A-1).

Nombre de pages pour la table des pages :

2^20 entrées / 2^12 entrées par page = 2^(20-12) = 2^8 = 256 pages

Réponse : Le nombre maximum de pages nécessaires est 256.

Question A-6

Dans quel cas ce maximum sera-t-il atteint ? Que se passe-t-il ensuite ?

Le maximum est atteint lorsque tout l'espace virtuel est utilisé, c'est-à-dire que toutes les pages virtuelles sont allouées et présentes dans la table des pages.

Ensuite, si le processus tente d'allouer plus de mémoire, il ne pourra pas car la table des pages est saturée. Le système devra alors gérer la mémoire en libérant des pages, en utilisant le swap ou en refusant l'allocation.

Réponse : Le maximum est atteint lorsque toutes les pages virtuelles sont utilisées. Ensuite, le système doit gérer la saturation en swapant ou en refusant des allocations.

Question A-7

Décrire le cas favorable pour un processus P1 utilisant 4000 pages virtuelles, donnant la taille minimum de la table des pages.

Le cas favorable est celui où les 4000 pages virtuelles sont contiguës, donc la table des pages peut être représentée par un bloc continu d'entrées.

Nombre de pages pour la table des pages :

4000 entrées / 4096 entrées par page ≈ 1 page

Donc la table des pages occupe une seule page physique.

Réponse : Le cas favorable est lorsque les 4000 pages sont contiguës, la table des pages occupe alors 1 page physique.

Question A-8

Décrire le cas défavorable pour P1, donnant la taille maximum de la table des pages et sa valeur.

Le cas défavorable est lorsque les 4000 pages virtuelles sont dispersées dans l'espace virtuel, ce qui oblige à avoir une entrée dans la table des pages pour chaque page, mais aussi à allouer une page de table des pages pour chaque bloc de 4096 entrées, même si elles sont peu utilisées.

Pour 4000 pages, si elles sont dispersées, chaque page virtuelle nécessite une entrée dans la table, mais la table des pages doit couvrir tout l'espace virtuel utilisé.

Le nombre maximum de pages de table des pages est donc 4000 / 4096 = 1 page (car 4000 < 4096), mais si elles sont dispersées sur plusieurs plages, il faut autant de pages de table des pages que nécessaire pour couvrir les plages.

Sans plus d'informations sur la fragmentation, on peut considérer que la taille maximum est 2 pages (car 4000 > 2048 × 2, mais ce n'est pas précisé).

Le document ne donne pas assez d'informations pour un calcul exact.

Réponse : Le cas défavorable est une dispersion maximale des pages virtuelles, ce qui augmente la taille de la table des pages. La taille maximum est approximativement 2 pages physiques.

Question A-9

Le système peut-il mettre en swap les pages utilisées pour représenter les tables des pages des processus ?

La table des pages est essentielle pour la traduction des adresses virtuelles en physiques. Si ces pages sont mises en swap, la traduction ne peut pas se faire, ce qui bloque l'accès mémoire.

En général, les pages contenant les tables des pages ne sont pas swappées pour garantir la cohérence et la disponibilité de la traduction.

Réponse : Non, le système ne peut pas mettre en swap les pages des tables des pages.

Partie B - Problème de création de processus

Cette partie analyse un programme en C utilisant fork(), open(), read() et sleep(), avec un fichier contenant une chaîne de caractères.

Question B-1

Positionner sur un axe de temps les appels de fonctions effectués par les processus créés au lancement du programme (1 ligne par processus).

Programme initial :

fd = open("/home/data", O_RDWR);
sleep(2);
pid = fork();
if (pid == 0) {
  sleep(1);
  rc = read(fd, buffer, 5);
  affiche(pid, buffer);
} else {
  rc = read(fd, buffer, 5);
  affiche(pid, buffer);
  sleep(2);
  rc = read(fd, buffer, 5);
  affiche(pid, buffer);
}

Chronologie (en secondes) :

• 0s : fd = open()
• 0s-2s : sleep(2) (processus initial)
• 2s : fork() → deux processus : P0 (parent), P1 (enfant)

Processus enfant (pid=0) :

• 2s : fork() retourne 0
• 2s-3s : sleep(1)
• 3s : read(fd, buffer, 5)
• 3s : affiche(0, buffer)

Processus parent (pid ≠ 0) :

• 2s : read(fd, buffer, 5)
• 2s : affiche(pid, buffer)
• 2s-4s : sleep(2)
• 4s : read(fd, buffer, 5)
• 4s : affiche(pid, buffer)

Représentation sur axe temps :

Temps (s) : 0    1    2    3    4    5
P0        : open - sleep - fork - read - affiche - sleep - read - affiche
P1        :           fork - sleep - read - affiche

Réponse : Le programme effectue open puis sleep(2) avant fork. Après fork, le parent lit et affiche à 2s, dort 2s, puis lit et affiche à 4s. L'enfant dort 1s, lit et affiche à 3s.

Question B-2

Décrire les structures de données (U, file et inode) et les pointeurs qui les relient au temps t=1s et t=3s.

À t=1s :

• Un processus initial (pid=10) est actif, avec un descripteur de fichier fd ouvert sur /home/data.
• Structures :
• U : structure de contrôle du processus contenant la table des descripteurs de fichiers.
• file : structure représentant l'ouverture du fichier, avec pointeur vers inode.
• inode : structure décrivant le fichier /home/data sur disque.
• Le fd pointe vers une entrée file, qui pointe vers inode.

À t=3s :

• Le fork a créé un processus enfant (pid=12) avec une copie des structures U, file et inode.
• Les deux processus partagent le même descripteur fd pointant vers la même file et inode.
• Les compteurs de références dans file et inode sont incrémentés.

Réponse : À t=1s, un processus avec fd ouvert sur /home/data. À t=3s, deux processus (pid=10 et 12) partagent les mêmes file et inode via leurs structures U.

Question B-3

Avec PID initial 10 et PID enfant 12, donner l'ordre des messages affichés par le programme.

Lecture du fichier /home/data contenant « aaaaabbbbbcccccdddddeeeee ».

Lecture de 5 caractères à chaque read.

Chronologie des lectures :

• À 2s, parent lit 5 caractères : "aaaaa"
• À 3s, enfant lit 5 caractères : "bbbbb" (pointeur fd partagé, avancé par la lecture du parent)
• À 4s, parent lit 5 caractères : "ccccc"

Affichages :

2s : affiche(10, "aaaaa")
3s : affiche(12, "bbbbb")
4s : affiche(10, "ccccc")

Réponse : L'ordre des affichages est :

1. 10 aaaaa
2. 12 bbbbb
3. 10 ccccc

Question B-4

Même question avec programme modifié où chaque processus ouvre indépendamment le fichier après fork.

Modification :

sleep(2);
pid = fork();
if (pid == 0) {
  fd = open("/home/data", O_RDWR);
  sleep(1);
  rc = read(fd, buffer, 5);
  affiche(pid, buffer);
} else {
  fd = open("/home/data", O_RDWR);
  rc = read(fd, buffer, 5);
  affiche(pid, buffer);
  sleep(2);
  rc = read(fd, buffer, 5);
  affiche(pid, buffer);
}

Chronologie :

• 0s-2s : sleep(2)
• 2s : fork()
• 2s : parent ouvre /home/data, lit 5 caractères → "aaaaa", affiche(10, "aaaaa")
• 2s : enfant ouvre /home/data
• 3s : enfant sleep(1) termine
• 3s : enfant lit 5 caractères → "aaaaa" (pointeur fd indépendant), affiche(12, "aaaaa")
• 4s : parent sleep(2) termine
• 4s : parent lit 5 caractères → "bbbbb", affiche(10, "bbbbb")

Ordre des affichages :

1. 10 aaaaa
2. 12 aaaaa
3. 10 bbbbb

Réponse : Les messages affichés sont dans l'ordre 10 aaaaa, 12 aaaaa, 10 bbbbb.

Partie C - Problème de systèmes de fichiers

Analyse d'un système de fichiers avec des blocs de données et des entrées de répertoire.

Question C-1

Identifier si le système est de type FAT ou inode.

Les entrées de répertoire contiennent :

• 1 lettre pour le type (F ou R)
• Nom de l'objet
• Numéro du premier bloc de données

Ce format correspond à une table d'allocation par blocs (FAT) où chaque entrée pointe vers le premier bloc.

Réponse : Il s'agit d'un système de fichiers de type FAT.

Question C-2

Donner le nom du fichier dont les données sont dans le bloc 5.

Dans la liste, le fichier "beta" commence au bloc 4 et a 4 blocs (4,5,6,7).

Le bloc 5 appartient donc au fichier "beta".

Réponse : Le fichier dont les données sont dans le bloc 5 est "beta".

Question C-3

Donner le contenu du fichier nommé « delta ».

"delta" commence au bloc 6 et a 6 blocs (6,7,8,9,10,11) selon la liste.

Le contenu des blocs 6 et suivants n'est pas précisé dans le document, sauf que le bloc 6 est listé.

Le document ne fournit pas le contenu exact des blocs de "delta".

Réponse : Le contenu exact du fichier « delta » n'est pas donné dans le document.

Question C-4

Donner la structure globale des fichiers et répertoires présents sur ce disque sous forme graphique.

À partir des données :

• R alpha 2
• F beta 4
• F delta 6
• F data 5

Structure :

alpha (répertoire)
├─ beta (fichier)
├─ delta (fichier)
└─ data (fichier)

Les noms Ernestine, Paulette, Cunégonde, Paris, Lyon, Marseille, Grenoble, Lille, Brest, Albert, Barnabé semblent être contenus dans les fichiers ou répertoires, mais sans précision sur leur organisation.

Réponse : La structure globale est un répertoire "alpha" contenant les fichiers "beta", "delta" et "data".

Question C-5

Quel serait l'effet pour un utilisateur si, à la suite d'une panne, le contenu du bloc 0 devenait :

3
1
0
0
0
0
0
7
0

Le bloc 0 contient des entrées de répertoire. Une modification non prévue dans ce bloc peut corrompre la table des fichiers et répertoires.

Effets possibles :

• Perte d'accès à certains fichiers ou répertoires
• Incohérence dans la navigation du système de fichiers
• Erreurs lors des opérations sur les fichiers

Réponse : L'utilisateur subirait une perte d'accès ou une corruption des fichiers/répertoires liés au bloc 0, entraînant des erreurs ou une impossibilité d'accéder à certains fichiers.

Méthodes et conseils pour réussir ce devoir

Ce devoir récompense une compréhension précise des concepts de mémoire virtuelle, de gestion des processus et de systèmes de fichiers. Il faut :

• Respecter les définitions et conventions données (taille des mots, organisation des pages, etc.).
• Effectuer des calculs rigoureux en puissances de 2, en tenant compte des unités (octets, mots, pages).
• Illustrer les raisonnements par des schémas ou des décompositions claires (ex. division adresse virtuelle).
• Pour la programmation, suivre la chronologie exacte des appels et comprendre l'impact du partage ou non des descripteurs de fichiers.
• Ne pas inventer d'informations manquantes, mais signaler clairement les insuffisances du document.
• Utiliser un vocabulaire technique précis et expliquer chaque étape, même simple.

Les erreurs fréquentes à éviter :

• Confondre taille en octets et en mots.
• Omettre les bits de contrôle dans le calcul de la taille des entrées.
• Ignorer le partage des descripteurs de fichiers après fork.
• Ne pas justifier les réponses par des calculs ou des raisonnements.