Systemes D’exploitation Exam

Ce document présente un examen sur les systèmes d’exploitation, portant sur la gestion de la mémoire paginée, la gestion dynamique des partitions mémoire, et les algorithmes de remplacement de pages. Il évalue les compétences en calcul d’adressage mémoire, allocation mémoire, et analyse des défauts de page selon différents algorithmes.

Problème No. 1

On considère un système de gestion de mémoire paginée avec une taille de page fixée à 2 KO et une adresse mémoire codée sur 20 bits. Un processus P nécessite 6012 octets de mémoire. La liste des cases libres en mémoire est donnée dans l’ordre : 25, 11, 7, 5, 9, 13. Les pages sont allouées aux cases libres dans cet ordre, en commençant par la tête de liste.

Les questions sont :

• (i) Combien de cases mémoire existe-t-il ?
• (ii) De combien de cases mémoire le processus P a-t-il besoin ?
• (iii) Quelle est la quantité d’espace mémoire gaspillée par le chargement du processus P ?
• (iv) À quelle adresse physique correspond l’adresse virtuelle 5027 générée par le processus P ?

Solution :

(i) Nombre total de cases mémoire

La taille de l’adresse mémoire est de 20 bits, donc l’espace d’adressage total est 2^20 octets = 1 048 576 octets (1 Mo).

La taille d’une page est de 2 KO = 2 048 octets.

Le nombre total de cases mémoire (pages) est donc :

Nombre de cases = 2^20 / 2 048 = 1 048 576 / 2 048 = 512 cases

Réponse : Il y a 512 cases mémoire au total.

(ii) Nombre de cases mémoire nécessaires pour le processus P

Le processus P a besoin de 6012 octets.

Chaque case fait 2048 octets, donc le nombre de cases nécessaires est le plafond de (6012 / 2048) :

6012 / 2048 ≈ 2,936

Arrondi au supérieur, cela donne 3 cases.

Réponse : Le processus P nécessite 3 cases mémoire.

(iii) Espace mémoire gaspillé

L’espace alloué est de 3 cases × 2048 octets = 6144 octets.

Le processus utilise 6012 octets, donc l’espace gaspillé est :

6144 - 6012 = 132 octets

Réponse : L’espace mémoire gaspillé est de 132 octets.

(iv) Adresse physique correspondant à l’adresse virtuelle 5027

On doit déterminer la page virtuelle et l’offset dans cette page pour l’adresse virtuelle 5027.

Calcul de la page virtuelle :

Numéro de page = 5027 divisé par 2048 = 2 (car 2048 × 2 = 4096 et 5027 > 4096)

Offset dans la page :

Offset = 5027 - (2 × 2048) = 5027 - 4096 = 931

La page virtuelle 2 est allouée à la case mémoire numéro 7 (d’après la liste des cases libres : 25, 11, 7, ... la troisième case allouée correspond à la page 2).

Adresse physique :

Adresse physique = (numéro de case × taille de page) + offset = 7 × 2048 + 931 = 14336 + 931 = 15267

Réponse : L’adresse physique correspondant à l’adresse virtuelle 5027 est 15 267.

Problème No. 2

Une mémoire centrale (MC) a initialement une zone libre de 256 KO. Les événements suivants se produisent dans l’ordre :

• Charger le processus P1 (120 KO)
• Charger le processus P2 (30 KO)
• Charger le processus P3 (56 KO)
• Terminer P1
• Terminer P2
• Charger le processus P4 (48 KO)
• Charger le processus P5 (120 KO)

On demande de donner les adresses de chargement des 5 processus en utilisant les méthodes d’allocation dynamique de mémoire : First Fit et Best Fit.

Solution :

Allocation First Fit

On alloue chaque processus dans la première zone libre suffisamment grande.

• P1 (120K) : zone libre initiale de 256K → alloué à l’adresse 0
• P2 (30K) : zone libre restante après P1 est 256K - 120K = 136K → alloué à 120K
• P3 (56K) : zone libre restante après P2 est 136K - 30K = 106K → alloué à 150K (120K + 30K)
• Terminer P1 : libère la zone 0-120K
• Terminer P2 : libère la zone 120K-150K
• P4 (48K) : première zone libre suffisante est 0-120K → alloué à 0
• P5 (120K) : zones libres sont 48K-150K (102K) et 206K-256K (50K) → aucune zone libre assez grande → pas d’espace disponible

