Éditeurs de liens et liaison dynamique

Les éditeurs de liens sont des outils logiciels qu'un système d'exploitation utilise pour combiner des fichiers objet en un fichier exécutable. Un éditeur de liens effectue la résolution de noms, faisant correspondre le nom d'une variable ou d'une fonction dans une application à une adresse de mémoire virtuelle (virtual memory) qu'elle aura lorsqu'elle sera chargée et exécutée. Un éditeur de liens combine de nombreuses parties distinctes d'un programme, réorganise l'allocation de stockage afin que toutes les pièces puissent s'assembler, et ajuste les adresses afin que le programme puisse s'exécuter sous la nouvelle organisation de la mémoire. Après qu'un éditeur de liens a terminé la tâche de combiner plusieurs fichiers objet générés par un compilateur en un seul fichier exécutable, le fichier exécutable peut être chargé et exécuté par le système d'exploitation (Figure 6.27).

Figure 6.27 Un processus d'édition de liens inclut des fichiers objet et des bibliothèques. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Le mécanisme (mechanism) qui permet à un programme d'associer des symboles de code externes à des adresses au moment de l'exécution est la liaison dynamique (dynamic linking). Le processus d'allocation (allocation) commence lorsque le processus est en cours d'exécution en divisant la mémoire en parties plus petites appelées segments. Par exemple, l'agencement de la mémoire de Linux est divisé de telle sorte que le code commence à l'emplacement 0, les données commencent immédiatement au-dessus du code et la pile commence à l'adresse la plus élevée, comme illustré dans la Figure 6.28. Lorsqu'un processus est démarré, le système d'exploitation chargera le fichier en mémoire avec l'option supplémentaire de partage (sharing) de la mémoire avec d'autres. Le système d'exploitation facilite la taille de la mémoire au moment de l'exécution en ajoutant plus de mémoire allouée si nécessaire.

Figure 6.28 Dans l'agencement de la mémoire de Linux, le code commence à l'emplacement 0, les données commencent immédiatement au-dessus du code et croissent vers le haut, et la pile commence à l'adresse la plus élevée et croît vers le bas. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Dans la liaison dynamique, le code est localisé et chargé lors de la première exécution du programme. Depuis la fin des années 1980, la plupart des systèmes ont commencé à prendre en charge les bibliothèques partagées et la liaison dynamique en ne conservant qu'une seule copie des paquets de bibliothèques courants en mémoire, partagée par tous les processus. Cela signifie que le système ne sait pas où la bibliothèque est chargée avant l'exécution et doit résoudre les références dynamiquement lorsque le programme s'exécute.

Gestion dynamique du stockage

Il existe deux opérations de base utilisées dans la gestion dynamique du stockage pour gérer une mémoire ou un stockage afin de satisfaire divers besoins : allouer un bloc avec un nombre donné d'octets ou libérer un bloc précédemment alloué. Il existe deux approches générales pour appliquer ces opérations d'allocation dynamique de stockage : (1) l'allocation de pile (stack allocation), qui est hiérarchique et restreinte, mais simple et efficace ; et (2) l'allocation de tas (heap allocation), qui est plus générale mais plus difficile à implémenter et moins efficace.

La structure de données linéaire qui suit un ordre LIFO (dernier entré, premier sorti), comme dans la configuration de la figure de données de pile dans la Figure 6.29, est appelée allocation de pile (stack allocation). Dans l'approche par pile, la mémoire est libérée dans l'ordre inverse de l'allocation. Par exemple, si la procédure X appelle Y, alors Y retournera certainement avant de retourner de X. Les piles tirent parti de cette pratique de programmation pour stocker l'état de l'appel de procédure actuel. Lorsque l'allocation de mémoire (memory allocation) et la libération sont partiellement prévisibles, une approche par pile peut être utilisée.

Figure 6.29 Cette représentation de structure de données de pile montre une approche dernier entré, premier sorti. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

L'allocation des données dans une structure de données arborescente appelée tas est l'allocation de tas (heap allocation). Un tas est représenté par un arbre binaire complet. Comme le montre la Figure 6.30, une structure de données de tas (heap data) peut être de deux types : tas max et tas min. Le tas max présente le nœud racine avec la plus grande valeur et il en va de même pour les sous-arbres. C'est l'inverse pour le tas min, où la racine aura la valeur minimale et il en va de même pour les sous-arbres.

Figure 6.30 L'allocation de tas utilise une structure de données appelée tas pour gérer la mémoire et le stockage. Il existe deux types de structures ou d'arbres de tas : un pour le tas max et un pour le tas min. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Les gestionnaires de mémoire, tels que ceux utilisés en C et C++, ne stockent pas réellement la mémoire disponible dans une structure de données de tas. Au lieu de cela, ils manipulent une liste doublement chaînée de blocs, qu'ils appellent de manière confuse un « tas », et tentent d'optimiser la mémoire en utilisant une méthode de « meilleur ajustement ».

