La programmation des structures de données

La programmation des structures de données telle que la liste en Java laisse la possibilité à l'implanteur de choisir des cases contiguës ou non contiguës en mémoire. Cette contrainte est donc forcément dans le bytecode que la JVM va prendre en charge. Quand je parle de la mémoire c'est forcément la mémoire vive pendant l'exécution du programme qui manipule la liste (création et entrée des données dans cette dernière).
Si on s'intéresse au cas du 32bits (x86), La mémoire est forcément segmentée.
Peut on dire que la liste doit se trouver en zone utilisateur ou données en respectant le fait qu'elle soit contiguë ou non? que se passe -t- il si la taille dépasse le segment (dans ce cas elle ne serait plus contiguë...)?

C'est tout de même impressionnant de traverser toutes les couches pour imposer une contrainte à la mémoire; je trouve!

A vous!

Quand on parle de contiguïté dans ce cadre, c'est forcément au niveau utilisateur seulement, rien ne garantit qu'au niveau physique tes cases soient contigües en mémoire RAM.

--
Jedaï

Le problème c'est qu'en RAM, le segment est partagé en zones ( cas du X86) parmi lesquelles se trouvent une zone utilisateur et une zone données. Donc, mes dires concernent forcement l'aspect physique de la chose.
Je pense que si JAVA par exemple te propose un rangement contigüe de la structure cela ne peut être qu'en RAM, elle doit donc respecter le contrat.
Pour moi, organiser les emplacements de façon contigüe mais pas en RAM n'a aucune signification. Certes tout cela n'est pas évident parce qu'on décent profondément dans la soute.

Tu veux dire que tu ne sais pas dans quels cas utiliser une liste chaînée plutôt qu'un tableau c'est ça ?

Citation:

---

Envoyé par wafiwafi

Si on s'intéresse au cas du 32bits (x86), La mémoire est forcément segmentée.

---

Sous Win32, plateforme bien supportée par les processeurs x86 32 bits, la mémoire est linéaire (4 Go). Il n'y a pas de segments mais des pages (qui ne sont pas des segments).

Citation:

---

Envoyé par wafiwafi

Le problème c'est qu'en RAM, le segment est partagé en zones (cas du X86) parmi lesquelles se trouvent une zone utilisateur et une zone données.

---

À ma connaissance le code est dans un segment de code (registre de segment CS) et les données sont dans un segment de données (registre de segment DS).
Chacun de ces 2 segments offre 4Go d'espace que la MMU va mapper sur la mémoire physique. Ça veut dire qu'un programme (et même plusieurs) peut utiliser 2Go de code et 3Go de données avec seulement 1Go de mémoire physique sans que le code et les données ne se marchent sur les pieds.
Si tu veux tu peux ajouter (pas en Java hein!) d'autres segments (toujours de 4Go chacun) à l'aide des registres de segment ES, FS et GS.
L'architecture supporte tout ça depuis le 386dx. Bien sûr, en pratique, dès qu'un même programme utilise plus que la mémoire physique disponible le ralentissement est insupportable.

Citation:

---

Envoyé par wafiwafi

Si on s'intéresse au cas du 32bits (x86), La mémoire est forcément segmentée.

---

Chaque segment occupant la totalité de l'espace d'adressage il n'y a pas de collision possible.
Ce qui peut se passer en revanche c'est que l'espace d'un segment de données peut devenir fragmenté. C'est-à-dire découpé en de petites zones chacune inférieure à la zone contiguë à allouer, bien que l'espace total disponible soit supérieur à cette quantité. Deux cas possibles:

• ton langage est un langage natif comme C/C++, dans ce cas l'allocation ne peut qu'échouer
• ton langage est un langage managé (Java/.Net/D/...), dans ce cas l'allocation va réussir après une phase de recompactage de la mémoire utilisée

Citation:

---

Chacun de ces 2 segments offre 4Go d'espace que la MMU va mapper sur la mémoire physique. Ça veut dire qu'un programme (et même plusieurs) peut utiliser 2Go de code et 3Go de données avec seulement 1Go de mémoire physique sans que le code et les données ne se marchent sur les pieds.

---

.
Tu parles du SWAP.

Tu confirmes donc que si un langage propose une allocation contigüe ou non, il respectera forcement le contrat bien que cela concerne la gestion de la mémoire physique et donc une contrainte pour l'OS en ce qui concerne la gestion de la mémoire.

Ma question ne concerne pas le choix en entre un tableau ou une liste; mais plutôt un cas d'allocation de mémoire de façon contigüe d'une manière générale. La liste est un exemple idéale.

Quand tu crées un tableau, l'OS t'octroie une mémoire contiguë en mémoire virtuelle (la mémoire vue des applications) pour ton tableau. C'est tout ce qui est garanti. Peu importe comment est organisé ton tableau en mémoire physique.

Citation:

---

Quand tu crées un tableau, l'OS t'octroie une mémoire contiguë en mémoire virtuelle (la mémoire vue des applications) pour ton tableau. C'est tout ce qui est garanti. Peu importe comment est organisé ton tableau en mémoire physique.

