Algo Library¶

The algo library (schedsim::algo) implements scheduling algorithms, bandwidth servers, allocators, and energy management policies on top of the core simulation engine.

Schedulers¶

Scheduler (Abstract Base)¶

class Scheduler¶

Abstract interface for scheduling algorithms.

A Scheduler manages a set of processors and makes dispatch decisions. Concrete implementations (e.g., EdfScheduler) maintain a ready queue of CBS servers and assign them to processors according to a scheduling policy.

See also

EdfScheduler, CbsServer, Allocator

Subclassed by schedsim::algo::EdfScheduler

Public Functions

virtual void on_job_arrival(core::Task &task, core::Job job) = 0¶

Handle a job arrival for a task.

The scheduler should find or create a server for the task and enqueue the job. This is the main entry point called by the allocator or directly by the simulation engine on each job release.

See also

Allocator::on_job_arrival

Parameters:

task – The task that released the job.
job – The newly released job to be scheduled.

virtual bool can_admit(core::Duration budget, core::Duration period) const = 0¶

Check if a new server with the given budget/period can be admitted.

Performs an admission test to determine whether adding a server with utilization budget/period would exceed the scheduler’s capacity bound.

See also

AdmissionTest, AdmissionError

Parameters:

budget – The maximum execution budget per period.
period – The replenishment period.

Returns:

True if the server can be admitted without violating the utilization bound; false otherwise.

virtual double utilization() const = 0¶

Get the total server utilization of this scheduler.

Returns the sum of utilizations (budget/period) of all servers currently registered with this scheduler.

Returns:: Total utilization as a dimensionless ratio.

virtual std::size_t processor_count() const noexcept = 0¶

Get the number of processors managed by this scheduler.

Returns:: The processor count.

inline virtual void set_expected_arrivals(const core::Task &task, std::size_t count)¶

Set the expected number of job arrivals for a task.

Used for server detach tracking: when a task has released all its expected jobs and they have completed, the scheduler may detach the associated server to reclaim bandwidth. The default implementation is a no-op.

Parameters:

task – The task whose expected arrival count is being set.
count – The total number of jobs expected from this task.

virtual ~Scheduler() = default¶

EDF Scheduler¶

class EdfScheduler : public schedsim::algo::Scheduler ¶

Earliest Deadline First scheduler with CBS bandwidth servers.

Manages a set of processors and dispatches jobs to CBS servers ordered by absolute deadline. Supports GRUB/CASH reclamation, DVFS frequency scaling policies (PA, FFA, CSF), and DPM power management.

Each task is assigned a CBS server via add_server(). When a job arrives, the scheduler replenishes the server budget (if needed), inserts the server into the EDF ready queue, and dispatches the highest-priority server to an available processor.

Example

core::Engine engine;
auto& plat = engine.platform();
auto& pt = plat.add_processor_type("cpu", 1.0);
auto& cd = plat.add_clock_domain(Frequency{500.0}, Frequency{2000.0});
auto& pd = plat.add_power_domain(
    {{0, CStateScope::PerProcessor, duration_from_seconds(0.0), Power{100.0}}});
auto& proc = plat.add_processor(pt, cd, pd);
auto& task = plat.add_task(
    duration_from_seconds(0.01),   // period: 10 ms
    duration_from_seconds(0.01),   // deadline: 10 ms
    duration_from_seconds(0.005)); // WCET: 5 ms
engine.finalize();

algo::EdfScheduler sched(engine, {&proc});
sched.add_server(task);
sched.enable_grub();
engine.run();

Scheduler Interface

virtual void on_job_arrival(core::Task &task, core::Job job) override¶

Handle a new job arrival for a task.

Parameters:

task – The task that owns the arriving job.
job – The new job instance.

virtual void set_expected_arrivals(const core::Task &task, std::size_t count) override¶

Set the expected number of job arrivals for a task.

Used by M-GRUB for server detach: when all expected arrivals have been received and the server becomes Inactive, the server is detached from the scheduler to reduce active utilization.

Parameters:

task – The task to track.
count – Total number of expected job arrivals.

virtual bool can_admit(core::Duration budget, core::Duration period) const override¶

Test whether a new server with the given utilization can be admitted.

Parameters:

budget – Requested server budget.
period – Requested server period.

Returns:

True if admitting the server would not exceed capacity.

virtual double utilization() const override¶

Returns the total utilization of all servers.

Returns:: Total utilization as a dimensionless ratio.

Migration Support

void remove_inactive_server(core::Task &task)¶

Remove an Inactive server for a task (used by cluster migration).

Decrements total_utilization_, erases the task_to_server_ mapping, and notifies the reclamation policy with Detached.

Warning

Internal migration method. Directly modifies scheduler state without full consistency checks. Use only from MultiClusterAllocator.

Parameters:: task – The task whose server should be removed.
Pre:: The server must be in Inactive state.

void detach_task_mapping(core::Task &task)¶

Detach the task-to-server mapping without removing the server.

Used for zombie migration: the CBS server stays alive for GRUB deadline tracking, but the task mapping is cleared so new jobs do not route to the old server.

Warning

Internal migration method. Erases the task-to-server mapping without removing the server. Use only from MultiClusterAllocator.

Parameters:: task – The task to unlink from its server.

void adjust_utilization(double delta)¶

Temporarily adjust total_utilization_ for migration evaluation.

The allocator uses this to temporarily exclude a server’s utilization while re-evaluating cluster placement, then restores it.

Warning

Dangerous: directly modifies total_utilization_ without notifying reclamation, DVFS, or DPM policies. Must be paired with a corresponding restore call. Use only from MultiClusterAllocator.

Parameters:: delta – The amount to add (negative to subtract).

std::optional<std::size_t> get_expected_arrivals(const core::Task &task) const¶

Get the expected number of arrivals for a task, if set.

Parameters:: task – The task to query.
Returns:: The expected arrival count, or std::nullopt if not set.

std::size_t get_arrival_count(const core::Task &task) const¶

Get the number of arrivals received for a task.

Parameters:: task – The task to query.
Returns:: The arrival count (0 if task has never arrived).

Server Management

CbsServer &add_server(core::Task &task, core::Duration budget, core::Duration period, CbsServer::OverrunPolicy policy = CbsServer::OverrunPolicy::Queue)¶

Add a CBS server for a task with explicit budget and period.

The server utilization (budget/period) is checked against the admission test. Throws AdmissionError if over capacity.

Parameters:

task – Task to associate with the server.
budget – Server budget per period.
period – Server replenishment period.
policy – What to do when the budget is exhausted mid-job.

Throws:

AdmissionError – if admission test fails.

Returns:

Reference to the created CbsServer.

CbsServer &add_server(core::Task &task)¶

Add a CBS server using the task’s WCET as budget and the task’s period.

Parameters:: task – Task to associate with the server.
Returns:: Reference to the created CbsServer.

CbsServer &add_server_unchecked(core::Task &task, core::Duration budget, core::Duration period, CbsServer::OverrunPolicy policy = CbsServer::OverrunPolicy::Queue)¶

Add a CBS server without running the admission test.

Use for testing or advanced scenarios where the caller manages capacity.

Parameters:

task – Task to associate with the server.
budget – Server budget per period.
period – Server replenishment period.
policy – What to do when the budget is exhausted mid-job.

Returns:

Reference to the created CbsServer.

CbsServer *find_server(core::Task &task)¶

Find the CBS server for a task, or nullptr if none.

Parameters:: task – The task to look up.
Returns:: Pointer to the CBS server, or nullptr.

const CbsServer *find_server(const core::Task &task) const¶

Find the CBS server for a task (const), or nullptr if none.

Parameters:: task – The task to look up.
Returns:: Const pointer to the CBS server, or nullptr.

inline std::size_t server_count() const noexcept¶

Returns the number of CBS servers.

Returns:: Server count.

Configuration

void set_admission_test(AdmissionTest test)¶

Set the admission test mode.

Parameters:: test – The admission test to use.

void set_deadline_miss_policy(DeadlineMissPolicy policy)¶

Set the policy for handling deadline misses on processors.

Parameters:: policy – The deadline miss policy to apply.

void set_deadline_miss_handler(std::function<void(core::Processor&, core::Job&)> handler)¶

Set a callback invoked when a running job misses its deadline.

Parameters:: handler – Callback receiving the processor and job.

void set_queued_deadline_miss_handler(std::function<void(core::Job&)> handler)¶

Set a callback invoked when a queued job misses its deadline.

Parameters:: handler – Callback receiving the job.

Policy Management

void set_reclamation_policy(std::unique_ptr<ReclamationPolicy> policy)¶

Set the bandwidth reclamation policy (GRUB or CASH).

Parameters:: policy – Reclamation policy (ownership transferred).

void set_dvfs_policy(std::unique_ptr<DvfsPolicy> policy)¶

Set the DVFS frequency scaling policy.

Parameters:: policy – DVFS policy (ownership transferred).

void set_dpm_policy(std::unique_ptr<DpmPolicy> policy)¶

Set the DPM power management policy.

