6-6 .pdf

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion

Syst`emes d’Exploitation Cours 6/13 : Remplacement de pages Nicolas Sabouret Universit´e Paris-Sud Licence 3 - semestre S5

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

1/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion

Plan

1

Pr´esentation du probl`eme

2

Algorithmes type FIFO

3

Algorithmes bas´es sur l’utilisation

4

Conclusion

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

2/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Plan

1

Pr´esentation du probl`eme Probl`eme

2

Algorithmes type FIFO

3

Algorithmes bas´es sur l’utilisation

4

Conclusion

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

3/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Remplacement de pages M´emoire virtuelle Chaque processus dispose d’un nombre de cadres limit´e selon la politique d’allocation

Ü Lib´erer un cadre lorsqu’on a besoin d’une nouvelle page

Probl`eme (rappel) Temps d’ex´ecution proportionnel `a la probabilit´e de d´efaut de page Ü R´eduire le nombre de d´efauts de page

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

4/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Remplacement de pages M´emoire virtuelle Chaque processus dispose d’un nombre de cadres limit´e selon la politique d’allocation

Ü Lib´erer un cadre lorsqu’on a besoin d’une nouvelle page

Probl`eme (rappel) Temps d’ex´ecution proportionnel `a la probabilit´e de d´efaut de page Ü R´eduire le nombre de d´efauts de page Exemple : 03 2A 1F 04 D´efauts : 0 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

4/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Remplacement de pages M´emoire virtuelle Chaque processus dispose d’un nombre de cadres limit´e selon la politique d’allocation

Ü Lib´erer un cadre lorsqu’on a besoin d’une nouvelle page

Probl`eme (rappel) Temps d’ex´ecution proportionnel `a la probabilit´e de d´efaut de page Ü R´eduire le nombre de d´efauts de page Exemple : 03 2A 1F 04 03 Info32b

2A

1F

04

Syst` emes d’Exploitation

D´efauts : 4 Nicolas Sabouret

4/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Remplacement de pages M´emoire virtuelle Chaque processus dispose d’un nombre de cadres limit´e selon la politique d’allocation

Ü Lib´erer un cadre lorsqu’on a besoin d’une nouvelle page

Probl`eme (rappel) Temps d’ex´ecution proportionnel `a la probabilit´e de d´efaut de page Ü R´eduire le nombre de d´efauts de page Exemple : 03 2A 1F 04 2A 03 Info32b

2A

1F

04

Syst` emes d’Exploitation

D´efauts : 4 Nicolas Sabouret

4/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Remplacement de pages M´emoire virtuelle Chaque processus dispose d’un nombre de cadres limit´e selon la politique d’allocation

Ü Lib´erer un cadre lorsqu’on a besoin d’une nouvelle page

Probl`eme (rappel) Temps d’ex´ecution proportionnel `a la probabilit´e de d´efaut de page Ü R´eduire le nombre de d´efauts de page Exemple : 03 2A 1F 04 2A 03 Info32b

2A

1F

04

Syst` emes d’Exploitation

D´efauts : 4 Nicolas Sabouret

4/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Remplacement de pages M´emoire virtuelle Chaque processus dispose d’un nombre de cadres limit´e selon la politique d’allocation

Ü Lib´erer un cadre lorsqu’on a besoin d’une nouvelle page

Probl`eme (rappel) Temps d’ex´ecution proportionnel `a la probabilit´e de d´efaut de page Ü R´eduire le nombre de d´efauts de page Exemple : 03 2A 1F 04 2A 12 03 Info32b

2A

1F

04

Syst` emes d’Exploitation

D´efauts : 4 Nicolas Sabouret

4/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Remplacement de pages M´emoire virtuelle Chaque processus dispose d’un nombre de cadres limit´e selon la politique d’allocation

Ü Lib´erer un cadre lorsqu’on a besoin d’une nouvelle page

Probl`eme (rappel) Temps d’ex´ecution proportionnel `a la probabilit´e de d´efaut de page Ü R´eduire le nombre de d´efauts de page Exemple : 03 2A 1F 04 2A 12 12 Info32b

2A

1F

04

Syst` emes d’Exploitation

D´efauts : 5 Nicolas Sabouret

4/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Remplacement de pages M´emoire virtuelle Chaque processus dispose d’un nombre de cadres limit´e selon la politique d’allocation

Ü Lib´erer un cadre lorsqu’on a besoin d’une nouvelle page

Probl`eme (rappel) Temps d’ex´ecution proportionnel `a la probabilit´e de d´efaut de page Ü R´eduire le nombre de d´efauts de page Exemple : 03 2A 1F 04 2A 12 03 12 Info32b

2A

1F

04

Syst` emes d’Exploitation

D´efauts : 5 Nicolas Sabouret

4/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Remplacement de pages M´emoire virtuelle Chaque processus dispose d’un nombre de cadres limit´e selon la politique d’allocation

Ü Lib´erer un cadre lorsqu’on a besoin d’une nouvelle page

Probl`eme (rappel) Temps d’ex´ecution proportionnel `a la probabilit´e de d´efaut de page Ü R´eduire le nombre de d´efauts de page Exemple : 03 2A 1F 04 2A 12 03 03 Info32b

2A

1F

04

Syst` emes d’Exploitation

D´efauts : 6 Nicolas Sabouret

4/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Repr´esentation visuelle Objectif Figurer l’´etat du cache dans le temps pour compter le nombre de d´efauts

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

5/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Repr´esentation visuelle Objectif Figurer l’´etat du cache dans le temps pour compter le nombre de d´efauts 03

2A

1F

04

2A

12

03

Premi`ere ligne : liste des pages demand´ees (dans l’ordre) Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

5/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Repr´esentation visuelle Objectif Figurer l’´etat du cache dans le temps pour compter le nombre de d´efauts 03

2A

1F

04

2A

12

03

0 1 2 3

Une ligne par cadre de page allou´e au processus Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

5/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Repr´esentation visuelle Objectif Figurer l’´etat du cache dans le temps pour compter le nombre de d´efauts 03 0

