Je suis confus concernant Ma compréhension de l'allocation de stockage (ouverte à l'amélioration): -
Lorsque nous appelons MALLOC, il alloue la mémoire dans le tas, et il le fait en cueillant un bloc de données de taille appropriée à partir de la liste Lorsqu'un certain bloc de mémoire est renvoyé par MALLOC, il est supprimé de la liste libre et l'adresse physique de ce bloc de mémoire est mise à jour dans la table de page.
Lorsque la mémoire est libre d'utiliser L'ensemble du tas est une liste gratuite (liste liée des blocs gratuits) + blocs de données alloués.
est-ce une image complète de l'allocation de stockage?
Edit: Du développement du noyau Linux (Robert Love) Chapitre sur la gestion de la mémoire, Allocation de dalle
"Une liste gratuite contient un bloc de disponible, déjà alloué, des données
structures. Lorsque le code nécessite une nouvelle instance d'une structure de données, il
peut attraper une des structures hors de la liste libre plutôt que d'allouer
la quantité suffisante de mémoire et la configurez-vous pour la structure de données.
Plus tard, lorsque la structure de données n'est plus nécessaire, elle est renvoyée à
la liste gratuite au lieu de trafiquée. En ce sens, la liste gratuite
agit comme un cache d'objet, mettant en cache un type d'objet fréquemment utilisé. "
Liste libre est mentionné comme un "bloc de structure de données disponibles et allouée".
tas et Liste libre . J'ai quelques questions et j'ai sa propre compréhension de la façon dont Malloc travaille dans C. S'il vous plaît corriger-moi si je me trompe.
, non?
gratuit () , le bloc de données est inséré dans la liste libre et éventuellement, pour réduire la fragmentation, conjointement avec le bloc voisin et le présent bit dans l'entrée de la table de page est effacé.
3 Réponses :
Notez que les pages peuvent être attribuées à un processus (par le noyau), même si le programme exécuté dans ce processus n'utilise pas les pages pour rien. Si vous Votre description de la façon dont une liste gratuite fonctionne bien pour moi, bien que je ne sois aucun expert dans la mise en œuvre de la mémoire. Mais la citation que vous avez postée de Robert Love Sounds comme il parle d'une allocation de mémoire dans le noyau Linux, qui n'est pas liée à la répartition de la mémoire par malloc () n'est pas vraiment lié à la table de la page; Il attribue des adresses virtuelles et le noyau est responsable de la tenue de l'endroit où les pages sont réellement stockées dans la RAM physique ou sur le disque.
malloc () interagit avec le noyau via l'appel de système BRK () , qui demande au noyau d'allouer plus de pages au processus ou libère des pages à la noyau. Donc, il y a vraiment deux niveaux d'allocation de mémoire:
brk () manipule la limite entre les adresses que le noyau vous permettra d'accéder (car ils correspondent à des pages allouées) et des adresses qui provoqueront une défaillance de segmentation si vous essayez d'accéder à eux.
MALLOC () attribue des parties de la taille variable du segment de données du programme pour une utilisation par le programme. Lorsqu'il n'y a pas assez d'espace libre dans la taille actuelle du segment de données, il utilise brk () pour obtenir plus de pages à partir du noyau, ce qui rend le segment de données plus grand. Lorsqu'il constate que certains espaces à la fin du segment de données sont inutilisés, il utilise BRK () pour remettre les pages inutilisées au noyau, ce qui rend le segment de données plus petit.
GRATUIT () Un bloc de mémoire situé au milieu de votre segment de données, la mise en oeuvre de gratuit () ne peut pas utiliser brk () < / Code> Pour réduire le segment de données car il y a toujours d'autres blocs alloués à des adresses supérieures. Les pages restent donc allouées à votre programme du point de vue du noyau, même s'ils sont "de l'espace libre" à partir du MALLOC () point de vue.
MALLOC () dans un processus d'espace utilisateur. Ce type de liste libre fonctionne probablement différemment.
Vous dites - "MALLOC () alloue des parties de la taille variable du segment de données du programme". N'est-ce pas le tas que vous parlez de? Le tas est-il une partie du segment de données? Je pense qu'ils étaient différents ..
Le tas est une structure de données située dans le segment de données. Ce sont les données de comptabilité qui conservent une trace de quelles parties du segment de données sont utilisées et qui sont disponibles. Comme une analogie lâche, pensez au rôle qu'un système de fichiers sert sur un disque.
Sharat: Je pense que tu penses tout au long de la chose - désolé!
(En quelque sorte, le timing a été gâché lorsqu'il essayait sans succès d'ajouter ceci au commentaire précédent.) Wyzard: J'ai écrit un Malloc () Mise en œuvre avec des crochets de débogage il y a 20 ans. J'ai rapidement découvert que vous ne voulez pas BRK () Retour au noyau lorsque vous avez des données inutilisées à la fin du segment de données. Vous effectuerez des appels système inutiles si votre programme est en cours d'exécution dans des cycles d'un groupe de MALLOC () S suivi d'un tas de gratuit () s. Bien entendu, les implémentations de la résistance au système d'exploitation de MALLOC () peuvent avoir des optimisations pour gérer des cas tels que ceci.
@AlexMeasDay, vous ne voulez pas non plus garder beaucoup de mémoire attachée pour toujours si le programme alloue beaucoup, puis libère tout. Vous ne voulez probablement pas BRK () DOWN TOUTES L'espace disponible devient disponible à la fin du segment de données, mais peut-être lorsque la quantité d'espace libérable atteint un pourcentage de seuil de la taille du segment de données total. (De même, lorsque vous BRK () UP, vous demanderiez probablement de l'espace proportionnelle à la taille actuelle du segment de données.)
MALLOC est également souvent, et principalement, à l'aide de l'appel système MMAP pour demander à la mémoire au noyau et utilisez munmap pour la publier. sbrk est moins utilisé.
La première chose que vous voulez faire est de vous différencier entre le noyau et l'allocation de programme. Comme @wyzard dit, Malloc utilise BRK (SBRK et parfois MMAP) pour obtenir plus de pages du noyau. Ma compréhension de Malloc est NTO très bonne, mais elle suit ce que vous pourriez appeler une arène. Il donne accès à l'accès à la mémoire et appelle les appels de système appropriés pour allouer la mémoire si nécessaire.
Une liste gratuite est une solution pour gérer la mémoire. Appeler MMAP ou BRK à chaque fois que vous avez besoin de plus de mémoire du noyau est lent et inefficace. Ces deux nécessiteront un passage de contexte en mode noyau et alloueront des structures de données à suivre ce que le processus possède la mémoire. Une liste gratuite au niveau utilisateur est une optimisation pour ne pas demander constamment et retourner la mémoire au noyau. L'objectif d'un programme utilisateur est de faire son travail, sans attendre que le noyau fasse son travail.
Maintenant pour répondre à vos autres questions:
Une autre façon de penser à une liste libre est comme cache. Un programme fera des demandes et le noyau essaiera de les réaliser à la demande plutôt que tout à la fois. Toutefois, lorsqu'un programme est effectué avec un morceau de mémoire, le chemin rapide ne doit pas le renvoyer au noyau, mais le mettre quelque part en sécurité pour être revêtu à nouveau. En particulier, une liste gratuite peut suivre les régions de mémoire qu'un allocateur peut tirer de, mais de la sorte de manière à ce que le code de l'utilisateur ne puisse pas simplement le co-opter et commencer à écrire sur tout cela. .
Si nous supposons que ce que nous supposons vraiment un blocage nécessite de le renvoyer sur le noyau et de la mettre à jour ses tables de page internes, la différence réside vraiment dans ce qui a une commande sur la page physique (ou le cadre) sous-jacent. Réfléchissant et renvoyant la mémoire au noyau signifie maintenant que le noyau peut désormais tirer de ces pages, alors que le renvoyer à une liste libre de niveau utilisateur signifie qu'une partie du programme contrôle toujours cette mémoire.
Cela commence à obtenir une zone différente (que je ne suis pas terriblement familier). L'allocator de la dalle est à l'origine du noyau gère la répartition de la mémoire. D'après ce que j'ai vu, la dalle tente de regrouper les allocations dans différentes tailles et dispose d'un pool de pages pour satisfaire ces demandes. Je crois que les architectures X86 communes permettront des allocations de mémoire physique continue dans les pouvoirs de deux octets de 16 octets à 4 Mo (même si je suis sur une machine de 64 bits). Je crois qu'il existe un concept de liste libre à ce niveau, ainsi que des moyens d'une mise à niveau efficace ou de la rétrogradation de la taille d'allocation pour permettre des besoins variables.
D'autre part, l'allocation de stockage sonne comme une garantie d'espace sur votre disque dur. En fait, je n'ai pas entendu le terme que je ne peux que spéculer.
Ici, vous vous référez à deux allocateurs différents,
Pour un programme C dans l'espace utilisateur, nous avons une mémoire de tas dans le Call_Stack où le malloc a lieu. Ceci est marqué par _Break qui est avancé par SBRK () lorsque davantage de mémoire est nécessaire.
dans le noyau Linux Chaque processus a Task_Structeur qui possède sa propre pile et un pointeur sur la liste des pages utilisées par elle.