Parameters:: policy – DPM policy (ownership transferred).

Convenience Policy Methods

Shorthand for creating and setting standard policies.

void enable_grub()¶: Enable GRUB bandwidth reclamation.

void enable_cash()¶: Enable CASH bandwidth reclamation.

void enable_power_aware_dvfs(core::Duration cooldown = core::duration_from_seconds(0.0))¶

Enable Power-Aware DVFS.

Parameters:: cooldown – Minimum time between frequency changes.

void enable_basic_dpm(int target_cstate = 1)¶

Enable basic DPM (put idle cores to sleep).

Parameters:: target_cstate – Target C-state for idle cores.

void enable_ffa(core::Duration cooldown = core::duration_from_seconds(0.0), int sleep_cstate = 1)¶

Enable FFA (Feedback-based Frequency Adaptation) with integrated DPM.

Parameters:

cooldown – Minimum time between frequency changes.
sleep_cstate – Target C-state for idle cores.

void enable_csf(core::Duration cooldown = core::duration_from_seconds(0.0), int sleep_cstate = 1)¶

Enable CSF (Cluster-level Sleep Frequency) with integrated DPM.

Parameters:

cooldown – Minimum time between frequency changes.
sleep_cstate – Target C-state for idle cores.

void enable_ffa_timer(core::Duration cooldown = core::duration_from_seconds(0.0), int sleep_cstate = 1)¶

Enable timer-based FFA variant.

Parameters:

cooldown – Minimum time between frequency changes.
sleep_cstate – Target C-state for idle cores.

void enable_csf_timer(core::Duration cooldown = core::duration_from_seconds(0.0), int sleep_cstate = 1)¶

Enable timer-based CSF variant.

Parameters:

cooldown – Minimum time between frequency changes.
sleep_cstate – Target C-state for idle cores.

Utilization Queries

double active_utilization() const¶

Returns the sum of utilization for currently active servers.

Returns:: Active utilization as a dimensionless ratio.

double scheduler_utilization() const¶

Returns the sum of utilization for servers in the scheduler (activated, not detached).

Returns:: Scheduler utilization as a dimensionless ratio.

double max_scheduler_utilization() const¶

Returns the maximum utilization among in-scheduler servers.

Returns:: Maximum single-server utilization in the scheduler.

double max_server_utilization() const¶

Returns the maximum utilization among all servers.

Returns:: Maximum single-server utilization.

Public Functions

EdfScheduler(core::Engine &engine, std::vector<core::Processor*> processors)¶

Construct an EDF scheduler managing the given processors.

Parameters:

engine – Reference to the simulation engine.
processors – Processors that this scheduler dispatches to.

~EdfScheduler() override¶

EdfScheduler(const EdfScheduler&) = delete¶

EdfScheduler &operator=(const EdfScheduler&) = delete¶

EdfScheduler(EdfScheduler&&) = delete¶

EdfScheduler &operator=(EdfScheduler&&) = delete¶

std::span<core::Processor*const> processors() const¶

Returns a view of the managed processors.

Returns:: Read-only span of processor pointers.

inline virtual std::size_t processor_count() const noexcept override¶

Returns the number of managed processors.

Returns:: Processor count.

void try_detach_server(CbsServer &server)¶

Attempt to detach a server from the scheduler (M-GRUB).

A server is detached when it is Inactive and all expected job arrivals have been received. Detached servers no longer contribute to active utilization.

Parameters:: server – The CBS server to try detaching.

inline core::Engine &engine() noexcept¶

Access the simulation engine.

Returns:: Reference to the engine.

inline const core::Engine &engine() const noexcept¶

Access the simulation engine (const).

Returns:: Const reference to the engine.

CBS Servers¶

class CbsServer¶

Constant Bandwidth Server (CBS) implementation.

A CbsServer reserves a fraction of processor bandwidth (budget/period) for a single task. It maintains a FIFO job queue, tracks a scheduling deadline used by EDF, and implements the CBS state machine for budget replenishment, exhaustion, and optional GRUB non-contending behaviour.

Servers are non-copyable but movable so they can be stored in containers.

See also

EdfScheduler, Scheduler, GrubPolicy

Public Types

enum class State¶

Server state machine states.

Values:

enumerator Inactive¶: No pending jobs; server is dormant.

enumerator Ready¶: Has pending jobs, waiting to be dispatched by EDF.

enumerator Running¶: Currently executing on a processor.

enumerator NonContending¶: GRUB: job completed early, waiting for deadline expiry.

enum class OverrunPolicy¶

Policy for handling a new job arrival while the server is already active.

Values:

enumerator Queue¶: Queue the new job behind the current one (default).

enumerator Skip¶: Drop the new job silently.

enumerator Abort¶: Abort the current job and start the new one immediately.

Public Functions

CbsServer(std::size_t id, core::Duration budget, core::Duration period, OverrunPolicy policy = OverrunPolicy::Queue)¶

Construct a CBS server with the given bandwidth reservation.

Parameters:

id – Unique identifier (used for deterministic tie-breaking in EDF).
budget – Maximum execution budget per period (Q).
period – Replenishment period (T). Utilization = Q/T.
policy – How to handle a new arrival when the server is active.

inline std::size_t id() const noexcept¶

Get the server’s unique identifier.

Returns:: Server ID used for deterministic EDF tie-breaking.

~CbsServer() = default¶

inline core::Duration budget() const noexcept¶

Get the maximum execution budget per period (Q).

Returns:: The server budget as a Duration.

inline core::Duration period() const noexcept¶

Get the replenishment period (T).

Returns:: The server period as a Duration.

inline double utilization() const noexcept¶

Get the server utilization (Q / T).

Returns:: Utilization as a dimensionless ratio in [0, 1].

inline State state() const noexcept¶

Get the current server state.

See also

State

Returns:: One of Inactive, Ready, Running, or NonContending.

inline core::TimePoint deadline() const noexcept¶

Get the current scheduling deadline.

Returns:: The absolute deadline used by EDF for priority ordering.

inline core::TimePoint virtual_time() const noexcept¶

Get the current virtual time.

Virtual time tracks logical progress and is used by GRUB for reclamation accounting.

See also

update_virtual_time, set_virtual_time

Returns:: The server’s virtual time.

inline core::Duration remaining_budget() const noexcept¶

Get the remaining execution budget.

Returns:: Budget left before the server must be replenished.

inline OverrunPolicy overrun_policy() const noexcept¶

Get the overrun policy for this server.

See also

OverrunPolicy

Returns:: The OverrunPolicy set at construction.

inline bool has_pending_jobs() const noexcept¶

Check whether the server has pending jobs.

Returns:: True if the job queue is non-empty.

inline std::size_t job_queue_size() const noexcept¶

Get the number of jobs waiting in the queue.

Returns:: Queue depth.

inline uint64_t last_enqueued_job_id() const noexcept¶

Get the ID of the most recently enqueued job.

Returns:: Job ID (monotonically increasing per server).

core::Job *current_job()¶

Get a pointer to the job at the head of the queue.

Returns:: Pointer to the current job, or nullptr if the queue is empty.

const core::Job *current_job() const¶

Get a const pointer to the job at the head of the queue.

Returns:: Const pointer to the current job, or nullptr if the queue is empty.

void enqueue_job(core::Job job)¶

Enqueue a new job at the back of the server’s FIFO queue.

Parameters:: job – The job to enqueue.

core::Job dequeue_job()¶

Dequeue and return the job at the front of the queue.

Throws:: std::logic_error – if the queue is empty.
Returns:: The dequeued job.

void activate(core::TimePoint current_time)¶

Activate the server (Inactive -> Ready).

Called when a job arrives for an inactive server. Initialises the deadline and virtual time based on the current simulation time.

Parameters:: current_time – The current simulation time.

void dispatch()¶

Dispatch the server (Ready -> Running).

Called by EDF when this server is selected for execution on a processor.

void preempt()¶

Preempt the server (Running -> Ready).

Called when a higher-priority server preempts this one.

void complete_job(core::TimePoint current_time)¶

Complete the current job (Running -> Ready or Inactive).

Transitions to Ready if further jobs are queued, or to Inactive if the queue is empty.

Parameters:: current_time – The current simulation time.

void abort_queued_job()¶

Abort the head job from the queue without executing it.

Used for queued deadline-miss handling. Transitions to Inactive if the queue becomes empty after removal.

void exhaust_budget(core::TimePoint current_time)¶

Handle budget exhaustion (Running -> Ready).

Called when the remaining budget reaches zero. Postpones the deadline and replenishes the budget.

See also

postpone_deadline

Parameters:: current_time – The current simulation time.

void enter_non_contending(core::TimePoint current_time)¶

Enter non-contending state (Running -> NonContending).

GRUB extension: the job completed early and the server waits for its deadline to expire before releasing its bandwidth.

See also

GrubPolicy

Parameters:: current_time – The current simulation time.

void reactivate_from_non_contending()¶

Reactivate from non-contending (NonContending -> Ready).

GRUB extension: a new job arrives while the server is waiting for its deadline, so it re-enters the ready queue.

