From 546b17c0f6360f4e83e6f0dda8db99656aa94077 Mon Sep 17 00:00:00 2001 From: Bjoern Brandenburg Date: Wed, 16 May 2012 18:01:56 +0200 Subject: Move MPPC++: Break out the MPCP code into own file Part of refactoring sharedres.cpp. --- native/Makefile | 2 +- native/include/blocking.h | 16 ++- native/src/blocking/mpcp.cpp | 320 ++++++++++++++++++++++++++++++++++++++++++ native/src/sharedres.cpp | 322 +------------------------------------------ 4 files changed, 335 insertions(+), 325 deletions(-) create mode 100644 native/src/blocking/mpcp.cpp diff --git a/native/Makefile b/native/Makefile index 2204788..ec6da1c 100644 --- a/native/Makefile +++ b/native/Makefile @@ -54,7 +54,7 @@ vpath %.cpp src src/edf src/blocking EDF_OBJ = baker.o baruah.o gfb.o bcl.o bcl_iterative.o rta.o ffdbf.o gedf.o load.o cpu_time.o SCHED_OBJ = sim.o schedule_sim.o CORE_OBJ = tasks.o -SYNC_OBJ = sharedres.o dpcp.o +SYNC_OBJ = sharedres.o dpcp.o mpcp.o # #### Targets #### diff --git a/native/include/blocking.h b/native/include/blocking.h index 80b4973..9930aa2 100644 --- a/native/include/blocking.h +++ b/native/include/blocking.h @@ -2,15 +2,10 @@ #define BLOCKING_H typedef std::vector ContentionSet; - typedef std::vector Resources; - typedef std::vector ClusterResources; - typedef std::vector AllPerCluster; - typedef std::vector TaskContention; - typedef std::vector ClusterContention; struct LimitedRequestBound { @@ -29,4 +24,15 @@ void sort_by_request_length(Resources& resources); void sort_by_request_length(ClusterResources& resources); void sort_by_request_length(ContentionSet& cs); + +typedef std::vector Cluster; +typedef std::vector Clusters; + +void split_by_cluster(const ResourceSharingInfo& info, Clusters& clusters); +void split_by_resource(const ResourceSharingInfo& info, Resources& resources); + + + +extern const unsigned int UNLIMITED; + #endif diff --git a/native/src/blocking/mpcp.cpp b/native/src/blocking/mpcp.cpp new file mode 100644 index 0000000..8b87556 --- /dev/null +++ b/native/src/blocking/mpcp.cpp @@ -0,0 +1,320 @@ +#include "sharedres.h" +#include "blocking.h" + +#include "stl-helper.h" +#include "math-helper.h" + +// *************************** MPCP ****************************************** + + +typedef std::vector 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 ResponseTimes; +typedef std::vector TaskResponseTimes; +typedef std::vector ClusterResponseTimes; + +static unsigned long get_max_gcs_length(const TaskInfo* tsk, + const PriorityCeilings& ceilings, + unsigned int preempted_ceiling) +{ + unsigned long gcs_length = 0; + + foreach(tsk->get_requests(), it) + { + unsigned int prio = ceilings[it->get_resource_id()]; + if (prio < preempted_ceiling) + gcs_length = std::max(gcs_length, + (unsigned long) it->get_request_length()); + } + + return gcs_length; +} + +static void determine_gcs_response_times(const TaskInfo* tsk, + const Cluster& cluster, + const PriorityCeilings& ceilings, + ResponseTimes& times) +{ + times.reserve(tsk->get_requests().size()); + + foreach(tsk->get_requests(), it) + { + unsigned long resp = it->get_request_length(); + unsigned int prio = ceilings[it->get_resource_id()]; + + // Equation (2) in LNR:09. + // One request of each local gcs that can preempt our ceiling, + // but at most one per task (since tasks are sequential). + + foreach(cluster, jt) + { + const TaskInfo* t = *jt; + + if (t != tsk) + resp += get_max_gcs_length(t, ceilings, prio); + } + + times.push_back(resp); + } +} + +static void determine_gcs_response_times(const Cluster& cluster, + const PriorityCeilings& ceilings, + TaskResponseTimes& times) +{ + times.reserve(cluster.size()); + foreach(cluster, it) + { + times.push_back(ResponseTimes()); + determine_gcs_response_times(*it, cluster, ceilings, + times.back()); + } +} + +static void determine_gcs_response_times(const Clusters& clusters, + const PriorityCeilings& ceilings, + ClusterResponseTimes& times) +{ + times.reserve(clusters.size()); + foreach(clusters, it) + { + times.push_back(TaskResponseTimes()); + determine_gcs_response_times(*it, ceilings, times.back()); + } +} + +static unsigned long response_time_for(unsigned int res_id, + unsigned long interval, + const TaskInfo* tsk, + const ResponseTimes& resp, + bool multiple) +{ + const Requests& requests = tsk->get_requests(); + unsigned int i = 0; + + for (i = 0; i < requests.size(); i++) + if (requests[i].get_resource_id() == res_id) + { + if (multiple) + { + // Equation (3) in LNR:09. + // How many jobs? + unsigned long num_jobs; + num_jobs = divide_with_ceil(interval, tsk->get_period()); + num_jobs += 1; + + // Note: this may represent multiple gcs, so multiply. + return num_jobs * resp[i] * requests[i].get_num_requests(); + } + else + // Just one request. + return resp[i]; + } + // if we get here, then the task does not access res_id + return 0; +} + +static unsigned long mpcp_remote_blocking(unsigned int res_id, + unsigned long interval, + const TaskInfo* tsk, + const Cluster& cluster, + const TaskResponseTimes times, + unsigned long& max_lower) +{ + unsigned int i; + unsigned long blocking = 0; + + // consider each task in cluster + for (i = 0; i < cluster.size(); i++) + { + const TaskInfo* t = cluster[i]; + if (t != tsk) + { + if (t->get_priority() < tsk->get_priority()) + // This is a higher-priority task; + // it can block multiple times. + blocking += response_time_for(res_id, interval, + t, times[i], true); + else + // This is a lower-priority task; + // it can block only once. + max_lower = std::max(max_lower, + response_time_for(res_id, interval, + t, times[i], false)); + } + } + + return blocking; +} + +static unsigned long mpcp_remote_blocking(unsigned int res_id, + unsigned long interval, + const TaskInfo* tsk, + const Clusters& clusters, + const ClusterResponseTimes times, + unsigned long& max_lower) +{ + unsigned int i; + unsigned long blocking; + + max_lower = 0; + blocking = 0; + + for (i = 0; i < clusters.size(); i++) + { + blocking += mpcp_remote_blocking(res_id, interval, + tsk, clusters[i], times[i], + max_lower); + } + return blocking; +} + +static unsigned long mpcp_remote_blocking(unsigned int res_id, + const TaskInfo* tsk, + const Clusters& clusters, + const ClusterResponseTimes times) +{ + unsigned long interval; + unsigned long blocking = 1; + unsigned long max_lower; + + do + { + // last bound + interval = blocking; + // Bail out if it doesn't converge. + if (interval > tsk->get_response()) + return UNLIMITED; + + blocking = mpcp_remote_blocking(res_id, interval, + tsk, clusters, times, + max_lower); + + // Account for the maximum lower-priority gcs + // that could get in the way. + blocking += max_lower; + + // Loop until it converges. + } while ( interval != blocking ); + + return blocking; +} + +static unsigned long mpcp_remote_blocking(const TaskInfo* tsk, + const Clusters& clusters, + const ClusterResponseTimes times) +{ + unsigned long blocking = 0; + + + const Requests& requests = tsk->get_requests(); + unsigned int i = 0; + + for (i = 0; i < requests.size(); i++) + { + unsigned int b; + b = mpcp_remote_blocking(requests[i].get_resource_id(), + tsk, clusters, times); + if (b != UNLIMITED) + // may represent multiple, multiply accordingly + blocking += b * requests[i].get_num_requests(); + else + // bail out if it didn't converge + return b; + } + + return blocking; +} + +static unsigned long mpcp_arrival_blocking(const TaskInfo* tsk, + const Cluster& cluster, + bool virtual_spinning) +{ + unsigned int prio = tsk->get_priority(); + unsigned int blocking = 0; + unsigned int i; + + for (i = 0; i < cluster.size(); i++) + if (cluster[i] != tsk && cluster[i]->get_priority() >= prio) + blocking += cluster[i]->get_max_request_length(); + + if (virtual_spinning) + // Equation (4) in LNR:09. + return blocking; + else + // Equation (1) in LNR:09. + return blocking * tsk->get_num_arrivals(); +} + +BlockingBounds* mpcp_bounds(const ResourceSharingInfo& info, + bool use_virtual_spinning) +{ + Resources resources; + Clusters clusters; + + split_by_resource(info, resources); + split_by_cluster(info, clusters); + + // 2) Determine priority ceiling for each request. + PriorityCeilings gc; + determine_priority_ceilings(resources, gc); + + + // 3) For each request, determine response time. This only depends on the + // priority ceiling for each request. + ClusterResponseTimes responses; + determine_gcs_response_times(clusters, gc, responses); + + unsigned int i; + + BlockingBounds* _results = new BlockingBounds(info); + BlockingBounds& results = *_results; + + for (i = 0; i < info.get_tasks().size(); i++) + { + const TaskInfo& tsk = info.get_tasks()[i]; + + unsigned long remote, local = 0; + + // 4) Determine remote blocking for each request. This depends on the + // response times for each remote request. + remote = mpcp_remote_blocking(&tsk, clusters, responses); + + // 5) Determine arrival blocking for each task. + if (remote != UNLIMITED) + local = mpcp_arrival_blocking(&tsk, clusters[tsk.get_cluster()], + use_virtual_spinning); + + // 6) Sum up blocking: remote blocking + arrival blocking. + results[i].total_length = remote + local; + + + Interference inf; + inf.total_length = remote; + results.set_remote_blocking(i, inf); + } + + return _results; +} + + diff --git a/native/src/sharedres.cpp b/native/src/sharedres.cpp index 935d20f..a3b4ed9 100644 --- a/native/src/sharedres.cpp +++ b/native/src/sharedres.cpp @@ -22,7 +22,7 @@ #include "blocking.h" -static const unsigned int UNLIMITED = UINT_MAX; +const unsigned int UNLIMITED = UINT_MAX; std::ostream& operator<<(std::ostream &os, const TaskInfo &ti) { @@ -78,10 +78,8 @@ unsigned int RequestBound::get_max_num_requests(unsigned long interval) const // ****** non-exported helpers ******* -typedef std::vector Cluster; -typedef std::vector Clusters; -static void split_by_cluster(const ResourceSharingInfo& info, Clusters& clusters) +void split_by_cluster(const ResourceSharingInfo& info, Clusters& clusters) { foreach(info.get_tasks(), it) { @@ -111,7 +109,7 @@ void sort_by_priority(Clusters& clusters) } -static void split_by_resource(const ResourceSharingInfo& info, Resources& resources) +void split_by_resource(const ResourceSharingInfo& info, Resources& resources) { foreach(info.get_tasks(), it) { @@ -1720,317 +1718,3 @@ BlockingBounds* part_fmlp_bounds(const ResourceSharingInfo& info, bool preemptiv return _results; } -// *************************** MPCP ****************************************** - - -typedef std::vector 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 ResponseTimes; -typedef std::vector TaskResponseTimes; -typedef std::vector ClusterResponseTimes; - -static unsigned long get_max_gcs_length(const TaskInfo* tsk, - const PriorityCeilings& ceilings, - unsigned int preempted_ceiling) -{ - unsigned long gcs_length = 0; - - foreach(tsk->get_requests(), it) - { - unsigned int prio = ceilings[it->get_resource_id()]; - if (prio < preempted_ceiling) - gcs_length = std::max(gcs_length, - (unsigned long) it->get_request_length()); - } - - return gcs_length; -} - -static void determine_gcs_response_times(const TaskInfo* tsk, - const Cluster& cluster, - const PriorityCeilings& ceilings, - ResponseTimes& times) -{ - times.reserve(tsk->get_requests().size()); - - foreach(tsk->get_requests(), it) - { - unsigned long resp = it->get_request_length(); - unsigned int prio = ceilings[it->get_resource_id()]; - - // Equation (2) in LNR:09. - // One request of each local gcs that can preempt our ceiling, - // but at most one per task (since tasks are sequential). - - foreach(cluster, jt) - { - const TaskInfo* t = *jt; - - if (t != tsk) - resp += get_max_gcs_length(t, ceilings, prio); - } - - times.push_back(resp); - } -} - -static void determine_gcs_response_times(const Cluster& cluster, - const PriorityCeilings& ceilings, - TaskResponseTimes& times) -{ - times.reserve(cluster.size()); - foreach(cluster, it) - { - times.push_back(ResponseTimes()); - determine_gcs_response_times(*it, cluster, ceilings, - times.back()); - } -} - -static void determine_gcs_response_times(const Clusters& clusters, - const PriorityCeilings& ceilings, - ClusterResponseTimes& times) -{ - times.reserve(clusters.size()); - foreach(clusters, it) - { - times.push_back(TaskResponseTimes()); - determine_gcs_response_times(*it, ceilings, times.back()); - } -} - -static unsigned long response_time_for(unsigned int res_id, - unsigned long interval, - const TaskInfo* tsk, - const ResponseTimes& resp, - bool multiple) -{ - const Requests& requests = tsk->get_requests(); - unsigned int i = 0; - - for (i = 0; i < requests.size(); i++) - if (requests[i].get_resource_id() == res_id) - { - if (multiple) - { - // Equation (3) in LNR:09. - // How many jobs? - unsigned long num_jobs; - num_jobs = divide_with_ceil(interval, tsk->get_period()); - num_jobs += 1; - - // Note: this may represent multiple gcs, so multiply. - return num_jobs * resp[i] * requests[i].get_num_requests(); - } - else - // Just one request. - return resp[i]; - } - // if we get here, then the task does not access res_id - return 0; -} - -static unsigned long mpcp_remote_blocking(unsigned int res_id, - unsigned long interval, - const TaskInfo* tsk, - const Cluster& cluster, - const TaskResponseTimes times, - unsigned long& max_lower) -{ - unsigned int i; - unsigned long blocking = 0; - - // consider each task in cluster - for (i = 0; i < cluster.size(); i++) - { - const TaskInfo* t = cluster[i]; - if (t != tsk) - { - if (t->get_priority() < tsk->get_priority()) - // This is a higher-priority task; - // it can block multiple times. - blocking += response_time_for(res_id, interval, - t, times[i], true); - else - // This is a lower-priority task; - // it can block only once. - max_lower = std::max(max_lower, - response_time_for(res_id, interval, - t, times[i], false)); - } - } - - return blocking; -} - -static unsigned long mpcp_remote_blocking(unsigned int res_id, - unsigned long interval, - const TaskInfo* tsk, - const Clusters& clusters, - const ClusterResponseTimes times, - unsigned long& max_lower) -{ - unsigned int i; - unsigned long blocking; - - max_lower = 0; - blocking = 0; - - for (i = 0; i < clusters.size(); i++) - { - blocking += mpcp_remote_blocking(res_id, interval, - tsk, clusters[i], times[i], - max_lower); - } - return blocking; -} - -static unsigned long mpcp_remote_blocking(unsigned int res_id, - const TaskInfo* tsk, - const Clusters& clusters, - const ClusterResponseTimes times) -{ - unsigned long interval; - unsigned long blocking = 1; - unsigned long max_lower; - - do - { - // last bound - interval = blocking; - // Bail out if it doesn't converge. - if (interval > tsk->get_response()) - return UNLIMITED; - - blocking = mpcp_remote_blocking(res_id, interval, - tsk, clusters, times, - max_lower); - - // Account for the maximum lower-priority gcs - // that could get in the way. - blocking += max_lower; - - // Loop until it converges. - } while ( interval != blocking ); - - return blocking; -} - -static unsigned long mpcp_remote_blocking(const TaskInfo* tsk, - const Clusters& clusters, - const ClusterResponseTimes times) -{ - unsigned long blocking = 0; - - - const Requests& requests = tsk->get_requests(); - unsigned int i = 0; - - for (i = 0; i < requests.size(); i++) - { - unsigned int b; - b = mpcp_remote_blocking(requests[i].get_resource_id(), - tsk, clusters, times); - if (b != UNLIMITED) - // may represent multiple, multiply accordingly - blocking += b * requests[i].get_num_requests(); - else - // bail out if it didn't converge - return b; - } - - return blocking; -} - -static unsigned long mpcp_arrival_blocking(const TaskInfo* tsk, - const Cluster& cluster, - bool virtual_spinning) -{ - unsigned int prio = tsk->get_priority(); - unsigned int blocking = 0; - unsigned int i; - - for (i = 0; i < cluster.size(); i++) - if (cluster[i] != tsk && cluster[i]->get_priority() >= prio) - blocking += cluster[i]->get_max_request_length(); - - if (virtual_spinning) - // Equation (4) in LNR:09. - return blocking; - else - // Equation (1) in LNR:09. - return blocking * tsk->get_num_arrivals(); -} - -BlockingBounds* mpcp_bounds(const ResourceSharingInfo& info, - bool use_virtual_spinning) -{ - Resources resources; - Clusters clusters; - - split_by_resource(info, resources); - split_by_cluster(info, clusters); - - // 2) Determine priority ceiling for each request. - PriorityCeilings gc; - determine_priority_ceilings(resources, gc); - - - // 3) For each request, determine response time. This only depends on the - // priority ceiling for each request. - ClusterResponseTimes responses; - determine_gcs_response_times(clusters, gc, responses); - - unsigned int i; - - BlockingBounds* _results = new BlockingBounds(info); - BlockingBounds& results = *_results; - - for (i = 0; i < info.get_tasks().size(); i++) - { - const TaskInfo& tsk = info.get_tasks()[i]; - - unsigned long remote, local = 0; - - // 4) Determine remote blocking for each request. This depends on the - // response times for each remote request. - remote = mpcp_remote_blocking(&tsk, clusters, responses); - - // 5) Determine arrival blocking for each task. - if (remote != UNLIMITED) - local = mpcp_arrival_blocking(&tsk, clusters[tsk.get_cluster()], - use_virtual_spinning); - - // 6) Sum up blocking: remote blocking + arrival blocking. - results[i].total_length = remote + local; - - - Interference inf; - inf.total_length = remote; - results.set_remote_blocking(i, inf); - } - - return _results; -} - - -- cgit v1.2.2