Les gestionnaires de mémoire utilisent l'approche par tas lorsque l'allocation et la libération de mémoire ne sont pas prévisibles (c'est-à-dire lorsqu'il n'est pas clair combien de mémoire est nécessaire avant d'exécuter le programme). Typiquement, le tas stocke des structures de données dont la taille peut changer au fil du temps en fonction du nombre d'éléments ajoutés ou supprimés de la structure de données. La mémoire de tas correspondante se compose de zones allouées et de zones libres (ou trous).

Mémoire virtuelle

Le composant clé du système d'exploitation (operating system) qui assure le processus (process) et son isolation (isolation) en garantissant que chaque processus obtient sa propre vue de la mémoire est la mémoire virtuelle. Un programme en cours d'exécution (processus) a une vue apparemment infinie de la mémoire et peut accéder à n'importe quelle région sans se soucier des autres programmes qui pourraient également s'exécuter sur l'ordinateur. Le système d'exploitation traduit de manière transparente chaque requête de mémoire de processus en une région distincte de la mémoire physique du matériel via la traduction d'adresses. Lorsque le système doit trouver une adresse physique en mémoire qui correspond à l'adresse virtuelle, une traduction d'adresses (address translation) se produit. Le processus en cours d'exécution ne traite que les adresses virtuelles et ne voit jamais l'adresse physique. La mémoire virtuelle est mappée à la mémoire physique en unités appelées « pages ».

Il y a cependant un coût temporel associé à l'exécution de la traduction d'adresses de la mémoire virtuelle à la mémoire physique, cependant, et cela peut s'accumuler étant donné que la plupart des programmes ont besoin d'accéder à la mémoire pour stocker des données. Pour accélérer la traduction d'adresses, le CPU dispose d'un matériel dédié pour la mise en cache (stockage) des traductions d'adresses récentes, appelé mémoire tampon d'adresses (TLB) (translation lookaside buffer (TLB)). Un TLB est un cache mémoire qui stocke la transaction récente de la mémoire virtuelle vers la mémoire physique. Les TLB aident le CPU à éviter de faire plusieurs allers-retours vers la mémoire principale juste pour résoudre un seul accès à la mémoire virtuelle en ne nécessitant qu'un seul aller-retour (Figure 6.31).

Un TLB contient les entrées de table de pages qui ont été utilisées le plus récemment. Étant donné une adresse virtuelle, le processeur examine la table TLB. Si une entrée de table de pages est présente, c'est un « hit » (succès). Cela signifie que le numéro de cadre est récupéré et que l'adresse réelle est formée. Si une entrée de table de pages n'est pas trouvée dans le TLB, c'est un « miss » (échec). Dans ce cas, le numéro de page est utilisé comme index lors du traitement de la table de pages. Le TLB vérifie si la page est déjà en mémoire ; si ce n'est pas le cas, alors un défaut de page (page fault) est émis et le TLB est mis à jour pour inclure la nouvelle entrée de page.

Figure 6.31 Les mémoires tampons d'adresses (TLB) accélèrent la traduction d'adresses en utilisant une approche qui implique la détection des « succès » (ce qui signifie qu'une entrée de table de pages est présente dans le TLB) et des « échecs » (une entrée de table de pages n'est pas trouvée dans le TLB). (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Pagination à la demande

Le mécanisme (mechanism) de stockage qui utilise une forme de page pour récupérer un processus (process) de la mémoire secondaire ou virtuelle vers la mémoire principale est appelé pagination (paging). La mémoire virtuelle présentait une quantité de mémoire apparemment infinie au processus en cours d'exécution, mais que se passe-t-il lorsque le système d'exploitation (operating system) manque de mémoire physique libre ? Les systèmes d'exploitation modernes ont également une solution de secours lorsque la DRAM est épuisée, ce qui signifie que la mémoire virtuelle peut être mappée sur disque pour répondre à la demande. Le mécanisme de stockage dans lequel les pages ne doivent être allouées en mémoire que si elles sont requises par le processus d'exécution est appelé pagination à la demande (demand paging). La Figure 6.32 montre un CPU qui demande des pages de la mémoire virtuelle vers la mémoire principale (c'est-à-dire « swap in ») et libère des pages de la mémoire principale vers la mémoire virtuelle (c'est-à-dire « swap out »). La taille de l'ensemble de travail (WSS) (working set size (WSS)) fait référence à la quantité totale de mémoire qu'un processus requiert pendant une période d'activité spécifique, mesurée comme l'ensemble des pages ou des blocs de données auxquels le processus accède. La WSS est mesurée en suivant les pages uniques qu'un processus référence sur un intervalle de temps fixe. Cela fournit une estimation de l'empreinte mémoire active du processus et aide aux décisions de gestion de la mémoire comme la pagination et l'échange pour optimiser les performances et l'allocation (allocation) des ressources.

Figure 6.32 Dans la pagination à la demande, un CPU récupère des pages de la mémoire virtuelle vers la mémoire principale et libère des pages de la mémoire principale vers la mémoire virtuelle. (source : Copyright Rice University, OpenStax, sous licence CC BY 4.0)

Lorsque le CPU demande une page et que cette page n'est pas présente dans la mémoire principale, nous appelons cette situation un défaut de page (page fault). Un défaut de page se produit lorsqu'un processus référence une page qui se trouve dans le stockage de sauvegarde. Pour gérer un défaut de page, le CPU transfère le contrôle du programme au système d'exploitation pour demander la page requise à la mémoire principale. Le système d'exploitation trouve un cadre de page libre en mémoire, charge la page du stockage de sauvegarde vers la mémoire principale et reprend l'exécution du fil d'exécution (thread). Le CPU dispose d'un matériel spécial pour aider à reprendre l'exécution après un défaut de page.

Étant donné que l'accès au disque est beaucoup plus lent que la DRAM, les systèmes d'exploitation sont souvent conçus pour échanger de manière prédictive les pages utilisées vers la DRAM et les pages inutilisées vers le disque. Le processus d'amener des pages en mémoire (c'est-à-dire la pagination (paging) à la demande) est appelé récupération de page (page fetching). La plupart des systèmes d'exploitation modernes utilisent la récupération de page en démarrant le processus sans pages chargées et ne chargent une page en mémoire que lorsqu'elle est référencée. Si une page demandée est stockée sur le disque, une prélecture, qui est l'acte d'essayer de prédire quand les pages seront nécessaires et de les charger à l'avance pour éviter les défauts de page, est effectuée.

