Планировщик

02/11/2011 - 14:05
   
Стандартный путь построения программ для микроконтроллеров основывается на применении так называемого суперлупа (superloop). Он представляет собой бесконечный цикл, в теле которого запускаются различные функции. Функции могут запускаться постоянно или в случае выполнения каких-то условий, например установки флагов. 
   Программы, построенные на таком принципе, обычно используются для простых приложений  с небольшим количеством задач, и в которых нет требований к таймингам. 
  Другой способ организации микроконтроллерных программ основан на применении планировщиков. Такие программы лучше структурированы, их проще модифицировать и они позволяют задавать время запуска задач. 
   В этой статье мы рассмотрим один из вариантов реализации простого планировщика.
 
 Планировщики – это одни из основных компонентов операционных систем, так как они распределяет процессорное время между задачами (процессами), создавая иллюзию параллельной работы. Планировщики подразделяются на кооперативные и вытесняющие.  
   В случае с кооперативными планировщиками, одиночная задача выполняется от начала и до конца. Поэтому важно, чтобы даже самая длинная задача укладывалась во  временной интервал системного таймера. Такие планировщики простые и понятные. 
   В случае с вытесняющими планировщиками, задачам отводится определенный квант времени. По завершению выделенного времени планировщик прерывает выполнение задачи, сохраняет ее контекст и запускает на выполнение другую задачу. Спустя какое-то время, первоначальная задача будет снова запущена на выполнение с того места, на котором она была остановлена. Реализация такого планировщика более трудоемка.
 
   Идея с кооперативным планировщиком заключается в следующем. У нас есть постоянно работающий таймер, который при переполнении перезагружается. Таймер формирует отрезки времени, используемые для синхронизации задач.  
   Для каждой задачи мы определяем две основные вещи – задержку перед самым первым выполнением задачи и период ее выполнения. Во время каждого прерывания таймера, запускается планировщик, который уменьшает значения счетчиков задач и помечает те из них, которые готовы к выполнению. 
   В главном цикле программы функция, именуемая диспетчером, выполняет помеченные задачи.  

Задачи                                                                                  

   Давайте начнем с рассмотрения задачи. Посмотрите на следующее описание.
#include <ioavr.h>
#include <intrinsics.h>
 
// Типы данных //
typedef unsigned char u8;
typedef unsigned int u16;
typedef struct task
{
   // указатель на функцию
   void (*pfunc) (void);
   // задержка перед первым запуском задачи
   u16 delay;
   // период запуска задачи
   u16 period;
   // флаг готовности задачи к запуску
   u8 run;
}task;
 
/// Определения ///////////
// Константа для таймера Т0
// 25 мс при тактовой частоте
// 8 МГц и предделителе 1024
#define StartFrom       0x3D
// максимальное количество задач
#define MAXnTASKS       8
 
/// Массив задач ///////////
volatile task TaskArray[MAXnTASKS];
   Мы определяем новый тип данных, именуемый task. Это структура, которая содержит в себе основные параметры задачи:  указатель на функцию, временные параметры и флаг ее готовности. 
 
   Каждая задача выполняет свою функцию и чтобы это обобщить, мы используем такую вещь, как указатель - void (*pfunc) (void). Как видно из описания, это указатель на функцию, которая не принимает аргументы и ничего не возвращает. Следует оставить функции задач именно в таком виде. Если у вас есть потребность в коммуникации задач между собой, нужно обеспечить ее с помощью глобальных переменных. 
   Задержка до первоначального выполнения задачи и интервал между последующими запусками (переменные dalay и period)задаются в виде количества «тиков» системного таймера, в роли которого у нас выступает 8-ми разрядный таймер Т0.
 
   Далее по коду мы задаем константу, определяющую период переполнения системного таймера, максимальное количество задач и объявляем массив для их хранения. 
   Частота работы системного таймера должна быть подобрана таким образом, чтобы даже самая продолжительная задача успевала завершиться в пределах одного цикла. В данном случае я выбрал 25-ти миллисекундный интервал, но он может быть и меньше.
 
