델타 큐 - 임베디드 스케줄러

Question

작은 Cortex-M3에서 간단한 델타 큐를 구현하여 향후 몇 가지 작업을 스케쥴하려고합니다. 나는 무언가를 만들었지 만, 그다지 우아한 (나는 종종 코드를 쓰지 않는다)라고 생각하지 않는다. 휘발성 지정자의 부정확 한 사용으로 인해 아마 같은 약간 희박한 것으로 보입니다.

#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++; 
} 

내가 무엇을 뒤에 아이디어는 델타 큐 오브젝트와 을 가득 정적 버퍼가 존재합니다. 각 델타 큐 객체는 이전/다음 델타 큐 객체에 대한 포인터, 이전 작업에 대한 상대적 지연 및 일부 프로세스 정보 (프로세스 ID 및 함수 포인터)를 가지고 있습니다. 3 개의 글로벌 포인터, 준비 포인터, 휴면 포인터 및 사용 가능한 포인터가 있습니다. 준비 포인터는 실행할 작업 목록을 가리 킵니다. 잠자기 ... 잠들고 준비가되지 않은 작업 목록에 대한 포인터 을 실행합니다. 사용 가능한 포인터는 기본적으로 끝 지점을 가리키며 여기서 은 사용 가능한 슬롯입니다. 이 포인터는 앞으로 만 이동합니다. 하나가 을 다른 것으로 밀어 붙이면 '서브 대기열'이 비어 있습니다. 예를 들어 준비된 포인터가 휴면 포인터와 같으면 준비 작업이 없습니다.

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

작업은 50ms의 지연과 지금과 같은 큐에 삽입 ..

이 처음 포인터 그래서 같이 ... :

그래서, 예를 들어 같은 것을 보일 수 있습니다

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

몇 진드기에 의해 이동하고 다른 작업은 10ms의 지연 삽입 ...

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()은이 1ms의 속도로 systick 인터럽트에 의해 호출됩니다. SchedulerRun()은 응용 프로그램의 주 루프에서 호출됩니다 ( 이 아닌 경우). 내 시스템 트레이스 인터럽트가 매우 짧습니다. SchedulerInsert()은 작업을 예약하는 데 필요한만큼 호출됩니다.

그래서 내가 위의 코드로 향하고 있습니다. 자, 내 문제 ...

1) SchedulerTick()에서 수정 되었기 때문에 psSleeping을 휘발성 포인터로 지정했습니다. 나는 그것이 필요하다고 확신하지만 나의 사용법은 정확합니까? 포인터가 휘발성으로 선언되었거나 휘발성으로 선언 된 것입니다.

2) SchedulerTick() 및 SchedulerRun() 함수는 매우 직선이지만, SchedulerInsert()은 상당히 엉망이되었습니다. 난장판의 대부분은 삽입 된 작업이 수면 포인터 앞에 놓일 수 있다는 사실에 기인합니다. 즉, SchedulerTick()은 더 이상 독점적으로 쓰는 것이 아니므로 그렇게 할 때 인터럽트를 비활성화해야합니다. 또한 psAvailable에 절대로 도달하지 못하기 때문에 while 루프에서 SchedulerTick()이 중단 될 수있는 인서트 (아마도)에 버그가있는 것 같습니다. 이 버그는 매우 드물게 발생합니다 ... 나는 단계별로 진행하는 동안 그것을 반복 할 수 없습니다.휘발성 선언과 관련이있는 것일까?

의견이 있으십니까?

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) { 
     . 
     . 
     . 
    } 
}