2A

1F

04

2A

12

03

03

1 2 3

Une page par colonne Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

5/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Repr´esentation visuelle Objectif Figurer l’´etat du cache dans le temps pour compter le nombre de d´efauts 03 0 1

2A

1F

04

2A

12

03

03 2A

2 3

Une page par colonne Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

5/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Repr´esentation visuelle Objectif Figurer l’´etat du cache dans le temps pour compter le nombre de d´efauts 03 0 1 2

2A

1F

04

2A

12

03

03 2A 1F

3

Une page par colonne Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

5/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Repr´esentation visuelle Objectif Figurer l’´etat du cache dans le temps pour compter le nombre de d´efauts 03 0 1 2 3

2A

1F

04

2A

12

03

03 2A 1F 04

Une page par colonne Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

5/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Repr´esentation visuelle Objectif Figurer l’´etat du cache dans le temps pour compter le nombre de d´efauts 03 0

2A

1F

04

2A

12

03

03

1

2A

2

1F

3

04 *

*

*

*

Marquer les d´efauts au fur et `a mesure Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

5/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Repr´esentation visuelle Objectif Figurer l’´etat du cache dans le temps pour compter le nombre de d´efauts 03 0

2A

1F

04

2A

12

03

03

1

2A

2

1F

3

04 *

*

*

*

Pas de d´efaut → laisser en blanc Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

5/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Repr´esentation visuelle Objectif Figurer l’´etat du cache dans le temps pour compter le nombre de d´efauts 03 0

2A

1F

04

03

1

2A

12

03

12 2A

2

1F

3

04 *

*

*

*

*

Et on continue. . . Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

5/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Repr´esentation visuelle Objectif Figurer l’´etat du cache dans le temps pour compter le nombre de d´efauts 03 0

2A

1F

04

03

1

2A

12

03

12 2A

2

03

1F

3

04 *

*

*

*

*

*

Et on continue. . . Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

5/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Repr´esentation visuelle Objectif Figurer l’´etat du cache dans le temps pour compter le nombre de d´efauts 03 0

2A

1F

04

03

1

2A

12

03

12 2A

Total : 6 d´efauts 2

03

1F

3

04 *

*

*

*

*

*

Et on continue. . . Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

5/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Solution optimale Politique de remplacement Pour une instance donn´ee, il existe une politique de remplacement optimale. . . . . . si on connaˆıt `a l’avance les pages qui seront demand´ees !

03 0

2A

1F

04

2A

12

03

03

1

12

2A

Total : 5 d´efauts 2

1F

3

04 *

*

*

*

*

En pratique, on ne connaˆıt pas les pages ! Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

6/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Solution Algorithme de remplacement D´efinir une fonction qui, ´etant donn´e l’´etat actuel (occupation des cadres par des pages), d´ecide quel cadre doit ˆetre lib´er´e.

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

7/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Solution Algorithme de remplacement D´efinir une fonction qui, ´etant donn´e l’´etat actuel (occupation des cadres par des pages), d´ecide quel cadre doit ˆetre lib´er´e.

Classes d’algorithmes First In, First Out (FIFO) Ü retirer les pages les plus anciennes

Bas´es sur l’utilisation des pages (Least Used) Ü retirer les pages les moins utilis´ees

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

7/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Probl` eme

Solution Algorithme de remplacement D´efinir une fonction qui, ´etant donn´e l’´etat actuel (occupation des cadres par des pages), d´ecide quel cadre doit ˆetre lib´er´e.

Classes d’algorithmes First In, First Out (FIFO) Ü retirer les pages les plus anciennes

Bas´es sur l’utilisation des pages (Least Used) Ü retirer les pages les moins utilis´ees

´ Evaluation = nombre de d´efauts de page Sur des instances (en TD, `a l’examen) Sur des benchmarks Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

7/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Plan

1

Pr´esentation du probl`eme

2

Algorithmes type FIFO FIFO Second chance

3

Algorithmes bas´es sur l’utilisation

4

Conclusion

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

8/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

2A

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

2A

1F

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

2A

1F

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

2A

1F

12

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

2A

1F

12

Syst` emes d’Exploitation

48

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

2A

1F

12

Syst` emes d’Exploitation

48

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

04

2A

1F

12

Syst` emes d’Exploitation

48

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

04

2A

1F

12

Syst` emes d’Exploitation

48

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

B1

2A

1F

12

Syst` emes d’Exploitation

48

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

B1

2A

1F

12

Syst` emes d’Exploitation

48

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

B1

2A

1F

12

Syst` emes d’Exploitation

48

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

B1

03

1F

12

Syst` emes d’Exploitation

48

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

B1

03

76

12

Syst` emes d’Exploitation

48

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

B1

03

76

2A

Syst` emes d’Exploitation

48

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

B1

03

76

2A

Syst` emes d’Exploitation

1F

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 37

Info32b

B1

03

76

2A

Syst` emes d’Exploitation

1F

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37

03

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 03

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 2A

Info32b

03

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 2A

03

1F

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 2A

03

1F

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 03

2A

1F 12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 2A

03

1F

48 12

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 2A

31

1F

48 12

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 2A

31

1F

48 12

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 2A

31

1F

48 12

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 03

31

1F

48 12

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 03

31

76

48 12

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 03

31

76

48 2A

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 03

31

76

1F 2A

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Principe File Retirer la page la plus ancienne Ü Impl´ementation = liste circulaire (clock based) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 03

37

76

1F 2A

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

9/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

0 1 2 3 4 5

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1 2 3 4 5 *

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2 3 4 5 *

Info32b

*

Syst` emes d’Exploitation

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3 4 5 *

Info32b

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

1F

4 5 *

Info32b

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

1F

4 5 *

Info32b

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

1F

4

12

5 *

Info32b

*

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 03

2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 03

2A

3

76

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

*

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 03

2A

3

76

1F

4

12

5

2A 48

*

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

*

*

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

04

37

B1 03

2A

3

76

1F

4

12

5

2A 48

*

1F

31

2

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

1F *

