Index: cpukit/score/include/rtems/score/scheduleredf.h
===================================================================
--- cpukit/score/include/rtems/score/scheduleredf.h	(revision 9a78f8a5076687a8744991998ee6119f87db12a8)
+++ cpukit/score/include/rtems/score/scheduleredf.h	(revision 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f)
@@ -36,5 +36,5 @@
 /**@{*/
 
-#define SCHEDULER_EDF_MAXIMUM_PRIORITY 255
+#define SCHEDULER_EDF_MAXIMUM_PRIORITY 0x7fffffff
 
 /**
@@ -83,16 +83,4 @@
 
 /**
- * @typedef Scheduler_EDF_Queue_state
- *
- * This enumeration distiguishes state of a thread with respect to the
- * ready queue.
- */
-typedef enum {
-  SCHEDULER_EDF_QUEUE_STATE_NOT_PRESENTLY,
-  SCHEDULER_EDF_QUEUE_STATE_YES,
-  SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN
-} Scheduler_EDF_Queue_state;
-
-/**
  * @brief Scheduler node specialization for EDF schedulers.
  */
@@ -111,8 +99,15 @@
    */
   RBTree_Node Node;
-  /**
-   * State of the thread with respect to ready queue.
-   */
-  Scheduler_EDF_Queue_state queue_state;
+
+  /**
+   * @brief The thread priority used by this scheduler instance in case no job
+   * is released.
+   */
+  Priority_Control background_priority;
+
+  /**
+   * @brief The thread priority currently used by this scheduler instance.
+   */
+  Priority_Control current_priority;
 } Scheduler_EDF_Node;
 
Index: cpukit/score/include/rtems/score/scheduleredfimpl.h
===================================================================
--- cpukit/score/include/rtems/score/scheduleredfimpl.h	(revision 9a78f8a5076687a8744991998ee6119f87db12a8)
+++ cpukit/score/include/rtems/score/scheduleredfimpl.h	(revision 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f)
@@ -45,42 +45,90 @@
 }
 
-int _Scheduler_EDF_Priority_compare (
-  Priority_Control p1,
-  Priority_Control p2
-);
+RTEMS_INLINE_ROUTINE bool _Scheduler_EDF_Less(
+  const void        *left,
+  const RBTree_Node *right
+)
+{
+  const Priority_Control   *the_left;
+  const Scheduler_EDF_Node *the_right;
+  Priority_Control          prio_left;
+  Priority_Control          prio_right;
 
-RBTree_Compare_result _Scheduler_EDF_Compare(
-  const RBTree_Node* n1,
-  const RBTree_Node* n2
-);
+  the_left = left;
+  the_right = RTEMS_CONTAINER_OF( right, Scheduler_EDF_Node, Node );
+
+  prio_left = *the_left;
+  prio_right = the_right->current_priority;
+
+  return prio_left < prio_right;
+}
+
+RTEMS_INLINE_ROUTINE bool _Scheduler_EDF_Less_or_equal(
+  const void        *left,
+  const RBTree_Node *right
+)
+{
+  const Priority_Control   *the_left;
+  const Scheduler_EDF_Node *the_right;
+  Priority_Control          prio_left;
+  Priority_Control          prio_right;
+
+  the_left = left;
+  the_right = RTEMS_CONTAINER_OF( right, Scheduler_EDF_Node, Node );
+
+  prio_left = *the_left;
+  prio_right = the_right->current_priority;
+
+  return prio_left <= prio_right;
+}
 
 RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Enqueue(
+  Scheduler_EDF_Context *context,
+  Scheduler_EDF_Node    *node,
+  Priority_Control       current_priority
+)
+{
+  _RBTree_Insert_inline(
+    &context->Ready,
+    &node->Node,
+    &current_priority,
+    _Scheduler_EDF_Less
+  );
+}
+
+RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Enqueue_first(
+  Scheduler_EDF_Context *context,
+  Scheduler_EDF_Node    *node,
+  Priority_Control       current_priority
+)
+{
+  _RBTree_Insert_inline(
+    &context->Ready,
+    &node->Node,
+    &current_priority,
+    _Scheduler_EDF_Less_or_equal
+  );
+}
+
+RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Extract(
+  Scheduler_EDF_Context *context,
+  Scheduler_EDF_Node    *node
+)
+{
+  _RBTree_Extract( &context->Ready, &node->Node );
+}
+
+RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Extract_body(
   const Scheduler_Control *scheduler,
   Thread_Control          *the_thread
 )
 {
-  Scheduler_EDF_Context *context =
-    _Scheduler_EDF_Get_context( scheduler );
-  Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
+  Scheduler_EDF_Context *context;
+  Scheduler_EDF_Node    *node;
 
-  _RBTree_Insert(
-    &context->Ready,
-    &node->Node,
-    _Scheduler_EDF_Compare,
-    false
-  );
-  node->queue_state = SCHEDULER_EDF_QUEUE_STATE_YES;
-}
+  context = _Scheduler_EDF_Get_context( scheduler );
+  node = _Scheduler_EDF_Thread_get_node( the_thread );
 
