Exercice Systèmes d’Exploitation Corrigé

Exercice Corrigé – Gestion de la mémoire – Partie 3

octobre 28, 2024octobre 28, 2024 Thomas Aucun commentaire

La gestion de la mémoire est à la base des systèmes d’exploitation. Parmi les techniques fondamentales, la pagination et la segmentation jouent un rôle crucial dans l’optimisation de l’utilisation de la mémoire physique et virtuelle. La pagination permet de diviser la mémoire en blocs de taille fixe, facilitant ainsi le partage et l’allocation efficace des ressources. En parallèle, la segmentation offre une approche plus flexible en organisant la mémoire en segments de taille variable, reflétant la structure logique des programmes. Ensemble, ces mécanismes permettent d’implémenter la mémoire virtuelle, qui étend l’espace d’adressage disponible et améliore la performance des applications. Ici, nous allons voir des exercices corrigés qui illustreront ces concepts clés, en vous aidant à mieux comprendre comment la gestion de la mémoire contribue à la performance des systèmes d’exploitation.

Exercice 1: Questions de base

1.1) Quelle est la cause d’une exception de défaut de page (page fault) ?

Une exception de défaut de page se produit lorsqu’un processus tente d’accéder à une page qui n’est pas présente dans la mémoire centrale physique.

Explication: Cela signifie que la page requise a été déplacée vers le disque (swapping) ou n’a jamais été chargée en mémoire.
Conséquence: Le système d’exploitation doit alors gérer cette situation en récupérant la page depuis le disque et en la chargeant en mémoire.

En générale, un défaut de page est causé par une tentative d’accès à une page absente de la mémoire physique.

1.2) Quelle est la réaction du système d’exploitation lorsqu’une exception de défaut de page se produit ?

Lorsque le système d’exploitation détecte un défaut de page, il exécute les étapes suivantes:

Allouer la page: Utilise le contrôleur et le pilote de périphérique pour identifier et préparer la page dans la mémoire d’échange (disque SSD/HDD).
Copier la page: Transfère la page demandée depuis le disque vers une page libre dans la mémoire principale.
Mettre à jour la table des pages: Actualise la table des pages pour refléter la nouvelle localisation de la page.
Rendre le contrôle au processus: Renvoie le contrôle au processus qui avait provoqué le défaut de page.
Réexécution: Le processus tente à nouveau d’exécuter l’instruction qui a causé le défaut de page.

En générale, le système d’exploitation gère le défaut de page en récupérant la page manquante et en mettant à jour les informations nécessaires, permettant ainsi la continuation de l’exécution du processus.

1.3) Quelle est la cause d’une exception de violation d’accès ou d’une exception d’erreur de protection générale ?

Une exception de violation d’accès (ou erreur de protection générale) se produit lorsque:

Tentative d’accès non autorisé: Un processus essaie d’accéder à une adresse de mémoire virtuelle pour laquelle il n’a pas les permissions appropriées.

En générale, une exception de violation d’accès est causée par une tentative d’accès à une mémoire virtuelle non autorisée par un processus.

1.4) Quelle est la conséquence (effet) d’une exception de violation d’accès ou d’une exception d’erreur de protection générale ?

Le système d’exploitation utilise des mécanismes de protection pour empêcher les processus d’accéder à la mémoire d’autres processus ou à des zones de mémoire réservées.

Conséquence: Cette exception provoque généralement l’arrêt du processus en question ou la génération d’un message d’erreur, garantissant ainsi la sécurité et la stabilité du système. Dans certains anciens systèmes d’exploitation Windows, les erreurs de segmentation provoquaient souvent des pannes de système et un écran bleu. Sous Linux, le signal SIGSEGV est renvoyé comme résultat.

1.5) Lorsque le partitionnement statique est utilisé, une fragmentation interne se produit. [Vrai/Faux].

Vrai. Lorsque le partitionnement statique est utilisé, une fragmentation interne peut se produire. Cela se produit lorsque la taille d’une partition est supérieure à la taille des données qu’elle contient, laissant ainsi des espaces inutilisés au sein de la partition.

1.6) Lorsque le partitionnement dynamique est utilisé, la fragmentation externe ne peut pas se produire. [Vrai/Faux].