*

*

Nicolas Sabouret

*

*

*

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

04

B1

3

03 76

1F

4

12

5

2A 48

*

37 37

2A

*

1F

31

2

Info32b

48

*

*

*

Syst` emes d’Exploitation

*

1F *

*

*

Nicolas Sabouret

*

*

*

*

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

03

1

31

B1

2A

03

76

2A

31 04

2

B1

3

03 76

1F

4

12

5

2A 48

*

37 37

2A

*

1F

*

*

*

*

1F *

*

*

*

*

*

*

Total : 13 d´efauts Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

10/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03

02

01

00

03

02

04

03

02

01

00

04

0 1 2

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

01

00

03

02

04

03

02

01

00

04

03

1 2 *

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

01

00

03

02

04

03

02

01

00

04

03

1

02

2 *

Info32b

*

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

00

03

02

04

03

02

01

00

04

03

1

02

2

01 *

Info32b

01

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

03

1

00

03

02

04

03

02

01

00

04

00 02

2

01 *

Info32b

01

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

03

1

00

03

02

04

03

02

01

00

04

00 02

2

03 01

*

Info32b

01

*

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

03

1

00

03

02

04

03

02

01

00

04

03 01

*

02

00

2

Info32b

01

*

*

02 *

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

03

1

00

03

02

*

04

03

02

01

00

04

04 03

01 *

02

00

2

Info32b

01

*

02 *

*

*

Syst` emes d’Exploitation

*

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

03

1

00

03

02

*

04

03

02

01

00

04

04 03

01 *

02

00

2

Info32b

01

*

02 *

*

*

Syst` emes d’Exploitation

*

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

03

1

00

03

02

*

04

03

02

01

00

04

04 03

01 *

02

00

2

Info32b

01

*

02 *

*

*

Syst` emes d’Exploitation

*

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

03

1

00

03

02

*

04

03

*

03

02

01

00

04

04

01 *

02

00

2

Info32b

01

01 02

*

*

*

Syst` emes d’Exploitation

*

*

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

03

1

00

03

02

*

04

03

*

03

02

01

04

01 02

*

00

04

01 *

02

00

2

Info32b

01

*

*

Syst` emes d’Exploitation

00 *

*

*

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

03

1

00

03

02

*

04

03

*

03

02

01

04

01 02

*

00

04

01 *

02

00

2

Info32b

01

*

*

Syst` emes d’Exploitation

00 *

*

*

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 3 cadres 03 0

02

01

03

1

00

03

00 02

2 *

04

03

03

*

02

01

04

01 02

*

00

04

01 *

02

*

*

00 *

*

*

Total : 9 d´efauts Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03

02

01

00

03

02

04

03

02

01

00

04

0 1 2 3

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

00

03

02

04

03

02

01

00

04

03

1 2 3 * Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

00

03

02

04

03

02

01

00

04

03

1

02

2 3 * Info32b

* Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

00

03

02

04

03

02

01

00

04

03

1

02

2

01

3 * Info32b

*

* Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

03

02

04

03

02

01

00

04

03

1

02

2

01

3

00 *

Info32b

00

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

03

02

04

03

02

01

00

04

03

1

02

2

01

3

00 *

Info32b

00

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

03

02

04

03

02

01

00

04

03

1

02

2

01

3

00 *

Info32b

00

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

03

02

03

1

04

03

02

01

00

04

04 02

2

01

3

00 *

Info32b

00

*

*

*

Syst` emes d’Exploitation

* Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

03

02

03

1

04

03

02

01

00

04

04 02

2

03 01

3

00 *

Info32b

00

*

*

*

Syst` emes d’Exploitation

*

* Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

03

02

03

1

04

03

02

01

00

04

04 02

2

03 01

3

02 00

* Info32b

00

*

*

*

Syst` emes d’Exploitation

*

*

* Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

03

02

03

1

04

03

02

02

00

04

03 01

3

02 00

*

01

04

2

Info32b

00

*

*

*

Syst` emes d’Exploitation

01 *

*

*

* Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

03

02

03

1

04

03

02

02

04

03

3

02 00

*

00 00

01

*

01

04

2

Info32b

00

*

*

Syst` emes d’Exploitation

01 *

*

*

*

*

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

03

02

03

1

04

03

02

02

02 00

*

04

04

03

3 *

00 00

01

*

01

04

2

Info32b

00

*

Syst` emes d’Exploitation

01 *

*

*

*

*

Nicolas Sabouret

* 11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Anomalie de Belady Algorithmes de type FIFO sur certaines instances. . .

Plus de cadres → plus de d´efauts ! Exemple : avec 4 cadres 03 0

02

01

00

03

02

03

1

04

03

02

04 02

2

02 00

*

04

04

03

3 *

00 00

01

*

01

01

*

*

*

*

*

*

*

Total : 10 d´efauts Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

11/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37

03 0

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 0

03 0

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 0

2A 0

Info32b

03 0

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 0

2A 0

03 0

0

1F

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 0

2A 0

03 0

0

1F

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 0

2A 0

03 0

0

1F

0

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 0

2A 0

0

1F

03 0

0 0

48

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 0

2A 0

0

1F

03 1

0 0

48

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 1

2A 0

0

1F

03 1

0 0

48

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 1

2A 1

0

1F

03 1

0 0

48

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 1

2A 1

1

1F

03 1

0 0

48

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 1

2A 1

1

1F

03 1

0 1

48

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 1

2A 1

1

1F

03 1

1 1

48

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 04 1

2A 1

1

1F

31 0

1 1

48

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 0

2A 1

1

1F

31 0

1 1

48

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 0

2A 0

1

1F

31 0

1 1

48

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 0

2A 1

1

1F

31 0

1 1

48

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 0

2A 1

0

03

31 0

1 1

48

12 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 0

2A 1

0

03

31 0

1 0

48

76 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 0

2A 0

0

03

31 0

1 0

48

76 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 0

2A 0

0

03

31 0

0 0

1F

76 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 0

2A 0

0

03

31 1

0 0

1F

76 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 1

2A 0

0

03

31 1

0 0

1F

76 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 1

2A 1

0

03

31 1

0 0

1F

76 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 1

2A 1

1

03

31 1

0 0

1F

76 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 1

2A 1

1

03

31 1

0 1

1F

76 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 1

2A 1

1

03

31 1

1 1

1F

76 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Seconde chance Principe Bit de seconde chance remis `a 0 lorsqu’on re-visite une page Lorsqu’on a besoin de lib´erer un cadre : Si bit(cadre courant)=0, mettre le bit `a 1 et passer Sinon utiliser le cadre (et remettre le bit `a 0) 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 B1 1