Перейдем к функции инициализации планировщика.
void InitScheduler (void)
{
   u8 i;
   
   // устанавливаем прескалер - 1024
   TCCR0 |= (1<<CS02)|(1<<CS00);
   // очищаем флаг прерывания таймера Т0
   TIFR = 1<<TOV0;
   // разрешаем прерывание по переполнению
   TIMSK |= 1<<TOIE0;
    // загружаем начальное зн. в счетный регистр
   TCNT0 = StartFrom;
 
   // очищаем массив задач
   for (i=0; i<MAXnTASKS; i++) DeleteTask(i);
}
 
void DeleteTask (u8 j)
{
   TaskArray[j].pfunc = 0x0000;
   TaskArray[j].delay = 0;
   TaskArray[j].period = 0;
   TaskArray[j].run = 0;
}
   Здесь мы просто конфигурируем таймер Т0 и очищаем массив задач с помощью функции DeleteTask().
 
   Для добавления задач используется функция AddTask(). Она определяет доступную позицию в массиве задач и помещает в нее новую задачу.
void AddTask (void (*taskfunc)(void), u16 taskdelay, u16 taskperiod)
{
   u8 n=0;
 
   // поиск следующей доступной позиции в массиве задач
   while ((TaskArray[n].pfunc != 0) && (n < MAXnTASKS)) n++;
 
   // размещение задачи
   if (n < MAXnTASKS)
   {
      TaskArray[n].pfunc = taskfunc;
      TaskArray[n].delay = taskdelay;
      TaskArray[n].period = taskperiod;
      TaskArray[n].run = 0;   
   }
}
   Например, если вы добавите следующие задачи в массив задач (AddTask (TestA, 0, 3), AddTask (TestB, 1, 4), AddTask (TestC, 4, 0)), то получите изображенный на рисунке  режим работы. 

Прерывание системного таймера  и диспетчер

   Самое время обсудить обработчик прерывания таймера и что в нем должно происходить. 
#pragma vector=TIMER0_OVF_vect
__interrupt void Timer0ovf(void)
{
   u8 m;
  
   //перезагрузка таймера Т0
   TCNT0 = StartFrom;
   
   for (m=0; m<MAXnTASKS; m++)
   {
      if (TaskArray[m].pfunc)
      {  
         //если подошло время запуска задачи 
         if (TaskArray[m].delay == 0) 
         {
            //устанавливаем флаг и перезаписываем счетчик 
            TaskArray[m].run = 1;
            TaskArray[m].delay = TaskArray[m].period;
         }
         else TaskArray[m].delay--;
      }
   }
}
 
   Что ж, это элементарно. Мы просто уменьшаем задержку для каждой задачи и помечаем задачи, готовые к запуску. Заметьте, что обработчик прерывания не вызывает никакие задачи, потому что должен работать быстро. Задачи запускаются из главного цикла программы с помощью специальной функции, называемой диспетчером. 
   Как видно из кода, переменная, в которой хранилась задержка первоначального запуска задачи, используется в качестве счетчика времени. После ее обнуления, она инициализируется значением переменной period. 
    
   Последняя функция, завершающая функционал нашего планировщика, это диспетчер. Она вызывается из основного цикла программы
void DispatchTask (void)
{
   u8 k;
        
   for (k=0; k<MAXnTASKS; k++)
   {
      if (TaskArray[k].run == 1)
      {
         // запуск задачи
         (*TaskArray[k].pfunc)();
         // очистка флага задачи
         TaskArray[k].run = 0;
      }
   }
}

   Тестовый проект

   Всесторонние испытания и доработку планировщика я оставляю на ваше усмотрение. 
   В качестве примера использования описанного планировщика, я предлагаю тестовый проект с тремя задачами. Задачи ничего полезного не делают, только выводят в последовательный порт определенные цифры. 
#include <ioavr.h>
#include <intrinsics.h>
#define sei() __enable_interrupt()
 
/// Типы данных //
typedef unsigned char u8;
typedef unsigned int u16;
typedef struct task
{
   // указатель на функцию
   void (*pfunc) (void);
   // задержка перед первым запуском задачи
   u16 delay;
   // период запуска задачи
   u16 period;
   // флаг готовности задачи к запуску
   u8 run;
}task;
 
