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/src/blocking/mpcp.cpp | 320 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 320 insertions(+) create mode 100644 native/src/blocking/mpcp.cpp (limited to 'native/src/blocking/mpcp.cpp') 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; +} + + -- cgit v1.2.2