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.

2 files changed, 39 insertions, 12 deletions

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))
             {