FICHE TD 2 Le nombre total de nœuds nécessaires serait égal au nombre total de segments

1. La fraction de temps CPU perdue est de 50% * 4 = 200%. de 64 Ko.

Cela signifie que le temps CPU est perdu deux fois plus que le temps total - Le nombre total de segments de 64 Ko serait de 128 Mo / (64 * 2^10) octets.
disponible Par conséquent, la taille de stockage nécessaire pour une liste chaînée serait de
2. Pour compacter 128 Mo, il faut d'abord calculer le nombre de mots [(32 + 16 + 16) * nombre total de segments de 64 Ko] bits.
mémoire dans 128 Mo. 128 Mo est égal à 134,217,728 octets. Maintenant, pour déterminer quelle méthode est la meilleure, nous devons
Le nombre de mots mémoire dans 128 Mo est de 134,217,728 / 4 = 33,554,432. comparer les tailles de stockage nécessaires pour chaque méthode.
Le temps processeur nécessaire pour compacter 128 Mo est de : Comparaison :
temps processeur = nombre de mots mémoire * temps de lecture/écriture par - Table de bits : (128 Mo / n) bits
mot - Liste chaînée : [(32 + 16 + 16) * nombre total de segments de 64 Ko] bits
temps processeur = (33,554,432) * (10 ns) Pour déterminer laquelle est la meilleure, nous devons évaluer les deux
<=> (33,554,432) * (10 * 10^-9 s) méthodes en fonction du contexte d'utilisation spécifique, des contraintes de
<=> (33,554,432) * (10^-8 s) mémoire et des opérations requises. La méthode la plus efficace dépendra de ces
<=> (33,554,432) * (10^-8 s) facteurs.
temps processeur = 0,33554432 s
Ainsi, le temps processeur nécessaire pour compacter 128 Mo est d'environ 4. FIRST BEST WORST NEXT FIT
FIRST FIT
0,33554432 s
a) 12 Ko : la zone de 20 Ko sera utilisée.
b) 10 Ko : la zone de 10 Ko sera utilisée.
3. Comparaison de stockage c) 9 Ko : la zone de 18 Ko sera utilisée.
Méthode avec une table de bits :
- La mémoire totale est de 128 Mo. BEST FIT
- Chaque unité de mémoire est de n octets. a) 12 Ko : la zone de 12 Ko sera utilisée.
- Donc, le nombre total d'unités de mémoire est de 128 Mo / n. b) 10 Ko : la zone de 10 Ko sera utilisée.
Pour représenter l'état de chaque unité de mémoire (occupée ou libre), nous c) 9 Ko : la zone de 9 Ko sera utilisée.
avons besoin d'un bit.
WORST FIT
- Par conséquent, la taille de stockage nécessaire pour une table de bits serait de
a) 12 Ko : la zone de 20 Ko sera utilisée.
(128 Mo / n) bits.
b) 10 Ko : la zone de 18 Ko sera utilisée.
Méthode avec une liste chaînée : c) 9 Ko : la zone de 15 Ko sera utilisée.
- La mémoire est constituée de segments de 64 Ko (64 * 2^10 octets) en
alternance avec des zones vides de taille identique. NEXT FIT
- Chaque nœud de la liste nécessite une adresse mémoire de 32 bits, une a) 12 Ko : la zone de 20 Ko sera utilisée.
longueur de 16 bits et un champ de 16 bits pour le prochain nœud. b) 10 Ko : la zone de 18 Ko sera utilisée.
- La taille de stockage nécessaire pour chaque nœud serait de (32 + 16 + 16) bits. c) 9 Ko : la zone de 9 Ko sera utilisée.
 entrées de table des pages (soit 32 entrées) et chaque entrée de table des pages est de 4 octets (soit
5. DIFFÉRENCE un mot). Par conséquent, chaque page contient 2^5 mots et la table des pages contient 2^(32-13-5)
Une adresse physique est l'adresse réelle d'un emplacement de mémoire dans le matériel pages, soit 2^14 pages. La table des pages contient donc 2^14 mots.
informatique. Le temps nécessaire pour copier la table des pages en mémoire principale est de 100 ns par mot. Par
Une adresse virtuelle est une adresse qui est utilisée par le système d'exploitation pour représenter un conséquent, le temps total nécessaire pour copier la table des pages en mémoire principale est de :
emplacement de mémoire dans l'espace d'adressage virtuel d'un processus. Les adresses virtuelles Temps total = Nombre de mots x Temps par mot
sont traduites en adresses physiques par le matériel informatique à l'aide d'une table de pagination ou Temps total = 2^14 x 100 ns
d'une table de segmentation. Temps total = 4 096 000 ns
Le temps total nécessaire pour exécuter un processus est de 100 ms (soit 100 000 000 ns). Par
6. Page virtuelle et déplacement conséquent, la fraction du temps processeur réservée au chargement des tables de pages est :
Pour déterminer le numéro de page virtuelle et le déplacement pour des pages de 4 Ko et de 8 Ko, Fraction du temps processeur = Temps total / Temps total d'exécution
nous devons diviser l'adresse virtuelle décimale par la taille de la page correspondante et prendre la Fraction du temps processeur = 4 096 000 ns / 100 000 000 ns
partie entière du résultat. Fraction du temps processeur = 0,04096 ou environ 4 %
Pour des pages de 4 Ko (4096 octets) :
Adresse virtuelle décimale : 20 000 10. Exo 10
- Numéro de page virtuelle : 20 000 / 4096 = 4 La taille des pages peut être calculée en utilisant la formule suivante :
- Déplacement : 20 000 % 4096 = 3616 Taille de la page = 2^(Nombre de bits pour le déplacement)
Adresse virtuelle décimale : 32 768 Dans ce cas, le nombre de bits pour le déplacement est égal à 32 - 9 - 11 = 12.
- Numéro de page virtuelle : 32 768 / 4096 = 8 Par conséquent, la taille de la page est : Taille de la page = 2^12 octets Taille de la page = 4 Ko
- Déplacement : 32 768 % 4096 = 0 Le nombre total de pages dans l'espace d'adressage peut être calculé en utilisant la formule suivante :
Adresse virtuelle décimale : 60 000 Nombre total de pages = 2^(Nombre de bits pour le premier niveau) x 2^(Nombre de bits pour le
- Numéro de page virtuelle : 60 000 / 4096 = 14 deuxième niveau)
- Déplacement : 60 000 % 4096 = 2656 Dans ce cas, le nombre de bits pour le premier niveau est égal à 9 et le nombre de bits pour le
Pour des pages de 8 Ko (8 192 octets) deuxième niveau est égal à 11. Par conséquent, le nombre total de pages dans l'espace d'adressage
Adresse virtuelle décimale : 20 000 est : Nombre total de pages = 2^9 x 2^11 Nombre total de pages = 524 288
- Numéro de page virtuelle : 20 000 / 8 192 = 2
- Déplacement : 20 000 % 8 192 = 3616 11. Exo 11
Adresse virtuelle décimale : 32 768 Le nombre de pages ne dépend pas de la taille des 4 champs. En effet, la taille des champs a, b et c
- Numéro de page virtuelle : 32 768 / 8 192 = 4 est utilisée pour une table des pages à trois niveaux. Le quatrième champ d est le déplacement
- Déplacement : 32 768 % 8 192 = 0 (offset). La taille de la page est fixe et ne dépend pas de la taille des champs.
Adresse virtuelle décimale : 60 000
- Numéro de page virtuelle : 60 000 / 8 192 = 7 12. Exo 12
- Déplacement : 60 000 % 8 192 = 2656 Pour une pagination à un niveau, il faut une entrée dans la table des pages pour
chaque page de 4 Ko. Comme il y a 2^32 adresses virtuelles de 32 bits et que chaque page contient 4
8. Exo 8 Ko (soit 2^12 octets), le nombre de pages est de 2^32 / 2^12 = 2^20. Par conséquent, le nombre
Le temps effectif d’une instruction = (temps d’exécution d’une instruction + (temps d’entrées dans la table des pages est également de 2^20.
supplémentaire pour un défaut de page / nombre d’instructions entre les défauts de page)) Pour une pagination à deux niveaux avec 10 bits pour chaque niveau, le nombre d’entrées dans la
AN - 10 + n/k table des pages est calculé comme suit :
• Le premier niveau a besoin d’une entrée pour chaque bloc de 1024 pages (2^10). Comme il
9. Exo 9 y a 2^32 adresses virtuelles et que chaque page contient 4 Ko (soit 2^12 octets), le nombre de
Pour calculer la fraction du temps processeur réservée au chargement des tables de pages, nous pages est de 2^32 / 2^12 = 2^20. Par conséquent, le nombre d’entrées dans la table des pages
devons d'abord déterminer le nombre de mots dans la table des pages. Étant donné que l'espace du premier niveau est de 2^20 / 1024 = 2^10. Le deuxième niveau a besoin d’une entrée pour
d'adressage est de 32 bits et que les pages sont de 8 Ko (soit 2^13 octets), chaque page contient 2^5
 chaque page. Le nombre total de pages est de 2^20. Par conséquent, le nombre d’entrées - Segment de code : 32 768 octets
