Autre que malloc / free, un programme nécessite-t-il que le système d'exploitation fournisse autre chose?

Question

Je travaille sur la conception du noyau (que je vais appeler le "noyau" juste pour être différent, mais c'est fondamentalement le même) pour un système d'exploitation sur lequel je travaille. Les spécificités du système d'exploitation lui-même ne sont pas pertinentes si je ne parviens pas à gérer plusieurs tâches à la fois, la gestion de la mémoire et d'autres éléments de base, je dois donc commencer par y travailler. J'ai quelques questions sur la conception d'une routine de malloc.

Je pense que malloc () fera soit partie du noyau lui-même (je penche pour cela), soit fait partie du programme, mais je vais devoir écrire ma propre implémentation de C bibliothèque standard de toute façon, donc je peux écrire un malloc. Ma question est en fait assez simple à cet égard, comment C (ou C ++) gère-t-il son tas?

Ce que l’on m’a toujours enseigné en théorie, c’est que le tas est un morceau de mémoire en expansion constante, qui commence à une adresse spécifiée et qui, dans bien des sens, se comporte comme une pile. De cette façon, je sais que les variables déclarées dans la portée globale sont au début et que davantage de variables sont "poussées". sur le tas comme ils sont déclarés dans leurs portées respectives, et les variables qui sortent de la portée sont simplement laissées dans l’espace mémoire, mais cet espace est marqué comme libre afin que le tas puisse s’étendre davantage si besoin est.

Ce que j’ai besoin de savoir, c’est comment, sur terre, C gère-t-il un tas en expansion dynamique de cette manière? Un programme C compilé fait-il ses propres appels à une routine malloc et gère-t-il son propre tas, ou dois-je lui fournir un espace qui s'étend automatiquement? De plus, comment le programme C sait-il où commence le tas?

Oh, et je sais que les mêmes concepts s'appliquent à d'autres langages, mais j'aimerais que tous les exemples soient en C / C ++ car je suis plus à l'aise avec ce langage. Je voudrais aussi ne pas m'inquiéter d'autres choses telles que la pile, car je pense que je suis capable de gérer des choses comme ça tout seul.

Donc, je suppose que ma vraie question est la suivante: autre que malloc / free (qui gère l’obtention et la libération de pages pour lui-même, etc.), un programme a-t-il besoin du système d’exploitation pour fournir autre chose?

Merci!

EDIT Je suis plus intéressé par la façon dont C utilise malloc en relation avec le tas que par le fonctionnement réel de la routine malloc elle-même. Si cela peut aider, je le fais sur x86, mais C est un compilateur croisé, donc ça ne devrait pas être grave ^ _ ^

ÉDITER DE PLUS: Je comprends que je puisse être en train de confondre les termes. On m'a appris que le "tas" était où le programme stockait des choses comme des variables globales / locales. Je suis habitué à faire face à une "pile" en programmation d’assemblage, et je viens de me rendre compte que je le pense probablement à la place. Une petite recherche de ma part montre que " heap " est plus communément utilisé pour faire référence à la mémoire totale qu'un programme s'est allouée, ou au nombre total (et à l'ordre) des pages de mémoire fournies par le système d'exploitation.

Alors, dans cet esprit, comment puis-je gérer une pile en expansion constante ? (Il semble que mon cours de théorie C était modérément ... imparfait.)

Answer 1

malloc est généralement implémenté dans l'environnement utilisateur C, en s'appuyant sur des appels système spécifiques du système d'exploitation pour mapper des pages de mémoire virtuelle. Le travail de malloc et de free consiste à gérer les pages de mémoire, dont la taille est fixée (généralement 4 Ko, mais parfois plus grandes), et à les découper en tranches et en dés morceaux que les applications peuvent utiliser.

Voir, par exemple, l'implémentation de la GNU libc .

Pour une implémentation beaucoup plus simple, consultez la classe Systèmes d'exploitation MIT du dernier année. Plus précisément, consultez le documentation finale sur le laboratoire . et consultez lib / malloc.c . Ce code utilise le système d'exploitation JOS développé dans la classe. La façon dont cela fonctionne est qu'il lit les tables de pages (fournies en lecture seule par le système d'exploitation), à la recherche de plages d'adresses virtuelles non mappées. Il utilise ensuite les appels système sys_page_alloc et sys_page_unmap pour mapper et démapper des pages dans le processus en cours.

Answer 2

Il existe plusieurs façons de résoudre le problème.

Le plus souvent, les programmes C ont leur propre fonctionnalité malloc / free. Celui-là travaillera pour les petits objets. Initialement (et dès que la mémoire est épuisée), le gestionnaire de mémoire demandera au système d'exploitation de plus de mémoire. Les méthodes traditionnelles pour ce faire sont mmap et sbrk sur les variantes unix (GlobalAlloc / LocalAlloc sur Win32).

