UeterAgrawal.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.SchedulingInfo.Feasiblity;
import mvd.jester.model.DagTask;
import mvd.jester.model.LightTask;
import mvd.jester.model.SortedTaskSet;
import mvd.jester.model.SystemManagerInterface;
import mvd.jester.model.Task;
import mvd.jester.priority.EarliestDeadlineFirst;
import mvd.jester.priority.PriorityManager;

public class UeterAgrawal extends AbstractTest<DagTask> {

    private final EarliestDeadlineFirst priorityManager;
    private final Map<DagTask, Double> stretchRatios;

    public UeterAgrawal(SystemManagerInterface manager) {
        super(manager);
        this.priorityManager = new EarliestDeadlineFirst();
        this.stretchRatios = new HashMap<>();
    }

    @Override
    public SchedulingInfo runSchedulabilityCheck(SortedTaskSet<DagTask> tasks) {
        stretchRatios.clear();
        assignThreadsAndStretchRatio(tasks);

        List<Double> bins = new ArrayList<>();

        for (int i = 0; i < manager.getNumberOfProcessors(); ++i) {
            bins.add((double) 0);
        }

        for (DagTask t : tasks) {
            if (t.getNumberOfThreads() == 1) { // Light task
                if (!bestFitBinPackingOfTask(bins, t)) {
                    return new SchedulingInfo(Feasiblity.FAILED);
                }
            } else { // heavy task
                boolean failure = true;
                long numberOfServers = 0;
                List<Double> binsWithTask = copyBins(bins);
                final List<Task> listOfServerTasks = new ArrayList<>();
                listOfServerTasks.add(t);
                while (numberOfServers <= checkNumberOfServers(t)) {
                    if (!binPackingOfServers(binsWithTask, listOfServerTasks)) {
                        binsWithTask = copyBins(bins);
                        numberOfServers += 1;

                        listOfServerTasks.clear();
                        for (int l = 0; l < numberOfServers; ++l) {
                            long reservationBudget = (long) Math.ceil((double) t.getWorkload()
                                    / numberOfServers
                                    + (1 - (double) 1 / numberOfServers) * t.getCriticalPath());

                            listOfServerTasks.add(new LightTask(t.getPeriod(), t.getDeadline(),
                                    reservationBudget));
                        }
                    } else {
                        failure = false;
                        bins = binsWithTask;
                        break;
                    }
                }

                if (failure) {
                    return new SchedulingInfo(Feasiblity.FAILED);
                }
            }
        }

        return new SchedulingInfo(Feasiblity.SUCCEEDED);

    }

    private List<Double> copyBins(List<Double> bins) {
        List<Double> copiedBins = new ArrayList<>();

        for (Double b : bins) {
            copiedBins.add(b.doubleValue());
        }

        return copiedBins;
    }

    private long checkNumberOfServers(DagTask task) {
        final long criticalPath = task.getCriticalPath();
        final long workload = task.getWorkload();
        final double strechRatio = stretchRatios.get(task);

        final long first = LongMath.divide(workload, criticalPath, RoundingMode.CEILING);
        final long second = (long) Math
                .ceil(((double) workload - criticalPath) / (criticalPath * (strechRatio - 1)));

        // TODO: include fucking boundaries
        final long max = Math.max(first, second);

        return max;
    }


    private boolean binPackingOfServers(List<Double> bins, List<Task> tasks) {
        for (Task t : tasks) {
            if (!bestFitBinPackingOfTask(bins, t)) {
                return false;
            }
        }
        return true;
    }

    private boolean bestFitBinPackingOfTask(List<Double> bins, Task task) {
        int bestFit = 0; // No one at first
        for (int b = 0; b < bins.size(); ++b) {
            if (bins.get(b) + task.getDensity() <= 1) {
                double currentBin = bins.get(b);
                double bestBin = bins.get(bestFit);

                if (currentBin + task.getDensity() > bestBin + task.getDensity() || bestBin + task.getDensity() > 1) {
                    bestFit = b;
                }
            }
        }
        if (bins.get(bestFit) + task.getDensity() <= 1) {
            bins.set(bestFit, bins.get(bestFit) + task.getDensity());
            return true;
        }
        return false;
    }
    
    @SuppressWarnings("unused")
    private boolean firstFitBinPackingOfTask(List<Double> bins, Task task) {
        Collections.sort(bins);
        Collections.reverse(bins);
        for (int b = 0; b < bins.size(); ++b) {
            if (bins.get(b) + task.getDensity() <= 1) {
                bins.set(b, bins.get(b) + task.getDensity());
                return true;
            }
        }
        return false;
    }

    @SuppressWarnings("unused")
    private boolean worstFitBinPackingOfTask(List<Double> bins, Task task) {
        Collections.sort(bins);
        if (bins.get(0) + task.getDensity() <= 1) {
            bins.set(0, bins.get(0) + task.getDensity());
            return true;
        } else {
            return false;
        }
    }

    private void assignThreadsAndStretchRatio(Set<DagTask> tasks) {
        for (DagTask t : tasks) {
            final long criticalPath = t.getCriticalPath();
            final long workload = t.getWorkload();
            long numberOfThreads = LongMath.divide(workload - criticalPath,
                    t.getDeadline() - criticalPath, RoundingMode.CEILING);

            if (numberOfThreads == 0) {
                numberOfThreads = 1;
            }
            t.setNumberOfThreads(numberOfThreads);

            final double stretchRatio =
                    1 + ((double) workload - criticalPath) / (numberOfThreads * criticalPath);

            stretchRatios.put(t, stretchRatio);
        }

    }

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

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

}