2011-09-11 Petr Benes <benesp16@fel.cvut.cz>

	PR 1896/cpukit
	* sapi/include/confdefs.h, score/Makefile.am, score/preinstall.am: Add
	Earliest Deadline First (EDF) Scheduling Algorithm implementation.
	* score/include/rtems/score/scheduleredf.h, score/src/scheduleredf.c,
	score/src/scheduleredfallocate.c, score/src/scheduleredfblock.c,
	score/src/scheduleredfenqueue.c,
	score/src/scheduleredfenqueuefirst.c,
	score/src/scheduleredfextract.c, score/src/scheduleredffree.c,
	score/src/scheduleredfprioritycompare.c,
	score/src/scheduleredfreleasejob.c, score/src/scheduleredfschedule.c,
	score/src/scheduleredfunblock.c, score/src/scheduleredfupdate.c,
	score/src/scheduleredfyield.c: New files.

18 files changed, 819 insertions, 1 deletions

diff --git a/cpukit/ChangeLog b/cpukit/ChangeLog
index 6b770a14e8..31581e0faa 100644
--- a/cpukit/ChangeLog
+++ b/cpukit/ChangeLog
@@ -1,3 +1,18 @@
+2011-09-11	Petr Benes <benesp16@fel.cvut.cz>
+
+	PR 1896/cpukit
+	* sapi/include/confdefs.h, score/Makefile.am, score/preinstall.am: Add
+	Earliest Deadline First (EDF) Scheduling Algorithm implementation.
+	* score/include/rtems/score/scheduleredf.h, score/src/scheduleredf.c,
+	score/src/scheduleredfallocate.c, score/src/scheduleredfblock.c,
+	score/src/scheduleredfenqueue.c,
+	score/src/scheduleredfenqueuefirst.c,
+	score/src/scheduleredfextract.c, score/src/scheduleredffree.c,
+	score/src/scheduleredfprioritycompare.c,
+	score/src/scheduleredfreleasejob.c, score/src/scheduleredfschedule.c,
+	score/src/scheduleredfunblock.c, score/src/scheduleredfupdate.c,
+	score/src/scheduleredfyield.c: New files.
+
 2011-09-09	Sebastian Huber <sebastian.huber@embedded-brains.de>
 
 	PR 1901/cpukit
diff --git a/cpukit/sapi/include/confdefs.h b/cpukit/sapi/include/confdefs.h
index 3ecc60941d..2a9d75ac2c 100644
--- a/cpukit/sapi/include/confdefs.h
+++ b/cpukit/sapi/include/confdefs.h
@@ -573,6 +573,7 @@ rtems_fs_init_functions_t    rtems_fs_init_helper =
  *  CONFIGURE_SCHEDULER_PRIORITY   - Deterministic Priority Scheduler
  *  CONFIGURE_SCHEDULER_SIMPLE     - Light-weight Priority Scheduler
  *  CONFIGURE_SCHEDULER_SIMPLE_SMP - Simple SMP Priority Scheduler
+ *  CONFIGURE_SCHEDULER_EDF        - EDF Scheduler
  * 
  * If no configuration is specified by the application, then 
  * CONFIGURE_SCHEDULER_PRIORITY is assumed to be the default.
@@ -598,7 +599,8 @@ rtems_fs_init_functions_t    rtems_fs_init_helper =
 #if !defined(CONFIGURE_SCHEDULER_USER) && \
     !defined(CONFIGURE_SCHEDULER_PRIORITY) && \
     !defined(CONFIGURE_SCHEDULER_SIMPLE) && \
-    !defined(CONFIGURE_SCHEDULER_SIMPLE_SMP)
+    !defined(CONFIGURE_SCHEDULER_SIMPLE_SMP) && \
+    !defined(CONFIGURE_SCHEDULER_EDF)
   #if defined(RTEMS_SMP) && defined(CONFIGURE_SMP_APPLICATION)
     #define CONFIGURE_SCHEDULER_SIMPLE_SMP
   #else
@@ -658,6 +660,22 @@ rtems_fs_init_functions_t    rtems_fs_init_helper =
   #define CONFIGURE_MEMORY_PER_TASK_FOR_SCHEDULER (0)
 #endif
 