void reach_deadline(core::TimePoint current_time)¶

Handle deadline expiry in non-contending state (NonContending -> Inactive).

GRUB extension: the server’s deadline is reached while non-contending, so it becomes inactive and releases its bandwidth.

Parameters:: current_time – The current simulation time.

void update_virtual_time(core::Duration execution_time)¶

Update virtual time after execution.

Advances virtual time by execution_time / utilization, reflecting the logical time consumed by the server.

See also

set_virtual_time

Parameters:: execution_time – The wall-clock execution time to account for.

inline void set_virtual_time(core::TimePoint vt) noexcept¶

Set the virtual time directly.

Used when a reclamation policy (e.g., GRUB) computes virtual time externally.

See also

update_virtual_time

Parameters:: vt – The new virtual time value.

void postpone_deadline()¶

Postpone the deadline and replenish the budget.

Advances the deadline by one period (d += T) and resets the remaining budget to the full budget (remaining = Q).

void consume_budget(core::Duration amount)¶

Consume a portion of the remaining budget.

Parameters:: amount – The amount of budget to subtract.

void set_pending_removal(std::function<void()> callback)¶

Mark this server for deferred removal (zombie migration).

When the server eventually transitions to Inactive (e.g., after a GRUB deadline fires), the callback is invoked and the server is cleaned up by EdfScheduler::try_detach_server().

Parameters:: callback – Cleanup action to run when the zombie is removed.

inline bool is_pending_removal() const noexcept¶

Check if this server is marked for deferred removal.

Returns:: True if set_pending_removal() was called.

void fire_removal_callback()¶: Fire and clear the removal callback (idempotent).

inline core::Task *task() const noexcept¶

Get the task associated with this server.

The association is established by EdfScheduler when the server is registered for a task.

See also

EdfScheduler

Returns:: Pointer to the associated task, or nullptr if none.

Allocators¶

Allocator (Abstract Base)¶

class Allocator¶

Abstract interface for job allocation.

An Allocator routes incoming jobs to the appropriate Scheduler. Concrete implementations decide the mapping strategy (e.g., partitioned worst-fit, best-fit, or global).

See also

Scheduler, Cluster

Subclassed by schedsim::algo::MultiClusterAllocator, schedsim::algo::SingleSchedulerAllocator

Public Functions

virtual void on_job_arrival(core::Task &task, core::Job job) = 0¶

Handle a job arrival for a task.

The allocator decides which scheduler should handle this job and forwards it accordingly.

See also

Scheduler::on_job_arrival

Parameters:

task – The task that released the job.
job – The newly released job to be routed.

Throws:

AllocationError – if no suitable scheduler can accept the job.

virtual ~Allocator() = default¶

Cluster¶

class Cluster¶

Lightweight algo-layer wrapper tying a ClockDomain to a Scheduler.

A Cluster binds a hardware ClockDomain to a scheduling entity and carries allocation metadata such as performance score, frequency-normalisation factor, and utilization target. It lives in the algo layer (rather than core) because it couples scheduling concepts (Scheduler, admission, u_target) to hardware concepts (ClockDomain).

Used by partitioned allocators to represent one scheduling unit (one or more processors sharing a clock domain and a scheduler).

See also

Allocator, Scheduler, core::ClockDomain

Public Functions

Cluster(core::ClockDomain &clock_domain, Scheduler &scheduler, double perf_score, double reference_freq_max)¶

Construct a Cluster binding a clock domain to a scheduler.

Parameters:

clock_domain – The hardware clock domain for this cluster.
scheduler – The scheduler managing processors in this cluster.
perf_score – Performance score of the cluster’s processor type (dimensionless; higher is faster).
reference_freq_max – Maximum frequency of the reference cluster, used for cross-cluster normalisation.

inline core::ClockDomain &clock_domain() noexcept¶

Get the underlying clock domain (mutable).

Returns:: Reference to the ClockDomain.

inline const core::ClockDomain &clock_domain() const noexcept¶

Get the underlying clock domain (const).

Returns:: Const reference to the ClockDomain.

inline Scheduler &scheduler() noexcept¶

Get the associated scheduler (mutable).

Returns:: Reference to the Scheduler.

inline const Scheduler &scheduler() const noexcept¶

Get the associated scheduler (const).

Returns:: Const reference to the Scheduler.

inline double perf() const noexcept¶

Get the performance score of this cluster’s processor type.

Returns:: Dimensionless performance score (higher is faster).

double scale_speed() const noexcept¶

Compute the cross-cluster frequency normalisation factor.

Returns reference_freq_max / this_cluster_freq_max, matching the legacy Cluster::scale_speed() semantics.

Returns:: Frequency scaling ratio (>=1.0 for slower clusters).

inline double u_target() const noexcept¶

Get the utilization target for allocation decisions.

Returns:: Current utilization target in [0, 1].

inline void set_u_target(double target) noexcept¶

Set the utilization target for allocation decisions.

Mutable because adaptive allocators may adjust it at run time.

Parameters:: target – New utilization target in [0, 1].

double scaled_utilization(double task_util) const noexcept¶

Scale a task’s utilization to this cluster.

Computes task_util * scale_speed() / perf(), converting a reference-normalised utilization into the cluster-local value.

Parameters:: task_util – The task utilization in reference units.
Returns:: Scaled utilization for this cluster.

void set_processor_id(std::size_t id) noexcept¶

Set the processor ID when this cluster wraps a single processor.

Used in per-core partitioned mode where each cluster contains exactly one processor.

Parameters:: id – The processor ID.

std::optional<std::size_t> processor_id() const noexcept¶

Get the single-processor ID, if set.

Returns:: The processor ID, or std::nullopt if not in per-core mode.

double remaining_capacity() const noexcept¶

Get the remaining scheduling capacity.

Computed as processor_count - raw utilization. Uses raw (reference) utilization rather than scaled utilization. Worst-fit / best-fit allocators rank clusters by this value within the scaled-utilization-admissible set.

Returns:: Remaining capacity as a dimensionless value.

std::size_t processor_count() const noexcept¶

Get the number of processors in this cluster.

See also

Scheduler::processor_count

Returns:: Processor count (delegated to Scheduler).

double utilization() const noexcept¶

Get the total utilization of the cluster’s scheduler.

See also

Scheduler::utilization

Returns:: Total server utilization (delegated to Scheduler).

bool can_admit(core::Duration budget, core::Duration period) const¶

Check if a new server can be admitted to this cluster.

See also

Scheduler::can_admit

Parameters:

budget – The server budget.
period – The server period.

Returns:

True if the server can be admitted.

bool try_admit_scaled(double task_util)¶

Try to admit a task using cluster-level GFB with scaled utilization.

Performs two checks using the cluster-local (scaled) utilization:

GFB: total_scaled_util + scaled_util <= m - (m-1)*u_max_scaled
u_target: scaled_util <= u_target

If both pass, updates internal scaled-utilization tracking and returns true.

Parameters:: task_util – The task utilization in reference units.
Returns:: True if the task was admitted.

void unadmit_scaled(double task_util)¶

Reverse a previous try_admit_scaled() call.

Decrements total_scaled_utilization_ and recomputes max_scaled_utilization_ from the remaining admitted tasks (O(n)).

Parameters:: task_util – The task utilization in reference units (same value originally passed to try_admit_scaled).

void readmit_scaled(double task_util)¶

Unconditionally restore accounting for a previously unadmitted task.

Used for rollback: re-adds the scaled utilization without performing admission checks (u_target, GFB). This is the inverse of unadmit_scaled.

Parameters:: task_util – The task utilization in reference units.

inline double total_scaled_utilization() const noexcept¶

Get the total scaled utilization of admitted tasks.

Returns:: Total scaled utilization.

MultiClusterAllocator¶

class MultiClusterAllocator : public schedsim::algo::Allocator ¶

Base allocator for multi-cluster systems.

Routes incoming jobs to one of several Cluster instances via the virtual select_cluster() hook. Task binding is permanent: once a task has been assigned to a cluster by select_cluster(), every subsequent job of that task is forwarded to the same cluster without re-invoking the selection logic.

Concrete subclasses (FirstFitAllocator, WorstFitAllocator, BestFitAllocator) implement different bin-packing heuristics by overriding select_cluster().

Subclassed by schedsim::algo::BestFitAllocator, schedsim::algo::CountingAllocator, schedsim::algo::FFBigFirstAllocator, schedsim::algo::FFCapAdaptiveLinearAllocator, schedsim::algo::FFCapAdaptivePolyAllocator, schedsim::algo::FFCapAllocator, schedsim::algo::FFLbAllocator, schedsim::algo::FFLittleFirstAllocator, schedsim::algo::FirstFitAllocator, schedsim::algo::MCTSAllocator, schedsim::algo::WorstFitAllocator

Public Functions

MultiClusterAllocator(core::Engine &engine, std::vector<Cluster*> clusters)¶

Construct a multi-cluster allocator.

Parameters:

