Система, управляемая событиями и SST(super-simple tasker), Выделено из "ООП. Классы и динамические объекты" Опции

[brag]

Недавно я начал пользоваться динамической памятью. Раньше пользовался только статикой, то есть placement new. Со статикой сложно работать с такими шаблонами, как фабрика обьектов, временные задачи итд.
Программирую в основном под cortex-m3/m4
Код реализации аллокатора вышел довольно простым и быстрым, критически секции есть, но очень короткие(там прочитать/записать пару байт).
При чем я не использую этих всяких монстров под названием RTOS, у меня свой простейший асинхронный планировщик задач, занимает строк 300 кода с комментариями(погуглите запрос "super simple tasker", поймете что это).
В купе с динамическим аллокатором, variable element-size queue, новыми фишками C++ (шаблоны, лямбда-функции, auto) получается очень простой, безопасный и мощный фреймворк.
Вспоминаю работу с классическими Thread-ами(с ихними стеками - куча кода было написано для анализа программ на предмет нужного обьема стека, и теперь эта куча кода отправлена на мусорку) со всеми этими тяжеленными мютексами, семафорами, вечными циклами как страшный сон.

Если кому интересно - расскажу и покажу как это все работает.

[brag]

Например если у вас хотя-бы одна из задач будет представлять из себя длинный цикл то на время его выполнения остальные задачи будут курить бамбук )

А вот и нет. У каждой задачи есть приоритет. Если приоритет вашего цикла выше, чем остальных зада - да, будет бамбук. Точно так же, как это будет и с классическими тредами(попробуйте в любой ОС создать вечный цикл в треде и поставить треду высокий приоритет, а остальным низкий).
У каждой задачи есть приоритет, если есть более приоритетная задача - она синхронно или асинхронно вытесняет менее приоритетную.

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

В этом нет никакой необходимости.

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

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

Не знаю почему это у вас ассоциируется со страшным сном, потому что подпиливать постоянно задачи под ваш планировщик тоже так себе удовольствие )
Поразмышляйте хотя-бы над предложенным мною сценарием с задачами А Б В и поймете, что тобы дать возможность задаче В спокойно крутиться придется подпиливать задачи А и Б.

Да ничего подпиливать не нужно:

Код

enum { TASK_V_PRIORITY = 1, TASK_A_PRIORITY = 2, TASK_B_PRIORITY = 3};
void task_V(){
    while(true){
      // do some heavy work
    }
}
void task_A(){
//  do work
  return;
}
void task_B(){
//  do work
  return;
}

SST::runTask(task_V, TASK_V_PRIORITY);

void on_event_a(){
   SST::runTask(task_A, TASK_A_PRIORITY);
}
void on_event_b(){
   SST::runTask(task_B, TASK_B_PRIORITY);
}

Ну а если у вас нормальное переключение контекста и всё что я написал не актульно то поздравляю - вы изобрели потоки. Скоро в этой системе появятся мьютексы и семафоры )

Да, это полноценные потоки, зато без выделения стека, инверсии приоритетов, livelock-ов, и кучи других проблем. Тут идеология и техника другая.
Мютексы и семафоры не появятся. Зачем они нужны? Тут всем рулят очередя. В отличии от тредовой архитектуры тут нет вышеперечисленных проблем. А переполнение очереди легко отлавливается на программном уровне, при чем оно может произойти даже прозрачно для пользователя. В то время, как переполнение стека приводит к падению всей системы, а глюки с мютексами вообще очень трудно находимые, целый год может отработать нормально и в один прекрасный момент глюканет, потом еще год будете моделировать ситуацию искать баг. Потом со временем будете вынуждены написать свой анализатор гонок(как в свое время делал я, потому что Relacy не детектирует даже самую простую реальную ситуацию https://github.com/dvyukov/relacy/issues/3 ) и анализатор стека(а что если рекурсия, что если куча виртуальных функций, порядок и уровень вложения которых на этапе компиляции неизвестен?)

А фраза «Не очень недавно», это получается как бы «давно»?

Извиняюсь, имелсь в виду недавно. исправил.

А какая у Вас стратегия управления кучей, хотел иметь представление о следующем:
1. Как ведется учет занятой и свободной памяти?

Через linked-list. служебное поле занимает одно 32-битное слово, это и есть оверхед, все остальное - полезные данные.
Каждый блок указывает на предыдущий и следующий. Для удаления блока достаточно сходить не предыдущий и следующий, и если они(один из них) пустые - обьеденить с удаляемым.

Как ищется для объекта подходящий по размеру участок памяти?

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

2. Как в куче объединяются соседние пустые участки для увеличения непрерывного пространства под размещение следующих объектов? В какие моменты, и при каких условиях эти действия выполняются?

Ну уже написал выше от части, дополню:
1. идем в предыдущий блок, если пустой - увеличиваем его размер на N+1 слов. Где N - размер удаляемого блока.
2. идем в следующий блок. если он пустой - N=размер этого блока, повторяем процедуру 1. для предыдущего и выходим. Если не пустой - меняем указатель prev на блок, который получился в п1. все.
Физически блок выглядит вот так:
|prev_offset_word[14 bits], reserved[2 bits], size_words[14 bits], mask[2 bits]; uint32_t data[size_words]|


В самом аллокаторе ничего сложного нет. Doubly linked list на основе 14-битных "ссылок". Этого хватит, чтобы покрыть 64кб памяти - для большинства задач этого достаточно.
Фит-алгоритм возможно придется подобрать, который больше понравится.
1. best-fit (ищем блок минимального размера) - проблема - остаются очень мелкие бесполезные фрагменты. нужно искать блок - тормоза.
2. first-fit (добавляем в первый попавшийся блок, обычно тот, который недавно очистили) - мне больше всего нравится - во первых, быстро, во вторых, по моей статистике меньше всего фрагментации.
3. worst-fit (добавляем в блок самого большого размера) - тоже неплохо работает, но надо искать блок.

Блокировок прерываний нет, тк аллокатор не используется в прерываниях и других высоко-приоритетных задачах У меня всего 32 приоритета юзера + еще 16-256 приоритетов прерываний(зависит от конкретного процессора). Задачи и прерывания более высокого приоритета всегда вытесняют(прерывают) задачи более низкого.
Обычно аллокатор нужен для задач с приоритетом 0,1,2 - это всякого рода UI и другой медленный ввод-вывод. Тогда ставим приоритет аллокатору 4 и все, никаких блокировок не нужно - аллокатор всегда будет вытеснять задачи, которые его используют.