+/*
+ * If the EDF Scheduler is selected, then configure for it.
+ */
+#if defined(CONFIGURE_SCHEDULER_EDF)
+  #include <rtems/score/scheduleredf.h>
+  #define CONFIGURE_SCHEDULER_ENTRY_POINTS SCHEDULER_EDF_ENTRY_POINTS
+
+  /**
+   * define the memory used by the EDF scheduler
+   */
+  #define CONFIGURE_MEMORY_FOR_SCHEDULER ( \
+    _Configure_From_workspace(0))
+  #define CONFIGURE_MEMORY_PER_TASK_FOR_SCHEDULER ( \
+    _Configure_From_workspace(sizeof(Scheduler_EDF_Per_thread)))
+#endif
+
 #if defined(CONFIGURE_SCHEDULER_USER)
   #define CONFIGURE_SCHEDULER_ENTRY_POINTS \
           CONFIGURE_SCHEDULER_USER_ENTRY_POINTS
diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
index 20d8ead7b9..d05ccfdb81 100644
--- a/cpukit/score/Makefile.am
+++ b/cpukit/score/Makefile.am
@@ -40,6 +40,7 @@ include_rtems_score_HEADERS += include/rtems/score/priority.h
 include_rtems_score_HEADERS += include/rtems/score/prioritybitmap.h
 include_rtems_score_HEADERS += include/rtems/score/rbtree.h
 include_rtems_score_HEADERS += include/rtems/score/scheduler.h
+include_rtems_score_HEADERS += include/rtems/score/scheduleredf.h
 include_rtems_score_HEADERS += include/rtems/score/schedulerpriority.h
 include_rtems_score_HEADERS += include/rtems/score/schedulersimple.h
 include_rtems_score_HEADERS += include/rtems/score/stack.h
@@ -222,6 +223,21 @@ libscore_a_SOURCES += src/schedulersimple.c \
     src/schedulersimpleunblock.c \
     src/schedulersimpleyield.c 
 
+## SCHEDULEREDF_C_FILES
+libscore_a_SOURCES += src/scheduleredf.c \
+    src/scheduleredfallocate.c \
+    src/scheduleredfblock.c \
+    src/scheduleredfenqueue.c \
+    src/scheduleredfenqueuefirst.c \
+    src/scheduleredfextract.c \
+    src/scheduleredffree.c \
+    src/scheduleredfprioritycompare.c \
+    src/scheduleredfreleasejob.c \
+    src/scheduleredfschedule.c \
+    src/scheduleredfunblock.c \
+    src/scheduleredfupdate.c \
+    src/scheduleredfyield.c
+
 ## PROTECTED_HEAP_C_FILES
 libscore_a_SOURCES += src/pheapallocate.c \
     src/pheapextend.c src/pheapfree.c src/pheapgetsize.c \