2A 1

1

03

37 0

1 1

1F

76 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

12/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

0 1 2 3 4 5

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1 2 3 4 5 *

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2 3 4 5 *

Info32b

*

Syst` emes d’Exploitation

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3 4 5 *

Info32b

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

1F

4 5 *

Info32b

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

-

2A

3

1F

4 5 *

Info32b

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

-

2A

3

1F

4

12

5 *

Info32b

*

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

31

B1

2A

03

76

2A

1F

37

03

1

04

2

-

2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

31

B1

2A

03

76

2A

1F

37

03

1

04

2

-

2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

+

04

2

-

2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

+

04

2

+

-

2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

+

04

2

+

-

2A

3

+

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

+

04

2

+

-

2A

3

+ +

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

+

04

2

+

-

2A

3

+ +

1F

4

12

5

+

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

+

04

2

+

-

2A

3

+ +

1F

4

12

5

+

48 + *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31 +

04

2

B1

2A

03

76

2A

1F

37

31

+

-

2A

3

+ +

1F

4

12

5

+

48 + *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31 +

04

2

-

2A

2A

03

76

2A

1F

37

B1

+ +

1F

4

B1

31

+

3

12

5

+

48 + *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31 +

04

2

-

2A

2A

03

76

2A

1F

37

B1 -

+ +

1F

4

B1

31

+

3

12

5

+

48 + *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31 +

04

2

-

2A

2A

03

76

2A

1F

37

B1 - +

+ +

1F

4

B1

31

+

3

12

5

+

48 + *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31 +

04

2

-

2A

5

03

76

2A

1F

37

- + 03

+

12

2A

B1

+

1F

4

B1

31

+

3

+

48 + *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31 +

04

2

-

2A

5

03

76

2A

1F

37

- + 03

+

12

2A

B1

+

1F

4

B1

31

+

3

76

+

48 + *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

*

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31 +

04

2

-

2A

5

03

76

- +

2A

1F

37

03

+

12

2A

B1

+

1F

4

B1

31

+

3

76

+

48 + *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

*

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31 +

04

2

-

2A

5

03

76

- +

*

*

*

*

Syst` emes d’Exploitation

37

76

+

*

1F

-

48 + *

2A

03

+

12

2A

B1

+

1F

4

B1

31

+

3

Info32b

48

1F *

*

*

Nicolas Sabouret

*

*

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31 +

04

2

-

2A

5

03

76

*

*

*

*

- +

-

Syst` emes d’Exploitation

37

+

03

+

76

+

*

37

1F

+

48 + *

2A

B1

+

12

2A

+

+

1F

4

B1

31

+

3

Info32b

48

+

1F + *

*

*

Nicolas Sabouret

*

*

*

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion FIFO Second chance

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

03

1

31 +

04

2

-

3 4 5

76

*

*

*

*

- +

-

37

+

03

+

76

+

*

37

1F

+

48 + *

2A

B1

+

12

03

+

+

1F

2A

31

+

2A

B1

+

1F + *

*

*

*

*

*

Total : 12 d´efauts Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

13/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Plan

1

Pr´esentation du probl`eme

2

Algorithmes type FIFO

3

Algorithmes bas´es sur l’utilisation Principe LFU NRU LRU

4

Conclusion

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

14/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Principe g´en´eral Retirer la page la plus pertinente La page la moins utilis´ee (LFU) Une page peu utilis´ee (NRU) La page la moins r´ecemment utilis´ee (LRU)

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

15/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Principe g´en´eral Retirer la page la plus pertinente La page la moins utilis´ee (LFU) Une page peu utilis´ee (NRU) La page la moins r´ecemment utilis´ee (LRU)

Avantage : moins de d´efaut de page En pratique, FIFO-2 fait 15 `a 20 % plus de d´efauts que LRU

Inconv´enient : algorithmes plus complexes Espace m´emoire suppl´ementaire Temps de calcul `a chaque appel de page

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

15/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 0 0 0 0 0 0 0 0 0 0

Nicolas Sabouret

Date

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 0 0 0 0 0 0 0 0 0 0

Nicolas Sabouret

Date

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 1 0 0 0 0 0 0 0 0 0

Nicolas Sabouret

Date 1

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 1 1 0 0 0 0 0 0 0 0

Nicolas Sabouret

Date 1 2

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

2A

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 1 1 0 0 1 0 0 0 0 0

Nicolas Sabouret

Date 1 2

3

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

2A

1F

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 1 1 0 1 1 0 0 0 0 0

Nicolas Sabouret

Date 1 2 4 3

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

2A

1F

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 1 1 0 1 2 0 0 0 0 0

Nicolas Sabouret

Date 1 2 4 3

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

2A

1F

12

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 1 1 1 1 2 0 0 0 0 0

Nicolas Sabouret

Date 1 2 6 4 3

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

Info32b

04

2A

1F

12

48

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 1 1 1 1 2 0 0 1 0 0

Nicolas Sabouret

Date 1 2 6 4 3

7

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

04

2A

1F

12

48

Usage = 1, Date = min({1,2,4,6,7})

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 1 1 1 1 2 1 0 1 0 0

Nicolas Sabouret

Date 1 2 6 4 3 8 7

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

B1

2A

1F

12

48

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 1 1 1 1 2 1 0 1 0 1

Nicolas Sabouret

Date 1 2 6 4 3 8 7 9

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

B1

2A

1F

12