Faux. Lorsque le partitionnement dynamique est utilisé, la fragmentation externe peut se produire. Cela se produit lorsque des espaces libres de mémoire sont dispersés, rendant difficile l’allocation de blocs de mémoire contigus pour de nouveaux processus, même si suffisamment d’espace est disponible au total.

1.7) Avec la pagination, toutes les pages ont la même taille. [Vrai/Faux].

Vrai. Avec la pagination, toutes les pages ont la même taille. Cela permet une gestion uniforme de la mémoire, simplifiant la translation des adresses et l’allocation des ressources.

1.8) L’un des avantages des pages longues est la faible fragmentation interne. [Vrai/Faux].

Faux. L’un des inconvénients des pages longues est généralement une plus grande fragmentation interne. En effet, si la taille d’une page est supérieure aux besoins d’un processus, cela entraîne plus d’espace inutilisé à l’intérieur de la page.

1.9) L’inconvénient des pages courtes est que la table des pages s’agrandit. [Vrai/Faux].

Vrai. L’inconvénient des pages courtes est que la table des pages peut s’agrandir. Comme chaque page nécessite une entrée dans la table des pages, un nombre accru de pages (en raison de la taille réduite des pages) entraîne une table plus volumineuse, ce qui peut affecter la performance et la consommation de mémoire.

1.10) Lorsque la pagination est utilisée, le MMU traduit les adresses de la mémoire logique en adresses de la mémoire physique. [Vrai/Faux].

Vrai. Lorsque la pagination est utilisée, l’unité de gestion de la mémoire (MMU) traduit les adresses de la mémoire logique (virtuelle) en adresses de la mémoire physique en utilisant des tables de pages.

1.11) Les systèmes d’exploitation modernes (pour x86) fonctionnent en mode protégé et n’utilisent que la pagination. [Vrai/Faux].

Faux. Les systèmes d’exploitation modernes pour x86 fonctionnent en mode protégé, mais ils n’utilisent pas uniquement la pagination. Ils peuvent également utiliser d’autres techniques de gestion de la mémoire, telles que la segmentation, souvent en combinaison avec la pagination.

Exercice 2:

Pourquoi est-il impossible de mettre en œuvre la stratégie de remplacement optimal OPT ?

Raison: Il est impossible de mettre en œuvre la stratégie de remplacement optimal (OPT) car il n’est pas possible de prédire l’avenir. En effet, la séquence des demandes futures de pages est inconnue, ce qui rend impossible de savoir à l’avance quelle page sera la moins utilisée. Cette imprévisibilité empêche l’application pratique de la stratégie OPT dans un système réel.

Exercice 3:

Considérons une chaîne de référence: 6, 7, 8, 9, 6, 7, 1, 6, 7, 8, 9, 1. Le nombre de cadres dans la mémoire est de 3. Trouvez le nombre de défauts de page, en utilisant l’algorithme de remplacement de page FIFO.

Algorithme de remplacement de page FIFO:

FIFO est l’un des algorithmes les plus simples, où la première page à entrer dans la mémoire est la première à être remplacée. Cet algorithme ne prend pas en compte l’utilisation des pages, ce qui peut conduire à des situations où des pages encore souvent utilisées sont remplacées.

+----------------+---+---+---+---+---+---+---+---+---+---+---+---+
| Ref Pages      | 6 | 7 | 8 | 9 | 6 | 7 | 1 | 6 | 7 | 8 | 9 | 1 |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+
| Cadre 3        |   |   | 8 | 8 | 8 | 7 | 7 | 7 | 7 | 7 | 9 | 9 |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+
| Cadre 2        |   | 7 | 7 | 7 | 6 | 6 | 6 | 6 | 6 | 8 | 8 | 8 |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+
| Cadre 1        | 6 | 6 | 6 | 9 | 9 | 9 | 1 | 1 | 1 | 1 | 1 | 1 |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+
| Défaut de page | X | X | X | X | X | X | X |   |   | X | X |   |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+

