created alternative fitting criteria for bestfit and worstfit

9 files changed, 337 insertions, 6 deletions

diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/experiments/packing/generate.sh b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/experiments/packing/generate.sh
index a827ad07741..127111ed440 100755
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/experiments/packing/generate.sh
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/experiments/packing/generate.sh
@@ -23,7 +23,7 @@ for TASK_NO in 10 20 40 80 160; do \
     -s $SS_UPPER \
     -z $SS_LOWER > ./$DATA_DIR/$TASK_NO-tasks.input && \
   for BACKUP_NO in 1 2 3 4; do \
-    for ALGORITHM in pftrmff aftrmff frftrmff bsftrmbf bsftrmwf; do \
+    for ALGORITHM in pftrmff aftrmff frftrmff bsftrmbf bsftrmwf bsftrmbfnf bsftrmwfnf; do \
       echo "run $ALGORITHM for $BACKUP_NO backups..." && \
       echo "start $ALGORITHM with $TASK_NO tasks and $BACKUP_NO backups at `date`" >> ./$DATA_DIR/timing.log && \
       $DECORAM_BIN/$ALGORITHM \
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/experiments/packing/processor_util.sh b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/experiments/packing/processor_util.sh
index 2261445bbd7..dc6a79241d1 100755
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/experiments/packing/processor_util.sh
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/experiments/packing/processor_util.sh
@@ -7,7 +7,7 @@ RESULT_DIR=$DATA_DIR/$EXPERIMENT_NAME
 if [ ! -d ./$DATA_DIR ]; then echo Directory $DATA_DIR does not exist && exit; fi
 if [ ! -d ./$RESULT_DIR ]; then mkdir -p ./$RESULT_DIR; fi
 
-for ALGORITHM in pftrmff aftrmff frftrmff bsftrmbf bsftrmwf; do \
+for ALGORITHM in pftrmff aftrmff frftrmff bsftrmbf bsftrmwf bsftrmbfnf bsftrmwfnf; do \
   for TASK_NO in 10 20 40 80 160; do \
     echo "$TASK_NO tasks:" >> ./$RESULT_DIR/$EXPERIMENT_NAME-$ALGORITHM.dat && \
     for BACKUP_NO in 1 2 3 4; do \
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/experiments/packing/schedulability.sh b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/experiments/packing/schedulability.sh
index b50e20a1c4e..2a9d0572fde 100755
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/experiments/packing/schedulability.sh
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/experiments/packing/schedulability.sh
@@ -7,7 +7,7 @@ RESULT_DIR=$DATA_DIR/$EXPERIMENT_NAME
 if [ ! -d ./$DATA_DIR ]; then echo Directory $DATA_DIR does not exist && exit; fi
 if [ ! -d ./$RESULT_DIR ]; then mkdir -p ./$RESULT_DIR; fi
 
-for ALGORITHM in pftrmff aftrmff frftrmff bsftrmbf bsftrmwf; do \
+for ALGORITHM in pftrmff aftrmff frftrmff bsftrmbf bsftrmwf bsftrmbfnf bsftrmwfnf; do \
   for TASK_NO in 10 20 40 80 160; do \
     echo "$TASK_NO tasks:" >> ./$RESULT_DIR/$EXPERIMENT_NAME-$ALGORITHM.dat && \
     for BACKUP_NO in 1 2 3 4; do \
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
index fe4bd5b829c..a83046262f8 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/DeCoRAM.mpc
@@ -167,6 +167,62 @@ project (binary_bestfit_ftrmff) : acelib {
   }
 }
 
