Qu'est-ce que sont la pile et le tas et où se trouvent-ils?

Question

• Qu'est-ce que la pile et le tas?
• Où sont-ils physiquement situés dans la mémoire d'un ordinateur?
• Dans quelle mesure sont-ils contrôlés par le SE ou par l'exécution de langage?
• Quelle est leur portée?
• Qu'est-ce qui détermine leur taille?
• Qu'est-ce qui les rend plus rapides?

Answer 1

La pile est la mémoire réservée en tant qu'espace d'échange pour un thread d'exécution. Lorsqu'une fonction est appelée, un bloc est réservé en haut de la pile pour les variables locales et certaines données de gestion. Lorsque cette fonction renvoie, le bloc devient inutilisé et peut être utilisé la prochaine fois qu'une fonction est appelée. La pile est toujours réservée selon un ordre LIFO (dernier entré, premier sorti); le bloc le plus récemment réservé est toujours le prochain bloc à être libéré. Cela rend vraiment simple de suivre la pile; libérer un bloc de la pile ne consiste qu'à ajuster un pointeur.

Le tas est la mémoire réservée pour l'allocation dynamique. Contrairement à la pile, il n'y a aucun schéma imposé pour l'allocation et la libération de blocs depuis le tas; vous pouvez allouer un bloc à tout moment et le libérer à tout moment. Cela rend beaucoup plus complexe de suivre quelles parties du tas sont allouées ou libres à un moment donné; il existe de nombreux allocateurs de tas personnalisés disponibles pour ajuster les performances du tas pour différents modèles d'utilisation.

