Zhorick 0 24 января, 2011 Опубликовано 24 января, 2011 · Жалоба Здравствуйте! Думаю написать динамический планировщик типа 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 0 11 февраля, 2011 Опубликовано 11 февраля, 2011 (изменено) · Жалоба Здравствуйте еще раз! На этой неделе доделал первую версию 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 из книжки Таненбаума). Используется ли что-то из этого на практике, или можно обойтись как-то попроще? Да..слишком много, наверное, я сейчас понаписал =) Пока еще начинаю работать в этой области, и достаточного опыта в системах реального времени у меня нет. Дело в том, что по этой теме я пишу диплом и хотелось бы сделать чего-то стоящее и полезное, что потом кому-то бы пригодилось. Изменено 11 февраля, 2011 пользователем Zhorick Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
AlexandrY 3 11 февраля, 2011 Опубликовано 11 февраля, 2011 · Жалоба Пока еще начинаю работать в этой области, и достаточного опыта в системах реального времени у меня нет. Дело в том, что по этой теме я пишу диплом и хотелось бы сделать чего-то стоящее и полезное, что потом кому-то бы пригодилось. Как понимаю данная тема к встраиваемым системам управления мало подходит, у нее ноги растут из приложений для мультимедиа в частности в применении к реализациям MPEG-4. Тогда eCOS неудачный выбор для базы проекта. ;) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Zhorick 0 11 февраля, 2011 Опубликовано 11 февраля, 2011 · Жалоба Да, возможно, Вы правы. Но в то же время, мультимедийные системы тоже, по-сути, являются системами реального (пусть и мягкого) времени. Почему те же принципы нельзя применять для систем управления? Или там все приоритеты жестко заданы при проектировании? Можно ли динамическое планирование использовать в сетевых устройствах? И, раз зашел разговор..какие ОС лучше применять для мультимедийных систем? Почему не стоит использовать eCos? Если посмотреть на список проектов с eCos-ом: http://ecoscentric.com/ecos/examples.shtml то где его только не применяют. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Zhorick 0 21 марта, 2011 Опубликовано 21 марта, 2011 · Жалоба В продолжение темы... Написал тест, который показывает, чем планировщик EDF лучше приоритетных планировщиков. Вкратце алгоритм тестирования: Создается 3 потока, в которых в течении заданного времени производится какая-либо обработка (у меня - просто опрашивает системный таймер). После завершения обработки поток блокируется. Разблокировка потоков (по-сути, активация задачи; в реальной системе может выполняться в обработчике ISR внешнего прерывания) осуществляется в функции-обработчике сигнальных часов (Alarm). При инициализации указывается периодичность вызова функции (и, соответственно, активации задачи). Получается, что: поток 0 запускается с периодом 29 тиков и выполняется 16 тиков поток 1 запускается с периодом 38 тиков и выполняется 13 тиков поток 2 запускается с периодом 49 тиков и выполняется 5 тиков Коэффициент загрузки процессора = 16/29+13/38+5/49=0.995 В приложении - 2 примера: 1 случай - для ecos-а со статическим приоритетным планировщиком Bitmap Приоритеты потоков: 10, 20, 30. Чем меньше значение, тем выше приоритет (10 - самый приоритетный) 2 случай - для ecos-а с планировщиком EDF. Различия исходников минимально (в EDF вместо приоритета у потока задаются 3 параметра: время выполнения задачи, период появления и время, к которому задача должна быть обработана). В итоге получаем, что приоритетный планировщик с высокой загрузкой уже не справляется (не успевает обработать все потоки), тогда как EDF может обеспечивать практически 100% загрузку процессора. Если посмотреть выводы теста, то и количество переключений контекста при использовании EDF-планировщика меньше. Исходник теста с EDF. В приложении - исходники и результаты тестов. src.tar.gz log.tar.gz /* ************************************************************************* * Файл: edftest.c * Тест дедлайнов планировщика EDF * Коэффициент использования процессора = 16/29+13/38+5/49=0.995 * *************************************************************************/ #include <cyg/kernel/kapi.h> cyg_thread thread_obj[3]; char stack[3][2048]; cyg_handle_t simple_thread[3]; // массив дескрипторов потоков cyg_thread_entry_t entry0; cyg_handle_t counter_hdl, sys_clk, alarm_hdl[3]; cyg_tick_count_t ticks; cyg_alarm_t alarm_handler; cyg_alarm alarm_obj[3]; int in_process[3] = {1, 1, 1}; // Период появления задачи #define PERIOD0 29 #define PERIOD1 38 #define PERIOD2 49 cyg_tick_count_t periods[3] = { PERIOD0, PERIOD1, PERIOD2 }; // Время обработки задачи в худшем случае #define CTIME0 16 #define CTIME1 13 #define CTIME2 5 cyg_tick_count_t ctimes[3] = { CTIME0, CTIME1, CTIME2 }; // Параметры потоков для планировщика EDF // Формат: <Дедлайн> <Время выполнения> <Период> cyg_edf_sched_info_t edf_info[3] = { { PERIOD0, CTIME0, PERIOD0 }, { PERIOD1, CTIME1, PERIOD1 }, { PERIOD2, CTIME2, PERIOD2 }, }; // --------------------------------------------------------------------- // externC void cyg_start(void) { // Создаем потоки задач cyg_thread_create((cyg_addrword_t)edf_info, entry0, (cyg_addrword_t) 0, "Thread A", (void *) stack[0], 2048, &simple_thread[0], &thread_obj[0]); cyg_thread_create((cyg_addrword_t)(edf_info + 1), entry0, (cyg_addrword_t) 1, "Thread B", (void *) stack[1], 2048, &simple_thread[1], &thread_obj[1]); cyg_thread_create((cyg_addrword_t)(edf_info + 2), entry0, (cyg_addrword_t) 2, "Thread C", (void *) stack[2], 2048, &simple_thread[2], &thread_obj[2]); sys_clk = cyg_real_time_clock(); cyg_clock_to_counter (sys_clk, &counter_hdl); cyg_alarm_create(counter_hdl, alarm_handler, 0, &alarm_hdl[0], &alarm_obj[0]); cyg_alarm_create(counter_hdl, alarm_handler, 1, &alarm_hdl[1], &alarm_obj[1]); cyg_alarm_create(counter_hdl, alarm_handler, 2, &alarm_hdl[2], &alarm_obj[2]); // Задаем периоды для активации задач cyg_alarm_initialize(alarm_hdl[0], cyg_current_time() + PERIOD0, PERIOD0); cyg_alarm_initialize(alarm_hdl[1], cyg_current_time() + PERIOD1, PERIOD1); cyg_alarm_initialize(alarm_hdl[2], cyg_current_time() + PERIOD2, PERIOD2); // Переводим потоки в состояние готовности cyg_thread_resume(simple_thread[0]); cyg_thread_resume(simple_thread[1]); cyg_thread_resume(simple_thread[2]); in_process[0] = in_process[1] = in_process[2] = 1; cyg_scheduler_start(); } // --------------------------------------------------------------------- // Точка входа в поток обработки // Для всех 3-х потоков используется одна функция // cyg_addrword_t data - номер потока void entry0(volatile cyg_addrword_t data) { cyg_tick_count_t ticks; int tnum; while(1) { ticks = cyg_current_time(); tnum = (int)data; diag_printf ("\n Thread %d start at time %llu \n", tnum, ticks); in_process[tnum] = 1; while (cyg_current_time() < ticks + ctimes[tnum]) { // Обработка в течение CTIMES тиков } diag_printf (" Thread %d end at time %llu \n", tnum, cyg_current_time()); in_process[tnum] = 0; // Блокируем поток cyg_thread_suspend(simple_thread[tnum]); } } // --------------------------------------------------------------------- // Функция активации задачи void alarm_handler (cyg_handle_t alarm_handle, cyg_addrword_t data) { int tnum = (int)data; diag_printf ("\nActivation of thread %d at time %llu \n", tnum, cyg_current_time()); if (in_process[tnum] == 1) // Поток не обработан diag_printf("\n\n!!! Thread %d DEADLINE \n", tnum); // Устанавливаем новое время дедлайна cyg_thread_set_edf_deadline(simple_thread[tnum], cyg_current_time() + periods[tnum]); // Разблокируем поток cyg_thread_resume (simple_thread[tnum]); } // end of edftest.c Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
