デルタキュー - 組み込みスケジューラ

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 

タスクは、50ミリ秒の遅延と、今のように見えるキューに挿入します。..

が最初ポインタがそうのように見える...：

ので、例は次のようになります

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

数ティックで行くと別のタスクが10ミリ秒の遅延で挿入されている...

0123二十その後で行くと我々が持っているダニ

...

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

SchedulerTick()は1ミリ秒の速度での割り込みのSysTickによって呼び出されます。 SchedulerRun()は、アプリケーションのメインループから呼び出されます（ は何も実行していません）ので、私のsysick割り込みは非常に短くなります。 SchedulerInsert()は、タスクをスケジュールするために必要に応じて呼び出されます。

だから私は上記のコードを読んでいました。さて、私の問題は...

1）SchedulerTick()で変更されたため、psSleepingを揮発性ポインタとして指定しました。私はそれが必要だと確信していますが、私の使用法は正しいですか？ポインタはvolatile宣言されているか、volatile宣言されているものです。

2）SchedulerTick()とSchedulerRun()の機能はかなり単純ですが、SchedulerInsert()は非常に面倒です。ほとんどの混乱は、挿入されたタスクがスリープポインタの前に置かれるという事実によるものです。つまり、SchedulerTick()はもはや排他的に書き込みをしていないので、その間に割り込みを無効にする必要があります。さらに、psAvailableに決して届かないので、SchedulerTick()がwhileループで停止するようになるインサート（おそらく）にいくつかのバグがあるようです。このバグはごくまれにしか発生しません...私はそれを繰り返すことができません。おそらくそれは激しい宣言に関係しているでしょうか？

どのような考えですか？

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