-RTEMS_INLINE_ROUTINE void _Scheduler_EDF_Extract(
-  const Scheduler_Control *scheduler,
-  Thread_Control          *the_thread
-)
-{
-  Scheduler_EDF_Context *context =
-    _Scheduler_EDF_Get_context( scheduler );
-  Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
-
-  _RBTree_Extract( &context->Ready, &node->Node );
+  _Scheduler_EDF_Extract( context, node );
 }
 
@@ -91,14 +139,15 @@
 )
 {
-  Scheduler_EDF_Context *context =
-    _Scheduler_EDF_Get_context( scheduler );
-  RBTree_Node *first = _RBTree_Minimum( &context->Ready );
-  Scheduler_EDF_Node *node =
-    RTEMS_CONTAINER_OF( first, Scheduler_EDF_Node, Node );
-  Thread_Control *heir = node->thread;
+  Scheduler_EDF_Context *context;
+  RBTree_Node           *first;
+  Scheduler_EDF_Node    *node;
 
-  ( void ) the_thread;
+  (void) the_thread;
 
-  _Scheduler_Update_heir( heir, force_dispatch );
+  context = _Scheduler_EDF_Get_context( scheduler );
+  first = _RBTree_Minimum( &context->Ready );
+  node = RTEMS_CONTAINER_OF( first, Scheduler_EDF_Node, Node );
+
+  _Scheduler_Update_heir( node->thread, force_dispatch );
 }
 
Index: cpukit/score/src/schedulercbsnodeinit.c
===================================================================
--- cpukit/score/src/schedulercbsnodeinit.c	(revision 9a78f8a5076687a8744991998ee6119f87db12a8)
+++ cpukit/score/src/schedulercbsnodeinit.c	(revision 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f)
@@ -26,12 +26,9 @@
 )
 {
-  Scheduler_CBS_Node *node = _Scheduler_CBS_Thread_get_node( the_thread );
+  Scheduler_CBS_Node *node;
 
-  (void) scheduler;
+  _Scheduler_EDF_Node_initialize( scheduler, the_thread );
 
-  _Scheduler_Node_do_initialize( &node->Base.Base, the_thread );
-
-  node->Base.thread = the_thread;
-  node->Base.queue_state = SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN;
+  node = _Scheduler_CBS_Thread_get_node( the_thread );
   node->cbs_server = NULL;
 }
