Add QPA EDF uniprocessor test

Based on Zhang and Burns (2009), "Schedulability Analysis for Real-Time Systems with EDF Scheduling", IEEE Transactions on Computers, Vol 58, No 9.

5 files changed, 205 insertions, 1 deletions

diff --git a/native/Makefile b/native/Makefile
index 6fb9c16..d9bfa1f 100644
--- a/native/Makefile
+++ b/native/Makefile
@@ -63,7 +63,8 @@ vpath %.cpp src src/edf src/blocking
 
 # #### Common C++ source files ####
 
-EDF_OBJ   = baker.o baruah.o gfb.o bcl.o bcl_iterative.o rta.o ffdbf.o gedf.o gel_pl.o load.o cpu_time.o
+EDF_OBJ   = baker.o baruah.o gfb.o bcl.o bcl_iterative.o rta.o
+EDF_OBJ  += ffdbf.o gedf.o gel_pl.o load.o cpu_time.o qpa.o
 SCHED_OBJ = sim.o schedule_sim.o
 CORE_OBJ  = tasks.o
 SYNC_OBJ  = sharedres.o dpcp.o mpcp.o
diff --git a/native/include/edf/qpa.h b/native/include/edf/qpa.h
new file mode 100644
index 0000000..18123aa
--- /dev/null
+++ b/native/include/edf/qpa.h
@@ -0,0 +1,16 @@
+#ifndef QPA_H
+#define QPA_H
+
+class QPATest : public SchedulabilityTest
+{
+ private:
+    unsigned int m;
+
+ public:
+    QPATest(unsigned int num_processors);
+
+    bool is_schedulable(const TaskSet &ts, bool check_preconditions = true);
+
+};
+
+#endif
diff --git a/native/include/math-helper.h b/native/include/math-helper.h
index 063558c..850e3a5 100644
--- a/native/include/math-helper.h
+++ b/native/include/math-helper.h
@@ -1,6 +1,8 @@
 #ifndef MATH_HELPER_H
 #define MATH_HELPER_H
 
+#include "time-types.h"
+
 static inline unsigned long divide_with_ceil(unsigned long numer,
                                              unsigned long denom)
 {
@@ -11,4 +13,24 @@ static inline unsigned long divide_with_ceil(unsigned long numer,
                 return (numer / denom) + 1;
 }
 
+
+
+
+static inline integral_t divide_with_ceil(const integral_t &numer,
+                                          const integral_t &denom)
+{
+        integral_t result;
+        mpz_cdiv_q(result.get_mpz_t(), numer.get_mpz_t(), denom.get_mpz_t());
+        return result;
+}
+
+
+static inline integral_t round_up(const fractional_t &f)
+{
+        integral_t result;
+        mpz_cdiv_q(result.get_mpz_t(), f.get_num_mpz_t(), f.get_den_mpz_t());
+        return result * f.get_den();
+}
+
+
 #endif
diff --git a/native/interface/sched.i b/native/interface/sched.i
index d0809b6..238f36e 100644
--- a/native/interface/sched.i
+++ b/native/interface/sched.i
@@ -13,6 +13,7 @@
 #include "edf/load.h"
 #include "edf/gedf.h"
 #include "edf/gel_pl.h"
+#include "edf/qpa.h"
 #include "sharedres.h"
 %}
 
@@ -41,3 +42,4 @@
 #include "edf/load.h"
 #include "edf/gedf.h"
 #include "edf/gel_pl.h"
