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.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.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(final long numberOfProcessors) {
        super(numberOfProcessors);
        this.responseTimes = new HashMap<>();
        this.priorityManager = new EarliestDeadlineFirst();
    }

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

    @Override
    public SchedulingInfo runSchedulabilityCheck(final SortedTaskSet<SynchronousTask> tasks) {
        responseTimes.clear();
        for (final SynchronousTask t : tasks) {
            final long responseTime = calculateResponseTime(tasks, t);
            responseTimes.put(t, new TerminationInfo(t.getDeadline(), responseTime));
        }

        return new SchedulingInfo(responseTimes.values());
    }

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

        long taskInterference = 0;

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

        long selfInterference = 0;

        final long maxNumberOfJobs = task.getMaximumParallelism();

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

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

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

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

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

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

        long workloadOfBodyJobs = 0;

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

        final long boundedBodyWorkload = numberOfBodyJobs * workloadOfBodyJobs;
        long boundedCarryInWorkload = 0;
        final long remainingLength = deadline % t.getPeriod();
        long carryInLength = 0;
        final List<Segment> segmentList = new ArrayList<>(t.getWorkloadDistribution());
        Collections.reverse(segmentList);
        for (final 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(final SynchronousTask task) {
        long minWcet = 0;
        for (final Segment s : task.getWorkloadDistribution()) {
            minWcet += s.getJobWcet();
        }

        return minWcet;
    }

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


}