Index: cpukit/score/src/schedulercbsunblock.c
===================================================================
--- cpukit/score/src/schedulercbsunblock.c	(revision 9a78f8a5076687a8744991998ee6119f87db12a8)
+++ cpukit/score/src/schedulercbsunblock.c	(revision 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f)
@@ -31,10 +31,13 @@
 )
 {
-  Scheduler_CBS_Node   *node = _Scheduler_CBS_Thread_get_node( the_thread );
-  Scheduler_CBS_Server *serv_info = node->cbs_server;
-  Priority_Control      new_priority;
+  Scheduler_EDF_Context *context;
+  Scheduler_CBS_Node    *node;
+  Scheduler_CBS_Server  *serv_info;
+  Priority_Control       priority;
 
-  _Scheduler_EDF_Enqueue( scheduler, the_thread );
-  /* TODO: flash critical section? */
+  context = _Scheduler_EDF_Get_context( scheduler );
+  node = _Scheduler_CBS_Thread_get_node( the_thread );
+  serv_info = node->cbs_server;
+  priority = node->Base.current_priority;
 
   /*
@@ -44,26 +47,27 @@
    * miss of another task.
    */
-  if (serv_info) {
+  if ( serv_info != NULL && ( priority & SCHEDULER_EDF_PRIO_MSB ) == 0 ) {
     time_t deadline = serv_info->parameters.deadline;
     time_t budget = serv_info->parameters.budget;
-    time_t deadline_left = the_thread->cpu_time_budget;
-    time_t budget_left = the_thread->real_priority -
-                           _Watchdog_Ticks_since_boot;
+    uint32_t deadline_left = the_thread->cpu_time_budget;
+    Priority_Control budget_left = priority - _Watchdog_Ticks_since_boot;
 
-    if ( deadline*budget_left > budget*deadline_left ) {
+    if ( deadline * budget_left > budget * deadline_left ) {
       /* Put late unblocked task to background until the end of period. */
-      new_priority = the_thread->Start.initial_priority;
-      the_thread->real_priority = new_priority;
-      if ( the_thread->current_priority != new_priority ) {
-        the_thread->current_priority = new_priority;
-        _Scheduler_EDF_Change_priority(
-          scheduler,
-          the_thread,
-          new_priority,
-          true
-        );
+
+      priority = node->Base.background_priority;
+      the_thread->real_priority = priority;
+
+      if (
+        _Thread_Priority_less_than( the_thread->current_priority, priority )
+          || !_Thread_Owns_resources( the_thread )
+      ) {
+        the_thread->current_priority = priority;
       }
     }
   }
+
+  node->Base.current_priority = priority;
+  _Scheduler_EDF_Enqueue( context, &node->Base, priority );
 
   /*
@@ -79,14 +83,6 @@
    *    a pseudo-ISR system task, we need to do a context switch.
    */
-  if (
-    _Scheduler_EDF_Priority_compare(
-      the_thread->current_priority,
-      _Thread_Heir->current_priority
-    ) == 1 
-  ) {
-    _Scheduler_Update_heir(
-      the_thread,
-      the_thread->current_priority == PRIORITY_PSEUDO_ISR
-    );
+  if ( priority < _Thread_Heir->current_priority ) {
+    _Scheduler_Update_heir( the_thread, priority == PRIORITY_PSEUDO_ISR );
   }
 
Index: cpukit/score/src/scheduleredf.c
===================================================================
--- cpukit/score/src/scheduleredf.c	(revision 9a78f8a5076687a8744991998ee6119f87db12a8)
+++ cpukit/score/src/scheduleredf.c	(revision 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f)
@@ -21,45 +21,4 @@
 #include <rtems/score/scheduleredfimpl.h>
 
-int _Scheduler_EDF_Priority_compare (
-  Priority_Control p1,
-  Priority_Control p2
-)
-{
-  Watchdog_Interval time = _Watchdog_Ticks_since_boot;
-
-  /*
-   * Reorder priorities to separate deadline driven and background tasks.
-   *
-   * The background tasks have p1 or p2 > SCHEDULER_EDF_PRIO_MSB.
-   * The deadline driven tasks need to have subtracted current time in order
-   * to see which deadline is closer wrt. current time.
-   */
-  if (!(p1 & SCHEDULER_EDF_PRIO_MSB))
-    p1 = (p1 - time) & ~SCHEDULER_EDF_PRIO_MSB;
-  if (!(p2 & SCHEDULER_EDF_PRIO_MSB))
-    p2 = (p2 - time) & ~SCHEDULER_EDF_PRIO_MSB;
-
-  return ((p1<p2) - (p1>p2));
-}
-
-RBTree_Compare_result _Scheduler_EDF_Compare(
-  const RBTree_Node* n1,
-  const RBTree_Node* n2
-)
-{
-  Scheduler_EDF_Node *edf1 =
-    RTEMS_CONTAINER_OF( n1, Scheduler_EDF_Node, Node );
-  Scheduler_EDF_Node *edf2 =
-    RTEMS_CONTAINER_OF( n2, Scheduler_EDF_Node, Node );
-  Priority_Control value1 = edf1->thread->current_priority;
-  Priority_Control value2 = edf2->thread->current_priority;
-
-  /*
-   * This function compares only numbers for the red-black tree,
-   * but priorities have an opposite sense.
-   */
-  return (-1)*_Scheduler_EDF_Priority_compare(value1, value2);
-}
-
 void _Scheduler_EDF_Initialize( const Scheduler_Control *scheduler )
 {
Index: cpukit/score/src/scheduleredfblock.c
===================================================================
--- cpukit/score/src/scheduleredfblock.c	(revision 9a78f8a5076687a8744991998ee6119f87db12a8)
+++ cpukit/score/src/scheduleredfblock.c	(revision 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f)
@@ -30,5 +30,5 @@
     scheduler,
     the_thread,
-    _Scheduler_EDF_Extract,
+    _Scheduler_EDF_Extract_body,
     _Scheduler_EDF_Schedule_body
   );
Index: cpukit/score/src/scheduleredfchangepriority.c
===================================================================
--- cpukit/score/src/scheduleredfchangepriority.c	(revision 9a78f8a5076687a8744991998ee6119f87db12a8)
+++ cpukit/score/src/scheduleredfchangepriority.c	(revision 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f)
@@ -44,15 +44,23 @@
 )
 {
-  Scheduler_EDF_Context *context =
-    _Scheduler_EDF_Get_context( scheduler );
-  Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
+  Scheduler_EDF_Context *context;
+  Scheduler_EDF_Node    *node;
 
-  _RBTree_Extract( &context->Ready, &node->Node );
-  _RBTree_Insert(
-    &context->Ready,
-    &node->Node,
-    _Scheduler_EDF_Compare,
-    false
-  );
+  context = _Scheduler_EDF_Get_context( scheduler );
+  node = _Scheduler_EDF_Thread_get_node( the_thread );
+
+  if ( ( new_priority & SCHEDULER_EDF_PRIO_MSB ) != 0 ) {
+    node->background_priority = new_priority;
+  }
+
+  node->current_priority = new_priority;
+
+  _Scheduler_EDF_Extract( context, node );
+
+  if ( prepend_it ) {
+    _Scheduler_EDF_Enqueue_first( context, node, new_priority );
+  } else {
+    _Scheduler_EDF_Enqueue( context, node, new_priority );
+  }
 
   _Scheduler_EDF_Schedule_body( scheduler, the_thread, false );
Index: cpukit/score/src/scheduleredfnodeinit.c
===================================================================
--- cpukit/score/src/scheduleredfnodeinit.c	(revision 9a78f8a5076687a8744991998ee6119f87db12a8)
+++ cpukit/score/src/scheduleredfnodeinit.c	(revision 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f)
@@ -33,4 +33,3 @@
 
   node->thread = the_thread;
-  node->queue_state = SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN;
 }
Index: cpukit/score/src/scheduleredfreleasejob.c
===================================================================
--- cpukit/score/src/scheduleredfreleasejob.c	(revision 9a78f8a5076687a8744991998ee6119f87db12a8)
+++ cpukit/score/src/scheduleredfreleasejob.c	(revision 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f)
@@ -19,7 +19,31 @@
 #endif
 
-#include <rtems/score/scheduleredf.h>
-#include <rtems/score/threadimpl.h>
-#include <rtems/score/watchdogimpl.h>
+#include <rtems/score/scheduleredfimpl.h>
+
+static bool _Scheduler_EDF_Priority_filter(
+  Thread_Control   *the_thread,
+  Priority_Control *new_priority_p,
+  void             *arg
+)
+{
+  Scheduler_EDF_Node *node;
+  Priority_Control    current_priority;
+  Priority_Control    new_priority;
+
+  node = _Scheduler_EDF_Thread_get_node( the_thread );
+
+  current_priority = the_thread->current_priority;
+  new_priority = *new_priority_p;
+
+  if ( new_priority == 0 ) {
+    new_priority = node->background_priority;
+  }
+
+  node->current_priority = new_priority;
+  the_thread->real_priority = new_priority;
+
+  return _Thread_Priority_less_than( current_priority, new_priority )
+    || !_Thread_Owns_resources( the_thread );
+}
 
 void _Scheduler_EDF_Release_job(
@@ -29,18 +53,10 @@
 )
 {
-  Priority_Control new_priority;
-  Priority_Control unused;
-
-  (void) scheduler;
-
-  if (deadline) {
-    /* Initializing or shifting deadline. */
-    new_priority = (uint32_t) deadline & ~SCHEDULER_EDF_PRIO_MSB;
-  }
-  else {
-    /* Switch back to background priority. */
-    new_priority = the_thread->Start.initial_priority;
-  }
-
-  _Thread_Set_priority( the_thread, new_priority, &unused, true );
+  _Thread_Change_priority(
+    the_thread,
+    (Priority_Control) deadline,
+    NULL,
+    _Scheduler_EDF_Priority_filter,
+    true
+  );
 }
Index: cpukit/score/src/scheduleredfunblock.c
===================================================================
--- cpukit/score/src/scheduleredfunblock.c	(revision 9a78f8a5076687a8744991998ee6119f87db12a8)
+++ cpukit/score/src/scheduleredfunblock.c	(revision 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f)
@@ -28,6 +28,11 @@
 )
 {
-  _Scheduler_EDF_Enqueue( scheduler, the_thread );
-  /* TODO: flash critical section? */
+  Scheduler_EDF_Context *context;
+  Scheduler_EDF_Node    *node;
+
+  context = _Scheduler_EDF_Get_context( scheduler );
+  node = _Scheduler_EDF_Thread_get_node( the_thread );
+
+  _Scheduler_EDF_Enqueue( context, node, node->current_priority );
 
   /*
@@ -43,10 +48,5 @@
    *    a pseudo-ISR system task, we need to do a context switch.
    */
-  if (
-    _Scheduler_EDF_Priority_compare(
-      the_thread->current_priority,
-      _Thread_Heir->current_priority
-    ) == 1 
-  ) {
+  if ( the_thread->current_priority < _Thread_Heir->current_priority ) {
     _Scheduler_Update_heir(
       the_thread,
Index: cpukit/score/src/scheduleredfupdate.c
===================================================================
--- cpukit/score/src/scheduleredfupdate.c	(revision 9a78f8a5076687a8744991998ee6119f87db12a8)
+++ cpukit/score/src/scheduleredfupdate.c	(revision 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f)
@@ -27,15 +27,12 @@
 )
 {
-  Scheduler_EDF_Node *node = _Scheduler_EDF_Thread_get_node( the_thread );
+  Scheduler_EDF_Node *node;
 
-  (void) scheduler;
-  (void) new_priority;
+  node = _Scheduler_EDF_Thread_get_node( the_thread );
 
-  if (node->queue_state == SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN) {
-    /* Shifts the priority to the region of background tasks. */
-    the_thread->Start.initial_priority |= (SCHEDULER_EDF_PRIO_MSB);
-    the_thread->real_priority    = the_thread->Start.initial_priority;
-    the_thread->current_priority = the_thread->Start.initial_priority;
-    node->queue_state = SCHEDULER_EDF_QUEUE_STATE_NOT_PRESENTLY;
+  if ( ( new_priority & SCHEDULER_EDF_PRIO_MSB ) != 0 ) {
+    node->background_priority = new_priority;
   }
+
+  node->current_priority = new_priority;
 }
Index: cpukit/score/src/scheduleredfyield.c
===================================================================
--- cpukit/score/src/scheduleredfyield.c	(revision 9a78f8a5076687a8744991998ee6119f87db12a8)
+++ cpukit/score/src/scheduleredfyield.c	(revision 99fc1d1d1b44e70a0bed4c94a514bd3f3b5df64f)
@@ -27,20 +27,12 @@
 )
 {
-  Scheduler_EDF_Context *context =
-    _Scheduler_EDF_Get_context( scheduler );
-  Scheduler_EDF_Node    *node = _Scheduler_EDF_Thread_get_node( the_thread );
+  Scheduler_EDF_Context *context;
+  Scheduler_EDF_Node    *node;
 
-  /*
-   * The RBTree has more than one node, enqueue behind the tasks
-   * with the same priority in case there are such ones.
-   */
-  _RBTree_Extract( &context->Ready, &node->Node );
-  _RBTree_Insert(
-    &context->Ready,
-    &node->Node,
-    _Scheduler_EDF_Compare,
-    false
-  );
+  context = _Scheduler_EDF_Get_context( scheduler );
+  node = _Scheduler_EDF_Thread_get_node( the_thread );
 
+  _Scheduler_EDF_Extract( context, node );
+  _Scheduler_EDF_Enqueue( context, node, node->current_priority );
   _Scheduler_EDF_Schedule_body( scheduler, the_thread, false );
 