Comme dans le tableau ci-dessus, il y a 3 cadres dans la mémoire.
6, 7, 8 sont alloués aux emplacements vides car ils ne sont pas en mémoire.
Lorsque le 9 arrive (défaut de page), il remplace le 6 qui est le plus ancien en mémoire ou l’élément avant de la file d’attente.
Lorsque 6 arrive (défaut de page), il remplace 7 qui est la page la plus ancienne en mémoire.
Pareillement, le 7 remplace le 8, le 1 remplace le 9.
Puis vient 6, qui est déjà en mémoire.
Puis vient le 7.
Ensuite, 8 remplace 6, 9 remplace 7. Puis 1 arrive.

Donc nombre de défauts de page = 9

Exercice 4:

Considérons une chaîne de référence: 6, 7, 8, 9, 6, 7, 1, 6, 7, 8, 9, 1, 7, 9, 6. Le nombre de cadres dans la mémoire est de 3. Trouvez le nombre de défauts de page correspondant à:

Algorithme de remplacement de page Optimal (OPT)
Algorithme de remplacement de page LRU

Algorithme de remplacement de page Optimal (OPT):

Cet algorithme remplace la page qui ne sera pas utilisée pendant la plus longue période dans le futur. Bien qu’il offre la meilleure performance théorique, il n’est pas réalisable en pratique, car il nécessite une connaissance future des références de pages.

+----------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Ref Pages      | 6 | 7 | 8 | 9 | 6 | 7 | 1 | 6 | 7 | 8 | 9 | 1 | 7 | 9 | 6 |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Cadre 3        |   |   | 8 | 9 | 9 | 9 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Cadre 2        |   | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Cadre 1        | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 8 | 9 | 9 | 9 | 9 | 6 |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Défaut de page | X | X | X | X |   |   | X |   |   | X | X |   |   |   | X |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Tout d’abord, tous les cadres sont vides. 6, 7, 8 sont attribués aux cadres (défaut de page).
Maintenant, le 9 vient remplacer le 8 car il est le plus loin dans la séquence à venir. Le 6 et le 7 arrivent plus tôt et ne sont donc pas remplacés.
Ensuite, le 6 arrive alors qu’il est déjà présent (saut de page).
Puis le 7 arrive.
Ensuite, le 1 remplace le 9 de la même manière (défaut de page).
Puis 6 arrive, 7 arrive.
Ensuite, 8 remplace 6 (défaut de page) et 9 remplace 8 (défaut de page).
Puis viennent respectivement 1, 7, 9 qui sont déjà présents dans la mémoire.
Ensuite, 6 remplace 9 (défaut de page), il peut également remplacer 7 et 1 car aucune autre page n’est présente dans la séquence à venir.

Le nombre de défauts de page = 8

Algorithme de remplacement de page LRU:

LRU remplace la page qui n’a pas été utilisée pendant la plus longue période de temps. Cet algorithme repose sur l’idée que les pages récemment utilisées sont susceptibles d’être utilisées à nouveau bientôt. LRU peut être implémenté à l’aide de structures de données comme des listes ou des tableaux.

+----------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Ref Pages      | 6 | 7 | 8 | 9 | 6 | 7 | 1 | 6 | 7 | 8 | 9 | 1 | 7 | 9 | 6 |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Cadre 3        |   |   | 8 | 8 | 8 | 7 | 7 | 7 | 7 | 7 | 7 | 1 | 1 | 1 | 6 |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Cadre 2        |   | 7 | 7 | 7 | 6 | 6 | 6 | 6 | 6 | 6 | 9 | 9 | 9 | 9 | 9 |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Cadre 1        | 6 | 6 | 6 | 9 | 9 | 9 | 1 | 1 | 1 | 8 | 8 | 8 | 7 | 7 | 7 |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Défaut de page | X | X | X | X | X | X | X |   |   | X | X | X | X |   | X |
+----------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

Tout d’abord, tous les cadres sont vides. 6, 7, 8 sont attribués aux cadres (Défaut de page).
Ensuite, 9 vient remplacer 6 qui est utilisé le plus tôt (Défaut de page).
Ensuite, 6 remplace 7, 7 remplace 8, 1 remplace 9 (Défaut de page).
Puis vient le 6 qui est déjà présent.
Puis vient le 7.
Ensuite, 8 remplace 1, 9 remplace 6, 1 remplace 7, et 7 remplace 8 (Défaut de page).
Puis 9 arrive (Page Hit).
Puis 6 remplace 1 (Défaut de page).

Le nombre de défauts de page = 12

