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.

13 files changed, 500 insertions, 0 deletions

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 );
+}