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.

See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    Polling.Info
    Derived description of the polling controller at a station.
    static class 
    Polling.Landing
    Result of a landing: the successor rows and the probability of each.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    MODE_PARK
    Landing mode: park (no work anywhere, every switchover immediate).
    static final int
    MODE_SWITCH
    Landing mode: enter the switchover into the resolved buffer.
    static final int
    MODE_VISIT
    Landing mode: start a visit at the resolved buffer.

  • Constructor Summary

    Constructors
    Constructor
    Description
    Polling()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    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.
    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.
    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.
    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.
    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).
    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.
    static Matrix
    project(Polling.Info pinfo, int[] trip)
    Project a full {pos, swk, ctr} triple onto the materialized columns.
    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.
    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.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • 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

    • 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 full {pos, swk, ctr} triple onto the materialized columns. The elided columns are reconstructible from the rest of the state (see get(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 full triple
      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 buffer of the job in service) or parked (and then its position is unobservable, so the first polled buffer 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}

    • 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)).
      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