Exercice 5:

Considérons une chaîne de référence: 4, 7, 6, 1, 7, 6, 1, 2, 7, 2. Le nombre de cadres dans la mémoire est de 3. Trouvez le nombre de défauts de page correspondant à:

Algorithme de remplacement de page Optimal (OPT)
Algorithme de remplacement de page FIFO
Algorithme de remplacement de page LRU

Algorithme de remplacement de page Optimal (OPT):

+----------------+----+----+----+----+----+----+----+----+----+----+
| Ref Pages      | 4  | 7  | 6  | 1  | 7  | 6  | 1  | 2  | 7  | 2  |
+----------------+----+----+----+----+----+----+----+----+----+----+
| Cadre 3        |    |    | 6  | 6  | 6  | 6  | 6  | 2  | 2  | 2  |
+----------------+----+----+----+----+----+----+----+----+----+----+
| Cadre 2        |    | 7  | 7  | 7  | 7  | 7  | 7  | 7  | 7  | 7  |
+----------------+----+----+----+----+----+----+----+----+----+----+
| Cadre 1        | 4  | 4  | 4  | 1  | 1  | 1  | 1  | 1  | 1  | 1  |
+----------------+----+----+----+----+----+----+----+----+----+----+
| Défaut de page | X  | X  | X  | X  |    |    |    | X  |    |    |
+----------------+----+----+----+----+----+----+----+----+----+----+

Nombre de défauts de page dans l'algorithme de remplacement optimal des pages = 5

Algorithme de remplacement de page LRU:

+----------------+----+----+----+----+----+----+----+----+----+----+
| Ref Pages      | 4  | 7  | 6  | 1  | 7  | 6  | 1  | 2  | 7  | 2  |
+----------------+----+----+----+----+----+----+----+----+----+----+
| Cadre 3        |    |    | 6  | 6  | 6  | 6  | 6  | 6  | 7  | 7  |
+----------------+----+----+----+----+----+----+----+----+----+----+
| Cadre 2        |    | 7  | 7  | 7  | 7  | 7  | 7  | 2  | 2  | 2  |
+----------------+----+----+----+----+----+----+----+----+----+----+
| Cadre 1        | 4  | 4  | 4  | 1  | 1  | 1  | 1  | 1  | 1  | 1  |
+----------------+----+----+----+----+----+----+----+----+----+----+
| Défaut de page | X  | X  | X  | X  |    |    |    | X  | X  |    |
+----------------+----+----+----+----+----+----+----+----+----+----+

Nombre de défauts de page dans l'algorithme de remplacement LRU = 6

Algorithme de remplacement de page FIFO:

+----------------+----+----+----+----+----+----+----+----+----+----+
| Ref Pages      | 4  | 7  | 6  | 1  | 7  | 6  | 1  | 2  | 7  | 2  |
+----------------+----+----+----+----+----+----+----+----+----+----+
| Cadre 3        |    |    | 6  | 6  | 6  | 6  | 6  | 6  | 7  | 7  |
+----------------+----+----+----+----+----+----+----+----+----+----+
| Cadre 2        |    | 7  | 7  | 7  | 7  | 7  | 7  | 2  | 2  | 2  |
+----------------+----+----+----+----+----+----+----+----+----+----+
| Cadre 1        | 4  | 4  | 4  | 1  | 1  | 1  | 1  | 1  | 1  | 1  |
+----------------+----+----+----+----+----+----+----+----+----+----+
| Défaut de page | X  | X  | X  | X  |    |    |    | X  | X  |    |
+----------------+----+----+----+----+----+----+----+----+----+----+

Nombre de défauts de page dans l'algorithme de remplacement FIFO = 6

Exercice 6:

Considérons une chaîne de référence: 1, 3, 0, 3, 5, 6, 3. Le nombre de cadres dans la mémoire est de 3. Trouvez le nombre de défauts de page, en utilisant l’algorithme de remplacement de page FIFO.

