Implement timeout in BaruahGEDF

Give up after running for 5 seconds. This is almost never triggered, but once in a while
this should help to catch a pseudo-polynomial excursion.

5 files changed, 49 insertions, 14 deletions

diff --git a/native/SConstruct b/native/SConstruct
index 797eaba..99cb6b4 100644
--- a/native/SConstruct
+++ b/native/SConstruct
@@ -110,6 +110,7 @@ swig.Append(
 )
 
 EDF_SRC = [
+    'src/cpu_time.cpp',
     'src/edf/baker.cpp',
     'src/edf/baruah.cpp',
     'src/edf/gfb.cpp',
@@ -132,4 +133,4 @@ gmp.Program('testmain', ['src/testmain.cpp',
 
 swig.SharedLibrary('_sched.so', ['src/tasks.cpp', 'interface/sched.i'] + EDF_SRC)
 swig.SharedLibrary('_locking.so', ['src/sharedres.cpp', 'interface/locking.i'])
-swig.SharedLibrary('_sim.so', ['src/tasks.cpp', 'interface/sim.i'] + SCHED_SRC)
\ No newline at end of file
+swig.SharedLibrary('_sim.so', ['src/tasks.cpp', 'interface/sim.i'] + SCHED_SRC)
diff --git a/native/include/cpu_time.h b/native/include/cpu_time.h
new file mode 100644
index 0000000..2484159
--- /dev/null
+++ b/native/include/cpu_time.h
@@ -0,0 +1,7 @@
+#ifndef CPU_TIME_H
+#define CPU_TIME_H
+
+// How much CPU time used (in seconds)?
+double get_cpu_usage(void);
+
+#endif
diff --git a/native/include/edf/baruah.h b/native/include/edf/baruah.h
index dcd4f14..c79b49d 100644
--- a/native/include/edf/baruah.h
+++ b/native/include/edf/baruah.h
@@ -23,7 +23,7 @@ public:
 
     bool is_schedulable(const TaskSet &ts, bool check_preconditions = true);
 
-    static const float MINIMUM_SLACK;
+    static const double MAX_RUNTIME;
 };
 
 #endif
diff --git a/native/src/cpu_time.cpp b/native/src/cpu_time.cpp
new file mode 100644
index 0000000..a7dfa6d
--- /dev/null
+++ b/native/src/cpu_time.cpp
@@ -0,0 +1,25 @@
+
+#include <sys/time.h>
+#include <sys/resource.h>
+
+#include "cpu_time.h"
+
+#ifdef RUSAGE_THREAD
+// This is a Linuxism...
+#define ACCOUNTING_SCOPE RUSAGE_THREAD
+#else
+// This is POSIX.
+#define ACCOUNTING_SCOPE RUSAGE_SELF
+#endif
+
+double get_cpu_usage(void)
+{
+        struct rusage u;
+        if (getrusage(ACCOUNTING_SCOPE, &u) == 0)
+        {
+                return u.ru_utime.tv_sec + u.ru_utime.tv_usec / 1E6;
+        }
+        else
+                return 0.0;
+}
+
diff --git a/native/src/edf/baruah.cpp b/native/src/edf/baruah.cpp
index a8d78d8..c4b16af 100644
--- a/native/src/edf/baruah.cpp
+++ b/native/src/edf/baruah.cpp
@@ -10,9 +10,12 @@
 #include <iostream>
 #include "task_io.h"
 
+#include "cpu_time.h"
+
 using namespace std;
 
-const float BaruahGedf::MINIMUM_SLACK = 0.01;
+const double BaruahGedf::MAX_RUNTIME = 5.0; /* seconds */
+
 
 static void demand_bound_function(const Task &tsk,
                                   const mpz_class &t,
@@ -253,22 +256,13 @@ bool BaruahGedf::is_schedulable(const TaskSet &ts,
             return true;
     }
 
-    /* Always check for too-small rest utilizations, as they
-     * create unmanagably-large testing intervals. We'll just
-     * enforce a minimum slack threshold here. */
+    double start_time = get_cpu_usage();
+
     mpq_class m_minus_u;
     ts.get_utilization(m_minus_u);
     m_minus_u *= -1;
     m_minus_u += m;
 
-    /*
-    if (m_minus_u < MINIMUM_SLACK) {
-        cerr << "# BaruahGedf: skipping task test; slack = " << m_minus_u
-             << endl;
-        return false;
-    }
-    */
-
     mpz_class i1, sum;
     mpz_class *max_test_point, *idiff;
     mpz_class** ptr; // indirect access to idiff
@@ -292,9 +286,17 @@ bool BaruahGedf::is_schedulable(const TaskSet &ts,
         all_pts[k].init(ts, k, max_test_point + k);
 
     // for every task for which point <= max_ak
+    unsigned long iter_count = 0;
     while (point_in_range && schedulable)
     {
         point_in_range = false;
+        // check for excessive run time every 10 iterations
+        if (++iter_count % 10 == 0 && get_cpu_usage() > start_time + MAX_RUNTIME)
+        {
+             // This is taking too long. Give up.
+             schedulable = false;
+             break;
+        }
         for (unsigned int k = 0; k < ts.get_task_count() && schedulable; k++)
             if (all_pts[k].get_next(ilen))
             {