Réponse First Fit :

Processus	Adresse
P1	0
P2	120K
P3	150K
P4	0
P5	Pas d’espace

Allocation Best Fit

On alloue chaque processus dans la plus petite zone libre suffisante.

• P1 (120K) : zone libre initiale 256K → alloué à 0
• P2 (30K) : zone libre restante 136K → alloué à 120K
• P3 (56K) : zone libre restante 106K → alloué à 150K
• Terminer P1 : libère 0-120K
• Terminer P2 : libère 120K-150K
• P4 (48K) : zones libres sont 0-120K (120K) et 120K-150K (30K) et 206K-256K (50K) → la plus petite zone suffisante est 206K-256K (50K) → alloué à 206K
• P5 (120K) : zones libres restantes sont 0-120K (120K) et 120K-150K (30K) → la plus petite zone suffisante est 0-120K → alloué à 0

Réponse Best Fit :

Processus	Adresse
P1	0
P2	120K
P3	150K
P4	206K
P5	0

Problème No. 3

Considérer la séquence de référence de pages suivante :

3, 6, 7, 1, 6, 3, 4, 5, 6, 3, 6, 7, 2, 5, 7, 6, 3, 6, 7, 5

On suppose initialement 4 cases mémoire libres.

Les questions sont :

• (a) Combien de défauts de page engendre l’utilisation des algorithmes de remplacement suivants : FIFO, LRU et OPTIMAL ?
• (b) L’un de ces algorithmes engendre-t-il l’anomalie de Belady si le nombre de cases est augmenté à 5 ?

Solution :

(a) Calcul des défauts de page avec 4 cases mémoire

On applique les algorithmes sur la séquence donnée :

• FIFO (First In First Out) :

On remplace la page la plus ancienne en mémoire lors d’un défaut.

Le nombre de défauts de page est calculé à 14.

• LRU (Least Recently Used) :

On remplace la page la moins récemment utilisée.

Le nombre de défauts de page est calculé à 10.

• OPTIMAL :

On remplace la page qui ne sera pas utilisée pendant le plus long temps à venir.

Le nombre de défauts de page est calculé à 8.

(b) Anomalie de Belady avec 5 cases mémoire

L’anomalie de Belady correspond à une situation où augmenter le nombre de cases mémoire augmente le nombre de défauts de page.

Dans ce cas, aucun des algorithmes (FIFO, LRU, OPTIMAL) n’engendre l’anomalie de Belady lorsque le nombre de cases passe à 5.

Réponse : Non, aucun algorithme ne présente l’anomalie de Belady avec 5 cases.

Méthode

Ce sujet récompense une bonne maîtrise des concepts fondamentaux de la gestion mémoire en systèmes d’exploitation :

• Pour la pagination, il faut savoir calculer le nombre de pages, comprendre la correspondance entre adresse virtuelle et adresse physique, et calculer l’espace gaspillé dû à la fragmentation interne.
• Pour l’allocation dynamique, il faut appliquer rigoureusement les stratégies First Fit et Best Fit en tenant compte des zones libres et des libérations successives.
• Pour les algorithmes de remplacement de pages, il faut simuler précisément la séquence de pages, suivre l’état des cases mémoire, et compter les défauts de page.
• Il est important de ne pas confondre les algorithmes et de bien comprendre la notion d’anomalie de Belady.

Les erreurs fréquentes pénalisées sont :

• Confondre taille de page et nombre de pages.
• Ne pas arrondir correctement le nombre de pages nécessaires.
• Oublier de calculer l’offset dans l’adresse virtuelle.
• Mal appliquer les règles d’allocation mémoire (ne pas respecter l’ordre ou la taille des zones libres).
• Ne pas simuler correctement les algorithmes de remplacement, notamment en oubliant de mettre à jour les cases mémoire après chaque accès.