+----------------+----+----+----+----+----+----+----+
| Ref Pages      | 1  | 3  | 0  | 3  | 5  | 6  | 3  |
+----------------+----+----+----+----+----+----+----+
| Cadre 3        |    |    | 0  | 0  | 0  | 0  | 3  |
+----------------+----+----+----+----+----+----+----+
| Cadre 2        |    | 3  | 3  | 3  | 3  | 6  | 6  |
+----------------+----+----+----+----+----+----+----+
| Cadre 1        | 1  | 1  | 1  | 1  | 5  | 5  | 5  |
+----------------+----+----+----+----+----+----+----+
| Défaut de page | X  | X  | X  |    | X  | X  | X  |
+----------------+----+----+----+----+----+----+----+

Nombre de défauts de page = 6

Au début, tous les emplacements sont vides, donc quand 1, 3, 0 arrivent, ils sont alloués aux emplacements vides -> 3 défauts de page.
Lorsque 3 arrive, il est déjà en mémoire -> 0 défaut de page.
Puis 5 arrive, il n’est pas disponible en mémoire, il remplace donc l’emplacement de page le plus ancien, c’est-à-dire 1 -> 1 Défaut de page.
6 arrive, il n’est pas non plus disponible en mémoire, il remplace donc l’emplacement de page le plus ancien, c’est-à-dire 3 -> 1 Défaut de page.
Enfin, lorsque 3 arrive, il n’est pas disponible et remplace donc 0 -> 1 défaut de page.

Exercice 7:

Considérons une chaîne de référence: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3. Le nombre de cadres dans la mémoire est de 4. Trouvez le nombre de défauts de page correspondant à:

Algorithme de remplacement de page Optimal (OPT)
Algorithme de remplacement de page LRU
Algorithme de remplacement de page Most Recently Used (MRU)

Algorithme de remplacement de page Optimal (OPT):

+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Ref     | 7  | 0  | 1  | 2  | 0  | 3  | 0  | 4  | 2  | 3  | 0  | 3  | 2  | 3  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Cadre 4 |    |    |    | 2  | 2  | 2  | 2  | 2  | 2  | 2  | 2  | 2  | 2  | 2  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Cadre 3 |    |    | 1  | 1  | 1  | 1  | 1  | 4  | 4  | 4  | 4  | 4  | 4  | 4  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Cadre 2 |    | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Cadre 1 | 7  | 7  | 7  | 7  | 7  | 3  | 3  | 3  | 3  | 3  | 3  | 3  | 3  | 3  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Défaut P| X  | X  | X  | X  |    | X  |    | X  |    |    |    |    |    |    |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+

Nombre de défauts de page dans l'algorithme de remplacement optimal(OPT) = 6

Au départ, tous les emplacements sont vides, donc lorsque 7 0 1 2 sont attribués aux emplacements vides -> 4 défauts de page.
0 est déjà là, donc -> 0 défaut de page.
Lorsque 3 arrive, il prend la place de 7 parce qu’il n’est pas utilisé pendant la plus longue période à l’avenir -> 1 défaut de page.
0 est déjà là donc -> 0 défaut de page.
4 prend la place de 1 -> 1 défaut de page.

Algorithme de remplacement de page LRU:

+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Ref     | 7  | 0  | 1  | 2  | 0  | 3  | 0  | 4  | 2  | 3  | 0  | 3  | 2  | 3  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Cadre 4 |    |    |    | 2  | 2  | 2  | 2  | 2  | 2  | 2  | 2  | 2  | 2  | 2  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Cadre 3 |    |    | 1  | 1  | 1  | 1  | 1  | 4  | 4  | 4  | 4  | 4  | 4  | 4  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Cadre 2 |    | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  | 0  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Cadre 1 | 7  | 7  | 7  | 7  | 7  | 3  | 3  | 3  | 3  | 3  | 3  | 3  | 3  | 3  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Défaut P| X  | X  | X  | X  |    | X  |    | X  |    |    |    |    |    |    |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+

Nombre de défauts de page dans l'algorithme de remplacement LRU = 6

Au départ, tous les emplacements sont vides, donc lorsque 7 0 1 2 sont attribués aux emplacements vides -> 4 défauts de page.
0 est déjà leur place -> 0 défaut de page.
Lorsque 3 arrive, il prend la place de 7 parce qu’il est le moins récemment utilisé -> 1 défaut de page.
0 est déjà en mémoire -> 0 défaut de page.
4 prend la place de 1 -> 1 défaut de page.
Maintenant, pour la chaîne de référence de la page suivante -> 0 défaut de page parce qu’elle est déjà disponible dans la mémoire.

