Pour répondre aux questions posées pendant l'examen: - Free

Corrigé de l'examen « Méthodes de programmation système »
Session Juin 2002 Pour répondre aux questions posées pendant l'examen:
- Le sujet forme un ensemble cohérent.
- Les questions sont progressives et toutes différentes. Rappel: une adresse est toujours un pointeur sur un octet. C'est pourquoi
les tailles mémoire sont toujours exprimées en octet (byte).
Les instructions machine, par contre, manipulent des mots mémoire. La
taille d'un mot est dépendant du hardware et représente l'unité d'échange
entre le processeur et la mémoire: la lecture d'un mot à l'adresse 0x0 sur
une machine 32 bits va faire transiter 32 bits sur le bus et charger 32
bits dans le registre destination. A-1:
Page de 4K mots et mot de 32 bits = page de 4K * 32 bits
= page de 16K octets Une adresse 32 bits = 18 bits (numéro de page) + 14 bits (offset)
Le nombre de pages est donc de 2^18 A-2:
18 bits (numéro de page virtuelle) + 14 bits (offset)
| |
| table des pages |
| entrée 1 --------
| entrée 2 |
| ... |
--------> entrée n ----> numéro de page physique |
... | |
entrée 2^18 | |
| |
| |
adresse physique = numéro de page physique + offset A-3:
256Mo = 2^28 : il ne faut que 28 bits pour accéder à toute la mémoire
physique. Le déplacement dans une page est codé sur 14 bits donc 14 bits
sont nécessaires pour le numéro de page physique. Lorsqu'une adresse virtuelle est valide, ces 14 bits sont dans une entrée
de la table des pages + 2 bits de gestion soit 16 bits au total = la taille
d'une entrée de la table des pages. A-4:
Les adresses virtuelles 0x00000000 - 0x01FFFFFF seront représentées en
mémoire par 2^11 = 2048 pages: 11 bits seulement sont utilisés pour
différencier les numéros de pages virtuelles.
En binaire, 0x01FFFFFF s'écrit :
0000 0001 1111 1111 1111 1111 1111 1111
bits des numéros de page 0000 000x xxxx xxxx xx La table des pages est donc structurée de la façon suivante:
Les 2048 premières entrées sont pour les adresses du noyau,
Les 2048 entrées suivantes sont pour les adresses du code,
Les 2048 entrées suivantes sont pour les adresses de la pile,
Toutes les entrées suivantes sont pour les adresses des allocations
mémoire. Lorsqu'un processus est créé, il n'a pas encore commencé à s'exécuter donc
il n'a pas encore alloué de mémoire. Quel que soit le nombre de pages virtuelles (entre 0 et 2048) utilisées
pour le noyau, pour le code (entre 0 et 2048) et pour la pile (entre 0 et
2048), les entrées correspondantes seront dans les 2048 * 3 premières
entrées de la table des pages. Une page physique contient 16Ko / 16 bits = 8K entrées de la table des
pages soit 8192 entrées. Le nombre minimum de page physique est donc de 1 page. A-5:
Si 1 page physique contient 8192 = 2^13 entrées, il faudra au maximum 32
pages physiques pour représenter la totalité de l'espace virtuel du
processus: 2^18 pages / 2^13 = 2^5 = 32 A-6:
La première page physique représente les adresses virtuelles de la région
0x00000000 - 0x07FFFFFF, soit 8192 entrées.
La deuxième page physique représente les adresses virtuelles de la région
0x08000000 - 0x0FFFFFFF, etc... Il suffit d'une seule adresse virtuelle (1 page) valide par région pour que
la page physique qui représente cette région soit allouée en mémoire. Les 32 pages physiques nécessaires pour représenter la totalité de l'espace
virtuel du processus seront présentes en mémoire si au moins une adresse
virtuelle (1 page) par région est valide. Ensuite, lorsque le processus s'exécute et demande de la mémoire, le
système va mettre à jour les entrées dans les pages physiques de la table
des pages à chaque faute de page. A-7:
Dans le cas favorable (pour le système), les 4000 pages virtuelles d'un
processus P1 seront reparties dans les 2048 * 4 premières entrées de la
table des pages donc dans 1 seule page physique de 16Ko. A-8:
Dans le cas défavorable, les 4000 pages virtuelles seront reparties dans
les 32 régions de l'espace virtuel du processus et donc dans 32 pages
physiques soit au total : 32 * 16Ko = 512Ko A-9:
Les tables des pages des processus sont nécessaires au système pour gérer
les pages en mémoire physique: bit M si la page est modifiée par exemple.
Bien que possible, autoriser la pagination des tables de pages n'est pas
réaliste pour des raisons de performance.
B - Problème de création de processus
B-1 +---------+---------+---------+---------+---------+
0 1 2 3 4 5 processus open()
père sleep(2)----------->fork()
read()
affiche()
sleep(2)----------->read()
affiche() processus sleep(1)->read()
fils affiche() Ce diagramme montre que les affichages auront lieu au temps t=2s par le
processus père, t=3s par le processus fils, et t=4s par le processus père. B-2 Au temps t=1s, seul le processus père existe. Il a déjà ouvert le fichier
/home/data. Les structures U, file et inode sont donc liées de la façon
suivante :
Au temps t=3s, le processus père a exécuté le fork(). Le processus fils a
été créé par clonage de la structure U. Par contre, les structures file et
inode ne sont pas dupliquées, mais partagées par les 2 processus : On observe donc en particulier que le pointeur de position courante dans le
fichier (utilisé par le système pour calculer le déplacement par rapport au
début du fichier où seront faites les lectures/écritures) est commun aux 2
processus. B-3 Le PID du père est 10, celui de sont fils 12. Comme vu à la question B-1,
c'est le père qui accède au fichier en premier. Il lit aaaaa (ce qui a pour
effet de déplacer le pointeur de position courante en 6) puis l'affiche. La
variable pid vaut pour lui la valeur du pid de son fils, soit 12.
L'affichage est donc : 12 aaaaa puis le fils accède à son tour au fichier et y lit bbbbb (la position
courante du fichier passe alors à 11). Pour lui, la variable pid rendue par
fork() vaut 0. L'affichage suivant est donc : 0 bbbbb ensuite le père effectue la troisième lecture et affiche : 12 ccccc B-4
Dans le programme modifié, l'ouverture du fichier est effectuée après le
fork(). Dans ce cas, 2 appels systèmes sont fait pour ouvrir 2 fois le
fichier. Chaque processus a donc une structure file privée, et le pointeur
de position courante n'est plus commun. Ainsi, l'affichage sera : 12 aaaaa
0 aaaaa
12 bbbbb
C - Problème de gestion de fichiers C-1
Il s'agit d'un système de fichier de type FAT, comme le précise l'énoncé :
en effet, une entrée dans un répertoire contient le numéro du premier bloc
de données de l'objet dans le cas d'un système FAT, et contient un numéro
d'inode dans le cas d'un système en mode inode. C-2
Il s'agit de rechercher une entrée de répertoire qui contiendrait comme
premier bloc de données 5. On voit que cet objet de type F - fichier dont
les données commencent dans le bloc 5 s'appelle data. Le répertoire dans
lequel se trouve sa description a ses données dans le bloc numéro 2. C-3
L'entrée de répertoire qui décrit le fichier nommé delta se trouve dans le
bloc 1 : F delta 6. Les données sont donc situées dans le bloc 6 :
Albert
Barnabé
C-4
Les répertoires et fichiers présents sur ce disque sont : \ répertoire racine, dont les données sont dans le bloc 1 (par convention,
le premier bloc de données du répertoire racine est situé juste après la
FAT sur le disque) Dans ce bloc 1, on retrouve les objets directement situés sous la racine :
1 répertoire alpha, et 2 fichiers beta et delta \alpha
\beta
\delta le répertoire alpha a son bloc de données en 2, et contient lui même un
fichier appelé data on a donc : \ (R)
|
+-------------------------+----------------------+
| | |
alpha (R) beta (F) delta (F)
|
|
data (F) C-5
La table FAT est utilisée pour les chaînages des blocs de données lorsqu'un
seul bloc n'est pas suffisant pour contenir toutes les données. Dans ce
cas, le numéro du bloc suivant est trouvé en lisant le contenu de l'entrée
dans la table FAT. Dans notre cas, c'est l'entrée 6 qui est
corrompue. C'est donc le fichier dont les données sont dans le bloc 6
(delta) qui va se voir « étendu » avec les données situées dans le bloc 7
(autrement dit, Ernestine, Paulette et Cunégonde vont rejoindre Albert et
Barnabé dans le fichier delta). Dans la réalité, l'entrée dans le répertoire contient aussi la longueur
exacte du fichier en octet. Ainsi, le système de fichier détecterait une
incohérence entre cette taille en octet et le nombre de blocs dans la
chaîne des blocs, mais il serait incapable de corriger, ne sachant pas
laquelle des 2 informations est fausse.
-----------------------
U U_id
G_id
table des
fichiers
ouverts
file position inode no disque
bloc 1
bloc 2
... inode no disque
bloc 1
bloc 2
... file position U (père) U_id
G_id
table des
fichiers
ouverts
U (fils) U_id
G_id
table des
fichiers
ouverts