Package jline.lang.nodes

Class Queue

java.lang.Object
jline.lang.Element
jline.lang.NetworkElement
jline.lang.nodes.Node
jline.lang.nodes.StatefulNode
jline.lang.nodes.ServiceNode
jline.lang.nodes.Station
jline.lang.nodes.ServiceStation
jline.lang.nodes.Queue
All Implemented Interfaces:
Serializable, Copyable
Direct Known Subclasses:
Delay
public class Queue extends ServiceStation implements Serializable
A queueing station that processes jobs according to various scheduling strategies.

The Queue node is the fundamental service station in queueing networks. It models a system where jobs wait in a buffer and are processed by one or more servers according to a scheduling strategy. Common examples include CPU schedulers, disk I/O queues, network routers, and service desks.

Key features:

  • Multiple scheduling strategies: FCFS, PS, LCFS, priority-based, etc.
  • Single or multi-server configurations
  • Load-dependent and class-dependent service rates
  • Support for preemptive and non-preemptive policies
  • Polling server capabilities with various polling types
  • Switchover times between job classes

Since:
1.0
See Also:

  • Field Details

    • setupTimes

      protected Map<JobClass,Distribution> setupTimes
      Setup time distributions for function tasks (cold start time). Maps job classes to their setup time distributions.

    • delayOffTimes

      protected Map<JobClass,Distribution> delayOffTimes
      Delay-off time distributions for function tasks (teardown time). Maps job classes to their delay-off time distributions.

  • Constructor Details

    • Queue

      public Queue(Network model, String name, SchedStrategy schedStrategy)
      Creates a new queueing station with the specified scheduling strategy. Configures the appropriate server type based on the scheduling strategy. The queue is automatically added to the network model.
      Parameters:
      model - the network model to add this queue to
      name - the name for this queueing station
      schedStrategy - the scheduling strategy to use (e.g., FCFS, PS, LCFS)
      Throws:
      RuntimeException - if the scheduling strategy is not supported

    • Queue

      public Queue(Network model, String name)
      Creates a new queueing station with default processor sharing (PS) scheduling.
      Parameters:
      model - The network model to add this queue to
      name - The name for this queueing station

  • Method Details

    • containsJobClass

      public boolean containsJobClass(JobClass jobClass)
      Checks whether this queue has a service process configured for the specified job class.
      Parameters:
      jobClass - The job class to check
      Returns:
      true if a service process exists for this job class, false otherwise

    • getSchedPolicy

      public SchedStrategyType getSchedPolicy()
      Gets the scheduling policy type (preemptive or non-preemptive).
      Returns:
      The scheduling policy type (PR for preemptive, NP for non-preemptive)

    • setService

      public void setService(SerializableFunction<Matrix,Double> muFun)
      Sets the total service rate function mu(c) of a pass-and-swap (PAS) queue. An order-independent/PAS queue is parameterized by mu(c) as a whole, not by per-class service distributions; this overload of setService accepts the mu(c) function directly.
      Parameters:
      muFun - maps the ordered state vector c (1xN row Matrix of 0-based class indices, c(0) oldest) to the scalar total service rate

    • setServiceRateFunction

      public void setServiceRateFunction(SerializableFunction<Matrix,Double> muFun)
      Sets the total service rate function mu(c) of a pass-and-swap (PAS) queue. Also derives a representative per-class rate mu([r]) (single class-r job) so the standard rate/process machinery stays consistent; the authoritative service description remains mu(c).
      Parameters:
      muFun - the mu(c) service rate function

    • getServiceRateFunction

      public SerializableFunction<Matrix,Double> getServiceRateFunction()
      Returns the mu(c) service rate function of a PAS queue, or null.
      Returns:
      the mu(c) function

    • checkPermInvariance

      public Queue.PermCheckResult checkPermInvariance(double[] Nvec, double cap)
      Checks the order-independence (OI) condition on the service rate mu(c): the rate of the job in position j must depend only on the jobs at or ahead of it (positions 1..j) and not on those behind. Since the position-j rate is the prefix increment mu(c[:j]) - mu(c[:j-1]), tail-independence is structural; the substantive requirement is that this increment be independent of the order of the jobs ahead, which (by induction on prefix length) is equivalent to mu(c) being permutation- invariant. Enumerates the reachable multisets (per-class counts <= Nvec, total <= cap) when small, otherwise samples and sets partial=true.

    • setSwapGraph

      public void setSwapGraph(Matrix graph)
      Sets the class compatibility/swap graph of a pass-and-swap (PAS) queue.
      Parameters:
      graph - (nclasses x nclasses) adjacency matrix; entry (r,s) nonzero iff, upon completion of a class-r job, a waiting class-s job may take its place. Undirected; self-loops allowed.

    • getSwapGraph

      public Matrix getSwapGraph()
      Returns the (nclasses x nclasses) swap graph of a PAS queue, or null.
      Returns:
      the swap graph matrix

    • getSchedStrategy

      public SchedStrategy getSchedStrategy()
      Gets the scheduling strategy used by this queue.
      Overrides:
      getSchedStrategy in class Station
      Returns:
      The scheduling strategy (e.g., FCFS, PS, LCFS, etc.)

    • getSchedStrategyPar

      public double getSchedStrategyPar(JobClass jobClass)
      Gets the scheduling strategy parameter for a specific job class.

      For strategies like DPS (Discriminatory Processor Sharing) and GPS (Generalized Processor Sharing), this returns the weight or priority parameter for the job class.

      Overrides:
      getSchedStrategyPar in class ServiceNode
      Parameters:
      jobClass - The job class to get the parameter for
      Returns:
      The scheduling parameter value, or 0.0 if not set

    • getService

      public Distribution getService(JobClass jobClass)
      Gets the service time distribution for a specific job class.
      Parameters:
      jobClass - The job class to get the service distribution for
      Returns:
      The service time distribution for this job class

    • setItemServiceRate

      public void setItemServiceRate(Cache cache, JobClass jobinClass, int item, double serviceRate)
      Override, at this queue, the retrieval service rate for a single item of the read class jobinClass in the given cache's retrieval system. The default (when not overridden) is the read class's own service distribution at this queue. item is 0-based.
      Parameters:
      cache - the cache whose retrieval system contains this queue
      jobinClass - the read class that creates the retrieval request
      item - the requested item (0-based)
      serviceRate - exponential service rate for the item at this queue

    • printSummary

      public void printSummary()
      Prints a summary of this queue's configuration to standard output.

      The summary includes the queue name, service processes for each job class, their mean service times and squared coefficients of variation, number of servers, and output routing configuration.

      Overrides:
      printSummary in class Node

    • setClassDependence

      public void setClassDependence(SerializableFunction<Matrix,Matrix> beta)
      Sets a class-dependent scaling function for service rates.

      The function takes a matrix representing the number of jobs of each class at the station and returns the service rate scaling. It may return either a 1x1 matrix, i.e. a chain-independent scaling beta_i(n) shared by every class, or a length-R row vector [beta_{i,1}(n), ..., beta_{i,R}(n)] giving each class its own rate at the same population, which expresses Sauer's chain-dependent service rates mu_{r,i}(n) (Sauer 1983, eq. (40)). This enables modeling of systems where service rates depend on the job mix.

      Parameters:
      beta - A function that maps job class populations to a service rate scaling
      Throws:
      RuntimeException - if the scheduling strategy doesn't support class dependence

    • setClassDependence

      public void setClassDependence(SerializableFunction<Matrix,Matrix> beta, Matrix peakRatePerClass)
      Sets a class-dependent service-rate scaling and its required peak rate per class. Utilization at the station is reported as U = T*S/peak.
      Parameters:
      beta - maps the per-class population vector to a service-rate scaling
      peakRatePerClass - 1x1 (broadcast) or 1xR peak rate scaling per class

    • setLoadDependence

      public void setLoadDependence(Matrix alpha)
      Sets load-dependent service rate scaling factors.

      Each element alpha[n] specifies the service rate scaling when there are n jobs at the station. This enables modeling of systems where performance degrades under load.

      Parameters:
      alpha - A matrix of scaling factors indexed by the number of jobs
      Throws:
      RuntimeException - if the scheduling strategy doesn't support load dependence

    • setNumberOfServers

      public void setNumberOfServers(int numberOfServers)
      Sets the number of servers at this queueing station.

      For infinite server (IS) queues, this method has no effect as they always have unlimited servers.

      Overrides:
      setNumberOfServers in class Station
      Parameters:
      numberOfServers - The number of parallel servers (must be positive)

    • setSchedStrategyPar

      public void setSchedStrategyPar(JobClass jobClass, double weight)
      Sets the scheduling strategy parameter for a specific job class.

      For weighted scheduling strategies (DPS, GPS, etc.), this sets the weight or priority parameter that determines the job class's share of the service capacity.

      Parameters:
      jobClass - The job class to set the parameter for
      weight - The scheduling parameter value (e.g., weight, priority)

    • setLimit

      public void setLimit(int limit)
      Sets the maximum number of jobs for LPS scheduling. For LPS: limit is the max number of jobs that can execute in PS mode.
      Parameters:
      limit - the maximum number of concurrent jobs in PS mode
      Throws:
      RuntimeException - if called on non-LPS queue

    • setPollingType

      public void setPollingType(PollingType pollingType)
      Sets the polling type for this queue (only valid for POLLING scheduling strategy).
      Parameters:
      pollingType - the polling type (GATED, EXHAUSTIVE, or KLIMITED)

    • setPollingType

      public void setPollingType(PollingType pollingType, int k)
      Sets the polling type for this queue with K value for K-LIMITED (only valid for POLLING scheduling strategy).
      Parameters:
      pollingType - the polling type (GATED, EXHAUSTIVE, or KLIMITED)
      k - the K value for K-LIMITED polling (ignored for other types)

    • setPollingK

      public void setPollingK(int k)
      Sets the K value for K-LIMITED polling (only valid for POLLING scheduling strategy with K-LIMITED type).
      Parameters:
      k - the K value (must be greater than 0)

    • setSwitchover

      public void setSwitchover(JobClass jobClass, Distribution switchoverTime)
      Sets the switchover time for a job class (only valid for POLLING scheduling strategy).
      Parameters:
      jobClass - the job class
      switchoverTime - the switchover time distribution

    • setSwitchover

      public void setSwitchover(JobClass fromClass, JobClass toClass, Distribution switchoverTime)
      Sets the switchover time from one job class to another (for general scheduling strategies).
      Parameters:
      fromClass - the job class to switch from
      toClass - the job class to switch to
      switchoverTime - the switchover time distribution

    • getSwitchover

      public Distribution getSwitchover(JobClass fromClass, JobClass toClass)
      Gets the switchover time from one job class to another.
      Parameters:
      fromClass - the job class to switch from
      toClass - the job class to switch to
      Returns:
      the switchover time distribution, or null if not set

    • getSwitchover

      public Distribution getSwitchover(JobClass jobClass)
      Gets the switchover time for a job class (POLLING scheduling strategy).
      Parameters:
      jobClass - the job class
      Returns:
      the switchover time distribution, or null if not set

    • setDelayOff

      public void setDelayOff(JobClass jobClass, Distribution setupTime, Distribution delayoffTime)
      Sets the setup time and delay off time for a job class. This is typically used for function-based tasks that have initialization overhead.
      Parameters:
      jobClass - the job class
      setupTime - the setup time distribution
      delayoffTime - the delay off time distribution

    • getSetupTime

      public Distribution getSetupTime(JobClass jobClass)
      Gets the setup time distribution for a job class.
      Parameters:
      jobClass - the job class
      Returns:
      the setup time distribution, or null if not set

    • getDelayOffTime

      public Distribution getDelayOffTime(JobClass jobClass)
      Gets the delay-off time distribution for a job class.
      Parameters:
      jobClass - the job class
      Returns:
      the delay-off time distribution, or null if not set

    • isDelayOffEnabled

      public boolean isDelayOffEnabled()
      Checks if this queue has delay-off times enabled. Delay-off is considered enabled if any job class has both a setup time and a delay-off time distribution configured.
      Returns:
      true if delay-off is enabled, false otherwise

    • addServerType

      public void addServerType(ServerType serverType)
      Adds a server type to this queue for heterogeneous multiserver configuration.

      When server types are added, the queue becomes a heterogeneous multiserver queue where different server types can have different service rates and serve different subsets of job classes.

      The total number of servers at this queue becomes the sum of all server type counts.

      Parameters:
      serverType - the server type to add
      Throws:
      IllegalArgumentException - if serverType is null or already added

    • getServerTypes

      public List<ServerType> getServerTypes()
      Gets the list of server types configured for this queue.
      Returns:
      a new list containing the server types

    • getNumServerTypes

      public int getNumServerTypes()
      Gets the number of server types configured for this queue.
      Returns:
      the number of server types, or 0 if homogeneous

    • isHeterogeneous

      public boolean isHeterogeneous()
      Checks if this queue is configured as a heterogeneous multiserver queue.
      Returns:
      true if server types are defined, false for homogeneous queue

    • setHeteroSchedPolicy

      public void setHeteroSchedPolicy(HeteroSchedPolicy policy)
      Sets the scheduling policy for heterogeneous servers.

      This policy determines how jobs are assigned to server types when a job's class is compatible with multiple server types.

      Parameters:
      policy - the heterogeneous scheduling policy
      Throws:
      IllegalArgumentException - if policy is null

    • getHeteroSchedPolicy

      public HeteroSchedPolicy getHeteroSchedPolicy()
      Gets the scheduling policy for heterogeneous servers.
      Returns:
      the heterogeneous scheduling policy

    • setService

      public void setService(JobClass jobClass, ServerType serverType, Distribution distribution)
      Sets the service time distribution for a specific job class and server type.

      This method is used for heterogeneous multiserver queues where different server types may have different service rates for the same job class.

      Parameters:
      jobClass - the job class
      serverType - the server type
      distribution - the service time distribution
      Throws:
      IllegalArgumentException - if any parameter is null or serverType is not in this queue

    • getService

      public Distribution getService(JobClass jobClass, ServerType serverType)
      Gets the service time distribution for a specific job class and server type.
      Parameters:
      jobClass - the job class
      serverType - the server type
      Returns:
      the service time distribution, or null if not set

    • getHeteroServiceDistributions

      public Map<ServerType,Map<JobClass,Distribution>> getHeteroServiceDistributions()
      Gets all heterogeneous service distributions for this queue.
      Returns:
      the map of server type to job class to distribution

    • getServerType

      public ServerType getServerType(int id)
      Gets a server type by its ID.
      Parameters:
      id - the server type ID
      Returns:
      the server type, or null if not found

    • getServerType

      public ServerType getServerType(String name)
      Gets a server type by its name.
      Parameters:
      name - the server type name
      Returns:
      the server type, or null if not found

    • validateCompatibility

      public boolean validateCompatibility()
      Checks if all job classes have at least one compatible server type.

      This validation is important because in heterogeneous queues, every job class must be able to be served by at least one server type.

      Returns:
      true if all job classes have at least one compatible server type

    • setImmediateFeedback

      public void setImmediateFeedback(boolean enabled)
      Enables or disables immediate feedback for all job classes at this queue. When enabled, jobs that self-loop at this station stay in service instead of rejoining the queue.
      Parameters:
      enabled - true to enable immediate feedback for all classes, false to disable

    • setImmediateFeedback

      public void setImmediateFeedback(JobClass jobClass)
      Enables immediate feedback for a specific job class at this queue.
      Parameters:
      jobClass - the job class to enable immediate feedback for

    • setImmediateFeedbackForClasses

      public void setImmediateFeedbackForClasses(List<JobClass> jobClasses)
      Enables immediate feedback for multiple job classes at this queue.
      Parameters:
      jobClasses - list of job classes to enable immediate feedback for

    • hasImmediateFeedback

      public boolean hasImmediateFeedback()
      Checks if immediate feedback is enabled for any class at this queue.
      Returns:
      true if immediate feedback is enabled for at least one class

    • hasImmediateFeedback

      public boolean hasImmediateFeedback(int classId)
      Checks if immediate feedback is enabled for a specific class at this queue.
      Parameters:
      classId - the class index (0-based)
      Returns:
      true if immediate feedback is enabled for the specified class

    • getImmediateFeedbackClasses

      public Set<Integer> getImmediateFeedbackClasses()
      Gets the set of class indices with immediate feedback enabled.
      Returns:
      set of class indices, or null if none are set

    • isImmediateFeedbackAll

      public boolean isImmediateFeedbackAll()
      Checks if immediate feedback is enabled for all classes.
      Returns:
      true if immediate feedback is enabled for all classes