EDF extended by Deadline inversion handling

The Deadline inversion is solved by PIP already embedded in the RTEMS.
It was necessary to pull out another function for the pluggable
infrastructure (deadline comparison) in order to solve this issue.

The scheduler is now capable of handling two policies simultaneously
(deadlines and priorities) while priorities are always considered less
important, thus enqueued as very far deadlines.

Not tested. A lot of bugs will definitely show up.

diff --git a/src/edf/edf_types.h b/src/edf/edf_types.h
index e30080eebba16790ab0e08cb17a01b42548ddd6a..edb959fcd4687beef36cee56e67e76f13435d409 100644 (file)
--- a/src/edf/edf_types.h
+++ b/src/edf/edf_types.h
@@ -12,7 +12,21 @@ extern "C" {
 
 typedef uint32_t Deadline_Control;
 
-#define ABS_DEADLINE_MAXIMUM 0xffffffff
+#define EDF_BYTES_FOR_TIME 4   // It is uint32_t
+//#define EDF_TIME_RANGE 0xffffffff
+
+#define EDF_ABS_DEADLINE_MAX ((1 << (EDF_BYTES_FOR_TIME*4)) - 1)
+#define EDF_PRIORITY_MAX 255
+
+/** 
+ * The scheduler has two separete policies for for tasks using deadlines 
+ * tasks using priorities. The priority driven tasks are always scheduled as less 
+ * important than the deadline driven ones.
+ * We can distinguish them by looking at the MSB of their priority. Priority diven
+ * have 1 and deadline driven have 0.
+ */
+#define EDF_HYBRID_MASK (1 << (EDF_BYTES_FOR_TIME*8 - 1)) //This is MSB
+
 
 typedef enum node_color_struct { N_RED, N_BLACK } Node_Color;
 typedef Thread_Control EDF_Node;

diff --git a/src/edf/rbtree.c b/src/edf/rbtree.c
index edbd562ffa55450e1b98cfb13395e15f90968cf0..fed9635c425c96eabdc07deeb4b67663b46df43f 100644 (file)
--- a/src/edf/rbtree.c
+++ b/src/edf/rbtree.c
@@ -1,5 +1,5 @@
 #include <rtems/score/thread.h>
-#include "edf_types.h"
+#include "scheduler_edf.h"
 #include "rbtree.h"
 
 
@@ -65,7 +65,7 @@ void _RBT_Insert(
    while (child) 
    {
            parent = child;
-           child = ( SI(node)->abs_deadline < SI(child)->abs_deadline ) \
+           child = ( edf_priority_is_lower(node->current_priority,child->current_priority) ) \
                   ? SI(child)->left : SI(child)->right;
    }
    
@@ -76,7 +76,7 @@ void _RBT_Insert(
 
    if (parent) 
    {
-          if ( SI(node)->abs_deadline < SI(parent)->abs_deadline ) 
+          if ( edf_priority_is_lower(node->current_priority, parent->current_priority) ) 
           { 
                   SI(parent)->left = node;
                   if ( parent == chain->first ) chain->first = node; 
@@ -222,7 +222,7 @@ static void _RBT_Delete_Fixup(
                                if (!SI(other)->left ||
                                    SI(SI(other)->left)->color == N_BLACK)
                                {
-                                       register struct rb_node *o_right;
+                                       //register struct rb_node *o_right;
                                        if ((o_child = SI(other)->right))
                                                SI(o_child)->color = N_BLACK;
                                        SI(other)->color = N_RED;
@@ -340,25 +340,25 @@ int _RBT_Has_only_one_node(
 )
 {
    if ( !chain->root ) return 0;
-   return ( ((SI(chain->root)->left == SI(chain->root)->right) == NULL) );
+   return (( (SI(chain->root)->left == NULL) && (SI(chain->root)->right == NULL) ));
 }
 
 /*
- * Returns node with specific absolute deadline
+ * Returns node with specific priority
  */
  
 EDF_Node* _RBT_Search(
    EDF_Chain_Control *chain,
-   Deadline_Control absdeadline
+   Priority_Control prio
 )
 {
    EDF_Node *current;
     
    current = chain->root;
    while (current != NULL) {
-       if ( absdeadline == SI(current)->abs_deadline) return current;
+       if ( prio == current->current_priority) return current;
        else { 
-           current = (absdeadline < SI(current)->abs_deadline) ?
+           current = (edf_priority_is_higher(prio,current->current_priority)) ?
                SI(current)->left : SI(current)->right;
        }
    }

diff --git a/src/edf/scheduler_edf.c b/src/edf/scheduler_edf.c
index 76eb47827d14dc3382b03839c8891bbb73cb8ee6..8212a90621a0489e863f2c73bed2f2e0c8709994 100644 (file)
--- a/src/edf/scheduler_edf.c
+++ b/src/edf/scheduler_edf.c
@@ -6,8 +6,37 @@
 #include <rtems/score/watchdog.h>
 #include <rtems/score/wkspace.h>
 #include <rtems/score/percpu.h>
+#include <rtems/score/thread.h>
+#include <stdint.h>
 
 
+/** 
+ * The threads wanted to be served on a priority base will be assigned the very 
+ * longest deadlines.
+ */ 
+#define edf_initial_priority_shift(init_prio)  \
+       (init_prio + EDF_ABS_DEADLINE_MAX + 1)
+
+void edf_next_period(Thread_Control *the_thread) {
+       RBT_Node *node = (RBT_Node*)the_thread->scheduler_info; 
+       the_thread->real_priority = the_thread->current_priority = (_Watchdog_Ticks_since_boot + node->rel_deadline) % EDF_HYBRID_MASK;
+       node->abs_deadline = the_thread->current_priority;      
+}
+
+
+
+int _Scheduler_edf_Priority_compare (Priority_Control p1, Priority_Control p2) {
+       uint32_t time = _Watchdog_Ticks_since_boot;
+       //correct priorities
+       if (p1 < EDF_HYBRID_MASK)
+               p1 = (p1 - time) % EDF_HYBRID_MASK;
+       if (p2 < EDF_HYBRID_MASK)
+               p2 = (p2 - time) % EDF_HYBRID_MASK;
+       if (p1 > p2) return -1;
+       else if (p1 < p2) return 1;
+       else return 0;
+}
+
 
 void _Scheduler_edf_Initialize(void) {
        // initialize the RB tree
@@ -39,9 +68,10 @@ void * _Scheduler_edf_Allocate(  Thread_Control      *the_thread) {
        RBT_Node *schinfo;
        sched = _Workspace_Allocate (sizeof(RBT_Node));
        the_thread->scheduler_info = (RBT_Node *) sched;
+       the_thread->real_priority = the_thread->current_priority = edf_initial_priority_shift(the_thread->real_priority);
        
        schinfo = (RBT_Node *)(the_thread->scheduler_info);
-       schinfo->rel_deadline = the_thread->real_priority;
+       schinfo->rel_deadline = 0;      // This has to be negotiated afterwards
        schinfo->abs_deadline = 0;
        schinfo->left = NULL;
        schinfo->right = NULL;
@@ -56,11 +86,18 @@ void _Scheduler_edf_Free(  Thread_Control      *the_thread) {
 }
 
 void _Scheduler_edf_Update(  Thread_Control      *the_thread) {
-       // after a priority changes, just extract and insert again
-       //in case it is in the tree
-//     EDF_Chain_Control* chain = ((RBT_Node*)the_thread->scheduler_info)->ready_chain;
-//     _RBT_Extract(chain, the_thread); 
-//     _RBT_Insert(chain, the_thread); // preserve the abs_deadline
+       // Update deadlines for deadline driven tasks
+       if (!(the_thread->current_priority && EDF_HYBRID_MASK))
+               ((RBT_Node*)the_thread->scheduler_info)->abs_deadline = the_thread->current_priority;   
+       else
+               ((RBT_Node*)the_thread->scheduler_info)->abs_deadline = 0;      
+       _Scheduler_edf_Extract(the_thread); 
+       _Scheduler_edf_Enqueue(the_thread); 
+       if ( the_thread->current_priority < _Thread_Heir->current_priority ) {
+               _Thread_Heir = the_thread;
+               if ( _Thread_Executing->is_preemptible || the_thread->current_priority == 0 )
+                       _Thread_Dispatch_necessary = true;      
+       }
 }
 
 void _Scheduler_edf_Unblock(  Thread_Control    *the_thread ) {
@@ -116,13 +153,8 @@ void _Scheduler_edf_Yield( void ) {
 void _Scheduler_edf_Enqueue(  Thread_Control    *the_thread) {
        RBT_Node *node = (RBT_Node*)the_thread->scheduler_info;
        EDF_Chain_Control *chain = node->ready_chain;
-       //FIXME: instead of this hack for idle task, make up a general rule
-       if (node->rel_deadline == 255) 
-               node->abs_deadline = ABS_DEADLINE_MAXIMUM;      
-       else
-               node->abs_deadline = _Watchdog_Ticks_since_boot + node->rel_deadline;
-       _RBT_Insert(chain,the_thread);
 
+       _RBT_Insert(chain,the_thread);
 }
 
 void _Scheduler_edf_Enqueue_first(  Thread_Control    *the_thread) {

diff --git a/src/edf/scheduler_edf.h b/src/edf/scheduler_edf.h
index 02e4d2a3b339e4685c17b55334db4eff9f8730ec..f67140a99e4f3857d684b18112b713baf7b59845 100644 (file)
--- a/src/edf/scheduler_edf.h
+++ b/src/edf/scheduler_edf.h
@@ -10,6 +10,13 @@
 // keeps the ready queue for EDF
 EDF_Chain_Control _Thread_Ready_EDF_chain;
 
+/**
+ * This routine shifts a deadline for the next period of a periodical task execution.
+ */
+void edf_next_period(Thread_Control *the_thread);
+
+
+/// Pluggable scheduler callback functions
 #define SCHEDULER_EDF_ENTRY_POINTS \
        { \
        _Scheduler_edf_Initialize,    /* initialize entry point */ \
@@ -22,7 +29,8 @@ EDF_Chain_Control _Thread_Ready_EDF_chain;
        _Scheduler_edf_Update,        /* update entry point */ \
        _Scheduler_edf_Enqueue,       /* enqueue entry point */ \
        _Scheduler_edf_Enqueue_first, /* enqueue_first entry point */ \
-       _Scheduler_edf_Extract        /* extract entry point */ \
+       _Scheduler_edf_Extract,        /* extract entry point */ \
+       _Scheduler_edf_Priority_compare /* compares two priorities */ \
        }
 
 
@@ -135,6 +143,18 @@ void _Scheduler_edf_Extract(
   Thread_Control     *the_thread
 );
 
+/**
+ * Compares absolute dedlines of threads while taking into account time overflow.
+ * Deadline is later.
+ * @return 1 for p1 > p2; 0 for p1 == p2; -1 for p1 < p2
+ */
+inline int _Scheduler_edf_Priority_compare (
+  Priority_Control p1, 
+  Priority_Control p2
+);
 
+#define edf_priority_is_lower(p1, p2) ( _Scheduler_edf_Priority_compare(p1, p2) == 1)
+#define edf_priority_is_higher(p1, p2) ( _Scheduler_edf_Priority_compare(p1, p2) == -1)
+#define edf_priority_is_equal(p1, p2) ( !_Scheduler_edf_Priority_compare(p1, p2) )
 
 #endif /*_SCHEDULER_EDF_H*/
\ No newline at end of file