fixed forward ranking permute_processors function

8 files changed, 171 insertions, 58 deletions

diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.h b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.h
index a90235c425a..b3bbcdcd70a 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.h
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.h
@@ -183,5 +183,4 @@ public:
   Task operator () (const Task & task);
 };
 
-
 #endif /* FTRMFF_ALGORITHMS_H_ */
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
index 44030dada22..b641a48b21d 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
@@ -200,7 +200,7 @@ project (bestfit_ranked_ftrmff) : acelib {
   exename = ftrmbf
   exeout = ../bin
 
-  macros += DO_DEBUG
+  macros += DO_DEBUG // DO_TRACE
 
   Source_Files {
     Algorithms.cpp
@@ -219,7 +219,7 @@ project (schedulability_check) : acelib {
   exename = scheck
   exeout = ../bin
 
-  macros += DO_DEBUG // DO_TRACE
+  macros += DO_DEBUG
 
   Source_Files {
     Algorithms.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 dd7091c0219..9fc4c83ba2e 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.cpp
@@ -42,6 +42,18 @@ FTRMFF_Bestfit_Algorithm::FTRMFF_Bestfit_Algorithm (
     scheduler_ (processors,
                 consistency_level_)
 {
+  // fill last_results data structure
+  ScheduleResult result = { {"NoTask", .0, .0, .0, PRIMARY, 0}, 
+                            "NO PROCESSOR", 
+                            .0};
+
+  for (PROCESSOR_LIST::const_iterator it = processors.begin ();
+       it != processors.end ();
+       ++it)
+    {
+      result.processor = *it;
+      last_results_[*it] = result;
+    }
 }
 
 FTRMFF_Bestfit_Algorithm::~FTRMFF_Bestfit_Algorithm ()
@@ -72,8 +84,25 @@ FTRMFF_Bestfit_Algorithm::operator () (const TASK_LIST & tasks)
            task_it != task_group.end ();
            ++task_it)
         {
-          ScheduleResult r = scheduler_ (*task_it);
-          if (r.wcrt <= .0)
+          std::cout << *task_it << std::endl;
+
+          PROCESSOR_LIST processors = this->best_processors ();
+
+          ScheduleResult schedule_result;
+          for (PROCESSOR_LIST::iterator p_it = processors.begin ();
+               p_it != processors.end ();
+               ++p_it)
+            {
+              TRACE (*task_it << " on " << *p_it);
+
+              schedule_result = scheduler_ (*task_it, *p_it);
+              if (schedule_result.wcrt > .0)
+                {
+                  break;
+                }
+            }
+
+          if (schedule_result.wcrt <= .0)
             {
               ScheduleProgress pg = {*task_it, 
                                      task_it->rank - consistency_level_ + 1};
@@ -82,10 +111,12 @@ FTRMFF_Bestfit_Algorithm::operator () (const TASK_LIST & tasks)
             }
           else
             {
-              scheduler_.update_schedule (r);
+              scheduler_.update_schedule (schedule_result);
+              last_results_[schedule_result.processor] = schedule_result;
             }
-
-          TRACE (*task_it << " -> " << r.processor);
+          
+          
+          TRACE (*task_it << " -> " << schedule_result.processor);
         }
     }
 
@@ -98,8 +129,60 @@ FTRMFF_Bestfit_Algorithm::get_unschedulable ()
   return unschedulable_;
 }
 
-SCHEDULE
+const SCHEDULE &
 FTRMFF_Bestfit_Algorithm::schedule () const
 {
   return scheduler_.schedule ();
 }
+
+struct ScheduleResultComparison : public std::binary_function <
+  RESULT_MAP::value_type, 
+  RESULT_MAP::value_type,
+  bool>
+{
+  bool operator () (const RESULT_MAP::value_type & r1, 
+                    const RESULT_MAP::value_type & r2)
+  {
+    return (r1.second.wcrt < r2.second.wcrt);
+  }
+};
+
+struct ProcessorAccumulator : public std::unary_function <
+  RESULT_MAP::value_type,
+  Processor>
+{
+public:
+  Processor operator () (const RESULT_MAP::value_type & entry)
+  {
+    return entry.second.processor;
+  }
+};
+
+typedef std::pair <Processor, ScheduleResult> RESULT_PAIR;
+
+PROCESSOR_LIST 
+FTRMFF_Bestfit_Algorithm::best_processors (void)
+{
+  TRACE ("last_results: " << last_results_.size ());
+
+  std::vector <RESULT_PAIR> entries;
+  std::copy (last_results_.begin (),
+             last_results_.end (),
+             std::inserter (entries,
+                            entries.begin ()));
+
+  std::sort (entries.begin (),
+             entries.end (),
+             ScheduleResultComparison ());
+
+  TRACE ("entries : " << entries.size ());
+
+  PROCESSOR_LIST result;
+  std::transform (entries.begin (),
+                  entries.end (),
+                  std::inserter (result,
+                                 result.begin ()),
+                  ProcessorAccumulator ());
+
+  return result;
+}
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 31f7e2810ed..15ac9a93051 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.h
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.h
@@ -23,6 +23,8 @@ public:
   virtual FTRMFF_Output operator () (const FTRMFF_Input & input);
 };
 
+typedef std::map <Processor, ScheduleResult> RESULT_MAP;
+
 class FTRMFF_Bestfit_Algorithm : 
   public std::unary_function <TASK_LIST,
                               SCHEDULING_MAP>
@@ -37,10 +39,14 @@ public:
 
   SCHEDULE_PROGRESS_LIST get_unschedulable ();
 
-  SCHEDULE schedule () const;
+  const SCHEDULE & schedule () const;
+
+private:
+  PROCESSOR_LIST best_processors (void);
 
 private:
   SCHEDULE_PROGRESS_LIST unschedulable_;
+  RESULT_MAP last_results_;
   unsigned int consistency_level_;
   Forward_Ranking_Scheduler scheduler_;
 };
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Forward_Ranking_Scheduler.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Forward_Ranking_Scheduler.cpp
index c60dba0d4ce..a2d75406dc7 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Forward_Ranking_Scheduler.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Forward_Ranking_Scheduler.cpp
@@ -83,8 +83,7 @@ Forward_Ranking_Scheduler::schedule_task (const Task & task,
 
   PROCESSOR_SETS failure_scenarios = 
     this->permute_processors (fixed_failures,
-                              additional_failures,
-                              max_failures_ - fixed_failures.size ());
+                              additional_failures);
 
   TRACE ("Relevant Failure Scenarios: " << failure_scenarios);
 