engine – Reference to the simulation engine (for event scheduling).
clusters – Non-owning pointers to the clusters available for task placement. Order matters for tie-breaking in derived allocators.

~MultiClusterAllocator() override = default¶: Virtual destructor.

MultiClusterAllocator(const MultiClusterAllocator&) = delete¶: Non-copyable, non-movable (registered with engine).

MultiClusterAllocator &operator=(const MultiClusterAllocator&) = delete¶

MultiClusterAllocator(MultiClusterAllocator&&) = delete¶

MultiClusterAllocator &operator=(MultiClusterAllocator&&) = delete¶

virtual void on_job_arrival(core::Task &task, core::Job job) override¶

Handle a job arrival for a task.

If the task has already been assigned to a cluster, the job is forwarded directly. Otherwise select_cluster() is called to choose a cluster, and the assignment is recorded permanently.

When migration is enabled, select_cluster() is called on every arrival. If a different cluster is selected and the server is in a migratable state (Inactive or NonContending), the task moves to the new cluster.

See also

Allocator::on_job_arrival

Parameters:

task – The task that produced the job.
job – The newly arrived job to dispatch.

inline void enable_migration() noexcept¶

Enable task migration on subsequent job arrivals.

When enabled, each job arrival re-evaluates cluster placement via select_cluster(). If a better cluster is found and the server is Inactive or NonContending, the task migrates.

SingleSchedulerAllocator¶

class SingleSchedulerAllocator : public schedsim::algo::Allocator ¶

Allocator that routes all jobs to a single Scheduler instance.

This is the simplest allocator strategy: every task is placed on the same scheduler, making it suitable for global scheduling policies (e.g. global EDF on a single clock domain) or single-scheduler setups.

On the first job arrival for a given task, the task is registered with the scheduler (and optionally with a ClockDomain for DVFS-aware accounting). Subsequent jobs for the same task are forwarded directly.

Public Functions

SingleSchedulerAllocator(core::Engine &engine, Scheduler &scheduler, core::ClockDomain *clock_domain = nullptr)¶

Construct a single-scheduler allocator.

Parameters:

engine – Reference to the simulation engine.
scheduler – The unique scheduler that will receive all jobs.
clock_domain – Optional clock domain for DVFS-aware task placement. Pass nullptr when DVFS is unused.

~SingleSchedulerAllocator() override = default¶: Virtual destructor.

SingleSchedulerAllocator(const SingleSchedulerAllocator&) = delete¶: Non-copyable, non-movable (registered with engine).

SingleSchedulerAllocator &operator=(const SingleSchedulerAllocator&) = delete¶

SingleSchedulerAllocator(SingleSchedulerAllocator&&) = delete¶

SingleSchedulerAllocator &operator=(SingleSchedulerAllocator&&) = delete¶

virtual void on_job_arrival(core::Task &task, core::Job job) override¶

Handle a job arrival for a task.

On the first arrival the task is placed on the scheduler (and optionally linked to the clock domain). Every arrival then forwards the job to the scheduler.

See also

Allocator::on_job_arrival

Parameters:

task – The task that produced the job.
job – The newly arrived job to dispatch.

FirstFitAllocator¶

class FirstFitAllocator : public schedsim::algo::MultiClusterAllocator ¶

First-Fit Decreasing allocator for multi-cluster task placement.

Iterates over the clusters in construction order and returns the first cluster that can admit the task (i.e. whose Cluster::can_admit() returns true for the task’s budget and period).

This is the classic first-fit bin-packing heuristic. It favours filling earlier clusters first, which tends to leave later clusters idle and available for power management.

WorstFitAllocator¶

class WorstFitAllocator : public schedsim::algo::MultiClusterAllocator ¶

Worst-Fit allocator for multi-cluster task placement.

Among all clusters that can admit the task, selects the one with the highest remaining capacity (as reported by Cluster::remaining_capacity()). Ties are broken by construction order (earlier cluster wins).

Worst-fit spreads load as evenly as possible across clusters, which can improve thermal balance and reduce per-core utilization peaks.

BestFitAllocator¶

class BestFitAllocator : public schedsim::algo::MultiClusterAllocator ¶

Best-Fit allocator for multi-cluster task placement.

Among all clusters that can admit the task, selects the one with the lowest remaining capacity (as reported by Cluster::remaining_capacity()). Ties are broken by construction order (earlier cluster wins).

Best-fit packs tasks tightly, which can consolidate work onto fewer clusters and maximise opportunities for powering down idle clusters.

FFBigFirstAllocator¶

class FFBigFirstAllocator : public schedsim::algo::MultiClusterAllocator ¶

First-fit allocator that processes big (high-performance) cores first.

Iterates over clusters from highest performance to lowest, assigning each task to the first cluster that can accept it. This strategy maximises single-task throughput at the cost of higher energy consumption.

See also

MultiClusterAllocator for the base class and task-binding semantics.

See also

FFLittleFirstAllocator for the energy-oriented counterpart.

See also

FFCapAllocator for a capacity-aware variant.

Public Functions

MultiClusterAllocator(core::Engine &engine, std::vector<Cluster*> clusters)¶

Construct a multi-cluster allocator.

Parameters:

engine – Reference to the simulation engine (for event scheduling).
clusters – Non-owning pointers to the clusters available for task placement. Order matters for tie-breaking in derived allocators.

MultiClusterAllocator(const MultiClusterAllocator&) = delete¶: Non-copyable, non-movable (registered with engine).

MultiClusterAllocator(MultiClusterAllocator&&) = delete¶

FFLittleFirstAllocator¶

class FFLittleFirstAllocator : public schedsim::algo::MultiClusterAllocator ¶

First-fit allocator that processes little (energy-efficient) cores first.

Iterates over clusters from lowest performance to highest, assigning each task to the first cluster that can accept it. This energy-oriented strategy uses small cores whenever possible, falling back to big cores only when capacity is exhausted. Tracks the total number of allocation steps.

See also

MultiClusterAllocator for the base class and task-binding semantics.

See also

FFBigFirstAllocator for the performance-oriented counterpart.

Public Functions

inline std::size_t allocation_count() const noexcept¶

Return the number of allocation steps performed so far.

Returns:: The cumulative count of select_cluster invocations.

MultiClusterAllocator(core::Engine &engine, std::vector<Cluster*> clusters)¶

Construct a multi-cluster allocator.

Parameters:

engine – Reference to the simulation engine (for event scheduling).
clusters – Non-owning pointers to the clusters available for task placement. Order matters for tie-breaking in derived allocators.

MultiClusterAllocator(const MultiClusterAllocator&) = delete¶: Non-copyable, non-movable (registered with engine).

MultiClusterAllocator(MultiClusterAllocator&&) = delete¶

FFCapAllocator¶

class FFCapAllocator : public schedsim::algo::MultiClusterAllocator ¶

First-fit allocator with capacity-aware admission control.

Extends the first-fit strategy with an admission test that checks whether a cluster has enough remaining utilisation bandwidth to accommodate the incoming task. Tasks are rejected (returned as nullptr) when no cluster can satisfy the capacity constraint.

See also

MultiClusterAllocator for the base class and task-binding semantics.

See also

FFBigFirstAllocator for a simpler first-fit without capacity checks.

See also

FFCapAdaptiveLinearAllocator for an adaptive variant with linear thresholds.

See also

FFCapAdaptivePolyAllocator for an adaptive variant with polynomial thresholds.

Public Functions

MultiClusterAllocator(core::Engine &engine, std::vector<Cluster*> clusters)¶

Construct a multi-cluster allocator.

Parameters:

engine – Reference to the simulation engine (for event scheduling).
clusters – Non-owning pointers to the clusters available for task placement. Order matters for tie-breaking in derived allocators.

MultiClusterAllocator(const MultiClusterAllocator&) = delete¶: Non-copyable, non-movable (registered with engine).

MultiClusterAllocator(MultiClusterAllocator&&) = delete¶

FFCapAdaptiveLinearAllocator¶

class FFCapAdaptiveLinearAllocator : public schedsim::algo::MultiClusterAllocator ¶

Capacity-aware first-fit allocator with a linearly adaptive admission threshold.

Builds on FFCapAllocator by dynamically adjusting the admission threshold using a linear function of the observed maximum per-task utilisation and the expected total task-set utilisation. The threshold tightens as the allocator gathers more information about incoming workloads. Task sets with expected total utilisation at or below 3.5 retain the full threshold of 1.0; the fitted linear model is applied only above that boundary.

See also

MultiClusterAllocator for the base class and task-binding semantics.

See also

FFCapAllocator for the non-adaptive capacity-aware variant.

See also

FFCapAdaptivePolyAllocator for a polynomial adaptive variant.

Public Functions

inline void set_expected_total_util(double util) noexcept¶

Set the expected total utilisation of the task set.

This value is used together with the observed maximum per-task utilisation to compute the adaptive admission threshold.

Parameters:: util – Expected aggregate utilisation (sum of task utilisations).

MultiClusterAllocator(core::Engine &engine, std::vector<Cluster*> clusters)¶

Construct a multi-cluster allocator.