Chaque thread reçoit une pile, tandis qu'il n'y a généralement qu'un seul tas pour l'application (bien qu'il ne soit pas rare d'avoir plusieurs tas pour différents types d'allocation).

Pour répondre directement à vos questions:

Dans quelle mesure sont-ils contrôlés par le système d'exploitation ou le runtime du langage?

Le système d'exploitation alloue la pile pour chaque thread de niveau système lors de la création du thread. En général, le système d'exploitation est appelé par le runtime du langage pour allouer le tas pour l'application.

Quelle est leur portée?

La pile est attachée à un thread, donc lorsque le thread se termine, la pile est récupérée. Le tas est généralement alloué au démarrage de l'application par le runtime, et est récupéré lorsque l'application (techniquement le processus) se termine.

Qu'est-ce qui détermine la taille de chacun d'eux?

La taille de la pile est définie lors de la création d'un thread. La taille du tas est définie au démarrage de l'application, mais peut augmenter au fur et à mesure que l'espace est nécessaire (l'allocateur demande plus de mémoire au système d'exploitation).

Qu'est-ce qui rend l'un plus rapide?

La pile est plus rapide car le modèle d'accès la rend triviale pour allouer et libérer de la mémoire à partir de celle-ci (un pointeur/entier est simplement incrémenté ou décrémenté), tandis que le tas implique beaucoup plus de complexité dans une allocation ou une libération. De plus, chaque octet de la pile est souvent réutilisé, ce qui signifie qu'il tend à être associé fréquemment au cache du processeur, le rendant très rapide. Un autre inconvénient de performance pour le tas est que le tas, étant principalement une ressource globale, doit généralement être sûr pour le multithreading, c'est-à-dire que chaque allocation et libération doit être - typiquement - synchronisée avec "toutes" les autres accès au tas dans le programme.

Une démonstration claire:
_{Source de l'image: <a href="http://vikashazrati.wordpress.com/2007/10/01/quicktip-java-basics-stack-and-heap/" rel="noreferrer">vikashazrati.wordpress.com</a>}

Answer 2

Pile :

• Stocké dans la RAM de l'ordinateur tout comme le tas.
• Les variables créées sur la pile sortiront de la portée et seront automatiquement désallouées.
• Beaucoup plus rapide à allouer par rapport aux variables sur le tas.
• Implémenté avec une véritable structure de données de pile.
• Stocke des données locales, des adresses de retour, utilisé pour le passage de paramètres.
• Peut avoir un dépassement de la pile lorsqu'une trop grande partie de la pile est utilisée (principalement causé par une récursion infinie ou trop profonde, de très grandes allocations).
• Les données créées sur la pile peuvent être utilisées sans pointeurs.
• Vous utiliseriez la pile si vous savez exactement combien de données vous devez allouer avant le temps de compilation et que ce n'est pas trop grand.
• A généralement une taille maximale déjà déterminée lorsque votre programme démarre.

Tas:

• Stocké dans la RAM de l'ordinateur tout comme la pile.
• En C++, les variables sur le tas doivent être détruites manuellement et ne sortent jamais de la portée. Les données sont libérées avec delete, delete[], ou free.
• Plus lent à allouer par rapport aux variables sur la pile.
• Utilisé sur demande pour allouer un bloc de données pour être utilisé par le programme.
• Peut avoir de la fragmentation lorsqu'il y a beaucoup d'allocations et de désallocations.
• En C++ ou C, les données créées sur le tas seront pointées par des pointeurs et allouées avec new ou malloc respectivement.
• Peut avoir des échecs d'allocation si un trop grand tampon est demandé pour être alloué.
• Vous utiliseriez le tas si vous ne savez pas exactement combien de données vous aurez besoin au moment de l'exécution ou si vous avez besoin d'allouer beaucoup de données.
• Responsable des fuites de mémoire.

Exemple :

int foo()
{
  char *pBuffer; //<-- rien n'est encore alloué (à l'exception du pointeur lui-même, qui est alloué ici sur la pile).
  bool b = true; // Alloué sur la pile.
  if(b)
  {
    //Créer 500 octets sur la pile
    char buffer[500];

    //Créer 500 octets sur le tas
    pBuffer = new char[500];

   }//<-- le tampon est désalloué ici, pBuffer ne l'est pas
}//<--- oops il y a une fuite de mémoire, j'aurais dû appeler delete[] pBuffer;

Answer 3

Le point le plus important est que le tas et la pile sont des termes génériques pour les différentes manières dont la mémoire peut être allouée. Ils peuvent être implémentés de nombreuses manières différentes, et les termes s'appliquent aux concepts de base.

• Dans une pile d'éléments, les éléments sont empilés les uns sur les autres dans l'ordre où ils ont été placés là, et vous ne pouvez retirer que le haut de la pile (sans renverser le tout).

  

  La simplicité d'une pile est que vous n'avez pas besoin de maintenir un tableau contenant un enregistrement de chaque section de mémoire allouée ; la seule information d'état dont vous avez besoin est un simple pointeur vers la fin de la pile. Pour allouer et désallouer, vous n'avez qu'à incrémenter et décrémenter ce pointeur unique. Remarque : une pile peut parfois être implémentée pour commencer en haut d'une section de mémoire et descendre plutôt que de grandir vers le haut.

• Dans un tas, il n'y a pas d'ordre particulier pour la manière dont les éléments sont placés. Vous pouvez aller chercher et retirer les éléments dans n'importe quel ordre car il n'y a pas d'élément clairement en haut.

  

  L'allocation de tas nécessite de maintenir un enregistrement complet de ce qui est alloué en mémoire et de ce qui ne l'est pas, ainsi que de la maintenance pour réduire la fragmentation, trouver des segments de mémoire contigus assez grands pour accueillir la taille demandée, etc. La mémoire peut être désallouée à tout moment en laissant de l'espace libre. Parfois, un allocateur de mémoire effectuera des tâches de maintenance telles que la défragmentation de la mémoire en déplaçant la mémoire allouée autour, ou la collecte de déchets - en identifiant au moment de l'exécution lorsque la mémoire n'est plus dans le champ d'application et en la désallouant.

Ces images devraient bien décrire les deux façons d'allouer et de libérer la mémoire dans une pile et un tas. Miam !

• Dans quelle mesure sont-ils contrôlés par le système d'exploitation ou l'environnement d'exécution du langage ?

  Comme mentionné, la pile et le tas sont des termes généraux, et peuvent être implémentés de nombreuses manières. Les programmes informatiques ont typiquement une pile appelée une pile d'appel qui stocke des informations pertinentes pour la fonction courante telle qu'un pointeur vers la fonction à partir de laquelle elle a été appelée, et toutes les variables locales. Parce que les fonctions en appellent d'autres et retournent ensuite, la pile grandit et rétrécit pour contenir les informations des fonctions plus bas dans la pile d'appels. Un programme n'a pas vraiment de contrôle d'exécution dessus ; c'est déterminé par le langage de programmation, le système d'exploitation et même l'architecture système.

  Un tas est un terme général utilisé pour toute mémoire allouée dynamiquement et aléatoirement ; c'est-à-dire sans ordre. La mémoire est typiquement allouée par le système d'exploitation, avec l'application appelant des fonctions API pour effectuer cette allocation. Beaucoup de surdité est nécessaire pour gérer la mémoire allouée dynamiquement, ce qui est généralement traité par le code d'exécution du langage de programmation ou de l'environnement utilisé.

• Quelle est leur étendue ?

  La pile d'appel est un concept si bas niveau qu'il n'est pas lié à 'l'étendue' au sens de la programmation. Si vous désassemblez un code, vous verrez des références de style pointeur relatif aux parties de la pile, mais en ce qui concerne un langage de haut niveau, le langage impose ses propres règles d'étendue. Un aspect important d'une pile est cependant que dès qu'une fonction retourne, tout ce qui est local à cette fonction est immédiatement libéré de la pile. Cela fonctionne comme on peut s'y attendre compte tenu du fonctionnement de vos langages de programmation. Pour un tas, c'est également difficile à définir. L'étendue est ce qui est exposé par le système d'exploitation, mais votre langage de programmation ajoute probablement ses propres règles sur ce qu'est une "étendue" dans votre application. L'architecture du processeur et le système d'exploitation utilisent l'adressage virtuel, que le processeur traduit en adresses physiques et il existe des pannes de page, etc. Ils tiennent compte de quelles pages appartiennent à quelles applications. Vous n'avez jamais vraiment besoin de vous en soucier, cependant, car vous utilisez simplement la méthode d'allocation et de libération de mémoire de votre langage de programmation, et vérifiez les erreurs (si l'allocation/la libération échoue pour une raison quelconque).

• Qu'est-ce qui détermine leur taille ?

  Encore une fois, cela dépend du langage, du compilateur, du système d'exploitation et de l'architecture. Une pile est généralement pré-allouée, car par définition elle doit être une mémoire contiguë. Le compilateur du langage ou le système d'exploitation détermine sa taille. Vous ne stockez pas de gros morceaux de données sur la pile, donc elle sera suffisamment grande pour ne jamais être entièrement utilisée, sauf en cas de récursion infinie non désirée (d'où "débordement de pile") ou d'autres décisions de programmation inhabituelles.

  Un tas est un terme général pour tout ce qui peut être alloué de manière dynamique. Selon le point de vue adopté, sa taille change constamment. Dans les processeurs et systèmes d'exploitation modernes, la façon exacte dont cela fonctionne est très abstraite de toute façon, donc vous n'avez généralement pas besoin de vous soucier beaucoup de son fonctionnement en profondeur, sauf que (dans les langages qui le permettent) vous ne devez pas utiliser de mémoire que vous n'avez pas encore allouée ou de mémoire que vous avez libérée.

