package mvd.jester.tests; import java.math.RoundingMode; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; import com.google.common.math.LongMath; import mvd.jester.info.SchedulingInfo; import mvd.jester.info.TerminationInfo; import mvd.jester.info.TerminationInfo.Level; import mvd.jester.model.DagTask; import mvd.jester.model.Segment; import mvd.jester.model.SortedTaskSet; import mvd.jester.model.Task; import mvd.jester.priority.PriorityManager; import mvd.jester.priority.RateMonotonic; /** * SchmidMottok */ public class SchmidMottok extends AbstractTest { private final Map responseTimes; private final PriorityManager priorityManager; public SchmidMottok(long numberOfProcessors) { super(numberOfProcessors); this.responseTimes = new HashMap<>(); this.priorityManager = new RateMonotonic(); } @Override public PriorityManager getPriorityManager() { return priorityManager; } @Override public SchedulingInfo runSchedulabilityCheck(SortedTaskSet tasks) { responseTimes.clear(); for (DagTask t : tasks) { long responseTime = calculateResponseTime(tasks, t); responseTimes.put(t, new TerminationInfo(t.getDeadline(), responseTime, Level.HIGH)); } return new SchedulingInfo(new HashSet<>(responseTimes.values()), tasks.getParallelTaskRatio(), tasks.getUtilization()); } @Override public String getName() { return "SchmidMottok"; } private long calculateResponseTime(Set tasks, DagTask task) { long minimumWcet = task.getCriticalPath(); long responseTime = minimumWcet; long previousResponseTime = 0; do { previousResponseTime = responseTime; double taskInterference = 0; for (DagTask t : tasks) { if (t.getPeriod() < task.getPeriod()) { long numberOfThreads = t.getNumberOfThreads(); for (int p = 0; p < numberOfThreads; ++p) { taskInterference += Math.min(getTaskInterference(t, responseTime, p + 1), responseTime - minimumWcet + 1); } } } taskInterference /= numberOfProcessors; double selfInterference = getSelfInterference(task); long totalInterference = (long) Math.floor(taskInterference + selfInterference); responseTime = minimumWcet + totalInterference; } while (previousResponseTime != responseTime); return responseTime; } private double getSelfInterference(DagTask task) { double interference = 0; long numberOfThreads = task.getNumberOfThreads(); for (Segment s : task.getWorkloadDistribution()) { interference += (double) (s.getNumberOfJobs() - 1) * s.getJobWcet(); } interference /= numberOfThreads; return interference; } private double getTaskInterference(DagTask task, long interval, long parallelism) { if (responseTimes.containsKey(task)) { long responseTime = responseTimes.get(task).getResponseTime(); long minWcet = task.getCriticalPath(); long period = task.getPeriod(); long amountOfJobs = (LongMath.divide(interval + responseTime - minWcet, period, RoundingMode.FLOOR) + 1); double workload = 0; for (Segment s : task.getWorkloadDistribution()) { long numberOfThreads = s.getNumberOfJobs() > 1 ? task.getNumberOfThreads() : 1; if (numberOfThreads >= parallelism) { workload += s.getNumberOfJobs() * s.getJobWcet() / numberOfThreads; } } double interference = amountOfJobs * workload; return interference; } else { throw new RuntimeException("Task was not found in task set!"); } } }