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

Question

J'ai commencé à développer des logiciels pour les systèmes en temps réel, il y a quelques mois en C pour les applications de l'espace, et aussi pour les microcontrôleurs avec C++. Il y a une règle de base dans de tels systèmes , on ne doit jamais créer des tas d'objets (donc pas de malloc/nouveau), car il rend le programme non-déterministe. Je n'étais pas en mesure de vérifier l'exactitude de cette affirmation, quand on me dit que. Donc, Est-ce un énoncé correct?

La confusion, pour moi, autant que je sache, le déterminisme signifie que l'exécution d'un programme de deux fois exactement, le même chemin d'exécution. De ma compréhension, c'est un problème avec multithread systèmes, depuis l'exécution du même programme plusieurs fois différents threads qui s'exécutent dans un ordre différent à chaque fois.

Answer 1

Dans le contexte en temps réel des systèmes, il n'y a plus de déterminisme qu'un répétable "chemin d'exécution". Une autre propriété est que la chronologie des événements clés est bornée. Dans le dur en temps réel des systèmes, un événement qui se produit en dehors de son permis intervalle de temps (soit avant le début de l'intervalle, ou après la fin) représente une défaillance du système.

Dans ce contexte, l'utilisation de l'allocation dynamique de la mémoire peut entraîner la non-déterminisme, en particulier si le programme a une variable de modèle de distribution, de le libérer, et la réaffectation. Le calendrier des dotations, de libération, et la réaffectation des ressources peut varier au fil du temps - et donc de rendre les horaires pour l'ensemble du système imprévisible.

Answer 2

Le commentaire, comme indiqué, est incorrecte.

À l'aide d'un gestionnaire de tas avec les non-déterministe comportement crée un programme avec un comportement non déterministe. Mais c'est évident.

Légèrement moins évident, c'est l'existence de gestionnaires de tas avec déterministe du comportement. Peut-être le plus exemple bien connu est la piscine de l'allocateur. Il a un tableau de N*M octets, et un available[] masque de N bits. D'allouer, il vérifie la première entrée (bit test, O(N), déterministe de la limite supérieure). Pour désallouer, il définit la disposition des bits (O(1)). malloc(X) rond de X à la prochaine plus grande valeur de M pour sélectionner la droite de la piscine.

Cela pourrait ne pas être très efficace, notamment si votre choix de N et M sont trop élevés. Et si vous choisissez trop faible, votre programme peut échouer. Mais la limite pour N et M peuvent être plus faible que pour un programme équivalent sans allocation dynamique de la mémoire.

Answer 3

Rien dans le C11 standard ou en n1570 dit qu' malloc est déterministe (ou n'est pas); et ni certains autres documents comme malloc(3) sur Linux. BTW, bon nombre malloc implémentations de logiciels libres.

Mais malloc peut (et ne doit) ne parviennent pas, et son rendement n'est pas connu (un appel à malloc sur mon bureau serait pratiquement prendre moins d'une microseconde, mais je ne pouvais imaginer des situations étranges où il pourrait prendre beaucoup plus, peut-être le nombre de millisecondes sur un très chargé ordinateur; lire sur raclée). Et mon bureau Linux a l'ASLR (address space layout randomization) donc runnning le même programme deux fois donne différents malloc-ed adresses (dans l'espace d'adressage virtuel du processus). BTW ici est un déterministe (sous certaines hypothèses que vous avez besoin pour élaborer) mais pratiquement inutiles malloc mise en œuvre.

le déterminisme qui signifie que l'exécution d'un programme de deux fois exactement, le même chemin d'exécution

C'est pratiquement de mal dans la plupart des systèmes embarqués, parce que l'environnement physique est en train de changer; par exemple, le logiciel de pilotage d'un moteur-fusée ne peut pas s'attendre à ce que la poussée, ou le déplacement, la vitesse du vent, etc... est exactement la même d'un lancement à l'autre.