---

Je ne suis pas d'accord. Tous dépend comment le langage implémente le tableau. L'utilisateur a une vision conceptuelle de cases les unes à côté des autres mais la réalité est autre. Si tu programmes les structures de données (j'ai implémenté quelques unes), tu as la possibilité d'imposer la contrainte "contigüe" en mémoire centrale. Voila pourquoi il est intéressant de déscendre dans la soute pour découvrir ce qui se passe vraiment. Au début, je pensais être un simple utilisateur, jusqu'au jour où le devoir m'a appelé pour fabriquer des structures de données. Il n'y a donc pas de limite pour un développeur quand il s'agit d'apprendre! Je pense que c'est une grave erreur de dire Peu importe comment est organisé....
Tout cela reste mon avis.
Je ne comprend pas pourquoi tu parles de mémoire virtuelle. le tableau n'est pas forcément swapé.
Il faut raisonner de façon générale et donc en mémoire centrale.

Swap ou pas swap ça ne change rien puisqu'on te dit que l'espace d'adressage est virtualisé, l'espace d'adressage continu que voit ton programme est virtuel, ta mémoire physique elle est découpée en pages.

Citation:

---

Swap ou pas swap ça ne change rien puisqu'on te dit que l'espace d'adressage est virtualisé, l'espace d'adressage continu que voit ton programme est virtuel, ta mémoire physique elle est découpée en pages.

---

Si tu lis bien la discussion, ce n'est pas moi qui a parlé de swap au début; j'ai juste répondu à la personne qui parlait de mémoire virtuelle alors qu'il s'agit de mémoire centrale. La mémoire virtuelle est sur le disque, j'ai donc supposé que la personne en question faisait allusion au swap; ce n'était qu'un passage!
Maintenant, certes la mémoire est paginée, segmentée, ...et tout ce que tu veux. Quand un langage propose de mémoriser des informations de façon contigüe, on n'est plus dans le conceptuel ni dans le virtuel, les informations sont bel et bien contigües sur la page en question. Je l'ai vérifié à plusieurs reprises pour m'assurer que c'est bien le cas ( avec java). Pour terminer, et je l'ai déjà précisé, où tu es un programmeur et tu ne considères que l'interface utilisateur qui reste virtuel et donc je suis d'accord avec toi : on peut se ficher de ce qui se passe dans la soute, où tu vas au delà et les possibilités de la programmation t'ouvrent bien des portes (programmation de structures de données, programmation avancée, et surtout optimisation dans son sens le plus large). Franchement, et je parle pour moi, je préfère la seconde.
Alors reste Zen, et ne t'énerve pas. La question que j'ai posté m'a été posée à plusieurs reprises et je voulais juste partager la réponse avec tout le monde. Si tu préfères, je vais déclarer le sujet résolu!
Bien à toi.

Désolé de revenir sur ce sujet puisque je n'arrive pas à me positionner par rapport à ce qui a été dit. Au début, vous m'avez convaincu jusqu'à ce que je participe à une discussion au forum du C++, qui m'a aiguillé plutôt vers le contraire de vos affirmations. Résultat "embrouille totale". Voila la discussion en question du forum C++ : (Regarder plutôt les derniers messages de la discussion ci-dessous).

Tableau et constructeurs sans arguments

J'aimerais bien avoir une mise au point pour la clarté des sujets.

Merci à vous

Tu sembles t'embrouiller facilement... La discussion que tu cites confirme pleinement nos affirmations : la "contiguïté" des cases d'une structure de donnée n'est assuré qu'au niveau des adresses virtuelles, il est tout à fait possible que les adresses physiques sous-jacentes soient constitués de plusieurs intervalles séparés. Ce qui ne signifie pas que la "contiguïté" d'une structure de donnée soit sans valeur aucune : en effet, de longues portions de tes structures de données sont réellement contiguës, et il est même possible que la totalité de la structure soit physiquement contiguë (mais ce n'est qu'une possibilité, plus probable si la structure est de petite taille). De plus cette contiguité facilite le travail du cache et assure souvent de meilleures performances à ce genre de structure comparés à des structures plus éclatés, même si la complexité des opérations est comparable.

--
Jedaï

Citation:

---

Tu sembles t'embrouiller facilement...

---

Peut être; ton avis est le bienvenu.

Néanmoins, Le point que tu as évoqué est une partie du problème; Je m'explique:

Vous êtes d'accords sur les points suivants et cela me va :
En gros, Le compilateur/Runtime ne manipulent que des adresses virtuelles. Quand l'os met son switch pour gérer le processus..., Il introduits les adresses mémoires en dur. ainsi, le compilateur/Runtime propose à l'utilisateur une contiguïté qui pourrait évidement être mise en question lors de la gestion du processus pour des questions de place et d'optimisation. Ok!


Vous n'êtes pas d'accord sur le partage : segment code, pile, Tas...
A travers la présente discussion, vous dites que ce n'est qu'une vision fournie à l'utilisateur (pour lui faciliter la tache) et n'a rien à voir avec ce qui ce que prévoit et fait le compilateur/runtime pendant la compilation et l'exécution; c'est ce point précisément qui me gène. Au forum du C++, il affirment qu'il ne s'agit pas du tout de vision mais bel et bien une réalité du compilateur/runtime, mais encore une fois au niveau mémoire virtuelle.
Le passage en dur aux adresses physique peut compromettre ce partage. et là est une autre pair de manche que je ne discute pas.

Néanmoins, je ne pense pas que l'os compromet l'organisation de prévu par le compilateur et le runtime à un fort pourcentage mais plutôt un faible. Sinon ça ne sert à rien de prévoir. Ce dernier point est une analyse personnel qui reste pleinement à confirmer.


J'espère avoir une réponse clair point par point évoqués qui fixera mes idées et celles certainement d'autres personnes qui suivent cette discussion.

En tout cas un grand merci pour ta manifestation qui ne peut être que précieuse.

Citation:

---

j'ai juste répondu à la personne qui parlait de mémoire virtuelle alors qu'il s'agit de mémoire centrale. La mémoire virtuelle est sur le disque, j'ai donc supposé que la personne en question faisait allusion au swap;

---

La mémoire virtuelle c'est la seule mémoire centrale que connaissent les applications. Ces dernières sont persuadées qu'elles voient, c'est la RAM, mais en fait le système mappe la mémoire virtuelle de chaque application vers la zone de la RAM correspondante (certaines données peuvent même se trouver en mémoire secondaire (disque dur) et ne se trouver dans la RAM que lorsqu'on en a besoin). Le compilateur lui ne fait pas la distinction entre adresse virtuelle et adresse physique, le code qu'il génère est dans tous les cas directement exécutable par le processeur.