+project (binary_bestfit_nofailure_ftrmff) : acelib {
+
+  exename = bsftrmbfnf
+  exeout = ../bin
+
+  macros += DO_DEBUG
+
+  Source_Files {
+    Algorithms.cpp
+    Schedule.cpp
+    Scheduler.cpp
+    CTT_Basic.cpp
+    CTT_Enhanced.cpp
+    Task_Scheduler.cpp
+    Forward_Ranking_Scheduler.cpp
+    Utilization_Ranking.cpp
+    OptimizedWCRT.cpp
+    RankedWCRT.cpp
+    FailureAwareWCRT.cpp
+    Simple_Ranking.cpp
+    FTRMFF_Worstfit.cpp
+    FTRMFF_Bestfit.cpp
+    FTRMFF_Binary_Search.cpp
+    FTRMFF_Basic.cpp
+    binary_bestfit_nonfailure_ftrmff.cpp
+  }
+}
+
+project (binary_worstfit_nofailure_ftrmff) : acelib {
+
+  exename = bsftrmwfnf
+  exeout = ../bin
+
+  macros += DO_DEBUG
+
+  Source_Files {
+    Algorithms.cpp
+    Schedule.cpp
+    Scheduler.cpp
+    CTT_Basic.cpp
+    CTT_Enhanced.cpp
+    Task_Scheduler.cpp
+    Forward_Ranking_Scheduler.cpp
+    Utilization_Ranking.cpp
+    OptimizedWCRT.cpp
+    RankedWCRT.cpp
+    FailureAwareWCRT.cpp
+    Simple_Ranking.cpp
+    FTRMFF_Worstfit.cpp
+    FTRMFF_Bestfit.cpp
+    FTRMFF_Binary_Search.cpp
+    FTRMFF_Basic.cpp
+    binary_worstfit_nonfailure_ftrmff.cpp
+  }
+}
+
 project (backward_packing_ftrmff) {
 
   exename = bpftrmff
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 abd56c6ddb6..d01c8b7c123 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.cpp
@@ -15,6 +15,51 @@
 
 #include "Forward_Ranking_Scheduler.h"
 #include "Packing_Scheduler.h"
+#include "CTT_Enhanced.h"
+
+class FailureResultUpdater : public ResultUpdater
+{
+public:
+  FailureResultUpdater (RESULT_MAP & result_map)
+    : ResultUpdater (result_map)
+  {
+  }
+
+  virtual void operator () (const ScheduleResult & result)
+  {
+    result_map_[result.processor] = result;
+  }
+};
+
+class NonFailureResultUpdater : public ResultUpdater
+{
+public:
+  NonFailureResultUpdater (RESULT_MAP & result_map,
+                           const SCHEDULE & schedule)
+    : ResultUpdater (result_map),
+      schedule_ (schedule)
+  {
+  }
+
+  virtual void operator () (const ScheduleResult & result)
+  {
+    ScheduleResult modified_result = result;
+    // calculate response time in non-failure case using the enhanced
+    // ctt algorithm.
+    SCHEDULE::const_iterator entry = schedule_.find (result.processor);
+
+    if (entry != schedule_.end ())
+      {
+        modified_result.wcrt = ctt_ (entry->second);
+      }
+
+    // add modified result to the mao
+    result_map_[result.processor] = modified_result;
+  }
+private:
+  const SCHEDULE & schedule_;
+  CTT_Enhanced ctt_;
+};
 
 FTRMFF_Bestfit::~FTRMFF_Bestfit ()
 {
@@ -38,7 +83,8 @@ FTRMFF_Bestfit::operator () (const FTRMFF_Input & input)
 FTRMFF_Bestfit_Algorithm::FTRMFF_Bestfit_Algorithm (
   const PROCESSOR_LIST & processors,
   unsigned int consistency_level,
-  bool bestfit)
+  bool bestfit,
+  bool weight_for_failure_case)
   : FTRMFF_Algorithm_Impl (consistency_level),
     scheduler_ (processors,
                 consistency_level_),
@@ -56,6 +102,16 @@ FTRMFF_Bestfit_Algorithm::FTRMFF_Bestfit_Algorithm (
       result.processor = *it;
       last_results_[*it] = result;
     }
+
+  if(weight_for_failure_case)
+    {
+      result_updater_.reset (new FailureResultUpdater (last_results_));
+    }
+  else
+    {
+      result_updater_.reset (new NonFailureResultUpdater (last_results_, 
+                                                          scheduler_.schedule ()));
+    }
 }
 
 FTRMFF_Bestfit_Algorithm::~FTRMFF_Bestfit_Algorithm ()
@@ -112,7 +168,7 @@ FTRMFF_Bestfit_Algorithm::operator () (const TASK_LIST & tasks)
           else
             {
               scheduler_.update_schedule (schedule_result);
-              last_results_[schedule_result.processor] = schedule_result;
+              (*result_updater_) (schedule_result);
             }
           
           
