Lec7 处理器共享排队模型 排队论及其应用 教学课件.pptVIP

排队论及其应用Lecture 7 处理器共享排队模型 中国科学技术大学 计算机科学与技术学院 田 野 * 处理器共享的排队模型 类似M/M/1 客户单个到达，到达速率λ 服务器服务一个客户的时间服从指数分布，服务速率是μ 当系统中有多个客户时，这些客户分享服务器的服务能力—如果有C个客户，每个客户完成服务的时间是期望为C/μ的指数分布 客户进入系统，立刻开始服务 记为M/M/1-PS，PS代表Processor Sharing 例如 计算机处理器通过分时的办法处理多个进程 路由器分时处理多个TCP流 * 求解M/M/1-PS 稳态条件λμ 关注状态i 用户单个到达，发生从i到i+1的迁移，用户到达速率是λ 一个用户完成服务离开，发生从i到i-1的迁移 当前i个客户接受服务，剩余服务时间视为i个期望为i/ μ的指数分布的随机变量，其中最小变量的分布服从期望为1/ μ的指数分布 从i到i-1的迁移速率是μ 与M/M/1相同！ * 求解M/M/1-PS 同M/M/1，稳态下，系统中有i个客户的概率 系统中平均客户人数L和客户平均逗留时间W * 单个客户的停留时间 假设在进入排队系统前，每个客户被随机分配一个服务量x，即如果这个客户独占服务器，所需要的服务时间是x，显然E[x]=1/μ 在M/M/1中，服务量x的客户在系统中停留时间E[W|x]=Wq+x 在M/M/1-PS中，E[W|x]=？ * 在M/M/1-PS中，客户无需排队，每个客户在系统中时间应严格与x成正比，W(x)=cx，c是一个常数 已知并且可知换言之，在每一个客户看来，服务器使用所有服务能力的1-ρ服务她。 * M/G/1-PS 服务器服务能力为C 几个记号 x：一个客户的服务量 FX(x)：客户服务量的CDF分布 N(x)：系统中服务量≤x的客户的平均数量 T(x)：系统中已经接受x服务量的客户在系统中平均耗时 n(x)： * 考虑一个黑盒 当客户已经完成了x的服务量，并且已经在系统中平均滞留了T(x)的时间，进入黑盒 当客户完成了x+Δx的服务量，并且平均滞留T(x+Δx)，离开黑盒 * 分析 客户进入黑盒的速率，λ(1-FX(x)) 客户在黑盒中滞留时间 根据Little’s law * 将Δx?0，有 另一方面，系统中“年龄”为x的客户人数满足 两者结合有 考虑一个x?∞的客户，这个客户将很长时间稳定地占用C(1-ρ)的服务能力 * 考虑把这个“大客户”排除后的排队系统 两式结合，n(0)/λ=1/ C(1-ρ)， 因此 考虑所有的服务量分布 * 例子：Download data traffic in a cellular system The HSPDA protocol (High speed downlink packet access) of 3G cellular systems uses a time-division type multiplexing: the base station (BS) transmits at full power to only one user in each time slot. If slots are assigned in a round robin fashion to the active users, then the BS station realizes a PS queue for the downlink traffic. * Link adaptation: the bit rate is adapted to the radio channel conditions. The rate goes down with the distance r from the BS as signal becomes weaker, e.g., C(r) is the maximum bit rate for a user at distance r when there are n users active in the cell, the rate is C(r)/n. * Assumptions: The cell is approximated by a circular disk with radius R Flows arrive at the base station at total rate λ (Poisson process). Each flow has a size X independently drawn from some distribution with mean . The locatio