salut à tous, voilà, j´ai une petite question sur cet algorithme dit optimal, qui consiste en gros à remplacer la page qui est le moins utilisée.

Comment les programmeurs ont ils pu réaliser un tel algo, car en réfléchissant un peu, je me dis que c´est impossible car il faut connaitre toutes les pages qui seront utilisées, et ça, je vois pas comment on peut le savoir à l´avance.

Où alors peut-etre font ils des estimations pour s´en rapprocher?

Enfin, voila, si quelqu´un connait bien le sujet, je suis tout ouie.

merci par avance

Alors en ce qui concerne la pagination, une technique simple consiste a associer a chaque page un compteur, ce compteur est en quelque sorte "la date de la derniere utilisation de la page"

On sait ainsi si une page a été accédée récemment ou non. De ce fait, on peut par exemple dire que les pages qui ont été accédées il y a longtemps sont moins prioritaires, et donc peuvent etre swappées.

Evidemment, ceci est l´idée de base. Apres, il y a surement plein de nouveaux algos plus puissants ou des nouveautés, mais cela, c´est un peu comme la question "que garder en mémoire cache ?"
--> il n´y a pas vraiment de regle. Chaque constructeur peut utiliser son propre moyen, basé tres souvent sur des probabilités et des statistiques.
Et je t´avoue que mes connaissances la dessus sont également pas plus avancées la dessus... (si tu trouves un bon site, je suis preneur)

Ah si, il y a quelque chose que j´oublie : le circuit "CAM" me semble t il : il s´agit d´un circuit fait pour la pagination. Ce circuit garde en mémoire un tableau qui, a chaque segment, donne son adresse physique. Ainsi, quand on interroge ce circuit, on cherche un segment spécifique, donc, si on utilisait un algorithmique normale, on serait obligé de le faire séquentiellement, donc de faire un "for" jusqu´a trouver le bon segment.

Le circuit CAM a la particularité d´etre parallele : ainsi, quand on cherche un segment, chaque case du tableau est comparée simultanément par un comparateur propre : ainsi, en 1 seul coup, on trouve le segment : plus besoin de faire des tests séquentiels...

Je pense que les algorithmes de swapping doivent également profiter de ces mises en parallele.

je te rassure ce n´est pas optimal... La raison est la suivante:
Tu peux mettre en place une technique d´adversaire. Suppose qu´un adversaire connaisse tes choix; tu peux stocker k pages. il fait k+1 requetes différentes. Il redemande ensuite la page que tu as choisi de ne pas stocker. boom ce n´est pas optimal...

Comment on travaille pour réaliser cette algorithme, on cherche a prouver des choses du style: Si j´avais tout a l´avance l´optimal est de OPT. Mon algorithme qui recoit les données au fur et a mesure ne sera jamais pire que 2*OPT.

Tu vois l´idée ?

Pour en revenir a la premiere idée : je veux compléter un truc :

"De ce fait, on peut par exemple dire que les pages qui ont été accédées il y a longtemps sont moins prioritaires, et donc peuvent etre swappées. "

--> Rien n´empeche bien entendu qu´on aie besoin a ce moment la de la page la plus vieille : donc on peut tres bien swapper cette page et la redemander juste apres (ce qui perd du temps, et n´était pas un choix judicieux)
Mais que veux tu... Il faut se dire que la page la plus vieille a statistiquement moins de chance d´etre demandée que la plus jeune, tout est une histoire de probabilité...

Oui tu as une histoire de modèle statistique.
Pour te donner une idée l´assertion suivante est fausse:
"la probabilité d´acceder a la page i est constante au cours du temps et ne dépend pas du passé".
Ce modèle statistique ne correspond pas a la réalite. On en construi d´autre qui son (avec une certaine probabilié) vrai. On utilise ensuite ce modèle d´accès au cache pour en retirer des propriété sur lesquels on fondent nos algorihtmes.

J´admire les mecs qui programment ces algos (pour le swapping et la mémoire cache)

Et ce sont davantage des mathématiciens que des informaticiens pour ce genre d´algos

