Планировщик EDF в eCos Опции

[Zhorick]

Здравствуйте!

Думаю написать динамический планировщик типа EDF (Earliest Deadline First) для eCos.
Задача в большей степени учебная, но все же хотелось бы избежать лишних ошибок и услышать мнения специалистов по eCos-у.

На данный момент в eCos реализованы планировщики:
- Bitmap (32 уровня приоритета, на каждом уровне может находиться только один поток);
- многоуровневые очереди;
- лотерейный планировщик.
По-сути, все эти планировщики, если верить хотя бы этому: http://ipm.kstu.ru/os/lec/4.php не предназначены для планирования задач реального времени (в первую очередь периодических задач, для которых точно известны времена выполнения, дедлайнов и периоды возникновения). На базе этих планировщиков можно реализовать только статические алгоритмы планирования, в которых приоритеты потоков будут жестко задаваться на уровне компиляции. Динамическое планирование там невозможно.

Попытки написать EDF в eCos уже были, причем довольно недавно..например, тут:
http://sourceware.org/ml/ecos-discuss/2010-01/msg00017.html
только ничего путного, как я понял, у них не получилось.

Можно по 3-м направлениям работать:
- писать планировщик на базе уже существующего в eCos, например, MLQ;
- писать с нуля;
- оставить существующий планировщик и создать какую-либо надстройку (по аналогии
например, с тем же RTAI в Linux) для обслуживания задач РВ.

Третий варинат мне нравится больше всего, ведь останется какая-никакая совместимость.
Конкретные детали пока обдумываю, читаю про RTAI, Xenomai, KURT, смотрю, как у них сделано.
Может быть, посоветуете еще чего-нибудь?

[Zhorick]

Здравствуйте еще раз!
На этой неделе доделал первую версию EDF планировщика для eCos-а.
Общая идея в том, что для хранения потоков у меня используется не в двусвязный список (или массив массив указателей), как в существущих планировщиках, а красно-черное дерево:
http://ru.wikipedia.org/wiki/Красно-чёрное_дерево

По-сути, это то же самое бинарное дерево, у которого длина всех ветвей равна (если говорить точнее, отличается не больше, чем на 1). Вычислительная сложность для всех операций с деревом - О(log n).
Кстати, идея эта не новая. Красно-черные деревья уже используют в RTAI. Хотя, довольно спорный вопрос, стоит ли их применять во встраиваемых системах =).
Потоки в дереве отсортированы по абсолютному времени крайнего срока завершения (дедлайна), и при планировании управление передается тому потоку, у которого это время наименьшее.
Для этого пришлось в исходники eCos добавить классы Cyg_RBNode, Cyg_RBTree работы с деревьями
(по аналогии с существующими Cyg_DNode и Cyg_CList), шаблонные классы, переписать несколько классов
для планировщика из ядра eCos, и дополнить заголовочные файлы ядра.
Сейчас разбираюсь со скриптами CDL, чтобы этот планировщик можно было выбрать и сконфигурировать в ConfigurationTool.
Создание потока выглядит следующим образом:

// -------------------------------------------------------------------------
cyg_thread thread_s;
char stack[2048];
cyg_thread_entry_t entry0;
cyg_handle_t thread_hdl;
// Время задается в тиках системных часов RTC
cyg_edf_sched_info_t edf_info =
{40, /* относительное время дедлайна */
10, /* время выполнения в худшем случае */
100 /* период возникновения */
};
/* . . . */
cyg_thread_create((cyg_addrword_t)(edf_info), entry0, (cyg_addrword_t) 2,
"Thread А", (void *) stack, 2048,
thread_hdl, &thread_s);

// -------------------------------------------------------------------------


Теперь возникла еще одна проблема...
Изначально EDF (как и статические алгоритмы), создавался для планирования независимых задач.
Как быть, если требуется организовать взаимодействие между потоками? Для статических алгоритмов разработана куча механизмов синхронизации: всякие мютексы, семафоры, очереди сообщений, флаги событий.
Будут ли они работать для динамических алгоритмов?

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

Как реализовать, например, наследование приоритетов в динамическом планировщике? Если, по аналогии с приоритетом потока в статических планировщиках, изменять время дедлайна (по-сути, тот же приоритет), будет ли система планируемой
(другими словами, успеет ли обработать все потоки)?

Еще один вопрос. В системах реального времени часто требуется обрабатывать какие-либо периодические события (например, прерывания от внешних устройств, обработку пакетов данных и т.д.). При этом хорошо было бы теоретически доказать, что система является планируемой. Конечно, по этой теме написаны целые научные труды, есть формулы оценки планируемости (хотя бы сумма Ci/Ti из книжки Таненбаума).
Используется ли что-то из этого на практике, или можно обойтись как-то попроще?


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

Сообщение отредактировал Zhorick - Feb 11 2011, 08:40

[AlexandrY]

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

Как понимаю данная тема к встраиваемым системам управления мало подходит, у нее ноги растут из приложений для мультимедиа в частности в применении к реализациям MPEG-4.

Тогда eCOS неудачный выбор для базы проекта.