Programmation Système

Ce sujet porte sur la programmation système et propose un contrôle portant sur la gestion de la mémoire virtuelle et la création de processus. Il évalue les compétences en compréhension des mécanismes de mémoire virtuelle, en gestion des processus, en synchronisation et en communication inter-processus.

Exercice A - Problème de mémoire virtuelle

Question 1

Il s'agit de compléter un tableau indiquant, pour des adresses virtuelles et physiques de 8, 16 ou 32 bits, le nombre de bits pour coder le numéro de page virtuelle, la taille d'une page physique et la taille maximale de la mémoire physique du processus.

On sait que la table des pages contient 8 entrées, donc 3 bits pour numéroter les entrées (car 2^3 = 8). La taille d'une page physique correspond à la taille adressable par le nombre de bits restants après avoir retiré les bits de numéro de page.

• Pour 8 bits d'adresse virtuelle :
• Nombre total de bits : 8
• Nombre de bits pour numéro de page virtuelle : 3 (car 8 entrées dans la table des pages)
• Donc, taille d'une page physique = 2^(8 - 3) = 2^5 = 32 octets
• Taille maximum de mémoire physique = nombre d'entrées × taille d'une page = 8 × 32 = 256 octets
• Pour 16 bits d'adresse virtuelle :
• Nombre total de bits : 16
• Nombre de bits pour numéro de page virtuelle : 3 (table limitée à 8 entrées)
• Taille d'une page physique = 2^(16 - 3) = 2^13 = 8192 octets
• Taille maximum de mémoire physique = 8 × 8192 = 65536 octets (64 Ko)
• Pour 32 bits d'adresse virtuelle :
• Nombre total de bits : 32
• Nombre de bits pour numéro de page virtuelle : 3
• Taille d'une page physique = 2^(32 - 3) = 2^29 = 536870912 octets (512 Mo)
• Taille maximum de mémoire physique = 8 × 536870912 = 4294967296 octets (4 Go)

Bits adresse	Nombre bits numéro page virtuelle	Taille page physique (octets)	Taille max mémoire physique (octets)
8	3	32	256
16	3	8192	65536
32	3	536870912	4294967296

Réponse finale : Le nombre de bits pour coder le numéro de page virtuelle est 3 dans tous les cas, la taille d'une page physique est 32 octets pour 8 bits, 8192 octets pour 16 bits, 536870912 octets pour 32 bits, et la taille maximale de mémoire physique est respectivement 256 octets, 65536 octets et 4294967296 octets.

Question 2

On doit déterminer les adresses physiques correspondant à 16 adresses virtuelles données, en mode 8 bits, à partir de la table des pages fournie.

La table des pages (8 entrées) est :

Index	Présente	Modifiée	Accédée	Numéro page physique
0	1	0	1	7
1	1	0	1	6
2	1	0	1	5
3	1	1	1	4
4	1	1	1	3
5	0	0	0	0
6	0	0	0	0
7	0	0	0	0

En mode 8 bits, l'adresse virtuelle est codée sur 8 bits. Le numéro de page virtuelle est codé sur 3 bits (bits de poids fort), et le décalage (offset) sur 5 bits (bits de poids faible). La taille d'une page est donc 2^5 = 32 octets.

Pour chaque adresse virtuelle, on décompose :

• Numéro de page virtuelle (bits 7 à 5) : adresse virtuelle >> 5
• Offset dans la page (bits 4 à 0) : adresse virtuelle & 0x1F

Si la page est présente (bit présente = 1), l'adresse physique est :

adresse physique = (numéro page physique << 5) + offset

Sinon, il n'y a pas d'adresse physique correspondante (page absente).

Adresse virtuelle	Numéro page virtuelle	Offset	Présente ?	Adresse physique
0x00	0	0	Oui	(7 << 5) + 0 = 224
0x11 (17)	0	17	Oui	224 + 17 = 241
0x22 (34)	1	2	Oui	(6 << 5) + 2 = 192 + 2 = 194
0x33 (51)	1	19	Oui	192 + 19 = 211
0x44 (68)	2	4	Oui	(5 << 5) + 4 = 160 + 4 = 164
0x55 (85)	2	21	Oui	160 + 21 = 181
0x66 (102)	3	6	Oui	(4 << 5) + 6 = 128 + 6 = 134
0x77 (119)	3	23	Oui	128 + 23 = 151
0x88 (136)	4	8	Oui	(3 << 5) + 8 = 96 + 8 = 104
0x99 (153)	4	25	Oui	96 + 25 = 121
0xAA (170)	5	10	Non	Pas d'adresse physique (page absente)
0xBB (187)	5	27	Non	Pas d'adresse physique
0xCC (204)	6	12	Non	Pas d'adresse physique
0xDD (221)	6	29	Non	Pas d'adresse physique
0xEE (238)	7	14	Non	Pas d'adresse physique
0xFF (255)	7	31	Non	Pas d'adresse physique

