Динамическая память в системах жёсткого реального времени

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



    (КДПВ – см. аннотацию к диаграмме в конце)


    Неочевидность свойств алгоритмов динамического распределения памяти породила настораживающую тенденцию к лёгкому искажению действительности в документации некоторых ОСРВ, причём не последнего пошиба. Например, раздел об управлении памятью FreeRTOS обходит стороною класс аллокаторов постоянной вычислительной сложности O(1), заставляя неискушённого коллегу принять, что O(n) есть теоретический потолок. Аналогичные артефакты находятся в документации к ChibiOS (1, 2). Мы, разумеется, не станем подозревать разработчиков столь выдающихся продуктов в незнании матчасти; скорее, спишем это на свойственный людям банальный недосмотр. Приложения реального времени редко полагаются на динамическое распределение во время выполнения, так что множество затронутых здесь невелико.


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


    Порядком вычислительной сложности дело не ограничивается. Ресурсный потолок по памяти, очевидно, имеет критическое значение для встраиваемых систем, где количество доступных мегабайт можно пересчитать пальцами одной руки. Поставщики же ОСРВ имеют наклонности к заимствованию оптимизированных на средний случай алгоритмов из продуктов, не рассчитанных на реальное время и встраиваемые приложения. Подтверждающим примером будет реализация аллокатора в NuttX, где используется стратегия поиска наилучшего совпадения (best fit), чья пониженная склонность к фрагментации в общем случае даётся ценою крайне пессимистичного её прогноза для худшего случая. Аналогичные замечания можно сделать в адрес упомянутых ранее конкурентов.


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


    Ваш покорный слуга недаром увяз в этой проблеме. Работая над реализацией встраиваемого сетевого стека для одного протокола реального времени, я обнаружил, что замена используемого на тот момент традиционного блочного менеджера памяти на обычный аллокатор фрагментов произвольного размера не только радикально упрощает API и реализацию, но и улучшает асимптотическую сложность внутренних процедур стека. Последнее обусловлено, среди прочего, заменой фрагментированных буферов из цепочек блоков на непрерывные фрагменты памяти:


    // Список фрагментов на блочном аллокаторе:
    struct FragmentedBuffer
    {
        struct FragmentedBuffer* next;
        uint8_t data[];
    };
    
    // ...превращается в:
    uint8_t* data;

    На второй день углубления в релевантные материалы, черенок моего сознания наткнулся на анализ алгоритмов Buddy Allocator, Half-Fit, и Two-Level Segregated Fit (TLSF). Все они представляют собою детерминированные аллокаторы постоянной вычислительной сложности O(1) (для Buddy Allocator мы делаем допущение, что объём памяти постоянен, в противном случае оценка будет иной). Почтенные господа J. Herter и J. Robson подвергают оба ресурсных вопроса – как времени, так и памяти – детальному рассмотрению в диссертации “Timing-Predictable Memory Allocation In Hard Real-Time Systems” и статье “Worst case fragmentation of first fit and best fit storage allocation strategies”, соответственно.


    Даже малознакомый с теорией динамического распределения памяти читатель найдёт обоснование постоянства вычислительной сложности приведённых алгоритмов тривиальным. Гораздо больший интерес здесь представляет фрагментация. Насколько я могу видеть, многие мои коллеги ошибочно подозревают, что динамические аллокаторы неизбежно приходят в состояние катастрофической фрагментации (где выделение памяти невозможно из-за высокого дробления свободных участков) за конечное время. Подробный разбор вопроса с доказательством обратного можно найти на страницах 26–33 диссертации многоуважаемого Хертера, здесь же я лишь оставлю финальный вывод, что предел размера кучи H, при котором катастрофическая фрагментация недостижима, для лучших из приведённых алгоритмов определён как:


    $H = 2 M (1 + \lceil{}\log_2 n\rceil{})$


    Где M – пиковая потребность приложения в динамической памяти, n – размер наибольшей аллокации.


    Здесь уместно вернуться к началу и бросить ещё камней в огород поставщиков ОСРВ. Как я упомянул, в некоторых продуктах встречаются реализации алгоритмов управления памятью, чья стратегия размещения предусматривает выбор свободного фрагмента минимально возможного размера. Эта стратегия хорошо показывает себя в среднем случае, но в особых условиях деградирует до теоретического предела H = M (n — 2), уничтожая надежду на её уместность во встраиваемых системах.


    Для меня было очевидным, что множество задач реального времени, где разумное применение хорошо охарактеризованных (предсказуемых) алгоритмов выделения памяти является оправданным, не исчерпывается моим стеком. Контраст между этим осознанием и недостаточным вниманием сообщества разработчиков встраиваемых систем к детерминированным аллокаторам, усугублённый также сомнительными дискуссиями на StackOverflow, побудил меня спасать дело самостоятельно, и я сделал свой собственный аллокатор. Он чрезвычайно компактен (500 строк на C99/C11), его процедуры выделения и освобождения памяти имеют постоянную вычислительную сложность, и предельный уровень фрагментации хорошо охарактеризован.


    Вот он: https://github.com/pavel-kirienko/o1heap.


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


    • Левая диаграмма: размер кучи H [KiB] от пиковой потребности приложения в памяти M [KiB] и наибольшей аллокации n [KiB] при минимальном размере аллокации 16 байт.
    • Правая диаграмма: аналогично, но единицы измерения MiB.

    Если величины H кажутся чрезмерными, это неспроста, ведь понятия верхнего предела и худшего случая не эквивалентны. Задача поиска огибающей худшего случая включает в себя минимизацию разрыва между теоретическим пределом и практически достижимым наихудшим состоянием. В нашем случае это конкретизируется в минимизацию разрыва между значением H, предсказанным нашей моделью, и реальным пиковым случаем фрагментации, который система может встретить на практике. Я надеялся подобраться к проблеме уменьшения H при сохранении гарантированных свойств алгоритма при помощи симуляций с систематическим перебором возможных состояний, но был вынужден отложить эту затею по причине отсутствия времени. Однако, вовлечённый в тему человек понимает высокую практическую значимость этой доработки. Если среди читателей найдутся достаточно мотивированные коллеги (Embox?), я бы с готовностью ввязался в коллаборацию по этому вопросу.


    Другой важный вопрос заключается в исправлении текущего положения дел в открытых системах. Я вяло потыкал метафорической палочкой одного из разработчиков NuttX по этому поводу, и почерпнул, что вопрос имеет низкий приоритет: "I considered porting TLSF at one point, but overall it's low on my list of NuttX improvements I'd explore if I actually had time". Есть куда стремиться.

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 51

      0

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

        +5
        Я не думаю, что существует универсальный оптимальный выбор. Мне, например, приходится иметь дело с транспортной бортовой электроникой, где требования к предсказуемости поведений и реальному времени высоки. Подходы, которые оправдывают себя в этих случаях, вряд ли будут востребованы, например, в классическом IoT, где допустимая вероятность отказа обычно на порядки выше. Попытка применения отказоустойчивых методик может привести к увеличению стоимости как самого железа, так и разработки ПО, что может сделать продукт коммерчески нежизнеспособным.
          +2

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

            –5

            простите новичка… что такое "девопс"?

              +2

              Простите, а что вам мешает погуглить?

              0
              Надеюсь, вы же не думаете, что разработчики компиляторов и базовых библиотек для «ширпотребного» софта лениво поплёвывают в потолок?
              Уже даже вон команда PHP занялась вопросом аллокаторов и сразу получила двукратный бонус производительности. А потом, после полировки внутренних структур, постепенно ещё почти такой же.
                0

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

          +8

          Все чаще и чаще подобного рода статьи обделены вниманием со стороны аудитории хабра. Плюсов меньше, нежели у соседних "новостей". Как результат — еще меньше шансов на просмотр.
          При этом когда ставишь минус соседям — есть выбор между вариантами причин. Низкий технический уровень материала, как по мне, один из самых востребованных. Есть ли резон добавить подобный опрос при плюсовании? Я бы нажал "Действительно полезно" или "The piece of habracake".

            +1
            Очень нишевая статья, все-таки, поэтому и меньше.
              +1

              На хабре то?

                0

                А почему нет?
                Ведь по сути людей занимающихся системами реального времени не так много, ещё часть может заинтересоваться "для общего развития" да и то после первого абзаца может передумать. Ведь это нормально для текущего момента истории, программирование выходит в массы, основная занятость в решении повседневных задач, "популярное на слуху" это bigdata, контейнеры js это всё очень далеко от систем реального времени.

            +3

            А какие недостатки данного подхода? Почему все менажеры динамической памяти не использует этот алгоритм?


            И вообще, главный недостаток статьи, это то, что не объяснено как все это работает. Конечно, код (при этом небольшой!) это прекрасно, но объяснение как это работает и почему сделано так, а не по другому многим понравится и повысит читаемость статьи.

              +3

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


              Рассматриваемые методы не новы и описаны в диссертации по ссылке и других гуглимых ресурсах. В моей библиотеке реализован алгоритм Half-Fit — один из трёх основных, наряду с более простым buddy allocator и более сложным TLSF. Детальное описание есть на странице 27-28, плюс комментарии к моей реализации есть прямо в README моей библиотеки. Buddy allocator я исключил из-за его более высокой (но детерминированной!) вычислительной сложности в сравнении с half-fit (который был предложен позже и более совершенен), TLSF же имеет более тяжёлый худший случай фрагментации за исключением одного вырожденного случая, где его поведение эквивалентно half-fit. Я мог бы набросать аналогичную заметку по этой теме, но зачем повторяться, ведь в источниках по ссылкам вопрос рассмотрен достаточно детально.


              Обычные, классические приложения (не (жёсткого) реального времени) не используют рассмотренные подходы потому что их средний случай сильно уступает среднему случаю популярных сегодня алгоритмов (например, dlmalloc). C худшим случаем всё наоборот! Как я отметил в тексте, анализ систем реального времени рассматривает прежде всего именно худший случай, в отличие от обычных приложений.


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

                –9
                Присоединяюсь к johnfound. Статья написана плохо, не структурирована, в ней нет введения, разъяснения основного вопроса, терминов, ошибочных постулатов и раскрытия темы.

                Вот я хз, что такое «традиционный» и что такое «блочный» аллокатор, что понимается под «катастрофической фрагментацией», хотя и знаком с основами и проблемами. А что скажет «традиционный» читатель хабра?
                  +16
                  Как традиционный читатель, говорю: это интересная техническая заметка, которая несёт гораздо больше пользы, чем бОльшая часть публикаций за день вместе взятых.
                  А тот факт, что Вам не разжевали и в рот не положили объясняется просто: это НЕ учебная статья, а заметка от профессионала для профессионалов.
                    +1
                    которая несёт гораздо больше пользы, чем бОльшая часть публикаций за день вместе взятых.

                    С этим нельзя не согласится. Поэтому я и плюсанул и статью и карму автора.


                    А тот факт, что Вам не разжевали и в рот не положили объясняется просто: это НЕ учебная статья, а заметка от профессионала для профессионалов.

                    А с этим согласится уже нельзя. Для заметки есть твитер и редит. На Хабре пишут именно статьи где объясняют. Такую статью тоже можно написать "для профессионалов". А можно написать и для школьников. Это как раз зависит от автора.

                      +4

                      Написать статью для школьников, при прочих равных, потребует в разы больше времени. Почему вы требуете от автора траты этого времени, ничего не предлагая взамен — непонятно.
                      Тут ведь всё добровольно.

                        –1

                        Ну-у-у, мне вообще-то нужна статья «для профессионалов», а не «для школьников». А автор, получает взамен популярность своей библиотеки. Все справедливо.

                  +3
                  Рассматриваемые методы не новы и описаны в диссертации по ссылке и других гуглимых ресурсах.

                  Диссертация это содержит 183 страниц текста на академическом английском. И вы предлагаете нам прочитать ее, чтобы понять как работает 500 строк кода на C.


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


                  потому что их средний случай сильно уступает среднему случаю популярных сегодня алгоритмов (например, dlmalloc)

                  А насколько сильно? Хотя бы приблизительно на глаз? Делались ли некие тесты и измерения?

                    0
                    Диссертация это содержит 183 страниц текста на академическом английском. И вы предлагаете нам прочитать ее, чтобы понять как работает 500 строк кода на C.

                    Я предлагаю вам прочитать только две; как я написал выше, "детальное описание есть на странице 27-28".


                    А насколько сильно? Хотя бы приблизительно на глаз? Делались ли некие тесты и измерения?

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

                0
                Автор несколько сферически описал проблему, поскольку когда речь идет о выборе аллокаторов для какой-то подсистемы, в первую очередь озадачиваются предельными параметрами (минимальный, максимальный размер и пр.) и обкладывают все это пограничными условиями, т.к., конечный результат может весьма сильно зависеть от них.
                Доводилось даже встречать системы РВ, в которых пользовательский интерпретатор и сетевой стек «кормятся» из одной кучи (хотя аллокатор был нетривиальный).
                  –1
                  Действительно, интересно бы было посмотреть на сравнение на каких-то бенчмарках с другими аллокаторами. И еще интересно, а влияют ли некоторые детали реализации RTOS на эффективность применения? Кажется, что должны. Я вижу issue про эксперимент с NuttX, но возможно, было бы интересно посмотреть на применение и в других системах для сравнения. Интересно еще посмотреть бы было на влияние архитектуры процессора, потому что особенно у некоторых процессоров для RTOS должны быть свои особенности, которые позволили бы оптимизировать некоторые аспекты работы с памятью.
                  А в целом, спасибо, интересно, еще раз хорошо показывает, что нет «серебряной пули» и что нужно правильно выбирать аллокатор и настраивать его под конкретную специфику даже если говорить про обычные приложения, у того же популярного jemalloc, очень много опций при сборке, которые стоит подкрутить, чтобы получить результаты получше.
                    0

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


                    влияют ли некоторые детали реализации RTOS на эффективность применения?
                    у некоторых процессоров для RTOS должны быть свои особенности, которые позволили бы оптимизировать некоторые аспекты работы с памятью.

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

                      +2
                      Не могли бы вы раскрыть тему подробнее, пожалуйста? О каких особенностях тут идёт речь?


                      Это старая как мир притча. Несколько десятилетий назад отдельные группы исследователей продвигали идею закладывания в архитектуру отдельных RTOS идей. От MMU до конвейеров и логики работы кэшей. Поддержки у вендоров хитрый план по ускоспециализированному железу не нашел и достаточно быстро сдулся. Но эхо в академической среде все еще витает.
                        –1
                        Я не специалист в RTOS, но на прошлом месте работы, например, приходилось иметь дело с микропроцессором, у которого был выделенный небольшой подтип памяти ( www.synopsys.com/dw/ipdir.php?ds=arc-dsp-options ). И на данные микропроцессоры ставили RTOS.
                        Или, например, даже в аллокаторах общего назначения, пытаются использовать некоторые сведения из спецификации процессоров и реализации ОС, чтобы улучшить производительность, например, читают напрямую из регистра идентификатор потока github.com/microsoft/mimalloc/blob/6a744a8549263696ef8d620006a0de2249e59b46/include/mimalloc-internal.h#L618
                        Просто, мне казалось, что в RTOS сфере вообще должны активно использовать различные уловки, чтобы выжать максимум из производительности.
                          +5
                          Просто, мне казалось, что в RTOS сфере вообще должны активно использовать различные уловки, чтобы выжать максимум из производительности.


                          RT к производительности никакого отношения не имеет. Real-time не значит быстро, но с гарантией своевременности. Тут можно с некоторым допущением противопоставить интерактивность и предсказуемость. Первое к ОС общего назначения, второе к ОСРВ.
                      0
                      Тема весьма интересная, но хочется увидеть практические результаты использования.
                        0
                        Спасибо за статью!

                        Мотивированные коллеги есть. :)

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

                        Поясню, казалось бы ОСРВ должно именно об худшем случае выделения ресурсов и заботится. однако в современной системе решение данной проблемы похоже для всех случаев не возможно. Поэтому и появляются описываемые Вами трюки как в lwIP. Мы пришли к похожему подходу, то есть какая то подсистема требует выделения специфической памяти, предположим тот же IP стек. Но тогда ведь можно выделить пул на максимальное количество объектов максимального размера и выделять за гарантированное время, не взирая на накладные расходы которых требует отдельный аллокатор.

                        Но повторюсь, тема очень интересная и близкая нам! Я бы предложил поставить issue. Как минимум попробуем студентов подключить, чтобы дополнительно свойства исследовать на тех или иных задачах.
                          +1
                          Но тогда ведь можно выделить пул на максимальное количество объектов максимального размера и выделять за гарантированное время, не взирая на накладные расходы которых требует отдельный аллокатор.

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


                          Но повторюсь, тема очень интересная и близкая нам! Я бы предложил поставить issue. Как минимум попробуем студентов подключить, чтобы дополнительно свойства исследовать на тех или иных задачах.

                          С нетерпением буду ждать ваших студентов.

                            +1
                            > то подход с блочной аллокацией как вы его описали окажется менее эффективным по памяти, чем выделение фрагментов произвольного размера.

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

                            > С нетерпением буду ждать ваших студентов.
                            ну студенты не мои (и не наши). Их тоже сначала нужно заинтерисовать. :)
                          0
                          Извините, что не по теме, но хотел бы спросить — скажите, а когда примерно ждать реализации libcanard для протокола версии 1.0? У нас тут проект в подвешенном состоянии, а на C++ не хотелось бы переходить.
                            +2

                            (Поясню для остальных: речь идёт о библиотеке Libcanard, которая реализует сетевой протокол для систем реального времени UAVCAN v1.0)


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

                              0

                              (спустя месяц) готово: https://github.com/UAVCAN/libcanard/pull/142

                              –3

                              Не являюсь сторонником динамического выделения памяти в системах жёсткого реального времени. Вообще.


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

                                0
                                Не являюсь сторонником динамического выделения памяти в системах жёсткого реального времени. Вообще.

                                Динамическое выделение и предсказуемость временных характеристик не связаны, как я показал в статье. Чем обсусловлена ваша позиция?


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

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


                                Если конкретные временные и поведенческие характеристики приложения хорошо известны, то, конечно, можно насрезать углов и свести реализацию к работе со статически предвыделенными буферами и т.п. Выбор оптимального подхода определяется главным образом требованиями к валидации и верификации ПО и доступными ресурсами на разработку.

                                  –2
                                  Динамическое выделение и предсказуемость временных характеристик не связаны, как я показал в статье. Чем обсусловлена ваша позиция?

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


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

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

                                    0
                                    но если malloc вернет null и этим скажет "Все чувак, сегодня на Луну не летим чайник не включится", то это не жесткое реальное время, а черт знает что.

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

                                      +2
                                      Вообще, я согласен с вашим мнением. О работе Робсона я узнал из документации SQLite. Но, честно говоря, с трудом представляю именно вычисление максимального размера потребляемой памяти. Для того же SQLite эта величина зависит от вида запросов, от полей в таблицах, а они могут поменяться, если, например, база нам подкладывается извне, скажем, при обновлении. Ну, и на практике всё упирается в то, что необходимо запускать приложение и по статистике смотреть потребляемую память, а потом ещё и доказывать, что в этом примере было именно максимальное потребление.
                                      Может, вы сможете развеять мои сомнения?
                                        +1

                                        Я не развею ваши сомнения. Точное прогнозирование выполняется в одних случаях легко, в других нет; ваш пример из второго. Если развивать пример дальше, то предсказание временных/ресурсных характеристик системы с SQLite потребует анализа не только движка БД, но и логики, что работает поверх и формирует запросы.

                                          +1
                                          Ну, подтверждение — это тоже хорошо.
                                          А вы не собираетесь подробнее написать о том, почему и как в вашем случае удалось вычислить максимальное потребление, и как это всё позволило упростит API и реализацию, о чём вы пишете в статье? Я бы с удовольствием почитал, интересная для меня тема.
                                            +1

                                            Посмотрим. Я ещё работаю над этим стеком; если к окончанию наберётся критическая масса интересных соображений, постараюсь поделиться.

                                        –1
                                        Вы можете статически доказать, что чайник всегда включится, если известна потребность приложения в памяти.

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


                                        Что вы сэкономите, выделяя меньшее количество памяти, чем нужно в худшем случае для корректной работы приложения?

                                          +1
                                          Так если потребность в памяти известна, зачем динамически ее выделять?
                                          Что вы сэкономите, выделяя меньшее количество памяти, чем нужно в худшем случае для корректной работы приложения?

                                          Вы сэкономите память и затраты когнитивных ресурсов на реализацию логики вашего приложения. Динамическое выделение позволяет удовлетворить потребность приложения в памяти при меньшем её общем размере благодаря разнесению перекрывающихся в адресном пространстве аллокаций во времени. Упрощение логики же достигается обобщением задач управления памятью в аллокаторе. Об этом пишет и Хертер:


                                          While often yielding better structured source code, another, more important advantage of dynamic memory allocation is to alleviate the programmer from finding ways to cope with a small amount of memory. I.e., alleviating him or her from assigning memory addresses such that objects not allocated contemporaneously can share memory locations to reduce overall memory consumption.

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


                                          Однако, от моего внимания, разумеется, не ускользает то факт, что снижение ресурсоёмкости и упрощение логики, которое даёт динамическое размещение, даётся ценою более сложной модели поведения программы. Я согласен с вашей подразумеваемой позицией, что динамическое размещение не является серебряной пулей, что его цена высока, и во многих случаях не является оправданной. В следующей цитате из поста ключевым словом является "разумное":


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

                                            Подождите. Выделение памяти под определенную реалтаймовую задачу до того, как она начала исполняться и возврат памяти обратно при ее завершении — это одно и в принципе это не мешает следовать принципам жесткого реального времени. Вы можете вполне в одном МК иметь задачи "взлет" и "посадка", которые никогда не исполняются одновременно, и динамически выделять под них память перед первым запуском одной из этих задач. И для этого не нужен специальный реалтаймовый аллокатор.


                                            Но это совсем не то же самое, что выделять память динамически, во время работы реалтаймовой задачи. Вот эту проблему я обсуждаю и надеюсь, вы меня понимаете. Здесь нет разнесения во времени — все внешние сигналы могут вдруг объявиться одновременно и на них придется ответить в течении гарантированного времени. При этом и возникает вопрос — что мы экономим, динамически выделяя память на данном этапе работы приложения, когда каждый программный цикл на счету?
                                            Ресурсы логики приложения? Да нет. Приложению по сути пофиг куда указывает поинтер на переменную — в статически размеченную область или динамически. Главное, чтобы это было место именно под эту переменную.
                                            Экономия памяти? Опять же как, если мы знаем, что нам может понадобиться Х килобайт в худшем случае? Будем рассчитывать, что этот случай не наступит?

                                              +2

                                              Мне кажется, что вы излишне углубляетесь в конкретику моего примера. Можно сконструировать другой пример, где вместо памяти под нужды системы управления межпланетным чайником мы будем выделять буферы под сообщения, что он принимает из ЦУП. Чайнику неизвестно, какие придут сообщения, в какой момент, и как они будут упорядочены во времени. В конечном итоге, потребный ресурс памяти будет ограничен сверху пропускной способностью линии связи и способностью чайника к обработке сообщений по мере их поступления. Если вас интересуют более конкретные примеры, посмотрите, например, на организацию работы с памятью в lwIP. Конечно, к системам жёсткого реального времени его можно отнести с натяжкой, но родственные сетевые технологии используются, например, в аэронавтике (AFDX, ARINC 664) и другом транспорте (SOME/IP, DDS/RTPS). Если пойти дальше, федеральное агентство аэронавтики США вполне всерьёз обсуждает тонкости реализаций буферизации и управления памятью в публикации Safety and Certification Approaches for Ethernet-Based Databuses. Вообще, современные и зарождающиеся сетевые протоколы на транспорте отличаются от предшественников существенно более высокой сложностью и предлагаемыми абстракциями, которые часто требуют более сложных подходов к реализации. Я не хотел бы сейчас погружаться в тонкости сетевых протоколов реального времени для отказоустойчивых систем, потому что тема крайне обширная и выведет нас далеко за рамки текущего вопроса.


                                              Ресурсы логики приложения?

                                              В моём сообщении выше речь шла о мыслительных ресурсах программиста, простите, если выразился неясно. Именно об их экономии рассуждает и Хертер. Они ценны не только с точки зрения человекочасов, затраченных на проектирование и реализацию ПО, но и с позиции вероятности появления непредусмотренных поведений в программе. Вы не хуже меня знаете, что человеческий мозг слаб, и наши возможности по удержанию в голове сложных абстракций ограничены.

                                                –1
                                                Можно сконструировать другой пример, где вместо памяти под нужды системы управления межпланетным чайником мы будем выделять буферы под сообщения, что он принимает из ЦУП. Чайнику неизвестно, какие придут сообщения, в какой момент, и как они будут упорядочены во времени. В конечном итоге, потребный ресурс памяти будет ограничен сверху пропускной способностью линии связи и способностью чайника к обработке сообщений по мере их поступления.


                                                Не забываем что есть лимит времени на обработку. Т.е. есть макс количество сообщений которое способен обработать чайник оставаясь системой реального времени. Если приход сообщений превышает их обработку/количество сообщений в очереди превысило какой то на перед заданный предел, то все уже поломалось, независимо от возможности расширить буфер, поелику это уже не система реального времени.
                                                  –2
                                                  так чайник как РТ и не обязан обрабатывать все сообщения. вполне имеет право ответить: — «вы кто такие, подождите»

                                                  но собственно, статья не отвечает и на более простые вопросы
                                                    0
                                                    так чайник как РТ и не обязан обрабатывать все сообщения. вполне имеет право ответить: — «вы кто такие, подождите»
                                                    Ну это уже в зависимости от зависимости кто там че — ЦУП будет кипятильник юзать пока он раздуплится или чайник окирпичится от того что он нереалтаймовым стал — не суть важно. Главное что ни в том ни в другом случае в динамическом буфере смысла нет. Обычный кольцевой и все ОК.
                                                    но собственно, статья не отвечает и на более простые вопросы

                                                    И самое главное на вопрос — а какой смысл вообще динамического перераспределения буферов в реалтаймовой софтине?
                                                +1
                                                При этом и возникает вопрос — что мы экономим, динамически выделяя память на данном этапе работы приложения, когда каждый программный цикл на счету?
                                                Запас вычислительной мощности это вопрос отдела оборудования. При этом накладные расходы на распределения памяти слишеом незначительны и происходит оно в любом случае редко чтобы могло на что то особо повлиять. Тут есть другой гораздо более важный аспект. А именно — гарантировать наличие нужной памяти можно только имея ее предварительно распределенной. Т.е. если оно все одновременно произойдет то просто вылетет bad_alloc и все упадет — динамически то распределяют только для того чтобы впихнуть невпихуемое — т.е. поюзать память по очереди если ее не хватает на все сразу. И собственно вот с этим бороться окромя четкого разделения по времени способов нет.
                                                  –1
                                                  Можно сконструировать другой пример, где вместо памяти под нужды системы управления межпланетным чайником мы будем выделять буферы под сообщения, что он принимает из ЦУП. Чайнику неизвестно, какие придут сообщения, в какой момент, и как они будут упорядочены во времени. В конечном итоге, потребный ресурс памяти будет ограничен сверху пропускной способностью линии связи и способностью чайника к обработке сообщений по мере их поступления.

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

                                    (ошибся веткой)

                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                    Самое читаемое