48

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 1 1 1 1 3 1 0 1 0 1

Nicolas Sabouret

Date 1 2 6 4 3 8 7 9

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

B1

2A

03

12

48

Usage = 1, Date = min({8,9,4,6,7})

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 2 1 1 1 3 1 0 1 0 1

Nicolas Sabouret

Date 11 2 6 4 3 8 7 9

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

B1

2A

03

76

48

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 2 1 1 1 3 1 0 1 1 1

Nicolas Sabouret

Date 11 2 6 4 3 8 7 12 9

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

B1

2A

03

76

48

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 2 1 1 1 4 1 0 1 1 1

Nicolas Sabouret

Date 11 2 6 4 3 8 7 12 9

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31

Info32b

B1

2A

03

76

1F

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 2 1 1 2 4 1 0 1 1 1

Nicolas Sabouret

Date 11 2 6 14 3 8 7 12 9

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Frequently Used Principe Noter le taux d’utilisation de chaque page du processus. Ü choisir la page la moins utilis´ee en cas d’´egalit´e : FIFO

Exemple : 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 37

B1

2A

03

76

1F

Usage = 1, Date = min({8,9,12})

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Usage 2 1 1 2 4 1 1 1 1 1

Nicolas Sabouret

Date 11 2 6 14 3 8 15 7 12 9

16/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

0 1 2 3 4 5

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1 2 3 4 5 *

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2 3 4 5 *

Info32b

*

Syst` emes d’Exploitation

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3 4 5 *

Info32b

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

1F

4 5 *

Info32b

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

1F

4 5 *

Info32b

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

1F

4

12

5 *

Info32b

*

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

03

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

03

1F

4

12

5

76 48

*

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

*

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

03

1F

4

12

5

76 48

*

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

*

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

03

1F

4

12

5

76 48

*

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

1F *

*

*

Nicolas Sabouret

*

*

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

31 04

2

37 37

B1 2A

3

03

1F

4

12

5

76 48

*

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

1F *

*

*

Nicolas Sabouret

*

*

*

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

03

1

31

B1

2A

03

76

2A

1F

31 04

2

37 37

B1 2A

3

03

1F

4

12

5

76 48

*

*

*

*

*

*

1F *

*

*

*

*

*

Total : 12 d´efauts Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

17/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LFU : avantages et inconv´enients Nombre total d’utilisation 7 Probl` eme : une page beaucoup utilis´ee reste toujours

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

18/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LFU : avantages et inconv´enients Nombre total d’utilisation 7 Probl` eme : une page beaucoup utilis´ee reste toujours 3 Solution : remettre usage `a 0 p´eriodiquement fenˆetre glissante trop coˆ uteux ` a impl´ementer. . .

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

18/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LFU : avantages et inconv´enients Nombre total d’utilisation 7 Probl` eme : une page beaucoup utilis´ee reste toujours 3 Solution : remettre usage `a 0 p´eriodiquement fenˆetre glissante trop coˆ uteux ` a impl´ementer. . .

Performance 3 Beaucoup moins de d´efaut de page que les autres m´ethodes

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

18/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LFU : avantages et inconv´enients Nombre total d’utilisation 7 Probl` eme : une page beaucoup utilis´ee reste toujours 3 Solution : remettre usage `a 0 p´eriodiquement fenˆetre glissante trop coˆ uteux ` a impl´ementer. . .

Performance 3 Beaucoup moins de d´efaut de page que les autres m´ethodes 7 Temps de calcul + m´emoire

M´emoire 7 64 bits de plus dans chaque ligne de la table des pages

Temps 7 O(n) op´erations `a chaque page manquante Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

18/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Observations Compter les utilisation est coˆ uteux → FIFO-2 = 1 seul bit : m´emoire + temps !

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

19/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Observations Compter les utilisation est coˆ uteux → FIFO-2 = 1 seul bit : m´emoire + temps ! Certaines pages deviennent inutiles → remettre `a 0 p´eriodiquement

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

19/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Observations Compter les utilisation est coˆ uteux → FIFO-2 = 1 seul bit : m´emoire + temps ! Certaines pages deviennent inutiles → remettre `a 0 p´eriodiquement Les pages dans lesquelles on ´ecrit sont plus susceptibles d’ˆetres r´eutilis´ees un peu plus tard, en g´en´eral. . .

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