@@ -197,3 +253,12 @@ FTRMFF_Bestfit_Algorithm::best_processors (void)
 
   return result;
 }
+
+ResultUpdater::ResultUpdater (RESULT_MAP & result_map)
+  : result_map_ (result_map)
+{
+}
+
+ResultUpdater::~ResultUpdater (void)
+{
+}
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 7c306265539..78b1457e7a8 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.h
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Bestfit.h
@@ -25,13 +25,30 @@ public:
 
 typedef std::map <Processor, ScheduleResult> RESULT_MAP;
 
+// This abstract base class allows for different strategies to weight
+// the processors for best-fit
+class ResultUpdater : public std::unary_function <ScheduleResult,
+                                                  void>
+{
+public:
+  ResultUpdater (RESULT_MAP & result_map);
+
+  virtual ~ResultUpdater (void);
+
+  virtual void operator () (const ScheduleResult & result) = 0;
+
+protected:
+  RESULT_MAP & result_map_;
+};
+
 class FTRMFF_Bestfit_Algorithm : 
   public FTRMFF_Algorithm_Impl
 {
 public:
   FTRMFF_Bestfit_Algorithm (const PROCESSOR_LIST & processors,
                             unsigned int consistency_level,
-                            bool bestfit = true);
+                            bool bestfit = true,
+                            bool weight_for_failure_case = true);
 
   virtual ~FTRMFF_Bestfit_Algorithm ();
 
@@ -46,6 +63,7 @@ private:
   RESULT_MAP last_results_;
   Forward_Ranking_Scheduler scheduler_;
   bool bestfit_;