Réponse finale : Les adresses physiques existent pour les pages 0 à 4 uniquement, calculées comme (numéro page physique << 5) + offset. Pour les adresses virtuelles 0xAA et suivantes, la page n'est pas présente, donc pas d'adresse physique correspondante.

Question 3

Un processus accède successivement aux pages 0, 1, 4, 2, 0, 1, 3, 0, 1, 4, 2, 3. Il y a 3 pages libres en mémoire physique. L'algorithme de remplacement est FIFO. On doit donner la suite des pages présentes en mémoire et calculer le nombre de défauts de pages.

On procède étape par étape :

Accès	Page demandée	Pages en mémoire (ordre FIFO)	Défaut de page ?
1	0	[0]	Oui (mémoire vide)
2	1	[0,1]	Oui
3	4	[0,1,4]	Oui
4	2	[1,4,2]	Oui (remplace 0)
5	0	[4,2,0]	Oui (remplace 1)
6	1	[2,0,1]	Oui (remplace 4)
7	3	[0,1,3]	Oui (remplace 2)
8	0	[0,1,3]	Non (présente)
9	1	[0,1,3]	Non
10	4	[1,3,4]	Oui (remplace 0)
11	2	[3,4,2]	Oui (remplace 1)
12	3	[3,4,2]	Non

Nombre total de défauts de pages : 9 (accès 1 à 7, 10 et 11).

Maintenant, si 4 pages libres sont disponibles :

Accès	Page demandée	Pages en mémoire (FIFO)	Défaut de page ?
1	0	[0]	Oui
2	1	[0,1]	Oui
3	4	[0,1,4]	Oui
4	2	[0,1,4,2]	Oui
5	0	[0,1,4,2]	Non
6	1	[0,1,4,2]	Non
7	3	[1,4,2,3]	Oui (remplace 0)
8	0	[4,2,3,0]	Oui (remplace 1)
9	1	[2,3,0,1]	Oui (remplace 4)
10	4	[3,0,1,4]	Oui (remplace 2)
11	2	[0,1,4,2]	Oui (remplace 3)
12	3	[1,4,2,3]	Oui (remplace 0)

Nombre total de défauts de pages : 9 également.

Observation : Le nombre de défauts de pages est identique avec 3 ou 4 pages libres dans ce cas précis, ce qui illustre un phénomène connu sous le nom d'anomalie de Belady où augmenter le nombre de cadres mémoire ne réduit pas forcément le nombre de défauts.

Question 4

Une personne propose d'utiliser les bits libres dans une entrée de table des pages codée sur moins de 8 bits pour coder le numéro de page physique. Il faut expliquer en 3 lignes l'effet de cette possibilité et dire si c'est réaliste.

Explication :

• Utiliser les bits libres pour coder le numéro de page physique permettrait de réduire la taille mémoire nécessaire pour stocker une entrée de table des pages.
• Cela pourrait augmenter le nombre de pages gérées ou réduire la mémoire utilisée par la table.
• Cependant, cette optimisation est peu réaliste car les bits libres sont souvent réservés à d'autres usages (flags, protection) et le numéro de page physique doit être codé sur un nombre fixe de bits pour adresser toute la mémoire physique.

Réponse finale : Cette optimisation réduit la taille des entrées mais est peu réaliste car elle limite la capacité d'adressage et peut interférer avec les bits de contrôle nécessaires.

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

Question 1

Donner l'enchaînement des fonctions exécutées par le processus père et le processus fils dans le programme donné.

Le programme :

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);
 }
}

Enchaînement père :

• open()
• read(fd, buffer, 10)
• print(buffer)
• fork()
• read(fd, buffer, 5)
• print(buffer)

Enchaînement fils :

• open() est partagé (pas appelé par le fils, héritage du descripteur)
• read(fd, buffer, 10) est fait avant fork(), donc déjà fait
• fork()
• read(fd, buffer, 5)
• print(buffer)

Réponse finale : Le père exécute open(), read(10), print, fork(), read(5), print. Le fils hérite du fd ouvert, exécute read(5), print après fork().

Question 2

Donner les deux affichages différents produits par plusieurs exécutions du programme.

Le fichier contient : "abcdefghijklmnopqrst"

Après le premier read(fd, buffer, 10), buffer contient "abcdefghij" (les 10 premiers caractères).

Ensuite, père et fils lisent chacun 5 caractères successifs à partir de la position actuelle du fichier (partagée).

Deux cas possibles selon l'ordre d'exécution :