/// Определения ///////////
// Константа для таймера Т0
// 25 мс при тактовой частоте
// 8 МГц и предделителе 1024
#define StartFrom       0x3D
// максимальное количество задач
#define MAXnTASKS       8
//Константа для UART`a
//скорость обмена 9600 при частоте 8 МГц
#define UBRRvalue 0x0033
 
/// Массив задач ///////////
volatile task TaskArray[MAXnTASKS];
 
/// Прототипы функций ////////
void InitUART (u16 baud);
void TransmitByte (u8 data);
void InitScheduler (void);
void UpdateScheduler(void);
void DeleteTask (u8 index);
void AddTask (void (*taskfunc)(void), u16 taskdelay, u16 taskperiod);
void DispatchTask (void);
 
void TestA (void);
void TestB (void);
void TestC (void);
 
/// Main //////////////
int main(void)
{
   // Инициализация 
   InitUART (UBRRvalue);
   InitScheduler();
        
   // Добавление задач       
   AddTask (TestA, 0, 3);
   AddTask (TestB, 1, 4);
   AddTask (TestC, 4, 0);
        
   sei();
        
   while (1) 
   {
      DispatchTask();
   }            
}
 
void InitUART (u16 baud)
{
   UBRRH = (u8)(baud>>8);                                                        
   UBRRL = (u8)baud;
   UCSRB = (1<<RXEN)|(1<<TXEN);              
   UCSRC = (1<<URSEL)|(1<<UCSZ1)|(1<<UCSZ0);
}
 
void TransmitByte (u8 data)
{
   while ( !( UCSRA & (1<<UDRE)) );
   UDR = data;
}
 
void InitScheduler (void)
{
   u8 i;
   
   // устанавливаем прескалер - 1024
   TCCR0 |= (1<<CS02)|(1<<CS00);
   // очищаем флаг прерывания таймера Т0
   TIFR = 1<<TOV0;
   // разрешаем прерывание по переполнению
   TIMSK |= 1<<TOIE0;
    // загружаем начальное зн. в счетный регистр
   TCNT0 = StartFrom;
 
   // очищаем массив задач
   for (i=0; i<MAXnTASKS; i++) DeleteTask(i);
}
 
void DeleteTask (u8 j)
{
   TaskArray[j].pfunc = 0x0000;
   TaskArray[j].delay = 0;
   TaskArray[j].period = 0;
   TaskArray[j].run = 0;
}
 
void AddTask (void (*taskfunc)(void), u16 taskdelay, u16 taskperiod)
{
   u8 n=0;
 
   // поиск следующей доступной позиции в массиве задач
   while ((TaskArray[n].pfunc != 0) && (n < MAXnTASKS)) n++;
 
   // размещение задачи
   if (n < MAXnTASKS)
   {
      TaskArray[n].pfunc = taskfunc;
      TaskArray[n].delay = taskdelay;
      TaskArray[n].period = taskperiod;
      TaskArray[n].run = 0;   
   }
}
 
 
#pragma vector=TIMER0_OVF_vect
__interrupt void Timer0ovf(void)
{
   u8 m;
 
   TransmitByte('-'); 
   
   TCNT0 = StartFrom;
   
   for (m=0; m<MAXnTASKS; m++)
   {
      if (TaskArray[m].pfunc)
      {   
         if (TaskArray[m].delay == 0) 
         {
            TaskArray[m].run = 1;
            TaskArray[m].delay = TaskArray[m].period;
         }
         else TaskArray[m].delay--;
      }
   }
}
 
void DispatchTask (void)
{
   u8 k;
   
   for (k=0; k<MAXnTASKS; k++)
   {
      if (TaskArray[k].run == 1)
      {
         // запуск задачи
         (*TaskArray[k].pfunc)();
         // очистка флага задачи
         TaskArray[k].run = 0;
      }
   }
}
 
void TestA (void)
{
   TransmitByte('1'); 
}
 
void TestB (void)
{
   TransmitByte('2'); 
}
 