Parameters:

engine – Reference to the simulation engine (for event scheduling).
clusters – Non-owning pointers to the clusters available for task placement. Order matters for tie-breaking in derived allocators.

MultiClusterAllocator(const MultiClusterAllocator&) = delete¶: Non-copyable, non-movable (registered with engine).

MultiClusterAllocator(MultiClusterAllocator&&) = delete¶

FFCapAdaptivePolyAllocator¶

class FFCapAdaptivePolyAllocator : public schedsim::algo::MultiClusterAllocator ¶

Capacity-aware first-fit allocator with a polynomially adaptive admission threshold.

Similar to FFCapAdaptiveLinearAllocator, but uses a polynomial function of the observed maximum per-task utilisation and the expected total utilisation to determine the admission threshold. The polynomial model can capture non-linear capacity margins that appear in heterogeneous platforms.

See also

MultiClusterAllocator for the base class and task-binding semantics.

See also

FFCapAllocator for the non-adaptive capacity-aware variant.

See also

FFCapAdaptiveLinearAllocator for the linear adaptive variant.

Public Functions

inline void set_expected_total_util(double util) noexcept¶

Set the expected total utilisation of the task set.

This value is used together with the observed maximum per-task utilisation to compute the polynomial adaptive admission threshold.

Parameters:: util – Expected aggregate utilisation (sum of task utilisations).

MultiClusterAllocator(core::Engine &engine, std::vector<Cluster*> clusters)¶

Construct a multi-cluster allocator.

Parameters:

engine – Reference to the simulation engine (for event scheduling).
clusters – Non-owning pointers to the clusters available for task placement. Order matters for tie-breaking in derived allocators.

MultiClusterAllocator(const MultiClusterAllocator&) = delete¶: Non-copyable, non-movable (registered with engine).

MultiClusterAllocator(MultiClusterAllocator&&) = delete¶

FFLbAllocator¶

class FFLbAllocator : public schedsim::algo::MultiClusterAllocator ¶

First-fit allocator with load-balancing across clusters.

Instead of always scanning clusters in a fixed order, this allocator selects the cluster with the lowest current utilisation that can still accommodate the incoming task. This spreads the load more evenly across clusters than a pure first-fit strategy, reducing worst-case per-cluster congestion.

See also

MultiClusterAllocator for the base class and task-binding semantics.

See also

FFBigFirstAllocator for fixed big-first ordering.

See also

FFLittleFirstAllocator for fixed little-first ordering.

See also

FFCapAllocator for capacity-aware admission without load balancing.

Public Functions

MultiClusterAllocator(core::Engine &engine, std::vector<Cluster*> clusters)¶

Construct a multi-cluster allocator.

Parameters:

engine – Reference to the simulation engine (for event scheduling).
clusters – Non-owning pointers to the clusters available for task placement. Order matters for tie-breaking in derived allocators.

MultiClusterAllocator(const MultiClusterAllocator&) = delete¶: Non-copyable, non-movable (registered with engine).

MultiClusterAllocator(MultiClusterAllocator&&) = delete¶

CountingAllocator¶

class CountingAllocator : public schedsim::algo::MultiClusterAllocator ¶

Allocator that counts the number of allocation attempts.

Wraps a trivial allocation strategy while maintaining a running count of how many times select_cluster has been invoked. Useful for instrumentation, testing, and comparing the decision frequency of different allocation policies.

See also

MultiClusterAllocator for the base class and task-binding semantics.

Public Functions

inline std::size_t allocation_count() const noexcept¶

Return the number of allocation attempts performed so far.

Returns:: The cumulative count of select_cluster invocations.

MultiClusterAllocator(core::Engine &engine, std::vector<Cluster*> clusters)¶

Construct a multi-cluster allocator.

Parameters:

engine – Reference to the simulation engine (for event scheduling).
clusters – Non-owning pointers to the clusters available for task placement. Order matters for tie-breaking in derived allocators.

MultiClusterAllocator(const MultiClusterAllocator&) = delete¶: Non-copyable, non-movable (registered with engine).

MultiClusterAllocator(MultiClusterAllocator&&) = delete¶

MCTSAllocator¶

class MCTSAllocator : public schedsim::algo::MultiClusterAllocator ¶

Monte Carlo Tree Search (MCTS) allocator.

Replays a pre-computed allocation pattern produced by an offline MCTS solver. Each entry in the pattern vector is a cluster index that determines where the corresponding task (in arrival order) is placed. When the pattern is exhausted, the allocator falls back to a pseudo-random selection using a splitmix64-style RNG.

See also

MultiClusterAllocator for the base class and task-binding semantics.

See also

FFBigFirstAllocator for a simpler heuristic alternative.

Public Functions

MCTSAllocator(core::Engine &engine, std::vector<Cluster*> clusters, std::vector<unsigned> pattern)¶

Construct an MCTS allocator with a pre-computed cluster pattern.

Parameters:

engine – Reference to the simulation engine.
clusters – Vector of pointers to the available clusters.
pattern – Sequence of cluster indices (one per expected task arrival).

inline std::size_t allocation_count() const noexcept¶

Return the number of allocation steps performed so far.

Returns:: The cumulative count of select_cluster invocations.

Reclamation Policies¶

ReclamationPolicy (Abstract Base)¶

class ReclamationPolicy¶

Abstract interface for bandwidth reclamation policies.

Reclamation policies allow unused CBS bandwidth to be redistributed among active servers. Concrete implementations (GrubPolicy, CashPolicy) define how surplus budget is detected, tracked, and reused.

The policy hooks into the CBS lifecycle at three points:

Early job completion (budget left over)
Budget exhaustion (server needs more time)
Virtual time computation (scaling the virtual clock)

See also

GrubPolicy

See also

CashPolicy

See also

CbsServer

Subclassed by schedsim::algo::CashPolicy, schedsim::algo::GrubPolicy

Public Types

enum class ServerStateChange¶

Server state transitions observed by the reclamation policy.

Notified via on_server_state_change() so the policy can track which servers are active and adjust bandwidth accounting accordingly.

Values:

enumerator Activated¶: Inactive -> Ready (first job arrival).

enumerator Dispatched¶: Ready -> Running (server begins executing).

enumerator Preempted¶: Running -> Ready (higher-priority preemption).

enumerator Completed¶: Running -> Inactive (job finished, no pending jobs).

enumerator NonContending¶: Running -> NonContending (GRUB early completion).

enumerator DeadlineReached¶: NonContending -> Inactive (GRUB deadline expiry).

enumerator Detached¶: Server removed from scheduler (no future arrivals).

Public Functions

virtual ~ReclamationPolicy() = default¶

virtual bool on_early_completion(CbsServer &server, core::Duration remaining_budget) = 0¶

Handle early job completion (job finishes before budget exhaustion).

Called when a job completes with remaining budget. The policy decides whether the server should enter a NonContending state (GRUB) or follow standard CBS behavior (Inactive/Ready).

See also

GrubPolicy::on_early_completion

See also

CashPolicy::on_early_completion

Parameters:

server – The CBS server whose job completed early.
remaining_budget – The unused budget at the time of completion.

Returns:

true if the server should enter NonContending state (GRUB behaviour); false for standard CBS behaviour (server goes Inactive/Ready).

virtual core::Duration on_budget_exhausted(CbsServer &server) = 0¶

Handle budget exhaustion for a running server.

Called when a server’s budget reaches zero while its job is still executing. The policy may grant extra budget (e.g. CASH borrowing from the spare queue) or return zero for standard CBS postponement.

See also

GrubPolicy::on_budget_exhausted

See also

CashPolicy::on_budget_exhausted

Parameters:: server – The CBS server whose budget is exhausted.
Returns:: Extra budget granted to the server; zero means standard CBS deadline postponement applies.

virtual core::TimePoint compute_virtual_time(const CbsServer &server, core::TimePoint current_vt, core::Duration exec_time) const¶

Compute the next virtual time after consuming execution time.

Default implementation uses the standard CBS formula: vt += exec_time / U_server. GRUB overrides this with vt += exec_time / U_active (clamped to avoid division by zero).

See also

GrubPolicy::compute_virtual_time

Parameters:

server – The CBS server whose virtual time is being updated.
current_vt – The server’s current virtual time.
exec_time – The wall-clock execution time consumed since the last virtual time update.

Returns:

The updated virtual time.

virtual void on_server_state_change(CbsServer &server, ServerStateChange change) = 0¶

Notify the policy of a server state transition.

Called whenever a CBS server changes state so the policy can update its internal bandwidth tracking (e.g. active utilization sums).

Parameters:

server – The CBS server whose state changed.
change – The type of state transition that occurred.

virtual core::Duration compute_server_budget(const CbsServer &server) const¶

Compute the dynamic budget for a running server.

Default implementation returns the server’s static remaining budget. M-GRUB overrides this to scale the budget by the bandwidth factor.

See also

GrubPolicy::compute_server_budget

Parameters:: server – The CBS server whose budget is being queried.
Returns:: The effective budget duration for timer scheduling.