dans la table des pages du deuxième niveau est également de 2^20 - Segment de données : 16 386 octets
- Segment de pile : 15 870 octets
13. Exo 13
La taille totale requise pour le programme spécifique est la somme de ces trois segments : 32 768 + 16
La machine a des adresses virtuelles sur 48 bits et des adresses physiques de 32 bits. Les pages sont 386 + 15 870 = 65 024 octets.
de 8 Ko (soit 2^13 octets). Pour une page de 8 Ko, il y a 2^35 adresses virtuelles (2^48 / 2^13) et 2^19
adresses physiques (2^32 / 2^13) Comme la taille totale requise (65 024 octets) est inférieure à la taille totale de l'espace d'adressage
Le nombre d’entrées dans la table des pages est égal au nombre de pages virtuelles. Le nombre de (65 536 octets), le programme spécifique rentre dans l'espace d'adressage avec des pages de 4 096
pages virtuelles est égal au nombre d’adresses virtuelles divisé par la taille d’une page. Dans ce cas, le octets.
nombre de pages virtuelles est de 2^35 / 2^13 = 2^22. Par conséquent, le nombre d’entrées dans la
table des pages est également de 2^22 2. Taille de page de 512 octets :
- Segment de code : 32 768 octets
- Segment de données : 16 386 octets
14. Exo 14 - Segment de pile : 15 870 octets
15. Exo 15
Pour calculer si le programme spécifique rentre dans l'espace d'adressage avec des pages de 512
16. Exo 16 : octets, nous devons recalculer la taille totale requise pour chaque segment en prenant en compte la
Temps de recherche + Temps de rotation + (Taille du fichier / Taille de la page) * Temps de rotation taille de page plus petite.
a) Pour des pages de 2 Ko: Temps de recherche = 10 ms Temps de rotation = 10 ms Taille du fichier =
64 Ko Taille de la page = 2 Ko - Segment de code : 32 768 octets / 512 = 64 pages
Temps de chargement = 10 + 10 + (64 / 2) * 10 = 370 ms - Segment de données : 16 386 octets / 512 = 32 pages
b) Pour des pages de 4 Ko: Temps de recherche = 10 ms Temps de rotation = 10 ms Taille du fichier = - Segment de pile : 15 870 octets / 512 = 31 pages
64 Ko Taille de la page = 4 Ko
Temps de chargement = 10 + 10 + (64 / 4) * 10 = 330 ms La taille totale requise avec des pages de 512 octets est de 64 + 32 + 31 = 127 pages.