+#include "edf/qpa.h"
diff --git a/native/src/edf/qpa.cpp b/native/src/edf/qpa.cpp
new file mode 100644
index 0000000..23865ca
--- /dev/null
+++ b/native/src/edf/qpa.cpp
@@ -0,0 +1,163 @@
+#include <algorithm>
+#include <set>
+
+#include <stdlib.h>
+#include "tasks.h"
+#include "math-helper.h"
+#include "stl-helper.h"
+#include "schedulability.h"
+
+#include "edf/qpa.h"
+
+QPATest::QPATest(unsigned int num_processors)
+{
+        if (num_processors != 1)
+        {
+                // This is a uniprocessor test---complain even in non-debug
+                // builds.
+                abort();
+        }
+}
+
+static integral_t edf_busy_interval(const TaskSet &ts)
+{
+        integral_t interval = 0;
+        integral_t total_cost = 0;
+
+        // initial guess: sum of all costs.
+        for (unsigned int i = 0; i < ts.get_task_count(); i++)
+                interval += ts[i].get_wcet();
+
+        total_cost = interval;
+        do {
+                interval = total_cost;
+                total_cost = 0;
+                for (unsigned int i = 0; i < ts.get_task_count(); i++)
+                {
+                        integral_t jobs;
+                        jobs = divide_with_ceil(interval, ts[i].get_period());
+                        total_cost += jobs * ts[i].get_wcet();
+                }
+        } while (interval != total_cost);
+
+        return interval;
+}
+
+static integral_t zhang_burns_interval(const TaskSet &ts)
+{
+        integral_t interval = 0;
+        fractional_t total_scaled_delta = 0;
+        fractional_t total_util;
+
+        ts.get_utilization(total_util);
+
+        for (unsigned int i = 0; i < ts.get_task_count(); i++)
+        {
+                integral_t dl  = ts[i].get_deadline();
+                integral_t per = ts[i].get_period();
+                integral_t delta = dl - per;
+
+                interval = std::max(interval, delta);
+
+                fractional_t util;
+                ts[i].get_utilization(util);
+                total_scaled_delta += (per - dl) * util;
+        }
+
+        total_scaled_delta /= (1 - total_util);
+
+        interval = std::max(interval, round_up(total_scaled_delta));
+
+        return interval;
+}
+
+std::set<unsigned long> get_testpoints(const TaskSet &ts,
+                                              const integral_t &max_time)
+{
+        std::set<unsigned long> points;
+
+        // determine all test points
+        for (unsigned int i = 0; i < ts.get_task_count(); i++)
+        {
+                unsigned long time = ts[i].get_deadline();
+
+                for (unsigned long j = 0; time < max_time; j++)
+                {
+                        points.insert(time);
+                        time += ts[i].get_period();
+                }
+        }
+        return points;
+}
+
+static integral_t max_deadline(const Task &task,
+                               const integral_t &max_time)
+{
+        integral_t dl = max_time - task.get_deadline();
+
+        // implicit floor in integer division
+        dl /= task.get_period();
+        return dl * task.get_period() + task.get_deadline();
+}
+
+
+static unsigned long min_relative_deadline(const TaskSet &ts)
+{
+        unsigned long dl = ULONG_MAX;
+
+        for (unsigned int i = 0; i < ts.get_task_count(); i++)
+                dl = std::min(dl, ts[i].get_deadline());
+
+        return dl;
+}
+
+static integral_t get_largest_testpoint(const TaskSet &ts,
+                                        const integral_t &max_time)
+{
+        integral_t point = 0;
+
+        for (unsigned int i = 0; i < ts.get_task_count(); i++)
+        {
+                unsigned long dl = ts[i].get_deadline();
+                if (dl < max_time)
+                {
+                        integral_t max_dl = max_deadline(ts[i], max_time);
+                        if (max_dl == max_time)
+                                max_dl -= ts[i].get_period();
+                        if (max_dl > point)
+                                point = max_dl;
+                }
+        }
+
+        return point;
+}
+
+bool QPATest::is_schedulable(const TaskSet &ts, bool check_preconditions)
+{
+        integral_t max_interval = edf_busy_interval(ts);
+        unsigned long min_interval = min_relative_deadline(ts);
+
+        fractional_t util;
+        ts.get_utilization(util);
+
+        if (util < 1)
+                max_interval = std::min(max_interval, zhang_burns_interval(ts));
+        else if (util > 1)
+                return false;
+
+        integral_t next = get_largest_testpoint(ts, max_interval);
+        integral_t demand;
+        integral_t interval;
+
+        do {
+                interval = next;
+                ts.bound_demand(interval, demand);
+                if (demand < interval)
+                        next = demand;
+                else
+                        next = get_largest_testpoint(ts, interval);
+
+        } while (demand <= interval && demand > min_interval);
+
+        return demand <= min_interval;
+}