Создает ли использование кучи памяти (malloc / new) недетерминированную программу?

Комментарий, как указано, неверен.

Использование менеджера кучи с недетерминирована Поведение создает программу с недетерминированным поведением. Но это очевидно.

Немного менее очевидно существование менеджеров кучи с детерминированным поведением. Пожалуй, самый известный пример — распределитель пулов. Он имеет массив из N * M байтов и available[] маска из N бит. Для выделения он проверяет первую доступную запись (битовый тест, O (N), детерминированная верхняя граница). Для освобождения он устанавливает доступный бит (O (1)). malloc(X) округлит X до следующего наибольшего значения M, чтобы выбрать правильный пул.

Это может быть не очень эффективно, особенно если ваш выбор N и M слишком высок. И если вы выберете слишком низкий уровень, ваша программа может потерпеть неудачу. Но пределы для N и M могут быть ниже, чем для эквивалентной программы без динамического выделения памяти.

Ничего в C11 стандарт или в n1570 Говорит, что malloc является детерминированным (или нет); и ни одна другая документация, как таНос (3) в линуксе Кстати, многие malloc реализации являются бесплатно программное обеспечение.

Но malloc может (и не работает), и его производительность не известна (типичный вызов malloc на моем рабочем столе будет практически займет меньше микросекунды, но я могу представить себе странные ситуации, когда это может занять гораздо больше, возможно, много миллисекунд на очень загруженном компьютере; прочитать о порка). И мой рабочий стол Linux имеет ASLR (рандомизация размещения адресного пространства), поэтому запуск одной и той же программы дважды дает разные mallocадреса (в виртуальном адресном пространстве процесса). КСТАТИ Вот является детерминированным (при определенных допущениях, которые вам необходимо уточнить), но практически бесполезный malloc реализация.

детерминизм означает, что двойной запуск программы приведет к точному и одинаковому пути выполнения

Это практически неправильно в большинстве встроенных систем, потому что физическая среда меняется; например, программное обеспечение, управляющее ракетным двигателем, не может ожидать, что тяга, или сопротивление, или скорость ветра и т. д. именно так то же самое от одного запуска до следующего.

^{(поэтому я удивлен, что вы верите или хотите, чтобы системы реального времени были детерминированными; они никогда не бывают! Возможно, вы заботитесь о WCET, что все труднее прогнозировать из-за кэши)}

Кстати, некоторые «в реальном времени» или «встроенные» системы реализуют свои собственные malloc (или какой-то его вариант). Программы на C ++ могут иметь свои распределитель-с, можно использовать по стандарту контейнерs. Смотрите также этот а также тот, и т. д. …..

И высокоуровневые уровни встроенного программного обеспечения (подумайте об автономном автомобиле и его планирование программное обеспечение), конечно, используют выделение кучи и, возможно, даже вывоз мусора методы (некоторые из которых «в режиме реального времени»), но, как правило, не считаются критически важными для безопасности.

tl; dr: Дело не в том, что динамическое распределение памяти по своей сути недетерминирована (как вы определили это с точки зрения идентичных путей выполнения); это то, что обычно делает вашу программу непредсказуемый. В частности, вы не можете предсказать, может ли распределитель потерпеть неудачу при произвольной последовательности входных данных.

Вы можете иметь недетерминированный распределитель. Это на самом деле распространено за пределами вашего мира реального времени, где операционные системы используют такие вещи, как рандомизация размещения адресов. Конечно, это сделает вашу программу недетерминированной.

Но это не интересный случай, поэтому давайте предположим, что распределитель полностью и детерминирован: одна и та же последовательность распределений и освобождений всегда будет приводить к одинаковым блокам в одних и тех же местах, и эти распределения и освобождения всегда будут иметь ограниченное время выполнения.

Теперь ваша программа может быть детерминированной: один и тот же набор входов приведет к точно такому пути выполнения.

Проблема заключается в том, что если вы выделяете и освобождаете память в ответ на входные данные, вы не можете предсказать, будет ли когда-либо выделение памяти (и отказ не возможен).

Во-первых, ваша программа может утечь память. Так что, если он должен работать бесконечно, в конечном итоге распределение не удастся.

