Package jline.lang.state

Class Polling

java.lang.Object
jline.lang.state.Polling
All Implemented Interfaces:
Serializable
public class Polling extends Object implements Serializable
State-space helpers for polling stations. Port of the MATLAB State.polling* functions.

The polling controller is stored in the trailing local-variable block of the station state, whose width is sn.nvars(ind, 2*R). The block holds, in order, the columns [pos, swk, ctr]; each is materialized only when the discipline actually needs it, so that a polling station never carries state that its dynamics cannot distinguish.

  • pos index of the buffer the server is currently at (serving) or heading to (switching). Materialized only when at least one switchover is non-immediate: while a job is in service pos always equals the class of that job, and while the station is empty and every switchover is immediate the server position is unobservable.
  • swk 0 when the server sits at pos, otherwise the phase of the switchover PH into buffer pos. Materialized only when some switchover is non-immediate.
  • ctr the visit budget, materialized for every discipline except EXHAUSTIVE. GATED: jobs of class pos admitted at the polling instant that have not completed yet (the job in service counts as one of them), so the visit ends when ctr reaches 0. KLIMITED: services still permitted in this visit, the one in progress included. DECREMENTING: the target class-pos population, i.e. one below the level found at the polling instant (semi-exhaustive).

The three tangible controller configurations are SERVING(p) (swk=0, one class-p job in the service facility), SWITCHING(p) (swk>0, service facility empty) and PARKED (swk=0, facility empty, station empty; reachable only when every switchover is immediate, in which case a server that completes a full lap without finding work would otherwise cycle in zero time forever).

Immediate switchovers are NOT represented as states: taking their rate literally would put a ~1e8 rate in the generator (stiff, and a spurious state per buffer). They are instead folded into the enclosing transition by next(jline.lang.state.Polling.Info, int, int[], int, boolean), which walks the cyclic order until a tangible state.

Three further columns extend the block, again only when the feature that needs them is set (Queue.setPollingTable/setPollingOrder/setPollingTimer): src (load-dependent order with distinct timed legs: the buffer whose switchover law the server walks, stored as class index + 1, 0 for none), tht (visit timer phase, 0 when no timer runs or a non-preemptive timer has expired) and, under a GLOBAL timer, one trt_r column per polled class (rotation timer phase, 0 once expired). With a polling table pos holds the table POSITION, ring[pos] being the class served there; in the cyclic order ring is 0..R-1, so position and class coincide. The full controller vector handled by getFull(jline.lang.state.Polling.Info, jline.util.matrix.Matrix, int), setFull(jline.lang.state.Polling.Info, jline.util.matrix.Matrix, int[]) and blocks(jline.lang.state.Polling.Info, int, int[], int) is [pos, swk, ctr, src, tht, trt_0..trt_{R-1}], of width 5+R, and project(jline.lang.state.Polling.Info, int[]) keeps the materialized columns. Port of MATLAB State.pollingInfo/pollingAdvance/pollingChoose/pollingLandAll.

