Ищем сравнение различных алгоритмов планирования для конечного автомата
Существуют ли хорошие ресурсы (книги, веб-сайты), которые дают очень хорошее сравнение различных алгоритмов планирования для конечного автомата (FSM) во встроенной системе без ОС?
Я проектирую простой встроенный веб-сервер без ОС. Я хотел бы знать, какие различные методы используются для планирования обработки различных событий, которые происходят в системе.
Например, если два события прибыли одновременно, как эти события имеют приоритет? Если я назначаю различные приоритеты событиям, как мне обеспечить, чтобы событие с более высоким приоритетом обрабатывалось первым? Если во время обработки события происходит событие с еще более высоким приоритетом, как можно убедиться, что это событие обрабатывается немедленно?
Я планирую использовать FSM для проверки различных условий по прибытии события, а затем правильно запланировать событие для обработки. Поскольку встроенный веб-сервер не имеет ОС, я рассматриваю возможность использования циклического исполнительного подхода. Но я хотел бы увидеть сравнение плюсов и минусов различных алгоритмов, которые могут быть использованы в этом подходе.
2 ответа
Вы утверждаете: "Я имею в виду, например, планирование условия в том же духе, если в одно и то же время прибыло две задачи, какой задаче необходимо уделить приоритетное внимание, и сравнить другие ситуации во встроенном веб-сервере".
Что я интерпретирую как: "Какой набор правил используется для определения того, какая задача выполняется первой (запланированной), когда несколько задач поступают одновременно".
Я использовал вашу терминологию "задача", чтобы проиллюстрировать сходство. Но Клиффорд прав. Правильный термин должен быть "событие" или "сообщение".
И когда вы говорите "условие планирования", я думаю, что вы имеете в виду "набор правил, которые определяют расписание событий".
Определение алгоритма: Процесс или набор правил, которым необходимо следовать в вычислениях или других операциях решения проблем, особенно с помощью компьютера.
Из статьи под названием " Алгоритмы планирования":
Рассмотрим центральный процессор компьютера, который должен обрабатывать последовательность заданий, поступающих с течением времени. В каком порядке должны обрабатываться задания, чтобы минимизировать, в среднем, время, в течение которого задание находится в системе с момента поступления до завершения?
Что, опять же, звучит как то, что вы называете "условиями планирования".
Я говорю об этом, потому что использование правильных слов для описания того, что вы ищете, поможет нам (сообществу SO) дать вам лучшие ответы. И поможет вам в дальнейшем исследовании самостоятельно.
Если моя интерпретация вашего вопроса все еще не соответствует вашим ожиданиям, пожалуйста, дайте мне знать, что, в частности, я сказал неправильно, и я попробую еще раз. Может быть, еще несколько примеров помогут мне лучше понять.
Некоторое дальнейшее чтение по планированию (что вы и просили):
- Хорошей отправной точкой, конечно же, является статья в Википедии о планировании дисциплин.
- Чуть ниже уровня, чем вы ищете, но все еще полно подробной информации о планировании, это Алгоритмы планирования для синтеза высокого уровня (ПРИМЕЧАНИЕ: по какой-то причине PDF имеет страницы в обратном порядке, поэтому начните снизу)
Пример приоритетного планировщика прерываний:
Возьмите архитектуру, где уровень приоритета 0 самый высокий. Два события приходят одновременно. Один с приоритетом 2, а другой с приоритетом 3. Алгоритм планирования начинает обработку алгоритма с приоритетом 2, поскольку он имеет более высокий приоритет.
Пока обрабатывается событие с приоритетом 2, приходит другое событие с приоритетом 0. Планировщик прерывает событие с приоритетом 2 и обрабатывает событие с приоритетом 0.
После завершения обработки события с приоритетом 0 возвращается обработка события с приоритетом 2. Когда он завершает обработку события Приоритета 2, он обрабатывает событие Приоритета 3.
Наконец, когда все операции с приоритетными прерываниями завершены, он возвращает управление основной задаче обработки, которая обрабатывает события, для которых приоритет не имеет значения.
Иллюстрация:
На изображении выше "задача" - это супер цикл, о котором упоминал DipSwitch, или бесконечный цикл в main() это происходит в циклической исполнительной власти, которую вы упомянули. "События" - это различные подпрограммы, которые выполняются в суперцикле или прерываниях, как показано выше, если они требуют приоритизации.
Условия для поиска: приоритетное прерывание и поток управления. Некоторым хорошим материалом для чтения является спецификация ядра Toppers (откуда я взял образ), архитектура прерываний ARM и статья об архитектуре прерываний 80196.
Я упоминаю спецификацию Toppers Kernel только потому, что именно там я получил изображение. Но в основе любой ОС реального времени лежит алгоритм планирования и архитектура прерываний.
Обработка "по событию", о которой вы спрашиваете, будет обрабатываться подсистемой прерываний микропроцессора / микроконтроллера. То, как вы структурируете уровни приоритета и как вы обрабатываете неприоритетные события, является тем, что составляет совокупность вашего алгоритма планирования.
Пример кооперативного планировщика:
typedef struct {
void (*task)(void); // Pointer to the task function.
uint32_t period; // Period to execute with.
uint32_t delay; // Delay before first call.
} task_type;
volatile uint32_t elapsed_ticks = 0;
task_type tasks[NUM_TASKS];
void Dispatch_Tasks(void)
{
Disable_Interrupts();
while (elapsed_ticks > 0) { // TRUE only if the ISR ran.
for (uint32_t i = 0; i < NUM_TASKS; i++) {
if (--tasks[i].delay == 0) {
tasks[i].delay = tasks[i].period;
Enable_Interrupts();
tasks[i].task(); // Execute the task!
Disable_Interrupts();
}
}
--elapsed_ticks;
}
Enable_Interrupts();
}
// Count the number of ticks yet to be processed.
void Timer_ISR(void)
{
++elapsed_ticks;
}
Приведенный выше пример взят из поста в блоге под названием "Простое совместное планирование".
Кооперативный планировщик представляет собой комбинацию супер цикла и прерывания по таймеру. Из раздела 2.4 в НЕБЛОКИРОВОЧНОМ ОБОРУДОВАНИИ ОБОРУДОВАНИЯ ДЛЯ ВСТРОЕННЫХ СИСТЕМ:
Кооперативный планировщик по сути представляет собой комбинацию двух ранее обсужденных планировщиков. Один таймер настроен на прерывание через регулярный интервал, который будет минимальным временным разрешением для различных задач. Затем каждой задаче присваивается период, кратный минимальному разрешению интервала прерывания. Затем постоянно вызывается функция для обновления счетчика прерываний для каждой задачи и запуска задач, которые достигли своего периода прерывания. Это приводит к планировщику, который имеет масштабируемость Superloop с надежностью синхронизации планировщика, запускаемого по времени. Это широко используемый планировщик для сенсорных систем. Однако этот тип планировщика не лишен своих ограничений. По-прежнему важно, чтобы вызовы задач в совместном планировщике были короткими. Если одна задача блокируется дольше, чем один период прерывания по таймеру, срочная задача может быть пропущена.
А для более глубокого анализа, вот статья из Международного журнала электрических и компьютерных наук.
Вытесняющий или кооперативный:
Кооперативный планировщик не может обрабатывать асинхронные события без какого-либо алгоритма вытеснения, выполняющегося поверх него. Примером этого может быть многоуровневая архитектура очереди. Некоторое обсуждение этого можно найти в этой статье по планированию ЦП. Конечно, у каждого есть свои плюсы и минусы. Некоторые из которых описаны в этой короткой статье о RTKernel-32.
Что касается "любого процесса планирования приоритетного планирования любого конкретного типа, который может удовлетворить планирование задач на основе приоритетов (как в графике)", любой контроллер прерываний на основе приоритетов по своей природе является вытесняющим. Если вы запланируете одну задачу на прерывание, она будет выполнена, как показано на графике.
Если бы я знал, что означает этот вопрос, ответ, вероятно, был бы, вероятно, практическим UML-диаграммой Миро Самека в C/C++, второе издание: программирование на основе событий для встроенных систем.