Algorithme de remplacement de page MRU:

L’algorithme MRU remplace la page qui a été utilisée le plus récemment. L’idée derrière cet algorithme est que les pages récemment utilisées sont moins susceptibles d’être utilisées à nouveau dans un avenir proche. Bien que cela puisse fonctionner dans certains scénarios, il peut aussi conduire à des performances médiocres dans des cas où les modèles d’accès sont cycliques ou lorsque certaines pages sont nécessaires peu après leur utilisation.

+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Ref     | 7  | 0  | 1  | 2  | 0  | 3  | 0  | 4  | 2  | 3  | 0  | 3  | 2  | 3  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Cadre 4 |    |    |    | 2  | 2  | 2  | 2  | 2  | 2  | 3  | 0  | 3  | 2  | 3  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Cadre 3 |    |    | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Cadre 2 |    | 0  | 0  | 0  | 0  | 3  | 0  | 4  | 4  | 4  | 4  | 4  | 4  | 4  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Cadre 1 | 7  | 7  | 7  | 7  | 7  | 7  | 7  | 7  | 7  | 7  | 7  | 7  | 7  | 7  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| Défaut P| X  | X  | X  | X  |    | X  | X  | X  |    | X  | X  | X  | X  | X  |
+---------+----+----+----+----+----+----+----+----+----+----+----+----+----+----+

Nombre de défauts de page dans l'algorithme de remplacement MRU = 12

Au départ, tous les emplacements sont vides, donc lorsque 7 0 1 2 sont attribués aux emplacements vides -> 4 défauts de page.
0 est déjà leur place donc -> 0 défaut de page.
lorsque 3 arrive, il prendra la place de 0 car il est le plus récemment utilisé -> 1 défaut de page.
lorsque 0 arrivera, il prendra la place de 3 -> 1 défaut de page.
lorsque 4 arrive, il prendra la place de 0 -> 1 défaut de page.
2 est déjà en mémoire donc -> 0 défaut de page.
lorsque 3 arrive, il prendra la place de 2 -> 1 défaut de page.
lorsque 0 arrive, il prend la place de 3 -> 1 défaut de page.
lorsque 3 arrivera, il prendra la place de 0 -> 1 défaut de page.
lorsque le 2 arrive, il prend la place du 3 -> 1 défaut de page.
lorsque 3 arrivera, il prendra la place de 2 -> 1 défaut de page.

Exercice 8:

Considérons une chaîne de référence: 5, 0, 1, 0, 2, 3, 0, 2, 4, 3, 3, 2, 0, 2, 1, 2, 7, 0, 1, 1, 0. Le nombre de cadres dans la mémoire est de 3. Trouvez le nombre et le taux de défauts de page correspondant à:

Algorithme de remplacement de page Optimal (OPT)
Algorithme de remplacement de page FIFO
Algorithme de remplacement de page LRU

Algorithme de remplacement de page FIFO:

+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|Rf| 5 | 0 | 1 | 0 | 2 | 3 | 0 | 2 | 4 | 3 | 3 | 2 | 0 | 2 | 1 | 2 | 7 | 0 | 1 | 1 | 0 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C3|   |   | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C2|   | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 2 | 0 | 0 | 0 | 0 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C1| 5 | 5 | 5 | 5 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 7 | 7 | 7 | 7 | 7 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|DP| X | X | X |   | X | X | X |   | X |   |   | X |   |   | X |   | X | X |   |   |   |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Nombre de défauts de page = 11

Taux de défaut de page = Nombre de défauts de page/Nombre de cadres
                       = 11/3 
                       = 3.6

Algorithme de remplacement de page LRU:

+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|Rf| 5 | 0 | 1 | 0 | 2 | 3 | 0 | 2 | 4 | 3 | 3 | 2 | 0 | 2 | 1 | 2 | 7 | 0 | 1 | 1 | 0 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C3|   |   | 1 | 1 | 1 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 0 | 0 | 0 | 0 | 7 | 7 | 7 | 7 | 7 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C2|   | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C1| 5 | 5 | 5 | 5 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|DP| X | X | X |   | X | X |   |   | X | X |   |   | X |   | X |   | X | X | X |   |   |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Nombre de défauts de page = 12