tout a fait, les politiques mise en place par les informaticiens sont souvent les politiques naives du genre LRU (last recently used) ou dans d´autre domaine FIFO (on le voit beaucoup sur les grilles de calcul). Ils sont peu judicieux en terme de performances mais sont facil a implémenter...

sauf qu´à ce que j´en ai lu, le OPT est bien plus malin que ça et cherche réellement la page qui sera accédée dans le plus de temps.

Même si j´ai pas la moindre idée de ce qu´il y a derrière, je suppose que ça tient au fait que les machines moderne ne sont pas des environnements servant à démontrer l´indécidabilité de tel ou tel truc (je parle de "l´adversaire" de godrik), par contre chaque processus dispose de ses pages et ne peut pas (ou pas dans un cas normal) accéder aux autres.

Donc en utilisant ce genre de chose on peut déjà se dire que si un processus ne tourne jamais (disont qu´il attend un événement lointain), il n´a pas vraiment besoin de sa mémoire.
Donc je suppose que l´idée c´est d´exploiter ce que le système sait des processus, afin de gérer la pagination, plutot que de n´exploiter que les données statistique sur l´usage qui en a été fait.

Mais il ne s´agit que d´hypothèse de ma part, vu que j´ai juste du lire quelqes pdf là dessus.

ok, merci pour ces réponses

juste une petite remarque sur ce que tu à dis Fvirtman:

=>"De ce fait, on peut par exemple dire que les pages qui ont été accédées il y a longtemps sont moins prioritaires, et donc peuvent etre swappées."

Mais cet algo (arrete mois si je me trompe), c´est le LRU et non pas OPT, à moins que ce dernier se serve en partie du premier (ce qui fort probable).

Merci à tous.

@+

oui, et il y a aussi l´aspect que les pages récement utilisé sont probablement les pages du processus en cours d´execution. Donc autant ne pas les décharger...

tu as un lien sur OPT ?

ok.

Sinon, je n´ai pas de liens interessants. Tous les cours que j´ai trouvé se contentent de survoler le sujet.

pour résumer:

"L’algorithme NRU n’est pas optimal, mais il est souvent suffisant. Il est, de plus, simple a mettre en oeuvre, car il ne nécessite pas de materiel spécialisé, au contraire de l’algorithme LRU. L’algorithme FIFO est douteux, car il peut entraıner le retrait d’une page tres utile, référencée souvent depuis le début d’exécution
du processus."

...attend, je viens de trouver ça:

"Optimum (non programmable, il sert de référence. Cet algorithme a la prescience des pages qui seront utiles dans l´avenir et décharge au mieux les pages les moins nécessaires)"

Je ne comprend plus, c´est bien de l´OPT dont il parle là? Bon, alors je relance ma question, c´est quoi cet algo, il existe ou pas?

...En fait, je pense que l´OPT tend à se rapprocher de l´optimum, mais il ne l´est pas, comme tu l´a expliqué Godrik.

etant donnée que tu n´s pas clairvoyant, tu ne peux pas garantir l´optimalité. Par contre tu peux (peut etre) garantir qu´il n´existe pas d´instance qui te font perdre plus qu´un facteur x ou je ne sais pas quoi.

Dommage que je n´ai pas mon tanenbaum sous la main.

une source qui parle de OPT
http://deptinfo2.unice.fr/~dalle/IUP2/2002/Support_Systeme_IUP2_part5.ps.gz

De ce qui en est dit OPT est l´algorithme offline optimal. Il n´est donc pas utilisable en pratique puisquel´on ne connait pas le futur. On s´en sert comme point de reference. Trois algorithmes sont discutés dans le meme document FIFO, FIFO2emeChance et LRU.

ok, merci, c´est clair à présent, l´algo OPT n´est qu´une chimère.

sinon, ils parlent du LRU comme se rapprochant de l´OPT, mais existe-il un algo meilleur que LRU?

merci, @+

sur des cas particuliers probablement, mais le noyau n´a en fait qu´assez peu d´information pour baser sa décision... qu´est ce qui est utilisé sur Linux d´ailleurs ?

Bonne question. Je n´en ai pas la moindre idée.