Dans cet exercice, la gestion de la mémoire virtuelle est ... - Free

Programmation Système

Correction de l'examen du 21 mai 2003


A - Mémoire virtuelle

Réponse 1 :
Une seule table des pages par processus impose la décomposition suivante :
adresse virtuelle = numéro de page virtuelle + déplacement dans la page

Le numéro de page virtuelle désigne une entrée dans la table des pages.
Si le bit de présence est à 1 alors le numéro de page physique est valide :
adresse physique = numéro de page physique + déplacement dans la page

Page virtuelle et page physique ont la même taille.

Si le nombre d'entrées dans la table des pages est limité à 8 alors 3 bits
sont nécessaires pour coder le numéro de page et ce quel que soit le mode
d'exécution. Les bits restants forment le déplacement dans la page.

Une adresse est toujours un pointeur vers un octet donc la taille d'une
page s'exprime en octet et est égale à :
2^nombre_de_bits_restants (lire : 2 puissance nombre_de_bits_restants)

| |8 bits |16 bits |32 bits |
|Numéro de page virtuelle |3 bits |3 bits |3 bits |
|Taille d'une page physique|2^5 = 32o |2^13 = 8Ko |2^29 = 512Mo |
|Taille mémoire du |2^8 = 256o |2^16 = 64Ko |2^32 = 4Go |
|processus | | | |



Réponse 2 :
Adresses physiques correspondant aux 16 adresses virtuelles :

|adresse |numéro de |bit de |numéro de |Adresse |
|virtuelle |page |présence |page physique|physique |
| |virtuelle | | | |
|0x00 |0 |1 |7 |0xE0 |
|0x11 |0 |1 |7 |0xF1 |
|0x22 |1 |1 |6 |0xC2 |
|0x33 |1 |1 |6 |0xD3 |
|0x44 |2 |1 |5 |0xA4 |
|0x55 |2 |1 |5 |0xB5 |
|0x66 |3 |1 |4 |0x86 |
|0x77 |3 |1 |4 |0x97 |
|0x88 |4 |1 |3 |0x68 |
|0x99 |4 |1 |3 |0x79 |
|0xAA |5 |0 |- |- |
|0xBB |5 |0 |- |- |
|0xCC |6 |0 |- |- |
|0xDD |6 |0 |- |- |
|0xEE |7 |0 |- |- |
|0xFF |7 |0 |- |- |



Réponse 3 :
L'algorithme de libération des pages est de type « premier arrivé, premier
enlevé » (FIFO). Un défaut de page est représenté par le symbole *

On obtient avec 3 pages libres en mémoire :

|Numéro de page|0 |1 |4 |2 |0 |1 |3 |0 |1 |4 |2 |3 |
|défaut de page|* |* |* |* |* |* |* | | |* |* | |
| |0 |0 |0 |2 |2 |2 |3 |3 |3 |3 |3 |3 |
| | |1 |1 |1 |0 |0 |0 |0 |0 |4 |4 |4 |
| | | |4 |4 |4 |1 |1 |1 |1 |1 |2 |2 |

Nombre de défauts de pages : 9

Et avec 4 pages libres en mémoire :

|Numéro de page|0 |1 |4 |2 |0 |1 |3 |0 |1 |4 |2 |3 |
|défaut de page|* |* |* |* | | |* |* |* |* |* |* |
| |0 |0 |0 |0 |0 |0 |3 |3 |3 |3 |2 |2 |
| | |1 |1 |1 |1 |1 |1 |0 |0 |0 |0 |3 |
| | | |4 |4 |4 |4 |4 |4 |1 |1 |1 |1 |
| | | | |2 |2 |2 |2 |2 |2 |4 |4 |4 |

Nombre de défauts de pages : 10

On constate que l'exécution du processus génère 1 faute de page
supplémentaire alors que la mémoire physique disponible est plus grande.
C'est un des problèmes de l'algorithme FIFO : anomalie de Belady.