17. Exo 17 Comme la taille totale requise (127 pages) est supérieure à la taille totale de l'espace d'adressage (65
536 octets / 512 = 128 pages), le programme spécifique ne rentre pas dans l'espace d'adressage avec
a) Avec l'algorithme NRU, la page qui sera remplacée est la page 0 car elle n'a pas été référencée des pages de 512 octets.
récemment et n'a pas été modifiée récemment.

b) Avec l'algorithme FIFO, la page qui sera remplacée est la page 0 car elle est la plus ancienne parmi 19. Exo 19
les pages chargées.
• La fragmentation interne se produit lorsque les blocs de mémoire de taille fixe sont alloués
c) Avec l'algorithme LRU, la page qui sera remplacée est la page 1 car elle a été référencée il y a plus aux processus sans se soucier de la taille du processus, et qu’il reste de l’espace libre dans le
longtemps que les autres pages. bloc alloué.
• La fragmentation externe se produit lorsque l’espace mémoire de taille variable est alloué
d) Avec l'algorithme de la deuxième chance, la page qui sera remplacée est la page 3 car elle a le bit R dynamiquement aux processus, et qu’il y a des trous dans la mémoire après la suppression
à 1 et donc elle a une deuxième chance. des processus.
• La fragmentation interne se produit dans les systèmes paginés, où la mémoire est divisée en
blocs de taille fixe appelés pages.
18. Exo 18 • La fragmentation externe se produit dans les systèmes à segmentation pure, où la
1. Taille de page de 4 096 octets : mémoire est divisée en blocs de taille variable appelés segments
 20. Exo 20 (a) 950
