Delta Queue - встроенный планировщик

Question

Я пытаюсь реализовать простую дельта-очередь на небольшом Cortex-M3, чтобы запланировать некоторые задачи на будущее.Я что-то сконструировал, но не думаю, что это очень элегантно (я не пишу код часто).Это также кажется немного странным из-за неправильного использования volatile-спецификатора.

#include "deltaqueue.h"
#include "debug.h"
#include "interrupt.h"

//*****************************************************************************
//
// Define NULL, if not already defined.
//
//*****************************************************************************
#ifndef NULL
#define NULL                    ((void *)0)
#endif

//! Delta queue structure encapsulating a complete process entry into the queue
typedef struct dq{
    struct dq * psPrev;             //Address of previous queue entry
    struct dq * psNext;             //Address of next queue entry
    unsigned long ulDelta;          //Delta ticks (ticks relative to the next/previous process)          
    tProcessObject sProcess;        //Process to be executed
} tDeltaQueueObject;


//! Contains the maximum number of processes in the queue at any one time (health indicator).
static unsigned long g_ulMaximumProcesses=0;
//! Contains the current number of processes in the queue (health indicator).
static unsigned long g_ulCurrentProcesses=0;
//! Contains the current number of executed processes (health indicator).
static unsigned long g_ulExecutedProcesses=0;
//! Contains the total number of processes scheduled since initialized (health indicator).
static unsigned long g_ulTotalProcesses=0;

//! Contains the accumulated tick count.
static volatile unsigned long g_ulSchedulerTickCount;
//! Simple counter used to generate process IDs.
static unsigned long g_ulPID=1;
//! Pointer to the first sleeping process.
static tDeltaQueueObject * volatile psSleeping;
//! Pointer to the processes ready for execution.
static tDeltaQueueObject * psReady;
//! Pointer to an available slot in the queue.
static tDeltaQueueObject * psAvailable;
//! Queue of processes.
static tDeltaQueueObject sDeltaQueue[QUEUE_MAX];


unsigned long SchedulerElapsedTicksCalc(unsigned long, unsigned long);
unsigned long GetProcessID(void);
tDeltaQueueObject * FreeEntry(void);

//****************************************************************************
//
//! Initializes the scheduler.
//!
//! This function resets the queue pointers.
//!
//! \return None.
//
//****************************************************************************
void SchedulerInit(void){

    //Initialize queue pointers
    psAvailable=&sDeltaQueue[0];
    psSleeping=psAvailable;
    psReady=psAvailable;

}


//****************************************************************************
//
//! Inserts supplied process into the queue.
//!
//! This function iterates the queue starting the sleep pointer and looks for
//! the insert location based on the supplied delay. As this is a delta queue,
//! the delay is decremented by the sleeping process' delta until a the delay
//! is less than that of the sleeping process. This then becomes the insertion
//! point. If there are no sleeping processes then the process is inserted 
//! after the last ready process. If there are no sleeping processes or ready
//! processes then it's inserted and becomes the sole sleeping process.
//!
//! \param pf is the process to execute after the supplied delay.
//! \param ulDelay is the number of ticks to wait before executing the supplied
//! process.
//!
//! \return Process ID of inserted process or zero if unable to insert.
//
//****************************************************************************
unsigned long SchedulerInsert(void (*pf)(void),unsigned long ulDelay){

    static unsigned long ulBeginCount; 
    static unsigned long ulEndCount;   

    ASSERT(psSleeping);
    ASSERT(psAvailable);    

    //Pick off current systick count to calculate execution time
    ulBeginCount=(*((volatile unsigned long *)(NVIC_ST_CURRENT)));

    //CRITICAL SECTION BEGIN
    IntMasterDisable();    

    //Begin iterating at the current sleep pointer
    tDeltaQueueObject * p=(void *)psSleeping;
    tDeltaQueueObject * q;

    //Adjust health indicators
    g_ulTotalProcesses++;
    if(++g_ulCurrentProcesses>g_ulMaximumProcesses)
        g_ulMaximumProcesses=g_ulCurrentProcesses;    

    //Loop through each sleeping process starting at the current
    //sleep pointer and ending when the next pointer of any is 
    //equivalent to the available pointer
    while(p!=psAvailable){

        //If the delay is greater than the current queue item delay,
        //compute the delta for the inserted process and move on
        if(p->ulDelta <= ulDelay){
            ulDelay-=p->ulDelta;   
        }
        //Otherwise, this is the point to insert the new process
        else{   

            //Insert the new process before the current queue entry
            q=FreeEntry();
            ASSERT(q);  //TODO: Exit gracefully when no room
            q->psNext=p;
            q->psPrev=p->psPrev;      

            //Adjust previous and next pointers on each side of the new process
            p->psPrev->psNext=q;
            p->psPrev=q;

            //Set deltas for inserted queue entry and the supplied queue entry 
            p->ulDelta-=ulDelay;
            q->ulDelta=ulDelay;

            //Set the function pointer for the new process and obtain a unique
            //process ID
            q->sProcess.pf=pf;
            q->sProcess.ulPID=GetProcessID();             

            //Adjust the sleep pointer if the insert 
            //happens before it
            if(p==psSleeping)
                psSleeping=q;

            //CRITICAL SECTION END
            IntMasterEnable();       

            //Pick off current systick count to calculate execution time
            ulEndCount=(*((volatile unsigned long *)(NVIC_ST_CURRENT)));

            return q->sProcess.ulPID;
        }

        //Move to next
        p=p->psNext;

    }

    //If here, the list is either empty or the delay is larger than the 
    //sum of all the delays in the queue and so it should be appended 
    //to the end of the queue
    psAvailable->ulDelta = ulDelay;
    psAvailable->sProcess.pf=pf;
    psAvailable->sProcess.ulPID=GetProcessID();      
    q=psAvailable;

    //Increment the available pointer 
    psAvailable=FreeEntry();
    ASSERT(psAvailable);
    psAvailable->psPrev=q;
    q->psNext=psAvailable;
    psAvailable->psNext=NULL;

    //CRITICAL SECTION END
    IntMasterEnable();       

    //Pick off current systick count to calculate execution time
    ulEndCount=(*((volatile unsigned long *)(NVIC_ST_CURRENT)));

    return q->sProcess.ulPID; 
}