inline virtual bool needs_global_budget_recalculation() const¶

Whether the scheduler must recalculate budget timers for all running servers after each reschedule.

Default is false (standard CBS). M-GRUB returns true because budget consumption rates change when the active utilization changes.

Returns:: true if global budget recalculation is required.

inline virtual double compute_bandwidth() const¶

Current bandwidth factor used for virtual time rate computation.

Default is 1.0 (no reclamation effect). GRUB overrides this with the M-GRUB formula that accounts for multiprocessor bandwidth sharing.

See also

GrubPolicy::compute_bandwidth

Returns:: The bandwidth scaling factor in [kMinUtilization, 1.0].

virtual double active_utilization() const = 0¶

Get the current active utilization.

Active utilization is the sum of U_i for all servers currently in the Running or Ready state. Used by DVFS policies to set processor frequencies proportional to actual workload.

Returns:: The sum of utilizations of active (Ready/Running) servers.

inline virtual double scheduler_utilization() const¶

Get the “in-scheduler” utilization.

Sum of U_i for servers that have been activated at least once and have not yet been detached. Used by the PA (Piloted Approach) DVFS policy. Default implementation delegates to active_utilization().

See also

GrubPolicy::scheduler_utilization

Returns:: The sum of utilizations of in-scheduler servers.

inline virtual double max_scheduler_utilization() const¶

Get the maximum utilization among in-scheduler servers.

Returns the largest U_i among servers that have been activated at least once and not yet detached. Used by PA DVFS for the u_max term. Default returns 0.0; callers should fall back to max_server_utilization().

See also

GrubPolicy::max_scheduler_utilization

Returns:: The maximum single-server utilization, or 0.0 if untracked.

GrubPolicy¶

class GrubPolicy : public schedsim::algo::ReclamationPolicy ¶

M-GRUB (Multiprocessor Greedy Reclamation of Unused Bandwidth) policy.

Implements the GRUB bandwidth reclamation algorithm extended for multiprocessor systems (M-GRUB). The policy maintains two utilization aggregates:

Active utilization (Ready + Running servers) — used by DVFS policies to scale processor frequency proportionally to real demand.
In-scheduler utilization (all non-detached servers) — used in the M-GRUB bandwidth formula that governs virtual time progression.

When a job completes early, the server enters a NonContending state and a deadline timer is armed. The server’s bandwidth is released from the active set immediately, allowing other servers to consume time at a faster virtual rate. When the deadline timer fires, the server returns to Inactive and its bandwidth is also released from the in-scheduler set.

See also

See also

See also

See also

Public Functions

explicit GrubPolicy(EdfScheduler &scheduler)¶

Construct a GrubPolicy attached to the given EDF scheduler.

Parameters:: scheduler – The EDF scheduler that owns the CBS servers managed by this policy.

~GrubPolicy() override¶: Destructor; cancels any outstanding deadline timers.

virtual bool on_early_completion(CbsServer &server, core::Duration remaining_budget) override¶

Handle early job completion by entering NonContending state.

The server transitions to NonContending and a deadline timer is armed so that the server’s bandwidth is reclaimed when its current deadline expires.

See also

ReclamationPolicy::on_early_completion

Parameters:

server – The CBS server whose job completed early.
remaining_budget – The unused budget at the time of completion.

Returns:

Always true (GRUB always enters NonContending on early completion).

virtual core::Duration on_budget_exhausted(CbsServer &server) override¶

Handle budget exhaustion with standard CBS postponement.

GRUB does not grant extra budget; it relies on virtual time scaling instead. Returns zero so that the scheduler performs a normal CBS deadline postponement.

See also

ReclamationPolicy::on_budget_exhausted

Parameters:: server – The CBS server whose budget is exhausted.
Returns:: Always zero (no extra budget granted).

virtual core::TimePoint compute_virtual_time(const CbsServer &server, core::TimePoint current_vt, core::Duration exec_time) const override¶

Compute virtual time using the GRUB reclamation formula.

Advances virtual time by exec_time scaled by the inverse of the M-GRUB bandwidth factor, so that servers consume their virtual budget faster when overall active utilization is low.

See also

ReclamationPolicy::compute_virtual_time

See also

compute_bandwidth

Parameters:

server – The CBS server whose virtual time is being updated.
current_vt – The server’s current virtual time.
exec_time – Wall-clock execution time consumed since last update.

Returns:

The updated virtual time.

virtual void on_server_state_change(CbsServer &server, ServerStateChange change) override¶

Update utilization tracking on server state transitions.

Adjusts both active and in-scheduler utilization sums, and manages deadline timers for NonContending servers.

Parameters:

server – The CBS server whose state changed.
change – The type of state transition that occurred.

inline virtual double active_utilization() const override¶

Get the current active utilization (Ready + Running servers).

Returns:: Sum of U_i for active servers.

inline virtual double scheduler_utilization() const override¶

Get the in-scheduler utilization (all non-detached servers).

Returns:: Sum of U_i for servers activated at least once and not detached.

inline virtual double max_scheduler_utilization() const override¶

Get the maximum utilization ever seen among in-scheduler servers.

This value is monotonically non-decreasing: it is never reduced when a server is detached. Used by PA DVFS for the u_max term.

Returns:: The historical maximum single-server utilization.

virtual core::Duration compute_server_budget(const CbsServer &server) const override¶

Compute the M-GRUB dynamic budget for a running server.

Scales the server’s remaining budget by the inverse of the bandwidth factor, yielding the wall-clock time until budget exhaustion given the current active utilization.

See also

compute_bandwidth

Parameters:: server – The CBS server whose budget is being queried.
Returns:: The scaled budget duration for timer scheduling.

inline virtual bool needs_global_budget_recalculation() const override¶

M-GRUB requires global budget recalculation after each reschedule.

Returns:: Always true.

virtual double compute_bandwidth() const override¶

Compute the M-GRUB bandwidth factor.

The bandwidth factor is max(kMinUtilization, min(1.0, m - (m-1) * U_max / U_sched)) where m is the number of processors and U_max / U_sched are derived from the in-scheduler set.

See also

ReclamationPolicy::compute_bandwidth

Returns:: The bandwidth scaling factor in [kMinUtilization, 1.0].

Public Static Attributes

static double kMinUtilization = 0.01¶: Minimum utilization floor to prevent division by zero in the GRUB virtual time formula.

CashPolicy¶

class CashPolicy : public schedsim::algo::ReclamationPolicy ¶

CASH (Capacity Sharing) bandwidth reclamation policy.

Implements the CASH algorithm, an alternative to GRUB for redistributing unused CBS bandwidth. When a job completes early, its remaining budget is deposited into a global spare queue rather than entering a NonContending state. Servers whose budget is exhausted can then borrow from the spare queue to continue executing without a deadline postponement.

CASH uses the standard CBS virtual time formula (inherited from ReclamationPolicy) and does not modify virtual time scaling.

See also

See also

See also

See also

Public Functions

explicit CashPolicy(EdfScheduler &scheduler)¶

Construct a CashPolicy attached to the given EDF scheduler.

Parameters:: scheduler – The EDF scheduler that owns the CBS servers managed by this policy.

virtual bool on_early_completion(CbsServer &server, core::Duration remaining_budget) override¶

Handle early job completion by depositing unused budget.

Adds the remaining budget to the global spare queue so that other servers may borrow it later.

See also

ReclamationPolicy::on_early_completion

Parameters:

server – The CBS server whose job completed early.
remaining_budget – The unused budget to deposit into the spare queue.

Returns:

Always false (CASH does not use the NonContending state).

virtual core::Duration on_budget_exhausted(CbsServer &server) override¶

Handle budget exhaustion by borrowing from the spare queue.

If the spare queue has accumulated budget from early completions, the server receives some or all of it as extra execution time.

See also

ReclamationPolicy::on_budget_exhausted

Parameters:: server – The CBS server whose budget is exhausted.
Returns:: The amount of extra budget granted from the spare queue; zero if the spare queue is empty (standard CBS postponement).

virtual void on_server_state_change(CbsServer &server, ServerStateChange change) override¶

Update active utilization tracking on server state transitions.

CASH tracks active utilization (Ready + Running) for DVFS integration but does not maintain an in-scheduler set (no NonContending state).

Parameters:

server – The CBS server whose state changed.
change – The type of state transition that occurred.

inline virtual double active_utilization() const override¶

Get the current active utilization (Ready + Running servers).

Returns:: Sum of U_i for active servers.

inline core::Duration spare_budget() const noexcept¶

Get the total spare budget currently available for borrowing.

Returns:: The accumulated unused budget in the spare queue.

DVFS Policies¶

DvfsPolicy (Abstract Base)¶

class DvfsPolicy¶

Abstract interface for DVFS (Dynamic Voltage and Frequency Scaling) policies.

DVFS policies adjust processor clock-domain frequency based on workload characteristics such as active utilization and per-server maximum utilization. Concrete implementations (PowerAwareDvfsPolicy, FfaPolicy, CsfPolicy) override the three event hooks to compute and apply a target frequency.

