100 tasks from the HWE arm-linux code-gen pool (outside the lk/man/pth range given to batch 22), each with at least one independent contract-edge defect and plain public docs. Claude reviewed 100/100 USABLE against current digests; no ID or source overlap with main or batch 22. Difficulty is unmeasured. progress.md records the wrap-up: all Codex sessions and Qwen schedulers stopped for the user's rollout, Qwen results so far (57 HARD of 373), and what is left on each batch branch. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
221 lines
8.4 KiB
C++
221 lines
8.4 KiB
C++
#include "dispatch.hpp"
|
|
#include <algorithm>
|
|
#include <limits>
|
|
#include <map>
|
|
#include <set>
|
|
#include <tuple>
|
|
#include <utility>
|
|
namespace edf {
|
|
namespace {
|
|
bool id_ok(std::int64_t x) { return x >= 1 && x <= 1000000000; }
|
|
bool work_ok(std::int64_t x) { return x > 0 && x <= 1000000000; }
|
|
bool delay_ok(std::int64_t x) { return x >= 0 && x <= MAX_TIME; }
|
|
using Key = std::tuple<std::uint64_t, std::uint64_t, std::int64_t>;
|
|
struct Definition { std::uint64_t relative, budget; };
|
|
struct Job {
|
|
std::uint64_t release, deadline, remaining, tag, serial;
|
|
};
|
|
Event event(std::int64_t id, const Job& job, int kind, std::uint64_t begin,
|
|
std::uint64_t end, std::uint64_t ticks) {
|
|
return {id,job.tag,kind,begin,end,job.deadline,job.serial,ticks,job.remaining};
|
|
}
|
|
}
|
|
struct Dispatcher::Impl {
|
|
std::uint64_t capacity = 8, now = 0, next = 1;
|
|
std::uint64_t submitted = 0, completed = 0, cancelled = 0, missed = 0, executed = 0;
|
|
std::map<std::int64_t,Definition> definitions;
|
|
std::map<std::int64_t,Job> jobs;
|
|
std::set<Key> ready, waiting, deadlines;
|
|
Key deadline_key(std::int64_t id, const Job& j) const {
|
|
return {j.deadline,j.serial,id};
|
|
}
|
|
Key release_key(std::int64_t id, const Job& j) const {
|
|
return {j.release,j.serial,id};
|
|
}
|
|
void attach(std::int64_t id) {
|
|
const Job& j = jobs.at(id);
|
|
auto key = deadline_key(id,j);
|
|
deadlines.insert(key);
|
|
if (j.release <= now) ready.insert(key);
|
|
else waiting.insert(release_key(id,j));
|
|
}
|
|
void detach(std::int64_t id) {
|
|
const Job& j = jobs.at(id);
|
|
auto key = deadline_key(id,j);
|
|
deadlines.erase(key);
|
|
ready.erase(key);
|
|
waiting.erase(release_key(id,j));
|
|
}
|
|
void remove(std::int64_t id) {
|
|
detach(id);
|
|
jobs.erase(id);
|
|
}
|
|
void promote() {
|
|
while (!waiting.empty() && std::get<0>(*waiting.begin()) <= now) {
|
|
auto id = std::get<2>(*waiting.begin());
|
|
waiting.erase(waiting.begin());
|
|
ready.insert(deadline_key(id,jobs.at(id)));
|
|
}
|
|
}
|
|
int times(std::int64_t id, std::int64_t delay,
|
|
std::uint64_t& release, std::uint64_t& deadline) const {
|
|
if (static_cast<std::uint64_t>(delay) > MAX_TIME - now) return Range;
|
|
release = now + static_cast<std::uint64_t>(delay);
|
|
auto relative = definitions.at(id).relative;
|
|
if (relative > MAX_TIME - release) return Range;
|
|
deadline = release + relative;
|
|
if (next == std::numeric_limits<std::uint64_t>::max()) return Range;
|
|
return Ok;
|
|
}
|
|
};
|
|
Dispatcher::Dispatcher() : state_(std::make_unique<Impl>()) {}
|
|
Dispatcher::~Dispatcher() = default;
|
|
Dispatcher::Dispatcher(const Dispatcher& x) : state_(std::make_unique<Impl>(*x.state_)) {}
|
|
Dispatcher& Dispatcher::operator=(const Dispatcher& x) {
|
|
if (this != &x) state_ = std::make_unique<Impl>(*x.state_);
|
|
return *this;
|
|
}
|
|
int Dispatcher::reset(std::int64_t cap, std::int64_t now) {
|
|
if (cap < 1 || cap > 64) return Invalid;
|
|
if (now < 0 || now > MAX_TIME) return Range;
|
|
auto replacement = std::make_unique<Impl>();
|
|
replacement->capacity = cap;
|
|
replacement->now = now;
|
|
state_ = std::move(replacement);
|
|
return Ok;
|
|
}
|
|
int Dispatcher::define(std::int64_t id, std::int64_t relative, std::int64_t budget) {
|
|
if (!id_ok(id) || !work_ok(relative) || !work_ok(budget)) return Invalid;
|
|
if (state_->definitions.count(id)) return Exists;
|
|
if (state_->definitions.size() == state_->capacity) return Full;
|
|
state_->definitions.emplace(id,Definition{static_cast<std::uint64_t>(relative),
|
|
static_cast<std::uint64_t>(budget)});
|
|
return Ok;
|
|
}
|
|
int Dispatcher::update(std::int64_t id, std::int64_t relative, std::int64_t budget) {
|
|
if (!id_ok(id) || !work_ok(relative) || !work_ok(budget)) return Invalid;
|
|
auto found = state_->definitions.find(id);
|
|
if (found == state_->definitions.end()) return Missing;
|
|
if (state_->jobs.count(id)) return Busy;
|
|
found->second = {static_cast<std::uint64_t>(relative),static_cast<std::uint64_t>(budget)};
|
|
return Ok;
|
|
}
|
|
int Dispatcher::erase(std::int64_t id) {
|
|
if (!id_ok(id)) return Invalid;
|
|
if (!state_->definitions.count(id)) return Missing;
|
|
if (state_->jobs.count(id)) return Busy;
|
|
state_->definitions.erase(id);
|
|
return Ok;
|
|
}
|
|
int Dispatcher::post(std::int64_t id, std::int64_t delay, std::int64_t tag) {
|
|
if (!id_ok(id) || !delay_ok(delay) || tag < 0 || tag > 4294967295LL) return Invalid;
|
|
if (!state_->definitions.count(id)) return Missing;
|
|
if (state_->jobs.count(id)) return Busy;
|
|
std::uint64_t release = 0, deadline = 0;
|
|
int status = state_->times(id,delay,release,deadline);
|
|
if (status) return status;
|
|
state_->jobs.emplace(id,Job{release,deadline,state_->definitions.at(id).budget,
|
|
static_cast<std::uint64_t>(tag),state_->next});
|
|
state_->attach(id);
|
|
++state_->next;
|
|
++state_->submitted;
|
|
return Ok;
|
|
}
|
|
int Dispatcher::cancel(std::int64_t id) {
|
|
if (!id_ok(id)) return Invalid;
|
|
if (!state_->definitions.count(id)) return Missing;
|
|
if (!state_->jobs.count(id)) return Empty;
|
|
state_->remove(id);
|
|
++state_->cancelled;
|
|
return Ok;
|
|
}
|
|
int Dispatcher::retime(std::int64_t id, std::int64_t delay) {
|
|
if (!id_ok(id) || !delay_ok(delay)) return Invalid;
|
|
if (!state_->definitions.count(id)) return Missing;
|
|
auto found = state_->jobs.find(id);
|
|
if (found == state_->jobs.end()) return Empty;
|
|
std::uint64_t release = 0, deadline = 0;
|
|
int status = state_->times(id,delay,release,deadline);
|
|
if (status) return status;
|
|
state_->detach(id);
|
|
found->second.release = release;
|
|
found->second.deadline = deadline;
|
|
found->second.serial = state_->next++;
|
|
state_->attach(id);
|
|
return Ok;
|
|
}
|
|
int Dispatcher::advance(std::int64_t delta) {
|
|
if (!delay_ok(delta)) return Invalid;
|
|
if (static_cast<std::uint64_t>(delta) > MAX_TIME - state_->now) return Range;
|
|
state_->now += delta;
|
|
state_->promote();
|
|
return Ok;
|
|
}
|
|
RunResult Dispatcher::run(std::int64_t cpu_limit) {
|
|
if (cpu_limit < 0 || cpu_limit > 1000000000) return {Invalid,{}};
|
|
RunResult result;
|
|
if (cpu_limit == 0) return result;
|
|
auto left = static_cast<std::uint64_t>(cpu_limit);
|
|
for (;;) {
|
|
while (!state_->deadlines.empty() && std::get<0>(*state_->deadlines.begin()) <= state_->now) {
|
|
auto id = std::get<2>(*state_->deadlines.begin());
|
|
result.events.push_back(event(id,state_->jobs.at(id),Missed,state_->now,state_->now,0));
|
|
state_->remove(id);
|
|
++state_->missed;
|
|
}
|
|
if (!left || state_->jobs.empty()) break;
|
|
state_->promote();
|
|
if (state_->ready.empty()) {
|
|
state_->now = std::get<0>(*state_->waiting.begin());
|
|
state_->promote();
|
|
continue;
|
|
}
|
|
auto id = std::get<2>(*state_->ready.begin());
|
|
Job& job = state_->jobs.at(id);
|
|
auto ticks = std::min({left,job.remaining,job.deadline-state_->now});
|
|
if (!state_->waiting.empty()) {
|
|
ticks = std::min(ticks,std::get<0>(*state_->waiting.begin())-state_->now);
|
|
}
|
|
auto begin = state_->now;
|
|
state_->now += ticks;
|
|
left -= ticks;
|
|
job.remaining -= ticks;
|
|
state_->executed += ticks;
|
|
int kind = job.remaining ? Partial : Done;
|
|
result.events.push_back(event(id,job,kind,begin,state_->now,ticks));
|
|
if (kind == Done) {
|
|
state_->remove(id);
|
|
++state_->completed;
|
|
}
|
|
}
|
|
return result;
|
|
}
|
|
Stats Dispatcher::stats() const {
|
|
return {state_->capacity,state_->now,state_->definitions.size(),state_->jobs.size(),
|
|
state_->submitted,state_->completed,state_->cancelled,state_->missed,state_->executed};
|
|
}
|
|
std::vector<View> Dispatcher::inspect() const {
|
|
std::vector<View> result;
|
|
for (const auto& pair : state_->definitions) {
|
|
auto id = pair.first;
|
|
const auto& definition = pair.second;
|
|
View v;
|
|
v.id = id;
|
|
v.relative = definition.relative;
|
|
v.budget = definition.budget;
|
|
auto found = state_->jobs.find(id);
|
|
if (found != state_->jobs.end()) {
|
|
const Job& j = found->second;
|
|
v.active = true;
|
|
v.release = j.release;
|
|
v.deadline = j.deadline;
|
|
v.remaining = j.remaining;
|
|
v.serial = j.serial;
|
|
v.tag = j.tag;
|
|
}
|
|
result.push_back(v);
|
|
}
|
|
return result;
|
|
}
|
|
}
|