ChwaLee.java

package mvd.jester.tests;

import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
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.Segment;
import mvd.jester.model.SortedTaskSet;
import mvd.jester.model.SynchronousTask;
import mvd.jester.priority.EarliestDeadlineFirst;
import mvd.jester.priority.PriorityManager;

/**
 * ChwaLee
 */
public class ChwaLee extends AbstractTest<SynchronousTask> {

    private final Map<SynchronousTask, TerminationInfo> responseTimes;
    private final PriorityManager priorityManager;

    public ChwaLee(long numberOfProcessors) {
        super(numberOfProcessors);
        this.responseTimes = new HashMap<>();
        this.priorityManager = new EarliestDeadlineFirst();
    }

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

    @Override
    public SchedulingInfo runSchedulabilityCheck(SortedTaskSet<SynchronousTask> tasks) {
        responseTimes.clear();
        for (SynchronousTask t : tasks) {
            Level taskLevel = tasks.headSet(t).size() <= tasks.size() / 2 ? Level.HIGH : Level.LOW;
            long responseTime = calculateResponseTime(tasks, t);
            responseTimes.put(t, new TerminationInfo(t.getDeadline(), responseTime, taskLevel));
        }

        return new SchedulingInfo(new HashSet<>(responseTimes.values()),
                tasks.getParallelTaskRatio(), tasks.getUtilization());
    }

    private long calculateResponseTime(Set<SynchronousTask> tasks, SynchronousTask task) {
        long minimumWcet = getMinimumWcet(task);
        long deadline = task.getDeadline();

        long taskInterference = 0;

        for (SynchronousTask t : tasks) {
            if (!t.equals(task)) {
                long maxNumberOfJobs = t.getMaximumParallelism();
                for (long p = 0; p < maxNumberOfJobs; ++p) {
                    taskInterference += Math.min(getTaskInterference(t, deadline, p + 1),
                            deadline - minimumWcet);
                }
            }
        }

        long selfInterference = 0;

        long maxNumberOfJobs = task.getMaximumParallelism();

        for (long p = 0; p < maxNumberOfJobs; ++p) {
            selfInterference +=
                    Math.min(getSelfInterference(task, deadline, p + 1), deadline - minimumWcet);
        }

        boolean feasible = taskInterference + selfInterference <= numberOfProcessors
                * (deadline - minimumWcet);

        return feasible ? deadline - 1 : deadline + 1;
    }

    private long getSelfInterference(SynchronousTask task, long deadline, long p) {
        long selfInterference = 0;

        for (Segment s : task.getWorkloadDistribution()) {
            if (s.getNumberOfJobs() >= p + 1) {
                selfInterference += s.getJobWcet();
            }
        }
        return selfInterference;
    }

    private long getTaskInterference(SynchronousTask t, long deadline, long p) {
        long numberOfBodyJobs = LongMath.divide(deadline, t.getPeriod(), RoundingMode.FLOOR);

        long workloadOfBodyJobs = 0;

        for (Segment s : t.getWorkloadDistribution()) {
            if (s.getNumberOfJobs() >= p) {
                workloadOfBodyJobs += s.getJobWcet();
            }
        }

        long boundedBodyWorkload = numberOfBodyJobs * workloadOfBodyJobs;
        long boundedCarryInWorkload = 0;
        long remainingLength = deadline % t.getPeriod();
        long carryInLength = 0;
        List<Segment> segmentList = new ArrayList<>(t.getWorkloadDistribution());
        Collections.reverse(segmentList);
        for (Segment s : segmentList) {
            carryInLength += s.getJobWcet();
            if (s.getNumberOfJobs() >= p && remainingLength > carryInLength) {
                boundedCarryInWorkload += s.getJobWcet();
            } else if (s.getNumberOfJobs() >= p && remainingLength <= carryInLength) {
                boundedCarryInWorkload += s.getJobWcet() - (carryInLength - remainingLength);
            }
            if (carryInLength >= remainingLength) {
                break;
            }
        }

        return boundedBodyWorkload + boundedCarryInWorkload;
    }

    private long getMinimumWcet(SynchronousTask task) {
        long minWcet = 0;
        for (Segment s : task.getWorkloadDistribution()) {
            minWcet += s.getJobWcet();
        }

        return minWcet;
    }

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


}