 |
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
|
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
One station's mutable state. More...
#include <line/solvers/ldes/ldes_engine.h>
Classes | |
| struct | BalkRule |
| Balking: the (min, max, probability) triples an arrival consults. More... | |
Public Attributes | |
| Role | role = Role::Queue |
| lang::SchedStrategy | sched = lang::SchedStrategy::FCFS |
| bool | ps = false |
| bool | preemptive = false |
| bool | resume = false |
| PR (continue the residual) as against PI (redraw). | |
| std::size_t | nservers = 1 |
| std::size_t | lps_limit = 0 |
| LPS admission cap; 0 = none. | |
| double | cap = std::numeric_limits<double>::infinity() |
| std::vector< double > | classcap |
| std::vector< lang::DropStrategy > | droprule |
| sn.droprule, per class, declared on the DESTINATION station. | |
| std::vector< double > | blocked_at |
| Jobs held OUTSIDE this station's buffer but counted in its queue length: a BAS or BBS job whose destination is full occupies the upstream server and is charged to the destination, which is where it is queueing for. | |
| std::vector< double > | weight |
| schedparam, the DPS/GPS weights | |
| std::vector< double > | class_mean |
| mean service per class, for SEPT/LEPT | |
| std::vector< double > | lld |
| sn.lldscaling: the RATE multiplier when n jobs are present, indexed n-1. | |
| lang::CdScaling< double > | cd |
| sn.cdscaling: beta_r(n), a per-class RATE at the station's population. | |
| bool | has_cd = false |
| bool | pas = false |
| A PASS-AND-SWAP station serves an ORDERED LIST whose total rate is a function of the whole class sequence (Dorsman and Gardner 2024). | |
| std::function< double(const std::vector< std::size_t > &)> | pas_rate |
| std::vector< std::vector< bool > > | pas_swap |
| std::vector< Job > | pas_list |
| std::uint64_t | pas_tag = 0 |
| bool | polling = false |
| A POLLING SERVER visits the per-class buffers in a fixed cyclic order, paying a SWITCHOVER on each leg. | |
| std::size_t | poll_at = 0 |
| the buffer the server is serving or heading to | |
| bool | poll_switching = false |
| bool | poll_parked = false |
| std::size_t | poll_budget = 0 |
| remaining visit budget; 0 = exhausted | |
| lang::PollingType | poll_type = lang::PollingType::EXHAUSTIVE |
| std::size_t | poll_k = 1 |
| std::vector< Sampler > | switchover |
| std::vector< bool > | has_switchover |
| bool | has_setup = false |
| SETUP AND DELAY-OFF: a station that powers down when it falls idle. | |
| Sampler | setup_time |
| Sampler | delayoff_time |
| bool | setup_on = false |
| the server has completed its setup | |
| bool | setup_running = false |
| a setup is in progress | |
| double | delayoff_at = std::numeric_limits<double>::infinity() |
| when it shuts down | |
| std::vector< Sampler > | retrial |
| RETRIAL: a job refused admission joins an ORBIT and tries again later, instead of being dropped or queueing. | |
| std::vector< bool > | has_retrial |
| std::vector< int > | max_attempts |
| std::vector< double > | orbit_size |
| live, per class | |
| std::vector< double > | tot_orbit |
| time integral of the orbit size | |
| double | orbit_last = 0.0 |
| std::vector< double > | retried |
| std::vector< double > | retrial_lost |
| std::vector< Sampler > | patience |
| Reneging: the abandonment timer of a WAITING job, per class. | |
| std::vector< bool > | has_patience |
| std::vector< std::vector< BalkRule > > | balk |
| std::vector< Sampler > | svc |
| std::vector< bool > | off |
| bool | has_pools = false |
| HETEROGENEOUS SERVER POOLS, empty on a station whose servers are alike. | |
| std::vector< std::size_t > | server_type |
| per slot, its pool | |
| std::vector< std::size_t > | type_first |
| per pool, its first slot | |
| std::vector< std::size_t > | type_count |
| per pool, its server count | |
| std::vector< std::vector< bool > > | type_compat |
| [pool][class] | |
| std::vector< std::vector< Sampler > > | type_svc |
| [pool][class] | |
| std::vector< std::vector< bool > > | type_has_svc |
| [pool][class], a law of its own | |
| std::vector< std::vector< double > > | type_rate |
| [pool][class], 1/mean, for FSF | |
| lang::HeteroSchedPolicy | hetero_policy = lang::HeteroSchedPolicy::ORDER |
| std::vector< std::size_t > | type_order |
| ALIS/FAIRNESS rotate this order; a used pool goes to the back. | |
| std::vector< std::size_t > | alfs_order |
| ALFS walks the pools least-flexible first: fewest compatible classes. | |
| std::vector< Job > | buffer |
| The waiting room, as an EXPLICIT HEAP rather than a std::priority_queue. | |
| WaitCmp | cmp |
| std::vector< Job > | server |
| std::vector< bool > | server_busy |
| std::vector< double > | server_start |
| instant the held job entered service | |
| std::vector< std::uint64_t > | server_tag |
| std::vector< bool > | server_blocked |
| A server holding a completed job it cannot hand on, because its destination is full. | |
| std::vector< bool > | server_held |
| A server HELD ACROSS A SYNCHRONOUS CALL. | |
| std::vector< std::size_t > | held_cls |
| std::vector< Job > | blocked_job |
| std::vector< std::size_t > | blocked_dest |
| std::vector< std::size_t > | blocked_dest_cls |
| std::vector< PsJob > | ps_jobs |
| double | ps_last_update = 0.0 |
| bool | state_dependent = false |
| True when the station's service RATE depends on its own population, i.e. | |
| double | util_peak = 1.0 |
| max(c, max(alpha)): the peak capacity the utilization is reported against. | |
| std::vector< double > | ps_cd |
| The class-dependent speed a SHARING station is running at right now, one entry per class. | |
| bool | has_breakdown = false |
| Server breakdown: the server alternates up and down on two clocks. | |
| bool | up = true |
| std::vector< double > | down_scale |
| std::vector< double > | down_rate_raw |
| The declared absolute rate, kept so the scale can be formed once E[S] is known. | |
| Sampler | failure_time |
| Sampler | repair_time |
| double | sd_last_update = 0.0 |
One station's mutable state.
Definition at line 425 of file ldes_engine.h.
| std::vector<std::size_t> line::ldes::engine::StationState::alfs_order |
ALFS walks the pools least-flexible first: fewest compatible classes.
Definition at line 583 of file ldes_engine.h.
| std::vector<std::vector<BalkRule> > line::ldes::engine::StationState::balk |
Definition at line 554 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::blocked_at |
Jobs held OUTSIDE this station's buffer but counted in its queue length: a BAS or BBS job whose destination is full occupies the upstream server and is charged to the destination, which is where it is queueing for.
Charging it upstream would let a full station report a queue below its own capacity while jobs pile up in front of it.
Definition at line 451 of file ldes_engine.h.
| std::vector<std::size_t> line::ldes::engine::StationState::blocked_dest |
Definition at line 618 of file ldes_engine.h.
| std::vector<std::size_t> line::ldes::engine::StationState::blocked_dest_cls |
Definition at line 619 of file ldes_engine.h.
| std::vector<Job> line::ldes::engine::StationState::blocked_job |
Definition at line 617 of file ldes_engine.h.
| std::vector<Job> line::ldes::engine::StationState::buffer |
The waiting room, as an EXPLICIT HEAP rather than a std::priority_queue.
FSP is why. Its order is the virtual finish time of a processor-sharing schedule over the residual work PRESENT AT THE STATION, so it changes whenever the station's composition does and cannot be stamped on a job when it arrives. A container that hides its storage cannot be reordered or rescanned; this one is scanned linearly for FSP and kept as a heap for every other discipline, whose keys are per-job constants.
Definition at line 595 of file ldes_engine.h.
| double line::ldes::engine::StationState::cap = std::numeric_limits<double>::infinity() |
Definition at line 433 of file ldes_engine.h.
| lang::CdScaling<double> line::ldes::engine::StationState::cd |
sn.cdscaling: beta_r(n), a per-class RATE at the station's population.
Definition at line 463 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::class_mean |
mean service per class, for SEPT/LEPT
Definition at line 453 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::classcap |
Definition at line 434 of file ldes_engine.h.
| WaitCmp line::ldes::engine::StationState::cmp |
Definition at line 596 of file ldes_engine.h.
| double line::ldes::engine::StationState::delayoff_at = std::numeric_limits<double>::infinity() |
when it shuts down
Definition at line 525 of file ldes_engine.h.
| Sampler line::ldes::engine::StationState::delayoff_time |
Definition at line 522 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::down_rate_raw |
The declared absolute rate, kept so the scale can be formed once E[S] is known.
Definition at line 667 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::down_scale |
Definition at line 665 of file ldes_engine.h.
| std::vector<lang::DropStrategy> line::ldes::engine::StationState::droprule |
sn.droprule, per class, declared on the DESTINATION station.
JMT's convention and the reference's: the policy belongs to the station whose capacity is limited, not to the upstream one whose server ends up blocked. A model that declared it on the source would be read as having no policy at all.
Definition at line 443 of file ldes_engine.h.
| Sampler line::ldes::engine::StationState::failure_time |
Definition at line 668 of file ldes_engine.h.
| bool line::ldes::engine::StationState::has_breakdown = false |
Server breakdown: the server alternates up and down on two clocks.
down_scale[r] is the RATE MULTIPLIER while down, down_rate(r) * E[S(i,r)], so the whole outage is expressed as a state-dependent rate change and needs no separate machinery: a zero multiplier stalls the job with its residual intact (nothing is rescheduled, so nothing departs until repair) and a positive one is the degraded server. That is exactly the reference's semantics – a breakdown does not evict the job in service, and downServiceRates degrades rather than stops.
Definition at line 663 of file ldes_engine.h.
| bool line::ldes::engine::StationState::has_cd = false |
Definition at line 464 of file ldes_engine.h.
| std::vector<bool> line::ldes::engine::StationState::has_patience |
Definition at line 547 of file ldes_engine.h.
| bool line::ldes::engine::StationState::has_pools = false |
HETEROGENEOUS SERVER POOLS, empty on a station whose servers are alike.
A pool is count servers that accept only compatible classes and serve them at a law of their own, so a model that declares them is a DIFFERENT system from the multiserver it would otherwise look like: flattening the pools into nservers answers that other system, plausibly and silently.
The slots are laid out POOL BY POOL in declaration order, so slot type_first[t] .. type_first[t] + type_count[t] - 1 belongs to pool t and server_type[slot] is the inverse. Every other part of the engine addresses a server by its slot and needs to know nothing about this.
Definition at line 571 of file ldes_engine.h.
| std::vector<bool> line::ldes::engine::StationState::has_retrial |
Definition at line 538 of file ldes_engine.h.
| bool line::ldes::engine::StationState::has_setup = false |
SETUP AND DELAY-OFF: a station that powers down when it falls idle.
The server runs a four-state machine. It starts OFF; an arrival puts it in SETUP for the setup time and only then does service begin; when it empties it enters DELAYOFF and shuts down when that timer expires, so a job arriving during the delay-off window pays NOTHING and one arriving after it pays the full setup. Collapsing the two idle states makes every arrival to an idle server pay the setup, which is the model of a server with no delay-off at all.
Definition at line 521 of file ldes_engine.h.
| std::vector<bool> line::ldes::engine::StationState::has_switchover |
Definition at line 508 of file ldes_engine.h.
| std::vector<std::size_t> line::ldes::engine::StationState::held_cls |
Definition at line 616 of file ldes_engine.h.
| lang::HeteroSchedPolicy line::ldes::engine::StationState::hetero_policy = lang::HeteroSchedPolicy::ORDER |
Definition at line 579 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::lld |
sn.lldscaling: the RATE multiplier when n jobs are present, indexed n-1.
It divides the sampled service time at an ordinary station and IS the effective server count at a sharing one – the same table read two ways, because a share of c servers and a c-fold rate are the same thing only for PS.
Definition at line 461 of file ldes_engine.h.
| std::size_t line::ldes::engine::StationState::lps_limit = 0 |
LPS admission cap; 0 = none.
Definition at line 432 of file ldes_engine.h.
| std::vector<int> line::ldes::engine::StationState::max_attempts |
Definition at line 539 of file ldes_engine.h.
| std::size_t line::ldes::engine::StationState::nservers = 1 |
Definition at line 431 of file ldes_engine.h.
| std::vector<bool> line::ldes::engine::StationState::off |
Definition at line 556 of file ldes_engine.h.
| double line::ldes::engine::StationState::orbit_last = 0.0 |
Definition at line 542 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::orbit_size |
live, per class
Definition at line 540 of file ldes_engine.h.
| bool line::ldes::engine::StationState::pas = false |
A PASS-AND-SWAP station serves an ORDERED LIST whose total rate is a function of the whole class sequence (Dorsman and Gardner 2024).
The rate of the token at position p is the INCREMENT mu(c1..cp) - mu(c1..c_{p-1}), which is what makes the station order-independent. On a completion at position p the departing job is not the one at p: the SWAP GRAPH chains forward from p to the last position reachable through it, and that job departs while the chain shifts into the hole. An empty swap graph is the plain OI station, where p itself departs.
Definition at line 477 of file ldes_engine.h.
| std::vector<Job> line::ldes::engine::StationState::pas_list |
Definition at line 480 of file ldes_engine.h.
| std::function<double(const std::vector<std::size_t>&)> line::ldes::engine::StationState::pas_rate |
Definition at line 478 of file ldes_engine.h.
| std::vector<std::vector<bool> > line::ldes::engine::StationState::pas_swap |
Definition at line 479 of file ldes_engine.h.
| std::uint64_t line::ldes::engine::StationState::pas_tag = 0 |
Definition at line 481 of file ldes_engine.h.
| std::vector<Sampler> line::ldes::engine::StationState::patience |
Reneging: the abandonment timer of a WAITING job, per class.
Definition at line 546 of file ldes_engine.h.
| std::size_t line::ldes::engine::StationState::poll_at = 0 |
the buffer the server is serving or heading to
Definition at line 501 of file ldes_engine.h.
| std::size_t line::ldes::engine::StationState::poll_budget = 0 |
remaining visit budget; 0 = exhausted
Definition at line 504 of file ldes_engine.h.
| std::size_t line::ldes::engine::StationState::poll_k = 1 |
Definition at line 506 of file ldes_engine.h.
| bool line::ldes::engine::StationState::poll_parked = false |
Definition at line 503 of file ldes_engine.h.
| bool line::ldes::engine::StationState::poll_switching = false |
Definition at line 502 of file ldes_engine.h.
| lang::PollingType line::ldes::engine::StationState::poll_type = lang::PollingType::EXHAUSTIVE |
Definition at line 505 of file ldes_engine.h.
| bool line::ldes::engine::StationState::polling = false |
A POLLING SERVER visits the per-class buffers in a fixed cyclic order, paying a SWITCHOVER on each leg.
It advances ONE STEP AT A TIME and pays that step's switchover whether or not the buffer it reaches holds work. Skipping ahead to the next non-empty buffer for a single switchover is a different and much faster discipline: it shortens the cycle and understates the waiting time by tens of percent against Takagi's exact formulas, which assume the walking server. The one exception is a lap made entirely of zero-time legs, which would spin forever at the same instant: there the server PARKS and the next arrival restarts it.
The switchover charged to a leg is the one stored against the buffer being LEFT – that is Takagi's r_i and what Queue.setSwitchover means – not the one against the buffer being entered.
Definition at line 500 of file ldes_engine.h.
| bool line::ldes::engine::StationState::preemptive = false |
Definition at line 429 of file ldes_engine.h.
| bool line::ldes::engine::StationState::ps = false |
Definition at line 428 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::ps_cd |
The class-dependent speed a SHARING station is running at right now, one entry per class.
It is cached rather than recomputed because ps_advance integrates the interval that just ENDED while the caller has already written the new population: reading the handle there would credit that interval at the speed that only starts now. ps_reschedule refreshes it in the same breath as it re-times the departures, which is the moment the new speed actually takes effect – the same flush-then-install order Accum::set_busy_scale uses for load dependence.
Definition at line 651 of file ldes_engine.h.
| std::vector<PsJob> line::ldes::engine::StationState::ps_jobs |
Definition at line 622 of file ldes_engine.h.
| double line::ldes::engine::StationState::ps_last_update = 0.0 |
Definition at line 623 of file ldes_engine.h.
| Sampler line::ldes::engine::StationState::repair_time |
Definition at line 668 of file ldes_engine.h.
| bool line::ldes::engine::StationState::resume = false |
PR (continue the residual) as against PI (redraw).
Definition at line 430 of file ldes_engine.h.
| std::vector<Sampler> line::ldes::engine::StationState::retrial |
RETRIAL: a job refused admission joins an ORBIT and tries again later, instead of being dropped or queueing.
The orbit is not a buffer. Its occupants are not at the station, do not occupy its capacity and are not in its queue length; they are a separate population that re-offers itself at the retrial rate. Treating a retrial job as queued makes the station hold more than its own capacity, which is exactly what the model says it cannot.
Definition at line 537 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::retrial_lost |
Definition at line 543 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::retried |
Definition at line 543 of file ldes_engine.h.
| Role line::ldes::engine::StationState::role = Role::Queue |
Definition at line 426 of file ldes_engine.h.
| lang::SchedStrategy line::ldes::engine::StationState::sched = lang::SchedStrategy::FCFS |
Definition at line 427 of file ldes_engine.h.
| double line::ldes::engine::StationState::sd_last_update = 0.0 |
Definition at line 669 of file ldes_engine.h.
| std::vector<Job> line::ldes::engine::StationState::server |
Definition at line 597 of file ldes_engine.h.
| std::vector<bool> line::ldes::engine::StationState::server_blocked |
A server holding a completed job it cannot hand on, because its destination is full.
It is NOT free: refusing to start a new service is the whole content of blocking, and a blocked slot treated as idle turns a blocking network into a lossless one with the same topology.
Definition at line 607 of file ldes_engine.h.
| std::vector<bool> line::ldes::engine::StationState::server_busy |
Definition at line 598 of file ldes_engine.h.
| std::vector<bool> line::ldes::engine::StationState::server_held |
A server HELD ACROSS A SYNCHRONOUS CALL.
Its job has left for the callee and the slot is NOT free: releasing it would let the caller serve someone else while its own call is outstanding, which is the asynchronous model under the synchronous one's name. Separate from server_blocked, which holds a COMPLETED job whose destination is full.
Definition at line 615 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::server_start |
instant the held job entered service
Definition at line 599 of file ldes_engine.h.
| std::vector<std::uint64_t> line::ldes::engine::StationState::server_tag |
Definition at line 600 of file ldes_engine.h.
| std::vector<std::size_t> line::ldes::engine::StationState::server_type |
per slot, its pool
Definition at line 572 of file ldes_engine.h.
| bool line::ldes::engine::StationState::setup_on = false |
the server has completed its setup
Definition at line 523 of file ldes_engine.h.
| bool line::ldes::engine::StationState::setup_running = false |
a setup is in progress
Definition at line 524 of file ldes_engine.h.
| Sampler line::ldes::engine::StationState::setup_time |
Definition at line 522 of file ldes_engine.h.
| bool line::ldes::engine::StationState::state_dependent = false |
True when the station's service RATE depends on its own population, i.e.
it declares a load- or class-dependence table.
Such a station cannot schedule a departure once and forget it: the rate in force changes every time the population does, so the residual work must be integrated forward and the completion re-timed at each change – the same discipline a sharing station needs, for a different reason. Applying the scaling only at service start would time every completion at the rate that happened to hold when it began.
Definition at line 636 of file ldes_engine.h.
| std::vector<Sampler> line::ldes::engine::StationState::svc |
Definition at line 555 of file ldes_engine.h.
| std::vector<Sampler> line::ldes::engine::StationState::switchover |
Definition at line 507 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::tot_orbit |
time integral of the orbit size
Definition at line 541 of file ldes_engine.h.
| std::vector<std::vector<bool> > line::ldes::engine::StationState::type_compat |
[pool][class]
Definition at line 575 of file ldes_engine.h.
| std::vector<std::size_t> line::ldes::engine::StationState::type_count |
per pool, its server count
Definition at line 574 of file ldes_engine.h.
| std::vector<std::size_t> line::ldes::engine::StationState::type_first |
per pool, its first slot
Definition at line 573 of file ldes_engine.h.
| std::vector<std::vector<bool> > line::ldes::engine::StationState::type_has_svc |
[pool][class], a law of its own
Definition at line 577 of file ldes_engine.h.
| std::vector<std::size_t> line::ldes::engine::StationState::type_order |
ALIS/FAIRNESS rotate this order; a used pool goes to the back.
Definition at line 581 of file ldes_engine.h.
| std::vector<std::vector<double> > line::ldes::engine::StationState::type_rate |
[pool][class], 1/mean, for FSF
Definition at line 578 of file ldes_engine.h.
| std::vector<std::vector<Sampler> > line::ldes::engine::StationState::type_svc |
[pool][class]
Definition at line 576 of file ldes_engine.h.
| bool line::ldes::engine::StationState::up = true |
Definition at line 664 of file ldes_engine.h.
| double line::ldes::engine::StationState::util_peak = 1.0 |
max(c, max(alpha)): the peak capacity the utilization is reported against.
Definition at line 638 of file ldes_engine.h.
| std::vector<double> line::ldes::engine::StationState::weight |
schedparam, the DPS/GPS weights
Definition at line 452 of file ldes_engine.h.
1.18.0