Subclassed by schedsim::algo::CsfPolicy, schedsim::algo::FfaPolicy, schedsim::algo::PowerAwareDvfsPolicy

Public Types

using FrequencyChangedCallback = std::function<void(core::ClockDomain&)>¶: Callback type invoked after a frequency change is applied.

Public Functions

virtual ~DvfsPolicy() = default¶

virtual void on_utilization_changed(EdfScheduler &scheduler, core::ClockDomain &domain) = 0¶

Called when active utilization changes.

Triggered after job arrival, completion, server attach/detach, or any event that modifies the aggregate utilization seen by the scheduler.

Parameters:

scheduler – The EDF scheduler owning the affected processors.
domain – The clock domain whose utilization changed.

virtual void on_processor_idle(EdfScheduler &scheduler, core::Processor &proc) = 0¶

Called when a processor becomes idle (no runnable job).

Parameters:

scheduler – The EDF scheduler owning the processor.
proc – The processor that just became idle.

virtual void on_processor_active(EdfScheduler &scheduler, core::Processor &proc) = 0¶

Called when a processor becomes active (starts executing a job).

Parameters:

scheduler – The EDF scheduler owning the processor.
proc – The processor that just became active.

inline virtual core::Duration cooldown_period() const¶

Return the cooldown period between successive frequency changes.

A non-zero value prevents rapid oscillation by enforcing a minimum interval between consecutive frequency adjustments on the same domain.

Returns:: The cooldown duration. Default is zero (no cooldown).

inline void set_frequency_changed_callback(FrequencyChangedCallback callback)¶

The EdfScheduler sets this callback so it can update job completion timers whenever the DVFS policy changes the clock domain frequency.

Parameters:: callback – Function to invoke after each frequency change.

CooldownTimer¶

class CooldownTimer¶

Per-domain cooldown timer to throttle frequency changes.

Tracks the earliest time at which the next frequency change is permitted for a given clock domain, preventing rapid DVFS oscillation.

See also

DvfsPolicy, PowerAwareDvfsPolicy

Public Functions

CooldownTimer(core::Engine &engine, core::Duration cooldown)¶

Construct a cooldown timer.

Parameters:

engine – The simulation engine (used to query the current time).
cooldown – Duration of the cooldown period.

bool can_change() const¶

Check whether a frequency change is currently permitted.

Returns:: true if the cooldown has expired (or was never started).

void start_cooldown()¶: Start (or restart) the cooldown period from the current time.

bool in_cooldown() const¶

Check whether the timer is still within the cooldown window.

Returns:: true if a cooldown is active and has not yet expired.

PowerAwareDvfsPolicy¶

class PowerAwareDvfsPolicy : public schedsim::algo::DvfsPolicy ¶

Power-aware DVFS policy using the PA frequency formula.

Computes the minimum feasible frequency as: f_min = f_max * ((m-1) * U_max + U_total) / m

where m is the number of processors in the domain, U_max is the maximum single-server utilization, and U_total is the aggregate active utilization.

Public Functions

explicit PowerAwareDvfsPolicy(core::Engine &engine, core::Duration cooldown = core::duration_from_seconds(0.0))¶

Construct a power-aware DVFS policy.

Parameters:

engine – The simulation engine (for time queries and tracing).
cooldown – Minimum interval between consecutive frequency changes.

virtual void on_utilization_changed(EdfScheduler &scheduler, core::ClockDomain &domain) override¶

Recompute and apply the target frequency after a utilization change.

Parameters:

scheduler – The EDF scheduler providing utilization data.
domain – The clock domain to adjust.

virtual void on_processor_idle(EdfScheduler &scheduler, core::Processor &proc) override¶

No-op for the PA policy (frequency depends only on utilization).

Parameters:

scheduler – The EDF scheduler owning the processor.
proc – The processor that became idle.

virtual void on_processor_active(EdfScheduler &scheduler, core::Processor &proc) override¶

No-op for the PA policy (frequency depends only on utilization).

Parameters:

scheduler – The EDF scheduler owning the processor.
proc – The processor that became active.

inline virtual core::Duration cooldown_period() const override¶

Return the configured cooldown period.

Returns:: The cooldown duration passed at construction.

FfaPolicy¶

class FfaPolicy : public schedsim::algo::DvfsPolicy ¶

FFA (Feedback-based Frequency Adaptation) DVFS+DPM policy.

Computes a minimum frequency using the PA formula first, then checks whether the resulting frequency falls below the domain’s efficient frequency (freq_eff). When it does, the policy reduces the number of active processors instead of lowering frequency further, putting excess idle cores to sleep.

Frequency-first: lower frequency as much as possible, then reduce cores.

Subclassed by schedsim::algo::FfaTimerPolicy

Public Functions

FfaPolicy(core::Engine &engine, core::Duration dvfs_cooldown = core::duration_from_seconds(0.0), int sleep_cstate = 1)¶

Construct an FFA policy.

Parameters:

engine – The simulation engine (for time queries and tracing).
dvfs_cooldown – Minimum interval between consecutive frequency changes.
sleep_cstate – C-state level to use when putting idle processors to sleep.

virtual void on_utilization_changed(EdfScheduler &scheduler, core::ClockDomain &domain) override¶

Recompute target frequency and active core count after a utilization change.

Parameters:

scheduler – The EDF scheduler providing utilization data.
domain – The clock domain to adjust.

virtual void on_processor_idle(EdfScheduler &scheduler, core::Processor &proc) override¶

Handle a processor becoming idle (potential DPM sleep candidate).

Parameters:

scheduler – The EDF scheduler owning the processor.
proc – The processor that became idle.

virtual void on_processor_active(EdfScheduler &scheduler, core::Processor &proc) override¶

Handle a processor becoming active (woken from sleep or assigned work).

Parameters:

scheduler – The EDF scheduler owning the processor.
proc – The processor that became active.

virtual core::Duration cooldown_period() const override¶

Return the configured cooldown period.

Returns:: The DVFS cooldown duration passed at construction.

CsfPolicy¶

class CsfPolicy : public schedsim::algo::DvfsPolicy ¶

CSF (Core Scaling First) DVFS+DPM policy.

Computes the minimum number of active processors first (m_min), then sets the frequency to satisfy schedulability on those cores. This policy prefers reducing the number of active cores over reducing frequency, which is the opposite trade-off from FfaPolicy.

Core-first: reduce active cores as much as possible, then lower frequency.

Subclassed by schedsim::algo::CsfTimerPolicy

Public Functions

CsfPolicy(core::Engine &engine, core::Duration dvfs_cooldown = core::duration_from_seconds(0.0), int sleep_cstate = 1)¶

Construct a CSF policy.

Parameters:

engine – The simulation engine (for time queries and tracing).
dvfs_cooldown – Minimum interval between consecutive frequency changes.
sleep_cstate – C-state level to use when putting idle processors to sleep.

virtual void on_utilization_changed(EdfScheduler &scheduler, core::ClockDomain &domain) override¶

Recompute target frequency and active core count after a utilization change.

Parameters:

scheduler – The EDF scheduler providing utilization data.
domain – The clock domain to adjust.

virtual void on_processor_idle(EdfScheduler &scheduler, core::Processor &proc) override¶

Handle a processor becoming idle (potential DPM sleep candidate).

Parameters:

scheduler – The EDF scheduler owning the processor.
proc – The processor that became idle.

virtual void on_processor_active(EdfScheduler &scheduler, core::Processor &proc) override¶

Handle a processor becoming active (woken from sleep or assigned work).

Parameters:

scheduler – The EDF scheduler owning the processor.
proc – The processor that became active.

virtual core::Duration cooldown_period() const override¶

Return the configured cooldown period.

Returns:: The DVFS cooldown duration passed at construction.

FfaTimerPolicy¶

class FfaTimerPolicy : public schedsim::algo::FfaPolicy ¶

Timer-deferred FFA (Feedback-based Frequency Adaptation) policy.

Extends FfaPolicy by deferring the application of DVFS+DPM changes by the configured cooldown duration using engine timers. When a utilization change occurs during an active cooldown, the pending target is updated in place so that only the most recent target is applied when the timer fires.

If the cooldown is zero, behaviour degrades to the parent FfaPolicy (immediate mode) with no timer overhead.

Public Functions

~FfaTimerPolicy() override¶: Destructor cancels any pending timers.

virtual void on_utilization_changed(EdfScheduler &scheduler, core::ClockDomain &domain) override¶

Recompute and defer the target frequency/core-count change.

If a timer is already pending for this domain, updates the pending target without rescheduling. Otherwise, starts a new timer that will apply the target after the cooldown expires.

Parameters:

scheduler – The EDF scheduler providing utilization data.
domain – The clock domain to adjust.

CsfTimerPolicy¶

class CsfTimerPolicy : public schedsim::algo::CsfPolicy ¶

Timer-deferred CSF (Core Scaling First) policy.

Extends CsfPolicy by deferring the application of DVFS+DPM changes by the configured cooldown duration using engine timers. When a utilization change occurs during an active cooldown, the pending target is updated in place so that only the most recent target is applied when the timer fires.

