Перейти к содержанию
    

Система, управляемая событиями и SST(super-simple tasker)

Недавно я начал пользоваться динамической памятью. Раньше пользовался только статикой, то есть placement new. Со статикой сложно работать с такими шаблонами, как фабрика обьектов, временные задачи итд.

Программирую в основном под cortex-m3/m4

Код реализации аллокатора вышел довольно простым и быстрым, критически секции есть, но очень короткие(там прочитать/записать пару байт).

При чем я не использую этих всяких монстров под названием RTOS, у меня свой простейший асинхронный планировщик задач, занимает строк 300 кода с комментариями(погуглите запрос "super simple tasker", поймете что это).

В купе с динамическим аллокатором, variable element-size queue, новыми фишками C++ (шаблоны, лямбда-функции, auto) получается очень простой, безопасный и мощный фреймворк.

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Ну так извините меня, классические, как вы говорите, Thread-ы и ваш планировщик задач это мягко говоря разные вещи!

Да, конечно, есть ряд применений где такой подход достаточен.

 

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

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

Представим что в системе есть задачи А Б и В. Задача А ресурсоемкая и долго считает, задача Б должна ожидать результатов. А задачу В надо крутить постоянно и независимо от А и Б.

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

 

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

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Не очень недавно я начал пользоваться динамической памятью.

.......

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

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

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

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

 

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

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

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

 

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

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

 

Представим что в системе есть задачи А Б и В. Задача А ресурсоемкая и долго считает, задача Б должна ожидать результатов. А задачу В надо крутить постоянно и независимо от А и Б.

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

Точно так же себя ведет и мой 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 и все, никаких блокировок не нужно - аллокатор всегда будет вытеснять задачи, которые его используют.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Конечно интересно!

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Интересно. Где можно посмотреть код, примеры?

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Присоединюсь к интересующимся. Если я правильно понял то для более низкоприоритетной задачи высокоприоритетная по сути является прерыванием? И соответственно равноприоритетные задачи не предусмотрены?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединюсь к интересующимся. Если я правильно понял то для более низкоприоритетной задачи высокоприоритетная по сути является прерыванием?

Да, совершенно верно.

 

И соответственно равноприоритетные задачи не предусмотрены?

Конечно предусмотрены! И они выполняются в порядке очереди. Так же, как и прерывания. Закончилась одна задача - начинается выполнение другой. Или закончилось одно прерывание(а второе висело в пендинге) - начинается выполнение другого.

 

В дополнение - я считаю вечные циклы и мютексы - каменным веком. Необходимость мютексов возникает из за вечных циклов. Нет вечных циклов - нет и мютексов.

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

void Thread1(){
    while(true){
        if(must_i_exit)break;
        if(is_user_clicked_helo_button){
             messageBox("Hi dear user");
        }
    }
}
void Thread2(){
    while(true){
        if(must_i_exit)break;
        if(mp3_frame_ready){
             decodeMp3Frame(frame);
        }
   }
}

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

 

Теперь давайте попробуем откажемся от этих циклов:

void on_helo_button_clicked(){
    messageBox("Hi dear user");
}

void on_mp3_frame_received(const Mp3Frame* frame){
    decodeMp3Frame(frame);
}

Код стал даже проще, теперь нам нужен один стек, теперь нам не нужны мютексы и блокировки. Мало того, сами функции, выполняющие работу остались прежние.

 

Что происходит при блокировке:

1. блокируются, как минимум все потоки. и как максимум - все прерывания

2. сохраняются все регистры в стеке(а это 16 4-байтовых слов для кортекса без FPU)

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

4. восстанавливаются из стека все регистры.

5. разблокируется все обратно

 

Теперь что происходит при добавлении задачи в очередь:

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

2. резервируется в очереди место под задачу. Фактически данные задачи состоят из аргументов функции, то есть там пара-тройка 4-байтовых слов. В отличии от сохранения контекста, где их как минимум 16, а на практике больше.

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

3. блок снимается.

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

5. опять блокируемся

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

7. снимаем блок

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

Код такой очереди занимает 240 строк вместе с комментами и C++ными приколами. Сколько строк исполняемого кода занимает мютекс и переключение контекста в какой-нибудь FreeRTOS :)?

 

Интересно. Где можно посмотреть код, примеры?

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

Пока задавайте вопросы, если есть.

 

Выше я показал почему не нужны треды. А вот как можно без них обойтись - рассказано в этом материале http://www.embedded.com/design/prototyping...r-Simple-Tasker

