Package jline.api.qsys

Class Qsys_mg1_ps

java.lang.Object
jline.api.qsys.Qsys_mg1_ps
public class Qsys_mg1_ps extends Object
Sojourn time distribution of the M/G/1 processor-sharing queue.

Jobs arrive in a Poisson stream of rate lambda at a single egalitarian processor-sharing server whose service requirement has Laplace-Stieltjes transform bhat(tau) and mean m1. Writing V(x) for the sojourn time of a tagged job of service requirement x and rho = lambda*m1 < 1, Ott (1984) and Yashkov (1983) express the conditional transform as

   E[exp(-s V(x))] = (1-rho) / D(s,x),

where D(s,x) is the inverse Laplace transform, evaluated at x, of

   f(tau;s) = [ (1-rho)*tau^2 - (1-rho)*lambda*(1-bhat(tau))*tau
                + s*rho*tau - s*lambda*(1-bhat(tau)) ]
              / [ tau^2 * (tau - s - lambda*(1-bhat(tau))) ].

The transform is exact but implicit, since f must be inverted in tau. For phase-type service f(tau;s) is a proper rational function of tau, the double pole at tau = 0 cancels, and D(s,x) is obtained in closed form as a finite sum of residues (or, for repeated poles, from the matrix exponential of the companion realization). This makes the M/PH/1-PS queue, hence every service law that can be fitted with a phase-type distribution, exactly solvable. For a service transform supplied as a callback, f is inverted in tau numerically on a Bromwich contour placed to the right of the dominant singularity tau*(s), the unique root of tau = s + lambda*(1-bhat(tau)) in the right half plane, which the fixed-point iteration of that equation reaches at geometric rate rho.

The conditional sojourn time is atomic on the lattice t = (k+1)*x, for k = 0,1,2,...: processor sharing gives every job in the system the same amount of work, so if the k jobs present on arrival all outlive the tagged job and no arrival intervenes, the sojourn is exactly (k+1)*x. For exponential service the masses are A_k = (1-rho)*rho^k*exp(-k*mu*x)*exp(-lambda*(k+1)*x), the k = 0 term being the probability of finding the system empty and sharing it with nobody, which is the only one that stays exact for general service. The k = 0 atom is removed before inverting in s; the remaining atoms make cdfCond jump and leave no density, so pdfCond is NaN on the lattice.

References: T. J. Ott, "The sojourn-time distribution in the M/G/1 queue with processor sharing", J. Appl. Prob. 21(2), 1984, pp. 360-378; S. F. Yashkov, "A derivation of response time distribution for an M/G/1 processor-sharing queue", Probl. Contr. Inform. Theory 12, 1983, pp. 133-148; Q. Zhen, C. Knessl, "Asymptotic expansions for the sojourn time distribution in the M/G/1-PS queue", Math. Meth. Oper. Res. 74, 2011, equations (2.2)-(2.5).

Port of MATLAB qsys_mg1_ps.m.

  • Method Details

    • qsys_mg1_ps

      public static QsysMg1PsResult qsys_mg1_ps(double lambda, double[] alpha, double[][] T, double[] x, double[] s, double[] t, int nterms)
      Sojourn time distribution with phase-type service PH(alpha,T).
      Parameters:
      lambda - Poisson arrival rate
      alpha - phase-type initial probability vector
      T - phase-type subgenerator
      x - service requirements to condition on, may be null
      s - transform arguments to tabulate, may be null
      t - times at which to evaluate the distribution, may be null
      nterms - function evaluations per numerical Laplace inversion, odd
      Returns:
      the tabulated result, still callable for other arguments

    • qsys_mg1_ps

      public static QsysMg1PsResult qsys_mg1_ps(double lambda, Qsys_mg1_ps.ServiceLST bhat, double m1, double[] x, double[] s, int nterms, Qsys_mg1_ps.ServicePDF pdf)
      Sojourn time distribution with the service law given by its transform.

      Only the transforms and their moments are available on this path: the time grid is rejected, because inverting a numerically inverted transform is unstable in double precision.

      Parameters:
      lambda - Poisson arrival rate
      bhat - service Laplace-Stieltjes transform
      m1 - mean service requirement
      x - service requirements to condition on, may be null
      s - transform arguments to tabulate, may be null
      nterms - function evaluations per numerical Laplace inversion, odd
      pdf - service density, needed to remove the conditioning, may be null
      Returns:
      the tabulated result, still callable for other arguments