Réponse 4 :
Dans le cas d'un adressage sur 8 bits, une entrée de la table des pages
peut être codée sur 6 bits : 3 bits d'état et 3 bits pour le numéro de page
physique.
Dans ce cas, la mémoire physique est limitée à 8 pages de 32 octets. Le
système ne sera pas très efficace : même avec une mémoire privée pour
l'exécution du système et dans le cas favorable de processus utilisant une
seule page, la mémoire physique est saturée avec 8 processus...

Augmenter le nombre de bits pour coder le numéro de page physique dans la
table des pages permet d'augmenter la mémoire physique de la machine sans
rien changer à l'espace d'adressage des processus : la mémoire virtuelle
d'un processus reste limitée à 256 octets. Par contre, le système est
capable d'exécuter beaucoup plus de processus en mémoire sans avoir besoin
d'utiliser l'espace de pagination (swap), toujours très pénalisant en terme
de performances.

Le même principe s'applique aux machines 32bits actuelles : la mémoire
physique n'est plus limitée à 4Go alors que les processus continuent de
fonctionner avec des adresses 32bits donc avec une mémoire de 4Go maximum.
Il faut par contre, pour que la machine soit performante, que le système et
surtout le matériel soient adaptes.



B - Problème de création de processus


Soit le fichier /user/toto contenant la chaîne de caractères :
abcdefghijklmnopqrst

On se propose d'étudier le programme suivant :

main()
{
int PID;
int fd;
char buffer[20];

fd = open("/user/toto", O_RDWR);
read(fd, buffer, 10);
print(buffer);

PID = fork();
if (PID == 0)
{
read(fd, buffer, 5);
print(buffer);
}
else
{
read(fd, buffer, 5);
print(buffer);
}
}
Les fonctions open() et read() sont les appels systèmes vus en cours.
La fonction print() affiche sur le terminal le contenu du buffer passé en
paramètre. On remarque que comme le fichier est ouvert AVANT l'appel à la
fonction fork(), les structures internes au noyau utilisées pour l'accès au
fichier sont PARTAGEES par le processus père et le processus fils.


Question 1 :
Donnez l'enchaînement des fonctions exécutées par le processus père et
l'enchaînement des fonctions exécutées par le processus fils.

processus père processus fils

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


Question 2 :
En exécutant plusieurs fois ce programme, on constate qu'il produit 2
affichages différents.
Donnez ces 2 affichages.

CAS 1 CAS 2
abcdefghij abcdefghij
klmno pqrst
pqrst klmno

Question 3 :
Expliquez comment ces affichages sont produits et pourquoi ils sont
différents.

Le système UNIX ne garantie pas d'ordonnancement particulier entre
processus Père et Fils. Il se peut que l'un des processus soit élu après
que l'autre ait fait le read() mais avant le print(). Il effectuera alors
sa propre séquence read()/print(), mais en ayant eu le pointeur de position
du fichier affecté par le read() de l'autre processus :

Le cas 1 ci dessus correspond à :

père fils ou père fils

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

Le cas 2 ci dessus correspond à :

père fils ou père fils

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




Le programme précédent est modifié dans le but d'utiliser le début du
fichier /usr/toto comme zone de communication entre les 2 processus. Le
processus père sera en charge de lire des données sur un capteur et de les
écrire au début du fichier, et le processus fils sera en charge de lire ces
données en début de fichier puis de les traiter et les afficher. On sait
que le traitement des données est plus long que l'acquisition des données,
et que donc le processus fils ne trouvera pas 2 fois de suite les mêmes
données dans le fichier.

Le programme devient :

main()
{
int PID;
int fd;

fd = open("/user/toto", O_RDWR);

read(fd, buffer, 10);
print(buffer);

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


Question 4 :
En prenant exemple sur la boucle de traitement du processus fils, écrire la
boucle de code du processus père.
Les données seront lues grâce à la fonction lire_capteur(buffer) qui lit 5
caractères et les place dans la variable buffer.

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


Question 5 :
Le code ci dessus ne fonctionne pas bien. En effet, on constate que de
temps en temps, le processus fils ne lit pas le début du fichier
(caractères 0 à 4) mais lit les caractères 5 à 9 du fichier.

Expliquer comment cela est possible.

De la même façon qu'à la question 3, c'est un problème d'ordre d'exécution
des processus père et fils. Si le processus fils perd le processeur aprè