^{(donc, je suis surpris que vous croyez ou souhaitez que des systèmes temps réel sont déterministes; elles ne le sont jamais! Peut-être que vous vous souciez de WCET, qui est de plus en plus difficile à prévoir en raison de caches)}

BTW certains "temps réel" ou "intégrés" sont les systèmes d'exécution de leurs propres malloc (ou une variante de celui-ci). Les programmes C++ peuvent avoir leur allocateur-s, utilisable par standard contenants. Voir aussi cette et que, etc, etc.....

Et de haut niveau des couches de logiciel embarqué (pensez autonome de l'automobile et de sa planification des logiciels) sont certainement à l'aide d'allocation de tas et peut-être même la collecte des ordures techniques (dont certains sont en "temps réel"), mais ne sont généralement pas considérés comme critiques pour la sécurité.

Answer 4

tl;dr: Ce n'est pas que l'allocation de mémoire dynamique est intrinsèquement non-déterministe (comme vous l'a défini en termes identiques (les chemins d'exécution); c'est que généralement votre programme imprévisible. Plus précisément, vous ne pouvez pas prédire si l'allocateur peut échouer face à l'arbitraire de la séquence d'entrées.

Vous pourriez avoir un non-déterministe de l'allocateur. C'est en fait commune à l'extérieur de votre temps réel de monde, où les systèmes d'exploitation utilisent des choses comme la présentation de l'adresse de la randomisation. Bien sûr, cela ferait de votre programme de non-déterministe.

Mais ce n'est pas un cas intéressant, supposons donc parfaitement déterministe de l'allocateur: la même séquence d'allocations et de deallocations entraînera toujours les mêmes blocs, dans les mêmes lieux et de ces allocations et deallocations aura toujours bornée de temps de fonctionnement.

Maintenant, votre programme peut être déterministe: le même ensemble d'entrées de conduit exactement le même chemin d'exécution.

Le problème est que si vous êtes d'allouer et de libérer de la mémoire en réponse aux intrants, vous ne pouvez pas prédire si une allocation jamais échouer (et l'échec n'est pas une option).

Tout d'abord, votre programme peut présenter une fuite de mémoire. Donc, si il a besoin pour fonctionner indéfiniment, éventuellement une allocation échoue.

Mais même si vous pouvez prouver il n'y a pas de fuites, vous devez savoir qu'il n'y a jamais une séquence d'entrée qui pourrait demander plus de mémoire que ce qui est 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'allocation peut, en fonction de la séquence des allocations et libère, fragment de la mémoire et donc, à terme, être incapable de trouver un bloc contigu de satisfaire à une allocation, même si il y a suffisamment de mémoire disponible dans l'ensemble.

Il est très difficile de prouver qu'il n'y a pas de séquence d'entrées qui conduira à pathologiques de la fragmentation.

Vous pouvez concevoir des allocateurs de garantie il n'y aura pas de fragmentation (par exemple, par l'attribution de blocs d'une seule taille), mais qui met une importante contrainte sur l'appelant et, éventuellement, augmente la quantité de mémoire nécessaire en raison de la quantité de déchets. Et l'appelant doit encore prouver qu'il n'y a pas de fuites et qu'il y a un satiable de la limite supérieure sur le total de la mémoire requise quelle que soit la séquence d'entrées. Ce fardeau est si élevé qu'il est en fait plus simple de concevoir le système de sorte qu'il ne peut pas utiliser l'allocation dynamique de la mémoire.

Answer 5

Le problème avec les systèmes en temps réel, c'est que le programme doit strictement respecter certaines de mémoire et de calcul des restrictions quel que soit le chemin d'exécution prises (qui peuvent varier considérablement en fonction de l'entrée). Donc, quelle est l'utilisation des génériques de l'allocation dynamique de la mémoire (comme malloc/nouveau) signifie dans ce contexte? Cela signifie que le développeur à un certain point, n'est pas en mesure de déterminer avec précision la consommation de mémoire et il serait impossible de dire si le programme qui sera en mesure de répondre aux exigences, à la fois de mémoire et de puissance de calcul.