Merci pour le lien, l'article de Jonathan Corbet est en effet très clair et je comprends un peu mieux le mécanisme.
Cependant, comme il le dit lui même, Son exemple est très simple (voire simpliste) : Il ne prend pas en compte les pages non-déplaçables (même s'il dit que le kernel essaye d'isoler les pages déplaçables d'une part et les pages non-déplaçables de l'autre).
Prenons quand même deux exemples simples (voire simplistes).
Soit une portion de mémoire définie par des bornes [ et ], des pages non-déplaçables U, des pages déplaçables M et des pages libres -. Dans cette portion de mémoire, on tente d'allouer 4 pages contigües.
Premier exemple : [-M-U--M-] L'algorithme commence à chercher les pages déplaçables depuis la droite et des places libres depuis la gauche. Le premier M (en seconde position) ira donc à la place du premier - (en dernière position). L'algorithme s’arrêtera sur le U qui est grosso-modo le milieu. [---U--MM]Et là c'est le drame.
Deuxième exemple : [M-M---M-MM] Pareil, l'algo va chercher les places libres à partir de la gauche et s'arrêter au milieu. Comme il n'y a qu'une place dans la moitié gauche, seul un M est déplaçable, alors qu'il est possible de trouver 4 pages contigües. [--M---MMMM]
Voilà ce qui me vient à l'esprit quand on me dit que l'algo s'arrête à la moitié.
Donc, ai-je loupé une subtilité ? Est ce que dans la pratique, ce genre de configuration est très hautement improbable ? Est ce que ce sont des worst case qu'on néglige ?
[^] # Re: Compactage mémoire
Posté par j_kerviel . En réponse à la dépêche Nouvelle version 2.6.35 du noyau Linux. Évalué à 3.
Cependant, comme il le dit lui même, Son exemple est très simple (voire simpliste) : Il ne prend pas en compte les pages non-déplaçables (même s'il dit que le kernel essaye d'isoler les pages déplaçables d'une part et les pages non-déplaçables de l'autre).
Prenons quand même deux exemples simples (voire simplistes).
Soit une portion de mémoire définie par des bornes [ et ], des pages non-déplaçables U, des pages déplaçables M et des pages libres -. Dans cette portion de mémoire, on tente d'allouer 4 pages contigües.
Premier exemple :
[-M-U--M-]L'algorithme commence à chercher les pages déplaçables depuis la droite et des places libres depuis la gauche. Le premier M (en seconde position) ira donc à la place du premier - (en dernière position). L'algorithme s’arrêtera sur le U qui est grosso-modo le milieu.[---U--MM]Et là c'est le drame.Deuxième exemple :
[M-M---M-MM]Pareil, l'algo va chercher les places libres à partir de la gauche et s'arrêter au milieu. Comme il n'y a qu'une place dans la moitié gauche, seul un M est déplaçable, alors qu'il est possible de trouver 4 pages contigües.[--M---MMMM]Voilà ce qui me vient à l'esprit quand on me dit que l'algo s'arrête à la moitié.
Donc, ai-je loupé une subtilité ? Est ce que dans la pratique, ce genre de configuration est très hautement improbable ? Est ce que ce sont des worst case qu'on néglige ?