Earliest Deadline First Scheduling

# Earliest Deadline First: at every instant, run the ready job whose
# ABSOLUTE deadline is nearest. Priority is recomputed as time passes --
# that is what separates EDF from rate-monotonic's fixed priorities.
import heapq

def edf(tasks, horizon):
    ready, timeline, nxt = [], [], {n: 0 for n, _, _ in tasks}
    for t in range(horizon):
        for name, c, p in tasks:                # release anything due at t
            if nxt[name] == t:
                # key on ABSOLUTE deadline, so the heap pops the urgent job
                heapq.heappush(ready, (t + p, name, c))
                nxt[name] = t + p
        if not ready:
            timeline.append("idle")
            continue
        dl, name, left = heapq.heappop(ready)   # nearest deadline wins
        timeline.append(name)
        if left - 1:                            # preemptible: requeue
            heapq.heappush(ready, (dl, name, left - 1))
        elif t + 1 > dl:
            raise RuntimeError(name + " missed deadline")
    return timeline

def utilisation(tasks):
    return sum(c / p for _, c, p in tasks)

TASKS = [("T1", 1, 3), ("T2", 2, 5), ("T3", 1, 6)]
run = edf(TASKS, 15)
print("schedule:", " ".join(run))
print("U = %.2f -> schedulable by EDF (bound is 1.0)" % utilisation(TASKS))

// Earliest Deadline First. The ready set is a min-heap keyed on the
// ABSOLUTE deadline, so the pop is always the most urgent job.
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <map>
struct Job {
    int deadline, left;
    std::string name;
};
struct Later {
    bool operator()(const Job& a, const Job& b) const {
        return a.deadline > b.deadline; // min-heap on deadline
    }
};
struct Task {
    std::string name;
    int c, p;
};
std::vector<std::string> edf(const std::vector<Task>& tasks, int horizon) {
    std::priority_queue<Job, std::vector<Job>, Later> ready;
    std::map<std::string, int> next;
    for (const auto& t : tasks) next[t.name] = 0;
    std::vector<std::string> timeline;
    for (int t = 0; t < horizon; ++t) {
        for (const auto& task : tasks) // releases at this tick
        if (next[task.name] == t) {
            ready.push({t + task.p, task.c, task.name});
            next[task.name] = t + task.p;
        }
        if (ready.empty()) {
            timeline.push_back("idle");
            continue;
        }
        Job j = ready.top();
        ready.pop(); // nearest deadline wins
        timeline.push_back(j.name);
        if (--j.left) ready.push(j); // preemptible: requeue
    }
    return timeline;
}
int main() {
    for (const auto& s : edf({{"T1",1,3},{"T2",2,5},{"T3",1,6}}, 15))
    std::cout << s << ' ';
    std::cout << '\n';
}

// Earliest Deadline First -- dynamic priority by absolute deadline.
import java.util.*;
class EDF {
    record Job(int deadline, int left, String name) {
    }
    static List<String> run(int[][] tasks, String[] names, int horizon) {
        // ordered by absolute deadline: the soonest deadline is highest priority
        PriorityQueue<Job> ready = new PriorityQueue<>(
        Comparator.comparingInt(Job::deadline));
        int[] next = new int[tasks.length];
        List<String> timeline = new ArrayList<>();
        for (int t = 0; t < horizon; t++) {
            for (int i = 0; i < tasks.length; i++)
            if (next[i] == t) {   // release
                ready.add(new Job(t + tasks[i][1], tasks[i][0], names[i]));
                next[i] = t + tasks[i][1];
            }
            if (ready.isEmpty()) {
                timeline.add("idle");
                continue;
            }
            Job j = ready.poll(); // most urgent
            timeline.add(j.name());
            if (j.left() - 1 > 0) // preempt back onto the heap
            ready.add(new Job(j.deadline(), j.left() - 1, j.name()));
            else if (t + 1 > j.deadline())
            throw new IllegalStateException("missed " + j.name());
        }
        return timeline;
    }
}