Discussion :

[hacksi]

Bonjour,

quelqu'un pourrait-il m'expliquer l'algorithme de l'horlage de gestion des défauts de pages mémoire (je sais ça n'a rien à voir avec un algorithme de programmation mais je tente ma chance).

Je pense que j'ai un problème dans l'initialisation de l'algorithme.

Merci

[pseudocode]

quelqu'un pourrait-il m'expliquer l'algorithme de l'horlage de gestion des défauts de pages mémoire (je sais ça n'a rien à voir avec un algorithme de programmation mais je tente ma chance).

C'est juste une FIFO avec un flag supplémentaire sur chaque élément. Ce flag est un booléen qui indique si l'élément a été utilisé récemment.

Lorsque tu dois supprimer un élément, au lieu de toujours prendre celui qui est en queue comme dans une FIFO classique, tu pars de la queue et tu supprimes le premier élément rencontré qui a son flag à "false".

[hacksi]

au départ, tout est à vrai ou faux ?

[pseudocode]

au départ, tout est à vrai ou faux ?

Quand tu ajoutes un élément, tu mets son flag à "true". A priori, si tu l'ajoutes c'est que tu vas l'utiliser .

Tu passes les flags de "true" a "false" lors de la suppression d'un élément (pendant que tu parcours ta pile à la recherche du premier élément qui a son flag a false).

[hacksi]

Oui mais au tout début, tout est à vrai ou à faux ?

[pseudocode]

Oui mais au tout début, tout est à vrai ou à faux ?

au début de quoi ? C'est une pile FIFO. Au début elle est vide.

[hacksi]

je ne pense pas comprendre ce que tu dis. Moi j'essaye de faire l'algo en mettant en cercle et en essayant de faire tourner un pointeur et en changeant la référence.

[pseudocode]

Moi j'essaye de faire l'algo en mettant en cercle et en essayant de faire tourner un pointeur et en changeant la référence.

Oui, ca c'est l'implémentation de la pile FIFO.

Mais au départ, ta pile est vide. Donc tu n'as pas d'élément dans ta pile. Donc ils n'ont pas de valeur "de début".

[hacksi]

bah il faut bien que les références soient initialisées à une valeur de départ...

[pseudocode]

bah il faut bien que les références soient initialisées à une valeur de départ...

On va reprendre le concept.
1. Tu as une FIFO implémentée avec un buffer circulaire
2. Chaque case de ton buffer possède 2 attributs : flag et valeur
3. Tu ajoutes des valeurs dans la fifo:
3a. la fifo n'est pas pleine, tu ajoutes un élément à la tête (set flag=true)
3b. la fifo est pleine, tu parcours les elements depuis la queue jusqu'a trouver le premier élément qui a son flag à false (en forcant flag=false sur tous les cases parcourues). Tu remplaces le contenu de cet élément par ta valeur (set flag=true)

[hacksi]

je teste et je te dis ce que ça donne

[hacksi]

bon bah ça marche pas, je dois louper une étape...

[Afnarel]

au début de quoi ? C'est une pile FIFO. Au début elle est vide.

Erf non FIFO c'est pas une pile mais une file
Edit : enfin j'ai vu plusieurs fois que certains appellent "Pile FIFO" une file mais ce n'est pas très judicieux à mon avis parce qu'une pile d'assiettes, si on essaie de retirer la première qu'on a posé (donc celle d'en bas), on a beaucoup de chances de renverser la pile entière...

[vingtage]

Bonjour, c'est une réponse tardive que j'apporte mais qui apporte quelques précisions pour les futurs lecteurs.

1. Conditions initiales:
On rempli chaque case avec les premières pages demandées.
On met le bit R à 0 pour chaque case.
On a à ce moment précis autant de défauts de page que de case.

2.algorithme de l'horloge (ou de la seconde chance)
Le pointeur pointe sur la plus ancienne page utilisée.
2.1Si on a besoin d'une page déjà chargée
On met le pointeur sur la plus ancienne page utilisée.
On recommence
2.2Si on a besoin d'une page qui n'est pas en mémoire
On a un défaut de page
On examine les pages dans le sens des aiguilles d'une montre.
La première page rencontrée ayant son bit R à 0 est remplacée.
Le bit R de la page ajoutée est mis à 1.
Si la page examinée a son bit R à 1, on le met à 0. (Explication du nom "seconde chance").

Remarques: Pour cette explication, il faut se représenter les pages chargées dans des cases, les cases réunies formant un cercle; on peut représenter le pointeur par une flèche partant du centre du cercle vers la page pointée.