• Cas 1 : Père lit d'abord 5 caractères ("klmno"), puis fils lit les 5 suivants ("pqrst").
• Affichage père : "abcdefghij" puis "klmno"
• Affichage fils : "pqrst"
• Cas 2 : Fils lit d'abord 5 caractères ("klmno"), puis père lit les 5 suivants ("pqrst").
• Affichage fils : "klmno"
• Affichage père : "pqrst"

Réponse finale : Les deux affichages possibles sont :

• "abcdefghij" puis "klmno" (père) et "pqrst" (fils)
• "abcdefghij" puis "pqrst" (père) et "klmno" (fils)

Question 3

Expliquer comment ces affichages sont produits et pourquoi ils diffèrent.

Le descripteur de fichier est partagé entre père et fils, donc la position de lecture est commune. Selon l'ordre d'exécution, soit le père lit en premier 5 caractères, soit le fils. Cela modifie la position du fichier avant la lecture du second processus, ce qui explique les deux affichages différents.

Réponse finale : Le partage du descripteur de fichier entraîne une position de lecture commune. L'ordre d'exécution non déterministe entre père et fils provoque des lectures différentes et donc deux affichages possibles.

Question 4

Écrire la boucle de code du processus père, en s'inspirant de la boucle du fils, pour lire des données via lire_capteur(buffer) et les écrire au début du fichier.

La boucle du fils est :

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

La boucle du père doit :

• lire 5 caractères du capteur dans buffer (lire_capteur(buffer))
• se positionner au début du fichier (lseek(fd, 0, SEEK_SET))
• écrire les 5 caractères dans le fichier (write(fd, buffer, 5))
• répéter indéfiniment

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

Réponse finale : La boucle du père est :

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

Question 5

Expliquer pourquoi le fils lit parfois les caractères 5 à 9 du fichier au lieu des caractères 0 à 4, identifier la ou les sections critiques et proposer une solution avec sémaphores.

Explication :

• Le père et le fils utilisent le même descripteur de fichier, donc la position du fichier est partagée.
• Le père fait lseek(fd, 0, SEEK_SET) avant write, mais le fils fait aussi lseek(fd, 0, SEEK_SET) avant read.
• Si le père écrit et modifie la position pendant que le fils lit, il peut arriver que le fils lise à partir d'une position incorrecte (par exemple après l'écriture partielle).
• La section critique est l'accès concurrent au fichier (lseek + read/write) sans synchronisation.

Solution avec sémaphores :

• Initialiser un sémaphore (ex : sem) à 1 avec init(sem)
• Avant chaque accès critique (lseek + read ou lseek + write), faire P(sem) pour verrouiller
• Après l'accès, faire V(sem) pour libérer

Exemple pour le père :

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

Pour le fils :

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

Réponse finale : Le problème vient du partage de la position du fichier sans synchronisation. La section critique est l'accès au fichier (lseek + read/write). La solution est d'utiliser un sémaphore pour protéger ces accès critiques avec P(sem) avant et V(sem) après.

Question 6

Proposer les modifications pour que les deux boucles infinies s'arrêtent à la réception du signal SIG_USR1.

Proposition :

• Définir un flag global volatile, par exemple volatile int stop = 0;
• Installer un gestionnaire de signal pour SIG_USR1 qui met stop = 1;
• Modifier les boucles infinies pour qu'elles s'arrêtent lorsque stop == 1;

Exemple :

volatile int stop = 0;

void handler(int sig) {
 stop = 1;
}

int main() {
 signal(SIG_USR1, handler);

 // boucle père
 do {
  P(sem);
  lire_capteur(buffer);
  lseek(fd, 0, SEEK_SET);
  write(fd, buffer, 5);
  V(sem);
 } while (!stop);

 // boucle fils
 do {
  P(sem);
  lseek(fd, 0, SEEK_SET);
  count = read(fd, buffer, 5);
  V(sem);
  if (count == 5) {
   traiter_données(buffer);
   print(buffer);
  }
 } while (!stop);

 return 0;
}

Réponse finale : Il faut installer un gestionnaire pour SIG_USR1 qui modifie un flag global. Les boucles doivent tester ce flag et s'arrêter lorsque le signal est reçu.

Méthode

Ce sujet récompense la rigueur dans la compréhension des mécanismes de mémoire virtuelle, notamment la décomposition des adresses virtuelles en numéro de page et offset, et la traduction via la table des pages. Il faut montrer clairement les étapes de calcul et vérifier la présence des pages.

Pour la gestion des processus, il est essentiel de comprendre le partage des descripteurs de fichiers et l'impact sur la position de lecture. La synchronisation est un point clé, notamment la protection des sections critiques avec sémaphores. Le sujet sanctionne les oublis de synchronisation ou les confusions entre processus père et fils.

Enfin, la gestion des signaux impose de manipuler des variables volatiles et des gestionnaires de signaux, avec une boucle conditionnée par un flag. Omettre cette condition ou ne pas installer le gestionnaire est pénalisé.