FonsecaNelis.java

package mvd.jester.tests;

import java.math.RoundingMode;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import com.google.common.collect.Lists;
import com.google.common.math.LongMath;
import org.jgrapht.experimental.dag.DirectedAcyclicGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.traverse.BreadthFirstIterator;
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.Job;
import mvd.jester.model.Segment;
import mvd.jester.model.SortedTaskSet;
import mvd.jester.model.Task;
import mvd.jester.model.DagTask.DagUtils;
import mvd.jester.priority.PriorityManager;
import mvd.jester.priority.RateMonotonic;
import mvd.jester.utils.BinaryDecompositionTree;

public class FonsecaNelis extends AbstractTest<DagTask> {

    private final Map<Task, TerminationInfo> responseTimes;
    private final PriorityManager priorityManager;
    private final Map<Task, Set<Segment>> sortedSegments;

    public FonsecaNelis(long numberOfProcessors) {
        super(numberOfProcessors);
        this.responseTimes = new HashMap<>();
        this.priorityManager = new RateMonotonic();
        this.sortedSegments = new HashMap<>();
    }

    @Override
    public PriorityManager getPriorityManager() {
        return priorityManager;
    }

    @Override
    public SchedulingInfo runSchedulabilityCheck(SortedTaskSet<DagTask> tasks) {
        sortedSegments.clear();
        responseTimes.clear();
        createNFJandDecompositionTree(tasks);
        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());
    }

    private void createNFJandDecompositionTree(SortedTaskSet<DagTask> tasks) {
        for (DagTask t : tasks) {
            DirectedAcyclicGraph<Job, DefaultEdge> jobDag = t.getJobDag();
            LinkedList<Job> joinNodes = new LinkedList<>();
            LinkedList<Job> forkNodes = new LinkedList<>();

            BreadthFirstIterator<Job, DefaultEdge> breadthFirstIterator =
                    new BreadthFirstIterator<>(jobDag);
            while (breadthFirstIterator.hasNext()) {
                Job j = breadthFirstIterator.next();
                if (jobDag.inDegreeOf(j) > 1) {
                    joinNodes.add(j);
                }
                if (jobDag.outDegreeOf(j) > 1) {
                    forkNodes.add(j);
                }
            }
            DirectedAcyclicGraph<Job, DefaultEdge> modifiedJobDag =
                    DagUtils.createNFJGraph(jobDag, forkNodes, joinNodes);
            BinaryDecompositionTree<Job> tree =
                    DagUtils.createDecompositionTree(modifiedJobDag, forkNodes, joinNodes);
        }
    }

    private long calculateResponseTime(SortedTaskSet<DagTask> tasks, DagTask task) {
        long criticalPath = task.getCriticalPath();
        long responseTime = criticalPath;
        long previousResponseTime = 0;

        do {
            previousResponseTime = responseTime;
            double taskInterference = 0;
            for (DagTask t : tasks) {
                if (t.getPeriod() < task.getPeriod()) {
                    taskInterference += getTaskInterference(t, responseTime);
                }
            }

            taskInterference /= numberOfProcessors;

            double selfInterference = getSelfInterference(task);

            long totalInterference = (long) Math.floor(taskInterference + selfInterference);
            responseTime = criticalPath + totalInterference;

        } while (responseTime != previousResponseTime);

        return responseTime;
    }

    private double getTaskInterference(DagTask task, long interval) {
        long period = task.getPeriod();
        long criticalPath = task.getCriticalPath();
        long numberOfIntervals =
                LongMath.divide(interval - criticalPath, period, RoundingMode.FLOOR);
        long carryInAndOutInterval = interval - Math.max(0, numberOfIntervals) * period;
        long numberOfBodyJobs =
                LongMath.divide(interval - carryInAndOutInterval, period, RoundingMode.FLOOR);

        long bodyWorkload = Math.max(0, numberOfBodyJobs) * task.getWorkload();


        long carryInAndOutWorkload = getCarryInAndOutWorkload(task, task.getWorkloadDistribution(),
                sortedSegments.get(task), carryInAndOutInterval);

        return carryInAndOutWorkload + bodyWorkload;
    }

    private long getCarryInAndOutWorkload(DagTask task, Set<Segment> carryInDistribution,
            Set<Segment> carryOutDistribution, long carryInAndOutPeriod) {
        long workload = getCarryOutWorkload(task, carryOutDistribution, carryInAndOutPeriod);
        long carryInPeriod = task.getPeriod() - responseTimes.get(task).getResponseTime();
        long carryOutPeriod = 0;
        List<Segment> carryInList = Lists.newArrayList(carryInDistribution);
        Collections.reverse(carryInList);

        for (Segment s : carryInList) {
            carryInPeriod += s.getJobWcet();
            carryOutPeriod = carryInAndOutPeriod - carryInPeriod;
            long carryInWorkload = getCarryInWorkload(task, carryInDistribution, carryInPeriod);
            long carryOutWorkload = getCarryOutWorkload(task, carryOutDistribution, carryOutPeriod);
            workload = Math.max(workload, carryInWorkload + carryOutWorkload);
        }

        workload = Math.max(workload,
                getCarryInWorkload(task, carryInDistribution, carryInAndOutPeriod));
        carryOutPeriod = 0;

        for (Segment s : carryOutDistribution) {
            carryOutPeriod += s.getJobWcet();
            carryInPeriod = carryInAndOutPeriod - carryOutPeriod;
            long carryInWorkload = getCarryInWorkload(task, carryInDistribution, carryInPeriod);
            long carryOutWorkload = getCarryOutWorkload(task, carryOutDistribution, carryOutPeriod);
            workload = Math.max(workload, carryInWorkload + carryOutWorkload);
        }

        return workload;
    }

    private long getCarryOutWorkload(DagTask task, Set<Segment> carryOutDistribution,
            long carryOutPeriod) {
        long workload = 0;
        long period = task.getPeriod();
        long responseTime = responseTimes.get(task).getResponseTime();
        List<Segment> distributionList = Lists.newArrayList(carryOutDistribution);

        for (int i = 0; i < distributionList.size(); ++i) {
            Segment s = distributionList.get(i);
            long weightOfPreviousSegments = 0;
            for (int j = 0; j < i; ++j) {
                weightOfPreviousSegments += distributionList.get(j).getJobWcet();
            }
            long width = carryOutPeriod - weightOfPreviousSegments;

            workload += Math.max(Math.min(width, s.getJobWcet()), 0) * s.getNumberOfJobs();
        }

        long improvedWorkload =
                Math.max(carryOutPeriod - (period - responseTime), 0) * numberOfProcessors;

        return Math.min(improvedWorkload, workload);
    }

    private long getCarryInWorkload(DagTask task, Set<Segment> carryInDistribution,
            long carryInPeriod) {
        long workload = 0;
        long period = task.getPeriod();
        long responseTime = responseTimes.get(task).getResponseTime();
        List<Segment> distributionList = Lists.newArrayList(carryInDistribution);

        for (int i = 0; i < carryInDistribution.size(); ++i) {
            Segment s = distributionList.get(i);
            long weightOfRemainingSegments = 0;
            for (int j = i + 1; j < carryInDistribution.size(); ++j) {
                weightOfRemainingSegments += distributionList.get(j).getJobWcet();
            }
            long width = carryInPeriod - period + responseTime - weightOfRemainingSegments;

            workload += Math.max(Math.min(width, s.getJobWcet()), 0) * s.getNumberOfJobs();
        }

        long improvedWorkload =
                Math.max(carryInPeriod - (period - responseTime), 0) * numberOfProcessors;

        return Math.min(improvedWorkload, workload);
    }

    private double getSelfInterference(DagTask task) {
        long criticalPath = task.getCriticalPath();
        long workload = task.getWorkload();

        return (double) (workload - criticalPath) / numberOfProcessors;
    }

    @Override
    public String getName() {
        return "FonsecaNelis";
    }


}