Scribd Logo
Importer

Bienvenue sur Scribd !

  • 137 vues

    SYE S7 Algorithmes Horloge Et LRU v2017.1.1 Answers

    Transféré par

    secoia
    Ce document décrit deux algorithmes de remplacement de pages en mémoire virtuelle: l'algorithme de la seconde chance et l'algorithme LRU. Il présente des exemples d'application de ces algorithmes sur des séquences de références de pages, et calcule le nombre de fautes de pages dans chaque cas.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    SYE S7 Algorithmes Horloge Et LRU v2017.1.1 Answers

    Transféré par

    secoia
    137 vues2 pages
    Ce document décrit deux algorithmes de remplacement de pages en mémoire virtuelle: l'algorithme de la seconde chance et l'algorithme LRU. Il présente des exemples d'application de ces algorithmes sur des séquences de références de pages, et calcule le nombre de fautes de pages dans chaque cas.

    Description originale:

    ffff

    Titre original

    SYE_S7_Algorithmes_horloge_et_LRU_v2017.1.1_answers

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Ce document décrit deux algorithmes de remplacement de pages en mémoire virtuelle: l'algorithme de la seconde chance et l'algorithme LRU. Il présente des exemples d'application de ces algorithmes sur des séquences de références de pages, et calcule le nombre de fautes de pages dans chaque cas.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    137 vues2 pages

    SYE S7 Algorithmes Horloge Et LRU v2017.1.1 Answers

    Transféré par

    secoia
    Ce document décrit deux algorithmes de remplacement de pages en mémoire virtuelle: l'algorithme de la seconde chance et l'algorithme LRU. Il présente des exemples d'application de ces algorithmes sur des séquences de références de pages, et calcule le nombre de fautes de pages dans chaque cas.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 2

    Systèmes d'exploitation

    Prof. D. Rossier / Prof. A. Dassatti


    v2017.1.1

    Série no 7 (Solutions)
    Algorithmes de la seconde chance et LRU

    1. Algorithme de la seconde chance

    Soit la séquence de références de page suivante :

    2 1 3 1 3 0 7 3 5 4 2 1

    a) Appliquez l'algorithme de remplacement de page de la "seconde chance" lorsque le système


    dispose de quatre pages physiques.

    Solution

    Le tableau ci-dessous représente le contenu des pages physiques au fil du temps.


    - La flèche indique le pointeur vers la prochaine page candidate au remplacement (page
    susceptible d'être remplacée au temps suivant)
    - Le signe "+" indique le bit de référence R à 1, le signe "-" le bit de référence R à zéro.
    - Le cercle indique la page référencée au temps t

    Explications

    Dans l'algorithme de la seconde chance, les pages à remplacer suivent une politique FIFO avec la
    particularité suivante: lorsque leur bit de référence est à 1, la page n'est pas remplacée (on lui
    donne une seconde chance); son bit de référence est remis à zéro et la page est placée en queue de
    liste (le prochain élément du FIFO à enlever se trouvant en tête de liste), comme si elle venait
    juste d'arriver en mémoire; bien entendu, la page ne change pas de place en mémoire. Par
    conséquent le déplacement du pointeur est similaire à l'algorithme FIFO.

    Temps 1 (2) : Faute de page / Page 2 chargée, bit de référence à 1, pas de remplacement; cette
    page sera la première candidate (cf pointeur FIFO)
    Temps 2 (1): Faute de page / Page 1 chargée, bit de référence à 1, pas de remplacement
    Temps 3 (3): Faute de page / Page 3 chargée, bit de référence à 1, pas de remplacement

    -1-
    Systèmes d'exploitation – Algorithmes de la seconde chance et LRU

    Temps 4 (1): Page 1 référencée sans faute de page


    Temps 5 (3): Page 3 référencée sans faute de page
    Temps 6 (0): Faute de page / Page 0 chargée, il y a encore de la plage; pas de remplacement
    Temps 7 (7): Faute de page / Le pointeur au temps 6 indiquait la page 7; comme son bit de
    référence est à 1, on met ce bit à 0, on considère cette page comme nouvellement chargée (c-à-d
    on la place en queue de liste), et on passe à la page suivante; comme les pages ont été chargées
    dans la première position libre disponible (c-à-d séquentiellement), il suffit donc de parcourir
    simplement la liste des pages de manière circulaire, jusqu'à ce qu'on trouve une page dont le bit de
    référence est à 0. Dans notre cas (temps 7), comme toutes les pages du temps 6 ont un bit à 1, on
    effectue un tour complet et on retombe sur la page P1, page qui sera remplacée. Le pointeur de la
    prochaine page indique maintenant la page P2.
    Temps 8 (3): Page 3 référencée sans faute de page; son bit de référence passe à 1
    Temps 9 (5): Faute de page / La page pointée à son bit de référence à 0 et peut être évincée. Le
    pointeur passe sur la page suivante.
    Temps 10 (4): Faute de page / La page pointée au temps 9 à son bit R à 1; on le ré-initialise et on
    regarde la page suivante (2-); cette dernière a le bit R à 0; on peut donc la remplacer.
    Temps 11 (2): Faute de page / Le pointeur (temps 10) indique la page 7, bit R à 1. On descend
    jusqu'à trouver la page 3 qui a son bit R à 0. Cette page est remplacée.
    Temps 12 (1): Faute de page / Le pointeur (temps 11) indique une page dont le bit R est à 1; on
    doit avancer d'une page (circulairement) et on tombe sur la page 7 dont le bit R est à 0, qui sera
    remplacée au temps 12.

    b) Combien y a-t-il de faute(s) de page ?

    Il y a en tout 9 fautes de page.

    2. Algorithme LRU

    Soit la séquence de références de page suivante :

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

    a) Donnez l’état de la mémoire avec cinq pages physiques et un algorithme de remplacement de


    page LRU.

    b) Combien y a-t-il de faute(s) de page ?

    Il y a en tout 9 fautes de pages.

    -2-

    Vous aimerez peut-être aussi