L’utilisation de la mémoire de tas (malloc / new) crée-t-elle un programme non déterministe?

Il y a quelques mois, j’ai commencé à développer des logiciels pour les systèmes temps réel en C pour les applications spatiales, ainsi que pour les microcontrôleurs en C ++. Il existe une règle de base dans de tels systèmes: il ne faut jamais créer d’objects de tas (donc pas de malloc / new), car cela rend le programme non déterministe . Je n’ai pas pu vérifier l’exactitude de cette déclaration lorsque les gens me le disent. Donc, est-ce une déclaration correcte?

La confusion pour moi est que, autant que je sache, le déterminisme signifie que l’exécution d’un programme deux fois conduira au même chemin d’exécution exact. À ma connaissance, il s’agit d’un problème avec les systèmes multithread, car exécuter plusieurs fois le même programme peut avoir des threads différents dans un ordre différent à chaque fois.

    Dans le contexte des systèmes temps réel, le déterminisme ne se limite pas à un “chemin d’exécution” reproductible. Une autre propriété requirejse est que la synchronisation des événements clés est limitée. Dans les systèmes temps réel durs, un événement qui se produit en dehors de son intervalle de temps autorisé (soit avant le début de cet intervalle, soit après la fin) représente une défaillance du système.

    Dans ce contexte, l’utilisation de l’allocation dynamic de la mémoire peut entraîner un non-déterminisme, en particulier si le programme a un schéma d’allocation, de désallocation et de réallocation variable. Le calendrier des allocations, de la désallocation et de la réallocation peut varier dans le temps, ce qui rend imprévisibles les délais pour le système dans son ensemble.

    Le commentaire, comme indiqué, est incorrect.

    L’utilisation d’un gestionnaire de tas avec un comportement non déterministe crée un programme avec un comportement non déterministe. Mais c’est évident.

    Un peu moins évident est l’existence de gestionnaires de tas avec un comportement déterministe. L’exemple le plus connu est peut-être l’allocateur de pool. Il a un tableau de N * M octets et un masque available[] de N bits disponible. Pour allouer, il vérifie la première entrée disponible (bit test, O (N), borne supérieure déterministe). Pour désallouer, il définit le bit disponible (O (1)). malloc(X) arrondira X à la plus grande valeur de M pour choisir le bon pool.

    Cela pourrait ne pas être très efficace, surtout si vos choix de N et M sont trop élevés. Et si vous choisissez trop bas, votre programme peut échouer. Mais les limites pour N et M peuvent être inférieures à celles d’un programme équivalent sans allocation de mémoire dynamic.

    Rien dans la norme C11 ou dans n1570 ne dit que malloc est déterministe (ou non); et aucune autre documentation comme malloc (3) sur Linux. BTW, de nombreuses implémentations de malloc sont des logiciels libres .

    Mais malloc peut (et ne réussit) pas, et ses performances ne sont pas connues (un appel typique à malloc sur mon bureau prendrait pratiquement moins d’une microseconde, mais je pourrais imaginer des situations étranges où cela pourrait prendre beaucoup plus, peut-être plusieurs millisecondes). ordinateur très chargé, lire à propos de thrashing ). Et mon bureau Linux a ASLR (randomisation de la disposition de l’espace d’adressage), ainsi, exécuter deux fois le même programme donne différentes adresses malloc (dans l’espace d’adressage virtuel du processus). BTW est ici une déterministe (sous des hypothèses spécifiques que vous devez élaborer) mais l’ implémentation malloc pratiquement inutile.

    déterminisme signifie que l’exécution d’un programme deux fois conduira au même chemin d’exécution exact

    Cela est pratiquement faux dans la plupart des systèmes embarqués, car l’environnement physique change; Par exemple, le logiciel qui pilote un moteur de fusée ne peut pas s’attendre à ce que la poussée, la traînée, la vitesse du vent, etc. soient exactement les mêmes d’un lancement à l’autre.

    (Je suis donc surpris que vous croyiez ou souhaitiez que les systèmes en temps réel soient déterministes; ils ne le sont jamais! Peut-être que vous vous souciez de WCET , qui est de plus en plus difficile à prévoir à cause des caches )

    Certains systèmes “temps réel” ou “embarqués” implémentent leur propre malloc (ou une variante de celui-ci). Les programmes C ++ peuvent avoir leur allocateur -s, utilisable par les conteneurs standard s. Voir aussi ceci et cela , etc, etc …..

    Et les couches de haut niveau de logiciels embarqués (pensez à une automobile autonome et à son logiciel de planification ) utilisent certainement des techniques d’allocation de tas et peut-être même de récupération de mémoire (certaines en temps réel), mais ne sont généralement pas considérées comme critiques.

    tl; dr: L’allocation dynamic de la mémoire n’est pas insortingnsèquement déterministe (comme vous l’avez définie en termes de chemins d’exécution identiques); c’est que cela rend généralement votre programme imprévisible . Plus précisément, vous ne pouvez pas prédire si l’allocateur risque d’échouer face à une séquence arbitraire d’entrées.

    Vous pouvez avoir un allocateur non déterministe. Ceci est en réalité courant en dehors de votre monde en temps réel, où les systèmes d’exploitation utilisent des choses comme la randomisation de la présentation des adresses. Bien sûr, cela rendrait votre programme non déterministe.

    Mais ce n’est pas un cas intéressant, supposons donc un allocateur parfaitement déterministe: la même séquence d’allocations et de désallocations donnera toujours les mêmes blocs aux mêmes emplacements et ces allocations et désallocations auront toujours une durée d’exécution limitée.

    Maintenant, votre programme peut être déterministe: le même ensemble d’entrées mènera exactement au même chemin d’exécution.

    Le problème est que si vous allouez et libérez de la mémoire en réponse à des entrées, vous ne pouvez pas prédire si une allocation échouera jamais (et l’échec n’est pas une option).

    Tout d’abord, votre programme pourrait perdre de la mémoire. Donc, s’il doit fonctionner indéfiniment, une allocation échouera éventuellement.

    Mais même si vous pouvez prouver qu’il n’y a pas de fuite, vous devez savoir qu’il n’y a jamais de séquence d’entrée pouvant exiger plus de mémoire que celle disponible.

    Mais même si vous pouvez prouver que le programme n’aura jamais besoin de plus de mémoire que ce qui est disponible, l’allocateur pourrait, en fonction de la séquence d’allocations et de libérations, fragmenter la mémoire et donc ne pas trouver un bloc contigu pour satisfaire une allocation. il y a assez de mémoire libre dans l’ensemble.

    Il est très difficile de prouver qu’il n’ya pas de séquence d’intrants qui conduirait à une fragmentation pathologique.

    Vous pouvez concevoir des allocateurs pour garantir qu’il n’y aura pas de fragmentation (par exemple, en allouant des blocs d’une seule taille), mais cela impose une contrainte substantielle à l’appelant et augmente éventuellement la quantité de mémoire requirejse à cause du gaspillage. Et l’appelant doit toujours prouver qu’il n’y a pas de fuite et qu’il existe une limite supérieure saturable sur la mémoire totale requirejse, quelle que soit la séquence des entrées. Ce fardeau est tellement élevé qu’il est en fait plus simple de concevoir le système de manière à ce qu’il n’utilise pas l’allocation dynamic de mémoire.

    Le problème des systèmes temps réel est que le programme doit respecter ssortingctement certaines ressortingctions de calcul et de mémoire, quel que soit le chemin d’exécution pris (qui peut encore varier considérablement en fonction de l’entrée). Alors, que signifie l’utilisation d’une allocation de mémoire dynamic générique (telle que malloc / new) dans ce contexte? Cela signifie que le développeur à un moment donné n’est pas en mesure de déterminer la consommation de mémoire exacte et il serait impossible de savoir si le programme résultant sera en mesure de répondre aux exigences, à la fois pour la mémoire et la puissance de calcul.

    Oui c’est correct. Pour le type d’applications que vous mentionnez, tout ce qui peut se produire doit être spécifié en détail. Le programme doit gérer le pire scénario selon les spécifications et mettre de côté autant de mémoire, pas plus, pas moins. La situation où “nous ne soaps pas combien d’intrants nous recevons” n’existe pas. Le pire scénario est spécifié avec des nombres fixes.

    Votre programme doit être déterministe en ce sens qu’il peut tout gérer jusqu’au pire des scénarios.

    Le but du tas est de permettre à plusieurs applications non liées de partager de la mémoire RAM, comme dans un PC, où la quantité de programmes / processus / threads en cours d’exécution n’est pas déterministe. Ce scénario n’existe pas dans un système temps réel.

    De plus, le tas est de nature non déterministe, car des segments sont ajoutés ou supprimés au fil du temps.

    Plus d’infos ici: https://electronics.stackexchange.com/a/171581/6102

    Même si votre alloceur de tas a un comportement reproductible (la même séquence d’allocation et les appels gratuits génèrent la même séquence de blocs, donc (espérons-le) le même état de segment interne), l’état du tas peut varier considérablement si la séquence des appels est modifiée , entraînant potentiellement une fragmentation qui entraînera des échecs d’allocation de mémoire de manière imprévisible.

    La raison pour laquelle l’allocation de tas est mal vue est carrément interdite dans les systèmes embarqués, esp. Les systèmes essentiels à la mission, tels que le guidage des aéronefs ou des engins spatiaux ou les systèmes de survie, ne permettent pas de tester toutes les variations possibles de la séquence d’appels malloc / libres pouvant se produire en réponse à des événements insortingnsèquement asynchrones.

    La solution est que chaque gestionnaire dispose d’une seule mémoire pour son objective et que cela n’a plus d’importance (du moins en ce qui concerne l’utilisation de la mémoire) dans quel ordre ces gestionnaires sont appelés.

    Le problème lié à l’utilisation du tas dans les logiciels temps réel difficiles, à savoir que les allocations de tas peuvent échouer. Que faites-vous quand vous êtes à court de tas?

    Vous parlez d’applications spatiales. Vous avez des exigences ssortingctes en matière de non-échec. Vous ne devez avoir aucune possibilité de fuite de mémoire, il n’y a donc pas assez pour que le code du mode sans échec soit exécuté. Vous ne devez pas tomber. Vous ne devez pas lancer d’exceptions sans bloc catch. Vous n’avez probablement pas de système d’exploitation avec mémoire protégée, alors une application en panne peut en théorie tout éliminer.

    Vous ne voulez probablement pas utiliser de tas du tout. Les avantages ne l’emportent pas sur les coûts de l’ensemble du programme.

    Non déterministe signifie normalement autre chose mais dans ce cas, la meilleure lecture est qu’ils veulent que le comportement du programme soit complètement prévisible.

    Introduire le RTOS Integrity de GHS:

    https://www.ghs.com/products/rtos/integrity.html

    et LynxOS:

    http://www.lynx.com/products/real-time-operating-systems/lynxos-178-rtos-for-do-178b-software-certificateion/

    LynxOS et Integrity RTOS font partie des logiciels utilisés dans les applications spatiales, les missiles, les avions, etc., car beaucoup d’autres ne sont pas approuvés ou certifiés par les autorités (par exemple, FAA).

    https://www.ghs.com/news/230210r.html

    Pour répondre aux critères rigoureux des applications spatiales, Integrity RTOS fournit en réalité une vérification formelle, c’est-à-dire une logique mathématiquement prouvée, que leur logiciel se comporte conformément aux spécifications.

    Parmi ces critères, pour citer ici:

    https://en.wikipedia.org/wiki/Integrity_(operating_system)

    et ici:

    Green Hills Integrity Allocation dynamic de la mémoire

    est-ce:

    entrer la description de l'image ici

    Je ne suis pas un spécialiste des méthodes formelles, mais l’une des exigences de cette vérification est peut-être de supprimer les incertitudes liées au calendrier nécessaire à l’allocation de mémoire. Dans RTOS, tous les événements sont précisément à des millisecondes près l’un de l’autre. Et l’allocation dynamic de la mémoire pose toujours un problème de synchronisation.

    Mathématiquement, vous devez vraiment prouver que tout a fonctionné à partir des hypothèses les plus fondamentales concernant la synchronisation et la quantité de mémoire.

    Et si vous pensez aux alternatives à la mémoire en tas: la mémoire statique . L’adresse est fixe, la taille allouée est fixe. La position en mémoire est fixe. Il est donc très facile de raisonner sur la suffisance de mémoire, la fiabilité, la disponibilité, etc.

    Réponse courte

    Il existe certains effets sur les valeurs de données ou leurs dissortingbutions d’incertitude statistique, par exemple, un dispositif à scintillateur à déclenchement de premier ou de second niveau pouvant dériver de la quantité de temps non reproductible que vous devrez attendre pour malloc/free .

    Le pire aspect est qu’ils ne sont pas liés au phénomène physique, ni au matériel, mais à l’état de la mémoire (et de son histoire).

    Votre objective, dans ce cas, est de reconstituer la séquence originale des événements à partir des données affectées par ces erreurs. La séquence reconstruite / supposée sera également affectée par des erreurs. Cette itération ne fera pas toujours la convergence sur une solution stable; on ne dit pas que ce sera le bon vos données ne sont plus indépendantes … Vous risquez un court-circuit logique …

    Réponse plus longue

    Vous avez déclaré “Je n’ai pas pu vérifier l’exactitude de cette déclaration lorsque les gens me le disent” .
    Je vais essayer de vous donner une situation / étude de cas purement hypothétique.

    Imaginons que vous traitez avec un capteur CCD ou avec des déclencheurs de scintillateurs de premier et de deuxième niveau sur un système devant économiser des ressources (vous êtes dans l’espace).
    Le taux d’acquisition sera défini de telle sorte que l’arrière-plan sera à x% du MAXBINCOUNT .

    • Il y a une rafale, vous avez un pic dans les comptes et un débordement dans le compteur de bacs.
      Je veux tout: vous passez au taux d’acquisition maximum et vous terminez votre tampon.
      Vous allez libérer / allouer plus de mémoire pendant que vous terminez le tampon supplémentaire.
      Que vas-tu faire?

      1. Vous allez garder le contrecoup risquant le débordement (le deuxième niveau va essayer de compter correctement le timing des paquets de données) mais dans ce cas, vous allez sousestimer les comptes pour cette période?
      2. vous allez arrêter le compteur en introduisant un trou dans la série chronologique ?

      Notez que:

      • En attente d’une allocation, vous perdrez le transitoire (ou au moins son début).
      • Quoi que vous fassiez, cela dépend de l’état de votre mémoire et il n’est pas reproductible.
    • Maintenant, le signal est variable autour du maxbincount maximal au débit maximal autorisé par votre matériel, et l’événement est plus long que d’habitude.
      Vous terminez l’espace et demandez plus … en attendant, vous vous engagez dans le même problème ci-dessus.
      Les dépassements et les pics systématiques comptent-ils sous-estimation ou les trous dans les séries chronologiques?

    Déplaçons-nous un deuxième niveau (il peut aussi être au 1er niveau).

    Depuis votre matériel, vous recevez plus de données que vous ne pouvez en stocker ou transmettre.
    Vous devez regrouper les données dans le temps ou dans l’espace (2×2, 4×4, … 16×16 … 256×256 … mise à l’échelle des pixels …).

    L’incertitude du problème précédent peut affecter la dissortingbution des erreurs .
    Il existe des parameters CCD pour lesquels vous avez les pixels de la bordure avec des comptages proches du nombre maxbincount (cela dépend de “où” vous voulez mieux voir).
    Maintenant, vous pouvez avoir une douche sur votre CCD ou un seul grand spot avec le même nombre total de points, mais avec une incertitude statistique différente (la partie introduite par le temps d’attente) …

    Donc, par exemple, lorsque vous vous attendez à un profil de Lorentz, vous pouvez obtenir sa convolution avec une gaussienne (une Voigt), ou si la seconde est vraiment dominante avec une Gaussienne sale

    Il y a toujours un compromis. C’est l’environnement d’exécution du programme et les tâches qu’il effectue qui devraient être la base pour décider si HEAP doit être utilisé ou non.

    L’object tas est efficace lorsque vous souhaitez partager les données entre plusieurs appels de fonction. Il suffit de passer le pointeur car le tas est accessible globalement. Il y a aussi des inconvénients. Certaines fonctions peuvent libérer cette mémoire, mais certaines références peuvent également exister ailleurs.

    Si la mémoire du tas n’est pas libérée après le travail et que le programme continue d’allouer plus de mémoire, à un moment donné, HEAP sera à court de mémoire et affectera le caractère déterministe du programme.