# Allocation de mémoire

L'allocation de mémoire vive désigne les techniques et les algorithmes sous-jacents permettant de réserver de la mémoire vive à un programme informatique pour son exécution.
L'opération symétrique de l'allocation est couramment appelée libération de la mémoire (on peut parler également de désallocation ou de restitution).

## Les trois modes d'allocation

Un programme informatique consomme essentiellement deux ressources : du temps de traitement des processeurs, et de l'espace de stockage des données. En machine, l'espace peut être la mémoire vive volatile ou la mémoire de masse persistante.
Il existe trois stratégies d'allocation de la mémoire : l'allocation statique, l'allocation dynamique sur la pile, et l'allocation dynamique sur le tas. L'allocation statique est principalement mise en place dans les langages de programmation compilés (C, C++, Pascal…). Les langages interprétés (PHP, Python, Perl…) ne peuvent allouer la mémoire que sur demande, lors de l'exécution du script.
À chacune des stratégies correspond une région mémoire du programme, ou segment. Ces segments sont nommés text (code), data (statique), stack (pile) et heap (tas).
Mode d'allocation de la mémoire :
| Mode d'allocation | Mode d'allocation | Mode d'allocation | Région mémoire utilisée | Avantage | Langage de programmation | Langage de programmation |
| Mode d'allocation | Mode d'allocation | Mode d'allocation | Région mémoire utilisée | Avantage | compilés (C, C++, Pascal, etc.) | interprétés (PHP, Python, Perl, etc.) |
| statique | | | text, data ou BSS | utilisation plus efficace du temps d'exécution | oui | non |
| dynamique | sur la pile (stack) | (lexicale ou automatique) | stack | utilisation plus efficace du temps d'exécution | oui | oui |
| dynamique | sur le tas (heap) | (allocation dynamique de mémoire) | heap | utilisation plus efficace de l'espace mémoire | oui | oui |
| Remarques | Remarques | Remarques | Remarques | Remarques | L'allocation statique est principalement mise en place dans les langages de programmation compilés (C, C++, Pascal…). | Les langages interprétés ne peuvent allouer la mémoire que sur demande, lors de l'exécution du script. |

### Allocation statique

L'allocation statique se fait au moment de l'initialisation du programme, avant son exécution proprement dite. L'espace alloué statiquement est déjà pré-réservé dans le fichier exécutable du programme lorsque le système d'exploitation charge le programme en mémoire pour l'exécuter.
Allouer statiquement de la mémoire pour un programme signifie :
* prévoir l'espace mémoire nécessaire avant l'exécution du programme, en spécifiant la quantité nécessaire dans le code source ;
* réserver cet espace au moment de la compilation, dans le fichier binaire produit ;
* au chargement du programme en mémoire, juste avant l'exécution, l'espace réservé devient alors accessible.
Lors de l'exécution, aucune allocation statique ne peut avoir lieu.
L'avantage de l'allocation statique se situe essentiellement au niveau des performances, puisqu'on évite les coûts de l'allocation dynamique à l'exécution : la mémoire statique est immédiatement utilisable.
Sur les systèmes d'exploitation communs, la mémoire allouée statiquement est placée dans le segment text, le segment de données ou le segment BSS du programme, selon le destin de cette zone mémoire (réservée, initialisée, lecture seule…).

### Allocation dynamique

L'allocation dynamique se fait pendant l'exécution du programme, ce qui signifie que ni l'espace à allouer, ni la taille de cet espace ne sont codés explicitement, parce qu'ils dépendent des données du programme et sont a priori variables ; la demande d'allocation d'espace au système d'exploitation se fait durant l'exécution du programme. L'allocation dynamique permet donc de n'utiliser que ce qu'il faut de mémoire à chaque exécution.

#### Allocation sur la pile (automatique)

L'exécution d'un programme utilise généralement une pile contenant les cadres d'appel aux routines (fonctions ou procédures) du langage de programmation utilisé. Schématiquement, les variables lexicales, c'est-à-dire les variables définies dans la portée textuelle d'une routine, sont :
* allouées lors de l'entrée dans la routine (entrée de la portée), c'est-à-dire que l'espace est réservé pour ces variables;
* désallouées automatiquement lors de la sortie de la routine (sortie de la portée), c'est-à-dire que l'espace réservé pour ces variables est dorénavant libre et disponible pour d'autres variables.
Un segment mémoire, dit segment de pile, est utilisé pour ces allocations/libération. Aucun mot clef n'est nécessaire dans le code source du langage supportant la notion de variable lexicale : l'espace est alloué et libéré selon la discipline de pile par définition.
Certains langages, comme le C ou le C++, parlent de variables automatiques au lieu de variables lexicales, mais il s'agit de la même chose.

#### Allocation sur le tas

