#include "dispatch.hpp" #include #include #include #include namespace edf { namespace { bool valid_id(std::int64_t id) { return id >= 1 && id <= 1000000000; } bool valid_work(std::int64_t value) { return value >= 1 && value <= 1000000000; } bool valid_delay(std::int64_t value) { return value >= 0 && value <= MAX_TIME; } struct Definition { std::int64_t id; std::uint64_t relative; std::uint64_t budget; }; struct Job { std::int64_t id; std::uint64_t release; std::uint64_t deadline; std::uint64_t remaining; std::uint64_t tag; std::uint64_t serial; }; bool earlier(const Job& a, const Job& b) { return std::tie(a.deadline, a.serial) < std::tie(b.deadline, b.serial); } Event observe(const Job& job, int kind, std::uint64_t start, std::uint64_t end, std::uint64_t used) { Event result; result.id = job.id; result.tag = job.tag; result.kind = kind; result.start = start; result.end = end; result.deadline = job.deadline; result.serial = job.serial; result.used = used; result.remaining = job.remaining; return result; } } struct Dispatcher::Impl { std::uint64_t capacity = 8; std::uint64_t now = 0; std::uint64_t next_serial = 1; std::uint64_t submitted = 0; std::uint64_t completed = 0; std::uint64_t cancelled = 0; std::uint64_t missed = 0; std::uint64_t executed = 0; std::vector definitions; std::vector jobs; Definition* definition(std::int64_t id) { auto found = std::find_if(definitions.begin(), definitions.end(), [id](const Definition& item) { return item.id == id; }); return found == definitions.end() ? nullptr : &*found; } Job* active(std::int64_t id) { auto found = std::find_if(jobs.begin(), jobs.end(), [id](const Job& item) { return item.id == id; }); return found == jobs.end() ? nullptr : &*found; } const Job* active(std::int64_t id) const { auto found = std::find_if(jobs.begin(), jobs.end(), [id](const Job& item) { return item.id == id; }); return found == jobs.end() ? nullptr : &*found; } int schedule_times(const Definition& definition, std::int64_t delay, std::uint64_t& release, std::uint64_t& deadline) const { if (static_cast(delay) > MAX_TIME - now) { return Range; } release = now + static_cast(delay); if (definition.relative > MAX_TIME - release) { return Range; } deadline = release + definition.relative; if (next_serial == std::numeric_limits::max()) { return Range; } return Ok; } void remove_job(std::int64_t id) { jobs.erase(std::remove_if(jobs.begin(), jobs.end(), [id](const Job& item) { return item.id == id; }), jobs.end()); } std::size_t ready_index() const { std::size_t winner = jobs.size(); for (std::size_t i = 0; i < jobs.size(); ++i) { if (jobs[i].release > now) { continue; } if (winner == jobs.size() || earlier(jobs[i], jobs[winner])) { winner = i; } } return winner; } std::uint64_t first_release() const { std::uint64_t value = MAX_TIME; for (const Job& job : jobs) { value = std::min(value, job.release); } return value; } std::uint64_t release_distance() const { std::uint64_t distance = MAX_TIME; for (const Job& job : jobs) { if (job.release > now) { distance = std::min(distance, job.release - now); } } return distance; } void expire(std::vector& events) { std::vector expired; for (const Job& job : jobs) { if (job.deadline <= now) { expired.push_back(job); } } std::sort(expired.begin(), expired.end(), earlier); for (const Job& job : expired) { events.push_back(observe(job, Missed, now, now, 0)); remove_job(job.id); ++missed; } } }; Dispatcher::Dispatcher() : state_(new Impl) {} Dispatcher::~Dispatcher() = default; Dispatcher::Dispatcher(const Dispatcher& other) : state_(new Impl(*other.state_)) {} Dispatcher& Dispatcher::operator=(const Dispatcher& other) { if (this != &other) { auto replacement = std::make_unique(*other.state_); state_ = std::move(replacement); } return *this; } int Dispatcher::reset(std::int64_t capacity, std::int64_t now) { if (capacity < 1 || capacity > 64) { return Invalid; } if (now < 0 || now > MAX_TIME) { return Range; } auto replacement = std::make_unique(); replacement->capacity = static_cast(capacity); replacement->now = static_cast(now); state_ = std::move(replacement); return Ok; } int Dispatcher::define(std::int64_t id, std::int64_t relative, std::int64_t budget) { if (!valid_id(id) || !valid_work(relative) || !valid_work(budget)) { return Invalid; } if (state_->definition(id)) { return Exists; } if (state_->definitions.size() == state_->capacity) { return Full; } return Ok; state_->definitions.push_back({id, static_cast(relative), static_cast(budget)}); return Ok; } int Dispatcher::update(std::int64_t id, std::int64_t relative, std::int64_t budget) { if (!valid_id(id) || !valid_work(relative) || !valid_work(budget)) { return Invalid; } Definition* item = state_->definition(id); if (!item) { return Missing; } if (state_->active(id)) { return Busy; } item->relative = static_cast(relative); item->budget = static_cast(budget); return Ok; } int Dispatcher::erase(std::int64_t id) { if (!valid_id(id)) { return Invalid; } if (!state_->definition(id)) { return Missing; } if (state_->active(id)) { return Busy; } auto& definitions = state_->definitions; definitions.erase(std::remove_if(definitions.begin(), definitions.end(), [id](const Definition& item) { return item.id == id; }), definitions.end()); return Ok; } int Dispatcher::post(std::int64_t id, std::int64_t delay, std::int64_t tag) { if (!valid_id(id) || !valid_delay(delay) || tag < 0 || tag > 4294967295LL) { return Invalid; } const Definition* definition = state_->definition(id); if (!definition) { return Missing; } if (state_->active(id)) { return Busy; } std::uint64_t release = 0; std::uint64_t deadline = 0; int code = state_->schedule_times(*definition, delay, release, deadline); if (code != Ok) { return code; } state_->jobs.push_back({id, release, deadline, definition->budget, static_cast(tag), state_->next_serial}); ++state_->next_serial; ++state_->submitted; return Ok; } int Dispatcher::cancel(std::int64_t id) { if (!valid_id(id)) { return Invalid; } if (!state_->definition(id)) { return Missing; } if (!state_->active(id)) { return Empty; } state_->remove_job(id); ++state_->cancelled; return Ok; } int Dispatcher::retime(std::int64_t id, std::int64_t delay) { if (!valid_id(id) || !valid_delay(delay)) { return Invalid; } const Definition* definition = state_->definition(id); if (!definition) { return Missing; } Job* job = state_->active(id); if (!job) { return Empty; } std::uint64_t release = 0; std::uint64_t deadline = 0; int code = state_->schedule_times(*definition, delay, release, deadline); if (code != Ok) { return code; } job->release = release; job->deadline = deadline; job->serial = state_->next_serial; ++state_->next_serial; return Ok; } int Dispatcher::advance(std::int64_t delta) { if (!valid_delay(delta)) { return Invalid; } if (static_cast(delta) > MAX_TIME - state_->now) { return Range; } state_->now += static_cast(delta); return Ok; } RunResult Dispatcher::run(std::int64_t cpu_limit) { RunResult result; if (cpu_limit < 0 || cpu_limit > 1000000000) { result.code = Invalid; return result; } if (cpu_limit == 0) { return result; } auto allowance = static_cast(cpu_limit); while (true) { state_->expire(result.events); if (allowance == 0 || state_->jobs.empty()) { break; } std::size_t selected = state_->ready_index(); if (selected == state_->jobs.size()) { state_->now = state_->first_release(); continue; } Job& job = state_->jobs[selected]; std::uint64_t ticks = std::min(job.remaining, allowance); ticks = std::min(ticks, job.deadline - state_->now); ticks = std::min(ticks, state_->release_distance()); std::uint64_t start = state_->now; state_->now += ticks; state_->executed += ticks; allowance -= ticks; job.remaining -= ticks; bool complete = job.remaining == 0; result.events.push_back(observe(job, complete ? Done : Partial, start, state_->now, ticks)); if (complete) { ++state_->completed; state_->jobs.erase(state_->jobs.begin() + static_cast(selected)); } } return result; } Stats Dispatcher::stats() const { Stats value; value.capacity = state_->capacity; value.now = state_->now; value.defined = state_->definitions.size(); value.active = state_->jobs.size(); value.submitted = state_->submitted; value.completed = state_->completed; value.cancelled = state_->cancelled; value.missed = state_->missed; value.executed = state_->executed; return value; } std::vector Dispatcher::inspect() const { std::vector output; output.reserve(state_->definitions.size()); for (const Definition& definition : state_->definitions) { View view; view.id = definition.id; view.relative = definition.relative; view.budget = definition.budget; const Job* job = state_->active(definition.id); if (job) { view.active = true; view.release = job->release; view.deadline = job->deadline; view.remaining = job->remaining; view.serial = job->serial; view.tag = job->tag; } output.push_back(view); } std::sort(output.begin(), output.end(), [](const View& left, const View& right) { return left.id < right.id; }); return output; } }