diff --git a/cpukit/score/include/rtems/score/scheduleredf.h b/cpukit/score/include/rtems/score/scheduleredf.h
new file mode 100644
index 0000000000..06569066d6
--- /dev/null
+++ b/cpukit/score/include/rtems/score/scheduleredf.h
@@ -0,0 +1,265 @@
+/**
+ *  @file  rtems/score/scheduleredf.h
+ *
+ *  This include file contains all the constants and structures associated
+ *  with the manipulation of threads for the EDF scheduler.
+ */
+
+/*
+ *  Copryight (c) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#ifndef _RTEMS_SCORE_SCHEDULEREDF_H
+#define _RTEMS_SCORE_SCHEDULEREDF_H
+
+#include <rtems/score/priority.h>
+#include <rtems/score/scheduler.h>
+#include <rtems/score/schedulerpriority.h>
+#include <rtems/score/rbtree.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ *  @addtogroup ScoreScheduler
+ *
+ */
+/**@{*/
+
+/**
+ *  Entry points for the Earliest Deadline First Scheduler.
+ */
+#define SCHEDULER_EDF_ENTRY_POINTS \
+  { \
+    _Scheduler_EDF_Initialize,       /* initialize entry point */ \
+    _Scheduler_EDF_Schedule,         /* schedule entry point */ \
+    _Scheduler_EDF_Yield,            /* yield entry point */ \
+    _Scheduler_EDF_Block,            /* block entry point */ \
+    _Scheduler_EDF_Unblock,          /* unblock entry point */ \
+    _Scheduler_EDF_Allocate,         /* allocate entry point */ \
+    _Scheduler_EDF_Free,             /* free 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_Priority_compare, /* compares two priorities */ \
+    _Scheduler_EDF_Release_job,      /* new period of task */ \
+    _Scheduler_priority_Tick         /* tick entry point */ \
+  }
+
+/**
+ * This is just a most significant bit of Priority_Control type. It
+ * distinguishes threads which are deadline driven (priority
+ * represented by a lower number than @a SCHEDULER_EDF_PRIO_MSB) from those
+ * ones who do not have any deadlines and thus are considered background
+ * tasks.
+ */
+#define SCHEDULER_EDF_PRIO_MSB 0x80000000
+
+/**
+ * @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;
+
+/**
+ * This structure handles EDF specific data of a thread.
+ */
+typedef struct {
+  /**
+   * Pointer to corresponding Thread Control Block.
+   */
+  Thread_Control *thread;
+  /**
+   * Rbtree node related to this thread.
+   */
+  RBTree_Node Node;
+  /**
+   * State of the thread with respect to ready queue.
+   */
+  Scheduler_EDF_Queue_state queue_state;
+} Scheduler_EDF_Per_thread;
+
+/**
+ * Top of the ready queue.
+ */
+extern RBTree_Control _Scheduler_EDF_Ready_queue;
+
+/**
+ * @brief Scheduler EDF Initialize
+ *
+ * This routine initializes the EDF scheduler.
+ */
+void _Scheduler_EDF_Initialize( void );
+
+/**
+ *  @brief Scheduler EDF Block
+ *
+ *  This routine removes @a the_thread from the scheduling decision,
+ *  that is, removes it from the ready queue.  It performs
+ *  any necessary scheduling operations including the selection of
+ *  a new heir thread.
+ *
+ *  @param[in] the_thread is the thread to be blocked.
+ */
+void _Scheduler_EDF_Block(
+  Thread_Control    *the_thread
+);
+
+/**
+ *  @brief Scheduler EDF Schedule
+ *
+ *  This kernel routine sets the heir thread to be the next ready thread
+ *  in the rbtree ready queue.
+ */
+void _Scheduler_EDF_Schedule( void );
+
+/**
+ *  @brief Scheduler EDF Allocate
+ *
+ *  This routine allocates EDF specific information of @a the_thread.
+ *
+ *  @param[in] the_thread is the thread the scheduler is allocating
+ *             management memory for.
+ */
+void *_Scheduler_EDF_Allocate(
+  Thread_Control      *the_thread
+);
+
+/**
+ *  @brief Scheduler EDF Free
+ *
+ *  This routine frees the EDF specific information of @a the_thread.
+ *
+ *  @param[in] the_thread is the thread whose scheduler specific information
+ *             will be deallocated.
+ */
+void _Scheduler_EDF_Free(
+  Thread_Control      *the_thread
+);
+
+/**
+ *  @brief Scheduler EDF Update
+ *
+ *  This routine updates position in the ready queue of @a the_thread.
+ *
+ *  @param[in] the_thread will have its scheduler specific information
+ *             structure updated.
+ */
+void _Scheduler_EDF_Update(
+  Thread_Control      *the_thread
+);
+
+/**
+ *  @brief Scheduler EDF Unblock
+ *
+ *  This routine adds @a the_thread to the scheduling decision, that is,
+ *  adds it to the ready queue and updates any appropriate scheduling
+ *  variables, for example the heir thread.
+ *
+ *  @param[in] the_thread will be unblocked.
+ */
+void _Scheduler_EDF_Unblock(
+  Thread_Control    *the_thread
+);
+
+/**
+ *  @brief Scheduler EDF Yield
+ *
+ *  This routine is invoked when a thread wishes to voluntarily
+ *  transfer control of the processor to another thread in the queue with
+ *  equal deadline. This does not have to happen very often.
+ *
+ *  This routine will remove the running THREAD from the ready queue
+ *  and place back. The rbtree ready queue is responsible for FIFO ordering
+ *  in such a case.
+ */
+void _Scheduler_EDF_Yield( void );
+
+/**
+ *  @brief Scheduler EDF Enqueue
+ *
+ *  This routine puts @a the_thread to the rbtree ready queue.
+ *
+ *  @param[in] the_thread will be enqueued to the ready queue.
+ */
+void _Scheduler_EDF_Enqueue(
+  Thread_Control    *the_thread
+);
+
+/**
+ *  @brief Scheduler EDF Enqueue first
+ *
+ *  This routine puts @a the_thread to the rbtree ready queue.
+ *  For the EDF scheduler this is the same as @a _Scheduler_EDF_Enqueue.
+ *
+ *  @param[in] the_thread will be enqueued to the ready queue.
+ */
+void _Scheduler_EDF_Enqueue_first(
+  Thread_Control    *the_thread
+);
+
+/**
+ *  @brief Scheduler EDF Extract
+ *
+ *  This routine removes a specific thread from the scheduler's set
+ *  of ready threads.
+ *
+ *  @param[in] the_thread will be extracted from the ready set.
+ */
+void _Scheduler_EDF_Extract(
+  Thread_Control     *the_thread
+);
+
+/**
+ *  @brief Scheduler EDF Priority compare
+ *
+ * This routine explicitly compares absolute dedlines (priorities) of threads.
+ * In case of EDF scheduling time overflow is taken into account.
+ *
+ * @return >0 for p1 > p2; 0 for p1 == p2; <0 for p1 < p2.
+ */
+int _Scheduler_EDF_Priority_compare (
+  Priority_Control p1,
+  Priority_Control p2
+);
+
+/**
+ *  @brief Scheduler EDF Release job
+ *
+ *  This routine is called when a new job of task is released.
+ *  It is called only from Rate Monotonic manager in the beginning
+ *  of new period.
+ *
+ *  @param[in] the_thread is the owner of the job.
+ *  @param[in] deadline of the new job from now. If equal to 0,
+ *             the job was cancelled or deleted, thus a running task
+ *             has to be suspended.
+ */
+void _Scheduler_EDF_Release_job (
+  Thread_Control  *the_thread,
+  uint32_t         deadline
+);
+
+#ifdef __cplusplus
+}
+#endif
+
+/**@}*/
+
+#endif
+/* end of include file */
diff --git a/cpukit/score/preinstall.am b/cpukit/score/preinstall.am
index 884891f5c3..0461648517 100644
--- a/cpukit/score/preinstall.am
+++ b/cpukit/score/preinstall.am
@@ -127,6 +127,10 @@ $(PROJECT_INCLUDE)/rtems/score/scheduler.h: include/rtems/score/scheduler.h $(PR
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduler.h
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduler.h
 
+$(PROJECT_INCLUDE)/rtems/score/scheduleredf.h: include/rtems/score/scheduleredf.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
+	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/scheduleredf.h
+PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/scheduleredf.h
+
 $(PROJECT_INCLUDE)/rtems/score/schedulerpriority.h: include/rtems/score/schedulerpriority.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/schedulerpriority.h
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/schedulerpriority.h
diff --git a/cpukit/score/src/scheduleredf.c b/cpukit/score/src/scheduleredf.c
new file mode 100644
index 0000000000..2aa2d52cea
--- /dev/null
+++ b/cpukit/score/src/scheduleredf.c
@@ -0,0 +1,49 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/config.h>
+#include <rtems/score/scheduler.h>
+#include <rtems/score/scheduleredf.h>
+
+int _Scheduler_EDF_RBTree_compare_function
+(
+  RBTree_Node* n1,
+  RBTree_Node* n2
+)
+{
+  Priority_Control value1 = _RBTree_Container_of
+    (n1,Scheduler_EDF_Per_thread,Node)->thread->current_priority;
+  Priority_Control value2 = _RBTree_Container_of
+    (n2,Scheduler_EDF_Per_thread,Node)->thread->current_priority;
+
+  /*
+   * This function compares only numbers for the red-black tree,
+   * but priorities have an opposite sense.
+   */
+  return (-1)*_Scheduler_Is_priority_higher_than(value1, value2);
+}
+
+void _Scheduler_EDF_Initialize(void)
+{
+  _RBTree_Initialize_empty(
+      &_Scheduler_EDF_Ready_queue,
+      &_Scheduler_EDF_RBTree_compare_function,
+      0
+  );
+}
+
+/* Instantiate any global variables needed by the EDF scheduler */
+RBTree_Control _Scheduler_EDF_Ready_queue;
diff --git a/cpukit/score/src/scheduleredfallocate.c b/cpukit/score/src/scheduleredfallocate.c
new file mode 100644
index 0000000000..6d45583519
--- /dev/null
+++ b/cpukit/score/src/scheduleredfallocate.c
@@ -0,0 +1,39 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/config.h>
+#include <rtems/score/scheduler.h>
+#include <rtems/score/scheduleredf.h>
+#include <rtems/score/wkspace.h>
+
+void *_Scheduler_EDF_Allocate(
+  Thread_Control      *the_thread
+)
+{
+  void *sched;
+  Scheduler_EDF_Per_thread *schinfo;
+
+  sched = _Workspace_Allocate( sizeof(Scheduler_EDF_Per_thread) );
+
+  if ( sched ) {
+    the_thread->scheduler_info = sched;
+    schinfo = (Scheduler_EDF_Per_thread *)(the_thread->scheduler_info);
+    schinfo->thread = the_thread;
+    schinfo->queue_state = SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN;
+  }
+
+  return sched;
+}
diff --git a/cpukit/score/src/scheduleredfblock.c b/cpukit/score/src/scheduleredfblock.c
new file mode 100644
index 0000000000..5923171bc9
--- /dev/null
+++ b/cpukit/score/src/scheduleredfblock.c
@@ -0,0 +1,36 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/score/context.h>
+#include <rtems/score/priority.h>
+#include <rtems/score/scheduler.h>
+#include <rtems/score/scheduleredf.h>
+#include <rtems/score/thread.h>
+
+void _Scheduler_EDF_Block(
+  Thread_Control    *the_thread
+)
+{
+  _Scheduler_EDF_Extract( the_thread );
+
+  /* TODO: flash critical section? */
+
+  if ( _Thread_Is_heir( the_thread ) )
+    _Scheduler_EDF_Schedule();
+
+  if ( _Thread_Is_executing( the_thread ) )
+    _Thread_Dispatch_necessary = true;
+}
diff --git a/cpukit/score/src/scheduleredfenqueue.c b/cpukit/score/src/scheduleredfenqueue.c
new file mode 100644
index 0000000000..dc59e26ab7
--- /dev/null
+++ b/cpukit/score/src/scheduleredfenqueue.c
@@ -0,0 +1,31 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/config.h>
+#include <rtems/score/scheduler.h>
+#include <rtems/score/scheduleredf.h>
+
+void _Scheduler_EDF_Enqueue(
+  Thread_Control    *the_thread
+)
+{
+  Scheduler_EDF_Per_thread *sched_info =
+    (Scheduler_EDF_Per_thread*) the_thread->scheduler_info;
+  RBTree_Node *node = &(sched_info->Node);
+
+  _RBTree_Insert( &_Scheduler_EDF_Ready_queue, node );
+  sched_info->queue_state = SCHEDULER_EDF_QUEUE_STATE_YES;
+}
diff --git a/cpukit/score/src/scheduleredfenqueuefirst.c b/cpukit/score/src/scheduleredfenqueuefirst.c
new file mode 100644
index 0000000000..e8297a147c
--- /dev/null
+++ b/cpukit/score/src/scheduleredfenqueuefirst.c
@@ -0,0 +1,25 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/config.h>
+#include <rtems/score/scheduleredf.h>
+
+void _Scheduler_EDF_Enqueue_first(
+  Thread_Control    *the_thread
+)
+{
+  _Scheduler_EDF_Enqueue(the_thread);
+}
diff --git a/cpukit/score/src/scheduleredfextract.c b/cpukit/score/src/scheduleredfextract.c
new file mode 100644
index 0000000000..019b68e32f
--- /dev/null
+++ b/cpukit/score/src/scheduleredfextract.c
@@ -0,0 +1,31 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/config.h>
+#include <rtems/score/chain.h>
+#include <rtems/score/scheduleredf.h>
+
+void _Scheduler_EDF_Extract(
+  Thread_Control     *the_thread
+)
+{
+  Scheduler_EDF_Per_thread *sched_info =
+    (Scheduler_EDF_Per_thread*) the_thread->scheduler_info;
+  RBTree_Node *node = &(sched_info->Node);
+
+  _RBTree_Extract( &_Scheduler_EDF_Ready_queue, node );
+  sched_info->queue_state = SCHEDULER_EDF_QUEUE_STATE_NOT_PRESENTLY;
+}
diff --git a/cpukit/score/src/scheduleredffree.c b/cpukit/score/src/scheduleredffree.c
new file mode 100644
index 0000000000..76667f0cdd
--- /dev/null
+++ b/cpukit/score/src/scheduleredffree.c
@@ -0,0 +1,27 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/config.h>
+#include <rtems/score/scheduler.h>
+#include <rtems/score/scheduleredf.h>
+#include <rtems/score/wkspace.h>
+
+void _Scheduler_EDF_Free(
+  Thread_Control      *the_thread
+)
+{
+  _Workspace_Free( the_thread->scheduler_info );
+}
diff --git a/cpukit/score/src/scheduleredfprioritycompare.c b/cpukit/score/src/scheduleredfprioritycompare.c
new file mode 100644
index 0000000000..324e44af37
--- /dev/null
+++ b/cpukit/score/src/scheduleredfprioritycompare.c
@@ -0,0 +1,40 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/config.h>
+#include <rtems/score/scheduleredf.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));
+}
diff --git a/cpukit/score/src/scheduleredfreleasejob.c b/cpukit/score/src/scheduleredfreleasejob.c
new file mode 100644
index 0000000000..0bd86e976f
--- /dev/null
+++ b/cpukit/score/src/scheduleredfreleasejob.c
@@ -0,0 +1,40 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/config.h>
+#include <rtems/score/scheduler.h>
+#include <rtems/score/scheduleredf.h>
+
+void _Scheduler_EDF_Release_job(
+  Thread_Control    *the_thread,
+  uint32_t           deadline
+)
+{
+  Priority_Control new_priority;
+
+  if (deadline) {
+    /* Initializing or shifting deadline. */
+    new_priority = (_Watchdog_Ticks_since_boot + deadline)
+                   & ~SCHEDULER_EDF_PRIO_MSB;
+  }
+  else {
+    /* Switch back to background priority. */
+    new_priority = the_thread->Start.initial_priority;
+  }
+
+  the_thread->real_priority = new_priority;
+  _Thread_Change_priority(the_thread, new_priority, true);
+}
diff --git a/cpukit/score/src/scheduleredfschedule.c b/cpukit/score/src/scheduleredfschedule.c
new file mode 100644
index 0000000000..1482be8207
--- /dev/null
+++ b/cpukit/score/src/scheduleredfschedule.c
@@ -0,0 +1,28 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/score/scheduler.h>
+#include <rtems/score/scheduleredf.h>
+
+void _Scheduler_EDF_Schedule(void)
+{
+  RBTree_Node *first_node =
+    _RBTree_Peek(&_Scheduler_EDF_Ready_queue, RBT_LEFT);
+  Scheduler_EDF_Per_thread *sched_info =
+    _RBTree_Container_of(first_node, Scheduler_EDF_Per_thread, Node);
+
+  _Thread_Heir = (Thread_Control *) sched_info->thread;
+}
diff --git a/cpukit/score/src/scheduleredfunblock.c b/cpukit/score/src/scheduleredfunblock.c
new file mode 100644
index 0000000000..bca071adbc
--- /dev/null
+++ b/cpukit/score/src/scheduleredfunblock.c
@@ -0,0 +1,47 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/score/scheduler.h>
+#include <rtems/score/scheduleredf.h>
+
+void _Scheduler_EDF_Unblock(
+  Thread_Control    *the_thread
+)
+{
+  _Scheduler_EDF_Enqueue(the_thread);
+  /* TODO: flash critical section? */
+
+  /*
+   *  If the thread that was unblocked is more important than the heir,
+   *  then we have a new heir.  This may or may not result in a
+   *  context switch.
+   *
+   *  Normal case:
+   *    If the current thread is preemptible, then we need to do
+   *    a context switch.
+   *  Pseudo-ISR case:
+   *    Even if the thread isn't preemptible, if the new heir is
+   *    a pseudo-ISR system task, we need to do a context switch.
+   */
+  if ( _Scheduler_Is_priority_lower_than(
+         _Thread_Heir->current_priority,
+         the_thread->current_priority )) {
+    _Thread_Heir = the_thread;
+    if ( _Thread_Executing->is_preemptible ||
+         the_thread->current_priority == 0 )
+      _Thread_Dispatch_necessary = true;
+  }
+}
diff --git a/cpukit/score/src/scheduleredfupdate.c b/cpukit/score/src/scheduleredfupdate.c
new file mode 100644
index 0000000000..a4592d8c46
--- /dev/null
+++ b/cpukit/score/src/scheduleredfupdate.c
@@ -0,0 +1,50 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/config.h>
+#include <rtems/score/priority.h>
+#include <rtems/score/scheduler.h>
+#include <rtems/score/scheduleredf.h>
+#include <rtems/score/thread.h>
+
+void _Scheduler_EDF_Update(
+  Thread_Control      *the_thread
+)
+{
+  Scheduler_EDF_Per_thread *sched_info =
+    (Scheduler_EDF_Per_thread*)the_thread->scheduler_info;
+  RBTree_Node *the_node = &(sched_info->Node);
+
+  if (sched_info->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;
+    sched_info->queue_state = SCHEDULER_EDF_QUEUE_STATE_NOT_PRESENTLY;
+  }
+
+  if ( sched_info->queue_state == SCHEDULER_EDF_QUEUE_STATE_YES ) {
+    _RBTree_Extract(&_Scheduler_EDF_Ready_queue, the_node);
+    _RBTree_Insert(&_Scheduler_EDF_Ready_queue, the_node);
+
+    _Scheduler_EDF_Schedule();
+    if ( _Thread_Executing != _Thread_Heir ) {
+      if ( _Thread_Executing->is_preemptible ||
+           the_thread->current_priority == 0 )
+        _Thread_Dispatch_necessary = true;
+    }
+  }
+}
diff --git a/cpukit/score/src/scheduleredfyield.c b/cpukit/score/src/scheduleredfyield.c
new file mode 100644
index 0000000000..be1b07a5c5
--- /dev/null
+++ b/cpukit/score/src/scheduleredfyield.c
@@ -0,0 +1,57 @@
+/*
+ *  Copyright (C) 2011 Petr Benes.
+ *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
+ *
+ *  The license and distribution terms for this file may be
+ *  found in the file LICENSE in this distribution or at
+ *  http://www.rtems.com/license/LICENSE.
+ *
+ *  $Id$
+ */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <rtems/system.h>
+#include <rtems/score/isr.h>
+#include <rtems/score/scheduler.h>
+#include <rtems/score/scheduleredf.h>
+#include <rtems/score/thread.h>
+
+void _Scheduler_EDF_Yield(void)
+{
+  Scheduler_EDF_Per_thread *first_info;
+  RBTree_Node              *first_node;
+  ISR_Level                 level;
+
+  Thread_Control *executing  = _Thread_Executing;
+  Scheduler_EDF_Per_thread *executing_info =
+    (Scheduler_EDF_Per_thread *) executing->scheduler_info;
+  RBTree_Node *executing_node = &(executing_info->Node);
+
+  _ISR_Disable( level );
+
+  if ( !_RBTree_Has_only_one_node(&_Scheduler_EDF_Ready_queue) ) {
+    /*
+     * The RBTree has more than one node, enqueue behind the tasks
+     * with the same priority in case there are such ones.
+     */
+    _RBTree_Extract( &_Scheduler_EDF_Ready_queue, executing_node );
+    _RBTree_Insert( &_Scheduler_EDF_Ready_queue, executing_node );
+
+    _ISR_Flash( level );
+
+    if ( _Thread_Is_heir( executing ) ) {
+      first_node = _RBTree_Peek( &_Scheduler_EDF_Ready_queue, RBT_LEFT );
+      first_info =
+        _RBTree_Container_of(first_node, Scheduler_EDF_Per_thread, Node);
+      _Thread_Heir = first_info->thread;
+    }
+    _Thread_Dispatch_necessary = true;
+  }
+  else if ( !_Thread_Is_heir( executing ) )
+    _Thread_Dispatch_necessary = true;
+
+  _ISR_Enable( level );
+}