Я конечно пошел дальше, сделал некоторые моменты более оптимально с учетом конкретной архитектуры(архитектур) и реализовал все на c++ чтобы было просто и удобно и безопасно пользоваться. Об этом позже.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Я конечно пошел дальше, сделал некоторые моменты более оптимально с учетом конкретной архитектуры(архитектур) и реализовал все на c++ чтобы было просто и удобно и безопасно пользоваться. Об этом позже.

 

Здесь с завидной регулярностью находятся первооткрыватели метода конечных автоматов Miro Samek-а.

Но индустрия уже давно проехала этот этап.

Вытесняющая асинхронная многозадачность сейчас даже в Arduino применяется.

Никто не пишет софт годный под модель SST.

Приняв SST вы останетесь голым, даже FatFS или lwIP не сможете портировать.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Вытесняющая асинхронная многозадачность сейчас даже в Arduino применяется.

SST и есть вытесняющая асинхронная многозадачность. Точно такая же, как и есть в мире PC, под названием Active Object паттерн итд. Где физически создается тред под конкретную задачу, отрабатывает и выходит.

Или взглянуть на NodeJS/javascript - там хоть и один поток, но все асинхронно без блокировок. Или ту же Qt. Мир потихоньку, вернее очень даже резво, движется в сторону неблокирующей модели.

 

Никто не пишет софт годный под модель SST.

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

 

Приняв SST вы останетесь голым, даже FatFS или lwIP не сможете портировать.

Портируем без проблем, при необходимости. Что есть такого в lwIP, что не ляжет на SST-модель? У меня давно написан свой fat и простейший ip-стек, который вообще не требует никакой ОС, то есть может работать на любой. Если нужно будет что-то готовое по-сложнее - запросто портируем на SST-модель. Тем более, на сколько я знаю, lwIp работает и в standalone, вообще без ОС.

Минусов я у нее не вижу, а вот очевидных плюсов достаточно. Перешел на нее я не так давно, и не по причине быстродействия, а по причине того, что сложный код под тредовую блокирующую модель рано или поздно либо ставал мертвым и глючным, либо сам превращался в active-object и другие асинхронные паттерны, появлялись очереди(каналы, как во всех модерн-языках типа Go) то есть все превращалось в SST. Треды были нужны только ради возможности работы этого всего. Создание запуск и удаление треда сопровождались огромными затратами ресурсов и блокировками. Потом я их выкинул за ненадобностью и заменил на простой и быстрый SST, где создание задачи занимает пару десятков инструкций :)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Очень интересно. Видимо этот SST прошел мимо меня... Надо будет почитать..

Add: Прочел http://www.embedded.com/design/prototyping...r-Simple-Tasker

Вселье закончилось тем, что все были загнаны в угол принудительным limiting all intertask communication to events после чего было замечено, что выполняющаяся задача блокирует все задачи ниже себя приоритетом и гордо были изобретены и мьютекс и критические секции )

Recall that the SST scheduler can only launch tasks with priorities higher than the initial priority with which the scheduler was entered. This means that temporarily increasing the current SST priority SST_currPrio_ blocks any tasks with priorities lower than this priority "ceiling." This is exactly what a priority-ceiling mutex is supposed to do. Listing 5 shows the SST implementation.

 

 

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

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Но даже если такое понадобится, например когда есть 2 тяжеленных алгоритма, например скажем mp3 и jpeg и надо чтобы они оба работали "одновременно", тогда и это не сложно решить на SST. Стек конечно придется выделить для этих двух задач и сделать простую переключалку по таймеру, но работать с остальными компонентами системы они запросто смогут через очереди - без всяких мютексов. И остальная система будет работать на едином стеке.

Но это в теории. На практике же любая работа с данными подразумевает деление на фреймы - получение и обработка фреймов по отдельности - Run to completion, а значит и необходимость в тайм-квант-планировщике практически отпадает.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

Пусть каждый поток имеет свою ивэнт очередь. Каждую итерацию цикла(а может и чаще) поток проверяет не поступил ли мне там ивэнт какой? И обрабатывает его если да.

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

И ладно бы эти все мьютексы не работали или действительно глючили на каждом шагу. Так нет же, работают вроде )

 

P.S. Никто не говорил, что многопоточное программирование это легко и просто. Но этот ваш SST больше отбирает чем дает.

Ну да, такты экономятся, спору нет. Реализация по-проще.... На этом все и заканчивается )

И я уже гвоорил, что в некоторых местах это может быть и вполне уместно!

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

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

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...