Планировщик 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 неудачный выбор для базы проекта.

[Zhorick]

Да, возможно, Вы правы.
Но в то же время, мультимедийные системы тоже, по-сути, являются системами реального (пусть и мягкого) времени. Почему те же принципы нельзя применять для систем управления? Или там все приоритеты жестко заданы при проектировании?
Можно ли динамическое планирование использовать в сетевых устройствах?

И, раз зашел разговор..какие ОС лучше применять для мультимедийных систем? Почему не стоит использовать eCos? Если посмотреть на список проектов с eCos-ом: http://ecoscentric.com/ecos/examples.shtml то где его только не применяют.

[Zhorick]

В продолжение темы...
Написал тест, который показывает, чем планировщик 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 ( 1.66 килобайт ) Кол-во скачиваний: 252

 log.tar.gz ( 862 байт ) Кол-во скачиваний: 243

Код

/*
*************************************************************************
* Файл: 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