See Also:

  • Field Details

    • MODE_VISIT

      public static final int MODE_VISIT
      Landing mode: start a visit at the resolved buffer.
      See Also:

    • MODE_SWITCH

      public static final int MODE_SWITCH
      Landing mode: enter the switchover into the resolved buffer.
      See Also:

    • MODE_PARK

      public static final int MODE_PARK
      Landing mode: park (no work anywhere, every switchover immediate).
      See Also:

  • Constructor Details

    • Polling

      public Polling()

  • Method Details

    • requirePH

      public static void requirePH(Polling.Info pinfo)
      Refuses a polling station whose switchover legs are not all phase-type. Called by the state-space walkers (AfterEventStation, Solver_ssa_nrm) before they read swD0/swD1: info(jline.lang.NetworkStruct, int) sizes a non-Markovian leg as one placeholder phase and records it in nonPH, with no matrices to walk.

    • info

      public static Polling.Info info(NetworkStruct sn, int ind)
      Derived description of the polling controller at the station of node ind, or null when the node is not a polling station. Memoized on the node parameters: this is read once per state per synchronization while the generator is built, and rebuilding it (map_pie and all) per call is orders of magnitude slower than the analysis itself.
      Parameters:
      sn - network structure
      ind - node index
      Returns:
      the controller description, or null

    • budget

      public static int budget(Polling.Info pinfo, int nbufq)
      Initial value of the ctr column of a visit that starts at a buffer holding nbufq waiting jobs. nbufq is the class-q population at the polling instant: the service facility is empty when a visit starts, so it is the whole class-q population at the station.
      Parameters:
      pinfo - controller description
      nbufq - waiting jobs of the visited class at the polling instant
      Returns:
      the initial visit budget

    • next

      public static int[] next(Polling.Info pinfo, int pos, int[] nbuf, int R, boolean arrived)
      Resolve the tangible controller state a polling server reaches once it stops serving buffer pos. Port of MATLAB State.pollingNext.

      The walk is what makes an Immediate switchover a zero-time leg rather than a state: the server passes straight through such a buffer when it has no work, and only stops at a buffer that either has work or costs time to reach. This is the classical cyclic-polling discipline, in which the server visits the buffers in strict cyclic order and pays the switchover of every buffer it moves to, whether or not that buffer turns out to have work.

      Parameters:
      pinfo - controller description
      pos - buffer the server is leaving, or has arrived at
      nbuf - per-class waiting counts (the service facility is empty)
      R - number of classes
      arrived - when true the server has just ARRIVED at pos and pos itself is examined first, without charging its switchover a second time; when false the server is LEAVING pos and the walk starts at pos+1
      Returns:
      {q, mode, budget}; mode is MODE_VISIT, MODE_SWITCH or MODE_PARK

    • blocks

      public static List<int[]> blocks(Polling.Info pinfo, int srvclass, int[] nbuf, int R)
      Every controller configuration compatible with a service facility holding a class-srvclass job (-1 when empty) and buffers holding nbuf. Returns one {pos, swk, ctr} triple per configuration, in full regardless of which columns are materialized (project with project(jline.lang.state.Polling.Info, int[])), and an empty list when the combination is unoccupiable.

      PARKED is pruned even when no column is materialized: leaving an idle server with a non-empty station in the state space would make the generator reducible.

      Parameters:
      pinfo - controller description
      srvclass - class in the service facility, -1 when empty
      nbuf - per-class waiting counts
      R - number of classes
      Returns:
      the admissible {pos, swk, ctr} triples

    • land

      public static Polling.Landing land(Polling.Info pinfo, int q, int mode, int budget, Matrix spaceBuf, Matrix spaceSrv, Matrix spaceVar, Matrix K, Matrix Ks, Map<JobClass,Matrix> pieist, List<JobClass> jobclasses, int R)
      Materialize the state rows a polling server lands in after next(jline.lang.state.Polling.Info, int, int[], int, boolean) has resolved (q, mode, budget). The three space rows describe the station at the instant the decision is taken, i.e. with the completed job (if any) already removed from the service facility.

      The probabilities split a landing across the entry phases of a phase-type: which phase a service or a switchover starts in is a random choice, so one decision yields one row per entry phase, weighted by the corresponding entry probability. Callers fold them into the transition rate rather than into outprob, since the branching happens at the instant the active event fires.

      Parameters:
      pinfo - controller description
      q - resolved buffer
      mode - MODE_VISIT, MODE_SWITCH or MODE_PARK
      budget - visit budget for MODE_VISIT
      spaceBuf - single buffer row
      spaceSrv - single server row
      spaceVar - single local-variable row
      K - per-class phase counts
      Ks - per-class phase offsets
      pieist - per-class entry probability vectors of the station
      R - number of classes
      Returns:
      the successor rows and their probabilities

    • space

      public static Matrix space(NetworkStruct sn, int ind, Matrix space, Matrix K)
      Append the polling controller columns to the rows of space, which must hold the [buffer, server, routing-variable] layout of a polling station. Rows are expanded into one row per controller configuration the discipline can occupy, and rows for which no configuration exists are dropped.

      Enumerating the controller per row rather than as a blind cartesian product is what keeps the state space tight and the chain irreducible: pos is pinned to the class in service, a switchover excludes a busy service facility, and a park excludes a non-empty station. A cartesian product would instead admit states such as "serving buffer 1 while a class-2 job occupies the server", which no transition can reach or leave consistently with the marginals.

      Parameters:
      sn - network structure
      ind - node index
      space - the [buffer, server, routing-var] rows
      K - per-class phase counts
      Returns:
      the rows with the controller appended

    • project

      public static Matrix project(Polling.Info pinfo, int[] trip)
      Project a controller vector onto the materialized columns. The vector is either a {pos, swk, ctr} triple or a full [pos, swk, ctr, src, tht, trt_0..trt_{R-1}] vector; missing entries read as 0. The elided columns are reconstructible from the rest of the state (see getFull(jline.lang.state.Polling.Info, jline.util.matrix.Matrix, int)), so keeping them would split each state into copies no observation can tell apart.
      Parameters:
      pinfo - controller description
      trip - the controller vector
      Returns:
      a 1-by-width row, empty when nothing is materialized

    • get

      public static int[] get(Polling.Info pinfo, Matrix spaceVar, int srvclass)
      Read the polling controller out of the local-variable columns of a single state row. The polling block occupies the trailing width columns of spaceVar, so it is located by counting back from the end.

      The elided columns are reconstructed here, so callers always see a complete controller. pos: with no materialized column every switchover is immediate, so the server is either serving (and then it stands at the first position of the class in service) or parked (and then its position is unobservable, so the first polled position is canonical). swk: no switchover takes time, so the server is never inside one. ctr: the discipline is EXHAUSTIVE, which bounds a visit by the buffer draining rather than by a budget.

      Parameters:
      pinfo - controller description
      spaceVar - the local-variable columns of one state row
      srvclass - class in the service facility, -1 when empty
      Returns:
      {pos, swk, ctr}

    • getFull

      public static int[] getFull(Polling.Info pinfo, Matrix spaceVar, int srvclass)
      Read the full controller vector [pos, swk, ctr, src, tht, trt_0..trt_{R-1}] out of the local-variable columns of a single state row. Columns that info(jline.lang.NetworkStruct, int) elides are reconstructed as in get(jline.lang.state.Polling.Info, jline.util.matrix.Matrix, int): src as the one law shared by every timed load-dependent leg, the rest as 0. Port of MATLAB State.pollingGetFull.
      Parameters:
      pinfo - controller description
      spaceVar - the local-variable columns of one state row
      srvclass - class in the service facility, -1 when empty
      Returns:
      the full controller vector, of length 5+R

    • set

      public static Matrix set(Polling.Info pinfo, Matrix spaceVar, int pos, int swk, int ctr)
      Write the polling controller into the local-variable columns of a state row. Columns that are not materialized are dropped: they are reconstructible from the rest of the state (see get(jline.lang.state.Polling.Info, jline.util.matrix.Matrix, int)). The src, tht and trt columns are left unchanged.
      Parameters:
      pinfo - controller description
      spaceVar - the local-variable columns of one state row (copied)
      pos - server position
      swk - switchover phase, 0 when the server sits at pos
      ctr - visit budget
      Returns:
      the updated local-variable row

    • setFull

      public static Matrix setFull(Polling.Info pinfo, Matrix spaceVar, int[] v)
      Write the full controller vector into the local-variable columns of a state row, dropping the columns info(jline.lang.NetworkStruct, int) elides. Port of MATLAB State.pollingSetFull.
      Parameters:
      pinfo - controller description
      spaceVar - the local-variable columns of one state row (copied)
      v - the full controller vector
      Returns:
      the updated local-variable row

    • init

      public static Matrix init(Polling.Info pinfo, int[] nbuf, int srvclass)
      Canonical initial value of the polling controller columns for a station whose buffers hold nbuf and whose service facility holds a class-srvclass job (-1 when empty). The row is always one that blocks(jline.lang.state.Polling.Info, int, int[], int) also enumerates. Port of MATLAB State.pollingInit.
      Parameters:
      pinfo - controller description
      nbuf - per-class waiting counts
      srvclass - class in the service facility, -1 when empty
      Returns:
      a 1-by-width row

    • advance

      public static Polling.Advance advance(Polling.Info pinfo, int[] c0, int[] nbuf, boolean arrived)
      Resolve every tangible controller state a polling server can reach once it stops serving, generalizing next(jline.lang.state.Polling.Info, int, int[], int, boolean) to polling tables, load-dependent orders and visit timers. Port of MATLAB State.pollingAdvance.

      c is the full controller vector at the decision instant, pos being the position the server LEAVES (arrived false) or has just reached (arrived true). nbuf holds the buffer contents with the service facility empty. A decision may branch over the entry phases of a switchover, of a LOCAL timer or, in GLOBAL mode, of the rotation timer restarted at each token arrival.

      Parameters:
      pinfo - controller description
      c0 - full controller vector
      nbuf - per-class waiting counts
      arrived - whether the server has just arrived at pos
      Returns:
      the outcomes with their probabilities, summing to one

    • choose

      public static int choose(Polling.Info pinfo, int i, int[] nbuf)
      Next buffer of a load-dependent polling order (Haverkort section 16.2.4), decided when the server stops serving buffer i with buffers nbuf (service facility empty). Returns -1 when no polled buffer holds work. SKIPEMPTY: the first non-empty buffer in cyclic order after i, i itself last. LQF: the longest queue, ties to the first in cyclic order after i, i last. THRESHOLD: the priority class when its buffer holds more than L jobs, else SKIPEMPTY. Port of MATLAB State.pollingChoose.
      Parameters:
      pinfo - controller description
      i - buffer the server leaves (0-based)
      nbuf - per-class waiting counts
      Returns:
      the chosen buffer (0-based), or -1

    • landAll

      public static Polling.LandingAll landAll(Polling.Info pinfo, Polling.Advance B, Matrix spaceBuf, Matrix spaceSrv, Matrix spaceVar, Matrix K, Matrix Ks, Map<JobClass,Matrix> pieist, List<JobClass> jobclasses)
      Materialize the state rows of the outcomes of advance(jline.lang.state.Polling.Info, int[], int[], boolean), as land(jline.lang.state.Polling.Info, int, int, int, jline.util.matrix.Matrix, jline.util.matrix.Matrix, jline.util.matrix.Matrix, jline.util.matrix.Matrix, jline.util.matrix.Matrix, java.util.Map<jline.lang.JobClass, jline.util.matrix.Matrix>, java.util.List<jline.lang.JobClass>, int) does for next(jline.lang.state.Polling.Info, int, int[], int, boolean). A visit pulls a waiting class-q job into service, split across the entry phases of its service; a switchover or a park moves no job. Port of MATLAB State.pollingLandAll.