Si toute la mémoire est utilisée, il est nécessaire de supprimer une page chaque fois qu'il y a un défaut de page. Ce processus (process) est appelé remplacement de page (page replacement). Lors du remplacement de page, une page de la DRAM (pleine) est échangée vers le disque tandis que la page demandée est amenée dans la DRAM. Cependant, si trop de processus ont besoin d'accéder à beaucoup de mémoire en va-et-vient entre la DRAM et le disque, cela pose des problèmes. Par exemple, chaque défaut de page entraîne le déplacement d'une des pages actives vers le disque, de sorte qu'un autre défaut de page se produit bientôt, et cela conduit au paginage intempestif (thrashing). Le paginage intempestif se produit lorsqu'un système d'exploitation (operating system) d'ordinateur est submergé par le nombre de processus demandant de la mémoire. Cette situation conduit à un cycle où le système passe plus de temps à déplacer des données entre la mémoire physique et le stockage sur disque (pagination ou échange) qu'à exécuter des processus réels. C'est comme un restaurant très fréquenté où le personnel passe plus de temps à réorganiser les tables qu'à servir de la nourriture. La cause principale du paginage intempestif est souvent qu'un trop grand nombre de programmes s'exécutent simultanément. Ces activités dépassent la mémoire disponible, ce qui amène le système à constamment essayer de faire de la place pour de nouvelles requêtes en déplaçant des données vers et depuis le disque.

Les stratégies pour prévenir le paginage intempestif incluent la limitation du nombre de programmes exécutés simultanément pour éviter le sur-engagement de mémoire, l'optimisation de la manière dont la mémoire est allouée aux processus, et éventuellement l'augmentation de la mémoire physique du système. En gérant la mémoire plus efficacement et en s'assurant que le système n'est pas surchargé de trop de tâches, le système peut non seulement éviter un ralentissement, mais aussi améliorer considérablement ses performances.

Dans les cas extrêmes de paginage intempestif, le système d'exploitation peut passer tout son temps à récupérer et à remplacer des pages et ne fera pas beaucoup de travail. C'est l'une des raisons pour lesquelles nos appareils peuvent ralentir jusqu'à l'arrêt lorsqu'ils manquent de mémoire et que chaque fil d'exécution doit attendre les pages demandées.

Concepts en pratique

Impatience avec les ordinateurs

Nous avons tous connu cela : sur nos ordinateurs portables, nous mettons la touche finale à une présentation de diapositives, tout en vérifiant nos e-mails, en téléchargeant une photo sur notre fil de médias sociaux, en écoutant une nouvelle playlist que notre ami vient de partager avec nous, en regardant une vidéo, en saisissant des données dans un tableur, et tout se fige — l'écran, le clavier, le pavé tactile. Non seulement rien ne fait ce que nous lui demandons, mais tout reste immobile. Ou pire, la petite roue tourne et ne s'arrête jamais. Maintenant que vous avez lu sur la mémoire, la gestion dynamique du stockage, l'allocation (allocation) des ressources et le paginage intempestif, réfléchissez à ce qui se passe à l'intérieur de votre CPU.

Si vous utilisez un ordinateur sous Windows, consultez cette ressource pour voir comment vous pourriez aider votre système d'exploitation à mieux fonctionner.