Taux de défaut de page = Nombre de défauts de page/Nombre de cadres
                       = 12/3 
                       = 4

Algorithme de remplacement de page Optimal (OPT):

+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|Rf| 5 | 0 | 1 | 0 | 2 | 3 | 0 | 2 | 4 | 3 | 3 | 2 | 0 | 2 | 1 | 2 | 7 | 0 | 1 | 1 | 0 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C3|   |   | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C2|   | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C1| 5 | 5 | 5 | 5 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 7 | 7 | 7 | 7 | 7 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|DP| X | X | X |   | X | X |   |   | X |   |   |   | X |   | X |   | X |   |   |   |   |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Nombre de défauts de page = 9

Taux de défaut de page = Nombre de défauts de page/Nombre de cadres
                       = 9/3 
                       = 3

Exercice 9:

Considérons une chaîne de référence: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. Le nombre de cadres dans la mémoire est de 4. Trouvez le nombre et le taux de défauts de page correspondant à:

Algorithme de remplacement de page Optimal (OPT)
Algorithme de remplacement de page FIFO
Algorithme de remplacement de page LRU

Algorithme de remplacement de page FIFO:

+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|Rf| 1 | 2 | 3 | 4 | 2 | 1 | 5 | 6 | 2 | 1 | 2 | 3 | 7 | 6 | 3 | 2 | 1 | 2 | 3 | 6 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C4|   |   |   | 4 | 4 | 4 | 4 | 4 | 4 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C3|   |   | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C2|   | 2 | 2 | 2 | 2 | 2 | 2 | 6 | 6 | 6 | 6 | 6 | 7 | 7 | 7 | 7 | 7 | 7 | 3 | 3 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C1| 1 | 1 | 1 | 1 | 1 | 1 | 5 | 5 | 5 | 5 | 5 | 3 | 3 | 3 | 3 | 3 | 1 | 1 | 1 | 1 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|DP| X | X | X | X |   |   | X | X | X | X |   | X | X | X |   | X | X |   | X |   |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Nombre de défauts de page = 14

Taux de défaut de page = Nombre de défauts de page/Nombre de cadres
                       = 14/4 
                       = 3.5

Algorithme de remplacement de page LRU:

+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|Rf| 1 | 2 | 3 | 4 | 2 | 1 | 5 | 6 | 2 | 1 | 2 | 3 | 7 | 6 | 3 | 2 | 1 | 2 | 3 | 6 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C4|   |   |   | 4 | 4 | 4 | 4 | 6 | 6 | 6 | 6 | 6 | 7 | 7 | 7 | 7 | 1 | 1 | 1 | 1 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C3|   |   | 3 | 3 | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C2|   | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C1| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|DP| X | X | X | X |   |   | X | X |   |   |   | X | X | X |   |   | X |   |   |   |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Nombre de défauts de page = 10

Taux de défaut de page = Nombre de défauts de page/Nombre de cadres
                       = 10/4 
                       = 2.5

Algorithme de remplacement de page Optimal (OPT):

+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|Rf| 1 | 2 | 3 | 4 | 2 | 1 | 5 | 6 | 2 | 1 | 2 | 3 | 7 | 6 | 3 | 2 | 1 | 2 | 3 | 6 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C4|   |   |   | 4 | 4 | 4 | 5 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C3|   |   | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C2|   | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|C1| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 7 | 7 | 7 | 7 | 1 | 1 | 1 | 1 |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|DP| X | X | X | X |   |   | X | X |   |   |   |   | X |   |   |   | X |   |   |   |
+--+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Nombre de défauts de page = 8

Taux de défaut de page = Nombre de défauts de page/Nombre de cadres
                       = 8/4 
                       = 2

QCMs qui pourraient vous intéresser :

Exercice 1: Questions de base

Exercice 2:

Exercice 3:

Exercice 4:

Exercice 5:

Exercice 6:

Exercice 7:

Exercice 8:

Exercice 9:

Vous pourrez aussi aimer

Exercice Corrigé Gestion Des Processus Linux – Partie 5

Exercice Corrigé Ordonnancement Des Processus – Partie 2

Exercice Corrigé – Gestion de la mémoire – Partie 1

Laisser un commentaire Annuler la réponse