• Qu'est-ce qui le rend plus rapide ?

  La pile est plus rapide car toute la mémoire libre est toujours contiguë. Aucune liste n'a besoin d'être maintenue de tous les segments de mémoire libre, juste un simple pointeur vers le haut actuel de la pile. Les compilateurs stockent généralement ce pointeur dans un registre spécial, rapide registre à cet effet. De plus, les opérations ultérieures sur une pile sont généralement concentrées dans des zones de mémoire très proches, ce qui est bon pour l'optimisation par les caches sur puce du processeur au niveau très bas.

Answer 4

(J'ai déplacé cette réponse d'une autre question qui était plus ou moins une copie de celle-ci.)

La réponse à votre question est spécifique à l'implémentation et peut varier selon les compilateurs et les architectures de processeur. Cependant, voici une explication simplifiée.

• À la fois la pile et le tas sont des zones mémoire allouées par le système d'exploitation sous-jacent (souvent de la mémoire virtuelle qui est mappée en mémoire physique au besoin).
• Dans un environnement multi-thread, chaque thread aura sa propre pile complètement indépendante mais ils partageront le tas. L'accès concurrent doit être contrôlé sur le tas et n'est pas possible sur la pile.

Le tas

• Le tas contient une liste chaînée de blocs utilisés et libres. Les nouvelles allocations sur le tas (par new ou malloc) sont satisfaites en créant un bloc approprié à partir d'un des blocs libres. Cela nécessite la mise à jour de la liste des blocs sur le tas. Ces informations méta sur les blocs sur le tas sont également stockées sur le tas souvent dans une petite zone juste devant chaque bloc.
• À mesure que le tas grandit, de nouveaux blocs sont souvent alloués à partir d'adresses inférieures vers des adresses supérieures. Ainsi, vous pouvez penser au tas comme à un tas de blocs mémoire qui grandit en taille à mesure que la mémoire est allouée. Si le tas est trop petit pour une allocation, la taille peut souvent être augmentée en acquérant plus de mémoire du système d'exploitation sous-jacent.
• Allouer et désallouer de nombreux petits blocs peut laisser le tas dans un état où il y a beaucoup de petits blocs libres intercalés entre les blocs utilisés. Une demande d'allocation d'un grand bloc peut échouer car aucun des blocs libres n'est assez grand pour satisfaire la demande d'allocation même si la taille combinée des blocs libres peut être suffisante. Cela s'appelle la fragmentation du tas.
• Lorsqu'un bloc utilisé adjacent à un bloc libre est désalloué, le nouveau bloc libre peut être fusionné avec le bloc libre adjacent pour créer un plus grand bloc libre réduisant efficacement la fragmentation du tas.

La pile

