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

Ответ 1

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

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

Кстати, некоторые "в реальном времени" или "встроенные" системы реализуют свой собственный malloc (или какой-то его вариант). Программы на С++ могут иметь allocator -s, используемые по стандарту container s. См. Также this и которые и т.д. И т.д......

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

Ответ 5

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

Ответ 6

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

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

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

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

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

Ответ 7

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

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

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

Ответ 8

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

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

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

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

Ответ 9

Короткий ответ

Есть некоторые эффекты на значения данных или их статистические распределения неопределенности, например, триггерного сцинтиллятора первого или второго уровня, которые могут быть получены из невоспроизводимого количества времени, которое вам, возможно, придется ждать malloc/free.

Худший аспект заключается в том, что они не связаны с физическим явлением ни с аппаратным, а каким-то образом с состоянием памяти (и ее историей).

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

Более длинный ответ

Вы сказали: "Я не смог проверить правильность этого утверждения, когда люди говорят мне об этом".
Я постараюсь дать вам чисто гипотетическую ситуацию/тематическое исследование.

Предположим, вы имеете дело с CCD или с некоторыми сцинтилляторами первого и второго уровней в системе, которые должны экономить ресурсы (вы находитесь в космосе).
Скорость приема будет установлена ​​так, чтобы фон был в x% MAXBINCOUNT.

• Там есть всплеск, у вас есть всплеск в подсчетах и ​​переполнение в счетчике bin.
  Я хочу все: вы переключаетесь на максимальную скорость приема и заканчиваете свой буфер.
  Вы идете освобождать/выделять больше памяти, пока вы заканчиваете дополнительный буфер.
  Что вы будете делать?

  • Вы сохраните встречный риск <переполнения (второй уровень попытается правильно подсчитать тайм-ауты пакетов данных), но в этом случае вы перейдете к недооценить strong > подсчеты за этот период?
  • вы остановите счетчик, введя отверстие в временном ряду?

  Обратите внимание, что:

  • Ожидая выделения, вы потеряете переходный процесс (или, по крайней мере, его начало).
  • Что бы вы ни делали, это зависит от состояния вашей памяти и не воспроизводится.

• Теперь вместо этого сигнал будет переменным вокруг MAXBINCOUNT с максимальной скоростью приема, доступной на вашем оборудовании, и это событие больше обычного.
  Вы закончите пространство и попросите еще... Между тем, вы понесете ту же проблему выше.
  Переполнение и систематические пики подсчитывают недооценку или дыры в временных рядах?

Давайте переместим второй уровень (он также может быть на триггере первого уровня).

С вашего оборудования вы получаете больше данных, чем вы можете запасти или передать.
Вы должны класть данные во времени или пространстве (2x2, 4x4,... 16x16... 256x256... пиксельное масштабирование...).

Неопределенность предыдущей проблемы может повлиять на распределение ошибок.
Есть настройка CCD, для которой у вас есть пиксели границы с подсчетами, близкими к MAXBINCOUNT (это зависит от того, где вы хотите видеть лучше).
Теперь вы можете иметь душ на вашем ПЗС или одном большом месте с одинаковым общим количеством отсчетов, но с другой статистической неопределенностью (часть, введенная временем ожидания)...

Итак, например, когда вы ожидаете профиль Лоренца, вы можете получить его свертку с гауссовой (Voigt), или если вторая она действительно доминирует с грязным гауссовым...

Ответ 10

Внедрить RTOS целостности из GHS:

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

и LynxOS:

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

LynxOS и Integrity RTOS относятся к программному обеспечению, используемому в космических приложениях, ракетах, самолетах и ​​т.д., поскольку многие другие не утверждены или не сертифицированы властями (например, FAA).

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

Для удовлетворения строгих критериев применения космических приложений Integrity RTOS фактически обеспечивает формальную проверку, то есть математически доказанную логику, что их программное обеспечение ведет себя в соответствии со спецификацией.

Среди этих критериев, цитируя здесь:

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

и здесь:

Целостность зеленых холмов Динамическое распределение памяти

:

Я не специалист по формальным методам, но, возможно, одним из требований к этой проверке является устранение неопределенностей в сроках, необходимых для распределения памяти. В RTOS все события точно запланированы в миллисекундах друг от друга. И динамическое распределение памяти всегда имеет проблему с требуемым сроком.

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

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

Ответ 11

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

Объект "Куча" эффективен, когда вы хотите делиться данными между несколькими вызовами функций. Вам просто нужно передать указатель, так как куча доступна по всему миру. Есть и недостатки. Некоторые функции могут освободить эту память, но все же некоторые ссылки могут существовать и в других местах.

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