@@ -199,50 +198,63 @@ Forward_Ranking_Scheduler::relevant_processors (
 PROCESSOR_SETS
 Forward_Ranking_Scheduler::permute_processors (
   const PROCESSOR_SET & fixed,
-  const PROCESSOR_SET & exchangeable,
-  unsigned int failure_number)
+  const PROCESSOR_SET & exchangeable)
 {
   PROCESSOR_SETS failure_sets;
-  PROCESSOR_LIST combination;
-  unsigned int tupel_size = 
-    std::min (failure_number,
-              static_cast <unsigned int> (exchangeable.size ()));
-
-  PROCESSOR_SET::iterator it = exchangeable.begin ();
-  for (unsigned int c_index = 0; 
-       c_index < tupel_size; 
-       ++c_index, ++it)
-    {
-      combination.push_back (*it);
-    }
 
-  PROCESSOR_LIST failure_elements;
-  std::copy (exchangeable.begin (),
-             exchangeable.end (),
-             std::inserter (failure_elements,
-                            failure_elements.begin ()));
-
-  do
+  if (fixed.size () == max_failures_)
     {
-      PROCESSOR_SET set;
-      // add a permutation of the relevant failures
-      std::copy (combination.begin (),
-                 combination.end (),
-                 std::inserter (set,
-                                set.begin ()));
-
-      // add the fixed aspects
-      std::copy (fixed.begin (),
-                 fixed.end (),
-                 std::inserter (set,
-                                set.begin ()));
-
-      failure_sets.push_back (set);
+      failure_sets.push_back (fixed);
     }
-  while (next_combination (failure_elements.begin (),
-                           failure_elements.end (),
-                           combination.begin (),
-                           combination.end ()));
+  else 
+    {
+      unsigned int tupel_size = max_failures_ - fixed.size ();
+
+      if (exchangeable.size () < tupel_size)
+        {
+          failure_sets.push_back (exchangeable);
+        }
+      else
+        {
+          PROCESSOR_LIST combination;
+
+          PROCESSOR_SET::iterator it = exchangeable.begin ();
+          for (unsigned int c_index = 0; 
+               c_index < tupel_size; 
+               ++c_index, ++it)
+            {
+              combination.push_back (*it);
+            }
+
+          PROCESSOR_LIST failure_elements;
+          std::copy (exchangeable.begin (),
+                     exchangeable.end (),
+                     std::inserter (failure_elements,
+                                    failure_elements.begin ()));
+
+          do
+            {
+              PROCESSOR_SET set;
+              // add a permutation of the relevant failures
+              std::copy (combination.begin (),
+                         combination.end (),
+                         std::inserter (set,
+                                        set.begin ()));
+              
+              // add the fixed aspects
+              std::copy (fixed.begin (),
+                         fixed.end (),
+                         std::inserter (set,
+                                        set.begin ()));
+
+              failure_sets.push_back (set);
+            }
+          while (next_combination (failure_elements.begin (),
+                                   failure_elements.end (),
+                                   combination.begin (),
+                                   combination.end ()));
+        } // end else if x > y
+    } // end else w != y
 
   return failure_sets;
 }
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Forward_Ranking_Scheduler.h b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Forward_Ranking_Scheduler.h
index 9c4adb0e0b5..f5fa786790f 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Forward_Ranking_Scheduler.h
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Forward_Ranking_Scheduler.h
@@ -66,8 +66,7 @@ private:
                                      const PROCESSOR_SET & ignored_processors);
 
   PROCESSOR_SETS permute_processors (const PROCESSOR_SET & fixed,
-                                     const PROCESSOR_SET & exchangeable,
-                                     unsigned int failure_number);
+                                     const PROCESSOR_SET & exchangeable);
 
   double accumulate_wcrt (const TASK_LIST & tasks,
                           const PROCESSOR_SETS & scenarios);
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.cpp
index 6259c589785..40833017462 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.cpp
@@ -51,6 +51,19 @@ Scheduler::operator () (const Task & task)
   return result;  
 }
 