//****************************************************************************
//
//! Runs any processes which are ready for execution.
//!
//! This function is usually called in the main loop of the application
//! (anywhere NOT within an interrupt handler). It will iterate the queue
//! and execute any processes which are not sleeping (delta is zero).
//!
//! \return None.
//
//****************************************************************************
void SchedulerRunTask(void){

    tDeltaQueueObject * p;

    ASSERT(psReady);

    //Run tasks until we bump up against the sleeping tasks
    while(psReady!=psSleeping){

        //Adjust health indicators
        g_ulCurrentProcesses--;
        g_ulExecutedProcesses++;

    //Execute task      
    if(psReady->sProcess.pf)
            (psReady->sProcess.pf)();

        p=psReady->psNext;

    //Clear task
    psReady->sProcess.pf=NULL;
        psReady->sProcess.ulPID=0;
    psReady->psNext=NULL;
        psReady->psPrev=NULL;
        psReady->ulDelta=0;

        //Increment ready pointer
    psReady=p;

    }   
}

//****************************************************************************
//
//! Manages sleeping processes in the queue.
//!
//! This function is to be called by the system tick interrupt (at a given 
//! interval). When called, the sleeping tasks' delta is decremented and the
//! sleep pointer is adjusted to point at the next sleeping task (if changed). 
//!
//! \return None.
//
//****************************************************************************
void SchedulerTick(void){

    ASSERT(psSleeping);

    //Increment tick counter
    g_ulSchedulerTickCount++;

    //Adjust sleeping task (never roll past zero)
    if(psSleeping->ulDelta)
        psSleeping->ulDelta--;

    //Push the sleep pointer until a non-zero delta.
    //Multiple processes can expire on one tick.
    while(!psSleeping->ulDelta && psSleeping!=psAvailable){
        psSleeping=psSleeping->psNext;
    }

}

//****************************************************************************
//
//! Searches the queue for a free slot.
//!
//! This function iterates the entire queue looking for an open slot.
//!
//! \return Pointer to the next free DeltaQueueObject or 0 if no free space
//! available.
//
//****************************************************************************
tDeltaQueueObject * FreeEntry(){

    unsigned long i;

    //Iterate entire queue
    for(i=0; i<QUEUE_MAX; i++){

        //Look for a free slot by examining the contents
        if(!(sDeltaQueue[i].psNext) && !(sDeltaQueue[i].psPrev) && !(sDeltaQueue[i].sProcess.ulPID) && !(sDeltaQueue[i].ulDelta) && !(sDeltaQueue[i].sProcess.pf))
            return &sDeltaQueue[i];
    }

    //If we are here, there are no free spots in the queue
    ASSERT(1);
    return NULL;

}

