Вы ничего не поняли. Простите за прямоту, я хочу сэкономить нам обоим время. Прочитайте учебники, что я предложил, подтяните матчасть, потом возвращайтесь. Ничего личного.
Я пока не увидел новых идей в вашей публикации. Если я что-то упустил или не так понял, пожалуйста, поправьте меня.
Согласно моему пониманию, вы описываете дисциплину организации очереди (мультиплексирования) с регулировкой скорости (rate-controlled service discipline). Конкретно в вашем случае, как это обычно бывает с RCS, вы описываете несохраняющую работу дисциплину (non-work-conserving service discipline, NWC). RCS в целом широко применяются в сетях реального времени с гарантированными характеристиками. Несохраняющие работу дисциплины могут быть неприемлемы в коммерческих сетях потому они, по своему определению, допускают простой (бездействие) канала, что снижает его среднюю загрузку, от чего страдает рентабельность оборудования и средний уровень обслуживания. Смысл их использования сводится к более равномерной резидентности пакетов по маршруту и упрощению анализа сети, что представляет высокую ценность лишь в реальном времени. Средний случай несохраняющей работу дисциплины обслуживания хуже, чем у сохраняющей, но с худшим случаем это отношение может быть обратным. Обратите внимание, что подобная инверсия отношения среднего и худшего случая наблюдается и в других областях; например, в аллокаторах памяти.
Я подозреваю, что вы можете возразить здесь, сказав, что ваше решение предлагает символьное планирование, а не пакетное, но это не имеет значения. Теория сетевого анализа применима независимо от определения единицы данных: это может быть пакет, символ, или отдельный бит. В силу простоты моделирования обычно применяется последнее, с последующей корректировкой модели для адаптации к пакетной коммутации (битовые потоки не коммутируются).
Конкретно для описанного вами случая обратите внимание на статью Rate-Controlled Service Disciplines (Zhang, Ferrari, 1994), где приводится анализ практически вашего случая, но с адекватным теоретическим аппаратом. Если у вас нет понимания сетевого анализа, рекомендую начать с вводного курса Network Calculus: A Comprehensive Guide (Bemten, Kellerer, 2016), иначе с наскоку утонете. Если интересует реальное время, ознакомьтесь с учебником Safety and Certification Approaches for Ethernet-Based Aviation Databuses (я его уже указал в источниках к этой статье). Также обратите внимание на десятки других методов планирования трафика под разные задачи, помимо класса RCS: D-EDD, VC, WFQ, EDF, и т.п., каждый из которых имеет свои преимущества и недостатки в конкретных приложениях.
На чём основано и что означает утверждение о "гарантированной надёжности" я не понял.
Что касается маршрутизации: вы писали о маршрутизации от источника, но это, в принципе, вещь широко известная и практикуемая. Я вот здесь даже писал о SpaceWire, как пример.
Если вы планируете и дальше заниматься этим вопросом, вам следует ознакомиться с современной теорией, иначе есть риск открыть Америку.
Да, через директиву @union. См. примеры и определение в спецификации. Ещё можете заглянуть в руководство, там это упоминается, в т.ч. в контексте проектирования типобезопасных интерфейсов.
Не покладая клавиатуры над поддержкой v1 в PX4 трудится товарищ Daniel Agar; вы можете наблюдать за прогрессом тут: https://github.com/PX4/Firmware/pull/14865. Параллельно идёт работа над DS-015 (чем со следующей недели я начну заниматься лично) и сериализацией (вместо ревью ценного пулреквеста я засел вот писать статью, сами видите). Всё это необходимо для интеграции в PX4.
документация неконсистентна
Где именно?
И да, у нас есть практически готовый актуатор с поддержкой CAN FD, к которому мы хотели бы прикрутить поддержку UAVCAN v1, если с Вашей стороны есть интерес в этом направлении, то было бы очень здорово.
Перед массивами переменной длины всегда есть длина. Я не знаю, о каком примере вы говорите, но, судя по вашему описанию, он корректен. Репрезентация массивов переменной длины описана спецификацией в разделе 3.7.4.2 Variable-length array types; там объясняется, как кодируется этот префикс.
Длина была бы не нужна только если бы определение было не uint8[<=50] name, а uint8[50] name.
Ваш комментарий относится скорее не к технологии, а к экосистеме вокруг неё. Экосистема не вырастет за ночь или даже за год; это крайне длительный процесс, и не следует ожидать консистентной поддержки вендорами технологии, альфа-релиз которой состоялся лишь шесть месяцев назад. По части конкретно дронов (я так понял, вы из этого сектора) у нас немного сошёл с рельсов процесс в марте этого года, когда выяснилось, что поддержка v1 не успевает в merge window следующего релиза PX4, что косвенно снизило приоритет внедрения и в других проектах из той же отрасли. Происходит это из-за хронической нехватки ресурсов, что вы (ваша компания) можете самым непосредственным образом помочь исправить, если вы видите потенциал во внедрении UAVCAN в ваши продукты. Если вы готовы рассмотреть прямое участие, напишите, пожалуйста, мне в личку — вопросы планирования ресурсов проекта мы не можем обсуждать публично.
Переход от экспериментальной версии v0 к стабильному релизу v1, безусловно, сказался очень тяжело на экосистеме, но это было ожидаемо, и если бы этого можно было избежать, мы бы поступили иначе. Не один тред на форуме посвящён ответам на разные формы вопроса "зачем ломать что работает", так что я тут не буду повторяться. Скажу лишь, что v0 всегда был тестовой площадкой; несколько лет назад я имел смелость сказать, что "v1 вот-вот уже выйдет", но кроличья нора оказалась существенно глубже. Опасения о внезапном выходе v2 со всеми вытекающими для вас как вендора необоснованны, потому что само предположение о том, что v0 является стабильным релизом некорректно (иначе мы назвали бы его v1). Мы заинтересованы в успехе технологии и экосистемы, и мы не собираемся стрелять себе (и вам) в ногу, ломая совместимость с тем, что мы строили шесть лет.
Ваши слова об отсутствии чёткого описания объективно не соответствуют действительности. Возможно, вы имели в виду, что не хватает удобоваримой документации, что было бы правдой, ведь спецификация написана максимально нудным языком (как это обычно бывает со спецификациями). Мы пытаемся это исправить в официальном руководстве, и нам очень нужна конструктивная критика от интеграторов вроде вас.
Насчёт Yukon — его действительно нет, никогда не было, наличие никогда не заявлялось, и причины всё те же. Пока его заменяют инструменты командной строки. Они не фонтан, конечно, но с задачей справляются пока мы работаем над нормальным инструментом.
Мне кажется, что вы излишне углубляетесь в конкретику моего примера. Можно сконструировать другой пример, где вместо памяти под нужды системы управления межпланетным чайником мы будем выделять буферы под сообщения, что он принимает из ЦУП. Чайнику неизвестно, какие придут сообщения, в какой момент, и как они будут упорядочены во времени. В конечном итоге, потребный ресурс памяти будет ограничен сверху пропускной способностью линии связи и способностью чайника к обработке сообщений по мере их поступления. Если вас интересуют более конкретные примеры, посмотрите, например, на организацию работы с памятью в lwIP. Конечно, к системам жёсткого реального времени его можно отнести с натяжкой, но родственные сетевые технологии используются, например, в аэронавтике (AFDX, ARINC 664) и другом транспорте (SOME/IP, DDS/RTPS). Если пойти дальше, федеральное агентство аэронавтики США вполне всерьёз обсуждает тонкости реализаций буферизации и управления памятью в публикации Safety and Certification Approaches for Ethernet-Based Databuses. Вообще, современные и зарождающиеся сетевые протоколы на транспорте отличаются от предшественников существенно более высокой сложностью и предлагаемыми абстракциями, которые часто требуют более сложных подходов к реализации. Я не хотел бы сейчас погружаться в тонкости сетевых протоколов реального времени для отказоустойчивых систем, потому что тема крайне обширная и выведет нас далеко за рамки текущего вопроса.
Ресурсы логики приложения?
В моём сообщении выше речь шла о мыслительных ресурсах программиста, простите, если выразился неясно. Именно об их экономии рассуждает и Хертер. Они ценны не только с точки зрения человекочасов, затраченных на проектирование и реализацию ПО, но и с позиции вероятности появления непредусмотренных поведений в программе. Вы не хуже меня знаете, что человеческий мозг слаб, и наши возможности по удержанию в голове сложных абстракций ограничены.
Так если потребность в памяти известна, зачем динамически ее выделять?
Что вы сэкономите, выделяя меньшее количество памяти, чем нужно в худшем случае для корректной работы приложения?
Вы сэкономите память и затраты когнитивных ресурсов на реализацию логики вашего приложения. Динамическое выделение позволяет удовлетворить потребность приложения в памяти при меньшем её общем размере благодаря разнесению перекрывающихся в адресном пространстве аллокаций во времени. Упрощение логики же достигается обобщением задач управления памятью в аллокаторе. Об этом пишет и Хертер:
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 кб под нужды системы управления во время полёта на Луну, и ещё столько же во время движения по её поверхности, вы можете сэкономить половину, зная, что эти режимы взаимоисключающи и не могут быть активны единовременно. Вместо того, чтобы делать оверлеи на буфере вручную, вы просто делегируете это дело аллокатору.
Однако, от моего внимания, разумеется, не ускользает то факт, что снижение ресурсоёмкости и упрощение логики, которое даёт динамическое размещение, даётся ценою более сложной модели поведения программы. Я согласен с вашей подразумеваемой позицией, что динамическое размещение не является серебряной пулей, что его цена высока, и во многих случаях не является оправданной. В следующей цитате из поста ключевым словом является "разумное":
Для меня было очевидным, что множество задач реального времени, где разумное применение хорошо охарактеризованных (предсказуемых) алгоритмов выделения памяти является оправданным, не исчерпывается моим стеком.
Я не развею ваши сомнения. Точное прогнозирование выполняется в одних случаях легко, в других нет; ваш пример из второго. Если развивать пример дальше, то предсказание временных/ресурсных характеристик системы с SQLite потребует анализа не только движка БД, но и логики, что работает поверх и формирует запросы.
но если malloc вернет null и этим скажет "Все чувак, сегодня на Луну не летим чайник не включится", то это не жесткое реальное время, а черт знает что.
Для исключения этого существует модель худшего случая фрагментации. Вы можете статически доказать, что чайник всегда включится, если известна потребность приложения в памяти. Можно провести аналогии с определением размера стека, если угодно.
Не являюсь сторонником динамического выделения памяти в системах жёсткого реального времени. Вообще.
Динамическое выделение и предсказуемость временных характеристик не связаны, как я показал в статье. Чем обсусловлена ваша позиция?
что же это за протокол такой, для которого не получилось сделать сетевой стек без динамического выделения памяти?
Если выйти за рамки тривиальных сигнальных протоколов, то отказ от динамической памяти не позволит сделать реализацию для общего случая, не делающую предположений о функциях и поведении приложения. Я работаю как раз над такой общей реализацией.
Если конкретные временные и поведенческие характеристики приложения хорошо известны, то, конечно, можно насрезать углов и свести реализацию к работе со статически предвыделенными буферами и т.п. Выбор оптимального подхода определяется главным образом требованиями к валидации и верификации ПО и доступными ресурсами на разработку.
Но тогда ведь можно выделить пул на максимальное количество объектов максимального размера и выделять за гарантированное время, не взирая на накладные расходы которых требует отдельный аллокатор.
Тут проблема в том, что если максимальный размер достаточно велик (это часто так в моих задачах, например), то подход с блочной аллокацией как вы его описали окажется менее эффективным по памяти, чем выделение фрагментов произвольного размера. И то, и другое можно делать за гарантированное время.
Но повторюсь, тема очень интересная и близкая нам! Я бы предложил поставить issue. Как минимум попробуем студентов подключить, чтобы дополнительно свойства исследовать на тех или иных задачах.
Обратите внимание, что если вы работаете над системой реального времени, средний случай вас обычно не интересует. Практические замеры позволяют оценить именно его (исключая, возможно, какие-то очень особые подходы, специально предназначенные для поиска граничных случаев, не берусь обобщать). Для обычных (не реального времени) систем, конечно, сравнить было бы интересно. Я не готов браться за это самостоятельно, но мог бы посодействовать, если найдутся желающие.
влияют ли некоторые детали реализации RTOS на эффективность применения?
у некоторых процессоров для RTOS должны быть свои особенности, которые позволили бы оптимизировать некоторые аспекты работы с памятью.
Не могли бы вы раскрыть тему подробнее, пожалуйста? О каких особенностях тут идёт речь?
Диссертация это содержит 183 страниц текста на академическом английском. И вы предлагаете нам прочитать ее, чтобы понять как работает 500 строк кода на C.
Я предлагаю вам прочитать только две; как я написал выше, "детальное описание есть на странице 27-28".
А насколько сильно? Хотя бы приблизительно на глаз? Делались ли некие тесты и измерения?
Я не делал практических замеров, потому что меня интересует доказуемый худший случай. Однако, я согласен с вами, что в целом это вопрос интересный.
Вы правы, я немного перешагнул через практическую сторону. Это отчасти умышленно, ведь смысл публикации не в предложении новых технических методов, а в информировании коллег о том, что популярные представления о методах работы с памятью в системах реального времени зачастую ошибочны.
Рассматриваемые методы не новы и описаны в диссертации по ссылке и других гуглимых ресурсах. В моей библиотеке реализован алгоритм Half-Fit — один из трёх основных, наряду с более простым buddy allocator и более сложным TLSF. Детальное описание есть на странице 27-28, плюс комментарии к моей реализации есть прямо в README моей библиотеки. Buddy allocator я исключил из-за его более высокой (но детерминированной!) вычислительной сложности в сравнении с half-fit (который был предложен позже и более совершенен), TLSF же имеет более тяжёлый худший случай фрагментации за исключением одного вырожденного случая, где его поведение эквивалентно half-fit. Я мог бы набросать аналогичную заметку по этой теме, но зачем повторяться, ведь в источниках по ссылкам вопрос рассмотрен достаточно детально.
Обычные, классические приложения (не (жёсткого) реального времени) не используют рассмотренные подходы потому что их средний случай сильно уступает среднему случаю популярных сегодня алгоритмов (например, dlmalloc). C худшим случаем всё наоборот! Как я отметил в тексте, анализ систем реального времени рассматривает прежде всего именно худший случай, в отличие от обычных приложений.
Об обосновании различий в подходах я ещё только что вот написал ответом к первому комментарию выше, посмотрите.
Вы ничего не поняли. Простите за прямоту, я хочу сэкономить нам обоим время. Прочитайте учебники, что я предложил, подтяните матчасть, потом возвращайтесь. Ничего личного.
По просьбе автора я оставил комментарий, но опубликовал его на другой странице: https://habr.com/ru/post/512570/#comment_21908502
Я пока не увидел новых идей в вашей публикации. Если я что-то упустил или не так понял, пожалуйста, поправьте меня.
Согласно моему пониманию, вы описываете дисциплину организации очереди (мультиплексирования) с регулировкой скорости (rate-controlled service discipline). Конкретно в вашем случае, как это обычно бывает с RCS, вы описываете несохраняющую работу дисциплину (non-work-conserving service discipline, NWC). RCS в целом широко применяются в сетях реального времени с гарантированными характеристиками. Несохраняющие работу дисциплины могут быть неприемлемы в коммерческих сетях потому они, по своему определению, допускают простой (бездействие) канала, что снижает его среднюю загрузку, от чего страдает рентабельность оборудования и средний уровень обслуживания. Смысл их использования сводится к более равномерной резидентности пакетов по маршруту и упрощению анализа сети, что представляет высокую ценность лишь в реальном времени. Средний случай несохраняющей работу дисциплины обслуживания хуже, чем у сохраняющей, но с худшим случаем это отношение может быть обратным. Обратите внимание, что подобная инверсия отношения среднего и худшего случая наблюдается и в других областях; например, в аллокаторах памяти.
Я подозреваю, что вы можете возразить здесь, сказав, что ваше решение предлагает символьное планирование, а не пакетное, но это не имеет значения. Теория сетевого анализа применима независимо от определения единицы данных: это может быть пакет, символ, или отдельный бит. В силу простоты моделирования обычно применяется последнее, с последующей корректировкой модели для адаптации к пакетной коммутации (битовые потоки не коммутируются).
Конкретно для описанного вами случая обратите внимание на статью Rate-Controlled Service Disciplines (Zhang, Ferrari, 1994), где приводится анализ практически вашего случая, но с адекватным теоретическим аппаратом. Если у вас нет понимания сетевого анализа, рекомендую начать с вводного курса Network Calculus: A Comprehensive Guide (Bemten, Kellerer, 2016), иначе с наскоку утонете. Если интересует реальное время, ознакомьтесь с учебником Safety and Certification Approaches for Ethernet-Based Aviation Databuses (я его уже указал в источниках к этой статье). Также обратите внимание на десятки других методов планирования трафика под разные задачи, помимо класса RCS: D-EDD, VC, WFQ, EDF, и т.п., каждый из которых имеет свои преимущества и недостатки в конкретных приложениях.
На чём основано и что означает утверждение о "гарантированной надёжности" я не понял.
Что касается маршрутизации: вы писали о маршрутизации от источника, но это, в принципе, вещь широко известная и практикуемая. Я вот здесь даже писал о SpaceWire, как пример.
Если вы планируете и дальше заниматься этим вопросом, вам следует ознакомиться с современной теорией, иначе есть риск открыть Америку.
Да, через директиву
@union. См. примеры и определение в спецификации. Ещё можете заглянуть в руководство, там это упоминается, в т.ч. в контексте проектирования типобезопасных интерфейсов.Не покладая клавиатуры над поддержкой v1 в PX4 трудится товарищ Daniel Agar; вы можете наблюдать за прогрессом тут: https://github.com/PX4/Firmware/pull/14865. Параллельно идёт работа над DS-015 (чем со следующей недели я начну заниматься лично) и сериализацией (вместо ревью ценного пулреквеста я засел вот писать статью, сами видите). Всё это необходимо для интеграции в PX4.
Где именно?
Есть. Рассказывайте. Можно в личку.
Перед массивами переменной длины всегда есть длина. Я не знаю, о каком примере вы говорите, но, судя по вашему описанию, он корректен. Репрезентация массивов переменной длины описана спецификацией в разделе 3.7.4.2 Variable-length array types; там объясняется, как кодируется этот префикс.
Длина была бы не нужна только если бы определение было не
uint8[<=50] name, аuint8[50] name.Ваш комментарий относится скорее не к технологии, а к экосистеме вокруг неё. Экосистема не вырастет за ночь или даже за год; это крайне длительный процесс, и не следует ожидать консистентной поддержки вендорами технологии, альфа-релиз которой состоялся лишь шесть месяцев назад. По части конкретно дронов (я так понял, вы из этого сектора) у нас немного сошёл с рельсов процесс в марте этого года, когда выяснилось, что поддержка v1 не успевает в merge window следующего релиза PX4, что косвенно снизило приоритет внедрения и в других проектах из той же отрасли. Происходит это из-за хронической нехватки ресурсов, что вы (ваша компания) можете самым непосредственным образом помочь исправить, если вы видите потенциал во внедрении UAVCAN в ваши продукты. Если вы готовы рассмотреть прямое участие, напишите, пожалуйста, мне в личку — вопросы планирования ресурсов проекта мы не можем обсуждать публично.
Переход от экспериментальной версии v0 к стабильному релизу v1, безусловно, сказался очень тяжело на экосистеме, но это было ожидаемо, и если бы этого можно было избежать, мы бы поступили иначе. Не один тред на форуме посвящён ответам на разные формы вопроса "зачем ломать что работает", так что я тут не буду повторяться. Скажу лишь, что v0 всегда был тестовой площадкой; несколько лет назад я имел смелость сказать, что "v1 вот-вот уже выйдет", но кроличья нора оказалась существенно глубже. Опасения о внезапном выходе v2 со всеми вытекающими для вас как вендора необоснованны, потому что само предположение о том, что v0 является стабильным релизом некорректно (иначе мы назвали бы его v1). Мы заинтересованы в успехе технологии и экосистемы, и мы не собираемся стрелять себе (и вам) в ногу, ломая совместимость с тем, что мы строили шесть лет.
Ваши слова об отсутствии чёткого описания объективно не соответствуют действительности. Возможно, вы имели в виду, что не хватает удобоваримой документации, что было бы правдой, ведь спецификация написана максимально нудным языком (как это обычно бывает со спецификациями). Мы пытаемся это исправить в официальном руководстве, и нам очень нужна конструктивная критика от интеграторов вроде вас.
Насчёт Yukon — его действительно нет, никогда не было, наличие никогда не заявлялось, и причины всё те же. Пока его заменяют инструменты командной строки. Они не фонтан, конечно, но с задачей справляются пока мы работаем над нормальным инструментом.
Насчёт регистров я вас не понял.
(спустя месяц) готово: https://github.com/UAVCAN/libcanard/pull/142
Мне кажется, что вы излишне углубляетесь в конкретику моего примера. Можно сконструировать другой пример, где вместо памяти под нужды системы управления межпланетным чайником мы будем выделять буферы под сообщения, что он принимает из ЦУП. Чайнику неизвестно, какие придут сообщения, в какой момент, и как они будут упорядочены во времени. В конечном итоге, потребный ресурс памяти будет ограничен сверху пропускной способностью линии связи и способностью чайника к обработке сообщений по мере их поступления. Если вас интересуют более конкретные примеры, посмотрите, например, на организацию работы с памятью в lwIP. Конечно, к системам жёсткого реального времени его можно отнести с натяжкой, но родственные сетевые технологии используются, например, в аэронавтике (AFDX, ARINC 664) и другом транспорте (SOME/IP, DDS/RTPS). Если пойти дальше, федеральное агентство аэронавтики США вполне всерьёз обсуждает тонкости реализаций буферизации и управления памятью в публикации Safety and Certification Approaches for Ethernet-Based Databuses. Вообще, современные и зарождающиеся сетевые протоколы на транспорте отличаются от предшественников существенно более высокой сложностью и предлагаемыми абстракциями, которые часто требуют более сложных подходов к реализации. Я не хотел бы сейчас погружаться в тонкости сетевых протоколов реального времени для отказоустойчивых систем, потому что тема крайне обширная и выведет нас далеко за рамки текущего вопроса.
В моём сообщении выше речь шла о мыслительных ресурсах программиста, простите, если выразился неясно. Именно об их экономии рассуждает и Хертер. Они ценны не только с точки зрения человекочасов, затраченных на проектирование и реализацию ПО, но и с позиции вероятности появления непредусмотренных поведений в программе. Вы не хуже меня знаете, что человеческий мозг слаб, и наши возможности по удержанию в голове сложных абстракций ограничены.
Вы сэкономите память и затраты когнитивных ресурсов на реализацию логики вашего приложения. Динамическое выделение позволяет удовлетворить потребность приложения в памяти при меньшем её общем размере благодаря разнесению перекрывающихся в адресном пространстве аллокаций во времени. Упрощение логики же достигается обобщением задач управления памятью в аллокаторе. Об этом пишет и Хертер:
Например, если ваш чайник требует 100 кб под нужды системы управления во время полёта на Луну, и ещё столько же во время движения по её поверхности, вы можете сэкономить половину, зная, что эти режимы взаимоисключающи и не могут быть активны единовременно. Вместо того, чтобы делать оверлеи на буфере вручную, вы просто делегируете это дело аллокатору.
Однако, от моего внимания, разумеется, не ускользает то факт, что снижение ресурсоёмкости и упрощение логики, которое даёт динамическое размещение, даётся ценою более сложной модели поведения программы. Я согласен с вашей подразумеваемой позицией, что динамическое размещение не является серебряной пулей, что его цена высока, и во многих случаях не является оправданной. В следующей цитате из поста ключевым словом является "разумное":
Посмотрим. Я ещё работаю над этим стеком; если к окончанию наберётся критическая масса интересных соображений, постараюсь поделиться.
Я не развею ваши сомнения. Точное прогнозирование выполняется в одних случаях легко, в других нет; ваш пример из второго. Если развивать пример дальше, то предсказание временных/ресурсных характеристик системы с SQLite потребует анализа не только движка БД, но и логики, что работает поверх и формирует запросы.
Для исключения этого существует модель худшего случая фрагментации. Вы можете статически доказать, что чайник всегда включится, если известна потребность приложения в памяти. Можно провести аналогии с определением размера стека, если угодно.
Динамическое выделение и предсказуемость временных характеристик не связаны, как я показал в статье. Чем обсусловлена ваша позиция?
Если выйти за рамки тривиальных сигнальных протоколов, то отказ от динамической памяти не позволит сделать реализацию для общего случая, не делающую предположений о функциях и поведении приложения. Я работаю как раз над такой общей реализацией.
Если конкретные временные и поведенческие характеристики приложения хорошо известны, то, конечно, можно насрезать углов и свести реализацию к работе со статически предвыделенными буферами и т.п. Выбор оптимального подхода определяется главным образом требованиями к валидации и верификации ПО и доступными ресурсами на разработку.
(ошибся веткой)
(Поясню для остальных: речь идёт о библиотеке Libcanard, которая реализует сетевой протокол для систем реального времени UAVCAN v1.0)
Вот прямо сейчас работаю над этим. Будет готово к осторожному использованию с недели на неделю, следите за новостями на GitHub или на форуме.
Тут проблема в том, что если максимальный размер достаточно велик (это часто так в моих задачах, например), то подход с блочной аллокацией как вы его описали окажется менее эффективным по памяти, чем выделение фрагментов произвольного размера. И то, и другое можно делать за гарантированное время.
С нетерпением буду ждать ваших студентов.
Обратите внимание, что если вы работаете над системой реального времени, средний случай вас обычно не интересует. Практические замеры позволяют оценить именно его (исключая, возможно, какие-то очень особые подходы, специально предназначенные для поиска граничных случаев, не берусь обобщать). Для обычных (не реального времени) систем, конечно, сравнить было бы интересно. Я не готов браться за это самостоятельно, но мог бы посодействовать, если найдутся желающие.
Не могли бы вы раскрыть тему подробнее, пожалуйста? О каких особенностях тут идёт речь?
Я предлагаю вам прочитать только две; как я написал выше, "детальное описание есть на странице 27-28".
Я не делал практических замеров, потому что меня интересует доказуемый худший случай. Однако, я согласен с вами, что в целом это вопрос интересный.
Вы правы, я немного перешагнул через практическую сторону. Это отчасти умышленно, ведь смысл публикации не в предложении новых технических методов, а в информировании коллег о том, что популярные представления о методах работы с памятью в системах реального времени зачастую ошибочны.
Рассматриваемые методы не новы и описаны в диссертации по ссылке и других гуглимых ресурсах. В моей библиотеке реализован алгоритм Half-Fit — один из трёх основных, наряду с более простым buddy allocator и более сложным TLSF. Детальное описание есть на странице 27-28, плюс комментарии к моей реализации есть прямо в README моей библиотеки. Buddy allocator я исключил из-за его более высокой (но детерминированной!) вычислительной сложности в сравнении с half-fit (который был предложен позже и более совершенен), TLSF же имеет более тяжёлый худший случай фрагментации за исключением одного вырожденного случая, где его поведение эквивалентно half-fit. Я мог бы набросать аналогичную заметку по этой теме, но зачем повторяться, ведь в источниках по ссылкам вопрос рассмотрен достаточно детально.
Обычные, классические приложения (не (жёсткого) реального времени) не используют рассмотренные подходы потому что их средний случай сильно уступает среднему случаю популярных сегодня алгоритмов (например, dlmalloc). C худшим случаем всё наоборот! Как я отметил в тексте, анализ систем реального времени рассматривает прежде всего именно худший случай, в отличие от обычных приложений.
Об обосновании различий в подходах я ещё только что вот написал ответом к первому комментарию выше, посмотрите.