19/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Observations Compter les utilisation est coˆ uteux → FIFO-2 = 1 seul bit : m´emoire + temps ! Certaines pages deviennent inutiles → remettre `a 0 p´eriodiquement Les pages dans lesquelles on ´ecrit sont plus susceptibles d’ˆetres r´eutilis´ees un peu plus tard, en g´en´eral. . . Ü Ajouter un 2e bit pour les pages modifi´ees

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

19/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 0 0 0 0 0 0 0 0

M 0 0 0 0 0 0 0 0 0 0

Date

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 0 0 0 0 0 0 0 0

M 0 0 0 0 0 0 0 0 0 0

Date

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r 03 R=1 M=0

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 1 0 0 0 0 0 0 0 0 0

M 0 0 0 0 0 0 0 0 0 0

Date 1

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

03

04

R=1 M=0

R=1 M=1

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 1 1 0 0 0 0 0 0 0 0

M 0 1 0 0 0 0 0 0 0 0

Date 1 2

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

03

04

2A

R=1 M=0

R=1 M=1

R=1 M=0

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 1 1 0 0 1 0 0 0 0 0

M 0 1 0 0 0 0 0 0 0 0

Date 1 2

3

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

03

04

2A

1F

R=1 M=0

R=1 M=1

R=1 M=0

R=1 M=1

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 1 1 0 1 1 0 0 0 0 0

M 0 1 0 1 0 0 0 0 0 0

Date 1 2 4 3

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r 03

04

2A

1F

R=1 M=0

R=1 M=1

R=1 M=0

R=1 M=1

RESET

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 1 1 0 1 1 0 0 0 0 0

M 0 1 0 1 0 0 0 0 0 0

Date 1 2 4 3

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r 03

04

2A

1F

R=0 M=0

R=0 M=1

R=0 M=0

R=0 M=1

RESET

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 0 0 0 0 0 0 0 0

M 0 1 0 1 0 0 0 0 0 0

Date 1 2 4 3

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

03

04

2A

1F

R=0 M=0

R=0 M=1

R=1 M=1

R=0 M=1

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 0 0 1 0 0 0 0 0

M 0 1 0 1 1 0 0 0 0 0

Date 1 2 4 3

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

03

04

2A

1F

12

R=0 M=0

R=0 M=1

R=1 M=1

R=0 M=1

R=1 M=0

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 1 0 1 0 0 0 0 0

M 0 1 0 1 1 0 0 0 0 0

Date 1 2 6 4 3

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

03

04

2A

1F

12

48

R=0 M=0

R=0 M=1

R=1 M=1

R=0 M=1

R=1 M=0

R=1 M=0

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 1 0 1 0 0 1 0 0

M 0 1 0 1 1 0 0 0 0 0

Date 1 2 6 4 3

7

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

31

04

2A

1F

12

48

R=1 M=0

R=0 M=1

R=1 M=1

R=0 M=1

R=1 M=0

R=1 M=0

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 1 0 1 1 0 1 0 0

M 0 1 0 1 1 0 0 0 0 0

Date 1 2 6 4 3 8 7

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r 31

04

2A

1F

12

48

R=1 M=0

R=0 M=1

R=1 M=1

R=0 M=1

R=1 M=0

R=1 M=0

RESET

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 1 0 1 1 0 1 0 0

M 0 1 0 1 1 0 0 0 0 0

Date 1 2 6 4 3 8 7

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r 31

04

2A

1F

12

48

R=0 M=0

R=0 M=1

R=0 M=1

R=0 M=1

R=0 M=0

R=0 M=0

RESET

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 0 0 0 0 0 0 0 0

M 0 1 0 1 1 0 0 0 0 0

Date 1 2 6 4 3 8 7

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

31

04

2A

1F

B1

48

R=0 M=0

R=0 M=1

R=0 M=1

R=0 M=1

R=1 M=0

R=0 M=0

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 0 0 0 0 0 0 0 1

M 0 1 0 1 1 0 0 0 0 0

Date 1 2 6 4 3 8 7 9

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

31

04

2A

1F

B1

48

R=0 M=0

R=0 M=1

R=1 M=1

R=0 M=1

R=1 M=0

R=0 M=0

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 0 0 1 0 0 0 0 1

M 0 1 0 1 1 0 0 0 0 0

Date 1 2 6 4 3 8 7 9

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

31

04

2A

1F

B1

03

R=0 M=0

R=0 M=1

R=1 M=1

R=0 M=1

R=1 M=0

R=1 M=1

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 1 0 0 0 1 0 0 0 0 1

M 1 1 0 1 1 0 0 0 0 0

Date 11 2 6 4 3 8 7 9

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

76

04

2A

1F

B1

03

R=1 M=0

R=0 M=1

R=1 M=1

R=0 M=1

R=1 M=0

R=1 M=1

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 1 0 0 0 1 0 0 0 1 1

M 1 1 0 1 1 0 0 0 0 0

Date 11 2 6 4 3 8 7 12 9

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r 76

04

2A

1F

B1

03

R=1 M=0

R=0 M=1

R=1 M=1

R=0 M=1

R=1 M=0

R=1 M=1

RESET

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 1 0 0 0 1 0 0 0 1 1

M 1 1 0 1 1 0 0 0 0 0

Date 11 2 6 4 3 8 7 12 9

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r 76

04

2A

1F

B1

03

R=0 M=0

R=0 M=1

R=0 M=1

R=0 M=1

R=0 M=0

R=0 M=1

RESET

Info32b

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 0 0 0 0 0 0 0 0

M 1 1 0 1 1 0 0 0 0 0

Date 11 2 6 4 3 8 7 12 9

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

76

04

2A

1F

B1

03

R=0 M=0

R=0 M=1

R=1 M=1

R=0 M=1

R=0 M=0

R=0 M=1

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 0 0 1 0 0 0 0 0

M 1 1 0 1 1 0 0 0 0 0

Date 11 2 6 4 3 8 7 12 9

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

76

04

2A

1F

B1

03

R=0 M=0

R=0 M=1

R=1 M=1

R=1 M=1

R=0 M=0

R=0 M=1

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 0 1 1 0 0 0 0 0

M 1 1 0 1 1 0 0 0 0 0

Date 11 2 6 4 3 8 7 12 9

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Not Recently Used Principe 2 bits : R (page r´ef´erenc´ee) et M (page modifi´ee) Lecture ou ´ecriture → R=1 ; ´ecriture → M=1 Priorit´e : (R=1,M=1) > (R=1,M=0) > (R=0,M=1) > (R=0,M=0) FIFO en cas d’´egalit´e

Tous les R sont remis `a 0 chaque K cycles 03r 04w 2Ar 1Fw 2Aw 12r 48r 31r B1r 2Ar 03w 76r 2Aw 1Fw 37r

Info32b

76

04

2A

1F

37

03

R=0 M=0

R=0 M=1

R=1 M=1

R=1 M=1

R=1 M=0

R=0 M=1

Syst` emes d’Exploitation

Page 03 04 12 1F 2A 31 37 48 76 B1

Nicolas Sabouret

R 0 0 0 1 1 0 1 0 0 0

M 1 1 0 1 1 0 0 0 0 0

Date 11 2 6 4 3 8 15 7 12 9

20/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r

04w

2Ar

1Fw 2Aw

12r

48r

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

0 1 2 3 4 5

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

12r

48r

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

0310

1 2 3 4 5 *

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

12r

48r

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

0310

1

0411

2 3 4 5 *

Info32b

*

Syst` emes d’Exploitation

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

12r

48r

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

0310

1

0411

2

2A10

3 4 5 *

Info32b

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

12r

48r

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

0310

1

0411

2

2A10

3

1F11

4 5 *

