SYSTÈME D’EXPLOITATION
PROCESSUS
Les algorithmes de gestion de processus
• FIFO ou PAPS
Lorsqu’un défaut de page se produit et qu’il n’y a
plus de place dans la mémoire physique pour
charger une nouvelle page, cet algorithme choisit la
page qui a été chargée en premier dans la mémoire
physique pour être remplacée par la nouvelle page.
• Algorithme du moins fréquemment utilisé
(LRU)
Lorsqu’un défaut de page se produit et qu’il n’y a
plus de place dans la mémoire physique pour
charger une nouvelle page, cet algorithme choisit la
page qui a été utilisée le moins récemment pour être
remplacée par la nouvelle page.
• Remplacement Optimal
Lorsqu’un défaut de page se produit et qu’il n’y a
plus de place dans la mémoire physique pour
charger une nouvelle page, cet algorithme choisit la
page qui ne sera pas utilisée pendant la plus longue
période de temps pour être remplacée par la
nouvelle page. Puis on cherche la plus ancienne dans
la mémoire physique
• Algorithme de vieillissement
L'algorithme de vieillissement est un algorithme de
remplacement de page utilisé dans les systèmes
d'exploitation pour gérer la mémoire virtuelle. Il
utilise un compteur pour chaque page pour suivre
son utilisation récente. À chaque top d'horloge, les
compteurs sont mis à jour en décalant leur valeur
d'un bit vers la droite et en ajoutant la valeur du bit
R (bit de référence) à gauche
o Algorithme de la double chance
o Algorithme du peu fréquemment utilisé
(NRU)
L’algorithme NRU divise les pages en quatre
catégories en fonction de leur historique d’utilisation
et sélectionne une page pour le remplacement à
partir de la catégorie ayant la priorité la plus basse.
• Catégorie 0: Pages qui n’ont pas été référencées
et modifiées récemment
• Catégorie 1: Pages qui n’ont pas été référencées
récemment mais ont été modifiées récemment
• Catégorie 2: Pages qui ont été référencées
récemment mais n’ont pas été modifiées
récemment
• Catégorie 3: Pages qui ont été référencées et
modifiées récemment
Lorsqu’un défaut de page se produit, l’algorithme
NRU analyse les pages en mémoire et identifie les
pages dans chaque catégorie. Il sélectionne ensuite
une page aléatoire à partir de la catégorie la plus
basse avec des pages non vides et la remplace par la
nouvelle page
EXERCICE
Supposons que nous avons un système de mémoire
virtuelle avec 3 cases de mémoire physique et un
espace virtuel de 7 pages. Les pages sont appelées
dans l’ordre suivant au cours de l’exécution d’un
processus par le processeur: 7, 0, 1, 2, 0, 3, 0, 4.
First Fit alloue le premier bloc de mémoire
suffisamment grand pour contenir la taille demandée
Best Fit on cherche le plus petit bloc suffisamment
grand pour contenir la taille demandée
Next Fit Il alloue ensuite le bloc de mémoire disponible
suivant aux processus suivants. Lorsqu’un nouveau bloc
de mémoire doit être alloué, l’algorithme Next Fit
commence à chercher un bloc libre à partir de l’endroit
où il a alloué le dernier bloc. S’il trouve un bloc libre
suffisamment grand pour contenir la taille demandée, il
alloue ce bloc. Sinon, il continue à chercher jusqu’à ce
qu’il atteigne la fin de la mémoire. S’il n’a pas trouvé de
bloc libre suffisamment grand, il revient au début de la
mémoire et continue à chercher jusqu’à ce qu’il atteigne
l’endroit où il a commencé.
Worst Fit est une méthode d’allocation de mémoire qui
alloue toujours le plus grand bloc disponible pour un
processus en espérant que le reste du bloc sera utile
pour répondre à une demande future. L’algorithme
fonctionne en parcourant la liste des blocs de mémoire
libres et en choisissant le plus grand bloc qui peut
accueillir le processus en cours. Si un tel bloc est trouvé,
il est alloué au processus et sa taille est réduite en
conséquence. Sinon, le processus ne peut pas être
alloué.
FAIRE EXO 4 FICHE TD 2
Les 02 ci sont optionnels il n’a pas parlé de ça dans le
cours
o SJF NON PRÉVENTIVE
Il attribue la priorité aux processus en fonction de la
durée de leur prochaine unité de travail (burst time).
Les processus avec les burst times les plus courts
sont exécutés en premier.
Une fois qu’un processus commence son exécution, il
continue jusqu’à ce qu’il soit terminé.
o SRTF
Dans la variante préemptive, également connue sous
le nom de SRTF (Shortest Remaining Time First), un
processus en cours d’exécution peut être interrompu
si un nouveau processus arrive avec un burst time
plus court.
EXERCICE
Supposons que nous avons 4 processus avec les
durées de burst time suivantes:
P1 = 6, P2 = 8, P3 = 7 et P4 = 3.
Les processus arrivent dans l’ordre suivant: P1
arrive à l’instant 0, P2 arrive à l’instant 2, P3 arrive à
l’instant 4 et P4 arrive à l’instant 5.
MÉMOIRE
1. PAGINATION
Numéro de page virtuelle = Adresse virtuelle /
Taille des pages
Le résultat est arrondi à l’entier inférieur
Décalage dans la page(déplacement) = Adresse
virtuelle mod Taille des pages
Traduction d’adresse(Adresse physique) =
Adresse de base de la page + Décalage dans la page
EXEMPLE
Dans un système à pagination de 100 octets, donner
la suite des pages correspondant aux adresses
suivantes : 34, 145, 236.
Calcul des pages
Adresse 34 : (34/100) = 0 (page 0)
Adresse 145 : (145/100) = 1.45 (page 1)
Adresse 236 : (236/100) = 2.36 (page 2)
Calcul du décalage
Adresse 34 : (34 mod 100 ) = 34
Adresse 145 : (145 mod 100) = 45
Adresse 236 : (236 mod 100) = 36
FAIRE EXO 6 FUCHE TD 2
La formule pour calculer le temps nécessaire pour
compacter la mémoire est la suivante:
Temps de compactage = (Taille de la mémoire /
Taille du mot mémoire) * Temps par opération * 2
La formule que vous devriez retenir pour calculer le
temps effectif d’une instruction lorsque des défauts de
page se produisent est la suivante :
(temps d’exécution d’une instruction + (temps
supplémentaire pour un défaut de page / nombre
d’instructions entre les défauts de page))
pour calculer la fraction du temps processeur
réservée au chargement des tables de pages est la
suivante : (temps pour copier la table des pages en
mémoire principale) / (temps total d’exécution d’un
processus)
2. LES ALGORITHMES
Algorithme de remplacement optimal
Algorithme de file
Algorithme du peu fréquemment utilisé (NRU)
Algorithme du moins fréquemment utilisé (LRU)
