finished checking algorithm

7 files changed, 122 insertions, 184 deletions

diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.cpp
index 3462fc5f810..e34330489d5 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Algorithms.cpp
@@ -70,7 +70,7 @@ std::ostream & operator<< (std::ostream & ostr, const Task & t)
        << t.period
        << ","
        << t.sync_time
-       << (t.role == PRIMARY ? ",p" : ",b")
+//       << (t.role == PRIMARY ? ",p" : ",b")
        << ")";
 
   return ostr;
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
index 6f3357d4a96..c6e3151ce16 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
@@ -186,6 +186,7 @@ project (forward_ranking_ftrmff) {
     CTT_Basic.cpp
     CTT_Enhanced.cpp
     Scheduler.cpp
+    FailureAwareWCRT.cpp
     Packing_Scheduler.cpp
     Forward_Ranking_Scheduler.cpp
     FTRMFF_Forward_Packing.cpp
@@ -205,6 +206,8 @@ project (schedulability_check) : acelib {
     Schedule.cpp
     CTT_Enhanced.cpp
     CTT_Basic.cpp 
+    Scheduler.cpp
+    FailureAwareWCRT.cpp
     schedulability_check.cpp
   }
 }
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 40b64bcfba9..72427628806 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
@@ -12,33 +12,8 @@
 
 #include <numeric>
 #include "Forward_Ranking_Scheduler.h"
+#include "FailureAwareWCRT.h"
 #include "Combination_T.h"
-#include "CTT_Enhanced.h"
-
-ReplicaFinder::ReplicaFinder (const REPLICA_GROUPS & rep_groups)
-  : rep_groups_ (rep_groups) 
-{
-}
-
-PROCESSOR_SET 
-ReplicaFinder::operator () (const Task & task)
-{
-  PROCESSOR_SET result;
-  
-  REPLICA_GROUPS::const_iterator replicas = 
-    rep_groups_.find (primary_name (task));
-  
-  if (replicas != rep_groups_.end ())
-    {
-      std::transform (replicas->second.begin (),
-                      replicas->second.begin () + task.rank,
-                      std::inserter (result,
-                                     result.begin ()),
-                      processor_picker_);
-    }
-  
-  return result;
-}
 
 FailureMapFinder::FailureMapFinder (const FAILURE_MAP & failure_map)
   : failure_map_ (failure_map)