void TestC (void)
{
   TransmitByte('3'); 
}
   Если вы подключите вашу любимую терминальную программу и получите следующий ряд… -1 -2 - - -13 -3 -23 -3 -13 -3 -3 -23 -13 -3 -3 -3 -123 -3 -3 -3 -13 -23 -3 -3 -13 -3 -23 -3 -13 -3 -3 -23 -13 -3 -3 -3 -123 ... это значит, что планировщик работает.
 
   Напоследок скажу, не желательно использовать с этой схемой прерывания. Единственное прерывание, которое должно здесь быть – это прерывание переполнения таймера. Если вы задействуете другие прерывания, задачи  не смогут запускаться в точно заданное время!
   По материалам сайта avrtutor.com, который, судя по всему, прекратил функционирование.  Код полностью взят оттуда. Текст частично мой, частично переводной. Pashgan.

Tagged under

Related items

Comments   

# Alexey 2011-11-03 05:10
Спасибо за очередной материал. Давно собирался опробовать аля ОС. Как раз вовремя статья пришлась. :-)
# Pashgan 2011-11-03 13:26
Да пожалуйста.
# ВладТ 2011-11-04 08:03
Немного не понял. Вы пишете:
Частота работы системного таймера должна быть подобрана таким образом, чтобы даже самая продолжительная задача успевала завершиться в пределах одного цикла.
А на самом деле вижу что:
Частота работы системного таймера должна быть подобрана таким образом, чтобы ОДИН ПРОХОД ВСЕХ(!) задач успевал завершиться в пределах одного цикла.
Так ли это?
# Pashgan 2011-11-04 09:25
В оригинале статьи написано именно так: "Частота работы системного таймера должна быть подобрана таким образом, чтобы даже самая продолжительная задача успевала завершиться в пределах одного цикла." Но если подумать логически, то напрашивается твой вариант.
# ВладТ 2011-11-04 10:26
Еще необходимо отметить, что порядок выполнения задач в одном интервале выполнения хаотический, например, Ваша цепочка 13 -3 -3 -3 -123 ... может быть и 31 -3 -3 -3 -231 ...
Это может происходить, когда прерывание произойдет во время цикла в DispatchTask, когда индекс k уже не равен 0. Прерывание выставит run=1 для всех(как в последнем звене Вашей цепочки -123...) - и диспетчер запустит k-тую задачу.
# Pashgan 2011-11-04 11:04
Да, это имеет место быть.
# igor727 2011-11-04 21:37
Павел, спасибо за статью очень интересная мысль!
Скоро будет проект по работе где возможно использую данный принцип или пойду по протоптанному пути - событийной системы, которая тоже очень нравится как работает.Недавн о делал макетик с проигрыванием Wav+SD как раз по принципу событийной системы читал/воспроизв одил аудио данные из кольцевого буфера, обработку кнопок, индикацию. все очень аккуратно пишется и работает стабильно. Кстате было бы очень интересно увидеть от Вас статью про SD карточки + FAT. Думаю ребята меня поддержут, а мы Вас ;)
# eltech21 2011-11-28 18:27
Спасибо огромное за статью!
Как я смог понять "жёсткого" реалтайма на такой системе не получить.
нашёл по теме:
"Простой анализ показывает, что кооперативные многозадачные системы пригодны только для учебных проектов или тех ситуаций, когда программисту на скорую руку необходимо сотворить многозадачное ядро. Вторая ситуация кажется несколько странной — зачем для серьезной работы может потребоваться быстро сделанное ядро, если существует много готовых систем реального времени"

Вопрос: чем вообще обеспечивается условие реалтайма "успел/неуспел" , кроме вычислительной мощности.
Где можно почитать про вытесняющую многозадачность и построение программы с помощью вытесняющего планировщика?
# Vfrcbv 2011-12-05 05:10
Скажите, а можно где-нибудь почитать так же подробно по реализации вытесняющегося планировщика?
# кАтя 2012-01-30 16:00
:-x :oops: :cry: :o ГОСПАДИ
# ArtemKAD 2013-09-14 19:45
Хорошая статья.
Вот только включать и выключать задачи в прерывании - это действительно слегка игрушечный подход. Возникает конфликт когда задачу запускает/остан авливает другая задача и прерывание. Лучше в прерывании только установить флаг события который в диспетчере уже обработать(к примеру перенести for из прерывания в диспетчер перед стоящем там for). Тогда все задачи и их переключение происходит на одном уровне не пересекаясь на служебных переменных.

У вас недостаточно прав для комментирования.

back to top