+ScheduleResult 
+Scheduler::operator () (const Task & task,
+                        const Processor & processor)
+{
+  ScheduleResult result;
+  result.task = task;
+  result.processor = processor;
+  result.wcrt = this->schedule_task (task, processor);
+    
+  return result;
+}
+
+
 void
 Scheduler::update_schedule (const ScheduleResult & result)
 {
@@ -82,7 +95,7 @@ Scheduler::update_replica_groups (const ScheduleResult & result)
   TRACE (replica_groups_);
 }
 
-SCHEDULE
+const SCHEDULE &
 Scheduler::schedule (void) const
 {
   return schedule_;
@@ -120,9 +133,6 @@ ReplicaFinder::operator () (const Task & task) const
 {
   PROCESSOR_SET result;
 
-  TRACE ("TEST");
-  TRACE (rep_groups_);
-  
   REPLICA_GROUPS::const_iterator replicas = 
     rep_groups_.find (primary_name (task));
   
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.h b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.h
index 66b82213b66..0794641d6b4 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.h
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.h
@@ -37,12 +37,16 @@ public:
   // If the WCRT response time is 0, it is not schedulable.
   ScheduleResult operator () (const Task & task);
 
+  // tries to schedule a task on a specific processor
+  ScheduleResult operator () (const Task & task,
+                              const Processor & processor);
+
   // this needs to be implemented by each scheduling algorithm
   virtual double schedule_task (const Task & task, 
                                 const Processor & processor) = 0;
 
   // getter method for the schedule
-  SCHEDULE schedule () const;
+  const SCHEDULE & schedule () const;
 
   virtual void update_schedule (const ScheduleResult & result);