+  std::auto_ptr<ResultUpdater> result_updater_;
 };
 
 #endif /* FTRMFF_BEST_FIT_ALGORITHM_H_ */
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
index e652209892a..d889171b12a 100644
--- a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.cpp
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/FTRMFF_Binary_Search.cpp
@@ -166,6 +166,16 @@ FTRMFF_Binary_Search_Algorithm::create_scheduling_algorithm (
     return new FTRMFF_Bestfit_Algorithm (processors,
                                          consistency_level_,
                                          false);
+  else if (scheduling_algorithm_ == "bestfit-nofailure")
+    return new FTRMFF_Bestfit_Algorithm (processors,
+                                         consistency_level_,
+                                         true,
+                                         false);
+  else if (scheduling_algorithm_ == "worstfit-nofailure")
+    return new FTRMFF_Bestfit_Algorithm (processors,
+                                         consistency_level_,
+                                         false,
+                                         false);
   else // this algorithm is outdated
     return new FTRMFF_Worstfit_Algorithm (processors,
                                           consistency_level_);
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/binary_bestfit_nonfailure_ftrmff.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/binary_bestfit_nonfailure_ftrmff.cpp
new file mode 100644
index 00000000000..fe25f051b32
--- /dev/null
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/binary_bestfit_nonfailure_ftrmff.cpp
@@ -0,0 +1,91 @@
+// -*- C++ -*-
+
+//=============================================================================
+/**
+ *  @file    binary_ftrmff.cpp
+ *
+ *  $Id$
+ *
+ *  @author  Friedhelm Wolf (fwolf@dre.vanderbilt.edu)
+ */
+//=============================================================================
+
+#include <fstream>
+#include <sstream>
+#include <iostream>
+#include <ace/Get_Opt.h>
+#include "FTRMFF_Binary_Search.h"
+
+std::string filename = "test.sd"; // filename of task list input
+unsigned int m = 4; // number of processors
+unsigned int c = 2; // consitency level
+
+int ACE_TMAIN (int argc, ACE_TCHAR *argv[])
+{
+  if (argc > 1)
+    filename = argv[1];
+
+  if (argc > 2)
+    m = atoi (argv[2]);
+
+  if (argc > 3)
+    c = atoi (argv[3]);
+
+  TASK_LIST tasks;
+  PROCESSOR_LIST procs;
+  for (unsigned int i = 1; i <= m; ++i)
+    {
+      std::stringstream ss;
+      ss << "P";
+      if (i < 10)
+        ss << "00";
+      else if (i < 100)
+        ss << "0";
+      ss << i;
+      procs.push_back (ss.str ());
+    }
+
+  std::ifstream ifile;
+  ifile.open (filename.c_str ());
+
+  std::transform (
+    std::istream_iterator <std::string> (ifile),
+    std::istream_iterator <std::string> (),
+    std::inserter <TASK_LIST> (tasks,
+                               tasks.begin ()),
+    string_to_task ());
+  
+  ifile.close ();
+
+  FTRMFF_Binary_Search ftrmff ("bestfit-nofailure");
+
+  FTRMFF_Input input;
+  input.tasks = tasks;
+  input.processors = procs;
+  input.backup_count = c;
+  FTRMFF_Output result = ftrmff (input);
+
+#if 0
+  for (SCHEDULING_MAP::iterator it = result.schedule.begin ();
+       it != result.schedule.end ();
+       ++it)
+    {
+      std::cout << it->first << " -> " 
+                << it->second.processor 
+                << " (" << it->second.priority << ")" 
+                << std::endl;
+    }
+#endif
+
+  if (result.unscheduled_tasks.size () > 0)
+    {
+      std::cout << "Could not schedule :"
+                << std::endl
+                << result.unscheduled_tasks
+                << std::endl;
+
+      return 1;
+    }
+
+  return 0;
+}
diff --git a/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/binary_worstfit_nonfailure_ftrmff.cpp b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/binary_worstfit_nonfailure_ftrmff.cpp
new file mode 100644
index 00000000000..25a2abc1ca4
--- /dev/null
+++ b/TAO/orbsvcs/examples/FaultTolerance/FLARe/DeCoRAM/src/binary_worstfit_nonfailure_ftrmff.cpp
@@ -0,0 +1,91 @@
+// -*- C++ -*-
+
+//=============================================================================
+/**
+ *  @file    binary_ftrmff.cpp
+ *
+ *  $Id$
+ *
+ *  @author  Friedhelm Wolf (fwolf@dre.vanderbilt.edu)
+ */
+//=============================================================================
+
+#include <fstream>
+#include <sstream>
+#include <iostream>
+#include <ace/Get_Opt.h>
+#include "FTRMFF_Binary_Search.h"
+
+std::string filename = "test.sd"; // filename of task list input
+unsigned int m = 4; // number of processors
+unsigned int c = 2; // consitency level
+
+int ACE_TMAIN (int argc, ACE_TCHAR *argv[])
+{
+  if (argc > 1)
+    filename = argv[1];
+
+  if (argc > 2)
+    m = atoi (argv[2]);
+
+  if (argc > 3)
+    c = atoi (argv[3]);
+
+  TASK_LIST tasks;
+  PROCESSOR_LIST procs;
+  for (unsigned int i = 1; i <= m; ++i)
+    {
+      std::stringstream ss;
+      ss << "P";
+      if (i < 10)
+        ss << "00";
+      else if (i < 100)
+        ss << "0";
+      ss << i;
+      procs.push_back (ss.str ());
+    }
+
+  std::ifstream ifile;
+  ifile.open (filename.c_str ());
+
+  std::transform (
+    std::istream_iterator <std::string> (ifile),
+    std::istream_iterator <std::string> (),
+    std::inserter <TASK_LIST> (tasks,
+                               tasks.begin ()),
+    string_to_task ());
+  
+  ifile.close ();
+
+  FTRMFF_Binary_Search ftrmff ("worstfit-nofailure");
+
+  FTRMFF_Input input;
+  input.tasks = tasks;
+  input.processors = procs;
+  input.backup_count = c;
+  FTRMFF_Output result = ftrmff (input);
+
+#if 0
+  for (SCHEDULING_MAP::iterator it = result.schedule.begin ();
+       it != result.schedule.end ();
+       ++it)
+    {
+      std::cout << it->first << " -> " 
+                << it->second.processor 
+                << " (" << it->second.priority << ")" 
+                << std::endl;
+    }
+#endif
+
+  if (result.unscheduled_tasks.size () > 0)
+    {
+      std::cout << "Could not schedule :"
+                << std::endl
+                << result.unscheduled_tasks
+                << std::endl;
+
+      return 1;
+    }
+
+  return 0;
+}