implemented best fit algorithm

11 files changed, 271 insertions, 65 deletions

diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
index ff3ae158659..cefc534b726 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
@@ -81,15 +81,16 @@ project (bestfit_ftrmff) {
   exename = ftrmbf
   exeout = ../bin
 
+  macros += DO_DEBUG
+
   Source_Files {
     Algorithms.cpp
     Schedule.cpp
-    CTT_Basic.cpp
     CTT_Enhanced.cpp
-    Task_Scheduler.cpp
+    Utilization_Ranking.cpp
+    OptimizedWCRT.cpp
+    RankedWCRT.cpp
     Simple_Ranking.cpp
-    FTRMFF_Primary.cpp
-    FTRMFF_Basic.cpp
     FTRMFF_Bestfit.cpp
     bestfit_ftrmff.cpp
   }
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.cpp
index 69f03bfa9e6..2a0666c8f16 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.cpp
@@ -11,9 +11,8 @@
 //=============================================================================
 
 #include "FTRMFF_Bestfit.h"
-#include "FTRMFF_Primary.h"
-#include "FTRMFF_Basic.h"
-#include "CTT_Enhanced.h"
+#include "RankedWCRT.h"
+#include "Utilization_Ranking.h"
 
 FTRMFF_Bestfit::~FTRMFF_Bestfit ()
 {
@@ -29,13 +28,15 @@ FTRMFF_Bestfit::operator () (const FTRMFF_Input & input)
   output.schedule = algorithm (input.tasks);
   output.unscheduled_tasks = algorithm.get_unschedulable ();
 
+  DBG_OUT (algorithm.schedule ());
+
   return output;
 }
 
 FTRMFF_Bestfit_Algorithm::FTRMFF_Bestfit_Algorithm (
   const PROCESSOR_LIST & processors,
   unsigned int consistency_level)
-  : processors_ (processors),
+  : schedule_ (create_schedule (processors)),
     consistency_level_ (consistency_level)
 {
 }
@@ -47,43 +48,88 @@ FTRMFF_Bestfit_Algorithm::~FTRMFF_Bestfit_Algorithm ()
 SCHEDULING_MAP
 FTRMFF_Bestfit_Algorithm::operator () (const TASK_LIST & tasks)
 {
-  // step one, only schedule primaries to get lower bound
-  FTRMFF_Primary_Algorithm primary_ftrmff (processors_);
-
-  primary_ftrmff (tasks);
-
-  unsigned long minimum = 
-    processor_usage (primary_ftrmff.schedule ());
-
-  std::cout << minimum << " ";
-
-  // step two, schedule replicas with only state synchronization times
-  CTT_Enhanced ctt_enhanced;
-  FTRMFF_Basic_Algorithm only_ss_ftrmff (processors_,
-                                         consistency_level_,
-                                         ctt_enhanced);
-
-  only_ss_ftrmff (tasks);
-  
-  unsigned long lower_bound = 
-    processor_usage (only_ss_ftrmff.schedule ());
-
-  std::cout << lower_bound << " ";
-
-  // step three, schedule all replicas as active
-  CTT_Basic ctt_basic;
-  FTRMFF_Basic_Algorithm active_ftrmff (processors_,
-                                        consistency_level_,
-                                        ctt_basic);
-
-  active_ftrmff (tasks);
-  
-  unsigned long upper_bound = 
-    processor_usage (active_ftrmff.schedule ());
-
-  std::cout << upper_bound << std::endl;
-
-  return SCHEDULING_MAP ();
+  // sort tasks according to their worst case response times
+  TASK_LIST sorted_tasks = tasks;
+
+  std::sort (sorted_tasks.begin (), 
+	     sorted_tasks.end (), 
+	     PeriodComparison <Task> ());
+
+  // for each task
+  for (TASK_LIST::const_iterator task_it = sorted_tasks.begin ();
+       task_it != sorted_tasks.end ();
+       ++task_it)
+    {
+      // create a set of replicas
+      TASK_LIST replica_group = create_tasks (*task_it, consistency_level_);
+
+      // copy global schedule for per-task scheduling
+      SCHEDULE local_schedule = schedule_;
+
+      // initialize worst-case response time algorithm
+      RankedWCRT wcrt_algorithm (local_schedule,
+                                 consistency_level_);
+
+      // this data-structure will store result schedules
+      SCHEDULE_RESULT_LIST schedule_results;
+
+      // for each replica
+      for (TASK_LIST::iterator replica_it = replica_group.begin ();
+           replica_it != replica_group.end ();
+           ++replica_it)
+        {
+          ScheduleResult best_result;
+          best_result.wcrt = -1.0;
+
+          // for each processor
+          for (SCHEDULE::iterator proc_it = local_schedule.begin ();
+               proc_it != local_schedule.end ();
+               ++proc_it)
+            {
+              // calculate worst-case response time of replica on processor
+              TASK_LIST local_tasks = local_schedule[proc_it->first];
+
+              local_tasks.push_back (*task_it);
+
+              double wcrt = wcrt_algorithm (local_tasks);
+
+              // remember result with minimum worst-case response time
+              if ((best_result.wcrt < .0) || (wcrt < best_result.wcrt))
+                {
+                  best_result.task = *task_it;
+                  best_result.processor = proc_it->first;
+                  best_result.wcrt = wcrt;
+                }
+            }
+
+          // use best schedule entry
+          schedule_results.push_back (best_result);
+
+          local_schedule.erase (best_result.processor);
+        }
+
+      // rank replicas based on the non-failure case response time
+      Utilization_Ranking ranking_algorithm;
+
+      unsigned int scheduled_replicas = 
+        ranking_algorithm (schedule_results,
+                           schedule_);
+
+      // if all tasks are schedulable
+      if (scheduled_replicas == schedule_results.size ())
+        {
+          // schedule all schedule entries for replicas
+          add_schedule_results (schedule_results, schedule_);
+        }
+      else
+        {
+          // if not add to unschedulable list
+          ScheduleProgress pg = {*task_it, scheduled_replicas};
+          unschedulable_.push_back (pg);
+        }
+    }
+
+  return transform_schedule (schedule_);
 }
 
 SCHEDULE_PROGRESS_LIST
@@ -91,3 +137,9 @@ FTRMFF_Bestfit_Algorithm::get_unschedulable ()
 {
   return unschedulable_;
 }
+
+const SCHEDULE & 
+FTRMFF_Bestfit_Algorithm::schedule () const
+{
+  return schedule_;
+}
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.h b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.h
index 38541874af2..81e61148904 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.h
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.h
@@ -37,8 +37,10 @@ public:
 
   SCHEDULE_PROGRESS_LIST get_unschedulable ();
 
+  const SCHEDULE & schedule () const;
+
 private:
-  const PROCESSOR_LIST & processors_;
+  SCHEDULE schedule_;
   SCHEDULE_PROGRESS_LIST unschedulable_;
   unsigned int consistency_level_;
 };
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.cpp
new file mode 100644
index 00000000000..74741524c66
--- /dev/null
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.cpp
@@ -0,0 +1,93 @@
+// -*- C++ -*-
+
+//=============================================================================
+/**
+ *  @file    FTRMFF_Binary_Search.cpp
+ *
+ *  $Id$
+ *
+ *  @author  Friedhelm Wolf (fwolf@dre.vanderbilt.edu)
+ */
+//=============================================================================
+
+#include "FTRMFF_Binary_Search.h"
+#include "FTRMFF_Primary.h"
+#include "FTRMFF_Basic.h"
+#include "CTT_Enhanced.h"
+
+FTRMFF_Binary_Search::~FTRMFF_Binary_Search ()
+{
+}
+
+FTRMFF_Output
+FTRMFF_Binary_Search::operator () (const FTRMFF_Input & input)
+{
+  FTRMFF_Binary_Search_Algorithm algorithm (input.processors,
+                                      input.backup_count);
+
+  FTRMFF_Output output;
+  output.schedule = algorithm (input.tasks);
+  output.unscheduled_tasks = algorithm.get_unschedulable ();
+
+  return output;
+}
+
+FTRMFF_Binary_Search_Algorithm::FTRMFF_Binary_Search_Algorithm (
+  const PROCESSOR_LIST & processors,
+  unsigned int consistency_level)
+  : processors_ (processors),
+    consistency_level_ (consistency_level)
+{
+}
+
+FTRMFF_Binary_Search_Algorithm::~FTRMFF_Binary_Search_Algorithm ()
+{
+}
+
+SCHEDULING_MAP
+FTRMFF_Binary_Search_Algorithm::operator () (const TASK_LIST & tasks)
+{
+  // step one, only schedule primaries to get lower bound
+  FTRMFF_Primary_Algorithm primary_ftrmff (processors_);
+
+  primary_ftrmff (tasks);
+
+  unsigned long minimum = 
+    processor_usage (primary_ftrmff.schedule ());
+
+  std::cout << minimum << " ";
+
+  // step two, schedule replicas with only state synchronization times
+  CTT_Enhanced ctt_enhanced;
+  FTRMFF_Basic_Algorithm only_ss_ftrmff (processors_,
+                                         consistency_level_,
+                                         ctt_enhanced);
+
+  only_ss_ftrmff (tasks);
+  
+  unsigned long lower_bound = 
+    processor_usage (only_ss_ftrmff.schedule ());
+
+  std::cout << lower_bound << " ";
+
+  // step three, schedule all replicas as active
+  CTT_Basic ctt_basic;
+  FTRMFF_Basic_Algorithm active_ftrmff (processors_,
+                                        consistency_level_,
+                                        ctt_basic);
+
+  active_ftrmff (tasks);
+  
+  unsigned long upper_bound = 
+    processor_usage (active_ftrmff.schedule ());
+
+  std::cout << upper_bound << std::endl;
+
+  return SCHEDULING_MAP ();
+}
+
+SCHEDULE_PROGRESS_LIST
+FTRMFF_Binary_Search_Algorithm::get_unschedulable ()
+{
+  return unschedulable_;
+}
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.h b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.h
new file mode 100644
index 00000000000..9e91eae404a
--- /dev/null
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.h
@@ -0,0 +1,46 @@
+// -*- C++ -*-
+
+//=============================================================================
+/**
+ *  @file    FTRMFF_Binary_Search.h
+ *
+ *  $Id$
+ *
+ *  @author  Friedhelm Wolf (fwolf@dre.vanderbilt.edu)
+ */
+//=============================================================================
+
+#ifndef FTRMFF_BESTFIT_ALGORITHM_H_
+#define FTRMFF_BESTFIT_ALGORITHM_H_
+
+#include "Schedule.h"
+
+class FTRMFF_Binary_Search : public FTRMFF_Algorithm
+{
+public:
+  virtual ~FTRMFF_Binary_Search ();
+
+  virtual FTRMFF_Output operator () (const FTRMFF_Input & input);
+};
+
+class FTRMFF_Binary_Search_Algorithm : 
+  public std::unary_function <TASK_LIST,
+                              SCHEDULING_MAP>
+{
+public:
+  FTRMFF_Binary_Search_Algorithm (const PROCESSOR_LIST & processors,
+                           unsigned int consistency_level);
+
+  virtual ~FTRMFF_Binary_Search_Algorithm ();
+
+  virtual SCHEDULING_MAP operator () (const TASK_LIST & tasks);
+
+  SCHEDULE_PROGRESS_LIST get_unschedulable ();
+
+private:
+  const PROCESSOR_LIST & processors_;
+  SCHEDULE_PROGRESS_LIST unschedulable_;
+  unsigned int consistency_level_;
+};
+
+#endif /* FTRMFF_BESTFIT_ALGORITHM_H_ */
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/OptimizedWCRT.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/OptimizedWCRT.cpp
index b27f9d16287..baa7527f0ef 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/OptimizedWCRT.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/OptimizedWCRT.cpp
@@ -61,8 +61,8 @@ OptimizedWCRT::operator () (double current_wcrt,
       // active get treated as primaries
       TASK_LIST modified_tasks;
 
-      std::cout << "Original: " << tasks_ << std::endl
-                << "Active: " << active_backups << std::endl;
+      TRACE ("Original: " << tasks_ << std::endl
+             << "Active: " << active_backups);
       
       std::transform (tasks_.begin (),
                       tasks_.end (),
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/RankedWCRT.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/RankedWCRT.cpp
index 3dbea5afca4..639fa3886f0 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/RankedWCRT.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/RankedWCRT.cpp
@@ -126,18 +126,6 @@ public:
   void operator () (const Task & task)
   {
     PROCESSOR_SET failure_set = map_ [task.name];
-    PROCESSOR_SET result;
-
-    /*    
-    std::set_union (failure_set.begin (),
-                    failure_set.end (),
-                    union_.begin (),
-                    union_.end (),
-                    std::inserter (result,
-                                   result.begin ()));
-
-                                   union_ = result;
-    */
 
     union_.insert (failure_set.begin (), failure_set.end ());
 
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Ranked_Scheduler.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Ranked_Scheduler.cpp
index de9078ee46a..94f691eef54 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Ranked_Scheduler.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Ranked_Scheduler.cpp
@@ -31,9 +31,6 @@ Ranked_Scheduler::operator () (const Task & task)
        processor_it != current_schedule_.end ();
        ++processor_it)
     {
-      // iterate through all possible failure cases that might affect
-      // this processor, based on its tasks
-      // TASK_LIST active_backups = 
       TASK_LIST local_tasks = processor_it->second;
 
       local_tasks.push_back (task);
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Schedule.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Schedule.cpp
index e5bbb831c91..33d4af4ac2c 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Schedule.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Schedule.cpp
@@ -159,6 +159,31 @@ SCHEDULE create_schedule (const PROCESSOR_LIST & processors)
   return result;
 }
 
+class ScheduleProcessorName : public std::unary_function <
+                                       SCHEDULE::value_type,
+                                       PROCESSOR_LIST::value_type>
+{
+public:
+  PROCESSOR_LIST::value_type operator () (const SCHEDULE::value_type & entry)
+  {
+    return entry.first;
+  }
+};
+
+PROCESSOR_LIST 
+get_processors (const SCHEDULE & schedule)
+{
+  PROCESSOR_LIST processors;
+
+  std::transform (schedule.begin (),
+                  schedule.end (),
+                  std::inserter (processors,
+                                 processors.begin ()),
+                  ScheduleProcessorName ());
+
+  return processors;
+}
+
 unsigned long 
 processor_usage (const SCHEDULE & schedule)
 {
@@ -183,7 +208,7 @@ std::ostream &
 operator<< (std::ostream & ostr, const ScheduleResult & r)
 {
   ostr << "<" << r.task << "|" << r.processor 
-       << "|" << r.wcrt << ">" << std::endl;
+       << "|" << r.wcrt << ">";
 
   return ostr;
 }
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Schedule.h b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Schedule.h
index 045a741daec..a37a406b2f8 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Schedule.h
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Schedule.h
@@ -33,6 +33,8 @@ SCHEDULE read_schedule (std::istream & istr);
 
 SCHEDULE create_schedule (const PROCESSOR_LIST & processors);
 
+PROCESSOR_LIST get_processors (const SCHEDULE & schedule);
+
 unsigned long processor_usage (const SCHEDULE & schedule);
 
 struct ScheduleResult
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Utilization_Ranking.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Utilization_Ranking.cpp
index de523316c52..9d273889525 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Utilization_Ranking.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Utilization_Ranking.cpp
@@ -33,7 +33,7 @@ unsigned long
 Utilization_Ranking::operator () (SCHEDULE_RESULT_LIST & result_list,
                                   const SCHEDULE & schedule)
 {
-  unsigned long scheduled_replicas;
+  unsigned long scheduled_replicas = 0;
 
   for (SCHEDULE_RESULT_LIST::iterator it = result_list.begin ();
        it != result_list.end ();