Info32b

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

48r

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

00

0411

2

01

2A10

3

00

1F11 01

4 5 *

Info32b

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

48r

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

00

0411

2

01

2A10

3

00

11

1F11 01

4 5 *

Info32b

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

48r

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

00

0411

2

01

2A10

3

00

11

1F11 01

4

1210

5 *

Info32b

*

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

00

0411

2

01

2A10

3

00

11

1F11 01

4

1210

5

4810 *

Info32b

48r

*

*

*

*

Syst` emes d’Exploitation

*

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

0411

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

3110

00

2

01

2A10

3

00

11

1F11 01

4

1210

5

4810 *

Info32b

48r

*

*

*

*

Syst` emes d’Exploitation

*

*

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

0411

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

3110 00

00

2

01

2A10

3

00

11

01

1F11 01

4

1210

5

00

4810 *

Info32b

48r

*

*

*

*

Syst` emes d’Exploitation

*

00

*

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

0411

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

3110 00

00

2

01

2A10

3

00

11

01

1F11 01

4

1210

5

00

4810 *

Info32b

48r

*

*

*

*

Syst` emes d’Exploitation

*

B110

00

*

*

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

0411

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

3110 00

00

2

01

2A10

3

00

11

01

11

1F11 01

4

1210

5

00

4810 *

Info32b

48r

*

*

*

*

Syst` emes d’Exploitation

*

B110

00

*

*

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

0411

31r

B1r

2Ar

03w

76r

2Aw 1Fw

37r

3110 00

00

2

01

2A10

3

00

11

01

11

1F11 01

4

1210

5

00

4810 *

Info32b

48r

*

*

*

*

Syst` emes d’Exploitation

*

B110 0311

00

*

*

*

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

0411

31r

B1r

2Ar

03w

3110 00

00

2

76r

2Aw 1Fw

37r

7610

01

2A10

3

00

11

01

11

1F11 01

4

1210

5

00

4810 *

Info32b

48r

*

*

*

*

Syst` emes d’Exploitation

*

B110 0311

00

*

*

*

Nicolas Sabouret

*

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

0411

31r

B1r

2Ar

03w

3110 00

00

2

76r

2Aw 1Fw

37r

7610 00

01

2A10

3

00

11

01

11

01

1F11 01

4

1210

5

00

4810 *

Info32b

48r

*

*

*

*

Syst` emes d’Exploitation

*

B110 0311

00

*

00

*

*

Nicolas Sabouret

01

*

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

0411

31r

B1r

2Ar

03w

3110 00

00

2

76r

2Aw 1Fw

37r

7610 00

01

2A10

3

00

11

01

11

01

11

1F11 01

4

1210

5

00

4810 *

Info32b

48r

*

*

*

*

Syst` emes d’Exploitation

*

B110 0311

00

*

00

*

*

Nicolas Sabouret

01

*

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

0411

31r

B1r

2Ar

03w

3110 00

00

2

76r

2Aw 1Fw

2A10

7610 00

00

11

01

11

01

1F11 01

4 5

00

4810 *

*

*

11

11

1210

*

37r

01

3

Info32b

48r

*

Syst` emes d’Exploitation

*

B110 0311

00

*

00

*

*

Nicolas Sabouret

01

*

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

0411

31r

B1r

2Ar

03w

3110 00

00

2

76r

2Aw 1Fw

2A10

7610 00

00

11

01

11

01

1F11 01

4 5

00

4810 *

*

*

11

11

1210

*

37r

01

3

Info32b

48r

*

Syst` emes d’Exploitation

*

B110 0311

00

*

00

*

*

Nicolas Sabouret

3710

01

*

*

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03r 0

04w

2Ar

1Fw 2Aw

0310

1

12r

48r

2

B1r

2Ar

03w

3110 00

00

0411

31r

76r

2Aw 1Fw

7610 00

01

2A10

3

00

11

01

11

01

1F11 01

4 5

00

4810 *

*

*

11

11

1210

*

37r

*

*

B110 0311

00

*

00

*

*

3710

01

*

*

Total : 11 d´efauts Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

21/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

NRU : avantages et inconv´enients

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

22/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

NRU : avantages et inconv´enients

Performance 3 Peu de d´efaut de page 3 Peu coˆ uteux en m´emoire 7 Temps de calcul : O(n) `a chaque reset et `a chaque page manquante

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

22/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

NRU : avantages et inconv´enients

Performance 3 Peu de d´efaut de page 3 Peu coˆ uteux en m´emoire 7 Temps de calcul : O(n) `a chaque reset et `a chaque page manquante

Gain En pratique, gain trop faible par rapport `a FIFO-2

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

22/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Recently Used Principe File (FIFO) avec remise en fin `a chaque utilisation Impl´ementation mat´erielle → calcul en O(1)

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

23/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Least Recently Used Principe File (FIFO) avec remise en fin `a chaque utilisation Impl´ementation mat´erielle → calcul en O(1)

Impl´ementation Matrice triangulaire de dimension N = nombre de cadres sans la diagonale, tout initialis´e ` a0

0 1 2 3 4 5 Info32b

0 1 2 3 0 0 0 0 0 0

Syst` emes d’Exploitation

4 0 0 0 0

5 0 0 0 0 0

Nicolas Sabouret

23/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1 2 3 4

1

2

3

4

5

0

0

0

0

0

0

0

0

0

0

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1 2 3 4

1

2

3

4

5

0

0

0

0

0

0

0

0

0

0

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

1

1

1

1

1

0

0

0

0

0

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

1

1

1

1

1

0

0

0

0

0

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

1

1

1

1

1

0

0

0

0

0

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03 04

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

1

1

1

1

1

1

1

1

0

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03 04

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

1

1

1

1

1

1

1

1

0

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03 04 2A

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

1

1

1

0

1

1

1

1

1

1

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03 04 2A

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

1

1

1

0

1

1

1

1

1

1

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03 04 2A 1F

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

1

1

0

0

1

1

0

1

1

1

1

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03 04 2A 1F

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

1

1

0

