C++: Properly consider priority ceilings in DPCP bound

The bound should not reflect requests executed by agents that can be preempted.

5 files changed, 80 insertions, 25 deletions

diff --git a/native/include/blocking.h b/native/include/blocking.h
index b70f1a6..9f8c7d6 100644
--- a/native/include/blocking.h
+++ b/native/include/blocking.h
@@ -82,6 +82,11 @@ Interference bound_blocking_all_clusters(
         unsigned long interval,
         const TaskInfo* exclude_tsk);
 
+typedef std::vector<unsigned int> PriorityCeilings;
+
+void determine_priority_ceilings(const Resources& resources,
+                                 PriorityCeilings& ceilings);
+
 extern const unsigned int UNLIMITED;
 
 #endif
diff --git a/native/src/blocking/dpcp.cpp b/native/src/blocking/dpcp.cpp
index 6e194aa..a9b1288 100644
--- a/native/src/blocking/dpcp.cpp
+++ b/native/src/blocking/dpcp.cpp
@@ -65,6 +65,7 @@ static unsigned int count_requests_to_cpu(
 static Interference bound_blocking_dpcp(
         const TaskInfo* tsk,
         const ContentionSet& cont,
+        const PriorityCeilings& prio_ceiling,
         unsigned int max_lower_prio)
 {
         Interference inter;
@@ -86,7 +87,8 @@ static Interference bound_blocking_dpcp(
                                 inter.count += num;
                                 inter.total_length += num * req->get_request_length();
                         }
-                        else if (max_lower_prio)
+                        else if (max_lower_prio &&
+                                 prio_ceiling[req->get_resource_id()] <= tsk->get_priority())
                         {
                                 // lower prio => only remaining
                                 num = std::min(req->get_max_num_requests(interval), max_lower_prio);
@@ -103,6 +105,7 @@ static Interference bound_blocking_dpcp(
 static Interference dpcp_remote_bound(
         const TaskInfo& tsk,
         const ResourceLocality& locality,
+        const PriorityCeilings& prio_ceilings,
         const AllPerCluster& per_cpu)
 {
         Interference blocking;
@@ -118,7 +121,7 @@ static Interference dpcp_remote_bound(
                         reqs = count_requests_to_cpu(tsk, locality, cpu);
 
                         if (reqs > 0)
-                                blocking += bound_blocking_dpcp(&tsk, cs, reqs);
+                                blocking += bound_blocking_dpcp(&tsk, cs, prio_ceilings, reqs);
                 }
                 cpu++;
         }
@@ -150,6 +153,17 @@ static Interference dpcp_local_bound(
 }
 
 
+static PriorityCeilings get_priority_ceilings(const ResourceSharingInfo& info)
+{
+        Resources resources;
+        PriorityCeilings ceilings;
+
+        split_by_resource(info, resources);
+        determine_priority_ceilings(resources, ceilings);
+
+        return ceilings;
+}
+
 BlockingBounds* dpcp_bounds(const ResourceSharingInfo& info,
                             const ResourceLocality& locality)
 {
@@ -158,6 +172,8 @@ BlockingBounds* dpcp_bounds(const ResourceSharingInfo& info,
         split_by_locality(info, locality, per_cpu);
         sort_by_request_length(per_cpu);
 
+        PriorityCeilings prio_ceilings = get_priority_ceilings(info);
+
         BlockingBounds* _results = new BlockingBounds(info);
         BlockingBounds& results = *_results;
 
@@ -166,7 +182,7 @@ BlockingBounds* dpcp_bounds(const ResourceSharingInfo& info,
                 const TaskInfo& tsk  = info.get_tasks()[i];
                 Interference remote, local;
 
-                remote = dpcp_remote_bound(tsk, locality, per_cpu);
+                remote = dpcp_remote_bound(tsk, locality, prio_ceilings, per_cpu);
                 local = dpcp_local_bound(&tsk, per_cpu[tsk.get_cluster()]);
 
                 results[i] = remote + local;
diff --git a/native/src/blocking/mpcp.cpp b/native/src/blocking/mpcp.cpp
index 8b87556..655e09e 100644
--- a/native/src/blocking/mpcp.cpp
+++ b/native/src/blocking/mpcp.cpp
@@ -7,28 +7,6 @@
 // ***************************  MPCP ******************************************
 
 
-typedef std::vector<unsigned int> PriorityCeilings;
-
-static void determine_priority_ceilings(const Resources& resources,
-                                        PriorityCeilings& ceilings)
-{
-        ceilings.reserve(resources.size());
-
-        foreach(resources, it)
-        {
-                unsigned int ceiling = UINT_MAX;
-                const ContentionSet& cs = *it;
-
-                foreach(cs, jt)
-                {
-                        const RequestBound* req = *jt;
-                        ceiling = std::min(ceiling, req->get_task()->get_priority());
-                }
-
-                ceilings.push_back(ceiling);
-        }
-}
-
 typedef std::vector<unsigned long> ResponseTimes;
 typedef std::vector<ResponseTimes> TaskResponseTimes;
 typedef std::vector<TaskResponseTimes> ClusterResponseTimes;
diff --git a/native/src/sharedres.cpp b/native/src/sharedres.cpp
index a91bfdf..5c8acee 100644
--- a/native/src/sharedres.cpp
+++ b/native/src/sharedres.cpp
@@ -225,6 +225,26 @@ void sort_by_request_length(ClusterResources& resources)
         apply_foreach(resources, sort_by_request_length);
 }
 
+void determine_priority_ceilings(const Resources& resources,
+                                        PriorityCeilings& ceilings)
+{
+        ceilings.reserve(resources.size());
+
+        foreach(resources, it)
+        {
+                unsigned int ceiling = UINT_MAX;
+                const ContentionSet& cs = *it;
+
+                foreach(cs, jt)
+                {
+                        const RequestBound* req = *jt;
+                        ceiling = std::min(ceiling, req->get_task()->get_priority());
+                }
+
+                ceilings.push_back(ceiling);
+        }
+}
+
 typedef std::vector<TaskContention> ClusterContention;
 
 typedef std::vector<ContentionSet> TaskContention;
diff --git a/tests/locking.py b/tests/locking.py
index 73cd8f1..b16c453 100644
--- a/tests/locking.py
+++ b/tests/locking.py
@@ -440,6 +440,42 @@ class Test_dpcp_terms(unittest.TestCase):
         self.assertEqual(6 + 3, res.get_remote_count(2))
         self.assertEqual(6 * 3 + 3 * 5, res.get_remote_blocking(2))
 
+    def test_priority_ceiling(self):
+        self.rsi = cpp.ResourceSharingInfo(4)
+
+        self.rsi.add_task(10, 10, 2, 100)
+        self.rsi.add_request(0, 1, 3)
+
+        self.rsi.add_task(25, 25, 3, 200)
+        self.rsi.add_request(0, 1, 5)
+
+        self.rsi.add_task(50, 50, 4, 300)
+        self.rsi.add_request(1, 1, 7)
+
+        self.rsi.add_task(100, 100, 1, 400)
+        self.rsi.add_request(1, 1, 9)
+
+        self.loc = cpp.ResourceLocality()
+        self.loc.assign_resource(0, 1)
+        self.loc.assign_resource(1, 1)
+
+        res = cpp.dpcp_bounds(self.rsi, self.loc)
+
+        self.assertEqual(1, res.get_remote_count(0))
+        self.assertEqual(5, res.get_remote_blocking(0))
+
+        self.assertEqual(4, res.get_remote_count(1))
+        self.assertEqual(4 * 3, res.get_remote_blocking(1))
+
+        self.assertEqual(6 + 3 + 1, res.get_remote_count(2))
+        self.assertEqual(6 * 3 + 3 * 5 + 1 * 9, res.get_remote_blocking(2))
+
+        self.assertEqual(0, res.get_remote_count(3))
+        self.assertEqual(0, res.get_remote_blocking(3))
+
+        self.assertEqual(11 + 5 + 3, res.get_local_count(3))
+        self.assertEqual(11 * 3 + 5 * 5 + 3 * 7, res.get_local_blocking(3))
+
 
 class Test_mpcp_terms(unittest.TestCase):