//****************************************************************************
//
//! Produces a unique process ID.
//!
//! This function simply returns the next PID available.
//!
//! \todo Keep a list of unexpired PIDs so that it can be guaranteed unique
//! must have before creating remove function
//!
//! \return A unique process ID.
//
//****************************************************************************
unsigned long GetProcessID(void){

    //PID can never be zero, catch this case
    if(!g_ulPID)
        g_ulPID=1;    

    return g_ulPID++;
}

Идея заключается в том, что существует статический буфер, который заполнен объектами дельта-очереди.Каждый объект дельта-очереди имеет указатели на предыдущий / следующий объект дельта-очереди, относительную задержку к предыдущей задаче и некоторую информацию о процессе (идентификатор процесса и указатель на функцию).Есть 3 глобальных указателя, указатель готовности, указатель сна и доступный указатель.Указатель готовности указывает на список задач, которые должны быть выполнены.Указатель сна на список задач, которые ... хорошо ... спят и не готовы к выполнению.Доступный указатель в основном указывает на конец, где есть доступный слот.Эти указатели только двигаться вперед.Когда один сталкивается с другим, эта «очередь» пуста.Например, когда указатель готовности равен указателю сна, готовых задач нет.

Итак, пример может выглядеть примерно так:

Изначально указатели выглядят так:

Pointers    Slot #    Delta  
RP,SP,AP -> Slot 1    0

Вставляется задача с задержкой в ​​50 мс и очередьтеперь выглядит как ...

Pointers    Slot #    Delta  
RP,SP    -> Slot 1    50
AP       -> Slot 2    0

Проходит несколько тиков и вставляется еще одно задание с задержкой в ​​10 мс ...

Pointers    Slot #    Delta  
RP,SP    -> Slot 3    10
         -> Slot 1    38
AP       -> Slot 2    0

Проходит двадцать тиков, и мы получаем...

Pointers    Slot #    Delta  
RP       -> Slot 3    0
SP       -> Slot 1    18
AP       -> Slot 2    0

SchedulerTick() вызывается прерыванием с помощью джойстика со скоростью 1 мс.SchedulerRun() вызывается из основного цикла приложения (когда он больше ничего не делает), так что прерывание моей ручки очень короткое.SchedulerInsert() вызывается по мере необходимости для планирования задачи.

Итак, вот куда я направлялся с кодом выше.Теперь мои проблемы ...

1) Я указал psSleeping как энергозависимый указатель, потому что он был изменен в SchedulerTick().Я уверен, что это необходимо, но правильно ли мое использование?Указатель объявлен как volatile или является тем, на который он указывает, как volatile.

2) Функции SchedulerTick() и SchedulerRun() довольно просты, но SchedulerInsert() стал довольно грязным.Большая часть беспорядка происходит из-за того, что вставленная задача может быть помещена перед указателем сна, означающим, что SchedulerTick() больше не записывает в него исключительно записи, и поэтому я должен отключить прерывания, пока я делаю это.Более того, кажется, что есть некоторая ошибка во вставке (предположительно), которая заставляет SchedulerTick() остановиться в цикле while, потому что psAvailable никогда не достигается.Эта ошибка встречается очень редко ... Я не могу повторить ее при переходе.Возможно, это связано с изменчивой декларацией?

Есть мысли?

Answer 1

Я предлагаю вам пересмотреть, действительно ли вам нужно для выполнения какой-либо фактической обработки списка из обработчика прерываний.

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

Например, что-то вроде этих строк:

// Only bumb the tick counter from within interrupts
void SchedulerTick(void) {
    g_ulSchedulerTickCount++;
}

// Use the number of elapsed ticks since the last call wake up processes for execution.
// Returns the first task that's still sleeping
tDeltaQueueObject *SchedulerStillSleeping(void) {
    static unsigned long lastTick;
    unsigned long currentTick = g_ulSchedulerTickCount;
    signed long elapsedTicks = currentTick - lastTick;
    lastTick = currentTick;

    for(; psSleeping != psAvailable; psSleeping = psSleeping->psNext) {
        if(psSleeping->ulDelta > elapsedTicks)
            psSleeping->ulDelta -= elapsedTicks;
            break;
        }
        elapsedTicks -= psSleeping->ulDelta;
        psSleeping->ulDelta = 0;
    }
    return psSleeping;
}

// Reassess the set of sleeping processes by calling the StillSleeping function anywhere
// you would previously have polled the list head
void SchedulerRunTask(void) {
    while(psReady != SchedulerStillSleeping()) {
        .
        .
        .
    }
}

unsigned long SchedulerInsert(...) {
    .
    .
    .
    tDeltaQueueObject *p = SchedulerStillSleeping();
    while(p != psAvailable) {
        .
        .
        .
    }
}