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.
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;
#include <rtems/score/thread.h>
-#include "edf_types.h"
+#include "scheduler_edf.h"
#include "rbtree.h"
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;
}
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;
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;
)
{
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;
}
}
#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
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;
}
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 ) {
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) {
// 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 */ \
_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 */ \
}
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