Но даже если вы можете доказать отсутствие утечек, вы должны знать, что никогда не будет входной последовательности, которая могла бы потребовать больше памяти, чем доступно.

Но даже если вы можете доказать, что программе никогда не понадобится больше памяти, чем доступно, распределитель может, в зависимости от последовательности выделений и освобождений, фрагментировать память и, таким образом, в конечном итоге не сможет найти непрерывный блок для удовлетворения выделения, даже если в целом достаточно свободной памяти.

Очень трудно доказать, что нет последовательности входов, которая приведет к патологической фрагментации.

Вы можете спроектировать распределители, чтобы гарантировать, что не будет фрагментации (например, путем выделения блоков только одного размера), но это накладывает существенное ограничение на вызывающего и, возможно, увеличивает объем памяти, требуемый из-за потери. И вызывающий должен все же доказать, что нет утечек и что существует допустимая верхняя граница общего объема памяти, требуемой независимо от последовательности входов. Это бремя настолько велико, что на самом деле проще спроектировать систему, чтобы она не использовала динамическое распределение памяти.

Работа с системами реального времени заключается в том, что программа должна строго соответствовать определенным ограничениям вычислений и памяти независимо от выбранного пути выполнения (который все еще может значительно варьироваться в зависимости от входных данных). Так что же означает использование общего динамического выделения памяти (например, malloc / new) в этом контексте? Это означает, что разработчик в какой-то момент не может определить точное потребление памяти, и было бы невозможно определить, сможет ли получающаяся в результате программа соответствовать требованиям как к памяти, так и к вычислительной мощности.

Да, это правильно. Для типов приложений, которые вы упоминаете, все, что может произойти, должно быть подробно описано. Программа должна обрабатывать наихудший сценарий в соответствии со спецификацией и выделять столько памяти, ни больше, ни меньше. Ситуации, когда «мы не знаем, сколько вкладов мы получаем», не существует. Наихудший сценарий указан с фиксированными номерами.

Ваша программа должна быть детерминированной в том смысле, что она может обрабатывать все до наихудшего сценария.

Сама цель кучи состоит в том, чтобы позволить нескольким несвязанным приложениям совместно использовать оперативную память, например, в ПК, где количество запущенных программ / процессов / потоков не является детерминированным. Этот сценарий не существует в системе реального времени.

Кроме того, куча недетерминирована по своей природе, так как сегменты добавляются или удаляются со временем.

Больше информации здесь: https://electronics.stackexchange.com/a/171581/6102

Даже если ваш распределитель кучи имеет повторяемое поведение (одна и та же последовательность выделения и свободные вызовы дают одинаковую последовательность блоков, следовательно (надеюсь) одно и то же состояние внутренней кучи), состояние кучи может существенно измениться, если последовательность вызовов будет изменена Это может привести к фрагментации, что приведет к непредсказуемым последствиям выделения памяти.

Причиной выделения кучи является прямое запрещение во встроенных системах, особенно Критически важные системы, такие как летательные аппараты, космические корабли или системы жизнеобеспечения, не позволяют проверить все возможные изменения в последовательности вызовов malloc / free, которые могут произойти в ответ на асинхронные по своей природе события.

Решение состоит в том, чтобы у каждого обработчика была выделена отдельная память для его цели, и это больше не имеет значения (по крайней мере, в том, что касается использования памяти), в каком порядке эти обработчики вызываются.

Проблема использования кучи в жестком программном обеспечении реального времени заключается в том, что выделение кучи может привести к сбою. Что у тебя, когда у тебя кончились кучи?

Вы говорите о космических приложениях. У вас довольно жесткие, безотказные требования. У вас не должно быть возможности утечки памяти, поэтому не хватает хотя бы кода безопасного режима для запуска. Вы не должны упасть. Вы не должны бросать исключения, которые не имеют блока catch. Вероятно, у вас нет ОС с защищенной памятью, поэтому одно сбойное приложение теоретически может уничтожить все.

Вы, вероятно, не хотите использовать кучу вообще. Преимущества не перевешивают стоимость всей программы.

Обычно «недетерминированный» означает что-то другое, но в этом случае лучше всего прочитать, что все поведение программы должно быть полностью предсказуемым.