La plupart des programmes ayant des besoins en mémoire dépendant de l'usage qu'on en fait, il est nécessaire de pouvoir, à des moments arbitraires de l'exécution, demander au système d'exploitation d'allouer de nouvelles zones de mémoire, et de pouvoir restituer au système ces zones (libérer la mémoire). Le système d'exploitation utilise une table pour gérer le tas où il enregistre pour chaque bloc de mémoire alloué:
* l'adresse de début du bloc de mémoire alloué;
* la taille en octets du bloc de mémoire alloué.
La gestion de l'allocation et de la libération de la mémoire est sous la responsabilité du programmeur.
Séquence d'utilisation de l'allocation dynamique de mémoire :
| Étape | Opération | Remarque |
| Demande d'allocation par le programme | Le programme demande au système d’exploitation de lui attribuer de l’espace mémoire [en spécifiant le nombre d’octets désirés]. | |
| Allocation par le système d'exploitation | Si un bloc d'octets [de mémoire] de la taille demandée est disponible dans le tas, le système d’exploitation retourne l’adresse du début de ce bloc d’octets disponibles. | ce bloc d'octets est alors réservé au programme (on dit qu'il lui est alloué); ce bloc d'octets n’est donc plus disponible à d'autre programme. |
| Utilisation de l'espace mémoire alloué | Le programme utilise à sa guise l'espace mémoire alloué. | |
| Demande de Libération par le programme | Lorsque le programme n’a plus besoin de l’espace mémoire alloué, il le libère en indiquant au système d’exploitation l’adresse du début du bloc réservé qu'il désire libérer. | Si le programme ne libère pas la mémoire allouée avant de se terminer, cela cause une fuite de mémoire. |
Les langages de programmation dotés de ramasse-miettes utilisent, mais de façon transparente pour le programmeur, l'allocation sur le tas et les primitives *alloc/free. Dans ce dernier cas, le ramasse-miettes permet au développeur de ne pas se soucier de la libération des ressources.

##### Danger

Les fuites de mémoire, qui se produisent aussi bien sous un système d'exploitation avec une interface en ligne de commande (tel que DOS) qu'avec une interface d'utilisation graphique (comme avec Windows), ainsi que d'autres erreurs fréquentes dans les programmes à gestion manuelle de la mémoire, ont leur source dans les erreurs d'allocation mémoire sur le tas.

##### Exemples dans certains langages de programmation

Classiquement, les fonctions malloc et free des bibliothèques standard du langage C ainsi que les opérateurs new et delete du langage C++ permettent, respectivement, d'allouer et de libérer la mémoire sur le tas.
Exemple simple en langage C :
* int UtiliserAllocationDynamiqueDeMemoire ( int Nb )
* // Pointeur vers la mémoire allouée dynamiquement.
* int *pInt = NULL;
* // Demander l'allocation dynamique de l'espace mémoire nécessaire pour une liste de «Nb» nombres entiers.
* pInt = (int *) malloc ( Nb * sizeof(int) );
* // Si l'espace mémoire demandé a bien été alloué
* if ( pInt != NULL )
* // Utiliser l’espace mémoire alloué.
* // Libérer l'espace mémoire alloué.
* free (pInt);
* }// Fin du si.
* // Retourner le code d'erreur à la routine appelante.
* return 0;

## Comparaison

L'allocation statique est la méthode la plus sûre au sens où :
* la quantité consommée est constante et complètement connue avant l'exécution ;
* elle est généralement accessible exclusivement en lecture seule (non modifiable).
C'est toutefois une méthode très rigide et insuffisante pour les programmes dont les besoins peuvent varier de façon imprévisible : pour un programme ayant des besoins potentiels de mémoire importants, l'allocation statique conduirait à un gaspillage. Elle est finalement essentiellement utilisée pour stocker des constantes ou des valeurs calculées et disponibles au moment de la compilation.
L'allocation sur la pile représente un bon compromis :
* la quantité consommée est proportionnelle aux paramètres d'entrées du programme, qui déterminent la profondeur de la pile et donc la quantité allouée ; elle peut être connue avant l'exécution par une analyse de la complexité algorithmique ;
* il n'y a pas de fuite de mémoire, du fait de la libération implicite (respectant la discipline de pile).
L'allocation sur la pile doit être choisie en priorité lorsque les besoins mémoires sont connus à l'avance et sont proportionnels à certains paramètres d'entrée du programme. L'allocation et la libération consécutives, selon une discipline de pile, de grosses quantités de mémoire peuvent toutefois poser des problèmes de performance et de lisibilité du source (explosion du nombre de paramètres passés aux fonctions) ; ces problèmes sont à mettre dans la balance contre l'assurance d'une libération correcte des ressources mémoire.
L'allocation sur le tas, puisqu'elle permet le contrôle complètement arbitraire de l'allocation et de la libération, offre le plus de possibilités. Les ressources allouées manuellement ont cependant une durée de vie indéfinie, c’est-à-dire que le programmeur a la responsabilité de la libération (et doit éviter de tomber dans des pièges comme celui de la double libération, c'est-à-dire libérer deux fois la même zone mémoire). La mémoire allouée sur le tas peut également être référencée par des variables globales (de préférence confinées dans un espace de noms), ce qui peut aider à délester un groupe de fonctions de paramètres communs.
En pratique, on préférera le mode d'allocation le plus simple. La plupart du temps, l'allocation sur la pile est suffisante. On n'utilise l'allocation sur le tas qu'en dernier recours, pour manipuler des structures de données complexes et/ou dont l'évolution ne suit pas la discipline de pile.
Dans les langages à libération automatique de la mémoire (algorithme du ramasse-miettes) comme LISP, Java ou C#, le choix du mode d'allocation est réalisé directement par le compilateur.