• La pile fonctionne souvent en étroite collaboration avec un registre spécial du processeur nommé le pointeur de pile. Initialement, le pointeur de pile pointe vers le sommet de la pile (l'adresse la plus élevée sur la pile).
• Le CPU a des instructions spéciales pour empiler des valeurs sur la pile et les dépiler. Chaque empilement stocke la valeur à l'emplacement actuel du pointeur de pile et diminue le pointeur de pile. Un dépilage récupère la valeur pointée par le pointeur de pile puis augmente le pointeur de pile (ne soyez pas confus par le fait que ajouter une valeur à la pile diminue le pointeur de pile et retirer une valeur l'augmente. Rappelez-vous que la pile grandit vers le bas). Les valeurs stockées et récupérées sont les valeurs des registres CPU.
• Si une fonction a des paramètres, ceux-ci sont poussés sur la pile avant l'appel à la fonction. Le code de la fonction est alors capable de remonter la pile depuis le pointeur de pile actuel pour localiser ces valeurs.
• Lorsqu'une fonction est appelée, le CPU utilise des instructions spéciales qui empilent le pointeur d'instruction actuel sur la pile, c'est-à-dire l'adresse du code en cours d'exécution sur la pile. Le CPU saute ensuite à la fonction en définissant le pointeur d'instruction à l'adresse de la fonction appelée. Plus tard, lorsque la fonction retoune, l'ancien pointeur d'instruction est dépilé de la pile et l'exécution reprend au code juste après l'appel à la fonction.
• Lorsqu'une fonction est entrée, le pointeur de pile est diminué pour allouer plus d'espace sur la pile pour les variables locales (automatiques). Si la fonction a une variable locale de 32 bits, quatre octets sont réservés sur la pile. Lorsque la fonction retourne, le pointeur de pile est ramené en arrière pour libérer la zone allouée.
• Les appels de fonctions imbriquées fonctionnent parfaitement. Chaque nouvel appel allouera des paramètres de fonction, l'adresse de retour et de l'espace pour les variables locales et ces enregistrements d'activation peuvent être empilés pour des appels imbriqués et se dérouleront de la manière correcte lorsque les fonctions retournent.
• Comme la pile est un bloc de mémoire limité, vous pouvez provoquer un débordement de pile en appelant trop de fonctions imbriquées et/ou en allouant trop d'espace pour les variables locales. Souvent, la zone mémoire utilisée pour la pile est configurée de manière à ce que l'écriture en dessous du bas (l'adresse la plus basse) de la pile déclenche un piége ou une exception dans le CPU. Cette condition exceptionnelle peut ensuite être capturée par le runtime et convertie en une sorte d'exception de débordement de pile.

Une fonction peut-elle être allouée sur le tas au lieu de la pile?

Non, les enregistrements d'activation pour les fonctions (c'est-à-dire les variables locales ou automatiques) sont alloués sur la pile qui est utilisée non seulement pour stocker ces variables, mais aussi pour suivre les appels de fonctions imbriquées.

La manière dont le tas est géré dépend vraiment de l'environnement d'exécution. C utilise malloc et C++ utilise new, mais de nombreux autres langages ont une collecte des déchets.

Cependant, la pile est une fonction plus bas-niveau étroitement liée à l'architecture du processeur. Augmenter le tas lorsqu'il n'y a pas assez d'espace n'est pas trop difficile car cela peut être mis en œuvre dans l'appel de bibliothèque qui gère le tas. Cependant, augmenter la pile est souvent impossible car le débordement de pile n'est découvert que lorsqu'il est trop tard ; et l'arrêt de l'exécution du thread est la seule option viable.

Answer 5

Dans le code C# suivant

public void Method1()
{
    int i = 4;
    int y = 2;
    class1 cls1 = new class1();
}

Voici comment la mémoire est gérée

Les variables locales qui ne doivent durer que pendant l'invocation de la fonction vont dans la pile. Le tas est utilisé pour les variables dont nous ne connaissons pas vraiment la durée de vie à l'avance mais que nous prévoyons de durer un certain temps. Dans la plupart des langues, il est essentiel de connaître à la compilation la taille d'une variable si nous voulons la stocker sur la pile.

Les objets (dont la taille varie lorsque nous les mettons à jour) vont dans le tas car nous ne savons pas à la création combien de temps ils vont durer. Dans de nombreuses langues, le tas est collecté par le ramasse-miettes pour trouver des objets (comme l'objet cls1) qui n'ont plus de références.

En Java, la plupart des objets vont directement dans le tas. Dans des langues comme C / C++, les structs et les classes peuvent souvent rester sur la pile lorsque vous ne travaillez pas avec des pointeurs.

Plus d'informations peuvent être trouvées ici:

La différence entre l'allocation de mémoire sur la pile et sur le tas « timmurphy.org

et ici:

Création d'objets sur la pile et sur le tas

Cet article est la source de l'image ci-dessus: Six concepts .NET importants : Pile, tas, types de valeur, types de référence, boxing et unboxing - CodeProject

mais soyez conscient qu'il peut contenir quelques inexactitudes.