- Si tu exécutes ce code pendant la phase de démarrage de la machine, là où aucun OS n'a encore été chargé, ces adresses seront évidemment utilisées telles quelles, le processeur ne va pas faire d'autre interprétation de ces adresses. Pour lui, ce sont des adresses "réelles" (c'est-à-dire de vraies adresses physiques).

- Si tu exécutes ce même code dans un quelconque OS, l'OS va interpréter ces adresses comme étant des adresses virtuelles.

Concernant la contigüité de quoi que ce soit en mémoire virtuelle, on t'a déjà dit une myriade de fois, dans cette discussion et dans d'autres, que ça reste juste au niveau de la mémoire virtuelle. Ce n'est pas forcément le cas en mémoire physique. Et personne n'y peut rien. Si tu veux gérer la mémoire physique, lance ton programme pendant la phase de démarrage de la machine.

Bonjour Melem,
Ce que tu viens de dire n'est plus un problème, et je l'ai affirmé dans mon dernier message. Vous me l'avez déjà expliqué, je l'ai compris; je vous en remercie.
Tu peux plutôt répondre par rapport à ce que j'ai avancé juste avant ton dernier message. que je rappelle :

Citation:

---

Vous n'êtes pas d'accord sur le partage : segment code, pile, Tas...
A travers la présente discussion, vous dites que ce n'est qu'une vision fournie à l'utilisateur (pour lui faciliter la tache) et n'a rien à voir avec ce qui ce que prévoit et fait le compilateur/runtime pendant la compilation et l'exécution; c'est ce point précisément qui me gène. Au forum du C++, il affirment qu'il ne s'agit pas du tout de vision mais bel et bien une réalité du compilateur/runtime, mais encore une fois au niveau mémoire virtuelle.
Le passage en dur aux adresses physique peut compromettre ce partage. et là est une autre pair de manche que je ne discute pas.

---

Si tu remarques bien, je ne parle que de mémoire virtuelle.

(Gardons notre calme!)

Je rappelle que sous la plupart des OS 32 bits, on est en modèle mémoire "plat": Tous les segments sont confondus, sur la totalité de la mémoire virtuelle (c'est comme un modèle "tiny" géant).

Ensuite, sur l'organisation, c'est assez facile de faire ça: La pile tout en haut du plan mémoire, le premier tas plus ou moins en bas au début... Et quant au code, on peut avoir plusieurs écoles: On peut supposer que le code ne change pas du tout après chargement (pas de chargement tardif de DLL) et tout mettre au début en-dessous du tas, soit allouer directement le nouveau code dans le tas, etc.

Ne pas oublier que seule la pile a vraiment besoin d'être contigüe: On peut toujours avoir un tas en deux parties, même si ça limite la quantité de mémoire contigüe disponible (et donc la plus grande allocation possible). De toute façon, dès qu'on commence à désallouer des choses dans un ordre plus ou moins aléatoire, on se retrouve avec une taille maximale d'allocation inférieure à la quantité totale de mémoire libre.

C'est la réponse que j'attendais depuis l'ouverture de la discussion. C'est super clair! En plus, tout rentre en concordance avec ce qui a été dit au forum c++.
Je mets le sujet résolu.
Un grand merci et Bonne année 2010.