0

1

1

0

1

1

1

1

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03 04 2A 1F

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

1

1

0

0

1

1

1

1

1

1

1

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03 04 2A 1F

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

1

1

0

0

1

1

1

1

1

1

1

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03 04 2A 1F 12

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

0

1

0

0

0

1

1

0

1

0

1

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03 04 2A 1F 12

2 3 4

1

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

0

1

0

0

0

1

1

0

1

0

1

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03 04 2A 1F 12 48

2 3 4

1

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

0

0

0

0

0

0

1

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 03 04 2A 1F 12 48

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

0

0

0

0

0

0

1

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 04 2A 1F 12 48

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

1

1

1

1

1

0

0

0

0

1

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 04 2A 1F 12 48

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

1

1

1

1

1

0

0

0

0

1

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 B1 2A 1F 12 48

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

1

1

1

1

1

1

1

1

1

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 B1 2A 1F 12 48

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

1

1

1

1

1

1

1

1

1

0

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 B1 2A 1F 12 48

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

1

1

1

0

1

1

1

1

1

1

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 B1 2A 1F 12 48

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

1

1

1

0

1

1

1

1

1

1

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 B1 2A 03 12 48

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

1

1

0

0

1

1

0

1

1

1

1

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 B1 2A 03 12 48

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

1

1

0

0

1

1

0

1

1

1

1

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 B1 2A 03 76 48

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

0

1

0

0

0

1

0

0

1

0

1

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 B1 2A 03 76 48

2 3 4

1

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

0

1

0

0

0

1

0

0

1

0

1

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 B1 2A 03 76 48

2 3 4

1

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

0

1

0

0

0

1

1

1

1

0

1

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 B1 2A 03 76 48

2 3 4

1

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

0

1

0

0

0

1

1

1

1

0

1

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 B1 2A 03 76 1F

2 3 4

1

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

0

0

0

0

0

0

1

1

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 31 B1 2A 03 76 1F

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

0

0

0

0

0

0

0

0

0

1

1

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 37 B1 2A 03 76 1F

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

LRU : impl´ementation Impl´ementation Matrice triangulaire de dimension N = nombre de cadres Utilisation d’une page dans le cadre i → remettre la ligne i `a 1 puis la colonne i `a 0 Ü Cadre le plus ancien (`a utiliser) = ligne est remplie de 0, colonne remplie de 1 (sauf ligne i) 0 0 1

1

2

3

4

5

1

1

1

1

1

0

0

0

0

1

1

0

0

0

03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 37 B1 2A 03 76 1F

2 3 4

0

5 Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

24/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

0 1 2 3 4 5

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1 2 3 4 5 *

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2 3 4 5 *

Info32b

*

Syst` emes d’Exploitation

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3 4 5 *

Info32b

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

1F

4 5 *

Info32b

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

2A 1F

4 5 *

Info32b

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

2A 1F

4

12

5 *

Info32b

*

*

*

*

Syst` emes d’Exploitation

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

31

B1

2A

03

76

2A

1F

37

03

1

04

2

2A

3

2A 1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

2A

3

2A 1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

2A 1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

2A

2A

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

2A

2A 03

1F

4

12

5

48 *

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

2A

2A 03

1F

4

12

5

76 48

*

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

*

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

2A

1F

37

31 04

2

B1 2A

3

2A

2A

2A 03

1F

4

12

5

76 48

*

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

*

*

*

Nicolas Sabouret

*

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

04

1F

37

B1 2A

3

2A

2A

4

2A 03

1F 12

5

76 48

*

2A

31

2

Info32b

48

*

*

*

*

Syst` emes d’Exploitation

*

1F *

*

*

Nicolas Sabouret

*

*

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

03

1

31

B1

2A

03

76

04

1F

3

37

2A

2A

4

2A 03

1F 12

5

76 48

*

37

B1 2A

*

2A

31

2

Info32b

48

*

*

*

Syst` emes d’Exploitation

*

1F *

*

*

Nicolas Sabouret

*

*

*

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Compter les d´efauts 03 0

04

2A

1F

2A

12

48

03

1

31

B1

2A

03

76

1F

31 04

2 3

37

2A

2A

4

2A 03

1F 12

5

76 48

*

37

B1 2A

*

2A

*

*

*

*

1F *

*

*

*

*

*

Total : 12 d´efauts Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

25/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Allocation optimale Exercice (pour finir) Quel est le nombre minimal de d´efaut sur cet exemple ? 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

26/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Allocation optimale Exercice (pour finir) Quel est le nombre minimal de d´efaut sur cet exemple ? 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 Ü 10 d´efauts min car il y a 10 pages diff´erentes. . . 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 0

03

1

37 04

2

31 2A

3

1F

4

12

5

48 *

Info32b

B1

*

*

*

*

*

76 *

Syst` emes d’Exploitation

*

*

* Nicolas Sabouret

26/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion Principe LFU NRU LRU

Allocation optimale Exercice (pour finir) Quel est le nombre minimal de d´efaut sur cet exemple ? 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 Ü 10 d´efauts min car il y a 10 pages diff´erentes. . . 03 04 2A 1F 2A 12 48 31 B1 2A 03 76 2A 1F 37 0

03

1

37 04

2

31 2A Total : 10 d´efauts

3

1F

4

12

5

48 *

Info32b

B1

*

*

*

*

*

76 *

Syst` emes d’Exploitation

*

*

* Nicolas Sabouret

26/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion

Plan

1

Pr´esentation du probl`eme

2

Algorithmes type FIFO

3

Algorithmes bas´es sur l’utilisation

4

Conclusion

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

27/28

Pr´ esentation du probl` eme Algorithmes type FIFO Algorithmes bas´ es sur l’utilisation Conclusion

Ce qu’il faut retenir

Politique de remplacement de page FIFO (avec bit de seconde chance) LRU (impl´ement´ee au niveau mat´eriel) Tracer l’ex´ecution et compter les d´efauts

Info32b

Syst` emes d’Exploitation

Nicolas Sabouret

28/28