排队模型及其实践

排队模型及其分布

定义

一种信息源模型，特征是由输入、排队、服务三 个过程组成

  1. 输入过程

    • 请求总体:有限、无限
    • 请求到达方式:逐个、成批
    • 请求间隔:确定型、随机型
    • 请求之间的关系:相关的、独立的

  2. 排队规则
    损失制
    等待制
    混合制

  3. 服务规则

    • 多窗口、单窗口

    • 服务时间: 确定型、随机型

运行指标 和分类

  • 系统吞吐率：平均单位时间内被服务完的请求数量

  • 请求响应时间：请求在系统内的平均逗留时间

  • 系统利用率：服务连续繁忙的时间长度

分类和记号

  • X/Y/Z/m (或o,可省略 )来表示排队模型

    X:请求相继到达系统的间隔时间T的概率分布。
    Y:服务所耗费的服务时间 的概率分布
    Z: 系统内服务的个数;
    m : 系统内( 最大)排队容量 ;

  • M/M/n -
    请求到达系统时间间隔与服务时间均服从负指数，系
    统内设有n个服务窗口，
    系统容量为无限的等待制排队模型

最简单事件流: 泊松流

  • 泊松( Poisson )流，又称最简单事件流。
    其具有如下特点:

    1. 平稳性: 出现任意数量事件的概率只与时间区间t的大小有关，与t的位置无关

    2. 无后效性: 在互不相交的两个时间区间T1、T2内所出现的事件数是相互独立的

    3. 普通性:在同一瞬间多于一个事件出现的概率可忽略不计

      pn(t)=(λt)nn!e−λtp_n(t)=\frac{(\lambda t)^n}{n!}e^{-\lambda t}

  • 用户请求到来的事件流通常符合泊松分布

负指数分布

  • 当请求流为泊松流时,两个相继请求到达系统的 时间间隔 t 分布为:

F(t)=1−e−λtf(t)=λe−λtF(t)=P(T≤t)=1−P0(t)=1−e−λt\begin{aligned} F(t)&=1-e^{-\lambda t} &f(t)&=\lambda e^{-\lambda t} \\\\ F(t)&=P(T\leq t)=1-P_0(t)=1-e^{-\lambda t} \end{aligned}

  • 用 μ 表示单位时间内完成服务响应的事件均值, 则

F(t)=1−e−μtf(t)=μe−μt\begin{aligned} F(t)&=1-e^{-\mu t}\\f(t)&=\mu e^{-\mu t} \end{aligned}

排队模型的求解

M/M/1

考虑情况 M/M/1：
到达系统的请求符合排队模型，
按λ-泊松流到达；
系统响应时间按μ-负指数分布；
服务器数量为1.

如果顾客的到达强度为 $\lambda $ ，服务台的服务强度为 μ\mu

定义系统负载 p 为

ρ=λμ\rho = \frac{\lambda} {\mu}

当p<1p<1时，λ<μ,排队系统稳定；反之，任务不断累积导致不稳定

系统利用率：$$\rho=\frac\lambda\mu $$

顾客在系统内的平均排队时间：$$W_q=\frac\rho{\mu-\lambda}$$

顾客在系统内的平均逗留时间：$$W_s=\frac 1{\mu-\lambda}$$

第 p 个百分点的逗留时间: mp=−ln⁡(1−p/100)μ−λm_{\mathfrak{p}}=-\frac{\ln(1-p/100)}{\mu-\lambda}

系统中平均任务数：

E(N)=ρ1−ρE(N)=\frac{\rho}{1-\rho}

平均任务响应时间：

E(R)=E(N)λ−1=1μ−λE(R)=E(N)\lambda^{-1}=\frac{1}{\mu-\lambda}

为了优化服务性能，需要制定一个优化阈值由上推导得，第 p 个百分点的响应时间为

mp=−ln⁡(1−p/100)μ−λm_{\mathfrak{p}}=-\frac{\ln(1-p/100)}{\mu-\lambda}

M/M/N服务系统

如果顾客的到达强度为 $\lambda $ ，服务台的服务强度为 μ\mu ，服务台的个数为 n。

image-20231117104808051

Little’s Law 利特尔定律

在一个系统的长期稳定状态下，系统中负载的平 均数量L是平均到达率λ和负载在系统中停留的 平均时间W的乘积，即

L = λ × W

依据Little’s Law，我们可以得出在服务系统中的 三个重要指标：
负载流量、处理时间、负载最大 容量

排队模型的应用

  1. 物理模型
  2. 抽象为排队模型
  3. 计算基本元素
    到达率
    服务率
  4. 应用
    排队时间
    系统瓶颈
  • 邮件服务器
    系统支持的在线用户数和响应时间进行预测
    邮件服务器的资源瓶颈进行考察
  • AI服务的尾延迟