Je vous suggère de consulter l'allocateur de mémoire Doug Lea ( google: dlmalloc) du point de vue du fournisseur de mémoire (par exemple, le système d'exploitation). Cet allocateur est excellent dans un très bon et possède des crochets pour tous les systèmes d'exploitation majeurs. Si vous voulez savoir ce qu’attend un système d’allocation hautes performances, c’est le code que vous choisirez en premier.

Answer 3

Confondez-vous le tas et la pile?

Je vous pose la question parce que vous parlez de "mémoire en expansion constante", de la portée et de l'insertion de variables dans le tas à mesure qu'elles sont déclarées. Cela ressemble certainement à ce que vous parlez de la pile.

Dans les implémentations C les plus courantes, les déclarations de variables automatiques telles que

int i;

entraînera généralement l'attribution de i sur la pile. En général, malloc ne sera impliqué que si vous l’invoquez explicitement ou si un appel de la bibliothèque que vous effectuez l’invoque.

Je vous conseillerais de consulter la section "Programmation Expert C". de Peter Van Der Linden pour en savoir plus sur le fonctionnement des programmes C avec la pile et le tas.

Answer 4

Lecture obligatoire: Knuth - L’art de la programmation informatique, volume 1, chapitre 2, section 2.5. Sinon, vous pourriez lire Kernighan & amp; Ritchie " Le langage de programmation C " voir une implémentation; ou, vous pouvez lire Plauger " La bibliothèque Standard C " pour voir une autre implémentation.

Je pense que ce que vous devez faire dans votre noyau sera quelque peu différent de ce que les programmes extérieurs au noyau voient. En particulier, l’allocation de mémoire dans le cœur des programmes concernera la mémoire virtuelle, etc., tandis que les programmes hors code voient simplement les résultats de ce que le noyau a fourni.

Answer 5

En savoir plus sur la gestion de la mémoire virtuelle (pagination). Il est hautement spécifique au processeur et chaque système d'exploitation implémente la gestion des machines virtuelles spécialement pour chaque processeur pris en charge. Si vous écrivez votre système d'exploitation pour x86 / amd64, lisez leurs manuels respectifs.

Answer 6

En règle générale, la bibliothèque C gère l'implémentation de malloc , demandant de la mémoire au système d'exploitation (via mmap ou, dans les systèmes plus anciens, sbrk ) si nécessaire. Ainsi, votre noyau devrait gérer l’allocation de pages entières par l’un de ces moyens.

Ensuite, il appartient à malloc de distribuer la mémoire de manière à ne pas trop fragmenter la mémoire disponible. Je ne suis pas trop au fait avec les détails de ceci, cependant; Cependant, le terme arena vient à l’esprit. Si je peux rechercher une référence, je mettrai à jour ce post.

Answer 7

Danger Danger !! Si vous envisagez même de tenter le développement du noyau, vous devez être très conscient du coût de vos ressources et de leur disponibilité relativement limitée ...

Une chose à propos de la récursion, c’est que c’est très coûteux (du moins dans le noyau), vous ne verrez pas beaucoup de fonctions écrites simplement pour continuer, sans quoi votre noyau paniquera.

Pour souligner ce que je veux dire ici (sur stackoverflow.com heh), consultez cet article à partir de Blog de débogage NT sur le dépassement de capacité de la pile du noyau, de manière spécifique,

  

& # 183; Sur les plates-formes x86, le   la pile en mode noyau est 12K .

     

& # 183; Sur les plates-formes x64, le   la pile en mode noyau est 24K . (basé sur x64   les plates-formes comprennent des systèmes avec   processeurs utilisant le processeur AMD64   architecture et processeurs utilisant le   Architecture Intel EM64T).

     

& # 183; Sur les plates-formes Itanium, le   la pile en mode noyau est 32 Ko avec un 32 Ko   sauvegarde magasin.

C'est vraiment, pas beaucoup;

  

Les suspects habituels

           

1. Utiliser la pile généreusement.

     

2. Appeler des fonctions récursivement.

Si vous relisez un peu le blog, vous verrez à quel point le développement du noyau peut être difficile avec un ensemble de problèmes plutôt unique. Votre cours théorique n'était pas faux, c'était simplement simple. ;)

Pour passer de la théorie - > le développement du noyau est aussi important que possible d'un commutateur context (peut-être enregistrer une interaction d'hyperviseur dans le mix !!).

De toute façon, ne supposez jamais, ne validez et testez pas vos attentes.