@@ -106,13 +81,8 @@ Forward_Ranking_Scheduler::schedule_task (const Task & task,
 
   TRACE ("Relevant Failure Scenarios: " << failure_scenarios);
 
-  TASK_SCENARIOS activation_scenarios = 
-    this->activate_tasks (local_tasks,
-                          failure_scenarios);
-
-  TRACE ("Task Scenarios: " << activation_scenarios);
-
-  double wcrt = this->accumulate_wcrt (activation_scenarios);
+  double wcrt = this->accumulate_wcrt (local_tasks,
+                                       failure_scenarios);
 
   TRACE ("Maximum wcrt: " << wcrt);
 
@@ -278,123 +248,15 @@ Forward_Ranking_Scheduler::permute_processors (
   return failure_sets;
 }
 
-class ActivateFailedTask : public std::unary_function <PROCESSOR_SET,
-                                                       Task>
-{
-public:
-  ActivateFailedTask (const PROCESSOR_SET & failures,
-                      const REPLICA_GROUPS & rep_groups)
-    : failures_ (failures),      
-      rep_groups_ (rep_groups),
-      find_replicas_ (rep_groups) {}
-
-  Task operator () (const Task & task)
-  {
-    // check in the replica map if all previous tasks get activated
-    // and switch the task to primary if this is the case
-    PROCESSOR_SET necessary_failures = find_replicas_ (task);
-
-    PROCESSOR_SET difference;
-    std::set_intersection (failures_.begin (),
-                           failures_.end (),
-                           necessary_failures.begin (),
-                           necessary_failures.end (),
-                           std::inserter (difference,
-                                          difference.begin ()));
-
-    // If all necessary processors are failing, make the task primary.
-    // This is the case if all necessary_failures are contained in the
-    // difference set.
-    if (difference.size () == necessary_failures.size ())
-      return convert_ (task);
-
-    return task;
-  }
-
-private:
-  const PROCESSOR_SET & failures_;
-  const REPLICA_GROUPS & rep_groups_;
-  PrimaryConversion convert_;
-  ReplicaFinder find_replicas_;
-};
-
-class ActivateFailedTasks : public std::unary_function <PROCESSOR_SET,
-                                                        TASK_LIST>
-{
-public:
-  ActivateFailedTasks (const TASK_LIST & tasks,
-                       const REPLICA_GROUPS & rep_groups)
-    : tasks_ (tasks),
-      rep_groups_ (rep_groups){}
-
-  TASK_LIST operator () (const PROCESSOR_SET & scenario)
-  {
-    TASK_LIST result;
-
-    // for each backup check whether it is activated
-    std::transform (tasks_.begin (),
-                    tasks_.end (),
-                    std::inserter (result,
-                                   result.begin ()),
-                    ActivateFailedTask (scenario,
-                                        rep_groups_));
-
-    return result;
-  }
-
-private:
-  const TASK_LIST & tasks_;
-  const REPLICA_GROUPS & rep_groups_;
-};
-
-TASK_SCENARIOS 
-Forward_Ranking_Scheduler::activate_tasks (const TASK_LIST & tasks,
-                                           const PROCESSOR_SETS & failures)
-{
-  TASK_SCENARIOS result;
-
-  // add an empty one for the primary case
-  result.push_back (tasks);
-
-  // add a case for each failure scenario
-  std::transform (failures.begin (),
-                  failures.end (),
-                  std::inserter (result,
-                                 result.begin ()),
-                  ActivateFailedTasks (tasks,
-                                       replica_groups_));
-
-  return result;
-}
-
-class WCRTAccumulator : public std::binary_function <double,
-                                                     TASK_LIST,
-                                                     double>
-{
-public:
-  double operator () (double previous,
-                      const TASK_LIST & tasks)
-  {
-    double result = ctt_ (tasks);
-
-    if ((result > .0) && (previous != .0))
-      return std::max(result,
-                      previous);
-    else
-      return .0;
-  }
-
-private:
-  CTT_Enhanced ctt_;
-};
-
 double
-Forward_Ranking_Scheduler::accumulate_wcrt (const TASK_SCENARIOS & scenarios)
+Forward_Ranking_Scheduler::accumulate_wcrt (const TASK_LIST & tasks,
+                                            const PROCESSOR_SETS & scenarios)
 {
   return std::accumulate (scenarios.begin (),
                           scenarios.end (),
                           -1.0,
-                          WCRTAccumulator ());
+                          FailureAwareWCRT (tasks,
+                                            replica_groups_));
 }
 
 std::ostream & operator<< (std::ostream & ostr, 
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 911dd4acf08..6dc20e8ac92 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
@@ -18,26 +18,6 @@
 typedef std::map <Taskname, PROCESSOR_SET> FAILURE_MAP;
 
 /**
- * @class ReplicaFinder
- *
- * @brief Functor that uses the replica group to determine the
- *        processors that need to fail in order for a given backup
- *        task to become active
- */
-class ReplicaFinder : public std::unary_function <Task,
-                                                  PROCESSOR_SET>
-{
-public:
-  ReplicaFinder (const REPLICA_GROUPS & rep_groups);
-
-  PROCESSOR_SET operator () (const Task & task);
-
-private:
-  const REPLICA_GROUPS rep_groups_;
-  ProcessorPicker processor_picker_;
-};
-
-/**
  * @class FailureMapFinder
  *
  * @brief Functor that uses the replica group to determine the
@@ -86,10 +66,8 @@ private:
                                      const PROCESSOR_SET & exchangeable,
                                      unsigned int failure_number);
 
-  TASK_SCENARIOS activate_tasks (const TASK_LIST & tasks,
-                                 const PROCESSOR_SETS & failures);
-
-  double accumulate_wcrt (const TASK_SCENARIOS & scenarios);
+  double accumulate_wcrt (const TASK_LIST & tasks,
+                          const PROCESSOR_SETS & scenarios);
 
 private:
   FAILURE_MAP failure_map_;
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.cpp
index 124d849f263..b94f03fa0e8 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.cpp
@@ -97,17 +97,42 @@ ProcessorNameComparison::ProcessorNameComparison (const Processor & p)
 {
 }
 
+bool
+ProcessorNameComparison::operator () (bool equal, 
+                                      const TASK_POSITIONS::value_type & pos)
+{
+  return (equal || (pos.first.compare (p_) == 0));
+}
+
 Processor 
 ProcessorPicker::operator () (const TASK_POSITIONS::value_type & entry)
 {
   return entry.first;
 }
 
-bool
-ProcessorNameComparison::operator () (bool equal, 
-                                      const TASK_POSITIONS::value_type & pos)
+ReplicaFinder::ReplicaFinder (const REPLICA_GROUPS & rep_groups)
+  : rep_groups_ (rep_groups) 
 {
-  return (equal || (pos.first.compare (p_) == 0));
+}
+
+PROCESSOR_SET 
+ReplicaFinder::operator () (const Task & task)
+{
+  PROCESSOR_SET result;
+  
+  REPLICA_GROUPS::const_iterator replicas = 
+    rep_groups_.find (primary_name (task));
+  
+  if (replicas != rep_groups_.end ())
+    {
+      std::transform (replicas->second.begin (),
+                      replicas->second.begin () + task.rank,
+                      std::inserter (result,
+                                     result.begin ()),
+                      processor_picker_);
+    }
+  
+  return result;
 }
 
 std::ostream & operator<< (std::ostream & ostr, 
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.h b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.h
index 10c9acbf6d6..cd2ff76f241 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.h
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/Scheduler.h
@@ -91,6 +91,26 @@ public:
   Processor operator () (const TASK_POSITIONS::value_type & entry);
 };
 
+/**
+ * @class ReplicaFinder
+ *
+ * @brief Functor that uses the replica group to determine the
+ *        processors that need to fail in order for a given backup
+ *        task to become active
+ */
+class ReplicaFinder : public std::unary_function <Task,
+                                                  PROCESSOR_SET>
+{
+public:
+  ReplicaFinder (const REPLICA_GROUPS & rep_groups);
+
+  PROCESSOR_SET operator () (const Task & task);
+
+private:
+  const REPLICA_GROUPS rep_groups_;
+  ProcessorPicker processor_picker_;
+};
+
 // streaming operators for used data structures
 std::ostream & operator<< (std::ostream & ostr, 
                            const TASK_POSITION & tp);
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/schedulability_check.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/schedulability_check.cpp
index 80e570dde1e..0cbe63bb783 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/schedulability_check.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/schedulability_check.cpp
@@ -17,6 +17,8 @@
 #include "Scheduler.h"
 #include "CTT_Enhanced.h"
 #include "CTT_Basic.h"
+#include "FailureAwareWCRT.h"
+#include "Combination_T.h"
 #include <ace/Get_Opt.h>
 
 std::string filename = "test.sd"; // filename of task list input
@@ -31,8 +33,10 @@ class ScheduleChecker : public std::binary_function <double,
 {
 public:
   ScheduleChecker (const SCHEDULE & schedule)
-    : schedule_ (schedule)
+    : schedule_ (schedule)      
   {
+    max_rank_ = this->max_rank ();
+
     // build replica_groups data structure
     for (SCHEDULE::const_iterator sched_it = schedule.begin ();
          sched_it != schedule.end ();
@@ -66,9 +70,13 @@ public:
   {
     PROCESSOR_SETS scenarios = 
       this->calculate_failure_scenarions (entry.first,
-                                          this->max_rank ());
+                                          max_rank_);
 
-    return .0;
+    return std::accumulate (scenarios.begin (),
+                            scenarios.end (),
+                            -1.0,
+                            FailureAwareWCRT (entry.second,
+                                              replica_groups_));
   }
 
 private:
@@ -78,6 +86,41 @@ private:
     PROCESSOR_SETS result;
     PROCESSOR_LIST all_processors = get_processors (schedule_, true);
 
+    // remove current processor
+    PROCESSOR_LIST::iterator myprocessor = std::find (all_processors.begin (),
+                                                      all_processors.end (),
+                                                      processor);
+    
+    all_processors.erase (myprocessor);
+
+    unsigned int tupel_size = std::min (consistency_level,
+                                        (unsigned int) all_processors.size ());
+
+    PROCESSOR_LIST combination;
+    PROCESSOR_LIST::iterator it = all_processors.begin ();
+    for (unsigned int c_index = 0; 
+         c_index < tupel_size; 
+         ++c_index, ++it)
+      {
+        combination.push_back (*it);
+      }
+
+    do
+      {
+        PROCESSOR_SET set;
+        // add a permutation of the relevant failures
+        std::copy (combination.begin (),
+                   combination.end (),
+                   std::inserter (set,
+                                  set.begin ()));
+
+        result.push_back (set);
+      }
+    while (next_combination (all_processors.begin (),
+                             all_processors.end (),
+                             combination.begin (),
+                             combination.end ()));
+
     return result;
   }
 
@@ -104,6 +147,7 @@ private:
 private:
   const SCHEDULE & schedule_;
   REPLICA_GROUPS replica_groups_;
+  unsigned int max_rank_;
 };
 
 static int
@@ -199,17 +243,23 @@ int main (int argc, char *argv[])
 
       SCHEDULE min_schedule;
       SCHEDULE::const_iterator schedule_it = schedule.begin ();
-      for (unsigned long i = 0; i < usage; ++i)
+      for (unsigned long i = 0; i < usage; ++i, ++schedule_it)
         {
           min_schedule.insert (*schedule_it);
         }
 
-      std::map <Processor, double> wcrts;
-
-      double wcrt = std::accumulate (min_schedule.begin (),
-                                     min_schedule.end (),
-                                     -1.0,
-                                     ScheduleChecker (min_schedule));
+      ScheduleChecker checker (min_schedule);
+      double wcrt = -1.0;
+      for (SCHEDULE::iterator it = min_schedule.begin ();
+           it != min_schedule.end ();
+           ++it)
+        {
+          wcrt = checker (wcrt, *it);
+          if (wcrt > .0)
+            DBG_OUT (it->first << ": " << "(" << wcrt << "," << (--(it->second.end ()))->period << ")");
+          else
+            DBG_OUT (it->first << ": not schedulable");
+        }
       
       return wcrt > .0;
     } // end else counting_mode not true