If the cooldown is zero, behaviour degrades to the parent CsfPolicy (immediate mode) with no timer overhead.

Public Functions

~CsfTimerPolicy() override¶: Destructor cancels any pending timers.

virtual void on_utilization_changed(EdfScheduler &scheduler, core::ClockDomain &domain) override¶

Recompute and defer the target frequency/core-count change.

If a timer is already pending for this domain, updates the pending target without rescheduling. Otherwise, starts a new timer that will apply the target after the cooldown expires.

Parameters:

scheduler – The EDF scheduler providing utilization data.
domain – The clock domain to adjust.

DPM Policy¶

class DpmPolicy¶

Abstract interface for DPM (Dynamic Power Management) policies.

DPM policies manage processor sleep states (C-states) to reduce static power consumption when cores are idle. The EdfScheduler invokes the two hooks below at the appropriate scheduling points.

Subclassed by schedsim::algo::BasicDpmPolicy

Public Functions

virtual ~DpmPolicy() = default¶

virtual void on_processor_idle(EdfScheduler &scheduler, core::Processor &proc) = 0¶

Called when a processor becomes idle.

The policy should decide whether to put the processor into a low-power sleep state (C-state) or leave it active for faster wake-up.

Parameters:

scheduler – The EDF scheduler owning the processor.
proc – The processor that just became idle.

virtual void on_processor_needed(EdfScheduler &scheduler) = 0¶

Called when a processor is needed (jobs are waiting to be scheduled).

The policy should wake up one or more sleeping processors so they can execute pending jobs.

Parameters:: scheduler – The EDF scheduler that needs a processor.

class BasicDpmPolicy : public schedsim::algo::DpmPolicy ¶

Basic DPM policy that puts idle processors to sleep immediately.

When a processor becomes idle, it is transitioned to the configured C-state. When the scheduler signals that a processor is needed, one of the sleeping processors is woken up.

See also

DpmPolicy, DvfsPolicy, EdfScheduler

Public Functions

explicit BasicDpmPolicy(int target_cstate = 1, core::Duration idle_threshold = core::duration_from_seconds(0.0))¶

Construct a basic DPM policy.

Parameters:

target_cstate – The C-state level to enter when idle (1 = C1, 2 = C2, etc.).
idle_threshold – Minimum idle duration before entering sleep. Zero means immediate sleep on idle.

virtual void on_processor_idle(EdfScheduler &scheduler, core::Processor &proc) override¶

Put the processor to sleep if appropriate.

Parameters:

scheduler – The EDF scheduler owning the processor.
proc – The processor that just became idle.

virtual void on_processor_needed(EdfScheduler &scheduler) override¶

Wake a sleeping processor to service pending jobs.

Parameters:: scheduler – The EDF scheduler that needs a processor.

inline int target_cstate() const noexcept¶

Return the target C-state level.

Returns:: The C-state index (e.g., 1 for C1).

inline core::Duration idle_threshold() const noexcept¶

Return the idle threshold duration.

Returns:: The minimum idle duration before the processor enters sleep.

inline std::size_t sleeping_processor_count() const noexcept¶

Return the number of processors currently sleeping.

Returns:: Count of processors managed by this policy that are in a sleep state.

Utilities¶

DVFS/DPM Utilities¶

namespace dvfs_dpm¶

Namespace for DVFS/DPM helper functions and types.

Functions

double compute_utilization_scale(const core::Platform &platform, const core::ClockDomain &domain)¶

Compute the utilization scale factor for a heterogeneous platform domain.

Returns ref_freq_max / (domain_freq_max * domain_perf) so that raw task utilization (WCET / Period) is converted to the fraction of a domain core’s capacity actually consumed. On a homogeneous platform this is 1.0.

Parameters:

platform – The simulation platform (provides the reference frequency).
domain – The clock domain to compute the scale for.

Returns:

The multiplicative scale factor.

double compute_freq_min(double freq_max, double total_util, double max_util, double nb_procs)¶

Compute the minimum feasible frequency using the PA formula.

f_min = f_max * (U_total + (m - 1) * U_max) / m

This is the lowest frequency at which an m-processor global-EDF system remains schedulable given aggregate utilization U_total and maximum single-server utilization U_max.

Parameters:

freq_max – The maximum frequency of the clock domain (Hz).
total_util – Aggregate active utilization (dimensionless, typically in [0, m]).
max_util – Maximum single-server utilization (dimensionless, in [0, 1]).
nb_procs – Number of processors in the domain.

Returns:

The minimum feasible frequency (Hz, not yet clamped to hardware steps).

std::size_t clamp_procs(double value, std::size_t max_procs)¶

Clamp a floating-point processor count to [1, max_procs].

Parameters:

value – The raw (possibly fractional) processor count.
max_procs – The upper bound (total processors in the domain).

Returns:

The clamped integer processor count, at least 1.

std::size_t count_active_processors(std::span<core::Processor*const> procs)¶

Count processors in Idle or Running state.

Excludes processors in Sleep, Changing, or ContextSwitching states.

Parameters:: procs – Span of processor pointers to inspect.
Returns:: The number of currently active processors.

void sleep_excess_processors(std::span<core::Processor*const> procs, std::size_t target_active, int cstate, core::Engine *engine = nullptr)¶

Put excess idle processors to sleep.

Only transitions processors that are currently in the Idle state (never Running). Iterates from the end of the span to avoid disturbing the lowest-indexed active processors.

See also

apply_platform_target, DpmPolicy

Parameters:

procs – Span of processor pointers in the domain.
target_active – Desired number of active processors after sleeping.
cstate – C-state level to enter (e.g., 1 for C1).
engine – Optional engine pointer; if non-null, emits proc_sleep trace events.

void apply_platform_target(EdfScheduler &scheduler, core::ClockDomain &domain, const PlatformTarget &target, int sleep_cstate, DvfsPolicy::FrequencyChangedCallback &on_freq_changed)¶

Apply a computed platform target: DPM first (sleep excess), then DVFS (set frequency).

Coordinates the sleep_excess_processors() and ClockDomain::set_frequency() calls, and invokes the frequency-changed callback so the scheduler can update job completion timers.

See also

PlatformTarget, FfaPolicy, CsfPolicy

Parameters:

scheduler – The EDF scheduler owning the affected processors.
domain – The clock domain to adjust.
target – The desired frequency and active processor count.
sleep_cstate – C-state for sleeping excess processors.
on_freq_changed – Callback to invoke after the frequency change.

struct PlatformTarget¶

Combined DVFS+DPM target: a frequency and an active processor count.

Returned by policy computation functions and consumed by apply_platform_target().

See also

apply_platform_target, FfaPolicy::compute_target, CsfPolicy::compute_target

Public Members

core::Frequency frequency¶: Target clock frequency for the domain.

std::size_t active_processors¶: Desired number of active (non-sleeping) processors.

Task Utilities¶

inline double schedsim::algo::task_utilization(const core::Task &t)¶

Compute the utilization of a task as WCET / Period.

Returns the ratio of the task’s worst-case execution time to its period, both expressed as core::Duration values. The result is a dimensionless value in [0, 1] for well-formed task sets.

See also

core::Task, EdfScheduler::utilization

Parameters:: t – The task whose utilization is computed.
Returns:: The utilization ratio (WCET / Period) as a double.

Errors¶

enum class schedsim::algo::AdmissionTest¶

Admission test variant for CBS server admission control.

Selects the schedulability condition used when admitting a new server to a global EDF scheduler.

See also

Scheduler::can_admit

Values:

enumerator CapacityBound¶: U <= m (necessary condition, default).

enumerator GFB¶: U <= m - (m-1)*u_max (sufficient, Goossens-Funk-Baruah 2003).

enum class schedsim::algo::DeadlineMissPolicy¶

Policy for handling scheduling deadline misses.

Controls simulator behaviour when a job misses its absolute deadline.

See also

EdfScheduler, DeadlineMissPolicy

Values:

enumerator Continue¶: Log the miss and continue simulation (default).

enumerator AbortJob¶: Abort the offending job but keep the task active.

enumerator AbortTask¶: Remove the entire task from the scheduler.

enumerator StopSimulation¶: Halt the simulation immediately.

class AdmissionError : public std::runtime_error¶

Exception thrown when a CBS server cannot be admitted.

Raised by Scheduler::on_job_arrival or Allocator::on_job_arrival when the requested server utilization would exceed the available scheduling capacity.

See also

Scheduler::can_admit, AdmissionTest

Public Functions

inline AdmissionError(double requested_utilization, double available_capacity)¶

Construct an AdmissionError with utilization details.

Parameters:

requested_utilization – The utilization that was requested.
available_capacity – The remaining capacity at the time of the request.

inline double requested_utilization() const noexcept¶

Get the utilization that was requested.

Returns:: Requested utilization as a dimensionless ratio.

inline double available_capacity() const noexcept¶

Get the capacity that was available at the time of the request.

Returns:: Available capacity as a dimensionless value.