Le numéro de page est : 950 / 1024 = 0
21. Exo 21 L'offset est : 950 % 1024 = 950.
Oui, c’est possible avec la pagination La pagination divise la mémoire en blocs fixes. Le système gère
les blocs et les droits d’accès. Le MMU traduit les adresses logiques en physiques. (b) 1851
Le numéro de page est : 1851 / 1024 = 1
22. Exo 22 L'offset est : 1851 % 1024 = 827.
La taille de la mémoire virtuelle = nombre de pages * taille d’une page.
Comme une adresse virtuelle est codée sur 32 bits, il y a 2^32 adresses virtuelles possibles. Comme (c) 25354
une page a une taille de 256 Ko, il y a 2^32 / 2^18 = 2^14 pages possibles. Donc, la taille de la Le numéro de page est : 25354 / 1024 = 24
mémoire virtuelle est égale à 2^14 * 2^18 = 2^32 octets, soit 4 Go. L'offset est : 25354 % 1024 = 778.

b) Pour une adresse virtuelle donnée, le numéro de la page virtuelle est le quotient de la division de (d) 11842
l’adresse par la taille d’une page, et l’adresse (déplacement) dans cette page est le reste de cette Le numéro de page est : 11842 / 1024 = 11
division. Comme une page a une taille de 256 Ko, il faut 18 bits pour coder le déplacement dans une L'offset est : 11842 % 1024 = 578.
page. Donc, le numéro de la page virtuelle est codé sur les 14 bits de poids fort de l’adresse virtuelle,
et le déplacement dans la page est codé sur les 18 bits de poids faible.
29. Exo 29
23. Exo 23 Les adresses physiques correspondant aux adresses logiques sont :
24. Exo 24 • (0, 128) : 540 + 128 = 668
La mémoire virtuelle permet d’utiliser plus de mémoire vive et de réduire les défauts de page. La • (1, 99) : 1254 + 99 = 1353
compression de mémoire virtuelle permet de réduire les requêtes de pagination.
• (4, 100) : 976 + 100 = 1076
25. Exo 25 • (3, 888) : 2048 + 888 = 2936
Un algorithme de remplacement statique de pages utilise un critère fixe et prédéfini pour choisir les
• (2, 465) : Cette adresse logique est invalide car elle dépasse la longueur du segment 2.
pages à remplacer Un algorithme de remplacement dynamique de pages adapte son critère en
fonction du comportement des processus et des caractéristiques du système • (4, 344) : Cette adresse logique est invalide car elle dépasse la longueur du segment 4.
30. Exo 30
26. Exo 26
31. Exo 31

27. Exo 27 La suite des pages correspondant aux adresses est :

La taille des blocs = taille des pages pour la mémoire virtuelle et à la taille des cadres pour la • 34 : page 0
mémoire physique. Elle est déterminée par le nombre de bits du déplacement dans l’adresse virtuelle • 145 : page 1
ou physique. Comme 2g+h adresses virtuelles correspondent à 2h+k adresses physiques, on a g+h = • 10 : page 0
h+k, donc g = k. On en déduit que la taille des blocs est une puissance de deux, 2g ou 2k. Le nombre • 236 : page 2
de bits pour l’adresse virtuelle est g+h, et le nombre de bits pour l’adresse physique est h+k. Par • 510 : page 5
exemple, si g = 12, h = 20 et k = 12, alors la taille des blocs est 4 Ko, le nombre de bits pour l’adresse • 412 : page 4
virtuelle est 32 et le nombre de bits pour l’adresse physique est 32 aussi. • 789 : page 7
La formule de calcul est :
28. Exo 28 page = adresse / taille de la page
numéro de page = adresse virtuelle / taille de la page
numéro de ligne (offset) = adresse virtuelle mod taille de la page